/*
 * Copyright 2004-2009, Ingo Weinhold, ingo_weinhold@gmx.de.
 * Copyright 2019, Haiku, Inc. All rights reserved.
 * Distributed under the terms of the MIT License.
 */
#ifndef HASH_SET_H
#define HASH_SET_H

#include <Locker.h>
#include <util/OpenHashTable.h>

#include "AutoLocker.h"


namespace BPrivate {


// HashSetElement
template<typename Key>
class HashSetElement {
private:
        typedef HashSetElement<Key> Element;

public:
        HashSetElement()
                :
                fKey(),
                fNext(NULL)
        {
        }

        HashSetElement(const Key& key)
                :
                fKey(key),
                fNext(NULL)
        {
        }

        Key                             fKey;
        HashSetElement* fNext;
};


// HashSetTableDefinition
template<typename Key>
struct HashSetTableDefinition {
        typedef Key                                     KeyType;
        typedef HashSetElement<Key>     ValueType;

        size_t HashKey(const KeyType& key) const
                { return key.GetHashCode(); }
        size_t Hash(const ValueType* value) const
                { return HashKey(value->fKey); }
        bool Compare(const KeyType& key, const ValueType* value) const
                { return value->fKey == key; }
        ValueType*& GetLink(ValueType* value) const
                { return value->fNext; }
};


// HashSet
template<typename Key>
class HashSet {
public:
        class Iterator {
        private:
                typedef HashSetElement<Key>     Element;
        public:
                Iterator(const Iterator& other)
                        :
                        fSet(other.fSet),
                        fIterator(other.fIterator),
                        fElement(other.fElement)
                {
                }

                bool HasNext() const
                {
                        return fIterator.HasNext();
                }

                Key Next()
                {
                        fElement = fIterator.Next();
                        if (fElement == NULL)
                                return Key();

                        return fElement->fKey;
                }

                Iterator& operator=(const Iterator& other)
                {
                        fSet = other.fSet;
                        fIterator = other.fIterator;
                        fElement = other.fElement;
                        return *this;
                }

        private:
                Iterator(const HashSet<Key>* set)
                        :
                        fSet(set),
                        fIterator(set->fTable.GetIterator()),
                        fElement(NULL)
                {
                }

        private:
                typedef BOpenHashTable<HashSetTableDefinition<Key> > ElementTable;

                const HashSet<Key>*                             fSet;
                typename ElementTable::Iterator fIterator;
                Element*                                                fElement;

        private:
                friend class HashSet<Key>;
        };

        HashSet();
        ~HashSet();

        status_t InitCheck() const;

        status_t Add(const Key& key);
        bool Remove(const Key& key);
        bool Remove(Iterator& it);
        void Clear();
        bool Contains(const Key& key) const;

        int32 Size() const;

        Iterator GetIterator() const;

protected:
        typedef BOpenHashTable<HashSetTableDefinition<Key> > ElementTable;
        typedef HashSetElement<Key>     Element;
        friend class Iterator;

protected:
        ElementTable    fTable;
};


// SynchronizedHashSet
template<typename Key, typename Locker = BLocker>
class SynchronizedHashSet : public Locker {
public:
        typedef typename HashSet<Key>::Iterator Iterator;

        SynchronizedHashSet() : Locker("synchronized hash set") {}
        ~SynchronizedHashSet()  { Locker::Lock(); }

        status_t InitCheck() const
        {
                return fSet.InitCheck();
        }

        status_t Add(const Key& key)
        {
                MapLocker locker(this);
                if (!locker.IsLocked())
                        return B_ERROR;
                return fSet.Add(key);
        }

        bool Remove(const Key& key)
        {
                MapLocker locker(this);
                if (!locker.IsLocked())
                        return false;
                return fSet.Remove(key);
        }

        void Clear()
        {
                MapLocker locker(this);
                fSet.Clear();
        }

        bool Contains(const Key& key) const
        {
                const Locker* lock = this;
                MapLocker locker(const_cast<Locker*>(lock));
                if (!locker.IsLocked())
                        return false;
                return fSet.Contains(key);
        }

        int32 Size() const
        {
                const Locker* lock = this;
                MapLocker locker(const_cast<Locker*>(lock));
                return fSet.Size();
        }

        Iterator GetIterator() const
        {
                return fSet.GetIterator();
        }

        // for debugging only
        const HashSet<Key>& GetUnsynchronizedSet() const        { return fSet; }
        HashSet<Key>& GetUnsynchronizedSet()                            { return fSet; }

protected:
        typedef AutoLocker<Locker> MapLocker;

        HashSet<Key>    fSet;
};


// HashSet

// constructor
template<typename Key>
HashSet<Key>::HashSet()
        :
        fTable()
{
        fTable.Init();
}


// destructor
template<typename Key>
HashSet<Key>::~HashSet()
{
        Clear();
}


// InitCheck
template<typename Key>
status_t
HashSet<Key>::InitCheck() const
{
        return (fTable.TableSize() > 0 ? B_OK : B_NO_MEMORY);
}


// Add
template<typename Key>
status_t
HashSet<Key>::Add(const Key& key)
{
        Element* element = fTable.Lookup(key);
        if (element) {
                // already contains the value
                return B_OK;
        }

        // does not contain the key yet: create an element and add it
        element = new(std::nothrow) Element(key);
        if (!element)
                return B_NO_MEMORY;

        status_t error = fTable.Insert(element);
        if (error != B_OK)
                delete element;

        return error;
}


// Remove
template<typename Key>
bool
HashSet<Key>::Remove(const Key& key)
{
        Element* element = fTable.Lookup(key);
        if (element == NULL)
                return false;

        fTable.Remove(element);
        delete element;

        return true;
}


// Remove
template<typename Key>
bool
HashSet<Key>::Remove(Iterator& it)
{
        Element* element = it.fElement;
        if (element == NULL)
                return false;

        fTable.RemoveUnchecked(element);
        delete element;
        it.fElement = NULL;

        return true;
}


// Clear
template<typename Key>
void
HashSet<Key>::Clear()
{
        // clear the table and delete the elements
        Element* element = fTable.Clear(true);
        while (element != NULL) {
                Element* next = element->fNext;
                delete element;
                element = next;
        }
}


// Contains
template<typename Key>
bool
HashSet<Key>::Contains(const Key& key) const
{
        return fTable.Lookup(key) != NULL;
}


// Size
template<typename Key>
int32
HashSet<Key>::Size() const
{
        return fTable.CountElements();
}


// GetIterator
template<typename Key>
typename HashSet<Key>::Iterator
HashSet<Key>::GetIterator() const
{
        return Iterator(this);
}

} // namespace BPrivate

using BPrivate::HashSet;

#endif  // HASH_SET_H