SortedCollection.h

#pragma once


#include <libutl/Collection.h>
#include <libutl/Ordering.h>


UTL_NS_BEGIN;



class SortedCollection : public Collection
{
    UTL_CLASS_DECL_ABC(SortedCollection, Collection);
    UTL_CLASS_DEFID;

public:
    void clobber(const SortedCollection* rhs);

    virtual int compare(const Object& rhs) const;

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

    void
    insert(const Object& object, const BidIt& it)
    {
        if (isOwner())
            insert(object.clone(), it);
        else
            return insert(&object, it);
    }

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

    void reverse();



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

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



    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);
        IFDEBUG(it.setConst(true));
    }

    virtual void findFirstIt(const Object& key, BidIt& it, 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);

    Object* findLinear(const Object& key) const;

    Object* findLinearSorted(const Object& key) const;


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

    virtual bool
    remove(const Object& key)
    {
        return super::remove(key);
    }

    void
    remove(const SortedCollection* rhs)
    {
        difference(rhs, this);
    }

    virtual void
    removeIt(BidIt& it)
    {
        super::removeIt(it);
    }

    virtual void removeIt(BidIt& begin, const BidIt& end);

    SortedCollection& operator-=(const SortedCollection& rhs)
    {
        remove(rhs);
        return *this;
    }



    Collection* difference(const SortedCollection* rhs, Collection* out = nullptr) const;

    void
    intersect(const SortedCollection* rhs)
    {
        intersection(rhs, this);
    }

    Collection* intersection(const SortedCollection* rhs,
                             Collection* out = nullptr,
                             bool multiSet = false) const;

    size_t intersectCard(const SortedCollection* rhs) const;

    bool intersects(const SortedCollection* rhs) const;

    bool isSubSet(const SortedCollection* rhs) const;

    bool
    isSuperSet(const SortedCollection* rhs) const
    {
        return rhs->isSubSet(this);
    }

    Collection* merge(const SortedCollection* rhs, Collection* out = nullptr) const;

    Collection* symmetricDifference(const SortedCollection* rhs, Collection* out = nullptr) const;

    void
    symmetricDifference(const SortedCollection* rhs, Collection* lhsOut, Collection* rhsOut) const;

    Collection* unique(Collection* out = nullptr);

    SortedCollection& operator&=(const SortedCollection* rhs)
    {
        intersect(rhs);
        return *this;
    }

    bool operator<=(const SortedCollection* rhs)
    {
        return isSubSet(rhs);
    }

    bool operator>=(const SortedCollection* rhs)
    {
        return isSuperSet(rhs);
    }


    bool testSorted() const;


    void multiKeyQuickSort(bool key = true, bool reverse = false);

    void
    sort()
    {
        sort(sort_quickSort);
    }

    virtual void sort(uint_t algorithm);

#ifdef DEBUG
    virtual void sanityCheck() const;
#endif
protected:
    inline int
    compareObjects(const Object* lhs, const Object* rhs) const
    {
        return super::compareObjects(lhs, rhs);
    }

#ifdef DEBUG
    void checkInsert(const Object* object, const BidIt& it, bool sorted) const;
#endif
};


UTL_NS_END;