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 "wtf/Assertions.h" 25 #include "wtf/HashMap.h" 26 #include "wtf/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 typedef typename ImplType::AddResult AddResult; 40 41 HashCountedSet() {} 42 43 void swap(HashCountedSet&); 44 45 int size() const; 46 int capacity() const; 47 bool isEmpty() const; 48 49 // Iterators iterate over pairs of values and counts. 50 iterator begin(); 51 iterator end(); 52 const_iterator begin() const; 53 const_iterator end() const; 54 55 iterator find(const ValueType&); 56 const_iterator find(const ValueType&) const; 57 bool contains(const ValueType&) const; 58 unsigned count(const ValueType&) const; 59 60 // Increases the count if an equal value is already present 61 // the return value is a pair of an interator to the new value's 62 // location, and a bool that is true if an new entry was added. 63 AddResult add(const ValueType&); 64 65 // Reduces the count of the value, and removes it if count 66 // goes down to zero, returns true if the value is removed. 67 bool remove(const ValueType&); 68 bool remove(iterator); 69 70 // Removes the value, regardless of its count. 71 void removeAll(iterator); 72 void removeAll(const ValueType&); 73 74 // Clears the whole set. 75 void clear(); 76 77 private: 78 ImplType m_impl; 79 }; 80 81 template<typename Value, typename HashFunctions, typename Traits> 82 inline void HashCountedSet<Value, HashFunctions, Traits>::swap(HashCountedSet& other) 83 { 84 m_impl.swap(other.m_impl); 85 } 86 87 template<typename Value, typename HashFunctions, typename Traits> 88 inline int HashCountedSet<Value, HashFunctions, Traits>::size() const 89 { 90 return m_impl.size(); 91 } 92 93 template<typename Value, typename HashFunctions, typename Traits> 94 inline int HashCountedSet<Value, HashFunctions, Traits>::capacity() const 95 { 96 return m_impl.capacity(); 97 } 98 99 template<typename Value, typename HashFunctions, typename Traits> 100 inline bool HashCountedSet<Value, HashFunctions, Traits>::isEmpty() const 101 { 102 return size() == 0; 103 } 104 105 template<typename Value, typename HashFunctions, typename Traits> 106 inline typename HashCountedSet<Value, HashFunctions, Traits>::iterator HashCountedSet<Value, HashFunctions, Traits>::begin() 107 { 108 return m_impl.begin(); 109 } 110 111 template<typename Value, typename HashFunctions, typename Traits> 112 inline typename HashCountedSet<Value, HashFunctions, Traits>::iterator HashCountedSet<Value, HashFunctions, Traits>::end() 113 { 114 return m_impl.end(); 115 } 116 117 template<typename Value, typename HashFunctions, typename Traits> 118 inline typename HashCountedSet<Value, HashFunctions, Traits>::const_iterator HashCountedSet<Value, HashFunctions, Traits>::begin() const 119 { 120 return m_impl.begin(); 121 } 122 123 template<typename Value, typename HashFunctions, typename Traits> 124 inline typename HashCountedSet<Value, HashFunctions, Traits>::const_iterator HashCountedSet<Value, HashFunctions, Traits>::end() const 125 { 126 return m_impl.end(); 127 } 128 129 template<typename Value, typename HashFunctions, typename Traits> 130 inline typename HashCountedSet<Value, HashFunctions, Traits>::iterator HashCountedSet<Value, HashFunctions, Traits>::find(const ValueType& value) 131 { 132 return m_impl.find(value); 133 } 134 135 template<typename Value, typename HashFunctions, typename Traits> 136 inline typename HashCountedSet<Value, HashFunctions, Traits>::const_iterator HashCountedSet<Value, HashFunctions, Traits>::find(const ValueType& value) const 137 { 138 return m_impl.find(value); 139 } 140 141 template<typename Value, typename HashFunctions, typename Traits> 142 inline bool HashCountedSet<Value, HashFunctions, Traits>::contains(const ValueType& value) const 143 { 144 return m_impl.contains(value); 145 } 146 147 template<typename Value, typename HashFunctions, typename Traits> 148 inline unsigned HashCountedSet<Value, HashFunctions, Traits>::count(const ValueType& value) const 149 { 150 return m_impl.get(value); 151 } 152 153 template<typename Value, typename HashFunctions, typename Traits> 154 inline typename HashCountedSet<Value, HashFunctions, Traits>::AddResult HashCountedSet<Value, HashFunctions, Traits>::add(const ValueType &value) 155 { 156 AddResult result = m_impl.add(value, 0); 157 ++result.iterator->value; 158 return result; 159 } 160 161 template<typename Value, typename HashFunctions, typename Traits> 162 inline bool HashCountedSet<Value, HashFunctions, Traits>::remove(const ValueType& value) 163 { 164 return remove(find(value)); 165 } 166 167 template<typename Value, typename HashFunctions, typename Traits> 168 inline bool HashCountedSet<Value, HashFunctions, Traits>::remove(iterator it) 169 { 170 if (it == end()) 171 return false; 172 173 unsigned oldVal = it->value; 174 ASSERT(oldVal); 175 unsigned newVal = oldVal - 1; 176 if (newVal) { 177 it->value = newVal; 178 return false; 179 } 180 181 m_impl.remove(it); 182 return true; 183 } 184 185 template<typename Value, typename HashFunctions, typename Traits> 186 inline void HashCountedSet<Value, HashFunctions, Traits>::removeAll(const ValueType& value) 187 { 188 removeAll(find(value)); 189 } 190 191 template<typename Value, typename HashFunctions, typename Traits> 192 inline void HashCountedSet<Value, HashFunctions, Traits>::removeAll(iterator it) 193 { 194 if (it == end()) 195 return; 196 197 m_impl.remove(it); 198 } 199 200 template<typename Value, typename HashFunctions, typename Traits> 201 inline void HashCountedSet<Value, HashFunctions, Traits>::clear() 202 { 203 m_impl.clear(); 204 } 205 206 template<typename Value, typename HashFunctions, typename Traits, typename VectorType> 207 inline void copyToVector(const HashCountedSet<Value, HashFunctions, Traits>& collection, VectorType& vector) 208 { 209 typedef typename HashCountedSet<Value, HashFunctions, Traits>::const_iterator iterator; 210 211 vector.resize(collection.size()); 212 213 iterator it = collection.begin(); 214 iterator end = collection.end(); 215 for (unsigned i = 0; it != end; ++it, ++i) 216 vector[i] = *it; 217 } 218 219 template<typename Value, typename HashFunctions, typename Traits> 220 inline void copyToVector(const HashCountedSet<Value, HashFunctions, Traits>& collection, Vector<Value>& vector) 221 { 222 typedef typename HashCountedSet<Value, HashFunctions, Traits>::const_iterator iterator; 223 224 vector.resize(collection.size()); 225 226 iterator it = collection.begin(); 227 iterator end = collection.end(); 228 for (unsigned i = 0; it != end; ++it, ++i) 229 vector[i] = (*it).key; 230 } 231 232 233 } // namespace khtml 234 235 using WTF::HashCountedSet; 236 237 #endif /* WTF_HashCountedSet_h */ 238
