Dogcows Code - chaz/carfire/blob - CarFire/CarFire/CarFire/PriorityQueue.cs

   1 using System;
   2 using System.Collections.Generic;
   3 using System.Linq;
   4 using System.Text;
   5 using System.Diagnostics;
   6
   7 namespace CarFire
   8 {
   9     /// <summary>
  10     /// Why .NET doesn't already provide such a basic data structure
  11     /// as a priority queue is anybody's best guess.  This is an interface
  12     /// for a queue class which treats the items themselves as keys,
  13     /// the relative priorities being determined by a comparison between
  14     /// them.
  15     /// </summary>
  16     /// <typeparam name="T">The type of item to queue.  This must be a
  17     /// comparable class.</typeparam>
  18     public interface IPriorityQueue<T> where T : IComparable<T>
  19     {
  20         /// <summary>
  21         /// Add a new item to the priority queue.
  22         /// </summary>
  23         /// <param name="item">The item to add.</param>
  24         void Add(T item);
  25
  26         /// <summary>
  27         /// Get the item with the highest priority, removing it
  28         /// from the priority queue.
  29         /// </summary>
  30         /// <returns>The highest priority item.</returns>
  31         T GetNext();
  32
  33         /// <summary>
  34         /// Get the item with the highest priority, but keep it in
  35         /// the priority queue.
  36         /// </summary>
  37         /// <returns>The highest priority item.</returns>
  38         T Peek();
  39
  40         /// <summary>
  41         /// Notify the priority queue that the priority of a certain item
  42         /// has improved.  If the items is not in the queue, it is added.
  43         /// Do not use this to demote items.  The internal structures will
  44         /// be reconfigured in order to ensure correct priority queueing.
  45         /// </summary>
  46         /// <param name="item">The item that improved.</param>
  47         void Promote(T item);
  48
  49         /// <summary>
  50         /// Remove all the items from the priority queue.
  51         /// </summary>
  52         void Clear();
  53
  54         /// <summary>
  55         /// Get the number of items in the priority queue.
  56         /// </summary>
  57         int Count { get; }
  58     }
  59
  60
  61     /// <summary>
  62     /// A minimum binary heap implementing a priority queue.
  63     /// </summary>
  64     /// <typeparam name="T">The type of items to load in the heap.</typeparam>
  65     public class BinaryHeap<T> : IPriorityQueue<T> where T : IComparable<T>
  66     {
  67         #region Public Properties
  68
  69         /// <summary>
  70         /// Get the number of items in the binary heap.
  71         /// </summary>
  72         public int Count { get { return mSize; } }
  73
  74         #endregion
  75
  76
  77         #region Public Methods
  78
  79         /// <summary>
  80         /// Construct a binary heap.
  81         /// </summary>
  82         public BinaryHeap()
  83         {
  84             mList.Add(default(T));
  85         }
  86
  87         /// <summary>
  88         /// Construct a binary heap with a predetermined capacity.
  89         /// The heap is dynamically-sized, but it will be more
  90         /// efficient if you set the capacity to the number of items
  91         /// you plan to add.
  92         /// </summary>
  93         /// <param name="capacity">The capacity of the heap.</param>
  94         public BinaryHeap(int capacity)
  95         {
  96             mList.Capacity = capacity;
  97             mList.Add(default(T));
  98         }
  99
 100
 101         /// <summary>
 102         /// Add a new item to the heap.
 103         /// </summary>
 104         /// <param name="item">The item to add.</param>
 105         public void Add(T item)
 106         {
 107             mList.Add(item);
 108             mSize++;
 109             PercolateUp(mSize);
 110         }
 111
 112
 113         /// <summary>
 114         /// Get the item with the lowest value, removing it from the heap.
 115         /// </summary>
 116         /// <returns>The highest priority item.</returns>
 117         public T GetNext()
 118         {
 119             Debug.Assert(mSize > 0);
 120
 121             T next = mList[1];
 122
 123             mList[1] = mList[mSize];
 124             PercolateDown(1);
 125             mList.RemoveAt(mSize);
 126             mSize--;
 127
 128             return next;
 129         }
 130
 131         /// <summary>
 132         /// Get the item with the lowest value, but keep it in the heap.
 133         /// </summary>
 134         /// <returns>The highest priority item.</returns>
 135         public T Peek()
 136         {
 137             Debug.Assert(mSize > 0);
 138
 139             return mList[1];
 140         }
 141
 142
 143         /// <summary>
 144         /// Decrease the value of one of the items in the heap.  If the
 145         /// item is not already in the heap, it is added.
 146         /// </summary>
 147         /// <param name="item">The item to change.</param>
 148         public void Promote(T item)
 149         {
 150             for (int i = 1; i < mList.Count; i++)
 151             {
 152                 if (item.Equals(mList[i]))
 153                 {
 154                     mList[i] = item;
 155                     if (PercolateUp(i) == i) PercolateDown(i);
 156                     return;
 157                 }
 158             }
 159
 160             Add(item);
 161         }
 162
 163
 164         /// <summary>
 165         /// Remove all the items from the heap.
 166         /// </summary>
 167         public void Clear()
 168         {
 169             mList.Clear();
 170             mSize = 0;
 171         }
 172
 173         #endregion
 174
 175
 176         #region Private Methods
 177
 178         int PercolateUp(int index)
 179         {
 180             T temp = mList[index];
 181
 182             for (int parent; index > 1; index = parent)
 183             {
 184                 parent = index / 2;
 185                 if (temp.CompareTo(mList[parent]) < 0) mList[index] = mList[parent];
 186                 else break;
 187             }
 188
 189             mList[index] = temp;
 190             return index;
 191         }
 192
 193         int PercolateDown(int index)
 194         {
 195             T temp = mList[index];
 196
 197             for (int child; index * 2 <= mSize; index = child)
 198             {
 199                 child = index * 2;
 200                 if (child != mSize && mList[child].CompareTo(mList[child + 1]) > 0) child++;
 201                 if (temp.CompareTo(mList[child]) > 0) mList[index] = mList[child];
 202                 else break;
 203             }
 204
 205             mList[index] = temp;
 206             return index;
 207         }
 208
 209         #endregion
 210
 211
 212         #region Private Variables
 213
 214         List<T> mList = new List<T>();
 215         int mSize = 0;
 216
 217         #endregion
 218     }
 219
 220
 221     /// <summary>
 222     /// The binary heap might be too slow for shortest path algorithms,
 223     /// so here is a fibonacci heap which should perform better.
 224     /// </summary>
 225     /// <typeparam name="T">The type of items to load in the heap.</typeparam>
 226     public class FibonacciHeap<T> : IPriorityQueue<T> where T : IComparable<T>
 227     {
 228         #region Public Properties
 229
 230         /// <summary>
 231         /// Get the number of items in the fibonacci heap.
 232         /// </summary>
 233         public int Count { get { return mCount; } }
 234
 235         #endregion
 236
 237
 238         #region Public Methods
 239
 240         /// <summary>
 241         /// Construct an empty fibonacci heap.
 242         /// </summary>
 243         public FibonacciHeap()
 244         {
 245             mList = new LinkedList<NodeInfo>();
 246             mLookup = new Dictionary<T, LinkedListNode<NodeInfo>>();
 247         }
 248
 249
 250         /// <summary>
 251         /// Add a new item to the heap.
 252         /// </summary>
 253         /// <param name="item">The item to add.</param>
 254         public void Add(T item)
 255         {
 256             LinkedListNode<NodeInfo> node = mList.AddLast(new NodeInfo(item));
 257             if (mMin == null || item.CompareTo(mMin.Value.Item) < 0) mMin = node;
 258
 259             mLookup[item] = node;
 260             mCount++;
 261         }
 262
 263
 264         /// <summary>
 265         /// Get the item with the lowest value, removing it from the heap.
 266         /// </summary>
 267         /// <returns>The highest priority item.</returns>
 268         public T GetNext()
 269         {
 270             LinkedListNode<NodeInfo> temp = mMin;
 271             mList.Remove(mMin);
 272             mMin = null;
 273
 274             LinkedListNode<NodeInfo> node = temp.Value.Children.First;
 275             while (node != null)
 276             {
 277                 Cut(node);
 278                 node = temp.Value.Children.First;
 279             }
 280             Consolidate();
 281
 282             mLookup.Remove(temp.Value.Item);
 283             mCount--;
 284             return temp.Value.Item;
 285         }
 286
 287         /// <summary>
 288         /// Get the item with the lowest value, but keep it in the heap.
 289         /// </summary>
 290         /// <returns>The highest priority item.</returns>
 291         public T Peek()
 292         {
 293             return mMin.Value.Item;
 294         }
 295
 296
 297         /// <summary>
 298         /// Decrease the value of one of the items in the heap.  If the
 299         /// item is not already in the heap, it is added.
 300         /// </summary>
 301         /// <param name="item">The item to change.</param>
 302         public void Promote(T item)
 303         {
 304             LinkedListNode<NodeInfo> node;
 305             if (mLookup.TryGetValue(item, out node))
 306             {
 307                 LinkedListNode<NodeInfo> parent = node.Value.Parent;
 308                 if (parent != null)
 309                 {
 310                     if (node.Value.Item.CompareTo(parent.Value.Item) < 0)
 311                     {
 312                         Cut(node);
 313                         CascadingCut(parent);
 314                         if (node.Value.Item.CompareTo(mMin.Value.Item) < 0) mMin = node;
 315                     }
 316                 }
 317                 else if (node.Value.Item.CompareTo(mMin.Value.Item) < 0) mMin = node;
 318             }
 319             else
 320             {
 321                 Add(item);
 322             }
 323         }
 324
 325
 326         /// <summary>
 327         /// Remove all the items from the heap.
 328         /// </summary>
 329         public void Clear()
 330         {
 331             mList.Clear();
 332             mMin = null;
 333             mCount = 0;
 334             mLookup.Clear();
 335         }
 336
 337         #endregion
 338
 339
 340         #region Private Methods
 341
 342         // Builds up the binomial trees.  More importantly, it sets the min
 343         // pointeer and ensures that no root binomial tree has the same degree.
 344         void Consolidate()
 345         {
 346             LinkedListNode<NodeInfo>[] degree = new LinkedListNode<NodeInfo>[64];
 347
 348             for (LinkedListNode<NodeInfo> node = mList.First; node != null;)
 349             {
 350                 LinkedListNode<NodeInfo> match = degree[node.Value.Degree];
 351                 if (match == null)
 352                 {
 353                     if (mMin == null || node.Value.Item.CompareTo(mMin.Value.Item) <= 0) mMin = node;
 354                     degree[node.Value.Degree] = node;
 355
 356                     node = node.Next;
 357                 }
 358                 else
 359                 {
 360                     degree[node.Value.Degree] = null;
 361
 362                     if (node.Value.Item.CompareTo(match.Value.Item) < 0)
 363                     {
 364                         Link(match, node);
 365                     }
 366                     else
 367                     {
 368                         mList.Remove(match);
 369                         mList.AddAfter(node, match);
 370                         Link(node, match);
 371                         node = match;
 372                     }
 373                 }
 374             }
 375         }
 376
 377         // Removes child from whatever list it is in and makes it a child
 378         // of parent.  This is for building up the binomial trees.
 379         void Link(LinkedListNode<NodeInfo> child, LinkedListNode<NodeInfo> parent)
 380         {
 381             child.List.Remove(child);
 382             parent.Value.Children.AddLast(child);
 383             child.Value.Parent = parent;
 384             child.Value.IsMarked = false;
 385         }
 386
 387         // Removes node from whatever list it is in and makes it a root binomial
 388         // tree.
 389         void Cut(LinkedListNode<NodeInfo> node)
 390         {
 391             node.List.Remove(node);
 392             mList.AddLast(node);
 393             node.Value.Parent = null;
 394             node.Value.IsMarked = false;
 395         }
 396
 397         // Cuts each node that is marked, following the ancestry until it finds
 398         // an unmarked ancestor (in which case it marks it) or a root node.
 399         void CascadingCut(LinkedListNode<NodeInfo> node)
 400         {
 401             while (node.Value.Parent != null)
 402             {
 403                 if (node.Value.IsMarked)
 404                 {
 405                     Cut(node);
 406                     node = node.Value.Parent;
 407                 }
 408                 else
 409                 {
 410                     node.Value.IsMarked = true;
 411                     break;
 412                 }
 413             }
 414         }
 415
 416         #endregion
 417
 418
 419         #region Private Types
 420
 421         // This container class has the information we need to form
 422         // a tree out of linked lists.
 423         class NodeInfo
 424         {
 425             public LinkedListNode<NodeInfo> Parent;
 426             public LinkedList<NodeInfo> Children = new LinkedList<NodeInfo>();
 427             public bool IsMarked = false;
 428
 429             public int Degree { get { return Children.Count; } }
 430
 431             public T Item { get { return mItem; } }
 432
 433             public NodeInfo(T item)
 434             {
 435                 mItem = item;
 436             }
 437
 438             T mItem;
 439         }
 440
 441         #endregion
 442
 443
 444         #region Private Variables
 445
 446         LinkedList<NodeInfo> mList;
 447         LinkedListNode<NodeInfo> mMin;
 448         int mCount;
 449
 450         // To speed up promotions, we need a fast lookup for nodes.
 451         Dictionary<T, LinkedListNode<NodeInfo>> mLookup;
 452
 453         #endregion
 454     }
 455 }