OLD | NEW |
1 /* | 1 /* |
2 * Copyright (C) 2005, 2006, 2008 Apple Inc. All rights reserved. | 2 * Copyright (C) 2005, 2006, 2008 Apple Inc. All rights reserved. |
3 * | 3 * |
4 * This library is free software; you can redistribute it and/or | 4 * This library is free software; you can redistribute it and/or |
5 * modify it under the terms of the GNU Library General Public | 5 * modify it under the terms of the GNU Library General Public |
6 * License as published by the Free Software Foundation; either | 6 * License as published by the Free Software Foundation; either |
7 * version 2 of the License, or (at your option) any later version. | 7 * version 2 of the License, or (at your option) any later version. |
8 * | 8 * |
9 * This library is distributed in the hope that it will be useful, | 9 * This library is distributed in the hope that it will be useful, |
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of | 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of |
(...skipping 19 matching lines...) Expand all Loading... |
30 template<typename Value, typename HashFunctions = typename DefaultHash<Value
>::Hash, | 30 template<typename Value, typename HashFunctions = typename DefaultHash<Value
>::Hash, |
31 typename Traits = HashTraits<Value> > class HashCountedSet { | 31 typename Traits = HashTraits<Value> > class HashCountedSet { |
32 WTF_MAKE_FAST_ALLOCATED; | 32 WTF_MAKE_FAST_ALLOCATED; |
33 private: | 33 private: |
34 typedef HashMap<Value, unsigned, HashFunctions, Traits> ImplType; | 34 typedef HashMap<Value, unsigned, HashFunctions, Traits> ImplType; |
35 public: | 35 public: |
36 typedef Value ValueType; | 36 typedef Value ValueType; |
37 typedef typename ImplType::iterator iterator; | 37 typedef typename ImplType::iterator iterator; |
38 typedef typename ImplType::const_iterator const_iterator; | 38 typedef typename ImplType::const_iterator const_iterator; |
39 typedef typename ImplType::AddResult AddResult; | 39 typedef typename ImplType::AddResult AddResult; |
40 | 40 |
41 HashCountedSet() {} | 41 HashCountedSet() {} |
42 | 42 |
43 void swap(HashCountedSet&); | 43 void swap(HashCountedSet&); |
44 | 44 |
45 int size() const; | 45 int size() const; |
46 int capacity() const; | 46 int capacity() const; |
47 bool isEmpty() const; | 47 bool isEmpty() const; |
48 | 48 |
49 // Iterators iterate over pairs of values and counts. | 49 // Iterators iterate over pairs of values and counts. |
50 iterator begin(); | 50 iterator begin(); |
51 iterator end(); | 51 iterator end(); |
52 const_iterator begin() const; | 52 const_iterator begin() const; |
53 const_iterator end() const; | 53 const_iterator end() const; |
54 | 54 |
55 iterator find(const ValueType&); | 55 iterator find(const ValueType&); |
56 const_iterator find(const ValueType&) const; | 56 const_iterator find(const ValueType&) const; |
57 bool contains(const ValueType&) const; | 57 bool contains(const ValueType&) const; |
58 unsigned count(const ValueType&) const; | 58 unsigned count(const ValueType&) const; |
59 | 59 |
60 // Increases the count if an equal value is already present | 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 | 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. | 62 // location, and a bool that is true if an new entry was added. |
63 AddResult add(const ValueType&); | 63 AddResult add(const ValueType&); |
64 | 64 |
65 // Reduces the count of the value, and removes it if count | 65 // Reduces the count of the value, and removes it if count |
66 // goes down to zero, returns true if the value is removed. | 66 // goes down to zero, returns true if the value is removed. |
67 bool remove(const ValueType&); | 67 bool remove(const ValueType&); |
68 bool remove(iterator); | 68 bool remove(iterator); |
69 | 69 |
70 // Removes the value, regardless of its count. | 70 // Removes the value, regardless of its count. |
71 void removeAll(iterator); | 71 void removeAll(iterator); |
72 void removeAll(const ValueType&); | 72 void removeAll(const ValueType&); |
73 | 73 |
74 // Clears the whole set. | 74 // Clears the whole set. |
75 void clear(); | 75 void clear(); |
76 | 76 |
77 private: | 77 private: |
78 ImplType m_impl; | 78 ImplType m_impl; |
79 }; | 79 }; |
80 | 80 |
81 template<typename Value, typename HashFunctions, typename Traits> | 81 template<typename Value, typename HashFunctions, typename Traits> |
82 inline void HashCountedSet<Value, HashFunctions, Traits>::swap(HashCountedSe
t& other) | 82 inline void HashCountedSet<Value, HashFunctions, Traits>::swap(HashCountedSe
t& other) |
83 { | 83 { |
84 m_impl.swap(other.m_impl); | 84 m_impl.swap(other.m_impl); |
85 } | 85 } |
86 | 86 |
87 template<typename Value, typename HashFunctions, typename Traits> | 87 template<typename Value, typename HashFunctions, typename Traits> |
88 inline int HashCountedSet<Value, HashFunctions, Traits>::size() const | 88 inline int HashCountedSet<Value, HashFunctions, Traits>::size() const |
89 { | 89 { |
90 return m_impl.size(); | 90 return m_impl.size(); |
91 } | 91 } |
92 | 92 |
93 template<typename Value, typename HashFunctions, typename Traits> | 93 template<typename Value, typename HashFunctions, typename Traits> |
94 inline int HashCountedSet<Value, HashFunctions, Traits>::capacity() const | 94 inline int HashCountedSet<Value, HashFunctions, Traits>::capacity() const |
95 { | 95 { |
96 return m_impl.capacity(); | 96 return m_impl.capacity(); |
97 } | 97 } |
98 | 98 |
99 template<typename Value, typename HashFunctions, typename Traits> | 99 template<typename Value, typename HashFunctions, typename Traits> |
100 inline bool HashCountedSet<Value, HashFunctions, Traits>::isEmpty() const | 100 inline bool HashCountedSet<Value, HashFunctions, Traits>::isEmpty() const |
101 { | 101 { |
102 return size() == 0; | 102 return size() == 0; |
103 } | 103 } |
104 | 104 |
105 template<typename Value, typename HashFunctions, typename Traits> | 105 template<typename Value, typename HashFunctions, typename Traits> |
106 inline typename HashCountedSet<Value, HashFunctions, Traits>::iterator HashC
ountedSet<Value, HashFunctions, Traits>::begin() | 106 inline typename HashCountedSet<Value, HashFunctions, Traits>::iterator HashC
ountedSet<Value, HashFunctions, Traits>::begin() |
107 { | 107 { |
108 return m_impl.begin(); | 108 return m_impl.begin(); |
109 } | 109 } |
110 | 110 |
111 template<typename Value, typename HashFunctions, typename Traits> | 111 template<typename Value, typename HashFunctions, typename Traits> |
112 inline typename HashCountedSet<Value, HashFunctions, Traits>::iterator HashC
ountedSet<Value, HashFunctions, Traits>::end() | 112 inline typename HashCountedSet<Value, HashFunctions, Traits>::iterator HashC
ountedSet<Value, HashFunctions, Traits>::end() |
113 { | 113 { |
114 return m_impl.end(); | 114 return m_impl.end(); |
115 } | 115 } |
116 | 116 |
117 template<typename Value, typename HashFunctions, typename Traits> | 117 template<typename Value, typename HashFunctions, typename Traits> |
118 inline typename HashCountedSet<Value, HashFunctions, Traits>::const_iterator
HashCountedSet<Value, HashFunctions, Traits>::begin() const | 118 inline typename HashCountedSet<Value, HashFunctions, Traits>::const_iterator
HashCountedSet<Value, HashFunctions, Traits>::begin() const |
119 { | 119 { |
120 return m_impl.begin(); | 120 return m_impl.begin(); |
121 } | 121 } |
122 | 122 |
123 template<typename Value, typename HashFunctions, typename Traits> | 123 template<typename Value, typename HashFunctions, typename Traits> |
124 inline typename HashCountedSet<Value, HashFunctions, Traits>::const_iterator
HashCountedSet<Value, HashFunctions, Traits>::end() const | 124 inline typename HashCountedSet<Value, HashFunctions, Traits>::const_iterator
HashCountedSet<Value, HashFunctions, Traits>::end() const |
125 { | 125 { |
126 return m_impl.end(); | 126 return m_impl.end(); |
127 } | 127 } |
128 | 128 |
129 template<typename Value, typename HashFunctions, typename Traits> | 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) | 130 inline typename HashCountedSet<Value, HashFunctions, Traits>::iterator HashC
ountedSet<Value, HashFunctions, Traits>::find(const ValueType& value) |
131 { | 131 { |
132 return m_impl.find(value); | 132 return m_impl.find(value); |
133 } | 133 } |
134 | 134 |
135 template<typename Value, typename HashFunctions, typename Traits> | 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 | 136 inline typename HashCountedSet<Value, HashFunctions, Traits>::const_iterator
HashCountedSet<Value, HashFunctions, Traits>::find(const ValueType& value) cons
t |
137 { | 137 { |
138 return m_impl.find(value); | 138 return m_impl.find(value); |
139 } | 139 } |
140 | 140 |
141 template<typename Value, typename HashFunctions, typename Traits> | 141 template<typename Value, typename HashFunctions, typename Traits> |
142 inline bool HashCountedSet<Value, HashFunctions, Traits>::contains(const Val
ueType& value) const | 142 inline bool HashCountedSet<Value, HashFunctions, Traits>::contains(const Val
ueType& value) const |
143 { | 143 { |
144 return m_impl.contains(value); | 144 return m_impl.contains(value); |
145 } | 145 } |
146 | 146 |
147 template<typename Value, typename HashFunctions, typename Traits> | 147 template<typename Value, typename HashFunctions, typename Traits> |
148 inline unsigned HashCountedSet<Value, HashFunctions, Traits>::count(const Va
lueType& value) const | 148 inline unsigned HashCountedSet<Value, HashFunctions, Traits>::count(const Va
lueType& value) const |
149 { | 149 { |
150 return m_impl.get(value); | 150 return m_impl.get(value); |
151 } | 151 } |
152 | 152 |
153 template<typename Value, typename HashFunctions, typename Traits> | 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) | 154 inline typename HashCountedSet<Value, HashFunctions, Traits>::AddResult Hash
CountedSet<Value, HashFunctions, Traits>::add(const ValueType &value) |
155 { | 155 { |
156 AddResult result = m_impl.add(value, 0); | 156 AddResult result = m_impl.add(value, 0); |
157 ++result.iterator->value; | 157 ++result.iterator->value; |
158 return result; | 158 return result; |
159 } | 159 } |
160 | 160 |
161 template<typename Value, typename HashFunctions, typename Traits> | 161 template<typename Value, typename HashFunctions, typename Traits> |
162 inline bool HashCountedSet<Value, HashFunctions, Traits>::remove(const Value
Type& value) | 162 inline bool HashCountedSet<Value, HashFunctions, Traits>::remove(const Value
Type& value) |
163 { | 163 { |
164 return remove(find(value)); | 164 return remove(find(value)); |
165 } | 165 } |
166 | 166 |
167 template<typename Value, typename HashFunctions, typename Traits> | 167 template<typename Value, typename HashFunctions, typename Traits> |
168 inline bool HashCountedSet<Value, HashFunctions, Traits>::remove(iterator it
) | 168 inline bool HashCountedSet<Value, HashFunctions, Traits>::remove(iterator it
) |
169 { | 169 { |
170 if (it == end()) | 170 if (it == end()) |
171 return false; | 171 return false; |
172 | 172 |
173 unsigned oldVal = it->value; | 173 unsigned oldVal = it->value; |
174 ASSERT(oldVal); | 174 ASSERT(oldVal); |
175 unsigned newVal = oldVal - 1; | 175 unsigned newVal = oldVal - 1; |
176 if (newVal) { | 176 if (newVal) { |
177 it->value = newVal; | 177 it->value = newVal; |
178 return false; | 178 return false; |
179 } | 179 } |
180 | 180 |
181 m_impl.remove(it); | 181 m_impl.remove(it); |
182 return true; | 182 return true; |
183 } | 183 } |
184 | 184 |
185 template<typename Value, typename HashFunctions, typename Traits> | 185 template<typename Value, typename HashFunctions, typename Traits> |
186 inline void HashCountedSet<Value, HashFunctions, Traits>::removeAll(const Va
lueType& value) | 186 inline void HashCountedSet<Value, HashFunctions, Traits>::removeAll(const Va
lueType& value) |
187 { | 187 { |
188 removeAll(find(value)); | 188 removeAll(find(value)); |
189 } | 189 } |
190 | 190 |
191 template<typename Value, typename HashFunctions, typename Traits> | 191 template<typename Value, typename HashFunctions, typename Traits> |
192 inline void HashCountedSet<Value, HashFunctions, Traits>::removeAll(iterator
it) | 192 inline void HashCountedSet<Value, HashFunctions, Traits>::removeAll(iterator
it) |
193 { | 193 { |
194 if (it == end()) | 194 if (it == end()) |
195 return; | 195 return; |
196 | 196 |
197 m_impl.remove(it); | 197 m_impl.remove(it); |
198 } | 198 } |
199 | 199 |
200 template<typename Value, typename HashFunctions, typename Traits> | 200 template<typename Value, typename HashFunctions, typename Traits> |
201 inline void HashCountedSet<Value, HashFunctions, Traits>::clear() | 201 inline void HashCountedSet<Value, HashFunctions, Traits>::clear() |
202 { | 202 { |
203 m_impl.clear(); | 203 m_impl.clear(); |
204 } | 204 } |
205 | 205 |
206 template<typename Value, typename HashFunctions, typename Traits, typename V
ectorType> | 206 template<typename Value, typename HashFunctions, typename Traits, typename V
ectorType> |
207 inline void copyToVector(const HashCountedSet<Value, HashFunctions, Traits>&
collection, VectorType& vector) | 207 inline void copyToVector(const HashCountedSet<Value, HashFunctions, Traits>&
collection, VectorType& vector) |
208 { | 208 { |
209 typedef typename HashCountedSet<Value, HashFunctions, Traits>::const_ite
rator iterator; | 209 typedef typename HashCountedSet<Value, HashFunctions, Traits>::const_ite
rator iterator; |
210 | 210 |
211 vector.resize(collection.size()); | 211 vector.resize(collection.size()); |
212 | 212 |
213 iterator it = collection.begin(); | 213 iterator it = collection.begin(); |
214 iterator end = collection.end(); | 214 iterator end = collection.end(); |
215 for (unsigned i = 0; it != end; ++it, ++i) | 215 for (unsigned i = 0; it != end; ++it, ++i) |
216 vector[i] = *it; | 216 vector[i] = *it; |
217 } | 217 } |
218 | 218 |
219 template<typename Value, typename HashFunctions, typename Traits> | 219 template<typename Value, typename HashFunctions, typename Traits> |
220 inline void copyToVector(const HashCountedSet<Value, HashFunctions, Traits>&
collection, Vector<Value>& vector) | 220 inline void copyToVector(const HashCountedSet<Value, HashFunctions, Traits>&
collection, Vector<Value>& vector) |
221 { | 221 { |
222 typedef typename HashCountedSet<Value, HashFunctions, Traits>::const_ite
rator iterator; | 222 typedef typename HashCountedSet<Value, HashFunctions, Traits>::const_ite
rator iterator; |
223 | 223 |
224 vector.resize(collection.size()); | 224 vector.resize(collection.size()); |
225 | 225 |
226 iterator it = collection.begin(); | 226 iterator it = collection.begin(); |
227 iterator end = collection.end(); | 227 iterator end = collection.end(); |
228 for (unsigned i = 0; it != end; ++it, ++i) | 228 for (unsigned i = 0; it != end; ++it, ++i) |
229 vector[i] = (*it).key; | 229 vector[i] = (*it).key; |
230 } | 230 } |
231 | 231 |
232 | 232 |
233 } // namespace khtml | 233 } // namespace khtml |
234 | 234 |
235 using WTF::HashCountedSet; | 235 using WTF::HashCountedSet; |
236 | 236 |
237 #endif /* WTF_HashCountedSet_h */ | 237 #endif /* WTF_HashCountedSet_h */ |
OLD | NEW |