#ifndef WH_AVL_H_c76525af_
#define WH_AVL_H_c76525af_

/* This file is in the public domain. */

/*
 * Package providing AVL trees, self-balancing binary search trees.
 *
 * The details are opaque; all accesses go through calls.  The
 *  differences between particular AVL trees (eg, strings versus
 *  integers) are handled with an ops struct.  (The ops struct also
 *  contains a few other things, such as a flags field.)
 *
 * The data values are fundamentally stored as void * pointers.  What
 *  these pointers point to is opaque to the AVL tree package; it does
 *  nothing with these values but pass them to ops functions (and, for
 *  some calls, return them).  They do not even have to point to
 *  anything, though code that does anything with pointers that neither
 *  are nil nor point to things is in violation of C requirements.
 *  While data pointers may be nil, there are functions (such as
 *  avl_delete) that return a data pointer or nil; if nil is used as a
 *  data pointer, such returns may be ambiguous as a result.
 *
 * Two data pointers may be considered duplicates.  By definition, two
 *  pointers are considered duplicates whenever the tree's compare
 *  function returns zero for them.
 *
 * For ease of language, the descriptions below speak of nodes being
 *  less than, greater than, or equal to one another.  This always
 *  refers to strictly the values returned by the comparison function.
 *  Also, when the comments speak of "the" node that satisfies some
 *  condition, for trees containing duplicates, there may be multiple
 *  such nodes.  In these cases, one of those nodes will be used, but
 *  it is specifically undefined exactly which one.
 *
 * The package will misbehave if the return values from the comparison
 *  function do not actually induce an order on the set of all data
 *  pointers.  For example, if compare(a,b)<=0 and compare(b,c)<=0,
 *  then compare(a,c) must also be <=0; similarly, if compare(a,b)<0
 *  then compare(b,a) must be >0.  (This is not an exhaustive list of
 *  restrictions; loosely put, it must be possible to define a mapping
 *  F from data values to real numbers such that compare(a,b) has the
 *  same signum as F(a)-F(b).)
 *
 * Because of C limitations, there are some internal symbols visible in
 *  this include file.  Any symbol whose name begins avl__ or AVL__
 *  should be considered internal to the implementation; using them
 *  directly is not supported and is liable to break unexpectedly.
 *
 * There are various manifest constants here defined as -2771, -2772,
 *  etc.  There is nothing particularly special about these; I just
 *  want something that's unlikely to occur by accident (and that's the
 *  only reason these aren't, say, 1, 2, etc).  At the end of the file
 *  is a comment with a list of all these constants, ordered
 *  numerically.
 *
 * There is a concept called a `noderef'.  This is a void * pointer
 *  which is a handle on a specific node in the tree.  It can be used
 *  to, for example, delete a specific node from a tree even in the
 *  presence of duplicates.  A noderef remains valid as long as that
 *  node contines to be present in that tree, but no longer than that;
 *  use of a noderef after that node has been deleted produces
 *  undefined behaviour (if you're lucky, it'll be obvious, like a
 *  coredump).
 *
 * Conceptually, all the `find' functions should have variants which
 *  return a noderef instead of a data pointer.  I haven't added these
 *  for lack of perceived need; it would be easy, if perhaps a bit
 *  tedious, to add them.  Also missing is a function which takes a
 *  noderef and returns its data pointer.
 */

typedef enum {
	  AVL_PREORDER = 1,
	  AVL_INORDER,
	  AVL_POSTORDER
	  } AVL_ORDER;

typedef struct avl AVL;
typedef struct avl_walker AVL_WALKER;

/*
 * Ops vector (and flags).
 *
 * In general, the ops struct for an AVL tree must not be changed once
 *  the tree is created.  There are a few exceptions, which are
 *  specifically noted.
 */
typedef struct avl_ops AVL_OPS;
struct avl_ops {
  /*
   * Flag bits.
   *
   *	AVL_F_NODUPS
   *		The tree cannot contain duplicates.  See avl_insert for
   *		what happens when this is attempted.  This bit may be
   *		cleared at any time; it may be set, but only when the
   *		tree does not actually contain any duplicates.
   *		(Setting it when the tree does contain duplicates
   *		produces undefined behaviour from calls on the affected
   *		tree.)
   */
  unsigned int flags;
#define AVL_F_NODUPS 0x00000001
  /*
   * Compare two nodes.  Returns negative, zero, or positive according
   *  as the first arg is to be considered less than, equal to, or
   *  greater than the second.
   */
  int (*compare)(void *, void *);
  } ;

