I am going through a course and after learning the theory I decided to implement the DS on my own. I write a few test cases and all operations seem to be working fine but once I tried to double check with the course's solution, it is not clear if I am missing anything since my logic is not line by line the same :(
Resizing approach I took:
- Doubling once full capacity is reach
- Halving once number of items in the Queue decrease to 1/4 of capacity
Operations:
public E dequeue()
public void enqueue(E item)
public int size()
private boolean isFullCapacity()
private boolean isFourthCapacity()
private void resize(int newSize)
public boolean isEmpty()
If anyone can point me to where I can more thoroughly test, I would also appreciate it. I could not find any test suite on the internet. Would also appreciate general good practices feed back :)
public class QueueResizingArray <E> implements Queue<E> {
private E[] arr;
private int size;
private int front;
private int end;
private static final int INITIAL_CAPACITY = 6;
private static final int INCREASE_FACTOR = 2;
public QueueResizingArray(){
this.arr = (E[]) new Object[INITIAL_CAPACITY];
}
@Override
public void enqueue(E item) {
if(item == null)
throw new IllegalArgumentException("item entered cannot be null");
this.arr[front] = item;
this.front = getNextPointerInCircularArray(this.front);
this.size ++;
if(isFullCapacity())
resize(INCREASE_FACTOR * this.arr.length);
}
@Override
public E dequeue() {
if(this.isEmpty())
throw new NoSuchElementException("Queue is empty when trying to dequeue");
E item = this.arr[end];
this.arr[end] = null;
this.end = getNextPointerInCircularArray(this.end);
this.size--;
/*
first condition added otherwise following will happen.
, lets take as an example an array of length, arr.length = 3,
and there is one item in array, size = 1, and we decide to dequeue this single item.
size = 1 will decrement to 0 in the dequeue() method and the reach isFourthCapacity().
at this point, the following check occurs. if ( size == arr.length/4) in this case
since size = 1 and arr.length = 4, the check evaluates to if ( 0 == 0), triggering a resize even with no items present.
if (0 == 0)
incorrectly triggering shrinking even with no items present
0 (size)/3 (array.length) = 0 (
*/
if(this.size > 0 && isFourthCapacity())
resize(this.arr.length/2);
return item;
}
@Override
public boolean isEmpty() {
return this.size == 0;
}
@Override
public int size() {
return this.size;
}
private boolean isFullCapacity(){
return this.size == this.arr.length;
}
private boolean isFourthCapacity(){
return this.size == this.arr.length/4;
}
private void resize(int newArrLength){
E[] newArr = (E[]) new Object[newArrLength];
int insertIndex = 0;
int tempEnd = this.end;
do{
newArr[insertIndex] = this.arr[tempEnd];
tempEnd = getNextPointerInCircularArray(tempEnd);
insertIndex++;
}while(this.front != tempEnd);
//the reason why i move end is because if halving, end will lag front and we can increment end to touch all items we need to copy. I think we could also decrement front
//TODO we need a do while to move end one away from front, below does not work because when full, end will equal front not triggering copying of elements
// while(this.front != tempEnd){
// newArr[insertIndex] = this.arr[tempEnd];
// tempEnd = getNextPointerInCircularArray(tempEnd);
// insertIndex++;
// }
//resetting indexes after resizing
this.front = this.size;
this.end = 0;
//setting new array
this.arr = newArr;
}
private int getNextPointerInCircularArray(int reference){
return (reference + 1) % this.arr.length;
}
}
Tests:
public class Test {
@org.junit.Test
public void testMyCircularResizingArraySolution(){
Queue<Integer> queue = new QueueResizingArray<>();
//enqueue
queue.enqueue(1);
//assert
Assert.assertEquals(1, queue.size());
//dequeue
int item1 = queue.dequeue();
Assert.assertEquals(1, item1);
Assert.assertEquals(0, queue.size());
//6 enqueues
queue.enqueue(1);
queue.enqueue(1);
queue.enqueue(1);
queue.enqueue(-9);
queue.enqueue(2);
queue.enqueue(7);
//last enqueue should have triggered doubling of circular array
int item2 = queue.dequeue();
Assert.assertEquals(1, item2);
Assert.assertEquals(5, queue.size());
int item3 = queue.dequeue();
Assert.assertEquals(1, item3);
Assert.assertEquals(4, queue.size());
//will trigger halving
int item4 = queue.dequeue();
Assert.assertEquals(1, item4);
Assert.assertEquals(3, queue.size());
int item5 = queue.dequeue();
Assert.assertEquals(-9, item5);
Assert.assertEquals(2, queue.size());
int item6 = queue.dequeue();
Assert.assertEquals(2, item6);
Assert.assertEquals(1, queue.size());
int item7 = queue.dequeue();
Assert.assertEquals(7, item7);
Assert.assertEquals(0, queue.size());
}
}