ArraySet.jvm.kt

/*
 * Copyright 2022 The Android Open Source Project
 *
 * 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 androidx.collection

import androidx.collection.internal.EMPTY_INTS
import androidx.collection.internal.EMPTY_OBJECTS

/**
 * ArraySet is a generic set data structure that is designed to be more memory efficient than a
 * traditional [HashSet].  The design is very similar to
 * [ArrayMap], with all of the caveats described there.  This implementation is
 * separate from ArrayMap, however, so the Object array contains only one item for each
 * entry in the set (instead of a pair for a mapping).
 *
 * Note that this implementation is not intended to be appropriate for data structures
 * that may contain large numbers of items.  It is generally slower than a traditional
 * HashSet, since lookups require a binary search and adds and removes require inserting
 * and deleting entries in the array.  For containers holding up to hundreds of items,
 * the performance difference is not significant, less than 50%.
 *
 * Because this container is intended to better balance memory use, unlike most other
 * standard Java containers it will shrink its array as items are removed from it.  Currently
 * you have no control over this shrinking -- if you set a capacity and then remove an
 * item, it may reduce the capacity to better match the current size.  In the future an
 * explicit call to set the capacity should turn off this aggressive shrinking behavior.
 *
 * This structure is **NOT** thread-safe.
 *
 * @constructor Creates a new empty ArraySet. The default capacity of an array map is 0, and
 * will grow once items are added to it.
 */
