mcs/class/System.Threading.Tasks.Dataflow/CoreFxSources/Internal/ImmutableList.cs

   1 // Copyright (c) Microsoft. All rights reserved.
   2 // Licensed under the MIT license. See LICENSE file in the project root for full license information.
   3
   4 // =+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+
   5 //
   6 // ImmutableList.cs
   7 //
   8 //
   9 // An immutable data structure that supports adding, removing, and enumerating elements.
  10 //
  11 // =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
  12
  13 using System.Collections.Generic;
  14 using System.Diagnostics.Contracts;
  15 using System.Diagnostics;
  16
  17 namespace System.Threading.Tasks.Dataflow.Internal
  18 {
  19     /// <summary>Provides a simple, immutable list.</summary>
  20     /// <typeparam name="T">Specifies the type of the data stored in the list.</typeparam>
  21     [DebuggerDisplay("Count={Count}")]
  22     [DebuggerTypeProxy(typeof(EnumerableDebugView<>))]
  23     internal sealed class ImmutableList<T> : IEnumerable<T>
  24     {
  25         /// <summary>An empty list.</summary>
  26         private readonly static ImmutableList<T> _empty = new ImmutableList<T>();
  27         /// <summary>The immutable data in this list instance.</summary>
  28         private readonly T[] _array;
  29
  30         /// <summary>Gets the empty list.</summary>
  31         public static ImmutableList<T> Empty { get { return _empty; } }
  32
  33         /// <summary>Initializes the immutable list to be empty.</summary>
  34         private ImmutableList() : this(new T[0]) { }
  35
  36         /// <summary>Initializes the immutable list with the specified elements.</summary>
  37         /// <param name="elements">The element array to use for this list's data.</param>
  38         private ImmutableList(T[] elements)
  39         {
  40             Contract.Requires(elements != null, "List requires an array to wrap.");
  41             _array = elements;
  42         }
  43
  44         /// <summary>Creates a new immutable list from this list and the additional element.</summary>
  45         /// <param name="item">The item to add.</param>
  46         /// <returns>The new list.</returns>
  47         public ImmutableList<T> Add(T item)
  48         {
  49             // Copy the elements from this list and the item
  50             // to a new list that's returned.
  51             var newArray = new T[_array.Length + 1];
  52             Array.Copy(_array, 0, newArray, 0, _array.Length);
  53             newArray[newArray.Length - 1] = item;
  54             return new ImmutableList<T>(newArray);
  55         }
  56
  57         /// <summary>Creates a new immutable list from this list and without the specified element.</summary>
  58         /// <param name="item">The item to remove.</param>
  59         /// <returns>The new list.</returns>
  60         public ImmutableList<T> Remove(T item)
  61         {
  62             // Get the index of the element.  If it's not in the list, just return this list.
  63             int index = Array.IndexOf(_array, item);
  64             if (index < 0) return this;
  65
  66             // It's in the list, so if it's the only one, just return the empty list
  67             if (_array.Length == 1) return Empty;
  68
  69             // Otherwise, copy the other elements to a new list that's returned.
  70             var newArray = new T[_array.Length - 1];
  71             Array.Copy(_array, 0, newArray, 0, index);
  72             Array.Copy(_array, index + 1, newArray, index, _array.Length - index - 1);
  73             return new ImmutableList<T>(newArray);
  74         }
  75
  76         /// <summary>Gets the number of elements in this list.</summary>
  77         public int Count { get { return _array.Length; } }
  78
  79         /// <summary>Gets whether the list contains the specified item.</summary>
  80         /// <param name="item">The item to lookup.</param>
  81         /// <returns>true if the list contains the item; otherwise, false.</returns>
  82         public bool Contains(T item) { return Array.IndexOf(_array, item) >= 0; }
  83
  84         /// <summary>Returns an enumerator that iterates through the collection.</summary>
  85         public IEnumerator<T> GetEnumerator() { return ((IEnumerable<T>)_array).GetEnumerator(); }
  86         /// <summary>Returns an enumerator that iterates through the collection.</summary>
  87         System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() { return this.GetEnumerator(); }
  88     }
  89 }