00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
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
00068
00069
00070
00071
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
00077
00078 pair<iterator, bool> add(const ValueType&);
00079
00080
00081
00082
00083
00084
00085
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 }
00269
00270 using WTF::HashSet;
00271
00272 #endif