package jrummikub.ai;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.List;

import jrummikub.model.GameSettings;
import jrummikub.model.Stone;
import jrummikub.model.StoneColor;
import jrummikub.model.StoneSet;
import jrummikub.util.Pair;

/**
 * Logic behind the AI turns. Ability to correctly find turns is completly
 * tested by the HandTest testcases.
 */
public class TurnLogic {
	private GameSettings settings;
	private int stoneCount;
	private List<Stone> inputStones;
	private StoneColor maxColor;
	private StoneColor minColor;
	private ArrayList<StoneColor> stoneColors;
	private volatile State bestState;

	private ArrayList<State> stack = new ArrayList<State>();
	private State top;

	private volatile boolean abort = false;
	private volatile boolean autoAbort = false;

	private int neededPoints = 0;
	private double neededScore = 0;

	/**
	 * A Contradiction is thrown once a state is reached that isn't legal
	 */
	@SuppressWarnings("serial")
	private static class Contradiction extends Throwable {

	}

	/**
	 * The state the search is in, containing {@link StoneState}s
	 */
	private class State {
		/**
		 * A list of all stones
		 */
		ArrayList<StoneState> stones = new ArrayList<StoneState>();
		/**
		 * The stones that were changed since the previous state
		 */
		HashSet<Integer> changedStones = new HashSet<Integer>();
		/**
		 * The position of the jokers in the other lists
		 */
		ArrayList<Integer> jokerIDs = new ArrayList<Integer>();

		/**
		 * Create a new
		 */
		public State() {
		}

		/**
		 * Create a copy of a state
		 * 
		 * @param state
		 *            the state to copy
		 */
		public State(State state) {
			for (StoneState stone : state.stones) {
				stones.add(new StoneState(stone));
			}
			jokerIDs = state.jokerIDs;
		}

		/**
		 * Adds stones to be considered in the state
		 * 
		 * @param stone
		 *            the stone to add
		 */
		public void add(StoneState stone) {
			stones.add(stone);
			changedStones.add(stones.size() - 1);
			if (stone.joker) {
				jokerIDs.add(stone.id);
			}
		}

		/**
		 * Update the stones to consider the changes of the changed stones
		 * 
		 * @throws Contradiction
		 *             Is thrown if the changes contradict each other
		 */
		public void updateStones() throws Contradiction {
			checkJokerCount();
			for (int i : changedStones) {
				stones.get(i).checkState();
			}
			checkScoreAndPoints();
			while (!changedStones.isEmpty()) {
				while (!changedStones.isEmpty()) {
					updateStonesStep();
					checkScoreAndPoints();
				}
				checkJokerCount();
				checkScoreAndPoints();

			}
		}

		/**
		 * One step in the update process
		 * 
		 * @throws Contradiction
		 *             Is thrown if changes contradict each other
		 */
		private void updateStonesStep() throws Contradiction {
			HashSet<Integer> newChangedStones = new HashSet<Integer>();
			for (int i = 0; i < stoneCount; i++) {
				StoneState stone = stones.get(i);
				if (stone.isInterested(changedStones)) {
					if (stone.update(changedStones)) {
						newChangedStones.add(i);
					}
				}
			}
			changedStones = newChangedStones;
		}

		/**
		 * Returns whether the stones have a definite value and the state is
		 * thereby solved
		 * 
		 * @return whether the state is solved
		 */
		public boolean isSolved() {
			for (StoneState stone : stones) {
				if (!stone.isSolved()) {
					return false;
				}
			}
			return true;
		}

		/**
		 * Checks that not more jokers than available are needed
		 * 
		 * @throws Contradiction
		 *             Is thrown if too many jokers are needed
		 */
		private void checkJokerCount() throws Contradiction {
			int jokersLeft = jokerIDs.size();
			int jokersRight = jokerIDs.size();
			for (StoneState stone : stones) {
				if (stone.needsJoker(true)) {
					jokersLeft--;
					if (jokersLeft < 0) {
						throw new Contradiction();
					}
				}
				if (stone.needsJoker(false)) {
					jokersRight--;
					if (jokersRight < 0) {
						throw new Contradiction();
					}
				}
			}
		}

