Vector.h

#pragma once


#include <libutl/FlagsMI.h>


UTL_NS_BEGIN;



template <typename T>
class Vector : public Object, protected FlagsMI
{
    UTL_CLASS_DECL_TPL(Vector, T, Object);

public:
    typedef T type;
    typedef T value_type;
    typedef T* iterator;
    typedef const T* const_iterator;

public:
    Vector(std::initializer_list<T> list);

    Vector(size_t size, size_t increment = 1);

    Vector(T* array, size_t size, bool owner = true, size_t increment = 1);


    virtual int compare(const Object& rhs) const;

    virtual size_t
    innerAllocatedSize() const
    {
        if (!isOwner()) return 0;
        return (_allocSize * sizeof(T));
    }

    bool
    isOwner() const
    {
        return getFlag(flg_owner);
    }

    bool
    autoInit() const
    {
        return getFlag(flg_autoInit);
    }

    const T*
    get() const
    {
        return _array;
    }

    T*
    get()
    {
        return _array;
    }

    const T&
    get(size_t idx) const
    {
        ASSERTD(idx < _size);
        return _array[idx];
    }

    const T&
    get(int idx) const
    {
        return get((size_t)idx);
    }

#if UTL_HOST_WORDSIZE == 64

    const T&
    get(uint_t idx) const
    {
        return get((size_t)idx);
    }
#endif

    bool
    empty() const
    {
        return (_size == 0);
    }

    size_t
    length() const
    {
        return _size;
    }

    size_t
    size() const
    {
        return _size;
    }

    size_t
    increment() const
    {
        return _increment;
    }



    const_iterator
    begin() const
    {
        return _array;
    }

    const_iterator
    end() const
    {
        return _array + _size;
    }

    const_iterator
    cbegin()
    {
        return _array;
    }

    const_iterator
    cend()
    {
        return _array + _size;
    }

    iterator
    begin()
    {
        return _array;
    }

    iterator
    end()
    {
        return _array + _size;
    }



    size_t
    indexOf(const_iterator it) const
    {
        ASSERTD((it >= this->begin()) && (it <= this->end()));
        return (it - this->begin());
    }

    size_t
    indexOf(iterator it)
    {
        ASSERTD((it >= this->begin()) && (it <= this->end()));
        return (it - this->begin());
    }



    void
    clear()
    {
        _size = 0;
    }

    void excise();

    void economize();

    virtual void steal(Object& rhs);

    virtual void copy(const Object&);

    void
    copy(size_t idx, const Vector<T>& src, size_t srcBegin = 0, size_t srcEnd = size_t_max)
    {
        copy(idx, src._array, srcBegin, min(srcEnd, src._size));
    }

    void copy(size_t idx, const T* src, size_t srcBegin, size_t srcEnd);

    void copy(size_t idx, std::initializer_list<T> list);

    void
    move(size_t idx, const Vector<T>& src, size_t srcBegin = 0, size_t srcEnd = size_t_max)
    {
        move(idx, src._array, srcBegin, min(srcEnd, src._size));
    }

    void move(size_t idx, T* src, size_t srcBegin, size_t srcEnd);

    virtual void serialize(Stream& stream, uint_t io, uint_t mode = ser_default);

    void
    setOwner(bool owner)
    {
        setFlag(flg_owner, owner);
    }

    void assertOwner();

    void assertOwner(size_t allocSize);

    void
    assertOwner(size_t allocSize, size_t increment)
    {
        setIncrement(increment);
        assertOwner(allocSize);
    }

    T&
    get(size_t idx)
    {
        ASSERTD(idx < _size);
        return _array[idx];
    }

    T&
    get(int idx)
    {
        return get((size_t)idx);
    }

#if UTL_HOST_WORDSIZE == 64

    T&
    get(uint_t idx)
    {
        return get((size_t)idx);
    }
#endif

    void setSize(size_t size);

    void grow(size_t size);

    void
    grow(size_t size, size_t increment)
    {
        setIncrement(increment);
        grow(size);
    }

    void
    reserve(size_t allocSize)
    {
        if (allocSize > _allocSize) assertOwner(allocSize);
    }

    void
    reserve(size_t allocSize, size_t increment)
    {
        if (allocSize > _allocSize) assertOwner(allocSize, increment);
    }

