DoublingQueue in Java

Question

Inspired by this CR question, I decided to create my own queue! If you guys see anything taboo or have any improvements, please let me know. Ultimately I want it to be feature rich and bug free, with every possible case tested, so if there's anything else that can be added (like an iterator) and thoroughly tested, please mention it.

IDoublingQueue.java

public interface IDoublingQueue<E> {
 public boolean isEmpty();
 public int size();
 public void enqueue(E item);
 public E dequeue();
}

DoublingQueue.java

public class DoublingQueue<E> implements IDoublingQueue<E> {
 private E[] queue;
 private int size = 0;
 private int first = 0;
 public DoublingQueue() {
 queue = (E[]) new Object[2];
 }
 @Override
 public boolean isEmpty() {
 return size == 0;
 }
 @Override
 public int size() {
 return size;
 }
 private void resize(int max) {
 assert max >= size;
 E[] temp = (E[]) new Object[max];
 for (int i = 0; i < size; ++i) {
 temp[i] = queue[(first + i) % queue.length];
 }
 queue = temp;
 first = 0;
 }
 @Override
 public void enqueue(E item) {
 // be sure no null items make it into the queue
 if (item == null) {
 throw new IllegalArgumentException("ERROR: Null elements cannot be inserted!");
 }
 if (size == queue.length) {
 resize(2 * queue.length);
 }
 queue[size++] = item;
 }
 @Override
 public E dequeue() {
 if (isEmpty()) {
 throw new RuntimeException("ERROR: Queue underflow");
 }
 E item = queue[first];
 queue[first] = null;
 size--;
 first++;
 if (first == queue.length) {
 first = 0;
 }
 // shrink the queue if necessary
 if (size > 0 && size == queue.length / 4) {
 resize(queue.length / 2);
 }
 return item;
 }
}

Tests

public class DoublingQueueTest {
 private final DoublingQueue<Integer> queue = new DoublingQueue();
 @Test(expected = IllegalArgumentException.class)
 public void enqueueNullTest() {
 queue.enqueue(null);
 }
 @Test(expected = RuntimeException.class)
 public void dequeueEmptyTest() {
 queue.dequeue();
 }
 @Test
 public void enqueueTest() {
 queue.enqueue(1);
 queue.enqueue(2);
 queue.enqueue(3);
 assertTrue(queue.size() == 3);
 }
 @Test
 public void dequeueTest() {
 queue.enqueue(1);
 queue.enqueue(2);
 queue.enqueue(3);
 int num = queue.dequeue();
 assertTrue(num == 1);
 }
}

Answer 1

Edit: As coderodde excellently pointed out in his answer, your implementation has the issue of not reusing previous entries in the array that have already been dequeued. This means that your array will always keep on growing in size. See his answer for an explanation on this.

---

First of all, good job on improving your coding skills through an exercise like this. More people should be doing this. Now lets get into the criticism from which you will hopefully learn even more.

Constructor

It's strange that you do not allow the user to specificy the initial size of the queue. Even if this were to be a design choice, I think 2 is too low of a value. Also the magic number 2 should be moved to a constant like DEFAULT_QUEUE_SIZE to increase readability and maintainability.

Size

Your size variable is quite confusing. For a while I thought it was the current size of the queue, meaning it would start at 2 and then double over time. But later I found out that it actually represents the amount of items currently in the queue. I think that this might also be confusing to anyone calling your size() method.

isFull()

In your enqueue() method you check size == queue.length. This is essentially the isFull() method. Replacing this with a call to isFull() would not only increase the readability of your enqueue() method, but also add the isFull()method to the public API of your class, fulfilling the symmetry with isEmpty().

resize()

To improve coherence and readability, I would add two methods called doubleSize()and halfSize(), which would simply then call the resize() method with the correct parameters. This improves the readability and intentions in the enqueue() and dequeue() method and allows the explanatory comment // shrink the queue if necessary to be removed.

Comments

There are a lot of opinions about comments. I share mine with Robert C. Martin in that they show a failure of expressing yourself by means of code. The comment I mentioned in the section above about the resize() method is a good example of that.

The other comment in your code, // be sure no null items make it into the queue, can also be removed, because the code below it is perfectly clear. It is simply a duplication of information, and just as duplication of code is bad, this kind of duplication is bad as well. This is because comments tend to get out of sync with the code they were intended to enlighten.

Interface

Personally, I do not see the use of an interface for this implementation. I think it is merely clutter as it provides no additional information that the concrete class itself does not already provide.

---

Testing

There is a lot that could be improved in the testing department here. I will try to create a somewhat short, comprehensive list of the things that I think are missing or incorrect. You will find that most of the things I say about testing have also been said in the Code Review question that inspired you, so perhaps you should also read through the accepted answer there on testing.

• Your enqueueTest function is testing size() functionality.
• Your test function names are not very descriptive about the situation that is being tested and what the expected outcome should be. There is a small blogpost by Google on test function names that might be useful to read.

Test ALL the things.

You are not even scratching the surface of having all scenarios tested.

• Are you sure that dequeue() actually halves the queue size when it can? You shouldn't be, because you haven't tested it.
• isEmpty() is not even tested once. What happens when isEmpty() is called when the queue is empty, filled or full? Or full and then emptied again. All of these scenarios should be tested.
• Your test for the size() method is way too simplistic. Does size() return 0 if the queue is empty? does it return the correct amount after enqueueing X items and dequeueing Y items? Does it return the correct amount after doubling and halving the queue X amount of times?
• You should also test the FIFO (First In First Out) concept of your queue more elaborately. You started with it in dequeueTest(), but kept it way too simple.

