dictionary.c

// Implements a dictionary's functionality

#include <stdbool.h>
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include<strings.h>
#include "dictionary.h"

// Represents a node in a hash table
typedef struct node
{
    char word[LENGTH + 1];
    struct node *next;
} node;

//function to delete the linked list
void deleteList(node *head)
{
    if (head == NULL)
    {
        return;
    }
    deleteList(head->next);
    free(head);
}

// Number of buckets in hash table
const unsigned int N = 65536;

// Initialise Hash table
node *table[N]; //basically initializes an array of size N that stores address to a node of a linked list (Since it's a pointer)

//variable to keep track of the size (i.e. the number of words in dictionary)
int noOfWords = 0; //global variable

// Hashes word to a number
// Reference Link: https://www.reddit.com/r/cs50/comments/1x6vc8/pset6_trie_vs_hashtable/cf9nlkn/
unsigned int hash(const char *word)
{
    unsigned int hash = 0;
    for (int i = 0, n = strlen(word); i < n; i++)
        hash = (hash << 2) ^ word[i];
    return hash % N;
    return 0;
}
// Produces a total of 2^16 buckets

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    //open dictionary using fopen function that takes 2 arguments; string name of the file to be opened and permissions
    FILE *dictPtr = fopen(dictionary, "r");
    if (dictPtr == NULL)
    {
        return false;
    }

    //initialise a char array to store the words read from the dictionary one by one
    char word[LENGTH + 1];

    //loop to read every word from our dictionary until we reach the end of the file and insert each word into our hash table thus loading it
    while (fscanf(dictPtr, "%s", word) != EOF)
    {
        //making a new node and allocating it memory
        node *temp = malloc(sizeof(node));


        //check if the malloc doesn't return NULL
        if (temp == NULL)
        {
            return false;
        }
        else
        {
            //using string copy function to copy the word from array word to our node
            strcpy(temp->word, word);
            noOfWords++;
            //determining the index using hash function
            int index = hash(temp->word);
            //inserting the node at the specified index
            temp->next = table[index];
            table[index] = temp;
        }
    }
    //close the dictionary file
    fclose(dictPtr);

    return true;
}

// Returns number of words in dictionary if loaded else 0 if not yet loaded
unsigned int size(void) {
    return noOfWords;
}


// Returns true if word is in dictionary else false
bool check(const char *word)
{
    char lowerCaseWord[LENGTH + 1];

    //stores the lower case word (to remove the case sensitivity issue) in another array
    for (int i = 0; i < LENGTH; i++)
    {
        lowerCaseWord[i] = tolower(word[i]);
    }

    //passing the word into the hash function
    int index = hash(lowerCaseWord);

    //make a temporary pointer to the nodes say cursor and point it to the first node of the linked list at that bucket item
    // transverse through that linked list
    for (node *cursor = table[index]; cursor != NULL; cursor = cursor->next)
    {
        //compare the words with those in the list; if matches return true
        if (strcasecmp(word, cursor->word) == 0) //since this function return 1 if both the strings are equal
        {
            return true;
        }
    }
    return false;
}

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    for (int i = 0; i < N; i++)
    {
        //call a recursive function to delete the linked list at each bucket
        deleteList(table[i]);
    }
    return true;
}