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