$ ./trie_binary ----------------------------------------------------------------------->called init_aux() at line 348 from ../Shell/builtins/libstring.h ----------------------------------------------------------------------->called init_env() at line 327 from ../Shell/builtins/libstring.h ----------------------------------------------------------------------->called init_argX() at line 336 from ../Shell/builtins/libstring.h adding rule 1: segments [1, 0] root [10] adding rule 2: segments [0, 1] root [01] adding rule 3: root [00] segment.string = 1 key = 1 idx = 0 pCrawl->count = 2 pCrawl->idx[i] = 0 pCrawl->idx[i] = 1 final_match = true result = true segment.string = 0 key = 0 idx = 1 pCrawl->count = 2 pCrawl->idx[i] = 1 pCrawl->idx[i] = 0 final_match = true result = true 10 --- Present in trie segment.string = 0 key = 0 idx = 0 pCrawl->count = 2 pCrawl->idx[i] = 1 pCrawl->idx[i] = 0 final_match = true result = true segment.string = 1 key = 1 idx = 1 pCrawl->count = 2 pCrawl->idx[i] = 0 pCrawl->idx[i] = 1 final_match = true result = true 01 --- Present in trie segment.string = 0 key = 0 idx = 0 pCrawl->count = 2 pCrawl->idx[i] = 1 pCrawl->idx[i] = 0 final_match = true result = true segment.string = 0 key = 0 idx = 1 pCrawl->count = 2 pCrawl->idx[i] = 1 pCrawl->idx[i] = 0 final_match = true result = true 00 --- Present in trie $ cat ./trie_binary.c // C implementation of search and insert operations // on Trie #include #include #include #include // printf shorthand macros #include "../Shell/builtins/printfmacro.h" // string library and strying type identification #include "../Shell/builtins/regex_str.h" #define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0]) // Alphabet size (# of symbols) #define ALPHABET_SIZE (26) // Converts key current character into index // use only 'a' through 'z' and lower case #define CHAR_TO_INDEX(c) ((int)c - (int)'a') #define INT_TO_INDEX(c) ((int)c - (int)'0') // trie node struct TrieNode { struct TrieNode *children[ALPHABET_SIZE]; int * idx; int count; // isEndOfWord is true if the node represents // end of a word bool isEndOfWord; }; // Returns new trie node (initialized to NULLs) struct TrieNode *getNode(void) { struct TrieNode *pNode = NULL; pNode = (struct TrieNode *)malloc(sizeof(struct TrieNode)); if (pNode) { int i; pNode->isEndOfWord = false; pNode->idx = NULL; pNode->count = 0; for (i = 0; i < ALPHABET_SIZE; i++) pNode->children[i] = NULL; } return pNode; } // If not present, inserts key into trie // If the key is prefix of trie node, just marks leaf node void insert(struct TrieNode *root, const char *key, int dest_idx) { int level; int length = strlen(key); int index; struct TrieNode *pCrawl = root; // pi(dest_idx) for (level = 0; level < length; level++) { // pi(level); // pc(key[level]) str_new(ch); str_insert_char(ch, key[level]); if (ch.type & STR_TYPE_DIGIT) index = INT_TO_INDEX(key[level]); else if (ch.type & STR_TYPE_ALPHABETIC) index = CHAR_TO_INDEX(key[level]); str_free(ch) // pi(index) // pp(pCrawl->children[index]) if (!pCrawl->children[index]) { pCrawl->children[index] = getNode(); } if (level == length-1) { // pp(pCrawl->children[index]) // pp(pCrawl->children[index]->idx) pCrawl->children[index]->count++; if (!pCrawl->children[index]->idx) { pCrawl->children[index]->idx = malloc(sizeof(int*)*pCrawl->children[index]->count); // pp(pCrawl->children[index]->idx) } else { pCrawl->children[index]->idx = realloc(pCrawl->children[index]->idx, sizeof(int*)*pCrawl->children[index]->count); } pCrawl->children[index]->idx[pCrawl->children[index]->count-1] = dest_idx; // pi(pCrawl->children[index]->idx[pCrawl->children[index]->count-1]) } pCrawl = pCrawl->children[index]; } // mark last node as leaf pCrawl->isEndOfWord = true; } // Returns true if key presents in trie, else false bool search(struct TrieNode *root, const char *key, int idx) { int level; int length = strlen(key); int index; struct TrieNode *pCrawl = root; // pi(idx); for (level = 0; level < length; level++) { str_new(ch); str_insert_char(ch, key[level]); if (ch.type & STR_TYPE_DIGIT) index = INT_TO_INDEX(key[level]); else if (ch.type & STR_TYPE_ALPHABETIC) index = CHAR_TO_INDEX(key[level]); str_free(ch) if (!pCrawl->children[index]) { index = CHAR_TO_INDEX('x'); if (!pCrawl->children[index]) return false; } pCrawl = pCrawl->children[index]; } ps(key); pi(idx); pi(pCrawl->count) bool final_match = false; for (int i = 0; i < pCrawl->count; i++) { pi(pCrawl->idx[i]) if (pCrawl->idx[i] == idx) final_match = true; } pb(final_match) return (pCrawl != NULL && pCrawl->isEndOfWord && final_match); } // Returns true if key presents in trie, else false bool search_segmented(struct TrieNode *root, struct TrieNode *segments, const char *key) { int level; int length = strlen(key); int index; struct TrieNode *pCrawl = root; str_new(segment); int idx = 0; for (level = 0; level < length; level++) { str_insert_char(segment, key[level]); ps(segment.string); bool result = search(segments, segment.string, idx); pb(result); if (result) { str_reset(segment); idx++; } str_new(ch); str_insert_char(ch, key[level]); if (ch.type & STR_TYPE_DIGIT) index = INT_TO_INDEX(key[level]); else if (ch.type & STR_TYPE_ALPHABETIC) index = CHAR_TO_INDEX(key[level]); str_free(ch) if (!pCrawl->children[index]) { index = CHAR_TO_INDEX('x'); if (!pCrawl->children[index]) return false; } pCrawl = pCrawl->children[index]; } str_free(segment); return (pCrawl != NULL && pCrawl->isEndOfWord); } #define isp(root, segments, c) printf("%s --- %s\n", c, output[search_segmented(root, segments, c)] ) // Driver int main() { char output[][32] = {"Not present in trie", "Present in trie"}; struct TrieNode *root = getNode(); struct TrieNode *segments = getNode(); // Construct trie /* shall aim to be equivilant to this rule_1 ::= "1" "0"; rule_2 ::= "0" "1"; rule_3 ::= "0" "0"; */ // rule 1 puts("adding rule 1: segments [1, 0] root [10]"); insert(segments, "1", 0); insert(segments, "0", 1); insert(root, "10", 0); // rule 2 puts("adding rule 2: segments [0, 1] root [01]"); insert(segments, "0", 0); insert(segments, "1", 1); insert(root, "01", 0); puts("adding rule 3: root [00]"); // no segments, needs to confirm segment to rule isolation, currently this seems impossible in a trie insert(root, "00", 0); // Search for different keys isp(root, segments, "10"); isp(root, segments, "01"); isp(root, segments, "00"); return 0; }