Flerex Flerex - 22 days ago 5
Java Question

Iterator with descending and ascending order does not work

I'm trying to implement the following deque that implements an Iterable:

public class Dequeue<E> implements Iterable<E> {

protected List<E> deque;

public Dequeue() {
this.deque = new ArrayList<>();

}

public void insertFirst( E elem ) {
this.deque.add( 0, elem );
}

public void insertLast( E elem ) {
this.deque.add( elem );
}

public E removeFirst() {
return (this.deque.isEmpty()) ? null : this.deque.remove(0);
}

public E removeLast() {
return (this.deque.isEmpty()) ? null : this.deque.remove( this.deque.size() - 1 );
}

public E examineFirst() {
return this.deque.get(0);
}

public E examineLast() {
return this.deque.get( this.deque.size() - 1 );
}

@Override
public Iterator<E> iterator() {
return new DequeIterator<>(false);
}

public Iterator<E> iterator( boolean isDesc ) {
return new DequeIterator<>(isDesc);
}

public class DequeIterator<E> implements Iterator<E> {

private int index;
private boolean isDesc;

public DequeIterator( boolean isdesc ) {
this.index = isdesc ? deque.size() - 1 : 0;
}

@Override
public boolean hasNext() {
return isDesc ? index > 0 : index < deque.size();
}

@Override
public E next() {
this.index = (isDesc) ? index-- : index++;
return (E) deque.get(index);
}

@Override
public void remove() {
deque.remove(index);
}
}

}


But if I try to test it with the following code, it goes into an infinite loop. What's happening? The compiler doesn't return any kind of error and I don't know if I'm doing the implementation of the Iterator class right.

List<Integer> result = new ArrayList<>();
Dequeue<Integer> deque = new Dequeue<>();
deque.insertLast( new Integer(1) );
deque.insertLast( new Integer(2) );

for( Integer i : deque ) {
System.out.println(i);
}

Answer

There are actually 3 mistakes in your code:

  1. You don't iterate over deque but over the useless list result
  2. You don't affect the value of the member variable isDesc in the constructor of the class DequeIterator.
  3. You don't manage properly the index in the method DequeIterator#next(), you affect the value of the post incrementation/decrementation which will end up with the same index so to an infinite loop, use directly the result of the post incrementation/decrementation as index.

Here is the code fixed:

Dequeue<Integer> deque = new Dequeue<>();
deque.insertLast(1);
deque.insertLast(2);

for( Integer i : deque ) {
    System.out.println(i);
}

And the class Dequeue.DequeIterator

public class DequeIterator<E> implements Iterator<E> {

    ...
    private boolean isDesc;

    public DequeIterator( boolean isdesc ) {
        ...
        this.isDesc = isdesc;
    }

   ...

    @Override
    public E next() {
        return (E) deque.get(isDesc ? index-- : index++);
    }

    ...
}