152 lines
3.4 KiB
C
152 lines
3.4 KiB
C
// Implements a dictionary's functionality
|
|
|
|
#include <stdbool.h>
|
|
#include "dictionary.h"
|
|
#include <string.h>
|
|
#include <ctype.h>
|
|
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
|
|
// Represents a node in a hash table
|
|
typedef struct node
|
|
{
|
|
char word[LENGTH + 1];
|
|
struct node *next;
|
|
}
|
|
node;
|
|
|
|
//initialize dictionary size
|
|
int counter = 0;
|
|
// Number of buckets in hash table
|
|
const unsigned int N = 1560;
|
|
|
|
// Hash table
|
|
node *table[N];
|
|
|
|
// Returns true if word is in dictionary, else false
|
|
bool check(const char *word)
|
|
{
|
|
// TODO
|
|
int word_len = strlen(word) + 1;
|
|
// convert to lowercase
|
|
char word_low[word_len];
|
|
for (int i = 0; i < word_len; i++)
|
|
{
|
|
word_low[i] = tolower(word[i]);
|
|
}
|
|
|
|
// convert word to hash value
|
|
int hash_val = hash(word_low);
|
|
|
|
// create node containing linked list from hash value position in table
|
|
node *n = table[hash_val];
|
|
|
|
//loop through linked list untill end
|
|
while (n != NULL)
|
|
{
|
|
// return true if word matches with current node from linked list, if not go next node
|
|
if (strcmp(word_low, n->word) == 0)
|
|
{
|
|
return true;
|
|
}
|
|
n = n->next;
|
|
}
|
|
|
|
// if word was not found in the linked list, return true, words is not in dict
|
|
return false;
|
|
}
|
|
|
|
// Hashes word to a number
|
|
unsigned int hash(const char *word)
|
|
{
|
|
// TODO
|
|
long sum = 0;
|
|
// create ASCII sum of all letters in word converted to lowercase
|
|
for (int i = 0; i < strlen(word); i++)
|
|
{
|
|
sum += tolower(word[i]);
|
|
|
|
}
|
|
// returns remainder of sum / bucket number
|
|
return sum % N;
|
|
}
|
|
|
|
// Loads dictionary into memory, returning true if successful, else false
|
|
bool load(const char *dictionary)
|
|
{
|
|
// TODO
|
|
// Open dictionary file
|
|
FILE *dict_file = fopen(dictionary, "r");
|
|
|
|
// Check if null
|
|
if (dictionary == NULL)
|
|
{
|
|
printf("Unable to open %s\n", dictionary);
|
|
return false;
|
|
}
|
|
|
|
//array to store newly found words
|
|
char new_word[LENGTH + 1];
|
|
|
|
// read dictionary strings one at a time
|
|
while (fscanf(dict_file, "%s", new_word) != EOF)
|
|
{
|
|
// create node for every word
|
|
node *n = malloc(sizeof(node));
|
|
|
|
// check if malloc worked, if not free memory
|
|
if (n == NULL)
|
|
{
|
|
unload();
|
|
return false;
|
|
}
|
|
|
|
// copy word to node
|
|
strcpy(n->word, new_word);
|
|
|
|
//obtain hash value
|
|
int hash_val = hash(new_word);
|
|
|
|
// set node next to correct place in table and than set table place to node
|
|
n->next = table[hash_val];
|
|
table[hash_val] = n;
|
|
|
|
//increase dict size for each loop
|
|
counter++;
|
|
}
|
|
|
|
// close the file
|
|
fclose(dict_file);
|
|
|
|
return true;
|
|
}
|
|
|
|
// Returns number of words in dictionary if loaded, else 0 if not yet loaded
|
|
unsigned int size(void)
|
|
{
|
|
// returns dictionary size
|
|
return counter;
|
|
}
|
|
|
|
// Unloads dictionary from memory, returning true if successful, else false
|
|
bool unload(void)
|
|
{
|
|
// TODO
|
|
//loop through all buckets
|
|
for (int i = 0; i <= N; i++)
|
|
{
|
|
// check and do until table is empty
|
|
while (table[i] != NULL)
|
|
{
|
|
//create temp node to store pointer to next table
|
|
node *tmp = table[i] ->next;
|
|
//free memory, set tmp pointer back to table and repeat untill all is free
|
|
free(table[i]);
|
|
table[i] = tmp;
|
|
}
|
|
}
|
|
|
|
return true;
|
|
}
|
|
|