// svector.hpp
#ifndef SVECTOR_HPP_
#define SVECTOR_HPP_

#include <cstdlib>                            // malloc, free
#include <cstddef>                            // size_t
#include <cstring>                            // memcpy, memmove, memset
#include <stdexcept>                          // out_of_range

template <typename U>                         // T必须是POD类型(例如int, char, double),
class svector                                 // 使用其它类型可能会导致程序崩溃
{
public:
  typedef std::size_t size_type;              // 一般为unsigned long或unsigned int
  typedef U value_type;                       // U
  typedef value_type* pointer;                // U*
  typedef const value_type* const_pointer;    // const U*
  typedef pointer iterator;                   // U*用作迭代器
  typedef const_pointer const_iterator;       // const U*用作迭代器
  typedef value_type& reference;              // U&
  typedef const value_type& const_reference;  // const U&
protected:
  iterator start, current, finish;            // 分别指向存储空间三个不同位置
  static const size_type TSZ = sizeof(value_type);
  iterator allocate(size_type);               // 申请内存, 失败则抛出bad_alloc
  void deallocate(void*);                     // 释放内存
  void insert_aux(iterator, const_reference); // 在指定位置插入一个元素
  void pswap(iterator&, iterator&);           // 交换两个指针
  size_type power2ceil(size_type);            // 圆整成2的指数次幂
public:
  iterator begin() { return start; }          // 指向第一个元素
  const_iterator begin() const { return start; }
  iterator end() { return current; }          // 指向最后一个元素的下一个位置
  const_iterator end() const { return current; }
  size_type size() const { return size_type(current - start); }    // 当前元素个数
  size_type max_size() const { return size_type(-1) / TSZ; }       // 理论极限容量
  size_type capacity() const { return size_type(finish - start); } // 当前最大容量
  bool empty() const { return start == current; }                  // 判断是否为空?
  value_type& operator[](size_type i) { return *(start + i); }
  const_reference operator[](size_type i) const { return *(start + i); }
  value_type& at(size_type);                  // 类似于operator[], 但检查下标
  const_reference at(size_type) const;
  svector() : start(0), current(0), finish(0) {}
  explicit svector(size_type, const_reference = value_type());
  svector(const_iterator, const_iterator);
  svector(const svector&);
  virtual ~svector() { deallocate(start); }
  svector& operator =(const svector&);
  value_type& front() { return *begin(); }    // 第一个元素
  const_reference front() const { return *begin(); }
  value_type& back() { return *(end() - 1); } // 最后一个元素
  const_reference back() const { return *(end() - 1); }
  void push_back(const_reference);            // 添加新元素到末尾
  void swap(svector&);                        // 交换两个svector
  iterator insert(iterator, const_reference); // 在指定位置插入一个元素
  iterator insert(iterator pos) { return insert(pos, U()); }
  void insert(iterator, iterator, iterator);  // 在指定位置插入一个元素序列
  void insert (iterator, size_type, const_reference); // 在指定位置插入多个相同元素
  void pop_back() { --current; }                      // 删除末尾元素
  iterator erase(iterator);                   // 删除指定元素
  iterator erase(iterator, iterator);         // 删除一个区间的所有元素
  void reserve(size_type);                    // 预定大小
  void assign(iterator, iterator);            // 用一个序列重建svector
  void assign(size_type, const_reference);    // 用多个相同的值重建svector
  void resize(size_type, const_reference);    // 重新设定svector的大小
  void resize(size_type new_sz) { resize(new_sz, value_type()); }
  void clear() { current = start; }           // 清除所有元素
};  // svector

template <typename U>                         // 类似于operator[], 但检查下标是否合法
inline typename svector<U>::reference svector<U>::at(size_type i)
{
  if(i < size())
  	return *(start + i);
  else
  	throw std::out_of_range("svector subscript");
}

template <typename U>
inline typename svector<U>::const_reference svector<U>::at(size_type i) const
{
  if(i < size())
  	return *(start + i);
  else
  	throw std::out_of_range("svector subscript");
}

template <typename U>                        // 在末尾添加一个新元素
inline void svector<U>::push_back(const_reference x)
{
  insert_aux(end(), x);
}

