linked_vector.hpp

Go to the documentation of this file.

 
#ifndef __BOXES_LINKED_VECTOR_HPP__
#define __BOXES_LINKED_VECTOR_HPP__
 
#include "compiler.hpp"
#include "ring_buffer.hpp"
 
#include <list>
#include <memory>
#include <stdexcept>
 
namespace boxes {
 
template <typename T, std::size_t ChunkSizeV> class LinkedVector {
public:
  using value_type = T;
  using reference = T &;
  using const_reference = const T &;
  using size_type = std::size_t;
  using difference_type = std::ptrdiff_t;
 
  static constexpr std::size_t ChunkSize = ChunkSizeV;
 
  class iterator {
  public:
    using value_type = T;
    using reference = T &;
    using pointer = T *;
    using difference_type = std::ptrdiff_t;
    using iterator_category = std::random_access_iterator_tag;
 
    iterator(LinkedVector<T, ChunkSizeV> *cnt, std::size_t pos)
        : cnt{cnt}, pos{pos} {}
 
    iterator &operator++() {
      if (pos != cnt->size()) {
        ++pos;
      }
      return *this;
    }
 
    iterator operator++(int) {
      iterator tmp{*this};
      ++(*this);
      return tmp;
    }
 
    iterator &operator--() {
      if (pos != 0) {
        --pos;
      }
      return *this;
    }
 
    iterator operator--(int) {
      iterator tmp{*this};
      --(*this);
      return tmp;
    }
 
    reference operator*() { return cnt->at(pos); }
 
    pointer operator->() { return &cnt->at(pos); }
 
    bool operator==(const iterator &other) const {
      return cnt == other.cnt && pos == other.pos;
    }
 
    bool operator!=(const iterator &other) const { return !(*this == other); }
 
  protected:
    LinkedVector<T, ChunkSizeV> *cnt;
    std::size_t pos;
  };
 
  LinkedVector() { initialise(); }
 
  LinkedVector(const LinkedVector<T, ChunkSizeV> &other) = delete;
 
  LinkedVector(LinkedVector<T, ChunkSizeV> &&other)
      : chunks{std::move(other.chunks)},
        discardedChunks{std::move(other.discardedChunks)},
        frontChunk{other.frontChunk}, backChunk{other.backChunk} {
    other.frontChunk = nullptr;
    other.backChunk = nullptr;
  }
 
  LinkedVector<T, ChunkSizeV> &
  operator=(const LinkedVector<T, ChunkSizeV> &other) = delete;
 
  LinkedVector<T, ChunkSizeV> &operator=(LinkedVector<T, ChunkSizeV> &&other) {
    if (this != &other) {
      LinkedVector<T, ChunkSizeV> tmp(std::move(other));
      swap(tmp);
    }
    return *this;
  }
 
  void swap(LinkedVector<T, ChunkSizeV> &other) {
    std::swap(chunks, other.chunks);
    std::swap(discardedChunks, other.discardedChunks);
    std::swap(frontChunk, other.frontChunk);
    std::swap(backChunk, other.backChunk);
  }
 
  template <typename Arg> void push_front(Arg &&value) {
    expandFront();
    frontChunk->push_front(std::forward<Arg>(value));
  }
 
  template <typename Arg> void push_back(Arg &&value) {
    expandBack();
    backChunk->push_back(std::forward<Arg>(value));
  }
 
  void pop_front() {
    if (frontChunk == backChunk && frontChunk->empty()) {
      return;
    }
 
    frontChunk->pop_front();
    trim_front();
  }
 
  void pop_back() {
    if (frontChunk == backChunk && backChunk->empty()) {
      return;
    }
 
    backChunk->pop_back();
    trim_back();
  }
 
  T &front() {
    if (frontChunk->empty()) {
      throw std::out_of_range("LinkedVector::front");
    }
 
    return frontChunk->front();
  }
 
  const T &front() const { return const_cast<LinkedVector *>(this)->front(); }
 
  T &back() {
    if (backChunk->empty()) {
      throw std::out_of_range("LinkedVector::back");
    }
 
    return backChunk->back();
  }
 
  const T &back() const { return const_cast<LinkedVector *>(this)->back(); }
 
  T &operator[](size_type pos) {
    if (const auto &fs = frontChunk->size(); pos < fs) {
      return frontChunk->operator[](pos);
    } else {
      pos -= fs;
      auto chunkIndex = pos / ChunkSizeV + 1;
      auto chunkOffset = pos % ChunkSizeV;
 
      auto it = chunks.begin();
      std::advance(it, chunkIndex);
      return it->get()->operator[](chunkOffset);
    }
 
    boxes_unreachable();
  }
 
  const T &operator[](size_type pos) const {
    return const_cast<LinkedVector *>(this)->operator[](pos);
  }
 
  T &at(size_type pos) {
    if (pos >= size()) {
      throw std::out_of_range("LinkedVector::at");
    }
    return (*this)[pos];
  }
 
  const T &at(size_type pos) const {
    return const_cast<LinkedVector *>(this)->at(pos);
  }
 
  iterator begin() { return iterator(this, 0); }
 
  iterator end() { return iterator(this, size()); }
 
  iterator cbegin() const { return begin(); }
 
  iterator cend() const { return end(); }
 
  bool operator==(const LinkedVector<T, ChunkSizeV> &other) const {
    if (size() != other.size()) {
      return false;
    }
 
    for (auto it = chunks.cbegin(), otherIt = other.chunks.cbegin();
         it != chunks.cend(); ++it, ++otherIt) {
      if (**it != **otherIt) {
        return false;
      }
    }
 
    return true;
  }
 
  bool operator!=(const LinkedVector<T, ChunkSizeV> &other) const {
    return !(*this == other);
  }
 
  std::size_t size() const BOXES_NOTHROW {
    switch (chunks.size()) {
    case 0:
      return 0;
    case 1:
      return frontChunk->size();
    case 2:
      return frontChunk->size() + backChunk->size();
    default:
      return frontChunk->size() + backChunk->size() +
             (chunks.size() - 2) * ChunkSizeV;
    }
 
    boxes_unreachable();
  }
 
  std::size_t capacity() const BOXES_NOTHROW {
    return chunks.size() * ChunkSizeV;
  }
 
  void clear() {
    chunks.clear();
    discardedChunks.clear();
    initialise();
  }
 
  bool empty() const BOXES_NOTHROW { return size() == 0; }
 
protected:
  using Chunk = RingBuffer<T, ChunkSizeV>;
  std::list<std::unique_ptr<Chunk>> chunks;
  std::list<std::unique_ptr<Chunk>> discardedChunks;
  Chunk *frontChunk{nullptr};
  Chunk *backChunk{nullptr};
 
  void trim_front() {
    if (frontChunk != backChunk && frontChunk->empty()) {
      discardedChunks.push_back(std::move(chunks.front()));
      chunks.pop_front();
      frontChunk = chunks.front().get();
    }
  }
 
  void trim_back() {
    if (frontChunk != backChunk && backChunk->empty()) {
      discardedChunks.push_back(std::move(chunks.back()));
      chunks.pop_back();
      backChunk = chunks.back().get();
    }
  }
 
  void expandFront() {
    if (frontChunk->full()) {
      auto c = getChunk();
      frontChunk = c.get();
      chunks.push_front(std::move(c));
    }
  }
 
  void expandBack() {
    if (backChunk->full()) {
      auto c = getChunk();
      backChunk = c.get();
      chunks.push_back(std::move(c));
    }
  }
 
  std::unique_ptr<Chunk> getChunk() {
    if (discardedChunks.empty()) {
      return std::make_unique<Chunk>();
    }
 
    auto c = std::move(discardedChunks.front());
    c->clear();
    discardedChunks.pop_front();
    return c;
  }
 
  void initialise() {
    chunks.push_back(getChunk());
    frontChunk = chunks.front().get();
    backChunk = chunks.back().get();
  }
};
 
} // namespace boxes
 
#endif // __BOXES_LINKED_VECTOR_HPP__