/*
 * Allocator.  By default, AVL trees allocate memory with malloc() and
 *  free it with free().  But, for special purposes, it can be useful
 *  to use a different allocator.  This supports that.
 *
 * The calling sequences are similar to malloc() and free(), but not
 *  identical.  The malloc() analog takes int rather than size_t (all
 *  the blocks allocated by this code are small) and the free() analog
 *  takes the size as well as a pointer to the block.
 *
 * The library uses only a few different sizes of block - two, at this
 *  writing.
 */
typedef struct avl_alloc AVL_ALLOC;
struct avl_alloc {
  // malloc() analog.
  void *(*get)(int);
  // free() analog.
  void (*put)(void *, int);
  } ;

/*
 * Create a new, empty, AVL tree with the given operations struct.  All
 *  options use the defaults.
 */
extern AVL *avl_new(const AVL_OPS *);

/*
 * Create a new, empty, AVL tree with the given operations struct.  The
 *  variable part of the argument list consists of one or more calls to
 *  AVL_NEW_OPT_*() macros, the last of which must be
 *  AVL_NEW_OPT_END().
 *
 *	AVL_NEW_OPT_END()
 *		Ends the list of arguments.
 *	AVL_NEW_OPT_ALLOC(alloc)
 *		alloc must be a const AVL_ALLOC * expression.  This
 *		specifies the allocator for the resulting tree.  The
 *		pointed-to AVL_ALLOC need not remain valid past the
 *              time avl_new_opt returns.  The default is to use
 *              malloc() and free(); see the comment on AVL_ALLOC.
 */
extern AVL *avl_new_opt(const AVL_OPS *, ...);
#define AVL_NEW_OPT_END() AVL__NEW_OPT_END
#define AVL_NEW_OPT_ALLOC(alloc) AVL__NEW_OPT_ALLOC, avl__ensure_avl_alloc((alloc))
extern const AVL_ALLOC *avl__ensure_avl_alloc(const AVL_ALLOC *);
// See the file header comment for the values here.
#define AVL__NEW_OPT_END   (-2771)
#define AVL__NEW_OPT_ALLOC (-2772)

/*
 * Destroy an AVL tree.  The function pointer and void * arguments are
 *  a callback and argument; for each node still left in the tree, the
 *  callback is called.  Its first argument is the void * argument to
 *  avl_destroy; its second argument is the node pointer.  The calls
 *  are made in some order, but nothing is promised about what that
 *  order is - it may be any order the package finds convenient.  If
 *  the callback pointer is nil, it is as if it were a function that
 *  ignored its arguments and did nothing.
 *
 * This must be called on each AVL tree created to avoid leaking
 *  memory.
 */
extern void avl_destroy(AVL *, void (*)(void *, void *), void *);

/*
 * Insert a node into a tree.  If a matching node already exists and
 *  the tree is flagged NODUPS, the insert does not happen and the old
 *  node is returned.  Otherwise (if the tree is not NODUPS, or no
 *  duplicate exists), the new node is inserted and nil is returned.
 */
extern void *avl_insert(AVL *, void *);

/*
 * Insert a node into a tree, with optional features.  Except as
 *  modified by the options (see below), this is just like
 *  avl_insert().  The variable part of the argument list consists of
 *  one or more calls to AVL_INSERT_OPT_*() macros, the last of which
 *  must be AVL_INSERT_OPT_END().
 *
 *	AVL_INSERT_OPT_END()
 *		Ends the list of arguments.
 *	AVL_INSERT_OPT_NODEREF(np)
 *		np must be a void ** expression.  If the insert
 *		happens, *np is written with a pointer to the internal
 *		node; if not, it is written with nil.  This node
 *		reference can be used with calls like
 *		avl_delete_noderef to manipulate that particular node.
 *
 * See the file header comment for more on noderefs.
 */
extern void *avl_insert_opt(AVL *, void *, ...);
#define AVL_INSERT_OPT_END() AVL__INSERT_OPT_END
#define AVL_INSERT_OPT_NODEREF(np) AVL__INSERT_OPT_NODEREF, avl__ensure_noderef((np))
extern void **avl__ensure_noderef(void **);
// See the file header comment for the values here.
#define AVL__INSERT_OPT_END     (-2773)
#define AVL__INSERT_OPT_NODEREF (-2774)

/*
 * Find a node in a tree.  If the tree contains a node which duplicates
 *  the argument, it is returned; otherwise, nil is returned.  In no
 *  case is the tree changed.
 */
extern void *avl_find(AVL *, void *);

/*
 * Find the first (minimum by the tree's comparison criterion) node in
 *  the tree.  If the tree contains any nodes, the minimum one is
 *  returned, otherwise nil.
 */
extern void *avl_find_first(AVL *);

/*
 * Find the first (minimum by the tree's comparison criterion) node
 *  which is at least as large as the argument.  If there is a node in
 *  the tree which compares >= the argument, the first such is
 *  returned; otherwise, nil is returned.  In no case is the tree
 *  changed.
 */
