Array.h

#pragma once


#include <libutl/RandUtils.h>
#include <libutl/SortedCollection.h>
#include <libutl/Vector.h>


UTL_NS_BEGIN;


class ArrayIt;


class Array : public SortedCollection
{
    UTL_CLASS_DECL(Array, SortedCollection);
    friend class ArrayIt;

public:
    typedef Object* const* iterator; // native iterator
    typedef ArrayIt base_iterator;   // iterator for compatibility with base

public:
    Array(size_t size,
          size_t increment = size_t_max,
          bool owner = true,
          bool multiSet = true,
          bool keepSorted = false,
          Ordering* ordering = nullptr);

    Array(bool owner, bool multiSet = true, bool keepSorted = false, Ordering* ordering = nullptr);

    virtual void copy(const Object& rhs);

    virtual void steal(Object& rhs);


    virtual size_t innerAllocatedSize() const;

    size_t
    firstNull() const
    {
        return _firstNull;
    }

    Object*
    get(size_t idx) const
    {
        return _array[idx];
    }

    size_t
    totalSize() const
    {
        return _array.size();
    }

    bool
    hasHole() const
    {
        return (_firstNull != _array.size());
    }

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

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



    void removeHoles(size_t low = 0, size_t high = size_t_max);

    void
    economize()
    {
        _array.economize();
    }

    void
    excise()
    {
        clear();
        _array.clear();
    }

    void
    reserve(size_t minSize)
    {
        _array.reserve(minSize);
    }

    void
    set(size_t idx, const Object& object, size_t firstNull = size_t_max)
    {
        set(idx, isOwner() ? object.clone() : &object, firstNull);
    }

    void set(size_t idx, const Object* object, size_t firstNull = size_t_max);

    void
    setIncrement(size_t increment)
    {
        _array.setIncrement(increment);
    }

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

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

    void
    shuffle(size_t low = 0, size_t high = size_t_max, randutils::mt19937_64_rng* rng = nullptr);

    void
    sort()
    {
        sort(sort_quickSort);
    }

    virtual void sort(uint_t algorithm);


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

    size_t findIndex(const Object& key,
                     uint_t findType = uint_t_max,
                     size_t low = 0,
                     size_t high = size_t_max) const;

    iterator findIt(const Object& key) const;

    void
    findIt(const Object& key, BidIt& it) const
    {
        super::findIt(key, it);
    }

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

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

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

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

    iterator findLastIt(const Object& key) const;

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


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

    virtual bool
    add(const Object* object)
    {
        return add(object, isKeptSorted());
    }

    bool add(const Object* object, bool keepSorted);

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

    void add(size_t idx, size_t num = 1);

    void
    add(size_t idx, const Object& object)
    {
        add(idx, isOwner() ? object.clone() : &object);
    }

    void add(size_t idx, const Object* object);

    void
    insert(const Object& object, iterator it)
    {
        insert(isOwner() ? object.clone() : &object, it);
    }

    void insert(const Object* object, iterator it);

    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, true, true);
    }

    virtual bool
    remove(const Object& key)
    {
        return remove(key, true, true);
    }

    bool remove(const Object& key, bool relocate, bool preserveOrder = true);

    void remove(size_t idx, bool relocate = true, bool preserveOrder = true);

    void removeIt(iterator it, bool relocate = true, bool preserveOrder = true);

    void removeIt(iterator begin, iterator end, bool relocate = true, bool preserveOrder = true);

    virtual void removeIt(BidIt& it);

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

    void removeItems(size_t idx, size_t num, bool relocate = true, bool preserveOrder = true);


    void replace(iterator it, const Object* newObject, bool keepSorted = true);

    void replace(base_iterator& it, const Object* newObject);

    void
    replace(size_t idx, const Object* newObject)
    {
        replace(this->begin() + idx, newObject);
    }

    bool
    replace(const Object& oldObject, const Object* newObject)
    {
        return replace(&oldObject, newObject);
    }

    bool replace(const Object* oldObject, const Object* newObject);



    void
    relocate(iterator destIt, iterator srcIt)
    {
        _array.relocate(indexOf(destIt), indexOf(srcIt));
    }

    void
    relocate(size_t destIdx, size_t srcIdx)
    {
        _array.relocate(destIdx, srcIdx);
    }


    inline iterator
    begin() const
    {
        return _array.begin();
    }

    inline iterator
    end() const
    {
        return _array.end();
    }

    inline virtual RandIt* beginNew() const;

    inline virtual RandIt* beginNew();

    inline virtual RandIt* endNew() const;

    inline virtual RandIt* endNew();

    size_t
    indexOf(iterator it) const
    {
        ASSERTD(isValid(it));
        return it - this->begin();
    }

#ifdef DEBUG
    bool
    isValid(iterator it) const
    {
        return (it >= this->begin()) && (it <= this->end());
    }
#endif




    Object* operator[](size_t idx) const
    {
        return get(idx);
    }

    Object* operator[](int idx) const
    {
        return operator[]((size_t)idx);
    }

    Object* operator[](size_t idx)
    {
        return get(idx);
    }

    Object* operator[](int idx)
    {
        return operator[]((size_t)idx);
    }

#if UTL_HOST_WORDSIZE == 64
    Object* operator[](uint_t idx) const
    {
        return operator[]((size_t)idx);
    }
    Object* operator[](uint_t idx)
    {
        return operator[]((size_t)idx);
    }
#endif

    Object& operator()(size_t idx) const
    {
        ASSERTD(idx < _array.size());
        ASSERTD(_array[idx] != nullptr);
        return *(_array[idx]);
    }

    Object& operator()(size_t idx)
    {
        return const_self(idx);
    }
    Object& operator()(int idx) const
    {
        return operator()((size_t)idx);
    }
    Object& operator()(int idx)
    {
        return operator()((size_t)idx);
    }

#if UTL_HOST_WORDSIZE == 64
    Object& operator()(uint_t idx) const
    {
        return operator()((size_t)idx);
    }
    Object& operator()(uint_t idx)
    {
        return operator()((size_t)idx);
    }
#endif

    Object* operator[](const Object* object)
    {
        return addOrFind(object);
    }

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

#ifdef DEBUG
    virtual void sanityCheck() const;
#endif

private:
    void init(size_t size = 4,
              size_t increment = size_t_max,
              bool owner = true,
              bool multiSet = true,
              bool keepSorted = false,
              Ordering* ordering = nullptr);
    void deInit();

    iterator findIt(const Object& key, uint_t findType) const;

    void _remove(size_t idx);

    void setFirstNull(size_t idx);

    void
    fixArraySize()
    {
        fixArraySize(_array.size());
    }

    void fixArraySize(size_t size);

private:
    enum flg_t
    {
        flg_keepSorted = 4,
        flg_sorted = 5
    };

private:
    size_t _firstNull;
    Vector<Object*> _array;
};


UTL_NS_END;


#include <libutl/ArrayIt.h>
#include <libutl/TArray.h>