		/**
		 * Checks that enough points and a high enough score can be reached
		 * 
		 * @throws Contradiction
		 *             Is thrown if points are too few or score is too low
		 */
		public void checkScoreAndPoints() throws Contradiction {
			if (getPoints() < neededPoints) {
				throw new Contradiction();
			}
			if (getScore() <= neededScore) {
				throw new Contradiction();
			}
		}

		/**
		 * Returns the points
		 * 
		 * @return the amount of points
		 */
		public int getPoints() {
			int sum = 0;
			for (StoneState stone : stones) {
				if (stone.onTable != Boolean.FALSE) {
					sum += stone.getPoints();
				}
			}
			return sum;
		}

		/**
		 * Returns the score
		 * 
		 * @return the total score reached
		 */
		public double getScore() {
			double sum = 0;
			for (StoneState stone : stones) {
				if (stone.onTable != Boolean.FALSE) {
					sum += stone.getScore();
				}

			}
			return sum;
		}
	}

	/**
	 * Contains the remaining possible values, colors, positions, etc. a stone
	 * can take and its possible neighbors in a group or run
	 */
	private class StoneState {
		int id;
		boolean joker;
		Integer value;
		StoneColor color;
		Boolean onTable;
		boolean fromTable;
		HashSet<Integer> leftRun;
		HashSet<Integer> rightRun;
		HashSet<Integer> leftGroup;
		HashSet<Integer> rightGroup;

		/**
		 * Creates a new
		 * 
		 * @param id
		 *            the stone's identifier
		 * @param stone
		 *            the stone
		 * @param table
		 *            whether is on the table
		 */
		public StoneState(int id, Stone stone, boolean table) {
			this.id = id;
			joker = stone.isJoker();
			if (!joker) {
				this.value = stone.getValue();
				this.color = stone.getColor();
			}
			onTable = table ? true : null;
			fromTable = table;
			leftRun = makeFullSet();
			rightRun = makeFullSet();
			leftGroup = makeFullSet();
			rightGroup = makeFullSet();
		}

		/**
		 * Creates a copy
		 * 
		 * @param stone
		 *            the state to copy
		 */
		public StoneState(StoneState stone) {
			this.id = stone.id;
			this.joker = stone.joker;
			this.value = stone.value;
			this.color = stone.color;
			this.onTable = stone.onTable;
			this.fromTable = stone.fromTable;
			this.leftRun = new HashSet<Integer>(stone.leftRun);
			this.rightRun = new HashSet<Integer>(stone.rightRun);
			this.leftGroup = new HashSet<Integer>(stone.leftGroup);
			this.rightGroup = new HashSet<Integer>(stone.rightGroup);
		}

		/**
		 * Returns a set containing all possible neighbors
		 * 
		 * @return the set
		 */
		private HashSet<Integer> makeFullSet() {
			HashSet<Integer> set = new HashSet<Integer>();
			for (int i = 0; i < stoneCount; i++) {
				if (i != id) {
					set.add(i);
				}
			}
			set.add(null);
			return set;
		}

		/**
		 * Returns whether the recent changes could affect the stone
		 * 
		 * @param changes
		 *            the changes
		 * @return whether the stone could be affected
		 */
		private boolean isInterested(HashSet<Integer> changes) {
			return !(Collections.disjoint(changes, leftRun)
					&& Collections.disjoint(changes, rightRun)
					&& Collections.disjoint(changes, leftGroup) && Collections
					.disjoint(changes, rightGroup));
		}

		/**
		 * Compare two objects, returning true if either is null
		 * 
		 * @param <T>
		 *            object's type
		 * @param a
		 *            first object
		 * @param b
		 *            second object
		 * @return whether a is less than b or either is null
		 */
		private <T extends Comparable<T>> boolean lessThan(T a, T b) {
			return a == null || b == null || a.compareTo(b) < 0;
		}

		/**
		 * Compare two objects, returning true if either is null
		 * 
		 * @param <T>
		 *            object;s type
		 * @param a
		 *            first object
		 * @param b
		 *            second object
		 * @return whether a is less than b or either is null
		 */
		private <T> boolean same(T a, T b) {
			return a == null || b == null || a.equals(b);
		}

		/**
		 * Checks whether a and b are consecutive integers or either is null
		 * 
		 * @param a
		 *            first integer
		 * @param b
		 *            next integer
		 * @return whether a + 1 is b or either is null
		 */
		private boolean step(Integer a, Integer b) {
			return a == null || b == null || (int) a == b - 1;
		}

