G&A 4

package gna;

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

/**
 * A tour constructed using the minimal spanning tree heuristic.
 */
public class MinimalSpanningTreeTour extends Tour {

	private Point root = getWorld().getPoints().get(0);
	private List<MSTEdge> MST = new ArrayList<MSTEdge>();
	private List<Point> visitSequence = new ArrayList<Point>();

	public class MSTEdge {
		public final Point p1, p2;

		public MSTEdge(Point p1, Point p2) {
			this.p1 = p1;
			this.p2 = p2;
		}
	}

	public MinimalSpanningTreeTour(World world) {
		super(world);

		// compute route here

		PriorityQueue<MSTEdge> edges = new PriorityQueue<MSTEdge>(1,
				new edgeComparator());
		for (Point p : getWorld().getPoints()) {
			if (p != root) {
				MSTEdge edge = new MSTEdge(root, p);
				edges.offer(edge);
			}
		}
		MSTEdge current = edges.peek();
		MST.add(edges.poll());

		while (MST.size() <= getWorld().getNbPoints() - 2) {
			getOptimalEdges(edges, current);
			current = edges.peek();
			MST.add(edges.poll());
		}
	}

	private void getOptimalEdges(PriorityQueue<MSTEdge> edges, MSTEdge current) {
		ArrayList<MSTEdge> removeList = new ArrayList<>();
		ArrayList<MSTEdge> addList = new ArrayList<>();
		for (MSTEdge e : edges) {
			if (current.p2.distanceTo(e.p2) < e.p1.distanceTo(e.p2)) {
				Point p2 = e.p2;
				removeList.add(e);
				MSTEdge edge = new MSTEdge(current.p2, p2);
				addList.add(edge);
			}
		}
		for (MSTEdge e : removeList) {
			edges.remove(e);
		}
		for (MSTEdge e : addList) {
			edges.offer(e);
		}
	}

	@Override
	public double getTotalDistance() {
		double d = 0;
		findVisitSequence();
		for (int i = 0; i < visitSequence.size(); i++) {
			if (i != visitSequence.size() - 1) {
				d += visitSequence.get(i).distanceTo(visitSequence.get(i + 1));
			} else {
				d += visitSequence.get(i).distanceTo(visitSequence.get(0));
			}
		}
		return d;
	}

	/**
	 * Return the root of the MST used to construct the visit sequence.
	 *
	 * This method returns null if and only if
	 * <code>getWorld().getPoints()</code> is empty.
	 */
	public Point getMSTRoot() {
		if (getWorld().getPoints().isEmpty()) {
			return null;
		} else {
			return root;
		}
	}

	/**
	 * Return the edges on the MST used to construct the visit sequence.
	 *
	 * The result of this method is never null.
	 */
	public List<MSTEdge> getMST() {
		return MST;
	}

	@Override
	/**
	 * The visit sequence is a PRE-ORDER traversal of the MST
	 * starting at a root (e.g. the first point of the world).
	 *
	 * Traverse the children of each node in increasing order of distance.
	 *
	 * Return the empty list if world is empty.
	 */
	public List<Point> getVisitSequence() {
		return visitSequence;
	}

	private void getChildren(Point current) {
		int position = visitSequence.indexOf(current) + 1;
		for (MSTEdge e : MST) {
			if (e.p1 == current) {
				visitSequence.add(position++, e.p2);
			}
		}
	}

	private void findVisitSequence() {
		Point current = root;
		int counter = 0;
		visitSequence.add(counter++, current);
		while (visitSequence.size() <= MST.size()) {
			getChildren(current);
			current = visitSequence.get(counter++);
		}
	}
}