package org.kareha.hareka.field;

import java.util.ArrayList;
import java.util.EnumSet;
import java.util.List;

import org.kareha.hareka.annotation.NotThreadSafe;

// See http://www.policyalmanac.org/games/aStarTutorial.htm
@NotThreadSafe
public final class Pathfinder {

	private final Field field;

	// HashSet may be better instead of ArrayList
	private final List<Node> openList = new ArrayList<>();
	private final List<Node> closedList = new ArrayList<>();

	public Pathfinder(final Field field) {
		this.field = field;
	}

	private void open(final Node a) {
		if (closedList.contains(a)) {
			return;
		}
		final int i = openList.indexOf(a);
		if (i == -1) {
			openList.add(a);
		} else {
			final Node b = openList.get(i);
			if (a.cost < b.cost) {
				b.parent = a.parent;
				b.cost = a.cost;
			}
		}
	}

	@SuppressWarnings("null")
	public List<Vector> findPath(final Vector start, final Vector end, final int limit) {
		openList.add(new Node(null, start, end));

		for (int i = 0; !openList.isEmpty() && i < limit; i++) {
			int cost = Integer.MAX_VALUE;
			Node a = null;
			for (final Node b : openList) {
				if (b.cost + b.heuristic <= cost) {
					cost = b.cost + b.heuristic;
					a = b;
				}
			}

			assert (a != null);

			if (a.position.equals(end)) {
				final List<Vector> path = new ArrayList<>();
				while (a != null) {
					path.add(0, a.position);
					a = a.parent;
				}
				return path;
			}

			openList.remove(a);
			closedList.add(a);

			for (final Direction direction : EnumSet.allOf(Direction.class)) {
				if (field.getTile(a.position.neighbor(direction)).type().isWalkable()) {
					open(new Node(a, a.position.neighbor(direction), end));
				}
			}
		}

		return null;
	}

	private static final class Node {

		Node parent;
		final Vector position;
		int cost;
		final int heuristic;

		Node(final Node parent, final Vector position, final Vector target) {
			this.parent = parent;
			this.position = position;
			if (parent != null) {
				cost = parent.cost + 1;
			}
			heuristic = position.distance(target);
		}

		@Override
		public boolean equals(final Object obj) {
			assert obj instanceof Node;
			final Node n = (Node) obj;
			return n.position.equals(position);
		}

		@Override
		public int hashCode() {
			return position.hashCode();
		}

	}

}
