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