|
Java example source code file (TreeRangeSet.java)
This example Java source code file (TreeRangeSet.java) is included in the alvinalexander.com
"Java Source Code
Warehouse" project. The intent of this project is to help you "Learn
Java by Example" TM.
Learn more about this Java project at its project page.
The TreeRangeSet.java Java example source code
/*
* 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 com.google.common.annotations.Beta;
import com.google.common.annotations.GwtIncompatible;
import com.google.common.annotations.VisibleForTesting;
import com.google.common.base.MoreObjects;
import java.io.Serializable;
import java.util.Collection;
import java.util.Comparator;
import java.util.Iterator;
import java.util.Map.Entry;
import java.util.NavigableMap;
import java.util.NoSuchElementException;
import java.util.Set;
import java.util.TreeMap;
import javax.annotation.Nullable;
/**
* An implementation of {@link RangeSet} backed by a {@link TreeMap}.
*
* @author Louis Wasserman
* @since 14.0
*/
@Beta
@GwtIncompatible // uses NavigableMap
public class TreeRangeSet<C extends Comparable extends AbstractRangeSet
implements Serializable {
@VisibleForTesting final NavigableMap<Cut> rangesByLowerBound;
/**
* Creates an empty {@code TreeRangeSet} instance.
*/
public static <C extends Comparable TreeRangeSet create() {
return new TreeRangeSet<C>(new TreeMap, Range>());
}
/**
* Returns a {@code TreeRangeSet} initialized with the ranges in the specified range set.
*/
public static <C extends Comparable TreeRangeSet create(RangeSet rangeSet) {
TreeRangeSet<C> result = create();
result.addAll(rangeSet);
return result;
}
private TreeRangeSet(NavigableMap<Cut> rangesByLowerCut) {
this.rangesByLowerBound = rangesByLowerCut;
}
private transient Set<Range asRanges;
private transient Set<Range asDescendingSetOfRanges;
@Override
public Set<Range asRanges() {
Set<Range result = asRanges;
return (result == null) ? asRanges = new AsRanges(rangesByLowerBound.values()) : result;
}
@Override
public Set<Range asDescendingSetOfRanges() {
Set<Range result = asDescendingSetOfRanges;
return (result == null)
? asDescendingSetOfRanges = new AsRanges(rangesByLowerBound.descendingMap().values())
: result;
}
final class AsRanges extends ForwardingCollection<Range implements Set> {
final Collection<Range delegate;
AsRanges(Collection<Range delegate) {
this.delegate = delegate;
}
@Override
protected Collection<Range delegate() {
return delegate;
}
@Override
public int hashCode() {
return Sets.hashCodeImpl(this);
}
@Override
public boolean equals(@Nullable Object o) {
return Sets.equalsImpl(this, o);
}
}
@Override
@Nullable
public Range<C> rangeContaining(C value) {
checkNotNull(value);
Entry<Cut> floorEntry = rangesByLowerBound.floorEntry(Cut.belowValue(value));
if (floorEntry != null && floorEntry.getValue().contains(value)) {
return floorEntry.getValue();
} else {
// TODO(kevinb): revisit this design choice
return null;
}
}
@Override
public boolean intersects(Range<C> range) {
checkNotNull(range);
Entry<Cut> ceilingEntry = rangesByLowerBound.ceilingEntry(range.lowerBound);
if (ceilingEntry != null
&& ceilingEntry.getValue().isConnected(range)
&& !ceilingEntry.getValue().intersection(range).isEmpty()) {
return true;
}
Entry<Cut> priorEntry = rangesByLowerBound.lowerEntry(range.lowerBound);
return priorEntry != null
&& priorEntry.getValue().isConnected(range)
&& !priorEntry.getValue().intersection(range).isEmpty();
}
@Override
public boolean encloses(Range<C> range) {
checkNotNull(range);
Entry<Cut> floorEntry = rangesByLowerBound.floorEntry(range.lowerBound);
return floorEntry != null && floorEntry.getValue().encloses(range);
}
@Nullable
private Range<C> rangeEnclosing(Range range) {
checkNotNull(range);
Entry<Cut> floorEntry = rangesByLowerBound.floorEntry(range.lowerBound);
return (floorEntry != null && floorEntry.getValue().encloses(range))
? floorEntry.getValue()
: null;
}
@Override
public Range<C> span() {
Entry<Cut> firstEntry = rangesByLowerBound.firstEntry();
Entry<Cut> lastEntry = rangesByLowerBound.lastEntry();
if (firstEntry == null) {
throw new NoSuchElementException();
}
return Range.create(firstEntry.getValue().lowerBound, lastEntry.getValue().upperBound);
}
@Override
public void add(Range<C> rangeToAdd) {
checkNotNull(rangeToAdd);
if (rangeToAdd.isEmpty()) {
return;
}
// We will use { } to illustrate ranges currently in the range set, and < >
// to illustrate rangeToAdd.
Cut<C> lbToAdd = rangeToAdd.lowerBound;
Cut<C> ubToAdd = rangeToAdd.upperBound;
Entry<Cut> entryBelowLB = rangesByLowerBound.lowerEntry(lbToAdd);
if (entryBelowLB != null) {
// { <
Range<C> rangeBelowLB = entryBelowLB.getValue();
if (rangeBelowLB.upperBound.compareTo(lbToAdd) >= 0) {
// { < }, and we will need to coalesce
if (rangeBelowLB.upperBound.compareTo(ubToAdd) >= 0) {
// { < > }
ubToAdd = rangeBelowLB.upperBound;
/*
* TODO(cpovirk): can we just "return;" here? Or, can we remove this if() entirely? If
* not, add tests to demonstrate the problem with each approach
*/
}
lbToAdd = rangeBelowLB.lowerBound;
}
}
Entry<Cut> entryBelowUB = rangesByLowerBound.floorEntry(ubToAdd);
if (entryBelowUB != null) {
// { >
Range<C> rangeBelowUB = entryBelowUB.getValue();
if (rangeBelowUB.upperBound.compareTo(ubToAdd) >= 0) {
// { > }, and we need to coalesce
ubToAdd = rangeBelowUB.upperBound;
}
}
// Remove ranges which are strictly enclosed.
rangesByLowerBound.subMap(lbToAdd, ubToAdd).clear();
replaceRangeWithSameLowerBound(Range.create(lbToAdd, ubToAdd));
}
@Override
public void remove(Range<C> rangeToRemove) {
checkNotNull(rangeToRemove);
if (rangeToRemove.isEmpty()) {
return;
}
// We will use { } to illustrate ranges currently in the range set, and < >
// to illustrate rangeToRemove.
Entry<Cut> entryBelowLB = rangesByLowerBound.lowerEntry(rangeToRemove.lowerBound);
if (entryBelowLB != null) {
// { <
Range<C> rangeBelowLB = entryBelowLB.getValue();
if (rangeBelowLB.upperBound.compareTo(rangeToRemove.lowerBound) >= 0) {
// { < }, and we will need to subdivide
if (rangeToRemove.hasUpperBound()
&& rangeBelowLB.upperBound.compareTo(rangeToRemove.upperBound) >= 0) {
// { < > }
replaceRangeWithSameLowerBound(
Range.create(rangeToRemove.upperBound, rangeBelowLB.upperBound));
}
replaceRangeWithSameLowerBound(
Range.create(rangeBelowLB.lowerBound, rangeToRemove.lowerBound));
}
}
Entry<Cut> entryBelowUB = rangesByLowerBound.floorEntry(rangeToRemove.upperBound);
if (entryBelowUB != null) {
// { >
Range<C> rangeBelowUB = entryBelowUB.getValue();
if (rangeToRemove.hasUpperBound()
&& rangeBelowUB.upperBound.compareTo(rangeToRemove.upperBound) >= 0) {
// { > }
replaceRangeWithSameLowerBound(
Range.create(rangeToRemove.upperBound, rangeBelowUB.upperBound));
}
}
rangesByLowerBound.subMap(rangeToRemove.lowerBound, rangeToRemove.upperBound).clear();
}
private void replaceRangeWithSameLowerBound(Range<C> range) {
if (range.isEmpty()) {
rangesByLowerBound.remove(range.lowerBound);
} else {
rangesByLowerBound.put(range.lowerBound, range);
}
}
private transient RangeSet<C> complement;
@Override
public RangeSet<C> complement() {
RangeSet<C> result = complement;
return (result == null) ? complement = new Complement() : result;
}
@VisibleForTesting
static final class RangesByUpperBound<C extends Comparable
extends AbstractNavigableMap<Cut> {
private final NavigableMap<Cut> rangesByLowerBound;
/**
* upperBoundWindow represents the headMap/subMap/tailMap view of the entire "ranges by upper
* bound" map; it's a constraint on the *keys*, and does not affect the values.
*/
private final Range<Cut upperBoundWindow;
RangesByUpperBound(NavigableMap<Cut> rangesByLowerBound) {
this.rangesByLowerBound = rangesByLowerBound;
this.upperBoundWindow = Range.all();
}
private RangesByUpperBound(
NavigableMap<Cut> rangesByLowerBound, Range> upperBoundWindow) {
this.rangesByLowerBound = rangesByLowerBound;
this.upperBoundWindow = upperBoundWindow;
}
private NavigableMap<Cut> subMap(Range> window) {
if (window.isConnected(upperBoundWindow)) {
return new RangesByUpperBound<C>(rangesByLowerBound, window.intersection(upperBoundWindow));
} else {
return ImmutableSortedMap.of();
}
}
@Override
public NavigableMap<Cut> subMap(
Cut<C> fromKey, boolean fromInclusive, Cut toKey, boolean toInclusive) {
return subMap(
Range.range(
fromKey, BoundType.forBoolean(fromInclusive),
toKey, BoundType.forBoolean(toInclusive)));
}
@Override
public NavigableMap<Cut> headMap(Cut toKey, boolean inclusive) {
return subMap(Range.upTo(toKey, BoundType.forBoolean(inclusive)));
}
@Override
public NavigableMap<Cut> tailMap(Cut fromKey, boolean inclusive) {
return subMap(Range.downTo(fromKey, BoundType.forBoolean(inclusive)));
}
@Override
public Comparator<? super Cut comparator() {
return Ordering.<Cutnatural();
}
@Override
public boolean containsKey(@Nullable Object key) {
return get(key) != null;
}
@Override
public Range<C> get(@Nullable Object key) {
if (key instanceof Cut) {
try {
@SuppressWarnings("unchecked") // we catch CCEs
Cut<C> cut = (Cut) key;
if (!upperBoundWindow.contains(cut)) {
return null;
}
Entry<Cut> candidate = rangesByLowerBound.lowerEntry(cut);
if (candidate != null && candidate.getValue().upperBound.equals(cut)) {
return candidate.getValue();
}
} catch (ClassCastException e) {
return null;
}
}
return null;
}
@Override
Iterator<Entry>> entryIterator() {
/*
* We want to start the iteration at the first range where the upper bound is in
* upperBoundWindow.
*/
final Iterator<Range backingItr;
if (!upperBoundWindow.hasLowerBound()) {
backingItr = rangesByLowerBound.values().iterator();
} else {
Entry<Cut> lowerEntry =
rangesByLowerBound.lowerEntry(upperBoundWindow.lowerEndpoint());
if (lowerEntry == null) {
backingItr = rangesByLowerBound.values().iterator();
} else if (upperBoundWindow.lowerBound.isLessThan(lowerEntry.getValue().upperBound)) {
backingItr = rangesByLowerBound.tailMap(lowerEntry.getKey(), true).values().iterator();
} else {
backingItr =
rangesByLowerBound
.tailMap(upperBoundWindow.lowerEndpoint(), true)
.values()
.iterator();
}
}
return new AbstractIterator<Entry>>() {
@Override
protected Entry<Cut> computeNext() {
if (!backingItr.hasNext()) {
return endOfData();
}
Range<C> range = backingItr.next();
if (upperBoundWindow.upperBound.isLessThan(range.upperBound)) {
return endOfData();
} else {
return Maps.immutableEntry(range.upperBound, range);
}
}
};
}
@Override
Iterator<Entry>> descendingEntryIterator() {
Collection<Range candidates;
if (upperBoundWindow.hasUpperBound()) {
candidates =
rangesByLowerBound
.headMap(upperBoundWindow.upperEndpoint(), false)
.descendingMap()
.values();
} else {
candidates = rangesByLowerBound.descendingMap().values();
}
final PeekingIterator<Range backingItr = Iterators.peekingIterator(candidates.iterator());
if (backingItr.hasNext()
&& upperBoundWindow.upperBound.isLessThan(backingItr.peek().upperBound)) {
backingItr.next();
}
return new AbstractIterator<Entry>>() {
@Override
protected Entry<Cut> computeNext() {
if (!backingItr.hasNext()) {
return endOfData();
}
Range<C> range = backingItr.next();
return upperBoundWindow.lowerBound.isLessThan(range.upperBound)
? Maps.immutableEntry(range.upperBound, range)
: endOfData();
}
};
}
@Override
public int size() {
if (upperBoundWindow.equals(Range.all())) {
return rangesByLowerBound.size();
}
return Iterators.size(entryIterator());
}
@Override
public boolean isEmpty() {
return upperBoundWindow.equals(Range.all())
? rangesByLowerBound.isEmpty()
: !entryIterator().hasNext();
}
}
private static final class ComplementRangesByLowerBound<C extends Comparable
extends AbstractNavigableMap<Cut> {
private final NavigableMap<Cut> positiveRangesByLowerBound;
private final NavigableMap<Cut> positiveRangesByUpperBound;
/**
* complementLowerBoundWindow represents the headMap/subMap/tailMap view of the entire
* "complement ranges by lower bound" map; it's a constraint on the *keys*, and does not affect
* the values.
*/
private final Range<Cut complementLowerBoundWindow;
ComplementRangesByLowerBound(NavigableMap<Cut> positiveRangesByLowerBound) {
this(positiveRangesByLowerBound, Range.<Cutall());
}
private ComplementRangesByLowerBound(
NavigableMap<Cut> positiveRangesByLowerBound, Range> window) {
this.positiveRangesByLowerBound = positiveRangesByLowerBound;
this.positiveRangesByUpperBound = new RangesByUpperBound<C>(positiveRangesByLowerBound);
this.complementLowerBoundWindow = window;
}
private NavigableMap<Cut> subMap(Range> subWindow) {
if (!complementLowerBoundWindow.isConnected(subWindow)) {
return ImmutableSortedMap.of();
} else {
subWindow = subWindow.intersection(complementLowerBoundWindow);
return new ComplementRangesByLowerBound<C>(positiveRangesByLowerBound, subWindow);
}
}
@Override
public NavigableMap<Cut> subMap(
Cut<C> fromKey, boolean fromInclusive, Cut toKey, boolean toInclusive) {
return subMap(
Range.range(
fromKey, BoundType.forBoolean(fromInclusive),
toKey, BoundType.forBoolean(toInclusive)));
}
@Override
public NavigableMap<Cut> headMap(Cut toKey, boolean inclusive) {
return subMap(Range.upTo(toKey, BoundType.forBoolean(inclusive)));
}
@Override
public NavigableMap<Cut> tailMap(Cut fromKey, boolean inclusive) {
return subMap(Range.downTo(fromKey, BoundType.forBoolean(inclusive)));
}
@Override
public Comparator<? super Cut comparator() {
return Ordering.<Cutnatural();
}
@Override
Iterator<Entry>> entryIterator() {
/*
* firstComplementRangeLowerBound is the first complement range lower bound inside
* complementLowerBoundWindow. Complement range lower bounds are either positive range upper
* bounds, or Cut.belowAll().
*
* positiveItr starts at the first positive range with lower bound greater than
* firstComplementRangeLowerBound. (Positive range lower bounds correspond to complement range
* upper bounds.)
*/
Collection<Range positiveRanges;
if (complementLowerBoundWindow.hasLowerBound()) {
positiveRanges =
positiveRangesByUpperBound
.tailMap(
complementLowerBoundWindow.lowerEndpoint(),
complementLowerBoundWindow.lowerBoundType() == BoundType.CLOSED)
.values();
} else {
positiveRanges = positiveRangesByUpperBound.values();
}
final PeekingIterator<Range positiveItr =
Iterators.peekingIterator(positiveRanges.iterator());
final Cut<C> firstComplementRangeLowerBound;
if (complementLowerBoundWindow.contains(Cut.<C>belowAll())
&& (!positiveItr.hasNext() || positiveItr.peek().lowerBound != Cut.<C>belowAll())) {
firstComplementRangeLowerBound = Cut.belowAll();
} else if (positiveItr.hasNext()) {
firstComplementRangeLowerBound = positiveItr.next().upperBound;
} else {
return Iterators.emptyIterator();
}
return new AbstractIterator<Entry>>() {
Cut<C> nextComplementRangeLowerBound = firstComplementRangeLowerBound;
@Override
protected Entry<Cut> computeNext() {
if (complementLowerBoundWindow.upperBound.isLessThan(nextComplementRangeLowerBound)
|| nextComplementRangeLowerBound == Cut.<C>aboveAll()) {
return endOfData();
}
Range<C> negativeRange;
if (positiveItr.hasNext()) {
Range<C> positiveRange = positiveItr.next();
negativeRange = Range.create(nextComplementRangeLowerBound, positiveRange.lowerBound);
nextComplementRangeLowerBound = positiveRange.upperBound;
} else {
negativeRange = Range.create(nextComplementRangeLowerBound, Cut.<C>aboveAll());
nextComplementRangeLowerBound = Cut.aboveAll();
}
return Maps.immutableEntry(negativeRange.lowerBound, negativeRange);
}
};
}
@Override
Iterator<Entry>> descendingEntryIterator() {
/*
* firstComplementRangeUpperBound is the upper bound of the last complement range with lower
* bound inside complementLowerBoundWindow.
*
* positiveItr starts at the first positive range with upper bound less than
* firstComplementRangeUpperBound. (Positive range upper bounds correspond to complement range
* lower bounds.)
*/
Cut<C> startingPoint =
complementLowerBoundWindow.hasUpperBound()
? complementLowerBoundWindow.upperEndpoint()
: Cut.<C>aboveAll();
boolean inclusive =
complementLowerBoundWindow.hasUpperBound()
&& complementLowerBoundWindow.upperBoundType() == BoundType.CLOSED;
final PeekingIterator<Range positiveItr =
Iterators.peekingIterator(
positiveRangesByUpperBound
.headMap(startingPoint, inclusive)
.descendingMap()
.values()
.iterator());
Cut<C> cut;
if (positiveItr.hasNext()) {
cut =
(positiveItr.peek().upperBound == Cut.<C>aboveAll())
? positiveItr.next().lowerBound
: positiveRangesByLowerBound.higherKey(positiveItr.peek().upperBound);
} else if (!complementLowerBoundWindow.contains(Cut.<C>belowAll())
|| positiveRangesByLowerBound.containsKey(Cut.belowAll())) {
return Iterators.emptyIterator();
} else {
cut = positiveRangesByLowerBound.higherKey(Cut.<C>belowAll());
}
final Cut<C> firstComplementRangeUpperBound =
MoreObjects.firstNonNull(cut, Cut.<C>aboveAll());
return new AbstractIterator<Entry>>() {
Cut<C> nextComplementRangeUpperBound = firstComplementRangeUpperBound;
@Override
protected Entry<Cut> computeNext() {
if (nextComplementRangeUpperBound == Cut.<C>belowAll()) {
return endOfData();
} else if (positiveItr.hasNext()) {
Range<C> positiveRange = positiveItr.next();
Range<C> negativeRange =
Range.create(positiveRange.upperBound, nextComplementRangeUpperBound);
nextComplementRangeUpperBound = positiveRange.lowerBound;
if (complementLowerBoundWindow.lowerBound.isLessThan(negativeRange.lowerBound)) {
return Maps.immutableEntry(negativeRange.lowerBound, negativeRange);
}
} else if (complementLowerBoundWindow.lowerBound.isLessThan(Cut.<C>belowAll())) {
Range<C> negativeRange = Range.create(Cut.belowAll(), nextComplementRangeUpperBound);
nextComplementRangeUpperBound = Cut.belowAll();
return Maps.immutableEntry(Cut.<C>belowAll(), negativeRange);
}
return endOfData();
}
};
}
@Override
public int size() {
return Iterators.size(entryIterator());
}
@Override
@Nullable
public Range<C> get(Object key) {
if (key instanceof Cut) {
try {
@SuppressWarnings("unchecked")
Cut<C> cut = (Cut) key;
// tailMap respects the current window
Entry<Cut> firstEntry = tailMap(cut, true).firstEntry();
if (firstEntry != null && firstEntry.getKey().equals(cut)) {
return firstEntry.getValue();
}
} catch (ClassCastException e) {
return null;
}
}
return null;
}
@Override
public boolean containsKey(Object key) {
return get(key) != null;
}
}
private final class Complement extends TreeRangeSet<C> {
Complement() {
super(new ComplementRangesByLowerBound<C>(TreeRangeSet.this.rangesByLowerBound));
}
@Override
public void add(Range<C> rangeToAdd) {
TreeRangeSet.this.remove(rangeToAdd);
}
@Override
public void remove(Range<C> rangeToRemove) {
TreeRangeSet.this.add(rangeToRemove);
}
@Override
public boolean contains(C value) {
return !TreeRangeSet.this.contains(value);
}
@Override
public RangeSet<C> complement() {
return TreeRangeSet.this;
}
}
private static final class SubRangeSetRangesByLowerBound<C extends Comparable
extends AbstractNavigableMap<Cut> {
/**
* lowerBoundWindow is the headMap/subMap/tailMap view; it only restricts the keys, and does not
* affect the values.
*/
private final Range<Cut lowerBoundWindow;
/**
* restriction is the subRangeSet view; ranges are truncated to their intersection with
* restriction.
*/
private final Range<C> restriction;
private final NavigableMap<Cut> rangesByLowerBound;
private final NavigableMap<Cut> rangesByUpperBound;
private SubRangeSetRangesByLowerBound(
Range<Cut lowerBoundWindow,
Range<C> restriction,
NavigableMap<Cut> rangesByLowerBound) {
this.lowerBoundWindow = checkNotNull(lowerBoundWindow);
this.restriction = checkNotNull(restriction);
this.rangesByLowerBound = checkNotNull(rangesByLowerBound);
this.rangesByUpperBound = new RangesByUpperBound<C>(rangesByLowerBound);
}
private NavigableMap<Cut> subMap(Range> window) {
if (!window.isConnected(lowerBoundWindow)) {
return ImmutableSortedMap.of();
} else {
return new SubRangeSetRangesByLowerBound<C>(
lowerBoundWindow.intersection(window), restriction, rangesByLowerBound);
}
}
@Override
public NavigableMap<Cut> subMap(
Cut<C> fromKey, boolean fromInclusive, Cut toKey, boolean toInclusive) {
return subMap(
Range.range(
fromKey,
BoundType.forBoolean(fromInclusive),
toKey,
BoundType.forBoolean(toInclusive)));
}
@Override
public NavigableMap<Cut> headMap(Cut toKey, boolean inclusive) {
return subMap(Range.upTo(toKey, BoundType.forBoolean(inclusive)));
}
@Override
public NavigableMap<Cut> tailMap(Cut fromKey, boolean inclusive) {
return subMap(Range.downTo(fromKey, BoundType.forBoolean(inclusive)));
}
@Override
public Comparator<? super Cut comparator() {
return Ordering.<Cutnatural();
}
@Override
public boolean containsKey(@Nullable Object key) {
return get(key) != null;
}
@Override
@Nullable
public Range<C> get(@Nullable Object key) {
if (key instanceof Cut) {
try {
@SuppressWarnings("unchecked") // we catch CCE's
Cut<C> cut = (Cut) key;
if (!lowerBoundWindow.contains(cut)
|| cut.compareTo(restriction.lowerBound) < 0
|| cut.compareTo(restriction.upperBound) >= 0) {
return null;
} else if (cut.equals(restriction.lowerBound)) {
// it might be present, truncated on the left
Range<C> candidate = Maps.valueOrNull(rangesByLowerBound.floorEntry(cut));
if (candidate != null && candidate.upperBound.compareTo(restriction.lowerBound) > 0) {
return candidate.intersection(restriction);
}
} else {
Range<C> result = rangesByLowerBound.get(cut);
if (result != null) {
return result.intersection(restriction);
}
}
} catch (ClassCastException e) {
return null;
}
}
return null;
}
@Override
Iterator<Entry>> entryIterator() {
if (restriction.isEmpty()) {
return Iterators.emptyIterator();
}
final Iterator<Range completeRangeItr;
if (lowerBoundWindow.upperBound.isLessThan(restriction.lowerBound)) {
return Iterators.emptyIterator();
} else if (lowerBoundWindow.lowerBound.isLessThan(restriction.lowerBound)) {
// starts at the first range with upper bound strictly greater than restriction.lowerBound
completeRangeItr =
rangesByUpperBound.tailMap(restriction.lowerBound, false).values().iterator();
} else {
// starts at the first range with lower bound above lowerBoundWindow.lowerBound
completeRangeItr =
rangesByLowerBound
.tailMap(
lowerBoundWindow.lowerBound.endpoint(),
lowerBoundWindow.lowerBoundType() == BoundType.CLOSED)
.values()
.iterator();
}
final Cut<Cut upperBoundOnLowerBounds =
Ordering.natural()
.min(lowerBoundWindow.upperBound, Cut.belowValue(restriction.upperBound));
return new AbstractIterator<Entry>>() {
@Override
protected Entry<Cut> computeNext() {
if (!completeRangeItr.hasNext()) {
return endOfData();
}
Range<C> nextRange = completeRangeItr.next();
if (upperBoundOnLowerBounds.isLessThan(nextRange.lowerBound)) {
return endOfData();
} else {
nextRange = nextRange.intersection(restriction);
return Maps.immutableEntry(nextRange.lowerBound, nextRange);
}
}
};
}
@Override
Iterator<Entry>> descendingEntryIterator() {
if (restriction.isEmpty()) {
return Iterators.emptyIterator();
}
Cut<Cut upperBoundOnLowerBounds =
Ordering.natural()
.min(lowerBoundWindow.upperBound, Cut.belowValue(restriction.upperBound));
final Iterator<Range completeRangeItr =
rangesByLowerBound
.headMap(
upperBoundOnLowerBounds.endpoint(),
upperBoundOnLowerBounds.typeAsUpperBound() == BoundType.CLOSED)
.descendingMap()
.values()
.iterator();
return new AbstractIterator<Entry>>() {
@Override
protected Entry<Cut> computeNext() {
if (!completeRangeItr.hasNext()) {
return endOfData();
}
Range<C> nextRange = completeRangeItr.next();
if (restriction.lowerBound.compareTo(nextRange.upperBound) >= 0) {
return endOfData();
}
nextRange = nextRange.intersection(restriction);
if (lowerBoundWindow.contains(nextRange.lowerBound)) {
return Maps.immutableEntry(nextRange.lowerBound, nextRange);
} else {
return endOfData();
}
}
};
}
@Override
public int size() {
return Iterators.size(entryIterator());
}
}
@Override
public RangeSet<C> subRangeSet(Range view) {
return view.equals(Range.<C>all()) ? this : new SubRangeSet(view);
}
private final class SubRangeSet extends TreeRangeSet<C> {
private final Range<C> restriction;
SubRangeSet(Range<C> restriction) {
super(
new SubRangeSetRangesByLowerBound<C>(
Range.<Cutall(), restriction, TreeRangeSet.this.rangesByLowerBound));
this.restriction = restriction;
}
@Override
public boolean encloses(Range<C> range) {
if (!restriction.isEmpty() && restriction.encloses(range)) {
Range<C> enclosing = TreeRangeSet.this.rangeEnclosing(range);
return enclosing != null && !enclosing.intersection(restriction).isEmpty();
}
return false;
}
@Override
@Nullable
public Range<C> rangeContaining(C value) {
if (!restriction.contains(value)) {
return null;
}
Range<C> result = TreeRangeSet.this.rangeContaining(value);
return (result == null) ? null : result.intersection(restriction);
}
@Override
public void add(Range<C> rangeToAdd) {
checkArgument(
restriction.encloses(rangeToAdd),
"Cannot add range %s to subRangeSet(%s)",
rangeToAdd,
restriction);
super.add(rangeToAdd);
}
@Override
public void remove(Range<C> rangeToRemove) {
if (rangeToRemove.isConnected(restriction)) {
TreeRangeSet.this.remove(rangeToRemove.intersection(restriction));
}
}
@Override
public boolean contains(C value) {
return restriction.contains(value) && TreeRangeSet.this.contains(value);
}
@Override
public void clear() {
TreeRangeSet.this.remove(restriction);
}
@Override
public RangeSet<C> subRangeSet(Range view) {
if (view.encloses(restriction)) {
return this;
} else if (view.isConnected(restriction)) {
return new SubRangeSet(restriction.intersection(view));
} else {
return ImmutableRangeSet.of();
}
}
}
}
Other Java examples (source code examples)
Here is a short list of links related to this Java TreeRangeSet.java source code file:
|