mcs/class/Mono.C5/linkedlists/HashedLinkedLIst.cs

   1 #if NET_2_0\r
   2 /*\r
   3  Copyright (c) 2003-2004 Niels Kokholm <kokholm@itu.dk> and Peter Sestoft <sestoft@dina.kvl.dk>\r
   4  Permission is hereby granted, free of charge, to any person obtaining a copy\r
   5  of this software and associated documentation files (the "Software"), to deal\r
   6  in the Software without restriction, including without limitation the rights\r
   7  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell\r
   8  copies of the Software, and to permit persons to whom the Software is\r
   9  furnished to do so, subject to the following conditions:\r
  10  \r
  11  The above copyright notice and this permission notice shall be included in\r
  12  all copies or substantial portions of the Software.\r
  13  \r
  14  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR\r
  15  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,\r
  16  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE\r
  17  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER\r
  18  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,\r
  19  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE\r
  20  SOFTWARE.\r
  21 */\r
  22 \r
  23 #define LISTORDERnot\r
  24 #define EXTLISTORDER\r
  25 using System;\r
  26 using System.Diagnostics;\r
  27 using MSG=System.Collections.Generic;\r
  28 \r
  29 namespace C5\r
  30 {\r
  31         /// <summary>\r
  32         /// A list collection based on a doubly linked list data structure with \r
  33         /// a hash index mapping item to node.\r
  34         /// </summary>\r
  35         public class HashedLinkedList<T>: LinkedList<T>, IList<T>\r
  36         {\r
  37                 #region Fields\r
  38 \r
  39                 HashDictionary<T,Node> dict;\r
  40 \r
  41                 //Invariant:  base.underlying == basehashedlist\r
  42                 HashedLinkedList<T> hashedunderlying;\r
  43 \r
  44                 #endregion\r
  45 \r
  46                 #region Constructors\r
  47 \r
  48                 void init()\r
  49                 {\r
  50 #if LISTORDER || EXTLISTORDER\r
  51                         maintaintags = true;\r
  52 #endif\r
  53                         dict = new HashDictionary<T,Node>(itemhasher);\r
  54                 }\r
  55                 \r
  56 \r
  57                 /// <summary>\r
  58                 /// Create a hashed linked list with an external item hasher.\r
  59                 /// </summary>\r
  60                 /// <param name="itemhasher">The external hasher</param>\r
  61                 public HashedLinkedList(IHasher<T> itemhasher) : base(itemhasher) { init(); }\r
  62 \r
  63 \r
  64                 /// <summary>\r
  65                 /// Create a hashed linked list with the natural item hasher.\r
  66                 /// </summary>\r
  67                 public HashedLinkedList() : base() { init(); }\r
  68 \r
  69                 #endregion\r
  70 \r
  71                 #region Util\r
  72 \r
  73                 bool contains(T item, out Node node)\r
  74                 {\r
  75                         if (!dict.Find(item,out node))\r
  76                                 return false;\r
  77                         else\r
  78                                 return insideview(node);\r
  79                 }\r
  80 \r
  81                 \r
  82                 void insert(Node succ, T item)\r
  83                 {\r
  84                         Node newnode = new Node(item);\r
  85 \r
  86                         if (dict.FindOrAdd(item, ref newnode))\r
  87                                 throw new ArgumentException("Item already in indexed list");\r
  88 \r
  89                         insertNode(succ, newnode);\r
  90                 }\r
  91 \r
  92 \r
  93                 private bool dictremove(T item, out Node node)\r
  94                 {\r
  95                         if (hashedunderlying == null)\r
  96                         {\r
  97                                 if (!dict.Remove(item, out node))\r
  98                                         return false;\r
  99                         }\r
 100                         else\r
 101                         {\r
 102                                 //We cannot avoid calling dict twice - have to intersperse the listorder test!\r
 103                                 if (!contains(item, out node))\r
 104                                         return false;\r
 105 \r
 106                                 dict.Remove(item);\r
 107                         }\r
 108 \r
 109                         return true;\r
 110                 }\r
 111 \r
 112 \r
 113                 bool insideview(Node node)\r
 114                 {\r
 115                         if (underlying == null)\r
 116                                 return true;\r
 117 \r
 118 #if LISTORDER\r
 119                         if (maintaintags)\r
 120                                 return (startsentinel.tag < node.tag && (endsentinel.tag == 0 || node.tag < endsentinel.tag));\r
 121                         else\r
 122 #elif EXTLISTORDER\r
 123                         if (maintaintags)\r
 124                                 return (startsentinel.precedes(node) && node.precedes(endsentinel));\r
 125                         else\r
 126 #endif\r
 127                         if (2 * size < hashedunderlying.size)\r
 128                         {\r
 129                                 Node cursor = startsentinel.next;\r
 130 \r
 131                                 while (cursor != endsentinel)\r
 132                                 {\r
 133                                         if (cursor == node)\r
 134                                                 return true;\r
 135 \r
 136                                         cursor = cursor.next;\r
 137                                 }\r
 138 \r
 139                                 return false;\r
 140                         }\r
 141                         else\r
 142                         {\r
 143                                 Node cursor = hashedunderlying.startsentinel.next;\r
 144 \r
 145                                 while (cursor != startsentinel.next)\r
 146                                 {\r
 147                                         if (cursor == node)\r
 148                                                 return false;\r
 149 \r
 150                                         cursor = cursor.next;\r
 151                                 }\r
 152 \r
 153                                 cursor = endsentinel;\r
 154                                 while (cursor != hashedunderlying.endsentinel)\r
 155                                 {\r
 156                                         if (cursor == node)\r
 157                                                 return false;\r
 158 \r
 159                                         cursor = cursor.next;\r
 160                                 }\r
 161 \r
 162                                 return true;\r
 163                         }\r
 164                 }\r
 165 \r
 166 \r
 167                 #endregion\r
 168 \r
 169                 #region IList<T> Members\r
 170 \r
 171                 /// <summary>\r
 172                 /// On this list, this indexer is read/write.\r
 173                 /// <exception cref="IndexOutOfRangeException"/> if i is negative or\r
 174                 /// &gt;= the size of the collection.\r
 175                 /// </summary>\r
 176                 /// <value>The i'th item of this list.</value>\r
 177                 /// <param name="i">The index of the item to fetch or store.</param>\r
 178                 [Tested]\r
 179                 public override T this[int i]\r
 180                 {\r
 181                         [Tested]\r
 182                         get\r
 183                         {\r
 184                                 modifycheck();\r
 185                                 return base[i];\r
 186                         }\r
 187                         [Tested]\r
 188                         set\r
 189                         {\r
 190                                 updatecheck();\r
 191 \r
 192                                 Node n = get(i);\r
 193 \r
 194                                 if (itemhasher.Equals(value, n.item))\r
 195                                 {\r
 196                                         n.item = value;\r
 197                                         dict.Update(value, n);\r
 198                                 }\r
 199                                 else if (!dict.FindOrAdd(value, ref n))\r
 200                                 {\r
 201                                         dict.Remove(n.item);\r
 202                                         n.item = value;\r
 203                                 }\r
 204                                 else\r
 205                                         throw new ArgumentException("Item already in indexed list");\r
 206                         }\r
 207                 }\r
 208 \r
 209 \r
 210                 /// <summary>\r
 211                 /// Insert an item at a specific index location in this list. \r
 212                 /// <exception cref="IndexOutOfRangeException"/> if i is negative or\r
 213                 /// &gt; the size of the collection.</summary>\r
 214                 /// <exception cref="InvalidOperationException"/> if  the item is \r
 215                 /// already in the list.\r
 216                 /// <param name="i">The index at which to insert.</param>\r
 217                 /// <param name="item">The item to insert.</param>\r
 218                 [Tested]\r
 219                 public override void Insert(int i, T item)\r
 220                 {\r
 221                         updatecheck();\r
 222                         insert(i == size ? endsentinel : get(i), item);\r
 223                 }\r
 224 \r
 225 \r
 226                 /// <summary>\r
 227                 /// Insert into this list all items from an enumerable collection starting \r
 228                 /// at a particular index.\r
 229                 /// <exception cref="IndexOutOfRangeException"/> if i is negative or\r
 230                 /// &gt; the size of the collection.\r
 231                 /// <exception cref="InvalidOperationException"/> if one of the items to insert is\r
 232                 /// already in the list.\r
 233                 /// </summary>\r
 234                 /// <param name="i">Index to start inserting at</param>\r
 235                 /// <param name="items">Items to insert</param>\r
 236                 [Tested]\r
 237                 public override void InsertAll(int i, MSG.IEnumerable<T> items)\r
 238                 {\r
 239                         updatecheck();\r
 240 \r
 241                         Node succ, node;\r
 242                         int count = 0;\r
 243 \r
 244                         succ = i == size ? endsentinel : get(i);\r
 245                         node = succ.prev;\r
 246 #if LISTORDER\r
 247                         //TODO: guard?\r
 248                         int taglimit = i == size ? int.MaxValue : succ.tag - 1, thetag = node.tag;\r
 249 #elif EXTLISTORDER\r
 250                         TagGroup taggroup = null;\r
 251                         int taglimit = 0, thetag = 0;\r
 252 \r
 253                         if (maintaintags)\r
 254                                 taggroup = gettaggroup(node, succ, out thetag, out taglimit);\r
 255 #endif\r
 256                         foreach (T item in items)\r
 257                         {\r
 258                                 Node tmp = new Node(item, node, null);\r
 259 \r
 260                                 if (!dict.FindOrAdd(item, ref tmp))\r
 261                                 {\r
 262 #if LISTORDER\r
 263                                         if (maintaintags)\r
 264                                                 tmp.tag = thetag < taglimit ? ++thetag : thetag;\r
 265 #elif EXTLISTORDER\r
 266                                         if (maintaintags)\r
 267                                         {\r
 268                                                 tmp.tag = thetag < taglimit ? ++thetag : thetag;\r
 269                                                 tmp.taggroup = taggroup;\r
 270                                         }\r
 271 #endif\r
 272                                         node.next = tmp;\r
 273                                         count++;\r
 274                                         node = tmp;\r
 275                                 }\r
 276                                 else\r
 277                                         throw new ArgumentException("Item already in indexed list");\r
 278                         }\r
 279 \r
 280 #if EXTLISTORDER\r
 281                         if (maintaintags)\r
 282                         {\r
 283                                 taggroup.count += count;\r
 284                                 taggroup.first = succ.prev;\r
 285                                 taggroup.last = node;\r
 286                         }\r
 287 #endif  \r
 288                         succ.prev = node;\r
 289                         node.next = succ;\r
 290                         size += count;\r
 291                         if (hashedunderlying != null)\r
 292                                 hashedunderlying.size += count;\r
 293 #if LISTORDER\r
 294                         if (maintaintags && node.tag == node.prev.tag)\r
 295                                 settag(node);\r
 296 #elif EXTLISTORDER\r
 297                         if (maintaintags)\r
 298                         {\r
 299                                 if (node.tag == node.prev.tag)\r
 300                                         splittaggroup(taggroup);\r
 301                         }\r
 302 #endif\r
 303                 }\r
 304 \r
 305 \r
 306                 /// <summary>\r
 307                 /// Insert an item right before the first occurrence of some target item.\r
 308                 /// <exception cref="ArgumentException"/> if target     is not found\r
 309                 /// <exception cref="InvalidOperationException"/> if the item is \r
 310                 /// already in the list.\r
 311                 /// </summary>\r
 312                 /// <param name="item">The item to insert.</param>\r
 313                 /// <param name="target">The target before which to insert.</param>\r
 314                 [Tested]\r
 315                 public override void InsertBefore(T item, T target)\r
 316                 {\r
 317                         updatecheck();\r
 318 \r
 319                         Node node;\r
 320 \r
 321                         if (!contains(target, out node))\r
 322                                 throw new ArgumentException("Target item not found");\r
 323 \r
 324                         insert(node, item);\r
 325                 }\r
 326 \r
 327 \r
 328                 /// <summary>\r
 329                 /// Insert an item right after the last(???) occurrence of some target item.\r
 330                 /// <exception cref="ArgumentException"/> if target     is not found\r
 331                 /// <exception cref="InvalidOperationException"/> if the item is \r
 332                 /// already in the list.\r
 333                 /// </summary>\r
 334                 /// <param name="item">The item to insert.</param>\r
 335                 /// <param name="target">The target after which to insert.</param>\r
 336                 [Tested]\r
 337                 public override void InsertAfter(T item, T target)\r
 338                 {\r
 339                         updatecheck();\r
 340 \r
 341                         Node node;\r
 342 \r
 343                         if (!contains(target, out node))\r
 344                                 throw new ArgumentException("Target item not found");\r
 345 \r
 346                         insert(node.next, item);\r
 347                 }\r
 348 \r
 349 \r
 350 \r
 351                 /// <summary>\r
 352                 /// Insert an item at the front of this list.\r
 353                 /// <exception cref="InvalidOperationException"/> if the item is \r
 354                 /// already in the list.\r
 355                 /// </summary>\r
 356                 /// <param name="item">The item to insert.</param>\r
 357                 [Tested]\r
 358                 public override void InsertFirst(T item)\r
 359                 {\r
 360                         updatecheck();\r
 361                         insert(startsentinel.next, item);\r
 362                 }\r
 363 \r
 364                 /// <summary>\r
 365                 /// Insert an item at the back of this list.\r
 366                 /// <exception cref="InvalidOperationException"/> if  the item is \r
 367                 /// already in the list.\r
 368                 /// </summary>\r
 369                 /// <param name="item">The item to insert.</param>\r
 370                 [Tested]\r
 371                 public override void InsertLast(T item)\r
 372                 {\r
 373                         updatecheck();\r
 374                         insert(endsentinel, item);\r
 375                 }\r
 376 \r
 377 \r
 378                 /// <summary>\r
 379                 /// Remove one item from the list: from the front if <code>FIFO</code>\r
 380                 /// is true, else from the back.\r
 381                 /// <exception cref="InvalidOperationException"/> if this list is empty.\r
 382                 /// </summary>\r
 383                 /// <returns>The removed item.</returns>\r
 384                 [Tested]\r
 385                 public override T Remove()\r
 386                 {\r
 387                         T retval = base.Remove();\r
 388 \r
 389                         dict.Remove(retval);\r
 390                         return retval;\r
 391                 }\r
 392 \r
 393 \r
 394                 /// <summary>\r
 395                 /// Remove one item from the front of the list.\r
 396                 /// <exception cref="InvalidOperationException"/> if this list is empty.\r
 397                 /// </summary>\r
 398                 /// <returns>The removed item.</returns>\r
 399                 [Tested]\r
 400                 public override T RemoveFirst()\r
 401                 {\r
 402                         T retval = base.RemoveFirst();\r
 403 \r
 404                         dict.Remove(retval);\r
 405                         return retval;\r
 406                 }\r
 407 \r
 408 \r
 409                 /// <summary>\r
 410                 /// Remove one item from the back of the list.\r
 411                 /// <exception cref="InvalidOperationException"/> if this list is empty.\r
 412                 /// </summary>\r
 413                 /// <returns>The removed item.</returns>\r
 414                 [Tested]\r
 415                 public override T RemoveLast()\r
 416                 {\r
 417                         T retval = base.RemoveLast();\r
 418 \r
 419                         dict.Remove(retval);\r
 420                         return retval;\r
 421                 }\r
 422 \r
 423 \r
 424                 /// <summary>\r
 425                 /// Create a list view on this list. \r
 426                 /// <exception cref="ArgumentOutOfRangeException"/> if the view would not fit into\r
 427                 /// this list.\r
 428                 /// </summary>\r
 429                 /// <param name="start">The index in this list of the start of the view.</param>\r
 430                 /// <param name="count">The size of the view.</param>\r
 431                 /// <returns>The new list view.</returns>\r
 432                 [Tested]\r
 433                 public override IList<T> View(int start, int count)\r
 434                 {\r
 435                         checkRange(start, count);\r
 436                         modifycheck();\r
 437 \r
 438                         HashedLinkedList<T> retval = (HashedLinkedList<T>)MemberwiseClone();\r
 439 \r
 440                         retval.underlying = retval.hashedunderlying = hashedunderlying != null ? hashedunderlying : this;\r
 441                         retval.offset = start + offset;\r
 442                         retval.startsentinel = start == 0 ? startsentinel : get(start - 1);\r
 443                         retval.endsentinel = start + count == size ? endsentinel : get(start + count);\r
 444                         retval.size = count;\r
 445                         return retval;\r
 446                 }\r
 447 \r
 448                 /// <summary>\r
 449                 /// Reverst part of the list so the items are in the opposite sequence order.\r
 450                 /// <exception cref="ArgumentException"/> if the count is negative.\r
 451                 /// <exception cref="ArgumentOutOfRangeException"/> if the part does not fit\r
 452                 /// into the list.\r
 453                 /// </summary>\r
 454                 /// <param name="start">The index of the start of the part to reverse.</param>\r
 455                 /// <param name="count">The size of the part to reverse.</param>\r
 456                 [Tested]\r
 457                 public override void Reverse(int start, int count)\r
 458                 {\r
 459                         //Duplicating linkedlist<T> code to minimize cache misses\r
 460                         updatecheck();\r
 461                         checkRange(start, count);\r
 462                         if (count == 0)\r
 463                                 return;\r
 464 \r
 465                         Node a = get(start), b = get(start + count - 1);\r
 466 \r
 467                         for (int i = 0; i < count / 2; i++)\r
 468                         {\r
 469                                 T swap = a.item;a.item = b.item;b.item = swap;\r
 470                                 dict[a.item] = a;dict[b.item] = b;\r
 471                                 a = a.next;b = b.prev;\r
 472                         }\r
 473                 }\r
 474 \r
 475 \r
 476                 /// <summary>\r
 477                 /// Shuffle the items of this list according to a specific random source.\r
 478                 /// </summary>\r
 479                 /// <param name="rnd">The random source.</param>\r
 480                 public override void Shuffle(Random rnd)\r
 481                 {\r
 482                         updatecheck();\r
 483 \r
 484                         ArrayList<T> a = new ArrayList<T>();\r
 485 \r
 486                         a.AddAll(this);\r
 487                         a.Shuffle(rnd);\r
 488 \r
 489                         Node cursor = startsentinel.next;\r
 490                         int j = 0;\r
 491 \r
 492                         while (cursor != endsentinel)\r
 493                         {\r
 494                                 dict[cursor.item = a[j++]] = cursor;\r
 495                                 cursor = cursor.next;\r
 496                         }\r
 497                 }\r
 498 \r
 499                 #endregion              \r
 500 \r
 501                 #region IIndexed<T> Members\r
 502 \r
 503                 /// <summary>\r
 504                 /// Searches for an item in the list going forwrds from the start.\r
 505                 /// </summary>\r
 506                 /// <param name="item">Item to search for.</param>\r
 507                 /// <returns>Index of item from start.</returns>\r
 508                 [Tested]\r
 509                 public override int IndexOf(T item)\r
 510                 {\r
 511                         Node node;\r
 512 \r
 513                         modifycheck();\r
 514                         if (!dict.Find(item, out node))\r
 515                                 return -1;\r
 516 #if LISTORDER\r
 517                         if (maintaintags && !insideview(node))\r
 518                                 return -1;\r
 519 #elif EXTLISTORDER\r
 520                         if (maintaintags && !insideview(node))\r
 521                                 return -1;\r
 522 #endif\r
 523                         return base.IndexOf(item);\r
 524                 }\r
 525 \r
 526 \r
 527                 /// <summary>\r
 528                 /// Searches for an item in the list going backwords from the end.\r
 529                 /// </summary>\r
 530                 /// <param name="item">Item to search for.</param>\r
 531                 /// <returns>Index of of item from the end.</returns>\r
 532                 [Tested]\r
 533                 public override int LastIndexOf(T item) { return IndexOf(item); }\r
 534 \r
 535 \r
 536                 /// <summary>\r
 537                 /// Remove the item at a specific position of the list.\r
 538                 /// <exception cref="IndexOutOfRangeException"/> if i is negative or\r
 539                 /// &gt;= the size of the collection.\r
 540                 /// </summary>\r
 541                 /// <param name="i">The index of the item to remove.</param>\r
 542                 /// <returns>The removed item.</returns>\r
 543                 [Tested]\r
 544                 public override T RemoveAt(int i)\r
 545                 {\r
 546                         T retval = base.RemoveAt(i);\r
 547 \r
 548                         dict.Remove(retval);\r
 549                         return retval;\r
 550                 }\r
 551 \r
 552 \r
 553                 /// <summary>\r
 554                 /// Remove all items in an index interval.\r
 555                 /// <exception cref="IndexOutOfRangeException"/>???. \r
 556                 /// </summary>\r
 557                 /// <param name="start">The index of the first item to remove.</param>\r
 558                 /// <param name="count">The number of items to remove.</param>\r
 559                 [Tested]\r
 560                 public override void RemoveInterval(int start, int count)\r
 561                 {\r
 562                         updatecheck();\r
 563                         checkRange(start, count);\r
 564                         if (count == 0)\r
 565                                 return;\r
 566 \r
 567                         Node a, b;\r
 568 \r
 569                         if (start <= size - start - count)\r
 570                         {\r
 571                                 b = a = get(start);\r
 572 #if EXTLISTORDER\r
 573                                 Node c = a.prev;\r
 574 #endif\r
 575                                 for (int i = 0; i < count; i++)\r
 576                                 {\r
 577                                         dict.Remove(b.item); \r
 578 #if EXTLISTORDER\r
 579                                         if (maintaintags)\r
 580                                         {\r
 581                                                 c.next = b;\r
 582                                                 b.prev = c;\r
 583                                                 removefromtaggroup(b);\r
 584                                         }\r
 585 #endif\r
 586                                         b = b.next;\r
 587                                 }\r
 588 \r
 589                                 a.prev.next = b;\r
 590                                 b.prev = a.prev;\r
 591                         }\r
 592                         else\r
 593                         {\r
 594                                 a = b = get(start + count - 1);\r
 595 #if EXTLISTORDER\r
 596                                 Node c = b.next;\r
 597 #endif\r
 598                                 for (int i = 0; i < count; i++)\r
 599                                 {\r
 600                                         dict.Remove(a.item); \r
 601 #if EXTLISTORDER\r
 602                                         if (maintaintags)\r
 603                                         {\r
 604                                                 c.prev = a;\r
 605                                                 a.next = c;\r
 606                                                 removefromtaggroup(a);\r
 607                                         }\r
 608 #endif\r
 609                                         a = a.prev;\r
 610                                 }\r
 611 \r
 612                                 a.next = b.next;\r
 613                                 b.next.prev = a;\r
 614                         }\r
 615 \r
 616                         size -= count;\r
 617                         if (hashedunderlying != null)\r
 618                                 hashedunderlying.size -= count;\r
 619                 }\r
 620 \r
 621                 #endregion\r
 622 \r
 623                 #region ISequenced<T> Members\r
 624 \r
 625                 int ISequenced<T>.GetHashCode()\r
 626                 { modifycheck(); return sequencedhashcode(); }\r
 627 \r
 628 \r
 629                 bool ISequenced<T>.Equals(ISequenced<T> that)\r
 630                 { modifycheck(); return sequencedequals(that); }\r
 631 \r
 632                 #endregion\r
 633 \r
 634                 #region IEditableCollection<T> Members\r
 635 \r
 636 \r
 637                 /// <summary>\r
 638                 /// The value is symbolic indicating the type of asymptotic complexity\r
 639                 /// in terms of the size of this collection (worst-case or amortized as\r
 640                 /// relevant).\r
 641                 /// </summary>\r
 642                 /// <value>Speed.Constant</value>\r
 643                 [Tested]\r
 644                 public override Speed ContainsSpeed\r
 645                 {\r
 646                         [Tested]\r
 647                         get\r
 648                         {\r
 649 #if LISTORDER || EXTLISTORDER\r
 650                                 return hashedunderlying == null || maintaintags ? Speed.Constant : Speed.Linear;\r
 651 #else\r
 652                                 return basehashedlist == null ? Speed.Constant : Speed.Linear;\r
 653 #endif\r
 654                         }\r
 655                 }\r
 656 \r
 657 \r
 658                 int ICollection<T>.GetHashCode()\r
 659                 { modifycheck(); return unsequencedhashcode(); }\r
 660 \r
 661 \r
 662                 bool ICollection<T>.Equals(ICollection<T> that)\r
 663                 { modifycheck(); return unsequencedequals(that); }\r
 664 \r
 665 \r
 666                 /// <summary>\r
 667                 /// Check if this collection contains (an item equivalent to according to the\r
 668                 /// itemhasher) a particular value.\r
 669                 /// </summary>\r
 670                 /// <param name="item">The value to check for.</param>\r
 671                 /// <returns>True if the items is in this collection.</returns>\r
 672                 [Tested]\r
 673                 public override bool Contains(T item)\r
 674                 {\r
 675                         Node node;\r
 676 \r
 677                         modifycheck();\r
 678                         return contains(item, out node);\r
 679                 }\r
 680 \r
 681 \r
 682                 /// <summary>\r
 683                 /// Check if this collection contains an item equivalent according to the\r
 684                 /// itemhasher to a particular value. If so, return in the ref argument (a\r
 685                 /// binary copy of) the actual value found.\r
 686                 /// </summary>\r
 687                 /// <param name="item">The value to look for.</param>\r
 688                 /// <returns>True if the items is in this collection.</returns>\r
 689                 [Tested]\r
 690                 public override bool Find(ref T item)\r
 691                 {\r
 692                         Node node;\r
 693 \r
 694                         modifycheck();\r
 695                         if (contains(item, out node)) { item = node.item; return true; }\r
 696 \r
 697                         return false;\r
 698                 }\r
 699 \r
 700 \r
 701                 /// <summary>\r
 702                 /// Check if this collection contains an item equivalent according to the\r
 703                 /// itemhasher to a particular value. If so, update the item in the collection \r
 704                 /// to with a binary copy of the supplied value. \r
 705                 /// </summary>\r
 706                 /// <param name="item">Value to update.</param>\r
 707                 /// <returns>True if the item was found and hence updated.</returns>\r
 708                 [Tested]\r
 709                 public override bool Update(T item)\r
 710                 {\r
 711                         Node node;\r
 712 \r
 713                         updatecheck();\r
 714                         if (contains(item, out node)) { node.item = item; return true; }\r
 715 \r
 716                         return false;\r
 717                 }\r
 718 \r
 719 \r
 720                 /// <summary>\r
 721                 /// Check if this collection contains an item equivalent according to the\r
 722                 /// itemhasher to a particular value. If so, return in the ref argument (a\r
 723                 /// binary copy of) the actual value found. Else, add the item to the collection.\r
 724                 /// </summary>\r
 725                 /// <param name="item">The value to look for.</param>\r
 726                 /// <returns>True if the item was found (hence not added).</returns>\r
 727                 [Tested]\r
 728                 public override bool FindOrAdd(ref T item)\r
 729                 {\r
 730                         updatecheck();\r
 731 \r
 732                         //This is an extended myinsert:\r
 733                         Node node = new Node(item);\r
 734 \r
 735                         if (!dict.FindOrAdd(item, ref node))\r
 736                         {\r
 737                                 insertNode(endsentinel, node);\r
 738                                 return false;\r
 739                         }\r
 740 \r
 741                         if (!insideview(node))\r
 742                                 throw new ArgumentException("Item alredy in indexed list but outside view");\r
 743 \r
 744                         item = node.item;\r
 745                         return true;\r
 746                 }\r
 747 \r
 748 \r
 749                 /// <summary>\r
 750                 /// Check if this collection contains an item equivalent according to the\r
 751                 /// itemhasher to a particular value. If so, update the item in the collection \r
 752                 /// to with a binary copy of the supplied value; else add the value to the collection. \r
 753                 /// </summary>\r
 754                 /// <param name="item">Value to add or update.</param>\r
 755                 /// <returns>True if the item was found and updated (hence not added).</returns>\r
 756                 [Tested]\r
 757                 public override bool UpdateOrAdd(T item)\r
 758                 {\r
 759                         updatecheck();\r
 760 \r
 761                         Node node = new Node(item);\r
 762 \r
 763                         /*if (basehashedlist == null)\r
 764                         {\r
 765                                 if (!dict.UpdateOrAdd(item, node))\r
 766                                         return false;\r
 767                         }\r
 768                         else\r
 769                         {*/\r
 770                                 //NOTE: it is hard to do this without double access to the dictionary\r
 771                                 //in the update case\r
 772                                 if (dict.FindOrAdd(item, ref node))\r
 773                                 {\r
 774                                         if (!insideview(node))\r
 775                                                 throw new ArgumentException("Item in indexed list but outside view");\r
 776 \r
 777                                         //dict.Update(item, node);\r
 778                                         node.item = item;\r
 779                                         return true;\r
 780                                 }\r
 781                         //}\r
 782 \r
 783                         insertNode(endsentinel, node);\r
 784                         return false;\r
 785                 }\r
 786 \r
 787 \r
 788                 /// <summary>\r
 789                 /// Remove a particular item from this collection. \r
 790                 /// </summary>\r
 791                 /// <param name="item">The value to remove.</param>\r
 792                 /// <returns>True if the item was found (and removed).</returns>\r
 793                 [Tested]\r
 794                 public override bool Remove(T item)\r
 795                 {\r
 796                         updatecheck();\r
 797 \r
 798                         Node node;\r
 799 \r
 800                         if (!dictremove(item, out node))\r
 801                                 return false;\r
 802 \r
 803                         remove(node);\r
 804                         return true;\r
 805                 }\r
 806 \r
 807 \r
 808                 /// <summary>\r
 809                 /// Remove a particular item from this collection if found. \r
 810                 /// If an item was removed, report a binary copy of the actual item removed in \r
 811                 /// the argument.\r
 812                 /// </summary>\r
 813                 /// <param name="item">The value to remove on input.</param>\r
 814                 /// <returns>True if the item was found (and removed).</returns>\r
 815                 [Tested]\r
 816                 public override bool RemoveWithReturn(ref T item)\r
 817                 {\r
 818                         Node node;\r
 819 \r
 820                         updatecheck();\r
 821                         if (!dictremove(item, out node))\r
 822                                 return false;\r
 823 \r
 824                         item = node.item;\r
 825                         remove(node);\r
 826                         return true;\r
 827                 }\r
 828 \r
 829 \r
 830                 /// <summary>\r
 831                 /// Remove all items in another collection from this one. \r
 832                 /// </summary>\r
 833                 /// <param name="items">The items to remove.</param>\r
 834                 [Tested]\r
 835                 public override void RemoveAll(MSG.IEnumerable<T> items)\r
 836                 {\r
 837                         Node node;\r
 838 \r
 839                         updatecheck();\r
 840                         foreach (T item in items)\r
 841                                 if (dictremove(item, out node))\r
 842                                         remove(node);\r
 843                 }\r
 844 \r
 845 \r
 846                 /// <summary>\r
 847                 /// Remove all items from this collection.\r
 848                 /// </summary>\r
 849                 [Tested]\r
 850                 public override void Clear()\r
 851                 {\r
 852                         updatecheck();\r
 853                         if (hashedunderlying == null)\r
 854                                 dict.Clear();\r
 855                         else\r
 856                                 foreach (T item in this)\r
 857                                         dict.Remove(item);\r
 858 \r
 859                         base.Clear();\r
 860                 }\r
 861 \r
 862 \r
 863                 /// <summary>\r
 864                 /// Remove all items not in some other collection from this one. \r
 865                 /// </summary>\r
 866                 /// <param name="items">The items to retain.</param>\r
 867                 [Tested]\r
 868                 public override void RetainAll(MSG.IEnumerable<T> items)\r
 869                 {\r
 870                         updatecheck();\r
 871                         if (hashedunderlying == null)\r
 872                         {\r
 873                                 HashDictionary<T,Node> newdict = new HashDictionary<T,Node>(itemhasher);\r
 874 \r
 875                                 foreach (T item in items)\r
 876                                 {\r
 877                                         Node node;\r
 878 \r
 879                                         if (dict.Remove(item, out node))\r
 880                                                 newdict.Add(item, node);\r
 881                                 }\r
 882 \r
 883                                 foreach (KeyValuePair<T,Node> pair in dict)\r
 884                                 {\r
 885                                         Node n = pair.value, p = n.prev, s = n.next; s.prev = p; p.next = s;\r
 886 #if EXTLISTORDER\r
 887                                         if (maintaintags)\r
 888                                                 removefromtaggroup(n);\r
 889 #endif\r
 890                                 }\r
 891 \r
 892                                 dict = newdict;\r
 893                                 size = dict.Count;\r
 894                                 //For a small number of items to retain it might be faster to \r
 895                                 //iterate through the list and splice out the chunks not needed\r
 896                         }\r
 897                         else\r
 898                         {\r
 899                                 HashSet<T> newdict = new HashSet<T>(itemhasher);\r
 900 \r
 901                                 foreach (T item in this)\r
 902                                         newdict.Add(item);\r
 903 \r
 904                                 foreach (T item in items)\r
 905                                         newdict.Remove(item);\r
 906 \r
 907                                 Node n = startsentinel.next;\r
 908 \r
 909                                 while (n != endsentinel)\r
 910                                 {\r
 911                                         if (newdict.Contains(n.item))\r
 912                                         {\r
 913                                                 dict.Remove(n.item);\r
 914                                                 remove(n);\r
 915                                         }\r
 916 \r
 917                                         n = n.next;\r
 918                                 }\r
 919                         }\r
 920                 }\r
 921 \r
 922                 /// <summary>\r
 923                 /// Check if this collection contains all the values in another collection\r
 924                 /// Multiplicities\r
 925                 /// are not taken into account.\r
 926                 /// </summary>\r
 927                 /// <param name="items">The </param>\r
 928                 /// <returns>True if all values in <code>items</code>is in this collection.</returns>\r
 929                 [Tested]\r
 930                 public override bool ContainsAll(MSG.IEnumerable<T> items)\r
 931                 {\r
 932                         Node node;\r
 933 \r
 934                         modifycheck();\r
 935                         foreach (T item in items)\r
 936                                 if (!contains(item, out node))\r
 937                                         return false;\r
 938 \r
 939                         return true;\r
 940                 }\r
 941 \r
 942 \r
 943                 /// <summary>\r
 944                 /// Count the number of items of the collection equal to a particular value.\r
 945                 /// Returns 0 if and only if the value is not in the collection.\r
 946                 /// </summary>\r
 947                 /// <param name="item">The value to count.</param>\r
 948                 /// <returns>The number of copies found.</returns>\r
 949                 [Tested]\r
 950                 public override int ContainsCount(T item) { return Contains(item) ? 1 : 0; }\r
 951 \r
 952 \r
 953                 /// <summary>\r
 954                 /// Remove all items equivalent to a given value.\r
 955                 /// </summary>\r
 956                 /// <param name="item">The value to remove.</param>\r
 957                 [Tested]\r
 958                 public override void RemoveAllCopies(T item) { Remove(item); }\r
 959 \r
 960                 #endregion\r
 961 \r
 962                 #region ISink<T> Members\r
 963 \r
 964                 /// <summary>\r
 965                 /// \r
 966                 /// </summary>\r
 967                 /// <value>False since this collection has set semantics.</value>\r
 968                 [Tested]\r
 969         public override bool AllowsDuplicates { [Tested]get { return false; } }\r
 970 \r
 971 \r
 972         //This is *not* the same as AddLast!!\r
 973                 /// <summary>\r
 974                 /// Add an item to this collection if possible. Since this collection has set\r
 975                 /// semantics, the item will be added if not already in the collection. \r
 976                 /// </summary>\r
 977                 /// <param name="item">The item to add.</param>\r
 978                 /// <returns>True if item was added.</returns>\r
 979                 [Tested]\r
 980                 public override bool Add(T item)\r
 981                 {\r
 982                         updatecheck();\r
 983 \r
 984                         Node node = new Node(item);\r
 985 \r
 986                         if (!dict.FindOrAdd(item, ref node))\r
 987                         {\r
 988                                 insertNode(endsentinel, node);\r
 989                                 return true;\r
 990                         }\r
 991 \r
 992                         return false;\r
 993                 }\r
 994 \r
 995 \r
 996                 //Note: this is *not* equivalent to InsertRange int this Set situation!!!\r
 997                 /// <summary>\r
 998                 /// Add the elements from another collection to this collection.\r
 999                 /// Only items not already in the collection\r
1000                 /// will be added.\r
1001                 /// </summary>\r
1002                 /// <param name="items">The items to add.</param>\r
1003                 [Tested]\r
1004                 public override void AddAll(MSG.IEnumerable<T> items)\r
1005                 {\r
1006                         updatecheck();\r
1007                         foreach (T item in items)\r
1008                         {\r
1009                                 Node node = new Node(item);\r
1010 \r
1011                                 if (!dict.FindOrAdd(item, ref node))\r
1012                                         insertNode(endsentinel, node);\r
1013                         }\r
1014                 }\r
1015 \r
1016         /// <summary>\r
1017         /// Add the elements from another collection with a more specialized item type \r
1018         /// to this collection. \r
1019         /// Only items not already in the collection\r
1020         /// will be added.\r
1021         /// </summary>\r
1022         /// <typeparam name="U">The type of items to add</typeparam>\r
1023         /// <param name="items">The items to add</param>\r
1024         public override void AddAll<U>(MSG.IEnumerable<U> items) //where U:T\r
1025         {\r
1026             updatecheck();\r
1027             foreach (T item in items)\r
1028             {\r
1029                 Node node = new Node(item);\r
1030 \r
1031                 if (!dict.FindOrAdd(item, ref node))\r
1032                     insertNode(endsentinel, node);\r
1033             }\r
1034         }\r
1035 \r
1036         #endregion\r
1037 \r
1038                 #region IDirectedEnumerable<T> Members\r
1039 \r
1040                 IDirectedEnumerable<T> IDirectedEnumerable<T>.Backwards() { return Backwards(); }\r
1041 \r
1042 \r
1043                 #endregion\r
1044 \r
1045                 #region Diagnostics\r
1046                 /// <summary>\r
1047                 /// Check the integrity of the internal data structures of this collection.\r
1048                 /// Only avaliable in DEBUG builds???\r
1049                 /// </summary>\r
1050                 /// <returns>True if check does not fail.</returns>\r
1051                 [Tested]\r
1052                 public override bool Check()\r
1053                 {\r
1054                         if (!base.Check())\r
1055                                 return false;\r
1056 \r
1057                         bool retval = true;\r
1058 \r
1059                         if (hashedunderlying == null)\r
1060                         {\r
1061                                 if (size != dict.Count)\r
1062                                 {\r
1063                                         Console.WriteLine("list.size ({0}) != dict.Count ({1})", size, dict.Count);\r
1064                                         retval = false;\r
1065                                 }\r
1066 \r
1067                                 Node n = startsentinel.next, n2;\r
1068 \r
1069                                 while (n != endsentinel)\r
1070                                 {\r
1071                                         if (!dict.Find(n.item, out n2))\r
1072                                         {\r
1073                                                 Console.WriteLine("Item in list but not dict: {0}", n.item);\r
1074                                                 retval = false;\r
1075                                         }\r
1076                                         else if (n != n2)\r
1077                                         {\r
1078                                                 Console.WriteLine("Wrong node in dict for item: {0}", n.item);\r
1079                                                 retval = false;\r
1080                                         }\r
1081 \r
1082                                         n = n.next;\r
1083                                 }\r
1084                         }\r
1085 \r
1086                         return retval;\r
1087                 }\r
1088                 #endregion\r
1089         }\r
1090 }\r
1091 #endif\r