    void
    setAutoInit(bool autoInit)
    {
        setFlag(flg_autoInit, autoInit);
    }

    void
    append(const T& val)
    {
        append(&val, 1);
    }

    void
    append(const Vector<T>& v)
    {
        append(v._array, v._size);
    }

    void append(const T* array, size_t arraySize);

    void append(std::initializer_list<T> list);

    void insert(size_t idx, size_t num);

    void
    insert(size_t idx, size_t num, const T& val)
    {
        insert(idx, num);
        set(idx, num, val);
    }

    void
    insert(size_t idx, size_t num, const T* val)
    {
        insert(idx, num);
        set(idx, num, *val);
    }

    void
    insert(size_t idx, const T* array, size_t arraySize)
    {
        insert(idx, arraySize);
        copy(idx, array, 0, arraySize);
    }

    void
    insert(size_t idx, std::initializer_list<T> list)
    {
        insert(idx, list.size());
        copy(idx, list);
    }

    void remove(size_t idx, size_t num);

    void relocate(size_t destIdx, size_t srcIdx);

    void reverse(size_t idx, size_t num);

    void
    set(T* array, size_t size)
    {
        set(array, size, isOwner(), _increment);
    }

    void set(T* array, size_t size, bool owner, size_t increment);

    void
    set(const T& val)
    {
        set(0, _size, val);
    }

    void set(size_t idx, size_t num, const T& val);

    void
    set(size_t idx, const T& val)
    {
        ASSERTD(idx < _size);
        _array[idx] = val;
    }

    void
    setIncrement(size_t increment)
    {
        ASSERTD((increment == size_t_max) || (increment == nextPow2(increment)));
        _increment = increment;
    }

    inline void swap(size_t i, size_t j);

    inline void swap(size_t i, size_t j, size_t n);



    T& operator[](size_t idx)
    {
        ASSERTD(idx < _size);
        return _array[idx];
    }

    const T& operator[](size_t idx) const
    {
        ASSERTD(idx < _size);
        return _array[idx];
    }

    T& operator[](int idx)
    {
        return operator[]((size_t)idx);
    }

    const T& operator[](int idx) const
    {
        return operator[]((size_t)idx);
    }

#if UTL_HOST_WORDSIZE == 64

    T& operator[](uint_t idx)
    {
        return operator[]((size_t)idx);
    }

    const T& operator[](uint_t idx) const
    {
        return operator[]((size_t)idx);
    }
#endif

    operator const T*() const
    {
        return _array;
    }

    operator const T*()
    {
        return _array;
    }

    operator T*()
    {
        return _array;
    }

    operator const void*() const
    {
        return _array;
    }

    operator const void*()
    {
        return _array;
    }

    operator void*()
    {
        return _array;
    }

    T* operator+(ssize_t n)
    {
        ASSERTD(n >= 0);
        ASSERTD((size_t)n <= _size);
        return _array + n;
    }

    const T* operator+(ssize_t n) const
    {
        ASSERTD(n >= 0);
        ASSERTD((size_t)n <= _size);
        return _array + n;
    }

    T* operator+(size_t n)
    {
        ASSERTD(n <= _size);
        return _array + n;
    }

    const T* operator+(size_t n) const
    {
        ASSERTD(n <= _size);
        return _array + n;
    }
protected:
    T* _array;
    size_t _size;
    size_t _allocSize;
    size_t _increment;

private:
    inline void
    init()
    {
        _array = nullptr;
        _size = _allocSize = 0;
        _increment = 1;
        setOwner(true);
    }

    inline void init(T* array, size_t size = 0, bool owner = true, size_t increment = 1);

    void
    deInit()
    {
        excise();
    }

    void _setAllocSize(size_t allocSize);

    void _autoInit(size_t begin, size_t end);

private:
    enum flg_t
    {
        flg_autoInit,
        flg_owner
    };
};


UTL_NS_END;


UTL_CLASS_IMPL_TPL(utl::Vector, T);


#include <libutl/Stream.h>


UTL_NS_BEGIN;


template <typename T>
Vector<T>::Vector(std::initializer_list<T> list)
{
    init();
    _setAllocSize(list.size());
    for (auto obj : list) append(obj);
}


template <typename T>
Vector<T>::Vector(size_t size, size_t increment)
{
    init(nullptr, size, true, increment);
}


