#include "library.h"
#include <string>
#include <fstream>
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <vector>
#include <sstream>
#include <stdlib.h>

using namespace std;

const int tabsize = 100000;
const double pi = acos(-1.0);

struct Descriptor {
	float area;
	int number; 
};

struct Region {
	float min_longitude;
	float min_latitude;
	float max_longitude;
	float max_latitude; 
};

struct Point {
	float longitude;
	float latitude; 
};

struct Outline {
	Descriptor* data;
	Point** points;
	Outline(Descriptor* d = NULL) {
		data = d;
		if (data != NULL) {
			int size = data->number;
			points = new Point* [size];
			for (int i=0; i<size; i++)
				points[i] = NULL;
		}
	}
};
	
struct state {
	Descriptor* description;
	Region* region;
	Outline** outlines;
	state(Descriptor* d = NULL, Region* r = NULL) {
		description = d;
		region = r;
		if (description != NULL) {
			int size = description->number;
			outlines = new Outline* [size];
			for (int i=0; i<size; i++)
				outlines[i] = NULL;
		}
	}
	void print() {
		cout << "Total area = " << description->area << " Num of outlines = " << description->number << "\n";
		cout << "Max Lat = " << region->max_latitude << " Max Lon = " << region->max_longitude << " Min Lat = " << region->min_latitude << " Min Lon = " << region->min_longitude << "\n";
		for (int i=0; i<50; i++) {
			cout << outlines[i]->data->area << "\n";
		}
	}
};

struct efile {
	int maxlat, minlat, maxlon, minlon;
	string filename;
	efile(int mala, int mila, int malo, int milo, string f):
		maxlat(mala), minlat(mila), maxlon(malo), minlon(milo), filename(f)
	{ }
};

struct position {
	double lat, lon;
	position(double latdeg, double londeg) {
		lat = latdeg * pi / 180;
		lon = londeg * pi / 180;
	 }
};

int Hash(string s) {
	const int init = 21512712, mult = 96169, emergency = 876127;
	int v = init;
	for (int i=0; i<s.length(); i+=1)
  		v = v * mult + s[i];
 	if (v < 0) v = -v;
	if (v < 0) v = emergency;
 	return v % tabsize;
}

string lowercase(string word) {
	for (int i=0; i<word.length(); i++) {
		if (word[i] >= 'A' && word[i] <= 'Z') word[i] = word[i] + 32;
	}
	return word;				//returns the string in all lowercase
}

string capitalized(string word) {
	if (word[0] >= 'a' && word[0] <= 'z') word[0] = word[0] - 32;
	for (int i=1; i<word.length(); i++) {
		if (word[i] >= 'A' && word[i] <= 'Z') word[i] = word[i] +32;
	}
	return word;				//returns the string with only first letter capitalized
}

class location {
  protected:
	int FIPSstate, FIPScensus, population, roadref;
	string state, town;
	double area, latitude, longitude, roaddist;
  public:
	location(int, int, string, string, int, double, double, double, int, double);
	void print();
	string getstate();			//returns the town's original state abbreviation
	string getstatelow();			//returns the town's state abbreviation in all lowercase
	string gettown();			//returns the town's name in all lowercase
	string gettowncaps();			//returns the original town name
	int getroad();
	double getlat();
	double getlon();
};

class Link {
   public:
	location* data;
	Link* next;
	Link(location* d, Link* n = NULL) {
		data = d;
		next = n;
	}
	~Link() {
		delete data;
		next = NULL;
	}
	void print() {
		data->print();
	}
};

class List {
  protected:
	Link* first;
	Link* last;
	int length;
  public:
	List() {
		first = NULL;
		last = NULL;
		length = 0;
	}
	~List() {
		Link* prev = NULL;
		while (first != NULL) {
			prev = first;
			first = prev->next;
			delete prev;
		}
		first = NULL;
		last = NULL;
		length = 0;
	}

	void add_to_front(location*);
	void add_to_end(location*);
	Link* get_first();
};

class connection {
  protected:
	string road, type;
	double roadlen;
	int start, end;						//these are just ref numbers, not really start and end
  public:
	connection(string, string, int, int, double);
	string getroad();
	int getstart();
	int getend();
	double getlen();
};

class intersection {
  protected:
	double longitude, latitude, towndist;
	string state, town;
	vector<connection*> connections;
//queue members
	bool nqueue, visitd;
	int pos;
	double shortestdist;
	connection* prevcon;
	intersection* previnter;
  public:
	intersection(double, double, double, string, string);
	void print();			//prints the user interface data
	void add_connection(connection* x) { connections.push_back(x); }
	vector<connection*> getconnections();
	double gettowndist();
	string gettown();
	string getstate();
	double getlon();
	double getlat();
//queue methods
	bool inqueue();			//returns true if intersection is in the queue
	void enqueue(int);		//places intersection in queue with queue position q
	void enqueue();			//default enqueue'ing without a queue position
	void dequeue();			//removes intersection from queue
	bool visited();			//returns true if intersection has been visited
	void visit();			//'visits' the intersection, sets visitd to true
	double getshortestdist();
	void setshortestdist(double);	//sets the shortest distance
	int getpos();
	void setpos(int);		//sets the position in queue
	void setprev(connection*,intersection*);		//sets the previous intersection/connection data
	connection* getprevcon();
	intersection* getprevinter();
};

