vector.h

Go to the documentation of this file.

#ifndef VECTOR_H
#define VECTOR_H
 
#include "baseList.h"
#include "iterationStream.h"
#include "array.h"
 
namespace original {
 
    template <typename TYPE, typename ALLOC = allocator<TYPE>>
    class vector final : public baseList<TYPE, ALLOC>, public iterationStream<TYPE, vector<TYPE, ALLOC>> {
        u_integer size_;                 
        static constexpr u_integer INNER_SIZE_INIT = 16; 
        u_integer max_size;              
        u_integer inner_begin;           
        TYPE* body;                     
 
        // ==================== Private Methods ====================
 
        void vectorInit();
 
        void vectorArrayDestroy() noexcept;
 
        TYPE* vectorArrayInit(u_integer size);
 
        TYPE getElem(integer pos) const;
 
        void setElem(integer pos, const TYPE &e);
 
        static void setBufElem(TYPE* buf, integer pos, const TYPE& e);
 
        static void moveElements(TYPE* old_body, u_integer inner_idx,
                                 u_integer len, TYPE* new_body, integer offset);
 
        [[nodiscard]] u_integer toInnerIdx(integer index) const;
 
        [[nodiscard]] bool outOfMaxSize(u_integer increment) const;
 
        void grow(u_integer new_size);
 
        void adjust(u_integer increment);
 
        explicit vector(u_integer size, ALLOC alloc = ALLOC{});
 
    public:
 
        // ==================== Iterator Class ====================
 
        class Iterator final : public randomAccessIterator<TYPE, ALLOC> {
            explicit Iterator(TYPE* ptr, const vector* container, integer pos);
 
        public:
            friend vector;
 
            Iterator(const Iterator& other);
 
            Iterator& operator=(const Iterator& other);
 
            Iterator* clone() const override;
 
            bool atPrev(const iterator<TYPE> *other) const override;
 
            bool atNext(const iterator<TYPE> *other) const override;
 
            [[nodiscard]] std::string className() const override;
        };
 
        // ==================== Constructors and Destructor ====================
 
        explicit vector(ALLOC alloc = ALLOC{});
 
        template<typename... ARGS>
        vector(u_integer size, ALLOC alloc, ARGS&&... args);
 
        vector(const vector& other);
 
        vector(const std::initializer_list<TYPE>& list);
 
        explicit vector(const array<TYPE>& arr);
 
        vector& operator=(const vector& other);
 
        vector(vector&& other) noexcept;
 
        vector& operator=(vector&& other) noexcept;
 
        ~vector() override;
 
        // ==================== Capacity Methods ====================
 
        [[nodiscard]] u_integer size() const override;
 
        [[nodiscard]] u_integer capacity() const noexcept;
 
        // ==================== Element Access ====================
 
        TYPE& data() const;
 
        TYPE get(integer index) const override;
 
        TYPE& operator[](integer index) override;
 
        // const version
        using serial<TYPE, ALLOC>::operator[];
 
        void set(integer index, const TYPE &e) override;
 
        // ==================== Search Operations ====================
 
        u_integer indexOf(const TYPE &e) const override;
 
        // ==================== Insertion Operations ====================
 
        void pushBegin(const TYPE &e) override;
 
        void push(integer index, const TYPE &e) override;
 
        void pushEnd(const TYPE &e) override;
 
        // ==================== Removal Operations ====================
 
        TYPE popBegin() override;
 
        TYPE pop(integer index) override;
 
        TYPE popEnd() override;
 
        // ==================== Iterator Methods ====================
 
        Iterator* begins() const override;
 
        Iterator* ends() const override;
 
        // ==================== Utility Methods ====================
 
        [[nodiscard]] std::string className() const override;
 
        template<typename T, typename... ARGS>
        friend vector<T> makeVector(u_integer size, ARGS&&... args);
    };
 
    // ==================== Factory Function ====================
 
