constructor for a class implementing doubly-linked list

[Igor Mechnikov]

Hello,
I am getting NullPointerException because my Tape() constructor is not correct.
I welcome any hints and suggestion regarding this or anything else that does not look right.
Thank you.

There are 3 classes: Cell, Tape, and TapeTest which has main()

package turing;
/*
		Your task is to write a class named Tape to represent Turing machine tapes. 
		The class should have an instance variable of type Cell that points to the current cell. 
		To be compatible with the classes that will use the Tape class, 
		your class must include the following methods:
		public Cell getCurrentCell() -- returns the pointer that points to the current cell. 

		public char getContent() -- returns the char from the current cell.

		public void setContent(char ch) -- changes the char in the current cell to the specified value. 

		public void moveLeft() -- moves the current cell one position to the left along the tape. 
		Note that if the current cell is the leftmost cell that exists, 
		then a new cell must be created and added to the tape at the left of the current cell, 
		and then the current cell pointer can be moved to point to the new cell. 
		The content of the new cell should be a blank space. 
		(Remember that the Turing machine's tape is conceptually infinite, 
		so your linked list must must be prepared to expand on demand, 
		when the machine wants to move past the current end of the list.) 

		public void moveRight() -- moves the current cell one position to the right along the tape. 
		Note that if the current cell is the rightmost cell that exists, 
		then a new cell must be created and added to the tape at the right of the current cell, 
		and then the current cell pointer can be moved to point to the new cell. 
		The content of the new cell should be a blank space. 
		public String getTapeContents() -- returns a String consisting of the chars from all the cells on the tape, 
		read from left to right, except that leading or trailing blank characters should be discarded. 
		The current cell pointer should not be moved by this method; 
		it should point to the same cell after the method is called as it did before. 
		You can create a different pointer to move along the tape and get the full contents. 
		(This method is the hardest one to implement.) 
 */

public class Tape {

	private Cell head; //will be set as instance variable for the methods
	private int index;

	Tape() {
		Cell runner = new Cell();
		runner = head;
		runner.content = '\u0000';
		runner.next = null;
		index = 0;
		//initially consists of a single cell. 
		//The cell should contain a blank space, and the current cell pointer should point to it. 
	}

	public Cell getCurrentCell() {//returns the pointer that points to the current cell. 
		Cell runner;
		runner = head;
		for(int i = 1; i < index && runner.next != null; i++)
		{
			runner = runner.next;
		}
		return runner;
		//if (runner != null) return runner;
		//else return null;
	}

	public char getContent() {//returns the char from the current cell.
		Cell runner;
		runner = head;
		for(int i = 1; i < index && runner.next != null; i++)
		{
			runner = runner.next;
		}
		return runner.content;
	}

	public void setContent(char ch) { //changes the char in the current cell to the specified value. 
		Cell runner;
		runner = head;
		for(int i = 1; i < index && runner.next != null; i++)
		{
			runner = runner.next;
		}
		runner.content = ch;
	}

	public void moveLeft() {//moves the current cell one position to the left along the tape.
		Cell runner;
		runner = head;
                getCurrentCell();
		runner = runner.prev;
		index--;
	}

	public void moveRight() {//moves the current cell one position to the left along the tape.
		Cell runner;
		runner = head;
                getCurrentCell();
		runner = runner.next;
		index++;
	}

	public String getTapeContents() {//returns String
		/*returns a String consisting of the chars from all the cells on the tape, 
			read from left to right, except that leading or trailing blank characters should be discarded. 
			The current cell pointer should not be moved by this method; 
			it should point to the same cell after the method is called as it did before. 
			You can create a different pointer to move along the tape and get the full contents. 
			(This method is the hardest one to implement.) */
		int count;          // For counting elements in the list.
		Cell runner;        // For traversing the list.
		String elements = "";  // An array to hold the list elements.

		// First, go through the list and count the number
		// of elements that it contains.

		count = 0;
		runner = head;
		while (runner.prev != null) moveLeft(); //move to the beginning of the list
		while (runner != null) {
			elements += runner.content;
			count++;
			runner = runner.next;
		}

		// Return the array that has been filled with the list elements.

		return elements;

	}

}

