lemon-project-template-glpk

annotate deps/glpk/src/glpavl.c @ 9:33de93886c88

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