1090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson/* 21d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Copyright (C) 2009 The Guava Authors 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 Wilson 24090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport javax.annotation.Nullable; 25090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 26090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson/** 27090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Implementation of {@link ImmutableList} with one or more elements. 28090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 29090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @author Kevin Bourrillion 30090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert@GwtCompatible(serializable = true, emulated = true) 32090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson@SuppressWarnings("serial") // uses writeReplace(), not default serialization 33bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnorclass RegularImmutableList<E> extends ImmutableList<E> { 34090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private final transient int offset; 35090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private final transient int size; 36090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private final transient Object[] array; 37090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 38090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson RegularImmutableList(Object[] array, int offset, int size) { 39090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson this.offset = offset; 40090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson this.size = size; 41090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson this.array = array; 42090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 43090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 44090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson RegularImmutableList(Object[] array) { 45090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson this(array, 0, array.length); 46090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 47090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 49090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public int size() { 50090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return size; 51090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 52090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 53090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean isEmpty() { 54090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return false; 55090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 56090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override boolean isPartialView() { 581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return offset != 0 || size != array.length; 591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public boolean contains(@Nullable Object target) { 62090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return indexOf(target) != -1; 63090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 64090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 65090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // The fake cast to E is safe because the creation methods only allow E's 66090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @SuppressWarnings("unchecked") 67090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public UnmodifiableIterator<E> iterator() { 68090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return (UnmodifiableIterator<E>) Iterators.forArray(array, offset, size); 69090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 70090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 71090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public Object[] toArray() { 72090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Object[] newArray = new Object[size()]; 731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert System.arraycopy(array, offset, newArray, 0, size); 74090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return newArray; 75090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 76090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 77090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public <T> T[] toArray(T[] other) { 78090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (other.length < size) { 79090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson other = ObjectArrays.newArray(other, size); 80090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } else if (other.length > size) { 81090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson other[size] = null; 82090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert System.arraycopy(array, offset, other, 0, size); 84090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return other; 85090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 86090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 87090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // The fake cast to E is safe because the creation methods only allow E's 881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 89090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @SuppressWarnings("unchecked") 90090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public E get(int index) { 91090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Preconditions.checkElementIndex(index, size); 92090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return (E) array[index + offset]; 93090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 94090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public int indexOf(@Nullable Object target) { 96090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (target != null) { 97090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson for (int i = offset; i < offset + size; i++) { 98090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (array[i].equals(target)) { 99090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return i - offset; 100090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 101090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 102090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 103090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return -1; 104090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 105090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public int lastIndexOf(@Nullable Object target) { 107090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (target != null) { 108090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson for (int i = offset + size - 1; i >= offset; i--) { 109090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (array[i].equals(target)) { 110090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return i - offset; 111090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 112090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 113090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 114090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return -1; 115090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 116090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 117090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public ImmutableList<E> subList(int fromIndex, int toIndex) { 118090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Preconditions.checkPositionIndexes(fromIndex, toIndex, size); 119090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return (fromIndex == toIndex) 120090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson ? ImmutableList.<E>of() 121090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson : new RegularImmutableList<E>( 122090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson array, offset + fromIndex, toIndex - fromIndex); 123090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 124090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public UnmodifiableListIterator<E> listIterator(final int start) { 1261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new AbstractIndexedListIterator<E>(size, start) { 1271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // The fake cast to E is safe because the creation methods only allow E's 1281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @SuppressWarnings("unchecked") 1291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override protected E get(int index) { 1301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (E) array[index + offset]; 131090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 132090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 133090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson }; 134090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 135090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 136090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean equals(@Nullable Object object) { 137090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (object == this) { 138090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return true; 139090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 140090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (!(object instanceof List)) { 141090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return false; 142090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 143090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 144090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson List<?> that = (List<?>) object; 145090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (this.size() != that.size()) { 146090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return false; 147090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 148090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 149090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson int index = offset; 150090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (object instanceof RegularImmutableList) { 151090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson RegularImmutableList<?> other = (RegularImmutableList<?>) object; 152090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson for (int i = other.offset; i < other.offset + other.size; i++) { 153090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (!array[index++].equals(other.array[i])) { 154090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return false; 155090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 156090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 157090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } else { 158090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson for (Object element : that) { 159090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (!array[index++].equals(element)) { 160090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return false; 161090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 162090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 163090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 164090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return true; 165090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 166090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 167090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public int hashCode() { 168090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // not caching hash code since it could change if the elements are mutable 169090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // in a way that modifies their hash codes 170090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson int hashCode = 1; 171090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson for (int i = offset; i < offset + size; i++) { 172090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson hashCode = 31 * hashCode + array[i].hashCode(); 173090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 174090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return hashCode; 175090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 176090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 177090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public String toString() { 1781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert StringBuilder sb = Collections2.newStringBuilderForCollection(size()) 1791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert .append('[').append(array[offset]); 180090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson for (int i = offset + 1; i < offset + size; i++) { 181090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson sb.append(", ").append(array[i]); 182090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 183090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return sb.append(']').toString(); 184090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 185090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson} 186