flex_vector.hpp

#pragma once

#include <cstddef>
#include <limits>
#include <new>
#include <stdexcept>
#include <type_traits>
#include <utility>

namespace ext {

template <typename T>
class FlexVectorIterator {
public:
    FlexVectorIterator(T* data, std::size_t l, std::size_t r, std::size_t cap, std::size_t index)
        : data_(data),
          l_(l),
          r_(r),
          cap_(cap),
          index_(index) {}

    T& operator*() const {
        return data_[to_physical_index(index_)];
    }

    FlexVectorIterator& operator++() {
        index_++;
        return *this;
    }

    FlexVectorIterator operator++(int) {
        FlexVectorIterator tmp = *this;
        index_++;
        return tmp;
    }

    T* operator->() const {
        return data_ + to_physical_index(index_);
    }

    bool operator==(const FlexVectorIterator& other) const {
        return data_ == other.data_ && index_ == other.index_;
    }

    bool operator!=(const FlexVectorIterator& other) const {
        return !(*this == other);
    }

private:
    T* data_;
    std::size_t l_;
    std::size_t r_;
    std::size_t cap_;
    std::size_t index_;

    std::size_t to_physical_index(std::size_t index) const {
        if (index < l_) {
            return cap_ - l_ + index;
        }
        if (index < l_ + r_) {
            return index - l_;
        }
        throw std::out_of_range("FlexVectorIterator::to_physical_index");
    }
};

template <typename T>
class FlexVector {
public:
    FlexVector()
        : arr_(static_cast<T*>(::operator new(sizeof(T)))),
          l_(0),
          r_(0),
          cap_(1) {}

    ~FlexVector() {
        destroy_all();
        ::operator delete(arr_);
    }

    FlexVector(const FlexVector& other)
        : arr_(other.cap_ == 0
                   ? nullptr
                   : static_cast<T*>(::operator new(sizeof(T) * other.cap_))),
          l_(other.l_),
          r_(other.r_),
          cap_(other.cap_) {
        std::size_t constructed_r = 0;
        std::size_t constructed_l = 0;

        try {
            for (; constructed_r < r_; ++constructed_r) {
                new (arr_ + constructed_r) T(other.arr_[constructed_r]);
            }

            for (; constructed_l < l_; ++constructed_l) {
                const std::size_t offset = constructed_l + 1;
                new (arr_ + cap_ - offset) T(other.arr_[other.cap_ - offset]);
            }
        } catch (...) {
            for (std::size_t i = 0; i < constructed_r; ++i) {
                arr_[i].~T();
            }

            for (std::size_t i = 1; i <= constructed_l; ++i) {
                arr_[cap_ - i].~T();
            }

            ::operator delete(arr_);
            throw;
        }
    }

    FlexVector& operator=(const FlexVector& other) {
        if (this == &other) {
            return *this;
        }

        FlexVector tmp(other);
        swap(tmp);
        return *this;
    }

    FlexVector(FlexVector&& other) noexcept
        : arr_(std::exchange(other.arr_, nullptr)),
          l_(std::exchange(other.l_, 0)),
          r_(std::exchange(other.r_, 0)),
          cap_(std::exchange(other.cap_, 0)) {}

    FlexVector& operator=(FlexVector&& other) noexcept {
        if (this == &other) {
            return *this;
        }

        destroy_all();
        ::operator delete(arr_);

        arr_ = std::exchange(other.arr_, nullptr);
        l_ = std::exchange(other.l_, 0);
        r_ = std::exchange(other.r_, 0);
        cap_ = std::exchange(other.cap_, 0);

        return *this;
    }

    void push_back(const T& val) {
        emplace_back(val);
    }

    void push_back(T&& val) {
        emplace_back(std::move(val));
    }

    template <typename... Args>
    T& emplace_back(Args&&... args) {
        if (size() == cap_) {
            grow();
        }

        T* ptr = new (arr_ + r_) T(std::forward<Args>(args)...);
        ++r_;
        return *ptr;
    }

    void push_front(const T& val) {
        emplace_front(val);
    }

    void push_front(T&& val) {
        emplace_front(std::move(val));
    }

    template <typename... Args>
    T& emplace_front(Args&&... args) {
        if (size() == cap_) {
            grow();
        }

        T* ptr = new (arr_ + cap_ - l_ - 1) T(std::forward<Args>(args)...);
        ++l_;
        return *ptr;
    }

    std::size_t size() const noexcept {
        return l_ + r_;
    }

