UnmodifiableSortedSet.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.UnmodifiableSortedSetCollector;
import java.util.Arrays;
import java.util.Collection;
import java.util.Comparator;
import java.util.Enumeration;
import java.util.Iterator;
import java.util.NavigableSet;
import java.util.NoSuchElementException;
import java.util.Objects;
import java.util.Set;
import java.util.SortedSet;
import java.util.function.Predicate;
import java.util.stream.Collector;
import static java.lang.Math.max;
import static java.util.Objects.requireNonNull;
/**
* A shallow unmodifiable sorted set. The sorting is always done on instance
* creation.
*
* @param <E> The set item type.
*/
public final class UnmodifiableSortedSet<E>
extends UnmodifiableCollection<E>
implements NavigableSet<E> {
// -------- Collectors --------
/**
* @param <T> The set item type.
* @return Collector to make a sorted set with default sorting.
*/
public static <T> Collector<T, ?, UnmodifiableSortedSet<T>> toSortedSet() {
return new UnmodifiableSortedSetCollector<>(null);
}
/**
* @param comparator Comparator to sort set with.
* @param <T> The set item type.
* @return Collector to make a sorted set with specific sorting.
*/
public static <T> Collector<T, ?, UnmodifiableSortedSet<T>> toSortedSet(Comparator<? super T> comparator) {
return new UnmodifiableSortedSetCollector<>(comparator);
}
// -------- Constructor --------
/**
* @param comparator Comparator to sort set with.
* @param values Values to make set of.
* @param <E> The set item type.
* @return The unmodifiable sorted set.
*/
@SafeVarargs
@SuppressWarnings("unchecked,varargs")
public static <E> UnmodifiableSortedSet<E> asSortedSetOrderedBy(Comparator<? super E> comparator, E... values) {
checkNotNull(values);
if (values.length == 0 && comparator == null) {
return sortedSetOf();
}
Object[] copy = Arrays.copyOf(values, values.length);
return construct((Comparator<Object>) comparator, copy);
}
/**
* @param values Values to make set of.
* @param <E> The set item type.
* @return The unmodifiable sorted set.
*/
@SafeVarargs
@SuppressWarnings("varargs")
public static <E> UnmodifiableSortedSet<E> asSortedSet(E... values) {
checkNotNull(values);
if (values.length == 0) {
return sortedSetOf();
}
Object[] copy = Arrays.copyOf(values, values.length);
return construct(null, copy);
}
/**
* @param iterable Iterable to make sorted set of.
* @param <E> The set item type.
* @return The unmodifiable sorted set.
*/
@SuppressWarnings("unchecked")
public static <E> UnmodifiableSortedSet<E> asSortedSet(Iterable<? extends E> iterable) {
if (iterable instanceof Collection) {
return asSortedSet((Collection<E>) iterable);
}
return asSortedSet(iterable.iterator());
}
/**
* @param iterator Iterator to make sorted set of.
* @param <E> The set item type.
* @return The unmodifiable sorted set.
*/
public static <E> UnmodifiableSortedSet<E> asSortedSet(Iterator<? extends E> iterator) {
if (!iterator.hasNext()) {
return sortedSetOf();
}
return UnmodifiableSortedSet.<E>newBuilderOrderedBy(null).addAll(iterator).build();
}
/**
* @param enumeration Enumeration to make sorted set of.
* @param <E> The set item type.
* @return The unmodifiable sorted set.
*/
public static <E extends Comparable<E>> UnmodifiableSortedSet<E> asSortedSet(Enumeration<? extends E> enumeration) {
if (!enumeration.hasMoreElements()) {
return sortedSetOf();
}
return UnmodifiableSortedSet.<E>newBuilderNaturalOrder().addAll(enumeration).build();
}
/**
* @param collection Collection to make sorted set of.
* @param <E> The set item type.
* @return The unmodifiable sorted set.
*/
@SuppressWarnings("unchecked")
public static <E> UnmodifiableSortedSet<E> asSortedSet(Collection<? extends E> collection) {
checkNotNull(collection);
if (collection instanceof UnmodifiableSortedSet) {
return (UnmodifiableSortedSet<E>) collection;
}
if (collection instanceof Set && !(collection instanceof SortedSet)) {
Object[] array = collection.toArray();
Arrays.sort(array);
return new UnmodifiableSortedSet<>(0, array.length, array, null);
}
Comparator<? super E> comparator = null;
if (collection instanceof SortedSet) {
comparator = ((SortedSet<E>) collection).comparator();
}
if (collection.isEmpty()) {
return UnmodifiableSortedSet.<E>newBuilderOrderedBy(comparator).build();
}
if (collection instanceof Set) {
Object[] array = collection.toArray();
Arrays.sort((E[]) array, comparator);
return new UnmodifiableSortedSet<>(0, array.length, array, comparator);
}
return construct(null, collection.toArray());
}
/**
* @param <E> The set item type.
* @return The unmodifiable sorted empty set.
*/
@SuppressWarnings("unchecked")
public static <E> UnmodifiableSortedSet<E> sortedSetOf() {
return (UnmodifiableSortedSet<E>) EMPTY;
}
/**
* @param e The item to make sorted singleton set of.
* @param <E> The set item type.
* @return The unmodifiable singleton sorted set.
*/
public static <E> UnmodifiableSortedSet<E> sortedSetOf(E e) {
return construct(null, e);
}
/**
* @param e1 The first item in the sorted set.
* @param e2 The second item in the sorted set.
* @param <E> The set item type.
* @return The unmodifiable sorted set.
*/
public static <E> UnmodifiableSortedSet<E> sortedSetOf(E e1, E e2) {
return construct(null, e1, e2);
}
/**
* @param e1 The first item in the sorted set.
* @param e2 The second item in the sorted set.
* @param e3 The third item in the sorted set.
* @param <E> The set item type.
* @return The unmodifiable sorted set.
*/
public static <E> UnmodifiableSortedSet<E> sortedSetOf(E e1, E e2, E e3) {
return construct(null, e1, e2, e3);
}
/**
* @param e1 The first item in the sorted set.
* @param e2 The second item in the sorted set.
* @param e3 The third item in the sorted set.
* @param e4 The fourth item in the sorted set.
* @param <E> The set item type.
* @return The unmodifiable sorted set.
*/
public static <E> UnmodifiableSortedSet<E> sortedSetOf(E e1, E e2, E e3, E e4) {
return construct(null, e1, e2, e3, e4);
}
/**
* @param e1 The first item in the sorted set.
* @param e2 The second item in the sorted set.
* @param e3 The third item in the sorted set.
* @param e4 The fourth item in the sorted set.
* @param e5 The fifth item in the sorted set.
* @param <E> The set item type.
* @return The unmodifiable sorted set.
*/
public static <E> UnmodifiableSortedSet<E> sortedSetOf(E e1, E e2, E e3, E e4, E e5) {
return construct(null, e1, e2, e3, e4, e5);
}
/**
* @param e1 The first item in the sorted set.
* @param e2 The second item in the sorted set.
* @param e3 The third item in the sorted set.
* @param e4 The fourth item in the sorted set.
* @param e5 The fifth item in the sorted set.
* @param e6 The sixth item in the sorted set.
* @param <E> The set item type.
* @return The unmodifiable sorted set.
*/
public static <E> UnmodifiableSortedSet<E> sortedSetOf(E e1, E e2, E e3, E e4, E e5, E e6) {
return construct(null, e1, e2, e3, e4, e5, e6);
}
/**
* @param e1 The first item in the sorted set.
* @param e2 The second item in the sorted set.
* @param e3 The third item in the sorted set.
* @param e4 The fourth item in the sorted set.
* @param e5 The fifth item in the sorted set.
* @param e6 The sixth item in the sorted set.
* @param e7 The seventh item in the sorted set.
* @param <E> The set item type.
* @return The unmodifiable sorted set.
*/
public static <E> UnmodifiableSortedSet<E> sortedSetOf(E e1, E e2, E e3, E e4, E e5, E e6, E e7) {
return construct(null, e1, e2, e3, e4, e5, e6, e7);
}
/**
* @param e1 The first item in the sorted set.
* @param e2 The second item in the sorted set.
* @param e3 The third item in the sorted set.
* @param e4 The fourth item in the sorted set.
* @param e5 The fifth item in the sorted set.
* @param e6 The sixth item in the sorted set.
* @param e7 The seventh item in the sorted set.
* @param e8 The eighth item in the sorted set.
* @param <E> The set item type.
* @return The unmodifiable sorted set.
*/
public static <E> UnmodifiableSortedSet<E> sortedSetOf(E e1, E e2, E e3, E e4, E e5, E e6, E e7, E e8) {
return construct(null, e1, e2, e3, e4, e5, e6, e7, e8);
}
/**
* @param e1 The first item in the sorted set.
* @param e2 The second item in the sorted set.
* @param e3 The third item in the sorted set.
* @param e4 The fourth item in the sorted set.
* @param e5 The fifth item in the sorted set.
* @param e6 The sixth item in the sorted set.
* @param e7 The seventh item in the sorted set.
* @param e8 The eighth item in the sorted set.
* @param e9 The ninth item in the sorted set.
* @param <E> The set item type.
* @return The unmodifiable sorted set.
*/
public static <E> UnmodifiableSortedSet<E> sortedSetOf(E e1, E e2, E e3, E e4, E e5, E e6, E e7, E e8, E e9) {
return construct(null, e1, e2, e3, e4, e5, e6, e7, e8, e9);
}
/**
* @param e1 The first item in the sorted set.
* @param e2 The second item in the sorted set.
* @param e3 The third item in the sorted set.
* @param e4 The fourth item in the sorted set.
* @param e5 The fifth item in the sorted set.
* @param e6 The sixth item in the sorted set.
* @param e7 The seventh item in the sorted set.
* @param e8 The eighth item in the sorted set.
* @param e9 The ninth item in the sorted set.
* @param e10 The tenth item in the sorted set.
* @param more More items in the sorted set.
* @param <E> The set item type.
* @return The unmodifiable sorted set.
*/
@SafeVarargs
@SuppressWarnings("varargs")
public static <E> UnmodifiableSortedSet<E> sortedSetOf(E e1,
E e2,
E e3,
E e4,
E e5,
E e6,
E e7,
E e8,
E e9,
E e10,
E... more) {
Object[] array = new Object[10 + more.length];
array[0] = e1;
array[1] = e2;
array[2] = e3;
array[3] = e4;
array[4] = e5;
array[5] = e6;
array[6] = e7;
array[7] = e8;
array[8] = e9;
array[9] = e10;
System.arraycopy(more, 0, array, 10, more.length);
return construct(null, array);
}
/**
* @param comparator Comparator to sort set by.
* @param <E> The set item type.
* @return The sorted set builder.
*/
public static <E> Builder<E> newBuilderOrderedBy(Comparator<? super E> comparator) {
return newBuilderOrderedBy(4, comparator);
}
/**
* @param initialCapacity Initial capacity of builder.
* @param comparator Comparator to sort set by.
* @param <E> The set item type.
* @return The sorted set builder.
*/
public static <E> Builder<E> newBuilderOrderedBy(int initialCapacity, Comparator<? super E> comparator) {
return new Builder<>(initialCapacity, comparator);
}
/**
* @param <E> The set item type.
* @return The sorted set builder using natural order.
*/
public static <E extends Comparable<E>> Builder<E> newBuilderNaturalOrder() {
return new Builder<>(4, null);
}
/**
* @param initialCapacity Initial capacity of builder.
* @param <E> The set item type.
* @return The sorted set builder using natural order.
*/
public static <E extends Comparable<E>> Builder<E> newBuilderNaturalOrder(int initialCapacity) {
return new Builder<>(max(1, initialCapacity), null);
}
/**
* @param <E> The set item type.
* @return The sorted set builder using reverse order.
*/
public static <E extends Comparable<E>> Builder<E> newBuilderReverseOrder() {
return new Builder<>(4, Comparator.reverseOrder());
}
/**
* @param initialCapacity Initial capacity of builder.
* @param <E> The set item type.
* @return The sorted set builder using reverse order.
*/
public static <E extends Comparable<E>> Builder<E> newBuilderReverseOrder(int initialCapacity) {
return new Builder<>(max(1, initialCapacity), Comparator.reverseOrder());
}
// -------- Object --------
@Override
@SuppressWarnings("rawtypes")
public boolean equals(Object obj) {
if (obj == this) {
return true;
}
if (!(obj instanceof Set)) {
return false;
}
Set other = (Set) obj;
if (other.size() != length) {
return false;
}
for (Object o : (Set) obj) {
if (!contains(o)) {
return false;
}
}
return true;
}
@Override
public String toString() {
StringBuilder builder = new StringBuilder("{");
for (int i = offset; i < (offset + length); ++i) {
if (i > offset) {
builder.append(", ");
}
builder.append(array[i].toString());
}
return builder.append("}").toString();
}
@Override
public int hashCode() {
if (hashCode == null) {
int hash = Objects.hash(getClass(), length);
for (int i = offset; i < (offset + length); ++i) {
hash ^= Objects.hash(array[i]);
}
hashCode = hash;
}
return hashCode;
}
// -------- Collection --------
@Override
@SuppressWarnings("unchecked")
public boolean contains(Object o) {
if (length == 0) {
return false;
}
return binarySearch((E) o) >= 0;
}
// -------- NavigableSet --------
@Override
@SuppressWarnings("unchecked")
public E lower(E of) {
var si = lowerIndex(of);
if (si < 0) return null;
return (E) array[si];
}
@Override
@SuppressWarnings("unchecked")
public E floor(E of) {
var si = floorIndex(of);
if (si < 0) return null;
return (E) array[si];
}
@Override
@SuppressWarnings("unchecked")
public E ceiling(E e) {
var i = ceilingIndex(e);
if (i < 0) return null;
return (E) array[i];
}
@Override
@SuppressWarnings("unchecked")
public E higher(E e) {
var i = higherIndex(e);
if (i < 0) return null;
return (E) array[i];
}
@Override
public UnmodifiableSortedSet<E> descendingSet() {
return reversed();
}
@Override
public Iterator<E> descendingIterator() {
return reversed().iterator();
}
@Override
public UnmodifiableSortedSet<E> subSet(E start, boolean startInclusive, E end, boolean endInclusive) {
var si = startInclusive ? ceilingIndex(start) : higherIndex(start);
var ei = endInclusive ? floorIndex(end) : lowerIndex(end);
if (si < 0 || ei < 0) {
// TODO: Exception on si > ei?
return sortedSetOf();
} else if (si == offset && ei == offset + length - 1) {
return this;
}
var len = 1 + ei - si;
return new UnmodifiableSortedSet<>(si, len, array, comparator);
}
@Override
public UnmodifiableSortedSet<E> headSet(E end, boolean inclusive) {
var ei = inclusive ? floorIndex(end) : lowerIndex(end);
if (ei < 0) {
return sortedSetOf();
} else if (ei == (offset + length - 1)) {
return this;
}
var len = 1 + ei - offset;
return new UnmodifiableSortedSet<>(offset, len, array, comparator);
}
@Override
public UnmodifiableSortedSet<E> tailSet(E start, boolean inclusive) {
var si = inclusive ? ceilingIndex(start) : higherIndex(start);
if (si < 0) {
return sortedSetOf();
} else if (si == offset) {
return this;
}
var len = offset + length - si;
return new UnmodifiableSortedSet<>(si, len, array, comparator);
}
@Override
public E pollFirst() {
throw new UnsupportedOperationException("Modifying unmodifiable set not allowed");
}
@Override
public E pollLast() {
throw new UnsupportedOperationException("Modifying unmodifiable set not allowed");
}
// -------- SortedSet --------
@Override
public Comparator<? super E> comparator() {
return comparator;
}
@Override
public UnmodifiableSortedSet<E> subSet(E start, E end) {
return subSet(start, true, end, false);
}
@Override
public UnmodifiableSortedSet<E> headSet(E end) {
return headSet(end, false);
}
@Override
public UnmodifiableSortedSet<E> tailSet(E start) {
return tailSet(start, true);
}
@Override
@SuppressWarnings("unchecked")
public E first() {
if (length == 0) {
throw new NoSuchElementException("size == 0");
}
return (E) array[offset];
}
@Override
@SuppressWarnings("unchecked")
public E last() {
if (length == 0) {
throw new NoSuchElementException("size == 0");
}
return (E) array[offset + length - 1];
}
// -------- UnmodifiableCollection --------
/**
* Get list with only the items matching the predicate.
*
* @param predicate The predicate to keep item in response.
* @return The filtered list.
*/
@Override
public UnmodifiableSortedSet<E> filtered(Predicate<? super E> predicate) {
return (UnmodifiableSortedSet<E>) super.filtered(predicate);
}
// -------- UnmodifiableCollection && SequencedSet (java 21) --------
@SuppressWarnings("unchecked")
@Override // in NavigableSet Since java 21.
public UnmodifiableSortedSet<E> reversed() {
return new UnmodifiableSortedSet<>(
0,
length,
reversedArray(),
comparator == null
? (Comparator<E>) Comparator.reverseOrder()
: comparator.reversed()
);
}
// -------- UnmodifiableSortedSet --------
/**
* Builder for making an unmodifiable sorted set.
*
* @param <E> The set item type.
*/
public final static class Builder<E>
implements SetBuilder<E>, UnmodifiableCollectionBuilder<E, UnmodifiableSortedSet<E>, Builder<E>> {
private Object[] array;
private int size;
private UnmodifiableSortedSet<E> justBuilt;
private final Comparator<? super E> comparator;
Builder(int initialCapacity, Comparator<? super E> comparator) {
this.array = new Object[initialCapacity];
this.size = 0;
this.justBuilt = null;
this.comparator = comparator;
}
@Override
public Builder<E> add(E e) {
requireNonNull(e, "null item");
ensureCapacity(size + 1);
array[size++] = e;
return this;
}
@Override
@SafeVarargs
@SuppressWarnings("varargs")
public final Builder<E> addAll(E... items) {
checkNotNull(items);
if (items.length == 0) {
return this;
}
ensureCapacity(size + items.length);
System.arraycopy(items, 0, array, size, items.length);
size += items.length;
return this;
}
@Override
public Builder<E> addAll(Collection<? extends E> collection) {
if (collection.isEmpty()) {
return this;
}
ensureCapacity(size + collection.size());
for (Object o : collection) {
array[size++] = o;
}
return this;
}
@Override
public UnmodifiableSortedSet<E> build() {
if (comparator == null && size == 0) {
return sortedSetOf();
}
if (justBuilt != null) {
return justBuilt;
}
makeSorted(1);
justBuilt = new UnmodifiableSortedSet<>(0, size, array, comparator);
return justBuilt;
}
@SuppressWarnings("unchecked,rawtypes")
private void makeSorted(int minSize) {
if (size == 0) {
return;
}
// A: Sort
Arrays.sort(array, 0, size, (Comparator) comparator);
// B: Deduplicate
final int originalSize = size;
for (int i = 1; i < originalSize; ++i) {
if (array[i].equals(array[i - 1])) {
// The last entry is kept.
array[i - 1] = null;
--size;
}
}
// C: Compact away null values.
if (size < originalSize) {
if (originalSize - max(size, minSize) > 1024) {
// In order to save memory, minimize larger arrays.
Object[] compact = new Object[max(minSize, size)];
int pos = 0;
for (int i = 0; i < originalSize; ++i) {
Object 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;
}
}
}
}
}
private void ensureCapacity(int newSize) {
if (array.length < newSize) {
Object[] old = array;
array = new Object[max(newSize, old.length * 2)];
System.arraycopy(old, 0, array, 0, size);
makeSorted(newSize);
} else if (justBuilt != null) {
Object[] old = array;
array = new Object[old.length];
System.arraycopy(old, 0, array, 0, size);
// Already sorted.
}
justBuilt = null;
}
}
// -------- Private --------
@SuppressWarnings("rawtypes,unchecked")
private static final UnmodifiableSortedSet<Object> EMPTY = new UnmodifiableSortedSet(
0, 0, EMPTY_ARRAY, Comparator.naturalOrder());
private final transient Comparator<? super E> comparator;
UnmodifiableSortedSet(int offset, int length, Object[] array, Comparator<? super E> comparator) {
super(offset, length, array);
this.comparator = comparator;
}
@Override
UnmodifiableCollection<E> newInstance(Object[] array, int length) {
return new UnmodifiableSortedSet<>(0, length, array, comparator);
}
@SuppressWarnings("unchecked")
int binarySearch(Object of) {
return Arrays.binarySearch(array, offset, offset + length, of, (Comparator<Object>) comparator);
}
int lowerIndex(E of) {
// return max X given X < e
if (length == 0) return -1;
int si = binarySearch(of);
if (si == 0) {
// found at first pos, no element lower than this.
return -1;
} else if (si > 0) {
// found, so there is an exact match, return the *previous* element.
si--;
} else {
// not found, calculate insertion point - 1
si = -2 - si;
}
if (si < 0) {
// before first, no match.
return -1;
}
return si;
}
int floorIndex(E of) {
// return max X given X <= e
if (length == 0) return -1;
int si = binarySearch(of);
if (si < 0) {
// not found, calculate point before insertion point.
si = -2 - si;
if (si < 0) {
// before first, no match.
return -1;
}
}
return si;
}
int higherIndex(E of) {
// return min X given X > e
if (length == 0) return -1;
int ei = binarySearch(of);
if (ei >= 0) {
// found, check next.
++ei;
} else {
// not found, calculate insertion point, that is the higher value.
ei = -1 - ei;
}
if (ei >= (offset + length)) {
// after last, return none.
return -1;
}
return ei;
}
int ceilingIndex(E of) {
// return min X given X >= e
if (length == 0) return -1;
int ei = binarySearch(of);
if (ei < 0) {
// not found, calculate insertion point.
ei = -1 - ei;
if (ei >= (offset + length)) {
// after last, return none.
return -1;
}
}
return ei;
}
static <E> UnmodifiableSortedSet<E> construct(Comparator<Object> comparator, Object... array) {
checkNotNull(array);
// A: Sort
Arrays.sort(array, comparator);
// B: Deduplicate
int size = array.length;
for (int i = 1; i < array.length; ++i) {
if (array[i].equals(array[i - 1])) {
// The last entry is kept.
array[i - 1] = null;
--size;
}
}
// C: Compact away null values.
if (size < array.length) {
if (array.length - size > 1024) {
// In order to save memory, minimize larger arrays.
Object[] compact = new Object[size];
int pos = 0;
for (Object o : array) {
if (o != null) {
compact[pos++] = o;
}
}
array = compact;
} else {
for (int moveTo = 0, moveFrom = 1; moveTo < size && moveFrom < array.length; ++moveTo, ++moveFrom) {
if (array[moveTo] == null) {
while (array[moveFrom] == null) {
++moveFrom;
}
array[moveTo] = array[moveFrom];
array[moveFrom] = null;
}
}
}
}
return new UnmodifiableSortedSet<>(0, size, array, comparator);
}
}