struct queue {							//I used a priority queue and referred to these for shortest path algorithm:
	vector<intersection*> data;				//rabbit.eng.miami.edu/class/een318/nebraska-pos.gif
	queue() {						//rabbit.eng.miami.edu/class/een511/explorenebraska.txt
		for (int i=0; i<data.size(); i++)
			data[i] = NULL;
	}
	void add(intersection* x) {				//adds to the queue with priority
		for (int i=0; i<data.size(); i++) {
			if (x->getshortestdist() < data[i]->getshortestdist()) {
				data.insert(data.begin()+i,x);		//if the new intersection's distance is less than the
				x->enqueue(i);				//current shortest path's distance at any intersection
				update();				//we add it to the queue and update every position in the queue
				return;
			}
		}
		data.push_back(x);				//else put it at the end of the queue
		x->enqueue(data.size()-1);			//last pos in the queue is size-1
	}
	void update() {						//updates the position of every member of the queue
		for (int i=0; i<data.size(); i++)
			data[i]->setpos(i);
	}
	void print() {
		for (int i=0; i<data.size(); i++)
			data[i]->print();
	}
};

Link* List::get_first() { return first; }			//methods to return protected variables
string location::getstate() { return state; }
string location::getstatelow() { return lowercase(state); }
string location::gettown() { return lowercase(town); }
string location::gettowncaps() { return town; }
int location::getroad() { return roadref; }
double location::getlat() { return latitude; }
double location::getlon() { return longitude; }
string connection::getroad() { return road; }
vector<connection*> intersection::getconnections() { return connections; }
int connection::getstart() { return start; }
int connection::getend() { return end; }
double connection::getlen() { return roadlen; }
double intersection::gettowndist() { return towndist; }
string intersection::gettown() { return town; }
string intersection::getstate() { return state; }
double intersection::getlon() { return longitude; }
double intersection::getlat() { return latitude; }
bool intersection::inqueue() { return nqueue; }
void intersection::enqueue(int p) { nqueue = true; pos = p; } 
void intersection::enqueue() { nqueue = true; }	
void intersection::dequeue() { nqueue = false; pos = -1; }	
bool intersection::visited() { return visitd; }
void intersection::visit() { visitd = true; }
double intersection::getshortestdist() { return shortestdist; }
void intersection::setshortestdist(double x) { shortestdist = x; }
int intersection::getpos() { return pos; }
void intersection::setpos(int p) { pos = p; }
void intersection::setprev(connection* c,intersection* i) { prevcon = c; previnter = i; }
connection* intersection::getprevcon() { return prevcon; }
intersection* intersection::getprevinter() { return previnter; }

void List::add_to_front(location* x) {
	first = new Link(x, first);
	if (last==NULL) last = first;
	length++; }
void List::add_to_end(location* x) {
	Link* n = new Link(x, NULL);
	if (last != NULL) last->next = n;
	else first = n;
	last = n;
	length++; }

location::location(int FS, int FC, string s, string t, int p, double a, double lat, double lon, int rr, double rd):
	FIPSstate(FS), FIPScensus(FC), state(s), town(t), population(p), area(a), latitude(lat), longitude(lon), roadref(rr), roaddist(rd)
{ }
intersection::intersection(double lon, double lat, double dist, string s, string t):
	longitude(lon), latitude(lat), towndist(dist), state(s), town(t), nqueue(false), visitd(false), shortestdist(9999999), prevcon(NULL), previnter(NULL)
{ }	
connection::connection(string r, string t, int s, int e, double l):
	road(r), type(t), start(s), end(e), roadlen(l)
{ }

void location::print() {
	cout << town << ", " << state << "., pop. " << population << ", area " << area << " sq. mi., " << latitude << "N " << longitude << "W, " << roaddist << " mi. from intersection " << roadref << ".\n"; 
}
void intersection::print() {
	cout << longitude << ", " << latitude << ". " << towndist << " miles away from " << town << ", " << state;
	cout << ". Connects to: ";
	for (int i=0; i<connections.size(); i++) {
		cout << connections[i]->getroad();
		if (i<connections.size()-1) cout << ", ";
	}
	cout << ".\n"; 
}

