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}