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}