1 #include <iostream>
2 #include <fstream>
3 #include <vector>
4 #include "testlib/testlib_test.h"
5 #include "testlib/testlib_root_dir.h"
6
7 #include <bstm/bstm_time_tree.h>
8
9 #ifdef _MSC_VER
10 # include "vcl_msvc_warnings.h"
11 #endif
12
13
14
15 #define DATA_LEN 80
16
ingest(bstm_time_tree & tree,char * tree_data,float time,char data)17 void ingest(bstm_time_tree& tree, char* tree_data ,float time, char data)
18 {
19 bstm_time_tree old_tree(tree);
20
21 //first check curr data is same as ingested data
22 int offset = tree.get_relative_index( tree.traverse(time));
23 if (data != tree_data[offset])
24 {
25 bool split_complete = false;
26 while (!split_complete)
27 {
28 int curr_cell = tree.traverse(time);
29 int currDepth = tree.depth_at(curr_cell);
30
31 float cell_min,cell_max;
32 tree.cell_range(curr_cell, cell_min,cell_max);
33 if (cell_min == time) //found cell starting at queried time.
34 {
35 split_complete = true;
36 }
37 else if (currDepth < 5)
38 {
39 tree.set_bit_at(curr_cell,true);
40 }
41 else //reached end of tree...
42 split_complete = true;
43 }
44
45 //move data
46 int newSize = tree.num_cells();
47 char new_data[DATA_LEN];
48
49 int cellsMoved = 0;
50 int oldDataPtr = 0;
51 int newDataPtr = 0;
52 int newInitCount = 0;
53 for (int j=0; j < 63 && cellsMoved<newSize; ++j)
54 {
55 //--------------------------------------------------------------------
56 //4 Cases:
57 // - Old cell and new cell exist - transfer data over
58 // - new cell exists, old cell doesn't - create new occupancy based on depth
59 // - old cell exists, new cell doesn't - uh oh this is bad news
60 // - neither cell exists - do nothing and carry on
61 //--------------------------------------------------------------------
62 //if parent bit is 1, then you're a valid cell
63 int pj = old_tree.parent_index(j); //Bit_index of parent bit
64 bool validCellOld = (j==0) || old_tree.bit_at(pj);
65 bool validCellNew = (j==0) || tree.bit_at(pj);
66 if (validCellOld && validCellNew) {
67 //move root data to new location
68 new_data[newDataPtr] = tree_data[oldDataPtr];
69
70 //increment
71 ++oldDataPtr;
72 ++newDataPtr;
73 ++cellsMoved;
74 }
75 //case where it's a new leaf...
76 else if (validCellNew) {
77 //find parent in old tree
78 int valid_parent_bit = pj;
79 while ( valid_parent_bit !=0 && !old_tree.bit_at( old_tree.parent_index(valid_parent_bit) ) )
80 valid_parent_bit = old_tree.parent_index(valid_parent_bit);
81
82 new_data[newDataPtr] = tree_data[ old_tree.get_relative_index(valid_parent_bit) ];
83
84 //update new data pointer
85 ++newDataPtr;
86 ++newInitCount;
87 ++cellsMoved;
88 }
89 }
90 //write new data in
91 new_data[ tree.get_relative_index( tree.traverse(time)) ] = data;
92 std::cout << "Placing " << data << " to " << tree.get_relative_index( tree.traverse(time)) << std::endl;
93 for (int i = 0; i < DATA_LEN; tree_data[i] = new_data[i], ++i); //copy new data into old data
94 }
95 }
96
test_time_tree_ingestion()97 void test_time_tree_ingestion()
98 {
99 char data[] = {'a','a','b','c',
100 'd','d','e','d',
101 'a','a','a','a',
102 'b','a','a','b',
103 'a','a','b','c',
104 'g','h','g','h',
105 'f','f','f','f',
106 'f','f','f','f'}; //DATA_LEN
107 char* tree_data = new char[DATA_LEN];
108 for (int i = 0; i < DATA_LEN; ++i) tree_data[i] = '0';
109
110 bstm_time_tree tree;
111
112 for (int i = 0; i < 32; ++i) //loop over each data item
113 ingest(tree, tree_data, (float)i /32, data[i]);
114
115 std::vector<int> leaf_bits = tree.get_leaf_bits(0);
116 for (int leaf_bit : leaf_bits)
117 std::cout << "Data at leaf " << leaf_bit << " is " << tree_data[tree.get_relative_index(leaf_bit)] << std::endl;
118
119 bool good = tree.bit_at(0) == 1
120 && tree.bit_at(1) == 1
121 && tree.bit_at(2) == 1
122 && tree.bit_at(3) == 1
123 && tree.bit_at(4) == 1
124 && tree.bit_at(5) == 1
125 && tree.bit_at(7) == 1
126 && tree.bit_at(8) == 1
127 && tree.bit_at(9) == 0
128 && tree.bit_at(10) == 1
129 && tree.bit_at(11) == 1
130 && tree.bit_at(12) == 1
131 && tree.bit_at(15) == 0
132 && tree.bit_at(16) == 1
133 && tree.bit_at(17) == 0
134 && tree.bit_at(18) == 1
135 && tree.bit_at(21) == 1
136 && tree.bit_at(22) == 1
137 && tree.bit_at(23) == 0
138 && tree.bit_at(24) == 1
139 && tree.bit_at(25) == 1
140 && tree.bit_at(26) == 1;
141 TEST("Tree structure ", true, good);
142 }
143
144 TESTMAIN(test_time_tree_ingestion);
145