11d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert/* 21d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Copyright (C) 2009 The Guava Authors 31d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 41d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except 51d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * in compliance with the License. You may obtain a copy of the License at 61d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 71d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * http://www.apache.org/licenses/LICENSE-2.0 81d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 91d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Unless required by applicable law or agreed to in writing, software distributed under the 101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either 111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * express or implied. See the License for the specific language governing permissions and 121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * limitations under the License. 131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertpackage com.google.common.collect; 161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.base.Preconditions; 181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.Comparator; 201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport javax.annotation.Nullable; 221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert/** 241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * List returned by {@code ImmutableSortedSet.asList()} when the set isn't empty. 251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @author Jared Levy 271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @author Louis Wasserman 281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert@SuppressWarnings("serial") 301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertfinal class ImmutableSortedAsList<E> extends ImmutableList<E> implements SortedIterable<E> { 311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private final transient ImmutableSortedSet<E> backingSet; 321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private final transient ImmutableList<E> backingList; 331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert ImmutableSortedAsList( 351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert ImmutableSortedSet<E> backingSet, ImmutableList<E> backingList) { 361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert this.backingSet = backingSet; 371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert this.backingList = backingList; 381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public Comparator<? super E> comparator() { 411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return backingSet.comparator(); 421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // Override contains(), indexOf(), and lastIndexOf() to be O(log N) instead of O(N). 451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public boolean contains(@Nullable Object target) { 471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // TODO: why not contains(target)? 481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return backingSet.indexOf(target) >= 0; 491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public int indexOf(@Nullable Object target) { 521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return backingSet.indexOf(target); 531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public int lastIndexOf(@Nullable Object target) { 561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return backingSet.indexOf(target); 571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // The returned ImmutableSortedAsList maintains the contains(), indexOf(), and 601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // lastIndexOf() performance benefits. 611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public ImmutableList<E> subList(int fromIndex, int toIndex) { 621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Preconditions.checkPositionIndexes(fromIndex, toIndex, size()); 631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (fromIndex == toIndex) ? ImmutableList.<E>of() 641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert : new RegularImmutableSortedSet<E>( 651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert backingList.subList(fromIndex, toIndex), backingSet.comparator()) 661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert .asList(); 671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // The ImmutableAsList serialized form has the correct behavior. 701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override Object writeReplace() { 711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new ImmutableAsList.SerializedForm(backingSet); 721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public UnmodifiableIterator<E> iterator() { 751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return backingList.iterator(); 761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public E get(int index) { 791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return backingList.get(index); 801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public UnmodifiableListIterator<E> listIterator() { 831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return backingList.listIterator(); 841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public UnmodifiableListIterator<E> listIterator(int index) { 871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return backingList.listIterator(index); 881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public int size() { 911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return backingList.size(); 921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public boolean equals(@Nullable Object obj) { 951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return backingList.equals(obj); 961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public int hashCode() { 991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return backingList.hashCode(); 1001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override boolean isPartialView() { 1031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return backingList.isPartialView(); 1041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert} 106