src/third_party/WebKit/Source/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 "wtf/Assertions.h"
  25 #include "wtf/HashMap.h"
  26 #include "wtf/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, HashTraits<unsigned>, DefaultAllocator> ImplType;
  35     public:
  36         typedef Value ValueType;
  37         typedef typename ImplType::iterator iterator;
  38         typedef typename ImplType::const_iterator const_iterator;
  39         typedef typename ImplType::AddResult AddResult;
  40
  41         HashCountedSet() {}
  42
  43         void swap(HashCountedSet&);
  44
  45         unsigned size() const;
  46         unsigned capacity() const;
  47         bool isEmpty() const;
  48
  49         // Iterators iterate over pairs of values and counts.
  50         iterator begin();
  51         iterator end();
  52         const_iterator begin() const;
  53         const_iterator end() const;
  54
  55         iterator find(const ValueType&);
  56         const_iterator find(const ValueType&) const;
  57         bool contains(const ValueType&) const;
  58         unsigned count(const ValueType&) const;
  59
  60         // Increases the count if an equal value is already present
  61         // the return value is a pair of an iterator to the new value's
  62         // location, and a bool that is true if an new entry was added.
  63         AddResult add(const ValueType&);
  64
  65         // Reduces the count of the value, and removes it if count
  66         // goes down to zero, returns true if the value is removed.
  67         bool remove(const ValueType&);
  68         bool remove(iterator);
  69
  70         // Removes the value, regardless of its count.
  71         void removeAll(iterator);
  72         void removeAll(const ValueType&);
  73
  74         // Clears the whole set.
  75         void clear();
  76
  77     private:
  78         ImplType m_impl;
  79     };
  80
  81     template<typename Value, typename HashFunctions, typename Traits>
  82     inline void HashCountedSet<Value, HashFunctions, Traits>::swap(HashCountedSet& other)
  83     {
  84         m_impl.swap(other.m_impl);
  85     }
  86
  87     template<typename Value, typename HashFunctions, typename Traits>
  88     inline unsigned HashCountedSet<Value, HashFunctions, Traits>::size() const
  89     {
  90         return m_impl.size();
  91     }
  92
  93     template<typename Value, typename HashFunctions, typename Traits>
  94     inline unsigned HashCountedSet<Value, HashFunctions, Traits>::capacity() const
  95     {
  96         return m_impl.capacity();
  97     }
  98
  99     template<typename Value, typename HashFunctions, typename Traits>
 100     inline bool HashCountedSet<Value, HashFunctions, Traits>::isEmpty() const
 101     {
 102         return size() == 0;
 103     }
 104
 105     template<typename Value, typename HashFunctions, typename Traits>
 106     inline typename HashCountedSet<Value, HashFunctions, Traits>::iterator HashCountedSet<Value, HashFunctions, Traits>::begin()
 107     {
 108         return m_impl.begin();
 109     }
 110
 111     template<typename Value, typename HashFunctions, typename Traits>
 112     inline typename HashCountedSet<Value, HashFunctions, Traits>::iterator HashCountedSet<Value, HashFunctions, Traits>::end()
 113     {
 114         return m_impl.end();
 115     }
 116
 117     template<typename Value, typename HashFunctions, typename Traits>
 118     inline typename HashCountedSet<Value, HashFunctions, Traits>::const_iterator HashCountedSet<Value, HashFunctions, Traits>::begin() const
 119     {
 120         return m_impl.begin();
 121     }
 122
 123     template<typename Value, typename HashFunctions, typename Traits>
 124     inline typename HashCountedSet<Value, HashFunctions, Traits>::const_iterator HashCountedSet<Value, HashFunctions, Traits>::end() const
 125     {
 126         return m_impl.end();
 127     }
 128
 129     template<typename Value, typename HashFunctions, typename Traits>
 130     inline typename HashCountedSet<Value, HashFunctions, Traits>::iterator HashCountedSet<Value, HashFunctions, Traits>::find(const ValueType& value)
 131     {
 132         return m_impl.find(value);
 133     }
 134
 135     template<typename Value, typename HashFunctions, typename Traits>
 136     inline typename HashCountedSet<Value, HashFunctions, Traits>::const_iterator HashCountedSet<Value, HashFunctions, Traits>::find(const ValueType& value) const
 137     {
 138         return m_impl.find(value);
 139     }
 140
 141     template<typename Value, typename HashFunctions, typename Traits>
 142     inline bool HashCountedSet<Value, HashFunctions, Traits>::contains(const ValueType& value) const
 143     {
 144         return m_impl.contains(value);
 145     }
 146
 147     template<typename Value, typename HashFunctions, typename Traits>
 148     inline unsigned HashCountedSet<Value, HashFunctions, Traits>::count(const ValueType& value) const
 149     {
 150         return m_impl.get(value);
 151     }
 152
 153     template<typename Value, typename HashFunctions, typename Traits>
 154     inline typename HashCountedSet<Value, HashFunctions, Traits>::AddResult HashCountedSet<Value, HashFunctions, Traits>::add(const ValueType &value)
 155     {
 156         AddResult result = m_impl.add(value, 0);
 157         ++result.storedValue->value;
 158         return result;
 159     }
 160
 161     template<typename Value, typename HashFunctions, typename Traits>
 162     inline bool HashCountedSet<Value, HashFunctions, Traits>::remove(const ValueType& value)
 163     {
 164         return remove(find(value));
 165     }
 166
 167     template<typename Value, typename HashFunctions, typename Traits>
 168     inline bool HashCountedSet<Value, HashFunctions, Traits>::remove(iterator it)
 169     {
 170         if (it == end())
 171             return false;
 172
 173         unsigned oldVal = it->value;
 174         ASSERT(oldVal);
 175         unsigned newVal = oldVal - 1;
 176         if (newVal) {
 177             it->value = newVal;
 178             return false;
 179         }
 180
 181         m_impl.remove(it);
 182         return true;
 183     }
 184
 185     template<typename Value, typename HashFunctions, typename Traits>
 186     inline void HashCountedSet<Value, HashFunctions, Traits>::removeAll(const ValueType& value)
 187     {
 188         removeAll(find(value));
 189     }
 190
 191     template<typename Value, typename HashFunctions, typename Traits>
 192     inline void HashCountedSet<Value, HashFunctions, Traits>::removeAll(iterator it)
 193     {
 194         if (it == end())
 195             return;
 196
 197         m_impl.remove(it);
 198     }
 199
 200     template<typename Value, typename HashFunctions, typename Traits>
 201     inline void HashCountedSet<Value, HashFunctions, Traits>::clear()
 202     {
 203         m_impl.clear();
 204     }
 205
 206     template<typename Value, typename HashFunctions, typename Traits, typename VectorType>
 207     inline void copyToVector(const HashCountedSet<Value, HashFunctions, Traits>& collection, VectorType& vector)
 208     {
 209         typedef typename HashCountedSet<Value, HashFunctions, Traits>::const_iterator iterator;
 210
 211         vector.resize(collection.size());
 212
 213         iterator it = collection.begin();
 214         iterator end = collection.end();
 215         for (unsigned i = 0; it != end; ++it, ++i)
 216             vector[i] = *it;
 217     }
 218
 219     template<typename Value, typename HashFunctions, typename Traits>
 220     inline void copyToVector(const HashCountedSet<Value, HashFunctions, Traits>& collection, Vector<Value>& vector)
 221     {
 222         typedef typename HashCountedSet<Value, HashFunctions, Traits>::const_iterator iterator;
 223
 224         vector.resize(collection.size());
 225
 226         iterator it = collection.begin();
 227         iterator end = collection.end();
 228         for (unsigned i = 0; it != end; ++it, ++i)
 229             vector[i] = (*it).key;
 230     }
 231
 232
 233 } // namespace WTF
 234
 235 using WTF::HashCountedSet;
 236
 237 #endif /* WTF_HashCountedSet_h */