Merge branch 'master' into issue/5846,4597,4027,4112

Conflicts:
	src/library/scala/collection/MapLike.scala
	src/library/scala/collection/SortedMapLike.scala

30 files changed, 442 insertions, 389 deletions

diff --git a/src/library/scala/collection/GenTraversableOnce.scala b/src/library/scala/collection/GenTraversableOnce.scala
index eadacd9209..e475865391 100644
--- a/src/library/scala/collection/GenTraversableOnce.scala
+++ b/src/library/scala/collection/GenTraversableOnce.scala
@@ -9,6 +9,8 @@
 package scala.collection
 
 import scala.reflect.ClassTag
+import scala.collection.generic.CanBuildFrom
+import scala.annotation.unchecked.{ uncheckedVariance => uV }
 
 /** A template trait for all traversable-once objects which may be
  *  traversed in parallel.
@@ -552,4 +554,21 @@ trait GenTraversableOnce[+A] extends Any {
    *               containing all key/value pairs of type `(T, U)` of this $coll.
    */
   def toMap[K, V](implicit ev: A <:< (K, V)): GenMap[K, V]
+
+  /** Converts this $coll to a Vector.
+   *  $willNotTerminateInf
+   *  @return a vector containing all elements of this $coll.
+   */
+  def toVector: Vector[A]
+
+  /** Converts this $coll into another by copying all elements.
+   *  @tparam Col  The collection type to build.
+   *  @return a new collection containing all elements of this $coll.
+   *  
+   *  @usecase def convertTo[Col[_]]: Col[A]
+   *    @inheritdoc
+   *    $willNotTerminateInf
+   *    @return a new collection containing all elements of this $coll.
+   */
+  def convertTo[Col[_]](implicit cbf: CanBuildFrom[Nothing, A, Col[A @uV]]): Col[A @uV]
 }
diff --git a/src/library/scala/collection/IterableViewLike.scala b/src/library/scala/collection/IterableViewLike.scala
index c842475590..e0c8b21d09 100644
--- a/src/library/scala/collection/IterableViewLike.scala
+++ b/src/library/scala/collection/IterableViewLike.scala
@@ -44,7 +44,7 @@ trait IterableViewLike[+A,
   }
 
   /** Explicit instantiation of the `Transformed` trait to reduce class file size in subclasses. */
-  private[collection] abstract class AbstractTransformed[+B] extends super[TraversableViewLike].Transformed[B] with Transformed[B]
+  private[collection] abstract class AbstractTransformed[+B] extends Iterable[B] with super[TraversableViewLike].Transformed[B] with Transformed[B]
 
   trait EmptyView extends Transformed[Nothing] with super[TraversableViewLike].EmptyView with super[GenIterableViewLike].EmptyView
 
diff --git a/src/library/scala/collection/Iterator.scala b/src/library/scala/collection/Iterator.scala
index b2bbc8d888..5f369de3b7 100644
--- a/src/library/scala/collection/Iterator.scala
+++ b/src/library/scala/collection/Iterator.scala
@@ -11,6 +11,8 @@ package scala.collection
 import mutable.ArrayBuffer
 import annotation.migration
 import immutable.Stream
+import scala.collection.generic.CanBuildFrom
+import scala.annotation.unchecked.{ uncheckedVariance => uV }
 
 /** The `Iterator` object provides various functions for creating specialized iterators.
  *
@@ -1138,6 +1140,7 @@ trait Iterator[+A] extends TraversableOnce[A] {
   def toStream: Stream[A] =
     if (self.hasNext) Stream.cons(self.next, self.toStream)
     else Stream.empty[A]
+  
 
   /** Converts this iterator to a string.
    *
diff --git a/src/library/scala/collection/SeqViewLike.scala b/src/library/scala/collection/SeqViewLike.scala
index f64045c9f6..73f5dda11c 100644
--- a/src/library/scala/collection/SeqViewLike.scala
+++ b/src/library/scala/collection/SeqViewLike.scala
@@ -40,7 +40,7 @@ trait SeqViewLike[+A,
   }
 
   /** Explicit instantiation of the `Transformed` trait to reduce class file size in subclasses. */
-  private[collection] abstract class AbstractTransformed[+B] extends super[IterableViewLike].AbstractTransformed[B] with Transformed[B]
+  private[collection] abstract class AbstractTransformed[+B] extends Seq[B] with super[IterableViewLike].Transformed[B] with Transformed[B]
 
   trait EmptyView extends Transformed[Nothing] with super[IterableViewLike].EmptyView with super[GenSeqViewLike].EmptyView
 
diff --git a/src/library/scala/collection/SortedMapLike.scala b/src/library/scala/collection/SortedMapLike.scala
index 1bef703053..f9e95230ea 100644
--- a/src/library/scala/collection/SortedMapLike.scala
+++ b/src/library/scala/collection/SortedMapLike.scala
@@ -83,6 +83,14 @@ self =>
     override def rangeImpl(from : Option[A], until : Option[A]): SortedMap[A, C] = self.rangeImpl(from, until).mapValues(f)
   }
   
+  /** Adds a number of elements provided by a traversable object
+   *  and returns a new collection with the added elements.
+   *
+   *  @param xs     the traversable object.
+   */
+  override def ++[B1 >: B](xs: GenTraversableOnce[(A, B1)]): SortedMap[A, B1] =
+    ((repr: SortedMap[A, B1]) /: xs.seq) (_ + _)
+  
 }
 
 
diff --git a/src/library/scala/collection/TraversableLike.scala b/src/library/scala/collection/TraversableLike.scala
index 3716a318d9..e5861f5760 100644
--- a/src/library/scala/collection/TraversableLike.scala
+++ b/src/library/scala/collection/TraversableLike.scala
@@ -616,6 +616,13 @@ trait TraversableLike[+A, +Repr] extends Any
   def toTraversable: Traversable[A] = thisCollection
   def toIterator: Iterator[A] = toStream.iterator
   def toStream: Stream[A] = toBuffer.toStream
+  // Override to provide size hint.
+  override def convertTo[Col[_]](implicit cbf: CanBuildFrom[Nothing, A, Col[A @uV]]): Col[A @uV] = {
+    val b = cbf()
+    b.sizeHint(this)
+    b ++= thisCollection
+    b.result
+  }
 
   /** Converts this $coll to a string.
    *
diff --git a/src/library/scala/collection/TraversableOnce.scala b/src/library/scala/collection/TraversableOnce.scala
index 386ce2d95a..8dc6184d88 100644
--- a/src/library/scala/collection/TraversableOnce.scala
+++ b/src/library/scala/collection/TraversableOnce.scala
@@ -9,6 +9,7 @@
 package scala.collection
 
 import mutable.{ Buffer, Builder, ListBuffer, ArrayBuffer }
+import generic.CanBuildFrom
 import annotation.unchecked.{ uncheckedVariance => uV }
 import language.{implicitConversions, higherKinds}
 import reflect.ClassTag
@@ -239,17 +240,25 @@ trait TraversableOnce[+A] extends Any with GenTraversableOnce[A] {
 
   def toTraversable: Traversable[A]
 
-  def toList: List[A] = (new ListBuffer[A] ++= seq).toList
+  def toList: List[A] = convertTo[List]
 
   def toIterable: Iterable[A] = toStream
 
   def toSeq: Seq[A] = toStream
 
-  def toIndexedSeq: immutable.IndexedSeq[A] = immutable.IndexedSeq() ++ seq
+  def toIndexedSeq: immutable.IndexedSeq[A] = convertTo[immutable.IndexedSeq]
 
-  def toBuffer[B >: A]: mutable.Buffer[B] = new ArrayBuffer[B] ++= seq
+  def toBuffer[B >: A]: mutable.Buffer[B] = convertTo[ArrayBuffer].asInstanceOf[mutable.Buffer[B]]
 
-  def toSet[B >: A]: immutable.Set[B] = immutable.Set() ++ seq
+  def toSet[B >: A]: immutable.Set[B] = convertTo[immutable.Set].asInstanceOf[immutable.Set[B]]
+
+  def toVector: Vector[A] = convertTo[Vector]
+
+  def convertTo[Col[_]](implicit cbf: CanBuildFrom[Nothing, A, Col[A @uV]]): Col[A @uV] = {
+    val b = cbf()
+    b ++= seq
+    b.result
+  }
 
   def toMap[T, U](implicit ev: A <:< (T, U)): immutable.Map[T, U] = {
     val b = immutable.Map.newBuilder[T, U]
diff --git a/src/library/scala/collection/TraversableViewLike.scala b/src/library/scala/collection/TraversableViewLike.scala
index eb2091a5f3..bf4f8205d6 100644
--- a/src/library/scala/collection/TraversableViewLike.scala
+++ b/src/library/scala/collection/TraversableViewLike.scala
@@ -117,7 +117,7 @@ trait TraversableViewLike[+A,
   }
 
   /** Explicit instantiation of the `Transformed` trait to reduce class file size in subclasses. */
-  private[collection] abstract class AbstractTransformed[+B] extends Transformed[B]
+  private[collection] abstract class AbstractTransformed[+B] extends Traversable[B] with Transformed[B]
 
   trait EmptyView extends Transformed[Nothing] with super.EmptyView
 
