1 /* 2 * Copyright (C) 2012 The Guava Authors 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package com.google.common.collect; 18 19 import com.google.common.annotations.GwtIncompatible; 20 import com.google.errorprone.annotations.DoNotMock; 21 import java.util.Collection; 22 import java.util.Map; 23 import java.util.Map.Entry; 24 import java.util.NoSuchElementException; 25 import javax.annotation.CheckForNull; 26 27 /** 28 * A mapping from disjoint nonempty ranges to non-null values. Queries look up the value associated 29 * with the range (if any) that contains a specified key. 30 * 31 * <p>In contrast to {@link RangeSet}, no "coalescing" is done of {@linkplain 32 * Range#isConnected(Range) connected} ranges, even if they are mapped to the same value. 33 * 34 * @author Louis Wasserman 35 * @since 14.0 36 */ 37 @DoNotMock("Use ImmutableRangeMap or TreeRangeMap") 38 @GwtIncompatible 39 @ElementTypesAreNonnullByDefault 40 public interface RangeMap<K extends Comparable, V> { 41 /* 42 * TODO(cpovirk): These docs sometimes say "map" and sometimes say "range map." Pick one, or at 43 * least decide on a policy for when to use which. 44 */ 45 46 /** 47 * Returns the value associated with the specified key, or {@code null} if there is no such value. 48 * 49 * <p>Specifically, if any range in this range map contains the specified key, the value 50 * associated with that range is returned. 51 */ 52 @CheckForNull get(K key)53 V get(K key); 54 55 /** 56 * Returns the range containing this key and its associated value, if such a range is present in 57 * the range map, or {@code null} otherwise. 58 */ 59 @CheckForNull getEntry(K key)60 Entry<Range<K>, V> getEntry(K key); 61 62 /** 63 * Returns the minimal range {@linkplain Range#encloses(Range) enclosing} the ranges in this 64 * {@code RangeMap}. 65 * 66 * @throws NoSuchElementException if this range map is empty 67 */ span()68 Range<K> span(); 69 70 /** 71 * Maps a range to a specified value (optional operation). 72 * 73 * <p>Specifically, after a call to {@code put(range, value)}, if {@link 74 * Range#contains(Comparable) range.contains(k)}, then {@link #get(Comparable) get(k)} will return 75 * {@code value}. 76 * 77 * <p>If {@code range} {@linkplain Range#isEmpty() is empty}, then this is a no-op. 78 */ put(Range<K> range, V value)79 void put(Range<K> range, V value); 80 81 /** 82 * Maps a range to a specified value, coalescing this range with any existing ranges with the same 83 * value that are {@linkplain Range#isConnected connected} to this range. 84 * 85 * <p>The behavior of {@link #get(Comparable) get(k)} after calling this method is identical to 86 * the behavior described in {@link #put(Range, Object) put(range, value)}, however the ranges 87 * returned from {@link #asMapOfRanges} will be different if there were existing entries which 88 * connect to the given range and value. 89 * 90 * <p>Even if the input range is empty, if it is connected on both sides by ranges mapped to the 91 * same value those two ranges will be coalesced. 92 * 93 * <p><b>Note:</b> coalescing requires calling {@code .equals()} on any connected values, which 94 * may be expensive depending on the value type. Using this method on range maps with large values 95 * such as {@link Collection} types is discouraged. 96 * 97 * @since 22.0 98 */ putCoalescing(Range<K> range, V value)99 void putCoalescing(Range<K> range, V value); 100 101 /** Puts all the associations from {@code rangeMap} into this range map (optional operation). */ putAll(RangeMap<K, ? extends V> rangeMap)102 void putAll(RangeMap<K, ? extends V> rangeMap); 103 104 /** Removes all associations from this range map (optional operation). */ clear()105 void clear(); 106 107 /** 108 * Removes all associations from this range map in the specified range (optional operation). 109 * 110 * <p>If {@code !range.contains(k)}, {@link #get(Comparable) get(k)} will return the same result 111 * before and after a call to {@code remove(range)}. If {@code range.contains(k)}, then after a 112 * call to {@code remove(range)}, {@code get(k)} will return {@code null}. 113 */ remove(Range<K> range)114 void remove(Range<K> range); 115 116 /** 117 * Returns a view of this range map as an unmodifiable {@code Map<Range<K>, V>}. Modifications to 118 * this range map are guaranteed to read through to the returned {@code Map}. 119 * 120 * <p>The returned {@code Map} iterates over entries in ascending order of the bounds of the 121 * {@code Range} entries. 122 * 123 * <p>It is guaranteed that no empty ranges will be in the returned {@code Map}. 124 */ asMapOfRanges()125 Map<Range<K>, V> asMapOfRanges(); 126 127 /** 128 * Returns a view of this range map as an unmodifiable {@code Map<Range<K>, V>}. Modifications to 129 * this range map are guaranteed to read through to the returned {@code Map}. 130 * 131 * <p>The returned {@code Map} iterates over entries in descending order of the bounds of the 132 * {@code Range} entries. 133 * 134 * <p>It is guaranteed that no empty ranges will be in the returned {@code Map}. 135 * 136 * @since 19.0 137 */ asDescendingMapOfRanges()138 Map<Range<K>, V> asDescendingMapOfRanges(); 139 140 /** 141 * Returns a view of the part of this range map that intersects with {@code range}. 142 * 143 * <p>For example, if {@code rangeMap} had the entries {@code [1, 5] => "foo", (6, 8) => "bar", 144 * (10, ∞) => "baz"} then {@code rangeMap.subRangeMap(Range.open(3, 12))} would return a range map 145 * with the entries {@code (3, 5] => "foo", (6, 8) => "bar", (10, 12) => "baz"}. 146 * 147 * <p>The returned range map supports all optional operations that this range map supports, except 148 * for {@code asMapOfRanges().iterator().remove()}. 149 * 150 * <p>The returned range map will throw an {@link IllegalArgumentException} on an attempt to 151 * insert a range not {@linkplain Range#encloses(Range) enclosed} by {@code range}. 152 */ 153 // TODO(cpovirk): Consider documenting that IAE on the various methods that can throw it. subRangeMap(Range<K> range)154 RangeMap<K, V> subRangeMap(Range<K> range); 155 156 /** 157 * Returns {@code true} if {@code obj} is another {@code RangeMap} that has an equivalent {@link 158 * #asMapOfRanges()}. 159 */ 160 @Override equals(@heckForNull Object o)161 boolean equals(@CheckForNull Object o); 162 163 /** Returns {@code asMapOfRanges().hashCode()}. */ 164 @Override hashCode()165 int hashCode(); 166 167 /** Returns a readable string representation of this range map. */ 168 @Override toString()169 String toString(); 170 } 171