/*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 8void 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 variablesint tab_size; // size of tableint tab_free; // amount of empty cells in tablevector<TableElem> table; int verb = 1; // verbose levelvoid 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]);}