00001 // Wild Magic Source Code 00002 // David Eberly 00003 // http://www.geometrictools.com 00004 // Copyright (c) 1998-2008 00005 // 00006 // This library is free software; you can redistribute it and/or modify it 00007 // under the terms of the GNU Lesser General Public License as published by 00008 // the Free Software Foundation; either version 2.1 of the License, or (at 00009 // your option) any later version. The license is available for reading at 00010 // either of the locations: 00011 // http://www.gnu.org/copyleft/lgpl.html 00012 // http://www.geometrictools.com/License/WildMagicLicense.pdf 00013 // 00014 // Version: 4.0.0 (2006/06/28) 00015 00016 #ifndef WM4THASHTABLE_H 00017 #define WM4THASHTABLE_H 00018 00019 #include "Wm4FoundationLIB.h" 00020 00021 // The class TKEY is either native data or is class data that has the 00022 // following member functions: 00023 // TKEY::TKEY () 00024 // TKEY& TKEY::operator= (const TKEY&) 00025 // bool TKEY::operator== (const TKEY&) const 00026 // bool TKEY::operator!= (const TKEY&) const 00027 // TKEY::operator unsigned int () const 00028 // The implicit conversion to unsigned int is used to select a hash table 00029 // index for the T object. The return value need not be within the range of 00030 // hash table indices. THashTable will use modular arithmetic to make this 00031 // happen. 00032 // 00033 // The class TVALUE is either native data or is class data that has the 00034 // following member functions: 00035 // TVALUE::TVALUE () 00036 // TVALUE& TVALUE::operator= (const TVALUE&) 00037 00038 #include "Wm4System.h" 00039 00040 namespace Wm4 00041 { 00042 00043 template <class TKEY, class TVALUE> 00044 class THashTable 00045 { 00046 public: 00047 // construction and destruction 00048 THashTable (int iTableSize); 00049 ~THashTable (); 00050 00051 // element access 00052 int GetQuantity () const; 00053 00054 // insert a key-value pair into the hash table 00055 bool Insert (const TKEY& rtKey, const TVALUE& rtValue); 00056 00057 // search for a key and returns it value (null, if key does not exist) 00058 TVALUE* Find (const TKEY& rtKey) const; 00059 00060 // remove key-value pairs from the hash table 00061 bool Remove (const TKEY& rtKey); 00062 void RemoveAll (); 00063 00064 // linear traversal of table 00065 TVALUE* GetFirst (TKEY* ptKey) const; 00066 TVALUE* GetNext (TKEY* ptKey) const; 00067 00068 // user-specified key-to-index construction 00069 int (*UserHashFunction)(const TKEY&); 00070 00071 private: 00072 class HashItem 00073 { 00074 public: 00075 TKEY m_tKey; 00076 TVALUE m_tValue; 00077 HashItem* m_pkNext; 00078 }; 00079 00080 // Default key-to-index construction (override by user-specified when 00081 // requested). 00082 int HashFunction (const TKEY& rtKey) const; 00083 00084 // hash table 00085 int m_iTableSize; 00086 int m_iQuantity; 00087 HashItem** m_apkTable; 00088 00089 // iterator for traversal 00090 mutable int m_iIndex; 00091 mutable HashItem* m_pkItem; 00092 }; 00093 00094 #include "Wm4THashTable.inl" 00095 00096 } 00097 00098 #endif