		/**
		 * Checks whether a and b are consecutive integers modulo highest value
		 * or either i snull
		 * 
		 * @param a
		 *            first integer
		 * @param b
		 *            second integer
		 * @return whether a + 1 is b (modulo highest value) or either is null
		 */
		private boolean cycleStep(Integer a, Integer b) {
			return a == null || b == null || (int) a == b - 1
					|| a == settings.getHighestValue() && b == 1;
		}

		/**
		 * Checks whether this stone could be left to other in a group
		 * 
		 * @param other
		 *            possible right neighbor
		 * @return whether they can be neighbors
		 */
		private boolean groupNeighbor(StoneState other) {
			if (isNullSet(leftGroup) && isNullSet(other.rightGroup)) {
				return false;
			}
			if (other.color == minColor || color == maxColor) {
				return false;
			}
			return lessThan(color, other.color) && same(value, other.value);
		}

		/**
		 * Checks whether this stone could be left to other in a run
		 * 
		 * @param other
		 *            possible right neighbor
		 * @return whether they can be neighbors
		 */
		private boolean runNeighbor(StoneState other) {
			if (isNullSet(leftRun) && isNullSet(other.rightRun)) {
				return false;
			}
			if (!same(color, other.color)) {
				return false;
			}
			if (settings.isNoLimits()) {
				return cycleStep(value, other.value);
			} else {
				if (((Integer) 1).equals(other.value)
						|| ((Integer) settings.getHighestValue()).equals(value)) {
					return false;
				}
				return step(value, other.value);
			}
		}

		/**
		 * Updates this stone considering the changes of all changed stones
		 * 
		 * @param changes
		 *            stones that have changed
		 * @return whether we could be updated
		 * @throws Contradiction
		 *             Is thrown if the changes contradict each other
		 */
		private boolean update(HashSet<Integer> changes) throws Contradiction {
			boolean changed = false;

			changed |= updateRightRuns(changes);
			changed |= updateLeftRuns(changes);
			changed |= updateRightGroups(changes);
			changed |= updateLeftGroups(changes);
			changed |= checkState();

			breakSymmetries(changes);

			return changed;
		}

		/**
		 * Checks that two objects are equal to each other and not null
		 * 
		 * @param a
		 * @param b
		 * @return whether a equals b and both are not null
		 */
		private boolean nonNullEquals(Object a, Object b) {
			return a != null && b != null && a.equals(b);
		}

		/**
		 * Try to break symmetries between exchangeable stones to reduce the
		 * state space
		 * 
		 * @param changes
		 *            stones that changed
		 * @throws Contradiction
		 *             Is thrown when there exists another trivial solution by
		 *             symmetry
		 */
		private void breakSymmetries(HashSet<Integer> changes)
				throws Contradiction {
			Integer mySym = symmetryBreakerValue();
			if (mySym == null) {
				return;
			}
			for (int other : changes) {
				if (other == id) {
					continue;
				}
				StoneState otherStone = top.stones.get(other);
				if (!(joker && otherStone.joker || nonNullEquals(value,
						otherStone.value)
						&& nonNullEquals(color, otherStone.color))) {
					continue;
				}
				Integer otherSym = top.stones.get(other).symmetryBreakerValue();
				if (otherSym == null) {
					continue;
				}

				if ((mySym != -1 | otherSym != -1)
						& ((id > other) != (mySym < otherSym))) {
					throw new Contradiction();
				}
			}
		}

		/**
		 * Order stones by their neighbors to decide on a solution of a set of
		 * symmetric solutions
		 * 
		 * @return the order value or null if it can't be determined yer
		 */
		private Integer symmetryBreakerValue() {
			if (onTable != Boolean.TRUE) {
				return -1;
			}
			if (leftRun.size() > 1 || leftGroup.size() > 1
					|| rightRun.size() > 1 || rightGroup.size() > 1) {
				return null;
			}
			int mode;
			int neighbor;
			if (leftRun.contains(null)) {
				if (leftGroup.contains(null)) {
					if (rightRun.contains(null)) {
						if (rightGroup.contains(null)) {
							return -1;
						} else {
							mode = 0;
							neighbor = rightGroup.iterator().next();
						}
					} else {
						mode = 1;
						neighbor = rightRun.iterator().next();
					}

				} else {
					mode = 2;
					neighbor = leftGroup.iterator().next();
				}
			} else {
				mode = 3;
				neighbor = leftRun.iterator().next();
			}
			return neighbor + stoneCount * mode;
		}

