HMap.h

Go to the documentation of this file.

//
// Copyright (c) 2006-2007 Raphael David / CANTOR
//

#ifndef CMR_HMAP_INCLUDED
#define CMR_HMAP_INCLUDED

#include <string.h>
#include <stddef.h>
#include "commore/Commore.h"

namespace commore
{
    template<class Arg, class Result> class  unary_function
    {
    public:
        //
        typedef Arg  argument_type;
        typedef Result  result_type;

    public:
        unary_function() : purify_unary_function(0) {}
        unary_function(const  unary_function< Arg, Result >&) : purify_unary_function(0) {}
        unary_function< Arg, Result >& operator=(const  unary_function< Arg, Result >&)
        {
            return *this;
        }

    private:
        char  purify_unary_function;

    };

    template< class T > class hash : public  unary_function< T, size_t >
    {
    public:
        size_t  CMREXD operator()(const T& key) const;  // { return (size_t) key; }
    };

    template<class Arg1, class Arg2, class Result> class  binary_function
    {
    public:
        typedef Arg1  first_argument_type;
        typedef Arg2  second_argument_type;
        typedef Result  result_type;

    public:
        binary_function() : purify_binary_function(0) {}
        binary_function(const  binary_function< Arg1, Arg2, Result >&) : purify_binary_function(0) {}
        binary_function<Arg1, Arg2, Result>&
        operator=(const  binary_function< Arg1, Arg2, Result >&)
        {
            return *this;
        }

    private:
        char  purify_binary_function;
    };

    template< class T > class  equal_to : public  binary_function< T, T, bool >
    {
    public:
        equal_to()
            : purify_equal_to(0)          {}
        equal_to(const  equal_to< T >&)
            : purify_equal_to(0)          {}
        equal_to< T >& operator=(const  equal_to< T >&)
        {
            return *this;
        }

    public:
        bool  operator()(const T& x, const T& y) const
        {
            return x == y;
        }

    private:
        char  purify_equal_to;
    };


    template<class T> class  not_equal_to : public  binary_function< T, T, bool >
    {
    private:
        char  purify_not_equal_to;
    public:
        not_equal_to()
            : purify_not_equal_to(0)      {}
        not_equal_to(const  not_equal_to< T >&)
            : purify_not_equal_to(0)      {}
        not_equal_to< T >& operator=(const  not_equal_to< T >&)
        {
            return *this;
        }

    public:
        bool  operator()(const T& x, const T& y) const
        {
            return x != y;
        }
    };

    template< class T, class U >  class stl_select1st : public  unary_function< T, const U& >
    {
    public:
        stl_select1st()
            : purify_stl_select1st(0)     {}
        stl_select1st(const stl_select1st< T, U >&)
            : purify_stl_select1st(0)     {}
        stl_select1st< T, U >& operator=(const stl_select1st< T, U >&)
        {
            return *this;
        }

    public:
        const U& operator()(const T& value) const
        {
            return value.first;
        }

    private:
        char  purify_stl_select1st;
    };

    template< class T1, class T2 > class  pair
    {
    public:
        typedef T1  first_type;
        typedef T2  second_type;

    public:
        pair() {}
        pair(const T1& x, const T2& y)
            : first(x), second(y)               { }
        pair(const  pair< T1, T2 >& p)
            : first(p.first), second(p.second)  { }
        ~pair() {}

    public:
        T1  first;
        T2  second;
    };



    template< class T1, class T2 >
    inline bool operator==(const  pair< T1, T2 >& x, const  pair< T1, T2 >& y)
    {
        return x.first == y.first && x.second == y.second;
    }


    template< class T1, class T2 >
    inline bool operator<(const  pair< T1, T2 >& x, const  pair< T1, T2 >& y)
    {
        return
            x.first < y.first
            || (!(y.first < x.first) && x.second < y.second);
    }


    template< class T1, class T2 >
    inline  pair< T1, T2 > make_pair(const T1& x, const T2& y)
    {
        return  pair< T1, T2 >(x, y);
    }

    template< class T > struct hash_node
    {
    public:
        hash_node()             {}
        hash_node(const T& t)
            : data_(t)          {}

    public:
        //
        T  data_;
        size_t  hash_;
        hash_node<T>* next_;
    };


    template< class T > class hash_table_iterator;
    template< class T > class hash_table_const_iterator;

