8000 Immutable TreeMap/TreeSet performance (SI-5331) by erikrozendaal · Pull Request #82 · scala/scala · GitHub
[go: up one dir, main page]

Skip to content

Immutable TreeMap/TreeSet performance (SI-5331) #82

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 37 commits into from
Feb 16, 2012
Merged
Show file tree
Hide file tree
Changes from 1 commit
Commits
Show all changes
37 commits
Select commit Hold shift + click to select a range
540ad02
Use RedBlack.iterator to create iterators for TreeSet/TreeMap.
erikrozendaal Dec 17, 2011
88ed930
Use custom implementation for iterating over RedBlack trees. Raw
erikrozendaal Dec 17, 2011
edcec03
Optimized implementations of head/headOption/last/lastOption for
erikrozendaal Dec 17, 2011
9cdede8
Optimized implementation of init/tail for TreeSet/TreeMap.
erikrozendaal Dec 17, 2011
b7e6714
RedBlack.scala: Change count from 'def' to 'val' in NonEmpty tree
erikrozendaal Dec 17, 2011
95cb7bc
Implemented drop/take/slice/splitAt/dropRight/takeRight for
erikrozendaal Dec 18, 2011
8d67823
Implemented takeWhile/dropWhile/span to use tree splitting. This
erikrozendaal Dec 18, 2011
3f66061
Switched from isSmaller to ordering.
erikrozendaal Dec 19, 2011
7ec9b0b
Moved from implicit ordering value to implicit parameter.
erikrozendaal Dec 19, 2011
a02a815
Moved from Empty case object to case class in preparation of moving
erikrozendaal Dec 19, 2011
418adc6
Moved type parameter A from RedBlack to Tree.
erikrozendaal Dec 19, 2011
6c0e036
Changed abstract class RedBlack to singleton object.
erikrozendaal Dec 19, 2011
d2706db
Use single shared Empty instance across all RedBlack trees.
erikrozendaal Dec 19, 2011
6b95074
Make sure the redblack test compiles and runs.
erikrozendaal Dec 21, 2011
b9699f9
Made RedBlack private to the scala.collection.immutable package.
erikrozendaal Dec 27, 2011
32171c2
TreeMap/TreeSet no longer keep track of the size (the RedBlack tree
erikrozendaal Dec 27, 2011
b421bba
Performance improvements for iteration (foreach and iterator).
erikrozendaal Dec 27, 2011
4a0c4bb
Improved performance of RedBlack.NonEmpty.nth (helps take/drop/split/…
erikrozendaal Dec 27, 2011
ad0b09c
Added some tests for TreeMap/TreeSet.
erikrozendaal Dec 28, 2011
c51bdea
Minimize number of calls to ordering.
erikrozendaal Dec 28, 2011
6d8dca7
Moved key/value/left/right fields up to NonEmpty class. Don't rely
erikrozendaal Jan 2, 2012
82374ad
Implemented deletes without pattern matching.
erikrozendaal Jan 2, 2012
3dea251
Implemented range without using pattern matching.
erikrozendaal Jan 2, 2012
5c05f66
Use null to represent empty trees. Removed Empty/NonEmpty classes.
erikrozendaal Jan 2, 2012
72ec0ac
Optimize foreach and iterators.
erikrozendaal Jan 4, 2012
d735d0f
Move nth method to RedBlack. Inline factories for tree nodes.
erikrozendaal Jan 5, 2012
388ff47
Add implementation notes. Consistently use eq/ne to compare with null.
erikrozendaal Jan 5, 2012
7e92b3c
Deprecate TreeMap.isSmaller and TreeSet.isSmaller.
erikrozendaal Jan 6, 2012
f656142
Restore old RedBlack class to maintain backwards compatibility.
erikrozendaal Jan 6, 2012
288874d
Renamed object RedBlack to RedBlackTree.
erikrozendaal Jan 7, 2012
e61075c
Tests for takeWhile/dropWhile/span.
erikrozendaal Jan 7, 2012
8b3f984
Fix silly copy-paste error.
erikrozendaal Jan 7, 2012
f26f610
Test for maximum height of red-black tree.
erikrozendaal Jan 8, 2012
00b5cb8
Optimized implementation of TreeMap/TreeSet#to method.
erikrozendaal Jan 15, 2012
7824dbd
Custom coded version of range/from/to/until.
erikrozendaal Jan 21, 2012
78374f3
Custom implementations of drop/take/slice.
erikrozendaal Jan 22, 2012
51667dc
Removed TODOs.
erikrozendaal Jan 24, 2012
File filter

Filter by extension

Filter by extension

Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Prev Previous commit
Next Next commit
Moved type parameter A from RedBlack to Tree.
  • Loading branch information
erikrozendaal committed Dec 28, 2011
commit 418adc642cbde26c09fe8ee24e019d89f6b123f9
124 changes: 62 additions & 62 deletions src/library/scala/collection/immutable/RedBlack.scala
10000
Original file line number Diff line number Diff line change
Expand Up @@ -16,70 +16,70 @@ package immutable
* @since 2.3
*/
@SerialVersionUID(8691885935445612921L)
abstract class RedBlack[A] extends Serializable {
abstract class RedBlack extends Serializable {

private def blacken[B](t: Tree[B]): Tree[B] = t match {
private def blacken[A, B](t: Tree[A, B]): Tree[A, B] = t match {
case RedTree(k, v, l, r) => BlackTree(k, v, l, r)
case t => t
}
private def mkTree[B](isBlack: Boolean, k: A, v: B, l: Tree[B], r: Tree[B]) =
private def mkTree[A, B](isBlack: Boolean, k: A, v: B, l: Tree[A, B], r: Tree[A, B]) =
if (isBlack) BlackTree(k, v, l, r) else RedTree(k, v, l, r)

abstract class Tree[+B] extends Serializable {
abstract class Tree[A, +B] extends Serializable {
def isEmpty: Boolean
def isBlack: Boolean
def lookup(x: A)(implicit ordering: Ordering[A]): Tree[B]
def update[B1 >: B](k: A, v: B1)(implicit ordering: Ordering[A]): Tree[B1] = blacken(upd(k, v))
def delete(k: A)(implicit ordering: Ordering[A]): Tree[B] = blacken(del(k))
def range(from: Option[A], until: Option[A])(implicit ordering: Ordering[A]): Tree[B] = blacken(rng(from, until))
def lookup(x: A)(implicit ordering: Ordering[A]): Tree[A, B]
def update[B1 >: B](k: A, v: B1)(implicit ordering: Ordering[A]): Tree[A, B1] = blacken(upd(k, v))
def delete(k: A)(implicit ordering: Ordering[A]): Tree[A, B] = blacken(del(k))
def range(from: Option[A], until: Option[A])(implicit ordering: Ordering[A]): Tree[A, B] = blacken(rng(from, until))
def foreach[U](f: (A, B) => U)
def toStream: Stream[(A,B)]
def iterator: Iterator[(A, B)]
def upd[B1 >: B](k: A, v: B1)(implicit ordering: Ordering[A]): Tree[B1]
def del(k: A)(implicit ordering: Ordering[A]): Tree[B]
def smallest: NonEmpty[B]
def greatest: NonEmpty[B]
def rng(from: Option[A], until: Option[A])(implicit ordering: Ordering[A]): Tree[B]
def upd[B1 >: B](k: A, v: B1)(implicit ordering: Ordering[A]): Tree[A, B1]
def del(k: A)(implicit ordering: Ordering[A]): Tree[A, B]
def smallest: NonEmpty[A, B]
def greatest: NonEmpty[A, B]
def rng(from: Option[A], until: Option[A])(implicit ordering: Ordering[A]): Tree[A, B]
def first : A
def last : A
def count : Int
protected[immutable] def nth(n: Int): NonEmpty[B]
protected[immutable] def nth(n: Int): NonEmpty[A, B]
}
abstract class NonEmpty[+B] extends Tree[B] with Serializable {
abstract class NonEmpty[A, +B] extends Tree[A, B] with Serializable {
def isEmpty = false
def key: A
def value: B
def left: Tree[B]
def right: Tree[B]
def lookup(k: A)(implicit ordering: Ordering[A]): Tree[B] =
def left: Tree[A, B]
def right: Tree[A, B]
def lookup(k: A)(implicit ordering: Ordering[A]): Tree[A, B] =
if (ordering.lt(k, key)) left.lookup(k)
else if (ordering.lt(key, k)) right.lookup(k)
else this
private[this] def balanceLeft[B1 >: B](isBlack: Boolean, z: A, zv: B, l: Tree[B1], d: Tree[B1])/*: NonEmpty[B1]*/ = l match {
private[this] def balanceLeft[B1 >: B](isBlack: Boolean, z: A, zv: B, l: Tree[A, B1], d: Tree[A, B1])/*: NonEmpty[A, B1]*/ = l match {
case RedTree(y, yv, RedTree(x, xv, a, b), c) =>
RedTree(y, yv, BlackTree(x, xv, a, b), BlackTree(z, zv, c, d))
case RedTree(x, xv, a, RedTree(y, yv, b, c)) =>
RedTree(y, yv, BlackTree(x, xv, a, b), BlackTree(z, zv, c, d))
case _ =>
mkTree(isBlack, z, zv, l, d)
}
private[this] def balanceRight[B1 >: B](isBlack: Boolean, x: A, xv: B, a: Tree[B1], r: Tree[B1])/*: NonEmpty[B1]*/ = r match {
private[this] def balanceRight[B1 >: B](isBlack: Boolean, x: A, xv: B, a: Tree[A, B1], r: Tree[A, B1])/*: NonEmpty[A, B1]*/ = r match {
case RedTree(z, zv, RedTree(y, yv, b, c), d) =>
RedTree(y, yv, BlackTree(x, xv, a, b), BlackTree(z, zv, c, d))
case RedTree(y, yv, b, RedTree(z, zv, c, d)) =>
RedTree(y, yv, BlackTree(x, xv, a, b), BlackTree(z, zv, c, d))
case _ =>
mkTree(isBlack, x, xv, a, r)
}
def upd[B1 >: B](k: A, v: B1)(implicit ordering: Ordering[A]): Tree[B1] = {
def upd[B1 >: B](k: A, v: B1)(implicit ordering: Ordering[A]): Tree[A, B1] = {
if (ordering.lt(k, key)) balanceLeft(isBlack, key, value, left.upd(k, v), right)
else if (ordering.lt(key, k)) balanceRight(isBlack, key, value, left, right.upd(k, v))
else mkTree(isBlack, k, v, left, right)
}
// Based on Stefan Kahrs' Haskell version of Okasaki's Red&Black Trees
// http://www.cse.unsw.edu.au/~dons/data/RedBlackTree.html
def del(k: A)(implicit ordering: Ordering[A]): Tree[B] = {
def balance(x: A, xv: B, tl: Tree[B], tr: Tree[B]) = (tl 8000 , tr) match {
def del(k: A)(implicit ordering: Ordering[A]): Tree[A, B] = {
def balance(x: A, xv: B, tl: Tree[A, B], tr: Tree[A, B]) = (tl, tr) match {
case (RedTree(y, yv, a, b), RedTree(z, zv, c, d)) =>
RedTree(x, xv, BlackTree(y, yv, a, b), BlackTree(z, zv, c, d))
case (RedTree(y, yv, RedTree(z, zv, a, b), c), d) =>
Expand All @@ -93,11 +93,11 @@ abstract class RedBlack[A] extends Serializable {
case (a, b) =>
BlackTree(x, xv, a, b)
}
def subl(t: Tree[B]) = t match {
def subl(t: Tree[A, B]) = t match {
case BlackTree(x, xv, a, b) => RedTree(x, xv, a, b)
case _ => sys.error("Defect: invariance violation; expected black, got "+t)
}
def balLeft(x: A, xv: B, tl: Tree[B], tr: Tree[B]) = (tl, tr) match {
def balLeft(x: A, xv: B, tl: Tree[A, B], tr: Tree[A, B]) = (tl, tr) match {
case (RedTree(y, yv, a, b), c) =>
RedTree(x, xv, BlackTree(y, yv, a, b), c)
case (bl, BlackTree(y, yv, a, b)) =>
Expand All @@ -106,7 +106,7 @@ abstract class RedBlack[A] extends Serializable {
RedTree(z, zv, BlackTree(x, xv, bl, a), balance(y, yv, b, subl(c)))
case _ => sys.error("Defect: invariance violation at "+right)
}
def balRight(x: A, xv: B, tl: Tree[B], tr: Tree[B]) = (tl, tr) match {
def balRight(x: A, xv: B, tl: Tree[A, B], tr: Tree[A, B]) = (tl, tr) match {
case (a, RedTree(y, yv, b, c)) =>
RedTree(x, xv, a, BlackTree(y, yv, b, c))
case (BlackTree(y, yv, a, b), bl) =>
Expand All @@ -116,14 +116,14 @@ abstract class RedBlack[A] extends Serializable {
case _ => sys.error("Defect: invariance violation at "+left)
}
def delLeft = left match {
case _: BlackTree[_] => balLeft(key, value, left.del(k), right)
case _: BlackTree[_, _] => balLeft(key, value, left.del(k), right)
case _ => RedTree(key, value, left.del(k), right)
}
def delRight = right match {
case _: BlackTree[_] => balRight(key, value, left, right.del(k))
case _: BlackTree[_, _] => balRight(key, value, left, right.del(k))
case _ => RedTree(key, value, left, right.del(k))
}
def append(tl: Tree[B], tr: Tree[B]): Tree[B] = (tl, tr) match {
def append(tl: Tree[A, B], tr: Tree[A, B]): Tree[A, B] = (tl, tr) match {
case (Empty(), t) => t
case (t, Empty()) => t
case (RedTree(x, xv, a, b), RedTree(y, yv, c, d)) =>
Expand All @@ -147,8 +147,8 @@ abstract class RedBlack[A] extends Serializable {
}
}

def smallest: NonEmpty[B] = if (left.isEmpty) this else left.smallest
def greatest: NonEmpty[B] = if (right.isEmpty) this else right.greatest
def smallest: NonEmpty[A, B] = if (left.isEmpty) this else left.smallest
def greatest: NonEmpty[A, B] = if (right.isEmpty) this else right.greatest

def toStream: Stream[(A,B)] = iterator.toStream

Expand All @@ -160,7 +160,7 @@ abstract class RedBlack[A] extends Serializable {
right foreach f
}

override def rng(from: Option[A], until: Option[A])(implicit ordering: Ordering[A]): Tree[B] = {
override def rng(from: Option[A], until: Option[A])(implicit ordering: Ordering[A]): Tree[A, B] = {
if (from == None && until == None) return this
if (from != None && ordering.lt(key, from.get)) return right.rng(from, until);
if (until != None && (ordering.lt(until.get,key) || !ordering.lt(key,until.get)))
Expand All @@ -182,23 +182,23 @@ abstract class RedBlack[A] extends Serializable {
// whether the zipper was traversed left-most or right-most.

// If the trees were balanced, returns an empty zipper
private[this] def compareDepth(left: Tree[B], right: Tree[B]): (List[NonEmpty[B]], Boolean, Boolean, Int) = {
private[this] def compareDepth(left: Tree[A, B], right: Tree[A, B]): (List[NonEmpty[A, B]], Boolean, Boolean, Int) = {
// Once a side is found to be deeper, unzip it to the bottom
def unzip(zipper: List[NonEmpty[B]], leftMost: Boolean): List[NonEmpty[B]] = {
def unzip(zipper: List[NonEmpty[A, B]], leftMost: Boolean): List[NonEmpty[A, B]] = {
val next = if (leftMost) zipper.head.left else zipper.head.right
next match {
case node: NonEmpty[_] => unzip(node :: zipper, leftMost)
case Empty() => zipper
case node: NonEmpty[_, _] => unzip(node :: zipper, leftMost)
case Empty() => zipper
}
}

// Unzip left tree on the rightmost side and right tree on the leftmost side until one is
// found to be deeper, or the bottom is reached
def unzipBoth(left: Tree[B],
right: Tree[B],
leftZipper: List[NonEmpty[B]],
rightZipper: List[NonEmpty[B]],
smallerDepth: Int): (List[NonEmpty[B]], Boolean, Boolean, Int) = (left, right) match {
def unzipBoth(left: Tree[A, B],
right: Tree[A, B],
leftZipper: List[NonEmpty[A, B]],
rightZipper: List[NonEmpty[A, B]],
smallerDepth: Int): (List[NonEmpty[A, B]], Boolean, Boolean, Int) = (left, right) match {
case (l @ BlackTree(_, _, _, _), r @ BlackTree(_, _, _, _)) =>
unzipBoth(l.right, r.left, l :: leftZipper, r :: rightZipper, smallerDepth + 1)
case (l @ RedTree(_, _, _, _), r @ RedTree(_, _, _, _)) =>
Expand All @@ -219,9 +219,9 @@ abstract class RedBlack[A] extends Serializable {
unzipBoth(left, right, Nil, Nil, 0)
}

private[this] def rebalance(newLeft: Tree[B], newRight: Tree[B]) = {
private[this] def rebalance(newLeft: Tree[A, B], newRight: Tree[A, B]) = {
// This is like drop(n-1), but only counting black nodes
def findDepth(zipper: List[NonEmpty[B]], depth: Int): List[NonEmpty[B]] = zipper match {
def findDepth(zipper: List[NonEmpty[A, B]], depth: Int): List[NonEmpty[A, B]] = zipper match {
case BlackTree(_, _, _, _) :: tail =>
if (depth == 1) zipper else findDepth(tail, depth - 1)
case _ :: tail => findDepth(tail, depth)
Expand All @@ -243,7 +243,7 @@ abstract class RedBlack[A] extends Serializable {
} else {
RedTree(key, value, zipFrom.head, blkNewRight)
}
val zippedTree = zipFrom.tail.foldLeft(union: Tree[B]) { (tree, node) =>
val zippedTree = zipFrom.tail.foldLeft(union: Tree[A, B]) { (tree, node) =>
if (leftMost)
balanceLeft(node.isBlack, node.key, node.value, tree, node.right)
else
Expand All @@ -261,14 +261,14 @@ abstract class RedBlack[A] extends Serializable {
else this
}
}
case class Empty() extends Tree[Nothing] {
case class Empty[A]() extends Tree[A, Nothing] {
def isEmpty = true
def isBlack = true
def lookup(k: A)(implicit ordering: Ordering[A]): Tree[Nothing] = this
def upd[B](k: A, v: B)( 6DAF implicit ordering: Ordering[A]): Tree[B] = RedTree(k, v, this, this)
def del(k: A)(implicit ordering: Ordering[A]): Tree[Nothing] = this
def smallest: NonEmpty[Nothing] = throw new NoSuchElementException("empty map")
def greatest: NonEmpty[Nothing] = throw new NoSuchElementException("empty map")
def lookup(k: A)(implicit ordering: Ordering[A]): Tree[A, Nothing] = this
def upd[B](k: A, v: B)(implicit ordering: Ordering[A]): Tree[A, B] = RedTree(k, v, this, this)
def del(k: A)(implicit ordering: Ordering[A]): Tree[A, Nothing] = this
def smallest: NonEmpty[A, Nothing] = throw new NoSuchElementException("empty map")
def greatest: NonEmpty[A, Nothing] = throw new NoSuchElementException("empty map")
def iterator: Iterator[(A, Nothing)] = Iterator.empty
def toStream: Stream[(A,Nothing)] = Stream.empty

Expand All @@ -280,46 +280,46 @@ abstract class RedBlack[A] extends Serializable {
def count = 0
protected[immutable] def nth(n: Int) = throw new NoSuchElementException("empty map")
}
case class RedTree[+B](override val key: A,
case class RedTree[A, +B](override val key: A,
override val value: B,
override val left: Tree[B],
override val right: Tree[B]) extends NonEmpty[B] {
override val left: Tree[A, B],
override val right: Tree[A, B]) extends NonEmpty[A, B] {
def isBlack = false
}
case class BlackTree[+B](override val key: A,
case class BlackTree[A, +B](override val key: A,
override val value: B,
override val left: Tree[B],
override val right: Tree[B]) extends NonEmpty[B] {
override val left: Tree[A, B],
override val right: Tree[A, B]) extends NonEmpty[A, B] {
def isBlack = true
}

private[this] class TreeIterator[B](tree: NonEmpty[B]) extends Iterator[(A, B)] {
private[this] class TreeIterator[A, B](tree: NonEmpty[A, B]) extends Iterator[(A, B)] {
import collection.mutable.Stack

override def hasNext: Boolean = !next.isEmpty

override def next: (A, B) = next match {
case Empty() =>
throw new NoSuchElementException("next on empty iterator")
case tree: NonEmpty[B] =>
case tree: NonEmpty[A, B] =>
val result = (tree.key, tree.value)
addLeftMostBranchToPath(tree.right)
next = if (path.isEmpty) Empty() else path.pop()
result
}

@annotation.tailrec
private[this] def addLeftMostBranchToPath(tree: Tree[B]) {
private[this] def addLeftMostBranchToPath(tree: Tree[A, B]) {
tree match {
case Empty() =>
case tree: NonEmpty[B] =>
case tree: NonEmpty[A, B] =>
path.push(tree)
addLeftMostBranchToPath(tree.left)
}
}

private[this] val path: Stack[NonEmpty[B]] = Stack.empty[NonEmpty[B]]
private[this] val path: Stack[NonEmpty[A, B]] = Stack.empty[NonEmpty[A, B]]
addLeftMostBranchToPath(tree)
private[this] var next: Tree[B] = path.pop()
private[this] var next: Tree[A, B] = path.pop()
}
}
10 changes: 5 additions & 5 deletions src/library/scala/collection/immutable/TreeMap.scala
Original file line number Diff line number Diff line change
Expand Up @@ -23,7 +23,7 @@ object TreeMap extends ImmutableSortedMapFactory[TreeMap] {
def empty[A, B](implicit ord: Ordering[A]) = new TreeMap[A, B]()(ord)
/** $sortedMapCanBuildFromInfo */
implicit def canBuildFrom[A, B](implicit ord: Ordering[A]): CanBuildFrom[Coll, (A, B), TreeMap[A, B]] = new SortedMapCanBuildFrom[A, B]
private def make[A, B](s: Int, t: RedBlack[A]#Tree[B])(implicit ord: Ordering[A]) = new TreeMap[A, B](s, t)(ord)
private def make[A, B](s: Int, t: RedBlack#Tree[A, B])(implicit ord: Ordering[A]) = new TreeMap[A, B](s, t)(ord)
}

/** This class implements immutable maps using a tree.
Expand All @@ -46,8 +46,8 @@ object TreeMap extends ImmutableSortedMapFactory[TreeMap] {
* @define mayNotTerminateInf
* @define willNotTerminateInf
*/
class TreeMap[A, +B](override val size: Int, t: RedBlack[A]#Tree[B])(implicit val ordering: Ordering[A])
extends RedBlack[A]
class TreeMap[A, +B](override val size: Int, t: RedBlack#Tree[A, B])(implicit val ordering: Ordering[A])
extends RedBlack
with SortedMap[A, B]
with SortedMapLike[A, B, TreeMap[A, B]]
with MapLike[A, B, TreeMap[A, B]]
Expand All @@ -60,7 +60,7 @@ class TreeMap[A, +B](override val size: Int, t: RedBlack[A]#Tree[B])(implicit va

def this()(implicit ordering: Ordering[A]) = this(0, null)(ordering)

protected val tree: RedBlack[A]#Tree[B] = if (size == 0) Empty() else t
protected val tree: RedBlack#Tree[A, B] = if (size == 0) Empty() else t

override def rangeImpl(from : Option[A], until : Option[A]): TreeMap[A,B] = {
val ntree = tree.range(from,until)
Expand Down Expand Up @@ -194,7 +194,7 @@ class TreeMap[A, +B](override val size: Int, t: RedBlack[A]#Tree[B])(implicit va
* @return the value of the mapping, if it exists
*/
override def get(key: A): Option[B] = tree.lookup(key) match {
case n: NonEmpty[b] => Some(n.value)
case n: NonEmpty[_, _] => Some(n.value)
case _ => None
}

Expand Down
8 changes: 4 additions & 4 deletions src/library/scala/collection/immutable/TreeSet.scala
Original file line number Diff line number Diff line change
Expand Up @@ -47,9 +47,9 @@ object TreeSet extends ImmutableSortedSetFactory[TreeSet] {
* @define willNotTerminateInf
*/
@SerialVersionUID(-234066569443569402L)
class TreeSet[A](override val size: Int, t: RedBlack[A]#Tree[Unit])
class TreeSet[A](override val size: Int, t: RedBlack#Tree[A, Unit])
(implicit val ordering: Ordering[A])
extends RedBlack[A] with SortedSet[A] with SortedSetLike[A, TreeSet[A]] with Serializable {
extends RedBlack with SortedSet[A] with SortedSetLike[A, TreeSet[A]] with Serializable {

override def stringPrefix = "TreeSet"

Expand Down Expand Up @@ -101,9 +101,9 @@ class TreeSet[A](override val size: Int, t: RedBlack[A]#Tree[Unit])

def this()(implicit ordering: Ordering[A]) = this(0, null)(ordering)

protected val tree: RedBlack[A]#Tree[Unit] = if (size == 0) Empty() else t
protected val tree: RedBlack#Tree[A, Unit] = if (size == 0) Empty() else t

private def newSet(s: Int, t: RedBlack[A]#Tree[Unit]) = new TreeSet[A](s, t)
private def newSet(s: Int, t: RedBlack#Tree[A, Unit]) = new TreeSet[A](s, t)

/** A factory to create empty sets of the same type of keys.
*/
Expand Down
0