// list standard header
#ifndef _LIST_
#define _LIST_

#pragma info(none)
#ifndef __CHKHDR__
#  pragma report(level, E)
#endif
#pragma info(restore)

#if __IBMCPP__ < 400
#error This file to be used only with IBM VisualAge C++ v4 and later compilers.
#endif /* __IBMCPP__ */

#pragma namemangling(ansi)

   /********************************************************************/
   /*  <list> header file                                              */
   /*                                                                  */
   /*  VisualAge C++, Version 4.0                                      */
   /*    Licensed Material - Property of IBM                           */
   /*                                                                  */
   /*  5801-AAR and Other Materials                                    */
   /*                                                                  */
   /*  (c) Copyright IBM Corp 1991, 1998. All rights reserved.         */
   /*                                                                  */
   /*                                                                  */
   /*  Licensed Materials.                                             */
   /*                                                                  */
   /*  Dinkum C++ Library                                              */
   /*  Copyright (c) 1998.  Licensed to IBM Corp. and its suppliers.   */
   /*                                                                  */
   /********************************************************************/

#include <functional>
#include <iterator>
#include <memory>
#include <stdexcept>
_STD_BEGIN

		// TEMPLATE CLASS _List_nod
template<class _Ty, class _A>
	class _List_nod {
protected:
	typedef typename _A::template
		rebind<void>::other::pointer _Genptr;
	struct _Node;
	friend struct _Node;
	struct _Node {
		_Genptr _Next, _Prev;
		_Ty _Value;
		};
	_List_nod(_A _Al)
		: _Alnod(_Al) {}
	typename _A::template rebind<_Node>::other _Alnod;
	};
		// TEMPLATE CLASS _List_ptr
template<class _Ty, class _A>
	class _List_ptr : public _List_nod<_Ty, _A> {
protected:
	typedef typename _List_nod<_Ty, _A>::_Node _Node;
	typedef typename _A::template
		rebind<_Node>::other::pointer _Nodeptr;
	_List_ptr(_A _Al)
		: _List_nod<_Ty, _A>(_Al), _Alptr(_Al) {}
	typename _A::template rebind<_Nodeptr>::other _Alptr;
	};
		// TEMPLATE CLASS _List_val
template<class _Ty, class _A>
	class _List_val : public _List_ptr<_Ty, _A> {
protected:
	_List_val(_A _Al = _A())
		: _List_ptr<_Ty, _A>(_Al), _Alval(_Al) {}
	typedef typename _A::template
		rebind<_Ty>::other _Alty;
	_Alty _Alval;
	};

		// TEMPLATE CLASS list
