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}