template <typename U>                           // 交换两个svector
inline void svector<U>::swap(svector& x)
{
  pswap(start, x.start);
  pswap(current, x.current);
  pswap(finish, x.finish);
}

template <typename U>                        // 分配内存, 失败时抛出bad_alloc异常
inline typename svector<U>::iterator svector<U>::allocate(size_type n)
{
	void* ptr = std::malloc(n * TSZ);
	if(0 == ptr)
	  throw std::bad_alloc();
	return (pointer)ptr;
}

template <typename U>
inline void svector<U>::deallocate(void* p) {	std::free(p); }

template <typename U>                        // 向上圆整成2的指数次幂大小
inline typename svector<U>::size_type svector<U>::power2ceil(size_type x)   // x > 0
{
  --x;
  x |= x >> 1;
  x |= x >> 2;
  x |= x >> 4;
  x |= x >> 8;
  x |= x >> 16;
  //x |= x >> 32;                            // for 64 bit system
  return ++x;
}

template <typename U>                        // 拷贝构造函数
svector<U>::svector(const svector& x)
{
  start = allocate(x.capacity());
  current = start + (x.end() - x.begin());
  std::memcpy(start, x.begin(), TSZ * x.size());
  finish = start + x.capacity();
}

template <typename U>                       // 用n个value创建一个svector
svector<U>::svector(size_type n, const_reference value)
{
	size_type len = power2ceil(n);
	start = allocate(len);
	std::memset(start, value, n * TSZ);
  current = start + n;
  finish = start + len;
}

template <typename U>                      // 交换两个迭代器
inline void svector<U>::pswap(iterator& x, iterator& y)
{
	iterator tmp = x;
	x = y;
	y = tmp;
}

template <typename U>                      // 用[first, last)区间的元素建一个svector
svector<U>::svector(const_iterator first, const_iterator last)
{
  size_type n = last - first, len = power2ceil(n);
  if(0 != len)
  {
    start = allocate(len);
	  std::memcpy(start, first, TSZ * n);
    current = start + n;
  }
  else
    start = current = 0;
  finish = start + len;
}

template <typename U>                      // 允许深层复制
inline svector<U>& svector<U>::operator =(const svector<U>& x)
{
	if(&x != this)
	{
    if(x.size() > capacity())
	  {
      iterator tmp = allocate(x.capacity());
      std::memcpy(tmp, x.begin(), TSZ * x.size());
      deallocate(start);
      start = tmp;
      finish = start + x.capacity();
    }
    else
	  	std::memcpy(start, x.begin(), TSZ * x.size());
    current = start + x.size();
  }
  return *this;
}

template <typename U>                      // 在pos处插入一个x
inline void svector<U>::insert_aux(iterator pos, const_reference x)
{
  if(current != finish)
	{
		std::memmove(pos + 1, pos, (current - pos) * TSZ);
    *pos = x;
    ++current;
  }
  else
  {
    size_type old_sz = size();
    size_type len = (0 != old_sz ? (old_sz << 1) : 1);
    size_type psz = pos - start;
    iterator new_start = allocate(len);
    std::memcpy(new_start, start, TSZ * psz);
    std::memcpy(new_start + psz + 1, pos, TSZ * (current - pos));
    deallocate(start);
    start = new_start;
    current = start + old_sz + 1;
    finish = start + len;
    *(start + psz) = x;
  }
}

template <typename U>                      // 在pos处插入一个x
typename svector<U>::iterator svector<U>::insert(iterator pos, const_reference x)
{
  size_type n = pos - begin();
  if(current != finish && pos == end())
    *current++ = x;
  else
    insert_aux(pos, x);
  return begin() + n;
}

template <typename U>                     // 用[first, last)之间的元素重建svector
inline void svector<U>::assign(iterator first, iterator last)
{
	size_type n = size_type(last - first);
	if(n > size())
	{
		size_type new_sz = power2ceil(n);
		deallocate(start);
		start = allocate(new_sz);
		finish = start + new_sz;
	}
	std::memcpy(start, first, TSZ * n);
	current = start + n;
}

template <typename U>                     // 删除pos指向的元素
inline typename svector<U>::iterator svector<U>::erase(iterator pos)
{
  std::memmove(pos, pos + 1, TSZ * (current - pos - 1));
  --current;
  return pos;
}

