4
\$\begingroup\$

I am new to this Immutability concept and I have some coding experience in JAVA. Recently as a part of internship program, they gave me a 5-day task, which was to implement Immutable Queue. After some research I came with a solution which was given below. Can some review the code.

[Technically your are not helping me in my internship process as it was over a while ago and I didn't got selected for the next round. So as per the rules of it there is no restriction on publishing the code after the process completion.]

ImmutableQueue.java

import java.util.NoSuchElementException;

public class ImmutableQueue<E> {

    private final class ImmutableEmptyQueue extends ImmutableQueue<E>{  //sub class for Empty queue

        public ImmutableEmptyQueue(){                                   //Constructor for the ImmutableEmptyQueue
            super(null, null);
        }
        public ImmutableQueue<E> enqueue(E e){                          //Enqueue operation on EmptyQueue
            if(e==null){
                throw new IllegalArgumentException();                   //if no argument passed throws exception
            }
            return new ImmutableQueue<E>(forward , backward.push(e));
        }
        public ImmutableQueue<E> dequeue(){                             //Dequeue operation on EmptyQueue
            throw new NoSuchElementException();                         //throws exception
        }
        public E peek(){                                                //returns the first object
            if(this.IsEmpty()){                                         //if empty throws exception
                throw new IllegalArgumentException();
            }
            return null;
        }
        public int size(){                                              //return size zero
            return 0;
        }
        public boolean IsEmpty(){                                       //Check if empty or not
            return true;
        }

    }

    private final ImmutableStack<E> forward;                            //forward queue
    private final ImmutableStack<E> backward;                           //backward queue

    private final ImmutableEmptyQueue empty = new ImmutableEmptyQueue();//ImmutableEmptyQueue object
    public  final ImmutableQueue<E> Empty = empty;                      //ImmutableQueue object which is empty

    public ImmutableQueue(ImmutableStack<E> forward, ImmutableStack<E> backward){//Constructor of the ImmutableQueue<E> class
        this.forward = forward;
        this.backward = backward;
    }

    public ImmutableQueue<E> enqueue(E e){                              //Enqueue operation of the Immutable Queue

        if(e==null){                                                    //if no valid argumnet passed throws error
            throw new IllegalArgumentException();
        }

        return new ImmutableQueue<E>(forward , backward.push(e));       //return new Queue
    }

    public ImmutableQueue<E> dequeue(){                                 //Dequeue Operation of the Immutable Queue
        if(this.IsEmpty()){
            throw new NoSuchElementException();                         //if queue is empty throw error
        }
        ImmutableStack<E> f = forward.pop();                            //top object removed from the forward stack
        if(!f.IsEmpty()){
            return new ImmutableQueue<E>(f , backward);                 //new ImmutableQueue formed
        }
        else if(backward.IsEmpty()){
            return new ImmutableEmptyQueue();                           //new ImmutableEmptyQueue
        }
        else{

            return new ImmutableQueue<E>(backward.Reverse(),(new ImmutableStack<E>(null,null)).Empty);//new ImmutableQueue with backward stack empty
        }
    }

    private boolean IsEmpty() {
        return (forward.IsEmpty() && backward.IsEmpty());               //Checks Whether the queue is empty or not
    }

    public E peek(){        
        return forward.peek();                                          //removes the first object from the ImmutableQueue
    }

    public int size(){
        return (forward.Size()+backward.Size());                        //return the size of the ImmutableQueue
    }

}

class ImmutableStack<E>{

    private final class ImmutableEmptyStack extends ImmutableStack<E> { //Immutable Empty Stack class 

        public ImmutableEmptyStack() {                                  //Constructor for Immutable Empty Stack
            super(null, null); 
        }
        public ImmutableStack<E> pop(){                                 //Pop Operation
            if(this.IsEmpty()){
                throw new NoSuchElementException();
            }
            return null;
        }
        public ImmutableStack<E> push(E e){                             //Push Operation

            if(e==null){
                throw new IllegalArgumentException();
            }

            return new ImmutableStack<E>(e,this);
        }
        public E peek(){                                                //Peek Operation
            if(this.IsEmpty()){
                throw new NoSuchElementException();
            }
            return null;
        }
        public boolean IsEmpty(){                                       //Checks whether any element present in the EmptyStack
            return true;
        }
        public int Size(){                                              //Size of the EmptyStack
            return 0;
        }

    }

    private final E head;                                               //head of the stack
    private final ImmutableStack<E> tail;                               //tail or the body of the stack is implemented as a stack

    private final ImmutableEmptyStack empty = new ImmutableEmptyStack();//Creating object of the ImmutableEmptyStack
    public  final ImmutableStack<E> Empty = empty;                      //Creating an EmptyImmutableStack

    public ImmutableStack(E head, ImmutableStack<E> tail){              //Constructor to build the ImmutableStack with two arguments 

        this.head = head;
        this.tail = tail != null ? tail : new ImmutableEmptyStack();    //if no tail is present add the ImmutableEmptyStack as the Tail
    }

    public ImmutableStack<E> pop(){                                     //return the tail of the stack

        if(this.IsEmpty()){
            throw new NoSuchElementException();                         //if no element exists throw exception
        }

        return this.tail;
    }

    public ImmutableStack<E> push(E e){                                 //Push Operation of the Stack                           

        if(e==null){
            throw new IllegalArgumentException();                       
        }

        return new ImmutableStack<E>(e , this);
    }

    public E peek(){                                                    //return the head of the stack

        if(this.IsEmpty()){                                             //if no element exists throw exception
            throw new NoSuchElementException();
        }

        return this.head;
    }

    public boolean IsEmpty(){                                           //Check if any element exists or not in the Stack

        return (head==null && tail==null);
    }

    public int Size(){                                                  //Return the Size of the Stack

        if(IsEmpty())
            return 0;
        else
            return (1+tail.Size());
    }

    public ImmutableStack<E> Reverse(){                                 //reverse the stack and point it to the same

        ImmutableStack<E> reversedstack = new ImmutableEmptyStack();    //resultant reverse Immutable Stack initialization
        ImmutableStack<E> temp = this;                                  //temporary Immutable Stack

        while(!(temp instanceof ImmutableStack.ImmutableEmptyStack)){   //Adding the non empty instances of temp into reversedstack

            reversedstack = reversedstack.push(temp.peek());
            temp = temp.pop();
        }

        return reversedstack;

    }
}
\$\endgroup\$
5
\$\begingroup\$
  1. This code assumes that all empty stacks are instances of ImmutableEmptyStack, but the public constructor allows code to create a new ImmutableStack that happens to be empty, so it would be better to use temp.IsEmpty()

    while(!(temp instanceof ImmutableStack.ImmutableEmptyStack)){
    
  2. It would be better to make the empty values static members, so you'd need to make the nested classes static too. This will save memory and also prevent code changes from accessing the surrounding ImmutableQueue / ImmutableStack fields. It would be even better to put the empty classes each in their own file, i.e. not a nested class.

    private static final class ImmutableEmptyQueue extends ImmutableQueue<E>{
    
    private static final ImmutableEmptyQueue empty = new ImmutableEmptyQueue();
    
    private final class ImmutableEmptyStack extends ImmutableStack<E> {
    
    private static final ImmutableEmptyStack empty = new ImmutableEmptyStack();
    
  3. Java coding conventions say to start method names with a lower case letter, so isEmpty() instead of IsEmpty().

  4. If you've made the empty values static, then you can even make the constructors private: then to use this class you always start with e.g. ImmutableQueue.empty and build it up using calls to enqueue(value).

\$\endgroup\$
4
\$\begingroup\$

First, let's get some general remarks out of the way:

  • Stop writing useless comments. Every single one of your comments was superfluous clutter that added no insight to the code.
  • Respect Java naming conventions.

I'll review ImmutableStack first. There are two cases: the empty stack and non-empty stacks. I see that you have made an attempt to implement the special case for the empty stack. However, you will have a better time if you reverse the inheritance. Think of it this way: the public should be able to make an empty stack, but all non-empty stacks should only be create using .push(). Furthermore, the empty stack is simpler: it has no "next" pointer.

import java.util.NoSuchElementException;

class ImmutableStack<E> {

    private class NonEmpty extends ImmutableStack<E> {
        private final E head;
        private final ImmutableStack<E> tail;
        private final int size;

        private NonEmpty(E head, ImmutableStack<E> tail) {
            this.head = head;
            this.tail = tail;
            this.size = 1 + tail.size();
        }

        @Override
        public ImmutableStack<E> pop() {
            return this.tail;
        }

        @Override
        public E peek() {
            return this.head;
        }

        @Override
        public boolean isEmpty() {
            return false;
        }

        @Override
        public int size() {
            return this.size;
        }
    }

    public ImmutableStack<E> pop() {
        throw new NoSuchElementException();
    }

    public ImmutableStack<E> push(E e) {
        if (e == null) {
            throw new IllegalArgumentException();                       
        }
        return new NonEmpty(e, this);
    }

    public E peek() {
        throw new NoSuchElementException();
    }

    public boolean isEmpty() {
        return true;
    }

    public int size() {
        return 0;
    }
}

A stack does not traditionally offer a reverse() operation, because the data structure is not designed to do it efficiently. If you need to reverse a stack, you can do so using its public methods, so I recommend that you leave this code outside of the stack class.

public static <E> ImmutableStack<E> reverse(ImmutableStack<E> stack) {
    ImmutableStack<E> rev = new ImmutableStack<E>();
    for (ImmutableStack<E> fwd = stack; !fwd.isEmpty(); fwd = fwd.pop()) {
        rev = rev.push(fwd.peek());
    }
    return rev;
}

Implementing the queue in terms of two stacks does not make much sense. You would be much better off with an independent implementation.

\$\endgroup\$
  • \$\begingroup\$ Inverting the inheritance is really elegant. This is a really traditional way to implement an immutable queue. The benefit is that you get O(1) enqueue and O(1) amortized dequeue operations. \$\endgroup\$ – Harold L Jan 27 '15 at 22:06

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.