1/*
2 * Copyright (C) 2012 The Guava Authors
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
5 * in compliance with the License. You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software distributed under the License
10 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
11 * or implied. See the License for the specific language governing permissions and limitations under
12 * the License.
13 */
14
15package com.google.common.collect;
16
17import static com.google.common.base.Preconditions.checkArgument;
18import static com.google.common.base.Preconditions.checkElementIndex;
19import static com.google.common.base.Preconditions.checkNotNull;
20
21import com.google.common.annotations.Beta;
22import com.google.common.annotations.GwtIncompatible;
23import com.google.common.collect.SortedLists.KeyAbsentBehavior;
24import com.google.common.collect.SortedLists.KeyPresentBehavior;
25
26import java.util.Map;
27import java.util.Map.Entry;
28import java.util.NoSuchElementException;
29
30import javax.annotation.Nullable;
31
32/**
33 * An immutable implementation of {@code RangeMap}, supporting all query operations efficiently.
34 *
35 * <p>Like all {@code RangeMap} implementations, this supports neither null keys nor null values.
36 *
37 * @author Louis Wasserman
38 * @since 14.0
39 */
40@Beta
41@GwtIncompatible("NavigableMap")
42public class ImmutableRangeMap<K extends Comparable<?>, V> implements RangeMap<K, V> {
43
44  private static final ImmutableRangeMap<Comparable<?>, Object> EMPTY =
45      new ImmutableRangeMap<Comparable<?>, Object>(
46          ImmutableList.<Range<Comparable<?>>>of(), ImmutableList.of());
47
48  /**
49   * Returns an empty immutable range map.
50   */
51  @SuppressWarnings("unchecked")
52  public static <K extends Comparable<?>, V> ImmutableRangeMap<K, V> of() {
53    return (ImmutableRangeMap<K, V>) EMPTY;
54  }
55
56  /**
57   * Returns an immutable range map mapping a single range to a single value.
58   */
59  public static <K extends Comparable<?>, V> ImmutableRangeMap<K, V> of(
60      Range<K> range, V value) {
61    return new ImmutableRangeMap<K, V>(ImmutableList.of(range), ImmutableList.of(value));
62  }
63
64  @SuppressWarnings("unchecked")
65  public static <K extends Comparable<?>, V> ImmutableRangeMap<K, V> copyOf(
66      RangeMap<K, ? extends V> rangeMap) {
67    if (rangeMap instanceof ImmutableRangeMap) {
68      return (ImmutableRangeMap<K, V>) rangeMap;
69    }
70    Map<Range<K>, ? extends V> map = rangeMap.asMapOfRanges();
71    ImmutableList.Builder<Range<K>> rangesBuilder = new ImmutableList.Builder<Range<K>>(map.size());
72    ImmutableList.Builder<V> valuesBuilder = new ImmutableList.Builder<V>(map.size());
73    for (Entry<Range<K>, ? extends V> entry : map.entrySet()) {
74      rangesBuilder.add(entry.getKey());
75      valuesBuilder.add(entry.getValue());
76    }
77    return new ImmutableRangeMap<K, V>(rangesBuilder.build(), valuesBuilder.build());
78  }
79
80  /**
81   * Returns a new builder for an immutable range map.
82   */
83  public static <K extends Comparable<?>, V> Builder<K, V> builder() {
84    return new Builder<K, V>();
85  }
86
87  /**
88   * A builder for immutable range maps. Overlapping ranges are prohibited.
89   */
90  public static final class Builder<K extends Comparable<?>, V> {
91    private final RangeSet<K> keyRanges;
92    private final RangeMap<K, V> rangeMap;
93
94    public Builder() {
95      this.keyRanges = TreeRangeSet.create();
96      this.rangeMap = TreeRangeMap.create();
97    }
98
99    /**
100     * Associates the specified range with the specified value.
101     *
102     * @throws IllegalArgumentException if {@code range} overlaps with any other ranges inserted
103     *         into this builder, or if {@code range} is empty
104     */
105    public Builder<K, V> put(Range<K> range, V value) {
106      checkNotNull(range);
107      checkNotNull(value);
108      checkArgument(!range.isEmpty(), "Range must not be empty, but was %s", range);
109      if (!keyRanges.complement().encloses(range)) {
110        // it's an error case; we can afford an expensive lookup
111        for (Entry<Range<K>, V> entry : rangeMap.asMapOfRanges().entrySet()) {
112          Range<K> key = entry.getKey();
113          if (key.isConnected(range) && !key.intersection(range).isEmpty()) {
114            throw new IllegalArgumentException(
115                "Overlapping ranges: range " + range + " overlaps with entry " + entry);
116          }
117        }
118      }
119      keyRanges.add(range);
120      rangeMap.put(range, value);
121      return this;
122    }
123
124    /**
125     * Copies all associations from the specified range map into this builder.
126     *
127     * @throws IllegalArgumentException if any of the ranges in {@code rangeMap} overlap with ranges
128     *         already in this builder
129     */
130    public Builder<K, V> putAll(RangeMap<K, ? extends V> rangeMap) {
131      for (Entry<Range<K>, ? extends V> entry : rangeMap.asMapOfRanges().entrySet()) {
132        put(entry.getKey(), entry.getValue());
133      }
134      return this;
135    }
136
137    /**
138     * Returns an {@code ImmutableRangeMap} containing the associations previously added to this
139     * builder.
140     */
141    public ImmutableRangeMap<K, V> build() {
142      Map<Range<K>, V> map = rangeMap.asMapOfRanges();
143      ImmutableList.Builder<Range<K>> rangesBuilder =
144          new ImmutableList.Builder<Range<K>>(map.size());
145      ImmutableList.Builder<V> valuesBuilder = new ImmutableList.Builder<V>(map.size());
146      for (Entry<Range<K>, V> entry : map.entrySet()) {
147        rangesBuilder.add(entry.getKey());
148        valuesBuilder.add(entry.getValue());
149      }
150      return new ImmutableRangeMap<K, V>(rangesBuilder.build(), valuesBuilder.build());
151    }
152  }
153
154  private final ImmutableList<Range<K>> ranges;
155  private final ImmutableList<V> values;
156
157  ImmutableRangeMap(ImmutableList<Range<K>> ranges, ImmutableList<V> values) {
158    this.ranges = ranges;
159    this.values = values;
160  }
161
162  @Override
163  @Nullable
164  public V get(K key) {
165    int index = SortedLists.binarySearch(ranges, Range.<K>lowerBoundFn(),
166        Cut.belowValue(key), KeyPresentBehavior.ANY_PRESENT, KeyAbsentBehavior.NEXT_LOWER);
167    if (index == -1) {
168      return null;
169    } else {
170      Range<K> range = ranges.get(index);
171      return range.contains(key) ? values.get(index) : null;
172    }
173  }
174
175  @Override
176  @Nullable
177  public Map.Entry<Range<K>, V> getEntry(K key) {
178    int index = SortedLists.binarySearch(ranges, Range.<K>lowerBoundFn(),
179        Cut.belowValue(key), KeyPresentBehavior.ANY_PRESENT, KeyAbsentBehavior.NEXT_LOWER);
180    if (index == -1) {
181      return null;
182    } else {
183      Range<K> range = ranges.get(index);
184      return range.contains(key) ? Maps.immutableEntry(range, values.get(index)) : null;
185    }
186  }
187
188  @Override
189  public Range<K> span() {
190    if (ranges.isEmpty()) {
191      throw new NoSuchElementException();
192    }
193    Range<K> firstRange = ranges.get(0);
194    Range<K> lastRange = ranges.get(ranges.size() - 1);
195    return Range.create(firstRange.lowerBound, lastRange.upperBound);
196  }
197
198  @Override
199  public void put(Range<K> range, V value) {
200    throw new UnsupportedOperationException();
201  }
202
203  @Override
204  public void putAll(RangeMap<K, V> rangeMap) {
205    throw new UnsupportedOperationException();
206  }
207
208  @Override
209  public void clear() {
210    throw new UnsupportedOperationException();
211  }
212
213  @Override
214  public void remove(Range<K> range) {
215    throw new UnsupportedOperationException();
216  }
217
218  @Override
219  public ImmutableMap<Range<K>, V> asMapOfRanges() {
220    if (ranges.isEmpty()) {
221      return ImmutableMap.of();
222    }
223    RegularImmutableSortedSet<Range<K>> rangeSet =
224        new RegularImmutableSortedSet<Range<K>>(ranges, Range.RANGE_LEX_ORDERING);
225    return new RegularImmutableSortedMap<Range<K>, V>(rangeSet, values);
226  }
227
228  @Override
229  public ImmutableRangeMap<K, V> subRangeMap(final Range<K> range) {
230    if (checkNotNull(range).isEmpty()) {
231      return ImmutableRangeMap.of();
232    } else if (ranges.isEmpty() || range.encloses(span())) {
233      return this;
234    }
235    int lowerIndex = SortedLists.binarySearch(
236        ranges, Range.<K>upperBoundFn(), range.lowerBound,
237        KeyPresentBehavior.FIRST_AFTER, KeyAbsentBehavior.NEXT_HIGHER);
238    int upperIndex = SortedLists.binarySearch(ranges,
239        Range.<K>lowerBoundFn(), range.upperBound,
240        KeyPresentBehavior.ANY_PRESENT, KeyAbsentBehavior.NEXT_HIGHER);
241    if (lowerIndex >= upperIndex) {
242      return ImmutableRangeMap.of();
243    }
244    final int off = lowerIndex;
245    final int len = upperIndex - lowerIndex;
246    ImmutableList<Range<K>> subRanges = new ImmutableList<Range<K>>() {
247      @Override
248      public int size() {
249        return len;
250      }
251
252      @Override
253      public Range<K> get(int index) {
254        checkElementIndex(index, len);
255        if (index == 0 || index == len - 1) {
256          return ranges.get(index + off).intersection(range);
257        } else {
258          return ranges.get(index + off);
259        }
260      }
261
262      @Override
263      boolean isPartialView() {
264        return true;
265      }
266    };
267    final ImmutableRangeMap<K, V> outer = this;
268    return new ImmutableRangeMap<K, V>(
269        subRanges, values.subList(lowerIndex, upperIndex)) {
270          @Override
271          public ImmutableRangeMap<K, V> subRangeMap(Range<K> subRange) {
272            if (range.isConnected(subRange)) {
273              return outer.subRangeMap(subRange.intersection(range));
274            } else {
275              return ImmutableRangeMap.of();
276            }
277          }
278    };
279  }
280
281  @Override
282  public int hashCode() {
283    return asMapOfRanges().hashCode();
284  }
285
286  @Override
287  public boolean equals(@Nullable Object o) {
288    if (o instanceof RangeMap) {
289      RangeMap<?, ?> rangeMap = (RangeMap<?, ?>) o;
290      return asMapOfRanges().equals(rangeMap.asMapOfRanges());
291    }
292    return false;
293  }
294
295  @Override
296  public String toString() {
297    return asMapOfRanges().toString();
298  }
299}
300