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}