Implemented routine to check if initial melds are possible

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

4 files changed, 204 insertions, 12 deletions

diff --git a/src/jrummikub/model/Hand.java b/src/jrummikub/model/Hand.java
index 724a48e..f415620 100644
--- a/src/jrummikub/model/Hand.java
+++ b/src/jrummikub/model/Hand.java
@@ -1,8 +1,13 @@
 package jrummikub.model;
 
-import jrummikub.util.Pair;
+import static jrummikub.model.StoneTray.Direction.LEFT;
+import static jrummikub.model.StoneTray.Direction.RIGHT;
+
+import java.util.Arrays;
+import java.util.Comparator;
+import java.util.TreeMap;
 
-import static jrummikub.model.StoneTray.Direction.*;
+import jrummikub.util.Pair;
 
 /** Class managing a {@link Player}'s {@link Stone}s */
 public class Hand extends StoneTray<Stone> implements IHand {
@@ -10,9 +15,15 @@ public class Hand extends StoneTray<Stone> implements IHand {
 	 * The width of the hand
 	 */
 	public final static int WIDTH = 14;
-	
+
 	private GameSettings settings;
-	
+
+	/**
+	 * Create a new empty hand with given game settings
+	 * 
+	 * @param settings
+	 *            the game settings
+	 */
 	public Hand(GameSettings settings) {
 		this.settings = settings;
 	}
@@ -42,8 +53,8 @@ public class Hand extends StoneTray<Stone> implements IHand {
 	}
 
 	@Override
-	protected Pair<Position, Direction> fixInvalidDrop(Stone stone, Position pos,
-			Direction dir) {
+	protected Pair<Position, Direction> fixInvalidDrop(Stone stone,
+			Position pos, Direction dir) {
 		float x = pos.getX();
 		float y = pos.getY();
 
@@ -54,16 +65,18 @@ public class Hand extends StoneTray<Stone> implements IHand {
 			return new Pair<Position, Direction>(new Position(0, y), RIGHT);
 		} else {
 			if (getFreeRowSpace((int) y) == 0) {
-				return new Pair<Position, Direction>(new Position(0, y + 1), RIGHT);
+				return new Pair<Position, Direction>(new Position(0, y + 1),
+						RIGHT);
 			} else {
-				return new Pair<Position, Direction>(new Position(WIDTH - 1, y), LEFT);
+				return new Pair<Position, Direction>(
+						new Position(WIDTH - 1, y), LEFT);
 			}
 		}
 	}
 
 	public int getStonePoints() {
 		int points = 0;
-		
+
 		for (Pair<Stone, Position> entry : this) {
 			if (entry.getFirst().isJoker()) {
 				points += settings.getJokerPoints();
@@ -71,13 +84,181 @@ public class Hand extends StoneTray<Stone> implements IHand {
 				points += entry.getFirst().getValue();
 			}
 		}
-		
+
 		return points;
 	}
 
+	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());
+			}
+		}
+	};
+
 	@Override
 	public boolean isInitialMeldPossible() {
-		// TODO Auto-generated method stub
-		throw new Error("not implemented");
+		int jokerCount = 0;
+		TreeMap<Pair<Integer, StoneColor>, Integer> stoneCounts = new TreeMap<Pair<Integer, StoneColor>, Integer>(
+				comparator);
+
+		for (Pair<Stone, Position> entry : this) {
+			if (entry.getFirst().isJoker()) {
+				jokerCount++;
+			} else {
+				Pair<Integer, StoneColor> key = new Pair<Integer, StoneColor>(
+						entry.getFirst().getValue(), entry.getFirst()
+								.getColor());
+
+				incrementStoneCount(stoneCounts, key);
+			}
+		}
+
+		return findSetsWithTotalPoints(settings.getInitialMeldThreshold(),
+				stoneCounts, jokerCount);
+	}
+
+	private 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);
+		}
+	}
+
+	private 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);
+		}
+	}
+
+	@SuppressWarnings("unchecked")
+	private 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;
+	}
+
+	private StoneColor getNextColor(StoneColor color) {
+		int index = Arrays.binarySearch(StoneColor.values(), color) + 1;
+		if (index >= StoneColor.values().length) {
+			return null;
+		}
+		return StoneColor.values()[index];
+	}
+
+	private 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;
+	}
+
+	private 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;
 	}
 }
diff --git a/src/jrummikub/model/IHand.java b/src/jrummikub/model/IHand.java
index a58c7be..afe5c12 100644
--- a/src/jrummikub/model/IHand.java
+++ b/src/jrummikub/model/IHand.java
@@ -28,5 +28,11 @@ public interface IHand extends IStoneTray<Stone> {
 	 */

 	int getStonePoints();

 

+	/**

+	 * Tests whether it is possible to lay down an initial meld using the stones

+	 * on the hand

+	 * 

+	 * @return true if an initial meld is possible

+	 */

 	public abstract boolean isInitialMeldPossible();

 }

diff --git a/src/jrummikub/model/IPlayer.java b/src/jrummikub/model/IPlayer.java
index 6c4a9ae..0545352 100644
--- a/src/jrummikub/model/IPlayer.java
+++ b/src/jrummikub/model/IPlayer.java
@@ -29,6 +29,9 @@ public interface IPlayer {
 	/**
 	 * Set if the player laid out
 	 * 
+	 * @param laidOut
+	 *            the player laid out
+	 * 
 	 */
 	void setLaidOut(boolean laidOut);
 }
\ No newline at end of file
diff --git a/src/jrummikub/model/Player.java b/src/jrummikub/model/Player.java
index 6d3e6d6..1d54c4a 100644
--- a/src/jrummikub/model/Player.java
+++ b/src/jrummikub/model/Player.java
@@ -11,6 +11,8 @@ public class Player implements IPlayer {
 	 * 
 	 * @param settings
 	 *            the player settings
+	 * @param gameSettings
+	 *            the game settings
 	 */
 	public Player(PlayerSettings settings, GameSettings gameSettings) {
 		this.settings = settings;