//-----------------------------------------------------------------------------
// 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_diff_key_count
//
// purpose	Scan two binary trees for node differences, counting the
//		number of nodes different in each based on just the key.
//
// arguments	1 (AVL *) pointer to binary tree one
//		2 (AVL *) pointer to binary tree two
//		3 (int *) store count of nodes in tree one not in tree two here
//		4 (int *) store count of nodes in tree two not in tree one here
//
// returns	(int) == 0 : trees have the same keys
//		(int)  > 0 : number of nodes not match in either tree
//		(int)  < 0 : error
//
// note		In order for tree-to-tree comparison to be made, both trees
//		MUST be using exactly the same comparison function.
//
// note		This function does not depend on the shape of the tree or any
//		aspect of the order the nodes were inserted.
//-----------------------------------------------------------------------------
int
avl_diff_key_count (
    AVL *	arg_tree_one
    ,
    AVL *	arg_tree_two
    ,
    int *	arg_count_one
    ,
    int *	arg_count_two
    )
__PROTO_END__
{
    int ( *		cmp_f		)( avl_link *, avl_link *, struct avl_root * );
    avl_link *		node_one	;
    avl_link *		node_two	;
    avl_link *		select_one	;
    avl_link *		select_two	;
    int			count_one	;
    int			count_two	;


#if AVL_CHECK_ARGS
    //--------------------------------------
    // Make sure we were given binary trees.
    //--------------------------------------
    if ( ! arg_tree_one ) return AVL_ERR_BAD_ROOT;
    if ( ! arg_tree_two ) return AVL_ERR_BAD_ROOT;
#endif

    //------------------------------------------------------
    // Make sure the binary trees are compared the same way.
    //------------------------------------------------------
    if ( ! ( cmp_f = arg_tree_one->compare_f ) ) return -1;
    if ( arg_tree_two->compare_f != cmp_f ) return -1;

    //--------------------------------------------
    // For both trees, save the currently selected
    // node and start them at the beginning.
    //--------------------------------------------
    select_one = arg_tree_one->select;
    select_two = arg_tree_two->select;
    node_one = avl_first( arg_tree_one );
    node_two = avl_first( arg_tree_two );
    count_one = 0;
    count_two = 0;

    //-------------------------------------------------------
    // Scan both trees in parallel counting mismatched nodes.
    //-------------------------------------------------------
    for (;;) {
	if ( node_one ) {
	    if ( node_two ) {
		int delta;
		delta = ( * cmp_f )( avl_node_to_link( arg_tree_one, node_one ),
				     avl_node_to_link( arg_tree_two, node_two ),
				     NULL );
		if ( delta <= 0 ) {
		    node_one = avl_forward( arg_tree_one, node_one );
		    if ( delta != 0 ) ++ count_one;
		}
		if ( delta >= 0 ) {
		    node_two = avl_forward( arg_tree_two, node_two );
		    if ( delta != 0 ) ++ count_two;
		}
	    } else {
		node_one = avl_forward( arg_tree_one, node_one );
		++ node_one;
	    }
	} else if ( node_two ) {
	    node_two = avl_forward( arg_tree_two, node_two );
	    ++ count_two;
	} else break;
    }

    //----------------------------
    // Restore the selected nodes.
    //----------------------------
    arg_tree_one->select = select_one;
    arg_tree_two->select = select_two;

    //----------------------------------------------------
    // Store individual counts and return the total count.
    //----------------------------------------------------
    if ( arg_count_one ) * arg_count_one = count_one;
    if ( arg_count_two ) * arg_count_two = count_two;
    return count_one + count_two;
}