mcs/class/Mono.C5/Collections.cs

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