		/**
		 * Updates this stone's right run neighbors considering the changes of
		 * all changed stones
		 * 
		 * @param changes
		 *            stones that have changed
		 * @return whether we could be updated
		 * @throws Contradiction
		 *             Is thrown if the changes contradict each other
		 */
		private boolean updateRightRuns(HashSet<Integer> changes)
				throws Contradiction {
			boolean changed = false;
			HashSet<Integer> relevantChanges = new HashSet<Integer>(leftRun);
			relevantChanges.retainAll(changes);
			for (int i : relevantChanges) {
				StoneState other = top.stones.get(i);
				if (!other.runNeighbor(this) || !other.rightRun.contains(id)) {
					leftRun.remove(i);
					changed = true;
				} else if (other.rightRun.size() == 1
						&& other.onTable == Boolean.TRUE) {
					changed |= leftRun.retainAll(Arrays.asList(i));
					changed |= onTable != Boolean.TRUE;
					onTable = true;
					break;
				}
			}
			return changed;
		}

		/**
		 * Updates this stone's left run neighbors considering the changes of
		 * all changed stones
		 * 
		 * @param changes
		 *            stones that have changed
		 * @return whether we could be updated
		 * @throws Contradiction
		 *             Is thrown if the changes contradict each other
		 */
		private boolean updateLeftRuns(HashSet<Integer> changes)
				throws Contradiction {
			boolean changed = false;
			HashSet<Integer> relevantChanges = new HashSet<Integer>(rightRun);
			relevantChanges.retainAll(changes);
			for (int i : relevantChanges) {
				StoneState other = top.stones.get(i);
				if (!this.runNeighbor(other) || !other.leftRun.contains(id)) {
					rightRun.remove(i);
					changed = true;
				} else if (other.leftRun.size() == 1
						&& other.onTable == Boolean.TRUE) {
					changed |= rightRun.retainAll(Arrays.asList(i));
					changed |= onTable != Boolean.TRUE;
					onTable = true;
					break;
				}
			}
			return changed;
		}

		/**
		 * Updates this stone's right group neighbors considering the changes of
		 * all changed stones
		 * 
		 * @param changes
		 *            stones that have changed
		 * @return whether we could be updated
		 * @throws Contradiction
		 *             Is thrown if the changes contradict each other
		 */
		private boolean updateRightGroups(HashSet<Integer> changes)
				throws Contradiction {
			boolean changed = false;
			HashSet<Integer> relevantChanges = new HashSet<Integer>(leftGroup);
			relevantChanges.retainAll(changes);
			for (int i : relevantChanges) {
				StoneState other = top.stones.get(i);
				if (!other.groupNeighbor(this)
						|| !other.rightGroup.contains(id)) {
					leftGroup.remove(i);
					changed = true;
				} else if (other.rightGroup.size() == 1
						&& other.onTable == Boolean.TRUE) {
					changed |= leftGroup.retainAll(Arrays.asList(i));
					changed |= onTable != Boolean.TRUE;
					onTable = true;
					break;
				}
			}
			return changed;
		}

		/**
		 * Updates this stone's left group neighbors considering the changes of
		 * all changed stones
		 * 
		 * @param changes
		 *            stones that have changed
		 * @return whether we could be updated
		 * @throws Contradiction
		 *             Is thrown if the changes contradict each other
		 */
		private boolean updateLeftGroups(HashSet<Integer> changes)
				throws Contradiction {
			boolean changed = false;
			HashSet<Integer> relevantChanges = new HashSet<Integer>(leftGroup);
			relevantChanges = new HashSet<Integer>(rightGroup);
			relevantChanges.retainAll(changes);
			for (int i : relevantChanges) {
				StoneState other = top.stones.get(i);
				if (!this.groupNeighbor(other) || !other.leftGroup.contains(id)) {
					rightGroup.remove(i);
					changed = true;
				} else if (other.leftGroup.size() == 1
						&& other.onTable == Boolean.TRUE) {
					changed |= rightGroup.retainAll(Arrays.asList(i));
					changed |= onTable != Boolean.TRUE;
					onTable = true;
					break;
				}
			}
			return changed;
		}

