|
0
|
1 #include <stdio.h>
|
|
|
2 #include <stdlib.h>
|
|
|
3 #include <string.h>
|
|
|
4 #include <ctype.h>
|
|
|
5 #include <inttypes.h>
|
|
|
6 #include <math.h>
|
|
|
7 #include <float.h>
|
|
|
8 #include "structs.h"
|
|
|
9 #include "alignmentFunctions.h"
|
|
|
10 #include "commonFunctions.h"
|
|
|
11
|
|
|
12
|
|
|
13
|
|
|
14 int64_t compare_letters(unsigned char a, unsigned char b){
|
|
|
15 if(a != (unsigned char) 'N' && a != (unsigned char) '>') return (a == b) ? POINT : -POINT;
|
|
|
16 return -POINT;
|
|
|
17 }
|
|
|
18
|
|
|
19 llpos * getNewLocationllpos(Mempool_l * mp, uint64_t * n_pools_used){
|
|
|
20
|
|
|
21 if(mp[*n_pools_used].current == POOL_SIZE){
|
|
|
22 *n_pools_used += 1;
|
|
|
23 if(*n_pools_used == MAX_MEM_POOLS) terror("Reached max pools");
|
|
|
24 init_mem_pool_llpos(&mp[*n_pools_used]);
|
|
|
25
|
|
|
26 }
|
|
|
27
|
|
|
28 llpos * new_pos = mp[*n_pools_used].base + mp[*n_pools_used].current;
|
|
|
29 mp[*n_pools_used].current++;
|
|
|
30
|
|
|
31
|
|
|
32 return new_pos;
|
|
|
33 }
|
|
|
34
|
|
|
35 void init_mem_pool_llpos(Mempool_l * mp){
|
|
|
36 mp->base = (llpos *) calloc(POOL_SIZE, sizeof(llpos));
|
|
|
37 if(mp->base == NULL) terror("Could not request memory pool");
|
|
|
38 mp->current = 0;
|
|
|
39 }
|
|
|
40
|
|
|
41 AVLTree * getNewLocationAVLTree(Mempool_AVL * mp, uint64_t * n_pools_used, uint64_t key){
|
|
|
42
|
|
|
43 if(mp[*n_pools_used].current == POOL_SIZE){
|
|
|
44 *n_pools_used += 1;
|
|
|
45 if(*n_pools_used == MAX_MEM_POOLS) terror("Reached max pools");
|
|
|
46 init_mem_pool_AVL(&mp[*n_pools_used]);
|
|
|
47
|
|
|
48 }
|
|
|
49
|
|
|
50 AVLTree * new_pos = mp[*n_pools_used].base + mp[*n_pools_used].current;
|
|
|
51 mp[*n_pools_used].current++;
|
|
|
52
|
|
|
53 new_pos->key = key;
|
|
|
54 new_pos->count = 1;
|
|
|
55 new_pos->height = 1;
|
|
|
56
|
|
|
57 return new_pos;
|
|
|
58 }
|
|
|
59
|
|
|
60 void init_mem_pool_AVL(Mempool_AVL * mp){
|
|
|
61 mp->base = (AVLTree *) calloc(POOL_SIZE, sizeof(AVLTree));
|
|
|
62 if(mp->base == NULL) terror("Could not request memory pool");
|
|
|
63 mp->current = 0;
|
|
|
64 }
|
|
|
65
|
|
|
66
|
|
|
67
|
|
|
68 /*
|
|
|
69 // An AVL tree node
|
|
|
70 typedef struct AVL_Node{
|
|
|
71 uint64_t key;
|
|
|
72 struct AVL_Node * left;
|
|
|
73 struct AVL_Node * right;
|
|
|
74 uint64_t height;
|
|
|
75 llpos * next;
|
|
|
76 } AVLTree;
|
|
|
77 */
|
|
|
78
|
|
|
79 // A utility function to get height of the tree
|
|
|
80
|
|
|
81 uint64_t height(AVLTree * N){
|
|
|
82 if (N == NULL)
|
|
|
83 return 0;
|
|
|
84 return N->height;
|
|
|
85 }
|
|
|
86
|
|
|
87 /* Substituted by (x == NULL) ? (0) : (x->height) */
|
|
|
88
|
|
|
89 /* Helper function that allocates a new node with the given key and
|
|
|
90 NULL left and right pointers. */
|
|
|
91
|
|
|
92 /* This one is substituted by AVLTree * getNewLocationAVLTree(Mempool_AVL * mp, uint64_t * n_pools_used, uint64_t key) */
|
|
|
93
|
|
|
94 // A utility function to right rotate subtree rooted with y
|
|
|
95 // See the diagram given above.
|
|
|
96 AVLTree * right_rotate(AVLTree * y){
|
|
|
97 AVLTree * x = y->left;
|
|
|
98 AVLTree * T2 = x->right;
|
|
|
99
|
|
|
100 // Perform rotation
|
|
|
101 x->right = y;
|
|
|
102 y->left = T2;
|
|
|
103
|
|
|
104 // Update heights
|
|
|
105 //x->height = MAX((x == NULL) ? (0) : (x->left->height), (x == NULL) ? (0) : (x->right->height))+1;
|
|
|
106 //y->height = MAX((y == NULL) ? (0) : (y->left->height), (y == NULL) ? (0) : (y->right->height))+1;
|
|
|
107 // Update heights
|
|
|
108 y->height = MAX(height(y->left), height(y->right))+1;
|
|
|
109 x->height = MAX(height(x->left), height(x->right))+1;
|
|
|
110
|
|
|
111 // Return new root
|
|
|
112 return x;
|
|
|
113 }
|
|
|
114
|
|
|
115 // A utility function to left rotate subtree rooted with x
|
|
|
116 // See the diagram given above.
|
|
|
117 AVLTree * left_rotate(AVLTree * x){
|
|
|
118 AVLTree * y = x->right;
|
|
|
119 AVLTree * T2 = y->left;
|
|
|
120
|
|
|
121 // Perform rotation
|
|
|
122 y->left = x;
|
|
|
123 x->right = T2;
|
|
|
124
|
|
|
125 // Update heights
|
|
|
126 //x->height = MAX((x == NULL) ? (0) : (x->left->height), (x == NULL) ? (0) : (x->right->height))+1;
|
|
|
127 //y->height = MAX((y == NULL) ? (0) : (y->left->height), (y == NULL) ? (0) : (y->right->height))+1;
|
|
|
128 x->height = MAX(height(x->left), height(x->right))+1;
|
|
|
129 y->height = MAX(height(y->left), height(y->right))+1;
|
|
|
130
|
|
|
131 // Return new root
|
|
|
132 return y;
|
|
|
133 }
|
|
|
134
|
|
|
135 // Get Balance factor of node N
|
|
|
136
|
|
|
137 int64_t get_balance(AVLTree * N){
|
|
|
138 if (N == NULL)
|
|
|
139 return 0;
|
|
|
140 return height(N->left) - height(N->right);
|
|
|
141 }
|
|
|
142
|
|
|
143 /* Substituted by (node == NULL) ? (0) : ((int64_t) node->left->height - (int64_t) node->right->height) */
|
|
|
144
|
|
|
145 AVLTree * find_AVLTree(AVLTree * node, uint64_t key){
|
|
|
146 AVLTree * found = NULL;
|
|
|
147 if(node == NULL) return NULL;
|
|
|
148
|
|
|
149 if (key < node->key) {
|
|
|
150 found = find_AVLTree(node->left, key);
|
|
|
151 } else if (key > node->key) {
|
|
|
152 found = find_AVLTree(node->right, key);
|
|
|
153 } else {
|
|
|
154 return node;
|
|
|
155 }
|
|
|
156 return found;
|
|
|
157 }
|
|
|
158
|
|
|
159 llpos * find_AVLTree_llpos(AVLTree * node, uint64_t key){
|
|
|
160 llpos * aux = NULL;
|
|
|
161 if(node == NULL) return NULL;
|
|
|
162
|
|
|
163 if (key < node->key) {
|
|
|
164 aux = find_AVLTree_llpos(node->left, key);
|
|
|
165 } else if (key > node->key) {
|
|
|
166 aux = find_AVLTree_llpos(node->right, key);
|
|
|
167 } else {
|
|
|
168 return node->next;
|
|
|
169 }
|
|
|
170 return aux;
|
|
|
171 }
|
|
|
172
|
|
|
173 // Recursive function to insert key in subtree rooted
|
|
|
174 // with node and returns new root of subtree.
|
|
|
175 AVLTree * insert_AVLTree(AVLTree * node, uint64_t key, Mempool_AVL * mp, uint64_t * n_pools_used, uint64_t pos, Mempool_l * mp_l, uint64_t * n_pools_used_l){
|
|
|
176 /* 1. Perform the normal BST insertion */
|
|
|
177 if (node == NULL){
|
|
|
178
|
|
|
179 AVLTree * n_node = getNewLocationAVLTree(mp, n_pools_used, key);
|
|
|
180 llpos * aux = getNewLocationllpos(mp_l, n_pools_used_l);
|
|
|
181 aux->pos = pos;
|
|
|
182 n_node->next = aux;
|
|
|
183 return n_node;
|
|
|
184 }
|
|
|
185
|
|
|
186 if (key < node->key) {
|
|
|
187 node->left = insert_AVLTree(node->left, key, mp, n_pools_used, pos, mp_l, n_pools_used_l);
|
|
|
188 } else if (key > node->key) {
|
|
|
189 node->right = insert_AVLTree(node->right, key, mp, n_pools_used, pos, mp_l, n_pools_used_l);
|
|
|
190 } else {
|
|
|
191 // Equal keys are inserted as a linked list
|
|
|
192 if(node->count == 1){ // DO NOT INSERT MORE THAN 2. 1 is good 2 is repetition
|
|
|
193 llpos * aux = getNewLocationllpos(mp_l, n_pools_used_l);
|
|
|
194 aux->pos = pos;
|
|
|
195 aux->next = node->next;
|
|
|
196 node->next = aux;
|
|
|
197 ++(node->count);
|
|
|
198 }
|
|
|
199
|
|
|
200 return node;
|
|
|
201 }
|
|
|
202
|
|
|
203 /* 2. Update height of this ancestor node */
|
|
|
204 //node->height = 1 + MAX((node->left == NULL) ? (0) : (node->left->height), (node->right == NULL) ? (0) : (node->right->height));
|
|
|
205 node->height = 1 + MAX(height(node->left), height(node->right));
|
|
|
206
|
|
|
207 /* 3. Get the balance factor of this ancestor
|
|
|
208 node to check whether this node became
|
|
|
209 unbalanced */
|
|
|
210 //int64_t balance = (node->left == NULL || node->right == NULL) ? (0) : ((int64_t) node->left->height - (int64_t) node->right->height);
|
|
|
211 int64_t balance = get_balance(node);
|
|
|
212
|
|
|
213 // If this node becomes unbalanced, then
|
|
|
214 // there are 4 cases
|
|
|
215
|
|
|
216 // Left Left Case
|
|
|
217 if (balance > 1 && key < node->left->key)
|
|
|
218 return right_rotate(node);
|
|
|
219
|
|
|
220 // Right Right Case
|
|
|
221 if (balance < -1 && key > node->right->key)
|
|
|
222 return left_rotate(node);
|
|
|
223
|
|
|
224 // Left Right Case
|
|
|
225 if (balance > 1 && key > node->left->key)
|
|
|
226 {
|
|
|
227 node->left = left_rotate(node->left);
|
|
|
228 return right_rotate(node);
|
|
|
229 }
|
|
|
230
|
|
|
231 // Right Left Case
|
|
|
232 if (balance < -1 && key < node->right->key)
|
|
|
233 {
|
|
|
234 node->right = right_rotate(node->right);
|
|
|
235 return left_rotate(node);
|
|
|
236 }
|
|
|
237
|
|
|
238 /* return the (unchanged) node pointer */
|
|
|
239 return node;
|
|
|
240 }
|
|
|
241
|
|
|
242 // A utility function to print preorder traversal
|
|
|
243 // of the tree.
|
|
|
244 // The function also prints height of every node
|
|
|
245
|
|
|
246 void pre_order(AVLTree * root){
|
|
|
247 if(root != NULL){
|
|
|
248 printf("%"PRIu64" ", root->key);
|
|
|
249 llpos * aux = root->next;
|
|
|
250 while(aux != NULL){ printf("#%"PRIu64", ", aux->pos); aux = aux->next; }
|
|
|
251 pre_order(root->left);
|
|
|
252 pre_order(root->right);
|
|
|
253 }
|
|
|
254 }
|
|
|
255
|
|
|
256
|
|
|
257 uint64_t sum_of_all_tree(AVLTree * root){
|
|
|
258 uint64_t mysum = 0;
|
|
|
259 if(root != NULL){
|
|
|
260
|
|
|
261 mysum = root->count;
|
|
|
262 mysum += sum_of_all_tree(root->left);
|
|
|
263 mysum += sum_of_all_tree(root->right);
|
|
|
264 }
|
|
|
265 return mysum;
|
|
|
266 } |
