In this long project, you are going to implement a word search engine using C++ and binary tree. The search engine would help users to count number of occurrence of a word among given set of text files and also sort all the words.

The input files are alreay given.

Upon execution, the program should load all the words from the input files in the memory. The program has two modes:

Mode 1: Word search

In this mode the program should run until the user explicitly specifies exit. The following functionality should be supported:

1. Count how many times a user-specified word appears in the files.

2. Display the name of input files and corresponding number of occurrences of the specified word.

3. Provide some stochastics such as: Total number of occurrences of the specified word (wordTotal) Total number of files that contain the word (fileTotal) Average number of occurrences of the specified word per file (Average)

Mode 2: Word Sorting

In this mode the program should ask user to input the number of words and then print the existing words in all the input file in alphabetic order up to the input number. Upon execution of you program, you should specify as input parameter the path to a directory containing the input files.

Implementation requirements: First, you need to implement a class for an abstract data type, in which you are going to store files in memory. This step is very specific, depending on the functionality of the program you are developing. For the current implementation you are required to use Binary Tree.

You need to declare a class Word that would store a word, those properties and pointers and another class File that would store a file-name and number of times that the word occurred in this file. The process of loading files in the memory consists of (i) creating an object of type Word for each new word that occurs in the set of input files, (ii) appending this object to a binary tree and update stochastics , (iii) creating an object File for each occurrence of the word in a file and (iv) updating the corresponding (blue) linked list with the object File. Once you have the files loaded in such structure, the searching would be as easy as finding the queried word in the green binary tree and tracing in which files it occurs by going over the corresponding blue linked list.

You are required to split different aspects of this program and implement them in separate files. Then you will have to put them all back together to achieve the program functionality. You will need to create several .h and .cpp files for this project.

First you need to identify the important object-types and methods you will need for your implementation. In this project, your main object types are going to be class Word and class File. You can reuse your classes for File list. As before, create a file called itemtype.h and declare class File in it. Then create another file called itemtype.cpp and define your class File in it. These two files are going to be related to objects from the blue lists on the picture.

The next step is to implement the functionality for creating the blue lists. For this purpose, you need to create two more files list.h and list.cpp. In list.h declare all the methods needed for building a blue list and in list.cpp define these methods. Now, you need to implement the functionality related to objects like these in the green binary tree which is different from the first project.

Create two more files word.h and word.cpp, declare class Word and all methods to this class in word.h and define them in word.cpp. Now what's left is to put it all together by writing a main function that utilizes both file and word. To do so, create wordsearch.h and wordsearch.cpp, declare your main function in wordsearch.h and define it in wordsearch.cpp.

So all in all you will need eight files: wordsearch.h, wordsearch.cpp, itemtype.h, itemtype.cpp, list.h, list.cpp, word.h, word.cpp.

However I have everything but wordsearch.cpp and wordsearch.h included here.

itemtype.cpp

#ifndef ITEMTYPE #define ITEMTYPE #include "itemtype.h" file* file::getNext(){ return this->next; } int file::getCount(){ return this->count; } string file::getfilename(){ return filename; } void file::setNext(file* next){ this->next = next; } void file::incrementCount(){ count++; } #endif

itemtype.h

#ifndef FILE #define FILE #include using namespace std;

class file { public: file(string filename = "", file* next = NULL){ this->filename = filename; this->count = 1; this->next = next; } file* getNext(); int getCount();

//Function to add +1 to the counter every time the word is repeated in a document. void incrementCount(); //Function that returns the name of the specified file. string getfilename(); //Function to set the next pointer node. void setNext(file* next); private: file* next; string filename; int count; }; #endif

list.cpp

#include "list.h" #include using namespace std; list::list(file* head_ptr){ this->head_ptr = head_ptr; } void list::print(){ file* current = head_ptr; while(current != NULL){ int count = current-> getCount(); string filename = current->getfilename(); if(current->getNext() == NULL && current != head_ptr){ cout << "and "; } if(count == 1){ cout << count << " time in " << filename; } else{ cout << count << " times in " << filename; } if(current->getNext() != NULL){ cout<<", "; } else{ cout<<"."; } current = current->getNext(); } cout << endl; } void list::createFront(string docname){ file* insert = new file(docname,head_ptr); head_ptr = insert; }

void list::insert(string docname){ file* current = head_ptr; bool found = false; while(current != NULL && !found){ if(current->getfilename() == docname){ current->incrementCount(); found = true; } current = current -> getNext(); } if(!found){ createFront(docname); }

}

list.h

#ifndef LIST #define LIST #include "itemtype.h" class list{ public: list(file* head_ptr = NULL);

//Function to insert a document into linked list. void insert(string docname);

//Function to insert document into linked list if document not already in list. void createFront(string docname);

//Function to print all items in the list void print();

//Function to return the head of the list file* returnHead(){ return head_ptr; } private: file* head_ptr; }; #endif

word.cpp

#include "word.h" #include #include #include using namespace std;

word::word(string wordparam, word* left_ptr, word* right_ptr){ this->wordparam = wordparam; this->left_ptr = left_ptr; this->right_ptr = right_ptr; this->files = new list(); }

void word::setRight(word* right_ptr){ this->right_ptr = right_ptr; }

void word::setLeft(word* left_ptr){ this->left_ptr = left_ptr; }

string word::getWord(){ return wordparam; }

word* word::getRight(){ return right_ptr; }

word* word::getLeft(){ return left_ptr; }

bool word::hasLeft(){ return (getLeft() != NULL); }

bool word::hasRight(){ return (getRight() != NULL); }

list* word::get_head(){ return files; }

word.h

#ifndef WORD_H #define WORD_H #include "list.h" #include #include

class word{ public: word(string wordparam = "", word* left_ptr = NULL, word* right_ptr = NULL);

//Function to set word. void setWord(string wordparam);

//Function to set left_ptr to the left_ptr void setLeft(word* left_ptr);

//Function to set right_ptr to the right_ptr void setRight(word* right_ptr);

//Function to get the pointer to a list containing file nodes. list* get_head();

//Function to access the specified word. string getWord();

//Function to access the pointer for the right node in the list. word* getRight();

//Function to access the pointer for the left node in the list. word* getLeft();

//Function that returns true or false if this node has a left node. bool hasLeft();

//Function that returns true or false if this node has a right node. bool hasRight();

private: string wordparam; word* left_ptr; word* right_ptr; list* files; }; #endif

Please give wordsearch.cpp and wordsearch.h

Now if you actually read through all of that, I congratulate you (and feel free to completely modify the project too).