/*
 
Assignment #3 - CMPT 225 - 1071 - Angelina Fabbro (amf3@sfu.ca)

Overview: Main Program File Invokes functions to use a basic hash table

*/


#include <vector>

#include <string>

#include <algorithm>

#include <sstream>

#include <cstdio>

#include <cctype>

using namespace std;



#define UNKNOWN_COMMAND -1

#define EMPTY_INPUT 0

#define HELP 1

#define VERBOSE 2

#define NEW 3

#define INSERT 4

#define LOAD 5

#define FIND 6

#define OUT 7

#define QUIT 8

void show_help();

void set_verbose(const vector<string> &a);

vector<string> get_input();

int parse_input(vector<string> a);

void init_table();

void new_table(const vector<string> &a);

void insert(string s);
void delete(string s);

void find(string s);

void load(const string &name);

void out(const vector<string> &a);




int main() {

	init_table(); // creates empty table of size 31

	show_help();

	bool flag = true; // exit, when flag == false 

	while(flag) { // main loop

		vector<string> in = get_input(); // read input and split it into words

		int v = parse_input(in); // parse input

		switch(v) {

			case HELP:

				show_help(); 

				break;

			case VERBOSE:

				set_verbose(in);

				break;

			case NEW:

				new_table(in); // clears and creates a new table

				break;

			case INSERT:

				insert(in[1]); // inserts a new word in table

				break;
			case DELETE:

				insert(in[1]); // Finds and deletes a word in table

				break;

			case LOAD:

				load(in[1]); // loads words from file

				break;

			case FIND:

				find(in[1]); // searches word in table

				break;

			case OUT:

				out(in); // output current table state

				break;

			case QUIT:

				flag = false; 

				break;

		}

	}

	return 0;

}



vector<string> get_input() {

	char buf[1024];

	printf("> "); // prompt

	gets(buf);

	string s(buf);

	stringstream u(s); // we use stringstream to split s into words

	vector<string> in;

	while(u && !u.eof()) {

		string t;

		u >> t;

		in.push_back(t);

	}

	return in; // returns vector of splitted input

}



int parse_input(vector<string> a) {

	if(a.size() < 0) return EMPTY_INPUT;

	// convert to lowercase

	for(unsigned i = 0; i < a[0].size(); ++i) 

		a[0][i] = tolower(a[0][i]);

	// commands with condition (a.size() > 1) require 2nd parameter

	if(a[0] == "help" || a[0] == "h" || a[0] == "?") return HELP;

	if(a[0] == "verbose" || a[0] == "v") return VERBOSE;

	if(a[0] == "new" || a[0] == "n") return NEW;

	if(a[0] == "insert" || a[0] == "i" && a.size() > 1) return INSERT;
	if(a[0] == "delete" || a[0] == "d" && a.size() > 1) return DELETE;

	if(a[0] == "load" || a[0] == "l" && a.size() > 1) return LOAD;

	if(a[0] == "find" || a[0] == "f" && a.size() > 1) return FIND;

	if(a[0] == "out" || a[0] == "o") return OUT;

	if(a[0] == "quit" || a[0] == "q") return QUIT;

	return UNKNOWN_COMMAND;

}



void init_table() {

	// create stub for new_table()

	vector<string> in;

	in.push_back("");

	in.push_back("31"); // pass 31 as 2nd parameter

	new_table(in);

}



struct TableElem {

	int hash_value;

	string value;

	bool trunc; // true, if value was truncated

	// simple constructor

	TableElem(int hv, const string &v, bool tr) : hash_value(hv), value(v), trunc(tr) {}

};



// table global variables

int tab_size; // size of table

int tab_free; // amount of empty cells in table

vector<TableElem> table; 

int verb = 1; // verbose level



void new_table(const vector<string> &a) {	

	if(a.size() < 2) tab_size = 31;

	else sscanf(a[1].c_str(),"%d",&tab_size);

	tab_free = tab_size;

	table.clear();

	table.resize(tab_size,TableElem(0,"",false)); 

	// creates new table of current tab_size elements

	// and fill it by TableElem(0,"",false)

}



int hash_function(const string &s) {

	// simple polynomial hash function

	// you can change it if you want

	// it should always return answers in range 0..(tab_size-1)

	int x = 0;

	for(unsigned i = 0; i < s.size(); ++i)

		x = (x*137 + s[i]) % tab_size;

	// let's denote N == s.size()

	// this calculates polynomial s[0]*137^(N-1) + s[1]*137^(N-1) + .. + s[N-1]

	// modulo tab_size

	return x;

}



void insert(string s) {

	bool tr = false; // truncate flag

	if(s.size() > 15) {

		s = s.substr(0,15); // substring of first 15 characters

		tr = true;

	}



	if(tab_free == 0) { // check, if we have empty space in table

		printf("Table is full! Impossible to insert.\n");

		return;

	}



	// here the main algorithm starts !!!

	int hv = hash_function(s); // calculate hash value of s

	int p = hv; // index of position, in wich we are trying to insert s

	int probe_count = 0;

	while(!table[p].value.empty()) { // empty strings denote empty positions

		++probe_count;

		// unsuccessful probe - position is occupied

		if(table[p].hash_value == hv) { // first, we compare hash values

			// it they equals, we have to check whole values

			if(table[p].value == s) {

				// we have found s - it's already in table

				if(verb) {

					printf("String \"%s\" already in table!\n",s.c_str());

					printf("Position found in %d probes\n",probe_count);

				}

				return;

			}

		}

		// go to next position (0 follows after (tab_size-1), cyclically)

		p = (p + 1) % tab_size;

	}

	++probe_count;

	// now p is index of first empty position

	// in table, starting from hv



	// store s in table:

	table[p].hash_value = hv;

	table[p].value = s;

	table[p].trunc = tr;

	--tab_free; // decrease amound of free positions

	if(verb) {

		printf("String \"%s\" inserted successfully!\n",s.c_str());

		printf("Position found in %d probes\n",probe_count);

	}

}



