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