1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
|
import scala.collection.immutable.ListSet
import scala.collection.immutable.HashSet
object Test extends dotty.runtime.LegacyApp {
def testCorrectness(): Unit = {
// a key that has many hashCode collisions
case class Collision(i: Int) { override def hashCode = i / 5 }
def subsetTest[T](emptyA:Set[T], emptyB:Set[T], mkKey:Int => T, n:Int): Unit = {
val outside = mkKey(n + 1)
for(i <- 0 to n) {
val a = emptyA ++ (0 until i).map(mkKey)
// every set must be a subset of itself
require(a.subsetOf(a), "A set must be the subset of itself")
for(k <- 0 to i) {
// k <= i, so b is definitely a subset
val b = emptyB ++ (0 until k).map(mkKey)
// c has less elements than a, but contains a value that is not in a
// so it is not a subset, but that is not immediately obvious due to size
val c = b + outside
require(b.subsetOf(a), s"$b must be a subset of $a")
require(!c.subsetOf(a), s"$c must not be a subset of $a")
}
}
}
// test the HashSet/HashSet case
subsetTest(HashSet.empty[Int], HashSet.empty[Int], identity, 100)
// test the HashSet/other set case
subsetTest(HashSet.empty[Int], ListSet.empty[Int], identity, 100)
// test the HashSet/HashSet case for Collision keys
subsetTest(HashSet.empty[Collision], HashSet.empty[Collision], Collision, 100)
// test the HashSet/other set case for Collision keys
subsetTest(HashSet.empty[Collision], ListSet.empty[Collision], Collision, 100)
}
/**
* A main performance benefit of the new subsetOf is that we do not have to call hashCode during subsetOf
* since we already have the hash codes in the HashSet1 nodes.
*/
def testNoHashCodeInvocationsDuringSubsetOf() = {
var count = 0
case class HashCodeCounter(i:Int) {
override def hashCode = {
count += 1
i
}
}
val a = HashSet.empty ++ (0 until 100).map(HashCodeCounter)
val b = HashSet.empty ++ (0 until 50).map(HashCodeCounter)
val count0 = count
val result = b.subsetOf(a)
require(count == count0, "key.hashCode must not be called during subsetOf of two HashSets")
result
}
testCorrectness()
testNoHashCodeInvocationsDuringSubsetOf()
}
|