		/**
		 * Enforce local rule consistency
		 * 
		 * @return whether this stone changed
		 * @throws Contradiction
		 *             Is thrown if this stone can't be placed anywhere
		 */
		private boolean checkState() throws Contradiction {
			boolean changed = false;

			if (onTable == Boolean.FALSE) {
				if (leftRun.size() + rightRun.size() + leftGroup.size()
						+ rightGroup.size() != 0) {
					leftRun.clear();
					rightRun.clear();
					leftGroup.clear();
					rightGroup.clear();
					return true;
				}
				return false;
			}

			changed |= checkSetTypeKnown();

			changed |= checkLonelyStone();

			changed |= checkNeighborStoneNeeded();

			changed |= checkStoneCanBeOnTable();

			checkGroupRunExclusive();

			changed |= checkJokerColor();
			changed |= checkJokerValue();

			return changed;
		}

		/**
		 * If this stone has to be in a group it can't be part of a run and the
		 * other way around
		 * 
		 * @return whether this stone changed
		 */
		private boolean checkSetTypeKnown() {
			boolean changed = false;
			if (!(leftGroup.contains(null) || rightGroup.contains(null))) {
				changed |= leftRun.retainAll(Arrays.asList((Integer) null))
						| rightRun.retainAll(Arrays.asList((Integer) null));
			}
			if (!(leftRun.contains(null) || rightRun.contains(null))) {
				changed |= leftGroup.retainAll(Arrays.asList((Integer) null))
						| rightGroup.retainAll(Arrays.asList((Integer) null));
			}
			return changed;
		}

		/**
		 * If we have no group/run neighbors and no left/right neighbors but are
		 * on the table we need to have a neighbor for the remaining case
		 * 
		 * @return whether this stone changed
		 */
		private boolean checkLonelyStone() {
			boolean changed = false;
			@SuppressWarnings("unchecked")
			List<HashSet<Integer>> sets = Arrays.<HashSet<Integer>> asList(
					leftGroup, rightGroup, leftRun, rightRun, leftGroup,
					rightGroup, leftRun);
			for (int i = 0; i < 4; i++) {
				if (isNullSet(sets.get(i)) && isNullSet(sets.get(i + 1))
						&& isNullSet(sets.get(i + 2))) {
					changed |= sets.get(i + 3).remove(null);
				}
			}
			return changed;
		}

		/**
		 * If we have a neighbor that is on the end of a set we can't be on the
		 * end either
		 * 
		 * @return whether this stone changed
		 */
		private boolean checkNeighborStoneNeeded() {
			boolean changed = false;
			if (isSingleNonNullSet(leftRun)
					&& isNullSet(top.stones.get(leftRun.iterator().next()).leftRun)) {
				changed |= rightRun.remove(null);
			}
			if (isSingleNonNullSet(rightRun)
					&& isNullSet(top.stones.get(rightRun.iterator().next()).rightRun)) {
				changed |= leftRun.remove(null);
			}

			if (isSingleNonNullSet(leftGroup)
					&& isNullSet(top.stones.get(leftGroup.iterator().next()).leftGroup)) {
				changed |= rightGroup.remove(null);
			}
			if (isSingleNonNullSet(rightGroup)
					&& isNullSet(top.stones.get(rightGroup.iterator().next()).rightGroup)) {
				changed |= leftGroup.remove(null);
			}
			return changed;
		}

		/**
		 * When we need to have some kind of neighbor but there isn't any
		 * possible one we're either not on the table or if we have to have a
		 * contradiction
		 * 
		 * @return whether this stone changed
		 * @throws Contradiction
		 *             Is thrown if this stone can't be placed anywhere
		 */
		private boolean checkStoneCanBeOnTable() throws Contradiction {
			boolean changed = false;
			if (leftGroup.isEmpty() || rightGroup.isEmpty()
					|| leftRun.isEmpty() || rightRun.isEmpty()) {
				if (onTable == Boolean.TRUE) {
					throw new Contradiction();
				}
				if (onTable == null) {
					onTable = false;
					leftRun.clear();
					rightRun.clear();
					leftGroup.clear();
					rightGroup.clear();
					changed = true;
				}
			}
			return changed;
		}

