/* trees.h - generic binary tree management
 *
 * This file is part of TUA.
 *
 *   Copyright (C) 1991,92,93  Lele Gaifax (lele@nautilus.sublink.org)
 *
 *   This program is free software; you can redistribute it and/or modify
 *   it under the terms of the GNU General Public License as published by
 *   the Free Software Foundation; either version 2 of the license, or (at
 *   your option) any later version.
 *
 *   This program is distributed in the hope that it will be useful,
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *   GNU General Public License for more details.
 *
 *   You should have received a copy of the GNU General Public License
 *   along with this program; if not, write to the Free Software
 *   Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 *
 */

#ifndef _TREES_H
#define _TREES_H

#include "ansidecl.h"
#include "config.h"
#include "customize.h"

#if HAVE_SIZE_T_IN_STDDEF_H
#include <stddef.h>

#else

#if HAVE_SIZE_T_IN_TYPES_H
#include <sys/types.h>

#else

#if HAVE_SIZE_T_IN_STDTYPES_H
#include <sys/stdtypes.h>

#endif /* HAVE_SIZE_T_IN_STDTYPES_H */
#endif /* HAVE_SIZE_T_IN_TYPES_H */
#endif /* HAVE_SIZE_T_IN_STDDEF_H */

typedef int EXFUN((*compare_func_t), (CONST PTR, CONST PTR));
typedef PTR EXFUN((*makenew_func_t), (CONST PTR));
typedef void EXFUN((*traverse_func_t), (CONST PTR));
     
#ifdef USE_SOFTCHIP_BTREE

#include <btree.h>

#else /* don't use SoftChip */

typedef struct _btree_node
{
  struct _btree_node * leftTree;
  struct _btree_node * rightTree;
  PTR nodeData;
} * BTREE_NODE;

typedef struct _btree_root
{
  compare_func_t compare;	/* function used to compare two nodes */
  makenew_func_t makenew;	/* function used to allocate a new node */
  BTREE_NODE rootNode;
} *BTREE;

#endif /* ifdef USE_SOFTCHIP_BTREE */

/*
 Create a new btree.

 COMPARE will be used for comparison, and it adopt
 the protocol used in str?cmp(), ie returns 0 for equal data, -1 if the
 first parm is less the the second, 1 otherwise.

 MAKENEW will be used when inserting new nodes in the tree. It takes an
 address of a node as the only parameter, containing the key field.
 makenew() should use it to alloc a copy of it, maybe initializing the
 other fields.
*/
extern BTREE EXFUN(btree_new, (compare_func_t compare, makenew_func_t makenew));

/* Insert some data in the tree */     
extern PTR EXFUN(btree_insert, (BTREE, PTR));

/*
 * Call the function for each node in the tree, passing the
 * node data as the only argument
 */
extern void EXFUN(btree_traverse, (BTREE, traverse_func_t func));

/* Search for some data in the tree */     
extern PTR EXFUN(btree_search, (BTREE, CONST PTR));          

/* Returns the number of items stored in the tree */
extern size_t EXFUN(btree_count, (BTREE));
     
#endif /* _TREES_H */