Split ArraySet into separate Jvm and Native implementations for toArray compatibility
It is required to provided a separate Java implementation of `.toArray` for
ArraySet for compatibility, due to:
1. Ignoring nullity of the generic type T to maintain the behavior of setting the n+1'th item to null
2. Allowing .toArray(array: Array<T>) to be called without making T a reified type
2. Delegate the array copy implementation to System.arraycopy which is implemented natively on JVM
Instead of providing a less-performance version for native / non-jvm platforms,
it was removed in this CL because it was always only ever needed for
compatibility. Users should instead prefer to follow the Kotlin stdlib standard
of using `.toTypedArray` or one of its primitive relatives, e.g., `.toIntArray`.
Relnote: "`ArraySet.toArray` is now only available on JVM as it was always only
included for compatibility with Java. Kotlin users should generaly use the
stdlib's `.toTypedArray` helpers instead, which provides the exact same
functionality with added type safety."
Test: :collection:collection:test
Change-Id: I2c59be76341e284936d6da16a3feb582d1f66c51
diff --git a/collection/collection/src/commonMain/kotlin/androidx/collection/ArraySet.kt b/collection/collection/src/commonMain/kotlin/androidx/collection/ArraySet.kt
index 6d7a336..0c7ac8e 100644
--- a/collection/collection/src/commonMain/kotlin/androidx/collection/ArraySet.kt
+++ b/collection/collection/src/commonMain/kotlin/androidx/collection/ArraySet.kt
@@ -59,132 +59,37 @@
* @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 class ArraySet<E> @JvmOverloads constructor(capacity: Int = 0) :
- MutableCollection<E>, MutableSet<E> {
+public expect class ArraySet<E> @JvmOverloads constructor(
+ capacity: Int = 0
+) : MutableCollection<E>, MutableSet<E> {
- private var hashes: IntArray = EMPTY_INTS
- private var array: Array<Any?> = EMPTY_OBJECTS
+ internal var hashes: IntArray
+ internal var array: Array<Any?>
- private var _size = 0
-
+ internal var _size: Int
override val size: Int
- get() = _size
/**
* Create a new ArraySet with the mappings from the given ArraySet.
*/
- public constructor(set: ArraySet<out E>?) : this(capacity = 0) {
- if (set != null) {
- addAll(set)
- }
- }
+ public constructor(set: ArraySet<out E>?)
/**
* Create a new ArraySet with the mappings from the given [Collection].
*/
- public constructor(set: Collection<E>?) : this(capacity = 0) {
- if (set != null) {
- addAll(set)
- }
- }
+ public constructor(set: Collection<E>?)
/**
* Create a new ArraySet with items from the given array.
*/
- public constructor(array: Array<out E>?) : this(capacity = 0) {
- if (array != null) {
- for (value in array) {
- add(value)
- }
- }
- }
-
- init {
- if (capacity > 0) {
- allocArrays(capacity)
- }
- }
-
- private fun binarySearchInternal(hash: Int): Int =
- try {
- binarySearch(hashes, _size, hash)
- } catch (e: IndexOutOfBoundsException) {
- throw ConcurrentModificationException()
- }
-
- private fun indexOf(key: Any?, hash: Int): Int {
- val n = _size
-
- // Important fast case: if nothing is in here, nothing to look for.
- if (n == 0) {
- return -1
- }
- val index = binarySearchInternal(hash)
-
- // If the hash code wasn't found, then we have no entry for this key.
- if (index < 0) {
- return index
- }
-
- // If the key at the returned index matches, that's what we want.
- if (key == array[index]) {
- return index
- }
-
- // Search for a matching key after the index.
- var end = index + 1
- while (end < n && hashes[end] == hash) {
- if (key == array[end]) {
- return end
- }
- end++
- }
-
- // Search for a matching key before the index.
- var i = index - 1
- while (i >= 0 && hashes[i] == hash) {
- if (key == array[i]) {
- return i
- }
- i--
- }
-
- // Key not found -- return negative value indicating where a
- // new entry for this key should go. We use the end of the
- // hash chain to reduce the number of array entries that will
- // need to be copied when inserting.
- return end.inv()
- }
-
- private fun indexOfNull(): Int = indexOf(key = null, hash = 0)
-
- private fun allocArrays(size: Int) {
- hashes = IntArray(size)
- array = arrayOfNulls(size)
- }
-
- private inline fun printlnIfDebug(message: () -> String) {
- if (DEBUG) {
- println(message())
- }
- }
+ public constructor(array: Array<out E>?)
/**
* Make the array map empty. All storage is released.
*
* @throws ConcurrentModificationException if concurrent modifications detected.
*/
- override fun clear() {
- if (_size != 0) {
- hashes = EMPTY_INTS
- array = EMPTY_OBJECTS
- _size = 0
- }
- @Suppress("KotlinConstantConditions")
- if (_size != 0) {
- throw ConcurrentModificationException()
- }
- }
+ override fun clear()
/**
* Ensure the array map can hold at least [minimumCapacity]
@@ -192,21 +97,7 @@
*
* @throws ConcurrentModificationException if concurrent modifications detected.
*/
- public fun ensureCapacity(minimumCapacity: Int) {
- val oSize: Int = _size
- if (hashes.size < minimumCapacity) {
- val ohashes = hashes
- val oarray = array
- allocArrays(minimumCapacity)
- if (_size > 0) {
- ohashes.copyInto(destination = hashes, endIndex = _size)
- oarray.copyInto(destination = array, endIndex = _size)
- }
- }
- if (_size != oSize) {
- throw ConcurrentModificationException()
- }
- }
+ public fun ensureCapacity(minimumCapacity: Int)
/**
* Check whether a value exists in the set.
@@ -214,8 +105,7 @@
* @param element The value to search for.
* @return Returns true if the value exists, else false.
*/
- override operator fun contains(element: E): Boolean =
- indexOf(element) >= 0
+ override operator fun contains(element: E): Boolean
/**
* Returns the index of a value in the set.
@@ -223,23 +113,20 @@
* @param key The value to search for.
* @return Returns the index of the value if it exists, else a negative integer.
*/
- public fun indexOf(key: Any?): Int =
- if (key == null) indexOfNull() else indexOf(key = key, hash = key.hashCode())
+ public fun indexOf(key: Any?): Int
/**
* 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.
*/
- @Suppress("UNCHECKED_CAST")
- public fun valueAt(index: Int): E =
- array[index] as E
+ public fun valueAt(index: Int): E
/**
- * Return true if the array map contains no items.
+ * Return `true` if the array map contains no items.
*/
- override fun isEmpty(): Boolean =
- _size <= 0
+ override fun isEmpty(): Boolean
/**
* Adds the specified object to this set. The set is not modified if it
@@ -249,98 +136,15 @@
* @return `true` if this set is modified, `false` otherwise.
* @throws ConcurrentModificationException if concurrent modifications detected.
*/
- override fun add(element: E): Boolean {
- val oSize = _size
- val hash: Int
- var index: Int
- if (element == null) {
- hash = 0
- index = indexOfNull()
- } else {
- hash = element.hashCode()
- index = indexOf(element, hash)
- }
-
- if (index >= 0) {
- return false
- }
-
- index = index.inv()
- if (oSize >= hashes.size) {
- val n =
- when {
- oSize >= BASE_SIZE * 2 -> oSize + (oSize shr 1)
- oSize >= BASE_SIZE -> BASE_SIZE * 2
- else -> BASE_SIZE
- }
-
- printlnIfDebug { "$TAG add: grow from ${hashes.size} to $n" }
-
- val ohashes = hashes
- val oarray = array
- allocArrays(n)
-
- if (oSize != _size) {
- throw ConcurrentModificationException()
- }
-
- if (hashes.isNotEmpty()) {
- printlnIfDebug { "$TAG add: copy 0-$oSize to 0" }
- ohashes.copyInto(destination = hashes, endIndex = ohashes.size)
- oarray.copyInto(destination = array, endIndex = oarray.size)
- }
- }
-
- if (index < oSize) {
- printlnIfDebug { "$TAG add: move $index-${oSize - index} to ${index + 1}" }
-
- hashes.copyInto(
- destination = hashes,
- destinationOffset = index + 1,
- startIndex = index,
- endIndex = oSize
- )
- array.copyInto(
- destination = array,
- destinationOffset = index + 1,
- startIndex = index,
- endIndex = oSize
- )
- }
-
- if (oSize != _size || index >= hashes.size) {
- throw ConcurrentModificationException()
- }
-
- hashes[index] = hash
- array[index] = element
- _size++
- return true
- }
+ override fun add(element: E): Boolean
/**
* 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 fun addAll(array: ArraySet<out E>) {
- val n = array._size
- ensureCapacity(_size + n)
- if (_size == 0) {
- if (n > 0) {
- array.hashes.copyInto(destination = hashes, endIndex = n)
- array.array.copyInto(destination = this.array, endIndex = n)
- if (0 != _size) {
- throw ConcurrentModificationException()
- }
- _size = n
- }
- } else {
- for (i in 0 until n) {
- add(array.valueAt(i))
- }
- }
- }
+ public fun addAll(array: ArraySet<out E>)
/**
* Removes the specified object from this set.
@@ -348,125 +152,23 @@
* @param element the object to remove.
* @return `true` if this set was modified, `false` otherwise.
*/
- override fun remove(element: E): Boolean {
- val index = indexOf(element)
- if (index >= 0) {
- removeAt(index)
- return true
- }
- return false
- }
+ override fun remove(element: E): Boolean
/**
* 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 fun removeAt(index: Int): E {
- val oSize = _size
- val old = array[index]
- if (oSize <= 1) {
- // Now empty.
- printlnIfDebug { "$TAG remove: shrink from ${hashes.size} to 0" }
- clear()
- } else {
- val nSize = oSize - 1
- if (hashes.size > (BASE_SIZE * 2) && (_size < hashes.size / 3)) {
- // Shrunk enough to reduce size of arrays. We don't allow it to
- // shrink smaller than (BASE_SIZE*2) to avoid flapping between
- // that and BASE_SIZE.
- val n = if (_size > BASE_SIZE * 2) _size + (_size shr 1) else BASE_SIZE * 2
- printlnIfDebug { "$TAG remove: shrink from ${hashes.size} to $n" }
- val ohashes = hashes
- val oarray = array
- allocArrays(n)
- if (index > 0) {
- printlnIfDebug { "$TAG remove: copy from 0-$index to 0" }
- ohashes.copyInto(destination = hashes, endIndex = index)
- oarray.copyInto(destination = array, endIndex = index)
- }
- if (index < nSize) {
- printlnIfDebug { "$TAG remove: copy from ${index + 1}-$nSize to $index" }
- ohashes.copyInto(
- destination = hashes,
- destinationOffset = index,
- startIndex = index + 1,
- endIndex = nSize + 1
- )
- oarray.copyInto(
- destination = array,
- destinationOffset = index,
- startIndex = index + 1,
- endIndex = nSize + 1
- )
- }
- } else {
- if (index < nSize) {
- printlnIfDebug { "$TAG remove: move ${index + 1}-$nSize to $index" }
- hashes.copyInto(
- destination = hashes,
- destinationOffset = index,
- startIndex = index + 1,
- endIndex = nSize + 1
- )
- array.copyInto(
- destination = array,
- destinationOffset = index,
- startIndex = index + 1,
- endIndex = nSize + 1
- )
- }
- array[nSize] = null
- }
- if (oSize != _size) {
- throw ConcurrentModificationException()
- }
- _size = nSize
- }
- @Suppress("UNCHECKED_CAST")
- return old as E
- }
+ public fun removeAt(index: Int): E
/**
* Perform a [remove] of all values in [array]
+ *
* @param array The array whose contents are to be removed.
*/
- public fun removeAll(array: ArraySet<out E>): Boolean {
- // TODO: If array is sufficiently large, a marking approach might be beneficial. In a first
- // pass, use the property that the sets are sorted by hash to make this linear passes
- // (except for hash collisions, which means worst case still n*m), then do one
- // collection pass into a new array. This avoids binary searches and excessive memcpy.
- val n = array._size
-
- // Note: ArraySet does not make thread-safety guarantees. So instead of OR-ing together all
- // the single results, compare size before and after.
- val originalSize = _size
- for (i in 0 until n) {
- remove(array.valueAt(i))
- }
- return originalSize != _size
- }
-
- @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> {
- return if (array.size < _size) {
- @Suppress("UNCHECKED_CAST")
- this.array.copyOfRange(fromIndex = 0, toIndex = _size) as Array<T>
- } else {
- @Suppress("UNCHECKED_CAST")
- this.array.copyInto(array as Array<Any?>, 0, 0, _size)
- if (array.size > _size) {
- array[_size] = null
- }
- array
- }
- }
+ public fun removeAll(array: ArraySet<out E>): Boolean
/**
* This implementation returns false if the object is not a set, or
@@ -477,70 +179,19 @@
*
* @see Any.equals
*/
- override fun equals(other: Any?): Boolean {
- if (this === other) {
- return true
- }
- if (other is Set<*>) {
- if (size != other.size) {
- return false
- }
- try {
- for (i in 0 until _size) {
- val mine = valueAt(i)
- if (!other.contains(mine)) {
- return false
- }
- }
- } catch (ignored: NullPointerException) {
- return false
- } catch (ignored: ClassCastException) {
- return false
- }
- return true
- }
- return false
- }
+ override fun equals(other: Any?): Boolean
/**
* @see Any.hashCode
*/
- override fun hashCode(): Int {
- val hashes = hashes
- val s = _size
- var result = 0
- for (i in 0 until s) {
- result += hashes[i]
- }
- return result
- }
+ override fun hashCode(): Int
/**
* 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.
*/
- override fun toString(): String {
- if (isEmpty()) {
- return "{}"
- }
-
- return buildString(capacity = _size * 14) {
- append('{')
- for (i in 0 until _size) {
- if (i > 0) {
- append(", ")
- }
- val value = valueAt(i)
- if (value !== this@ArraySet) {
- append(value)
- } else {
- append("(this Set)")
- }
- }
- append('}')
- }
- }
+ override fun toString(): String
/**
* Return a [MutableIterator] over all values in the set.
@@ -548,84 +199,430 @@
* **Note:** this is a less efficient way to access the array contents compared to
* looping from 0 until [size] and calling [valueAt].
*/
- 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) {
- [email protected](index)
- }
- }
+ override fun iterator(): MutableIterator<E>
/**
* 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.
*/
- override fun containsAll(elements: Collection<E>): Boolean {
- for (item in elements) {
- if (!contains(item)) {
- return false
- }
- }
- return true
- }
+ override fun containsAll(elements: Collection<E>): Boolean
/**
* Perform an [add] of all values in [elements]
+ *
* @param elements The collection whose contents are to be retrieved.
*/
- override fun addAll(elements: Collection<E>): Boolean {
- ensureCapacity(_size + elements.size)
- var added = false
- for (value in elements) {
- added = add(value) or added
- }
- return added
- }
+ override fun addAll(elements: Collection<E>): Boolean
/**
* 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.
*/
- override fun removeAll(elements: Collection<E>): Boolean {
- var removed = false
- for (value in elements) {
- removed = removed or remove(value)
- }
- return removed
- }
+ override fun removeAll(elements: Collection<E>): Boolean
/**
* 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.
*/
- override fun retainAll(elements: Collection<E>): Boolean {
- var removed = false
- for (i in _size - 1 downTo 0) {
- if (array[i] !in elements) {
- removeAt(i)
- removed = true
+ override fun retainAll(elements: Collection<E>): Boolean
+}
+
+/**
+ * The minimum amount by which the capacity of a ArraySet will increase.
+ * This is tuned to be relatively space-efficient.
+ */
+internal const val ARRAY_SET_BASE_SIZE = 4
+
+internal fun <E> ArraySet<E>.binarySearchInternal(hash: Int): Int =
+ try {
+ binarySearch(hashes, _size, hash)
+ } catch (e: IndexOutOfBoundsException) {
+ throw ConcurrentModificationException()
+ }
+
+internal fun <E> ArraySet<E>.indexOf(key: Any?, hash: Int): Int {
+ val n = _size
+
+ // Important fast case: if nothing is in here, nothing to look for.
+ if (n == 0) {
+ return -1
+ }
+ val index = binarySearchInternal(hash)
+
+ // If the hash code wasn't found, then we have no entry for this key.
+ if (index < 0) {
+ return index
+ }
+
+ // If the key at the returned index matches, that's what we want.
+ if (key == array[index]) {
+ return index
+ }
+
+ // Search for a matching key after the index.
+ var end = index + 1
+ while (end < n && hashes[end] == hash) {
+ if (key == array[end]) {
+ return end
+ }
+ end++
+ }
+
+ // Search for a matching key before the index.
+ var i = index - 1
+ while (i >= 0 && hashes[i] == hash) {
+ if (key == array[i]) {
+ return i
+ }
+ i--
+ }
+
+ // Key not found -- return negative value indicating where a
+ // new entry for this key should go. We use the end of the
+ // hash chain to reduce the number of array entries that will
+ // need to be copied when inserting.
+ return end.inv()
+}
+
+internal fun <E> ArraySet<E>.indexOfNull(): Int = indexOf(key = null, hash = 0)
+
+internal fun <E> ArraySet<E>.allocArrays(size: Int) {
+ hashes = IntArray(size)
+ array = arrayOfNulls(size)
+}
+
+@Suppress("NOTHING_TO_INLINE")
+internal inline fun <E> ArraySet<E>.clearInternal() {
+ if (_size != 0) {
+ hashes = EMPTY_INTS
+ array = EMPTY_OBJECTS
+ _size = 0
+ }
+ @Suppress("KotlinConstantConditions")
+ if (_size != 0) {
+ throw ConcurrentModificationException()
+ }
+}
+
+@Suppress("NOTHING_TO_INLINE")
+internal inline fun <E> ArraySet<E>.ensureCapacityInternal(minimumCapacity: Int) {
+ val oSize: Int = _size
+ if (hashes.size < minimumCapacity) {
+ val ohashes = hashes
+ val oarray = array
+ allocArrays(minimumCapacity)
+ if (_size > 0) {
+ ohashes.copyInto(destination = hashes, endIndex = _size)
+ oarray.copyInto(destination = array, endIndex = _size)
+ }
+ }
+ if (_size != oSize) {
+ throw ConcurrentModificationException()
+ }
+}
+
+@Suppress("NOTHING_TO_INLINE")
+internal inline fun <E> ArraySet<E>.containsInternal(element: E): Boolean {
+ return indexOf(element) >= 0
+}
+
+@Suppress("NOTHING_TO_INLINE")
+internal inline fun <E> ArraySet<E>.indexOfInternal(key: Any?): Int {
+ return if (key == null) indexOfNull() else indexOf(key = key, hash = key.hashCode())
+}
+
+@Suppress("NOTHING_TO_INLINE")
+internal inline fun <E> ArraySet<E>.valueAtInternal(index: Int): E {
+ @Suppress("UNCHECKED_CAST")
+ return array[index] as E
+}
+
+@Suppress("NOTHING_TO_INLINE")
+internal inline fun <E> ArraySet<E>.isEmptyInternal(): Boolean {
+ return _size <= 0
+}
+
+@Suppress("NOTHING_TO_INLINE")
+internal inline fun <E> ArraySet<E>.addInternal(element: E): Boolean {
+ val oSize = _size
+ val hash: Int
+ var index: Int
+ if (element == null) {
+ hash = 0
+ index = indexOfNull()
+ } else {
+ hash = element.hashCode()
+ index = indexOf(element, hash)
+ }
+
+ if (index >= 0) {
+ return false
+ }
+
+ index = index.inv()
+ if (oSize >= hashes.size) {
+ val n =
+ when {
+ oSize >= ARRAY_SET_BASE_SIZE * 2 -> oSize + (oSize shr 1)
+ oSize >= ARRAY_SET_BASE_SIZE -> ARRAY_SET_BASE_SIZE * 2
+ else -> ARRAY_SET_BASE_SIZE
+ }
+
+ val ohashes = hashes
+ val oarray = array
+ allocArrays(n)
+
+ if (oSize != _size) {
+ throw ConcurrentModificationException()
+ }
+
+ if (hashes.isNotEmpty()) {
+ ohashes.copyInto(destination = hashes, endIndex = ohashes.size)
+ oarray.copyInto(destination = array, endIndex = oarray.size)
+ }
+ }
+
+ if (index < oSize) {
+ hashes.copyInto(
+ destination = hashes,
+ destinationOffset = index + 1,
+ startIndex = index,
+ endIndex = oSize
+ )
+ array.copyInto(
+ destination = array,
+ destinationOffset = index + 1,
+ startIndex = index,
+ endIndex = oSize
+ )
+ }
+
+ if (oSize != _size || index >= hashes.size) {
+ throw ConcurrentModificationException()
+ }
+
+ hashes[index] = hash
+ array[index] = element
+ _size++
+ return true
+}
+
+@Suppress("NOTHING_TO_INLINE")
+internal inline fun <E> ArraySet<E>.addAllInternal(array: ArraySet<out E>) {
+ val n = array._size
+ ensureCapacity(_size + n)
+ if (_size == 0) {
+ if (n > 0) {
+ array.hashes.copyInto(destination = hashes, endIndex = n)
+ array.array.copyInto(destination = this.array, endIndex = n)
+ if (0 != _size) {
+ throw ConcurrentModificationException()
+ }
+ _size = n
+ }
+ } else {
+ for (i in 0 until n) {
+ add(array.valueAt(i))
+ }
+ }
+}
+
+@Suppress("NOTHING_TO_INLINE")
+internal inline fun <E> ArraySet<E>.removeInternal(element: E): Boolean {
+ val index = indexOf(element)
+ if (index >= 0) {
+ removeAt(index)
+ return true
+ }
+ return false
+}
+
+@Suppress("NOTHING_TO_INLINE")
+internal inline fun <E> ArraySet<E>.removeAtInternal(index: Int): E {
+ val oSize = _size
+ val old = array[index]
+ if (oSize <= 1) {
+ // Now empty.
+ clear()
+ } else {
+ val nSize = oSize - 1
+ if (hashes.size > (ARRAY_SET_BASE_SIZE * 2) && (_size < hashes.size / 3)) {
+ // Shrunk enough to reduce size of arrays. We don't allow it to
+ // shrink smaller than (ARRAY_SET_BASE_SIZE*2) to avoid flapping between
+ // that and ARRAY_SET_BASE_SIZE.
+ val n = when {
+ _size > ARRAY_SET_BASE_SIZE * 2 -> _size + (_size shr 1)
+ else -> ARRAY_SET_BASE_SIZE * 2
+ }
+ val ohashes = hashes
+ val oarray = array
+ allocArrays(n)
+ if (index > 0) {
+ ohashes.copyInto(destination = hashes, endIndex = index)
+ oarray.copyInto(destination = array, endIndex = index)
+ }
+ if (index < nSize) {
+ ohashes.copyInto(
+ destination = hashes,
+ destinationOffset = index,
+ startIndex = index + 1,
+ endIndex = nSize + 1
+ )
+ oarray.copyInto(
+ destination = array,
+ destinationOffset = index,
+ startIndex = index + 1,
+ endIndex = nSize + 1
+ )
+ }
+ } else {
+ if (index < nSize) {
+ hashes.copyInto(
+ destination = hashes,
+ destinationOffset = index,
+ startIndex = index + 1,
+ endIndex = nSize + 1
+ )
+ array.copyInto(
+ destination = array,
+ destinationOffset = index,
+ startIndex = index + 1,
+ endIndex = nSize + 1
+ )
+ }
+ array[nSize] = null
+ }
+ if (oSize != _size) {
+ throw ConcurrentModificationException()
+ }
+ _size = nSize
+ }
+ @Suppress("UNCHECKED_CAST")
+ return old as E
+}
+
+@Suppress("NOTHING_TO_INLINE")
+internal inline fun <E> ArraySet<E>.removeAllInternal(array: ArraySet<out E>): Boolean {
+ // TODO: If array is sufficiently large, a marking approach might be beneficial. In a first
+ // pass, use the property that the sets are sorted by hash to make this linear passes
+ // (except for hash collisions, which means worst case still n*m), then do one
+ // collection pass into a new array. This avoids binary searches and excessive memcpy.
+ val n = array._size
+
+ // Note: ArraySet does not make thread-safety guarantees. So instead of OR-ing together all
+ // the single results, compare size before and after.
+ val originalSize = _size
+ for (i in 0 until n) {
+ remove(array.valueAt(i))
+ }
+ return originalSize != _size
+}
+
+@Suppress("NOTHING_TO_INLINE")
+internal inline fun <E> ArraySet<E>.equalsInternal(other: Any?): Boolean {
+ if (this === other) {
+ return true
+ }
+ if (other is Set<*>) {
+ if (size != other.size) {
+ return false
+ }
+ try {
+ for (i in 0 until _size) {
+ val mine = valueAt(i)
+ if (!other.contains(mine)) {
+ return false
+ }
+ }
+ } catch (ignored: NullPointerException) {
+ return false
+ } catch (ignored: ClassCastException) {
+ return false
+ }
+ return true
+ }
+ return false
+}
+
+@Suppress("NOTHING_TO_INLINE")
+internal inline fun <E> ArraySet<E>.hashCodeInternal(): Int {
+ val hashes = hashes
+ val s = _size
+ var result = 0
+ for (i in 0 until s) {
+ result += hashes[i]
+ }
+ return result
+}
+
+@Suppress("NOTHING_TO_INLINE")
+internal inline fun <E> ArraySet<E>.toStringInternal(): String {
+ if (isEmpty()) {
+ return "{}"
+ }
+
+ return buildString(capacity = _size * 14) {
+ append('{')
+ for (i in 0 until _size) {
+ if (i > 0) {
+ append(", ")
+ }
+ val value = valueAt(i)
+ if (value !== this@toStringInternal) {
+ append(value)
+ } else {
+ append("(this Set)")
}
}
- return removed
+ append('}')
}
+}
- private companion object {
- private const val DEBUG = false
- private const val TAG = "ArraySet"
-
- /**
- * The minimum amount by which the capacity of a ArraySet will increase.
- * This is tuned to be relatively space-efficient.
- */
- private const val BASE_SIZE = 4
+@Suppress("NOTHING_TO_INLINE")
+internal inline fun <E> ArraySet<E>.containsAllInternal(elements: Collection<E>): Boolean {
+ for (item in elements) {
+ if (!contains(item)) {
+ return false
+ }
}
+ return true
+}
+
+@Suppress("NOTHING_TO_INLINE")
+internal inline fun <E> ArraySet<E>.addAllInternal(elements: Collection<E>): Boolean {
+ ensureCapacity(_size + elements.size)
+ var added = false
+ for (value in elements) {
+ added = add(value) or added
+ }
+ return added
+}
+
+@Suppress("NOTHING_TO_INLINE")
+internal inline fun <E> ArraySet<E>.removeAllInternal(elements: Collection<E>): Boolean {
+ var removed = false
+ for (value in elements) {
+ removed = removed or remove(value)
+ }
+ return removed
+}
+
+@Suppress("NOTHING_TO_INLINE")
+internal inline fun <E> ArraySet<E>.retainAllInternal(elements: Collection<E>): Boolean {
+ var removed = false
+ for (i in _size - 1 downTo 0) {
+ if (array[i] !in elements) {
+ removeAt(i)
+ removed = true
+ }
+ }
+ return removed
}
diff --git a/collection/collection/src/commonTest/kotlin/androidx/collection/ArraySetTest.kt b/collection/collection/src/commonTest/kotlin/androidx/collection/ArraySetTest.kt
index 365694f..257a876 100644
--- a/collection/collection/src/commonTest/kotlin/androidx/collection/ArraySetTest.kt
+++ b/collection/collection/src/commonTest/kotlin/androidx/collection/ArraySetTest.kt
@@ -35,7 +35,6 @@
import kotlinx.coroutines.runBlocking
internal class ArraySetTest {
-
private val set = ArraySet<String>()
/**
diff --git a/collection/collection/src/jvmMain/java/androidx/collection/ArraySetJvmUtil.java b/collection/collection/src/jvmMain/java/androidx/collection/ArraySetJvmUtil.java
new file mode 100644
index 0000000..13642b6
--- /dev/null
+++ b/collection/collection/src/jvmMain/java/androidx/collection/ArraySetJvmUtil.java
@@ -0,0 +1,39 @@
+/*
+ * 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 java.lang.reflect.Array;
+
+class ArraySetJvmUtil {
+ private ArraySetJvmUtil() {
+ }
+
+ // Necessary to implement in Java to allow allocating a typed array without a callback for
+ // initialization. We also need to ignore the nullity of the type in order to null out the
+ // (n+1)'th item for behavior compatibility.
+ @SuppressWarnings("unchecked")
+ static <T> T[] resizeForToArray(T[] destination, int size) {
+ if (destination.length < size) {
+ return (T[]) Array.newInstance(destination.getClass().getComponentType(), size);
+ } else {
+ if (destination.length > size) {
+ destination[size] = null;
+ }
+ return destination;
+ }
+ }
+}
diff --git a/collection/collection/src/jvmMain/kotlin/androidx/collection/ArraySet.jvm.kt b/collection/collection/src/jvmMain/kotlin/androidx/collection/ArraySet.jvm.kt
new file mode 100644
index 0000000..e804ff1
--- /dev/null
+++ b/collection/collection/src/jvmMain/kotlin/androidx/collection/ArraySet.jvm.kt
@@ -0,0 +1,302 @@
+/*
+ * 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) {
+ [email protected](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)
+ }
+}
diff --git a/collection/collection/src/jvmTest/kotlin/androidx/collection/ArraySetJvmTest.kt b/collection/collection/src/jvmTest/kotlin/androidx/collection/ArraySetJvmTest.kt
new file mode 100644
index 0000000..df77ccc
--- /dev/null
+++ b/collection/collection/src/jvmTest/kotlin/androidx/collection/ArraySetJvmTest.kt
@@ -0,0 +1,47 @@
+/*
+ * 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 kotlin.test.assertNull
+import org.junit.Test
+
+class ArraySetJvmTest {
+
+ @Test
+ fun toArray_emptyTypedDestination() {
+ val set = ArraySet<Int>()
+ for (i in 0..5) {
+ set.add(i)
+ }
+
+ // Forces casting, otherwise may not pick up certain failures. Typing just the destination
+ // array or return type is not sufficient to test on JVM.
+ @Suppress("UNUSED_VARIABLE")
+ val result: Array<Int> = set.toArray(emptyArray())
+ }
+
+ @Test
+ fun toArray_nullsLastElement() {
+ val set = ArraySet<Int>()
+ for (i in 0..4) {
+ set.add(i)
+ }
+
+ val result: Array<Int> = set.toArray(Array(10) { -1 })
+ assertNull(result[5])
+ }
+}
\ No newline at end of file
diff --git a/collection/collection/src/nativeMain/kotlin/androidx/collection/ArraySet.native.kt b/collection/collection/src/nativeMain/kotlin/androidx/collection/ArraySet.native.kt
new file mode 100644
index 0000000..9c7be56
--- /dev/null
+++ b/collection/collection/src/nativeMain/kotlin/androidx/collection/ArraySet.native.kt
@@ -0,0 +1,285 @@
+/*
+ * 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> actual constructor(
+ capacity: Int
+) : 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)
+ }
+
+ /**
+ * 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) {
+ [email protected](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 removeAll(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)
+ }
+}