    template < class Key, class T, class KeyOfValue, class Hasher, class KeyEqual>
    class hash_table
    {
    public:
        typedef Key  key_type;
        typedef T  value_type;
        typedef Hasher  hasher;
        typedef  KeyEqual  key_equal;
        typedef T& reference;
        typedef const T& const_reference;
        typedef T* pointer;
        typedef const T* const_pointer;
        typedef size_t  size_type;
        typedef ptrdiff_t  difference_type;

        typedef hash_table_iterator <T>  iterator;
        typedef hash_table_const_iterator <T>  const_iterator;

    public:

        hash_table(
            size_type table_size,
            const Hasher& hf,
            const KeyEqual& ke,
            float load_ratio ,
            bool insert_always = false) :
            size_(0),
            length_(table_size),
            hasher_(hf),
            key_equal_(ke),
            ratio_(load_ratio),
            buckets_(0),
            insert_always_(insert_always)
        {
            limit_ = (size_type)(length_ * ratio_);
            buckets_ = allocate_node_ptr(length_);
        }


        hash_table(
            iterator first,
            iterator last,
            size_type table_size ,
            const Hasher& hf ,
            const KeyEqual& ke ,
            float load_ratio ,
            bool insert_always = false) :
            size_(0),
            length_(table_size),
            hasher_(hf),
            key_equal_(ke),
            ratio_(load_ratio),
            buckets_(0),
            insert_always_(insert_always)
        {
            limit_ = (size_type)(length_ * ratio_);
            buckets_ = allocate_node_ptr(length_);
            insert(first, last);
        }

        hash_table(
            const hash_table <Key, T, KeyOfValue, Hasher, KeyEqual >& other)
        {
            copy(other);
        }

        ~hash_table()
        {
            clear();
            deallocate_node_ptr(buckets_);
        }

        hash_table < Key, T, KeyOfValue, Hasher, KeyEqual>& operator=(
            const hash_table < Key, T, KeyOfValue, Hasher, KeyEqual>& other)
        {
            if (this != &other)
            {
                clear();
                deallocate_node_ptr(buckets_);
                copy(other);
            }
            return *this;
        }

        void swap(hash_table < Key, T, KeyOfValue, Hasher, KeyEqual>& other)
        {
            swap(insert_always_, other.insert_always_);
            swap(size_, other.size_);
            swap(buckets_, other.buckets_);
            swap(length_, other.length_);
            swap(limit_, other.limit_);
            swap(ratio_, other.ratio_);
            swap(hasher_, other.hasher_);
            swap(key_equal_, other.key_equal_);
            swap(key_of_value_, other.key_of_value_);
        }

    public:
        hasher hash_funct() const
        {
            return hasher_;
        }

        key_equal key_eq() const
        {
            return key_equal_;
        }

        iterator  begin()
        {
            return iterator(buckets_, length_, first());
        }

        const_iterator  begin() const
        {
            return const_iterator(buckets_, length_, first());
        }

        const_iterator cbegin() const 
        {
            return begin();
        }

        iterator  end()
        {
            return iterator(buckets_, length_, 0);
        }

        const_iterator  end() const
        {
            return const_iterator(buckets_, length_, 0);
        }

        const_iterator cend() const
        {
            return end();
        }

        bool  empty() const
        {
            return size_ == 0;
        }

        size_type  size() const
        {
            return size_;
        }

        size_type  max_size() const
        {
            const size_type s = (size_type)(0xffffffff / sizeof(T));
            return 1 < s ? s : 1;
        }

        pair< hash_table_iterator< T >, bool  > insert(const T& value);

        void  insert(const T* first, const T* last);

        void  insert(const_iterator first, const_iterator last);
        void  erase(iterator pos);

        size_type  erase(const key_type& key);
        void  erase(iterator first, iterator last);

        iterator  find(const key_type& key);
        const_iterator  find(const key_type& key) const;

        size_type  count(const key_type& key) const;

        pair< hash_table_iterator < T >, hash_table_iterator < T > > equal_range(const key_type& key);

        pair < hash_table_const_iterator < T >, hash_table_const_iterator < T > > equal_range(const key_type& key) const;

        size_type  bucket_count() const
        {
            return limit_;
        }

        void  resize(size_type buckets)
        {
            expand(buckets);
        }
        void  clear();

