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