Wm4THashTable.h

Go to the documentation of this file.
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

Generated on Fri Feb 13 13:58:10 2009 for meshmorph by  doxygen 1.5.1