**Data Structures in C language: Need help finishing code (in C language) for a program that uses a hash map to implement case-insensitive spell checker. Code with what I already have/header files is included below.

NOTE: I ONLY NEED help with code in "spellChecker.c". NO OTHER FILE CODE SHOULD BE CHANGED!!

**I WILL give positive reviews IF the code meets ALL requirements below! ***

Overview of program: 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.

*** PROGRAM REQUIREMENTS: ***

1) Program Flow--the program should flow in the following order:

----> User types in a word

----> Potential matches are output w/ phrase "did you mean .... ?"

----> Continue to prompt user for word until they type quit.

2) STEPS TO FOLLOW IN ORDER TO IMPLEMENT THE PROGRAM **Code = required for this part

--- 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: If 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 message " Did you mean .... ? ".

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

/************ Start of code *********************/

/************* SPELLCHECKER.C ****************/

#include "hashMap.h" #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); 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); } 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); }

/** * 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); FILE* file = fopen("dictionary.txt", "r"); //if file not found if(file==NULL) { perror("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) //Step 4: continue to prompt user for word until they type quit { printf("Enter a word or \"quit\" to quit: "); scanf("%s", inputBuffer); // Implement the spell checker code here..

/*** 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 * *********************/

//HELP

/***** STEP 2: * Traverse down hash table, checking each bucket. * Jump out if you find an exact matching dictionary word * print a message that "word spelled correctly" * **********************/

//HELP if (hashMapContainsKey(map, inputBuffer)) { printf("That word is spelled correctly! "); } /************ STEP 3: * If the input Buffer did not match any of the dictionary words exactly, * generate an array of 5 words that are the closest matches to input Buffer based * on the LOWEST Levenshtein distance. * print the array INCLUDING the message "did you mean ...?" * ********************/

//HELP else { printf("Did you mean ... ? "); }

//check if input equals "quit" if (strcmp(inputBuffer, "quit") == 0) { quit = 1; } } hashMapDelete(map); return 0; }

/****************** HASHMAP.H *********************/

#ifndef HASH_MAP_H #define HASH_MAP_H

/* * CS 261 Data Structures * Assignment 5 */

#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 ****************************/

**NOTE: I DO NOT NEED CODE FOR THIS FILE!!

#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 for (int i = 0; i < map->capacity; i++) { HashLink* link = map->table[i]; map->table[i] = NULL;

while (link != NULL) { HashLink* temp = link; link = link->next; hashLinkDelete(temp); }

free(map->table[i]); }

free(map->table); }

/** * 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. 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 int idx = HASH_FUNCTION(key) % (map->capacity);

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

while (link != NULL) { if (strcmp(link->key, key) == 0) { return &(link->value); } link = link->next; } return NULL;

}

/** * Resizes the hash table to have a number of buckets equal to the given * capacity. After allocating the new table, all of the links need to be * 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 // Save old Map information int oldCap = map->capacity; HashLink ** oldTable = map->table;

// Initialize new map data to replace old map data hashMapInit(map, capacity);

// Rehash old map key/value pairs to new map for (int i = 0; i < oldCap; i++) { HashLink * link = oldTable[i];

while (link != NULL) { hashMapPut(map, link->key, link->value); link = link->next; } }

// Free allocated data in old table for (int i = 0; i < oldCap; i++) { HashLink* link = oldTable[i]; oldTable[i] = NULL;

while (link != NULL) { HashLink* temp = link; link = link->next; hashLinkDelete(temp); } free(oldTable[i]); } free(oldTable); }

/** * 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. 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. Also make sure to search the entire list. * * @param map * @param key * @param value */ void hashMapPut(HashMap* map, const char* key, int value) { // FIXME: implement // Resize table if exceeds MAX_TABLE_LOAD if (hashMapTableLoad(map) >= MAX_TABLE_LOAD) { resizeTable(map, 2 * map->capacity); } // Compute index int idx = HASH_FUNCTION(key) % (map->capacity); if (idx < 0) { idx += map->capacity; } // Add to bucket HashLink* link = map->table[idx]; HashLink* newLink = NULL; if (link == NULL) { // Bucket is currently empty newLink= hashLinkNew(key, value, NULL); map->table[idx] = newLink; map->size++; return; } else { //bucket contains @ least 1 link while (link != NULL) { if (strcmp(link->key, key) == 0) { //link w/ key already exists link->value = value; return; } link = link->next; } // Link with given key does not already exist, create new Link newLink = hashLinkNew(key, value, map->table[idx]); map->table[idx] = newLink; map->size++; return; } }

/** * 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 if (!hashMapContainsKey(map, key)) { printf("Not in map "); return; }

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

HashLink* cur = map->table[idx]; HashLink* last = map->table[idx];

if (cur == NULL) { printf("No links in bucket to remove "); } while (cur != NULL) { if (strcmp(cur->key, key) == 0) { //printf("Found key/link to remove "); if (cur == map->table[idx]) { //printf("Link to remove is first link "); map->table[idx] = cur->next; hashLinkDelete(cur); map->size--; cur = 0; } else { last->next = cur->next; hashLinkDelete(cur); map->size--; cur = 0; } } else { last = cur; cur = cur->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 int idx = HASH_FUNCTION(key) % (map->capacity);

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

while (link != NULL) { if (strcmp(link->key, key) == 0) { return 1; } 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; }

/** * 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; }

/** * 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;

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 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) { 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(" "); }