#if ! defined(_DICT_H_)				// 避免重複 include
#define _DICT_H_

template <class A, class B>			// 一對東西
class pair {
public:
    A first;
    B second;
};

template <class K, class V>			// 字典樣版
class dictionary {
public:
    dictionary(int n);
    ~dictionary();
    // 應該要有 copy constructor 和 operator =

    void insert(K key, V val);			// 新增
    void remove(K key);				// 刪除
    V lookup(K key) const;			// 查詢
    int size() const { return n_elem; }		// 目前字典中有多少個元素?

    typedef pair<K, V> entry_type;
    typedef entry_type * iterator;
    iterator begin() const { return data; }
    iterator end() const { return data + n_elem; }

private:
    int capacity;				// 最大容量
    int n_elem;					// 目前字典中有多少個元素
    entry_type * data;				// 真正的資料
};

// 名稱: dictionary.cc
// 作者: 洪朝貴 http://www.cyut.edu.tw/~ckhung/
// 功能: 字典樣版. 以無序陣列 (unsorted array) 來實作字典.
//	 旨在提供語法範例; 設計有許多方面待改善: 功能貧乏,
//	 錯誤狀況檢查不足 ... 實際應用請用 STL 的 map.

#include <assert.h>

template <class K, class V>
dictionary<K,V>::dictionary(int n) :
    capacity(n),
    n_elem(0),
    data(new dictionary<K,V>::entry_type[n])
{
}

template <class K, class V>
dictionary<K,V>::~dictionary()
{
    delete [] data;
}

template <class K, class V>
void dictionary<K,V>::insert(K key, V val)
{
    data[n_elem].first = key;
    data[n_elem].second = val;
    ++n_elem;
}

template <class K, class V>
void dictionary<K,V>::remove(K key)
{
    int i;

    for (i=0; data[i].first != key && i<n_elem; ++i);
    assert(i < n_elem);
    --n_elem;
    data[i] = data[n_elem];
}

template <class K, class V>
V dictionary<K,V>::lookup(K key) const
{
    int i;

    for (i=0; data[i].first != key && i<n_elem; ++i);
    assert(i < n_elem);
    return data[i].second;
}

#endif

#if defined(TEST)

// #include "stack.h"
#include <iostream.h>

int main(int argc, char *argv[])
{
    dictionary<const char *, int> days_in_month(12);

    days_in_month.insert("jan", 31);
    days_in_month.insert("feb", 28);
    days_in_month.insert("mar", 31);
    cout << "jan: " << days_in_month.lookup("jan") << endl << endl;

    cout << "There are " << days_in_month.size() << " elements" << endl;
    dictionary<const char *, int >::iterator p;
    for (p=days_in_month.begin(); p!=days_in_month.end(); ++p)
	cout << (*p).first << ": " << (*p).second << endl;

    return 0;
}

#endif