location* readline(string &input) {
	int pos = 0;
	string FIPSs, FIPSc, s, t, pop, a, lat, lon, rr, rd;
	location* output = NULL;
	FIPSs = ""; FIPSc = ""; s = ""; t = ""; pop = "";
	a = ""; lat = ""; lon = ""; rr = ""; rd = "";

	FIPSs = input.substr(0,2);
	FIPSc = input.substr(2,5);
	s = input.substr(7,2);

	for (int i=9; input.substr(i,2)!="  "; i++) {		//reading in the town name of variable length
		t += input[i];					//building up the string char by char	
		if (input.substr(i+1,2)=="  ") pos = i+1; }	//updating the current position
	while (input[pos]==' ') pos++;				//incrementing to the next piece of data
	for (int i=pos; input[i]!=' '; i++) {			//reading in the population
		pop += input[i];				
		if (input[i+1]==' ') pos = i+1; }		//updating the current position
	while (input[pos]==' ') pos++;				//incrementing to the next piece of data
	for (int i=pos; input[i]!=' '; i++) {			//reading in the area
		a += input[i];
		if (input[i+1]==' ') pos = i+1;	}		//updating the current position
	for (int i=pos+1; input[i]!=' ' && input[i]!='-'; i++) {	//reading in the latitude  
		lat += input[i];
		if (input[i+1]==' ' || input[i+1]=='-') pos = i+1; }	//updating the current position
	while (input[pos]==' ') pos++;
	for (int i=pos; i<(input.length()-13); i++) {		//reading in the longitude
		lon += input[i];
		if (i+1==(input.length()-13)) pos = i+1; }	//updating the current position
	while (input[pos]==' ') pos++;
	for (int i=pos; i<(input.length()-8); i++) {		//reading in the road reference number
		rr += input[i];
		if (i+1==(input.length()-8)) pos = i+1;	}	//updating the current position
	while (input[pos]==' ') pos++;
	for (int i=pos; i<(input.length()); i++) {		//reading in the distance to road
		rd += input[i]; }
	output = new location(atoi(FIPSs.c_str()), atoi(FIPSc.c_str()), s, t, atoi(pop.c_str()), atof(a.c_str()), atof(lat.c_str()), atof(lon.c_str()), atoi(rr.c_str()), atof(rd.c_str()));	

	return output;
}

void read_file(string filename, List** &hashtable) {
	ifstream f(filename.c_str());
	if (f.fail()) {
		cerr << "Failed to open town file\n";
		exit(1);
	}
	
	int hashval;
	location* temp = NULL;
	string input;
	while (!f.eof()) {
		input = "";
		getline(f,input);
		if (f.fail()) break;
		temp = readline(input);
		hashval = Hash(temp->gettown());		//hash value is determined with a lowercase town name
		if (hashtable[hashval]->get_first() != NULL)	//when that value on the hash table has been taken
			hashtable[hashval]->add_to_end(temp);		
		else hashtable[hashval]->add_to_front(temp);
	}
	f.close(); 	
}

void read_inter(string filename, vector<intersection*> &data) {
	ifstream f(filename.c_str());
	if (f.fail()) {
		cerr << "Failed to open intersecion file\n";
		exit(1);
	}
	string lon, lat, dist, state, town;
	string input;	
	lon = ""; lat = ""; dist = ""; state = ""; town = ""; input = "";
	while (!f.eof()) {
		getline(f,input);
		if (f.fail()) break;
		istringstream parse(input);
		parse >> lon >> lat >> dist >> state;
		town = input.substr(30,input.length());
		data.push_back(new intersection(atof(lon.c_str()), atof(lat.c_str()), atof(dist.c_str()), state, town));
	}
	f.close();
}

void read_connect(string filename, vector<connection*> &data, vector<intersection*> &inter) {
	ifstream f(filename.c_str());
	if (f.fail()) {
		cerr << "Failed to open connection file\n";
		exit(1);
	}
	string name, type, ref1, ref2, len;
	string input;
	name = ""; type = ""; ref1 = ""; ref2 = ""; len = ""; input = "";
	connection* temp = NULL;
	while (!f.eof()) {
		getline(f, input);
		if (f.fail()) break;
		istringstream parse(input);
		parse >> name >> type >> ref1 >> ref2 >> len;
		temp = new connection(name, type, atoi(ref1.c_str()), atoi(ref2.c_str()), atof(len.c_str()));		
		data.push_back(temp);
		inter[atoi(ref1.c_str())]->add_connection(temp);
		inter[atoi(ref2.c_str())]->add_connection(temp);
	}
	f.close();
} 

