#ifndef TITBIT_CXX_DEQUE
#define TITBIT_CXX_DEQUE
#include <memory>
#include <utility>
#include <iterator>
namespace std {
// Authored circular buffer. Preserve the observed 48-byte x86 owner size; no
// recovered code accesses its old segmented-iterator representation directly.
template<class T,class A=allocator<T> > class deque {
 A alloc_;T*data_;size_t head_,size_,capacity_;unsigned reserved_[7];
 size_t slot(size_t i)const{return (head_+i)%capacity_;}
 void grow(size_t n){
  if(n<=capacity_)return;
  size_t cap=capacity_?capacity_*2:8;if(cap<n)cap=n;
  T*p=alloc_.allocate(cap);size_t copied=0;
  try{for(;copied<size_;++copied)new(p+copied)T(operator[](copied));}
  catch(...){while(copied)(p+--copied)->~T();alloc_.deallocate(p,cap);throw;}
  size_t count=size_;clear();if(data_)alloc_.deallocate(data_,capacity_);
  data_=p;head_=0;size_=count;capacity_=cap;
 }
 void initialize(){data_=0;head_=size_=capacity_=0;for(int i=0;i<7;++i)reserved_[i]=0;}
public:
 typedef T value_type;typedef size_t size_type;typedef ptrdiff_t difference_type;
 class const_iterator {
 protected:const deque*owner_;size_t index_;
 public:typedef T value_type;typedef ptrdiff_t difference_type;
  const_iterator():owner_(0),index_(0){}const_iterator(const deque*q,size_t n):owner_(q),index_(n){}
  const T&operator*()const{return (*owner_)[index_];}const T*operator->()const{return &operator*();}
  const_iterator&operator++(){++index_;return *this;}const_iterator operator++(int){const_iterator v=*this;++*this;return v;}const_iterator&operator--(){--index_;return *this;}
  bool operator==(const const_iterator&v)const{return owner_==v.owner_&&index_==v.index_;}bool operator!=(const const_iterator&v)const{return !(*this==v);}
 };
 class iterator:public const_iterator {
 public:iterator(){}iterator(deque*q,size_t n):const_iterator(q,n){}
  T&operator*()const{return const_cast<T&>(const_iterator::operator*());}T*operator->()const{return &operator*();}
  iterator&operator++(){++this->index_;return *this;}iterator operator++(int){iterator v=*this;++*this;return v;}iterator&operator--(){--this->index_;return *this;}
 };
 deque():alloc_(){initialize();}
 explicit deque(size_t n,const T&v=T()):alloc_(){initialize();while(n--)push_back(v);}
 deque(const deque&v):alloc_(){initialize();try{for(size_t i=0;i<v.size();++i)push_back(v[i]);}catch(...){clear();if(data_)alloc_.deallocate(data_,capacity_);throw;}}
 ~deque(){clear();if(data_)alloc_.deallocate(data_,capacity_);}
 deque&operator=(const deque&v){if(this!=&v){deque copy(v);swap(copy);}return *this;}
 size_t size()const{return size_;}bool empty()const{return size_==0;}
 T&front(){return operator[](0);}const T&front()const{return operator[](0);}T&back(){return operator[](size_-1);}const T&back()const{return operator[](size_-1);}
 iterator begin(){return iterator(this,0);}iterator end(){return iterator(this,size_);}const_iterator begin()const{return const_iterator(this,0);}const_iterator end()const{return const_iterator(this,size_);}
 void push_front(const T&v){T copy(v);grow(size_+1);size_t first=head_?head_-1:capacity_-1;new(data_+first)T(copy);head_=first;++size_;}
 void push_back(const T&v){T copy(v);grow(size_+1);new(data_+slot(size_))T(copy);++size_;}
 void pop_front(){data_[head_].~T();head_=(head_+1)%capacity_;--size_;}
 void pop_back(){data_[slot(size_-1)].~T();--size_;}
 void clear(){while(size_)pop_back();head_=0;}
 T&operator[](size_t i){return data_[slot(i)];}const T&operator[](size_t i)const{return data_[slot(i)];}
 void swap(deque&v){std::swap(data_,v.data_);std::swap(head_,v.head_);std::swap(size_,v.size_);std::swap(capacity_,v.capacity_);}
};
}
#endif
