/**
 * File: pathfinder.cpp
 * --------------------
 * Path finder algorithm implemented 
 * as part of the "Programming abstractions"
 * class (CS 106B) taken at Stanford.
 * Please note that only the main class was written entirely by me, 
 * some of the other classes and interfaces were provided 
 * as part of the assignment.
 * The final program also includes a library of classes,
 * which was provided as part of the assignment
 * and which I did not include here.
 */

#include <cmath>
#include <fstream>
#include <iostream>
#include <string>
#include "console.h"
#include "pathfinder-graph.h"
#include "pathfinder-graphics.h"
#include "error.h"
#include "gwindow.h"
#include "map.h"
#include "pqueue.h"
#include "point.h"
#include "tokenscanner.h"
#include "set.h"
#include "simpio.h"
#include "strlib.h"
#include <vector.h>
#include "stdlib.h" // for atof
#include "path.h"
using namespace std;

static void giveInstructions();
static void newMap(PathfinderGraph& g);
void readGraphFromFile(ifstream& infile, PathfinderGraph& g);

static void Dijkstra(PathfinderGraph& g);
static void Dijkstra(const GPoint& pt, PathfinderGraph& g);
void findShortestPath(Node* origin, const Node* destination, PathfinderGraph& g);
double getPathCost(const Vector<Arc *>& path);

static void quitAction();
void drawGraph(PathfinderGraph& g);
void printGraph(PathfinderGraph& g);

static const string kStarter_Map = "data-files/USA.txt";
static const int kClick_Tolerance = 5;

string getFileName(ifstream & infile, const string prompt);

/**
 * Function: main
 * --------------
 * Defines the entry point for the entire application.
 */
int main() {
 GWindow gw(kWindowWidth, kWindowHeight + kControlStripHeight);
 initPathfinderGraphics(gw);
 giveInstructions();
 PathfinderGraph g;
 ifstream infile;
 infile.open(kStarter_Map.c_str());
 readGraphFromFile(infile, g);
 drawPathfinderMap(g.getMapFile());
 drawGraph(g); 
 addButton("Quit", quitAction);
 addButton("Map", newMap, g);
 addButton("Dijkstra", Dijkstra, g);
 pathfinderEventLoop();
 return 0;
}

/**
 * Function: giveInstructions
 * Usage: giveInstructions();
 * --------------------------
 * Describes the Pathfinder assignment on the console. This text has
 * been retained in its original form to preserve the assignment history.
 */
static void giveInstructions() {
 cout << "This masterful piece of work is a graph extravaganza!" << endl;
 cout << "The main attractions include a lovely visual presentation" << endl;
 cout << "of the graph along with an implementation of Dijkstra's" << endl;
 cout << "shortest path algorithm and Kruskal's computation of" << endl;
 cout << "a minimal spanning tree. Enjoy!" << endl << endl;
}

/**
 * newMap
 */

static void newMap(PathfinderGraph& g) {
 g.clear();
 ifstream infile;
 string filename = getFileName(infile, "Please enter name of graph data file: ");
 readGraphFromFile(infile, g);
 drawPathfinderMap(g.getMapFile());
 drawGraph(g);
 printGraph(g);
}

/**
 * This function assumes that the data file is well formed.
 */

void readGraphFromFile(ifstream& infile, PathfinderGraph& g) {
 string mapName;
 getline(infile, mapName);
 //cout << "Map name: " << mapName << endl;
 g.setMapFile(mapName);
 string newLine;
 getline(infile, newLine); // get 'NODES"
 //cout << newLine << endl;
 getline(infile, newLine); // get first node
 while (newLine != "ARCS") {
 TokenScanner ts(newLine);
 ts.ignoreWhitespace();
 ts.scanNumbers();
 Node *newNode = new Node;
 newNode->name = ts.nextToken();
 GPoint loc = GPoint(stringToInteger(ts.nextToken()), stringToInteger(ts.nextToken()));
 newNode->loc = loc;
 g.addNode(newNode);
 //cout << newNode->name << loc.getX() << "; " << loc.getY() << endl;
 getline(infile, newLine);
 }
 //cout << newLine << endl;
 getline(infile, newLine); // get first arc
 while (!infile.eof()) {
 TokenScanner ts(newLine);
 ts.ignoreWhitespace();
 ts.scanNumbers();
 Arc *newArc = new Arc;
 Arc *mirrorArc = new Arc;
 mirrorArc->finish = newArc->start = g.getNode(ts.nextToken());
 mirrorArc->start = newArc->finish = g.getNode(ts.nextToken());
 mirrorArc->cost = newArc->cost = atof(ts.nextToken().c_str());
 g.addArc(newArc);
 g.addArc(mirrorArc);
 //cout << newArc->start->name << " " << newArc->finish->name << " " << newArc->cost << endl;
 //cout << mirrorArc->start->name << " " << mirrorArc->finish->name << " " << mirrorArc->cost << endl;
 getline(infile, newLine);
 }
}