    private:
        size_type  hash_value(const key_type& key) const
        {
            return (size_type)(hasher_(key) & 0x7FFFFFFF);
        }
        bool  hash_key_equal(size_type  hash, const key_type& key, hash_node< T >* n) const
        {
            return n->hash_ == hash && key_equal_(key, key_of_value_(n->data_));
        }

        hash_node< T >* allocate_node()
        {
            hash_node< T >* z;
            z = new hash_node<T>();
            z->next_ = 0;
            return z;
        }

        void  deallocate_node(hash_node< T >* node)
        {
            delete node;
        }

        hash_node< T >** allocate_node_ptr(size_t n);

        void  deallocate_node_ptr(hash_node< T >** node)
        {
            delete [] node;
        }

        hash_node< T >* first() const;
        void  copy(const hash_table < Key, T, KeyOfValue, Hasher, KeyEqual>& other);
        void  expand(size_t new_length = 0);
        hash_node< T >* next(hash_node< T >* node) const;

    private:
        bool  insert_always_;
        size_type  size_;
        hash_node< T >** buckets_;
        size_type  length_;
        size_type  limit_;
        float  ratio_;
        Hasher  hasher_;
        KeyEqual  key_equal_;
        KeyOfValue  key_of_value_;
    };



    template< class T >
    class hash_table_iterator   // : public  forward_iterator< T, Distance >
    {
    public:
        hash_table_iterator()
            : buckets_(0), node_(0), length_(0)                   { }


        hash_table_iterator(hash_node< T >** buckets, size_t length, hash_node< T >* node)
            : buckets_(buckets), node_(node), length_(length)     { }


        hash_table_iterator(const hash_table_iterator< T >& other)
            : buckets_(other. buckets_), node_(other. node_), length_(other. length_) { }


        ~hash_table_iterator() { }


        hash_table_iterator< T >&
        operator=(const hash_table_iterator< T >& other)
        {
            buckets_ = other. buckets_;
            node_ = other. node_;
            length_ = other. length_;
            return *this;
        }

    public:

        T& operator*() const
        {
            return node_->data_;
        }

        hash_table_iterator< T >& operator++()
        {
            node_ = node_->next_ ? node_->next_ : next(node_);
            return *this;
        }


        hash_table_iterator< T > operator++(int)
        {
            hash_table_iterator< T > tmp = *this;
            ++*this;
            return tmp;
        }


        bool operator==(const hash_table_iterator< T >& other) const
        {
            return node_ == other.node_;
        }


        bool operator!=(const hash_table_iterator< T >& other) const
        {
            return node_ != other.node_;
        }


        hash_node< T >* next(hash_node< T >* node);

    public:
        hash_node< T >** buckets_;
        hash_node< T >* node_;
        size_t length_;
    };


    template< class T >
    class hash_table_const_iterator   //: public  forward_iterator< T, Distance >
    {
    public:
        hash_table_const_iterator() : buckets_(0), node_(0), length_(0)   { }

        hash_table_const_iterator(hash_node< T >** buckets, size_t length, hash_node< T >* node)
            : buckets_(buckets), node_(node), length_(length)             { }


        hash_table_const_iterator(const hash_table_const_iterator< T >& other)
            : buckets_(other. buckets_), node_(other. node_), length_(other. length_)  { }

        hash_table_const_iterator(const hash_table_iterator< T >& other)
            : buckets_(other. buckets_), node_(other. node_), length_(other. length_)  { }

        ~hash_table_const_iterator() {}


        hash_table_const_iterator< T >& operator=(const hash_table_const_iterator< T >& other)
        {
            buckets_ = other. buckets_;
            node_ = other. node_;
            length_ = other. length_;
            return *this;
        }

    public:

        const T& operator*() const
        {
            return node_->data_;
        }

        hash_table_const_iterator< T >& operator++()
        {
            node_ = node_->next_ ? node_->next_ : next(node_);
            return *this;
        }

        hash_table_const_iterator< T > operator++(int)
        {
            hash_table_const_iterator< T > tmp = *this;
            ++*this;
            return tmp;
        }


        bool operator==(const hash_table_const_iterator< T >& other) const
        {
            return node_ == other.node_;
        }


        bool operator!=(const hash_table_const_iterator< T >& other) const
        {
            return node_ != other.node_;
        }

        hash_node< T >* next(hash_node< T >* node);

    public:
        hash_node< T >** buckets_;
        hash_node< T >* node_;
        size_t length_;
    };