void find(string s) {

	if(s.size() > 15) {

		s = s.substr(0,15); // substring of first 15 characters

	}



	// here the main algorithm starts !!!

	int hv = hash_function(s); // calculate hash value of s

	int p = hv; // index of position, in wich we are trying to insert s

	int probe_count = 0;



	// searching for s in table

	while(probe_count < tab_size) { // to avoid infinite loopm, when table is full

		++probe_count;

		 // first, we compare hash values

		if(table[p].value.empty()) {

			// we have found empty cell

			// this means, that s was not found

			break;

		}

		if(table[p].hash_value == hv) {

			// then, we have to compare whole values

			if(table[p].value == s) {

				printf("String \"%s\" was found in %d probes!\n",s.c_str(),probe_count);

				return;

			}

		}		

		// go to next position (0 follows after (tab_size-1), cyclically)

		p = (p + 1) % tab_size;

	}

	printf("String \"%s\" was not found! %d probes was made\n",s.c_str(),probe_count);

}

void delete(string s) {

	if(s.size() > 15) {

		s = s.substr(0,15); // substring of first 15 characters

	}



	// here the main algorithm starts !!!

	int hv = hash_function(s); // calculate hash value of s

	int p = hv; // index of position, in wich we are trying to insert s

	int probe_count = 0;



	// searching for s in table

	while(probe_count < tab_size) { // to avoid infinite loopm, when table is full

		++probe_count;

		 // first, we compare hash values

		if(table[p].value.empty()) {

			// we have found empty cell

			// this means, that s was not found

	

			break;

		}

		if(table[p].hash_value == hv) {

			// then, we have to compare whole values

			if(table[p].value == s) {

				printf("String \"%s\" was found in %d probes!\n",s.c_str(),probe_count);
				printf("Deleting string...");
				table[p].value = 0;
				printf("Dump table to file or console to verify string removal.");

				return;

			}

		}		

		// go to next position (0 follows after (tab_size-1), cyclically)

		p = (p + 1) % tab_size;

	}

	printf("String \"%s\" was not found! %d probes was made\n",s.c_str(),probe_count);

}


void load(const string &name) {

	// name if filename of file to read from

	char buf[1024];

	FILE * fin = fopen(name.c_str(),"r");

	if(fin) {

		fscanf(fin," "); // read empty space

		while(!feof(fin)) {

			fscanf(fin,"%s ",buf);

			if(strlen(buf) > 0) insert(string(buf)); 

			// conditional to avoid inserting empty strings

		}

		fclose(fin);

		if(verb) printf("Strings loaded from file %s successfully!\n",name.c_str());

	}

	else printf("Unable to open file %s\n",name.c_str());

}



void out(const vector<string> &a) {

	char t2s[2][2] = {" ","T"};

	// t[trunc] is string, representating trunceting status

	// if trunc == 0, it's blanc

	// if trunc == 1, it's "T" string



	if(a.size() > 1) {

		// we have 2nd parameter

		// out to file

		FILE * fout = fopen(a[1].c_str(),"w");

		if(fout) {

			for(int i = 0; i < tab_size; ++i) {

				if(!table[i].value.empty())

					fprintf(fout,"%5d %5d %20s %s\n",i,table[i].hash_value,table[i].value.c_str(),

					t2s[(int)table[i].trunc]);

				else

					fprintf(fout,"%5d\n",i);

			}

			fclose(fout);

			printf("Saved to file \"%s\" successfully\n");

		}

		else printf("Unable to open file %s\n",a[1].c_str());

	}

	else {

		// we have less than 2 parametrs - 

		// out to console

		for(int i = 0; i < tab_size; ++i) {

			if(!table[i].value.empty())

				printf("%5d %5d %20s %s\n",i,table[i].hash_value,table[i].value.c_str(),

				t2s[(int)table[i].trunc]);

			else

				printf("%5d\n",i);

		}

	}

}



void show_help() {

	printf("Commands:\n\n");

	printf("  help or ? - this message\n");

	printf("  verbose [on|off] - set verbose level (enter empty param to view)\n");

	printf("  new [size] - creates new empty table; size can be specified (31 by defaulf)\n");

	printf("  insert <string> - inserts new string in table\n");

	printf("  load <filename> - loads strings in table from specified file\n");

	printf("  find <string> - searches for string in table\n");

	printf("  out [filename] - output current table state to file; if empty - to console\n");

	printf("  quit - finishes work\n\n");

	printf("You can use short names for commands - h,v,n,i,l,f,o,q\n\n");

}



void set_verbose(const vector<string> &a) 
{

	// set and show verbose level

	char diag[2][10] = {"off","on"};

	if(a.size() > 1) 
	{

		if(a[1] == "on") verb = 1;

		else if(a[1] == "off") verb = 0;

	}

	printf("Verbose level is \"%s\" now\n",diag[verb]);

}