|
Java example source code file (TreeRangeMap.java)
This example Java source code file (TreeRangeMap.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 TreeRangeMap.java Java example source code
/*
* Copyright (C) 2012 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.base.Predicates.compose;
import static com.google.common.base.Predicates.in;
import static com.google.common.base.Predicates.not;
import com.google.common.annotations.Beta;
import com.google.common.annotations.GwtIncompatible;
import com.google.common.base.MoreObjects;
import com.google.common.base.Predicate;
import com.google.common.collect.Maps.IteratorBasedAbstractMap;
import java.util.AbstractMap;
import java.util.Collection;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.NavigableMap;
import java.util.NoSuchElementException;
import java.util.Set;
import javax.annotation.Nullable;
/**
* An implementation of {@code RangeMap} based on a {@code TreeMap}, supporting
* all optional operations.
*
* <p>Like all {@code RangeMap} implementations, this supports neither null
* keys nor null values.
*
* @author Louis Wasserman
* @since 14.0
*/
@Beta
@GwtIncompatible // NavigableMap
public final class TreeRangeMap<K extends Comparable, V> implements RangeMap {
private final NavigableMap<Cut> entriesByLowerBound;
public static <K extends Comparable, V> TreeRangeMap create() {
return new TreeRangeMap<K, V>();
}
private TreeRangeMap() {
this.entriesByLowerBound = Maps.newTreeMap();
}
private static final class RangeMapEntry<K extends Comparable, V>
extends AbstractMapEntry<Range {
private final Range<K> range;
private final V value;
RangeMapEntry(Cut<K> lowerBound, Cut upperBound, V value) {
this(Range.create(lowerBound, upperBound), value);
}
RangeMapEntry(Range<K> range, V value) {
this.range = range;
this.value = value;
}
@Override
public Range<K> getKey() {
return range;
}
@Override
public V getValue() {
return value;
}
public boolean contains(K value) {
return range.contains(value);
}
Cut<K> getLowerBound() {
return range.lowerBound;
}
Cut<K> getUpperBound() {
return range.upperBound;
}
}
@Override
@Nullable
public V get(K key) {
Entry<Range entry = getEntry(key);
return (entry == null) ? null : entry.getValue();
}
@Override
@Nullable
public Entry<Range getEntry(K key) {
Map.Entry<Cut> mapEntry =
entriesByLowerBound.floorEntry(Cut.belowValue(key));
if (mapEntry != null && mapEntry.getValue().contains(key)) {
return mapEntry.getValue();
} else {
return null;
}
}
@Override
public void put(Range<K> range, V value) {
if (!range.isEmpty()) {
checkNotNull(value);
remove(range);
entriesByLowerBound.put(range.lowerBound, new RangeMapEntry<K, V>(range, value));
}
}
@Override
public void putAll(RangeMap<K, V> rangeMap) {
for (Map.Entry<Range entry : rangeMap.asMapOfRanges().entrySet()) {
put(entry.getKey(), entry.getValue());
}
}
@Override
public void clear() {
entriesByLowerBound.clear();
}
@Override
public Range<K> span() {
Entry<Cut> firstEntry = entriesByLowerBound.firstEntry();
Entry<Cut> lastEntry = entriesByLowerBound.lastEntry();
if (firstEntry == null) {
throw new NoSuchElementException();
}
return Range.create(
firstEntry.getValue().getKey().lowerBound, lastEntry.getValue().getKey().upperBound);
}
private void putRangeMapEntry(Cut<K> lowerBound, Cut upperBound, V value) {
entriesByLowerBound.put(lowerBound, new RangeMapEntry<K, V>(lowerBound, upperBound, value));
}
@Override
public void remove(Range<K> rangeToRemove) {
if (rangeToRemove.isEmpty()) {
return;
}
/*
* The comments for this method will use [ ] to indicate the bounds of rangeToRemove and ( ) to
* indicate the bounds of ranges in the range map.
*/
Map.Entry<Cut> mapEntryBelowToTruncate =
entriesByLowerBound.lowerEntry(rangeToRemove.lowerBound);
if (mapEntryBelowToTruncate != null) {
// we know ( [
RangeMapEntry<K, V> rangeMapEntry = mapEntryBelowToTruncate.getValue();
if (rangeMapEntry.getUpperBound().compareTo(rangeToRemove.lowerBound) > 0) {
// we know ( [ )
if (rangeMapEntry.getUpperBound().compareTo(rangeToRemove.upperBound) > 0) {
// we know ( [ ] ), so insert the range ] ) back into the map --
// it's being split apart
putRangeMapEntry(
rangeToRemove.upperBound,
rangeMapEntry.getUpperBound(),
mapEntryBelowToTruncate.getValue().getValue());
}
// overwrite mapEntryToTruncateBelow with a truncated range
putRangeMapEntry(
rangeMapEntry.getLowerBound(),
rangeToRemove.lowerBound,
mapEntryBelowToTruncate.getValue().getValue());
}
}
Map.Entry<Cut> mapEntryAboveToTruncate =
entriesByLowerBound.lowerEntry(rangeToRemove.upperBound);
if (mapEntryAboveToTruncate != null) {
// we know ( ]
RangeMapEntry<K, V> rangeMapEntry = mapEntryAboveToTruncate.getValue();
if (rangeMapEntry.getUpperBound().compareTo(rangeToRemove.upperBound) > 0) {
// we know ( ] ), and since we dealt with truncating below already,
// we know [ ( ] )
putRangeMapEntry(
rangeToRemove.upperBound,
rangeMapEntry.getUpperBound(),
mapEntryAboveToTruncate.getValue().getValue());
entriesByLowerBound.remove(rangeToRemove.lowerBound);
}
}
entriesByLowerBound.subMap(rangeToRemove.lowerBound, rangeToRemove.upperBound).clear();
}
@Override
public Map<Range asMapOfRanges() {
return new AsMapOfRanges(entriesByLowerBound.values());
}
@Override
public Map<Range asDescendingMapOfRanges() {
return new AsMapOfRanges(entriesByLowerBound.descendingMap().values());
}
private final class AsMapOfRanges extends IteratorBasedAbstractMap<Range {
final Iterable<Entry> entryIterable;
@SuppressWarnings("unchecked") // it's safe to upcast iterables
AsMapOfRanges(Iterable<RangeMapEntry entryIterable) {
this.entryIterable = (Iterable) entryIterable;
}
@Override
public boolean containsKey(@Nullable Object key) {
return get(key) != null;
}
@Override
public V get(@Nullable Object key) {
if (key instanceof Range) {
Range<?> range = (Range) key;
RangeMapEntry<K, V> rangeMapEntry = entriesByLowerBound.get(range.lowerBound);
if (rangeMapEntry != null && rangeMapEntry.getKey().equals(range)) {
return rangeMapEntry.getValue();
}
}
return null;
}
@Override
public int size() {
return entriesByLowerBound.size();
}
@Override
Iterator<Entry> entryIterator() {
return entryIterable.iterator();
}
}
@Override
public RangeMap<K, V> subRangeMap(Range subRange) {
if (subRange.equals(Range.all())) {
return this;
} else {
return new SubRangeMap(subRange);
}
}
@SuppressWarnings("unchecked")
private RangeMap<K, V> emptySubRangeMap() {
return EMPTY_SUB_RANGE_MAP;
}
private static final RangeMap EMPTY_SUB_RANGE_MAP =
new RangeMap() {
@Override
@Nullable
public Object get(Comparable key) {
return null;
}
@Override
@Nullable
public Entry<Range, Object> getEntry(Comparable key) {
return null;
}
@Override
public Range span() {
throw new NoSuchElementException();
}
@Override
public void put(Range range, Object value) {
checkNotNull(range);
throw new IllegalArgumentException(
"Cannot insert range " + range + " into an empty subRangeMap");
}
@Override
public void putAll(RangeMap rangeMap) {
if (!rangeMap.asMapOfRanges().isEmpty()) {
throw new IllegalArgumentException(
"Cannot putAll(nonEmptyRangeMap) into an empty subRangeMap");
}
}
@Override
public void clear() {}
@Override
public void remove(Range range) {
checkNotNull(range);
}
@Override
public Map<Range, Object> asMapOfRanges() {
return Collections.emptyMap();
}
@Override
public Map<Range, Object> asDescendingMapOfRanges() {
return Collections.emptyMap();
}
@Override
public RangeMap subRangeMap(Range range) {
checkNotNull(range);
return this;
}
};
private class SubRangeMap implements RangeMap<K, V> {
private final Range<K> subRange;
SubRangeMap(Range<K> subRange) {
this.subRange = subRange;
}
@Override
@Nullable
public V get(K key) {
return subRange.contains(key) ? TreeRangeMap.this.get(key) : null;
}
@Override
@Nullable
public Entry<Range getEntry(K key) {
if (subRange.contains(key)) {
Entry<Range entry = TreeRangeMap.this.getEntry(key);
if (entry != null) {
return Maps.immutableEntry(entry.getKey().intersection(subRange), entry.getValue());
}
}
return null;
}
@Override
public Range<K> span() {
Cut<K> lowerBound;
Entry<Cut> lowerEntry =
entriesByLowerBound.floorEntry(subRange.lowerBound);
if (lowerEntry != null
&& lowerEntry.getValue().getUpperBound().compareTo(subRange.lowerBound) > 0) {
lowerBound = subRange.lowerBound;
} else {
lowerBound = entriesByLowerBound.ceilingKey(subRange.lowerBound);
if (lowerBound == null || lowerBound.compareTo(subRange.upperBound) >= 0) {
throw new NoSuchElementException();
}
}
Cut<K> upperBound;
Entry<Cut> upperEntry =
entriesByLowerBound.lowerEntry(subRange.upperBound);
if (upperEntry == null) {
throw new NoSuchElementException();
} else if (upperEntry.getValue().getUpperBound().compareTo(subRange.upperBound) >= 0) {
upperBound = subRange.upperBound;
} else {
upperBound = upperEntry.getValue().getUpperBound();
}
return Range.create(lowerBound, upperBound);
}
@Override
public void put(Range<K> range, V value) {
checkArgument(
subRange.encloses(range), "Cannot put range %s into a subRangeMap(%s)", range, subRange);
TreeRangeMap.this.put(range, value);
}
@Override
public void putAll(RangeMap<K, V> rangeMap) {
if (rangeMap.asMapOfRanges().isEmpty()) {
return;
}
Range<K> span = rangeMap.span();
checkArgument(
subRange.encloses(span),
"Cannot putAll rangeMap with span %s into a subRangeMap(%s)",
span,
subRange);
TreeRangeMap.this.putAll(rangeMap);
}
@Override
public void clear() {
TreeRangeMap.this.remove(subRange);
}
@Override
public void remove(Range<K> range) {
if (range.isConnected(subRange)) {
TreeRangeMap.this.remove(range.intersection(subRange));
}
}
@Override
public RangeMap<K, V> subRangeMap(Range range) {
if (!range.isConnected(subRange)) {
return emptySubRangeMap();
} else {
return TreeRangeMap.this.subRangeMap(range.intersection(subRange));
}
}
@Override
public Map<Range asMapOfRanges() {
return new SubRangeMapAsMap();
}
@Override
public Map<Range asDescendingMapOfRanges() {
return new SubRangeMapAsMap() {
@Override
Iterator<Entry> entryIterator() {
if (subRange.isEmpty()) {
return Iterators.emptyIterator();
}
final Iterator<RangeMapEntry backingItr =
entriesByLowerBound
.headMap(subRange.upperBound, false)
.descendingMap()
.values()
.iterator();
return new AbstractIterator<Entry>() {
@Override
protected Entry<Range computeNext() {
while (backingItr.hasNext()) {
RangeMapEntry<K, V> entry = backingItr.next();
if (entry.getUpperBound().compareTo(subRange.lowerBound) <= 0) {
return endOfData();
}
return Maps.immutableEntry(entry.getKey().intersection(subRange), entry.getValue());
}
return endOfData();
}
};
}
};
}
@Override
public boolean equals(@Nullable Object o) {
if (o instanceof RangeMap) {
RangeMap<?, ?> rangeMap = (RangeMap) o;
return asMapOfRanges().equals(rangeMap.asMapOfRanges());
}
return false;
}
@Override
public int hashCode() {
return asMapOfRanges().hashCode();
}
@Override
public String toString() {
return asMapOfRanges().toString();
}
class SubRangeMapAsMap extends AbstractMap<Range {
@Override
public boolean containsKey(Object key) {
return get(key) != null;
}
@Override
public V get(Object key) {
try {
if (key instanceof Range) {
@SuppressWarnings("unchecked") // we catch ClassCastExceptions
Range<K> r = (Range) key;
if (!subRange.encloses(r) || r.isEmpty()) {
return null;
}
RangeMapEntry<K, V> candidate = null;
if (r.lowerBound.compareTo(subRange.lowerBound) == 0) {
// r could be truncated on the left
Entry<Cut> entry =
entriesByLowerBound.floorEntry(r.lowerBound);
if (entry != null) {
candidate = entry.getValue();
}
} else {
candidate = entriesByLowerBound.get(r.lowerBound);
}
if (candidate != null
&& candidate.getKey().isConnected(subRange)
&& candidate.getKey().intersection(subRange).equals(r)) {
return candidate.getValue();
}
}
} catch (ClassCastException e) {
return null;
}
return null;
}
@Override
public V remove(Object key) {
V value = get(key);
if (value != null) {
@SuppressWarnings("unchecked") // it's definitely in the map, so safe
Range<K> range = (Range) key;
TreeRangeMap.this.remove(range);
return value;
}
return null;
}
@Override
public void clear() {
SubRangeMap.this.clear();
}
private boolean removeEntryIf(Predicate<? super Entry> predicate) {
List<Range toRemove = Lists.newArrayList();
for (Entry<Range entry : entrySet()) {
if (predicate.apply(entry)) {
toRemove.add(entry.getKey());
}
}
for (Range<K> range : toRemove) {
TreeRangeMap.this.remove(range);
}
return !toRemove.isEmpty();
}
@Override
public Set<Range keySet() {
return new Maps.KeySet<Range(SubRangeMapAsMap.this) {
@Override
public boolean remove(@Nullable Object o) {
return SubRangeMapAsMap.this.remove(o) != null;
}
@Override
public boolean retainAll(Collection<?> c) {
return removeEntryIf(compose(not(in(c)), Maps.<RangekeyFunction()));
}
};
}
@Override
public Set<Entry> entrySet() {
return new Maps.EntrySet<Range() {
@Override
Map<Range map() {
return SubRangeMapAsMap.this;
}
@Override
public Iterator<Entry> iterator() {
return entryIterator();
}
@Override
public boolean retainAll(Collection<?> c) {
return removeEntryIf(not(in(c)));
}
@Override
public int size() {
return Iterators.size(iterator());
}
@Override
public boolean isEmpty() {
return !iterator().hasNext();
}
};
}
Iterator<Entry> entryIterator() {
if (subRange.isEmpty()) {
return Iterators.emptyIterator();
}
Cut<K> cutToStart =
MoreObjects.firstNonNull(
entriesByLowerBound.floorKey(subRange.lowerBound), subRange.lowerBound);
final Iterator<RangeMapEntry backingItr =
entriesByLowerBound.tailMap(cutToStart, true).values().iterator();
return new AbstractIterator<Entry>() {
@Override
protected Entry<Range computeNext() {
while (backingItr.hasNext()) {
RangeMapEntry<K, V> entry = backingItr.next();
if (entry.getLowerBound().compareTo(subRange.upperBound) >= 0) {
return endOfData();
} else if (entry.getUpperBound().compareTo(subRange.lowerBound) > 0) {
// this might not be true e.g. at the start of the iteration
return Maps.immutableEntry(entry.getKey().intersection(subRange), entry.getValue());
}
}
return endOfData();
}
};
}
@Override
public Collection<V> values() {
return new Maps.Values<Range(this) {
@Override
public boolean removeAll(Collection<?> c) {
return removeEntryIf(compose(in(c), Maps.<V>valueFunction()));
}
@Override
public boolean retainAll(Collection<?> c) {
return removeEntryIf(compose(not(in(c)), Maps.<V>valueFunction()));
}
};
}
}
}
@Override
public boolean equals(@Nullable Object o) {
if (o instanceof RangeMap) {
RangeMap<?, ?> rangeMap = (RangeMap) o;
return asMapOfRanges().equals(rangeMap.asMapOfRanges());
}
return false;
}
@Override
public int hashCode() {
return asMapOfRanges().hashCode();
}
@Override
public String toString() {
return entriesByLowerBound.values().toString();
}
}
Other Java examples (source code examples)
Here is a short list of links related to this Java TreeRangeMap.java source code file:
|