Chat with us, powered by LiveChat to implement a program that creates an English dictionary for users to search through for definitions of words | WriteDemy
Login   Register

Question Description

main.cppmain.cppmain.cppmain.cpp

In this task, you will implement a program that creates an English dictionary for users to search through for definitions of words. You will implement a hashtable to store the dictionary and a user interface for managing/using the dictionary. The hash table will be indexed via the words in the English language. The dictionary will store the definition of the words for doing lookups after the dictionary is built.

Here are some of the key components of your implementation:

●Word class

oholds a word (string)

oholds the word’s definition (string)

oAlready implemented for testing, but it’s a tiny thing anyway.

●Hashtable class

oImplements a hash table (a vector)

oThe hash table will start with size 101

oThe Hashtable class will keep track of how many Words it holds (which is size N)

oThe main table will be a C++ STL vector (see note in private: section of the class)

oThe hash table uses separate chaining to resolve collisions (Chapter 5.3)

▪Each chain is a linked list holding Words

▪You’re welcome to decide how you want to do the linked list (STL list is fine)

oThe hash table needs to implement:

▪int hash_function(string key)

●returns an integer based upon converting the string key to an int

●See Figure 5.4 from the book for this algorithm

▪int hash_function(int key)

●returns hashkey integer based upon table size

●The function from the book using mod TableSize would work just fine

▪void insert(key, value)

●Hashes the Word’s key and adds a Word object to the hash table if it isn’t already there

●Updates (overwrites) old entry if there’s a already the same Word in the hash table

▪bool contains(string key)

●Searches the hash table by a string.

●Will need to convert the string to a key, then hash it and search the vector of Words to see if it’s there

▪Word remove(string key)

●Finds an entry using the passed in word, erases it (list.erase()) from the hash table, then returns how many elements it removed [0,1]

▪void rehash()

        • Is called if the table gets above a load factor (N / Table Size) of 1.0 during an insert of a new Word
        • At least doubles the table size then finds the next prime number for the new table size (See figure 5.22 for an example)
        • Example code for finding the next prime above a given integer can be found at:
          https://gist.github.com/alabombarda/f3944cd68dda390d25cb
  • Dictionary class:
    • This class is the user interface for your dictionary.
    • I’ve stubbed in the basics for you, but you’ll need to handle parsing the user’s input they type in and handle JSON files with dictionaries in them.
    • I provided the canonical loop for C++ to handle user input that ends when the file ends (EOF) or ctrl-D because you should just know that one by heart.
    • This class needs to allow the user to enter these commands via STDIN:

help -> print out command help

add “word” “definition” -> Add (or update!) a word and its definition. Must handle quotes

remove “word” -> Remove a given word. Must handle quotes

define “word” -> Define a word by printing out its definition or “unknown word”

load “filename” -> Load in a JSON file of dictionary words

unload “filename” -> Remove words from a given JSON file of dictionary words

size -> Print out current number of words in the dictionary

clear -> Remove ALL words from the dictionary

