summaryrefslogtreecommitdiff
path: root/Build/source/texk/web2c/mplibdir/avl.h
blob: 9771c0952201108880e2c8447458db92b5fc290e (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466

/*
    pyavl -- HEADER FILE "avl.h"
    Interface to manipulate "objects" of type 'avl_tree' and 'avl_iterator'
*/

#ifndef __AVL__
#define __AVL__

#include <stdarg.h>
#include <stdio.h>
#include <stdlib.h>

#define avl_del mp_avl_del
#define avl_ins mp_avl_ins
#define avl_tree mp_avl_tree
#define avl_entry mp_avl_entry
#define avl_find mp_avl_find
#define avl_create mp_avl_create
#define avl_destroy mp_avl_destroy

typedef enum
{ avl_false, avl_true } avl_bool_t;

#ifndef MPW_C
#include <inttypes.h>
typedef int8_t avl_code_t;
typedef int8_t avl_bal_t;
typedef uint32_t avl_size_t;
#else
#include <MacTypes.h>
typedef SInt8 avl_code_t;
typedef SInt8 avl_bal_t;
typedef UInt32 avl_size_t;
#endif

typedef int (*avl_compare_func) (void *param, const void *lhs,
								 const void *rhs);
typedef void *(*avl_item_copy_func) (const void *item);
typedef void *(*avl_item_dispose_func) (void *item);
typedef void (*avl_item_func) (const void *item, void *param);
typedef void *(*avl_alloc_func) (size_t);
typedef void (*avl_dealloc_func) (void *);

#ifdef      AVL_FOR_PYTHON
#undef        AVL_CMPERR
#undef		  AVL_NULLCHECKS
#define       AVL_CMPERR 1
#define       AVL_NULLCHECKS 1
#else
#ifndef		AVL_CMPERR
#define       AVL_CMPERR 0
#endif
#ifndef		AVL_NULLCHECKS
#define       AVL_NULLCHECKS 0
#endif
#endif

#if AVL_CMPERR != 0
extern avl_code_t avl_errcmp_occurred(void *);
#endif

/* At minimum, shallow copy */

const void *avl_default_item_copy(const void *);
void *avl_default_item_dispose(void *);

#define AVL_STACK_CAPACITY  32	/* for avl_split() function */

typedef enum
{
  AVL_ITERATOR_INI_PRE,
  AVL_ITERATOR_INI_POST,
  AVL_ITERATOR_INI_INTREE
} avl_ini_t;

typedef struct avl_tree_ *avl_tree;
typedef struct avl_iterator_ *avl_iterator;

typedef struct avl_itersource_ avl_itersource_struct, *avl_itersource;

struct avl_itersource_
{
  void *p;
  /* return nonzero on error */
    avl_code_t(*f) (avl_itersource from, void **to);
};

typedef struct
{
  avl_compare_func compare;
  avl_item_copy_func copy;
  avl_item_dispose_func dispose;
  avl_alloc_func alloc;
  avl_dealloc_func dealloc;
} avl_config_struct, *avl_config;

/* -------------------------------------------------------------------------------------------------/
                                        Public Functions
---------------------------------------------------------------------------------------------------*/

/*
    --- CREATE ---
    Return a new tree and set its config.
    Return NULL on allocation failure.
	* 'alloc' defaults to malloc from stdlib
 	* 'dealloc' defaults to free from stdlib
	* 'param' user param/refcon
*/

avl_tree avl_create(avl_compare_func compare,
					avl_item_copy_func copy,
					avl_item_dispose_func dispose,
					avl_alloc_func alloc,
					avl_dealloc_func dealloc, void *param);

/*
    --- RESET ---
    Empty tree 't' as in 'avl_empty()' and modify its config.
*/

void
avl_reset(avl_tree t,
		  avl_compare_func compare,
		  avl_item_copy_func copy,
		  avl_item_dispose_func dispose,
		  avl_alloc_func alloc, avl_dealloc_func dealloc);

/*
    --- EMPTY ---
    Empty tree 't', calling its dispose_func for each item in 't'.
    The config is untouched.
*/

void avl_empty(avl_tree t);

/*
    --- DESTROY ---
    Empty tree 't' and free the handle.
*/

void avl_destroy(avl_tree t);

/*
    --- DUPLICATE (COPY) ---
    Return a copy of tree 't', using its copy_func for each item in 't'.
    Upon failure to allocate room for some item, return NULL.
*/

avl_tree avl_dup(avl_tree t, void *param);

/*
    --- EMPTYNESS ---
    Return 'avl_true' iff tree 't' is empty (i.e. the handle is NULL or 't' contains no item).
*/

avl_bool_t avl_isempty(avl_tree t);

/*
    --- SIZE ---
    Return number of items contained in tree 't'.
*/

avl_size_t avl_size(avl_tree t);

/*
    --- FIRST (MINIMUM) ---
    Return first item in in-order traversal of 't'.
    Return NULL if 't' is empty.
*/

void *avl_first(avl_tree t);

/*
    --- LAST (MAXIMUM) ---
    Return last item in in-order traversal of 't'.
    Return NULL if 't' is empty.
*/

void *avl_last(avl_tree t);

/*
    --- FIND MATCHING ITEM ---
    Find item matching 'item' parameter in tree 't'.
    Return NULL if it's not found.
    If there are multiple matches, the first one that is encountered
    during the search is returned; it may not be the one with lowest rank.
*/

void *avl_find(const void *item, avl_tree t);

/*
    --- INDEX (RANK) OF ITEM ---
    Return smallest index 'i' s.t. 't[i]' matches 'item',
    or zero if 'item' is not found.
*/

avl_size_t avl_index(const void *item, avl_tree t);

/*
    --- SPAN ITEMS ---
    Return integers 'i,j' s.t. 't[i,j]'
    i smallest index s.t. t[i] >= lo_item, or t->count+1 and
    j greatest one s.t. t[j] <= hi_item, or 0.
    If 'hi_item' is less than 'lo_item' those are swapped.
    Return codes:
 		 0		success
 		-1		error: tree had no root
 		-2		error: compare failed
*/

avl_code_t
avl_span(const void *lo_item,
		 const void *hi_item,
		 avl_tree t, avl_size_t * lo_idx, avl_size_t * hi_idx);

/*
    --- FIND AT LEAST ---
    Return smallest item in 't' that is GEQ 'item', or NULL.
*/

void *avl_find_atleast(const void *item, avl_tree t);

/*
    --- FIND AT MOST ---
    Return largest item in 't' that is LEQ 'item', or NULL.
*/

void *avl_find_atmost(const void *item, avl_tree t);

/*
    --- FIND BY INDEX (RANK) ---
    Find item in 't' by index, that is return 't[idx]'.
    If 'idx' is not in '[1,avl_size(t)]' then return NULL.
 	If a compare failed then return NULL.
*/

void *avl_find_index(avl_size_t idx, avl_tree t);

/*
    --- INSERTION ---
    Insert 'item' in tree 't' with regard to its compare_func.
    Say 'avl_ins(item,t,avl_true)' to insert 'item' in 't'
    even if it is there already.
    If 'item' is a duplicate and 'allow_duplicates' is avl_false,
    nothing is done.
    Return codes:
            -1      error: allocation of new node failed
			-2		error: compare failed, tree unchanged
             0      nothing was done, no error
            +1      operation successful
            +2      the same and height(t) increased by one.
*/

avl_code_t avl_ins(void *item, avl_tree t, avl_bool_t allow_duplicates);

/*
    --- DELETION ---
    Remove 'item' from tree 't', calling its dispose_func.
    To make a backup of 'item' involving its copy_func,
    say 't(item,backup)' where 'backup' is some pointer to pointer to item.
    Otherwise set it to NULL.
    Return codes:
             0      item not found
			-2		error: compare failed, tree unchanged
            +1      operation successful
            +2      the same and height(t) decreased by one.
*/

avl_code_t avl_del(void *item, avl_tree t, void **backup);

/*
    --- DELETE FIRST ---
    Remove first item in in-order traversal from tree 't'.
    Note that only one item is removed.
    Return +1 or +2 as above.
*/

avl_code_t avl_del_first(avl_tree t, void **backup);

/*
    --- DELETE LAST ---
    Remove last item in in-order traversal from tree 't'.
    Note that only one item is removed.
    Return +1 or +2 as above.
*/

avl_code_t avl_del_last(avl_tree t, void **backup);

/*
    --- INSERT IN FRONT OF INDEX ---
    Insert 'item' in tree 't' so that afterwards,
    't[idx]=item' except if 'idx<=0' or 'idx>size(t)+1'.
    To append 'item' to 't' regardless of order, 
    say 'avl_ins_index(item,size+1,t)'.
*/

avl_code_t avl_ins_index(void *item, avl_size_t idx, avl_tree t);

/*
    --- DELETE ITEM BY INDEX ---
    Remove item of rank 'idx' from tree 't' and 
    return +1 or +2 as above except if 'idx' is not in
    '[1,avl_size(t)]' in which case return 0.
*/

avl_code_t avl_del_index(avl_size_t idx, avl_tree t, void **backup);

/*
    --- IN-PLACE CONCATENATION ---
    Pre-condition: 't0' and 't1' are valid avl_trees
    Note that the code does not check whether the maximal item in 't0' is LEQ than
    the minimal item in 't1'.
    Post-condition: 't0' handles the concatenation of
    't0' and 't1' which becomes empty (but its config is untouched).
*/

void avl_cat(avl_tree t0, avl_tree t1);

/*
    --- SPLITTING ---
    Pre-condition: 't0' and 't1' are existing handles.
    Post-condition: items in 't0' all compare LEQ than 'item'
    and items in 't1' all compare GEQ than 'item'.
    This implementation removes one item.
 	Return codes:
 		 0		item not found, no-op
 		-2		compare failed, tree unchanged
 		+1		success
*/

avl_code_t avl_split(const void *item, avl_tree t, avl_tree t0, avl_tree t1);

/*
    --- IN-ORDER TRAVERSAL ---
    Walk tree 't' in in-order, applying 'proc' at each node.
    The 'param' pointer is passed to 'proc', like this:
    '(*proc) (item_at_node,param)'.
*/

void avl_walk(avl_tree t, avl_item_func proc, void *param);

/*
    --- SLICE ---
    Create a _new tree_ from the slice 't[lo_idx,hi_idx)'
    provided 'lo_idx <= hi_idx' and these indices
    are both in range. If a new tree can't be created
    or if some item can't be allocated, return NULL.
    Otherwise if the indices are inconsistent return NULL.
*/

avl_tree
avl_slice(avl_tree t, avl_size_t lo_idx, avl_size_t hi_idx, void *param);

/* ----------------------------------------------------------/
                            ITERATORS
                        
    An iterator assigned to a tree 't' is still usable after
    any item is inserted into 't' and after any item
    not located at this iterator's current position is
    deleted. The 'avl_iterator_del()' function may be used
    to remove the item at the iterator's current position.
------------------------------------------------------------*/

/*
    --- ITERATOR --- SEEK
    Find 'item' in this iterator's tree as in 'avl_find()'
    and make it the current position.
*/

void avl_iterator_seek(const void *item, avl_iterator iter);

/*
    --- ITERATOR --- COUNT
    Return size of this iterator's tree
*/

avl_size_t avl_iterator_count(avl_iterator iter);

/*
    --- ITERATOR --- SEEK BY INDEX
    Set the current position of 'iter' to 't[idx]'
    where 't' is the tree that is iterated over.
*/

void avl_iterator_seek_index(avl_size_t idx, avl_iterator iter);

/*
    --- ITERATOR --- CURRENT POSITION
    Return item at current position of 'iter'.
*/

void *avl_iterator_cur(avl_iterator iter);

/*
    --- ITERATOR --- INDEX
    Return rank of current item of 'iter' (as a result of computation)
    except it returns 0 or size of tree plus one if 'iter' is a pre- or post- iterator.
*/

avl_size_t avl_iterator_index(avl_iterator iter);

/*
    --- ITERATOR --- CREATE
    Return a new cursor for tree 't'. 
    If allocation of an iterator struct is impossible, return NULL.
    Say 'avl_iterator_new(t, ini)' with 'ini==AVL_ITERATOR_INI_PRE' or 'ini==AVL_ITERATOR_INI_POST'
    or say 'avl_iterator_new(t, AVL_ITERATOR_INI_INTREE, item_pointer)'
    to set the iterator's current position via 'avl_iterator_seek(item_pointer,the_iterator)'.
    In the latter case, the iterator is flagged
    as pre-iterator if the item is not found.
*/

avl_iterator avl_iterator_new(avl_tree t, avl_ini_t ini, ...);

/*
    --- ITERATOR --- KILL
    Cleanup: free the iterator struct.
*/

void avl_iterator_kill(avl_iterator iter);

/*
    --- ITERATOR --- SUCCESSOR
    Get next item pointer in iterator or NULL.
    'iter' is flagged as post-iterator if it's in post-position.
*/

void *avl_iterator_next(avl_iterator iter);

/*
    --- ITERATOR --- PREDECESSOR
    Get next item pointer in iterator or NULL.
    'iter' is flagged as pre-iterator if it's in pre-position.
*/

void *avl_iterator_prev(avl_iterator iter);

/*
    --- ITERATOR --- DELETION
    Remove item at current position of iterator 'iter' from its tree, if there is one.
    Current position is set to next item or iterator is flagged as post-iterator.
*/

avl_code_t avl_iterator_del(avl_iterator iter, void **backup);

/*
    --- VERIFICATION ---
    Return avl_true iff 't' is a valid avl_tree.
    Note that 'avl_verify(NULL)==avl_false'.
*/

#ifdef HAVE_AVL_VERIFY
avl_bool_t avl_verify(avl_tree t);
#endif /* HAVE_AVL_VERIFY */

/*
    --- LOAD ---
    More general version of avl_slice
*/

avl_tree
avl_xload(avl_itersource src,
		  void **pres, avl_size_t len, avl_config conf, void *param);

#endif /* __AVL__ */