mcs/class/Mono.C5/heaps/IntervalHeap.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
  27 namespace C5
  28 {
  29         /// <summary>
  30         /// A priority queue class based on an interval heap data structure.
  31         /// </summary>
  32         public class IntervalHeap<T>: CollectionValueBase<T>, IPriorityQueue<T>
  33         {
  34                 #region Fields
  35                 struct Interval
  36                 {
  37                         internal T first, last;
  38
  39
  40                         public override string ToString() { return String.Format("[{0}; {1}]", first, last); }
  41                 }
  42
  43
  44
  45                 object syncroot = new object();
  46
  47         int stamp;
  48
  49         IComparer<T> comparer;
  50
  51                 Interval[] heap;
  52
  53                 int size;
  54                 #endregion
  55
  56                 #region Util
  57                 void heapifyMin(int i)
  58                 {
  59                         int j = i, minpt = j;
  60                         T pv = heap[j].first, min = pv;
  61
  62                         while (true)
  63                         {
  64                                 int l = 2 * j + 1, r = l + 1;
  65                                 T lv, rv, other;
  66
  67                                 if (2 * l < size && comparer.Compare(lv = heap[l].first, min) < 0) { minpt = l; min = lv; }
  68
  69                 if (2 * r < size && comparer.Compare(rv = heap[r].first, min) < 0) { minpt = r; min = rv; }
  70
  71                 if (minpt == j)
  72                                         break;
  73
  74                                 other = heap[minpt].last;
  75                                 heap[j].first = min;
  76                 if (2 * minpt + 1 < size && comparer.Compare(pv, other) > 0)
  77                 { heap[minpt].last = pv; pv = other; }
  78
  79                                 min = pv;
  80                                 j = minpt;
  81                         }
  82
  83                         if (minpt != i)
  84                                 heap[minpt].first = min;
  85                 }
  86
  87
  88                 void heapifyMax(int i)
  89                 {
  90                         int j = i, maxpt = j;
  91                         T pv = heap[j].last, max = pv;
  92
  93                         while (true)
  94                         {
  95                                 int l = 2 * j + 1, r = l + 1;
  96                                 T lv, rv, other;
  97
  98                 if (2 * l + 1 < size && comparer.Compare(lv = heap[l].last, max) > 0) { maxpt = l; max = lv; }
  99
 100                 if (2 * r + 1 < size && comparer.Compare(rv = heap[r].last, max) > 0) { maxpt = r; max = rv; }
 101
 102                 if (maxpt == j)
 103                                         break;
 104
 105                                 other = heap[maxpt].first;
 106                                 heap[j].last = max;
 107                 if (comparer.Compare(pv, other) < 0)
 108                 {
 109                                         heap[maxpt].first = pv;
 110                                         pv = other;
 111                                 }
 112
 113                                 max = pv;
 114                                 j = maxpt;
 115                         }
 116
 117                         if (maxpt != i)
 118                                 heap[maxpt].last = max;
 119                 }
 120
 121
 122                 void bubbleUpMin(int i)
 123                 {
 124                         if (i > 0)
 125                         {
 126                                 T min = heap[i].first, iv = min;
 127                                 int p = (i + 1) / 2 - 1;
 128
 129                                 while (i > 0)
 130                                 {
 131                     if (comparer.Compare(iv, min = heap[p = (i + 1) / 2 - 1].first) < 0)
 132                     {
 133                                                 heap[i].first = min; min = iv;
 134                                                 i = p;
 135                                         }
 136                                         else
 137                                                 break;
 138                                 }
 139
 140                                 heap[i].first = iv;
 141                         }
 142                 }
 143
 144
 145                 void bubbleUpMax(int i)
 146                 {
 147                         if (i > 0)
 148                         {
 149                                 T max = heap[i].last, iv = max;
 150                                 int p = (i + 1) / 2 - 1;
 151
 152                                 while (i > 0)
 153                                 {
 154                     if (comparer.Compare(iv, max = heap[p = (i + 1) / 2 - 1].last) > 0)
 155                     {
 156                                                 heap[i].last = max; max = iv;
 157                                                 i = p;
 158                                         }
 159                                         else
 160                                                 break;
 161                                 }
 162
 163                                 heap[i].last = iv;
 164                         }
 165                 }
 166
 167                 #endregion
 168
 169                 #region Constructors
 170                 /// <summary>
 171                 /// Create an interval heap with natural item comparer and default initial capacity (16)
 172                 /// </summary>
 173                 public IntervalHeap() : this(16) { }
 174
 175
 176                 /// <summary>
 177                 /// Create an interval heap with external item comparer and default initial capacity (16)
 178                 /// </summary>
 179                 /// <param name="c">The external comparer</param>
 180                 public IntervalHeap(IComparer<T> c) : this(c,16) { }
 181
 182
 183                 /// <summary>
 184                 /// Create an interval heap with natural item comparer and prescribed initial capacity
 185                 /// </summary>
 186                 /// <param name="capacity">The initial capacity</param>
 187                 public IntervalHeap(int capacity)  : this(ComparerBuilder.FromComparable<T>.Examine(),capacity) { }
 188
 189
 190                 /// <summary>
 191                 /// Create an interval heap with external item comparer and prescribed initial capacity
 192                 /// </summary>
 193                 /// <param name="c">The external comparer</param>
 194                 /// <param name="capacity">The initial capacity</param>
 195                 public IntervalHeap(IComparer<T> c, int capacity)
 196                 {
 197                         comparer = c;
 198
 199                         int length = 1;
 200
 201                         while (length < capacity) length <<= 1;
 202
 203                         heap = new Interval[length];
 204                 }
 205                 #endregion
 206
 207                 #region IPriorityQueue<T> Members
 208
 209                 /// <summary>
 210                 /// Find the current least item of this priority queue.
 211                 /// <exception cref="InvalidOperationException"/> if queue is empty
 212                 /// </summary>
 213                 /// <returns>The least item.</returns>
 214                 [Tested]
 215                 public T FindMin()
 216                 {
 217                         if (size == 0)
 218                                 throw new InvalidOperationException("Heap is empty");
 219
 220                         return heap[0].first;
 221                 }
 222
 223
 224                 /// <summary>
 225                 /// Remove the least item from this  priority queue.
 226                 /// <exception cref="InvalidOperationException"/> if queue is empty
 227                 /// </summary>
 228                 /// <returns>The removed item.</returns>
 229                 [Tested]
 230                 public T DeleteMin()
 231                 {
 232             stamp++;
 233             if (size == 0)
 234                 throw new InvalidOperationException("Heap is empty");
 235
 236                         T retval = heap[0].first;;
 237                         if (size == 1)
 238                         {
 239                                 size = 0;
 240                                 heap[0].first = default(T);
 241                         }
 242                         else
 243                         {
 244                                 int ind = (size - 1) / 2;
 245
 246                                 if (size % 2 == 0)
 247                                 {
 248                                         heap[0].first = heap[ind].last;
 249                                         heap[ind].last = default(T);
 250                                 }
 251                                 else
 252                                 {
 253                                         heap[0].first = heap[ind].first;
 254                                         heap[ind].first = default(T);
 255                                 }
 256
 257                                 size--;
 258                                 heapifyMin(0);
 259                         }
 260
 261                         return retval;
 262                 }
 263
 264
 265                 /// <summary>
 266                 /// Find the current largest item of this priority queue.
 267                 /// <exception cref="InvalidOperationException"/> if queue is empty
 268                 /// </summary>
 269                 /// <returns>The largest item.</returns>
 270                 [Tested]
 271                 public T FindMax()
 272                 {
 273                         if (size == 0)
 274                                 throw new InvalidOperationException("Heap is empty");
 275                         else if (size == 1)
 276                                 return heap[0].first;
 277                         else
 278                                 return heap[0].last;
 279                 }
 280
 281
 282                 /// <summary>
 283                 /// Remove the largest item from this  priority queue.
 284                 /// <exception cref="InvalidOperationException"/> if queue is empty
 285                 /// </summary>
 286                 /// <returns>The removed item.</returns>
 287                 [Tested]
 288                 public T DeleteMax()
 289                 {
 290             stamp++;
 291             if (size == 0)
 292                 throw new InvalidOperationException("Heap is empty");
 293
 294                         T retval;
 295
 296                         if (size == 1)
 297                         {
 298                                 size = 0;
 299                                 retval = heap[0].first;
 300                                 heap[0].first = default(T);
 301                                 return retval;
 302                         }
 303                         else
 304                         {
 305                                 retval = heap[0].last;
 306
 307                                 int ind = (size - 1) / 2;
 308
 309                                 if (size % 2 == 0)
 310                                 {
 311                                         heap[0].last = heap[ind].last;
 312                                         heap[ind].last = default(T);
 313                                 }
 314                                 else
 315                                 {
 316                                         heap[0].last = heap[ind].first;
 317                                         heap[ind].first = default(T);
 318                                 }
 319
 320                                 size--;
 321                                 heapifyMax(0);
 322                                 return retval;
 323                         }
 324                 }
 325
 326
 327         /// <summary>
 328         /// The comparer object supplied at creation time for this collection
 329         /// </summary>
 330         /// <value>The comparer</value>
 331         public IComparer<T> Comparer { get { return comparer; } }
 332
 333                 #endregion
 334
 335                 #region ISink<T> Members
 336
 337                 /// <summary>
 338                 ///
 339                 /// </summary>
 340                 /// <value>True since this collection has bag semantics</value>
 341                 [Tested]
 342                 public bool AllowsDuplicates { [Tested]get { return true; } }
 343
 344
 345                 /// <summary>
 346                 ///
 347                 /// </summary>
 348                 /// <value>The distinguished object to use for locking to synchronize multithreaded access</value>
 349                 [Tested]
 350                 public object SyncRoot { [Tested]get { return syncroot; } }
 351
 352
 353                 /// <summary>
 354                 ///
 355                 /// </summary>
 356                 /// <value>True if this collection is empty.</value>
 357                 [Tested]
 358                 public bool IsEmpty { [Tested]get { return size == 0; } }
 359
 360
 361                 /// <summary>
 362                 /// Add an item to this priority queue.
 363                 /// </summary>
 364                 /// <param name="item">The item to add.</param>
 365                 /// <returns>True</returns>
 366                 [Tested]
 367                 public bool Add(T item)
 368                 {
 369             stamp++;
 370             if (size == 0)
 371                         {
 372                                 size = 1;
 373                                 heap[0].first = item;
 374                                 return true;
 375                         }
 376
 377                         if (size == 2 * heap.Length)
 378                         {
 379                                 Interval[] newheap = new Interval[2 * heap.Length];
 380
 381                                 Array.Copy(heap, newheap, heap.Length);
 382                                 heap = newheap;
 383                         }
 384
 385                         if (size % 2 == 0)
 386                         {
 387                                 int i = size / 2, p = (i + 1) / 2 - 1;
 388                                 T tmp;
 389
 390                                 size++;
 391                 if (comparer.Compare(item, tmp = heap[p].last) > 0)
 392                 {
 393                                         heap[i].first = tmp;
 394                                         heap[p].last = item;
 395                                         bubbleUpMax(p);
 396                                 }
 397                                 else
 398                                 {
 399                                         heap[i].first = item;
 400                     if (comparer.Compare(item, heap[p].first) < 0)
 401                         bubbleUpMin(i);
 402                                 }
 403                         }
 404                         else
 405                         {
 406                                 int i = size / 2;
 407                                 T other = heap[i].first;
 408
 409                                 size++;
 410                 if (comparer.Compare(item, other) < 0)
 411                 {
 412                                         heap[i].first = item;
 413                                         heap[i].last = other;
 414                                         bubbleUpMin(i);
 415                                 }
 416                                 else
 417                                 {
 418                                         heap[i].last = item;
 419                                         bubbleUpMax(i);
 420                                 }
 421                         }
 422
 423                         return true;
 424                 }
 425
 426
 427                 /// <summary>
 428                 /// Add the elements from another collection to this collection.
 429                 /// </summary>
 430                 /// <param name="items">The items to add.</param>
 431                 [Tested]
 432                 public void AddAll(MSG.IEnumerable<T> items)
 433                 {
 434             //TODO: avoid incrementing stamp repeatedly
 435                         foreach (T item in items)
 436                                 Add(item);
 437                 }
 438
 439         /// <summary>
 440         /// Add the elements from another collection with a more specialized item type
 441         /// to this collection.
 442         /// </summary>
 443         /// <typeparam name="U">The type of items to add</typeparam>
 444         /// <param name="items">The items to add</param>
 445         public void AddAll<U>(MSG.IEnumerable<U> items) where U : T
 446         {
 447             //TODO: avoid incrementing stamp repeatedly
 448             foreach (T item in items)
 449                 Add(item);
 450         }
 451
 452                 #endregion
 453
 454         #region ICollection<T> members
 455         /// <summary>
 456         ///
 457         /// </summary>
 458         /// <value>The size of this collection</value>
 459         [Tested]
 460         public override int Count { [Tested]get { return size; } }
 461
 462
 463         /// <summary>
 464         /// The value is symbolic indicating the type of asymptotic complexity
 465         /// in terms of the size of this collection (worst-case or amortized as
 466         /// relevant).
 467         /// </summary>
 468         /// <value>A characterization of the speed of the
 469         /// <code>Count</code> property in this collection.</value>
 470         public override Speed CountSpeed { get { return Speed.Constant; } }
 471
 472         /// <summary>
 473         /// Create an enumerator for the collection
 474         /// <para>Note: the enumerator does *not* enumerate the items in sorted order,
 475         /// but in the internal table order.</para>
 476         /// </summary>
 477         /// <returns>The enumerator(SIC)</returns>
 478         [Tested]
 479         public override MSG.IEnumerator<T> GetEnumerator()
 480         {
 481             int mystamp = stamp;
 482             for (int i = 0; i < size; i++)
 483             {
 484                 if (mystamp != stamp) throw new InvalidOperationException();
 485                 yield return i % 2 == 0 ? heap[i >> 1].first : heap[i >> 1].last;
 486             }
 487             yield break;
 488         }
 489
 490
 491         #endregion
 492
 493
 494                 #region Diagnostics
 495                 private bool check(int i, T min, T max)
 496                 {
 497                         bool retval = true;
 498                         Interval interval = heap[i];
 499                         T first = interval.first, last = interval.last;
 500
 501                         if (2 * i + 1 == size)
 502                         {
 503                 if (comparer.Compare(min, first) > 0)
 504                 {
 505                                         Console.WriteLine("Cell {0}: parent.first({1}) > first({2})  [size={3}]", i, min, first, size);
 506                                         retval = false;
 507                                 }
 508
 509                 if (comparer.Compare(first, max) > 0)
 510                 {
 511                                         Console.WriteLine("Cell {0}: first({1}) > parent.last({2})  [size={3}]", i, first, max, size);
 512                                         retval = false;
 513                                 }
 514
 515                                 return retval;
 516                         }
 517                         else
 518                         {
 519                 if (comparer.Compare(min, first) > 0)
 520                 {
 521                                         Console.WriteLine("Cell {0}: parent.first({1}) > first({2})  [size={3}]", i, min, first, size);
 522                                         retval = false;
 523                                 }
 524
 525                 if (comparer.Compare(first, last) > 0)
 526                 {
 527                                         Console.WriteLine("Cell {0}: first({1}) > last({2})  [size={3}]", i, first, last, size);
 528                                         retval = false;
 529                                 }
 530
 531                 if (comparer.Compare(last, max) > 0)
 532                 {
 533                                         Console.WriteLine("Cell {0}: last({1}) > parent.last({2})  [size={3}]", i, last, max, size);
 534                                         retval = false;
 535                                 }
 536
 537                                 int l = 2 * i + 1, r = l + 1;
 538
 539                                 if (2 * l < size)
 540                                         retval = retval && check(l, first, last);
 541
 542                                 if (2 * r < size)
 543                                         retval = retval && check(r, first, last);
 544                         }
 545
 546                         return retval;
 547                 }
 548
 549
 550                 /// <summary>
 551                 /// Check the integrity of the internal data structures of this collection.
 552                 /// Only avaliable in DEBUG builds???
 553                 /// </summary>
 554                 /// <returns>True if check does not fail.</returns>
 555                 [Tested]
 556                 public bool Check()
 557                 {
 558                         if (size == 0)
 559                                 return true;
 560
 561                         if (size == 1)
 562                                 return (object)(heap[0].first) != null;
 563
 564                         return check(0, heap[0].first, heap[0].last);
 565                 }
 566
 567                 #endregion
 568         }
 569 }
 570 #endif