| 1 |
/* |
/* |
| 2 |
* $Id: Hashtable.h,v 1.4 2007-08-18 08:52:18 maya Exp $ |
* $Id: Hashtable.h,v 1.4 2007-08-18 08:52:18 maya Exp $ |
| 3 |
*/ |
*/ |
| 4 |
|
|
| 5 |
#ifndef _YCL_HASHTABLE_H_ |
#ifndef _YCL_HASHTABLE_H_ |
| 6 |
#define _YCL_HASHTABLE_H_ |
#define _YCL_HASHTABLE_H_ |
| 7 |
|
|
| 8 |
#if _MSC_VER >= 1000 |
#if _MSC_VER >= 1000 |
| 9 |
#pragma once |
#pragma once |
| 10 |
#endif // _MSC_VER >= 1000 |
#endif // _MSC_VER >= 1000 |
| 11 |
|
|
| 12 |
#include <YCL/common.h> |
#include <YCL/common.h> |
| 13 |
|
|
| 14 |
#include <YCL/HASHCODE.h> |
#include <YCL/HASHCODE.h> |
| 15 |
#include <YCL/ValueCtrl.h> |
#include <YCL/ValueCtrl.h> |
| 16 |
#include <YCL/Enumeration.h> |
#include <YCL/Enumeration.h> |
| 17 |
#include <YCL/Pointer.h> |
#include <YCL/Pointer.h> |
| 18 |
|
|
| 19 |
namespace yebisuya { |
namespace yebisuya { |
| 20 |
|
|
| 21 |
// ハッシュテーブルを管理するクラス。 |
// ハッシュテーブルを管理するクラス。 |
| 22 |
template<class TYPE_KEY, class TYPE_VALUE, class KEYCTRL = ValueCtrl<TYPE_KEY>, class VALCTRL = ValueCtrl<TYPE_VALUE> > |
template<class TYPE_KEY, class TYPE_VALUE, class KEYCTRL = ValueCtrl<TYPE_KEY>, class VALCTRL = ValueCtrl<TYPE_VALUE> > |
| 23 |
class Hashtable { |
class Hashtable { |
| 24 |
// TYPE_KEY, TYPE_VALUEにとれる型: |
// TYPE_KEY, TYPE_VALUEにとれる型: |
| 25 |
// ・デフォルトコンストラクタを持つ |
// ・デフォルトコンストラクタを持つ |
| 26 |
// ・コピーコンストラクタを持つ |
// ・コピーコンストラクタを持つ |
| 27 |
// ・==演算子を持つ |
// ・==演算子を持つ |
| 28 |
// ・=演算子を持つ(この条件のため参照は指定できない) |
// ・=演算子を持つ(この条件のため参照は指定できない) |
| 29 |
// KEYCTRL、VALCTRLにデフォルトのものを使用する場合は |
// KEYCTRL、VALCTRLにデフォルトのものを使用する場合は |
| 30 |
// ・デフォルトコンストラクタで生成されたインスタンスとNULLを比較すると真になる |
// ・デフォルトコンストラクタで生成されたインスタンスとNULLを比較すると真になる |
| 31 |
// ・NULLインスタンスとNULLを比較すると真になる |
// ・NULLインスタンスとNULLを比較すると真になる |
| 32 |
// ・TYPE_KEYはハッシュ値を生成するhashCodeメソッドを持つ |
// ・TYPE_KEYはハッシュ値を生成するhashCodeメソッドを持つ |
| 33 |
// が条件に加わる。 |
// が条件に加わる。 |
| 34 |
public: |
public: |
| 35 |
typedef Enumeration<TYPE_KEY> KeyEnumeration; |
typedef Enumeration<TYPE_KEY> KeyEnumeration; |
| 36 |
typedef Enumeration<TYPE_VALUE> ElementEnumeration; |
typedef Enumeration<TYPE_VALUE> ElementEnumeration; |
| 37 |
private: |
private: |
| 38 |
// コピーコンストラクタは使用禁止 |
// コピーコンストラクタは使用禁止 |
| 39 |
Hashtable(Hashtable&); |
Hashtable(Hashtable&); |
| 40 |
// 代入演算子は使用禁止 |
// 代入演算子は使用禁止 |
| 41 |
void operator=(Hashtable&); |
void operator=(Hashtable&); |
| 42 |
|
|
| 43 |
// ハッシュテーブルのエントリ。 |
// ハッシュテーブルのエントリ。 |
| 44 |
struct Entry { |
struct Entry { |
| 45 |
TYPE_KEY key; |
TYPE_KEY key; |
| 46 |
TYPE_VALUE value; |
TYPE_VALUE value; |
| 47 |
Entry() { |
Entry() { |
| 48 |
KEYCTRL::initialize(key); |
KEYCTRL::initialize(key); |
| 49 |
VALCTRL::initialize(value); |
VALCTRL::initialize(value); |
| 50 |
} |
} |
| 51 |
}; |
}; |
| 52 |
// ハッシュテーブルのエントリを列挙するためのクラス。 |
// ハッシュテーブルのエントリを列挙するためのクラス。 |
| 53 |
class EnumEntries { |
class EnumEntries { |
| 54 |
private: |
private: |
| 55 |
const Hashtable& table; |
const Hashtable& table; |
| 56 |
mutable int index; |
mutable int index; |
| 57 |
void skip()const { |
void skip()const { |
| 58 |
while (index < table.backetSize && VALCTRL::isEmpty(table.backet[index].value)) |
while (index < table.backetSize && VALCTRL::isEmpty(table.backet[index].value)) |
| 59 |
index++; |
index++; |
| 60 |
} |
} |
| 61 |
public: |
public: |
| 62 |
EnumEntries(const Hashtable& table) |
EnumEntries(const Hashtable& table) |
| 63 |
:table(table), index(0) { |
:table(table), index(0) { |
| 64 |
skip(); |
skip(); |
| 65 |
} |
} |
| 66 |
bool hasMoreEntries()const { |
bool hasMoreEntries()const { |
| 67 |
return index < table.backetSize; |
return index < table.backetSize; |
| 68 |
} |
} |
| 69 |
const Entry& nextEntry()const { |
const Entry& nextEntry()const { |
| 70 |
const Entry& entry = table.backet[index++]; |
const Entry& entry = table.backet[index++]; |
| 71 |
skip(); |
skip(); |
| 72 |
return entry; |
return entry; |
| 73 |
} |
} |
| 74 |
}; |
}; |
| 75 |
friend class EnumEntries; |
friend class EnumEntries; |
| 76 |
// ハッシュテーブルのキーを列挙するためのクラス。 |
// ハッシュテーブルのキーを列挙するためのクラス。 |
| 77 |
class EnumKeys : public KeyEnumeration { |
class EnumKeys : public KeyEnumeration { |
| 78 |
private: |
private: |
| 79 |
EnumEntries entries; |
EnumEntries entries; |
| 80 |
public: |
public: |
| 81 |
EnumKeys(const Hashtable& table) |
EnumKeys(const Hashtable& table) |
| 82 |
:entries(table) { |
:entries(table) { |
| 83 |
} |
} |
| 84 |
virtual bool hasMoreElements()const { |
virtual bool hasMoreElements()const { |
| 85 |
return entries.hasMoreEntries(); |
return entries.hasMoreEntries(); |
| 86 |
} |
} |
| 87 |
virtual TYPE_KEY nextElement()const { |
virtual TYPE_KEY nextElement()const { |
| 88 |
return entries.nextEntry().key; |
return entries.nextEntry().key; |
| 89 |
} |
} |
| 90 |
}; |
}; |
| 91 |
// ハッシュテーブルの値を列挙するためのクラス。 |
// ハッシュテーブルの値を列挙するためのクラス。 |
| 92 |
class EnumValues : public ElementEnumeration { |
class EnumValues : public ElementEnumeration { |
| 93 |
private: |
private: |
| 94 |
EnumEntries entries; |
EnumEntries entries; |
| 95 |
public: |
public: |
| 96 |
EnumValues(const Hashtable& table) |
EnumValues(const Hashtable& table) |
| 97 |
:entries(table) { |
:entries(table) { |
| 98 |
} |
} |
| 99 |
virtual bool hasMoreElements()const { |
virtual bool hasMoreElements()const { |
| 100 |
return entries.hasMoreEntries(); |
return entries.hasMoreEntries(); |
| 101 |
} |
} |
| 102 |
virtual TYPE_VALUE nextElement()const { |
virtual TYPE_VALUE nextElement()const { |
| 103 |
return entries.nextEntry().value; |
return entries.nextEntry().value; |
| 104 |
} |
} |
| 105 |
}; |
}; |
| 106 |
|
|
| 107 |
// エントリの配列。 |
// エントリの配列。 |
| 108 |
Entry* backet; |
Entry* backet; |
| 109 |
// エントリの配列のサイズ |
// エントリの配列のサイズ |
| 110 |
int backetSize; |
int backetSize; |
| 111 |
// 有効なエントリの数 |
// 有効なエントリの数 |
| 112 |
int count; |
int count; |
| 113 |
enum { |
enum { |
| 114 |
// エントリの配列を大きくするときに使用するサイズ |
// エントリの配列を大きくするときに使用するサイズ |
| 115 |
BOUNDARY = 8, |
BOUNDARY = 8, |
| 116 |
}; |
}; |
| 117 |
// keyと等しいキーを持つエントリのインデックスを返す。 |
// keyと等しいキーを持つエントリのインデックスを返す。 |
| 118 |
// 引数: |
// 引数: |
| 119 |
// key 検索するキー |
// key 検索するキー |
| 120 |
// 返値: |
// 返値: |
| 121 |
// keyと等しいキーを持つか、まだ設定されていないエントリのインデックス。 |
// keyと等しいキーを持つか、まだ設定されていないエントリのインデックス。 |
| 122 |
// 全てのエントリが設定済みでkeyと等しいものがなければ-1を返す。 |
// 全てのエントリが設定済みでkeyと等しいものがなければ-1を返す。 |
| 123 |
int find(const TYPE_KEY& key)const { |
int find(const TYPE_KEY& key)const { |
| 124 |
int found = -1; |
int found = -1; |
| 125 |
int h = HASHCODE(key); |
int h = HASHCODE(key); |
| 126 |
for (int i = 0; i < backetSize; i++) { |
for (int i = 0; i < backetSize; i++) { |
| 127 |
int index = ((unsigned) h + i) % backetSize; |
int index = ((unsigned) h + i) % backetSize; |
| 128 |
const TYPE_KEY& bkey = backet[index].key; |
const TYPE_KEY& bkey = backet[index].key; |
| 129 |
if (KEYCTRL::isEmpty(bkey) || bkey == key) { |
if (KEYCTRL::isEmpty(bkey) || bkey == key) { |
| 130 |
found = index; |
found = index; |
| 131 |
break; |
break; |
| 132 |
} |
} |
| 133 |
} |
} |
| 134 |
return found; |
return found; |
| 135 |
} |
} |
| 136 |
// エントリの配列を指定のサイズに変え、もう一度テーブルを作り直す。 |
// エントリの配列を指定のサイズに変え、もう一度テーブルを作り直す。 |
| 137 |
// 引数: |
// 引数: |
| 138 |
// newSize 新しい配列のサイズ。 |
// newSize 新しい配列のサイズ。 |
| 139 |
// 有効なエントリの数よりも少なくしてはいけない。 |
// 有効なエントリの数よりも少なくしてはいけない。 |
| 140 |
void rehash(int newSize) { |
void rehash(int newSize) { |
| 141 |
Entry* oldBacket = backet; |
Entry* oldBacket = backet; |
| 142 |
int oldSize = backetSize; |
int oldSize = backetSize; |
| 143 |
backet = new Entry[newSize]; |
backet = new Entry[newSize]; |
| 144 |
backetSize = newSize; |
backetSize = newSize; |
| 145 |
for (int i = 0; i < oldSize; i++) { |
for (int i = 0; i < oldSize; i++) { |
| 146 |
if (!VALCTRL::isEmpty(oldBacket[i].value)) { |
if (!VALCTRL::isEmpty(oldBacket[i].value)) { |
| 147 |
backet[find(oldBacket[i].key)] = oldBacket[i]; |
backet[find(oldBacket[i].key)] = oldBacket[i]; |
| 148 |
} |
} |
| 149 |
} |
} |
| 150 |
delete[] oldBacket; |
delete[] oldBacket; |
| 151 |
} |
} |
| 152 |
public: |
public: |
| 153 |
// デフォルトコンストラクタ。 |
// デフォルトコンストラクタ。 |
| 154 |
// 空のハッシュテーブルを作る。 |
// 空のハッシュテーブルを作る。 |
| 155 |
Hashtable() |
Hashtable() |
| 156 |
:backet(NULL), backetSize(0), count(0) { |
:backet(NULL), backetSize(0), count(0) { |
| 157 |
} |
} |
| 158 |
// エントリの配列の初期サイズを指定するコンストラクタ。 |
// エントリの配列の初期サイズを指定するコンストラクタ。 |
| 159 |
// 引数: |
// 引数: |
| 160 |
// backetSize エントリの配列の大きさ。 |
// backetSize エントリの配列の大きさ。 |
| 161 |
Hashtable(int backetSize) |
Hashtable(int backetSize) |
| 162 |
:backet(new Entry[backetSize]), backetSize(backetSize), count(0) { |
:backet(new Entry[backetSize]), backetSize(backetSize), count(0) { |
| 163 |
} |
} |
| 164 |
// デストラクタ。 |
// デストラクタ。 |
| 165 |
// エントリの配列を削除する。 |
// エントリの配列を削除する。 |
| 166 |
~Hashtable() { |
~Hashtable() { |
| 167 |
delete[] backet; |
delete[] backet; |
| 168 |
} |
} |
| 169 |
// 指定のキーに対応する値を取得する。 |
// 指定のキーに対応する値を取得する。 |
| 170 |
// 引数: |
// 引数: |
| 171 |
// key 検索するキー |
// key 検索するキー |
| 172 |
// 返値: |
// 返値: |
| 173 |
// キーに対応する値。見つからなければNULLと等しい値を返す。 |
// キーに対応する値。見つからなければNULLと等しい値を返す。 |
| 174 |
TYPE_VALUE get(const TYPE_KEY& key)const { |
TYPE_VALUE get(const TYPE_KEY& key)const { |
| 175 |
TYPE_VALUE value; |
TYPE_VALUE value; |
| 176 |
VALCTRL::initialize(value); |
VALCTRL::initialize(value); |
| 177 |
int index = find(key); |
int index = find(key); |
| 178 |
if (index != -1) |
if (index != -1) |
| 179 |
value = backet[index].value; |
value = backet[index].value; |
| 180 |
return value; |
return value; |
| 181 |
} |
} |
| 182 |
// 指定のキーに対応する値を設定する。 |
// 指定のキーに対応する値を設定する。 |
| 183 |
// 引数: |
// 引数: |
| 184 |
// key 設定するキー |
// key 設定するキー |
| 185 |
// value 設定する値 |
// value 設定する値 |
| 186 |
// 返値: |
// 返値: |
| 187 |
// 前にキーに設定されていた値。未設定だった場合はNULLと等しい値を返す。 |
// 前にキーに設定されていた値。未設定だった場合はNULLと等しい値を返す。 |
| 188 |
TYPE_VALUE put(const TYPE_KEY& key, const TYPE_VALUE& value) { |
TYPE_VALUE put(const TYPE_KEY& key, const TYPE_VALUE& value) { |
| 189 |
int index = find(key); |
int index = find(key); |
| 190 |
if (index == -1) { |
if (index == -1) { |
| 191 |
rehash(backetSize + BOUNDARY); |
rehash(backetSize + BOUNDARY); |
| 192 |
index = find(key); |
index = find(key); |
| 193 |
} |
} |
| 194 |
TYPE_VALUE old = backet[index].value; |
TYPE_VALUE old = backet[index].value; |
| 195 |
if (VALCTRL::isEmpty(old)) { |
if (VALCTRL::isEmpty(old)) { |
| 196 |
count++; |
count++; |
| 197 |
backet[index].key = key; |
backet[index].key = key; |
| 198 |
} |
} |
| 199 |
backet[index].value = value; |
backet[index].value = value; |
| 200 |
return old; |
return old; |
| 201 |
} |
} |
| 202 |
// 指定のキーに対応する値を削除する。 |
// 指定のキーに対応する値を削除する。 |
| 203 |
// 引数: |
// 引数: |
| 204 |
// key 削除するキー |
// key 削除するキー |
| 205 |
// 返値: |
// 返値: |
| 206 |
// キーに設定されていた値。未設定だった場合はNULLと等しい値を返す。 |
// キーに設定されていた値。未設定だった場合はNULLと等しい値を返す。 |
| 207 |
TYPE_VALUE remove(const TYPE_KEY& key) { |
TYPE_VALUE remove(const TYPE_KEY& key) { |
| 208 |
TYPE_VALUE old; |
TYPE_VALUE old; |
| 209 |
VALCTRL::initialize(old); |
VALCTRL::initialize(old); |
| 210 |
int index = find(key); |
int index = find(key); |
| 211 |
if (index != -1) { |
if (index != -1) { |
| 212 |
old = backet[index].value; |
old = backet[index].value; |
| 213 |
if (!VALCTRL::isEmpty(old)) { |
if (!VALCTRL::isEmpty(old)) { |
| 214 |
count--; |
count--; |
| 215 |
VALCTRL::initialize(backet[index].value); |
VALCTRL::initialize(backet[index].value); |
| 216 |
if (backetSize - count > BOUNDARY) |
if (backetSize - count > BOUNDARY) |
| 217 |
rehash(count); |
rehash(count); |
| 218 |
} |
} |
| 219 |
} |
} |
| 220 |
return old; |
return old; |
| 221 |
} |
} |
| 222 |
// キーを列挙するためのインスタンスを生成する。 |
// キーを列挙するためのインスタンスを生成する。 |
| 223 |
// 使用後はdeleteを忘れないように注意。 |
// 使用後はdeleteを忘れないように注意。 |
| 224 |
// 返値: |
// 返値: |
| 225 |
// キーを列挙するためのインスタンス。 |
// キーを列挙するためのインスタンス。 |
| 226 |
Pointer<KeyEnumeration> keys()const { |
Pointer<KeyEnumeration> keys()const { |
| 227 |
return new EnumKeys(*this); |
return new EnumKeys(*this); |
| 228 |
} |
} |
| 229 |
// 値を列挙するためのインスタンスを生成する。 |
// 値を列挙するためのインスタンスを生成する。 |
| 230 |
// 使用後はdeleteを忘れないように注意。 |
// 使用後はdeleteを忘れないように注意。 |
| 231 |
// 返値: |
// 返値: |
| 232 |
// 値を列挙するためのインスタンス。 |
// 値を列挙するためのインスタンス。 |
| 233 |
Pointer<ElementEnumeration> elements()const { |
Pointer<ElementEnumeration> elements()const { |
| 234 |
return new EnumValues(*this); |
return new EnumValues(*this); |
| 235 |
} |
} |
| 236 |
// 有効な値を持つキーの数を取得する。 |
// 有効な値を持つキーの数を取得する。 |
| 237 |
// 返値: |
// 返値: |
| 238 |
// 有効な値を持つキーの数。 |
// 有効な値を持つキーの数。 |
| 239 |
int size()const { |
int size()const { |
| 240 |
return count; |
return count; |
| 241 |
} |
} |
| 242 |
// 指定のキーが有効な値を持っているかどうかを判定する。 |
// 指定のキーが有効な値を持っているかどうかを判定する。 |
| 243 |
// 引数: |
// 引数: |
| 244 |
// 判定するキー。 |
// 判定するキー。 |
| 245 |
// 返値: |
// 返値: |
| 246 |
// 有効な値を持っていれば真。 |
// 有効な値を持っていれば真。 |
| 247 |
bool contains(const TYPE_KEY& key)const { |
bool contains(const TYPE_KEY& key)const { |
| 248 |
int index = find(key); |
int index = find(key); |
| 249 |
return index != -1 && !VALCTRL::isEmpty(backet[index].value); |
return index != -1 && !VALCTRL::isEmpty(backet[index].value); |
| 250 |
} |
} |
| 251 |
// 有効な値を一つも持っていないかどうかを判定する。 |
// 有効な値を一つも持っていないかどうかを判定する。 |
| 252 |
// 返値: |
// 返値: |
| 253 |
// 有効な値を一つも持っていなければ真。 |
// 有効な値を一つも持っていなければ真。 |
| 254 |
bool isEmpty()const { |
bool isEmpty()const { |
| 255 |
return count == 0; |
return count == 0; |
| 256 |
} |
} |
| 257 |
// 有効な値を一つも持っていない状態に戻す。 |
// 有効な値を一つも持っていない状態に戻す。 |
| 258 |
void empty() { |
void empty() { |
| 259 |
delete[] backet; |
delete[] backet; |
| 260 |
backet = NULL; |
backet = NULL; |
| 261 |
backetSize = 0; |
backetSize = 0; |
| 262 |
count = 0; |
count = 0; |
| 263 |
} |
} |
| 264 |
}; |
}; |
| 265 |
|
|
| 266 |
} |
} |
| 267 |
|
|
| 268 |
#endif//_YCL_HASHTABLE_H_ |
#endif//_YCL_HASHTABLE_H_ |
Tera Term
Parent Directory
Revision Log
Patch