## Tuesday, November 13, 2012

### Word Frequency Counter Using Heap

This is an assignment from our Data Structure class. However, the deadline was passed already, and here I post my code and the report. This may be an example code for heap algorithm.

The original problem of the assignment is to count the word in an article to see the frequency of each word. And show out the first k in the rank.

### Algorithm

Heap is used in this program, so that we don’t have to sort the strings by their frequencies before showing the result.
There are two main operations for heap in this program. One is “add_if_exists()”, another is “add()”. “add_if_exists()” checks if the new input word is already in the heap or not. If yes, this function adds one on its frequency and bubble up this node so that the heap tree remain correct; if no, it returns false, and the program will call “add()”. On the other hand, “add()” is the function to add new word in the heap, which is not seem before.
To implement the heap in this program, I built an array of structure nodes. For each node, there is a word (character array) and an integer, which records the frequency of the word.

### Program Structure

Pseudo code as below,
while( read one word, exits if end of file ){
if( input word is empty ) skip
if( input word exists already ){
add input word to the current heap
reheap
}
else{
add input word as a new node in the heap
}
}
while( k times ){
remove the max node from the heap and show it as the result
}

### Analysis

• For adding the new word which is not in the heap yet, we don’t have to reheap, because the new word must come with frequency = 1 which becomes the smallest node in the heap.
• Time Complexity: say n is the amount of words in the text file, in the worst case (all the n words is not the same), time complexity is O(n2). Most of the time spends on searching if the word is already in the heap or not. However, this can be improved be adding “hash table” in the program, which is not done yet my code.
• Space Complexity: space used in this code is fixed. Adjust the size in the head of the code to different usage. Depends on the amount of words in the article, and the longest characters in one word.

### Program Elements

Functions relates to the heap:
• add_if_exist() Search the heap array to see if the new input word is already in the heap or not. If yes, add one on its frequency, then reheap and return TRUE; if no, return FALSE.
• add() Add the new input word at the end of the heap when it is sure that the word is not in the heap yet.
• reheap() Recheck the heap tree. If it’s not correct, then fix it.
• reheap_from()After adding one on the frequency of a curtain node, we bubble up the node to make sure the heap is correct.
• remove_max()To move the root, we exchange the root with the smallest node then reheap the heap tree. Return the original root node.
Functions relates to the heap tree in array:
• int heap_left(int root) {return (root*2+1);}
• int heap_right(int root) {return (root*2+2);}
• int heap_parent(int child) {return (child-1)/2;}

### Result

• Test on Darwin Kernel Version 12.2.0, GCC 4.8.0.

• Testing on school’s Linux machine, FreeBSD 8.3-RELEASE-p3, GCC 4.2.2.
• The test text file contains 33705 words, which is larger than the last one.

### Other

• To make the program run faster, we can add “-O3” as the argument of GCC, which ask the complier to do some optimisations for speed. Some versions of GCC even offer “-Ofast” selection.
• In the future improvement, the searching part, it can be done by using hash table, which tells the location of a word in the heap tree in the constant of time. Just like the “dictionary” in some programming languages, which is not built-in in C.

### Code

