Problem with List<E>

[leverin4]

I'm working on a program to find a way out of a series of underground tunnels. The LinearStructure Interface and the Location Class were written for me and I wrote the LinearStack and LinearQueue Classes, and they are working fine (as far as I can tell). My problem comes in when I run the getOutOfTunnel method. I get a null pointer method the first time the isExit(Location) method is ran, and I can't figure out why. I've included what I think are the important classes below. Let me know if I should post something else. The nullPointerException is thrown at line 134 of Map.java, which is a call to the method at line 55. Why is there a null pointer? Thanks in advance.

Map.java:

import java.io.*;
import java.util.*;

public class Map {
	private int width, height;
	private Position[][] map;
	private boolean foundExit;
	private LinearStructure<Location> steps = null;
	
	public Map (File f) throws IOException {
		String line;
		StringTokenizer tok;
		char temp;
		
		BufferedReader fin = new BufferedReader(new FileReader(f));
		tok = new StringTokenizer(fin.readLine());
		height = Integer.parseInt(tok.nextToken());
		width = Integer.parseInt(tok.nextToken());
		map = new Position[getHeight()][getWidth()];
		
		try {
			for (int row = 0; row < getHeight(); row++) {
				line = fin.readLine();
				for (int col = 0; col < getWidth(); col++) {
					temp = line.charAt(col);
					if (temp == 'D' || temp == 'S' || temp == 'E' || temp == 'T') {
						map[row][col] = new Position(temp);
					}
					else {
						throw new InvalidMapException();
					}
				}
			}
			fin.close();
		}
		catch (InvalidMapException ime) {
			System.out.println("'" + f + "' Contains An Invalid Character.");
			System.out.println("Please Check '" + f + "' And Try Again.");
		}
		catch (IndexOutOfBoundsException ioobe) {
			System.out.println("'" + f + "' Contains A Ragged Map.");
			System.out.println("Please Check '" + f + "' And Try Again.");
		}
	}
		
	public int getWidth() {
		return width;
	}
	
	public int getHeight() {
		return height;
	}
	
	public boolean isExit(Location pt) {
		return (map[pt.getRow()][pt.getColumn()].getType() == 'E');
	}
	
	public boolean isStart(Location pt) {
		return (map[pt.getRow()][pt.getColumn()].getType() == 'S');
	}
	
	public boolean isTraversable(Location pt) {
		return (map[pt.getRow()][pt.getColumn()].getType() == 'T');
	}
	
	public List<Location> getExits() {
		ArrayList<Location> exits = new ArrayList<Location>();
		int capacity = 10;
		for (int row = 0; row < getHeight(); row++) {
			for (int col = 0; col < getWidth(); row++) {
				if (exits.size() == capacity) {
					exits.ensureCapacity(capacity + 10);
					capacity += 10;
				}
				if (map[row][col].getType() == 'E') {
					exits.add(new Location(row, col, null));
				}
			}
		}
		exits.trimToSize();
		return exits;
	}
	
	public Location getStart() {
		Location start = null;
		int count = 0;
		
		try {
			for (int row = 0; row < getHeight(); row++) {
				for (int col = 0; col < getWidth(); col++) {
					if (map[row][col].getType() == 'S') {
						start = new Location(row, col, null);
						count++;
					}
					if (count > 1) {
						throw new InvalidMapException();
					}
				}
			}
			return start;
		}
		catch (InvalidMapException ime) {
			System.out.println("Map Contained More Than One Start.");
			System.out.println("Please Check Data And Try Again.");
			return null;
		}
	}
	
	public boolean hasBeenVisited(Location pt) {
		return map[pt.getRow()][pt.getColumn()].beenVisited();
	}
	
	public void visit(Location pt) {
		map[pt.getRow()][pt.getColumn()].visit();
	}
	
	public List<Location> getOutOfTunnel(boolean useStack) {
		ArrayList<Location> path = new ArrayList<Location>();
		Location start = getStart(), current;
		LinearStructure<Location> steps;
		int capacity = 10;
		
		if (useStack) {
			steps = new LinearStack<Location>();
		}
		else {
			steps = new LinearQueue<Location>();
		}
		
		steps.add(getStart());
		
		while (!steps.isEmpty()) {
			current = steps.remove();
			if (isExit(current)) {
				while (current != null) {
					if (path.size() == capacity) {
						path.ensureCapacity(capacity + 10);
						capacity += 10;
					}					
					path.add(0, current);
					current = current.getFrom();
				}
				path.trimToSize();
				return path;
			}
			else if (isTraversable(current) && !hasBeenVisited(current)) {
				visit(current);
				steps.add(current.getLocation(current, Direction.EAST));
				steps.add(current.getLocation(current, Direction.SOUTH));
				steps.add(current.getLocation(current, Direction.WEST));
				steps.add(current.getLocation(current, Direction.NORTH));
			}
		}
		return path;
	}
}

Location.java:

public class Location {
  private int row, col;
  private Location from;

  public Location(int row, int col, Location from) {
    this.row = row;
    this.col = col;
    this.from = from;
  }

  public String toString() {
    return "("  + col + "," + row + ")";
  }

  public Location getLocation(Location from, Direction d) {
    switch(d) {
      case EAST: return new Location(row, col+1, from);
      case SOUTH: return new Location(row+1, col, from);
      case WEST: return new Location(row, col-1, from);
      case NORTH: return new Location(row-1, col, from);
      default: return null;
    }
  }