template <typename T>
Vector<T>::Vector(T* array, size_t size, bool owner, size_t increment)
{
    init(array, size, owner, increment);
}


template <typename T>
void
Vector<T>::economize()
{
    ASSERTD(isOwner());
    if (_allocSize > _size)
    {
        auto saveIncrement = _increment;
        _increment = 1;
        _setAllocSize(_size);
        _increment = saveIncrement;
    }
}


template <typename T>
void
Vector<T>::excise()
{
    if (isOwner()) delete[] _array;
    _array = nullptr;
    _size = 0;
    _allocSize = 0;
}


template <typename T>
int
Vector<T>::compare(const Object& rhs) const
{
    auto& v = utl::cast<const Vector<T>>(rhs);
    if (&v == this) return 0;
    return utl::compare(_array, _size, v._array, v._size);
}


template <typename T>
void
Vector<T>::steal(Object& rhs)
{
    auto& v = utl::cast<Vector<T>>(rhs);
    if (_array != nullptr) excise();
    FlagsMI::copyFlags(v);
    _array = v._array;
    _size = v._size;
    _allocSize = v._allocSize;
    _increment = v._increment;
    v._array = nullptr;
    v._size = 0;
    v._allocSize = 0;
}


template <typename T>
void
Vector<T>::copy(const Object& rhs)
{
    auto& v = utl::cast<const Vector<T>>(rhs);
    if (&v == this) return;
    bool lhsOwner = this->isOwner();
    bool rhsOwner = v.isOwner();
    if (lhsOwner && rhsOwner)
    {
        clear();
    }
    else
    {
        excise();
    }
    FlagsMI::copyFlags(v);
    _increment = v._increment;
    if (rhsOwner)
    {
        copy(0, v);
    }
    else
    {
        _array = v._array;
        _size = v._size;
        _allocSize = v._size;
    }
}


template <typename T>
void
Vector<T>::copy(size_t idx, const T* src, size_t srcBegin, size_t srcEnd)
{
    // grow to required size
    grow(idx + (srcEnd - srcBegin));

    // perform the copy
    auto dstPtr = _array + idx;
    auto srcPtr = src + srcBegin;
    auto srcLim = src + srcEnd;
    if (std::is_trivially_copyable<T>())
    {
        memcpy(dstPtr, srcPtr, (srcLim - srcPtr) * sizeof(T));
    }
    else
    {
        while (srcPtr != srcLim) *dstPtr++ = *srcPtr++;
    }
}


template <typename T>
void
Vector<T>::copy(size_t idx, std::initializer_list<T> list)
{
    grow(idx + list.size());
    T* ptr = _array + idx;
    for (auto obj : list) *ptr++ = obj;
}


template <typename T>
void
Vector<T>::move(size_t idx, T* src, size_t srcBegin, size_t srcEnd)
{
    // grow to required size
    grow(idx + (srcEnd - srcBegin));

    // move objects
    auto dstPtr = _array + idx;
    auto srcPtr = src + srcBegin;
    auto srcLim = src + srcEnd;
    if (std::is_trivially_copyable<T>())
    {
        memcpy(dstPtr, srcPtr, (srcLim - srcPtr) * sizeof(T));
    }
    else
    {
        while (srcPtr != srcLim) *dstPtr++ = std::move(*srcPtr++);
    }
}


template <typename T>
void
Vector<T>::serialize(Stream& stream, uint_t io, uint_t mode)
{
    if (io == io_rd)
    {
        clear();
        setOwner(true);
        // increment
        utl::serialize(_increment, stream, io, mode);
        if (_increment == 0) _increment = 1;
        // size
        size_t size;
        utl::serialize(size, stream, io, mode);
        setSize(size);
    }
    else
    {
        // increment
        utl::serialize(_increment, stream, io, mode);
        // size
        utl::serialize(_size, stream, io, mode);
    }

    for (size_t i = 0; i < _size; i++)
    {
        utl::serialize(_array[i], stream, io, mode);
    }
}


template <typename T>
void
Vector<T>::assertOwner()
{
    if (isOwner()) return;

    // set the flag
    setOwner(true);

    // remember _array, _size
    T* oldArray = _array;
    size_t oldSize = _size;

    // _array = null
    _array = nullptr;
    _size = 0;
    _allocSize = 0;

    // grow allocation to the old size, re-set _size
    _setAllocSize(oldSize);
    _size = oldSize;

    // copy from the old array to the new one
    copy(0, oldArray, 0, oldSize);
}