		/**
		 * If we need to be in a group and in a run at the same time we have a
		 * contradiction
		 * 
		 * @throws Contradiction
		 *             Is thrown if this stone can't be placed anywhere
		 */
		private void checkGroupRunExclusive() throws Contradiction {
			if ((isSingleNonNullSet(leftGroup) || isSingleNonNullSet(rightGroup))
					&& (isSingleNonNullSet(leftRun) || isSingleNonNullSet(rightRun))) {
				throw new Contradiction();
			}
		}

		/**
		 * Try to derive the value of a joker stone from it's neighbor(s)
		 * 
		 * @return whether we could derive the value
		 */
		private boolean checkJokerValue() {
			boolean changed = false;
			if (this.value == null) {
				if (isSingleNonNullSet(leftGroup)) {
					this.value = top.stones.get(leftGroup.iterator().next()).value;
				} else if (isSingleNonNullSet(rightGroup)) {
					this.value = top.stones.get(rightGroup.iterator().next()).value;
				} else if (isSingleNonNullSet(leftRun)) {
					Integer value = top.stones.get(leftRun.iterator().next()).value;
					if (value != null) {
						this.value = value % settings.getHighestValue() + 1;
					}
				} else if (isSingleNonNullSet(rightRun)) {
					Integer value = top.stones.get(rightRun.iterator().next()).value;
					if (value != null) {
						this.value = (value - 2) % settings.getHighestValue()
								+ 1;
					}
				}
				changed |= this.value != null;
			}
			return changed;
		}

		/**
		 * Try to derive the color of a joker stone from it's neighbor(s)
		 * 
		 * @return whether we could derive the color
		 */
		private boolean checkJokerColor() {
			boolean changed = false;
			if (this.color == null) {
				if (isSingleNonNullSet(leftRun)) {
					this.color = top.stones.get(leftRun.iterator().next()).color;
				} else if (isSingleNonNullSet(rightRun)) {
					this.color = top.stones.get(rightRun.iterator().next()).color;
				}
				changed |= this.color != null;
			}
			return changed;
		}

		/**
		 * Check whether this stone's position, value and color are known
		 * 
		 * @return true when this stone is solved
		 */
		public boolean isSolved() {
			if (onTable == Boolean.FALSE) {
				return true;
			}
			if (onTable == null || color == null || value == null) {
				return false;
			}
			if (leftRun.size() > 1 || rightRun.size() > 1
					|| leftGroup.size() > 1 || rightGroup.size() > 1) {
				return false;
			}
			return true;
		}

		/**
		 * How badly we want to get rid of this stone
		 * 
		 * @return this stone's badness score
		 */
		public double getScore() {
			if (fromTable) {
				return 0;
			}
			return 1;
		}

		/**
		 * How many points we get for melding this stone
		 * 
		 * @return amount of points
		 */
		public double getPoints() {
			if (fromTable) {
				return 0;
			}
			if (value == null)
				return (double) settings.getHighestValue();
			else
				return (double) value;
		}

		/**
		 * Checks whether we need a joker on the left or right side to place
		 * this stone
		 * 
		 * @param side
		 *            which side to check
		 * @return true when a joker is the only possible neighbor
		 */
		@SuppressWarnings("unchecked")
		public boolean needsJoker(boolean side) {
			if (onTable != Boolean.TRUE) {
				return false;
			}
			for (HashSet<Integer> set : side ? Arrays
					.asList(leftGroup, leftRun) : Arrays.asList(rightGroup,
					rightRun)) {
				cancle: if (!set.contains(null)) {
					for (int idx : set) {
						if (!top.stones.get(idx).joker) {
							break cancle;
						}
					}
					return true;
				}
			}

			return false;
		}
	}

	/**
	 * Check whether a set of Integers only contains null
	 * 
	 * @param i
	 *            set to check
	 * @return true when it only contains null
	 */
	private static boolean isNullSet(HashSet<Integer> i) {
		return i.size() == 1 && i.contains(null);
	}

	/**
	 * Check whether a set of Integers only contains a single non null value
	 * 
	 * @param i
	 *            set to check
	 * @return true when it only contains a single non null value
	 */
	private static boolean isSingleNonNullSet(HashSet<Integer> i) {
		return i.size() == 1 && !i.contains(null);
	}

