UnmodifiableSortedMap.java
/*
* Copyright (C) 2018 Stein Eldar Johnsen
*
* 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 net.morimekta.collect;
import net.morimekta.collect.collectors.UnmodifiableSortedMapCollector;
import java.util.AbstractMap;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Map;
import java.util.NavigableMap;
import java.util.NavigableSet;
import java.util.NoSuchElementException;
import java.util.Set;
import java.util.SortedMap;
import java.util.function.Function;
import java.util.stream.Collector;
import static java.lang.Math.max;
import static java.util.Objects.requireNonNull;
/**
* A shallow unmodifiable sorted map. Sorting will be done on instance creation.
*
* @param <K> The map key type.
* @param <V> The map value type.
*/
@SuppressWarnings("JdkObsolete")
public final class UnmodifiableSortedMap<K, V>
extends UnmodifiableMapBase<K, V>
implements SortedMap<K, V>, NavigableMap<K, V> {
// -------- Collectors --------
/**
* @param toKey Function to map entry to key.
* @param <K> The map key type.
* @param <V> The map value type.
* @return The sorted map collector.
*/
public static <K extends Comparable<K>, V>
Collector<V, ?, UnmodifiableSortedMap<K, V>>
toSortedMap(Function<V, K> toKey) {
return new UnmodifiableSortedMapCollector<>(toKey, v -> v, null);
}
/**
* @param toKey Function to map entry to key.
* @param toValue Function to map entry to value.
* @param <K> The map key type.
* @param <V> The map value type.
* @param <E> The stream entry type.
* @return The sorted map collector.
*/
public static <K extends Comparable<K>, V, E>
Collector<E, ?, UnmodifiableSortedMap<K, V>>
toSortedMap(Function<E, K> toKey, Function<E, V> toValue) {
return new UnmodifiableSortedMapCollector<>(toKey, toValue, null);
}
/**
* @param toKey Function to map entry to key.
* @param comparator Key comparator to sort map by.
* @param <K> The map key type.
* @param <V> The map value type.
* @return The sorted map collector.
*/
public static <K, V> Collector<V, ?, UnmodifiableSortedMap<K, V>>
toSortedMap(Function<V, K> toKey, Comparator<? super K> comparator) {
return new UnmodifiableSortedMapCollector<>(toKey, v -> v, comparator);
}
/**
* @param toKey Function to map entry to key.
* @param toValue Function to map entry to value.
* @param comparator Key comparator to sort map by.
* @param <K> The map key type.
* @param <V> The map value type.
* @param <E> The stream entry type.
* @return The sorted map collector.
*/
public static <K, V, E> Collector<E, ?, UnmodifiableSortedMap<K, V>>
toSortedMap(Function<E, K> toKey,
Function<E, V> toValue,
Comparator<? super K> comparator) {
return new UnmodifiableSortedMapCollector<>(toKey, toValue, comparator);
}
// -------- Constructors --------
/**
* @param map Map to make sorted map of.
* @param <K> The map key type.
* @param <V>The map value type.
* @return The unmodifiable sorted map.
*/
public static <K, V> UnmodifiableSortedMap<K, V> asSortedMap(Map<K, V> map) {
if (map.isEmpty() && !(map instanceof SortedMap)) {
return sortedMapOf();
}
if (map instanceof UnmodifiableSortedMap) {
return (UnmodifiableSortedMap<K, V>) map;
}
Comparator<? super K> comparator = null;
if (map instanceof SortedMap) {
comparator = ((SortedMap<K, V>) map).comparator();
}
UnmodifiableSortedMap.Builder<K, V> builder = new Builder<>(map.size(), comparator);
builder.putAll(map);
return builder.build();
}
/**
* @param <K> The map key type.
* @param <V> The map value type.
* @return The unmodifiable sorted empty map.
*/
@SuppressWarnings("unchecked")
public static <K, V> UnmodifiableSortedMap<K, V> sortedMapOf() {
return (UnmodifiableSortedMap<K, V>) EMPTY;
}
/**
* @param key The map entry key.
* @param value The map entry value.
* @param <K> The map key type.
* @param <V> The map values type.
* @return The unmodifiable sorted singleton map.
*/
public static <K, V> UnmodifiableSortedMap<K, V> sortedMapOf(K key, V value) {
return construct(entry(key, value));
}
/**
* @param k1 The first map entry key.
* @param v1 The first map entry value.
* @param k2 The second map entry key.
* @param v2 The second map entry value.
* @param <K> The map key type.
* @param <V> The map values type.
* @return The unmodifiable sorted map.
*/
public static <K, V> UnmodifiableSortedMap<K, V> sortedMapOf(K k1, V v1,
K k2, V v2) {
return construct(entry(k1, v1), entry(k2, v2));
}
/**
* @param k1 The first map entry key.
* @param v1 The first map entry value.
* @param k2 The second map entry key.
* @param v2 The second map entry value.
* @param k3 The third map entry key.
* @param v3 The third map entry value.
* @param <K> The map key type.
* @param <V> The map values type.
* @return The unmodifiable sorted map.
*/
public static <K, V> UnmodifiableSortedMap<K, V> sortedMapOf(K k1, V v1,
K k2, V v2,
K k3, V v3) {
return construct(entry(k1, v1), entry(k2, v2), entry(k3, v3));
}
/**
* @param k1 The first map entry key.
* @param v1 The first map entry value.
* @param k2 The second map entry key.
* @param v2 The second map entry value.
* @param k3 The third map entry key.
* @param v3 The third map entry value.
* @param k4 The fourth map entry key.
* @param v4 The fourth map entry value.
* @param <K> The map key type.
* @param <V> The map values type.
* @return The unmodifiable sorted map.
*/
public static <K, V> UnmodifiableSortedMap<K, V> sortedMapOf(K k1, V v1,
K k2, V v2,
K k3, V v3,
K k4, V v4) {
return construct(entry(k1, v1), entry(k2, v2), entry(k3, v3), entry(k4, v4));
}
/**
* @param k1 The first map entry key.
* @param v1 The first map entry value.
* @param k2 The second map entry key.
* @param v2 The second map entry value.
* @param k3 The third map entry key.
* @param v3 The third map entry value.
* @param k4 The fourth map entry key.
* @param v4 The fourth map entry value.
* @param k5 The fifth map entry key.
* @param v5 The fifth map entry value.
* @param <K> The map key type.
* @param <V> The map values type.
* @return The unmodifiable sorted map.
*/
public static <K, V> UnmodifiableSortedMap<K, V> sortedMapOf(K k1, V v1,
K k2, V v2,
K k3, V v3,
K k4, V v4,
K k5, V v5) {
return construct(entry(k1, v1), entry(k2, v2), entry(k3, v3), entry(k4, v4), entry(k5, v5));
}
/**
* @param k1 The first map entry key.
* @param v1 The first map entry value.
* @param k2 The second map entry key.
* @param v2 The second map entry value.
* @param k3 The third map entry key.
* @param v3 The third map entry value.
* @param k4 The fourth map entry key.
* @param v4 The fourth map entry value.
* @param k5 The fifth map entry key.
* @param v5 The fifth map entry value.
* @param k6 The sixth map entry key.
* @param v6 The sixth map entry value.
* @param <K> The map key type.
* @param <V> The map values type.
* @return The unmodifiable sorted map.
*/
public static <K, V> UnmodifiableSortedMap<K, V> sortedMapOf(K k1, V v1,
K k2, V v2,
K k3, V v3,
K k4, V v4,
K k5, V v5,
K k6, V v6) {
return construct(entry(k1, v1),
entry(k2, v2),
entry(k3, v3),
entry(k4, v4),
entry(k5, v5),
entry(k6, v6));
}
/**
* @param k1 The first map entry key.
* @param v1 The first map entry value.
* @param k2 The second map entry key.
* @param v2 The second map entry value.
* @param k3 The third map entry key.
* @param v3 The third map entry value.
* @param k4 The fourth map entry key.
* @param v4 The fourth map entry value.
* @param k5 The fifth map entry key.
* @param v5 The fifth map entry value.
* @param k6 The sixth map entry key.
* @param v6 The sixth map entry value.
* @param k7 The seventh map entry key.
* @param v7 The seventh map entry value.
* @param <K> The map key type.
* @param <V> The map values type.
* @return The unmodifiable sorted map.
*/
public static <K, V> UnmodifiableSortedMap<K, V> sortedMapOf(K k1, V v1,
K k2, V v2,
K k3, V v3,
K k4, V v4,
K k5, V v5,
K k6, V v6,
K k7, V v7) {
return construct(entry(k1, v1),
entry(k2, v2),
entry(k3, v3),
entry(k4, v4),
entry(k5, v5),
entry(k6, v6),
entry(k7, v7));
}
/**
* @param k1 The first map entry key.
* @param v1 The first map entry value.
* @param k2 The second map entry key.
* @param v2 The second map entry value.
* @param k3 The third map entry key.
* @param v3 The third map entry value.
* @param k4 The fourth map entry key.
* @param v4 The fourth map entry value.
* @param k5 The fifth map entry key.
* @param v5 The fifth map entry value.
* @param k6 The sixth map entry key.
* @param v6 The sixth map entry value.
* @param k7 The seventh map entry key.
* @param v7 The seventh map entry value.
* @param k8 The eighth map entry key.
* @param v8 The eighth map entry value.
* @param <K> The map key type.
* @param <V> The map values type.
* @return The unmodifiable sorted map.
*/
public static <K, V> UnmodifiableSortedMap<K, V> sortedMapOf(K k1, V v1,
K k2, V v2,
K k3, V v3,
K k4, V v4,
K k5, V v5,
K k6, V v6,
K k7, V v7,
K k8, V v8) {
return construct(entry(k1, v1),
entry(k2, v2),
entry(k3, v3),
entry(k4, v4),
entry(k5, v5),
entry(k6, v6),
entry(k7, v7),
entry(k8, v8));
}
/**
* @param k1 The first map entry key.
* @param v1 The first map entry value.
* @param k2 The second map entry key.
* @param v2 The second map entry value.
* @param k3 The third map entry key.
* @param v3 The third map entry value.
* @param k4 The fourth map entry key.
* @param v4 The fourth map entry value.
* @param k5 The fifth map entry key.
* @param v5 The fifth map entry value.
* @param k6 The sixth map entry key.
* @param v6 The sixth map entry value.
* @param k7 The seventh map entry key.
* @param v7 The seventh map entry value.
* @param k8 The eighth map entry key.
* @param v8 The eighth map entry value.
* @param k9 The ninth map entry key.
* @param v9 The ninth map entry value.
* @param <K> The map key type.
* @param <V> The map values type.
* @return The unmodifiable sorted map.
*/
public static <K, V> UnmodifiableSortedMap<K, V> sortedMapOf(K k1, V v1,
K k2, V v2,
K k3, V v3,
K k4, V v4,
K k5, V v5,
K k6, V v6,
K k7, V v7,
K k8, V v8,
K k9, V v9) {
return construct(entry(k1, v1),
entry(k2, v2),
entry(k3, v3),
entry(k4, v4),
entry(k5, v5),
entry(k6, v6),
entry(k7, v7),
entry(k8, v8),
entry(k9, v9));
}
/**
* @param k1 The first map entry key.
* @param v1 The first map entry value.
* @param k2 The second map entry key.
* @param v2 The second map entry value.
* @param k3 The third map entry key.
* @param v3 The third map entry value.
* @param k4 The fourth map entry key.
* @param v4 The fourth map entry value.
* @param k5 The fifth map entry key.
* @param v5 The fifth map entry value.
* @param k6 The sixth map entry key.
* @param v6 The sixth map entry value.
* @param k7 The seventh map entry key.
* @param v7 The seventh map entry value.
* @param k8 The eighth map entry key.
* @param v8 The eighth map entry value.
* @param k9 The ninth map entry key.
* @param v9 The ninth map entry value.
* @param k10 The tenth map entry key.
* @param v10 The tenth map entry value.
* @param <K> The map key type.
* @param <V> The map values type.
* @return The unmodifiable sorted map.
*/
public static <K, V> UnmodifiableSortedMap<K, V> sortedMapOf(K k1, V v1,
K k2, V v2,
K k3, V v3,
K k4, V v4,
K k5, V v5,
K k6, V v6,
K k7, V v7,
K k8, V v8,
K k9, V v9,
K k10, V v10) {
return construct(entry(k1, v1),
entry(k2, v2),
entry(k3, v3),
entry(k4, v4),
entry(k5, v5),
entry(k6, v6),
entry(k7, v7),
entry(k8, v8),
entry(k9, v9),
entry(k10, v10));
}
/**
* @param comparator Comparator to sort entries by.
* @param <K> The map key type.
* @param <V> The map value type.
* @return The sorted map builder.
*/
public static <K, V> Builder<K, V> newBuilderOrderedBy(Comparator<? super K> comparator) {
return new Builder<>(4, comparator);
}
/**
* @param initialCapacity Initial capacity of builder.
* @param comparator Comparator to sort entries by.
* @param <K> The map key type.
* @param <V> The map value type.
* @return The sorted map builder.
*/
public static <K, V> Builder<K, V> newBuilderOrderedBy(int initialCapacity, Comparator<? super K> comparator) {
return new Builder<>(max(1, initialCapacity), comparator);
}
/**
* @param <K> The map key type.
* @param <V> The map value type.
* @return The sorted map builder using natural order.
*/
public static <K extends Comparable<K>, V> Builder<K, V> newBuilderNaturalOrder() {
return new Builder<>(4, null);
}
/**
* @param initialCapacity Initial capacity of builder.
* @param <K> The map key type.
* @param <V> The map value type.
* @return The sorted map builder using natural order.
*/
public static <K extends Comparable<K>, V> Builder<K, V> newBuilderNaturalOrder(int initialCapacity) {
return new Builder<>(max(1, initialCapacity), null);
}
/**
* @param <K> The map key type.
* @param <V> The map value type.
* @return The sorted map builder using reverse order.
*/
public static <K extends Comparable<K>, V> Builder<K, V> newBuilderReverseOrder() {
return new Builder<>(4, Comparator.reverseOrder());
}
/**
* @param initialCapacity Initial capacity of builder.
* @param <K> The map key type.
* @param <V> The map value type.
* @return The sorted map builder using reverse order.
*/
public static <K extends Comparable<K>, V> Builder<K, V> newBuilderReverseOrder(int initialCapacity) {
return new Builder<>(max(1, initialCapacity), Comparator.reverseOrder());
}
// -------- Map --------
@Override
@SuppressWarnings("unchecked")
public boolean containsKey(Object o) {
return keySet().binarySearch((K) o) >= 0;
}
@Override
@SuppressWarnings("unchecked")
public V get(Object o) {
int index = keySet().binarySearch((K) o);
if (index >= 0) {
return entries[index].getValue();
}
return null;
}
// -------- SortedMap --------
@Override
public Comparator<? super K> comparator() {
return comparator;
}
@Override
public UnmodifiableSortedMap<K, V> subMap(K start, K end) {
return subMap(start, true, end, false);
}
@Override
public UnmodifiableSortedMap<K, V> headMap(K end) {
return headMap(end, false);
}
@Override
public UnmodifiableSortedMap<K, V> tailMap(K start) {
return tailMap(start, true);
}
@Override
public K firstKey() {
if (size == 0) {
throw new NoSuchElementException("size == 0");
}
return entries[0].getKey();
}
@Override
public K lastKey() {
if (size == 0) {
throw new NoSuchElementException("size == 0");
}
return entries[size - 1].getKey();
}
// -------- NavigableMap ---------
@Override
public Entry<K, V> firstEntry() {
if (size == 0) {
throw new NoSuchElementException("size == 0");
}
return entries[0];
}
@Override
public Entry<K, V> lastEntry() {
if (size == 0) {
throw new NoSuchElementException("size == 0");
}
return entries[size - 1];
}
@Override
public Entry<K, V> lowerEntry(K k) {
var li = keySet().lowerIndex(k);
if (li < 0) {
return null;
}
return entries[li];
}
@Override
public K lowerKey(K k) {
return keySet().lower(k);
}
@Override
public Entry<K, V> floorEntry(K k) {
var hi = keySet().floorIndex(k);
if (hi < 0) {
return null;
}
return entries[hi];
}
@Override
public K floorKey(K k) {
return keySet().floor(k);
}
@Override
public Entry<K, V> ceilingEntry(K k) {
var hi = keySet().ceilingIndex(k);
if (hi < 0) {
return null;
}
return entries[hi];
}
@Override
public K ceilingKey(K k) {
return keySet().ceiling(k);
}
@Override
public Entry<K, V> higherEntry(K k) {
var hi = keySet().higherIndex(k);
if (hi < 0) return null;
return entries[hi];
}
@Override
public K higherKey(K k) {
return keySet().higher(k);
}
@Override
public UnmodifiableSortedMap<K, V> descendingMap() {
Entry<K, V>[] newArray = makeEntryArray(size);
for (int i = 0; i < size; ++i) {
var o = size - i - 1;
newArray[o] = entries[i];
}
return new UnmodifiableSortedMap<>(size, newArray, comparator);
}
@Override
public UnmodifiableSortedSet<K> navigableKeySet() {
return keySet();
}
@Override
public UnmodifiableSortedSet<K> descendingKeySet() {
return keySet().descendingSet();
}
@Override
public UnmodifiableSortedMap<K, V> subMap(K start, boolean startInclusive, K end, boolean endInclusive) {
var si = startInclusive ? keySet().ceilingIndex(start) : keySet().higherIndex(start);
var ei = endInclusive ? keySet().floorIndex(end) : keySet().lowerIndex(end);
if (si < 0 || ei < 0) {
// TODO: Exception on si > ei?
return sortedMapOf();
} else if (si == 0 && ei == size - 1) {
return this;
} else if (si == 0) {
// if there is no offset, just reuse the array.
return new UnmodifiableSortedMap<>(ei + 1, entries, comparator);
}
var newSize = 1 + ei - si;
Entry<K, V>[] newArray = makeEntryArray(newSize);
System.arraycopy(entries, si, newArray, 0, newSize);
return new UnmodifiableSortedMap<>(newSize, newArray, comparator);
}
@Override
public UnmodifiableSortedMap<K, V> headMap(K end, boolean inclusive) {
int ei = inclusive ? keySet().floorIndex(end) : keySet().lowerIndex(end);
if (ei < 0) {
return sortedMapOf();
} else if (ei == size - 1) {
return this;
}
return new UnmodifiableSortedMap<>(
ei + 1, entries, comparator, entryComparator);
}
@Override
public UnmodifiableSortedMap<K, V> tailMap(K start, boolean inclusive) {
var si = inclusive ? keySet().ceilingIndex(start) : keySet().higherIndex(start);
if (si < 0) {
return sortedMapOf();
} else if (si == 0) {
return this;
}
var newSize = size - si;
Entry<K, V>[] newArray = makeEntryArray(newSize);
System.arraycopy(entries, si, newArray, 0, newSize);
return new UnmodifiableSortedMap<>(newSize, newArray, comparator);
}
public Entry<K, V> pollFirstEntry() {
throw new UnsupportedOperationException("Modifying unmodifiable map not allowed");
}
public Entry<K, V> pollLastEntry() {
throw new UnsupportedOperationException("Modifying unmodifiable map not allowed");
}
// -------- UnmodifiableMapBase --------
@Override
public UnmodifiableSortedSet<K> keySet() {
return (UnmodifiableSortedSet<K>) super.keySet();
}
@Override
public UnmodifiableSortedMap<K, V> withEntry(K key, V value) {
requireNonNull(key, "key == null");
requireNonNull(value, "value == null");
if (isEmpty()) {
if (comparator != null) {
return UnmodifiableSortedMap.<K, V>newBuilderOrderedBy(1, comparator)
.put(key, value)
.build();
}
return sortedMapOf(key, value);
}
return new UnmodifiableSortedMap.Builder<K, V>(size + 1, comparator)
.putAll(this)
.put(key, value)
.build();
}
@Override
@SuppressWarnings("unchecked")
public UnmodifiableSortedMap<K, V> withEntries(Map<? extends K, ? extends V> map) {
requireNonNull(map, "map == null");
if (map.isEmpty()) {
return this;
}
if (isEmpty()) {
if (comparator != null) {
return UnmodifiableSortedMap.<K, V>newBuilderOrderedBy(map.size(), comparator)
.putAll(map)
.build();
}
return asSortedMap((Map<K, V>) map);
}
return new UnmodifiableSortedMap.Builder<K, V>(size + map.size(), comparator)
.putAll(this)
.putAll(map)
.build();
}
// -------- Builder --------
/**
* A builder for making unmodifiable sorted map.
*
* @param <K> The map key type.
* @param <V> The map value type.
*/
public final static class Builder<K, V>
extends UnmodifiableMapBuilder<K, V, UnmodifiableSortedMap<K, V>, Builder<K, V>>
implements MapBuilder<K, V> {
private Entry<K, V>[] array;
private int size;
private UnmodifiableSortedMap<K, V> justBuilt;
private final Comparator<K> comparator;
private final Comparator<Entry<K, V>> entryComparator;
@SuppressWarnings("unchecked,rawtypes")
Builder(int initialCapacity, Comparator comparator) {
this.array = makeEntryArray(initialCapacity);
this.size = 0;
this.comparator = comparator;
this.entryComparator = makeEntryComparator(comparator);
this.justBuilt = null;
}
@Override
public Builder<K, V> put(K key, V value) {
ensureCapacity(size + 1);
array[size++] = new AbstractMap.SimpleImmutableEntry<>(key, value);
return this;
}
@Override
@SuppressWarnings("unchecked,rawtypes")
public Builder<K, V> putAll(Map<? extends K, ? extends V> map) {
if (map.isEmpty()) {
return this;
}
ensureCapacity(size + map.size());
if (map instanceof UnmodifiableMapBase) {
UnmodifiableMapBase<? extends K, ? extends V> base = (UnmodifiableMapBase<? extends K, ? extends V>) map;
for (int i = 0; i < base.size; ++i) {
array[size++] = (Entry) base.entries[i];
}
} else {
for (Entry<? extends K, ? extends V> entry : map.entrySet()) {
array[size++] = new AbstractMap.SimpleImmutableEntry<>(entry.getKey(), entry.getValue());
}
}
return this;
}
@Override
public UnmodifiableSortedMap<K, V> build() {
if (size == 0 && comparator == null) {
return sortedMapOf();
}
if (justBuilt != null) {
return justBuilt;
}
makeSorted(1);
justBuilt = new UnmodifiableSortedMap<>(size, array, comparator, entryComparator);
return justBuilt;
}
@SuppressWarnings("unchecked")
private void makeSorted(int minSize) {
if (size == 0) {
return;
}
// A: Sort
Arrays.sort(array, 0, size, entryComparator);
// B: Deduplicate
final int originalSize = size;
for (int i = 1; i < originalSize; ++i) {
if (array[i].getKey().equals(array[i - 1].getKey())) {
// The last entry is kept.
array[i - 1] = null;
--size;
}
}
// C: compact away null values.
if (size < originalSize) {
if (array.length - max(size, minSize) > 1024) {
// In order to save memory, minimize larger arrays.
@SuppressWarnings("rawtypes")
Entry[] compact = makeEntryArray(max(minSize, size));
int pos = 0;
for (int i = 0; i < originalSize; ++i) {
@SuppressWarnings("rawtypes")
Entry o = array[i];
if (o != null) {
compact[pos++] = o;
}
}
array = compact;
} else {
for (int moveTo = 0, moveFrom = 1;
moveTo < size && moveFrom < originalSize;
++moveTo, ++moveFrom) {
if (array[moveTo] == null) {
while (array[moveFrom] == null) {
++moveFrom;
}
array[moveTo] = array[moveFrom];
array[moveFrom] = null;
}
}
}
}
}
@SuppressWarnings("unchecked")
private void ensureCapacity(int newSize) {
if (array.length < newSize) {
@SuppressWarnings("rawtypes")
Entry[] old = array;
array = makeEntryArray(old.length * 2);
System.arraycopy(old, 0, array, 0, size);
makeSorted(newSize);
} else if (justBuilt != null) {
@SuppressWarnings("rawtypes")
Entry[] old = array;
array = makeEntryArray(old.length);
System.arraycopy(old, 0, array, 0, size);
// Already sorted.
}
justBuilt = null;
}
}
// -------- UnmodifiableMapBase : Protected --------
@Override
protected Set<Entry<K, V>> makeEntrySet() {
if (size == 0) {
return UnmodifiableSortedSet.sortedSetOf();
}
return new UnmodifiableSortedSet<>(0, size, entries, entryComparator);
}
@Override
protected Set<K> makeKeySet() {
if (size == 0) {
return UnmodifiableSortedSet.sortedSetOf();
}
Object[] keys = new Object[size];
for (int i = 0; i < size; ++i) {
keys[i] = entries[i].getKey();
}
return new UnmodifiableSortedSet<>(0, size, keys, comparator);
}
// -------- Private --------
private UnmodifiableSortedMap(int size, Entry<K, V>[] entries, Comparator<? super K> comparator) {
this(size, entries, comparator, makeEntryComparator(comparator));
}
UnmodifiableSortedMap(int size,
Entry<K, V>[] entries,
Comparator<? super K> comparator,
Comparator<Entry<K, V>> entryComparator) {
super(size, entries);
this.comparator = comparator;
this.entryComparator = entryComparator;
}
@SafeVarargs
private static <K, V> UnmodifiableSortedMap<K, V> construct(Entry<K, V>... entries) {
Comparator<Entry<K, V>> entryComparator = makeEntryComparator(null);
Arrays.sort(entries, entryComparator);
return new UnmodifiableSortedMap<>(entries.length, entries, null, entryComparator);
}
static <K, V> Comparator<Entry<K, V>> makeEntryComparator(Comparator<? super K> comparator) {
@SuppressWarnings("unchecked")
Comparator<Entry<K, V>> base = comparator == null ?
Entry.comparingByKey((Comparator<K>) Comparator.naturalOrder()) :
Entry.comparingByKey(comparator);
// This should make it sort null values before non-null.
// This is used to get the correct binary search behavior based on null values in search key.
return base.thenComparing(e -> e.getValue() != null);
}
private static final UnmodifiableSortedMap<Object, Object> EMPTY = new UnmodifiableSortedMap<>(
0, NO_ENTRIES, null);
private final transient Comparator<? super K> comparator;
private final transient Comparator<Entry<K, V>> entryComparator;
}