    template<class Key, class Value,
             class Hasher = hash< Key >,
             class KeyEqual =  equal_to< Key >
             >
    class HMap
    {
    public:
        typedef Key key_type;
        typedef  pair< Key, Value > value_type;
        typedef Hasher hasher;
        typedef KeyEqual key_equal;
        typedef size_t  size_type;
        typedef ptrdiff_t  difference_type;
        typedef  pair< Key, Value >&  reference;
        typedef const  pair< Key, Value >&  const_reference;

        typedef hash_table_iterator < pair< Key, Value > >  iterator;
        typedef hash_table_const_iterator < pair< Key, Value > >  const_iterator;

    public:



        explicit HMap(size_type table_size = 203) :
            hash_table_(table_size, Hasher(), KeyEqual(), 0.75f)
        {
        }

        HMap(
            size_type table_size,
            const Hasher& hf,
            const KeyEqual& ke,
            float load_ratio = 0.75f) :
            hash_table_(table_size, hf, ke, load_ratio)
        {
        }


        HMap(
            iterator first,
            iterator last,
            size_type table_size = 203) :
            hash_table_(first, last, table_size, Hasher(), KeyEqual(), 0.75f)
        {
        }

        HMap(
            iterator first,
            iterator last,
            size_type table_size,
            const Hasher& hf,
            const KeyEqual& ke,
            float load_ratio = 0.75f) :
            hash_table_(first, last, table_size, hf, ke, load_ratio)
        {
        }




        HMap(const HMap < Key, Value, Hasher, KeyEqual>& other) :
            hash_table_(other.hash_table_) {}

        ~HMap() {}

        HMap < Key, Value, Hasher, KeyEqual>& operator= (const HMap < Key, Value, Hasher, KeyEqual>& other)
        {
            if (this != &other)
            {
                hash_table_ = other.hash_table_;
            }
            return *this;
        }

    public:
        void swap(HMap < Key, Value, Hasher, KeyEqual>& other)
        {
            hash_table_.swap(other.hash_table_);
        }

        hasher hash_funct() const
        {
            return hash_table_.hash_funct();
        }

        key_equal key_eq() const
        {
            return hash_table_.key_eq();
        }

        iterator begin()
        {
            return hash_table_.begin();
        }

        const_iterator begin() const
        {
            return hash_table_.begin();
        }

        iterator end()
        {
            return hash_table_.end();
        }

        const_iterator end() const
        {
            return hash_table_.end();
        }

        bool empty() const
        {
            return hash_table_.empty();
        }

        size_type size() const
        {
            return hash_table_.size();
        }

        size_type max_size() const
        {
            return hash_table_.max_size();
        }

        pair< iterator, bool > insert(const  pair< Key, Value >& p)
        {
            return hash_table_.insert(p);
        }

        pair< iterator, bool > insert(const Key& key, const Value& value)
        {
            pair< Key, Value > p(key, value);
            return hash_table_.insert(p);
        }

        void insert(
            const  pair< Key, Value >* first,
            const  pair< Key, Value >* last)
        {
            hash_table_.insert(first, last);
        }

        void insert(const_iterator first, const_iterator last)
        {
            hash_table_.insert(first, last);
        }

        Value& operator[](const key_type& key)
        {
            return (*(insert(pair< Key, Value >(key, Value())).first)).second;
        }

        const Value& operator[](const key_type& key) const
        {
            const_iterator i = find(key);
            if (i == end())
            {
                return (const Value&)(*(const Value*)0);
            }
            else
            {
                return (*i).second;
            }
        }

        void erase(iterator pos)
        {
            hash_table_.erase(pos);
        }

        size_type erase(const key_type& key)
        {
            return hash_table_.erase(key);
        }

        void erase(iterator first, iterator last)
        {
            hash_table_.erase(first, last);
        }

        iterator find(const key_type& key)
        {
            return hash_table_.find(key);
        }

        const_iterator find(const key_type& key) const
        {
            return hash_table_.find(key);
        }

        size_type count(const key_type& key) const
        {
            return hash_table_.count(key);
        }

        pair< iterator, iterator > equal_range(const key_type& key)
        {
            return hash_table_.equal_range(key);
        }

        pair< const_iterator, const_iterator> equal_range(const key_type& key) const
        {
            return hash_table_.equal_range(key);
        }

        size_type bucket_count() const
        {
            return hash_table_.bucket_count();
        }

        void resize(size_type buckets)
        {
            hash_table_.resize(buckets);
        }

