001// License: GPL. For details, see LICENSE file.
002package org.openstreetmap.josm.tools;
003
004import java.util.AbstractList;
005import java.util.ConcurrentModificationException;
006import java.util.Iterator;
007import java.util.NoSuchElementException;
008import java.util.RandomAccess;
009
010/**
011 * A List implementation initially based on given array, but never modifying
012 * the array directly. On the first modification, the implementation will
013 * create its own copy of the array, and after that it behaves mostly as
014 * an ArrayList.
015 *
016 * @author nenik
017 */
018public final class CopyList<E> extends AbstractList<E> implements RandomAccess, Cloneable {
019    private E[] array;
020    private int size;
021    private boolean pristine;
022
023    /**
024     * Create a List over given array.
025     * @param array The initial List content. The array is never modified
026     * by the {@code CopyList}.
027     */
028    public CopyList(E[] array) {
029        this(array, array.length);
030    }
031
032    public CopyList(E[] array, int size) {
033        this.array = array;
034        this.size = size;
035        pristine = true;
036    }
037
038    // read-only access:
039    @Override
040    public E get(int index) {
041        rangeCheck(index);
042        return array[index];
043    }
044
045    @Override
046    public int size() {
047        return size;
048    }
049
050    // modification:
051    @Override
052    public E set(int index, E element) {
053        rangeCheck(index);
054        changeCheck();
055
056        E old = array[index];
057        array[index] = element;
058        return old;
059    }
060
061    // full resizable semantics:
062    @Override
063    public void add(int index, E element) {
064        // range check
065        ensureCapacity(size+1);
066        changeCheck();
067
068        System.arraycopy(array, index, array, index+1, size-index);
069        array[index] = element;
070        size++;
071    }
072
073    @Override
074    public E remove(int index) {
075        rangeCheck(index);
076        changeCheck();
077
078        modCount++;
079        E element = array[index];
080        if (index < size-1) {
081            System.arraycopy(array, index+1, array, index, size-index-1);
082        } else {
083            array[index] = null;
084        }
085        size--;
086        return element;
087    }
088
089    // speed optimizations:
090    @Override
091    public boolean add(E element) {
092        ensureCapacity(size+1);
093        changeCheck();
094        array[size++] = element;
095        return true;
096    }
097
098    @Override
099    public void clear() {
100        modCount++;
101
102        // clean up the array
103        while (size > 0) {
104            array[--size] = null;
105        }
106    }
107
108    // helpers:
109    /**
110     * Returns another independent copy-on-write copy of this <tt>List</tt>
111     * instance. Neither the elements nor the backing storage are copied.
112     *
113     * @return a clone of this <tt>CopyList</tt> instance
114     */
115    @Override
116    public Object clone() {
117        return new CopyList<E>(array, size);
118    }
119
120    private void rangeCheck(int index) {
121        if (index >= size || index < 0) throw new IndexOutOfBoundsException("Index:" + index + " Size:" + size);
122    }
123
124    private void changeCheck() {
125        if (pristine) {
126            array = array.clone();
127            pristine = false;
128        }
129    }
130
131    @SuppressWarnings("unchecked")
132    private void ensureCapacity(int target) {
133        modCount++;
134        if (target > array.length) {
135            E[] old = array;
136
137            int newCapacity = Math.max(target, (array.length * 3)/2 + 1);
138            array = (E[]) new Object[newCapacity];
139            System.arraycopy(old, 0, array, 0, size);
140            pristine = false;
141        }
142    }
143
144    @Override
145    public Iterator<E> iterator() {
146        return new Itr();
147    }
148
149    private class Itr implements Iterator<E> {
150        /**
151         * Index of element to be returned by subsequent call to next.
152         */
153        int cursor = 0;
154
155        /**
156         * Index of element returned by most recent call to next or
157         * previous.  Reset to -1 if this element is deleted by a call
158         * to remove.
159         */
160        int lastRet = -1;
161
162        /**
163         * The modCount value that the iterator believes that the backing
164         * List should have.  If this expectation is violated, the iterator
165         * has detected concurrent modification.
166         */
167        int expectedModCount = modCount;
168
169        @Override
170        public boolean hasNext() {
171            return cursor != size;
172        }
173
174        @Override
175        public E next() {
176            checkForComodification();
177            try {
178                E next = array[cursor];
179                lastRet = cursor++;
180                return next;
181            } catch (IndexOutOfBoundsException e) {
182                checkForComodification();
183                throw new NoSuchElementException();
184            }
185        }
186
187        @Override
188        public void remove() {
189            if (lastRet == -1)
190                throw new IllegalStateException();
191            checkForComodification();
192
193            try {
194                CopyList.this.remove(lastRet);
195                if (lastRet < cursor) {
196                    cursor--;
197                }
198                lastRet = -1;
199                expectedModCount = modCount;
200            } catch (IndexOutOfBoundsException e) {
201                throw new ConcurrentModificationException();
202            }
203        }
204
205        final void checkForComodification() {
206            if (modCount != expectedModCount)
207                throw new ConcurrentModificationException();
208        }
209    }
210
211}