UnmodifiableSet.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.UnmodifiableSetCollector;
import java.util.Arrays;
import java.util.Collection;
import java.util.Enumeration;
import java.util.Iterator;
import java.util.Objects;
import java.util.Set;
import java.util.function.Predicate;
import java.util.stream.Collector;
import static java.lang.Integer.highestOneBit;
import static java.lang.Math.max;
import static java.util.Objects.requireNonNull;
/**
* Simple immutable set. This set is order-preserving, so when iterating
* the elements, they will come in the same order as added. If same value
* was added multiple times, the first entry counts.
*
* @param <E> The set element type.
*/
public final class UnmodifiableSet<E> extends UnmodifiableCollection<E> implements Set<E> {
// -------- Collectors --------
/**
* Collect stream to an unmodifiable set.
*
* @param <E> The set item type.
* @return Collector instance.
*/
public static <E> Collector<E, ?, UnmodifiableSet<E>> toSet() {
return new UnmodifiableSetCollector<>();
}
// -------- Constructors --------
/**
* @param array Array of items to make set of.
* @param <E> The set item type.
* @return The unmodifiable set.
*/
@SafeVarargs
@SuppressWarnings("varargs")
public static <E> UnmodifiableSet<E> asSet(E... array) {
if (array.length == 0) {
return setOf();
}
Object[] copy = Arrays.copyOf(array, array.length);
return new UnmodifiableSet<>(copy.length, copy, makeHashTable(copy, copy.length));
}
/**
* @param iterable Iterable of items to make set of.
* @param <E> The set item type.
* @return The unmodifiable set.
*/
@SuppressWarnings("unchecked")
public static <E> UnmodifiableSet<E> asSet(Iterable<? extends E> iterable) {
if (iterable instanceof Collection) {
return asSet((Collection<E>) iterable);
}
return asSet(iterable.iterator());
}
/**
* @param iterator Iterator of items to make set of.
* @param <E> The set item type.
* @return The unmodifiable set.
*/
public static <E> UnmodifiableSet<E> asSet(Iterator<? extends E> iterator) {
if (!iterator.hasNext()) {
return setOf();
}
return UnmodifiableSet.<E>newBuilder().addAll(iterator).build();
}
/**
* @param enumeration Enumeration of items to make set of.
* @param <E> The set item type.
* @return The unmodifiable set.
*/
public static <E> UnmodifiableSet<E> asSet(Enumeration<? extends E> enumeration) {
if (!enumeration.hasMoreElements()) {
return setOf();
}
return UnmodifiableSet.<E>newBuilder().addAll(enumeration).build();
}
/**
* @param collection Collection of items to make set of.
* @param <E> The set item type.
* @return The unmodifiable set.
*/
@SuppressWarnings("unchecked")
public static <E> UnmodifiableSet<E> asSet(Collection<? extends E> collection) {
if (collection.size() == 0) {
return setOf();
}
if (collection instanceof UnmodifiableSet) {
return (UnmodifiableSet<E>) collection;
}
if (collection instanceof UnmodifiableSortedSet) {
UnmodifiableSortedSet<E> set = (UnmodifiableSortedSet<E>) collection;
return new UnmodifiableSet<>(set.length, set.array, makeHashTable(set.array, set.length));
}
if (collection instanceof Set) {
Object[] array = collection.toArray();
return new UnmodifiableSet<>(array.length, array, makeHashTable(array, array.length));
}
return UnmodifiableSet.<E>newBuilder(collection.size())
.addAll(collection)
.build();
}
/**
* @param <E> The set item type.
* @return The unmodifiable empty set.
*/
@SuppressWarnings("unchecked")
public static <E> UnmodifiableSet<E> setOf() {
return (UnmodifiableSet<E>) EMPTY;
}
/**
* @param e The item to make a set of.
* @param <E> The set item type.
* @return The unmodifiable singleton set.
*/
public static <E> UnmodifiableSet<E> setOf(E e) {
return construct(e);
}
/**
* @param e1 The first item to make a set of.
* @param e2 The second item to make a set of.
* @param <E> The set item type.
* @return The unmodifiable set.
*/
public static <E> UnmodifiableSet<E> setOf(E e1, E e2) {
return construct(e1, e2);
}
/**
* @param e1 The first item to make a set of.
* @param e2 The second item to make a set of.
* @param e3 The third item to make a set of.
* @param <E> The set item type.
* @return The unmodifiable set.
*/
public static <E> UnmodifiableSet<E> setOf(E e1, E e2, E e3) {
return construct(e1, e2, e3);
}
/**
* @param e1 The first item to make a set of.
* @param e2 The second item to make a set of.
* @param e3 The third item to make a set of.
* @param e4 The fourth item to make a set of.
* @param <E> The set item type.
* @return The unmodifiable set.
*/
public static <E> UnmodifiableSet<E> setOf(E e1, E e2, E e3, E e4) {
return construct(e1, e2, e3, e4);
}
/**
* @param e1 The first item to make a set of.
* @param e2 The second item to make a set of.
* @param e3 The third item to make a set of.
* @param e4 The fourth item to make a set of.
* @param e5 The fifth item to make a set of.
* @param <E> The set item type.
* @return The unmodifiable set.
*/
public static <E> UnmodifiableSet<E> setOf(E e1, E e2, E e3, E e4, E e5) {
return construct(e1, e2, e3, e4, e5);
}
/**
* @param e1 The first item to make a set of.
* @param e2 The second item to make a set of.
* @param e3 The third item to make a set of.
* @param e4 The fourth item to make a set of.
* @param e5 The fifth item to make a set of.
* @param e6 The sixth item to make a set of.
* @param <E> The set item type.
* @return The unmodifiable set.
*/
public static <E> UnmodifiableSet<E> setOf(E e1, E e2, E e3, E e4, E e5, E e6) {
return construct(e1, e2, e3, e4, e5, e6);
}
/**
* @param e1 The first item to make a set of.
* @param e2 The second item to make a set of.
* @param e3 The third item to make a set of.
* @param e4 The fourth item to make a set of.
* @param e5 The fifth item to make a set of.
* @param e6 The sixth item to make a set of.
* @param e7 The seventh item to make a set of.
* @param <E> The set item type.
* @return The unmodifiable set.
*/
public static <E> UnmodifiableSet<E> setOf(E e1, E e2, E e3, E e4, E e5, E e6, E e7) {
return construct(e1, e2, e3, e4, e5, e6, e7);
}
/**
* @param e1 The first item to make a set of.
* @param e2 The second item to make a set of.
* @param e3 The third item to make a set of.
* @param e4 The fourth item to make a set of.
* @param e5 The fifth item to make a set of.
* @param e6 The sixth item to make a set of.
* @param e7 The seventh item to make a set of.
* @param e8 The eighth item to make a set of.
* @param <E> The set item type.
* @return The unmodifiable set.
*/
public static <E> UnmodifiableSet<E> setOf(E e1, E e2, E e3, E e4, E e5, E e6, E e7, E e8) {
return construct(e1, e2, e3, e4, e5, e6, e7, e8);
}
/**
* @param e1 The first item to make a set of.
* @param e2 The second item to make a set of.
* @param e3 The third item to make a set of.
* @param e4 The fourth item to make a set of.
* @param e5 The fifth item to make a set of.
* @param e6 The sixth item to make a set of.
* @param e7 The seventh item to make a set of.
* @param e8 The eighth item to make a set of.
* @param e9 The ninth item to make a set of.
* @param <E> The set item type.
* @return The unmodifiable set.
*/
public static <E> UnmodifiableSet<E> setOf(E e1, E e2, E e3, E e4, E e5, E e6, E e7, E e8, E e9) {
return construct(e1, e2, e3, e4, e5, e6, e7, e8, e9);
}
/**
* @param e1 The first item to make a set of.
* @param e2 The second item to make a set of.
* @param e3 The third item to make a set of.
* @param e4 The fourth item to make a set of.
* @param e5 The fifth item to make a set of.
* @param e6 The sixth item to make a set of.
* @param e7 The seventh item to make a set of.
* @param e8 The eighth item to make a set of.
* @param e9 The ninth item to make a set of.
* @param e10 The tenth item to make a set of.
* @param more More items to put in set.
* @param <E> The set item type.
* @return The unmodifiable set.
*/
@SafeVarargs
@SuppressWarnings("varargs")
public static <E> UnmodifiableSet<E> setOf(E e1, E e2, E e3, E e4, E e5, E e6, E e7, E e8, E e9, E e10, E... more) {
return UnmodifiableSet
.<E>newBuilder(10 + more.length)
.add(e1)
.add(e2)
.add(e3)
.add(e4)
.add(e5)
.add(e6)
.add(e7)
.add(e8)
.add(e9)
.add(e10)
.addAll(more)
.build();
}
/**
* @param <E> The set item type.
* @return A builder for an unmodifiable set.
*/
public static <E> UnmodifiableSet.Builder<E> newBuilder() {
return new UnmodifiableSet.Builder<>(4);
}
/**
* @param initialCapacity The initial expected capacity of the map.
* @param <E> The set item type.
* @return A builder for an unmodifiable set.
*/
public static <E> UnmodifiableSet.Builder<E> newBuilder(int initialCapacity) {
return new UnmodifiableSet.Builder<>(max(1, initialCapacity));
}
// -------- UnmodifiableCollection --------
@Override
public UnmodifiableSet<E> reversed() {
if (length < 2) {
return this;
}
var out = reversedArray();
var hashTable = makeHashTable(out, length);
return new UnmodifiableSet<>(length, out, hashTable);
}
// -------- Object --------
@Override
public boolean equals(Object obj) {
if (obj == this) {
return true;
}
if (!(obj instanceof Set)) {
return false;
}
@SuppressWarnings("rawtypes")
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 = 0; i < length; ++i) {
if (i > 0) {
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 = 0; i < length; ++i) {
hash ^= Objects.hash(array[i]);
}
hashCode = hash;
}
return hashCode;
}
// -------- Collection --------
@Override
public boolean contains(Object o) {
if (o == null) {
return false;
}
int hash = o.hashCode();
for (int hp = hash & mask; ; hp = ++hp & mask) {
Object p = hashTable[hp];
if (p == null) {
return false;
}
if (p.equals(o)) {
return true;
}
}
}
// -------- 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 UnmodifiableSet<E> filtered(Predicate<? super E> predicate) {
return (UnmodifiableSet<E>) super.filtered(predicate);
}
// -------- UnmodifiableSet --------
/**
* A builder for making unmodifiable set.
*
* @param <E> The set item type.
*/
public final static class Builder<E>
implements SetBuilder<E>, UnmodifiableCollectionBuilder<E, UnmodifiableSet<E>, Builder<E>> {
private Object[] array;
private int size;
private Object[] hashTable;
private int mask;
private boolean forceRehash;
Builder(int initialSize) {
array = new Object[initialSize];
size = 0;
hashTable = new Object[hashTableSizeFor(array.length, MIN_HASH_TABLE_SIZE)];
mask = hashTable.length - 1;
forceRehash = false;
}
@Override
public Builder<E> add(E e) {
requireNonNull(e, "null item");
ensureCapacity(size + 1);
hashTableAdd(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);
for (E e : items) {
hashTableAdd(e);
}
return this;
}
@Override
public Builder<E> addAll(Collection<? extends E> collection) {
checkNotNull(collection);
if (collection.isEmpty()) {
return this;
}
ensureCapacity(size + collection.size());
for (E e : collection) {
hashTableAdd(e);
}
return this;
}
@Override
public UnmodifiableSet<E> build() {
forceRehash = true; // In case the builder is continuously used.
if (size == 0) {
return setOf();
}
return new UnmodifiableSet<>(size, array, hashTable);
}
private void ensureCapacity(int capacity) {
if (array.length < capacity) {
Object[] old = array;
array = new Object[max(capacity, array.length * 2)];
System.arraycopy(old, 0, array, 0, size);
forceRehash = true;
}
if (forceRehash) {
hashTable = makeHashTable(array, size, hashTableSizeFor(array.length, hashTable.length));
mask = hashTable.length - 1;
forceRehash = false;
}
}
private void hashTableAdd(Object e) {
int hash = e.hashCode();
for (int hp = hash & mask; ; hp = ++hp & mask) {
Object p = hashTable[hp];
if (p == null) {
hashTable[hp] = e;
array[size++] = e;
break;
} else if (p.equals(e)) {
break;
}
}
}
}
// -------- Private --------
UnmodifiableSet(int size, Object[] array, Object[] hashTable) {
super(0, size, array);
this.hashTable = hashTable;
this.mask = hashTable.length - 1;
}
@Override
UnmodifiableCollection<E> newInstance(Object[] array, int length) {
return new UnmodifiableSet<>(length, array, makeHashTable(array, length));
}
@SafeVarargs
@SuppressWarnings("varargs")
static <E> UnmodifiableSet<E> construct(E... array) {
return UnmodifiableSet.<E>newBuilder(array.length).addAll(array).build();
}
private static int hashTableSizeFor(final int arraySize, int currentHashTableSize) {
int tableSize = max(highestOneBit(arraySize) << 1, max(MIN_HASH_TABLE_SIZE, currentHashTableSize));
if (tableSize < (int) (MIN_OVER_CAPACITY * (double) arraySize)) {
tableSize <<= 1;
}
return tableSize;
}
static Object[] makeHashTable(Object[] array, int size) {
return makeHashTable(array, size, hashTableSizeFor(size, MIN_HASH_TABLE_SIZE));
}
private static Object[] makeHashTable(Object[] array, int size, int hashTableSize) {
int mask = hashTableSize - 1;
Object[] hashTable = new Object[hashTableSize];
for (int i = 0; i < size; ++i) {
Object o = array[i];
// if (o == null) throw new NullPointerException("Null item at index " + i + " of " + size);
int hash = o.hashCode();
int hp = hash & mask;
for (; ; ) {
Object p = hashTable[hp];
if (p == null) {
hashTable[hp] = o;
break;
}
hp = ++hp & mask;
}
}
return hashTable;
}
private static final double MIN_OVER_CAPACITY = 1.38;
private static final int MIN_HASH_TABLE_SIZE = 2;
private static final UnmodifiableSet<Object> EMPTY = new UnmodifiableSet<>(
0, EMPTY_ARRAY, new Object[MIN_HASH_TABLE_SIZE]);
private final transient Object[] hashTable;
private final transient int mask;
}