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