2 * Copyright (C) 2005, 2006, 2008 Apple Inc. All rights reserved.
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.
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.
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.
21 #ifndef WTF_HashCountedSet_h
22 #define WTF_HashCountedSet_h
24 #include <wtf/Assertions.h>
25 #include <wtf/HashMap.h>
26 #include <wtf/Vector.h>
30 template<typename Value, typename HashFunctions = typename DefaultHash<Value>::Hash,
31 typename Traits = HashTraits<Value> > class HashCountedSet {
32 WTF_MAKE_FAST_ALLOCATED;
34 typedef HashMap<Value, unsigned, HashFunctions, Traits> ImplType;
36 typedef Value ValueType;
37 typedef typename ImplType::iterator iterator;
38 typedef typename ImplType::const_iterator const_iterator;
39 typedef typename ImplType::AddResult AddResult;
43 void swap(HashCountedSet&);
49 // Iterators iterate over pairs of values and counts.
52 const_iterator begin() const;
53 const_iterator end() const;
55 iterator find(const ValueType&);
56 const_iterator find(const ValueType&) const;
57 bool contains(const ValueType&) const;
58 unsigned count(const ValueType&) const;
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&);
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);
70 // Removes the value, regardless of its count.
71 void removeAll(iterator);
72 void removeAll(const ValueType&);
74 // Clears the whole set.
81 template<typename Value, typename HashFunctions, typename Traits>
82 inline void HashCountedSet<Value, HashFunctions, Traits>::swap(HashCountedSet& other)
84 m_impl.swap(other.m_impl);
87 template<typename Value, typename HashFunctions, typename Traits>
88 inline int HashCountedSet<Value, HashFunctions, Traits>::size() const
93 template<typename Value, typename HashFunctions, typename Traits>
94 inline int HashCountedSet<Value, HashFunctions, Traits>::capacity() const
96 return m_impl.capacity();
99 template<typename Value, typename HashFunctions, typename Traits>
100 inline bool HashCountedSet<Value, HashFunctions, Traits>::isEmpty() const
105 template<typename Value, typename HashFunctions, typename Traits>
106 inline typename HashCountedSet<Value, HashFunctions, Traits>::iterator HashCountedSet<Value, HashFunctions, Traits>::begin()
108 return m_impl.begin();
111 template<typename Value, typename HashFunctions, typename Traits>
112 inline typename HashCountedSet<Value, HashFunctions, Traits>::iterator HashCountedSet<Value, HashFunctions, Traits>::end()
117 template<typename Value, typename HashFunctions, typename Traits>
118 inline typename HashCountedSet<Value, HashFunctions, Traits>::const_iterator HashCountedSet<Value, HashFunctions, Traits>::begin() const
120 return m_impl.begin();
123 template<typename Value, typename HashFunctions, typename Traits>
124 inline typename HashCountedSet<Value, HashFunctions, Traits>::const_iterator HashCountedSet<Value, HashFunctions, Traits>::end() const
129 template<typename Value, typename HashFunctions, typename Traits>
130 inline typename HashCountedSet<Value, HashFunctions, Traits>::iterator HashCountedSet<Value, HashFunctions, Traits>::find(const ValueType& value)
132 return m_impl.find(value);
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
138 return m_impl.find(value);
141 template<typename Value, typename HashFunctions, typename Traits>
142 inline bool HashCountedSet<Value, HashFunctions, Traits>::contains(const ValueType& value) const
144 return m_impl.contains(value);
147 template<typename Value, typename HashFunctions, typename Traits>
148 inline unsigned HashCountedSet<Value, HashFunctions, Traits>::count(const ValueType& value) const
150 return m_impl.get(value);
153 template<typename Value, typename HashFunctions, typename Traits>
154 inline typename HashCountedSet<Value, HashFunctions, Traits>::AddResult HashCountedSet<Value, HashFunctions, Traits>::add(const ValueType &value)
156 AddResult result = m_impl.add(value, 0);
157 ++result.iterator->second;
161 template<typename Value, typename HashFunctions, typename Traits>
162 inline bool HashCountedSet<Value, HashFunctions, Traits>::remove(const ValueType& value)
164 return remove(find(value));
167 template<typename Value, typename HashFunctions, typename Traits>
168 inline bool HashCountedSet<Value, HashFunctions, Traits>::remove(iterator it)
173 unsigned oldVal = it->second;
175 unsigned newVal = oldVal - 1;
185 template<typename Value, typename HashFunctions, typename Traits>
186 inline void HashCountedSet<Value, HashFunctions, Traits>::removeAll(const ValueType& value)
188 removeAll(find(value));
191 template<typename Value, typename HashFunctions, typename Traits>
192 inline void HashCountedSet<Value, HashFunctions, Traits>::removeAll(iterator it)
200 template<typename Value, typename HashFunctions, typename Traits>
201 inline void HashCountedSet<Value, HashFunctions, Traits>::clear()
206 template<typename Value, typename HashFunctions, typename Traits, typename VectorType>
207 inline void copyToVector(const HashCountedSet<Value, HashFunctions, Traits>& collection, VectorType& vector)
209 typedef typename HashCountedSet<Value, HashFunctions, Traits>::const_iterator iterator;
211 vector.resize(collection.size());
213 iterator it = collection.begin();
214 iterator end = collection.end();
215 for (unsigned i = 0; it != end; ++it, ++i)
219 template<typename Value, typename HashFunctions, typename Traits>
220 inline void copyToVector(const HashCountedSet<Value, HashFunctions, Traits>& collection, Vector<Value>& vector)
222 typedef typename HashCountedSet<Value, HashFunctions, Traits>::const_iterator iterator;
224 vector.resize(collection.size());
226 iterator it = collection.begin();
227 iterator end = collection.end();
228 for (unsigned i = 0; it != end; ++it, ++i)
229 vector[i] = (*it).first;
235 using WTF::HashCountedSet;
237 #endif /* WTF_HashCountedSet_h */