package turing;


/**
 * Represents one cell on a Turing Machine tape.
 */
public class Cell {
	
	public char content;  // The character in this cell.
	public Cell next;     // Pointer to the cell to the right of this one.
	public Cell prev;     // Pointer to the cell to the left of this one.
	
}

package turing;

// A test program for the Tape class that calls most of the methods in that class.
//
// The output from this program should be:  Tape Contents:  Hello World
//                                          Final position at the W

public class TestTape {
	
	public static void main(String[] args) {
		
		Tape tape = new Tape();
		for (int i = 0; i < "World".length(); i++) {
			tape.setContent("World".charAt(i));
			tape.moveRight();
		}
		for (int i = 0; i < "Hello World".length(); i++)
			tape.moveLeft();
		for (int i =0; i < "Hello".length(); i++) {
			tape.setContent("Hello".charAt(i));
			tape.moveRight();
		}
		System.out.println("Tape Contents:  " + tape.getTapeContents());
		tape.moveRight();
		System.out.println("Final position at the " + tape.getContent());
	}

}

[Stefan Evans]

Cell runner = new Cell();  
runner = head;  
// ask yourself why would the value of runner be null at this point?
runner.content = '\u0000';  

[Igor Mechnikov]

Stefan Evans wrote:

Cell runner = new Cell();  
runner = head;  
// ask yourself why would the value of runner be null at this point?
runner.content = '\u0000';  

Thank you for responding.

The idea was to implement "initially consists of a single cell. The cell should contain a blank space, and the current cell pointer should point to it."

I suppose if it is a new Cell containing a char that would have a default value of '\u0000' already so it is not necessary to initialize it.

[Jared Malcolm]

Igor Mechnikov wrote:The idea was to implement "initially consists of a single cell. The cell should contain a blank space, and the current cell pointer should point to it."

Then why assign the value of NULL to the char? Why not

runner.content=' ';

Also something that should be done is encapsulation... If you are changing variables in another class you should be using accessor methods to do so. I.E.

public class Cell {	
        private char content;  // The character in this cell.
        private Cell next;     // Pointer to the cell to the right of this one.
        private Cell prev;     // Pointer to the cell to the left of this one.
	
        public char getContent(){ 
             return content; 
        }
        public void setContent(char content){ 
             this.content = content; 
        }
        public Cell getNext(){ 
             return next; 
        }
        public void setNext(Cell next){ 
             this.next = next; 
        }
        public Cell getPrev(){ 
             return prev; 
        }
        public void setPrev(Cell prev){ 
             this.prev = prev; 
        }	
}

While what you are doing will work it is in no way proper.

[Igor Mechnikov]

Jared Malcolm wrote:

Igor Mechnikov wrote:The idea was to implement "initially consists of a single cell. The cell should contain a blank space, and the current cell pointer should point to it."

Then why assign the value of NULL to the char? Why not

runner.content=' ';

While what you are doing will work it is in no way proper.

Thank you very much. I actually looked up the default value for char, did not know I could have used ' '. little light bulb flickers.

As far as encapsulation, I was given Cell and TapeTest classes and had to create Tape.

However, It makes too much sense that methods having to do with Cell ought to be where they belong.

This way Tape methods could go to the currentCell and then implement Cell methods.

[Jared Malcolm]

Igor Mechnikov wrote:As far as encapsulation, I was given Cell and TapeTest classes and had to create Tape.

Gotcha, was kinda curious what code if any you had been provided.
Regardless, adding that in when it wasn't required simply to practice proper OO coding SHOULD (I'd hope) impress/please the instructor.


Also...

Cell runner;  
runner = head;

could be done as...

