| /* |
| * Copyright (C) 2009 Google Inc. |
| * |
| * Licensed under the Apache License, Version 2.0 (the "License"); |
| * you may not use this file except in compliance with the License. |
| * You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| |
| package com.google.common.collect; |
| |
| import com.google.common.annotations.GwtCompatible; |
| |
| import java.util.Collection; |
| import java.util.Comparator; |
| import java.util.Iterator; |
| import java.util.NoSuchElementException; |
| import java.util.Set; |
| |
| import javax.annotation.Nullable; |
| |
| /** |
| * An immutable sorted set with one or more elements. |
| * TODO: Consider creating a separate class for a single-element sorted set. |
| * |
| * @author Jared Levy |
| */ |
| @GwtCompatible(serializable = true) |
| @SuppressWarnings("serial") |
| final class RegularImmutableSortedSet<E> |
| extends ImmutableSortedSet<E> { |
| |
| private final Object[] elements; |
| /** |
| * The index of the first element that's in the sorted set (inclusive |
| * index). |
| */ |
| private final int fromIndex; |
| /** |
| * The index after the last element that's in the sorted set (exclusive |
| * index). |
| */ |
| private final int toIndex; |
| |
| RegularImmutableSortedSet(Object[] elements, |
| Comparator<? super E> comparator) { |
| super(comparator); |
| this.elements = elements; |
| this.fromIndex = 0; |
| this.toIndex = elements.length; |
| } |
| |
| RegularImmutableSortedSet(Object[] elements, |
| Comparator<? super E> comparator, int fromIndex, int toIndex) { |
| super(comparator); |
| this.elements = elements; |
| this.fromIndex = fromIndex; |
| this.toIndex = toIndex; |
| } |
| |
| // The factory methods ensure that every element is an E. |
| @SuppressWarnings("unchecked") |
| @Override public UnmodifiableIterator<E> iterator() { |
| return (UnmodifiableIterator<E>) |
| Iterators.forArray(elements, fromIndex, size()); |
| } |
| |
| @Override public boolean isEmpty() { |
| return false; |
| } |
| |
| public int size() { |
| return toIndex - fromIndex; |
| } |
| |
| @Override public boolean contains(Object o) { |
| if (o == null) { |
| return false; |
| } |
| try { |
| return binarySearch(o) >= 0; |
| } catch (ClassCastException e) { |
| return false; |
| } |
| } |
| |
| @Override public boolean containsAll(Collection<?> targets) { |
| // TODO: For optimal performance, use a binary search when |
| // targets.size() < size() / log(size()) |
| if (!hasSameComparator(targets, comparator()) || (targets.size() <= 1)) { |
| return super.containsAll(targets); |
| } |
| |
| /* |
| * If targets is a sorted set with the same comparator, containsAll can |
| * run in O(n) time stepping through the two collections. |
| */ |
| int i = fromIndex; |
| Iterator<?> iterator = targets.iterator(); |
| Object target = iterator.next(); |
| |
| while (true) { |
| if (i >= toIndex) { |
| return false; |
| } |
| |
| int cmp = unsafeCompare(elements[i], target); |
| |
| if (cmp < 0) { |
| i++; |
| } else if (cmp == 0) { |
| if (!iterator.hasNext()) { |
| return true; |
| } |
| target = iterator.next(); |
| i++; |
| } else if (cmp > 0) { |
| return false; |
| } |
| } |
| } |
| |
| private int binarySearch(Object key) { |
| int lower = fromIndex; |
| int upper = toIndex - 1; |
| |
| while (lower <= upper) { |
| int middle = lower + (upper - lower) / 2; |
| int c = unsafeCompare(key, elements[middle]); |
| if (c < 0) { |
| upper = middle - 1; |
| } else if (c > 0) { |
| lower = middle + 1; |
| } else { |
| return middle; |
| } |
| } |
| |
| return -lower - 1; |
| } |
| |
| @Override public Object[] toArray() { |
| Object[] array = new Object[size()]; |
| Platform.unsafeArrayCopy(elements, fromIndex, array, 0, size()); |
| return array; |
| } |
| |
| // TODO: Move to ObjectArrays (same code in ImmutableList). |
| @Override public <T> T[] toArray(T[] array) { |
| int size = size(); |
| if (array.length < size) { |
| array = ObjectArrays.newArray(array, size); |
| } else if (array.length > size) { |
| array[size] = null; |
| } |
| Platform.unsafeArrayCopy(elements, fromIndex, array, 0, size); |
| return array; |
| } |
| |
| @Override public boolean equals(@Nullable Object object) { |
| if (object == this) { |
| return true; |
| } |
| if (!(object instanceof Set)) { |
| return false; |
| } |
| |
| Set<?> that = (Set<?>) object; |
| if (size() != that.size()) { |
| return false; |
| } |
| |
| if (hasSameComparator(that, comparator)) { |
| Iterator<?> iterator = that.iterator(); |
| try { |
| for (int i = fromIndex; i < toIndex; i++) { |
| Object otherElement = iterator.next(); |
| if (otherElement == null |
| || unsafeCompare(elements[i], otherElement) != 0) { |
| return false; |
| } |
| } |
| return true; |
| } catch (ClassCastException e) { |
| return false; |
| } catch (NoSuchElementException e) { |
| return false; // concurrent change to other set |
| } |
| } |
| return this.containsAll(that); |
| } |
| |
| @Override public int hashCode() { |
| // not caching hash code since it could change if the elements are mutable |
| // in a way that modifies their hash codes |
| int hash = 0; |
| for (int i = fromIndex; i < toIndex; i++) { |
| hash += elements[i].hashCode(); |
| } |
| return hash; |
| } |
| |
| // The factory methods ensure that every element is an E. |
| @SuppressWarnings("unchecked") |
| public E first() { |
| return (E) elements[fromIndex]; |
| } |
| |
| // The factory methods ensure that every element is an E. |
| @SuppressWarnings("unchecked") |
| public E last() { |
| return (E) elements[toIndex - 1]; |
| } |
| |
| @Override ImmutableSortedSet<E> headSetImpl(E toElement) { |
| return createSubset(fromIndex, findSubsetIndex(toElement)); |
| } |
| |
| @Override ImmutableSortedSet<E> subSetImpl(E fromElement, E toElement) { |
| return createSubset( |
| findSubsetIndex(fromElement), findSubsetIndex(toElement)); |
| } |
| |
| @Override ImmutableSortedSet<E> tailSetImpl(E fromElement) { |
| return createSubset(findSubsetIndex(fromElement), toIndex); |
| } |
| |
| private int findSubsetIndex(E element) { |
| int index = binarySearch(element); |
| return (index >= 0) ? index : (-index - 1); |
| } |
| |
| private ImmutableSortedSet<E> createSubset( |
| int newFromIndex, int newToIndex) { |
| if (newFromIndex < newToIndex) { |
| return new RegularImmutableSortedSet<E>(elements, comparator, |
| newFromIndex, newToIndex); |
| } else { |
| return emptySet(comparator); |
| } |
| } |
| |
| @Override boolean hasPartialArray() { |
| return (fromIndex != 0) || (toIndex != elements.length); |
| } |
| |
| @Override int indexOf(Object target) { |
| if (target == null) { |
| return -1; |
| } |
| int position; |
| try { |
| position = binarySearch(target); |
| } catch (ClassCastException e) { |
| return -1; |
| } |
| // The equals() check is needed when the comparator isn't compatible with |
| // equals(). |
| return (position >= 0 && elements[position].equals(target)) |
| ? position - fromIndex : -1; |
| } |
| |
| @Override ImmutableList<E> createAsList() { |
| return new ImmutableSortedAsList<E>(elements, fromIndex, size(), this); |
| } |
| } |