Hello, I've completed the hashMap implementation for this assignment but was having some issues with the spellCheck.c portion of the assignment and would appreciate any assistance available.

Part 3: Spell Checker

There are a lot of uses for a hash map, and one of them is implementing a case-insensitive spell checker. All you need to get started is a dictionary, which is provided in dictionary.txt. In spellChecker.c you will find some code to get you started with the spell checker. It is fairly similar to the code in main.c.

You can build the program with make spellChecker. FYI:

The spellchecker program flow should as following - 1. The user types in a word (only one word at a time should be allowed) 2. If the spelling is correct, the following message should be outputted - " The inputted word .... is spelled correctly If the spelling is incorrect, the following message should be outputted - " The inputted word .... is spelled incorrectly. Also, 5 potential matches should be outputted like "Did you mean...?" etc 4. Continue to prompt user for word until they type quit

One way to implement a dictionary that's used for a spellchecker would probably be to design it with that purpose in mind from the beginning, i.e. associating a similarity for each word to some base word (maybe "abcdefghijklmnopqrstuvwyz") and then incorporating that into the hash function. But there are better ways (https:// en.wikipedia.org/wiki/Levenshtein_distance) to establish similarity than computing the cosine of the angle between two vectors (strings) to create a list of candidates and further winnowed that list according to substring comparisons. So, I would say calculating the Levenshtein distance between the misspelled word and all strings in the dictionary, create 5 best candidates and print them as suggestion.

Below is one example of the steps that you can follow to implement your spellchecker -

Step 1: Compare input buffer to words in the dictionary, computing their Levenshtein distance. Store that distance as the value for each key in the table. Step 2: Traverse down the hash table, checking each bucket. Jump out if you find an exact matching dictionary word. and print a message that "word spelled correctly".

Step 3: f the input Buffer did not match any of the dictionary words exactly, generate an array of 5 words that are closest matches to input Buffer based on the lowest Levenshtein distance. print the array including the messages "word spelled incorrectly", " Did you mean .... ?

Step 4: Continue to prompt user for word until they type quit

hashMap.h

#ifndef HASH_MAP_H #define HASH_MAP_H

#define HASH_FUNCTION hashFunction1 #define MAX_TABLE_LOAD 10

typedef struct HashMap HashMap; typedef struct HashLink HashLink;

struct HashLink { char* key; int value; HashLink* next; };

