// deque standard header

/* This file is for use only in conjunction with a valid license for
Microsoft Visual C++ V5.0 or V6.0. Microsoft Corporation is in no way
involved with the production or release of this file. The file is
offered on an ``as is'' basis.

DINKUMWARE, LTD. AND P.J. PLAUGER MAKE NO REPRESENTATIONS OR WARRANTIES
ABOUT THE SUITABILITY OF THIS FILES, EITHER EXPRESS OR IMPLIED,
INCLUDING BUT NOT LIMITED TO THE IMPLIED WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE, OR NON-INFRINGEMENT. DINKUMWARE, LTD.
AND P.J. PLAUGER SHALL NOT BE LIABLE FOR ANY DAMAGES SUFFERED BY
LICENSEE AS A RESULT OF USING THIS FILE.

For additional information, contact Dinkumware, Ltd. (+1-888-4DINKUM or
support@dinkumware.com).

Version date: 18 October 1999
	replace 02 July 1999/11 August 1998 version with latest
	to fix several allocation and iterator comparison errors
 */

#if 1000 < _MSC_VER /*IFSTRIP=IGN*/
#pragma once
#endif

#ifndef _DEQUE_
#define _DEQUE_
#include <iterator>
#include <memory>
#include <stdexcept>

#ifdef  _MSC_VER
#pragma pack(push,8)
#endif  /* _MSC_VER */
#if 1200 <= _MSC_VER
#pragma warning(push,3)
#endif
 #pragma warning(disable:4284)
_STD_BEGIN
#define _DEQUEMAPSIZ	8	/* at least 1 */
#define _DEQUESIZ (4096 < sizeof (_Ty) ? \
	1 : 4096 / sizeof (_Ty))

		// TEMPLATE CLASS _Deque_val
template<class _Ty, class _A>
	class _Deque_val {
protected:
	_Deque_val(_A _Al = _A())
		: _Alval(_Al) {}
	typedef _A _Alty;
	_Alty _Alval;
	};

		// TEMPLATE CLASS deque
