Doubly-Linked List Implementation

/* Foley C# Utilities
 * Copyright (C)2002 Rodney S. Foley
 *  
 * This program is free software; you can 
 * redistribute it and/or modify it under the 
 * terms of the GNU General Public License as 
 * published by the Free Software Foundation; 
 * either version 2 of the License, or (at your 
 * option) any later version.
 * 
 * This program is distributed in the hope that 
 * it will be useful, but WITHOUT ANY WARRANTY; 
 * without even the implied warranty of 
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR 
 * PURPOSE. See the GNU General Public License 
 * for more details.
 * 
 * You should have received a copy of the GNU 
 * General Public License along with this 
 * program; if not, write to: 
 * 
 *		Free Software Foundation, Inc., 
 *		59 Temple Place, Suite 330, 
 *		Boston, MA 02111-1307 USA
 * 
 *					- or -
 * 
 * http://opensource.org/licenses/gpl-license.php
 */

using System;
using System.Collections;

namespace Foley.Utilities.Collections
{
	/// <summary>
	/// A Linked List implementation of the <see cref="IList"/> interface.
	/// </summary>
	/// <remarks>
	/// The <see cref="LinkedList"/> can be used with all objects including null.
	/// <para>This class is not guaranteed to be thread safe.</para>
	/// The <see cref="IEnumerator.MoveNext()"/> method of the <see cref="IEnumerator"/> 
	/// that is returned from <see cref="LinkedList.GetEnumerator"/> is fail-fast.  That 
	/// is, if the <see cref="LinkedList"/> is  modified after the enumerator is created 
	/// it will throw a <see cref="SystemException"/> This behavior cannot be guaranteed, 
	/// and should not be depended on.
	/// </remarks>
	[Serializable]
	public class LinkedList : IList, ICloneable
	{
		#region Private Member Variables
		private Node	headerNode;
		private int		count;
		private int		modifications;
		#endregion

		#region Public Constructors
		/// <summary>
		/// Initializes a new instance of the LinkedList class that is empty.
		/// </summary>
		public LinkedList()
		{
			headerNode = new Node(null, null, null);

			headerNode.NextNode		= headerNode;
			headerNode.PreviousNode	= headerNode;

			count = 0;
		}

		/// <summary>
		/// Initializes a new instance of the LinkedList class that contains 
		/// elements copied from the specified collection.
		/// </summary>
		/// <param name="collection">The ICollection whose elements are copied to the new list.</param>
		public LinkedList(ICollection collection) : this()
		{
			AddAll(collection);
		}
		#endregion

		#region Public Member Properties
		/// <summary>
		/// Gets the number of objects contained in the LinkedList.
		/// </summary>
		public virtual int		Count			{get {return count;}}

		/// <summary>
		/// Returns false.
		/// </summary>
		public virtual bool		IsSynchronized	{get {return false;}}

		/// <summary>
		/// Returns a reference to this <see cref="LinkedList"/>.
		/// </summary>
		public virtual object	SyncRoot		{get {return this; }}		

		/// <summary>
		/// Returns false.
		/// </summary>
		public virtual bool		IsFixedSize		{get {return false;}}
		/// <summary>
		/// Returns false.
		/// </summary>
		public virtual bool		IsReadOnly		{get {return false;}}
		
		/// <summary>
		/// Gets or sets the <see cref="object"/> at the specified 
		/// <paramref name="index"/>. [C#] In C#, this property is 
		/// the indexer for the <see cref="LinkedList"/> class.
		/// </summary>
		public virtual object this[int index] 
		{
			get 
			{
				return FindNodeAt(index).CurrentNode;
			} 
			
			set
			{
				FindNodeAt(index).CurrentNode = value;
			}
		}
		#endregion
										 
		#region Public Member Methods
		/// <summary>
		/// Adds an <see cref="object"/> to the end of the 
		/// <see cref="LinkedList"/>.
		/// </summary>
		/// <param name="value">
		/// The <see cref="object"/> to be added to the end of 
		/// the <see cref="LinkedList"/>
		/// </param>
		/// <returns>
		/// The <see cref="LinkedList"/> index at which the 
		/// <paramref name="value"/> was added.
		/// </returns>
		public virtual int Add(object value)
		{
			Insert(count, value);
			
			return (count - 1);
		}

		/// <summary>
		/// Adds the <see cref="object"/>s of an <see cref="ICollection"/> 
		/// to the end of the <see cref="LinkedList"/>.
		/// </summary>
		/// <param name="collection">
		/// The <see cref="ICollection"/> whose <see cref="object"/>s 
		/// should be added to the end of the <see cref="LinkedList"/>.
		/// </param>
		/// <exception cref="System.ArgumentNullException">
		/// The <paramref name="collection"/> is a <c>null</c> reference 
		/// (<c>Nothing</c> in Visual Basic).
		/// </exception>
		public virtual void AddAll(ICollection collection)
		{
			InsertAll(count, collection);
		}

