I have been developing an Immutable queue in java, but the version I have developed is supposedly slow and I have been suggested to create a faster version of the same and I have no idea as to how to accomplish that.
import java.util.ArrayList;
import java.util.List;
import java.util.NoSuchElementException;
public class ImmutableQueueImpl<E> implements ImmutableQueue<E>
{
private List<E> queue;
public ImmutableQueueImpl()
{
queue=new ArrayList<E>();
}
public ImmutableQueueImpl(List<E> queue)
{
this.queue=queue;
}
public ImmutableQueue<E> enqueue(E e)
{
if(e==null) throw new IllegalArgumentException();
List<E> clone = new ArrayList<E>(queue);
clone.add(e);
return new ImmutableQueueImpl<E>(clone);
}
public ImmutableQueue<E> dequeue()
{
if(queue.isEmpty())
{
throw new NoSuchElementException();
}
List<E> clone = new ArrayList<E>(queue);
clone.remove(0);
return new ImmutableQueueImpl<E>(clone);
}
public E peek()
{
if(queue.isEmpty()) throw new NoSuchElementException();
return queue.get(0);
}
public int size()
{
return queue.size();
}
}
Please suggest any improvements in the implementation or the libraries used .
We remove elements from immutable lists all the time and dequeue is just a special case of that. The point is that the result is not really the element, but another immutable list without it. The point of this design is mutation safety and way better in parallelized settings than mutable data structures.
8
You should read up on structure sharing for immutable datatypes. Obviously, when your enqueue involves creating a complete clone of that list, then your enqueue is O(n). The whole idea of structure sharing is that you return a new object, that in some way reuses the original object such as to avoid this duplication.
For your queue implementation in particular, you cannot simply rely on a mutable Java ArrayList. Take a look at some functional language and cons-cells for constructing immutable list datastructures. They allow you to simply keep track of start and end elements of your queue and derive a new queue object by reusing all cons-cells and simply adding a new one. The new object reuses the original cons-cells, but has a different end-pointer to the newly added cons cell.
Long story short: When writing immutable datastructures avoid copies and share structures instead.
In response to the comment about Java: All of this is language-agnostic. It is just that functional languages have been working with immutable datastructures for decades, whereas it is a relatively recent trend to add immutability to OO languages. All of this structure sharing, cons-cells, etc. is implementable in any programming language (well, Turing-complete that is).
3
This is an untested sketch of the usual functional implementation. First you need immutable Lists:
import java.util.Iterator;
import java.util.NoSuchElementException;
public class ImmutableList<T> implements Iterable<T> {
@SuppressWarnings("unchecked")
private final static ImmutableList NIL = new ImmutableList(null, null);
public final T head;
public final ImmutableList<T> tail;
public ImmutableList(T head, ImmutableList<T> tail) {
this.head = head;
this.tail = tail;
}
public ImmutableList<T> add(T t) {
return new ImmutableList<T>(t, this);
}
public boolean isEmpty() {
return this == NIL;
}
public ImmutableList<T> reverse() {
ImmutableList<T> result = nil();
for (T t : this) {
result = result.add(t);
}
return result;
}
@SuppressWarnings("unchecked")
public static <T> ImmutableList<T> nil() {
return NIL;
}
@Override
public Iterator<T> iterator() {
return new Iterator<T>() {
private ImmutableList<T> list = ImmutableList.this;
@Override
public boolean hasNext() {
return !list.isEmpty();
}
@Override
public T next() {
if (!hasNext()) throw new NoSuchElementException();
T t = list.head;
list = list.tail;
return t;
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
};
}
}
Then you take two lists. The front one is for enqueueing items, the back one is for dequeueing. If the back one gets empty, the reversed front becomes the new back.
import java.util.NoSuchElementException;
public class ImmutableQueue<T> {
private final ImmutableList<T> front;
private final ImmutableList<T> back;
private ImmutableQueue(ImmutableList<T> front, ImmutableList<T> back) {
this.front = front;
this.back = back;
}
public static <T> ImmutableQueue<T> empty() {
return new ImmutableQueue<T>(ImmutableList.<T>nil(), ImmutableList.<T>nil());
}
public boolean isEmpty() {
return front.isEmpty() && back.isEmpty();
}
public ImmutableQueue<T> enqueue(T t) {
return new ImmutableQueue<T>(front.add(t), back);
}
public DequeueResult<T> dequeue(T t) {
if (isEmpty()) throw new NoSuchElementException();
if (back.isEmpty()) {
ImmutableList<T> tnorf = front.reverse();
return new DequeueResult<T>(tnorf.head, new ImmutableQueue<T>(ImmutableList.<T>nil(), tnorf.tail));
} else {
return new DequeueResult<T>(back.head, new ImmutableQueue<T>(front, back.tail));
}
}
//Sorry, no tuples in Java land...
public static class DequeueResult<T> {
public final T t;
public final ImmutableQueue<T> queue;
public DequeueResult(T t, ImmutableQueue<T> queue) {
this.t = t;
this.queue = queue;
}
}
}
AFAIK you can’t get it much faster with immutable data structures.
4