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

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