static void Dijkstra(PathfinderGraph& g) {
 cout << "Please click on the origin and destination cities to find the cheapest path between them." << endl;
 defineClickListener(Dijkstra, g);
}

static void Dijkstra(const GPoint& pt, PathfinderGraph& g) {
 int x = pt.getX();
 int y = pt.getY();
 for (Node* node : g.getNodeSet()) {
 if ( ((node->loc.getX() - kClick_Tolerance ) < x)
 && (x < (node->loc.getX() + kClick_Tolerance ))
 && ((node->loc.getY() - kClick_Tolerance ) < y)
 && (y < (node->loc.getY() + kClick_Tolerance )) ) {
 if (g.getHighlightedNode() == NULL) {
 drawGraph(g);
 cout << "x: " << x << " y: " << y << endl;
 cout << "Your chosen origin is " << node->name << "." << endl;
 g.setHighlightedNode(node);
 drawPathfinderNode(node->loc, kHighlightColor);
 }
 else {
 Node* origin = g.getHighlightedNode();
 cout << "Your chosen destination is " << node->name << "." << endl << endl;
 g.setHighlightedNode(NULL);
 drawPathfinderNode(node->loc, kHighlightColor);
 findShortestPath(origin, node, g);
 }
 break;
 }
 }
}

void findShortestPath(Node* origin, const Node* destination, PathfinderGraph& g) {
 cout << "Finding the cheapest path between " << origin->name << " and " << destination->name << "..." << endl;
 Path* path = new Path;
 PQueue<Path *> queue;
 Node* start = origin;
 Map<string, double> fixed;
 while (start != destination) {
 if (!fixed.containsKey(start->name)) {
 fixed.put(start->name, path->getCost());
 cout << "Fix the cost to " << start->name << " at " << path->getCost() << endl;
 cout << "Process the arcs out of " << start->name << " (";
 int arcs = 0;
 for (Arc *arc : start->arcs) {
 cout << arc->finish->name;
 if (++arcs < start->arcs.size()) cout << ", ";
 }
 cout << ")" << endl;
 for (Arc *arc : start->arcs) {
 if (!fixed.containsKey(arc->finish->name)) {
 path->addArc(arc);
 queue.enqueue(path, path->getCost());
 //cout << " " << "Enqueue the path: " << arc->start->name << " -> "
 // << arc->finish->name << "(" << arc->cost << ")" << endl;
 path->removeLast();
 }
 else cout << "Ignore " << arc->finish->name << " because its cost is known." << endl;
 }
 }
 else cout << "Ignore " << origin->name << " because its cost is known." << endl;
 if (queue.isEmpty()) {
 path->clear();
 break;
 }
 path = queue.extractMin();
 //cout << "Dequeue the cheapest path: " << path.toString() << " (" << path.getCost() << ")." << endl;
 start = path->getLast()->finish;
 }
 if (path->isEmpty())
 cout << endl << "This is too daunting a task for a modest computer like me. "
 << "Please stop tormenting me and choose two distinct cities." << endl << endl;
 else {
 cout << endl << "The cheapest path between " << origin->name << " and " << destination->name
 << " is: " << path->toString() << "." << endl << endl;
 }
}

double getPathCost(const Vector<Arc *>& path) {
 double cost = 0;
 for (Arc *arc : path) {
 cost += arc->cost;
 }
 return cost;
}

/**
 * Function: quitAction
 * Usage: quitAction(g);
 * ---------------------
 * Called when the user clicks the Quit button in the control strip.
 */
static void quitAction() {
 exitGraphics();
}

/**
 * Gets a new map file name from the user and opens the file.
 * If the file does not exist, it prompts the user for another file name. 
 * Same if the file cannot be opened.
 * Returns the file name.
 */
