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