package janet.applications.branchandbound;

import  janet.applications.branchandbound.Q;
import  janet.services.*;
import  janet.services.shared.*;
import  janet.services.tasks.*;
import java.rmi.*;
import java.util.*;

//import janet.applications.branchandbound.tsp.pete.*; // !! DEBUG ONLY

/** BranchAndBound.java - a Janet task for a generic branch & bound framework.
 * This class is the main part of the Janet Branch & Bound Framework.
 * Please see the programming tutorial for an explanation of its design.
 * @author Peter Cappello
 * @version 1.0
 */
public final class BranchAndBound extends Task 
{
    private Solution solution;

    /** Used to construct a BranchAndBound task that corresponds to the search
     * subtree represented by the Solution passed to it as its argument.
     * @param solution A partial solution to the problem. It represents a search
     * subtree. Initially, this would be the "starting" solution.
     */    
    public BranchAndBound( Solution solution ) { this.solution = solution; }
    
    /** The method that searches the search tree. If the search subtree
     * represented by this task is sufficiently small, it explores it, returning
     * the best solution found, if it is better than the best known solution;
     * otherwise, it "branches": constructs subtasks that correspond to subtrees
     * of this search tree.
     * @param environment Contains the the problem input & the shared object. The latter
     * holds the <I>cost</I> of the best solution found so far.
     * @return If the task is atomic (i.e., does not construct subtasks), it
     * returns either null, if it finds no solution better than what
     * it already knows about, or a Solution, if it does find a new
     * minimum cost Solution. When the task does construct subtasks,
     * it returns a MinSolution task that will receive the results of
     * the spawned subtasks.
     */    
    public Object execute ( Environment environment )
    {
        /* Prune? The upper bound may have gone down after this task was 
         * constructed, but before its execute method is invoked.
         */
        int lowerBound = solution.getLowerBound( environment.getInput() );
        if ( lowerBound >= sharedUpperBound( environment ) ) 
        {
            return null; // To successor: "This subtree was pruned."
        }
        if ( solution.isAtomic( this ) )
        {
            return exploreSubTree( environment );
        }
        else
        {
            return branch( environment );
        }
    }
    
    // return value of shared UpperBound
    private int sharedUpperBound( Environment environment )
    {
        return ( (Integer) environment.getShared().get() ).intValue();
    }

    /* getChildren returns only children that should be explored:
     *     child's computed lower bound < upperBound.
     */
    private MinSolution branch( Environment environment )
    {        
        Object problem = environment.getInput();
        int upperBound = sharedUpperBound( environment );
        Q q = solution.getChildren( environment );
        if ( q.isEmpty() ) // Have all of the children been pruned?
        {
            return null; // To successor: "This search subtree was pruned."
        }           

        // construct, spawn children tasks
        while ( ! q.isEmpty() ) 
        {
            Solution child = q.remove ();
            Task task = new BranchAndBound( child );
            compute( task );
        }
        return new MinSolution();
    }

    private Solution exploreSubTree( Environment environment )
    {
        // Since this task does not construct subTasks, prefetch a Task.
        environment.fetchTask();

        Solution currentBest = null;
        Object input = environment.getInput();

        assert ! solution.isComplete(); 
        Stack stack = new Stack();
        for ( stack.push( solution ); ! stack.isEmpty(); )
        {
            solution = stack.pop();
            int lowerBound = solution.getLowerBound( input );
            
            // Prune?
            if ( lowerBound >= sharedUpperBound( environment ) ) 
            {        
                continue; // prune
            }
            Q q = solution.getChildren( environment );
            while ( ! q.isEmpty() ) 
            {
                Solution child = q.remove ();                                
                if ( child.isComplete() ) 
                {   
                    int cost = child.getLowerBound( input );
                    if ( cost < sharedUpperBound( environment ) )
                    { 
                        // new upper bound
                        environment.setShared( new IntUpperBound( cost ) );
                        currentBest = child;
                    }
                }
                else 
                {
                    stack.push( child );
                }
            }
        }                          
        return currentBest; // report result to successor
    }
    
    /* I am not using java.util.Stack because it extends Vector, 
     * whose operations are synchronized, an unnecessary overhead in this case.
     * LinkedList operations are not synchronized. However, every push requires
     * memory allocation, unfortunately.
     *
     * It might be better to define a data structure, based on a LinkedList,
     * where pop returns the top value and "empties" the top node and moves the
     * top pointer to the previous node, but does not free the unused node. Push
     * behaves analogously, actually getting a new node only when there are no
     * "empty" nodes left. Would this perform better overall?
     */
    private class Stack
    {
        LinkedList stack = new LinkedList();
        
        boolean isEmpty() { return ( stack.size() == 0 ) ? true : false; }
        
        Solution pop()
        {
            assert ! isEmpty();
            return (Solution) stack.removeFirst();
        }
        
        void push ( Solution solution ) { stack.addFirst( solution ); }
    }
}