mcs/class/Mono.C5/Collections.cs

   1 #if NET_2_0
   2 /*
   3  Copyright (c) 2003-2004 Niels Kokholm <kokholm@itu.dk> and Peter Sestoft <sestoft@dina.kvl.dk>
   4  Permission is hereby granted, free of charge, to any person obtaining a copy
   5  of this software and associated documentation files (the "Software"), to deal
   6  in the Software without restriction, including without limitation the rights
   7  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
   8  copies of the Software, and to permit persons to whom the Software is
   9  furnished to do so, subject to the following conditions:
  10
  11  The above copyright notice and this permission notice shall be included in
  12  all copies or substantial portions of the Software.
  13
  14  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  15  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  16  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  17  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  18  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  19  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  20  SOFTWARE.
  21 */
  22
  23 using System;
  24 using System.Diagnostics;
  25 using MSG = System.Collections.Generic;
  26 namespace C5
  27 {
  28         /// <summary>
  29         /// Direction of enumeration order relative to original collection.
  30         /// </summary>
  31         public enum EnumerationDirection {
  32                 /// <summary>
  33                 /// Same direction
  34                 /// </summary>
  35                 Forwards,
  36                 /// <summary>
  37                 /// Opposite direction
  38                 /// </summary>
  39                 Backwards
  40         }
  41
  42         #region int stuff
  43         class IC: IComparer<int>
  44         {
  45                 [Tested]
  46                 public int Compare(int a, int b) { return a > b ? 1 : a < b ? -1 : 0; }
  47         }
  48
  49
  50
  51         /// <summary>
  52         /// A hasher for int32
  53         /// </summary>
  54         public class IntHasher: IHasher<int>
  55         {
  56                 /// <summary>
  57                 /// Get the hash code of this integer, i.e. itself
  58                 /// </summary>
  59                 /// <param name="item">The integer</param>
  60                 /// <returns>The same</returns>
  61                 [Tested]
  62                 public int GetHashCode(int item) { return item; }
  63
  64
  65                 /// <summary>
  66                 /// Check if two integers are equal
  67                 /// </summary>
  68                 /// <param name="i1">first integer</param>
  69                 /// <param name="i2">second integer</param>
  70                 /// <returns>True if equal</returns>
  71                 [Tested]
  72                 public bool Equals(int i1, int i2) { return i1 == i2; }
  73         }
  74
  75
  76         #endregion
  77
  78         #region Natural Comparers
  79
  80
  81         /// <summary>
  82         /// A natural generic IComparer for an IComparable&lt;T&gt; item type
  83         /// </summary>
  84         public class NaturalComparer<T>: IComparer<T>
  85                 where T: IComparable<T>
  86         {
  87                 /// <summary>
  88                 /// Compare two items
  89                 /// </summary>
  90                 /// <param name="a">First item</param>
  91                 /// <param name="b">Second item</param>
  92                 /// <returns>a &lt;=&gt; b</returns>
  93                 [Tested]
  94                 public int Compare(T a, T b) { return a.CompareTo(b); }
  95         }
  96
  97
  98
  99         /// <summary>
 100         /// A natural generic IComparer for a System.IComparable item type
 101         /// </summary>
 102         public class NaturalComparerO<T>: IComparer<T>
 103                 where T: System.IComparable
 104         {
 105                 /// <summary>
 106                 /// Compare two items
 107                 /// </summary>
 108                 /// <param name="a">First item</param>
 109                 /// <param name="b">Second item</param>
 110                 /// <returns>a &lt;=&gt; b</returns>
 111                 [Tested]
 112                 public int Compare(T a, T b) { return a.CompareTo(b); }
 113         }
 114
 115
 116
 117         #endregion
 118
 119         #region Hashers
 120         /// <summary>
 121         /// The default item hasher for a reference type. A trivial wrapper for calling
 122         /// the GetHashCode and Equals methods inherited from object.
 123         ///
 124         /// <p>Should only be instantiated with a reference type as generic type parameter.
 125         /// This is asserted at instatiation time in Debug builds.</p>
 126         /// </summary>
 127         public sealed class DefaultReferenceTypeHasher<T>: IHasher<T>
 128         {
 129                 static DefaultReferenceTypeHasher()
 130                 {
 131                         Debug.Assert(!typeof(T).IsValueType, "DefaultReferenceTypeHasher instantiated with value type: " + typeof(T));
 132                 }
 133
 134                 /// <summary>
 135                 /// Get the hash code with respect to this item hasher
 136                 /// </summary>
 137                 /// <param name="item">The item</param>
 138                 /// <returns>The hash code</returns>
 139                 [Tested]
 140                 public int GetHashCode(T item) { return item.GetHashCode(); }
 141
 142
 143                 /// <summary>
 144                 /// Check if two items are equal with respect to this item hasher
 145                 /// </summary>
 146                 /// <param name="i1">first item</param>
 147                 /// <param name="i2">second item</param>
 148                 /// <returns>True if equal</returns>
 149                 [Tested]
 150                 public bool Equals(T i1, T i2)
 151                 {
 152                         //For reference types, the (object) cast should be jitted as a noop.
 153                         return (object)i1 == null ? (object)i2 == null : i1.Equals(i2);
 154                 }
 155         }
 156
 157         /// <summary>
 158         /// The default item hasher for a value type. A trivial wrapper for calling
 159         /// the GetHashCode and Equals methods inherited from object.
 160         ///
 161         /// <p>Should only be instantiated with a value type as generic type parameter.
 162         /// This is asserted at instatiation time in Debug builds.</p>
 163         /// <p>We cannot add the constraint "where T : struct" to get a compile time check
 164         /// because we need to instantiate this class in C5.HasherBuilder.ByPrototype[T].Examine()
 165         /// with a T that is only known at runtime to be a value type!</p>
 166         /// </summary>
 167
 168     //Note: we could (now) add a constraint "where T : struct" to get a compile time check,
 169     //but
 170         public sealed class DefaultValueTypeHasher<T>: IHasher<T>
 171         {
 172                 static DefaultValueTypeHasher()
 173                 {
 174                         Debug.Assert(typeof(T).IsValueType, "DefaultValueTypeHasher instantiated with reference type: " + typeof(T));
 175                 }
 176                 /// <summary>
 177                 /// Get the hash code with respect to this item hasher
 178                 /// </summary>
 179                 /// <param name="item">The item</param>
 180                 /// <returns>The hash code</returns>
 181                 [Tested]
 182                 public int GetHashCode(T item) { return item.GetHashCode(); }
 183
 184
 185                 /// <summary>
 186                 /// Check if two items are equal with respect to this item hasher
 187                 /// </summary>
 188                 /// <param name="i1">first item</param>
 189                 /// <param name="i2">second item</param>
 190                 /// <returns>True if equal</returns>
 191                 [Tested]
 192                 public bool Equals(T i1, T i2) { return i1.Equals(i2); }
 193         }
 194
 195         #endregion
 196
 197         #region Bases
 198
 199         /// <summary>
 200         /// A base class for implementing an IEnumerable&lt;T&gt;
 201         /// </summary>
 202         public abstract class EnumerableBase<T>: MSG.IEnumerable<T>
 203         {
 204                 /// <summary>
 205                 /// Create an enumerator for this collection.
 206                 /// </summary>
 207                 /// <returns>The enumerator</returns>
 208                 public abstract MSG.IEnumerator<T> GetEnumerator();
 209
 210                 /// <summary>
 211                 /// Count the number of items in an enumerable by enumeration
 212                 /// </summary>
 213                 /// <param name="items">The enumerable to count</param>
 214                 /// <returns>The size of the enumerable</returns>
 215                 protected static int countItems(MSG.IEnumerable<T> items)
 216                 {
 217                         ICollectionValue<T> jtems = items as ICollectionValue<T>;
 218
 219                         if (jtems != null)
 220                                 return jtems.Count;
 221
 222                         int count = 0;
 223
 224                         using (MSG.IEnumerator<T> e = items.GetEnumerator())
 225                                 while (e.MoveNext()) count++;
 226
 227                         return count;
 228                 }
 229         }
 230
 231
 232         /// <summary>
 233         /// Base class for classes implementing ICollectionValue[T]
 234         /// </summary>
 235         public abstract class CollectionValueBase<T>: EnumerableBase<T>, ICollectionValue<T>
 236         {
 237                 //This forces our subclasses to make Count virtual!
 238                 /// <summary>
 239                 /// The number of items in this collection.
 240                 /// </summary>
 241                 /// <value></value>
 242                 public abstract int Count { get;}
 243
 244         /// <summary>
 245         /// The value is symbolic indicating the type of asymptotic complexity
 246         /// in terms of the size of this collection (worst-case or amortized as
 247         /// relevant).
 248         /// </summary>
 249         /// <value>A characterization of the speed of the
 250         /// <code>Count</code> property in this collection.</value>
 251         public abstract Speed CountSpeed { get; }
 252
 253
 254         /// <summary>
 255                 /// Copy the items of this collection to part of an array.
 256                 /// <exception cref="ArgumentOutOfRangeException"/> if i is negative.
 257                 /// <exception cref="ArgumentException"/> if the array does not have room for the items.
 258                 /// </summary>
 259                 /// <param name="a">The array to copy to</param>
 260                 /// <param name="i">The starting index.</param>
 261                 [Tested]
 262                 public virtual void CopyTo(T[] a, int i)
 263                 {
 264                         if (i < 0)
 265                                 throw new ArgumentOutOfRangeException();
 266
 267                         if (i + Count > a.Length)
 268                                 throw new ArgumentException();
 269
 270                         foreach (T item in this) a[i++] = item;
 271                 }
 272
 273         /// <summary>
 274         /// Create an array with the items of this collection (in the same order as an
 275         /// enumerator would output them).
 276         /// </summary>
 277         /// <returns>The array</returns>
 278         //[Tested]
 279         public virtual T[] ToArray()
 280         {
 281             T[] res = new T[Count];
 282             int i = 0;
 283
 284             foreach (T item in this) res[i++] = item;
 285
 286             return res;
 287         }
 288
 289         /// <summary>
 290         /// Apply an Applier&lt;T&gt; to this enumerable
 291         /// </summary>
 292         /// <param name="a">The applier delegate</param>
 293         [Tested]
 294         public void Apply(Applier<T> a)
 295         {
 296             foreach (T item in this)
 297                 a(item);
 298         }
 299
 300
 301         /// <summary>
 302         /// Check if there exists an item  that satisfies a
 303         /// specific predicate in this collection.
 304         /// </summary>
 305         /// <param name="filter">A filter delegate
 306         /// (<see cref="T:C5.Filter!1"/>) defining the predicate</param>
 307         /// <returns>True is such an item exists</returns>
 308         [Tested]
 309         public bool Exists(Filter<T> filter)
 310         {
 311             foreach (T item in this)
 312                 if (filter(item))
 313                     return true;
 314
 315             return false;
 316         }
 317
 318
 319         /// <summary>
 320         /// Check if all items in this collection satisfies a specific predicate.
 321         /// </summary>
 322         /// <param name="filter">A filter delegate
 323         /// (<see cref="T:C5.Filter!1"/>) defining the predicate</param>
 324         /// <returns>True if all items satisfies the predicate</returns>
 325         [Tested]
 326         public bool All(Filter<T> filter)
 327         {
 328             foreach (T item in this)
 329                 if (!filter(item))
 330                     return false;
 331
 332             return true;
 333         }
 334
 335         /// <summary>
 336         /// Create an enumerator for this collection.
 337                 /// </summary>
 338                 /// <returns>The enumerator</returns>
 339                 public override abstract MSG.IEnumerator<T> GetEnumerator();
 340         }
 341
 342
 343         /// <summary>
 344         /// Base class (abstract) for ICollection implementations.
 345         /// </summary>
 346         public abstract class CollectionBase<T>: CollectionValueBase<T>
 347         {
 348                 #region Fields
 349
 350                 object syncroot = new object();
 351
 352                 /// <summary>
 353                 /// The underlying field of the ReadOnly property
 354                 /// </summary>
 355                 protected bool isReadOnly = false;
 356
 357                 /// <summary>
 358                 /// The current stamp value
 359                 /// </summary>
 360                 protected int stamp;
 361
 362                 /// <summary>
 363                 /// The number of items in the collection
 364                 /// </summary>
 365                 protected int size;
 366
 367                 /// <summary>
 368                 /// The item hasher of the collection
 369                 /// </summary>
 370                 protected IHasher<T> itemhasher;
 371
 372                 int iUnSequencedHashCode, iUnSequencedHashCodeStamp = -1;
 373
 374                 #endregion
 375
 376                 #region Util
 377
 378                 //protected bool equals(T i1, T i2) { return itemhasher.Equals(i1, i2); }
 379                 /// <summary>
 380                 /// Utility method for range checking.
 381                 /// <exception cref="ArgumentOutOfRangeException"/> if the start or count is negative
 382                 /// <exception cref="ArgumentException"/> if the range does not fit within collection size.
 383                 /// </summary>
 384                 /// <param name="start">start of range</param>
 385                 /// <param name="count">size of range</param>
 386                 [Tested]
 387                 protected void checkRange(int start, int count)
 388                 {
 389                         if (start < 0 || count < 0)
 390                                 throw new ArgumentOutOfRangeException();
 391
 392                         if (start + count > size)
 393                                 throw new ArgumentException();
 394                 }
 395
 396
 397                 /// <summary>
 398                 /// Compute the unsequenced hash code of a collection
 399                 /// </summary>
 400                 /// <param name="items">The collection to compute hash code for</param>
 401                 /// <param name="itemhasher">The item hasher</param>
 402                 /// <returns>The hash code</returns>
 403                 [Tested]
 404                 public static int ComputeHashCode(ICollectionValue<T> items, IHasher<T> itemhasher)
 405                 {
 406                         int h = 0;
 407
 408                         foreach (T item in items)
 409                                 h ^= itemhasher.GetHashCode(item);
 410
 411                         return (items.Count << 16) + h;
 412                 }
 413
 414
 415                 /// <summary>
 416                 /// Examine if tit and tat are equal as unsequenced collections
 417                 /// using the specified item hasher (assumed compatible with the two collections).
 418                 /// </summary>
 419                 /// <param name="tit">The first collection</param>
 420                 /// <param name="tat">The second collection</param>
 421                 /// <param name="itemhasher">The item hasher to use for comparison</param>
 422                 /// <returns>True if equal</returns>
 423                 [Tested]
 424                 public static bool StaticEquals(ICollection<T> tit, ICollection<T> tat, IHasher<T> itemhasher)
 425                 {
 426                         if (tat == null)
 427                                 return tit == null;
 428
 429                         if (tit.Count != tat.Count)
 430                                 return false;
 431
 432                         //This way we might run through both enumerations twice, but
 433                         //probably not (if the hash codes are good)
 434                         if (tit.GetHashCode() != tat.GetHashCode())
 435                                 return false;
 436
 437             if (!tit.AllowsDuplicates && (tat.AllowsDuplicates || tat.ContainsSpeed >= tit.ContainsSpeed))
 438             {
 439                 //TODO: use foreach construction
 440                                 using (MSG.IEnumerator<T> dit = tit.GetEnumerator())
 441                                 {
 442                                         while (dit.MoveNext())
 443                                                 if (!tat.Contains(dit.Current))
 444                                                         return false;
 445                                 }
 446                         }
 447             else if (!tat.AllowsDuplicates)
 448             {
 449                                 using (MSG.IEnumerator<T> dat = tat.GetEnumerator())
 450                                 {
 451                                         while (dat.MoveNext())
 452                                                 if (!tit.Contains(dat.Current))
 453                                                         return false;
 454                                 }
 455                         }
 456                         else
 457                         {//both are bags, we only have a slow one
 458                                 //unless the bags are based on a fast T->int dictinary (tree or hash)
 459                                 using (MSG.IEnumerator<T> dat = tat.GetEnumerator())
 460                                 {
 461                                         while (dat.MoveNext())
 462                                         {
 463                                                 T item = dat.Current;
 464
 465                                                 if (tit.ContainsCount(item) != tat.ContainsCount(item))
 466                                                         return false;
 467                                         }
 468                                 }
 469                                 //That was O(n^3) - completely unacceptable.
 470                                 //If we use an auxiliary bool[] we can do the comparison in O(n^2)
 471                         }
 472
 473                         return true;
 474                 }
 475
 476
 477                 /// <summary>
 478                 /// Get the unsequenced collection hash code of this collection: from the cached
 479                 /// value if present and up to date, else (re)compute.
 480                 /// </summary>
 481                 /// <returns>The hash code</returns>
 482                 protected int unsequencedhashcode()
 483                 {
 484                         if (iUnSequencedHashCodeStamp == stamp)
 485                                 return iUnSequencedHashCode;
 486
 487                         iUnSequencedHashCode = ComputeHashCode(this, itemhasher);
 488                         iUnSequencedHashCodeStamp = stamp;
 489                         return iUnSequencedHashCode;
 490                 }
 491
 492
 493                 /// <summary>
 494                 /// Check if the contents of that is equal to the contents of this
 495                 /// in the unsequenced sense. Using the item hasher of this collection.
 496                 /// </summary>
 497                 /// <param name="that">The collection to compare to.</param>
 498                 /// <returns>True if  equal</returns>
 499                 protected bool unsequencedequals(ICollection<T> that)
 500                 {
 501                         return StaticEquals((ICollection<T>)this, that, itemhasher);
 502                 }
 503
 504
 505                 /// <summary>
 506                 /// <exception cref="InvalidOperationException"/> if this collection has been updated
 507                 /// since a target time
 508                 /// </summary>
 509                 /// <param name="thestamp">The stamp identifying the target time</param>
 510                 protected virtual void modifycheck(int thestamp)
 511                 {
 512                         if (this.stamp != thestamp)
 513                                 throw new InvalidOperationException("Collection was modified");
 514                 }
 515
 516
 517                 /// <summary>
 518                 /// Check if it is valid to perform update operations, and if so increment stamp
 519                 /// </summary>
 520                 protected virtual void updatecheck()
 521                 {
 522                         if (isReadOnly)
 523                                 throw new InvalidOperationException("Collection cannot be modified through this guard object");
 524
 525                         stamp++;
 526                 }
 527
 528                 #endregion
 529
 530                 #region IEditableCollection<T> members
 531
 532                 /// <summary>
 533                 ///
 534                 /// </summary>
 535                 /// <value>True if this collection is read only</value>
 536                 [Tested]
 537                 public bool IsReadOnly { [Tested]get { return isReadOnly; } }
 538
 539                 #endregion
 540
 541                 #region ICollection<T> members
 542                 /// <summary>
 543                 ///
 544                 /// </summary>
 545                 /// <value>The size of this collection</value>
 546                 [Tested]
 547                 public override int Count { [Tested]get { return size; } }
 548
 549         /// <summary>
 550         /// The value is symbolic indicating the type of asymptotic complexity
 551         /// in terms of the size of this collection (worst-case or amortized as
 552         /// relevant).
 553         /// </summary>
 554         /// <value>A characterization of the speed of the
 555         /// <code>Count</code> property in this collection.</value>
 556         public override Speed CountSpeed { get { return Speed.Constant; } }
 557
 558
 559                 #endregion
 560
 561                 #region ISink<T> members
 562                 /// <summary>
 563                 ///
 564                 /// </summary>
 565                 /// <value>A distinguished object to use for locking to synchronize multithreaded access</value>
 566                 [Tested]
 567                 public object SyncRoot { get { return syncroot; } }
 568
 569
 570                 /// <summary>
 571                 ///
 572                 /// </summary>
 573                 /// <value>True is this collection is empty</value>
 574                 [Tested]
 575                 public bool IsEmpty { [Tested]get { return size == 0; } }
 576                 #endregion
 577
 578                 #region IEnumerable<T> Members
 579                 /// <summary>
 580                 /// Create an enumerator for this collection.
 581                 /// </summary>
 582                 /// <returns>The enumerator</returns>
 583                 public override abstract MSG.IEnumerator<T> GetEnumerator();
 584                 #endregion
 585         }
 586
 587
 588         /// <summary>
 589         /// Base class (abstract) for sequenced collection implementations.
 590         /// </summary>
 591         public abstract class SequencedBase<T>: CollectionBase<T>
 592         {
 593                 #region Fields
 594
 595                 int iSequencedHashCode, iSequencedHashCodeStamp = -1;
 596
 597                 #endregion
 598
 599                 #region Util
 600
 601                 /// <summary>
 602                 /// Compute the unsequenced hash code of a collection
 603                 /// </summary>
 604                 /// <param name="items">The collection to compute hash code for</param>
 605                 /// <param name="itemhasher">The item hasher</param>
 606                 /// <returns>The hash code</returns>
 607                 [Tested]
 608                 public static int ComputeHashCode(ISequenced<T> items, IHasher<T> itemhasher)
 609                 {
 610                         //NOTE: It must be possible to devise a much stronger combined hashcode,
 611                         //but unfortunately, it has to be universal. OR we could use a (strong)
 612                         //family and initialise its parameter randomly at load time of this class!
 613                         //(We would not want to have yet a flag to check for invalidation?!)
 614                         int iIndexedHashCode = 0;
 615
 616                         foreach (T item in items)
 617                                 iIndexedHashCode = iIndexedHashCode * 31 + itemhasher.GetHashCode(item);
 618
 619                         return iIndexedHashCode;
 620                 }
 621
 622
 623                 /// <summary>
 624                 /// Examine if tit and tat are equal as sequenced collections
 625                 /// using the specified item hasher (assumed compatible with the two collections).
 626                 /// </summary>
 627                 /// <param name="tit">The first collection</param>
 628                 /// <param name="tat">The second collection</param>
 629                 /// <param name="itemhasher">The item hasher to use for comparison</param>
 630                 /// <returns>True if equal</returns>
 631                 [Tested]
 632                 public static bool StaticEquals(ISequenced<T> tit, ISequenced<T> tat, IHasher<T> itemhasher)
 633                 {
 634                         if (tat == null)
 635                                 return tit == null;
 636
 637                         if (tit.Count != tat.Count)
 638                                 return false;
 639
 640                         //This way we might run through both enumerations twice, but
 641                         //probably not (if the hash codes are good)
 642                         if (tit.GetHashCode() != tat.GetHashCode())
 643                                 return false;
 644
 645                         using (MSG.IEnumerator<T> dat = tat.GetEnumerator(), dit = tit.GetEnumerator())
 646                         {
 647                                 while (dit.MoveNext())
 648                                 {
 649                                         dat.MoveNext();
 650                                         if (!itemhasher.Equals(dit.Current, dat.Current))
 651                                                 return false;
 652                                 }
 653                         }
 654
 655                         return true;
 656                 }
 657
 658
 659                 /// <summary>
 660                 /// Get the sequenced collection hash code of this collection: from the cached
 661                 /// value if present and up to date, else (re)compute.
 662                 /// </summary>
 663                 /// <returns>The hash code</returns>
 664                 protected int sequencedhashcode()
 665                 {
 666                         if (iSequencedHashCodeStamp == stamp)
 667                                 return iSequencedHashCode;
 668
 669                         iSequencedHashCode = ComputeHashCode((ISequenced<T>)this, itemhasher);
 670                         iSequencedHashCodeStamp = stamp;
 671                         return iSequencedHashCode;
 672                 }
 673
 674
 675                 /// <summary>
 676                 /// Check if the contents of that is equal to the contents of this
 677                 /// in the sequenced sense. Using the item hasher of this collection.
 678                 /// </summary>
 679                 /// <param name="that">The collection to compare to.</param>
 680                 /// <returns>True if  equal</returns>
 681                 protected bool sequencedequals(ISequenced<T> that)
 682                 {
 683                         return StaticEquals((ISequenced<T>)this, that, itemhasher);
 684                 }
 685
 686
 687                 #endregion
 688
 689                 /// <summary>
 690                 /// Create an enumerator for this collection.
 691                 /// </summary>
 692                 /// <returns>The enumerator</returns>
 693                 public override abstract MSG.IEnumerator<T> GetEnumerator();
 694
 695
 696                 /// <summary>
 697                 /// <code>Forwards</code> if same, else <code>Backwards</code>
 698                 /// </summary>
 699                 /// <value>The enumeration direction relative to the original collection.</value>
 700                 [Tested]
 701                 public EnumerationDirection Direction { [Tested]get { return EnumerationDirection.Forwards; } }
 702         }
 703
 704
 705         /// <summary>
 706         /// Base class for collection classes of dynamic array type implementations.
 707         /// </summary>
 708         public class ArrayBase<T>: SequencedBase<T>
 709         {
 710                 #region Fields
 711                 /// <summary>
 712                 /// The actual internal array container. Will be extended on demand.
 713                 /// </summary>
 714                 protected T[] array;
 715
 716                 /// <summary>
 717                 /// The offset into the internal array container of the first item. The offset is 0 for a
 718                 /// base dynamic array and may be positive for an updatable view into a base dynamic array.
 719                 /// </summary>
 720                 protected int offset;
 721                 #endregion
 722
 723                 #region Util
 724                 /// <summary>
 725                 /// Double the size of the internal array.
 726                 /// </summary>
 727                 protected virtual void expand()
 728                 {
 729                         expand(2 * array.Length, size);
 730                 }
 731
 732
 733                 /// <summary>
 734                 /// Expand the internal array container.
 735                 /// </summary>
 736                 /// <param name="newcapacity">The new size of the internal array -
 737                 /// will be rounded upwards to a power of 2.</param>
 738                 /// <param name="newsize">The (new) size of the (base) collection.</param>
 739                 protected virtual void expand(int newcapacity, int newsize)
 740                 {
 741                         Debug.Assert(newcapacity >= newsize);
 742
 743                         int newlength = array.Length;
 744
 745                         while (newlength < newcapacity) newlength *= 2;
 746
 747                         T[] newarray = new T[newlength];
 748
 749                         Array.Copy(array, newarray, newsize);
 750                         array = newarray;
 751                 }
 752
 753
 754                 /// <summary>
 755                 /// Insert an item at a specific index, moving items to the right
 756                 /// upwards and expanding the array if necessary.
 757                 /// </summary>
 758                 /// <param name="i">The index at which to insert.</param>
 759                 /// <param name="item">The item to insert.</param>
 760                 protected virtual void insert(int i, T item)
 761                 {
 762                         if (size == array.Length)
 763                                 expand();
 764
 765                         if (i < size)
 766                                 Array.Copy(array, i, array, i + 1, size - i);
 767
 768                         array[i] = item;
 769                         size++;
 770                 }
 771
 772                 #endregion
 773
 774                 #region Constructors
 775
 776                 /// <summary>
 777                 /// Create an empty ArrayBase object.
 778                 /// </summary>
 779                 /// <param name="capacity">The initial capacity of the internal array container.
 780                 /// Will be rounded upwards to the nearest power of 2 greater than or equal to 8.</param>
 781                 /// <param name="hasher">The item hasher to use, primarily for item equality</param>
 782                 public ArrayBase(int capacity, IHasher<T> hasher)
 783                 {
 784                         int newlength = 8;
 785
 786                         while (newlength < capacity) newlength *= 2;
 787
 788                         array = new T[newlength];
 789                         itemhasher = hasher;
 790                 }
 791
 792                 #endregion
 793
 794                 #region IIndexed members
 795
 796                 /// <summary>
 797                 /// <exception cref="IndexOutOfRangeException"/>.
 798                 /// </summary>
 799                 /// <value>The directed collection of items in a specific index interval.</value>
 800                 /// <param name="start">The low index of the interval (inclusive).</param>
 801         /// <param name="count">The size of the range.</param>
 802         [Tested]
 803         public IDirectedCollectionValue<T> this[int start, int count]
 804                 {
 805                         [Tested]
 806                         get
 807                         {
 808                                 checkRange(start, count);
 809                                 return new Range(this, start, count, true);
 810                         }
 811                 }
 812
 813                 #endregion
 814
 815                 #region IEditableCollection members
 816                 /// <summary>
 817                 /// Remove all items and reset size of internal array container.
 818                 /// </summary>
 819                 [Tested]
 820                 public virtual void Clear()
 821                 {
 822                         updatecheck();
 823                         array = new T[8];
 824                         size = 0;
 825                 }
 826
 827
 828                 /// <summary>
 829                 /// Create an array containing (copies) of the items of this collection in enumeration order.
 830                 /// </summary>
 831                 /// <returns>The new array</returns>
 832                 [Tested]
 833                 public override T[] ToArray()
 834                 {
 835                         T[] res = new T[size];
 836
 837                         Array.Copy(array, res, size);
 838                         return res;
 839                 }
 840
 841
 842                 /// <summary>
 843                 /// Perform an internal consistency (invariant) test on the array base.
 844                 /// </summary>
 845                 /// <returns>True if test succeeds.</returns>
 846                 [Tested]
 847                 public virtual bool Check()
 848                 {
 849                         bool retval = true;
 850
 851                         if (size > array.Length)
 852                         {
 853                                 Console.WriteLine("Bad size ({0}) > array.Length ({1})", size, array.Length);
 854                                 return false;
 855                         }
 856
 857                         for (int i = 0; i < size; i++)
 858                         {
 859                                 if ((object)(array[i]) == null)
 860                                 {
 861                                         Console.WriteLine("Bad element: null at index {0}", i);
 862                                         return false;
 863                                 }
 864                         }
 865
 866                         return retval;
 867                 }
 868
 869                 #endregion
 870
 871                 #region IDirectedCollection<T> Members
 872
 873                 /// <summary>
 874                 /// Create a directed collection with the same contents as this one, but
 875                 /// opposite enumeration sequence.
 876                 /// </summary>
 877                 /// <returns>The mirrored collection.</returns>
 878                 [Tested]
 879                 public IDirectedCollectionValue<T> Backwards() { return this[0, size].Backwards(); }
 880
 881                 #endregion
 882
 883                 #region IEnumerable<T> Members
 884                 /// <summary>
 885                 /// Create an enumerator for this array based collection.
 886                 /// </summary>
 887                 /// <returns>The enumerator</returns>
 888                 [Tested]
 889                 public override MSG.IEnumerator<T> GetEnumerator()
 890                 {
 891                         int thestamp = stamp, theend = size + offset, thestart = offset;
 892
 893                         for (int i = thestart; i < theend; i++)
 894                         {
 895                                 modifycheck(thestamp);
 896                                 yield return array[i];
 897                         }
 898                 }
 899                 #endregion
 900
 901                 #region Range nested class
 902                 /// <summary>
 903                 /// A helper class for defining results of interval queries on array based collections.
 904                 /// </summary>
 905                 protected class Range: CollectionValueBase<T>, IDirectedCollectionValue<T>
 906                 {
 907                         int start, count, delta, stamp;
 908
 909                         ArrayBase<T> thebase;
 910
 911
 912                         internal Range(ArrayBase<T> thebase, int start, int count, bool forwards)
 913                         {
 914                                 this.thebase = thebase;  stamp = thebase.stamp;
 915                                 delta = forwards ? 1 : -1;
 916                                 this.start = start + thebase.offset; this.count = count;
 917                         }
 918
 919
 920                         /// <summary>
 921                         ///
 922                         /// </summary>
 923                         /// <value>The number of items in the range</value>
 924                         [Tested]
 925                         public override int Count { [Tested]get { thebase.modifycheck(stamp); return count; } }
 926
 927             /// <summary>
 928             /// The value is symbolic indicating the type of asymptotic complexity
 929             /// in terms of the size of this collection (worst-case or amortized as
 930             /// relevant).
 931             /// </summary>
 932             /// <value>A characterization of the speed of the
 933             /// <code>Count</code> property in this collection.</value>
 934             public override Speed CountSpeed { get { thebase.modifycheck(stamp); return Speed.Constant; } }
 935
 936             /// <summary>
 937                         /// Create an enumerator for this range of an array based collection.
 938                         /// </summary>
 939                         /// <returns>The enumerator</returns>
 940                         [Tested]
 941                         public override MSG.IEnumerator<T> GetEnumerator()
 942                         {
 943                                 for (int i = 0; i < count; i++)
 944                                 {
 945                                         thebase.modifycheck(stamp);
 946                                         yield return thebase.array[start + delta * i];
 947                                 }
 948                         }
 949
 950
 951                         /// <summary>
 952                         /// Create a araay collection range with the same contents as this one, but
 953                         /// opposite enumeration sequence.
 954                         /// </summary>
 955                         /// <returns>The mirrored collection.</returns>
 956                         [Tested]
 957                         public IDirectedCollectionValue<T> Backwards()
 958                         {
 959                                 thebase.modifycheck(stamp);
 960
 961                                 Range res = (Range)MemberwiseClone();
 962
 963                                 res.delta = -delta;
 964                                 res.start = start + (count - 1) * delta;
 965                                 return res;
 966                         }
 967
 968
 969                         IDirectedEnumerable<T> C5.IDirectedEnumerable<T>.Backwards()
 970                         {
 971                                 return Backwards();
 972                         }
 973
 974
 975                         /// <summary>
 976                         /// <code>Forwards</code> if same, else <code>Backwards</code>
 977                         /// </summary>
 978                         /// <value>The enumeration direction relative to the original collection.</value>
 979                         [Tested]
 980                         public EnumerationDirection Direction
 981                         {
 982                                 [Tested]
 983                                 get
 984                                 {
 985                                         thebase.modifycheck(stamp);
 986                                         return delta > 0 ? EnumerationDirection.Forwards : EnumerationDirection.Backwards;
 987                                 }
 988                         }
 989                 }
 990                 #endregion
 991         }
 992
 993         #endregion
 994
 995         #region Sorting
 996         /// <summary>
 997         /// A utility class with functions for sorting arrays with respect to an IComparer&lt;T&gt;
 998         /// </summary>
 999         public class Sorting
1000         {
1001                 /// <summary>
1002                 /// Sort part of array in place using IntroSort
1003                 /// </summary>
1004                 /// <param name="a">Array to sort</param>
1005                 /// <param name="f">Index of first position to sort</param>
1006                 /// <param name="b">Index of first position beyond the part to sort</param>
1007                 /// <param name="c">IComparer&lt;T&gt; to sort by</param>
1008                 [Tested]
1009                 public static void IntroSort<T>(T[] a, int f, int b, IComparer<T> c)
1010                 {
1011                         new Sorter<T>(a, c).IntroSort(f, b);
1012                 }
1013
1014
1015                 /// <summary>
1016                 /// Sort part of array in place using Insertion Sort
1017                 /// </summary>
1018                 /// <param name="a">Array to sort</param>
1019                 /// <param name="f">Index of first position to sort</param>
1020                 /// <param name="b">Index of first position beyond the part to sort</param>
1021                 /// <param name="c">IComparer&lt;T&gt; to sort by</param>
1022                 [Tested]
1023                 public static void InsertionSort<T>(T[] a, int f, int b, IComparer<T> c)
1024                 {
1025                         new Sorter<T>(a, c).InsertionSort(f, b);
1026                 }
1027
1028
1029                 /// <summary>
1030                 /// Sort part of array in place using Heap Sort
1031                 /// </summary>
1032                 /// <param name="a">Array to sort</param>
1033                 /// <param name="f">Index of first position to sort</param>
1034                 /// <param name="b">Index of first position beyond the part to sort</param>
1035                 /// <param name="c">IComparer&lt;T&gt; to sort by</param>
1036                 [Tested]
1037                 public static void HeapSort<T>(T[] a, int f, int b, IComparer<T> c)
1038                 {
1039                         new Sorter<T>(a, c).HeapSort(f, b);
1040                 }
1041
1042
1043                 class Sorter<T>
1044                 {
1045                         T[] a;
1046
1047                         IComparer<T> c;
1048
1049
1050                         internal Sorter(T[] a, IComparer<T> c) { this.a = a; this.c = c; }
1051
1052
1053                         internal void IntroSort(int f, int b)
1054                         {
1055                                 if (b - f > 31)
1056                                 {
1057                                         int depth_limit = (int)Math.Floor(2.5 * Math.Log(b - f, 2));
1058
1059                                         introSort(f, b, depth_limit);
1060                                 }
1061                                 else
1062                                         InsertionSort(f, b);
1063                         }
1064
1065
1066                         private void introSort(int f, int b, int depth_limit)
1067                         {
1068                                 const int size_threshold = 14;//24;
1069
1070                                 if (depth_limit-- == 0)
1071                                         HeapSort(f, b);
1072                                 else if (b - f <= size_threshold)
1073                                         InsertionSort(f, b);
1074                                 else
1075                                 {
1076                                         int p = partition(f, b);
1077
1078                                         introSort(f, p, depth_limit);
1079                                         introSort(p, b, depth_limit);
1080                                 }
1081                         }
1082
1083
1084                         private int compare(T i1, T i2) { return c.Compare(i1, i2); }
1085
1086
1087                         private int partition(int f, int b)
1088                         {
1089                                 int bot = f, mid = (b + f) / 2, top = b - 1;
1090                                 T abot = a[bot], amid = a[mid], atop = a[top];
1091
1092                                 if (compare(abot, amid) < 0)
1093                                 {
1094                                         if (compare(atop, abot) < 0)//atop<abot<amid
1095                                                 { a[top] = amid; amid = a[mid] = abot; a[bot] = atop; }
1096                                         else if (compare(atop, amid) < 0) //abot<=atop<amid
1097                                                 { a[top] = amid; amid = a[mid] = atop; }
1098                                         //else abot<amid<=atop
1099                                 }
1100                                 else
1101                                 {
1102                                         if (compare(amid, atop) > 0) //atop<amid<=abot
1103                                                 { a[bot] = atop; a[top] = abot; }
1104                                         else if (compare(abot, atop) > 0) //amid<=atop<abot
1105                                                 { a[bot] = amid; amid = a[mid] = atop; a[top] = abot; }
1106                                         else //amid<=abot<=atop
1107                                                 { a[bot] = amid; amid = a[mid] = abot; }
1108                                 }
1109
1110                                 int i = bot, j = top;
1111
1112                                 while (true)
1113                                 {
1114                                         while (compare(a[++i], amid) < 0);
1115
1116                                         while (compare(amid, a[--j]) < 0);
1117
1118                                         if (i < j)
1119                                         {
1120                                                 T tmp = a[i]; a[i] = a[j]; a[j] = tmp;
1121                                         }
1122                                         else
1123                                                 return i;
1124                                 }
1125                         }
1126
1127
1128                         internal void InsertionSort(int f, int b)
1129                         {
1130                                 for (int j = f + 1; j < b; j++)
1131                                 {
1132                                         T key = a[j], other;
1133                                         int i = j - 1;
1134
1135                                         if (c.Compare(other = a[i], key) > 0)
1136                                         {
1137                                                 a[j] = other;
1138                                                 while (i > f && c.Compare(other = a[i - 1], key) > 0) { a[i--] = other; }
1139
1140                                                 a[i] = key;
1141                                         }
1142                                 }
1143                         }
1144
1145
1146                         internal void HeapSort(int f, int b)
1147                         {
1148                                 for (int i = (b + f) / 2; i >= f; i--) heapify(f, b, i);
1149
1150                                 for (int i = b - 1; i > f; i--)
1151                                 {
1152                                         T tmp = a[f]; a[f] = a[i]; a[i] = tmp;
1153                                         heapify(f, i, f);
1154                                 }
1155                         }
1156
1157
1158                         private void heapify(int f, int b, int i)
1159                         {
1160                                 T pv = a[i], lv, rv, max = pv;
1161                                 int j = i, maxpt = j;
1162
1163                                 while (true)
1164                                 {
1165                                         int l = 2 * j - f + 1, r = l + 1;
1166
1167                                         if (l < b && compare(lv = a[l], max) > 0) { maxpt = l; max = lv; }
1168
1169                                         if (r < b && compare(rv = a[r], max) > 0) { maxpt = r; max = rv; }
1170
1171                                         if (maxpt == j)
1172                                                 break;
1173
1174                                         a[j] = max;
1175                                         max = pv;
1176                                         j = maxpt;
1177                                 }
1178
1179                                 if (j > i)
1180                                         a[j] = pv;
1181                         }
1182                 }
1183         }
1184
1185         #endregion
1186
1187         #region Random
1188         /// <summary>
1189         /// A modern random number generator based on (whatever)
1190         /// </summary>
1191         public class C5Random : Random
1192         {
1193                 private uint[] Q = new uint[16];
1194
1195                 private uint c = 362436, i = 15;
1196
1197
1198                 private uint Cmwc()
1199                 {
1200                         ulong t, a = 487198574UL;
1201                         uint x, r = 0xfffffffe;
1202
1203                         i = (i + 1) & 15;
1204                         t = a * Q[i] + c;
1205                         c = (uint)(t >> 32);
1206                         x = (uint)(t + c);
1207                         if (x < c)
1208                         {
1209                                 x++;
1210                                 c++;
1211                         }
1212
1213                         return Q[i] = r - x;
1214                 }
1215
1216
1217                 /// <summary>
1218                 /// Get a new random System.Double value
1219                 /// </summary>
1220                 /// <returns>The random double</returns>
1221                 public override double NextDouble()
1222                 {
1223                         return Cmwc() / 4294967296.0;
1224                 }
1225
1226
1227                 /// <summary>
1228                 /// Get a new random System.Double value
1229                 /// </summary>
1230                 /// <returns>The random double</returns>
1231                 protected override double Sample()
1232                 {
1233                         return NextDouble();
1234                 }
1235
1236
1237                 /// <summary>
1238                 /// Get a new random System.Int32 value
1239                 /// </summary>
1240                 /// <returns>The random int</returns>
1241                 public override int Next()
1242                 {
1243                         return (int)Cmwc();
1244                 }
1245
1246
1247                 /// <summary>
1248                 /// Get a random non-negative integer less than a given upper bound
1249                 /// </summary>
1250                 /// <param name="max">The upper bound (exclusive)</param>
1251                 /// <returns></returns>
1252                 public override int Next(int max)
1253                 {
1254                         if (max < 0)
1255                                 throw new ApplicationException("max must be non-negative");
1256
1257                         return (int)(Cmwc() / 4294967296.0 * max);
1258                 }
1259
1260
1261                 /// <summary>
1262                 /// Get a random integer between two given bounds
1263                 /// </summary>
1264                 /// <param name="min">The lower bound (inclusive)</param>
1265                 /// <param name="max">The upper bound (exclusive)</param>
1266                 /// <returns></returns>
1267                 public override int Next(int min, int max)
1268                 {
1269                         if (min > max)
1270                                 throw new ApplicationException("min must be less than or equal to max");
1271
1272                         return min + (int)(Cmwc() / 4294967296.0 * max);
1273                 }
1274
1275                 /// <summary>
1276                 /// Fill a array of byte with random bytes
1277                 /// </summary>
1278                 /// <param name="buffer">The array to fill</param>
1279                 public override void NextBytes(byte[] buffer)
1280                 {
1281                         for (int i = 0, length = buffer.Length; i < length; i++)
1282                                 buffer[i] = (byte)Cmwc();
1283                 }
1284
1285
1286                 /// <summary>
1287                 /// Create a random number generator seed by system time.
1288                 /// </summary>
1289                 public C5Random() : this(DateTime.Now.Ticks)
1290                 {
1291                 }
1292
1293
1294                 /// <summary>
1295                 /// Create a random number generator with a given seed
1296                 /// </summary>
1297                 /// <param name="seed">The seed</param>
1298                 public C5Random(long seed)
1299                 {
1300                         if (seed == 0)
1301                                 throw new ApplicationException("Seed must be non-zero");
1302
1303                         uint j = (uint)(seed & 0xFFFFFFFF);
1304
1305                         for (int i = 0; i < 16; i++)
1306                         {
1307                                 j ^= j << 13;
1308                                 j ^= j >>17;
1309                                 j ^= j << 5;
1310                                 Q[i] = j;
1311                         }
1312
1313                         Q[15] = (uint)(seed ^ (seed >> 32));
1314                 }
1315         }
1316
1317         #endregion
1318
1319         #region Custom code attributes
1320
1321         /// <summary>
1322         /// A custom attribute to mark methods and properties as being tested
1323         /// sufficiently in the regression test suite.
1324         /// </summary>
1325         [AttributeUsage(AttributeTargets.All, AllowMultiple = true)]
1326         public class TestedAttribute: Attribute
1327         {
1328
1329                 /// <summary>
1330                 /// Optional reference to test case
1331                 /// </summary>
1332                 [Tested]
1333                 public string via;
1334
1335
1336                 /// <summary>
1337                 /// Pretty print attribute value
1338                 /// </summary>
1339                 /// <returns>"Tested via " + via</returns>
1340                 [Tested]
1341                 public override string ToString() { return "Tested via " + via; }
1342         }
1343
1344         #endregion
1345 }
1346 #endif