1 // =======================================
2 // Unit : map template (KYMapObjs.h)
3 // Version: 3.0.0.0 (build 2011.03.08)
4 // Author : Kyee Ye
5 // Email : kyee_ye(at)126.com
6 // Copyright (C) Kyee workroom
7 // =======================================
8
9 #ifndef _KYMapObjs_H_
10 #define _KYMapObjs_H_
11
12 #include "KYAVLTree.h"
13 #include "KYAVLTreeEx.h"
14
15 // KYLib 2.0 開始使用 KYLib 命名空間
16 namespace KYLib
17 {
18
19 // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
20
21 /* TKYMapIntKey - 整型鍵值 map 類模板 */
22
23 template <class T>
24 class TKYMapIntKey
25 {
26 public:
27 // 構造函數
28 // 1. ANeedFree 鍵值是否需要釋放, 若為 false 則不釋放
29 // 2. ACanLock 是否內置鎖, 為了多線程存取安全, 也可以外部使用鎖控制
30 TKYMapIntKey(bool ANeedFree = false, bool ACanLock = false)
31 {
32 // 創建 AVL 樹
33 FTree = new TKYAVLTree(ACanLock, false);
34
35 // 判斷是否需要釋放
36 if (ANeedFree)
37 {
38 FTree->OnDeletion.Object = this;
39 FTree->OnDeletion.Method = (TKYAVLTree::TDoDeletion)
40 &TKYMapIntKey<T>::DoDeletion;
41 }
42 }
43
44 // 析構函數
45 ~TKYMapIntKey() { FreeAndNil(FTree); }
46
47 // 屬性
48 void* Data() const { return FTree->Data(); } // default: NULL
49 long Count() const { return FTree->Count(); } // default: 0
50 long MaxCount() const { return FTree->MaxCount(); } // default: 0
51 bool CanDuplicate() const { return FTree->CanDuplicate(); } // default: false
52
53 // 設置屬性
54 void SetData(void* AData) { FTree->SetData(AData); }
55 void SetMaxCount(long AMaxCount)
56 { FTree->SetMaxCount(AMaxCount); }
57 void SetCanDuplicate(bool ACanDuplicate)
58 { FTree->SetCanDuplicate(ACanDuplicate); }
59
60 // 鍵值項結點的取值和設置值, 注: 不檢查 ANode 是否合法
61 long Key(void* ANode) const
62 { return (long)((TKYAVLTree::TNode*)ANode)->Item; }
63 T* Value(void* ANode) const
64 { return (T*)((TKYAVLTree::TNode*)ANode)->Data; }
65 void SetValue(void* ANode, T* AValue)
66 { ((TKYAVLTree::TNode*)ANode)->Data = (void*)AValue; }
67
68 // 判斷鍵值項結點是否存在
69 bool Existed(void* ANode) const
70 { return FTree->Existed((TKYAVLTree::TNode*)ANode); }
71
72 // 判斷鍵值是否存在
73 bool Existed(long AKey) const
74 { return FTree->Existed((void*)AKey, NULL); }
75
76 // 查找鍵值項, 若返回值為 NULL 則未找到鍵值, 否則返回找到的鍵值項結點
77 void* Find(long AKey) const
78 { return (void*)FTree->Search((void*)AKey, NULL); }
79
80 // 添加鍵值項, 若返回值為 NULL 則加入失敗, 否則返回加入的鍵值項結點
81 void* Add(long AKey, T* AValue)
82 { return (void*)FTree->Add((void*)AKey, (void*)AValue); }
83
84 // 刪除鍵值項
85 bool Delete(long AKey) { return FTree->Delete((void*)AKey, NULL); }
86
87 // 刪除鍵值項結點
88 bool Remove(void* ANode) { return FTree->Remove((TKYAVLTree::TNode*)ANode); }
89
90 // 清除所有鍵值項結點
91 void Clear() { FTree->Clear(); }
92
93 // 取第一個鍵值項結點
94 void* First() const { return (void*)FTree->Next(NULL); }
95
96 // 取最后一個鍵值項結點
97 void* Last() const { return (void*)FTree->Prior(NULL); }
98
99 // 取下一鍵值項結點, 若ANode == NULL, 則取第一個鍵值項結點
100 void* Next(void* ANode) const
101 { return (void*)FTree->Next((TKYAVLTree::TNode*)ANode); }
102
103 // 取上一鍵值項結點, 若ANode == NULL, 則取最后一個鍵值項結點
104 void* Prior(void* ANode) const
105 { return (void*)FTree->Prior((TKYAVLTree::TNode*)ANode); }
106
107 private:
108 void DoDeletion(void* Sender, TKYAVLTree::TNode* ANode);
109
110 private:
111 TKYAVLTree* FTree;
112 };
113
114 // FTree 的 OnDeletion 事件方法
115 template <class T>
116 void TKYMapIntKey<T>::DoDeletion(void* Sender, TKYAVLTree::TNode* ANode)
117 {
118 delete (T*)ANode->Data;
119 }
120
121 // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
122
123 /* TKYMapStrKey - 字符串鍵值 map 類模板 */
124
125 template <class T>
126 class TKYMapStrKey
127 {
128 public:
129 // 構造函數
130 // 1. ACaseSensitive 鍵值是否區分大小寫, 若為 false 則不區分大小寫
131 // 2. ANeedFree 鍵值是否需要釋放, 若為 false 則不釋放
132 // 3. ACanLock 是否內置鎖, 為了多線程存取安全, 也可以外部使用鎖控制
133 TKYMapStrKey(bool ACaseSensitive = false, bool ANeedFree = false,
134 bool ACanLock = false)
135 {
136 // 初始化
137 FNeedFree = ANeedFree;
138 FCaseSensitive = ACaseSensitive;
139
140 // 創建 AVL 樹
141 FTree = new TKYAVLTree(ACanLock, false);
142
143 // 設置 FTree 的事件方法
144 FTree->OnCompare.Object = this;
145 FTree->OnCompare.Method = (TKYAVLTree::TDoCompare)
146 &TKYMapStrKey<T>::DoCompare;
147 FTree->OnDeletion.Object = this;
148 FTree->OnDeletion.Method = (TKYAVLTree::TDoDeletion)
149 &TKYMapStrKey<T>::DoDeletion;
150 }
151
152 // 析構函數
153 ~TKYMapStrKey() { FreeAndNil(FTree); }
154
155 // 屬性
156 void* Data() const { return FTree->Data(); } // default: NULL
157 long Count() const { return FTree->Count(); } // default: 0
158 long MaxCount() const { return FTree->MaxCount(); } // default: 0
159 bool CanDuplicate() const { return FTree->CanDuplicate(); } // default: false
160 bool CaseSensitive() const{ return FCaseSensitive; } // default: false
161
162 // 設置屬性
163 void SetData(void* AData) { FTree->SetData(AData); }
164 void SetMaxCount(long AMaxCount)
165 { FTree->SetMaxCount(AMaxCount); }
166 void SetCanDuplicate(bool ACanDuplicate)
167 { FTree->SetCanDuplicate(ACanDuplicate); }
168
169 // 鍵值項結點的取值和設置值, 注: 不檢查 ANode 是否合法
170 KYString Key(void* ANode) const
171 { return *(KYString*)((TKYAVLTree::TNode*)ANode)->Item; }
172 T* Value(void* ANode) const
173 { return (T*)((TKYAVLTree::TNode*)ANode)->Data; }
174 void SetValue(void* ANode, T* AValue)
175 { ((TKYAVLTree::TNode*)ANode)->Data = (void*)AValue; }
176
177 // 判斷鍵值項結點是否存在
178 bool Existed(void* ANode) const
179 { return FTree->Existed((TKYAVLTree::TNode*)ANode); }
180
181 // 判斷鍵值是否存在
182 bool Existed(const KYString& AKey) const
183 { return FTree->Existed((void*)&AKey, NULL); }
184
185 // 查找鍵值項, 若返回值為 NULL 則未找到鍵值, 否則返回找到的鍵值項結點
186 void* Find(const KYString& AKey) const
187 { return (void*)FTree->Search((void*)&AKey, NULL); }
188
189 // 添加鍵值項, 若返回值為 NULL 則加入失敗, 否則返回加入的鍵值項結點
190 void* Add(const KYString& AKey, T* AValue);
191
192 // 刪除鍵值項
193 bool Delete(const KYString& AKey)
194 { return FTree->Delete((void*)&AKey, NULL); }
195
196 // 刪除鍵值項結點
197 bool Remove(void* ANode) { return FTree->Remove((TKYAVLTree::TNode*)ANode); }
198
199 // 清除所有鍵值項結點
200 void Clear() { FTree->Clear(); }
201
202 // 取第一個鍵值項結點
203 void* First() const { return (void*)FTree->Next(NULL); }
204
205 // 取最后一個鍵值項結點
206 void* Last() const { return (void*)FTree->Prior(NULL); }
207
208 // 取下一鍵值項結點, 若ANode == NULL, 則取第一個鍵值項結點
209 void* Next(void* ANode) const
210 { return (void*)FTree->Next((TKYAVLTree::TNode*)ANode); }
211
212 // 取上一鍵值項結點, 若ANode == NULL, 則取最后一個鍵值項結點
213 void* Prior(void* ANode) const
214 { return (void*)FTree->Prior((TKYAVLTree::TNode*)ANode); }
215
216 private:
217 void DoCompare(const TKYAVLTree::TNode* ANode1,
218 const TKYAVLTree::TNode* ANode2, long& ACompare);
219 void DoDeletion(void* Sender, TKYAVLTree::TNode* ANode);
220
221 private:
222 TKYAVLTree* FTree;
223 bool FNeedFree;
224 bool FCaseSensitive;
225 };
226
227 // FTree 的 OnCompare 事件方法
228 template <class T>
229 void TKYMapStrKey<T>::DoCompare(const TKYAVLTree::TNode* ANode1,
230 const TKYAVLTree::TNode* ANode2, long& ACompare)
231 {
232 ACompare = CompareStr(*(KYString*)ANode1->Item,
233 *(KYString*)ANode2->Item, FCaseSensitive);
234 }
235
236 // FTree 的 OnDeletion 事件方法
237 template <class T>
238 void TKYMapStrKey<T>::DoDeletion(void* Sender, TKYAVLTree::TNode* ANode)
239 {
240 // 釋放鍵值
241 delete (KYString*)ANode->Item;
242
243 // 判斷是否需要釋放
244 if (FNeedFree)
245 delete (T*)ANode->Data;
246 }
247
248 // 添加鍵值項, 若返回值為 NULL 則加入失敗, 否則返回加入的鍵值項結點
249 template <class T>
250 void* TKYMapStrKey<T>::Add(const KYString& AKey, T* AValue)
251 {
252 // 加入
253 KYString* pKey = new KYString(AKey);
254 TKYAVLTree::TNode* result = FTree->Add((void*)pKey, (void*)AValue);
255
256 // 若加入失敗則釋放
257 if (result == NULL)
258 delete pKey;
259
260 // 返回結果
261 return (void*)result;
262 }
263
264 // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
265
266 /* TKYMapIntKeyEx - 整型鍵值 map 類模板 */
267
268 template <class T>
269 class TKYMapIntKeyEx
270 {
271 public:
272 // 構造函數
273 // 1. ANeedFree 鍵值是否需要釋放, 若為 false 則不釋放
274 // 2. ACanLock 是否內置鎖, 為了多線程存取安全, 也可以外部使用鎖控制
275 TKYMapIntKeyEx(bool ANeedFree = false, bool ACanLock = false)
276 {
277 // 創建 AVL 樹
278 FTree = new TKYAVLTreeEx(ACanLock, false);
279
280 // 判斷是否需要釋放
281 if (ANeedFree)
282 {
283 FTree->OnDeletion.Object = this;
284 FTree->OnDeletion.Method = (TKYAVLTreeEx::TDoDeletion)
285 &TKYMapIntKeyEx<T>::DoDeletion;
286 }
287 }
288
289 // 析構函數
290 ~TKYMapIntKeyEx() { FreeAndNil(FTree); }
291
292 // 屬性
293 void* Data() const { return FTree->Data(); } // default: NULL
294 long Count() const { return FTree->Count(); } // default: 0
295 long MaxCount() const { return FTree->MaxCount(); } // default: 0
296 bool CanDuplicate() const { return FTree->CanDuplicate(); } // default: false
297
298 // 設置屬性
299 void SetData(void* AData) { FTree->SetData(AData); }
300 void SetMaxCount(long AMaxCount)
301 { FTree->SetMaxCount(AMaxCount); }
302 void SetCanDuplicate(bool ACanDuplicate)
303 { FTree->SetCanDuplicate(ACanDuplicate); }
304
305 // 鍵值項結點的取值和設置值, 注: 不檢查 ANode 是否合法
306 long Key(void* ANode) const
307 { return (long)((TKYAVLTreeEx::TNode*)ANode)->Item; }
308 T* Value(void* ANode) const
309 { return (T*)((TKYAVLTreeEx::TNode*)ANode)->Data; }
310 void SetValue(void* ANode, T* AValue)
311 { ((TKYAVLTreeEx::TNode*)ANode)->Data = (void*)AValue; }
312
313 // 根據索引讀取鍵值項結點, AIndex 取值范圍: [0..Count()-1], 可以快速定位指定索引結點
314 void* Node(long AIndex) const
315 { return (void*)FTree->Node(AIndex); }
316
317 // 取鍵值項結點所在的索引, 若不存在則返回 -1
318 long IndexOf(void* ANode) const
319 { return FTree->IndexOf((TKYAVLTreeEx::TNode*)ANode); }
320
321 // 取鍵值所在的索引, 若不存在則返回 -1
322 long IndexOf(long AKey) const
323 { return FTree->IndexOf((void*)AKey, NULL); }
324
325 // 判斷鍵值項結點是否存在
326 bool Existed(void* ANode) const
327 { return FTree->Existed((TKYAVLTreeEx::TNode*)ANode); }
328
329 // 判斷鍵值是否存在
330 bool Existed(long AKey) const
331 { return FTree->Existed((void*)AKey, NULL); }
332
333 // 查找鍵值項, 若返回值為 NULL 則未找到鍵值, 否則返回找到的鍵值項結點
334 void* Find(long AKey) const
335 { return (void*)FTree->Search((void*)AKey, NULL); }
336
337 // 添加鍵值項, 若返回值為 NULL 則加入失敗, 否則返回加入的鍵值項結點
338 void* Add(long AKey, T* AValue)
339 { return (void*)FTree->Add((void*)AKey, (void*)AValue); }
340
341 // 刪除鍵值項
342 bool Delete(long AKey) { return FTree->Delete((void*)AKey, NULL); }
343
344 // 刪除鍵值項結點
345 bool Remove(void* ANode) { return FTree->Remove((TKYAVLTreeEx::TNode*)ANode); }
346
347 // 清除所有鍵值項結點
348 void Clear() { FTree->Clear(); }
349
350 // 取第一個鍵值項結點
351 void* First() const { return (void*)FTree->Next(NULL); }
352
353 // 取最后一個鍵值項結點
354 void* Last() const { return (void*)FTree->Prior(NULL); }
355
356 // 取下一鍵值項結點, 若ANode == NULL, 則取第一個鍵值項結點
357 void* Next(void* ANode) const
358 { return (void*)FTree->Next((TKYAVLTreeEx::TNode*)ANode); }
359
360 // 取上一鍵值項結點, 若ANode == NULL, 則取最后一個鍵值項結點
361 void* Prior(void* ANode) const
362 { return (void*)FTree->Prior((TKYAVLTreeEx::TNode*)ANode); }
363
364 private:
365 void DoDeletion(void* Sender, TKYAVLTreeEx::TNode* ANode);
366
367 private:
368 TKYAVLTreeEx* FTree;
369 };
370
371 // FTree 的 OnDeletion 事件方法
372 template <class T>
373 void TKYMapIntKeyEx<T>::DoDeletion(void* Sender, TKYAVLTreeEx::TNode* ANode)
374 {
375 delete (T*)ANode->Data;
376 }
377
378 // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
379
380 /* TKYMapStrKeyEx - 字符串鍵值 map 類模板 */
381
382 template <class T>
383 class TKYMapStrKeyEx
384 {
385 public:
386 // 構造函數
387 // 1. ACaseSensitive 鍵值是否區分大小寫, 若為 false 則不區分大小寫
388 // 2. ANeedFree 鍵值是否需要釋放, 若為 false 則不釋放
389 // 3. ACanLock 是否內置鎖, 為了多線程存取安全, 也可以外部使用鎖控制
390 TKYMapStrKeyEx(bool ACaseSensitive = false, bool ANeedFree = false,
391 bool ACanLock = false)
392 {
393 // 初始化
394 FNeedFree = ANeedFree;
395 FCaseSensitive = ACaseSensitive;
396
397 // 創建 AVL 樹
398 FTree = new TKYAVLTreeEx(ACanLock, false);
399
400 // 設置 FTree 的事件方法
401 FTree->OnCompare.Object = this;
402 FTree->OnCompare.Method = (TKYAVLTreeEx::TDoCompare)
403 &TKYMapStrKeyEx<T>::DoCompare;
404 FTree->OnDeletion.Object = this;
405 FTree->OnDeletion.Method = (TKYAVLTreeEx::TDoDeletion)
406 &TKYMapStrKeyEx<T>::DoDeletion;
407 }
408
409 // 析構函數
410 ~TKYMapStrKeyEx() { FreeAndNil(FTree); }
411
412 // 屬性
413 void* Data() const { return FTree->Data(); } // default: NULL
414 long Count() const { return FTree->Count(); } // default: 0
415 long MaxCount() const { return FTree->MaxCount(); } // default: 0
416 bool CanDuplicate() const { return FTree->CanDuplicate(); } // default: false
417 bool CaseSensitive() const{ return FCaseSensitive; } // default: false
418
419 // 設置屬性
420 void SetData(void* AData) { FTree->SetData(AData); }
421 void SetMaxCount(long AMaxCount)
422 { FTree->SetMaxCount(AMaxCount); }
423 void SetCanDuplicate(bool ACanDuplicate)
424 { FTree->SetCanDuplicate(ACanDuplicate); }
425
426 // 鍵值項結點的取值和設置值, 注: 不檢查 ANode 是否合法
427 KYString Key(void* ANode) const
428 { return *(KYString*)((TKYAVLTreeEx::TNode*)ANode)->Item; }
429 T* Value(void* ANode) const
430 { return (T*)((TKYAVLTreeEx::TNode*)ANode)->Data; }
431 void SetValue(void* ANode, T* AValue)
432 { ((TKYAVLTreeEx::TNode*)ANode)->Data = (void*)AValue; }
433
434 // 根據索引讀取鍵值項結點, AIndex 取值范圍: [0..Count()-1], 可以快速定位指定索引結點
435 void* Node(long AIndex) const
436 { return (void*)FTree->Node(AIndex); }
437
438 // 取鍵值項結點所在的索引, 若不存在則返回 -1
439 long IndexOf(void* ANode) const
440 { return FTree->IndexOf((TKYAVLTreeEx::TNode*)ANode); }
441
442 // 取鍵值所在的索引, 若不存在則返回 -1
443 long IndexOf(const KYString& AKey) const
444 { return FTree->IndexOf((void*)&AKey, NULL); }
445
446 // 判斷鍵值項結點是否存在
447 bool Existed(void* ANode) const
448 { return FTree->Existed((TKYAVLTreeEx::TNode*)ANode); }
449
450 // 判斷鍵值是否存在
451 bool Existed(const KYString& AKey) const
452 { return FTree->Existed((void*)&AKey, NULL); }
453
454 // 查找鍵值項, 若返回值為 NULL 則未找到鍵值, 否則返回找到的鍵值項結點
455 void* Find(const KYString& AKey) const
456 { return (void*)FTree->Search((void*)&AKey, NULL); }
457
458 // 添加鍵值項, 若返回值為 NULL 則加入失敗, 否則返回加入的鍵值項結點
459 void* Add(const KYString& AKey, T* AValue);
460
461 // 刪除鍵值項
462 bool Delete(const KYString& AKey)
463 { return FTree->Delete((void*)&AKey, NULL); }
464
465 // 刪除鍵值項結點
466 bool Remove(void* ANode) { return FTree->Remove((TKYAVLTreeEx::TNode*)ANode); }
467
468 // 清除所有鍵值項結點
469 void Clear() { FTree->Clear(); }
470
471 // 取第一個鍵值項結點
472 void* First() const { return (void*)FTree->Next(NULL); }
473
474 // 取最后一個鍵值項結點
475 void* Last() const { return (void*)FTree->Prior(NULL); }
476
477 // 取下一鍵值項結點, 若ANode == NULL, 則取第一個鍵值項結點
478 void* Next(void* ANode) const
479 { return (void*)FTree->Next((TKYAVLTreeEx::TNode*)ANode); }
480
481 // 取上一鍵值項結點, 若ANode == NULL, 則取最后一個鍵值項結點
482 void* Prior(void* ANode) const
483 { return (void*)FTree->Prior((TKYAVLTreeEx::TNode*)ANode); }
484
485 private:
486 void DoCompare(const TKYAVLTreeEx::TNode* ANode1,
487 const TKYAVLTreeEx::TNode* ANode2, long& ACompare);
488 void DoDeletion(void* Sender, TKYAVLTreeEx::TNode* ANode);
489
490 private:
491 TKYAVLTreeEx* FTree;
492 bool FNeedFree;
493 bool FCaseSensitive;
494 };
495
496 // FTree 的 OnCompare 事件方法
497 template <class T>
498 void TKYMapStrKeyEx<T>::DoCompare(const TKYAVLTreeEx::TNode* ANode1,
499 const TKYAVLTreeEx::TNode* ANode2, long& ACompare)
500 {
501 ACompare = CompareStr(*(KYString*)ANode1->Item,
502 *(KYString*)ANode2->Item, FCaseSensitive);
503 }
504
505 // FTree 的 OnDeletion 事件方法
506 template <class T>
507 void TKYMapStrKeyEx<T>::DoDeletion(void* Sender, TKYAVLTreeEx::TNode* ANode)
508 {
509 // 釋放鍵值
510 delete (KYString*)ANode->Item;
511
512 // 判斷是否需要釋放
513 if (FNeedFree)
514 delete (T*)ANode->Data;
515 }
516
517 // 添加鍵值項, 若返回值為 NULL 則加入失敗, 否則返回加入的鍵值項結點
518 template <class T>
519 void* TKYMapStrKeyEx<T>::Add(const KYString& AKey, T* AValue)
520 {
521 // 加入
522 KYString* pKey = new KYString(AKey);
523 TKYAVLTreeEx::TNode* result = FTree->Add((void*)pKey, (void*)AValue);
524
525 // 若加入失敗則釋放
526 if (result == NULL)
527 delete pKey;
528
529 // 返回結果
530 return (void*)result;
531 }
532
533 }
534
535 #endif
536
posted on 2011-05-22 12:10
Kyee Ye 閱讀(607)
評論(0) 編輯 收藏 引用 所屬分類:
C++類庫KYLib