Home | History | Annotate | Download | only in wtf 
      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 */
    229