```/*
* Program    : Word Frequency Counter
* Author    : Heron Yang @ NCTU
* Class    : Data Structure
* Date        : 2012/11/06
*
* By using the heap tree in array, we can calculate
* the frequency on words in an article in a short
* time.
*/

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>

#define FALSE    0
#define TRUE    1

#define LENGTH    100
#define NODES    1000000

/*
* Structure Declaration
* Word_node structure includes the original word,
* and its frequency in the article so far.
*/
struct Word_node{
char word[LENGTH];
int freq;
}heap[NODES];

int node_ind = 0;

// Character Operation Related Functions
int isDigit(char c);
int isAlpha(char c);
char toLower(char c);

// Self-Completed Function Declarations
void reheap_from(int child);
void reheap(int root);
void swap_node(int a, int b);

// Functions for Heap Operations
int heap_left(int root)        {return (root*2+1);}
int heap_right(int root)    {return (root*2+2);}
int heap_parent(int child)    {return (child-1)/2;}

// I/O Related Functions
void output_result(int k);
void output_debug(int k);
struct Word_node remove_max();

// main
int main(int argc, char **argv){

FILE *fin = freopen(argv[1], "r", stdin);
int k = atoi(argv[2]);

// read the words from file into the heap
char input[LENGTH] = {0};
// if the length is zero, skip it
if( !strlen(input) )    continue;
}

// output the result here
output_result(k);

// output time information
float elapsed = (float) (clock()) / CLOCKS_PER_SEC;
printf("%f sec\n", elapsed);

// end here
fclose(fin);
return 0;
}

/*
* Function : output_result
* Output the whole result here.
* Also, to output the all the same rank nodes, we
* have to check if there still have nodes need to
* be poped out.
*/
void output_result(int k){
int t = 0;
struct Word_node out;
while(k--){
out = remove_max();
t = out.freq;
printf("(%s,%d)\n", out.word, out.freq);
}
out = remove_max();
while(t == out.freq && node_ind){
printf("(%s,%d)\n", out.word, out.freq);
out = remove_max();
}
}

/*
* Function : output_debug
* Output the heap for debug purpose
*/
void output_debug(int k){
int i, t=0;
for(i=0 ; i<k ; i++){
printf("(%s,%d)\n", heap[i].word, heap[i].freq);
t = heap[i].freq;
}
while(t == heap[i].freq && t){
printf("(%s,%d)\n", heap[i].word, heap[i].freq);
i++;
}
}

/*
* Function : swap_node
* Swap two nodes in the heap structure.
*/
void swap_node(int a, int b){
int t;
char t_c[LENGTH];

// swapping frequency
t = heap[a].freq;
heap[a].freq = heap[b].freq;
heap[b].freq = t;

// swapping word
strcpy(t_c, heap[a].word);
strcpy(heap[a].word, heap[b].word);
strcpy(heap[b].word, t_c);
}

/*
* After making sure that this word hasn't appeared,
* add this word into the structure array.
*/
heap[node_ind].freq = 1;
strcpy(heap[node_ind].word, input);
node_ind++;
}

/*
* Search the existing structure array, add one on
* its frequency if the word is already in the array.
*/
int i;
for(i=0 ; i<node_ind ; i++){
if(!strcmp(heap[i].word, input)){
heap[i].freq ++;
reheap_from(i);
return TRUE;
}
}
return FALSE;
}

/*
* Function : reheap_from
* After adding one on frequency on one node, we have
* to bubble up the node to make sure the heap is right.
*/
void reheap_from(int child){
int root = heap_parent(child);
if( heap[root].freq >= heap[child].freq || root <0 )    return;
swap_node(root, child);

reheap_from(root);
}

/*
* Function :
* Most important part of these program, which rebuild
* or check the heap is in the right condition or not.
*/
void reheap(int root){
int child = heap_left(root);
if( child >= node_ind )    return;
if( (heap[child].freq < heap[child+1].freq) &&
(child < (node_ind-1)) )    child++;
if( heap[root].freq >= heap[child].freq )    return;
swap_node(root, child);
reheap(child);
}

/*
* Function : remove_max
* Pop out the max node in the heap.
* Method : Exchange the last one and the root, then
* reheap the tree to make the exchanged root to its
* right position.
*/
struct Word_node remove_max(){
node_ind --;
if(node_ind != 0){
swap_node(0, node_ind);
reheap(0);
}
return heap[node_ind];
}

/*
* Read in one word form the file, and store in the
* char array, input.
*/
char c;
int ind = 0;
while(scanf("%c", &c) != EOF){
if( !isAlpha(c) && !isDigit(c) ){
input[ind] = '\0';
return TRUE;
}
input[ind++] = toLower(c);
}
return FALSE;
}

/*
* Function : isDigit
* Determine whether the character c is a digit.
*/
int isDigit(char c){
if( c>='0' && c<='9')    return TRUE;
return FALSE;
}

/* Function : isAlpha
* Determine whether the character c is a alphabet.
*/
int isAlpha(char c){
if((c>='a' && c<='z')||(c>='A' && c<='Z'))    return TRUE;
return FALSE;
}

/*
* Function : toLower
* Return the lower case of the input character.
* Method : By modifying the 6th bit of the character to zero,
* we obtain the lower case. (0010 0000)2 = (1<<5)
*/
char toLower(char c){
if(!isAlpha(c))    return c;
return (c|(1<<5));
}
```

## Wednesday, October 31, 2012

### Continuation Passing Style(CPS) using Scheme

Resource:
http://mainline.brynmawr.edu/cs245/cps.pdf
http://en.wikipedia.org/wiki/Continuation-passing_style

