table.hh

Go to the documentation of this file.

/* -*- C++ -*-
 * $Id: table.hh 957 2005-03-07 16:01:20Z sjoyeux $
 */
#ifndef UTILMM_UTILS_HASH_TABLE_HEADER
# define UTILMM_UTILS_HASH_TABLE_HEADER

# include <utility> 
# include <vector>

#include "utilmm/functional/arg_traits.hh"

#include "utilmm/hash/hash_fwd.hh"
#include "utilmm/hash/bits/iter.hh"

namespace utilmm {
  namespace hash_toolbox {

    template<typename Value>
    struct node {
      explicit node(Value const &v, node *n=0);

      Value val;
      node *next;
    }; // struct utilmm::hash_toolbox::node<>
    
    template<typename Key, typename Value, 
             class Extract, class Hash, class Equal>
    class table {
    public:
      typedef Value  value_type;
      typedef Key    key_type;
      typedef size_t size_type;
      
      typedef typename arg_traits<value_type>::type value_arg;
      typedef typename arg_traits<key_type>::type key_arg;

    private:
      typedef node<value_type> node_type;
      typedef std::vector<node_type *> bucket_type;

    public:
      typedef iter<Key, Value, Extract, Hash, Equal>       iterator;
      typedef const_iter<Key, Value, Extract, Hash, Equal> const_iterator;
      
      table();
      table(table const &);
      
      ~table();

      void swap(table &other);
      table &operator= (table const &other);
      
      size_type size() const;
      size_type max_size() const;

      bool empty() const;

      iterator begin();
      iterator end();

      const_iterator begin() const;
      const_iterator end() const;

      std::pair<iterator, iterator> equal_range(key_arg key);
      std::pair< const_iterator,
                 const_iterator > equal_range(key_arg key) const;

      void erase(iterator const &first, iterator const &last);

      std::pair<iterator, bool> insert_unique(value_arg v);
      iterator insert_multiple(value_arg v);

      void clear();

    private:
      bucket_type bucket;
      size_type   node_count, avg_bucket_count;
      
      void resize(size_type size);
      
      node_type *insert(node_type **helper, value_arg v);
      
      static size_t hash_key(key_arg k, size_type mod);
      static size_t hash_node(value_arg v, size_type mod);
      static key_type const &get_key(value_arg v);

      static bucket_type copy_bucket(bucket_type const &other);

      size_t hash_node(value_arg v);
      
      node_type **find_node(key_arg k);
      node_type *find_node(key_arg k) const;

      template<typename K, typename V, class Ex, class H, class Eq>
      friend class iter;
      
      template<typename K, typename V, class Ex, class H, class Eq>
      friend class const_iter;
    }; // class utilmm::hash_toolbox::table<>

  } // namespace utilmm::hash_toolbox
} // namespace utilmm

# define IN_UTILMM_UTILS_HASH_TABLE_HEADER
#include "utilmm/hash/bits/table.tcc"
# undef IN_UTILMM_UTILS_HASH_TABLE_HEADER
#endif // UTILMM_UTILS_HASH_TABLE_HEADER