Remove 'level' argument of normal().
[ginac.git] / ginac / hash_map.h
1 /** @file hash_map.h
2  *
3  *  Replacement for map<> using hash tables. */
4
5 /*
6  *  GiNaC Copyright (C) 1999-2016 Johannes Gutenberg University Mainz, Germany
7  *
8  *  This program is free software; you can redistribute it and/or modify
9  *  it under the terms of the GNU General Public License as published by
10  *  the Free Software Foundation; either version 2 of the License, or
11  *  (at your option) any later version.
12  *
13  *  This program is distributed in the hope that it will be useful,
14  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
15  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16  *  GNU General Public License for more details.
17  *
18  *  You should have received a copy of the GNU General Public License
19  *  along with this program; if not, write to the Free Software
20  *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
21  */
22
23 #ifndef GINAC_HASH_MAP_H
24 #define GINAC_HASH_MAP_H
25
26 #include <algorithm>
27 #include <functional>
28 #include <iterator>
29 #include <list>
30 #include <utility>
31
32 namespace GiNaC {
33
34 /*
35  *  "Hashmap Light" - buckets only contain one value, quadratic probing,
36  *  grows automatically
37  */
38
39 namespace internal {
40
41 // List of prime numbers shamelessly stolen from GCC STL
42 enum { num_primes = 29 };
43
44 static const unsigned long prime_list[num_primes] =
45 {
46         31ul,        53ul,         97ul,         193ul,       389ul,
47         769ul,       1543ul,       3079ul,       6151ul,      12289ul,
48         24593ul,     49157ul,      98317ul,      196613ul,    393241ul,
49         786433ul,    1572869ul,    3145739ul,    6291469ul,   12582917ul,
50         25165843ul,  50331653ul,   100663319ul,  201326611ul, 402653189ul,
51         805306457ul, 1610612741ul, 3221225473ul, 4294967291ul
52 };
53
54 inline unsigned long next_prime(unsigned long n)
55 {
56         const unsigned long *first = prime_list;
57         const unsigned long *last = prime_list + num_primes;
58         const unsigned long *pos = std::lower_bound(first, last, n);
59         return pos == last ? *(last - 1) : *pos;
60 }
61
62 } // namespace internal
63
64
65 // Define default arguments
66 template <typename T, template <class> class A = std::allocator>
67 class exhashmap;
68
69
70 /** Pair Associative Container with 'ex' objects as keys, that is implemented
71  *  with a hash table and can be used as a replacement for map<> in many cases.
72  *
73  *  Differences to map<>:
74  *   - no lower_bound()/upper_bound()
75  *   - no reverse iterators, no rbegin()/rend()
76  *   - no operator<()
77  *   - comparison functor is hardcoded to ex_is_less
78  *   - bucket_count() returns the number of buckets allocated in the hash table
79  *   - insert() and erase() invalidate all iterators
80  *   - average complexity of find() is constant time, worst case is O(n) */
81 template <typename T, template <class> class A>
82 class exhashmap {
83 public:
84         static const unsigned min_num_buckets = 31; // must be prime
85
86         // Standard types
87         typedef ex key_type;
88         typedef T mapped_type;
89         typedef std::pair<key_type, T> value_type;
90         typedef ex_is_less key_compare;
91         typedef ex_is_equal key_equal;
92         typedef value_type & reference;
93         typedef const value_type & const_reference;
94         typedef value_type * pointer;
95         typedef const value_type * const_pointer;
96
97 protected:
98         // Private types
99         enum bucket_state {
100                 EMPTY,  ///< bucket empty (never used)
101                 USED,   ///< bucket in use
102                 ERASED  ///< bucket empty (element deleted), but may be part of a search chain
103         };
104         typedef std::pair<bucket_state, value_type> Bucket;
105
106 public:
107         // More standard types
108         typedef A<Bucket> allocator_type;
109
110 protected:
111         // More private types
112         typedef std::vector<Bucket, allocator_type> Table;
113
114         typedef typename Table::iterator table_iterator;
115         typedef typename Table::const_iterator table_const_iterator;
116
117 public:
118         // Iterators
119         template <typename Pointer, typename Reference, class TableIterator>
120         class exhashmap_iterator : public std::iterator<std::forward_iterator_tag, value_type, typename Table::difference_type, Pointer, Reference> {
121         protected:
122                 friend class exhashmap;
123
124         public:
125                 exhashmap_iterator() {}
126                 exhashmap_iterator(TableIterator t, TableIterator te)
127                  : it(t), table_end(te) {}
128
129                 // Allow iterator to const_iterator conversion
130                 template <typename P, typename R, class TI>
131                 exhashmap_iterator(const exhashmap_iterator<P, R, TI> &other)
132                  : it(other.get_it_()), table_end(other.get_table_end_()) {}
133
134                 typename exhashmap_iterator::reference operator*() const
135                 {
136                         return it->second;
137                 }
138
139                 typename exhashmap_iterator::pointer operator->() const
140                 {
141                         return &(it->second);
142                 }
143
144                 exhashmap_iterator &operator++()
145                 {
146                         increment();
147                         return *this;
148                 }
149
150                 exhashmap_iterator operator++(int)
151                 {
152                         exhashmap_iterator tmp = *this;
153                         increment();
154                         return tmp;
155                 }
156
157                 template <typename P, typename R, class TI>
158                 bool operator==(const exhashmap_iterator<P, R, TI> &other) const
159                 {
160                         return it == other.get_it_();
161                 }
162
163                 template <typename P, typename R, class TI>
164                 bool operator!=(const exhashmap_iterator<P, R, TI> &other) const
165                 {
166                         return it != other.get_it_();
167                 }
168
169                 // Private access function
170                 TableIterator get_it_() const { return it; }
171                 TableIterator get_table_end_() const { return table_end; }
172
173         protected:
174                 TableIterator it;        ///< Pointer to current bucket
175                 TableIterator table_end; ///< Pointer to one-past-last bucket
176
177                 void increment()
178                 {
179                         if (it != table_end)
180                                 ++it;
181
182                         // Skip empty and erased buckets
183                         while (it != table_end && it->first != USED)
184                                 ++it;
185                 }
186         };
187
188         typedef exhashmap_iterator<value_type*, value_type&, table_iterator> iterator;
189         typedef exhashmap_iterator<const value_type*, const value_type&, table_const_iterator> const_iterator;
190
191         // More standard types
192         typedef typename Table::size_type size_type;
193         typedef typename Table::difference_type difference_type;
194
195         class value_compare : public std::binary_function<value_type, value_type, bool>, private key_compare {
196                 friend class exhashmap;
197         public:
198                 bool operator()(const value_type &lhs, const value_type &rhs) const
199                 {
200                         return key_compare::operator()(lhs.first, rhs.first);
201                 }
202
203                 bool operator()(const key_type &lhs, const value_type &rhs) const
204                 {
205                         return key_compare::operator()(lhs, rhs.first);
206                 }
207
208                 bool operator()(const value_type &lhs, const key_type &rhs) const
209                 {
210                         return key_compare::operator()(lhs.first, rhs);
211                 }
212         };
213
214 protected:
215         // Private data
216         size_type num_entries; ///< Number of values stored in container (cached for faster operation of size())
217         size_type num_buckets; ///< Number of buckets (= hashtab.size())
218         Table hashtab;         ///< Vector of buckets, each bucket is kept sorted
219
220         /** Return index of key in hash table. */
221         static size_type hash_index(const key_type &x, size_type nbuckets)
222         {
223                 return x.gethash() % nbuckets;
224         }
225
226         static table_iterator find_bucket(const key_type &x, table_iterator tab, size_type nbuckets);
227         static table_const_iterator find_bucket(const key_type &x, table_const_iterator tab, size_type nbuckets);
228         static table_iterator find_bucket_for_insertion(const key_type &x, table_iterator tab, size_type nbuckets);
229
230         /** Return pointer to bucket corresponding to key (or first empty bucket). */
231         table_iterator find_bucket(const key_type &x)
232         {
233                 return find_bucket(x, hashtab.begin(), num_buckets);
234         }
235
236         /** Return pointer to bucket corresponding to key (or first empty bucket). */
237         table_const_iterator find_bucket(const key_type &x) const
238         {
239                 return find_bucket(x, hashtab.begin(), num_buckets);
240         }
241
242         /** Return pointer to bucket corresponding to key (or first empty or erased bucket). */
243         table_iterator find_bucket_for_insertion(const key_type &x)
244         {
245                 return find_bucket_for_insertion(x, hashtab.begin(), num_buckets);
246         }
247
248         /** Return number of entries above which the table will grow. */
249         size_type hwm() const
250         {
251                 // Try to keep at least 25% of the buckets free
252                 return num_buckets - (num_buckets >> 2);
253         }
254
255         void grow();
256
257 public:
258         // 23.3.1.1 Construct/copy/destroy
259         exhashmap()
260          : num_entries(0), num_buckets(min_num_buckets), hashtab(num_buckets, std::make_pair(EMPTY, std::make_pair(0, mapped_type()))) {}
261
262         explicit exhashmap(size_type nbuckets)
263          : num_entries(0), num_buckets(internal::next_prime(nbuckets)), hashtab(num_buckets, std::make_pair(EMPTY, std::make_pair(0, mapped_type()))) {}
264
265         template <class InputIterator>
266         exhashmap(InputIterator first, InputIterator last)
267          : num_entries(0), num_buckets(min_num_buckets), hashtab(num_buckets, std::make_pair(EMPTY, std::make_pair(0, mapped_type())))
268         {
269                 insert(first, last);
270         }
271
272         exhashmap &operator=(const exhashmap &other)
273         {
274                 exhashmap(other).swap(*this);
275                 return *this;
276         }
277
278         // Iterators
279         iterator begin()
280         {
281                 // Find first used bucket
282                 table_iterator bucket = hashtab.begin();
283                 while (bucket != hashtab.end() && bucket->first != USED)
284                         ++bucket;
285                 return iterator(bucket, hashtab.end());
286         }
287
288         const_iterator begin() const
289         {
290                 // Find first used bucket
291                 table_const_iterator bucket = hashtab.begin();
292                 while (bucket != hashtab.end() && bucket->first != USED)
293                         ++bucket;
294                 return const_iterator(bucket, hashtab.end());
295         }
296
297         iterator end()
298         {
299                 return iterator(hashtab.end(), hashtab.end());
300         }
301
302         const_iterator end() const
303         {
304                 return const_iterator(hashtab.end(), hashtab.end());
305         }
306
307         // Capacity
308         bool empty() const
309         {
310                 return num_entries == 0;
311         }
312
313         size_type size() const
314         {
315                 return num_entries;
316         }
317
318         size_type max_size() const
319         {
320                 return hashtab.max_size();
321         }
322
323         size_type bucket_count() const
324         {
325                 return num_buckets;
326         }
327
328         // 23.3.1.2 Element access
329         T &operator[](const key_type &x)
330         {
331                 return insert(value_type(x, mapped_type())).first->second;
332         }
333
334         // Modifiers
335         std::pair<iterator, bool> insert(const value_type &x);
336
337         iterator insert(iterator pos, const value_type &x)
338         {
339                 return insert(x).first;
340         }
341
342         template <class InputIterator>
343         void insert(InputIterator first, InputIterator last)
344         {
345                 for (; first != last; ++first)
346                         insert(*first);
347         }
348
349         void erase(iterator position)
350         {
351                 table_iterator bucket = position.get_it_();
352                 bucket->first = ERASED;
353                 bucket->second.first = 0;
354                 --num_entries;
355         }
356
357         size_type erase(const key_type &x);
358
359         void swap(exhashmap &other)
360         {
361                 hashtab.swap(other.hashtab);
362                 std::swap(num_buckets, other.num_buckets);
363                 std::swap(num_entries, other.num_entries);
364         }
365
366         void clear();
367
368         // Observers
369         key_compare key_comp() const
370         {
371                 return key_compare();
372         }
373
374         value_compare value_comp() const
375         {
376                 return value_compare();
377         }
378
379         // 23.3.1.3 Map operations
380         iterator find(const key_type &x);
381         const_iterator find(const key_type &x) const;
382
383         size_type count(const key_type &x) const
384         {
385                 return find(x) == end() ? 0 : 1;
386         }
387
388         std::pair<iterator, iterator> equal_range(const key_type &x)
389         {
390                 iterator i = find(x);
391                 if (i == end())
392                         return std::make_pair(i, i);
393                 else {
394                         iterator j = ++i;
395                         return std::make_pair(i, j);
396                 }
397         }
398
399         std::pair<const_iterator, const_iterator> equal_range(const key_type &x) const
400         {
401                 const_iterator i = find(x);
402                 if (i == end())
403                         return std::make_pair(i, i);
404                 else {
405                         const_iterator j = ++i;
406                         return std::make_pair(i, j);
407                 }
408         }
409
410         friend bool operator==(const exhashmap &lhs, const exhashmap &rhs)
411         {
412                 if (lhs.num_entries != rhs.num_entries || lhs.num_buckets != rhs.num_buckets)
413                         return false;
414
415                 // We can't compare the tables directly as the elements may be
416                 // in different order due to the collision handling. We therefore
417                 // look up each value from the lhs map in the rhs map separately.
418                 for (const_iterator itl = lhs.begin(); itl != lhs.end(); ++itl) {
419                         const_iterator itr = rhs.find(itl->first);
420                         if (itr == rhs.end())
421                                 return false;
422                         if (itl->second != itr->second)
423                                 return false;
424                 }
425                 return true;
426         }
427
428         friend bool operator!=(const exhashmap &lhs, const exhashmap &rhs)
429         {
430                 return !(lhs == rhs);
431         }
432
433 #if 0
434         void dump() const
435         {
436                 std::clog << "num_entries = " << num_entries << std::endl;
437                 std::clog << "num_buckets = " << num_buckets << std::endl;
438                 size_type t = 0;
439                 for (table_const_iterator it = hashtab.begin(); it != hashtab.end(); ++it, ++t) {
440                         std::clog << " bucket " << t << ": ";
441                         std::clog << (it->first == EMPTY ? "free" : (it->first == USED ? "used" : "erased")) << ", " << it->second.first << " -> " << it->second.second << std::endl;
442                 }
443         }
444 #endif
445 };
446
447 /** Return pointer to bucket corresponding to key (or first empty bucket). */
448 template <typename T, template <class> class A>
449 inline typename exhashmap<T, A>::table_iterator exhashmap<T, A>::find_bucket(const key_type &x, table_iterator tab, size_type nbuckets)
450 {
451         // Quadratic probing
452         size_type h = hash_index(x, nbuckets);
453         size_type d = 1;
454         table_iterator it = tab + h;
455         while (it->first != EMPTY && !(it->first == USED && key_equal()(it->second.first, x))) {
456                 h = (h + d) % nbuckets;
457                 d += 2;
458                 it = tab + h;
459         }
460         return it;
461 }
462
463 /** Return pointer to bucket corresponding to key (or first empty bucket). */
464 template <typename T, template <class> class A>
465 inline typename exhashmap<T, A>::table_const_iterator exhashmap<T, A>::find_bucket(const key_type &x, table_const_iterator tab, size_type nbuckets)
466 {
467         // Quadratic probing
468         size_type h = hash_index(x, nbuckets);
469         size_type d = 1;
470         table_const_iterator it = tab + h;
471         while (it->first != EMPTY && !(it->first == USED && key_equal()(it->second.first, x))) {
472                 h = (h + d) % nbuckets;
473                 d += 2;
474                 it = tab + h;
475         }
476         return it;
477 }
478
479 /** Return pointer to bucket corresponding to key (or first empty or erased bucket). */
480 template <typename T, template <class> class A>
481 inline typename exhashmap<T, A>::table_iterator exhashmap<T, A>::find_bucket_for_insertion(const key_type &x, table_iterator tab, size_type nbuckets)
482 {
483         // Quadratic probing
484         size_type h = hash_index(x, nbuckets);
485         size_type d = 1;
486         table_iterator it = tab + h;
487         while (it->first != EMPTY && !key_equal()(it->second.first, x)) {
488                 h = (h + d) % nbuckets;
489                 d += 2;
490                 it = tab + h;
491         }
492         return it;
493 }
494
495 /** Grow hash table */
496 template <typename T, template <class> class A>
497 void exhashmap<T, A>::grow()
498 {
499         // Allocate new empty hash table
500         size_type new_num_buckets = internal::next_prime(num_buckets + 1);
501         Table new_hashtab;
502         new_hashtab.resize(new_num_buckets);
503         for (table_iterator it = new_hashtab.begin(); it != new_hashtab.end(); ++it)
504                 it->first = EMPTY;
505
506         // Re-insert all elements into new table
507         for (table_const_iterator it = hashtab.begin(); it != hashtab.end(); ++it) {
508                 if (it->first == USED) {
509                         table_iterator bucket = find_bucket(it->second.first, new_hashtab.begin(), new_num_buckets);
510                         *bucket = *it;
511                 }
512         }
513
514         // Swap with the old table
515         hashtab.swap(new_hashtab);
516         num_buckets = new_num_buckets;
517 }
518
519 template <typename T, template <class> class A>
520 std::pair<typename exhashmap<T, A>::iterator, bool> exhashmap<T, A>::insert(const value_type &x)
521 {
522         table_iterator bucket = find_bucket_for_insertion(x.first);
523         if (bucket->first == USED) {
524                 // Value already in map
525                 return std::make_pair(iterator(bucket, hashtab.end()), false);
526         } else {
527                 // Insert new value
528                 bucket->first = USED;
529                 bucket->second = x;
530                 ++num_entries;
531                 if (num_entries >= hwm()) {
532                         grow();
533                         bucket = find_bucket(x.first);
534                 }
535                 return std::make_pair(iterator(bucket, hashtab.end()), true);
536         }
537 }
538
539 template <typename T, template <class> class A>
540 typename exhashmap<T, A>::size_type exhashmap<T, A>::erase(const key_type &x)
541 {
542         iterator i = find(x);
543         if (i != end()) {
544                 erase(i);
545                 return 1;
546         } else
547                 return 0;
548 }
549
550 template <typename T, template <class> class A>
551 typename exhashmap<T, A>::iterator exhashmap<T, A>::find(const key_type &x)
552 {
553         table_iterator bucket = find_bucket(x);
554         if (bucket->first == USED)
555                 return iterator(bucket, hashtab.end());
556         else
557                 return end();
558 }
559
560 template <typename T, template <class> class A>
561 typename exhashmap<T, A>::const_iterator exhashmap<T, A>::find(const key_type &x) const
562 {
563         table_const_iterator bucket = find_bucket(x);
564         if (bucket->first == USED)
565                 return const_iterator(bucket, hashtab.end());
566         else
567                 return end();
568 }
569
570 template <typename T, template <class> class A>
571 void exhashmap<T, A>::clear()
572 {
573         for (table_iterator i = hashtab.begin(); i != hashtab.end(); ++i) {
574                 i->first = EMPTY;
575                 i->second.first = 0;
576                 i->second.second = mapped_type();
577         }
578         num_entries = 0;
579 }
580
581 } // namespace GiNaC
582
583
584 // Specializations of Standard Library algorithms
585 namespace std {
586
587 /** Specialization of std::swap() for exhashmap. */
588 template <typename T, template <class> class A>
589 inline void swap(GiNaC::exhashmap<T, A> &lhs, GiNaC::exhashmap<T, A> &rhs)
590 {
591         lhs.swap(rhs);
592 }
593
594 } // namespace std
595
596 #endif // ndef GINAC_HASH_MAP_H