SkipList.h

#pragma once


#include <libutl/SortedCollection.h>
#include <libutl/SkipListNode.h>

// comment out this #define to try the regular/deterministic method of setting node level
//#define UTL_SKIPLIST_RNG
#ifdef UTL_SKIPLIST_RNG
#include <libutl/RandUtils.h>
#endif


UTL_NS_BEGIN;


class SkipListIt;



class SkipList : public SortedCollection
{
    UTL_CLASS_DECL(SkipList, SortedCollection);
    friend class SkipListIt;

public:
    typedef SkipListIt iterator;

public:
    SkipList(bool owner, bool multiSet = false, Ordering* ordering = nullptr, uint_t maxLevel = 19)
    {
        init(owner, multiSet, ordering, maxLevel);
    }

    virtual void steal(Object& rhs);

    virtual size_t innerAllocatedSize() const;


    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);

    void
    findFirstIt(const Object& key, BidIt& it, bool insert = false) const
    {
        const_cast_this->findFirstIt(key, it, insert);
        IFDEBUG(it.setConst(true));
    }

    virtual void findFirstIt(const Object& key, BidIt& it, bool insert = false);

    iterator findFirstIt(const Object& key, bool insert = false) const;

    iterator findFirstIt(const Object& key, bool insert = false);

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

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

    iterator findLastIt(const Object& key) const;

    iterator findLastIt(const Object& key);


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

    virtual bool add(const Object* object);

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

    void
    insert(const Object& object, const BidIt& it)
    {
        return super::insert(object, it);
    }

    virtual void insert(const Object* object, const BidIt& it);


    virtual void clear();

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

    virtual bool remove(const Object& key);

    virtual void removeIt(BidIt& it);


    inline iterator begin() const;

    inline iterator begin();

    inline virtual BidIt* beginNew() const;

    inline virtual BidIt* beginNew();

    inline iterator end() const;

    inline iterator end();

    inline virtual BidIt* endNew() const;

    inline virtual BidIt* endNew();

    static void utl_init();

    static void utl_deInit();

private:
    void init(bool owner = true,
              bool multiSet = false,
              Ordering* ordering = nullptr,
              uint_t maxLevel = 19);
    void deInit();
    iterator findIt(const Object& key, uint_t findType) const;
    iterator findIt(const Object& key, uint_t findType);
    SkipListNode* findNode(const Object& key,
                           uint_t findType = find_first,
                           SkipListNode** update = nullptr) const;
    void removeNode(SkipListNode* node, SkipListNode** update);

private:
    SkipListNode *_head, *_tail;
    uint_t _level;
    uint_t _maxLevel;
#ifdef UTL_SKIPLIST_RNG
    randutils::default_rng* _rng;
#else
    uint32_t _counter;
    uint32_t _counterLim;
#endif
};


UTL_NS_END;


#include <libutl/TSkipList.h>