        void clear()
        {
            hash_table_.clear();
        }

    protected:
        hash_table < Key, pair< Key, Value >,
                   stl_select1st<  pair< Key, Value >, Key >,
                   Hasher,
                   KeyEqual
                   > hash_table_;
    };

    template < class Key, class Value, class Hasher, class KeyEqual>
    inline bool operator==(
        const HMap < Key, Value, Hasher, KeyEqual>& x,
        const HMap < Key, Value, Hasher, KeyEqual>& y)
    {
        return x.size() == y.size() && equal(x.begin(), x.end(), y.begin()) ;
    }


    template < class Key, class Value, class Hasher, class KeyEqual>
    inline bool operator < (
        const HMap < Key, Value, Hasher, KeyEqual>& x,
        const HMap < Key, Value, Hasher, KeyEqual>& y)
    {
        return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
    }


    template < class Key, class Value, class Hasher, class KeyEqual>
    inline void swap(
        HMap < Key, Value, Hasher, KeyEqual>& x,
        HMap < Key, Value, Hasher, KeyEqual>& y)
    {
        x.swap(y);
    }

    template <  class Key, class Value, class Hasher = hash< Key >,
                class KeyEqual =  equal_to< Key > >
    class hash_multimap
    {
    public:
        typedef Key key_type;
        typedef  pair< Key, Value > value_type;
        typedef Hasher hasher;
        typedef KeyEqual key_equal;
        typedef size_t  size_type;
        typedef ptrdiff_t  difference_type;
        typedef  pair< Key, Value >&  reference;
        typedef const  pair< Key, Value >&  const_reference;

        typedef hash_table_iterator < pair< Key, Value > >  iterator;
        typedef hash_table_const_iterator < pair< Key, Value > >  const_iterator;

    public:
        explicit hash_multimap(size_type table_size = 203) :
            hash_table_(table_size, Hasher(), KeyEqual(), 0.75f, true) { }

        hash_multimap(
            size_type table_size,
            const Hasher& hf,
            const KeyEqual& ke,
            float load_ratio = 0.75f) :
            hash_table_(table_size, hf, ke, load_ratio, true) {}


        hash_multimap(iterator first, iterator last, size_type table_size = 203) :
            hash_table_(first, last, table_size, Hasher(), KeyEqual(), 0.75f, true)
        {
        }

        hash_multimap(
            iterator first,
            iterator last,
            size_type table_size,
            const Hasher& hf,
            const KeyEqual& ke,
            float load_ratio = 0.75f) :
            hash_table_(first, last, table_size, hf, ke, load_ratio, true)
        {
        }


        hash_multimap(const hash_multimap < Key, Value, Hasher, KeyEqual>& other) :
            hash_table_(other.hash_table_)
        {
        }

        ~hash_multimap() { }

        hash_multimap < Key, Value, Hasher, KeyEqual>& operator= (
            const hash_multimap < Key, Value, Hasher, KeyEqual>& other)
        {
            if (this != &other)
            {
                hash_table_ = other.hash_table_;
            }
            return *this;
        }

        void swap(hash_multimap < Key, Value, Hasher, KeyEqual>& other)
        {
            hash_table_.swap(other.hash_table_);
        }

    public:
        hasher hash_funct() const
        {
            return hash_table_.hash_funct();
        }

        key_equal key_eq() const
        {
            return hash_table_.key_eq();
        }

        iterator begin()
        {
            return hash_table_.begin();
        }

        const_iterator begin() const
        {
            return hash_table_.begin();
        }

        iterator end()
        {
            return hash_table_.end();
        }

        const_iterator end() const
        {
            return hash_table_.end();
        }

        bool empty() const
        {
            return hash_table_.empty();
        }

        size_type size() const
        {
            return hash_table_.size();
        }

        size_type max_size() const
        {
            return hash_table_.max_size();
        }

        iterator insert(const  pair< Key, Value >& x)
        {
            return hash_table_.insert(x).first;
        }

        iterator insert(const Key& key, const Value& value)
        {
            pair< Key, Value > p(key, value);
            return hash_table_.insert(p).first;
        }

        void insert(const  pair< Key, Value >* first, const  pair< Key, Value >* last)
        {
            hash_table_.insert(first, last);
        }

        void insert(const_iterator first, const_iterator last)
        {
            hash_table_.insert(first, last);
        }

        void erase(iterator pos)
        {
            hash_table_.erase(pos);
        }

