#region License
/*
* Copyright 2002-2005 the original author or authors.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
#endregion
#region Imports
using System;
using System.Collections;
#endregion
namespace Spring.Collections{
/// <summary>
/// Simple linked list implementation.
/// </summary>
/// <author>Simon White</author>
[Serializable]
public class LinkedList : IList
{
private int _nodeIndex;
private Node _rootNode;
private int _modId;
#region Constructors
/// <summary>
/// Creates a new instance of the
/// <see cref="Spring.Collections.LinkedList"/> class.
/// </summary>
public LinkedList()
{
_rootNode = new Node(null, null, null);
_rootNode.PreviousNode = _rootNode;
_rootNode.NextNode = _rootNode;
}
/// <summary>
/// Creates a new instance of the
/// <see cref="Spring.Collections.LinkedList"/> class that contains all
/// elements of the specified list.
/// </summary>
/// <param name="list">
/// A list of elements that defines the initial contents.
/// </param>
public LinkedList(IList list) : this()
{
AddAll(list);
}
#endregion
#region IList Members
/// <summary>
/// Is list read only?
/// </summary>
/// <value>
/// <see langword="true"/> if the list is read only.
/// </value>
public bool IsReadOnly
{
get { return false; }
}
/// <summary>
/// Returns the node at the specified index.
/// </summary>
/// <remarks>
/// <p>
/// This is the indexer for the
/// <see cref="Spring.Collections.LinkedList"/> class.
/// </p>
/// </remarks>
/// <seealso cref="GetNode(int)"/>
public object this[int index]
{
get { return GetNode(index).Value; }
set { GetNode(index).Value = value; }
}
/// <summary>
/// Removes the object at the specified index.
/// </summary>
/// <param name="index">The lookup index.</param>
/// <exception cref="System.ArgumentOutOfRangeException">
/// If the specified <paramref name="index"/> is greater than the
/// number of objects within the list.
/// </exception>
public void RemoveAt(int index)
{
CheckUpdateState();
RemoveNode(GetNode(index));
}
/// <summary>
/// Inserts an object at the specified index.
/// </summary>
/// <param name="index">The lookup index.</param>
/// <param name="value">The object to be inserted.</param>
/// <exception cref="System.ArgumentOutOfRangeException">
/// If the specified <paramref name="index"/> is greater than the
/// number of objects within the list.
/// </exception>
public void Insert(int index, object value)
{
CheckUpdateState();
Node node = null;
if (index == _nodeIndex)
{
node = new Node(value, _rootNode.PreviousNode, _rootNode);
}
else
{
Node insert = GetNode(index);
node = new Node(value, insert.PreviousNode, insert);
}
node.PreviousNode.NextNode = node;
node.NextNode.PreviousNode = node;
_nodeIndex++;
_modId++;
}
/// <summary>
/// Removes the first instance of the specified object found.
/// </summary>
/// <param name="value">The object to remove</param>
public void Remove(object value)
{
CheckUpdateState();
NodeHolder nh = GetNode(value);
RemoveNode(nh.Node);
}
/// <summary>
/// Returns <see langword="true"/> if this list contains the specified
/// element.
/// </summary>
/// <param name="value">The element to look for.</param>
/// <returns>
/// <see langword="true"/> if this list contains the specified element.
/// </returns>
public bool Contains(object value)
{
return GetNode(value) != null;
}
/// <summary>
/// Removes all objects from the list.
/// </summary>
public void Clear()
{
_rootNode = new Node(null, null, null);
_nodeIndex = 0;
_modId++;
}
/// <summary>
/// Returns the index of the first instance of the specified
/// <paramref name="value"/> found.
/// </summary>
/// <param name="value">The object to search for</param>
/// <returns>
/// The index of the first instance found, or -1 if the element was not
/// found.
/// </returns>
public int IndexOf(object value)
{
NodeHolder nh = GetNode(value);
if (nh == null)
{
return -1;
}
return nh.Index;
}
/// <summary>
/// Adds the specified object to the end of the list.
/// </summary>
/// <param name="value">The object to add</param>
/// <returns>The index that the object was added at.</returns>
public int Add(object value)
{
Insert(_nodeIndex, value);
return _nodeIndex - 1;
}
/// <summary>
/// Adds all of the elements of the supplied
/// <paramref name="elements"/>list to the end of this list.
/// </summary>
/// <param name="elements">The list of objects to add.</param>
public void AddAll(IList elements)
{
foreach (object obj in elements)
{
Add(obj);
}
}
/// <summary>
/// Is the list a fixed size?
/// </summary>
/// <value>
/// <see langword="true"/> if the list is a fixed size list.
/// </value>
public bool IsFixedSize
{
get { return false; }
}
#endregion
#region Private Methods
/// <summary>
/// Checks whether the list can be modified.
/// </summary>
/// <exception cref="System.NotSupportedException">
/// If the list cannot be modified.
/// </exception>
private void CheckUpdateState()
{
if (IsReadOnly || IsFixedSize)
{
throw new NotSupportedException("LinkedList cannot be modified.");
}
}
/// <summary>
/// Validates the specified index.
/// </summary>
/// <param name="index">The lookup index.</param>
/// <exception cref="System.ArgumentOutOfRangeException">
/// If the index is invalid.
/// </exception>
private void ValidateIndex(int index)
{
if (index < 0 || index >= _nodeIndex)
{
throw new ArgumentOutOfRangeException("index");
}
}
/// <summary>
/// Returns the node at the specified index.
/// </summary>
/// <param name="index">The lookup index.</param>
/// <returns>The node at the specified index.</returns>
/// <exception cref="System.ArgumentOutOfRangeException">
/// If the specified <paramref name="index"/> is greater than the
/// number of objects within the list.
/// </exception>
private Node GetNode(int index)
{
ValidateIndex(index);
Node node = _rootNode;
for (int i = 0; i <= index; i++)
{
node = node.NextNode;
}
return node;
}
/// <summary>
/// Returns the node (and index) of the first node that contains
/// the specified value.
/// </summary>
/// <param name="value">The value to search for.</param>
/// <returns>
/// The node, or <see langword="null"/> if not found.
/// </returns>
private NodeHolder GetNode(object value)
{
int i = 0;
if (value == null)
{
for (Node n = _rootNode.NextNode; n != _rootNode; n = n.NextNode)
{
if (n.Value == null)
{
return new NodeHolder(n, i);
}
i++;
}
}
else
{
for (Node n = _rootNode.NextNode; n != _rootNode; n = n.NextNode)
{
if (value.Equals(n.Value))
{
return new NodeHolder(n, i);
}
i++;
}
}
return null;
}
/// <summary>
/// Removes the specified node.
/// </summary>
/// <param name="node">The node to be removed.</param>
private void RemoveNode(Node node)
{
Node previousNode = node.PreviousNode;
previousNode.NextNode = node.NextNode;
node.NextNode.PreviousNode = previousNode;
node.PreviousNode = null;
node.NextNode = null;
_nodeIndex--;
_modId++;
}
#endregion
#region ICollection Members
/// <summary>
/// Returns <see langword="true"/> if the list is synchronized across
/// threads.
/// </summary>
/// <remarks>
/// <note>
/// This implementation <b>always</b> returns <see langword="false"/>.
/// </note>
/// <p>
/// Note that enumeration is inherently not thread-safe. Use the
/// <see cref="SyncRoot"/> to lock the object during enumeration.
/// </p>
/// </remarks>
public bool IsSynchronized
{
get { return false; }
}
/// <summary>
/// The number of objects within the list.
/// </summary>
public int Count
{
get { return _nodeIndex; }
}
/// <summary>
/// Copies the elements in this list to an array.
/// </summary>
/// <remarks>
/// <p>
/// The type of array needs to be compatible with the objects in this
/// list, obviously.
/// </p>
/// </remarks>
/// <param name="array">
/// An array that will be the target of the copy operation.
/// </param>
/// <param name="index">
/// The zero-based index where copying will start.
/// </param>
/// <exception cref="System.ArgumentNullException">
/// If the supplied <paramref name="array"/> is <see langword="null"/>.
/// </exception>
/// <exception cref="System.ArgumentOutOfRangeException">
/// If the supplied <paramref name="index"/> is less than zero
/// or is greater than the length of <paramref name="array"/>.
/// </exception>
/// <exception cref="System.ArgumentException">
/// If the supplied <paramref name="array"/> is of insufficient size.
/// </exception>
public void CopyTo(Array array, int index)
{
if (array == null)
{
throw new ArgumentNullException("array");
}
if ((index < 0) || (index > array.Length))
{
throw new ArgumentOutOfRangeException("index", String.Format("Index {0} is out of range.", index));
}
if ((array.Length - index) < this._nodeIndex)
{
throw new ArgumentException("Array is of insufficient size.");
}
Node node = this._rootNode;
for (int i = 0, pos = index; i < this._nodeIndex; i++, pos++)
{
node = node.NextNode;
array.SetValue(node.Value, pos);
}
}
/// <summary>
/// An object that can be used to synchronize this
/// <see cref="Spring.Collections.LinkedList"/> to make it thread-safe.
/// </summary>
/// <value>
/// An object that can be used to synchronize this
/// <see cref="Spring.Collections.LinkedList"/> to make it thread-safe.
/// </value>
public object SyncRoot
{
get { return this; }
}
#endregion
#region IEnumerable Members
/// <summary>
/// Gets an enumerator for the elements in the
/// <see cref="Spring.Collections.LinkedList"/>.
/// </summary>
/// <remarks>
/// <p>
/// Enumerators are fail fast.
/// </p>
/// </remarks>
/// <returns>
/// An <see cref="System.Collections.IEnumerator"/> over the elements
/// in the <see cref="Spring.Collections.LinkedList"/>.
/// </returns>
public IEnumerator GetEnumerator()
{
return new LinkedListEnumerator(this);
}
#endregion
#region Inner Classes
[Serializable]
private class Node
{
private object _value;
private Node _next;
private Node _previous;
public object Value
{
get { return _value; }
set { _value = value; }
}
public Node NextNode
{
get { return _next; }
set { this._next = value; }
}
public Node PreviousNode
{
get { return _previous; }
set { this._previous = value; }
}
public Node(object val, Node previous, Node next)
{
this._value = val;
this._next = next;
this._previous = previous;
}
}
private class NodeHolder
{
private int _index;
private Node _node;
public int Index
{
get { return _index; }
}
public Node Node
{
get { return _node; }
}
public NodeHolder(Node node, int index)
{
this._node = node;
this._index = index;
}
}
private class LinkedListEnumerator : IEnumerator
{
private LinkedList _ll;
private Node _current;
private int _modId;
public object Current
{
get { return _current.Value; }
}
public LinkedListEnumerator(LinkedList ll)
{
this._ll = ll;
this._modId = ll._modId;
this._current = _ll._rootNode;
}
public bool MoveNext()
{
if (this._modId != this._ll._modId)
{
throw new InvalidOperationException("LinkedList has been modified.");
}
_current = _current.NextNode;
return (_current == _ll._rootNode ? false : true);
}
public void Reset()
{
_current = _ll._rootNode;
}
}
#endregion
}
}
|