immutable stack implementation

[Jerry Oreganini]

Hi.. I am trying to work on some exercises that I found that seem to be pretty good for learning some interesting things about Java. The one I am on now is to implement an immutable Stack. I wanted to see if you can critique my implementation and let me know what I could do better or correct if it is wrong. Here is what I have so far. The original implementation was from Bloch's book. The method repOk is supposed to be used for the jUnit tests I have written. I have those written too now to test each method and they pass the tests but I want more feedback if possible, please.

Thanks!

import java.util.*;
import java.lang.IllegalArgumentException;

/**
 * Immutable stack implementation
 *
 */
public final class Stack {

	private Object[] elements;
	private int size = 0;

	// don't really need this anymore.
	// private static final int DEFAULT_INITIAL_CAPACITY = 16;

	/**
    * 
    */
	public Stack() {
		this.elements = new Object[] {};
	}

	/**
	 * 
	 * @param newObject
	 * @param elements
	 */
	private Stack(Object newObject, Object[] existingElements) {

		if (newObject == null) {
			throw new IllegalArgumentException(
					"Cannot add null element to stack.");
		}

		// this.elements = new Object[DEFAULT_INITIAL_CAPACITY];
		this.elements = new Object[] {};
		
		this.size = 0;

		for (int i = 0; i < existingElements.length; i++) {
			// this.elements[i] = existingElements[i];
			Object copy = existingElements[i];

			if (copy != null) {
				ensureCapacity();
				this.elements[i] = copy;
				this.size++;
			}
		}

		// we know newObject is not null if we got here.
		ensureCapacity();

		this.elements[size] = newObject;
		this.size++;
	}

	/**
	 * To be used with pop() to return a new stack based off of the old stack's
	 * elements minus the top.
	 * 
	 * @param elementsToAdd
	 */
	private Stack(Object[] elementsToAdd) {
		
		this.elements = new Object[elementsToAdd.length];

		this.size = elementsToAdd.length;

		for (int i = 0; i < elementsToAdd.length; i++) {
			
			Object copy = elementsToAdd[i];

			if (copy != null) {
				this.elements[i] = copy;
			}
		}
	}

	/**
	 * 
	 * @return
	 */
	public boolean isEmpty() {
		if (this.size == 0) {
			return true;
		} else {
			return false;
		}
	}

	/**
	 * 
	 * @param e
	 * @return
	 */
	public Stack push(Object e) {

		if (e == null) {
			throw new IllegalArgumentException("Cannot push null object.");
		}

		Stack returnStack = new Stack(e, this.elements);

		return returnStack;
	}

	/**
	 * 
	 * @return
	 */
	public Stack pop() {

		if (size == 0) {
			throw new IllegalStateException("Stack.pop called on empty stack.");
		}
		
		//make new array that does not include "top" element.
		int newArraySize = this.size - 1;
		Object[] elementsMinusTop = new Object[newArraySize];
		
		for(int i = 0; i < newArraySize; i++) {
			elementsMinusTop[i] = this.elements[i];
		}
		
		Stack returnStack = new Stack(elementsMinusTop);
		
		return returnStack;
	}
	
	/**
	 * 
	 * @return top element of stack
	 */
	public Object top() {
		
		int topElementIndex = this.size - 1;
		
		Object topObjectCopy = this.elements[topElementIndex];
		
		return topObjectCopy;
	}

	// Ensure space for at least one more element
	private void ensureCapacity() {

		if (elements.length == size) {
			//original -- elements = Arrays.copyOf(elements, 2 * size + 1);
			elements = Arrays.copyOf(elements, size + 1);
		}
	}

	/**
	 * 
	 * @return
	 */
	public boolean repOk() {

		if (elements == null) {
			return false;
		}

		if (size != elements.length) {
			return false;
		}

		for (int i = 0; i < size; i++) {
			if (elements[i] == null) {
				return false;
			}
		}

		return true;
	}

	/**
    * 
    */
	public String toString() {
		// EFFECTS: Returns the String representation
		// of this Stack from the top to the bottom.

		StringBuffer buf = new StringBuffer("{");

		for (int i = size - 1; i >= 0; i--) {

			if (i < (size - 1)) {
				buf.append(", ");
			}

			buf.append(elements[i].toString());
		}

		buf.append("}");

		return buf.toString();
	}
}

[Stephan van Hulst]

Hi Jerry, here are a few things to consider.

