1 files changed, 400 insertions, 0 deletions
diff --git a/labb8/lib/StanfordCPPLib/pqueue.h b/labb8/lib/StanfordCPPLib/pqueue.h
new file mode 100755
index 0000000..1946797
--- /dev/null
+++ b/labb8/lib/StanfordCPPLib/pqueue.h
@@ -0,0 +1,400 @@
+/*
+ * File: pqueue.h
+ * --------------
+ * This file exports the <code>PriorityQueue</code> class, a
+ * collection in which values are processed in priority order.
+ */
+
+#ifndef _pqueue_h
+#define _pqueue_h
+
+#include "vector.h"
+
+/*
+ * Class: PriorityQueue<ValueType>
+ * -------------------------------
+ * This class models a structure called a <b><i>priority&nbsp;queue</i></b>
+ * in which values are processed in order of priority.  As in conventional
+ * English usage, lower priority numbers correspond to higher effective
+ * priorities, so that a priority 1 item takes precedence over a
+ * priority 2 item.
+ */
+
+template <typename ValueType>
+class PriorityQueue {
+
+public:
+
+/*
+ * Constructor: PriorityQueue
+ * Usage: PriorityQueue<ValueType> pq;
+ * -----------------------------------
+ * Initializes a new priority queue, which is initially empty.
+ */
+
+   PriorityQueue();
+
+/*
+ * Destructor: ~PriorityQueue
+ * --------------------------
+ * Frees any heap storage associated with this priority queue.
+ */
+
+   virtual ~PriorityQueue();
+
+/*
+ * Method: size
+ * Usage: int n = pq.size();
+ * -------------------------
+ * Returns the number of values in the priority queue.
+ */
+
+   int size() const;
+
+/*
+ * Method: isEmpty
+ * Usage: if (pq.isEmpty()) ...
+ * ----------------------------
+ * Returns <code>true</code> if the priority queue contains no elements.
+ */
+
+   bool isEmpty() const;
+
+/*
+ * Method: clear
+ * Usage: pq.clear();
+ * ------------------
+ * Removes all elements from the priority queue.
+ */
+
+   void clear();
+
+/*
+ * Method: enqueue
+ * Usage: pq.enqueue(value, priority);
+ * -----------------------------------
+ * Adds <code>value</code> to the queue with the specified priority.
+ * Lower priority numbers correspond to higher priorities, which
+ * means that all priority 1 elements are dequeued before any
+ * priority 2 elements.
+ */
+
+   void enqueue(ValueType value, double priority);
+
+/*
+ * Method: changePriority
+ * Usage: pq.changePriority(value, newPriority);
+ * -----------------------------------
+ * Adjusts <code>value</code> in the queue to now have the specified new priority,
+ * which must be at least as urgent (lower number) than that value's previous
+ * priority in the queue.
+ * Throws an error if the element value is not present in the queue, or if the
+ * new priority passed is not at least as urgent as its current priority.
+ */
+
+void changePriority(ValueType value, double newPriority);
+
+/*
+ * Method: dequeue
+ * Usage: ValueType first = pq.dequeue();
+ * --------------------------------------
+ * Removes and returns the highest priority value.  If multiple
+ * entries in the queue have the same priority, those values are
+ * dequeued in the same order in which they were enqueued.
+ */
+
+   ValueType dequeue();
+
+/*
+ * Method: peek
+ * Usage: ValueType first = pq.peek();
+ * -----------------------------------
+ * Returns the value of highest priority in the queue, without
+ * removing it.
+ */
+
+   ValueType peek() const;
+
+/*
+ * Method: peekPriority
+ * Usage: double priority = pq.peekPriority();
+ * -------------------------------------------
+ * Returns the priority of the first element in the queue, without
+ * removing it.
+ */
+
+   double peekPriority() const;
+
+/*
+ * Method: front
+ * Usage: ValueType first = pq.front();
+ * ------------------------------------
+ * Returns the first value in the queue by reference.
+ */
+
+   ValueType & front();
+
+/*
+ * Method: back
+ * Usage: ValueType last = pq.back();
+ * ----------------------------------
+ * Returns the last value in the queue by reference.
+ */
+
+   ValueType & back();
+
+/*
+ * Method: toString
+ * Usage: string str = pq.toString();
+ * ----------------------------------
+ * Converts the queue to a printable string representation.
+ */
+
+   std::string toString();
+
+/* Private section */
+
+/**********************************************************************/
+/* Note: Everything below this point in the file is logically part    */
+/* of the implementation and should not be of interest to clients.    */
+/**********************************************************************/
+
+/*
+ * Implementation notes: PriorityQueue data structure
+ * --------------------------------------------------
+ * The PriorityQueue class is implemented using a data structure called
+ * a heap.
+ */
+
+private:
+
+/* Type used for each heap entry */
+
+   struct HeapEntry {
+      ValueType value;
+      double priority;
+      long sequence;
+   };
+
+/* Instance variables */
+
+   Vector<HeapEntry> heap;
+   long enqueueCount;
+   int backIndex;
+   int count;
+   int capacity;
+
+/* Private function prototypes */
+
+   void enqueueHeap(ValueType & value, double priority);
+   ValueType dequeueHeap();
+   bool takesPriority(int i1, int i2);
+   void swapHeapEntries(int i1, int i2);
+
+};
+
+extern void error(std::string msg);
+
+template <typename ValueType>
+PriorityQueue<ValueType>::PriorityQueue() {
+   clear();
+}
+
+/*
+ * Implementation notes: ~PriorityQueue destructor
+ * -----------------------------------------------
+ * All of the dynamic memory is allocated in the Vector class,
+ * so no work is required at this level.
+ */
+
+template <typename ValueType>
+PriorityQueue<ValueType>::~PriorityQueue() {
+   /* Empty */
+}
+
+template <typename ValueType>
+int PriorityQueue<ValueType>::size() const {
+   return count;
+}
+
+template <typename ValueType>
+bool PriorityQueue<ValueType>::isEmpty() const {
+   return count == 0;
+}
+
+template <typename ValueType>
+void PriorityQueue<ValueType>::clear() {
+   heap.clear();
+   count = 0;
+}
+
+template <typename ValueType>
+void PriorityQueue<ValueType>::enqueue(ValueType value, double priority) {
+   if (count == heap.size()) heap.add(HeapEntry());
+   int index = count++;
+   heap[index].value = value;
+   heap[index].priority = priority;
+   heap[index].sequence = enqueueCount++;
+   if (index == 0 || takesPriority(backIndex, index)) backIndex = index;
+   while (index > 0) {
+      int parent = (index - 1) / 2;
+      if (takesPriority(parent, index)) break;
+      swapHeapEntries(parent, index);
+      index = parent;
+   }
+}
+
+template <typename ValueType>
+void PriorityQueue<ValueType>::changePriority(ValueType value, double newPriority) {
+    // parts of this implementation are adapted from TrailblazerPQueue.h,
+    // which was written by Keith Schwarz
+
+    if (!(newPriority == newPriority)) {
+        error("PriorityQueue::changePriority(" + genericValueToString(value) + ", "
+              + realToString(newPriority) + "): Attempted to use NaN as a priority.");
+    }
+
+    // find the element in the pqueue; must use a simple iteration over elements
+    for (int i = 0; i < count; i++) {
+        if (heap[i].value == value) {
+            if (heap[i].priority < newPriority) {
+                error("PriorityQueue::changePriority(" + genericValueToString(value) + ", "
+                      + realToString(newPriority)
+                      + "): new priority cannot be less urgent than current priority of "
+                      + realToString(heap[i].priority) + ".");
+            }
+            heap[i].priority = newPriority;
+
+            // after changing the priority, must percolate up to proper level
+            // to maintain heap ordering
+            while (i > 0) {
+                int parent = (i - 1) / 2;
+                if (takesPriority(parent, i)) break;
+                swapHeapEntries(parent, i);
+                i = parent;
+            }
+
+            return;
+        }
+    }
+
+    // if we get here, the element was not ever found
+    error("PriorityQueue::changePriority(" + genericValueToString(value) + ", "
+          + realToString(newPriority) + "): Element value not found.");
+}
+
+/*
+ * Implementation notes: dequeue, peek, peekPriority
+ * -------------------------------------------------
+ * These methods must check for an empty queue and report an error
+ * if there is no first element.
+ */
+
+template <typename ValueType>
+ValueType PriorityQueue<ValueType>::dequeue() {
+   if (count == 0) error("dequeue: Attempting to dequeue an empty queue");
+   count--;
+   bool wasBack = (backIndex == count);
+   ValueType value = heap[0].value;
+   swapHeapEntries(0, count);
+   int index = 0;
+   while (true) {
+      int left = 2 * index + 1;
+      int right = 2 * index + 2;
+      if (left >= count) break;
+      int child = left;
+      if (right < count && takesPriority(right, left)) child = right;
+      if (takesPriority(index, child)) break;
+      swapHeapEntries(index, child);
+      index = child;
+   }
+   if (wasBack) backIndex = index;
+   return value;
+}
+
+template <typename ValueType>
+ValueType PriorityQueue<ValueType>::peek() const {
+   if (count == 0) error("peek: Attempting to peek at an empty queue");
+   return heap.get(0).value;
+}
+
+template <typename ValueType>
+double PriorityQueue<ValueType>::peekPriority() const {
+   if (count == 0) error("peekPriority: Attempting to peek at an empty queue");
+   return heap.get(0).priority;
+}
+
+template <typename ValueType>
+ValueType & PriorityQueue<ValueType>::front() {
+   if (count == 0) error("front: Attempting to read front of an empty queue");
+   return heap.get(0).value;
+}
+
+template <typename ValueType>
+ValueType & PriorityQueue<ValueType>::back() {
+   if (count == 0) error("back: Attempting to read back of an empty queue");
+   return heap.get(backIndex).value;
+}
+
+template <typename ValueType>
+bool PriorityQueue<ValueType>::takesPriority(int i1, int i2) {
+   if (heap[i1].priority < heap[i2].priority) return true;
+   if (heap[i1].priority > heap[i2].priority) return false;
+   return (heap[i1].sequence < heap[i2].sequence);
+}
+
+template <typename ValueType>
+void PriorityQueue<ValueType>::swapHeapEntries(int i1, int i2) {
+   HeapEntry entry = heap[i1];
+   heap[i1] = heap[i2];
+   heap[i2] = entry;
+}
+
+template <typename ValueType>
+std::string PriorityQueue<ValueType>::toString() {
+   ostringstream os;
+   os << *this;
+   return os.str();
+}
+
+template <typename ValueType>
+std::ostream & operator<<(std::ostream & os,
+                          const PriorityQueue<ValueType> & pq) {
+   os << "{";
+   PriorityQueue<ValueType> copy = pq;
+   int len = pq.size();
+   for (int i = 0; i < len; i++) {
+      if (i > 0) os << ", ";
+      os << copy.peekPriority() << ":";
+      writeGenericValue(os, copy.dequeue(), true);
+   }
+   return os << "}";
+}
+
+template <typename ValueType>
+std::istream & operator>>(std::istream & is, PriorityQueue<ValueType> & pq) {
+   char ch;
+   is >> ch;
+   if (ch != '{') error("operator >>: Missing {");
+   pq.clear();
+   is >> ch;
+   if (ch != '}') {
+      is.unget();
+      while (true) {
+         double priority;
+         is >> priority >> ch;
+         if (ch != ':') error("operator >>: Missing colon after priority");
+         ValueType value;
+         readGenericValue(is, value);
+         pq.enqueue(value, priority);
+         is >> ch;
+         if (ch == '}') break;
+         if (ch != ',') {
+            error(std::string("operator >>: Unexpected character ") + ch);
+         }
+      }
+   }
+   return is;
+}
+
+#endif