1 /*
2 * \AUTHOR: Serena Pallecchi student of Computer Science University of Pisa (Italy)
3 * Commission from Faunalia Pontedera (PI) www.faunalia.it
4 *
5 * This program is free software under the GPL (>=v2)
6 * Read the COPYING file that comes with GRASS for details.
7 *
8 */
9
10 #include <string.h>
11 #include <stdlib.h>
12 #include <math.h>
13 #include <stdio.h>
14
15 #include <grass/gis.h>
16 #include <grass/glocale.h>
17
18 #include "defs.h"
19 #include "avlDefs.h"
20 #include "avl.h"
21
22
23 static avl_node *avl_individua(const avl_tree root, const generic_cell k,
24 avl_node ** father, int *direction);
25 static int avl_height(const avl_tree root);
26 static avl_node *critical_node(avl_node * added, int *pos1, int *pos2,
27 const avl_node * prec);
28
29 void avl_rotation_ll(avl_node * critical);
30 void avl_rotation_lr(avl_node * critical);
31 void avl_rotation_rl(avl_node * critical);
32 void avl_rotation_rr(avl_node * critical);
33 void printAVL(avl_node * r);
34
35
36 /* define function declared in avl.h */
37
avl_make(const generic_cell k,const long n)38 avl_tree avl_make(const generic_cell k, const long n)
39 {
40
41 avl_node *root = NULL; /* tree root pointer */
42
43 /* create root */
44 root = G_malloc(sizeof(avl_node));
45 if (root == NULL) {
46 G_fatal_error("avl.c: avl_make: malloc error");
47 return NULL;
48 }
49
50 /* inizialize root */
51 root->right_child = NULL;
52 root->left_child = NULL;
53 root->father = NULL;
54 root->counter = n;
55 root->key = k;
56
57 return root;
58 }
59
avl_destroy(avl_tree root)60 void avl_destroy(avl_tree root)
61 {
62 struct avl_node *it;
63 struct avl_node *save = root;
64
65 /*
66 Rotate away the left links so that
67 we can treat this like the destruction
68 of a linked list
69 */
70 while((it = save) != NULL) {
71 if (it->left_child == NULL) {
72 /* No left links, just kill the node and move on */
73 save = it->right_child;
74 G_free(it);
75 it = NULL;
76 }
77 else {
78 /* Rotate away the left link and check again */
79 save = it->left_child;
80 it->left_child = save->right_child;
81 save->right_child = it;
82 }
83 }
84 }
85
howManyCell(const avl_tree root,const generic_cell k)86 long howManyCell(const avl_tree root, const generic_cell k)
87 {
88 avl_node *nodo = NULL;
89
90 nodo = avl_find(root, k);
91 if (nodo == NULL)
92 return 0;
93 else
94 return nodo->counter;
95 }
96
97
avl_find(const avl_tree root,const generic_cell k)98 avl_node *avl_find(const avl_tree root, const generic_cell k)
99 {
100 avl_node *p = NULL;
101
102 int d = 0;
103
104 if (root == NULL)
105 return NULL;
106
107 return avl_individua(root, k, &p, &d);
108 }
109
110
avl_add(avl_tree * root,const generic_cell k,const long n)111 int avl_add(avl_tree * root, const generic_cell k, const long n)
112 {
113
114 avl_node *p = NULL;
115 avl_node *node_temp = NULL;
116 avl_node *critical = NULL;
117
118 int d = 0;
119 int pos1 = 0, pos2 = 0;
120 int rotation = 0;
121
122
123
124 if ((root == NULL) || (*root == NULL)) {
125 G_fatal_error("\navl.c: avl_add: param NULL");
126 return AVL_ERR;
127 }
128
129
130 /* search position where insert the new node */
131 node_temp = avl_individua(*root, k, &p, &d);
132
133 if (node_temp != NULL) {
134 node_temp->counter = node_temp->counter + n;
135 return AVL_PRES;
136 }
137
138 node_temp = avl_make(k, n);
139 if (node_temp == NULL) {
140 G_fatal_error("\navl.c: avl_add: create node error");
141 return AVL_ERR;
142 }
143
144
145 /* link the new node */
146 node_temp->father = p;
147
148 if (d == -1) {
149 p->left_child = node_temp;
150 }
151 else {
152 if (d == 1) {
153 p->right_child = node_temp;
154 }
155 else {
156 G_free(node_temp);
157 G_fatal_error("avl.c: avl_add: new node position unknown");
158 return AVL_ERR;
159 }
160 }
161
162 /* if it's necessary balance the tree */
163 critical = critical_node(node_temp, &pos1, &pos2, NULL);
164 if (critical == NULL)
165 return AVL_ADD;
166 rotation = (pos1 * 10) + pos2;
167
168 switch (rotation) {
169 case AVL_SS:
170 avl_rotation_ll(critical);
171 break;
172 case AVL_SD:
173 avl_rotation_lr(critical);
174 break;
175 case AVL_DS:
176 avl_rotation_rl(critical);
177 break;
178 case AVL_DD:
179 avl_rotation_rr(critical);
180 break;
181 default:
182 G_fatal_error("avl, avl_add: balancing error\n");
183 return AVL_ERR;
184 }
185
186 /* if after rotation the root is changed modufy the pointer to the root */
187 while ((*root)->father != NULL)
188 *root = (*root)->father;
189
190 return AVL_ADD;
191 }
192
193
194
195
avl_to_array(avl_node * root,long i,AVL_table a)196 long avl_to_array(avl_node * root, long i, AVL_table a)
197 {
198
199 if (root != NULL) {
200 i = avl_to_array(root->left_child, i, a);
201 if (a == NULL)
202 G_fatal_error("avl, avl_to_array: null value");
203 else {
204 a[i].k = root->key;
205 a[i].tot = root->counter;
206 i++;
207 i = avl_to_array(root->right_child, i, a);
208 }
209 }
210 return i;
211 }
212
213
214
215
avl_individua(const avl_tree root,const generic_cell k,avl_node ** father,int * direction)216 static avl_node *avl_individua(const avl_tree root, const generic_cell k,
217 avl_node ** father, int *direction)
218 {
219 int ris = 0;
220
221
222 if (root == NULL) {
223 return NULL;
224 }
225
226 ris = equalsGenericCell(root->key, k);
227
228
229 switch (ris) {
230 case GC_EQUAL:
231 {
232 return root;
233 break;
234 }
235 case GC_HIGHER:
236 {
237 *father = root;
238 *direction = -1;
239 return avl_individua(root->left_child, k, father, direction);
240 }
241 case GC_LOWER:
242 {
243 *father = root;
244 *direction = 1;
245 return avl_individua(root->right_child, k, father, direction);
246 }
247 case GC_DIFFERENT_TYPE:
248 {
249 G_fatal_error("\avl.c: avl_individua: different type");
250 return NULL;
251 }
252 default:
253 {
254 G_fatal_error("\avl.c: avl_individua: error");
255 return NULL;
256 }
257 }
258
259 }
260
261
avl_height(const avl_tree root)262 static int avl_height(const avl_tree root)
263 {
264 if (root == NULL)
265 return -1;
266 else {
267 int tmp1 = avl_height(root->left_child);
268 int tmp2 = avl_height(root->right_child);
269
270 return (1 + ((tmp1 > tmp2) ? tmp1 : tmp2));
271 }
272
273 }
274
275
critical_node(avl_node * added,int * pos1,int * pos2,const avl_node * prec)276 static avl_node *critical_node(avl_node * added, int *pos1, int *pos2,
277 const avl_node * prec)
278 {
279 int fdb = 0;
280
281 if (added == NULL)
282 return NULL;
283
284 if (prec == NULL)
285 *pos1 = *pos2 = 0;
286 else {
287 *pos2 = *pos1;
288 if (prec == added->left_child)
289 *pos1 = AVL_S;
290 else
291 *pos1 = AVL_D; /* prec == added->right_child */
292 }
293
294
295 fdb = abs(avl_height(added->left_child) - avl_height(added->right_child));
296
297 if (fdb > 1)
298 return added;
299 else {
300 prec = added;
301 return critical_node(added->father, pos1, pos2, prec);
302 }
303
304 }
305
306
avl_rotation_ll(avl_node * critical)307 void avl_rotation_ll(avl_node * critical)
308 {
309 avl_node *b = NULL;
310 avl_node *r = critical;
311 avl_node *s = critical->left_child;
312
313 s->father = r->father;
314
315 if (r->father != NULL) {
316 if ((r->father)->left_child == r)
317 (r->father)->left_child = s;
318 else
319 (r->father)->right_child = s;
320 }
321
322 b = s->right_child;
323 s->right_child = r;
324 r->father = s;
325 r->left_child = b;
326
327 if (b != NULL)
328 b->father = r;
329 }
330
331
avl_rotation_rr(avl_node * critical)332 void avl_rotation_rr(avl_node * critical)
333 {
334 avl_node *b = NULL;
335 avl_node *r = critical;
336 avl_node *s = critical->right_child;
337
338 s->father = r->father;
339
340 if (r->father != NULL) {
341 if ((r->father)->left_child == r)
342 (r->father)->left_child = s;
343 else
344 (r->father)->right_child = s;
345 }
346
347 b = s->left_child;
348 s->left_child = r;
349 r->father = s;
350 r->right_child = b;
351
352 if (b != NULL)
353 b->father = r;
354 }
355
356
avl_rotation_lr(avl_node * critical)357 void avl_rotation_lr(avl_node * critical)
358 {
359 avl_node *b = NULL;
360 avl_node *g = NULL;
361 avl_node *r = critical;
362 avl_node *s = critical->left_child;
363 avl_node *t = (critical->left_child)->right_child;
364
365 t->father = r->father;
366
367 if (r->father != NULL) {
368 if ((r->father)->left_child == r)
369 (r->father)->left_child = t;
370 else
371 (r->father)->right_child = t;
372 }
373
374 b = t->left_child;
375 g = t->right_child;
376
377 t->left_child = s;
378 t->right_child = r;
379 r->father = t;
380 s->father = t;
381
382 s->right_child = b;
383 r->left_child = g;
384
385 if (b != NULL)
386 b->father = s;
387 if (g != NULL)
388 g->father = r;
389 }
390
391
avl_rotation_rl(avl_node * critical)392 void avl_rotation_rl(avl_node * critical)
393 {
394 avl_node *b = NULL;
395 avl_node *g = NULL;
396 avl_node *r = critical;
397 avl_node *s = critical->right_child;
398 avl_node *t = (critical->right_child)->left_child;
399
400 t->father = r->father;
401
402 if (r->father != NULL) {
403 if ((r->father)->left_child == r)
404 (r->father)->left_child = t;
405 else
406 (r->father)->right_child = t;
407 }
408
409 b = t->left_child;
410 g = t->right_child;
411
412 t->left_child = r;
413 t->right_child = s;
414 r->father = t;
415 s->father = t;
416
417 r->right_child = b;
418 s->left_child = g;
419
420 if (b != NULL)
421 b->father = r;
422 if (g != NULL)
423 g->father = s;
424 }
425