List.h

#pragma once


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


UTL_NS_BEGIN;


class ListIt;



class List : public SortedCollection
{
    UTL_CLASS_DECL(List, SortedCollection);

public:
    typedef ListIt iterator;

public:
    List(bool owner, bool multiSet = true, bool keepSorted = false, Ordering* ordering = nullptr);

    virtual void steal(Object& rhs);

    virtual size_t innerAllocatedSize() const;



    Object*
    front() const
    {
        return first();
    }

    Object*
    back() const
    {
        return last();
    }

    const ListNode*
    frontNode() const
    {
        return _front;
    }

    bool
    isKeptSorted() const
    {
        return getFlag(flg_keepSorted);
    }

    bool
    isSorted() const
    {
        return getFlag(flg_sorted);
    }



    void
    setKeepSorted(bool keepSorted)
    {
        setFlag(flg_keepSorted, keepSorted);
        if (keepSorted) setFlag(flg_sorted, true);
    }

    virtual void setOrdering(Ordering* ordering, uint_t algorithm = sort_mergeSort);

    void
    setOrdering(const Ordering& ordering, uint_t algorithm = sort_mergeSort)
    {
        setOrdering(ordering.clone(), algorithm);
    }

    void
    setSorted(bool sorted)
    {
        setFlag(flg_sorted, sorted);
        if (!sorted) setFlag(flg_keepSorted, false);
    }

    void
    sort()
    {
        sort(sort_mergeSort);
    }

    virtual void sort(uint_t algorithm);

    void moveBefore(const iterator& lhs, const iterator& rhs);


    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
    findEqualRange(const Object& key, BidIt& begin, BidIt& end) const
    {
        const_cast_this->findEqualRange(key, begin, end);
        IFDEBUG(begin.setConst(true));
        IFDEBUG(end.setConst(true));
    }

    virtual void findEqualRange(const Object& key, BidIt& begin, BidIt& end);

    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 addBefore(const Object* object, const iterator& it);

    void
    pushFront(const Object& object)
    {
        isOwner() ? pushFront(object.clone()) : pushFront(&object);
    }

    void
    pushBack(const Object& object)
    {
        isOwner() ? pushBack(object.clone()) : pushBack(&object);
    }

    void pushFront(const Object* object);

    void pushBack(const Object* object);

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

    bool removeFront();

    bool removeBack();

    Object* popFront();

    Object* popBack();


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

private:
    void init(bool owner = true,
              bool multiSet = true,
              bool keepSorted = false,
              Ordering* ordering = nullptr);
    void deInit();
    ListNode* findInsertionPoint(const Object& key) const;
    iterator findIt(const Object& key, uint_t findType) const;
    iterator findIt(const Object& key, uint_t findType);
    ListNode* findNode(const Object& key) const;
    ListNode* insertionSort(ListNode* c);
    ListNode* merge(ListNode* a, ListNode* b);
    ListNode* mergeSort(ListNode* c);
    void removeNode(ListNode* node);

private:
    ListNode *_front, *_back;
    enum flg_t
    {
        flg_keepSorted = 4,
        flg_sorted = 5
    };
};


UTL_NS_END;


#include <libutl/TList.h>