diff options
author | Erik Rozendaal <erik@deler.org> | 2011-12-17 19:17:52 +0100 |
---|---|---|
committer | Erik Rozendaal <erik@deler.org> | 2011-12-28 13:12:34 +0100 |
commit | b7e671446892c232afdfb5e36ceeab135ece649b (patch) | |
tree | f3bc3723a5836e127ca987038d696b280db8d4f2 | |
parent | 9cdede8f033f661cfa3840070089fadd1b17fede (diff) | |
download | scala-b7e671446892c232afdfb5e36ceeab135ece649b.tar.gz scala-b7e671446892c232afdfb5e36ceeab135ece649b.tar.bz2 scala-b7e671446892c232afdfb5e36ceeab135ece649b.zip |
RedBlack.scala: Change count from 'def' to 'val' in NonEmpty tree
to ensure TreeSet/TreeMap 'range' operations are O(log n) instead
of O(n).
-rw-r--r-- | src/library/scala/collection/immutable/RedBlack.scala | 2 |
1 files changed, 1 insertions, 1 deletions
diff --git a/src/library/scala/collection/immutable/RedBlack.scala b/src/library/scala/collection/immutable/RedBlack.scala index 2d3d839851..534d476507 100644 --- a/src/library/scala/collection/immutable/RedBlack.scala +++ b/src/library/scala/collection/immutable/RedBlack.scala @@ -255,7 +255,7 @@ abstract class RedBlack[A] extends Serializable { } def first = if (left .isEmpty) key else left.first def last = if (right.isEmpty) key else right.last - def count = 1 + left.count + right.count + val count = 1 + left.count + right.count } case object Empty extends Tree[Nothing] { def isEmpty = true |