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

public class ParByteTSP implements TSPInf {

    protected Graph graph;
    protected Point[] points;
    protected Path bestPath; // beware of threads
    protected BestByteStore best;

    protected int number = 0;

    public ParByteTSP(Point[] p, int th) {
        this.points = p;
        graph = new PlaneGraph(p);
        number = th;
    }


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

    public Path getBest(long max) {
        bestPath = PathByteArray.standardPath(graph); // standard path
        if ( bestPath.length() <= 2 ) {
            return bestPath;
        }
        best = new BestByteStore( bestPath, 0, number );
        Path path = PathByteArray.emptyPath(graph); // empty path
        Deque stack = new Deque(10000);
        try {
            stack.push( path );
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        Thread[] t = new Thread[number];
        for ( int i = 0; i < number; i++ ) {
            t[i] = new RunByteTSP(stack,best,max);
            t[i].start();
        }
        try {
            for ( int i = 0; i < number; i++ ) {
                t[i].join();
            }
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        return best.getPath();
    }

}

class BestByteStore {

    private Path path;
    private int idlers;
    public final int threads;

    public BestByteStore(Path b, int i, int t) {
        path = b;
        idlers = i;
        threads = t;
    }

    public Path getPath() {
        return path;
    }

    public void setPath(Path p) {
        path = p;
    }

    public synchronized void incIdle() {
        idlers++;
    }

    public synchronized void decIdle() {
        idlers--;
    }

    public synchronized boolean allIdle() {
        return (idlers == threads);
    }
}


class RunByteTSP extends Thread {

    private BestByteStore best;
    private Deque stack;
    private Path bestPath;
    private long maxiter;
    private long iter;

    public RunByteTSP(Deque s, BestByteStore b, long max) {
        stack = s;
        best = b;
        bestPath = b.getPath();
        maxiter = max;
    }


    public void run() {
        iter = 0;
        boolean running = true;
        while (running) {
            Object o = null;
            try {
                best.incIdle();
                if ( stack.empty() && best.allIdle() ) {
                    for ( int i = 0; i < best.threads-1; i++) {
                        stack.push(null);
                    }
                    best.decIdle();
                    System.out.println("iterations = " + iter);
                    return;
                }
                o = stack.pop();
                best.decIdle();
            } catch (InterruptedException e) {
                e.printStackTrace();
                running = false;
            }
            if ( o == null ) {
                System.out.println("iterations = " + iter);
                return;
            }
            Path path = (Path)o;
            getBest( path );
        }
        System.out.println("iterations = " + iter);
    }


    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
               synchronized ( best ) {
                   if ( ps[i].cost() < best.getPath().cost() ) {
                        bestPath = ps[i];
                        best.setPath(bestPath);
                        System.out.println("par best = " + bestPath);
                   }
               }
           }
           return;
        }
        if ( iter >= maxiter ) {
            return;
        }
        for ( int i = 0; i < ps.length; i++ ) { // branch
            if ( ps[i].cost() < best.getPath().cost() ) { // cut
                // getBest( ps[i] ); // changes best and bestPath
                try {
                    stack.push( ps[i] ); // beware of deadlock
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        }
        return;
    }

}