// list stl/clr header
#ifndef _CLI_LIST_
 #define _CLI_LIST_
#include <cliext/functional>
#include <cliext/iterator>

namespace cliext {
	namespace impl {
//
// TEMPLATE REF CLASS list_node
//
template<typename _Value_t>
	ref class list_node
	:	public _STLCLR Generic::INode<_Value_t>
	{	// list node
public:
	typedef list_node<_Value_t> _Mytype_t;
	typedef _STLCLR Generic::INode<_Value_t> _Mynode_it;
	typedef _STLCLR Generic::IBidirectionalContainer<_Value_t> _Mycont_it;
	typedef _Value_t value_type;

	list_node(_Mycont_it^ _Owner)
		:	_Mycont(_Owner)
		{	// construct a node with defaults
		}

	_Mycont_it^ container()
		{	// return owning container
		return (_Head == nullptr ? nullptr : _Head->_Mycont);
		}

	bool is_head()
		{	// test if head node
		return (_Mycont != nullptr);
		}

	_Mytype_t^ next_node()
		{	// return successor node
		if (this == _Head || _Head == nullptr)
			throw gcnew System::InvalidOperationException();
		return (_Next);
		}

	_Mytype_t^ prev_node()
		{	// return predecessor node
		if (_Head == _Prev || _Head == nullptr)
			throw gcnew System::InvalidOperationException();
		return (_Prev);
		}

	property _Value_t% _Value
		{	// get or set _Myval
		virtual _Value_t% get()
			{	// get _Myval element
			if (this == _Head || _Head == nullptr)
				throw gcnew System::InvalidOperationException();
			return (_Myval);
			}

		virtual void set(_Value_t% _Val)
			{	// set _Myval element
			if (this == _Head || _Head == nullptr)
				throw gcnew System::InvalidOperationException();
			_Myval = _Val;
			}
		};

	// data members
	_Mycont_it^ _Mycont;	// pointer to owning list (if head node)
	_Mytype_t^ _Head;	// pointer to head node
	_Mytype_t^ _Next;	// pointer to successor node
	_Mytype_t^ _Prev;	// pointer to predecessor node
	value_type _Myval;	// the stored value (if not head node)

private:
	virtual _Mycont_it^ container_virtual() sealed
		= _Mynode_it::container
		{	// return owning container
		return (container());
		}

	virtual bool is_head_virtual() sealed
		= _Mynode_it::is_head
		{	// test if head node
		return (is_head());
		}

	virtual _Mynode_it^ next_node_virtual() sealed
		= _Mynode_it::next_node
		{	// return successor node
		return (next_node());
		}

	virtual _Mynode_it^ prev_node_virtual() sealed
		= _Mynode_it::prev_node
		{	// return predecessor node
		return (prev_node());
		}
	};

//
// TEMPLATE REF CLASS list_impl
//
template<typename _Value_t,
	bool _Is_ref>
	ref class list_impl
	:	public _STLCLR IList<_Value_t>
	{	// bidirectional linked list of elements
public:
	// types
	typedef list_impl<_Value_t, _Is_ref> _Mytype_t;
	typedef _STLCLR IList<_Value_t> _Mycont_it;
	typedef list_node<_Value_t> _Mynode_t;
	typedef cli::array<_Value_t> _Myarray_t;
	typedef System::Collections::Generic::IEnumerable<_Value_t> _Myenum_it;
	typedef _Cont_make_value<_Value_t, _Is_ref> _Mymake_t;

	typedef list_node<_Value_t> node_type;

	typedef BidirectionalIterator<_Mytype_t>
		iterator;
	typedef ConstBidirectionalIterator<_Mytype_t>
		const_iterator;
	typedef ReverseBidirectionalIterator<_Mytype_t>
		reverse_iterator;
	typedef ReverseBidirectionalIterator<_Mytype_t>
		const_reverse_iterator;

	typedef int size_type;
	typedef int difference_type;
	typedef _Value_t value_type;
	typedef value_type% reference;
	typedef value_type% const_reference;

	typedef _Mycont_it generic_container;
	typedef value_type generic_value;
	typedef _STLCLR Generic::ContainerBidirectionalIterator<_Value_t>
		generic_iterator;
	typedef _STLCLR Generic::ReverseBidirectionalIterator<_Value_t>
		generic_reverse_iterator;

	typedef _STLCLR BinaryDelegate<value_type, value_type, bool>
		_Valcomp_dt;
	typedef _STLCLR UnaryDelegate<value_type, bool> _Valtest_dt;

	// constants
	static const int _Maxsize = MAX_CONTAINER_SIZE;

	// basics
	list_impl()
		:	_Mysize(0), _Mygen(0)
		{	// construct empty list
		_Myhead = _Buynode();
		}

	list_impl% operator=(list_impl% _Right)
		{	// assign
		if ((Object^)this != %_Right)
			{	// worth doing, do it
			clear();
			insert_node(head_node(),
				_Right.front_node(), _Right.head_node());
			}
		return (*this);
		}

	// constructors
	list_impl(_Mytype_t% _Right)
		:	_Mysize(0), _Mygen(0)
		{	// construct by copying _Right
		_Myhead = _Buynode();
		insert_node(head_node(), _Right.front_node(), _Right.head_node());
		}

	explicit list_impl(size_type _Count)
		:	_Mysize(0), _Mygen(0)
		{	// construct from _Count * value_type()
		_Myhead = _Buynode();
		insert_node(head_node(), _Count, value_type());
		}

	list_impl(size_type _Count, value_type _Val)
		:	_Mysize(0), _Mygen(0)
		{	// construct from _Count * _Val
		_Myhead = _Buynode();
		insert_node(head_node(), _Count, _Val);
		}

	template<typename _InIt_t>
		list_impl(_InIt_t _First, _InIt_t _Last)
		:	_Mysize(0), _Mygen(0)
		{	// construct from [_First, _Last)
		_Myhead = _Buynode();
		_Construct(_First, _Last, _Iter_category(_First));
		}

	template<typename _InIt_t>
		void _Construct(_InIt_t _Count, _InIt_t _Val,
			_Int_iterator_tag%)
		{	// initialize with _Count * _Val
		insert_node(head_node(), (size_type)_Count, (value_type)_Val);
		}

	template<typename _InIt_t>
		void _Construct(_InIt_t _First, _InIt_t _Last,
			input_iterator_tag%)
		{	// initialize with [_First, _Last), input iterators
		for (; _First != _Last; ++_First)
			push_back((value_type)*_First);
		}

	template<typename _InIt_t>
		void _Construct(_InIt_t _First, _InIt_t _Last,
			random_access_iterator_tag%)
		{	// initialize with [_First, _Last), random-access iterators
		if (_Last < _First)
			throw gcnew System::ArgumentOutOfRangeException();
		for (; _First != _Last; ++_First)
			push_back((value_type)*_First);
		}

	list_impl(_Myenum_it^ _Right)
		:	_Mysize(0), _Mygen(0)
		{	// initialize with enumeration
		_Myhead = _Buynode();
		for each (value_type _Val in _Right)
			push_back(_Val);
		}

	// destructor
	~list_impl()
		{	// destroy the object
		clear();
		_Myhead = nullptr;
		_Mysize = 0;
		++_Mygen;
		}

	// accessors
	unsigned long get_generation()
		{	// get underlying container generation
		return (_Mygen);
		}

	node_type^ get_node(iterator _Where)
		{	// get node from valid iterator
		node_type^ _Node = (node_type^)_Where.get_node();

		if (_Node->container() != (System::Object^)this)
			throw gcnew System::InvalidOperationException();
		return (_Node);
		}

	node_type^ front_node()
		{	// return leftmost node in tree
		return (head_node()->_Next);	// avoid usual check
		}

	node_type^ back_node()
		{	// return rightmost node in tree
		return (head_node()->_Prev);	// avoid usual check
		}

	node_type^ head_node()
		{	// get head node
		return (_Myhead);
		}

//	property reference default[/* size_type */];

	property value_type front_item
		{	// get or set first element
		virtual value_type get()
			{	// get first element
			return (front());
			}

		virtual void set(value_type _Val)
			{	// set first element
			front() = _Mymake_t::make_value(_Val);
			}
		};

	property value_type back_item
		{	// get or set last element
		virtual value_type get()
			{	// get last element
			return (back());
			}

		virtual void set(value_type _Val)
			{	// set last element
			back() = _Mymake_t::make_value(_Val);
			}
		};

	reference front()
		{	// get first element of mutable sequence
		if (empty())
			throw gcnew System::NullReferenceException();
		return (front_node()->_Myval);
		}

	reference back()
		{	// get last element of mutable sequence
		if (empty())
			throw gcnew System::NullReferenceException();
		return (back_node()->_Myval);
		}

	// converters
	_Myarray_t^ to_array()
		{	// convert to array
		_Myarray_t^ _Ans = gcnew _Myarray_t(size());
		node_type^ _Node = head_node();

		for (int _Idx = size(); 0 <= --_Idx; )
			{	// copy back to front
			_Node = _Node->prev_node();
			_Ans[_Idx] = _Mymake_t::make_value(_Node->_Myval);
			}
		return (_Ans);
		}

	// iterator generators
	iterator make_iterator(node_type^ _Node)
		{	// return iterator for node
		return (iterator(_Node));
		}

	iterator begin()
		{	// return iterator for beginning of mutable sequence
		return (make_iterator(front_node()));
		}

	iterator end()
		{	// return iterator for end of mutable sequence
		return (make_iterator(head_node()));
		}

	reverse_iterator rbegin()
		{	// return reverse iterator for beginning of mutable sequence
		return (reverse_iterator(end()));
		}

	reverse_iterator rend()
		{	// return reverse iterator for end of mutable sequence
		return (reverse_iterator(begin()));
		}

	// size controllers
//	void reserve(size_type _Capacity);
//	size_type capacity();

	virtual void resize(size_type _Newsize)
		{	// determine new length, padding with value_type elements
		resize(_Newsize, value_type());
		}

	void resize(size_type _Newsize, value_type _Val)
		{	// determine new length, padding with _Val elements
		if (_Newsize < 0)
			throw gcnew System::ArgumentOutOfRangeException();

		if (size() < _Newsize)
			insert_node(head_node(), _Newsize - size(), _Val);
		else
			for (; _Newsize < size(); )
				pop_back();	// discard from end
		}

	size_type size()
		{	// return length of sequence
		return (_Mysize);
		}

	bool empty()
		{	// test if sequence is empty
		return (size() == 0);
		}

	// mutators
	void push_front(value_type _Val)
		{	// insert element at beginning
		insert_node(front_node(), 1, _Val);
		}

	void pop_front()
		{	// erase element at beginning
		if (empty())
			throw gcnew System::InvalidOperationException();
		erase_node(front_node());	// discard from beginning
		}

	void push_back(value_type _Val)
		{	// insert element at end
		insert_node(head_node(), 1, _Val);
		}

	void pop_back()
		{	// erase element at end
		if (empty())
			throw gcnew System::InvalidOperationException();
		erase_node(back_node());	// discard from end
		}

	void assign(size_type _Count, value_type _Val)
		{	// assign _Count * _Val
		clear();
		insert_node(head_node(), _Count, _Val);
		}

	void assign(_STLCLR Generic::IInputIterator<_Value_t>^ _First,
		_STLCLR Generic::IInputIterator<_Value_t>^ _Last)
		{	// assign [_First, _Last)
		if (_First->container() != this)
			clear();

		size_type _Oldsize = size();

		_Insert_safe(front_node(), _First, _Last);
		for (; 0 < _Oldsize; --_Oldsize)
			pop_back();	// discard old stuff
		}

	void assign(_Myenum_it^ _Right)
		{	// initialize with enumeration
		node_type^ _Oldfirst = front_node();

		try
			{	// try to build insert list
			for each (value_type _Val in _Right)
				insert_node(_Oldfirst,	// insert new at beginning
					1, _Val);
			}
		catch (System::Object^)
			{	// failed, discard new stuff
			for (; front_node() != _Oldfirst; )
				pop_front();
			throw;
			}
		for (; _Oldfirst != head_node(); )
			_Oldfirst = erase_node(_Oldfirst);	// discard old stuff
		}

	void assign(System::Collections::IEnumerable^ _Right)
		{	// initialize with enumeration
		node_type^ _Oldfirst = front_node();

		try
			{	// try to build insert list
			for each (value_type _Val in _Right)
				insert_node(_Oldfirst,	// insert new at beginning
					1, _Val);
			}
		catch (System::Object^)
			{	// failed, discard new stuff
			for (; front_node() != _Oldfirst; )
				pop_front();
			throw;
			}
		for (; _Oldfirst != head_node(); )
			_Oldfirst = erase_node(_Oldfirst);	// discard old stuff
		}

	iterator insert(iterator _Where, value_type _Val)
		{	// insert _Val at _Where
		insert_node(get_node(_Where), 1, _Val);