11d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert/* 21d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Copyright (C) 2009 The Guava Authors 31d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 41d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Licensed under the Apache License, Version 2.0 (the "License"); 51d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * you may not use this file except in compliance with the License. 61d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * You may obtain a copy of the License at 71d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 81d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * http://www.apache.org/licenses/LICENSE-2.0 91d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Unless required by applicable law or agreed to in writing, software 111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * distributed under the License is distributed on an "AS IS" BASIS, 121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * See the License for the specific language governing permissions and 141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * limitations under the License. 151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertpackage com.google.common.collect; 181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport static com.google.common.base.Preconditions.checkArgument; 201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport static com.google.common.base.Preconditions.checkNotNull; 211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport static com.google.common.collect.SortedLists.KeyAbsentBehavior.INVERTED_INSERTION_INDEX; 221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport static com.google.common.collect.SortedLists.KeyAbsentBehavior.NEXT_HIGHER; 231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport static com.google.common.collect.SortedLists.KeyPresentBehavior.ANY_PRESENT; 241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport static com.google.common.collect.SortedLists.KeyPresentBehavior.FIRST_AFTER; 251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport static com.google.common.collect.SortedLists.KeyPresentBehavior.FIRST_PRESENT; 261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.annotations.GwtCompatible; 281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.Collection; 301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.Collections; 311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.Comparator; 321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.Iterator; 331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.NoSuchElementException; 341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.Set; 351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport javax.annotation.Nullable; 371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert/** 391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * An immutable sorted set with one or more elements. TODO(jlevy): Consider 401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * separate class for a single-element sorted set. 411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @author Jared Levy 431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @author Louis Wasserman 441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert@GwtCompatible(serializable = true, emulated = true) 461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert@SuppressWarnings("serial") 471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertfinal class RegularImmutableSortedSet<E> extends ImmutableSortedSet<E> { 481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private transient final ImmutableList<E> elements; 501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert RegularImmutableSortedSet( 521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert ImmutableList<E> elements, Comparator<? super E> comparator) { 531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert super(comparator); 541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert this.elements = elements; 551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkArgument(!elements.isEmpty()); 561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public UnmodifiableIterator<E> iterator() { 591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return elements.iterator(); 601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public boolean isEmpty() { 631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return false; 641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public int size() { 681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return elements.size(); 691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public boolean contains(Object o) { 721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (o == null) { 731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return false; 741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert try { 761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return binarySearch(o) >= 0; 771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } catch (ClassCastException e) { 781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return false; 791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public boolean containsAll(Collection<?> targets) { 831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // TODO(jlevy): For optimal performance, use a binary search when 841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // targets.size() < size() / log(size()) 851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // TODO(kevinb): see if we can share code with OrderedIterator after it 861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // graduates from labs. 871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (!SortedIterables.hasSameComparator(comparator(), targets) 881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert || (targets.size() <= 1)) { 891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return super.containsAll(targets); 901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /* 931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * If targets is a sorted set with the same comparator, containsAll can run 941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * in O(n) time stepping through the two collections. 951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Iterator<E> thisIterator = iterator(); 971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Iterator<?> thatIterator = targets.iterator(); 981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Object target = thatIterator.next(); 991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert try { 1011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert while (thisIterator.hasNext()) { 1031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int cmp = unsafeCompare(thisIterator.next(), target); 1051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (cmp == 0) { 1071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (!thatIterator.hasNext()) { 1091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return true; 1111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert target = thatIterator.next(); 1141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } else if (cmp > 0) { 1161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return false; 1171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } catch (NullPointerException e) { 1201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return false; 1211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } catch (ClassCastException e) { 1221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return false; 1231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return false; 1261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private int binarySearch(Object key) { 1291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // TODO(kevinb): split this into binarySearch(E) and 1301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // unsafeBinarySearch(Object), use each appropriately. name all methods that 1311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // might throw CCE "unsafe*". 1321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // Pretend the comparator can compare anything. If it turns out it can't 1341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // compare a and b, we should get a CCE on the subsequent line. Only methods 1351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // that are spec'd to throw CCE should call this. 1361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @SuppressWarnings("unchecked") 1371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Comparator<Object> unsafeComparator = (Comparator<Object>) comparator; 1381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return Collections.binarySearch(elements, key, unsafeComparator); 1401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override boolean isPartialView() { 1431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return elements.isPartialView(); 1441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public Object[] toArray() { 1471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return elements.toArray(); 1481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public <T> T[] toArray(T[] array) { 1511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return elements.toArray(array); 1521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public boolean equals(@Nullable Object object) { 1551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (object == this) { 1561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return true; 1571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (!(object instanceof Set)) { 1591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return false; 1601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Set<?> that = (Set<?>) object; 1631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (size() != that.size()) { 1641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return false; 1651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (SortedIterables.hasSameComparator(comparator, that)) { 1681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Iterator<?> otherIterator = that.iterator(); 1691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert try { 1701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Iterator<E> iterator = iterator(); 1711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert while (iterator.hasNext()) { 1721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Object element = iterator.next(); 1731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Object otherElement = otherIterator.next(); 1741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (otherElement == null 1751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert || unsafeCompare(element, otherElement) != 0) { 1761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return false; 1771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return true; 1801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } catch (ClassCastException e) { 1811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return false; 1821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } catch (NoSuchElementException e) { 1831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return false; // concurrent change to other set 1841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return this.containsAll(that); 1871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 1901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public E first() { 1911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return elements.get(0); 1921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 1951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public E last() { 1961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return elements.get(size() - 1); 1971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 2001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert ImmutableSortedSet<E> headSetImpl(E toElement, boolean inclusive) { 2011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int index; 2021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (inclusive) { 2031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert index = SortedLists.binarySearch( 2041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert elements, checkNotNull(toElement), comparator(), FIRST_AFTER, NEXT_HIGHER); 2051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } else { 2061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert index = SortedLists.binarySearch( 2071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert elements, checkNotNull(toElement), comparator(), FIRST_PRESENT, NEXT_HIGHER); 2081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return createSubset(0, index); 2101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 2131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert ImmutableSortedSet<E> subSetImpl( 2141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) { 2151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return tailSetImpl(fromElement, fromInclusive) 2161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert .headSetImpl(toElement, toInclusive); 2171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 2201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert ImmutableSortedSet<E> tailSetImpl(E fromElement, boolean inclusive) { 2211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int index; 2221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (inclusive) { 2231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert index = SortedLists.binarySearch( 2241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert elements, checkNotNull(fromElement), comparator(), FIRST_PRESENT, NEXT_HIGHER); 2251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } else { 2261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert index = SortedLists.binarySearch( 2271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert elements, checkNotNull(fromElement), comparator(), FIRST_AFTER, NEXT_HIGHER); 2281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return createSubset(index, size()); 2301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // Pretend the comparator can compare anything. If it turns out it can't 2331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // compare two elements, it'll throw a CCE. Only methods that are specified to 2341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // throw CCE should call this. 2351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @SuppressWarnings("unchecked") 2361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Comparator<Object> unsafeComparator() { 2371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (Comparator<Object>) comparator; 2381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private ImmutableSortedSet<E> createSubset(int newFromIndex, int newToIndex) { 2411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (newFromIndex == 0 && newToIndex == size()) { 2421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return this; 2431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } else if (newFromIndex < newToIndex) { 2441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new RegularImmutableSortedSet<E>( 2451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert elements.subList(newFromIndex, newToIndex), comparator); 2461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } else { 2471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return emptySet(comparator); 2481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @SuppressWarnings("unchecked") 2521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override int indexOf(@Nullable Object target) { 2531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (target == null) { 2541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return -1; 2551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int position; 2571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert try { 2581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert position = SortedLists.binarySearch(elements, (E) target, comparator(), 2591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert ANY_PRESENT, INVERTED_INSERTION_INDEX); 2601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } catch (ClassCastException e) { 2611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return -1; 2621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // TODO(kevinb): reconsider if it's really worth making feeble attempts at 2641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // sanity for inconsistent comparators. 2651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // The equals() check is needed when the comparator isn't compatible with 2671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // equals(). 2681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (position >= 0 && elements.get(position).equals(target)) 2691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert ? position : -1; 2701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override ImmutableList<E> createAsList() { 2731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new ImmutableSortedAsList<E>(this, elements); 2741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert} 276