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; 28import com.google.common.annotations.GwtIncompatible; 29 30import java.util.Collection; 31import java.util.Collections; 32import java.util.Comparator; 33import java.util.Iterator; 34import java.util.NoSuchElementException; 35import java.util.Set; 36 37import javax.annotation.Nullable; 38 39/** 40 * An immutable sorted set with one or more elements. TODO(jlevy): Consider 41 * separate class for a single-element sorted set. 42 * 43 * @author Jared Levy 44 * @author Louis Wasserman 45 */ 46@GwtCompatible(serializable = true, emulated = true) 47@SuppressWarnings("serial") 48final class RegularImmutableSortedSet<E> extends ImmutableSortedSet<E> { 49 50 private transient final ImmutableList<E> elements; 51 52 RegularImmutableSortedSet( 53 ImmutableList<E> elements, Comparator<? super E> comparator) { 54 super(comparator); 55 this.elements = elements; 56 checkArgument(!elements.isEmpty()); 57 } 58 59 @Override public UnmodifiableIterator<E> iterator() { 60 return elements.iterator(); 61 } 62 63 @GwtIncompatible("NavigableSet") 64 @Override public UnmodifiableIterator<E> descendingIterator() { 65 return elements.reverse().iterator(); 66 } 67 68 @Override public boolean isEmpty() { 69 return false; 70 } 71 72 @Override 73 public int size() { 74 return elements.size(); 75 } 76 77 @Override public boolean contains(Object o) { 78 try { 79 return o != null && unsafeBinarySearch(o) >= 0; 80 } catch (ClassCastException e) { 81 return false; 82 } 83 } 84 85 @Override public boolean containsAll(Collection<?> targets) { 86 // TODO(jlevy): For optimal performance, use a binary search when 87 // targets.size() < size() / log(size()) 88 // TODO(kevinb): see if we can share code with OrderedIterator after it 89 // graduates from labs. 90 if (targets instanceof Multiset) { 91 targets = ((Multiset<?>) targets).elementSet(); 92 } 93 if (!SortedIterables.hasSameComparator(comparator(), targets) 94 || (targets.size() <= 1)) { 95 return super.containsAll(targets); 96 } 97 98 /* 99 * If targets is a sorted set with the same comparator, containsAll can run 100 * in O(n) time stepping through the two collections. 101 */ 102 PeekingIterator<E> thisIterator = Iterators.peekingIterator(iterator()); 103 Iterator<?> thatIterator = targets.iterator(); 104 Object target = thatIterator.next(); 105 106 try { 107 108 while (thisIterator.hasNext()) { 109 110 int cmp = unsafeCompare(thisIterator.peek(), target); 111 112 if (cmp < 0) { 113 thisIterator.next(); 114 } else if (cmp == 0) { 115 116 if (!thatIterator.hasNext()) { 117 118 return true; 119 } 120 121 target = thatIterator.next(); 122 123 } else if (cmp > 0) { 124 return false; 125 } 126 } 127 } catch (NullPointerException e) { 128 return false; 129 } catch (ClassCastException e) { 130 return false; 131 } 132 133 return false; 134 } 135 136 private int unsafeBinarySearch(Object key) throws ClassCastException { 137 return Collections.binarySearch(elements, key, unsafeComparator()); 138 } 139 140 @Override boolean isPartialView() { 141 return elements.isPartialView(); 142 } 143 144 @Override 145 int copyIntoArray(Object[] dst, int offset) { 146 return elements.copyIntoArray(dst, offset); 147 } 148 149 @Override public boolean equals(@Nullable Object object) { 150 if (object == this) { 151 return true; 152 } 153 if (!(object instanceof Set)) { 154 return false; 155 } 156 157 Set<?> that = (Set<?>) object; 158 if (size() != that.size()) { 159 return false; 160 } 161 162 if (SortedIterables.hasSameComparator(comparator, that)) { 163 Iterator<?> otherIterator = that.iterator(); 164 try { 165 Iterator<E> iterator = iterator(); 166 while (iterator.hasNext()) { 167 Object element = iterator.next(); 168 Object otherElement = otherIterator.next(); 169 if (otherElement == null 170 || unsafeCompare(element, otherElement) != 0) { 171 return false; 172 } 173 } 174 return true; 175 } catch (ClassCastException e) { 176 return false; 177 } catch (NoSuchElementException e) { 178 return false; // concurrent change to other set 179 } 180 } 181 return this.containsAll(that); 182 } 183 184 @Override 185 public E first() { 186 return elements.get(0); 187 } 188 189 @Override 190 public E last() { 191 return elements.get(size() - 1); 192 } 193 194 @Override 195 public E lower(E element) { 196 int index = headIndex(element, false) - 1; 197 return (index == -1) ? null : elements.get(index); 198 } 199 200 @Override 201 public E floor(E element) { 202 int index = headIndex(element, true) - 1; 203 return (index == -1) ? null : elements.get(index); 204 } 205 206 @Override 207 public E ceiling(E element) { 208 int index = tailIndex(element, true); 209 return (index == size()) ? null : elements.get(index); 210 } 211 212 @Override 213 public E higher(E element) { 214 int index = tailIndex(element, false); 215 return (index == size()) ? null : elements.get(index); 216 } 217 218 @Override 219 ImmutableSortedSet<E> headSetImpl(E toElement, boolean inclusive) { 220 return getSubSet(0, headIndex(toElement, inclusive)); 221 } 222 223 int headIndex(E toElement, boolean inclusive) { 224 return SortedLists.binarySearch( 225 elements, checkNotNull(toElement), comparator(), 226 inclusive ? FIRST_AFTER : FIRST_PRESENT, NEXT_HIGHER); 227 } 228 229 @Override 230 ImmutableSortedSet<E> subSetImpl( 231 E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) { 232 return tailSetImpl(fromElement, fromInclusive) 233 .headSetImpl(toElement, toInclusive); 234 } 235 236 @Override 237 ImmutableSortedSet<E> tailSetImpl(E fromElement, boolean inclusive) { 238 return getSubSet(tailIndex(fromElement, inclusive), size()); 239 } 240 241 int tailIndex(E fromElement, boolean inclusive) { 242 return SortedLists.binarySearch( 243 elements, 244 checkNotNull(fromElement), 245 comparator(), 246 inclusive ? FIRST_PRESENT : FIRST_AFTER, NEXT_HIGHER); 247 } 248 249 // Pretend the comparator can compare anything. If it turns out it can't 250 // compare two elements, it'll throw a CCE. Only methods that are specified to 251 // throw CCE should call this. 252 @SuppressWarnings("unchecked") 253 Comparator<Object> unsafeComparator() { 254 return (Comparator<Object>) comparator; 255 } 256 257 ImmutableSortedSet<E> getSubSet(int newFromIndex, int newToIndex) { 258 if (newFromIndex == 0 && newToIndex == size()) { 259 return this; 260 } else if (newFromIndex < newToIndex) { 261 return new RegularImmutableSortedSet<E>( 262 elements.subList(newFromIndex, newToIndex), comparator); 263 } else { 264 return emptySet(comparator); 265 } 266 } 267 268 @Override int indexOf(@Nullable Object target) { 269 if (target == null) { 270 return -1; 271 } 272 int position; 273 try { 274 position = SortedLists.binarySearch(elements, target, unsafeComparator(), 275 ANY_PRESENT, INVERTED_INSERTION_INDEX); 276 } catch (ClassCastException e) { 277 return -1; 278 } 279 return (position >= 0) ? position : -1; 280 } 281 282 @Override ImmutableList<E> createAsList() { 283 return new ImmutableSortedAsList<E>(this, elements); 284 } 285 286 @Override 287 ImmutableSortedSet<E> createDescendingSet() { 288 return new RegularImmutableSortedSet<E>(elements.reverse(), 289 Ordering.from(comparator).reverse()); 290 } 291} 292