struct HashMap { HashLink** table; // Number of links in the table. int size; // Number of buckets in the table. int capacity; };

HashMap* hashMapNew(int capacity); void hashMapDelete(HashMap* map); int* hashMapGet(HashMap* map, const char* key); void hashMapPut(HashMap* map, const char* key, int value); void hashMapRemove(HashMap* map, const char* key); int hashMapContainsKey(HashMap* map, const char* key);

int hashMapSize(HashMap* map); int hashMapCapacity(HashMap* map); int hashMapEmptyBuckets(HashMap* map); float hashMapTableLoad(HashMap* map); void hashMapPrint(HashMap* map);

#endif

hashMap.c

#define _CRT_SECURE_NO_WARNINGS

#include "hashMap.h"

#include

#include

#include

#include

#include

int hashFunction1(const char* key)

{

int r = 0;

for (int i = 0; key[i] != '\0'; i++)

{

r += key[i];

}

return r;

}

int hashFunction2(const char* key)

{

int r = 0;

for (int i = 0; key[i] != '\0'; i++)

{

r += (i + 1) * key[i];

}

return r;

}

/**

* Creates a new hash table link with a copy of the key string.

* @param key Key string to copy in the link.

* @param value Value to set in the link.

* @param next Pointer to set as the link's next.

* @return Hash table link allocated on the heap.

*/

HashLink* hashLinkNew(const char* key, int value, HashLink* next)

{

HashLink* link = malloc(sizeof(HashLink));

link->key = malloc(sizeof(char) * (strlen(key) + 1));

strcpy(link->key, key);

link->value = value;

link->next = next;

return link;

}

/**

* Free the allocated memory for a hash table link created with hashLinkNew.

* @param link

*/

static void hashLinkDelete(HashLink* link)

{

free(link->key);

free(link);

}

/**

* Initializes a hash table map, allocating memory for a link pointer table with

* the given number of buckets.

* @param map

* @param capacity The number of table buckets.

*/

void hashMapInit(HashMap* map, int capacity)

{

map->capacity = capacity;

map->size = 0;

map->table = malloc(sizeof(HashLink*) * capacity);

for (int i = 0; i < capacity; i++)

{

map->table[i] = NULL;

}

}

/**

* Removes all links in the map and frees all allocated memory. You can use

* hashLinkDelete to free the links.

* @param map

*/

void hashMapCleanUp(HashMap* map)

{

// FIXME: implement

struct HashLink *link;

struct HashLink *next;

/* Begin a loop to go through the table: */

for (int i = 0; i < map->capacity; i++) {

link = map->table[i];

//iterate through the buckets

if (link != 0) {

do {

next = link->next;

hashLinkDelete(link);

link = next;

} while (next != 0);

}

}

free(map->table);

map->table = 0;

}

/**

* Creates a hash table map, allocating memory for a link pointer table with

* the given number of buckets.

* @param capacity The number of buckets.

* @return The allocated map.

*/

HashMap* hashMapNew(int capacity)

{

HashMap* map = malloc(sizeof(HashMap));

hashMapInit(map, capacity);

return map;

}

/**

* Removes all links in the map and frees all allocated memory, including the

* map itself.

* @param map

*/

void hashMapDelete(HashMap* map)

{

hashMapCleanUp(map);

free(map);

}

/**

* Returns a pointer to the value of the link with the given key and skip traversing as well. Returns NULL

* if no link with that key is in the table.

*

* Use HASH_FUNCTION(key) and the map's capacity to find the index of the

* correct linked list bucket. Also make sure to search the entire list.

*

* @param map

* @param key

* @return Link value or NULL if no matching link.

*/

int* hashMapGet(HashMap* map, const char* key)

{

// FIXME: implement

/* Call the Hash Function to get the index. */

//int index = HASH_FUNCTION(key) % map->capacity;

//if (index < 0) {

// index += map->capacity;

//}

////go to index location pointer

//HashLink *searcher = map->table[index];

////traverse the linked list until key matches

//while (searcher != NULL) {

// if (strcmp(searcher->key, key) == 0) {

// return &(searcher->value);

// }

// searcher = searcher->next;

//}

////NULL if no key match

// return NULL;

int hashIndex = HASH_FUNCTION(key) % map->capacity;

if (hashIndex < 0)

hashIndex = hashIndex + map->capacity;

struct HashLink *link = map->table[hashIndex];

while (link != 0) {

if (strcmp(link->key, key) == 0)

return &(link->value);

else

link = link->next;

}

return 0;

}

/**

* Resizes the hash table to have a number of buckets equal to the given

* capacity (double of the old capacity). After allocating the new table,

* all of the links need to rehashed into it because the capacity has changed.

*

* Remember to free the old table and any old links if you use hashMapPut to

* rehash them.

*

* @param map

* @param capacity The new number of buckets.

*/

void resizeTable(HashMap* map, int capacity)

{

// FIXME: implement

//create a new hashmap

//HashMap *newHashMap = hashMapNew(capacity);

////traverse the current map table

//for (int i = 0; i < map->capacity; i++) {

// HashLink *searcher = map->table[i];

// //traverse the linked list and add to the new map

// while (searcher != NULL) {

// hashMapPut(newHashMap, searcher->key, searcher->value);

// searcher = searcher->next;

// }

//}

////clean the current map, copy contents, and free newMap

//hashMapCleanUp(map);

//*map = *newHashMap;

//free(newHashMap);

struct HashMap *newMap = hashMapNew(capacity);

struct HashLink *link;

for (int i = 0; i < map->capacity; i++) {

link = map->table[i];

//add links

while (link != 0) {

hashMapPut(newMap, link->key, link->value);

link = link->next;

}

}

//Swap the capacities of the tables

hashMapCleanUp(map);

map->table = newMap->table;

map->size = newMap->size;

map->capacity = newMap->capacity;

free(newMap); //free temporary map

}

/**

* Updates the given key-value pair in the hash table. If a link with the given

* key already exists, this will just update the value and skip traversing. Otherwise, it will

* create a new link with the given key and value and add it to the table

* bucket's linked list. You can use hashLinkNew to create the link.

*

* Use HASH_FUNCTION(key) and the map's capacity to find the index of the

* correct linked list bucket.

*

* @param map

* @param key

* @param value

*/

void hashMapPut(HashMap* map, const char* key, int value)

{

// FIXME: implement

// Update existing key value field if key exists.

if (hashMapContainsKey(map, key)) {

int *valPtr = hashMapGet(map, key);

*valPtr += value;

}

else {

//Add link if key does not exist.

//resize if table will exceed MAX_TABLE_LOAD.

if (hashMapTableLoad(map) >= MAX_TABLE_LOAD) {

resizeTable(map, 2 * map->capacity);

}

//calculate hash index.

int index = HASH_FUNCTION(key) % map->capacity;

if (index < 0) {

index += map->capacity;

}

//create new hashLink.

HashLink *newHashLink = hashLinkNew(key, value, NULL);

//if location is NULL, directly assign the newHashLink

if (map->table[index] == NULL) {

map->table[index] = newHashLink;

}

else {

//otherwise add to the end of the linked list.

//create searcher.

HashLink *searcher = map->table[index];

//traverse to the end of the linked list

while (searcher->next != NULL) {

searcher = searcher->next;

}

//set the next to the new link

searcher->next = newHashLink;

}

//increment map size

map->size++;

}

//int hashIndex = HASH_FUNCTION(key) % map->capacity;

//if (hashIndex < 0)

// hashIndex = hashIndex + map->capacity;

//struct HashLink *link = map->table[hashIndex];

//while (link != 0) {

// if (strcmp(link->key, key) == 0) {

// link->value = value; //set new value

// return;

// }

// link = link->next; //move to next

//}

////No value found to match, add to front

//link = hashLinkNew(key, value, map->table[hashIndex]);

//map->table[hashIndex] = link;

//map->size++;

//if (hashMapTableLoad(map) > MAX_TABLE_LOAD) {

// resizeTable(map, 2 * hashMapCapacity(map)); //resize if load factor's higher than max

//}

}

/**

* Removes and frees the link with the given key from the table. If no such link

* exists, this does nothing. Remember to search the entire linked list at the

* bucket. You can use hashLinkDelete to free the link.

* @param map

* @param key

*/

void hashMapRemove(HashMap* map, const char* key)

{

// FIXME: implement

////calculate hash index.

//int index = HASH_FUNCTION(key) % map->capacity;

//if (index < 0) {

// index += map->capacity;

//}

////create a searcher and previous link pointer.

//HashLink *searcher = map->table[index];

//HashLink *previous;

////loop through the linked list

//while (searcher != NULL) {

// if (strcmp(searcher->key, key) == 0) {

// //check if first link

// if (searcher == map->table[index]) {

// map->table[index] = searcher->next;

// }

// //not first link; set previous->next

// else {

// previous->next = searcher->next;

// }

// //delete link and stop loop

// hashLinkDelete(searcher);

// searcher = NULL;

// map->size--;

// }

// //go to next link

// else {

// previous = searcher;

// searcher = searcher->next;

// }

//}

assert(map != 0);

int hashIndex = HASH_FUNCTION(key) % map->capacity;

if (hashIndex < 0)

hashIndex = hashIndex + map->table[hashIndex]->next;

struct HashLink *link = map->table[hashIndex];

struct HashLink *next = map->table[hashIndex]->next;

if (link == 0) {

return;

}

if (strcmp(link->key, key) == 0) {

hashLinkDelete(link);

map->table[hashIndex] = next;

map->size--;

return;

}

while (next != 0) {

if (strcmp(next->key, key) == 0) {

link->next = next->next;

hashLinkDelete(next);

map->size--;

return;

}

else {

link = link->next;

next = next->next;

}

}

}

/**

* Returns 1 if a link with the given key is in the table and 0 otherwise.

*

* Use HASH_FUNCTION(key) and the map's capacity to find the index of the

* correct linked list bucket. Also make sure to search the entire list.

*

* @param map

* @param key

* @return 1 if the key is found, 0 otherwise.

*/

int hashMapContainsKey(HashMap* map, const char* key)

{

// FIXME: implement

//index calculation

//int index = HASH_FUNCTION(key) % map->capacity;

//if (index < 0) {

// index += map->capacity;

//}

////create searcher

//HashLink *searcher = map->table[index];

////traverse the linked list

//while (searcher != NULL) {

// if (strcmp(searcher->key, key) == 0) {

// return 1;

// }

// searcher = searcher->next;

//}

//return 0;

int hashIndex = HASH_FUNCTION(key) % map->capacity;

if (hashIndex < 0)

hashIndex = hashIndex + map->capacity;

struct HashLink *link = map->table[hashIndex];

while (link != 0) {

if (strcmp(link->key, key) == 0) {

return 1;

}

else

link = link->next;

}

return 0;

}

/**

* Returns the number of links in the table.

* @param map

* @return Number of links in the table.

*/

int hashMapSize(HashMap* map)

{

// FIXME: implement

return map->size; //return num of links

}

/**

* Returns the number of buckets in the table.

* @param map

* @return Number of buckets in the table.

*/

int hashMapCapacity(HashMap* map)

{

// FIXME: implement

return map->capacity; //return num of buckets

}

/**

* Returns the number of table buckets without any links.

* @param map

* @return Number of empty buckets.

*/

int hashMapEmptyBuckets(HashMap* map)

{

// FIXME: implement

//int emptyBuckets = 0;

////index through the table to accumlate NULL pointers

//for (int i = 0; i < map->capacity; i++) {

// if (map->table[i] == NULL) {

// emptyBuckets++;

// }

//}

//return emptyBuckets;

int emptyBuckets = 0;

for (int i = 0; i < map->capacity; i++)

{

HashLink* link = map->table[i];

if (link == NULL)

{

emptyBuckets++;

}

}

return emptyBuckets;

}

/**

* Returns the ratio of (number of links) / (number of buckets) in the table.

* Remember that the buckets are linked lists, so this ratio tells you nothing

* about the number of empty buckets. Remember also that the load is a floating

* point number, so don't do integer division.

* @param map

* @return Table load.

*/

float hashMapTableLoad(HashMap* map)

{

// FIXME: implement

//return (float)map->size / (float)map->capacity;

//return (double)map->size / (map->capacity); //calculate table load = num of links / num of buckets

float links = (float)map->size;

float buckets = (float)map->capacity;

return (links / buckets);

}

/**

* Prints all the links in each of the buckets in the table.

* @param map

*/

void hashMapPrint(HashMap* map)

{

// FIXME: implement

for (int i = 0; i < map->capacity; i++)

{

HashLink* link = map->table[i];

if (link != NULL)

{

printf(" Bucket %i ->", i);

while (link != NULL)

{

printf(" (%s, %d) ->", link->key, link->value);

link = link->next;

}

}

}

printf(" ");

}

spellChecker.c

#define _CRT_SECURE_NO_WARNINGS

#include "hashMap.h"

#include

#include

#include

#include

#include

#include

/**

* Allocates a string for the next word in the file and returns it. This string

* is null terminated. Returns NULL after reaching the end of the file.

* @param file

* @return Allocated string or NULL.

*/

char* nextWord(FILE* file)

{

int maxLength = 16;

int length = 0;

char* word = malloc(sizeof(char) * maxLength);

assert(word != NULL);

while (1)

{

char c = fgetc(file);

if ((c >= '0' && c <= '9') ||

(c >= 'A' && c <= 'Z') ||

(c >= 'a' && c <= 'z') ||

c == '\'')

{

if (length + 1 >= maxLength)

{

maxLength *= 2;

word = realloc(word, maxLength);

}

c = tolower(c);

word[length] = c;

length++;

}

else if (length > 0 || c == EOF)

{

break;

}

}

if (length == 0)

{

free(word);

return NULL;

}

word[length] = '\0';

return word;

}

/**

* Loads the contents of the file into the hash map.

* @param file

* @param map

*/

void loadDictionary(FILE* file, HashMap* map)

{

// FIXME: implement

char* word = nextWord(file);

while (word) {

hashMapPut(map, word, 1);

free(word);

word = nextWord(file);

}

free(word);

}

void casefix(char* word);

/**

* Prints the concordance of the given file and performance information. Uses

* the file input1.txt by default or a file name specified as a command line

* argument.

* @param argc

* @param argv

* @return

*/

int main(int argc, const char** argv)

{

// FIXME: implement

HashMap* map = hashMapNew(1000);

/* Define file: */

printf("Opening dictionary.txt ");

FILE* file = fopen("dictionary.txt", "r");

/*assert(file != NULL);*/

// If file not present

if (file == NULL)

{

//Display error

printf("Error");

}

clock_t timer = clock();

loadDictionary(file, map);

timer = clock() - timer;

printf("Dictionary loaded in %f seconds ", (float)timer / (float)CLOCKS_PER_SEC);

fclose(file);

char inputBuffer[256];

int quit = 0;

while (!quit)

{

printf("Enter a word or \"quit\" to quit: ");

scanf("%s", inputBuffer);

casefix(inputBuffer);

// Implement the spell checker code here..

//If condition matches

if (hashMapContainsKey(map, inputBuffer))

{

//Display message

printf("That word is spelled correctly! ");

}

//Otherwise

else

{

//Display message

printf("That word is mispelled! ");

}

if (strcmp(inputBuffer, "quit") == 0)

{

quit = 1;

}

}

hashMapDelete(map);

return 0;

}

void casefix(char* word)

{

if (word == NULL)

{

return;

}

if (word == 0)

{

return;

}

int i = 0;

while (word[i] != '\0')

{

word[i] = tolower(word[i]);

i++;

}

}