modules/speller/default/vector_hash.hpp

   1 // Copyright (c) 2000
   2 // Kevin Atkinson
   3 //
   4 // Permission to use, copy, modify, distribute and sell this software
   5 // and its documentation for any purpose is hereby granted without
   6 // fee, provided that the above copyright notice appear in all copies
   7 // and that both that copyright notice and this permission notice
   8 // appear in supporting documentation. Kevin Atkinson makes no
   9 // representations about the suitability of this software for any
  10 // purpose.  It is provided "as is" without express or implied
  11 // warranty.
  12
  13 #ifndef __aspeller_vector_hash_hh__
  14 #define __aspeller_vector_hash_hh__
  15
  16 //#include <iterator>
  17 //#include <utility>
  18
  19 #include "settings.h"
  20 #undef REL_OPS_POLLUTION  // FIXME
  21
  22 namespace aspeller {
  23
  24   //
  25   // This hash table is implemnted as a Open Address Hash Table
  26   // which uses a Vector like object to store its data.  So
  27   // it might even be considered an adapter
  28   //
  29
  30   ////////////////////////////////////////////////////////
  31   //                                                    //
  32   //          Vector Hash Table Iterator               //
  33   //                                                    //
  34   ////////////////////////////////////////////////////////
  35   //
  36   // This is an internal object and should not be created
  37   // directly.  Instead use VectorHashTable::begin() and end()
  38
  39   template <class Parms>
  40   // Parms is expected to have:
  41   //  typename HashTable;
  42   //  typename TableIter;
  43   //  typename Value;
  44   class VHTIterator
  45   {
  46     template <class T>
  47     friend bool operator== (VHTIterator<T>, VHTIterator<T>);
  48 #ifndef REL_OPS_POLLUTION
  49     template <class T>
  50     friend bool operator!= (VHTIterator<T>, VHTIterator<T>);
  51 #endif
  52   public: //but don't use
  53     typedef typename Parms::TableIter       TableIter;
  54     typedef typename Parms::HashTable       HashTable;
  55     TableIter   pos;
  56     HashTable * hash_table;
  57   public:
  58     //typedef std::bidirectional_iterator_tag             iterator_category;
  59     typedef typename Parms::Value                       value_type;
  60     // these cause problems for SUNPRO_CC
  61     //typedef typename std::iterator_traits<TableIter>::difference_type difference_type;
  62     //typedef typename std::iterator_traits<TableIter>::pointer         pointer;
  63     //typedef typename std::iterator_traits<TableIter>::reference       reference;
  64
  65     //VHTIterator vector_iterator() const {return pos;}
  66   public:
  67     VHTIterator(TableIter p, HashTable *ht) : pos(p), hash_table(ht) {}
  68     VHTIterator(TableIter p, HashTable *ht, bool)
  69       : pos(p), hash_table(ht)
  70     {
  71       while (pos != hash_table->vector().end()
  72              && hash_table->parms().is_nonexistent(*pos) )
  73         ++pos;
  74     }
  75
  76     value_type & operator * () const  {return *pos;}
  77     value_type * operator -> () const {return &*pos;}
  78
  79     bool at_end() const {return pos == hash_table->vector().end();}
  80
  81     VHTIterator& operator++ () {
  82       ++pos;
  83       for (;;) {
  84         if (pos == hash_table->vector().end()) break;
  85         if (!hash_table->parms().is_nonexistent(*pos)) break;
  86         ++pos;
  87       }
  88       return *this;
  89     }
  90     VHTIterator operator++ (int) {
  91       VHTIterator temp = *this;
  92       operator++();
  93       return temp;
  94     }
  95
  96     VHTIterator& operator-- () {
  97       --pos;
  98       for (;;) {
  99         if (pos < hash_table->vector().begin()) break;
 100         if (!hash_table->parms().is_nonexistent_func(*pos)) break;
 101         --pos;
 102       }
 103       return *this;
 104     }
 105     VHTIterator operator-- (int) {
 106       VHTIterator temp = *this;
 107       operator--();
 108       return temp;
 109     }
 110   };
 111
 112   template <class Parms>
 113   inline
 114   bool operator== (VHTIterator<Parms> rhs, VHTIterator<Parms> lhs)
 115   {
 116     return rhs.pos == lhs.pos;
 117   }
 118
 119 #ifndef REL_OPS_POLLUTION
 120
 121   template <class Parms>
 122   inline
 123   bool operator!= (VHTIterator<Parms> rhs, VHTIterator<Parms> lhs)
 124   {
 125     return rhs.pos != lhs.pos;
 126   }
 127
 128 #endif
 129
 130   ////////////////////////////////////////////////////////
 131   //                                                    //
 132   //                Vector Hash Table                   //
 133   //                                                    //
 134   ////////////////////////////////////////////////////////
 135
 136   // Parms is expected to have the following methods
 137   //   typename Vector
 138   //   typedef Vector::value_type Value
 139   //   typedef Vector::size_type  Size
 140   //   typename Key
 141   //   bool is_multi;
 142   //   Size hash(Key)
 143   //   bool equal(Key, Key)
 144   //   Key key(Value)
 145   //   bool is_nonexistent(Value)
 146   //   void make_nonexistent(Value &)
 147
 148   template <class Parms>
 149   class VectorHashTable {
 150     typedef typename Parms::Vector           Vector;
 151   public:
 152     typedef typename Parms::Vector           vector_type;
 153     typedef typename Vector::value_type      value_type;
 154     typedef typename Vector::size_type       size_type;
 155     typedef typename Vector::difference_type difference_type;
 156
 157     typedef typename Vector::pointer         pointer;
 158     typedef typename Vector::reference       reference;
 159     typedef typename Vector::const_reference const_reference;
 160
 161     typedef typename Parms::Key              key_type;
 162   public: // but don't use
 163     typedef VectorHashTable<Parms>           HashTable;
 164   private:
 165     Parms parms_;
 166
 167   public:
 168     typedef Parms parms_type;
 169     const parms_type & parms() const {return parms_;}
 170
 171   public:
 172     // These public functions are very dangerous and should be used with
 173     // great care as the modify the internal structure of the object
 174     Vector & vector()       {return vector_;}
 175     const Vector & vector() const {return vector_;}
 176     parms_type & parms() {return parms_;}
 177     void recalc_size();
 178     void set_size(size_type s) {size_  = s;}
 179
 180   private:
 181     Vector      vector_;
 182     size_type   size_;
 183
 184   public: // but don't use
 185     typedef typename Vector::iterator       vector_iterator;
 186     typedef typename Vector::const_iterator const_vector_iterator;
 187
 188   private:
 189     int hash1(const key_type &d) const {
 190       return parms_.hash(d) % bucket_count();
 191     }
 192     int hash2(const key_type &d) const {
 193       return 1 + (parms_.hash(d) % (bucket_count() - 2));
 194     }
 195
 196     struct NonConstParms {
 197       typedef VectorHashTable HashTable;
 198       typedef vector_iterator TableIter;
 199       typedef value_type      Value;
 200     };
 201     struct ConstParms {
 202       typedef const VectorHashTable HashTable;
 203       typedef const_vector_iterator TableIter;
 204       typedef const value_type      Value;
 205     };
 206   public:
 207     typedef VHTIterator<NonConstParms> iterator;
 208     typedef VHTIterator<ConstParms>    const_iterator;
 209
 210   private:
 211     void nonexistent_vector();
 212
 213   public:
 214     VectorHashTable(size_type i, const Parms & p = Parms());
 215
 216     VectorHashTable(const Parms & p = Parms())
 217       : parms_(p), vector_(19), size_(0) {nonexistent_vector();}
 218
 219     iterator begin() {return iterator(vector_.begin(), this, 1);}
 220     iterator end()   {return iterator(vector_.end(), this);}
 221     const_iterator begin() const {return const_iterator(vector_.begin(), this, 1);}
 222     const_iterator end()   const {return const_iterator(vector_.end(), this);}
 223
 224     std::pair<iterator, bool> insert(const value_type &);
 225     bool have(const key_type &) const;
 226
 227     iterator find(const key_type&);
 228     const_iterator find(const key_type&) const;
 229
 230     size_type erase(const key_type &key);
 231     void erase(const iterator &p);
 232
 233     size_type size() const {return size_;}
 234     bool      empty() const {return !size_;}
 235
 236     void swap(VectorHashTable &);
 237     void resize(size_type);
 238     size_type bucket_count() const {return vector_.size();}
 239     double load_factor() const {return static_cast<double>(size())/bucket_count();}
 240
 241   private:
 242     class FindIterator
 243     {
 244     public: // but don't use
 245       const vector_type * vector;
 246       const Parms       * parms;
 247       key_type key;
 248       int i;
 249       int hash2;
 250       FindIterator() {}
 251       FindIterator(const HashTable * ht, const key_type & k);
 252     public:
 253       bool at_end() const {return parms->is_nonexistent((*vector)[i]);}
 254       void adv();
 255       FindIterator & operator ++() {adv(); return *this;}
 256     };
 257     friend class FindIterator;
 258
 259   public:
 260     class ConstFindIterator : public FindIterator
 261     {
 262     public:
 263       ConstFindIterator() {}
 264       ConstFindIterator(const HashTable * ht, const key_type & k)
 265         : FindIterator(ht,k) {}
 266       const value_type & deref() const {return (*this->vector)[this->i];}
 267     };
 268
 269     class MutableFindIterator : public FindIterator
 270     {
 271     public:
 272       MutableFindIterator() {}
 273       MutableFindIterator(HashTable * ht, const key_type & k)
 274         : FindIterator(ht,k) {}
 275       value_type & deref() const {
 276         return (*const_cast<vector_type *>(this->vector))[this->i];
 277       }
 278     };
 279
 280     ConstFindIterator multi_find(const key_type & k) const {
 281       return ConstFindIterator(this, k);
 282     }
 283
 284     MutableFindIterator multi_find(const key_type & k) {
 285       return MutableFindIterator(this, k);
 286     }
 287
 288   };
 289 }
 290
 291 #endif