string getFileName(ifstream & infile, const string prompt) {
 while (true) {
 cout << prompt;
 string filename;
 cin >> filename;
 filename = string("data-files/") + filename;
 infile.open(filename.c_str());
 if(!infile.fail()) return filename;
 infile.clear();
 cout << "Unable to open the map file named " << filename << ". It may be missing or corrupted. Please select another file." << endl;
 }
}

/**
 * Function: drawGraph
 * Usage: drawGraph(g);
 * -------------------
 * Draws all the nodes and all the arcs of the graph.
 */
void drawGraph(PathfinderGraph& g) {
 for (Node* node : g.getNodeSet()) {
 drawPathfinderNode(node->loc, kNodeColor, node->name);
 }
 for (Arc* arc : g.getArcSet()) {
 drawPathfinderArc(arc->start->loc, arc->finish->loc, kArcColor);
 }
}

/**
 * Helper Function: printGraph
 * Usage: printGraph(g);
 * ---------------------------
 * Prints all nodes and all arcs of the graph to the console.
 */
void printGraph(PathfinderGraph& g) {
 cout << endl << "PRINTING GRAPH: " << endl;
 cout << g.getMapFile() << endl;
 cout << "NODES" << endl;
 for (Node* node : g.getNodeSet()) {
 cout << node->name << " " << node->loc.getX() << " " << node->loc.getY() << endl;
 }
 cout << "ARCS " << endl;
 for (Arc* arc : g.getArcSet()) {
 cout << arc->start->name << " " << arc->finish->name << " " << arc->cost << endl;
 }
}

/*

 * File: graphtypes.h
 * ------------------
 * This file defines low-level data structures that represent graphs.
 */

#ifndef _graphtypes_h
#define _graphtypes_h

#include <string>
#include "gtypes.h"
#include "map.h"
#include "set.h"

struct Node; /* Forward references to these two types so */
struct Arc; /* that the C++ compiler can recognize them. */

/*
 * Type: SimpleGraph
 * -----------------
 * This type represents a graph and consists of a set of nodes, a set of
 * arcs, and a map that creates an association between names and nodes.
 */

struct SimpleGraph {
 Set<Node *> nodes;
 Set<Arc *> arcs;
 Map<std::string, Node *> nodeMap;
};

/*
 * Type: Node
 * ----------
 * This type represents an individual node and consists of the
 * name of the node and the set of arcs from this node.
 */

struct Node {
 std::string name;
 Set<Arc *> arcs;
 GPoint loc;
};

/*
 * Type: Arc
 * ---------
 * This type represents an individual arc and consists of pointers
 * to the endpoints, along with the cost of traversing the arc.
 */

struct Arc {
 Node *start;
 Node *finish;
 double cost;
};

#endif

/**
 * File: pathfinder-graph.cpp
 * --------------------------
 * Provides the (fairly obvious) implementation of
 * the PathfinderGraph class.
 */

#include "pathfinder-graph.h"
using namespace std;

void PathfinderGraph::setMapFile(const string& filename) {
 mapFile = filename;
 highlightedNode = NULL;
}

const string& PathfinderGraph::getMapFile() const {
 return mapFile;
}

void PathfinderGraph::setHighlightedNode(Node *node) {
 highlightedNode = node;
}

Node *PathfinderGraph::getHighlightedNode() const {
 return highlightedNode;
}

/**
 * File: pathfinder-graphics.cpp
 * -----------------------------
 * The pathfinder-graphics.cpp file implements a set of functions that help draw the
 * necessary parts of the Pathfinder maps.
 */

#include <iostream>
#include <string>
#include "gevents.h"
#include "gobjects.h"
#include "pathfinder-graphics.h"
#include "gwindow.h"
#include "point.h"
using namespace std;

/* Constants */

const string kControlStripColor = "#E5E5E5";
const double kButtonWidth = 90;
const double kButtonHeight = 29;
const double kButtonSeparation = 6;
const double kStartupDelay = 50;

/* Class for buttons */

class ActionButton : public GButton {
public:
 ActionButton(const string& label, ButtonFunction *fn) : GButton(label) {
 this->fn = fn;
 }

void execute() {
 fn->execute();
 }

private:
 ButtonFunction *fn;
};

/* Global data */

