SHARE
TWEET

Model.jaba

a guest Sep 22nd, 2019 110 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package signpost;
  2.  
  3. import java.util.ArrayList;
  4. import java.util.BitSet;
  5. import java.util.Formatter;
  6. import java.util.HashSet;
  7. import java.util.Iterator;
  8. import java.util.Arrays;
  9.  
  10. import static signpost.Place.*;
  11. import static signpost.Utils.*;
  12.  
  13. /** The state of a Signpost puzzle.  Each cell has coordinates (x, y),
  14.  *  where 0 <= x < width(),  0 <= y < height().  The upper-left corner of
  15.  *  the puzzle has coordinates (0, height() - 1), and the lower-right corner
  16.  *  is at (width() - 1, 0).
  17.  *
  18.  *  A constructor initializes the squares according to a particular
  19.  *  solution.  A solution is an assignment of sequence numbers from 1 to
  20.  *  size() == width() * height() to square positions so that squares with
  21.  *  adjacent numbers are separated by queen moves. A queen move is a move from
  22.  *  one square to another horizontally, vertically, or diagonally. The effect
  23.  *  is to give each square whose number in the solution is less than
  24.  *  size() an <i>arrow direction</i>, 1 <= d <= 8, indicating the direction
  25.  *  of the next higher numbered square in the solution: d * 45 degrees clockwise
  26.  *  from straight up (i.e., toward higher y coordinates).  The highest-numbered
  27.  *  square has direction 0.  Certain squares can have their values fixed to
  28.  *  those in the solution. Initially, the only two squares with fixed values
  29.  *  are those with the lowest and highest sequence numbers in the solution.
  30.  *
  31.  *  At any given time after initialization, a square whose value is not fixed
  32.  *  may have an unknown value, represented as 0, or a tentative number (not
  33.  *  necessarily that of the solution) between 1 and size(). Squares may be
  34.  *  connected together, indicating that their sequence numbers (unknown or not)
  35.  *  are consecutive.
  36.  *
  37.  *  When square S0 is connected to S1, we say that S1 is the <i>successor</i> of
  38.  *  S0, and S0 is the <i>predecessor</i> of S1.  Sequences of connected squares
  39.  *  with unknown (0) values form a <i>group</i>, identified by a unique
  40.  *  <i>group number</i>.  Numbered cells (whether linked or not) are in group 0.
  41.  *  Unnumbered, unlinked cells are in group -1.
  42.  *
  43.  *  Squares are represented as objects of the inner class Sq (Model.Sq).  A
  44.  *  Model object is itself iterable, yielding its squares in unspecified order.
  45.  *
  46.  *  The puzzle is solved when all cells are contained in a single sequence
  47.  *  of consecutively numbered cells (therefore all in group 0) and all cells
  48.  *  with fixed sequence numbers appear at the corresponding position
  49.  *  in that sequence.
  50.  *
  51.  *  @author
  52.  */
  53. class Model implements Iterable<Model.Sq> {
  54.  
  55.     /** A Model whose solution is SOLUTION, initialized to its starting,
  56.      *  unsolved state (where only cells with fixed numbers currently
  57.      *  have sequence numbers and no unnumbered cells are connected).
  58.      *  SOLUTION must be a proper solution:
  59.      *      1. It must have dimensions w x h such that w * h >= 2.
  60.      *      2. There must be a sequence of chess-queen moves such that
  61.      *         the sequence of values in the cells reached is 1, 2, ... w * h.
  62.      *  The contents of SOLUTION are copied into this Model, so that subsequent
  63.      *  changes to it have no effect on the Model.
  64.      */
  65.     Model(int[][] solution) {
  66.         if (solution.length == 0 || solution.length * solution[0].length < 2) {
  67.             throw badArgs("must have at least 2 squares");
  68.         }
  69.         _width = solution.length; _height = solution[0].length;
  70.         int last = _width * _height;
  71.         BitSet allNums = new BitSet();
  72.  
  73.         _allSuccessors = Place.successorCells(_width, _height);
  74.         _solution = new int[_width][_height];
  75.         deepCopy(solution, _solution);
  76.  
  77.         // DUMMY SETUP
  78.         // FIXME: Remove everything down "// END DUMMY SETUP".
  79.  
  80.         // END DUMMY SETUP
  81.  
  82.  
  83.         // FIXME: Initialize _board so that _board[x][y] contains the Sq object
  84.         //        representing the contents at cell (x, y), _allSquares
  85.         //        contains the list of all Sq objects on the board, and
  86.         //        _solnNumToPlace[k] contains the Place in _solution that
  87.         //        contains sequence number k.  Check that all numbers from
  88.         //        1 - last appear; else throw IllegalArgumentException (see
  89.         //        badArgs utility).
  90.  
  91.         _solnNumToPlace = new Place[_width*_height+1];
  92.         int check = 1;
  93.  
  94.         for (int k=1; k < _solnNumToPlace.length; k++){
  95.  
  96.             for (int i=0; i < _width; i++) {
  97.  
  98.                 for (int j = 0; j < _height; j++) {
  99.  
  100.                     if (_solution[i][j] == k){
  101.  
  102.                         _solnNumToPlace[k] = pl(i,j);
  103.                         check++;
  104.                     }
  105.                 }
  106.             }
  107.         }
  108.  
  109.         if ( _solnNumToPlace.length != check){
  110.  
  111.             throw badArgs("must contain all numbers");
  112.         }
  113.  
  114.  
  115.  
  116.          _board = new Sq[_width][_height];
  117.  
  118.          for (int i=0; i < _width; i++){
  119.              for (int j=0; j < _height; j++){
  120.  
  121.                  if (_solnNumToPlace[1].equals(pl(i,j)) || _solnNumToPlace[_solnNumToPlace.length-1].equals(pl(i,j)) ){
  122.                      _board[i][j] = new Sq(i,j,_solution[i][j],true, arrowDirection(i,j),0);
  123.                  }
  124.                  else{
  125.                      _board[i][j] = new Sq(i,j,0,false, arrowDirection(i,j),-1);
  126.                  }
  127.  
  128.              }
  129.          }
  130.  
  131.         for (int i=0; i < _width; i++){
  132.             for (int j=0; j < _height; j++){
  133.  
  134.                 _allSquares.add(_board[i][j]);
  135.             }
  136.         }
  137.  
  138.  
  139.  
  140.         // FIXME: For each Sq object on the board, set its _successors and
  141.         //        _predecessor lists to the lists of locations of all cells
  142.         //        that it might connect to (i.e., all cells that are a queen
  143.         //        move away in the direction of its arrow, and of all cells
  144.         //        that might connect to it.
  145.  
  146.         for(Sq each: _allSquares){
  147.  
  148.  
  149.  
  150.             each._successors = allSuccessors(each.x, each.y, each._dir);
  151.  
  152.  
  153.             //each._predecessors = allSuccessors(each.x, each.y, -each._dir);
  154.         }
  155.  
  156.         _unconnected = last - 1;
  157.     }
  158.  
  159.     /** Initializes a copy of MODEL. */
  160.     Model(Model model) {
  161.         _width = model.width(); _height = model.height();
  162.         _unconnected = model._unconnected;
  163.         _solnNumToPlace = model._solnNumToPlace;
  164.         _solution = model._solution;
  165.         _usedGroups.addAll(model._usedGroups);
  166.         _allSuccessors = model._allSuccessors;
  167.  
  168.         // FIXME: Initialize _board and _allSquares to contain copies of the
  169.         //        the Sq objects in MODEL other than their _successor,
  170.         //        _predecessor, and _head fields (which can't necessarily be
  171.         //        set until all the necessary Sq objects are first created.)
  172.  
  173.  
  174.         _board = new Sq[_width][_height];
  175.  
  176.         for (int i=0; i < _width; i++){
  177.             for (int j=0; j < _height; j++){
  178.  
  179.                 _board[i][j] = model._board[i][j];
  180.  
  181.             }
  182.         }
  183.  
  184.  
  185.         for (int i=0; i < _width; i++){
  186.             for (int j=0; j < _height; j++){
  187.  
  188.                 _allSquares.add(_board[i][j]);
  189.             }
  190.         }
  191.  
  192.  
  193.  
  194.         // FIXME: Fill in the _successor, _predecessor, and _head fields of the
  195.         //        copied Sq objects.
  196.     }
  197.  
  198.     /** Returns the width (number of columns of cells) of the board. */
  199.     final int width() {
  200.         return _width;
  201.     }
  202.  
  203.     /** Returns the height (number of rows of cells) of the board. */
  204.     final int height() {
  205.         return _height;
  206.     }
  207.  
  208.     /** Returns the number of cells (and thus, the sequence number of the
  209.      *  final cell). */
  210.     final int size() {
  211.         return _width * _height;
  212.     }
  213.  
  214.     /** Returns true iff (X, Y) is a valid cell location. */
  215.     final boolean isCell(int x, int y) {
  216.         return 0 <= x && x < width() && 0 <= y && y < height();
  217.     }
  218.  
  219.     /** Returns true iff P is a valid cell location. */
  220.     final boolean isCell(Place p) {
  221.         return isCell(p.x, p.y);
  222.     }
  223.  
  224.     /** Returns all cell locations that are a queen move from (X, Y)
  225.      *  in direction DIR, or all queen moves in any direction if DIR = 0. */
  226.     final PlaceList allSuccessors(int x, int y, int dir) {
  227.         return _allSuccessors[x][y][dir];
  228.     }
  229.  
  230.     /** Returns all cell locations that are a queen move from P in direction
  231.      *  DIR, or all queen moves in any direction if DIR = 0. */
  232.     final PlaceList allSuccessors(Place p, int dir) {
  233.         return _allSuccessors[p.x][p.y][dir];
  234.     }
  235.  
  236.     /** Initialize MODEL to an empty WIDTH x HEIGHT board with a null solution.
  237.      */
  238.     void init(int width, int height) {
  239.         if (width <= 0 || width * height < 2) {
  240.             throw badArgs("must have at least 2 squares");
  241.         }
  242.         _width = width; _height = height;
  243.         _unconnected = _width * _height - 1;
  244.         _solution = null;
  245.         _usedGroups.clear();
  246.         // FIXME: Initialize _board to contain nulls and clear all objects from
  247.         //        _allSquares.
  248.  
  249.         _board = new Sq[_width][_height];
  250.  
  251.         _allSquares = new ArrayList<Sq>();
  252.  
  253.  
  254.         // FIXME: Initialize _allSuccSquares so that _allSuccSquares[x][y][dir]
  255.         //        is a list of all the Places on the board that are a queen
  256.         //        move in direction DIR from (x, y) and _allSuccSquares[x][y][0]
  257.         //        is a list of all Places that are one queen move from in
  258.         //        direction from (x, y).
  259.  
  260.         _allSuccessors = successorCells(_width, _height);
  261.     }
  262.  
  263.     /** Remove all connections and non-fixed sequence numbers. */
  264.     void restart() {
  265.         for (Sq sq : this) {
  266.             sq.disconnect();
  267.         }
  268.         assert _unconnected == _width * _height - 1;
  269.     }
  270.  
  271.     /** Return the number array that solves the current puzzle (the argument
  272.      *  the constructor.  The result must not be subsequently modified.  */
  273.     final int[][] solution() {
  274.         return _solution;
  275.     }
  276.  
  277.     /** Return the position of the cell with sequence number N in my
  278.      *  solution. */
  279.     Place solnNumToPlace(int n) {
  280.         return _solnNumToPlace[n];
  281.     }
  282.  
  283.     /** Return the current number of unconnected cells. */
  284.     final int unconnected() {
  285.         return _unconnected;
  286.     }
  287.  
  288.     /** Returns true iff the puzzle is solved. */
  289.     final boolean solved() {
  290.         return _unconnected == 0;
  291.     }
  292.  
  293.     /** Return the cell at (X, Y). */
  294.     final Sq get(int x, int y) {
  295.         return _board[x][y];
  296.     }
  297.  
  298.     /** Return the cell at P. */
  299.     final Sq get(Place p) {
  300.         return p == null ? null : _board[p.x][p.y];
  301.     }
  302.  
  303.     /** Return the cell at the same position as SQ (generally from another
  304.      *  board), or null if SQ is null. */
  305.     final Sq get(Sq sq) {
  306.         return sq == null ? null : _board[sq.x][sq.y];
  307.     }
  308.  
  309.     /** Connect all numbered cells with successive numbers that as yet are
  310.      *  unconnected and are separated by a queen move.  Returns true iff
  311.      *  any changes were made. */
  312.     boolean autoconnect() {
  313.  
  314.         for (int x = 0; x < _width; x++) {
  315.             for (int y = 0; y < _height; y++) {
  316.                 Sq mySquare = _board[x][y];
  317.                 if (mySquare._successor == null && mySquare._sequenceNum != 0) {
  318.                     for (Place temp : allSuccessors(x, y, _board[x][y]._dir)) {
  319.                         Sq potentialSuccessor = get(temp);
  320.                         if (potentialSuccessor._sequenceNum == mySquare._sequenceNum + 1)          {
  321.                             if (mySquare.connectable(potentialSuccessor)) {
  322.                                 mySquare.connect(potentialSuccessor);
  323.                                 return true;
  324.                             }
  325.                         }
  326.                     }
  327.                 }
  328.             }
  329.         }
  330.         return false; // FIXME
  331.     }
  332.  
  333.     /** Sets the numbers in my squares to the solution from which I was
  334.      *  last initialized by the constructor. */
  335.     void solve() {
  336.         // FIXME
  337.  
  338.        // _board = new Sq[_width][_height];
  339.  
  340.         for (int i=0; i < _width; i++){
  341.             for (int j=0; j < _height; j++){
  342.  
  343.                 if (_board[i][j]._hasFixedNum == false ){
  344.                     _board[i][j] = new Sq(i,j,_solution[i][j],false, arrowDirection(i,j),-1);
  345.                 }
  346.  
  347.             }
  348.         }
  349.  
  350.         _unconnected = 0;
  351.     }
  352.  
  353.     /** Return the direction from cell (X, Y) in the solution to its
  354.      *  successor, or 0 if it has none. */
  355.     private int arrowDirection(int x, int y) {
  356.         int seq0 = _solution[x][y];
  357.  
  358.  
  359.         if (seq0 < _solnNumToPlace.length-1 ){
  360.  
  361.             if (_solnNumToPlace[seq0+1] != null){
  362.  
  363.                 return _solnNumToPlace[seq0].dirOf(_solnNumToPlace[seq0+1]);
  364.             }
  365.         }
  366.  
  367.         return 0;
  368.     }
  369.  
  370.     /** Return a new, currently unused group number > 0.  Selects the
  371.      *  lowest not currently in used. */
  372.     private int newGroup() {
  373.         for (int i = 1; true; i += 1) {
  374.             if (_usedGroups.add(i)) {
  375.                 return i;
  376.             }
  377.         }
  378.     }
  379.  
  380.     /** Indicate that group number GROUP is no longer in use. */
  381.     private void releaseGroup(int group) {
  382.         _usedGroups.remove(group);
  383.     }
  384.  
  385.     /** Combine the groups G1 and G2, returning the resulting group. Assumes
  386.      *  G1 != 0 != G2 and G1 != G2. */
  387.     private int joinGroups(int g1, int g2) {
  388.         assert (g1 != 0 && g2 != 0);
  389.         if (g1 == -1 && g2 == -1) {
  390.             return newGroup();
  391.         } else if (g1 == -1) {
  392.             return g2;
  393.         } else if (g2 == -1) {
  394.             return g1;
  395.         } else if (g1 < g2) {
  396.             releaseGroup(g2);
  397.             return g1;
  398.         } else {
  399.             releaseGroup(g1);
  400.             return g2;
  401.         }
  402.     }
  403.  
  404.     @Override
  405.     public Iterator<Sq> iterator() {
  406.         return _allSquares.iterator();
  407.     }
  408.  
  409.     @Override
  410.     public String toString() {
  411.         String hline;
  412.         hline = "+";
  413.         for (int x = 0; x < _width; x += 1) {
  414.             hline += "------+";
  415.         }
  416.  
  417.         Formatter out = new Formatter();
  418.         for (int y = _height - 1; y >= 0; y -= 1) {
  419.             out.format("%s%n", hline);
  420.             out.format("|");
  421.             for (int x = 0; x < _width; x += 1) {
  422.                 Sq sq = get(x, y);
  423.                 if (sq.hasFixedNum()) {
  424.                     out.format("+%-5s|", sq.seqText());
  425.                 } else {
  426.                     out.format("%-6s|", sq.seqText());
  427.                 }
  428.             }
  429.             out.format("%n|");
  430.             for (int x = 0; x < _width; x += 1) {
  431.                 Sq sq = get(x, y);
  432.                 if (sq.predecessor() == null && sq.sequenceNum() != 1) {
  433.                     out.format(".");
  434.                 } else {
  435.                     out.format(" ");
  436.                 }
  437.                 if (sq.successor() == null
  438.                     && sq.sequenceNum() != size()) {
  439.                     out.format("o ");
  440.                 } else {
  441.                     out.format("  ");
  442.                 }
  443.                 out.format("%s |", ARROWS[sq.direction()]);
  444.             }
  445.             out.format("%n");
  446.         }
  447.         out.format(hline);
  448.         return out.toString();
  449.     }
  450.  
  451.     @Override
  452.     public boolean equals(Object obj) {
  453.         Model model = (Model) obj;
  454.         return (_unconnected == model._unconnected
  455.                 && _width == model._width && _height == model._height
  456.                 && Arrays.deepEquals(_solution, model._solution)
  457.                 && Arrays.deepEquals(_board, model._board));
  458.     }
  459.  
  460.     @Override
  461.     public int hashCode() {
  462.         return Arrays.deepHashCode(_solution) * Arrays.deepHashCode(_board);
  463.     }
  464.  
  465.     /** Represents a square on the board. */
  466.     final class Sq {
  467.         /** A square at (X0, Y0) with arrow in direction DIR (0 if not
  468.          *  set), group number GROUP, sequence number SEQUENCENUM (0
  469.          *  if none initially assigned), which is fixed iff FIXED. */
  470.         Sq(int x0, int y0, int sequenceNum, boolean fixed, int dir, int group) {
  471.             x = x0; y = y0;
  472.             pl = pl(x, y);
  473.             _hasFixedNum = fixed;
  474.             _sequenceNum = sequenceNum;
  475.             _dir = dir;
  476.             _head = this;
  477.             _group = group;
  478.         }
  479.  
  480.         /** A copy of OTHER, excluding head, successor, and predecessor. */
  481.         Sq(Sq other) {
  482.             this(other.x, other.y, other._sequenceNum, other._hasFixedNum,
  483.                  other._dir, other._group);
  484.             _successor = _predecessor = null;
  485.             _head = this;
  486.             _successors = other._successors;
  487.             _predecessors = other._predecessors;
  488.         }
  489.  
  490.         /** Return my current sequence number, or 0 if none assigned. */
  491.         int sequenceNum() {
  492.             return _sequenceNum;
  493.         }
  494.  
  495.         /** Fix my current sequence number at N>0.  It is an error if my number
  496.          *  is not initially 0 or N. */
  497.         void setFixedNum(int n) {
  498.             if (n == 0 || (_sequenceNum != 0 && _sequenceNum != n)) {
  499.                 throw badArgs("sequence number may not be fixed");
  500.             }
  501.             _hasFixedNum = true;
  502.             if (_sequenceNum == n) {
  503.                 return;
  504.             } else {
  505.                 releaseGroup(_head._group);
  506.             }
  507.             _sequenceNum = n;
  508.             for (Sq sq = this; sq._successor != null; sq = sq._successor) {
  509.                 sq._successor._sequenceNum = sq._sequenceNum + 1;
  510.             }
  511.             for (Sq sq = this; sq._predecessor != null; sq = sq._predecessor) {
  512.                 sq._predecessor._sequenceNum = sq._sequenceNum - 1;
  513.             }
  514.         }
  515.  
  516.         /** Unfix my sequence number if it is currently fixed; otherwise do
  517.          *  nothing. */
  518.         void unfixNum() {
  519.             Sq next = _successor, pred = _predecessor;
  520.             _hasFixedNum = false;
  521.             disconnect();
  522.             if (pred != null) {
  523.                 pred.disconnect();
  524.             }
  525.             _sequenceNum = 0;
  526.             if (next != null) {
  527.                 connect(next);
  528.             }
  529.             if (pred != null) {
  530.                 pred.connect(this);
  531.             }
  532.         }
  533.  
  534.         /** Return true iff my sequence number is fixed. */
  535.         boolean hasFixedNum() {
  536.             return _hasFixedNum;
  537.         }
  538.  
  539.         /** Returns direction of my arrow (0 if no arrow). */
  540.         int direction() {
  541.             return _dir;
  542.         }
  543.  
  544.         /** Return my current predecessor. */
  545.         Sq predecessor() {
  546.             return _predecessor;
  547.         }
  548.  
  549.         /** Return my current successor. */
  550.         Sq successor() {
  551.             return _successor;
  552.         }
  553.  
  554.         /** Return the head of the connected sequence I am currently in. */
  555.         Sq head() {
  556.             return _head;
  557.         }
  558.  
  559.         /** Return the group number of my group.  It is 0 if I am numbered, and
  560.          *  -1 if I am alone in my group. */
  561.         int group() {
  562.             if (_sequenceNum != 0) {
  563.                 return 0;
  564.             } else {
  565.                 return _head._group;
  566.             }
  567.         }
  568.  
  569.         /** Size of alphabet. */
  570.         static final int ALPHA_SIZE = 26;
  571.  
  572.         /** Return a textual representation of my sequence number or
  573.          *  group/position. */
  574.         String seqText() {
  575.             if (_sequenceNum != 0) {
  576.                 return String.format("%d", _sequenceNum);
  577.             }
  578.             int g = group() - 1;
  579.             if (g < 0) {
  580.                 return "";
  581.             }
  582.  
  583.             String groupName =
  584.                 String.format("%s%s",
  585.                               g < ALPHA_SIZE ? ""
  586.                               : Character.toString((char) (g / ALPHA_SIZE
  587.                                                            + 'a')),
  588.                               Character.toString((char) (g % ALPHA_SIZE
  589.                                                          + 'a')));
  590.             if (this == _head) {
  591.                 return groupName;
  592.             }
  593.             int n;
  594.             n = 0;
  595.             for (Sq p = this; p != _head; p = p._predecessor) {
  596.                 n += 1;
  597.             }
  598.             return String.format("%s%+d", groupName, n);
  599.         }
  600.  
  601.         /** Return locations of my potential successors. */
  602.         PlaceList successors() {
  603.             return _successors;
  604.         }
  605.  
  606.         /** Return locations of my potential predecessors. */
  607.         PlaceList predecessors() {
  608.             return _predecessors;
  609.         }
  610.  
  611.         /** Returns true iff I may be connected to cell S1, that is:
  612.          *  + S1 is in the correct direction from me.
  613.          *  + S1 does not have a current predecessor, and I do not have a
  614.          *    current successor.
  615.          *  + If S1 and I both have sequence numbers, then mine is
  616.          *    sequenceNum() == S1.sequenceNum() - 1.
  617.          *  + If neither S1 nor I have sequence numbers, then we are not part
  618.          *    of the same connected sequence.
  619.          */
  620.         boolean connectable(Sq s1) {
  621.  
  622.             if (_successors.contains(s1.pl) && s1._predecessor == null && _successor == null ){
  623.  
  624.                if (sequenceNum() != 0 && s1.sequenceNum() != 0 && (sequenceNum() == s1.sequenceNum()-1 )){
  625.                    return true;
  626.                }
  627.                else if (sequenceNum() == 0 && s1.sequenceNum() == 0 && ( _head != s1._head)){
  628.                    return true;
  629.                }
  630.                else{}
  631.  
  632.  
  633.             }
  634.             return false;
  635.         }
  636.  
  637.         /** Connect me to S1, if we are connectable; otherwise do nothing.
  638.          *  Returns true iff we were connectable.  Assumes S1 is in the proper
  639.          *  arrow direction from me. */
  640.         boolean connect(Sq s1) {
  641.             if (!connectable(s1)) {
  642.                 return false;
  643.             }
  644.             int sgroup = s1.group();
  645.  
  646.             _unconnected -= 1;
  647.  
  648.             // FIXME: Connect me to my successor:
  649.             //        + Set my _successor field and S1's _predecessor field.
  650.             //        + If I have a number, number all my successors
  651.             //          accordingly (if needed).
  652.             //        + If S1 is numbered, number me and my predecessors
  653.             //          accordingly (if needed).
  654.             //        + Set the _head fields of my successors to my _head.
  655.             //        + If either of this or S1 used to be unnumbered and is
  656.             //          now numbered, release its group of whichever was
  657.             //          unnumbered, so that it can be reused.
  658.             //        + If both this and S1 are unnumbered, set the group of
  659.             //          my head to the result of joining the two groups.
  660.             boolean thisWasNumbered, s1WasNumbered;
  661.             thisWasNumbered = s1WasNumbered = false;
  662.             this._successor = s1; s1._predecessor = this;
  663.             if (this._sequenceNum != 0) { // Condition 2: I had a #
  664.                 if (s1._sequenceNum == 0)
  665.                     s1WasNumbered = true;
  666.                 Sq successorPtr = this._successor;
  667.                 int offset = this._sequenceNum;
  668.                 while (successorPtr != null) {
  669.                     offset += 1;
  670.                     successorPtr._sequenceNum = offset;
  671.                     successorPtr = successorPtr._successor;
  672.                 }
  673.             }
  674.             if (s1._sequenceNum != 0) { // Condition 3: S1 had a #
  675.                 if (this._sequenceNum == 0)
  676.                     thisWasNumbered = true;
  677.                 this._sequenceNum = s1._sequenceNum - 1;
  678.                 Sq predecessorPtr = this._predecessor;
  679.                 int initNum = this._sequenceNum;
  680.                 while (predecessorPtr != null) {
  681.                     initNum -= 1;
  682.                     predecessorPtr._sequenceNum = initNum;
  683.                     predecessorPtr = predecessorPtr._predecessor;
  684.                 }
  685.             }
  686.             // Condition 4 : Head of my successors is my head
  687.             Sq successorPtr = this._successor;
  688.             while (successorPtr != null) {
  689.                 successorPtr._head = this._head;
  690.                 successorPtr = successorPtr._successor;
  691.             }
  692.             // Condition 5: Either was numbered
  693.             if (thisWasNumbered || s1WasNumbered) {
  694.                 if (thisWasNumbered) {
  695.                     releaseGroup(this._group);
  696.                 }
  697.                 else if (s1WasNumbered) {
  698.                     releaseGroup(s1._group);
  699.                 }
  700.             }
  701.             // Condition 6: Both are unnumbered
  702.             if ((this._sequenceNum == 0) && (s1._sequenceNum == 0))  {
  703.                 this._head._group = joinGroups(this._head._group, s1._head._group);
  704.             }
  705.  
  706.             return true;
  707.         }
  708.  
  709.         /** Disconnect me from my current successor, if any. */
  710.         void disconnect() {
  711.             Sq next = _successor;
  712.             if (next == null) {
  713.                 return;
  714.             }
  715.             _unconnected += 1;
  716.             next._predecessor = _successor = null;
  717.             if (_sequenceNum == 0) {
  718.                 // FIXME: If both this and next are now one-element groups,
  719.                 //        release their former group and set both group
  720.                 //        numbers to -1.
  721.                 //        Otherwise, if either is now a one-element group, set
  722.                 //        its group number to -1 without releasing the group
  723.                 //        number.
  724.                 //        Otherwise, the group has been split into two multi-
  725.                 //        element groups.  Create a new group for next.
  726.             } else {
  727.                 // FIXME: If neither this nor any square in its group that
  728.                 //        precedes it has a fixed sequence number, set all
  729.                 //        their sequence numbers to 0 and create a new group
  730.                 //        for them if this has a current predecessor (other
  731.                 //        set group to -1).
  732.                 // FIXME: If neither next nor any square in its group that
  733.                 //        follows it has a fixed sequence number, set all
  734.                 //        their sequence numbers to 0 and create a new
  735.                 //        group for them if next has a current successor
  736.                 //        (otherwise set next's group to -1.)
  737.             }
  738.             // FIXME: Set the _head of next and all squares in its group to
  739.             //        next.
  740.         }
  741.  
  742.         @Override
  743.         public boolean equals(Object obj) {
  744.             Sq sq = (Sq) obj;
  745.             return sq != null
  746.                 && pl == sq.pl
  747.                 && _hasFixedNum == sq._hasFixedNum
  748.                 && _sequenceNum == sq._sequenceNum
  749.                 && _dir == sq._dir
  750.                 && (_predecessor == null) == (sq._predecessor == null)
  751.                 && (_predecessor == null
  752.                     || _predecessor.pl == sq._predecessor.pl)
  753.                 && (_successor == null || _successor.pl == sq._successor.pl);
  754.         }
  755.  
  756.         @Override
  757.         public int hashCode() {
  758.             return (x + 1) * (y + 1) * (_dir + 1)
  759.                 * (_hasFixedNum ? 3 : 1) * (_sequenceNum + 1);
  760.         }
  761.  
  762.         /** The coordinates of this square in the board. */
  763.         protected final int x, y;
  764.         /** My coordinates as a Place. */
  765.         protected final Place pl;
  766.         /** The first in the currently connected sequence of cells ("group")
  767.          *  that includes this one. */
  768.         private Sq _head;
  769.         /** If _head == this, then the group number of the group of which this
  770.          *  is a member.  Numbered sequences have a group number of 0,
  771.          *  regardless of the value of _group. Unnumbered one-member groups
  772.          *  have a group number of -1.   */
  773.         private int _group;
  774.         /** True iff assigned a fixed sequence number. */
  775.         private boolean _hasFixedNum;
  776.         /** The current imputed or fixed sequence number,
  777.          *  numbering from 1, or 0 if there currently is none. */
  778.         private int _sequenceNum;
  779.         /** The arrow direction. The possible values are 0 (for unset),
  780.          *  1 for northeast, 2 for east, 3 for southeast, 4 for south,
  781.          *  5 for southwest, 6 for west, 7 for northwest, and 8 for north. */
  782.         private int _dir;
  783.         /** The current predecessor of this square, or null if there is
  784.          *  currently no predecessor. */
  785.         private Sq _predecessor;
  786.         /** The current successor of this square, or null if there is
  787.          *  currently no successor. */
  788.         private Sq _successor;
  789.         /** Locations of my possible predecessors. */
  790.         private PlaceList _predecessors;
  791.         /** Locations of my possible successor. */
  792.         private PlaceList _successors;
  793.     }
  794.  
  795.     /** ASCII denotations of arrows, indexed by direction. */
  796.     private static final String[] ARROWS = {
  797.         " *", "NE", "E ", "SE", "S ", "SW", "W ", "NW", "N "
  798.     };
  799.  
  800.     /** Number of squares that haven't been connected. */
  801.     private int _unconnected;
  802.     /** Dimensions of board. */
  803.     private int _width, _height;
  804.     /** Contents of board, indexed by position. */
  805.     private Sq[][] _board;
  806.     /** Contents of board as a sequence of squares for convenient iteration. */
  807.     private ArrayList<Sq> _allSquares = new ArrayList<>();
  808.     /** _allSuccessors[x][y][dir] is a sequence of all queen moves possible
  809.      *  on the board of in direction dir from (x, y).  If dir == 0,
  810.      *  this is all places that are a queen move from (x, y) in any
  811.      *  direction. */
  812.     private PlaceList[][][] _allSuccessors;
  813.     /** The solution from which this Model was built. */
  814.     private int[][] _solution;
  815.     /** Inverse mapping from sequence numbers to board positions. */
  816.     private Place[] _solnNumToPlace;
  817.     /** The set of positive group numbers currently in use. */
  818.     private HashSet<Integer> _usedGroups = new HashSet<>();
  819.  
  820. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top