Now you are ready to implement a spell checker by using or quadratic. Given a document, your program should output all of the correctly spelled words, labeled as such, and all of the misspelled words. For each misspelled word you should provide a list of candidate corrections from the dictionary, that can be formed by applying one of the following rules to the misspelled word: a) Adding one character in any possible position
b) Removing one character from the word
c) Swapping adjacent characters in the word
Your program should run from the command line as follows:
% ./spell_check
You will be provided with a small document named document1_short. txt, document_1.txt,
and a dictionary file with approximately 370k words named wordsEnglish. txt.
As an example, your spell checker should correct the following mistakes.
deciive -> decisive (Case A)
deciasion -> decision (Case B)
ocunry -> counry (Case C)
//spell_check. cc file
#include "quadratic_probing. h"
#include
#include
#include
using namespace std;
int testSpellingWrapper(int argument_count, char** argument_list) {
const string document_filename(argument_list[1]) ;
const string dictionary_filename(argument_list[2 ]);
// Call functions implementing the assignment requirements.
// HashTableDouble dictionary = MakeDictionary(dictionary_filename) ;
// SpellChecker(dictionary, document_filename);
return 0;
}
// Sample main for program spell_check.
// WE WILL NOT USE YOUR MAIN IN TESTING. DO NOT CODE FUNCTIONALITY INTO THE
// MAIN. WE WILL DIRECTLY CALL testSpellingWrapper. ALL FUNCTIONALITY SHOULD BE
// THERE. This main is only here for your own testing purposes.
int main(int argc, char** argv) {
if (argc != 3) {
cout << "Usage: " << argv[0] << " "
<< endl;
return 0;
}
testSpellingWrapper(argc, argv);
return 0;
}

//quadratic_probing. h file
#ifndef QUADRATIC_PROBING_H
#define QUADRATIC_PROBING_H
#include
#include
#include
namespace {
// Internal method to test if a positive number is prime.
bool IsPrime(size_t n) {
if( n == 2 || n == 3 )
return true;
if( n == 1 || n % 2 == 0 )
return false;
for( int i = 3; i * i <= n; i += 2 )
if( n % i == 0 )
return false;
return true;
}
// Internal method to return a prime number at least as large as n.
int NextPrime(size_t n) {
if (n % 2 == 0)
++n;
while (!IsPrime(n)) n += 2;
return n;
}
} // namespace
// Quadratic probing implementation.
template
class HashTable {
public:
enum EntryType {ACTIVE, EMPTY, DELETED};
explicit HashTable(size_t size = 101) : array_(NextPrime(size))
{ MakeEmpty(); }
bool Contains(const HashedObj & x) const {
return IsActive(FindPos(x));
}
void MakeEmpty() {
current_size_ = 0;
for (auto &entry : array_)
entry. info_ = EMPTY;
}
bool Insert(const HashedObj & x) {
// Insert x as active
size_t current_pos = FindPos(x);
if (IsActive(current_pos))
return false;
array_[current_pos].element_ = x;
array_[current_pos].info_ = ACTIVE;
// Rehash; see Section 5.5
if (++current_size_ > array_.size() / 2)
Rehash();
return true;
}
bool Insert(HashedObj && x) {
// Insert x as active
size_t current_pos = FindPos(x);
if (IsActive(current_pos))
return false;
array_[current_pos] = std::move(x);
array_[current_pos].info_ = ACTIVE;
// Rehash; see Section 5.5
if (++current_size_ > array_.size() / 2)
Rehash();
return true;
}
bool Remove(const HashedObj & x) {
size_t current_pos = FindPos(x);
if (!IsActive(current_pos))
return false;
array_[current_pos].info_ = DELETED;
return true;
}
private:
struct HashEntry {
HashedObj element_;
EntryType info_;
HashEntry(const HashedObj& e = HashedObj{}, EntryType i = EMPTY)
:element_{e}, info_{i} { }
HashEntry(HashedObj && e, EntryType i = EMPTY)
:element_{std::move(e)}, info_{ i } {}
};
std::vector array_;
size_t current_size_;
bool IsActive(size_t current_pos) const
{ return array_[current_pos].info_ == ACTIVE; }
size_t FindPos(const HashedObj & x) const {
size_t offset = 1;
size_t current_pos = InternalHash(x);
while (array_[current_pos].info_ != EMPTY &&
array_[current_pos].element_ != x) {
current_pos += offset; // Compute ith probe.
offset += 2;
if (current_pos >= array_.size())
current_pos -= array_.size();
}
return current_pos;
}
void Rehash() {
std::vector old_array = array_;
// Create new double-sized, empty table.
array_.resize(NextPrime(2 * old_array. size()));
for (auto & entry : array_)
entry. info_ = EMPTY;
// Copy table over.
current_size_ = 0;
for (auto & entry :old_array)
if (entry. info_ == ACTIVE)
Insert(std::move(entry. element_));
}
size_t InternalHash(const HashedObj & x) const {
static std::hash hf;
return hf(x) % array_.size( );
}
};
#endif // QUADRATIC_PROBING_H