00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019 #ifndef __CSUTIL_WEAKKEYEDHASH_H__
00020 #define __CSUTIL_WEAKKEYEDHASH_H__
00021
00022 #include "hash.h"
00023
00024 namespace CS
00025 {
00026 namespace Container
00027 {
00047 template <class T, class K,
00048 class ArrayMemoryAlloc = CS::Container::ArrayAllocDefault,
00049 class ArrayElementHandler = csArraySafeCopyElementHandler<
00050 CS::Container::HashElement<T, K> > >
00051 class WeakKeyedHash :
00052 protected csHash<T, K, ArrayMemoryAlloc, ArrayElementHandler>
00053 {
00054 typedef csHash<T, K, ArrayMemoryAlloc, ArrayElementHandler> Superclass;
00055 public:
00056
00061 const T& Get (const K& key, const T& fallback)
00062 {
00063 if (this->Elements.GetSize() == 0) return fallback;
00064 typename Superclass::ElementArray& values =
00065 this->Elements[csHashComputer<K>::ComputeHash (key) % this->Modulo];
00066 const size_t len = values.GetSize ();
00067 for (size_t i = 0; i < len; ++i)
00068 {
00069 const typename Superclass::Element& v = values[i];
00070
00071 if (!v.GetKey())
00072 {
00073 values.DeleteIndexFast (i);
00074 this->Size--;
00075 i--;
00076 continue;
00077 }
00078 if (csComparator<K, K>::Compare (v.GetKey(), key) == 0)
00079 return v.GetValue();
00080 }
00081
00082 return fallback;
00083 }
00084 using Superclass::Get;
00085
00093 T& Put (const K& key, const T &value)
00094 {
00095 if (this->Elements.GetSize() == 0) this->Elements.SetSize (this->Modulo);
00096 typename Superclass::ElementArray& values =
00097 this->Elements[csHashComputer<K>::ComputeHash (key) % this->Modulo];
00098
00099 size_t idx = 0;
00100 while (idx < values.GetSize())
00101 {
00102 if (!values[idx].GetKey())
00103 {
00104 break;
00105 }
00106 idx++;
00107 }
00108 if (idx >= values.GetSize())
00109 {
00110 values.Push (typename Superclass::Element (key, value));
00111 this->Size++;
00112 }
00113 if (values.GetSize () > this->Elements.GetSize () / this->GrowRate
00114 && this->Elements.GetSize () < this->MaxSize)
00115 {
00116 this->Grow ();
00117
00118
00119 return *(this->GetElementPointer (key));
00120 }
00121 return values[idx].GetValue();
00122 }
00123
00124 using Superclass::DeleteAll;
00125
00127 class GlobalIterator
00128 {
00129 private:
00130 typedef typename Superclass::GlobalIterator WrappedIterator;
00131 WrappedIterator iter;
00132
00133 bool haveNext;
00134 K key;
00135 T* value;
00136 protected:
00137 void NextElement ()
00138 {
00139 while (iter.HasNext ())
00140 {
00141 K key;
00142 value = &(iter.Next (key));
00143 if (key)
00144 {
00145 this->key = key;
00146 this->value = value;
00147 haveNext = true;
00148 break;
00149 }
00150
00151
00152 }
00153 haveNext = false;
00154 key = K ();
00155 }
00156
00157 GlobalIterator (const WrappedIterator& iter)
00158 : iter (iter)
00159 {
00160 NextElement ();
00161 }
00162
00163 friend class WeakKeyedHash<T, K, ArrayMemoryAlloc, ArrayElementHandler>;
00164 public:
00166 GlobalIterator (const GlobalIterator& o)
00167 : iter (o.iter), haveNext (o.haveNext), key (o.key), value (o.value) {}
00168
00170 GlobalIterator& operator=(const GlobalIterator& o)
00171 {
00172 iter = o.iter;
00173 haveNext = o.haveNext;
00174 key = o.key;
00175 value = o.value;
00176 return *this;
00177 }
00178
00180 bool HasNext () const
00181 {
00182 return haveNext;
00183 }
00184
00186 void Advance ()
00187 {
00188 NextElement ();
00189 }
00190
00192 T& NextNoAdvance ()
00193 {
00194 return *value;
00195 }
00196
00198 T& Next ()
00199 {
00200 T &ret = NextNoAdvance ();
00201 Advance ();
00202 return ret;
00203 }
00204
00206 T& NextNoAdvance (K &key)
00207 {
00208 key = this->key;
00209 return NextNoAdvance ();
00210 }
00211
00213 T& Next (K &key)
00214 {
00215 key = this->key;
00216 return Next ();
00217 }
00218
00220 const csTuple2<T, K> NextTuple ()
00221 {
00222 csTuple2<T, K> t (NextNoAdvance (),
00223 this->key);
00224 Advance ();
00225 return t;
00226 }
00227
00229 void Reset ()
00230 {
00231 iter->Reset ();
00232 NextElement ();
00233 }
00234 };
00235 friend class GlobalIterator;
00236
00242 GlobalIterator GetIterator ()
00243 {
00244 return GlobalIterator (Superclass::GetIterator ());
00245 }
00246
00247
00248 };
00249 }
00250 }
00251
00252 #endif // __CSUTIL_WEAKKEYEDHASH_H__