print [#words] -> Print out all words, unless user gives a maximum number

random -> Print out a single word chosen randomly from the dictionary

quit -> Quit the user interface and shut down

●The key parts include:

●Words can be mixed case, but should still match!

○Hello == hello == HELLO == hElL0

●Words might have quotes around them if they have special characters like spaces, so make sure to strip those off when you parse

●Filenames for JSON files *can* have directory paths. C++ fopen and istream will take those just fine. i.e. configs/fullDict.json

●print has an optional number of words to limit printing

○If the user doesn’t specify, they get *everything* – test with care

○print isn’t in sorted order, just start from the first word you find

  • unload will read in the JSON file and call remove on every word it finds

A note about JSON files:

JSON is a very common format for web servers. It’s used to pass data structures between programs and for storing configurations. The dictionaries I’ve provided are in JSON format. They live in the config/ directory. You may either use a C++ JSON library to load the files or write your own parser, which doesn’t have to handle the full JSON spec, but only our dictionary files. The lines are simple enough that it should be reasonably easy to parse the files without a full on library for handling the full JSON specification, but you’re welcome to approach it either way.
Main JSON page: http://www.json.org/
A couple of JSON libraries if you want to use those:
https://github.com/miloyip/rapidjson
http://uscilab.github.io/cereal/

Don’t underestimate how much it will take to get a working parser for the dictionary files! Handling the various pieces of texts, quotes, and other string handling could be interestingdepending on how you approach things. You can do most of it by reading in each line of the file, deciding if it’s a line with a word and definition, then using string iterators to find the start and stop of the word and definition to copy out.

Testing

As per normal, the Makefile has test cases. In this case there are separate tests for the hash table and the dictionary. The hash table tests are very similar to the ones we’ve seen for trees. The tests for the dictionary are more UI-style where they pass in a series of user commands to view the output. Please have a look at how these tests are implemented to make sure you have a sense of what is expected of the program. They pass in the kinds of strings you would expect based on the documentation here, but the ones in the tests are the canonical ones if there’s a discrepancy.

Deliverables

You must upload your program by checking it into blackboard on the PA3 branch. Please do not merge it into the master branch so the graders can find it more easily. Also, ensure your code stays in the PA3 directory so we know which code base to check. Grading should follow this pattern:
1) git clone your repository (or git pull to sync your local repo with the online version)
2) cd into your repository’s directory
3) git checkout PA3
4) cd PA3
5) make
6) make test
7) make bigtest
8) inspect your output, errors, and code for style and quality

Grading Criteria

