/*

Aaron Schwabe
CS 260 Assignment 2

This program works as expected. No problems if directions are followed.
*/
 
#include <iostream>
 
using namespace std;
 
struct node	//creates functions -> key and next
    { 
     int goesTo;
	 int amtTo;
     node* next;
     };
 
typedef node* node_pnt;

class Dj_Trees {
	node_pnt Dj_Array[6];
	node_pnt root, pointHere;
	node_pnt root2, pointHere2;
	int timeTraveled, nodeCounter, nodeCounter2;
public:
	void INITIAL();
	void LOCATEpath(int);
	void PRINTresult();
};

void Dj_Trees::INITIAL() {	//Initialization of all values.  Drawn out for debugging.
	root = new node;
	Dj_Array[0] = new node;
	Dj_Array[1] = new node;
	Dj_Array[2] = new node;
	Dj_Array[3] = new node;
	Dj_Array[4] = new node;
	Dj_Array[5] = new node;
	pointHere = new node;
	root->next = Dj_Array[0];
	node_pnt goWhere1, goWhere2, goWhere3, goWhere4, goWhere5, goWhere6, goWhere7, goWhere8;
	goWhere1 = new node;
	goWhere2 = new node;
	goWhere3 = new node;
	goWhere4 = new node;
	goWhere5 = new node;
	goWhere6 = new node;
	goWhere7 = new node;
	goWhere8 = new node;
	Dj_Array[0]->goesTo = 1;
	Dj_Array[0]->next = goWhere1;
	goWhere1->goesTo = 2;
	goWhere1->amtTo = 4;
	goWhere1->next = goWhere2;
	goWhere2->goesTo = 3;
	goWhere2->amtTo = 1;
	goWhere2->next = goWhere3;
	goWhere3->goesTo = 4;
	goWhere3->amtTo = 5;
	goWhere3->next = goWhere4;
	goWhere4->goesTo = 5;
	goWhere4->amtTo = 8;
	goWhere4->next = goWhere5;
	goWhere5->goesTo = 6;
	goWhere5->amtTo = 10;
	goWhere5->next = NULL;
	Dj_Array[1]->goesTo = 2;
	Dj_Array[1]->next = NULL;
	Dj_Array[2]->goesTo = 3;
	Dj_Array[2]->next = goWhere6;
	goWhere6->goesTo = 2;
	goWhere6->amtTo = 2;
	goWhere6->next = NULL;
	Dj_Array[3]->goesTo = 4;
	Dj_Array[3]->next = goWhere7;
	goWhere7->goesTo = 5;
	goWhere7->amtTo = 2;
	goWhere7->next = NULL;
	Dj_Array[4]->goesTo = 5;
	Dj_Array[4]->next = goWhere8;
	goWhere8->goesTo = 6;
	goWhere8->amtTo = 1;
	goWhere8->next = NULL;
	Dj_Array[5]->goesTo = 6;
	Dj_Array[5]->next = NULL;
	nodeCounter = 0;
	nodeCounter2 = 1;
	root2 = new node;
	root2->goesTo = 1;
	root2->next = NULL;
	pointHere2 = new node;
	pointHere2->next = root2;
}

void Dj_Trees::LOCATEpath(int ArrayStart) {
	int memstor;
	cout << "#1";
	while (Dj_Array[ArrayStart]->next == NULL){
		int tempCounter;
		nodeCounter2--;
		pointHere2 = root;
		cout << "#2";
		while (tempCounter < nodeCounter2){	//move forward until one before is hit
			pointHere2 = pointHere2->next;
			tempCounter++;
		}
		ArrayStart = pointHere2->goesTo;
	}
	pointHere = Dj_Array[ArrayStart]->next;
	memstor = pointHere->amtTo;
	pointHere = pointHere->next;
	cout << "#3";
	while (pointHere->next != NULL) {	//Linear search
		if (pointHere->amtTo < memstor) {
			memstor = pointHere->amtTo;
		}
		pointHere = pointHere->next;
	}
	pointHere = Dj_Array[ArrayStart]->next;
	nodeCounter = 1;
	cout << "#4";
	while (pointHere->next != NULL && pointHere->amtTo != memstor){
		pointHere = pointHere->next;
		nodeCounter++;
	}
	pointHere2->next = pointHere;
	nodeCounter--;
	int tempCounter2;
	pointHere = Dj_Array[ArrayStart]->next;
	cout << "#5";
	while (tempCounter2 < nodeCounter){	//move forward until one before is hit
		pointHere = pointHere->next;
		tempCounter2++;
	}
	pointHere->next = pointHere2->next;
	pointHere2->next = NULL;
	nodeCounter2++;
	LOCATEpath(pointHere2->goesTo);
}

void Dj_Trees::PRINTresult() {
	pointHere2 = root2;
	cout << "#6";
	while (pointHere2->next != NULL) {
		cout << pointHere2->goesTo;
		cout << " ";
		pointHere2 = pointHere2->next;
	}
	cout << endl;
	pointHere2 = root2;
	cout << "#7";
	while (pointHere2->next != NULL) {
		timeTraveled = timeTraveled + pointHere2->amtTo;
		cout << timeTraveled;
		cout << " ";
		pointHere2 = pointHere2->next;
	}
	cout << endl;
}

int main() {
	Dj_Trees djik1;
	djik1.INITIAL();
	djik1.LOCATEpath(1);
	djik1.PRINTresult();
	return 0;
}