WTF

HashSet.h

00001 // -*- mode: c++; c-basic-offset: 4 -*-
00002 /*
00003  * This file is part of the KDE libraries
00004  *
00005  * Copyright (C) 2005, 2006 Apple Computer, Inc.
00006  *
00007  * This library is free software; you can redistribute it and/or
00008  * modify it under the terms of the GNU Library General Public
00009  * License as published by the Free Software Foundation; either
00010  * version 2 of the License, or (at your option) any later version.
00011  *
00012  * This library is distributed in the hope that it will be useful,
00013  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00014  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00015  * Library General Public License for more details.
00016  *
00017  * You should have received a copy of the GNU Library General Public License
00018  * along with this library; see the file COPYING.LIB.  If not, write to
00019  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
00020  * Boston, MA 02110-1301, USA.
00021  *
00022  */
00023 
00024 #ifndef WTF_HashSet_h
00025 #define WTF_HashSet_h
00026 
00027 #include "HashTable.h"
00028 
00029 namespace WTF {
00030 
00031     template<typename T> struct IdentityExtractor;
00032 
00033     template<typename Value, typename HashFunctions, typename Traits> class HashSet;
00034     template<typename Value, typename HashFunctions, typename Traits>
00035     void deleteAllValues(const HashSet<Value, HashFunctions, Traits>&);
00036 
00037     template<typename ValueArg, typename HashArg = typename DefaultHash<ValueArg>::Hash,
00038         typename TraitsArg = HashTraits<ValueArg> > class HashSet {
00039     private:
00040         typedef HashArg HashFunctions;
00041         typedef TraitsArg ValueTraits;
00042 
00043         typedef typename HashKeyStorageTraits<HashFunctions, ValueTraits>::Hash StorageHashFunctions;
00044 
00045         typedef typename HashKeyStorageTraits<HashFunctions, ValueTraits>::Traits StorageTraits;
00046         typedef typename StorageTraits::TraitType StorageType;
00047 
00048         typedef HashTable<StorageType, StorageType, IdentityExtractor<StorageType>,
00049             StorageHashFunctions, StorageTraits, StorageTraits> HashTableType;
00050 
00051     public:
00052         typedef typename ValueTraits::TraitType ValueType;
00053         typedef HashTableIteratorAdapter<HashTableType, ValueType> iterator;
00054         typedef HashTableConstIteratorAdapter<HashTableType, ValueType> const_iterator;
00055 
00056         HashSet();
00057         HashSet(const HashSet&);
00058         HashSet& operator=(const HashSet&);
00059         ~HashSet();
00060 
00061         void swap(HashSet&);
00062 
00063         int size() const;
00064         int capacity() const;
00065         bool isEmpty() const;
00066 
00067         iterator begin();
00068         iterator end();
00069         const_iterator begin() const;
00070         const_iterator end() const;
00071 
00072         iterator find(const ValueType&);
00073         const_iterator find(const ValueType&) const;
00074         bool contains(const ValueType&) const;
00075 
00076         // the return value is a pair of an interator to the new value's location, 
00077         // and a bool that is true if an new entry was added
00078         pair<iterator, bool> add(const ValueType&);
00079 
00080         // a special version of add() that finds the object by hashing and comparing
00081         // with some other type, to avoid the cost of type conversion if the object is already
00082         // in the table. HashTranslator should have the following methods:
00083         //   static unsigned hash(const T&);
00084         //   static bool equal(const ValueType&, const T&);
00085         //   static translate(ValueType&, const T&, unsigned hashCode);
00086         template<typename T, typename HashTranslator> pair<iterator, bool> add(const T&);
00087 
00088         void remove(const ValueType&);
00089         void remove(iterator);
00090         void clear();
00091 
00092     private:
00093         void refAll();
00094         void derefAll();
00095 
00096         friend void deleteAllValues<>(const HashSet&);
00097 
00098         HashTableType m_impl;
00099     };
00100 
00101     template<typename T> struct IdentityExtractor {
00102         static const T& extract(const T& t) { return t; }
00103     };
00104 
00105     template<bool canReplaceDeletedValue, typename ValueType, typename ValueTraits, typename StorageTraits, typename HashFunctions>
00106     struct HashSetTranslator;
00107 
00108     template<typename ValueType, typename ValueTraits, typename StorageTraits, typename HashFunctions>
00109     struct HashSetTranslator<true, ValueType, ValueTraits, StorageTraits, HashFunctions> {
00110         typedef typename StorageTraits::TraitType StorageType;
00111         static unsigned hash(const ValueType& key) { return HashFunctions::hash(key); }
00112         static bool equal(const StorageType& a, const ValueType& b) { return HashFunctions::equal(*(const ValueType*)&a, b); }
00113         static void translate(StorageType& location, const ValueType& key, const ValueType&, unsigned)
00114         {
00115             Assigner<ValueTraits::needsRef, ValueType, StorageType, ValueTraits>::assign(key, location);
00116         }
00117     };
00118 
00119     template<typename ValueType, typename ValueTraits, typename StorageTraits, typename HashFunctions>
00120     struct HashSetTranslator<false, ValueType, ValueTraits, StorageTraits, HashFunctions> {
00121         typedef typename StorageTraits::TraitType StorageType;
00122         static unsigned hash(const ValueType& key) { return HashFunctions::hash(key); }
00123         static bool equal(const StorageType& a, const ValueType& b) { return HashFunctions::equal(*(const ValueType*)&a, b); }
00124         static void translate(StorageType& location, const ValueType& key, const ValueType&, unsigned)
00125         {
00126             if (location == StorageTraits::deletedValue())
00127                 location = StorageTraits::emptyValue();
00128             Assigner<ValueTraits::needsRef, ValueType, StorageType, ValueTraits>::assign(key, location);
00129         }
00130     };
00131 
00132     template<bool canReplaceDeletedValue, typename ValueType, typename StorageTraits, typename T, typename Translator>
00133     struct HashSetTranslatorAdapter;
00134 
00135     template<typename ValueType, typename StorageTraits, typename T, typename Translator>
00136     struct HashSetTranslatorAdapter<true, ValueType, StorageTraits, T, Translator> {
00137         typedef typename StorageTraits::TraitType StorageType;
00138         static unsigned hash(const T& key) { return Translator::hash(key); }
00139         static bool equal(const StorageType& a, const T& b) { return Translator::equal(*(const ValueType*)&a, b); }
00140         static void translate(StorageType& location, const T& key, const T&, unsigned hashCode)
00141         {
00142             Translator::translate(*(ValueType*)&location, key, hashCode);
00143         }
00144     };
00145 
00146     template<typename ValueType, typename StorageTraits, typename T, typename Translator>
00147     struct HashSetTranslatorAdapter<false, ValueType, StorageTraits, T, Translator> {
00148         typedef typename StorageTraits::TraitType StorageType;
00149         static unsigned hash(const T& key) { return Translator::hash(key); }
00150         static bool equal(const StorageType& a, const T& b) { return Translator::equal(*(const ValueType*)&a, b); }
00151         static void translate(StorageType& location, const T& key, const T&, unsigned hashCode)
00152         {
00153             if (location == StorageTraits::deletedValue())
00154                 location = StorageTraits::emptyValue();
00155             Translator::translate(*(ValueType*)&location, key, hashCode);
00156         }
00157     };
00158 
00159     template<typename T, typename U, typename V>
00160     inline void HashSet<T, U, V>::refAll()
00161     {
00162         HashTableRefCounter<HashTableType, ValueTraits>::refAll(m_impl);
00163     }
00164 
00165     template<typename T, typename U, typename V>
00166     inline void HashSet<T, U, V>::derefAll()
00167     {
00168         HashTableRefCounter<HashTableType, ValueTraits>::derefAll(m_impl);
00169     }
00170 
00171     template<typename T, typename U, typename V>
00172     inline HashSet<T, U, V>::HashSet()
00173     {
00174     }
00175 
00176     template<typename T, typename U, typename V>
00177     inline HashSet<T, U, V>::HashSet(const HashSet& other)
00178         : m_impl(other.m_impl)
00179     {
00180         refAll();
00181     }
00182 
00183     template<typename T, typename U, typename V>
00184     inline HashSet<T, U, V>& HashSet<T, U, V>::operator=(const HashSet& other)
00185     {
00186         HashSet tmp(other);
00187         swap(tmp); 
00188         return *this;
00189     }
00190 
00191     template<typename T, typename U, typename V>
00192     inline void HashSet<T, U, V>::swap(HashSet& other)
00193     {
00194         m_impl.swap(other.m_impl); 
00195     }
00196 
00197     template<typename T, typename U, typename V>
00198     inline HashSet<T, U, V>::~HashSet()
00199     {
00200         derefAll();
00201     }
00202 
00203     template<typename T, typename U, typename V>
00204     inline int HashSet<T, U, V>::size() const
00205     {
00206         return m_impl.size(); 
00207     }
00208 
00209     template<typename T, typename U, typename V>
00210     inline int HashSet<T, U, V>::capacity() const
00211     {
00212         return m_impl.capacity(); 
00213     }
00214 
00215     template<typename T, typename U, typename V>
00216     inline bool HashSet<T, U, V>::isEmpty() const
00217     {
00218         return m_impl.isEmpty(); 
00219     }
00220 
00221     template<typename T, typename U, typename V>
00222     inline typename HashSet<T, U, V>::iterator HashSet<T, U, V>::begin()
00223     {
00224         return m_impl.begin(); 
00225     }
00226 
00227     template<typename T, typename U, typename V>
00228     inline typename HashSet<T, U, V>::iterator HashSet<T, U, V>::end()
00229     {
00230         return m_impl.end(); 
00231     }
00232 
00233     template<typename T, typename U, typename V>
00234     inline typename HashSet<T, U, V>::const_iterator HashSet<T, U, V>::begin() const
00235     {
00236         return m_impl.begin(); 
00237     }
00238 
00239     template<typename T, typename U, typename V>
00240     inline typename HashSet<T, U, V>::const_iterator HashSet<T, U, V>::end() const
00241     {
00242         return m_impl.end(); 
00243     }
00244 
00245     template<typename T, typename U, typename V>
00246     inline typename HashSet<T, U, V>::iterator HashSet<T, U, V>::find(const ValueType& value)
00247     {
00248         return m_impl.find(*(const StorageType*)&value); 
00249     }
00250 
00251     template<typename T, typename U, typename V>
00252     inline typename HashSet<T, U, V>::const_iterator HashSet<T, U, V>::find(const ValueType& value) const
00253     {
00254         return m_impl.find(*(const StorageType*)&value); 
00255     }
00256 
00257     template<typename T, typename U, typename V>
00258     inline bool HashSet<T, U, V>::contains(const ValueType& value) const
00259     {
00260         return m_impl.contains(*(const StorageType*)&value); 
00261     }
00262 
00263     template<typename T, typename U, typename V>
00264     pair<typename HashSet<T, U, V>::iterator, bool> HashSet<T, U, V>::add(const ValueType &value)
00265     {
00266         const bool canReplaceDeletedValue = !ValueTraits::needsDestruction || StorageTraits::needsDestruction;
00267         typedef HashSetTranslator<canReplaceDeletedValue, ValueType, ValueTraits, StorageTraits, HashFunctions> Translator;
00268         return m_impl.template add<ValueType, ValueType, Translator>(value, value);
00269     }
00270 
00271     template<typename Value, typename HashFunctions, typename Traits>
00272     template<typename T, typename Translator> 
00273     pair<typename HashSet<Value, HashFunctions, Traits>::iterator, bool>
00274     HashSet<Value, HashFunctions, Traits>::add(const T& value)
00275     {
00276         const bool canReplaceDeletedValue = !ValueTraits::needsDestruction || StorageTraits::needsDestruction;
00277         typedef HashSetTranslatorAdapter<canReplaceDeletedValue, ValueType, StorageTraits, T, Translator> Adapter;
00278         return m_impl.template add<T, T, Adapter>(value, value);
00279     }
00280 
00281     template<typename T, typename U, typename V>
00282     inline void HashSet<T, U, V>::remove(iterator it)
00283     {
00284         if (it.m_impl == m_impl.end())
00285             return;
00286         RefCounter<ValueTraits, StorageTraits>::deref(*it.m_impl);
00287         m_impl.remove(it.m_impl);
00288     }
00289 
00290     template<typename T, typename U, typename V>
00291     inline void HashSet<T, U, V>::remove(const ValueType& value)
00292     {
00293         remove(find(value));
00294     }
00295 
00296     template<typename T, typename U, typename V>
00297     inline void HashSet<T, U, V>::clear()
00298     {
00299         derefAll();
00300         m_impl.clear(); 
00301     }
00302 
00303     template<typename ValueType, typename HashTableType>
00304     void deleteAllValues(HashTableType& collection)
00305     {
00306         typedef typename HashTableType::const_iterator iterator;
00307         iterator end = collection.end();
00308         for (iterator it = collection.begin(); it != end; ++it)
00309             delete *(ValueType*)&*it;
00310     }
00311 
00312     template<typename T, typename U, typename V>
00313     inline void deleteAllValues(const HashSet<T, U, V>& collection)
00314     {
00315         deleteAllValues<typename HashSet<T, U, V>::ValueType>(collection.m_impl);
00316     }
00317 
00318 } // namespace WTF
00319 
00320 using WTF::HashSet;
00321 
00322 #endif /* WTF_HashSet_h */
WTF

HashSet.h

WTF

kdelibs
