using System;

namespace System.Collections
{
	class Node
	{
		internal Node _prev;
		internal Node _next;
		internal object _data;
		internal bool _valid = true;
	}

	/// <summary>
	/// A double linked list.
	/// </summary>
	/// <remarks>
	/// This class does not invalidate the enumerators when changed except when the
	/// enumerator points to a node that is removed.
	/// </remarks>
	public class DoubleLinkedList
		: ICollection
	{
		private int _count;
		internal Node _head;
		internal Node _tail;

		/// <summary>
		/// Constructs an empty list.
		/// </summary>
		public DoubleLinkedList()
		{
		}

		/// <summary>
		/// Adds an element at the head of the list.
		/// </summary>
		/// <param name="o">The element to be added.</param>
		public void AddHead(object o)
		{
			Node n = new Node();
			n._prev = null;
			if(_head != null)
				_head._prev = n;
			n._next = _head;
			n._data = o;
			_head = n;
			if(_tail == null)
				_tail = n;
			_count++;
		}

		/// <summary>
		/// Adds an element at the back of the list.
		/// </summary>
		/// <param name="o">The element to be added.</param>
		public void AddTail(object o)
		{
			Node n = new Node();
			if(_tail != null)
				_tail._next = n;
			n._prev = _tail;
			n._next = null;
			n._data = o;
			_tail = n;
			if(_head == null)
				_head = n;
			_count++;
		}

		/// <summary>
		/// Gets or sets the first element of the list.
		/// </summary>
		public object Head
		{
			get
			{
				return _head._data;
			}
			set
			{
				_head._data = value;
			}
		}

		/// <summary>
		/// Gets or sets the last element of the list.
		/// </summary>
		public object Tail
		{
			get
			{
				return _tail._data;
			}
			set
			{
				_tail._data = value;
			}
		}

		/// <summary>
		/// Removes the first element of the list.
		/// </summary>
		/// <returns>The data stored at the now-removed head.</returns>
		public object RemoveHead()
		{
			if(_count <= 0)
				throw new InvalidOperationException(
					"Can't remove an element of an empty list");
			if(_head._next != null)
				_head._next._prev = null;
			else
				_tail = null;
			Node n = _head;
			_head = _head._next;
			n._next = null;
			object o = n._data;
			n._data = null;
			n._valid = false;
			_count--;
			return o;
		}

		/// <summary>
		/// Removes the last element of the list.
		/// </summary>
		/// <returns>The data stored at the now-removed tail.</returns>
		public object RemoveTail()
		{
			if(_count <= 0)
				throw new InvalidOperationException(
					"Can't remove an element of an empty list");
			if(_tail._prev != null)
				_tail._prev._next = null;
			else
				_head = null;
			Node n = _tail;
			_tail = _tail._prev;
			n._prev = null;
			object o = n._data;
			n._data = null;
			n._valid = false;
			_count--;
			return o;
		}

		/// <summary>
		/// Removes the element an enumerator points to. Invalidates the enumerator.
		/// </summary>
		/// <param name="i">The enumerator that points to the element that should be removed.
		/// Must be a DoLiLiEnumerator, otherwise the function throws an exception.</param>
		public void RemoveAt(IEnumerator i)
		{
			if(_count <= 0)
				throw new InvalidOperationException(
					"Can't remove an element of an empty list");
			try
			{
				DoLiLiEnumerator e = (DoLiLiEnumerator)i;
				if(e._list != this)
					throw new ArgumentException(
						"Enumerator does not belong to the collection", "i");
				RemoveNode(e._node);
			}
			catch(InvalidCastException e)
			{
				throw new ArgumentException(
					"Enumerator does not belong to the collection", "i", e);
			}
		}

		/// <summary>
		/// Searches and removes a node from the list.
		/// </summary>
		/// <param name="o">The object to remove.</param>
		public void Remove(object o)
		{
			for(Node n = _head; n != null; n = n._next)
			{
				if(n._data == o)
				{
					RemoveNode(n);
					break;
				}
			}
		}

		private void RemoveNode(Node n)
		{
			if(n._next != null)
				n._next._prev = n._prev;
			if(n._prev != null)
				n._prev._next = n._next;
			if(_head == n)
				_head = n._next;
			if(_tail == n)
				_tail = n._prev;
			n._next = null;
			n._prev = null;
			n._data = null;
			n._valid = false;
			_count--;
		}

		#region ICollectionImpl
		/// <summary>
		/// Gets the number of elements in the list.
		/// </summary>
		public int Count
		{
			get
			{
				return _count;
			}
		}

		/// <summary>
		/// Returns true if this list is synchronized (thread-safe).
		/// Always returns false;
		/// </summary>
		public bool IsSynchronized
		{
			get
			{
				return false;
			}
		}

		/// <summary>
		/// Returns an object to synchronize on.
		/// Always returns null.
		/// </summary>
		public object SyncRoot
		{
			get
			{
				return null;
			}
		}

		public void CopyTo(Array array, int index)
		{
			if(array == null)
				throw new ArgumentNullException("array");
			if(index < 0)
				throw new ArgumentOutOfRangeException("index");
			if(array.Rank > 1 || index > array.GetLength(0)
				|| _count > array.GetLength(0)-index)
				throw new ArgumentException();
			// This satisfies the last exception requirement of CopyTo.
			foreach(object o in this)
			{
				array.SetValue(o, index++);
			}
		}
		#endregion

		#region IEnumerableImpl
		/// <summary>
		/// Obtains an enumerator for this list.
		/// </summary>
		/// <returns>An IEnumerator that points to a DoLiLiEnumerator.</returns>
		public IEnumerator GetEnumerator()
		{
			return new DoLiLiEnumerator(this);
		}
		#endregion

		/// <summary>
		/// An enumerator for a double linked list.
		/// </summary>
		public class DoLiLiEnumerator
			: IEnumerator
		{
			internal DoubleLinkedList _list;
			internal Node _node;

			/// <summary>
			/// Constructs a new enumerator for a list.
			/// </summary>
			/// <param name="list">The list to enumerate.</param>
			public DoLiLiEnumerator(DoubleLinkedList list)
			{
				_list = list;
			}

			#region IEnumeratorImpl
			/// <summary>
			/// Gets the element the enumerator points to.
			/// This implementation supports set. This sets the data at the current node.
			/// </summary>
			public object Current
			{
				get
				{
					if(_node == null || !_node._valid)
						throw new InvalidOperationException("Enumerator invalid");
					return _node._data;
				}
				set
				{
					if(_node == null || !_node._valid)
						throw new InvalidOperationException("Enumerator invalid");
					_node._data = value;
				}
			}

			/// <summary>
			/// Advances the enumerator.
			/// </summary>
			/// <returns>true if the enumerator is still valid.</returns>
			public bool MoveNext()
			{
				if(_node == null)
					_node = _list._head;
				else
					_node = _node._next;
				return _node != null;
			}

			/// <summary>
			/// Resets the enumerator to the start of the list.
			/// </summary>
			public void Reset()
			{
				_node = null;
			}
			#endregion
		}
	}
}