File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes Beginning Java and the fly likes immutable stack implementation Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Murach's Java Servlets and JSP this week in the Servlets forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "immutable stack implementation" Watch "immutable stack implementation" New topic
Author

immutable stack implementation

Jerry Oreganini
Greenhorn

Joined: Oct 04, 2006
Posts: 7
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!

Stephan van Hulst
Bartender

Joined: Sep 20, 2010
Posts: 3575
    
  14

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
Greenhorn

Joined: Oct 04, 2006
Posts: 7
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
Greenhorn

Joined: Oct 04, 2006
Posts: 7
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!

Matthew Brown
Bartender

Joined: Apr 06, 2010
Posts: 4341
    
    7

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
Greenhorn

Joined: Oct 04, 2006
Posts: 7
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
Bartender

Joined: Sep 20, 2010
Posts: 3575
    
  14

I'm glad you figured things out for yourself

For comparison:
Normally I would use an ArrayDeque though.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: immutable stack implementation
 
Similar Threads
Iterator Pattern
Memory Leaks
garbage collector
Filling Array