00001
00002
00003
00004
00005
00006
00007
00008
00009 #ifndef __TOOLBOX_HASHMAP_H
00010 #define __TOOLBOX_HASHMAP_H
00011
00012
00016 #define _TB_HM_DEFAULTINITSIZE 16
00017
00021 #define _TB_HM_DEFAULTDESIREDFILLRATIO 50
00022
00026 #define _TB_HM_MINIMUMSIZE 1
00027
00031 #define _TB_HM_MINIMUMDESIREDFILLRATIO 10
00032
00033
00034 namespace toolbox
00035 {
00048 template <class VALUETYPE> class HashMap
00049 {
00050 private:
00051
00056 long Count;
00057
00066 int DesiredFillRatio;
00067
00072 long InitSize;
00073
00074 #ifdef _TOOLBOX_TEST
00075
00078 static int InstanceCount;
00079 #endif
00080
00085 void CheckSize();
00086
00092 void Init(long initSize, int desiredFillRatio);
00093
00098 void Rehash(long newSize);
00099
00111 void SetWithoutSizeChecking(void * key, VALUETYPE * Value);
00112
00113 protected:
00114
00118 PointeredList ** KeyBuckets;
00119
00124 long Size;
00125
00129 PointeredList ** ValueBuckets;
00130
00145 virtual void * CreateKey(void * key) const;
00146
00159 virtual void DestroyKey(void * key) const;
00160
00171 virtual bool Equals(void * key1, void * key2) const;
00172
00185 virtual unsigned long HashCode(void * key) const;
00186
00187 public:
00188
00192 HashMap();
00193
00199 HashMap(long initSize);
00200
00212 HashMap(long initSize, int desiredFillRatio);
00213
00219 virtual ~HashMap();
00220
00227 bool ContainsKey(void * key) const;
00228
00237 void Delete(void * key);
00238
00245 void DeleteAll();
00246
00254 VALUETYPE * Get(void * key) const;
00255
00260 inline long GetCount() const;
00261
00266 inline int GetDesiredFillRatio() const;
00267
00274 inline int GetFillRatio() const;
00275
00283 PointeredList * GetKeys() const;
00284
00290 inline long GetSize() const;
00291
00299 PointeredList * GetValues() const;
00300
00305 inline bool IsEmpty() const;
00306
00307 #ifdef _TOOLBOX_TEST
00308
00314 static void RunTestSuite(int * performedTests, int * failedTests);
00315 #endif
00316
00317 #ifdef _TOOLBOX_TEST
00318
00331 static void RunTestSuiteCheck(int * performedTests, int * failedTests,
00332 HashMap<TestObject> * TestHashMap, TestObject ** Keys, TestObject ** Values,
00333 int firstContained, int firstNotContained);
00334 #endif
00335
00352 void Set(void * key, VALUETYPE * Value);
00353
00364 VALUETYPE * Unset(void * key);
00365
00374 void UnsetAll();
00375 };
00376
00377
00383 template <class VALUETYPE> class IntKeyHashMap : public HashMap<VALUETYPE>
00384 {
00385 private:
00386
00387 #ifdef _TOOLBOX_TEST
00388
00391 static int InstanceCount;
00392 #endif
00393
00394 protected:
00395
00406 virtual unsigned long HashCode(void * key) const;
00407
00408 public:
00409
00413 IntKeyHashMap();
00414
00420 IntKeyHashMap(long initSize);
00421
00433 IntKeyHashMap(long initSize, int desiredFillRatio);
00434
00438 virtual ~IntKeyHashMap();
00439
00446 bool ContainsKey(long key) const;
00447
00454 inline void Delete(long key);
00455
00463 inline VALUETYPE * Get(long key) const;
00464
00465 #ifdef _TOOLBOX_TEST
00466
00472 static void RunTestSuite(int * performedTests, int * failedTests);
00473 #endif
00474
00488 inline void Set(long key, VALUETYPE * Value);
00489
00499 inline VALUETYPE * Unset(long key);
00500 };
00501
00502
00510 template <class VALUETYPE> class StringKeyHashMap : public HashMap<VALUETYPE>
00511 {
00512 private:
00513
00514 #ifdef _TOOLBOX_TEST
00515
00518 static int InstanceCount;
00519 #endif
00520
00521 protected:
00522
00536 virtual void * CreateKey(void * key) const;
00537
00548 virtual void DestroyKey(void * key) const;
00549
00558 virtual bool Equals(void * key1, void * key2) const;
00559
00570 virtual unsigned long HashCode(void * key) const;
00571
00572 public:
00573
00577 StringKeyHashMap();
00578
00584 StringKeyHashMap(long initSize);
00585
00597 StringKeyHashMap(long initSize, int desiredFillRatio);
00598
00602 virtual ~StringKeyHashMap();
00603
00609 bool ContainsKey(const char * key) const;
00610
00618 inline void Delete(const char * key);
00619
00626 inline VALUETYPE * Get(const char * key) const;
00627
00628 #ifdef _TOOLBOX_TEST
00629
00635 static void RunTestSuite(int * performedTests, int * failedTests);
00636 #endif
00637
00653 inline void Set(const char * key, VALUETYPE * Value);
00654
00664 inline VALUETYPE * Unset(const char * key);
00665 };
00666
00667
00673 template <class VALUETYPE> class ICStringKeyHashMap : public StringKeyHashMap<VALUETYPE>
00674 {
00675 private:
00676
00677 #ifdef _TOOLBOX_TEST
00678
00681 static int InstanceCount;
00682 #endif
00683
00684 protected:
00685
00694 virtual bool Equals(void * key1, void * key2) const;
00695
00706 virtual unsigned long HashCode(void * key) const;
00707
00708 public:
00709
00713 ICStringKeyHashMap();
00714
00720 ICStringKeyHashMap(long initSize);
00721
00733 ICStringKeyHashMap(long initSize, int desiredFillRatio);
00734
00738 virtual ~ICStringKeyHashMap();
00739
00740 #ifdef _TOOLBOX_TEST
00741
00747 static void RunTestSuite(int * performedTests, int * failedTests);
00748 #endif
00749 };
00750 }
00751
00752
00753 #endif