5
\$\begingroup\$

I have this contract:

public interface Stack<T> {
    void push(T object);
    T pop();
    int size();
}

I am curious what you think about my test of the size() and pop() in order to prevent bugs (underlying data structure in not being cleaned) in implementation like below:

Implementation:

public class StackImpl implements Stack<Object> {
    private int size;
    private Object data[];
    @Override
    public void push(Object object) {
        data[size] = object;
        size++;
    }
    @Override
    public Object pop() {
        --size;
        return data[size];
    }
    @Override
    public int size() {
        return size;
    }
}

Test:

public class StackTest {
    @Test
    public void pushTwoObjectsToEmtyStackCheckThatSizeIsTwo() {
        pushObjectsInOrder(OBJECT_A, OBJECT_B);
        assertEquals(2, stack.size());
    }
    @Test
    public void pushTwoObjectToEmptyStackAndPopTheSameObjectsInReversedOrder() {
        pushObjectsInOrder(OBJECT_A, OBJECT_B);
        assertEquals(OBJECT_B, stack.pop());
        assertEquals(OBJECT_A, stack.pop());
    }
    @Test(expected=IllegalArgumentException.class)
    public void stackDoesntAcceptNullAndThrowExcpetion() {
        stack.push(null);
    }
    @Before
    public void setUp() throws Exception {
        stack = new StackImpl();
    }
    private void pushObjectsInOrder(Object... objects) {
        for (Object object : objects) {
            stack.push(object);
        }
    }
    private static final Object OBJECT_A = new Object();
    private static final Object OBJECT_B = new Object();
    private Stack<Object> stack;
}

I'd like to not focus too much on the implementation itself, like whether it should be List or array etc. Assume that you defined interface and going to give to implement it to other guy. Since you defined the contract you are the one who writes a unit test.

\$\endgroup\$
  • 1
    \$\begingroup\$ Code Review is for reviewing code. If the code does not exist, it's not ready for review. Where are your tests? \$\endgroup\$ – rolfl Jan 21 '15 at 15:11
  • \$\begingroup\$ Thanks guys for pointing. Sorry for you time. Now I've fixed. Please review. \$\endgroup\$ – magulla Jan 21 '15 at 17:37
  • 2
    \$\begingroup\$ @magulla I have edited your question to make it more on-topic for Code Review. I hope the question still matches your intentions. On Code Review, it is better to ask "What do you think of my approach?" \$\endgroup\$ – Simon Forsberg Jan 21 '15 at 17:45
5
\$\begingroup\$

Here are some tests I'd perform at the very least. There may be more you'd want:

  1. Create an empty Stack. Test that its size is 0.
  2. Push an element onto the stack. Test that its size is now 1.
  3. Push another element onto the stack. Test that its size is now 2.
  4. Pop an element from the stack. Test that it matches the 2nd pushed value. Check that the size of the stack is now 1.
  5. Pop an element from the stack. Test that it matches the 1st pushed value. Check that the size of the stack is 0.
  6. Attempt to pop an element from the stack. You should receive an ArrayIndexOutOfBounds exception.
\$\endgroup\$
  • \$\begingroup\$ Thanks Phil, that's very useful answer, however I'm still interested how would you write a test to prevent memory leak. \$\endgroup\$ – magulla Jan 21 '15 at 17:39
  • \$\begingroup\$ @magulla I think you commented on the wrong answer. \$\endgroup\$ – David Harkness Jan 22 '15 at 2:46
  • \$\begingroup\$ @David Harkness i mean this answer, since it was first advice about ArrayIndexOutOfBounds. though i thing this exception should be wrapped with you own exception. \$\endgroup\$ – magulla Jan 22 '15 at 16:22
  • \$\begingroup\$ @magulla Oh, you asked about preventing the memory leak which janos had brought up in his answer. No worries. \$\endgroup\$ – David Harkness Jan 23 '15 at 22:03
4
\$\begingroup\$

@PhilWright made some good points. I would add:

  • Popping element from an empty stack should throw java.util.EmptyStackException
  • Test for memory leaks. Since the Stack is in charge of managing its own memory, this is a real concern. A common memory leak in stack implementations is when removed elements are not nulled out correctly.

Here's one way to verify that pop cleans up after the removed object, based on @DavidHarkness' idea in comments, using a WeakReference:

@Test
public void testPopCleansUpReference() {
    Object value = new Object();
    WeakReference<Object> reference = new WeakReference<>(value);

    Stack<Object> stack = new StackImpl();
    stack.push(value);
    value = null;

    stack.pop();
    Runtime.getRuntime().gc();
    assertNull(reference.get());
}

The current implementation fails this test, because this implementation only decreases the size variable, the popped object remains inside the data array:

@Override
public Object pop() {
    --size;
    return data[size];
}

For the record, the fix is simple enough:

@Override
public Object pop() {
    Object result = data[--size];
    data[size] = null;
    return result;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ You may be able to use a WeakReference to detect a memory leak. My reading of the docs say that when the GC is performed, all weakly-referenced objects will be removed immediately. \$\endgroup\$ – David Harkness Jan 22 '15 at 2:53
  • \$\begingroup\$ @janos 1. If your read my question, you'll see that I've mention about memory leak "(underlying data structure in not being cleaned)". 2. Agree that you need to throw proper exception. java.util.EmptyStackException - I wouldn't agree. You probably mean to say to have your own exception like EmptyStackException. Not java.util.EmptyStackException - because it used y Java Stack, and it's stated in JavaDoc. 3. Your hint to test memory leak is interesting. But I doubb't it would work, If you run multiple tests in parallel. \$\endgroup\$ – magulla Jan 22 '15 at 16:29
  • 1
    \$\begingroup\$ Thanks @DavidHarkness, I rewrote my post to use your tip instead of my crappy previous solution \$\endgroup\$ – janos Jan 22 '15 at 20:56
  • \$\begingroup\$ Hi @magulla, I largely rewrote my unit testing recommendation for the memory leak. But I don't see your point with java.util.EmptyStackException. Are you implying it's reserved for java.util.Stack to throw? If that was the intention, I'd think it would be a nested class in java.util.Stack. Am I missing something? \$\endgroup\$ – janos Jan 22 '15 at 21:01
  • 1
    \$\begingroup\$ @magulla The JVM will perform garbage collection before throwing an OutOfMemoryError, and the docs for WeakReference state that during GC any weakly-reachable object will be collected and all weak references to it cleared. Thus, holding a weak reference cannot cause an OOM. \$\endgroup\$ – David Harkness Jan 25 '15 at 20:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.