mcs/class/Mono.C5/C5/Collections.cs

   1 /*
   2  Copyright (c) 2003-2006 Niels Kokholm and Peter Sestoft
   3  Permission is hereby granted, free of charge, to any person obtaining a copy
   4  of this software and associated documentation files (the "Software"), to deal
   5  in the Software without restriction, including without limitation the rights
   6  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
   7  copies of the Software, and to permit persons to whom the Software is
   8  furnished to do so, subject to the following conditions:
   9
  10  The above copyright notice and this permission notice shall be included in
  11  all copies or substantial portions of the Software.
  12
  13  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  14  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  15  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  16  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  17  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  18  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  19  SOFTWARE.
  20 */
  21
  22 #define IMPROVED_COLLECTION_HASHFUNCTION
  23
  24 using System;
  25 using System.Diagnostics;
  26 using SCG = System.Collections.Generic;
  27 namespace C5
  28 {
  29   /// <summary>
  30   /// A base class for implementing an IEnumerable&lt;T&gt;
  31   /// </summary>
  32   [Serializable]
  33   public abstract class EnumerableBase<T> : SCG.IEnumerable<T>
  34   {
  35     /// <summary>
  36     /// Create an enumerator for this collection.
  37     /// </summary>
  38     /// <returns>The enumerator</returns>
  39     public abstract SCG.IEnumerator<T> GetEnumerator();
  40
  41     /// <summary>
  42     /// Count the number of items in an enumerable by enumeration
  43     /// </summary>
  44     /// <param name="items">The enumerable to count</param>
  45     /// <returns>The size of the enumerable</returns>
  46     [Tested]
  47     protected static int countItems(SCG.IEnumerable<T> items)
  48     {
  49       ICollectionValue<T> jtems = items as ICollectionValue<T>;
  50
  51       if (jtems != null)
  52         return jtems.Count;
  53
  54       int count = 0;
  55
  56       using (SCG.IEnumerator<T> e = items.GetEnumerator())
  57         while (e.MoveNext()) count++;
  58
  59       return count;
  60     }
  61
  62     #region IEnumerable Members
  63
  64     System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
  65     {
  66       return GetEnumerator();
  67     }
  68
  69     #endregion
  70   }
  71
  72
  73   /// <summary>
  74   /// Base class for classes implementing ICollectionValue[T]
  75   /// </summary>
  76   [Serializable]
  77   public abstract class CollectionValueBase<T> : EnumerableBase<T>, ICollectionValue<T>, IShowable
  78   {
  79     #region Event handling
  80     EventBlock<T> eventBlock;
  81     /// <summary>
  82     ///
  83     /// </summary>
  84     /// <value></value>
  85     public virtual EventTypeEnum ListenableEvents { get { return 0; } }
  86
  87     /// <summary>
  88     /// A flag bitmap of the events currently subscribed to by this collection.
  89     /// </summary>
  90     /// <value></value>
  91     public virtual EventTypeEnum ActiveEvents { get { return eventBlock == null ? 0 : eventBlock.events; } }
  92
  93     private void checkWillListen(EventTypeEnum eventType)
  94     {
  95       if ((ListenableEvents & eventType) == 0)
  96         throw new UnlistenableEventException();
  97     }
  98
  99     /// <summary>
 100     /// The change event. Will be raised for every change operation on the collection.
 101     /// </summary>
 102     public virtual event CollectionChangedHandler<T> CollectionChanged
 103     {
 104       add { checkWillListen(EventTypeEnum.Changed); (eventBlock ?? (eventBlock = new EventBlock<T>())).CollectionChanged += value; }
 105       remove
 106       {
 107         checkWillListen(EventTypeEnum.Changed);
 108         if (eventBlock != null)
 109         {
 110           eventBlock.CollectionChanged -= value;
 111           if (eventBlock.events == 0) eventBlock = null;
 112         }
 113       }
 114     }
 115     /// <summary>
 116     /// Fire the CollectionChanged event
 117     /// </summary>
 118     protected virtual void raiseCollectionChanged()
 119     { if (eventBlock != null) eventBlock.raiseCollectionChanged(this); }
 120
 121     /// <summary>
 122     /// The clear event. Will be raised for every Clear operation on the collection.
 123     /// </summary>
 124     public virtual event CollectionClearedHandler<T> CollectionCleared
 125     {
 126       add { checkWillListen(EventTypeEnum.Cleared); (eventBlock ?? (eventBlock = new EventBlock<T>())).CollectionCleared += value; }
 127       remove
 128       {
 129         checkWillListen(EventTypeEnum.Cleared);
 130         if (eventBlock != null)
 131         {
 132           eventBlock.CollectionCleared -= value;
 133           if (eventBlock.events == 0) eventBlock = null;
 134         }
 135       }
 136     }
 137     /// <summary>
 138     /// Fire the CollectionCleared event
 139     /// </summary>
 140     protected virtual void raiseCollectionCleared(bool full, int count)
 141     { if (eventBlock != null) eventBlock.raiseCollectionCleared(this, full, count); }
 142
 143     /// <summary>
 144     /// Fire the CollectionCleared event
 145     /// </summary>
 146     protected virtual void raiseCollectionCleared(bool full, int count, int? offset)
 147     { if (eventBlock != null) eventBlock.raiseCollectionCleared(this, full, count, offset); }
 148
 149     /// <summary>
 150     /// The item added  event. Will be raised for every individual addition to the collection.
 151     /// </summary>
 152     public virtual event ItemsAddedHandler<T> ItemsAdded
 153     {
 154       add { checkWillListen(EventTypeEnum.Added); (eventBlock ?? (eventBlock = new EventBlock<T>())).ItemsAdded += value; }
 155       remove
 156       {
 157         checkWillListen(EventTypeEnum.Added);
 158         if (eventBlock != null)
 159         {
 160           eventBlock.ItemsAdded -= value;
 161           if (eventBlock.events == 0) eventBlock = null;
 162         }
 163       }
 164     }
 165     /// <summary>
 166     /// Fire the ItemsAdded event
 167     /// </summary>
 168     /// <param name="item">The item that was added</param>
 169     /// <param name="count"></param>
 170     protected virtual void raiseItemsAdded(T item, int count)
 171     { if (eventBlock != null) eventBlock.raiseItemsAdded(this, item, count); }
 172
 173     /// <summary>
 174     /// The item removed event. Will be raised for every individual removal from the collection.
 175     /// </summary>
 176     public virtual event ItemsRemovedHandler<T> ItemsRemoved
 177     {
 178       add { checkWillListen(EventTypeEnum.Removed); (eventBlock ?? (eventBlock = new EventBlock<T>())).ItemsRemoved += value; }
 179       remove
 180       {
 181         checkWillListen(EventTypeEnum.Removed);
 182         if (eventBlock != null)
 183         {
 184           eventBlock.ItemsRemoved -= value;
 185           if (eventBlock.events == 0) eventBlock = null;
 186         }
 187       }
 188     }
 189     /// <summary>
 190     /// Fire the ItemsRemoved event
 191     /// </summary>
 192     /// <param name="item">The item that was removed</param>
 193     /// <param name="count"></param>
 194     protected virtual void raiseItemsRemoved(T item, int count)
 195     { if (eventBlock != null) eventBlock.raiseItemsRemoved(this, item, count); }
 196
 197     /// <summary>
 198     /// The item added  event. Will be raised for every individual addition to the collection.
 199     /// </summary>
 200     public virtual event ItemInsertedHandler<T> ItemInserted
 201     {
 202       add { checkWillListen(EventTypeEnum.Inserted); (eventBlock ?? (eventBlock = new EventBlock<T>())).ItemInserted += value; }
 203       remove
 204       {
 205         checkWillListen(EventTypeEnum.Inserted);
 206         if (eventBlock != null)
 207         {
 208           eventBlock.ItemInserted -= value;
 209           if (eventBlock.events == 0) eventBlock = null;
 210         }
 211       }
 212     }
 213     /// <summary>
 214     /// Fire the ItemInserted event
 215     /// </summary>
 216     /// <param name="item">The item that was added</param>
 217     /// <param name="index"></param>
 218     protected virtual void raiseItemInserted(T item, int index)
 219     { if (eventBlock != null) eventBlock.raiseItemInserted(this, item, index); }
 220
 221     /// <summary>
 222     /// The item removed event. Will be raised for every individual removal from the collection.
 223     /// </summary>
 224     public virtual event ItemRemovedAtHandler<T> ItemRemovedAt
 225     {
 226       add { checkWillListen(EventTypeEnum.RemovedAt); (eventBlock ?? (eventBlock = new EventBlock<T>())).ItemRemovedAt += value; }
 227       remove
 228       {
 229         checkWillListen(EventTypeEnum.RemovedAt);
 230         if (eventBlock != null)
 231         {
 232           eventBlock.ItemRemovedAt -= value;
 233           if (eventBlock.events == 0) eventBlock = null;
 234         }
 235       }
 236     }
 237     /// <summary>
 238     /// Fire the ItemRemovedAt event
 239     /// </summary>
 240     /// <param name="item">The item that was removed</param>
 241     /// <param name="index"></param>
 242     protected virtual void raiseItemRemovedAt(T item, int index)
 243     { if (eventBlock != null) eventBlock.raiseItemRemovedAt(this, item, index); }
 244
 245     #region Event support for IList
 246     /// <summary>
 247     ///
 248     /// </summary>
 249     /// <param name="index"></param>
 250     /// <param name="value"></param>
 251     /// <param name="item"></param>
 252     protected virtual void raiseForSetThis(int index, T value, T item)
 253     {
 254       if (ActiveEvents != 0)
 255       {
 256         raiseItemsRemoved(item, 1);
 257         raiseItemRemovedAt(item, index);
 258         raiseItemsAdded(value, 1);
 259         raiseItemInserted(value, index);
 260         raiseCollectionChanged();
 261       }
 262     }
 263     /// <summary>
 264     ///
 265     /// </summary>
 266     /// <param name="i"></param>
 267     /// <param name="item"></param>
 268     protected virtual void raiseForInsert(int i, T item)
 269     {
 270       if (ActiveEvents != 0)
 271       {
 272         raiseItemInserted(item, i);
 273         raiseItemsAdded(item, 1);
 274         raiseCollectionChanged();
 275       }
 276     }
 277
 278     /// <summary>
 279     ///
 280     /// </summary>
 281     /// <param name="item"></param>
 282     protected void raiseForRemove(T item)
 283     {
 284       if (ActiveEvents != 0)
 285       {
 286         raiseItemsRemoved(item, 1);
 287         raiseCollectionChanged();
 288       }
 289     }
 290
 291     /// <summary>
 292     ///
 293     /// </summary>
 294     /// <param name="item"></param>
 295     /// <param name="count"></param>
 296     protected void raiseForRemove(T item, int count)
 297     {
 298       if (ActiveEvents != 0)
 299       {
 300         raiseItemsRemoved(item, count);
 301         raiseCollectionChanged();
 302       }
 303     }
 304
 305     /// <summary>
 306     ///
 307     /// </summary>
 308     /// <param name="index"></param>
 309     /// <param name="item"></param>
 310     protected void raiseForRemoveAt(int index, T item)
 311     {
 312       if (ActiveEvents != 0)
 313       {
 314         raiseItemRemovedAt(item, index);
 315         raiseItemsRemoved(item, 1);
 316         raiseCollectionChanged();
 317       }
 318     }
 319
 320     #endregion
 321
 322     #region Event  Support for ICollection
 323     /// <summary>
 324     ///
 325     /// </summary>
 326     /// <param name="newitem"></param>
 327     /// <param name="olditem"></param>
 328     protected virtual void raiseForUpdate(T newitem, T olditem)
 329     {
 330       if (ActiveEvents != 0)
 331       {
 332         raiseItemsRemoved(olditem, 1);
 333         raiseItemsAdded(newitem, 1);
 334         raiseCollectionChanged();
 335       }
 336     }
 337     /// <summary>
 338     ///
 339     /// </summary>
 340     /// <param name="newitem"></param>
 341     /// <param name="olditem"></param>
 342     /// <param name="count"></param>
 343     protected virtual void raiseForUpdate(T newitem, T olditem, int count)
 344     {
 345       if (ActiveEvents != 0)
 346       {
 347         raiseItemsRemoved(olditem, count);
 348         raiseItemsAdded(newitem, count);
 349         raiseCollectionChanged();
 350       }
 351     }
 352     /// <summary>
 353     ///
 354     /// </summary>
 355     /// <param name="item"></param>
 356     protected virtual void raiseForAdd(T item)
 357     {
 358       if (ActiveEvents != 0)
 359       {
 360         raiseItemsAdded(item, 1);
 361         raiseCollectionChanged();
 362       }
 363     }
 364     /// <summary>
 365     ///
 366     /// </summary>
 367     /// <param name="wasRemoved"></param>
 368     protected virtual void raiseForRemoveAll(ICollectionValue<T> wasRemoved)
 369     {
 370       if ((ActiveEvents & EventTypeEnum.Removed) != 0)
 371         foreach (T item in wasRemoved)
 372           raiseItemsRemoved(item, 1);
 373       if (wasRemoved != null && wasRemoved.Count > 0)
 374         raiseCollectionChanged();
 375     }
 376
 377     /// <summary>
 378     ///
 379     /// </summary>
 380     protected class RaiseForRemoveAllHandler
 381     {
 382       CollectionValueBase<T> collection;
 383       CircularQueue<T> wasRemoved;
 384       bool wasChanged = false;
 385
 386       /// <summary>
 387       ///
 388       /// </summary>
 389       /// <param name="collection"></param>
 390       public RaiseForRemoveAllHandler(CollectionValueBase<T> collection)
 391       {
 392         this.collection = collection;
 393         mustFireRemoved = (collection.ActiveEvents & EventTypeEnum.Removed) != 0;
 394         MustFire = (collection.ActiveEvents & (EventTypeEnum.Removed | EventTypeEnum.Changed)) != 0;
 395       }
 396
 397       bool mustFireRemoved;
 398       /// <summary>
 399       ///
 400       /// </summary>
 401       public readonly bool MustFire;
 402
 403       /// <summary>
 404       ///
 405       /// </summary>
 406       /// <param name="item"></param>
 407       public void Remove(T item)
 408       {
 409         if (mustFireRemoved)
 410         {
 411           if (wasRemoved == null)
 412             wasRemoved = new CircularQueue<T>();
 413           wasRemoved.Enqueue(item);
 414         }
 415         if (!wasChanged)
 416           wasChanged = true;
 417       }
 418
 419       /// <summary>
 420       ///
 421       /// </summary>
 422       public void Raise()
 423       {
 424         if (wasRemoved != null)
 425           foreach (T item in wasRemoved)
 426             collection.raiseItemsRemoved(item, 1);
 427         if (wasChanged)
 428           collection.raiseCollectionChanged();
 429       }
 430     }
 431     #endregion
 432
 433     #endregion
 434
 435     /// <summary>
 436     /// Check if collection is empty.
 437     /// </summary>
 438     /// <value>True if empty</value>
 439     public abstract bool IsEmpty { get;}
 440
 441     /// <summary>
 442     /// The number of items in this collection.
 443     /// </summary>
 444     /// <value></value>
 445     public abstract int Count { get;}
 446
 447     /// <summary>
 448     /// The value is symbolic indicating the type of asymptotic complexity
 449     /// in terms of the size of this collection (worst-case or amortized as
 450     /// relevant).
 451     /// </summary>
 452     /// <value>A characterization of the speed of the
 453     /// <code>Count</code> property in this collection.</value>
 454     public abstract Speed CountSpeed { get; }
 455
 456     /// <summary>
 457     /// Copy the items of this collection to part of an array.
 458     /// </summary>
 459     /// <exception cref="ArgumentOutOfRangeException"> if <code>index</code>
 460     /// is not a valid index
 461     /// into the array (i.e. negative or greater than the size of the array)
 462     /// or the array does not have room for the items.</exception>
 463     /// <param name="array">The array to copy to.</param>
 464     /// <param name="index">The starting index.</param>
 465     [Tested]
 466     public virtual void CopyTo(T[] array, int index)
 467     {
 468       if (index < 0 || index + Count > array.Length)
 469         throw new ArgumentOutOfRangeException();
 470
 471       foreach (T item in this) array[index++] = item;
 472     }
 473
 474     /// <summary>
 475     /// Create an array with the items of this collection (in the same order as an
 476     /// enumerator would output them).
 477     /// </summary>
 478     /// <returns>The array</returns>
 479     //[Tested]
 480     public virtual T[] ToArray()
 481     {
 482       T[] res = new T[Count];
 483       int i = 0;
 484
 485       foreach (T item in this) res[i++] = item;
 486
 487       return res;
 488     }
 489
 490     /// <summary>
 491     /// Apply an single argument action, <see cref="T:C5.Act`1"/> to this enumerable
 492     /// </summary>
 493     /// <param name="action">The action delegate</param>
 494     [Tested]
 495     public virtual void Apply(Act<T> action)
 496     {
 497       foreach (T item in this)
 498         action(item);
 499     }
 500
 501
 502     /// <summary>
 503     /// Check if there exists an item  that satisfies a
 504     /// specific predicate in this collection.
 505     /// </summary>
 506     /// <param name="predicate">A delegate
 507     /// (<see cref="T:C5.Fun`2"/> with <code>R = bool</code>)
 508     /// defining the predicate</param>
 509     /// <returns>True if such an item exists</returns>
 510     [Tested]
 511     public virtual bool Exists(Fun<T, bool> predicate)
 512     {
 513       foreach (T item in this)
 514         if (predicate(item))
 515           return true;
 516
 517       return false;
 518     }
 519
 520     /// <summary>
 521     /// Check if there exists an item  that satisfies a
 522     /// specific predicate in this collection and return the first one in enumeration order.
 523     /// </summary>
 524     /// <param name="predicate">A delegate
 525     /// (<see cref="T:C5.Fun`2"/> with <code>R == bool</code>) defining the predicate</param>
 526     /// <param name="item"></param>
 527     /// <returns>True is such an item exists</returns>
 528     public virtual bool Find(Fun<T, bool> predicate, out T item)
 529     {
 530       foreach (T jtem in this)
 531         if (predicate(jtem))
 532         {
 533           item = jtem;
 534           return true;
 535         }
 536       item = default(T);
 537       return false;
 538     }
 539
 540     /// <summary>
 541     /// Check if all items in this collection satisfies a specific predicate.
 542     /// </summary>
 543     /// <param name="predicate">A delegate
 544     /// (<see cref="T:C5.Fun`2"/> with <code>R = bool</code>)
 545     /// defining the predicate</param>
 546     /// <returns>True if all items satisfies the predicate</returns>
 547     [Tested]
 548     public virtual bool All(Fun<T, bool> predicate)
 549     {
 550       foreach (T item in this)
 551         if (!predicate(item))
 552           return false;
 553
 554       return true;
 555     }
 556
 557     /// <summary>
 558     /// Create an enumerable, enumerating the items of this collection that satisfies
 559     /// a certain condition.
 560     /// </summary>
 561     /// <param name="predicate">A delegate
 562     /// (<see cref="T:C5.Fun`2"/> with <code>R = bool</code>)
 563     /// defining the predicate</param>
 564     /// <returns>The filtered enumerable</returns>
 565     public virtual SCG.IEnumerable<T> Filter(Fun<T, bool> predicate)
 566     {
 567       foreach (T item in this)
 568         if (predicate(item))
 569           yield return item;
 570     }
 571
 572     /// <summary>
 573     /// Choose some item of this collection.
 574     /// </summary>
 575     /// <exception cref="NoSuchItemException">if collection is empty.</exception>
 576     /// <returns></returns>
 577     public abstract T Choose();
 578
 579
 580     /// <summary>
 581     /// Create an enumerator for this collection.
 582     /// </summary>
 583     /// <returns>The enumerator</returns>
 584     public override abstract SCG.IEnumerator<T> GetEnumerator();
 585
 586     #region IShowable Members
 587
 588     /// <summary>
 589     ///
 590     /// </summary>
 591     /// <param name="stringbuilder"></param>
 592     /// <param name="rest"></param>
 593     /// <param name="formatProvider"></param>
 594     /// <returns></returns>
 595     public virtual bool Show(System.Text.StringBuilder stringbuilder, ref int rest, IFormatProvider formatProvider)
 596     {
 597       return Showing.ShowCollectionValue<T>(this, stringbuilder, ref rest, formatProvider);
 598     }
 599     #endregion
 600
 601     #region IFormattable Members
 602
 603     /// <summary>
 604     ///
 605     /// </summary>
 606     /// <param name="format"></param>
 607     /// <param name="formatProvider"></param>
 608     /// <returns></returns>
 609     public virtual string ToString(string format, IFormatProvider formatProvider)
 610     {
 611       return Showing.ShowString(this, format, formatProvider);
 612     }
 613
 614     #endregion
 615
 616     /// <summary>
 617     ///
 618     /// </summary>
 619     /// <returns></returns>
 620     public override string ToString()
 621     {
 622       return ToString(null, null);
 623     }
 624
 625   }
 626
 627   /// <summary>
 628   ///
 629   /// </summary>
 630   /// <typeparam name="T"></typeparam>
 631   public abstract class DirectedCollectionValueBase<T> : CollectionValueBase<T>, IDirectedCollectionValue<T>
 632   {
 633     /// <summary>
 634     /// <code>Forwards</code> if same, else <code>Backwards</code>
 635     /// </summary>
 636     /// <value>The enumeration direction relative to the original collection.</value>
 637     public virtual EnumerationDirection Direction { [Tested]get { return EnumerationDirection.Forwards; } }
 638
 639     /// <summary>
 640     ///
 641     /// </summary>
 642     /// <returns></returns>
 643     public abstract IDirectedCollectionValue<T> Backwards();
 644
 645     IDirectedEnumerable<T> IDirectedEnumerable<T>.Backwards() { return this.Backwards(); }
 646
 647     /// <summary>
 648     /// Check if there exists an item  that satisfies a
 649     /// specific predicate in this collection and return the first one in enumeration order.
 650     /// </summary>
 651     /// <param name="predicate">A delegate
 652     /// (<see cref="T:C5.Fun`2"/> with <code>R == bool</code>) defining the predicate</param>
 653     /// <param name="item"></param>
 654     /// <returns>True is such an item exists</returns>
 655     public virtual bool FindLast(Fun<T, bool> predicate, out T item)
 656     {
 657       foreach (T jtem in Backwards())
 658         if (predicate(jtem))
 659         {
 660           item = jtem;
 661           return true;
 662         }
 663       item = default(T);
 664       return false;
 665     }
 666   }
 667
 668   /// <summary>
 669   /// Base class (abstract) for ICollection implementations.
 670   /// </summary>
 671   [Serializable]
 672   public abstract class CollectionBase<T> : CollectionValueBase<T>
 673   {
 674     #region Fields
 675
 676     /// <summary>
 677     /// The underlying field of the ReadOnly property
 678     /// </summary>
 679     protected bool isReadOnlyBase = false;
 680
 681     /// <summary>
 682     /// The current stamp value
 683     /// </summary>
 684     protected int stamp;
 685
 686     /// <summary>
 687     /// The number of items in the collection
 688     /// </summary>
 689     protected int size;
 690
 691     /// <summary>
 692     /// The item equalityComparer of the collection
 693     /// </summary>
 694     protected readonly SCG.IEqualityComparer<T> itemequalityComparer;
 695
 696     int iUnSequencedHashCode, iUnSequencedHashCodeStamp = -1;
 697
 698     #endregion
 699
 700     /// <summary>
 701     ///
 702     /// </summary>
 703     /// <param name="itemequalityComparer"></param>
 704     protected CollectionBase(SCG.IEqualityComparer<T> itemequalityComparer)
 705     {
 706       if (itemequalityComparer == null)
 707         throw new NullReferenceException("Item EqualityComparer cannot be null.");
 708       this.itemequalityComparer = itemequalityComparer;
 709     }
 710
 711     #region Util
 712
 713     /// <summary>
 714     /// Utility method for range checking.
 715     /// </summary>
 716     /// <exception cref="ArgumentOutOfRangeException"> if the start or count is negative or
 717     ///  if the range does not fit within collection size.</exception>
 718     /// <param name="start">start of range</param>
 719     /// <param name="count">size of range</param>
 720     [Tested]
 721     protected void checkRange(int start, int count)
 722     {
 723       if (start < 0 || count < 0 || start + count > size)
 724         throw new ArgumentOutOfRangeException();
 725     }
 726
 727
 728     /// <summary>
 729     /// Compute the unsequenced hash code of a collection
 730     /// </summary>
 731     /// <param name="items">The collection to compute hash code for</param>
 732     /// <param name="itemequalityComparer">The item equalityComparer</param>
 733     /// <returns>The hash code</returns>
 734     [Tested]
 735     public static int ComputeHashCode(ICollectionValue<T> items, SCG.IEqualityComparer<T> itemequalityComparer)
 736     {
 737       int h = 0;
 738
 739 #if IMPROVED_COLLECTION_HASHFUNCTION
 740       //But still heuristic:
 741       //Note: the three odd factors should really be random,
 742       //but there will be a problem with serialization/deserialization!
 743       //Two products is too few
 744       foreach (T item in items)
 745       {
 746         uint h1 = (uint)itemequalityComparer.GetHashCode(item);
 747
 748         h += (int)((h1 * 1529784657 + 1) ^ (h1 * 2912831877) ^ (h1 * 1118771817 + 2));
 749       }
 750
 751       return h;
 752       /*
 753             The pairs (-1657792980, -1570288808) and (1862883298, -272461342) gives the same
 754             unsequenced hashcode with this hashfunction. The pair was found with code like
 755
 756             HashDictionary<int, int[]> set = new HashDictionary<int, int[]>();
 757             Random rnd = new C5Random(12345);
 758             while (true)
 759             {
 760                 int[] a = new int[2];
 761                 a[0] = rnd.Next(); a[1] = rnd.Next();
 762                 int h = unsequencedhashcode(a);
 763                 int[] b = a;
 764                 if (set.FindOrAdd(h, ref b))
 765                 {
 766                     Console.WriteLine("Code {5}, Pair ({1},{2}) number {0} matched other pair ({3},{4})", set.Count, a[0], a[1], b[0], b[1], h);
 767                 }
 768             }
 769             */
 770 #else
 771             foreach (T item in items)
 772                                 h ^= itemequalityComparer.GetHashCode(item);
 773
 774                         return (items.Count << 16) + h;
 775 #endif
 776     }
 777
 778     static Type isortedtype = typeof(ISorted<T>);
 779
 780     /// <summary>
 781     /// Examine if collection1 and collection2 are equal as unsequenced collections
 782     /// using the specified item equalityComparer (assumed compatible with the two collections).
 783     /// </summary>
 784     /// <param name="collection1">The first collection</param>
 785     /// <param name="collection2">The second collection</param>
 786     /// <param name="itemequalityComparer">The item equalityComparer to use for comparison</param>
 787     /// <returns>True if equal</returns>
 788     [Tested]
 789     public static bool StaticEquals(ICollection<T> collection1, ICollection<T> collection2, SCG.IEqualityComparer<T> itemequalityComparer)
 790     {
 791       if (object.ReferenceEquals(collection1, collection2))
 792         return true;
 793
 794       // bug20070227:
 795       if (collection1 == null || collection2 == null)
 796         return false;
 797
 798       if (collection1.Count != collection2.Count)
 799         return false;
 800
 801       //This way we might run through both enumerations twice, but
 802       //probably not (if the hash codes are good)
 803       //TODO: check equal equalityComparers, at least here!
 804       if (collection1.GetUnsequencedHashCode() != collection2.GetUnsequencedHashCode())
 805         return false;
 806
 807       //TODO: move this to the sorted implementation classes?
 808       //Really depends on speed of InstanceOfType: we could save a cast
 809       {
 810         ISorted<T> stit, stat;
 811         if ((stit = collection1 as ISorted<T>) != null && (stat = collection2 as ISorted<T>) != null && stit.Comparer == stat.Comparer)
 812         {
 813           using (SCG.IEnumerator<T> dat = collection2.GetEnumerator(), dit = collection1.GetEnumerator())
 814           {
 815             while (dit.MoveNext())
 816             {
 817               dat.MoveNext();
 818               if (!itemequalityComparer.Equals(dit.Current, dat.Current))
 819                 return false;
 820             }
 821             return true;
 822           }
 823         }
 824       }
 825
 826       if (!collection1.AllowsDuplicates && (collection2.AllowsDuplicates || collection2.ContainsSpeed >= collection1.ContainsSpeed))
 827       {
 828         foreach (T x in collection1) if (!collection2.Contains(x)) return false;
 829       }
 830       else if (!collection2.AllowsDuplicates)
 831       {
 832         foreach (T x in collection2) if (!collection1.Contains(x)) return false;
 833       }
 834       // Now tit.AllowsDuplicates && tat.AllowsDuplicates
 835       else if (collection1.DuplicatesByCounting && collection2.DuplicatesByCounting)
 836       {
 837         foreach (T item in collection2) if (collection1.ContainsCount(item) != collection2.ContainsCount(item)) return false;
 838       }
 839       else
 840       {
 841         // To avoid an O(n^2) algorithm, we make an aux hashtable to hold the count of items
 842         // bug20101103: HashDictionary<T, int> dict = new HashDictionary<T, int>();
 843         HashDictionary<T, int> dict = new HashDictionary<T, int>(itemequalityComparer);
 844         foreach (T item in collection2)
 845         {
 846           int count = 1;
 847           if (dict.FindOrAdd(item, ref count))
 848             dict[item] = count + 1;
 849         }
 850         foreach (T item in collection1)
 851         {
 852           int count;
 853           if (dict.Find(item, out count) && count > 0)
 854             dict[item] = count - 1;
 855           else
 856             return false;
 857         }
 858         return true;
 859       }
 860
 861       return true;
 862     }
 863
 864
 865     /// <summary>
 866     /// Get the unsequenced collection hash code of this collection: from the cached
 867     /// value if present and up to date, else (re)compute.
 868     /// </summary>
 869     /// <returns>The hash code</returns>
 870     public virtual int GetUnsequencedHashCode()
 871     {
 872       if (iUnSequencedHashCodeStamp == stamp)
 873         return iUnSequencedHashCode;
 874
 875       iUnSequencedHashCode = ComputeHashCode(this, itemequalityComparer);
 876       iUnSequencedHashCodeStamp = stamp;
 877       return iUnSequencedHashCode;
 878     }
 879
 880
 881     /// <summary>
 882     /// Check if the contents of otherCollection is equal to the contents of this
 883     /// in the unsequenced sense.  Uses the item equality comparer of this collection
 884     /// </summary>
 885     /// <param name="otherCollection">The collection to compare to.</param>
 886     /// <returns>True if  equal</returns>
 887     public virtual bool UnsequencedEquals(ICollection<T> otherCollection)
 888     {
 889       return otherCollection != null && StaticEquals((ICollection<T>)this, otherCollection, itemequalityComparer);
 890     }
 891
 892
 893     /// <summary>
 894     /// Check if the collection has been modified since a specified time, expressed as a stamp value.
 895     /// </summary>
 896     /// <exception cref="CollectionModifiedException"> if this collection has been updated
 897     /// since a target time</exception>
 898     /// <param name="thestamp">The stamp identifying the target time</param>
 899     protected virtual void modifycheck(int thestamp)
 900     {
 901       if (this.stamp != thestamp)
 902         throw new CollectionModifiedException();
 903     }
 904
 905
 906     /// <summary>
 907     /// Check if it is valid to perform update operations, and if so increment stamp.
 908     /// </summary>
 909     /// <exception cref="ReadOnlyCollectionException">If colection is read-only</exception>
 910     protected virtual void updatecheck()
 911     {
 912       if (isReadOnlyBase)
 913         throw new ReadOnlyCollectionException();
 914
 915       stamp++;
 916     }
 917
 918     #endregion
 919
 920     #region ICollection<T> members
 921
 922     /// <summary>
 923     ///
 924     /// </summary>
 925     /// <value>True if this collection is read only</value>
 926     [Tested]
 927     public virtual bool IsReadOnly { [Tested]get { return isReadOnlyBase; } }
 928
 929     #endregion
 930
 931     #region ICollectionValue<T> members
 932     /// <summary>
 933     ///
 934     /// </summary>
 935     /// <value>The size of this collection</value>
 936     [Tested]
 937     public override int Count { [Tested]get { return size; } }
 938
 939     /// <summary>
 940     /// The value is symbolic indicating the type of asymptotic complexity
 941     /// in terms of the size of this collection (worst-case or amortized as
 942     /// relevant).
 943     /// </summary>
 944     /// <value>A characterization of the speed of the
 945     /// <code>Count</code> property in this collection.</value>
 946     public override Speed CountSpeed { get { return Speed.Constant; } }
 947
 948
 949     #endregion
 950
 951     #region IExtensible<T> members
 952
 953     /// <summary>
 954     ///
 955     /// </summary>
 956     /// <value></value>
 957     public virtual SCG.IEqualityComparer<T> EqualityComparer { get { return itemequalityComparer; } }
 958
 959     /// <summary>
 960     ///
 961     /// </summary>
 962     /// <value>True if this collection is empty</value>
 963     [Tested]
 964     public override bool IsEmpty { [Tested]get { return size == 0; } }
 965
 966     #endregion
 967
 968     #region IEnumerable<T> Members
 969     /// <summary>
 970     /// Create an enumerator for this collection.
 971     /// </summary>
 972     /// <returns>The enumerator</returns>
 973     public override abstract SCG.IEnumerator<T> GetEnumerator();
 974     #endregion
 975   }
 976
 977   /// <summary>
 978   ///
 979   /// </summary>
 980   /// <typeparam name="T"></typeparam>
 981   [Serializable]
 982   public abstract class DirectedCollectionBase<T> : CollectionBase<T>, IDirectedCollectionValue<T>
 983   {
 984     /// <summary>
 985     ///
 986     /// </summary>
 987     /// <param name="itemequalityComparer"></param>
 988     protected DirectedCollectionBase(SCG.IEqualityComparer<T> itemequalityComparer) : base(itemequalityComparer) { }
 989     /// <summary>
 990     /// <code>Forwards</code> if same, else <code>Backwards</code>
 991     /// </summary>
 992     /// <value>The enumeration direction relative to the original collection.</value>
 993     public virtual EnumerationDirection Direction { [Tested]get { return EnumerationDirection.Forwards; } }
 994
 995     /// <summary>
 996     ///
 997     /// </summary>
 998     /// <returns></returns>
 999     public abstract IDirectedCollectionValue<T> Backwards();
1000
1001     IDirectedEnumerable<T> IDirectedEnumerable<T>.Backwards() { return this.Backwards(); }
1002
1003     /// <summary>
1004     /// Check if there exists an item  that satisfies a
1005     /// specific predicate in this collection and return the first one in enumeration order.
1006     /// </summary>
1007     /// <param name="predicate">A delegate
1008     /// (<see cref="T:C5.Fun`2"/> with <code>R == bool</code>) defining the predicate</param>
1009     /// <param name="item"></param>
1010     /// <returns>True is such an item exists</returns>
1011     public virtual bool FindLast(Fun<T, bool> predicate, out T item)
1012     {
1013       foreach (T jtem in Backwards())
1014         if (predicate(jtem))
1015         {
1016           item = jtem;
1017           return true;
1018         }
1019       item = default(T);
1020       return false;
1021     }
1022   }
1023
1024   /// <summary>
1025   /// Base class (abstract) for sequenced collection implementations.
1026   /// </summary>
1027   [Serializable]
1028   public abstract class SequencedBase<T> : DirectedCollectionBase<T>, IDirectedCollectionValue<T>
1029   {
1030     #region Fields
1031
1032     int iSequencedHashCode, iSequencedHashCodeStamp = -1;
1033
1034     #endregion
1035
1036     /// <summary>
1037     ///
1038     /// </summary>
1039     /// <param name="itemequalityComparer"></param>
1040     protected SequencedBase(SCG.IEqualityComparer<T> itemequalityComparer) : base(itemequalityComparer) { }
1041
1042     #region Util
1043
1044     //TODO: make random for release
1045     const int HASHFACTOR = 31;
1046
1047     /// <summary>
1048     /// Compute the unsequenced hash code of a collection
1049     /// </summary>
1050     /// <param name="items">The collection to compute hash code for</param>
1051     /// <param name="itemequalityComparer">The item equalityComparer</param>
1052     /// <returns>The hash code</returns>
1053     [Tested]
1054     public static int ComputeHashCode(ISequenced<T> items, SCG.IEqualityComparer<T> itemequalityComparer)
1055     {
1056       //NOTE: It must be possible to devise a much stronger combined hashcode,
1057       //but unfortunately, it has to be universal. OR we could use a (strong)
1058       //family and initialise its parameter randomly at load time of this class!
1059       //(We would not want to have yet a flag to check for invalidation?!)
1060       //NBNBNB: the current hashcode has the very bad property that items with hashcode 0
1061       // is ignored.
1062       int iIndexedHashCode = 0;
1063
1064       foreach (T item in items)
1065         iIndexedHashCode = iIndexedHashCode * HASHFACTOR + itemequalityComparer.GetHashCode(item);
1066
1067       return iIndexedHashCode;
1068     }
1069
1070
1071     /// <summary>
1072     /// Examine if tit and tat are equal as sequenced collections
1073     /// using the specified item equalityComparer (assumed compatible with the two collections).
1074     /// </summary>
1075     /// <param name="collection1">The first collection</param>
1076     /// <param name="collection2">The second collection</param>
1077     /// <param name="itemequalityComparer">The item equalityComparer to use for comparison</param>
1078     /// <returns>True if equal</returns>
1079     [Tested]
1080     public static bool StaticEquals(ISequenced<T> collection1, ISequenced<T> collection2, SCG.IEqualityComparer<T> itemequalityComparer)
1081     {
1082       if (object.ReferenceEquals(collection1, collection2))
1083         return true;
1084
1085       if (collection1.Count != collection2.Count)
1086         return false;
1087
1088       //This way we might run through both enumerations twice, but
1089       //probably not (if the hash codes are good)
1090       if (collection1.GetSequencedHashCode() != collection2.GetSequencedHashCode())
1091         return false;
1092
1093       using (SCG.IEnumerator<T> dat = collection2.GetEnumerator(), dit = collection1.GetEnumerator())
1094       {
1095         while (dit.MoveNext())
1096         {
1097           dat.MoveNext();
1098           if (!itemequalityComparer.Equals(dit.Current, dat.Current))
1099             return false;
1100         }
1101       }
1102
1103       return true;
1104     }
1105
1106
1107     /// <summary>
1108     /// Get the sequenced collection hash code of this collection: from the cached
1109     /// value if present and up to date, else (re)compute.
1110     /// </summary>
1111     /// <returns>The hash code</returns>
1112     public virtual int GetSequencedHashCode()
1113     {
1114       if (iSequencedHashCodeStamp == stamp)
1115         return iSequencedHashCode;
1116
1117       iSequencedHashCode = ComputeHashCode((ISequenced<T>)this, itemequalityComparer);
1118       iSequencedHashCodeStamp = stamp;
1119       return iSequencedHashCode;
1120     }
1121
1122
1123     /// <summary>
1124     /// Check if the contents of that is equal to the contents of this
1125     /// in the sequenced sense. Using the item equalityComparer of this collection.
1126     /// </summary>
1127     /// <param name="otherCollection">The collection to compare to.</param>
1128     /// <returns>True if  equal</returns>
1129     public virtual bool SequencedEquals(ISequenced<T> otherCollection)
1130     {
1131       return StaticEquals((ISequenced<T>)this, otherCollection, itemequalityComparer);
1132     }
1133
1134
1135     #endregion
1136
1137     /// <summary>
1138     /// Create an enumerator for this collection.
1139     /// </summary>
1140     /// <returns>The enumerator</returns>
1141     public override abstract SCG.IEnumerator<T> GetEnumerator();
1142
1143     /// <summary>
1144     /// <code>Forwards</code> if same, else <code>Backwards</code>
1145     /// </summary>
1146     /// <value>The enumeration direction relative to the original collection.</value>
1147     [Tested]
1148     public override EnumerationDirection Direction { [Tested]get { return EnumerationDirection.Forwards; } }
1149
1150     /// <summary>
1151     /// Check if there exists an item  that satisfies a
1152     /// specific predicate in this collection and return the index of the first one.
1153     /// </summary>
1154     /// <param name="predicate">A delegate
1155     /// (<see cref="T:C5.Fun`2"/> with <code>R == bool</code>) defining the predicate</param>
1156     /// <returns>the index, if found, a negative value else</returns>
1157     public int FindIndex(Fun<T, bool> predicate)
1158     {
1159       int index = 0;
1160       foreach (T item in this)
1161       {
1162         if (predicate(item))
1163           return index;
1164         index++;
1165       }
1166       return -1;
1167     }
1168
1169     /// <summary>
1170     /// Check if there exists an item  that satisfies a
1171     /// specific predicate in this collection and return the index of the last one.
1172     /// </summary>
1173     /// <param name="predicate">A delegate
1174     /// (<see cref="T:C5.Fun`2"/> with <code>R == bool</code>) defining the predicate</param>
1175     /// <returns>the index, if found, a negative value else</returns>
1176     public int FindLastIndex(Fun<T, bool> predicate)
1177     {
1178       int index = Count - 1;
1179       foreach (T item in Backwards())
1180       {
1181         if (predicate(item))
1182           return index;
1183         index--;
1184       }
1185       return -1;
1186     }
1187
1188   }
1189
1190
1191   /// <summary>
1192   /// Base class for collection classes of dynamic array type implementations.
1193   /// </summary>
1194   [Serializable]
1195   public abstract class ArrayBase<T> : SequencedBase<T>
1196   {
1197     #region Fields
1198     /// <summary>
1199     /// The actual internal array container. Will be extended on demand.
1200     /// </summary>
1201     protected T[] array;
1202
1203     /// <summary>
1204     /// The offset into the internal array container of the first item. The offset is 0 for a
1205     /// base dynamic array and may be positive for an updatable view into a base dynamic array.
1206     /// </summary>
1207     protected int offset;
1208     #endregion
1209
1210     #region Util
1211     /// <summary>
1212     /// Double the size of the internal array.
1213     /// </summary>
1214     protected virtual void expand()
1215     {
1216       expand(2 * array.Length, size);
1217     }
1218
1219
1220     /// <summary>
1221     /// Expand the internal array container.
1222     /// </summary>
1223     /// <param name="newcapacity">The new size of the internal array -
1224     /// will be rounded upwards to a power of 2.</param>
1225     /// <param name="newsize">The (new) size of the (base) collection.</param>
1226     protected virtual void expand(int newcapacity, int newsize)
1227     {
1228       Debug.Assert(newcapacity >= newsize);
1229
1230       int newlength = array.Length;
1231
1232       while (newlength < newcapacity) newlength *= 2;
1233
1234       T[] newarray = new T[newlength];
1235
1236       Array.Copy(array, newarray, newsize);
1237       array = newarray;
1238     }
1239
1240
1241     /// <summary>
1242     /// Insert an item at a specific index, moving items to the right
1243     /// upwards and expanding the array if necessary.
1244     /// </summary>
1245     /// <param name="i">The index at which to insert.</param>
1246     /// <param name="item">The item to insert.</param>
1247     protected virtual void insert(int i, T item)
1248     {
1249       if (size == array.Length)
1250         expand();
1251
1252       if (i < size)
1253         Array.Copy(array, i, array, i + 1, size - i);
1254
1255       array[i] = item;
1256       size++;
1257     }
1258
1259     #endregion
1260
1261     #region Constructors
1262
1263     /// <summary>
1264     /// Create an empty ArrayBase object.
1265     /// </summary>
1266     /// <param name="capacity">The initial capacity of the internal array container.
1267     /// Will be rounded upwards to the nearest power of 2 greater than or equal to 8.</param>
1268     /// <param name="itemequalityComparer">The item equalityComparer to use, primarily for item equality</param>
1269     protected ArrayBase(int capacity, SCG.IEqualityComparer<T> itemequalityComparer)
1270       : base(itemequalityComparer)
1271     {
1272       int newlength = 8;
1273       while (newlength < capacity) newlength *= 2;
1274       array = new T[newlength];
1275     }
1276
1277     #endregion
1278
1279     #region IIndexed members
1280
1281     /// <summary>
1282     /// </summary>
1283     /// <exception cref="ArgumentOutOfRangeException">If the arguments does not describe a
1284     /// valid range in the indexed collection, cf. <see cref="M:C5.CollectionBase`1.checkRange(System.Int32,System.Int32)"/>.</exception>
1285     /// <value>The directed collection of items in a specific index interval.</value>
1286     /// <param name="start">The low index of the interval (inclusive).</param>
1287     /// <param name="count">The size of the range.</param>
1288     [Tested]
1289     public virtual IDirectedCollectionValue<T> this[int start, int count]
1290     {
1291       [Tested]
1292       get
1293       {
1294         checkRange(start, count);
1295         return new Range(this, start, count, true);
1296       }
1297     }
1298
1299     #endregion
1300
1301     #region IEditableCollection members
1302     /// <summary>
1303     /// Remove all items and reset size of internal array container.
1304     /// </summary>
1305     [Tested]
1306     public virtual void Clear()
1307     {
1308       updatecheck();
1309       array = new T[8];
1310       size = 0;
1311     }
1312
1313
1314     /// <summary>
1315     /// Create an array containing (copies) of the items of this collection in enumeration order.
1316     /// </summary>
1317     /// <returns>The new array</returns>
1318     [Tested]
1319     public override T[] ToArray()
1320     {
1321       T[] res = new T[size];
1322
1323       Array.Copy(array, offset, res, 0, size);
1324       return res;
1325     }
1326
1327
1328     /// <summary>
1329     /// Perform an internal consistency (invariant) test on the array base.
1330     /// </summary>
1331     /// <returns>True if test succeeds.</returns>
1332     [Tested]
1333     public virtual bool Check()
1334     {
1335       bool retval = true;
1336
1337       if (size > array.Length)
1338       {
1339         Console.WriteLine("Bad size ({0}) > array.Length ({1})", size, array.Length);
1340         return false;
1341       }
1342
1343       for (int i = 0; i < size; i++)
1344       {
1345         if ((object)(array[i]) == null)
1346         {
1347           Console.WriteLine("Bad element: null at index {0}", i);
1348           return false;
1349         }
1350       }
1351
1352       return retval;
1353     }
1354
1355     #endregion
1356
1357     #region IDirectedCollection<T> Members
1358
1359     /// <summary>
1360     /// Create a directed collection with the same contents as this one, but
1361     /// opposite enumeration sequence.
1362     /// </summary>
1363     /// <returns>The mirrored collection.</returns>
1364     [Tested]
1365     public override IDirectedCollectionValue<T> Backwards() { return this[0, size].Backwards(); }
1366
1367     #endregion
1368
1369     /// <summary>
1370     /// Choose some item of this collection. The result is the last item in the internal array,
1371     /// making it efficient to remove.
1372     /// </summary>
1373     /// <exception cref="NoSuchItemException">if collection is empty.</exception>
1374     /// <returns></returns>
1375     public override T Choose() { if (size > 0) return array[size - 1]; throw new NoSuchItemException(); }
1376
1377     #region IEnumerable<T> Members
1378     /// <summary>
1379     /// Create an enumerator for this array based collection.
1380     /// </summary>
1381     /// <returns>The enumerator</returns>
1382     [Tested]
1383     public override SCG.IEnumerator<T> GetEnumerator()
1384     {
1385       int thestamp = stamp, theend = size + offset, thestart = offset;
1386
1387       for (int i = thestart; i < theend; i++)
1388       {
1389         modifycheck(thestamp);
1390         yield return array[i];
1391       }
1392     }
1393     #endregion
1394
1395     #region Range nested class
1396     /// <summary>
1397     /// A helper class for defining results of interval queries on array based collections.
1398     /// </summary>
1399     protected class Range : DirectedCollectionValueBase<T>, IDirectedCollectionValue<T>
1400     {
1401       int start, count, delta, stamp;
1402
1403       ArrayBase<T> thebase;
1404
1405
1406       internal Range(ArrayBase<T> thebase, int start, int count, bool forwards)
1407       {
1408         this.thebase = thebase; stamp = thebase.stamp;
1409         delta = forwards ? 1 : -1;
1410         this.start = start + thebase.offset; this.count = count;
1411       }
1412
1413       /// <summary>
1414       ///
1415       /// </summary>
1416       /// <exception cref="CollectionModifiedException">if underlying collection has been modified.</exception>
1417       /// <value>True if this collection is empty.</value>
1418       public override bool IsEmpty { get { thebase.modifycheck(stamp); return count == 0; } }
1419
1420
1421       /// <summary>
1422       ///
1423       /// </summary>
1424       /// <exception cref="CollectionModifiedException">if underlying collection has been modified.</exception>
1425       /// <value>The number of items in the range</value>
1426       [Tested]
1427       public override int Count { [Tested]get { thebase.modifycheck(stamp); return count; } }
1428
1429       /// <summary>
1430       /// The value is symbolic indicating the type of asymptotic complexity
1431       /// in terms of the size of this collection (worst-case or amortized as
1432       /// relevant).
1433       /// </summary>
1434       /// <value>A characterization of the speed of the
1435       /// <exception cref="CollectionModifiedException">if underlying collection has been modified.</exception>
1436       /// <code>Count</code> property in this collection.</value>
1437       public override Speed CountSpeed { get { thebase.modifycheck(stamp); return Speed.Constant; } }
1438
1439       /// <summary>
1440       /// Choose some item of this collection.
1441       /// </summary>
1442       /// <exception cref="CollectionModifiedException">if underlying collection has been modified.</exception>
1443       /// <exception cref="NoSuchItemException">if range is empty.</exception>
1444       /// <returns></returns>
1445       public override T Choose()
1446       {
1447         thebase.modifycheck(stamp);
1448         if (count == 0)
1449           throw new NoSuchItemException();
1450         return thebase.array[start];
1451       }
1452
1453
1454       /// <summary>
1455       /// Create an enumerator for this range of an array based collection.
1456       /// </summary>
1457       /// <exception cref="CollectionModifiedException">if underlying collection has been modified.</exception>
1458       /// <returns>The enumerator</returns>
1459       [Tested]
1460       public override SCG.IEnumerator<T> GetEnumerator()
1461       {
1462         for (int i = 0; i < count; i++)
1463         {
1464           thebase.modifycheck(stamp);
1465           yield return thebase.array[start + delta * i];
1466         }
1467       }
1468
1469
1470       /// <summary>
1471       /// Create a araay collection range with the same contents as this one, but
1472       /// opposite enumeration sequence.
1473       /// </summary>
1474       /// <exception cref="CollectionModifiedException">if underlying collection has been modified.</exception>
1475       /// <returns>The mirrored collection.</returns>
1476       [Tested]
1477       public override IDirectedCollectionValue<T> Backwards()
1478       {
1479         thebase.modifycheck(stamp);
1480
1481         Range res = (Range)MemberwiseClone();
1482
1483         res.delta = -delta;
1484         res.start = start + (count - 1) * delta;
1485         return res;
1486       }
1487
1488
1489       IDirectedEnumerable<T> C5.IDirectedEnumerable<T>.Backwards()
1490       {
1491         return Backwards();
1492       }
1493
1494
1495       /// <summary>
1496       /// <code>Forwards</code> if same, else <code>Backwards</code>
1497       /// </summary>
1498       /// <exception cref="CollectionModifiedException">if underlying collection has been modified.</exception>
1499       /// <value>The enumeration direction relative to the original collection.</value>
1500       [Tested]
1501       public override EnumerationDirection Direction
1502       {
1503         [Tested]
1504         get
1505         {
1506           thebase.modifycheck(stamp);
1507           return delta > 0 ? EnumerationDirection.Forwards : EnumerationDirection.Backwards;
1508         }
1509       }
1510     }
1511     #endregion
1512   }
1513 }