wtf/HashCountedSet.h

   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
  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>
  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 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>
 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>
 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>
 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>
 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>
 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>
 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 */