HomeTom - CS

Wednesday, April 29, 2009

Thursday, April 16, 2009

Programming Pearls - Reading notes

==## Part I ##==Preliminaries

==Column 1== Cracking the Oyster

The major point is find the optimal solution of a problem, instead of going straight with a rash solution.
The coding example is soring with bit vector (aka bitmap).

==Column 2== Aha! Algorithms

- binary search
* search
* find bug by setting checking points in a binary search pattern
* find missing element in an integer range
* finding root for equation: bisection method in numerical analysis

- the power of primitives
Problem: rotating an array ab to ba.
Solutions:
* copying. but this is space inefficient
* juggling
* recursive swapping
* define primitive action reverse(): a b -> a^r b -> a^r b^r -> b a

- sorting
Problem: find anagrams in a dictionary.
Solution: get signature for each word.

==Column 3== Data structures programs

- Use of array
- Structuring data
- Powerful tools for specialized data

Don't write a big program when a little one will do.

==Column 4== Writing correct programs

- binary search - hard to get right
- program verification, invariant

==Column 5== A small matter of programming

- Use assertion for correctness
- Scaffolding
- Automated testing
- debugging
- Timing

==## Part II ##==Performance

==Column 6== Perspective on Performance

- A case study: Andrew Appel's many-body simulation program
- Work at many level to achieve performance improvement:
* problem definition
* system structure
* algorithms and data structures
* code tuning
* hardware

==Column 7==The back of the envelop

- Calculation by reasonable estimation
- Quick check: Test by dimension
- Rules of thumb: e.g., 1) Rule of 72 (for exponential increase), 2) pi seconds is a nanocentury.
- Performance estimates, and little experiments
- Safety factors: compensate ignorance with extra safe factors
- Little's Law: queue size = consumption rate * average wait time

==Column 8==Algorithm design techniques

- Problem: range of array for max sum
- Solutions:
* cubic
* quadratic
* Divide and conquer (n log(n))
* scanning (linear)

==Column 9==Code tuning

- Prevent premature optimization
- Optimization should be made on the bottle-neck part - profiling the program

==Column 10==Squeezing space

- The key is simplicity
- Example: sparse matrix representation of grid.
- When simplicity is not sufficient, there are skills to better utilize space:
* recompute
* sparse data structure
* data compression
* allocation policies
* garbage collection

==## Part III ##==The Product

==Column 11==Sorting

- Insertion sort
- Quick sort

==Column 12== A sample problem

- Problem: sampling: select m from n integers
* by selection
* by shuffling
- Principles: understand the problem, specify an abstraction, explore design space, implement, retrospect.

==Column 13== Searching

- Problem: store a set of integers (w/o associated data).
- linear structure
- binary search trees: STL, BST, BST*, Bins, Bins*, BitVec
- structures for integers

==Column 14== Heaps

- Heap, Priority Queue, Heap sort
Comment: the material here can be found in any data structure and algorithm textbook, nothing new.

== Column 15== Strings of pearls

- We are surrounded by strings
- Words. 1) Map, Set, 2) Hash (no worst case guarantee, no order information)
- Phrases.
* the longest substring problem - solved by suffix array
- Generating sentences

==Appendix 1== A catalog of algorithms

- Sorting
- Searching
- Other Set algorithms
- Algorithms on Strings
- Vector and Matrix algorithms
- Random objects
- Numerical algorithms

==Appendix 4== Rules for code tuning

- Space-for-time rules
- Time-for-space rules
- Loop rules
- Logic rules
- Procedure rules
- Expression rules

Wednesday, October 1, 2008

C# convert PDF to image format

The solution generally is provided by 3rd party component. In many cases it is not free. E.g., PDFRasterizer.NET component, PDF4NET etc.

Here's one solution: http://www.mobileread.com/forums/showthread.php?t=10137

