/* trees.c - 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.
 *
 */

#include <stdio.h>
#include "tua.h"

#ifdef USE_SOFTCHIP_BTREE

/*
 * Simple interface with SoftChip Btree Library.
 */

BTREE
DEFUN (btree_new, (comp),
       compare_func_t comp AND
       makenew_func_t makenew)
{
  BT_SETUP setup = bt_setup (5, (int (*)(void *, void *))comp, 0);
  BTREE tree = bt_new (setup);

  /* the function responsible of the creation of new instances is kept
   * in the private data field of the tree
   */
  bt_setData (tree, makenew);
  bt_freeSetup (setup);
  return tree;
}

PTR
DEFUN (btree_insert, (btree, data),
       BTREE btree AND PTR data)
{
  PTR node = bt_search (btree, data, 0);

  if (node == NULL)
    {
      makenew_func_t makenew = bt_data (btree);

      node = (*makenew) (data);

      if (bt_insert (btree, node, 0) == 0)
	return NULL;
    }

  return node;
}

void
DEFUN (btree_traverse, (btree, func),
       BTREE btree AND
       traverse_func_t func)
{
  /* bt_traverse will three parameters to the function. My enquiry functions
   * will use (and accept) only the first one. */
  
  bt_traverse (btree, (void (*)(void *, void *, void *)) func, 0);
}

PTR
DEFUN (btree_search, (btree, data),
       BTREE btree AND CONST PTR data)
{
  return bt_search (btree, (PTR)data, 0);
}

#else /* !USE_SOFTCHIP_BTREE */

BTREE
DEFUN (btree_new, (comp),
       int EXFUN ((*comp), (CONST PTR, CONST PTR)) AND
       PTR EXFUN ((*makenew), (CONST PTR)))
{
  BTREE tree;

  tree = (BTREE) xmalloc (sizeof (struct _btree_root));
  tree->compare = comp;
  tree->makenew = makenew;
  tree->rootNode = NULL;
  return tree;
}


static PTR
DEFUN (_btree_insert, (tree, compare, makenew, data),
       BTREE_NODE * tree AND
       compare_func_t compare AND
       makenew_func_t makenew AND
       PTR data)
{
  if (*tree == NULL)
    {
      *tree = (BTREE_NODE) xmalloc (sizeof (struct _btree_node));
      (*tree)->leftTree = (*tree)->rightTree = NULL;
      (*tree)->nodeData = (*makenew)(data);
      return (*tree)->nodeData;
    }
  else
    {
      int cmpres = (*compare)(data, (*tree)->nodeData);

      if (cmpres == 0)
	return (*tree)->nodeData;
      else if (cmpres < 0)
	return _btree_insert (&((*tree)->leftTree), compare, makenew, data);
      else
	return _btree_insert (&((*tree)->rightTree), compare, makenew, data);
    }
}

PTR
DEFUN (btree_insert, (btree, data),
       BTREE btree AND PTR data)
{
  return (btree ? _btree_insert (&(btree->rootNode), btree->compare, btree->makenew, data) : 0);
}

static void
DEFUN (_btree_traverse, (tree, func),
       BTREE_NODE tree AND
       traverse_func_t func)
{
  if (tree)
    {
      _btree_traverse (tree->leftTree, func);
      (*func) (tree->nodeData);
      _btree_traverse (tree->rightTree, func);
    }
}
  
void
DEFUN (btree_traverse, (btree, func),
       BTREE btree AND
       traverse_func_t func)
{
  if (btree)
    _btree_traverse (btree->rootNode, func);
}

static PTR
DEFUN (_btree_search, (tree, compare, data),
       BTREE_NODE tree AND
       compare_func_t compare AND
       CONST PTR data)
{
  if (tree == NULL)
    return NULL;
  else
    {
      int cmpres = (*compare)(data, tree->nodeData);

      if (cmpres == 0)
	return tree->nodeData;
      else if (cmpres < 0)
	return _btree_search (tree->leftTree, compare, data);
      else
	return _btree_search (tree->rightTree, compare, data);
    }
}

PTR
DEFUN (btree_search, (btree, data),
       BTREE btree AND CONST PTR data)
{
  return (btree ? _btree_search (btree->rootNode, btree->compare, data) : 0);
}

#endif /* if USE_SOFTCHIP_BTREE */

static size_t count;

static void
DEFUN (btree_counter, (data),
       CONST PTR data)
{
  count++;
}

size_t
DEFUN (btree_count, (btree),
       BTREE btree)
{
  count = 0;
  btree_traverse (btree, btree_counter);
  return count;
}