static GWindow *gwp;
static ClickFunction *clickHook = NULL;
static double nextButtonX = kButtonSeparation;

/* Prototypes */

void drawCircle(double x, double y, double r);
void fillCircle(double x, double y, double r);

/* Exported functions */

void initPathfinderGraphics(GWindow& gw) {
 gwp = &gw;
 GRect strip(0, kWindowHeight, kWindowWidth, kControlStripHeight);
 strip.setColor(kControlStripColor);
 strip.setFilled(true);
 gwp->draw(strip);
 gwp->setWindowTitle("Pathfinder");
 pause(kStartupDelay);
}

void drawPathfinderMap(const string& mapFile) {
 gwp->setColor("WHITE");
 gwp->fillRect(0, 0, kWindowWidth, kWindowHeight);
 gwp->setColor("BLACK");
 if (mapFile != "") {
 GImage map(mapFile);
 gwp->draw(map);
 }
}

void drawPathfinderNode(const GPoint& center, const string& color, const string& str) {
 gwp->setColor(color);
 fillCircle(center.getX(), center.getY(), kNodeRadius);
 if (!str.empty()) {
 GLabel label(str);
 label.setFont(kLabelFont);
 label.setLocation(center.getX() + kNodeRadius + 2, center.getY() + 5);
 gwp->draw(label);
 }
}

void drawPathfinderArc(const GPoint& start, const GPoint& end, const string& color) {
 gwp->setColor(color);
 gwp->drawLine(start.getX(), start.getY(), end.getX(), end.getY());
}

/*
 * Implementation notes: addButton
 * -------------------------------
 * This function creates a button and adds it to the vector of buttons
 * at the next available position in the control strip.
 */

void addButton(const string& name, void (*actionFn)()) {
 addButton(name, new ButtonFunctionWithoutData(actionFn));
}

void addButton(const string& name, ButtonFunction *fn) {
 double x = nextButtonX;
 double y = kWindowHeight + (kControlStripHeight - kButtonHeight) / 2;
 ActionButton *button = new ActionButton(name, fn);
 button->setBounds(x, y, kButtonWidth, kButtonHeight);
 gwp->add(button);
 nextButtonX += kButtonWidth + kButtonSeparation;
}

/*
 * Implementation notes: defineClickListener
 * -----------------------------------------
 * This function designates a listener for mouse clicks in the window.
 */

void defineClickListener(void (*clickFn)(const GPoint& pt)) {
 defineClickListener(new ClickFunctionWithoutData(clickFn));
}

void defineClickListener(ClickFunction *callback) {
 clickHook = callback;
}

void pathfinderEventLoop() {
 while (true) {
 GEvent e;
 waitForClick(e);
 if (e.getEventClass() == ACTION_EVENT) {
 ActionButton *bp = (ActionButton *) ((GActionEvent) e).getSource();
 bp->execute();
 } else if (e.getEventClass() == MOUSE_EVENT && clickHook != NULL) {
 GMouseEvent me = (GMouseEvent) e;
 if (me.getEventType() == MOUSE_CLICKED) {
 clickHook->execute(GPoint(me.getX(), me.getY()));
 }
 }
 }
}

/*
 * Implementation notes: getMouseClick
 * -----------------------------------
 * getMouseClick waits for the mouse button to go down and then up again,
 * at which point the function returns the mouse position at the time of
 * release.
 */

GPoint getMouseClick() {
 GMouseEvent e;
 waitForClick(e);
 return GPoint(e.getX(), e.getY());
}

/* Helper functions */

/*
 * Implementation notes: drawCircle, fillCircle
 * --------------------------------------------
 * These functions are useful tools that draw an outlined and a filled
 * circle, respectively. If you are extending the Pathfinder assignment,
 * you might well want to export these methods through the gpathfinder.h
 * interface.
 */

void drawCircle(double x, double y, double r) {
 gwp->drawOval(x - r, y - r, 2 * r, 2 * r);
}

void fillCircle(double x, double y, double r) {
 gwp->fillOval(x - r, y - r, 2 * r, 2 * r);
}

/*
 * Implementation notes: Implementation of the callback classes
 * ------------------------------------------------------------
 * The remaining functions in this file support the implementation
 * of the various callback classes.
 */

ButtonFunctionWithoutData::ButtonFunctionWithoutData(void (*fn)()) {
 this->fn = fn;
}

