//-----------------------------------------------------------------------------
// Copyright © 2003 - Philip Howard - All rights reserved
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
// as published by the Free Software Foundation; either version 2
// of the License, or (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
//-----------------------------------------------------------------------------
// package	libh/avl
// homepage	http://libh.slashusr.org/
//-----------------------------------------------------------------------------
// author	Philip Howard
// email	libh at ipal dot org
// homepage	http://phil.ipal.org/
//-----------------------------------------------------------------------------
// This file is best viewed using a fixed spaced font such as Courier
// and in a display at least 120 columns wide.
//-----------------------------------------------------------------------------

//-----------------------------------------------------------------------------
// G. M. Adelson-Velskii and E. M. Landis are the inventors of the algorithm
// bearing their initials, AVL.  Their algorithm for height-balanced binary
// search trees is the basis of the code in this package.  Some modification
// is made to the balancing operations, and features are added for practical
// purposes.
//-----------------------------------------------------------------------------

#include "avl_lib.h"

__PROTO_BEGIN__
//-----------------------------------------------------------------------------
// function	avl_balance
//
// purpose	Balance the binary tree branch containing the specified node.
//
// arguments	1 (AVL *) pointer to root of the binary tree
//		2 (avl_link *) pointer to node to do balancing from
//
// returns	(int) number of shuffles performed
//-----------------------------------------------------------------------------
int
avl_balance(
    AVL *		arg_tree
    ,
    avl_link *		arg_link
    )
__PROTO_END__
{

#ifndef AVL_DONT_BALANCE

    avl_link *	b	;
    avl_link *	c	;
    avl_link *	d	;
    avl_link *	e	;
    avl_link *	f	;

    avl_link *	l	;
    avl_link *	h	;

    avl_link *	n	;
    avl_link *	p	;

    int		dl	;
    int		dh	;


#if AVL_CHECK_INTERNAL_ARGS
    if ( ! arg_tree ) {
	return AVL_ERR_BAD_ROOT;
    }
    if ( ! arg_link ) {
	return AVL_ERR_BAD_NODE;
    }
#endif

    //-- This is here only because gcc cannot figure
    //-- out that they will not be used uninitialized.
    b = c = d = e = f = NULL;

    //-------------------------------------------
    // While below top of tree, do the balancing.
    //-------------------------------------------
    n = arg_link;
    while ( n != & ( arg_tree->link ) ) {

	p = n->pa;

	//-- Get lo and hi depths.
	dl = ( l = n->lo ) ? l->depth : 0;
	dh = ( h = n->hi ) ? h->depth : 0;

	//----------------------------------------------------------
	// Collect individual nodes differently for four conditions.
	//----------------------------------------------------------
	if ( l && dl - dh > 1 ) {
	    f = n;
	    if ( l->lo && l->lo->depth > (l->hi?l->hi->depth:0) ) {
		//----------------------------
		//     ___F___       _D_
		//   _D_      G ->  B   F
		//  B   E          A C E G
		// A C
		//----------------------------
		c = ( b = ( d = l )->lo )->hi;
	    } else if ( l->hi ) {
		//----------------------------
		//    ___F___       _D_
		//  _B_      G ->  B   F
		// A   D          A C E G
		//    C E
		//----------------------------
		c = ( d = ( b = l )->hi )->lo;
	    }
	    e = d->hi;
	} else if ( h && dl - dh < -1 ) {
	    b = n;
	    if ( h->lo && h->lo->depth > (h->hi?h->hi->depth:0) ) {
		//----------------------------
		//  ___B___         _D_
		// A      _F_  ->  B   F
		//       D   G    A C E G
		//      C E
		//----------------------------
		e = ( d = ( f = h )->lo )->hi;
	    } else if ( h->hi ) {
		//----------------------------
		//  ___B___          _D_
		// A      _D_   ->  B   F
		//       C   F     A C E G
		//          E G
		//----------------------------
		e = ( f = ( d = h )->hi )->lo;
	    }
	    c = d->lo;
	} else {

	    //-- Recompute depths of unchanged structure.
	    if ( dl < dh ) dl = dh;
	    ++ dl;

	    //-- If depth is the same, balancing is done.
	    if ( n->depth == dl ) break;

	    //-- Put new depth in link.
	    n->depth = dl;

	    //-- Continue balancing from parent.
	    n = p;
	    continue;
	}

	//------------------------------
	// Reconstruct in balanced form:
	//      _D_
	// ->  B   F
	//    A C E G
	//------------------------------
	if ( c ) c->pa = b;
	if ( e ) e->pa = f;

	b->hi = c;
	b->pa = d;

	f->pa = d;
	f->lo = e;

	d->pa = p;
	d->lo = b;
	d->hi = f;

	if ( p->lo == n ) p->lo = d;
#if AVL_PARANOID_LOGIC
	else if ( p->hi != n ) {
	    return avl_abort( arg_tree, n, "avl_balance(): orphan node being balanced" );
	}
#endif /* AVL_PARANOID_LOGIC */
	else p->hi = d;

	//-- Recompute depths of changed structure.
	dl = c ? c->depth : 0;
	if ( b->lo && b->lo->depth > dl ) dl = b->lo->depth;
	++ dl;
	b->depth = dl;

	dh = e ? e->depth : 0;
	if ( f->hi && f->hi->depth > dh ) dh = f->hi->depth;
	++ dh;
	f->depth = dh;

	if ( dl < dh ) dl = dh;
	++ dl;

	//-- If depth is the same as before,  balancing is done.
	if ( dl == n->depth ) {
	    break;
	}

	//-- Put new depth in link.
	d->depth = dl;

	//-- Continue balancing from parent.
	n = p;
	continue;
    }

#if 0
    //-- Update root depth.  Do we really need this?
    if ( n == & ( arg_tree.link ) ) {
	n->depth = ( ( n->hi ) ? ( n->hi->depth ) : 0 ) + 1;
    }
#endif

#endif /* AVL_DONT_BALANCE */

    return 0;
}