//-----------------------------------------------------------------------------
// 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_put
//
// purpose	Put a node into the given binary tree at the location
//		indicated by the key link within the node.
//
// arguments	1 (AVL *) pointer to binary tree
//		2 (void *) pointer to node
//		3 (void * *) where to store pointer to replaced node
//		4 (int) option: allow duplicate insert
//
// note		If argument 3 is non-NULL, then replacement is allowed.
//		If argument 3 is NULL, then replacement is not allowed.
//
// returns	(int) -1: node not replaced or inserted
//		(int)  0: node replaces an existing node
//		(int)  1: node inserted as new
//		(int)  2: node inserted as duplicate
//
// note		If the allow duplicate insert option is true, then the node
//		is inserted regardless of whether one already exists with
//		that key or not.  The order duplicate nodes are retrieved,
//		and which node will match a find, is not defined.
//-----------------------------------------------------------------------------
// macro	avl_insert
//
// purpose	Call avl_put to do an insert only, without duplicate.
//-----------------------------------------------------------------------------
// macro	avl_insert_dup
//
// purpose	Call avl_put to do an insert with duplication allowed.
//-----------------------------------------------------------------------------
// macro	avl_replace
//
// purpose	Call avl_put to do an insert or replacement.
//-----------------------------------------------------------------------------
int
avl_put (
    AVL *	arg_tree
    ,
    void *	arg_node
    ,
    void * *	arg_rep_node
    ,
    int		arg_dup_ok
    )
__PROTO_END__
{
    avl_link *		new_p		;
    avl_link *		link_p		;

    int			match		;
    int			action		;


#if AVL_CHECK_ARGS
    //-- Make sure we were given a binary tree.
    if ( ! arg_tree ) return -1;

    //-- Make sure we were given a node.
    if ( ! arg_node ) return -1;
#endif

    //-- Point to the key link in the node.
    new_p = avl_node_to_link( arg_tree, arg_node );

    //----------------------------------------------------------------------
    // Search for where to put this new node.
    //
    // If the tree is empty, it simply becomes the apex.
    //
    // If it exactly matches an existing node and replacement is allowed,
    // then that node can be replaced where it is with no tree shape change.
    //
    // Otherwise, a hole must must be found, a nil link, thus adding the new
    // node as a leaf.  Then the tree is balanced to integrate it, which may
    // move the new node to a non-leaf position.
    //----------------------------------------------------------------------
    action = 1;
    if ( ! arg_tree->link.hi ) {
	//-- Add first node to tree.
	link_p = & ( arg_tree->link );
	link_p->hi = new_p;
    } else {
	link_p = arg_tree->link.hi;
	for (;;) {
	    match = avl_compare_keys( new_p, link_p, arg_tree );
	    if ( match == 0 ) {
		//-- Match found, check if duplicate or replace.
		if ( arg_dup_ok ) {
		    action = 2;
		    //-- Always go hi to add a duplicate.
		    if ( ! link_p->hi ) {
			link_p->hi = new_p;
			break;
		    }
		    //-- No hi opening here, continue that way.
		    link_p = link_p->hi;
		} else {
		    //-- No duplicating, must replace or return.
		    if ( arg_rep_node ) goto do_replace;
		    return -1;
		}
	    } else if ( match < 0 ) {
		//-- Check only the lo branch for an opening.
		if ( ! link_p->lo ) {
		    //-- Link the open lo branch to the new node.
		    link_p->lo = new_p;
		    break;
		}
		link_p = link_p->lo;
	    } else {
		//-- Check only the hi branch for an opening.
		if ( ! link_p->hi ) {
		    //-- Link the open hi branch to the new node.
		    link_p->hi = new_p;
		    break;
		}
		link_p = link_p->hi;
	    }
	}
    }

    //-- Finish linking new node back to insert point.
    new_p->pa    = link_p;

    //-- Initialize the new node as a leaf.
    new_p->lo    = NULL;
    new_p->hi    = NULL;
    new_p->depth = 1;

    //-- Balance from the parent of the new node.
    avl_balance( arg_tree, link_p );

    //-- Count the new node.
    avl_count_inc_nodes( arg_tree );

    //-- Remember the node as currently selected.
    arg_tree->select = new_p;

    // Return new or dup status.
    return action;

//-----------------------------------------------------------------------------

do_replace:
    //----------------------------------------------------------
    // Replace this old node with the new one right where it is.
    // Balancing will not be needed as the tree keeps its shape.
    //----------------------------------------------------------
    {	avl_link * pa_p;

	//-- Copy pointer to parent link.
	new_p->pa = pa_p = link_p->pa;

	//-- Copy the depth which stays the same.
	new_p->depth = link_p->depth;

	//-- Update parent to point back to new node.
	if ( pa_p->lo == link_p ) pa_p->lo = new_p;
#if AVL_PARANOID_LOGIC
	else if ( pa_p->hi != link_p ) {
	    return avl_abort( arg_tree, link_p, "avl_put: orphan node being replaced\n" );
	}
#endif
	else pa_p->hi = new_p;
    }

    //-- Copy child links and make them point back if they exist.
    {	avl_link * ch_p;
	if ( ( ch_p = new_p->lo = link_p->lo ) ) ch_p->pa = new_p;
	if ( ( ch_p = new_p->hi = link_p->hi ) ) ch_p->pa = new_p;
    }

#if AVL_CLEAN_NODE
    //-- Clean up the old node to detect misuse.
    link_p->lo		= NULL;
    link_p->hi		= NULL;
    link_p->pa		= NULL;
    link_p->depth	= 0;
#endif /* AVL_CLEAN_NODE */

    //-- Store the old node back for caller.
    * arg_rep_node = avl_link_to_node( arg_tree, link_p );

    //-- Remember the node as currently selected.
    arg_tree->select = new_p;

    //-- Return indicating replace.
    return 1;
}