Guest User

full code: dictionary

a guest
Oct 24th, 2016
165
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /**
  2.  * dictionary.c
  3.  *
  4.  * Computer Science 50
  5.  * Problem Set 5
  6.  *
  7.  * Implements a dictionary's functionality.
  8.  */
  9.  
  10. #include <stdbool.h>
  11. #include <stdint.h> // stdint is required for the uint32_t and other type declarations for murmurhash
  12. #include <string.h>
  13. #include <stdio.h>
  14. #include <stdlib.h>
  15. #include "dictionary.h"
  16. #include <ctype.h>
  17.  
  18. // Initial values
  19.  
  20.  
  21. int num_words; // define the count of words in the dictionary
  22. int index = 0; // set an index for counting characters in 'words'
  23.  
  24. // define a structure for linear probing in hash function; will have the hash index, and the maximum distance to probe.
  25.  
  26. typedef struct trie
  27. {
  28.     bool isWord;
  29.     struct trie* children[27];
  30. } trie;
  31.  
  32. trie* head; // declare a global variable for the head of the trie
  33.  
  34. // Prototype some functions
  35.  
  36. trie* insert(char c, trie* ptr); // insert a character into the trie at an appropriate location and return a pointer to where the value was inserted
  37. bool endword(trie* wordPtr); // end the world by setting the boolean value to true
  38. bool delete(trie* node); // hopefully a recursive function to delete nodes
  39. trie* buildTrie(void); // create the head of the Trie
  40. trie* trieCheck(char c, trie* ptr); // checks to see if a character is in the list given a set location in the trie
  41.  
  42. /**
  43.  * Returns true if word is in dictionary else false.
  44.  */
  45. bool check(const char* word)
  46. {
  47.     trie* checkPtr = head;
  48.     int len = strlen(word);
  49.     for (int k = 0; k < len; k++)
  50.         {
  51.             char c2 = tolower(word[k]);
  52.             if (checkPtr != 0)
  53.             {
  54.                 checkPtr = trieCheck(c2, checkPtr);
  55.             }
  56.             else
  57.             return false;
  58.         }
  59.     if (checkPtr->isWord == 1)
  60.     {
  61.         return true;
  62.     }
  63.     else
  64.     return false;
  65. }
  66.  
  67. /**
  68.  * Loads dictionary into memory.  Returns true if successful else false.
  69.  */
  70. bool load(const char* dictionary)
  71. {
  72.     /**
  73.      * We'll load each word character by character into a trie. Once a word is ended we'll set the boolean to true
  74.      **/
  75.     head = buildTrie(); // buildTrie returns a pointer to head
  76.     FILE* fp = fopen(dictionary, "r");
  77.     if (fp == NULL)
  78.     {
  79.         printf("Could not open %s.\n", dictionary);
  80.         unload();
  81.         return 1;
  82.     }
  83.     // to insert the words into the trie, we will start at the head, and then add letter by letter
  84.     // inside of word, we'll use the function insert to allocate memory for new letters, returning pointers to the new memory or the memory that is there
  85.     // this way we keep progress and don't have to start at the beginning of the word - nor do we have to keep the word in a buffer, we can go char by char
  86.     // when the word is done, we set the pointer to the head of the trie, and restart the process;
  87.  
  88.     trie* wordPtr = head;
  89.     for (int c = fgetc(fp); c != EOF; c = fgetc(fp))
  90.         {
  91.             if (isalpha(c) || (c == '\'' && index > 0))
  92.             {
  93.                 wordPtr = insert(c, wordPtr);
  94.                 index++;
  95.             }
  96.            
  97.             else if (index > 0)
  98.             {
  99.                // update counter
  100.                 num_words++;
  101.                 endword(wordPtr);
  102.                 wordPtr = head;
  103.                 index = 0;
  104.             }
  105.         }
  106.     fclose(fp);
  107.     return false;
  108. }
  109.  
  110. /**
  111.  * Returns number of words in dictionary if loaded else 0 if not yet loaded.
  112.  */
  113. unsigned int size(void)
  114. {
  115.     // since num_words is a good proxy for whether we loaded a dictionary (unless it's size zero, which is the same thing)
  116.     // we just return the number of words loaded.
  117.     return num_words;
  118. }
  119.  
  120. /**
  121.  * Unloads dictionary from memory.  Returns true if successful else false.
  122.  */
  123. bool unload(void)
  124. {
  125.     if (delete(head) == true)
  126.     {
  127.         return 0;
  128.     }
  129.     else
  130.         return -1;
  131. }
  132.  
  133. trie* insert(char c, trie* ptr)
  134. {
  135.     if (c == '\'' && ptr->children[26] == 0)
  136.     {
  137.         ptr->children[26] = calloc(1, sizeof(trie));
  138.         return ptr->children[26];
  139.     }
  140.     else if (c == '\'' && ptr->children[26] != 0)
  141.     {
  142.         return ptr->children[26];
  143.     }
  144.     if (ptr->children[c -'a'] == 0)
  145.     {
  146.         ptr->children[c - 'a'] = calloc(1, sizeof(trie));
  147.         return ptr->children[c - 'a'];
  148.     }
  149.     else
  150.     {
  151.         // check to see if our logic is tight - in this instance there should already be a place there.
  152.         // assert(ptr->children[c - 'a']);
  153.         return ptr->children[c - 'a'];
  154.     }
  155. }
  156.  
  157. trie* trieCheck(char c, trie* checkPtr)
  158. {
  159.     if (c == '\'' && checkPtr->children[26] == 0)
  160.     {
  161.         return 0;
  162.     }
  163.     else if (c == '\'' && checkPtr->children[26] != 0)
  164.     {
  165.         return checkPtr->children[26];
  166.     }
  167.     if (checkPtr->children[c -'a'] == 0)
  168.     {
  169.         return 0;
  170.     }
  171.     else
  172.     {
  173.         // check to see if our logic is tight - in this instance there should already be a place there.
  174.         // assert(ptr->children[c - 'a']);
  175.         return checkPtr->children[c - 'a'];
  176.     }
  177. }
  178.  
  179. bool endword(trie* wordPtr)
  180. {
  181.     wordPtr->isWord = 1;
  182.     return 0;
  183. }
  184.    
  185. trie* buildTrie(void)
  186. {
  187.     return (trie*)calloc(1, sizeof(trie));
  188. }
  189.  
  190.  
  191.  
  192. bool delete(trie* deleteptr)
  193. {
  194.     for (int i = 0; i < 27; i++)
  195.         {
  196.             if(deleteptr->children[i] != NULL)
  197.             {
  198.                 deleteptr = deleteptr->children[i];
  199.                 delete(deleteptr);
  200.             }
  201.         }
  202.     free(deleteptr);
  203.     return 0;
  204. }
  205. /*
  206. bool wrd_insert(uint32_t key, char word[])
  207. {
  208.     if (dctnry[key] == NULL)
  209.         {
  210.             strcpy(dctnry[key], word);
  211.         }
  212.        
  213.         else
  214.         {
  215.             collisions[num_col].index = key;
  216.             collisions[num_col].probe += 1;
  217.             num_col++;
  218.             key += 1;
  219.             wrd_insert(key, word);
  220.         }
  221. }
  222. */
RAW Paste Data