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
29namespace 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
223using WTF::HashCountedSet;
224
225#endif /* WTF_HashCountedSet_h */
226

source code of qtscript/src/3rdparty/javascriptcore/JavaScriptCore/wtf/HashCountedSet.h