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 "FastAllocBase.h"
  26 #include "HashMap.h"
  27 #include "Vector.h"
  28
  29 namespace 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
 223 using WTF::HashCountedSet;
 224
 225 #endif /* WTF_HashCountedSet_h */