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_;                 
        const u_integer INNER_SIZE_INIT = 16; 
        u_integer max_size;              
        u_integer inner_begin;           
        TYPE* body;                     

        void vectorInit();

        void vectorArrayDestruct() noexcept;

        TYPE* vectorArrayInit(u_integer size);

        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:
        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;
        };

        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;

        [[nodiscard]] u_integer size() const override;

        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;

        u_integer indexOf(const TYPE &e) const override;

        void pushBegin(const TYPE &e) override;

        void push(integer index, const TYPE &e) override;

        void pushEnd(const TYPE &e) override;

        TYPE popBegin() override;

        TYPE pop(integer index) override;

        TYPE popEnd() override;

        Iterator* begins() const override;

        Iterator* ends() const override;

        [[nodiscard]] std::string className() const override;

        ~vector() override;
 
        template<typename T, typename... ARGS>
        friend vector<T> makeVector(u_integer size, ARGS&&... args);
    };

    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 = this->INNER_SIZE_INIT;
        this->inner_begin = (this->INNER_SIZE_INIT - 1)/2;
        this->body = vector::vectorArrayInit(this->INNER_SIZE_INIT);
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::vector<TYPE, ALLOC>::vectorArrayDestruct() 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>
    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)
            {
                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)
            {
                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->vectorArrayDestruct();
        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->vectorArrayDestruct();
 
        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->vectorArrayDestruct();
        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>
    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 = this->toInnerIdx(this->parseNegIndex(index));
        return this->body[index];
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::vector<TYPE, ALLOC>::operator[](integer index) -> TYPE&
    {
        if (this->indexOutOfBound(index))
        {
            throw outOfBoundError();
        }
        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 = this->toInnerIdx(this->parseNegIndex(index));
        this->body[index] = e;
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::vector<TYPE, ALLOC>::indexOf(const TYPE &e) const -> u_integer
    {
        for (u_integer i = 0; i < this->size(); i += 1)
        {
            if (this->get(i) == e)
            {
                return i;
            }
        }
        return this->size();
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::vector<TYPE, ALLOC>::pushBegin(const TYPE &e) -> void
    {
        this->adjust(1);
        this->inner_begin -= 1;
        this->body[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();
            }
            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->body[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->body[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();
        }
        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->vectorArrayDestruct();
    }
 
    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