--- jsr166/src/test/loops/Microscope.java 2010/09/19 12:55:37 1.1 +++ jsr166/src/test/loops/Microscope.java 2010/09/20 20:42:37 1.2 @@ -18,7 +18,7 @@ import java.util.concurrent.*; * See * Microscope version for instructions. *

- * The code has been mangled beyond recognition + * The code has been mangled beyond recognition * as a test of ForkJoin **/ @@ -72,13 +72,13 @@ public class Microscope extends JPanel { System.exit(0); } - static void onExit() { + static void onExit() { long now = System.currentTimeMillis(); System.out.println("time: " + (now - startTime) + "ms"); System.out.println(group.toString()); System.exit(0); - } - + } + static void oneRun() { if (java.awt.GraphicsEnvironment.isHeadless()) { headless = true; @@ -89,7 +89,7 @@ public class Microscope extends JPanel { JFrame frame = new JFrame(); frame.addWindowListener(new WindowAdapter() { public void windowClosing(WindowEvent e) {onExit();}}); - + Microscope t = new Microscope(); frame.setSize(new Dimension(400, 400)); frame.getContentPane().add(t); @@ -104,11 +104,11 @@ public class Microscope extends JPanel { Board board = new Board(); // The current board representation synchronized Board getBoard() { return board; } - synchronized void setBoard(Board b) { - board = b; + synchronized void setBoard(Board b) { + board = b; System.out.print(b.score(player) + " "); if (boardPanel != null) - boardPanel.repaint(); + boardPanel.repaint(); } Player player = Player.Blue; // current player (BLUE, GREEN) @@ -140,7 +140,7 @@ public class Microscope extends JPanel { JButton modeButton; JSlider levelSlider; - public Microscope() { + public Microscope() { if (headless) { boardPanel = null; auto = new AutoMover(this); @@ -166,7 +166,7 @@ public class Microscope extends JPanel { } else { stopMover(); - if (getDemoMode()) + if (getDemoMode()) autoButton.setText(" Start "); else autoButton.setText(" Find "); @@ -184,7 +184,7 @@ public class Microscope extends JPanel { public void actionPerformed(ActionEvent e) { undo(); }}); - + levelSlider.addChangeListener(new ChangeListener() { public void stateChanged(ChangeEvent e) { setLevel(((JSlider)(e.getSource())).getValue()); @@ -194,14 +194,14 @@ public class Microscope extends JPanel { // Dimension labDim = new Dimension(72, 24); // scoreLabel.setMinimumSize(labDim); // scoreLabel.setPreferredSize(labDim); - + topPanel.add(autoButton); topPanel.add(modeButton); topPanel.add(undoButton); topPanel.add(scoreLabel); add(topPanel); - + levelSlider.setLabelTable(levelSlider.createStandardLabels(1)); levelSlider.setPaintLabels(true); @@ -215,7 +215,7 @@ public class Microscope extends JPanel { sliderPanel.add(new JLabel("Level")); botPanel.add(sliderPanel); - + add(botPanel); } @@ -242,14 +242,14 @@ public class Microscope extends JPanel { lookAheads = l; if (lookAheads <= 1) lookAheads = 2; } - + public int level () { return Microscope.lookAheads; } - + // process a move (called only from mover) public void move(Move m, Mover mvr) { - if (mvr != mover || + if (mvr != mover || m == null || (mvr == user && !m.isLegal())) { setMover(null); @@ -265,8 +265,8 @@ public class Microscope extends JPanel { history.addElement(m); - if (mvr == auto && - getDemoMode() && + if (mvr == auto && + getDemoMode() && !m.isPass()) { if (getBoard().gameOver()) { if (autostart) { @@ -303,7 +303,7 @@ public class Microscope extends JPanel { mvr.cancel(); } } - + // handle Undo button synchronized void undo() { @@ -326,7 +326,7 @@ public class Microscope extends JPanel { startMover(user); user.choose(row, col); } - + void updateStatus() { // normally called from board update Player p = getPlayer(); int s = getBoard().score(p); @@ -334,11 +334,11 @@ public class Microscope extends JPanel { System.out.print(s + " "); return; } - + scoreLabel.setForeground(displayColor(p)); scoreLabel.setText("Score: " + s); - if (getDemoMode()) + if (getDemoMode()) modeButton.setText("Demo mode"); else { if (getPlayer().isBlue()) @@ -350,13 +350,13 @@ public class Microscope extends JPanel { } - static final int CELL_SIZE = 40; // size of a tile/cell - + static final int CELL_SIZE = 40; // size of a tile/cell + static final Color paleGreen = new Color(152, 251, 152); static final Color darkGreen = new Color(60, 179, 113); - + static final Color possibleMoveColor = Color.yellow; - + public static Color displayColor(Player pl) { if (pl.isBlue()) return Color.blue; @@ -372,64 +372,64 @@ public class Microscope extends JPanel { class BoardPanel extends Canvas implements MouseListener { - - BoardPanel() { - setSize(new Dimension(Board.RANKS * CELL_SIZE + 5, + + BoardPanel() { + setSize(new Dimension(Board.RANKS * CELL_SIZE + 5, Board.RANKS * CELL_SIZE + 5)); addMouseListener(BoardPanel.this); } - + public void paint(Graphics g) { - + Board b = getBoard(); Player p = getPlayer(); - + // the cells for (int row = 0; row < Board.RANKS; row++) { for (int col = 0; col < Board.RANKS; col++) { - + // Highlight selected tile and legal destinations if (user.placing()) { - if (user.hasMovedFrom(row, col)) + if (user.hasMovedFrom(row, col)) g.setColor(lightDisplayColor(p)); else if (user.canMoveTo(row, col)) g.setColor(possibleMoveColor); else g.setColor(displayColor(b.occupant(row, col))); } - + else g.setColor(displayColor(b.occupant(row, col))); - + // tiles are just filled rectangles g.fillRect(row * CELL_SIZE, col * CELL_SIZE, CELL_SIZE, CELL_SIZE); } } - + // the grid over the cells g.setColor(Color.black); for ( int i = 0; i <= Board.RANKS; i++) { g.drawLine(0, i * CELL_SIZE, Board.RANKS * CELL_SIZE, i * CELL_SIZE); g.drawLine(i * CELL_SIZE, 0, i * CELL_SIZE, Board.RANKS * CELL_SIZE); } - + updateStatus(); } - + public void mouseReleased(MouseEvent evt) { - + int x = evt.getX(); int y = evt.getY(); - + int row = x / CELL_SIZE; int col = y / CELL_SIZE; - + if (Board.inBounds(row, col)) { // cell selection userMove(row, col); repaint(); } } - + public void mouseClicked(MouseEvent e) {} public void mousePressed(MouseEvent e) {} public void mouseEntered(MouseEvent e) {} @@ -446,32 +446,32 @@ public class Microscope extends JPanel { public static final int BLUE = 1; public static final int GREEN = 2; public static final int ILLEGAL_PLAYER_VALUE = 3; - + public static final Player Empty = new Player(EMPTY); public static final Player Blue = new Player(BLUE); public static final Player Green = new Player(GREEN); public static final Player Illegal = new Player(ILLEGAL_PLAYER_VALUE); - + /* private */ int code_; - + public Player(int code) { code_ = code; } public Player(Player p) { code_ = p.code_; } - + public boolean same(Player p) { return code_ == p.code_; } - + public boolean isEmpty() { return code_ == EMPTY; } public boolean isBlue() { return code_ == BLUE; } public boolean isGreen() { return code_ == GREEN; } public boolean isLegal() { return code_ <= GREEN; } - - public Player opponent() { + + public Player opponent() { if (code_ == GREEN) return Blue; else if (code_ == BLUE) return Green; else return Illegal; } - + } - + /** * Board configurations are represented by bit vectors. * Since there are only 49 cells, the bits can be held in `longs', @@ -481,24 +481,24 @@ public class Microscope extends JPanel { * threads (instead new ones are constructed), so don't * need any synch. **/ - + static final class Board { - /* + /* First, some Constants and utilities that might as well be here */ - + public static final int RANKS = 7; public static final int CELLS = RANKS * RANKS; - + static final long FULL = (1L << CELLS) - 1; - + // The finder uses a spare bit to remember whose move it is. static final long BLUEBIT = (1L << CELLS); - + // Bits representing the adjacent cells for every position static final long[] adjacentMasks = new long[CELLS]; - + // bit pattern associated with each tile static final long[] cellBits = new long[CELLS]; @@ -537,32 +537,32 @@ public class Microscope extends JPanel { } } - - + + public static boolean inBounds(int row, int col) { return (0 <= row) && (row < RANKS) && (0 <= col) && (col < RANKS); } - + // The representation - + long blue_; // bit vector; true if occupied by blue long green_; // same for green; - + // constructors and intializers: - + public Board() { blue_ = 0L; green_ = 0L; } public Board(Board b) { blue_ = b.blue_; green_ = b.green_; } public Board(long b, long g) { blue_ = b; green_ = g; } - + public void copyState(Board b) { - blue_ = b.blue_; - green_ = b.green_; + blue_ = b.blue_; + green_ = b.green_; } - void reset() { - blue_ = 0L; green_ = 0L; + void reset() { + blue_ = 0L; green_ = 0L; } - + long getBlue() { return blue_; } long getGreen() { return green_; } @@ -577,37 +577,37 @@ public class Microscope extends JPanel { else return Player.Illegal; } - - + + // place a tile without taking opponent tiles - + public void occupy(Player player, int row, int col) { long m = 1L << (row + col * RANKS); long nm = ~m; - if (player.code_ == Player.BLUE) { + if (player.code_ == Player.BLUE) { blue_ |= m; green_ &= nm; } - else if (player.code_ == Player.GREEN) { + else if (player.code_ == Player.GREEN) { blue_ &= nm; green_ |= m; } - else { + else { blue_ &= nm; green_ &= nm; } } - + public void unoccupy(int row, int col) { long nm = ~(1L << (row + col * RANKS)); blue_ &= nm; green_ &= nm; } - - - + + + // place a tile, taking all adjacent tiles of opponent - + public void take(Player player, int row, int col) { int k = (row + col * RANKS); long dest = 1L << k; @@ -623,15 +623,15 @@ public class Microscope extends JPanel { green_ = sourceGreen | dest | (sourceBlue & nbrMask); } } - + public boolean gameOver() { - return + return (((blue_ | green_) & FULL) == FULL) || ((blue_ & ~BLUEBIT) == 0) || ((green_ & ~BLUEBIT) == 0); } - - + + public int score(Player player) { if (player.isBlue()) { return score(blue_, green_); @@ -640,12 +640,12 @@ public class Microscope extends JPanel { return score(green_, blue_); } } - + static int score(long b, long g) { - + // much faster by splitting into ints // and using clever shift-based bit counter - + int lb = (int)(b & ((1L << 32) - 1)); int hb = ((int)(b >>> 32)) & ((1 << (CELLS - 32)) - 1); @@ -680,9 +680,9 @@ public class Microscope extends JPanel { return hb - ((lg + hg) & 0xff); } - - - + + + static int slowscore(long b, long g) { int score = 0; for (int l = 0; l < CELLS; ++l) { @@ -693,10 +693,10 @@ public class Microscope extends JPanel { } return score; } - - + + } - + /** * Moves represent transitions across Board states **/ @@ -706,118 +706,118 @@ public class Microscope extends JPanel { static final int NO_VALUE = -1; // row/col value if not yet set static final int PASS_VALUE = -2; // special value for pass moves - + // utilities for classifying moves - - public static boolean twoFrom(int a, int b) { - return (a - b == 2) || (b - a == 2); + + public static boolean twoFrom(int a, int b) { + return (a - b == 2) || (b - a == 2); } - - public static boolean withinTwo(int a, int b) { + + public static boolean withinTwo(int a, int b) { int diff = a - b; return -2 <= diff && diff <= 2; } - + // representations - + int fromRow; int fromCol; - + int toRow; int toCol; - + Player player_; Board board_; - + boolean committed = false; // true if board reflects move - + // constructors and intializers - - public Move(Player turn, Board board) { + + public Move(Player turn, Board board) { fromRow = NO_VALUE; fromCol = NO_VALUE; toRow = NO_VALUE; toCol = NO_VALUE; player_ = turn; board_ = board; } - - public Move(Player turn, Board board, boolean isCommitted) { + + public Move(Player turn, Board board, boolean isCommitted) { fromRow = NO_VALUE; fromCol = NO_VALUE; toRow = NO_VALUE; toCol = NO_VALUE; player_ = turn; board_ = board; committed = isCommitted; } - + synchronized void reset() { fromRow = NO_VALUE; fromCol = NO_VALUE; toRow = NO_VALUE; toCol = NO_VALUE; } - + // setters: - + synchronized void player(Player p) { player_ = p; } synchronized void board(Board b) { board_ = b; } synchronized void from(int sr, int sc) { fromRow = sr; fromCol = sc; } synchronized void to(int dr, int dc) { toRow = dr; toCol = dc; } - + // accessors: - - synchronized boolean isFrom(int r, int c) { - return fromRow== r && fromCol == c; + + synchronized boolean isFrom(int r, int c) { + return fromRow== r && fromCol == c; } - synchronized boolean isTo(int r, int c) { - return toRow == r && toCol == c; + synchronized boolean isTo(int r, int c) { + return toRow == r && toCol == c; } - synchronized Board board() { - return board_; + synchronized Board board() { + return board_; } - synchronized Player player() { - return player_; + synchronized Player player() { + return player_; } - + // status checks: - + synchronized boolean isPass() { // is this a `pass' move? return (toRow == PASS_VALUE || fromRow == PASS_VALUE); } - + synchronized boolean isJump() { - return + return (fromRow - toRow == 2) || (toRow - fromRow == 2) || (fromCol - toCol == 2) || (toCol - fromCol == 2); } - + synchronized boolean hasFrom() { // is from set? return fromRow != NO_VALUE && fromCol != NO_VALUE; } - + synchronized boolean hasTo() { // is to set? return toRow != NO_VALUE && toCol != NO_VALUE; } - - + + synchronized boolean possibleTo(int r, int c) { // is (r, c) a legal `to'? return hasFrom() && withinTwo(fromRow, r) && withinTwo(fromCol, c) && board_.occupant(r, c).isEmpty(); } - + synchronized boolean isLegal() { - if (isPass()) + if (isPass()) return true; - else if (!board_.occupant(toRow, toCol).isEmpty()) + else if (!board_.occupant(toRow, toCol).isEmpty()) return false; - else if (!board_.occupant(fromRow, fromCol).same(player_)) + else if (!board_.occupant(fromRow, fromCol).same(player_)) return false; - else if (!(withinTwo(fromRow, toRow) && withinTwo(fromCol, toCol))) + else if (!(withinTwo(fromRow, toRow) && withinTwo(fromCol, toCol))) return false; else return true; } - + synchronized void commit() { // update board to reflect move if (!committed) { committed = true; @@ -827,33 +827,33 @@ public class Microscope extends JPanel { } } } - + } - + /** * Mover is an abstract class to simplify code dealing with * either user moves or auto moves. **/ - + static abstract class Mover { - + // caller for move callbacks protected Microscope game; - + protected Mover(Microscope ap) { game = ap; } - + // start a turn as player on given board public abstract void startTurn(Board b, Player p); - + // cancel current partial move public abstract void cancel(); - + // return true if move not yet ready public abstract boolean placing(); - + } - + /** * User builds moves via instructions/clicks by users **/ @@ -861,24 +861,24 @@ public class Microscope extends JPanel { static class User extends Mover { private Move current; - + public User(Microscope ap) { super(ap); current = null; } - + public synchronized void startTurn(Board b, Player p) { current = new Move(p, b); } - - public boolean placing() { - return current != null && current.hasFrom() && !current.hasTo(); + + public boolean placing() { + return current != null && current.hasFrom() && !current.hasTo(); } - - public synchronized void cancel() { + + public synchronized void cancel() { if (current != null) { - current.reset(); - current = null; + current.reset(); + current = null; } } - + public synchronized void choose(int row, int col) { if (current != null) { if (row == Move.PASS_VALUE) { @@ -898,15 +898,15 @@ public class Microscope extends JPanel { } } } - + public synchronized boolean canMoveTo(int row, int col) { return placing() && current.possibleTo(row, col); } - + public synchronized boolean hasMovedFrom(int row, int col) { return current != null && current.isFrom(row, col); } - + } @@ -922,19 +922,19 @@ public class Microscope extends JPanel { public AutoMover(Microscope ap) { super(ap); } - - - public synchronized boolean placing() { - return currentFinder != null; + + + public synchronized boolean placing() { + return currentFinder != null; } - synchronized void stopPlacing() { + synchronized void stopPlacing() { currentFinder = null; } - - + + public synchronized void cancel() { - if (placing()) { + if (placing()) { currentFinder.cancel(false); stopPlacing(); } @@ -942,21 +942,21 @@ public class Microscope extends JPanel { public synchronized void startTurn(Board board, Player player) { if (!placing()) { - currentFinder = new RootFinder(board, player, + currentFinder = new RootFinder(board, player, Microscope.lookAheads, this); group.execute(currentFinder); } } - + synchronized void relay(Move move) { // relay callback from finder if (placing()) { stopPlacing(); game.move(move, this); } } - + } - + /** * Implements a classic all-possible-move search algorith using @@ -967,13 +967,13 @@ public class Microscope extends JPanel { * be changed to prune moves, although this is unlikely to work * well without better partial evaluation functions. **/ - + static class Finder extends RecursiveAction { static final int NOMOVE = Integer.MIN_VALUE; static final int LOSE = NOMOVE+1; static final int WIN = -LOSE; - + final long ours; // bits for our tiles final long theirs; // bits for opponent tiles final int level; // current number of lookAheads @@ -992,10 +992,10 @@ public class Microscope extends JPanel { protected final void compute() { // Handle sure wins and losses here - if ((ours & ~Board.BLUEBIT) == 0) + if ((ours & ~Board.BLUEBIT) == 0) bestScore = LOSE; - else if ((theirs & ~Board.BLUEBIT) == 0) + else if ((theirs & ~Board.BLUEBIT) == 0) bestScore = WIN; else if (((ours | theirs) & Board.FULL) == Board.FULL) { @@ -1005,18 +1005,18 @@ public class Microscope extends JPanel { else bestScore = 0; } - else + else search(); } - + final void search() { int best = NOMOVE; // For direct evaluation when level == 1 Finder forked = null; // list of forked subtasks when level > 1 - + long open = ~(ours | theirs); // currently empty cells long here = 1; // travserse through bits - + for (int k = 0; k < Board.CELLS; ++k, here <<= 1) { if ((here & ours) != 0) { /* @@ -1027,14 +1027,14 @@ public class Microscope extends JPanel { for (int j = 0; j < dests.length; ++j) { byte d = dests[j]; long dest = 1L << d; - + if ( (dest & open) != 0) { long adjacent = Board.adjacentMasks[d]; long nTheirs = theirs & ~adjacent; long nOurs = (ours & ~here) | dest | (theirs & adjacent); - if (level > 1) - (forked = + if (level > 1) + (forked = new Finder(nTheirs, nOurs, level-1, forked)).fork(); else { int sc = Board.score(nOurs, nTheirs); @@ -1054,7 +1054,7 @@ public class Microscope extends JPanel { if ((ours & adjacent) != 0) { long nTheirs = theirs & ~adjacent; long nOurs = ours | here | (theirs & adjacent); - if (level > 1) + if (level > 1) (forked = new Finder(nTheirs, nOurs, level-1, forked)).fork(); else { int sc = Board.score(nOurs, nTheirs); @@ -1078,8 +1078,8 @@ public class Microscope extends JPanel { void collect(Finder forked) { int best = NOMOVE; while (forked != null) { - while (!forked.isDone()) { - // interleave joins with status checks + while (!forked.isDone()) { + // interleave joins with status checks if (isDone()) { cancelAll(forked); return; @@ -1122,14 +1122,14 @@ public class Microscope extends JPanel { **/ static class RootFinder extends Finder { - final AutoMover automover; + final AutoMover automover; final Player player; RootFinder(Board board, Player p, int level, AutoMover automover) { super( (p.isBlue()? (board.getBlue()| Board.BLUEBIT) : board.getGreen()), (p.isBlue()? board.getGreen() : (board.getBlue()| Board.BLUEBIT)), level, null); - + this.player = p; this.automover = automover; } @@ -1163,26 +1163,26 @@ public class Microscope extends JPanel { break; } } - + // Just for fun, introduce a little randomness via hashcodes else if (score == best && !Microscope.DETERMINISTIC && - (System.identityHashCode(forked) > + (System.identityHashCode(forked) > System.identityHashCode(bestFinder))) { bestFinder = forked; } forked = forked.next; } - + Move move = null; if (bestFinder != null) { - /* + /* Even though accessed here, the ours and theirs vars of Finders do not need to be volatile because they are immutably established in constructors. */ - + long nextOurs = bestFinder.theirs; long nextTheirs = bestFinder.ours; long blue = (player.isBlue())? nextOurs : nextTheirs; @@ -1193,5 +1193,5 @@ public class Microscope extends JPanel { } } - + }