Link* search(List** table, string Town) {
	string town = lowercase(Town);
	int key = Hash(town);

	if (table[key]->get_first() == NULL) {
		cerr << "Town not found.\n";
		return NULL;
	}

	if (table[key]->get_first()->data != NULL) {
		if (table[key]->get_first()->next == NULL && table[key]->get_first()->data->gettown() == town) return table[key]->get_first();
		else if (table[key]->get_first()->next != NULL) {
			Link* cur = table[key]->get_first();
			int counter = 0;
			if (cur->data->gettown() == town) counter++;
			while (cur->next != NULL) {
				cur = cur->next;
				if (cur->data != NULL && cur->data->gettown() == town) counter++; }
			cur = table[key]->get_first();

			if (counter>1) {				//if the town appears in the list multiples times
				cout << capitalized(Town) << " appears in: ";
				while (cur != NULL) {			//finding each state the town appears
					if (cur->data->gettown() == town) cout << cur->data->getstate() << ", ";
					cur = cur->next; }
				cout << "Which one? ";
				string whichstate;
				getline(cin, whichstate);
				whichstate = lowercase(whichstate);	//converting to lowercase for comparison

				cur = table[key]->get_first();
				if (cur->data->getstatelow() == whichstate) return cur;
				while (cur->next != NULL) {		//finding the user entered state to return correct town
					cur = cur->next;
					if (cur->data != NULL && cur->data->getstatelow() == whichstate && cur->data->gettown() == town) return cur; }
				cerr << "Invalid state!\n";
				return NULL;	
			}
			else if (counter==1) {				//if the town appears in the list once
				if (cur->data->gettown() == town) return cur;
				while (cur->next != NULL) {
					cur = cur->next;
					if (cur->data !=NULL && cur->data->gettown() == town) return cur; }
				cerr << "Town not found.\n";
				return NULL;
			}
			else {
				cerr << "Town not found.\n";
				return NULL;
			}
		}
		cerr << "Town not found.\n";
		return NULL;
	}	
	else {
		cerr << "Town not found.\n";
		return NULL;
	}
}	

void trace(intersection* end, intersection* start, vector<intersection*> &path) {	//traces back the shortest path and puts it into a vector
	intersection* curr = end;
	while (curr != NULL) {
		path.push_back(curr);
		curr = curr->getprevinter();
	}
	/*for (int i=0; i<path.size(); i++) {	//un-comment to print out the shortest path
		path[i]->print();
	}*/
}

vector<intersection*> navigate(intersection* &start, intersection* &end, vector<intersection*> iarray, vector<connection*> carray) {
	vector<intersection*> empty;
	if (start==end) {
		cerr << "You are already there.\n";
		return empty;
	}

	queue* q = new queue();			//the priority queue
	q->data.push_back(start);		//push the first town onto the queue
	start->setshortestdist(0);		//the origin has a distance of 0 from the origin
	
	intersection* currI = NULL;		//current intersection and connection 
	connection* currC = NULL;
	intersection* nextI = NULL;		//two intersections to be able to look at both ends of a connection
	int currindex, ref1, ref2;		//ref's are the index numbers of both ends of a connection

	while (!q->data.empty()) {
		currI = q->data.front();	//start with the top of the queue
		currindex = currI->getpos();
		q->data.erase(q->data.begin());	//these two commands remove the top item from the queue
		q->update();			//and then update the queue to fill in the missing spot
		currI->visit();			//marking the town being processed as visited

		for (int i=0; i<currI->getconnections().size(); i++) {		//exploring all of the connections to the current intersection
			currC = currI->getconnections()[i];
			if (iarray[currC->getstart()] == currI) {		//setting the reference numberss of the current connection
				ref1 = currC->getstart();			//to their correct values
				ref2 = currC->getend();						
			}
			else {
				ref1 = currC->getend();
				ref2 = currC->getstart();
			}							//ref1 is the intersection we're currently at
			nextI = iarray[ref2];					//ref2 is the intersection on the otherside

			if (nextI->visited())					//if the intersection was already visited move to the next connection
                continue;
			if (nextI == end) {					//if we've reached the destination intersection
				nextI->setshortestdist(currI->getshortestdist() + currC->getlen());	//update the total distance
				nextI->setprev(currC,iarray[ref1]);		//setting the current intersection we're at as the one previous to the destination
				nextI->visit();
				vector<intersection*> path;
				trace(nextI,start,path);			//tracing the final shortest path
				return path;
			}
			if (nextI->inqueue()) {		//if the intersection is already in the queue we check to see if we've found a shorter path
				if (currI->getshortestdist() + currC->getlen() < nextI->getshortestdist()) {
					nextI->setshortestdist(currI->getshortestdist() + currC->getlen());	//updating to a shorter path
					nextI->setprev(currC,iarray[ref1]);	//setting the current intersection we're at as the previous one to the next intersection
					q->update();
					q->add(nextI);				//we add the improved intersection back to the queue
				}
				continue;
			}							//now the default case of a new town to be added to the queue
			nextI->setshortestdist(currI->getshortestdist() + currC->getlen());	//update the path thus far
			nextI->setprev(currC,iarray[ref1]);			//linking the next intersection back to the one we're currently at
			q->add(nextI);						//adding the town to the queue
		}
		currI->dequeue();		//remove from queue because we're done with this intersection now
	}
	return empty;				//no path is found, perhaps between usa and alaska or hawaii
}

void userquery(List** table) {
	string query = "";
	while (true) {
		cout << "-- Enter name of town: ";
		getline(cin, query);
		if (query=="Exit" || query=="exit") exit(1);
		Link* result = search(table, query);
		if (result!=NULL) result->print();
	}
}