    template<typename T, typename... ARGS>
    vector<T> makeVector(u_integer size, ARGS&&... args);
}
 
    template <typename TYPE, typename ALLOC>
    auto original::vector<TYPE, ALLOC>::vectorInit() -> void
    {
        this->size_ = 0;
        this->max_size = INNER_SIZE_INIT;
        this->inner_begin = (INNER_SIZE_INIT - 1)/2;
        this->body = vector::vectorArrayInit(INNER_SIZE_INIT);
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::vector<TYPE, ALLOC>::vectorArrayDestroy() noexcept -> void
    {
        if (this->body) {
            for (u_integer i = 0; i < this->max_size; ++i) {
                this->destroy(&this->body[i]);
            }
            this->deallocate(this->body, this->max_size);
            this->body = nullptr;
        }
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::vector<TYPE, ALLOC>::vectorArrayInit(const u_integer size) -> TYPE* {
        auto arr = this->allocate(size);
        for (u_integer i = 0; i < size; i++) {
            this->construct(&arr[i]);
        }
        return arr;
    }
 
    template <typename TYPE, typename ALLOC>
    TYPE original::vector<TYPE, ALLOC>::getElem(integer pos) const
    {
        if constexpr (std::is_copy_constructible_v<TYPE>) {
            return this->body[pos];
        } else if constexpr (std::is_move_constructible_v<TYPE>) {
            return std::move(this->body[pos]);
        } else {
            staticError<unSupportedMethodError, !std::is_copy_constructible_v<TYPE> && !std::is_move_constructible_v<TYPE>>::asserts();
            return TYPE{};
        }
    }
 
    template <typename TYPE, typename ALLOC>
    void original::vector<TYPE, ALLOC>::setElem(const integer pos, const TYPE& e)
    {
        setBufElem(this->body, pos, e);
    }
 
    template <typename TYPE, typename ALLOC>
    void original::vector<TYPE, ALLOC>::setBufElem(TYPE* buf, integer pos, const TYPE& e)
    {
        if constexpr (std::is_copy_assignable_v<TYPE>) {
            buf[pos] = e;
        } else if constexpr (std::is_move_assignable_v<TYPE>) {
            buf[pos] = std::move(const_cast<TYPE&>(e));
        } else {
            staticError<unSupportedMethodError, !std::is_copy_constructible_v<TYPE> && !std::is_move_constructible_v<TYPE>>::asserts();
        }
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::vector<TYPE, ALLOC>::moveElements(TYPE* old_body, const u_integer inner_idx,
                                              const u_integer len, TYPE* new_body, const integer offset) -> void{
        if (offset > 0)
        {
            for (u_integer i = 0; i < len; i += 1)
            {
                setBufElem(new_body, inner_idx + offset + len - 1 - i, old_body[inner_idx + len - 1 - i]);
            }
        }else
        {
            for (u_integer i = 0; i < len; i += 1)
            {
                setBufElem(new_body, inner_idx + offset + i, old_body[inner_idx + i]);
            }
        }
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::vector<TYPE, ALLOC>::toInnerIdx(integer index) const -> u_integer
    {
        return this->inner_begin + index;
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::vector<TYPE, ALLOC>::outOfMaxSize(u_integer increment) const -> bool
    {
        return this->inner_begin + this->size() + increment > this->max_size - 1 || static_cast<integer>(this->inner_begin) - static_cast<integer>(increment) < 0;
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::vector<TYPE, ALLOC>::grow(const u_integer new_size) -> void
    {
        TYPE* new_body = vector::vectorArrayInit(new_size);
        u_integer new_begin = (new_size - 1) / 4;
        const integer offset = static_cast<integer>(new_begin) - static_cast<integer>(this->inner_begin);
        vector::moveElements(this->body, this->inner_begin,
                             this->size(), new_body, offset);
        this->vectorArrayDestroy();
        this->body = new_body;
        this->max_size = new_size;
        this->inner_begin = new_begin;
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::vector<TYPE, ALLOC>::adjust(u_integer increment) -> void {
        if (!this->outOfMaxSize(increment)) {
            return;
        }
        u_integer new_begin = (this->max_size - this->size() - increment) / 2;
        if (this->max_size >= this->size_ + increment && new_begin > 0) {
            const integer offset = static_cast<integer>(new_begin) - static_cast<integer>(this->inner_begin);
            vector::moveElements(this->body, this->inner_begin, this->size(),
                                 this->body, offset);
            this->inner_begin = new_begin;
        } else {
            const u_integer new_max_size = (this->size() + increment) * 2;
            this->grow(new_max_size);
        }
    }
 
    template <typename TYPE, typename ALLOC>
    original::vector<TYPE, ALLOC>::Iterator::Iterator(TYPE* ptr, const vector* container, integer pos)
        : randomAccessIterator<TYPE, ALLOC>(ptr, container, pos) {}
 
    template <typename TYPE, typename ALLOC>
    original::vector<TYPE, ALLOC>::Iterator::Iterator(const Iterator& other)
        : randomAccessIterator<TYPE, ALLOC>(nullptr, nullptr, 0)
    {
        this->operator=(other);
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::vector<TYPE, ALLOC>::Iterator::operator=(const Iterator& other) -> Iterator&
    {
        if (this == &other) {
            return *this;
        }
        randomAccessIterator<TYPE, ALLOC>::operator=(other);
        return *this;
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::vector<TYPE, ALLOC>::Iterator::clone() const -> Iterator* {
        return new Iterator(*this);
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::vector<TYPE, ALLOC>::Iterator::atPrev(const iterator<TYPE> *other) const -> bool {
        auto other_it = dynamic_cast<const Iterator*>(other);
        return this->_ptr + 1 == other_it->_ptr;
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::vector<TYPE, ALLOC>::Iterator::atNext(const iterator<TYPE> *other) const -> bool {
        auto other_it = dynamic_cast<const Iterator*>(other);
        return other_it->_ptr + 1 == this->_ptr;
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::vector<TYPE, ALLOC>::Iterator::className() const -> std::string {
        return "vector::Iterator";
    }
 
    template <typename TYPE, typename ALLOC>
    original::vector<TYPE, ALLOC>::vector(ALLOC alloc)
        : baseList<TYPE, ALLOC>(std::move(alloc)), size_(), max_size(), inner_begin()
    {
        this->vectorInit();
    }
 
template<typename TYPE, typename ALLOC>
template<typename... ARGS>
original::vector<TYPE, ALLOC>::vector(u_integer size, ALLOC alloc, ARGS&&... args)
    : vector(size, std::move(alloc)) {
    this->body = this->allocate(this->max_size);
    for (u_integer i = 0; i < this->size_; ++i) {
        this->construct(&this->body[this->toInnerIdx(i)], std::forward<ARGS>(args)...);
    }
}
 
template<typename TYPE, typename ALLOC>
    original::vector<TYPE, ALLOC>::vector(const u_integer size, ALLOC alloc)
    : baseList<TYPE, ALLOC>(std::move(alloc)), size_(size),
      max_size(size * 4 / 3), inner_begin(size / 3 >= 1 ? size / 3 - 1 : 0), body(nullptr) {
}
 
    template <typename TYPE, typename ALLOC>
    original::vector<TYPE, ALLOC>::vector(const vector& other) : vector(){
        this->operator=(other);
    }
 
    template <typename TYPE, typename ALLOC>
    original::vector<TYPE, ALLOC>::vector(const std::initializer_list<TYPE>& list) : vector()
    {
        this->adjust(list.size());
        for (const TYPE& e: list)
        {
            this->body[this->inner_begin + this->size()] = e;
            this->size_ += 1;
        }
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::vector<TYPE, ALLOC>::operator=(const vector& other) -> vector&
    {
        if (this == &other)
            return *this;
 
        this->vectorArrayDestroy();
 
        this->max_size = other.max_size;
        this->inner_begin = other.inner_begin;
        this->size_ = other.size_;
        this->body = vector::vectorArrayInit(this->max_size);
        for (u_integer i = 0; i < this->size(); ++i) {
            const TYPE& data = other.body[this->toInnerIdx(i)];
            this->body[this->toInnerIdx(i)] = data;
        }
        if constexpr (ALLOC::propagate_on_container_copy_assignment::value){
            this->allocator = other.allocator;
        }
        return *this;
    }
 
    template <typename TYPE, typename ALLOC>
    original::vector<TYPE, ALLOC>::vector(vector&& other) noexcept : vector()
    {
        this->operator=(std::move(other));
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::vector<TYPE, ALLOC>::operator=(vector&& other) noexcept -> vector&
    {
        if (this == &other)
            return *this;
 
        this->vectorArrayDestroy();
        this->body = other.body;
        other.body = nullptr;
        this->max_size = other.max_size;
        this->inner_begin = other.inner_begin;
        this->size_ = other.size_;
        if constexpr (ALLOC::propagate_on_container_move_assignment::value){
            this->allocator = std::move(other.allocator);
        }
        other.vectorInit();
        return *this;
    }
 
    template <typename TYPE, typename ALLOC>
    original::vector<TYPE, ALLOC>::vector(const array<TYPE>& arr) : vector()
    {
        this->adjust(arr.size());
        for (u_integer i = 0; i < arr.size(); i += 1)
        {
            this->body[this->toInnerIdx(i)] = arr.get(i);
            this->size_ += 1;
        }
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::vector<TYPE, ALLOC>::size() const -> u_integer
    {
        return this->size_;
    }
 
    template <typename TYPE, typename ALLOC>
    original::u_integer original::vector<TYPE, ALLOC>::capacity() const noexcept
    {
        return this->max_size;
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::vector<TYPE, ALLOC>::data() const -> TYPE& {
        return this->body[this->toInnerIdx(0)];
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::vector<TYPE, ALLOC>::get(integer index) const -> TYPE
    {
        if (this->indexOutOfBound(index))
        {
            throw outOfBoundError("Index " + std::to_string(this->parseNegIndex(index)) +
                                  " out of bound max index " + std::to_string(this->size() - 1) + ".");
        }
        index = this->toInnerIdx(this->parseNegIndex(index));
        return this->getElem(index);
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::vector<TYPE, ALLOC>::operator[](integer index) -> TYPE&
    {
        if (this->indexOutOfBound(index))
        {
            throw outOfBoundError("Index " + std::to_string(this->parseNegIndex(index)) +
                                  " out of bound max index " + std::to_string(this->size() - 1) + ".");
        }
        index = this->toInnerIdx(this->parseNegIndex(index));
        return this->body[index];
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::vector<TYPE, ALLOC>::set(integer index, const TYPE &e) -> void
    {
        if (this->indexOutOfBound(index))
        {
            throw outOfBoundError("Index " + std::to_string(this->parseNegIndex(index)) +
                                  " out of bound max index " + std::to_string(this->size() - 1) + ".");
        }
        index = this->toInnerIdx(this->parseNegIndex(index));
        this->setElem(index, e);
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::vector<TYPE, ALLOC>::indexOf(const TYPE &e) const -> u_integer
    {
        if constexpr (Comparable<TYPE>) {
            for (u_integer i = 0; i < this->size(); i += 1)
            {
                if (this->get(i) == e)
                {
                    return i;
                }
            }
            return this->size();
        } else {
            throw unSupportedMethodError("Comparison unsupported type");
        }
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::vector<TYPE, ALLOC>::pushBegin(const TYPE &e) -> void
    {
        this->adjust(1);
        this->inner_begin -= 1;
        this->setElem(this->toInnerIdx(0), e);
        this->size_ += 1;
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::vector<TYPE, ALLOC>::push(integer index, const TYPE &e) -> void
    {
        if (this->parseNegIndex(index) == this->size())
        {
            this->pushEnd(e);
        }else if (this->parseNegIndex(index) == 0)
        {
            this->pushBegin(e);
        }else
        {
            if (this->indexOutOfBound(index))
            {
                throw outOfBoundError("Index " + std::to_string(this->parseNegIndex(index)) +
                                      " out of bound max index " + std::to_string(this->size() - 1) + ".");
            }
            this->adjust(1);
            index = this->toInnerIdx(this->parseNegIndex(index));
            u_integer rel_idx = index - this->inner_begin;
            if (index - this->inner_begin <= (this->size() - 1) / 2)
            {
                vector::moveElements(this->body, this->inner_begin,
                                     rel_idx + 1, this->body, -1);
                this->inner_begin -= 1;
            }else
            {
                vector::moveElements(this->body, index,
                                     this->size() - rel_idx, this->body, 1);
            }
            this->setElem(this->toInnerIdx(rel_idx), e);
            this->size_ += 1;
        }
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::vector<TYPE, ALLOC>::pushEnd(const TYPE &e) -> void
    {
        this->adjust(1);
        this->setElem(this->toInnerIdx(this->size()), e);
        this->size_ += 1;
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::vector<TYPE, ALLOC>::popBegin() -> TYPE
    {
        if (this->size() == 0){
            throw noElementError();
        }
        TYPE res = this->get(0);
        this->inner_begin += 1;
        this->size_ -= 1;
        return res;
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::vector<TYPE, ALLOC>::pop(integer index) -> TYPE
    {
        if (this->parseNegIndex(index) == 0)
        {
            return this->popBegin();
        }
        if (this->parseNegIndex(index) == this->size() - 1)
        {
            return this->popEnd();
        }
        if (this->indexOutOfBound(index)){
            throw outOfBoundError("Index " + std::to_string(this->parseNegIndex(index)) +
                                  " out of bound max index " + std::to_string(this->size() - 1) + ".");
        }
        TYPE res = this->get(index);
        index = this->toInnerIdx(this->parseNegIndex(index));
        u_integer rel_idx = index - this->inner_begin;
        if (index - this->inner_begin <= (this->size() - 1) / 2)
        {
            vector::moveElements(this->body, this->inner_begin,
                                 rel_idx, this->body, 1);
            this->inner_begin += 1;
        }else
        {
            vector::moveElements(this->body, index + 1,
                                 this->size() - 1 - rel_idx, this->body, -1);
        }
        this->size_ -= 1;
        return res;
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::vector<TYPE, ALLOC>::popEnd() -> TYPE
    {
        if (this->size() == 0){
            throw noElementError();
        }
        TYPE res = this->get(this->size() - 1);
        this->size_ -= 1;
        return res;
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::vector<TYPE, ALLOC>::begins() const -> Iterator* {
        return new Iterator(&this->body[this->toInnerIdx(0)], this, 0);
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::vector<TYPE, ALLOC>::ends() const -> Iterator* {
        return new Iterator(&this->body[this->toInnerIdx(this->size() - 1)], this, this->size() - 1);
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::vector<TYPE, ALLOC>::className() const -> std::string
    {
        return "vector";
    }
 
    template <typename TYPE, typename ALLOC>
    original::vector<TYPE, ALLOC>::~vector() {
        this->vectorArrayDestroy();
    }
 
    template<typename T, typename... ARGS>
    original::vector<T> original::makeVector(u_integer size, ARGS &&... args) {
        return original::vector<T>(size, original::allocator<T>{}, std::forward<ARGS>(args)...);
    }
 
#endif //VECTOR_H