extern void *avl_find_first_ge(AVL *, void *);

/*
 * Find the first (minimum by the tree's comparison criterion) node
 *  which is strictly larger than the argument.  If there is a node in
 *  the tree which compares > the argument, the first such is returned;
 *  otherwise, nil is returned.  In no case is the tree changed.
 */
extern void *avl_find_first_gt(AVL *, void *);

/*
 * Find the last (maximum by the tree's comparison criterion) node in
 *  the tree.  If the tree contains any nodes, the maximum one is
 *  returned, otherwise nil.
 */
extern void *avl_find_last(AVL *);

/*
 * Find the last (maximum by the tree's comparison criterion) node
 *  which is at most as large as the argument.  If there is a node in
 *  the tree which compares <= the argument, the last such is returned;
 *  otherwise, nil is returned.  In no case is the tree changed.
 */
extern void *avl_find_last_le(AVL *, void *);

/*
 * Find the last (maximum by the tree's comparison criterion) node
 *  which is strictly less than the argument.  If there is a node in
 *  the tree which compares < the argument, the last such is returned;
 *  otherwise, nil is returned.  In no case is the tree changed.
 */
extern void *avl_find_last_lt(AVL *, void *);

/*
 * Delete a node from a tree.  If the tree contains a node which
 *  duplicates the argument, it is deleted and returned; otherwise, no
 *  changes are made and nil is returned.
 */
extern void *avl_delete(AVL *, void *);

/*
 * Just like the functions named similarly but with "find" instead of
 *  "delete", except that, when a node is returned, it is deleted from
 *  the tree before being returned.
 */
extern void *avl_delete_first(AVL *);
extern void *avl_delete_first_ge(AVL *, void *);
extern void *avl_delete_first_gt(AVL *, void *);
extern void *avl_delete_last(AVL *);
extern void *avl_delete_last_le(AVL *, void *);
extern void *avl_delete_last_lt(AVL *, void *);

/*
 * Delete a node by noderef.  Returns the node pointer.
 *
 * There is no error return.  Assuming the tree and noderef are still
 *  valid, it cannot error; if either is invalid, behaviour is
 *  undefined anyway, so there's no need for any error return.
 */
extern void *avl_delete_noderef(AVL *, void *);

/*
 * Walk the tree, callback style.  This takes three callbacks, one
 *  preorder, one inorder, and one postorder.  Any (or even all) of
 *  them may be nil, in which case it is as if that callback were a
 *  function which does nothing and returns zero.  It also takes a void
 *  pointer, while the callbacks each take two void * arguments.  The
 *  first callback argument is the void * passed to the walk function;
 *  the second callback argument is the node pointer (the thing passed
 *  to avl_insert).
 *
 * All callbacks return an int.  In every case, if the callback returns
 *  a negative int, the walk stops immediately, returning that int
 *  without visiting any further nodes or making any further callbacks.
 *  Otherwise, the value returned from the walk function is the sum of
 *  all the values returned by the callbacks.
 */
extern int avl_walk(AVL *,
	int (*)(void *, void *),	// preorder
	int (*)(void *, void *),	// inorder
	int (*)(void *, void *),	// postorder
	void *);

/*
 * Walk the tree, call style.  avl_walk_tree takes a tree and an
 *  AVL_ORDER value, returning an opaque AVL_WALKER pointer.
 *  avl_walk_next returns the next node in the specified order.
 *  avl_walk_done cleans up.  avl_walk_next produces undefined
 *  behaviour if the tree has been modified between avl_walk_start and
 *  avl_walk_next, but it is safe to modify the tree provided the next
 *  call made on the AVL_WALKER is avl_walk_done.
 */
extern AVL_WALKER *avl_walk_start(AVL *, AVL_ORDER);
extern void *avl_walk_next(AVL_WALKER *);
extern void avl_walk_done(AVL_WALKER *);

/*
 * Return the block sizes used by the library internally (useful when
 *  using avl_new_opt's AVL_NEW_OPT_ALLOC facility).
 *
 *	int avl_alloc_sizes(int *vp, int nv)
 *
 * Always returns the number (called N here) of distinct sizes the
 *  library wants to allocate.  If N <= nv, also stores those sizes
 *  into vp[0] through vp[N-1], in an unspecified order.
 */
extern int avl_alloc_sizes(int *, int);

/*
 * Magic number defines, ordered numerically:
-2771	AVL__NEW_OPT_END
-2772	AVL__NEW_OPT_ALLOC
-2773	AVL__INSERT_OPT_END
-2774	AVL__INSERT_OPT_NODEREF
*/

#endif