        size_type erase(const key_type& key)
        {
            return hash_table_.erase(key);
        }

        void erase(iterator first, iterator last)
        {
            hash_table_.erase(first, last);
        }

        iterator find(const key_type& key)
        {
            return hash_table_.find(key);
        }

        const_iterator find(const key_type& key) const
        {
            return hash_table_.find(key);
        }

        size_type count(const key_type& key) const
        {
            return hash_table_.count(key);
        }

        pair< iterator, iterator > equal_range(const key_type& key)
        {
            return hash_table_.equal_range(key);
        }

        pair< const_iterator, const_iterator > equal_range(const key_type& key) const
        {
            return hash_table_.equal_range(key);
        }

        size_type bucket_count() const
        {
            return hash_table_.bucket_count();
        }

        void resize(size_type buckets)
        {
            hash_table_.resize(buckets);
        }

        void clear()
        {
            hash_table_.clear();
        }

    protected:

        hash_table < Key, pair< Key, Value >,
                   stl_select1st<  pair< Key, Value >, Key >,
                   Hasher,
                   KeyEqual
                   > hash_table_;
    };

    template < class Key, class Value, class Hasher, class KeyEqual>
    inline bool operator==(const hash_multimap
                           < Key, Value, Hasher, KeyEqual>& x,
                           const hash_multimap
                           < Key, Value, Hasher, KeyEqual>& y)
    {
        return x.size() == y.size() && equal(x.begin(), x.end(), y.begin()) ;
    }

    template < class Key, class Value, class Hasher, class KeyEqual>
    inline bool operator < (
        const hash_multimap < Key, Value, Hasher, KeyEqual>& x,
        const hash_multimap < Key, Value, Hasher, KeyEqual>& y)
    {
        return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
    }

    template< class T>
    hash_node< T >* hash_table_iterator< T >::next(hash_node< T >* node)
    {
        for (size_t i = (node->hash_ % length_) + 1; i < length_; i++)
            if (buckets_[ i ])
            {
                return  buckets_[ i ];
            }
        return 0;
    }


    template< class T>
    hash_node< T >* hash_table_const_iterator< T >::next(hash_node< T >* node)
    {
        for (size_t i = (node->hash_ % length_) + 1; i < length_; i++)
            if (buckets_[ i ])
            {
                return buckets_[ i ];
            }
        return 0;
    }


    template < class Key, class Value, class Hasher, class KeyEqual>
    inline void swap(
        hash_multimap < Key, Value, Hasher, KeyEqual>& x,
        hash_multimap < Key, Value, Hasher, KeyEqual>& y)
    {
        x.swap(y);
    }


    template < class Key, class T, class KeyOfValue, class Hasher, class KeyEqual>
    hash_node< T >* hash_table < Key, T, KeyOfValue, Hasher, KeyEqual>::first() const
    {
        if (size_ > 0)
            for (size_t i = 0; i < length_; i++)
                if (buckets_[ i ])
                {
                    return buckets_[ i ];
                }
        return 0;
    }


    template < class Key, class T, class KeyOfValue, class Hasher, class KeyEqual>
    void hash_table < Key, T, KeyOfValue, Hasher, KeyEqual>::clear()
    {
        for (size_t i = 0; i < length_; i++)
        {
            hash_node< T >* node = buckets_[ i ];

            while (node)
            {
                hash_node< T >* next = node->next_;

                delete node;
                node = next;
            }

            buckets_[ i ] = 0;
        }

        size_ = 0;
    }

    template < class Key, class T, class KeyOfValue, class Hasher, class KeyEqual>
    void hash_table < Key, T, KeyOfValue, Hasher, KeyEqual>::insert(
        const T* first,
        const T* last)
    {
        while (first != last)
        {
            insert(*first);
            first++;
        }
    }


    template < class Key, class T, class KeyOfValue, class Hasher, class KeyEqual>
    size_t hash_table < Key, T, KeyOfValue, Hasher, KeyEqual>::erase(const Key& key)
    {
        size_t hash = hash_value(key);
        size_t probe = hash % length_;

        hash_node< T >* node = buckets_[ probe ];
        hash_node< T >* previous = 0;
        for (; node; previous = node, node = node->next_)
            if (hash_key_equal(hash, key, node))
            {
                size_type count = 1;
                hash_node< T >* tmp = node;
                hash_node< T >* end = node->next_;

                delete tmp;

                while (end && hash_key_equal(hash, key, end))
                {
                    ++count;
                    tmp = end;
                    end = end->next_;
                    delete tmp;
                }
                if (previous)
                {
                    previous->next_ = end;
                }
                else
                {
                    buckets_[ probe ] = end;
                }

                size_ -= count;
                return count;
            }
        return 0;
    }