void adventure(List** towns, vector<intersection*> inters, vector<connection*> connects) {
	cout << "Enter a town to begin your adventure (type 'exit' to exit): ";
	string query = "";
	getline(cin, query);
	if (query=="exit" || query=="Exit") exit(1);
	Link* result = search(towns, query);
	while (result==NULL) {
		getline(cin, query);
		if (query=="exit" || query=="Exit") exit(1);
		result = search(towns, query);
	}
	int num = (result->data->getroad());			//num is the line in the intersection file that we're at
	if (inters[num]==NULL) {	
		cerr << "Town has no intersection!\n";
		return;
	}
	cout << "Your location is " << inters[num]->getlat() << "N " << inters[num]->getlon() << "E. ";
	cout << "You are " << inters[num]->gettowndist() << " mi. from" << inters[num]->gettown() << ", " << inters[num]->getstate() << ".\n";

	while (true) {
		cout << "Choose one of these roads (Type 'new' to start over):\n";
		for (int i=1; i<inters[num]->getconnections().size()+1; i++) {
			cout << i << ": " << inters[num]->getconnections()[i-1]->getroad() << " (";
			cout << inters[num]->getconnections()[i-1]->getlen() << " miles long)\n";
		}
		string choice = "";
		int x;
		getline(cin, choice);
		if (choice=="exit" || choice=="Exit") exit(1);
		if (choice=="new" || choice=="New") adventure(towns,inters,connects);
		x = atoi(choice.c_str());			//atoi returns 0 if non-int value is entered
		while (x<1 || x>=inters[num]->getconnections().size()+1 || x==0) {
			cerr << "Invalid road\n";
			getline(cin, choice);
			if (choice=="exit" || choice=="Exit") exit(1);
			x = atoi(choice.c_str());
		}

		if (inters[num]->getconnections()[x-1]->getstart() == num)	//updating to new intersection
			num = inters[num]->getconnections()[x-1]->getend();
		else num = inters[num]->getconnections()[x-1]->getstart();

		cout << "Your location is " << inters[num]->getlat() << "N " << inters[num]->getlon() << "E. ";
		cout << "You are " << inters[num]->gettowndist() << " mi. from" << inters[num]->gettown() << ", " << inters[num]->getstate() << ".\n";
	}
}			
	
state* read_boundaries(string filename) {			//reads the state outlines of a selected state
	FILE* fin = fopen(filename.c_str(), "rb");
	if (fin==NULL) {
		cerr << "Failed to open boundary file\n";
		return NULL;
	}
	fseek(fin,0,SEEK_END);
	int bytes = ftell(fin);
	fseek(fin,0,SEEK_SET);

	Descriptor* tempd = new Descriptor();
	Region* tempr = new Region();

	int x = fread(tempd, sizeof(float)+sizeof(int), 1, fin);	//the initial descriptor and
	int y = fread(tempr, 4*sizeof(float), 1, fin);			//region values of the state

	state* st = new state(tempd, tempr);	

	for (int i=0; i<st->description->number; i++) {
		Descriptor* temp = new Descriptor();			//the descriptor of each outline
		int check = fread(temp, sizeof(float)+sizeof(int), 1, fin);
		if (check == 0) {
			cerr << "Error reading in state's outline\n";
			return NULL;
		}
		st->outlines[i] = new Outline(temp);
		for (int j=0; j<st->outlines[i]->data->number; j++) {	//the points for each outline
			Point* temp2 = new Point();							
			int check2 = fread(temp2, 2*sizeof(float), 1, fin);
			if (check2 == 0) {
				cerr << "Error reading in state's point\n";
				return NULL;
			}
			st->outlines[i]->points[j] = temp2;
		}
	}
	fclose(fin);
	return st;
}

void draw_state(state* s, int width, int height) {		//draws a single state
	if (s==NULL) {
		cerr << "Invalid state\n";
		return;
	}
	set_pen_color(color::black);
	set_pen_width(1);
	int num = s->description->number;			//number of outlines
	for (int i=0; i<num; i++) {
		float initlon = (2.085*width + s->outlines[i]->points[0]->longitude*13.35);	
		float initlat = (1.667*height - s->outlines[i]->points[0]->latitude*13.35);
		move_to(initlon,initlat);			//starting the outline
		int amt = s->outlines[i]->data->number;		//number of points
		for (int j=1; j<amt; j++) {								
			float lon = (2.085*width + s->outlines[i]->points[j]->longitude*13.35);
			float lat = (1.667*height - s->outlines[i]->points[j]->latitude*13.35);
			draw_to(lon,lat);			//drawing all the points in the outline
		}
	}
}		

