tree build

 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
/*void SuffixTree::initializationFromContainer(ConcatenatedUnistringContainer &container) {
long value = 0;
std::vector<long> permutation = container.suffixArray();
for (long i = 0; i < permutation.size(); i++) {
container.getUnichar(i).print();
//std::cout << std::endl;
}
std::queue<Task *> task_queue = std::queue<Task *>();
root = new TreeVertex(value++);
task_queue.push(new Task(root, 0, permutation.size() - 1, 0));
while (!task_queue.empty()) {
Task *task_current = task_queue.front();
task_queue.pop();
std::vector<long> factor_positions = std::vector<long>();
std::vector<int> lcp_values = std::vector<int>();
long low = task_current->left_bound;
long high = task_current->right_bound;
int cutted_prefix_len = task_current->cutted_prefix_len;
while (low < high) {
long middle = (high - low) >> 1;
if (low >= high) {
task_current->vertex->children[container.getUnichar(low + cutted_prefix_len)] = new TreeVertex(value++);
std::cout << "next factor point: " << middle << std::endl;
}
int lcp1 = container.LCP(low, middle);
int lcp2 = container.LCP(low, middle + 1);
if (lcp1 > lcp2 && lcp2 == cutted_prefix_len) {
task_current->vertex->children[container.getUnichar(low + cutted_prefix_len)] = new TreeVertex(value++);
low = middle + 1;
std::cout << "next factor point: " << middle << std::endl;
}
if (lcp2 > cutted_prefix_len) {
low = middle + 1;
}
if (lcp1 == cutted_prefix_len) {
high = middle - 1;
}
}
}
}*/