Cell runner = head;
//and in some of the methods something like...
Cell runner = head.getNext(); //turning three lines of code into one.

[Igor Mechnikov]

Jared Malcolm wrote:

Igor Mechnikov wrote:As far as encapsulation, I was given Cell and TapeTest classes and had to create Tape.

Gotcha, was kinda curious what code if any you had been provided.
Regardless, adding that in when it wasn't required simply to practice proper OO coding SHOULD (I'd hope) impress/please the instructor.


Also...

Cell runner;  
runner = head;

could be done as...

Cell runner = head;
//and in some of the methods something like...
Cell runner = head.getNext(); //turning three lines of code into one.

I wish I had an instructor who evaluated my work (story for another day)

I changed constructor to

Tape() {
		/*Cell runner = new Cell();
		runner = head;
		runner.content = ' '; 
		runner.next = null;
		runner.prev = null;
		index = 0;
		*/
		Cell head = new Cell();
		head.next = head.prev = head;
		head.content = ' ';
		index = 0;
	}

and Eclipse no longer complains about it,

Now, the problem becomes my for loop

public Cell getCurrentCell() {//returns the pointer that points to the current cell. 
		Cell runner = head;
		for(int i = 1; i < index && runner.next != null; i++)
		{
			runner = runner.next;
		}
		return runner;
		//if (runner != null) return runner;
		//else return null;
	}

since index is initialized to 0 I am getting more NullPointerExceptions

[Jared Malcolm]

So do a check on the line Before or Change one of your values

[Igor Mechnikov]

I ended up adapting Sedgewick's doubly-linked list code. Learned a little about iterators as well. Thank you.

Code:

/*************************************************************************
  *  Compilation:  javac EasyTape.java
  *  Execution:    java EasyTape
  * 
  *
  *  A tape implemented with a doubly linked list. The elements are stored
  *  (and iterated over) in the same order that they are inserted.
  * 
  *  This program implements Iterable interface.
  *  ListIterator makes moving along the tape simpler and allows to
  *  choose different types of values for the Cells.
  *  The test client illustrates how easy it is to move forwards and backwards.
  *  Thus moving one can easily remove any and all cells, e.g. trailing white spaces.
  *  (for additional example, try included "another" test client which uses integers)
  * 
  *  Contains 1 file:
  *  Class Cell is implemented as a private class, TestTape is the main() method.
  *  Also contains private class EasyTapeIterator for the iterator methods.
  *
  *  adapted from DoublyLinkedList.java 
  *  http://algs4.cs.princeton.edu/13stacks/DoublyLinkedList.java.html
  *  Copyright © 2007, Robert Sedgewick and Kevin Wayne. 
  *
  *************************************************************************/

import java.util.ListIterator;
import java.util.NoSuchElementException;

public class EasyTape<Value> implements Iterable<Value> {
  int N;                // number of elements on tape
  private Cell pre;     // sentinel before first element
  private Cell post;    // sentinel after last element
  
  public EasyTape() {
    pre  = new Cell();
    post = new Cell();
    pre.next = post;
    post.prev = pre;
  }
  
  // linked tape node helper data type
  private class Cell {
    Value value;
    Cell next;
    Cell prev;
  }
  
  public boolean isEmpty()    { return N == 0; }
  public int size()           { return N;      }
  
  // add the value to the tape
  public void add(Value value) {
    Cell last = post.prev;
    Cell x = new Cell();
    x.value = value;
    x.next  = post;
    x.prev  = last;
    post.prev = x;
    last.next = x;
    N++;
  }
  
  public ListIterator<Value> iterator()  { return new EasyTapeIterator(); }
  
  // assumes no calls to EasyTape.add() during iteration
  private class EasyTapeIterator implements ListIterator<Value> {
    Cell current      = pre.next;  // the node that is returned by next()
    Cell lastAccessed = null;      // the last node to be returned by prev() or next()
    // reset to null upon intervening remove() or add()
    int index = 0;
    
