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 

    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 */