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 WM4THASHSET_H 00017 #define WM4THASHSET_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. THashSet will use modular arithmetic to make this 00031 // happen. 00032 00033 #include "Wm4System.h" 00034 00035 namespace Wm4 00036 { 00037 00038 template <class TKEY> 00039 class THashSet 00040 { 00041 public: 00042 // construction and destruction 00043 THashSet (int iTableSize); 00044 ~THashSet (); 00045 00046 // element access 00047 int GetQuantity () const; 00048 00049 // A pointer to the actual storage is returned so that the caller has 00050 // direct access to it. This allows a subset of TKEY members to be used 00051 // in key comparison. 00052 TKEY* Insert (const TKEY& rtKey); 00053 00054 // If the input key exists, a pointer to the actual storage is returned. 00055 // This allows a subset of TKEY members to be used in key comparison, 00056 // but gives the caller a chance to modify other TKEY members. 00057 TKEY* Get (const TKEY& rtKey) const; 00058 00059 bool Remove (const TKEY& rtKey); 00060 void RemoveAll (); 00061 00062 // linear traversal of map 00063 TKEY* GetFirst () const; 00064 TKEY* GetNext () const; 00065 00066 // user-specified key-to-index construction 00067 int (*UserHashFunction)(const TKEY&); 00068 00069 private: 00070 class HashItem 00071 { 00072 public: 00073 TKEY m_tKey; 00074 HashItem* m_pkNext; 00075 }; 00076 00077 // Default key-to-index construction (override by user-specified when 00078 // requested). 00079 int HashFunction (const TKEY& rtKey) const; 00080 00081 // hash table 00082 int m_iTableSize; 00083 int m_iQuantity; 00084 HashItem** m_apkTable; 00085 00086 // iterator for traversal 00087 mutable int m_iIndex; 00088 mutable HashItem* m_pkItem; 00089 }; 00090 00091 #include "Wm4THashSet.inl" 00092 00093 } 00094 00095 #endif