mcs/class/System/System.Collections.Generic/LinkedList.cs

   1 //
   2 // System.Collections.Generic.LinkedList
   3 //
   4 // Author:
   5 //    David Waite
   6 //
   7 // (C) 2005 David Waite (mass@akuma.org)
   8 //
   9
  10 //
  11 // Copyright (C) 2005 David Waite
  12 //
  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:
  20 //
  21 // The above copyright notice and this permission notice shall be
  22 // included in all copies or substantial portions of the Software.
  23 //
  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.
  31 //
  32
  33 using System;
  34 using System.Runtime.InteropServices;
  35 using System.Runtime.Serialization;
  36 using System.Security.Permissions;
  37 using System.Diagnostics;
  38
  39 namespace System.Collections.Generic
  40 {
  41         [Serializable, ComVisible (false)]
  42         [DebuggerDisplay ("Count={Count}")]
  43         [DebuggerTypeProxy (typeof (CollectionDebuggerView<>))]
  44         public class LinkedList <T> : ICollection <T>, ICollection, ISerializable, IDeserializationCallback
  45         {
  46                 const string DataArrayKey = "DataArray";
  47                 const string VersionKey = "version";
  48                 uint count, version;
  49
  50                 // Internally a circular list - first.back == last
  51                 internal LinkedListNode <T> first;
  52                 internal SerializationInfo si;
  53
  54                 public LinkedList ()
  55                 {
  56                 }
  57
  58                 public LinkedList (IEnumerable <T> collection)
  59                 {
  60                         foreach (T item in collection)
  61                                 AddLast (item);
  62                 }
  63
  64                 protected LinkedList (SerializationInfo info, StreamingContext context)
  65                 {
  66                         si = info;
  67                 }
  68
  69                 void VerifyReferencedNode (LinkedListNode <T> node)
  70                 {
  71                         if (node == null)
  72                                 throw new ArgumentNullException ("node");
  73
  74                         if (node.List != this)
  75                                 throw new InvalidOperationException ();
  76                 }
  77
  78                 static void VerifyBlankNode (LinkedListNode <T> newNode)
  79                 {
  80                         if (newNode == null)
  81                                 throw new ArgumentNullException ("newNode");
  82
  83                         if (newNode.List != null)
  84                                 throw new InvalidOperationException ();
  85                 }
  86
  87                 public LinkedListNode <T> AddAfter (LinkedListNode <T> node, T value)
  88                 {
  89                         VerifyReferencedNode (node);
  90                         LinkedListNode <T> newNode = new LinkedListNode <T> (this, value, node, node.forward);
  91                         count++;
  92                         version++;
  93                         return newNode;
  94                 }
  95
  96                 public void AddAfter (LinkedListNode <T> node, LinkedListNode <T> newNode)
  97                 {
  98                         VerifyReferencedNode (node);
  99                         VerifyBlankNode (newNode);
 100                         newNode.InsertBetween (node, node.forward, this);
 101                         count++;
 102                         version++;
 103                 }
 104
 105                 public LinkedListNode <T> AddBefore (LinkedListNode <T> node, T value)
 106                 {
 107                         VerifyReferencedNode (node);
 108                         LinkedListNode <T> newNode = new LinkedListNode <T> (this, value, node.back, node);
 109                         count++;
 110                         version++;
 111
 112                         if (node == first)
 113                                 first = newNode;
 114                         return newNode;
 115                 }
 116
 117                 public void AddBefore (LinkedListNode <T> node, LinkedListNode <T> newNode)
 118                 {
 119                         VerifyReferencedNode (node);
 120                         VerifyBlankNode (newNode);
 121                         newNode.InsertBetween (node.back, node, this);
 122                         count++;
 123                         version++;
 124
 125                         if (node == first)
 126                                 first = newNode;
 127                 }
 128
 129                 public void AddFirst (LinkedListNode <T> node)
 130                 {
 131                         VerifyBlankNode (node);
 132                         if (first == null)
 133                                 node.SelfReference (this);
 134                         else
 135                                 node.InsertBetween (first.back, first, this);
 136                         count++;
 137                         version++;
 138                         first = node;
 139                 }
 140
 141                 public LinkedListNode <T> AddFirst (T value)
 142                 {
 143                         LinkedListNode <T> newNode;
 144                         if (first == null)
 145                                 newNode = new LinkedListNode <T> (this, value);
 146                         else
 147                                 newNode = new LinkedListNode <T> (this, value, first.back, first);
 148                         count++;
 149                         version++;
 150                         first = newNode;
 151                         return newNode;
 152                 }
 153
 154                 public LinkedListNode <T> AddLast (T value)
 155                 {
 156                         LinkedListNode <T> newNode;
 157                         if (first == null)
 158                         {
 159                                 newNode = new LinkedListNode <T> (this, value);
 160                                 first = newNode;
 161                         }
 162                         else
 163                                 newNode = new LinkedListNode <T> (this, value, first.back, first);
 164                         count++;
 165                         version++;
 166                         return newNode;
 167                 }
 168
 169                 public void AddLast (LinkedListNode <T> node)
 170                 {
 171                         VerifyBlankNode (node);
 172                         if (first == null)
 173                         {
 174                                 node.SelfReference (this);
 175                                 first = node;
 176                         }
 177                         else
 178                                 node.InsertBetween (first.back, first, this);
 179                         count++;
 180                         version++;
 181                 }
 182
 183                 public void Clear ()
 184                 {
 185                         while (first != null)
 186                                 Remove (first);
 187                 }
 188
 189                 public bool Contains (T value)
 190                 {
 191                         return Find (value) != null;
 192                 }
 193
 194                 public void CopyTo (T [] array, int index)
 195                 {
 196                         if (array == null)
 197                                 throw new ArgumentNullException ("array");
 198                         if ( (uint) index < (uint) array.GetLowerBound (0))
 199                                 throw new ArgumentOutOfRangeException ("index");
 200                         if (array.Rank != 1)
 201                                 throw new ArgumentException ("array", "Array is multidimensional");
 202                         if (array.Length - index + array.GetLowerBound (0) < count)
 203                                 throw new ArgumentException ("number of items exceeds capacity");
 204
 205                         LinkedListNode <T> node = first;
 206                         if (first == null)
 207                                 return;
 208                         do
 209                         {
 210                                 array [index] = node.Value;
 211                                 index++;
 212                                 node = node.forward;
 213                         }
 214                         while (node != first);
 215                 }
 216
 217                 public LinkedListNode<T> Find (T value)
 218                 {
 219                         var node = first;
 220                         if (node == null)
 221                                 return null;
 222
 223                         do {
 224                                 if (value == null) {
 225                                         if (node.Value == null)
 226                                                 return node;
 227                                 } else {
 228                                         if (EqualityComparer<T>.Default.Equals (node.Value, value))
 229                                                 return node;
 230                                 }
 231
 232                                 node = node.forward;
 233                         } while (node != first);
 234
 235                         return null;
 236                 }
 237
 238                 public LinkedListNode<T> FindLast (T value)
 239                 {
 240                         var node = first;
 241                         if (node == null)
 242                                 return null;
 243
 244                         do {
 245                                 node = node.back;
 246
 247                                 if (value == null) {
 248                                         if (node.Value == null)
 249                                                 return node;
 250                                 } else {
 251                                         if (EqualityComparer<T>.Default.Equals (node.Value, value))
 252                                                 return node;
 253                                 }
 254                         } while (node != first);
 255
 256                         return null;
 257                 }
 258
 259                 public Enumerator GetEnumerator ()
 260                 {
 261                         return new Enumerator (this);
 262                 }
 263
 264                 [SecurityPermission (SecurityAction.LinkDemand, Flags=SecurityPermissionFlag.SerializationFormatter)]
 265                 public virtual void GetObjectData (SerializationInfo info, StreamingContext context)
 266                 {
 267                         T [] data = new T [count];
 268                         CopyTo (data, 0);
 269                         info.AddValue (DataArrayKey, data, typeof (T []));
 270                         info.AddValue (VersionKey, version);
 271                 }
 272
 273                 public virtual void OnDeserialization (object sender)
 274                 {
 275                         if (si != null)
 276                         {
 277                                 T [] data = (T []) si.GetValue (DataArrayKey, typeof (T []));
 278                                 if (data != null)
 279                                         foreach (T item in data)
 280                                                 AddLast (item);
 281                                 version = si.GetUInt32 (VersionKey);
 282                                 si = null;
 283                         }
 284                 }
 285
 286                 public bool Remove (T value)
 287                 {
 288                         LinkedListNode <T> node = Find (value);
 289                         if (node == null)
 290                                 return false;
 291                         Remove (node);
 292                         return true;
 293                 }
 294
 295                 public void Remove (LinkedListNode <T> node)
 296                 {
 297                         VerifyReferencedNode (node);
 298                         count--;
 299                         if (count == 0)
 300                                 first = null;
 301
 302                         if (node == first)
 303                                 first = first.forward;
 304
 305                         version++;
 306                         node.Detach ();
 307                 }
 308
 309                 public void RemoveFirst ()
 310                 {
 311                         if (first == null)
 312                                 throw new InvalidOperationException ();
 313
 314                         Remove (first);
 315                 }
 316
 317                 public void RemoveLast ()
 318                 {
 319                         if (first == null)
 320                                 throw new InvalidOperationException ();
 321
 322                         Remove (first.back);
 323                 }
 324
 325                 void ICollection <T>.Add (T value)
 326                 {
 327                         AddLast (value);
 328                 }
 329
 330                 void ICollection.CopyTo (Array array, int index)
 331                 {
 332                         T [] Tarray = array as T [];
 333                         if (Tarray == null)
 334                                 throw new ArgumentException ("array");
 335                         CopyTo (Tarray, index);
 336                 }
 337
 338                 IEnumerator <T> IEnumerable <T>.GetEnumerator ()
 339                 {
 340                         return GetEnumerator ();
 341                 }
 342
 343                 IEnumerator IEnumerable.GetEnumerator ()
 344                 {
 345                         return GetEnumerator ();
 346                 }
 347
 348                 public int Count {
 349                         get { return (int) count; }
 350                 }
 351
 352                 public LinkedListNode <T> First {
 353                         get { return first; }
 354                 }
 355
 356                 public LinkedListNode <T> Last {
 357                         get { return (first != null) ? first.back : null; }
 358                 }
 359
 360                 bool ICollection <T>.IsReadOnly {
 361                         get { return false; }
 362                 }
 363
 364                 bool ICollection.IsSynchronized {
 365                         get { return false; }
 366                 }
 367
 368                 object ICollection.SyncRoot {
 369                         get { return this; }
 370                 }
 371
 372                 [Serializable, StructLayout (LayoutKind.Sequential)]
 373                 public struct Enumerator : IEnumerator <T>, IDisposable, IEnumerator
 374 #if !NET_2_1
 375                         , ISerializable, IDeserializationCallback
 376 #endif
 377                 {
 378                         const String VersionKey = "version";
 379                         const String IndexKey = "index";
 380                         const String ListKey = "list";
 381
 382                         LinkedList <T> list;
 383                         LinkedListNode <T> current;
 384                         int index;
 385                         uint version;
 386 #if !NET_2_1
 387                         SerializationInfo si;
 388
 389                         internal Enumerator (SerializationInfo info, StreamingContext context)
 390                         {
 391                                 si = info;
 392                                 list = (LinkedList <T>) si.GetValue (ListKey, typeof (LinkedList <T>));
 393                                 index = si.GetInt32 (IndexKey);
 394                                 version = si.GetUInt32 (VersionKey);
 395                                 current = null;
 396                         }
 397 #endif
 398
 399                         internal Enumerator (LinkedList <T> parent)
 400                         {
 401 #if !NET_2_1
 402                                 si = null;
 403 #endif
 404                                 this.list = parent;
 405                                 current = null;
 406                                 index = -1;
 407                                 version = parent.version;
 408                         }
 409
 410                         public T Current {
 411                                 get {
 412                                         if (list == null)
 413                                                 throw new ObjectDisposedException (null);
 414                                         if (current == null)
 415                                                 throw new InvalidOperationException ();
 416                                         return current.Value;
 417                                 }
 418                         }
 419
 420                         object IEnumerator.Current {
 421                                 get { return Current; }
 422                         }
 423
 424                         public bool MoveNext ()
 425                         {
 426                                 if (list == null)
 427                                         throw new ObjectDisposedException (null);
 428                                 if (version != list.version)
 429                                         throw new InvalidOperationException ("list modified");
 430
 431                                 if (current == null) {
 432                                         if (index < 0)
 433                                                 current = list.first;
 434                                 } else {
 435                                         current = current.forward;
 436                                         if (current == list.first)
 437                                                 current = null;
 438                                 }
 439
 440                                 if (current == null) {
 441                                         index = int.MaxValue;
 442                                         return false;
 443                                 }
 444
 445                                 ++index;
 446                                 return true;
 447                         }
 448
 449                         void IEnumerator.Reset ()
 450                         {
 451                                 if (list == null)
 452                                         throw new ObjectDisposedException (null);
 453                                 if (version != list.version)
 454                                         throw new InvalidOperationException ("list modified");
 455
 456                                 current = null;
 457                                 index = -1;
 458                         }
 459
 460                         public void Dispose ()
 461                         {
 462                                 if (list == null)
 463                                         throw new ObjectDisposedException (null);
 464                                 current = null;
 465                                 list = null;
 466                         }
 467
 468 #if !NET_2_1
 469                         [SecurityPermission (SecurityAction.LinkDemand, Flags=SecurityPermissionFlag.SerializationFormatter)]
 470                         void ISerializable.GetObjectData (SerializationInfo info, StreamingContext context)
 471                         {
 472                                 if (list == null)
 473                                         throw new ObjectDisposedException (null);
 474                                 info.AddValue (VersionKey, version);
 475                                 info.AddValue (IndexKey, index);
 476                         }
 477
 478                         void IDeserializationCallback.OnDeserialization (object sender)
 479                         {
 480                                 if (si == null)
 481                                         return;
 482
 483                                 if (list.si != null)
 484                                         ( (IDeserializationCallback) list).OnDeserialization (this);
 485
 486                                 si = null;
 487
 488                                 if (version == list.version && index != -1)
 489                                 {
 490                                         LinkedListNode <T> node = list.First;
 491
 492                                         for (int i = 0; i < index; i++)
 493                                                 node = node.forward;
 494
 495                                         current = node;
 496                                 }
 497                         }
 498 #endif
 499                 }
 500         }
 501 }