Developer Forums | About Us | Site Map
Search  
HOME > TUTORIALS > SERVER SIDE CODING > JAVA TUTORIALS > OPTIMIZE YOUR JAVA APPLICATIONS PERFORMANCE


Sponsors





Useful Lists

Web Host
site hosted by netplex

Online Manuals

Optimize your Java applications performance
By Erwin Vervaet & Maarten De Cock - 2003-12-15 Page:  1 2 3 4 5 6 7 8 9 10 11

The Board Class

Before we implement the Board class, we'll need to tackle two interesting problems. First we have to decide on a data structure. A Meteor puzzle board is basically a 5-by-10 grid of regular hexagons, which we can represent as an array of 50 Cell objects. Instead of using the Cell class directly, we'll use the BoardCell subclass, shown in Listing 5, which keeps track of the piece that occupies the cell:

Listing 5. The BoardCell subclass


public class BoardCell extends Cell {
  private Piece piece = null;

  public Piece getPiece() {
    return piece;
  }

  public void setPiece(Piece piece) {
    this.piece = piece;
  }
}

If we store all 50 board cells of the board in an array, we'll have to write some tedious initialisation code. This initialisation identifies the neighbouring board cells for each cell of the board, as illustrated in Figure 3. For instance, cell 0 has two neighbours: cell 1 in the east and cell 5 in the southeast. Listing 6 shows the initializeBoardCell() method that is called from the constructor of the Board class to do this initialisation.

Figure 3. The board represented as an array of cells
The board represented as an array of cells

Now that we've implemented the data structure for the board, we move on to the next problem: writing a placePiece() method that puts a piece on the board. The hardest part of writing this method is deciding whether the piece fits on the board at the given position. One way to determine whether the piece fits is to first find all the board cells that would be occupied by the cells of the piece if it were placed on the board. After we have this set of board cells, we can easily determine if the new piece would fit: all corresponding board cells need to be empty and the piece needs to fit completely on the board. This process is implemented by the findOccupiedBoardCells() method and placePiece() method shown in Listing 6. Note that we use the processed field of the PieceCell objects to avoid an infinite recursion in the findOccupiedBoardCells() method.

Listing 6. The Board class


public class Board {
  public static final int NUMBEROFCELLS = 50;
  public static final int NUMBEROFCELLSINROW = 5;

  private BoardCell[] boardCells = new BoardCell[NUMBEROFCELLS];

  public Board() {
    for (int i = 0; i < NUMBEROFCELLS; i++) {
      boardCells[i] = new BoardCell();
    }

    for (int i = 0; i < NUMBEROFCELLS; i++) {
      initializeBoardCell(boardCells[i], i);
    }
  }

  /**
   * Initialize the neighbours of the given boardCell at the given
   * index on the board
   */
  private void initializeBoardCell(BoardCell boardCell, int index) {
    int row = index/NUMBEROFCELLSINROW;

    // Check if cell is in last or first column
    boolean isFirst = (index%NUMBEROFCELLSINROW == 0);
    boolean isLast = ((index+1)%NUMBEROFCELLSINROW == 0);

    if (row%2 == 0) { // Even rows
      if (row != 0) {
        // Northern neighbours

        if (!isFirst) {
          boardCell.setNeighbour(Cell.NORTHWEST, boardCells[index-6]);
        }
        boardCell.setNeighbour(Cell.NORTHEAST, boardCells[index-5]);
      }
      if (row != ((NUMBEROFCELLS/NUMBEROFCELLSINROW)-1)) {
        // Southern neighbours
        if (!isFirst) {
          boardCell.setNeighbour(Cell.SOUTHWEST, boardCells[index+4]);
        }
        boardCell.setNeighbour(Cell.SOUTHEAST, boardCells[index+5]);
      }
    }
    else { // Uneven rows
      // Northern neighbours
      if (!isLast) {
        boardCell.setNeighbour(Cell.NORTHEAST, boardCells[index-4]);
      }
      boardCell.setNeighbour(Cell.NORTHWEST, boardCells[index-5]);
      // Southern neighbours
      if (row != ((NUMBEROFCELLS/NUMBEROFCELLSINROW)-1)) {
        if (!isLast) {
          boardCell.setNeighbour(Cell.SOUTHEAST, boardCells[index+6]);
        }
        boardCell.setNeighbour(Cell.SOUTHWEST, boardCells[index+5]);
      }
    }

    // Set the east and west neighbours
    if (!isFirst) {
      boardCell.setNeighbour(Cell.WEST, boardCells[index-1]);
    }
    if (!isLast) {
      boardCell.setNeighbour(Cell.EAST, boardCells[index+1]);
    }
  }

  public void findOccupiedBoardCells(
    ArrayList occupiedCells, PieceCell pieceCell, BoardCell boardCell) {
    if (pieceCell != null && boardCell != null && !pieceCell.isProcessed()) {
      occupiedCells.add(boardCell);
      

      /* Neighbouring cells can form loops, which would lead to an
         infinite recursion. Avoid this by marking the processed 
         cells. */
      
      pieceCell.setProcessed(true);

      // Repeat for each neighbour of the piece cell
      for (int i = 0; i < Cell.NUMBEROFSIDES; i++) {
        findOccupiedBoardCells(occupiedCells,
                               (PieceCell)pieceCell.getNeighbour(i),
                               (BoardCell)boardCell.getNeighbour(i));
      }
    }
  }

  public boolean placePiece(Piece piece, int boardCellIdx) {
    // We will manipulate the piece using its first cell
    return placePiece(piece, 0, boardCellIdx);
  }

  public boolean 
    placePiece(Piece piece, int pieceCellIdx, int boardCellIdx) {
    // We're going to process the piece

    piece.resetProcessed();

    // Get all the boardCells that this piece would occupy
    ArrayList occupiedBoardCells = new ArrayList();
    findOccupiedBoardCells(occupiedBoardCells,
                           piece.getPieceCell(pieceCellIdx),
                           boardCells[boardCellIdx]);

    if (occupiedBoardCells.size() != Piece.NUMBEROFCELLS) {
      // Some cells of the piece don't fall on the board
      return false;
    }

    for (int i = 0; i < occupiedBoardCells.size(); i++) {
      if (((BoardCell)occupiedBoardCells.get(i)).getPiece() != null)
        // The board cell is already occupied by another piece
        return false;
    }

    // Occupy the board cells with the piece

    for (int i = 0; i < occupiedBoardCells.size(); i++) {
      ((BoardCell)occupiedBoardCells.get(i)).setPiece(piece);
    }

    return true; // The piece fits on the board
  }

  public void removePiece(Piece piece) {
    for (int i = 0; i < NUMBEROFCELLS; i++) {
      // Piece objects are unique, so use reference equality
      if (boardCells[i].getPiece() == piece) {
        boardCells[i].setPiece(null);
      }
    }
  }
}

This completes the implementation of our initial solution. Let's put it to the test.



View Optimize your Java applications performance Discussion

Page:  1 2 3 4 5 6 7 8 9 10 11 Next Page: Running The Program

First published by IBM developerWorks


Copyright 2004-2017 GrindingGears.com. All rights reserved.
Article copyright and all rights retained by the author.