proto/Source/hash_vector.h

Go to the documentation of this file.

#ifndef _HASH_H
#define _HASH_H

#include <algorithm>
#include <functional>
#include <vector>

namespace ace {

// NOTE: Class is designed with above-lying structure in mind,
// which is generally (very) bad idea. But performace is... performance.

template<class _StType, class _HashFunc>
class HashVector {
public:
    typedef _StType type;

private:
    typedef typename std::vector<_StType> _store_t;
    typedef typename std::vector<_store_t> _buckets_t;

    size_t _init_size;
    size_t _bucket_size;
    std::vector<_store_t> _buckets; 
    _HashFunc _h;
    size_t _items;
    size_t _crop_ratio;

    class items_compare: public std::unary_function<_StType, bool> {
        const _StType _look_for;
    public:
        items_compare(_StType look_for): _look_for(look_for) {}
        bool operator()(_StType ptr) const {
            return *ptr == *_look_for;
        }
    };

    class items_sort: public std::binary_function<_StType, _StType, bool> {
    public:
        bool operator()(_StType lhs, _StType rhs) const {
            // > -> we want descending order!
            return lhs->frequency() > rhs->frequency();
        }
    };

    void _expand(void) {
        //
        size_t _recent_buckets_size = _buckets.size();

        // Double size buckets table.
        _buckets.resize(_recent_buckets_size * 2);

        bool any_empty = false;
        size_t bucket_index = 0, index_of_empty = 0;
        // Process each bucket (except newly added of course).
        for ( size_t i = 0; i < _recent_buckets_size; ++i ) {
            any_empty = false; // !
            for ( size_t j = 0; j < _buckets[i].size(); ++j ) {
                // Get bucket no.
                bucket_index = _h(_buckets[i][j]) % _buckets.size();                
                if ( bucket_index != i ) {
                    // Copy to new bucket.
                    _buckets[bucket_index].push_back(_buckets[i][j]);
                    if ( !any_empty ) {
                        any_empty = true; index_of_empty = j;
                    }
                } else if ( any_empty ) {
                    // Any empty before?
                    _buckets[i][index_of_empty] = _buckets[i][j];
                    ++index_of_empty;
                    // We get rid of tail empty elements later...
                }
            }

            // Really remove "removed" elements (we have to count number of elements added into new bucket,
            // to know how much elements to erase (from end).
            _buckets[i].erase(_buckets[i].end() - _buckets[i + _recent_buckets_size].size(), _buckets[i].end());

            // STD way.
            // The two calls below does exactly the same, as the loop and erase command above.
            // It's a pity, remove_copy_if doesn't really "remove" elements (even in remove_if way!).
            //std::remove_copy_if(_buckets[i].begin(), _buckets[i].end(), std::back_inserter(_buckets[i+_recent_buckets_size]), std::not1(hash_compare(i, _buckets.size())));
            // Two calls are more expensive then one hand written loop.
            //_buckets[i].erase(std::remove_if(_buckets[i].begin(), _buckets[i].end(), hash_compare(i, _buckets.size())), _buckets[i].end());

            // Too much unused space in bucket?
            if ( _crop_ratio ) {
                if ( (_buckets[i].size() * _crop_ratio) < _buckets[i].capacity() ) {
                    // So do crop!
                    std::vector<_StType>(_buckets[i]).swap(_buckets[i]);
                }
            }
        }
    }

public:
    class iterator {
        typedef HashVector<_StType, _HashFunc> _hash_t;
        typename _hash_t::_buckets_t::const_iterator _end_of_buckets;
        typename _hash_t::_buckets_t::const_iterator _i_bucket;
        typename _hash_t::_store_t::const_iterator _i_item;
        inline bool _end(void) const { return _i_bucket == _end_of_buckets; }
        void _init_item(void) {
            if ( _end() ) {
                return;
            }
            if ( _i_bucket->empty() ) {
                // Find first non empty bucket.
                _next();
            } else {
                _i_item = _i_bucket->begin();
            }
        }
        void _next(void) {
            // Go to next non empty bucket.
            while ( (++_i_bucket != _end_of_buckets) && _i_bucket->empty() );
            if ( _i_bucket != _end_of_buckets ) {
                //
                _i_item = _i_bucket->begin();
            }
        }