void draw_country(int w, int h) {
	state* AK = read_boundaries("boundaryAK.dat");	draw_state(AK,w,h);
	state* AL = read_boundaries("boundaryAL.dat");  draw_state(AL,w,h);	
	state* AR = read_boundaries("boundaryAR.dat");  draw_state(AR,w,h);
	state* AZ = read_boundaries("boundaryAZ.dat");  draw_state(AZ,w,h);
	state* CA = read_boundaries("boundaryCA.dat");  draw_state(CA,w,h);
	state* CO = read_boundaries("boundaryCO.dat");  draw_state(CO,w,h);
	state* CT = read_boundaries("boundaryCT.dat");  draw_state(CT,w,h);
	state* DC = read_boundaries("boundaryDC.dat");  draw_state(DC,w,h);
	state* DE = read_boundaries("boundaryDE.dat");  draw_state(DE,w,h);
	state* FL = read_boundaries("boundaryFL.dat");  draw_state(FL,w,h);
	state* GA = read_boundaries("boundaryGA.dat");  draw_state(GA,w,h);
	state* HI = read_boundaries("boundaryHI.dat");  draw_state(HI,w,h);
	state* IA = read_boundaries("boundaryIA.dat");  draw_state(IA,w,h);
	state* ID = read_boundaries("boundaryID.dat");  draw_state(ID,w,h);
	state* IL = read_boundaries("boundaryIL.dat");  draw_state(IL,w,h);
	state* In = read_boundaries("boundaryIN.dat");  draw_state(In,w,h);
	state* KS = read_boundaries("boundaryKS.dat");  draw_state(KS,w,h);
	state* KY = read_boundaries("boundaryKY.dat");  draw_state(KY,w,h);
	state* LA = read_boundaries("boundaryLA.dat");  draw_state(LA,w,h);
	state* MA = read_boundaries("boundaryMA.dat");  draw_state(MA,w,h);
	state* MD = read_boundaries("boundaryMD.dat");  draw_state(MD,w,h);
	state* ME = read_boundaries("boundaryME.dat");  draw_state(ME,w,h);
	state* MI = read_boundaries("boundaryMI.dat");  draw_state(MI,w,h);
	state* MN = read_boundaries("boundaryMN.dat");  draw_state(MN,w,h);
	state* MO = read_boundaries("boundaryMO.dat");  draw_state(MO,w,h);
	state* MS = read_boundaries("boundaryMS.dat");  draw_state(MS,w,h);
	state* MT = read_boundaries("boundaryMT.dat");  draw_state(MT,w,h);
	state* NC = read_boundaries("boundaryNC.dat");  draw_state(NC,w,h);
	state* ND = read_boundaries("boundaryND.dat");  draw_state(ND,w,h);
	state* NE = read_boundaries("boundaryNE.dat");  draw_state(NE,w,h);
	state* NH = read_boundaries("boundaryNH.dat");  draw_state(NH,w,h);
	state* NJ = read_boundaries("boundaryNJ.dat");  draw_state(NJ,w,h);
	state* NM = read_boundaries("boundaryNM.dat");  draw_state(NM,w,h);
	state* NV = read_boundaries("boundaryNV.dat");  draw_state(NV,w,h);
	state* NY = read_boundaries("boundaryNY.dat");  draw_state(NY,w,h);
	state* OH = read_boundaries("boundaryOH.dat");  draw_state(OH,w,h);
	state* OK = read_boundaries("boundaryOK.dat");  draw_state(OK,w,h);
	state* OR = read_boundaries("boundaryOR.dat");  draw_state(OR,w,h);
	state* PA = read_boundaries("boundaryPA.dat");  draw_state(PA,w,h);
	state* RI = read_boundaries("boundaryRI.dat");  draw_state(RI,w,h);
	state* SC = read_boundaries("boundarySC.dat");  draw_state(SC,w,h);
	state* SD = read_boundaries("boundarySD.dat");  draw_state(SD,w,h);
	state* TN = read_boundaries("boundaryTN.dat");  draw_state(TN,w,h);
	state* TX = read_boundaries("boundaryTX.dat");  draw_state(TX,w,h);
	state* US = read_boundaries("boundaryUS.dat");  draw_state(US,w,h);
	state* UT = read_boundaries("boundaryUT.dat");  draw_state(UT,w,h);
	state* VA = read_boundaries("boundaryVA.dat");  draw_state(VA,w,h);
	state* VT = read_boundaries("boundaryVT.dat");  draw_state(VT,w,h);
	state* WA = read_boundaries("boundaryWA.dat");  draw_state(WA,w,h);
	state* WI = read_boundaries("boundaryWI.dat");  draw_state(WI,w,h);
	state* WV = read_boundaries("boundaryWV.dat");  draw_state(WV,w,h);
	state* WY = read_boundaries("boundaryWY.dat");  draw_state(WY,w,h);
}		//draws all of the states

