/*

* Copyright (C) 2005, 2006, 2008, 2013 Apple Inc. All rights reserved.

*

* This library is free software; you can redistribute it and/or

* modify it under the terms of the GNU Library General Public

* License as published by the Free Software Foundation; either

* version 2 of the License, or (at your option) any later version.

*

* This library is distributed in the hope that it will be useful,

* but WITHOUT ANY WARRANTY; without even the implied warranty of

* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU

* Library General Public License for more details.

*

* You should have received a copy of the GNU Library General Public License

* along with this library; see the file COPYING.LIB. If not, write to

* the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,

* Boston, MA 02110-1301, USA.

*

*/

#ifndef WTF_HashCountedSet_h

#define WTF_HashCountedSet_h

#include <wtf/Assertions.h>

#include <wtf/HashMap.h>

#include <wtf/Vector.h>

namespace WTF {

template<typename Value, typename HashFunctions = typename DefaultHash<Value>::Hash, typename Traits = HashTraits<Value>>

class HashCountedSet {

WTF_MAKE_FAST_ALLOCATED;

private:

typedef HashMap<Value, unsigned, HashFunctions, Traits> ImplType;

public:

typedef Value ValueType;

typedef typename ImplType::iterator iterator;

typedef typename ImplType::const_iterator const_iterator;

typedef typename ImplType::AddResult AddResult;

void swap(HashCountedSet&);

int size() const;

int capacity() const;

bool isEmpty() const;

// Iterators iterate over pairs of values and counts.

iterator begin();

iterator end();

const_iterator begin() const;

const_iterator end() const;

iterator find(const ValueType&);

const_iterator find(const ValueType&) const;

bool contains(const ValueType&) const;

unsigned count(const ValueType&) const;

// Increments the count if an equal value is already present.

// The return value includes both an iterator to the value's location,

// and an isNewEntry bool that indicates whether it is a new or existing entry.

AddResult add(const ValueType&);

// Decrements the count of the value, and removes it if count goes down to zero.

// Returns true if the value is removed.

bool remove(const ValueType&);

bool remove(iterator);

// Removes the value, regardless of its count.

// Returns true if a value was removed.

bool removeAll(iterator);

bool removeAll(const ValueType&);

// Clears the whole set.

void clear();

private:

ImplType m_impl;

};

template<typename Value, typename HashFunctions, typename Traits>

inline void HashCountedSet<Value, HashFunctions, Traits>::swap(HashCountedSet& other)

{

m_impl.swap(other.m_impl);

}

template<typename Value, typename HashFunctions, typename Traits>

inline int HashCountedSet<Value, HashFunctions, Traits>::size() const

{

return m_impl.size();

}

template<typename Value, typename HashFunctions, typename Traits>

inline int HashCountedSet<Value, HashFunctions, Traits>::capacity() const

{

return m_impl.capacity();

}

template<typename Value, typename HashFunctions, typename Traits>

inline bool HashCountedSet<Value, HashFunctions, Traits>::isEmpty() const

{

return size() == 0;

}

template<typename Value, typename HashFunctions, typename Traits>

inline typename HashCountedSet<Value, HashFunctions, Traits>::iterator HashCountedSet<Value, HashFunctions, Traits>::begin()

{

return m_impl.begin();

}

template<typename Value, typename HashFunctions, typename Traits>

inline typename HashCountedSet<Value, HashFunctions, Traits>::iterator HashCountedSet<Value, HashFunctions, Traits>::end()

{

return m_impl.end();

}

template<typename Value, typename HashFunctions, typename Traits>

inline typename HashCountedSet<Value, HashFunctions, Traits>::const_iterator HashCountedSet<Value, HashFunctions, Traits>::begin() const

{

return m_impl.begin();

}

template<typename Value, typename HashFunctions, typename Traits>

inline typename HashCountedSet<Value, HashFunctions, Traits>::const_iterator HashCountedSet<Value, HashFunctions, Traits>::end() const

{

return m_impl.end();

}

template<typename Value, typename HashFunctions, typename Traits>

inline typename HashCountedSet<Value, HashFunctions, Traits>::iterator HashCountedSet<Value, HashFunctions, Traits>::find(const ValueType& value)

{

return m_impl.find(value);

}

template<typename Value, typename HashFunctions, typename Traits>

inline typename HashCountedSet<Value, HashFunctions, Traits>::const_iterator HashCountedSet<Value, HashFunctions, Traits>::find(const ValueType& value) const

{

return m_impl.find(value);

}

template<typename Value, typename HashFunctions, typename Traits>

inline bool HashCountedSet<Value, HashFunctions, Traits>::contains(const ValueType& value) const

{

return m_impl.contains(value);

}

template<typename Value, typename HashFunctions, typename Traits>

inline unsigned HashCountedSet<Value, HashFunctions, Traits>::count(const ValueType& value) const

{

return m_impl.get(value);

}

template<typename Value, typename HashFunctions, typename Traits>

inline typename HashCountedSet<Value, HashFunctions, Traits>::AddResult HashCountedSet<Value, HashFunctions, Traits>::add(const ValueType &value)

{

AddResult result = m_impl.add(value, 0);

++result.iterator->value;

return result;

}

template<typename Value, typename HashFunctions, typename Traits>

inline bool HashCountedSet<Value, HashFunctions, Traits>::remove(const ValueType& value)

{

return remove(find(value));

}

template<typename Value, typename HashFunctions, typename Traits>

inline bool HashCountedSet<Value, HashFunctions, Traits>::remove(iterator it)

{

if (it == end())

return false;

unsigned oldVal = it->value;

ASSERT(oldVal);

unsigned newVal = oldVal - 1;

if (newVal) {

it->value = newVal;

return false;

}

m_impl.remove(it);

return true;

}

template<typename Value, typename HashFunctions, typename Traits>

inline bool HashCountedSet<Value, HashFunctions, Traits>::removeAll(const ValueType& value)

{

return removeAll(find(value));

}

template<typename Value, typename HashFunctions, typename Traits>

inline bool HashCountedSet<Value, HashFunctions, Traits>::removeAll(iterator it)

{

if (it == end())

return false;

m_impl.remove(it);

return true;

}

template<typename Value, typename HashFunctions, typename Traits>

inline void HashCountedSet<Value, HashFunctions, Traits>::clear()

{

m_impl.clear();

}

template<typename Value, typename HashFunctions, typename Traits, typename VectorType>

inline void copyToVector(const HashCountedSet<Value, HashFunctions, Traits>& collection, VectorType& vector)

{

typedef typename HashCountedSet<Value, HashFunctions, Traits>::const_iterator iterator;

vector.resize(collection.size());

iterator it = collection.begin();

iterator end = collection.end();

for (unsigned i = 0; it != end; ++it, ++i)

vector[i] = *it;

}

template<typename Value, typename HashFunctions, typename Traits>

inline void copyToVector(const HashCountedSet<Value, HashFunctions, Traits>& collection, Vector<Value>& vector)

{

typedef typename HashCountedSet<Value, HashFunctions, Traits>::const_iterator iterator;

vector.resize(collection.size());

iterator it = collection.begin();

iterator end = collection.end();

for (unsigned i = 0; it != end; ++it, ++i)

vector[i] = (*it).key;

}

} // namespace khtml

using WTF::HashCountedSet;

#endif /* WTF_HashCountedSet_h */