template<class _Ty, class _Ax = allocator<_Ty> >
	class deque
		: public _Deque_val<_Ty, _Ax> {
public:
	typedef deque<_Ty, _Ax> _Myt;
	typedef _Deque_val<_Ty, _Ax> _Mybase;
	typedef typename _Mybase::_Alty _A;
	typedef _A allocator_type;
	typedef typename _A::size_type size_type;
	typedef typename _A::difference_type _Dift;
	typedef _Dift difference_type;
	typedef typename _A::pointer _Tptr;
	typedef typename _A::const_pointer _Ctptr;
	typedef _Tptr pointer;
	typedef _Ctptr const_pointer;
	typedef _POINTER_X(_Tptr, _A) _Mapptr;
	typedef typename _A::reference _Reft;
	typedef _Tptr pointer;
	typedef _Ctptr const_pointer;
	typedef _Reft reference;
	typedef typename _A::const_reference const_reference;
	typedef typename _A::value_type value_type;

		// CLASS iterator
	class iterator;
	friend class iterator;
	class iterator : public _Ranit<_Ty, _Dift> {
	public:
		typedef random_access_iterator_tag iterator_category;
		typedef _Ty value_type;
		typedef _Dift difference_type;
		typedef _Tptr pointer;
		typedef _Reft reference;
		iterator()
			: _Idx(0), _Deque(0)
			{}
		iterator(difference_type _I, const deque<_Ty, _A> *_P)
			: _Idx(_I), _Deque(_P)
			{}
		reference operator*() const
			{size_type _Block = _Idx / _DEQUESIZ;
			size_type _Off = _Idx - _Block * _DEQUESIZ;
			if (_Deque->_Mapsize <= _Block)
				_Block -= _Deque->_Mapsize;
			return ((_Deque->_Map)[_Block][_Off]); }
		_Tptr operator->() const
			{return (&**this); }
		iterator& operator++()
			{++_Idx;
			return (*this); }
		iterator operator++(int)
			{iterator _Tmp = *this;
			++*this;
			return (_Tmp); }
		iterator& operator--()
			{--_Idx;
			return (*this); }
		iterator operator--(int)
			{iterator _Tmp = *this;
			--*this;
			return (_Tmp); }
		iterator& operator+=(difference_type _N)
			{_Idx += _N;
			return (*this); }
		iterator& operator-=(difference_type _N)
			{return (*this += -_N); }
		iterator operator+(difference_type _N) const
			{iterator _Tmp = *this;
			return (_Tmp += _N); }
		iterator operator-(difference_type _N) const
			{iterator _Tmp = *this;
			return (_Tmp -= _N); }
		difference_type operator-(const iterator& _X) const
			{return (_Idx - _X._Idx); }
		reference operator[](difference_type _N) const
			{return (*(*this + _N)); }
		bool operator==(const iterator& _X) const
			{return (_Deque == _X._Deque && _Idx == _X._Idx); }
		bool operator!=(const iterator& _X) const
			{return (!(*this == _X)); }
		bool operator<(const iterator& _X) const
			{return (_Idx < _X._Idx); }
		bool operator<=(const iterator& _X) const
			{return (!(_X < *this)); }
		bool operator>(const iterator& _X) const
			{return (_X < *this); }
		bool operator>=(const iterator& _X) const
			{return (!(*this < _X)); }
//	protected:
		difference_type _Idx;
		const deque<_Ty, _A> *_Deque;
		};

		// CLASS const_iterator
	class const_iterator;
	friend class const_iterator;
	class const_iterator
		: public _Ranit<_Ty, _Dift> {
	public:
		typedef random_access_iterator_tag iterator_category;
		typedef _Ty value_type;
		typedef _Dift difference_type;
		typedef _Ctptr pointer;
		typedef const_reference reference;
		const_iterator()
			: _Idx(0), _Deque(0)
			{}
		const_iterator(difference_type _I,
			const deque<_Ty, _A> *_P)
			: _Idx(_I), _Deque(_P)
			{}
		const_iterator(const iterator& _X)
			: _Idx(_X._Idx), _Deque(_X._Deque)
			{}
		const_reference operator*() const
			{size_type _Block = _Idx / _DEQUESIZ;
			size_type _Off = _Idx - _Block * _DEQUESIZ;
			if (_Deque->_Mapsize <= _Block)
				_Block -= _Deque->_Mapsize;
			return ((_Deque->_Map)[_Block][_Off]); }
		_Ctptr operator->() const
			{return (&**this); }
		const_iterator& operator++()
			{++_Idx;
			return (*this); }
		const_iterator operator++(int)
			{const_iterator _Tmp = *this;
			++*this;
			return (_Tmp); }
		const_iterator& operator--()
			{--_Idx;
			return (*this); }
		const_iterator operator--(int)
			{const_iterator _Tmp = *this;
			--*this;
			return (_Tmp); }
		const_iterator& operator+=(difference_type _N)
			{_Idx += _N;
			return (*this); }
		const_iterator& operator-=(difference_type _N)
			{return (*this += -_N); }
		const_iterator operator+(difference_type _N) const
			{const_iterator _Tmp = *this;
			return (_Tmp += _N); }
		const_iterator operator-(difference_type _N) const
			{const_iterator _Tmp = *this;
			return (_Tmp -= _N); }
		difference_type operator-(
			const const_iterator& _X) const
			{return (_Idx - _X._Idx); }
		const_reference operator[](difference_type _N) const
			{return (*(*this + _N)); }
		bool operator==(const const_iterator& _X) const
			{return (_Deque == _X._Deque && _Idx == _X._Idx); }
		bool operator!=(const const_iterator& _X) const
			{return (!(*this == _X)); }
		bool operator<(const const_iterator& _X) const
			{return (_Idx < _X._Idx); }
		bool operator<=(const const_iterator& _X) const
			{return (!(_X < *this)); }
		bool operator>(const const_iterator& _X) const
			{return (_X < *this); }
		bool operator>=(const const_iterator& _X) const
			{return (!(*this < _X)); }
	protected:
		difference_type _Idx;
		const deque<_Ty, _A> *_Deque;
		};
	typedef std::reverse_iterator<const_iterator, value_type,
		const_reference, _Ctptr, difference_type>
			const_reverse_iterator;
	typedef std::reverse_iterator<iterator, value_type,
		reference, _Tptr, difference_type>
			reverse_iterator;
	deque()
		: _Mybase(), _Map(0),
			_Mapsize(0), _Offset(0), _Size(0)
		{}
	explicit deque(const _A& _Al)
		: _Mybase(_Al), _Map(0),
			_Mapsize(0), _Offset(0), _Size(0)
		{}
	explicit deque(size_type _N)
		: _Mybase(), _Map(0),
			_Mapsize(0), _Offset(0), _Size(0)
		{insert(begin(), _N, _Ty()); }
	deque(size_type _N, const _Ty& _V)
		: _Mybase(), _Map(0),
			_Mapsize(0), _Offset(0), _Size(0)
		{insert(begin(), _N, _V); }
	deque(size_type _N, const _Ty& _V, const _A& _Al)
		: _Mybase(_Al), _Map(0),
			_Mapsize(0), _Offset(0), _Size(0)
		{insert(begin(), _N, _V); }
	deque(const _Myt& _X)
		: _Mybase(_X._Alval), _Map(0),
			_Mapsize(0), _Offset(0), _Size(0)
		{insert(begin(), _X.begin(), _X.end()); }
	template<class _It>
		deque(_It _F, _It _L)
		: _Mybase(), _Map(0),
			_Mapsize(0), _Offset(0), _Size(0)
		{_Construct(_F, _L, _Iter_cat(_F)); }
	template<class _It>
		deque(_It _F, _It _L, const _A& _Al)
		: _Mybase(_Al), _Map(0),
			_Mapsize(0), _Offset(0), _Size(0)
		{_Construct(_F, _L, _Iter_cat(_F)); }
	template<class _It>
		void _Construct(_It _F, _It _L, input_iterator_tag)
		{insert(begin(), _F, _L); }

	~deque()
		{clear(); }
	_Myt& operator=(const _Myt& _X)
		{if (this == &_X)
			;
		else if (_X.size() == 0)
			clear();
		else if (_X.size() <= size())
			{iterator _S = copy(_X.begin(), _X.end(), begin());
			erase(_S, end()); }
		else
			{const_iterator _Sx = _X.begin() + size();
			copy(_X.begin(), _Sx, begin());
			insert(end(), _Sx, _X.end()); }
		return (*this); }
	iterator begin()
		{return (iterator(_Offset, this)); }
	const_iterator begin() const
		{return (const_iterator(_Offset, this)); }
	iterator end()
		{return (iterator(_Offset + _Size, this)); }
	const_iterator end() const
		{return (const_iterator(_Offset + _Size, this)); }
	reverse_iterator rbegin()
		{return (reverse_iterator(end())); }
	const_reverse_iterator rbegin() const
		{return (const_reverse_iterator(end())); }
	reverse_iterator rend()
		{return (reverse_iterator(begin())); }
	const_reverse_iterator rend() const
		{return (const_reverse_iterator(begin())); }
	void resize(size_type _N)
		{resize(_N, _Ty()); }
	void resize(size_type _N, _Ty _X)
		{if (size() < _N)
			insert(end(), _N - size(), _X);
		else if (_N < size())
			erase(begin() + _N, end()); }
	size_type size() const
		{return (_Size); }
	size_type max_size() const
		{return (_Alval.max_size()); }
	bool empty() const
		{return (size() == 0); }
	allocator_type get_allocator() const
		{return (_Alval); }
	const_reference at(size_type _P) const
		{if (size() <= _P)
			_Xran();
		return (*(begin() + _P)); }