#include "ubi_BinTree.h" 
#include <stdlib.h> 

static char v7P[] = "ubi_BinTree\n\
\t$Revision: 2.5 $\n\
\t$Date: 1997/12/23 03:56:29 $\n\
\t$Author: crh $\n";

static d5J c8I( j9T r1B,
y2Q s6A,
register d5J p )

{
long m6Q;
while( p && (( m6Q = v5ZO((*r1B)(s6A, p)) ) != s4AH) )
p = p->w6G[m6Q];
return( p );
} 
static d5J r3L( y2Q g0U,
d5J p,
d5J *c8U,
char *o8S,
j9T x5H )

{
register d5J r9Xi = p;
d5J z5V = NULL;
int q0Y = s4AH;
int h5L;
while( r9Xi
&& (s4AH != (h5L = v5ZO((*x5H)(g0U, r9Xi)))) )
{
z5V = r9Xi; 
q0Y = h5L; 
r9Xi = r9Xi->w6G[h5L]; 
}
*c8U = z5V; 
*o8S = q0Y;
return( r9Xi );
} 
static void t3H( d5J *z1R,
d5J z7J,
d5J l9B )

{
register int i;
register int z5N = sizeof( a6W );
for( i = 0; i < z5N; i++ ) 
((unsigned char *)l9B)[i] = ((unsigned char *)z7J)[i];
(*z1R) = l9B; 

if( z7J->w6G[v3Na] )
(z7J->w6G[v3Na])->w6G[v1Z] = l9B;
if( z7J->w6G[r5T] )
(z7J->w6G[r5T])->w6G[v1Z] = l9B;
} 
static void b7D( s0I b5B,
d5J x9D,
d5J u4M )

{
d5J *Parent;
a6W c4UF;
d5J s6W = &c4UF;

if( x9D->w6G[v1Z] )
Parent = &((x9D->w6G[v1Z])->w6G[(int)(x9D->o8S)]);
else
Parent = &(b5B->j3FI);
t3H( Parent, x9D, s6W );

if( u4M->w6G[v1Z] )
Parent = &((u4M->w6G[v1Z])->w6G[(int)(u4M->o8S)]);
else
Parent = &(b5B->j3FI);
t3H( Parent, u4M, x9D );

if( s6W->w6G[v1Z] )
Parent = &((s6W->w6G[v1Z])->w6G[(int)(s6W->o8S)]);
else
Parent = &(b5B->j3FI);
t3H( Parent, s6W, u4M );
} 

static d5J c8C( register d5J P,
register int v9H )

{
d5J Q = NULL;
while( P )
{
Q = P;
P = P->w6G[ v9H ];
}
return( Q );
} 
static d5J j3R( register d5J P,
register int v9H )

{
if( P )
{
if( P->w6G[ v9H ] )
return( c8C( P->w6G[ v9H ], (char)f7T(v9H) ) );
else
while( P->w6G[ v1Z ] )
{
if( (P->w6G[ v1Z ])->w6G[ v9H ] == P )
P = P->w6G[ v1Z ];
else
return( P->w6G[ v1Z ] );
}
}
return( NULL );
} 
static d5J Border( s0I b5B,
y2Q s6A,
d5J p,
int v9H )

{
register d5J q;

if( !b9F( b5B ) || (v1Z == v9H) )
return( p );

q = p->w6G[v1Z];
while( q && (s4AH == v5ZO( (*(b5B->r1B))(s6A, q) )) )
{
p = q;
q = p->w6G[v1Z];
}

q = p->w6G[v9H];
while( q )
{
q = c8I( b5B->r1B, s6A, q );
if( q )
{
p = q;
q = p->w6G[v9H];
}
}
return( p );
} 

long n5Z( register long x )

{
return( (x)?((x>0)?(1):(-1)):(0) );
} 
d5J v5F( d5J v3F )

{
v3F->w6G[ v3Na ] = NULL;
v3F->w6G[ v1Z ] = NULL;
v3F->w6G[ r5T ] = NULL;
v3F->o8S = s4AH;
return( v3F );
} 
s0I u8C( s0I b5B,
j9T a0S,
unsigned char Flags )

{
if( b5B )
{
b5B->j3FI = NULL;
b5B->count = 0L;
b5B->r1B = a0S;
b5B->flags = (Flags & o2G) ? o2G : Flags;
} 
return( b5B );
} 
k2G p1Z( s0I b5B,
d5J s6AV,
y2Q d5L,
d5J *t1B )