Definition:
Continuation Passing Style is a formed for expressions such that no function ever returns, instead they pass control onto a continuation.
or,
"A data structure represents what is left to do."

Features:

• return early
• exceptions and failure can be signalled
• pass in a continuation for success
• pass in another continuation for fail
• suspend
Why:
• CPS quickly fills the stack or has to be given hand-coded infrastructure in languages that don't support the automatic merging of unneeded stack frames.

To Complement:
• every function takes an extra argument, its continuation
• every argument in a function call must be either a variable or a lambda expression (not a more complex expression)
Note:
• There's no implicit continuation - every call  is a tail call.
• There's no magic there, every continuation is simply explicitly passed.
• For using CPS without tail call optimisation will cause not only the constructed continuation potentially grow during recursion, but also the call stack.
Another Topic, Call-with-current-continuation:
• Scheme allows the continuation of a computation to be captured by call/cc.
• (call/cc proc), where proc is a one-parameter function.
• (define get-back 'any), usage: (get-back k)
• (exit 0), escaping from deep recursion.
My Review:
Quite hard to read Scheme code especially with lots for function calls and recursion. This might because I am more familiar with basic imperative programming languages.

## Friday, September 28, 2012

### iTerm 2 v.s. Terminal (on Mac)

1. 分割畫面：可以水平和垂直分割出不同的畫面，由於是內健在iTerm 2裡面操作上與快捷鍵的設定普遍順暢合理。
2. 系統叫出iTerm 2的全域快捷鍵：可以設定在系統任何處叫出iTerm 2的快捷鍵，然而，需要先設定iTerm 2為"Open At Login"，這樣它才會在使用者登入後開始等待讀設定好的快捷鍵。
4. 支援全螢幕：Mountain Lion開始，Mac OS X程式有無支援全螢幕模式成為大家在意的事情，或許不能說是非常重要的一件事情，但表示iTerm 2更新和維護的頻率是高的。

## Sunday, August 5, 2012

### Commands of Appengine

dev_appserver.py <folder path>
demo on local machine

appcfg.py update <folder path>

## Saturday, June 16, 2012

[[119853858155674]] [[406381676079369]] [[405569136151638]] [[123046641168163]] [[351541474918594]] [[350116605059320]]
[[330262407053149]] [[119515894855852]] [[248128375300088]] [[251189481647356]] [[252104128229413]] [[404711332904212]]
[[315426835210887]] [[358358740897499]] [[144806638987969]] [[330205803723974]] [[400975169955496]] [[309864779103545]]
[[433440300023950]] [[395893770456168]] [[162290537236794]] [[253404078092844]] [[345436568858428]] [[441776292507972]]
[[453347648010473]] [[473114889368633]] [[310365985721855]] [[221169918003673]] [[294436837320086]] [[244573498991442]]
[[459915707353191]] [[409172655792153]] [[372764052783133]] [[432841633416823]] [[460590967285763]] [[146421248826697]]

 ex. [[395893770456168]]

1. 過程中圖片和粉絲專頁名稱一定要標好，且可以從中讀出影像的位置（幾之幾）
2. 使用Photoimpact分割圖片與創立數十個粉絲專頁，比想像還要費時，往後若要操作可以寫自動化的程式運作，讓全部程序自動化

HSNU ROCKS!!

"我們面對著螢幕，卻背對了幸福"

## Friday, May 4, 2012

### Stanford Karel

Wiki: http://en.wikipedia.org/wiki/Karel_(programming_language)

• 以了解概念為主導，課程非常強調學生寫程式要如何思考、如何有一個正確的習慣
• 它限制了給學生的東西，與一般學校授課的方式不同，過程中由簡入深，把比較深的內容包裝起來不被你看到，讓初學者不會一開始就陷入茫然
• 很有趣！教材都很完整的教學，修完課讓學生自己有能力可以寫很多東西

• 製作GUI
• 自撰教材或是翻譯教材
• 分享給需要的人

## Wednesday, April 25, 2012

### Linux Keyboard Shortcuts

• X Window System
• ctrl + alt + + ：zoom in，即放大螢幕上文字
• ctrl + alt + - ：zoom out，即縮寫螢幕上的文字
• 滑鼠中間鍵：在一般gnome的Linux環境中，滑鼠中間鍵可以把你目前有在任何一處圈選（反白）的文字複製貼上
• Command Line <input>
• Home or ctrl+a：跳至句首
• End or ctrl+e：跳至句尾
• * alt + b：跳到上一個單字首(word, 以空白分開者)
• * alt + f：跳到下一個單字首(word, 以空白分開者)
• tab太重要了！它可以在你沒打完單字的時候自動補上剩餘的字元，若是沒有辦法找到唯一的對應，多按一下tab，會列出所有可能對應的選項
• ctrl + u：刪掉現在這行
• ctrl + k：從當前的位置，往後刪除到行底
• ctrl + w：從當前的位置，往前刪除一個單字
• Command Line <output>
• shift + page up：往上檢視
• shift + page down：往下檢視
• clear or ctrl+l：清空目前頁面
• reset：清空、類似於重新開啟這個terminal。比如你cat一個binary檔案，在你之後輸入command時不斷有字元跑出來煩你時可以用（根據該網頁的講法）
• Command Line <history> 翻閱先前打過的command
• history：查用近期的command紀錄（可以用pipeline配合grep, more等指令使用）
• 上方向鍵 or ctrl + p：顯示上一個執行過的指令（查閱history）
• 下方向鍵 or ctrl + n：顯示下一個執行過的指令（查閱history）
• ctrl + r：透過類似於搜尋的功能，邊打邊搜尋對應history裡的紀錄
• Command Line <其他>
• ctrl + c：強至中止當前的process
• ctrl + z：讓目前的process（前景）到後景運作，透過fg指令可以喚回，ps可以查看背景process有哪些
• ctrl + d：寄送出已經沒有輸入的訊息。可用來寄送EOF訊息給一般process，或是直接按下後便log out當前的terminal
• ctrl + alt + del：當機時候可以使用，至於對應的反應可能因系統而不同，可以/etc/inittab設定
p.s. 加'*'者表示該指令不一定能在圖形化界面的terminal操作，因為該shortcut往往已經被map到系統的其他地方

Reference:

## Monday, April 23, 2012

### Sharing IPMI IP with the host

http://serverfault.com/questions/259792/how-does-ipmi-sideband-share-the-ethernet-port-with-the-host

• Sharing Ethernet means that LAN1 appears to have 2 MAC addresses(the IPMI interface, the standard Broadcom NIC)
• 公用同一條網路線表示LAN1會有兩個對應到的MAC位址（IPMI和原本的網路卡）
• Traffic to the IPMI interface is magically intercepted below the operating system level and never seen by whatever OS is running.
• 原本到 IPMI 介面的流量會跑到作業系統底下，而不論使用什麼作業系統都將無法看到

Downsides for sharing the IP for IPMI and OS host
• It's particularly difficult to partition the IPMI interface onto a separate subnet in a secure manner.
• 很難做到將兩者分開成不同子網路以保證安全
• The latest IPMI cards now support assigning a VLAN to the IPMI NIC, so you can get some semblance of separation - but the underlying OS could always sniff the traffic for that VLAN.
• 最新的IPMI卡可以支持把VLAN轉到IPMI NIC的功能，所以你可以得到一個「看似」兩者區分開來的樣子，但是OS仍然可以監視到該通訊流
• Older BMC controllers don't allow changing the VLAN at all, although tools like ipmitool or ipmicfg will ostensibly let you change it, it just doesn't work.
• 比較舊的BMC控制器不允許你更便VLAN，雖然有像是ipmitool或ipmicfg等工具，但是就是辦不到
• You're centralizing your failure points on the system. Doing configuration on a switch and manage to cut yourself off somehow? And, you've now cut off the primary network connection to your server AND the backup via IPMI. NIC hardware fail? Same problem,
• 你把所有可能失敗的地方都集中在系統，要怎麼設定一個開關，然後要他關掉自己？你關掉最重要的到伺服器的網路連線和透過IPMI備份的機制。至於NIC硬體問題也會遇到一樣的狀況

### Chrome Theme Creator

https://www.mychrometheme.com/t/bt72bhq8ns74oxshp76ztsuie

## Friday, April 20, 2012

### VIM - That's Why Linux!

VIM這文字編輯器在Linux底下與系統間有很完美的結合，讓一切的Programming變得快速又好玩，我想這是我喜愛Linux的原因之一。

## Thursday, April 19, 2012

### Reference in C++

Reference : A simple reference datatype that is less powerful but safer than the pointer type inherited form C. (from Wiki)

Comparing to "Pointers"
1. It's not possible to refer directly to a reference object after it is defined; any occurrence of its name refers directly to the object it references. (cannot be "reseated", which is often done with pointers)
• 在初次定義過後不能再指向其他物件（但pointer常常被用來做這件事情），故命名中會表達所指向的物件為何。
2. References cannot be "null", whereas pointers can. (Note, containers of references are not allowed)
• reference不能存「空」的值，也表示，一個「裝references」的容器是不被允許的。
3. References cannot be uninitialized. Because it is impossible to reinitialize a reference, they must be initialized as soon as they are created.
• 基於reference一定要在初次定義時候初始化（分配指向的物件），所以沒有「重新初始化」或是「消去初始值」類的東西。
1. [運作]不論上述三項目的不同之外，References與Pointer都是用「傳位址」的方法實現。
• 當作函數參數值時，函數改變該參數內容，原本呼叫函數的地方，該參數對應的變數，值也會被更改。
• 非「傳值」的方式，所以沒有傳送太大資料量的問題。
2. [使用]作為函式傳入值使用的時候：
• 呼叫函式的地方值用一般變數方法：int square( x, result ); // int result, int x=3;
• 接傳入值的函數定義處要加"&"：int square( int x, int &result ) {}
• 函式內部使用該傳入值時，用一般變數的方法：result = x*x;

## Wednesday, April 11, 2012

### "unget" Function in C++

unget函式可以把一個已經讀進來的char吐回去，於是是一個簡易判斷使用者輸入為數字或是String等類似問題的解決方法，但是個人感覺這方法並不嚴謹，難以只透過一個char判斷出太多資訊，而且如此的方法比較沒有效率（如果input有數萬個表示要吐數萬次），已經讀進來的資料其實是可以透過程式設計的方法做後續的判斷的。
• 只一個char透漏的資訊並不多
• 沒有效率

## Tuesday, April 10, 2012

### Simple Web Server (nweb.c) Running On Windows

Class Website : http://people.cs.nctu.edu.tw/~cjtsai/courses/ics/index.html
Simple C code (nweb.c) here : http://people.cs.nctu.edu.tw/~cjtsai/courses/ics/homework/nweb.c

2. Create C:\public_html Directory
3. Create index.html and favicon.ico

• 選最上方的"Tools"
• 選"Compiler Options"
• 該下方的輸入方格中輸入" -lws2_32 "
• 按下"Ok"按鍵，完成設定

2. Create C:\public_html Directory

>> cd Desktop

>> nweb.exe

3. Create index.html and favicon.ico

favicon.ico即是網頁載入時上頭的小icon，可以到這個網頁：http://www.favicon.cc/ 畫一個可愛的圖案、下載後放到C:\public_html就好囉！

DONE!!

### Linux 內建 C 函式庫 Manual

Linux中，對於不了解的command可以直接打"man <command>"即可得到該command的使用手冊，而其實對於 C 語言函式也可以，如"man printf"。

\$sudo apt-get install manpages-dev manpages-posix-dev

\$sudo yum install man-pages

Reference:

## Sunday, April 8, 2012

### Lua Programming Language

\$sudo yum install lua

```#!/usr/bin/lua
print ("Hello World!")
```

then,
\$chmod +x helloworld.lua
\$./helloworld

## Saturday, April 7, 2012

### Can't connect to local MySQL server through socket '/var/lib/mysql/mysql.sock'

Can't connect to local MySQL server through socket '/var/lib/mysql/mysql.sock'(2)
即使touch該檔案(sudo touch /var/lib/mysql/mysql.sock)還是會出現：

Can't connect to local MySQL server through socket '/var/lib/mysql/mysql.sock'(111)

sudo /etc/init.d/mysqld start

### DocumentRoot does not exist

1. 安裝policycoreutils-gui：sudo yum install -y policycoreutils-gui
2. 執行system-config-selinux：system-config-selinux
3. 點選左側"Boolean"選單
4. 將"Allow httpd to read home directories"(httpd_enable_homedirs)的選項打勾（立即生效）

## Thursday, March 29, 2012

### Let's Match!開發心得和紀錄

Let’s Match!開發心得和紀錄
Heron Yang @ NCTU.CS
2012.03.28
http://letsmatch.nctucs.net/

2012年寒假，認識一位系上同學，專研於server-side相關事務，擅長Perl語言，於是找他合作；分工上，我負責client-side（那時我也只會HTML/CSS, JavaScript），他負責server-side，從假期最後一週開始，預計一週是足夠的，事實證明的確足夠「完成」，但並沒辦法真的發表。
client-side的資料送到後端，他使用Perl/CGI的方式去讀取，且將配對資料直接以檔案的方式存在系統裡面，對於有心人要去盜取是十分容易，所以這個方法不能被接受；同時，十分明顯地，欲解決此類問題應該使用一個具有安全性的資料庫，如php+mySQL。提出這個方式去解決時，與我合作的同學表示他不會也沒有意願去學，我也不曾接觸過，於是就這樣Let’s Match!被擱置了約一個多月。

• 沒有測試足夠的平台
• 沒有預料到所有可能的使用情況

App運作背後機制：
• 只有把App分享出去，才能提升自己Match的成功率
• 使用者希望跟「那個人」Match，故應該至少分享給一個人，所以此級數 r>=1 必不收斂（每個人都有心上人、網路使用人口不限的情況下）
• 看到頁面Match成功次數，讓使用者躍躍欲試

• 對使用者使用經驗的責任
• 對資料安全的責任
• 對自己作品的要求

• 開發流程完整，釋出前應有少數人的測試階段
• server端的安全問題要了解且下功夫
• 了解server能夠承受的量
• 文字（包括中文與英文）都應該要多與人討論
• 延攬同興趣的人進行分工，目前需要「設計」、「文字」、「宣傳」，可增加一位programmer

• 已經蒐集使用者的建議，可以添加上去
• 增加VOID選項
• 搜尋朋友功能
• server管理、維護和安全問題改進
• 防止惡意使用行為
• 增加完整度、提升使用品質、增加趣味性，方可以延攬更多使用者
• 文字修飾、宣傳

• 此程式對自己的意義和目的？
• 資料安全產生的法律問題我承擔？
• 此程式發展與自己原先計畫的不同，本應該沒有要花這麼多時間相對犧牲掉所謂的「本業」，是否應該停止？

## Saturday, February 18, 2012

### templates（模板）

templates採通用格式的方法，在C++語言中可大量減少撰寫重複的程式碼，分為兩種形式：

• function templates
• class templates

Function Templates

• function templates則用於完全相同而只有資料型態差異的情況下
definition（出現在該function前面）：
• template< typename T >
• template< class ElementType >

```#include <iostream>
using namespace std;

// function template
template< typename T>
void printArray(const T * const array, int size){
for(int i=0 ; i<size ; i++){
cout << array[i] << " ";
}
cout << endl;
}

int main(){

int a[4] = {1,2,4,3};
char b[3] = {'b', 'c', 'a'};
double c[5] = {1.23, 12.3, 0.12, 1.233, 0.11};

printArray(a, 4);
printArray(b, 3);
printArray(c, 5);

return 0;
}```

"The compiler uses its overload resolution capabilities to find a definition of function printArray the best matched the function call."

• 若是自訂的資料型態，要記得有沒有先overload該型態的operators(for example, ==, >=, ...)
• 同一個template definition裡頭names of template parameters不能重複；不同template definition則可以重複
• template的處理在compile time

Class Templates

Stack.h
```#include <iostream>

using namespace std;

template<typename T>
class Stack{
public:
Stack(int = 10); // default constructor
~Stack(){ // destructor
delete [] stackPtr;
}
bool push(const T &);
bool pop(T &);

bool isEmpty() const{
}
bool isFull() const{
}

private:
int size;
int top;
T *stackPtr;
};

template<typename T>
Stack< T >::Stack(int s):
size(s>0 ? s : 10),
top(-1),
stackPtr( new T[size] ){
}

template<typename T>
bool Stack< T >::push(const T &pushValue){
if(!isFull()){
stackPtr[++top] = pushValue;
return true;
}
return false;
}

template<typename T>
bool Stack<T>::pop(T &popValue){
if(!isEmpty()){
popValue = stackPtr[top--];
return true;
}
return false;
}
```

main.cpp
```#include <iostream>
#include "Stack.h"
using namespace std;

int main(){

/* int */
Stack<int> intStack(5);
int intValue = 1;

// push
while(intStack.push(intValue)){
cout << intValue << " ";
intValue += 2;
}
cout << endl;

// pop
while(intStack.pop(intValue)){
cout << intValue << " ";
}
cout << endl;

/* double */
Stack<double> doubleStack(6);
double doubleValue = 1.0;

// push
while(doubleStack.push(doubleValue)){
cout << doubleValue << " ";
doubleValue *= 1.1;
}
cout << endl;

// pop
while(doubleStack.pop(doubleValue)){
cout << doubleValue << " ";
}
cout << endl;

return 0;
}
```

template<typename T, int elements>

Stack<int, 13> helloStack;
T對應到int，elements對應到13

template<typename T = int>

Stack<> scores;

• 不同數量  和
• 資料型態
• 輸入參數
• 傳回值

## Monday, February 13, 2012

### Polymorphism

main.cpp

```#include <iostream>
#include <iomanip>
#include "GodStudent.h"

using namespace std;

int main(){

Student people("People", 60);
Student *ppeople = &people;

GodStudent heron("Heron", 100, 90);
GodStudent *pheron = &heron;

// base-class object
people.print(); // static binding
ppeople->print(); // dynamic binding

// derive-class object
heron.print(); // static binging
pheron->print(); // dynamic binding

//
// pheron = &people; // this can not work
ppeople = &heron;

return 0;
}
```

1. base-class pointer可以指向derive-class object，但derive-class pointer不能指向base-class object。因為derive-class object "is-a" base-class object，所以第一句敘述是對的，C++中會依照宣告的資料型態去操作資料，所以透過base-class pointer指向derive-class object的方法只能使用base-class中有定義的函式，而derive-class中新定義的函式便沒有辦法操控（像是這例子的getBaseScore()/setBaseScore()）
2. object後面加"."讀取函式的方法為static binding，透過pointer/reference的方法為dynamic binding。static binding可以在compile的時候即知道有無錯誤，dynamic binding則要到程式執行時才能知道有沒有問題。

• virtual，在base class中在某函式定義前面加virtual，往後base-class pointer指向derive-class object時，仍可以呼叫到derive-class object的函式，例如print()，他即可呼叫derive-class的print()，得以印出baseScore。撰寫derive-class時，寫覆蓋過base-class中的virtual函式的動作稱為override。
• 含有pure virtual函式的class稱為abstract class（反義為concrete class），只有抽象意義，不能產生instance。例如「二維」是abstract class，底下繼承的「方形」、「圓形」才是concrete class。
• 在直接或間接的derive class中要能生成instance（concrete class），必須完成所有pure virtual函式的implementation

## Sunday, February 12, 2012

### 繼承（Inheritance）

1. 繼承的方式：public, private, protected
2. base classes中的不同類型（public, private ,protected）變數可以被derived classes使用的權限

class Car : public Vehicle{};

base classes中的不同類型（public, private ,protected）變數可以被derived classes使用的權限

1. set的函式中往往會檢查輸入值是否為有效值，或是一些客製化的處理，若是繞過set/get函式去更變變數，可能導致該變數儲存了無效值
2. 若是base classes改變內部的設置（程式碼），直接讀取、使用base classes的public, protected變數的方式，derived classes的程式碼也可能要跟著更變，導致整份程式變得複雜麻煩，而使用set/get的方式可以避免這樣的問題，即是「封裝」的概念

• base classes的程式碼是不需要因為繼承而有任何更改的
• derived classes程式碼中要使用base classes中的變數或函式可以直接使用，但若是該變數或函式已經被另一個相同名稱的變數或函式覆蓋，可以在前面加上"base clesses name::"的方式讀取使用，例如：Vehicle::drive()
• 若是base classes已經有的東西盡量避免重複撰寫，善用base classes提供的函式

Example Code

```#include <string>
using namespace std;

class Student{
public:
Student(const string &, int = 0);

void setName(const string &);
string getName() const;

void setScore(int);
int getScore() const;

void print() const;

private:
string name;
int score;
};```

base class的implementation （Student.cpp）
```#include <iostream>
#include <string>
#include "Student.h"

using namespace std;

Student::Student(const string &_name, int _score){
name = _name;
score = _score;
}

// name, set/get
void Student::setName(const string &_name){
name = _name;
}

string Student::getName() const{
return name;
}

// score, set/get
void Student::setScore(int _score){
score = _score;
}

int Student::getScore() const{
return score;
}

// print
void Student::print() const{
cout << "Name >> " << name << "\tScore >> " << score << endl;
}```

```#include <string>
#include "Student.h"
using namespace std;

class GodStudent : public Student{
public:
GodStudent(const string &, int = 0, int = 90);

void setBaseScore(int);
int getBaseScore() const;

void print() const;
private:
int baseScore;
};
```

derived class的implementation （GodStudent.cpp）
```#include <iostream>
#include "GodStudent.h"

using namespace std;

GodStudent::GodStudent(const string &_name, int _score, int _baseScore)
:Student(_name, _score){
setBaseScore(_baseScore);
}

void GodStudent::setBaseScore(int _baseScore){
baseScore = _baseScore;
}

int GodStudent::getBaseScore() const{
return baseScore;
}

void GodStudent::print() const{
// accessing protected variables
/*
cout << "Protected Variables" << endl;
cout << "Name >> " << name << "\tScore >> " << score;
cout << "\tBaseScore >> " << baseScore << endl;
*/

// accessing private variables
cout << "\nPrivate Variables" << endl;
Student::print();
cout << "BaseScore >> " << baseScore << endl;
}
```

```#include <iostream>
#include <iomanip>
#include "GodStudent.h"

using namespace std;

int main(){
GodStudent heron("Heron", 100, 90);

cout << "getName >> " << heron.getName() << endl;
cout << "getScore >> " << heron.getScore() << endl;
cout << "getBaseScore >> " << heron.getBaseScore() << endl;

heron.setScore(120);
heron.print();

return 0;
}
```

## Monday, January 30, 2012

### Proxy -- Hiding Implementation Details From Interface (C++)

"Separating interface from implementation and hiding implementation details"是我閱讀OOP到現在不斷提到的概念，基於一層層往上架構、每階層對上密封，只提供使用界面(interface)，至於內部如何完成則加以密封，不需要也不該讓使用的人看到。

Write C++ Code in Multi-files提到把C++程式分到不同檔案，來使得implementation和interface分離，然而會發現到在interface中仍然可以看到private variables之類應該密封的程式碼，所以我們透過"Proxy Class"來近一步把該密封的東西分到不同檔案中。

Implementation.h
```class Implementation{
public:
Implementation(int new_value)
:value(new_value){
}

void setValue(int new_value){
value = new_value;
}

int getValue(){
return value;
}

private:
int value;
};
```

Interface.h
```class Implementation;//forward class declaration for Implementation.h

class Interface{
public:
Interface(int);
~Interface();
void setValue(int);
int getValue();
private:
Implementation *ptr;
};
```

```#include "Interface.h"
#include "Implementation.h"

Interface::Interface(int value)
: ptr(new Implementation(value)){
}

Interface::~Interface(){
delete ptr;
}

void Interface::setValue(int value){
ptr->setValue(value);
}

int Interface::getValue(){
ptr->getValue();
}
```

```#include <iostream>
#include "Interface.h"

using namespace std;

int main(){

Interface a(19);

cout << "Value >> " << a.getValue() << endl;

a.setValue(13);

cout << "Value >> " << a.getValue() << endl;

return 0;
}
```

Output:
Value >> 19
Value >> 13

### Static Members in Class

myClass.h
```class MyClass{
public:
//constructor
MyClass();
//destructor
~MyClass();
//get the amount value
static int getAmount();
private:
static int amount;
};
```

myClass.cpp
```#include <iostream>
#include "myClass.h"

using namespace std;

int MyClass::amount = 0;

MyClass::MyClass(){
amount++;
cout << "no." << amount << " object built." << endl;
}

MyClass::~MyClass(){
cout << "no." << amount << " object deleted." << endl;
amount--;
}

int MyClass::getAmount(){
return amount;
}
```

main.cpp
```#include <iostream>
#include "myClass.h"

using namespace std;

void displayAmount();

int main(){

if(1){
MyClass a1;
MyClass a2;
displayAmount();

MyClass b[2];
displayAmount();
}

displayAmount();

return 0;
}

void displayAmount(){
cout << "Amount >> " << MyClass::getAmount() << endl;
}
```

Output
no.1 object built.
no.2 object built.
Amount >> 2
no.3 object built.
no.4 object built.
Amount >> 4
no.4 object deleted.
no.3 object deleted.
no.2 object deleted.
no.1 object deleted.
Amount >> 0