NGSolve  5.3
ngstd/hashtable.hpp
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