spacepaste

Paste details

reply | raw

  1.  
  2. // C implementation of search and insert operations
  3. // on Trie
  4. #include <stdio.h>
  5. #include <stdlib.h>
  6. #include <string.h>
  7. #include <stdbool.h>
  8. #define pi(x) printf("%s = %d\n", #x, x);
  9. #define pc(x) printf("%s = %c\n", #x, x);
  10. #define pp(x) printf("%s = %p\n", #x, x);
  11. #define ps(x) printf("%s = %s\n", #x, x);
  12. #define pb(x) printf("%s = %s\n", #x, x==true?"true":"false");
  13. struct regex_string_structure
  14. {
  15. char * string;
  16. int index;
  17. int len;
  18. int malloced;
  19. };
  21. struct regex_string
  22. {
  23. char * string;
  24. int index;
  25. int len;
  26. int malloced;
  27. };
  29. #define str_malloc_(y, z) \
  30. (y).string = malloc(z); \
  31. memset((y).string, 0, z); \
  32. (y).malloced = z; \
  33. (y).len = 0; \
  34. (y).index = 0;
  36. #define str_mallocr(y, z) \
  37. str_malloc_((y), z); \
  39. #define str_malloc(y, z) \
  40. struct regex_string y; \
  41. str_mallocr((y), z);
  43. #define str_new(str) \
  44. str_malloc(str, 1) \
  46. #define str_free_(y) \
  47. memset((y).string, 0, (y).malloced); \
  48. free((y).string); \
  49. (y).string = NULL; \
  50. (y).malloced = 0; \
  51. (y).len = 0; \
  52. (y).index = 0; \
  54. #define str_free(y) \
  55. { \
  56. str_free_((y)); \
  57. }
  59. #define str_reset_(str) { \
  60. str_free_((str)) \
  61. str_malloc_((str), 1) \
  62. }
  64. #define str_reset(str) { \
  65. str_reset_((str)) \
  66. }
  68. #define str_realloc(y, z) \
  69. (y).string = realloc((y).string, z); \
  70. if ((y).malloced < z) { \
  71. memset((y).string+(y).malloced, 0, (z)-(y).malloced); \
  72. } \
  73. (y).malloced = z;
  75. #define str_insert_char(str, ch) { \
  76. str_realloc((str), (str).malloced+2); \
  77. (str).string[(str).index] = ch; \
  78. (str).index++; \
  79. (str).string[(str).index] = 0; \
  80. (str).len = strlen((str).string); \
  81. }
  83. #define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0])
  85. // Alphabet size (# of symbols)
  86. #define ALPHABET_SIZE (26)
  88. // Converts key current character into index
  89. // use only 'a' through 'z' and lower case
  90. #define CHAR_TO_INDEX(c) ((int)c - (int)'a')
  92. // trie node
  93. struct TrieNode
  94. {
  95. struct TrieNode *children[ALPHABET_SIZE];
  96. int idx;
  98. // isEndOfWord is true if the node represents
  99. // end of a word
  100. bool isEndOfWord;
  101. };
  103. // Returns new trie node (initialized to NULLs)
  104. struct TrieNode *getNode(int idx)
  105. {
  106. struct TrieNode *pNode = NULL;
  108. pNode = (struct TrieNode *)malloc(sizeof(struct TrieNode));
  110. if (pNode)
  111. {
  112. int i;
  114. pNode->isEndOfWord = false;
  115. pNode->idx = idx;
  116. for (i = 0; i < ALPHABET_SIZE; i++)
  117. pNode->children[i] = NULL;
  118. }
  120. return pNode;
  121. }
  123. // If not present, inserts key into trie
  124. // If the key is prefix of trie node, just marks leaf node
  125. void insert(struct TrieNode *root, const char *key, int dest_idx)
  126. {
  127. int level;
  128. int length = strlen(key);
  129. int index;
  131. struct TrieNode *pCrawl = root;
  133. for (level = 0; level < length; level++)
  134. {
  135. index = CHAR_TO_INDEX(key[level]);
  136. if (!pCrawl->children[index])
  137. pCrawl->children[index] = getNode(dest_idx);
  139. else pCrawl->children[index]->idx = dest_idx;
  141. pCrawl = pCrawl->children[index];
  142. }
  144. // mark last node as leaf
  145. pCrawl->isEndOfWord = true;
  146. }
  148. // Returns true if key presents in trie, else false
  149. bool search(struct TrieNode *root, const char *key, int idx)
  150. {
  151. int level;
  152. int length = strlen(key);
  153. int index;
  154. struct TrieNode *pCrawl = root;
  155. pi(idx);
  156. for (level = 0; level < length; level++)
  157. {
  158. index = CHAR_TO_INDEX(key[level]);
  159. if (!pCrawl->children[index]) {
  160. index = CHAR_TO_INDEX('x');
  161. if (!pCrawl->children[index]) return false;
  162. }
  164. pCrawl = pCrawl->children[index];
  165. }
  167. pi(pCrawl->idx);
  168. return (pCrawl != NULL && pCrawl->isEndOfWord && pCrawl->idx == idx);
  169. }
  171. // Returns true if key presents in trie, else false
  172. bool search_segmented(struct TrieNode *root, struct TrieNode *segments, const char *key)
  173. {
  174. int level;
  175. int length = strlen(key);
  176. int index;
  177. struct TrieNode *pCrawl = root;
  179. str_new(segment);
  180. int idx = 0;
  182. for (level = 0; level < length; level++)
  183. {
  184. str_insert_char(segment, key[level]);
  186. ps(segment.string);
  187. pb(search(segments, segment.string, idx));
  188. if (search(segments, segment.string, idx)) {
  189. str_reset(segment);
  190. idx++;
  191. }
  192. index = CHAR_TO_INDEX(key[level]);
  194. if (!pCrawl->children[index]) {
  195. index = CHAR_TO_INDEX('x');
  196. if (!pCrawl->children[index]) return false;
  197. }
  199. pCrawl = pCrawl->children[index];
  200. }
  201. str_free(segment);
  202. return (pCrawl != NULL && pCrawl->isEndOfWord);
  203. }
  205. #define isp(root, segments, c) printf("%s --- %s\n", c, output[search_segmented(root, segments, c)] )
  207. // Driver
  208. int main()
  209. {
  210. char output[][32] = {"Not present in trie", "Present in trie"};
  213. struct TrieNode *root = getNode(0);
  214. struct TrieNode *segments = getNode(0);
  216. // Construct trie
  217. insert(segments, "0011", 0);
  218. insert(segments, "001", 1);
  219. insert(segments, "0", 2);
  220. insert(root, "00110010", 0);
  222. // Search for different keys
  223. isp(root, segments, "00110010");
  224. return 0;
  225. }
  226.  
Powered by spacepaste. Paste removal.