2 // System.Collections.Generic.LinkedListNode
7 // (C) 2005 David Waite (mass@akuma.org)
11 // Copyright (C) 2005 David Waite
13 // Permission is hereby granted, free of charge, to any person obtaining
14 // a copy of this software and associated documentation files (the
15 // "Software"), to deal in the Software without restriction, including
16 // without limitation the rights to use, copy, modify, merge, publish,
17 // distribute, sublicense, and/or sell copies of the Software, and to
18 // permit persons to whom the Software is furnished to do so, subject to
19 // the following conditions:
21 // The above copyright notice and this permission notice shall be
22 // included in all copies or substantial portions of the Software.
24 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35 using System.Runtime.InteropServices;
36 using System.Runtime.Serialization;
37 using System.Security.Permissions;
39 namespace System.Collections.Generic
41 [Serializable, ComVisible (false)]
42 public class LinkedList <T> : ICollection <T>, ICollection, ISerializable, IDeserializationCallback
44 const string DataArrayKey = "DataArray";
45 const string VersionKey = "version";
48 // Internally a circular list - first.back == last
49 internal LinkedListNode <T> first;
50 internal SerializationInfo si;
54 syncRoot = new object ();
59 public LinkedList (IEnumerable <T> collection) : this ()
61 foreach (T item in collection)
65 protected LinkedList (SerializationInfo info, StreamingContext context) : this ()
68 syncRoot = new object ();
71 void VerifyReferencedNode (LinkedListNode <T> node)
74 throw new ArgumentNullException ("node");
76 if (node.List != this)
77 throw new InvalidOperationException ();
80 static void VerifyBlankNode (LinkedListNode <T> newNode)
83 throw new ArgumentNullException ("newNode");
85 if (newNode.List != null)
86 throw new InvalidOperationException ();
89 public LinkedListNode <T> AddAfter (LinkedListNode <T> node, T value)
91 VerifyReferencedNode (node);
92 LinkedListNode <T> newNode = new LinkedListNode <T> (this, value, node, node.forward);
98 public void AddAfter (LinkedListNode <T> node, LinkedListNode <T> newNode)
100 VerifyReferencedNode (node);
101 VerifyBlankNode (newNode);
102 newNode.InsertBetween (node, node.forward, this);
107 public LinkedListNode <T> AddBefore (LinkedListNode <T> node, T value)
109 VerifyReferencedNode (node);
110 LinkedListNode <T> newNode = new LinkedListNode <T> (this, value, node.back, node);
119 public void AddBefore (LinkedListNode <T> node, LinkedListNode <T> newNode)
121 VerifyReferencedNode (node);
122 VerifyBlankNode (newNode);
123 newNode.InsertBetween (node.back, node, this);
131 public void AddFirst (LinkedListNode <T> node)
133 VerifyBlankNode (node);
135 node.SelfReference (this);
137 node.InsertBetween (first.back, first, this);
143 public LinkedListNode <T> AddFirst (T value)
145 LinkedListNode <T> newNode;
147 newNode = new LinkedListNode <T> (this, value);
149 newNode = new LinkedListNode <T> (this, value, first.back, first);
156 public LinkedListNode <T> AddLast (T value)
158 LinkedListNode <T> newNode;
161 newNode = new LinkedListNode <T> (this, value);
165 newNode = new LinkedListNode <T> (this, value, first.back, first);
171 public void AddLast (LinkedListNode <T> node)
173 VerifyBlankNode (node);
176 node.SelfReference (this);
180 node.InsertBetween (first.back, first, this);
192 public bool Contains (T value)
194 LinkedListNode <T> node = first;
199 if (value.Equals (node.Value))
203 while (node != first);
208 public void CopyTo (T [] array, int index)
211 throw new ArgumentNullException ("array");
212 if ( (uint) index < (uint) array.GetLowerBound (0))
213 throw new ArgumentOutOfRangeException ("index");
215 throw new ArgumentException ("array", "Array is multidimensional");
216 if (array.Length - index + array.GetLowerBound (0) < count)
217 throw new ArgumentException ("number of items exceeds capacity");
219 LinkedListNode <T> node = first;
224 array [index] = node.Value;
228 while (node != first);
231 public LinkedListNode <T> Find (T value)
233 LinkedListNode <T> node = first;
238 if ( (value == null && node.Value == null) || value.Equals (node.Value))
242 while (node != first);
247 public LinkedListNode <T> FindLast (T value)
249 LinkedListNode <T> node = first;
255 if (value.Equals (node.Value))
258 while (node != first);
263 public Enumerator GetEnumerator ()
265 return new Enumerator (this);
268 [SecurityPermission (SecurityAction.LinkDemand, Flags=SecurityPermissionFlag.SerializationFormatter)]
269 public virtual void GetObjectData (SerializationInfo info, StreamingContext context)
271 T [] data = new T [count];
273 info.AddValue (DataArrayKey, data, typeof (T []));
274 info.AddValue (VersionKey, version);
277 public void OnDeserialization (object sender)
281 T [] data = (T []) si.GetValue (DataArrayKey, typeof (T []));
283 foreach (T item in data)
285 version = si.GetUInt32 (VersionKey);
290 public bool Remove (T value)
292 LinkedListNode <T> node = Find (value);
299 public void Remove (LinkedListNode <T> node)
301 VerifyReferencedNode (node);
307 first = first.forward;
313 public void RemoveFirst ()
319 public void RemoveLast ()
325 void ICollection <T>.Add (T value)
330 void ICollection.CopyTo (Array array, int index)
332 T [] Tarray = array as T [];
334 throw new ArgumentException ("array");
335 CopyTo (Tarray, index);
338 IEnumerator <T> IEnumerable <T>.GetEnumerator ()
340 return GetEnumerator ();
343 IEnumerator IEnumerable.GetEnumerator ()
345 return GetEnumerator ();
349 get { return (int) count; }
352 public LinkedListNode <T> First {
353 get { return first; }
356 public LinkedListNode <T> Last {
357 get { return (first != null) ? first.back : null; }
360 bool ICollection <T>.IsReadOnly {
361 get { return false; }
364 bool ICollection.IsSynchronized {
365 get { return false; }
368 object ICollection.SyncRoot {
369 get { return syncRoot; }
372 [Serializable, StructLayout (LayoutKind.Sequential)]
373 public struct Enumerator : IEnumerator <T>, IDisposable, IEnumerator, ISerializable, IDeserializationCallback
375 const String VersionKey = "version";
376 const String IndexKey = "index";
377 const String ListKey = "list";
380 LinkedListNode <T> current;
383 SerializationInfo si;
385 internal Enumerator (LinkedList <T> parent)
391 version = parent.version;
394 internal Enumerator (SerializationInfo info, StreamingContext context)
397 list = (LinkedList <T>) si.GetValue (ListKey, typeof (LinkedList <T>));
398 index = si.GetInt32 (IndexKey);
399 version = si.GetUInt32 (VersionKey);
406 throw new ObjectDisposedException (null);
408 throw new InvalidOperationException ();
409 return current.Value;
413 object IEnumerator.Current {
414 get { return Current; }
417 public bool MoveNext ()
420 throw new ObjectDisposedException (null);
421 if (version != list.version)
422 throw new InvalidOperationException ("list modified");
425 current = list.first;
428 current = current.forward;
429 if (current == list.first)
441 void IEnumerator.Reset ()
444 throw new ObjectDisposedException (null);
445 if (version != list.version)
446 throw new InvalidOperationException ("list modified");
452 public void Dispose ()
455 throw new ObjectDisposedException (null);
460 [SecurityPermission (SecurityAction.LinkDemand, Flags=SecurityPermissionFlag.SerializationFormatter)]
461 void ISerializable.GetObjectData (SerializationInfo info, StreamingContext context)
464 throw new ObjectDisposedException (null);
465 info.AddValue (VersionKey, version);
466 info.AddValue (IndexKey, index);
469 void IDeserializationCallback.OnDeserialization (object sender)
475 ( (IDeserializationCallback) list).OnDeserialization (this);
479 if (version == list.version && index != -1)
481 LinkedListNode <T> node = list.First;
483 for (int i = 0; i < index; i++)