/*
 * Copyright (c) 2002-2004 Sendmail, Inc. and its suppliers.
 *	All rights reserved.
 *
 * By using this file, you agree to the terms and conditions set
 * forth in the LICENSE file which can be found at the top level of
 * the sendmail distribution.
 *
 */

#include "sm/generic.h"
SM_RCSID("@(#)$Id: t-tree-1.c,v 1.14 2004/12/26 04:08:53 ca Exp $")

#include <stdio.h>

#include "sm/assert.h"
#include "sm/tree.h"
#include "sm/test.h"

#define MAX_KEYS	1024

static int
sm_tree_key_compare(sm_tree_key_T k1, sm_tree_key_T k2, uint len)
{
	return (*(int *)k1) - (*(int *)k2);
}

static void
print_tree(sm_tree_P tree)
{
	sm_tree_node_P cur;

	cur = sm_tree_first(tree);
	while (cur != NULL)
	{
		printf("tree: key=%d, data=%d, balance=%d\n",
			*(int *) cur->sm_tree_key,
			*(int *) (cur->sm_tree_data),
			cur->sm_tree_balance);
		cur = sm_tree_next(tree, cur);
	}
}

static void
show_tree(sm_tree_node_P n, int d)
{
	if (n == NULL)
		return;
	printf("%*skey=%d, data=%d, balance=%d\n",
		2 * d, " ",
		* (int *) n->sm_tree_key,
		* (int *) (n->sm_tree_data),
		n->sm_tree_balance);
	show_tree(n->sm_tree_left, d + 1);
	show_tree(n->sm_tree_right, d + 1);
}

#define TINS(x, y)	\
	do {							\
	int res;						\
	res = sm_tree_add(tree, (sm_tree_key_T) &keys[x], sizeof(int *), (void *) &keys[y]);	\
	SM_TEST(res >= 0);					\
	if (res < 0)						\
	{							\
		fprintf(stderr, "sm_tree_add failed\n");	\
		SM_TEST(0);					\
		exit(1);					\
	}							\
	} while (0)

#define TREE_SEARCH(r) sm_tree_lookup(tree, (sm_tree_key_T) &keys[r], sizeof(int *))
#define TREE_RM(r) sm_tree_rm(tree, (sm_tree_key_T) &keys[r], sizeof(int *))

#define GETONE()	if (scanf("%d", &v) != 1) exit(2); else
#define GETTWO()	if (scanf("%d %d", &v, &d) != 2) exit(3); else

int
main(int argc, char *argv[])
{
	int a, v, r, d;
	bool interactive;
	sm_tree_P tree;
	sm_tree_node_P tn;
	sm_tree_node_P hn;
	int keys[MAX_KEYS];
	sm_ret_T ret;

	interactive = false;
	while ((a = getopt(argc, argv, "i")) != -1)
	{
		switch (a)
		{
		  case 'i':
			interactive = true;
			break;
		  default:
			(void) fprintf(stderr,
				"Unknown command line option -%c\n", optopt);
			(void) fprintf(stderr, "%s: %s [-i]\n", argv[0],
				argv[0]);
			exit(1);
		}
	}
	sm_test_begin(argc, argv, "test tree 1");
	tree = sm_tree_create(NULL, 0, sm_tree_key_compare);
	SM_TEST(tree != NULL);
	for (a = 0; a < MAX_KEYS; a++)
		keys[a] = a;
	TINS(3, 3);
	TINS(5, 5);
	TINS(6, 6);
	TINS(4, 4);
	TINS(2, 2);
	if (!interactive)
		goto end;
	print_tree(tree);
	tn = NULL;
	printf("depth: %d\n", sm_tree_depth(tn));
	while ((a = getchar()) != EOF && a != 'q')
	{
		switch(a)
		{
		  case 'i':
			GETTWO();
			if (v >= MAX_KEYS || d >= MAX_KEYS)
				break;
			TINS(v, d);
			break;
		  case 'v':
			show_tree(tn, 0);
			break;
		  case 'p':
			print_tree(tree);
			break;
		  case 'd':
			printf("depth: %d\n", sm_tree_depth(tn));
			break;
		  case 's':
			GETONE();
			if (v >= MAX_KEYS)
				break;
			hn = sm_tree_lookup(tree, (sm_tree_key_T) &keys[v], sizeof(int *));
			printf("%sfound\n", (hn == NULL) ? "Not " : "");
			break;
		  case 'r':
			GETONE();
			if (v >= MAX_KEYS)
				break;
			r = sm_tree_rm(tree, (sm_tree_key_T) &keys[v], sizeof(int *));
			printf("result=%d\n", r);
			break;
		}
	}
  end:
	if (tree != NULL)
	{
		ret = sm_tree_destroy(tree);
		SM_TEST(ret == SM_SUCCESS);
	}
	return sm_test_end();
}