Overriding Iterator in circular array

Question

I am writing my own Deque class and I need to override iterator.

Example: Say the array is [3,4,5,null,null,null,1,2] where 1 is the front and 5 is the end. I would need to be able to use the iterator to start at 1 and end at after 5.

Here is my whole Deque Class. I believe I have everything right with the iterator except the hasNext method.

import java.util.Iterator;
import java.util.*;
import javax.swing.border.*;

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

    public final int INITIAL_SIZE = 16;

    private E[] items;
    private E[] temp;
    private int size;
    private int first;

    @SuppressWarnings("unchecked")  // Casting Object[] to E[]
    public Deque20() {
        items = (E[]) new Object[INITIAL_SIZE];
        size = 0;
        first = 0;
    }

    public void addFirst(E e){
        if(size == items.length){
            doubleSize();
        }
        first -= 1;
        if(first == -1){
            first = items.length - 1;
        }
        items[first] = e;
        size += 1;
    }

    public void addLast(E e){
        if(size == items.length){
            doubleSize();
        }
        items[(first + size) % items.length] = e;
        size++; 
    }

    public void removeFirst(){
        items[first] = null;
        first++;
        size--;
    }

    public void removeLast(){
        items[((first + size) % items.length) - 1] = null;
        size--;
    }

    public E peekFirst(){
        if(size == 1){
            return items[first];
        }else{
            return items[first];
        }
    }

    public E peekLast(){
        if(size == 1){
            return items[first];
        }else{
            return items[((first + size) % items.length) - 1];
        }
    }

    @SuppressWarnings("unchecked")
    private void doubleSize(){
        temp = (E[]) new Object[size * 2];
        for(int i = 0; i < size; i++){
            temp[i] = items[(first + i) % items.length];
        }
        items = temp;
        first = 0;
    }

    @SuppressWarnings("unchecked")
    private void realign(){
        temp = (E[]) new Object[size];
        for(int i = 0; i < size; i++){
            temp[i] = items[(first + i) % items.length];
        }
        items = temp;
        first = 0;
    }

    public int size(){
        return size;
    }

    public boolean isEmpty(){
        if(size == 0){
            return true;
        }
        return false;
    }

    @Override
    public Iterator<E> iterator() {
        Iterator<E> it = new Iterator<E>(){
            private int currentIndex = first;

            @Override
            public boolean hasNext() {
                return currentIndex < size && items[currentIndex] != null;
            }

            @Override
            public E next() {
                return items[currentIndex++];
            }

            @Override
            public void remove() {
                throw new UnsupportedOperationException();
            }
        };
        return it;
    }

    public String toString(){
        String str = "[";
        for(E e : items){
            str += e + ",";
        }
        str += "]";
        return str;
    }
}

EDIT: My question is how can I fix the hasNext method for my Iterator.When iterating it will only go to the end of the list and not circle around to the front.

The Deque20 class is just assignment I have to write my own class that behaves like the built in ArrayDeque.

how to override iterator on circular array. Specifically the hasNext — Ryan Bautista
– Ryan Bautista, Commented May 21, 2016 at 0:20
(Please edit that into your question.) What's wrong with your current solution? — Sotirios Delimanolis
– Sotirios Delimanolis, Commented May 21, 2016 at 0:21
The hasNext method doesn't work and The size will double when capacity is reached — Ryan Bautista
– Ryan Bautista, Commented May 21, 2016 at 0:25

Rajeev Sampath · Accepted Answer · 2016-05-21 00:44:44Z

1

You may need to initialize the currentIndex in a constructor in iterator inner class and also set currentIndex to 0 when size is exceeded (assuming hasNext will always be called before next, otherwise the next should have the same.), as in:

        public Iterator() {
            // init first position - assuming first element is always available somewhere in the array.
            for (int i = 0;i<items.length;i++) {
                if (items[i] == first) {
                    currentIndex = i;
                    break;
                }
            }
        }
    @Override
    public boolean hasNext() {
        if (currentIndex >= size()) {
            currentIndex = 0;
        }
        return  items[currentIndex] != null;
    }

If there are next() calls without hasNext():

 public E next() {
            if (currentIndex >= size()) {
                currentIndex = 0;
            }
            return items[currentIndex++];
        }

edited May 21, 2016 at 0:44

answered May 21, 2016 at 0:39

Rajeev Sampath

2,7571 gold badge18 silver badges19 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Ryan Bautista Over a year ago

Worked thank you! also I didn't need the constructor I only used the if statement to check if it went over the and it worked fine.

Kedar Mhaswade · Accepted Answer · 2016-05-21 01:54:18Z

I'd use a currentOffset from first:

@Override
public Iterator<E> iterator() {
    return new Iterator<E>() {
        private int currentOffset = 0;

        @Override
        public boolean hasNext() {
            return currentOffset < size;
        }

        @Override
        public E next() {
            E n = items[(first + currentOffset) % items.length];
            currentOffset += 1;
            return n;
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException();
        }
    };
}

Also, I suggest that you rename your method doubleSize() as doubleCapacity(), since you are actually doubling the capacity without making any change to the size of the deque. Ideally, you should consider handling a SimultaneousModificationException wherein you detect the changes to the deque while iterating.

Collectives™ on Stack Overflow

Overriding Iterator in circular array

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related