template<class _Ty, class _Ax _TDEF(allocator<_Ty>) >
	class list : public _List_val<_Ty, _Ax> {
public:
	typedef list<_Ty, _Ax> _Myt;
	typedef _List_val<_Ty, _Ax> _Mybase;
	typedef typename _Mybase::_Alty _A;
protected:
	typedef typename _List_nod<_Ty, _A>::_Genptr _Genptr;
	typedef typename _List_nod<_Ty, _A>::_Node _Node;
	typedef _POINTER_X(_Node, _A) _Nodeptr;
	struct _Acc;
	friend struct _Acc;
	struct _Acc {
		typedef _REFERENCE_X(_Nodeptr, _A) _Nodepref;
		typedef typename _A::reference _Vref;
		static _Nodepref _Next(_Nodeptr _P)
			{return ((_Nodepref)(*_P)._Next); }
		static _Nodepref _Prev(_Nodeptr _P)
			{return ((_Nodepref)(*_P)._Prev); }
		static _Vref _Value(_Nodeptr _P)
			{return ((_Vref)(*_P)._Value); }
		};
public:
	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 typename _A::reference _Reft;
	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 _Bidit<_Ty, _Dift, _Tptr, _Reft> {
	public:
		typedef _Bidit<_Ty, _Dift, _Tptr, _Reft> _Mybase;
		typedef typename _Mybase::iterator_category
			iterator_category;
		typedef typename _Mybase::value_type value_type;
		typedef typename _Mybase::difference_type
			difference_type;
		typedef typename _Mybase::pointer pointer;
		typedef typename _Mybase::reference reference;
		iterator()
			: _Ptr(0) {}
		iterator(_Nodeptr _P)
			: _Ptr(_P) {}
		reference operator*() const
			{return (_Acc::_Value(_Ptr)); }
		_Tptr operator->() const
			{return (&**this); }
		iterator& operator++()
			{_Ptr = _Acc::_Next(_Ptr);
			return (*this); }
		iterator operator++(int)
			{iterator _Tmp = *this;
			++*this;
			return (_Tmp); }
		iterator& operator--()
			{_Ptr = _Acc::_Prev(_Ptr);
			return (*this); }
		iterator operator--(int)
			{iterator _Tmp = *this;
			--*this;
			return (_Tmp); }
		bool operator==(const iterator& _X) const
			{return (_Ptr == _X._Ptr); }
		bool operator!=(const iterator& _X) const
			{return (!(*this == _X)); }
		_Nodeptr _Mynode() const
			{return (_Ptr); }
	protected:
		_Nodeptr _Ptr;
		};
		// CLASS const_iterator
	class const_iterator;
	friend class const_iterator;
	class const_iterator
		: public _Bidit<_Ty, _Dift, _Ctptr, const_reference> {
	public:
		typedef _Bidit<_Ty, _Dift, _Ctptr, const_reference>
			_Mybase;
		typedef typename _Mybase::iterator_category
			iterator_category;
		typedef typename _Mybase::value_type value_type;
		typedef typename _Mybase::difference_type
			difference_type;
		typedef typename _Mybase::pointer pointer;
		typedef typename _Mybase::reference reference;
		const_iterator()
			: _Ptr(0) {}
		const_iterator(_Nodeptr _P)
			: _Ptr(_P) {}
		const_iterator(const iterator& _X)
			: _Ptr(_X._Mynode()) {}
		const_reference operator*() const
			{return (_Acc::_Value(_Ptr)); }
		_Ctptr operator->() const
			{return (&**this); }
		const_iterator& operator++()
			{_Ptr = _Acc::_Next(_Ptr);
			return (*this); }
		const_iterator operator++(int)
			{const_iterator _Tmp = *this;
			++*this;
			return (_Tmp); }
		const_iterator& operator--()
			{_Ptr = _Acc::_Prev(_Ptr);
			return (*this); }
		const_iterator operator--(int)
			{const_iterator _Tmp = *this;
			--*this;
			return (_Tmp); }
		bool operator==(const const_iterator& _X) const
			{return (_Ptr == _X._Ptr); }
		bool operator!=(const const_iterator& _X) const
			{return (!(*this == _X)); }
		_Nodeptr _Mynode() const
			{return (_Ptr); }
	protected:
		_Nodeptr _Ptr;
		};
	typedef typename std::reverse_iterator<iterator>
		reverse_iterator;
	typedef typename std::reverse_iterator<const_iterator>
		const_reverse_iterator;
	list()
		: _Mybase(), _Head(_Buynode()), _Size(0)
		{}
	explicit list(const _A& _Al)
		: _Mybase(_Al), _Head(_Buynode()), _Size(0)
		{}
	explicit list(size_type _N)
		: _Mybase(), _Head(_Buynode()), _Size(0)
		{insert(begin(), _N, _Ty()); }
	list(size_type _N, const _Ty& _V)
		: _Mybase(), _Head(_Buynode()), _Size(0)
		{insert(begin(), _N, _V); }
	list(size_type _N, const _Ty& _V, const _A& _Al)
		: _Mybase(_Al), _Head(_Buynode()), _Size(0)
		{insert(begin(), _N, _V); }
	list(const _Myt& _X)
		: _Mybase(_X._Alval),
			_Head(_Buynode()), _Size(0)
		{insert(begin(), _X.begin(), _X.end()); }
	template<class _It>
		list(_It _F, _It _L)
		: _Mybase(), _Head(_Buynode()), _Size(0)
		{_Construct(_F, _L, _Iter_cat(_F)); }
	template<class _It>
		list(_It _F, _It _L, const _A& _Al)
		: _Mybase(_Al), _Head(_Buynode()), _Size(0)
		{_Construct(_F, _L, _Iter_cat(_F)); }
	template<class _It>
		void _Construct(_It _F, _It _L, _Int_iterator_tag)
		{insert(begin(), (size_type)_F, (_Ty)_L); }
	template<class _It>
		void _Construct(_It _F, _It _L, input_iterator_tag)
		{insert(begin(), _F, _L); }
	~list()
		{erase(begin(), end());
		_Freenode(_Head);
		_Head = 0, _Size = 0; }
	_Myt& operator=(const _Myt& _X)
		{if (this != &_X)
			{iterator _F1 = begin();
			iterator _L1 = end();
			const_iterator _F2 = _X.begin();
			const_iterator _L2 = _X.end();
			for (; _F1 != _L1 && _F2 != _L2; ++_F1, ++_F2)
				*_F1 = *_F2;
			erase(_F1, _L1);
			insert(_L1, _F2, _L2); }
		return (*this); }
	iterator begin()
		{return (iterator(_Head == 0 ? 0
			: _Acc::_Next(_Head))); }
	const_iterator begin() const
		{return (const_iterator(_Head == 0 ? 0
			: _Acc::_Next(_Head))); }
	iterator end()
		{return (iterator(_Head)); }
	const_iterator end() const
		{return (const_iterator(_Head)); }
	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
			while (_N < size())
				pop_back(); }
	size_type size() const
		{return (_Size); }
	size_type max_size() const
		{return (_Mybase::_Alval.max_size()); }
	bool empty() const
		{return (size() == 0); }
	allocator_type get_allocator() const
		{return (_Mybase::_Alval); }
	reference front()
		{return (*begin()); }
	const_reference front() const
		{return (*begin()); }
	reference back()
		{return (*(--end())); }
	const_reference back() const
		{return (*(--end())); }
	void push_front(const _Ty& _X)
		{_Insert(begin(), _X); }
	void pop_front()
		{erase(begin()); }
	void push_back(const _Ty& _X)
		{_Insert(end(), _X); }
	void pop_back()
		{erase(--end()); }
	template<class _It>
		void assign(_It _F, _It _L)
		{_Assign(_F, _L, _Iter_cat(_F)); }
	template<class _It>
		void _Assign(_It _F, _It _L, _Int_iterator_tag)
		{assign((size_type)_F, (_Ty)_L); }
	template<class _It>
		void _Assign(_It _F, _It _L, input_iterator_tag)
		{erase(begin(), end());
		insert(begin(), _F, _L); }
	void assign(size_type _N, const _Ty& _X)
		{_Ty _Tx = _X;
		erase(begin(), end());
		insert(begin(), _N, _Tx); }
	iterator insert(iterator _P, const _Ty& _X)
		{_Insert(_P, _X);
		return (--_P); }
	void _Insert(iterator _P, const _Ty& _X)
		{_Nodeptr _S = _P._Mynode();
		_Nodeptr _Snew = _Buynode(_S, _Acc::_Prev(_S));
		_Incsize(1);
		_TRY_BEGIN
		_Mybase::_Alval.construct(&_Acc::_Value(_Snew), _X);
		_CATCH_ALL
		--_Size;
		_Freenode(_Snew);
		_RERAISE;
		_CATCH_END
		_Acc::_Prev(_S) = _Snew;
		_Acc::_Next(_Acc::_Prev(_Snew)) = _Snew; }
	void insert(iterator _P, size_type _M, const _Ty& _X)
		{size_type _N = _M;
		_TRY_BEGIN
		for (; 0 < _M; --_M)
			_Insert(_P, _X);
		_CATCH_ALL
		for (; _M < _N; ++_M)
			{iterator _Pm = _P;
			erase(--_Pm); }
		_RERAISE;
		_CATCH_END }
	template<class _It>
		void insert(iterator _P, _It _F, _It _L)
		{_Insert(_P, _F, _L, _Iter_cat(_F)); }
	template<class _It>
		void _Insert(iterator _P, _It _F, _It _L,
			_Int_iterator_tag)
		{insert(_P, (size_type)_F, (_Ty)_L); }
	template<class _It>
		void _Insert(iterator _P, _It _F, _It _L,
			input_iterator_tag)
		{size_type _N = 0;
		_TRY_BEGIN
		for (; _F != _L; ++_F, ++_N)
			_Insert(_P, *_F);
		_CATCH_ALL
		for (; 0 < _N; --_N)
			{iterator _Pm = _P;
			erase(--_Pm); }
		_RERAISE;
		_CATCH_END }
	template<class _It>
		void _Insert(iterator _P, _It _F, _It _L,
			forward_iterator_tag)
		{_It _Fs = _F;
		_TRY_BEGIN
		for (; _F != _L; ++_F)
			_Insert(_P, *_F);
		_CATCH_ALL
		for (; _Fs != _F; ++_Fs)
			{iterator _Pm = _P;
			erase(--_Pm); }
		_RERAISE;
		_CATCH_END }
	iterator erase(iterator _P)
		{_Nodeptr _S = (_P++)._Mynode();
		_Acc::_Next(_Acc::_Prev(_S)) = _Acc::_Next(_S);
		_Acc::_Prev(_Acc::_Next(_S)) = _Acc::_Prev(_S);
		_Mybase::_Alval.destroy(&_Acc::_Value(_S));
		_Freenode(_S);
		--_Size;
		return (_P); }
	iterator erase(iterator _F, iterator _L)
		{while (_F != _L)
			erase(_F++);
		return (_F); }
	void clear()
		{erase(begin(), end()); }
	void swap(_Myt& _X)
		{if (_Mybase::_Alval == _X._Alval)
			{std::swap(_Head, _X._Head);
			std::swap(_Size, _X._Size); }
		else
			{iterator _P = begin();
			splice(_P, _X);
			_X.splice(_X.begin(), *this, _P, end()); }}
	void splice(iterator _P, _Myt& _X)
		{if (!_X.empty())
			{_Incsize(_X._Size);
			_Splice(_P, _X, _X.begin(), _X.end());
			_X._Size = 0; }}
	void splice(iterator _P, _Myt& _X, iterator _F)
		{iterator _L = _F;
		if (0 < _X.size() && _P != _F && _P != ++_L)
			{_Incsize(1);
			_Splice(_P, _X, _F, _L);
			--_X._Size; }}
	void splice(iterator _P, _Myt& _X, iterator _F, iterator _L)
		{if (_F != _L)
			{if (&_X != this)
				{difference_type _N = 0;
				_Distance(_F, _L, _N);
				_Incsize(_N);
				_X._Size -= _N; }
			_Splice(_P, _X, _F, _L); }}
	void remove(const _Ty& _V)
		{iterator _L = end();
		for (iterator _F = begin(); _F != _L; )
			if (*_F == _V)
				erase(_F++);
			else
				++_F; }
	template<class _Pr1>
	void remove_if(_Pr1 _Pr)
		{iterator _L = end();
		for (iterator _F = begin(); _F != _L; )
			if (_Pr(*_F))
				erase(_F++);
			else
				++_F; }
	void unique()
		{iterator _F = begin(), _L = end();
		if (_F != _L)
			for (iterator _M = _F; ++_M != _L; _M = _F)
				if (*_F == *_M)
					erase(_M);
				else
					_F = _M; }
	template<class _Pr2>
	void unique(_Pr2 _Pr)
		{iterator _F = begin(), _L = end();
		if (_F != _L)
			for (iterator _M = _F; ++_M != _L; _M = _F)
				if (_Pr(*_F, *_M))
					erase(_M);
				else
					_F = _M; }
	void merge(_Myt& _X)
		{if (&_X != this)
			{iterator _F1 = begin(), _L1 = end();
			iterator _F2 = _X.begin(), _L2 = _X.end();
			while (_F1 != _L1 && _F2 != _L2)
				if (*_F2 < *_F1)
					{iterator _Mid2 = _F2;
					_Splice(_F1, _X, _F2, ++_Mid2);
					_F2 = _Mid2; }
				else
					++_F1;
			if (_F2 != _L2)
				_Splice(_L1, _X, _F2, _L2);
			_Incsize(_X._Size);
			_X._Size = 0; }}
	template<class _Pr3>
	void merge(_Myt& _X, _Pr3 _Pr)
		{if (&_X != this)
			{iterator _F1 = begin(), _L1 = end();
			iterator _F2 = _X.begin(), _L2 = _X.end();
			while (_F1 != _L1 && _F2 != _L2)
				if (_Pr(*_F2, *_F1))
					{iterator _Mid2 = _F2;
					_Splice(_F1, _X, _F2, ++_Mid2);
					_F2 = _Mid2; }
				else
					++_F1;
			if (_F2 != _L2)
				_Splice(_L1, _X, _F2, _L2);
			_Incsize(_X._Size);
			_X._Size = 0; }}
	void sort()
		{if (2 <= size())
			{const size_t _MAXN = 15;
			_Myt _X(_Mybase::_Alval), _Arr[_MAXN + 1];
			size_t _N = 0;
			while (!empty())
				{_X.splice(_X.begin(), *this, begin());
				size_t _I;
				for (_I = 0; _I < _N && !_Arr[_I].empty(); ++_I)
					{_Arr[_I].merge(_X);
					_Arr[_I].swap(_X); }
				if (_I == _MAXN)
					_Arr[_I - 1].merge(_X);
				else
					{_Arr[_I].swap(_X);
					if (_I == _N)
						++_N; }}
			while (0 < _N)
				merge(_Arr[--_N]); }}
	template<class _Pr3>
	void sort(_Pr3 _Pr)
		{if (2 <= size())
			{const size_t _MAXN = 15;
			_Myt _X(_Mybase::_Alval), _Arr[_MAXN + 1];
			size_t _N = 0;
			while (!empty())
				{_X.splice(_X.begin(), *this, begin());
				size_t _I;
				for (_I = 0; _I < _N && !_Arr[_I].empty(); ++_I)
					{_Arr[_I].merge(_X, _Pr);
					_Arr[_I].swap(_X); }
				if (_I == _MAXN)
					_Arr[_I - 1].merge(_X, _Pr);
				else
					{_Arr[_I].swap(_X);
					if (_I == _N)
						++_N; }}
			while (0 < _N)
				merge(_Arr[--_N], _Pr); }}
	void reverse()
		{if (2 <= size())
			{iterator _L = end();
			for (iterator _F = ++begin(); _F != _L; )
				{iterator _M = _F;
				_Splice(begin(), *this, _M, ++_F); }}}
