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 "FastAllocBase.h" 26 #include "HashMap.h" 27 #include "Vector.h" 28 29 namespace WTF { 30 31 template<typename Value, typename HashFunctions = typename DefaultHash<Value>::Hash, 32 typename Traits = HashTraits<Value> > class HashCountedSet : public FastAllocBase { 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& value); 53 const_iterator find(const ValueType& value) const; 54 bool contains(const ValueType& value) const; 55 unsigned count(const ValueType& value) 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 location, 59 // and a bool that is true if an new entry was added 60 std::pair<iterator, bool> add(const ValueType &value); 61 62 // reduces the count of the value, and removes it if count 63 // goes down to zero 64 void remove(const ValueType& value); 65 void remove(iterator it); 66 67 void clear(); 68 69 private: 70 ImplType m_impl; 71 }; 72 73 template<typename Value, typename HashFunctions, typename Traits> size()74 inline int HashCountedSet<Value, HashFunctions, Traits>::size() const 75 { 76 return m_impl.size(); 77 } 78 79 template<typename Value, typename HashFunctions, typename Traits> capacity()80 inline int HashCountedSet<Value, HashFunctions, Traits>::capacity() const 81 { 82 return m_impl.capacity(); 83 } 84 85 template<typename Value, typename HashFunctions, typename Traits> isEmpty()86 inline bool HashCountedSet<Value, HashFunctions, Traits>::isEmpty() const 87 { 88 return size() == 0; 89 } 90 91 template<typename Value, typename HashFunctions, typename Traits> begin()92 inline typename HashCountedSet<Value, HashFunctions, Traits>::iterator HashCountedSet<Value, HashFunctions, Traits>::begin() 93 { 94 return m_impl.begin(); 95 } 96 97 template<typename Value, typename HashFunctions, typename Traits> end()98 inline typename HashCountedSet<Value, HashFunctions, Traits>::iterator HashCountedSet<Value, HashFunctions, Traits>::end() 99 { 100 return m_impl.end(); 101 } 102 103 template<typename Value, typename HashFunctions, typename Traits> begin()104 inline typename HashCountedSet<Value, HashFunctions, Traits>::const_iterator HashCountedSet<Value, HashFunctions, Traits>::begin() const 105 { 106 return m_impl.begin(); 107 } 108 109 template<typename Value, typename HashFunctions, typename Traits> end()110 inline typename HashCountedSet<Value, HashFunctions, Traits>::const_iterator HashCountedSet<Value, HashFunctions, Traits>::end() const 111 { 112 return m_impl.end(); 113 } 114 115 template<typename Value, typename HashFunctions, typename Traits> find(const ValueType & value)116 inline typename HashCountedSet<Value, HashFunctions, Traits>::iterator HashCountedSet<Value, HashFunctions, Traits>::find(const ValueType& value) 117 { 118 return m_impl.find(value); 119 } 120 121 template<typename Value, typename HashFunctions, typename Traits> find(const ValueType & value)122 inline typename HashCountedSet<Value, HashFunctions, Traits>::const_iterator HashCountedSet<Value, HashFunctions, Traits>::find(const ValueType& value) const 123 { 124 return m_impl.find(value); 125 } 126 127 template<typename Value, typename HashFunctions, typename Traits> contains(const ValueType & value)128 inline bool HashCountedSet<Value, HashFunctions, Traits>::contains(const ValueType& value) const 129 { 130 return m_impl.contains(value); 131 } 132 133 template<typename Value, typename HashFunctions, typename Traits> count(const ValueType & value)134 inline unsigned HashCountedSet<Value, HashFunctions, Traits>::count(const ValueType& value) const 135 { 136 return m_impl.get(value); 137 } 138 139 template<typename Value, typename HashFunctions, typename Traits> add(const ValueType & value)140 inline std::pair<typename HashCountedSet<Value, HashFunctions, Traits>::iterator, bool> HashCountedSet<Value, HashFunctions, Traits>::add(const ValueType &value) 141 { 142 pair<iterator, bool> result = m_impl.add(value, 0); 143 ++result.first->second; 144 return result; 145 } 146 147 template<typename Value, typename HashFunctions, typename Traits> remove(const ValueType & value)148 inline void HashCountedSet<Value, HashFunctions, Traits>::remove(const ValueType& value) 149 { 150 remove(find(value)); 151 } 152 153 template<typename Value, typename HashFunctions, typename Traits> remove(iterator it)154 inline void HashCountedSet<Value, HashFunctions, Traits>::remove(iterator it) 155 { 156 if (it == end()) 157 return; 158 159 unsigned oldVal = it->second; 160 ASSERT(oldVal != 0); 161 unsigned newVal = oldVal - 1; 162 if (newVal == 0) 163 m_impl.remove(it); 164 else 165 it->second = newVal; 166 } 167 168 template<typename Value, typename HashFunctions, typename Traits> clear()169 inline void HashCountedSet<Value, HashFunctions, Traits>::clear() 170 { 171 m_impl.clear(); 172 } 173 174 template<typename Value, typename HashFunctions, typename Traits, typename VectorType> copyToVector(const HashCountedSet<Value,HashFunctions,Traits> & collection,VectorType & vector)175 inline void copyToVector(const HashCountedSet<Value, HashFunctions, Traits>& collection, VectorType& vector) 176 { 177 typedef typename HashCountedSet<Value, HashFunctions, Traits>::const_iterator iterator; 178 179 vector.resize(collection.size()); 180 181 iterator it = collection.begin(); 182 iterator end = collection.end(); 183 for (unsigned i = 0; it != end; ++it, ++i) 184 vector[i] = *it; 185 } 186 187 template<typename Value, typename HashFunctions, typename Traits> copyToVector(const HashCountedSet<Value,HashFunctions,Traits> & collection,Vector<Value> & vector)188 inline void copyToVector(const HashCountedSet<Value, HashFunctions, Traits>& collection, Vector<Value>& vector) 189 { 190 typedef typename HashCountedSet<Value, HashFunctions, Traits>::const_iterator iterator; 191 192 vector.resize(collection.size()); 193 194 iterator it = collection.begin(); 195 iterator end = collection.end(); 196 for (unsigned i = 0; it != end; ++it, ++i) 197 vector[i] = (*it).first; 198 } 199 200 201 } // namespace khtml 202 203 using WTF::HashCountedSet; 204 205 #endif /* WTF_HashCountedSet_h */ 206