diff options
author | Erik Rozendaal <erik@deler.org> | 2012-01-04 17:10:20 +0100 |
---|---|---|
committer | Erik Rozendaal <erik@deler.org> | 2012-01-04 22:36:21 +0100 |
commit | 72ec0ac869a29fca9ea0d45a3f70f1e9e1babaaf (patch) | |
tree | 37591a9c2cea97da7afdf55ee03a84fa2133a1db /test | |
parent | 5c05f66b619ea9c8a543518fd9d7d601268c6f19 (diff) | |
download | scala-72ec0ac869a29fca9ea0d45a3f70f1e9e1babaaf.tar.gz scala-72ec0ac869a29fca9ea0d45a3f70f1e9e1babaaf.tar.bz2 scala-72ec0ac869a29fca9ea0d45a3f70f1e9e1babaaf.zip |
Optimize foreach and iterators.
Diffstat (limited to 'test')
-rw-r--r-- | test/files/scalacheck/treemap.scala | 16 | ||||
-rw-r--r-- | test/files/scalacheck/treeset.scala | 16 |
2 files changed, 32 insertions, 0 deletions
diff --git a/test/files/scalacheck/treemap.scala b/test/files/scalacheck/treemap.scala index 43d307600d..9970bb01aa 100644 --- a/test/files/scalacheck/treemap.scala +++ b/test/files/scalacheck/treemap.scala @@ -22,6 +22,22 @@ object Test extends Properties("TreeMap") { consistent } + property("worst-case tree height is iterable") = forAll(choose(0, 10), arbitrary[Boolean]) { (n: Int, even: Boolean) => + /* + * According to "Ralf Hinze. Constructing red-black trees" [http://www.cs.ox.ac.uk/ralf.hinze/publications/#P5] + * you can construct a skinny tree of height 2n by inserting the elements [1 .. 2^(n+1) - 2] and a tree of height + * 2n+1 by inserting the elements [1 .. 3 * 2^n - 2], both in reverse order. + * + * Since we allocate a fixed size buffer in the iterator (based on the tree size) we need to ensure + * it is big enough for these worst-case trees. + */ + val highest = if (even) (1 << (n+1)) - 2 else 3*(1 << n) - 2 + val values = (1 to highest).reverse + val subject = TreeMap(values zip values: _*) + val it = subject.iterator + try { while (it.hasNext) it.next; true } catch { case _ => false } + } + property("sorted") = forAll { (subject: TreeMap[Int, String]) => (subject.size >= 3) ==> { subject.zip(subject.tail).forall { case (x, y) => x._1 < y._1 } }} diff --git a/test/files/scalacheck/treeset.scala b/test/files/scalacheck/treeset.scala index 3cefef7040..87c3eb7108 100644 --- a/test/files/scalacheck/treeset.scala +++ b/test/files/scalacheck/treeset.scala @@ -18,6 +18,22 @@ object Test extends Properties("TreeSet") { consistent } + property("worst-case tree height is iterable") = forAll(choose(0, 10), arbitrary[Boolean]) { (n: Int, even: Boolean) => + /* + * According to "Ralf Hinze. Constructing red-black trees" [http://www.cs.ox.ac.uk/ralf.hinze/publications/#P5] + * you can construct a skinny tree of height 2n by inserting the elements [1 .. 2^(n+1) - 2] and a tree of height + * 2n+1 by inserting the elements [1 .. 3 * 2^n - 2], both in reverse order. + * + * Since we allocate a fixed size buffer in the iterator (based on the tree size) we need to ensure + * it is big enough for these worst-case trees. + */ + val highest = if (even) (1 << (n+1)) - 2 else 3*(1 << n) - 2 + val values = (1 to highest).reverse + val subject = TreeSet(values: _*) + val it = subject.iterator + try { while (it.hasNext) it.next; true } catch { case _ => false } + } + property("sorted") = forAll { (subject: TreeSet[Int]) => (subject.size >= 3) ==> { subject.zip(subject.tail).forall { case (x, y) => x < y } }} |