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. key = 1
  11. idx = 0
  12. pCrawl->count = 2
  13. pCrawl->idx[i] = 0
  14. pCrawl->idx[i] = 1
  15. final_match = true
  16. result = true
  17. segment.string = 0
  18. key = 0
  19. idx = 1
  20. pCrawl->count = 2
  21. pCrawl->idx[i] = 1
  22. pCrawl->idx[i] = 0
  23. final_match = true
  24. result = true
  25. 10 --- Present in trie
  26. segment.string = 0
  27. key = 0
  28. idx = 0
  29. pCrawl->count = 2
  30. pCrawl->idx[i] = 1
  31. pCrawl->idx[i] = 0
  32. final_match = true
  33. result = true
  34. segment.string = 1
  35. key = 1
  36. idx = 1
  37. pCrawl->count = 2
  38. pCrawl->idx[i] = 0
  39. pCrawl->idx[i] = 1
  40. final_match = true
  41. result = true
  42. 01 --- Present in trie
  43. segment.string = 0
  44. key = 0
  45. idx = 0
  46. pCrawl->count = 2
  47. pCrawl->idx[i] = 1
  48. pCrawl->idx[i] = 0
  49. final_match = true
  50. result = true
  51. segment.string = 0
  52. key = 0
  53. idx = 1
  54. pCrawl->count = 2
  55. pCrawl->idx[i] = 1
  56. pCrawl->idx[i] = 0
  57. final_match = true
  58. result = true
  59. 00 --- Present in trie
  61. $ cat ./trie_binary.c
  62. // C implementation of search and insert operations
  63. // on Trie
  64. #include <stdio.h>
  65. #include <stdlib.h>
  66. #include <string.h>
  67. #include <stdbool.h>
  69. // printf shorthand macros
  70. #include "../Shell/builtins/printfmacro.h"
  72. // string library and strying type identification
  73. #include "../Shell/builtins/regex_str.h"
  76. #define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0])
  78. // Alphabet size (# of symbols)
  79. #define ALPHABET_SIZE (26)
  81. // Converts key current character into index
  82. // use only 'a' through 'z' and lower case
  83. #define CHAR_TO_INDEX(c) ((int)c - (int)'a')
  84. #define INT_TO_INDEX(c) ((int)c - (int)'0')
  86. // trie node
  87. struct TrieNode
  88. {
  89. struct TrieNode *children[ALPHABET_SIZE];
  90. int * idx;
  91. int count;
  92. // isEndOfWord is true if the node represents
  93. // end of a word
  94. bool isEndOfWord;
  95. };
  97. // Returns new trie node (initialized to NULLs)
  98. struct TrieNode *getNode(void)
  99. {
  100. struct TrieNode *pNode = NULL;
  102. pNode = (struct TrieNode *)malloc(sizeof(struct TrieNode));
  104. if (pNode)
  105. {
  106. int i;
  108. pNode->isEndOfWord = false;
  109. pNode->idx = NULL;
  110. pNode->count = 0;
  111. for (i = 0; i < ALPHABET_SIZE; i++)
  112. pNode->children[i] = NULL;
  113. }
  115. return pNode;
  116. }
  118. // If not present, inserts key into trie
  119. // If the key is prefix of trie node, just marks leaf node
  120. void insert(struct TrieNode *root, const char *key, int dest_idx)
  121. {
  122. int level;
  123. int length = strlen(key);
  124. int index;
  126. struct TrieNode *pCrawl = root;
  127. // pi(dest_idx)
  128. for (level = 0; level < length; level++)
  129. {
  130. // pi(level);
  131. // pc(key[level])
  132. str_new(ch);
  133. str_insert_char(ch, key[level]);
  134. if (ch.type & STR_TYPE_DIGIT) index = INT_TO_INDEX(key[level]);
  135. else if (ch.type & STR_TYPE_ALPHABETIC) index = CHAR_TO_INDEX(key[level]);
  136. str_free(ch)
  137. // pi(index)
  138. // pp(pCrawl->children[index])
  139. if (!pCrawl->children[index]) {
  140. pCrawl->children[index] = getNode();
  141. }
  143. if (level == length-1) {
  144. // pp(pCrawl->children[index])
  145. // pp(pCrawl->children[index]->idx)
  146. pCrawl->children[index]->count++;
  147. if (!pCrawl->children[index]->idx) {
  148. pCrawl->children[index]->idx = malloc(sizeof(int*)*pCrawl->children[index]->count);
  149. // pp(pCrawl->children[index]->idx)
  150. }
  151. else {
  152. pCrawl->children[index]->idx = realloc(pCrawl->children[index]->idx, sizeof(int*)*pCrawl->children[index]->count);
  153. }
  154. pCrawl->children[index]->idx[pCrawl->children[index]->count-1] = dest_idx;
  155. // pi(pCrawl->children[index]->idx[pCrawl->children[index]->count-1])
  156. }
  158. pCrawl = pCrawl->children[index];
  159. }
  161. // mark last node as leaf
  162. pCrawl->isEndOfWord = true;
  163. }
  165. // Returns true if key presents in trie, else false
  166. bool search(struct TrieNode *root, const char *key, int idx)
  167. {
  168. int level;
  169. int length = strlen(key);
  170. int index;
  171. struct TrieNode *pCrawl = root;
  172. // pi(idx);
  173. for (level = 0; level < length; level++)
  174. {
  175. str_new(ch);
  176. str_insert_char(ch, key[level]);
  177. if (ch.type & STR_TYPE_DIGIT) index = INT_TO_INDEX(key[level]);
  178. else if (ch.type & STR_TYPE_ALPHABETIC) index = CHAR_TO_INDEX(key[level]);
  179. str_free(ch)
  180. if (!pCrawl->children[index]) {
  181. index = CHAR_TO_INDEX('x');
  182. if (!pCrawl->children[index]) return false;
  183. }
  185. pCrawl = pCrawl->children[index];
  186. }
  187. ps(key);
  188. pi(idx);
  189. pi(pCrawl->count)
  190. bool final_match = false;
  191. for (int i = 0; i < pCrawl->count; i++) {
  192. pi(pCrawl->idx[i])
  193. if (pCrawl->idx[i] == idx) final_match = true;
  194. }
  195. pb(final_match)
  196. return (pCrawl != NULL && pCrawl->isEndOfWord && final_match);
  197. }
  199. // Returns true if key presents in trie, else false
  200. bool search_segmented(struct TrieNode *root, struct TrieNode *segments, const char *key)
  201. {
  202. int level;
  203. int length = strlen(key);
  204. int index;
  205. struct TrieNode *pCrawl = root;
  207. str_new(segment);
  208. int idx = 0;
  210. for (level = 0; level < length; level++)
  211. {
  212. str_insert_char(segment, key[level]);
  214. ps(segment.string);
  215. bool result = search(segments, segment.string, idx);
  216. pb(result);
  217. if (result) {
  218. str_reset(segment);
  219. idx++;
  220. }
  221. str_new(ch);
  222. str_insert_char(ch, key[level]);
  223. if (ch.type & STR_TYPE_DIGIT) index = INT_TO_INDEX(key[level]);
  224. else if (ch.type & STR_TYPE_ALPHABETIC) index = CHAR_TO_INDEX(key[level]);
  225. str_free(ch)
  227. if (!pCrawl->children[index]) {
  228. index = CHAR_TO_INDEX('x');
  229. if (!pCrawl->children[index]) return false;
  230. }
  232. pCrawl = pCrawl->children[index];
  233. }
  234. str_free(segment);
  235. return (pCrawl != NULL && pCrawl->isEndOfWord);
  236. }
  238. #define isp(root, segments, c) printf("%s --- %s\n", c, output[search_segmented(root, segments, c)] )
  240. // Driver
  241. int main()
  242. {
  243. char output[][32] = {"Not present in trie", "Present in trie"};
  246. struct TrieNode *root = getNode();
  247. struct TrieNode *segments = getNode();
  249. // Construct trie
  251. /* shall aim to be equivilant to this
  253. rule_1 ::= "1" "0";
  254. rule_2 ::= "0" "1";
  255. rule_3 ::= "0" "0";
  257. */
  258. // rule 1
  259. puts("adding rule 1: segments [1, 0] root [10]");
  260. insert(segments, "1", 0);
  261. insert(segments, "0", 1);
  262. insert(root, "10", 0);
  263. // rule 2
  264. puts("adding rule 2: segments [0, 1] root [01]");
  265. insert(segments, "0", 0);
  266. insert(segments, "1", 1);
  267. insert(root, "01", 0);
  269. puts("adding rule 3: root [00]"); // no segments, needs to confirm segment to rule isolation, currently this seems impossible in a trie
  270. insert(root, "00", 0);
  272. // Search for different keys
  273. isp(root, segments, "10");
  274. isp(root, segments, "01");
  275. isp(root, segments, "00");
  276. return 0;
  277. }
  278.  
Powered by spacepaste. Paste removal.