Merge branch 'develop'

11 files changed, 642 insertions, 137 deletions

diff --git a/src/compiler/scala/tools/nsc/typechecker/Typers.scala b/src/compiler/scala/tools/nsc/typechecker/Typers.scala
index 770b55d6ab..d3ff331f98 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