diff --git a/src/library/scala/collection/concurrent/TrieMap.scala b/src/library/scala/collection/concurrent/TrieMap.scala
index 08e9125bd8..2d8217551a 100644
--- a/src/library/scala/collection/concurrent/TrieMap.scala
+++ b/src/library/scala/collection/concurrent/TrieMap.scala
@@ -473,7 +473,11 @@ extends CNodeBase[K, V] {
   private def computeSize(ct: TrieMap[K, V]): Int = {
     var i = 0
     var sz = 0
-    val offset = math.abs(util.Random.nextInt()) % array.length
+    val offset =
+      if (array.length > 0)
+        //util.Random.nextInt(array.length) /* <-- benchmarks show that this causes observable contention */
+        scala.concurrent.forkjoin.ThreadLocalRandom.current.nextInt(0, array.length)
+      else 0
     while (i < array.length) {
       val pos = (i + offset) % array.length
       array(pos) match {
diff --git a/src/library/scala/collection/immutable/IntMap.scala b/src/library/scala/collection/immutable/IntMap.scala
index 039a57041c..e895c94599 100644
--- a/src/library/scala/collection/immutable/IntMap.scala
+++ b/src/library/scala/collection/immutable/IntMap.scala
@@ -18,17 +18,17 @@ import scala.collection.mutable.{ Builder, MapBuilder }
 private[immutable] object IntMapUtils extends BitOperations.Int {
   def branchMask(i: Int, j: Int) = highestOneBit(i ^ j)
 
-  def join[T](p1 : Int, t1 : IntMap[T], p2 : Int, t2 : IntMap[T]) : IntMap[T] = {
-    val m = branchMask(p1, p2);
-    val p = mask(p1, m);
+  def join[T](p1: Int, t1: IntMap[T], p2: Int, t2: IntMap[T]): IntMap[T] = {
+    val m = branchMask(p1, p2)
+    val p = mask(p1, m)
     if (zero(p1, m)) IntMap.Bin(p, m, t1, t2)
-    else IntMap.Bin(p, m, t2, t1);
+    else IntMap.Bin(p, m, t2, t1)
   }
 
-  def bin[T](prefix : Int, mask : Int, left : IntMap[T], right : IntMap[T]) : IntMap[T] = (left, right) match {
-    case (left, IntMap.Nil) => left;
-    case (IntMap.Nil, right) => right;
-    case (left, right) => IntMap.Bin(prefix, mask, left, right);
+  def bin[T](prefix: Int, mask: Int, left: IntMap[T], right: IntMap[T]): IntMap[T] = (left, right) match {
+    case (left, IntMap.Nil) => left
+    case (IntMap.Nil, right) => right
+    case (left, right) => IntMap.Bin(prefix, mask, left, right)
   }
 }
 
@@ -50,9 +50,9 @@ object IntMap {
   }
 
   def empty[T] : IntMap[T]  = IntMap.Nil;
-  def singleton[T](key : Int, value : T) : IntMap[T] = IntMap.Tip(key, value);
-  def apply[T](elems : (Int, T)*) : IntMap[T] =
-    elems.foldLeft(empty[T])((x, y) => x.updated(y._1, y._2));
+  def singleton[T](key: Int, value: T): IntMap[T] = IntMap.Tip(key, value);
+  def apply[T](elems: (Int, T)*): IntMap[T] =
+    elems.foldLeft(empty[T])((x, y) => x.updated(y._1, y._2))
 
   private[immutable] case object Nil extends IntMap[Nothing] {
     // Important! Without this equals method in place, an infinite
@@ -66,15 +66,15 @@ object IntMap {
     }
   }
 
-  private[immutable] case class Tip[+T](key : Int, value : T) extends IntMap[T]{
+  private[immutable] case class Tip[+T](key: Int, value: T) extends IntMap[T]{
     def withValue[S](s: S) =
-      if (s.asInstanceOf[AnyRef] eq value.asInstanceOf[AnyRef]) this.asInstanceOf[IntMap.Tip[S]];
-      else IntMap.Tip(key, s);
+      if (s.asInstanceOf[AnyRef] eq value.asInstanceOf[AnyRef]) this.asInstanceOf[IntMap.Tip[S]]
+      else IntMap.Tip(key, s)
   }
-  private[immutable] case class Bin[+T](prefix : Int, mask : Int, left : IntMap[T], right : IntMap[T]) extends IntMap[T]{
-    def bin[S](left : IntMap[S], right : IntMap[S]) : IntMap[S] = {
-      if ((this.left eq left) && (this.right eq right)) this.asInstanceOf[IntMap.Bin[S]];
-      else IntMap.Bin[S](prefix, mask, left, right);
+  private[immutable] case class Bin[+T](prefix: Int, mask: Int, left: IntMap[T], right: IntMap[T]) extends IntMap[T] {
+    def bin[S](left: IntMap[S], right: IntMap[S]): IntMap[S] = {
+      if ((this.left eq left) && (this.right eq right)) this.asInstanceOf[IntMap.Bin[S]]
+      else IntMap.Bin[S](prefix, mask, left, right)
     }
   }
 
@@ -83,60 +83,60 @@ object IntMap {
 import IntMap._
 
 // Iterator over a non-empty IntMap.
-private[immutable] abstract class IntMapIterator[V, T](it : IntMap[V]) extends AbstractIterator[T] {
+private[immutable] abstract class IntMapIterator[V, T](it: IntMap[V]) extends AbstractIterator[T] {
 
   // Basically this uses a simple stack to emulate conversion over the tree. However
   // because we know that Ints are at least 32 bits we can have at most 32 IntMap.Bins and
   // one IntMap.Tip sitting on the tree at any point. Therefore we know the maximum stack
   // depth is 33 and
-  var index = 0;
-  var buffer = new Array[AnyRef](33);
+  var index = 0
+  var buffer = new Array[AnyRef](33)
 
   def pop = {
-    index -= 1;
-    buffer(index).asInstanceOf[IntMap[V]];
+    index -= 1
+    buffer(index).asInstanceOf[IntMap[V]]
   }
 
-  def push(x : IntMap[V]) {
-    buffer(index) = x.asInstanceOf[AnyRef];
-    index += 1;
+  def push(x: IntMap[V]) {
+    buffer(index) = x.asInstanceOf[AnyRef]
+    index += 1
   }
-  push(it);
+  push(it)
 
   /**
    * What value do we assign to a tip?
    */
-  def valueOf(tip : IntMap.Tip[V]) : T;
+  def valueOf(tip: IntMap.Tip[V]): T
 
-  def hasNext = index != 0;
-  final def next : T =
+  def hasNext = index != 0
+  final def next: T =
     pop match {
       case IntMap.Bin(_,_, t@IntMap.Tip(_, _), right) => {
-        push(right);
-        valueOf(t);
+        push(right)
+        valueOf(t)
       }
       case IntMap.Bin(_, _, left, right) => {
-        push(right);
-        push(left);
-        next;
+        push(right)
+        push(left)
+        next
       }
-      case t@IntMap.Tip(_, _) => valueOf(t);
+      case t@IntMap.Tip(_, _) => valueOf(t)
       // This should never happen. We don't allow IntMap.Nil in subtrees of the IntMap
       // and don't return an IntMapIterator for IntMap.Nil.
-      case IntMap.Nil => sys.error("Empty maps not allowed as subtrees");
+      case IntMap.Nil => sys.error("Empty maps not allowed as subtrees")
     }
 }
 
-private[immutable] class IntMapEntryIterator[V](it : IntMap[V]) extends IntMapIterator[V, (Int, V)](it){
-  def valueOf(tip : IntMap.Tip[V]) = (tip.key, tip.value);
+private[immutable] class IntMapEntryIterator[V](it: IntMap[V]) extends IntMapIterator[V, (Int, V)](it) {
+  def valueOf(tip: IntMap.Tip[V]) = (tip.key, tip.value)
 }
 
-private[immutable] class IntMapValueIterator[V](it : IntMap[V]) extends IntMapIterator[V, V](it){
-  def valueOf(tip : IntMap.Tip[V]) = tip.value
+private[immutable] class IntMapValueIterator[V](it: IntMap[V]) extends IntMapIterator[V, V](it) {
+  def valueOf(tip: IntMap.Tip[V]) = tip.value
 }
 
-private[immutable] class IntMapKeyIterator[V](it : IntMap[V]) extends IntMapIterator[V, Int](it){
-  def valueOf(tip : IntMap.Tip[V]) = tip.key
+private[immutable] class IntMapKeyIterator[V](it: IntMap[V]) extends IntMapIterator[V, Int](it) {
+  def valueOf(tip: IntMap.Tip[V]) = tip.key
 }
 
 import IntMap._
@@ -145,7 +145,7 @@ import IntMap._
  *  <a href="http://citeseer.ist.psu.edu/okasaki98fast.html">Fast Mergeable Integer Maps</a>
  *  by Okasaki and Gill. Essentially a trie based on binary digits of the integers.
  *
- *  Note: This class is as of 2.8 largely superseded by HashMap.
+ *  '''Note:''' This class is as of 2.8 largely superseded by HashMap.
  *
  *  @tparam T    type of the values associated with integer keys.
  *
@@ -155,17 +155,16 @@ import IntMap._
  *  @define mayNotTerminateInf
  *  @define willNotTerminateInf
  */
-sealed abstract class IntMap[+T]
-extends AbstractMap[Int, T]
+sealed abstract class IntMap[+T] extends AbstractMap[Int, T]
    with Map[Int, T]
    with MapLike[Int, T, IntMap[T]] {
 
-  override def empty: IntMap[T] = IntMap.Nil;
+  override def empty: IntMap[T] = IntMap.Nil
 
   override def toList = {
-    val buffer = new scala.collection.mutable.ListBuffer[(Int, T)];
-    foreach(buffer += _);
-    buffer.toList;
+    val buffer = new scala.collection.mutable.ListBuffer[(Int, T)]
+    foreach(buffer += _)
+    buffer.toList
   }
 
   /**
@@ -173,109 +172,112 @@ extends AbstractMap[Int, T]
    *
    * @return an iterator over pairs of integer keys and corresponding values.
    */
-  def iterator : Iterator[(Int, T)] = this match {
-    case IntMap.Nil => Iterator.empty;
-    case _ => new IntMapEntryIterator(this);
+  def iterator: Iterator[(Int, T)] = this match {
+    case IntMap.Nil => Iterator.empty
+    case _ => new IntMapEntryIterator(this)
   }
 
   /**
    * Loops over the key, value pairs of the map in unsigned order of the keys.
    */
-  override final def foreach[U](f : ((Int, T)) =>  U) : Unit = this match {
-    case IntMap.Bin(_, _, left, right) => {left.foreach(f); right.foreach(f); }
-    case IntMap.Tip(key, value) => f((key, value));
-    case IntMap.Nil => {};
+  override final def foreach[U](f: ((Int, T)) =>  U): Unit = this match {
+    case IntMap.Bin(_, _, left, right) => { left.foreach(f); right.foreach(f) }
+    case IntMap.Tip(key, value) => f((key, value))
+    case IntMap.Nil =>
   }
 
-  override def keysIterator : Iterator[Int] = this match {
-    case IntMap.Nil => Iterator.empty;
-    case _ => new IntMapKeyIterator(this);
+  override def keysIterator: Iterator[Int] = this match {
+    case IntMap.Nil => Iterator.empty
+    case _ => new IntMapKeyIterator(this)
   }
 
   /**
-   * Loop over the keys of the map. The same as keys.foreach(f), but may
+   * Loop over the keys of the map. The same as `keys.foreach(f)`, but may
    * be more efficient.
    *
    * @param f The loop body
    */
-  final def foreachKey(f : Int => Unit) : Unit = this match {
-    case IntMap.Bin(_, _, left, right) => {left.foreachKey(f); right.foreachKey(f); }
-    case IntMap.Tip(key, _) => f(key);
-    case IntMap.Nil => {}
+  final def foreachKey(f: Int => Unit): Unit = this match {
+    case IntMap.Bin(_, _, left, right) => { left.foreachKey(f); right.foreachKey(f) }
+    case IntMap.Tip(key, _) => f(key)
+    case IntMap.Nil =>
   }
 
-  override def valuesIterator : Iterator[T] = this match {
-    case IntMap.Nil => Iterator.empty;
-    case _ => new IntMapValueIterator(this);
+  override def valuesIterator: Iterator[T] = this match {
+    case IntMap.Nil => Iterator.empty
+    case _ => new IntMapValueIterator(this)
   }
 
   /**
-   * Loop over the keys of the map. The same as keys.foreach(f), but may
+   * Loop over the keys of the map. The same as `keys.foreach(f)`, but may
    * be more efficient.
    *
    * @param f The loop body
    */
-  final def foreachValue(f : T => Unit) : Unit = this match {
-    case IntMap.Bin(_, _, left, right) => {left.foreachValue(f); right.foreachValue(f); }
-    case IntMap.Tip(_, value) => f(value);
-    case IntMap.Nil => {};
+  final def foreachValue(f: T => Unit): Unit = this match {
+    case IntMap.Bin(_, _, left, right) => { left.foreachValue(f); right.foreachValue(f) }
+    case IntMap.Tip(_, value) => f(value)
+    case IntMap.Nil =>
   }
 
   override def stringPrefix = "IntMap"
 
-  override def isEmpty = this == IntMap.Nil;
+  override def isEmpty = this == IntMap.Nil
 
-  override def filter(f : ((Int, T)) => Boolean) : IntMap[T] = this match {
+  override def filter(f: ((Int, T)) => Boolean): IntMap[T] = this match {
     case IntMap.Bin(prefix, mask, left, right) => {
-      val (newleft, newright) = (left.filter(f), right.filter(f));
-      if ((left eq newleft) && (right eq newright)) this;
-      else bin(prefix, mask, newleft, newright);
+      val (newleft, newright) = (left.filter(f), right.filter(f))
+      if ((left eq newleft) && (right eq newright)) this
+      else bin(prefix, mask, newleft, newright)
     }
     case IntMap.Tip(key, value) =>
       if (f((key, value))) this
-      else IntMap.Nil;
-    case IntMap.Nil => IntMap.Nil;
+      else IntMap.Nil
+    case IntMap.Nil => IntMap.Nil
   }
 
-  def transform[S](f : (Int, T) => S) : IntMap[S] = this match {
-    case b@IntMap.Bin(prefix, mask, left, right) => b.bin(left.transform(f), right.transform(f));
-    case t@IntMap.Tip(key, value) => t.withValue(f(key, value));
-    case IntMap.Nil => IntMap.Nil;
+  def transform[S](f: (Int, T) => S): IntMap[S] = this match {
+    case b@IntMap.Bin(prefix, mask, left, right) => b.bin(left.transform(f), right.transform(f))
+    case t@IntMap.Tip(key, value) => t.withValue(f(key, value))
+    case IntMap.Nil => IntMap.Nil
   }
 
-  final override def size : Int = this match {
-    case IntMap.Nil => 0;
-    case IntMap.Tip(_, _) => 1;
-    case IntMap.Bin(_, _, left, right) => left.size + right.size;
+  final override def size: Int = this match {
+    case IntMap.Nil => 0
+    case IntMap.Tip(_, _) => 1
+    case IntMap.Bin(_, _, left, right) => left.size + right.size
   }
 
-  final def get(key : Int) : Option[T] = this match {
-    case IntMap.Bin(prefix, mask, left, right) => if (zero(key, mask)) left.get(key) else right.get(key);
-    case IntMap.Tip(key2, value) => if (key == key2) Some(value) else None;
-    case IntMap.Nil => None;
+  final def get(key: Int): Option[T] = this match {
+    case IntMap.Bin(prefix, mask, left, right) => if (zero(key, mask)) left.get(key) else right.get(key)
+    case IntMap.Tip(key2, value) => if (key == key2) Some(value) else None
+    case IntMap.Nil => None
   }
 
-  final override def getOrElse[S >: T](key : Int, default : =>S) : S = this match {
-    case IntMap.Nil => default;
-    case IntMap.Tip(key2, value) => if (key == key2) value else default;
-    case IntMap.Bin(prefix, mask, left, right) => if (zero(key, mask)) left.getOrElse(key, default) else right.getOrElse(key, default);
+  final override def getOrElse[S >: T](key: Int, default: => S): S = this match {
+    case IntMap.Nil => default
+    case IntMap.Tip(key2, value) => if (key == key2) value else default
+    case IntMap.Bin(prefix, mask, left, right) =>
+      if (zero(key, mask)) left.getOrElse(key, default) else right.getOrElse(key, default)
   }
 
-  final override def apply(key : Int) : T = this match {
-    case IntMap.Bin(prefix, mask, left, right) => if (zero(key, mask)) left(key) else right(key);
-    case IntMap.Tip(key2, value) => if (key == key2) value else sys.error("Key not found");
-    case IntMap.Nil => sys.error("key not found");
+  final override def apply(key: Int): T = this match {
+    case IntMap.Bin(prefix, mask, left, right) => if (zero(key, mask)) left(key) else right(key)
+    case IntMap.Tip(key2, value) => if (key == key2) value else sys.error("Key not found")
+    case IntMap.Nil => sys.error("key not found")
   }
 
   def + [S >: T] (kv: (Int, S)): IntMap[S] = updated(kv._1, kv._2)
 
-  override def updated[S >: T](key : Int, value : S) : IntMap[S] = this match {
-    case IntMap.Bin(prefix, mask, left, right) => if (!hasMatch(key, prefix, mask)) join(key, IntMap.Tip(key, value), prefix, this);
-                                          else if (zero(key, mask)) IntMap.Bin(prefix, mask, left.updated(key, value), right)
-                                          else IntMap.Bin(prefix, mask, left, right.updated(key, value));
-    case IntMap.Tip(key2, value2) => if (key == key2) IntMap.Tip(key, value);
-                             else join(key, IntMap.Tip(key, value), key2, this);
-    case IntMap.Nil => IntMap.Tip(key, value);
+  override def updated[S >: T](key: Int, value: S): IntMap[S] = this match {
+    case IntMap.Bin(prefix, mask, left, right) =>
+      if (!hasMatch(key, prefix, mask)) join(key, IntMap.Tip(key, value), prefix, this)
+      else if (zero(key, mask)) IntMap.Bin(prefix, mask, left.updated(key, value), right)
+      else IntMap.Bin(prefix, mask, left, right.updated(key, value))
+    case IntMap.Tip(key2, value2) =>
+      if (key == key2) IntMap.Tip(key, value)
+      else join(key, IntMap.Tip(key, value), key2, this)
+    case IntMap.Nil => IntMap.Tip(key, value)
   }
 
   /**
@@ -284,7 +286,7 @@ extends AbstractMap[Int, T]
    * Equivalent to:
    * {{{
    *   this.get(key) match {
-   *     case None => this.update(key, value);
+   *     case None => this.update(key, value)
    *     case Some(oldvalue) => this.update(key, f(oldvalue, value)
    *   }
    * }}}
@@ -295,24 +297,26 @@ extends AbstractMap[Int, T]
    * @param f      The function used to resolve conflicts.
    * @return       The updated map.
    */
-  def updateWith[S >: T](key : Int, value : S, f : (T, S) => S) : IntMap[S] = this match {
-    case IntMap.Bin(prefix, mask, left, right) => if (!hasMatch(key, prefix, mask)) join(key, IntMap.Tip(key, value), prefix, this);
-                                          else if (zero(key, mask)) IntMap.Bin(prefix, mask, left.updateWith(key, value, f), right)
-                                          else IntMap.Bin(prefix, mask, left, right.updateWith(key, value, f));
-    case IntMap.Tip(key2, value2) => if (key == key2) IntMap.Tip(key, f(value2, value));
-                             else join(key, IntMap.Tip(key, value), key2, this);
-    case IntMap.Nil => IntMap.Tip(key, value);
+  def updateWith[S >: T](key: Int, value: S, f: (T, S) => S): IntMap[S] = this match {
+    case IntMap.Bin(prefix, mask, left, right) =>
+      if (!hasMatch(key, prefix, mask)) join(key, IntMap.Tip(key, value), prefix, this)
+      else if (zero(key, mask)) IntMap.Bin(prefix, mask, left.updateWith(key, value, f), right)
+      else IntMap.Bin(prefix, mask, left, right.updateWith(key, value, f))
+    case IntMap.Tip(key2, value2) =>
+      if (key == key2) IntMap.Tip(key, f(value2, value))
+      else join(key, IntMap.Tip(key, value), key2, this)
+    case IntMap.Nil => IntMap.Tip(key, value)
   }
 
-  def - (key : Int) : IntMap[T] = this match {
+  def - (key: Int): IntMap[T] = this match {
     case IntMap.Bin(prefix, mask, left, right) =>
-      if (!hasMatch(key, prefix, mask)) this;
-      else if (zero(key, mask)) bin(prefix, mask, left - key, right);
-      else bin(prefix, mask, left, right - key);
+      if (!hasMatch(key, prefix, mask)) this
+      else if (zero(key, mask)) bin(prefix, mask, left - key, right)
+      else bin(prefix, mask, left, right - key)
     case IntMap.Tip(key2, _) =>
-      if (key == key2) IntMap.Nil;
-      else this;
-    case IntMap.Nil => IntMap.Nil;
+      if (key == key2) IntMap.Nil
+      else this
+    case IntMap.Nil => IntMap.Nil
   }
 
   /**
@@ -324,7 +328,7 @@ extends AbstractMap[Int, T]
    * @param f   The transforming function.
    * @return    The modified map.
    */
-  def modifyOrRemove[S](f : (Int, T) => Option[S]) : IntMap[S] = this match {
+  def modifyOrRemove[S](f: (Int, T) => Option[S]): IntMap[S] = this match {
     case IntMap.Bin(prefix, mask, left, right) =>
       val newleft = left.modifyOrRemove(f)
       val newright = right.modifyOrRemove(f)
@@ -350,25 +354,25 @@ extends AbstractMap[Int, T]
    * @param f       The function used to resolve conflicts between two mappings.
    * @return        Union of `this` and `that`, with identical key conflicts resolved using the function `f`.
    */
-  def unionWith[S >: T](that : IntMap[S], f : (Int, S, S) => S) : IntMap[S] = (this, that) match{
+  def unionWith[S >: T](that: IntMap[S], f: (Int, S, S) => S): IntMap[S] = (this, that) match{
     case (IntMap.Bin(p1, m1, l1, r1), that@(IntMap.Bin(p2, m2, l2, r2))) =>
       if (shorter(m1, m2)) {
-        if (!hasMatch(p2, p1, m1)) join[S](p1, this, p2, that); // TODO: remove [S] when SI-5548 is fixed
-        else if (zero(p2, m1)) IntMap.Bin(p1, m1, l1.unionWith(that, f), r1);
-        else IntMap.Bin(p1, m1, l1, r1.unionWith(that, f));
+        if (!hasMatch(p2, p1, m1)) join[S](p1, this, p2, that) // TODO: remove [S] when SI-5548 is fixed
+        else if (zero(p2, m1)) IntMap.Bin(p1, m1, l1.unionWith(that, f), r1)
+        else IntMap.Bin(p1, m1, l1, r1.unionWith(that, f))
       } else if (shorter(m2, m1)){
-        if (!hasMatch(p1, p2, m2)) join[S](p1, this, p2, that); // TODO: remove [S] when SI-5548 is fixed
-        else if (zero(p1, m2)) IntMap.Bin(p2, m2, this.unionWith(l2, f), r2);
-        else IntMap.Bin(p2, m2, l2, this.unionWith(r2, f));
+        if (!hasMatch(p1, p2, m2)) join[S](p1, this, p2, that) // TODO: remove [S] when SI-5548 is fixed
+        else if (zero(p1, m2)) IntMap.Bin(p2, m2, this.unionWith(l2, f), r2)
+        else IntMap.Bin(p2, m2, l2, this.unionWith(r2, f))
       }
       else {
-        if (p1 == p2) IntMap.Bin(p1, m1, l1.unionWith(l2,f), r1.unionWith(r2, f));
-        else join[S](p1, this, p2, that); // TODO: remove [S] when SI-5548 is fixed
+        if (p1 == p2) IntMap.Bin(p1, m1, l1.unionWith(l2,f), r1.unionWith(r2, f))
+        else join[S](p1, this, p2, that) // TODO: remove [S] when SI-5548 is fixed
       }
-    case (IntMap.Tip(key, value), x) => x.updateWith[S](key, value, (x, y) => f(key, y, x));
-    case (x, IntMap.Tip(key, value)) => x.updateWith[S](key, value, (x, y) => f(key, x, y));
-    case (IntMap.Nil, x) => x;
-    case (x, IntMap.Nil) => x;
+    case (IntMap.Tip(key, value), x) => x.updateWith[S](key, value, (x, y) => f(key, y, x))
+    case (x, IntMap.Tip(key, value)) => x.updateWith[S](key, value, (x, y) => f(key, x, y))
+    case (IntMap.Nil, x) => x
+    case (x, IntMap.Nil) => x
   }
 
   /**
@@ -382,13 +386,13 @@ extends AbstractMap[Int, T]
    * @param f       The combining function.
    * @return        Intersection of `this` and `that`, with values for identical keys produced by function `f`.
    */
-  def intersectionWith[S, R](that : IntMap[S], f : (Int, T, S) => R) : IntMap[R] = (this, that) match {
+  def intersectionWith[S, R](that: IntMap[S], f: (Int, T, S) => R): IntMap[R] = (this, that) match {
     case (IntMap.Bin(p1, m1, l1, r1), that@IntMap.Bin(p2, m2, l2, r2)) =>
       if (shorter(m1, m2)) {
         if (!hasMatch(p2, p1, m1)) IntMap.Nil
         else if (zero(p2, m1)) l1.intersectionWith(that, f)
         else r1.intersectionWith(that, f)
-      } else if (m1 == m2) bin(p1, m1, l1.intersectionWith(l2, f), r1.intersectionWith(r2, f));
+      } else if (m1 == m2) bin(p1, m1, l1.intersectionWith(l2, f), r1.intersectionWith(r2, f))
         else {
         if (!hasMatch(p1, p2, m2)) IntMap.Nil
         else if (zero(p1, m2)) this.intersectionWith(l2, f)
@@ -413,15 +417,16 @@ extends AbstractMap[Int, T]
    * @param that    The map to intersect with.
    * @return        A map with all the keys both in `this` and `that`, mapped to corresponding values from `this`.
    */
-  def intersection[R](that : IntMap[R]) : IntMap[T] = this.intersectionWith(that, (key : Int, value : T, value2 : R) => value);
+  def intersection[R](that: IntMap[R]): IntMap[T] =
+    this.intersectionWith(that, (key: Int, value: T, value2: R) => value)
 
-  def ++[S >: T](that : IntMap[S]) =
+  def ++[S >: T](that: IntMap[S]) =
     this.unionWith[S](that, (key, x, y) => y)
 
   /**
    * The entry with the lowest key value considered in unsigned order.
    */
-  final def firstKey : Int = this match {
+  final def firstKey: Int = this match {
     case Bin(_, _, l, r) => l.firstKey
     case Tip(k, v) => k
     case IntMap.Nil => sys.error("Empty set")
@@ -430,7 +435,7 @@ extends AbstractMap[Int, T]
   /**
    * The entry with the highest key value considered in unsigned order.
    */
-  final def lastKey : Int = this match {
+  final def lastKey: Int = this match {
     case Bin(_, _, l, r) => r.lastKey
     case Tip(k, v) => k
     case IntMap.Nil => sys.error("Empty set")
diff --git a/src/library/scala/collection/immutable/LongMap.scala b/src/library/scala/collection/immutable/LongMap.scala
index 8a316f37de..002027b162 100644
--- a/src/library/scala/collection/immutable/LongMap.scala
+++ b/src/library/scala/collection/immutable/LongMap.scala
@@ -18,17 +18,17 @@ import scala.collection.mutable.{ Builder, MapBuilder }
 private[immutable] object LongMapUtils extends BitOperations.Long {
   def branchMask(i: Long, j: Long) = highestOneBit(i ^ j)
 
-  def join[T](p1 : Long, t1 : LongMap[T], p2 : Long, t2 : LongMap[T]) : LongMap[T] = {
-    val m = branchMask(p1, p2);
-    val p = mask(p1, m);
+  def join[T](p1: Long, t1: LongMap[T], p2: Long, t2: LongMap[T]): LongMap[T] = {
+    val m = branchMask(p1, p2)
+    val p = mask(p1, m)
     if (zero(p1, m)) LongMap.Bin(p, m, t1, t2)
-    else LongMap.Bin(p, m, t2, t1);
+    else LongMap.Bin(p, m, t2, t1)
   }
 
-  def bin[T](prefix : Long, mask : Long, left : LongMap[T], right : LongMap[T]) : LongMap[T] = (left, right) match {
-    case (left, LongMap.Nil) => left;
-    case (LongMap.Nil, right) => right;
-    case (left, right) => LongMap.Bin(prefix, mask, left, right);
+  def bin[T](prefix: Long, mask: Long, left: LongMap[T], right: LongMap[T]): LongMap[T] = (left, right) match {
+    case (left, LongMap.Nil) => left
+    case (LongMap.Nil, right) => right
+    case (left, right) => LongMap.Bin(prefix, mask, left, right)
   }
 }
 
@@ -49,29 +49,29 @@ object LongMap {
     def apply(): Builder[(Long, B), LongMap[B]] = new MapBuilder[Long, B, LongMap[B]](empty[B])
   }
 
-  def empty[T] : LongMap[T]  = LongMap.Nil;
-  def singleton[T](key : Long, value : T) : LongMap[T] = LongMap.Tip(key, value);
-  def apply[T](elems : (Long, T)*) : LongMap[T] =
-    elems.foldLeft(empty[T])((x, y) => x.updated(y._1, y._2));
+  def empty[T]: LongMap[T]  = LongMap.Nil
+  def singleton[T](key: Long, value: T): LongMap[T] = LongMap.Tip(key, value)
+  def apply[T](elems: (Long, T)*): LongMap[T] =
+    elems.foldLeft(empty[T])((x, y) => x.updated(y._1, y._2))
 
   private[immutable] case object Nil extends LongMap[Nothing] {
     // Important, don't remove this! See IntMap for explanation.
     override def equals(that : Any) = that match {
-      case (that : AnyRef) if (this eq that) => true;
-      case (that : LongMap[_]) => false; // The only empty LongMaps are eq Nil
-      case that => super.equals(that);
+      case (that: AnyRef) if (this eq that) => true
+      case (that: LongMap[_]) => false // The only empty LongMaps are eq Nil
+      case that => super.equals(that)
     }
-  };
+  }
 
-  private[immutable] case class Tip[+T](key : Long, value : T) extends LongMap[T]{
-    def withValue[S](s : S) =
-      if (s.asInstanceOf[AnyRef] eq value.asInstanceOf[AnyRef]) this.asInstanceOf[LongMap.Tip[S]];
-      else LongMap.Tip(key, s);
+  private[immutable] case class Tip[+T](key: Long, value: T) extends LongMap[T] {
+    def withValue[S](s: S) =
+      if (s.asInstanceOf[AnyRef] eq value.asInstanceOf[AnyRef]) this.asInstanceOf[LongMap.Tip[S]]
+      else LongMap.Tip(key, s)
   }
-  private[immutable] case class Bin[+T](prefix : Long, mask : Long, left : LongMap[T], right : LongMap[T]) extends LongMap[T]{
-    def bin[S](left : LongMap[S], right : LongMap[S]) : LongMap[S] = {
-      if ((this.left eq left) && (this.right eq right)) this.asInstanceOf[LongMap.Bin[S]];
-      else LongMap.Bin[S](prefix, mask, left, right);
+  private[immutable] case class Bin[+T](prefix: Long, mask: Long, left: LongMap[T], right: LongMap[T]) extends LongMap[T] {
+    def bin[S](left: LongMap[S], right: LongMap[S]): LongMap[S] = {
+      if ((this.left eq left) && (this.right eq right)) this.asInstanceOf[LongMap.Bin[S]]
+      else LongMap.Bin[S](prefix, mask, left, right)
     }
   }
 }
@@ -79,64 +79,62 @@ object LongMap {
 import LongMap._
 
 // Iterator over a non-empty LongMap.
-private[immutable] abstract class LongMapIterator[V, T](it : LongMap[V]) extends AbstractIterator[T] {
+private[immutable] abstract class LongMapIterator[V, T](it: LongMap[V]) extends AbstractIterator[T] {
 
   // Basically this uses a simple stack to emulate conversion over the tree. However
   // because we know that Longs are only 64 bits we can have at most 64 LongMap.Bins and
   // one LongMap.Tip sitting on the tree at any point. Therefore we know the maximum stack
   // depth is 65
-  var index = 0;
-  var buffer = new Array[AnyRef](65);
+  var index = 0
+  var buffer = new Array[AnyRef](65)
 
   def pop() = {
-    index -= 1;
-    buffer(index).asInstanceOf[LongMap[V]];
+    index -= 1
+    buffer(index).asInstanceOf[LongMap[V]]
   }
 
-  def push(x : LongMap[V]) {
-    buffer(index) = x.asInstanceOf[AnyRef];
-    index += 1;
+  def push(x: LongMap[V]) {
+    buffer(index) = x.asInstanceOf[AnyRef]
+    index += 1
   }
   push(it);
 
   /**
    * What value do we assign to a tip?
    */
-  def valueOf(tip : LongMap.Tip[V]) : T;
+  def valueOf(tip: LongMap.Tip[V]): T
 
-  def hasNext = index != 0;
-  final def next : T =
+  def hasNext = index != 0
+  final def next: T =
     pop() match {
       case LongMap.Bin(_,_, t@LongMap.Tip(_, _), right) => {
-        push(right);
-        valueOf(t);
+        push(right)
+        valueOf(t)
       }
       case LongMap.Bin(_, _, left, right) => {
-        push(right);
-        push(left);
-        next;
+        push(right)
+        push(left)
+        next
       }
-      case t@LongMap.Tip(_, _) => valueOf(t);
+      case t@LongMap.Tip(_, _) => valueOf(t)
       // This should never happen. We don't allow LongMap.Nil in subtrees of the LongMap
       // and don't return an LongMapIterator for LongMap.Nil.
-      case LongMap.Nil => sys.error("Empty maps not allowed as subtrees");
+      case LongMap.Nil => sys.error("Empty maps not allowed as subtrees")
     }
 }
 
-private[immutable] class LongMapEntryIterator[V](it : LongMap[V]) extends LongMapIterator[V, (Long, V)](it){
-  def valueOf(tip : LongMap.Tip[V]) = (tip.key, tip.value);
+private[immutable] class LongMapEntryIterator[V](it: LongMap[V]) extends LongMapIterator[V, (Long, V)](it){
+  def valueOf(tip: LongMap.Tip[V]) = (tip.key, tip.value)
 }
 
-private[immutable] class LongMapValueIterator[V](it : LongMap[V]) extends LongMapIterator[V, V](it){
-  def valueOf(tip : LongMap.Tip[V]) = tip.value;
+private[immutable] class LongMapValueIterator[V](it: LongMap[V]) extends LongMapIterator[V, V](it){
+  def valueOf(tip: LongMap.Tip[V]) = tip.value
 }
 
-private[immutable] class LongMapKeyIterator[V](it : LongMap[V]) extends LongMapIterator[V, Long](it){
-  def valueOf(tip : LongMap.Tip[V]) = tip.key;
+private[immutable] class LongMapKeyIterator[V](it: LongMap[V]) extends LongMapIterator[V, Long](it){
+  def valueOf(tip: LongMap.Tip[V]) = tip.key
 }
 
-import LongMap._;
-
 /**
  *  Specialised immutable map structure for long keys, based on
  *  <a href="http://citeseer.ist.psu.edu/okasaki98fast.html">Fast Mergeable Long Maps</a>
@@ -157,12 +155,12 @@ extends AbstractMap[Long, T]
    with Map[Long, T]
    with MapLike[Long, T, LongMap[T]] {
 
-  override def empty: LongMap[T] = LongMap.Nil;
+  override def empty: LongMap[T] = LongMap.Nil
 
   override def toList = {
-    val buffer = new scala.collection.mutable.ListBuffer[(Long, T)];
-    foreach(buffer += _);
-    buffer.toList;
+    val buffer = new scala.collection.mutable.ListBuffer[(Long, T)]
+    foreach(buffer += _)
+    buffer.toList
   }
 
   /**
@@ -171,22 +169,22 @@ extends AbstractMap[Long, T]
    * @return an iterator over pairs of long keys and corresponding values.
    */
   def iterator: Iterator[(Long, T)] = this match {
-    case LongMap.Nil => Iterator.empty;
-    case _ => new LongMapEntryIterator(this);
+    case LongMap.Nil => Iterator.empty
+    case _ => new LongMapEntryIterator(this)
   }
 
   /**
    * Loops over the key, value pairs of the map in unsigned order of the keys.
    */
-  override final def foreach[U](f : ((Long, T)) =>  U) : Unit = this match {
-    case LongMap.Bin(_, _, left, right) => {left.foreach(f); right.foreach(f); }
+  override final def foreach[U](f: ((Long, T)) =>  U): Unit = this match {
+    case LongMap.Bin(_, _, left, right) => { left.foreach(f); right.foreach(f) }
     case LongMap.Tip(key, value) => f((key, value));
-    case LongMap.Nil => {};
+    case LongMap.Nil =>
   }
 
-  override def keysIterator : Iterator[Long] = this match {
-    case LongMap.Nil => Iterator.empty;
-    case _ => new LongMapKeyIterator(this);
+  override def keysIterator: Iterator[Long] = this match {
+    case LongMap.Nil => Iterator.empty
+    case _ => new LongMapKeyIterator(this)
   }
 
   /**
@@ -195,15 +193,15 @@ extends AbstractMap[Long, T]
    *
    * @param f The loop body
    */
-  final def foreachKey(f : Long => Unit) : Unit = this match {
-    case LongMap.Bin(_, _, left, right) => {left.foreachKey(f); right.foreachKey(f); }
-    case LongMap.Tip(key, _) => f(key);
-    case LongMap.Nil => {}
+  final def foreachKey(f: Long => Unit): Unit = this match {
+    case LongMap.Bin(_, _, left, right) => { left.foreachKey(f); right.foreachKey(f) }
+    case LongMap.Tip(key, _) => f(key)
+    case LongMap.Nil =>
   }
 
-  override def valuesIterator : Iterator[T] = this match {
-    case LongMap.Nil => Iterator.empty;
-    case _ => new LongMapValueIterator(this);
+  override def valuesIterator: Iterator[T] = this match {
+    case LongMap.Nil => Iterator.empty
+    case _ => new LongMapValueIterator(this)
   }
 
   /**
@@ -212,67 +210,70 @@ extends AbstractMap[Long, T]
    *
    * @param f The loop body
    */
-  final def foreachValue(f : T => Unit) : Unit = this match {
-    case LongMap.Bin(_, _, left, right) => {left.foreachValue(f); right.foreachValue(f); }
-    case LongMap.Tip(_, value) => f(value);
-    case LongMap.Nil => {};
+  final def foreachValue(f: T => Unit): Unit = this match {
+    case LongMap.Bin(_, _, left, right) => { left.foreachValue(f); right.foreachValue(f) }
+    case LongMap.Tip(_, value) => f(value)
+    case LongMap.Nil =>
   }
 
   override def stringPrefix = "LongMap"
 
-  override def isEmpty = this == LongMap.Nil;
+  override def isEmpty = this == LongMap.Nil
 
-  override def filter(f : ((Long, T)) => Boolean) : LongMap[T] = this match {
+  override def filter(f: ((Long, T)) => Boolean): LongMap[T] = this match {
     case LongMap.Bin(prefix, mask, left, right) => {
-      val (newleft, newright) = (left.filter(f), right.filter(f));
-      if ((left eq newleft) && (right eq newright)) this;
-      else bin(prefix, mask, newleft, newright);
+      val (newleft, newright) = (left.filter(f), right.filter(f))
+      if ((left eq newleft) && (right eq newright)) this
+      else bin(prefix, mask, newleft, newright)
     }
     case LongMap.Tip(key, value) =>
       if (f((key, value))) this
-      else LongMap.Nil;
-    case LongMap.Nil => LongMap.Nil;
+      else LongMap.Nil
+    case LongMap.Nil => LongMap.Nil
   }
 
-  def transform[S](f : (Long, T) => S) : LongMap[S] = this match {
-    case b@LongMap.Bin(prefix, mask, left, right) => b.bin(left.transform(f), right.transform(f));
-    case t@LongMap.Tip(key, value) => t.withValue(f(key, value));
-    case LongMap.Nil => LongMap.Nil;
+  def transform[S](f: (Long, T) => S): LongMap[S] = this match {
+    case b@LongMap.Bin(prefix, mask, left, right) => b.bin(left.transform(f), right.transform(f))
+    case t@LongMap.Tip(key, value) => t.withValue(f(key, value))
+    case LongMap.Nil => LongMap.Nil
   }
 
-  final override def size : Int = this match {
-    case LongMap.Nil => 0;
-    case LongMap.Tip(_, _) => 1;
-    case LongMap.Bin(_, _, left, right) => left.size + right.size;
+  final override def size: Int = this match {
+    case LongMap.Nil => 0
+    case LongMap.Tip(_, _) => 1
+    case LongMap.Bin(_, _, left, right) => left.size + right.size
   }
 
-  final def get(key : Long) : Option[T] = this match {
-    case LongMap.Bin(prefix, mask, left, right) => if (zero(key, mask)) left.get(key) else right.get(key);
-    case LongMap.Tip(key2, value) => if (key == key2) Some(value) else None;
-    case LongMap.Nil => None;
+  final def get(key: Long): Option[T] = this match {
+    case LongMap.Bin(prefix, mask, left, right) => if (zero(key, mask)) left.get(key) else right.get(key)
+    case LongMap.Tip(key2, value) => if (key == key2) Some(value) else None
+    case LongMap.Nil => None
   }
 
-  final override def getOrElse[S >: T](key : Long, default : =>S) : S = this match {
-    case LongMap.Nil => default;
-    case LongMap.Tip(key2, value) => if (key == key2) value else default;
-    case LongMap.Bin(prefix, mask, left, right) => if (zero(key, mask)) left.getOrElse(key, default) else right.getOrElse(key, default);
+  final override def getOrElse[S >: T](key: Long, default: => S): S = this match {
+    case LongMap.Nil => default
+    case LongMap.Tip(key2, value) => if (key == key2) value else default
+    case LongMap.Bin(prefix, mask, left, right) =>
+      if (zero(key, mask)) left.getOrElse(key, default) else right.getOrElse(key, default)
   }
 
-  final override def apply(key : Long) : T = this match {
-    case LongMap.Bin(prefix, mask, left, right) => if (zero(key, mask)) left(key) else right(key);
-    case LongMap.Tip(key2, value) => if (key == key2) value else sys.error("Key not found");
-    case LongMap.Nil => sys.error("key not found");
+  final override def apply(key: Long): T = this match {
+    case LongMap.Bin(prefix, mask, left, right) => if (zero(key, mask)) left(key) else right(key)
+    case LongMap.Tip(key2, value) => if (key == key2) value else sys.error("Key not found")
+    case LongMap.Nil => sys.error("key not found")
   }
 
   def + [S >: T] (kv: (Long, S)): LongMap[S] = updated(kv._1, kv._2)
 
-  override def updated[S >: T](key : Long, value : S) : LongMap[S] = this match {
-    case LongMap.Bin(prefix, mask, left, right) => if (!hasMatch(key, prefix, mask)) join(key, LongMap.Tip(key, value), prefix, this);
-                                          else if (zero(key, mask)) LongMap.Bin(prefix, mask, left.updated(key, value), right)
-                                          else LongMap.Bin(prefix, mask, left, right.updated(key, value));
-    case LongMap.Tip(key2, value2) => if (key == key2) LongMap.Tip(key, value);
-                             else join(key, LongMap.Tip(key, value), key2, this);
-    case LongMap.Nil => LongMap.Tip(key, value);
+  override def updated[S >: T](key: Long, value: S): LongMap[S] = this match {
+    case LongMap.Bin(prefix, mask, left, right) =>
+      if (!hasMatch(key, prefix, mask)) join(key, LongMap.Tip(key, value), prefix, this)
+      else if (zero(key, mask)) LongMap.Bin(prefix, mask, left.updated(key, value), right)
+      else LongMap.Bin(prefix, mask, left, right.updated(key, value))
+    case LongMap.Tip(key2, value2) =>
+      if (key == key2) LongMap.Tip(key, value)
+      else join(key, LongMap.Tip(key, value), key2, this)
+    case LongMap.Nil => LongMap.Tip(key, value)
   }
 
   /**
@@ -281,7 +282,7 @@ extends AbstractMap[Long, T]
    * Equivalent to
    * {{{
    *   this.get(key) match {
-   *     case None => this.update(key, value);
+   *     case None => this.update(key, value)
    *     case Some(oldvalue) => this.update(key, f(oldvalue, value)
    *   }
    * }}}
@@ -292,24 +293,26 @@ extends AbstractMap[Long, T]
    * @param f      The function used to resolve conflicts.
    * @return       The updated map.
    */
-  def updateWith[S >: T](key : Long, value : S, f : (T, S) => S) : LongMap[S] = this match {
-    case LongMap.Bin(prefix, mask, left, right) => if (!hasMatch(key, prefix, mask)) join(key, LongMap.Tip(key, value), prefix, this);
-                                          else if (zero(key, mask)) LongMap.Bin(prefix, mask, left.updateWith(key, value, f), right)
-                                          else LongMap.Bin(prefix, mask, left, right.updateWith(key, value, f));
-    case LongMap.Tip(key2, value2) => if (key == key2) LongMap.Tip(key, f(value2, value));
-                             else join(key, LongMap.Tip(key, value), key2, this);
-    case LongMap.Nil => LongMap.Tip(key, value);
+  def updateWith[S >: T](key: Long, value: S, f: (T, S) => S): LongMap[S] = this match {
+    case LongMap.Bin(prefix, mask, left, right) =>
+      if (!hasMatch(key, prefix, mask)) join(key, LongMap.Tip(key, value), prefix, this)
+      else if (zero(key, mask)) LongMap.Bin(prefix, mask, left.updateWith(key, value, f), right)
+      else LongMap.Bin(prefix, mask, left, right.updateWith(key, value, f))
+    case LongMap.Tip(key2, value2) => 
+      if (key == key2) LongMap.Tip(key, f(value2, value))
+      else join(key, LongMap.Tip(key, value), key2, this)
+    case LongMap.Nil => LongMap.Tip(key, value)
   }
 
-  def -(key : Long) : LongMap[T] = this match {
+  def -(key: Long): LongMap[T] = this match {
     case LongMap.Bin(prefix, mask, left, right) =>
-      if (!hasMatch(key, prefix, mask)) this;
-      else if (zero(key, mask)) bin(prefix, mask, left - key, right);
-      else bin(prefix, mask, left, right - key);
+      if (!hasMatch(key, prefix, mask)) this
+      else if (zero(key, mask)) bin(prefix, mask, left - key, right)
+      else bin(prefix, mask, left, right - key)
     case LongMap.Tip(key2, _) =>
-      if (key == key2) LongMap.Nil;
-      else this;
-    case LongMap.Nil => LongMap.Nil;
+      if (key == key2) LongMap.Nil
+      else this
+    case LongMap.Nil => LongMap.Nil
   }
 
   /**
@@ -321,21 +324,21 @@ extends AbstractMap[Long, T]
    * @param f     The transforming function.
    * @return      The modified map.
    */
-  def modifyOrRemove[S](f : (Long, T) => Option[S]) : LongMap[S] = this match {
+  def modifyOrRemove[S](f: (Long, T) => Option[S]): LongMap[S] = this match {
       case LongMap.Bin(prefix, mask, left, right) => {
-        val newleft = left.modifyOrRemove(f);
-        val newright = right.modifyOrRemove(f);
-        if ((left eq newleft) && (right eq newright)) this.asInstanceOf[LongMap[S]];
+        val newleft = left.modifyOrRemove(f)
+        val newright = right.modifyOrRemove(f)
+        if ((left eq newleft) && (right eq newright)) this.asInstanceOf[LongMap[S]]
         else bin(prefix, mask, newleft, newright)
       }
     case LongMap.Tip(key, value) => f(key, value) match {
-      case None => LongMap.Nil;
+      case None => LongMap.Nil
       case Some(value2) =>
         //hack to preserve sharing
         if (value.asInstanceOf[AnyRef] eq value2.asInstanceOf[AnyRef]) this.asInstanceOf[LongMap[S]]
-        else LongMap.Tip(key, value2);
+        else LongMap.Tip(key, value2)
       }
-    case LongMap.Nil => LongMap.Nil;
+    case LongMap.Nil => LongMap.Nil
   }
 
   /**
@@ -346,25 +349,25 @@ extends AbstractMap[Long, T]
    * @param f       The function used to resolve conflicts between two mappings.
    * @return        Union of `this` and `that`, with identical key conflicts resolved using the function `f`.
    */
-  def unionWith[S >: T](that : LongMap[S], f : (Long, S, S) => S) : LongMap[S] = (this, that) match{
+  def unionWith[S >: T](that: LongMap[S], f: (Long, S, S) => S): LongMap[S] = (this, that) match{
     case (LongMap.Bin(p1, m1, l1, r1), that@(LongMap.Bin(p2, m2, l2, r2))) =>
       if (shorter(m1, m2)) {
-        if (!hasMatch(p2, p1, m1)) join[S](p1, this, p2, that); // TODO: remove [S] when SI-5548 is fixed
-        else if (zero(p2, m1)) LongMap.Bin(p1, m1, l1.unionWith(that, f), r1);
-        else LongMap.Bin(p1, m1, l1, r1.unionWith(that, f));
+        if (!hasMatch(p2, p1, m1)) join[S](p1, this, p2, that) // TODO: remove [S] when SI-5548 is fixed
+        else if (zero(p2, m1)) LongMap.Bin(p1, m1, l1.unionWith(that, f), r1)
+        else LongMap.Bin(p1, m1, l1, r1.unionWith(that, f))
       } else if (shorter(m2, m1)){
-        if (!hasMatch(p1, p2, m2)) join[S](p1, this, p2, that); // TODO: remove [S] when SI-5548 is fixed
-        else if (zero(p1, m2)) LongMap.Bin(p2, m2, this.unionWith(l2, f), r2);
-        else LongMap.Bin(p2, m2, l2, this.unionWith(r2, f));
+        if (!hasMatch(p1, p2, m2)) join[S](p1, this, p2, that) // TODO: remove [S] when SI-5548 is fixed
+        else if (zero(p1, m2)) LongMap.Bin(p2, m2, this.unionWith(l2, f), r2)
+        else LongMap.Bin(p2, m2, l2, this.unionWith(r2, f))
       }
       else {
-        if (p1 == p2) LongMap.Bin(p1, m1, l1.unionWith(l2,f), r1.unionWith(r2, f));
-        else join[S](p1, this, p2, that); // TODO: remove [S] when SI-5548 is fixed
+        if (p1 == p2) LongMap.Bin(p1, m1, l1.unionWith(l2,f), r1.unionWith(r2, f))
+        else join[S](p1, this, p2, that) // TODO: remove [S] when SI-5548 is fixed
       }
-    case (LongMap.Tip(key, value), x) => x.updateWith[S](key, value, (x, y) => f(key, y, x)); // TODO: remove [S] when SI-5548 is fixed
-    case (x, LongMap.Tip(key, value)) => x.updateWith[S](key, value, (x, y) => f(key, x, y));
-    case (LongMap.Nil, x) => x;
-    case (x, LongMap.Nil) => x;
+    case (LongMap.Tip(key, value), x) => x.updateWith[S](key, value, (x, y) => f(key, y, x)) // TODO: remove [S] when SI-5548 is fixed
+    case (x, LongMap.Tip(key, value)) => x.updateWith[S](key, value, (x, y) => f(key, x, y))
+    case (LongMap.Nil, x) => x
+    case (x, LongMap.Nil) => x
   }
 
   /**
@@ -378,27 +381,27 @@ extends AbstractMap[Long, T]
    * @param f       The combining function.
    * @return        Intersection of `this` and `that`, with values for identical keys produced by function `f`.
    */
-  def intersectionWith[S, R](that : LongMap[S], f : (Long, T, S) => R) : LongMap[R] = (this, that) match {
+  def intersectionWith[S, R](that: LongMap[S], f: (Long, T, S) => R): LongMap[R] = (this, that) match {
     case (LongMap.Bin(p1, m1, l1, r1), that@LongMap.Bin(p2, m2, l2, r2)) =>
       if (shorter(m1, m2)) {
-        if (!hasMatch(p2, p1, m1)) LongMap.Nil;
-        else if (zero(p2, m1)) l1.intersectionWith(that, f);
-        else r1.intersectionWith(that, f);
-      } else if (m1 == m2) bin(p1, m1, l1.intersectionWith(l2, f), r1.intersectionWith(r2, f));
+        if (!hasMatch(p2, p1, m1)) LongMap.Nil
+        else if (zero(p2, m1)) l1.intersectionWith(that, f)
+        else r1.intersectionWith(that, f)
+      } else if (m1 == m2) bin(p1, m1, l1.intersectionWith(l2, f), r1.intersectionWith(r2, f))
         else {
-        if (!hasMatch(p1, p2, m2)) LongMap.Nil;
-        else if (zero(p1, m2)) this.intersectionWith(l2, f);
-        else this.intersectionWith(r2, f);
+        if (!hasMatch(p1, p2, m2)) LongMap.Nil
+        else if (zero(p1, m2)) this.intersectionWith(l2, f)
+        else this.intersectionWith(r2, f)
       }
     case (LongMap.Tip(key, value), that) => that.get(key) match {
-      case None => LongMap.Nil;
-      case Some(value2) => LongMap.Tip(key, f(key, value, value2));
+      case None => LongMap.Nil
+      case Some(value2) => LongMap.Tip(key, f(key, value, value2))
     }
     case (_, LongMap.Tip(key, value)) => this.get(key) match {
-      case None => LongMap.Nil;
-      case Some(value2) => LongMap.Tip(key, f(key, value2, value));
+      case None => LongMap.Nil
+      case Some(value2) => LongMap.Tip(key, f(key, value2, value))
     }
-    case (_, _) => LongMap.Nil;
+    case (_, _) => LongMap.Nil
   }
 
   /**
@@ -409,9 +412,10 @@ extends AbstractMap[Long, T]
    * @param that    The map to intersect with.
    * @return        A map with all the keys both in `this` and `that`, mapped to corresponding values from `this`.
    */
-  def intersection[R](that : LongMap[R]) : LongMap[T] = this.intersectionWith(that, (key : Long, value : T, value2 : R) => value);
+  def intersection[R](that: LongMap[R]): LongMap[T] =
+    this.intersectionWith(that, (key: Long, value: T, value2: R) => value)
 
-  def ++[S >: T](that : LongMap[S]) =
+  def ++[S >: T](that: LongMap[S]) =
     this.unionWith[S](that, (key, x, y) => y)
 }
 
diff --git a/src/library/scala/collection/immutable/RedBlackTree.scala b/src/library/scala/collection/immutable/RedBlackTree.scala
index 0f28c4997b..4b573511d1 100644
--- a/src/library/scala/collection/immutable/RedBlackTree.scala
+++ b/src/library/scala/collection/immutable/RedBlackTree.scala
@@ -43,7 +43,7 @@ object RedBlackTree {
   }
 
   def count(tree: Tree[_, _]) = if (tree eq null) 0 else tree.count
-  def update[A, B, B1 >: B](tree: Tree[A, B], k: A, v: B1)(implicit ordering: Ordering[A]): Tree[A, B1] = blacken(upd(tree, k, v))
+  def update[A, B, B1 >: B](tree: Tree[A, B], k: A, v: B1, overwrite: Boolean)(implicit ordering: Ordering[A]): Tree[A, B1] = blacken(upd(tree, k, v, overwrite))
   def delete[A, B](tree: Tree[A, B], k: A)(implicit ordering: Ordering[A]): Tree[A, B] = blacken(del(tree, k))
   def rangeImpl[A: Ordering, B](tree: Tree[A, B], from: Option[A], until: Option[A]): Tree[A, B] = (from, until) match {
     case (Some(from), Some(until)) => this.range(tree, from, until)
@@ -122,17 +122,18 @@ object RedBlackTree {
     else
       mkTree(isBlack, x, xv, a, r)
   }
-  private[this] def upd[A, B, B1 >: B](tree: Tree[A, B], k: A, v: B1)(implicit ordering: Ordering[A]): Tree[A, B1] = if (tree eq null) {
+  private[this] def upd[A, B, B1 >: B](tree: Tree[A, B], k: A, v: B1, overwrite: Boolean)(implicit ordering: Ordering[A]): Tree[A, B1] = if (tree eq null) {
     RedTree(k, v, null, null)
   } else {
     val cmp = ordering.compare(k, tree.key)
-    if (cmp < 0) balanceLeft(isBlackTree(tree), tree.key, tree.value, upd(tree.left, k, v), tree.right)
-    else if (cmp > 0) balanceRight(isBlackTree(tree), tree.key, tree.value, tree.left, upd(tree.right, k, v))
-    else mkTree(isBlackTree(tree), k, v, tree.left, tree.right)
+    if (cmp < 0) balanceLeft(isBlackTree(tree), tree.key, tree.value, upd(tree.left, k, v, overwrite), tree.right)
+    else if (cmp > 0) balanceRight(isBlackTree(tree), tree.key, tree.value, tree.left, upd(tree.right, k, v, overwrite))
+    else if (overwrite || k != tree.key) mkTree(isBlackTree(tree), k, v, tree.left, tree.right)
+    else tree
   }
 
-  // Based on Stefan Kahrs' Haskell version of Okasaki's Red&Black Trees
-  // http://www.cse.unsw.edu.au/~dons/data/RedBlackTree.html
+  /* Based on Stefan Kahrs' Haskell version of Okasaki's Red&Black Trees
+   * http://www.cse.unsw.edu.au/~dons/data/RedBlackTree.html */
   private[this] def del[A, B](tree: Tree[A, B], k: A)(implicit ordering: Ordering[A]): Tree[A, B] = if (tree eq null) null else {
     def balance(x: A, xv: B, tl: Tree[A, B], tr: Tree[A, B]) = if (isRedTree(tl)) {
       if (isRedTree(tr)) {
@@ -216,7 +217,7 @@ object RedBlackTree {
     if (ordering.lt(tree.key, from)) return doFrom(tree.right, from)
     val newLeft = doFrom(tree.left, from)
     if (newLeft eq tree.left) tree
-    else if (newLeft eq null) upd(tree.right, tree.key, tree.value)
+    else if (newLeft eq null) upd(tree.right, tree.key, tree.value, false)
     else rebalance(tree, newLeft, tree.right)
   }
   private[this] def doTo[A, B](tree: Tree[A, B], to: A)(implicit ordering: Ordering[A]): Tree[A, B] = {
@@ -224,7 +225,7 @@ object RedBlackTree {
     if (ordering.lt(to, tree.key)) return doTo(tree.left, to)
     val newRight = doTo(tree.right, to)
     if (newRight eq tree.right) tree
-    else if (newRight eq null) upd(tree.left, tree.key, tree.value)
+    else if (newRight eq null) upd(tree.left, tree.key, tree.value, false)
     else rebalance(tree, tree.left, newRight)
   }
   private[this] def doUntil[A, B](tree: Tree[A, B], until: A)(implicit ordering: Ordering[A]): Tree[A, B] = {
@@ -232,7 +233,7 @@ object RedBlackTree {
     if (ordering.lteq(until, tree.key)) return doUntil(tree.left, until)
     val newRight = doUntil(tree.right, until)
     if (newRight eq tree.right) tree
-    else if (newRight eq null) upd(tree.left, tree.key, tree.value)
+    else if (newRight eq null) upd(tree.left, tree.key, tree.value, false)
     else rebalance(tree, tree.left, newRight)
   }
   private[this] def doRange[A, B](tree: Tree[A, B], from: A, until: A)(implicit ordering: Ordering[A]): Tree[A, B] = {
@@ -242,8 +243,8 @@ object RedBlackTree {
     val newLeft = doFrom(tree.left, from)
     val newRight = doUntil(tree.right, until)
     if ((newLeft eq tree.left) && (newRight eq tree.right)) tree
-    else if (newLeft eq null) upd(newRight, tree.key, tree.value);
-    else if (newRight eq null) upd(newLeft, tree.key, tree.value);
+    else if (newLeft eq null) upd(newRight, tree.key, tree.value, false);
+    else if (newRight eq null) upd(newLeft, tree.key, tree.value, false);
     else rebalance(tree, newLeft, newRight)
   }
 
@@ -254,7 +255,7 @@ object RedBlackTree {
     if (n > count) return doDrop(tree.right, n - count - 1)
     val newLeft = doDrop(tree.left, n)
     if (newLeft eq tree.left) tree
-    else if (newLeft eq null) upd(tree.right, tree.key, tree.value)
+    else if (newLeft eq null) upd(tree.right, tree.key, tree.value, false)
     else rebalance(tree, newLeft, tree.right)
   }
   private[this] def doTake[A: Ordering, B](tree: Tree[A, B], n: Int): Tree[A, B] = {
@@ -264,7 +265,7 @@ object RedBlackTree {
     if (n <= count) return doTake(tree.left, n)
     val newRight = doTake(tree.right, n - count - 1)
     if (newRight eq tree.right) tree
-    else if (newRight eq null) upd(tree.left, tree.key, tree.value)
+    else if (newRight eq null) upd(tree.left, tree.key, tree.value, false)
     else rebalance(tree, tree.left, newRight)
   }
   private[this] def doSlice[A: Ordering, B](tree: Tree[A, B], from: Int, until: Int): Tree[A, B] = {
@@ -275,8 +276,8 @@ object RedBlackTree {
     val newLeft = doDrop(tree.left, from)
     val newRight = doTake(tree.right, until - count - 1)
     if ((newLeft eq tree.left) && (newRight eq tree.right)) tree
-    else if (newLeft eq null) upd(newRight, tree.key, tree.value)
-    else if (newRight eq null) upd(newLeft, tree.key, tree.value)
+    else if (newLeft eq null) upd(newRight, tree.key, tree.value, false)
+    else if (newRight eq null) upd(newLeft, tree.key, tree.value, false)
     else rebalance(tree, newLeft, newRight)
   }
 
diff --git a/src/library/scala/collection/immutable/TreeMap.scala b/src/library/scala/collection/immutable/TreeMap.scala
index 4c1a5f2e03..51bc76efc3 100644
--- a/src/library/scala/collection/immutable/TreeMap.scala
+++ b/src/library/scala/collection/immutable/TreeMap.scala
@@ -131,7 +131,7 @@ class TreeMap[A, +B] private (tree: RB.Tree[A, B])(implicit val ordering: Orderi
    *  @param value   the value to be associated with `key`
    *  @return        a new $coll with the updated binding
    */
-  override def updated [B1 >: B](key: A, value: B1): TreeMap[A, B1] = new TreeMap(RB.update(tree, key, value))
+  override def updated [B1 >: B](key: A, value: B1): TreeMap[A, B1] = new TreeMap(RB.update(tree, key, value, true))
 
   /** Add a key/value pair to this map.
    *  @tparam   B1   type of the value of the new binding, a supertype of `B`
@@ -171,7 +171,7 @@ class TreeMap[A, +B] private (tree: RB.Tree[A, B])(implicit val ordering: Orderi
    */
   def insert [B1 >: B](key: A, value: B1): TreeMap[A, B1] = {
     assert(!RB.contains(tree, key))
-    new TreeMap(RB.update(tree, key, value))
+    new TreeMap(RB.update(tree, key, value, true))
   }
 
   def - (key:A): TreeMap[A, B] =
diff --git a/src/library/scala/collection/immutable/TreeSet.scala b/src/library/scala/collection/immutable/TreeSet.scala
index 882e828c5b..697da2bc4b 100644
--- a/src/library/scala/collection/immutable/TreeSet.scala
+++ b/src/library/scala/collection/immutable/TreeSet.scala
@@ -112,7 +112,7 @@ class TreeSet[A] private (tree: RB.Tree[A, Unit])(implicit val ordering: Orderin
    *  @param elem    a new element to add.
    *  @return        a new $coll containing `elem` and all the elements of this $coll.
    */
-  def + (elem: A): TreeSet[A] = newSet(RB.update(tree, elem, ()))
+  def + (elem: A): TreeSet[A] = newSet(RB.update(tree, elem, (), false))
 
   /** A new `TreeSet` with the entry added is returned,
    *  assuming that elem is <em>not</em> in the TreeSet.
@@ -122,7 +122,7 @@ class TreeSet[A] private (tree: RB.Tree[A, Unit])(implicit val ordering: Orderin
    */
   def insert(elem: A): TreeSet[A] = {
     assert(!RB.contains(tree, elem))
-    newSet(RB.update(tree, elem, ()))
+    newSet(RB.update(tree, elem, (), false))
   }
 
   /** Creates a new `TreeSet` with the entry removed.
diff --git a/src/library/scala/collection/immutable/Vector.scala b/src/library/scala/collection/immutable/Vector.scala
index 1395a8f52d..d100bf93df 100644
--- a/src/library/scala/collection/immutable/Vector.scala
+++ b/src/library/scala/collection/immutable/Vector.scala
@@ -77,6 +77,8 @@ override def companion: GenericCompanion[Vector] = Vector
 
   override def par = new ParVector(this)
 
+  override def toVector: Vector[A] = this
+
   override def lengthCompare(len: Int): Int = length - len
 
   private[collection] final def initIterator[B >: A](s: VectorIterator[B]) {
diff --git a/src/library/scala/collection/mutable/ArrayOps.scala b/src/library/scala/collection/mutable/ArrayOps.scala
index 01636eb54e..7a595f211d 100644
--- a/src/library/scala/collection/mutable/ArrayOps.scala
+++ b/src/library/scala/collection/mutable/ArrayOps.scala
@@ -64,7 +64,7 @@ abstract class ArrayOps[T] extends ArrayLike[T, Array[T]] with CustomParalleliza
    *  @param asTrav    A function that converts elements of this array to rows - arrays of type `U`.
    *  @return          An array obtained by concatenating rows of this array.
    */
-  def flatten[U, To](implicit asTrav: T => collection.Traversable[U], m: ClassTag[U]): Array[U] = {
+  def flatten[U](implicit asTrav: T => collection.Traversable[U], m: ClassTag[U]): Array[U] = {
     val b = Array.newBuilder[U]
     b.sizeHint(map{case is: collection.IndexedSeq[_] => is.size case _ => 0}.sum)
     for (xs <- this)
diff --git a/src/library/scala/collection/mutable/LinkedHashMap.scala b/src/library/scala/collection/mutable/LinkedHashMap.scala
index 4150cf9eba..5643e070f8 100644
--- a/src/library/scala/collection/mutable/LinkedHashMap.scala
+++ b/src/library/scala/collection/mutable/LinkedHashMap.scala
@@ -49,7 +49,8 @@ class LinkedHashMap[A, B] extends AbstractMap[A, B]
                              with Map[A, B]
                              with MapLike[A, B, LinkedHashMap[A, B]]
                              with HashTable[A, LinkedEntry[A, B]]
-                             with Serializable {
+                             with Serializable
+{
 
   override def empty = LinkedHashMap.empty[A, B]
   override def size = tableSize
@@ -107,7 +108,25 @@ class LinkedHashMap[A, B] extends AbstractMap[A, B]
       if (hasNext) { val res = (cur.key, cur.value); cur = cur.later; res }
       else Iterator.empty.next
   }
+  
+  protected class FilteredKeys(p: A => Boolean) extends super.FilteredKeys(p) {
+    override def empty = LinkedHashMap.empty
+  }
+  
+  override def filterKeys(p: A => Boolean): scala.collection.Map[A, B] = new FilteredKeys(p)
 
+  protected class MappedValues[C](f: B => C) extends super.MappedValues[C](f) {
+    override def empty = LinkedHashMap.empty
+  }
+  
+  override def mapValues[C](f: B => C): scala.collection.Map[A, C] = new MappedValues(f)
+  
+  protected class DefaultKeySet extends super.DefaultKeySet {
+    override def empty = LinkedHashSet.empty
+  }
+  
+  override def keySet: scala.collection.Set[A] = new DefaultKeySet
+  
   override def keysIterator: Iterator[A] = new AbstractIterator[A] {
     private var cur = firstEntry
     def hasNext = cur ne null
diff --git a/src/library/scala/collection/parallel/ParIterableLike.scala b/src/library/scala/collection/parallel/ParIterableLike.scala
index a447f1b5e4..815253b537 100644
--- a/src/library/scala/collection/parallel/ParIterableLike.scala
+++ b/src/library/scala/collection/parallel/ParIterableLike.scala
@@ -841,7 +841,7 @@ self: ParIterableLike[T, Repr, Sequential] =>
 
   override def toBuffer[U >: T]: collection.mutable.Buffer[U] = seq.toBuffer // have additional, parallel buffers?
 
-  override def toTraversable: GenTraversable[T] = this.asInstanceOf[GenTraversable[T]] // TODO add ParTraversable[T]
+  override def toTraversable: GenTraversable[T] = this.asInstanceOf[GenTraversable[T]]
 
   override def toIterable: ParIterable[T] = this.asInstanceOf[ParIterable[T]]
 
@@ -850,7 +850,13 @@ self: ParIterableLike[T, Repr, Sequential] =>
   override def toSet[U >: T]: immutable.ParSet[U] = toParCollection[U, immutable.ParSet[U]](() => immutable.ParSet.newCombiner[U])
 
   override def toMap[K, V](implicit ev: T <:< (K, V)): immutable.ParMap[K, V] = toParMap[K, V, immutable.ParMap[K, V]](() => immutable.ParMap.newCombiner[K, V])
+  
+  override def toVector: Vector[T] = convertTo[Vector]
 
+  override def convertTo[Col[_]](implicit cbf: CanBuildFrom[Nothing, T, Col[T @uncheckedVariance]]): Col[T @uncheckedVariance] = if (cbf().isCombiner) {
+    toParCollection[T, Col[T]](() => cbf().asCombiner)
+  } else seq.convertTo(cbf)
+  
   /* tasks */
 
   protected trait StrictSplitterCheckTask[R, Tp] extends Task[R, Tp] {
diff --git a/src/library/scala/collection/parallel/immutable/ParIterable.scala b/src/library/scala/collection/parallel/immutable/ParIterable.scala
index d8c42d74b0..349f4fa44c 100644
--- a/src/library/scala/collection/parallel/immutable/ParIterable.scala
+++ b/src/library/scala/collection/parallel/immutable/ParIterable.scala
@@ -34,6 +34,7 @@ extends collection/*.immutable*/.GenIterable[T]
    with collection.parallel.ParIterable[T]
    with GenericParTemplate[T, ParIterable]
    with ParIterableLike[T, ParIterable[T], collection.immutable.Iterable[T]]
+   with Immutable
 {
   override def companion: GenericCompanion[ParIterable] with GenericParCompanion[ParIterable] = ParIterable
 
diff --git a/src/library/scala/collection/parallel/immutable/ParVector.scala b/src/library/scala/collection/parallel/immutable/ParVector.scala
index 1ece663a1d..e4099f1809 100644
--- a/src/library/scala/collection/parallel/immutable/ParVector.scala
+++ b/src/library/scala/collection/parallel/immutable/ParVector.scala
@@ -62,6 +62,8 @@ extends ParSeq[T]
 
   override def seq: Vector[T] = vector
 
+  override def toVector: Vector[T] = vector
+
   class ParVectorIterator(_start: Int, _end: Int) extends VectorIterator[T](_start, _end) with SeqSplitter[T] {
     def remaining: Int = remainingElementCount
     def dup: SeqSplitter[T] = (new ParVector(remainingVector)).splitter
diff --git a/src/library/scala/collection/parallel/mutable/ParIterable.scala b/src/library/scala/collection/parallel/mutable/ParIterable.scala
index 700d21d0bb..b5747a31cf 100644
--- a/src/library/scala/collection/parallel/mutable/ParIterable.scala
+++ b/src/library/scala/collection/parallel/mutable/ParIterable.scala
@@ -29,7 +29,8 @@ import scala.collection.GenIterable
 trait ParIterable[T] extends collection/*.mutable*/.GenIterable[T]
                         with collection.parallel.ParIterable[T]
                         with GenericParTemplate[T, ParIterable]
-                        with ParIterableLike[T, ParIterable[T], Iterable[T]] {
+                        with ParIterableLike[T, ParIterable[T], Iterable[T]]
+                        with Mutable {
   override def companion: GenericCompanion[ParIterable] with GenericParCompanion[ParIterable] = ParIterable
   //protected[this] override def newBuilder = ParIterable.newBuilder[T]
 
diff --git a/src/library/scala/concurrent/SyncVar.scala b/src/library/scala/concurrent/SyncVar.scala
index 292014706d..5a6d95c2ed 100644
--- a/src/library/scala/concurrent/SyncVar.scala
+++ b/src/library/scala/concurrent/SyncVar.scala
@@ -53,8 +53,6 @@ class SyncVar[A] {
     value
   }
 
-  /** Waits for this SyncVar to become defined and returns
-   *  the result */
   def take(): A = synchronized {
     try get
     finally unsetVal()
@@ -66,8 +64,7 @@ class SyncVar[A] {
    *  the SyncVar.
    *
    *  @param timeout     the amount of milliseconds to wait, 0 means forever
-   *  @return            the value or a throws an exception if the timeout occurs
-   *  @throws NoSuchElementException on timeout
+   *  @return            `None` if variable is undefined after `timeout`, `Some(value)` otherwise
    */
   def take(timeout: Long): A = synchronized {
     try get(timeout).get
@@ -75,28 +72,25 @@ class SyncVar[A] {
   }
 
   // TODO: this method should be private
-  // [Heather] the reason why: it doesn't take into consideration
+  // [Heather] the reason why: it doesn't take into consideration 
   // whether or not the SyncVar is already defined. So, set has been
   // deprecated in order to eventually be able to make "setting" private
   @deprecated("Use `put` instead, as `set` is potentionally error-prone", "2.10.0")
   def set(x: A): Unit = setVal(x)
 
-  /** Places a value in the SyncVar. If the SyncVar already has a stored value,
-   * it waits until another thread takes it */
   def put(x: A): Unit = synchronized {
     while (isDefined) wait()
     setVal(x)
   }
 
-  /** Checks whether a value is stored in the synchronized variable */
   def isSet: Boolean = synchronized {
     isDefined
   }
 
   // TODO: this method should be private
-  // [Heather] the reason why: it doesn't take into consideration
+  // [Heather] the reason why: it doesn't take into consideration 
   // whether or not the SyncVar is already defined. So, unset has been
-  // deprecated in order to eventually be able to make "unsetting" private
+  // deprecated in order to eventually be able to make "unsetting" private  
   @deprecated("Use `take` instead, as `unset` is potentionally error-prone", "2.10.0")
   def unset(): Unit = synchronized {
     isDefined = false
@@ -104,7 +98,7 @@ class SyncVar[A] {
     notifyAll()
   }
 
-  // `setVal` exists so as to retroactively deprecate `set` without
+  // `setVal` exists so as to retroactively deprecate `set` without 
   // deprecation warnings where we use `set` internally. The
   // implementation of `set` was moved to `setVal` to achieve this
   private def setVal(x: A): Unit = synchronized {
@@ -113,13 +107,13 @@ class SyncVar[A] {
     notifyAll()
   }
 
-  // `unsetVal` exists so as to retroactively deprecate `unset` without
+  // `unsetVal` exists so as to retroactively deprecate `unset` without 
   // deprecation warnings where we use `unset` internally. The
   // implementation of `unset` was moved to `unsetVal` to achieve this
   private def unsetVal(): Unit = synchronized {
     isDefined = false
     value = None
-    notifyAll()
+    notifyAll()    
   }
 
 }
diff --git a/src/library/scala/reflect/ClassTag.scala b/src/library/scala/reflect/ClassTag.scala
index f753dfbcbb..860e7bac28 100644
--- a/src/library/scala/reflect/ClassTag.scala
+++ b/src/library/scala/reflect/ClassTag.scala
@@ -52,7 +52,7 @@ trait ClassTag[T] extends Equals with Serializable {
    * `SomeExtractor(...)` is turned into `ct(SomeExtractor(...))` if `T` in `SomeExtractor.unapply(x: T)`
    * is uncheckable, but we have an instance of `ClassTag[T]`.
    */
-  def unapply(x: Any): Option[T] = if (runtimeClass.isAssignableFrom(x.getClass)) Some(x.asInstanceOf[T]) else None
+  def unapply(x: Any): Option[T] = if (x != null && runtimeClass.isAssignableFrom(x.getClass)) Some(x.asInstanceOf[T]) else None
 
   /** case class accessories */
   override def canEqual(x: Any) = x.isInstanceOf[ClassTag[_]]
diff --git a/src/library/scala/reflect/base/Base.scala b/src/library/scala/reflect/base/Base.scala
index 461eaa2e9e..490a9e8c03 100644
--- a/src/library/scala/reflect/base/Base.scala
+++ b/src/library/scala/reflect/base/Base.scala
@@ -451,7 +451,7 @@ class Base extends Universe { self =>
     }
   }
 
-  def show(tree: Tree) = s"<tree ${tree.getClass}>"
+  def treeToString(tree: Tree) = s"<tree ${tree.getClass}>"
 
   trait TermTree extends Tree
 
diff --git a/src/library/scala/reflect/base/Trees.scala b/src/library/scala/reflect/base/Trees.scala
index 298d229570..2814450ae3 100644
--- a/src/library/scala/reflect/base/Trees.scala
+++ b/src/library/scala/reflect/base/Trees.scala
@@ -28,11 +28,11 @@ trait Trees { self: Universe =>
     def isType: Boolean
 
     /** Obtains string representation of a tree */
-    override def toString: String = show(this)
+    override def toString: String = treeToString(this)
   }
 
   /** Obtains string representation of a tree */
-  def show(tree: Tree): String
+  protected def treeToString(tree: Tree): String
 
   /** Tree is the basis for scala's abstract syntax. The nodes are
    *  implemented as case classes, and the parameters which initialize
diff --git a/src/library/scala/reflect/compat.scala b/src/library/scala/reflect/compat.scala
deleted file mode 100644
index fc0e5fbf9c..0000000000
--- a/src/library/scala/reflect/compat.scala
+++ /dev/null
@@ -1,33 +0,0 @@
-// [Eugene++] delete this once we merge with trunk and have a working IDE
-
-package scala.reflect {
-  trait ArrayTag[T]
-  trait ErasureTag[T]
-  trait ConcreteTypeTag[T]
-}
-
-package scala.reflect.api {
-  trait TypeTags {
-    trait TypeTag[T]
-    trait ConcreteTypeTag[T]
-  }
-}
-
-package scala {
-  import scala.reflect.base.{Universe => BaseUniverse}
-
-  trait reflect_compat {
-    lazy val mirror: BaseUniverse = ???
-  }
-}
-
-package scala.reflect {
-  import language.experimental.macros
-  import scala.reflect.base.{Universe => BaseUniverse}
-
-  trait internal_compat {
-    private[scala] def materializeArrayTag[T](u: BaseUniverse): ArrayTag[T] = ???
-    private[scala] def materializeErasureTag[T](u: BaseUniverse): ErasureTag[T] = ???
-    private[scala] def materializeConcreteTypeTag[T](u: BaseUniverse): ConcreteTypeTag[T] = ???
-  }
-}
\ No newline at end of file
diff --git a/src/library/scala/reflect/makro/internal/package.scala b/src/library/scala/reflect/makro/internal/package.scala
index d31a0f0d14..78cb0ffb10 100644
--- a/src/library/scala/reflect/makro/internal/package.scala
+++ b/src/library/scala/reflect/makro/internal/package.scala
@@ -9,7 +9,7 @@ import scala.reflect.base.{Universe => BaseUniverse}
 //
 // todo. once we have implicit macros for tag generation, we can remove these anchors
 // [Eugene++] how do I hide this from scaladoc?
-package object internal extends scala.reflect.internal_compat {
+package object internal {
   private[scala] def materializeClassTag[T](u: BaseUniverse): ClassTag[T] = macro ???
   private[scala] def materializeAbsTypeTag[T](u: BaseUniverse): u.AbsTypeTag[T] = macro ???
   private[scala] def materializeTypeTag[T](u: BaseUniverse): u.TypeTag[T] = macro ???
diff --git a/src/library/scala/reflect/package.scala b/src/library/scala/reflect/package.scala
index 0ee58df2cd..2ebc82875e 100644
--- a/src/library/scala/reflect/package.scala
+++ b/src/library/scala/reflect/package.scala
@@ -1,6 +1,6 @@
 package scala
 
-package object reflect extends reflect_compat {
+package object reflect {
 
   lazy val basis: base.Universe = new base.Base
 
diff --git a/src/library/scala/util/control/Breaks.scala b/src/library/scala/util/control/Breaks.scala
index d7f5a57f50..accda5b8f7 100644
--- a/src/library/scala/util/control/Breaks.scala
+++ b/src/library/scala/util/control/Breaks.scala
@@ -41,8 +41,8 @@ class Breaks {
     }
   }
 
-  trait TryBlock {
-    def catchBreak(onBreak: => Unit): Unit
+  sealed trait TryBlock[T] {
+    def catchBreak(onBreak: =>T): T
   }
 
   /**
@@ -57,8 +57,8 @@ class Breaks {
    * }
    * }}}
    */
-  def tryBreakable(op: => Unit) = new TryBlock {
-    def catchBreak(onBreak: => Unit) = try {
+  def tryBreakable[T](op: =>T) = new TryBlock[T] {
+    def catchBreak(onBreak: =>T) = try {
       op
     } catch {
       case ex: BreakControl =>
diff --git a/src/library/scala/util/control/ControlThrowable.scala b/src/library/scala/util/control/ControlThrowable.scala
index 8cbe3064ef..64afb1f10f 100644
--- a/src/library/scala/util/control/ControlThrowable.scala
+++ b/src/library/scala/util/control/ControlThrowable.scala
@@ -24,8 +24,9 @@ package scala.util.control
  *  try {
  *    // Body might throw arbitrarily
  *  } catch {
- *    case ce : ControlThrowable => throw ce // propagate
- *    case t : Exception => log(t)           // log and suppress
+ *    case c: ControlThrowable => throw c // propagate
+ *    case t: Exception        => log(t)  // log and suppress
+ *  }
  *  }}}
  *
  *  @author Miles Sabin