CODEWITHSUNDEEP
javaalgorithmdata-structuresqueue
StephenChen
StephenChen

Reputation: 763

Java-Randomized Queue Iterator Causes Invalid Range Exception

I have an implementation of randomized queue in Java. Although enqueue, dequeue and sample operations work fine, the iterator causes Invalid Range Exception to be thrown every time in the shuffle method.

I do not understand why since the random number generation in the shuffle() method is bound by size of the queue. Here is the code: 

private int N=0;
private Item[] queue;
public RandomizedQueue(){
   queue= (Item[]) new Object[8];
}                // construct an empty randomized queue
public boolean isEmpty(){
   return N==0;
}                 // is the queue empty?
public int size(){
   return N;
}// return the number of items on the queue
private void resize(int capacity){
    Item[] copy=(Item[]) new Object[capacity];
    for(int i=0;i<N;i++){
        copy[i]=queue[i];
    }
    queue=copy;
}

private class QueueIterator implements Iterator<Item>{
    int i=0;
    public QueueIterator(){
        if(N>0){
            shuffle();
        }
    }
    @Override
    public boolean hasNext() {
        return i<N;
    }

    @Override
    public Item next() {
        Item item=queue[i];
        i++;
        return item;
    }

    @Override
    public void remove() {
        throw new java.lang.UnsupportedOperationException("remove is not supported");
    }

}

public void enqueue(Item item){
    if(item==null){
        throw new java.lang.NullPointerException("can't insert null items"); 
    }

    if(N==queue.length){
        resize(2*queue.length);
    }
    queue[N++]=item;
}           // add the item
public Item dequeue(){
    if(isEmpty()){
        throw new java.util.NoSuchElementException("queue is empty");
    }
    int i=StdRandom.uniform(0, N);
    Item item=queue[i];
    exchange(i,N-1);
    N=N-1;
    queue[N]=null;
    return item;
}                    // remove and return a random item
public Item sample(){
    if(isEmpty()){
        throw new java.util.NoSuchElementException("queue is empty");
    }
    int i=StdRandom.uniform(0,N);
    return queue[i];
}                     // return (but do not remove) a random item
public Iterator<Item> iterator(){
   return new QueueIterator();
}         // return an independent iterator over items in random order
private void exchange( int i, int j){
    Item swap=queue[i];
    queue[i]=queue[j];
    queue[j]=swap;
}

private void shuffle(){
    for(int i=0;i<N;i++){
        int j=StdRandom.uniform(0, i);
        exchange(i,j);
    }
}

Upvotes: 2

Views: 777

Answers (1)

Anderson Vieira
Anderson Vieira

Reputation: 9049

In the method shuffle():

private void shuffle(){
    for(int i=0;i<N;i++){
        int j=StdRandom.uniform(0, i);
        exchange(i,j);
    }
}

In the first iteration, when you call StdRandom.uniform(0, 0), it throws the exception because the second argument must be strictly greater than the first. Probably you should change your for loop so that the minimum value for i is 1.

From the documentation:

uniform

public static int uniform(int a, int b)

Returns an integer uniformly in [a, b).

Throws:

IllegalArgumentException - if b <= a

IllegalArgumentException - if b - a >= Integer.MAX_VALUE

Upvotes: 1

Related Questions