13ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin/* 23ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * Copyright (C) 2012 The Guava Authors 33ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * 43ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * Licensed under the Apache License, Version 2.0 (the "License"); 53ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * you may not use this file except in compliance with the License. 63ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * You may obtain a copy of the License at 73ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * 83ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * http://www.apache.org/licenses/LICENSE-2.0 93ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * 103ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * Unless required by applicable law or agreed to in writing, software 113ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * distributed under the License is distributed on an "AS IS" BASIS, 123ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 133ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * See the License for the specific language governing permissions and 143ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * limitations under the License. 153ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin */ 163ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 173ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffinpackage com.google.common.collect; 183ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 193ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffinimport com.google.common.annotations.Beta; 203ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 213ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffinimport java.util.Map; 223ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 233ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffinimport javax.annotation.Nullable; 243ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 253ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin/** 263ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * A mapping from disjoint nonempty ranges to non-null values. Queries look up the value 273ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * associated with the range (if any) that contains a specified key. 283ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * 293ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * <p>In contrast to {@link RangeSet}, no "coalescing" is done of {@linkplain 303ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * Range#isConnected(Range) connected} ranges, even if they are mapped to the same value. 313ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * 323ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * @author Louis Wasserman 333ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * @since 14.0 343ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin */ 353ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin@Beta 363ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffinpublic interface RangeMap<K extends Comparable, V> { 373ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin /** 383ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * Returns the value associated with the specified key, or {@code null} if there is no 393ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * such value. 403ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * 413ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * <p>Specifically, if any range in this range map contains the specified key, the value 423ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * associated with that range is returned. 433ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin */ 443ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin @Nullable 453ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin V get(K key); 463ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 473ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin /** 483ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * Returns the range containing this key and its associated value, if such a range is present 493ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * in the range map, or {@code null} otherwise. 503ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin */ 513ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin @Nullable 523ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin Map.Entry<Range<K>, V> getEntry(K key); 533ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 543ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin /** 553ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * Returns the minimal range {@linkplain Range#encloses(Range) enclosing} the ranges 563ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * in this {@code RangeMap}. 573ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * 583ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * @throws NoSuchElementException if this range map is empty 593ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin */ 603ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin Range<K> span(); 613ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 623ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin /** 633ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * Maps a range to a specified value (optional operation). 643ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * 653ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * <p>Specifically, after a call to {@code put(range, value)}, if 663ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * {@link Range#contains(Comparable) range.contains(k)}, then {@link #get(Comparable) get(k)} 673ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * will return {@code value}. 683ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * 693ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * <p>If {@code range} {@linkplain Range#isEmpty() is empty}, then this is a no-op. 703ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin */ 713ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin void put(Range<K> range, V value); 723ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 733ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin /** 743ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * Puts all the associations from {@code rangeMap} into this range map (optional operation). 753ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin */ 763ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin void putAll(RangeMap<K, V> rangeMap); 773ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 783ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin /** 793ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * Removes all associations from this range map (optional operation). 803ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin */ 813ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin void clear(); 823ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 833ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin /** 843ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * Removes all associations from this range map in the specified range (optional operation). 853ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * 863ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * <p>If {@code !range.contains(k)}, {@link #get(Comparable) get(k)} will return the same result 873ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * before and after a call to {@code remove(range)}. If {@code range.contains(k)}, then 883ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * after a call to {@code remove(range)}, {@code get(k)} will return {@code null}. 893ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin */ 903ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin void remove(Range<K> range); 913ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 923ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin /** 933ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * Returns a view of this range map as an unmodifiable {@code Map<Range<K>, V>}. 943ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * Modifications to this range map are guaranteed to read through to the returned {@code Map}. 953ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * 963ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * <p>It is guaranteed that no empty ranges will be in the returned {@code Map}. 973ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin */ 983ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin Map<Range<K>, V> asMapOfRanges(); 993ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 1003ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin /** 1013ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * Returns a view of the part of this range map that intersects with {@code range}. 1023ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * 1033ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * <p>For example, if {@code rangeMap} had the entries 1043ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * {@code [1, 5] => "foo", (6, 8) => "bar", (10, \u2025) => "baz"} 1053ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * then {@code rangeMap.subRangeMap(Range.open(3, 12))} would return a range map 1063ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * with the entries {@code (3, 5) => "foo", (6, 8) => "bar", (10, 12) => "baz"}. 1073ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * 1083ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * <p>The returned range map supports all optional operations that this range map supports, 1093ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * except for {@code asMapOfRanges().iterator().remove()}. 1103ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * 1113ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * <p>The returned range map will throw an {@link IllegalArgumentException} on an attempt to 1123ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * insert a range not {@linkplain Range#encloses(Range) enclosed} by {@code range}. 1133ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin */ 1143ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin RangeMap<K, V> subRangeMap(Range<K> range); 1153ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 1163ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin /** 1173ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * Returns {@code true} if {@code obj} is another {@code RangeMap} that has an equivalent 1183ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * {@link #asMapOfRanges()}. 1193ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin */ 1203ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin @Override 1213ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin boolean equals(@Nullable Object o); 1223ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 1233ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin /** 1243ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * Returns {@code asMapOfRanges().hashCode()}. 1253ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin */ 1263ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin @Override 1273ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin int hashCode(); 1283ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 1293ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin /** 1303ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * Returns a readable string representation of this range map. 1313ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin */ 1323ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin @Override 1333ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin String toString(); 1343ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin} 135