    template < class Key, class T, class KeyOfValue, class Hasher, class KeyEqual>
    void hash_table < Key, T, KeyOfValue, Hasher, KeyEqual>::erase(
        hash_table_iterator < T >  pos)
    {
        hash_node< T >* target = pos.node_;
        size_t probe = target->hash_ % length_;
        hash_node< T >* node = buckets_[ probe ];

        if (target == node)
        {
            buckets_[ probe ] = target->next_;
        }
        else
        {
            while (node->next_ != target)
            {
                node = node->next_;
            }

            node->next_ = target->next_;
        }

        delete target;
        --size_;
    }


    template < class Key, class T, class KeyOfValue, class Hasher, class KeyEqual>
    void hash_table < Key, T, KeyOfValue, Hasher, KeyEqual>::insert(
        hash_table_const_iterator<T>  first,
        hash_table_const_iterator<T>  last)
    {
        while (first != last)
        {
            insert(*first);
            first++;
        }
    }


    template < class Key, class T, class KeyOfValue, class Hasher, class KeyEqual>
    void hash_table < Key, T, KeyOfValue, Hasher, KeyEqual>::expand(size_t new_length)
    {
        if (!new_length)
        {
            new_length = length_ * 2 + 1;
        }

        hash_node< T >** new_buckets = allocate_node_ptr(new_length);

        for (size_t i = 0; i < length_; i++)
        {
            hash_node< T >* node = buckets_[ i ];

            while (node)
            {
                hash_node< T >* current = node;
                node = node->next_;
                size_t probe = current->hash_ % new_length;
                current->next_ = new_buckets[ probe ];
                new_buckets[ probe ] = current;
            }
        }

        deallocate_node_ptr(buckets_);
        buckets_ = new_buckets;
        length_ = new_length;
        limit_ = (size_type)(length_ * ratio_);
    }


    template < class Key, class T, class KeyOfValue, class Hasher, class KeyEqual>
    hash_node< T >** hash_table < Key, T, KeyOfValue, Hasher, KeyEqual>::allocate_node_ptr(size_t n)
    {
        hash_node< T >** z = new hash_node< T >* [n];
        hash_node< T >** y = z + n;

        while (y != z)
        {
            *--y = 0;
        }
        return z;
    }


    template < class Key, class T, class KeyOfValue, class Hasher, class KeyEqual>
    pair<hash_table_iterator<T>, bool> hash_table < Key, T, KeyOfValue, Hasher, KeyEqual>::insert(const T& value)
    {
        size_t hash = hash_value(key_of_value_(value));
        size_t probe = hash % length_;
        hash_node< T >* node;

        for (node = buckets_[ probe ]; node != 0; node = node->next_)
            if (hash_key_equal(hash, key_of_value_(value), node))
            {
                if (insert_always_)
                {
                    hash_node< T >* new_node = new hash_node< T >(value);
                    new_node->hash_ = hash;
                    new_node->next_ = node->next_;
                    node->next_ = new_node;

                    if (++size_ > limit_)
                    {
                        expand();
                    }

                    return  pair< iterator, bool >(iterator(buckets_, length_, new_node), true);
                }
                else
                {
                    return  pair< iterator, bool >(iterator(buckets_, length_, node), false);
                }
            }
        node = new hash_node< T >(value);
        node->hash_ = hash;
        node->next_ = buckets_[ probe ];

        buckets_[ probe ] = node;
        if (++size_ > limit_)
        {
            expand();
        }

        return pair< iterator, bool >(iterator(buckets_, length_, node), true);
    }

    template < class Key, class T, class KeyOfValue, class Hasher, class KeyEqual>
    hash_table_iterator <T> hash_table < Key, T, KeyOfValue, Hasher, KeyEqual>::find(const Key& key)
    {
        size_t hash = hash_value(key);
        hash_node< T >* node;

        for (node = buckets_[ hash % length_ ]; node != 0; node = node->next_)
            if (hash_key_equal(hash, key, node))
            {
                return  iterator(buckets_, length_, node);
            }

        return end();
    }
}


#endif