The GFL SDK/GFLAx (http://www.xnview.com/en/gfl.html) free library component can be used to convert PDF to image format. It works for ASP, VB, C# etc. GhostScript (http://sourceforge.net/projects/ghostscript/) is required for it to work.

Example code in C#:


{
       string file = "D:/test.pdf";
       string image = "D:\\test.png";

       try
       {
           GflAx.GflAxClass g = new GflAx.GflAxClass();
           g.EpsDpi = 150;
           g.Page = 1;
           g.LoadBitmap(file);
           g.SaveFormat = GflAx.AX_SaveFormats.AX_PNG;
           g.SaveBitmap(image);
           MessageBox.Show(this, "PDF to PNG conversion ended");
       }
       catch (Exception ex) {
           MessageBox.Show(this, "GflAx error: " + ex.Message);
       }
}

barcode reader and writer

libdmtx - library of data matrix. Currently hosted at http://www.libdmtx.org/

Thursday, July 10, 2008

SQL statements

- Return primary key of the new inserted entry:

Method 1:
INSERT (..) VALUES (..) INTO tbl ; SELECT @@IDENTITY AS NewID;
Method 2 (preferred over Method 1 in some cases):
INSERT (..) VALUES (..) INTO tbl ; SELECT NEWID = SCOPE_IDENTITY();

An article for more.

- Create a table from another table:

SELECT * FROM tbl_old INTO tbl_new

- Create an empty table from an existing table:

SELECT * INTO tbl_new FROM tbl_old where 1 = 0

- Get column names in a table:

SELECT COLUMN_NAME FROM INFORMATION_SCHEMA.Columns where TABLE_NAME = 'tbl_name'

- Count rows in union statement:

SELECT count(*) FROM (
SELECT field1 FROM table1
UNION
SELECT field2 FROM table2
) as t

- COALESCE - returns first non-null value in list, or null if all values are null

See COALESCE (Transact-SQL).

- Insert from another table in batch mode

INSERT INTO MyTable (FirstCol, SecondCol) SELECT Col1, Col2 FROM MyTable2

Thursday, July 3, 2008

C# simulate mouse and keyboard events

This is achieved by calling windows API functions.
Also see
reference.

using System.Runtime.InteropServices;

public class Form1 : System.Windows.Forms.Form {
  public enum VK : ushort
  {
   SHIFT        = 0x10,
   CONTROL      = 0x11,
   MENU         = 0x12,
   ESCAPE       = 0x1B,
   BACK         = 0x08,
   TAB          = 0x09,
   RETURN       = 0x0D,
   PRIOR        = 0x21,
   NEXT         = 0x22,
   END          = 0x23,
   HOME         = 0x24,
   LEFT         = 0x25,
   UP           = 0x26,
   RIGHT        = 0x27,
   DOWN         = 0x28,
   SELECT       = 0x29,
   PRINT        = 0x2A,
   EXECUTE      = 0x2B,
   SNAPSHOT     = 0x2C,
   INSERT       = 0x2D,
   DELETE       = 0x2E,
   HELP         = 0x2F,
   NUMPAD0      = 0x60,
   NUMPAD1      = 0x61,
   NUMPAD2      = 0x62,
   NUMPAD3      = 0x63,
   NUMPAD4      = 0x64,
   NUMPAD5      = 0x65,
   NUMPAD6      = 0x66,
   NUMPAD7      = 0x67,
   NUMPAD8      = 0x68,
   NUMPAD9      = 0x69,
   MULTIPLY     = 0x6A,
   ADD          = 0x6B,
   SEPARATOR    = 0x6C,
   SUBTRACT     = 0x6D,
   DECIMAL      = 0x6E,
   DIVIDE       = 0x6F,
   F1           = 0x70,
   F2           = 0x71,
   F3           = 0x72,
   F4           = 0x73,
   F5           = 0x74,
   F6           = 0x75,
   F7           = 0x76,
   F8           = 0x77,
   F9           = 0x78,
   F10          = 0x79,
   F11          = 0x7A,
   F12          = 0x7B,
   OEM_1        = 0xBA,   // ',:' for US
   OEM_PLUS     = 0xBB,   // '+' any country
   OEM_COMMA    = 0xBC,   // ',' any country
   OEM_MINUS    = 0xBD,   // '-' any country
   OEM_PERIOD   = 0xBE,   // '.' any country
   OEM_2        = 0xBF,   // '/?' for US
   OEM_3        = 0xC0,   // '`~' for US
   MEDIA_NEXT_TRACK     = 0xB0,
   MEDIA_PREV_TRACK     = 0xB1,
   MEDIA_STOP           = 0xB2,
   MEDIA_PLAY_PAUSE     = 0xB3,
   LWIN       =0x5B,
   RWIN       =0x5C
  }

  #region Dll Imports

  [StructLayout(LayoutKind.Sequential)]
   struct MOUSEINPUT
  {
   public int dx;
   public int dy;
   public uint mouseData;
   public uint dwFlags;
   public uint time;
   public IntPtr dwExtraInfo;
  }

  [StructLayout(LayoutKind.Sequential)]
   struct KEYBDINPUT
  {
   public ushort wVk;
   public ushort wScan;
   public uint dwFlags;
   public uint time;
   public IntPtr dwExtraInfo;
  }

  [StructLayout(LayoutKind.Sequential)]
   struct HARDWAREINPUT
  {
   public uint uMsg;
   public ushort wParamL;
   public ushort wParamH;
  }

  [StructLayout(LayoutKind.Explicit)]
   struct INPUT
  {
   [FieldOffset(0)]
   public int type;
   [FieldOffset(4)] 
   public MOUSEINPUT mi;
   [FieldOffset(4)] 
   public KEYBDINPUT ki;
   [FieldOffset(4)] 
   public HARDWAREINPUT hi;
  }

  [DllImport("user32.dll", SetLastError=true)]
  private static extern uint SendInput(uint nInputs, INPUT[] pInputs, int cbSize);

  const int INPUT_MOUSE          = 0;
  const int INPUT_KEYBOARD       = 1;
  const int INPUT_HARDWARE       = 2;
  const uint KEYEVENTF_EXTENDEDKEY   = 0x0001;
  const uint KEYEVENTF_KEYUP     = 0x0002;
  const uint KEYEVENTF_UNICODE       = 0x0004;
  const uint KEYEVENTF_SCANCODE      = 0x0008;
  const uint XBUTTON1        = 0x0001;
  const uint XBUTTON2        = 0x0002;
  const uint MOUSEEVENTF_MOVE    = 0x0001;
  const uint MOUSEEVENTF_LEFTDOWN    = 0x0002;
  const uint MOUSEEVENTF_LEFTUP      = 0x0004;
  const uint MOUSEEVENTF_RIGHTDOWN   = 0x0008;
  const uint MOUSEEVENTF_RIGHTUP     = 0x0010;
  const uint MOUSEEVENTF_MIDDLEDOWN  = 0x0020;
  const uint MOUSEEVENTF_MIDDLEUP    = 0x0040;
  const uint MOUSEEVENTF_XDOWN       = 0x0080;
  const uint MOUSEEVENTF_XUP     = 0x0100;
  const uint MOUSEEVENTF_WHEEL       = 0x0800;
  const uint MOUSEEVENTF_VIRTUALDESK = 0x4000;
  const uint MOUSEEVENTF_ABSOLUTE    = 0x8000;


  private MOUSEINPUT createMouseInput(int x, int y, uint data, uint t, uint flag) {
   MOUSEINPUT mi = new MOUSEINPUT();
   mi.dx = x;
   mi.dy = y;
   mi.mouseData = data;
   mi.time = t;
   //mi.dwFlags = MOUSEEVENTF_ABSOLUTE| MOUSEEVENTF_MOVE;
   mi.dwFlags = flag;
   return mi;
  }

  private KEYBDINPUT createKeybdInput(short wVK, uint flag) 
  {
   KEYBDINPUT i = new KEYBDINPUT();
   i.wVk = (ushort) wVK;
   i.wScan = 0;
   i.time = 0;
   i.dwExtraInfo = IntPtr.Zero;
   i.dwFlags = flag; 
   return i;
  }

  private short getCVal(char c) {
   if (c >= 'a' && c <= 'z') return c - 'a' + 0x61;
   else if (c >= '0' && c <= '9') return c - '0' + 0x30;
   else if (c == '-') return 0x6D; // Note it's NOT 0x2D as in ASCII code!
   else return 0; // default
  }

  /// 
  /// Each time first move the upper left corner, then move from there.
  /// x, y: pixel value of position.
  /// 

  private void sim_mov(int x, int y) {
   INPUT[] inp = new INPUT[2];
   inp[0].type = INPUT_MOUSE;
   inp[0].mi = createMouseInput(0, 0, 0, 0, MOUSEEVENTF_ABSOLUTE | MOUSEEVENTF_MOVE);
   inp[1].type = INPUT_MOUSE;
   inp[1].mi = createMouseInput(x, y, 0, 0, MOUSEEVENTF_MOVE); 
   SendInput((uint)inp.Length, inp, Marshal.SizeOf(inp[0].GetType()));
  }

  private void sim_click() 
  {
   INPUT[] inp = new INPUT[2];
   inp[0].type = INPUT_MOUSE;
   inp[0].mi = createMouseInput(0, 0, 0, 0, MOUSEEVENTF_LEFTDOWN);
   inp[1].type = INPUT_MOUSE;
   inp[1].mi = createMouseInput(0, 0, 0, 0, MOUSEEVENTF_LEFTUP);
   SendInput((uint)inp.Length, inp, Marshal.SizeOf(inp[0].GetType()));
  }

  private void sim_type(string txt) 
  {
   int i, len;
   char[] c_array;
   short c;
   INPUT[] inp;

   if (txt == null || txt.Length == 0) return;

   c_array = txt.ToCharArray();
   len = c_array.Length;
   inp = new INPUT[2];

   for (i = 0; i < len; i ++) 
   {
    c = getCVal(txt[i]); 
    
    inp[0].type = INPUT_KEYBOARD;
    inp[0].ki = createKeybdInput(c, 0);
    inp[1].type = INPUT_KEYBOARD;
    inp[1].ki = createKeybdInput(c, KEYEVENTF_KEYUP);
    
    SendInput((uint)inp.Length, inp, Marshal.SizeOf(inp[0].GetType()));
   }
  }

  private void sim_actions() {
   sim_mov(x0, y0);
   sim_click();
  }

  public Form1() {
    InitializeComponent();
    //sim_actions();
  }

  [STAThread]
  static void Main() {
    Application.Run(new Form1());
  }
}

C# screen capture

This is achieved by calling windows API functions.
Also see Reference.


using System.Runtime.InteropServices;
using System.Drawing.Imaging;

public class Form1 : System.Windows.Forms.Form {
  #region Dll Imports
    [DllImport("user32.dll")]
    private static extern bool PrintWindow(IntPtr hwnd, IntPtr hdcBlt, uint nFlags);
  #endregion

  private void screen_capture() {
    try {
      Bitmap bm = new Bitmap(this.Width, this.Height);
      Graphics g = Graphics.FromImage(bm);
      IntPtr hdc = g.GetHdc();
      Form1.PrintWindow(this.Handle, hdc, 0);
      //MessageBox.Show("color: " + bm.GetPixel(550, 300));
      g.ReleaseHdc(hdc);
      g.Flush();
      g.Dispose();
      //this.pictureBox1.Image = bm;
      bm.Save("test.bmp");
    } catch (Exception e) {
      MessageBox.Show(this, "error: " + e.Message);
    }
  }

  public Form1() { InitializeComponent(); /* screen_capture(); */  }

  [STAThread]
  static void Main() { Application.Run(new Form1()); }
}