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:
018: package java.util;
019:
020: /**
021: * AbstractList is an abstract implementation of the List interface, optimized
022: * for a backing store which supports random access. This implementation does
023: * not support adding or replacing. A subclass must implement the abstract
024: * methods get() and size().
025: *
026: * @since 1.2
027: */
028: public abstract class AbstractList<E> extends AbstractCollection<E>
029: implements List<E> {
030:
031: protected transient int modCount;
032:
033: private class SimpleListIterator implements Iterator<E> {
034: int pos = -1;
035:
036: int expectedModCount;
037:
038: int lastPosition = -1;
039:
040: SimpleListIterator() {
041: super ();
042: expectedModCount = modCount;
043: }
044:
045: public boolean hasNext() {
046: return pos + 1 < size();
047: }
048:
049: public E next() {
050: if (expectedModCount == modCount) {
051: try {
052: E result = get(pos + 1);
053: lastPosition = ++pos;
054: return result;
055: } catch (IndexOutOfBoundsException e) {
056: throw new NoSuchElementException();
057: }
058: }
059: throw new ConcurrentModificationException();
060: }
061:
062: public void remove() {
063: if (this .lastPosition == -1) {
064: throw new IllegalStateException();
065: }
066:
067: if (expectedModCount != modCount) {
068: throw new ConcurrentModificationException();
069: }
070:
071: try {
072: AbstractList.this .remove(lastPosition);
073: } catch (IndexOutOfBoundsException e) {
074: throw new ConcurrentModificationException();
075: }
076:
077: expectedModCount = modCount;
078: if (pos == lastPosition) {
079: pos--;
080: }
081: lastPosition = -1;
082: }
083: }
084:
085: private final class FullListIterator extends SimpleListIterator
086: implements ListIterator<E> {
087: FullListIterator(int start) {
088: super ();
089: if (0 <= start && start <= size()) {
090: pos = start - 1;
091: } else {
092: throw new IndexOutOfBoundsException();
093: }
094: }
095:
096: public void add(E object) {
097: if (expectedModCount == modCount) {
098: try {
099: AbstractList.this .add(pos + 1, object);
100: } catch (IndexOutOfBoundsException e) {
101: throw new NoSuchElementException();
102: }
103: pos++;
104: lastPosition = -1;
105: if (modCount != expectedModCount) {
106: expectedModCount++;
107: }
108: } else {
109: throw new ConcurrentModificationException();
110: }
111: }
112:
113: public boolean hasPrevious() {
114: return pos >= 0;
115: }
116:
117: public int nextIndex() {
118: return pos + 1;
119: }
120:
121: public E previous() {
122: if (expectedModCount == modCount) {
123: try {
124: E result = get(pos);
125: lastPosition = pos;
126: pos--;
127: return result;
128: } catch (IndexOutOfBoundsException e) {
129: throw new NoSuchElementException();
130: }
131: }
132: throw new ConcurrentModificationException();
133: }
134:
135: public int previousIndex() {
136: return pos;
137: }
138:
139: public void set(E object) {
140: if (expectedModCount == modCount) {
141: try {
142: AbstractList.this .set(lastPosition, object);
143: } catch (IndexOutOfBoundsException e) {
144: throw new IllegalStateException();
145: }
146: } else {
147: throw new ConcurrentModificationException();
148: }
149: }
150: }
151:
152: private static final class SubAbstractListRandomAccess<E> extends
153: SubAbstractList<E> implements RandomAccess {
154: SubAbstractListRandomAccess(AbstractList<E> list, int start,
155: int end) {
156: super (list, start, end);
157: }
158: }
159:
160: private static class SubAbstractList<E> extends AbstractList<E> {
161: private final AbstractList<E> fullList;
162:
163: private int offset;
164:
165: private int size;
166:
167: private static final class SubAbstractListIterator<E>
168: implements ListIterator<E> {
169: private final SubAbstractList<E> subList;
170:
171: private final ListIterator<E> iterator;
172:
173: private int start;
174:
175: private int end;
176:
177: SubAbstractListIterator(ListIterator<E> it,
178: SubAbstractList<E> list, int offset, int length) {
179: super ();
180: iterator = it;
181: subList = list;
182: start = offset;
183: end = start + length;
184: }
185:
186: public void add(E object) {
187: iterator.add(object);
188: subList.sizeChanged(true);
189: end++;
190: }
191:
192: public boolean hasNext() {
193: return iterator.nextIndex() < end;
194: }
195:
196: public boolean hasPrevious() {
197: return iterator.previousIndex() >= start;
198: }
199:
200: public E next() {
201: if (iterator.nextIndex() < end) {
202: return iterator.next();
203: }
204: throw new NoSuchElementException();
205: }
206:
207: public int nextIndex() {
208: return iterator.nextIndex() - start;
209: }
210:
211: public E previous() {
212: if (iterator.previousIndex() >= start) {
213: return iterator.previous();
214: }
215: throw new NoSuchElementException();
216: }
217:
218: public int previousIndex() {
219: int previous = iterator.previousIndex();
220: if (previous >= start) {
221: return previous - start;
222: }
223: return -1;
224: }
225:
226: public void remove() {
227: iterator.remove();
228: subList.sizeChanged(false);
229: end--;
230: }
231:
232: public void set(E object) {
233: iterator.set(object);
234: }
235: }
236:
237: SubAbstractList(AbstractList<E> list, int start, int end) {
238: super ();
239: fullList = list;
240: modCount = fullList.modCount;
241: offset = start;
242: size = end - start;
243: }
244:
245: @Override
246: public void add(int location, E object) {
247: if (modCount == fullList.modCount) {
248: if (0 <= location && location <= size) {
249: fullList.add(location + offset, object);
250: size++;
251: modCount = fullList.modCount;
252: } else {
253: throw new IndexOutOfBoundsException();
254: }
255: } else {
256: throw new ConcurrentModificationException();
257: }
258: }
259:
260: @Override
261: public boolean addAll(int location,
262: Collection<? extends E> collection) {
263: if (modCount == fullList.modCount) {
264: if (0 <= location && location <= size) {
265: boolean result = fullList.addAll(location + offset,
266: collection);
267: if (result) {
268: size += collection.size();
269: modCount = fullList.modCount;
270: }
271: return result;
272: }
273: throw new IndexOutOfBoundsException();
274: }
275: throw new ConcurrentModificationException();
276: }
277:
278: @Override
279: public boolean addAll(Collection<? extends E> collection) {
280: if (modCount == fullList.modCount) {
281: boolean result = fullList.addAll(offset + size,
282: collection);
283: if (result) {
284: size += collection.size();
285: modCount = fullList.modCount;
286: }
287: return result;
288: }
289: throw new ConcurrentModificationException();
290: }
291:
292: @Override
293: public E get(int location) {
294: if (modCount == fullList.modCount) {
295: if (0 <= location && location < size) {
296: return fullList.get(location + offset);
297: }
298: throw new IndexOutOfBoundsException();
299: }
300: throw new ConcurrentModificationException();
301: }
302:
303: @Override
304: public Iterator<E> iterator() {
305: return listIterator(0);
306: }
307:
308: @Override
309: public ListIterator<E> listIterator(int location) {
310: if (modCount == fullList.modCount) {
311: if (0 <= location && location <= size) {
312: return new SubAbstractListIterator<E>(fullList
313: .listIterator(location + offset), this ,
314: offset, size);
315: }
316: throw new IndexOutOfBoundsException();
317: }
318: throw new ConcurrentModificationException();
319: }
320:
321: @Override
322: public E remove(int location) {
323: if (modCount == fullList.modCount) {
324: if (0 <= location && location < size) {
325: E result = fullList.remove(location + offset);
326: size--;
327: modCount = fullList.modCount;
328: return result;
329: }
330: throw new IndexOutOfBoundsException();
331: }
332: throw new ConcurrentModificationException();
333: }
334:
335: @Override
336: protected void removeRange(int start, int end) {
337: if (start != end) {
338: if (modCount == fullList.modCount) {
339: fullList.removeRange(start + offset, end + offset);
340: size -= end - start;
341: modCount = fullList.modCount;
342: } else {
343: throw new ConcurrentModificationException();
344: }
345: }
346: }
347:
348: @Override
349: public E set(int location, E object) {
350: if (modCount == fullList.modCount) {
351: if (0 <= location && location < size) {
352: return fullList.set(location + offset, object);
353: }
354: throw new IndexOutOfBoundsException();
355: }
356: throw new ConcurrentModificationException();
357: }
358:
359: @Override
360: public int size() {
361: return size;
362: }
363:
364: void sizeChanged(boolean increment) {
365: if (increment) {
366: size++;
367: } else {
368: size--;
369: }
370: modCount = fullList.modCount;
371: }
372: }
373:
374: /**
375: * Constructs a new instance of this AbstractList.
376: *
377: */
378: protected AbstractList() {
379: super ();
380: }
381:
382: /**
383: * Inserts the specified object into this List at the specified location.
384: * The object is inserted before any previous element at the specified
385: * location. If the location is equal to the size of this List, the object
386: * is added at the end.
387: *
388: *
389: * @param location
390: * the index at which to insert
391: * @param object
392: * the object to add
393: *
394: * @exception UnsupportedOperationException
395: * when adding to this List is not supported
396: * @exception ClassCastException
397: * when the class of the object is inappropriate for this
398: * List
399: * @exception IllegalArgumentException
400: * when the object cannot be added to this List
401: * @exception IndexOutOfBoundsException
402: * when <code>location < 0 || >= size()</code>
403: */
404: public void add(int location, E object) {
405: throw new UnsupportedOperationException();
406: }
407:
408: /**
409: * Adds the specified object at the end of this List.
410: *
411: *
412: * @param object
413: * the object to add
414: * @return true
415: *
416: * @exception UnsupportedOperationException
417: * when adding to this List is not supported
418: * @exception ClassCastException
419: * when the class of the object is inappropriate for this
420: * List
421: * @exception IllegalArgumentException
422: * when the object cannot be added to this List
423: */
424: @Override
425: public boolean add(E object) {
426: add(size(), object);
427: return true;
428: }
429:
430: /**
431: * Inserts the objects in the specified Collection at the specified location
432: * in this List. The objects are added in the order they are returned from
433: * the Collection iterator.
434: *
435: *
436: * @param location
437: * the index at which to insert
438: * @param collection
439: * the Collection of objects
440: * @return true if this List is modified, false otherwise
441: *
442: * @exception UnsupportedOperationException
443: * when adding to this List is not supported
444: * @exception ClassCastException
445: * when the class of an object is inappropriate for this List
446: * @exception IllegalArgumentException
447: * when an object cannot be added to this List
448: * @exception IndexOutOfBoundsException
449: * when <code>location < 0 || >= size()</code>
450: */
451: public boolean addAll(int location,
452: Collection<? extends E> collection) {
453: Iterator<? extends E> it = collection.iterator();
454: while (it.hasNext()) {
455: add(location++, it.next());
456: }
457: return !collection.isEmpty();
458: }
459:
460: /**
461: * Removes all elements from this List, leaving it empty.
462: *
463: *
464: * @exception UnsupportedOperationException
465: * when removing from this List is not supported
466: *
467: * @see List#isEmpty
468: * @see List#size
469: */
470: @Override
471: public void clear() {
472: removeRange(0, size());
473: }
474:
475: /**
476: * Compares the specified object to this List and answer if they are equal.
477: * The object must be a List which contains the same objects in the same
478: * order.
479: *
480: *
481: * @param object
482: * the object to compare with this object
483: * @return true if the specified object is equal to this List, false
484: * otherwise
485: *
486: * @see #hashCode
487: */
488: @Override
489: public boolean equals(Object object) {
490: if (this == object) {
491: return true;
492: }
493: if (object instanceof List) {
494: List<?> list = (List<?>) object;
495: if (list.size() != size()) {
496: return false;
497: }
498:
499: Iterator<?> it1 = iterator(), it2 = list.iterator();
500: while (it1.hasNext()) {
501: Object e1 = it1.next(), e2 = it2.next();
502: if (!(e1 == null ? e2 == null : e1.equals(e2))) {
503: return false;
504: }
505: }
506: return true;
507: }
508: return false;
509: }
510:
511: /**
512: * Answers the element at the specified location in this List.
513: *
514: *
515: * @param location
516: * the index of the element to return
517: * @return the element at the specified index
518: *
519: * @exception IndexOutOfBoundsException
520: * when <code>location < 0 || >= size()</code>
521: */
522: public abstract E get(int location);
523:
524: /**
525: * Answers an integer hash code for the receiver. Objects which are equal
526: * answer the same value for this method.
527: *
528: *
529: * @return the receiver's hash
530: *
531: * @see #equals
532: */
533: @Override
534: public int hashCode() {
535: int result = 1;
536: Iterator<?> it = iterator();
537: while (it.hasNext()) {
538: Object object = it.next();
539: result = (31 * result)
540: + (object == null ? 0 : object.hashCode());
541: }
542: return result;
543: }
544:
545: /**
546: * Searches this List for the specified object and returns the index of the
547: * first occurrence.
548: *
549: *
550: * @param object
551: * the object to search for
552: * @return the index of the first occurrence of the object
553: */
554: public int indexOf(Object object) {
555: ListIterator<?> it = listIterator();
556: if (object != null) {
557: while (it.hasNext()) {
558: if (object.equals(it.next())) {
559: return it.previousIndex();
560: }
561: }
562: } else {
563: while (it.hasNext()) {
564: if (it.next() == null) {
565: return it.previousIndex();
566: }
567: }
568: }
569: return -1;
570: }
571:
572: /**
573: * Answers an Iterator on the elements of this List. The elements are
574: * iterated in the same order that they occur in the List.
575: *
576: *
577: * @return an Iterator on the elements of this List
578: *
579: * @see Iterator
580: */
581: @Override
582: public Iterator<E> iterator() {
583: return new SimpleListIterator();
584: }
585:
586: /**
587: * Searches this List for the specified object and returns the index of the
588: * last occurrence.
589: *
590: *
591: * @param object
592: * the object to search for
593: * @return the index of the last occurrence of the object
594: */
595: public int lastIndexOf(Object object) {
596: ListIterator<?> it = listIterator(size());
597: if (object != null) {
598: while (it.hasPrevious()) {
599: if (object.equals(it.previous())) {
600: return it.nextIndex();
601: }
602: }
603: } else {
604: while (it.hasPrevious()) {
605: if (it.previous() == null) {
606: return it.nextIndex();
607: }
608: }
609: }
610: return -1;
611: }
612:
613: /**
614: * Answers a ListIterator on the elements of this List. The elements are
615: * iterated in the same order that they occur in the List.
616: *
617: *
618: * @return a ListIterator on the elements of this List
619: *
620: * @see ListIterator
621: */
622: public ListIterator<E> listIterator() {
623: return listIterator(0);
624: }
625:
626: /**
627: * Answers a ListIterator on the elements of this List. The elements are
628: * iterated in the same order that they occur in the List. The iteration
629: * starts at the specified location.
630: *
631: *
632: * @param location
633: * the index at which to start the iteration
634: * @return a ListIterator on the elements of this List
635: *
636: * @exception IndexOutOfBoundsException
637: * when <code>location < 0 || >= size()</code>
638: *
639: * @see ListIterator
640: */
641: public ListIterator<E> listIterator(int location) {
642: return new FullListIterator(location);
643: }
644:
645: /**
646: * Removes the object at the specified location from this List.
647: *
648: *
649: * @param location
650: * the index of the object to remove
651: * @return the removed object
652: *
653: * @exception UnsupportedOperationException
654: * when removing from this List is not supported
655: * @exception IndexOutOfBoundsException
656: * when <code>location < 0 || >= size()</code>
657: */
658: public E remove(int location) {
659: throw new UnsupportedOperationException();
660: }
661:
662: /**
663: * Removes the objects in the specified range from the start to the, but not
664: * including, end index.
665: *
666: *
667: * @param start
668: * the index at which to start removing
669: * @param end
670: * the index one past the end of the range to remove
671: *
672: * @exception UnsupportedOperationException
673: * when removing from this List is not supported
674: * @exception IndexOutOfBoundsException
675: * when <code>start < 0
676: */
677: protected void removeRange(int start, int end) {
678: Iterator<?> it = listIterator(start);
679: for (int i = start; i < end; i++) {
680: it.next();
681: it.remove();
682: }
683: }
684:
685: /**
686: * Replaces the element at the specified location in this List with the
687: * specified object.
688: *
689: *
690: * @param location
691: * the index at which to put the specified object
692: * @param object
693: * the object to add
694: * @return the previous element at the index
695: *
696: * @exception UnsupportedOperationException
697: * when replacing elements in this List is not supported
698: * @exception ClassCastException
699: * when the class of an object is inappropriate for this List
700: * @exception IllegalArgumentException
701: * when an object cannot be added to this List
702: * @exception IndexOutOfBoundsException
703: * when <code>location < 0 || >= size()</code>
704: */
705: public E set(int location, E object) {
706: throw new UnsupportedOperationException();
707: }
708:
709: /**
710: * Returns a part of consecutive elements of this list as a view. From start
711: * (inclusive), to end(exclusive). The returned view will be of zero length
712: * if start equals end. Any change occurs in the returned subList will be
713: * reflected to the original list, and vice-versa. All the supported
714: * optional operations by the original list will also be supported by this
715: * subList.
716: *
717: * This method can be used as a handy method to do some operations on a sub
718: * range of the original list. For example: list.subList(from, to).clear();
719: *
720: * If the original list is modified other than through the returned subList,
721: * the behavior of the returned subList becomes undefined.
722: *
723: * The returned subList is a subclass of AbstractList. The subclass stores
724: * offset, size of itself, and modCount of the original list. If the
725: * original list implements RandomAccess interface, the returned subList
726: * also implements RandomAccess interface.
727: *
728: * The subList's set(int, Object), get(int), add(int, Object), remove(int),
729: * addAll(int, Collection) and removeRange(int, int) methods first check the
730: * bounds, adjust offsets and then call the corresponding methods of the
731: * original AbstractList. addAll(Collection c) method of the returned
732: * subList calls the original addAll(offset + size, c).
733: *
734: * The listIterator(int) method of the subList wraps the original list
735: * iterator. The iterator() method of the subList invokes the original
736: * listIterator() method, and the size() method merely returns the size of
737: * the subList.
738: *
739: * All methods will throw a ConcurrentModificationException if the modCount
740: * of the original list is not equal to the expected value.
741: *
742: * @param start
743: * start index of the subList, include start
744: * @param end
745: * end index of the subList, exclude end
746: * @return a subList view of this list start from start (inclusive), end
747: * with end (exclusive)
748: * @exception IndexOutOfBoundsException
749: * when (start < 0 || end > size())
750: * @exception IllegalArgumentException
751: * when (start > end)
752: */
753: public List<E> subList(int start, int end) {
754: if (0 <= start && end <= size()) {
755: if (start <= end) {
756: if (this instanceof RandomAccess) {
757: return new SubAbstractListRandomAccess<E>(this ,
758: start, end);
759: }
760: return new SubAbstractList<E>(this , start, end);
761: }
762: throw new IllegalArgumentException();
763: }
764: throw new IndexOutOfBoundsException();
765: }
766: }
|