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