//template <typename U>                     // 在pos处插入n个x
//inline void svector<U>::insert(iterator pos, size_type n, const_reference x)
//{
//  if(0 != n)
//	{
//    if(size_type(finish - current) >= n)
//	  {
//      size_type elems_after = current - pos;
//      if(elems_after > n)
//				std::memmove(pos + n, pos, TSZ * elems_after);
//      else
//        std::memcpy(pos + n, pos, TSZ * elems_after);
//      std::memset(pos, x, n * TSZ);
//      current += n;
//    }
//    else
//		{
//      size_type old_sz = size(), len = power2ceil(capacity() + n);
//      size_type psz = pos - start;
//      iterator new_start = allocate(len);
//      std::memcpy(new_start, start, TSZ * psz);
//      std::memset(new_start + psz, x, n * TSZ);
//      std::memcpy(new_start + n + psz, start + psz, TSZ * (old_sz - psz));
//      start = new_start;
//      current = start + old_sz + n;
//      finish = start + len;
//    }
//  }
//}
//
//template <typename U>                     // 在pos处插入[first, last)区间的所有元素
//inline void svector<U>::insert(iterator pos, iterator first, iterator last)
//{
//  if(first != last)
//	{
//		size_type n = size_type(last - first);
//    if(size_type(finish - current) >= n)
//	  {
//      size_type elems_after = current - pos;
//      if(elems_after > n)
//				std::memmove(pos + n, pos, TSZ * elems_after);
//      else
//        std::memcpy(pos + n, pos, TSZ * elems_after);
//      std::memcpy(pos, first, n * TSZ);
//      current += n;
//    }
//    else
//		{
//      size_type old_sz = size(), len = power2ceil(old_sz + n);
//      size_type psz = pos - start;
//      iterator new_start = allocate(len);
//      std::memcpy(new_start, start, TSZ * psz);
//      std::memcpy(new_start + psz, first, n * TSZ);
//      std::memcpy(new_start + n + psz, start + psz, TSZ * (old_sz - psz));
//      deallocate(start);
//      start = new_start;
//      current = start + old_sz + n;
//      finish = start + len;
//    }
//  }
//}

//template <typename U>                     // 用n个value重建svector
//inline void svector<U>::assign(size_type n, const_reference value)
//{
//	if(n > size())
//	{
//		size_type new_sz = power2ceil(n);
//		deallocate(start);
//		start = allocate(new_sz);
//		finish = start + new_sz;
//	}
//	std::memset(start, value, TSZ * n);
//	current = start + n;
//}

template <typename U>                    // 删除[first, last)之间的所有元素
inline typename svector<U>::iterator svector<U>::erase(iterator first, iterator last)
{
  if(first != last)
  {
  	std::memcpy(first, last, TSZ * (current - last));
    current -= size_type(last - first);
  }
  return first;
}

template <typename U>                     // 预定n个元素的位置
inline void svector<U>::reserve(size_type n)
{
  if(capacity() < n)
	{
    size_type old_sz = size(), len = power2ceil(n);
    iterator first = start;
	  start = allocate(len);
	  std::memcpy(start, first, TSZ * old_sz);
	  deallocate(first);
	  current = start + old_sz;
    finish = start + len;
  }
}

template <typename U>                     // 重新指定大小为new_sz, 用x填充富余空间
inline void svector<U>::resize(size_type new_sz, const_reference x)
{
  if(new_sz < size())
  {
    std::memset(start, x, TSZ * new_sz);
    current = start + new_sz;
  }
  else
	  insert(end(), new_sz - size(), x);
}

template <typename U>
inline void swap(svector<U>& x, svector<U>& y) { x.swap(y); }

template <typename U>                    // 比较两个svector是否相等
inline bool operator ==(const svector<U>& x, const svector<U>& y)
{
  return (x.size() == y.size()) &&
         (0 == std::memcmp(x.begin(), x.end(), x.size() * sizeof(U)));
}

template <typename U>                    // 比较两个svector是否前者较小
inline bool operator <(const svector<U>& x, const svector<U>& y)
{
  return (x.size() <= y.size()) &&
         (std::memcmp(x.begin(), x.end(), x.size() * sizeof(U)) < 0);
}

#endif // SVECTOR_HPP_
