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, Cloneable {
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     * Returns another independent copy-on-write copy of this <tt>List</tt>
117     * instance. Neither the elements nor the backing storage are copied.
118     *
119     * @return a clone of this <tt>CopyList</tt> instance
120     */
121    @Override
122    public Object clone() {
123        return new CopyList<>(array, size);
124    }
125
126    private void rangeCheck(int index) {
127        if (index >= size || index < 0) throw new IndexOutOfBoundsException("Index:" + index + " Size:" + size);
128    }
129
130    private void changeCheck() {
131        if (pristine) {
132            array = array.clone();
133            pristine = false;
134        }
135    }
136
137    private void ensureCapacity(int target) {
138        modCount++;
139        if (target > array.length) {
140            int newCapacity = Math.max(target, (array.length * 3)/2 + 1);
141            array = Arrays.copyOf(array, newCapacity);
142            pristine = false;
143        }
144    }
145
146    @Override
147    public Iterator<E> iterator() {
148        return new Itr();
149    }
150
151    private class Itr implements Iterator<E> {
152        /**
153         * Index of element to be returned by subsequent call to next.
154         */
155        private int cursor;
156
157        /**
158         * Index of element returned by most recent call to next or
159         * previous.  Reset to -1 if this element is deleted by a call
160         * to remove.
161         */
162        private int lastRet = -1;
163
164        /**
165         * The modCount value that the iterator believes that the backing
166         * List should have.  If this expectation is violated, the iterator
167         * has detected concurrent modification.
168         */
169        private int expectedModCount = modCount;
170
171        @Override
172        public boolean hasNext() {
173            return cursor != size;
174        }
175
176        @Override
177        public E next() {
178            checkForComodification();
179            try {
180                E next = array[cursor];
181                lastRet = cursor++;
182                return next;
183            } catch (IndexOutOfBoundsException e) {
184                checkForComodification();
185                throw new NoSuchElementException(e.getMessage());
186            }
187        }
188
189        @Override
190        public void remove() {
191            if (lastRet == -1)
192                throw new IllegalStateException();
193            checkForComodification();
194
195            try {
196                CopyList.this.remove(lastRet);
197                if (lastRet < cursor) {
198                    cursor--;
199                }
200                lastRet = -1;
201                expectedModCount = modCount;
202            } catch (IndexOutOfBoundsException e) {
203                throw new ConcurrentModificationException(e);
204            }
205        }
206
207        final void checkForComodification() {
208            if (modCount != expectedModCount)
209                throw new ConcurrentModificationException();
210        }
211    }
212
213}