CVC3

hash_map.h

Go to the documentation of this file.
00001 /*****************************************************************************/
00002 /*!
00003  *\file hash_map.h
00004  *\brief hash map implementation
00005  *
00006  * Author: Alexander Fuchs
00007  *
00008  * Created: Fri Oct 13 11:04:00 2006
00009  *
00010  * <hr>
00011  *
00012  * License to use, copy, modify, sell and/or distribute this software
00013  * and its documentation for any purpose is hereby granted without
00014  * royalty, subject to the terms and conditions defined in the \ref
00015  * LICENSE file provided with this distribution.
00016  * 
00017  * <hr>
00018  */
00019 /*****************************************************************************/
00020 
00021 /*
00022  * Copyright (c) 1996,1997
00023  * Silicon Graphics Computer Systems, Inc.
00024  *
00025  * Permission to use, copy, modify, distribute and sell this software
00026  * and its documentation for any purpose is hereby granted without fee,
00027  * provided that the above copyright notice appear in all copies and
00028  * that both that copyright notice and this permission notice appear
00029  * in supporting documentation.  Silicon Graphics makes no
00030  * representations about the suitability of this software for any
00031  * purpose.  It is provided "as is" without express or implied warranty.
00032  *
00033  *
00034  * Copyright (c) 1994
00035  * Hewlett-Packard Company
00036  *
00037  * Permission to use, copy, modify, distribute and sell this software
00038  * and its documentation for any purpose is hereby granted without fee,
00039  * provided that the above copyright notice appear in all copies and
00040  * that both that copyright notice and this permission notice appear
00041  * in supporting documentation.  Hewlett-Packard Company makes no
00042  * representations about the suitability of this software for any
00043  * purpose.  It is provided "as is" without express or implied warranty.
00044  *
00045  */
00046 
00047 // this implementation is in essence a subset of the SGI implementation:
00048 // http://www.sgi.com/tech/stl/stl_hash_map.h
00049 
00050 #ifndef _cvc3__hash__hash_map_h_
00051 #define _cvc3__hash__hash_map_h_
00052 
00053 #include "hash_fun.h"
00054 #include "hash_table.h"
00055 #include <functional>
00056 #include <utility>
00057 
00058 namespace Hash {
00059 
00060   // select1st is an extension taken from the SGI
00061   // implementation of the STL file functional:
00062   // http://www.sgi.com/tech/stl/stl_function.h
00063   template <class _Pair>
00064   struct _Select1st : public std::unary_function<_Pair, typename _Pair::first_type> {
00065     const typename _Pair::first_type& operator()(const _Pair& __x) const {
00066       return __x.first;
00067     }
00068   };
00069 
00070 
00071   /*! hash map implementation based on the sgi interface:
00072     http://www.sgi.com/tech/stl/hash_map.html
00073 
00074     _Key: hash key type
00075     _Data: data to store
00076     _HashFcn: functional class providing a hash function: size_type (_Key)
00077     _EqualKey: functional class providing a comparison function: bool(_Key, _Key)
00078       returns true iff two keys are considered to be equal
00079   */
00080   template <class _Key, class _Data, class _HashFcn = hash<_Key>,
00081       class _EqualKey = std::equal_to<_Key> >
00082   class hash_map {
00083 
00084   /// types
00085   protected:
00086   // note: const _Key must be used for _Value and _ExtractKey.
00087   // if one is const and the other is not,
00088   // then extracting a key will require a conversion and a temporary
00089   // (at least in debug mode),
00090   // so that the reference returned by _ExtractKey point to a temporary.
00091   typedef hash_table<_Key, std::pair<const _Key, _Data>,
00092          _HashFcn, _EqualKey, _Select1st<std::pair<const _Key, _Data> > >
00093           _hash_table;
00094 
00095   public:
00096     // typedefs as custom for other implementations
00097     typedef typename _hash_table::size_type size_type;
00098     typedef typename _hash_table::key_type key_type;
00099     typedef _Data data_type;
00100     typedef typename _hash_table::value_type value_type;
00101     typedef typename _hash_table::hasher hasher;
00102     typedef typename _hash_table::key_equal key_equal;
00103 
00104   public:
00105     // iterators
00106     typedef typename _hash_table::iterator iterator;
00107     typedef typename _hash_table::const_iterator const_iterator;
00108 
00109   /// variables
00110 
00111   protected:
00112     // the hash table
00113     _hash_table d_table;
00114 
00115 
00116   /// methods
00117 
00118   public:
00119     /// constructors
00120 
00121     // default size is 16 buckets
00122     hash_map() :
00123       d_table()
00124     { };
00125     
00126     // specifiy initial number of buckets - must be positive
00127     hash_map(size_type initial_capacity) : 
00128       d_table(initial_capacity)
00129     { };
00130 
00131     // specifiy initial number of buckets and hash function
00132     hash_map(size_type initial_capacity, const _HashFcn& hash) : 
00133       d_table(initial_capacity, hash)
00134     { };
00135 
00136     // specifiy initial number of buckets, hash and equal function
00137     hash_map(size_type initial_capacity,
00138        const _HashFcn& hash, const _EqualKey& equal) : 
00139       d_table(initial_capacity, hash, equal)
00140     { };
00141 
00142     // copy hash map.
00143     hash_map(const hash_map& other) :
00144       d_table(other.d_table)
00145     { };
00146     
00147     // assign hash map
00148     hash_map& operator=(const hash_map& other) {
00149       if (this != &other) {
00150   d_table = other.d_table;
00151       }
00152 
00153       return *this;
00154     }
00155 
00156     void swap(hash_map& other) {
00157       d_table.swap(other.d_table);
00158     }
00159 
00160     // removes all entries, number of buckets is not reduced.
00161     void clear() {
00162       d_table.clear();
00163     };
00164 
00165 
00166 
00167     /// operations
00168 
00169     
00170     // returns end iterator if key was not bound
00171     iterator find(const key_type& key) {
00172       return d_table.find(key);
00173     }
00174     
00175     // const version of find
00176     const_iterator find(const key_type& key) const {
00177       return d_table.find(key);
00178     }
00179 
00180     // if key in value is already bound,
00181     // returns that binding,
00182     // otherwise inserts a default value and returns a reference to it.
00183     data_type& operator[](const key_type& key) {
00184       return d_table.find_or_insert(std::make_pair(key, data_type())).second;
00185     }
00186 
00187 
00188     // adds the mapping from key to data, if key is still unbound
00189     // otherwise returns false
00190     std::pair<iterator, bool> insert(const value_type& entry) {
00191       return d_table.insert(entry);
00192     }
00193 
00194     // removes binding of key
00195     // returns number of keys removed,
00196     // i.e. 1 if key was bound, 0 if key was not bound.
00197     size_type erase(const key_type& key) {
00198       return d_table.erase(key);
00199     }
00200 
00201     // removes element pointed to by iter,
00202     // returns element after iter.
00203     const_iterator erase(const const_iterator& i) {
00204       return d_table.erase(i);
00205     }
00206 
00207 
00208     /// status
00209 
00210     // is the key bound?
00211     bool contains(const key_type& key) const {
00212       return d_table.contains(key);
00213     }
00214 
00215     // returns the number of times a key is bound,
00216     // i.e. 0 or 1
00217     size_type count(const _Key& key) const {
00218       return d_table.count(key);
00219     }
00220   
00221     // is the hash map empty?
00222     bool empty() const {
00223       return d_table.empty();
00224     }
00225 
00226     // the number of elements in the hash map
00227     size_type size() const {
00228       return d_table.size();
00229     }
00230 
00231     // the number of buckets in the hash map
00232     size_type bucket_count() const {
00233       return d_table.bucket_count();
00234     }
00235 
00236     // returns the average number of elements per bucket
00237     float load_factor() const {
00238       return d_table.load_factor();
00239     }
00240 
00241 
00242 
00243     /// iterators
00244 
00245     // returns forward iterator to iterate over all key/data pairs
00246     iterator begin() {
00247       return d_table.begin();
00248     }
00249 
00250     // const version of begin
00251     const_iterator begin() const {
00252       return d_table.begin();
00253     }
00254 
00255 
00256     // returns end iterator
00257     iterator end() {
00258       return d_table.end();
00259     }
00260     
00261     // const version of end
00262     const_iterator end() const {
00263       return d_table.end();
00264     }
00265   };
00266 
00267 }
00268 
00269 #endif