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