dictionary.c

// Implements a dictionary's functionality

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

#include "dictionary.h"
bool loadfile = false;

// https://www.reddit.com/r/cs50/comments/ey5q5j/pset5_speller_whyyy_int_n_65536/
#define HASHTABLE_SIZE 65536


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

// Number of buckets in hash table
// Hash table
// Hash table is array of node pointers[node1.node2..]
// [node*, node*]

node *table[HASHTABLE_SIZE];

int wordsize = 0;

unsigned int hash(const char* word)
 {
     unsigned long hash = 5381;

     for (const char* ptr = word; *ptr != '\0'; ptr++)
     {
         hash = ((hash << 5) + hash) + tolower(*ptr);
     }

     return hash % HASHTABLE_SIZE;
 }
 
 
 // Loads dictionary into memory, returning true if successful else false
// When you open up this dictionary file and store all of the words in memory, you're going to store them all inside of a hash table. Hash table is array of individual linked lists
    // the way you determine which of those linked lists you're going to insert a word into is based on a hash fucnction. (Hash function is going to take input, a string, or a word)
    // that you're going to include in the dictionary, and the output is going to be some number that you're able to generate from that input, which is correspond to which of the linked lists
    // you want to place this particular word into.
// 1. open up this dictionary file.
// 2. read strings from file one at a time (one word in the dictionary at a time)
// 3. create a new node for each word (value and pointer to next)
// 4. hash word to obtain a hash value, and index into your hash table to determine which of those linked lists you should use when you're inserting this node into a linked list.
// 5. take each of those words and insert that node into hash table at that location given by your hash function.
bool load(const char *dictionary)
{
    // TODO
    FILE *file = fopen(dictionary, "r");
    if (file == NULL)
    {
        return false;
    }
    // hashtable[] need to be initialized, because it could contain garbage pointer data, not NULLs
    for (int i = 0; i < HASHTABLE_SIZE; i++)
    {
        table[i] = NULL;
    }
    
    
    // read string from the file, fscanf, short for scanning from a file, where the first argument is going to be that file pointer, the result of calling fopne on the dictionary file.
    // The second argument is %s, meanning you want to read in a string. the third argument is word, which is going to be some character array, some place where you're going to
    // read the word into. In other words, some character array inside of memory where you can then access all of the individual characters of that word after you've read it from
    // the file.
    char w[LENGTH + 1];
    while (fscanf(file, "%s", w) != EOF)
    {
        node *n = malloc(sizeof(node));
        if (n == NULL)
        {
            return false;
        }
        // insert the node to hash table, hash table is an array of linked lists.
        // if hashtable contains no value in this index,
        // insert at the begining
        
        strcpy(n->word, w);
        
        int index = hash(w);
        if (table[index] == NULL)
        {
            table[index] = n;
            n->next = NULL;
        }
        else
        {
            n->next = table[index];
            table[index] = n;
        }
        wordsize++;
    }
    fclose(file);
    loadfile = true;
    return true;
}
 

// Returns true if word is in dictionary else false
// 1. Hash word to obtain a hash value
    // Take the word and hash the word by using hash function in order to obtain a hash value
// 2. Access linked list at that index in the hash table
    // You'll access the linked list at that hash value at that particular index in your hashtable, which is an array of
    // those individual linked lists.
// 3. Traverse linked list, looking for the word(strcasecmp)
    // Once you've access that individual linked list, if that word is in the dictionary, it's going to be in that list
bool check(const char *word)
{
    // Word is constant, need a tmp variable.
    int n = strlen(word);
    char checkword[LENGTH + 1];
    for (int i = 0; i < n; i++)
    {
        checkword[i] = tolower(word[i]);
    }
    checkword[n] = '\0';
    
    int index = hash(checkword);
    
    // table is array, which is gonna be NULL
    if (table[index] != NULL)
    {
        for (node *cursor = table[index]; cursor != NULL; cursor = cursor->next)
        {
            if (strcmp(cursor->word, checkword) == 0)    
            {
                return true;
            }
        }
    }
    return false;
}



// Returns number of words in dictionary if loaded else 0 if not yet loaded
unsigned int size(void)
{
    // TODO
    if (loadfile == false)
    {
        return 0;
    }
    return wordsize;
}

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    // TODO
    if (loadfile == false)
    {
        return false;
    }
    
    for (int i = 0; i < HASHTABLE_SIZE; i++)
    {
        if (table[i] != NULL)
        {
            node *cursor = table[i];
            // https://stackoverflow.com/questions/14606466/difference-between-an-if-statement-and-while-loop
            // the difference between if and while
            while (cursor != NULL)
            {
                node *tmp = cursor;
                cursor = cursor->next;
                free(tmp);
            }
        }
        
    }
    return true;
}