1/*	$NetBSD$	*/
2
3/* testavl.c - Test Tim Howes AVL code */
4/* OpenLDAP: pkg/ldap/libraries/liblutil/testtavl.c,v 1.2.2.5 2010/04/13 20:23:07 kurt Exp */
5/* This work is part of OpenLDAP Software <http://www.openldap.org/>.
6 *
7 * Copyright 1998-2010 The OpenLDAP Foundation.
8 * All rights reserved.
9 *
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted only as authorized by the OpenLDAP
12 * Public License.
13 *
14 * A copy of this license is available in the file LICENSE in the
15 * top-level directory of the distribution or, alternatively, at
16 * <http://www.OpenLDAP.org/license.html>.
17 */
18/* Portions Copyright (c) 1993 Regents of the University of Michigan.
19 * All rights reserved.
20 *
21 * Redistribution and use in source and binary forms are permitted
22 * provided that this notice is preserved and that due credit is given
23 * to the University of Michigan at Ann Arbor. The name of the University
24 * may not be used to endorse or promote products derived from this
25 * software without specific prior written permission. This software
26 * is provided ``as is'' without express or implied warranty.
27 */
28/* ACKNOWLEDGEMENTS:
29 * This work was originally developed by the University of Michigan
30 * (as part of U-MICH LDAP). Additional contributors include
31 *   Howard Chu
32 */
33
34#include "portable.h"
35
36#include <stdio.h>
37
38#include <ac/stdlib.h>
39#include <ac/string.h>
40
41#define AVL_INTERNAL
42#include "avl.h"
43
44static void ravl_print LDAP_P(( Avlnode *root, int depth, int thread ));
45static void myprint LDAP_P(( Avlnode *root ));
46static int avl_strcmp LDAP_P(( const void *s, const void *t ));
47
48int
49main( int argc, char **argv )
50{
51	Avlnode	*tree = NULL, *n;
52	char	command[ 10 ];
53	char	name[ 80 ];
54	char	*p;
55
56	printf( "> " );
57	while ( fgets( command, sizeof( command ), stdin ) != NULL ) {
58		switch( *command ) {
59		case 'n':	/* new tree */
60			( void ) tavl_free( tree, free );
61			tree = NULL;
62			break;
63		case 'p':	/* print */
64			( void ) myprint( tree );
65			break;
66		case 't':	/* traverse with first, next */
67			printf( "***\n" );
68			for ( n = tavl_end( tree, TAVL_DIR_LEFT );
69			    n != NULL;
70				n = tavl_next( n, TAVL_DIR_RIGHT ))
71				printf( "%s\n", n->avl_data );
72			printf( "***\n" );
73			break;
74		case 'f':	/* find */
75			printf( "data? " );
76			if ( fgets( name, sizeof( name ), stdin ) == NULL )
77				exit( EXIT_SUCCESS );
78			name[ strlen( name ) - 1 ] = '\0';
79			if ( (p = (char *) tavl_find( tree, name, avl_strcmp ))
80			    == NULL )
81				printf( "Not found.\n\n" );
82			else
83				printf( "%s\n\n", p );
84			break;
85		case 'i':	/* insert */
86			printf( "data? " );
87			if ( fgets( name, sizeof( name ), stdin ) == NULL )
88				exit( EXIT_SUCCESS );
89			name[ strlen( name ) - 1 ] = '\0';
90			if ( tavl_insert( &tree, strdup( name ), avl_strcmp,
91			    avl_dup_error ) != 0 )
92				printf( "\nNot inserted!\n" );
93			break;
94		case 'd':	/* delete */
95			printf( "data? " );
96			if ( fgets( name, sizeof( name ), stdin ) == NULL )
97				exit( EXIT_SUCCESS );
98			name[ strlen( name ) - 1 ] = '\0';
99			if ( tavl_delete( &tree, name, avl_strcmp ) == NULL )
100				printf( "\nNot found!\n" );
101			break;
102		case 'q':	/* quit */
103			exit( EXIT_SUCCESS );
104			break;
105		case '\n':
106			break;
107		default:
108			printf("Commands: insert, delete, print, new, quit\n");
109		}
110
111		printf( "> " );
112	}
113
114	return( 0 );
115}
116
117static const char bfc_array[] = "\\-/";
118static const char *bfcs = bfc_array+1;
119
120static void ravl_print( Avlnode *root, int depth, int thread )
121{
122	int	i;
123
124	if ( root && !thread )
125	ravl_print( root->avl_link[1], depth+1, root->avl_bits[1] == AVL_THREAD );
126
127	for ( i = 0; i < depth; i++ )
128		printf( "   " );
129	if ( thread )
130		printf( "~" );
131	else if ( root )
132		printf( "%c", bfcs[root->avl_bf] );
133	else
134		printf( " " );
135	if ( !root) {
136		printf( ".\n" );
137		return;
138	}
139	printf( "%s\n", (char *) root->avl_data );
140
141	if ( !thread )
142	ravl_print( root->avl_link[0], depth+1, root->avl_bits[0] == AVL_THREAD );
143}
144
145static void myprint( Avlnode *root )
146{
147	printf( "********\n" );
148
149	if ( root == 0 )
150		printf( "\tNULL\n" );
151	else
152		ravl_print( root, 0, 0 );
153
154	printf( "********\n" );
155}
156
157static int avl_strcmp( const void *s, const void *t )
158{
159	return strcmp( s, t );
160}
161