Your assignment will be judged by the following criteria:

  • [80] Your code compiles on the EECS servers using g++ -std=c++11 *.cpp (as is defined in the Makefile), passes inspection with a set of test cases (dictionary json files, Makefile, and general poking/prodding via make test and make bigtest.
  • [10] Data structure usage. Your program uses a vector for the hashtable and separate chaining with linked lists for the collision resolution.
  • [10] Your code is well documented and generally easy to read.

the given files

Makefile

# Variables
GPP = g++
CFLAGS = -g -Wall -std=c++11
RM = rm -f
BINNAME = HashingDict
# Shell gives make a full user environment
# Adding this to PATH will find the newer g++ compiler on the EECS servers.
SHELL := /bin/bash
PATH := /opt/rh/devtoolset-3/root/usr/bin/:$(PATH)
# Default is what happenes when you call make with no options
# In this case, it requires that 'all' is completed
default: all
# All is the normal default for most Makefiles
# In this case, it requires that build is completed
all: build
# build depends upon *.cpp, then runs the command:
# g++ -g -std=c++0x -o bigFiveList
build: main.cpp
$(GPP) $(CFLAGS) -o $(BINNAME) main.cpp
run: build
./$(BINNAME)
test: build
./$(BINNAME) –test
bigtest: build
./$(BINNAME) –test –withFuzzing
# If you call "make clean" it will remove the built program
# rm -f HelloWorld
clean veryclean:
$(RM) $(BINNAME)

dictionary.h

#ifndef __DICT_H
#define __DICT_H
#include "hashtable.h"
#include "word.h"
#include <string>
#include <iostream>
class Dictionary
{
private:
Hashtable<string, Word> _dict; // Primary dictionary store
void parseline( string line ) {
//cout << " [d] Parsing line: " << line << endl;
cout << endl;
}
public:
Dictionary()// Default constructor
{ }
/**
* Run the main dictionary user interface
*/
void run_ui() {
// print out header
cout << "+——————————————+" << endl;
cout << "|– Welcome to the best dictionary evar! –|" << endl;
cout << "+——————————————+" << endl;
string instr;
cout << " Enter command (^D or EOF quits): ";
// read in user input until eof
while (getline(cin, instr)) {
cout << endl << " –debug– Entered command: " << instr << endl;
parseline(instr);
// call function based on line contents
// print results
cout << "Enter command: ";
}
cout << endl;
}
};
#endif

hashtable.h

#ifndef __HASH_H
#define __HASH_H
#include <unordered_map>
#include <string>
#include <iostream>
using namespace std;
/*
private:
void rehash();
int hash_function(KEYTYPE key);
public:
bool insert(KEYTYPE key, VALTYPE val);
bool contains(KEYTYPE key);
int remove(KEYTYPE key);
VALTYPE & find(KEYTYPE key);
int size(); // Elements currently in table
bool empty(); // Is the hash empty?
float load_factor(); // Return current load factor
void clear(); // Empty out the table
int bucket_count(); // Total number of buckets in table
*/
template <typename KEYTYPE, typename VALTYPE>
class Hashtable
{
private:
/**
* Rehash the table into a larger table when the load factor is too large
*/
void rehash() {
}
/**
* Function that takes the key (a string or int) and returns the hash key
* This function needs to be implemented for several types it could be used with!
*/
int hash_function(int key) {
cout << " Hashing with int type keys." << endl;
return –1;
}
int hash_function(string key) {
cout << " Hashing with string type keys." << endl;
return –1;
}
public:
/**
* Basic constructor
*/
Hashtable( int startingSize = 101 )
{
}
/**
* Add an element to the hash table
*/
bool insert(KEYTYPE key, VALTYPE val) {
// Currently unimplemented
return false;
}
/**
* Return whether a given key is present in the hash table
*/
bool contains(KEYTYPE key) {
return false;
}
/**
* Completely remove key from hash table
* Returns number of elements removed
*/
int remove(KEYTYPE key) {
// Doesn't actually remove anything yet
return 0;
}
/**
* Searches the hash and returns a pointer
* Pointer to Word if found, or nullptr if nothing matches
*/
VALTYPE *find(KEYTYPE key) {
return nullptr;
}
/**
* Return current number of elements in hash table
*/
int size() {
return(-1);
}
/**
* Return true if hash table is empty, false otherwise
*/
bool empty() {
return(false);
}
/**
* Calculates the current load factor for the hash
*/
float load_factor() {
//return _hash.load_factor();
return (-1.0);
}
/**
* Returns current number of buckets (elements in vector)
*/
int bucket_count() {
return (-1);
}
/**
* Deletes all elements in the hash
*/
void clear() {
// Does nothing yet
}
};
#endif

main.cpp

#include <iostream>
#include <cstdlib>
#include <string.h>
#include "word.h"
#include "hashtable.h"
#include "dictionary.h"
#include "testinghash.h"
#include "testingdictionary.h"
using namespace std;
/**
* Test mode operations
*/
void run_test_mode( bool bigtest = false ) {
cout << " [t] Running in test mode. " << endl;
run_hashtable_tests(); // See testinghash.h
cout << endl << " ———————————————————– " << endl << endl;;
cout << " [t] Testing the dictionary class. " << endl;
run_dictionary_tests( bigtest ); // See testingdictionary.h
}
/**
* Normal mode execution for general user control
*/
void run_normal_mode() {
cout << " [x] Running in normal mode. " << endl;
Dictionary dict;
dict.run_ui();
}
/**
* Main function for test or use
*/
int main( int argc, char* argv[] )
{
// Note: If you call this program like this: ./HashingDict –test
// it will call the test function and –withFuzzing will test and load a big dictionary file
bool do_test = false;
bool do_big_test = false;
for( int i = 0; i < argc; ++i ) {
if( !strcmp(argv[i], "–test" ) ) {
cout << " [x] Enabling test mode. " << endl;
do_test = true;
}
else if( !strcmp(argv[i], "–withFuzzing" ) ) {
cout << " [x] Enabling test and BIG test mode. " << endl;
do_test = true;
do_big_test = true;
}
}
if( do_test ) {
run_test_mode( do_big_test );
cout << " [x] Testing program complete. " << endl;
if( do_big_test )
cout << " [x] BIGTEST testing program complete. " << endl;
}
else
{
cout << " [x] Running in normal mode. " << endl;
cout << " [!] Nothing to do in normal mode so here's a helicopter: " << endl;
cout << " .—-.-.n / ( o \n '| __ ` ||n ||| ||| -'" << endl << endl;
cout << " Since that's not a helicopter, you should probably replace this code with something like "Welcome to my dictionary program" and go into normal running mode." << endl << endl;
cout << endl << " Oh, and you should probably run 'make test' to test your program. " << endl;
run_normal_mode();
}
return(0);
}

testingdictionary.h

#ifndef __DICT_TESTS_H
#define __DICT_TESTS_H
#include <iostream>
#include <string>
#include <fstream>
#include "dictionary.h"
using namespace std;
//**********************************************************************
void do_test( string testname, string filename ) {
cout << "***************************************************************************" << endl;
cout << " [t] Testing '" << testname << "' command" << endl;
string instr;
cout << " [t] Commands being run on the dictionary are: " << endl;
ifstream in(filename); // Open up commands to test for tester to see
while(getline(in, instr)) {
cout << instr << endl;
}
cout << endl << " [t] Running those commands to dict: " << endl << endl;
ifstream in2(filename); // Create file stream for file of commands to test
cin.rdbuf(in2.rdbuf()); // Redirect std::cin to filename!
Dictionary dict; // Create a new dictionary to test
dict.run_ui(); // Run the dictionary, reading from filename
cout << endl << " [t] Done testing '" << testname << "' command" << endl << endl;
}
//**********************************************************************
void run_dictionary_tests( bool bigtest = false ) {
streambuf *cinbuf = cin.rdbuf(); //save default STDIN
cout << " [t] Dictionary tests begin." << endl;
cout << " [x] These tests redirect STDIN to other files. " << endl;
cout << " [x] This *should* work on Windows, but no promises! " << endl;
cout << endl;
do_test("help", "UITests/help.txt");
do_test("add", "UITests/add.txt");
do_test("remove", "UITests/remove.txt");
do_test("define", "UITests/define.txt");
do_test("load", "UITests/load.txt");
do_test("unload", "UITests/unload.txt");
do_test("size", "UITests/size.txt");
do_test("print", "UITests/print.txt");
do_test("random", "UITests/random.txt");
do_test("quit", "UITests/quit.txt");
if( bigtest )
do_test("bigtest","UITests/bigtest.txt");
cin.rdbuf(cinbuf); //reset cin to STDIN again
cout << endl << " [t] Dictionary tests end." << endl;
}
#endif

testinghash.h

#include "hashtable.h"
#include "word.h"
//**************************************************************
void test_hash_empty() {
cout << " [t] Testing empty()" << endl;;
Hashtable<string, Word> ht;
cout << " [t] If is empty – ";
( ht.empty() ) ? cout << "pass" : cout << "fail";
cout << endl;
ht.insert( "test", Word{ "test", "def" } );
cout << " [t] If is not empty – ";
( ht.empty() == false ) ? cout << "pass" : cout << "fail";
cout << endl;
}
//**************************************************************
void test_hash_size() {
cout << " [t] Testing size()" << endl;;
Hashtable<string, Word> ht;
for( int i = 0; i < 4; i++ )
{
cout << " [t] Size " << i << " : " << ht.size();
( i == ht.size() ) ? cout << " – pass" : cout << " – fail";
cout << endl;
ht.insert( to_string(i), Word(to_string(i), "number") );
}
for( int i = 3; i > –1; i– )
{
ht.remove( to_string(i) );
cout << " [t] Size " << i << " : " << ht.size();
( i == ht.size() ) ? cout << " – pass" : cout << " – fail";
cout << endl;
}
}
//**************************************************************
void test_hash_contains() {
cout << " [t] Testing contains()" << endl;;
Hashtable<string, Word> ht;
ht.insert( "wordA", Word("wordA", "It's a word!") );
cout << " [t] Contains wordA (yes)";
( ht.contains( "wordA" ) ) ? cout << " – pass" : cout << " – fail";
cout << endl;
cout << " [t] Contains wordNO (no)";
( !ht.contains( "wordNO" ) ) ? cout << " – pass" : cout << " – fail";
cout << endl;
}
//**************************************************************
void test_hash_remove() {
cout << " [t] Testing remove()" << endl;;
Hashtable<string, Word> ht;
ht.insert( "wordA", Word("WordA", "It's a word!") );
cout << " [t] Contains wordA (yes)";
( ht.contains( "wordA" ) ) ? cout << " – pass" : cout << " – fail";
cout << endl;
cout << " [t] Removing WordA: " << endl;
int count = ht.remove( "wordA" );
cout << " Count (1): " << count;
( count == 1 ) ? cout << " – pass" : cout << " – fail"; cout << endl;
cout << " Contains (no): ";
( !ht.contains( "wordA" ) ) ? cout << " – pass" : cout << " – fail";
cout << endl;
}
//**************************************************************
void test_hash_find() {
cout << " [t] Testing find()" << endl;;
Hashtable<string, Word> ht;
ht.insert( "myWord", Word("myWord", "It's a word!") );
cout << " [t] Contains myWord (yes)";
( ht.contains( "myWord" ) ) ? cout << " – pass" : cout << " – fail";
cout << endl;
Word * found = ht.find( "myWord" );
cout << " [t] myWord should be : myWord : It's a word!" << endl;
cout << " [t] myWord instead is: ";
if( found != nullptr ) {
cout << found->to_string();
if( "myWord : It's a word!" == found->to_string() )
cout << " – pass";
else
cout << " – fail";
}
else
cout << " – fail";
cout << endl;
}
//**************************************************************
// Test load factor (force initial size, insert a couple, output)
void test_hash_loadfactor() {
cout << " [t] Testing loadfactor()" << endl;;
Hashtable<string, Word> ht;
for( int i = 0; i < 500; i++ ) {
ht.insert( to_string(i), Word( to_string(i), "isa word" ) );
if( i % 33 == 0 ) {
cout << " [t] load factor (" << ht.size() << " / "
<< ht.bucket_count() << ") -> ";
float roundedTarget = (float)((int)(100*(float)ht.size() / (float)ht.bucket_count())) /100;
float foundTarget = (float)((int)(100*ht.load_factor())) / 100.0;
cout << roundedTarget << " vs " << foundTarget;
(roundedTarget == foundTarget) ? cout << " – pass" : cout << " – fail";
cout << endl;
}
}
}
//**************************************************************
// Test clearing out whole hash table
void test_hash_clear() {
cout << " [t] Testing clear()" << endl;;
Hashtable<string, Word> ht;
int tbsize = 500;
for( int i = 0; i < tbsize; i++ ) {
ht.insert( to_string(i), Word( to_string(i), "isa word" ) );
}
cout << " [t] Table should be " << tbsize << " elements and is: " << ht.size();
( tbsize == ht.size() ) ? cout << " – pass" : cout << " – fail";
cout << endl;
cout << " [t] Calling clear() on table now." << endl;;
ht.clear();
cout << " [t] Table should be " << 0 << " elements and is: " << ht.size();
( 0 == ht.size() ) ? cout << " – pass" : cout << " – fail";
cout << endl;
cout << " [t] Testing empty() one more time. ";
( ht.empty() ) ? cout << " – pass" : cout << " – fail";
cout << endl;
}
//**************************************************************
void run_hashtable_tests() {
cout << " [t] Testing the hash class itself. " << endl;
// Create object
Hashtable<string, Word> h1;
// NOTE: insert() tested by size() and contains() (at least)
test_hash_empty(); // Test if empty
test_hash_size(); // Test size

Tutor Answer

wolfram777
School: Carnegie Mellon University

Hello buddy,Here's the complete …

Download Completed Work

flagReport DMCA

Review

Anonymous
Thanks, good work
Similar Questions

Assignment
https://youtu.be/2Cg2So2js5kFor this assignment, you will write an essay on the above video:Introduction to Basic Cryptogr…

CryptographyHashing

Hashing Functions
This assignment provides you with the opportunity to work with hashing functions. Study the simple hash function in sectio…

cloud computingsecuritynetworkingcomputer scienceHashing

Heaps, Trees and Hashing
The task this week is to complete the pseudo code for the following hash table operations:InsertRemoveAssume Hashtable is …

javatreesData Structures for Problem Solving (IT265 -1704A -01)HeapsHashing

Heaps, Trees and Hashing
The task this week is to complete the pseudo code for the following hash table operations:InsertRemoveAssume Hashtable is …

javatreesColorado Technical UniversityData Structures for Problem Solving (IT265 -1704A -01)Heaps

Information assurance
Discuss how randomness plays a significant role within the context of message digest functions with your classmates in the…

encryptionHashing

Perfect hashing?
How many times must you attempt to construct one of a perfect hash table’ssub-tables so you have one with probability …

algorithmsHashingPerfecthashing

Cryptography: Hashing
Introduction to Basic Cryptography: HashingIn this essay, you will provide a real-world example of how cryptography/hashin…

Cryptography Hashing

Hashing Question?
You have decided to get away from it all and live on a lighthouse on an island. No internet,no cellular phone, no commu…

computer sciencealgorithmsdata structuresData Structures for Problem Solving (IT265 -1704A -01)Hashing

Requesting Java program
One of the challenges in programs is to store data in a structure that allows fast and efficient searching. Hash tables pr…

programmingcomputer sciencejava Hashing
Hot Questions

loops, programs, abstracts, Programming Essentials exam help
Question 1  A loop can also be known as aDecisionSequenceIterationStructure 2 points   …

runtime errors, keywords, Programming Essentials, quiz help
Question 1  Exception handling allows our programs to:Deal with situations, except in certain condi…

when opening a file, the “wt” parameter indicated that we, Programming Essentials quiz help
Question 1  when opening a file, the “wt” parameter indicated that we:want to append to the end…

Team Management OOP Style, computer science homework help
Team Management OOP StyleYour program for keeping track of team members is coming along, but now you want to be able to in…

SDLC stands for?, Programming Essentials quiz help
Question 1  SDLC stands for:Software Development Life CycleSoftware Deployment Life CycleSoft Dema…

programming, programming homework help
QUESTION 11. Considered the brain of the computerGPU…

When defining a function, which keyword do we use?, Programming Essentials help
Question 1  When defining a function, which keyword do we use:definedeffunctionfunc 1 points &nbs…

FLOWCHART and PSEUDOCODE , programming homework help
Create a FLOWCHART and a PSEUDOCODE for each problem.Use the information below to create a pseudocode (which can be a text…

1 23

Develop a 5-6 page Word document that describes the design for a small Web site
AssignmentDetails_7_1_2015.pdfDevelop a 5-6 page Word document that describes the design for a small Web site that meets t…

Related Tags

keeping tracksystem designPythonHTMLprogrammingarchitecturelanguagevisual flow chartpython programtext and stores each unique wordNative Datatypesthe strings in a vector

Study Guides

Brown University

1271 Tutors

California Institute of Technology

2131 Tutors

Carnegie Mellon University

982 Tutors

Columbia University

1256 Tutors

Dartmouth University

2113 Tutors

Emory University

2279 Tutors

Harvard University

599 Tutors

Massachusetts Institute of Technology

2319 Tutors

New York University

1645 Tutors

Notre Dam University

1911 Tutors

Oklahoma University

2122 Tutors

Pennsylvania State University

932 Tutors

Princeton University

1211 Tutors

Stanford University

983 Tutors

University of California

1282 Tutors

Oxford University

123 Tutors

Yale University

2325 Tutors

Our website has a team of professional writers who can help you write any of your homework. They will write your papers from scratch. We also have a team of editors just to make sure all papers are of HIGH QUALITY & PLAGIARISM FREE. To make an Order you only need to click Ask A Question and we will direct you to our Order Page at WriteDemy. Then fill Our Order Form with all your assignment instructions. Select your deadline and pay for your paper. You will get it few hours before your set deadline.

Fill in all the assignment paper details that are required in the order form with the standard information being the page count, deadline, academic level and type of paper. It is advisable to have this information at hand so that you can quickly fill in the necessary information needed in the form for the essay writer to be immediately assigned to your writing project. Make payment for the custom essay order to enable us to assign a suitable writer to your order. Payments are made through Paypal on a secured billing page. Finally, sit back and relax.

Do you need an answer to this or any other questions?

About Writedemy

We are a professional paper writing website. If you have searched a question and bumped into our website just know you are in the right place to get help in your coursework. We offer HIGH QUALITY & PLAGIARISM FREE Papers.

How It Works

To make an Order you only need to click on “Place Order” and we will direct you to our Order Page. Fill Our Order Form with all your assignment instructions. Select your deadline and pay for your paper. You will get it few hours before your set deadline.

Are there Discounts?

All new clients are eligible for 20% off in their first Order. Our payment method is safe and secure.

Hire a tutor today CLICK HERE to make your first order