mcs/class/dlr/Runtime/Microsoft.Scripting.Core/Utils/ReadOnlyCollectionBuilder.cs

   1 /* ****************************************************************************
   2  *
   3  * Copyright (c) Microsoft Corporation.
   4  *
   5  * This source code is subject to terms and conditions of the Apache License, Version 2.0. A
   6  * copy of the license can be found in the License.html file at the root of this distribution. If
   7  * you cannot locate the  Apache License, Version 2.0, please send an email to
   8  * dlr@microsoft.com. By using this source code in any fashion, you are agreeing to be bound
   9  * by the terms of the Apache License, Version 2.0.
  10  *
  11  * You must not remove this notice, or any other, from this software.
  12  *
  13  *
  14  * ***************************************************************************/
  15
  16 #if !FEATURE_CORE_DLR
  17 using Microsoft.Scripting.Ast;
  18 #else
  19 using System.Linq.Expressions;
  20 #endif
  21 #if SILVERLIGHT
  22 using System.Core;
  23 #endif
  24
  25 using System.Collections.Generic;
  26 using System.Collections.ObjectModel;
  27 using System.Dynamic.Utils;
  28
  29 namespace System.Runtime.CompilerServices {
  30     /// <summary>
  31     /// The builder for read only collection.
  32     /// </summary>
  33     /// <typeparam name="T">The type of the collection element.</typeparam>
  34     [Serializable]
  35     [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Naming", "CA1710:IdentifiersShouldHaveCorrectSuffix")]
  36     public sealed class ReadOnlyCollectionBuilder<T> : IList<T>, System.Collections.IList {
  37         private const int DefaultCapacity = 4;
  38
  39         private T[] _items;
  40         private int _size;
  41         private int _version;
  42
  43         [NonSerialized]
  44         private Object _syncRoot;
  45
  46         static readonly T[] _emptyArray = new T[0];
  47
  48         /// <summary>
  49         /// Constructs a ReadOnlyCollectionBuilder.
  50         /// </summary>
  51         public ReadOnlyCollectionBuilder() {
  52             _items = _emptyArray;
  53         }
  54
  55         /// <summary>
  56         /// Constructs a ReadOnlyCollectionBuilder with a given initial capacity.
  57         /// The contents are empty but builder will have reserved room for the given
  58         /// number of elements before any reallocations are required.
  59         /// </summary>
  60         public ReadOnlyCollectionBuilder(int capacity) {
  61             ContractUtils.Requires(capacity >= 0, "capacity");
  62             _items = new T[capacity];
  63         }
  64
  65         /// <summary>
  66         /// Constructs a ReadOnlyCollectionBuilder, copying contents of the given collection.
  67         /// </summary>
  68         /// <param name="collection"></param>
  69         public ReadOnlyCollectionBuilder(IEnumerable<T> collection) {
  70             ContractUtils.Requires(collection != null, "collection");
  71
  72             ICollection<T> c = collection as ICollection<T>;
  73             if (c != null) {
  74                 int count = c.Count;
  75                 _items = new T[count];
  76                 c.CopyTo(_items, 0);
  77                 _size = count;
  78             } else {
  79                 _size = 0;
  80                 _items = new T[DefaultCapacity];
  81
  82                 using (IEnumerator<T> en = collection.GetEnumerator()) {
  83                     while (en.MoveNext()) {
  84                         Add(en.Current);
  85                     }
  86                 }
  87             }
  88         }
  89
  90         /// <summary>
  91         /// Gets and sets the capacity of this ReadOnlyCollectionBuilder
  92         /// </summary>
  93         public int Capacity {
  94             get { return _items.Length; }
  95             set {
  96                 ContractUtils.Requires(value >= _size, "value");
  97
  98                 if (value != _items.Length) {
  99                     if (value > 0) {
 100                         T[] newItems = new T[value];
 101                         if (_size > 0) {
 102                             Array.Copy(_items, 0, newItems, 0, _size);
 103                         }
 104                         _items = newItems;
 105                     } else {
 106                         _items = _emptyArray;
 107                     }
 108                 }
 109             }
 110         }
 111
 112         /// <summary>
 113         /// Returns number of elements in the ReadOnlyCollectionBuilder.
 114         /// </summary>
 115         public int Count {
 116             get { return _size; }
 117         }
 118
 119         #region IList<T> Members
 120
 121         /// <summary>
 122         /// Returns the index of the first occurrence of a given value in the builder.
 123         /// </summary>
 124         /// <param name="item">An item to search for.</param>
 125         /// <returns>The index of the first occurrence of an item.</returns>
 126         public int IndexOf(T item) {
 127             return Array.IndexOf(_items, item, 0, _size);
 128         }
 129
 130         /// <summary>
 131         /// Inserts an item to the <see cref="ReadOnlyCollectionBuilder{T}"/> at the specified index.
 132         /// </summary>
 133         /// <param name="index">The zero-based index at which item should be inserted.</param>
 134         /// <param name="item">The object to insert into the <see cref="ReadOnlyCollectionBuilder{T}"/>.</param>
 135         public void Insert(int index, T item) {
 136             ContractUtils.Requires(index <= _size, "index");
 137
 138             if (_size == _items.Length) {
 139                 EnsureCapacity(_size + 1);
 140             }
 141             if (index < _size) {
 142                 Array.Copy(_items, index, _items, index + 1, _size - index);
 143             }
 144             _items[index] = item;
 145             _size++;
 146             _version++;
 147         }
 148
 149         /// <summary>
 150         /// Removes the <see cref="ReadOnlyCollectionBuilder{T}"/> item at the specified index.
 151         /// </summary>
 152         /// <param name="index">The zero-based index of the item to remove.</param>
 153         public void RemoveAt(int index) {
 154             ContractUtils.Requires(index >= 0 && index < _size, "index");
 155
 156             _size--;
 157             if (index < _size) {
 158                 Array.Copy(_items, index + 1, _items, index, _size - index);
 159             }
 160             _items[_size] = default(T);
 161             _version++;
 162         }
 163
 164         /// <summary>
 165         ///  Gets or sets the element at the specified index.
 166         /// </summary>
 167         /// <param name="index">The zero-based index of the element to get or set.</param>
 168         /// <returns>The element at the specified index.</returns>
 169         public T this[int index] {
 170             get {
 171                 ContractUtils.Requires(index < _size, "index");
 172                 return _items[index];
 173             }
 174             set {
 175                 ContractUtils.Requires(index < _size, "index");
 176                 _items[index] = value;
 177                 _version++;
 178             }
 179         }
 180
 181         #endregion
 182
 183         #region ICollection<T> Members
 184
 185         /// <summary>
 186         /// Adds an item to the <see cref="ReadOnlyCollectionBuilder{T}"/>.
 187         /// </summary>
 188         /// <param name="item">The object to add to the <see cref="ReadOnlyCollectionBuilder{T}"/>.</param>
 189         public void Add(T item) {
 190             if (_size == _items.Length) {
 191                 EnsureCapacity(_size + 1);
 192             }
 193             _items[_size++] = item;
 194             _version++;
 195         }
 196
 197         /// <summary>
 198         /// Removes all items from the <see cref="ReadOnlyCollectionBuilder{T}"/>.
 199         /// </summary>
 200         public void Clear() {
 201             if (_size > 0) {
 202                 Array.Clear(_items, 0, _size);
 203                 _size = 0;
 204             }
 205             _version++;
 206         }
 207
 208         /// <summary>
 209         /// Determines whether the <see cref="ReadOnlyCollectionBuilder{T}"/> contains a specific value
 210         /// </summary>
 211         /// <param name="item">the object to locate in the <see cref="ReadOnlyCollectionBuilder{T}"/>.</param>
 212         /// <returns>true if item is found in the <see cref="ReadOnlyCollectionBuilder{T}"/>; otherwise, false.</returns>
 213         public bool Contains(T item) {
 214             if ((Object)item == null) {
 215                 for (int i = 0; i < _size; i++) {
 216                     if ((Object)_items[i] == null) {
 217                         return true;
 218                     }
 219                 }
 220                 return false;
 221             } else {
 222                 EqualityComparer<T> c = EqualityComparer<T>.Default;
 223                 for (int i = 0; i < _size; i++) {
 224                     if (c.Equals(_items[i], item)) {
 225                         return true;
 226                     }
 227                 }
 228                 return false;
 229             }
 230         }
 231
 232         /// <summary>
 233         /// Copies the elements of the <see cref="ReadOnlyCollectionBuilder{T}"/> to an <see cref="Array"/>,
 234         /// starting at particular <see cref="Array"/> index.
 235         /// </summary>
 236         /// <param name="array">The one-dimensional <see cref="Array"/> that is the destination of the elements copied from <see cref="ReadOnlyCollectionBuilder{T}"/>.</param>
 237         /// <param name="arrayIndex">The zero-based index in array at which copying begins.</param>
 238         public void CopyTo(T[] array, int arrayIndex) {
 239             Array.Copy(_items, 0, array, arrayIndex, _size);
 240         }
 241
 242         bool ICollection<T>.IsReadOnly {
 243             get { return false; }
 244         }
 245
 246         /// <summary>
 247         /// Removes the first occurrence of a specific object from the <see cref="ReadOnlyCollectionBuilder{T}"/>.
 248         /// </summary>
 249         /// <param name="item">The object to remove from the <see cref="ReadOnlyCollectionBuilder{T}"/>.</param>
 250         /// <returns>true if item was successfully removed from the <see cref="ReadOnlyCollectionBuilder{T}"/>;
 251         /// otherwise, false. This method also returns false if item is not found in the original <see cref="ReadOnlyCollectionBuilder{T}"/>.
 252         /// </returns>
 253         public bool Remove(T item) {
 254             int index = IndexOf(item);
 255             if (index >= 0) {
 256                 RemoveAt(index);
 257                 return true;
 258             }
 259
 260             return false;
 261         }
 262
 263         #endregion
 264
 265         #region IEnumerable<T> Members
 266
 267         /// <summary>
 268         /// Returns an enumerator that iterates through the collection.
 269         /// </summary>
 270         /// <returns>A <see cref="IEnumerator{T}"/> that can be used to iterate through the collection.</returns>
 271         public IEnumerator<T> GetEnumerator() {
 272             return new Enumerator(this);
 273         }
 274
 275         #endregion
 276
 277         #region IEnumerable Members
 278
 279         System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() {
 280             return GetEnumerator();
 281         }
 282
 283         #endregion
 284
 285         #region IList Members
 286
 287         bool System.Collections.IList.IsReadOnly {
 288             get { return false; }
 289         }
 290
 291         int System.Collections.IList.Add(object value) {
 292             ValidateNullValue(value, "value");
 293             try {
 294                 Add((T)value);
 295             } catch (InvalidCastException) {
 296                 ThrowInvalidTypeException(value, "value");
 297             }
 298             return Count - 1;
 299         }
 300
 301         bool System.Collections.IList.Contains(object value) {
 302             if (IsCompatibleObject(value)) {
 303                 return Contains((T)value);
 304             } else return false;
 305         }
 306
 307         int System.Collections.IList.IndexOf(object value) {
 308             if (IsCompatibleObject(value)) {
 309                 return IndexOf((T)value);
 310             }
 311             return -1;
 312         }
 313
 314         void System.Collections.IList.Insert(int index, object value) {
 315             ValidateNullValue(value, "value");
 316             try {
 317                 Insert(index, (T)value);
 318             } catch (InvalidCastException) {
 319                 ThrowInvalidTypeException(value, "value");
 320             }
 321         }
 322
 323         bool System.Collections.IList.IsFixedSize {
 324             get { return false; }
 325         }
 326
 327         void System.Collections.IList.Remove(object value) {
 328             if (IsCompatibleObject(value)) {
 329                 Remove((T)value);
 330             }
 331         }
 332
 333         object System.Collections.IList.this[int index] {
 334             get {
 335                 return this[index];
 336             }
 337             set {
 338                 ValidateNullValue(value, "value");
 339
 340                 try {
 341                     this[index] = (T)value;
 342                 } catch (InvalidCastException) {
 343                     ThrowInvalidTypeException(value, "value");
 344                 }
 345             }
 346         }
 347
 348         #endregion
 349
 350         #region ICollection Members
 351
 352         void System.Collections.ICollection.CopyTo(Array array, int index) {
 353             ContractUtils.RequiresNotNull(array, "array");
 354             ContractUtils.Requires(array.Rank == 1, "array");
 355             Array.Copy(_items, 0, array, index, _size);
 356         }
 357
 358         bool System.Collections.ICollection.IsSynchronized {
 359             get { return false; }
 360         }
 361
 362         object System.Collections.ICollection.SyncRoot {
 363             get {
 364                 if (_syncRoot == null) {
 365                     System.Threading.Interlocked.CompareExchange<Object>(ref _syncRoot, new Object(), null);
 366                 }
 367                 return _syncRoot;
 368             }
 369         }
 370
 371         #endregion
 372
 373         /// <summary>
 374         /// Reverses the order of the elements in the entire <see cref="ReadOnlyCollectionBuilder{T}"/>.
 375         /// </summary>
 376         public void Reverse() {
 377             Reverse(0, Count);
 378         }
 379
 380         /// <summary>
 381         /// Reverses the order of the elements in the specified range.
 382         /// </summary>
 383         /// <param name="index">The zero-based starting index of the range to reverse.</param>
 384         /// <param name="count">The number of elements in the range to reverse.</param>
 385         public void Reverse(int index, int count) {
 386             ContractUtils.Requires(index >= 0, "index");
 387             ContractUtils.Requires(count >= 0, "count");
 388
 389             Array.Reverse(_items, index, count);
 390             _version++;
 391         }
 392
 393         /// <summary>
 394         /// Copies the elements of the <see cref="ReadOnlyCollectionBuilder{T}"/> to a new array.
 395         /// </summary>
 396         /// <returns>An array containing copies of the elements of the <see cref="ReadOnlyCollectionBuilder{T}"/>.</returns>
 397         public T[] ToArray() {
 398             T[] array = new T[_size];
 399             Array.Copy(_items, 0, array, 0, _size);
 400             return array;
 401         }
 402
 403         /// <summary>
 404         /// Creates a <see cref="ReadOnlyCollection{T}"/> containing all of the the elements of the <see cref="ReadOnlyCollectionBuilder{T}"/>,
 405         /// avoiding copying the elements to the new array if possible. Resets the <see cref="ReadOnlyCollectionBuilder{T}"/> after the
 406         /// <see cref="ReadOnlyCollection{T}"/> has been created.
 407         /// </summary>
 408         /// <returns>A new instance of <see cref="ReadOnlyCollection{T}"/>.</returns>
 409         public ReadOnlyCollection<T> ToReadOnlyCollection() {
 410             // Can we use the stored array?
 411             T[] items;
 412             if (_size == _items.Length) {
 413                 items = _items;
 414             } else {
 415                 items = ToArray();
 416             }
 417             _items = _emptyArray;
 418             _size = 0;
 419             _version++;
 420
 421             return new TrueReadOnlyCollection<T>(items);
 422         }
 423
 424         private void EnsureCapacity(int min) {
 425             if (_items.Length < min) {
 426                 int newCapacity = DefaultCapacity;
 427                 if (_items.Length > 0) {
 428                     newCapacity = _items.Length * 2;
 429                 }
 430                 if (newCapacity < min) {
 431                     newCapacity = min;
 432                 }
 433                 Capacity = newCapacity;
 434             }
 435         }
 436
 437         private static bool IsCompatibleObject(object value) {
 438             return ((value is T) || (value == null && default(T) == null));
 439         }
 440
 441         private static void ValidateNullValue(object value, string argument) {
 442             if (value == null && !(default(T) == null)) {
 443                 throw new ArgumentException(Strings.InvalidNullValue(typeof(T)), argument);
 444             }
 445         }
 446
 447         private static void ThrowInvalidTypeException(object value, string argument) {
 448             throw new ArgumentException(Strings.InvalidObjectType(value != null ? value.GetType() : (object)"null", typeof(T)), argument);
 449         }
 450
 451         [Serializable]
 452         private class Enumerator : IEnumerator<T>, System.Collections.IEnumerator {
 453             private readonly ReadOnlyCollectionBuilder<T> _builder;
 454             private readonly int _version;
 455
 456             private int _index;
 457             private T _current;
 458
 459             internal Enumerator(ReadOnlyCollectionBuilder<T> builder) {
 460                 _builder = builder;
 461                 _version = builder._version;
 462                 _index = 0;
 463                 _current = default(T);
 464             }
 465
 466             #region IEnumerator<T> Members
 467
 468             public T Current {
 469                 get { return _current; }
 470             }
 471
 472             #endregion
 473
 474             #region IDisposable Members
 475
 476             public void Dispose() {
 477                 GC.SuppressFinalize(this);
 478             }
 479
 480             #endregion
 481
 482             #region IEnumerator Members
 483
 484             object System.Collections.IEnumerator.Current {
 485                 get {
 486                     if (_index == 0 || _index > _builder._size) {
 487                         throw Error.EnumerationIsDone();
 488                     }
 489                     return _current;
 490                 }
 491             }
 492
 493             public bool MoveNext() {
 494                 if (_version == _builder._version) {
 495                     if (_index < _builder._size) {
 496                         _current = _builder._items[_index++];
 497                         return true;
 498                     } else {
 499                         _index = _builder._size + 1;
 500                         _current = default(T);
 501                         return false;
 502                     }
 503                 } else {
 504                     throw Error.CollectionModifiedWhileEnumerating();
 505                 }
 506             }
 507
 508             #endregion
 509
 510             #region IEnumerator Members
 511
 512             void System.Collections.IEnumerator.Reset() {
 513                 if (_version != _builder._version) {
 514                     throw Error.CollectionModifiedWhileEnumerating();
 515                 }
 516                 _index = 0;
 517                 _current = default(T);
 518             }
 519
 520             #endregion
 521         }
 522     }
 523 }