Extracted a AIUtil class from several hand methods

git-svn-id: svn://sunsvr01.isp.uni-luebeck.de/swproj13/trunk@330 72836036-5685-4462-b002-a69064685172

1 files changed, 208 insertions, 0 deletions

diff --git a/src/jrummikub/control/AIUtil.java b/src/jrummikub/control/AIUtil.java
new file mode 100644
index 0000000..66a3442
--- /dev/null
+++ b/src/jrummikub/control/AIUtil.java
@@ -0,0 +1,208 @@
+package jrummikub.control;

+

+import java.util.Arrays;

+import java.util.Comparator;

+import java.util.List;

+import java.util.TreeMap;

+

+import jrummikub.model.Stone;

+import jrummikub.model.StoneColor;

+import jrummikub.util.Pair;

+

+/**

+ * A collection of several AI utility methods

+ * 

+ */

+public class AIUtil {

+

+	private AIUtil() {

+	}

+

+	/**

+	 * Finds sets with a certain total of points

+	 * 

+	 * @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 whether such sets exist

+	 */

+	@SuppressWarnings("unchecked")

+	public static boolean findSetsWithTotalPoints(int pointsMissing,

+			TreeMap<Pair<Integer, StoneColor>, Integer> stoneCounts, int jokerCount) {

+

+		if (pointsMissing <= 0) {

+			return true;

+		}

+

+		stoneCounts = (TreeMap<Pair<Integer, StoneColor>, Integer>) stoneCounts

+				.clone();

+

+		for (int value = 13; value >= 1; value--) {

+			for (StoneColor color : StoneColor.values()) {

+				Pair<Integer, StoneColor> stone = new Pair<Integer, StoneColor>(value,

+						color);

+

+				if (stoneCounts.containsKey(stone)) {

+					decrementStoneCount(stoneCounts, stone);

+

+					if (findRunsWithTotalPoints(pointsMissing - value, stoneCounts,

+							jokerCount, stone, 1))

+						return true;

+					if (findGroupsWithTotalPoints(pointsMissing - value, stoneCounts,

+							jokerCount, stone, 1))

+						return true;

+				}

+

+				if (jokerCount > 0) {

+					if (findRunsWithTotalPoints(pointsMissing - value, stoneCounts,

+							jokerCount - 1, stone, 1))

+						return true;

+					if (findGroupsWithTotalPoints(pointsMissing - value, stoneCounts,

+							jokerCount - 1, stone, 1))

+						return true;

+				}

+			}

+		}

+

+		return false;

+	}

+

+	static boolean findGroupsWithTotalPoints(int pointsMissing,

+			TreeMap<Pair<Integer, StoneColor>, Integer> stoneCounts, int jokerCount,

+			Pair<Integer, StoneColor> stone, int groupSize) {

+

+		StoneColor nextColor = getNextColor(stone.getSecond());

+		Pair<Integer, StoneColor> nextStone = new Pair<Integer, StoneColor>(

+				stone.getFirst(), nextColor);

+

+		if (nextColor != null) {

+			if (stoneCounts.containsKey(nextStone)) {

+				decrementStoneCount(stoneCounts, nextStone);

+				if (findGroupsWithTotalPoints(pointsMissing - stone.getFirst(),

+						stoneCounts, jokerCount, nextStone, groupSize + 1))

+					return true;

+				incrementStoneCount(stoneCounts, nextStone);

+			}

+			if (jokerCount > 0) {

+				if (findGroupsWithTotalPoints(pointsMissing - stone.getFirst(),

+						stoneCounts, jokerCount - 1, nextStone, groupSize + 1))

+					return true;

+			}

+			if (findGroupsWithTotalPoints(pointsMissing, stoneCounts, jokerCount,

+					nextStone, groupSize))

+				return true;

+		}

+

+		if (groupSize >= 3) {

+			if (findSetsWithTotalPoints(pointsMissing, stoneCounts, jokerCount))

+				return true;

+		}

+		return false;

+	}

+

+	static boolean findRunsWithTotalPoints(int pointsMissing,

+			TreeMap<Pair<Integer, StoneColor>, Integer> stoneCounts, int jokerCount,

+			Pair<Integer, StoneColor> stone, int runLength) {

+

+		Pair<Integer, StoneColor> nextStone = null;

+		if (stone.getFirst() > 1) {

+			int nextValue = stone.getFirst() - 1;

+			nextStone = new Pair<Integer, StoneColor>(nextValue, stone.getSecond());

+

+			if (stoneCounts.containsKey(nextStone)) {

+				decrementStoneCount(stoneCounts, nextStone);

+				if (findRunsWithTotalPoints(pointsMissing - nextValue, stoneCounts,

+						jokerCount, nextStone, runLength + 1))

+					return true;

+				incrementStoneCount(stoneCounts, nextStone);

+

+			}

+			if (jokerCount > 0) {

+				if (findRunsWithTotalPoints(pointsMissing - nextValue, stoneCounts,

+						jokerCount - 1, nextStone, runLength + 1))

+					return true;

+			}

+		}

+

+		if (runLength >= 3) {

+			if (findSetsWithTotalPoints(pointsMissing, stoneCounts, jokerCount))

+				return true;

+		}

+		return false;

+	}

+

+	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);

+		}

+	}

+

+	static StoneColor getNextColor(StoneColor color) {

+		int index = Arrays.binarySearch(StoneColor.values(), color) + 1;

+		if (index >= StoneColor.values().length) {

+			return null;

+		}

+		return StoneColor.values()[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);

+	}

+}