There are three parts to this assignment. In the rst two parts, you will complete the implementation of a hash map and a concordance program. In the third part, you will answer a number of questions using the concordance program. There is also an extra credit opportunity. Prerequisites It may also be helpful to review C le I/O with fopen() and fclose(). Hash map First complete the hash map implementation in hashMap.c. This hash map uses a table of buckets, each containing a linked list of hash links. Each hash link stores the key-value pair (string and integer in this case) and a pointer to the next link in the list. See hashMap.h and the accompanied drawing posted with this assignment for clarication. You must implement each function in hashMap.c with the // FIXME: implement comment. At the top of hashMap.h you should see two macros: HASH_FUNCTION and MAX_TABLE_LOAD. You are free to change their denitions but know that the default values will be used when grading. HASH_FUNCTION is the name of the hash function you want to use. You will change this when answering the written part of the assignment. Make sure everywhere in your implementation to use HASH_FUNCTION(key) instead of directly calling a hash function. MAX_TABLE_LOAD is the table load threshold on which you should resize the table. A number of tests for the hash map are included in tests.c. Each one of these test cases use several or all of the hash map functions, so dont expect tests to pass until you implement all of them. Each test case is slightly more thorough than the one before it and there is a lot of redundancy to better ensure correctness. Use these tests to help you debug your hash map implementation. They will also help your TA grade your submission. You can build the tests with make tests or make and run them with ./tests. Concordance The concordance counts how many times each word occurs in a document. You will implement a concor-dance using the hash map implementation from the previous part. Each hash link in the table will store a word from the document as the key and the number of times the word appeared as the value. You must nish the concordance implementation in main.c. You are provided with a function nextWord() which takes a FILE*, allocates memory for the next word in the le, and returns the word. If the end of the le is reached, nextWord() will return NULL. It is your job to open the le using fopen(), populate the concordance with the words, and close the le with fclose(). The le name to open should be given as a command line argument when running the program. It will default to input1.txt if no le name is provided.

Your concordance code should loop over the words until the end of the le is reached, doing the following steps each iteration:

1. Get the next word with getWord. 2. If the word is already in the hash map, then increment its number of occurrences. 3. Otherwise, put the word in the hash map with a count of 1. 4. Free the word.

After processing the text le, print all words and occurrence counts in the hash map. Please print them in the format of the following example above the call to hashMapPrint():

best: 1 It: 2 was: 2 the: 2 of: 2 worst: 1 times: 2

You can build the program with make prog or make and run it with ./prog , where is the name of a text le like input1.txt.

Written

Submit a pdf or text le answering the following questions:

1. Give an example of two words that would hash to the same value using hashFunction1 but would not using hashFunction2. 2. Why does the above observation make hashFunction2 superior to hashFunction1? 3. When you run your program on the same input le once with hashFunction1 and once with hashFunction2, is it possible for your hashMapSize function to return different values? 4. When you run your program on the same input le once with hashFunction1 and once with hashFunction2, is it possible for your hashMapTableLoad function to return different values? 5. When you run your program on the same input le once with hashFunction1 and once with hashFunction2, is it possible for your hashMapEmptyBuckets function to return different values? 6. Is there any difference in the number of empty buckets when you change the table size from an even number like 1000 to a prime like 997?

Extra credit There are a lot of uses for a hash map, and one of them is implementing a spell checker. All you need to get started is a dictionary, which is provided in dictionary.txt. In spellChecker.c you will nd 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 2. Potential matches are outputted Like "Did you mean...?" etc 3. Continue to prompt user for word until they type quit The best 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. 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/6 best candidates and print them as suggestion.

CuTest.h

#ifndef CU_TEST_H #define CU_TEST_H

#include #include

#define CUTEST_VERSION "CuTest 1.5"

/* CuString */

char* CuStrAlloc(int size); char* CuStrCopy(const char* old);

#define CU_ALLOC(TYPE) ((TYPE*) malloc(sizeof(TYPE)))

#define HUGE_STRING_LEN 8192 #define STRING_MAX 256 #define STRING_INC 256

typedef struct { int length; int size; char* buffer; } CuString;

void CuStringInit(CuString* str); CuString* CuStringNew(void); void CuStringRead(CuString* str, const char* path); void CuStringAppend(CuString* str, const char* text); void CuStringAppendChar(CuString* str, char ch); void CuStringAppendFormat(CuString* str, const char* format, ...); void CuStringInsert(CuString* str, const char* text, int pos); void CuStringResize(CuString* str, int newSize); void CuStringDelete(CuString* str);

/* CuTest */

typedef struct CuTest CuTest;

typedef void (*TestFunction)(CuTest *);

struct CuTest { char* name; TestFunction function; int failed; int ran; int parents; char* message; jmp_buf *jumpBuf; };

