A4

#include <cstdlib>
#include <iostream>
#include <string>
#include <fstream>
#include <iostream>
#include <vector>

using namespace std;

class BstNode {

public:
	int key, search_cost;
	BstNode *left, *right;
	BstNode(int k=0, int sc=0, BstNode *l = NULL, BstNode *r = NULL)
	  : key(k), search_cost(sc), left(l), right(r) {}
};

BstNode* Insert(BstNode* root, int key, int sc=1) {
	if (root == NULL) { //empty tree
		root = new BstNode(key, sc);
	}
	else if(key <= root->key) {
		sc++;
		root->left = Insert(root->left, key, sc);
	}
	else {
		sc++;
		root->right = Insert(root->right, key, sc);
	}
	return root;
}

void preOrderTrav(BstNode* root, vector<BstNode*>& output) { //Performs a Pre-Order Traversal of a tree, outputting it to a vector.
	output.push_back(root);
	if (root->left != NULL) {
		preOrderTrav(root->left, output);
	}
	if (root->right != NULL) {
		preOrderTrav(root->right, output);
	}
}

void inOrderTrav(BstNode* root, vector<BstNode*>& output) {  //Performs an In-Order Traversal of a tree, outputting it to a vector.
	if (root->left != NULL) {
		inOrderTrav(root->left, output);
	}
	output.push_back(root);
	if (root->right != NULL) {
		inOrderTrav(root->right, output);
	}
}

void postOrderTrav(BstNode* root, vector<BstNode*>& output) { //Performs a Post-Order Traversal of a tree, outputting it to a vector.
	if (root->left != NULL) {
		postOrderTrav(root->left, output);
	}
	if (root->right != NULL) {
		postOrderTrav(root->right, output);
	}
	output.push_back(root);
}

vector<int> getInput(string filename) {
	string line;
	vector<int> lines;
	ifstream inputFile(filename);
	if (inputFile.is_open()) {
		while (getline(inputFile, line)) {
			lines.push_back(stoi(line));
		}
	}
	else {
		cout << "There was an error opening this file, please try again.\n";
	}
	inputFile.close();
	return lines;
}

string printTrav(vector<BstNode*> input) { //Because of how my traversal output to a vector, this function just makes outputting them easier.
	string output = "";
	for (int i=0; i < input.size(); i++) {
		output.append(to_string(input[i]->key));
		output.append("[");
		output.append(to_string(input[i]->search_cost));
		output.append("] ");
	}
	output.append("\n");
	return output;
}

float avgSearchCost(BstNode* root) {
	vector<BstNode*> node_vec; //to get the search cost, stores the nodes in a vector then adds up the search cost of each.
	int tSC=0; //the total search cost of the tree is stored here.
	
	inOrderTrav(root, node_vec);
	for (int i=0; i<node_vec.size(); i++) {
		tSC += node_vec[i]->search_cost;
	}
	
	float avgSC = (float)(tSC)/(float)(node_vec.size()); //average search cost = total search cost / number of nodes.
	return avgSC;
}

void levelVecs(BstNode* node, vector<vector<string> > &v) {
	int level = node->search_cost - 1;
	if (node == NULL) {
		v[level].push_back("x");
	}
	else if (node->left == NULL && node->right == NULL) {
		v[level].push_back(to_string(node->key));
	}
	else {
		v[level].push_back(to_string(node->key));
		levelVecs(node->left, v);
		levelVecs(node->right, v);
	}
}
	
void levelPrint(vector<vector<string>> v) {
	for (int i=0; i < v.size(); i++) {
		for (int j=0; j < v[i].size(); j++) {
			cout << v[i][j];
		}
		cout << '\n';
	}
}
	
	
	

void infoOut(string filename) { //1 function to run outputs for each input file.
	BstNode* root = NULL;
	
	vector<int> input = getInput(filename); //gets the inputs from the file.
	
	for(int i=0; i < input.size(); i++) {  //Creates the BST from the input data.
		root = Insert(root, input[i]);
	}
	
	vector<BstNode*> inOrderVec, preOrderVec, postOrderVec; //creates vectors of nodes based on each traversal type.
	inOrderTrav(root, inOrderVec);
	preOrderTrav(root, preOrderVec);
	postOrderTrav(root, postOrderVec);

	if (input.size() < 16) { //if # of nodes < 16 outputs the traversals to screen, else outputs them to a file.
		cout << "In-Order Traversal: ";
		cout << printTrav(inOrderVec);
		cout << "\nPre-Order Traversal: ";  //Could be condensed to one cout, but for easier understanding leaving it seperated.
		cout << printTrav(preOrderVec);
		cout << "\nPost-Order Traversal: ";
		cout << printTrav(postOrderVec);
	}
	
	else {
		cout << "Writing Traversal Outputs to a file named: " << filename.append("_travs") << '\n';
		ofstream trav_file (filename.append("_travs")); //creates a new file called <filename>_travs where traversals can be seen.
		if (trav_file.is_open()) {
			trav_file << "In-Order Traversal: ";
			trav_file << printTrav(inOrderVec);
			trav_file << "\nPre-Order Traversal: ";
			trav_file << printTrav(preOrderVec);
			trav_file << "\nPost-Order Traversal: ";
		    trav_file << printTrav(postOrderVec);
			trav_file.close();
		}
	}
	
	vector<vector<string>> v;
	levelVecs(root, v);
	cout << "ran levelVecs\n";
	levelPrint(v);
	//cout << "\nTotal number of nodes is " << input.size();	
	//cout << "\nAverage Search Cost: " << avgSearchCost(root) << '\n'; //outputs the average search cost to screen.
	
}

int main() {
	
	vector<string> p_files = {"1p","2p","3p","4p","5p","6p","7p","8p","9p","10p","11p","12p"};
	vector<string> l_files = {"1l","2l","3l","4l","5l","6l","7l","8l","9l","10l","11l","12l"}; //all of the files that need to be ran.
	vector<string> r_files = {"1r","2r","3r","4r","5r","6r","7r","8r","9r","10r","11r","12r"};
	
	string File;
	cout << "Enter an input file to analyze, or type 'all' to analyze all of the provided files: ";
	getline(cin, File);
	if (File == "all") { //outputs every test file provided for this assignment.
		cout << "Perfect Binary Tree Files:  \n\n";
		for (int i=0; i < 12; i++) {
			infoOut(p_files[i]);
		}
		cout << "Random Binary Tree Files:  \n\n";
		for (int i=0; i < 12; i++) {
			infoOut(r_files[i]);
		}
		cout << "Linear Binary Tree Files:  \n\n";
		for (int i=0; i < 12; i++) {
			infoOut(l_files[i]);
		}
	}
	else {
		infoOut(File);
	}
	
}