lemon-project-template-glpk
comparison deps/glpk/src/glpavl.c @ 11:4fc6ad2fb8a6
Test GLPK in src/main.cc
author | Alpar Juttner <alpar@cs.elte.hu> |
---|---|
date | Sun, 06 Nov 2011 21:43:29 +0100 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:20b04205a116 |
---|---|
1 /* glpavl.c (binary search tree) */ | |
2 | |
3 /*********************************************************************** | |
4 * This code is part of GLPK (GNU Linear Programming Kit). | |
5 * | |
6 * Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, | |
7 * 2009, 2010, 2011 Andrew Makhorin, Department for Applied Informatics, | |
8 * Moscow Aviation Institute, Moscow, Russia. All rights reserved. | |
9 * E-mail: <mao@gnu.org>. | |
10 * | |
11 * GLPK is free software: you can redistribute it and/or modify it | |
12 * under the terms of the GNU General Public License as published by | |
13 * the Free Software Foundation, either version 3 of the License, or | |
14 * (at your option) any later version. | |
15 * | |
16 * GLPK is distributed in the hope that it will be useful, but WITHOUT | |
17 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY | |
18 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public | |
19 * License for more details. | |
20 * | |
21 * You should have received a copy of the GNU General Public License | |
22 * along with GLPK. If not, see <http://www.gnu.org/licenses/>. | |
23 ***********************************************************************/ | |
24 | |
25 #include "glpavl.h" | |
26 | |
27 AVL *avl_create_tree(int (*fcmp)(void *info, const void *key1, | |
28 const void *key2), void *info) | |
29 { /* create AVL tree */ | |
30 AVL *tree; | |
31 tree = xmalloc(sizeof(AVL)); | |
32 tree->pool = dmp_create_pool(); | |
33 tree->root = NULL; | |
34 tree->fcmp = fcmp; | |
35 tree->info = info; | |
36 tree->size = 0; | |
37 tree->height = 0; | |
38 return tree; | |
39 } | |
40 | |
41 int avl_strcmp(void *info, const void *key1, const void *key2) | |
42 { /* compare character string keys */ | |
43 xassert(info == info); | |
44 return strcmp(key1, key2); | |
45 } | |
46 | |
47 static AVLNODE *rotate_subtree(AVL *tree, AVLNODE *node); | |
48 | |
49 AVLNODE *avl_insert_node(AVL *tree, const void *key) | |
50 { /* insert new node into AVL tree */ | |
51 AVLNODE *p, *q, *r; | |
52 short int flag; | |
53 /* find an appropriate point for insertion */ | |
54 p = NULL; q = tree->root; | |
55 while (q != NULL) | |
56 { p = q; | |
57 if (tree->fcmp(tree->info, key, p->key) <= 0) | |
58 { flag = 0; | |
59 q = p->left; | |
60 p->rank++; | |
61 } | |
62 else | |
63 { flag = 1; | |
64 q = p->right; | |
65 } | |
66 } | |
67 /* create new node and insert it into the tree */ | |
68 r = dmp_get_atom(tree->pool, sizeof(AVLNODE)); | |
69 r->key = key; r->type = 0; r->link = NULL; | |
70 r->rank = 1; r->up = p; | |
71 r->flag = (short int)(p == NULL ? 0 : flag); | |
72 r->bal = 0; r->left = NULL; r->right = NULL; | |
73 tree->size++; | |
74 if (p == NULL) | |
75 tree->root = r; | |
76 else | |
77 if (flag == 0) p->left = r; else p->right = r; | |
78 /* go upstairs to the root and correct all subtrees affected by | |
79 insertion */ | |
80 while (p != NULL) | |
81 { if (flag == 0) | |
82 { /* the height of the left subtree of [p] is increased */ | |
83 if (p->bal > 0) | |
84 { p->bal = 0; | |
85 break; | |
86 } | |
87 if (p->bal < 0) | |
88 { rotate_subtree(tree, p); | |
89 break; | |
90 } | |
91 p->bal = -1; flag = p->flag; p = p->up; | |
92 } | |
93 else | |
94 { /* the height of the right subtree of [p] is increased */ | |
95 if (p->bal < 0) | |
96 { p->bal = 0; | |
97 break; | |
98 } | |
99 if (p->bal > 0) | |
100 { rotate_subtree(tree, p); | |
101 break; | |
102 } | |
103 p->bal = +1; flag = p->flag; p = p->up; | |
104 } | |
105 } | |
106 /* if the root has been reached, the height of the entire tree is | |
107 increased */ | |
108 if (p == NULL) tree->height++; | |
109 return r; | |
110 } | |
111 | |
112 void avl_set_node_type(AVLNODE *node, int type) | |
113 { /* assign the type field of specified node */ | |
114 node->type = type; | |
115 return; | |
116 } | |
117 | |
118 void avl_set_node_link(AVLNODE *node, void *link) | |
119 { /* assign the link field of specified node */ | |
120 node->link = link; | |
121 return; | |
122 } | |
123 | |
124 AVLNODE *avl_find_node(AVL *tree, const void *key) | |
125 { /* find node in AVL tree */ | |
126 AVLNODE *p; | |
127 int c; | |
128 p = tree->root; | |
129 while (p != NULL) | |
130 { c = tree->fcmp(tree->info, key, p->key); | |
131 if (c == 0) break; | |
132 p = (c < 0 ? p->left : p->right); | |
133 } | |
134 return p; | |
135 } | |
136 | |
137 int avl_get_node_type(AVLNODE *node) | |
138 { /* retrieve the type field of specified node */ | |
139 return node->type; | |
140 } | |
141 | |
142 void *avl_get_node_link(AVLNODE *node) | |
143 { /* retrieve the link field of specified node */ | |
144 return node->link; | |
145 } | |
146 | |
147 static AVLNODE *find_next_node(AVL *tree, AVLNODE *node) | |
148 { /* find next node in AVL tree */ | |
149 AVLNODE *p, *q; | |
150 if (tree->root == NULL) return NULL; | |
151 p = node; | |
152 q = (p == NULL ? tree->root : p->right); | |
153 if (q == NULL) | |
154 { /* go upstairs from the left subtree */ | |
155 for (;;) | |
156 { q = p->up; | |
157 if (q == NULL) break; | |
158 if (p->flag == 0) break; | |
159 p = q; | |
160 } | |
161 } | |
162 else | |
163 { /* go downstairs into the right subtree */ | |
164 for (;;) | |
165 { p = q->left; | |
166 if (p == NULL) break; | |
167 q = p; | |
168 } | |
169 } | |
170 return q; | |
171 } | |
172 | |
173 void avl_delete_node(AVL *tree, AVLNODE *node) | |
174 { /* delete specified node from AVL tree */ | |
175 AVLNODE *f, *p, *q, *r, *s, *x, *y; | |
176 short int flag; | |
177 p = node; | |
178 /* if both subtrees of the specified node are non-empty, the node | |
179 should be interchanged with the next one, at least one subtree | |
180 of which is always empty */ | |
181 if (p->left == NULL || p->right == NULL) goto skip; | |
182 f = p->up; q = p->left; | |
183 r = find_next_node(tree, p); s = r->right; | |
184 if (p->right == r) | |
185 { if (f == NULL) | |
186 tree->root = r; | |
187 else | |
188 if (p->flag == 0) f->left = r; else f->right = r; | |
189 r->rank = p->rank; r->up = f; | |
190 r->flag = p->flag; r->bal = p->bal; | |
191 r->left = q; r->right = p; | |
192 q->up = r; | |
193 p->rank = 1; p->up = r; p->flag = 1; | |
194 p->bal = (short int)(s == NULL ? 0 : +1); | |
195 p->left = NULL; p->right = s; | |
196 if (s != NULL) s->up = p; | |
197 } | |
198 else | |
199 { x = p->right; y = r->up; | |
200 if (f == NULL) | |
201 tree->root = r; | |
202 else | |
203 if (p->flag == 0) f->left = r; else f->right = r; | |
204 r->rank = p->rank; r->up = f; | |
205 r->flag = p->flag; r->bal = p->bal; | |
206 r->left = q; r->right = x; | |
207 q->up = r; x->up = r; y->left = p; | |
208 p->rank = 1; p->up = y; p->flag = 0; | |
209 p->bal = (short int)(s == NULL ? 0 : +1); | |
210 p->left = NULL; p->right = s; | |
211 if (s != NULL) s->up = p; | |
212 } | |
213 skip: /* now the specified node [p] has at least one empty subtree; | |
214 go upstairs to the root and adjust the rank field of all nodes | |
215 affected by deletion */ | |
216 q = p; f = q->up; | |
217 while (f != NULL) | |
218 { if (q->flag == 0) f->rank--; | |
219 q = f; f = q->up; | |
220 } | |
221 /* delete the specified node from the tree */ | |
222 f = p->up; flag = p->flag; | |
223 q = p->left != NULL ? p->left : p->right; | |
224 if (f == NULL) | |
225 tree->root = q; | |
226 else | |
227 if (flag == 0) f->left = q; else f->right = q; | |
228 if (q != NULL) q->up = f, q->flag = flag; | |
229 tree->size--; | |
230 /* go upstairs to the root and correct all subtrees affected by | |
231 deletion */ | |
232 while (f != NULL) | |
233 { if (flag == 0) | |
234 { /* the height of the left subtree of [f] is decreased */ | |
235 if (f->bal == 0) | |
236 { f->bal = +1; | |
237 break; | |
238 } | |
239 if (f->bal < 0) | |
240 f->bal = 0; | |
241 else | |
242 { f = rotate_subtree(tree, f); | |
243 if (f->bal < 0) break; | |
244 } | |
245 flag = f->flag; f = f->up; | |
246 } | |
247 else | |
248 { /* the height of the right subtree of [f] is decreased */ | |
249 if (f->bal == 0) | |
250 { f->bal = -1; | |
251 break; | |
252 } | |
253 if (f->bal > 0) | |
254 f->bal = 0; | |
255 else | |
256 { f = rotate_subtree(tree, f); | |
257 if (f->bal > 0) break; | |
258 } | |
259 flag = f->flag; f = f->up; | |
260 } | |
261 } | |
262 /* if the root has been reached, the height of the entire tree is | |
263 decreased */ | |
264 if (f == NULL) tree->height--; | |
265 /* returns the deleted node to the memory pool */ | |
266 dmp_free_atom(tree->pool, p, sizeof(AVLNODE)); | |
267 return; | |
268 } | |
269 | |
270 static AVLNODE *rotate_subtree(AVL *tree, AVLNODE *node) | |
271 { /* restore balance of AVL subtree */ | |
272 AVLNODE *f, *p, *q, *r, *x, *y; | |
273 xassert(node != NULL); | |
274 p = node; | |
275 if (p->bal < 0) | |
276 { /* perform negative (left) rotation */ | |
277 f = p->up; q = p->left; r = q->right; | |
278 if (q->bal <= 0) | |
279 { /* perform single negative rotation */ | |
280 if (f == NULL) | |
281 tree->root = q; | |
282 else | |
283 if (p->flag == 0) f->left = q; else f->right = q; | |
284 p->rank -= q->rank; | |
285 q->up = f; q->flag = p->flag; q->bal++; q->right = p; | |
286 p->up = q; p->flag = 1; | |
287 p->bal = (short int)(-q->bal); p->left = r; | |
288 if (r != NULL) r->up = p, r->flag = 0; | |
289 node = q; | |
290 } | |
291 else | |
292 { /* perform double negative rotation */ | |
293 x = r->left; y = r->right; | |
294 if (f == NULL) | |
295 tree->root = r; | |
296 else | |
297 if (p->flag == 0) f->left = r; else f->right = r; | |
298 p->rank -= (q->rank + r->rank); | |
299 r->rank += q->rank; | |
300 p->bal = (short int)(r->bal >= 0 ? 0 : +1); | |
301 q->bal = (short int)(r->bal <= 0 ? 0 : -1); | |
302 r->up = f; r->flag = p->flag; r->bal = 0; | |
303 r->left = q; r->right = p; | |
304 p->up = r; p->flag = 1; p->left = y; | |
305 q->up = r; q->flag = 0; q->right = x; | |
306 if (x != NULL) x->up = q, x->flag = 1; | |
307 if (y != NULL) y->up = p, y->flag = 0; | |
308 node = r; | |
309 } | |
310 } | |
311 else | |
312 { /* perform positive (right) rotation */ | |
313 f = p->up; q = p->right; r = q->left; | |
314 if (q->bal >= 0) | |
315 { /* perform single positive rotation */ | |
316 if (f == NULL) | |
317 tree->root = q; | |
318 else | |
319 if (p->flag == 0) f->left = q; else f->right = q; | |
320 q->rank += p->rank; | |
321 q->up = f; q->flag = p->flag; q->bal--; q->left = p; | |
322 p->up = q; p->flag = 0; | |
323 p->bal = (short int)(-q->bal); p->right = r; | |
324 if (r != NULL) r->up = p, r->flag = 1; | |
325 node = q; | |
326 } | |
327 else | |
328 { /* perform double positive rotation */ | |
329 x = r->left; y = r->right; | |
330 if (f == NULL) | |
331 tree->root = r; | |
332 else | |
333 if (p->flag == 0) f->left = r; else f->right = r; | |
334 q->rank -= r->rank; | |
335 r->rank += p->rank; | |
336 p->bal = (short int)(r->bal <= 0 ? 0 : -1); | |
337 q->bal = (short int)(r->bal >= 0 ? 0 : +1); | |
338 r->up = f; r->flag = p->flag; r->bal = 0; | |
339 r->left = p; r->right = q; | |
340 p->up = r; p->flag = 0; p->right = x; | |
341 q->up = r; q->flag = 1; q->left = y; | |
342 if (x != NULL) x->up = p, x->flag = 1; | |
343 if (y != NULL) y->up = q, y->flag = 0; | |
344 node = r; | |
345 } | |
346 } | |
347 return node; | |
348 } | |
349 | |
350 void avl_delete_tree(AVL *tree) | |
351 { /* delete AVL tree */ | |
352 dmp_delete_pool(tree->pool); | |
353 xfree(tree); | |
354 return; | |
355 } | |
356 | |
357 /* eof */ |