vlist

vlist.h

#ifndef VLIST_H
#define VLIST_H

#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <iterator>
#include <memory>
#include <utility>
#include <vector>

namespace vlist_ns {

using default_index_type = std::int32_t;

template<typename I>
inline constexpr I null_index = static_cast<I>(-1);

template<typename T, typename I>
struct node {
    T value;
    I next = null_index<I>;
    I prev = null_index<I>;

    template<typename... Args>
    explicit node(Args&&... args)
        : value{std::forward<Args>(args)...}
    {}
};

template<typename T, typename I>
class vlist_const_iterator {
public:
    using iterator = vlist_const_iterator<T, I>;
    using value_type = T;
    using reference = const T&;
    using pointer = const T*;
    using difference_type = std::ptrdiff_t;
    using iterator_category = std::forward_iterator_tag;

    vlist_const_iterator() = default;

    vlist_const_iterator(const node<T, I>* ptr, I idx)
        : ptr_(ptr), idx_(idx)
    {}

    vlist_const_iterator(const vlist_const_iterator&) = default;
    vlist_const_iterator(vlist_const_iterator&&) noexcept = default;
    vlist_const_iterator& operator=(const vlist_const_iterator&) = default;
    vlist_const_iterator& operator=(vlist_const_iterator&&) noexcept = default;

    reference operator*() const {
        return this->ptr_[static_cast<std::size_t>(this->idx_)].value;
    }

    pointer operator->() const {
        return &this->ptr_[static_cast<std::size_t>(this->idx_)].value;
    }

    iterator& operator++() {
        this->idx_ = this->ptr_[static_cast<std::size_t>(this->idx_)].next;
        return *this;
    }

    iterator operator++(int) {
        auto it = *this;
        ++(*this);
        return it;
    }

    bool operator==(const iterator& rhs) const {
        return this->idx_ == rhs.idx_;
    }

    bool operator!=(const iterator& rhs) const {
        return !(*this == rhs);
    }

private:
    const node<T, I>* ptr_ = nullptr;
    I idx_ = null_index<I>;

    template<typename, typename, typename> friend class vlist;
};

template<typename T, typename I>
class vlist_iterator {
public:
    using iterator = vlist_iterator<T, I>;
    using value_type = T;
    using reference = T&;
    using pointer = T*;
    using difference_type = std::ptrdiff_t;
    using iterator_category = std::forward_iterator_tag;

    vlist_iterator() = default;

    vlist_iterator(node<T, I>* ptr, I idx)
        : ptr_(ptr), idx_(idx)
    {}

    vlist_iterator(const vlist_iterator&) = default;
    vlist_iterator(vlist_iterator&&) noexcept = default;
    vlist_iterator& operator=(const vlist_iterator&) = default;
    vlist_iterator& operator=(vlist_iterator&&) noexcept = default;

    reference operator*() {
        return this->ptr_[static_cast<std::size_t>(this->idx_)].value;
    }

    pointer operator->() {
        return &this->ptr_[static_cast<std::size_t>(this->idx_)].value;
    }

    iterator& operator++() {
        this->idx_ = this->ptr_[static_cast<std::size_t>(this->idx_)].next;
        return *this;
    }

    iterator operator++(int) {
        auto it = *this;
        ++(*this);
        return it;
    }

    bool operator==(const iterator& rhs) const {
        return this->idx_ == rhs.idx_;
    }

    bool operator!=(const iterator& rhs) const {
        return !(*this == rhs);
    }

    operator vlist_const_iterator<T, I>() const {
        // to allow conversion from mutable to const iterator
        return {this->ptr_, this->idx_};
    }

private:
    node<T, I>* ptr_ = nullptr;
    I idx_ = null_index<I>;

    template<typename, typename, typename> friend class vlist;
};

template<
    typename T,
    typename I = default_index_type,
    typename A = std::allocator<node<T, I>>
>
class vlist {
    static constexpr I null = null_index<I>;

public:
    using value_type = T;
    using index_type = I;
    using allocator_type = A;
    using node_type = node<T, I>;
    using iterator = vlist_iterator<T, I>;
    using const_iterator = vlist_const_iterator<T, I>;

    vlist() = default;

    explicit vlist(std::size_t reserve, allocator_type alloc = {})
        : nodes_(alloc)
    {
        this->nodes_.reserve(reserve);
    }

    explicit vlist(allocator_type alloc)
        : vlist(0, alloc)
    {}

    vlist(const vlist&) = default;
    vlist(vlist&&) noexcept = default;
    vlist& operator=(const vlist&) = default;
    vlist& operator=(vlist&&) noexcept = default;

    void clear() noexcept {
        this->nodes_.clear();
        this->size_ = 0;
        this->first_ = null;
    }

    std::size_t size() const noexcept {
        return this->size_;
    }

    bool empty() const noexcept {
        return this->size_ == 0;
    }

    template<typename... Args>
    iterator emplace(const_iterator pos, Args&&... args) {
        return this->emplace_(pos, std::forward<Args>(args)...);
    }

    iterator erase(iterator pos) {
        return this->erase_(pos);
    }

    iterator erase(const_iterator pos) {
        return this->erase_(pos);
    }

    iterator begin() {
        return {this->nodes_.data(), this->first_};
    }

    iterator end() {
        return {};
    }

    iterator begin() const {
        return {this->nodes_.data(), this->first_};
    }

    iterator end() const {
        return {};
    }

    const_iterator cbegin() const {
        return {this->nodes_.data(), this->first_};
    }

    const_iterator cend() const {
        return {};
    }

    template<typename A_, typename I_>
    bool operator==(const vlist<T, I_, A_>& rhs) const {
        return (
            this->size() == rhs.size()
            && std::equal(this->cbegin(), this->cend(), rhs.cbegin())
        );
    }

    template<typename A_, typename I_>
    bool operator!=(const vlist<T, I_, A_>& rhs) const {
        return !(*this == rhs);
    }

public:
    std::vector<node_type, allocator_type> nodes_;
    I first_ = null;
    I last_ = null;
    std::size_t size_ = 0;

    node_type& at(index_type idx) {
        return this->nodes_[static_cast<std::size_t>(idx)];
    }

    const node_type& at(index_type idx) const {
        return this->nodes_[static_cast<std::size_t>(idx)];
    }

    template<typename P, typename... Args>
    iterator emplace_(P pos, Args&&... args) {
        auto size = static_cast<index_type>(this->size());

        node_type node{std::forward<Args>(args)...};
        node.next = pos.idx_;

        auto& prev = pos.idx_ == null ? this->last_ : this->at(pos.idx_).prev;
        node.prev = prev;
        if (prev == null) {
            this->first_ = size;
        } else {
            this->at(prev).next = size;
        }
        prev = size;

        this->nodes_.emplace_back(std::move(node));

        ++this->size_;
        return {this->nodes_.data(), size};
    }


    template<typename P>
    iterator erase_(P pos) {
        if (pos.idx_ != null) {
            auto &node = this->at(pos.idx_);
            if (node.prev != null) {
                this->at(node.prev).next = node.next;
            } else {
                this->first_ = node.next;
            }
            if (node.next != null) {
                this->at(node.next).prev = node.prev;
            } else {
                this->last_ = node.prev;
            }
            node.prev = null;
            node.next = null;
            --this->size_;
            if (this->size_ == 0) {
                this->nodes_.clear();
            }
            return {this->nodes_.data(), node.next};
        } else {
            return this->begin();
        }
    }
};

}  // namespace vlist_ns

using vlist_ns::vlist;

#endif  // VLIST_H