Hashtable.h

#pragma once


#include <libutl/BitArray.h>
#include <libutl/Collection.h>
#include <libutl/PointerIntPair.h>
#include <libutl/Vector.h>
#include <libutl/dlist.h>


UTL_NS_BEGIN;


class HashFunction;
class HashtableIt;

// HashFunction ////////////////////////////////////////////////////////////////////////////////////


class HashFunction
{
public:
    virtual ~HashFunction()
    {
    }

    virtual HashFunction* clone() const = 0;

    virtual size_t
    hash(const Object* object, size_t size) const
    {
        return object->hash(size);
    }

    size_t operator()(const Object* object, size_t size) const
    {
        return hash(object, size);
    }
};

// Hashtable ///////////////////////////////////////////////////////////////////////////////////////


class Hashtable : public Collection
{
    UTL_CLASS_DECL(Hashtable, Collection);
    friend class HashtableIt;

public:
    typedef HashtableIt iterator;

public:
    Hashtable(size_t size,
              uint_t maxLF = 90,
              bool owner = true,
              bool multiSet = false,
              const HashFunction* hfunc = nullptr)
    {
        init(size, maxLF, owner, multiSet, hfunc);
    }

    Hashtable(bool owner, bool multiSet = false, const HashFunction* hfunc = nullptr)
    {
        init(0, 90, owner, multiSet, hfunc);
    }

    virtual void steal(Object& rhs);

    virtual void vclone(const Object& rhs);

    virtual size_t innerAllocatedSize() const;



    void
    setHashFunction(const HashFunction* hashfn)
    {
        delete _hashfn;
        _hashfn = hashfn;
    }

    void reserve(size_t newSize);


    virtual Object* find(const Object& key) const;

    iterator findIt(const Object& key) const;

    iterator findIt(const Object& key);

    void
    findIt(const Object& key, BidIt& it) const
    {
        const_cast_this->findIt(key, it);
        IFDEBUG(it.setConst(true));
    }

    virtual void findIt(const Object& key, BidIt& it);


    bool
    add(const Object& object)
    {
        return super::add(object);
    }

    virtual bool add(const Object* object);

    void
    add(const Collection& collection)
    {
        super::add(collection);
    }

    Object*
    addOrFind(const Object& object)
    {
        return super::addOrFind(object);
    }

    virtual Object* addOrFind(const Object* object);

    bool
    addOrUpdate(const Object& object)
    {
        return super::addOrUpdate(object);
    }

    virtual bool addOrUpdate(const Object* object);


    virtual void clear();

    void excise();

    bool
    remove(const Object* key)
    {
        ASSERTD(key != nullptr);
        return remove(*key);
    }

    virtual bool remove(const Object& key);

    virtual void removeIt(BidIt& it);


    iterator begin() const;

    iterator begin();

    virtual BidIt* beginNew() const;

    virtual BidIt* beginNew();

    inline iterator end() const;

    inline iterator end();

    virtual BidIt* endNew() const;

    virtual BidIt* endNew();

private:
    void init(size_t size = 0,
              uint_t maxLF = 90,
              bool owner = true,
              bool multiSet = false,
              const HashFunction* hashfn = nullptr);
    void deInit();

    void grow(size_t newSize);

    void find(const Object& key, size_t& idx, ListNode*& node) const;

    void remove(size_t idx, ListNode* node);

    size_t
    hash(const Object* object) const
    {
        ASSERTD(object != nullptr);
        if (_hashfn == nullptr) return object->hash(_array.size());
        return _hashfn->hash(object, _array.size());
    }

    bool
    isObject(size_t idx) const
    {
        return (_array[idx].getInt() == 0);
    }

    auto getObject(size_t idx) const
    {
        ASSERTD(isObject(idx));
        return _array[idx].getPointer();
    }

    auto setObject(size_t idx, Object* obj)
    {
        _array[idx].set(obj, 0);
        return obj;
    }

    bool
    isHead(size_t idx) const
    {
        return (_array[idx].getInt() == 1);
    }

    ListNode*
    getHead(size_t idx) const
    {
        ASSERTD(isHead(idx));
        return reinterpret_cast<ListNode*>(_array[idx].getPointer());
    }

    void
    setHead(size_t idx, ListNode* ln)
    {
        _array[idx].set(reinterpret_cast<Object*>(ln), 1);
    }

private:
    typedef PointerIntPair<Object*, 1> pip_t;

private:
    const HashFunction* _hashfn;
    size_t _limit;
    uint_t _maxLF;
    Vector<pip_t> _array;
    static size_t primes[];
};


UTL_NS_END;


#include <libutl/THashtable.h>