mcs/class/Mono.C5/C5/hashing/HashTable.cs

   1 #if NET_2_0
   2 /*\r
   3  Copyright (c) 2003-2006 Niels Kokholm and Peter Sestoft\r
   4  Permission is hereby granted, free of charge, to any person obtaining a copy\r
   5  of this software and associated documentation files (the "Software"), to deal\r
   6  in the Software without restriction, including without limitation the rights\r
   7  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell\r
   8  copies of the Software, and to permit persons to whom the Software is\r
   9  furnished to do so, subject to the following conditions:\r
  10  \r
  11  The above copyright notice and this permission notice shall be included in\r
  12  all copies or substantial portions of the Software.\r
  13  \r
  14  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR\r
  15  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,\r
  16  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE\r
  17  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER\r
  18  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,\r
  19  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE\r
  20  SOFTWARE.\r
  21 */\r
  22 \r
  23 #define LINEARPROBINGnot\r
  24 #define REFBUCKET\r
  25 #define SHRINKnot\r
  26 #define INTERHASHINGnot\r
  27 #define RANDOMINTERHASHING\r
  28 \r
  29 using System;\r
  30 using System.Diagnostics;\r
  31 using SCG = System.Collections.Generic;\r
  32 \r
  33 namespace C5\r
  34 {\r
  35   /// <summary>\r
  36   /// A set collection class based on linear hashing\r
  37   /// </summary>\r
  38   [Serializable]\r
  39   public class HashSet<T> : CollectionBase<T>, ICollection<T>\r
  40   {\r
  41     #region Feature\r
  42     /// <summary>\r
  43     /// Enum class to assist printing of compilation alternatives.\r
  44     /// </summary>\r
  45     [Flags]\r
  46     public enum Feature : short\r
  47     {\r
  48       /// <summary>\r
  49       /// Nothing\r
  50       /// </summary>\r
  51       Dummy = 0,\r
  52       /// <summary>\r
  53       /// Buckets are of reference type\r
  54       /// </summary>\r
  55       RefTypeBucket = 1,\r
  56       /// <summary>\r
  57       /// Primary buckets are of value type\r
  58       /// </summary>\r
  59       ValueTypeBucket = 2,\r
  60       /// <summary>\r
  61       /// Using linear probing to resolve index clashes\r
  62       /// </summary>\r
  63       LinearProbing = 4,\r
  64       /// <summary>\r
  65       /// Shrink table when very sparsely filled\r
  66       /// </summary>\r
  67       ShrinkTable = 8,\r
  68       /// <summary>\r
  69       /// Use chaining to resolve index clashes\r
  70       /// </summary>\r
  71       Chaining = 16,\r
  72       /// <summary>\r
  73       /// Use hash function on item hash code\r
  74       /// </summary>\r
  75       InterHashing = 32,\r
  76       /// <summary>\r
  77       /// Use a universal family of hash functions on item hash code\r
  78       /// </summary>\r
  79       RandomInterHashing = 64\r
  80     }\r
  81 \r
  82 \r
  83 \r
  84     static Feature features = Feature.Dummy\r
  85 #if REFBUCKET\r
  86  | Feature.RefTypeBucket\r
  87 #else\r
  88  | Feature.ValueTypeBucket\r
  89 #endif\r
  90 #if SHRINK\r
  91                 | Feature.ShrinkTable\r
  92 #endif\r
  93 #if LINEARPROBING\r
  94  | Feature.LinearProbing\r
  95 #else\r
  96  | Feature.Chaining\r
  97 #endif\r
  98 #if INTERHASHING\r
  99                 | Feature.InterHashing\r
 100 #elif RANDOMINTERHASHING\r
 101  | Feature.RandomInterHashing\r
 102 #endif\r
 103 ;\r
 104 \r
 105 \r
 106     /// <summary>\r
 107     /// Show which implementation features was chosen at compilation time\r
 108     /// </summary>\r
 109     public static Feature Features { get { return features; } }\r
 110 \r
 111     #endregion\r
 112 \r
 113     #region Fields\r
 114 \r
 115     int indexmask, bits, bitsc, origbits, lastchosen; //bitsc==32-bits; indexmask==(1<<bits)-1;\r
 116 \r
 117     Bucket[] table;\r
 118 \r
 119 #if !REFBUCKET\r
 120     bool defaultvalid = false;\r
 121 \r
 122     T defaultitem;\r
 123 #endif\r
 124     double fillfactor = 0.66;\r
 125 \r
 126     int resizethreshhold;\r
 127 \r
 128 #if RANDOMINTERHASHING\r
 129 #if DEBUG\r
 130     const uint randomhashfactor = 1529784659;\r
 131 #else\r
 132     uint randomhashfactor = (2 * (uint)(new Random()).Next() + 1) * 1529784659;\r
 133 #endif\r
 134 #endif\r
 135 \r
 136     #endregion\r
 137 \r
 138     #region Events\r
 139 \r
 140     /// <summary>\r
 141     /// \r
 142     /// </summary>\r
 143     /// <value></value>\r
 144     public override EventTypeEnum ListenableEvents { get { return EventTypeEnum.Basic; } }\r
 145 \r
 146     #endregion\r
 147 \r
 148     #region Bucket nested class(es)\r
 149 #if REFBUCKET\r
 150     [Serializable]\r
 151     class Bucket\r
 152     {\r
 153       internal T item;\r
 154 \r
 155       internal int hashval; //Cache!\r
 156 \r
 157 #if LINEARPROBING\r
 158       internal Bucket(T item, int hashval)\r
 159       {\r
 160         this.item = item;\r
 161         this.hashval = hashval;\r
 162       }\r
 163 #else\r
 164       internal Bucket overflow;\r
 165 \r
 166       internal Bucket(T item, int hashval, Bucket overflow)\r
 167       {\r
 168         this.item = item;\r
 169         this.hashval = hashval;\r
 170         this.overflow = overflow;\r
 171       }\r
 172 #endif\r
 173     }\r
 174 #else\r
 175     struct Bucket\r
 176     {\r
 177       internal T item;\r
 178 \r
 179       internal int hashval; //Cache!\r
 180 \r
 181 #if LINEARPROBING\r
 182       internal Bucket(T item, int hashval)\r
 183       {\r
 184         this.item = item;\r
 185         this.hashval = hashval;\r
 186       }\r
 187 #else\r
 188                         internal OverflowBucket overflow;\r
 189 \r
 190 \r
 191                         internal Bucket(T item, int hashval)\r
 192                         {\r
 193                                 this.item = item;\r
 194                                 this.hashval = hashval;\r
 195                                 this.overflow = default(OverflowBucket);\r
 196                         }\r
 197 #endif\r
 198     }\r
 199 \r
 200 \r
 201 #if !LINEARPROBING\r
 202                 class OverflowBucket\r
 203                 {\r
 204                         internal T item;\r
 205 \r
 206                         internal int hashval; //Cache!\r
 207 \r
 208                         internal OverflowBucket overflow;\r
 209 \r
 210 \r
 211                         internal OverflowBucket(T item, int hashval, OverflowBucket overflow)\r
 212                         {\r
 213                                 this.item = item;\r
 214                                 this.hashval = hashval;\r
 215                                 this.overflow = overflow;\r
 216                         }\r
 217                 }\r
 218 #endif\r
 219 #endif\r
 220 \r
 221     #endregion\r
 222 \r
 223     #region Basic Util\r
 224 \r
 225     bool equals(T i1, T i2) { return itemequalityComparer.Equals(i1, i2); }\r
 226 \r
 227 #if !REFBUCKET\r
 228     bool isnull(T item) { return itemequalityComparer.Equals(item, default(T)); }\r
 229 #endif\r
 230 \r
 231     int gethashcode(T item) { return itemequalityComparer.GetHashCode(item); }\r
 232 \r
 233 \r
 234     int hv2i(int hashval)\r
 235     {\r
 236 #if INTERHASHING\r
 237                         //Note: *inverse  mod 2^32 is -1503427877\r
 238                         return (int)(((uint)hashval * 1529784659) >>bitsc); \r
 239 #elif RANDOMINTERHASHING\r
 240       return (int)(((uint)hashval * randomhashfactor) >> bitsc);\r
 241 #else\r
 242                         return indexmask & hashval;\r
 243 #endif\r
 244     }\r
 245 \r
 246 \r
 247     void expand()\r
 248     {\r
 249       //Console.WriteLine(String.Format("Expand to {0} bits", bits+1));\r
 250       resize(bits + 1);\r
 251     }\r
 252 \r
 253 \r
 254     void shrink()\r
 255     {\r
 256       if (bits > 3)\r
 257       {\r
 258         //Console.WriteLine(String.Format("Shrink to {0} bits", bits - 1));\r
 259         resize(bits - 1);\r
 260       }\r
 261     }\r
 262 \r
 263 \r
 264     void resize(int bits)\r
 265     {\r
 266       //Console.WriteLine(String.Format("Resize to {0} bits", bits));\r
 267       this.bits = bits;\r
 268       bitsc = 32 - bits;\r
 269       indexmask = (1 << bits) - 1;\r
 270 \r
 271       Bucket[] newtable = new Bucket[indexmask + 1];\r
 272 \r
 273       for (int i = 0, s = table.Length; i < s; i++)\r
 274       {\r
 275         Bucket b = table[i];\r
 276 \r
 277 #if LINEARPROBING\r
 278 #if REFBUCKET\r
 279         if (b != null)\r
 280         {\r
 281           int j = hv2i(b.hashval);\r
 282 \r
 283           while (newtable[j] != null) { j = indexmask & (j + 1); }\r
 284 \r
 285           newtable[j] = b;\r
 286         }\r
 287 #else\r
 288         if (!isnull(b.item))\r
 289         {\r
 290           int j = hv2i(b.hashval);\r
 291 \r
 292           while (!isnull(newtable[j].item)) { j = indexmask & (j + 1); }\r
 293 \r
 294           newtable[j] = b;\r
 295         }\r
 296 #endif\r
 297 #else\r
 298 #if REFBUCKET\r
 299         while (b != null)\r
 300         {\r
 301           int j = hv2i(b.hashval);\r
 302 \r
 303           newtable[j] = new Bucket(b.item, b.hashval, newtable[j]);\r
 304           b = b.overflow;\r
 305         }\r
 306 #else\r
 307                                 if (!isnull(b.item))\r
 308                                 {\r
 309                                         insert(b.item, b.hashval, newtable);\r
 310 \r
 311                                         OverflowBucket ob = b.overflow;\r
 312 \r
 313                                         while (ob != null)\r
 314                                         {\r
 315                                                 insert(ob.item, ob.hashval, newtable);\r
 316                                                 ob = ob.overflow;\r
 317                                         }\r
 318                                 }\r
 319 #endif\r
 320 #endif\r
 321       }\r
 322 \r
 323       table = newtable;\r
 324       resizethreshhold = (int)(table.Length * fillfactor);\r
 325       //Console.WriteLine(String.Format("Resize to {0} bits done", bits));\r
 326     }\r
 327 \r
 328 #if REFBUCKET\r
 329 #else\r
 330 #if LINEARPROBING\r
 331 #else\r
 332                 //Only for resize!!!\r
 333                 private void insert(T item, int hashval, Bucket[] t)\r
 334                 {\r
 335                         int i = hv2i(hashval);\r
 336                         Bucket b = t[i];\r
 337 \r
 338                         if (!isnull(b.item))\r
 339                         {\r
 340                                 t[i].overflow = new OverflowBucket(item, hashval, b.overflow);\r
 341                         }\r
 342                         else\r
 343                                 t[i] = new Bucket(item, hashval);\r
 344                 }\r
 345 #endif\r
 346 #endif\r
 347 \r
 348     /// <summary>\r
 349     /// Search for an item equal (according to itemequalityComparer) to the supplied item.  \r
 350     /// </summary>\r
 351     /// <param name="item"></param>\r
 352     /// <param name="add">If true, add item to table if not found.</param>\r
 353     /// <param name="update">If true, update table entry if item found.</param>\r
 354     /// <param name="raise">If true raise events</param>\r
 355     /// <returns>True if found</returns>\r
 356     private bool searchoradd(ref T item, bool add, bool update, bool raise)\r
 357     {\r
 358 \r
 359 #if LINEARPROBING\r
 360 #if REFBUCKET\r
 361       int hashval = gethashcode(item);\r
 362       int i = hv2i(hashval);\r
 363       Bucket b = table[i];\r
 364 \r
 365       while (b != null)\r
 366       {\r
 367         T olditem = b.item;\r
 368         if (equals(olditem, item))\r
 369         {\r
 370           if (update)\r
 371             b.item = item;\r
 372           else\r
 373             item = olditem;\r
 374 \r
 375           if (raise && update)\r
 376             raiseForUpdate(item, olditem);\r
 377           return true;\r
 378         }\r
 379 \r
 380         b = table[i = indexmask & (i + 1)];\r
 381       }\r
 382 \r
 383       if (!add) goto notfound;\r
 384 \r
 385       table[i] = new Bucket(item, hashval);\r
 386 \r
 387 #else\r
 388       if (isnull(item))\r
 389       {\r
 390         if (defaultvalid)\r
 391         {\r
 392           T olditem = defaultitem;\r
 393           if (update)\r
 394             defaultitem = item;\r
 395           else\r
 396             item = defaultitem;\r
 397 \r
 398           if (raise && update)\r
 399             raiseForUpdate(item, olditem);\r
 400           return true;\r
 401         }\r
 402 \r
 403         if (!add) goto notfound;\r
 404 \r
 405         defaultvalid = true;\r
 406         defaultitem = item;\r
 407       }\r
 408       else\r
 409       {\r
 410         int hashval = gethashcode(item);\r
 411         int i = hv2i(hashval);\r
 412         T t = table[i].item;\r
 413 \r
 414         while (!isnull(t))\r
 415         {\r
 416           if (equals(t, item))\r
 417           {\r
 418             if (update)\r
 419               table[i].item = item;\r
 420             else\r
 421               item = t;\r
 422 \r
 423             if (raise && update)\r
 424               raiseForUpdate(item, t);\r
 425             return true;\r
 426           }\r
 427 \r
 428           t = table[i = indexmask & (i + 1)].item;\r
 429         }\r
 430 \r
 431         if (!add) goto notfound;\r
 432 \r
 433         table[i] = new Bucket(item, hashval);\r
 434       }\r
 435 #endif\r
 436 #else\r
 437 #if REFBUCKET\r
 438       int hashval = gethashcode(item);\r
 439       int i = hv2i(hashval);\r
 440       Bucket b = table[i], bold = null;\r
 441 \r
 442       if (b != null)\r
 443       {\r
 444         while (b != null)\r
 445         {\r
 446           T olditem = b.item;\r
 447           if (equals(olditem, item))\r
 448           {\r
 449             if (update)\r
 450             {\r
 451               b.item = item;\r
 452             }\r
 453             item = b.item;\r
 454 \r
 455             if (raise && update)\r
 456               raiseForUpdate(item, olditem);\r
 457             return true;\r
 458           }\r
 459 \r
 460           bold = b;\r
 461           b = b.overflow;\r
 462         }\r
 463 \r
 464         if (!add) goto notfound;\r
 465 \r
 466         bold.overflow = new Bucket(item, hashval, null);\r
 467       }\r
 468       else\r
 469       {\r
 470         if (!add) goto notfound;\r
 471 \r
 472         table[i] = new Bucket(item, hashval, null);\r
 473       }\r
 474 #else\r
 475                         if (isnull(item))\r
 476                         {\r
 477         if (defaultvalid)\r
 478         {\r
 479           T olditem = defaultitem;\r
 480           if (update)\r
 481             defaultitem = item;\r
 482           else\r
 483             item = defaultitem;\r
 484 \r
 485           if (raise && update)\r
 486             raiseForUpdate(item, olditem);\r
 487           return true;\r
 488         }\r
 489 \r
 490                                 if (!add) goto notfound;\r
 491 \r
 492                                 defaultvalid = true;\r
 493                                 defaultitem = item;\r
 494                         }\r
 495                         else\r
 496                         {\r
 497                                 int hashval = gethashcode(item);\r
 498                                 int i = hv2i(hashval);\r
 499                                 Bucket b = table[i];\r
 500 \r
 501                                 if (!isnull(b.item))\r
 502                                 {\r
 503                                         if (equals(b.item, item))\r
 504                                         {\r
 505                                                 if (update)\r
 506                                                         table[i].item = item;\r
 507                                                 else\r
 508                                                         item = b.item;\r
 509 \r
 510             if (raise && update)\r
 511               raiseForUpdate(item, b.item);\r
 512             return true;\r
 513                                         }\r
 514 \r
 515                                         OverflowBucket ob = table[i].overflow;\r
 516 \r
 517                                         if (ob == null)\r
 518                                         {\r
 519                                                 if (!add) goto notfound;\r
 520 \r
 521                                                 table[i].overflow = new OverflowBucket(item, hashval, null);\r
 522                                         }\r
 523                                         else\r
 524                                         {\r
 525             T olditem = ob.item;\r
 526                                                 while (ob.overflow != null)\r
 527                                                 {\r
 528               if (equals(item, olditem))\r
 529               {\r
 530                 if (update)\r
 531                   ob.item = item;\r
 532                 else\r
 533                   item = olditem;\r
 534 \r
 535                 if (raise && update)\r
 536                   raiseForUpdate(item, olditem);\r
 537                 return true;\r
 538               }\r
 539 \r
 540                                                         ob = ob.overflow;\r
 541               olditem = ob.item;\r
 542                                                 }\r
 543 \r
 544             if (equals(item, olditem))\r
 545             {\r
 546               if (update)\r
 547                 ob.item = item;\r
 548               else\r
 549                 item = olditem;\r
 550 \r
 551               if (raise && update)\r
 552                 raiseForUpdate(item, olditem);\r
 553               return true;\r
 554             }\r
 555 \r
 556                                                 if (!add) goto notfound;\r
 557 \r
 558                                                 ob.overflow = new OverflowBucket(item, hashval, null);\r
 559                                         }\r
 560                                 }\r
 561                                 else\r
 562                                 {\r
 563                                         if (!add) goto notfound;\r
 564 \r
 565                                         table[i] = new Bucket(item, hashval);\r
 566                                 }\r
 567                         }\r
 568 #endif\r
 569 #endif\r
 570       size++;\r
 571       if (size > resizethreshhold)\r
 572         expand();\r
 573     notfound:\r
 574       if (raise && add)\r
 575         raiseForAdd(item);\r
 576       return false;\r
 577     }\r
 578 \r
 579 \r
 580     private bool remove(ref T item)\r
 581     {\r
 582 \r
 583       if (size == 0)\r
 584         return false;\r
 585 #if LINEARPROBING\r
 586 #if REFBUCKET\r
 587       int hashval = gethashcode(item);\r
 588       int index = hv2i(hashval);\r
 589       Bucket b = table[index];\r
 590 \r
 591       while (b != null)\r
 592       {\r
 593         if (equals(item, b.item))\r
 594         {\r
 595           //ref\r
 596           item = table[index].item;\r
 597           table[index] = null;\r
 598 \r
 599           //Algorithm R\r
 600           int j = (index + 1) & indexmask;\r
 601 \r
 602           b = table[j];\r
 603           while (b != null)\r
 604           {\r
 605             int k = hv2i(b.hashval);\r
 606 \r
 607             if ((k <= index && index < j) || (index < j && j < k) || (j < k && k <= index))\r
 608             //if (index > j ? (j < k && k <= index): (k <= index || j < k) )\r
 609             {\r
 610               table[index] = b;\r
 611               table[j] = null;\r
 612               index = j;\r
 613             }\r
 614 \r
 615             j = (j + 1) & indexmask;\r
 616             b = table[j];\r
 617           }\r
 618 \r
 619           goto found;\r
 620         }\r
 621 \r
 622         b = table[index = indexmask & (index + 1)];\r
 623       }\r
 624       return false;\r
 625 #else\r
 626       if (isnull(item))\r
 627       {\r
 628         if (!defaultvalid)\r
 629           return false;\r
 630 \r
 631         //ref\r
 632         item = defaultitem;\r
 633         defaultvalid = false;\r
 634         defaultitem = default(T); //No spaceleaks!\r
 635       }\r
 636       else\r
 637       {\r
 638         int hashval = gethashcode(item);\r
 639         int index = hv2i(hashval);\r
 640         T t = table[index].item;\r
 641 \r
 642         while (!isnull(t))\r
 643         {\r
 644           if (equals(item, t))\r
 645           {\r
 646             //ref\r
 647             item = table[index].item;\r
 648             table[index].item = default(T);\r
 649 \r
 650             //algorithm R\r
 651             int j = (index + 1) & indexmask;\r
 652             Bucket b = table[j];\r
 653 \r
 654             while (!isnull(b.item))\r
 655             {\r
 656               int k = hv2i(b.hashval);\r
 657 \r
 658               if ((k <= index && index < j) || (index < j && j < k) || (j < k && k <= index))\r
 659               {\r
 660                 table[index] = b;\r
 661                 table[j].item = default(T);\r
 662                 index = j;\r
 663               }\r
 664 \r
 665               j = (j + 1) & indexmask;\r
 666               b = table[j];\r
 667             }\r
 668 \r
 669             goto found;\r
 670           }\r
 671 \r
 672           t = table[index = indexmask & (index + 1)].item;\r
 673         }\r
 674 \r
 675         return false;\r
 676       }\r
 677 #endif\r
 678     found:\r
 679 #else\r
 680 #if REFBUCKET\r
 681       int hashval = gethashcode(item);\r
 682       int index = hv2i(hashval);\r
 683       Bucket b = table[index], bold;\r
 684 \r
 685       if (b == null)\r
 686         return false;\r
 687 \r
 688       if (equals(item, b.item))\r
 689       {\r
 690         //ref\r
 691         item = b.item;\r
 692         table[index] = b.overflow;\r
 693       }\r
 694       else\r
 695       {\r
 696         bold = b;\r
 697         b = b.overflow;\r
 698         while (b != null && !equals(item, b.item))\r
 699         {\r
 700           bold = b;\r
 701           b = b.overflow;\r
 702         }\r
 703 \r
 704         if (b == null)\r
 705           return false;\r
 706 \r
 707         //ref\r
 708         item = b.item;\r
 709         bold.overflow = b.overflow;\r
 710       }\r
 711 \r
 712 #else\r
 713                         if (isnull(item))\r
 714                         {\r
 715                                 if (!defaultvalid)\r
 716                                         return false;\r
 717 \r
 718                                 //ref\r
 719                                 item = defaultitem;\r
 720                                 defaultvalid = false;\r
 721                                 defaultitem = default(T); //No spaceleaks!\r
 722                         }\r
 723                         else\r
 724                         {\r
 725                                 int hashval = gethashcode(item);\r
 726                                 int index = hv2i(hashval);\r
 727                                 Bucket b = table[index];\r
 728                                 OverflowBucket ob = b.overflow;\r
 729 \r
 730                                 if (equals(item, b.item))\r
 731                                 {\r
 732                                         //ref\r
 733                                         item = b.item;\r
 734                                         if (ob == null)\r
 735                                         {\r
 736                                                 table[index] = new Bucket();\r
 737                                         }\r
 738                                         else\r
 739                                         {\r
 740                                                 b = new Bucket(ob.item, ob.hashval);\r
 741                                                 b.overflow = ob.overflow;\r
 742                                                 table[index] = b;\r
 743                                         }\r
 744                                 }\r
 745                                 else\r
 746                                 {\r
 747                                         if (ob == null)\r
 748                                                 return false;\r
 749 \r
 750                                         if (equals(item, ob.item)) \r
 751                                         {\r
 752                                                 //ref\r
 753                                                 item=ob.item;\r
 754                                                 table[index].overflow = ob.overflow;\r
 755                                         }\r
 756                                         else\r
 757                                         {\r
 758                                                 while (ob.overflow != null)\r
 759                                                         if (equals(item, ob.overflow.item))\r
 760                                                         {\r
 761                                                                 //ref\r
 762                                                                 item = ob.overflow.item;\r
 763                                                                 break;\r
 764                                                         }\r
 765                                                         else\r
 766                                                                 ob = ob.overflow;\r
 767 \r
 768                                                 if (ob.overflow == null)\r
 769                                                         return false;\r
 770 \r
 771                                                 ob.overflow = ob.overflow.overflow;\r
 772                                         }\r
 773                                 }\r
 774                         }\r
 775 #endif\r
 776 #endif\r
 777       size--;\r
 778 \r
 779       return true;\r
 780     }\r
 781 \r
 782 \r
 783     private void clear()\r
 784     {\r
 785       bits = origbits;\r
 786       bitsc = 32 - bits;\r
 787       indexmask = (1 << bits) - 1;\r
 788       size = 0;\r
 789       table = new Bucket[indexmask + 1];\r
 790       resizethreshhold = (int)(table.Length * fillfactor);\r
 791 #if !REFBUCKET\r
 792       defaultitem = default(T);\r
 793       defaultvalid = false;\r
 794 #endif\r
 795     }\r
 796 \r
 797     #endregion\r
 798 \r
 799     #region Constructors\r
 800     /// <summary>\r
 801     /// Create a hash set with natural item equalityComparer and default fill threshold (66%)\r
 802     /// and initial table size (16).\r
 803     /// </summary>\r
 804     public HashSet() \r
 805                         : this(EqualityComparer<T>.Default) { }\r
 806 \r
 807 \r
 808     /// <summary>\r
 809     /// Create a hash set with external item equalityComparer and default fill threshold (66%)\r
 810     /// and initial table size (16).\r
 811     /// </summary>\r
 812     /// <param name="itemequalityComparer">The external item equalityComparer</param>\r
 813     public HashSet(SCG.IEqualityComparer<T> itemequalityComparer) \r
 814                         : this(16, itemequalityComparer) { }\r
 815 \r
 816 \r
 817     /// <summary>\r
 818     /// Create a hash set with external item equalityComparer and default fill threshold (66%)\r
 819     /// </summary>\r
 820     /// <param name="capacity">Initial table size (rounded to power of 2, at least 16)</param>\r
 821     /// <param name="itemequalityComparer">The external item equalityComparer</param>\r
 822     public HashSet(int capacity, SCG.IEqualityComparer<T> itemequalityComparer) \r
 823                         : this(capacity, 0.66, itemequalityComparer) { }\r
 824 \r
 825 \r
 826     /// <summary>\r
 827     /// Create a hash set with external item equalityComparer.\r
 828     /// </summary>\r
 829     /// <param name="capacity">Initial table size (rounded to power of 2, at least 16)</param>\r
 830     /// <param name="fill">Fill threshold (in range 10% to 90%)</param>\r
 831     /// <param name="itemequalityComparer">The external item equalityComparer</param>\r
 832     public HashSet(int capacity, double fill, SCG.IEqualityComparer<T> itemequalityComparer) : base(itemequalityComparer)\r
 833     {\r
 834       if (fill < 0.1 || fill > 0.9)\r
 835         throw new ArgumentException("Fill outside valid range [0.1, 0.9]");\r
 836       if (capacity <= 0)\r
 837         throw new ArgumentException("Capacity must be non-negative");\r
 838       //this.itemequalityComparer = itemequalityComparer;\r
 839       origbits = 4;\r
 840       while (capacity - 1 >> origbits > 0) origbits++;\r
 841       clear();\r
 842     }\r
 843 \r
 844 \r
 845 \r
 846     #endregion\r
 847 \r
 848     #region IEditableCollection<T> Members\r
 849 \r
 850     /// <summary>\r
 851     /// The complexity of the Contains operation\r
 852     /// </summary>\r
 853     /// <value>Always returns Speed.Constant</value>\r
 854     [Tested]\r
 855     public virtual Speed ContainsSpeed { [Tested]get { return Speed.Constant; } }\r
 856 \r
 857     /// <summary>\r
 858     /// Check if an item is in the set \r
 859     /// </summary>\r
 860     /// <param name="item">The item to look for</param>\r
 861     /// <returns>True if set contains item</returns>\r
 862     [Tested]\r
 863     public virtual bool Contains(T item) { return searchoradd(ref item, false, false, false); }\r
 864 \r
 865 \r
 866     /// <summary>\r
 867     /// Check if an item (collection equal to a given one) is in the set and\r
 868     /// if so report the actual item object found.\r
 869     /// </summary>\r
 870     /// <param name="item">On entry, the item to look for.\r
 871     /// On exit the item found, if any</param>\r
 872     /// <returns>True if set contains item</returns>\r
 873     [Tested]\r
 874     public virtual bool Find(ref T item) { return searchoradd(ref item, false, false, false); }\r
 875 \r
 876 \r
 877     /// <summary>\r
 878     /// Check if an item (collection equal to a given one) is in the set and\r
 879     /// if so replace the item object in the set with the supplied one.\r
 880     /// </summary>\r
 881     /// <param name="item">The item object to update with</param>\r
 882     /// <returns>True if item was found (and updated)</returns>\r
 883     [Tested]\r
 884     public virtual bool Update(T item)\r
 885     { updatecheck(); return searchoradd(ref item, false, true, true); }\r
 886 \r
 887     /// <summary>\r
 888     /// Check if an item (collection equal to a given one) is in the set and\r
 889     /// if so replace the item object in the set with the supplied one.\r
 890     /// </summary>\r
 891     /// <param name="item">The item object to update with</param>\r
 892     /// <param name="olditem"></param>\r
 893     /// <returns>True if item was found (and updated)</returns>\r
 894     public virtual bool Update(T item, out T olditem)\r
 895     { updatecheck(); olditem = item; return searchoradd(ref olditem, false, true, true); }\r
 896 \r
 897 \r
 898     /// <summary>\r
 899     /// Check if an item (collection equal to a given one) is in the set.\r
 900     /// If found, report the actual item object in the set,\r
 901     /// else add the supplied one.\r
 902     /// </summary>\r
 903     /// <param name="item">On entry, the item to look for or add.\r
 904     /// On exit the actual object found, if any.</param>\r
 905     /// <returns>True if item was found</returns>\r
 906     [Tested]\r
 907     public virtual bool FindOrAdd(ref T item)\r
 908     { updatecheck(); return searchoradd(ref item, true, false, true); }\r
 909 \r
 910 \r
 911     /// <summary>\r
 912     /// Check if an item (collection equal to a supplied one) is in the set and\r
 913     /// if so replace the item object in the set with the supplied one; else\r
 914     /// add the supplied one.\r
 915     /// </summary>\r
 916     /// <param name="item">The item to look for and update or add</param>\r
 917     /// <returns>True if item was updated</returns>\r
 918     [Tested]\r
 919     public virtual bool UpdateOrAdd(T item)\r
 920     { updatecheck(); return searchoradd(ref item, true, true, true); }\r
 921 \r
 922 \r
 923     /// <summary>\r
 924     /// Check if an item (collection equal to a supplied one) is in the set and\r
 925     /// if so replace the item object in the set with the supplied one; else\r
 926     /// add the supplied one.\r
 927     /// </summary>\r
 928     /// <param name="item">The item to look for and update or add</param>\r
 929     /// <param name="olditem"></param>\r
 930     /// <returns>True if item was updated</returns>\r
 931     public virtual bool UpdateOrAdd(T item, out T olditem)\r
 932     { updatecheck(); olditem = item; return searchoradd(ref olditem, true, true, true); }\r
 933 \r
 934 \r
 935     /// <summary>\r
 936     /// Remove an item from the set\r
 937     /// </summary>\r
 938     /// <param name="item">The item to remove</param>\r
 939     /// <returns>True if item was (found and) removed </returns>\r
 940     [Tested]\r
 941     public virtual bool Remove(T item)\r
 942     {\r
 943       updatecheck();\r
 944       if (remove(ref item))\r
 945       {\r
 946 #if SHRINK\r
 947                                 if (size<resizethreshhold/2 && resizethreshhold>8)\r
 948                                         shrink();\r
 949 #endif\r
 950         raiseForRemove(item);\r
 951         return true;\r
 952       }\r
 953       else\r
 954         return false;\r
 955     }\r
 956 \r
 957 \r
 958     /// <summary>\r
 959     /// Remove an item from the set, reporting the actual matching item object.\r
 960     /// </summary>\r
 961     /// <param name="item">The value to remove.</param>\r
 962     /// <param name="removeditem">The removed value.</param>\r
 963     /// <returns>True if item was found.</returns>\r
 964     [Tested]\r
 965     public virtual bool Remove(T item, out T removeditem)\r
 966     {\r
 967       updatecheck();\r
 968       removeditem = item;\r
 969       if (remove(ref removeditem))\r
 970       {\r
 971 #if SHRINK\r
 972                                 if (size<resizethreshhold/2 && resizethreshhold>8)\r
 973                                         shrink();\r
 974 #endif\r
 975         raiseForRemove(removeditem);\r
 976         return true;\r
 977       }\r
 978       else\r
 979         return false;\r
 980     }\r
 981 \r
 982 \r
 983     /// <summary>\r
 984     /// Remove all items in a supplied collection from this set.\r
 985     /// </summary>\r
 986     /// <typeparam name="U"></typeparam>\r
 987     /// <param name="items">The items to remove.</param>\r
 988     [Tested]\r
 989     public virtual void RemoveAll<U>(SCG.IEnumerable<U> items) where U : T\r
 990     {\r
 991       updatecheck();\r
 992       RaiseForRemoveAllHandler raiseHandler = new RaiseForRemoveAllHandler(this);\r
 993       bool raise = raiseHandler.MustFire;\r
 994       T jtem;\r
 995       foreach (U item in items)\r
 996       { jtem = item; if (remove(ref jtem) && raise) raiseHandler.Remove(jtem); }\r
 997 #if SHRINK\r
 998                         if (size < resizethreshhold / 2 && resizethreshhold > 16)\r
 999                         {\r
1000                                 int newlength = table.Length;\r
1001 \r
1002                                 while (newlength >= 32 && newlength * fillfactor / 2 > size)\r
1003                                         newlength /= 2;\r
1004 \r
1005                                 resize(newlength - 1);\r
1006                         }\r
1007 #endif\r
1008       if (raise) raiseHandler.Raise();\r
1009     }\r
1010 \r
1011     /// <summary>\r
1012     /// Remove all items from the set, resetting internal table to initial size.\r
1013     /// </summary>\r
1014     [Tested]\r
1015     public virtual void Clear()\r
1016     {\r
1017       updatecheck();\r
1018       int oldsize = size;\r
1019       clear();\r
1020       if (ActiveEvents != 0 && oldsize > 0)\r
1021       {\r
1022         raiseCollectionCleared(true, oldsize);\r
1023         raiseCollectionChanged();\r
1024       }\r
1025     }\r
1026 \r
1027 \r
1028     /// <summary>\r
1029     /// Remove all items *not* in a supplied collection from this set.\r
1030     /// </summary>\r
1031     /// <typeparam name="U"></typeparam>\r
1032     /// <param name="items">The items to retain</param>\r
1033     [Tested]\r
1034     public virtual void RetainAll<U>(SCG.IEnumerable<U> items) where U : T\r
1035     {\r
1036       updatecheck();\r
1037 \r
1038       HashSet<T> aux = new HashSet<T>(EqualityComparer);\r
1039 \r
1040       //This only works for sets:\r
1041       foreach (U item in items)\r
1042         if (Contains(item))\r
1043         {\r
1044           T jtem = item;\r
1045 \r
1046           aux.searchoradd(ref jtem, true, false, false);\r
1047         }\r
1048 \r
1049       if (size == aux.size)\r
1050         return;\r
1051 \r
1052       CircularQueue<T> wasRemoved = null;\r
1053       if ((ActiveEvents & EventTypeEnum.Removed) != 0)\r
1054       {\r
1055         wasRemoved = new CircularQueue<T>();\r
1056         foreach (T item in this)\r
1057           if (!aux.Contains(item))\r
1058             wasRemoved.Enqueue(item);\r
1059       }\r
1060 \r
1061       table = aux.table;\r
1062       size = aux.size;\r
1063 #if !REFBUCKET\r
1064       defaultvalid = aux.defaultvalid;\r
1065       defaultitem = aux.defaultitem;\r
1066 #endif\r
1067       indexmask = aux.indexmask;\r
1068       resizethreshhold = aux.resizethreshhold;\r
1069 \r
1070 \r
1071       if ((ActiveEvents & EventTypeEnum.Removed) != 0)\r
1072         raiseForRemoveAll(wasRemoved);\r
1073       else if ((ActiveEvents & EventTypeEnum.Changed) != 0)\r
1074         raiseCollectionChanged();\r
1075     }\r
1076 \r
1077     /// <summary>\r
1078     /// Check if all items in a supplied collection is in this set\r
1079     /// (ignoring multiplicities). \r
1080     /// </summary>\r
1081     /// <param name="items">The items to look for.</param>\r
1082     /// <typeparam name="U"></typeparam>\r
1083     /// <returns>True if all items are found.</returns>\r
1084     [Tested]\r
1085     public virtual bool ContainsAll<U>(SCG.IEnumerable<U> items) where U : T\r
1086     {\r
1087       foreach (U item in items)\r
1088         if (!Contains(item))\r
1089           return false;\r
1090       return true;\r
1091     }\r
1092 \r
1093 \r
1094     /// <summary>\r
1095     /// Create an array containing all items in this set (in enumeration order).\r
1096     /// </summary>\r
1097     /// <returns>The array</returns>\r
1098     [Tested]\r
1099     public override T[] ToArray()\r
1100     {\r
1101       T[] res = new T[size];\r
1102       int index = 0;\r
1103 \r
1104 #if !REFBUCKET\r
1105       if (defaultvalid)\r
1106         res[index++] = defaultitem;\r
1107 #endif\r
1108       for (int i = 0; i < table.Length; i++)\r
1109       {\r
1110         Bucket b = table[i];\r
1111 #if LINEARPROBING\r
1112 #if REFBUCKET\r
1113         if (b != null)\r
1114           res[index++] = b.item;\r
1115 #else\r
1116         if (!isnull(b.item))\r
1117           res[index++] = b.item;\r
1118 #endif\r
1119 #else\r
1120 #if REFBUCKET\r
1121         while (b != null)\r
1122         {\r
1123           res[index++] = b.item;\r
1124           b = b.overflow;\r
1125         }\r
1126 #else\r
1127                                 if (!isnull(b.item))\r
1128                                 {\r
1129                                         res[index++] = b.item;\r
1130 \r
1131                                         OverflowBucket ob = b.overflow;\r
1132 \r
1133                                         while (ob != null)\r
1134                                         {\r
1135                                                 res[index++] = ob.item;\r
1136                                                 ob = ob.overflow;\r
1137                                         }\r
1138                                 }\r
1139 #endif\r
1140 #endif\r
1141       }\r
1142 \r
1143       Debug.Assert(size == index);\r
1144       return res;\r
1145     }\r
1146 \r
1147 \r
1148     /// <summary>\r
1149     /// Count the number of times an item is in this set (either 0 or 1).\r
1150     /// </summary>\r
1151     /// <param name="item">The item to look for.</param>\r
1152     /// <returns>1 if item is in set, 0 else</returns>\r
1153     [Tested]\r
1154     public virtual int ContainsCount(T item) { return Contains(item) ? 1 : 0; }\r
1155 \r
1156     /// <summary>\r
1157     /// \r
1158     /// </summary>\r
1159     /// <returns></returns>\r
1160     public virtual ICollectionValue<T> UniqueItems() { return this; }\r
1161 \r
1162     /// <summary>\r
1163     /// \r
1164     /// </summary>\r
1165     /// <returns></returns>\r
1166     public virtual ICollectionValue<KeyValuePair<T, int>> ItemMultiplicities()\r
1167     {\r
1168       return new MultiplicityOne<T>(this);\r
1169     }\r
1170 \r
1171     /// <summary>\r
1172     /// Remove all (at most 1) copies of item from this set.\r
1173     /// </summary>\r
1174     /// <param name="item">The item to remove</param>\r
1175     [Tested]\r
1176     public virtual void RemoveAllCopies(T item) { Remove(item); }\r
1177 \r
1178     #endregion\r
1179 \r
1180     #region IEnumerable<T> Members\r
1181 \r
1182 \r
1183     /// <summary>\r
1184     /// Choose some item of this collection. \r
1185     /// </summary>\r
1186     /// <exception cref="NoSuchItemException">if collection is empty.</exception>\r
1187     /// <returns></returns>\r
1188     [Tested]\r
1189     public override T Choose()\r
1190     {\r
1191       int len = table.Length;\r
1192       if (size == 0)\r
1193         throw new NoSuchItemException();\r
1194 #if REFBUCKET\r
1195       do { if (++lastchosen >= len) lastchosen = 0; } while (table[lastchosen] == null);\r
1196 #else\r
1197       if (defaultvalid) return defaultitem;\r
1198       do { if (++lastchosen >= len) lastchosen = 0; } while (isnull(table[lastchosen].item));\r
1199 #endif\r
1200       return table[lastchosen].item;\r
1201     }\r
1202 \r
1203     /// <summary>\r
1204     /// Create an enumerator for this set.\r
1205     /// </summary>\r
1206     /// <returns>The enumerator</returns>\r
1207     [Tested]\r
1208     public override SCG.IEnumerator<T> GetEnumerator()\r
1209     {\r
1210       int index = -1;\r
1211       int mystamp = stamp;\r
1212       int len = table.Length;\r
1213 \r
1214 #if LINEARPROBING\r
1215 #if REFBUCKET\r
1216       while (++index < len)\r
1217       {\r
1218         if (mystamp != stamp) throw new CollectionModifiedException();\r
1219 \r
1220         if (table[index] != null) yield return table[index].item;\r
1221       }\r
1222 #else\r
1223       if (defaultvalid)\r
1224         yield return defaultitem;\r
1225 \r
1226       while (++index < len)\r
1227       {\r
1228         if (mystamp != stamp) throw new CollectionModifiedException();\r
1229 \r
1230         T item = table[index].item;\r
1231 \r
1232         if (!isnull(item)) yield return item;\r
1233       }\r
1234 #endif\r
1235 #else\r
1236 #if REFBUCKET\r
1237       Bucket b = null;\r
1238 #else\r
1239                         OverflowBucket ob = null;\r
1240 \r
1241                         if (defaultvalid)\r
1242                                 yield return defaultitem;\r
1243 #endif\r
1244       while (true)\r
1245       {\r
1246         if (mystamp != stamp)\r
1247           throw new CollectionModifiedException();\r
1248 \r
1249 #if REFBUCKET\r
1250         if (b == null || b.overflow == null)\r
1251         {\r
1252           do\r
1253           {\r
1254             if (++index >= len) yield break;\r
1255           } while (table[index] == null);\r
1256 \r
1257           b = table[index];\r
1258           yield return b.item;\r
1259         }\r
1260         else\r
1261         {\r
1262           b = b.overflow;\r
1263           yield return b.item;\r
1264         }\r
1265 #else\r
1266                                 if (ob != null && ob.overflow != null)\r
1267                                 {\r
1268                                         ob = ob.overflow;\r
1269                                         yield return ob.item;\r
1270                                 }\r
1271                                 else if (index >= 0 && ob == null && (ob = table[index].overflow) != null)\r
1272                                 {\r
1273                                         yield return  ob.item;\r
1274                                 }\r
1275                                 else\r
1276                                 {\r
1277                                         do\r
1278                                         {\r
1279                                                 if (++index >= len) yield break;\r
1280                                         } while (isnull(table[index].item));\r
1281 \r
1282           yield return table[index].item;\r
1283           ob = null;\r
1284                                 }\r
1285 #endif\r
1286       }\r
1287 #endif\r
1288     }\r
1289 \r
1290     #endregion\r
1291 \r
1292     #region ISink<T> Members\r
1293     /// <summary>\r
1294     /// Report if this is a set collection.\r
1295     /// </summary>\r
1296     /// <value>Always false</value>\r
1297     [Tested]\r
1298     public virtual bool AllowsDuplicates { [Tested]get { return false; } }\r
1299 \r
1300     /// <summary>\r
1301     /// By convention this is true for any collection with set semantics.\r
1302     /// </summary>\r
1303     /// <value>True if only one representative of a group of equal items \r
1304     /// is kept in the collection together with the total count.</value>\r
1305     public virtual bool DuplicatesByCounting { get { return true; } }\r
1306 \r
1307     /// <summary>\r
1308     /// Add an item to this set.\r
1309     /// </summary>\r
1310     /// <param name="item">The item to add.</param>\r
1311     /// <returns>True if item was added (i.e. not found)</returns>\r
1312     [Tested]\r
1313     public virtual bool Add(T item)\r
1314     {\r
1315       updatecheck();\r
1316       return !searchoradd(ref item, true, false, true);\r
1317     }\r
1318 \r
1319     /// <summary>\r
1320     /// Add the elements from another collection with a more specialized item type \r
1321     /// to this collection. Since this\r
1322     /// collection has set semantics, only items not already in the collection\r
1323     /// will be added.\r
1324     /// </summary>\r
1325     /// <typeparam name="U">The type of items to add</typeparam>\r
1326     /// <param name="items">The items to add</param>\r
1327     [Tested]\r
1328     public virtual void AddAll<U>(SCG.IEnumerable<U> items) where U : T\r
1329     {\r
1330       updatecheck();\r
1331       bool wasChanged = false;\r
1332       bool raiseAdded = (ActiveEvents & EventTypeEnum.Added) != 0;\r
1333       CircularQueue<T> wasAdded = raiseAdded ? new CircularQueue<T>() : null;\r
1334       foreach (T item in items)\r
1335       {\r
1336         T jtem = item;\r
1337 \r
1338         if (!searchoradd(ref jtem, true, false, false))\r
1339         {\r
1340           wasChanged = true;\r
1341           if (raiseAdded)\r
1342             wasAdded.Enqueue(item);\r
1343         }\r
1344       }\r
1345       //TODO: implement a RaiseForAddAll() method\r
1346       if (raiseAdded & wasChanged)\r
1347         foreach (T item in wasAdded)\r
1348           raiseItemsAdded(item, 1);\r
1349       if (((ActiveEvents & EventTypeEnum.Changed) != 0 && wasChanged))\r
1350         raiseCollectionChanged();\r
1351     }\r
1352 \r
1353 \r
1354     #endregion\r
1355 \r
1356     #region Diagnostics\r
1357 \r
1358     /// <summary>\r
1359     /// Test internal structure of data (invariants)\r
1360     /// </summary>\r
1361     /// <returns>True if pass</returns>\r
1362     [Tested]\r
1363     public virtual bool Check()\r
1364     {\r
1365       int count = 0;\r
1366 #if LINEARPROBING\r
1367       int lasthole = table.Length - 1;\r
1368 \r
1369 #if REFBUCKET\r
1370       while (lasthole >= 0 && table[lasthole] != null)\r
1371 #else\r
1372       while (lasthole >= 0 && !isnull(table[lasthole].item))\r
1373 #endif\r
1374       {\r
1375         lasthole--;\r
1376         count++;\r
1377       }\r
1378 \r
1379       if (lasthole < 0)\r
1380       {\r
1381         Console.WriteLine("Table is completely filled!");\r
1382         return false;\r
1383       }\r
1384 \r
1385       for (int cellindex = lasthole + 1, s = table.Length; cellindex < s; cellindex++)\r
1386       {\r
1387         Bucket b = table[cellindex];\r
1388         int hashindex = hv2i(b.hashval);\r
1389 \r
1390         if (hashindex <= lasthole || hashindex > cellindex)\r
1391         {\r
1392           Console.WriteLine("Bad cell item={0}, hashval={1}, hashindex={2}, cellindex={3}, lasthole={4}", b.item, b.hashval, hashindex, cellindex, lasthole);\r
1393           return false;\r
1394         }\r
1395       }\r
1396 \r
1397       int latesthole = -1;\r
1398 \r
1399       for (int cellindex = 0; cellindex < lasthole; cellindex++)\r
1400       {\r
1401         Bucket b = table[cellindex];\r
1402 \r
1403 #if REFBUCKET\r
1404         if (b != null)\r
1405 #else\r
1406         if (!isnull(b.item))\r
1407 #endif\r
1408         {\r
1409           count++;\r
1410 \r
1411           int hashindex = hv2i(b.hashval);\r
1412 \r
1413           if (cellindex < hashindex && hashindex <= lasthole)\r
1414           {\r
1415             Console.WriteLine("Bad cell item={0}, hashval={1}, hashindex={2}, cellindex={3}, latesthole={4}", b.item, b.hashval, hashindex, cellindex, latesthole);\r
1416             return false;\r
1417           }\r
1418         }\r
1419         else\r
1420         {\r
1421           latesthole = cellindex;\r
1422           break;\r
1423         }\r
1424       }\r
1425 \r
1426       for (int cellindex = latesthole + 1; cellindex < lasthole; cellindex++)\r
1427       {\r
1428         Bucket b = table[cellindex];\r
1429 \r
1430 #if REFBUCKET\r
1431         if (b != null)\r
1432 #else\r
1433         if (!isnull(b.item))\r
1434 #endif\r
1435         {\r
1436           count++;\r
1437 \r
1438           int hashindex = hv2i(b.hashval);\r
1439 \r
1440           if (hashindex <= latesthole || cellindex < hashindex)\r
1441           {\r
1442             Console.WriteLine("Bad cell item={0}, hashval={1}, hashindex={2}, cellindex={3}, latesthole={4}", b.item, b.hashval, hashindex, cellindex, latesthole);\r
1443             return false;\r
1444           }\r
1445         }\r
1446         else\r
1447         {\r
1448           latesthole = cellindex;\r
1449         }\r
1450       }\r
1451 \r
1452       return true;\r
1453 #else\r
1454       bool retval = true;\r
1455       for (int i = 0, s = table.Length; i < s; i++)\r
1456       {\r
1457         int level = 0;\r
1458         Bucket b = table[i];\r
1459 #if REFBUCKET\r
1460         while (b != null)\r
1461         {\r
1462           if (i != hv2i(b.hashval))\r
1463           {\r
1464             Console.WriteLine("Bad cell item={0}, hashval={1}, index={2}, level={3}", b.item, b.hashval, i, level);\r
1465             retval = false;\r
1466           }\r
1467 \r
1468           count++;\r
1469           level++;\r
1470           b = b.overflow;\r
1471         }\r
1472 #else\r
1473                                 if (!isnull(b.item))\r
1474                                 {\r
1475                                         count++;\r
1476                                         if (i != hv2i(b.hashval))\r
1477                                         {\r
1478                                                 Console.WriteLine("Bad cell item={0}, hashval={1}, index={2}, level={3}", b.item, b.hashval, i, level);\r
1479                                                 retval = false;\r
1480                                         }\r
1481 \r
1482                                         OverflowBucket ob = b.overflow;\r
1483 \r
1484                                         while (ob != null)\r
1485                                         {\r
1486                                                 level++;\r
1487                                                 count++;\r
1488                                                 if (i != hv2i(ob.hashval))\r
1489                                                 {\r
1490                                                         Console.WriteLine("Bad cell item={0}, hashval={1}, index={2}, level={3}", b.item, b.hashval, i, level);\r
1491                                                         retval = false;\r
1492                                                 }\r
1493 \r
1494                                                 ob = ob.overflow;\r
1495                                         }\r
1496                                 }\r
1497 #endif\r
1498       }\r
1499 \r
1500       if (count != size)\r
1501       {\r
1502         Console.WriteLine("size({0}) != count({1})", size, count);\r
1503         retval = false;\r
1504       }\r
1505 \r
1506       return retval;\r
1507 #endif\r
1508     }\r
1509 \r
1510 \r
1511     /// <summary>\r
1512     /// Produce statistics on distribution of bucket sizes. Current implementation is incomplete.\r
1513     /// </summary>\r
1514     /// <returns>Histogram data.</returns>\r
1515     [Tested(via = "Manually")]\r
1516     public ISortedDictionary<int, int> BucketCostDistribution()\r
1517     {\r
1518       TreeDictionary<int, int> res = new TreeDictionary<int, int>();\r
1519 #if LINEARPROBING\r
1520       int count = 0;\r
1521 #if REFBUCKET\r
1522       while (table[count] != null)\r
1523 #else\r
1524       while (!isnull(table[count].item))\r
1525 #endif\r
1526         count++;\r
1527       for (int i = table.Length - 1; i >= 0; i--)\r
1528       {\r
1529 #if REFBUCKET\r
1530         if (table[i] != null)\r
1531 #else\r
1532         if (!isnull(table[i].item))\r
1533 #endif\r
1534           count++;\r
1535         else\r
1536           count = 0;\r
1537         if (res.Contains(count))\r
1538           res[count]++;\r
1539         else\r
1540           res[count] = 1;\r
1541       }\r
1542 \r
1543       return res;\r
1544 #else\r
1545       for (int i = 0, s = table.Length; i < s; i++)\r
1546       {\r
1547         int count = 0;\r
1548 #if REFBUCKET\r
1549         Bucket b = table[i];\r
1550 \r
1551         while (b != null)\r
1552         {\r
1553           count++;\r
1554           b = b.overflow;\r
1555         }\r
1556 #else\r
1557                                 Bucket b = table[i];\r
1558 \r
1559                                 if (!isnull(b.item))\r
1560                                 {\r
1561                                         count = 1;\r
1562 \r
1563                                         OverflowBucket ob = b.overflow;\r
1564 \r
1565                                         while (ob != null)\r
1566                                         {\r
1567                                                 count++;\r
1568                                                 ob = ob.overflow;\r
1569                                         }\r
1570                                 }\r
1571 #endif\r
1572         if (res.Contains(count))\r
1573           res[count]++;\r
1574         else\r
1575           res[count] = 1;\r
1576       }\r
1577 \r
1578       return res;\r
1579 #endif\r
1580     }\r
1581 \r
1582     #endregion\r
1583 \r
1584     #region ICloneable Members\r
1585 \r
1586     /// <summary>\r
1587     /// Make a shallow copy of this HashSet.\r
1588     /// </summary>\r
1589     /// <returns></returns>\r
1590     public virtual object Clone()\r
1591     {\r
1592       HashSet<T> clone = new HashSet<T>(size > 0 ? size : 1, itemequalityComparer);\r
1593       //TODO: make sure this really adds in the counting bag way!\r
1594       clone.AddAll(this);\r
1595       return clone;\r
1596     }\r
1597 \r
1598     #endregion\r
1599 \r
1600   }\r
1601 }\r
1602
1603 #endif