NGSolve
5.3
|
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, typename T = int> 00017 class INT 00018 { 00020 T i[(N>0)?N:1]; 00021 00022 public: 00024 INLINE INT () { } 00025 00027 INLINE INT (T ai1) 00028 { 00029 for (int j = 0; j < N; j++) { i[j] = ai1; } 00030 } 00031 00033 INLINE INT (T ai1, T ai2) 00034 { i[0] = ai1; i[1] = ai2; } 00035 00037 INLINE INT (T ai1, T ai2, T ai3) 00038 { i[0] = ai1; i[1] = ai2; i[2] = ai3; } 00039 00041 INLINE INT (T ai1, T ai2, T ai3, T ai4) 00042 { i[0] = ai1; i[1] = ai2; i[2] = ai3; i[3] = ai4; } 00043 00044 template <int N2, typename T2> 00045 INLINE INT (const INT<N2,T2> & in2) 00046 { 00047 if (N2 <= N) 00048 { 00049 for (int j = 0; j < N2; j++) 00050 i[j] = in2[j]; 00051 for (int j = N2; j < N; j++) 00052 i[j] = 0; 00053 } 00054 else 00055 { 00056 for (int j = 0; j < N; j++) 00057 i[j] = in2[j]; 00058 } 00059 } 00060 00062 INLINE bool operator== (const INT & in2) const 00063 { 00064 for (int j = 0; j < N; j++) 00065 if (i[j] != in2.i[j]) return 0; 00066 return 1; 00067 } 00068 00070 INLINE void Sort () 00071 { 00072 for (int k = 0; k < N; k++) 00073 for (int l = k+1; l < N; l++) 00074 if (i[k] > i[l]) 00075 Swap (i[k], i[l]); 00076 } 00077 00079 INLINE T & operator[] (int j) 00080 { return i[j]; } 00081 00083 INLINE const T & operator[] (int j) const 00084 { return i[j]; } 00085 00086 /* 00087 INLINE void SetAll (T value) 00088 { 00089 for (int j = 0; j < N; j++) 00090 i[j] = value; 00091 } 00092 */ 00093 00094 INLINE INT<N,T> & operator= (T value) 00095 { 00096 for (int j = 0; j < N; j++) 00097 i[j] = value; 00098 return *this; 00099 } 00100 00101 template <typename T2> 00102 INLINE INT<N,T> & operator= (INT<N,T2> v2) 00103 { 00104 for (int j = 0; j < N; j++) 00105 i[j] = v2[j]; 00106 return *this; 00107 } 00108 }; 00109 00111 template <> 00112 INLINE void INT<2>::Sort () 00113 { 00114 if (i[0] > i[1]) Swap (i[0], i[1]); 00115 } 00116 00118 template <> 00119 INLINE void INT<3>::Sort () 00120 { 00121 if (i[0] > i[1]) Swap (i[0], i[1]); 00122 if (i[1] > i[2]) Swap (i[1], i[2]); 00123 if (i[0] > i[1]) Swap (i[0], i[1]); 00124 } 00125 00127 template <int N, typename T> 00128 inline ostream & operator<<(ostream & s, const INT<N,T> & i2) 00129 { 00130 for (int j = 0; j < N; j++) 00131 s << i2[j] << " "; 00132 return s; 00133 } 00134 00135 00136 template <int N> 00137 INLINE int HashValue (const INT<N> & ind, int size) 00138 { 00139 int sum = 0; 00140 for (int i = 0; i < N; i++) 00141 sum += ind[i]; 00142 return sum % size; 00143 } 00144 00146 INLINE int HashValue (const INT<1> & ind, int size) 00147 { 00148 return ind[0] % size; 00149 } 00150 00152 INLINE int HashValue (const INT<2> & ind, int size) 00153 { 00154 return (113*ind[0]+ind[1]) % size; 00155 } 00156 00158 INLINE int HashValue (const INT<3> & ind, int size) 00159 { 00160 return (113*ind[0]+59*ind[1]+ind[2]) % size; 00161 } 00162 00163 00164 // using ngstd::max; 00165 00166 template <int D, typename T> 00167 INLINE T Max (const INT<D,T> & i) 00168 { 00169 if (D == 0) return 0; 00170 T m = i[0]; 00171 for (int j = 1; j < D; j++) 00172 if (i[j] > m) m = i[j]; 00173 return m; 00174 } 00175 00176 template <int D, typename T> 00177 INLINE T Min (const INT<D,T> & i) 00178 { 00179 if (D == 0) return 0; 00180 T m = i[0]; 00181 for (int j = 1; j < D; j++) 00182 if (i[j] < m) m = i[j]; 00183 return m; 00184 } 00185 00186 template <int D, typename T> 00187 INLINE INT<D,T> Max (INT<D,T> i1, INT<D,T> i2) 00188 { 00189 INT<D,T> tmp; 00190 for (int i = 0; i < D; i++) 00191 tmp[i] = max2(i1[i], i2[i]); 00192 return tmp; 00193 } 00194 00195 template <int D, typename T> 00196 INLINE INT<D,T> operator+ (INT<D,T> i1, INT<D,T> i2) 00197 { 00198 INT<D,T> tmp; 00199 for (int i = 0; i < D; i++) 00200 tmp[i] = i1[i]+i2[i]; 00201 return tmp; 00202 } 00203 00204 00205 00206 00207 00208 00209 00210 00211 00212 00213 00220 template <class T_HASH, class T> 00221 class HashTable 00222 { 00223 DynamicTable<T_HASH> hash; 00224 DynamicTable<T> cont; 00225 00226 public: 00228 INLINE HashTable (int size) 00229 : hash(size), cont(size) 00230 { ; } 00231 INLINE ~HashTable () { ; } 00232 00234 void Set (const T_HASH & ahash, const T & acont) 00235 { 00236 int bnr = HashValue (ahash, hash.Size()); 00237 int pos = CheckPosition (bnr, ahash); 00238 if (pos != -1) 00239 cont.Set (bnr, pos, acont); 00240 else 00241 { 00242 hash.Add (bnr, ahash); 00243 cont.Add (bnr, acont); 00244 } 00245 } 00246 00248 const T & Get (const T_HASH & ahash) const 00249 { 00250 int bnr = HashValue (ahash, hash.Size()); 00251 int pos = Position (bnr, ahash); 00252 return cont.Get (bnr, pos); 00253 } 00254 00256 const T & Get (int bnr, int pos) const 00257 { 00258 return cont.Get (bnr, pos); 00259 } 00260 00262 bool Used (const T_HASH & ahash) const 00263 { 00264 return (CheckPosition (HashValue (ahash, hash.Size()), ahash) != -1); 00265 } 00266 00268 bool Used (const T_HASH & ahash, int & bnr, int & pos) const 00269 { 00270 bnr = HashValue (ahash, hash.Size()); 00271 pos = CheckPosition (bnr, ahash); 00272 return (pos != -1); 00273 } 00274 00275 00277 int Size () const 00278 { 00279 return hash.Size(); 00280 } 00281 00283 int EntrySize (int bnr) const 00284 { 00285 return hash[bnr].Size(); 00286 } 00287 00289 void GetData (int bnr, int colnr, T_HASH & ahash, T & acont) const 00290 { 00291 ahash = hash[bnr][colnr]; 00292 acont = cont[bnr][colnr]; 00293 } 00294 00296 void SetData (int bnr, int colnr, const T_HASH & ahash, const T & acont) 00297 { 00298 hash[bnr][colnr] = ahash; 00299 cont[bnr][colnr] = acont; 00300 } 00301 00303 int CheckPosition (int bnr, const T_HASH & ind) const 00304 { 00305 for (int i = 0; i < hash[bnr].Size(); i++) 00306 if (hash[bnr][i] == ind) 00307 return i; 00308 return -1; 00309 } 00310 00312 int Position (int bnr, const T_HASH & ind) const 00313 { 00314 for (int i = 0; i < hash[bnr].Size(); i++) 00315 if (hash[bnr][i] == ind) 00316 return i; 00317 throw Exception ("Ask for unsused hash-value"); 00318 } 00319 00320 T & operator[] (T_HASH ahash) 00321 { 00322 int bnr, pos; 00323 if (Used (ahash, bnr, pos)) 00324 return cont[bnr][pos]; 00325 else 00326 { 00327 hash.Add (bnr, ahash); 00328 cont.Add (bnr, T(0)); 00329 return cont[bnr][cont[bnr].Size()-1]; 00330 } 00331 } 00332 00333 class Iterator 00334 { 00335 const HashTable & ht; 00336 int bnr; 00337 int pos; 00338 public: 00339 Iterator (const HashTable & aht, int abnr, int apos) 00340 : ht(aht), bnr(abnr), pos(apos) { ; } 00341 pair<T_HASH,T> operator* () const 00342 { 00343 T_HASH hash; 00344 T data; 00345 ht.GetData (bnr, pos, hash, data); 00346 return pair<T_HASH,T> (hash, data); 00347 } 00348 00349 Iterator & operator++() 00350 { 00351 pos++; 00352 if (pos == ht.EntrySize(bnr)) 00353 { 00354 pos = 0; 00355 bnr++; 00356 for ( ; bnr < ht.Size(); bnr++) 00357 if (ht.EntrySize(bnr) != 0) break; 00358 } 00359 return *this; 00360 } 00361 00362 bool operator!= (const Iterator & it2) { return bnr != it2.bnr || pos != it2.pos; } 00363 }; 00364 00365 Iterator begin () const 00366 { 00367 int i = 0; 00368 for ( ; i < Size(); i++) 00369 if (EntrySize(i) != 0) break; 00370 return Iterator(*this, i,0); 00371 } 00372 Iterator end () const { return Iterator(*this, Size(),0); } 00373 }; 00374 00375 00376 00377 00378 00379 00385 template <class T_HASH, class T> 00386 class ClosedHashTable 00387 { 00388 protected: 00390 int size; 00392 Array<T_HASH,size_t> hash; 00394 Array<T,size_t> cont; 00396 T_HASH invalid; 00397 public: 00399 ClosedHashTable (int asize) 00400 : size(asize), hash(asize), cont(asize) 00401 { 00402 // hash.SetName ("i2-hashtable, hash"); 00403 // cont.SetName ("i2-hashtable, contents"); 00404 invalid = -1; // .SetAll (-1); 00405 for (int i = 0; i < size; i++) 00406 hash[i] = invalid; 00407 } 00408 00410 int Size() const 00411 { 00412 return size; 00413 } 00414 00416 bool UsedPos (int pos) const 00417 { 00418 return ! (hash[pos] == invalid); 00419 } 00420 00422 int UsedElements () const 00423 { 00424 int cnt = 0; 00425 for (int i = 0; i < size; i++) 00426 if (hash[i] != invalid) 00427 cnt++; 00428 return cnt; 00429 } 00430 00431 int Position (const T_HASH ind) const 00432 { 00433 int i = HashValue(ind, size); 00434 while (1) 00435 { 00436 if (hash[i] == ind) return i; 00437 if (hash[i] == invalid) return -1; 00438 i++; 00439 if (i >= size) i = 0; 00440 } 00441 } 00442 // returns 1, if new postion is created 00443 int PositionCreate (const T_HASH ind, int & apos) 00444 { 00445 int i = HashValue (ind, size); 00446 00447 while (1) 00448 { 00449 if (hash[i] == invalid) 00450 { 00451 hash[i] = ind; 00452 apos = i; 00453 return 1; 00454 } 00455 if (hash[i] == ind) 00456 { 00457 apos = i; 00458 return 0; 00459 } 00460 i++; 00461 if (i >= size) i = 0; 00462 } 00463 } 00464 00465 00467 void Set (const T_HASH & ahash, const T & acont) 00468 { 00469 int pos; 00470 PositionCreate (ahash, pos); 00471 hash[pos] = ahash; 00472 cont[pos] = acont; 00473 } 00475 const T & Get (const T_HASH & ahash) const 00476 { 00477 int pos = Position (ahash); 00478 return cont[pos]; 00479 } 00480 00482 bool Used (const T_HASH & ahash) const 00483 { 00484 int pos = Position (ahash); 00485 return (pos != -1); 00486 } 00487 00488 void SetData (int pos, const T_HASH & ahash, const T & acont) 00489 { 00490 hash[pos] = ahash; 00491 cont[pos] = acont; 00492 } 00493 00494 void GetData (int pos, T_HASH & ahash, T & acont) const 00495 { 00496 ahash = hash[pos]; 00497 acont = cont[pos]; 00498 } 00499 00500 void SetData (int pos, const T & acont) 00501 { 00502 cont[pos] = acont; 00503 } 00504 00505 void GetData (int pos, T & acont) const 00506 { 00507 acont = cont[pos]; 00508 } 00509 00510 void SetSize (int asize) 00511 { 00512 size = asize; 00513 hash.Alloc(size); 00514 cont.Alloc(size); 00515 for (int i = 0; i < size; i++) 00516 hash[i] = invalid; 00517 } 00518 00519 void SetName (const char * aname) 00520 { 00521 cont.SetName(aname); 00522 hash.SetName(aname); 00523 } 00524 }; 00525 00526 00527 00528 00529 00530 00531 00532 00533 template <int N, typename T> 00534 Archive & operator & (Archive & archive, INT<N,T> & mi) 00535 { 00536 for (int i = 0; i < N; i++) 00537 archive & mi[i]; 00538 return archive; 00539 } 00540 } 00541 00542 #endif