void CuTestInit(CuTest* t, const char* name, TestFunction function); CuTest* CuTestNew(const char* name, TestFunction function); CuTest* CuTestCopy(CuTest* t); void CuTestRun(CuTest* tc); void CuTestDelete(CuTest *t);

/* Internal versions of assert functions -- use the public versions */ void CuFail_Line(CuTest* tc, const char* file, int line, const char* message2, const char* message); void CuAssert_Line(CuTest* tc, const char* file, int line, const char* message, int condition); void CuAssertStrEquals_LineMsg(CuTest* tc, const char* file, int line, const char* message, const char* expected, const char* actual); void CuAssertIntEquals_LineMsg(CuTest* tc, const char* file, int line, const char* message, int expected, int actual); void CuAssertDblEquals_LineMsg(CuTest* tc, const char* file, int line, const char* message, double expected, double actual, double delta); void CuAssertPtrEquals_LineMsg(CuTest* tc, const char* file, int line, const char* message, void* expected, void* actual);

/* public assert functions */

#define CuFail(tc, ms) CuFail_Line( (tc), __FILE__, __LINE__, NULL, (ms)) #define CuAssert(tc, ms, cond) CuAssert_Line((tc), __FILE__, __LINE__, (ms), (cond)) #define CuAssertTrue(tc, cond) CuAssert_Line((tc), __FILE__, __LINE__, "assert failed", (cond))

#define CuAssertStrEquals(tc,ex,ac) CuAssertStrEquals_LineMsg((tc),__FILE__,__LINE__,NULL,(ex),(ac)) #define CuAssertStrEquals_Msg(tc,ms,ex,ac) CuAssertStrEquals_LineMsg((tc),__FILE__,__LINE__,(ms),(ex),(ac)) #define CuAssertIntEquals(tc,ex,ac) CuAssertIntEquals_LineMsg((tc),__FILE__,__LINE__,NULL,(ex),(ac)) #define CuAssertIntEquals_Msg(tc,ms,ex,ac) CuAssertIntEquals_LineMsg((tc),__FILE__,__LINE__,(ms),(ex),(ac)) #define CuAssertDblEquals(tc,ex,ac,dl) CuAssertDblEquals_LineMsg((tc),__FILE__,__LINE__,NULL,(ex),(ac),(dl)) #define CuAssertDblEquals_Msg(tc,ms,ex,ac,dl) CuAssertDblEquals_LineMsg((tc),__FILE__,__LINE__,(ms),(ex),(ac),(dl)) #define CuAssertPtrEquals(tc,ex,ac) CuAssertPtrEquals_LineMsg((tc),__FILE__,__LINE__,NULL,(ex),(ac)) #define CuAssertPtrEquals_Msg(tc,ms,ex,ac) CuAssertPtrEquals_LineMsg((tc),__FILE__,__LINE__,(ms),(ex),(ac))

#define CuAssertPtrNotNull(tc,p) CuAssert_Line((tc),__FILE__,__LINE__,"null pointer unexpected",(p != NULL)) #define CuAssertPtrNotNullMsg(tc,msg,p) CuAssert_Line((tc),__FILE__,__LINE__,(msg),(p != NULL))

/* CuSuite */

#define MAX_TEST_CASES 1024

#define SUITE_ADD_TEST(SUITE,TEST) CuSuiteAdd(SUITE, CuTestNew(#TEST, TEST))

typedef struct { int count; CuTest* list[MAX_TEST_CASES]; int failCount;

} CuSuite;

void CuSuiteInit(CuSuite* testSuite); CuSuite* CuSuiteNew(void); void CuSuiteDelete(CuSuite *testSuite); void CuSuiteAdd(CuSuite* testSuite, CuTest *testCase); void CuSuiteAddSuite(CuSuite* testSuite, CuSuite* testSuite2); void CuSuiteConsume(CuSuite* testSuite, CuSuite* testSuite2); void CuSuiteRun(CuSuite* testSuite); void CuSuiteSummary(CuSuite* testSuite, CuString* summary); void CuSuiteDetails(CuSuite* testSuite, CuString* details);

#endif /* CU_TEST_H */

CuTest.c

#include #include #include #include #include #include #include

#include "CuTest.h"

/*CuStr*/

char* CuStrAlloc(int size) { char* newStr = (char*) malloc( sizeof(char) * (size) ); return newStr; }

char* CuStrCopy(const char* old) { int len = strlen(old); char* newStr = CuStrAlloc(len + 1); strcpy(newStr, old); return newStr; }

/* CuString-*/

void CuStringInit(CuString* str) { str->length = 0; str->size = STRING_MAX; str->buffer = (char*) malloc(sizeof(char) * str->size); str->buffer[0] = '\0'; }