  public int getColumn() {
    return col;
  }

  public boolean equals(Object other) {
    if(other instanceof Location ){
      Location loc = (Location)other;
      return loc.row == row && loc.col == col;
    }
    return false;
  }

  public Location getFrom() {
    return from;
  }

  public int getRow() {
    return row;
  }

}

Position.java:

public class Position {
	private char type;
	private boolean hasBeenVisited;
	
	public Position(char t) {
		type = t;
		hasBeenVisited = false;
	}
	
	public char getType() {
		return type;
	}
	
	public void visit() {
		hasBeenVisited = true;
	}
	
	public boolean beenVisited() {
		return hasBeenVisited;
	}
	
	public String toString() {
		return ("" + type);
	}
}

[BestJewSinceJC]

Location start = getStart(), current;

You should check that that line is doing what you want it to.

[leverin4]

I figured it out, kind of. There is definitely something wrong with my Stack, and possibly something with my queue. Would you mind looking them over and seeing if you can see it? I've looked over them line by line twice, and everything looks fine to my untrained eyes.

LinearStructure.java:

import java.util.NoSuchElementException;
public interface LinearStructure<E> {
	public int size();
	public boolean add(E e);
	public E remove() throws NoSuchElementException;
	public boolean isEmpty();
	public E peek() throws NoSuchElementException;
	public void print();
	public void clear();
}

LinearStack.java:

import java.util.NoSuchElementException;

public class LinearStack<E> implements LinearStructure<E> {
	private Object[] data;
	private int top;
	
	public LinearStack() {
		top = 0;
		data = new Object[1000];
	}
	
	public int size() {
		return top;
	}
	
	public boolean add(E e) {
		if (size() == data.length) {
			resize();
		}
		try {
			data[top] = e;
			top++;
		}
		catch (Exception ex) {
			return false;
		}
		return true;
	}
	
	public E remove() throws NoSuchElementException {
		if(!isEmpty()) {
			E temp = (E)data[top--];
			data[top] = null;
			return temp;
		}
		else {
			throw new NoSuchElementException();
		}
	}
	
	public boolean isEmpty() {
		return (top == 0);
	}
	
	public E peek() throws NoSuchElementException {
		try {
			return (E)data[top-1];
		}
		catch (ArrayIndexOutOfBoundsException aioobe) {
			throw new NoSuchElementException();
		}
	}
	
	public void print() {
		for (int i = top-1; i >= 0; i--) {
			System.out.println(data[i]);
		}
	}
	
	public void clear() {
		for (int i = 0; i < size(); i++) {
			data[i] = null;
		}
		top = 0;
	}
	
	private void resize() {
		final int INCREMENT = 1000;
		Object[] temp = new Object[size() + INCREMENT];
		for (int i = 0; i < size(); i++) {
			temp[i] = (E)data[i];
		}
		data = temp;
	}
}

[BestJewSinceJC]

I took a look but I didn't see anything wrong at first glance. Got tired of looking after a couple minutes though. We aren't really here to debug your code. . most people will not do it at all. You should write tests for each method to make sure they are performing as expected. Figure out the first method that has a problem, then post back here again telling us what method the problem is in, what it is supposed to do, and any other info you have.

[leverin4]

You're right, I apologize. Wasn't thinking when I asked that. I wrote a short test program that just tested add() and remove() in the stack. It's definitely in remove(), since the code below just printed null 50 times, but it looks like it should work to me.

public class StackTest {

	public static void main(String args[]) {	
		LinearStack<String> stack = new LinearStack<String>();
		for (int i = 1; i <= 50; i++) {
			stack.add(""+i);
		}
		
		while (!stack.isEmpty()) {
			System.out.println(stack.remove());
		}
	}
}

[BestJewSinceJC]

I don't see any problems with your add method. The code in your remove method looks far more complicated than it needs to be. Your 'last' variable already tells you where the last element is (it is at that index last-1) so all you need to do when removing an element is check to see if last > 0 and remove & return the element at the index last-1. Don't forget to do last-- also since you no longer have an element there.

[BestJewSinceJC]

wait, nevermind. Your code confused me. Your class is a Queue class but you called it 'stack' so I thought it was LIFO. Forget what I said.

[leverin4]

I think you looked at the queue. I just removed it from the post it was in, because the same code I used for the stack worked fine with a queue. The queue had a variable called last, which is why I think you checked my methods there, and stack has one called top. I really appreciate your help thus far. I've made quite a bit of progress.

EDIT:

wait, nevermind. Your code confused me. Your class is a Queue class but you called it 'stack' so I thought it was LIFO. Forget what I said.

Ok, haha, sorry. I originally posted way more code than I needed to.

[BestJewSinceJC]

Ok. I think I see a problem:

E temp = (E)data[top--];
data[top] = null;
return temp;

You set temp to the element at top, then you subtracted one from top, then you set top to null. What you should be doing is setting temp to the element at top, setting top to null, then subtracting one from top. (Which would look like):

E temp = (E)data[top];
data[top--] = null;
return temp;

[leverin4]

That did it. I've been working on this too long. Thanks for your help. +Rep for you.

[BestJewSinceJC]

See my post above. .

edit:

No problem, glad I could help. Your code looks good, by the way.