namespace System.Collections.Generic {
using System;
using System.Diagnostics;
using System.Diagnostics.CodeAnalysis;
#if !SILVERLIGHT
using System.Runtime.Serialization;
#endif
using System.Security.Permissions;
[System.Runtime.InteropServices.ComVisible(false)]
[DebuggerTypeProxy(typeof(System_CollectionDebugView<>))]
[DebuggerDisplay("Count = {Count}")]
#if SILVERLIGHT
public class LinkedList: ICollection, System.Collections.ICollection
#else
[Serializable()]
public class LinkedList: ICollection, System.Collections.ICollection
,ISerializable, IDeserializationCallback
#endif
{
// This LinkedList is a doubly-Linked circular list.
internal LinkedListNode head;
internal int count;
internal int version;
private Object _syncRoot;
#if !SILVERLIGHT
private SerializationInfo siInfo; //A temporary variable which we need during deserialization.
#endif
// names for serialization
const String VersionName = "Version";
const String CountName = "Count";
const String ValuesName = "Data";
public LinkedList() {
}
public LinkedList(IEnumerable collection) {
if (collection==null) {
throw new ArgumentNullException("collection");
}
foreach( T item in collection) {
AddLast(item);
}
}
#if !SILVERLIGHT
protected LinkedList(SerializationInfo info, StreamingContext context) {
siInfo = info;
}
#endif
public int Count {
get { return count;}
}
public LinkedListNode First {
get { return head;}
}
public LinkedListNode Last {
get { return head == null? null: head.prev;}
}
bool ICollection.IsReadOnly {
get { return false; }
}
void ICollection.Add(T value) {
AddLast(value);
}
public LinkedListNode AddAfter(LinkedListNode node, T value) {
ValidateNode(node);
LinkedListNode result = new LinkedListNode(node.list, value);
InternalInsertNodeBefore(node.next, result);
return result;
}
public void AddAfter(LinkedListNode node, LinkedListNode newNode) {
ValidateNode(node);
ValidateNewNode(newNode);
InternalInsertNodeBefore(node.next, newNode);
newNode.list = this;
}
public LinkedListNode AddBefore(LinkedListNode node, T value) {
ValidateNode(node);
LinkedListNode result = new LinkedListNode(node.list, value);
InternalInsertNodeBefore(node, result);
if ( node == head) {
head = result;
}
return result;
}
public void AddBefore(LinkedListNode node, LinkedListNode newNode) {
ValidateNode(node);
ValidateNewNode(newNode);
InternalInsertNodeBefore(node, newNode);
newNode.list = this;
if ( node == head) {
head = newNode;
}
}
public LinkedListNode AddFirst(T value) {
LinkedListNode result = new LinkedListNode(this, value);
if (head == null) {
InternalInsertNodeToEmptyList(result);
}
else {
InternalInsertNodeBefore( head, result);
head = result;
}
return result;
}
public void AddFirst(LinkedListNode node) {
ValidateNewNode(node);
if (head == null) {
InternalInsertNodeToEmptyList(node);
}
else {
InternalInsertNodeBefore( head, node);
head = node;
}
node.list = this;
}
public LinkedListNode AddLast(T value) {
LinkedListNode result = new LinkedListNode(this, value);
if (head== null) {
InternalInsertNodeToEmptyList(result);
}
else {
InternalInsertNodeBefore( head, result);
}
return result;
}
public void AddLast(LinkedListNode node) {
ValidateNewNode(node);
if (head == null) {
InternalInsertNodeToEmptyList(node);
}
else {
InternalInsertNodeBefore( head, node);
}
node.list = this;
}
public void Clear() {
LinkedListNode current = head;
while (current != null ) {
LinkedListNode temp = current;
current = current.Next; // use Next the instead of "next", otherwise it will loop forever
temp.Invalidate();
}
head = null;
count = 0;
version++;
}
public bool Contains(T value) {
return Find(value) != null;
}
public void CopyTo( T[] array, int index) {
if (array == null) {
throw new ArgumentNullException("array");
}
if(index < 0 || index > array.Length) {
throw new ArgumentOutOfRangeException("index",SR.GetString(SR.IndexOutOfRange, index) );
}
if (array.Length - index < Count) {
throw new ArgumentException(SR.GetString(SR.Arg_InsufficientSpace));
}
LinkedListNode node = head;
if (node != null) {
do {
array[index++] = node.item;
node = node.next;
} while (node != head);
}
}
public LinkedListNode Find(T value) {
LinkedListNode node = head;
EqualityComparer c = EqualityComparer.Default;
if (node != null) {
if (value != null) {
do {
if (c.Equals(node.item, value)) {
return node;
}
node = node.next;
} while (node != head);
}
else {
do {
if (node.item == null) {
return node;
}
node = node.next;
} while (node != head);
}
}
return null;
}
public LinkedListNode FindLast(T value) {
if ( head == null) return null;
LinkedListNode last = head.prev;
LinkedListNode node = last;
EqualityComparer c = EqualityComparer.Default;
if (node != null) {
if (value != null) {
do {
if (c.Equals(node.item, value)) {
return node;
}
node = node.prev;
} while (node != last);
}
else {
do {
if (node.item == null) {
return node;
}
node = node.prev;
} while (node != last);
}
}
return null;
}
public Enumerator GetEnumerator() {
return new Enumerator(this);
}
IEnumerator IEnumerable.GetEnumerator() {
return GetEnumerator();
}
public bool Remove(T value) {
LinkedListNode node = Find(value);
if (node != null) {
InternalRemoveNode(node);
return true;
}
return false;
}
public void Remove(LinkedListNode node) {
ValidateNode(node);
InternalRemoveNode(node);
}
public void RemoveFirst() {
if ( head == null) { throw new InvalidOperationException(SR.GetString(SR.LinkedListEmpty)); }
InternalRemoveNode(head);
}
public void RemoveLast() {
if ( head == null) { throw new InvalidOperationException(SR.GetString(SR.LinkedListEmpty)); }
InternalRemoveNode(head.prev);
}
#if !SILVERLIGHT
[SuppressMessage("Microsoft.Security", "CA2123:OverrideLinkDemandsShouldBeIdenticalToBase", Justification = "System.dll is still using pre-v4 security model and needs this demand")]
[SecurityPermissionAttribute(SecurityAction.LinkDemand, Flags = SecurityPermissionFlag.SerializationFormatter)]
public virtual void GetObjectData(SerializationInfo info, StreamingContext context) {
// Customized serialization for LinkedList.
// We need to do this because it will be too expensive to Serialize each node.
// This will give us the flexiblility to change internal implementation freely in future.
if (info==null) {
throw new ArgumentNullException("info");
}
info.AddValue(VersionName, version);
info.AddValue(CountName, count); //This is the length of the bucket array.
if ( count != 0) {
T[] array = new T[Count];
CopyTo(array, 0);
info.AddValue(ValuesName, array, typeof(T[]));
}
}
public virtual void OnDeserialization(Object sender) {
if (siInfo==null) {
return; //Somebody had a dependency on this Dictionary and fixed us up before the ObjectManager got to it.
}
int realVersion = siInfo.GetInt32(VersionName);
int count = siInfo.GetInt32(CountName);
if ( count != 0) {
T[] array = (T[]) siInfo.GetValue(ValuesName, typeof(T[]));
if (array==null) {
throw new SerializationException(SR.GetString(SR.Serialization_MissingValues));
}
for ( int i = 0; i < array.Length; i++) {
AddLast(array[i]);
}
}
else {
head = null;
}
version = realVersion;
siInfo=null;
}
#endif
private void InternalInsertNodeBefore(LinkedListNode node, LinkedListNode newNode) {
newNode.next = node;
newNode.prev = node.prev;
node.prev.next = newNode;
node.prev = newNode;
version++;
count++;
}
private void InternalInsertNodeToEmptyList(LinkedListNode newNode) {
Debug.Assert( head == null && count == 0, "LinkedList must be empty when this method is called!");
newNode.next = newNode;
newNode.prev = newNode;
head = newNode;
version++;
count++;
}
internal void InternalRemoveNode(LinkedListNode node) {
Debug.Assert( node.list == this, "Deleting the node from another list!");
Debug.Assert( head != null, "This method shouldn't be called on empty list!");
if ( node.next == node) {
Debug.Assert(count == 1 && head == node, "this should only be true for a list with only one node");
head = null;
}
else {
node.next.prev = node.prev;
node.prev.next = node.next;
if ( head == node) {
head = node.next;
}
}
node.Invalidate();
count--;
version++;
}
internal void ValidateNewNode(LinkedListNode node) {
if (node == null) {
throw new ArgumentNullException("node");
}
if ( node.list != null) {
throw new InvalidOperationException(SR.GetString(SR.LinkedListNodeIsAttached));
}
}
internal void ValidateNode(LinkedListNode node) {
if (node == null) {
throw new ArgumentNullException("node");
}
if ( node.list != this) {
throw new InvalidOperationException(SR.GetString(SR.ExternalLinkedListNode));
}
}
bool System.Collections.ICollection.IsSynchronized {
get { return false;}
}
object System.Collections.ICollection.SyncRoot {
get {
if( _syncRoot == null) {
System.Threading.Interlocked.CompareExchange