1 /**************************************************************** 2 Copyright (C) 2007 David M. Gay 3 4 Permission to use, copy, modify, and distribute this software and its 5 documentation for any purpose and without fee is hereby granted, 6 provided that the above copyright notice appear in all copies and that 7 both that the copyright notice and this permission notice and warranty 8 disclaimer appear in supporting documentation. 9 10 The author disclaims all warranties with regard to this software, 11 including all implied warranties of merchantability and fitness. 12 In no event shall the author be liable for any special, indirect or 13 consequential damages or any damages whatsoever resulting from loss of 14 use, data or profits, whether in an action of contract, negligence or 15 other tortious action, arising out of or in connection with the use or 16 performance of this software. 17 ****************************************************************/ 18 19 #include <stddef.h> /* for size_t */ 20 21 typedef struct AVL_Tree AVL_Tree; 22 typedef struct Element Element; 23 24 typedef int (*AVL_Elcomp)(void*, const Element*, const Element*); 25 typedef int (*AVL_Visitor)(void*, const Element*); 26 27 extern AVL_Tree *AVL_Tree_alloc(void*, AVL_Elcomp, void *(Mallocfunc)(size_t)); 28 extern AVL_Tree *AVL_Tree_alloc2(void*, AVL_Elcomp, void *(Mallocfunc)(size_t), void (*Free)(void*)); 29 extern void AVL_Tree_free(AVL_Tree**); 30 extern size_t AVL_Tree_size(AVL_Tree*); 31 extern const Element *AVL_find(const Element *, AVL_Tree*); 32 extern const Element *AVL_insert(const Element *, AVL_Tree*); 33 extern int AVL_visit(void*, AVL_Tree*, AVL_Visitor); 34 extern const Element *AVL_delete(const Element *, AVL_Tree*); 35 extern void *AVL_setv(AVL_Tree *, void*); 36 37 /* The third argument to Avl_Tree_alloc is a malloc-like function that */ 38 /* only returns nonzero values. It should use longjmp to avoid returning */ 39 /* if no memory is available. If you are using the AMPL/Solver interface */ 40 /* library, simply pass mymalloc_ASL for this argument. */ 41 42 /* AVL_Tree_alloc returns a pointer to an AVL structure in which it has */ 43 /* stored its arguments. The current void* value (possibly a "this" */ 44 /* pointer) is passed to the comparision function. AVL_setv replaces */ 45 /* the current such void* value and returns the old value. */ 46 47 /* AVL_Tree_size(Tree) returns the number of elements in Tree. */ 48 49 /* AVL_Visit(Tree,V) calls V once for each element in Tree, from first */ 50 /* to last, in the order defined by the AVL_Elcomp associated with Tree,*/ 51 /* so long as V returns 0. The return from AVL_visit is the value */ 52 /* returned by the last call on V (or 0 if Tree is empty). */ 53 54 /* If E is not already in Tree, AVL_insert(E, Tree) adds E to Tree and */ 55 /* returns 0. If Tree contains an Element* E1 that AVL_Elcomp reports */ 56 /* to be "equal" to E (i.e., AVL_Elcomp(v,E,E1) == 0), then AVL_insert()*/ 57 /* returns E1. */ 58