//-----------------------------------------------------------------------------
// 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_empty
//
// purpose	Delete all nodes from the specified binary tree in a faster
//		way than would be done if each node were deleted individually.
//
//		Since the time to delete one node is almost O(log N) then the
//		time to delete all nodes one at a time is more than O(N) (but
//		not quite O(N log N) since N is diminishing), this function
//		is preferred as a faster way to delete all nodes in bulk since
//		its execution time is proportional to O(N).
//
// arguments	1 (AVL *) pointer to binary tree
//		2 (void (*fun)(void *)) optional pointer to function to call
//
// returns	(long) number of nodes deleted
//		(long) < 0 : error
//
// callback	The function specified in argument 2 is called with:
//   arguments	1 (void *) pointer to node
//   returns	(void) ignored
//
// note		Although the function pointer in argument 2 is optional, it
//		is essential to specify a function if the nodes need to be
//		returned to free memory.  The avl_empty function will not free
//		the nodes otherwise.  Just specify free() as the function to
//		call to simply free all the nodes as they are deleted, if no
//		other special handling is needed for each deleted node.  Or
//		specify your own function that uses the callback arguments.
//-----------------------------------------------------------------------------
long
avl_empty (
    AVL *		arg_tree
    ,
    void		(*(arg_fun))(void *)
    )
__PROTO_END__
{
    avl_link *		this_link	;
    avl_link *		next_link	;
    unsigned long	count		;

#if AVL_COUNT_ENABLE
#if AVL_PARANOID_LOGIC
    unsigned long	nodes		;
#endif /* AVL_PARANOID_LOGIC */
#endif /* AVL_COUNT_ENABLE */


#if AVL_CHECK_ARGS
    if ( ! arg_tree ) {
	return (long) AVL_ERR_BAD_ROOT;
    }
#endif

#if AVL_COUNT_ENABLE
#if AVL_PARANOID_LOGIC
    //----------------------------------------------------------
    // Save the count of nodes in the tree for comparison later.
    //----------------------------------------------------------
    nodes = avl_count_get_nodes( arg_tree );
#endif /* AVL_PARANOID_LOGIC */
#endif /* AVL_COUNT_ENABLE */

    //--------------------------------------------------------------------
    // Unlink everything from the root first and make it appear empty now.
    //--------------------------------------------------------------------
    next_link = arg_tree->link.hi;
    arg_tree->link.hi		= NULL;
    arg_tree->link.depth	= 0;
    arg_tree->select		= NULL;
    avl_count_set_nodes( arg_tree, 0 );

    //----------------------------------------------------------------------
    // This is the main loop to break up all the nodes.  Since nodes are
    // likely to be freed during the function call, this logic must not
    // reference the pointer to the node after the given function is called.
    // It will keep the pointer to the next node during that call.
    //----------------------------------------------------------------------
    count = 0UL;
    for (;;) {
	if ( ! next_link ) break;
	if ( next_link == (avl_link *) arg_tree ) break;
	this_link = next_link;
	if ( this_link->hi ) {
	    //-- Make the hi branch backtrack the same as this node.
	    this_link->hi->pa = this_link->pa;
	    if ( this_link->lo ) {
		//-- Make the lo branch backtrack the same as the hi one.
		next_link = this_link->lo;
		next_link->pa = this_link->hi;
	    } else {
		//-- No lo branch, so the hi branch is the next one.
		next_link = this_link->hi;
	    }
	} else {
	    if ( this_link->lo ) {
		//-- Make the lo branch backtrack the same as this node.
		next_link = this_link->lo;
		next_link->pa = this_link->pa;
	    } else {
		//-- Follow the backtrack.
		next_link = this_link->pa;
	    }
	}

#if AVL_CLEAN_NODE
	//-- Clean the node to detect misuse.
	this_link->pa    = NULL;
	this_link->lo    = NULL;
	this_link->hi    = NULL;
	this_link->depth = -1;
#endif

	//-------------------------------------------------------
	// Call the specified function which may free() the node.
	//-------------------------------------------------------
	if ( arg_fun ) {
	    ( * arg_fun )( avl_link_to_node( arg_tree, this_link ) );
	}
	++ count;
    }

#if AVL_COUNT_ENABLE
#if AVL_PARANOID_LOGIC
    //----------------------
    // Check the node count.
    //----------------------
    if ( nodes != count ) {
	avl_abort( arg_tree, NULL, "avl_empty: count mismatch (expect %lu != %lu counted)", nodes, count );
    }
#endif /* AVL_PARANOID_LOGIC */
#endif /* AVL_COUNT_ENABLE */

    return count;
}