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