Test examples

In this section I will provide some example tests for only the method isEmpty() to illustrate my points above.

@Test
public void testIsEmptyReturnsTrueWhenQueueIsEmpty() {
 assertTrue(queue.isEmpty());
}
@Test
public void testIsEmptyReturnsFalseWhenQueueIsFilled() {
 queue.enqueue(1);
 assertFalse(queue.isEmpty());
}
@Test
public void testIsEmptyReturnsFalseWhenQueueIsFull() {
 // Since your magic starting queue size number
 // is 2 I enqueue two items.
 queue.enqueue(1);
 queue.enqueue(2);
 assertFalse(queue.isEmpty());
}
@Test
public void testIsEmptyReturnsTrueWhenQueueIsEmptiedAfterUse() {
 for (int i = 0; i < 10; i++) queue.enqueue(i);
 for (int i = 0; i < 10; i++) queue.dequeue();
 assertTrue(queue.isEmpty());
 // This second part is debatable since you generally want
 // to test only one thing per test.
 for (int i = 0; i < 10; i++) {
 queue.enqueue(i);
 queue.dequeue();
 }
 assertTrue(queue.isEmpty());
}

• T145: Ik barely any testing scenarios are shown; it's just that there are a lot that I don't know about, don't know how to test, or felt my implementation was bad. This is why I wanted to see some alternate JUnit tests, so I can understand effective testing methods.
• T145: Do you mean to assertTrue on that last test? :P

Answer 2

What comes to your queue implementation, I have spotted the following issue:

Suppose you are given a routine \$R\$ that enqueues, say, \$m\$ elements and then dequeues them all. Now suppose you repeat \$R\$ many times; the size of your queue is no more than \$m\,ドル yet you keep moving the integer size towards greater values and your internal storage array keeps growing!

One remedy is to "wrap around" whenever size gets the value queue.length, and keep inserting the new elements at the beginning of the internal storage array.

Also, what comes to throwing an exception when adding a null, I think you need to throw NullPointerException after all.

private int size = 0;
private int first = 0;

ints are initialised to zero by default; write

private int size;
private int first;

All in all, I had this in mind:

DoublingQueue2.java:

import java.util.NoSuchElementException;
import java.util.Objects;
public final class DoublingQueue2<E> implements IDoublingQueue<E> {
 private int head;
 private int size;
 private int mask = 1;
 private Object[] storage = new Object[2];
 @Override
 public boolean isEmpty() {
 return size == 0;
 }
 @Override
 public int size() {
 return size;
 }
 @Override
 public void enqueue(E item) {
 Objects.requireNonNull(item, "The input item is null.");
 ensureCapacity();
 storage[(head + size++) & mask] = item;
 }
 @Override
 public E dequeue() {
 if (isEmpty()) {
 throw new NoSuchElementException(
 "Dequeue from an empty queue.");
 }
 E ret = (E) storage[head];
 head = (head + 1) & mask;
 --size;
 return ret;
 }
 private final void ensureCapacity() {
 if (size == storage.length) {
 Object[] newStorage = new Object[size << 1];
 for (int i = 0; i < size; ++i) {
 newStorage[i] = storage[(head + i) & mask];
 }
 this.storage = newStorage;
 this.head = 0;
 this.mask = newStorage.length - 1;
 }
 }
 public static void main(String[] args) {
 DoublingQueue<Integer> queue1 = new DoublingQueue<>();
 long startTime = System.nanoTime();
 for (int i = 0; i < 1_000_000; ++i) {
 for (int j = 0; j < 10; ++j) {
 queue1.enqueue(j);
 }
 for (int j = 0; j < 10; ++j) {
 queue1.dequeue();
 }
 }
 long endTime = System.nanoTime();
 System.out.printf("DoublingQueue in %.2f milliseconds.\n",
 (endTime - startTime) / 1e6);
 DoublingQueue2<Integer> queue2 = new DoublingQueue2<>();
 startTime = System.nanoTime();
 for (int i = 0; i < 10_000; ++i) {
 for (int j = 0; j < 10; ++j) {
 queue2.enqueue(j);
 }
 for (int j = 0; j < 10; ++j) {
 queue2.dequeue();
 }
 }
 endTime = System.nanoTime();
 System.out.printf("DoublingQueue2 in %.2f milliseconds.\n",
 (endTime - startTime) / 1e6);
 }
}

The demonstration will give you something like this:

DoublingQueue in 478.39 milliseconds.
DoublingQueue2 in 9.11 milliseconds.

• Thijs Riezebeek: There is an interesting discussion stackoverflow.com/q/3881/4519644 on whether to throw an IllegalArgumentException or a NullPointerException. Good find on the implementation detail.
• coderodde: java.util.ArrayDeque throws NullPointerException on null value.
• T145: Nice job! The only things I'd change just at first glance is just put the ensureCapacity inside enqueue, since it's only used one time. Also, I'd change Object[] newStorage = new Object[size << 1]; to E[] newStorage = (E[]) new Object[size << 1];, and trim all the occurrences of this.. Any input on testing?
• coderodde: You could do some sort of "brute force" test: take, say, java.util.ArrayDeque and keep modifying them both (a lot) and checking that they agree on content.
• coderodde: @T145 Dumping the contents of ensureCapacity inside enqueue is not a good idea for a couple of reasons: (1) suppose you decide to convert your queue to a deque (double-ended queue), you will have to add ensureCapacity to the companion method for adding elements from the other end as well; (2) ideally, each method "should not" be longer than 8 rows.