import java.util.ArrayList;

/**
 * A sequential algorithm for an euclidean 2d TSP Problem
 */

public class SeqByteStackTSP implements TSPInf {

    protected Graph graph;
    protected Point[] points;
    protected double best;   // beware of threads
    protected Path bestPath; // beware of threads
    protected long iter;
    protected long maxiter;
    protected ArrayList stack;


    public SeqByteStackTSP(Point[] p) {
        this.points = p;
        graph = new PlaneGraph(p);
        stack = new ArrayList( graph.size()*graph.size() );
    }


    public Path actualBest() {
        return bestPath;
    }

    public void setBest(Path b) {
        if ( b == null ) {
           return;
        }
        if ( bestPath == null ) {
           bestPath = b;
           best = b.cost();
           return;
        }
        if ( b.cost() < best ) {
           bestPath = b;
           best = b.cost();
        }
    }


    public Path getBest() {
        return getBest(Long.MAX_VALUE);
    }

    public Path getBest(long max) {
        iter = 0; 
        maxiter = max;
        bestPath = PathByteArray.standardPath(graph); // standard path
        best = bestPath.cost();
        if ( bestPath.length() <= 2 ) {
            return bestPath;
        }
        Path path = PathByteArray.emptyPath(graph); // empty path
        stack.add( path );
        while ( stack.size() > 0 ) {
            Object o = stack.remove( stack.size()-1 );
           getBest( (Path)o );
        }
        System.out.println("iterations = " + iter);
        return bestPath;
    }

    public void getBest(Path path) {
        Path[] ps = path.nextPaths(); 
        iter += ps.length;
        if ( path.length()+1 == path.maxsize() ) {
           for ( int i = 0; i < ps.length; i++ ) { // branch
               if ( ps[i].cost() < best ) {
                  best = ps[i].cost();
                  bestPath = ps[i];
                  System.out.println("seq best = " + bestPath);
               }
           }
           return;
        }
        if ( iter >= maxiter ) {
            return;
        }
        for ( int i = 0; i < ps.length; i++ ) { // branch
            if ( ps[i].cost() < best ) { // cut
                //getBest( ps[i] ); // changes best and bestPath
                stack.add( ps[i] );
            }
        }
        return;
    }


}