/*
 * This source file is part of Vahunz,
 * a tool to make source code un-/more legible.
 *
 *--------------------------------------------------------------------------
 *
 * Vahunz and the Ugly library are Copyright (C) 1998 by
 * Thomas Aglassinger <agi@giga.or.at>
 *
 * All rights reserved.
 *
 * Refer to the manual for more information.
 *
 *--------------------------------------------------------------------------
 *
 * Ubiqx library is Copyright (C) 1991-1998 by
 * Christopher R. Hertel <crh@ubiqx.mn.org>
 *
 * Ubiqx library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Library General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 *
 */
#include "ubi_AVLtree.h" 
#include <stdlib.h> 
static char b9F[] = "ubi_AVLtree\n\
\t$Revision: 2.5 $\n\
\t$Date: 1997/12/23 04:00:42 $\n\
\t$Author: crh $\n";
static e6M L1( e6M p )
{
e6M j3J;
j3J = p->e2Q[w6O];
p->e2Q[w6O] = j3J->e2Q[e4E];
j3J->e2Q[e4E] = p;
j3J->e2Q[i0E] = p->e2Q[i0E];
j3J->h1V = p->h1V;
if(j3J->e2Q[i0E])
(j3J->e2Q[i0E])->e2Q[(int)(j3J->h1V)] = j3J;
p->e2Q[i0E] = j3J;
p->h1V = e4E;
if( p->e2Q[w6O] )
{
p->e2Q[w6O]->e2Q[i0E] = p;
(p->e2Q[w6O])->h1V = w6O;
}
p->n7P -= q2Q( j3J->n7P );
(j3J->n7P)--;
return( j3J );
} 
static e6M R1( e6M p )
{
e6M j3J;
j3J = p->e2Q[e4E];
p->e2Q[e4E] = j3J->e2Q[w6O];
j3J->e2Q[w6O] = p;
j3J->e2Q[i0E] = p->e2Q[i0E];
j3J->h1V = p->h1V;
if(j3J->e2Q[i0E])
(j3J->e2Q[i0E])->e2Q[(int)(j3J->h1V)] = j3J;
p->e2Q[i0E] = j3J;
p->h1V = w6O;
if(p->e2Q[e4E])
{
p->e2Q[e4E]->e2Q[i0E] = p;
p->e2Q[e4E]->h1V = e4E;
}
p->n7P -= q2Q( j3J->n7P );
(j3J->n7P)++;
return( j3J );
} 
static e6M L2( e6M j5L )
{
e6M j3J, l1B;
j3J = j5L->e2Q[w6O];
l1B = j3J->e2Q[e4E];
j3J->e2Q[e4E] = l1B->e2Q[w6O];
l1B->e2Q[w6O] = j3J;
j5L->e2Q[w6O] = l1B->e2Q[e4E];
l1B->e2Q[e4E] = j5L;
l1B->e2Q[i0E] = j5L->e2Q[i0E];
l1B->h1V = j5L->h1V;
j5L->e2Q[i0E] = l1B;
j5L->h1V = e4E;
j3J->e2Q[i0E] = l1B;
j3J->h1V = w6O;
if( j5L->e2Q[w6O] )
{
j5L->e2Q[w6O]->e2Q[i0E] = j5L;
j5L->e2Q[w6O]->h1V = w6O;
}
if( j3J->e2Q[e4E] )
{
j3J->e2Q[e4E]->e2Q[i0E] = j3J;
j3J->e2Q[e4E]->h1V = e4E;
}
if(l1B->e2Q[i0E])
l1B->e2Q[i0E]->e2Q[(int)(l1B->h1V)] = l1B;
switch( l1B->n7P )
{
case e4E :
j5L->n7P = g8I; j3J->n7P = w6O; break;
case g8I:
j5L->n7P = g8I; j3J->n7P = g8I; break;
case w6O:
j5L->n7P = e4E; j3J->n7P = g8I; break;
}
l1B->n7P = g8I;
return( l1B );
} 
static e6M R2( e6M j5L )
{
e6M j3J, l1B;
j3J = j5L->e2Q[e4E];
l1B = j3J->e2Q[w6O];
j3J->e2Q[w6O] = l1B->e2Q[e4E];
l1B->e2Q[e4E] = j3J;
j5L->e2Q[e4E] = l1B->e2Q[w6O];
l1B->e2Q[w6O] = j5L;
l1B->e2Q[i0E] = j5L->e2Q[i0E];
l1B->h1V = j5L->h1V;
j5L->e2Q[i0E] = l1B;
j5L->h1V = w6O;
j3J->e2Q[i0E] = l1B;
j3J->h1V = e4E;
if( j5L->e2Q[e4E] )
{
j5L->e2Q[e4E]->e2Q[i0E] = j5L;
j5L->e2Q[e4E]->h1V = e4E;
}
if( j3J->e2Q[w6O] )
{
j3J->e2Q[w6O]->e2Q[i0E] = j3J;
j3J->e2Q[w6O]->h1V = w6O;
}
if(l1B->e2Q[i0E])
l1B->e2Q[i0E]->e2Q[(int)(l1B->h1V)] = l1B;
switch( l1B->n7P )
{
case e4E :
j5L->n7P = w6O; j3J->n7P = g8I; break;
case g8I :
j5L->n7P = g8I; j3J->n7P = g8I; break;
case w6O :
j5L->n7P = g8I; j3J->n7P = e4E; break;
}
l1B->n7P = g8I;
return( l1B );
} 
static e6M t9D( e6M p, char l3J )
{
if( p->n7P != l3J )
p->n7P += q2Q(l3J);
else
{
char r5P; 
r5P = p->e2Q[(int)l3J]->n7P;
if( ( g8I == r5P ) || ( p->n7P == r5P ) )
p = ( (e4E==l3J) ? R1(p) : L1(p) ); 
else
p = ( (e4E==l3J) ? R2(p) : L2(p) ); 
}
return( p );
} 
static e6M s0W( e6M g2I,
e6M l9D,
char l3J )
{
while( l9D )
{
l9D = t9D( l9D, l3J );
if( i0E == l9D->h1V )
return( l9D );
if( g8I == l9D->n7P )
return( g2I );
l3J = l9D->h1V;
l9D = l9D->e2Q[i0E];
}
return( g2I );
} 
static e6M h1T( e6M g2I,
e6M l9D,
char l3J )
{
while( l9D )
{
l9D = t9D( l9D, h3H(l3J) );
if( i0E == l9D->h1V )
return( l9D );
if( g8I != l9D->n7P )
return( g2I );
l3J = l9D->h1V;
l9D = l9D->e2Q[i0E];
}
return( g2I );
} 
static void b5P( e6M *u8S,
e6M k2O,
e6M t1D )
{
register int i;
register int o0E = sizeof( v5T );
for( i = 0; i < o0E; i++ )
((unsigned char *)t1D)[i] = ((unsigned char *)k2O)[i];
(*u8S) = t1D;
if(k2O->e2Q[e4E ] )
(k2O->e2Q[e4E ])->e2Q[i0E] = t1D;
if(k2O->e2Q[w6O] )
(k2O->e2Q[w6O])->e2Q[i0E] = t1D;
} 
static void t3R( g8Sh v5F,
e6M e8Uh,
e6M c2U )
{
e6M *Parent;
v5T p7D;
e6M c0W = &p7D;
if( e8Uh->e2Q[i0E] )
Parent = &((e8Uh->e2Q[i0E])->e2Q[(int)(e8Uh->h1V)]);
else
Parent = (e6M *)&(v5F->k4S);
b5P( Parent, e8Uh, c0W );
if( c2U->e2Q[i0E] )
Parent = &((c2U->e2Q[i0E])->e2Q[(int)(c2U->h1V)]);
else
Parent = (e6M *)&(v5F->k4S);
b5P( Parent, c2U, e8Uh );
if( c0W->e2Q[i0E] )
Parent = &((c0W->e2Q[i0E])->e2Q[(int)(c0W->h1V)]);
else
Parent = (e6M *)&(v5F->k4S);
b5P( Parent, c0W, c2U );
} 
e6M j3V( e6M l9P )
{
(void)y6S( (y8Ut)l9P );
l9P->n7P = g8I;
return( l9P );
} 
h3R m0C( g8Sh v5F,
e6M i8C,
y8Or x1B,
e6M *j9B )
{
e6M y0U;
if( !(j9B) ) j9B = &y0U;
if( n5F( v5F,
(y8Ut)i8C,
x1B,
(y8Ut *)j9B ) )
{
if( (*j9B) )
i8C->n7P = (*j9B)->n7P;
else
{
i8C->n7P = g8I;
v5F->k4S = (y8Ut)s0W( (e6M)v5F->k4S,
i8C->e2Q[i0E],
i8C->h1V );
}
return( z1Zy );
}
return( d5B ); 
} 
e6M c6W( g8Sh v5F,
e6M g4C )
{
y8Ut p,
*r3Vg;
if( (g4C->e2Q[e4E]) && (g4C->e2Q[w6O]) )
t3R( v5F, g4C, l9B( g4C ) );
if( g4C->e2Q[i0E] )
r3Vg = (y8Ut *)
&((g4C->e2Q[i0E])->e2Q[(int)(g4C->h1V)]);
else
r3Vg = &( v5F->k4S );
if( g8I == g4C->n7P )
(*r3Vg) = NULL;
else
{
p = (y8Ut)(g4C->e2Q[(int)(g4C->n7P)]);
p->e2Q[i0E] = (y8Ut)g4C->e2Q[i0E];
p->h1V = g4C->h1V;
(*r3Vg) = p;
}
v5F->k4S = (y8Ut)h1T( (e6M)v5F->k4S,
g4C->e2Q[i0E],
g4C->h1V );
(v5F->count)--;
return( g4C );
} 
int z7Zy( int u0Qh, char *list[] )
{
if( u0Qh > 0 )
{
list[0] = b9F;
if( u0Qh > 1 )
return( 1 + r7F( --u0Qh, &(list[1]) ) );
return( 1 );
}
return( 0 );
}