• Skip to content
  • Skip to link menu
KDE 4.3 API Reference
  • KDE API Reference
  • kdelibs
  • Sitemap
  • Contact Us
 

WTF

HashSet.h

Go to the documentation of this file.
00001 // -*- mode: c++; c-basic-offset: 4 -*-
00002 /*
00003  * Copyright (C) 2005, 2006, 2007, 2008 Apple Inc. All rights reserved.
00004  *
00005  * This library is free software; you can redistribute it and/or
00006  * modify it under the terms of the GNU Library General Public
00007  * License as published by the Free Software Foundation; either
00008  * version 2 of the License, or (at your option) any later version.
00009  *
00010  * This library is distributed in the hope that it will be useful,
00011  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00012  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00013  * Library General Public License for more details.
00014  *
00015  * You should have received a copy of the GNU Library General Public License
00016  * along with this library; see the file COPYING.LIB.  If not, write to
00017  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
00018  * Boston, MA 02110-1301, USA.
00019  *
00020  */
00021 
00022 #ifndef WTF_HashSet_h
00023 #define WTF_HashSet_h
00024 
00025 #include "HashTable.h"
00026 
00027 namespace WTF {
00028 
00029     template<typename Value, typename HashFunctions, typename Traits> class HashSet;
00030     template<typename Value, typename HashFunctions, typename Traits>
00031     void deleteAllValues(const HashSet<Value, HashFunctions, Traits>&);
00032 
00033     template<typename T> struct IdentityExtractor;
00034 
00035     template<typename ValueArg, typename HashArg = typename DefaultHash<ValueArg>::Hash,
00036         typename TraitsArg = HashTraits<ValueArg> > class HashSet {
00037     private:
00038         typedef HashArg HashFunctions;
00039         typedef TraitsArg ValueTraits;
00040 
00041     public:
00042         typedef typename ValueTraits::TraitType ValueType;
00043 
00044     private:
00045         typedef HashTable<ValueType, ValueType, IdentityExtractor<ValueType>,
00046             HashFunctions, ValueTraits, ValueTraits> HashTableType;
00047 
00048     public:
00049         typedef HashTableIteratorAdapter<HashTableType, ValueType> iterator;
00050         typedef HashTableConstIteratorAdapter<HashTableType, ValueType> const_iterator;
00051 
00052         void swap(HashSet&);
00053 
00054         int size() const;
00055         int capacity() const;
00056         bool isEmpty() const;
00057 
00058         iterator begin();
00059         iterator end();
00060         const_iterator begin() const;
00061         const_iterator end() const;
00062 
00063         iterator find(const ValueType&);
00064         const_iterator find(const ValueType&) const;
00065         bool contains(const ValueType&) const;
00066 
00067         // An alternate version of find() that finds the object by hashing and comparing
00068         // with some other type, to avoid the cost of type conversion. HashTranslator
00069         // must have the following function members:
00070         //   static unsigned hash(const T&);
00071         //   static bool equal(const ValueType&, const T&);
00072         template<typename T, typename HashTranslator> iterator find(const T&);
00073         template<typename T, typename HashTranslator> const_iterator find(const T&) const;
00074         template<typename T, typename HashTranslator> bool contains(const T&) 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         // An alternate 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 must 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         friend void deleteAllValues<>(const HashSet&);
00094 
00095         HashTableType m_impl;
00096     };
00097 
00098     template<typename T> struct IdentityExtractor {
00099         static const T& extract(const T& t) { return t; }
00100     };
00101 
00102     template<typename ValueType, typename ValueTraits, typename T, typename Translator>
00103     struct HashSetTranslatorAdapter {
00104         static unsigned hash(const T& key) { return Translator::hash(key); }
00105         static bool equal(const ValueType& a, const T& b) { return Translator::equal(a, b); }
00106         static void translate(ValueType& location, const T& key, const T&, unsigned hashCode)
00107         {
00108             Translator::translate(location, key, hashCode);
00109         }
00110     };
00111 
00112     template<typename T, typename U, typename V>
00113     inline void HashSet<T, U, V>::swap(HashSet& other)
00114     {
00115         m_impl.swap(other.m_impl); 
00116     }
00117 
00118     template<typename T, typename U, typename V>
00119     inline int HashSet<T, U, V>::size() const
00120     {
00121         return m_impl.size(); 
00122     }
00123 
00124     template<typename T, typename U, typename V>
00125     inline int HashSet<T, U, V>::capacity() const
00126     {
00127         return m_impl.capacity(); 
00128     }
00129 
00130     template<typename T, typename U, typename V>
00131     inline bool HashSet<T, U, V>::isEmpty() const
00132     {
00133         return m_impl.isEmpty(); 
00134     }
00135 
00136     template<typename T, typename U, typename V>
00137     inline typename HashSet<T, U, V>::iterator HashSet<T, U, V>::begin()
00138     {
00139         return m_impl.begin(); 
00140     }
00141 
00142     template<typename T, typename U, typename V>
00143     inline typename HashSet<T, U, V>::iterator HashSet<T, U, V>::end()
00144     {
00145         return m_impl.end(); 
00146     }
00147 
00148     template<typename T, typename U, typename V>
00149     inline typename HashSet<T, U, V>::const_iterator HashSet<T, U, V>::begin() const
00150     {
00151         return m_impl.begin(); 
00152     }
00153 
00154     template<typename T, typename U, typename V>
00155     inline typename HashSet<T, U, V>::const_iterator HashSet<T, U, V>::end() const
00156     {
00157         return m_impl.end(); 
00158     }
00159 
00160     template<typename T, typename U, typename V>
00161     inline typename HashSet<T, U, V>::iterator HashSet<T, U, V>::find(const ValueType& value)
00162     {
00163         return m_impl.find(value); 
00164     }
00165 
00166     template<typename T, typename U, typename V>
00167     inline typename HashSet<T, U, V>::const_iterator HashSet<T, U, V>::find(const ValueType& value) const
00168     {
00169         return m_impl.find(value); 
00170     }
00171 
00172     template<typename T, typename U, typename V>
00173     inline bool HashSet<T, U, V>::contains(const ValueType& value) const
00174     {
00175         return m_impl.contains(value); 
00176     }
00177 
00178     template<typename Value, typename HashFunctions, typename Traits>
00179     template<typename T, typename Translator> 
00180     typename HashSet<Value, HashFunctions, Traits>::iterator
00181     inline HashSet<Value, HashFunctions, Traits>::find(const T& value)
00182     {
00183         typedef HashSetTranslatorAdapter<ValueType, ValueTraits, T, Translator> Adapter;
00184         return m_impl.find<T, Adapter>(value);
00185     }
00186 
00187     template<typename Value, typename HashFunctions, typename Traits>
00188     template<typename T, typename Translator> 
00189     typename HashSet<Value, HashFunctions, Traits>::const_iterator
00190     inline HashSet<Value, HashFunctions, Traits>::find(const T& value) const
00191     {
00192         typedef HashSetTranslatorAdapter<ValueType, ValueTraits, T, Translator> Adapter;
00193         return m_impl.find<T, Adapter>(value);
00194     }
00195 
00196     template<typename Value, typename HashFunctions, typename Traits>
00197     template<typename T, typename Translator> 
00198     inline bool HashSet<Value, HashFunctions, Traits>::contains(const T& value) const
00199     {
00200         typedef HashSetTranslatorAdapter<ValueType, ValueTraits, T, Translator> Adapter;
00201         return m_impl.contains<T, Adapter>(value);
00202     }
00203 
00204     template<typename T, typename U, typename V>
00205     pair<typename HashSet<T, U, V>::iterator, bool> HashSet<T, U, V>::add(const ValueType& value)
00206     {
00207         return m_impl.add(value);
00208     }
00209 
00210     template<typename Value, typename HashFunctions, typename Traits>
00211     template<typename T, typename Translator> 
00212     pair<typename HashSet<Value, HashFunctions, Traits>::iterator, bool>
00213     HashSet<Value, HashFunctions, Traits>::add(const T& value)
00214     {
00215         typedef HashSetTranslatorAdapter<ValueType, ValueTraits, T, Translator> Adapter;
00216         return m_impl.template addPassingHashCode<T, T, Adapter>(value, value);
00217     }
00218 
00219     template<typename T, typename U, typename V>
00220     inline void HashSet<T, U, V>::remove(iterator it)
00221     {
00222         if (it.m_impl == m_impl.end())
00223             return;
00224         m_impl.checkTableConsistency();
00225         m_impl.removeWithoutEntryConsistencyCheck(it.m_impl);
00226     }
00227 
00228     template<typename T, typename U, typename V>
00229     inline void HashSet<T, U, V>::remove(const ValueType& value)
00230     {
00231         remove(find(value));
00232     }
00233 
00234     template<typename T, typename U, typename V>
00235     inline void HashSet<T, U, V>::clear()
00236     {
00237         m_impl.clear(); 
00238     }
00239 
00240     template<typename ValueType, typename HashTableType>
00241     void deleteAllValues(HashTableType& collection)
00242     {
00243         typedef typename HashTableType::const_iterator iterator;
00244         iterator end = collection.end();
00245         for (iterator it = collection.begin(); it != end; ++it)
00246             delete *it;
00247     }
00248 
00249     template<typename T, typename U, typename V>
00250     inline void deleteAllValues(const HashSet<T, U, V>& collection)
00251     {
00252         deleteAllValues<typename HashSet<T, U, V>::ValueType>(collection.m_impl);
00253     }
00254     
00255     template<typename T, typename U, typename V, typename W>
00256     inline void copyToVector(const HashSet<T, U, V>& collection, W& vector)
00257     {
00258         typedef typename HashSet<T, U, V>::const_iterator iterator;
00259         
00260         vector.resize(collection.size());
00261         
00262         iterator it = collection.begin();
00263         iterator end = collection.end();
00264         for (unsigned i = 0; it != end; ++it, ++i)
00265             vector[i] = *it;
00266     }  
00267 
00268 } // namespace WTF
00269 
00270 using WTF::HashSet;
00271 
00272 #endif /* WTF_HashSet_h */

WTF

Skip menu "WTF"
  • Main Page
  • Namespace List
  • Class Hierarchy
  • Alphabetical List
  • Class List
  • File List
  • Namespace Members
  • Class Members
  • Related Pages

kdelibs

Skip menu "kdelibs"
  • DNSSD
  • Interfaces
  •   KHexEdit
  •   KMediaPlayer
  •   KSpeech
  •   KTextEditor
  • Kate
  • kconf_update
  • KDE3Support
  •   KUnitTest
  • KDECore
  • KDED
  • KDEsu
  • KDEUI
  • KDocTools
  • KFile
  • KHTML
  • KImgIO
  • KInit
  • kio
  • KIOSlave
  • KJS
  •   KJS-API
  •   WTF
  • kjsembed
  • KNewStuff
  • KParts
  • KPty
  • Kross
  • KUtils
  • Nepomuk
  • Plasma
  • Solid
  • Sonnet
  • ThreadWeaver
Generated for kdelibs by doxygen 1.6.1
This website is maintained by Adriaan de Groot and Allen Winter.
KDE® and the K Desktop Environment® logo are registered trademarks of KDE e.V. | Legal