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 }