OLD | NEW |
| (Empty) |
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(HashCountedSe
t& 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 HashC
ountedSet<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 HashC
ountedSet<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 HashC
ountedSet<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) cons
t | |
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 Val
ueType& 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 Va
lueType& 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 Hash
CountedSet<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 Value
Type& 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 Va
lueType& 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 V
ectorType> | |
207 inline void copyToVector(const HashCountedSet<Value, HashFunctions, Traits>&
collection, VectorType& vector) | |
208 { | |
209 typedef typename HashCountedSet<Value, HashFunctions, Traits>::const_ite
rator 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_ite
rator 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 */ | |
OLD | NEW |