// Copyright (C) 2000, International Business Machines
// Corporation and others.  All Rights Reserved.
#include <cstdio>
#include "BCP_tm.hpp"
#include "BCP_tm_functions.hpp"

static int BCP_tm_trim_tree(BCP_tm_prob& p, BCP_tm_node* node,
			    const bool between_phases);

//#############################################################################
// For now we'll trim the tree only between phases when nothing is processed.
// Reason: It's kinda ugly to cut off a subtree when several of its nodes
// might be processed. Nevertheless, this should be done sooner or later.
//
// *THINK*
//#############################################################################

void BCP_tm_trim_tree_wrapper(BCP_tm_prob& p, const bool between_phases)
{
    BCP_tree& tree = p.search_tree;
    BCP_tm_node* root = tree.root();
    tree.enumerate_leaves(root, p.ub() - p.granularity());
    const int trimmed =
	BCP_tm_trim_tree(p, root, true /* called between phases */);
    if (p.param(BCP_tm_par::TmVerb_TrimmedNum)) {
	printf("\
TM: before starting the new phase, \n\
    %i nodes were trimmed from the tree.\n", trimmed);
    }

    BCP_vec<BCP_tm_node*>::iterator nodep;
    BCP_vec<BCP_tm_node*>::const_iterator lastnodep;
    BCP_tm_node * node;

    // clean up the next phase nodes
    nodep = p.next_phase_nodes.begin();
    lastnodep = p.next_phase_nodes.end();
    while (nodep != lastnodep) {
	if ((*nodep)->index() == -1) {
	    *nodep = *--lastnodep;
	    p.next_phase_nodes.pop_back();
	} else {
	    ++nodep;
	}
    }

    // FIXME: Why is this block necessary?
    // clean up the list of candidates
    if (! p.candidate_list.empty()) {
	BCP_vec<BCP_tm_node*> cands;
	while (! p.candidate_list.empty()) {
	    CoinTreeNode* coinnode = p.candidate_list.top();
	    node = dynamic_cast<BCP_tm_node*>(coinnode);
	    if (node->index() != -1)
		cands.push_back(node);
	    p.candidate_list.pop();
	}
	lastnodep = cands.end();
	for (nodep = cands.begin(); nodep != lastnodep; ++nodep)
	    p.candidate_list.push(*nodep);
    }

    // clean up the tree
    nodep = p.search_tree.begin();
    lastnodep = p.search_tree.end();
    while (nodep != lastnodep) {
	node = *nodep;
	if (node->index() == -1) {
	    // The search tree node is in a subtree that is trimmed
#ifdef BCP_DEBUG
	    if (node->lp != -1 || node->cg != -1 || node->vg != -1)
		throw BCP_fatal_error("\
TM: At least on of lp/cg/vg of a trimmed node is non-0.\n");
#endif
	    if (node->cp != -1 && node->child_num() == 0) {
		BCP_vec< std::pair<int, int> >::iterator proc =
		    BCP_tm_identify_process(p.leaves_per_cp, node->cp);
#ifdef BCP_DEBUG
		if (proc == p.leaves_per_cp.end())
		    throw BCP_fatal_error("\
TM: non-existing CP is assigned to a leaf.\n");
#endif
		--proc->second;
	    }
	    if (node->vp != -1 && node->child_num() == 0) {
		BCP_vec< std::pair<int, int> >::iterator proc =
		    BCP_tm_identify_process(p.leaves_per_vp, node->vp);
#ifdef BCP_DEBUG
		if (proc == p.leaves_per_vp.end())
		    throw BCP_fatal_error("\
TM: non-existing VP is assigned to a leaf.\n");
#endif
		--proc->second;
	    }
	    delete node;
	    *nodep = 0;
	}
	++nodep;
    }

#if ! defined(BCP_ONLY_LP_PROCESS_HANDLING_WORKS)
    // scan through the CP and VP list to mark the free ones
    BCP_vec< std::pair<int, int> >::iterator proc;
    BCP_vec< std::pair<int, int> >::iterator lastproc;

    lastproc = p.leaves_per_cp.end();
    for (proc = p.leaves_per_cp.begin(); proc != lastproc; ++proc)
	if (proc->second == 0)
	    p.slaves.cp->set_proc_free(proc->first);

    lastproc = p.leaves_per_vp.end();
    for (proc = p.leaves_per_vp.begin(); proc != lastproc; ++proc)
	if (proc->second == 0)
	    p.slaves.vp->set_proc_free(proc->first);
#endif
}

//#############################################################################
// We will trim very conservatively

int BCP_tm_trim_tree(BCP_tm_prob& p, BCP_tm_node* node,
		     const bool between_phases)
{
    bool trim = true;
    int trimmed = 0;

    if (node->_processed_leaf_num > 0) {
	// if there is a node currently processed in the subtree then don't
	// trim here
	trim = false;
    } else if (node->child_num() == 0) {
	// if this is a leaf then there is no point in trimming
	trim = false;
    } else if (node->_leaf_num - node->_pruned_leaf_num <= 2) {
	// if there are no more than 2 nodes further down that have to be taken
	// care of then don't trim
	trim = false;
    } else if (node->getTrueLB() < p.ub() - p.granularity()) {
	// don't trim if the gap at this node is not below the granularity
	trim = false;
    }

    if (trim) {
	trimmed = node->mark_descendants_for_deletion();
	if (node->cp != -1) {
	    BCP_vec< std::pair<int, int> >::iterator proc =
		BCP_tm_identify_process(p.leaves_per_cp, node->cp);
#ifdef BCP_DEBUG
	    if (proc == p.leaves_per_cp.end())
		throw BCP_fatal_error("\
TM: An internal node is assigned to a non-existing CP.\n");
#endif
	    ++proc->second;
	}
	if (node->vp != -1) {
	    BCP_vec< std::pair<int, int> >::iterator proc =
		BCP_tm_identify_process(p.leaves_per_vp, node->vp);
#ifdef BCP_DEBUG
	    if (proc == p.leaves_per_vp.end())
		throw BCP_fatal_error("\
TM: An internal node is assigned to a non-existing VP.\n");
#endif
	    ++proc->second;
	}
    } else {
	// try to trim at the children
	BCP_vec<BCP_tm_node*>::iterator child;
	BCP_vec<BCP_tm_node*>::const_iterator lastchild =
	    node->_children.end();
	for (child = node->_children.begin(); child != lastchild; ++child)
	    trimmed += BCP_tm_trim_tree(p, *child, between_phases);
    }

    return trimmed;
}

//#############################################################################
// This routine will delete a node (which must be a leaf)

void BCP_tm_remove_explored(BCP_tm_prob& p, BCP_tm_node* node)
{
    if (! p.param(BCP_tm_par::RemoveExploredBranches))
	return;

    if (node->child_num() == 0) {
	BCP_tm_node* parent = node->parent();
	p.search_tree.remove(node->index());
	delete node;

	if (parent) {
	    parent->remove_child(node);
	    BCP_tm_remove_explored(p, parent);
	}
    }
}

//#############################################################################
