點陣字

　
以前的 DOS，或仿 DOS 環境，可以在 BIOS 的 F000:FA6E 取得
ASCII bitmap，在 WinXP上可以 LoadLibrary("ntdll.dll")，
用裡頭的 ZwOpenSection 與 ZwMapViewOfSection 取得此
section 的映射，但此法在 Vista 下不能用。

DOS 倚天中文下則由 B800:0000 開始取 (Big5, color) pair，
再對到 16 or 24 號字形檔 (.15 or .24x) 取出 bitmap。
Windows 上有許多 true type font，這些向量字不存在 bitmap，
只能用 GetGlyphOutline 或 TextOut 去轉出點陣圖。

現今由於字型檔繁多，較便捷的做法是用 Win32 API 指定字型檔與字樣，
將字畫到 canvas 上，再把座標數出來，譬如：

#include <windows.h>
#include <stdio.h>

//輸出文字 s, 字體=face, 字形大小=size

void show_text (HDC hdc, wchar_t* s, int size=16, wchar_t* face= L"細明體")
{
    int  x,y, len = wcslen(s);  
    HFONT   font    = CreateFont (size,0,0,0,400,0,0,0,0,0,0,0,0,face);
    HGDIOBJ oldFont = SelectObject (hdc, font);
    SetBkColor (hdc,RGB(255,255,255));
    SetTextColor (hdc, 0);                 //黑色
    TextOut (hdc, 0,0, s, len);

    for (y=0; y<size; y++, puts(""))
        for (x=0; x<len*size; x++)
            printf (GetPixel (hdc,x,y)? "  ":"█");
    SelectObject (hdc, oldFont);     
    DeleteObject (font);   
}

int main ()
{
    SetConsoleTitle (L"Conso");
    HDC hdc = GetDC (FindWindow (0, L"Conso"));

    show_text (hdc, L"選擇");

    DeleteDC (hdc);
    return system ("pause");
}

輸出：

█      ████  ████        ██
      ██  █    █  █    █        █      █████████
            ████  ████        █      █    █  █    █
  █        █        █          █████  █████████
    ██    █    █  █    █        █              █
              ███    ███        █        ███████
                                      █              █
      █          █    █            █  █  █████████
  ████    ████████        ██        █      █
      █          █    █        ███            █  █
      █    ██████████  █  █        ███████
      █          █    █            █              █
      ██    ██        ██        █      █████████
  ██    ██                    ███              █
  █          █████████    █                █

底下是另一種 ttf 轉點陣的寫法，需用 Unicode mode 編譯：

//將文字 ch 的點陣圖存入 buf 中, 點陣圖大小記錄於 bytes 中傳回
//字體=face, 字形大小=size, [此函式在 Unicode 模式下測試正常]

int text_bitmap (HDC hdc, UINT ch, char* buf, GLYPHMETRICS& gm,
                int size=16, wchar_t* face= L"細明體")
{
    MAT2    mat     = {{0,1},{0,0},{0,0},{0,1}};    //轉置矩陣
    HFONT   font    = CreateFont (size,0,0,0,400,0,0,0,0,0,0,0,0,face);
    HGDIOBJ oldFont = SelectObject (hdc, font);
    int bytes = GetGlyphOutline (hdc, ch, 1, &gm, 0, 0, &mat);
    if (bytes != GDI_ERROR)
        GetGlyphOutline (hdc, ch, 1, &gm, bytes, buf, &mat);
    SelectObject (hdc, oldFont);     
    DeleteObject (font);   
    return bytes;
}

int main ()
{
    SetConsoleTitle (L"Conso");
    HDC hdc = GetDC (FindWindow (0, L"Conso"));

    GLYPHMETRICS gm;
    char a[512];
    int sz = text_bitmap (hdc, L'選', a, gm);
    int nx = sz/gm.gmBlackBoxY;     //每行占幾Byte, gmBlackBoxX=位元寬度
                                    //亦即 ((gm.gmBlackBoxX+31)>>5)<<2   
    for (int x,j,i=0; i<sz; puts(""))
        for (x=0; x<nx; x++, i++)
            for (j=1<<8; j; j>>=1)
                printf (a[i]&j? "█":"  ");
   
    DeleteDC (hdc);
    return system ("pause");
}