CuString* CuStringNew(void) { CuString* str = (CuString*) malloc(sizeof(CuString)); str->length = 0; str->size = STRING_MAX; str->buffer = (char*) malloc(sizeof(char) * str->size); str->buffer[0] = '\0'; return str; }

void CuStringDelete(CuString *str) { if (!str) return; free(str->buffer); free(str); }

void CuStringResize(CuString* str, int newSize) { str->buffer = (char*) realloc(str->buffer, sizeof(char) * newSize); str->size = newSize; }

void CuStringAppend(CuString* str, const char* text) { int length;

if (text == NULL) { text = "NULL"; }

length = strlen(text); if (str->length + length + 1 >= str->size) CuStringResize(str, str->length + length + 1 + STRING_INC); str->length += length; strcat(str->buffer, text); }

void CuStringAppendChar(CuString* str, char ch) { char text[2]; text[0] = ch; text[1] = '\0'; CuStringAppend(str, text); }

void CuStringAppendFormat(CuString* str, const char* format, ...) { va_list argp; char buf[HUGE_STRING_LEN]; va_start(argp, format); vsprintf(buf, format, argp); va_end(argp); CuStringAppend(str, buf); }

void CuStringInsert(CuString* str, const char* text, int pos) { int length = strlen(text); if (pos > str->length) pos = str->length; if (str->length + length + 1 >= str->size) CuStringResize(str, str->length + length + 1 + STRING_INC); memmove(str->buffer + pos + length, str->buffer + pos, (str->length - pos) + 1); str->length += length; memcpy(str->buffer + pos, text, length); }

/* CuTest---*/

void CuTestInit(CuTest* t, const char* name, TestFunction function) { t->name = CuStrCopy(name); t->failed = 0; t->ran = 0; t->parents = 0; t->message = NULL; t->function = function; t->jumpBuf = NULL; }

CuTest* CuTestNew(const char* name, TestFunction function) { CuTest* tc = CU_ALLOC(CuTest); CuTestInit(tc, name, function); return tc; }

CuTest* CuTestCopy(CuTest* t) { CuTest* copy = CU_ALLOC(CuTest); memcpy(copy, t, sizeof(CuTest)); return copy; }

void CuTestDelete(CuTest *t) { if (!t) return; if (--t->parents < 1) { free(t->name); free(t->message); free(t); } }

void CuTestRun(CuTest* tc) { jmp_buf buf; tc->jumpBuf = &buf; if (setjmp(buf) == 0) { tc->ran = 1; (tc->function)(tc); } tc->jumpBuf = 0; }

static void CuFailInternal(CuTest* tc, const char* file, int line, CuString* string) { char buf[HUGE_STRING_LEN];

sprintf(buf, "%s:%d: ", file, line); CuStringInsert(string, buf, 0);

tc->failed = 1; tc->message = string->buffer; if (tc->jumpBuf != 0) longjmp(*(tc->jumpBuf), 0); }

void CuFail_Line(CuTest* tc, const char* file, int line, const char* message2, const char* message) { CuString string;

CuStringInit(&string); if (message2 != NULL) { CuStringAppend(&string, message2); CuStringAppend(&string, ": "); } CuStringAppend(&string, message); CuFailInternal(tc, file, line, &string); }

void CuAssert_Line(CuTest* tc, const char* file, int line, const char* message, int condition) { if (condition) return; CuFail_Line(tc, file, line, NULL, message); }

void CuAssertStrEquals_LineMsg(CuTest* tc, const char* file, int line, const char* message, const char* expected, const char* actual) { CuString string; if ((expected == NULL && actual == NULL) || (expected != NULL && actual != NULL && strcmp(expected, actual) == 0)) { return; }

CuStringInit(&string); if (message != NULL) { CuStringAppend(&string, message); CuStringAppend(&string, ": "); } CuStringAppend(&string, "expected <"); CuStringAppend(&string, expected); CuStringAppend(&string, "> but was <"); CuStringAppend(&string, actual); CuStringAppend(&string, ">"); CuFailInternal(tc, file, line, &string); }

void CuAssertIntEquals_LineMsg(CuTest* tc, const char* file, int line, const char* message, int expected, int actual) { char buf[STRING_MAX]; if (expected == actual) return; sprintf(buf, "expected <%d> but was <%d>", expected, actual); CuFail_Line(tc, file, line, message, buf); }

void CuAssertDblEquals_LineMsg(CuTest* tc, const char* file, int line, const char* message, double expected, double actual, double delta) { char buf[STRING_MAX]; if (fabs(expected - actual) <= delta) return; sprintf(buf, "expected <%f> but was <%f>", expected, actual);

CuFail_Line(tc, file, line, message, buf); }

