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 | |
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 location, |
59 | // 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 |
64 | void remove(const ValueType&); |
65 | void 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> |
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> |
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> |
91 | inline bool HashCountedSet<Value, HashFunctions, Traits>::isEmpty() const |
92 | { |
93 | return size() == 0; |
94 | } |
95 | |
96 | template<typename Value, typename HashFunctions, typename Traits> |
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> |
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> |
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> |
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> |
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> |
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> |
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> |
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> |
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> |
153 | inline void HashCountedSet<Value, HashFunctions, Traits>::remove(const ValueType& value) |
154 | { |
155 | remove(find(value)); |
156 | } |
157 | |
158 | template<typename Value, typename HashFunctions, typename Traits> |
159 | inline void HashCountedSet<Value, HashFunctions, Traits>::remove(iterator it) |
160 | { |
161 | if (it == end()) |
162 | return; |
163 | |
164 | unsigned oldVal = it->second; |
165 | ASSERT(oldVal != 0); |
166 | unsigned newVal = oldVal - 1; |
167 | if (newVal == 0) |
168 | m_impl.remove(it); |
169 | else |
170 | it->second = newVal; |
171 | } |
172 | |
173 | template<typename Value, typename HashFunctions, typename Traits> |
174 | inline void HashCountedSet<Value, HashFunctions, Traits>::removeAll(const ValueType& value) |
175 | { |
176 | removeAll(find(value)); |
177 | } |
178 | |
179 | template<typename Value, typename HashFunctions, typename Traits> |
180 | inline void HashCountedSet<Value, HashFunctions, Traits>::removeAll(iterator it) |
181 | { |
182 | if (it == end()) |
183 | return; |
184 | |
185 | m_impl.remove(it); |
186 | } |
187 | |
188 | template<typename Value, typename HashFunctions, typename Traits> |
189 | inline void HashCountedSet<Value, HashFunctions, Traits>::clear() |
190 | { |
191 | m_impl.clear(); |
192 | } |
193 | |
194 | template<typename Value, typename HashFunctions, typename Traits, typename VectorType> |
195 | inline void copyToVector(const HashCountedSet<Value, HashFunctions, Traits>& collection, VectorType& vector) |
196 | { |
197 | typedef typename HashCountedSet<Value, HashFunctions, Traits>::const_iterator iterator; |
198 | |
199 | vector.resize(collection.size()); |
200 | |
201 | iterator it = collection.begin(); |
202 | iterator end = collection.end(); |
203 | for (unsigned i = 0; it != end; ++it, ++i) |
204 | vector[i] = *it; |
205 | } |
206 | |
207 | template<typename Value, typename HashFunctions, typename Traits> |
208 | inline void copyToVector(const HashCountedSet<Value, HashFunctions, Traits>& collection, Vector<Value>& vector) |
209 | { |
210 | typedef typename HashCountedSet<Value, HashFunctions, Traits>::const_iterator iterator; |
211 | |
212 | vector.resize(collection.size()); |
213 | |
214 | iterator it = collection.begin(); |
215 | iterator end = collection.end(); |
216 | for (unsigned i = 0; it != end; ++it, ++i) |
217 | vector[i] = (*it).first; |
218 | } |
219 | |
220 | |
221 | } // namespace khtml |
222 | |
223 | using WTF::HashCountedSet; |
224 | |
225 | #endif /* WTF_HashCountedSet_h */ |
226 | |