		/// <summary>
		/// Removes all <see cref="object"/>s from the <see cref="LinkedList"/>.
		/// </summary>
		public virtual void Clear()
		{
			modifications++;

			headerNode.NextNode		= headerNode;
			headerNode.PreviousNode	= headerNode;

			count = 0;
		}

		/// <summary>
		/// Creates a shallow copy of the <see cref="LinkedList"/>.
		/// </summary>
		/// <returns>
		/// A shallow copy of the <see cref="LinkedList"/>.
		/// </returns>
		/// <remarks>
		/// If you need a deep copy to be attempted use the
		/// <see cref="LinkedList.Clone(bool)"/> method.
		/// </remarks>
		public virtual object Clone()
		{
			LinkedList	listClone = new LinkedList();
			
			for (Node node = headerNode.NextNode; node != headerNode; node = node.NextNode)
				listClone.Add(node.CurrentNode);
			
			return listClone;
		}

		/// <summary>
		/// Attempts to make a deep copy of the <see cref="LinkedList"/>.
		/// </summary>
		/// <param name="attemptDeepCopy">
		/// If true will attempt to make a deep copy, 
		/// if false it will just return a shallow copy
		/// </param>
		/// <returns>
		/// The newly cloned <see cref="LinkedList"/>.
		/// </returns>
		/// <exception cref="SystemException">
		/// If and <see cref="object"/> in the list is not an 
		/// <see cref="ICloneable"/>.
		/// </exception>
		/// <remarks>
		/// Attempts to make a deep copy if <paramref name="attemptDeepCopy"/> is true.
		/// It will attempt this by checking if an <see cref="object"/> is an 
		/// <see cref="ICloneable"/>, and then defer the process to its Clone method. 
		/// At the first <see cref="object"/> that is not an <see cref="ICloneable"/>
		/// a SystemException will be thrown.
		/// <para>
		/// If a true deep copy is important, please check the <see cref="object"/>s that are
		/// contained in the list API documentation to verify how its Clone method
		/// was implemented.
		/// </para>
		/// </remarks>
		public virtual LinkedList Clone(bool attemptDeepCopy)
		{
			LinkedList listClone;

			if (attemptDeepCopy)
			{
				listClone = new LinkedList();

				object currentObject;

				for (Node node = headerNode.NextNode; node != headerNode; node = node.NextNode)
				{
					currentObject = node.CurrentNode;

					if (currentObject == null)
						listClone.Add(null);
					else if (currentObject is ICloneable)
						listClone.Add(((ICloneable)currentObject).Clone());
					else
						throw new SystemException("The object of type [" + currentObject.GetType() + 
												  "] in the list is not an ICloneable, cannot attempt a deep copy.");
				}	
			}
			else
				listClone = (LinkedList)this.Clone();

			return listClone;
		}

		/// <summary>
		/// Determines whether an <see cref="object"/> is in the <see cref="LinkedList"/>.
		/// </summary>
		/// <param name="value">
		/// <br>The <see cref="object"/> to locate in the <see cref="LinkedList"/>.</br> 
		/// The <see cref="object"/> to locate can be a <c>null</c> reference (<c>Nothing</c> in Visual Basic). 
		/// </param>
		/// <returns>
		/// <c>true</c> if <paramref name="value"/> is found in the <see cref="LinkedList"/>; otherwise, false.
		/// </returns>
		/// <remarks>
		/// This method determines equality by calling <see cref="object.Equals"/>.
		/// </remarks>
		public virtual bool Contains(object value)
		{
			return (0 <= IndexOf(value));
		}

