#ifndef IndexSparseSet_h
#define IndexSparseSet_h
#include <wtf/HashTraits.h>
#include <wtf/Vector.h>
namespace WTF {
template<typename T>
struct DefaultIndexSparseSetTraits {
typedef T EntryType;
static T create(unsigned entry)
{
return entry;
}
static unsigned key(const T& entry)
{
return entry;
}
};
template<typename KeyType, typename ValueType>
struct DefaultIndexSparseSetTraits<KeyValuePair<KeyType, ValueType>> {
typedef KeyValuePair<KeyType, ValueType> EntryType;
template<typename PassedValueType>
static EntryType create(unsigned key, PassedValueType&& value)
{
return EntryType(key, std::forward<PassedValueType>(value));
}
static unsigned key(const EntryType& entry)
{
return entry.key;
}
};
template<typename EntryType = unsigned, typename EntryTypeTraits = DefaultIndexSparseSetTraits<EntryType>, typename OverflowHandler = CrashOnOverflow>
class IndexSparseSet {
typedef Vector<EntryType, 0, OverflowHandler> ValueList;
public:
explicit IndexSparseSet(unsigned size);
template<typename... Arguments>
bool add(unsigned, Arguments&&...);
template<typename... Arguments>
bool set(unsigned, Arguments&&...);
bool remove(unsigned);
void clear();
unsigned size() const;
bool isEmpty() const;
bool contains(unsigned) const;
const EntryType* get(unsigned) const;
EntryType* get(unsigned);
typedef typename ValueList::const_iterator const_iterator;
const_iterator begin() const;
const_iterator end() const;
void sort();
const ValueList& values() const { return m_values; }
private:
Vector<unsigned, 0, OverflowHandler, 1> m_map;
ValueList m_values;
};
template<typename EntryType, typename EntryTypeTraits, typename OverflowHandler>
inline IndexSparseSet<EntryType, EntryTypeTraits, OverflowHandler>::IndexSparseSet(unsigned size)
{
m_map.grow(size);
}
template<typename EntryType, typename EntryTypeTraits, typename OverflowHandler>
template<typename... Arguments>
inline bool IndexSparseSet<EntryType, EntryTypeTraits, OverflowHandler>::add(unsigned value, Arguments&&... arguments)
{
if (contains(value))
return false;
unsigned newPosition = m_values.size();
m_values.append(EntryTypeTraits::create(value, std::forward<Arguments>(arguments)...));
m_map[value] = newPosition;
return true;
}
template<typename EntryType, typename EntryTypeTraits, typename OverflowHandler>
template<typename... Arguments>
inline bool IndexSparseSet<EntryType, EntryTypeTraits, OverflowHandler>::set(unsigned value, Arguments&&... arguments)
{
if (EntryType* entry = get(value)) {
*entry = EntryTypeTraits::create(value, std::forward<Arguments>(arguments)...);
return false;
}
unsigned newPosition = m_values.size();
m_values.append(EntryTypeTraits::create(value, std::forward<Arguments>(arguments)...));
m_map[value] = newPosition;
return true;
}
template<typename EntryType, typename EntryTypeTraits, typename OverflowHandler>
inline bool IndexSparseSet<EntryType, EntryTypeTraits, OverflowHandler>::remove(unsigned value)
{
unsigned position = m_map[value];
if (position >= m_values.size())
return false;
if (m_values[position] == value) {
EntryType lastValue = m_values.last();
m_values[position] = WTFMove(lastValue);
m_map[EntryTypeTraits::key(lastValue)] = position;
m_values.removeLast();
return true;
}
return false;
}
template<typename EntryType, typename EntryTypeTraits, typename OverflowHandler>
void IndexSparseSet<EntryType, EntryTypeTraits, OverflowHandler>::clear()
{
m_values.shrink(0);
}
template<typename EntryType, typename EntryTypeTraits, typename OverflowHandler>
unsigned IndexSparseSet<EntryType, EntryTypeTraits, OverflowHandler>::size() const
{
return m_values.size();
}
template<typename EntryType, typename EntryTypeTraits, typename OverflowHandler>
bool IndexSparseSet<EntryType, EntryTypeTraits, OverflowHandler>::isEmpty() const
{
return !size();
}
template<typename EntryType, typename EntryTypeTraits, typename OverflowHandler>
bool IndexSparseSet<EntryType, EntryTypeTraits, OverflowHandler>::contains(unsigned value) const
{
unsigned position = m_map[value];
if (position >= m_values.size())
return false;
return EntryTypeTraits::key(m_values[position]) == value;
}
template<typename EntryType, typename EntryTypeTraits, typename OverflowHandler>
auto IndexSparseSet<EntryType, EntryTypeTraits, OverflowHandler>::get(unsigned value) -> EntryType*
{
unsigned position = m_map[value];
if (position >= m_values.size())
return nullptr;
EntryType& entry = m_values[position];
if (EntryTypeTraits::key(entry) != value)
return nullptr;
return &entry;
}
template<typename EntryType, typename EntryTypeTraits, typename OverflowHandler>
auto IndexSparseSet<EntryType, EntryTypeTraits, OverflowHandler>::get(unsigned value) const -> const EntryType*
{
return const_cast<IndexSparseSet*>(this)->get(value);
}
template<typename EntryType, typename EntryTypeTraits, typename OverflowHandler>
void IndexSparseSet<EntryType, EntryTypeTraits, OverflowHandler>::sort()
{
std::sort(
m_values.begin(), m_values.end(),
[&] (const EntryType& a, const EntryType& b) {
return EntryTypeTraits::key(a) < EntryTypeTraits::key(b);
});
}
template<typename EntryType, typename EntryTypeTraits, typename OverflowHandler>
auto IndexSparseSet<EntryType, EntryTypeTraits, OverflowHandler>::begin() const -> const_iterator
{
return m_values.begin();
}
template<typename EntryType, typename EntryTypeTraits, typename OverflowHandler>
auto IndexSparseSet<EntryType, EntryTypeTraits, OverflowHandler>::end() const -> const_iterator
{
return m_values.end();
}
}
using WTF::DefaultIndexSparseSetTraits;
using WTF::IndexSparseSet;
#endif // IndexSparseSet_h