[CC150v5] 14.6 Implement CircularArray in Java

Question

Implement a CircularArray class that supports an array-like data structure which can be efficiently rotated.

The class should use a generic type, and should support iteration via the standard for (Object : circuLarArray) notation.

Solution

First part of the question is solved by using an array and a pointer. The solution simplifies the question by fixing the array size (not a dynamic-resizing array).

The difficult part is how to write iterator.

Note that we should support Java Generics:

class MyCircularArray<T>

Implement Iterable Interface:

public class MyCircularArray<T> implements Iterable<T> {
}

Override iterator() method:

@Override
public Iterator<T> iterator() {
    return new MyIterator<T>(this);
}

Write our own Iterator Class:

class MyIterator<T> implements Iterator<T> {
}

Finish it up

public class MyCircularArray<T> implements Iterable<T> {

    @Override
    public Iterator<T> iterator() {
        return new MyIterator<T>(this);
    }

    class MyIterator<T> implements Iterator<T> {
        @Override
        public boolean hasNext() {
        }

        @Override
        public T next() {
        }

        @Override
        public void remove() {
        }
    }
}

It might be confusing when implementing Iterable and Iterator Class.

Code

public class MyCircularArray<T> implements Iterable<T> {

    T[] items;

    int head;
    int cur;

    public MyCircularArray(int size) {
        // this is really important (casting the type)
        items = (T[]) new Object[size];

        head = 0;
        cur = 0;
    }

    public void put(T item) {
        items[cur++] = item;
        cur = cur % items.length;
    }

    public T get(int i) {
        int newIndex = (i + head) % items.length;
        return items[newIndex];
    }

    public void rotate(int shiftRight) {
        head += shiftRight;
        head = head % items.length;
    }

    @Override
    public Iterator<T> iterator() {
        return new MyIterator<T>(this);
    }

    class MyIterator<T> implements Iterator<T> {

        T[] items;
        int head;
        int count;

        public MyIterator(MyCircularArray<T> array) {
            this.items = array.items;
            this.head = array.head;
            this.count = 0;
        }

        @Override
        public boolean hasNext() {
            return this.count != items.length;
        }

        @Override
        public T next() {
            if (hasNext()) {
                return items[(head + count++) % items.length];
            }
            return null;
        }

        @Override
        public void remove() {
        }
    }

}