-
Notifications
You must be signed in to change notification settings - Fork 0
/
AutoCompleteImpl.c
158 lines (131 loc) · 3.8 KB
/
AutoCompleteImpl.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define ALPHABET_SIZE 26
typedef enum { TRUE, FALSE } boolean;
typedef struct TrieNode{
struct TrieNode *children;
char label;
boolean isEndOfWord;
} TrieNode;
TrieNode* createNode(){
TrieNode* tnode=(TrieNode*)malloc(sizeof(TrieNode));
tnode->children=(TrieNode*)malloc(sizeof(TrieNode)*ALPHABET_SIZE);
return tnode;
}
//strLen as an integer.
int strLen(char* string){
return (int)strlen(string);
}
//Get the substring [0:String.len-1]
char* prifString(char* data){
int length=strlen(data);
char* new=(char*)malloc(sizeof(char)*(length-1));
int i;
for(i=0; i<length-1; i++){
new[i]=data[i];
}
return new;
}
//get the substring [1:String.len]
char* subString(char* data){
int length=strlen(data);
char* new=(char*)malloc(sizeof(char)*(length-1));
int i;
for(i=1; i<length; i++){
new[i-1]=data[i];
}
return new;
}
void insert(TrieNode *root,char *word){
if(strLen(word) != 0){
//Get the corresponding child object.
TrieNode* child=&(root->children[word[0]-97]);
if(child->label == 0){ //No label assigned to child.
child->label=word[0]; //Update the child
child->children=(TrieNode*)malloc(sizeof(TrieNode)*ALPHABET_SIZE);
if(strLen(word) == 1){ //End of the word
child->isEndOfWord=TRUE;
}else{ //If not insert a substring of the word to the Trie.
child->isEndOfWord=FALSE;
insert(child,subString(word));
}
}else if(child->label == word[0]){ //Sub string of word
if(strLen(word) == 1){ //End of the new Substring
child->isEndOfWord=TRUE;
}else{ //Add mode string to the Tire
insert(child,subString(word));
}
}
}else{
return;
}
}
//Print array helper function for printWors.
void printArray(int arr[],int size,char* prif){
int i;
for(i=0;i<strLen(prif); i++){
printf("%c",(char)prif[i]);
}
for(i=0;i<size;i++){
if(arr[i] != '#'){
printf("%c",(char)arr[i]);
}
}
printf("\n");
}
void printWords(TrieNode* root,int path[],int pathLen,char* pref){
path[pathLen]=root->label; //Append the character to the path[]
pathLen++;
if(root->isEndOfWord == TRUE){ //If the node isEnd then print the word.
printArray(path,pathLen,prifString(pref));
if(root->children != NULL){ //Check there are childrens to the node with longer length words.
int i;
for(i=0; i<ALPHABET_SIZE; i++){
TrieNode* child=&(root->children[i]);
if(child->label != 0){
printWords(child,path,pathLen,pref); //Call all valid childern.
}
}
}
}else{ //If it is not the end call all valid childrens
int i;
for(i=0; i<ALPHABET_SIZE; i++){
TrieNode* child=&(root->children[i]);
if(child->label != 0){
printWords(child,path,pathLen,pref);
}
}
}
}
//Given a node print all paths bellow it
void printPaths(TrieNode* node,char* pref)
{
int path[1000];
printWords(node, path, 0,pref);
}
//search for the last node in the string path
TrieNode* search(TrieNode *root,char* substring){
if(strLen(substring) == 1){ //The last label to check
TrieNode* child=&(root->children[substring[0]-97]); //Get the corresponding child
if(child->label == substring[0]){
return child; //The correct sub tree found.
}else{
return NULL;
}
}else{
TrieNode* child=&(root->children[substring[0]-97]);
if(child->label == substring[0]){
return search(child,subString(substring));//Travel through the tree
}else{
return NULL;
}
}
}
//travel through the string and find all maching words.
void traverse(char* prifix,TrieNode* root){
TrieNode* subtree=search(root,prifix);
if(subtree != NULL){
printPaths(subtree,prifix);
}
}