mcs/class/Mono.C5/Collections.cs

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