diff options
author | RĂ¼diger Klaehn <rklaehn@gmail.com> | 2014-01-15 21:12:43 +0100 |
---|---|---|
committer | RĂ¼diger Klaehn <rklaehn@gmail.com> | 2014-01-15 21:12:43 +0100 |
commit | 47a91d76fc08dbac889f37915b7c08534bfa74a8 (patch) | |
tree | cb51e18fd452d16226cbbee10d5ab19c54f9f208 /test/files/run | |
parent | afcfba02edf342ea020f8c45c3ef83168c45e5ae (diff) | |
download | scala-47a91d76fc08dbac889f37915b7c08534bfa74a8.tar.gz scala-47a91d76fc08dbac889f37915b7c08534bfa74a8.tar.bz2 scala-47a91d76fc08dbac889f37915b7c08534bfa74a8.zip |
SI-6200 - HashMap should implement filter
This is the exact same algorithm as in SI-6196, with only slight
differences due to the two type arguments of HashMap.
Filter is tested by the new comparative collection test by @Ichoran, but
there is nevertheless a small correctness test in t6200 in addition to
tests of the new desirable behavior.
Diffstat (limited to 'test/files/run')
-rw-r--r-- | test/files/run/t6200.scala | 68 |
1 files changed, 68 insertions, 0 deletions
diff --git a/test/files/run/t6200.scala b/test/files/run/t6200.scala new file mode 100644 index 0000000000..02659c26bc --- /dev/null +++ b/test/files/run/t6200.scala @@ -0,0 +1,68 @@ +import scala.collection.immutable.HashMap + +object Test extends App { + + case class Collision(value: Int) extends Ordered[Collision] { + def compare(that: Collision) = value compare that.value + + override def hashCode = value / 5 + } + + def testCorrectness[T: Ordering](n: Int, mkKey: Int => T) { + val o = implicitly[Ordering[T]] + val s = HashMap.empty[T, Unit] ++ (0 until n).map(x => mkKey(x) ->()) + for (i <- 0 until n) { + val ki = mkKey(i) + val a = s.filter(kv => o.lt(kv._1, ki)) + val b = s.filterNot(kv => o.lt(kv._1, ki)) + require(a.size == i && (0 until i).forall(i => a.contains(mkKey(i)))) + require(b.size == n - i && (i until n).forall(i => b.contains(mkKey(i)))) + } + } + + // this tests the structural sharing of the new filter + // I could not come up with a simple test that tests structural sharing when only parts are reused, but + // at least this fails with the old and passes with the new implementation + def testSharing() { + val s = HashMap.empty[Int, Unit] ++ (0 until 100).map(_ ->()) + require(s.filter(_ => true) eq s) + require(s.filterNot(_ => false) eq s) + } + + // this tests that neither hashCode nor equals are called during filter + def testNoHashing() { + var hashCount = 0 + var equalsCount = 0 + case class HashCounter(value: Int) extends Ordered[HashCounter] { + def compare(that: HashCounter) = value compare that.value + + override def hashCode = { + hashCount += 1 + value + } + + override def equals(that: Any) = { + equalsCount += 1 + this match { + case HashCounter(value) => this.value == value + case _ => false + } + } + } + + val s = HashMap.empty[HashCounter, Unit] ++ (0 until 100).map(k => HashCounter(k) ->()) + val hashCount0 = hashCount + val equalsCount0 = equalsCount + val t = s.filter(_._1 < HashCounter(50)) + require(hashCount == hashCount0) + require(equalsCount == equalsCount0) + } + + // this tests correctness of filter and filterNot for integer keys + testCorrectness[Int](100, identity _) + // this tests correctness of filter and filterNot for keys with lots of collisions + // this is necessary because usually collisions are rare so the collision-related code is not thoroughly tested + testCorrectness[Collision](100, Collision.apply _) + testSharing() + testNoHashing() +} |