spacepaste

Paste details

reply | raw

  1.  
  2. $ ./trie_binary
  3. ----------------------------------------------------------------------->called init_aux() at line 348 from ../Shell/builtins/libstring.h
  4. ----------------------------------------------------------------------->called init_env() at line 327 from ../Shell/builtins/libstring.h
  5. ----------------------------------------------------------------------->called init_argX() at line 336 from ../Shell/builtins/libstring.h
  6. adding rule 1: segments [1, 0] root [10]
  7. adding rule 2: segments [0, 1] root [01]
  8. adding rule 3: root [00]
  9. segment.string = 1
  10. result = true
  11. segment.string = 0
  12. result = true
  13. 10 --- Present in trie
  14. segment.string = 0
  15. result = true
  16. segment.string = 1
  17. result = true
  18. 01 --- Present in trie
  19. segment.string = 0
  20. result = true
  21. segment.string = 0
  22. result = false
  23. 00 --- Present in trie
  25. $ cat ./trie_binary.c
  26. // C implementation of search and insert operations
  27. // on Trie
  28. #include <stdio.h>
  29. #include <stdlib.h>
  30. #include <string.h>
  31. #include <stdbool.h>
  32. #include "../Shell/builtins/printfmacro.h"
  33. #include "../Shell/builtins/regex_str.h"
  36. #define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0])
  38. // Alphabet size (# of symbols)
  39. #define ALPHABET_SIZE (26)
  41. // Converts key current character into index
  42. // use only 'a' through 'z' and lower case
  43. #define CHAR_TO_INDEX(c) ((int)c - (int)'a')
  44. #define INT_TO_INDEX(c) ((int)c - (int)'0')
  46. // trie node
  47. struct TrieNode
  48. {
  49. struct TrieNode *children[ALPHABET_SIZE];
  50. int * idx;
  51. int count;
  52. // isEndOfWord is true if the node represents
  53. // end of a word
  54. bool isEndOfWord;
  55. struct TrieNode * next;
  56. };
  58. // Returns new trie node (initialized to NULLs)
  59. struct TrieNode *getNode(void)
  60. {
  61. struct TrieNode *pNode = NULL;
  63. pNode = (struct TrieNode *)malloc(sizeof(struct TrieNode));
  65. if (pNode)
  66. {
  67. int i;
  69. pNode->isEndOfWord = false;
  70. pNode->idx = NULL;
  71. pNode->count = 0;
  72. for (i = 0; i < ALPHABET_SIZE; i++)
  73. pNode->children[i] = NULL;
  74. }
  76. return pNode;
  77. }
  79. // If not present, inserts key into trie
  80. // If the key is prefix of trie node, just marks leaf node
  81. void insert(struct TrieNode *root, const char *key, int dest_idx, struct TrieNode *next)
  82. {
  83. int level;
  84. int length = strlen(key);
  85. int index;
  87. struct TrieNode *pCrawl = root;
  88. // pi(dest_idx)
  89. for (level = 0; level < length; level++)
  90. {
  91. // pi(level);
  92. // pc(key[level])
  93. str_new(ch);
  94. str_insert_char(ch, key[level]);
  95. if (ch.type & STR_TYPE_DIGIT) index = INT_TO_INDEX(key[level]);
  96. else if (ch.type & STR_TYPE_ALPHABETIC) index = CHAR_TO_INDEX(key[level]);
  97. str_free(ch)
  98. // pi(index)
  99. // pp(pCrawl->children[index])
  100. if (!pCrawl->children[index]) {
  101. pCrawl->children[index] = getNode();
  102. }
  104. if (level == length-1) {
  105. // pp(pCrawl->children[index])
  106. // pp(pCrawl->children[index]->idx)
  107. pCrawl->children[index]->next = next;
  108. pCrawl->children[index]->count++;
  109. if (!pCrawl->children[index]->idx) {
  110. pCrawl->children[index]->idx = malloc(sizeof(int*)*pCrawl->children[index]->count);
  111. // pp(pCrawl->children[index]->idx)
  112. }
  113. else {
  114. pCrawl->children[index]->idx = realloc(pCrawl->children[index]->idx, sizeof(int*)*pCrawl->children[index]->count);
  115. }
  116. pCrawl->children[index]->idx[pCrawl->children[index]->count-1] = dest_idx;
  117. // pi(pCrawl->children[index]->idx[pCrawl->children[index]->count-1])
  118. }
  120. pCrawl = pCrawl->children[index];
  121. }
  123. // mark last node as leaf
  124. pCrawl->isEndOfWord = true;
  125. }
  127. // Returns true if key presents in trie, else false
  128. bool search(struct TrieNode **root, const char *key, int idx)
  129. {
  130. int level;
  131. int length = strlen(key);
  132. int index;
  133. struct TrieNode *pCrawl = *root;
  134. // pi(idx);
  135. for (level = 0; level < length; level++)
  136. {
  137. str_new(ch);
  138. str_insert_char(ch, key[level]);
  139. if (ch.type & STR_TYPE_DIGIT) index = INT_TO_INDEX(key[level]);
  140. else if (ch.type & STR_TYPE_ALPHABETIC) index = CHAR_TO_INDEX(key[level]);
  141. str_free(ch)
  142. if (!pCrawl->children[index]) {
  143. index = CHAR_TO_INDEX('x');
  144. if (!pCrawl->children[index]) return false;
  145. }
  147. pCrawl = pCrawl->children[index];
  148. // pp(pCrawl->next);
  149. if (pCrawl->next) {
  150. // pi(pCrawl->next->idx)
  151. // pp(*root)
  152. *root = pCrawl->next;
  153. // pp(*root)
  154. // bool result = search(pCrawl->next, key, idx);
  155. // pb(result);
  156. }
  157. }
  159. // pi(pCrawl->count)
  160. bool final_match = false;
  161. for (int i = 0; i < pCrawl->count; i++) {
  162. // pi(pCrawl->idx[i])
  163. if (pCrawl->idx[i] == idx) final_match = true;
  164. }
  165. // pb(final_match)
  166. return (pCrawl != NULL && pCrawl->isEndOfWord && final_match);
  167. }
  169. // Returns true if key presents in trie, else false
  170. bool search_segmented(struct TrieNode *root, struct TrieNode *segments, const char *key)
  171. {
  172. int level;
  173. int length = strlen(key);
  174. int index;
  175. struct TrieNode *pCrawl = root;
  177. str_new(segment);
  178. int idx = 0;
  180. for (level = 0; level < length; level++)
  181. {
  182. str_insert_char(segment, key[level]);
  184. ps(segment.string);
  185. // pp(segments)
  186. bool result = search(&segments, segment.string, idx);
  187. // pp(segments)
  188. pb(result);
  189. if (result) {
  190. str_reset(segment);
  191. idx++;
  192. }
  193. str_new(ch);
  194. str_insert_char(ch, key[level]);
  195. if (ch.type & STR_TYPE_DIGIT) index = INT_TO_INDEX(key[level]);
  196. else if (ch.type & STR_TYPE_ALPHABETIC) index = CHAR_TO_INDEX(key[level]);
  197. str_free(ch)
  199. if (!pCrawl->children[index]) {
  200. index = CHAR_TO_INDEX('x');
  201. if (!pCrawl->children[index]) return false;
  202. }
  204. pCrawl = pCrawl->children[index];
  205. }
  206. str_free(segment);
  207. return (pCrawl != NULL && pCrawl->isEndOfWord);
  208. }
  210. #define isp(root, segments, c) printf("%s --- %s\n", c, output[search_segmented(root, segments, c)] )
  212. // Driver
  213. int main()
  214. {
  215. char output[][32] = {"Not present in trie", "Present in trie"};
  217. /*
  218. // Construct trie
  219. insert(segments, "0011", 0, segments1);
  220. pp(segments->next)
  221. insert(segments1, "001", 1, NULL);
  222. insert(segments1, "0", 2, NULL);
  223. insert(segments1, "0", 3, NULL);
  224. insert(root, "001100100", 0, NULL);
  226. // Search for different keys
  227. isp(root, segments, "001100100");
  228. */
  230. // Construct trie
  232. /* shall aim to be equivilant to this
  234. rule_1 ::= "1" "0";
  235. rule_2 ::= "0" "1";
  236. rule_3 ::= "0" "0";
  238. */
  239. // rule 1
  240. struct TrieNode *root = getNode();
  241. struct TrieNode *sub_root = getNode();
  242. struct TrieNode *rule_1 = getNode();
  243. struct TrieNode *rule_2 = getNode();
  245. // when adding a new rule indexing resets to 0
  247. puts("adding rule 1: segments [1, 0] root [10]");
  248. insert(root, "10", 0, NULL);
  249. insert(sub_root, "1", 0, rule_1);
  250. insert(rule_1, "0", 1, NULL);
  252. puts("adding rule 2: segments [0, 1] root [01]");
  253. insert(root, "01", 0, NULL);
  254. insert(sub_root, "0", 0, rule_2);
  255. insert(rule_2, "1", 1, NULL);
  257. puts("adding rule 3: root [00]");
  258. insert(root, "00", 0, NULL);
  259. // Search for different keys
  260. isp(root, sub_root, "10");
  261. isp(root, sub_root, "01");
  262. isp(root, sub_root, "00");
  263. return 0;
  264. }
  265.  
Powered by spacepaste. Paste removal.