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