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