- Your class is not generic. It would be far more useful if you parameterized it, so your client can push and pop objects of a specific type.
- Why should it be illegal to add null elements to a stack?
- Your Stack(Object, Object[]) constructor is incredibly inefficient. You are creating a new array for every element in the given object array, and copying all the elements. Why not just create the new array in one go?
- If the array argument contains null elements and you want to disallow them (again, I don't understand why), you can just throw an exception upon discovery of the first null element.
- Even if you don't want to throw an exception, you can just count the number of null objects in the given array first, and then still create the new array in one go.
- Why are the semantics of the Stack(Object[]) constructor so different from the former?
- Your isEmpty() method uses a lot of redundant code. Just return size == 0, or Campbell will eat you.
- I'm all for clarity and using lots of variables and all, but why not just have your top() method return elements[size -1]?
- Don't use StringBuffer, use StringBuilder.

Now I know this is an exercise, but consider how useful such a class would be. It would probably only be useful for defensive copying if you want to return a stack field from a method in another class, in which case you might as well return Collections.unmodifiableCollection(myStack), where myStack is an instance of the Deque interface. It's also very inefficient, because it achieves its immutability through lots of copying. To make it more efficient, you could consider letting all the instances that are derived from the same stack (through push and pop operations) share the same array. They can just keep some index fields around to tell them which part of the array is valid for them.

[Jerry Oreganini]

Thanks for your time and great advice. I will work on incorporating all of what you have said and post an updated one for further inspection.

[Jerry Oreganini]

Ok so it seems like maybe I was going overboard with this idea of copying the objects around to keep a client of the class from adding mutable objects to the stack and changing them after the fact. I thought that is a big concern here, no? Does this implementation still avoid that issue, i.e. a client adds date references to the immutable stack and changes them after they have been pushed?

Other than that, I think I incorporated everything you indicated. Does this look better?

Thanks again!

import java.util.*;
import java.lang.IllegalArgumentException;

/**
 * Immutable stack implementation
 *
 */
public final class Stack<T> {

	private Object[] elements;
	private int size = 0;

	/**
    * 
    */
	public Stack () {
		this.elements = new Object[] {};
	}

	/**
	 * 
	 * @param newObject
	 * @param elements
	 */
	private Stack(T newObject, Object[] existingElements) {

		this.elements = existingElements;
		this.size = existingElements.length;

		ensureCapacity();

		this.elements[size] = newObject;
		this.size++;
	}

	/**
	 * To be used with pop() to return a new stack based off of the old stack's
	 * elements minus the top.
	 * 
	 * @param elementsToAdd
	 */
	private Stack(Object[] elementsToAdd) {
		
		this.elements = elementsToAdd;

		this.size = elementsToAdd.length;
	}

	/**
	 * 
	 * @return
	 */
	public boolean isEmpty() {
		return this.size == 0;
	}

	/**
	 * 
	 * @param e
	 * @return
	 */
	public Stack<T> push(T e) {

		if (e == null) {
			throw new IllegalArgumentException("Cannot push null object.");
		}

		Stack<T> returnStack = new Stack<T>(e, this.elements);

		return returnStack;
	}

	/**
	 * 
	 * @return
	 */
	public Stack<T> pop() {

		if (this.size == 0) {
			throw new IllegalStateException("Stack.pop called on empty stack.");
		}
		
		//make new array that does not include "top" element.
		int newArraySize = this.size - 1;
		Object[] elementsMinusTop = new Object[newArraySize];
		
		for(int i = 0; i < newArraySize; i++) {
			elementsMinusTop[i] = this.elements[i];
		}
		
		Stack<T> returnStack = new Stack<T>(elementsMinusTop);
		
		return returnStack;
	}
	
	/**
	 * 
	 * @return top element of stack
	 */
	public Object top() {
		return this.elements[this.size - 1];
	}

	/**
	 *  Ensure space for at least one more element
	 */
	private void ensureCapacity() {

		if (elements.length == size) {
			//original -- elements = Arrays.copyOf(elements, 2 * size + 1);
			elements = Arrays.copyOf(elements, size + 1);
		}
	}

	/**
	 * 
	 * @return
	 */
	public boolean repOk() {

		if (elements == null) {
			return false;
		}

		if (size != elements.length) {
			return false;
		}

		for (int i = 0; i < size; i++) {
			if (elements[i] == null) {
				return false;
			}
		}

		return true;
	}

	/**
    * EFFECTS: Returns the String representation
    * of this Stack from the top to the bottom.
    */
	public String toString() {

		StringBuilder stringBuilder = new StringBuilder("{");

		for (int i = size - 1; i >= 0; i--) {

			if (i < (size - 1)) {
				stringBuilder.append(", ");
			}

			stringBuilder.append(elements[i].toString());
		}

		stringBuilder.append("}");

		return stringBuilder.toString();
	}
}

[Matthew Brown]

If someone wants to add mutable objects to the stack and change them later, there's absolutely nothing you can do about it. Your previous implementation wouldn't help there either, because you're never actually copying objects, just references. All you can do is make sure the stack itself is immutable.

[Jerry Oreganini]

Thanks, it all makes good sense now! I agree the usefulness of this is near zero but it has taught me a lot about what an immutable object can and can't do and how it should behave and look in the end. Your replies were very helpful.

[Stephan van Hulst]

I'm glad you figured things out for yourself

For comparison:

import java.util.*;

public final class ImmutableArrayStack<E> {

  private E[] elements;
  private int size;


  @SuppressWarnings("unchecked")
  public ImmutableArrayStack() {
    elements = (E[]) new Object[0];
    size = 0;
  }


  @SuppressWarnings("unchecked")
  public ImmutableArrayStack(Collection<E> c) {
    elements = (E[]) new Object[c.size()];
    size = c.size();

    int i = 0;
    for (E e: c)
      elements[i++] = e;
  }

  private ImmutableArrayStack(E[] elements) {
    this.elements = elements;
  }

  public boolean isEmpty() {
    return size == 0;
  }

  public ImmutableArrayStack<E> push(E e) {
    if (elements.length == size)
      elements = Arrays.copyOf(elements, elements.length *2 +1);

    elements[size] = e;
    ImmutableArrayStack<E> result = new ImmutableArrayStack<>(elements);
    result.size = size +1;
    return result;
  }

  public ImmutableArrayStack<E> pop() {
    if (isEmpty())
      throw new IllegalStateException("Empty stack");

    ImmutableArrayStack<E> result = new ImmutableArrayStack<>(elements);
    result.size = size -1;
    return result;
  }

  public E peek() {
    if (isEmpty())
      throw new IllegalStateException("Empty stack");

    return elements[size -1];
  }

  public String toString() {
    StringBuilder s = new StringBuilder("{");

    for (int i = 0; i < size; i++) {
      if (i > 0)
        s.append(", ");

      s.append(elements[i].toString());
    }

    s.append("}");
    return s.toString();
  }
}

Normally I would use an ArrayDeque though.