    public:
        explicit iterator(const typename _hash_t::_buckets_t& hash_buckets): _end_of_buckets(hash_buckets.end()), _i_bucket(hash_buckets.begin()), _i_item() {
            _init_item();
        }
        explicit iterator(const typename _hash_t::_buckets_t& hash_buckets, typename _hash_t::_buckets_t::const_iterator i_bucket): _end_of_buckets(hash_buckets.end()), _i_bucket(i_bucket), _i_item() {
            _init_item();
        }
        explicit iterator(const typename _hash_t::_buckets_t& hash_buckets, typename _hash_t::_buckets_t::const_iterator i_bucket, typename _hash_t::_store_t::const_iterator i_item): _end_of_buckets(hash_buckets.end()), _i_bucket(i_bucket), _i_item(i_item) {}

        // Following operators are needed to satisfy NGramStore functionality.

        iterator& operator++(void) {
            if ( _end() ) {
                // Do nothing.
                return *this;
            }
            if ( ++_i_item == _i_bucket->end() ) {
                // Find next non empty bucket and set item iterator to its beginning.
                _next();
            }
            return *this;
        }

        const typename _hash_t::type& operator*(void) const {
            // If invalid, would fall as it should.
            return *_i_item;
        }

        bool operator==(const iterator& rhs) const {

            if ( _i_bucket != rhs._i_bucket ) {             
                // Different buckets.
                return false;
            }
            if ( _end() && rhs._end() ) {
                // Both at end.
                return true;
            }
            if ( _end() || rhs._end() ) {
                // Only one at its end, so:
                return false;
            }           
            if ( _i_item == rhs._i_item ) {
                // Both the same!
                return true;
            }
            return false;
        }

        bool operator!=(const iterator& rhs) const {
            return !operator==(rhs);
        }

    };

    // Following typedefs are needed to meet in hashset interface used by
    // overlying N-grams storing structure.
    
    typedef iterator const_iterator;
    typedef std::pair<iterator, bool> pair_ib;
    typedef std::pair<iterator, iterator> pair_ii;

    HashVector(size_t init_size, size_t bucket_size, size_t crop_ratio): _init_size(1 << init_size), _bucket_size(1 << bucket_size), _buckets(_init_size), _items(0), _crop_ratio(crop_ratio) {}

    HashVector& operator=(const HashVector& rhs) {
        if ( this != &rhs ) {
            _init_size = rhs._init_size;
            _bucket_size = rhs._bucket_size;
            _buckets = rhs._buckets;
            _items = rhs._items;
            _h = rhs._h;
            _crop_ratio = rhs._crop_ratio;
        }
        return *this;
    }

    const_iterator begin(void) const {
        return const_iterator(_buckets);
    }

    const_iterator end(void) const {
        return const_iterator(_buckets, _buckets.end());
    }

    pair_ib insert(_StType value) {
        // Update items counter and do check...
        if ( ++_items > (_buckets.size() * _bucket_size) ) {
            // Expansion needed!
            _expand();
        }
        // Find bucket.
        typename _buckets_t::iterator bucket = _buckets.begin() + (_h(value) % _buckets.size());
        // Insert...
        bucket->push_back(value);
        // ...and return.
        return pair_ib(iterator(_buckets, bucket, bucket->end() - 1), true);
    }

    pair_ii equal_range(const _StType value) const {
        
        typename _buckets_t::const_iterator bucket = _buckets.begin() + (_h(value) % _buckets.size());
        // Look into recent.
        typename _store_t::const_iterator searched = std::find_if(bucket->begin(), bucket->end(), items_compare(value));

        if ( searched != bucket->end() ) {
            // Founded!
            return pair_ii(iterator(_buckets, bucket, searched), iterator(_buckets, bucket, searched + 1));
        } else {
            // Sorry, not found.
            return pair_ii(iterator(_buckets, bucket, bucket->end()), iterator(_buckets, bucket, bucket->end()));
        }           
    }

    inline size_t size(void) const { return _items; }

    void sort(void) {
        for ( typename _buckets_t::iterator i_bucket = _buckets.begin(); i_bucket != _buckets.end(); ++i_bucket ) {
            std::sort(i_bucket->begin(), i_bucket->end(), items_sort());
        }
    }

};

} // namespace ace

#endif

---