Alexander Shabalin
415 lines
14 KiB
Kotlin
415 lines
14 KiB
Kotlin
/*
|
|
* Copyright 2010-2023 JetBrains s.r.o. and Kotlin Programming Language contributors.
|
|
* Use of this source code is governed by the Apache 2.0 license that can be found in the license/LICENSE.txt file.
|
|
*/
|
|
|
|
package test.collections
|
|
|
|
import kotlin.test.*
|
|
|
|
private fun assertContainsOnly(bitSet: BitSet, trueBits: Set<Int>, size: Int) {
|
|
for (i in 0 until size) {
|
|
assertEquals(i in trueBits, bitSet[i])
|
|
}
|
|
}
|
|
|
|
private fun assertNotContainsOnly(bitSet: BitSet, falseBits: Set<Int>, size: Int) {
|
|
for (i in 0 until size) {
|
|
assertNotEquals(i in falseBits, bitSet[i])
|
|
}
|
|
}
|
|
|
|
class BitSetTest {
|
|
@Test fun constructor() {
|
|
var b = BitSet(12)
|
|
assertContainsOnly(b, setOf(), 12)
|
|
|
|
b = BitSet(12) { it == 0 || it in 5..6 || it == 11 }
|
|
assertContainsOnly(b, setOf(0, 5, 6, 11), 12)
|
|
}
|
|
|
|
@Test fun set() {
|
|
var b = BitSet(0)
|
|
assertEquals(b.lastTrueIndex, -1)
|
|
b = BitSet(2)
|
|
// Test set and clear operation for single index.
|
|
assertTrue(b.isEmpty)
|
|
b.set(0, true)
|
|
b.set(3, true)
|
|
assertEquals(b.lastTrueIndex, 3)
|
|
assertFalse(b.isEmpty)
|
|
assertContainsOnly(b, setOf(0, 3), 4)
|
|
b.clear()
|
|
assertContainsOnly(b, setOf(), 4)
|
|
b.set(1)
|
|
b.set(5)
|
|
assertEquals(b.lastTrueIndex, 5)
|
|
assertContainsOnly(b, setOf(1, 5), 6)
|
|
b.set(1, false)
|
|
b.set(7, false)
|
|
assertEquals(b.lastTrueIndex, 5)
|
|
assertContainsOnly(b, setOf(5), 8)
|
|
b.clear(5)
|
|
assertEquals(b.lastTrueIndex, -1)
|
|
assertContainsOnly(b, setOf(), 8)
|
|
b.set(70)
|
|
assertEquals(b.lastTrueIndex, 70)
|
|
assertContainsOnly(b, setOf(70), 71)
|
|
b.clear(70)
|
|
assertEquals(b.lastTrueIndex, -1)
|
|
assertContainsOnly(b, setOf(), 71)
|
|
|
|
// Test set and clear operations for ranges.
|
|
// Set false and clear.
|
|
b = BitSet(2)
|
|
assertContainsOnly(b, setOf(), 2)
|
|
b.set(0..70, true)
|
|
assertNotContainsOnly(b, setOf(), 71)
|
|
b.set(0..2, false)
|
|
assertNotContainsOnly(b, setOf(0, 1, 2), 71)
|
|
b.set(63..65, false)
|
|
assertNotContainsOnly(b, setOf(0, 1, 2, 63, 64, 65), 71)
|
|
b.set(68..70, false)
|
|
assertNotContainsOnly(b, setOf(0, 1, 2, 63, 64, 65, 68, 69, 70), 71)
|
|
b.set(68..72, false)
|
|
assertNotContainsOnly(b, setOf(0, 1, 2, 63, 64, 65, 68, 69, 70, 71, 72), 73)
|
|
b.set(0..72, false)
|
|
assertContainsOnly(b, setOf(), 73)
|
|
|
|
b.set(0..72)
|
|
assertNotContainsOnly(b, setOf(), 73)
|
|
b.clear(0..2)
|
|
assertNotContainsOnly(b, setOf(0, 1, 2), 73)
|
|
b.clear(63..65)
|
|
assertNotContainsOnly(b, setOf(0, 1, 2, 63, 64, 65), 73)
|
|
b.clear(68..70)
|
|
assertNotContainsOnly(b, setOf(0, 1, 2, 63, 64, 65, 68, 69, 70), 73)
|
|
b.clear(68..72)
|
|
assertNotContainsOnly(b, setOf(0, 1, 2, 63, 64, 65, 68, 69, 70, 71, 72), 73)
|
|
b.clear(0..72)
|
|
assertContainsOnly(b, setOf(), 73)
|
|
|
|
// Set true.
|
|
b.set(0..2, true)
|
|
assertContainsOnly(b, setOf(0, 1, 2), 73)
|
|
b.set(63..65, true)
|
|
assertContainsOnly(b, setOf(0, 1, 2, 63, 64, 65), 73)
|
|
b.set(70..72, true)
|
|
assertContainsOnly(b, setOf(0, 1, 2, 63, 64, 65, 70, 71, 72), 73)
|
|
b.set(73..74, true)
|
|
assertContainsOnly(b, setOf(0, 1, 2, 63, 64, 65, 70, 71, 72, 73, 74), 75)
|
|
b.set(0..74, true)
|
|
assertNotContainsOnly(b, setOf(), 75)
|
|
|
|
// Test set and clear for pair of indices.
|
|
b = BitSet(2)
|
|
assertContainsOnly(b, setOf(), 71)
|
|
b.set(0, 71, true)
|
|
assertNotContainsOnly(b, setOf(), 71)
|
|
b.set(0, 3, false)
|
|
assertNotContainsOnly(b, setOf(0, 1, 2), 71)
|
|
b.set(63, 66, false)
|
|
assertNotContainsOnly(b, setOf(0, 1, 2, 63, 64, 65), 71)
|
|
b.set(68, 71, false)
|
|
assertNotContainsOnly(b, setOf(0, 1, 2, 63, 64, 65, 68, 69, 70), 71)
|
|
b.set(68, 73, false)
|
|
assertNotContainsOnly(b, setOf(0, 1, 2, 63, 64, 65, 68, 69, 70, 71, 72), 73)
|
|
b.set(0, 73, false)
|
|
assertContainsOnly(b, setOf(), 73)
|
|
|
|
b.set(0, 73)
|
|
assertNotContainsOnly(b, setOf(), 73)
|
|
b.clear(0, 3)
|
|
assertNotContainsOnly(b, setOf(0, 1, 2), 73)
|
|
b.clear(63, 66)
|
|
assertNotContainsOnly(b, setOf(0, 1, 2, 63, 64, 65), 73)
|
|
b.clear(68, 71)
|
|
assertNotContainsOnly(b, setOf(0, 1, 2, 63, 64, 65, 68, 69, 70), 73)
|
|
b.clear(68, 73)
|
|
assertNotContainsOnly(b, setOf(0, 1, 2, 63, 64, 65, 68, 69, 70, 71, 72), 73)
|
|
b.clear(0, 73)
|
|
assertContainsOnly(b, setOf(), 73)
|
|
|
|
// Set true.
|
|
b.set(0, 3, true)
|
|
assertContainsOnly(b, setOf(0, 1, 2), 73)
|
|
b.set(63, 66, true)
|
|
assertContainsOnly(b, setOf(0, 1, 2, 63, 64, 65), 73)
|
|
b.set(70, 73, true)
|
|
assertContainsOnly(b, setOf(0, 1, 2, 63, 64, 65, 70, 71, 72), 73)
|
|
b.set(73, 75, true)
|
|
assertContainsOnly(b, setOf(0, 1, 2, 63, 64, 65, 70, 71, 72, 73, 74), 75)
|
|
b.set(0, 75, true)
|
|
assertNotContainsOnly(b, setOf(), 75)
|
|
|
|
// Access to negative elements must cause an exception
|
|
assertFailsWith<IndexOutOfBoundsException> {
|
|
b.set(-1)
|
|
}
|
|
assertFailsWith<IndexOutOfBoundsException> {
|
|
b.clear(-1)
|
|
}
|
|
assertFailsWith<IndexOutOfBoundsException> {
|
|
b.clear(-1..0)
|
|
}
|
|
assertFailsWith<IndexOutOfBoundsException> {
|
|
b.set(-1..0)
|
|
}
|
|
assertFailsWith<IndexOutOfBoundsException> {
|
|
b[-1]
|
|
}
|
|
}
|
|
|
|
@Test fun flip() {
|
|
val b = BitSet(2)
|
|
b.set(0, true)
|
|
b.set(70, true)
|
|
b.set(63..65, true)
|
|
assertEquals(b.lastTrueIndex, 70)
|
|
// 0 element
|
|
assertContainsOnly(b, setOf(0, 63, 64, 65, 70), 71)
|
|
b.flip(0)
|
|
assertContainsOnly(b, setOf(63, 64, 65, 70), 71)
|
|
b.flip(1)
|
|
assertContainsOnly(b, setOf(1, 63, 64, 65, 70), 71)
|
|
b.flip(0)
|
|
assertContainsOnly(b, setOf(0, 1, 63, 64, 65, 70), 71)
|
|
|
|
// last element
|
|
b.flip(70)
|
|
assertContainsOnly(b, setOf(0, 1, 63, 64, 65), 71)
|
|
b.flip(69)
|
|
assertContainsOnly(b, setOf(0, 1, 63, 64, 65, 69), 71)
|
|
b.flip(70)
|
|
assertContainsOnly(b, setOf(0, 1, 63, 64, 65, 69, 70), 71)
|
|
|
|
// element in the middle
|
|
b.flip(64)
|
|
assertContainsOnly(b, setOf(0, 1, 63, 65, 69, 70), 71)
|
|
b.flip(65)
|
|
assertContainsOnly(b, setOf(0, 1, 63, 69, 70), 71)
|
|
b.flip(65)
|
|
b.flip(64)
|
|
assertContainsOnly(b, setOf(0, 1, 63, 64, 65, 69, 70), 71)
|
|
|
|
// range in the beginning
|
|
b.flip(0..2)
|
|
assertContainsOnly(b, setOf(2, 63, 64, 65, 69, 70), 71)
|
|
b.flip(0, 3)
|
|
assertContainsOnly(b, setOf(0, 1, 63, 64, 65, 69, 70), 71)
|
|
|
|
// In the end
|
|
b.flip(68..70)
|
|
assertContainsOnly(b, setOf(0, 1, 63, 64, 65, 68), 71)
|
|
b.flip(68, 71)
|
|
assertContainsOnly(b, setOf(0, 1, 63, 64, 65, 69, 70), 71)
|
|
|
|
// In the middle
|
|
b.flip(64..66)
|
|
assertContainsOnly(b, setOf(0, 1, 63, 66, 69, 70), 71)
|
|
b.flip(64, 67)
|
|
assertContainsOnly(b, setOf(0, 1, 63, 64, 65, 69, 70), 71)
|
|
|
|
// Access to a negative element must cause an exception.
|
|
assertFailsWith<IndexOutOfBoundsException> {
|
|
b.flip(-1)
|
|
}
|
|
assertFailsWith<IndexOutOfBoundsException> {
|
|
b.flip(-1..0)
|
|
}
|
|
}
|
|
|
|
@Test fun nextBit() {
|
|
val b = BitSet(71)
|
|
b.set(0)
|
|
b.set(65)
|
|
b.set(70)
|
|
assertEquals(b.nextSetBit(), 0)
|
|
assertEquals(b.nextSetBit(0), 0)
|
|
assertEquals(b.nextSetBit(1), 65)
|
|
assertEquals(b.nextSetBit(65), 65)
|
|
assertEquals(b.nextSetBit(66), 70)
|
|
assertEquals(b.nextSetBit(70), 70)
|
|
assertEquals(b.nextSetBit(71), -1)
|
|
|
|
assertEquals(b.previousSetBit(0), 0)
|
|
assertEquals(b.previousSetBit(64), 0)
|
|
assertEquals(b.previousSetBit(65), 65)
|
|
assertEquals(b.previousSetBit(69), 65)
|
|
assertEquals(b.previousSetBit(70), 70)
|
|
assertEquals(b.previousSetBit(71), 70)
|
|
|
|
b.clear()
|
|
assertEquals(b.nextSetBit(), -1)
|
|
assertEquals(b.previousSetBit(70), -1)
|
|
|
|
b.set(0..70)
|
|
assertEquals(b.nextClearBit(), 71)
|
|
assertEquals(b.previousClearBit(70), -1)
|
|
|
|
b.clear(0)
|
|
b.clear(65)
|
|
b.clear(70)
|
|
assertEquals(b.nextClearBit(), 0)
|
|
assertEquals(b.nextClearBit(0), 0)
|
|
assertEquals(b.nextClearBit(1), 65)
|
|
assertEquals(b.nextClearBit(65), 65)
|
|
assertEquals(b.nextClearBit(66), 70)
|
|
assertEquals(b.nextClearBit(70), 70)
|
|
assertEquals(b.nextClearBit(71), 71) // assume that the bitset is extended here (virtually).
|
|
|
|
assertEquals(b.previousClearBit(0), 0)
|
|
assertEquals(b.previousClearBit(64), 0)
|
|
assertEquals(b.previousClearBit(65), 65)
|
|
assertEquals(b.previousClearBit(69), 65)
|
|
assertEquals(b.previousClearBit(70), 70)
|
|
assertEquals(b.previousClearBit(71), 71)
|
|
|
|
// See http://docs.oracle.com/javase/8/docs/api/java/util/BitSet.html#previousClearBit-int-
|
|
assertEquals(b.previousClearBit(-1), -1)
|
|
assertEquals(b.previousSetBit(-1), -1)
|
|
|
|
// Test behaviour on the right border of the bit vector.
|
|
// We assume that the vector is infinite and have zeros after (size - 1)th bit.
|
|
var a = BitSet(64)
|
|
assertEquals(a.nextClearBit(63), 63)
|
|
assertEquals(a.nextClearBit(64), 64)
|
|
assertEquals(a.nextSetBit(63), -1)
|
|
assertEquals(a.nextSetBit(64), -1)
|
|
a.set(0, 64)
|
|
assertEquals(a.nextClearBit(63), 64)
|
|
assertEquals(a.nextClearBit(64), 64)
|
|
assertEquals(a.nextSetBit(63), 63)
|
|
assertEquals(a.nextSetBit(64), -1)
|
|
|
|
a.clear()
|
|
assertEquals(a.previousClearBit(63), 63)
|
|
assertEquals(a.previousClearBit(64), 64)
|
|
assertEquals(a.previousSetBit(63), -1)
|
|
assertEquals(a.previousSetBit(64), -1)
|
|
a.set(0, 64)
|
|
assertEquals(a.previousClearBit(63), -1)
|
|
assertEquals(a.previousClearBit(64), 64)
|
|
assertEquals(a.previousSetBit(63), 63)
|
|
assertEquals(a.previousSetBit(64), 63)
|
|
|
|
a = BitSet(0)
|
|
assertEquals(a.nextSetBit(0), -1)
|
|
assertEquals(a.nextClearBit(0), 0)
|
|
assertEquals(a.previousSetBit(0), -1)
|
|
assertEquals(a.previousClearBit(0), 0)
|
|
|
|
// Access to a negative element must cause an exception.
|
|
assertFailsWith<IndexOutOfBoundsException> {
|
|
b.previousSetBit(-2)
|
|
}
|
|
assertFailsWith<IndexOutOfBoundsException> {
|
|
b.previousClearBit(-2)
|
|
}
|
|
assertFailsWith<IndexOutOfBoundsException> {
|
|
b.nextSetBit(-1)
|
|
}
|
|
assertFailsWith<IndexOutOfBoundsException> {
|
|
b.nextClearBit(-1)
|
|
}
|
|
}
|
|
|
|
@Test fun logic() {
|
|
var b2 = BitSet(76)
|
|
intArrayOf(1, 3, 61, 63, 65, 67, 70, 72).forEach {
|
|
b2.set(it)
|
|
}
|
|
|
|
// and
|
|
var b1 = BitSet(73)
|
|
b1.set(2..3); b1.set(62..63); b1.set(66..67); b1.set(71..72)
|
|
b1.and(b2)
|
|
assertContainsOnly(b1, setOf(3, 63, 67, 72), 76)
|
|
b1 = BitSet(73)
|
|
b1.set(2..3); b1.set(62..63); b1.set(66..67); b1.set(71..72)
|
|
b1.set(128)
|
|
b1.and(b2)
|
|
assertContainsOnly(b1, setOf(3, 63, 67, 72), 129)
|
|
|
|
// or
|
|
b1 = BitSet(73)
|
|
b1.set(2..3); b1.set(62..63); b1.set(66..67); b1.set(71..72)
|
|
b1.or(b2)
|
|
assertContainsOnly(b1, setOf(1, 2, 3, 61, 62, 63, 65, 66, 67, 70, 71, 72), 76)
|
|
|
|
b1 = BitSet(73)
|
|
b1.set(2..3); b1.set(62..63); b1.set(66..67); b1.set(71..72)
|
|
b1.set(128)
|
|
b1.or(b2)
|
|
assertContainsOnly(b1, setOf(1, 2, 3, 61, 62, 63, 65, 66, 67, 70, 71, 72, 128), 129)
|
|
|
|
// xor
|
|
b1 = BitSet(73)
|
|
b1.set(2..3); b1.set(62..63); b1.set(66..67); b1.set(71..72)
|
|
b1.xor(b2)
|
|
assertContainsOnly(b1, setOf(1, 2, 61, 62, 65, 66, 70, 71), 76)
|
|
|
|
b1 = BitSet(73)
|
|
b1.set(2..3); b1.set(62..63); b1.set(66..67); b1.set(71..72)
|
|
b1.set(128)
|
|
b1.xor(b2)
|
|
assertContainsOnly(b1, setOf(1, 2, 61, 62, 65, 66, 70, 71, 128), 129)
|
|
|
|
// andNot
|
|
b1 = BitSet(73)
|
|
b1.set(2..3); b1.set(62..63); b1.set(66..67); b1.set(71..72)
|
|
b1.andNot(b2)
|
|
assertContainsOnly(b1, setOf(2, 62, 66, 71), 76)
|
|
|
|
b1 = BitSet(73)
|
|
b1.set(2..3); b1.set(62..63); b1.set(66..67); b1.set(71..72)
|
|
b1.set(128)
|
|
b1.andNot(b2)
|
|
assertContainsOnly(b1, setOf(2, 62, 66, 71, 128), 129)
|
|
|
|
// intersects
|
|
b1 = BitSet(73)
|
|
b1.set(0..1); b1.set(62..63); b1.set(64..65); b1.set(71..72)
|
|
b2.clear(); b2.set(0)
|
|
assertTrue(b1.intersects(b2))
|
|
b2.clear(); b2.set(62..65)
|
|
assertTrue(b1.intersects(b2))
|
|
b2.clear(); b2.set(72)
|
|
assertTrue(b1.intersects(b2))
|
|
b2.clear()
|
|
assertFalse(b1.intersects(b2))
|
|
b2.set(128)
|
|
assertFalse(b1.intersects(b2))
|
|
}
|
|
|
|
// Based on Harmony tests.
|
|
@Test fun equalsHashCode() {
|
|
// HashCode.
|
|
val b = BitSet()
|
|
b.set(0..7)
|
|
b.clear(2)
|
|
b.clear(6)
|
|
assertEquals(1129, b.hashCode())
|
|
b.set(10)
|
|
b.clear(3)
|
|
assertEquals(97, b.hashCode())
|
|
|
|
// Equals.
|
|
val b1 = BitSet()
|
|
val b2 = BitSet()
|
|
b1.set(0..7)
|
|
b2.set(0..7)
|
|
|
|
assertTrue(b1 == b1)
|
|
assertTrue(b1 == b2)
|
|
b2.clear(6)
|
|
assertFalse(b1 == b2)
|
|
|
|
val b3 = BitSet()
|
|
b3.set(0..7)
|
|
b3.set(128)
|
|
assertFalse(b1 == b3)
|
|
b3.clear(128)
|
|
assertTrue(b1 == b3)
|
|
}
|
|
} |