/**
* 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