void ButtonFunctionWithoutData::execute() {
 fn();
}

ClickFunctionWithoutData::ClickFunctionWithoutData(void (*fn)(const GPoint&)) {
 this->fn = fn;
}

void ClickFunctionWithoutData::execute(const GPoint& pt) {
 fn(pt);
}

/*
 * File: graphtypes.h
 * ------------------
 * This file defines low-level data structures that represent graphs.
 */

#ifndef _graphtypes_h
#define _graphtypes_h

#include <string>
#include "gtypes.h"
#include "map.h"
#include "set.h"

struct Node; /* Forward references to these two types so */
struct Arc; /* that the C++ compiler can recognize them. */

/*
 * Type: SimpleGraph
 * -----------------
 * This type represents a graph and consists of a set of nodes, a set of
 * arcs, and a map that creates an association between names and nodes.
 */

struct SimpleGraph {
 Set<Node *> nodes;
 Set<Arc *> arcs;
 Map<std::string, Node *> nodeMap;
};

/*
 * Type: Node
 * ----------
 * This type represents an individual node and consists of the
 * name of the node and the set of arcs from this node.
 */

struct Node {
 std::string name;
 Set<Arc *> arcs;
 GPoint loc;
};

/*
 * Type: Arc
 * ---------
 * This type represents an individual arc and consists of pointers
 * to the endpoints, along with the cost of traversing the arc.
 */

struct Arc {
 Node *start;
 Node *finish;
 double cost;
};

#endif

/*
 * File: path.h
 * ------------
 * This file is the interface for a Path class, which consists of a
 * sequence of arcs.
 */

#include "pathfinder-graph.h"
#include "hashset.h"

#ifndef _path_h
#define _path_h

class Path {

public:

Path();
 ~Path();

 void addArc(Arc* const arc);
 Arc *getLast() const;
 void removeLast();
 void clear();
 double getCost() const;
 string toString() const;
 bool isEmpty() const;

private:

static const int kInitialArraySize = 10;

 Arc **arcs;
 double cost;
 int capacity;
 int size;

 void doubleCapacity();
};

#endif

/**
 * File: pathfinder-graph.h
* ------------
* Exports a strongly typed subclass of the Graph template
* that's Pathfinder-specific.
*/

#ifndef _pathfinder_graph_
#define _pathfinder_graph_

#include <string>
#include "graph.h" // for template Graph class
#include "graphtypes.h" // for struct Node

/**
 * Class: PathfinderGraph
 * ----------------------
 * This class extends the standard Graph class so that the new
 * class incorporates the Node and Arc type parameters. The
 * extended data structure also includes an image file name for
 * the map and the ability to designate a particular node as
 * highlighted.
 */

class PathfinderGraph : public Graph<Node,Arc> {
public:
 void setMapFile(const std::string& filename);
 const std::string& getMapFile() const;
 void setHighlightedNode(Node *node);
 Node *getHighlightedNode() const;

private:
 std::string mapFile;
 Node *highlightedNode;
};

#endif

/**
 * File: pathfinder-graphics.h
 * ---------------------------
 * The pathfinder-graphics.h file defines the interface for a set of functions
 * that help draw the necessary parts of the Pathfinder maps. The
 * pathfinder-graphics.h interface uses screen coordinates in which distances
 * on the screen are expressed in pixels and in which the origin in the
 * upper left corner of the window. Several of the functions defined
 * in this package use values of type GPoint, which is simply a pair of
 * x and y coordinate values, as defined in the point.h interface.
 *
 * This interface also exports several methods for creating buttons
 * in a control strip and for responding to button and mouse clicks.
 * The general approach parallels the standard model used in modern
 * event-driven systems. The client application creates a series of
 * buttons, each of which supplies a callback function that is
 * invoked whenever that button is clicked. The application then
 * calls pathfinderEventLoop, which waits for events generated in
 * response to user actions.
 */

#ifndef _pathfinder_graphics_
#define _pathfinder_graphics_

#include "gtypes.h"
#include "gobjects.h"

/**
 * Constants
 * ---------
 * A few program-wide constants concerning the graphical display.
 * All coordinate values and distances are expressed in pixels.
 */

