001/* 002 * Copyright (C) 2012 The Guava Authors 003 * 004 * Licensed under the Apache License, Version 2.0 (the "License"); 005 * you may not use this file except in compliance with the License. 006 * You may obtain a copy of the License at 007 * 008 * http://www.apache.org/licenses/LICENSE-2.0 009 * 010 * Unless required by applicable law or agreed to in writing, software 011 * distributed under the License is distributed on an "AS IS" BASIS, 012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 013 * See the License for the specific language governing permissions and 014 * limitations under the License. 015 */ 016 017package com.google.common.collect; 018 019import com.google.common.annotations.Beta; 020import com.google.common.annotations.GwtIncompatible; 021import com.google.errorprone.annotations.DoNotMock; 022import java.util.Collection; 023import java.util.Map; 024import java.util.Map.Entry; 025import java.util.NoSuchElementException; 026import java.util.function.BiFunction; 027import javax.annotation.CheckForNull; 028import org.checkerframework.checker.nullness.qual.Nullable; 029 030/** 031 * A mapping from disjoint nonempty ranges to non-null values. Queries look up the value associated 032 * with the range (if any) that contains a specified key. 033 * 034 * <p>In contrast to {@link RangeSet}, no "coalescing" is done of {@linkplain 035 * Range#isConnected(Range) connected} ranges, even if they are mapped to the same value. 036 * 037 * @author Louis Wasserman 038 * @since 14.0 039 */ 040@Beta 041@DoNotMock("Use ImmutableRangeMap or TreeRangeMap") 042@GwtIncompatible 043@ElementTypesAreNonnullByDefault 044public interface RangeMap<K extends Comparable, V> { 045 /* 046 * TODO(cpovirk): These docs sometimes say "map" and sometimes say "range map." Pick one, or at 047 * least decide on a policy for when to use which. 048 */ 049 050 /** 051 * Returns the value associated with the specified key, or {@code null} if there is no such value. 052 * 053 * <p>Specifically, if any range in this range map contains the specified key, the value 054 * associated with that range is returned. 055 */ 056 @CheckForNull 057 V get(K key); 058 059 /** 060 * Returns the range containing this key and its associated value, if such a range is present in 061 * the range map, or {@code null} otherwise. 062 */ 063 @CheckForNull 064 Entry<Range<K>, V> getEntry(K key); 065 066 /** 067 * Returns the minimal range {@linkplain Range#encloses(Range) enclosing} the ranges in this 068 * {@code RangeMap}. 069 * 070 * @throws NoSuchElementException if this range map is empty 071 */ 072 Range<K> span(); 073 074 /** 075 * Maps a range to a specified value (optional operation). 076 * 077 * <p>Specifically, after a call to {@code put(range, value)}, if {@link 078 * Range#contains(Comparable) range.contains(k)}, then {@link #get(Comparable) get(k)} will return 079 * {@code value}. 080 * 081 * <p>If {@code range} {@linkplain Range#isEmpty() is empty}, then this is a no-op. 082 */ 083 void put(Range<K> range, V value); 084 085 /** 086 * Maps a range to a specified value, coalescing this range with any existing ranges with the same 087 * value that are {@linkplain Range#isConnected connected} to this range. 088 * 089 * <p>The behavior of {@link #get(Comparable) get(k)} after calling this method is identical to 090 * the behavior described in {@link #put(Range, Object) put(range, value)}, however the ranges 091 * returned from {@link #asMapOfRanges} will be different if there were existing entries which 092 * connect to the given range and value. 093 * 094 * <p>Even if the input range is empty, if it is connected on both sides by ranges mapped to the 095 * same value those two ranges will be coalesced. 096 * 097 * <p><b>Note:</b> coalescing requires calling {@code .equals()} on any connected values, which 098 * may be expensive depending on the value type. Using this method on range maps with large values 099 * such as {@link Collection} types is discouraged. 100 * 101 * @since 22.0 102 */ 103 void putCoalescing(Range<K> range, V value); 104 105 /** Puts all the associations from {@code rangeMap} into this range map (optional operation). */ 106 void putAll(RangeMap<K, V> rangeMap); 107 108 /** Removes all associations from this range map (optional operation). */ 109 void clear(); 110 111 /** 112 * Removes all associations from this range map in the specified range (optional operation). 113 * 114 * <p>If {@code !range.contains(k)}, {@link #get(Comparable) get(k)} will return the same result 115 * before and after a call to {@code remove(range)}. If {@code range.contains(k)}, then after a 116 * call to {@code remove(range)}, {@code get(k)} will return {@code null}. 117 */ 118 void remove(Range<K> range); 119 120 /** 121 * Merges a value into a part of the map by applying a remapping function. 122 * 123 * <p>If any parts of the range are already present in this map, those parts are mapped to new 124 * values by applying the remapping function. The remapping function accepts the map's existing 125 * value for that part of the range and the given value. It returns the value to be associated 126 * with that part of the map, or it returns {@code null} to clear that part of the map. 127 * 128 * <p>Any parts of the range not already present in this map are mapped to the specified value, 129 * unless the value is {@code null}. 130 * 131 * <p>Any existing entry spanning either range boundary may be split at the boundary, even if the 132 * merge does not affect its value. For example, if {@code rangeMap} had one entry {@code [1, 5] 133 * => 3} then {@code rangeMap.merge(Range.closed(0,2), 3, Math::max)} could yield a map with the 134 * entries {@code [0, 1) => 3, [1, 2] => 3, (2, 5] => 3}. 135 * 136 * @since 28.1 137 */ 138 void merge( 139 Range<K> range, 140 @CheckForNull V value, 141 BiFunction<? super V, ? super @Nullable V, ? extends @Nullable V> remappingFunction); 142 143 /** 144 * Returns a view of this range map as an unmodifiable {@code Map<Range<K>, V>}. Modifications to 145 * this range map are guaranteed to read through to the returned {@code Map}. 146 * 147 * <p>The returned {@code Map} iterates over entries in ascending order of the bounds of the 148 * {@code Range} entries. 149 * 150 * <p>It is guaranteed that no empty ranges will be in the returned {@code Map}. 151 */ 152 Map<Range<K>, V> asMapOfRanges(); 153 154 /** 155 * Returns a view of this range map as an unmodifiable {@code Map<Range<K>, V>}. Modifications to 156 * this range map are guaranteed to read through to the returned {@code Map}. 157 * 158 * <p>The returned {@code Map} iterates over entries in descending order of the bounds of the 159 * {@code Range} entries. 160 * 161 * <p>It is guaranteed that no empty ranges will be in the returned {@code Map}. 162 * 163 * @since 19.0 164 */ 165 Map<Range<K>, V> asDescendingMapOfRanges(); 166 167 /** 168 * Returns a view of the part of this range map that intersects with {@code range}. 169 * 170 * <p>For example, if {@code rangeMap} had the entries {@code [1, 5] => "foo", (6, 8) => "bar", 171 * (10, ∞) => "baz"} then {@code rangeMap.subRangeMap(Range.open(3, 12))} would return a range map 172 * with the entries {@code (3, 5] => "foo", (6, 8) => "bar", (10, 12) => "baz"}. 173 * 174 * <p>The returned range map supports all optional operations that this range map supports, except 175 * for {@code asMapOfRanges().iterator().remove()}. 176 * 177 * <p>The returned range map will throw an {@link IllegalArgumentException} on an attempt to 178 * insert a range not {@linkplain Range#encloses(Range) enclosed} by {@code range}. 179 */ 180 // TODO(cpovirk): Consider documenting that IAE on the various methods that can throw it. 181 RangeMap<K, V> subRangeMap(Range<K> range); 182 183 /** 184 * Returns {@code true} if {@code obj} is another {@code RangeMap} that has an equivalent {@link 185 * #asMapOfRanges()}. 186 */ 187 @Override 188 boolean equals(@CheckForNull Object o); 189 190 /** Returns {@code asMapOfRanges().hashCode()}. */ 191 @Override 192 int hashCode(); 193 194 /** Returns a readable string representation of this range map. */ 195 @Override 196 String toString(); 197}