Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
  /*
   * Copyright (C) 2009 The Guava Authors
   *
   * Licensed under the Apache License, Version 2.0 (the "License");
   * you may not use this file except in compliance with the License.
   * You may obtain a copy of the License at
   *
   * http://www.apache.org/licenses/LICENSE-2.0
   *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */
 
 package com.google.common.collect;
 
 import static com.google.common.base.Preconditions.checkArgument;
 import static com.google.common.base.Preconditions.checkNotNull;
 import static com.google.common.collect.Maps.keyOrNull;
 
 
 import java.util.List;
 import java.util.Map;
 
 import  javax.annotation.Nullable;

An immutable SortedMap. Does not permit null keys or values.

Unlike Collections.unmodifiableSortedMap, which is a view of a separate map which can still change, an instance of ImmutableSortedMap contains its own data and will never change. ImmutableSortedMap is convenient for public static final maps ("constant maps") and also lets you easily make a "defensive copy" of a map provided to your class by a caller.

Note: Although this class is not final, it cannot be subclassed as it has no public or protected constructors. Thus, instances of this class are guaranteed to be immutable.

See the Guava User Guide article on immutable collections.

Author(s):
Jared Levy
Louis Wasserman
Since:
2.0 (imported from Google Collections Library; implements NavigableMap since 12.0)
 
 @GwtCompatible(serializable = true, emulated = true)
 public abstract class ImmutableSortedMap<K, V>
     extends ImmutableSortedMapFauxverideShim<K, V> implements NavigableMap<K, V> {
   /*
    * TODO(kevinb): Confirm that ImmutableSortedMap is faster to construct and
    * uses less memory than TreeMap; then say so in the class Javadoc.
    */
   private static final Comparator<ComparableNATURAL_ORDER = Ordering.natural();
 
   private static final ImmutableSortedMap<ComparableObjectNATURAL_EMPTY_MAP =
 
   static <K, V> ImmutableSortedMap<K, V> emptyMap(Comparator<? super K> comparator) {
     if (Ordering.natural().equals(comparator)) {
       return of();
     } else {
       return new EmptyImmutableSortedMap<K, V>(comparator);
     }
   }
 
   static <K, V> ImmutableSortedMap<K, V> fromSortedEntries(
       Comparator<? super K> comparator,
       Collection<? extends Entry<? extends K, ? extends V>> entries) {
     if (entries.isEmpty()) {
       return emptyMap(comparator);
     }
 
     ImmutableList.Builder<K> keyBuilder = ImmutableList.builder();
     ImmutableList.Builder<V> valueBuilder = ImmutableList.builder();
     for (Entry<? extends K, ? extends V> entry : entries) {
       keyBuilder.add(entry.getKey());
       valueBuilder.add(entry.getValue());
     }
 
     return new RegularImmutableSortedMap<K, V>(
         new RegularImmutableSortedSet<K>(keyBuilder.build(), comparator),
         valueBuilder.build());
   }
 
   static <K, V> ImmutableSortedMap<K, V> from(
      ImmutableSortedSet<K> keySetImmutableList<V> valueList) {
    if (keySet.isEmpty()) {
      return emptyMap(keySet.comparator());
    } else {
      return new RegularImmutableSortedMap<K, V>(
          (RegularImmutableSortedSet<K>) keySet,
          valueList);
    }
  }

  
Returns the empty sorted map.
  @SuppressWarnings("unchecked")
  // unsafe, comparator() returns a comparator on the specified type
  // TODO(kevinb): evaluate whether or not of().comparator() should return null
  public static <K, V> ImmutableSortedMap<K, V> of() {
    return (ImmutableSortedMap<K, V>) ;
  }

  
Returns an immutable map containing a single entry.
  public static <K extends Comparable<? super K>, V>
      ImmutableSortedMap<K, V> of(K k1, V v1) {
    return from(ImmutableSortedSet.of(k1), ImmutableList.of(v1));
  }

  
Returns an immutable sorted map containing the given entries, sorted by the natural ordering of their keys.

Throws:
IllegalArgumentException if the two keys are equal according to their natural ordering
  public static <K extends Comparable<? super K>, V> ImmutableSortedMap<K, V>
      of(K k1, V v1, K k2, V v2) {
    return new Builder<K, V>(Ordering.natural())
        .put(k1v1).put(k2v2).build();
  }

  
Returns an immutable sorted map containing the given entries, sorted by the natural ordering of their keys.

Throws:
IllegalArgumentException if any two keys are equal according to their natural ordering
  public static <K extends Comparable<? super K>, V> ImmutableSortedMap<K, V>
      of(K k1, V v1, K k2, V v2, K k3, V v3) {
    return new Builder<K, V>(Ordering.natural())
        .put(k1v1).put(k2v2).put(k3v3).build();
  }

  
Returns an immutable sorted map containing the given entries, sorted by the natural ordering of their keys.

Throws:
IllegalArgumentException if any two keys are equal according to their natural ordering
  public static <K extends Comparable<? super K>, V> ImmutableSortedMap<K, V>
      of(K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4) {
    return new Builder<K, V>(Ordering.natural())
        .put(k1v1).put(k2v2).put(k3v3).put(k4v4).build();
  }

  
Returns an immutable sorted map containing the given entries, sorted by the natural ordering of their keys.

Throws:
IllegalArgumentException if any two keys are equal according to their natural ordering
  public static <K extends Comparable<? super K>, V> ImmutableSortedMap<K, V>
      of(K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5) {
    return new Builder<K, V>(Ordering.natural())
        .put(k1v1).put(k2v2).put(k3v3).put(k4v4).put(k5v5).build();
  }

  
Returns an immutable map containing the same entries as map, sorted by the natural ordering of the keys.

Despite the method name, this method attempts to avoid actually copying the data when it is safe to do so. The exact circumstances under which a copy will or will not be performed are undocumented and subject to change.

This method is not type-safe, as it may be called on a map with keys that are not mutually comparable.

Throws:
ClassCastException if the keys in map are not mutually comparable
NullPointerException if any key or value in map is null
IllegalArgumentException if any two keys are equal according to their natural ordering
  public static <K, V> ImmutableSortedMap<K, V> copyOf(
      Map<? extends K, ? extends V> map) {
    // Hack around K not being a subtype of Comparable.
    // Unsafe, see ImmutableSortedSetFauxverideShim.
    @SuppressWarnings("unchecked")
    Ordering<K> naturalOrder = (Ordering<K>) Ordering.<Comparable>natural();
    return copyOfInternal(mapnaturalOrder);
  }

  
Returns an immutable map containing the same entries as map, with keys sorted by the provided comparator.

Despite the method name, this method attempts to avoid actually copying the data when it is safe to do so. The exact circumstances under which a copy will or will not be performed are undocumented and subject to change.

Throws:
NullPointerException if any key or value in map is null
IllegalArgumentException if any two keys are equal according to the comparator
  public static <K, V> ImmutableSortedMap<K, V> copyOf(
      Map<? extends K, ? extends V> mapComparator<? super K> comparator) {
    return copyOfInternal(mapcheckNotNull(comparator));
  }

  
Returns an immutable map containing the same entries as the provided sorted map, with the same ordering.

Despite the method name, this method attempts to avoid actually copying the data when it is safe to do so. The exact circumstances under which a copy will or will not be performed are undocumented and subject to change.

Throws:
NullPointerException if any key or value in map is null
  @SuppressWarnings("unchecked")
  public static <K, V> ImmutableSortedMap<K, V> copyOfSorted(
      SortedMap<K, ? extends V> map) {
    Comparator<? super K> comparator = map.comparator();
    if (comparator == null) {
      // If map has a null comparator, the keys should have a natural ordering,
      // even though K doesn't explicitly implement Comparable.
      comparator = (Comparator<? super K>) ;
    }
    return copyOfInternal(mapcomparator);
  }
  private static <K, V> ImmutableSortedMap<K, V> copyOfInternal(
      Map<? extends K, ? extends V> mapComparator<? super K> comparator) {
    boolean sameComparator = false;
    if (map instanceof SortedMap) {
      SortedMap<?, ?> sortedMap = (SortedMap<?, ?>) map;
      Comparator<?> comparator2 = sortedMap.comparator();
      sameComparator = (comparator2 == null)
          ? comparator == 
          : comparator.equals(comparator2);
    }
    if (sameComparator && (map instanceof ImmutableSortedMap)) {
      // TODO(kevinb): Prove that this cast is safe, even though
      // Collections.unmodifiableSortedMap requires the same key type.
      @SuppressWarnings("unchecked")
      ImmutableSortedMap<K, V> kvMap = (ImmutableSortedMap<K, V>) map;
      if (!kvMap.isPartialView()) {
        return kvMap;
      }
    }
    // "adding" type params to an array of a raw type should be safe as
    // long as no one can ever cast that same array instance back to a
    // raw type.
    @SuppressWarnings("unchecked")
    Entry<K, V>[] entries = map.entrySet().toArray(new Entry[0]);
    for (int i = 0; i < entries.lengthi++) {
      Entry<K, V> entry = entries[i];
      entries[i] = entryOf(entry.getKey(), entry.getValue());
    }
    List<Entry<K, V>> list = Arrays.asList(entries);
    if (!sameComparator) {
      sortEntries(listcomparator);
      validateEntries(listcomparator);
    }
    return fromSortedEntries(comparatorlist);
  }
  private static <K, V> void sortEntries(
      List<Entry<K, V>> entriesfinal Comparator<? super K> comparator) {
    Comparator<Entry<K, V>> entryComparator = new Comparator<Entry<K, V>>() {
      @Override public int compare(Entry<K, V> entry1Entry<K, V> entry2) {
        return comparator.compare(entry1.getKey(), entry2.getKey());
      }
    };
    Collections.sort(entriesentryComparator);
  }
  private static <K, V> void validateEntries(List<Entry<K, V>> entries,
      Comparator<? super K> comparator) {
    for (int i = 1; i < entries.size(); i++) {
      if (comparator.compare(
          entries.get(i - 1).getKey(), entries.get(i).getKey()) == 0) {
        throw new IllegalArgumentException(
            "Duplicate keys in mappings " + entries.get(i - 1) + " and "
                + entries.get(i));
      }
    }
  }

  
Returns a builder that creates immutable sorted maps whose keys are ordered by their natural ordering. The sorted maps use Ordering.natural() as the comparator.

Note: the type parameter K extends Comparable<K> rather than Comparable<? super K> as a workaround for javac bug 6468354.

  public static <K extends Comparable<K>, V> Builder<K, V> naturalOrder() {
    return new Builder<K, V>(Ordering.natural());
  }

  
Returns a builder that creates immutable sorted maps with an explicit comparator. If the comparator has a more general type than the map's keys, such as creating a SortedMap<Integer, String> with a Comparator<Number>, use the Builder constructor instead.

Throws:
NullPointerException if comparator is null
  public static <K, V> Builder<K, V> orderedBy(Comparator<K> comparator) {
    return new Builder<K, V>(comparator);
  }

  
Returns a builder that creates immutable sorted maps whose keys are ordered by the reverse of their natural ordering.

Note: the type parameter K extends Comparable<K> rather than Comparable<? super K> as a workaround for javac bug 6468354.

  public static <K extends Comparable<K>, V> Builder<K, V> reverseOrder() {
    return new Builder<K, V>(Ordering.natural().reverse());
  }

  
A builder for creating immutable sorted map instances, especially public static final maps ("constant maps"). Example:
   static final ImmutableSortedMap<Integer, String> INT_TO_WORD =
       new ImmutableSortedMap.Builder<Integer, String>(Ordering.natural())
           .put(1, "one")
           .put(2, "two")
           .put(3, "three")
           .build();
For small immutable sorted maps, the ImmutableSortedMap.of() methods are even more convenient.

Builder instances can be reused - it is safe to call build multiple times to build multiple maps in series. Each map is a superset of the maps created before it.

Since:
2.0 (imported from Google Collections Library)
  public static class Builder<K, V> extends ImmutableMap.Builder<K, V> {
    private final Comparator<? super K> comparator;

    
Creates a new builder. The returned builder is equivalent to the builder generated by ImmutableSortedMap.orderedBy.
    public Builder(Comparator<? super K> comparator) {
      this. = checkNotNull(comparator);
    }

    
Associates key with value in the built map. Duplicate keys, according to the comparator (which might be the keys' natural order), are not allowed, and will cause build to fail.
    @Override public Builder<K, V> put(K key, V value) {
      .add(entryOf(keyvalue));
      return this;
    }

    
Adds the given entry to the map, making it immutable if necessary. Duplicate keys, according to the comparator (which might be the keys' natural order), are not allowed, and will cause build to fail.

Since:
11.0
    @Override public Builder<K, V> put(Entry<? extends K, ? extends V> entry) {
      super.put(entry);
      return this;
    }

    
Associates all of the given map's keys and values in the built map. Duplicate keys, according to the comparator (which might be the keys' natural order), are not allowed, and will cause build to fail.

Throws:
NullPointerException if any key or value in map is null
    @Override public Builder<K, V> putAll(Map<? extends K, ? extends V> map) {
      for (Entry<? extends K, ? extends V> entry : map.entrySet()) {
        put(entry.getKey(), entry.getValue());
      }
      return this;
    }

    
Returns a newly-created immutable sorted map.

Throws:
IllegalArgumentException if any two keys are equal according to the comparator (which might be the keys' natural order)
    @Override public ImmutableSortedMap<K, V> build() {
      return fromSortedEntries();
    }
  }
  }
  ImmutableSortedMap(ImmutableSortedMap<K, V> descendingMap) {
    this. = descendingMap;
  }
  public int size() {
    return values().size();
  }
  @Override public boolean containsValue(@Nullable Object value) {
    return values().contains(value);
  }
  @Override boolean isPartialView() {
    return keySet().isPartialView() || values().isPartialView();
  }

  
Returns an immutable set of the mappings in this map, sorted by the key ordering.
  @Override public ImmutableSet<Entry<K, V>> entrySet() {
    return super.entrySet();
  }

  
Returns an immutable sorted set of the keys in this map.
  @Override public abstract ImmutableSortedSet<K> keySet();

  
Returns an immutable collection of the values in this map, sorted by the ordering of the corresponding keys.
  @Override public abstract ImmutableCollection<V> values();

  
Returns the comparator that orders the keys, which is Ordering.natural() when the natural ordering of the keys is used. Note that its behavior is not consistent with TreeMap.comparator(), which returns null to indicate natural ordering.
  public Comparator<? super K> comparator() {
    return keySet().comparator();
  }
  public K firstKey() {
    return keySet().first();
  }
  public K lastKey() {
    return keySet().last();
  }

  
This method returns a ImmutableSortedMap, consisting of the entries whose keys are less than toKey.

The SortedMap.headMap documentation states that a submap of a submap throws an IllegalArgumentException if passed a toKey greater than an earlier toKey. However, this method doesn't throw an exception in that situation, but instead keeps the original toKey.

  public ImmutableSortedMap<K, V> headMap(K toKey) {
    return headMap(toKeyfalse);
  }

  
This method returns a ImmutableSortedMap, consisting of the entries whose keys are less than (or equal to, if inclusive) toKey.

The SortedMap.headMap documentation states that a submap of a submap throws an IllegalArgumentException if passed a toKey greater than an earlier toKey. However, this method doesn't throw an exception in that situation, but instead keeps the original toKey.

Since:
12.0
  public abstract ImmutableSortedMap<K, V> headMap(K toKeyboolean inclusive);

  
This method returns a ImmutableSortedMap, consisting of the entries whose keys ranges from fromKey, inclusive, to toKey, exclusive.

The SortedMap.subMap documentation states that a submap of a submap throws an IllegalArgumentException if passed a fromKey less than an earlier fromKey. However, this method doesn't throw an exception in that situation, but instead keeps the original fromKey. Similarly, this method keeps the original toKey, instead of throwing an exception, if passed a toKey greater than an earlier toKey.

  public ImmutableSortedMap<K, V> subMap(K fromKey, K toKey) {
    return subMap(fromKeytruetoKeyfalse);
  }

  
This method returns a ImmutableSortedMap, consisting of the entries whose keys ranges from fromKey to toKey, inclusive or exclusive as indicated by the boolean flags.

The SortedMap.subMap documentation states that a submap of a submap throws an IllegalArgumentException if passed a fromKey less than an earlier fromKey. However, this method doesn't throw an exception in that situation, but instead keeps the original fromKey. Similarly, this method keeps the original toKey, instead of throwing an exception, if passed a toKey greater than an earlier toKey.

Since:
12.0
  public ImmutableSortedMap<K, V> subMap(K fromKeyboolean fromInclusive, K toKey,
      boolean toInclusive) {
    checkNotNull(fromKey);
    checkNotNull(toKey);
    checkArgument(comparator().compare(fromKeytoKey) <= 0,
        "expected fromKey <= toKey but %s > %s"fromKeytoKey);
    return headMap(toKeytoInclusive).tailMap(fromKeyfromInclusive);
  }

  
This method returns a ImmutableSortedMap, consisting of the entries whose keys are greater than or equals to fromKey.

The SortedMap.tailMap documentation states that a submap of a submap throws an IllegalArgumentException if passed a fromKey less than an earlier fromKey. However, this method doesn't throw an exception in that situation, but instead keeps the original fromKey.

  public ImmutableSortedMap<K, V> tailMap(K fromKey) {
    return tailMap(fromKeytrue);
  }

  
This method returns a ImmutableSortedMap, consisting of the entries whose keys are greater than (or equal to, if inclusive) fromKey.

The SortedMap.tailMap documentation states that a submap of a submap throws an IllegalArgumentException if passed a fromKey less than an earlier fromKey. However, this method doesn't throw an exception in that situation, but instead keeps the original fromKey.

Since:
12.0
  public abstract ImmutableSortedMap<K, V> tailMap(K fromKeyboolean inclusive);
  public Entry<K, V> lowerEntry(K key) {
    return headMap(keyfalse).lastEntry();
  }
  public K lowerKey(K key) {
    return keyOrNull(lowerEntry(key));
  }
  public Entry<K, V> floorEntry(K key) {
    return headMap(keytrue).lastEntry();
  }
  public K floorKey(K key) {
    return keyOrNull(floorEntry(key));
  }
  public Entry<K, V> ceilingEntry(K key) {
    return tailMap(keytrue).firstEntry();
  }
  public K ceilingKey(K key) {
    return keyOrNull(ceilingEntry(key));
  }
  public Entry<K, V> higherEntry(K key) {
    return tailMap(keyfalse).firstEntry();
  }
  public K higherKey(K key) {
    return keyOrNull(higherEntry(key));
  }
  public Entry<K, V> firstEntry() {
    return isEmpty() ? null : entrySet().asList().get(0);
  }
  public Entry<K, V> lastEntry() {
    return isEmpty() ? null : entrySet().asList().get(size() - 1);
  }
  public final Entry<K, V> pollFirstEntry() {
    throw new UnsupportedOperationException();
  }
  public final Entry<K, V> pollLastEntry() {
    throw new UnsupportedOperationException();
  }
  private transient ImmutableSortedMap<K, V> descendingMap;
  public ImmutableSortedMap<K, V> descendingMap() {
    ImmutableSortedMap<K, V> result = ;
    if (result == null) {
      result =  = createDescendingMap();
    }
    return result;
  }
    return keySet();
  }
    return keySet().descendingSet();
  }

  
Serialized type for all ImmutableSortedMap instances. It captures the logical contents and they are reconstructed using public factory methods. This ensures that the implementation types remain as implementation details.
  private static class SerializedForm extends ImmutableMap.SerializedForm {
    private final Comparator<Objectcomparator;
    @SuppressWarnings("unchecked")
    SerializedForm(ImmutableSortedMap<?, ?> sortedMap) {
      super(sortedMap);
       = (Comparator<Object>) sortedMap.comparator();
    }
      Builder<ObjectObjectbuilder = new Builder<ObjectObject>();
      return createMap(builder);
    }
    private static final long serialVersionUID = 0;
  }
    return new SerializedForm(this);
  }
  // This class is never actually serialized directly, but we have to make the
  // warning go away (and suppressing would suppress for all nested classes too)
  private static final long serialVersionUID = 0;
New to GrepCode? Check out our FAQ X