輸出：

█      █████  ████
      ██  █    ██  █    █
            █████  ████
██        █          █
    ██    █    ██  █    █
              ████    ███

      █          ██    █
█████    █████████
      █          ██    █
      █    ███████████
      █          ██    █
      ██    ██          ██
███    ██
██          ██████████

字串處理

//判斷字串是否相等
    bool str_eq (register const char* a, 
                 register const char* b)
    {
        while (*a == *b++) 
            if (!*a++) return true;
        return !(*a-b[-1]);
    }

洗版程式

#include <windows.h>
#include <stdio.h>

int main ()
{
    wchar_t text[] = L"讚";                  //指定文字
    wchar_t face[] = L"細明體";              //指定字體
    int  size = 32;                         //指定字形大小
    int  x,y, len = (sizeof text/sizeof*text)-1;  

    SetConsoleTitle (L"ASCII Art");
    HDC     hdc     = GetDC (FindWindow (0, L"ASCII Art")); 
    HFONT   font    = CreateFont (size,0,0,0,FW_BOLD,0,0,0,0,0,0,0,0,face);
    HGDIOBJ oldFont = SelectObject (hdc, font); 

    SetBkColor (hdc, RGB (255,255,255));
    SetTextColor (hdc, 0);                  //黑色
    TextOut (hdc, 0,0, text, len);

    FILE* f = fopen ("text.txt","wt");      //開檔
    for (y=0; y<size; y++, fputc('\n',f))
        for (x=0; x<len*size; x++)
            fprintf (f, GetPixel (hdc,x,y)? "□":"■");
    fclose (f);

    SelectObject (hdc, oldFont);     
    DeleteObject (font);   
    DeleteDC (hdc);
}

輸出結果:

□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□
□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□
□□□□□□□□■□□□□□□■■■□□□□□□□■■□□□□□□
□□■■■■■■■■□□■■■■■□□□□□■■■■□□□□□□□
□□□□□□□□□□□□■□□■■□□■■■□□□■□□□■□□□
□□□□□□□□□□□□■■■■■■■■■■■■■■■■■■■□□
□□□□□□□□□□□■□□□■■□□□□□□□□■□□□□□□□
□□□□□□□□■■□□□□□■■□□■■□□□□■□□□■□□□
□□■■■■■■■■■■■■■■■■■■■■■■■■■■■■■□□
□□□□□□□□□□□□□□■□□■□□□□□■□□■□□□□□□
□□□□□□□□□□□□□■□□□■□□□□□■□□■□□□□□□
□□□□□□□□■■□□□■□□□■■■■■■□□□■□□□■□□
□□□■■■■■■■■■■■■■■■□□□■■□□□■■■■■■□
□□□□□□□□□□□□■□□□□□□□■□□□□□■■■■■□□
□□□□□□□□□□■■□□■■■■■■■■■■■■■■■□□□□
□□□□□□□□■■□□□□■■□□□□□□□□□□□■■□□□□
□□■■■■■■■■□□□□■■□□□□□□□□□□□■□□□□□
□□□□□□□□□□□□□□■■■■■■■■■■■■■■□□□□□
□□□□□□□□□□□□□□■■□□□□□□□□□□□■□□□□□
□□□□□□□□□□□□□□■■□□□□□□□□□□□■□□□□□
□□□■□□□□□■□□□□■■□□□□□□□□□□□■□□□□□
□□□■■■■■■■■□□□■■■■■■■■■■■■■■□□□□□
□□□■□□□□■■□□□□■■□□□□□□□□□□□■□□□□□
□□□■□□□□■■□□□□■■□□□□□□□□□□□■□□□□□
□□□■□□□□■■□□□□■■■■■■■■■■■■■■□□□□□
□□□■□□□□■■□□□□■■□□□□□□□□□□□■□□□□□
□□□■□□□□■■□□□□■□□□■□□□□■□□□□□□□□□
□□□■□□□□■■□□□□□□□■■■□□□□■■■□□□□□□
□□□■■■■■■■□□□□□■■□□□□□□□□□■■■□□□□
□□□■□□□□■■□□□■■□□□□□□□□□□□□□■■■□□
□□□■□□□□□□□■■□□□□□□□□□□□□□□□□□■□□
□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□