	/**
	 * Creates new turn logic
	 * 
	 * @param settings
	 *            the game settings
	 * @param tableStones
	 *            all stones on the table
	 * @param handStones
	 *            all stones on the hand
	 */
	public TurnLogic(GameSettings settings, Collection<Stone> tableStones,
			Collection<Stone> handStones) {
		this.settings = settings;

		stoneCount = tableStones.size() + handStones.size();

		maxColor = Collections.max(settings.getStoneColors());
		minColor = Collections.min(settings.getStoneColors());

		stoneColors = new ArrayList<StoneColor>(settings.getStoneColors());
		Collections.sort(stoneColors);

		top = new State();
		stack.add(top);

		ArrayList<Pair<Stone, Boolean>> sortedStones = new ArrayList<Pair<Stone, Boolean>>();
		inputStones = new ArrayList<Stone>();
		for (Stone stone : tableStones) {
			sortedStones.add(new Pair<Stone, Boolean>(stone, true));
		}
		for (Stone stone : handStones) {
			sortedStones.add(new Pair<Stone, Boolean>(stone, false));
		}
		Collections.sort(sortedStones, new Comparator<Pair<Stone, Boolean>>() {
			@Override
			public int compare(Pair<Stone, Boolean> o1, Pair<Stone, Boolean> o2) {
				int cmp;
				cmp = ((Boolean) o1.getFirst().isJoker()).compareTo(o2
						.getFirst().isJoker());
				if (cmp != 0) {
					return -cmp;
				}
				cmp = (o1.getFirst().getColor()).compareTo(o2.getFirst()
						.getColor());
				if (cmp != 0) {
					return cmp;
				}
				cmp = ((Integer) o1.getFirst().getValue()).compareTo(o2
						.getFirst().getValue());
				return cmp;
			}
		});

		int i = 0;
		for (Pair<Stone, Boolean> pair : sortedStones) {
			top.add(new StoneState(i++, pair.getFirst(), pair.getSecond()));
			inputStones.add(pair.getFirst());
		}
	}

	/**
	 * Include initial meld threshold into turn logic
	 */
	public void needIntialMeldThreshold() {
		neededPoints = settings.getInitialMeldThreshold();
	}

	/**
	 * Remove a contradicted state from the try stack, reset top
	 */
	private void pop() {
		stack.remove(stack.size() - 1);
		if (!stack.isEmpty()) {
			top = stack.get(stack.size() - 1);
		}
	}

	/**
	 * Remove an unsolved state, to be replaced with refined state, from the try
	 * stack
	 */
	private void replace() {
		stack.remove(stack.size() - 1);
	}

	/**
	 * Push multiple new state onto the try stack
	 * 
	 * @param states
	 *            states to push
	 */
	private void pushes(State... states) {
		for (State state : states) {
			stack.add(state);
		}
	}

	/**
	 * Done with modifying the try stack, reset top
	 */
	private void done() {
		top = stack.get(stack.size() - 1);
	}

	/**
	 * Aborts currently running solve call
	 */
	public void abort() {
		abort = true;
	}

	/**
	 * Get the found stones and create output sets
	 * 
	 * @return output sets to put on table
	 */
	public List<StoneSet> getResult() {
		State result = bestState;

		if (result == null) {
			return null;
		}

		ArrayList<StoneSet> outputSets = new ArrayList<StoneSet>();

		for (int i = 0; i < stoneCount; i++) {
			StoneState stone = result.stones.get(i);
			if (isNullSet(stone.leftRun) && isNullSet(stone.leftGroup)) {
				ArrayList<Stone> setStones = new ArrayList<Stone>();
				while (true) {
					setStones.add(inputStones.get(stone.id));
					if (isNullSet(stone.rightRun)
							&& isNullSet(stone.rightGroup)) {
						break;
					}
					Integer rightRunID = stone.rightRun.iterator().next();
					Integer rightGroupID = stone.rightGroup.iterator().next();

					stone = result.stones.get(rightRunID == null ? rightGroupID
							: rightRunID);
				}
				outputSets.add(new StoneSet(setStones));
			}
		}
		return outputSets;
	}

	/**
	 * Solves next state on stack while not aborted
	 * 
	 * @return solved
	 */
	public boolean solve() {
		if (top.isSolved()) {
			pop();
		}
		while (stack.size() != 0) {
			if (abort) {
				return false;
			}
			try {
				top.updateStones();
				if (top.isSolved()) {
					bestState = top;
					return true;
				}
				branch();
				done();
			} catch (Contradiction c) {
				pop();
			}
		}
		return false;
	}

