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                         LinkedListNode <T> node = first;
 192                         if (node == null)
 193                                 return false;
 194                         do
 195                         {
 196                                 if (value.Equals (node.Value))
 197                                         return true;
 198                                 node = node.forward;
 199                         }
 200                         while (node != first);
 201
 202                         return false;
 203                 }
 204
 205                 public void CopyTo (T [] array, int index)
 206                 {
 207                         if (array == null)
 208                                 throw new ArgumentNullException ("array");
 209                         if ( (uint) index < (uint) array.GetLowerBound (0))
 210                                 throw new ArgumentOutOfRangeException ("index");
 211                         if (array.Rank != 1)
 212                                 throw new ArgumentException ("array", "Array is multidimensional");
 213                         if (array.Length - index + array.GetLowerBound (0) < count)
 214                                 throw new ArgumentException ("number of items exceeds capacity");
 215
 216                         LinkedListNode <T> node = first;
 217                         if (first == null)
 218                                 return;
 219                         do
 220                         {
 221                                 array [index] = node.Value;
 222                                 index++;
 223                                 node = node.forward;
 224                         }
 225                         while (node != first);
 226                 }
 227
 228                 public LinkedListNode <T> Find (T value)
 229                 {
 230                         LinkedListNode <T> node = first;
 231                         if (node == null)
 232                                 return null;
 233                         do
 234                         {
 235                                 if ( (value == null && node.Value == null) ||
 236                                      (value != null && value.Equals (node.Value)) )
 237                                         return node;
 238                                 node = node.forward;
 239                         }
 240                         while (node != first);
 241
 242                         return null;
 243                 }
 244
 245                 public LinkedListNode <T> FindLast (T value)
 246                 {
 247                         LinkedListNode <T> node = first;
 248                         if (node == null)
 249                                 return null;
 250                         do
 251                         {
 252                                 node = node.back;
 253                                 if (value.Equals (node.Value))
 254                                         return node;
 255                         }
 256                         while (node != first);
 257
 258                         return null;
 259                 }
 260
 261                 public Enumerator GetEnumerator ()
 262                 {
 263                         return new Enumerator (this);
 264                 }
 265
 266                 [SecurityPermission (SecurityAction.LinkDemand, Flags=SecurityPermissionFlag.SerializationFormatter)]
 267                 public virtual void GetObjectData (SerializationInfo info, StreamingContext context)
 268                 {
 269                         T [] data = new T [count];
 270                         CopyTo (data, 0);
 271                         info.AddValue (DataArrayKey, data, typeof (T []));
 272                         info.AddValue (VersionKey, version);
 273                 }
 274
 275                 public virtual void OnDeserialization (object sender)
 276                 {
 277                         if (si != null)
 278                         {
 279                                 T [] data = (T []) si.GetValue (DataArrayKey, typeof (T []));
 280                                 if (data != null)
 281                                         foreach (T item in data)
 282                                                 AddLast (item);
 283                                 version = si.GetUInt32 (VersionKey);
 284                                 si = null;
 285                         }
 286                 }
 287
 288                 public bool Remove (T value)
 289                 {
 290                         LinkedListNode <T> node = Find (value);
 291                         if (node == null)
 292                                 return false;
 293                         Remove (node);
 294                         return true;
 295                 }
 296
 297                 public void Remove (LinkedListNode <T> node)
 298                 {
 299                         VerifyReferencedNode (node);
 300                         count--;
 301                         if (count == 0)
 302                                 first = null;
 303
 304                         if (node == first)
 305                                 first = first.forward;
 306
 307                         version++;
 308                         node.Detach ();
 309                 }
 310
 311                 public void RemoveFirst ()
 312                 {
 313                         if (first != null)
 314                                 Remove (first);
 315                 }
 316
 317                 public void RemoveLast ()
 318                 {
 319                         if (first != null)
 320                                 Remove (first.back);
 321                 }
 322
 323                 void ICollection <T>.Add (T value)
 324                 {
 325                         AddLast (value);
 326                 }
 327
 328                 void ICollection.CopyTo (Array array, int index)
 329                 {
 330                         T [] Tarray = array as T [];
 331                         if (Tarray == null)
 332                                 throw new ArgumentException ("array");
 333                         CopyTo (Tarray, index);
 334                 }
 335
 336                 IEnumerator <T> IEnumerable <T>.GetEnumerator ()
 337                 {
 338                         return GetEnumerator ();
 339                 }
 340
 341                 IEnumerator IEnumerable.GetEnumerator ()
 342                 {
 343                         return GetEnumerator ();
 344                 }
 345
 346                 public int Count {
 347                         get { return (int) count; }
 348                 }
 349
 350                 public LinkedListNode <T> First {
 351                         get { return first; }
 352                 }
 353
 354                 public LinkedListNode <T> Last {
 355                         get { return (first != null) ? first.back : null; }
 356                 }
 357
 358                 bool ICollection <T>.IsReadOnly {
 359                         get { return false; }
 360                 }
 361
 362                 bool ICollection.IsSynchronized {
 363                         get { return false; }
 364                 }
 365
 366                 object ICollection.SyncRoot {
 367                         get { return this; }
 368                 }
 369
 370                 [Serializable, StructLayout (LayoutKind.Sequential)]
 371                 public struct Enumerator : IEnumerator <T>, IDisposable, IEnumerator
 372 #if !NET_2_1
 373                         , ISerializable, IDeserializationCallback
 374 #endif
 375                 {
 376                         const String VersionKey = "version";
 377                         const String IndexKey = "index";
 378                         const String ListKey = "list";
 379
 380                         LinkedList <T> list;
 381                         LinkedListNode <T> current;
 382                         int index;
 383                         uint version;
 384 #if !NET_2_1
 385                         SerializationInfo si;
 386
 387                         internal Enumerator (SerializationInfo info, StreamingContext context)
 388                         {
 389                                 si = info;
 390                                 list = (LinkedList <T>) si.GetValue (ListKey, typeof (LinkedList <T>));
 391                                 index = si.GetInt32 (IndexKey);
 392                                 version = si.GetUInt32 (VersionKey);
 393                                 current = null;
 394                         }
 395 #endif
 396
 397                         internal Enumerator (LinkedList <T> parent)
 398                         {
 399 #if !NET_2_1
 400                                 si = null;
 401 #endif
 402                                 this.list = parent;
 403                                 current = null;
 404                                 index = -1;
 405                                 version = parent.version;
 406                         }
 407
 408                         public T Current {
 409                                 get {
 410                                         if (list == null)
 411                                                 throw new ObjectDisposedException (null);
 412                                         if (current == null)
 413                                                 throw new InvalidOperationException ();
 414                                         return current.Value;
 415                                 }
 416                         }
 417
 418                         object IEnumerator.Current {
 419                                 get { return Current; }
 420                         }
 421
 422                         public bool MoveNext ()
 423                         {
 424                                 if (list == null)
 425                                         throw new ObjectDisposedException (null);
 426                                 if (version != list.version)
 427                                         throw new InvalidOperationException ("list modified");
 428
 429                                 if (current == null)
 430                                         current = list.first;
 431                                 else
 432                                 {
 433                                         current = current.forward;
 434                                         if (current == list.first)
 435                                                 current = null;
 436                                 }
 437                                 if (current == null)
 438                                 {
 439                                         index = -1;
 440                                         return false;
 441                                 }
 442                                 ++index;
 443                                 return true;
 444                         }
 445
 446                         void IEnumerator.Reset ()
 447                         {
 448                                 if (list == null)
 449                                         throw new ObjectDisposedException (null);
 450                                 if (version != list.version)
 451                                         throw new InvalidOperationException ("list modified");
 452
 453                                 current = null;
 454                                 index = -1;
 455                         }
 456
 457                         public void Dispose ()
 458                         {
 459                                 if (list == null)
 460                                         throw new ObjectDisposedException (null);
 461                                 current = null;
 462                                 list = null;
 463                         }
 464
 465 #if !NET_2_1
 466                         [SecurityPermission (SecurityAction.LinkDemand, Flags=SecurityPermissionFlag.SerializationFormatter)]
 467                         void ISerializable.GetObjectData (SerializationInfo info, StreamingContext context)
 468                         {
 469                                 if (list == null)
 470                                         throw new ObjectDisposedException (null);
 471                                 info.AddValue (VersionKey, version);
 472                                 info.AddValue (IndexKey, index);
 473                         }
 474
 475                         void IDeserializationCallback.OnDeserialization (object sender)
 476                         {
 477                                 if (si == null)
 478                                         return;
 479
 480                                 if (list.si != null)
 481                                         ( (IDeserializationCallback) list).OnDeserialization (this);
 482
 483                                 si = null;
 484
 485                                 if (version == list.version && index != -1)
 486                                 {
 487                                         LinkedListNode <T> node = list.First;
 488
 489                                         for (int i = 0; i < index; i++)
 490                                                 node = node.forward;
 491
 492                                         current = node;
 493                                 }
 494                         }
 495 #endif
 496                 }
 497         }
 498 }