lemon-project-template-glpk: 33de93886c88 deps/glpk/src/glpavl.c

lemon-project-template-glpk

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

Import GLPK 4.47

author	Alpar Juttner <alpar@cs.elte.hu>
date	Sun, 06 Nov 2011 20:59:10 +0100
parents
children

line source

1 /* glpavl.c (binary search tree) */

3 /***********************************************************************

4 * This code is part of GLPK (GNU Linear Programming Kit).

5 *

7 * 2009, 2010, 2011 Andrew Makhorin, Department for Applied Informatics,

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 ***********************************************************************/

25 #include "glpavl.h"

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 }

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 }

47 static AVLNODE *rotate_subtree(AVL *tree, AVLNODE *node);

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 */