    bool empty() const noexcept {
        return size() == 0;
    }

    std::size_t capacity() const noexcept {
        return cap_;
    }

    std::pair<std::ptrdiff_t, std::ptrdiff_t> range() const {
        if (l_ > max_index_size() || r_ > max_index_size()) {
            throw std::overflow_error("FlexVector::range");
        }

        return {
            -static_cast<std::ptrdiff_t>(l_),
            static_cast<std::ptrdiff_t>(r_)
        };
    }

    T& operator[](std::ptrdiff_t index) {
        return arr_[physical_index_unchecked(index)];
    }

    const T& operator[](std::ptrdiff_t index) const {
        return arr_[physical_index_unchecked(index)];
    }

    T& at(std::ptrdiff_t index) {
        return arr_[physical_index_checked(index)];
    }

    const T& at(std::ptrdiff_t index) const {
        return arr_[physical_index_checked(index)];
    }

    void swap(FlexVector& other) noexcept {
        if (this == &other) {
            return;
        }

        using std::swap;
        swap(arr_, other.arr_);
        swap(l_, other.l_);
        swap(r_, other.r_);
        swap(cap_, other.cap_);
    }

    FlexVectorIterator<T> begin() {
        return FlexVectorIterator<T>(arr_, l_, r_, cap_, 0);
    }

    FlexVectorIterator<T> end() {
        return FlexVectorIterator<T>(arr_, l_, r_, cap_, size());
    }

private:
    T* arr_;
    std::size_t l_;
    std::size_t r_;
    std::size_t cap_;

    static constexpr std::size_t max_index_size() noexcept {
        return static_cast<std::size_t>(
            std::numeric_limits<std::ptrdiff_t>::max()
        );
    }

    std::size_t physical_index_unchecked(std::ptrdiff_t index) const noexcept {
        if (index >= 0) {
            return static_cast<std::size_t>(index);
        }

        return cap_ - static_cast<std::size_t>(-index);
    }

    std::size_t physical_index_checked(std::ptrdiff_t index) const {
        if (index >= 0) {
            const auto i = static_cast<std::size_t>(index);
            if (i >= r_) {
                throw std::out_of_range("FlexVector::at");
            }
            return i;
        }

        if (index == std::numeric_limits<std::ptrdiff_t>::min()) {
            throw std::out_of_range("FlexVector::at");
        }

        const auto neg = static_cast<std::size_t>(-index);
        if (neg > l_) {
            throw std::out_of_range("FlexVector::at");
        }

        return cap_ - neg;
    }

    void grow() {
        if (cap_ > static_cast<std::size_t>(-1) / 2) {
            throw std::length_error("FlexVector::grow capacity overflow");
        }

        const std::size_t new_cap = (cap_ == 0) ? 1 : (cap_ * 2);
        T* new_arr = static_cast<T*>(::operator new(sizeof(T) * new_cap));

        std::size_t constructed_r = 0;
        std::size_t constructed_l = 0;

        try {
            for (; constructed_r < r_; ++constructed_r) {
                relocate_construct(new_arr + constructed_r, arr_ + constructed_r);
            }

            for (; constructed_l < l_; ++constructed_l) {
                const std::size_t old_idx = cap_ - 1 - constructed_l;
                const std::size_t new_idx = new_cap - 1 - constructed_l;

                relocate_construct(new_arr + new_idx, arr_ + old_idx);
            }
        } catch (...) {
            for (std::size_t i = 0; i < constructed_r; ++i) {
                new_arr[i].~T();
            }

            for (std::size_t i = 0; i < constructed_l; ++i) {
                new_arr[new_cap - 1 - i].~T();
            }

            ::operator delete(new_arr);
            throw;
        }

        destroy_all();
        ::operator delete(arr_);

        arr_ = new_arr;
        cap_ = new_cap;
    }

    static void relocate_construct(T* dst, T* src) {
        if constexpr (std::is_nothrow_move_constructible_v<T> ||
                      !std::is_copy_constructible_v<T>) {
            new (dst) T(std::move(*src));
        } else {
            new (dst) T(*src);
        }
    }

    void destroy_all() noexcept {
        for (std::size_t i = 0; i < r_; ++i) {
            arr_[i].~T();
        }

        for (std::size_t i = 1; i <= l_; ++i) {
            arr_[cap_ - i].~T();
        }
    }
};

template <typename T>
void swap(FlexVector<T>& a, FlexVector<T>& b) noexcept {
    a.swap(b);
}

} // namespace ext