const int kWindowWidth = 655;
const int kWindowHeight = 400;
const int kControlStripHeight = 40;
const double kNodeRadius = 3.5; /* Radius of the node circle */
const string kArcColor = "DarkGray"; /* Normal arc color */
const string kNodeColor = "Black"; /* Normal node color */
const string kHighlightColor = "Red"; /* Color of chosen path/nodes */
const string kDimColor = "Gray"; /* Color of unchosen path/nodes */
const string kLabelFont = "Helvetica-10"; /* Font for node labels */

/**
 * Function: initPathfinderGraphics
 * Usage: initPathfinderGraphics();
 * --------------------------------
 * Initializes the graphics window for Pathfinder. This call should
 * be the first statement in main.
 */
void initPathfinderGraphics(GWindow & gw);

/**
 * Function: drawPathfinderMap
 * Usage: drawPathfinderMap(mapFile);
 * ----------------------------------
 * Clears the graphics window and then draws the image contained in
 * the specified image file, which will typically live in an images
 * subdirectory of the project directory.
 */
void drawPathfinderMap(const string& mapFile);

/**
 * Function: drawPathfinderNode
 * Usage: drawPathfinderNode(center, color, label);
 * ------------------------------------------------
 * Draw a node circle whose center is at the coordinate position
 * specified by the first argument and that is filled in the specified
 * color. If a third argument is provided, the function draws a label
 * to the right of the circle containing the specified text.
 */
void drawPathfinderNode(const GPoint& center, const string& color, const string& label = "");

/**
 * Function: drawPathfinderArc
 * Usage: drawPathfinderArc(start, end, color);
 * --------------------------------------------
 * Draws a line on the screen connecting the two specified coordinate
 * positions using the indicated color.
 */
void drawPathfinderArc(const GPoint& start, const GPoint& end, const string& color);

/**
 * Function: addButton
 * Usage: addButton(name, actionFn);
 * addButton(name, actionFn, data);
 * ---------------------------------------
 * Adds a button to the window and assigns it an action function.
 * When the button is clicked, the program will invoke
 *
 * actionFn()
 * or
 * actionFn(data)
 *
 * depending on whether the data parameter is supplied. The data
 * parameter is passed by reference, so that the action function
 * can modify the program state.
 */
void addButton(const string& name, void (*actionFn)());

template <typename ClientType>
void addButton(const string& name, void (*actionFn)(ClientType& data), ClientType& data);

/**
 * Function: defineClickListener
 * Usage: defineClickListener(clickFn);
 * defineClickListener(clickFn, data);
 * ------------------------------------------
 * Designates a function that will be called whenever the user
 * clicks the mouse in the graphics window. If a click listener
 * has been specified by the program, the event loop will invoke
 *
 * clickFn(pt)
 *
 * or
 *
 * clickFn(pt, data)
 *
 * depending on whether the data parameter is supplied. In either
 * case, pt is the GPoint at which the click occurred and data
 * is a parameter of any type appropriate to the application. The
 * data parameter is passed by reference, so that the click function
 * can modify the program state.
 */
void defineClickListener(void (*actionFn)(const GPoint& pt));

template <typename ClientType>
void defineClickListener(void (*actionFn)(const GPoint& pt, ClientType & data), ClientType & data);

/**
 * Function: pathfinderEventLoop
 * Usage: pathfinderEventLoop();
 * -----------------------------
 * Initiates a loop that repeatedly waits for the user to click
 * on a button and calls the action function associated with that
 * button. Moreover, if the client has registered a click listener,
 * pathfinderEventLoop will call that listener whenever the mouse is
 * clicked inside the window.
 *
 * Note that pathfinderEventLoop never returns, so programs that need
 * to exit on user command need to call the exit() function in the
 * standard libraries.
 */
void pathfinderEventLoop();

/**
 * Function: getMouseClick
 * Usage: pt = getMouseClick();
 * ----------------------------
 * Waits for the user to click somewhere on the graphics window
 * and returns the coordinate of where the click took place.
 */

GPoint getMouseClick();

#include "pathfinder-graphics-impl.h"

#endif

/**
 * File: pqueue-impl.h
 * Original implementation by eroberts
 * Last modified on Sat Nov 03 16:33:00 PST 2012 by jcain
 * -------------------
 * This file provides a Vector-based implementation of the
 * pqueue.h interface.
 */

