mcs/class/Mono.C5/heaps/IntervalHeap.cs

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