//copyright (C) 2007 Mocanu Cristian Romeo
package balls;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.List;
/**
* Describe class
<code>Transition</code> here.
*
* @author <a
href="mailto:chrimeea@yahoo.com">Cristian Mocanu</a>
* @version 1.0
*/
public class Transition implements Cloneable {
private
List<Integer> leftPan;
private
List<Integer> rightPan;
private Knowledge
knowledge;
public Transition(Knowledge
k) {
leftPan =
new LinkedList<Integer>();
rightPan =
new LinkedList<Integer>();
knowledge =
k.clone();
}
public
Transition(List<Integer> lp, List<Integer> rp, Knowledge k) {
leftPan =
new LinkedList<Integer>(lp);
rightPan =
new LinkedList<Integer>(rp);
knowledge =
k.clone();
}
private void
generateForSize(int size) {
assert size
> 0;
leftPan =
new LinkedList<Integer>();
rightPan =
new LinkedList<Integer>();
int k = 0;
for (int b:
sortBalls()) {
if (k < size) {
leftPan.add(b);
} else if (k < 2 * size) {
rightPan.add(b);
} else {
break;
}
k++;
}
}
public
List<Integer> getComparedBalls() {
List<Integer>
cb = new LinkedList<Integer>(leftPan);
cb.addAll(rightPan);
return cb;
}
public
List<Integer> getRemainingBalls() {
List<Integer>
remaining = new LinkedList<Integer>();
for (int i
= 0; i < knowledge.getTotalBalls(); i++) {
remaining.add(i);
}
remaining.removeAll(getComparedBalls());
return
remaining;
}
public
List<Integer> getLeftPan() {
return
leftPan;
}
public
List<Integer> getRightPan() {
return
rightPan;
}
public boolean
isCanonical() {
return
(noExcludedInEachPanel() &&
smallerFirst() &&
firstUnknown() &&
mostUnknownFirst() &&
ascendingOrder());
}
private boolean
noExcludedInEachPanel() {
if
(knowledge.containState(leftPan, BallState.EXCLUDED) &&
knowledge.containState(rightPan,
BallState.EXCLUDED)) {
return false;
}
return true;
}
private boolean
smallerFirst() {
int
minExcluded, minUnknown, minUnknownLight, minUnknownHeavy;
minExcluded
= minUnknown = minUnknownLight = minUnknownHeavy = knowledge.getTotalBalls();
for (int b:
getRemainingBalls()) {
if (b < minExcluded &&
knowledge.isState(b, BallState.EXCLUDED)) {
minExcluded
= b;
} else if (b < minUnknown &&
knowledge.isState(b, BallState.UNKNOWN)) {
minUnknown
= b;
} else if (b < minUnknownLight
&& knowledge.isState(b, BallState.UNKNOWN_LIGHT)) {
minUnknownLight
= b;
} else if (b < minUnknownHeavy
&& knowledge.isState(b, BallState.UNKNOWN_HEAVY)) {
minUnknownHeavy
= b;
}
}
for (int b:
getComparedBalls()) {
if (b > minExcluded &&
knowledge.isState(b, BallState.EXCLUDED)) {
return
false;
} else if (b > minUnknown &&
knowledge.isState(b, BallState.UNKNOWN)) {
return
false;
} else if (b > minUnknownLight
&& knowledge.isState(b, BallState.UNKNOWN_LIGHT)) {
return
false;
} else if (b > minUnknownHeavy
&& knowledge.isState(b, BallState.UNKNOWN_HEAVY)) {
return
false;
}
}
return
true;
}
private boolean
firstUnknown() {
List<Integer>
c = leftPan;
while
(true) {
int prev = -1;
for (int b: c) {
if
(prev > -1) {
if (knowledge.isState(prev,
BallState.EXCLUDED) &&
knowledge.isUnknown(b))
{
return
false;
} else if (knowledge.isState(prev,
BallState.UNKNOWN_HEAVY) &&
knowledge.isState(b,
BallState.UNKNOWN_LIGHT)) {
return
false;
}
}
prev
= b;
}
if (c == leftPan) {
c
= rightPan;
} else {
break;
}
}
return
true;
}
private boolean
mostUnknownFirst() {
int
allUnknownLeft = knowledge.countState(leftPan, BallState.UNKNOWN);
int
allUnknownLightLeft = knowledge.countState(leftPan, BallState.UNKNOWN_LIGHT);
int
allUnknownHeavyLeft = knowledge.countState(leftPan, BallState.UNKNOWN_HEAVY);
int
allUnknownRight = knowledge.countState(rightPan, BallState.UNKNOWN);
int
allUnknownLightRight = knowledge.countState(rightPan, BallState.UNKNOWN_LIGHT);
int
allUnknownHeavyRight = knowledge.countState(rightPan, BallState.UNKNOWN_HEAVY);
if
(allUnknownLeft < allUnknownRight) {
return false;
} else if
(allUnknownLeft == allUnknownRight) {
if (allUnknownLightLeft < allUnknownLightRight)
{
return
false;
} else if (allUnknownLightLeft ==
allUnknownLightRight) {
if
(allUnknownHeavyLeft < allUnknownHeavyRight) {
return false;
}
}
}
return
true;
}
private boolean
ascendingOrder() {
int
lastBall = -1;
for (int b:
getComparedBalls()) {
if (lastBall > 0) {
if
(knowledge.isStateEqual(b, lastBall)) {
if (b < lastBall) {
return
false;
}
}
}
lastBall = b;
}
return
true;
}
private boolean
increasePanel(List<Integer> panel) {
List<Integer>
availableb = getRemainingBalls();
for (int b
= panel.size() - 1; b >= 0; b--) {
int p = panel.get(b);
if (!knowledge.isState(p,
BallState.EXCLUDED)) {
BallState
bstate = knowledge.getState(p).nextState();
int
iofstate = knowledge.ballOfState(availableb, bstate);
while
(iofstate == -1) {
if (bstate != BallState.EXCLUDED) {
bstate
= bstate.nextState();
} else {
break;
}
iofstate =
knowledge.ballOfState(availableb, bstate);
}
if
(iofstate >= 0) {
panel.set(b, iofstate);
for (int i = b + 1; i < panel.size();
i++) {
if
(knowledge.isStateEqual(panel.get(i - 1), panel.get(i))) {
panel.set(i - 1, panel.get(i));
}
else {
panel.set(i - 1, iofstate);
return true;
}
}
panel.set(panel.size() - 1, iofstate);
return true;
}
}
}
return
false;
}
private
List<Integer> sortBalls() {
List<Integer>
lUnknown = new LinkedList<Integer>();
List<Integer>
lUnknownLight = new LinkedList<Integer>();
List<Integer>
lUnknownHeavy = new LinkedList<Integer>();
List<Integer>
lExcluded = new LinkedList<Integer>();
for (int b
= 0; b < knowledge.getTotalBalls(); b++) {
if (knowledge.isState(b,
BallState.UNKNOWN)) {
lUnknown.add(b);
} else if (knowledge.isState(b,
BallState.UNKNOWN_LIGHT)) {
lUnknownLight.add(b);
} else if (knowledge.isState(b, BallState.UNKNOWN_HEAVY))
{
lUnknownHeavy.add(b);
} else {
lExcluded.add(b);
}
}
lUnknown.addAll(lUnknownLight);
lUnknown.addAll(lUnknownHeavy);
lUnknown.addAll(lExcluded);
return
lUnknown;
}
private boolean
increaseTransition() {
List<Integer>
l = getRemainingBalls();
if
(knowledge.countState(l, BallState.UNKNOWN) < l.size()) {
if (increasePanel(rightPan)) {
return
true;
} else {
rightPan.clear();
if
(increasePanel(leftPan)) {
List<Integer> look = sortBalls();
look.removeAll(leftPan);
rightPan.addAll(look.subList(0,
leftPan.size()));
return true;
}
else {
leftPan.clear();
}
}
}
return
false;
}
public boolean
nextTransition() {
int size;
if
(leftPan.size() == 0) {
size = 1;
generateForSize(size);
} else {
size = leftPan.size();
if (!increaseTransition()) {
size++;
if
(size < knowledge.getTotalBalls() / 2) {
generateForSize(size);
}
else {
return false;
}
}
}
while (!isCanonical())
{
if (!increaseTransition()) {
size++;
if
(size < knowledge.getTotalBalls() / 2) {
generateForSize(size);
}
else {
return false;
}
}
}
return
true;
}
public int
getSize() {
return
leftPan.size();
}
@Override
public Transition
clone() {
return new
Transition(leftPan, rightPan, knowledge);
}
@Override
public String
toString() {
return
getComparedBalls().toString();
}
}