1/* 2 * Copyright (C) 2009 The Guava Authors 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17package com.google.common.collect; 18 19import static com.google.common.base.Preconditions.checkArgument; 20import static com.google.common.base.Preconditions.checkNotNull; 21import static com.google.common.collect.SortedLists.KeyAbsentBehavior.INVERTED_INSERTION_INDEX; 22import static com.google.common.collect.SortedLists.KeyAbsentBehavior.NEXT_HIGHER; 23import static com.google.common.collect.SortedLists.KeyPresentBehavior.ANY_PRESENT; 24import static com.google.common.collect.SortedLists.KeyPresentBehavior.FIRST_AFTER; 25import static com.google.common.collect.SortedLists.KeyPresentBehavior.FIRST_PRESENT; 26 27import com.google.common.annotations.GwtCompatible; 28 29import java.util.Collection; 30import java.util.Collections; 31import java.util.Comparator; 32import java.util.Iterator; 33import java.util.NoSuchElementException; 34import java.util.Set; 35 36import javax.annotation.Nullable; 37 38/** 39 * An immutable sorted set with one or more elements. TODO(jlevy): Consider 40 * separate class for a single-element sorted set. 41 * 42 * @author Jared Levy 43 * @author Louis Wasserman 44 */ 45@GwtCompatible(serializable = true, emulated = true) 46@SuppressWarnings("serial") 47final class RegularImmutableSortedSet<E> extends ImmutableSortedSet<E> { 48 49 private transient final ImmutableList<E> elements; 50 51 RegularImmutableSortedSet( 52 ImmutableList<E> elements, Comparator<? super E> comparator) { 53 super(comparator); 54 this.elements = elements; 55 checkArgument(!elements.isEmpty()); 56 } 57 58 @Override public UnmodifiableIterator<E> iterator() { 59 return elements.iterator(); 60 } 61 62 @Override public boolean isEmpty() { 63 return false; 64 } 65 66 @Override 67 public int size() { 68 return elements.size(); 69 } 70 71 @Override public boolean contains(Object o) { 72 if (o == null) { 73 return false; 74 } 75 try { 76 return binarySearch(o) >= 0; 77 } catch (ClassCastException e) { 78 return false; 79 } 80 } 81 82 @Override public boolean containsAll(Collection<?> targets) { 83 // TODO(jlevy): For optimal performance, use a binary search when 84 // targets.size() < size() / log(size()) 85 // TODO(kevinb): see if we can share code with OrderedIterator after it 86 // graduates from labs. 87 if (!SortedIterables.hasSameComparator(comparator(), targets) 88 || (targets.size() <= 1)) { 89 return super.containsAll(targets); 90 } 91 92 /* 93 * If targets is a sorted set with the same comparator, containsAll can run 94 * in O(n) time stepping through the two collections. 95 */ 96 Iterator<E> thisIterator = iterator(); 97 Iterator<?> thatIterator = targets.iterator(); 98 Object target = thatIterator.next(); 99 100 try { 101 102 while (thisIterator.hasNext()) { 103 104 int cmp = unsafeCompare(thisIterator.next(), target); 105 106 if (cmp == 0) { 107 108 if (!thatIterator.hasNext()) { 109 110 return true; 111 } 112 113 target = thatIterator.next(); 114 115 } else if (cmp > 0) { 116 return false; 117 } 118 } 119 } catch (NullPointerException e) { 120 return false; 121 } catch (ClassCastException e) { 122 return false; 123 } 124 125 return false; 126 } 127 128 private int binarySearch(Object key) { 129 // TODO(kevinb): split this into binarySearch(E) and 130 // unsafeBinarySearch(Object), use each appropriately. name all methods that 131 // might throw CCE "unsafe*". 132 133 // Pretend the comparator can compare anything. If it turns out it can't 134 // compare a and b, we should get a CCE on the subsequent line. Only methods 135 // that are spec'd to throw CCE should call this. 136 @SuppressWarnings("unchecked") 137 Comparator<Object> unsafeComparator = (Comparator<Object>) comparator; 138 139 return Collections.binarySearch(elements, key, unsafeComparator); 140 } 141 142 @Override boolean isPartialView() { 143 return elements.isPartialView(); 144 } 145 146 @Override public Object[] toArray() { 147 return elements.toArray(); 148 } 149 150 @Override public <T> T[] toArray(T[] array) { 151 return elements.toArray(array); 152 } 153 154 @Override public boolean equals(@Nullable Object object) { 155 if (object == this) { 156 return true; 157 } 158 if (!(object instanceof Set)) { 159 return false; 160 } 161 162 Set<?> that = (Set<?>) object; 163 if (size() != that.size()) { 164 return false; 165 } 166 167 if (SortedIterables.hasSameComparator(comparator, that)) { 168 Iterator<?> otherIterator = that.iterator(); 169 try { 170 Iterator<E> iterator = iterator(); 171 while (iterator.hasNext()) { 172 Object element = iterator.next(); 173 Object otherElement = otherIterator.next(); 174 if (otherElement == null 175 || unsafeCompare(element, otherElement) != 0) { 176 return false; 177 } 178 } 179 return true; 180 } catch (ClassCastException e) { 181 return false; 182 } catch (NoSuchElementException e) { 183 return false; // concurrent change to other set 184 } 185 } 186 return this.containsAll(that); 187 } 188 189 @Override 190 public E first() { 191 return elements.get(0); 192 } 193 194 @Override 195 public E last() { 196 return elements.get(size() - 1); 197 } 198 199 @Override 200 ImmutableSortedSet<E> headSetImpl(E toElement, boolean inclusive) { 201 int index; 202 if (inclusive) { 203 index = SortedLists.binarySearch( 204 elements, checkNotNull(toElement), comparator(), FIRST_AFTER, NEXT_HIGHER); 205 } else { 206 index = SortedLists.binarySearch( 207 elements, checkNotNull(toElement), comparator(), FIRST_PRESENT, NEXT_HIGHER); 208 } 209 return createSubset(0, index); 210 } 211 212 @Override 213 ImmutableSortedSet<E> subSetImpl( 214 E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) { 215 return tailSetImpl(fromElement, fromInclusive) 216 .headSetImpl(toElement, toInclusive); 217 } 218 219 @Override 220 ImmutableSortedSet<E> tailSetImpl(E fromElement, boolean inclusive) { 221 int index; 222 if (inclusive) { 223 index = SortedLists.binarySearch( 224 elements, checkNotNull(fromElement), comparator(), FIRST_PRESENT, NEXT_HIGHER); 225 } else { 226 index = SortedLists.binarySearch( 227 elements, checkNotNull(fromElement), comparator(), FIRST_AFTER, NEXT_HIGHER); 228 } 229 return createSubset(index, size()); 230 } 231 232 // Pretend the comparator can compare anything. If it turns out it can't 233 // compare two elements, it'll throw a CCE. Only methods that are specified to 234 // throw CCE should call this. 235 @SuppressWarnings("unchecked") 236 Comparator<Object> unsafeComparator() { 237 return (Comparator<Object>) comparator; 238 } 239 240 private ImmutableSortedSet<E> createSubset(int newFromIndex, int newToIndex) { 241 if (newFromIndex == 0 && newToIndex == size()) { 242 return this; 243 } else if (newFromIndex < newToIndex) { 244 return new RegularImmutableSortedSet<E>( 245 elements.subList(newFromIndex, newToIndex), comparator); 246 } else { 247 return emptySet(comparator); 248 } 249 } 250 251 @SuppressWarnings("unchecked") 252 @Override int indexOf(@Nullable Object target) { 253 if (target == null) { 254 return -1; 255 } 256 int position; 257 try { 258 position = SortedLists.binarySearch(elements, (E) target, comparator(), 259 ANY_PRESENT, INVERTED_INSERTION_INDEX); 260 } catch (ClassCastException e) { 261 return -1; 262 } 263 // TODO(kevinb): reconsider if it's really worth making feeble attempts at 264 // sanity for inconsistent comparators. 265 266 // The equals() check is needed when the comparator isn't compatible with 267 // equals(). 268 return (position >= 0 && elements.get(position).equals(target)) 269 ? position : -1; 270 } 271 272 @Override ImmutableList<E> createAsList() { 273 return new ImmutableSortedAsList<E>(this, elements); 274 } 275} 276