    public boolean hasNext()      { return index < N; }
    public boolean hasPrevious()  { return index > 0; }
    public int previousIndex()    { return index - 1; }
    public int nextIndex()        { return index;     }
    
    public Value next() {
      if (!hasNext()) throw new NoSuchElementException();
      lastAccessed = current;
      Value value = current.value;
      current = current.next; 
      index++;
      return value;
    }
    
    public Value previous() {
      if (!hasPrevious()) throw new NoSuchElementException();
      current = current.prev;
      index--;
      lastAccessed = current;
      return current.value;
    }
    
    // replace the value of the element that was last accessed by next() or previous()
    // condition: no calls to remove() or add() after last call to next() or previous()
    public void set(Value value) {
      if (lastAccessed == null) throw new IllegalStateException();
      lastAccessed.value = value;
    }
    
    // remove the element that was last accessed by next() or previous()
    // condition: no calls to remove() or add() after last call to next() or previous()
    public void remove() { 
      if (lastAccessed == null) throw new IllegalStateException();
      Cell x = lastAccessed.prev;
      Cell y = lastAccessed.next;
      x.next = y;
      y.prev = x;
      N--;
      index--;
      lastAccessed = null;
    }
    
    // add element to tape 
    public void add(Value value) {
      Cell x = current.prev;
      Cell y = new Cell();
      Cell z = current;
      y.value = value;
      x.next = y;
      y.next = z;
      z.prev = y;
      y.prev = x;
      N++;
      index++;
      lastAccessed = null;
    }
    
  }
  //*
  //TestTape test client
  public static void main(String[] args) {
    
    EasyTape<Character> tape = new EasyTape<Character>();
    for (int i = 0; i < "World".length(); i++) tape.add("World".charAt(i));
  
    //print the tape's initial contents
    for (Character x : tape) System.out.print("<" + x + ">");
    System.out.println();
    
    ListIterator<Character> iterator = tape.iterator();
   
    //go backwards to the tape beginning.
    while (iterator.hasPrevious()) {char x = iterator.previous();}
   
    //continue backwards adding Cells containing chars spelling "Hello "
    for (int j = 0; j < "Hello ".length(); j++) iterator.add("Hello ".charAt(j));
    
    //print contents of tape as required.
    System.out.print("Tape Contents:  ");
    for (Character x : tape) System.out.print(x);
    System.out.println();
    
    //move forward to the tape end.
    while (iterator.hasNext()) {char x = iterator.next();}
    //print value of the last Cell
    System.out.println("Final position at the " + iterator.previous());
  }
  //*/
  /*
   // another test client, this one came with the original program.   
  public static void main(String[] args) {
   //int N  = Integer.parseInt(args[0]);
   int N  = 5;
   
   
   // add elements 1, ..., N
   EasyTape<Integer> tape = new EasyTape<Integer>();
   for (int i = 0; i < N; i++)
   tape.add((int) (100 * Math.random()));
   
   // try out the iterator
   for (Integer x : tape)
   System.out.print(x + " ");
   System.out.println();
   
   ListIterator<Integer> iterator = tape.iterator();
   
   // go forwards
   while (iterator.hasNext()) {
   int x = iterator.next();
   iterator.set(x + 1);
   }
   
   // print contents of tape
   for (Integer x : tape)
   System.out.print(x + " ");
   System.out.println();
   
   // go backwards
   while (iterator.hasPrevious()) {
   int x = iterator.previous();
   iterator.set(x + x + x);
   }
   
   // print contents of tape
   for (Integer x : tape)
   System.out.print(x + " ");
   System.out.println();
   
   // remove all even elements
   while (iterator.hasNext()) {
   int x = iterator.next();
   if (x % 2 == 0) iterator.remove();
   }
   
   // print contents of tape
   for (Integer x : tape)
   System.out.print(x + " ");
   System.out.println();
   
   }
   */
}