Merge branch 'master' into inline

7 files changed, 470 insertions, 0 deletions

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