	/**
	 * Optimizes the solution found as long as stopped from control
	 * 
	 * @return score of found solution
	 */
	public double optimize() {
		while (!autoAbort && solve()) {
			neededScore = top.getScore();
		}
		return neededScore;
	}

	/**
	 * Refine the currently unsolved top stack state
	 */
	private void branch() {
		for (int i = 0; i < stoneCount; i++) {
			StoneState stone = top.stones.get(i);
			if (stone.leftRun.size() > 1) {
				branchLeftRun(i, stone);
				return;
			}
			if (stone.rightRun.size() > 1) {
				branchRightRun(i, stone);
				return;
			}
			if (stone.leftGroup.size() > 1) {
				branchLeftGroup(i, stone);
				return;
			}
			if (stone.rightGroup.size() > 1) {
				branchRightGroup(i, stone);
				return;
			}
			if (stone.onTable == null) {
				branchOnHand(i);
				return;
			}
		}
		for (int i = 0; i < stoneCount; i++) {
			StoneState stone = top.stones.get(i);
			if (stone.color == null) {
				branchColor(i);
				return;
			}
			if (stone.value == null) {
				branchValue(i);
				return;
			}
		}
		// This should never happen
		throw new Error("Internal AI error");
	}

	/**
	 * Create states for all possible values of stone i
	 * 
	 * @param i
	 *            stone id to branch on
	 */
	private void branchValue(int i) {
		replace();
		for (int value = 1; value <= settings.getHighestValue(); value++) {
			State newState = new State(top);
			newState.stones.get(i).value = value;
			newState.changedStones.add(i);
			pushes(newState);
		}
	}

	/**
	 * Create states for all possible colors of stone i
	 * 
	 * @param i
	 *            stone id to branch on
	 */
	private void branchColor(int i) {
		replace();
		for (StoneColor color : stoneColors) {
			State newState = new State(top);
			newState.stones.get(i).color = color;
			newState.changedStones.add(i);
			pushes(newState);
		}

	}

	/**
	 * Create states for all possible right group neighbors of stone i
	 * 
	 * @param i
	 *            stone id to branch on
	 */
	private void branchRightGroup(int i, StoneState stone) {
		replace();
		for (Integer id : stone.rightGroup) {
			State newState = new State(top);
			newState.stones.get(i).rightGroup.clear();
			newState.stones.get(i).rightGroup.add(id);
			newState.changedStones.add(i);
			pushes(newState);
		}
	}

	/**
	 * Create states for all possible left group neighbors of stone i
	 * 
	 * @param i
	 *            stone id to branch on
	 */
	private void branchLeftGroup(int i, StoneState stone) {
		replace();
		for (Integer id : stone.leftGroup) {
			State newState = new State(top);
			newState.stones.get(i).leftGroup.clear();
			newState.stones.get(i).leftGroup.add(id);
			newState.changedStones.add(i);
			pushes(newState);
		}
	}

	/**
	 * Create states for all possible right run neighbors of stone i
	 * 
	 * @param i
	 *            stone id to branch on
	 */
	private void branchRightRun(int i, StoneState stone) {
		replace();
		for (Integer id : stone.rightRun) {
			State newState = new State(top);
			newState.stones.get(i).rightRun.clear();
			newState.stones.get(i).rightRun.add(id);
			newState.changedStones.add(i);
			pushes(newState);
		}
	}

	/**
	 * Create states for all possible left run neighbors of stone i
	 * 
	 * @param i
	 *            stone id to branch on
	 */
	private void branchLeftRun(int i, StoneState stone) {
		replace();
		for (Integer id : stone.leftRun) {
			State newState = new State(top);
			newState.stones.get(i).leftRun.clear();
			newState.stones.get(i).leftRun.add(id);
			newState.changedStones.add(i);
			pushes(newState);
		}
	}

	/**
	 * Create states with stone i on the table and stone i on the hand
	 * 
	 * @param i
	 *            stone id to branch on
	 */
	private void branchOnHand(int i) {
		replace();
		State newState = new State(top);
		newState.stones.get(i).onTable = true;
		newState.changedStones.add(i);
		State altState = new State(top);
		altState.stones.get(i).onTable = false;
		altState.changedStones.add(i);
		pushes(altState, newState);
	}

	/**
	 * Abort as soon as a solution is found
	 */
	public void autoAbort() {
		if (bestState != null) {
			abort = true;
		}
		autoAbort = true;
	}
}