package jrummikub.control;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.TreeMap;

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

/**
 * A collection of several AI utility methods with given game settings
 * 
 */
public class AIUtil {

	GameSettings settings;
	List<StoneColor> stoneColors;

	/**
	 * The utility class's methods calculate their results based on the game
	 * settings
	 * 
	 * @param settings
	 *          the underlying game settings
	 */
	public AIUtil(GameSettings settings) {
		this.settings = settings;

		stoneColors = new ArrayList<StoneColor>(Arrays.asList(StoneColor.values()));
		stoneColors.retainAll(settings.getStoneColors());
	}

	private static class SearchState {
		int pointsMissing;
		TreeMap<Pair<Integer, StoneColor>, Integer> stoneCounts;
		int jokerCount;

		SearchState(int pointsMissing,
				TreeMap<Pair<Integer, StoneColor>, Integer> stoneCounts, int jokerCount) {
			this.pointsMissing = pointsMissing;
			this.stoneCounts = stoneCounts;
			this.jokerCount = jokerCount;
		}
	}

	/**
	 * Tries to find sets with a certain total of points. If only lower totals are
	 * found, returns the sets with the highest cumulated point total.
	 * 
	 * @param pointsMissing
	 *          the desired number of points
	 * @param stoneCounts
	 *          the number of each stone
	 * @param jokerCount
	 *          the total number of jokers in the game
	 * @return the sets that have the desired point total or the highest found
	 */
	@SuppressWarnings("unchecked")
	public Pair<List<StoneSet>, Integer> findSetsWithTotalPoints(
			int pointsMissing,
			TreeMap<Pair<Integer, StoneColor>, Integer> stoneCounts, int jokerCount) {

		if (pointsMissing <= 0) {
			return new Pair<List<StoneSet>, Integer>(
					Collections.<StoneSet> emptyList(), 0);
		}

		stoneCounts = (TreeMap<Pair<Integer, StoneColor>, Integer>) stoneCounts
				.clone();

		Pair<List<StoneSet>, Integer> result, bestResult;
		bestResult = new Pair<List<StoneSet>, Integer>(
				Collections.<StoneSet> emptyList(), 0);

		for (int value = settings.getHighestValue(); value >= 1; value--) {
			for (StoneColor color : stoneColors) {
				Pair<Integer, StoneColor> stone = new Pair<Integer, StoneColor>(value,
						color);

				if (stoneCounts.containsKey(stone)) {
					decrementStoneCount(stoneCounts, stone);
					result = findRunsWithTotalPoints(new SearchState(pointsMissing
							- value, stoneCounts, jokerCount), stone, 1);
					if (result.getSecond() >= pointsMissing)
						return result;
					if (result.getSecond() > bestResult.getSecond())
						bestResult = result;

					result = findGroupsWithTotalPoints(new SearchState(pointsMissing
							- value, stoneCounts, jokerCount), value,
							Collections.singletonList(color), color);
					if (result.getSecond() >= pointsMissing)
						return result;
					if (result.getSecond() > bestResult.getSecond())
						bestResult = result;
				}

				if (jokerCount > 0) {
					result = findRunsWithTotalPoints(new SearchState(pointsMissing
							- value, stoneCounts, jokerCount - 1), stone, 1);
					if (result.getSecond() >= pointsMissing)
						return result;
					if (result.getSecond() > bestResult.getSecond())
						bestResult = result;

					result = findGroupsWithTotalPoints(new SearchState(pointsMissing
							- value, stoneCounts, jokerCount - 1), value,
							Collections.singletonList(color), color);
					if (result.getSecond() >= pointsMissing)
						return result;
					if (result.getSecond() > bestResult.getSecond())
						bestResult = result;
				}
			}
		}

		return bestResult;
	}

	private Pair<List<StoneSet>, Integer> findGroupsWithTotalPoints(
			SearchState searchState, int value, List<StoneColor> chosenColors,
			StoneColor testedColor) {

		StoneColor nextColor = getNextColor(testedColor);
		Pair<Integer, StoneColor> nextStone = new Pair<Integer, StoneColor>(value,
				nextColor);

		Pair<List<StoneSet>, Integer> result, bestResult;
		bestResult = new Pair<List<StoneSet>, Integer>(
				Collections.<StoneSet> emptyList(), 0);

		if (nextColor != null) {
			if (searchState.stoneCounts.containsKey(nextStone)) {
				decrementStoneCount(searchState.stoneCounts, nextStone);
				List<StoneColor> newColors = new ArrayList<StoneColor>(chosenColors);
				newColors.add(nextColor);
				result = findGroupsWithTotalPoints(new SearchState(
						searchState.pointsMissing, searchState.stoneCounts,
						searchState.jokerCount), value, newColors, nextColor);
				if (result.getSecond() >= searchState.pointsMissing)
					return result;
				if (result.getSecond() > bestResult.getSecond())
					bestResult = result;
				incrementStoneCount(searchState.stoneCounts, nextStone);
			}
			if (searchState.jokerCount > 0) {
				List<StoneColor> newColors = new ArrayList<StoneColor>(chosenColors);
				newColors.add(nextColor);
				result = findGroupsWithTotalPoints(new SearchState(
						searchState.pointsMissing, searchState.stoneCounts,
						searchState.jokerCount - 1), value, newColors, nextColor);
				if (result.getSecond() >= searchState.pointsMissing)
					return result;
				if (result.getSecond() > bestResult.getSecond())
					bestResult = result;
			}
			result = findGroupsWithTotalPoints(new SearchState(
					searchState.pointsMissing, searchState.stoneCounts,
					searchState.jokerCount), value, chosenColors, nextColor);
			if (result.getSecond() >= searchState.pointsMissing)
				return result;
			if (result.getSecond() > bestResult.getSecond())
				bestResult = result;
		}

		if (chosenColors.size() >= 3) {
			int groupPoints = chosenColors.size() * value;
			result = findSetsWithTotalPoints(searchState.pointsMissing - groupPoints,
					searchState.stoneCounts, searchState.jokerCount);
			List<Stone> newStones = new ArrayList<Stone>();
			for (StoneColor color : chosenColors) {
				newStones.add(new Stone(value, color));
			}
			List<StoneSet> newResultList = new ArrayList<StoneSet>(result.getFirst());
			newResultList.add(new StoneSet(newStones));
			result = new Pair<List<StoneSet>, Integer>(newResultList,
					result.getSecond() + groupPoints);
			if (result.getSecond() >= searchState.pointsMissing)
				return result;
			if (result.getSecond() > bestResult.getSecond())
				bestResult = result;
		}
		return bestResult;
	}

