prime/include/rstl/vector.hpp

#ifndef _RSTL_VECTOR
#define _RSTL_VECTOR

#include "types.h"

#include "rstl/allocator_auto_ptr.hpp"
#include "rstl/iterator.hpp"
#include "rstl/pointer_iterator.hpp"
#include "rstl/rmemory_allocator.hpp"

class CInputStream;

namespace rstl {

template < typename T, typename Alloc = rmemory_allocator >
class vector {
public:
  Alloc x0_allocator;
  int x4_count;
  int x8_capacity;
  T* xc_items;

public:
  typedef Alloc allocator_type;
  typedef pointer_iterator< T, vector< T, Alloc >, Alloc > iterator;
  typedef const_pointer_iterator< T, vector< T, Alloc >, Alloc > const_iterator;
  typedef T value_type;

  iterator begin() { return iterator(xc_items); }
  const_iterator begin() const { return const_iterator(xc_items); }
  iterator end() { return iterator(xc_items + x4_count); }
  const_iterator end() const { return const_iterator(xc_items + x4_count); }
  vector(const Alloc& alloc = Alloc())
  : x0_allocator(alloc), x4_count(0), x8_capacity(0), xc_items(nullptr) {}
  vector(int count) : x4_count(0), x8_capacity(0), xc_items(0) { reserve(count); }
  vector(const int count, const T& v) : x4_count(count), x8_capacity(count) {
    x0_allocator.allocate(xc_items, x4_count);
    uninitialized_fill_n(xc_items, count, v);
  }
  vector(int count, const T& v, const Alloc& alloc);

  vector(const vector& other) : x4_count(other.x4_count), x8_capacity(other.x8_capacity) {
    if (other.x4_count == 0 && other.x8_capacity == 0) {
      xc_items = nullptr;
    } else {
      x0_allocator.allocate(xc_items, x8_capacity);
      uninitialized_copy_n(other.xc_items, x4_count, xc_items);
    }
  }
  vector(CInputStream& in, const Alloc& alloc = Alloc());
  ~vector() {
    destroy(begin(), end());
    x0_allocator.deallocate(xc_items);
  }

  void resize(int size, const T& in = T());
  void reserve(int size);
  iterator insert(iterator it, const T& value);

  template < typename from_iterator >
  iterator insert(iterator it, from_iterator begin, from_iterator end);

  // iterator erase(iterator it);
  // iterator erase(iterator first, iterator last);

  iterator erase(iterator it);
  iterator erase(iterator first, iterator last);

  void push_back(const T& in) {
    if (x4_count >= x8_capacity) {
      reserve(x8_capacity != 0 ? x8_capacity * 2 : 4);
    }
    rstl::construct(xc_items + x4_count, in);
    ++x4_count;
  }

  void pop_back() { --x4_count; }

  vector& operator=(const vector& other);

  void clear() {
    destroy(begin(), end());
    x4_count = 0;
  }

  T* data() { return xc_items; }
  const T* data() const { return xc_items; }
  int size() const { return x4_count; }
  bool empty() const { return x4_count == 0; }
  int capacity() const { return x8_capacity; }
  T& at(int idx) { return xc_items[idx]; }
  const T& at(int idx) const { return xc_items[idx]; }
  T& front() { return at(0); }
  const T& front() const { return at(0); }
  T& back() { return at(x4_count - 1); }
  const T& back() const { return at(x4_count - 1); }
  T& operator[](int idx) { return xc_items[idx]; }
  const T& operator[](int idx) const { return xc_items[idx]; }

protected:
  template < typename In >
  void insert_into(iterator at, int n, In in);
};

template < typename T, typename Alloc >
void vector< T, Alloc >::resize(int size, const T& in) {
  clear();
  reserve(size);
  for (int i = 0; i < size; ++i) {
    push_back(in);
  }
}

template < typename T, typename Alloc >
void vector< T, Alloc >::reserve(int newSize) {
  if (newSize <= x8_capacity) {
    return;
  }

  T* newData;
  x0_allocator.allocate(newData, newSize);
  uninitialized_copy(begin(), end(), newData);
  destroy(xc_items, xc_items + x4_count);
  x0_allocator.deallocate(xc_items);
  xc_items = newData;
  x8_capacity = newSize;
}

template < typename T, typename Alloc >
typename vector< T, Alloc >::iterator vector< T, Alloc >::insert(iterator it, const T& value) {
  typename iterator::difference_type diff = it.operator->() - xc_items;
  const_counting_iterator< T > in(&value, 0);
  insert_into(it, 1, in);
  return iterator(xc_items + diff);
}

template < typename T, typename Alloc >
template < typename from_iterator >
typename vector< T, Alloc >::iterator vector< T, Alloc >::insert(iterator it, from_iterator begin,
                                                                 from_iterator end) {
  insert_into(it, rstl::distance(begin, end), begin);
}

template < typename T, typename Alloc >
template < typename In >
void vector< T, Alloc >::insert_into(iterator at, int n, In in) {
  iterator atIt = at;
  T* items = xc_items;
  T* atPtr = atIt.operator->();
  const int newCount = x4_count + n;

  if (newCount <= x8_capacity) {
    const int atIdx = atPtr - items;
    int moveCount = x4_count - atIdx;
    int i = moveCount - 1;
    T* dst = atPtr + i + n;

    for (; i >= 0; --i) {
      construct(dst, items[atIdx + i]);
      --dst;
    }

    for (i = 0; i < n; ++i) {
      construct(atPtr, *in);
      ++atPtr;
    }

    x4_count += n;
  } else {
    int newCapacity = 4;
    if (x8_capacity != 0) {
      newCapacity = x8_capacity << 1;
    }
    while (newCapacity < newCount) {
      newCapacity <<= 1;
    }

    T* newData;
    x0_allocator.allocate(newData, newCapacity);

    int i = 0;
    int atIdx = atPtr - items;
    T* dst = newData;
    for (; i < atIdx; ++i) {
      construct(dst, items[i]);
      ++dst;
    }
    for (; i < atIdx + n; ++i) {
      construct(dst, *in);
      ++dst;
    }
    for (; i < x4_count + n; ++i) {
      construct(dst, items[i - n]);
      ++dst;
    }

    destroy(items, items + x4_count);
    x0_allocator.deallocate(items);
    xc_items = newData;
    x8_capacity = newCapacity;
    x4_count += n;
  }
}

template < typename T, typename Alloc >
vector< T, Alloc >& vector< T, Alloc >::operator=(const vector< T, Alloc >& other) {
  if (this == &other)
    return *this;
  clear();
  if (other.size() == 0) {
    x0_allocator.deallocate(xc_items);
    x4_count = 0;
    x8_capacity = 0;
    xc_items = nullptr;
  } else {
    reserve(other.size());
    uninitialized_copy(other.xc_items, other.xc_items + other.x4_count, data());
    x4_count = other.x4_count;
  }
  return *this;
}

template < typename T, typename Alloc >
typename vector< T, Alloc >::iterator vector< T, Alloc >::erase(iterator it) {
  return erase(it, it + 1);
}

template < typename T, typename Alloc >
typename vector< T, Alloc >::iterator vector< T, Alloc >::erase(iterator first, iterator last) {
  destroy(first, last);

  const int tmp = first - begin();

  int newCount = tmp;

  for (iterator it = last, moved = begin() + tmp; it != end(); ++moved, ++newCount, ++it) {
    construct(&*moved, *it);
  }
  x4_count = newCount;

  return first;
}

typedef vector< int > unk_vector;
CHECK_SIZEOF(unk_vector, 0x10)
} // namespace rstl

#endif // _RSTL_VECTOR