template <typename T>
void
Vector<T>::assertOwner(size_t allocSize)
{
    // we already own the array?
    if (isOwner())
    {
        if (allocSize > _allocSize)
        {
            _setAllocSize(allocSize);
        }
    }
    else
    {
        // set the flag
        setOwner(true);

        // empty sequence?
        if (allocSize == 0)
        {
            // just nuke the array
            _size = 0;
            _allocSize = 0;
            _array = nullptr;
        }
        else
        {
            // remember _array, _size
            T* oldArray = _array;
            size_t oldSize = _size;

            // _array = null
            _array = nullptr;
            _size = 0;
            _allocSize = 0;

            // grow allocation to the new size
            _setAllocSize(allocSize);

            // move as much as we can from the old allocation to the new one
            _size = min(oldSize, allocSize);
            move(0, oldArray, 0, _size);
        }
    }
}


template <typename T>
void
Vector<T>::setSize(size_t size)
{
    if (isOwner() && (size > _allocSize)) _setAllocSize(size);
    if ((size > _size) && autoInit()) _autoInit(_size, size);
    _size = size;
}


template <typename T>
void
Vector<T>::grow(size_t size)
{
    if (size <= _size) return;
    if (size > _allocSize) assertOwner(size);
    if (autoInit()) _autoInit(_size, size);
    _size = size;
}


template <typename T>
void
Vector<T>::append(const T* array, size_t arraySize)
{
    size_t oldSize = _size;
    grow(_size + arraySize);
    if (std::is_trivially_copyable<T>())
    {
        memcpy(_array + oldSize, array, arraySize * sizeof(T));
    }
    else
    {
        T* op = _array + oldSize;
        const T* ip = array;
        T* lim = _array + _size;
        for (; op < lim; ++ip, ++op) *op = *ip;
    }
}


template <typename T>
void
Vector<T>::append(std::initializer_list<T> list)
{
    reserve(_size + list.size());
    for (auto obj : list) append(obj);
}


template <typename T>
void
Vector<T>::insert(size_t idx, size_t num)
{
    // the sequence grows in size by num
    grow(_size + num);

    // shift elements over
    if (std::is_trivially_copyable<T>())
    {
        memmove(_array + idx + num, _array + idx, (_size - idx - num) * sizeof(T));
    }
    else
    {
        T* op = _array + _size - 1;
        T* opLim = _array + idx + num;
        T* ip = op - num;
        for (; op >= opLim; --ip, --op) *op = std::move(*ip);
    }
    if (autoInit()) _autoInit(idx, idx + num);
}


template <typename T>
void
Vector<T>::remove(size_t idx, size_t num)
{
    ASSERTD(_size >= (idx + num));

    // shift elements over
    if (std::is_trivially_copyable<T>())
    {
        memmove(_array + idx, _array + idx + num, (_size - idx - num) * sizeof(T));
    }
    else
    {
        T* op = _array + idx;
        T* opLim = _array + _size - num;
        T* ip = op + num;
        for (; op != opLim; ++ip, ++op) *op = std::move(*ip);
    }

    _size -= num;
}


template <typename T>
void
Vector<T>::relocate(size_t destIdx, size_t srcIdx)
{
    ASSERTD(destIdx <= _size);
    ASSERTD(srcIdx < _size);
    if ((destIdx == srcIdx) || (destIdx == (srcIdx + 1))) return;
    T tmp = _array[srcIdx];
    if (std::is_trivially_copyable<T>())
    {
        if (srcIdx < destIdx)
        {
            // objects in (srcIdx,destIdx) move to the left
            memmove(_array + srcIdx, _array + srcIdx + 1, (destIdx - srcIdx - 1) * sizeof(T));
            _array[destIdx - 1] = tmp;
        }
        else
        {
            // objects in [destIdx,srcIdx) move to the right
            memmove(_array + destIdx + 1, _array + destIdx, (srcIdx - destIdx) * sizeof(T));
            _array[destIdx] = tmp;
        }
    }
    else
    {
        T* destPtr;
        T* srcPtr;
        T* srcLim;
        if (srcIdx < destIdx)
        {
            // objects in (srcIdx,destIdx) move to the left
            destPtr = _array + srcIdx;
            srcPtr = _array + srcIdx + 1;
            srcLim = srcPtr + (destIdx - srcIdx - 1);
            for (; srcPtr != srcLim; ++srcPtr, ++destPtr) *destPtr = std::move(*srcPtr);
            _array[destIdx - 1] = tmp;
        }
        else
        {
            // objects in [destIdx,srcIdx) move to the right
            destPtr = _array + destIdx + 1;
            srcPtr = _array + destIdx;
            srcLim = srcPtr + (srcIdx - destIdx);
            for (; srcPtr != srcLim; ++srcPtr, ++destPtr) *destPtr = std::move(*srcPtr);
            _array[destIdx] = tmp;
        }
    }
}