	private Pair<List<StoneSet>, Integer> findRunsWithTotalPoints(
			SearchState searchState, Pair<Integer, StoneColor> testedStone,
			int runLength) {

		Pair<List<StoneSet>, Integer> result, bestResult;
		bestResult = new Pair<List<StoneSet>, Integer>(
				Collections.<StoneSet> emptyList(), 0);

		Pair<Integer, StoneColor> nextStone = null;
		if (testedStone.getFirst() > 1) {
			int nextValue = testedStone.getFirst() - 1;
			nextStone = new Pair<Integer, StoneColor>(nextValue,
					testedStone.getSecond());

			if (searchState.stoneCounts.containsKey(nextStone)) {
				decrementStoneCount(searchState.stoneCounts, nextStone);
				result = findRunsWithTotalPoints(new SearchState(
						searchState.pointsMissing, searchState.stoneCounts,
						searchState.jokerCount), nextStone, runLength + 1);
				if (result.getSecond() >= searchState.pointsMissing)
					return result;
				if (result.getSecond() > bestResult.getSecond())
					bestResult = result;
				incrementStoneCount(searchState.stoneCounts, nextStone);

			}
			if (searchState.jokerCount > 0) {
				result = findRunsWithTotalPoints(new SearchState(
						searchState.pointsMissing, searchState.stoneCounts,
						searchState.jokerCount - 1), nextStone, runLength + 1);
				if (result.getSecond() >= searchState.pointsMissing)
					return result;
				if (result.getSecond() > bestResult.getSecond())
					bestResult = result;
			}
		}

		if (runLength >= 3) {

			int below = testedStone.getFirst() - 1;
			int high = below + runLength;
			int runPoints = (high * (high + 1)) / 2 - (below * (below + 1)) / 2;

			result = findSetsWithTotalPoints(searchState.pointsMissing - runPoints,
					searchState.stoneCounts, searchState.jokerCount);

			List<Stone> newStones = new ArrayList<Stone>();
			for (int i = 0; i < runLength; i++) {
				newStones.add(new Stone(i + testedStone.getFirst(), testedStone
						.getSecond()));
			}
			List<StoneSet> newResultList = new ArrayList<StoneSet>(result.getFirst());
			newResultList.add(new StoneSet(newStones));
			result = new Pair<List<StoneSet>, Integer>(newResultList,
					result.getSecond() + runPoints);

			if (result.getSecond() >= searchState.pointsMissing)
				return result;
			if (result.getSecond() > bestResult.getSecond())
				bestResult = result;
		}
		return bestResult;
	}

	static void incrementStoneCount(
			TreeMap<Pair<Integer, StoneColor>, Integer> stones,
			Pair<Integer, StoneColor> stone) {
		if (stones.containsKey(stone)) {
			stones.put(stone, stones.get(stone) + 1);
		} else {
			stones.put(stone, 1);
		}
	}

	static void decrementStoneCount(
			TreeMap<Pair<Integer, StoneColor>, Integer> stones,
			Pair<Integer, StoneColor> stone) {
		int count = stones.get(stone);
		count--;

		if (count == 0) {
			stones.remove(stone);
		} else {
			stones.put(stone, count);
		}
	}

	StoneColor getNextColor(StoneColor color) {
		int index = stoneColors.indexOf(color) + 1;
		if (index >= stoneColors.size()) {
			return null;
		}
		return stoneColors.get(index);
	}

	private final static Comparator<Pair<Integer, StoneColor>> comparator = new Comparator<Pair<Integer, StoneColor>>() {

		@Override
		public int compare(Pair<Integer, StoneColor> o1,
				Pair<Integer, StoneColor> o2) {
			int firstComparison = o1.getFirst().compareTo(o2.getFirst());
			if (firstComparison != 0) {
				return -firstComparison;
			} else {
				return o1.getSecond().compareTo(o2.getSecond());
			}
		}
	};

	/**
	 * Counts the numbers of stones
	 * 
	 * @param stones
	 *          the stones to count
	 * @return the numbers for all stones
	 */
	public static Pair<TreeMap<Pair<Integer, StoneColor>, Integer>, Integer> countStones(
			List<Stone> stones) {
		int jokerCount = 0;
		TreeMap<Pair<Integer, StoneColor>, Integer> stoneCounts = new TreeMap<Pair<Integer, StoneColor>, Integer>(
				comparator);

		for (Stone stone : stones) {
			if (stone.isJoker()) {
				jokerCount++;
			} else {
				Pair<Integer, StoneColor> key = new Pair<Integer, StoneColor>(
						stone.getValue(), stone.getColor());

				incrementStoneCount(stoneCounts, key);
			}
		}
		return new Pair<TreeMap<Pair<Integer, StoneColor>, Integer>, Integer>(
				stoneCounts, jokerCount);
	}
}