void draw_elevation(string filename, double* x, double* y, double* dpp) {	//draws an elevation file
	FILE* f = fopen(filename.c_str(), "rb");
	if (f == NULL) {
		cerr << "Failed to open elevation file\n";
		return;
	}

	ifstream fin(filename.c_str());		//using fstream to read in the first row of meta data
	if (fin.fail()) {
		cerr << "Failed to open elevation file\n";
		return;
	}

	int rows, cols, bytesperpixel, secondsperpixel, leftlonseconds, toplatseconds, min, max, specialval;
	string junk;				//reading in the the parameters of the file

	fin >> junk >> rows >> junk >> cols >> junk >> bytesperpixel >> junk >> secondsperpixel;
	fin >> junk >> leftlonseconds >> junk >> toplatseconds >> junk >> min >> junk >> max >> junk >> specialval;

	const int rowsize = cols * sizeof(short int);		//rowsize is size in bytes of one row

	short int *a = (short int*)malloc(2*(rows+1)*cols);	//allocating space to read *everything* in the file
								//we read in all the data but only access the 2nd row onwards
	int n = fread(a, rowsize, rows+1, f);			//the extra row is the dummy row at beginning
								//n is the rows successfully read
	make_window(cols,rows);
	set_pen_color(color::black);
	set_pen_width(2);
	move_to(0,0);
	for (int r=1; r<rows+1; r++) {				//starting at 1 and going to +1 accounts for the initial dummy row
		for (int c=0; c<cols; c++) {
			move_to(c,r-1);				//each row with a col number will be a coordinate on the window
			if (a[r*cols+c] == specialval) {	//if the elevation data is supposed to be water
				set_pen_color(color::blue);
				draw_point();
			}
			else {						//if the elevation data is on land
				short int e = a[r*cols+c];		//accessing the data as if it was a 2d array
				if (e<0) set_pen_color_int(204,204,0);	//different colors based on level of elevation
				else if (e>=0 && e<51) set_pen_color_int(0,255,51);		//dark green
				else if (e>50 && e<101) set_pen_color_int(0,227,51);	
				else if (e>100 && e<201) set_pen_color_int(0,205,51);
				else if (e>200 && e<351) set_pen_color_int(0,175,51);
				else if (e>350 && e<501) set_pen_color_int(0,155,51);
				else if (e>500 && e<1001) set_pen_color_int(0,125,51);	
				else if (e>1000 && e<1501) set_pen_color_int(0,100,51);		
				else if (e>1500 && e<2001) set_pen_color_int(0,75,51);		//light green
				else if (e>2000 && e<2501) set_pen_color_int(51,51,0);		//brown
				else if (e>2500 && e<3001) set_pen_color_int(101,101,101);
				else if (e>3000 && e<3501) set_pen_color_int(153,153,153);
				else if (e>3500 && e<4001) set_pen_color_int(204,204,204);	
				else if (e>4000) set_pen_color_int(255,255,255);		//white
				else { set_pen_color_int(0,255,51); cout << "Exception\n"; }	//this should never happen
				draw_point();
			}
		}
	}
	fclose(f);
	fin.close();
	*x = leftlonseconds/3600;			//will essentially "return" the lat/lon coordinates
	*y = toplatseconds/3600;			//for the top left corner of the elevation map and the
	*dpp = (double)secondsperpixel/3600;		//degreesperpixel for scaling the window's coordinates

	if (filename == "usaW125N50D60.dat")		//draws the state outlines for this one particular "default" file
		draw_country(cols,rows);
}

efile** read_coverage() {				//reads the coverage file
	ifstream f("coverage.txt");
	if (f.fail()) {
		cerr << "Error opening coverage file.\n";
		return NULL;
	}
	efile** data = new efile* [149];		//There are 149 total elevation map files
	int maxla, minla, maxlo, minlo;
	string fname;
	for (int i=0; i<149; i++) {
		f >> maxla >> minla >> minlo >> maxlo >> fname;
		data[i] = new efile(maxla,minla,maxlo,minlo,fname);
	}
	f.close();
	return data;
}

void plot_location(Link* town, double topleftX, double topleftY, double degreesperpixel) {
	location* place = town->data;
	double xcoord = (topleftX - place->getlon())/(-degreesperpixel);
	double ycoord = (topleftY - place->getlat())/(degreesperpixel);
	move_to(xcoord,ycoord);
	set_pen_width(10);				
	set_pen_color(color::red);
	draw_point();					//plotting the town's point
	set_font("arial", 20);				//and labelling it
	set_pen_color(color::white);
	write_string(place->gettowncaps(),direction::north_west,false);
}

void plot_path(vector<intersection*> path, List** towns, location* d, location* o, double topleftX, double topleftY, double degreesperpixel) {
				//initx and inity are lat and lon of the top left corner of the window
				//degreesperpixel is to scale the window's coordinates
				//d and o let me draw to the destination and origin *location* as well as their intersection
	double initx = (topleftX - d->getlon())/(-degreesperpixel);
	double inity = (topleftY - d->getlat())/(degreesperpixel);
	move_to(initx,inity);				//the initial point is the destination location
	set_pen_width(10);
	set_pen_color(color::red);
	draw_point();					//drawing a point at the destination location on map

	set_pen_width(2);
	set_pen_color(color::red);
	intersection* curr = path.front();
	while (curr != NULL) {				//working backwards through the vector to draw the path from the destination to the origin
		double x = (topleftX - curr->getlon())/(-degreesperpixel);
		double y = (topleftY - curr->getlat())/(degreesperpixel);
		draw_to(x, y);
		curr = curr->getprevinter();
	}

	double finalx = (topleftX - o->getlon())/(-degreesperpixel);
	double finaly = (topleftY - o->getlat())/(degreesperpixel);
	draw_to(finalx, finaly);			//the final point is the origin location
	set_pen_width(10);
	set_pen_color(color::red);
	draw_point();					//drawing a point at the origin location on map
	set_font("arial", 20);				//and labelling it
	set_pen_color(color::white);
	write_string(o->gettowncaps(),direction::north_west,false);
	
	move_to(initx,inity);				//Labelling the destination
	write_string(d->gettowncaps(),direction::north_west,false);
}

