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