]> pd.if.org Git - zpackage/blob - lib/jsw/jsw_atree.c
ba66bd0ccb6eb984c285a178c2b6f93383de0122
[zpackage] / lib / jsw / jsw_atree.c
1 /*
2   Andersson tree library
3
4     > Created (Julienne Walker): September 10, 2005
5     > Corrections (James Bucanek): April 10, 2006
6       1) Typo in jsw_aerase:
7            up != 0 should be top != 0
8       2) Bug in jsw_aerase:
9            skew ( path[top] ) should be skew ( up )
10            split ( path[top] ) should be split ( up )
11       3) Bug in skew and split macros:
12            Condition should test for nil
13       4) Bug in jsw_aerase:
14            Search for successor should save the path
15 */
16 #include "jsw_atree.h"
17
18 #ifdef __cplusplus
19 #include <cstdlib>
20
21 using std::malloc;
22 using std::free;
23 using std::size_t;
24 #else
25 #include <stdlib.h>
26 #endif
27
28 #ifndef HEIGHT_LIMIT
29 #define HEIGHT_LIMIT 64 /* Tallest allowable tree */
30 #endif
31
32 typedef struct jsw_anode {
33   int               level;   /* Horizontal level for balance */
34   void             *data;    /* User-defined content */
35   struct jsw_anode *link[2]; /* Left (0) and right (1) links */
36 } jsw_anode_t;
37
38 struct jsw_atree {
39   jsw_anode_t *root; /* Top of the tree */
40   jsw_anode_t *nil;  /* End of tree sentinel */
41   cmp_f        cmp;  /* Compare two items */
42   dup_f        dup;  /* Clone an item (user-defined) */
43   rel_f        rel;  /* Destroy an item (user-defined) */
44   size_t       size; /* Number of items (user-defined) */
45 };
46
47 struct jsw_atrav {
48   jsw_atree_t *tree;               /* Paired tree */
49   jsw_anode_t *it;                 /* Current node */
50   jsw_anode_t *path[HEIGHT_LIMIT]; /* Traversal path */
51   size_t       top;                /* Top of stack */
52 };
53
54 /* Remove left horizontal links */
55 #define skew(t) do {                                      \
56   if ( t->link[0]->level == t->level && t->level != 0 ) { \
57     jsw_anode_t *save = t->link[0];                       \
58     t->link[0] = save->link[1];                           \
59     save->link[1] = t;                                    \
60     t = save;                                             \
61   }                                                       \
62 } while(0)
63
64 /* Remove consecutive horizontal links */
65 #define split(t) do {                                              \
66   if ( t->link[1]->link[1]->level == t->level && t->level != 0 ) { \
67     jsw_anode_t *save = t->link[1];                                \
68     t->link[1] = save->link[0];                                    \
69     save->link[0] = t;                                             \
70     t = save;                                                      \
71     ++t->level;                                                    \
72   }                                                                \
73 } while(0)
74
75 static jsw_anode_t *new_node ( jsw_atree_t *tree, void *data )
76 {
77   jsw_anode_t *rn = (jsw_anode_t *)malloc ( sizeof *rn );
78
79   if ( rn == NULL )
80     return tree->nil;
81
82   rn->level = 1;
83   rn->data = tree->dup ( data );
84   rn->link[0] = rn->link[1] = tree->nil;
85
86   return rn;
87 }
88
89 jsw_atree_t *jsw_anew ( cmp_f cmp, dup_f dup, rel_f rel )
90 {
91   jsw_atree_t *rt = (jsw_atree_t *)malloc ( sizeof *rt );
92
93   if ( rt == NULL )
94     return NULL;
95
96   /* Initialize sentinel */
97   rt->nil = (jsw_anode_t *)malloc ( sizeof *rt->nil );
98   if ( rt->nil == NULL ) {
99     free ( rt );
100     return NULL;
101   }
102
103   rt->nil->data = NULL; /* Simplifies some ops */
104   rt->nil->level = 0;
105   rt->nil->link[0] = rt->nil->link[1] = rt->nil;
106
107   /* Initialize tree */
108   rt->root = rt->nil;
109   rt->cmp = cmp;
110   rt->dup = dup;
111   rt->rel = rel;
112   rt->size = 0;
113
114   return rt;
115 }
116
117 void jsw_adelete ( jsw_atree_t *tree )
118 {
119   jsw_anode_t *it = tree->root;
120   jsw_anode_t *save;
121
122   /* Destruction by rotation */
123   while ( it != tree->nil ) {
124     if ( it->link[0] == tree->nil ) {
125       /* Remove node */
126       save = it->link[1];
127       tree->rel ( it->data );
128       free ( it );
129     }
130     else {
131       /* Rotate right */
132       save = it->link[0];
133       it->link[0] = save->link[1];
134       save->link[1] = it;
135     }
136
137     it = save;
138   }
139
140   /* Finalize destruction */
141   free ( tree->nil );
142   free ( tree );
143 }
144
145 void *jsw_afind ( jsw_atree_t *tree, void *data )
146 {
147   jsw_anode_t *it = tree->root;
148
149   while ( it != tree->nil ) {
150     int cmp = tree->cmp ( it->data, data );
151
152     if ( cmp == 0 )
153       break;
154
155     it = it->link[cmp < 0];
156   }
157
158   /* nil->data == NULL */
159   return it->data;
160 }
161
162 int jsw_ainsert ( jsw_atree_t *tree, void *data )
163 {
164   if ( tree->root == tree->nil ) {
165     /* Empty tree case */
166     tree->root = new_node ( tree, data );
167     if ( tree->root == tree->nil )
168       return 0;
169   }
170   else {
171     jsw_anode_t *it = tree->root;
172     jsw_anode_t *path[HEIGHT_LIMIT];
173     int top = 0, dir;
174
175     /* Find a spot and save the path */
176     for ( ; ; ) {
177       path[top++] = it;
178       dir = tree->cmp ( it->data, data ) < 0;
179
180       if ( it->link[dir] == tree->nil )
181         break;
182
183       it = it->link[dir];
184     }
185
186     /* Create a new item */
187     it->link[dir] = new_node ( tree, data );
188     if ( it->link[dir] == tree->nil )
189       return 0;
190
191     /* Walk back and rebalance */
192     while ( --top >= 0 ) {
193       /* Which child? */
194       if ( top != 0 )
195         dir = path[top - 1]->link[1] == path[top];
196
197       skew ( path[top] );
198       split ( path[top] );
199
200       /* Fix the parent */
201       if ( top != 0 )
202         path[top - 1]->link[dir] = path[top];
203       else
204         tree->root = path[top];
205     }
206   }
207
208   ++tree->size;
209
210   return 1;
211 }
212
213 int jsw_aerase ( jsw_atree_t *tree, void *data )
214 {
215   if ( tree->root == tree->nil )
216     return 0;
217   else {
218     jsw_anode_t *it = tree->root;
219     jsw_anode_t *path[HEIGHT_LIMIT];
220     int top = 0, dir, cmp;
221
222     /* Find node to remove and save path */
223     for ( ; ; ) {
224       path[top++] = it;
225
226       if ( it == tree->nil )
227         return 0;
228
229       cmp = tree->cmp ( it->data, data );
230       if ( cmp == 0 )
231         break;
232
233       dir = cmp < 0;
234       it = it->link[dir];
235     }
236
237     /* Remove the found node */
238     if ( it->link[0] == tree->nil
239       || it->link[1] == tree->nil )
240     {
241       /* Single child case */
242       int dir2 = it->link[0] == tree->nil;
243
244       /* Unlink the item */
245       if ( --top != 0 )
246         path[top - 1]->link[dir] = it->link[dir2];
247       else
248         tree->root = it->link[1];
249
250       tree->rel ( it->data );
251       free ( it );
252     }
253     else {
254       /* Two child case */
255       jsw_anode_t *heir = it->link[1];
256       jsw_anode_t *prev = it;
257
258       while ( heir->link[0] != tree->nil ) {
259         path[top++] = prev = heir;
260         heir = heir->link[0];
261       }
262
263       /*
264         Order is important!
265         (free item, replace item, free heir)
266       */
267       tree->rel ( it->data );
268       it->data = heir->data;
269       prev->link[prev == it] = heir->link[1];
270       free ( heir );
271     }
272
273     /* Walk back up and rebalance */
274     while ( --top >= 0 ) {
275       jsw_anode_t *up = path[top];
276
277       if ( top != 0 )
278         dir = path[top - 1]->link[1] == up;
279
280       /* Rebalance (aka. black magic) */
281       if ( up->link[0]->level < up->level - 1
282         || up->link[1]->level < up->level - 1 )
283       {
284         if ( up->link[1]->level > --up->level )
285           up->link[1]->level = up->level;
286
287         /* Order is important! */
288         skew ( up );
289         skew ( up->link[1] );
290         skew ( up->link[1]->link[1] );
291         split ( up );
292         split ( up->link[1] );
293       }
294
295       /* Fix the parent */
296       if ( top != 0 )
297         path[top - 1]->link[dir] = up;
298       else
299         tree->root = up;
300     }
301   }
302
303   --tree->size;
304
305   return 1;
306 }
307
308 size_t jsw_asize ( jsw_atree_t *tree )
309 {
310   return tree->size;
311 }
312
313 jsw_atrav_t *jsw_atnew ( void )
314 {
315   return malloc ( sizeof ( jsw_atrav_t ) );
316 }
317
318 void jsw_atdelete ( jsw_atrav_t *trav )
319 {
320   free ( trav );
321 }
322
323 /*
324   First step in traversal,
325   handles min and max
326 */
327 static void *start ( jsw_atrav_t *trav,
328   jsw_atree_t *tree, int dir )
329 {
330   trav->tree = tree;
331   trav->it = tree->root;
332   trav->top = 0;
333
334   /* Build a path to work with */
335   if ( trav->it != tree->nil ) {
336     while ( trav->it->link[dir] != tree->nil ) {
337       trav->path[trav->top++] = trav->it;
338       trav->it = trav->it->link[dir];
339     }
340   }
341
342   /* Could be nil, but nil->data == NULL */
343   return trav->it->data;
344 }
345
346 /*
347   Subsequent traversal steps,
348   handles ascending and descending
349 */
350 static void *move ( jsw_atrav_t *trav, int dir )
351 {
352   jsw_anode_t *nil = trav->tree->nil;
353
354   if ( trav->it->link[dir] != nil ) {
355     /* Continue down this branch */
356     trav->path[trav->top++] = trav->it;
357     trav->it = trav->it->link[dir];
358
359     while ( trav->it->link[!dir] != nil ) {
360       trav->path[trav->top++] = trav->it;
361       trav->it = trav->it->link[!dir];
362     }
363   }
364   else {
365     /* Move to the next branch */
366     jsw_anode_t *last;
367
368     do {
369       if ( trav->top == 0 ) {
370         trav->it = nil;
371         break;
372       }
373
374       last = trav->it;
375       trav->it = trav->path[--trav->top];
376     } while ( last == trav->it->link[dir] );
377   }
378
379   /* Could be nil, but nil->data == NULL */
380   return trav->it->data;
381 }
382
383 void *jsw_atfirst ( jsw_atrav_t *trav, jsw_atree_t *tree )
384 {
385   return start ( trav, tree, 0 ); /* Min value */
386 }
387
388 void *jsw_atlast ( jsw_atrav_t *trav, jsw_atree_t *tree )
389 {
390   return start ( trav, tree, 1 ); /* Max value */
391 }
392
393 void *jsw_atnext ( jsw_atrav_t *trav )
394 {
395   return move ( trav, 1 ); /* Toward larger items */
396 }
397
398 void *jsw_atprev ( jsw_atrav_t *trav )
399 {
400   return move ( trav, 0 ); /* Toward smaller items */
401 }