string choose_map(location* o, location* d) {		//o is the origin location and d is the destination
	efile** coverage = read_coverage();
	vector<efile*> possibilities;			//this array used later when finding the maps that fit the criteria
	double maxlon, minlon, maxlat, minlat;
	if (o->getlon() >= d->getlon()) {		//finding the max/min lat/lon of the two towns
		maxlon = o->getlon();
		minlon = d->getlon(); }
	else {
		maxlon = d->getlon();
		minlon = o->getlon(); }
	if (o->getlat() >= d->getlat()) {
		maxlat = o->getlat();
		minlat = d->getlat(); }
	else {
		maxlat = d->getlat();
		minlat = o->getlat(); }

	for (int i=0; i<149; i++) {			//finding the map files that will fit the two towns in them
		if (coverage[i]->maxlat >= maxlat && coverage[i]->maxlon >= maxlon && coverage[i]->minlat <= minlat && coverage[i]->minlon <= minlon)
			possibilities.push_back(coverage[i]);
	}
	if (possibilities.empty()) return "";		//if no appropriate maps are found
	efile* best = possibilities[0];	
	int smallestdegree = possibilities[0]->maxlon - possibilities[0]->minlon;
	for (int i=1; i<possibilities.size(); i++) {	//now we search through the possibilities to find the one with the smallest degrees
		int degree = possibilities[i]->maxlon - possibilities[i]->minlon;
		if (degree <= smallestdegree) {		//the map with the smallest degrees will be the most "zoomed in" map
			best = possibilities[i];
			smallestdegree = degree;
		}
	}
	if (best != NULL) return best->filename;
	else return "";					//if no appropriate map is found
}

void mapquest(List** hashtable, vector<intersection*> interarray, vector<connection*> connectarray) {
	double lon, lat, degreesperpixel;
	string defawlt = "usaW125N50D60.dat";			//the initial map loaded and the default if no smaller map is found
	draw_elevation(defawlt, &lon, &lat, &degreesperpixel);	//the initial map drawn before user enters towns
	
	string start, end;
	Link *origin = NULL, *destination = NULL;
	cout << "\n-- Enter current location: ";
	while (origin == NULL) {
		getline(cin, start);
		origin = search(hashtable, start);		//the starting town
		if (origin!=NULL) {
			origin->print();				//printing the town's info and plotting it
			plot_location(origin,lon,lat,degreesperpixel);	//on the map instantly
	} }	
	cout << "\n-- Enter destination: ";
	while (destination == NULL) {
		getline(cin, end);
		destination = search(hashtable, end);		//the end town
		if (destination!=NULL) {
			destination->print();			//printing the town's info and plotting it
			plot_location(destination,lon,lat,degreesperpixel);
	} }

	int startref = origin->data->getroad();			//used to access the intersections of both towns
	int endref = destination->data->getroad();

	string filename = choose_map(origin->data,destination->data);	//finding a higher resolution map
	
	cout << "\nCalculating...\n";

	vector<intersection*> shortestpath;			//finding the shortest path
	shortestpath = navigate(interarray[startref],interarray[endref],interarray,connectarray);
	if (shortestpath.empty()) {				//this case is probably going from alaska/hawaii to continental usa
		cerr << "No path found.\n";
		return;
	}
									
	if (filename != "" && filename != defawlt) { 		//changing the window to the higher resolution map
		hide_window();
		draw_elevation(filename, &lon, &lat, &degreesperpixel);
	}

	cout << "Destination reached in " << shortestpath[0]->getshortestdist() << " miles.\n";		//printing the total distance between the points
	plot_path(shortestpath,hashtable,destination->data,origin->data,lon,lat,degreesperpixel);	//drawing the path data on the map
}

void main() {
	cout << "Loading towns...\n";
	List** hashtable = new List* [tabsize];		//creating the hashtable
	for (int i=0; i<tabsize; i++)			//initializing all Lists in table to NULL
		hashtable[i] = new List();

	vector<intersection*> interarray;
	vector<connection*> connectarray;
	
	read_file("named-places.txt", hashtable);	//reading the location/intersection/connection files		
	cout << "Loading intersections...\n";
	read_inter("intersections.txt", interarray);	
	cout << "Loading connections...\n";
	read_connect("connections.txt", connectarray, interarray);	

	mapquest(hashtable,interarray,connectarray);	//the main work is done here
}