mcs/class/Mono.C5/arrays/SortedArray.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 using System;
  24 using System.Diagnostics;
  25 using MSG = System.Collections.Generic;
  26 namespace C5
  27 {
  28         /// <summary>
  29         /// A collection class implementing a sorted dynamic array data structure.
  30         /// </summary>
  31         public class SortedArray<T>: ArrayBase<T>, IIndexedSorted<T>
  32         {
  33                 #region Features
  34                 /// <summary>
  35                 /// A debugging artifact. To be removed.
  36                 /// </summary>
  37                 [Flags]
  38                 public enum Feature: short
  39                 {
  40                         /// <summary>
  41                         /// A debugging artifact. To be removed.
  42                         /// </summary>
  43                         Standard = 0
  44                 }
  45
  46
  47                 static Feature features = Feature.Standard;
  48
  49
  50                 /// <summary>
  51                 /// A debugging artifact. To be removed.
  52                 /// </summary>
  53                 /// <value></value>
  54                 public static Feature Features { get { return features; } }
  55
  56                 #endregion
  57
  58                 #region Fields
  59
  60                 IComparer<T> comparer;
  61
  62                 #endregion
  63
  64                 #region Util
  65                 /// <summary>
  66                 ///
  67                 /// </summary>
  68                 /// <param name="item">The item to search for</param>
  69                 /// <param name="mid">The least index, mid, for which array[mid] >= item</param>
  70                 /// <returns>True if item found</returns>
  71                 private bool binarySearch(T item, out int mid)
  72                 {
  73                         int bot = 0, top = size;
  74
  75                         mid = top / 2;
  76                         while (top > bot)
  77                         {
  78                                 int c;
  79
  80                                 if ((c = comparer.Compare(array[mid], item)) == 0)
  81                                         return true;
  82
  83                                 if (c > 0)
  84                                 { top = mid; }
  85                                 else
  86                                 { bot = mid + 1; }
  87
  88                                 mid = (bot + top) / 2;
  89                         }
  90
  91                         return false;
  92                 }
  93
  94                 private int indexOf(T item)
  95                 {
  96                         int ind;
  97
  98                         if (binarySearch(item, out ind))
  99                                 return ind;
 100
 101                         return -1;
 102                 }
 103
 104                 #endregion
 105
 106                 #region Constructors
 107
 108                 /// <summary>
 109                 /// Create a dynamic sorted array with a natural comparer
 110                 /// </summary>
 111                 public SortedArray() : this(8) { }
 112
 113
 114                 /// <summary>
 115                 /// Create a dynamic sorted array with a natural comparer
 116                 /// and prescribed initial capacity.
 117                 /// </summary>
 118                 /// <param name="capacity">The capacity</param>
 119                 public SortedArray(int capacity)
 120                         : this(ComparerBuilder.FromComparable<T>.Examine()) { }
 121
 122
 123                 /// <summary>
 124                 /// Create a dynamic sorted array with an external comparer
 125                 /// </summary>
 126                 /// <param name="c">The comparer</param>
 127                 public SortedArray(IComparer<T> c)
 128                         : this(8,c) { }
 129
 130
 131                 /// <summary>
 132                 /// Create a dynamic sorted array with an external comparer
 133                 /// and prescribed initial capacity.
 134                 /// </summary>
 135                 /// <param name="capacity">The capacity</param>
 136                 /// <param name="c">The comparer</param>
 137                 public SortedArray(int capacity, IComparer<T> c)
 138                         : this(capacity, c, HasherBuilder.ByPrototype<T>.Examine()) { }
 139
 140                 /// <summary>
 141                 /// Create a dynamic sorted array with an external comparer, an external hasher
 142                 /// and prescribed initial capacity.
 143                 /// </summary>
 144                 /// <param name="capacity">The capacity</param>
 145                 /// <param name="c">The comparer</param>
 146                 /// <param name="h">The hasher (compatible)</param>
 147                 public SortedArray(int capacity, IComparer<T> c, IHasher<T> h)
 148                         : base(capacity, h) { comparer = c; }
 149
 150                 #endregion
 151
 152                 #region IIndexedSorted<T> Members
 153
 154                 /// <summary>
 155                 /// Determine the number of items at or above a supplied threshold.
 156                 /// </summary>
 157                 /// <param name="bot">The lower bound (inclusive)</param>
 158                 /// <returns>The number of matcing items.</returns>
 159                 [Tested]
 160                 public int CountFrom(T bot)
 161                 {
 162                         int lo;
 163
 164                         binarySearch(bot, out lo);
 165                         return size - lo;
 166                 }
 167
 168
 169                 /// <summary>
 170                 /// Determine the number of items between two supplied thresholds.
 171                 /// </summary>
 172                 /// <param name="bot">The lower bound (inclusive)</param>
 173                 /// <param name="top">The upper bound (exclusive)</param>
 174                 /// <returns>The number of matcing items.</returns>
 175                 [Tested]
 176                 public int CountFromTo(T bot, T top)
 177                 {
 178                         int lo, hi;
 179
 180                         binarySearch(bot, out lo);
 181                         binarySearch(top, out hi);
 182                         return hi > lo ? hi - lo : 0;
 183                 }
 184
 185
 186                 /// <summary>
 187                 /// Determine the number of items below a supplied threshold.
 188                 /// </summary>
 189                 /// <param name="top">The upper bound (exclusive)</param>
 190                 /// <returns>The number of matcing items.</returns>
 191                 [Tested]
 192                 public int CountTo(T top)
 193                 {
 194                         int hi;
 195
 196                         binarySearch(top, out hi);
 197                         return hi;
 198                 }
 199
 200
 201                 /// <summary>
 202                 /// Query this sorted collection for items greater than or equal to a supplied value.
 203                 /// </summary>
 204                 /// <param name="bot">The lower bound (inclusive).</param>
 205                 /// <returns>The result directed collection.</returns>
 206                 [Tested]
 207                 public IDirectedCollectionValue<T> RangeFrom(T bot)
 208                 {
 209                         int lo;
 210
 211                         binarySearch(bot, out lo);
 212                         return new Range(this, lo, size - lo, true);
 213                 }
 214
 215
 216                 /// <summary>
 217                 /// Query this sorted collection for items between two supplied values.
 218                 /// </summary>
 219                 /// <param name="bot">The lower bound (inclusive).</param>
 220                 /// <param name="top">The upper bound (exclusive).</param>
 221                 /// <returns>The result directed collection.</returns>
 222                 [Tested]
 223                 public IDirectedCollectionValue<T> RangeFromTo(T bot, T top)
 224                 {
 225                         int lo, hi;
 226
 227                         binarySearch(bot, out lo);
 228                         binarySearch(top, out hi);
 229
 230                         int sz = hi - lo;
 231
 232                         return new Range(this, lo, sz, true);
 233                 }
 234
 235
 236                 /// <summary>
 237                 /// Query this sorted collection for items less than a supplied value.
 238                 /// </summary>
 239                 /// <param name="top">The upper bound (exclusive).</param>
 240                 /// <returns>The result directed collection.</returns>
 241                 [Tested]
 242                 public IDirectedCollectionValue<T> RangeTo(T top)
 243                 {
 244                         int hi;
 245
 246                         binarySearch(top, out hi);
 247                         return new Range(this, 0, hi, true);
 248                 }
 249
 250
 251                 /// <summary>
 252                 /// Create a new indexed sorted collection consisting of the items of this
 253                 /// indexed sorted collection satisfying a certain predicate.
 254                 /// </summary>
 255                 /// <param name="f">The filter delegate defining the predicate.</param>
 256                 /// <returns>The new indexed sorted collection.</returns>
 257                 [Tested]
 258                 public IIndexedSorted<T> FindAll(Filter<T> f)
 259                 {
 260                         SortedArray<T> res = new SortedArray<T>(comparer);
 261                         int j = 0, rescap = res.array.Length;
 262
 263                         for (int i = 0; i < size; i++)
 264                         {
 265                                 T a = array[i];
 266
 267                                 if (f(a))
 268                                 {
 269                                         if (j == rescap) res.expand(rescap = 2 * rescap, j);
 270
 271                                         res.array[j++] = a;
 272                                 }
 273                         }
 274
 275                         res.size = j;
 276                         return res;
 277                 }
 278
 279
 280                 /// <summary>
 281                 /// Create a new indexed sorted collection consisting of the results of
 282                 /// mapping all items of this list.
 283                 /// <exception cref="ArgumentException"/> if the map is not increasing over
 284                 /// the items of this collection (with respect to the two given comparison
 285                 /// relations).
 286                 /// </summary>
 287                 /// <param name="m">The delegate definging the map.</param>
 288                 /// <param name="c">The comparion relation to use for the result.</param>
 289                 /// <returns>The new sorted collection.</returns>
 290                 [Tested]
 291                 public IIndexedSorted<V> Map<V>(Mapper<T,V> m, IComparer<V> c)
 292                 {
 293                         SortedArray<V> res = new SortedArray<V>(size, c);
 294
 295                         if (size > 0)
 296                         {
 297                                 V oldv = res.array[0] = m(array[0]), newv;
 298
 299                                 for (int i = 1; i < size; i++)
 300                                 {
 301                                         if (c.Compare(oldv, newv = res.array[i] = m(array[i])) >= 0)
 302                                                 throw new ArgumentException("mapper not monotonic");
 303
 304                                         oldv = newv;
 305                                 }
 306                         }
 307
 308                         res.size = size;
 309                         return res;
 310                 }
 311
 312                 #endregion
 313
 314                 #region ISorted<T> Members
 315
 316                 /// <summary>
 317                 /// Find the strict predecessor in the sorted collection of a particular value,
 318                 /// i.e. the largest item in the collection less than the supplied value.
 319                 /// <exception cref="InvalidOperationException"/> if no such element exists (the
 320                 /// supplied  value is less than or equal to the minimum of this collection.)
 321                 /// </summary>
 322                 /// <param name="item">The item to find the predecessor for.</param>
 323                 /// <returns>The predecessor.</returns>
 324                 [Tested]
 325                 public T Predecessor(T item)
 326                 {
 327                         int lo;
 328
 329                         binarySearch(item, out lo);
 330                         if (lo == 0)
 331                                 throw new ArgumentOutOfRangeException("item", item, "Below minimum of set");
 332
 333                         return array[lo - 1];
 334                 }
 335
 336
 337                 /// <summary>
 338                 /// Find the strict successor in the sorted collection of a particular value,
 339                 /// i.e. the least item in the collection greater than the supplied value.
 340                 /// <exception cref="InvalidOperationException"/> if no such element exists (the
 341                 /// supplied  value is greater than or equal to the maximum of this collection.)
 342                 /// </summary>
 343                 /// <param name="item">The item to find the successor for.</param>
 344                 /// <returns>The successor.</returns>
 345                 [Tested]
 346                 public T Successor(T item)
 347                 {
 348                         int hi;
 349
 350                         if (binarySearch(item, out hi)) hi++;
 351
 352                         if (hi >= size)
 353                                 throw new ArgumentOutOfRangeException("item", item, "Above maximum of set");
 354
 355                         return array[hi];
 356                 }
 357
 358
 359                 /// <summary>
 360                 /// Find the weak predecessor in the sorted collection of a particular value,
 361                 /// i.e. the largest item in the collection less than or equal to the supplied value.
 362                 /// <exception cref="InvalidOperationException"/> if no such element exists (the
 363                 /// supplied  value is less than the minimum of this collection.)
 364                 /// </summary>
 365                 /// <param name="item">The item to find the weak predecessor for.</param>
 366                 /// <returns>The weak predecessor.</returns>
 367                 [Tested]
 368                 public T WeakPredecessor(T item)
 369                 {
 370                         int lo;
 371
 372                         if (!binarySearch(item, out lo)) lo--;
 373
 374                         if (lo < 0)
 375                                 throw new ArgumentOutOfRangeException("item", item, "Below minimum of set");
 376
 377                         return array[lo];
 378                 }
 379
 380
 381                 /// <summary>
 382                 /// Find the weak successor in the sorted collection of a particular value,
 383                 /// i.e. the least item in the collection greater than or equal to the supplied value.
 384                 /// <exception cref="InvalidOperationException"/> if no such element exists (the
 385                 /// supplied  value is greater than the maximum of this collection.)
 386                 /// </summary>
 387                 /// <param name="item">The item to find the weak successor for.</param>
 388                 /// <returns>The weak successor.</returns>
 389                 [Tested]
 390                 public T WeakSuccessor(T item)
 391                 {
 392                         int hi;
 393
 394                         binarySearch(item, out hi);
 395                         if (hi >= size)
 396                                 throw new ArgumentOutOfRangeException("item", item, "Above maximum of set");
 397
 398                         return array[hi];
 399                 }
 400
 401
 402                 /// <summary>
 403                 /// Perform a search in the sorted collection for the ranges in which a
 404                 /// non-decreasing function from the item type to <code>int</code> is
 405                 /// negative, zero respectively positive. If the supplied cut function is
 406                 /// not non-decreasing, the result of this call is undefined.
 407                 /// </summary>
 408                 /// <param name="c">The cut function <code>T</code> to <code>int</code>, given
 409                 /// as an <code>IComparable&lt;T&gt;</code> object, where the cut function is
 410                 /// the <code>c.CompareTo(T that)</code> method.</param>
 411                 /// <param name="low">Returns the largest item in the collection, where the
 412                 /// cut function is negative (if any).</param>
 413                 /// <param name="lowIsValid">True if the cut function is negative somewhere
 414                 /// on this collection.</param>
 415                 /// <param name="high">Returns the least item in the collection, where the
 416                 /// cut function is positive (if any).</param>
 417                 /// <param name="highIsValid">True if the cut function is positive somewhere
 418                 /// on this collection.</param>
 419                 /// <returns></returns>
 420                 [Tested]
 421                 public bool Cut(IComparable<T> c, out T low, out bool lowIsValid, out T high, out bool highIsValid)
 422                 {
 423                         int lbest = -1, rbest = size;
 424
 425                         low = default(T);
 426                         lowIsValid = false;
 427                         high = default(T);
 428                         highIsValid = false;
 429
 430                         int bot = 0, top = size, mid, comp = -1, sol;
 431
 432                         mid = top / 2;
 433                         while (top > bot)
 434                         {
 435                                 if ((comp = c.CompareTo(array[mid])) == 0)
 436                                         break;
 437
 438                                 if (comp < 0)
 439                                 { rbest = top = mid; }
 440                                 else
 441                                 { lbest = mid; bot = mid + 1; }
 442
 443                                 mid = (bot + top) / 2;
 444                         }
 445
 446                         if (comp != 0)
 447                         {
 448                                 if (lbest >= 0) { lowIsValid = true; low = array[lbest]; }
 449
 450                                 if (rbest < size) { highIsValid = true; high = array[rbest]; }
 451
 452                                 return false;
 453                         }
 454
 455                         sol = mid;
 456                         bot = sol - 1;
 457
 458                         //Invariant: c.Compare(array[x]) < 0  when rbest <= x < size
 459                         //           c.Compare(array[x]) >= 0 when x < bot)
 460                         //(Assuming c.Compare monotonic)
 461                         while (rbest > bot)
 462                         {
 463                                 mid = (bot + rbest) / 2;
 464                                 if (c.CompareTo(array[mid]) < 0)
 465                                 { rbest = mid; }
 466                                 else
 467                                 { bot = mid + 1; }
 468                         }
 469
 470                         if (rbest < size) { highIsValid = true; high = array[rbest]; }
 471
 472                         top = sol + 1;
 473
 474                         //Invariant: c.Compare(array[x]) > 0  when 0 <= x <= lbest
 475                         //           c.Compare(array[x]) <= 0 when x>top)
 476                         //(Assuming c.Compare monotonic)
 477                         while (top > lbest)
 478                         {
 479                                 mid = (lbest + top + 1) / 2;
 480                                 if (c.CompareTo(array[mid]) > 0)
 481                                 { lbest = mid; }
 482                                 else
 483                                 { top = mid - 1; }
 484                         }
 485
 486                         if (lbest >= 0) { lowIsValid = true; low = array[lbest]; }
 487
 488                         return true;
 489                 }
 490
 491
 492                 IDirectedEnumerable<T> ISorted<T>.RangeFrom(T bot)
 493                 { return RangeFrom(bot); }
 494
 495
 496                 IDirectedEnumerable<T> ISorted<T>.RangeFromTo(T bot, T top)
 497                 { return RangeFromTo(bot, top); }
 498
 499
 500                 IDirectedEnumerable<T> ISorted<T>.RangeTo(T top)
 501                 { return RangeTo(top); }
 502
 503
 504                 /// <summary>
 505                 /// Create a directed collection with the same items as this collection.
 506                 /// </summary>
 507                 /// <returns>The result directed collection.</returns>
 508                 [Tested]
 509                 public IDirectedCollectionValue<T> RangeAll()
 510                 { return new Range(this, 0, size, true); }
 511
 512
 513                 /// <summary>
 514                 /// Add all the items from another collection with an enumeration order that
 515                 /// is increasing in the items.
 516                 /// <exception cref="ArgumentException"/> if the enumerated items turns out
 517                 /// not to be in increasing order.
 518                 /// </summary>
 519                 /// <param name="items">The collection to add.</param>
 520                 [Tested]
 521                 public void AddSorted(MSG.IEnumerable<T> items)
 522                 {
 523                         //Unless items have <=1 elements we would expect it to be
 524                         //too expensive to do repeated inserts, thus:
 525                         updatecheck();
 526
 527                         int j = 0, i = 0, c = -1, itemcount = EnumerableBase<T>.countItems(items);
 528                         SortedArray<T> res = new SortedArray<T>(size + itemcount, comparer);
 529                         T lastitem = default(T);
 530
 531                         foreach (T item in items)
 532                         {
 533                                 while (i < size && (c = comparer.Compare(array[i], item)) <= 0)
 534                                 {
 535                                         lastitem = res.array[j++] = array[i++];
 536                                         if (c == 0)
 537                                                 goto next;
 538                                 }
 539
 540                                 if (j > 0 && comparer.Compare(lastitem, item) >= 0)
 541                                         throw new ArgumentException("Argument not sorted");
 542
 543                                 lastitem = res.array[j++] = item;
 544                         next :
 545                                 c = -1;
 546                         }
 547
 548                         while (i < size) res.array[j++] = array[i++];
 549
 550                         size = j;
 551                         array = res.array;
 552                 }
 553
 554
 555                 /// <summary>
 556                 /// Remove all items of this collection above or at a supplied threshold.
 557                 /// </summary>
 558                 /// <param name="low">The lower threshold (inclusive).</param>
 559                 [Tested]
 560                 public void RemoveRangeFrom(T low)
 561                 {
 562                         int lowind;
 563
 564                         binarySearch(low, out lowind);
 565                         if (lowind == size)
 566                                 return;
 567
 568                         Array.Clear(array, lowind, size - lowind);
 569                         size = lowind;
 570                 }
 571
 572
 573                 /// <summary>
 574                 /// Remove all items of this collection between two supplied thresholds.
 575                 /// </summary>
 576                 /// <param name="low">The lower threshold (inclusive).</param>
 577                 /// <param name="hi">The upper threshold (exclusive).</param>
 578                 [Tested]
 579                 public void RemoveRangeFromTo(T low, T hi)
 580                 {
 581                         int lowind, highind;
 582
 583                         binarySearch(low, out lowind);
 584                         binarySearch(hi, out highind);
 585                         if (highind <= lowind)
 586                                 return;
 587
 588                         Array.Copy(array, highind, array, lowind, size - highind);
 589                         Array.Clear(array, size - highind + lowind, highind - lowind);
 590                         size -= highind - lowind;
 591                 }
 592
 593
 594                 /// <summary>
 595                 /// Remove all items of this collection below a supplied threshold.
 596                 /// </summary>
 597                 /// <param name="hi">The upper threshold (exclusive).</param>
 598                 [Tested]
 599                 public void RemoveRangeTo(T hi)
 600                 {
 601                         int highind;
 602
 603                         binarySearch(hi, out highind);
 604                         if (highind == 0)
 605                                 return;
 606
 607                         Array.Copy(array, highind, array, 0, size - highind);
 608                         Array.Clear(array, size - highind, highind);
 609                         size = size - highind;
 610                 }
 611
 612                 #endregion
 613
 614                 #region ISequenced<T> Members
 615
 616                 int ISequenced<T>.GetHashCode() { return sequencedhashcode(); }
 617
 618
 619                 bool ISequenced<T>.Equals(ISequenced<T> that) { return sequencedequals(that); }
 620
 621                 #endregion
 622
 623                 #region IEditableCollection<T> Members
 624                 /// <summary>
 625                 /// The value is symbolic indicating the type of asymptotic complexity
 626                 /// in terms of the size of this collection (worst-case).
 627                 /// </summary>
 628                 /// <value>Speed.Log</value>
 629                 [Tested]
 630                 public Speed ContainsSpeed { [Tested]get { return Speed.Log; } }
 631
 632
 633                 int ICollection<T>.GetHashCode() { return unsequencedhashcode(); }
 634
 635
 636                 bool ICollection<T>.Equals(ICollection<T> that)
 637                 { return unsequencedequals(that); }
 638
 639
 640                 /// <summary>
 641                 /// Check if this collection contains (an item equivalent to according to the
 642                 /// itemhasher) a particular value.
 643                 /// </summary>
 644                 /// <param name="item">The value to check for.</param>
 645                 /// <returns>True if the items is in this collection.</returns>
 646                 [Tested]
 647                 public bool Contains(T item)
 648                 {
 649                         int ind;
 650
 651                         return binarySearch(item, out ind);
 652                 }
 653
 654
 655                 /// <summary>
 656                 /// Check if this collection contains an item equivalent according to the
 657                 /// itemhasher to a particular value. If so, return in the ref argument (a
 658                 /// binary copy of) the actual value found.
 659                 /// </summary>
 660                 /// <param name="item">The value to look for.</param>
 661                 /// <returns>True if the items is in this collection.</returns>
 662                 [Tested]
 663                 public bool Find(ref T item)
 664                 {
 665                         int ind;
 666
 667                         if (binarySearch(item, out ind))
 668                         {
 669                                 item = array[ind];
 670                                 return true;
 671                         }
 672
 673                         return false;
 674                 }
 675
 676
 677                 //This should probably just be bool Add(ref T item); !!!
 678                 /// <summary>
 679                 /// Check if this collection contains an item equivalent according to the
 680                 /// itemhasher to a particular value. If so, return in the ref argument (a
 681                 /// binary copy of) the actual value found. Else, add the item to the collection.
 682                 /// </summary>
 683                 /// <param name="item">The value to look for.</param>
 684                 /// <returns>True if the item was added (hence not found).</returns>
 685                 [Tested]
 686                 public bool FindOrAdd(ref T item)
 687                 {
 688                         updatecheck();
 689
 690                         int ind;
 691
 692                         if (binarySearch(item, out ind))
 693                         {
 694                                 item = array[ind];
 695                                 return true;
 696                         }
 697
 698                         if (size == array.Length - 1) expand();
 699
 700                         Array.Copy(array, ind, array, ind + 1, size - ind);
 701                         array[ind] = item;
 702                         size++;
 703                         return false;
 704                 }
 705
 706
 707                 /// <summary>
 708                 /// Check if this collection contains an item equivalent according to the
 709                 /// itemhasher to a particular value. If so, update the item in the collection
 710                 /// to with a binary copy of the supplied value. If the collection has bag semantics,
 711                 /// it is implementation dependent if this updates all equivalent copies in
 712                 /// the collection or just one.
 713                 /// </summary>
 714                 /// <param name="item">Value to update.</param>
 715                 /// <returns>True if the item was found and hence updated.</returns>
 716                 [Tested]
 717                 public bool Update(T item)
 718                 {
 719                         updatecheck();
 720
 721                         int ind;
 722
 723                         if (binarySearch(item, out ind))
 724                         {
 725                                 array[ind] = item;
 726                                 return true;
 727                         }
 728
 729                         return false;
 730                 }
 731
 732
 733                 /// <summary>
 734                 /// Check if this collection contains an item equivalent according to the
 735                 /// itemhasher to a particular value. If so, update the item in the collection
 736                 /// to with a binary copy of the supplied value; else add the value to the collection.
 737                 /// </summary>
 738                 /// <param name="item">Value to add or update.</param>
 739                 /// <returns>True if the item was found and updated (hence not added).</returns>
 740                 [Tested]
 741                 public bool UpdateOrAdd(T item)
 742                 {
 743                         updatecheck();
 744
 745                         int ind;
 746
 747                         if (binarySearch(item, out ind))
 748                         {
 749                                 array[ind] = item;
 750                                 return true;
 751                         }
 752
 753                         if (size == array.Length - 1) expand();
 754
 755                         Array.Copy(array, ind, array, ind + 1, size - ind);
 756                         array[ind] = item;
 757                         size++;
 758                         return false;
 759                 }
 760
 761
 762                 /// <summary>
 763                 /// Remove a particular item from this collection. If the collection has bag
 764                 /// semantics only one copy equivalent to the supplied item is removed.
 765                 /// </summary>
 766                 /// <param name="item">The value to remove.</param>
 767                 /// <returns>True if the item was found (and removed).</returns>
 768                 [Tested]
 769                 public bool Remove(T item)
 770                 {
 771                         int ind;
 772
 773                         updatecheck();
 774                         if (binarySearch(item, out ind))
 775                         {
 776                                 Array.Copy(array, ind + 1, array, ind, size - ind - 1);
 777                                 array[--size] = default(T);
 778                                 return true;
 779                         }
 780
 781                         return false;
 782                 }
 783
 784
 785                 /// <summary>
 786                 /// Remove a particular item from this collection if found. If the collection
 787                 /// has bag semantics only one copy equivalent to the supplied item is removed,
 788                 /// which one is implementation dependent.
 789                 /// If an item was removed, report a binary copy of the actual item removed in
 790                 /// the argument.
 791                 /// </summary>
 792                 /// <param name="item">The value to remove on input.</param>
 793                 /// <returns>True if the item was found (and removed).</returns>
 794                 [Tested]
 795                 public bool RemoveWithReturn(ref T item)
 796                 {
 797                         int ind;
 798
 799                         updatecheck();
 800                         if (binarySearch(item, out ind))
 801                         {
 802                                 item = array[ind];
 803                                 Array.Copy(array, ind + 1, array, ind, size - ind - 1);
 804                                 array[--size] = default(T);
 805                                 return true;
 806                         }
 807
 808                         return false;
 809                 }
 810
 811
 812                 /// <summary>
 813                 /// Remove all items in another collection from this one.
 814                 /// </summary>
 815                 /// <param name="items">The items to remove.</param>
 816                 [Tested]
 817                 public void RemoveAll(MSG.IEnumerable<T> items)
 818                 {
 819                         //This is O(m*logn) with n bits extra storage
 820                         //(Not better to collect the m items and sort them)
 821                         updatecheck();
 822
 823                         int[] toremove = new int[(size >>5) + 1];
 824                         int ind, j = 0;
 825
 826                         foreach (T item in items)
 827                                 if (binarySearch(item, out ind))
 828                                         toremove[ind >>5] |= 1 << (ind & 31);
 829
 830                         for (int i = 0; i < size; i++)
 831                                 if ((toremove[i >>5] & (1 << (i & 31))) == 0)
 832                                         array[j++] = array[i];
 833
 834                         Array.Clear(array, j, size - j);
 835                         size = j;
 836                 }
 837
 838
 839                 /// <summary>
 840                 /// Remove all items not in some other collection from this one.
 841                 /// </summary>
 842                 /// <param name="items">The items to retain.</param>
 843                 [Tested]
 844                 public void RetainAll(MSG.IEnumerable<T> items)
 845                 {
 846                         //This is O(m*logn) with n bits extra storage
 847                         //(Not better to collect the m items and sort them)
 848                         updatecheck();
 849
 850                         int[] toretain = new int[(size >>5) + 1];
 851                         int ind, j = 0;
 852
 853                         foreach (T item in items)
 854                                 if (binarySearch(item, out ind))
 855                                         toretain[ind >>5] |= 1 << (ind & 31);
 856
 857                         for (int i = 0; i < size; i++)
 858                                 if ((toretain[i >>5] & (1 << (i & 31))) != 0)
 859                                         array[j++] = array[i];
 860
 861                         Array.Clear(array, j, size - j);
 862                         size = j;
 863                 }
 864
 865
 866                 /// <summary>
 867                 /// Check if this collection contains all the values in another collection.
 868                 /// Multiplicities are not taken into account.
 869                 /// </summary>
 870                 /// <param name="items">The </param>
 871                 /// <returns>True if all values in <code>items</code>is in this collection.</returns>
 872                 [Tested]
 873                 public bool ContainsAll(MSG.IEnumerable<T> items)
 874                 {
 875                         int tmp;
 876
 877                         foreach (T item in items)
 878                                 if (!binarySearch(item, out tmp))
 879                                         return false;
 880
 881                         return true;
 882                 }
 883
 884
 885                 /// <summary>
 886                 /// Count the number of items of the collection equal to a particular value.
 887                 /// Returns 0 if and only if the value is not in the collection.
 888                 /// </summary>
 889                 /// <param name="item">The value to count.</param>
 890                 /// <returns>The number of copies found (0 or 1).</returns>
 891                 [Tested]
 892                 public int ContainsCount(T item)
 893                 {
 894                         int tmp;
 895
 896                         return binarySearch(item, out tmp) ? 1 : 0;
 897                 }
 898
 899
 900                 /// <summary>
 901                 /// Remove all (0 or 1) items equivalent to a given value.
 902                 /// </summary>
 903                 /// <param name="item">The value to remove.</param>
 904                 [Tested]
 905                 public void RemoveAllCopies(T item) { Remove(item); }
 906
 907
 908                 /// <summary>
 909                 /// Check the integrity of the internal data structures of this collection.
 910                 /// Only avaliable in DEBUG builds???
 911                 /// </summary>
 912                 /// <returns>True if check does not fail.</returns>
 913                 [Tested]
 914                 public override bool Check()
 915                 {
 916                         bool retval = true;
 917
 918                         if (size > array.Length)
 919                         {
 920                                 Console.WriteLine("Bad size ({0}) > array.Length ({1})", size, array.Length);
 921                                 return false;
 922                         }
 923
 924                         for (int i = 0; i < size; i++)
 925                         {
 926                                 if ((object)(array[i]) == null)
 927                                 {
 928                                         Console.WriteLine("Bad element: null at index {0}", i);
 929                                         return false;
 930                                 }
 931
 932                                 if (i > 0 && comparer.Compare(array[i], array[i - 1]) <= 0)
 933                                 {
 934                                         Console.WriteLine("Inversion at index {0}", i);
 935                                         retval = false;
 936                                 }
 937                         }
 938
 939                         return retval;
 940                 }
 941
 942                 #endregion
 943
 944                 #region ISink<T> Members
 945
 946                 /// <summary>
 947                 ///
 948                 /// </summary>
 949                 /// <value>False since this collection has set semantics</value>
 950                 [Tested]
 951                 public bool AllowsDuplicates { [Tested]get { return false; } }
 952
 953
 954                 /// <summary>
 955                 /// Add an item to this collection if possible. If this collection has set
 956                 /// semantics, the item will be added if not already in the collection. If
 957                 /// bag semantics, the item will always be added.
 958                 /// </summary>
 959                 /// <param name="item">The item to add.</param>
 960                 /// <returns>True if item was added.</returns>
 961                 [Tested]
 962                 public bool Add(T item)
 963                 {
 964                         updatecheck();
 965
 966                         int ind;
 967
 968                         if (binarySearch(item, out ind)) return false;
 969
 970                         insert(ind, item);
 971                         return true;
 972                 }
 973
 974
 975                 /// <summary>
 976                 /// Add the elements from another collection to this collection. If this
 977                 /// collection has set semantics, only items not already in the collection
 978                 /// will be added.
 979                 /// </summary>
 980                 /// <param name="items">The items to add.</param>
 981                 [Tested]
 982                 public void AddAll(MSG.IEnumerable<T> items)
 983                 {
 984                         int toadd = EnumerableBase<T>.countItems(items), newsize = array.Length;
 985
 986                         while (newsize < size + toadd) { newsize *= 2; }
 987
 988                         T[] newarr = new T[newsize];
 989
 990                         toadd = 0;
 991                         foreach (T item in items) newarr[size + toadd++] = item;
 992
 993                         Sorting.IntroSort<T>(newarr, size, size + toadd, comparer);
 994
 995                         int j = 0, i = 0;
 996                         T lastitem = default(T);
 997
 998                         //The following eliminates duplicates (including duplicates in input)
 999                         //while merging the old and new collection
1000                         for (int k = size, klimit = size + toadd; k < klimit; k++)
1001                         {
1002                                 while (i < size && comparer.Compare(array[i], newarr[k]) <= 0)
1003                                         lastitem = newarr[j++] = array[i++];
1004
1005                                 if (j == 0 || comparer.Compare(lastitem, newarr[k]) < 0)
1006                                         lastitem = newarr[j++] = newarr[k];
1007                         }
1008
1009                         while (i < size) newarr[j++] = array[i++];
1010
1011                         Array.Clear(newarr, j, size + toadd - j);
1012                         size = j;
1013                         array = newarr;
1014                 }
1015
1016         /// <summary>
1017         /// Add the elements from another collection with a more specialized item type
1018         /// to this collection. Since this
1019         /// collection has set semantics, 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 void AddAll<U>(MSG.IEnumerable<U> items) where U : T
1025         {
1026             int toadd = EnumerableBase<U>.countItems(items), newsize = array.Length;
1027
1028             while (newsize < size + toadd) { newsize *= 2; }
1029
1030             T[] newarr = new T[newsize];
1031
1032             toadd = 0;
1033             foreach (T item in items) newarr[size + toadd++] = item;
1034
1035             Sorting.IntroSort<T>(newarr, size, size + toadd, comparer);
1036
1037             int j = 0, i = 0;
1038             T lastitem = default(T);
1039
1040             //The following eliminates duplicates (including duplicates in input)
1041             //while merging the old and new collection
1042             for (int k = size, klimit = size + toadd; k < klimit; k++)
1043             {
1044                 while (i < size && comparer.Compare(array[i], newarr[k]) <= 0)
1045                     lastitem = newarr[j++] = array[i++];
1046
1047                 if (j == 0 || comparer.Compare(lastitem, newarr[k]) < 0)
1048                     lastitem = newarr[j++] = newarr[k];
1049             }
1050
1051             while (i < size) newarr[j++] = array[i++];
1052
1053             Array.Clear(newarr, j, size + toadd - j);
1054             size = j;
1055             array = newarr;
1056         }
1057
1058         #endregion
1059
1060                 #region IPriorityQueue<T> Members
1061
1062                 /// <summary>
1063                 /// Find the current least item of this priority queue.
1064                 /// </summary>
1065                 /// <returns>The least item.</returns>
1066                 [Tested]
1067                 public T FindMin()
1068                 {
1069                         if (size == 0)
1070                                 throw new InvalidOperationException("Priority queue is empty");
1071
1072                         return array[0];
1073                 }
1074
1075                 /// <summary>
1076                 /// Remove the least item from this  priority queue.
1077                 /// </summary>
1078                 /// <returns>The removed item.</returns>
1079                 [Tested]
1080                 public T DeleteMin()
1081                 {
1082                         updatecheck();
1083                         if (size == 0)
1084                                 throw new InvalidOperationException("Priority queue is empty");
1085
1086                         T retval = array[0];
1087
1088                         size--;
1089                         Array.Copy(array, 1, array, 0, size);
1090                         array[size] = default(T);
1091                         return retval;
1092                 }
1093
1094
1095                 /// <summary>
1096                 /// Find the current largest item of this priority queue.
1097                 /// </summary>
1098                 /// <returns>The largest item.</returns>
1099                 [Tested]
1100                 public T FindMax()
1101                 {
1102                         if (size == 0)
1103                                 throw new InvalidOperationException("Priority queue is empty");
1104
1105                         return array[size - 1];
1106                 }
1107
1108
1109                 /// <summary>
1110                 /// Remove the largest item from this  priority queue.
1111                 /// </summary>
1112                 /// <returns>The removed item.</returns>
1113                 [Tested]
1114                 public T DeleteMax()
1115                 {
1116                         updatecheck();
1117                         if (size == 0)
1118                                 throw new InvalidOperationException("Priority queue is empty");
1119
1120                         T retval = array[size - 1];
1121
1122                         size--;
1123                         array[size] = default(T);
1124                         return retval;
1125                 }
1126
1127         /// <summary>
1128         /// The comparer object supplied at creation time for this collection
1129         /// </summary>
1130         /// <value>The comparer</value>
1131         public IComparer<T> Comparer { get { return comparer; } }
1132
1133                 #endregion
1134
1135                 #region IIndexed<T> Members
1136
1137                 /// <summary>
1138                 /// <exception cref="IndexOutOfRangeException"/> if i is negative or
1139                 /// &gt;= the size of the collection.
1140                 /// </summary>
1141                 /// <value>The i'th item of this list.</value>
1142                 /// <param name="i">the index to lookup</param>
1143                 [Tested]
1144                 public T this[int i]
1145                 {
1146                         [Tested]
1147                         get
1148                         {
1149                                 if (i < 0 || i >= size)
1150                                         throw new IndexOutOfRangeException();
1151
1152                                 return array[i];
1153                         }
1154                 }
1155
1156
1157                 /// <summary>
1158                 /// Searches for an item in the list going forwrds from the start.
1159                 /// </summary>
1160                 /// <param name="item">Item to search for.</param>
1161                 /// <returns>Index of item from start.</returns>
1162                 [Tested]
1163                 public int IndexOf(T item) { return indexOf(item); }
1164
1165
1166                 /// <summary>
1167                 /// Searches for an item in the list going backwords from the end.
1168                 /// </summary>
1169                 /// <param name="item">Item to search for.</param>
1170                 /// <returns>Index of of item from the end.</returns>
1171                 [Tested]
1172                 public int LastIndexOf(T item){ return indexOf(item); }
1173
1174
1175                 /// <summary>
1176                 /// Remove the item at a specific position of the list.
1177                 /// <exception cref="IndexOutOfRangeException"/> if i is negative or
1178                 /// &gt;= the size of the collection.
1179                 /// </summary>
1180                 /// <param name="i">The index of the item to remove.</param>
1181                 /// <returns>The removed item.</returns>
1182                 [Tested]
1183                 public T RemoveAt(int i)
1184                 {
1185                         if (i < 0 || i >= size)
1186                                 throw new IndexOutOfRangeException("Index out of range for sequenced collection");
1187
1188                         updatecheck();
1189
1190                         T retval = array[i];
1191
1192                         size--;
1193                         Array.Copy(array, i + 1, array, i, size - i);
1194                         array[size] = default(T);
1195                         return retval;
1196                 }
1197
1198                 /// <summary>
1199                 /// Remove all items in an index interval.
1200                 /// <exception cref="IndexOutOfRangeException"/>???.
1201                 /// </summary>
1202                 /// <param name="start">The index of the first item to remove.</param>
1203                 /// <param name="count">The number of items to remove.</param>
1204                 [Tested]
1205                 public void RemoveInterval(int start, int count)
1206                 {
1207                         updatecheck();
1208                         checkRange(start, count);
1209                         Array.Copy(array, start + count, array, start, size - start - count);
1210                         size -= count;
1211                         Array.Clear(array, size, count);
1212                 }
1213
1214                 #endregion
1215
1216                 #region IDirectedEnumerable<T> Members
1217
1218                 /// <summary>
1219                 /// Create a collection containing the same items as this collection, but
1220                 /// whose enumerator will enumerate the items backwards. The new collection
1221                 /// will become invalid if the original is modified. Method typicaly used as in
1222                 /// <code>foreach (T x in coll.Backwards()) {...}</code>
1223                 /// </summary>
1224                 /// <returns>The backwards collection.</returns>
1225                 [Tested]
1226                 IDirectedEnumerable<T> IDirectedEnumerable<T>.Backwards()
1227                 { return Backwards(); }
1228
1229                 #endregion
1230         }
1231 }
1232 #endif