Mercurial > repos > alvarofaure > bitlab

comparison chromeister/src/alignmentFunctions.c @ 1:3d1fbde7e0cc draft default tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Deleted selected files
author alvarofaure
date Thu, 13 Dec 2018 03:41:58 -0500
parents 7fdf47a0bae8
children
comparison
equal deleted inserted replaced
0:7fdf47a0bae8 1:3d1fbde7e0cc
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 }