template <typename T>
void
Vector<T>::reverse(size_t idx, size_t num)
{
    ASSERTD((idx + num) <= _size);
    T* lhs = _array + idx;
    T* rhs = _array + idx + num - 1;
    for (; lhs < rhs; ++lhs, --rhs)
    {
        std::swap(*lhs, *rhs);
    }
}


template <typename T>
void
Vector<T>::set(T* array, size_t size, bool owner, size_t increment)
{
    if (_array != nullptr) clear();
    setOwner(owner);
    _array = array;
    _size = size;
    _allocSize = size;
    _increment = increment;
}


template <typename T>
void
Vector<T>::set(size_t idx, size_t num, const T& val)
{
    T* lim = _array + idx + num;
    for (T* ptr = _array + idx; ptr != lim; ++ptr)
    {
        *ptr = val;
    }
}


template <typename T>
void
Vector<T>::swap(size_t i, size_t j)
{
    ASSERTD(i < _size);
    ASSERTD(j < _size);
    std::swap(_array[i], _array[j]);
}


template <typename T>
void
Vector<T>::swap(size_t i, size_t j, size_t n)
{
    ASSERTD((i + n) <= _size);
    ASSERTD((j + n) <= _size);

    T* lhs = _array + i;
    T* rhs = _array + j;
    T* lhsLim = lhs + n;
    for (; lhs != lhsLim; ++lhs, ++rhs)
    {
        std::swap(*lhs, *rhs);
    }
}


template <typename T>
void
Vector<T>::init(T* array, size_t size, bool owner, size_t increment)
{
    setOwner(owner);
    if ((array == nullptr) && (size > 0))
    {
        ASSERTD(owner);
        _array = nullptr;
        _size = 0;
        _allocSize = 0;
        grow(size, increment);
    }
    else
    {
        _array = array;
        _size = size;
        _allocSize = _size;
        setIncrement(increment);
    }
}


template <typename T>
void
Vector<T>::_setAllocSize(size_t reqAllocSize)
{
    ASSERTD(isOwner());

    // figure out the new allocation size
    size_t allocSize;
    if (_increment == size_t_max)
    {
        // find nearest power of 2
        allocSize = nextPow2(reqAllocSize);
    }
    else
    {
        // find nearest multiple of _increment
        allocSize = nextMultipleOfPow2(_increment, reqAllocSize);
    }
    ASSERTD(allocSize >= reqAllocSize);

    // ensure _size <= requested allocSize
    _size = min(_size, reqAllocSize);

    // create new array
    if (std::is_trivially_copyable<T>())
    {
        _array
            = static_cast<T*>(utl::realloc(_array, _allocSize * sizeof(T), allocSize * sizeof(T)));
    }
    else
    {
        // remember the old allocation, make a new one
        T* oldArray = _array;
        _array = new T[allocSize];

        // move objects to the new array
        T* lhs = _array;
        T* rhs = oldArray;
        T* lhsLim = lhs + _size;
        for (; lhs != lhsLim; ++lhs, ++rhs) *lhs = std::move(*rhs);

        // nuke the old allocation
        delete[] oldArray;
    }

    // re-set allocSize
    _allocSize = allocSize;
}


template <typename T>
void
Vector<T>::_autoInit(size_t begin, size_t end)
{
    auto ptr = _array + begin;
    auto lim = _array + end;
    for (; ptr != lim; ++ptr) *ptr = T();
}


UTL_NS_END;