--- /dev/null
+using System;\r
+using System.Collections.Generic;\r
+using System.Linq;\r
+using System.Text;\r
+using System.Diagnostics;\r
+\r
+namespace CarFire\r
+{\r
+ /// <summary>\r
+ /// Why .NET doesn't already provide such a basic data structure\r
+ /// as a priority queue is anybody's best guess. This is an interface\r
+ /// for a queue class which treats the items themselves as keys,\r
+ /// the relative priorities being determined by a comparison between\r
+ /// them.\r
+ /// </summary>\r
+ /// <typeparam name="T">The type of item to queue. This must be a\r
+ /// comparable class.</typeparam>\r
+ public interface IPriorityQueue<T> where T : IComparable<T>\r
+ {\r
+ /// <summary>\r
+ /// Add a new item to the priority queue.\r
+ /// </summary>\r
+ /// <param name="item">The item to add.</param>\r
+ void Add(T item);\r
+\r
+ /// <summary>\r
+ /// Get the item with the highest priority, removing it\r
+ /// from the priority queue.\r
+ /// </summary>\r
+ /// <returns>The highest priority item.</returns>\r
+ T GetNext();\r
+\r
+ /// <summary>\r
+ /// Get the item with the highest priority, but keep it in\r
+ /// the priority queue.\r
+ /// </summary>\r
+ /// <returns>The highest priority item.</returns>\r
+ T Peek();\r
+\r
+ /// <summary>\r
+ /// Notify the priority queue that the priority of a certain item\r
+ /// has improved. If the items is not in the queue, it is added.\r
+ /// Do not use this to demote items. The internal structures will\r
+ /// be reconfigured in order to ensure correct priority queueing.\r
+ /// </summary>\r
+ /// <param name="item">The item that improved.</param>\r
+ void Promote(T item);\r
+\r
+ /// <summary>\r
+ /// Remove all the items from the priority queue.\r
+ /// </summary>\r
+ void Clear();\r
+\r
+ /// <summary>\r
+ /// Get the number of items in the priority queue.\r
+ /// </summary>\r
+ int Count { get; }\r
+ }\r
+\r
+\r
+ /// <summary>\r
+ /// A minimum binary heap implementing a priority queue.\r
+ /// </summary>\r
+ /// <typeparam name="T">The type of items to load in the heap.</typeparam>\r
+ public class BinaryHeap<T> : IPriorityQueue<T> where T : IComparable<T>\r
+ {\r
+ #region Public Properties\r
+\r
+ /// <summary>\r
+ /// Get the number of items in the binary heap.\r
+ /// </summary>\r
+ public int Count { get { return mSize; } }\r
+\r
+ #endregion\r
+\r
+\r
+ #region Public Methods\r
+\r
+ /// <summary>\r
+ /// Construct a binary heap.\r
+ /// </summary>\r
+ public BinaryHeap()\r
+ {\r
+ mList.Add(default(T));\r
+ }\r
+\r
+ /// <summary>\r
+ /// Construct a binary heap with a predetermined capacity.\r
+ /// The heap is dynamically-sized, but it will be more\r
+ /// efficient if you set the capacity to the number of items\r
+ /// you plan to add.\r
+ /// </summary>\r
+ /// <param name="capacity">The capacity of the heap.</param>\r
+ public BinaryHeap(int capacity)\r
+ {\r
+ mList.Capacity = capacity;\r
+ mList.Add(default(T));\r
+ }\r
+\r
+\r
+ /// <summary>\r
+ /// Add a new item to the heap.\r
+ /// </summary>\r
+ /// <param name="item">The item to add.</param>\r
+ public void Add(T item)\r
+ {\r
+ mList.Add(item);\r
+ mSize++;\r
+ PercolateUp(mSize);\r
+ }\r
+\r
+\r
+ /// <summary>\r
+ /// Get the item with the lowest value, removing it from the heap.\r
+ /// </summary>\r
+ /// <returns>The highest priority item.</returns>\r
+ public T GetNext()\r
+ {\r
+ Debug.Assert(mSize > 0);\r
+\r
+ T next = mList[1];\r
+\r
+ mList[1] = mList[mSize];\r
+ PercolateDown(1);\r
+ mList.RemoveAt(mSize);\r
+ mSize--;\r
+\r
+ return next;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Get the item with the lowest value, but keep it in the heap.\r
+ /// </summary>\r
+ /// <returns>The highest priority item.</returns>\r
+ public T Peek()\r
+ {\r
+ Debug.Assert(mSize > 0);\r
+\r
+ return mList[1];\r
+ }\r
+\r
+\r
+ /// <summary>\r
+ /// Decrease the value of one of the items in the heap. If the\r
+ /// item is not already in the heap, it is added.\r
+ /// </summary>\r
+ /// <param name="item">The item to change.</param>\r
+ public void Promote(T item)\r
+ {\r
+ for (int i = 1; i < mList.Count; i++)\r
+ {\r
+ if (item.Equals(mList[i]))\r
+ {\r
+ mList[i] = item;\r
+ if (PercolateUp(i) == i) PercolateDown(i);\r
+ return;\r
+ }\r
+ }\r
+\r
+ Add(item);\r
+ }\r
+\r
+\r
+ /// <summary>\r
+ /// Remove all the items from the heap.\r
+ /// </summary>\r
+ public void Clear()\r
+ {\r
+ mList.Clear();\r
+ mSize = 0;\r
+ }\r
+\r
+ #endregion\r
+\r
+\r
+ #region Private Methods\r
+\r
+ int PercolateUp(int index)\r
+ {\r
+ T temp = mList[index];\r
+\r
+ for (int parent; index > 1; index = parent)\r
+ {\r
+ parent = index / 2;\r
+ if (temp.CompareTo(mList[parent]) < 0) mList[index] = mList[parent];\r
+ else break;\r
+ }\r
+\r
+ mList[index] = temp;\r
+ return index;\r
+ }\r
+\r
+ int PercolateDown(int index)\r
+ {\r
+ T temp = mList[index];\r
+\r
+ for (int child; index * 2 <= mSize; index = child)\r
+ {\r
+ child = index * 2;\r
+ if (child != mSize && mList[child].CompareTo(mList[child + 1]) > 0) child++;\r
+ if (temp.CompareTo(mList[child]) > 0) mList[index] = mList[child];\r
+ else break;\r
+ }\r
+\r
+ mList[index] = temp;\r
+ return index;\r
+ }\r
+\r
+ #endregion\r
+\r
+\r
+ #region Private Variables\r
+\r
+ List<T> mList = new List<T>();\r
+ int mSize = 0;\r
+\r
+ #endregion\r
+ }\r
+\r
+\r
+ /// <summary>\r
+ /// The binary heap might be too slow for shortest path algorithms,\r
+ /// so here is a fibonacci heap which should perform better.\r
+ /// </summary>\r
+ /// <typeparam name="T">The type of items to load in the heap.</typeparam>\r
+ public class FibonacciHeap<T> : IPriorityQueue<T> where T : IComparable<T>\r
+ {\r
+ #region Public Properties\r
+\r
+ /// <summary>\r
+ /// Get the number of items in the fibonacci heap.\r
+ /// </summary>\r
+ public int Count { get { return mCount; } }\r
+\r
+ #endregion\r
+\r
+\r
+ #region Public Methods\r
+\r
+ /// <summary>\r
+ /// Construct an empty fibonacci heap.\r
+ /// </summary>\r
+ public FibonacciHeap()\r
+ {\r
+ mList = new LinkedList<NodeInfo>();\r
+ mLookup = new Dictionary<T, LinkedListNode<NodeInfo>>();\r
+ }\r
+\r
+\r
+ /// <summary>\r
+ /// Add a new item to the heap.\r
+ /// </summary>\r
+ /// <param name="item">The item to add.</param>\r
+ public void Add(T item)\r
+ {\r
+ LinkedListNode<NodeInfo> node = mList.AddLast(new NodeInfo(item));\r
+ if (mMin == null || item.CompareTo(mMin.Value.Item) < 0) mMin = node;\r
+\r
+ mLookup[item] = node;\r
+ mCount++;\r
+ }\r
+\r
+\r
+ /// <summary>\r
+ /// Get the item with the lowest value, removing it from the heap.\r
+ /// </summary>\r
+ /// <returns>The highest priority item.</returns>\r
+ public T GetNext()\r
+ {\r
+ LinkedListNode<NodeInfo> temp = mMin;\r
+ mList.Remove(mMin);\r
+ mMin = null;\r
+\r
+ LinkedListNode<NodeInfo> node = temp.Value.Children.First;\r
+ while (node != null)\r
+ {\r
+ Cut(node);\r
+ node = temp.Value.Children.First;\r
+ }\r
+ Consolidate();\r
+\r
+ mLookup.Remove(temp.Value.Item);\r
+ mCount--;\r
+ return temp.Value.Item;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Get the item with the lowest value, but keep it in the heap.\r
+ /// </summary>\r
+ /// <returns>The highest priority item.</returns>\r
+ public T Peek()\r
+ {\r
+ return mMin.Value.Item;\r
+ }\r
+\r
+\r
+ /// <summary>\r
+ /// Decrease the value of one of the items in the heap. If the\r
+ /// item is not already in the heap, it is added.\r
+ /// </summary>\r
+ /// <param name="item">The item to change.</param>\r
+ public void Promote(T item)\r
+ {\r
+ LinkedListNode<NodeInfo> node;\r
+ if (mLookup.TryGetValue(item, out node))\r
+ {\r
+ LinkedListNode<NodeInfo> parent = node.Value.Parent;\r
+ if (parent != null)\r
+ {\r
+ if (node.Value.Item.CompareTo(parent.Value.Item) < 0)\r
+ {\r
+ Cut(node);\r
+ CascadingCut(parent);\r
+ if (node.Value.Item.CompareTo(mMin.Value.Item) < 0) mMin = node;\r
+ }\r
+ }\r
+ else if (node.Value.Item.CompareTo(mMin.Value.Item) < 0) mMin = node;\r
+ }\r
+ else\r
+ {\r
+ Add(item);\r
+ }\r
+ }\r
+\r
+\r
+ /// <summary>\r
+ /// Remove all the items from the heap.\r
+ /// </summary>\r
+ public void Clear()\r
+ {\r
+ mList.Clear();\r
+ mMin = null;\r
+ mCount = 0;\r
+ mLookup.Clear();\r
+ }\r
+\r
+ #endregion\r
+\r
+\r
+ #region Private Methods\r
+\r
+ // Builds up the binomial trees. More importantly, it sets the min\r
+ // pointeer and ensures that no root binomial tree has the same degree.\r
+ void Consolidate()\r
+ {\r
+ LinkedListNode<NodeInfo>[] degree = new LinkedListNode<NodeInfo>[64];\r
+\r
+ for (LinkedListNode<NodeInfo> node = mList.First; node != null;)\r
+ {\r
+ LinkedListNode<NodeInfo> match = degree[node.Value.Degree];\r
+ if (match == null)\r
+ {\r
+ if (mMin == null || node.Value.Item.CompareTo(mMin.Value.Item) <= 0) mMin = node;\r
+ degree[node.Value.Degree] = node;\r
+ \r
+ node = node.Next;\r
+ }\r
+ else\r
+ {\r
+ degree[node.Value.Degree] = null;\r
+\r
+ if (node.Value.Item.CompareTo(match.Value.Item) < 0)\r
+ {\r
+ Link(match, node);\r
+ }\r
+ else\r
+ {\r
+ mList.Remove(match);\r
+ mList.AddAfter(node, match);\r
+ Link(node, match);\r
+ node = match;\r
+ }\r
+ }\r
+ }\r
+ }\r
+\r
+ // Removes child from whatever list it is in and makes it a child\r
+ // of parent. This is for building up the binomial trees.\r
+ void Link(LinkedListNode<NodeInfo> child, LinkedListNode<NodeInfo> parent)\r
+ {\r
+ child.List.Remove(child);\r
+ parent.Value.Children.AddLast(child);\r
+ child.Value.Parent = parent;\r
+ child.Value.IsMarked = false;\r
+ }\r
+\r
+ // Removes node from whatever list it is in and makes it a root binomial\r
+ // tree.\r
+ void Cut(LinkedListNode<NodeInfo> node)\r
+ {\r
+ node.List.Remove(node);\r
+ mList.AddLast(node);\r
+ node.Value.Parent = null;\r
+ node.Value.IsMarked = false;\r
+ }\r
+\r
+ // Cuts each node that is marked, following the ancestry until it finds\r
+ // an unmarked ancestor (in which case it marks it) or a root node.\r
+ void CascadingCut(LinkedListNode<NodeInfo> node)\r
+ {\r
+ while (node.Value.Parent != null)\r
+ {\r
+ if (node.Value.IsMarked)\r
+ {\r
+ Cut(node);\r
+ node = node.Value.Parent;\r
+ }\r
+ else\r
+ {\r
+ node.Value.IsMarked = true;\r
+ break;\r
+ }\r
+ }\r
+ }\r
+\r
+ #endregion\r
+\r
+\r
+ #region Private Types\r
+\r
+ // This container class has the information we need to form\r
+ // a tree out of linked lists.\r
+ class NodeInfo\r
+ {\r
+ public LinkedListNode<NodeInfo> Parent;\r
+ public LinkedList<NodeInfo> Children = new LinkedList<NodeInfo>();\r
+ public bool IsMarked = false;\r
+\r
+ public int Degree { get { return Children.Count; } }\r
+\r
+ public T Item { get { return mItem; } }\r
+\r
+ public NodeInfo(T item)\r
+ {\r
+ mItem = item;\r
+ }\r
+\r
+ T mItem;\r
+ }\r
+\r
+ #endregion\r
+\r
+\r
+ #region Private Variables\r
+\r
+ LinkedList<NodeInfo> mList;\r
+ LinkedListNode<NodeInfo> mMin;\r
+ int mCount;\r
+\r
+ // To speed up promotions, we need a fast lookup for nodes.\r
+ Dictionary<T, LinkedListNode<NodeInfo>> mLookup;\r
+\r
+ #endregion\r
+ }\r
+}\r
projects / chaz / carfire / blobdiff