void CuAssertPtrEquals_LineMsg(CuTest* tc, const char* file, int line, const char* message, void* expected, void* actual) { char buf[STRING_MAX]; if (expected == actual) return; sprintf(buf, "expected pointer <0x%p> but was <0x%p>", expected, actual); CuFail_Line(tc, file, line, message, buf); }

/*CuSuite--*/

void CuSuiteInit(CuSuite* testSuite) { testSuite->count = 0; testSuite->failCount = 0; memset(testSuite->list, 0, sizeof(testSuite->list)); }

CuSuite* CuSuiteNew(void) { CuSuite* testSuite = CU_ALLOC(CuSuite); CuSuiteInit(testSuite); return testSuite; }

void CuSuiteDelete(CuSuite *testSuite) { unsigned int n; for (n=0; n < MAX_TEST_CASES; n++){ if (testSuite->list[n]){ CuTestDelete(testSuite->list[n]); } } free(testSuite);

}

void CuSuiteAdd(CuSuite* testSuite, CuTest *testCase) { assert(testSuite->count < MAX_TEST_CASES); testSuite->list[testSuite->count] = testCase; testSuite->count++; if (testCase->parents != INT_MAX){ testCase->parents++; } else{ testCase = CuTestCopy(testCase); } }

void CuSuiteAddSuite(CuSuite* testSuite, CuSuite* testSuite2) { int i; for (i = 0 ; i < testSuite2->count ; ++i){ CuTest* testCase = testSuite2->list[i]; CuSuiteAdd(testSuite, testCase); } }

void CuSuiteConsume(CuSuite* testSuite, CuSuite* testSuite2) { CuSuiteAddSuite(testSuite, testSuite2); CuSuiteDelete(testSuite2); }

void CuSuiteRun(CuSuite* testSuite) { int i; for (i = 0 ; i < testSuite->count ; ++i){ CuTest* testCase = testSuite->list[i]; CuTestRun(testCase); if (testCase->failed) { testSuite->failCount += 1; } } }

void CuSuiteSummary(CuSuite* testSuite, CuString* summary) { int i; for (i = 0 ; i < testSuite->count ; ++i){ CuTest* testCase = testSuite->list[i]; CuStringAppend(summary, testCase->failed ? "F" : "."); } CuStringAppend(summary, " "); }

void CuSuiteDetails(CuSuite* testSuite, CuString* details) { int i; int failCount = 0;

if (testSuite->failCount == 0){ int passCount = testSuite->count - testSuite->failCount; const char* testWord = passCount == 1 ? "test" : "tests"; CuStringAppendFormat(details, "OK (%d %s) ", passCount, testWord); } else{ if (testSuite->failCount == 1) CuStringAppend(details, "There was 1 failure: "); else CuStringAppendFormat(details, "There were %d failures: ", testSuite->failCount);

for (i = 0 ; i < testSuite->count ; ++i){ CuTest* testCase = testSuite->list[i]; if (testCase->failed){ failCount++; CuStringAppendFormat(details, "%d) %s: %s ", failCount, testCase->name, testCase->message); } } CuStringAppend(details, " !!!FAILURES!!! ");

CuStringAppendFormat(details, "Runs: %d ", testSuite->count); CuStringAppendFormat(details, "Passes: %d ", testSuite->count - testSuite->failCount); CuStringAppendFormat(details, "Fails: %d ", testSuite->failCount); } }

hashMap.h

#ifndef HASH_MAP_H #define HASH_MAP_H

#define HASH_FUNCTION hashFunction1 #define MAX_TABLE_LOAD .75

typedef struct HashMap HashMap; typedef struct HashLink HashLink;

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