		/// <summary>
		/// Copies the entire <see cref="LinkedList"/> to a compatible one-dimensional <see cref="Array"/>, 
		/// starting at the specified <paramref name="index"/> of the target <paramref name="array"/>.
		/// </summary>
		/// <param name="array">
		/// <br>The one-dimensional <see cref="Array"/> that is the destination of the <see cref="object"/>s</br>
		/// copied from the <see cref="LinkedList"/>. The <see cref="Array"/> must have zero-based indexing.
		/// </param>
		/// <param name="index">
		/// The zero-based <paramref name="index"/> in <paramref name="array"/> at which copying begins.
		/// </param>
		/// <exception cref="System.ArgumentNullException">
		/// The <paramref name="array"/> is a <c>null</c> reference (<c>Nothing</c> in Visual Basic).
		/// </exception>
		/// <exception cref="System.ArgumentOutOfRangeException">
		/// The <paramref name="index"/> is less than zero.
		/// </exception>
		/// <exception cref="System.ArgumentException">
		/// The <paramref name="array"/> is multidimensional.
		/// <p>-or-</p>
		/// The <paramref name="index"/> is equal to or greater than the length of <paramref name="array"/>.
		/// <p>-or-</p>
		/// <br>The number of <see cref="object"/>s in the <see cref="LinkedList"/> is greater than</br>
		/// the available space from <paramref name="index"/> to the end of the destination <paramref name="array"/>.
		/// </exception>
		public virtual void CopyTo(Array array, int index)
		{	
			if (array != null)
			{	
				if (0 <= index)
				{	
					if (array.Rank == 1)
					{	
						if (count <= (array.Length - index))
						{
							if (index < array.Length)
							{	
								for (int i = index, j = 0;j < count; i++, j++)
									array.SetValue(FindNodeAt(j).CurrentNode, i);
							}
							else
								throw new ArgumentException("index is equal to or greater than the length of array.", "index");
						}
						else
							throw new ArgumentException("The number of elements is greater than the available space from index in the destination array.", "array");
					}
					else
						throw new ArgumentException("Multidimensional array", "array");
				}
				else
					throw new ArgumentOutOfRangeException("index", index, "less than zero");
			}
			else
				throw new ArgumentNullException("array");
		}

		/// <summary>
		/// Returns an enumerator for the entire <see cref="LinkedList"/>.
		/// </summary>
		/// <returns>
		/// An <see cref="IEnumerator"/> for the entire <see cref="LinkedList"/>.
		/// </returns>
		public virtual IEnumerator GetEnumerator()
		{
			return new LinkedListEnumerator(this);
		}

		/// <summary>
		/// Searches for the specified <see cref="object"/> and returns the zero-based 
		/// index of the first occurrence within the entire <see cref="LinkedList"/>.
		/// </summary>
		/// <param name="value">
		/// The <see cref="object"/> to locate in the <see cref="LinkedList"/>.
		/// </param>
		/// <returns>
		/// The zero-based index of the first occurrence of <paramref name="value"/> within the entire 
		/// <see cref="LinkedList"/>, if found; otherwise, -1.
		/// </returns>
		public virtual int IndexOf(object value)
		{
			int currentIndex = 0;

			if (value == null) 
			{
				for (Node node = headerNode.NextNode; node != headerNode; node = node.NextNode)
				{
					if (node.CurrentNode == null)
						break;

					currentIndex++;
				}
			} 
			else 
			{
				for (Node node = headerNode.NextNode; node != headerNode; node = node.NextNode)
				{
					if (value.Equals(node.CurrentNode))
						break;

					currentIndex++;
				}
			}

			if (count <= currentIndex)
				currentIndex = -1;

			return currentIndex;
		}

		/// <summary>
		/// Inserts an <see cref="object"/> into the <see cref="LinkedList"/> 
		/// at the specified <paramref name="index"/>.
		/// </summary>
		/// <param name="index">
		/// The zero-based <paramref name="index"/> at which 
		/// <paramref name="value"/> should be inserted.
		/// </param>
		/// <param name="value">
		/// The <see cref="object"/> to insert.
		/// </param>
		public virtual void Insert(int index, object value)
		{
			Node node;

			if (index == count)
				node = new Node(value, headerNode, headerNode.PreviousNode);
			else
			{
				Node tmp = FindNodeAt(index);

				node = new Node(value, tmp, tmp.PreviousNode);
			}

			node.PreviousNode.NextNode = node;
			node.NextNode.PreviousNode = node;
			
			count++;
			modifications++;
		}

		/// <summary>
		/// Inserts all the <see cref="object"/>s of an <see cref="ICollection"/> starting at a
		/// index in the <see cref="LinkedList"/>. 
		/// </summary>
		/// <param name="index">
		/// The index in the <see cref="LinkedList"/> to starting inserting the
		/// objects of the provided <see cref="ICollection"/>.
		/// </param>
		/// <param name="collection">
		/// The <see cref="ICollection"/> whose objects should be inserted 
		/// to the <see cref="LinkedList"/> starting at the provided index.
		/// </param>
		/// <exception cref="System.ArgumentNullException">
		/// The collection is a null reference (Nothing in Visual Basic).
		/// </exception>
		/// <exception cref="System.ArgumentOutOfRangeException">
		/// The index is less than zero.
		/// </exception>
		public virtual void InsertAll(int index, ICollection collection)
		{
			if (collection != null)
			{
				if (0 < collection.Count)
				{
					modifications++;

					Node startingNode = (index == count ? headerNode : FindNodeAt(index));
					Node previousNode = startingNode.PreviousNode;
				
					foreach (object obj in collection)
					{
						Node node				= new Node(obj, startingNode, previousNode);
						previousNode.NextNode	= node;
						previousNode			= node;
					}
				
					startingNode.PreviousNode = previousNode;

					count += collection.Count;						
				}
				else
					throw new ArgumentOutOfRangeException("index", index, "less than zero");
			}
			else
				throw new ArgumentNullException("collection");
		}

