/*
* Copyright (C) 2011 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.
BoundType.
CLOSED;
import static com.google.common.collect.
BoundType.
OPEN;
import com.google.common.annotations.
GwtCompatible;
import com.google.common.base.
Objects;
import java.io.
Serializable;
import java.util.
Comparator;
import javax.annotation.
Nullable;
/**
* A generalized interval on any ordering, for internal use. Supports {@code null}. Unlike
* {@link Range}, this allows the use of an arbitrary comparator. This is designed for use in the
* implementation of subcollections of sorted collection types.
*
* <p>Whenever possible, use {@code Range} instead, which is better supported.
*
* @author Louis Wasserman
*/
@
GwtCompatible(serializable = true)
final class
GeneralRange<T> implements
Serializable {
/**
* Converts a Range to a GeneralRange.
*/
static <T extends
Comparable>
GeneralRange<T>
from(
Range<T>
range) {
@
Nullable
T
lowerEndpoint =
range.
hasLowerBound() ?
range.
lowerEndpoint() : null;
BoundType lowerBoundType =
range.
hasLowerBound() ?
range.
lowerBoundType() :
OPEN;
@
Nullable
T
upperEndpoint =
range.
hasUpperBound() ?
range.
upperEndpoint() : null;
BoundType upperBoundType =
range.
hasUpperBound() ?
range.
upperBoundType() :
OPEN;
return new
GeneralRange<T>(
Ordering.
natural(),
range.
hasLowerBound(),
lowerEndpoint,
lowerBoundType,
range.
hasUpperBound(),
upperEndpoint,
upperBoundType);
}
/**
* Returns the whole range relative to the specified comparator.
*/
static <T>
GeneralRange<T>
all(
Comparator<? super T>
comparator) {
return new
GeneralRange<T>(
comparator, false, null,
OPEN, false, null,
OPEN);
}
/**
* Returns everything above the endpoint relative to the specified comparator, with the specified
* endpoint behavior.
*/
static <T>
GeneralRange<T>
downTo(
Comparator<? super T>
comparator, @
Nullable T
endpoint,
BoundType boundType) {
return new
GeneralRange<T>(
comparator, true,
endpoint,
boundType, false, null,
OPEN);
}
/**
* Returns everything below the endpoint relative to the specified comparator, with the specified
* endpoint behavior.
*/
static <T>
GeneralRange<T>
upTo(
Comparator<? super T>
comparator, @
Nullable T
endpoint,
BoundType boundType) {
return new
GeneralRange<T>(
comparator, false, null,
OPEN, true,
endpoint,
boundType);
}
/**
* Returns everything between the endpoints relative to the specified comparator, with the
* specified endpoint behavior.
*/
static <T>
GeneralRange<T>
range(
Comparator<? super T>
comparator, @
Nullable T
lower,
BoundType lowerType, @
Nullable T
upper,
BoundType upperType) {
return new
GeneralRange<T>(
comparator, true,
lower,
lowerType, true,
upper,
upperType);
}
private final
Comparator<? super T>
comparator;
private final boolean
hasLowerBound;
@
Nullable
private final T
lowerEndpoint;
private final
BoundType lowerBoundType;
private final boolean
hasUpperBound;
@
Nullable
private final T
upperEndpoint;
private final
BoundType upperBoundType;
private
GeneralRange(
Comparator<? super T>
comparator, boolean
hasLowerBound,
@
Nullable T
lowerEndpoint,
BoundType lowerBoundType, boolean
hasUpperBound,
@
Nullable T
upperEndpoint,
BoundType upperBoundType) {
this.
comparator =
checkNotNull(
comparator);
this.
hasLowerBound =
hasLowerBound;
this.
hasUpperBound =
hasUpperBound;
this.
lowerEndpoint =
lowerEndpoint;
this.
lowerBoundType =
checkNotNull(
lowerBoundType);
this.
upperEndpoint =
upperEndpoint;
this.
upperBoundType =
checkNotNull(
upperBoundType);
if (
hasLowerBound) {
comparator.
compare(
lowerEndpoint,
lowerEndpoint);
}
if (
hasUpperBound) {
comparator.
compare(
upperEndpoint,
upperEndpoint);
}
if (
hasLowerBound &&
hasUpperBound) {
int
cmp =
comparator.
compare(
lowerEndpoint,
upperEndpoint);
// be consistent with Range
checkArgument(
cmp <= 0, "lowerEndpoint (%s) > upperEndpoint (%s)",
lowerEndpoint,
upperEndpoint);
if (
cmp == 0) {
checkArgument(
lowerBoundType !=
OPEN |
upperBoundType !=
OPEN);
}
}
}
Comparator<? super T>
comparator() {
return
comparator;
}
boolean
hasLowerBound() {
return
hasLowerBound;
}
boolean
hasUpperBound() {
return
hasUpperBound;
}
boolean
isEmpty() {
return (
hasUpperBound() &&
tooLow(
getUpperEndpoint()))
|| (
hasLowerBound() &&
tooHigh(
getLowerEndpoint()));
}
boolean
tooLow(@
Nullable T
t) {
if (!
hasLowerBound()) {
return false;
}
T
lbound =
getLowerEndpoint();
int
cmp =
comparator.
compare(
t,
lbound);
return
cmp < 0 | (
cmp == 0 &
getLowerBoundType() ==
OPEN);
}
boolean
tooHigh(@
Nullable T
t) {
if (!
hasUpperBound()) {
return false;
}
T
ubound =
getUpperEndpoint();
int
cmp =
comparator.
compare(
t,
ubound);
return
cmp > 0 | (
cmp == 0 &
getUpperBoundType() ==
OPEN);
}
boolean
contains(@
Nullable T
t) {
return !
tooLow(
t) && !
tooHigh(
t);
}
/**
* Returns the intersection of the two ranges, or an empty range if their intersection is empty.
*/
GeneralRange<T>
intersect(
GeneralRange<T>
other) {
checkNotNull(
other);
checkArgument(
comparator.
equals(
other.
comparator));
boolean
hasLowBound = this.
hasLowerBound;
@
Nullable
T
lowEnd =
getLowerEndpoint();
BoundType lowType =
getLowerBoundType();
if (!
hasLowerBound()) {
hasLowBound =
other.
hasLowerBound;
lowEnd =
other.
getLowerEndpoint();
lowType =
other.
getLowerBoundType();
} else if (
other.
hasLowerBound()) {
int
cmp =
comparator.
compare(
getLowerEndpoint(),
other.
getLowerEndpoint());
if (
cmp < 0 || (
cmp == 0 &&
other.
getLowerBoundType() ==
OPEN)) {
lowEnd =
other.
getLowerEndpoint();
lowType =
other.
getLowerBoundType();
}
}
boolean
hasUpBound = this.
hasUpperBound;
@
Nullable
T
upEnd =
getUpperEndpoint();
BoundType upType =
getUpperBoundType();
if (!
hasUpperBound()) {
hasUpBound =
other.
hasUpperBound;
upEnd =
other.
getUpperEndpoint();
upType =
other.
getUpperBoundType();
} else if (
other.
hasUpperBound()) {
int
cmp =
comparator.
compare(
getUpperEndpoint(),
other.
getUpperEndpoint());
if (
cmp > 0 || (
cmp == 0 &&
other.
getUpperBoundType() ==
OPEN)) {
upEnd =
other.
getUpperEndpoint();
upType =
other.
getUpperBoundType();
}
}
if (
hasLowBound &&
hasUpBound) {
int
cmp =
comparator.
compare(
lowEnd,
upEnd);
if (
cmp > 0 || (
cmp == 0 &&
lowType ==
OPEN &&
upType ==
OPEN)) {
// force allowed empty range
lowEnd =
upEnd;
lowType =
OPEN;
upType =
CLOSED;
}
}
return new
GeneralRange<T>(
comparator,
hasLowBound,
lowEnd,
lowType,
hasUpBound,
upEnd,
upType);
}
@
Override
public boolean
equals(@
Nullable Object obj) {
if (
obj instanceof
GeneralRange) {
GeneralRange<?>
r = (
GeneralRange<?>)
obj;
return
comparator.
equals(
r.
comparator) &&
hasLowerBound ==
r.
hasLowerBound
&&
hasUpperBound ==
r.
hasUpperBound &&
getLowerBoundType().
equals(
r.
getLowerBoundType())
&&
getUpperBoundType().
equals(
r.
getUpperBoundType())
&&
Objects.
equal(
getLowerEndpoint(),
r.
getLowerEndpoint())
&&
Objects.
equal(
getUpperEndpoint(),
r.
getUpperEndpoint());
}
return false;
}
@
Override
public int
hashCode() {
return
Objects.
hashCode(
comparator,
getLowerEndpoint(),
getLowerBoundType(),
getUpperEndpoint(),
getUpperBoundType());
}
private transient
GeneralRange<T>
reverse;
/**
* Returns the same range relative to the reversed comparator.
*/
GeneralRange<T>
reverse() {
GeneralRange<T>
result =
reverse;
if (
result == null) {
result = new
GeneralRange<T>(
Ordering.
from(
comparator).
reverse(),
hasUpperBound,
getUpperEndpoint(),
getUpperBoundType(),
hasLowerBound,
getLowerEndpoint(),
getLowerBoundType());
result.
reverse = this;
return this.
reverse =
result;
}
return
result;
}
@
Override
public
String toString() {
return new
StringBuilder()
.
append(
comparator)
.
append(":")
.
append(
lowerBoundType ==
CLOSED ? '[' : '(')
.
append(
hasLowerBound ?
lowerEndpoint : "-\u221e")
.
append(',')
.
append(
hasUpperBound ?
upperEndpoint : "\u221e")
.
append(
upperBoundType ==
CLOSED ? ']' : ')')
.
toString();
}
T
getLowerEndpoint() {
return
lowerEndpoint;
}
BoundType getLowerBoundType() {
return
lowerBoundType;
}
T
getUpperEndpoint() {
return
upperEndpoint;
}
BoundType getUpperBoundType() {
return
upperBoundType;
}
}