NGSolve
4.9
|
00001 #ifndef FILE_NGSTD_HASHTABLE 00002 #define FILE_NGSTD_HASHTABLE 00003 00004 /**************************************************************************/ 00005 /* File: hashtable.hpp */ 00006 /* Author: Joachim Schoeberl */ 00007 /* Date: 01. Jun. 95 */ 00008 /**************************************************************************/ 00009 00010 00011 namespace ngstd 00012 { 00013 00014 00016 template <int N> 00017 class INT 00018 { 00020 int i[N]; 00021 00022 public: 00024 INT () { } 00025 00027 INT (int ai1) 00028 { 00029 for (int j = 0; j < N; j++) { i[j] = ai1; } 00030 } 00031 00033 INT (int ai1, int ai2) 00034 { i[0] = ai1; i[1] = ai2; } 00035 00037 INT (int ai1, int ai2, int ai3) 00038 { i[0] = ai1; i[1] = ai2; i[2] = ai3; } 00039 00041 INT (int ai1, int ai2, int ai3, int ai4) 00042 { i[0] = ai1; i[1] = ai2; i[2] = ai3; i[3] = ai4; } 00043 00044 00046 INT (const INT & in2) 00047 { 00048 for (int j = 0; j < N; j++) 00049 i[j] = in2.i[j]; 00050 } 00051 00053 bool operator== (const INT & in2) const 00054 { 00055 for (int j = 0; j < N; j++) 00056 if (i[j] != in2.i[j]) return 0; 00057 return 1; 00058 } 00059 00061 void Sort () 00062 { 00063 for (int k = 0; k < N; k++) 00064 for (int l = k+1; l < N; l++) 00065 if (i[k] > i[l]) 00066 Swap (i[k], i[l]); 00067 } 00068 00070 int & operator[] (int j) 00071 { return i[j]; } 00072 00074 const int & operator[] (int j) const 00075 { return i[j]; } 00076 00077 void SetAll (int value) 00078 { 00079 for (int j = 0; j < N; j++) 00080 i[j] = value; 00081 } 00082 00083 INT<N> & operator= (int value) 00084 { 00085 for (int j = 0; j < N; j++) 00086 i[j] = value; 00087 return *this; 00088 } 00089 00090 INT<N> & operator= (INT<N> v2) 00091 { 00092 for (int j = 0; j < N; j++) 00093 i[j] = v2.i[j]; 00094 return *this; 00095 } 00096 }; 00097 00099 template <> 00100 inline void INT<2>::Sort () 00101 { 00102 if (i[0] > i[1]) swap (i[0], i[1]); 00103 } 00104 00106 template <> 00107 inline void INT<3>::Sort () 00108 { 00109 if (i[0] > i[1]) swap (i[0], i[1]); 00110 if (i[1] > i[2]) swap (i[1], i[2]); 00111 if (i[0] > i[1]) swap (i[0], i[1]); 00112 } 00113 00115 template <int N> 00116 inline ostream & operator<<(ostream & s, const INT<N> & i2) 00117 { 00118 for (int j = 0; j < N; j++) 00119 s << i2[j] << " "; 00120 return s; 00121 } 00122 00123 00124 template <int N> 00125 inline int HashValue (const INT<N> & ind, int size) 00126 { 00127 int sum = 0; 00128 for (int i = 0; i < N; i++) 00129 sum += ind[i]; 00130 return sum % size; 00131 } 00132 00134 inline int HashValue (const INT<1> & ind, int size) 00135 { 00136 return ind[0] % size; 00137 } 00138 00140 inline int HashValue (const INT<2> & ind, int size) 00141 { 00142 return (113*ind[0]+ind[1]) % size; 00143 } 00144 00146 inline int HashValue (const INT<3> & ind, int size) 00147 { 00148 return (113*ind[0]+59*ind[1]+ind[2]) % size; 00149 } 00150 00151 00152 // using ngstd::max; 00153 00154 template <int D> 00155 inline int Max (const INT<D> & i) 00156 { 00157 if (D == 0) return 0; 00158 int m = i[0]; 00159 for (int j = 1; j < D; j++) 00160 if (i[j] > m) m = i[j]; 00161 return m; 00162 } 00163 00164 00165 00166 00167 00168 00169 00170 00171 00172 00173 00174 00181 template <class T_HASH, class T> 00182 class HashTable 00183 { 00184 DynamicTable<T_HASH> hash; 00185 DynamicTable<T> cont; 00186 00187 public: 00189 HashTable (int size) 00190 : hash(size), cont(size) 00191 { 00192 ; 00193 } 00194 00196 void Set (const T_HASH & ahash, const T & acont) 00197 { 00198 int bnr = HashValue (ahash, hash.Size()); 00199 int pos = CheckPosition (bnr, ahash); 00200 if (pos != -1) 00201 cont.Set (bnr, pos, acont); 00202 else 00203 { 00204 hash.Add (bnr, ahash); 00205 cont.Add (bnr, acont); 00206 } 00207 } 00208 00210 const T & Get (const T_HASH & ahash) const 00211 { 00212 int bnr = HashValue (ahash, hash.Size()); 00213 int pos = Position (bnr, ahash); 00214 return cont.Get (bnr, pos); 00215 } 00216 00218 const T & Get (int bnr, int pos) const 00219 { 00220 return cont.Get (bnr, pos); 00221 } 00222 00224 bool Used (const T_HASH & ahash) const 00225 { 00226 return (CheckPosition (HashValue (ahash, hash.Size()), ahash) != -1) 00227 ? 1 : 0; 00228 } 00229 00231 bool Used (const T_HASH & ahash, int & bnr, int & pos) const 00232 { 00233 bnr = HashValue (ahash, hash.Size()); 00234 pos = CheckPosition (bnr, ahash); 00235 return (pos != -1); 00236 } 00237 00238 00240 int Size () const 00241 { 00242 return hash.Size(); 00243 } 00244 00246 int EntrySize (int bnr) const 00247 { 00248 return hash[bnr].Size(); 00249 } 00250 00252 void GetData (int bnr, int colnr, T_HASH & ahash, T & acont) 00253 { 00254 ahash = hash[bnr][colnr]; 00255 acont = cont[bnr][colnr]; 00256 } 00257 00259 void SetData (int bnr, int colnr, const T_HASH & ahash, const T & acont) 00260 { 00261 hash[bnr][colnr] = ahash; 00262 cont[bnr][colnr] = acont; 00263 } 00264 00266 int CheckPosition (int bnr, const T_HASH & ind) const 00267 { 00268 for (int i = 0; i < hash[bnr].Size(); i++) 00269 if (hash[bnr][i] == ind) 00270 return i; 00271 return -1; 00272 } 00273 00275 int Position (int bnr, const T_HASH & ind) const 00276 { 00277 for (int i = 0; i < hash[bnr].Size(); i++) 00278 if (hash[bnr][i] == ind) 00279 return i; 00280 throw Exception ("Ask for unsused hash-value"); 00281 } 00282 }; 00283 00284 00285 00286 00287 00288 00294 template <class T_HASH, class T> 00295 class ClosedHashTable 00296 { 00297 protected: 00299 int size; 00301 Array<T_HASH,size_t> hash; 00303 Array<T,size_t> cont; 00305 T_HASH invalid; 00306 public: 00308 ClosedHashTable (int asize) 00309 : size(asize), hash(asize), cont(asize) 00310 { 00311 // hash.SetName ("i2-hashtable, hash"); 00312 // cont.SetName ("i2-hashtable, contents"); 00313 invalid.SetAll (-1); 00314 for (int i = 0; i < size; i++) 00315 hash[i] = invalid; 00316 } 00317 00319 int Size() const 00320 { 00321 return size; 00322 } 00323 00325 bool UsedPos (int pos) const 00326 { 00327 return ! (hash[pos] == invalid); 00328 } 00329 00331 int UsedElements () const 00332 { 00333 int cnt = 0; 00334 for (int i = 0; i < size; i++) 00335 if (hash[i] != invalid) 00336 cnt++; 00337 return cnt; 00338 } 00339 00340 int Position (const T_HASH ind) const 00341 { 00342 int i = HashValue(ind, size); 00343 while (1) 00344 { 00345 if (hash[i] == ind) return i; 00346 if (hash[i] == invalid) return -1; 00347 i++; 00348 if (i >= size) i = 0; 00349 } 00350 } 00351 // returns 1, if new postion is created 00352 int PositionCreate (const T_HASH ind, int & apos) 00353 { 00354 int i = HashValue (ind, size); 00355 00356 while (1) 00357 { 00358 if (hash[i] == invalid) 00359 { 00360 hash[i] = ind; 00361 apos = i; 00362 return 1; 00363 } 00364 if (hash[i] == ind) 00365 { 00366 apos = i; 00367 return 0; 00368 } 00369 i++; 00370 if (i >= size) i = 0; 00371 } 00372 } 00373 00374 00376 void Set (const T_HASH & ahash, const T & acont) 00377 { 00378 int pos; 00379 PositionCreate (ahash, pos); 00380 hash[pos] = ahash; 00381 cont[pos] = acont; 00382 } 00384 const T & Get (const T_HASH & ahash) const 00385 { 00386 int pos = Position (ahash); 00387 return cont[pos]; 00388 } 00389 00391 bool Used (const T_HASH & ahash) const 00392 { 00393 int pos = Position (ahash); 00394 return (pos != -1); 00395 } 00396 00397 void SetData (int pos, const T_HASH & ahash, const T & acont) 00398 { 00399 hash[pos] = ahash; 00400 cont[pos] = acont; 00401 } 00402 00403 void GetData (int pos, T_HASH & ahash, T & acont) const 00404 { 00405 ahash = hash[pos]; 00406 acont = cont[pos]; 00407 } 00408 00409 void SetData (int pos, const T & acont) 00410 { 00411 cont[pos] = acont; 00412 } 00413 00414 void GetData (int pos, T & acont) const 00415 { 00416 acont = cont[pos]; 00417 } 00418 00419 void SetSize (int asize) 00420 { 00421 size = asize; 00422 hash.Alloc(size); 00423 cont.Alloc(size); 00424 for (int i = 0; i < size; i++) 00425 hash[i] = invalid; 00426 } 00427 00428 void SetName (const char * aname) 00429 { 00430 cont.SetName(aname); 00431 hash.SetName(aname); 00432 } 00433 }; 00434 00435 } 00436 00437 00438 #endif