#pragma once

#include <iostream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <queue>
using namespace std;


class directedGraph
{
private:
	class vertex
	{
	public:
		string data;
		vector<vertex*> neighbors;

		//bfs variables
		bool marked;
		vertex* breadCrumb;

		vertex(string s)
		{
			data = s;
			marked = false;
			breadCrumb = nullptr;
		}
	};

	//container/data structure to hold all vertices
	unordered_map<string,vertex*> vertexMap;

	void clearData()
	{
		for (auto x : vertexMap)
		{
			x.second->marked =false;
			x.second->breadCrumb = nullptr;
		}
	}

	void breadthFirstSearch(vertex* s)
	{
		//setup, variables
		clearData();
		queue<vertex*> Q;

		//step 0: mark s, put s into Q
		s->marked = true;
		Q.push(s);

		//step 1: Enter BFS loop
		while (!Q.empty())
		{
			//step 1.1: get item x from Q
			vertex* x = Q.front();
			Q.pop();

			//step 1.2: visit all of x's unvisited neighbors
			for (auto y : x->neighbors)
			{
				if (!y->marked)
				{
					y->marked = true;
					Q.push(y);

					//augment
					y->breadCrumb = x;
				}
			}
		}

	}

public:
	//Add a vertex to the graph
	//run time: O(1) a.c.
	void addVertex(string s)
	{
		vertexMap[s] = new vertex(s);
	}

	//Add a directed edge from a to b
	//run time: O(1) a.c.
	void addDirectedEdge(string a, string b)
	{
		vertex* aptr = vertexMap[a]; //O(1) a.c.
		vertex* bptr = vertexMap[b]; //O(1) a.c.

		aptr->neighbors.push_back(bptr); //O(1)
	}

	//Add a bidirectional edge between a and b
	//run time:
	void addBasicEdge(string a, string b)
	{
		addDirectedEdge(a, b);
		addDirectedEdge(b, a);
	}

	//Compute shortest path from start to end
	//return path in string form.
	string shortestPath(string start, string end)
	{
		//Step 0: Get the start/end vertices
		vertex* sPtr = vertexMap[start];
		vertex* ePtr = vertexMap[end];

		//Step 1: Run BFS on start vertex
		//to properly set breadcrumbs poineters
		//encoding shortest paths.
		breadthFirstSearch(sPtr);

		//Step 2: Start at ePtr, following breadcrumbs
		//back to sPtr, return path of vertices you
		//visit.
		string output;

		vertex* current = ePtr;
		while (current != nullptr)
		{
			output = current->data + ", " + output;
			current = current->breadCrumb;
		}
		//output = current->data + ", " + output;

		return output;

	}

	void testDisplay()
	{
		for (auto x : vertexMap)
		{
			cout << x.first << " : ";
			//now list neighbors of x
			for (auto y : x.second->neighbors)
			{
				cout << y->data << ", ";
			}
			cout << endl;
		}
	}

};