/*
* tc.catseye.yoob.YpsilaxState -- Ypsilax for yoob
* The source code in this file has been placed into the public domain.
*/
/*
* A tc.catseye.yoob.YpsilaxState tries to implement the semantics of the
* Ypsilax grid-rewriter, for running under the yoob framework.
*/
package tc.catseye.yoob.ypsilax;
import tc.catseye.yoob.Error;
import tc.catseye.yoob.*;
import java.util.List;
import java.util.ArrayList;
import java.util.Set;
import java.util.HashSet;
import java.util.Map;
import java.util.HashMap;
import java.util.Random;
import java.util.Iterator;
class Ypsilax implements Language {
public String getName() {
return "Ypsilax";
}
public int numPlayfields() {
return 1;
}
public int numTapes() {
return 0;
}
public boolean hasProgramText() {
return false;
}
public boolean hasInput() {
return false;
}
public boolean hasOutput() {
return false;
}
public List<String> exampleProgramNames() {
ArrayList<String> names = new ArrayList<String>();
names.add("transform it");
names.add("classic example");
names.add("abracadabra");
names.add("escaped");
names.add("multisymbol pattern");
names.add("grow tape");
names.add("wildcard");
//names.add("higher-order");
names.add("self-modifying");
return names;
}
public YpsilaxState loadExampleProgram(int index) {
String[][] program = {
{
"DDDD",
"",
"( )",
" D* ",
"",
"DDDD",
},
{
"( ) ( )",
" # #",
" # ### ### #",
" # #",
"",
" ### ###",
"",
" # #",
" # #",
" # ###",
},
{
"( ) ( )",
" AB BA",
"ABRACADABRA",
},
{
"* ",
"( ) ( )",
" AB BA",
"ABRACADABRA",
},
{
"( )",
" ABBA",
" ^^ ",
"ABRACADABRA",
"^^^^^^^^^^^",
},
{
"( )",
" > -> ",
" > -> ",
" > -> ",
"",
"---->",
"---->",
"---->",
},
{
"( ?)",
" A?AX",
"",
"ABRACADABRA",
"",
"...........",
},/*
{
"( ?) ",
"",
"",
" ? ?",
" ----( )",
"",
"",
"",
" -------------",
" ABRACADABRA",
"",
"",
" ABRACADABRA",
},*/
{
"(X X ) (X X )",
" ( )( ) ( )( )",
" AB BA BA AB",
"",
"",
" ( )",
" AB",
"",
"",
" ABRACADABRA",
},
};
YpsilaxState s = new YpsilaxState();
s.playfield.load(program[index]);
return s;
}
public YpsilaxState importFromText(String text) {
YpsilaxState s = new YpsilaxState();
s.playfield.load(text.split("\\r?\\n"));
return s;
}
public List<String> getAvailableOptionNames() {
ArrayList<String> names = new ArrayList<String>();
return names;
}
private static final String[][] properties = {
{"Author", "Chris Pressey"},
{"Implementer", "Chris Pressey"},
{"Implementation notes",
"In this version, patterns detected in the playfield are always within the " +
"current bounds of the playfield; in other words, even if the pattern contains " +
"spaces or wildcards, it will not match the assumed-empty space surrounding " +
"the defined part of the playfield."},
};
public String[][] getProperties() {
return properties;
}
}
class Rule extends OverlayPlayfield<CharacterElement> {
private IntegerElement width, height;
private CharacterElement wildcard;
private static final IntegerElement TWO = new IntegerElement(2);
public Rule(Playfield<CharacterElement> p, IntegerElement x, IntegerElement y,
IntegerElement width, CharacterElement wildcard) {
super(p, x, y, width, width.divide(TWO));
this.width = width;
this.height = width.divide(TWO);
this.wildcard = wildcard;
}
public Rule(Playfield<CharacterElement> p, IntegerElement x, IntegerElement y,
IntegerElement width, IntegerElement height, CharacterElement wildcard) {
super(p, x, y, width, height);
this.width = width;
this.height = height;
this.wildcard = wildcard;
}
public Rule createMatchSubject() {
return new Rule(getPlayfield(), getOffsetX(), getOffsetY(),
getHeight(), getHeight(), getWildcard());
}
public IntegerElement getWidth() {
return width;
}
public IntegerElement getHeight() {
return height;
}
public CharacterElement getWildcard() {
return wildcard;
}
// This should be a method on a Dumper object which takes a Codec.
public String dump() {
IntegerElement min_x = getMinX();
IntegerElement min_y = getMinY();
IntegerElement max_x = getMaxX();
IntegerElement max_y = getMaxY();
IntegerElement x = min_x;
IntegerElement y = min_y;
StringBuffer buf = new StringBuffer();
//System.out.println("(" + getOffsetX() + "," + getOffsetY() + ")_(" + width + "x" + height + ")");
while (y.compareTo(max_y) <= 0) {
x = min_x;
while (x.compareTo(max_x) <= 0) {
CharacterElement e = get(x, y);
buf.append(dumpElement(e));
x = x.succ();
}
y = y.succ();
buf.append("\n");
}
return buf.toString();
}
public String dumpElement(CharacterElement e) {
return e.getName();
}
}
class WildcardMatcher implements Matcher<CharacterElement,CharacterElement> {
private CharacterElement wildcard;
public WildcardMatcher(CharacterElement wildcard) {
this.wildcard = wildcard;
}
public boolean match(CharacterElement sought, CharacterElement candidate) {
if (wildcard != null && sought.getChar() == wildcard.getChar()) {
return true;
}
return candidate.equals(sought);
}
}
class PlayfieldMatcher<E extends Element> {
public boolean isMatchAt(Playfield<E> haystack, Playfield<E> needle, Matcher<E,E> m, IntegerElement x, IntegerElement y) {
IntegerElement width = needle.getMaxX().subtract(needle.getMinX()).succ();
IntegerElement height = needle.getMaxY().subtract(needle.getMinY()).succ();
if (x.pred().add(width).compareTo(haystack.getMaxX()) > 0 ||
y.pred().add(height).compareTo(haystack.getMaxY()) > 0) {
// exceeds the right or bottom edge, so, no
return false;
}
IntegerElement cx, cy, dx, dy;
for (cx = x, dx = needle.getMinX();
dx.compareTo(needle.getMaxX()) <= 0;
cx = cx.succ(), dx = dx.succ()) {
for (cy = y, dy = needle.getMinY();
dy.compareTo(needle.getMinY()) <= 0;
cy = cy.succ(), dy = dy.succ()) {
E soughtElem = needle.get(dx, dy);
E foundElem = haystack.get(cx, cy);
//System.out.printf("sought (%s,%s): '%s', found (%s,%s): '%s'\n",
// dx, dy, soughtElem.getName(),
// cx, cy, foundElem.getName());
if (m.match(soughtElem, foundElem)) {
// add something to the result-list
} else {
return false;
}
}
}
return true;
}
public Set<Position> getAllMatches(Playfield<E> haystack, Playfield<E> needle, Matcher<E,E> matcher) {
Set<Position> results = new HashSet<Position>();
IntegerElement haystackWidth = haystack.getMaxX().subtract(haystack.getMinX()).succ();
IntegerElement haystackHeight = haystack.getMaxY().subtract(haystack.getMinY()).succ();
IntegerElement needleWidth = needle.getMaxX().subtract(needle.getMinX()).succ();
IntegerElement needleHeight = needle.getMaxY().subtract(needle.getMinY()).succ();
if (needleWidth.compareTo(haystackWidth) > 0 || needleHeight.compareTo(haystackHeight) > 0) {
// thing being sought is larger than the thing seeking in, so, no
return results;
}
IntegerElement xSpan = haystackWidth.subtract(needleWidth).succ();
IntegerElement ySpan = haystackHeight.subtract(needleHeight).succ();
IntegerElement x, y;
for (x = IntegerElement.ZERO; x.compareTo(xSpan) < 0; x = x.succ()) {
for (y = IntegerElement.ZERO; y.compareTo(ySpan) < 0; y = y.succ()) {
if (isMatchAt(haystack, needle, matcher, x, y)) {
results.add(new Position(x, y));
} else {
}
}
}
return results;
}
}
class YpsilaxPlayfield extends BasicPlayfield<CharacterElement> {
public YpsilaxPlayfield() {
super(new CharacterElement(' '));
}
public YpsilaxPlayfield clone() {
YpsilaxPlayfield c = new YpsilaxPlayfield();
c.copyBackingStoreFrom(this);
return c;
}
public List<Position> match(YpsilaxPlayfield pattern) {
return null;
}
public List<Rule> findAllRules() {
IntegerElement x, y;
ArrayList<Rule> rules = new ArrayList<Rule>();
for (x = (IntegerElement)getMinX(); x.compareTo(getMaxX()) <= 0; x = x.succ()) {
for (y = (IntegerElement)getMinY(); y.compareTo(getMaxY()) <= 0; y = y.succ()) {
boolean escaped = (!y.isZero() && get(x, y.pred()).getChar() != ' ');
if (escaped) continue;
if (get(x, y).getChar() == '(') {
//System.out.println("Found a rule start at " + x + ", " + y);
IntegerElement x2 = x;
CharacterElement g = get(x2, y);
while (g.getChar() != ')' && x2.compareTo(getMaxX()) <= 0) {
x2 = x2.succ();
g = get(x2, y);
}
if (g.getChar() != ')') continue;
//System.out.println("Found a rule from " + x + "," + y + " to " + x2);
CharacterElement w = get(x2.pred(), y);
if (w.getChar() == ' ') w = null;
Rule r = new Rule(this, x.succ(), y.succ(), (x2.subtract(x)).pred(), w);
rules.add(r);
}
}
}
return rules;
}
public List<Position> findAllRuleMatches(Rule r) {
//System.out.printf("%s", r.dump());
WildcardMatcher matcher = new WildcardMatcher(r.getWildcard());
PlayfieldMatcher<CharacterElement> pm = new PlayfieldMatcher<CharacterElement>();
List<Position> positions = new ArrayList<Position>();
// We only want to match the LEFT side of the rule, so we do this:
Rule matchSubject = r.createMatchSubject();
for (Position p : pm.getAllMatches(this, matchSubject, matcher)) {
// System.out.println("CONSIDERING (" + p.getX() + "," + p.getY() + ")");
// Discard all the ones that are at or above the rule
if (p.getY().compareTo(r.getOffsetY().add(r.getHeight())) >= 0) {
//System.out.println("(" + p.getX() + "," + p.getY() + ")..." + r.getOffsetY());
positions.add(p);
}
}
//System.out.println("---");
return positions;
}
/*
* We assume a match was made at the given position.
*/
public void applyRule(Rule r, Position p) {
IntegerElement i, j;
CharacterElement wildcard = r.getWildcard();
//System.out.printf("applying at %s: %s", p.toString(), r.dump());
/* Note that r.getHeight() == width/2 ... */
for(i = IntegerElement.ZERO; i.compareTo(r.getHeight()) < 0; i = i.succ()) {
for(j = IntegerElement.ZERO; j.compareTo(r.getHeight()) < 0; j = j.succ()) {
CharacterElement replacement = r.get(i.add(r.getHeight()), j);
IntegerElement destX = p.getX().add(i);
IntegerElement destY = p.getY().add(j);
//System.out.printf("(%s,%s): [%s] '%s' -> (%s,%s)\n", i, j, wildcard, replacement.getChar(), destX, destY);
if (wildcard == null || wildcard.getChar() != replacement.getChar()) {
set(destX, destY, replacement);
}
}
}
}
}
public class YpsilaxState implements tc.catseye.yoob.State {
protected YpsilaxPlayfield playfield;
protected BasicPlayfieldView view;
private Random rand;
private static final Ypsilax language = new Ypsilax();
private boolean halted = false;
public YpsilaxState() {
playfield = new YpsilaxPlayfield();
view = new BasicPlayfieldView();
rand = new Random();
}
public YpsilaxState clone() {
YpsilaxState c = new YpsilaxState();
c.playfield = this.playfield.clone();
return c;
}
public Language getLanguage() {
return language;
}
public List<Error> step(World world) {
ArrayList<Error> errors = new ArrayList<Error>();
List<Rule> rules = playfield.findAllRules();
if (rules.size() == 0) {
// no sense continuing. halt.
halted = true;
return errors;
}
//System.out.println("rules: " + rules.size());
Rule r = rules.get(rand.nextInt(rules.size()));
List<Position> positions = playfield.findAllRuleMatches(r);
//System.out.println("matches: " + positions.size());
if (positions.size() > 0) {
Position p = positions.get(rand.nextInt(positions.size()));
playfield.applyRule(r, p);
}
return errors;
}
public Playfield getPlayfield(int index) {
return playfield;
}
public Tape getTape(int index) {
return null;
}
public String getProgramText() {
return "";
}
public int getProgramPosition() {
return 0;
}
public List<Error> setProgramText(String text) {
ArrayList<Error> errors = new ArrayList<Error>();
return errors;
}
public View getPlayfieldView(int index) {
return view;
}
public View getTapeView(int index) {
return null;
}
public void setOption(String name, boolean value) {
}
public String exportToText() {
return playfield.dump();
}
public boolean needsInput() {
return false;
}
public boolean hasHalted() {
return halted;
}
}