1 /* 2 * Copyright (C) 2005, 2006, 2008 Apple Inc. All rights reserved. 3 * 4 * This library is free software; you can redistribute it and/or 5 * modify it under the terms of the GNU Library General Public 6 * License as published by the Free Software Foundation; either 7 * version 2 of the License, or (at your option) any later version. 8 * 9 * This library is distributed in the hope that it will be useful, 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of 11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 12 * Library General Public License for more details. 13 * 14 * You should have received a copy of the GNU Library General Public License 15 * along with this library; see the file COPYING.LIB. If not, write to 16 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, 17 * Boston, MA 02110-1301, USA. 18 * 19 */ 20 21 #ifndef WTF_HashCountedSet_h 22 #define WTF_HashCountedSet_h 23 24 #include "Assertions.h" 25 #include "HashMap.h" 26 #include "Vector.h" 27 28 namespace WTF { 29 30 template<typename Value, typename HashFunctions = typename DefaultHash<Value>::Hash, 31 typename Traits = HashTraits<Value> > class HashCountedSet { 32 WTF_MAKE_FAST_ALLOCATED; 33 private: 34 typedef HashMap<Value, unsigned, HashFunctions, Traits> ImplType; 35 public: 36 typedef Value ValueType; 37 typedef typename ImplType::iterator iterator; 38 typedef typename ImplType::const_iterator const_iterator; 39 HashCountedSet()40 HashCountedSet() {} 41 42 int size() const; 43 int capacity() const; 44 bool isEmpty() const; 45 46 // Iterators iterate over pairs of values and counts. 47 iterator begin(); 48 iterator end(); 49 const_iterator begin() const; 50 const_iterator end() const; 51 52 iterator find(const ValueType&); 53 const_iterator find(const ValueType&) const; 54 bool contains(const ValueType&) const; 55 unsigned count(const ValueType&) const; 56 57 // Increases the count if an equal value is already present 58 // the return value is a pair of an interator to the new value's 59 // location, and a bool that is true if an new entry was added. 60 std::pair<iterator, bool> add(const ValueType&); 61 62 // Reduces the count of the value, and removes it if count 63 // goes down to zero, returns true if the value is removed. 64 bool remove(const ValueType&); 65 bool remove(iterator); 66 67 // Removes the value, regardless of its count. 68 void removeAll(iterator); 69 void removeAll(const ValueType&); 70 71 // Clears the whole set. 72 void clear(); 73 74 private: 75 ImplType m_impl; 76 }; 77 78 template<typename Value, typename HashFunctions, typename Traits> size()79 inline int HashCountedSet<Value, HashFunctions, Traits>::size() const 80 { 81 return m_impl.size(); 82 } 83 84 template<typename Value, typename HashFunctions, typename Traits> capacity()85 inline int HashCountedSet<Value, HashFunctions, Traits>::capacity() const 86 { 87 return m_impl.capacity(); 88 } 89 90 template<typename Value, typename HashFunctions, typename Traits> isEmpty()91 inline bool HashCountedSet<Value, HashFunctions, Traits>::isEmpty() const 92 { 93 return size() == 0; 94 } 95 96 template<typename Value, typename HashFunctions, typename Traits> begin()97 inline typename HashCountedSet<Value, HashFunctions, Traits>::iterator HashCountedSet<Value, HashFunctions, Traits>::begin() 98 { 99 return m_impl.begin(); 100 } 101 102 template<typename Value, typename HashFunctions, typename Traits> end()103 inline typename HashCountedSet<Value, HashFunctions, Traits>::iterator HashCountedSet<Value, HashFunctions, Traits>::end() 104 { 105 return m_impl.end(); 106 } 107 108 template<typename Value, typename HashFunctions, typename Traits> begin()109 inline typename HashCountedSet<Value, HashFunctions, Traits>::const_iterator HashCountedSet<Value, HashFunctions, Traits>::begin() const 110 { 111 return m_impl.begin(); 112 } 113 114 template<typename Value, typename HashFunctions, typename Traits> end()115 inline typename HashCountedSet<Value, HashFunctions, Traits>::const_iterator HashCountedSet<Value, HashFunctions, Traits>::end() const 116 { 117 return m_impl.end(); 118 } 119 120 template<typename Value, typename HashFunctions, typename Traits> find(const ValueType & value)121 inline typename HashCountedSet<Value, HashFunctions, Traits>::iterator HashCountedSet<Value, HashFunctions, Traits>::find(const ValueType& value) 122 { 123 return m_impl.find(value); 124 } 125 126 template<typename Value, typename HashFunctions, typename Traits> find(const ValueType & value)127 inline typename HashCountedSet<Value, HashFunctions, Traits>::const_iterator HashCountedSet<Value, HashFunctions, Traits>::find(const ValueType& value) const 128 { 129 return m_impl.find(value); 130 } 131 132 template<typename Value, typename HashFunctions, typename Traits> contains(const ValueType & value)133 inline bool HashCountedSet<Value, HashFunctions, Traits>::contains(const ValueType& value) const 134 { 135 return m_impl.contains(value); 136 } 137 138 template<typename Value, typename HashFunctions, typename Traits> count(const ValueType & value)139 inline unsigned HashCountedSet<Value, HashFunctions, Traits>::count(const ValueType& value) const 140 { 141 return m_impl.get(value); 142 } 143 144 template<typename Value, typename HashFunctions, typename Traits> add(const ValueType & value)145 inline std::pair<typename HashCountedSet<Value, HashFunctions, Traits>::iterator, bool> HashCountedSet<Value, HashFunctions, Traits>::add(const ValueType &value) 146 { 147 pair<iterator, bool> result = m_impl.add(value, 0); 148 ++result.first->second; 149 return result; 150 } 151 152 template<typename Value, typename HashFunctions, typename Traits> remove(const ValueType & value)153 inline bool HashCountedSet<Value, HashFunctions, Traits>::remove(const ValueType& value) 154 { 155 return remove(find(value)); 156 } 157 158 template<typename Value, typename HashFunctions, typename Traits> remove(iterator it)159 inline bool HashCountedSet<Value, HashFunctions, Traits>::remove(iterator it) 160 { 161 if (it == end()) 162 return false; 163 164 unsigned oldVal = it->second; 165 ASSERT(oldVal); 166 unsigned newVal = oldVal - 1; 167 if (newVal) { 168 it->second = newVal; 169 return false; 170 } 171 172 m_impl.remove(it); 173 return true; 174 } 175 176 template<typename Value, typename HashFunctions, typename Traits> removeAll(const ValueType & value)177 inline void HashCountedSet<Value, HashFunctions, Traits>::removeAll(const ValueType& value) 178 { 179 removeAll(find(value)); 180 } 181 182 template<typename Value, typename HashFunctions, typename Traits> removeAll(iterator it)183 inline void HashCountedSet<Value, HashFunctions, Traits>::removeAll(iterator it) 184 { 185 if (it == end()) 186 return; 187 188 m_impl.remove(it); 189 } 190 191 template<typename Value, typename HashFunctions, typename Traits> clear()192 inline void HashCountedSet<Value, HashFunctions, Traits>::clear() 193 { 194 m_impl.clear(); 195 } 196 197 template<typename Value, typename HashFunctions, typename Traits, typename VectorType> copyToVector(const HashCountedSet<Value,HashFunctions,Traits> & collection,VectorType & vector)198 inline void copyToVector(const HashCountedSet<Value, HashFunctions, Traits>& collection, VectorType& vector) 199 { 200 typedef typename HashCountedSet<Value, HashFunctions, Traits>::const_iterator iterator; 201 202 vector.resize(collection.size()); 203 204 iterator it = collection.begin(); 205 iterator end = collection.end(); 206 for (unsigned i = 0; it != end; ++it, ++i) 207 vector[i] = *it; 208 } 209 210 template<typename Value, typename HashFunctions, typename Traits> copyToVector(const HashCountedSet<Value,HashFunctions,Traits> & collection,Vector<Value> & vector)211 inline void copyToVector(const HashCountedSet<Value, HashFunctions, Traits>& collection, Vector<Value>& vector) 212 { 213 typedef typename HashCountedSet<Value, HashFunctions, Traits>::const_iterator iterator; 214 215 vector.resize(collection.size()); 216 217 iterator it = collection.begin(); 218 iterator end = collection.end(); 219 for (unsigned i = 0; it != end; ++it, ++i) 220 vector[i] = (*it).first; 221 } 222 223 224 } // namespace khtml 225 226 using WTF::HashCountedSet; 227 228 #endif /* WTF_HashCountedSet_h */ 229