Stacks

The goal of this lab period is to update our LinkedList class to implement a Stack interface and begin work on the project.


Tasks

Implementing a Stack

  1. Setup

    Make a new folder for this week's project.

    Copy over your LinkedList and LinkedListTests files from the previous project and download this Stack interface.

  2. Implement the Stack interface

    Edit the declaration of your LinkedList class to implement the Stack interface: public class LinkedList<T> implements Stack<T>, Iterable<T>

    In order to do so, you'll have to make sure you have all the methods from the Stack, namely:

    • public int size(): returns the number of items in the stack
    • public T peek(): returns the item on the top of the stack
    • public T pop(): removes and returns the item on the top of the stack
    • public void push(T item): adds the given item to the top of the stack
    One thing to be a bit careful about is that your peek method is used in both the Queue and Stack interfaces, so you'll need to ensure that your methods work in both cases.

    Having done so, add a few tests to the LinkedListTests file to confirm that your stack is operating as expected.

Cell Class

In order to begin playing Sudoku, we'll write a simple Cell class, similar to the Cell class from Project 2 (Conway's Game of Life). The Cell will represent one location in a Sudoku board. If you haven't played Sudoku before, consider taking a minute to check out Sudoku.com. Accordingly, instead of being a somewhat binary object (Cells in Project 2 were either alive or dead), a cell in Sudoku can take on the values 1 - 9. A locked cell's value will be read from an input file and an unlocked cell's value is to be determined by the Sudoku solver.

  1. Setup

    Start a Java file called Cell.java and make a public class called Cell. The Cell class should have four fields to hold the row index, column index, value, and whether the value is locked.

  2. Write your constructors

    Write two constructors for the Cell class.

    • public Cell(int row, int col, int value) - initialize the row, column, and value fields to the given parameter values. Set the locked field to false;
    • public Cell(int row, int col, int value, boolean locked) - initialize all of the Cell fields given the parameters.
  3. Write the accessor and mutator functions

    The following accessor and mutator functions manage the position of a cell (row, col), its value (number), and whether it is a locked value.

    • public int getRow() - return the Cell's row index.
    • public int getCol() - return the Cell's column index.
    • public int getValue() - return the Cell's value.
    • public void setValue(int newval) - set the Cell's value.
    • public boolean isLocked() - return the value of the locked field.
    • public void setLocked(boolean lock) - set the Cell's locked field to the new value.
  4. Write a toString function

    The toString function should generate and return a representating String. In this case, have it return a string with the Cell's numeric value.

  5. Write a few tests for your Cell class to validate your code.

Reading Files

The final part of the lab is to read data (in this case, a board) from a file.

  1. Create a new file Board.java. In it, create a new class Board. This will keep track of the Sudoku board itself. In particular, we'll need to manage 2D Array of Cells. For now, create a constructor that creates a 9x9 2D array of Cells, all of which are initialized to have value 0. Add the following two methods:
    • public Cell get(int row, int col): this returns the Cell at the given row and col
    • public void set(int row, int col, int value): this sets the Cell at the given row and col to the given value
    • public void set(int row, int col, boolean locked): this sets whether the Cell at the given row and col is locked
  2. The first thing we'll do is give ourselves the ability to do is read in a Sudoku board. At the top of your file, import java.io.*, java.io.FileReader and java.io.BufferedReader. Then, we'll use the template below:
      public boolean read(String filename) {
        try {
          // assign to a variable of type FileReader a new FileReader object, passing filename to the constructor
          FileReader fr = new FileReader(filename);
          // assign to a variable of type BufferedReader a new BufferedReader, passing the FileReader variable to the constructor
          BufferedReader br = new BufferedReader(fr);
          
          // assign to a variable of type String line the result of calling the readLine method of your BufferedReader object.
          String line = br.readLine();
          // start a while loop that loops while line isn't null
          while(line != null){
              // print line
    	  System.out.println( line );
              // assign to an array of Strings the result of splitting the line up by spaces (line.split("[ ]+"))
              String[] arr = line.split( "[ ]+" );
              // let's see what this array holds: 
              System.out.println("the first item in arr: " + arr[0] + ", the second item in arr: " + arr[1]);
              // print the size of the String array (you can use .length)
              System.out.println( arr.length );
              // use the line to set various Cells of this Board accordingly
    	  // TODO THIS IS WHAT NEEDS TO BE FILLED IN!
              // assign to line the result of calling the readLine method of your BufferedReader object.
              line = br.readLine();
          }
          // call the close method of the BufferedReader
          br.close();
          return true;
        }
        catch(FileNotFoundException ex) {
          System.out.println("Board.read():: unable to open file " + filename );
        }
        catch(IOException ex) {
          System.out.println("Board.read():: error reading file " + filename);
        }
    
        return false;
      }
  3. Define a Board toString method

    Write a public String toString() method that generates a multi-line string representation of the board. To make it easy to examine the board, you may want to have spaces that separate the 9x9 board into 3x3 blocks. When you have written this function, write a main method you can run to test the constructor and the toString methods. The main method should create a new Board object and then print it.

  4. Write a main function that creates a new Board and calls the read method. Use a command line argument as the filename you pass to the read method.
  5. Download board1.txt and board2.txt and make sure the output makes sense.

Lab checkpoint: Show us your code can read in a board correctly (call the read method on board1.txt or board2.txt, then call the board's toString method and make sure it matches the file you read in!).

When you are done with the lab, go ahead and get started on the current project.