00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023 #ifndef WTF_HashCountedSet_h
00024 #define WTF_HashCountedSet_h
00025
00026 #include "Assertions.h"
00027 #include "HashMap.h"
00028 #include "Vector.h"
00029
00030 namespace WTF {
00031
00032 template<typename Value, typename HashFunctions = typename DefaultHash<Value>::Hash,
00033 typename Traits = HashTraits<Value> > class HashCountedSet {
00034 private:
00035 typedef HashMap<Value, unsigned, HashFunctions, Traits> ImplType;
00036 public:
00037 typedef Value ValueType;
00038 typedef typename ImplType::iterator iterator;
00039 typedef typename ImplType::const_iterator const_iterator;
00040
00041 HashCountedSet() {}
00042
00043 int size() const;
00044 int capacity() const;
00045 bool isEmpty() const;
00046
00047
00048 iterator begin();
00049 iterator end();
00050 const_iterator begin() const;
00051 const_iterator end() const;
00052
00053 iterator find(const ValueType& value);
00054 const_iterator find(const ValueType& value) const;
00055 bool contains(const ValueType& value) const;
00056 unsigned count(const ValueType& value) const;
00057
00058
00059
00060
00061 std::pair<iterator, bool> add(const ValueType &value);
00062
00063
00064
00065 void remove(const ValueType& value);
00066 void remove(iterator it);
00067
00068 void clear();
00069
00070 private:
00071 ImplType m_impl;
00072 };
00073
00074 template<typename Value, typename HashFunctions, typename Traits>
00075 inline int HashCountedSet<Value, HashFunctions, Traits>::size() const
00076 {
00077 return m_impl.size();
00078 }
00079
00080 template<typename Value, typename HashFunctions, typename Traits>
00081 inline int HashCountedSet<Value, HashFunctions, Traits>::capacity() const
00082 {
00083 return m_impl.capacity();
00084 }
00085
00086 template<typename Value, typename HashFunctions, typename Traits>
00087 inline bool HashCountedSet<Value, HashFunctions, Traits>::isEmpty() const
00088 {
00089 return size() == 0;
00090 }
00091
00092 template<typename Value, typename HashFunctions, typename Traits>
00093 inline typename HashCountedSet<Value, HashFunctions, Traits>::iterator HashCountedSet<Value, HashFunctions, Traits>::begin()
00094 {
00095 return m_impl.begin();
00096 }
00097
00098 template<typename Value, typename HashFunctions, typename Traits>
00099 inline typename HashCountedSet<Value, HashFunctions, Traits>::iterator HashCountedSet<Value, HashFunctions, Traits>::end()
00100 {
00101 return m_impl.end();
00102 }
00103
00104 template<typename Value, typename HashFunctions, typename Traits>
00105 inline typename HashCountedSet<Value, HashFunctions, Traits>::const_iterator HashCountedSet<Value, HashFunctions, Traits>::begin() const
00106 {
00107 return m_impl.begin();
00108 }
00109
00110 template<typename Value, typename HashFunctions, typename Traits>
00111 inline typename HashCountedSet<Value, HashFunctions, Traits>::const_iterator HashCountedSet<Value, HashFunctions, Traits>::end() const
00112 {
00113 return m_impl.end();
00114 }
00115
00116 template<typename Value, typename HashFunctions, typename Traits>
00117 inline typename HashCountedSet<Value, HashFunctions, Traits>::iterator HashCountedSet<Value, HashFunctions, Traits>::find(const ValueType& value)
00118 {
00119 return m_impl.find(value);
00120 }
00121
00122 template<typename Value, typename HashFunctions, typename Traits>
00123 inline typename HashCountedSet<Value, HashFunctions, Traits>::const_iterator HashCountedSet<Value, HashFunctions, Traits>::find(const ValueType& value) const
00124 {
00125 return m_impl.find(value);
00126 }
00127
00128 template<typename Value, typename HashFunctions, typename Traits>
00129 inline bool HashCountedSet<Value, HashFunctions, Traits>::contains(const ValueType& value) const
00130 {
00131 return m_impl.contains(value);
00132 }
00133
00134 template<typename Value, typename HashFunctions, typename Traits>
00135 inline unsigned HashCountedSet<Value, HashFunctions, Traits>::count(const ValueType& value) const
00136 {
00137 return m_impl.get(value);
00138 }
00139
00140 template<typename Value, typename HashFunctions, typename Traits>
00141 inline std::pair<typename HashCountedSet<Value, HashFunctions, Traits>::iterator, bool> HashCountedSet<Value, HashFunctions, Traits>::add(const ValueType &value)
00142 {
00143 pair<iterator, bool> result = m_impl.add(value, 0);
00144 ++result.first->second;
00145 return result;
00146 }
00147
00148 template<typename Value, typename HashFunctions, typename Traits>
00149 inline void HashCountedSet<Value, HashFunctions, Traits>::remove(const ValueType& value)
00150 {
00151 remove(find(value));
00152 }
00153
00154 template<typename Value, typename HashFunctions, typename Traits>
00155 inline void HashCountedSet<Value, HashFunctions, Traits>::remove(iterator it)
00156 {
00157 if (it == end())
00158 return;
00159
00160 unsigned oldVal = it->second;
00161 ASSERT(oldVal != 0);
00162 unsigned newVal = oldVal - 1;
00163 if (newVal == 0)
00164 m_impl.remove(it);
00165 else
00166 it->second = newVal;
00167 }
00168
00169 template<typename Value, typename HashFunctions, typename Traits>
00170 inline void HashCountedSet<Value, HashFunctions, Traits>::clear()
00171 {
00172 m_impl.clear();
00173 }
00174
00175 template<typename Value, typename HashFunctions, typename Traits, typename VectorType>
00176 inline void copyToVector(const HashCountedSet<Value, HashFunctions, Traits>& collection, VectorType& vector)
00177 {
00178 typedef typename HashCountedSet<Value, HashFunctions, Traits>::const_iterator iterator;
00179
00180 vector.resize(collection.size());
00181
00182 iterator it = collection.begin();
00183 iterator end = collection.end();
00184 for (unsigned i = 0; it != end; ++it, ++i)
00185 vector[i] = *it;
00186 }
00187
00188 template<typename Value, typename HashFunctions, typename Traits>
00189 inline void copyToVector(const HashCountedSet<Value, HashFunctions, Traits>& collection, Vector<Value>& vector)
00190 {
00191 typedef typename HashCountedSet<Value, HashFunctions, Traits>::const_iterator iterator;
00192
00193 vector.resize(collection.size());
00194
00195 iterator it = collection.begin();
00196 iterator end = collection.end();
00197 for (unsigned i = 0; it != end; ++it, ++i)
00198 vector[i] = (*it).first;
00199 }
00200
00201
00202 }
00203
00204 using WTF::HashCountedSet;
00205
00206 #endif