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

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