/**
 * Implementation notes: PQueue constuctor and destructor
 * ------------------------------------------------------
 * All the work for the constructor and destructor is done by the
 * Vector class.
 */

template <typename Type>
PQueue<Type>::PQueue() {}

template <typename Type>
PQueue<Type>::~PQueue() {}

/**
 * Implementation notes: size, isEmpty, clear
 * ------------------------------------------
 * These implementations simply forward the request to the
 * underlying Vector object.
 */

template <typename Type>
int PQueue<Type>::size() const {
 return entries.size();
}

template <typename Type>
bool PQueue<Type>::isEmpty() const {
 return entries.isEmpty();
}

/**
 * Implementation notes: enqueue
 * -----------------------------
 * This function finds where to insert a new element into the
 * queue and then calls insertAt to put it there. Because
 * items are removed from the end of the queue, the highest
 * priority elements must be stored at the end of the queue.
 * Moreover, to ensure that elements obey the first-in/first-out
 * discipline when they have the same priority, the function must
 * insert each new element before any with the same priority.
 * Keep in mind that the base type of the vector is pqEntryT,
 * which contains both the element and the priority.
 */

template <typename Type>
void PQueue<Type>::enqueue(const Type& elem, double priority) {
 int pos = 0;
 while (pos < entries.size() && entries[pos].priority > priority) {
 pos++;
 }
 entry ent = {elem, priority};
 entries.insert(pos, ent);
}

/**
 * Implementation notes: extractMin, peek
 * --------------------------------------
 * These functions must check for an empty queue and report an
 * error if there are no entries.
 */

template <typename Type>
Type PQueue<Type>::extractMin() {
 if (isEmpty()) error("extractMin: Attempting to extractMin from an empty queue.");
 int lastIndex = entries.size() - 1;
 Type result = entries[lastIndex].elem;
 entries.remove(lastIndex);
 return result;
}

template <typename Type>
const Type& PQueue<Type>::peek() const {
 if (isEmpty()) error("peek: Attempting to peek at an empty queue.");
 return entries[entries.size() - 1].elem;
}

/**
 * File: pqueue.h
 * Original interface by eroberts
 * Last modified on Sat Nov 03 16:33:00 PST 2012 by jcain
 * ----------------------------------------------------------
 * This file provides the interface to the PQueue class, which
 * implements a simple priority queue.
 */

#ifndef _pqueue_
#define _pqueue_

#include "vector.h"

/**
 * Class: PQueue
 * -------------
 * This class that models a priority queue, which is similar to a
 * traditional queue except that the elements are inserted in
 * order of priority. As in conventional English usage, lower
 * priority numbers correspond to higher priorities, so that a
 * priority 1 item must take precedence over a priority 2 item.
 */

template <typename Type>
class PQueue {
public:

/**
 * Constructor: PQueue
 * Usage: PQueue<int> pq;
 * ----------------------
 * The constructor initializes a new priority queue containing
 * elements of the specified type.
 */
 PQueue();

/**
 * Destructor: ~PQueue
 * Usage: (usually implicit)
 * -------------------------
 * The destructor deallocates storage associated with this queue.
 */
 ~PQueue();

/**
 * Method: size
 * Usage: nElems = pq.size();
 * --------------------------
 * Returns the number of elements in this priority queue.
 */
 int size() const;

/**
 * Method: isEmpty
 * Usage: if (pq.isEmpty()) . . .
 * ------------------------------
 * Returns true if this priority queue contains no elements,
 * and false otherwise.
 */
 bool isEmpty() const;

/**
 * Method: enqueue
 * Usage: pq.enqueue(element);
 * ---------------------------------
 * This method adds element to the priority queue, using operator<
 * to decide which elements have higher priority. Rather than relying
 * on operator< to determine priority, the interface just asks that the
 * client supply the priority.
 */
 void enqueue(const Type& elem, double priority);

/**
 * Method: extractMin
 * Usage: first = pq.extractMin();
 * ----------------------------
 * This method removes the highest-priority element from this queue
 * and returns it.
 */
 Type extractMin();

/**
 * Method: peek
 * Usage: first = pq.peek();
 * -------------------------
 * This method returns the value of highest-priority element in this
 * queue, without removing it.
 */
 const Type& peek() const;

private:
 struct entry {
 Type elem;
 double priority;
 };

 Vector<entry> entries;
};

#include "pqueue-impl.h"

#endif