1 /*-----------------------------------------------------------------------
2
3 File : clb_quadtrees.c
4
5 Author: Stephan Schulz
6
7 Contents
8
9 Functions for SPLAY trees indexed by two pointers and two ints, and
10 containing a IntOrP.
11
12 Copyright 1998, 1999 by the author.
13 This code is released under the GNU General Public Licence and
14 the GNU Lesser General Public License.
15 See the file COPYING in the main E directory for details..
16 Run "eprover -h" for contact information.
17
18 Changes
19
20 <1> Tue Jan 4 00:55:10 MET 2000
21 Modified from clb_ptrees.c
22
23 -----------------------------------------------------------------------*/
24
25 #include "clb_quadtrees.h"
26
27
28
29 /*---------------------------------------------------------------------*/
30 /* Global Variables */
31 /*---------------------------------------------------------------------*/
32
33
34 /*---------------------------------------------------------------------*/
35 /* Forward Declarations */
36 /*---------------------------------------------------------------------*/
37
38
39 /*---------------------------------------------------------------------*/
40 /* Internal Functions */
41 /*---------------------------------------------------------------------*/
42
43 /*-----------------------------------------------------------------------
44 //
45 // Function: splay_tree()
46 //
47 // Perform the splay operation on tree at node with key.
48 //
49 // Global Variables: -
50 //
51 // Side Effects : Changes tree
52 //
53 /----------------------------------------------------------------------*/
54
splay_tree(QuadTree_p tree,QuadKey_p key)55 static QuadTree_p splay_tree(QuadTree_p tree, QuadKey_p key)
56 {
57 QuadTree_p left, right, tmp;
58 QuadTreeCell newnode;
59 int cmpres;
60
61 if (!tree)
62 {
63 return tree;
64 }
65
66 newnode.lson = NULL;
67 newnode.rson = NULL;
68 left = &newnode;
69 right = &newnode;
70
71 for (;;)
72 {
73 cmpres = QuadKeyCmp(key, &(tree->key));
74 if (cmpres < 0)
75 {
76 if(!tree->lson)
77 {
78 break;
79 }
80 if(QuadKeyCmp(key, &(tree->lson->key)) < 0)
81 {
82 tmp = tree->lson;
83 tree->lson = tmp->rson;
84 tmp->rson = tree;
85 tree = tmp;
86 if (!tree->lson)
87 {
88 break;
89 }
90 }
91 right->lson = tree;
92 right = tree;
93 tree = tree->lson;
94 }
95 else if(cmpres > 0)
96 {
97 if (!tree->rson)
98 {
99 break;
100 }
101 if(QuadKeyCmp(key, &(tree->rson->key)) > 0)
102 {
103 tmp = tree->rson;
104 tree->rson = tmp->lson;
105 tmp->lson = tree;
106 tree = tmp;
107 if (!tree->rson)
108 {
109 break;
110 }
111 }
112 left->rson = tree;
113 left = tree;
114 tree = tree->rson;
115 }
116 else
117 {
118 break;
119 }
120 }
121 left->rson = tree->lson;
122 right->lson = tree->rson;
123 tree->lson = newnode.rson;
124 tree->rson = newnode.lson;
125
126 return tree;
127 }
128
129
130
131
132 /*---------------------------------------------------------------------*/
133 /* Exported Functions */
134 /*---------------------------------------------------------------------*/
135
136 /*-----------------------------------------------------------------------
137 //
138 // Function: DoubleKeyCmp()
139 //
140 // Compare two pointer/integer pairs.
141 //
142 // Global Variables: -
143 //
144 // Side Effects : -
145 //
146 /----------------------------------------------------------------------*/
147
DoubleKeyCmp(void * p1,int i1,void * p2,int i2)148 int DoubleKeyCmp(void* p1, int i1, void *p2, int i2)
149 {
150 int res;
151
152 res = PCmp(p1, p2);
153 if(res)
154 {
155 return res;
156 }
157 res = i1 - i2;
158
159 return res;
160 }
161
162 /*-----------------------------------------------------------------------
163 //
164 // Function: QuadKeyCmp()
165 //
166 // Compare two QuadKeys.
167 //
168 // Global Variables: -
169 //
170 // Side Effects : -
171 //
172 /----------------------------------------------------------------------*/
173
QuadKeyCmp(QuadKey_p key1,QuadKey_p key2)174 int QuadKeyCmp(QuadKey_p key1, QuadKey_p key2)
175 {
176 int res;
177
178 res = DoubleKeyCmp(key1->p1, key1->i1, key2->p1, key2->i1);
179 if(res)
180 {
181 return res;
182 }
183 res = DoubleKeyCmp(key1->p2, key1->i2, key2->p2, key2->i2);
184 return res;
185 }
186
187
188 /*-----------------------------------------------------------------------
189 //
190 // Function: QuadTreeFree()
191 //
192 // Free a QuadTree (including the keys, but not potential objects
193 // pointed to in the val fields
194 //
195 // Global Variables: -
196 //
197 // Side Effects : Memory operations
198 //
199 /----------------------------------------------------------------------*/
200
QuadTreeFree(QuadTree_p junk)201 void QuadTreeFree(QuadTree_p junk)
202 {
203 if(junk)
204 {
205 PStack_p stack = PStackAlloc();
206
207 PStackPushP(stack, junk);
208
209 while(!PStackEmpty(stack))
210 {
211 junk = PStackPopP(stack);
212 if(junk->lson)
213 {
214 PStackPushP(stack, junk->lson);
215 }
216 if(junk->rson)
217 {
218 PStackPushP(stack, junk->rson);
219 }
220 QuadTreeCellFree(junk);
221 }
222 PStackFree(stack);
223 }
224 }
225
226
227 /*-----------------------------------------------------------------------
228 //
229 // Function: QuadTreeInsert()
230 //
231 // If an entry with key *newnode->key exists in the tree return a
232 // pointer to it. Otherwise insert *newnode in the tree and return
233 // NULL. Will splay the tree!
234 //
235 // Global Variables: -
236 //
237 // Side Effects : Changes the tree.
238 //
239 /----------------------------------------------------------------------*/
240
QuadTreeInsert(QuadTree_p * root,QuadTree_p newnode)241 QuadTree_p QuadTreeInsert(QuadTree_p *root, QuadTree_p newnode)
242 {
243 int cmpres;
244
245 if (!*root)
246 {
247 newnode->lson = newnode->rson = NULL;
248 *root = newnode;
249 return NULL;
250 }
251 *root = splay_tree(*root, &(newnode->key));
252
253 cmpres = QuadKeyCmp(&(newnode->key), &(*root)->key);
254
255 if (cmpres < 0)
256 {
257 newnode->lson = (*root)->lson;
258 newnode->rson = *root;
259 (*root)->lson = NULL;
260 *root = newnode;
261 return NULL;
262 }
263 else if(cmpres > 0)
264 {
265 newnode->rson = (*root)->rson;
266 newnode->lson = *root;
267 (*root)->rson = NULL;
268 *root = newnode;
269 return NULL;
270 }
271 return *root;
272 }
273
274
275
276
277 /*-----------------------------------------------------------------------
278 //
279 // Function: QuadTreeStore()
280 //
281 // Insert a cell with given key into the tree. Return false if an
282 // entry for this key exists, true otherwise. The key is never
283 // freed!
284 //
285 // Global Variables: -
286 //
287 // Side Effects : Changes tree
288 //
289 /----------------------------------------------------------------------*/
290
QuadTreeStore(QuadTree_p * root,QuadKey_p key,IntOrP val)291 bool QuadTreeStore(QuadTree_p *root, QuadKey_p key, IntOrP val)
292 {
293 QuadTree_p handle, newnode;
294
295 handle = QuadTreeCellAlloc();
296 handle->key.p1 = key->p1;
297 handle->key.i1 = key->i1;
298 handle->key.p2 = key->p2;
299 handle->key.i2 = key->i2;
300 handle->val.i_val = val.i_val;
301
302 newnode = QuadTreeInsert(root, handle);
303
304 if(newnode)
305 {
306 QuadTreeCellFree(handle);
307 return false;
308 }
309 return true;
310 }
311
312 /*-----------------------------------------------------------------------
313 //
314 // Function: QuadTreeFind()
315 //
316 // Find the entry with key key in the tree and return it. Return
317 // NULL if no such key exists.
318 //
319 // Global Variables: -
320 //
321 // Side Effects : -
322 //
323 /----------------------------------------------------------------------*/
324
QuadTreeFind(QuadTree_p * root,QuadKey_p key)325 QuadTree_p QuadTreeFind(QuadTree_p *root, QuadKey_p key)
326 {
327 if(*root)
328 {
329 *root = splay_tree(*root, key);
330 if(QuadKeyCmp(&((*root)->key), key)==0)
331 {
332 return *root;
333 }
334 }
335 return NULL;
336 }
337
338
339 /*-----------------------------------------------------------------------
340 //
341 // Function: QuadTreeExtractEntry()
342 //
343 // Find the entry with key key, remove it from the tree, rebalance
344 // the tree, and return the pointer to the removed element. Return
345 // NULL if no matching element exists.
346 //
347 //
348 // Global Variables: -
349 //
350 // Side Effects : Changes the tree
351 //
352 /----------------------------------------------------------------------*/
353
354
QuadTreeExtractEntry(QuadTree_p * root,QuadKey_p key)355 QuadTree_p QuadTreeExtractEntry(QuadTree_p *root, QuadKey_p key)
356 {
357 QuadTree_p x, cell;
358
359 if (!(*root))
360 {
361 return NULL;
362 }
363 *root = splay_tree(*root, key);
364 if(QuadKeyCmp(key, &((*root)->key))==0)
365 {
366 if (!(*root)->lson)
367 {
368 x = (*root)->rson;
369 }
370 else
371 {
372 x = splay_tree((*root)->lson, key);
373 x->rson = (*root)->rson;
374 }
375 cell = *root;
376 cell->lson = cell->rson = NULL;
377 *root = x;
378 return cell;
379 }
380 return NULL;
381 }
382
383
384 /*-----------------------------------------------------------------------
385 //
386 // Function: QuadTreeDeleteEntry()
387 //
388 // Delete the entry with key key from the tree. Return true, if the
389 // key existed, false otherwise.
390 //
391 // Global Variables: -
392 //
393 // Side Effects : By QuadTreeExtract(), memory operations
394 //
395 /----------------------------------------------------------------------*/
396
QuadTreeDeleteEntry(QuadTree_p * root,QuadKey_p key)397 bool QuadTreeDeleteEntry(QuadTree_p *root, QuadKey_p key)
398 {
399 QuadTree_p cell;
400
401 cell = QuadTreeExtractEntry(root, key);
402 if(cell)
403 {
404 QuadTreeCellFree(cell);
405 return true;
406 }
407 return false;
408 }
409
410
411 AVL_TRAVERSE_DEFINITION(QuadTree, QuadTree_p)
412
413 /*---------------------------------------------------------------------*/
414 /* End of File */
415 /*---------------------------------------------------------------------*/
416
417
418