hash_set.h

Go to the documentation of this file.
00001 /*****************************************************************************/
00002 /*!
00003  *\file hash_set.h
00004  *\brief hash map implementation
00005  *
00006  * Author: Alexander Fuchs
00007  *
00008  * Created: Thu Oct 19 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_set.h
00049 
00050 #ifndef _cvc3__hash__hash_set_h_
00051 #define _cvc3__hash__hash_set_h_
00052 
00053 
00054 #include "hash_fun.h"
00055 #include "hash_table.h"
00056 
00057 namespace Hash {
00058 
00059   // identity is an extension taken from the SGI
00060   // implementation of the STL file functional:
00061   // http://www.sgi.com/tech/stl/stl_function.h
00062   template <class _Tp>
00063   struct _Identity : public std::unary_function<_Tp,_Tp> {
00064     const _Tp& operator()(const _Tp& __x) const { return __x; }
00065   };
00066 
00067 
00068   /*! hash set implementation based on the sgi interface:
00069     http://www.sgi.com/tech/stl/hash_set.html
00070 
00071     _Key: hash key type
00072     _HashFcn: functional class providing a hash function: size_type (_Key)
00073     _EqualKey: functional class providing a comparison function: bool(_Key, _Key)
00074       returns true iff two keys are considered to be equal
00075   */
00076   template <class _Key, class _HashFcn = hash<_Key>,
00077       class _EqualKey = std::equal_to<_Key> >
00078   class hash_set {
00079 
00080   /// types
00081   protected:
00082   typedef hash_table<_Key, _Key, _HashFcn, _EqualKey, _Identity<_Key> > _hash_table;
00083 
00084   public:
00085     // typedefs as custom for other implementations
00086     typedef typename _hash_table::size_type size_type;
00087     typedef typename _hash_table::key_type key_type;
00088     typedef typename _hash_table::value_type value_type;
00089     typedef typename _hash_table::hasher hasher;
00090     typedef typename _hash_table::key_equal key_equal;
00091 
00092   public:
00093     // iterators
00094     typedef typename _hash_table::iterator iterator;
00095     typedef typename _hash_table::const_iterator const_iterator;
00096 
00097 
00098 
00099   /// variables
00100 
00101   protected:
00102     // the hash table
00103     _hash_table d_table;
00104 
00105 
00106   /// methods
00107 
00108   public:
00109     /// constructors
00110 
00111     // default size is 16 buckets
00112     hash_set() :
00113       d_table()
00114     { };
00115     
00116     // specifiy initial number of buckets - must be positive
00117     hash_set(size_type initial_capacity) : 
00118       d_table(initial_capacity)
00119     { };
00120 
00121     // specifiy initial number of buckets and hash function
00122     hash_set(size_type initial_capacity, const _HashFcn& hash) : 
00123       d_table(initial_capacity, hash)
00124     { };
00125 
00126     // specifiy initial number of buckets, hash and equal function
00127     hash_set(size_type initial_capacity,
00128        const _HashFcn& hash, const _EqualKey& equal) : 
00129       d_table(initial_capacity, hash, equal)
00130     { };
00131 
00132     // copy hash map.
00133     hash_set(const hash_set& other) :
00134       d_table(other.d_table)
00135     { };
00136     
00137     // assign hash map
00138     hash_set& operator=(const hash_set& other) {
00139       if (this != &other) {
00140   d_table = other.d_table;
00141       }
00142 
00143       return *this;
00144     }
00145 
00146     void swap(hash_set& other) {
00147       d_table.swap(other.d_table);
00148     }
00149 
00150     // removes all entries, number of buckets is not reduced.
00151     void clear() {
00152       d_table.clear();
00153     };
00154 
00155 
00156 
00157     /// operations
00158 
00159     
00160     // returns end iterator if key was not bound
00161     iterator find(const key_type& key) {
00162       return d_table.find(key);
00163     }
00164     
00165     // const version of find
00166     const_iterator find(const key_type& key) const {
00167       return d_table.find(key);
00168     }
00169 
00170 
00171     // adds the mapping from key to data, if key is still unbound
00172     // otherwise returns false
00173     std::pair<iterator, bool> insert(const value_type& entry) {
00174       return d_table.insert(entry);
00175     }
00176 
00177     // removes binding of key
00178     // returns number of keys removed,
00179     // i.e. 1 if key was bound, 0 if key was not bound.
00180     size_type erase(const key_type& key) {
00181       return d_table.erase(key);
00182     }
00183 
00184 
00185 
00186     /// status
00187 
00188     // is the key bound?
00189     bool contains(const key_type& key) const {
00190       return d_table.contains(key);
00191     }
00192 
00193     // returns the number of times a key is bound,
00194     // i.e. 0 or 1
00195     size_type count(const _Key& key) const {
00196       return d_table.count(key);
00197     }
00198   
00199     // is the hash map empty?
00200     bool empty() const {
00201       return d_table.empty();
00202     }
00203 
00204     // the number of elements in the hash map
00205     size_type size() const {
00206       return d_table.size();
00207     }
00208 
00209     // the number of buckets in the hash map
00210     size_type bucket_count() const {
00211       return d_table.bucket_count();
00212     }
00213 
00214     // returns the average number of elements per bucket
00215     float load_factor() const {
00216       return d_table.load_factor();
00217     }
00218 
00219 
00220 
00221     /// iterators
00222 
00223     // returns forward iterator to iterate over all key/data pairs
00224     iterator begin() {
00225       return d_table.begin();
00226     }
00227 
00228     // const version of begin
00229     const_iterator begin() const {
00230       return d_table.begin();
00231     }
00232 
00233 
00234     // returns end iterator
00235     iterator end() {
00236       return d_table.end();
00237     }
00238     
00239     // const version of end
00240     const_iterator end() const {
00241       return d_table.end();
00242     }
00243   };
00244 
00245 }
00246 
00247 #endif

Generated on Tue Jul 3 14:33:37 2007 for CVC3 by  doxygen 1.5.1