NGSolve  4.9
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>
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