RegularImmutableList.java revision bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dc
1090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson/* 2090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Copyright (C) 2009 Google Inc. 3090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 4090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Licensed under the Apache License, Version 2.0 (the "License"); 5090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * you may not use this file except in compliance with the License. 6090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * You may obtain a copy of the License at 7090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 8090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * http://www.apache.org/licenses/LICENSE-2.0 9090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 10090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Unless required by applicable law or agreed to in writing, software 11090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * distributed under the License is distributed on an "AS IS" BASIS, 12090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * See the License for the specific language governing permissions and 14090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * limitations under the License. 15090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 16090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 17090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonpackage com.google.common.collect; 18090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 19090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport com.google.common.annotations.GwtCompatible; 20090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport com.google.common.base.Preconditions; 21090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 22090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.List; 23090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.ListIterator; 24090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.NoSuchElementException; 25090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 26090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport javax.annotation.Nullable; 27090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 28090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson/** 29090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Implementation of {@link ImmutableList} with one or more elements. 30090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 31090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @author Kevin Bourrillion 32090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 33090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson@GwtCompatible(serializable = true) 34090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson@SuppressWarnings("serial") // uses writeReplace(), not default serialization 35bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnorclass RegularImmutableList<E> extends ImmutableList<E> { 36090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private final transient int offset; 37090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private final transient int size; 38090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private final transient Object[] array; 39090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 40090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson RegularImmutableList(Object[] array, int offset, int size) { 41090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson this.offset = offset; 42090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson this.size = size; 43090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson this.array = array; 44090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 45090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 46090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson RegularImmutableList(Object[] array) { 47090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson this(array, 0, array.length); 48090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 49090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 50090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public int size() { 51090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return size; 52090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 53090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 54090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean isEmpty() { 55090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return false; 56090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 57090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 58090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean contains(Object target) { 59090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return indexOf(target) != -1; 60090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 61090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 62090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // The fake cast to E is safe because the creation methods only allow E's 63090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @SuppressWarnings("unchecked") 64090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public UnmodifiableIterator<E> iterator() { 65090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return (UnmodifiableIterator<E>) Iterators.forArray(array, offset, size); 66090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 67090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 68090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public Object[] toArray() { 69090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Object[] newArray = new Object[size()]; 70bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor Platform.unsafeArrayCopy(array, offset, newArray, 0, size); 71090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return newArray; 72090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 73090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 74090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public <T> T[] toArray(T[] other) { 75090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (other.length < size) { 76090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson other = ObjectArrays.newArray(other, size); 77090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } else if (other.length > size) { 78090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson other[size] = null; 79090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 80bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor Platform.unsafeArrayCopy(array, offset, other, 0, size); 81090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return other; 82090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 83090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 84090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // The fake cast to E is safe because the creation methods only allow E's 85090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @SuppressWarnings("unchecked") 86090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public E get(int index) { 87090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Preconditions.checkElementIndex(index, size); 88090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return (E) array[index + offset]; 89090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 90090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 91090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public int indexOf(Object target) { 92090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (target != null) { 93090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson for (int i = offset; i < offset + size; i++) { 94090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (array[i].equals(target)) { 95090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return i - offset; 96090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 97090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 98090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 99090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return -1; 100090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 101090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 102090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public int lastIndexOf(Object target) { 103090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (target != null) { 104090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson for (int i = offset + size - 1; i >= offset; i--) { 105090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (array[i].equals(target)) { 106090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return i - offset; 107090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 108090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 109090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 110090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return -1; 111090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 112090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 113090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public ImmutableList<E> subList(int fromIndex, int toIndex) { 114090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Preconditions.checkPositionIndexes(fromIndex, toIndex, size); 115090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return (fromIndex == toIndex) 116090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson ? ImmutableList.<E>of() 117090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson : new RegularImmutableList<E>( 118090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson array, offset + fromIndex, toIndex - fromIndex); 119090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 120090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 121090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public ListIterator<E> listIterator() { 122090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return listIterator(0); 123090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 124090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 125090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public ListIterator<E> listIterator(final int start) { 126090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Preconditions.checkPositionIndex(start, size); 127090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 128090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new ListIterator<E>() { 129090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson int index = start; 130090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 131090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean hasNext() { 132090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return index < size; 133090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 134090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean hasPrevious() { 135090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return index > 0; 136090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 137090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 138090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public int nextIndex() { 139090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return index; 140090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 141090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public int previousIndex() { 142090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return index - 1; 143090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 144090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 145090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public E next() { 146090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson E result; 147090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson try { 148090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson result = get(index); 149090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } catch (IndexOutOfBoundsException rethrown) { 150090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson throw new NoSuchElementException(); 151090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 152090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson index++; 153090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return result; 154090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 155090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public E previous() { 156090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson E result; 157090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson try { 158090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson result = get(index - 1); 159090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } catch (IndexOutOfBoundsException rethrown) { 160090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson throw new NoSuchElementException(); 161090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 162090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson index--; 163090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return result; 164090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 165090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 166090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public void set(E o) { 167090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson throw new UnsupportedOperationException(); 168090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 169090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public void add(E o) { 170090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson throw new UnsupportedOperationException(); 171090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 172090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public void remove() { 173090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson throw new UnsupportedOperationException(); 174090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 175090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson }; 176090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 177090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 178090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean equals(@Nullable Object object) { 179090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (object == this) { 180090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return true; 181090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 182090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (!(object instanceof List)) { 183090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return false; 184090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 185090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 186090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson List<?> that = (List<?>) object; 187090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (this.size() != that.size()) { 188090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return false; 189090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 190090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 191090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson int index = offset; 192090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (object instanceof RegularImmutableList) { 193090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson RegularImmutableList<?> other = (RegularImmutableList<?>) object; 194090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson for (int i = other.offset; i < other.offset + other.size; i++) { 195090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (!array[index++].equals(other.array[i])) { 196090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return false; 197090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 198090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 199090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } else { 200090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson for (Object element : that) { 201090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (!array[index++].equals(element)) { 202090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return false; 203090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 204090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 205090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 206090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return true; 207090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 208090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 209090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public int hashCode() { 210090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // not caching hash code since it could change if the elements are mutable 211090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // in a way that modifies their hash codes 212090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson int hashCode = 1; 213090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson for (int i = offset; i < offset + size; i++) { 214090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson hashCode = 31 * hashCode + array[i].hashCode(); 215090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 216090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return hashCode; 217090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 218090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 219090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public String toString() { 220090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson StringBuilder sb = new StringBuilder(size() * 16); 221090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson sb.append('[').append(array[offset]); 222090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson for (int i = offset + 1; i < offset + size; i++) { 223090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson sb.append(", ").append(array[i]); 224090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 225090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return sb.append(']').toString(); 226090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 227bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor 228bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor int offset() { 229bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor return offset; 230bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 231bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor 232bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor Object[] array() { 233bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor return array; 234bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 235090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson} 236