UnmodifiableSet.java

  1. /*
  2.  * Copyright (C) 2018 Stein Eldar Johnsen
  3.  *
  4.  * Licensed under the Apache License, Version 2.0 (the "License");
  5.  * you may not use this file except in compliance with the License.
  6.  * You may obtain a copy of the License at
  7.  *
  8.  * http://www.apache.org/licenses/LICENSE-2.0
  9.  *
  10.  * Unless required by applicable law or agreed to in writing, software
  11.  * distributed under the License is distributed on an "AS IS" BASIS,
  12.  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13.  * See the License for the specific language governing permissions and
  14.  * limitations under the License.
  15.  */
  16. package net.morimekta.collect;

  18. import net.morimekta.collect.collectors.UnmodifiableSetCollector;

  20. import java.util.Arrays;
  21. import java.util.Collection;
  22. import java.util.Enumeration;
  23. import java.util.Iterator;
  24. import java.util.Objects;
  25. import java.util.Set;
  26. import java.util.function.Predicate;
  27. import java.util.stream.Collector;

  29. import static java.lang.Integer.highestOneBit;
  30. import static java.lang.Math.max;
  31. import static java.util.Objects.requireNonNull;

  33. /**
  34.  * Simple immutable set. This set is order-preserving, so when iterating
  35.  * the elements, they will come in the same order as added. If same value
  36.  * was added multiple times, the first entry counts.
  37.  *
  38.  * @param <E> The set element type.
  39.  */
  40. public final class UnmodifiableSet<E> extends UnmodifiableCollection<E> implements Set<E> {
  41.     // -------- Collectors --------

  43.     /**
  44.      * Collect stream to an unmodifiable set.
  45.      *
  46.      * @param <E> The set item type.
  47.      * @return Collector instance.
  48.      */
  49.     public static <E> Collector<E, ?, UnmodifiableSet<E>> toSet() {
  50.         return new UnmodifiableSetCollector<>();
  51.     }

  53.     // -------- Constructors --------

  55.     /**
  56.      * @param array Array of items to make set of.
  57.      * @param <E>   The set item type.
  58.      * @return The unmodifiable set.
  59.      */
  60.     @SafeVarargs
  61.     @SuppressWarnings("varargs")
  62.     public static <E> UnmodifiableSet<E> asSet(E... array) {
  63.         if (array.length == 0) {
  64.             return setOf();
  65.         }
  66.         Object[] copy = Arrays.copyOf(array, array.length);
  67.         return new UnmodifiableSet<>(copy.length, copy, makeHashTable(copy, copy.length));
  68.     }

  70.     /**
  71.      * @param iterable Iterable of items to make set of.
  72.      * @param <E>      The set item type.
  73.      * @return The unmodifiable set.
  74.      */
  75.     @SuppressWarnings("unchecked")
  76.     public static <E> UnmodifiableSet<E> asSet(Iterable<? extends E> iterable) {
  77.         if (iterable instanceof Collection) {
  78.             return asSet((Collection<E>) iterable);
  79.         }
  80.         return asSet(iterable.iterator());
  81.     }

  83.     /**
  84.      * @param iterator Iterator of items to make set of.
  85.      * @param <E>      The set item type.
  86.      * @return The unmodifiable set.
  87.      */
  88.     public static <E> UnmodifiableSet<E> asSet(Iterator<? extends E> iterator) {
  89.         if (!iterator.hasNext()) {
  90.             return setOf();
  91.         }
  92.         return UnmodifiableSet.<E>newBuilder().addAll(iterator).build();
  93.     }

  95.     /**
  96.      * @param enumeration Enumeration of items to make set of.
  97.      * @param <E>         The set item type.
  98.      * @return The unmodifiable set.
  99.      */
  100.     public static <E> UnmodifiableSet<E> asSet(Enumeration<? extends E> enumeration) {
  101.         if (!enumeration.hasMoreElements()) {
  102.             return setOf();
  103.         }
  104.         return UnmodifiableSet.<E>newBuilder().addAll(enumeration).build();
  105.     }

  107.     /**
  108.      * @param collection Collection of items to make set of.
  109.      * @param <E>        The set item type.
  110.      * @return The unmodifiable set.
  111.      */
  112.     @SuppressWarnings("unchecked")
  113.     public static <E> UnmodifiableSet<E> asSet(Collection<? extends E> collection) {
  114.         if (collection.size() == 0) {
  115.             return setOf();
  116.         }
  117.         if (collection instanceof UnmodifiableSet) {
  118.             return (UnmodifiableSet<E>) collection;
  119.         }
  120.         if (collection instanceof UnmodifiableSortedSet) {
  121.             UnmodifiableSortedSet<E> set = (UnmodifiableSortedSet<E>) collection;
  122.             return new UnmodifiableSet<>(set.length, set.array, makeHashTable(set.array, set.length));
  123.         }
  124.         if (collection instanceof Set) {
  125.             Object[] array = collection.toArray();
  126.             return new UnmodifiableSet<>(array.length, array, makeHashTable(array, array.length));
  127.         }
  128.         return UnmodifiableSet.<E>newBuilder(collection.size())
  129.                               .addAll(collection)
  130.                               .build();
  131.     }

  133.     /**
  134.      * @param <E> The set item type.
  135.      * @return The unmodifiable empty set.
  136.      */
  137.     @SuppressWarnings("unchecked")
  138.     public static <E> UnmodifiableSet<E> setOf() {
  139.         return (UnmodifiableSet<E>) EMPTY;
  140.     }

  142.     /**
  143.      * @param e   The item to make a set of.
  144.      * @param <E> The set item type.
  145.      * @return The unmodifiable singleton set.
  146.      */
  147.     public static <E> UnmodifiableSet<E> setOf(E e) {
  148.         return construct(e);
  149.     }

  151.     /**
  152.      * @param e1  The first item to make a set of.
  153.      * @param e2  The second item to make a set of.
  154.      * @param <E> The set item type.
  155.      * @return The unmodifiable set.
  156.      */
  157.     public static <E> UnmodifiableSet<E> setOf(E e1, E e2) {
  158.         return construct(e1, e2);
  159.     }

  161.     /**
  162.      * @param e1  The first item to make a set of.
  163.      * @param e2  The second item to make a set of.
  164.      * @param e3  The third item to make a set of.
  165.      * @param <E> The set item type.
  166.      * @return The unmodifiable set.
  167.      */
  168.     public static <E> UnmodifiableSet<E> setOf(E e1, E e2, E e3) {
  169.         return construct(e1, e2, e3);
  170.     }

  172.     /**
  173.      * @param e1  The first item to make a set of.
  174.      * @param e2  The second item to make a set of.
  175.      * @param e3  The third item to make a set of.
  176.      * @param e4  The fourth item to make a set of.
  177.      * @param <E> The set item type.
  178.      * @return The unmodifiable set.
  179.      */
  180.     public static <E> UnmodifiableSet<E> setOf(E e1, E e2, E e3, E e4) {
  181.         return construct(e1, e2, e3, e4);
  182.     }

  184.     /**
  185.      * @param e1  The first item to make a set of.
  186.      * @param e2  The second item to make a set of.
  187.      * @param e3  The third item to make a set of.
  188.      * @param e4  The fourth item to make a set of.
  189.      * @param e5  The fifth item to make a set of.
  190.      * @param <E> The set item type.
  191.      * @return The unmodifiable set.
  192.      */
  193.     public static <E> UnmodifiableSet<E> setOf(E e1, E e2, E e3, E e4, E e5) {
  194.         return construct(e1, e2, e3, e4, e5);
  195.     }

  197.     /**
  198.      * @param e1  The first item to make a set of.
  199.      * @param e2  The second item to make a set of.
  200.      * @param e3  The third item to make a set of.
  201.      * @param e4  The fourth item to make a set of.
  202.      * @param e5  The fifth item to make a set of.
  203.      * @param e6  The sixth item to make a set of.
  204.      * @param <E> The set item type.
  205.      * @return The unmodifiable set.
  206.      */
  207.     public static <E> UnmodifiableSet<E> setOf(E e1, E e2, E e3, E e4, E e5, E e6) {
  208.         return construct(e1, e2, e3, e4, e5, e6);
  209.     }

  211.     /**
  212.      * @param e1  The first item to make a set of.
  213.      * @param e2  The second item to make a set of.
  214.      * @param e3  The third item to make a set of.
  215.      * @param e4  The fourth item to make a set of.
  216.      * @param e5  The fifth item to make a set of.
  217.      * @param e6  The sixth item to make a set of.
  218.      * @param e7  The seventh item to make a set of.
  219.      * @param <E> The set item type.
  220.      * @return The unmodifiable set.
  221.      */
  222.     public static <E> UnmodifiableSet<E> setOf(E e1, E e2, E e3, E e4, E e5, E e6, E e7) {
  223.         return construct(e1, e2, e3, e4, e5, e6, e7);
  224.     }

  226.     /**
  227.      * @param e1  The first item to make a set of.
  228.      * @param e2  The second item to make a set of.
  229.      * @param e3  The third item to make a set of.
  230.      * @param e4  The fourth item to make a set of.
  231.      * @param e5  The fifth item to make a set of.
  232.      * @param e6  The sixth item to make a set of.
  233.      * @param e7  The seventh item to make a set of.
  234.      * @param e8  The eighth item to make a set of.
  235.      * @param <E> The set item type.
  236.      * @return The unmodifiable set.
  237.      */
  238.     public static <E> UnmodifiableSet<E> setOf(E e1, E e2, E e3, E e4, E e5, E e6, E e7, E e8) {
  239.         return construct(e1, e2, e3, e4, e5, e6, e7, e8);
  240.     }

  242.     /**
  243.      * @param e1  The first item to make a set of.
  244.      * @param e2  The second item to make a set of.
  245.      * @param e3  The third item to make a set of.
  246.      * @param e4  The fourth item to make a set of.
  247.      * @param e5  The fifth item to make a set of.
  248.      * @param e6  The sixth item to make a set of.
  249.      * @param e7  The seventh item to make a set of.
  250.      * @param e8  The eighth item to make a set of.
  251.      * @param e9  The ninth item to make a set of.
  252.      * @param <E> The set item type.
  253.      * @return The unmodifiable set.
  254.      */
  255.     public static <E> UnmodifiableSet<E> setOf(E e1, E e2, E e3, E e4, E e5, E e6, E e7, E e8, E e9) {
  256.         return construct(e1, e2, e3, e4, e5, e6, e7, e8, e9);
  257.     }

  259.     /**
  260.      * @param e1   The first item to make a set of.
  261.      * @param e2   The second item to make a set of.
  262.      * @param e3   The third item to make a set of.
  263.      * @param e4   The fourth item to make a set of.
  264.      * @param e5   The fifth item to make a set of.
  265.      * @param e6   The sixth item to make a set of.
  266.      * @param e7   The seventh item to make a set of.
  267.      * @param e8   The eighth item to make a set of.
  268.      * @param e9   The ninth item to make a set of.
  269.      * @param e10  The tenth item to make a set of.
  270.      * @param more More items to put in set.
  271.      * @param <E>  The set item type.
  272.      * @return The unmodifiable set.
  273.      */
  274.     @SafeVarargs
  275.     @SuppressWarnings("varargs")
  276.     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) {
  277.         return UnmodifiableSet
  278.                 .<E>newBuilder(10 + more.length)
  279.                 .add(e1)
  280.                 .add(e2)
  281.                 .add(e3)
  282.                 .add(e4)
  283.                 .add(e5)
  284.                 .add(e6)
  285.                 .add(e7)
  286.                 .add(e8)
  287.                 .add(e9)
  288.                 .add(e10)
  289.                 .addAll(more)
  290.                 .build();
  291.     }

  293.     /**
  294.      * @param <E> The set item type.
  295.      * @return A builder for an unmodifiable set.
  296.      */
  297.     public static <E> UnmodifiableSet.Builder<E> newBuilder() {
  298.         return new UnmodifiableSet.Builder<>(4);
  299.     }

  301.     /**
  302.      * @param initialCapacity The initial expected capacity of the map.
  303.      * @param <E>             The set item type.
  304.      * @return A builder for an unmodifiable set.
  305.      */
  306.     public static <E> UnmodifiableSet.Builder<E> newBuilder(int initialCapacity) {
  307.         return new UnmodifiableSet.Builder<>(max(1, initialCapacity));
  308.     }

  310.     // -------- UnmodifiableCollection --------

  312.     @Override
  313.     public UnmodifiableSet<E> reversed() {
  314.         if (length < 2) {
  315.             return this;
  316.         }
  317.         var out = reversedArray();
  318.         var hashTable = makeHashTable(out, length);
  319.         return new UnmodifiableSet<>(length, out, hashTable);
  320.     }

  322.     // -------- Object --------

  324.     @Override
  325.     public boolean equals(Object obj) {
  326.         if (obj == this) {
  327.             return true;
  328.         }
  329.         if (!(obj instanceof Set)) {
  330.             return false;
  331.         }
  332.         @SuppressWarnings("rawtypes")
  333.         Set other = (Set) obj;
  334.         if (other.size() != length) {
  335.             return false;
  336.         }
  337.         for (Object o : (Set<?>) obj) {
  338.             if (!contains(o)) {
  339.                 return false;
  340.             }
  341.         }
  342.         return true;
  343.     }

  345.     @Override
  346.     public String toString() {
  347.         StringBuilder builder = new StringBuilder("{");
  348.         for (int i = 0; i < length; ++i) {
  349.             if (i > 0) {
  350.                 builder.append(", ");
  351.             }
  352.             builder.append(array[i].toString());
  353.         }
  354.         return builder.append("}").toString();
  355.     }

  357.     @Override
  358.     public int hashCode() {
  359.         if (hashCode == null) {
  360.             int hash = Objects.hash(getClass(), length);
  361.             for (int i = 0; i < length; ++i) {
  362.                 hash ^= Objects.hash(array[i]);
  363.             }
  364.             hashCode = hash;
  365.         }
  366.         return hashCode;
  367.     }

  369.     // -------- Collection --------

  371.     @Override
  372.     public boolean contains(Object o) {
  373.         if (o == null) {
  374.             return false;
  375.         }
  376.         int hash = o.hashCode();
  377.         for (int hp = hash & mask; ; hp = ++hp & mask) {
  378.             Object p = hashTable[hp];
  379.             if (p == null) {
  380.                 return false;
  381.             }
  382.             if (p.equals(o)) {
  383.                 return true;
  384.             }
  385.         }
  386.     }

  388.     // -------- UnmodifiableCollection --------

  390.     /**
  391.      * Get list with only the items matching the predicate.
  392.      *
  393.      * @param predicate The predicate to keep item in response.
  394.      * @return The filtered list.
  395.      */
  396.     @Override
  397.     public UnmodifiableSet<E> filtered(Predicate<? super E> predicate) {
  398.         return (UnmodifiableSet<E>) super.filtered(predicate);
  399.     }

  401.     // -------- UnmodifiableSet --------

  403.     /**
  404.      * A builder for making unmodifiable set.
  405.      *
  406.      * @param <E> The set item type.
  407.      */
  408.     public final static class Builder<E>
  409.             implements SetBuilder<E>, UnmodifiableCollectionBuilder<E, UnmodifiableSet<E>, Builder<E>> {
  410.         private Object[] array;
  411.         private int      size;
  412.         private Object[] hashTable;
  413.         private int      mask;
  414.         private boolean  forceRehash;

  416.         Builder(int initialSize) {
  417.             array = new Object[initialSize];
  418.             size = 0;
  419.             hashTable = new Object[hashTableSizeFor(array.length, MIN_HASH_TABLE_SIZE)];
  420.             mask = hashTable.length - 1;
  421.             forceRehash = false;
  422.         }

  424.         @Override
  425.         public Builder<E> add(E e) {
  426.             requireNonNull(e, "null item");
  427.             ensureCapacity(size + 1);
  428.             hashTableAdd(e);
  429.             return this;
  430.         }

  432.         @Override
  433.         @SafeVarargs
  434.         @SuppressWarnings("varargs")
  435.         public final Builder<E> addAll(E... items) {
  436.             checkNotNull(items);
  437.             if (items.length == 0) {
  438.                 return this;
  439.             }
  440.             ensureCapacity(size + items.length);
  441.             for (E e : items) {
  442.                 hashTableAdd(e);
  443.             }
  444.             return this;
  445.         }

  447.         @Override
  448.         public Builder<E> addAll(Collection<? extends E> collection) {
  449.             checkNotNull(collection);
  450.             if (collection.isEmpty()) {
  451.                 return this;
  452.             }
  453.             ensureCapacity(size + collection.size());
  454.             for (E e : collection) {
  455.                 hashTableAdd(e);
  456.             }
  457.             return this;
  458.         }

  460.         @Override
  461.         public UnmodifiableSet<E> build() {
  462.             forceRehash = true;  // In case the builder is continuously used.
  463.             if (size == 0) {
  464.                 return setOf();
  465.             }
  466.             return new UnmodifiableSet<>(size, array, hashTable);
  467.         }

  469.         private void ensureCapacity(int capacity) {
  470.             if (array.length < capacity) {
  471.                 Object[] old = array;
  472.                 array = new Object[max(capacity, array.length * 2)];
  473.                 System.arraycopy(old, 0, array, 0, size);
  474.                 forceRehash = true;
  475.             }
  476.             if (forceRehash) {
  477.                 hashTable = makeHashTable(array, size, hashTableSizeFor(array.length, hashTable.length));
  478.                 mask = hashTable.length - 1;
  479.                 forceRehash = false;
  480.             }
  481.         }

  483.         private void hashTableAdd(Object e) {
  484.             int hash = e.hashCode();
  485.             for (int hp = hash & mask; ; hp = ++hp & mask) {
  486.                 Object p = hashTable[hp];
  487.                 if (p == null) {
  488.                     hashTable[hp] = e;
  489.                     array[size++] = e;
  490.                     break;
  491.                 } else if (p.equals(e)) {
  492.                     break;
  493.                 }
  494.             }
  495.         }
  496.     }

  498.     // -------- Private --------

  500.     UnmodifiableSet(int size, Object[] array, Object[] hashTable) {
  501.         super(0, size, array);
  502.         this.hashTable = hashTable;
  503.         this.mask = hashTable.length - 1;
  504.     }

  506.     @Override
  507.     UnmodifiableCollection<E> newInstance(Object[] array, int length) {
  508.         return new UnmodifiableSet<>(length, array, makeHashTable(array, length));
  509.     }

  511.     @SafeVarargs
  512.     @SuppressWarnings("varargs")
  513.     static <E> UnmodifiableSet<E> construct(E... array) {
  514.         return UnmodifiableSet.<E>newBuilder(array.length).addAll(array).build();
  515.     }

  517.     private static int hashTableSizeFor(final int arraySize, int currentHashTableSize) {
  518.         int tableSize = max(highestOneBit(arraySize) << 1, max(MIN_HASH_TABLE_SIZE, currentHashTableSize));
  519.         if (tableSize < (int) (MIN_OVER_CAPACITY * (double) arraySize)) {
  520.             tableSize <<= 1;
  521.         }
  522.         return tableSize;
  523.     }

  525.     static Object[] makeHashTable(Object[] array, int size) {
  526.         return makeHashTable(array, size, hashTableSizeFor(size, MIN_HASH_TABLE_SIZE));
  527.     }

  529.     private static Object[] makeHashTable(Object[] array, int size, int hashTableSize) {
  530.         int mask = hashTableSize - 1;
  531.         Object[] hashTable = new Object[hashTableSize];
  532.         for (int i = 0; i < size; ++i) {
  533.             Object o = array[i];
  534.             // if (o == null) throw new NullPointerException("Null item at index " + i + " of " + size);
  535.             int hash = o.hashCode();
  536.             int hp = hash & mask;
  537.             for (; ; ) {
  538.                 Object p = hashTable[hp];
  539.                 if (p == null) {
  540.                     hashTable[hp] = o;
  541.                     break;
  542.                 }
  543.                 hp = ++hp & mask;
  544.             }
  545.         }

  547.         return hashTable;
  548.     }

  550.     private static final double MIN_OVER_CAPACITY   = 1.38;
  551.     private static final int    MIN_HASH_TABLE_SIZE = 2;

  553.     private static final UnmodifiableSet<Object> EMPTY = new UnmodifiableSet<>(
  554.             0, EMPTY_ARRAY, new Object[MIN_HASH_TABLE_SIZE]);

  556.     private final transient Object[] hashTable;
  557.     private final transient int      mask;

  559. }
Created with JaCoCo 0.8.11.202310140853