diff options
author | Erik Rozendaal <erik@deler.org> | 2012-01-15 13:48:00 +0100 |
---|---|---|
committer | Erik Rozendaal <erik@deler.org> | 2012-01-15 14:41:30 +0100 |
commit | 00b5cb84df493aace270674054d2f6ddf3721131 (patch) | |
tree | 2568b2913408feca58cb970b9b1402a4153eeffd /test | |
parent | f26f610278887b842de3a4e4fdafb866dd1afb62 (diff) | |
download | scala-00b5cb84df493aace270674054d2f6ddf3721131.tar.gz scala-00b5cb84df493aace270674054d2f6ddf3721131.tar.bz2 scala-00b5cb84df493aace270674054d2f6ddf3721131.zip |
Optimized implementation of TreeMap/TreeSet#to method.
Performance of `to` and `until` is now the same.
Diffstat (limited to 'test')
-rw-r--r-- | test/files/scalacheck/redblacktree.scala | 31 | ||||
-rw-r--r-- | test/files/scalacheck/treemap.scala | 18 | ||||
-rw-r--r-- | test/files/scalacheck/treeset.scala | 18 |
3 files changed, 54 insertions, 13 deletions
diff --git a/test/files/scalacheck/redblacktree.scala b/test/files/scalacheck/redblacktree.scala index 34fa8eae8d..14538c2352 100644 --- a/test/files/scalacheck/redblacktree.scala +++ b/test/files/scalacheck/redblacktree.scala @@ -174,36 +174,41 @@ package scala.collection.immutable.redblacktree { object TestRange extends RedBlackTreeTest with RedBlackTreeInvariants { import RB._ - override type ModifyParm = (Option[Int], Option[Int]) + override type ModifyParm = (Option[Int], Boolean, Option[Int], Boolean) override def genParm(tree: Tree[String, Int]): Gen[ModifyParm] = for { from <- choose(0, iterator(tree).size) + fromInclusive <- oneOf(false, true) to <- choose(0, iterator(tree).size) suchThat (from <=) + toInclusive <- oneOf(false, true) optionalFrom <- oneOf(Some(from), None, Some(from)) // Double Some(n) to get around a bug optionalTo <- oneOf(Some(to), None, Some(to)) // Double Some(n) to get around a bug - } yield (optionalFrom, optionalTo) + } yield (optionalFrom, fromInclusive, optionalTo, toInclusive) override def modify(tree: Tree[String, Int], parm: ModifyParm): Tree[String, Int] = { val from = parm._1 flatMap (nodeAt(tree, _) map (_._1)) - val to = parm._2 flatMap (nodeAt(tree, _) map (_._1)) - range(tree, from, to) + val to = parm._3 flatMap (nodeAt(tree, _) map (_._1)) + range(tree, from, parm._2, to, parm._4) } property("range boundaries respected") = forAll(genInput) { case (tree, parm, newTree) => val from = parm._1 flatMap (nodeAt(tree, _) map (_._1)) - val to = parm._2 flatMap (nodeAt(tree, _) map (_._1)) - ("lower boundary" |: (from forall ( key => iterator(newTree).map(_._1) forall (key <=)))) && - ("upper boundary" |: (to forall ( key => iterator(newTree).map(_._1) forall (key >)))) + val fromPredicate: String => String => Boolean = if (parm._2) (_ <=) else (_ <) + val to = parm._3 flatMap (nodeAt(tree, _) map (_._1)) + val toPredicate: String => String => Boolean = if (parm._4) (_ >=) else (_ >) + ("lower boundary" |: (from forall ( key => keysIterator(newTree) forall fromPredicate(key)))) && + ("upper boundary" |: (to forall ( key => keysIterator(newTree) forall toPredicate(key)))) } property("range returns all elements") = forAll(genInput) { case (tree, parm, newTree) => val from = parm._1 flatMap (nodeAt(tree, _) map (_._1)) - val to = parm._2 flatMap (nodeAt(tree, _) map (_._1)) - val filteredTree = (iterator(tree) - .map(_._1) - .filter(key => from forall (key >=)) - .filter(key => to forall (key <)) + val fromPredicate: String => String => Boolean = if (parm._2) (_ >=) else (_ >) + val to = parm._3 flatMap (nodeAt(tree, _) map (_._1)) + val toPredicate: String => String => Boolean = if (parm._4) (_ <=) else (_ <) + val filteredTree = (keysIterator(tree) + .filter(key => from forall fromPredicate(key)) + .filter(key => to forall toPredicate(key)) .toList) - filteredTree == iterator(newTree).map(_._1).toList + filteredTree == keysIterator(newTree).toList } } } diff --git a/test/files/scalacheck/treemap.scala b/test/files/scalacheck/treemap.scala index 7d5f94d58b..ba6d117fd4 100644 --- a/test/files/scalacheck/treemap.scala +++ b/test/files/scalacheck/treemap.scala @@ -111,6 +111,24 @@ object Test extends Properties("TreeMap") { prefix.forall(_._1 < 0) && suffix.forall(_._1 >= 0) && subject == prefix ++ suffix } + property("from is inclusive") = forAll { (subject: TreeMap[Int, String]) => subject.nonEmpty ==> { + val n = choose(0, subject.size - 1).sample.get + val from = subject.drop(n).firstKey + subject.from(from).firstKey == from && subject.from(from).forall(_._1 >= from) + }} + + property("to is inclusive") = forAll { (subject: TreeMap[Int, String]) => subject.nonEmpty ==> { + val n = choose(0, subject.size - 1).sample.get + val to = subject.drop(n).firstKey + subject.to(to).lastKey == to && subject.to(to).forall(_._1 <= to) + }} + + property("until is exclusive") = forAll { (subject: TreeMap[Int, String]) => subject.size > 1 ==> { + val n = choose(1, subject.size - 1).sample.get + val until = subject.drop(n).firstKey + subject.until(until).lastKey == subject.take(n).lastKey && subject.until(until).forall(_._1 <= until) + }} + property("remove single") = forAll { (subject: TreeMap[Int, String]) => subject.nonEmpty ==> { val key = oneOf(subject.keys.toSeq).sample.get val removed = subject - key diff --git a/test/files/scalacheck/treeset.scala b/test/files/scalacheck/treeset.scala index 7f99aec77e..e6d1b50860 100644 --- a/test/files/scalacheck/treeset.scala +++ b/test/files/scalacheck/treeset.scala @@ -107,6 +107,24 @@ object Test extends Properties("TreeSet") { prefix.forall(_ < 0) && suffix.forall(_ >= 0) && subject == prefix ++ suffix } + property("from is inclusive") = forAll { (subject: TreeSet[Int]) => subject.nonEmpty ==> { + val n = choose(0, subject.size - 1).sample.get + val from = subject.drop(n).firstKey + subject.from(from).firstKey == from && subject.from(from).forall(_ >= from) + }} + + property("to is inclusive") = forAll { (subject: TreeSet[Int]) => subject.nonEmpty ==> { + val n = choose(0, subject.size - 1).sample.get + val to = subject.drop(n).firstKey + subject.to(to).lastKey == to && subject.to(to).forall(_ <= to) + }} + + property("until is exclusive") = forAll { (subject: TreeSet[Int]) => subject.size > 1 ==> { + val n = choose(1, subject.size - 1).sample.get + val until = subject.drop(n).firstKey + subject.until(until).lastKey == subject.take(n).lastKey && subject.until(until).forall(_ <= until) + }} + property("remove single") = forAll { (subject: TreeSet[Int]) => subject.nonEmpty ==> { val element = oneOf(subject.toSeq).sample.get val removed = subject - element |