diff options
author | Erik Rozendaal <erik@deler.org> | 2011-12-19 23:08:06 +0100 |
---|---|---|
committer | Erik Rozendaal <erik@deler.org> | 2011-12-28 13:12:34 +0100 |
commit | 418adc642cbde26c09fe8ee24e019d89f6b123f9 (patch) | |
tree | 9e1a784ab5535e7d076db3f3fbfe326557d60ab3 | |
parent | a02a81574ea2329dd04241abcba8f8fba40e61ac (diff) | |
download | scala-418adc642cbde26c09fe8ee24e019d89f6b123f9.tar.gz scala-418adc642cbde26c09fe8ee24e019d89f6b123f9.tar.bz2 scala-418adc642cbde26c09fe8ee24e019d89f6b123f9.zip |
Moved type parameter A from RedBlack to Tree.
-rw-r--r-- | src/library/scala/collection/immutable/RedBlack.scala | 124 | ||||
-rw-r--r-- | src/library/scala/collection/immutable/TreeMap.scala | 10 | ||||
-rw-r--r-- | src/library/scala/collection/immutable/TreeSet.scala | 8 |
3 files changed, 71 insertions, 71 deletions
diff --git a/src/library/scala/collection/immutable/RedBlack.scala b/src/library/scala/collection/immutable/RedBlack.scala index 6ca5a286f4..3fbe9a3407 100644 --- a/src/library/scala/collection/immutable/RedBlack.scala +++ b/src/library/scala/collection/immutable/RedBlack.scala @@ -16,46 +16,46 @@ 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)) => @@ -63,7 +63,7 @@ abstract class RedBlack[A] extends Serializable { 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)) => @@ -71,15 +71,15 @@ abstract class RedBlack[A] extends Serializable { 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, 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) => @@ -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)) => @@ -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) => @@ -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)) => @@ -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 @@ -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))) @@ -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(_, _, _, _)) => @@ -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) @@ -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 @@ -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)(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 @@ -280,20 +280,20 @@ 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 @@ -301,7 +301,7 @@ abstract class RedBlack[A] extends Serializable { 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() @@ -309,17 +309,17 @@ abstract class RedBlack[A] extends Serializable { } @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() } } diff --git a/src/library/scala/collection/immutable/TreeMap.scala b/src/library/scala/collection/immutable/TreeMap.scala index bdb4533faa..3dfda05e17 100644 --- a/src/library/scala/collection/immutable/TreeMap.scala +++ b/src/library/scala/collection/immutable/TreeMap.scala @@ -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. @@ -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]] @@ -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) @@ -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 } diff --git a/src/library/scala/collection/immutable/TreeSet.scala b/src/library/scala/collection/immutable/TreeSet.scala index 7b90d6d9c3..47a28f88df 100644 --- a/src/library/scala/collection/immutable/TreeSet.scala +++ b/src/library/scala/collection/immutable/TreeSet.scala @@ -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" @@ -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. */ |