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

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