diff options
author | Ichoran <ichoran@gmail.com> | 2014-01-16 14:22:27 -0800 |
---|---|---|
committer | Ichoran <ichoran@gmail.com> | 2014-01-16 14:22:27 -0800 |
commit | 695b9e11a02175c2df47222e7a80627453f39e52 (patch) | |
tree | 6832e57c8f0c51a81df9594194a6715d34c557cd /test | |
parent | fe408de32ba84a46bba026a17fe3b9311404e5c5 (diff) | |
parent | 034f6b9452265dcd0e7493ed29971c8864b95c35 (diff) | |
download | scala-695b9e11a02175c2df47222e7a80627453f39e52.tar.gz scala-695b9e11a02175c2df47222e7a80627453f39e52.tar.bz2 scala-695b9e11a02175c2df47222e7a80627453f39e52.zip |
Merge pull request #3322 from rklaehn/issue/6253
SI-6253 HashSet should implement union
Diffstat (limited to 'test')
-rw-r--r-- | test/files/run/t6253a.scala | 64 | ||||
-rw-r--r-- | test/files/run/t6253b.scala | 62 | ||||
-rw-r--r-- | test/files/run/t6253c.scala | 63 |
3 files changed, 189 insertions, 0 deletions
diff --git a/test/files/run/t6253a.scala b/test/files/run/t6253a.scala new file mode 100644 index 0000000000..efa3230df6 --- /dev/null +++ b/test/files/run/t6253a.scala @@ -0,0 +1,64 @@ +import scala.collection.immutable.HashSet + +object Test extends App { + + var hashCount = 0 + + /** + * A key that produces lots of hash collisions, to exercise the part of the code that deals with those + */ + case class Collision(value: Int) { + + override def hashCode = { + // we do not check hash counts for Collision keys because ListSet.++ uses a mutable hashset internally, + // so when we have hash collisions, union will call key.hashCode. + // hashCount += 1 + value / 5 + } + } + + /** + * A key that is identical to int other than that it counts hashCode invocations + */ + case class HashCounter(value: Int) { + + override def hashCode = { + hashCount += 1 + value + } + } + + def testUnion[T](sizes: Seq[Int], offsets: Seq[Double], keyType: String, mkKey: Int => T) { + for { + i <- sizes + o <- offsets + } { + val e = HashSet.empty[T] + val j = (i * o).toInt + // create two sets of size i with overlap o + val a = e ++ (0 until i).map(mkKey) + require(a.size == i, s"Building HashSet of size $i failed. Key type $keyType.") + val b = e ++ (j until (i + j)).map(mkKey) + require(b.size == i, s"Building HashSet of size $i failed. Key type $keyType.") + val as = e ++ (0 until j).map(mkKey) + require(as.size == j, s"Building HashSet of size $j failed. Key type $keyType.") + val hashCount0 = hashCount + val u = a union b + require(hashCount == hashCount0, s"key.hashCode should not be called, but has been called ${hashCount - hashCount0} times. Key type $keyType.") + require(u == (a union scala.collection.mutable.HashSet(b.toSeq: _*)), s"Operation must still work for other sets!") + require(u.size == i + j, s"Expected size ${i+j}. Real size ${u.size}. Key type $keyType.") + for (x <- 0 until i + j) + require(u.contains(mkKey(x)), s"Key type $keyType. Set (0 until ${i + j}) should contain $x but does not.") + val a_as = a union as + val as_a = as union a + require((a_as eq a) || (a_as eq as), s"No structural sharing in a union as. Key type $keyType, a=(0 until $i) as=(0 until $j)") + require((as_a eq a) || (as_a eq as), s"No structural sharing in as union a. Key type $keyType, a=(0 until $i) as=(0 until $j)") + } + } + + val sizes = Seq(1, 10, 100, 1000, 10000, 100000) + val offsets = Seq(0.0, 0.25, 0.5, 0.75, 1.0) + testUnion(sizes, offsets, "int", identity[Int]) + testUnion(sizes, offsets, "hashcounter", HashCounter.apply) + testUnion(sizes, offsets, "collision", Collision.apply) +} diff --git a/test/files/run/t6253b.scala b/test/files/run/t6253b.scala new file mode 100644 index 0000000000..9cbfefd49e --- /dev/null +++ b/test/files/run/t6253b.scala @@ -0,0 +1,62 @@ +import scala.collection.immutable.HashSet + +object Test extends App { + + var hashCount = 0 + + /** + * A key that produces lots of hash collisions, to exercise the part of the code that deals with those + */ + case class Collision(value: Int) { + + override def hashCode = { + hashCount += 1 + value / 5 + } + } + + /** + * A key that is identical to int other than that it counts hashCode invocations + */ + case class HashCounter(value: Int) { + + override def hashCode = { + hashCount += 1 + value + } + } + + def testIntersect[T](sizes: Seq[Int], offsets: Seq[Double], keyType: String, mkKey: Int => T) { + for { + i <- sizes + o <- offsets + } { + val e = HashSet.empty[T] + val j = (i * o).toInt + // create two sets of size i with overlap o + val a = e ++ (0 until i).map(mkKey) + require(a.size == i, s"Building HashSet of size $i failed. Key type $keyType.") + val b = e ++ (j until (i + j)).map(mkKey) + require(b.size == i, s"Building HashSet of size $i failed. Key type $keyType.") + val as = e ++ (0 until j).map(mkKey) + require(as.size == j, s"Building HashSet of size $j failed. Key type $keyType.") + val hashCount0 = hashCount + val u = a intersect b + require(hashCount == hashCount0, s"key.hashCode should not be called, but has been called ${hashCount - hashCount0} times. Key type $keyType.") + require(u == (a intersect scala.collection.mutable.HashSet(b.toSeq: _*)), s"Operation must still work for other sets!") + require(u.size == i - j, s"Expected size ${i + j}. Real size ${u.size}. Key type $keyType.") + for (x <- j until i) + require(u.contains(mkKey(x)), s"Key type $keyType. Set (0 until ${i + j}) should contain $x but does not.") + val a_as = a intersect as + val as_a = as intersect a + require((a_as eq as) || (a_as eq a), s"No structural sharing in a intersect as. Key type $keyType, a=(0 until $i) as=(0 until $j)") + require((as_a eq as) || (as_a eq a), s"No structural sharing in as intersect a. Key type $keyType, a=(0 until $i) as=(0 until $j)") + } + } + + val sizes = Seq(1, 10, 100, 1000, 10000, 100000) + val offsets = Seq(0.0, 0.25, 0.5, 0.75, 1.0) + testIntersect(sizes, offsets, "int", identity[Int]) + testIntersect(sizes, offsets, "hashcounter", HashCounter.apply) + testIntersect(sizes, offsets, "collision", Collision.apply) +} diff --git a/test/files/run/t6253c.scala b/test/files/run/t6253c.scala new file mode 100644 index 0000000000..71dfe1473e --- /dev/null +++ b/test/files/run/t6253c.scala @@ -0,0 +1,63 @@ +import scala.collection.immutable.HashSet + +object Test extends App { + + var hashCount = 0 + + /** + * A key that produces lots of hash collisions, to exercise the part of the code that deals with those + */ + case class Collision(value: Int) { + + override def hashCode = { + hashCount += 1 + value / 5 + } + } + + /** + * A key that is identical to int other than that it counts hashCode invocations + */ + case class HashCounter(value: Int) { + + override def hashCode = { + hashCount += 1 + value + } + } + + def testDiff[T](sizes: Seq[Int], offsets: Seq[Double], keyType: String, mkKey: Int => T) { + for { + i <- sizes + o <- offsets + } { + val e = HashSet.empty[T] + val j = (i * o).toInt + // create two sets of size i with overlap o + val a = e ++ (0 until i).map(mkKey) + require(a.size == i, s"Building HashSet of size $i failed. Key type $keyType.") + val b = e ++ (j until (i + j)).map(mkKey) + require(b.size == i, s"Building HashSet of size $i failed. Key type $keyType.") + val as = e ++ (0 until j).map(mkKey) + require(as.size == j, s"Building HashSet of size $j failed. Key type $keyType.") + val hashCount0 = hashCount + val u = a diff b + require(hashCount == hashCount0, s"key.hashCode should not be called, but has been called ${hashCount - hashCount0} times. Key type $keyType.") + require(u == (a diff scala.collection.mutable.HashSet(b.toSeq: _*)), s"Operation must still work for other sets!") + require(u.size == j, s"Expected size $j. Real size ${u.size}. Key type $keyType.") + for (x <- 0 until j) + require(u.contains(mkKey(x)), s"Key type $keyType. Set (0 until ${i + j}) should contain $x but does not.") + require((as intersect b).isEmpty) + val b_as = b diff as + val as_b = as diff b + require((b_as eq b) || (b_as eq as), s"No structural sharing in b diff as. Key type $keyType, b=($j until ${i + j}) as=(0 until $j)") + require((as_b eq b) || (as_b eq as), s"No structural sharing in as diff b. Key type $keyType, b=($j until ${i + j}) as=(0 until $j)") + } + } + + val sizes = Seq(1, 10, 100, 1000, 10000, 100000) + val offsets = Seq(0.0, 0.25, 0.5, 0.75, 1.0) + testDiff(sizes, offsets, "int", identity[Int]) + testDiff(sizes, offsets, "hashCounter", HashCounter.apply) + testDiff(sizes, offsets, "collision", Collision.apply) +} |