summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/compiler/scala/tools/nsc/interpreter/IMain.scala3
-rw-r--r--src/compiler/scala/tools/nsc/interpreter/Power.scala144
-rw-r--r--src/compiler/scala/tools/nsc/typechecker/Typers.scala2
-rw-r--r--src/library/scala/collection/immutable/List.scala2
-rw-r--r--src/library/scala/collection/mutable/AVLTree.scala289
-rw-r--r--src/library/scala/collection/mutable/TreeSet.scala16
-rw-r--r--test/benchmarking/TreeSetInsert.scala68
-rw-r--r--test/benchmarking/TreeSetInsertRandom.scala65
-rw-r--r--test/benchmarking/TreeSetIterator.scala69
-rw-r--r--test/benchmarking/TreeSetRemove.scala69
-rw-r--r--test/benchmarking/TreeSetRemoveRandom.scala66
-rw-r--r--test/files/pos/t4336.scala19
-rw-r--r--test/files/scalacheck/avl.scala114
13 files changed, 733 insertions, 193 deletions
diff --git a/src/compiler/scala/tools/nsc/interpreter/IMain.scala b/src/compiler/scala/tools/nsc/interpreter/IMain.scala
index 8cdd2334ab..567d6c2f78 100644
--- a/src/compiler/scala/tools/nsc/interpreter/IMain.scala
+++ b/src/compiler/scala/tools/nsc/interpreter/IMain.scala
@@ -1125,6 +1125,9 @@ class IMain(initialSettings: Settings, protected val out: JPrintWriter) extends
val termname = newTypeName(name)
findName(termname) getOrElse getModuleIfDefined(termname)
}
+ def types[T: ClassManifest] : Symbol = types(classManifest[T].erasure.getName)
+ def terms[T: ClassManifest] : Symbol = terms(classManifest[T].erasure.getName)
+ def apply[T: ClassManifest] : Symbol = apply(classManifest[T].erasure.getName)
/** the previous requests this interpreter has processed */
private lazy val prevRequests = mutable.ListBuffer[Request]()
diff --git a/src/compiler/scala/tools/nsc/interpreter/Power.scala b/src/compiler/scala/tools/nsc/interpreter/Power.scala
index b4a9b9b0e3..2ec41506ab 100644
--- a/src/compiler/scala/tools/nsc/interpreter/Power.scala
+++ b/src/compiler/scala/tools/nsc/interpreter/Power.scala
@@ -20,7 +20,7 @@ import io.{ Path }
class Power[ReplValsImpl <: ReplVals : Manifest](val intp: IMain, replVals: ReplValsImpl) {
import intp.{ beQuietDuring, typeOfExpression, interpret, parse }
import intp.global._
- import definitions.{ manifestToType, getClassIfDefined, getModuleIfDefined }
+ import definitions.{ manifestToType, manifestToSymbol, getClassIfDefined, getModuleIfDefined }
abstract class SymSlurper {
def isKeep(sym: Symbol): Boolean
@@ -65,10 +65,7 @@ class Power[ReplValsImpl <: ReplVals : Manifest](val intp: IMain, replVals: Repl
}
}
- class PackageSlurper(pkgName: String) extends SymSlurper {
- val pkgSymbol = getModuleIfDefined(pkgName)
- val modClass = pkgSymbol.moduleClass
-
+ class PackageSlurper(packageClass: Symbol) extends SymSlurper {
/** Looking for dwindling returns */
def droppedEnough() = unseenHistory.size >= 4 && {
unseenHistory takeRight 4 sliding 2 forall { it =>
@@ -79,9 +76,16 @@ class Power[ReplValsImpl <: ReplVals : Manifest](val intp: IMain, replVals: Repl
def isRecur(sym: Symbol) = true
def isIgnore(sym: Symbol) = sym.isAnonOrRefinementClass || (sym.name.toString contains "$mc")
- def isKeep(sym: Symbol) = sym.hasTransOwner(modClass)
+ def isKeep(sym: Symbol) = sym.hasTransOwner(packageClass)
def isFinished() = droppedEnough()
- def slurp() = apply(modClass)
+ def slurp() = {
+ if (packageClass.isPackageClass)
+ apply(packageClass)
+ else {
+ repldbg("Not a package class! " + packageClass)
+ Set()
+ }
+ }
}
private def customBanner = replProps.powerBanner.option flatMap (f => io.File(f).safeSlurp())
@@ -124,7 +128,7 @@ class Power[ReplValsImpl <: ReplVals : Manifest](val intp: IMain, replVals: Repl
def to_str(m: Symbol) = "%12s %s".format(
m.decodedName, "" + elimRefinement(m.accessedOrSelf.tpe) stripPrefix "scala.tools.nsc.")
- ( rutil.info[ReplValsImpl].declares
+ ( rutil.info[ReplValsImpl].membersDeclared
filter (m => m.isPublic && !m.hasModuleFlag && !m.isConstructor)
sortBy (_.decodedName)
map to_str
@@ -136,59 +140,78 @@ class Power[ReplValsImpl <: ReplVals : Manifest](val intp: IMain, replVals: Repl
implicit def apply[T: Manifest] : InternalInfo[T] = new InternalInfo[T](None)
}
object InternalInfo extends LowPriorityInternalInfo { }
+
+ /** Now dealing with the problem of acidentally calling a method on Type
+ * when you're holding a Symbol and seeing the Symbol converted to the
+ * type of Symbol rather than the type of the thing represented by the
+ * symbol, by only implicitly installing one method, "?", and the rest
+ * of the conveniences exist on that wrapper.
+ */
+ trait LowPriorityInternalInfoWrapper {
+ implicit def apply[T: Manifest] : InternalInfoWrapper[T] = new InternalInfoWrapper[T](None)
+ }
+ object InternalInfoWrapper extends LowPriorityInternalInfoWrapper {
+
+ }
+ class InternalInfoWrapper[T: Manifest](value: Option[T] = None) {
+ def ? : InternalInfo[T] = new InternalInfo[T](value)
+ }
/** Todos...
* translate manifest type arguments into applied types
* customizable symbol filter (had to hardcode no-spec to reduce noise)
*/
class InternalInfo[T: Manifest](value: Option[T] = None) {
- // Decided it was unwise to have implicit conversions via commonly
- // used type/symbol methods, because it's too easy to e.g. call
- // "x.tpe" where x is a Type, and rather than failing you get the
- // Type representing Types#Type (or Manifest, or whatever.)
- private def tpe = tpe_
- private def symbol = symbol_
- private def name = name_
-
- def symbol_ : Symbol = getClassIfDefined(erasure.getName)
- def tpe_ : Type = manifestToType(man)
- def name_ : Name = symbol.name
- def companion = symbol.companionSymbol
- def info = symbol.info
- def module = symbol.moduleClass
- def owner = symbol.owner
- def owners = symbol.ownerChain drop 1
- def defn = symbol.defString
- def decls = symbol.info.decls
-
- def declares = decls.toList
- def inherits = members filterNot (declares contains _)
- def types = members filter (_.name.isTypeName)
- def methods = members filter (_.isMethod)
- def overrides = declares filter (_.isOverride)
- def inPackage = owners find (x => x.isPackageClass || x.isPackage) getOrElse definitions.RootPackage
-
- def man = manifest[T]
- def erasure = man.erasure
- def members = tpe.members filterNot (_.name.toString contains "$mc")
- def allMembers = tpe.members
- def bts = info.baseTypeSeq.toList
- def btsmap = bts map (x => (x, x.decls.toList)) toMap
- def pkgName = Option(erasure.getPackage) map (_.getName)
- def pkg = pkgName map getModuleIfDefined getOrElse NoSymbol
- def pkgmates = pkg.tpe.members
- def pkgslurp = pkgName match {
- case Some(name) => new PackageSlurper(name) slurp()
- case _ => Set()
- }
- def ? = this
-
- def whoHas(name: String) = bts filter (_.decls exists (_.name.toString == name))
- def <:<[U: Manifest](other: U) = tpe <:< InternalInfo[U].tpe
- def lub[U: Manifest](other: U) = intp.global.lub(List(tpe, InternalInfo[U].tpe))
- def glb[U: Manifest](other: U) = intp.global.glb(List(tpe, InternalInfo[U].tpe))
+ private def newInfo[U: Manifest](value: U): InternalInfo[U] = new InternalInfo[U](Some(value))
+ private def isSpecialized(s: Symbol) = s.name.toString contains "$mc"
+ private def isImplClass(s: Symbol) = s.name.toString endsWith "$class"
+
+ /** Standard noise reduction filter. */
+ def excludeMember(s: Symbol) = (
+ isSpecialized(s)
+ || isImplClass(s)
+ || s.isAnonOrRefinementClass
+ || s.isAnonymousFunction
+ )
+ def symbol = manifestToSymbol(fullManifest)
+ def tpe = manifestToType(fullManifest)
+ def name = symbol.name
+ def companion = symbol.companionSymbol
+ def info = symbol.info
+ def moduleClass = symbol.moduleClass
+ def owner = symbol.owner
+ def owners = symbol.ownerChain drop 1
+ def signature = symbol.defString
+
+ def decls = info.decls
+ def declsOverride = membersDeclared filter (_.isOverride)
+ def declsOriginal = membersDeclared filterNot (_.isOverride)
+
+ def members = membersUnabridged filterNot excludeMember
+ def membersUnabridged = tpe.members
+ def membersDeclared = members filterNot excludeMember
+ def membersInherited = members filterNot (membersDeclared contains _)
+ def memberTypes = members filter (_.name.isTypeName)
+ def memberMethods = members filter (_.isMethod)
+
+ def pkg = symbol.enclosingPackage
+ def pkgName = pkg.fullName
+ def pkgClass = symbol.enclosingPackageClass
+ def pkgMembers = pkg.info.members filterNot excludeMember
+ def pkgClasses = pkgMembers filter (s => s.isClass && s.isDefinedInPackage)
+ def pkgSymbols = new PackageSlurper(pkgClass).slurp() filterNot excludeMember
+
+ def fullManifest = manifest[T]
+ def erasure = fullManifest.erasure
+ def shortClass = erasure.getName split "[$.]" last
+ def baseTypeSeq = tpe.baseTypeSeq.toList
+ def baseTypeSeqMap = baseTypeSeq map (x => (x, x.decls.toList)) toMap
+
+ def baseTypeWhichDefines(name: String) = baseTypeSeq filter (_.decls exists (_.name.toString == name))
+ def <:<[U: Manifest](other: U) = tpe <:< newInfo(other).tpe
+ def lub[U: Manifest](other: U) = intp.global.lub(List(tpe, newInfo(other).tpe))
+ def glb[U: Manifest](other: U) = intp.global.glb(List(tpe, newInfo(other).tpe))
- def shortClass = erasure.getName split "[$.]" last
override def toString = value match {
case Some(x) => "%s (%s)".format(x, shortClass)
case _ => erasure.getName
@@ -288,11 +311,17 @@ class Power[ReplValsImpl <: ReplVals : Manifest](val intp: IMain, replVals: Repl
def slurp(): String = io.Streamable.slurp(url)
def pp() { intp prettyPrint slurp() }
}
-
+ class RichSymbolList(syms: List[Symbol]) {
+ def sigs = syms map (_.defString)
+ def infos = syms map (_.info)
+ }
+
trait Implicits1 {
// fallback
implicit def replPrinting[T](x: T)(implicit pretty: Prettifier[T] = Prettifier.default[T]) =
new SinglePrettifierClass[T](x)
+
+ implicit def liftToTypeName(s: String): TypeName = newTypeName(s)
}
trait Implicits2 extends Implicits1 {
class RichSymbol(sym: Symbol) {
@@ -309,7 +338,7 @@ class Power[ReplValsImpl <: ReplVals : Manifest](val intp: IMain, replVals: Repl
implicit lazy val powerSymbolOrdering: Ordering[Symbol] = Ordering[Name] on (_.name)
implicit lazy val powerTypeOrdering: Ordering[Type] = Ordering[Symbol] on (_.typeSymbol)
- implicit def replInternalInfo[T: Manifest](x: T): InternalInfo[T] = new InternalInfo[T](Some(x))
+ implicit def replInternalInfo[T: Manifest](x: T): InternalInfoWrapper[T] = new InternalInfoWrapper[T](Some(x))
implicit def replEnhancedStrings(s: String): RichReplString = new RichReplString(s)
implicit def replMultiPrinting[T: Prettifier](xs: TraversableOnce[T]): MultiPrettifierClass[T] =
new MultiPrettifierClass[T](xs.toSeq)
@@ -318,6 +347,9 @@ class Power[ReplValsImpl <: ReplVals : Manifest](val intp: IMain, replVals: Repl
implicit def replInputStream(in: InputStream)(implicit codec: Codec) = new RichInputStream(in)
implicit def replEnhancedURLs(url: URL)(implicit codec: Codec): RichReplURL = new RichReplURL(url)(codec)
+
+ implicit def liftToTermName(s: String): TermName = newTermName(s)
+ implicit def replListOfSymbols(xs: List[Symbol]) = new RichSymbolList(xs)
}
trait ReplUtilities {
diff --git a/src/compiler/scala/tools/nsc/typechecker/Typers.scala b/src/compiler/scala/tools/nsc/typechecker/Typers.scala
index 161daa4275..7c16c7642d 100644
--- a/src/compiler/scala/tools/nsc/typechecker/Typers.scala
+++ b/src/compiler/scala/tools/nsc/typechecker/Typers.scala
@@ -793,7 +793,7 @@ trait Typers extends Modes with Adaptations with PatMatVirtualiser {
val tree0 = etaExpand(context.unit, tree)
// println("eta "+tree+" ---> "+tree0+":"+tree0.tpe+" undet: "+context.undetparams+ " mode: "+Integer.toHexString(mode))
- if (meth.typeParams.nonEmpty) {
+ if (context.undetparams.nonEmpty) {
// #2624: need to infer type arguments for eta expansion of a polymorphic method
// context.undetparams contains clones of meth.typeParams (fresh ones were generated in etaExpand)
// need to run typer on tree0, since etaExpansion sets the tpe's of its subtrees to null
diff --git a/src/library/scala/collection/immutable/List.scala b/src/library/scala/collection/immutable/List.scala
index f789de9fac..5f3f9b717f 100644
--- a/src/library/scala/collection/immutable/List.scala
+++ b/src/library/scala/collection/immutable/List.scala
@@ -620,7 +620,7 @@ object List extends SeqFactory[List] {
}
/** Only used for list serialization */
-@SerialVersionUID(0L - 8476791151975527571L)
+@SerialVersionUID(0L - 8287891243975527522L)
private[scala] case object ListSerializeStart
/** Only used for list serialization */
diff --git a/src/library/scala/collection/mutable/AVLTree.scala b/src/library/scala/collection/mutable/AVLTree.scala
index 0cf6cb06e5..ba2af8f120 100644
--- a/src/library/scala/collection/mutable/AVLTree.scala
+++ b/src/library/scala/collection/mutable/AVLTree.scala
@@ -9,7 +9,6 @@
package scala.collection
package mutable
-import annotation.tailrec
/**
* An immutable AVL Tree implementation used by mutable.TreeSet
@@ -22,185 +21,221 @@ private[mutable] sealed trait AVLTree[+A] extends Serializable {
def depth: Int
-}
+ def iterator[B >: A]: Iterator[B] = Iterator.empty
-private case class Node[A](val data: A, val left: AVLTree[A], val right: AVLTree[A]) extends AVLTree[A] {
- override val balance: Int = right.depth - left.depth
+ def contains[B >: A](value: B, ordering: Ordering[B]): Boolean = false
- override val depth: Int = math.max(left.depth, right.depth) + 1
+ /**
+ * Returns a new tree containing the given element.
+ * Thows an IllegalArgumentException if element is already present.
+ *
+ */
+ def insert[B >: A](value: B, ordering: Ordering[B]): AVLTree[B] = Node(value, Leaf, Leaf)
+ /**
+ * Return a new tree which not contains given element.
+ *
+ */
+ def remove[B >: A](value: B, ordering: Ordering[B]): AVLTree[A] =
+ throw new NoSuchElementException(String.valueOf(value))
+
+ /**
+ * Return a tuple containing the smallest element of the provided tree
+ * and a new tree from which this element has been extracted.
+ *
+ */
+ def removeMin[B >: A]: (B, AVLTree[B]) = sys.error("Should not happen.")
+
+ /**
+ * Return a tuple containing the biggest element of the provided tree
+ * and a new tree from which this element has been extracted.
+ *
+ */
+ def removeMax[B >: A]: (B, AVLTree[B]) = sys.error("Should not happen.")
+
+ def rebalance[B >: A]: AVLTree[B] = this
+
+ def leftRotation[B >: A]: Node[B] = sys.error("Should not happen.")
+
+ def rightRotation[B >: A]: Node[B] = sys.error("Should not happen.")
+
+ def doubleLeftRotation[B >: A]: Node[B] = sys.error("Should not happen.")
+
+ def doubleRightRotation[B >: A]: Node[B] = sys.error("Should not happen.")
}
private case object Leaf extends AVLTree[Nothing] {
override val balance: Int = 0
override val depth: Int = -1
-
}
-private[mutable] object AVLTree {
+private case class Node[A](val data: A, val left: AVLTree[A], val right: AVLTree[A]) extends AVLTree[A] {
+ override val balance: Int = right.depth - left.depth
+
+ override val depth: Int = math.max(left.depth, right.depth) + 1
+
+ override def iterator[B >: A]: Iterator[B] = new AVLIterator(this)
+
+ override def contains[B >: A](value: B, ordering: Ordering[B]) = {
+ val ord = ordering.compare(value, data)
+ if (0 == ord)
+ true
+ else if (ord < 0)
+ left.contains(value, ordering)
+ else
+ right.contains(value, ordering)
+ }
/**
* Returns a new tree containing the given element.
* Thows an IllegalArgumentException if element is already present.
*
*/
- def insert[A](value: A, tree: AVLTree[A], ordering: Ordering[A]): AVLTree[A] = {
- @tailrec
- def insertTC(value: A, tree: AVLTree[A], reassemble: AVLTree[A] => AVLTree[A]): AVLTree[A] = tree match {
- case Leaf => reassemble(Node(value, Leaf, Leaf))
-
- case Node(a, left, right) => if (0 == ordering.compare(value, a)) {
- throw new IllegalArgumentException()
- } else if (-1 == ordering.compare(value, a)) {
- insertTC(value, left, x => reassemble(rebalance(Node(a, x, right))))
- } else {
- insertTC(value, right, x => reassemble(rebalance(Node(a, left, x))))
- }
- }
-
- insertTC(value, tree, x => rebalance(x))
- }
-
- def contains[A](value: A, tree: AVLTree[A], ordering: Ordering[A]): Boolean = tree match {
- case Leaf => false
-
- case Node(a, left, right) => if (0 == ordering.compare(value, a)) {
- true
- } else if (-1 == ordering.compare(value, a)) {
- contains(value, left, ordering)
- } else {
- contains(value, right, ordering)
- }
+ override def insert[B >: A](value: B, ordering: Ordering[B]) = {
+ val ord = ordering.compare(value, data)
+ if (0 == ord)
+ throw new IllegalArgumentException()
+ else if (ord < 0)
+ Node(data, left.insert(value, ordering), right).rebalance
+ else
+ Node(data, left, right.insert(value, ordering)).rebalance
}
/**
* Return a new tree which not contains given element.
*
*/
- def remove[A](value: A, tree: AVLTree[A], ordering: Ordering[A]): AVLTree[A] = tree match {
- case Leaf => throw new NoSuchElementException()
-
- case Node(a, Leaf, Leaf) => if (0 == ordering.compare(value, a)) {
- Leaf
- } else {
- throw new NoSuchElementException()
- }
-
- case Node(a, left, right@Node(_, _, _)) => if (0 == ordering.compare(value, a)) {
- val (min, newRight) = removeMin(right)
- rebalance(Node(min, left, newRight))
- } else if (-1 == ordering.compare(value, a)) {
- rebalance(Node(a, remove(value, left, ordering), right))
- } else {
- rebalance(Node(a, left, remove(value, right, ordering)))
- }
-
- case Node(a, left@Node(_, _, _), right) => if (0 == ordering.compare(value, a)) {
- val (max, newLeft) = removeMax(left)
- rebalance(Node(max, newLeft, right))
- } else if (-1 == ordering.compare(value, a)) {
- rebalance(Node(a, remove(value, left, ordering), right))
+ override def remove[B >: A](value: B, ordering: Ordering[B]): AVLTree[A] = {
+ val ord = ordering.compare(value, data)
+ if(ord == 0) {
+ if (Leaf == left) {
+ if (Leaf == right) {
+ Leaf
+ } else {
+ val (min, newRight) = right.removeMin
+ Node(min, left, newRight).rebalance
+ }
+ } else {
+ val (max, newLeft) = left.removeMax
+ Node(max, newLeft, right).rebalance
+ }
+ } else if (ord < 0) {
+ Node(data, left.remove(value, ordering), right).rebalance
} else {
- rebalance(Node(a, left, remove(value, right, ordering)))
+ Node(data, left, right.remove(value, ordering)).rebalance
}
}
/**
- * Return a tuple containing the biggest element of the provided tree
+ * Return a tuple containing the smallest element of the provided tree
* and a new tree from which this element has been extracted.
*
*/
- def removeMax[A](tree: Node[A]): (A, AVLTree[A]) = {
- @tailrec
- def removeMaxTC(tree: AVLTree[A], assemble: (A, AVLTree[A]) => (A, AVLTree[A])): (A, AVLTree[A]) = tree match {
- case Node(a, Leaf, Leaf) => assemble(a, Leaf)
- case Node(a, left, Leaf) => assemble(a, left)
- case Node(a, left, right) => removeMaxTC(right,
- (max: A, avl: AVLTree[A]) => assemble(max, rebalance(Node(a, left, avl))))
- case Leaf => sys.error("Should not happen.")
+ override def removeMin[B >: A]: (B, AVLTree[B]) = {
+ if (Leaf == left)
+ (data, right)
+ else {
+ val (min, newLeft) = left.removeMin
+ (min, Node(data, newLeft, right).rebalance)
}
-
- removeMaxTC(tree, (a, b) => (a, b))
}
/**
- * Return a tuple containing the smallest element of the provided tree
+ * Return a tuple containing the biggest element of the provided tree
* and a new tree from which this element has been extracted.
*
*/
- def removeMin[A](tree: Node[A]): (A, AVLTree[A]) = {
- @tailrec
- def removeMinTC(tree: AVLTree[A], assemble: (A, AVLTree[A]) => (A, AVLTree[A])): (A, AVLTree[A]) = tree match {
- case Node(a, Leaf, Leaf) => assemble(a, Leaf)
- case Node(a, Leaf, right) => assemble(a, right)
- case Node(a, left, right) => removeMinTC(left,
- (min: A, avl: AVLTree[A]) => assemble(min, rebalance(Node(a, avl, right))))
- case Leaf => sys.error("Should not happen.")
+ override def removeMax[B >: A]: (B, AVLTree[B]) = {
+ if (Leaf == right)
+ (data, left)
+ else {
+ val (max, newRight) = right.removeMax
+ (max, Node(data, left, newRight).rebalance)
}
-
- removeMinTC(tree, (a, b) => (a, b))
}
-
- /**
- * Returns a bounded stream of elements in the tree.
- *
- */
- def toStream[A](tree: AVLTree[A], isLeftAcceptable: A => Boolean, isRightAcceptable: A => Boolean): Stream[A] = tree match {
- case Leaf => Stream.empty
-
- case Node(a, left, right) => if (isLeftAcceptable(a)) {
- if (isRightAcceptable(a)) {
- toStream(left, isLeftAcceptable, isRightAcceptable) ++ Stream(a) ++ toStream(right, isLeftAcceptable, isRightAcceptable)
- } else {
- toStream(left, isLeftAcceptable, isRightAcceptable)
- }
- } else if (isRightAcceptable(a)) {
- toStream(right, isLeftAcceptable, isRightAcceptable)
+
+ override def rebalance[B >: A] = {
+ if (-2 == balance) {
+ if (1 == left.balance)
+ doubleRightRotation
+ else
+ rightRotation
+ } else if (2 == balance) {
+ if (-1 == right.balance)
+ doubleLeftRotation
+ else
+ leftRotation
} else {
- Stream.empty
+ this
}
}
- /**
- * Returns a bounded iterator of elements in the tree.
- *
- */
- def iterator[A](tree: AVLTree[A], isLeftAcceptable: A => Boolean, isRightAcceptable: A => Boolean): Iterator[A] =
- toStream(tree, isLeftAcceptable, isRightAcceptable).iterator
-
- def rebalance[A](tree: AVLTree[A]): AVLTree[A] = (tree, tree.balance) match {
- case (node@Node(_, left, _), -2) => left.balance match {
- case 1 => doubleRightRotation(node)
- case _ => rightRotation(node)
- }
-
- case (node@Node(_, _, right), 2) => right.balance match {
- case -1 => doubleLeftRotation(node)
- case _ => leftRotation(node)
- }
+ override def leftRotation[B >: A] = {
+ if (Leaf != right) {
+ val r: Node[A] = right.asInstanceOf[Node[A]]
+ Node(r.data, Node(data, left, r.left), r.right)
+ } else sys.error("Should not happen.")
+ }
- case _ => tree
+ override def rightRotation[B >: A] = {
+ if (Leaf != left) {
+ val l: Node[A] = left.asInstanceOf[Node[A]]
+ Node(l.data, l.left, Node(data, l.right, right))
+ } else sys.error("Should not happen.")
}
- def leftRotation[A](tree: Node[A]): AVLTree[A] = tree.right match {
- case Node(b, left, right) => Node(b, Node(tree.data, tree.left, left), right)
- case _ => sys.error("Should not happen.")
+ override def doubleLeftRotation[B >: A] = {
+ if (Leaf != right) {
+ val r: Node[A] = right.asInstanceOf[Node[A]]
+ // Let's save an instanceOf by 'inlining' the left rotation
+ val rightRotated = r.rightRotation
+ Node(rightRotated.data, Node(data, left, rightRotated.left), rightRotated.right)
+ } else sys.error("Should not happen.")
}
- def rightRotation[A](tree: Node[A]): AVLTree[A] = tree.left match {
- case Node(b, left, right) => Node(b, left, Node(tree.data, right, tree.right))
- case _ => sys.error("Should not happen.")
+ override def doubleRightRotation[B >: A] = {
+ if (Leaf != left) {
+ val l: Node[A] = left.asInstanceOf[Node[A]]
+ // Let's save an instanceOf by 'inlining' the right rotation
+ val leftRotated = l.leftRotation
+ Node(leftRotated.data, leftRotated.left, Node(data, leftRotated.right, right))
+ } else sys.error("Should not happen.")
}
+}
+
+private class AVLIterator[A](root: Node[A]) extends Iterator[A] {
+ val stack = mutable.ArrayStack[Node[A]](root)
+ diveLeft()
- def doubleLeftRotation[A](tree: Node[A]): AVLTree[A] = tree.right match {
- case right@Node(b, l, r) => leftRotation(Node(tree.data, tree.left, rightRotation(right)))
- case _ => sys.error("Should not happen.")
+ private def diveLeft(): Unit = {
+ if (Leaf != stack.head.left) {
+ val left: Node[A] = stack.head.left.asInstanceOf[Node[A]]
+ stack.push(left)
+ diveLeft()
+ }
}
- def doubleRightRotation[A](tree: Node[A]): AVLTree[A] = tree.left match {
- case left@Node(b, l, r) => rightRotation(Node(tree.data, leftRotation(left), tree.right))
- case _ => sys.error("Should not happen.")
+ private def engageRight(): Unit = {
+ if (Leaf != stack.head.right) {
+ val right: Node[A] = stack.head.right.asInstanceOf[Node[A]]
+ stack.pop
+ stack.push(right)
+ diveLeft()
+ } else
+ stack.pop
}
+ override def hasNext: Boolean = !stack.isEmpty
+
+ override def next(): A = {
+ if (stack.isEmpty)
+ throw new NoSuchElementException()
+ else {
+ val result = stack.head.data
+ // Let's maintain stack for the next invocation
+ engageRight()
+ result
+ }
+ }
}
diff --git a/src/library/scala/collection/mutable/TreeSet.scala b/src/library/scala/collection/mutable/TreeSet.scala
index 38fa0c953f..e0f1c3adfe 100644
--- a/src/library/scala/collection/mutable/TreeSet.scala
+++ b/src/library/scala/collection/mutable/TreeSet.scala
@@ -79,7 +79,7 @@ class TreeSet[A](implicit val ordering: Ordering[A]) extends SortedSet[A] with S
override def -=(elem: A): this.type = {
try {
- resolve.avl = AVLTree.remove(elem, resolve.avl, ordering)
+ resolve.avl = resolve.avl.remove(elem, ordering)
resolve.cardinality = resolve.cardinality - 1
} catch {
case e: NoSuchElementException => ()
@@ -89,7 +89,7 @@ class TreeSet[A](implicit val ordering: Ordering[A]) extends SortedSet[A] with S
override def +=(elem: A): this.type = {
try {
- resolve.avl = AVLTree.insert(elem, resolve.avl, ordering)
+ resolve.avl = resolve.avl.insert(elem, ordering)
resolve.cardinality = resolve.cardinality + 1
} catch {
case e: IllegalArgumentException => ()
@@ -98,7 +98,7 @@ class TreeSet[A](implicit val ordering: Ordering[A]) extends SortedSet[A] with S
}
/**
- * Thanks to the nature immutable of the
+ * Thanks to the immutable nature of the
* underlying AVL Tree, we can share it with
* the clone. So clone complexity in time is O(1).
*
@@ -113,11 +113,11 @@ class TreeSet[A](implicit val ordering: Ordering[A]) extends SortedSet[A] with S
override def contains(elem: A): Boolean = {
isLeftAcceptable(from, ordering)(elem) &&
isRightAcceptable(until, ordering)(elem) &&
- AVLTree.contains(elem, resolve.avl, ordering)
+ resolve.avl.contains(elem, ordering)
}
- override def iterator: Iterator[A] =
- AVLTree.iterator(resolve.avl,
- isLeftAcceptable(from, ordering),
- isRightAcceptable(until, ordering))
+ override def iterator: Iterator[A] = resolve.avl.iterator
+ .dropWhile(e => !isLeftAcceptable(from, ordering)(e))
+ .takeWhile(e => isRightAcceptable(until, ordering)(e))
+
}
diff --git a/test/benchmarking/TreeSetInsert.scala b/test/benchmarking/TreeSetInsert.scala
new file mode 100644
index 0000000000..9ede8aedc5
--- /dev/null
+++ b/test/benchmarking/TreeSetInsert.scala
@@ -0,0 +1,68 @@
+
+object TreeSetInsert {
+
+ def main(args: Array[String]): Unit = {
+ val n = 500000
+ JavaUtilTS.main(args)
+ MutableTS.main(args)
+ ImmutableTS.main(args)
+ }
+}
+
+class Dummy(val a: Int) extends math.Ordered[Dummy] {
+ def compare(other: Dummy) = this.a - other.a
+
+ override def toString = a.toString
+ }
+
+
+object JavaUtilTS extends testing.Benchmark {
+ val length = sys.props("length").toInt
+ var data: Array[Dummy] = (0 until length) map { a => new Dummy(a) } toArray
+ var t: java.util.TreeSet[Dummy] = null
+
+ def run = {
+ t = new java.util.TreeSet[Dummy]()
+
+ var i = 0
+ while (i < length) {
+ val elem = data(i)
+ t add elem
+ i += 1
+ }
+ }
+}
+
+object MutableTS extends testing.Benchmark {
+ val length = sys.props("length").toInt
+ var data: Array[Dummy] = (0 until length) map { a => new Dummy(a) } toArray
+ var t: collection.mutable.TreeSet[Dummy] = null
+
+ def run = {
+ t = collection.mutable.TreeSet[Dummy]()
+
+ var i = 0
+ while (i < length) {
+ val elem = data(i)
+ t += elem
+ i += 1
+ }
+ }
+}
+
+object ImmutableTS extends testing.Benchmark {
+ val length = sys.props("length").toInt
+ var data: Array[Dummy] = (0 until length) map { a => new Dummy(a) } toArray
+ var t: collection.immutable.TreeSet[Dummy] = null
+
+ def run = {
+ t = collection.immutable.TreeSet[Dummy]()
+
+ var i = 0
+ while (i < length) {
+ val elem = data(i)
+ t += elem
+ i += 1
+ }
+ }
+}
diff --git a/test/benchmarking/TreeSetInsertRandom.scala b/test/benchmarking/TreeSetInsertRandom.scala
new file mode 100644
index 0000000000..7f182548b7
--- /dev/null
+++ b/test/benchmarking/TreeSetInsertRandom.scala
@@ -0,0 +1,65 @@
+
+object TreeSetInsertRandom {
+
+ def main(args: Array[String]): Unit = {
+ val n = 500000
+ new JavaUtilTS(n).main(args)
+ new MutableTS(n).main(args)
+ new ImmutableTS(n).main(args)
+ }
+}
+
+class Dummy(val a: Int) extends math.Ordered[Dummy] {
+ def compare(other: Dummy) = this.a - other.a
+
+ override def toString = a.toString
+ }
+
+
+class JavaUtilTS(val length: Int) extends testing.Benchmark {
+ var data: Array[Dummy] = util.Random.shuffle((0 until length) map { a => new Dummy(a) }) toArray
+ var t: java.util.TreeSet[Dummy] = null
+
+ def run = {
+ t = new java.util.TreeSet[Dummy]()
+
+ var i = 0
+ while (i < length) {
+ val elem = data(i)
+ t add elem
+ i += 1
+ }
+ }
+}
+
+class MutableTS(val length: Int) extends testing.Benchmark {
+ var data: Array[Dummy] = util.Random.shuffle((0 until length) map { a => new Dummy(a) }) toArray
+ var t: collection.mutable.TreeSet[Dummy] = null
+
+ def run = {
+ t = collection.mutable.TreeSet[Dummy]()
+
+ var i = 0
+ while (i < length) {
+ val elem = data(i)
+ t += elem
+ i += 1
+ }
+ }
+}
+
+class ImmutableTS(val length: Int) extends testing.Benchmark {
+ var data: Array[Dummy] = util.Random.shuffle((0 until length) map { a => new Dummy(a) }) toArray
+ var t: collection.immutable.TreeSet[Dummy] = null
+
+ def run = {
+ t = collection.immutable.TreeSet[Dummy]()
+
+ var i = 0
+ while (i < length) {
+ val elem = data(i)
+ t += elem
+ i += 1
+ }
+ }
+}
diff --git a/test/benchmarking/TreeSetIterator.scala b/test/benchmarking/TreeSetIterator.scala
new file mode 100644
index 0000000000..08c20e8b0c
--- /dev/null
+++ b/test/benchmarking/TreeSetIterator.scala
@@ -0,0 +1,69 @@
+
+object TreeSetIterator {
+
+ def main(args: Array[String]): Unit = {
+ val n = 500000
+ JavaUtilTS.main(args)
+ MutableTS.main(args)
+ ImmutableTS.main(args)
+ }
+}
+
+class Dummy(val a: Int) extends math.Ordered[Dummy] {
+ def compare(other: Dummy) = this.a - other.a
+
+ override def toString = a.toString
+ }
+
+
+object JavaUtilTS extends testing.Benchmark {
+ val length = sys.props("length").toInt
+ var data: Array[Dummy] = (0 until length) map { a => new Dummy(a) } toArray
+ var t: java.util.TreeSet[Dummy] = null
+
+ def run = {
+ t = new java.util.TreeSet[Dummy]()
+ data foreach { a => t add a }
+
+ var i: Dummy = null
+ var it = t.iterator
+ while (it.hasNext) {
+ i = it.next
+ }
+ i
+ }
+}
+
+object MutableTS extends testing.Benchmark {
+ val length = sys.props("length").toInt
+ var data: Array[Dummy] = (0 until length) map { a => new Dummy(a) } toArray
+ var t: collection.mutable.TreeSet[Dummy] = null
+
+ def run = {
+ t = collection.mutable.TreeSet[Dummy](data: _*)
+
+ var i: Dummy = null
+ var it = t.iterator
+ while (it.hasNext) {
+ i = it.next
+ }
+ i
+ }
+}
+
+object ImmutableTS extends testing.Benchmark {
+ val length = sys.props("length").toInt
+ var data: Array[Dummy] = (0 until length) map { a => new Dummy(a) } toArray
+ var t: collection.immutable.TreeSet[Dummy] = null
+
+ def run = {
+ t = collection.immutable.TreeSet[Dummy](data: _*)
+
+ var i: Dummy = null
+ var it = t.iterator
+ while (it.hasNext) {
+ i = it.next
+ }
+ i
+ }
+}
diff --git a/test/benchmarking/TreeSetRemove.scala b/test/benchmarking/TreeSetRemove.scala
new file mode 100644
index 0000000000..f84066f336
--- /dev/null
+++ b/test/benchmarking/TreeSetRemove.scala
@@ -0,0 +1,69 @@
+
+object TreeSetRemove {
+
+ def main(args: Array[String]): Unit = {
+ val n = 500000
+ JavaUtilTS.main(args)
+ MutableTS.main(args)
+ ImmutableTS.main(args)
+ }
+}
+
+class Dummy(val a: Int) extends math.Ordered[Dummy] {
+ def compare(other: Dummy) = this.a - other.a
+
+ override def toString = a.toString
+ }
+
+
+object JavaUtilTS extends testing.Benchmark {
+ val length = sys.props("length").toInt
+ var data: Array[Dummy] = (0 until length) map { a => new Dummy(a) } toArray
+ var t: java.util.TreeSet[Dummy] = null
+
+ def run = {
+ t = new java.util.TreeSet[Dummy]()
+ data foreach { a => t add a }
+
+ var i = 0
+ while (i < length) {
+ val elem = data(i)
+ t remove elem
+ i += 1
+ }
+ }
+}
+
+object MutableTS extends testing.Benchmark {
+ val length = sys.props("length").toInt
+ var data: Array[Dummy] = (0 until length) map { a => new Dummy(a) } toArray
+ var t: collection.mutable.TreeSet[Dummy] = null
+
+ def run = {
+ t = collection.mutable.TreeSet[Dummy](data: _*)
+
+ var i = 0
+ while (i < length) {
+ val elem = data(i)
+ t -= elem
+ i += 1
+ }
+ }
+}
+
+object ImmutableTS extends testing.Benchmark {
+ val length = sys.props("length").toInt
+ var data: Array[Dummy] = (0 until length) map { a => new Dummy(a) } toArray
+ var t: collection.immutable.TreeSet[Dummy] = null
+
+ def run = {
+ t = collection.immutable.TreeSet[Dummy](data: _*)
+
+ var i = 0
+ while (i < length) {
+ val elem = data(i)
+ t -= elem
+ i += 1
+ }
+ }
+}
diff --git a/test/benchmarking/TreeSetRemoveRandom.scala b/test/benchmarking/TreeSetRemoveRandom.scala
new file mode 100644
index 0000000000..4d311679e3
--- /dev/null
+++ b/test/benchmarking/TreeSetRemoveRandom.scala
@@ -0,0 +1,66 @@
+
+object TreeSetRemoveRandom {
+
+ def main(args: Array[String]): Unit = {
+ val n = 500000
+ new JavaUtilTS(n).main(args)
+ new MutableTS(n).main(args)
+ new ImmutableTS(n).main(args)
+ }
+}
+
+class Dummy(val a: Int) extends math.Ordered[Dummy] {
+ def compare(other: Dummy) = this.a - other.a
+
+ override def toString = a.toString
+ }
+
+
+class JavaUtilTS(val length: Int) extends testing.Benchmark {
+ var data: Array[Dummy] = util.Random.shuffle((0 until length) map { a => new Dummy(a) }) toArray
+ var t: java.util.TreeSet[Dummy] = null
+
+ def run = {
+ t = new java.util.TreeSet[Dummy]()
+ data foreach { a => t add a }
+
+ var i = 0
+ while (i < length) {
+ val elem = data(i)
+ t remove elem
+ i += 1
+ }
+ }
+}
+
+class MutableTS(val length: Int) extends testing.Benchmark {
+ var data: Array[Dummy] = util.Random.shuffle((0 until length) map { a => new Dummy(a) }) toArray
+ var t: collection.mutable.TreeSet[Dummy] = null
+
+ def run = {
+ t = collection.mutable.TreeSet[Dummy](data: _*)
+
+ var i = 0
+ while (i < length) {
+ val elem = data(i)
+ t -= elem
+ i += 1
+ }
+ }
+}
+
+class ImmutableTS(val length: Int) extends testing.Benchmark {
+ var data: Array[Dummy] = util.Random.shuffle((0 until length) map { a => new Dummy(a) }) toArray
+ var t: collection.immutable.TreeSet[Dummy] = null
+
+ def run = {
+ t = collection.immutable.TreeSet[Dummy](data: _*)
+
+ var i = 0
+ while (i < length) {
+ val elem = data(i)
+ t -= elem
+ i += 1
+ }
+ }
+}
diff --git a/test/files/pos/t4336.scala b/test/files/pos/t4336.scala
new file mode 100644
index 0000000000..e10d001585
--- /dev/null
+++ b/test/files/pos/t4336.scala
@@ -0,0 +1,19 @@
+object Main {
+ class NonGeneric {}
+ class Generic[T] {}
+
+ class Composite {
+ def contains(setup : Composite => Unit) : Composite = this
+ }
+
+ def generic[T](parent: Composite): Generic[T] = new Generic[T]
+ def nonGeneric(parent: Composite): NonGeneric = new NonGeneric
+
+ new Composite().contains(
+ nonGeneric // should have type Composite => NonGeneric
+ )
+
+ new Composite().contains(
+ generic[Int] // should have type Composite => Generic[Int]
+ )
+}
diff --git a/test/files/scalacheck/avl.scala b/test/files/scalacheck/avl.scala
new file mode 100644
index 0000000000..51fb1fe8c3
--- /dev/null
+++ b/test/files/scalacheck/avl.scala
@@ -0,0 +1,114 @@
+import org.scalacheck.Gen
+import org.scalacheck.Prop.forAll
+import org.scalacheck.Properties
+
+import util.logging.ConsoleLogger
+
+package scala.collection.mutable {
+
+ /**
+ * Property of an AVL Tree : Any node of the tree has a balance value beetween in [-1; 1]
+ */
+ abstract class AVLTreeTest(name: String) extends Properties(name) with ConsoleLogger {
+
+ def `2^`(n: Int) = (1 to n).fold(1)((a, b) => b*2)
+
+ def capacityMax(depth: Int): Int = `2^`(depth+1) - 1
+
+ def minDepthForCapacity(x: Int): Int = {
+ var depth = 0
+ while(capacityMax(depth) < x)
+ depth += 1
+ depth
+ }
+
+ def numberOfElementsInLeftSubTree(n: Int): collection.immutable.IndexedSeq[Int] = {
+ val mid = n/2 + n%2
+ ((1 until mid)
+ .filter { i => math.abs(minDepthForCapacity(i) - minDepthForCapacity(n-i)) < 2 }
+ .flatMap { i => Seq(i, n-(i+1)) }).toIndexedSeq.distinct
+ }
+
+ def makeAllBalancedTree[A](elements: List[A]): List[AVLTree[A]] = elements match {
+ case Nil => Leaf::Nil
+ case first::Nil => Node(first, Leaf, Leaf)::Nil
+ case first::second::Nil => Node(second, Node(first, Leaf, Leaf), Leaf)::Node(first, Leaf, Node(second, Leaf, Leaf))::Nil
+ case first::second::third::Nil => Node(second, Node(first, Leaf, Leaf), Node(third, Leaf, Leaf))::Nil
+ case _ => {
+ val combinations = for {
+ left <- numberOfElementsInLeftSubTree(elements.size)
+ root = elements(left)
+ right = elements.size - (left + 1)
+ } yield (root, left, right)
+ (combinations.flatMap(triple => for {
+ l <- makeAllBalancedTree(elements.take(triple._2))
+ r <- makeAllBalancedTree(elements.takeRight(triple._3))
+ } yield Node(triple._1, l, r))).toList
+ }
+ }
+
+ def genInput: Gen[(Int, List[AVLTree[Int]])] = for {
+ size <- Gen.choose(20, 25)
+ elements <- Gen.listOfN(size, Gen.choose(0, 1000))
+ selected <- Gen.choose(0, 1000)
+ } yield {
+ // selected mustn't be in elements already
+ val list = makeAllBalancedTree(elements.sorted.distinct.map(_*2))
+ (selected*2+1, list)
+ }
+
+ def genInputDelete: Gen[(Int, List[AVLTree[Int]])] = for {
+ size <- Gen.choose(20, 25)
+ elements <- Gen.listOfN(size, Gen.choose(0, 1000))
+ e = elements.sorted.distinct
+ selected <- Gen.choose(0, e.size-1)
+ } yield {
+ // selected must be in elements already
+ val list = makeAllBalancedTree(e)
+ (e(selected), list)
+ }
+ }
+
+ trait AVLInvariants {
+ self: AVLTreeTest =>
+
+ def isBalanced[A](t: AVLTree[A]): Boolean = t match {
+ case node: Node[A] => math.abs(node.balance) < 2 && (List(node.left, node.right) forall isBalanced)
+ case Leaf => true
+ }
+
+ def setup(invariant: AVLTree[Int] => Boolean) = forAll(genInput) {
+ case (selected: Int, trees: List[AVLTree[Int]]) =>
+ trees.map(tree => invariant(tree)).fold(true)((a, b) => a && b)
+ }
+
+ property("Every tree is initially balanced.") = setup(isBalanced)
+ }
+
+ object TestInsert extends AVLTreeTest("Insert") with AVLInvariants {
+ import math.Ordering.Int
+ property("`insert` creates a new tree containing the given element. The tree remains balanced.") = forAll(genInput) {
+ case (selected: Int, trees: List[AVLTree[Int]]) =>
+ trees.map(tree => {
+ val modifiedTree = tree.insert(selected, Int)
+ modifiedTree.contains(selected, Int) && isBalanced(modifiedTree)
+ }).fold(true)((a, b) => a && b)
+ }
+ }
+
+ object TestRemove extends AVLTreeTest("Remove") with AVLInvariants {
+ import math.Ordering.Int
+ property("`remove` creates a new tree without the given element. The tree remains balanced.") = forAll(genInputDelete) {
+ case (selected: Int, trees: List[AVLTree[Int]]) =>
+ trees.map(tree => {
+ val modifiedTree = tree.remove(selected, Int)
+ tree.contains(selected, Int) && !modifiedTree.contains(selected, Int) && isBalanced(modifiedTree)
+ }).fold(true)((a, b) => a && b)
+ }
+ }
+}
+
+object Test extends Properties("AVL") {
+ include(scala.collection.mutable.TestInsert)
+ include(scala.collection.mutable.TestRemove)
+} \ No newline at end of file
generated by cgit v1.2.3 (git 2.39.1) at 2024-09-17 21:21:38 +0000