| /* |
| * Copyright 2007 Google Inc. |
| * |
| * Licensed under the Apache License, Version 2.0 (the "License"); you may not |
| * use this file except in compliance with the License. You may obtain a copy of |
| * the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT |
| * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the |
| * License for the specific language governing permissions and limitations under |
| * the License. |
| */ |
| package java.util; |
| |
| /** |
| * Skeletal implementation of the List interface. <a |
| * href="http://java.sun.com/j2se/1.5.0/docs/api/java/util/AbstractList.html">[Sun |
| * docs]</a> |
| * |
| * @param <E> the element type. |
| */ |
| public abstract class AbstractList<E> extends AbstractCollection<E> implements |
| List<E> { |
| |
| private class IteratorImpl implements Iterator<E> { |
| /* |
| * i is the index of the item that will be returned on the next call to |
| * next() last is the index of the item that was returned on the previous |
| * call to next() or previous (for ListIterator), -1 if no such item exists. |
| */ |
| |
| int i = 0, last = -1; |
| |
| public boolean hasNext() { |
| return i < AbstractList.this.size(); |
| } |
| |
| public E next() { |
| if (!hasNext()) { |
| throw new NoSuchElementException(); |
| } |
| return AbstractList.this.get(last = i++); |
| } |
| |
| public void remove() { |
| if (last < 0) { |
| throw new IllegalStateException(); |
| } |
| AbstractList.this.remove(last); |
| i = last; |
| last = -1; |
| } |
| } |
| |
| /** |
| * Implementation of <code>ListIterator</code> for abstract lists. |
| */ |
| private final class ListIteratorImpl extends IteratorImpl implements |
| ListIterator<E> { |
| /* |
| * i is the index of the item that will be returned on the next call to |
| * next() last is the index of the item that was returned on the previous |
| * call to next() or previous (for ListIterator), -1 if no such item exists. |
| */ |
| |
| private ListIteratorImpl() { |
| // Nothing to do |
| } |
| |
| private ListIteratorImpl(int start) { |
| int size = AbstractList.this.size(); |
| if (start < 0 || start > size) { |
| indexOutOfBounds(start, size); |
| } |
| i = start; |
| } |
| |
| public void add(E o) { |
| AbstractList.this.add(i++, o); |
| last = -1; |
| } |
| |
| public boolean hasPrevious() { |
| return i > 0; |
| } |
| |
| public int nextIndex() { |
| return i; |
| } |
| |
| public E previous() { |
| if (!hasPrevious()) { |
| throw new NoSuchElementException(); |
| } |
| return AbstractList.this.get(last = --i); |
| } |
| |
| public int previousIndex() { |
| return i - 1; |
| } |
| |
| public void set(E o) { |
| if (last == -1) { |
| throw new IllegalStateException(); |
| } |
| AbstractList.this.set(last, o); |
| } |
| } |
| |
| private static class SubList<E> extends AbstractList<E> { |
| private final List<E> wrapped; |
| private final int fromIndex; |
| private int size; |
| |
| public SubList(List<E> wrapped, int fromIndex, int toIndex) { |
| this.wrapped = wrapped; |
| this.fromIndex = fromIndex; |
| size = getSize(fromIndex, toIndex); |
| if (fromIndex > toIndex) { |
| throw new IllegalArgumentException("fromIndex: " + fromIndex + |
| " > toIndex: " + toIndex); |
| } |
| if (fromIndex < 0) { |
| throw new IndexOutOfBoundsException("fromIndex: " + fromIndex + |
| " < 0"); |
| } |
| if (toIndex > wrapped.size()) { |
| throw new IndexOutOfBoundsException("toIndex: " + toIndex + |
| " > wrapped.size() " + wrapped.size()); |
| } |
| } |
| |
| @Override |
| public void add(int index, E element) { |
| checkIndexForAdd(index); |
| size++; |
| wrapped.add(fromIndex + index, element); |
| } |
| |
| @Override |
| public E get(int index) { |
| checkIndex(index); |
| return wrapped.get(fromIndex + index); |
| } |
| |
| @Override |
| public E remove(int index) { |
| checkIndex(index); |
| E result = wrapped.remove(fromIndex + index); |
| size--; |
| return result; |
| } |
| |
| @Override |
| public E set(int index, E element) { |
| checkIndex(index); |
| return wrapped.set(fromIndex + index, element); |
| } |
| |
| @Override |
| public int size() { |
| return size; |
| } |
| |
| private void checkIndex(int index) { |
| checkIndex(index, size); |
| } |
| |
| private void checkIndexForAdd(int index) { |
| checkIndex(index, size + 1); |
| } |
| |
| private int getSize(int fromIndex, int toIndex) { |
| return toIndex - fromIndex; |
| } |
| } |
| |
| protected static void checkIndex(int index, int size) { |
| if (index < 0 || index >= size) { |
| indexOutOfBounds(index, size); |
| } |
| } |
| |
| /** |
| * Throws an <code>indexOutOfBoundsException</code>. |
| */ |
| protected static void indexOutOfBounds(int index, int size) { |
| throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size); |
| } |
| |
| protected AbstractList() { |
| } |
| |
| @Override |
| public boolean add(E obj) { |
| add(size(), obj); |
| return true; |
| } |
| |
| public void add(int index, E element) { |
| throw new UnsupportedOperationException("Add not supported on this list"); |
| } |
| |
| public boolean addAll(int index, Collection<? extends E> c) { |
| Iterator<? extends E> iter = c.iterator(); |
| boolean changed = false; |
| while (iter.hasNext()) { |
| add(index++, iter.next()); |
| changed = true; |
| } |
| return changed; |
| } |
| |
| @Override |
| public void clear() { |
| removeRange(0, size()); |
| } |
| |
| @Override |
| public boolean equals(Object o) { |
| if (o == this) { |
| return true; |
| } |
| |
| if (!(o instanceof List)) { |
| return false; |
| } |
| |
| List<?> other = (List<?>) o; |
| if (size() != other.size()) { |
| return false; |
| } |
| |
| Iterator<E> iter = iterator(); |
| Iterator<?> iterOther = other.iterator(); |
| |
| while (iter.hasNext()) { |
| E elem = iter.next(); |
| Object elemOther = iterOther.next(); |
| |
| if (!(elem == null ? elemOther == null : elem.equals(elemOther))) { |
| return false; |
| } |
| } |
| |
| return true; |
| } |
| |
| public abstract E get(int index); |
| |
| @Override |
| public int hashCode() { |
| int k = 1; |
| final int coeff = 31; |
| Iterator<E> iter = iterator(); |
| while (iter.hasNext()) { |
| E obj = iter.next(); |
| k = coeff * k + (obj == null ? 0 : obj.hashCode()); |
| k = ~~k; |
| } |
| return k; |
| } |
| |
| public int indexOf(Object toFind) { |
| for (int i = 0, n = size(); i < n; ++i) { |
| if (toFind == null ? get(i) == null : toFind.equals(get(i))) { |
| return i; |
| } |
| } |
| return -1; |
| } |
| |
| @Override |
| public Iterator<E> iterator() { |
| return new IteratorImpl(); |
| } |
| |
| public int lastIndexOf(Object toFind) { |
| for (int i = size() - 1; i > -1; --i) { |
| if (toFind == null ? get(i) == null : toFind.equals(get(i))) { |
| return i; |
| } |
| } |
| return -1; |
| } |
| |
| public ListIterator<E> listIterator() { |
| return listIterator(0); |
| } |
| |
| public ListIterator<E> listIterator(int from) { |
| return new ListIteratorImpl(from); |
| } |
| |
| public E remove(int index) { |
| throw new UnsupportedOperationException("Remove not supported on this list"); |
| } |
| |
| public E set(int index, E o) { |
| throw new UnsupportedOperationException("Set not supported on this list"); |
| } |
| |
| public List<E> subList(int fromIndex, int toIndex) { |
| return new SubList<E>(this, fromIndex, toIndex); |
| } |
| |
| protected void removeRange(int fromIndex, int endIndex) { |
| ListIterator<E> iter = listIterator(fromIndex); |
| for (int i = fromIndex; i < endIndex; ++i) { |
| iter.next(); |
| iter.remove(); |
| } |
| } |
| } |