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

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