1 files changed, 372 insertions, 0 deletions
diff --git a/labb8/lib/StanfordCPPLib/queue.h b/labb8/lib/StanfordCPPLib/queue.h
new file mode 100755
index 0000000..0d94a2c
--- /dev/null
+++ b/labb8/lib/StanfordCPPLib/queue.h
@@ -0,0 +1,372 @@
+/*
+ * File: queue.h
+ * -------------
+ * This file exports the <code>Queue</code> class, a collection
+ * in which values are ordinarily processed in a first-in/first-out
+ * (FIFO) order.
+ */
+
+#ifndef _queue_h
+#define _queue_h
+
+#include "vector.h"
+
+/*
+ * Class: Queue<ValueType>
+ * -----------------------
+ * This class models a linear structure called a <b><i>queue</i></b>
+ * in which values are added at one end and removed from the other.
+ * This discipline gives rise to a first-in/first-out behavior (FIFO)
+ * that is the defining feature of queues.
+ */
+
+template <typename ValueType>
+class Queue {
+
+public:
+
+/*
+ * Constructor: Queue
+ * Usage: Queue<ValueType> queue;
+ * ------------------------------
+ * Initializes a new empty queue.
+ */
+
+   Queue();
+
+/*
+ * Destructor: ~Queue
+ * ------------------
+ * Frees any heap storage associated with this queue.
+ */
+
+   virtual ~Queue();
+
+/*
+ * Method: size
+ * Usage: int n = queue.size();
+ * ----------------------------
+ * Returns the number of values in the queue.
+ */
+
+   int size() const;
+
+/*
+ * Method: isEmpty
+ * Usage: if (queue.isEmpty()) ...
+ * -------------------------------
+ * Returns <code>true</code> if the queue contains no elements.
+ */
+
+   bool isEmpty() const;
+
+/*
+ * Method: clear
+ * Usage: queue.clear();
+ * ---------------------
+ * Removes all elements from the queue.
+ */
+
+   void clear();
+
+/*
+ * Method: enqueue
+ * Usage: queue.enqueue(value);
+ * ----------------------------
+ * Adds <code>value</code> to the end of the queue.
+ */
+
+   void enqueue(ValueType value);
+
+/*
+ * Method: dequeue
+ * Usage: ValueType first = queue.dequeue();
+ * -----------------------------------------
+ * Removes and returns the first item in the queue.
+ */
+
+   ValueType dequeue();
+
+/*
+ * Method: peek
+ * Usage: ValueType first = queue.peek();
+ * --------------------------------------
+ * Returns the first value in the queue, without removing it.  For
+ * compatibility with the STL classes, this method is also exported
+ * under the name <code>front</code>, in which case it returns the
+ * value by reference.
+ */
+
+   ValueType peek() const;
+
+/*
+ * Method: front
+ * Usage: ValueType first = queue.front();
+ * ---------------------------------------
+ * Returns the first value in the queue by reference.
+ */
+
+   ValueType & front();
+
+/*
+ * Method: back
+ * Usage: ValueType last = queue.back();
+ * -------------------------------------
+ * Returns the last value in the queue by reference.
+ */
+
+   ValueType & back();
+
+/*
+ * Method: toString
+ * Usage: string str = queue.toString();
+ * -------------------------------------
+ * Converts the queue to a printable string representation.
+ */
+
+   std::string toString();
+
+/*
+ * Operator: ==
+ * Usage: queue1 == queue2
+ * -------------------
+ * Returns <code>true</code> if <code>queue1</code> and <code>queue2</code>
+ * contain the same elements.
+ */
+
+   bool operator==(const Queue & queue2) const;
+
+/*
+ * Operator: !=
+ * Usage: queue1 != queue2
+ * -------------------
+ * Returns <code>true</code> if <code>queue1</code> and <code>queue2</code>
+ * do not contain the same elements.
+ */
+
+   bool operator!=(const Queue & queue2) const;
+
+/* 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: Queue data structure
+ * ------------------------------------------
+ * The Queue class is implemented using a ring buffer.
+ */
+
+private:
+
+/* Instance variables */
+
+   Vector<ValueType> ringBuffer;
+   int count;
+   int capacity;
+   int head;
+   int tail;
+
+/* Private functions */
+
+   void expandRingBufferCapacity();
+
+};
+
+extern void error(std::string msg);
+
+/*
+ * Implementation notes: Queue data structure
+ * ------------------------------------------
+ * The array-based queue stores the elements in successive index
+ * positions in a vector, just as a stack does.  What makes the
+ * queue structure more complex is the need to avoid shifting
+ * elements as the queue expands and contracts.  In the array
+ * model, this goal is achieved by keeping track of both the
+ * head and tail indices.  The tail index increases by one each
+ * time an element is enqueued, and the head index increases by
+ * one each time an element is dequeued.  Each index therefore
+ * marches toward the end of the allocated vector and will
+ * eventually reach the end.  Rather than allocate new memory,
+ * this implementation lets each index wrap around back to the
+ * beginning as if the ends of the array of elements were joined
+ * to form a circle.  This representation is called a ring buffer.
+ */
+
+const int INITIAL_CAPACITY = 10;
+
+/*
+ * Implementation notes: Queue constructor
+ * ---------------------------------------
+ * The constructor must allocate the array storage for the queue
+ * elements and initialize the fields of the object.
+ */
+
+template <typename ValueType>
+Queue<ValueType>::Queue() {
+   clear();
+}
+
+/*
+ * Implementation notes: ~Queue destructor
+ * ---------------------------------------
+ * All of the dynamic memory is allocated in the Vector class,
+ * so no work is required at this level.
+ */
+
+template <typename ValueType>
+Queue<ValueType>::~Queue() {
+   /* Empty */
+}
+
+template <typename ValueType>
+int Queue<ValueType>::size() const {
+   return count;
+}
+
+template <typename ValueType>
+bool Queue<ValueType>::isEmpty() const {
+   return count == 0;
+}
+
+template <typename ValueType>
+void Queue<ValueType>::clear() {
+   capacity = INITIAL_CAPACITY;
+   ringBuffer = Vector<ValueType>(capacity);
+   head = 0;
+   tail = 0;
+   count = 0;
+}
+
+template <typename ValueType>
+void Queue<ValueType>::enqueue(ValueType value) {
+   if (count >= capacity - 1) expandRingBufferCapacity();
+   ringBuffer[tail] = value;
+   tail = (tail + 1) % capacity;
+   count++;
+}
+
+/*
+ * Implementation notes: dequeue, peek
+ * -----------------------------------
+ * These methods must check for an empty queue and report an error
+ * if there is no first element.
+ */
+
+template <typename ValueType>
+ValueType Queue<ValueType>::dequeue() {
+   if (count == 0) error("dequeue: Attempting to dequeue an empty queue");
+   ValueType result = ringBuffer[head];
+   head = (head + 1) % capacity;
+   count--;
+   return result;
+}
+
+template <typename ValueType>
+ValueType Queue<ValueType>::peek() const {
+   if (count == 0) error("peek: Attempting to peek at an empty queue");
+   return ringBuffer.get(head);
+}
+
+template <typename ValueType>
+ValueType & Queue<ValueType>::front() {
+   if (count == 0) error("front: Attempting to read front of an empty queue");
+   return ringBuffer[head];
+}
+
+template <typename ValueType>
+ValueType & Queue<ValueType>::back() {
+   if (count == 0) error("back: Attempting to read back of an empty queue");
+   return ringBuffer[(tail + capacity - 1) % capacity];
+}
+
+/*
+ * Implementation notes: expandRingBufferCapacity
+ * ----------------------------------------------
+ * This private method doubles the capacity of the ringBuffer vector.
+ * Note that this implementation also shifts all the elements back to
+ * the beginning of the vector.
+ */
+
+template <typename ValueType>
+void Queue<ValueType>::expandRingBufferCapacity() {
+   Vector<ValueType> copy = ringBuffer;
+   ringBuffer = Vector<ValueType>(2 * capacity);
+   for (int i = 0; i < count; i++) {
+      ringBuffer[i] = copy[(head + i) % capacity];
+   }
+   head = 0;
+   tail = count;
+   capacity *= 2;
+}
+
+template <typename ValueType>
+std::string Queue<ValueType>::toString() {
+   ostringstream os;
+   os << *this;
+   return os.str();
+}
+
+template <typename ValueType>
+bool Queue<ValueType>::operator==(const Queue & queue2) const {
+   if (size() != queue2.size()) return false;
+   Queue<ValueType> copy1 = *this;
+   Queue<ValueType> copy2 = queue2;
+   for (int i = 0; i < size(); i++) {
+       if (copy1.dequeue() != copy2.dequeue()) {
+           return false;
+       }
+   }
+   return true;
+}
+
+template <typename ValueType>
+bool Queue<ValueType>::operator!=(const Queue & queue2) const {
+   return !(*this == queue2);
+}
+
+template <typename ValueType>
+std::ostream & operator<<(std::ostream & os, const Queue<ValueType> & queue) {
+   os << "{";
+   Queue<ValueType> copy = queue;
+   int len = queue.size();
+   for (int i = 0; i < len; i++) {
+      if (i > 0) os << ", ";
+      writeGenericValue(os, copy.dequeue(), true);
+   }
+   return os << "}";
+}
+
+template <typename ValueType>
+std::istream & operator>>(std::istream & is, Queue<ValueType> & queue) {
+   char ch;
+   is >> ch;
+   if (ch != '{') error("operator >>: Missing {");
+   queue.clear();
+   is >> ch;
+   if (ch != '}') {
+      is.unget();
+      while (true) {
+         ValueType value;
+         readGenericValue(is, value);
+         queue.enqueue(value);
+         is >> ch;
+         if (ch == '}') break;
+         if (ch != ',') {
+            error(std::string("operator >>: Unexpected character ") + ch);
+         }
+      }
+   }
+   return is;
+}
+
+// hashing functions for queues;  defined in hashmap.cpp
+int hashCode(const Queue<std::string>& q);
+int hashCode(const Queue<int>& q);
+int hashCode(const Queue<char>& q);
+int hashCode(const Queue<long>& q);
+int hashCode(const Queue<double>& q);
+
+#endif