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     private:
  33         typedef HashMap<Value, unsigned, HashFunctions, Traits> ImplType;
  34     public:
  35         typedef Value ValueType;
  36         typedef typename ImplType::iterator iterator;
  37         typedef typename ImplType::const_iterator const_iterator;
  38
  39         HashCountedSet() {}
  40
  41         int size() const;
  42         int capacity() const;
  43         bool isEmpty() const;
  44
  45         // iterators iterate over pairs of values and counts
  46         iterator begin();
  47         iterator end();
  48         const_iterator begin() const;
  49         const_iterator end() const;
  50
  51         iterator find(const ValueType& value);
  52         const_iterator find(const ValueType& value) const;
  53         bool contains(const ValueType& value) const;
  54         unsigned count(const ValueType& value) const;
  55
  56         // increases the count if an equal value is already present
  57         // the return value is a pair of an interator to the new value's location,
  58         // and a bool that is true if an new entry was added
  59         std::pair<iterator, bool> add(const ValueType &value);
  60
  61         // reduces the count of the value, and removes it if count
  62         // goes down to zero
  63         void remove(const ValueType& value);
  64         void remove(iterator it);
  65
  66        void clear();
  67
  68     private:
  69         ImplType m_impl;
  70     };
  71
  72     template<typename Value, typename HashFunctions, typename Traits>
  73     inline int HashCountedSet<Value, HashFunctions, Traits>::size() const
  74     {
  75         return m_impl.size();
  76     }
  77
  78     template<typename Value, typename HashFunctions, typename Traits>
  79     inline int HashCountedSet<Value, HashFunctions, Traits>::capacity() const
  80     {
  81         return m_impl.capacity();
  82     }
  83
  84     template<typename Value, typename HashFunctions, typename Traits>
  85     inline bool HashCountedSet<Value, HashFunctions, Traits>::isEmpty() const
  86     {
  87         return size() == 0;
  88     }
  89
  90     template<typename Value, typename HashFunctions, typename Traits>
  91     inline typename HashCountedSet<Value, HashFunctions, Traits>::iterator HashCountedSet<Value, HashFunctions, Traits>::begin()
  92     {
  93         return m_impl.begin();
  94     }
  95
  96     template<typename Value, typename HashFunctions, typename Traits>
  97     inline typename HashCountedSet<Value, HashFunctions, Traits>::iterator HashCountedSet<Value, HashFunctions, Traits>::end()
  98     {
  99         return m_impl.end();
 100     }
 101
 102     template<typename Value, typename HashFunctions, typename Traits>
 103     inline typename HashCountedSet<Value, HashFunctions, Traits>::const_iterator HashCountedSet<Value, HashFunctions, Traits>::begin() const
 104     {
 105         return m_impl.begin();
 106     }
 107
 108     template<typename Value, typename HashFunctions, typename Traits>
 109     inline typename HashCountedSet<Value, HashFunctions, Traits>::const_iterator HashCountedSet<Value, HashFunctions, Traits>::end() const
 110     {
 111         return m_impl.end();
 112     }
 113
 114     template<typename Value, typename HashFunctions, typename Traits>
 115     inline typename HashCountedSet<Value, HashFunctions, Traits>::iterator HashCountedSet<Value, HashFunctions, Traits>::find(const ValueType& value)
 116     {
 117         return m_impl.find(value);
 118     }
 119
 120     template<typename Value, typename HashFunctions, typename Traits>
 121     inline typename HashCountedSet<Value, HashFunctions, Traits>::const_iterator HashCountedSet<Value, HashFunctions, Traits>::find(const ValueType& value) const
 122     {
 123         return m_impl.find(value);
 124     }
 125
 126     template<typename Value, typename HashFunctions, typename Traits>
 127     inline bool HashCountedSet<Value, HashFunctions, Traits>::contains(const ValueType& value) const
 128     {
 129         return m_impl.contains(value);
 130     }
 131
 132     template<typename Value, typename HashFunctions, typename Traits>
 133     inline unsigned HashCountedSet<Value, HashFunctions, Traits>::count(const ValueType& value) const
 134     {
 135         return m_impl.get(value);
 136     }
 137
 138     template<typename Value, typename HashFunctions, typename Traits>
 139     inline std::pair<typename HashCountedSet<Value, HashFunctions, Traits>::iterator, bool> HashCountedSet<Value, HashFunctions, Traits>::add(const ValueType &value)
 140     {
 141         pair<iterator, bool> result = m_impl.add(value, 0);
 142         ++result.first->second;
 143         return result;
 144     }
 145
 146     template<typename Value, typename HashFunctions, typename Traits>
 147     inline void HashCountedSet<Value, HashFunctions, Traits>::remove(const ValueType& value)
 148     {
 149         remove(find(value));
 150     }
 151
 152     template<typename Value, typename HashFunctions, typename Traits>
 153     inline void HashCountedSet<Value, HashFunctions, Traits>::remove(iterator it)
 154     {
 155         if (it == end())
 156             return;
 157
 158         unsigned oldVal = it->second;
 159         ASSERT(oldVal != 0);
 160         unsigned newVal = oldVal - 1;
 161         if (newVal == 0)
 162             m_impl.remove(it);
 163         else
 164             it->second = newVal;
 165     }
 166
 167     template<typename Value, typename HashFunctions, typename Traits>
 168     inline void HashCountedSet<Value, HashFunctions, Traits>::clear()
 169     {
 170         m_impl.clear();
 171     }
 172
 173     template<typename Value, typename HashFunctions, typename Traits, typename VectorType>
 174     inline void copyToVector(const HashCountedSet<Value, HashFunctions, Traits>& collection, VectorType& vector)
 175     {
 176         typedef typename HashCountedSet<Value, HashFunctions, Traits>::const_iterator iterator;
 177
 178         vector.resize(collection.size());
 179
 180         iterator it = collection.begin();
 181         iterator end = collection.end();
 182         for (unsigned i = 0; it != end; ++it, ++i)
 183             vector[i] = *it;
 184     }
 185
 186     template<typename Value, typename HashFunctions, typename Traits>
 187     inline void copyToVector(const HashCountedSet<Value, HashFunctions, Traits>& collection, Vector<Value>& vector)
 188     {
 189         typedef typename HashCountedSet<Value, HashFunctions, Traits>::const_iterator iterator;
 190
 191         vector.resize(collection.size());
 192
 193         iterator it = collection.begin();
 194         iterator end = collection.end();
 195         for (unsigned i = 0; it != end; ++it, ++i)
 196             vector[i] = (*it).first;
 197     }
 198
 199
 200 } // namespace khtml
 201
 202 using WTF::HashCountedSet;
 203
 204 #endif /* WTF_HashCountedSet_h */