二元樹

　
用 C 語言的 struct 建立二元樹，一般作法是用兩個
link list node 不斷去連結子樹。 用 array 建也是可行的，
特別是超大型、且要求高速存取的二元樹，
一般會用 hash 來分配節點。

底下是簡單範例，使用 C 建立一個 binary tree 形式的
container，並附上相關操作。

//--------------- BTree definition --------------------

typedef struct Node
{
    void *data;                     //資料項
    Node *L, *R;                    //指向左右子樹
} 
Node;
                                    //建樹            
void add (Node** p, void* data, 
          int (*comp)(void*,void*), int size)    
{
    void* obj;

    if (!*p) {
        obj = malloc (size);        //建立存放物件的空間
        memcpy (obj, data, size);
        *p = (Node*) malloc (sizeof(Node));
        (*p)->data = obj;
        (*p)->L = (*p)->R = 0;
    }
    else if (comp((*p)->data, data)) 
        add (&(*p)->L, data, comp, size);    //建左子樹  
    else 
        add (&(*p)->R, data, comp, size);    //建右子樹
}

void release (Node* p)              //砍樹
{
    if (!p) return;
    release (p->L);
    release (p->R);
    free (p->data);
    free (p); p = 0;
}


typedef enum {PRE, IN, POST} Order;    //指定節點拜訪順序
void show (Node* p, Order o, void (*print)(void*))  //秀樹
{
    if (!p) return;
    if (PRE == o) print (p->data);  show (p->L, o, print);
    if (IN  == o) print (p->data);  show (p->R, o, print);
    if (POST== o) print (p->data);    
}


//---------------------- Instance ------------------------

typedef struct { char* name; int IQ; } Grade;

void print_int(void* i)          { printf(" %d", *(int*)i);     }
int  comp_int (void* a, void* b) { return *(int*)a > *(int*)b;  }
void print_ch (void* i)          { printf("%c", *(char*)i);     }
int  comp_ch  (void* a, void* b) { return *(char*)a > *(char*)b;}
void print_iq (void* i)          { printf(" %s", ((Grade*)i)->name); }
int  comp_iq  (void* a, void* b) { return ((Grade*)a)->IQ > ((Grade*)b)->IQ;}

int main (void)   
{   
    int   i, j;
    char  exp[] = "hello word";
    Grade grade[] = 
    {
        "羅開",  120,
        "木蘭花",130,
        "高達",  113,
        "白素",  145,
        "衛斯理",115, 
    };
    Node* root = 0;
    srand (time (0));

    //TEST1
    for (i=0; i<10; i++) {        
        j = rand()%100;
        add (&root, &j, comp_int, sizeof(int));        
    }
    show (root, IN, print_int);
    release (root);
    puts("\n");
    root=0;

    //TEST2
    for (i=0; i<sizeof exp; i++)         
        add (&root, exp+i, comp_ch, sizeof(char));            
    show (root, IN, print_ch);
    release (root);
    puts("\n");
    root=0;

    //TEST3
    for (i=0; i<5; i++)         
        add (&root, grade+i, comp_iq, sizeof(Grade));            
    show (root, IN, print_iq);
    release (root);

    getch();
    return 0;
}

用 Haskell 寫，流程架構更為清晰：

data Tree  a = Leaf | Node(a, Tree a, Tree a)
add n Nil = Node n Nil Nil
add n p @ (Node v L R)
        | n < v = Node x (add n L) R
        | n > v = Node x L (add n R)
        | otherwise = p
preodr  Leaf=[] preodr (Node x,L,R) = [x] ++ preodr L ++ preodr R
postodr Leaf=[] postodr(Node x,L,R) = postodr L ++ postodr R ++ [x]
inodr   Leaf=[] inodr  (Node x,L,R) = inodr L ++ [x] ++ inodr R 

邊緣偵測

用平面方程去逼近 3x3 影像區塊時，可假設

      f(x,y) = ax + by + c