protected:
	_Nodeptr _Buynode(_Nodeptr _Narg = 0, _Nodeptr _Parg = 0)
		{_Nodeptr _S = _Alnod.allocate(1, (void *)0);
		_Alptr.construct(&_Acc::_Next(_S),
			_Narg != 0 ? _Narg : _S);
		_Alptr.construct(&_Acc::_Prev(_S),
			_Parg != 0 ? _Parg : _S);
		return (_S); }
	void _Freenode(_Nodeptr _S)
		{_Alptr.destroy(&_Acc::_Next(_S));
		_Alptr.destroy(&_Acc::_Prev(_S));
		_Alnod.deallocate(_S, 1); }
	void _Splice(iterator _P, _Myt& _X, iterator _F, iterator _L)
		{if (_Mybase::_Alval == _X._Alval)
			{_Acc::_Next(_Acc::_Prev(_L._Mynode())) =
				_P._Mynode();
			_Acc::_Next(_Acc::_Prev(_F._Mynode())) =
				_L._Mynode();
			_Acc::_Next(_Acc::_Prev(_P._Mynode())) =
				_F._Mynode();
			_Nodeptr _S = _Acc::_Prev(_P._Mynode());
			_Acc::_Prev(_P._Mynode()) =
				_Acc::_Prev(_L._Mynode());
			_Acc::_Prev(_L._Mynode()) =
				_Acc::_Prev(_F._Mynode());
			_Acc::_Prev(_F._Mynode()) = _S; }
		else
			{insert(_P, _F, _L);
			_X.erase(_F, _L); }}
	void _Incsize(size_type _N)
		{if (max_size() - size() < _N)
			_THROW(length_error, "");
		_Size += _N; }
	void _Xran() const
		{_THROW(out_of_range, ""); }
	_Nodeptr _Head;
	size_type _Size;
	};
		// list TEMPLATE OPERATORS