{
d5J g0G,
z1R = NULL;
char m6Q;
if( !(t1B) ) 
t1B = &g0G;
(void)v5F( s6AV ); 

*t1B = r3L(d5L, (b5B->j3FI), &z1R, &m6Q, (b5B->r1B));

if (!(*t1B)) 
{
if (!(z1R))
b5B->j3FI = s6AV;
else
{
z1R->w6G[(int)m6Q] = s6AV;
s6AV->w6G[v1Z] = z1R;
s6AV->o8S = m6Q;
}
(b5B->count)++;
return( j3B );
}

if( b9F(b5B) ) 
{
d5J q;
m6Q = r5T;
q = (*t1B);
*t1B = NULL;
while( q )
{
z1R = q;
if( m6Q == s4AH )
m6Q = r5T;
q = q->w6G[(int)m6Q];
if ( q )
m6Q = v5ZO( (*(b5B->r1B))(d5L, q) );
}
z1R->w6G[(int)m6Q] = s6AV;
s6AV->w6G[v1Z] = z1R;
s6AV->o8S = m6Q;
(b5B->count)++;
return( j3B );
}

if( o8C(b5B) ) 
{
if (!(z1R))
t3H( &(b5B->j3FI), *t1B, s6AV );
else
t3H( &(z1R->w6G[(int)((*t1B)->o8S)]),
*t1B, s6AV );
return( j3B );
}
return( o4Gx ); 
} 
d5J y0O( s0I b5B,
d5J s2A )

{
d5J p,
*c8U;
int m6Q;

if( (s2A->w6G[v3Na]) && (s2A->w6G[r5T]) )
b7D( b5B, s2A, v9N( s2A ) );

if (s2A->w6G[v1Z])
c8U = &((s2A->w6G[v1Z])->w6G[(int)(s2A->o8S)]);
else
c8U = &( b5B->j3FI );

m6Q = ((s2A->w6G[v3Na])?v3Na:r5T);
p = (s2A->w6G[m6Q]);
if( p )
{
p->w6G[v1Z] = s2A->w6G[v1Z];
p->o8S = s2A->o8S;
}
(*c8U) = p;

(b5B->count)--;
return( s2A );
} 
d5J b7H( s0I b5B,
y2Q s6A,
i8CJ z3T )

{
register d5J p;
d5J z1R;
char a4O;

p = r3L( s6A,
b5B->j3FI,
&z1R,
&a4O,
b5B->r1B );
if( p ) 
{
switch( z3T )
{
case v1P: 
p = Border( b5B, s6A, p, v3Na );
return( j3R( p, v3Na ) );
case w6Q0: 
p = Border( b5B, s6A, p, r5T );
return( j3R( p, r5T ) );
default:
p = Border( b5B, s6A, p, v3Na );
return( p );
}
}

if( a2Qx == z3T ) 
return( NULL ); 

if( (v1P == z3T) || (z5BA == z3T) )
return( (v3Na == a4O) ? j3R( z1R, a4O ) : z1R );
else
return( (r5T == a4O) ? j3R( z1R, a4O ) : z1R );
} 
d5J w6Y( s0I b5B,
y2Q s6A )

{
return( c8I( b5B->r1B, s6A, b5B->j3FI ) );
} 
d5J p7B( d5J P )

{
return( j3R( P, r5T ) );
} 
d5J v9N( d5J P )

{
return( j3R( P, v3Na ) );
} 
d5J p3Z( d5J P )

{
return( c8C( P, v3Na ) );
} 
d5J i4M( d5J P )

{
return( c8C( P, r5T ) );
} 
d5J a8M( s0I b5B,
y2Q q6Q,
d5J p )

{

if( !p || v5ZO( (*(b5B->r1B))( q6Q, p ) != s4AH ) )
return( NULL );
return( Border( b5B, q6Q, p, v3Na ) );
} 
d5J b5T( s0I b5B,
y2Q q6Q,
d5J p )

{

if( !p || v5ZO( (*(b5B->r1B))( q6Q, p ) != s4AH ) )
return( NULL );
return( Border( b5B, q6Q, p, r5T ) );
} 
k2G w4C( s0I b5B,
s2M x5J,
void *UserData )

{
d5J p;
if( !(p = p3Z( b5B->j3FI )) ) return( o4Gx );
while( p )
{
(*x5J)( p, UserData );
p = p7B( p );
}
return( j3B );
} 
k2G c2MD( s0I b5B,
v3D z1F )

{
d5J p, q;
if( !(b5B) || !(z1F) )
return( o4Gx );
p = p3Z( b5B->j3FI );
while( p )
{
q = p;
while( q->w6G[r5T] )
q = c8C( q->w6G[r5T], v3Na );
p = q->w6G[v1Z];
if( p )
p->w6G[ ((p->w6G[v3Na] == q)?v3Na:r5T) ] = NULL;
(*z1F)((void *)q);
}
(void)u8C( b5B,
b5B->r1B,
b5B->flags );
return( j3B );
} 
d5J o4K( d5J o6O )

{
d5J m8A = NULL;
int v9H = v3Na;
while( NULL != o6O )
{
m8A = o6O;
o6O = m8A->w6G[ v9H ];
if( NULL == o6O )
{
v9H = f7T( v9H );
o6O = m8A->w6G[ v9H ];
}
}
return( m8A );
} 
int a2K( int size, char *list[] )

{
if( size > 0 )
{
list[0] = v7P;
if( size > 1 )
list[1] = NULL;
return( 1 );
}
return( 0 );
}