Preserving encapsulation of a generic in Java

Question

Good evening.

I have a rather involved question. To practice Java, I've been re-implementing some of the data structures in the standard library. Stacks, LinkedLists, Trees, etc. I just established, through a very simple example, that the java.util.Stack class performs a deep copy when either the peek() or pop() methods are used. This is understandable, since the goal would be to protect the contents of the class from outside interference. So far, in my own implementation of the Stack (a naive implementation with a simple array, linked lists will come later), I have not cared for this at all:

public class ArrayStack<T> implements Stack<T> {
    private T[] data; // Will expand the array when stack is full.
    private int top; // serves as both top and count indicator.
    ...
    ...
   @Override
   public T pop() throws EmptyStackException {
    if(top == -1)
        throw new EmptyStackException("Stack is empty.");
    return data[top--]; // Shallow copy, dangerous!
}

Unfortunately, since a generic cannot be instantiated, I cannot assume a copy constructor and do stuff like return new T(data[top--]); I've been looking around in S.O and I've found two relevant threads which attempt to solve the problem by using some variant of clone(). This thread suggests that the class's signature be extended to:

public class ArrayStack<T extends DeepCloneableClass> implements Stack<T>
...

where DeepCloneableClass is a class that implements an interface that allows for "deep cloning" (see the top response in that thread for the relevant details). The problem with this method, of course, is that I can't really expect from standard classes such as String or Integer to be extending that custom class of mine, and, of course, all my existing jUnit tests are now complaining at compile-time, since they depend on such Stacks of Integers and Strings. So I don't feel as if this solution is viable.

This thread suggests the use of a third-party library for cloning pretty much any object. While it appears that this library is still supported (latest bug fixes date from less than a month ago), I would rather not rely on third-party tools and use whatever Java can provide for me. The reason for this is that the source code for these ADTs might be someday shared with undergraduate college students, and I would rather not have them burdened with installing extra tools.

I am therefore looking for a simple and, if possible, efficient way to maintain a generic Java data structure's inner integrity while still allowing for a simple interface to methods such as pop(), peek(), popFront(), etc.

Thanks very much for any help!

Jason

Answer 1

Why do you need to clone the objects?

Your stack just has a collection of references. You probably don't need to clone them, just make a new array and put the appropriate references in it, then throw away the old array.

Answer 2

Integer, Strings, etc are all immutable, so their contents are safe by design.

As for custom objects, while experienced Java Programmers will certain have mixed feelings about it, implementing a custom interface is certainly one way to approach the problem.

Another one is to make <T extends Serializable> (which is implemented by Integer, String, etc) and "clone" through serialization.

But if you want to teach your students the "right way" I would definitively use a third party library... You can just create a lib folder in your project and configure you build tool / IDE to add the needed jars to the Classpath using relative paths, so your undergraduate students will not have to install or setup anything.

Just for reference, this question may be very useful.

I've been teaching Java introductory classes (as an IT Instructor / not as a college Professor) using this kind of approach, and it is way less painful than it sounds.

Answer 3

The comments helped me understand what I had wrong. I was using the following example to "prove" to myself and others that the Java Standard Library's Collections do a deep copy when providing references to objects in the Collection:

import java.util.Stack;

public class StackTestDeepCopy {
    public static void main(String[] args){
        Stack<String> st = new Stack<String>();
        st.push("Jim");
        st.push("Jill");
        String top = st.peek();
        top = "Jack";
        System.out.println(st); 
    }
}

When printing st, I saw that objects had been unchanged, and concluded that a deep copy had taken place. Wrong! Strings are immutable, and therefore the statement top = "Jack" does not in any way modify the String (not that any Object would be "modified" by a statement like that, but I wasn't thinking straight), it just makes the reference point to a new place on the heap. A new example, involving an actually mutable class, made me understand the error in my ways.

Now that this problem has been solved, I'm quite baffled by the fact that the standard library allows for this. Why is it that accessing elements in the standard library is implemented as a shallow copy? Sounds very unsafe.

Answer 4

java.util.Stack doesn't do a deep copy:

import java.util.Stack;
public class Test {
    String foo;
    public static void main(String[] args) {
        Test test = new Test();
        test.foo = "bar";
        Stack<Test> stack = new Stack<Test>();
        stack.push(test);
        Test otherTest = stack.pop();
        otherTest.foo = "wibble";
        System.out.println("Are the same object: "+(test.foo == otherTest.foo));
    }
}

Results in:

Are the same object: true

If it did do a copy then test and otherTest would point to a different object. A typical stack implementation simply returns a reference to the same object that was added onto the stack, not a copy.

---

You probably also want to set the array item to null before returning, otherwise the array will still hold a reference to the object.