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

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