CS50- PSET5

Dictionary.c

// Implements a dictionary's functionality

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

#include "dictionary.h"
#define HASH_SIZE 10000

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

node* hashtable[HASH_SIZE]; // an array of pointer to nodes

int word_count = 0; // global word counts variable

//Hash function via https://www.reddit.com/r/cs50/comments/1x6vc8/pset6_trie_vs_hashtable/cf9nlkn/
// Hashes word to a number
int hash_it(char* needs_hashing)
{
    unsigned int hash = 0;
    for (int i = 0, n = strlen(needs_hashing); i < n; i++)
        hash = (hash << 2) ^ needs_hashing[i];
    return hash % HASH_SIZE;
}


// Returns true if word is in dictionary else false
bool check(const char *word)
{
   // (1) create a copy of the word
   int length = strlen(word); 
   char copy [LENGTH + 1];
   
   // (2) convert into lower case and store in copy
   for (int i = 0; i < length; i++)
   {
       copy[i] = tolower (word[i]);
   }
   copy[length] = '\0';
   
   // (3) hash the copy and point the cursor to the right box in the hashtable
   int copy_index = hash_it (copy); 
   node *cursor = hashtable[copy_index];
   
   // (4) compare the word with where the cursor is pointing, return true if same, else advance
   while (cursor != NULL)
   {
        if (strcasecmp(cursor -> word, copy) == 0)
        {
            return true;
        }
        else
        {
            cursor = cursor->next;
        }
   }
   // (5) return false if reached the end and couldn't find
    return false;
}


// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    // (1) open file to read, return false if null  
    FILE *file = fopen (dictionary, "r");
    if (file == NULL)
    {
        return false; 
    }
    // (2) scan words in dictionary, and hash them 
    char word [LENGTH + 1];
    while (fscanf (file, "%s", word) != EOF)
    {
        node *new_node = malloc (sizeof(node));  //assign memory for new node 
        if (new_node == NULL) // safety check
        {
            unload (); 
            return false; 
        }
        strcpy(new_node -> word, word); //copies word into new node
        int h = hash_it (new_node -> word); // hashes the word 
       
        // (3) insert the new hashed word into the hash table
        node *head = hashtable[h]; // Initializes head to point to hashtable index/bucket
        if (head == NULL) // new nodes go to the beginning 
        {
            hashtable [h] = new_node; 
            word_count++;
        }
        else 
        {
            new_node -> next = hashtable [h]; 
            hashtable [h] = new_node;
            word_count++; 
        }
    }
    fclose (file);
    return true;
}
    
// Returns number of words in dictionary if loaded else 0 if not yet loaded
unsigned int size(void)
{
    return word_count;
}

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    node *head = NULL;
    node *cursor = head;
    // freeing linked lists
    while (cursor != NULL)
    {
        node *temp = cursor;
        cursor = cursor->next;
        free(temp);
    }
    return true;
}