public actual class ArraySet<E>
// TODO(b/237405792): Default value for optional argument is required here to workaround Metalava's
//  lack of support for expect / actual.
@Suppress("ACTUAL_FUNCTION_WITH_DEFAULT_ARGUMENTS")
// TODO(b/237405286): @JvmOverloads is redundant in this actual, but is necessary here to workaround
//  Metalava's lack of support for expect / actual.
@JvmOverloads actual constructor(capacity: Int = 0) : MutableCollection<E>, MutableSet<E> {
    internal actual var hashes: IntArray = EMPTY_INTS
    internal actual var array: Array<Any?> = EMPTY_OBJECTS

    internal actual var _size = 0
    actual override val size: Int
        get() = _size

    /**
     * Create a new ArraySet with the mappings from the given ArraySet.
     */
    public actual constructor(set: ArraySet<out E>?) : this(capacity = 0) {
        if (set != null) {
            addAll(set)
        }
    }

    /**
     * Create a new ArraySet with the mappings from the given [Collection].
     */
    public actual constructor(set: Collection<E>?) : this(capacity = 0) {
        if (set != null) {
            addAll(set)
        }
    }

    /**
     * Create a new ArraySet with items from the given array.
     */
    public actual constructor(array: Array<out E>?) : this(capacity = 0) {
        if (array != null) {
            for (value in array) {
                add(value)
            }
        }
    }

    init {
        if (capacity > 0) {
            allocArrays(capacity)
        }
    }

    /**
     * Make the array map empty.  All storage is released.
     *
     * @throws ConcurrentModificationException if concurrent modifications detected.
     */
    actual override fun clear() {
        clearInternal()
    }

    /**
     * Ensure the array map can hold at least [minimumCapacity]
     * items.
     *
     * @throws ConcurrentModificationException if concurrent modifications detected.
     */
    public actual fun ensureCapacity(minimumCapacity: Int) {
        ensureCapacityInternal(minimumCapacity)
    }

    /**
     * Check whether a value exists in the set.
     *
     * @param element The value to search for.
     * @return Returns true if the value exists, else false.
     */
    actual override operator fun contains(element: E): Boolean {
        return containsInternal(element)
    }

    /**
     * Returns the index of a value in the set.
     *
     * @param key The value to search for.
     * @return Returns the index of the value if it exists, else a negative integer.
     */
    public actual fun indexOf(key: Any?): Int {
        return indexOfInternal(key)
    }

    /**
     * Return the value at the given index in the array.
     *
     * @param index The desired index, must be between 0 and [size]-1.
     * @return Returns the value stored at the given index.
     */
    public actual fun valueAt(index: Int): E {
        return valueAtInternal(index)
    }

    /**
     * Return `true` if the array map contains no items.
     */
    actual override fun isEmpty(): Boolean {
        return isEmptyInternal()
    }

    /**
     * Adds the specified object to this set. The set is not modified if it
     * already contains the object.
     *
     * @param element the object to add.
     * @return `true` if this set is modified, `false` otherwise.
     * @throws ConcurrentModificationException if concurrent modifications detected.
     */
    actual override fun add(element: E): Boolean {
        return addInternal(element)
    }

    /**
     * Perform a [add] of all values in [array]
     *
     * @param array The array whose contents are to be retrieved.
     * @throws ConcurrentModificationException if concurrent modifications detected.
     */
    public actual fun addAll(array: ArraySet<out E>) {
        addAllInternal(array)
    }

    /**
     * Removes the specified object from this set.
     *
     * @param element the object to remove.
     * @return `true` if this set was modified, `false` otherwise.
     */
    actual override fun remove(element: E): Boolean {
        return removeInternal(element)
    }

    /**
     * Remove the key/value mapping at the given index.
     *
     * @param index The desired index, must be between 0 and [size]-1.
     * @return Returns the value that was stored at this index.
     * @throws ConcurrentModificationException if concurrent modifications detected.
     */
    public actual fun removeAt(index: Int): E {
        return removeAtInternal(index)
    }

    /**
     * Perform a [remove] of all values in [array]
     *
     * @param array The array whose contents are to be removed.
     */
    public actual fun removeAll(array: ArraySet<out E>): Boolean {
        return removeAllInternal(array)
    }

    @Suppress("ArrayReturn")
    public fun toArray(): Array<Any?> {
        return array.copyOfRange(fromIndex = 0, toIndex = _size)
    }

    @Suppress("ArrayReturn")
    public fun <T> toArray(array: Array<T>): Array<T> {
        val result = ArraySetJvmUtil.resizeForToArray(array, _size)

        @Suppress("UNCHECKED_CAST")
        this.array.copyInto(result as Array<Any?>, 0, 0, _size)
        return result
    }

    /**
     * This implementation returns false if the object is not a set, or
     * if the sets have different sizes.  Otherwise, for each value in this
     * set, it checks to make sure the value also exists in the other set.
     * If any value doesn't exist, the method returns false; otherwise, it
     * returns true.
     *
     * @see Any.equals
     */
    actual override fun equals(other: Any?): Boolean {
        return equalsInternal(other)
    }

    /**
     * @see Any.hashCode
     */
    actual override fun hashCode(): Int {
        return hashCodeInternal()
    }

    /**
     * This implementation composes a string by iterating over its values. If
     * this set contains itself as a value, the string "(this Set)"
     * will appear in its place.
     */
    actual override fun toString(): String {
        return toStringInternal()
    }

    /**
     * Return a [MutableIterator] over all values in the set.
     *
     * **Note:** this is a less efficient way to access the array contents compared to
     * looping from 0 until [size] and calling [valueAt].
     */
    actual override fun iterator(): MutableIterator<E> = ElementIterator()

    private inner class ElementIterator : IndexBasedArrayIterator<E>(_size) {
        override fun elementAt(index: Int): E = valueAt(index)

        override fun removeAt(index: Int) {
            this@ArraySet.removeAt(index)
        }
    }

    /**
     * Determine if the array set contains all of the values in the given collection.
     *
     * @param elements The collection whose contents are to be checked against.
     * @return Returns true if this array set contains a value for every entry
     * in [elements] else returns false.
     */
    actual override fun containsAll(elements: Collection<E>): Boolean {
        return containsAllInternal(elements)
    }

    /**
     * Perform an [add] of all values in [elements]
     *
     * @param elements The collection whose contents are to be retrieved.
     */
    actual override fun addAll(elements: Collection<E>): Boolean {
        return addAllInternal(elements)
    }

    /**
     * Remove all values in the array set that exist in the given collection.
     *
     * @param elements The collection whose contents are to be used to remove values.
     * @return Returns true if any values were removed from the array set, else false.
     */
    actual override fun removeAll(elements: Collection<E>): Boolean {
        return removeAllInternal(elements)
    }

    /**
     * Remove all values in the array set that do **not** exist in the given collection.
     *
     * @param elements The collection whose contents are to be used to determine which
     * values to keep.
     * @return Returns true if any values were removed from the array set, else false.
     */
    actual override fun retainAll(elements: Collection<E>): Boolean {
        return retainAllInternal(elements)
    }
}