Dogcows Code - chaz/yoink/blob - src/stlplus/containers/hash.hpp

   1 #ifndef STLPLUS_HASH
   2 #define STLPLUS_HASH
   3 ////////////////////////////////////////////////////////////////////////////////
   4
   5 //   Author:    Andy Rushton
   6 //   Copyright: (c) Southampton University 1999-2004
   7 //              (c) Andy Rushton           2004-2009
   8 //   License:   BSD License, see ../docs/license.html
   9
  10 //   A chained hash table using STL semantics
  11
  12 ////////////////////////////////////////////////////////////////////////////////
  13 #include "containers_fixes.hpp"
  14 #include "exceptions.hpp"
  15 #include "safe_iterator.hpp"
  16 #include <map>
  17 #include <iostream>
  18
  19 namespace stlplus
  20 {
  21
  22   ////////////////////////////////////////////////////////////////////////////////
  23   // internals
  24
  25   template<typename K, typename T, class H, class E> class hash;
  26   template<typename K, typename T, class H, class E> class hash_element;
  27
  28   ////////////////////////////////////////////////////////////////////////////////
  29   // iterator class
  30
  31   template<typename K, typename T, class H, class E, typename V>
  32   class hash_iterator : public safe_iterator<hash<K,T,H,E>,hash_element<K,T,H,E> >
  33   {
  34   public:
  35     friend class hash<K,T,H,E>;
  36
  37     // local type definitions
  38     // an iterator points to a value whilst a const_iterator points to a const value
  39     typedef V                                                  value_type;
  40     typedef hash_iterator<K,T,H,E,std::pair<const K,T> >       iterator;
  41     typedef hash_iterator<K,T,H,E,const std::pair<const K,T> > const_iterator;
  42     typedef hash_iterator<K,T,H,E,V>                           this_iterator;
  43     typedef V&                                                 reference;
  44     typedef V*                                                 pointer;
  45
  46     // constructor to create a null iterator - you must assign a valid value to this iterator before using it
  47     // any attempt to dereference or use a null iterator is an error
  48     // the only valid thing you can do is assign an iterator to it
  49     hash_iterator(void);
  50     ~hash_iterator(void);
  51
  52     // Type conversion methods allow const_iterator and iterator to be converted
  53     // convert an iterator/const_iterator to a const_iterator
  54     const_iterator constify(void) const;
  55     // convert an iterator/const_iterator to an iterator
  56     iterator deconstify(void) const;
  57
  58     // increment operators used to step through the set of all values in a hash
  59     // it is only legal to increment a valid iterator
  60     // there's no decrement - I've only implemented this as a unidirectional iterator
  61     // pre-increment
  62     this_iterator& operator ++ (void)
  63       throw(null_dereference,end_dereference);
  64     // post-increment
  65     this_iterator operator ++ (int)
  66       throw(null_dereference,end_dereference);
  67
  68     // test useful for testing whether iteration has completed
  69     bool operator == (const this_iterator& r) const;
  70     bool operator != (const this_iterator& r) const;
  71     bool operator < (const this_iterator& r) const;
  72
  73     // access the value - a const_iterator gives you a const value, an iterator a non-const value
  74     // it is illegal to dereference an invalid (i.e. null or end) iterator
  75     reference operator*(void) const
  76       throw(null_dereference,end_dereference);
  77     pointer operator->(void) const
  78       throw(null_dereference,end_dereference);
  79
  80   private:
  81     friend class hash_element<K,T,H,E>;
  82
  83     // constructor used by hash to create a non-null iterator
  84     // you cannot create a valid iterator except by calling a hash method that returns one
  85     explicit hash_iterator(hash_element<K,T,H,E>* element);
  86     // constructor used to create an end iterator
  87     explicit hash_iterator(const hash<K,T,H,E>* owner);
  88     // used to create an alias of an iterator
  89     explicit hash_iterator(const safe_iterator<hash<K,T,H,E>, hash_element<K,T,H,E> >& iterator);
  90   };
  91
  92   ////////////////////////////////////////////////////////////////////////////////
  93   // Hash class
  94   // K = key type
  95   // T = value type
  96   // H = hash function object with the profile 'unsigned H(const K&)'
  97   // E = equal function object with profile 'bool E(const K&, const K&)' defaults to equal_to which in turn calls '=='
  98
  99   template<typename K, typename T, class H, class E = std::equal_to<K> >
 100   class hash
 101   {
 102   public:
 103     typedef unsigned                                size_type;
 104     typedef K                                       key_type;
 105     typedef T                                       data_type;
 106     typedef T                                       mapped_type;
 107     typedef std::pair<const K, T>                   value_type;
 108     typedef hash_iterator<K,T,H,E,value_type>       iterator;
 109     typedef hash_iterator<K,T,H,E,const value_type> const_iterator;
 110
 111     // construct a hash table with specified number of bins
 112     // the default 0 bins means leave it to the table to decide
 113     // specifying 0 bins also enables auto-rehashing, otherwise auto-rehashing defaults off
 114     hash(unsigned bins = 0);
 115     ~hash(void);
 116
 117     // copy and equality copy the data elements but not the size of the copied table
 118     hash(const hash&);
 119     hash& operator = (const hash&);
 120
 121     // test for an empty table and for the size of a table
 122     // efficient because the size is stored separately from the table contents
 123     bool empty(void) const;
 124     unsigned size(void) const;
 125
 126     // test for equality - two hashes are equal if they contain equal values
 127     bool operator == (const hash&) const;
 128     bool operator != (const hash&) const;
 129
 130     // switch auto-rehash on
 131     void auto_rehash(void);
 132     // switch auto-rehash off
 133     void manual_rehash(void);
 134     // force a rehash now
 135     // default of 0 means implement built-in size calculation for rehashing (recommended - it doubles the number of bins)
 136     void rehash(unsigned bins = 0);
 137     // test the loading ratio, which is the size divided by the number of bins
 138     // use this if you are doing your own rehashing
 139     // the recommendation is to double the bins when the loading exceeds 0.5 which is what auto-rehashing does
 140     float loading(void) const;
 141
 142     // test for the presence of a key
 143     bool present(const K& key) const;
 144     // provide map equivalent key count function (0 or 1, as not a multimap)
 145     size_type count(const K& key) const;
 146
 147     // insert a new key/data pair - replaces any previous value for this key
 148     iterator insert(const K& key, const T& data);
 149     // insert a copy of the pair into the table (std::map compatible)
 150     std::pair<iterator, bool> insert(const value_type& value);
 151     // insert a new key and return the iterator so that the data can be filled in
 152     iterator insert(const K& key);
 153
 154     // remove a key/data pair from the hash table
 155     // as in map, this returns the number of elements erased
 156     size_type erase(const K& key);
 157     // remove an element from the hash table using an iterator
 158     // as in map, returns an iterator to the next element
 159     iterator erase(iterator it);
 160     // remove all elements from the hash table
 161     void erase(void);
 162     // map equivalent of above
 163     void clear(void);
 164
 165     // find a key and return an iterator to it
 166     // The iterator is like a pointer to a pair<const K,T>
 167     // end() is returned if the find fails
 168     const_iterator find(const K& key) const;
 169     iterator find(const K& key);
 170
 171     // returns the data corresponding to the key
 172     // const version is used for const hashes and cannot change the hash, so failure causes an exception
 173     // non-const version is for non-const hashes and is like map - it creates a new key/data pair if find fails
 174     const T& operator[] (const K& key) const throw(std::out_of_range);
 175     T& operator[] (const K& key);
 176
 177     // iterators allow the hash table to be traversed
 178     // iterators remain valid unless an item is removed or unless a rehash happens
 179     const_iterator begin(void) const;
 180     iterator begin(void);
 181     const_iterator end(void) const;
 182     iterator end(void);
 183
 184     // diagnostic report shows the number of items in each bin so can be used
 185     // to diagnose effectiveness of hash functions
 186     void debug_report(std::ostream&) const;
 187
 188     // internals
 189   private:
 190     friend class hash_element<K,T,H,E>;
 191     friend class hash_iterator<K,T,H,E,std::pair<const K,T> >;
 192     friend class hash_iterator<K,T,H,E,const std::pair<const K,T> >;
 193
 194     unsigned m_rehash;
 195     unsigned m_bins;
 196     unsigned m_size;
 197     hash_element<K,T,H,E>** m_values;
 198   };
 199
 200   ////////////////////////////////////////////////////////////////////////////////
 201
 202 } // end namespace stlplus
 203
 204 #include "hash.tpp"
 205 #endif