csutil/hash.h
Go to the documentation of this file.
00001 /* 00002 Copyright (C) 2003 by Mat Sutcliffe <oktal@gmx.co.uk> 00003 00004 This library is free software; you can redistribute it and/or 00005 modify it under the terms of the GNU Lesser General Public 00006 License as published by the Free Software Foundation; either 00007 version 2 of the License, or (at your option) any later version. 00008 00009 This library is distributed in the hope that it will be useful, 00010 but WITHOUT ANY WARRANTY; without even the implied warranty of 00011 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00012 Library General Public License for more details. 00013 00014 You should have received a copy of the GNU Library General Public 00015 License along with this library; if not, write to the Free 00016 Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. 00017 */ 00018 00019 #ifndef __CS_UTIL_HASH_H__ 00020 #define __CS_UTIL_HASH_H__ 00021 00026 #include "csextern.h" 00027 #include "csutil/array.h" 00028 #include "csutil/comparator.h" 00029 #include "csutil/util.h" 00030 #include "csutil/tuple.h" 00031 00041 CS_CRYSTALSPACE_EXPORT 00042 unsigned int csHashCompute (char const*); 00043 00050 CS_CRYSTALSPACE_EXPORT 00051 unsigned int csHashCompute (char const*, size_t length); 00052 00057 template <class T> 00058 class csHashComputer 00059 { 00060 public: 00062 static uint ComputeHash (const T& key) 00063 { 00064 return key.GetHash(); 00065 } 00066 }; 00067 00072 template <class T> 00073 class csHashComputerIntegral 00074 { 00075 public: 00077 static uint ComputeHash (const T& key) 00078 { 00079 return (uintptr_t)key; 00080 } 00081 }; 00082 00084 00087 template<> 00088 class csHashComputer<void*> : public csHashComputerIntegral<void*> {}; 00089 00090 template<> 00091 class csHashComputer<int> : public csHashComputerIntegral<int> {}; 00092 template<> 00093 class csHashComputer<unsigned int> : 00094 public csHashComputerIntegral<unsigned int> {}; 00095 00096 template<> 00097 class csHashComputer<long> : public csHashComputerIntegral<long> {}; 00098 template<> 00099 class csHashComputer<unsigned long> : 00100 public csHashComputerIntegral<unsigned long> {}; 00101 00102 #if (CS_LONG_SIZE < 8) 00103 template<> 00104 class csHashComputer<longlong> : 00105 public csHashComputerIntegral<longlong> {}; 00106 template<> 00107 class csHashComputer<ulonglong> : 00108 public csHashComputerIntegral<ulonglong> {}; 00109 #endif 00110 00111 template<> 00112 class csHashComputer<float> 00113 { 00114 public: 00116 static uint ComputeHash (float key) 00117 { 00118 union 00119 { 00120 float f; 00121 uint u; 00122 } float2uint; 00123 float2uint.f = key; 00124 return float2uint.u; 00125 } 00126 }; 00127 template<> 00128 class csHashComputer<double> 00129 { 00130 public: 00132 static uint ComputeHash (double key) 00133 { 00134 union 00135 { 00136 double f; 00137 uint u; 00138 } double2uint; 00139 double2uint.f = key; 00140 return double2uint.u; 00141 } 00142 }; 00144 00148 template <typename T> 00149 class csPtrKey 00150 { 00151 T* ptr; 00152 public: 00153 csPtrKey () : ptr(0) {} 00154 csPtrKey (T* ptr) : ptr(ptr) {} 00155 csPtrKey (csPtrKey const& other) : ptr (other.ptr) {} 00156 00157 uint GetHash () const { return (uintptr_t)ptr; } 00158 inline friend bool operator < (const csPtrKey& r1, const csPtrKey& r2) 00159 { return r1.ptr < r2.ptr; } 00160 operator T* () const 00161 { return ptr; } 00162 T* operator -> () const 00163 { return ptr; } 00164 csPtrKey& operator = (csPtrKey const& other) 00165 { ptr = other.ptr; return *this; } 00166 }; 00167 00171 template <typename T> 00172 class csConstPtrKey 00173 { 00174 const T* ptr; 00175 public: 00176 csConstPtrKey () : ptr(0) {} 00177 csConstPtrKey (const T* ptr) : ptr(ptr) {} 00178 csConstPtrKey (csConstPtrKey const& other) : ptr (other.ptr) {} 00179 00180 uint GetHash () const { return (uintptr_t)ptr; } 00181 inline friend bool operator < (const csConstPtrKey& r1, const csConstPtrKey& r2) 00182 { return r1.ptr < r2.ptr; } 00183 operator const T* () const 00184 { return ptr; } 00185 const T* operator -> () const 00186 { return ptr; } 00187 csConstPtrKey& operator = (csConstPtrKey const& other) 00188 { ptr = other.ptr; return *this; } 00189 }; 00190 00200 template <class T> 00201 class csHashComputerString 00202 { 00203 public: 00204 static uint ComputeHash (const T& key) 00205 { 00206 return csHashCompute ((const char*)key); 00207 } 00208 }; 00209 00213 template<> 00214 class csHashComputer<const char*> : public csHashComputerString<const char*> {}; 00215 00225 template <class T> 00226 class csHashComputerStruct 00227 { 00228 public: 00229 static uint ComputeHash (const T& key) 00230 { 00231 return csHashCompute ((char*)&key, sizeof (T)); 00232 } 00233 }; 00234 00235 template <class T, class K, 00236 class ArrayMemoryAlloc, class ArrayElementHandler> class csHash; 00237 00238 namespace CS 00239 { 00240 namespace Container 00241 { 00247 template <class T, class K> 00248 class HashElement 00249 { 00250 private: 00251 template <class _T, class _K, class ArrayMemoryAlloc, 00252 class ArrayElementHandler> friend class csHash; 00253 00254 const K key; 00255 T value; 00256 00257 HashElement (const K& key0, const T &value0) : key (key0), value (value0) {} 00258 public: 00259 HashElement (const HashElement& other) : key (other.key), value (other.value) {} 00260 00261 const K& GetKey() const { return key; } 00262 const T& GetValue() const { return value; } 00263 T& GetValue() { return value; } 00264 }; 00265 } // namespace Container 00266 } // namespace CS 00267 00277 template <class T, class K = unsigned int, 00278 class ArrayMemoryAlloc = CS::Memory::AllocatorMalloc, 00279 class ArrayElementHandler = csArrayElementHandler< 00280 CS::Container::HashElement<T, K> > > 00281 class csHash 00282 { 00283 public: 00284 typedef csHash<T, K, ArrayMemoryAlloc, ArrayElementHandler> ThisType; 00285 typedef T ValueType; 00286 typedef K KeyType; 00287 typedef ArrayMemoryAlloc AllocatorType; 00288 00289 protected: 00290 typedef CS::Container::HashElement<T, K> Element; 00291 typedef csArray<Element, 00292 ArrayElementHandler, ArrayMemoryAlloc> ElementArray; 00293 csArray<ElementArray, csArrayElementHandler<ElementArray>, 00294 ArrayMemoryAlloc> Elements; 00295 00296 size_t Modulo; 00297 size_t Size; 00298 00299 private: 00300 size_t InitModulo; 00301 size_t GrowRate; 00302 size_t MaxSize; 00303 00304 void Grow () 00305 { 00306 static const size_t Primes[] = 00307 { 00308 53, 97, 193, 389, 769, 00309 1543, 3079, 6151, 12289, 24593, 00310 49157, 98317, 196613, 393241, 786433, 00311 1572869, 3145739, 6291469, 12582917, 25165843, 00312 50331653, 100663319, 201326611, 402653189, 805306457, 00313 1610612741, 0 00314 }; 00315 00316 const size_t *p; 00317 size_t elen = Elements.GetSize (); 00318 for (p = Primes; *p && *p <= elen; p++) ; 00319 Modulo = *p; 00320 CS_ASSERT (Modulo); 00321 00322 Elements.SetSize (Modulo, ElementArray (0, MIN(Modulo / GrowRate, 4))); 00323 00324 for (size_t i = 0; i < elen; i++) 00325 { 00326 ElementArray& src = Elements[i]; 00327 size_t slen = src.GetSize (); 00328 for (size_t j = slen; j > 0; j--) 00329 { 00330 const Element& srcElem = src[j - 1]; 00331 ElementArray& dst = 00332 Elements.Get (csHashComputer<K>::ComputeHash (srcElem.key) % Modulo); 00333 if (&src != &dst) 00334 { 00335 dst.Push (srcElem); 00336 src.DeleteIndex (j - 1); 00337 } 00338 } 00339 } 00340 } 00341 00342 public: 00357 csHash (size_t size = 23, size_t grow_rate = 5, size_t max_size = 20000) 00358 : Modulo (size), Size(0), InitModulo (size), 00359 GrowRate (MIN (grow_rate, size)), MaxSize (max_size) 00360 { 00361 } 00362 00364 csHash (const csHash<T, K, ArrayMemoryAlloc, ArrayElementHandler> &o) : 00365 Elements (o.Elements), 00366 Modulo (o.Modulo), Size(o.Size), InitModulo (o.InitModulo), 00367 GrowRate (o.GrowRate), MaxSize (o.MaxSize) {} 00368 00376 T& Put (const K& key, const T &value) 00377 { 00378 if (Elements.GetSize() == 0) Elements.SetSize (Modulo); 00379 ElementArray& values = 00380 Elements[csHashComputer<K>::ComputeHash (key) % Modulo]; 00381 size_t idx = values.Push (Element (key, value)); 00382 Size++; 00383 if (values.GetSize () > Elements.GetSize () / GrowRate 00384 && Elements.GetSize () < MaxSize) 00385 { 00386 Grow (); 00387 /* can't use 'values[idx]' since that is no longer the place where 00388 the item is stored. */ 00389 return *(GetElementPointer (key)); 00390 } 00391 return values[idx].value; 00392 } 00393 00395 csArray<T> GetAll () const 00396 { 00397 if (Elements.GetSize() == 0) return csArray<T> (); 00398 00399 ConstGlobalIterator itr = GetIterator(); 00400 csArray<T> ret; 00401 while(itr.HasNext()) 00402 { 00403 ret.Push(itr.Next()); 00404 } 00405 00406 return ret; 00407 } 00408 00410 csArray<T> GetAll (const K& key) const 00411 { 00412 return GetAll<typename csArray<T>::ElementHandlerType, 00413 typename csArray<T>::AllocatorType> (key); 00414 } 00415 00417 template<typename H, typename M> 00418 csArray<T, H, M> GetAll (const K& key) const 00419 { 00420 if (Elements.GetSize() == 0) return csArray<T> (); 00421 const ElementArray& values = 00422 Elements[csHashComputer<K>::ComputeHash (key) % Modulo]; 00423 csArray<T> ret (values.GetSize () / 2); 00424 const size_t len = values.GetSize (); 00425 for (size_t i = 0; i < len; ++i) 00426 { 00427 const Element& v = values[i]; 00428 if (csComparator<K, K>::Compare (v.key, key) == 0) 00429 ret.Push (v.value); 00430 } 00431 return ret; 00432 } 00433 00435 T& PutUnique (const K& key, const T &value) 00436 { 00437 if (Elements.GetSize() == 0) Elements.SetSize (Modulo); 00438 ElementArray& values = 00439 Elements[csHashComputer<K>::ComputeHash (key) % Modulo]; 00440 const size_t len = values.GetSize (); 00441 for (size_t i = 0; i < len; ++i) 00442 { 00443 Element& v = values[i]; 00444 if (csComparator<K, K>::Compare (v.key, key) == 0) 00445 { 00446 v.value = value; 00447 return v.value; 00448 } 00449 } 00450 00451 size_t idx = values.Push (Element (key, value)); 00452 Size++; 00453 if (values.GetSize () > Elements.GetSize () / GrowRate 00454 && Elements.GetSize () < MaxSize) 00455 { 00456 Grow (); 00457 /* can't use 'values[idx]' since that is no longer the place where 00458 the item is stored. */ 00459 return *(GetElementPointer (key)); 00460 } 00461 return values[idx].value; 00462 } 00463 00465 bool Contains (const K& key) const 00466 { 00467 if (Elements.GetSize() == 0) return false; 00468 const ElementArray& values = 00469 Elements[csHashComputer<K>::ComputeHash (key) % Modulo]; 00470 const size_t len = values.GetSize (); 00471 for (size_t i = 0; i < len; ++i) 00472 if (csComparator<K, K>::Compare (values[i].key, key) == 0) 00473 return true; 00474 return false; 00475 } 00476 00482 bool In (const K& key) const 00483 { return Contains(key); } 00484 00489 const T* GetElementPointer (const K& key) const 00490 { 00491 if (Elements.GetSize() == 0) return 0; 00492 const ElementArray& values = 00493 Elements[csHashComputer<K>::ComputeHash (key) % Modulo]; 00494 const size_t len = values.GetSize (); 00495 for (size_t i = 0; i < len; ++i) 00496 { 00497 const Element& v = values[i]; 00498 if (csComparator<K, K>::Compare (v.key, key) == 0) 00499 return &v.value; 00500 } 00501 00502 return 0; 00503 } 00504 00509 T* GetElementPointer (const K& key) 00510 { 00511 if (Elements.GetSize() == 0) return 0; 00512 ElementArray& values = 00513 Elements[csHashComputer<K>::ComputeHash (key) % Modulo]; 00514 const size_t len = values.GetSize (); 00515 for (size_t i = 0; i < len; ++i) 00516 { 00517 Element& v = values[i]; 00518 if (csComparator<K, K>::Compare (v.key, key) == 0) 00519 return &v.value; 00520 } 00521 00522 return 0; 00523 } 00524 00528 T* operator[] (const K& key) 00529 { 00530 return GetElementPointer (key); 00531 } 00532 00537 const T& Get (const K& key, const T& fallback) const 00538 { 00539 if (Elements.GetSize() == 0) return fallback; 00540 const ElementArray& values = 00541 Elements[csHashComputer<K>::ComputeHash (key) % Modulo]; 00542 const size_t len = values.GetSize (); 00543 for (size_t i = 0; i < len; ++i) 00544 { 00545 const Element& v = values[i]; 00546 if (csComparator<K, K>::Compare (v.key, key) == 0) 00547 return v.value; 00548 } 00549 00550 return fallback; 00551 } 00552 00557 T& Get (const K& key, T& fallback) 00558 { 00559 if (Elements.GetSize() == 0) return fallback; 00560 ElementArray& values = 00561 Elements[csHashComputer<K>::ComputeHash (key) % Modulo]; 00562 const size_t len = values.GetSize (); 00563 for (size_t i = 0; i < len; ++i) 00564 { 00565 Element& v = values[i]; 00566 if (csComparator<K, K>::Compare (v.key, key) == 0) 00567 return v.value; 00568 } 00569 00570 return fallback; 00571 } 00572 00577 T& GetOrCreate (const K& key, const T& defaultValue = T()) 00578 { 00579 if (Elements.GetSize() != 0) 00580 { 00581 ElementArray& values = 00582 Elements[csHashComputer<K>::ComputeHash (key) % Modulo]; 00583 const size_t len = values.GetSize (); 00584 for (size_t i = 0; i < len; ++i) 00585 { 00586 Element& v = values[i]; 00587 if (csComparator<K, K>::Compare (v.key, key) == 0) 00588 return v.value; 00589 } 00590 } 00591 00592 return Put (key, defaultValue); 00593 } 00594 00596 void DeleteAll () 00597 { 00598 Elements.DeleteAll(); 00599 Modulo = InitModulo; 00600 Size = 0; 00601 } 00602 00604 void Empty() { DeleteAll(); } 00605 00607 bool DeleteAll (const K& key) 00608 { 00609 bool ret = false; 00610 if (Elements.GetSize() == 0) return ret; 00611 ElementArray& values = 00612 Elements[csHashComputer<K>::ComputeHash (key) % Modulo]; 00613 for (size_t i = values.GetSize (); i > 0; i--) 00614 { 00615 const size_t idx = i - 1; 00616 if (csComparator<K, K>::Compare (values[idx].key, key) == 0) 00617 { 00618 values.DeleteIndexFast (idx); 00619 ret = true; 00620 Size--; 00621 } 00622 } 00623 return ret; 00624 } 00625 00627 bool Delete (const K& key, const T &value) 00628 { 00629 bool ret = false; 00630 if (Elements.GetSize() == 0) return ret; 00631 ElementArray& values = 00632 Elements[csHashComputer<K>::ComputeHash (key) % Modulo]; 00633 for (size_t i = values.GetSize (); i > 0; i--) 00634 { 00635 const size_t idx = i - 1; 00636 if ((csComparator<K, K>::Compare (values[idx].key, key) == 0) && 00637 (csComparator<T, T>::Compare (values[idx].value, value) == 0 )) 00638 { 00639 values.DeleteIndexFast (idx); 00640 ret = true; 00641 Size--; 00642 } 00643 } 00644 return ret; 00645 } 00646 00648 size_t GetSize () const 00649 { 00650 return Size; 00651 } 00652 00658 bool IsEmpty() const 00659 { 00660 return GetSize() == 0; 00661 } 00662 00664 class Iterator 00665 { 00666 private: 00667 csHash<T, K, ArrayMemoryAlloc, ArrayElementHandler>* hash; 00668 const K key; 00669 size_t bucket, size, element; 00670 00671 void Seek () 00672 { 00673 while ((element < size) && 00674 (csComparator<K, K>::Compare (hash->Elements[bucket][element].GetKey(), 00675 key) != 0)) 00676 element++; 00677 } 00678 00679 protected: 00680 Iterator (csHash<T, K, ArrayMemoryAlloc, ArrayElementHandler>* hash0, 00681 const K& key0) : 00682 hash(hash0), 00683 key(key0), 00684 bucket(csHashComputer<K>::ComputeHash (key) % hash->Modulo), 00685 size((hash->Elements.GetSize() > 0) ? hash->Elements[bucket].GetSize () : 0) 00686 { Reset (); } 00687 00688 friend class csHash<T, K, ArrayMemoryAlloc, ArrayElementHandler>; 00689 public: 00691 Iterator (const Iterator &o) : 00692 hash (o.hash), 00693 key(o.key), 00694 bucket(o.bucket), 00695 size(o.size), 00696 element(o.element) {} 00697 00699 Iterator& operator=(const Iterator& o) 00700 { 00701 hash = o.hash; 00702 key = o.key; 00703 bucket = o.bucket; 00704 size = o.size; 00705 element = o.element; 00706 return *this; 00707 } 00708 00710 bool HasNext () const 00711 { 00712 return element < size; 00713 } 00714 00716 T& Next () 00717 { 00718 T &ret = hash->Elements[bucket][element].GetValue(); 00719 element++; 00720 Seek (); 00721 return ret; 00722 } 00723 00725 void Reset () { element = 0; Seek (); } 00726 }; 00727 friend class Iterator; 00728 00730 class GlobalIterator 00731 { 00732 private: 00733 csHash<T, K, ArrayMemoryAlloc, ArrayElementHandler> *hash; 00734 size_t bucket, size, element; 00735 00736 void Zero () { bucket = element = 0; } 00737 void Init () 00738 { 00739 size = 00740 (hash->Elements.GetSize() > 0) ? hash->Elements[bucket].GetSize () : 0; 00741 } 00742 00743 void FindItem () 00744 { 00745 if (element >= size) 00746 { 00747 while (++bucket < hash->Elements.GetSize ()) 00748 { 00749 Init (); 00750 if (size != 0) 00751 { 00752 element = 0; 00753 break; 00754 } 00755 } 00756 } 00757 } 00758 00759 protected: 00760 GlobalIterator (csHash<T, K, ArrayMemoryAlloc, ArrayElementHandler> *hash0) 00761 : hash (hash0) 00762 { 00763 Zero (); 00764 Init (); 00765 FindItem (); 00766 } 00767 00768 friend class csHash<T, K, ArrayMemoryAlloc, ArrayElementHandler>; 00769 public: 00771 GlobalIterator (const GlobalIterator &o) : 00772 hash (o.hash), 00773 bucket (o.bucket), 00774 size (o.size), 00775 element (o.element) {} 00776 00778 GlobalIterator& operator=(const GlobalIterator& o) 00779 { 00780 hash = o.hash; 00781 bucket = o.bucket; 00782 size = o.size; 00783 element = o.element; 00784 return *this; 00785 } 00786 00788 bool HasNext () const 00789 { 00790 if (hash->Elements.GetSize () == 0) return false; 00791 return element < size || bucket < hash->Elements.GetSize (); 00792 } 00793 00795 void Advance () 00796 { 00797 element++; 00798 FindItem (); 00799 } 00800 00802 T& NextNoAdvance () 00803 { 00804 return hash->Elements[bucket][element].GetValue(); 00805 } 00806 00808 T& Next () 00809 { 00810 T &ret = NextNoAdvance (); 00811 Advance (); 00812 return ret; 00813 } 00814 00816 T& NextNoAdvance (K &key) 00817 { 00818 key = hash->Elements[bucket][element].GetKey(); 00819 return NextNoAdvance (); 00820 } 00821 00823 T& Next (K &key) 00824 { 00825 key = hash->Elements[bucket][element].GetKey(); 00826 return Next (); 00827 } 00828 00830 const csTuple2<T, K> NextTuple () 00831 { 00832 csTuple2<T, K> t (NextNoAdvance (), 00833 hash->Elements[bucket][element].GetKey()); 00834 Advance (); 00835 return t; 00836 } 00837 00839 void Reset () { Zero (); Init (); FindItem (); } 00840 }; 00841 friend class GlobalIterator; 00842 00844 class ConstIterator 00845 { 00846 private: 00847 const csHash<T, K, ArrayMemoryAlloc, ArrayElementHandler>* hash; 00848 const K key; 00849 size_t bucket, size, element; 00850 00851 void Seek () 00852 { 00853 while ((element < size) && 00854 (csComparator<K, K>::Compare (hash->Elements[bucket][element].key, 00855 key) != 0)) 00856 element++; 00857 } 00858 00859 protected: 00860 ConstIterator (const csHash<T, K, ArrayMemoryAlloc, ArrayElementHandler>* 00861 hash0, const K& key0) : 00862 hash(hash0), 00863 key(key0), 00864 bucket(csHashComputer<K>::ComputeHash (key) % hash->Modulo), 00865 size((hash->Elements.GetSize() > 0) ? hash->Elements[bucket].GetSize () : 0) 00866 { Reset (); } 00867 00868 friend class csHash<T, K, ArrayMemoryAlloc, ArrayElementHandler>; 00869 public: 00871 ConstIterator (const ConstIterator &o) : 00872 hash (o.hash), 00873 key(o.key), 00874 bucket(o.bucket), 00875 size(o.size), 00876 element(o.element) {} 00877 00879 ConstIterator& operator=(const ConstIterator& o) 00880 { 00881 hash = o.hash; 00882 key = o.key; 00883 bucket = o.bucket; 00884 size = o.size; 00885 element = o.element; 00886 return *this; 00887 } 00888 00890 bool HasNext () const 00891 { 00892 return element < size; 00893 } 00894 00896 const T& Next () 00897 { 00898 const T &ret = hash->Elements[bucket][element].value; 00899 element++; 00900 Seek (); 00901 return ret; 00902 } 00903 00905 void Reset () { element = 0; Seek (); } 00906 }; 00907 friend class ConstIterator; 00908 00910 class ConstGlobalIterator 00911 { 00912 private: 00913 const csHash<T, K, ArrayMemoryAlloc, ArrayElementHandler> *hash; 00914 size_t bucket, size, element; 00915 00916 void Zero () { bucket = element = 0; } 00917 void Init () 00918 { 00919 size = 00920 (hash->Elements.GetSize() > 0) ? hash->Elements[bucket].GetSize () : 0; 00921 } 00922 00923 void FindItem () 00924 { 00925 if (element >= size) 00926 { 00927 while (++bucket < hash->Elements.GetSize ()) 00928 { 00929 Init (); 00930 if (size != 0) 00931 { 00932 element = 0; 00933 break; 00934 } 00935 } 00936 } 00937 } 00938 00939 protected: 00940 ConstGlobalIterator (const csHash<T, K, ArrayMemoryAlloc, 00941 ArrayElementHandler> *hash0) : hash (hash0) 00942 { 00943 Zero (); 00944 Init (); 00945 FindItem (); 00946 } 00947 00948 friend class csHash<T, K, ArrayMemoryAlloc, ArrayElementHandler>; 00949 public: 00951 ConstGlobalIterator (const ConstGlobalIterator &o) : 00952 hash (o.hash), 00953 bucket (o.bucket), 00954 size (o.size), 00955 element (o.element) {} 00956 00958 ConstGlobalIterator& operator=(const ConstGlobalIterator& o) 00959 { 00960 hash = o.hash; 00961 bucket = o.bucket; 00962 size = o.size; 00963 element = o.element; 00964 return *this; 00965 } 00966 00968 bool HasNext () const 00969 { 00970 if (hash->Elements.GetSize () == 0) return false; 00971 return element < size || bucket < hash->Elements.GetSize (); 00972 } 00973 00975 void Advance () 00976 { 00977 element++; 00978 FindItem (); 00979 } 00980 00982 const T& NextNoAdvance () 00983 { 00984 return hash->Elements[bucket][element].GetValue(); 00985 } 00986 00988 const T& Next () 00989 { 00990 const T &ret = NextNoAdvance (); 00991 Advance (); 00992 return ret; 00993 } 00994 00996 const T& NextNoAdvance (K &key) 00997 { 00998 key = hash->Elements[bucket][element].GetKey(); 00999 return NextNoAdvance (); 01000 } 01001 01003 const T& Next (K &key) 01004 { 01005 key = hash->Elements[bucket][element].GetKey(); 01006 return Next (); 01007 } 01008 01010 const csTuple2<T, K> NextTuple () 01011 { 01012 csTuple2<T, K> t (NextNoAdvance (), 01013 hash->Elements[bucket][element].GetKey()); 01014 Advance (); 01015 return t; 01016 } 01017 01019 void Reset () { Zero (); Init (); FindItem (); } 01020 }; 01021 friend class ConstGlobalIterator; 01022 01025 void DeleteElement (GlobalIterator& iterator) 01026 { 01027 Elements[iterator.bucket].DeleteIndex(iterator.element); 01028 Size--; 01029 iterator.size--; 01030 iterator.FindItem (); 01031 } 01032 01035 void DeleteElement (ConstGlobalIterator& iterator) 01036 { 01037 Elements[iterator.bucket].DeleteIndex(iterator.element); 01038 Size--; 01039 iterator.size--; 01040 iterator.FindItem (); 01041 } 01042 01049 Iterator GetIterator (const K& key) 01050 { 01051 return Iterator (this, key); 01052 } 01053 01059 GlobalIterator GetIterator () 01060 { 01061 return GlobalIterator (this); 01062 } 01063 01070 ConstIterator GetIterator (const K& key) const 01071 { 01072 return ConstIterator (this, key); 01073 } 01074 01080 ConstGlobalIterator GetIterator () const 01081 { 01082 return ConstGlobalIterator (this); 01083 } 01084 }; 01085 01088 #endif
Generated for Crystal Space 1.4.1 by doxygen 1.7.1