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