template<class _Ty, class _A> inline
	void swap(list<_Ty, _A>& _X, list<_Ty, _A>& _Y)
	{_X.swap(_Y); }
template<class _Ty, class _A> inline
	bool operator==(const list<_Ty, _A>& _X,
		const list<_Ty, _A>& _Y)
	{return (_X.size() == _Y.size()
		&& equal(_X.begin(), _X.end(), _Y.begin())); }
template<class _Ty, class _A> inline
	bool operator!=(const list<_Ty, _A>& _X,
		const list<_Ty, _A>& _Y)
	{return (!(_X == _Y)); }
template<class _Ty, class _A> inline
	bool operator<(const list<_Ty, _A>& _X,
		const list<_Ty, _A>& _Y)
	{return (lexicographical_compare(_X.begin(), _X.end(),
		_Y.begin(), _Y.end())); }
template<class _Ty, class _A> inline
	bool operator>(const list<_Ty, _A>& _X,
		const list<_Ty, _A>& _Y)
	{return (_Y < _X); }
template<class _Ty, class _A> inline
	bool operator<=(const list<_Ty, _A>& _X,
		const list<_Ty, _A>& _Y)
	{return (!(_Y < _X)); }
template<class _Ty, class _A> inline
	bool operator>=(const list<_Ty, _A>& _X,
		const list<_Ty, _A>& _Y)
	{return (!(_X < _Y)); }
_STD_END

#pragma namemangling()

#pragma info(none)
#ifndef __CHKHDR__
#  pragma report(pop)
#endif
#pragma info(restore)

#endif /* _LIST_ */

/*
 * Copyright (c) 1995 by P.J. Plauger.  ALL RIGHTS RESERVED. 
 * Consult your license regarding permissions and restrictions.
 */

/*
 * This file is derived from software bearing the following
 * restrictions:
 *
 * Copyright (c) 1994
 * Hewlett-Packard Company
 *
 * Permission to use, copy, modify, distribute and sell this
 * software and its documentation for any purpose is hereby
 * granted without fee, provided that the above copyright notice
 * appear in all copies and that both that copyright notice and
 * this permission notice appear in supporting documentation.
 * Hewlett-Packard Company makes no representations about the
 * suitability of this software for any purpose. It is provided
 * "as is" without express or implied warranty.
V2.2:0081 */
