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