/*
* Copyright (C) 2009 The Guava Authors
*
* 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 static com.google.common.base.
Preconditions.checkArgument;
import static com.google.common.base.
Preconditions.checkNotNull;
import static com.google.common.collect.
SortedLists.
KeyAbsentBehavior.
INVERTED_INSERTION_INDEX;
import static com.google.common.collect.
SortedLists.
KeyAbsentBehavior.
NEXT_HIGHER;
import static com.google.common.collect.
SortedLists.
KeyPresentBehavior.
ANY_PRESENT;
import static com.google.common.collect.
SortedLists.
KeyPresentBehavior.
FIRST_AFTER;
import static com.google.common.collect.
SortedLists.
KeyPresentBehavior.
FIRST_PRESENT;
import com.google.common.annotations.
GwtCompatible;
import com.google.common.annotations.
GwtIncompatible;
import java.util.
Collection;
import java.util.
Collections;
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(jlevy): Consider
* separate class for a single-element sorted set.
*
* @author Jared Levy
* @author Louis Wasserman
*/
@
GwtCompatible(serializable = true, emulated = true)
@
SuppressWarnings("serial")
final class
RegularImmutableSortedSet<E> extends
ImmutableSortedSet<E> {
private transient final
ImmutableList<E>
elements;
RegularImmutableSortedSet(
ImmutableList<E>
elements,
Comparator<? super E>
comparator) {
super(
comparator);
this.
elements =
elements;
checkArgument(!
elements.
isEmpty());
}
@
Override public
UnmodifiableIterator<E>
iterator() {
return
elements.
iterator();
}
@
GwtIncompatible("NavigableSet")
@
Override public
UnmodifiableIterator<E>
descendingIterator() {
return
elements.
reverse().
iterator();
}
@
Override public boolean
isEmpty() {
return false;
}
@
Override
public int
size() {
return
elements.
size();
}
@
Override public boolean
contains(
Object o) {
try {
return
o != null &&
unsafeBinarySearch(
o) >= 0;
} catch (
ClassCastException e) {
return false;
}
}
@
Override public boolean
containsAll(
Collection<?>
targets) {
// TODO(jlevy): For optimal performance, use a binary search when
// targets.size() < size() / log(size())
// TODO(kevinb): see if we can share code with OrderedIterator after it
// graduates from labs.
if (
targets instanceof
Multiset) {
targets = ((
Multiset<?>)
targets).
elementSet();
}
if (!
SortedIterables.
hasSameComparator(
comparator(),
targets)
|| (
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.
*/
PeekingIterator<E>
thisIterator =
Iterators.
peekingIterator(
iterator());
Iterator<?>
thatIterator =
targets.
iterator();
Object target =
thatIterator.
next();
try {
while (
thisIterator.
hasNext()) {
int
cmp =
unsafeCompare(
thisIterator.
peek(),
target);
if (
cmp < 0) {
thisIterator.
next();
} else if (
cmp == 0) {
if (!
thatIterator.
hasNext()) {
return true;
}
target =
thatIterator.
next();
} else if (
cmp > 0) {
return false;
}
}
} catch (
NullPointerException e) {
return false;
} catch (
ClassCastException e) {
return false;
}
return false;
}
private int
unsafeBinarySearch(
Object key) throws
ClassCastException {
return
Collections.
binarySearch(
elements,
key,
unsafeComparator());
}
@
Override boolean
isPartialView() {
return
elements.
isPartialView();
}
@
Override
int
copyIntoArray(
Object[]
dst, int
offset) {
return
elements.
copyIntoArray(
dst,
offset);
}
@
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 (
SortedIterables.
hasSameComparator(
comparator,
that)) {
Iterator<?>
otherIterator =
that.
iterator();
try {
Iterator<E>
iterator =
iterator();
while (
iterator.
hasNext()) {
Object element =
iterator.
next();
Object otherElement =
otherIterator.
next();
if (
otherElement == null
||
unsafeCompare(
element,
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 E
first() {
return
elements.
get(0);
}
@
Override
public E
last() {
return
elements.
get(
size() - 1);
}
@
Override
public E
lower(E
element) {
int
index =
headIndex(
element, false) - 1;
return (
index == -1) ? null :
elements.
get(
index);
}
@
Override
public E
floor(E
element) {
int
index =
headIndex(
element, true) - 1;
return (
index == -1) ? null :
elements.
get(
index);
}
@
Override
public E
ceiling(E
element) {
int
index =
tailIndex(
element, true);
return (
index ==
size()) ? null :
elements.
get(
index);
}
@
Override
public E
higher(E
element) {
int
index =
tailIndex(
element, false);
return (
index ==
size()) ? null :
elements.
get(
index);
}
@
Override
ImmutableSortedSet<E>
headSetImpl(E
toElement, boolean
inclusive) {
return
getSubSet(0,
headIndex(
toElement,
inclusive));
}
int
headIndex(E
toElement, boolean
inclusive) {
return
SortedLists.
binarySearch(
elements,
checkNotNull(
toElement),
comparator(),
inclusive ?
FIRST_AFTER :
FIRST_PRESENT,
NEXT_HIGHER);
}
@
Override
ImmutableSortedSet<E>
subSetImpl(
E
fromElement, boolean
fromInclusive, E
toElement, boolean
toInclusive) {
return
tailSetImpl(
fromElement,
fromInclusive)
.
headSetImpl(
toElement,
toInclusive);
}
@
Override
ImmutableSortedSet<E>
tailSetImpl(E
fromElement, boolean
inclusive) {
return
getSubSet(
tailIndex(
fromElement,
inclusive),
size());
}
int
tailIndex(E
fromElement, boolean
inclusive) {
return
SortedLists.
binarySearch(
elements,
checkNotNull(
fromElement),
comparator(),
inclusive ?
FIRST_PRESENT :
FIRST_AFTER,
NEXT_HIGHER);
}
// Pretend the comparator can compare anything. If it turns out it can't
// compare two elements, it'll throw a CCE. Only methods that are specified to
// throw CCE should call this.
@
SuppressWarnings("unchecked")
Comparator<
Object>
unsafeComparator() {
return (
Comparator<
Object>)
comparator;
}
ImmutableSortedSet<E>
getSubSet(int
newFromIndex, int
newToIndex) {
if (
newFromIndex == 0 &&
newToIndex ==
size()) {
return this;
} else if (
newFromIndex <
newToIndex) {
return new
RegularImmutableSortedSet<E>(
elements.
subList(
newFromIndex,
newToIndex),
comparator);
} else {
return
emptySet(
comparator);
}
}
@
Override int
indexOf(@
Nullable Object target) {
if (
target == null) {
return -1;
}
int
position;
try {
position =
SortedLists.
binarySearch(
elements,
target,
unsafeComparator(),
ANY_PRESENT,
INVERTED_INSERTION_INDEX);
} catch (
ClassCastException e) {
return -1;
}
return (
position >= 0) ?
position : -1;
}
@
Override ImmutableList<E>
createAsList() {
return new
ImmutableSortedAsList<E>(this,
elements);
}
@
Override
ImmutableSortedSet<E>
createDescendingSet() {
return new
RegularImmutableSortedSet<E>(
elements.
reverse(),
Ordering.
from(
comparator).
reverse());
}
}