[CC150v5] 14.6 Implement CircularArray in Java - Shuatiblog.com

[CC150v5] 14.6 Implement CircularArray in Java - Shuatiblog.com

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.

Fail fast, add expectedModCount feature.

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() {throw new UnsupportedOperationException("");
        }
    }

}

[CareerCup] 14.6 CircularArray 环形数组 - Grandyang - 博客园
14.6 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 (Obj o : CircularArray) notation.

这道题让我们实现一个环形数组类CircularArray，由于环形数组需要调用rotate(int shiftRight)函数，在这里，我们并不会真的去旋转数组，因为这样十分不高效。我们采用另一种实现方法，用一个变量head来记录环形数组的起始位置，那么调用rotate实际上就是改变head的位置而已

public static class CircularArray<T> implements Iterable<T> {
    private T[] items;
    private int head = 0;
    
    public CircularArray(int size) {
        items = (T[]) new Object[size];
    }
    
    private int convert(int idx) {
        if (idx < 0) {
            idx += items.length;
        }
        return (head + idx) % items.length;
    }
    
    public void rotate(int shiftRight) {
        head = convert(shiftRight);
    }
    
    public T get(int i) {
        if (i < 0 || i >= items.length) {
            throw new java.lang.IndexOutOfBoundsException("...");
        }
        return items[convert(i)];
    }
    
    public void set(int i, T item) {
        items[convert(i)] = item;
    }
    
    public Iterator<T> iterator() {
        return new CircularArrayIterator<T> (this);
    }
    
    private class CircularArrayIterator<TI> implements Iterator<TI> {
        private int _current = -1;
        private TI[] _items;
        
        public CircularArrayIterator(CircularArray<TI> array) {
            _items = array.items;
        }
        
        @Override
        public boolean hasNext() {
            return _current < items.length - 1;
        }
        
        @Override
        public TI next() {
            ++_current;
            TI item = (TI) _items[convert(_current)];
            return item;
        }
        
        @Override
        public void remove() {
            throw new UnsupportedOperationException("...");
        }
    }
}

1. 实现CircularArray类

实现的过程中容易犯一些错误，比如:

- 我们不能新建一个泛类的数组，我们必须cast数组或者定义类型为List<T>.

- 取余操作符%对于负数运算后会得到负数，这和数学家们定义的取余运算不同，所以我们需要给负数序列加上items.length，时期变为正数再做运算。

- 我们必须一致地保证将原序列转为旋转序列。

2. 实现迭代器Iterator接口

为了使用迭代来遍历数组for (Obj o : CircularArray)，我们必须实现迭代器Iterator接口：

- 修改CircularArray<T>的定义，添加implements Iteratble<T>。这需要我们添加一个iterator()方法给CircularArray<T>。

- 建立CircularArrayIterator<T>类implements Iterator<T>，这需要我们实现CircularArrayIterator的一些方法，如hasNext(), next(), 和 remove()。

一旦我们实现了上面两项，for (Obj o : CircularArray)循环就会神奇的运行了

https://github.com/niannianli/LJava/blob/master/src/java/CircularArray6.java
cpp code: http://www.cnblogs.com/zhuli19901106/p/3691937.html
Read full article from [CC150v5] 14.6 Implement CircularArray in Java - Shuatiblog.com