		/// <summary>
		/// Removes the first occurrence of a specific <see cref="object"/> 
		/// from the <see cref="LinkedList"/>.
		/// </summary>
		/// <param name="value">
		/// The <see cref="object"/> to remove from the <see cref="LinkedList"/>.
		/// </param>
		public virtual void Remove(object value)
		{	
			if (value == null) 
			{	
				for (Node node = headerNode.NextNode; node != headerNode; node = node.NextNode)
					if (node.CurrentNode == null) 
						Remove(node);
			} 
			else 
			{
				for (Node node = headerNode.NextNode; node != headerNode; node = node.NextNode)
					if (value.Equals(node.CurrentNode)) 
						Remove(node);
			}
		}

		/// <summary>
		/// Removes the <see cref="object"/> at the specified 
		/// <paramref name="index"/> of the <see cref="LinkedList"/>.
		/// </summary>
		/// <param name="index">
		/// The zero-based <paramref name="index"/> of the 
		/// <see cref="object"/> to remove.
		/// </param>
		public virtual void RemoveAt(int index)
		{
			Remove(FindNodeAt(index));
		}
		#endregion

		#region Private Member Methods
		/// <summary>
		/// Returns the <see cref="Node"/> at the provided <paramref name="index"/>.
		/// </summary>
		/// <param name="index">
		/// The zero-based <paramref name="index"/> of the <see cref="Node"/>.
		/// </param>
		/// <returns>
		/// The <see cref="Node"/> at the provided <paramref name="index"/>.
		/// </returns>
		/// <exception cref="IndexOutOfRangeException">
		/// If the <paramref name="index"/> is invalid.
		/// </exception>
		private Node FindNodeAt(int index) 
		{
			if (index < 0 || count <= index)
				throw new IndexOutOfRangeException("Attempted to access index " + index + 
												   ", while the total count is " + count + ".");

			Node node = headerNode;

			if (index < (count / 2)) 
			{
				for (int i = 0; i <= index; i++)
					node = node.NextNode;
			} 
			else 
			{
				for (int i = count; i > index; i--)
					node = node.PreviousNode;
			}

			return node;
		}

		/// <summary>
		/// Removes the <see cref="Node"/> from the <see cref="LinkedList"/>.
		/// </summary>
		/// <param name="value">
		/// </param>
		/// <remarks>
		/// This removal adjusts the remaining <see cref="Node"/> accordingly.
		/// </remarks>
		private void Remove(Node value)
		{
			if (value != headerNode)
			{				
				value.PreviousNode.NextNode = value.NextNode;
				value.NextNode.PreviousNode = value.PreviousNode;
			
				count--;
				modifications++;
			}
		}
		#endregion

		#region Private Member Classes
		[Serializable]
		private class Node
		{
			#region Private Member Variables
			private object	currentNode;
			private Node	nextNode;
			private Node	previousNode;
			#endregion

			#region Public Constructor
			public Node(object currentNode, Node nextNode, Node previousNode)
			{
				this.currentNode	= currentNode;
				this.nextNode		= nextNode;
				this.previousNode	= previousNode;
			}
			#endregion

			#region Public Member Properties
			public object CurrentNode
			{
				get
				{
					return currentNode;
				}

				set
				{
					currentNode = value;
				}
			}

			public Node NextNode
			{
				get
				{
					return nextNode;
				}

				set
				{
					nextNode = value;
				}
			}

			public Node PreviousNode
			{
				get
				{
					return previousNode;
				}

				set
				{
					previousNode = value;
				}
			}
			#endregion
		}

		[Serializable]
		private class LinkedListEnumerator : IEnumerator
		{
			#region Private Member Variables
			private LinkedList	linkedList;
			private int			validModificationCount;
			private Node		currentNode;
			#endregion

			#region Public Constructor
			public LinkedListEnumerator(LinkedList linkedList)
			{
				this.linkedList			= linkedList;
				validModificationCount	= linkedList.modifications;
				currentNode				= linkedList.headerNode;
			}
			#endregion

			#region Public Member Properties
			public object Current
			{
				get
				{
					return currentNode.CurrentNode;
				}
			}
			#endregion

			#region Public Member Methods
			public void Reset()
			{
				currentNode				= linkedList.headerNode;
			}

			public bool MoveNext()
			{
				bool moveSuccessful = false;

				if (validModificationCount != linkedList.modifications)
					throw new SystemException("A concurrent modification occured to the LinkedList while accessing it through it's enumerator.");

				currentNode = currentNode.NextNode;

				if (currentNode != linkedList.headerNode)
					moveSuccessful = true;

				return moveSuccessful;
			}
			#endregion
		}
		#endregion
	}
}