當中的 (a,b) 表示此區塊的 gradient (可摹想成傾斜向量)
代入 x,y = [-1,0,1] 可得出此區域的代數描述:

     ┌ -a-b+c  -a+c  -a+b+c ┐
     │   -b+c     c     b+c │
     └  a-b+c   a+c   a+b+c ┘

想偵測區塊中一條水平的線，可使用如下的 mask:

     ┌  0   0   0 ┐     ┌  1   1   1 ┐
     │  1   1   1 │ 或  │  0   0   0 │
     └ -1  -1  -1 ┘     └ -1  -1  -1 ┘

後者較佳，因為直行數值為單調增(減)，有助於設計上的最佳化。
再將 mask 改成加權形式，用以增強邊緣點，寫成：

     ┌  β  α  β ┐     ┌  β  0  -β ┐
     │   0   0  0  │ 與  │  α  0  -α │
     └ -β -α -β ┘     └  β  0  -β ┘

將 mask 和區域的代數描述 做 convolution，分別得到一階導數

      2b(α+2β)   與   2a(α+2β)

把他們分別叫做 Gx, Gy，由於此區域之 gradient 量值為

      √(Gx*Gx + Gy*Gy) = 2(α+2β) * √(a*a+b*b)

當 2(α+2β)=1 時，gradient 才符合標準定義 √(a*a+b*b)
於是求解兩根，得 (α,β) = (1/4, 1/8) = ....
將兩根代回 mask 並乘上 8 轉成整數，便得出 Sobel kernel:
  
     ┌  1   2   1 ┐     ┌  1   0  -1 ┐
     │  0   0   0 │ 與  │  2   0  -2 │
     └ -1  -2  -1 ┘     └  1   0  -1 ┘

這程式分別輸出 horizontal 與 vertical mask 運算的結果。

一般對影像邊緣有 zero padding 與 wrapping 與 omit 3 種料理法，
此處採用省略法。無論用的是何種方法，實際上只能處理中央的
(W-2)*(H-2) 區塊。

int sobelH [3*3] = {-1,-2,-1, 0,0,0, 1,2,1};   //平的
int sobelV [3*3] = {-1,0,1, -2,0,2, -1,0,1};   //直的

template <typename T>      
void edge (T* in, T* out, int w, int h, int* m)    //m = kernel
{
    int c;                  //c = color
    out += (w+1);
    in  += (w+1);
    T* end = out+ (w-2)*h-2;            

    while (out < end) {
        c  = m[0]*in[-w-1]; c += m[1]*in[-w]; c += m[2]*in[-w+1];
        c += m[3]*in[  -1]; c += m[4]*in[ 0]; c += m[5]*in[   1];
        c += m[6]*in[ w-1]; c += m[7]*in[ w]; c += m[8]*in[ w+1];
        if (c < 0)   c = -c; //c/=8;
        if (c > 255) c = 255;
        *out++ = c;
        in++;
    }
}

排序

　
Quick Sort：

template <class T> struct Qsort
{
    T *a, t;
    void swap (int i, int j) {t=a[i]; a[i]=a[j]; a[j]=t;}
    void operator = (T* v)   {a=v;}

    void sort (int L, int R)        //M=midden, L=left, R=right
    {
        if (L >= R) return;               
        int i, M=L;
        swap (L, (L+R)/2)                        
        for (i=L+1; i<=R; ++i)
            if (a[i] < a[L]) 
                swap (++M, i);  
        swap (L, M);        
        sort (L, M-1); 
        sort (M+1, R);
    }
};

int main ()
{
    int i, a[] = {26, 8, 42, 3, 81, 14, 60, 16, 50, 18};
    int n = sizeof a/ sizeof*a - 1;
    Qsort<int> Q; 
    Q = a;
    Q.sort (0, n);
    for (i=0; i<=n; i++) 
        cout <<" " << a[i];
}

巨集

取十進位數的每位數字：

#define DEC(x,n) ((x/(int)1E##n)%10)

int a = 1234;
printf ("%i, %i, %i, %i\n", 
    DEC(a,0), DEC(a,1), DEC(a,2), DEC(a,3));