Mercurial > repos > alvarofaure > bitlab

comparison chromeister/src/alignmentFunctions.c @ 0:7fdf47a0bae8 draft

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Uploaded
author alvarofaure
date Wed, 12 Dec 2018 07:18:40 -0500
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:7fdf47a0bae8
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 }