struct HashMap { HashLink** table;

int size;// Number of links in the table. int capacity; // Number of buckets in the table. };

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

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

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

static void hashLinkDelete(HashLink* link) { free(link->key); free(link); }

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

void hashMapCleanUp(HashMap* map) { // FIXME: implement }

HashMap* hashMapNew(int capacity) { HashMap* map = malloc(sizeof(HashMap)); hashMapInit(map, capacity); return map; }

void hashMapDelete(HashMap* map) { hashMapCleanUp(map); free(map); }

int* hashMapGet(HashMap* map, const char* key) { // FIXME: implement return NULL; }

void resizeTable(HashMap* map, int capacity) { // FIXME: implement }

void hashMapPut(HashMap* map, const char* key, int value) { // FIXME: implement }

void hashMapRemove(HashMap* map, const char* key) { // FIXME: implement }

int hashMapContainsKey(HashMap* map, const char* key) { // FIXME: implement return 0; }

int hashMapSize(HashMap* map) { // FIXME: implement return 0; }

int hashMapCapacity(HashMap* map) { // FIXME: implement return 0; }

int hashMapEmptyBuckets(HashMap* map) { // FIXME: implement return 0; }

float hashMapTableLoad(HashMap* map) { // FIXME: implement return 0; }

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

spellChecker.c

#include "hashMap.h" #include #include #include #include #include

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

void loadDictionary(FILE* file, HashMap* map) { // FIXME: implement }

int main(int argc, const char** argv) { // FIXME: implement HashMap* map = hashMapNew(1000); FILE* file = fopen("dictionary.txt", "r"); 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); // Implement the spell checker code here.. if (strcmp(inputBuffer, "quit") == 0){ quit = 1; } } hashMapDelete(map); return 0; }

tests.c

#include "CuTest.h"

#include "hashMap.h" #include #include #include #include

// --- Test Helpers ---

typedef struct HistLink HistLink; typedef struct Histogram Histogram;

struct HistLink { char* key; int count; HistLink* next; };

struct Histogram { HistLink* head; int size; };

void histInit(Histogram* hist) { hist->head = NULL; hist->size = 0; }

void histCleanUp(Histogram* hist) { HistLink* link = hist->head; while (link != NULL){ HistLink* next = link->next; free(link); link = next; } }

void histAdd(Histogram* hist, char* key) { HistLink* link = hist->head; while (link != NULL){ if (strcmp(key, link->key) == 0 ){ link->count++; return; } link = link->next; } link = malloc(sizeof(HistLink)); link->key = key; link->count = 1; link->next = hist->head; hist->head = link; hist->size++; }

void histFromTable(Histogram* hist, HashMap* map) { histInit(hist); for (int i = 0; i < map->capacity; i++){ HashLink* link = map->table[i]; while (link != NULL){ histAdd(hist, link->key); link = link->next; } } }

void assertHistCounts(CuTest* test, Histogram* hist) { HistLink* link = hist->head; while (link != NULL){ CuAssertIntEquals(test, 1, link->count); link = link->next; } }

// --- Hash Map tests ---

void testCase(CuTest* test, HashLink* links, const char** notKeys, int numLinks, int numNotKeys, int numBuckets)

{ HashMap* map = hashMapNew(numBuckets); Histogram hist; // Add links for (int i = 0; i < numLinks; i++){ hashMapPut(map, links[i].key, links[i].value); } // Print table printf(" After adding all key-value pairs:"); hashMapPrint(map); // Check size CuAssertIntEquals(test, numLinks, hashMapSize(map)); // Check capacity CuAssertIntEquals(test, map->capacity, hashMapCapacity(map)); // Check empty buckets int sum = 0; for (int i = 0; i < map->capacity; i++){ if (map->table[i] == NULL){ sum++; } } CuAssertIntEquals(test, sum, hashMapEmptyBuckets(map)); // Check table load CuAssertIntEquals(test, (float)numLinks / map->capacity, hashMapTableLoad(map)); // Check contains and get on valid keys. for (int i = 0; i < numLinks; i++){ CuAssertIntEquals(test, 1, hashMapContainsKey(map, links[i].key)); int* value = hashMapGet(map, links[i].key); CuAssertPtrNotNull(test, value); CuAssertIntEquals(test, links[i].value, *value); } // Check contains and get on invalid keys. for (int i = 0; i < numNotKeys; i++){ CuAssertIntEquals(test, 0, hashMapContainsKey(map, notKeys[i])); CuAssertPtrEquals(test, NULL, hashMapGet(map, notKeys[i])); } // Check that all links are present and have a unique key. histFromTable(&hist, map); CuAssertIntEquals(test, numLinks, hist.size); assertHistCounts(test, &hist); histCleanUp(&hist); // Remove keys for (int i = 0; i < numLinks; i++){ hashMapRemove(map, links[i].key); } // Print table printf(" After removing all key-value pairs:"); hashMapPrint(map); // Check size CuAssertIntEquals(test, 0, hashMapSize(map)); // Check capacity CuAssertIntEquals(test, map->capacity, hashMapCapacity(map)); // Check empty buckets CuAssertIntEquals(test, map->capacity, hashMapEmptyBuckets(map)); // Check table load CuAssertIntEquals(test, 0, hashMapTableLoad(map)); // Check contains and get on valid keys. for (int i = 0; i < numLinks; i++){ CuAssertIntEquals(test, 0, hashMapContainsKey(map, links[i].key)); CuAssertPtrEquals(test, NULL, hashMapGet(map, links[i].key)); } // Check contains and get on invalid keys. for (int i = 0; i < numNotKeys; i++){ CuAssertIntEquals(test, 0, hashMapContainsKey(map, notKeys[i])); CuAssertPtrEquals(test, NULL, hashMapGet(map, notKeys[i])); } // Check that there are no links in the table. histFromTable(&hist, map); CuAssertIntEquals(test, 0, hist.size); assertHistCounts(test, &hist); histCleanUp(&hist); hashMapDelete(map); }

void testSingleUnder(CuTest* test) { printf(" --- Testing single-link chains under threshold --- "); HashLink links[] = { { .key = "a", .value = 0, .next = NULL }, { .key = "c", .value = 1, .next = NULL }, { .key = "d", .value = 2, .next = NULL }, { .key = "f", .value = 3, .next = NULL }, { .key = "g", .value = 4, .next = NULL } }; const char* notKeys[] = { "b", "e", "h" }; testCase(test, links, notKeys, 5, 3, 10); }

void testSingleOver(CuTest* test) { printf(" --- Testing single-link chains over threshold --- "); HashLink links[] = { { .key = "a", .value = 0, .next = NULL }, { .key = "c", .value = 1, .next = NULL }, { .key = "d", .value = 2, .next = NULL }, { .key = "f", .value = 3, .next = NULL }, { .key = "g", .value = 4, .next = NULL } }; const char* notKeys[] = { "b", "e", "h" }; testCase(test, links, notKeys, 5, 3, 1);

}

void testMultipleUnder(CuTest* test) { printf(" --- Testing multiple-link chains under threshold --- "); HashLink links[] = { { .key = "ab", .value = 0, .next = NULL }, { .key = "c", .value = 1, .next = NULL }, { .key = "ba", .value = 2, .next = NULL }, { .key = "f", .value = 3, .next = NULL }, { .key = "gh", .value = 4, .next = NULL } }; const char* notKeys[] = { "b", "e", "hg" }; testCase(test, links, notKeys, 5, 3, 10); }

void testMultipleOver(CuTest* test) { printf(" --- Testing multiple-link chains over threshold --- "); HashLink links[] = { { .key = "ab", .value = 0, .next = NULL }, { .key = "c", .value = 1, .next = NULL }, { .key = "ba", .value = 2, .next = NULL }, { .key = "f", .value = 3, .next = NULL }, { .key = "gh", .value = 4, .next = NULL } }; const char* notKeys[] = { "b", "e", "hg" }; testCase(test, links, notKeys, 5, 3, 1); }

void testValueUpdate(CuTest* test) { int numLinks = 5; printf(" --- Testing value updates --- "); HashLink links[] = { { .key = "ab", .value = 0, .next = NULL }, { .key = "c", .value = 1, .next = NULL }, { .key = "ba", .value = 2, .next = NULL }, { .key = "ab", .value = 3, .next = NULL }, { .key = "gh", .value = 4, .next = NULL } }; HashMap* map = hashMapNew(1); // Add links for (int i = 0; i < numLinks; i++){ hashMapPut(map, links[i].key, links[i].value); } // Print table printf(" After adding all key-value pairs:"); hashMapPrint(map); int* value = hashMapGet(map, "ab"); CuAssertPtrNotNull(test, value); CuAssertIntEquals(test, 3, *value); Histogram hist; histFromTable(&hist, map); CuAssertIntEquals(test, numLinks - 1, hist.size); assertHistCounts(test, &hist); histCleanUp(&hist); hashMapDelete(map); }

// --- Test Suite ---

void addAllTests(CuSuite* suite) { SUITE_ADD_TEST(suite, testSingleUnder); SUITE_ADD_TEST(suite, testSingleOver); SUITE_ADD_TEST(suite, testMultipleUnder); SUITE_ADD_TEST(suite, testMultipleOver); SUITE_ADD_TEST(suite, testValueUpdate); }

int main() { CuSuite* suite = CuSuiteNew(); addAllTests(suite); CuSuiteRun(suite); CuString* output = CuStringNew(); CuSuiteSummary(suite, output); CuSuiteDetails(suite, output); printf(" %s ", output->buffer); CuStringDelete(output); CuSuiteDelete(suite); return 0; }

main.c

#include "hashMap.h" #include #include #include #include #include

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

int main(int argc, const char** argv) { // FIXME: implement const char* fileName = "input1.txt"; if (argc > 1){ fileName = argv[1]; } printf("Opening file: %s ", fileName); clock_t timer = clock(); HashMap* map = hashMapNew(10); // --- Concordance code begins here --- // Be sure to free the word after you are done with it here. // --- Concordance code ends here --- hashMapPrint(map); timer = clock() - timer; printf(" Ran in %f seconds ", (float)timer / (float)CLOCKS_PER_SEC); printf("Empty buckets: %d ", hashMapEmptyBuckets(map)); printf("Number of links: %d ", hashMapSize(map)); printf("Number of buckets: %d ", hashMapCapacity(map)); printf("Table load: %f ", hashMapTableLoad(map)); hashMapDelete(map); return 0; }

input1.txt

As the wind does blow Across the trees I see the Buds blooming in May

I walk across sand And find myself blistering In the hot hot heat

Falling to the ground I watch a leaf settle down In a bed of brown.

It's cold and I wait For someone to shelter me And take me from here.

I hear crackling Crunch of today's new found day And know it won't last

So I will leave it At bay; and hope for the best This bitter new day

input2.txt

Call me Ishmael Some years ago never mind how long precisely having little or no money in my purse and nothing particular to interest me on shore I thought I would sail about a little and see the watery part of the world It is a way I have of driving off the spleen and regulating the circulation Whenever I find myself growing grim about the mouth whenever it is a damp drizzly November in my soul whenever I find myself involuntarily pausing before coffin warehouses and bringing up the rear of every funeral I meet and especially whenever my hypos get such an upper hand of me that it requires a strong moral principle to prevent me from deliberately stepping into the street and methodically knocking peoples hats off then I account it high time to get to sea as soon as I can This is my substitute for pistol and ball With a philosophical flourish Cato throws himself upon his sword I quietly take to the ship There is nothing surprising in this If they but knew it almost all men in their degree some time or other cherish very nearly the same feelings towards the ocean with me There now is your insular city of the Manhattoes belted round by wharves as Indian isles by coral reefs commerce surrounds it with her surf Right and left the streets take you waterward Its extreme downtown is the battery where that noble mole is washed by waves and cooled by breezes which a few hours previous were out of sight of land Look at the crowds of water gazers there Circumambulate the city of a dreamy Sabbath afternoon Go from Corlears Hook to Coenties Slip and from thence by Whitehall northward What do you see Posted like silent sentinels all around the town stand thousands upon thousands of mortal men fixed in ocean reveries Some leaning against the spiles some seated upon the pier heads some looking over the bulwarks of ships from China some high aloft in the rigging as if striving to get a still better seaward peep But these are all landsmen of week days pent up in lath and plaster tied to counters nailed to benches clinched to desks How then is this Are the green fields gone What do they here But look here come more crowds pacing straight for the water and seemingly bound for a dive Strange Nothing will content them but the extremest limit of the land loitering under the shady lee of yonder warehouses will not suffice No They must get just as nigh the water as they possibly can without falling And there they stand miles of them leagues Inlanders all they come from lanes and alleys streets avenues north east south and west Yet here they all unite Tell me does the magnetic virtue of the needles of the compasses of all those ships attract them thither Once more Say you are in the country in some high land of lakes Take almost any path you please and ten to one it carries you down in a dale and leaves you there by a pool in the stream There is magic in it Let the most absent minded of men be plunged in his deepest reveries stand that man on his legs set his feet a going and he will infallibly lead you to water if water there be in all that region Should you ever be athirst in the great American desert try this experiment if your caravan happen to be supplied with a metaphysical professor Yes as every one knows meditation and water are wedded for ever But here is an artist He desires to paint you the dreamiest shadiest quietest most enchanting bit of romantic landscape in all the valley of the Saco What is the chief element he employs There stand his trees each with a hollow trunk as if a hermit and a crucifix were within and here sleeps his meadow and there sleep his cattle and up from yonder cottage goes a sleepy smoke Deep into distant woodlands winds a mazy way reaching to overlapping spurs of mountains bathed in their hill side blue But though the picture lies thus tranced and though this pine tree shakes down its sighs like leaves upon this shepherds head yet all were vain unless the shepherds eye were fixed upon the magic stream before him Go visit the Prairies in June when for scores on scores of miles you wade knee deep among Tiger lilies what is the one charm wanting Water there is not a drop of water there Were Niagara but a cataract of sand would you travel your thousand miles to see it Why did the poor poet of Tennessee upon suddenly receiving two handfuls of silver deliberate whether to buy him a coat which he sadly needed or invest his money in a pedestrian trip to Rockaway Beach Why is almost every robust healthy boy with a robust healthy soul in him at some time or other crazy to go to sea Why upon your first voyage as a passenger did you yourself feel such a mystical vibration when first told that you and your ship were now out of sight of land Why did the old Persians hold the sea holy Why did the Greeks give it a separate deity and own brother of Jove Surely all this is not without meaning And still deeper the meaning of that story of Narcissus who because he could not grasp the tormenting mild image he saw in the fountain plunged into it and was drowned But that same image we ourselves see in all rivers and oceans It is the image of the ungraspable phantom of life and this is the key to it all Now when I say that I am in the habit of going to sea whenever I begin to grow hazy about the eyes and begin to be over conscious of my lungs I do not mean to have it inferred that I ever go to sea as a passenger For to go as a passenger you must needs have a purse and a purse is but a rag unless you have something in it Besides passengers get sea sick grow quarrelsome dont sleep of nights do not enjoy themselves much as a general thing no I never go as a passenger nor though I am something of a salt do I ever go to sea as a Commodore or a Captain or a Cook I abandon the glory and distinction of such offices to those who like them For my part I abominate all honorable respectable toils trials and tribulations of every kind whatsoever It is quite as much as I can do to take care of myself without taking care of ships barques brigs schooners and what not And as for going as cook though I confess there is considerable glory in that a cook being a sort of officer on ship board yet somehow I never fancied broiling fowls though once broiled judiciously buttered and judgmatically salted and peppered there is no one who will speak more respectfully not to say reverentially of a broiled fowl than I will It is out of the idolatrous dotings of the old Egyptians upon broiled ibis and roasted river horse that you see the mummies of those creatures in their huge bakehouses the pyramids No when I go to sea I go as a simple sailor right before the mast plumb down into the fore castle aloft there to the royal mast head True they rather order me about some and make me jump from spar to spar like a grasshopper in a May meadow And at first this sort of thing is unpleasant enough It touches ones sense of honor particularly if you come of an old established family in the land the Van Rensselaers or Randolphs or Hardicanutes And more than all if just previous to putting your hand into the tar pot you have been lording it as a country schoolmaster making the tallest boys stand in awe of you The transition is a keen one I assure you from a schoolmaster to a sailor and requires a strong decoction of Seneca and the Stoics to enable you to grin and bear it But even this wears off in time What of it if some old hunks of a sea captain orders me to get a broom and sweep down the decks What does that indignity amount to weighed I mean in the scales of the New Testament Do you think the archangel Gabriel thinks anything the less of me because I promptly and respectfully obey that old hunks in that particular instance Who aint a slave Tell me that Well then however the old sea captains may order me about however they may thump and punch me about I have the satisfaction of knowing that it is all right that everybody else is one way or other served in much the same way either in a physical or metaphysical point of view that is and so the universal thump is passed round and all hands should rub each others shoulder blades and be content Again I always go to sea as a sailor because they make a point of paying me for my trouble whereas they never pay passengers a single penny that I ever heard of On the contrary passengers themselves must pay And there is all the difference in the world between paying and being paid The act of paying is perhaps the most uncomfortable infliction that the two orchard thieves entailed upon us But being paid what will compare with it The urbane activity with which a man receives money is really marvellous considering that we so earnestly believe money to be the root of all earthly ills and that on no account can a monied man enter heaven Ah how cheerfully we consign ourselves to perdition Finally I always go to sea as a sailor because of the wholesome exercise and pure air of the fore castle deck For as in this world head winds are far more prevalent than winds from astern that is if you never violate the Pythagorean maxim so for the most part the Commodore on the quarter deck gets his atmosphere at second hand from the sailors on the forecastle He thinks he breathes it first but not so In much the same way do the commonalty lead their leaders in many other things at the same time that the leaders little suspect it But wherefore it was that after having repeatedly smelt the sea as a merchant sailor I should now take it into my head to go on a whaling voyage this the invisible police officer of the Fates who has the constant surveillance of me and secretly dogs me and influences me in some unaccountable way he can better answer than any one else And doubtless my going on this whaling voyage formed part of the grand programme of Providence that was drawn up a long time ago It came in as a sort of brief interlude and solo between more extensive performances I take it that this part of the bill must have run something like this Grand Contested Election for the Presidency of the United States WHALING VOYAGE BY ONE ISHMAEL BLOODY BATTLE IN AFFGHANISTAN Though I cannot tell why it was exactly that those stage managers the Fates put me down for this shabby part of a whaling voyage when others were set down for magnificent parts in high tragedies and short and easy parts in genteel comedies and jolly parts in farces though I cannot tell why this was exactly yet now that I recall all the circumstances I think I can see a little into the springs and motives which being cunningly presented to me under various disguises induced me to set about performing the part I did besides cajoling me into the delusion that it was a choice resulting from my own unbiased freewill and discriminating judgment Chief among these motives was the overwhelming idea of the great whale himself Such a portentous and mysterious monster roused all my curiosity Then the wild and distant seas where he rolled his island bulk the undeliverable nameless perils of the whale these with all the attending marvels of a thousand Patagonian sights and sounds helped to sway me to my wish With other men perhaps such things would not have been inducements but as for me I am tormented with an everlasting itch for things remote I love to sail forbidden seas and land on barbarous coasts Not ignoring what is good I am quick to perceive a horror and could still be social with it would they let me since it is but well to be on friendly terms with all the inmates of the place one lodges in By reason of these things then the whaling voyage was welcome the great flood gates of the wonder world swung open and in the wild conceits that swayed me to my purpose two and two there floated into my inmost soul endless processions of the whale and mid most of them all one grand hooded phantom like a snow hill in the air

input3.txt

eat ate tea