package planiart.locations;

import java.util.ArrayList;
import java.util.Stack;

import edu.uci.ics.jung.algorithms.shortestpath.BFSDistanceLabeler;
import edu.uci.ics.jung.graph.Graph;

public class Path {

	private final ArrayList<MyRegion> path;

	public Path() {
		path = new ArrayList<MyRegion>();
	}

	public void addNode(MyRegion node) {
		path.add(node);
	}

	public ArrayList<MyRegion> getPath() {
		return path;
	}

	public static ArrayList<Path> computePath(Graph<MyRegion, Integer> graph,
			MyRegion source, MyRegion target) {
		if (source.equals(target)) {
			ArrayList<Path> allPath = new ArrayList<Path>();
			allPath.add(new Path());
			return allPath;
		}

		BFSDistanceLabeler<MyRegion, Integer> labeler = new BFSDistanceLabeler<MyRegion, Integer>();
		labeler.labelDistances(graph, source);

		ArrayList<Path> paths = computePathWithLabel(graph, labeler, source,
				target, new Stack<MyRegion>());
		return paths;
	}

	private static ArrayList<Path> computePathWithLabel(
			Graph<MyRegion, Integer> graph,
			BFSDistanceLabeler<MyRegion, Integer> labeler, MyRegion source,
			MyRegion target, Stack<MyRegion> stack) {
		ArrayList<Path> plans = new ArrayList<Path>();

		stack.push(target);

		if (source == target) {
			Path plan = new Path();
			MyRegion prev = stack.pop();
			plan.addNode(prev);
			while (!stack.isEmpty()) {
				prev = stack.pop();
				plan.addNode(prev);
			}

			plans.add(plan);
		} else {
			MyRegion currentPos = target;
			int currentDist = labeler.getDistance(graph, target);

			if (graph.getNeighborCount(currentPos) < 2) {
				MyRegion previous = graph.getNeighbors(currentPos).iterator()
						.next();
				plans.addAll(computePathWithLabel(graph, labeler, source,
						previous, stack));
			} else {
				for (MyRegion neigh : graph.getNeighbors(currentPos)) {
					int dist = labeler.getDistance(graph, neigh);
					if (dist < currentDist) {
						plans.addAll(computePathWithLabel(graph, labeler,
								source, neigh, (Stack<MyRegion>) stack.clone()));
					}
				}
			}
		}

		return plans;
	}
}