#ifndef LCDF_HASHMAP_HH #define LCDF_HASHMAP_HH #include #include // K AND V REQUIREMENTS: // // K::K() // K::operator bool() const // Must have (bool)(K()) == false // and no k with (bool)k == false is stored. // K & K::operator=(const K &) // k1 == k2 // hashcode_t hashcode(const K &) // If hashcode(k1) != hashcode(k2), then k1 != k2. // Actually any unsigned integer type may be used. // // V::V() // V & V::operator=(const V &) template class _HashMap_const_iterator; template class _HashMap_iterator; template class HashMap { public: HashMap(); explicit HashMap(const V &); HashMap(const HashMap &); ~HashMap() { delete[] _e; } int size() const { return _n; } bool empty() const { return _n == 0; } int capacity() const { return _capacity; } const V &default_value() const { return _default_value; } void set_default_value(const V &v) { _default_value = v; } typedef _HashMap_const_iterator const_iterator; typedef _HashMap_iterator iterator; inline const_iterator begin() const; inline iterator begin(); inline const_iterator end() const; inline iterator end(); inline const V &find(const K &) const; inline V *findp(const K &) const; inline const V &operator[](const K &k) const; V &find_force(const K &, const V &); inline V &find_force(const K &); bool insert(const K &, const V &); void clear(); HashMap &operator=(const HashMap &); void swap(HashMap &); void resize(int size) { increase(size); } struct Pair { K key; V value; Pair() : key(), value() { } }; private: int _capacity; int _grow_limit; int _n; Pair *_e; V _default_value; void increase(int); inline void check_capacity(); inline int bucket(const K &) const; friend class _HashMap_const_iterator; friend class _HashMap_iterator; }; template class _HashMap_const_iterator { public: typedef _HashMap_const_iterator const_iterator; typedef typename HashMap::Pair Pair; operator bool() const { return _pos < _hm->_capacity; } bool operator!() const { return _pos >= _hm->_capacity; } void operator++(int); void operator++() { (*this)++; } const K &key() const { return _hm->_e[_pos].key; } const V &value() const { return _hm->_e[_pos].value; } const Pair &pair() const { return _hm->_e[_pos]; } inline bool operator==(const const_iterator &) const; inline bool operator!=(const const_iterator &) const; private: const HashMap *_hm; int _pos; _HashMap_const_iterator(const HashMap *, int); friend class HashMap; friend class _HashMap_iterator; }; template class _HashMap_iterator : public _HashMap_const_iterator { public: typedef _HashMap_iterator iterator; V &value() const { return this->_hm->_e[this->_pos].value; } private: _HashMap_iterator(const HashMap *hm, int pos) : _HashMap_const_iterator(hm, pos) { } friend class HashMap; }; template inline int HashMap::bucket(const K &key) const { assert(key); hashcode_t hc = hashcode(key); int i = hc & (_capacity - 1); int j = ((hc >> 6) & (_capacity - 1)) | 1; while (_e[i].key && !(_e[i].key == key)) i = (i + j) & (_capacity - 1); return i; } template inline const V & HashMap::find(const K &key) const { int i = bucket(key); const V *v = (_e[i].key ? &_e[i].value : &_default_value); return *v; } template inline const V & HashMap::operator[](const K &key) const { return find(key); } template inline V * HashMap::findp(const K &key) const { int i = bucket(key); return _e[i].key ? &_e[i].value : 0; } template inline V & HashMap::find_force(const K &key) { return find_force(key, _default_value); } template inline _HashMap_const_iterator HashMap::begin() const { return const_iterator(this, 0); } template inline _HashMap_const_iterator HashMap::end() const { return const_iterator(this, _capacity); } template inline _HashMap_iterator HashMap::begin() { return iterator(this, 0); } template inline _HashMap_iterator HashMap::end() { return iterator(this, _capacity); } template inline bool _HashMap_const_iterator::operator==(const const_iterator &i) const { return _hm == i._hm && _pos == i._pos; } template inline bool _HashMap_const_iterator::operator!=(const const_iterator &i) const { return _hm != i._hm || _pos != i._pos; } #include // necessary to support GCC 3.3 #endif