001 /*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements. See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License. You may obtain a copy of the License at
008 *
009 * http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017 package org.apache.commons.collections.primitives;
018
019 import java.util.ConcurrentModificationException;
020 import java.util.NoSuchElementException;
021
022 /**
023 * Abstract base class for {@link LongList}s backed
024 * by random access structures like arrays.
025 * <p />
026 * Read-only subclasses must override {@link #get}
027 * and {@link #size}. Mutable subclasses
028 * should also override {@link #set}. Variably-sized
029 * subclasses should also override {@link #add(long)}
030 * and {@link #removeElementAt}. All other methods
031 * have at least some base implementation derived from
032 * these. Subclasses may choose to override these methods
033 * to provide a more efficient implementation.
034 *
035 * @since Commons Primitives 0.1
036 * @version $Revision: 480460 $ $Date: 2006-11-29 09:14:21 +0100 (Wed, 29 Nov 2006) $
037 *
038 * @author Rodney Waldhoff
039 */
040 public abstract class RandomAccessLongList extends AbstractLongCollection implements LongList {
041
042 // constructors
043 //-------------------------------------------------------------------------
044
045 /** Constructs an empty list. */
046 protected RandomAccessLongList() {
047 }
048
049 // fully abstract methods
050 //-------------------------------------------------------------------------
051
052 public abstract long get(int index);
053 public abstract int size();
054
055 // unsupported in base
056 //-------------------------------------------------------------------------
057
058 /**
059 * Unsupported in this implementation.
060 * @throws UnsupportedOperationException since this method is not supported
061 */
062 public long removeElementAt(int index) {
063 throw new UnsupportedOperationException();
064 }
065
066 /**
067 * Unsupported in this implementation.
068 * @throws UnsupportedOperationException since this method is not supported
069 */
070 public long set(int index, long element) {
071 throw new UnsupportedOperationException();
072 }
073
074 /**
075 * Unsupported in this implementation.
076 * @throws UnsupportedOperationException since this method is not supported
077 */
078 public void add(int index, long element) {
079 throw new UnsupportedOperationException();
080 }
081
082 //-------------------------------------------------------------------------
083
084 // javadocs here are inherited
085
086 public boolean add(long element) {
087 add(size(),element);
088 return true;
089 }
090
091 public boolean addAll(int index, LongCollection collection) {
092 boolean modified = false;
093 for(LongIterator iter = collection.iterator(); iter.hasNext(); ) {
094 add(index++,iter.next());
095 modified = true;
096 }
097 return modified;
098 }
099
100 public int indexOf(long element) {
101 int i = 0;
102 for(LongIterator iter = iterator(); iter.hasNext(); ) {
103 if(iter.next() == element) {
104 return i;
105 } else {
106 i++;
107 }
108 }
109 return -1;
110 }
111
112 public int lastIndexOf(long element) {
113 for(LongListIterator iter = listIterator(size()); iter.hasPrevious(); ) {
114 if(iter.previous() == element) {
115 return iter.nextIndex();
116 }
117 }
118 return -1;
119 }
120
121 public LongIterator iterator() {
122 return listIterator();
123 }
124
125 public LongListIterator listIterator() {
126 return listIterator(0);
127 }
128
129 public LongListIterator listIterator(int index) {
130 return new RandomAccessLongListIterator(this,index);
131 }
132
133 public LongList subList(int fromIndex, int toIndex) {
134 return new RandomAccessLongSubList(this,fromIndex,toIndex);
135 }
136
137 public boolean equals(Object that) {
138 if(this == that) {
139 return true;
140 } else if(that instanceof LongList) {
141 LongList thatList = (LongList)that;
142 if(size() != thatList.size()) {
143 return false;
144 }
145 for(LongIterator thatIter = thatList.iterator(), thisIter = iterator(); thisIter.hasNext();) {
146 if(thisIter.next() != thatIter.next()) {
147 return false;
148 }
149 }
150 return true;
151 } else {
152 return false;
153 }
154 }
155
156 public int hashCode() {
157 int hash = 1;
158 for(LongIterator iter = iterator(); iter.hasNext(); ) {
159 long val = iter.next();
160 hash = 31*hash + ((int)(val ^ (val >>> 32)));
161 }
162 return hash;
163 }
164
165 public String toString() {
166 StringBuffer buf = new StringBuffer();
167 buf.append("[");
168 for(LongIterator iter = iterator(); iter.hasNext();) {
169 buf.append(iter.next());
170 if(iter.hasNext()) {
171 buf.append(", ");
172 }
173 }
174 buf.append("]");
175 return buf.toString();
176 }
177
178 // protected utilities
179 //-------------------------------------------------------------------------
180
181 /** Get my count of structural modifications. */
182 protected int getModCount() {
183 return _modCount;
184 }
185
186 /** Increment my count of structural modifications. */
187 protected void incrModCount() {
188 _modCount++;
189 }
190
191 // attributes
192 //-------------------------------------------------------------------------
193
194 private int _modCount = 0;
195
196 // inner classes
197 //-------------------------------------------------------------------------
198
199 private static class ComodChecker {
200 ComodChecker(RandomAccessLongList source) {
201 _source = source;
202 resyncModCount();
203 }
204
205 protected RandomAccessLongList getList() {
206 return _source;
207 }
208
209 protected void assertNotComodified() throws ConcurrentModificationException {
210 if(_expectedModCount != getList().getModCount()) {
211 throw new ConcurrentModificationException();
212 }
213 }
214
215 protected void resyncModCount() {
216 _expectedModCount = getList().getModCount();
217 }
218
219 private RandomAccessLongList _source = null;
220 private int _expectedModCount = -1;
221 }
222
223 protected static class RandomAccessLongListIterator extends ComodChecker implements LongListIterator {
224 RandomAccessLongListIterator(RandomAccessLongList list, int index) {
225 super(list);
226 if(index < 0 || index > getList().size()) {
227 throw new IndexOutOfBoundsException("Index " + index + " not in [0," + getList().size() + ")");
228 } else {
229 _nextIndex = index;
230 resyncModCount();
231 }
232 }
233
234 public boolean hasNext() {
235 assertNotComodified();
236 return _nextIndex < getList().size();
237 }
238
239 public boolean hasPrevious() {
240 assertNotComodified();
241 return _nextIndex > 0;
242 }
243
244 public int nextIndex() {
245 assertNotComodified();
246 return _nextIndex;
247 }
248
249 public int previousIndex() {
250 assertNotComodified();
251 return _nextIndex - 1;
252 }
253
254 public long next() {
255 assertNotComodified();
256 if(!hasNext()) {
257 throw new NoSuchElementException();
258 } else {
259 long val = getList().get(_nextIndex);
260 _lastReturnedIndex = _nextIndex;
261 _nextIndex++;
262 return val;
263 }
264 }
265
266 public long previous() {
267 assertNotComodified();
268 if(!hasPrevious()) {
269 throw new NoSuchElementException();
270 } else {
271 long val = getList().get(_nextIndex-1);
272 _lastReturnedIndex = _nextIndex-1;
273 _nextIndex--;
274 return val;
275 }
276 }
277
278 public void add(long value) {
279 assertNotComodified();
280 getList().add(_nextIndex,value);
281 _nextIndex++;
282 _lastReturnedIndex = -1;
283 resyncModCount();
284 }
285
286 public void remove() {
287 assertNotComodified();
288 if (_lastReturnedIndex == -1) {
289 throw new IllegalStateException();
290 }
291 if (_lastReturnedIndex == _nextIndex) {
292 // remove() following previous()
293 getList().removeElementAt(_lastReturnedIndex);
294 } else {
295 // remove() following next()
296 getList().removeElementAt(_lastReturnedIndex);
297 _nextIndex--;
298 }
299 _lastReturnedIndex = -1;
300 resyncModCount();
301 }
302
303 public void set(long value) {
304 assertNotComodified();
305 if(-1 == _lastReturnedIndex) {
306 throw new IllegalStateException();
307 } else {
308 getList().set(_lastReturnedIndex,value);
309 resyncModCount();
310 }
311 }
312
313 private int _nextIndex = 0;
314 private int _lastReturnedIndex = -1;
315 }
316
317 protected static class RandomAccessLongSubList extends RandomAccessLongList implements LongList {
318 RandomAccessLongSubList(RandomAccessLongList list, int fromIndex, int toIndex) {
319 if(fromIndex < 0 || toIndex > list.size()) {
320 throw new IndexOutOfBoundsException();
321 } else if(fromIndex > toIndex) {
322 throw new IllegalArgumentException();
323 } else {
324 _list = list;
325 _offset = fromIndex;
326 _limit = toIndex - fromIndex;
327 _comod = new ComodChecker(list);
328 _comod.resyncModCount();
329 }
330 }
331
332 public long get(int index) {
333 checkRange(index);
334 _comod.assertNotComodified();
335 return _list.get(toUnderlyingIndex(index));
336 }
337
338 public long removeElementAt(int index) {
339 checkRange(index);
340 _comod.assertNotComodified();
341 long val = _list.removeElementAt(toUnderlyingIndex(index));
342 _limit--;
343 _comod.resyncModCount();
344 incrModCount();
345 return val;
346 }
347
348 public long set(int index, long element) {
349 checkRange(index);
350 _comod.assertNotComodified();
351 long val = _list.set(toUnderlyingIndex(index),element);
352 incrModCount();
353 _comod.resyncModCount();
354 return val;
355 }
356
357 public void add(int index, long element) {
358 checkRangeIncludingEndpoint(index);
359 _comod.assertNotComodified();
360 _list.add(toUnderlyingIndex(index),element);
361 _limit++;
362 _comod.resyncModCount();
363 incrModCount();
364 }
365
366 public int size() {
367 _comod.assertNotComodified();
368 return _limit;
369 }
370
371 private void checkRange(int index) {
372 if(index < 0 || index >= size()) {
373 throw new IndexOutOfBoundsException("index " + index + " not in [0," + size() + ")");
374 }
375 }
376
377 private void checkRangeIncludingEndpoint(int index) {
378 if(index < 0 || index > size()) {
379 throw new IndexOutOfBoundsException("index " + index + " not in [0," + size() + "]");
380 }
381 }
382
383 private int toUnderlyingIndex(int index) {
384 return (index + _offset);
385 }
386
387 private int _offset = 0;
388 private int _limit = 0;
389 private RandomAccessLongList _list = null;
390 private ComodChecker _comod = null;
391
392 }
393 }
394