1.

80 files changed, 2630 insertions, 1437 deletions

diff --git a/src/compiler/scala/tools/ant/ScalaTool.scala b/src/compiler/scala/tools/ant/ScalaTool.scala
index 13a46070b5..c88939f502 100644
--- a/src/compiler/scala/tools/ant/ScalaTool.scala
+++ b/src/compiler/scala/tools/ant/ScalaTool.scala
@@ -300,10 +300,10 @@ package scala.tools.ant {
       }
 
     private def expandUnixVar(vars: Map[String,String]): Map[String,String] =
-      vars map { case Pair(_, vari) => vari.replaceAll("#([^#]*)#", "\\$$1") }
+      vars transform { (x, vari) => vari.replaceAll("#([^#]*)#", "\\$$1") }
 
     private def expandWinVar(vars: Map[String,String]): Map[String,String] =
-      vars map { case Pair(_, vari) => vari.replaceAll("#([^#]*)#", "%_$1%") }
+      vars transform { (x, vari) => vari.replaceAll("#([^#]*)#", "%_$1%") }
 
     private def pipeTemplate(template: String, patches: Map[String,String]) = {
       val resourceRoot = "scala/tools/ant/templates/"
diff --git a/src/compiler/scala/tools/nsc/ast/TreePrinters.scala b/src/compiler/scala/tools/nsc/ast/TreePrinters.scala
index 3ac528844e..0ba2519e0d 100644
--- a/src/compiler/scala/tools/nsc/ast/TreePrinters.scala
+++ b/src/compiler/scala/tools/nsc/ast/TreePrinters.scala
@@ -318,7 +318,9 @@ abstract class TreePrinters {
 
         case WildcardTypeTree(lo, hi) =>
           print("_ "); printOpt(" >: ", lo); printOpt(" <: ", hi)
-        case tree if (tree ne null) => print(tree.toString())
+
+        case tree =>
+          print("<unknown tree of class "+tree.getClass+">")
       }
       if (global.settings.printtypes.value && tree.isTerm && !tree.isEmpty) {
         print("{"); print(if (tree.tpe eq null) "<null>" else tree.tpe.toString()); print("}")
diff --git a/src/compiler/scala/tools/nsc/ast/parser/Parsers.scala b/src/compiler/scala/tools/nsc/ast/parser/Parsers.scala
index f40a759dc3..454eed1755 100644
--- a/src/compiler/scala/tools/nsc/ast/parser/Parsers.scala
+++ b/src/compiler/scala/tools/nsc/ast/parser/Parsers.scala
@@ -74,6 +74,8 @@ trait Parsers requires SyntaxAnalyzer {
       def freshName(prefix: String): Name = unit.fresh.newName(prefix)
     }
 
+    var implicitClassViews: List[Tree] = Nil
+
     /** this is the general parse method
      */
     def parse(): Tree = {
@@ -928,7 +930,7 @@ trait Parsers requires SyntaxAnalyzer {
 
     /** PostfixExpr   ::= [`.'] InfixExpr [Id [NewLine]]
      *  InfixExpr     ::= PrefixExpr
-     *                  | InfixExpr Id [NewLine] InfixExpr
+     *                  | InfixExpr Id [NewLine] (InfixExpr | ArgumentExprs)
      */
     def postfixExpr(): Tree = {
       val base = opstack
@@ -936,11 +938,12 @@ trait Parsers requires SyntaxAnalyzer {
       while (isIdent) {
         top = reduceStack(
           true, base, top, precedence(in.name), treeInfo.isLeftAssoc(in.name))
-        opstack = OpInfo(top, in.name, in.currentPos) :: opstack
+        val op = in.name
+        opstack = OpInfo(top, op, in.currentPos) :: opstack
         ident()
         newLineOptWhenFollowing(isExprIntroToken)
         if (isExprIntro) {
-          top = prefixExpr()
+          top = secondInfixOperandExpr(op)
         } else {
           val topinfo = opstack.head
           opstack = opstack.tail
@@ -952,6 +955,17 @@ trait Parsers requires SyntaxAnalyzer {
       reduceStack(true, base, top, 0, true)
     }
 
+    def secondInfixOperandExpr(op: Name): Tree =
+      if (in.token == LPAREN && treeInfo.isLeftAssoc(op)) {
+        val pos = in.currentPos
+        val args = argumentExprs()
+        if (args.isEmpty) simpleExprRest(Literal(()) setPos pos, false)
+        else if (args.tail.isEmpty) simpleExprRest(args.head, false)
+        else ArgumentExprs(args)
+      } else {
+        prefixExpr()
+      }
+
     /** PrefixExpr   ::= [`-' | `+' | `~' | `!' | `&' | `/'] SimpleExpr
     */
     def prefixExpr(): Tree =
@@ -1052,25 +1066,23 @@ trait Parsers requires SyntaxAnalyzer {
           syntaxError("illegal start of simple expression", true)
           t = errorTermTree
       }
-      while (true) {
-        in.token match {
-          case DOT =>
-            t = atPos(in.skipToken()) { selector(t) }
-          case LBRACKET =>
-            t match {
-              case Ident(_) | Select(_, _) =>
-                t = atPos(in.currentPos) { TypeApply(t, typeArgs(false)) }
-              case _ =>
-                return t
-            }
-          case LPAREN | LBRACE if (!isNew) =>
-            t = atPos(in.currentPos) { Apply(t, argumentExprs()) }
+      simpleExprRest(t, isNew)
+    }
+
+    def simpleExprRest(t: Tree, isNew: boolean): Tree = in.token match {
+      case DOT =>
+        simpleExprRest(atPos(in.skipToken()) { selector(t) }, false)
+      case LBRACKET =>
+        t match {
+          case Ident(_) | Select(_, _) =>
+            simpleExprRest(atPos(in.currentPos) { TypeApply(t, typeArgs(false)) }, false)
           case _ =>
-            return t
+            t
         }
-        isNew = false
-      }
-      null;//dummy
+      case LPAREN | LBRACE if (!isNew) =>
+        simpleExprRest(atPos(in.currentPos) { Apply(t, argumentExprs()) }, false)
+      case _ =>
+        t
     }
 
     /** ArgumentExprs ::= `(' [Exprs] `)'
@@ -1244,13 +1256,25 @@ trait Parsers requires SyntaxAnalyzer {
       while (isIdent && in.name != BAR) {
         top = reduceStack(
           false, base, top, precedence(in.name), treeInfo.isLeftAssoc(in.name))
-        opstack = OpInfo(top, in.name, in.currentPos) :: opstack
+        val op = in.name
+        opstack = OpInfo(top, op, in.currentPos) :: opstack
         ident()
-        top = simplePattern(seqOK)
+        top = secondInfixOperandPattern(op, seqOK)
       }
       reduceStack(false, base, top, 0, true)
     }
 
+    def secondInfixOperandPattern(op: Name, seqOK: boolean): Tree =
+      if (in.token == LPAREN && treeInfo.isLeftAssoc(op)) {
+        val pos = in.currentPos
+        val args = argumentPatterns()
+        if (args.isEmpty) Literal(()) setPos pos
+        else if (args.tail.isEmpty) args.head
+        else ArgumentExprs(args)
+      } else {
+        simplePattern(seqOK)
+      }
+
     /** SimplePattern    ::= varid
      *                    |  `_'
      *                    |  literal
@@ -1289,22 +1313,9 @@ trait Parsers requires SyntaxAnalyzer {
           }
         else */
         if (in.token == LPAREN) {
-          atPos(in.skipToken()) {
-            val ps = if (in.token == RPAREN) List() else patterns(true, false)
-            accept(RPAREN)
-            Apply(convertToTypeId(t), ps)
-          }
+          atPos(in.currentPos) { Apply(convertToTypeId(t), argumentPatterns()) }
         } else if (in.token == LBRACE) {
-          in.nextToken()
-          val ts = if (in.token == RBRACE) List()
-                   else {
-                     val p1 = pattern()
-                     accept(COMMA)
-                     p1 :: (if (in.token == RBRACE) List() else patterns(false, true))
-                   }
-          checkSize("tuple elements", ts.length, definitions.MaxTupleArity)
-          accept(RBRACE)
-          makeTupleTerm(ts, false)
+          atPos(in.currentPos) { Apply(convertToTypeId(t), List(tuplePattern())) }
         } else t
       case USCORE =>
         atPos(in.skipToken()) { Ident(nme.WILDCARD) }
@@ -1319,6 +1330,8 @@ trait Parsers requires SyntaxAnalyzer {
           else Literal(()).setPos(pos)
         accept(RPAREN)
         p
+      case LBRACE =>
+        tuplePattern()
       case XMLSTART =>
         xmlp.xLiteralPattern
       case _ =>
@@ -1329,6 +1342,26 @@ trait Parsers requires SyntaxAnalyzer {
         errorPatternTree
     }
 
+    def argumentPatterns(): List[Tree] = {
+      accept(LPAREN)
+      val ps = if (in.token == RPAREN) List() else patterns(true, false)
+      accept(RPAREN)
+      ps
+    }
+
+    def tuplePattern(): Tree = {
+      in.nextToken()
+      val ts = if (in.token == RBRACE) List()
+               else {
+                 val p1 = pattern()
+                 accept(COMMA)
+                 p1 :: (if (in.token == RBRACE) List() else patterns(false, true))
+               }
+      checkSize("tuple elements", ts.length, definitions.MaxTupleArity)
+      accept(RBRACE)
+      makeTuplePattern(ts)
+    }
+
 ////////// MODIFIERS ////////////////////////////////////////////////////////////
 
     /** Modifiers ::= {Modifier}
@@ -1511,7 +1544,7 @@ trait Parsers requires SyntaxAnalyzer {
      *  FunTypeParamClauseOpt ::= [[NewLine] `[' TypeParam {`,' TypeParam} `]']
      *  TypeParam             ::= Id TypeBounds [<% Type]
      */
-    def typeParamClauseOpt(owner: Name, implicitViews: ListBuffer[Tree]): List[AbsTypeDef] = {
+    def typeParamClauseOpt(owner: Name, implicitViewBuf: ListBuffer[Tree]): List[AbsTypeDef] = {
       def typeParam(): AbsTypeDef = {
         var mods = Modifiers(Flags.PARAM)
         if (owner.isTypeName && isIdent) {
@@ -1525,8 +1558,8 @@ trait Parsers requires SyntaxAnalyzer {
         }
         val pname = ident()
         val param = atPos(in.currentPos) { typeBounds(mods, pname) }
-        if (in.token == VIEWBOUND && (implicitViews ne null))
-          implicitViews += atPos(in.skipToken()) {
+        if (in.token == VIEWBOUND && (implicitViewBuf ne null))
+          implicitViewBuf += atPos(in.skipToken()) {
             makeFunctionTypeTree(List(Ident(pname.toTypeName)), typ())
           }
         param
@@ -1743,16 +1776,16 @@ trait Parsers requires SyntaxAnalyzer {
       atPos(in.skipToken()) {
         if (in.token == THIS) {
           in.nextToken()
-          val vparamss = paramClauses(nme.CONSTRUCTOR, List(), false)
-          val rhs = if (in.token == LBRACE) constrBlock()
-                    else { accept(EQUALS); constrExpr() }
+          val vparamss = paramClauses(nme.CONSTRUCTOR, implicitClassViews map (.duplicate), false)
+          val rhs = if (in.token == LBRACE) constrBlock(vparamss)
+                    else { accept(EQUALS); constrExpr(vparamss) }
           DefDef(mods, nme.CONSTRUCTOR, List(), vparamss, TypeTree(), rhs)
         } else {
           var newmods = mods
           val name = ident()
-          val implicitViews = new ListBuffer[Tree]
-          val tparams = typeParamClauseOpt(name, implicitViews)
-          val vparamss = paramClauses(name, implicitViews.toList, false)
+          val implicitViewBuf = new ListBuffer[Tree]
+          val tparams = typeParamClauseOpt(name, implicitViewBuf)
+          val vparamss = paramClauses(name, implicitViewBuf.toList, false)
           var restype = typedOpt()
           val rhs =
             if (in.token == SEMI || in.token == NEWLINE || in.token == RBRACE) {
@@ -1770,24 +1803,25 @@ trait Parsers requires SyntaxAnalyzer {
     /** ConstrExpr      ::=  SelfInvocation
      *                    |  ConstrBlock
      */
-    def constrExpr(): Tree =
-      if (in.token == LBRACE) constrBlock() else selfInvocation()
+    def constrExpr(vparamss: List[List[ValDef]]): Tree =
+      if (in.token == LBRACE) constrBlock(vparamss) else selfInvocation(vparamss)
 
     /** SelfInvocation  ::= this ArgumentExprs {ArgumentExprs}
      */
-    def selfInvocation(): Tree =
+    def selfInvocation(vparamss: List[List[ValDef]]): Tree =
       atPos(accept(THIS)) {
         var t = Apply(Ident(nme.CONSTRUCTOR), argumentExprs())
         while (in.token == LPAREN) t = Apply(t, argumentExprs())
+        if (!implicitClassViews.isEmpty) t = Apply(t, vparamss.last.map(vd => Ident(vd.name)))
         t
       }
 
     /** ConstrBlock    ::=  `{' SelfInvocation {StatementSeparator BlockStat} `}'
      */
-    def constrBlock(): Tree =
+    def constrBlock(vparamss: List[List[ValDef]]): Tree =
       atPos(in.skipToken()) {
         val statlist = new ListBuffer[Tree]
-        statlist += selfInvocation()
+        statlist += selfInvocation(vparamss)
         val stats =
           if (in.token == SEMI || in.token == NEWLINE) {
             in.nextToken(); blockStatSeq(statlist)
@@ -1844,17 +1878,21 @@ trait Parsers requires SyntaxAnalyzer {
     def classDef(mods: Modifiers): ClassDef =
       atPos(in.skipToken()) {
         val name = ident().toTypeName
-        val implicitViews = new ListBuffer[Tree]
-        val tparams = typeParamClauseOpt(name, implicitViews)
+        val savedViews = implicitClassViews
+        val implicitViewBuf = new ListBuffer[Tree]
+        val tparams = typeParamClauseOpt(name, implicitViewBuf)
+        implicitClassViews = implicitViewBuf.toList
         //if (mods.hasFlag(Flags.CASE) && in.token != LPAREN) accept(LPAREN)
         val vparamss = if (mods.hasFlag(Flags.TRAIT)) List()
-                       else paramClauses(name, implicitViews.toList, mods.hasFlag(Flags.CASE))
+                       else paramClauses(name, implicitClassViews, mods.hasFlag(Flags.CASE))
         val thistpe = requiresTypeOpt()
         val template = classTemplate(mods, name, vparamss)
         val mods1 = if (mods.hasFlag(Flags.TRAIT) && (template.body forall treeInfo.isInterfaceMember))
                       mods | Flags.INTERFACE
                     else mods
-        ClassDef(mods1, name, tparams, thistpe, template)
+        val result = ClassDef(mods1, name, tparams, thistpe, template)
+        implicitClassViews = savedViews
+        result
       }
 
     /** ObjectDef       ::= Id ClassTemplate
diff --git a/src/compiler/scala/tools/nsc/ast/parser/TreeBuilder.scala b/src/compiler/scala/tools/nsc/ast/parser/TreeBuilder.scala
index 3fe1bd28b8..e2d2fb4a97 100644
--- a/src/compiler/scala/tools/nsc/ast/parser/TreeBuilder.scala
+++ b/src/compiler/scala/tools/nsc/ast/parser/TreeBuilder.scala
@@ -92,6 +92,11 @@ abstract class TreeBuilder {
     case _ => makeTuple(trees, false)
   }
 
+  def makeTuplePattern(trees: List[Tree]): Tree = trees match {
+    case List() => Literal(())
+    case _ => makeTuple(trees, true)
+  }
+
   def makeTupleType(trees: List[Tree], flattenUnary: boolean): Tree = trees match {
     case List() => scalaUnitConstr
     case List(tree) if flattenUnary => tree
@@ -109,10 +114,14 @@ abstract class TreeBuilder {
   }
 
   /** Create tree representing (unencoded) binary operation expression or pattern. */
-  def makeBinop(isExpr: boolean, left: Tree, op: Name, right: Tree): Tree =
+  def makeBinop(isExpr: boolean, left: Tree, op: Name, right: Tree): Tree = {
+    val arguments = right match {
+      case ArgumentExprs(args) => args
+      case _ => List(right)
+    }
     if (isExpr) {
       if (treeInfo.isLeftAssoc(op)) {
-        Apply(Select(left, op.encode), List(right))
+        Apply(Select(left, op.encode), arguments)
       } else {
         val x = freshName();
         Block(
@@ -120,8 +129,9 @@ abstract class TreeBuilder {
           Apply(Select(right, op.encode), List(Ident(x))))
       }
     } else {
-      Apply(Ident(op.encode.toTypeName), List(left, right))
+      Apply(Ident(op.encode.toTypeName), left :: arguments)
     }
+  }
 
   /** Create tree representing an object creation <new parents { stats }> */
   def makeNew(parents: List[Tree], stats: List[Tree], argss: List[List[Tree]]): Tree =
@@ -425,4 +435,6 @@ abstract class TreeBuilder {
     case Select(qual, name) =>
       makePackaging(qual, List(PackageDef(name, stats)))
   }
+
+  case class ArgumentExprs(args: List[Tree]) extends Tree
 }
diff --git a/src/compiler/scala/tools/nsc/backend/jvm/GenJVM.scala b/src/compiler/scala/tools/nsc/backend/jvm/GenJVM.scala
index 82692e9ac7..433f4f055a 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/GenJVM.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/GenJVM.scala
@@ -792,7 +792,7 @@ abstract class GenJVM extends SubComponent {
             val mtype = new JMethodType(javaType(boxedClass), Array(javaType(kind)))
             jcode.emitINVOKESTATIC(javaName(boxedClass), "box", mtype)
 
-          case UNBOX(BOOL) /* if (boxType.symbol == definitions.BooleanClass) */=>
+          case UNBOX(BOOL) /* if (boxType.symbol == definitions.BooleanClass) */ =>
             // if null emit false
             val nonNull = jcode.newLabel()
             jcode.emitDUP()
@@ -874,7 +874,8 @@ abstract class GenJVM extends SubComponent {
             if (settings.debug.value)
               log("Emitting SWITHCH:\ntags: " + tags + "\nbranches: " + branches);
             jcode.emitSWITCH(tagArray,
-                             (branches map labels dropRight 1).copyToArray(branchArray, 0),
+                             { (branches map labels dropRight 1).copyToArray(branchArray, 0);
+                              branchArray },
                              labels(branches.last),
                              MIN_SWITCH_DENSITY);
 
diff --git a/src/compiler/scala/tools/nsc/symtab/Definitions.scala b/src/compiler/scala/tools/nsc/symtab/Definitions.scala
index 676d2e5530..3203637130 100644
--- a/src/compiler/scala/tools/nsc/symtab/Definitions.scala
+++ b/src/compiler/scala/tools/nsc/symtab/Definitions.scala
@@ -329,6 +329,7 @@ trait Definitions requires SymbolTable {
 
     // special attributes
     var SerializableAttr: Symbol = _
+    var DeprecatedAttr: Symbol = _
     var BeanPropertyAttr: Symbol = _
     var AnnotationDefaultAttr: Symbol = _
 
@@ -789,6 +790,7 @@ trait Definitions requires SymbolTable {
                                        nme.AnnotationDefaultATTR,
                                        List(AttributeClass.typeConstructor))
       SerializableAttr = getClass("scala.serializable")
+      DeprecatedAttr = getClass("scala.deprecated")
       BeanPropertyAttr = if (forCLDC) null else getClass("scala.reflect.BeanProperty")
     }
   }
diff --git a/src/compiler/scala/tools/nsc/symtab/Types.scala b/src/compiler/scala/tools/nsc/symtab/Types.scala
index 3673f1f4fc..7863e4c714 100644
--- a/src/compiler/scala/tools/nsc/symtab/Types.scala
+++ b/src/compiler/scala/tools/nsc/symtab/Types.scala
@@ -47,7 +47,7 @@ trait Types requires SymbolTable {
 
   private var explainSwitch = false
   private var checkMalformedSwitch = true
-  private var globalVariance = 1
+  private var globalVariance = 1//only necessary of healTypes = true?
   private final val healTypes = false
   private final val LubGlbMargin = 0
 
@@ -1436,7 +1436,7 @@ trait Types requires SymbolTable {
     }
 
     /** Map this function over given list of symbols */
-    private def mapOver(syms: List[Symbol]): List[Symbol] = {
+    def mapOver(syms: List[Symbol]): List[Symbol] = {
       val infos = syms map (.info)
       val infos1 = List.mapConserve(infos)(this)
       if (infos1 eq infos) syms
diff --git a/src/compiler/scala/tools/nsc/typechecker/Infer.scala b/src/compiler/scala/tools/nsc/typechecker/Infer.scala
index 0428161cc2..45d7f3f863 100644
--- a/src/compiler/scala/tools/nsc/typechecker/Infer.scala
+++ b/src/compiler/scala/tools/nsc/typechecker/Infer.scala
@@ -107,8 +107,10 @@ trait Infer requires Analyzer {
    *  @param targs   ...
    *  @return        ...
    */
-  private def isWithinBounds(tparams: List[Symbol], targs: List[Type]): boolean = {
-    val bounds = tparams map (.info.subst(tparams, targs).bounds)
+  private def isWithinBounds(pre: Type, owner: Symbol, tparams: List[Symbol], targs: List[Type]): boolean = {
+    val bounds = tparams map { tparam =>
+      tparam.info.asSeenFrom(pre, owner).subst(tparams, targs).bounds
+    }
     !(List.map2(bounds, targs)((bound, targ) => bound containsType targ) contains false)
   }
 
@@ -284,7 +286,7 @@ trait Infer requires Analyzer {
         for {
           val sym1 <- syms1
           val sym2 <- syms2
-          sym1 != sym2 && sym1.name == sym2.name
+          sym1 != sym2 && sym1.toString == sym2.toString
         } yield {
           val name = sym1.name
           explainName(sym1)
@@ -526,7 +528,7 @@ trait Infer requires Analyzer {
               val uninstantiated = new ListBuffer[Symbol]
               val targs = methTypeArgs(undetparams, formals, restpe, argtpes, pt, uninstantiated)
               (exprTypeArgs(uninstantiated.toList, restpe.subst(undetparams, targs), pt) ne null) &&
-              isWithinBounds(undetparams, targs)
+              isWithinBounds(NoPrefix, NoSymbol, undetparams, targs)
             } catch {
               case ex: NoInstance => false
             }
@@ -573,10 +575,10 @@ trait Infer requires Analyzer {
     /** error if arguments not within bounds. */
     def checkBounds(pos: PositionType, tparams: List[Symbol],
                     targs: List[Type], prefix: String): unit =
-      if (!isWithinBounds(tparams, targs)) {
+      if (!isWithinBounds(NoPrefix, NoSymbol, tparams, targs)) {
         if (!(targs exists (.isErroneous)) && !(tparams exists (.isErroneous))) {
           //Console.println("tparams = "+tparams+", bounds = "+tparams.map(.info)+", targs="+targs)//DEBUG
-          //withTypesExplained(isWithinBounds(tparams, targs))//DEBUG
+          //withTypesExplained(isWithinBounds(NoPrefix, tparams, targs))//DEBUG
           error(pos,
                 prefix + "type arguments " + targs.mkString("[", ",", "]") +
                 " do not conform to " + tparams.head.owner + "'s type parameter bounds " +
@@ -839,7 +841,7 @@ trait Infer requires Analyzer {
     }
 
     def inferTypedPattern(tpt: Tree, pt: Type): Type = {
-      //Console.println("infer typed pattern: "+tpt)//DEBUG
+      //Console.println("infer typed pattern: "+tpt+" wrt "+pt)//debug
       checkCheckable(tpt.pos, tpt.tpe)
       if (!(tpt.tpe <:< pt)) {
         val tpparams = freeTypeParamsOfTerms.collect(tpt.tpe)
@@ -1047,19 +1049,38 @@ trait Infer requires Analyzer {
      *  @param tree ...
      *  @param nparams ...
      */
-    def inferPolyAlternatives(tree: Tree, nparams: int): unit = tree.tpe match {
+    def inferPolyAlternatives(tree: Tree, argtypes: List[Type]): unit = tree.tpe match {
       case OverloadedType(pre, alts) =>
-        val sym = tree.symbol filter (alt => alt.typeParams.length == nparams)
+        val sym0 = tree.symbol filter { alt => alt.typeParams.length == argtypes.length }
+        if (sym0 == NoSymbol) {
+          error(
+            tree.pos,
+            if (alts exists (alt => alt.typeParams.length > 0))
+              "wrong number of type parameters for " + treeSymTypeMsg(tree)
+            else treeSymTypeMsg(tree) + " does not take type parameters")
+          return
+        }
+        val sym = sym0 filter { alt => isWithinBounds(pre, alt.owner, alt.typeParams, argtypes) }
         if (sym == NoSymbol) {
-          errorTree(tree,
-                    if (alts exists (alt => alt.typeParams.length > 0))
-                      "wrong number of type parameters for " + treeSymTypeMsg(tree)
-                    else treeSymTypeMsg(tree) + " does not take type parameters")
-        } else if (sym.hasFlag(OVERLOADED)) {
-          val tparams = sym.alternatives.head.typeParams
+          if (!(argtypes exists (.isErroneous))) {
+            Console.println(":"+sym0.alternatives.map(
+              alt => alt.typeParams.map(
+                p => p.info.asSeenFrom(pre, alt.owner))))
+            error(
+              tree.pos,
+              "type arguments " + argtypes.mkString("[", ",", "]") +
+              " conform to the bounds of none of the overloaded alternatives of\n "+sym0+
+              ": "+sym0.info)
+            return
+          }
+        }
+        if (sym.hasFlag(OVERLOADED)) {
+          val tparams = new AsSeenFromMap(pre, sym.alternatives.head.owner).mapOver(
+            sym.alternatives.head.typeParams)
+          val bounds = tparams map (.tpe)
           val tpe =
             PolyType(tparams,
-                     OverloadedType(AntiPolyType(pre, tparams map (.tpe)), sym.alternatives))
+                     OverloadedType(AntiPolyType(pre, bounds), sym.alternatives))
           sym.setInfo(tpe)
           tree.setSymbol(sym).setType(tpe)
         } else {
diff --git a/src/compiler/scala/tools/nsc/typechecker/Namers.scala b/src/compiler/scala/tools/nsc/typechecker/Namers.scala
index cb6e29650f..8e4e0d317e 100644
--- a/src/compiler/scala/tools/nsc/typechecker/Namers.scala
+++ b/src/compiler/scala/tools/nsc/typechecker/Namers.scala
@@ -533,6 +533,7 @@ trait Namers requires Analyzer {
       var result = tp;
       if (sym hasFlag IMPLICIT) {
         val p = provided(tp);
+        //Console.println("check contractive: "+sym+" "+p+"/"+required(tp))
         for (val r <- required(tp)) {
           if (!isContainedIn(r, p) || (r =:= p)) {
             context.error(sym.pos, "implicit " + sym + " is not contractive," +
@@ -549,6 +550,10 @@ trait Namers requires Analyzer {
       makePolyType(typer.reenterTypeParams(tparams), typer.typedType(rhs).tpe);
 
     def typeSig(tree: Tree): Type = {
+      tree match {
+        case md: MemberDef => attributes(md)
+        case _ =>
+      }
       val result =
         try {
           val sym: Symbol = tree.symbol
@@ -644,6 +649,66 @@ trait Namers requires Analyzer {
       deSkolemize(result)
     }
 
+    /**
+     *  @param defn ...
+     */
+    protected def attributes(defn: MemberDef): Unit = {
+      var attrError: Boolean = false;
+      def error(pos: PositionType, msg: String): Null = {
+        context.error(pos, msg)
+        attrError = true
+        null
+      }
+      def getConstant(tree: Tree): Constant = tree match {
+        case Literal(value) => value
+        case arg => error(arg.pos, "attribute argument needs to be a constant; found: "+arg)
+      }
+      val attrInfos =
+        for (val t @ Attribute(constr, elements) <- defn.mods.attributes) yield {
+          typer.typed(constr, EXPRmode | CONSTmode, AttributeClass.tpe) match {
+            case Apply(Select(New(tpt), nme.CONSTRUCTOR), args) =>
+              val constrArgs = args map getConstant
+              val attrScope = tpt.tpe.decls.
+                filter(sym => sym.isMethod && !sym.isConstructor && sym.hasFlag(JAVA));
+              val names = new collection.mutable.HashSet[Symbol]
+              names ++= attrScope.elements.filter(.isMethod)
+              if (args.length == 1) {
+                names.retain(sym => sym.name != nme.value)
+              }
+              val nvPairs = elements map {
+                case Assign(ntree @ Ident(name), rhs) => {
+                  val sym = attrScope.lookup(name);
+                  if (sym == NoSymbol) {
+                    error(ntree.pos, "unknown attribute element name: " + name)
+                  } else if (!names.contains(sym)) {
+                    error(ntree.pos, "duplicate value for element " + name)
+                  } else {
+                    names -= sym
+                    Pair(sym.name, getConstant(typer.typed(rhs, EXPRmode | CONSTmode, sym.tpe.resultType)))
+                  }
+                }
+              }
+              for (val name <- names) {
+                if (!name.attributes.contains(Triple(AnnotationDefaultAttr.tpe, List(), List()))) {
+                  error(t.pos, "attribute " + tpt.tpe.symbol.fullNameString + " is missing element " + name.name)
+                }
+              }
+              if (tpt.tpe.symbol.hasFlag(JAVA) && settings.target.value == "jvm-1.4") {
+                context.unit.warning (t.pos, "Java annotation will not be emitted in classfile unless you use the '-target:jvm-1.5' option")
+              }
+              Triple(tpt.tpe, constrArgs, nvPairs)
+          }
+        }
+      if (!attrError) {
+        val attributed =
+          if (defn.symbol.isModule) defn.symbol.moduleClass else defn.symbol
+        if (!attrInfos.isEmpty) {
+          attributed.attributes = attrInfos
+        }
+      }
+//    defn.mods setAttr List();
+    }
+
     /** Check that symbol's definition is well-formed. This means:
      *   - no conflicting modifiers
      *   - `abstract' modifier only for classes
diff --git a/src/compiler/scala/tools/nsc/typechecker/Typers.scala b/src/compiler/scala/tools/nsc/typechecker/Typers.scala
index 26799b4fd9..a55ba1045e 100644
--- a/src/compiler/scala/tools/nsc/typechecker/Typers.scala
+++ b/src/compiler/scala/tools/nsc/typechecker/Typers.scala
@@ -424,9 +424,16 @@ trait Typers requires Analyzer {
      *  </ol>
      */
     private def stabilize(tree: Tree, pre: Type, mode: int, pt: Type): Tree = {
+      def isDeprecated(sym: Symbol) =
+        sym.attributes exists (attr => attr._1.symbol == DeprecatedAttr)
       if (tree.symbol.hasFlag(OVERLOADED) && (mode & FUNmode) == 0)
         inferExprAlternative(tree, pt)
       val sym = tree.symbol
+      if (!phase.erasedTypes &&
+          isDeprecated(sym) && !context.owner.ownerChain.exists(isDeprecated)) {
+        unit.deprecationWarning(tree.pos,
+          sym+sym.locationString+" is deprecated;\n see API documentation for alternatives")
+      }
       if (tree.tpe.isError) tree
       else if ((mode & (PATTERNmode | FUNmode)) == PATTERNmode && tree.isTerm) { // (1)
         checkStable(tree)
@@ -807,7 +814,7 @@ trait Typers requires Analyzer {
      *  @return     ...
      */
     def typedClassDef(cdef: ClassDef): Tree = {
-      attributes(cdef)
+//      attributes(cdef)
       val clazz = cdef.symbol
       reenterTypeParams(cdef.tparams)
       val tparams1 = List.mapConserve(cdef.tparams)(typedAbsTypeDef)
@@ -826,7 +833,7 @@ trait Typers requires Analyzer {
      */
     def typedModuleDef(mdef: ModuleDef): Tree = {
       //Console.println("sourcefile of " + mdef.symbol + "=" + mdef.symbol.sourceFile)
-      attributes(mdef)
+//      attributes(mdef)
       val clazz = mdef.symbol.moduleClass
       val impl1 = newTyper(context.make(mdef.impl, clazz, newTemplateScope(mdef.impl, clazz)))
         .typedTemplate(mdef.impl, parentTypes(mdef.impl))
@@ -917,7 +924,7 @@ trait Typers requires Analyzer {
      *  @return     ...
      */
     def typedValDef(vdef: ValDef): ValDef = {
-      attributes(vdef)
+//      attributes(vdef)
       val sym = vdef.symbol
       val typer1 = if (sym.hasFlag(PARAM) && sym.owner.isConstructor)
                      newTyper(context.makeConstructorContext)
@@ -1001,7 +1008,7 @@ trait Typers requires Analyzer {
      *  @return     ...
      */
     def typedDefDef(ddef: DefDef): DefDef = {
-      attributes(ddef)
+//      attributes(ddef)
 
       val meth = ddef.symbol
 
@@ -1450,69 +1457,6 @@ trait Typers requires Analyzer {
     }
 
     /**
-     *  @param defn ...
-     */
-    protected def attributes(defn: MemberDef): Unit = {
-      var attrError: Boolean = false;
-      def getConstant(tree: Tree): Constant = tree match {
-        case Literal(value) => value
-        case arg =>
-          error(arg.pos, "attribute argument needs to be a constant; found: "+arg)
-          attrError = true;
-          null
-      }
-      val attrInfos =
-        for (val t @ Attribute(constr, elements) <- defn.mods.attributes) yield {
-          typed(constr, EXPRmode | CONSTmode, AttributeClass.tpe) match {
-            case Apply(Select(New(tpt), nme.CONSTRUCTOR), args) =>
-              val constrArgs = args map getConstant
-              val attrScope = tpt.tpe.decls.
-                filter(sym => sym.isMethod && !sym.isConstructor && sym.hasFlag(JAVA));
-              val names = new collection.mutable.HashSet[Symbol]
-              names ++= attrScope.elements.filter(.isMethod)
-              if (args.length == 1) {
-                names.filter(sym => sym.name != nme.value)
-              }
-              val nvPairs = elements map {
-                case Assign(ntree @ Ident(name), rhs) => {
-                  val sym = attrScope.lookup(name);
-                  if (sym == NoSymbol) {
-                    error(ntree.pos, "unknown attribute element name: " + name)
-                    attrError = true
-                    null
-                  } else if (!names.contains(sym)) {
-                    error(ntree.pos, "duplicate value for element " + name)
-                    attrError = true
-                    null
-                  } else {
-                    names -= sym
-                    Pair(sym.name, getConstant(typed(rhs, EXPRmode | CONSTmode, sym.tpe.resultType)))
-                  }
-                }
-              }
-              for (val name <- names) {
-                if (!name.attributes.contains(Triple(AnnotationDefaultAttr.tpe, List(), List()))) {
-                  error(t.pos, "attribute " + tpt.tpe.symbol.fullNameString + " is missing element " + name.name)
-                  attrError = true;
-                }
-              }
-              if (tpt.tpe.symbol.hasFlag(JAVA) && settings.target.value == "jvm-1.4") {
-                context.unit.warning (t.pos, "Java annotation will not be emitted in classfile unless you use the '-target:jvm-1.5' option")
-              }
-              Triple(tpt.tpe, constrArgs, nvPairs)
-          }
-        }
-      if (!attrError) {
-        val attributed =
-          if (defn.symbol.isModule) defn.symbol.moduleClass else defn.symbol
-        if (!attrInfos.isEmpty) {
-          attributed.attributes = attrInfos
-        }
-      }
-      defn.mods setAttr List();
-    }
-
-    /**
      *  @param tree ...
      *  @param mode ...
      *  @param pt   ...
@@ -1524,7 +1468,7 @@ trait Typers requires Analyzer {
 
       def typedTypeApply(fun: Tree, args: List[Tree]): Tree = fun.tpe match {
         case OverloadedType(pre, alts) =>
-          inferPolyAlternatives(fun, args.length)
+          inferPolyAlternatives(fun, args map (.tpe))
           typedTypeApply(fun, args)
         case PolyType(tparams, restpe) if (tparams.length != 0) =>
           if (tparams.length == args.length) {
@@ -2153,7 +2097,8 @@ trait Typers requires Analyzer {
           tree setType ref1.tpe.resultType
 
         case SelectFromTypeTree(qual, selector) =>
-          tree setType typedSelect(typedType(qual), selector).tpe
+          val sel = typedSelect(typedType(qual), selector)
+          tree setSymbol sel.symbol setType typedSelect(typedType(qual), selector).tpe
 
         case tree @ CompoundTypeTree(templ: Template) =>
           tree setType {
diff --git a/src/library/scala/Array.scala b/src/library/scala/Array.scala
index a7534e31fb..041213beb8 100644
--- a/src/library/scala/Array.scala
+++ b/src/library/scala/Array.scala
@@ -166,14 +166,90 @@ object Array {
  */
 final class Array[A](_length: Int) extends Seq[A] {
   import Predef.Error
+
+  /** The length of the array */
   def length: Int = throw new Error()
+
+  /** The element at given index.
+   *  Indices start a <code>0</code>; <code>xs.apply(0)</code> is the first
+   *  element of array <code>xs</code>.
+   *  Note the indexing syntax <code>xs(i)</code> is a shorthand for <code>xs.apply(i)</code>.
+   *  @param i   the index
+   *  @throws ArrayIndexOutOfBoundsException if <code>i < 0</code> or
+   *          <code>length <= i</code>
+   */
   def apply(i: Int): A = throw new Error()
+
+  /** Update the element at given index.
+   *  Indices start a <code>0</code>; <code>xs.apply(0)</code> is the first
+   *  element of array <code>xs</code>.
+   *  Note the indexing syntax <code>xs(i) = x</code> is a shorthand
+   *  for <code>xs.update(i, x)</code>.
+   *  @param i   the index
+   *  @param x   the value to be written at index <code>i</code>
+   *  @throws ArrayIndexOutOfBoundsException if <code>i < 0</code> or
+   *          <code>length <= i</code>
+   */
   def update(i: Int, x: A): Unit = throw new Error()
+
+  /** An iterator returning the elements of this array, starting from 0.
+   */
   def elements: Iterator[A] = throw new Error()
+
+  /** @deprecated  use slice instead */
   def subArray(from: Int, end: Int): Array[A] = throw new Error()
-  def filter(p: A => Boolean): Array[A] = throw new Error()
-  def map[B](f: A => B): Array[B] = throw new Error()
-  def flatMap[B](f: A => Array[B]): Array[B] = throw new Error()
+
+  /** A sub-array of <code>len</code> elements
+   *  starting at index <code>from</code>
+   *  @param from   The index of the first element of the slice
+   *  @param len    The number of elements in the slice
+   *  @throws IndexOutOfBoundsException if <code>from < 0</code>
+   *          or <code>length < from + len<code>
+   */
+  override def slice(from: Int, len: Int): Array[A] = throw new Error()
+
+  /** Returns an array consisting of all elements of this array that satisfy the
+   *  predicate <code>p</code>. The order of the elements is preserved.
+   *
+   *  @param p the predicate used to filter the array.
+   *  @return the elements of this array satisfying <code>p</code>.
+   */
+  override def filter(p: A => Boolean): Array[A] = throw new Error()
+
+  /** Returns the array resulting from applying the given function <code>f</code> to each
+   *  element of this array.
+   *
+   *  @param f function to apply to each element.
+   *  @return <code>[f(a0), ..., f(an)]</code> if this array is <code>[a0, ..., an]</code>.
+   */
+  override def map[B](f: A => B): Array[B] = throw new Error()
+
+  /** Applies the given function <code>f</code> to each element of
+   *  this array, then concatenates the results.
+   *
+   *  @param f the function to apply on each element.
+   *  @return  <code>f(a<sub>0</sub>) ::: ... ::: f(a<sub>n</sub>)</code> if
+   *           this array is <code>[a<sub>0</sub>, ..., a<sub>n</sub>]</code>.
+   */
+  override def flatMap[B](f: A => Iterable[B]): Array[B] = throw new Error()
+
+  /** Returns an array formed from this array and the specified array
+   *  <code>that</code> by associating each element of the former with
+   *  the element at the same position in the latter.
+   *  If one of the two arrays is longer than the other, its remaining elements are ignored.
+   *
+   *  @return     <code>Array({a<sub>0</sub>,b<sub>0</sub>}, ...,
+   *              {a<sub>min(m,n)</sub>,b<sub>min(m,n)</sub>})</code> when
+   *              <code>Array(a<sub>0</sub>, ..., a<sub>m</sub>)
+   *              zip Array(b<sub>0</sub>, ..., b<sub>n</sub>)</code> is invoked.
+   */
   def zip[B](that: Array[B]): Array[Tuple2[A,B]] = throw new Error()
+
+  /** Returns an array that pairs each element of this array
+   *  with its index, counting from 0.
+   *
+   *  @return      the array <code>Array({a<sub>0</sub>,0}, {a<sub>1</sub>,1},...)</code>
+   *               where <code>a<sub>i</sub></code> are the elements of this stream.
+   */
   def zipWithIndex: Array[Tuple2[A,Int]] = throw new Error()
 }
diff --git a/src/library/scala/Iterable.scala b/src/library/scala/Iterable.scala
index 600736fea2..13699db23a 100644
--- a/src/library/scala/Iterable.scala
+++ b/src/library/scala/Iterable.scala
@@ -13,6 +13,8 @@ package scala
 
 
 import Predef.IllegalArgumentException
+import collection.mutable.{Buffer,ArrayBuffer}
+import compat.StringBuilder
 
 /** This object ...
  *
@@ -62,6 +64,11 @@ object Iterable {
     }
     max
   }
+
+  /** The empty iterable object */
+  val empty = new Iterable[Nothing] {
+    def elements = Iterator.empty
+  }
 }
 
 
@@ -81,15 +88,96 @@ trait Iterable[+A] {
    */
   def elements: Iterator[A]
 
-  /** Concatenates two iterable objects
+  /** Appends two iterable objects
    *
    *  @return the new iterable object
-   *  @author buraq
    */
-  def concat[B >: A](that: Iterable[B]): Iterable[B] = new Iterable[B] {
-    def elements: Iterator[B] = Iterable.this.elements.append(that.elements)
+  def concat [B >: A](that: Iterable[B]): Iterable[B] = {
+    val buf = new ArrayBuffer[B]
+    this copyToBuffer buf
+    that copyToBuffer buf
+    buf
+  }
+
+  /** Returns the iterable resulting from applying the given function <code>f</code> to each
+   *  element of this iterable.
+   *
+   *  @param f function to apply to each element.
+   *  @return <code>f(a0), ..., f(an)</code> if this iterable is <code>a0, ..., an</code>.
+   */
+  def map[B](f: A => B): Iterable[B] = {
+    val buf = new ArrayBuffer[B]
+    val elems = elements
+    while (elems.hasNext) buf += f(elems.next)
+    buf
   }
 
+  /** Applies the given function <code>f</code> to each element of
+   *  this iterable, then concatenates the results.
+   *
+   *  @param f the function to apply on each element.
+   *  @return  <code>f(a<sub>0</sub>) ::: ... ::: f(a<sub>n</sub>)</code> if
+   *           this iterable is <code>a<sub>0</sub>, ..., a<sub>n</sub></code>.
+   */
+  def flatMap[B](f: A => Iterable[B]): Iterable[B] = {
+    val buf = new ArrayBuffer[B]
+    val elems = elements
+    while (elems.hasNext) f(elems.next) copyToBuffer buf
+    buf
+  }
+
+  /** Returns all the elements of this iterable that satisfy the
+   *  predicate <code>p</code>. The order of the elements is preserved.
+   *
+   *  @param p the predicate used to filter the list.
+   *  @return the elements of this list satisfying <code>p</code>.
+   */
+  def filter(p: A => Boolean): Iterable[A] = {
+    val buf = new ArrayBuffer[A]
+    val elems = elements
+    while (elems.hasNext) { val x = elems.next; if (p(x)) buf += x }
+    buf
+  }
+
+  /** Returns the longest prefix of this iterable whose elements satisfy
+   *  the predicate <code>p</code>.
+   *
+   *  @param p the test predicate.
+   *  @return  the longest prefix of this iterable whose elements satisfy
+   *           the predicate <code>p</code>.
+   */
+  def takeWhile(p: A => Boolean): Iterable[A] =
+    new ArrayBuffer[A] ++ elements.takeWhile(p)
+
+  /** Returns the longest suffix of this iterable whose first element
+   *  does not satisfy the predicate <code>p</code>.
+   *
+   *  @param p the test predicate.
+   *  @return  the longest suffix of the iterable whose first element
+   *           does not satisfy the predicate <code>p</code>.
+   */
+  def dropWhile(p: A => Boolean): Iterable[A] =
+    new ArrayBuffer[A] ++ elements.dropWhile(p)
+
+  /** Returns an iterable consisting only over the first <code>n</code>
+   *  elements of this iterable, or else the whole iterable, if it has less
+   *  than <code>n</code> elements.
+   *
+   *  @param n the number of elements to take
+   *  @return  the new iterable
+   */
+  def take(n: Int): Iterable[A] =
+    new ArrayBuffer[A] ++ elements.take(n)
+
+  /** Returns this iterable without its <code>n</code> first elements
+   *  If this iterable has less than <code>n</code> elements, the empty iterable is returned.
+   *
+   *  @param n the number of elements to drop
+   *  @return  the new iterable
+   */
+  def drop(n: Int): Iterable[A] =
+    new ArrayBuffer[A] ++ elements.take(n)
+
   /** Apply a function <code>f</code> to all elements of this
    *  iterable object.
    *
@@ -163,19 +251,22 @@ trait Iterable[+A] {
     if (found) i else -1
   }
 
-  /** Combines the elements of this list together using the binary
-   *  operator <code>op</code>, from left to right, and starting with
+  /** Combines the elements of this iterable object together using the binary
+   *  function <code>f</code>, from left to right, and starting with
    *  the value <code>z</code>.
-   *  @return <code>op(... (op(op(z,a0),a1) ...), an)</code> if the list
-   *  is <code>List(a0, a1, ..., an)</code>.
+   *
+   *  @return <code>f(... (f(f(z, a<sub>0</sub>), a<sub>1</sub>) ...),
+   *          a<sub>n</sub>)</code> if the list is
+   *          <code>[a<sub>0</sub>, a<sub>1</sub>, ..., a<sub>n</sub>]</code>.
    */
   def foldLeft[B](z: B)(op: (B, A) => B): B = elements.foldLeft(z)(op)
 
   /** Combines the elements of this list together using the binary
-   *  operator <code>op</code>, from rigth to left, and starting with
+   *  function <code>f</code>, from right to left, and starting with
    *  the value <code>z</code>.
-   *  @return <code>a0 op (... op (an op z)...)</code> if the list
-   *  is <code>[a0, a1, ..., an]</code>.
+   *
+   *  @return <code>f(a<sub>0</sub>, f(a<sub>1</sub>, f(..., f(a<sub>n</sub>, z)...)))</code>
+   *          if the list is <code>[a<sub>0</sub>, a1, ..., a<sub>n</sub>]</code>.
    */
   def foldRight[B](z: B)(op: (A, B) => B): B = elements.foldRight(z)(op)
 
@@ -183,12 +274,39 @@ trait Iterable[+A] {
    *  an operator with the order of list and zero arguments reversed.
    *  That is, <code>z /: xs</code> is the same as <code>xs foldLeft z</code>
    */
-  def /:[B](z: B)(f: (B, A) => B): B = foldLeft(z)(f)
+  def /:[B](z: B)(op: (B, A) => B): B = foldLeft(z)(op)
 
   /** An alias for <code>foldRight</code>.
    *  That is, <code>xs :\ z</code> is the same as <code>xs foldRight z</code>
    */
-  def :\[B](z: B)(f: (A, B) => B): B = foldRight(z)(f)
+  def :\[B](z: B)(op: (A, B) => B): B = foldRight(z)(op)
+
+  /** Combines the elements of this iterable object together using the binary
+   *  operator <code>op</code>, from left to right
+   *  @param op  The operator to apply
+   *  @return <code>op(... op(a<sub>0</sub>,a<sub>1</sub>), ..., a<sub>n</sub>)</code>
+      if the iterable object has elements
+   *          <code>a<sub>0</sub>, a<sub>1</sub>, ..., a<sub>n</sub></code>.
+   *  @throws Predef.UnsupportedOperationException if the iterable object is empty.
+   */
+  def reduceLeft[B >: A](op: (B, B) => B): B = elements.reduceLeft(op)
+
+/** Combines the elements of this iterable object together using the binary
+   *  operator <code>op</code>, from right to left
+   *  @param op  The operator to apply
+   *
+   *  @return <code>a<sub>0</sub> op (... op (a<sub>n-1</sub> op a<sub>n</sub>)...)</code>
+   *          if the iterable object has elements <code>a<sub>0</sub>, a<sub>1</sub>, ...,
+   *          a<sub>n</sub></code>.
+   *
+   *  @throws Predef.UnsupportedOperationException if the iterator is empty.
+   */
+  def reduceRight[B >: A](op: (B, B) => B): B = elements.reduceRight(op)
+
+  /** Copy all elements to a given buffer
+   *  @param  dest   The buffer to which elements are copied
+   */
+  def copyToBuffer[B >: A](dest: Buffer[B]): Unit = elements copyToBuffer dest
 
   /** Checks if the other iterable object contains the same elements.
    *
@@ -209,4 +327,42 @@ trait Iterable[+A] {
    * @return a list with all the elements of this iterable object
    */
   def toList: List[A] = elements.toList
+
+  /** Returns a string representation of this iterable object. The resulting string
+   *  begins with the string <code>start</code> and is finished by the string
+   *  <code>end</code>. Inside, the string representations of elements (w.r.t.
+   *  the method <code>toString()</code>) are separated by the string
+   *  <code>sep</code>.
+   *  <p/>
+   *  Ex: <br/>
+   *  <code>List(1, 2, 3).mkString("(", "; ", ")") = "(1; 2; 3)"</code>
+   *
+   *  @param start starting string.
+   *  @param sep separator string.
+   *  @param end ending string.
+   *  @return a string representation of this iterable object.
+   */
+  def mkString(start: String, sep: String, end: String): String = {
+    val buf = new StringBuilder()
+    buf.append(start)
+    val elems = elements
+    if (elems.hasNext) buf.append(elems.next)
+    while (elems.hasNext) {
+      buf.append(sep); buf.append(elems.next)
+    }
+    buf.append(end)
+    buf.toString
+  }
+
+  /** Write all elements of this string into given string builder */
+  // todo: haromize with print?
+  def addString(buf: StringBuilder, start: String, sep: String, end: String): StringBuilder = {
+    buf.append(start)
+    val elems = elements
+    if (elems.hasNext) buf.append(elems.next)
+    while (elems.hasNext) {
+      buf.append(sep); buf.append(elems.next)
+    }
+    buf.append(end)
+  }
 }
diff --git a/src/library/scala/IterableProxy.scala b/src/library/scala/IterableProxy.scala
index a35e7e0ecd..84fccb9d7a 100644
--- a/src/library/scala/IterableProxy.scala
+++ b/src/library/scala/IterableProxy.scala
@@ -11,96 +11,44 @@
 
 package scala
 
+import collection.mutable.Buffer
+import scala.compat.StringBuilder
+
 
 /** This class implements a proxy for iterable objects. It forwards
  *  all calls to a different iterable object.
  *
  *  @author  Matthias Zenger
- *  @version 1.0, 26/04/2004
+ *  @author  Martin Odersky
+ *  @version 2.0, 31/12/2006
  */
 trait IterableProxy[+A] extends Iterable[A] with Proxy {
 
   def self: Iterable[A]
-
-  /** Creates a new iterator over all elements contained in this
-   *  object.
-   *
-   *  @return the new iterator
-   */
-  def elements: Iterator[A] = self.elements
-
-  /** Apply a function <code>f</code> to all elements of this
-   *  iterable object.
-   *
-   *  @param  f   a function that is applied to every element.
-   */
-  override def foreach(f: A => Unit): Unit = self.foreach(f)
-
-  /** Apply a predicate <code>p</code> to all elements of this
-   *  iterable object and return true, iff the predicate yields
-   *  true for all elements.
-   *
-   *  @param   p     the predicate
-   *  @returns true, iff the predicate yields true for all elements.
-   */
-  override def forall(p: A => Boolean): Boolean = self.forall(p)
-
-  /** Apply a predicate <code>p</code> to all elements of this
-   *  iterable object and return true, iff there is at least one
-   *  element for which <code>p</code> yields true.
-   *
-   *  @param   p     the predicate
-   *  @returns true, iff the predicate yields true for at least one element.
-   */
-  override def exists(p: A => Boolean): Boolean = self.exists(p)
-
-  /** Find and return the first element of the iterable object satisfying a
-   *  predicate, if any.
-   *
-   *  @param p the predicate
-   *  @return the first element in the iterable object satisfying <code>p</code>,
-   *  or <code>None</code> if none exists.
-   */
-  override def find(p: A => Boolean): Option[A] = self.find(p)
-
-  /** Combines the elements of this list together using the binary
-   *  operator <code>op</code>, from left to right, and starting with
-   *  the value <code>z</code>.
-   *  @return <code>op(... (op(op(z,a0),a1) ...), an)</code> if the list
-   *  is <code>List(a0, a1, ..., an)</code>.
-   */
-  override def foldLeft[B](z: B)(op: (B, A) => B): B = self.foldLeft(z)(op)
-
-  /** Combines the elements of this list together using the binary
-   *  operator <code>op</code>, from rigth to left, and starting with
-   *  the value <code>z</code>.
-   *  @return <code>a0 op (... op (an op z)...)</code> if the list
-   *  is <code>[a0, a1, ..., an]</code>.
-   */
-  override def foldRight[B](z: B)(op: (A, B) => B): B = self.foldRight(z)(op)
-
-  /** Similar to <code>foldLeft</code> but can be used as
-   *  an operator with the order of list and zero arguments reversed.
-   *  That is, <code>z /: xs</code> is the same as <code>xs foldLeft z</code>
-   */
-  override def /:[B](z: B)(f: (B, A) => B): B = self./:(z)(f)
-
-  /** An alias for <code>foldRight</code>.
-   *  That is, <code>xs :\ z</code> is the same as <code>xs foldRight z</code>
-   *
-   *  @param z ...
-   *  @param f ...
-   *  @return ...
-   */
-  override def :\[B](z: B)(f: (A, B) => B): B = self.:\(z)(f)
-
-  /** Checks if the other iterable object contains the same elements.
-   *
-   *  @param that  the other iterable object
-   *  @return true, iff both iterable objects contain the same elements.
-   */
-  override def sameElements[B >: A](that: Iterable[B]): Boolean =
-    self.sameElements(that)
-
+  override def elements: Iterator[A] = self.elements
+  override def concat [B >: A](that: Iterable[B]): Iterable[B] = self concat that
+  override def map[B](f: A => B): Iterable[B] = self map f
+  override def flatMap[B](f: A => Iterable[B]): Iterable[B] = self flatMap f
+  override def filter(p: A => Boolean): Iterable[A] = self filter p
+  override def takeWhile(p: A => Boolean): Iterable[A] = self takeWhile p
+  override def dropWhile(p: A => Boolean): Iterable[A] = self dropWhile p
+  override def take(n: Int): Iterable[A] = self take n
+  override def drop(n: Int): Iterable[A] = self drop n
+  override def foreach(f: A => Unit): Unit = self foreach f
+  override def forall(p: A => Boolean): Boolean = self forall p
+  override def exists(p: A => Boolean): Boolean = self exists p
+  override def find(p: A => Boolean): Option[A] = self find p
+  override def findIndexOf(p: A => Boolean): Int = self findIndexOf p
+  override def indexOf[B >: A](elem: B): Int = self indexOf elem
+  override def foldLeft[B](z: B)(op: (B, A) => B): B = (self foldLeft z)(op)
+  override def foldRight[B](z: B)(op: (A, B) => B): B = (self foldRight z)(op)
+  override def /:[B](z: B)(op: (B, A) => B): B = (z /: self)(op)
+  override def :\[B](z: B)(op: (A, B) => B): B = (self :\ z)(op)
+  override def reduceLeft[B >: A](op: (B, B) => B): B = self reduceLeft op
+  override def reduceRight[B >: A](op: (B, B) => B): B = self reduceRight op
+  override def sameElements[B >: A](that: Iterable[B]): Boolean = self sameElements that
+  override def copyToBuffer[B >: A](dest: Buffer[B]): Unit = self copyToBuffer dest
   override def toList: List[A] = self.toList
+  override def mkString(start: String, sep: String, end: String): String = self.mkString(start, sep, end)
+  override def addString(buf: StringBuilder, start: String, sep: String, end: String): StringBuilder = self.addString(buf, start, sep, end)
 }
diff --git a/src/library/scala/Iterator.scala b/src/library/scala/Iterator.scala
index e652cc4ded..e8fb2d4f05 100644
--- a/src/library/scala/Iterator.scala
+++ b/src/library/scala/Iterator.scala
@@ -13,6 +13,7 @@ package scala
 
 
 import Predef._
+import collection.mutable.{Buffer, ArrayBuffer}
 
 /** The <code>Iterator</code> object provides various functions for
  *  creating specialized iterators.
@@ -23,9 +24,9 @@ import Predef._
  */
 object Iterator {
 
-  def empty[a] = new Iterator[a] {
+  val empty = new Iterator[Nothing] {
     def hasNext: Boolean = false
-    def next: a = throw new NoSuchElementException("next on empty iterator")
+    def next: Nothing = throw new NoSuchElementException("next on empty iterator")
   }
 
   /**
@@ -91,9 +92,9 @@ object Iterator {
   }
 
   /**
-   * @deprecated use class <code>Product&lt;n&gt;</code> instead.
+   * @deprecated use <code>fromProduct</code> instead.
    */
-  def fromCaseClass(n: Product) = fromProduct(n)
+  [deprecated] def fromCaseClass(n: Product) = fromProduct(n)
 
   /** Create an iterator with elements
    *  <code>e<sub>n+1</sub> = e<sub>n</sub> + 1</code>
@@ -218,7 +219,7 @@ trait Iterator[+A] {
   /** Returns a new iterator that iterates only over the first <code>n</code>
    *  elements.
    *
-   *  @param n the first <code>n</code> elements of the iterator
+   *  @param n the number of elements to take
    *  @return  the new iterator
    */
   def take(n: Int) = new Iterator[A] {
@@ -230,6 +231,9 @@ trait Iterator[+A] {
   }
 
   /** Removes the first <code>n</code> elements from this iterator.
+   *
+   *  @param n the number of elements to drop
+   *  @return  the new iterator
    */
   def drop(n: Int): Iterator[A] =
     if (n > 0) { next; drop(n - 1) } else this
@@ -274,14 +278,7 @@ trait Iterator[+A] {
       } else throw new NoSuchElementException("next on empty iterator")
   }
 
-  /** Returns an iterator over all the elements of this iterator that
-   *  satisfy the predicate <code>p</code>. The order of the elements
-   *  is preserved.
-   *
-   *  @param p the predicate used to filter the iterator.
-   *  @return  the elements of this iterator satisfying <code>p</code>.
-   */
-  def filter(p: A => Boolean): Iterator[A] = new BufferedIterator[A] {
+  private def predicatedIterator(p: A => boolean, isFilter: boolean) = new BufferedIterator[A] {
     private var hd: A = _
     private var ahead: Boolean = false
     private var hasMore = Iterator.this.hasNext
@@ -291,21 +288,51 @@ trait Iterator[+A] {
         hasMore = Iterator.this.hasNext
         ahead = p(hd)
       }
-    def hasNext: Boolean = { skip; ahead || hasMore }
+    def hasNext: Boolean = { skip; ahead || isFilter && hasMore }
     def next: A =
       if (hasNext) { ahead = false; hd }
       else throw new NoSuchElementException("next on empty iterator")
     def head: A = { skip; hd }
- }
+  }
+
+  /** Returns an iterator over all the elements of this iterator that
+   *  satisfy the predicate <code>p</code>. The order of the elements
+   *  is preserved.
+   *
+   *  @param p the predicate used to filter the iterator.
+   *  @return  the elements of this iterator satisfying <code>p</code>.
+   */
+  def filter(p: A => Boolean): Iterator[A] = predicatedIterator(p, true)
+
+  /** Returns an iterator over the longest prefix of this iterator such that
+   *  all elements of the result satisfy the predicate <code>p</code>.
+   *  The order of the elements is preserved.
+   *
+   *  @param p the predicate used to filter the iterator.
+   *  @return  the longest prefix of this iterator satisfying <code>p</code>.
+   */
+  def takeWhile(p: A => Boolean): Iterator[A] = predicatedIterator(p, false)
+
+  /** Skips longest sequence of elements of this iterator which satisfy given
+   *  predicate <code>p</code>, and returns an iterator of the remaining elements.
+   *
+   *  @param p the predicate used to skip elements.
+   *  @return  an iterator consisting of the remaining elements
+   */
+  def dropWhile(p: A => Boolean): Iterator[A] =
+    if (hasNext) {
+      val x = next
+      if (p(x)) dropWhile(p)
+      else Iterator.single(x) append this
+    } else this
 
   /** Return an iterator formed from this iterator and the specified iterator
    *  <code>that</code> by associating each element of the former with
    *  the element at the same position in the latter.
+   *  If one of the two iterators is longer than the other, its remaining elements are ignored.
    *
-   *  @param that list <code>that</code> must have the same number of
-   *              elements as this iterator.
-   *  @return     an iterator yielding <code>(a<sub>0</sub>,b<sub>0</sub>), ...,
-   *              (a<sub>n</sub>,b<sub>n</sub>)</code> where
+   *  @return     an iterator yielding <code>{a<sub>0</sub>,b<sub>0</sub>},
+   *              {a<sub>1</sub>,b<sub>1</sub>}, ...</code> where
    *              <code>a<sub>i</sub></code> are the elements from this iterator
    *              and <code>b<sub>i</sub></code> are the elements from iterator
    *              <code>that</code>.
@@ -319,8 +346,8 @@ trait Iterator[+A] {
    *  with its index, counting from 0.
    *
    *  @param start the index of the first element.
-   *  @return      an iterator yielding <code>(a<sub>0</sub>,0),
-   *               (a<sub>0</sub>,1)...</code> where <code>a<sub>i</sub></code>
+   *  @return      an iterator yielding <code>{a<sub>0</sub>,0},
+   *               {a<sub>1</sub>,1}...</code> where <code>a<sub>i</sub></code>
    *               are the elements from this iterator.
    */
   def zipWithIndex = new Iterator[Pair[A, int]] {
@@ -368,10 +395,10 @@ trait Iterator[+A] {
     res
   }
 
-  /** Tests if the given value <code>elem</code> is a member of this list.
+  /** Tests if the given value <code>elem</code> is a member of this iterator.
    *
    *  @param elem element whose membership has to be tested.
-   *  @return     <code>true</code> iff there is an element of this list which
+   *  @return     <code>true</code> iff there is an element of this iterator which
    *              is equal (w.r.t. <code>==</code>) to <code>elem</code>.
    */
   def contains(elem: Any): Boolean = exists { x => x == elem }
@@ -392,13 +419,13 @@ trait Iterator[+A] {
     res
   }
 
-  /** Combines the elements of this list together using the binary
+  /** Combines the elements of this iterator together using the binary
    *  operator <code>op</code>, from left to right, and starting with
    *  the value <code>z</code>.
    *
    *  @return <code>op(... (op(op(z,a<sub>0</sub>),a<sub>1</sub>) ...),
-   *          a<sub>n</sub>)</code> if the list is
-   *          <code>List(a<sub>0</sub>, a<sub>1</sub>, ..., a<sub>n</sub>)</code>.
+   *          a<sub>n</sub>)</code> if the iterator yields elements
+   *          <code>a<sub>0</sub>, a<sub>1</sub>, ..., a<sub>n</sub></code>.
    */
   def foldLeft[B](z: B)(op: (B, A) => B): B = {
     var acc = z
@@ -406,13 +433,13 @@ trait Iterator[+A] {
     acc
   }
 
-  /** Combines the elements of this list together using the binary
-   *  operator <code>op</code>, from rigth to left, and starting with
+  /** Combines the elements of this iterator together using the binary
+   *  operator <code>op</code>, from right to left, and starting with
    *  the value <code>z</code>.
    *
    *  @return <code>a<sub>0</sub> op (... op (a<sub>n</sub> op z)...)</code>
-   *          if the list is <code>List(a<sub>0</sub>, a<sub>1</sub>, ...,
-   *          a<sub>n</sub>)</code>.
+   *          if the iterator yields elements <code>a<sub>0</sub>, a<sub>1</sub>, ...,
+   *          a<sub>n</sub></code>.
    */
   def foldRight[B](z: B)(op: (A, B) => B): B = {
     def fold(z: B): B = if (hasNext) op(next, fold(z)) else z
@@ -420,27 +447,57 @@ trait Iterator[+A] {
   }
 
   /** Similar to <code>foldLeft</code> but can be used as
-   *  an operator with the order of list and zero arguments reversed.
+   *  an operator with the order of iterator and zero arguments reversed.
    *  That is, <code>z /: xs</code> is the same as <code>xs foldLeft z</code>.
    *
-   *  @param z the left argument of the first application of <code>f</code>
+   *  @param z the left argument of the first application of <code>op</code>
    *           (evaluation occurs from left to right).
-   *  @param f the applied function.
+   *  @param op the applied operator.
    *  @return  the result value
    *  @see     <code><a href="#foldLeft">foldLeft</a></code>.
    */
-  def /:[B](z: B)(f: (B, A) => B): B = foldLeft(z)(f)
+  def /:[B](z: B)(op: (B, A) => B): B = foldLeft(z)(op)
 
   /** An alias for <code>foldRight</code>.
    *  That is, <code>xs :\ z</code> is the same as <code>xs foldRight z</code>.
    *
-   *  @param z the right argument of the first application of <code>f</code>
+   *  @param z the right argument of the first application of <code>op</code>
    *           (evaluation occurs from right to left).
-   *  @param f the applied function.
+   *  @param op the applied operator.
    *  @return  the result value.
    *  @see     <code><a href="#foldRight">foldRight</a></code>.
    */
-  def :\[B](z: B)(f: (A, B) => B): B = foldRight(z)(f)
+  def :\[B](z: B)(op: (A, B) => B): B = foldRight(z)(op)
+
+  /** Combines the elements of this iterator together using the binary
+   *  operator <code>op</code>, from left to right
+   *  @param op  The operator to apply
+   *  @return <code>op(... op(a<sub>0</sub>,a<sub>1</sub>), ..., a<sub>n</sub>)</code>
+      if the iterator yields elements
+   *          <code>a<sub>0</sub>, a<sub>1</sub>, ..., a<sub>n</sub></code>.
+   *  @throws Predef.UnsupportedOperationException if the iterator is empty.
+   */
+  def reduceLeft[B >: A](op: (B, B) => B): B = {
+    if (hasNext) foldLeft[B](next)(op)
+    else throw new UnsupportedOperationException("empty.reduceLeft")
+  }
+
+  /** Combines the elements of this iterator together using the binary
+   *  operator <code>op</code>, from right to left
+   *  @param op  The operator to apply
+   *
+   *  @return <code>a<sub>0</sub> op (... op (a<sub>n-1</sub> op a<sub>n</sub>)...)</code>
+   *          if the iterator yields elements <code>a<sub>0</sub>, a<sub>1</sub>, ...,
+   *          a<sub>n</sub></code>.
+
+   *  @throws Predef.UnsupportedOperationException if the iterator is empty.
+   */
+  def reduceRight[B >: A](op: (B, B) => B): B = {
+    if (!hasNext) throw new UnsupportedOperationException("empty.reduceRight")
+    val x = next
+    if (hasNext) op(x, reduceRight(op))
+    else x
+  }
 
   /** Returns a buffered iterator from this iterator.
    */
@@ -511,19 +568,23 @@ trait Iterator[+A] {
    *
    *  @param  xs    the array to fill.
    *  @param  start the starting index.
-   *  @return       the given array <code>xs</code> filled with the elements
-   *                of this iterator.
    *  @pre          the array must be large enough to hold all elements.
    */
-  def copyToArray[B >: A](xs: Array[B], start: Int): Array[B] = {
+  def copyToArray[B >: A](xs: Array[B], start: Int): Unit = {
     var i = start
     while (hasNext) {
       xs(i) = next
       i = i + 1
     }
-    xs
   }
 
+  /** Copy all elements to a buffer
+   *  @param   The buffer to which elements are copied
+   *  @return  The buffer to which elements are copied
+   */
+  def copyToBuffer[B >: A](dest: Buffer[B]): Unit =
+    while (hasNext) dest += next
+
   /** Transform this iterator into a list of all elements.
    *
    *  @return  a list which enumerates all elements of this iterator.
@@ -535,11 +596,4 @@ trait Iterator[+A] {
     }
     res.toList
   }
-
-  /** Transforms the elements of this iterator into a string, thereby destroying it.
-   *  Has the same effect as toList.mkString(start,sep,end)
-   */
-  def mkString(start: String, sep: String, end: String): String =
-    toList.mkString(start, sep, end)
-
 }
diff --git a/src/library/scala/List.scala b/src/library/scala/List.scala
index 362b2744ff..e03f39bc63 100644
--- a/src/library/scala/List.scala
+++ b/src/library/scala/List.scala
@@ -525,11 +525,12 @@ sealed abstract class List[+a] extends Seq[a] {
    *  @throws Predef.UnsupportedOperationException if the list is empty.
    */
   def last: a =
-    if (isEmpty) throw new UnsupportedOperationException("Nil.last")
+    if (isEmpty) throw new Predef.NoSuchElementException("Nil.last")
     else if (tail.isEmpty) head
     else tail.last
 
-  /** Returns the <code>n</code> first elements of this list.
+  /** Returns the <code>n</code> first elements of this list, or else the whole
+   *  list, if it has less than <code>n</code> elements.
    *
    *  @param n the number of elements to take.
    *  @return the <code>n</code> first elements of this list.
@@ -547,6 +548,7 @@ sealed abstract class List[+a] extends Seq[a] {
   }
 
   /** Returns the list without its <code>n</code> first elements.
+   *  If this list has less than <code>n</code> elements, the empty list is returned.
    *
    *  @param n the number of elements to drop.
    *  @return the list without its <code>n</code> first elements.
@@ -607,7 +609,7 @@ sealed abstract class List[+a] extends Seq[a] {
    *  @return  the longest prefix of this list whose elements satisfy
    *           the predicate <code>p</code>.
    */
-  def takeWhile(p: a => Boolean): List[a] = {
+  override def takeWhile(p: a => Boolean): List[a] = {
     val b = new ListBuffer[a]
     var these = this
     while (!these.isEmpty && p(these.head)) {
@@ -624,7 +626,7 @@ sealed abstract class List[+a] extends Seq[a] {
    *  @return  the longest suffix of the list whose first element
    *           does not satisfy the predicate <code>p</code>.
    */
-  def dropWhile(p: a => Boolean): List[a] =
+  override def dropWhile(p: a => Boolean): List[a] =
     if (isEmpty || !p(head)) this
     else tail dropWhile p;
 
@@ -664,7 +666,7 @@ sealed abstract class List[+a] extends Seq[a] {
    *  @param f function to apply to each element.
    *  @return <code>[f(a0), ..., f(an)]</code> if this list is <code>[a0, ..., an]</code>.
    */
-  def map[b](f: a => b): List[b] = {
+  override def map[b](f: a => b): List[b] = {
     val b = new ListBuffer[b]
     var these = this
     while (!these.isEmpty) {
@@ -705,10 +707,10 @@ sealed abstract class List[+a] extends Seq[a] {
   /** Returns all the elements of this list that satisfy the
    *  predicate <code>p</code>. The order of the elements is preserved.
    *
-   *  @param p the redicate used to filter the list.
+   *  @param p the predicate used to filter the list.
    *  @return the elements of this list satisfying <code>p</code>.
    */
-  def filter(p: a => Boolean): List[a] = {
+  override def filter(p: a => Boolean): List[a] = {
     // return same list if all elements satisfy p
     var these = this
     while (!these.isEmpty && p(these.head)) {
@@ -874,15 +876,6 @@ sealed abstract class List[+a] extends Seq[a] {
     false
   }
 
-  /** Tests if the given value <code>elem</code> is a member of this
-   *  iterable object.
-   *
-   *  @param elem element whose membership has to be tested.
-   *  @return     <code>true</code> iff there is an element of this list
-   *              which is equal (w.r.t. <code>==</code>) to <code>elem</code>.
-   */
-  def contains(elem: Any): boolean = exists (.==(elem))
-
   /** Find and return the first element of the list satisfying a
    *  predicate, if any.
    *
@@ -918,7 +911,7 @@ sealed abstract class List[+a] extends Seq[a] {
   }
 
   /** Combines the elements of this list together using the binary
-   *  function <code>f</code>, from rigth to left, and starting with
+   *  function <code>f</code>, from right to left, and starting with
    *  the value <code>z</code>.
    *
    *  @return <code>f(a<sub>0</sub>, f(a<sub>1</sub>, f(..., f(a<sub>n</sub>, z)...)))</code>
@@ -929,27 +922,30 @@ sealed abstract class List[+a] extends Seq[a] {
     case x :: xs => f(x, xs.foldRight(z)(f))
   }
 
-  /** <p>
-   *   Example:
-   *  </p>
-   *  <pre>
-   *    val xs = List(1, 2, 3, 4)
-   *    0 :: xs reduceLeft ((x:int, y:int) => x + y) = 10 //sum
-   *    1 :: xs reduceLeft ((x:int, y:int) => x * y) = 24 //prod</pre>
-   *
-   *  @return ...
+  /** Combines the elements of this list together using the binary
+   *  operator <code>op</code>, from left to right
+   *  @param op  The operator to apply
+   *  @return <code>op(... op(a<sub>0</sub>,a<sub>1</sub>), ..., a<sub>n</sub>)</code>
+      if the list has elements
+   *          <code>a<sub>0</sub>, a<sub>1</sub>, ..., a<sub>n</sub></code>.
    *  @throws Predef.UnsupportedOperationException if the list is empty.
    */
-  def reduceLeft[b >: a](f: (b, b) => b): b = this match {
+  override def reduceLeft[b >: a](f: (b, b) => b): b = this match {
     case Nil => throw new UnsupportedOperationException("Nil.reduceLeft")
     case x :: xs => ((xs: List[b]) foldLeft (x: b))(f)
   }
 
-  /**
-   *  @return ...
+  /** Combines the elements of this list together using the binary
+   *  operator <code>op</code>, from right to left
+   *  @param op  The operator to apply
+   *
+   *  @return <code>a<sub>0</sub> op (... op (a<sub>n-1</sub> op a<sub>n</sub>)...)</code>
+   *          if the list has elements <code>a<sub>0</sub>, a<sub>1</sub>, ...,
+   *          a<sub>n</sub></code>.
+   *
    *  @throws Predef.UnsupportedOperationException if the list is empty.
    */
-  def reduceRight[b >: a](f: (b, b) => b): b = this match {
+  override def reduceRight[b >: a](f: (b, b) => b): b = this match {
     case Nil => throw new UnsupportedOperationException("Nil.reduceRight")
     case x :: Nil => x: b
     case x :: xs => f(x, xs reduceRight f)
@@ -962,41 +958,40 @@ sealed abstract class List[+a] extends Seq[a] {
    *  @return  <code>f(a<sub>0</sub>) ::: ... ::: f(a<sub>n</sub>)</code> if
    *           this list is <code>[a<sub>0</sub>, ..., a<sub>n</sub>]</code>.
    */
-  def flatMap[b](f: a => List[b]): List[b] = {
+  override def flatMap[b](f: a => Iterable[b]): List[b] = {
     val b = new ListBuffer[b]
     var these = this
     while (!these.isEmpty) {
-      var those = f(these.head)
-      while (!those.isEmpty) {
-        b += those.head
-        those = those.tail
+      var those = f(these.head).elements
+      while (those.hasNext) {
+        b += those.next
       }
       these = these.tail
     }
     b.toList
   }
 
-  /** <p>
-   *    Reverses the elements of this list. Example:
-   *  </p>
-   *  <pre>
-   *    List(1, 2, 3) reverse = List(3, 2, 1)</pre>
-   *
-   *  @return the elements of this list in reverse order.
+  /** A list consisting of all elements of this list in reverse order.
    */
-  def reverse: List[a] =
-    foldLeft(Nil : List[a])((xs, x) => x :: xs);
+  override def reverse: List[a] = {
+    var result: List[a] = Nil
+    var these = this
+    while (!these.isEmpty) {
+      result = these.head :: result
+      these = these.tail
+    }
+    result
+  }
 
   /** Returns a list formed from this list and the specified list
    *  <code>that</code> by associating each element of the former with
    *  the element at the same position in the latter.
+   *  If one of the two lists is longer than the other, its remaining elements are ignored.
    *
-   *  @param that list <code>that</code> must have the same length as the
-   *              self list.
-   *  @return     <code>[(a<sub>0</sub>,b<sub>0</sub>), ...,
-   *              (a<sub>n</sub>,b<sub>n</sub>)]</code> when
-   *              <code>[a<sub>0</sub>, ..., a<sub>n</sub>]
-   *              zip [b<sub>0</sub>, ..., b<sub>n</sub>]</code> is invoked.
+   *  @return     <code>List({a<sub>0</sub>,b<sub>0</sub>}, ...,
+   *              {a<sub>min(m,n)</sub>,b<sub>min(m,n)</sub>})</code> when
+   *              <code>List(a<sub>0</sub>, ..., a<sub>m</sub>)
+   *              zip List(b<sub>0</sub>, ..., b<sub>n</sub>)</code> is invoked.
    */
   def zip[b](that: List[b]): List[Pair[a,b]] = {
     val b = new ListBuffer[Pair[a, b]]
@@ -1010,15 +1005,12 @@ sealed abstract class List[+a] extends Seq[a] {
     b.toList
   }
 
-   /** Returns a list that pairs each element of this list
-    *  with its index, counting from 0.
-    *
-    *  @param start the index of the first element
-    *  @return      an iterator yielding <code>(a<sub>0</sub>,0),
-    *               (a<sub>0</sub>,1)...</code>
-    *               where <code>a<sub>i</sub></code> are the elements from
-    *               this iterator.
-    */
+  /** Returns a list that pairs each element of this list
+   *  with its index, counting from 0.
+   *
+   *  @return      the list <code>List({a<sub>0</sub>,0}, {a<sub>1</sub>,1}...)</code>
+   *               where <code>a<sub>i</sub></code> are the elements of this list.
+   */
   def zipWithIndex = {
     val b = new ListBuffer[Pair[a,int]]
     var these = this
@@ -1045,9 +1037,9 @@ sealed abstract class List[+a] extends Seq[a] {
    *  @param thatElem element <code>thatElem</code> is used to fill up the
    *                  resulting list if <code>that</code> is shorter than
    *                  the self list
-   *  @return         <code>[(a<sub>0</sub>,b<sub>0</sub>), ...,
-   *                  (a<sub>n</sub>,b<sub>n</sub>), (elem,b<sub>n+1</sub>),
-   *                  ..., (elem,b<sub>m</sub>)]</code>
+   *  @return         <code>List({a<sub>0</sub>,b<sub>0</sub>}, ...,
+   *                  {a<sub>n</sub>,b<sub>n</sub>}, {elem,b<sub>n+1</sub>},
+   *                  ..., {elem,b<sub>m</sub>})</code>
    *                  when <code>[a<sub>0</sub>, ..., a<sub>n</sub>] zip
    *                  [b<sub>0</sub>, ..., b<sub>m</sub>]</code> is
    *                  invoked where <code>m &gt; n</code>.
diff --git a/src/library/scala/Option.scala b/src/library/scala/Option.scala
index ee0e32e636..78f501fa9f 100644
--- a/src/library/scala/Option.scala
+++ b/src/library/scala/Option.scala
@@ -42,17 +42,17 @@ sealed abstract class Option[+A] extends Iterable[A] with Product {
     case Some(x) => x
   }
 
-  def map[B](f: A => B): Option[B] = this match {
+  override def map[B](f: A => B): Option[B] = this match {
     case None => None
     case Some(x) => Some(f(x))
   }
 
-  def flatMap[B](f: A => Option[B]): Option[B] = this match {
+  override def flatMap[B](f: A => Iterable[B]): Iterable[B] = this match {
     case None => None
     case Some(x) => f(x)
   }
 
-  def filter(p: A => Boolean): Option[A] = this match {
+  override def filter(p: A => Boolean): Option[A] = this match {
     case None => None
     case Some(x) => if (p(x)) Some(x) else None
   }
diff --git a/src/library/scala/Predef.scala b/src/library/scala/Predef.scala
index 1422aa6d0d..17128b6096 100644
--- a/src/library/scala/Predef.scala
+++ b/src/library/scala/Predef.scala
@@ -39,6 +39,7 @@ object Predef {
   type AllRef = Null
 
   type String = java.lang.String
+  type StringBuilder = compat.StringBuilder
   type Class = java.lang.Class
 
   type Throwable = java.lang.Throwable
@@ -60,6 +61,7 @@ object Predef {
 
   type Function[-a,+b] = Function1[a,b]
 
+
   // errors and asserts -------------------------------------------------
 
   def error(message: String): Nothing = throw new Error(message)
@@ -99,11 +101,10 @@ object Predef {
   type Triple[+a, +b, +c] = Tuple3[a, b, c]
   def Triple[a, b, c](x: a, y: b, z: c) = Tuple3(x, y, z)
 
-  type &: [+a, +b] = Tuple2[a, b]
-  class SndOfPair[+b](y: b) {
-    def &: [a](x: a): Tuple2[a, b] = Tuple2(x, y)
+  class ArrowAssoc[a](x: a) {
+    def -> [b](y: b): Tuple2[a, b] = Tuple2(x, y)
   }
-  implicit def any2sndOfPair[b](x: b): SndOfPair[b] = new SndOfPair(x)
+  implicit def any2ArrowAssoc[a](x: a): ArrowAssoc[a] = new ArrowAssoc(x)
 
   def Tuple[a1](x1: a1) = Tuple1(x1)
   def Tuple[a1, a2](x1: a1, x2: a2) = Tuple2(x1, x2)
diff --git a/src/library/scala/Seq.scala b/src/library/scala/Seq.scala
index 85a3b08f60..df8ba7e35c 100644
--- a/src/library/scala/Seq.scala
+++ b/src/library/scala/Seq.scala
@@ -11,11 +11,18 @@
 
 package scala
 
-
-import Predef.IllegalArgumentException
+import Predef.{IllegalArgumentException, NoSuchElementException}
+import collection.mutable.{ArrayBuffer}
 
 object Seq {
 
+  /** The empty sequence */
+  val empty = new Seq[Nothing] {
+    def length = 0
+    def apply(i: Int): Nothing = throw new NoSuchElementException("empty sequence")
+    def elements = Iterator.empty
+  }
+
   def unapplySeq[A](x:Any): Option[Tuple1[Seq[A]]] =
     if(x.isInstanceOf[Seq[A]]) Some(Tuple1(x.asInstanceOf[Seq[A]])) else None
 
@@ -64,23 +71,19 @@ trait Seq[+A] extends AnyRef with PartialFunction[Int, A] with Iterable[A] {
    */
   def length: Int
 
-  /** Returns true is length == 0
-   *
-   *  @return the sequence length.
+  /** Returns true if length == 0
    */
   def isEmpty: Boolean = { length == 0 }
 
-  /** Returns the concatenation of two sequences.
+  /** Appends two iterable objects
    *
-   *  @return concatenation of this sequence with argument
-   *  @author buraq
+   *  @return the new iterable object
    */
-  def concat[B >: A](that: Seq[B]): Seq[B] = new Seq[B] {
-    def length = Seq.this.length + that.length
-    def elements: Iterator[B] = Seq.this.elements.append(that.elements)
-    def apply(i: Int) =
-      if (Seq.this.isDefinedAt(i)) Seq.this.apply(i)
-      else that.apply(i - Seq.this.length)
+  override def concat [B >: A](that: Iterable[B]): Seq[B] = {
+    val buf = new ArrayBuffer[B]
+    this copyToBuffer buf
+    that copyToBuffer buf
+    buf
   }
 
   /** Is this partial function defined for the index <code>x</code>?
@@ -109,51 +112,122 @@ trait Seq[+A] extends AnyRef with PartialFunction[Int, A] with Iterable[A] {
     if (found) i else -1;
   }
 
-  /** Returns the sub-sequence starting from index <code>n</code>.
+  /** Returns the sequence resulting from applying the given function <code>f</code> to each
+   *  element of this sequence.
+   *
+   *  @param f function to apply to each element.
+   *  @return <code>f(a0), ..., f(an)</code> if this sequence is <code>a0, ..., an</code>.
+   */
+  override def map[B](f: A => B): Seq[B] = {
+    // todo: malformed scala signature suing build when replaced by
+    // super.map(f).asInstanceOf[Seq[B2]]
+    val buf = new ArrayBuffer[B]
+    val elems = elements
+    while (elems.hasNext) buf += f(elems.next)
+    buf
+  }
+
+  /** Applies the given function <code>f</code> to each element of
+   *  this sequence, then concatenates the results.
+   *
+   *  @param f the function to apply on each element.
+   *  @return  <code>f(a<sub>0</sub>) ::: ... ::: f(a<sub>n</sub>)</code> if
+   *           this sequence is <code>a<sub>0</sub>, ..., a<sub>n</sub></code>.
+   */
+  override def flatMap[B](f: A => Iterable[B]): Seq[B] = {
+    val buf = new ArrayBuffer[B]
+    val elems = elements
+    while (elems.hasNext) f(elems.next) copyToBuffer buf
+    buf
+  }
+
+  /** Returns all the elements of this sequence that satisfy the
+   *  predicate <code>p</code>. The order of the elements is preserved.
+   *
+   *  @param p the predicate used to filter the list.
+   *  @return the elements of this list satisfying <code>p</code>.
+   */
+  override def filter(p: A => Boolean): Seq[A] = super.filter(p).asInstanceOf[Seq[A]]
+
+  /** Returns a sequence consisting only over the first <code>n</code>
+   *  elements of this sequence, or else the whole sequence, if it has less
+   *  than <code>n</code> elements.
+   *
+   *  @param n the number of elements to take
+   *  @return  the new sequence
+   */
+  override def take(n: Int): Seq[A] = super.take(n).asInstanceOf[Seq[A]]
+
+  /** Returns this sequence without its <code>n</code> first elements
+   *  If this sequence has less than <code>n</code> elements, the empty sequence is returned.
    *
-   *  @param n ...
+   *  @param n the number of elements to drop
+   *  @return  the new sequence
    */
-  def take(n: Int): Seq[A] = subseq(0, n)
+  override def drop(n: Int): Seq[A] = super.drop(n).asInstanceOf[Seq[A]]
 
-  /** Returns a new sub-sequence that drops the first <code>n</code>
-   *  elements of this sequence.
+  /** Returns the longest prefix of this sequence whose elements satisfy
+   *  the predicate <code>p</code>.
    *
-   *  @param n ...
+   *  @param p the test predicate.
+   *  @return  the longest prefix of this sequence whose elements satisfy
+   *           the predicate <code>p</code>.
    */
-  def drop(n: Int): Seq[A] = subseq(n, length - n)
+  override def takeWhile(p: A => Boolean): Seq[A] = super.takeWhile(p).asInstanceOf[Seq[A]]
+
+  /** Returns the longest suffix of this sequence whose first element
+   *  does not satisfy the predicate <code>p</code>.
+   *
+   *  @param p the test predicate.
+   *  @return  the longest suffix of the sequence whose first element
+   *           does not satisfy the predicate <code>p</code>.
+   */
+  override def dropWhile(p: A => Boolean): Seq[A] = super.dropWhile(p).asInstanceOf[Seq[A]]
+
+  /** A sequence consisting of all elements of this sequence in reverse order.
+   */
+  def reverse: Seq[A] = {
+    var result: List[A] = Nil
+    val elems = elements
+    while (elems.hasNext) result = elems.next :: result
+    result
+  }
+
+  /** Tests if the given value <code>elem</code> is a member of this
+   *  sequence.
+   *
+   *  @param elem element whose membership has to be tested.
+   *  @return     <code>true</code> iff there is an element of this sequence
+   *              which is equal (w.r.t. <code>==</code>) to <code>elem</code>.
+   */
+  def contains(elem: Any): Boolean = exists (.==(elem))
 
   /** Returns a subsequence starting from index <code>from</code>
   *  consisting of <code>len</code> elements.
   */
-  def subseq(from: Int, len: Int): Seq[A] =
-    if ((from + len) <= length) new Seq[A] {
-      def apply(n: Int): A = Seq.this.apply(n + from);
-      def length: Int = len;
-      def elements: Iterator[A] = new Iterator[A] {
-        var i = from;
-        def hasNext = (i < (from + len));
-        def next = {
-          val res = Seq.this.apply(i);
-          i = i + 1;
-          res
-        }
-      }
-    } else
-      throw new IllegalArgumentException("cannot create subsequence for "+from+","+len);
+  def slice(from: Int, len: Int): Seq[A] = this.drop(from).take(len)
 
-  /** Converts this sequence to a fresh Array */
-  def toArray[B >: A]: Array[B] =
-    elements.copyToArray(new Array[B](length), 0)
+  /** Returns a subsequence starting from index <code>from</code>
+  *   consisting of <code>len</code> elements.
+  *   @deprecated; use slice instead
+  */
+  [deprecated] def subseq(from: Int, end: Int): Seq[A] = slice(from, end - from)
+
+  /** Converts this sequence to a fresh Array with <code>length</code> elements */
+  def toArray[B >: A]: Array[B] = {
+    val result = new Array[B](length)
+    copyToArray(result, 0)
+    result
+  }
 
   /** Fills the given array <code>xs</code> with the elements of
    *  this sequence starting at position <code>start</code>.
    *
    *  @param  xs the array to fill.
    *  @param  start starting index.
-   *  @return the given array <code>xs</code> filled with this list.
+   *  @pre    the array must be large enough to hold all elements.
    */
-  def copyToArray[B >: A](xs: Array[B], start: Int): Array[B] =
-    elements.copyToArray(xs, start)
+  def copyToArray[B >: A](xs: Array[B], start: Int): Unit = elements.copyToArray(xs, start)
 
   /** Customizes the <code>toString</code> method.
    *
@@ -161,32 +235,6 @@ trait Seq[+A] extends AnyRef with PartialFunction[Int, A] with Iterable[A] {
    */
   override def toString() = mkString(stringPrefix+"(", ",", ")")
 
-  /** Returns a string representation of this sequence. The resulting string
-   *  begins with the string <code>start</code> and is finished by the string
-   *  <code>end</code>. Inside, the string representations of elements (w.r.t.
-   *  the method <code>toString()</code>) are separated by the string
-   *  <code>sep</code>.
-   *  <p/>
-   *  Ex: <br/>
-   *  <code>List(1, 2, 3).mkString("(", "; ", ")") = "(1; 2; 3)"</code>
-   *
-   *  @param start starting string.
-   *  @param sep separator string.
-   *  @param end ending string.
-   *  @return a string representation of this sequence.
-   */
-  def mkString(start: String, sep: String, end: String): String = {
-    val buf = new compat.StringBuilder()
-    buf.append(start)
-    val elems = elements
-    if (elems.hasNext) buf.append(elems.next)
-    while (elems.hasNext) {
-      buf.append(sep); buf.append(elems.next)
-    }
-    buf.append(end)
-    buf.toString
-  }
-
   /** Defines the prefix of the string representation.
    */
   protected def stringPrefix: String = "Seq"
diff --git a/src/library/scala/SeqProxy.scala b/src/library/scala/SeqProxy.scala
index f43da07aaf..d346060e50 100644
--- a/src/library/scala/SeqProxy.scala
+++ b/src/library/scala/SeqProxy.scala
@@ -12,88 +12,32 @@
 package scala
 
 
-/** Class <code>Seq[A]</code> represents finite sequences of elements
- *  of type <code>A</code>.
+/** This class implements a proxy for sequences. It forwards
+ *  all calls to a different sequence object.
  *
  *  @author  Martin Odersky
  *  @author  Matthias Zenger
- *  @version 1.0, 16/07/2003
+ *  @version 2.0, 31/12/2006
  */
 trait SeqProxy[+A] extends Seq[A] with IterableProxy[A] {
 
   def self: Seq[A]
 
-  /** Returns the length of the sequence.
-   *
-   *  @return the sequence length.
-   */
-  def length: Int = self.length
-
-  /** Access element number <code>n</code>.
-   *
-   *  @return  the element at index <code>n</code>.
-   */
-  def apply(n: Int): A = self.apply(n)
-
-  /** Is this partial function defined for the index <code>x</code>?
-   *
-   *  @return true, iff <code>x</code> is a legal sequence index.
-   */
-  override def isDefinedAt(y: Int): Boolean = self.isDefinedAt(y)
-
-  /** Returns the index of the first occurence of the specified
-   *  object in this sequence.
-   *
-   *  @param  elem  element to search for.
-   *  @return the index in this sequence of the first occurence of the
-   *          specified element, or -1 if the sequence does not contain
-   *          this element.
-   */
-  override def indexOf[B >: A](elem: B): Int = self.indexOf(elem)
-
-  /** Returns the index of the last occurence of the specified
-   *  element in this sequence, or -1 if the sequence does not
-   *  contain this element.
-   *
-   *  @param  elem   element to search for.
-   *  @return the index in this sequence of the last occurence of the
-   *          specified  element, or -1 if the sequence does not contain
-   *          this element.
-   */
-  override def lastIndexOf[B >: A](elem: B): Int = self.lastIndexOf(elem)
-
-  /** Returns the sub-sequence starting from index <code>n</code>.
-   *
-   *  @param n ...
-   *  @return ...
-   */
-  override def take(n: Int): Seq[A] = self.take(n)
-
-  /** Returns a new sub-sequence that drops the first <code>n</code>
-   *  elements of this sequence.
-   *
-   *  @param n ...
-   *  @return ...
-   */
-  override def drop(n: Int): Seq[A] = self.drop(n)
-
-  /** Returns a subsequence starting from index <code>from</code>
-   *  consisting of <code>len</code> elements.
-   *
-   *  @param from ...
-   *  @param len ...
-   */
-  override def subseq(from: Int, len: Int): Seq[A] = self.subseq(from, len)
-
-  /** Fills the given array <code>xs</code> with the elements of
-   *  this sequence starting at position <code>start</code>.
-   *
-   *  @param  xs the array to fill.
-   *  @param  start starting index.
-   *  @return the given array <code>xs</code> filled with the elements
-   *          of this sequence.
-   */
-  override def copyToArray[B >: A](xs: Array[B], start: Int): Array[B] =
-    self.copyToArray(xs, start)
-
+  override def length: Int = self.length
+  override def isEmpty: Boolean = self.isEmpty
+  override def concat [B >: A](that: Iterable[B]): Seq[B] = self concat that
+  override def isDefinedAt(x: Int): Boolean = self isDefinedAt x
+  override def lastIndexOf[B >: A](elem: B): Int = self lastIndexOf elem
+  override def map[B](f: A => B): Seq[B] = self map f
+  override def flatMap[B](f: A => Iterable[B]): Seq[B] = self flatMap f
+  override def filter(p: A => Boolean): Seq[A] = self filter p
+  override def take(n: Int): Seq[A] = self take n
+  override def drop(n: Int): Seq[A] = self drop n
+  override def takeWhile(p: A => Boolean): Seq[A] = self takeWhile p
+  override def dropWhile(p: A => Boolean): Seq[A] = self dropWhile p
+  override def reverse: Seq[A] = self.reverse
+  override def contains(elem: Any): Boolean = self contains elem
+  override def slice(from: Int, len: Int): Seq[A] = self.slice(from, len)
+  override def toArray[B >: A]: Array[B] = self.toArray
+  override def copyToArray[B >: A](xs: Array[B], start: Int): Unit = self.copyToArray(xs, start)
 }
diff --git a/src/library/scala/Stream.scala b/src/library/scala/Stream.scala
index 54bf3ae694..e42947512b 100644
--- a/src/library/scala/Stream.scala
+++ b/src/library/scala/Stream.scala
@@ -13,7 +13,7 @@ package scala
 
 
 import compat.StringBuilder
-import Predef.NoSuchElementException
+import Predef.{NoSuchElementException, UnsupportedOperationException}
 
 /**
  * The object <code>Stream</code> provides helper functions
@@ -24,13 +24,18 @@ import Predef.NoSuchElementException
  */
 object Stream {
 
+  /** The empty stream */
   val empty: Stream[Nothing] = new Stream[Nothing] {
     override def isEmpty = true
     def head: Nothing = throw new NoSuchElementException("head of empty stream")
-    def tail: Stream[Nothing] = throw new NoSuchElementException("tail of empty stream")
-    def printElems(buf: StringBuilder, prefix: String): StringBuilder = buf
+    def tail: Stream[Nothing] = throw new UnsupportedOperationException("tail of empty stream")
+    protected def addDefinedElems(buf: StringBuilder, prefix: String): StringBuilder = buf
   }
 
+  /** A stream consisting of a given first element and remaining elements
+   *  @param hd   The first element of the result stream
+   *  @param tl   The remaining elements of the result stream
+   */
   def cons[a](hd: a, tl: => Stream[a]) = new Stream[a] {
     override def isEmpty = false
     def head = hd
@@ -40,17 +45,29 @@ object Stream {
       if (!tlDefined) { tlVal = tl; tlDefined = true }
       tlVal
     }
-    def printElems(buf: StringBuilder, prefix: String): StringBuilder = {
+    protected def addDefinedElems(buf: StringBuilder, prefix: String): StringBuilder = {
       val buf1 = buf.append(prefix).append(hd)
-      if (tlDefined) tlVal.printElems(buf1, ", ") else buf1 append ", ?"
+      if (tlDefined) tlVal.addDefinedElems(buf1, ", ") else buf1 append ", ?"
     }
   }
 
+  /** A stream containing all elements of a given iterator, in the order they are produced.
+   *  @param it   The iterator producing the stream's elements
+   */
   def fromIterator[a](it: Iterator[a]): Stream[a] =
     if (it.hasNext) cons(it.next, fromIterator(it)) else empty
 
-  def concat[a](xs: Seq[Stream[a]]): Stream[a] = concat(xs.elements)
+  /** The concatenation of a sequence of streams
+   */
+  def concat[a](xs: Iterable[Stream[a]]): Stream[a] = concat(xs.elements)
+
+  /** The concatenation of all given streams
+   */
+  def concat[a](s1: Stream[a], s2: Stream[a], ss: Stream[a]*): Stream[a] =
+    s1 append s2 append concat(ss.elements)
 
+  /** The concatenation of all streams returned by an iterator
+   */
   def concat[a](xs: Iterator[Stream[a]]): Stream[a] =
     if (xs.hasNext) xs.next append concat(xs)
     else empty
@@ -148,27 +165,50 @@ object Stream {
  */
 trait Stream[+a] extends Seq[a] {
 
+  /** is this stream empty? */
   override def isEmpty: Boolean
+
+  /** The first element of this stream
+   *  @throws Predef.NoSuchElementException if the stream is empty.
+   */
   def head: a
+
+  /** A stream consisting of the remaining elements of this stream after the first one.
+   *  @throws Predef.UnsupportedOperationException if the stream is empty.
+   */
   def tail: Stream[a]
 
+  /** The length of this stream */
   def length: Int = if (isEmpty) 0 else tail.length + 1
 
+  /** The stream resulting from the concatenation of thsi stream with the argument stream.
+   *  @param rest   The stream that gets appended to this stream
+   */
   def append[b >: a](rest: => Stream[b]): Stream[b] =
     if (isEmpty) rest
     else Stream.cons(head, tail.append(rest))
 
+  /** An iterator returning the elements of this stream one by one.
+   */
   def elements: Iterator[a] = new Iterator[a] {
     var current = Stream.this
     def hasNext: boolean = !current.isEmpty
     def next: a = { val result = current.head; current = current.tail; result }
   }
 
+  /** The stream without its last element.
+   *  @throws Predef.UnsupportedOperationException if the stream is empty.
+   */
   def init: Stream[a] =
-    if (isEmpty) throw new NoSuchElementException("Stream.empty.init")
+    if (isEmpty) throw new UnsupportedOperationException("Stream.empty.init")
     else if (tail.isEmpty) Stream.empty
     else Stream.cons(head, tail.init)
 
+  /** Returns the last element of this stream.
+   *
+   *  @return the last element of the stream.
+   *  @throws Predef.NoSuchElementException if the stream is empty.
+   */
   def last: a =
     if (isEmpty) throw new NoSuchElementException("Stream.empty.last")
     else {
@@ -179,10 +219,31 @@ trait Stream[+a] extends Seq[a] {
       loop(this)
     }
 
+  /** Returns the <code>n</code>-th element of this stream. The first element
+   *  (head of the stream) is at position 0.
+   *
+   *  @param n index of the element to return
+   *  @return  the element at position <code>n</code> in this stream.
+   *  @throws Predef.NoSuchElementException if the stream is too short.
+   */
+  def apply(n: Int) = drop(n).head
+
+  /** Returns the <code>n</code> first elements of this stream, or else the whole
+   *  stream, if it has less than <code>n</code> elements.
+   *
+   *  @param n the number of elements to take.
+   *  @return the <code>n</code> first elements of this stream.
+   */
   override def take(n: Int): Stream[a] =
     if (n == 0) Stream.empty
     else Stream.cons(head, tail.take(n-1))
 
+  /** Returns the stream without its <code>n</code> first elements.
+   *  If the stream has less than <code>n</code> elements, the empty stream is returned.
+   *
+   *  @param n the number of elements to drop.
+   *  @return the stream without its <code>n</code> first elements.
+   */
   override def drop(n: Int): Stream[a] = {
     def loop(s: Stream[a], n: Int): Stream[a] =
       if (n == 0) s
@@ -190,32 +251,61 @@ trait Stream[+a] extends Seq[a] {
     loop(this, n)
   }
 
-  def apply(n: Int) = drop(n).head
-  def at(n: Int) = drop(n).head
-
-  def takeWhile(p: a => Boolean): Stream[a] =
+  /** Returns the longest prefix of this stream whose elements satisfy
+   *  the predicate <code>p</code>.
+   *
+   *  @param p the test predicate.
+   *  @return  the longest prefix of this stream whose elements satisfy
+   *           the predicate <code>p</code>.
+   */
+  override def takeWhile(p: a => Boolean): Stream[a] =
     if (isEmpty || !p(head)) Stream.empty
     else Stream.cons(head, tail.takeWhile(p))
 
-  def dropWhile(p: a => Boolean): Stream[a] = {
+  /** Returns the longest suffix of this stream whose first element
+   *  does not satisfy the predicate <code>p</code>.
+   *
+   *  @param p the test predicate.
+   *  @return  the longest suffix of the stream whose first element
+   *           does not satisfy the predicate <code>p</code>.
+   */
+  override def dropWhile(p: a => Boolean): Stream[a] = {
     def loop(s: Stream[a]): Stream[a] =
       if (s.isEmpty || !p(s.head)) this
       else loop(s.tail)
     loop(this)
   }
 
-  def map[b](f: a => b): Stream[b] =
+  /** Returns the stream resulting from applying the given function <code>f</code> to each
+   *  element of this stream.
+   *
+   *  @param f function to apply to each element.
+   *  @return <code>[f(a0), ..., f(an)]</code> if this stream is <code>[a0, ..., an]</code>.
+   */
+  override def map[b](f: a => b): Stream[b] =
     if (isEmpty) Stream.empty
     else Stream.cons(f(head), tail.map(f))
 
-  override def foreach(f: a => unit): unit = {
-    def loop(s: Stream[a]): unit =
+  /** Apply the given function <code>f</code> to each element of this stream
+   *  (while respecting the order of the elements).
+   *
+   *  @param f the treatment to apply to each element.
+   */
+  override def foreach(f: a => Unit) {
+    def loop(s: Stream[a]) {
       if (s.isEmpty) {}
       else { f(s.head); loop(s.tail) }
+    }
     loop(this)
   }
 
-  def filter(p: a => Boolean): Stream[a] = {
+  /** Returns all the elements of this stream that satisfy the
+   *  predicate <code>p</code>. The order of the elements is preserved.
+   *
+   *  @param p the predicate used to filter the stream.
+   *  @return the elements of this stream satisfying <code>p</code>.
+   */
+  override def filter(p: a => Boolean): Stream[a] = {
     def loop(s: Stream[a]): Stream[a] =
       if (s.isEmpty) s
       else if (p(s.head)) Stream.cons(s.head, loop(s.tail))
@@ -223,6 +313,13 @@ trait Stream[+a] extends Seq[a] {
     loop(this)
   }
 
+  /** Tests if the predicate <code>p</code> is satisfied by all elements
+   *  in this stream.
+   *
+   *  @param p the test predicate.
+   *  @return  <code>true</code> iff all elements of this stream satisfy the
+   *           predicate <code>p</code>.
+   */
   override def forall(p: a => Boolean): Boolean = {
     def loop(s: Stream[a]): Boolean = {
       if (s.isEmpty) true
@@ -232,6 +329,13 @@ trait Stream[+a] extends Seq[a] {
     loop(this)
   }
 
+  /** Tests the existence in this stream of an element that satisfies the
+   *  predicate <code>p</code>.
+   *
+   *  @param p the test predicate.
+   *  @return  <code>true</code> iff there exists an element in this stream that
+   *           satisfies the predicate <code>p</code>.
+   */
   override def exists(p: a => Boolean): Boolean = {
     def loop(s: Stream[a]): Boolean = {
       if (s.isEmpty) false
@@ -241,6 +345,14 @@ trait Stream[+a] extends Seq[a] {
     loop(this)
   }
 
+  /** Combines the elements of this stream together using the binary
+   *  function <code>f</code>, from left to right, and starting with
+   *  the value <code>z</code>.
+   *
+   *  @return <code>f(... (f(f(z, a<sub>0</sub>), a<sub>1</sub>) ...),
+   *          a<sub>n</sub>)</code> if the stream is
+   *          <code>[a<sub>0</sub>, a<sub>1</sub>, ..., a<sub>n</sub>]</code>.
+   */
   override def foldLeft[b](z: b)(f: (b, a) => b): b = {
     def loop(s: Stream[a], z: b): b =
       if (s.isEmpty) z
@@ -248,58 +360,91 @@ trait Stream[+a] extends Seq[a] {
     loop(this, z)
   }
 
+  /** Combines the elements of this stream together using the binary
+   *  function <code>f</code>, from rigth to left, and starting with
+   *  the value <code>z</code>.
+   *
+   *  @return <code>f(a<sub>0</sub>, f(a<sub>1</sub>, f(..., f(a<sub>n</sub>, z)...)))</code>
+   *          if the stream is <code>[a<sub>0</sub>, a1, ..., a<sub>n</sub>]</code>.
+   */
   override def foldRight[b](z: b)(f: (a, b) => b): b =
     if (isEmpty) z
     else f(head, tail.foldRight(z)(f))
 
-  def reduceLeft[b >: a](f: (b, b) => b): b =
-    if (isEmpty) throw new NoSuchElementException("Stream.empty.reduceLeft")
-    else ((tail: Stream[b]) foldLeft (head: b))(f)
-
-  def reduceRight[b >: a](f: (b, b) => b): b =
-    if (isEmpty) throw new NoSuchElementException("Stream.empty.reduceRight")
-    else if (tail.isEmpty) head: b
-    else f(head, tail.reduceRight(f))
-
-  def flatMap[b](f: a => Stream[b]): Stream[b] =
+  /** Applies the given function <code>f</code> to each element of
+   *  this stream, then concatenates the results.
+   *
+   *  @param f the function to apply on each element.
+   *  @return  <code>f(a<sub>0</sub>) ::: ... ::: f(a<sub>n</sub>)</code> if
+   *           this stream is <code>[a<sub>0</sub>, ..., a<sub>n</sub>]</code>.
+   */
+  override def flatMap[b](f: a => Iterable[b]): Stream[b] =
     if (isEmpty) Stream.empty
-    else f(head).append(tail.flatMap(f))
+    else Stream.fromIterator(f(head).elements).append(tail.flatMap(f))
 
-  def reverse: Stream[a] =
+  /** A stream consisting of all elements of this stream in reverse order.
+   */
+  override def reverse: Stream[a] =
     foldLeft(Stream.empty: Stream[a])((xs, x) => Stream.cons(x, xs))
 
-  // The following method is not compilable without run-time type
-  // information. It should therefore be left commented-out for
-  // now.
-  //       def toArray: Array[a] = {
-  //         val xs = new Array[a](length)
-  //         copyToArray(xs, 0)
-  //         xs
-  //       }
-
-  override def copyToArray[b >: a](xs: Array[b], start: Int): Array[b] = {
-    def loop(s: Stream[a], start: Int): Array[b] =
-      if (s.isEmpty) xs
-      else { xs(start) = s.head; loop(s.tail, start + 1) }
+  /** Fills the given array <code>xs</code> with the elements of
+   *  this stream starting at position <code>start</code>.
+   *
+   *  @param  xs the array to fill.
+   *  @param  start starting index.
+   *  @pre    the array must be large enough to hold all elements.
+   */
+  override def copyToArray[b >: a](xs: Array[b], start: Int) {
+    def loop(s: Stream[a], start: Int) {
+      if (!xs.isEmpty) { xs(start) = s.head; loop(s.tail, start + 1) }
+    }
     loop(this, start)
   }
 
+  /** Returns a stream formed from this stream and the specified stream
+   *  <code>that</code> by associating each element of the former with
+   *  the element at the same position in the latter.
+   *  If one of the two streams is longer than the other, its remaining elements are ignored.
+   *
+   *  @return     <code>Stream({a<sub>0</sub>,b<sub>0</sub>}, ...,
+   *              {a<sub>min(m,n)</sub>,b<sub>min(m,n)</sub>)}</code> when
+   *              <code>Stream(a<sub>0</sub>, ..., a<sub>m</sub>)
+   *              zip Stream(b<sub>0</sub>, ..., b<sub>n</sub>)</code> is invoked.
+   */
   def zip[b](that: Stream[b]): Stream[Tuple2[a, b]] =
     if (this.isEmpty || that.isEmpty) Stream.empty
     else Stream.cons(Tuple2(this.head, that.head), this.tail.zip(that.tail))
 
+
+  /** Returns a stream that pairs each element of this stream
+   *  with its index, counting from 0.
+   *
+   *  @return      the stream <code>Stream({a<sub>0</sub>,0}, {a<sub>0</sub>,1},...)</code>
+   *               where <code>a<sub>i</sub></code> are the elements of this stream.
+   */
   def zipWithIndex: Stream[Tuple2[a, Int]] =
     zip(Stream.from(0))
 
-  def print: unit = {
-    def loop(s: Stream[a]): unit =
-      if (s.isEmpty) Console.println("Stream.empty")
-      else { Console.print(s.head); Console.print(", "); loop(s.tail) }
+  /** Prints elements of this stream one by one, separated by commas */
+  def print { print(Console.out) }
+  def print(out: java.io.PrintStream) { print(out, ", ") }
+
+  /** Prints elements of this stream one by one, separated by <code>sep</code>
+   *  @param sep   The separator string printed between consecutive elements.
+   */
+  def print(sep: String) { print(Console.out, sep) }
+  def print(out: java.io.PrintStream, sep: String) {
+    def loop(s: Stream[a]) {
+      if (s.isEmpty) out.println("Stream.empty")
+      else { out.print(s.head); out.print(sep); loop(s.tail) }
+    }
     loop(this)
   }
 
+  /** Converts stream to string */
   override def toString() =
-    "Stream(" + printElems(new StringBuilder(), "") + ")"
+    "Stream(" + addDefinedElems(new StringBuilder(), "") + ")"
 
-  def printElems(buf: StringBuilder, prefix: String): StringBuilder
+  /** Write all elements of this string into given string builder */
+  protected def addDefinedElems(buf: StringBuilder, prefix: String): StringBuilder
 }
diff --git a/src/library/scala/collection/BitSet.scala b/src/library/scala/collection/BitSet.scala
index d6607058cf..17ecd1fa6c 100644
--- a/src/library/scala/collection/BitSet.scala
+++ b/src/library/scala/collection/BitSet.scala
@@ -19,10 +19,11 @@ package scala.collection
  *  </p>
  *
  *  @author  Burak Emir, Stephane Micheloud, Nikolay Mihaylov
- *  @version 1.1
+ *  @author  Martin Odersky
+ *  @version 2.0  01/01/2007
  */
 
-abstract class BitSet extends AnyRef with Function1[Int,Boolean] with Set[Int] {
+abstract class BitSet extends Set[Int] {
 
   import compat.Platform.arraycopy
   import compat.Math.min
@@ -67,21 +68,25 @@ abstract class BitSet extends AnyRef with Function1[Int,Boolean] with Set[Int] {
    *
    * @return true, iff both bitsets contain the same elements.
    */
-  override def equals(that: Any): Boolean = (
-    that.isInstanceOf[BitSet] &&
-    { val other = that.asInstanceOf[BitSet];
-      (size == other.size) && ( size == 0 || {
-        var len = memsize(min(this.capacity, other.capacity))
+  override def equals(other: Any): Boolean = other match {
+    case that: BitSet =>
+      (size == that.size) && {
+        var len = memsize(min(this.capacity, that.capacity))
         var i = 0
-        var res = true
-        while ((i < len) && res) {
-          res = arr(i) == other.arr(i)
-          i = i + 1
-        }
-        res
-      })
-   } || super.equals(that)
-  );
+        while (i < len && arr(i) == that.arr(i)) i = i + 1
+        i == len
+      }
+    case _ =>
+      super.equals(other)
+  }
+
+  override def hashCode(): Int = {
+    val len = memsize(this.capacity)
+    var h = 0
+    var i = 0
+    while (i < len) { h = h * 41 + arr(i); i = i + 1 }
+    h
+  }
 
   /**
    * Checks if this set is a subset of set <code>that</code>.
@@ -90,26 +95,18 @@ abstract class BitSet extends AnyRef with Function1[Int,Boolean] with Set[Int] {
    * @param  that another set.
    * @return true, iff the other set is a superset of this set.
    */
-  override def subsetOf(that: Set[Int]): Boolean =
-    (that.isInstanceOf[BitSet] && {
-      val other = that.asInstanceOf[BitSet]
-      val len = memsize(min(this.capacity, other.capacity))
+  override def subsetOf(other: Set[Int]): Boolean = other match {
+    case that: BitSet =>
+      val thisLen = memsize(this.capacity)
+      val thatLen = memsize(that.capacity)
+      val minLen = min(thisLen, thatLen)
       var i = 0
-      var res = true
-      while((i < len) && res) {
-        res = other.arr(i) == (other.arr(i) | arr(i))
-        i = i + 1
-      }
-      res && (this.capacity <= other.capacity || {
-        // if this set is bigger check that the rest is empty
-        while (i < memsize(this.capacity) && res) {
-          res == arr(i) == 0
-          i = i + 1
-        }
-        res
-      })
-    }) || super.subsetOf(that);
-
+      while (i < minLen && that.arr(i) == (that.arr(i) | arr(i))) i = i + 1
+      while (i < thisLen && arr(i) == 0) i = i + 1
+      i == thisLen
+    case _ =>
+      super.subsetOf(other)
+  }
 
   /** @return the number of Int cells needed to store <code>n</code> bits */
   protected final def memsize(n: Int): Int = offset(n + 31)
diff --git a/src/library/scala/collection/Map.scala b/src/library/scala/collection/Map.scala
index ad3dc29380..cf23b8cbdf 100644
--- a/src/library/scala/collection/Map.scala
+++ b/src/library/scala/collection/Map.scala
@@ -28,132 +28,126 @@ package scala.collection
  *  immutable data structures.
  *
  *  @author  Matthias Zenger
- *  @version 1.1, 02/05/2004
+ *  @author  Martin Odersky
+ *  @version 1.2, 31/12/2006
  */
-trait Map[A, +B] extends AnyRef
-      with PartialFunction[A, B]
-      with Iterable[Pair[A, B]]
-{
-    /** Compute the number of key-to-value mappings.
-     *
-     *  @return the number of mappings
-     */
-    def size: Int
-
-    /** Check if this map maps <code>key</code> to a value and return the
-     *  value if it exists.
-     *
-     *  @param  key the key of the mapping of interest
-     *  @return     the value of the mapping, if it exists
-     */
-    def get(key: A): Option[B]
-
-    /** Is this an empty map?
-     *
-     *  @return <code>true</code> iff the map is empty.
-     */
-    def isEmpty: Boolean = (size == 0)
-
-    /** Retrieve the value which is associated with the given key. This
-     *  method throws an exception if there is no mapping from the given
-     *  key to a value.
-     *
-     *  @param  key the key
-     *  @return     the value associated with the given key.
-     */
-    def apply(key: A): B = get(key) match {
-      case None => default(key)
-      case Some(value) => value
-    }
-
-    /** Is the given key mapped to a value by this map?
-     *
-     *  @param key the key
-     *  @return    <code>true</code> iff there is a mapping for key in this map
-     */
-    def contains(key: A): Boolean = get(key) match {
-      case None => false
-      case Some(_) => true
-    }
-
-    /** @return the keys of this map as a set.
-     */
-    def keySet = new Set[A] {
-      def size = Map.this.size;
-      def contains(key : A) = Map.this.contains(key);
-      def elements = Map.this.elements.map(._1);
-    }
-
-    /** Does this map contain a mapping from the given key to a value?
-     *
-     *  @param key the key
-     *  @return    <code>true</code> iff there is a mapping for key in this map
-     */
-    def isDefinedAt(key: A) = contains(key)
-
-    /** Creates an iterator for all keys.
-     *
-     *  @return an iterator over all keys.
-     */
-    def keys: Iterator[A] = new Iterator[A] {
-      val iter = Map.this.elements
-      def hasNext = iter.hasNext
-      def next = iter.next._1
-    }
-
-    /** Creates an iterator for a contained values.
-     *
-     *  @return an iterator over all values.
-     */
-    def values: Iterator[B] = new Iterator[B] {
-      val iter = Map.this.elements
-      def hasNext = iter.hasNext
-      def next = iter.next._2
-    }
-
-    /** Compares two maps structurally; i.e. checks if all mappings
-     *  contained in this map are also contained in the other map,
-     *  and vice versa.
-     *
-     *  @param that the other map
-     *  @return     <code>true</code> iff both maps contain exactly the
-     *              same mappings.
-     */
-    override def equals(that: Any): Boolean = that match {
-      case other: Map[a, b] =>
-        this.size == other.size && this.elements.forall {
-          case Pair(key, value) => other.get(key.asInstanceOf[a]) match {
-            case None => false
-            case Some(otherval) => value == otherval
-          }
+trait Map[A, +B] extends PartialFunction[A, B] with Iterable[Pair[A, B]] {
+
+  /** Compute the number of key-to-value mappings.
+   *
+   *  @return the number of mappings
+   */
+  def size: Int
+
+  /** Check if this map maps <code>key</code> to a value and return the
+   *  value if it exists.
+   *
+   *  @param  key the key of the mapping of interest
+   *  @return     the value of the mapping, if it exists
+   */
+  def get(key: A): Option[B]
+
+  /** Is this an empty map?
+   *
+   *  @return <code>true</code> iff the map is empty.
+   */
+  def isEmpty: Boolean = size == 0
+
+  /** Retrieve the value which is associated with the given key. This
+   *  method throws an exception if there is no mapping from the given
+   *  key to a value.
+   *
+   *  @param  key the key
+   *  @return     the value associated with the given key.
+   */
+  def apply(key: A): B = get(key) match {
+    case None => default(key)
+    case Some(value) => value
+  }
+
+  /** Is the given key mapped to a value by this map?
+   *
+   *  @param key the key
+   *  @return    <code>true</code> iff there is a mapping for key in this map
+   */
+  def contains(key: A): Boolean = get(key) match {
+    case None => false
+    case Some(_) => true
+  }
+
+  /** Does this map contain a mapping from the given key to a value?
+   *
+   *  @param key the key
+   *  @return    <code>true</code> iff there is a mapping for key in this map
+   */
+  def isDefinedAt(key: A) = contains(key)
+
+  /** Creates an iterator for all keys.
+   *
+   *  @return an iterator over all keys.
+   */
+  def keys: Iterator[A] = new Iterator[A] {
+    val iter = Map.this.elements
+    def hasNext = iter.hasNext
+    def next = iter.next._1
+  }
+
+  /** @return the keys of this map as a set.
+   */
+  def keySet = new Set[A] {
+    def size = Map.this.size;
+    def contains(key : A) = Map.this.contains(key);
+    def elements = Map.this.elements.map(._1);
+  }
+
+  /** Creates an iterator for a contained values.
+   *
+   *  @return an iterator over all values.
+   */
+  def values: Iterator[B] = new Iterator[B] {
+    val iter = Map.this.elements
+    def hasNext = iter.hasNext
+    def next = iter.next._2
+  }
+
+  /** Compares two maps structurally; i.e. checks if all mappings
+   *  contained in this map are also contained in the other map,
+   *  and vice versa.
+   *
+   *  @param that the other map
+   *  @return     <code>true</code> iff both maps contain exactly the
+   *              same mappings.
+   */
+  override def equals(that: Any): Boolean = that match {
+    case other: Map[a, b] =>
+      this.size == other.size && this.elements.forall {
+        case Pair(key, value) => other.get(key.asInstanceOf[a]) match {
+          case None => false
+          case Some(otherval) => value == otherval
         }
-      case _ => false
-    }
-
-    /** Creates a string representation for this map.
-     *
-     *  @return    a string showing all mappings
-     */
-    override def toString() =
-      if (size == 0)
-        "{}"
-      else
-        "{" + {
-          val iter = elements
-          var res = iter.next.toString()
-          while (iter.hasNext) {
-            res = res + ", " + iter.next
-          }
-          res
-        } + "}"
-
-    /** The default value for the map, returned when a key is not found
-     *  The method implemented here yields an error,
-     *  but it might be overridden in subclasses.
-     *
-     *  @param key ...
-     *  @throws Predef.NoSuchElementException ...
-     */
-    def default(key: A): B =
-      throw new NoSuchElementException("key not found: " + key)
+      }
+    case _ => false
+  }
+
+  /** A hash method compatible with <code>equals</code>
+   */
+  override def hashCode() =
+    (0 /: elements) ((hash, kv) => hash + kv.hashCode)
+
+  /** Creates a string representation for this map.
+   *
+   *  @return    a string showing all mappings
+   */
+  override def toString() =
+    elements.toList.map(kv => kv._1 + " -> " + kv._2).mkString("Map(", ", ", ")")
+
+  /** The default value for the map, returned when a key is not found
+   *  The method implemented here yields an error,
+   *  but it might be overridden in subclasses.
+   *
+   *  @param key the given key value
+   *  @throws Predef.NoSuchElementException
+   */
+  def default(key: A): B =
+    throw new NoSuchElementException("key not found: " + key)
 }
diff --git a/src/library/scala/collection/MapProxy.scala b/src/library/scala/collection/MapProxy.scala
index 54aeccde36..2585f24c7d 100644
--- a/src/library/scala/collection/MapProxy.scala
+++ b/src/library/scala/collection/MapProxy.scala
@@ -24,20 +24,14 @@ trait MapProxy[A, +B] extends Map[A, B] with IterableProxy[Pair[A, B]] {
 
   def self: Map[A, B]
 
-  def size: Int = self.size
-
-  def get(key: A): Option[B] = self.get(key)
-
+  override def size: Int = self.size
+  override def get(key: A): Option[B] = self.get(key)
   override def isEmpty: Boolean = self.isEmpty
-
   override def apply(key: A): B = self.apply(key)
-
   override def contains(key: A): Boolean = self.contains(key)
-
   override def isDefinedAt(key: A) = self.isDefinedAt(key)
-
   override def keys: Iterator[A] = self.keys
-
+  override def keySet: Set[A] = self.keySet
   override def values: Iterator[B] = self.values
-
+  override def default(key: A): B = self.default(key)
 }
diff --git a/src/library/scala/collection/Set.scala b/src/library/scala/collection/Set.scala
index 0fd60805af..3d3cb9bece 100644
--- a/src/library/scala/collection/Set.scala
+++ b/src/library/scala/collection/Set.scala
@@ -26,67 +26,71 @@ package scala.collection
  *  data structures.
  *
  *  @author  Matthias Zenger
- *  @version 1.0, 08/07/2003
+ *  @author  Martin Odersky
+ *  @version 2.0, 01/01/2007
  */
-trait Set[A] extends AnyRef with Function1[A, Boolean] with Iterable[A] {
+trait Set[A] extends AnyRef with (A => Boolean) with Iterable[A] {
 
-    /** Returns the number of elements in this set.
-    *
-    *  @return number of set elements.
-    */
-    def size: Int
+  /** Returns the number of elements in this set.
+   *
+   *  @return number of set elements.
+   */
+  def size: Int
 
-    /** Checks if this set contains element <code>elem</code>.
-     *
-     *  @param elem the element to check for membership.
-     *  @return     <code>true</code> iff <code>elem</code> is contained ini
-     *              this set.
-     */
-    def contains(elem: A): Boolean
+  /** Checks if this set contains element <code>elem</code>.
+   *
+   *  @param elem the element to check for membership.
+   *  @return     <code>true</code> iff <code>elem</code> is contained ini
+   *              this set.
+   */
+  def contains(elem: A): Boolean
 
-    /** This method allows sets to be interpreted as predicates.
-     *  It returns true, iff this set contains element <code>elem</code>.
-     *
-     *  @param elem the element to check for membership.
-     *  @return     <code>true</code> iff <code>elem</code> is contained in
-     *              this set.
-     */
-    def apply(elem: A): Boolean = contains(elem)
+  /** This method allows sets to be interpreted as predicates.
+   *  It returns true, iff this set contains element <code>elem</code>.
+   *
+   *  @param elem the element to check for membership.
+   *  @return     <code>true</code> iff <code>elem</code> is contained in
+   *              this set.
+   */
+  def apply(elem: A): Boolean = contains(elem)
 
-    /** Checks if this set is empty.
-     *
-     *  @return <code>true</code> iff there is no element in the set.
-     */
-    def isEmpty: Boolean = (size == 0)
+  /** Checks if this set is empty.
+   *
+   *  @return <code>true</code> iff there is no element in the set.
+   */
+  def isEmpty: Boolean = size == 0
 
-    /** Checks if this set is a subset of set <code>that</code>.
-     *
-     *  @param that another set.
-     *  @return     <code>true</code> iff the other set is a superset of
-     *              this set.
-     */
-    def subsetOf(that: Set[A]): Boolean = forall(that.contains)
+  /** Checks if this set is a subset of set <code>that</code>.
+   *
+   *  @param that another set.
+   *  @return     <code>true</code> iff the other set is a superset of
+   *              this set.
+   *  todo: rename to isSubsetOf
+   */
+  def subsetOf(that: Set[A]): Boolean = forall(that.contains)
 
-    /** Compares this set with another object and returns true, iff the
-     *  other object is also a set which contains the same elements as
-     *  this set.
-     *
-     *  @param that the other object
-     *  @return     <code>true</code> iff this set and the other set
-     *              contain the same elements.
-     */
-    override def equals(that: Any): Boolean = that match {
-      case other: Set[a] =>
-        this.size == other.size && this.elements.forall(
-          x => other contains x.asInstanceOf[a])
-      case _ =>
-        false
-    }
+  /** Compares this set with another object and returns true, iff the
+   *  other object is also a set which contains the same elements as
+   *  this set.
+   *
+   *  @param that the other object
+   *  @return     <code>true</code> iff this set and the other set
+   *              contain the same elements.
+   */
+  override def equals(that: Any): Boolean = that match {
+    case other: Set[a] =>
+      this.size == other.size && subsetOf(other.asInstanceOf[Set[A]])
+    case _ =>
+      false
+  }
 
-    /** Returns a string representation of this set.
-     *
-     *  @return a string showing all elements of this set.
-     */
-    override def toString(): String =
-      if (isEmpty) "{}" else toList.mkString("{", ", ", "}")
+  /** hashcode for this set */
+  override def hashCode() =
+    (0 /: this)((hash, e) => hash * 41 + e.hashCode())
+
+  /** Returns a string representation of this set.
+   *
+   *  @return a string showing all elements of this set.
+   */
+  override def toString(): String = mkString("{", ", ", "}")
 }
diff --git a/src/library/scala/collection/SetProxy.scala b/src/library/scala/collection/SetProxy.scala
index 4d770daec9..d710ce48ba 100644
--- a/src/library/scala/collection/SetProxy.scala
+++ b/src/library/scala/collection/SetProxy.scala
@@ -18,22 +18,13 @@ package scala.collection
  *  dynamically using object composition and forwarding.
  *
  *  @author  Matthias Zenger
- *  @version 1.0, 21/07/2003
+ *  @author  Martin Odersky
+ *  @version 2.0, 01/01/2007
  */
 trait SetProxy[A] extends Set[A] with IterableProxy[A] {
-
   def self: Set[A]
-
   def size: Int = self.size
-
   override def isEmpty: Boolean = self.isEmpty
-
   def contains(elem: A): Boolean = self.contains(elem)
-
   override def subsetOf(that: Set[A]): Boolean = self.subsetOf(that)
-
-  override def foreach(f: A => Unit): Unit = self.foreach(f)
-
-  override def exists(p: A => Boolean): Boolean = self.exists(p)
-
 }
diff --git a/src/library/scala/collection/immutable/BitSet.scala b/src/library/scala/collection/immutable/BitSet.scala
index 1f3af38ee0..b2d50c329f 100644
--- a/src/library/scala/collection/immutable/BitSet.scala
+++ b/src/library/scala/collection/immutable/BitSet.scala
@@ -28,6 +28,12 @@ package scala.collection.immutable
  */
 
 [serializable]
+/*
+ *                This is a strange class! It claims to be immutable but is not.
+ *                It claims to be a BitSet but it is not a Set.
+ *                Remove it or integrate it into the Set hierarchy.
+ *                [Comments by Martin]
+ */
 class BitSet(val size: Int, val capacity: Int, ba: Array[Int], copy: Boolean)
   extends collection.BitSet
 {
diff --git a/src/library/scala/collection/immutable/ListMap.scala b/src/library/scala/collection/immutable/ListMap.scala
index d7e2df5329..837d5e36a4 100644
--- a/src/library/scala/collection/immutable/ListMap.scala
+++ b/src/library/scala/collection/immutable/ListMap.scala
@@ -9,11 +9,22 @@
 // $Id$
 
 
-package scala.collection.immutable
 
+package scala.collection.immutable
 
 object ListMap {
-  def Empty[A, B] = new ListMap[A, B]
+
+  /** The empty map of this type
+   *  @deprecated   use <code>empty</code> instead
+   */
+  [deprecated] def Empty[A, B] = new ListMap[A, B]
+
+  /** The empty map of this type */
+  def empty[A, B] = new ListMap[A, B]
+
+  /** The canonical factory for this type
+   */
+  //def apply[A, B](elems: Pair[A, B]*) = empty[A, B] ++ elems
 }
 
 /** This class implements immutable maps using a list-based data
@@ -22,15 +33,16 @@ object ListMap {
  *  directly, or by applying the function <code>ListMap.Empty</code>.
  *
  *  @author  Matthias Zenger
- *  @version 1.0, 09/07/2003
+ *  @author  Martin Oderskty
+ *  @version 2.0, 01/01/2007
  */
 [serializable]
-class ListMap[A, B] extends AnyRef with Map[A, B] {
+class ListMap[A, +B] extends Map[A, B] {
 
   /** Returns a <code>new ListMap</code> instance mapping keys of the
    *  same type to values of type <code>C</code>.
    */
-  def empty[C] = ListMap.Empty[A, C]
+  def empty[C] = ListMap.empty[A, C]
 
   /** Returns the number of mappings in this map.
    *
@@ -55,7 +67,7 @@ class ListMap[A, B] extends AnyRef with Map[A, B] {
    *  @param key  the key element of the updated entry.
    *  @param value the value element of the updated entry.
    */
-  def update(key: A, value: B): ListMap[A, B] = new Node(key, value)
+  def update [B1 >: B](key: A, value: B1): ListMap[A, B1] = new Node(key, value)
 
   /** This creates a new mapping without the given <code>key</code>.
    *  If the map does not contain a mapping for the given key, the
@@ -63,49 +75,30 @@ class ListMap[A, B] extends AnyRef with Map[A, B] {
    *
    *  @param key a map without a mapping for the given key.
    */
-  def -(key: A): ListMap[A, B] = this
+  def - (key: A): ListMap[A, B] = this
 
   /** Returns an iterator over key-value pairs.
    */
   def elements: Iterator[Pair[A,B]] = new Iterator[Pair[A,B]] {
-    var that: ListMap[A,B] = ListMap.this;
-    def hasNext = !that.isEmpty;
+    var self: ListMap[A,B] = ListMap.this
+    def hasNext = !self.isEmpty
     def next: Pair[A,B] =
       if (!hasNext) throw new NoSuchElementException("next on empty iterator")
-      else { val res = Pair(that.key, that.value); that = that.next; res }
+      else { val res = Pair(self.key, self.value); self = self.next; res }
   }
 
-  /** Compares two maps for equality.
-   *   Two maps are equal iff they contain exactly the
-   *   same key-value pairs.
-   */
-  override def equals(obj: Any): Boolean =
-    if (obj.isInstanceOf[scala.collection.Map[A, B]]) {
-      val that = obj.asInstanceOf[scala.collection.Map[A, B]]
-      if (size != that.size) false else toList.forall {
-        case Pair(key, value) => that.get(key) match {
-          case None => false
-          case Some(v) => v == value
-        }
-      }
-    } else
-      false
-
-  override def hashCode(): Int = 0
-
-  protected def key: A = throw new NoSuchElementException("empty map");
-  protected def value: B = throw new NoSuchElementException("empty map");
-  protected def next: ListMap[A, B] = throw new NoSuchElementException("empty map");
+  protected def key: A = throw new NoSuchElementException("empty map")
+  protected def value: B = throw new NoSuchElementException("empty map")
+  protected def next: ListMap[A, B] = throw new NoSuchElementException("empty map")
 
   [serializable]
-  protected class Node(override protected val key: A, override protected val value: B)
-    extends ListMap[A, B]
-  {
+  protected class Node[B1 >: B](override protected val key: A,
+                                override protected val value: B1) extends ListMap[A, B1] {
     /** Returns the number of mappings in this map.
      *
      *  @return number of mappings.
      */
-    override def size: Int = ListMap.this.size + 1
+    override def size: Int = next.size + 1
 
     /** Is this an empty map?
      *
@@ -120,7 +113,7 @@ class ListMap[A, B] extends AnyRef with Map[A, B] {
      *  @param  key the key
      *  @return     the value associated with the given key.
      */
-    override def apply(k: A): B = if (k == key) value else ListMap.this(k)
+    override def apply(k: A): B1 = if (k == key) value else next(k)
 
     /** Checks if this map maps <code>key</code> to a value and return the
      *  value if it exists.
@@ -128,8 +121,8 @@ class ListMap[A, B] extends AnyRef with Map[A, B] {
      *  @param  key the key of the mapping of interest
      *  @return     the value of the mapping, if it exists
      */
-    override def get(k: A): Option[B] =
-      if (k == key) Some(value) else ListMap.this.get(k)
+    override def get(k: A): Option[B1] =
+      if (k == key) Some(value) else next.get(k)
 
     /** This method allows one to create a new map with an
      *  additional mapping from <code>key</code>
@@ -140,12 +133,10 @@ class ListMap[A, B] extends AnyRef with Map[A, B] {
      *  @param k ...
      *  @param v ...
      */
-    override def update(k: A, v: B): ListMap[A, B] =
-      if (k == key) {
-        new ListMap.this.Node(k, v)
-      } else {
-        val tail = ListMap.this.update(k,v); new tail.Node(key, value)
-      }
+    override def update [B2 >: B1](k: A, v: B2): ListMap[A, B2] = {
+      val m = if (contains(k)) this - k else this
+      new m.Node(k, v)
+    }
 
     /** Creates a new mapping without the given <code>key</code>.
      *  If the map does not contain a mapping for the given key, the
@@ -154,16 +145,15 @@ class ListMap[A, B] extends AnyRef with Map[A, B] {
      *  @param k ...
      *  @return  ...
      */
-    override def -(k: A): ListMap[A, B] =
+    override def - (k: A): ListMap[A, B1] =
       if (k == key)
-        ListMap.this
+        next
       else {
-        val tail = ListMap.this - k; new tail.Node(key, value)
+        val tail = next - k
+        if (tail eq next) this
+        else new tail.Node(key, value)
       }
 
-    override def hashCode(): Int =
-      (key.hashCode() ^ value.hashCode()) + ListMap.this.hashCode()
-
-    override protected def next: ListMap[A,B] = ListMap.this;
+    override protected def next: ListMap[A,B1] = ListMap.this
   }
 }
diff --git a/src/library/scala/collection/immutable/ListSet.scala b/src/library/scala/collection/immutable/ListSet.scala
index 3e95923b2c..22c2ffa8c9 100644
--- a/src/library/scala/collection/immutable/ListSet.scala
+++ b/src/library/scala/collection/immutable/ListSet.scala
@@ -15,9 +15,19 @@ package scala.collection.immutable
 //import Predef.NoSuchElementException
 
 object ListSet {
+
   /** constructs an empty ListSet
+   *  @deprecated   use <code>empty</code> instead
+   */
+  [deprecated] def Empty[A] = new ListSet[A]
+
+  /** The empty set of this type.
+   */
+  def empty[A] = new ListSet[A]
+
+  /** The canonical factory for this type
    */
-  def Empty[A] = new ListSet[A]
+//  def apply[A, B](elems: A*) = empty[A] ++ elems
 }
 
 
@@ -40,7 +50,7 @@ class ListSet[A] extends AnyRef with Set[A] {
 
   override def isEmpty: Boolean = true;
 
-  def empty[B] = new ListSet[B]
+  def empty[B] = ListSet.empty[B]
 
   /** Checks if this set contains element <code>elem</code>.
    *
diff --git a/src/library/scala/collection/immutable/Map.scala b/src/library/scala/collection/immutable/Map.scala
index 787d5d1670..41f9126fd6 100644
--- a/src/library/scala/collection/immutable/Map.scala
+++ b/src/library/scala/collection/immutable/Map.scala
@@ -30,9 +30,11 @@ package scala.collection.immutable
  *
  *  @author  Matthias Zenger
  *  @author  Erik Stenman
- *  @version 1.1, 22/03/2004
+ *  @author  Martin Odersky
+ *  @version 1.2, 31/06/2006
+ *  todo: make contravariant in A?
  */
-trait Map[A, B] extends AnyRef with collection.Map[A, B] {
+trait Map[A, +B] extends collection.Map[A, B] {
 
   /** This method returns a new map instance of the same class
    *  mapping keys of the same type to values of type <code>C</code>.
@@ -48,14 +50,102 @@ trait Map[A, B] extends AnyRef with collection.Map[A, B] {
    *  @param key   ...
    *  @param value ...
    *  @return      the created map
+   *  @deprecated    use <code>+({A, B})</code> instead
    */
-  def update(key: A, value: B): Map[A, B]
+  def update [B1 >: B] (key: A, value: B1): Map[A, B1]
 
-  /** This creates a new mapping without the given <code>key</code>.
-   *  If the map does not contain a mapping for the given key, the
-   *  method returns the same map.
+  /** Add a key/value pair to this map.
+   *  @param    kv the key/value pair.
+   *  @return   A new map with the new binding added to this map
    */
-  def -(key: A): Map[A, B]
+  def + [B1 >: B] (kv: Pair[A, B1]): Map[A, B1] = update(kv._1, kv._2)
+
+  /** Add two or more key/value pairs to this map.
+   *  @param    kv1 the first key/value pair.
+   *  @param    kv2 the second key/value pair.
+   *  @param    kvs the remaining key/value pairs.
+   *  @return   A new map with the new bindings added
+   */
+  def + [B1 >: B] (kv1: Pair[A, B1], kv2: Pair[A, B1], kvs: Pair[A, B1]*): Map[A, B1] =
+    this + kv1 + kv2 ++ kvs
+
+  /** Add a sequence of key/value pairs to this map.
+   *  @param    kvs the iterable object containing all key/value pairs.
+   *  @return   A new map with the new bindings added
+   */
+  def ++ [B1 >: B] (kvs: Iterable[Pair[A, B1]]): Map[A, B1] = this ++ kvs.elements
+
+  /** Add a sequence of key/value pairs to this map.
+   *  @param    kvs the iterator containing all key/value pairs.
+   *  @return   A new map with the new bindings added
+   */
+  def ++ [B1 >: B] (kvs: Iterator[Pair[A, B1]]): Map[A, B1] =
+    ((this: Map[A, B1]) /: kvs) ((m, kv) => m + kv)
+
+  /** Remove a key from this map
+   *  @param    key the key to be removed
+   *  @return   If the map does not contain a binding for <code>key</code>
+   *            it is returned unchanged. Otherwise, return a new map
+   *            without a binding for <code>key</code>
+   */
+  def - (key: A): Map[A, B]
+
+  /** Remove two or more keys from this map
+   *  @param    key1 the first key to be removed
+   *  @param    key2 the second key to be removed
+   *  @param    keys the remaining keys to be removed
+   *  @return   A map without bindings for <code>keys</code>
+   *            If the map is mutable, the bindings are removed in place
+   *            and the map itself is returned.
+   *            If the map is immutable, a new map with the bindings removed is returned.
+   */
+  def - (key1: A, key2: A, keys: A*): Map[A, B] =
+    this - key1 - key2 -- keys
+
+  /** Remove a sequence of keys from this map
+   *  @param    keys the keys to be removed
+   *  @return   A map without bindings for the given keys.
+   *            If the map is mutable, the bindings are removed in place
+   *            and the map itself is returned.
+   *            If the map is immutable, a new map with the bindings removed is returned.
+   */
+  def -- (keys: Iterable[A]): Map[A, B] = this -- keys.elements
+
+  /** Remove a sequence of keys from this map
+   *  @param    keys the keys to be removed
+   *  @return   A map without bindings for the given keys.
+   *            If the map is mutable, the bindings are removed in place
+   *            and the map itself is returned.
+   *            If the map is immutable, a new map with the bindings removed is returned.
+   */
+  def -- (keys: Iterator[A]): Map[A, B] =
+    (this /: keys) ((m, key) => m - key)
+
+  /** This function transforms all the values of mappings contained
+   *  in this map with function <code>f</code>.
+   *
+   *  @param f A function over keys and values
+   *  @return  the updated map
+   */
+  def transform[C](f: (A, B) => C): Map[A, C] = {
+    var res = empty[C]
+    foreach { case Pair(key, value) => res = res.update(key, f(key, value)) }
+    res
+  }
+
+  /** This method removes all the mappings for which the predicate
+   *  <code>p</code> returns <code>false</code>.
+   *
+   *  @param p A prediacte over key-value pairs
+   *  @return  the updated map
+   */
+  override def filter(p: Pair[A, B] => Boolean): Map[A, B] = {
+    var res = this
+    foreach {
+      case kv @ Pair(key, _) => if (!p(kv)) { res = res - key }
+    }
+    res
+  }
 
   /** <p>
    *    This method defines syntactic sugar for adding a
@@ -64,8 +154,9 @@ trait Map[A, B] extends AnyRef with collection.Map[A, B] {
    *  <pre>
    *    map + key -> value
    *  </pre>
+   *  @deprecated  use <code>+({A, B})</code> instead
    */
-  def +(key: A): MapTo = new MapTo(key)
+  [deprecated] def +(key: A): MapTo = new MapTo(key)
 
   /** <code>incl</code> can be used to add many mappings at the same time
    *  to the map. The method assumes that a mapping is represented
@@ -74,19 +165,20 @@ trait Map[A, B] extends AnyRef with collection.Map[A, B] {
    *
    *  @param mappings ...
    *  @return         ...
+   *  @deprecated   use <code>+</code> instead
    */
-  def incl(mappings: Pair[A, B]*): Map[A, B] = incl(mappings)
+  [deprecated] def incl[B1 >: B](mappings: Pair[A, B1]*): Map[A, B1] = incl(mappings)
 
   /** <code>incl</code> can be used to add many mappings at the same time
    *  to the map. The method assumes that each mapping is represented
    *  by an Iterator over <code>Pair</code> objects who's first component
    *  denotes the key, and who's second component refers to the value.
    *
-   *  @param map ...
+   *  @deprecated    use <code>++</code> instead
    */
-  def incl(map: Iterable[Pair[A, B]]): Map[A, B] = {
+  [deprecated] def incl[B1 >: B](map: Iterable[Pair[A, B1]]): Map[A, B1] = {
     val iter = map.elements
-    var res = this
+    var res: Map[A, B1] = this
     while (iter.hasNext) {
       val Pair(key, value) = iter.next
       res = res.update(key, value);
@@ -99,16 +191,17 @@ trait Map[A, B] extends AnyRef with collection.Map[A, B] {
    *
    *  @param keys ...
    *  @return     the updated map
-   */
-  def excl(keys: A*): Map[A, B] = excl(keys)
+   *  @deprecated    use <code>-</code> instead   */
+  [deprecated] def excl(keys: A*): Map[A, B] = excl(keys)
 
   /** This method removes all the mappings for keys provided by an
    *  iterator over the elements of the <code>keys</code> object.
    *
    *  @param keys ...
    *  @return     the updated map
+   *  @deprecated    use <code>--</code> instead
    */
-  def excl(keys: Iterable[A]): Map[A, B] = {
+  [deprecated] def excl(keys: Iterable[A]): Map[A, B] = {
     val iter = keys.elements
     var res = this
     while (iter.hasNext) {
@@ -117,62 +210,18 @@ trait Map[A, B] extends AnyRef with collection.Map[A, B] {
     res
   }
 
-  /** This function transforms all the values of mappings contained
-   *  in this map with function <code>f</code>.
-   *
-   *  @param f A function over key-value pairs
-   *  @return  the updated map
-   */
-  def map[C](f: Pair[A, B] => C): Map[A, C] = {
-    var res = empty[C]
-    foreach {
-      case kv @ Pair(key, _) => res = res.update(key, f(kv)) }
-    res
-  }
-
-  /** This method removes all the mappings for which the predicate
-   *  <code>p</code> returns <code>false</code>.
-   *
-   *  @param p A prediacte over key-value pairs
-   *  @return  the updated map
-   */
-  def filter(p: Pair[A, B] => Boolean): Map[A, B] = {
-    var res = this
-    foreach {
-      case kv @ Pair(key, _) => if (!p(kv)) { res = res.excl(key) }
-    }
-    res
-  }
-
-  /** Returns a string representation of this map which shows
-   *  all the mappings.
-   */
-  override def toString() =
-    if (size == 0)
-      "{}"
-    else
-      "{" + {
-        val iter = elements
-        var res = mappingToString(iter.next)
-        while (iter.hasNext) {
-          res = res + ", " + mappingToString(iter.next);
-        }
-        res
-      } + "}"
-
-  override def hashCode() =
-    elements.foldLeft(0)((hash: Int, pair: AnyRef) => hash + pair.hashCode())
-
   /** This method controls how a mapping is represented in the string
    *  representation provided by method <code>toString</code>.
    *
    *  @param p ...
    *  @return  the string representation of a map entry
    */
-  def mappingToString(p: Pair[A, B]) = p._1.toString() + " -> " + p._2
+  [deprecated] def mappingToString[B1 >: B](p: Pair[A, B1]) = p._1.toString() + " -> " + p._2
 
-  class MapTo(key: A) {
-    def ->(value: B) = update(key, value)
+  /** @deprecated    use <code>+({A, B})</code> instead
+   */
+  [deprecated] class MapTo(key: A) {
+    def -> [B1 >: B](value: B1) = update(key, value)
   }
 }
 
diff --git a/src/library/scala/collection/immutable/RedBlack.scala b/src/library/scala/collection/immutable/RedBlack.scala
new file mode 100755
index 0000000000..67c933af57
--- /dev/null
+++ b/src/library/scala/collection/immutable/RedBlack.scala
@@ -0,0 +1,92 @@
+package scala.collection.immutable
+
+abstract class RedBlack[A] {
+
+  def isSmaller(x: A, y: A): boolean
+
+  private def blacken[B](t: Tree[B]): Tree[B] = t match {
+    case RedTree(k, v, l, r) => BlackTree(k, v, l, r)
+    case t => t
+  }
+  private def mkTree[B](isBlack: boolean, k: A, v: B, l: Tree[B], r: Tree[B]) =
+    if (isBlack) BlackTree(k, v, l, r) else RedTree(k, v, l, r)
+
+  abstract class Tree[+B] {
+    def isEmpty: boolean
+    def isBlack: boolean
+    def lookup(x: A): Tree[B]
+    def update[B1 >: B](k: A, v: B1): Tree[B1] = blacken(upd(k, v))
+    def delete(k: A): Tree[B] = del(k)
+    def elements: Iterator[Pair[A, B]]
+    def upd[B1 >: B](k: A, v: B1): Tree[B1]
+    def del(k: A): Tree[B]
+    def smallest: NonEmpty[B]
+  }
+  abstract class NonEmpty[+B] extends Tree[B] {
+    def isEmpty = false
+    def key: A
+    def value: B
+    def left: Tree[B]
+    def right: Tree[B]
+    def lookup(k: A): Tree[B] =
+      if (isSmaller(k, key)) left.lookup(k)
+      else if (isSmaller(key, k)) right.lookup(k)
+      else this
+    def upd[B1 >: B](k: A, v: B1): Tree[B1] = {
+      def balanceLeft(isBlack: boolean, z: A, zv: B, l: Tree[B1], d: Tree[B1]) = l match {
+        case RedTree(y, yv, RedTree(x, xv, a, b), c) =>
+          RedTree(y, yv, BlackTree(x, xv, a, b), BlackTree(z, zv, c, d))
+        case RedTree(x, xv, a, RedTree(y, yv, b, c)) =>
+          RedTree(y, yv, BlackTree(x, xv, a, b), BlackTree(z, zv, c, d))
+        case _ =>
+          mkTree(isBlack, z, zv, l, d)
+      }
+      def balanceRight(isBlack: boolean, x: A, xv: B, a: Tree[B1], r: Tree[B1]) = r match {
+        case RedTree(z, zv, RedTree(y, yv, b, c), d) =>
+          RedTree(y, yv, BlackTree(x, xv, a, b), BlackTree(z, zv, c, d))
+        case RedTree(y, yv, b, RedTree(z, zv, c, d)) =>
+          RedTree(y, yv, BlackTree(x, xv, a, b), BlackTree(z, zv, c, d))
+        case _ =>
+          mkTree(isBlack, x, xv, a, r)
+      }
+      if (isSmaller(k, key)) balanceLeft(isBlack, key, value, left.upd(k, v), right)
+      else if (isSmaller(key, k)) balanceRight(isBlack, key, value, left, right.upd(k, v))
+      else mkTree(isBlack, k, v, left, right)
+    }
+    def del(k: A): Tree[B] = {
+      if (isSmaller(k, key)) mkTree(isBlack, key, value, left.del(k), right)
+      else if (isSmaller(key, k)) mkTree(isBlack, key, value, left, right.del(k))
+      else if (left.isEmpty) right
+      else if (right.isEmpty) left
+      else {
+        val s = right.smallest
+        mkTree(isBlack, s.key, s.value, left, right.del(s.key))
+      }
+    }
+    def smallest: NonEmpty[B] = if (left.isEmpty) this else left.smallest
+    def elements: Iterator[Pair[A, B]] =
+      left.elements append Iterator.single(Pair(key, value)) append right.elements
+  }
+  case object Empty extends Tree[Nothing] {
+    def isEmpty = true
+    def isBlack = true
+    def lookup(k: A): Tree[Nothing] = this
+    def upd[B](k: A, v: B): Tree[B] = RedTree(k, v, Empty, Empty)
+    def del(k: A): Tree[Nothing] = this
+    def smallest: NonEmpty[Nothing] = throw new NoSuchElementException("empty map")
+    def elements: Iterator[Pair[A, Nothing]] = Iterator.empty
+  }
+  case class RedTree[+B](override val key: A,
+                         override val value: B,
+                         override val left: Tree[B],
+                         override val right: Tree[B]) extends NonEmpty[B] {
+    def isBlack = false
+  }
+  case class BlackTree[+B](override val key: A,
+                           override val value: B,
+                           override val left: Tree[B],
+                           override val right: Tree[B]) extends NonEmpty[B] {
+    def isBlack = true
+  }
+}
+
diff --git a/src/library/scala/collection/immutable/Set.scala b/src/library/scala/collection/immutable/Set.scala
index 6450a371b2..da647a363a 100644
--- a/src/library/scala/collection/immutable/Set.scala
+++ b/src/library/scala/collection/immutable/Set.scala
@@ -26,62 +26,132 @@ package scala.collection.immutable
  */
 trait Set[A] extends AnyRef with collection.Set[A] {
 
-  /** This method creates a new set with an additional element.
+  /** @return an empty set of arbitrary element type
+   */
+  def empty[B]: Set[B]
+
+  /** Create a new set with an additional element.
    */
   def +(elem: A): Set[A]
 
-  /** @return an empty set of arbitrary type
+  /** Add two or more elements to this set.
+   *  @param    elem1 the first element.
+   *  @param    elem2 the second element.
+   *  @param    elems the remaining elements.
+   *  @return a new set with the elements added.
    */
-  def empty[B]: Set[B]
+  def + (elem1: A, elem2: A, elems: A*): Set[A] =
+    this + elem1 + elem2 ++ elems
+
+  /** Add all the elements provided by an iterator
+   *  of the iterable object <code>elems</code> to the set.
+   *
+   *  @param elems  the iterable object containing the elements to be added
+   *  @return a new set with the elements added.
+   */
+  def ++ (elems: Iterable[A]): Set[A] = this ++ elems.elements
+
+  /** Add all the elements provided by an iterator to the set.
+   *  @param elems  the iterator containing the elements to be added
+   *  @return a new set with the elements added.
+   */
+  def ++ (elems: Iterator[A]): Set[A] =
+    (this /: elems) ((s, elem) => s + elem)
 
   /** <code>incl</code> can be used to add many elements to the set
    *  at the same time.
    */
-  def incl(elems: A*): Set[A] = incl(elems)
+  [deprecated] def incl(elems: A*): Set[A] = incl(elems)
 
   /** This method will add all the elements provided by an iterator
    *  of the iterable object <code>that</code> to the set.
    *
    *  @param that ...
    */
-  def incl(that: Iterable[A]): Set[A] =
+  [deprecated] def incl(that: Iterable[A]): Set[A] =
     that.foldLeft(this)((set, elem) => set + elem)
 
-  /** <code>-</code> can be used to remove a single element from
-   *  a set.
+  /** Remove a single element from a set.
+   *  @param elem the element to be removed
+   *  @return a new set with the element removed.
    */
   def -(elem: A): Set[A]
 
+  /** Remove two or more elements from this set.
+   *  @param    elem1 the first element.
+   *  @param    elem2 the second element.
+   *  @param    elems the remaining elements.
+   *  @return a new set with the elements removed.
+   */
+  def - (elem1: A, elem2: A, elems: A*): Set[A] =
+    this - elem1 - elem2 -- elems
+
+  /** Remove all the elements provided by an iterator
+   *  of the iterable object <code>elems</code> from the set.
+   *
+   *  @param elems An iterable object containing the elements to remove from the set.
+   *  @return a new set with the elements removed.
+   */
+  def -- (elems: Iterable[A]): Set[A] = this -- elems.elements
+
+  /** Remove all the elements provided by an iterator
+   *  <code>elems</code> from the set.
+   *  @param elems An iterator containing the elements to remove from the set.
+   *  @return a new set with the elements removed.
+   */
+  def -- (elems: Iterator[A]): Set[A] =
+    (this /: elems) ((s, elem) => s - elem)
+
   /** <code>excl</code> removes many elements from the set.
    */
-  def excl(elems: A*): Set[A] = excl(elems)
+  [deprecated] def excl(elems: A*): Set[A] = excl(elems)
 
   /** This method removes all the elements provided by an iterator
    *  of the iterable object <code>that</code> from the set.
    */
-  def excl(that: Iterable[A]): Set[A] =
+  [deprecated] def excl(that: Iterable[A]): Set[A] =
     that.foldLeft(this)((set, elem) => set - elem)
 
   /** This method computes an intersection with set <code>that</code>.
    *  It removes all the elements that are not present in <code>that</code>.
    *
-   *  @param that ...
+   *  @param that the set to intersect with
    */
   def intersect(that: collection.Set[A]): Set[A] = filter(that.contains)
 
-  def map[B](f: A => B): Set[B] =
+  /** This method is an alias for <code>intersect</code>.
+   *  It computes an intersection with set <code>that</code>.
+   *  It removes all the elements that are not present in <code>that</code>.
+   *
+   *  @param that the set to intersect with
+   */
+   def ** (that: collection.Set[A]): Set[A] = intersect(that)
+
+  /** Returns the set resulting from applying the given function <code>f</code> to each
+   *  element of this set.
+   *
+   *  @param f function to apply to each element.
+   *  @return a set containing <code>f(a0), ..., f(an)</code>
+   *          if this set contains <code>a0, ..., an</code>.
+   */
+  override def map[B](f: A => B): Set[B] =
     foldLeft(empty[B])((set: Set[B], elem: A) => set + f(elem))
 
+  /** Applies the given function <code>f</code> to each element of
+   *  this set, then forms the union of all results.
+   *  @param f function to apply to each element.
+   *  @return a set containing all elements in each <code>f(a0), ..., f(an)</code>
+   *          if this set contains <code>a0, ..., an</code>.
+   */
+  override def flatMap[B](f: A => Iterable[B]): Set[B] =
+    foldLeft(empty[B])((set: Set[B], elem: A) => set incl f(elem))
+
   /** Method <code>filter</code> removes all elements from the set for
    *  which the predicate <code>p</code> yields the value <code>false</code>.
    *
-   *  @param p ...
+   *  @param p The predicate used to filter the set
    */
-  def filter(p: A => Boolean): Set[A] =
+  override def filter(p: A => Boolean): Set[A] =
     foldLeft(this)((set, elem) => if (p(elem)) set else set - elem)
 
-  /** hashcode for this set */
-  override def hashCode() =
-    foldLeft(0)((hash: Int, e: A) => hash + e.hashCode())
-
 }
diff --git a/src/library/scala/collection/immutable/TreeMap.scala b/src/library/scala/collection/immutable/TreeMap.scala
index 7197fad73c..3b5e245cb5 100644
--- a/src/library/scala/collection/immutable/TreeMap.scala
+++ b/src/library/scala/collection/immutable/TreeMap.scala
@@ -8,12 +8,24 @@
 
 // $Id$
 
+// todo: make balanced once Tree.scala is updated to be covariant.
 
 package scala.collection.immutable
 
 
 object TreeMap {
-  def Empty[A <% Ordered[A], B] = new TreeMap[A, B]
+
+  /** The empty map of this type
+   *  @deprecated   use <code>empty</code> instead
+   */
+  [deprecated] def Empty[A <% Ordered[A], B] = empty[A, B]
+
+  /** The empty map of this type */
+  def empty[A <% Ordered[A], B] = new TreeMap[A, B]
+
+  /** The canonical factory for this type
+   */
+//  def apply[A, B](elems: Pair[A, B]*) = empty[A, B] ++ elems
 }
 
 /** This class implements immutable maps using a tree.
@@ -22,28 +34,34 @@ object TreeMap {
  *  @author  Matthias Zenger
  *  @version 1.1, 03/05/2004
  */
-
 [serializable]
-class TreeMap[A <% Ordered[A], B] extends Tree[A, Pair[A, B]] with Map[A, B] {
+class TreeMap[A <% Ordered[A], +B] extends Map[A, B] {
 
-  override protected type This = TreeMap[A, B]
-  override protected def getThis: This = this
+  def size: int = 0
 
-  /** A factory to create empty maps of the same type of keys.
-   */
-  def empty[C] = new TreeMap[A, C]
+  [serializable]
+  class RB extends RedBlack[A] {
+    def isSmaller(x: A, y: A) = x < y
+  }
 
-  /** Creates a new TreeMap from a GBTree and its size.
-   *
-   *  @param sz ...
-   *  @param t ...
-   *  @return ...
-   */
-  protected def New(sz: Int, t: aNode): This = new TreeMap[A, B] {
-    override def size = sz
-    override protected def tree: aNode = t
+  val rb: RedBlack[A] = new RB
+
+  protected def tree: rb.Tree[B] = rb.Empty
+
+  [serializable]
+  class NonEmptyTreeMap[B](s: int, t: rb.Tree[B]) extends TreeMap[A, B] {
+    override val size = s
+    override val rb: TreeMap.this.rb.type = TreeMap.this.rb
+    override val tree = t
   }
 
+
+  private def newMap[B](s: int, t: rb.Tree[B]) = new NonEmptyTreeMap[B](s, t)
+
+  /** A factory to create empty maps of the same type of keys.
+   */
+  def empty[C] = ListMap.empty[A, C]
+
   /** A new TreeMap with the entry added is returned,
    *  if key is <em>not</em> in the TreeMap, otherwise
    *  the key is updated with the new entry.
@@ -52,16 +70,22 @@ class TreeMap[A <% Ordered[A], B] extends Tree[A, Pair[A, B]] with Map[A, B] {
    *  @param value ...
    *  @return ...
    */
-  def update(key: A, value: B) = updateOrAdd(key, Pair(key, value))
+  def update [B1 >: B](key: A, value: B1): TreeMap[A, B1] = {
+    val newsize = if (tree.lookup(key).isEmpty) size + 1 else size
+    newMap(newsize, tree.update(key, value))
+  }
 
   /** A new TreeMap with the entry added is returned,
    *  assuming that key is <em>not</em> in the TreeMap.
    */
-  def insert(key:A,value:B) = add(key, Pair(key, value))
+  def insert [B1 >: B](key: A, value: B1): TreeMap[A, B1] = {
+    assert(tree.lookup(key).isEmpty)
+    newMap(size + 1, tree.update(key, value))
+  }
 
-  /** Removes the key from the TreeMap.
-   */
-  def -(key:A) = deleteAny(key)
+  def - (key:A): TreeMap[A, B] =
+    if (tree.lookup(key).isEmpty) this
+    else newMap(size - 1, tree.delete(key))
 
   /** Check if this map maps <code>key</code> to a value and return the
    *  value if it exists.
@@ -69,11 +93,10 @@ class TreeMap[A <% Ordered[A], B] extends Tree[A, Pair[A, B]] with Map[A, B] {
    *  @param  key     the key of the mapping of interest
    *  @return the value of the mapping, if it exists
    */
-  override def get(key: A): Option[B] =
-    findValue(key) match {
-      case Some(Pair(_, value)) => Some(value)
-      case _ => None
-    }
+  override def get(key: A): Option[B] = tree.lookup(key) match {
+    case n: rb.NonEmpty[b] => Some(n.value)
+    case _ => None
+  }
 
   /** Retrieve the value which is associated with the given key. This
    *  method throws an exception if there is no mapping from the given
@@ -83,37 +106,19 @@ class TreeMap[A <% Ordered[A], B] extends Tree[A, Pair[A, B]] with Map[A, B] {
    *  @return the value associated with the given key.
    *  @throws Error("key not found").
    */
-  override def apply(key: A): B = tree.apply(key)._2
-
-  /** Creates a list of all (key, value) mappings.
-   *
-   *  @return    the list of all mappings
-   */
-  override def toList: List[Pair[A, B]] =
-    tree.toList(scala.Nil) map (._2)
+  override def apply(key: A): B = tree.lookup(key) match {
+    case n: rb.NonEmpty[b] => n.value
+    case _ => super.apply(key)
+  }
 
   /** Creates a new iterator over all elements contained in this
    *  object.
    *
    *  @return the new iterator
    */
-  def elements: Iterator[Pair[A, B]] = entries
-
-  /** Compares two maps structurally; i.e. checks if all mappings
-   *  contained in this map are also contained in the other map,
-   *  and vice versa.
-   *
-   *  @return    true, iff both maps contain exactly the same mappings.
-   */
-  override def equals(obj: Any): Boolean =
-    obj.isInstanceOf[scala.collection.Map[A, B]] && {
-      val that = obj.asInstanceOf[scala.collection.Map[A, B]]
-      size == that.size && elements.forall {
-        case Pair(key, value) => that.get(key) match {
-          case None => false
-          case Some(v) => v == value
-        }
-      }
-    }
+  def elements: Iterator[Pair[A, B]] = tree.elements
 }
 
+
+
+
diff --git a/src/library/scala/collection/immutable/TreeMap.scala.disabled b/src/library/scala/collection/immutable/TreeMap.scala.disabled
new file mode 100755
index 0000000000..3e470e9442
--- /dev/null
+++ b/src/library/scala/collection/immutable/TreeMap.scala.disabled
@@ -0,0 +1,101 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2006, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |                                         **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id: TreeMap.scala 8997 2006-10-19 20:52:30Z odersky $
+
+package scala.collection.immutable
+
+
+object TreeMap {
+  def Empty[A <% Ordered[A], B] = new TreeMap[A, B]
+}
+
+/** This class implements immutable maps using a tree.
+ *
+ *  @author  Erik Stenman
+ *  @author  Matthias Zenger
+ *  @version 1.1, 03/05/2004
+ */
+
+[serializable]
+class TreeMap[A <% Ordered[A], B] extends Tree[A, Pair[A, B]] with Map[A, B] {
+
+  override protected type This = TreeMap[A, B]
+  override protected def getThis: This = this
+
+  /** A factory to create empty maps of the same type of keys.
+   */
+  def empty[C] = new TreeMap[A, C]
+
+  /** Creates a new TreeMap from a GBTree and its size.
+   *
+   *  @param sz ...
+   *  @param t ...
+   *  @return ...
+   */
+  protected def New(sz: Int, t: aNode): This = new TreeMap[A, B] {
+    override def size = sz
+    override protected def tree: aNode = t
+  }
+
+  /** A new TreeMap with the entry added is returned,
+   *  if key is <em>not</em> in the TreeMap, otherwise
+   *  the key is updated with the new entry.
+   *
+   *  @param key ...
+   *  @param value ...
+   *  @return ...
+   */
+  def update [B1 >: B](key: A, value: B1) = updateOrAdd(key, {key, value})
+
+  /** A new TreeMap with the entry added is returned,
+   *  assuming that key is <em>not</em> in the TreeMap.
+   */
+  def insert [B1 >: B](key:A, value:B) = add(key, {key, value})
+
+  /** Removes the key from the TreeMap.
+   */
+  def remove(key:A) = deleteAny(key)
+
+  /** Check if this map maps <code>key</code> to a value and return the
+   *  value if it exists.
+   *
+   *  @param  key     the key of the mapping of interest
+   *  @return the value of the mapping, if it exists
+   */
+  override def get(key: A): Option[B] =
+    findValue(key) match {
+      case Some(Pair(_, value)) => Some(value)
+      case _ => None
+    }
+
+  /** Retrieve the value which is associated with the given key. This
+   *  method throws an exception if there is no mapping from the given
+   *  key to a value.
+   *
+   *  @param  key     the key
+   *  @return the value associated with the given key.
+   *  @throws Error("key not found").
+   */
+  override def apply(key: A): B = tree.apply(key)._2
+
+  /** Creates a list of all (key, value) mappings.
+   *
+   *  @return    the list of all mappings
+   */
+  override def toList: List[Pair[A, B]] =
+    tree.toList(scala.Nil) map (._2)
+
+  /** Creates a new iterator over all elements contained in this
+   *  object.
+   *
+   *  @return the new iterator
+   */
+  def elements: Iterator[Pair[A, B]] = entries
+}
+
diff --git a/src/library/scala/collection/immutable/TreeSet.scala b/src/library/scala/collection/immutable/TreeSet.scala
index 768eda6e8b..3402adca79 100644
--- a/src/library/scala/collection/immutable/TreeSet.scala
+++ b/src/library/scala/collection/immutable/TreeSet.scala
@@ -11,68 +11,75 @@
 
 package scala.collection.immutable
 
+object TreeSet {
+
+  /** The empty set of this type
+   *  @deprecated   use <code>empty</code> instead
+   */
+  [deprecated] def Empty[A <% Ordered[A]] = empty[A]
+
+  /** The empty set of this type
+   */
+  def empty[A <% Ordered[A]] = new TreeSet[A]
+}
 
 /** This class implements immutable sets using a tree.
  *
- *  @author  Matthias Zenger
- *  @author  Burak Emir
- *  @version 1.1, 03/05/2004
+ *  @author  Martin Odersky
+ *  @version 2.0, 02/01/2007
  */
 
 [serializable]
-class TreeSet[A <% Ordered[A]]() extends Tree[A, A] with Set[A] {
+class TreeSet[A <% Ordered[A]] extends Set[A] {
 
-  override protected type This = TreeSet[A]
-  override protected def getThis: This = this
+  def size: int = 0
 
-  protected def New(sz: Int, t: aNode): This = new TreeSet[A] {
-    override def size = sz
-    override protected def tree: aNode = t
+  val rb = new RedBlack[A] {
+    def isSmaller(x: A, y: A) = x < y
   }
 
-  /** Checks if this set contains element <code>elem</code>.
-   *
-   *  @param  elem    the element to check for membership.
-   *  @return true, iff <code>elem</code> is contained in this set.
+  def tree: rb.Tree[Unit] = rb.Empty
+
+  private def newSet[B](s: int, t: rb.Tree[Unit]) = new TreeSet[A] {
+    override val size = s
+    override val rb: TreeSet.this.rb.type = TreeSet.this.rb
+    override val tree = t
+  }
+
+  /** A factory to create empty maps of the same type of keys.
    */
-  def contains(elem: A): Boolean = !findValue(elem).isEmpty
+  def empty[B]: Set[B] = ListSet.empty[B]
 
-  /** This method creates a new set with an additional element.
-   *
-   *  @param elem ...
-   *  @return ...
+  /** A new TreeSet with the entry added is returned,
    */
-  def +(elem: A): TreeSet[A] = updateOrAdd(elem, elem)
+  def + (elem: A): TreeSet[A] = {
+    val newsize = if (tree.lookup(elem).isEmpty) size + 1 else size
+    newSet(newsize, tree.update(elem, ()))
+  }
 
-  override def empty[B]: Set[B] = ListSet.Empty
+  /** A new TreeSet with the entry added is returned,
+   *  assuming that elem is <em>not</em> in the TreeSet.
+   */
+  def insert (elem: A): TreeSet[A] = {
+    assert(tree.lookup(elem).isEmpty)
+    newSet(size + 1, tree.update(elem, ()))
+  }
 
-  def emptyTreeSet: TreeSet[A] = New(0, GBLeaf[A,A]())
+  def - (elem:A): TreeSet[A] =
+    if (tree.lookup(elem).isEmpty) this
+    else newSet(size - 1, tree.delete(elem))
 
-  /** <code>-</code> can be used to remove a single element from
-   *  a set.
+  /** Checks if this set contains element <code>elem</code>.
+   *
+   *  @param  elem    the element to check for membership.
+   *  @return true, iff <code>elem</code> is contained in this set.
    */
-  def -(elem: A): TreeSet[A] = deleteAny(elem)
+  def contains(elem: A): Boolean = !tree.lookup(elem).isEmpty
 
   /** Creates a new iterator over all elements contained in this
    *  object.
    *
    *  @return the new iterator
    */
-  def elements: Iterator[A] = entries
-
-  /** Transform this set into a list of all elements.
-   *
-   *  @return  a list which enumerates all elements of this set.
-   */
-  override def toList: List[A] =
-    tree.toList(scala.Nil) map (._2)
-
-  /** Compares two sets for equality.
-   *  Two set are equal iff they contain the same elements.
-   */
-  override def equals(obj: Any): Boolean =
-    obj.isInstanceOf[scala.collection.Set[A]] && {
-      val that = obj.asInstanceOf[scala.collection.Set[A]]
-      (size == that.size) && toList.forall(that.contains)
-    }
+  def elements: Iterator[A] = tree.elements map (._1)
 }
diff --git a/src/library/scala/collection/mutable/ArrayBuffer.scala b/src/library/scala/collection/mutable/ArrayBuffer.scala
index 6fa7da2b74..ab68478b87 100644
--- a/src/library/scala/collection/mutable/ArrayBuffer.scala
+++ b/src/library/scala/collection/mutable/ArrayBuffer.scala
@@ -41,8 +41,18 @@ class ArrayBuffer[A] extends Buffer[A] with ResizableArray[A] {
    *  @param iter  the iterable object.
    *  @return      the updated buffer.
    */
-  override def ++(iter: Iterable[A]): Buffer[A] = {
-    insertAll(size, iter); this
+  override def ++=(iter: Iterable[A]): Unit = iter copyToBuffer this
+
+  /** Appends a number of elements in an array
+   *
+   *  @param src    the array
+   *  @param start  the first element to append
+   *  @param len    the number of elements to append
+   */
+  override def ++=(src: Array[A], start: int, len: int): Unit = {
+    ensureSize(size + len)
+    Array.copy(src, start, array, size, len)
+    size = size + len
   }
 
   /** Prepends a single element to this buffer and return
diff --git a/src/library/scala/collection/mutable/Buffer.scala b/src/library/scala/collection/mutable/Buffer.scala
index 02e5a2ad42..4bf49e3c57 100644
--- a/src/library/scala/collection/mutable/Buffer.scala
+++ b/src/library/scala/collection/mutable/Buffer.scala
@@ -28,97 +28,105 @@ trait Buffer[A] extends AnyRef
       with Scriptable[Message[Pair[Location, A]]]
 {
 
-  /** Append a single element to this buffer and return
-   *  the identity of the buffer.
+  /** Append a single element to this buffer.
    *
    *  @param elem  the element to append.
    */
-  def +(elem: A): Buffer[A] = {
-    this += elem
-    this
-  }
+  def +=(elem: A): Unit
 
-  /** Append a single element to this buffer.
+  /** Append a single element to this buffer and return
+   *  the identity of the buffer.
    *
    *  @param elem  the element to append.
    */
-  def +=(elem: A): Unit
+  def +(elem: A): Buffer[A] = { this += elem; this }
 
-  /** Appends a number of elements provided by an iterable object
-   *  via its <code>elements</code> method. The identity of the
-   *  buffer is returned.
+  /** Prepend a single element to this buffer and return
+   *  the identity of the buffer.
    *
-   *  @param iter  the iterable object.
-   *  @return      the updated buffer.
+   *  @param elem  the element to append.
    */
-  def ++(elems: Iterable[A]): Buffer[A] = this ++ elems.elements
+  def +:(elem: A): Buffer[A]
 
-  /** Appends a number of elements provided by an iterable object
-   *  via its <code>elements</code> method. The identity of the
-   *  buffer is returned.
+  /** Appends a number of elements provided by an iterator
    *
-   *  @param iter  the iterable object.
-   *  @return      the updated buffer.
+   *  @param iter  the iterator.
    */
-  def ++(iter: Iterator[A]): Buffer[A] = {
-    iter.foreach(e => this += e)
-    this
-  }
+  def ++=(iter: Iterator[A]): Unit = iter foreach +=
 
   /** Appends a number of elements provided by an iterable object
    *  via its <code>elements</code> method.
    *
    *  @param iter  the iterable object.
    */
-  def ++=(elems: Iterable[A]): Unit = this ++ elems.elements
+  def ++=(iter: Iterable[A]): Unit = ++=(iter.elements)
 
-  /** Appends a number of elements provided by an iterable object
-   *  via its <code>elements</code> method.
+  /** Appends a number of elements in an array
    *
-   *  @param iter  the iterable object.
+   *  @param src    the array
+   *  @param start  the first element to append
+   *  @param len    the number of elements to append
    */
-  def ++=(it: Iterator[A]): Unit = this ++ it
+  def ++=(src: Array[A], start: int, len: int): Unit = {
+    var i = start
+    val end = i + len
+    while (i < end) {
+      this += src(i)
+      i = i + 1
+    }
+  }
 
-  /** Appends a sequence of elements to this buffer.
+  /** Appends a number of elements provided by an iterable object
+   *  via its <code>elements</code> method. The identity of the
+   *  buffer is returned.
    *
-   *  @param elems  the elements to append.
+   *  @param iter     the iterable object.
+   *  @return       the updated buffer.
    */
-  def append(elems: A*): Unit = this ++ elems
+  def ++(iter: Iterable[A]): Buffer[A] = { this ++= iter; this }
 
-  /** Appends a number of elements provided by an iterable object
-   *  via its <code>elements</code> method.
+  /** Appends a number of elements provided by an iterator
+   *  via its <code>elements</code> method. The identity of the
+   *  buffer is returned.
    *
-   *  @param iter  the iterable object.
+   *  @param iter   the iterator
+   *  @return       the updated buffer.
    */
-  def appendAll(iter: Iterable[A]): Unit = this ++ iter
+  def ++(iter: Iterator[A]): Buffer[A] = { this ++= iter; this }
 
-  /** Prepend a single element to this buffer and return
-   *  the identity of the buffer.
+  /** Prepends a number of elements provided by an iterable object
+   *  via its <code>elements</code> method. The identity of the
+   *  buffer is returned.
    *
-   *  @param elem  the element to append.
+   *  @param iter  the iterable object.
    */
-  def +:(elem: A): Buffer[A]
+  def ++:(iter: Iterable[A]): Buffer[A] = {
+    iter.elements.toList.reverse.foreach(e => e +: this)
+    this
+  }
 
   /** Removes a single element from this buffer, at its first occurrence.
    *  If the list does not contain that element, it is unchanged
    *
    *  @param x  the element to remove.
    */
-  def -= (x: A): unit = {
+  def -= (x: A): Unit = {
     val i = indexOf(x)
     if(i != -1) remove(i)
   }
 
-  /** Prepends a number of elements provided by an iterable object
-   *  via its <code>elements</code> method. The identity of the
-   *  buffer is returned.
+  /** Appends a sequence of elements to this buffer.
+   *
+   *  @param elems  the elements to append.
+   */
+  def append(elems: A*): Unit = this ++= elems
+
+  /** Appends a number of elements provided by an iterable object
+   *  via its <code>elements</code> method.
    *
    *  @param iter  the iterable object.
    */
-  def ++:(iter: Iterable[A]): Buffer[A] = {
-    iter.elements.toList.reverse.foreach(e => e +: this)
-    this
-  }
+  def appendAll(iter: Iterable[A]): Unit = this ++= iter
 
   /** Prepend an element to this list.
    *
@@ -132,7 +140,7 @@ trait Buffer[A] extends AnyRef
    *
    *  @param iter  the iterable object.
    */
-  def prependAll(elems: Iterable[A]): Unit = elems ++: this
+  def prependAll(iter: Iterable[A]): Unit = iter ++: this
 
   /** Inserts new elements at the index <code>n</code>. Opposed to method
    *  <code>update</code>, this method will not replace an element with a
@@ -148,7 +156,7 @@ trait Buffer[A] extends AnyRef
    *  one. Instead, it will insert a new element at index <code>n</code>.
    *
    *  @param n     the index where a new element will be inserted.
-   *  @param iter  the iterable object providing all elements to insert.
+   *  @param iter    the iterable object providing all elements to insert.
    */
   def insertAll(n: Int, iter: Iterable[A]): Unit
 
diff --git a/src/library/scala/collection/mutable/DefaultMapModel.scala b/src/library/scala/collection/mutable/DefaultMapModel.scala
index 2bcaa1ccbe..c7409774bd 100644
--- a/src/library/scala/collection/mutable/DefaultMapModel.scala
+++ b/src/library/scala/collection/mutable/DefaultMapModel.scala
@@ -18,37 +18,29 @@ package scala.collection.mutable
  *  @author  Matthias Zenger
  *  @version 1.0, 08/07/2003
  */
-trait DefaultMapModel[A, B] extends AnyRef with Map[A, B] {
+trait DefaultMapModel[A, B] extends Map[A, B] {
 
-  protected type Entry = DefaultEntry[A,B]
-
-  protected def findEntry(key: A): Option[Entry]
-
-  protected def addEntry(e: Entry): Unit
+  type Entry = DefaultEntry[A, B]
 
+  protected def findEntry(key: A): Entry
+  protected def addEntry(e: Entry)
   protected def entries: Iterator[Entry]
 
-  def get(key: A) = findEntry(key) match {
-    case None => None
-    case Some(e) => Some(e.value);
+  def get(key: A): Option[B] = {
+    val e = findEntry(key)
+    if (e == null) None
+    else Some(e.value);
   }
 
-  def update(key: A, value: B) = findEntry(key) match {
-    case None => addEntry(new Entry(key, value));
-    case Some(e) => e.value = value;
+  def update(key: A, value: B) {
+    val e = findEntry(key)
+    if (e == null) addEntry(new Entry(key, value))
+    else e.value = value
   }
 
-  def elements = new Iterator[Pair[A, B]] {
-    val iter = entries
-    def hasNext = iter.hasNext
-    def next = iter.next.toPair
-  }
+  def elements = entries map (e => Pair(e.key, e.value))
 }
 
 [serializable]
-protected class DefaultEntry[A,B](k: A, v: B) extends AnyRef {
-  def key = k
-  var value = v
-  def toPair = Pair(k, value)
-  override def toString() = k.toString() + " -> " + value
-}
+final class DefaultEntry[A, B](val key: A, var value: B)
+      extends HashEntry[A, DefaultEntry[A, B]]
diff --git a/src/library/scala/collection/mutable/HashMap.scala b/src/library/scala/collection/mutable/HashMap.scala
index 4f0a9efc49..c75b6101f5 100644
--- a/src/library/scala/collection/mutable/HashMap.scala
+++ b/src/library/scala/collection/mutable/HashMap.scala
@@ -14,23 +14,18 @@ package scala.collection.mutable
 /** This class implements mutable maps using a hashtable.
  *
  *  @author  Matthias Zenger
- *  @version 1.0, 08/07/2003
+ *  @author  Martin Odersky
+ *  @version 2.0, 31/12/2006
  */
 [serializable]
 class HashMap[A, B] extends Map[A,B] with HashTable[A] with DefaultMapModel[A,B] {
 
-  def -=(key: A): Unit = removeEntry(key)
-
-  protected def entryKey(e: Entry) = e.key
+  def -= (key: A) { removeEntry(key) }
 
   override def clear = {
-    initTable(table)
+    initTable()
     tableSize = 0
   }
 
-  override def clone(): Map[A, B] = {
-    val res = new HashMap[A, B]
-    res ++= this
-    res
-  }
+  override def clone(): Map[A, B] = new HashMap[A, B] ++ this
 }
diff --git a/src/library/scala/collection/mutable/HashSet.scala b/src/library/scala/collection/mutable/HashSet.scala
index c1be821fd0..7db50fc049 100644
--- a/src/library/scala/collection/mutable/HashSet.scala
+++ b/src/library/scala/collection/mutable/HashSet.scala
@@ -19,32 +19,20 @@ package scala.collection.mutable
 [serializable]
 class HashSet[A] extends Set[A] with HashTable[A] {
 
-  def contains(elem: A): Boolean = findEntry(elem) match {
-    case None => false
-    case Some(_) => true
-  }
+  def contains(elem: A): Boolean = findEntry(elem) != null
 
-  def +=(elem: A): Unit = findEntry(elem) match {
-    case None => addEntry(elem)
-    case Some(_) =>
-  }
+  def +=(elem: A) { if (findEntry(elem) == null) addEntry(new SetEntry(elem)) }
 
-  def -=(elem: A): Unit = removeEntry(elem)
+  def -=(elem: A) { removeEntry(elem) }
 
-  def elements = entries
+  def elements = entries map (.key)
 
-  def clear = {
-    initTable(table)
-    tableSize = 0
-  }
+  def clear {initTable(); tableSize = 0 }
 
-  protected type Entry = A
+  protected type Entry = SetEntry[A]
 
-  protected def entryKey(e: Entry) = e
-
-  override def clone(): Set[A] = {
-    val res = new HashSet[A]
-    res ++= this
-    res
-  }
+  override def clone(): Set[A] = new HashSet[A] ++ this
 }
+
+[serializable]
+final class SetEntry[A](val key: A) extends HashEntry[A, SetEntry[A]]
diff --git a/src/library/scala/collection/mutable/HashTable.scala b/src/library/scala/collection/mutable/HashTable.scala
index f778ccf28b..cb52e6cb4a 100644
--- a/src/library/scala/collection/mutable/HashTable.scala
+++ b/src/library/scala/collection/mutable/HashTable.scala
@@ -15,8 +15,7 @@ package scala.collection.mutable
  *  on hashtables. Class <code>HashTable[A]</code> implements a hashtable
  *  that maps keys of type <code>A</code> to values of the fully abstract
  *  member type <code>Entry</code>. Classes that make use of <code>HashTable</code>
- *  have to provide an implementation for <code>Entry</code> and implement the
- *  function <code>entryKey</code>.<p/>
+ *  have to provide an implementation for <code>Entry</code>
  *
  *  There are mainly two parameters that affect the performance of a hashtable:
  *  the <i>initial size</i> and the <i>load factor</i>. The <i>size</i>
@@ -26,10 +25,13 @@ package scala.collection.mutable
  *  overriding the corresponding values in class <code>HashTable</code>.
  *
  *  @author  Matthias Zenger
- *  @version 1.0, 08/07/2003
+ *  @author  Martin Odersky
+ *  @version 2.0, 31/12/2006
  */
 trait HashTable[A] extends AnyRef {
 
+  protected type Entry >: Null <: HashEntry[A, Entry]
+
   /** The load factor for the hash table.
    */
   protected val loadFactor: Float = 0.75f
@@ -44,8 +46,7 @@ trait HashTable[A] extends AnyRef {
 
   /** The actual hash table.
    */
-  protected var table: Array[List[Entry]] = new Array(initialSize)
-  initTable(table)
+  protected var table: Array[Entry] = new Array(initialSize)
 
   /** The number of mappings contained in this hash table.
    */
@@ -59,73 +60,86 @@ trait HashTable[A] extends AnyRef {
    */
   def size = tableSize
 
-  protected def findEntry(key: A): Option[Entry] =
-    table(index(elemHashCode(key))).find(entryFor(key))
+  protected def findEntry(key: A): Entry = {
+    val h = index(elemHashCode(key))
+    var e = table(h)
+    while (e != null && !elemEquals(e.key, key)) e = e.next
+    e
+  }
 
-  protected def addEntry(e: Entry): Unit = {
-    val h = index(elemHashCode(entryKey(e)))
-    table(h) = e :: table(h)
+  protected def addEntry(e: Entry) {
+    val h = index(elemHashCode(e.key))
+    e.next = table(h)
+    table(h) = e
     tableSize = tableSize + 1
     if (tableSize > threshold)
       resize(2 * table.length)
   }
 
-  protected def removeEntry(key: A): Unit = findEntry(key) match {
-    case None =>
-    case Some(e) =>
-      val idx = index(elemHashCode(key))
-      table(idx) = table(idx).filter(e => !elemEquals(entryKey(e), key))
-      tableSize = tableSize - 1
+  protected def removeEntry(key: A) {
+    val h = index(elemHashCode(key))
+    var e = table(h)
+    if (e != null) {
+      if (elemEquals(e.key, key)) {
+        table(h) = e.next
+        tableSize = tableSize - 1
+      } else {
+        var e1 = e.next
+        while (e1 != null && !elemEquals(e1.key, key)) {
+          e = e1
+          e1 = e1.next
+        }
+        if (e1 != null) {
+          e.next = e1.next
+          tableSize = tableSize - 1
+        }
+      }
+    }
   }
 
-  protected type Entry
-
-  protected def entryKey(e: Entry): A
-
   protected def entries: Iterator[Entry] = new Iterator[Entry] {
     val iterTable = table
     var idx = table.length - 1
-    var xs = iterTable(idx)
+    var es = iterTable(idx)
     scan()
-    def hasNext = !xs.isEmpty
+    def hasNext = es != null
     def next = {
-      val res = xs.head
-      xs = xs.tail
+      val res = es
+      es = es.next
       scan()
       res
     }
-    def scan(): Unit = if (xs.isEmpty && (idx > 0)) {
-      idx = idx - 1
-      xs = iterTable(idx)
-      scan()
+    def scan() {
+      while (es == null && idx > 0) {
+        idx = idx - 1
+        es = iterTable(idx)
+      }
     }
   }
 
-  private def entryFor(key: A) = { e: Entry => elemEquals(entryKey(e), key) }
-
-  protected def initTable(tb: Array[List[Entry]]): Unit = {
-    var i = tb.length - 1
-    while (i >= 0) {
-      tb(i) = Nil
-      i = i - 1
-    }
+  protected def initTable() {
+    var i = table.length - 1
+    while (i >= 0) { table(i) = null; i = i - 1 }
   }
 
   private def newThreshold(size: Int) =
     (size * loadFactor).asInstanceOf[Int]
 
   private def resize(newSize: Int) = {
-    val newTable: Array[List[Entry]] = new Array(newSize)
-    initTable(newTable)
-    var i = table.length - 1
+    val oldTable = table
+    table = new Array(newSize)
+    var i = oldTable.length - 1
     while (i >= 0) {
-      table(i).foreach { e => {
-        val idx = improve(elemHashCode(entryKey(e))) & (newSize - 1)
-        newTable(idx) = e :: newTable(idx)
-      }}
+      var e = oldTable(i)
+      while (e != null) {
+        val h = index(elemHashCode(e.key))
+        val e1 = e.next
+        e.next = table(h)
+        table(h) = e
+        e = e1
+      }
       i = i - 1
     }
-    table = newTable
     threshold = newThreshold(newSize)
   }
 
@@ -142,3 +156,11 @@ trait HashTable[A] extends AnyRef {
 
   protected final def index(hcode: Int) = improve(hcode) & (table.length - 1)
 }
+
+trait HashEntry[A, E] {
+  val key: A
+  var next: E = _
+}
+
+
+
diff --git a/src/library/scala/collection/mutable/ImmutableMapAdaptor.scala b/src/library/scala/collection/mutable/ImmutableMapAdaptor.scala
index 16007865d1..18fd6885f6 100644
--- a/src/library/scala/collection/mutable/ImmutableMapAdaptor.scala
+++ b/src/library/scala/collection/mutable/ImmutableMapAdaptor.scala
@@ -19,7 +19,8 @@ package scala.collection.mutable
  *  return the representation of an empty map.
  *
  *  @author  Matthias Zenger
- *  @version 1.0, 21/07/2003
+ *  @author  Martin Odersky
+ *  @version 2.0, 01/01/2007
  */
 [serializable]
 class ImmutableMapAdaptor[A, B](protected var imap: immutable.Map[A, B])
@@ -40,25 +41,37 @@ extends Map[A, B]
 
   override def keys: Iterator[A] = imap.keys
 
+  override def keySet: collection.Set[A] = imap.keySet
+
   override def values: Iterator[B] = imap.values
 
   def elements: Iterator[Pair[A, B]] = imap.elements
 
-  override def foreach(f: Pair[A, B] => Unit) = imap.foreach(f)
-
   override def toList: List[Pair[A, B]] = imap.toList
 
-  override def toString() = imap.toString()
-
   def update(key: A, value: B): Unit = { imap = imap.update(key, value) }
 
-  def -=(key: A): Unit = { imap = imap - key }
+  def -= (key: A): Unit = { imap = imap - key }
 
   override def clear: Unit = { imap = imap.empty }
 
-  override def map(f: Pair[A, B] => B): Unit = { imap = imap.map(f) }
+  override def transform(f: (A, B) => B): Unit = { imap = imap.transform(f) }
 
-  override def filter(p: Pair[A, B] => Boolean): Unit = { imap = imap.filter(p) }
+  [deprecated] override def map[C](f: Pair[A, B] => C): Iterable[C] = {
+    val f1 = f.asInstanceOf[Pair[A, B] => B]
+    imap = imap transform { (x, y) => f1(Pair(x, y)) }
+    null
+  }
 
-  override def mappingToString(p: Pair[A, B]) = imap.mappingToString(p)
+  /** @deprecated   use retain instead */
+  [deprecated] override def filter(p: Pair[A, B] => Boolean): Iterable[Pair[A, B]] = {
+    imap = imap.filter(p)
+    this
+  }
+
+  override def retain(p: (A, B) => Boolean): Unit = {
+    imap = imap.filter(xy => p(xy._1, xy._2))
+  }
+
+  override def toString() = imap.toString()
 }
diff --git a/src/library/scala/collection/mutable/JavaMapAdaptor.scala b/src/library/scala/collection/mutable/JavaMapAdaptor.scala
index 9131b25ecf..550ef3b9d9 100644
--- a/src/library/scala/collection/mutable/JavaMapAdaptor.scala
+++ b/src/library/scala/collection/mutable/JavaMapAdaptor.scala
@@ -56,7 +56,7 @@ class JavaMapAdaptor[A, B](jmap: java.util.Map) extends Map[A, B] {
 
   def update(key: A, value: B): Unit = { val x = jmap.put(key, value); }
 
-  def -=(key: A): Unit = { val x = jmap.remove(key); }
+  def -= (key: A): Unit = { val x = jmap.remove(key); }
 
   override def clear: Unit = jmap.clear()
 
diff --git a/src/library/scala/collection/mutable/Map.scala b/src/library/scala/collection/mutable/Map.scala
index e1e08abd85..75d14e58fd 100644
--- a/src/library/scala/collection/mutable/Map.scala
+++ b/src/library/scala/collection/mutable/Map.scala
@@ -16,7 +16,7 @@ package scala.collection.mutable
 /** This class represents mutable maps. Concrete map implementations
  *  just have to provide functionality for the abstract methods in
  *  <code>scala.collection.Map</code> as well as for <code>update</code>,
- *  and <code>remove</code>.
+ *  and <code>-=</code>.
  *
  *  @author  Matthias Zenger
  *  @version 1.1, 09/05/2004
@@ -31,72 +31,109 @@ trait Map[A, B] extends AnyRef
    *  mapping for <code>key</code>, it will be overridden by this
    *  function.
    *
-   * @param key
-   * @param value
+   * @param key    The key to update
+   * @param value  The new value
    */
-  def update(key: A, value: B): Unit
+  def update(key: A, value: B)
 
-  /** This method defines syntactic sugar for adding or modifying
-   *  mappings. It is typically used in the following way:
-   *  <pre>
-   *  map += key -> value;
-   *  </pre>
+  /** Add a key/value pair to this map.
+   *  @param    kv the key/value pair.
    */
-  def +=(key: A): MapTo = new MapTo(key)
+  def += (kv: Pair[A, B]) { update(kv._1, kv._2) }
 
-  /** This method adds all the mappings provided by an iterator of
-   *  parameter <code>map</code> to the map.
-   *
-   * @param map
+  /** Add two or more key/value pairs to this map.
+   *  @param    kv1 the first key/value pair.
+   *  @param    kv2 the second key/value pair.
+   *  @param    kvs the remaining key/value pairs.
    */
-  def ++=(map: Iterable[Pair[A, B]]): Unit = ++=(map.elements)
+  def += (kv1: Pair[A, B], kv2: Pair[A, B], kvs: Pair[A, B]*) { this += kv1; this += kv2; this ++= kvs }
 
-  /** This method adds all the mappings provided by an iterator of
-   *  parameter <code>map</code> to the map.
-   *
-   * @param it
+  /** Add a sequence of key/value pairs to this map.
+   *  @param    kvs the iterable object containing all key/value pairs.
+   */
+  def ++= (kvs: Iterable[Pair[A, B]]) { this ++= kvs.elements }
+
+  /** Add a sequence of key/value pairs to this map.
+   *  @param    kvs the iterator containing all key/value pairs.
+   */
+  def ++= (kvs: Iterator[Pair[A, B]]) { kvs foreach += }
+
+  /** Add a key/value pair to this map.
+   *  @param    kv the key/value pair.
+   *  @return   The map itself with the new binding added in place.
+   */
+  def + (kv: Pair[A, B]): Map[A, B] = { this += kv; this }
+
+  /** Add two or more key/value pairs to this map.
+   *  @param    kv1 the first key/value pair.
+   *  @param    kv2 the second key/value pair.
+   *  @param    kvs the remaining key/value pairs.
+   *  @return   The map itself with the new bindings added in place.
    */
-  def ++=(it: Iterator[Pair[A, B]]): Unit = it foreach {
-    case Pair(key, value) => update(key, value)
+  def + (kv1: Pair[A, B], kv2: Pair[A, B], kvs: Pair[A, B]*): Map[A, B] = {
+    this.+=(kv1, kv2, kvs: _*); this
   }
 
-  /** <code>incl</code> can be used to add many mappings at the same time
-   *  to the map. The method assumes that a mapping is represented
-   *  by a <code>Pair</code> object who's first component denotes the
-   *  key, and who's second component refers to the value.
-   *
-   * @param mappings
+  /** Add a sequence of key/value pairs to this map.
+   *  @param    kvs the iterable object containing all key/value pairs.
+   *  @return   The itself map with the new bindings added in place.
    */
-  def incl(mappings: Pair[A, B]*): Unit = ++=(mappings.elements)
+  def ++ (kvs: Iterable[Pair[A, B]]): Map[A, B] = { this ++= kvs; this }
 
-  /** This method removes a mapping from the given <code>key</code>.
-   *  If the map does not contain a mapping for the given key, the
-   *  method does nothing.
-   *
-   *  @param key
+  /** Add a sequence of key/value pairs to this map.
+   *  @param    kvs the iterator containing all key/value pairs.
+   *  @return   The itself map with the new bindings added in place.
    */
-  def -=(key: A): Unit
+  def ++ (kvs: Iterator[Pair[A, B]]): Map[A, B] = { this ++= kvs; this }
 
-  /** This method removes all the mappings for keys provided by an
-   *  iterator over the elements of the <code>keys</code> object.
-   *
-   * @param keys
+  /** Remove a key from this map, noop if key is not present.
+   *  @param    key the key to be removed
    */
-  def --=(keys: Iterable[A]): Unit = --=(keys.elements)
+  def -= (key: A)
 
-  /** This method removes all the mappings for keys provided by an
-   *  iterator over the elements of the <code>keys</code> object.
-   *
-   * @param it
+  /** Remove two or more keys from this map
+   *  @param    key1 the first key to be removed
+   *  @param    key2 the second key to be removed
+   *  @param    keys the remaining keys to be removed
    */
-  def --=(it: Iterator[A]): Unit = it foreach -=
+  def -= (key1: A, key2: A, keys: A*) { this -= key1; this -= key2; this --= keys }
 
-  /** This method will remove all the mappings for the given sequence
-   *  of keys from the map.
-   *
-   * @param keys
+  /** Remove a sequence of keys from this map
+   *  @param    keys the keys to be removed
+   */
+  def --= (keys: Iterable[A]) { this --= keys.elements }
+
+  /** Remove a sequence of keys from this map
+   *  @param    keys the keys to be removed
+   */
+  def --= (keys: Iterator[A]) { keys foreach -= }
+
+  /** Remove a key from this map
+   *  @param    key the key to be removed
+   *  @return   The map itself with the binding for <code>key</code> removed if
+   *            it existed.
    */
-  def excl(keys: A*): Unit = --=(keys.elements)
+  def - (key: A): Map[A, B] = { this -= key; this }
+
+  /** Remove two or more keys from this map
+   *  @param    key1 the first key to be removed
+   *  @param    key2 the second key to be removed
+   *  @param    keys the remaining keys to be removed
+   *  @return   The map itself with all bindings for the given keys removed.
+   */
+  def - (key1: A, key2: A, keys: A*): Map[A, B] = { this.-=(key1, key2, keys: _*); this }
+
+  /** Remove a sequence of keys from this map
+   *  @param    keys the keys to be removed
+   *  @return   The map itself with all bindings for <code>keys</code> removed.
+   */
+  def -- (keys: Iterable[A]): Map[A, B] = { this --= keys; this }
+
+  /** Remove a sequence of keys from this map
+   *  @param    keys the keys to be removed
+   *  @return   The map itself with all bindings for <code>keys</code> removed.
+   */
+  def -- (keys: Iterator[A]): Map[A, B] = { this --= keys; this }
 
   /** Removes all mappings from the map. After this operation is
    *  completed, the map is empty.
@@ -106,19 +143,21 @@ trait Map[A, B] extends AnyRef
   /** This function transforms all the values of mappings contained
    *  in this map with function <code>f</code>.
    *
-   * @param f
+   * @param f  The transformation to apply
    */
-  def map(f: Pair[A, B] => B): Unit = elements foreach {
-    case kv @ Pair(key, _) => update(key, f(kv))
+  def transform(f: (A, B) => B) {
+    elements foreach {
+      case Pair(key, value) => update(key, f(key, value))
+    }
   }
 
-  /** This method removes all the mappings for which the predicate
-   *  <code>p</code> returns <code>false</code>.
+  /** This method retains only those mappings for which the predicate
+   *  <code>p</code> returns <code>true</code>.
    *
-   * @param p
+   * @param p  The test predicate
    */
-  def filter(p: Pair[A, B] => Boolean): Unit = toList foreach {
-    case kv @ Pair(key, _) => if (!p(kv)) -=(key)
+  def retain(p: (A, B) => Boolean): Unit = toList foreach {
+    case Pair(key, value) => if (!p(key, value)) -=(key)
   }
 
   /** Send a message to this scriptable object.
@@ -140,37 +179,47 @@ trait Map[A, B] extends AnyRef
    */
   override def clone(): Map[A, B] = super.clone().asInstanceOf[Map[A, B]]
 
-  /** The hashCode method always yields an error, since it is not
-   *  safe to use mutable maps as keys in hash tables.
+  /** This method defines syntactic sugar for adding or modifying
+   *  mappings. It is typically used in the following way:
+   *  <pre>
+   *  map += key -> value;
+   *  </pre>
+   *  @deprecated   use <code>+={key, value}</code>
+   */
+  [deprecated] def +=(key: A): MapTo = new MapTo(key)
+
+  /** <code>incl</code> can be used to add many mappings at the same time
+   *  to the map. The method assumes that a mapping is represented
+   *  by a <code>Pair</code> object who's first component denotes the
+   *  key, and who's second component refers to the value.
    *
-   *  @return never.
-   */
-  override def hashCode(): Int = throw new UnsupportedOperationException("unsuitable as hash key")
-
-  /** Returns a string representation of this map which shows
-   *  all the mappings.
-   */
-  override def toString() =
-    if (size == 0)
-      "{}"
-    else
-      "{" + {
-        val iter = elements
-        var res = mappingToString(iter.next)
-        while (iter.hasNext) {
-          res = res + ", " + mappingToString(iter.next)
-        }
-        res
-      } + "}"
-
-  /** This method controls how a mapping is represented in the string
-   *  representation provided by method <code>toString</code>.
+   * @param mappings
+   * @deprecated   use <code>+=</code>
+   */
+  [deprecated] def incl(mappings: Pair[A, B]*): Unit = this ++= mappings.elements
+
+  /** This method will remove all the mappings for the given sequence
+   *  of keys from the map.
    *
+   * @param keys
+   * @deprecated    use <code>-=</code>
+   */
+  [deprecated] def excl(keys: A*): Unit = this --= keys.elements
+
+  /** This method removes all the mappings for which the predicate
+   *  <code>p</code> returns <code>false</code>.
+   *
+   * @deprecated   use retain instead
    * @param p
    */
-  def mappingToString(p: Pair[A, B]) = p._1.toString() + " -> " + p._2
+  [deprecated] override def filter(p: Pair[A, B] => Boolean): Iterable[Pair[A, B]] = {
+    toList foreach {
+      case kv @ Pair(key, _) => if (!p(kv)) -=(key)
+    }
+    this
+  }
 
-  class MapTo(key: A) {
+  [deprecated] class MapTo(key: A) {
     def ->(value: B): Unit = update(key, value)
   }
 
diff --git a/src/library/scala/collection/mutable/MapProxy.scala b/src/library/scala/collection/mutable/MapProxy.scala
index 20c326b968..2c612b9911 100644
--- a/src/library/scala/collection/mutable/MapProxy.scala
+++ b/src/library/scala/collection/mutable/MapProxy.scala
@@ -22,41 +22,37 @@ package scala.collection.mutable
  *  </p>
  *
  *  @author  Matthias Zenger
- *  @version 1.0, 21/07/2003
+ *  @author  Martin Odersky
+ *  @version 2.0, 31/12/2006
  */
 trait MapProxy[A, B] extends Map[A, B] with collection.MapProxy[A, B] {
 
   def self: Map[A, B]
 
-  def update(key: A, value: B): Unit = self.update(key, value)
-
-  override def ++=(map: Iterable[Pair[A, B]]): Unit = self ++= map
-
-  override def ++=(it: Iterator[Pair[A, B]]): Unit = self ++= it
-
-  override def incl(mappings: Pair[A, B]*): Unit = self ++= mappings
-
-  def -=(key: A): Unit = self -= key
-
-  override def --=(keys: Iterable[A]): Unit = self --= keys
-
-  override def --=(it: Iterator[A]): Unit = self --= it
-
-  override def excl(keys: A*): Unit = self --= keys
-
+  override def update(key: A, value: B): Unit = self.update(key, value)
+  override def += (kv: Pair[A, B]) = self += kv
+  override def += (kv1: Pair[A, B], kv2: Pair[A, B], kvs: Pair[A, B]*) = self.+=(kv1, kv2, kvs: _*)
+  override def ++= (kvs: Iterable[Pair[A, B]]) = self ++= kvs
+  override def ++= (kvs: Iterator[Pair[A, B]]) = self ++= kvs
+  override def + (kv: Pair[A, B]): Map[A, B] = self + kv
+  override def + (kv1: Pair[A, B], kv2: Pair[A, B], kvs: Pair[A, B]*): Map[A, B] = self.+(kv1, kv2, kvs: _*)
+  override def ++ (kvs: Iterable[Pair[A, B]]): Map[A, B] = self ++ kvs
+  override def ++ (kvs: Iterator[Pair[A, B]]): Map[A, B] = self ++ kvs
+  override def -= (key: A) = self -= key
+  override def -= (key1: A, key2: A, keys: A*) = self.-=(key1, key2, keys: _*)
+  override def --= (keys: Iterable[A]) = self --= keys
+  override def --= (keys: Iterator[A]) = self --= keys
+  override def - (key: A): Map[A, B] = self - key
+  override def - (key1: A, key2: A, keys: A*): Map[A, B] = self.-(key1, key2, keys: _*)
+  override def -- (keys: Iterable[A]): Map[A, B] = self -- keys
+  override def -- (keys: Iterator[A]): Map[A, B] = self -- keys
   override def clear: Unit = self.clear
-
-  override def map(f: Pair[A, B] => B): Unit = self.map(f)
-
-  override def filter(p: Pair[A, B] => Boolean): Unit = self.filter(p)
-
-  override def toString() = self.toString()
-
-  override def mappingToString(p: Pair[A, B]) = self.mappingToString(p)
-
+  override def transform(f: (A, B) => B) = self transform f
+  override def retain(p: (A, B) => Boolean): Unit = self retain p
   override def <<(cmd: Message[Pair[A, B]]): Unit = self << cmd
-
-  override def clone(): Map[A, B] = new MapProxy[A, B] {
-    def self = MapProxy.this.self.clone()
-  }
+  override def clone(): Map[A, B] = self.clone()
+  [deprecated] override def incl(mappings: Pair[A, B]*): Unit = self.incl(mappings: _*)
+  [deprecated] override def excl(keys: A*): Unit = self.excl(keys: _*)
+  [deprecated] override def map[C](f: Pair[A, B] => C): Iterable[C] = self map f
+  [deprecated] override def filter(p: Pair[A, B] => Boolean): Iterable[Pair[A, B]] = self filter p
 }
diff --git a/src/library/scala/collection/mutable/ObservableMap.scala b/src/library/scala/collection/mutable/ObservableMap.scala
index f6713125d9..55b0cb3ede 100644
--- a/src/library/scala/collection/mutable/ObservableMap.scala
+++ b/src/library/scala/collection/mutable/ObservableMap.scala
@@ -18,7 +18,8 @@ package scala.collection.mutable
  *  events of the type <code>Message</code>.
  *
  *  @author  Matthias Zenger
- *  @version 1.0, 08/07/2003
+ *  @author  Martin Odersky
+ *  @version 2.0, 31/12/2006
  */
 trait ObservableMap[A, B, This <: ObservableMap[A, B, This]] requires This
       extends Map[A, B]
@@ -39,7 +40,7 @@ trait ObservableMap[A, B, This <: ObservableMap[A, B, This]] requires This
       })
   }
 
-  abstract override def -=(key: A): Unit = get(key) match {
+  abstract override def -= (key: A): Unit = get(key) match {
     case None =>
     case Some(old) =>
       super.-=(key)
diff --git a/src/library/scala/collection/mutable/PriorityQueue.scala b/src/library/scala/collection/mutable/PriorityQueue.scala
index 8950a9fa0f..866348af1a 100644
--- a/src/library/scala/collection/mutable/PriorityQueue.scala
+++ b/src/library/scala/collection/mutable/PriorityQueue.scala
@@ -69,6 +69,17 @@ class PriorityQueue[A <% Ordered[A]] extends ResizableArray[A] {
     size = size + 1
   }
 
+  def +(elem: A): PriorityQueue[A] = { this += elem; this }
+
+  /** Add two or more elements to this set.
+   *  @param    elem1 the first element.
+   *  @param    kv2 the second element.
+   *  @param    kvs the remaining elements.
+   */
+  def += (elem1: A, elem2: A, elems: A*) { this += elem1; this += elem2; this ++= elems }
+
+  def + (elem1: A, elem2: A, elems: A*) = { this.+=(elem1, elem2, elems: _*); this }
+
   /** Adds all elements provided by an <code>Iterable</code> object
    *  into the priority queue.
    *
@@ -82,6 +93,10 @@ class PriorityQueue[A <% Ordered[A]] extends ResizableArray[A] {
    */
   def ++=(it: Iterator[A]): Unit = it foreach { e => this += e }
 
+  def ++(iter: Iterable[A]): PriorityQueue[A] = { this ++= iter; this }
+
+  def ++(iter: Iterator[A]): PriorityQueue[A] = { this ++= iter; this }
+
   /** Adds all elements to the queue.
    *
    *  @param  elems       the elements to add.
diff --git a/src/library/scala/collection/mutable/PriorityQueueProxy.scala b/src/library/scala/collection/mutable/PriorityQueueProxy.scala
index 6bc810dc1e..e9a5a866ed 100644
--- a/src/library/scala/collection/mutable/PriorityQueueProxy.scala
+++ b/src/library/scala/collection/mutable/PriorityQueueProxy.scala
@@ -20,7 +20,7 @@ package scala.collection.mutable
  *  @version 1.0, 03/05/2004
  */
 abstract class PriorityQueueProxy[A <% Ordered[A]] extends PriorityQueue[A]
-         with IterableProxy[A]
+         with SeqProxy[A]
 {
 
   def self: PriorityQueue[A]
diff --git a/src/library/scala/collection/mutable/ResizableArray.scala b/src/library/scala/collection/mutable/ResizableArray.scala
index 5d3fd7ecfd..acd8d53179 100644
--- a/src/library/scala/collection/mutable/ResizableArray.scala
+++ b/src/library/scala/collection/mutable/ResizableArray.scala
@@ -11,9 +11,9 @@
 
 package scala.collection.mutable
 
-
 /** This class is used internally to implement data structures that
  *  are based on resizable arrays.
+ *  //todo enrich with more efficient operations
  *
  *  @author  Matthias Zenger, Burak Emir
  *  @version 1.0, 03/05/2004
@@ -33,11 +33,20 @@ trait ResizableArray[A] extends Seq[A] {
 
   def apply(i: Int) = array(i)
 
-  override def toArray[B >: A]: Array[B] = {
-    val narr = new Array[B](size)
-    Array.copy(array, 0, narr, 0, size)
-    narr
-  }
+  /** Fills the given array <code>xs</code> with the elements of
+   *  this sequence starting at position <code>start</code>.
+   *
+   *  @param  xs the array to fill.
+   *  @param  start starting index.
+   */
+  override def copyToArray[B >: A](xs: Array[B], start: Int): Unit =
+    Array.copy(array, 0, xs, start, size)
+
+  /** Copy all elements to a buffer
+   *  @param   The buffer to which elements are copied
+   */
+  override def copyToBuffer[B >: A](dest: Buffer[B]): Unit =
+    dest.++=(array.asInstanceOf[Array[B]], 0, size)
 
   /** Returns a new iterator over all elements of this resizable array.
    */
diff --git a/src/library/scala/collection/mutable/Set.scala b/src/library/scala/collection/mutable/Set.scala
index 825102475f..26a827dcd9 100644
--- a/src/library/scala/collection/mutable/Set.scala
+++ b/src/library/scala/collection/mutable/Set.scala
@@ -15,85 +15,162 @@ package scala.collection.mutable
 /** This class represents mutable sets. Concrete set implementations
  *  just have to provide functionality for the abstract methods in
  *  <a href="../Set.html" target="contentFrame">
- *  <code>scala.collection.Set</code></a> as well as for <code>add</code>,
- *  <code>remove</code>, and <code>clear</code>.
+ *  <code>scala.collection.Set</code></a> as well as for <code>+=</code>,
+ *  <code>-= and <code>clear</code>.
  *
  *  @author  Matthias Zenger
  *  @version 1.1, 09/05/2004
  */
 [cloneable]
-trait Set[A] extends AnyRef with collection.Set[A]
-      with Scriptable[Message[A]]
-{
+trait Set[A] extends collection.Set[A] with Scriptable[Message[A]] {
 
   /** This method allows one to add or remove an element <code>elem</code>
    *  from this set depending on the value of parameter <code>included</code>.
    *  Typically, one would use the following syntax:
    *  <pre>set(elem) = true</pre>
    *
-   *  @param elem     ...
-   *  @param included ...
    */
   def update(elem: A, included: Boolean): Unit =
-    if (included) +=(elem) else -=(elem)
+    if (included) this += elem else this -= elem
 
-  /** This method adds a new element to the set.
+  /** Add a new element to the set.
    *
-   *  @param elem ...
+   *  @param elem the element to be added
    */
-  def +=(elem: A): Unit
+  def +=(elem: A)
 
-  /** This method will add all the elements provided by an iterator
+  /** Add two or more elements to this set.
+   *  @param    elem1 the first element.
+   *  @param    kv2 the second element.
+   *  @param    kvs the remaining elements.
+   */
+  def += (elem1: A, elem2: A, elems: A*) { this += elem1; this += elem2; this ++= elems }
+
+  /** Add all the elements provided by an iterator
    *  of the iterable object <code>that</code> to the set.
+   *  @param elems  the iterable object containing the elements to be added
+   */
+  def ++=(elems: Iterable[A]): Unit = ++=(elems.elements)
+
+  /** Add all the elements provided by an iterator
+   *  <code>elems</code> to the set.
+   *  @param elems  the iterator containing the elements to be added
+   */
+  def ++=(elems: Iterator[A]): Unit = elems foreach +=
+
+  /** Add a new element to the set.
+   *  @return the set itself with the element added.
    *
-   *  @param that ...
+   *  @param elem the element to be added
    */
-  def ++=(that: Iterable[A]): Unit = ++=(that.elements)
+  def + (elem: A): Set[A] = { +=(elem); this }
 
-  /** This method will add all the elements provided by an iterator
-   *  of the iterable object <code>that</code> to the set.
+  /** Add two or more elements to this set.
+   *  @param    elem1 the first element.
+   *  @param    kv2 the second element.
+   *  @param    kvs the remaining elements.
+   *  @return the set itself with the elements added.
+   */
+  def + (elem1: A, elem2: A, elems: A*): Set[A] = { this.+=(elem1, elem2, elems: _*); this }
+
+  /** Add all the elements provided by an iterator
+   *  of the iterable object <code>elems</code> to the set.
    *
-   *  @param it ...
+   *  @param elems  the iterable object containing the elements to be added
+   *  @return the set itself with the elements added.
+   */
+  def ++ (elems: Iterable[A]): Set[A] = { this ++= elems; this }
+
+  /** Add all the elements provided by an iterator
+   *  <code>elems</code> to the set.
+   *  @param elems  the iterator containing the elements to be added
    */
-  def ++=(it: Iterator[A]): Unit = it foreach +=
+  def ++ (elems: Iterator[A]): Set[A] = { this ++= elems; this }
 
   /** <code>incl</code> can be used to add many elements to the set
    *  at the same time.
+   *  @deprecated   use <code>++=</code> instead
+   */
+  [deprecated] def incl(elems: A*): Unit = ++=(elems.elements)
+
+  /** Removes a single element from a set.
+   *  @param elem  The element to be removed.
+   */
+  def -=(elem: A)
+
+  /** Remove two or more elements from this set.
+   *  @param    elem1 the first element.
+   *  @param    elem2 the second element.
+   *  @param    elems the remaining elements.
+   */
+  def -= (elem1: A, elem2: A, elems: A*) { this -= elem1; this -= elem2; this --= elems }
+
+  /** Remove all the elements provided by an iterator
+   *  of the iterable object <code>elems</code> from the set.
+   */
+  def --=(elems: Iterable[A]): Unit = --=(elems.elements)
+
+  /** Remove all the elements provided by an iterator
+   *  <code>elems</code> from the set.
+   */
+  def --=(elems: Iterator[A]): Unit = elems foreach -=
+
+  /** Remove a new element from the set.
+   *  @return the set itself with the element removed.
    *
-   *  @param elems ...
+   *  @param elem the element to be removed
    */
-  def incl(elems: A*): Unit = ++=(elems.elements)
+  def - (elem: A) { -=(elem); this }
 
-  /** <code>-=</code> can be used to remove a single element from
-   *  a set.
+  /** Remove two or more elements from this set.
+   *  @param    elem1 the first element.
+   *  @param    elem2 the second element.
+   *  @param    elems the remaining elements.
+   *  @return the set itself with the elements removed.
    */
-  def -=(elem: A): Unit
+  def - (elem1: A, elem2: A, elems: A*): Set[A] = { this.-=(elem1, elem2, elems: _*); this }
 
-  /** This method removes all the elements provided by the
-   *  the iterable object <code>that</code> from the set.
+  /** Remove all the elements provided by an iterator
+   *  of the iterable object <code>elems</code> from the set.
+   *
+   *  @param elems An iterable object containing the elements to remove from the set.
+   *  @return the set itself with the elements removed.
    */
-  def --=(that: Iterable[A]): Unit = --=(that.elements)
+  def -- (elems: Iterable[A]): Set[A] = { this --= elems; this }
 
-  /** This method removes all the elements provided by an iterator
-   *  <code>it</code> from the set.
+  /** Remove all the elements provided by an iterator
+   *  <code>elems</code> from the set.
+   *  @param elems An iterator containing the elements to remove from the set.
+   *  @return the set itself with the elements removed.
    */
-  def --=(it: Iterator[A]): Unit = it foreach -=
+  def -- (elems: Iterator[A]): Set[A] = { this --= elems; this }
 
   /** <code>excl</code> removes many elements from the set.
    */
-  def excl(elems: A*): Unit = --=(elems.elements)
+  [deprecated] def excl(elems: A*): Unit = --=(elems.elements)
 
   /** This method computes an intersection with set <code>that</code>.
    *  It removes all the elements that are not present in <code>that</code>.
    *
-   *  @param that ...
+   *  @param that the set to intersect with.
    */
-  def intersect(that: Set[A]): Unit = filter(that.contains)
+  def intersect(that: Set[A]): Unit = retain(that.contains)
 
   /** Method <code>filter</code> removes all elements from the set for
    *  which the predicate <code>p</code> yields the value <code>false</code>.
+   * @deprecated   use retain instead
    */
-  def filter(p: A => Boolean): Unit = toList.foreach {
+  [deprecated] override def filter(p: A => Boolean): Set[A] = {
+    toList.foreach {
+      elem => if (!p(elem)) -=(elem)
+    }
+    this
+  }
+
+  /** Method <code>retain removes all elements from the set for
+   *  which the predicate <code>p</code> yields the value <code>false</code>.
+   */
+  def retain(p: A => Boolean): Unit = toList.foreach {
     elem => if (!p(elem)) -=(elem)
   }
 
@@ -121,12 +198,4 @@ trait Set[A] extends AnyRef with collection.Set[A]
    *  @return  a set with the same elements.
    */
   override def clone(): Set[A] = super.clone().asInstanceOf[Set[A]]
-
-  /** The <code>hashCode</code> method always yields an error, since it is
-   *  not safe to use mutable stacks as keys in hash tables.
-   *
-   *  @return never.
-   */
-  override def hashCode(): Int =
-    throw new UnsupportedOperationException("unsuitable as hash key")
 }
diff --git a/src/library/scala/collection/mutable/SetProxy.scala b/src/library/scala/collection/mutable/SetProxy.scala
index 54c0c753b5..739f2398c3 100644
--- a/src/library/scala/collection/mutable/SetProxy.scala
+++ b/src/library/scala/collection/mutable/SetProxy.scala
@@ -46,7 +46,9 @@ trait SetProxy[A] extends Set[A] with collection.SetProxy[A] {
 
   def clear: Unit = self.clear
 
-  override def filter(p: A => Boolean): Unit =  self.filter(p)
+  override def retain(p: A => Boolean): Unit =  self.retain(p)
+
+  [deprecated] override def filter(p: A => Boolean) = self.filter(p)
 
   override def <<(cmd: Message[A]): Unit = self << cmd
 
diff --git a/src/library/scala/collection/mutable/SynchronizedMap.scala b/src/library/scala/collection/mutable/SynchronizedMap.scala
index d6b2fa65ef..88b8d72404 100644
--- a/src/library/scala/collection/mutable/SynchronizedMap.scala
+++ b/src/library/scala/collection/mutable/SynchronizedMap.scala
@@ -16,7 +16,8 @@ package scala.collection.mutable
  *  functions of the class into which it is mixed in.
  *
  *  @author  Matthias Zenger
- *  @version 1.0, 08/07/2003
+ *  @author  Martin Odersky
+ *  @version 2.0, 31/12/2006
  */
 trait SynchronizedMap[A, B] extends Map[A, B] {
 
@@ -48,12 +49,16 @@ trait SynchronizedMap[A, B] extends Map[A, B] {
     super.keys
   }
 
+  override def keySet: collection.Set[A] = synchronized {
+    super.keySet
+  }
+
   override def values: Iterator[B] = synchronized {
     super.values
   }
 
-  override def foreach(f: Pair[A, B] => Unit) = synchronized {
-    super.foreach(f)
+  abstract override def elements: Iterator[Pair[A, B]] = synchronized {
+    super.elements
   }
 
   override def toList: List[Pair[A, B]] = synchronized {
@@ -64,6 +69,19 @@ trait SynchronizedMap[A, B] extends Map[A, B] {
     super.update(key, value)
   }
 
+  override def += (kv: Pair[A, B]): Unit = synchronized {
+    super.+=(kv)
+  }
+
+  /** Add two or more key/value pairs to this map.
+   *  @param    kv1 the key/first value pair.
+   *  @param    kv2 the second key/first value pair.
+   *  @param    kvs the remaining key/first value pairs.
+   */
+  override def += (kv1: Pair[A, B], kv2: Pair[A, B], kvs: Pair[A, B]*): Unit = synchronized {
+    super.+=(kv1, kv2, kvs: _*)
+  }
+
   override def ++=(map: Iterable[Pair[A, B]]): Unit = synchronized {
     super.++=(map)
   }
@@ -72,14 +90,18 @@ trait SynchronizedMap[A, B] extends Map[A, B] {
     super.++=(it)
   }
 
-  override def incl(mappings: Pair[A, B]*): Unit = synchronized {
-    super.++=(mappings)
+  [deprecated] override def incl(mappings: Pair[A, B]*): Unit = synchronized {
+    super.incl(mappings: _*)
   }
 
   abstract override def -=(key: A): Unit = synchronized {
     super.-=(key)
   }
 
+  override def -= (key1: A, key2: A, keys: A*): Unit = synchronized {
+    super.-=(key1, key2, keys: _*)
+  }
+
   override def --=(keys: Iterable[A]): Unit = synchronized {
     super.--=(keys)
   }
@@ -88,19 +110,28 @@ trait SynchronizedMap[A, B] extends Map[A, B] {
     super.--=(it)
   }
 
-  override def excl(keys: A*): Unit = synchronized {
-    super.--=(keys)
+  [deprecated] override def excl(keys: A*): Unit = synchronized {
+    super.excl(keys: _*)
   }
 
   override def clear: Unit = synchronized {
     super.clear
   }
 
-  override def map(f: Pair[A, B] => B): Unit = synchronized {
+  override def transform(f: (A, B) => B): Unit = synchronized {
+    super.transform(f)
+  }
+
+  [deprecated] override def map[C](f: Pair[A, B] => C) = synchronized {
     super.map(f)
   }
 
-  override def filter(p: Pair[A, B] => Boolean): Unit = synchronized {
+  override def retain(p: (A, B) => Boolean): Unit = synchronized {
+    super.retain(p)
+  }
+
+  /** @deprecated  use retain instead */
+  [deprecated] override def filter(p: Pair[A, B] => Boolean) = synchronized {
     super.filter(p)
   }
 
@@ -108,6 +139,14 @@ trait SynchronizedMap[A, B] extends Map[A, B] {
     super.toString()
   }
 
+  override def equals(that: Any): Boolean = synchronized {
+    super.equals(that)
+  }
+
+  override def hashCode(): int = synchronized {
+    super.hashCode()
+  }
+
   override def <<(cmd: Message[Pair[A, B]]): Unit = synchronized {
     super.<<(cmd)
   }
diff --git a/src/library/scala/collection/mutable/SynchronizedSet.scala b/src/library/scala/collection/mutable/SynchronizedSet.scala
index fc222e6121..588f42853a 100644
--- a/src/library/scala/collection/mutable/SynchronizedSet.scala
+++ b/src/library/scala/collection/mutable/SynchronizedSet.scala
@@ -84,10 +84,14 @@ trait SynchronizedSet[A] extends Set[A] {
     super.foreach(f)
   }
 
-  override def filter(p: A => Boolean) = synchronized {
+  [deprecated] override def filter(p: A => Boolean) = synchronized {
     super.filter(p)
   }
 
+  override def retain(p: A => Boolean) = synchronized {
+    super.retain(p)
+  }
+
   override def toList: List[A] = synchronized {
     super.toList
   }
diff --git a/src/library/scala/deprecated.scala b/src/library/scala/deprecated.scala
new file mode 100755
index 0000000000..0b81e3224f
--- /dev/null
+++ b/src/library/scala/deprecated.scala
@@ -0,0 +1,18 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2002-2007, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |                                         **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id: remote.scala 9400 2006-11-28 17:22:45 +0000 (Tue, 28 Nov 2006) michelou $
+
+
+package scala
+
+/**
+ * An attribute that designates the definition to which it is applied as deprecated.
+ * Access to the member then generates a deprecated warning.
+ */
+class deprecated extends Attribute {}
diff --git a/src/library/scala/runtime/BoxedAnyArray.scala b/src/library/scala/runtime/BoxedAnyArray.scala
index 7242e5763a..431b3f0be5 100644
--- a/src/library/scala/runtime/BoxedAnyArray.scala
+++ b/src/library/scala/runtime/BoxedAnyArray.scala
@@ -27,7 +27,7 @@ final class BoxedAnyArray(val length: Int) extends BoxedArray {
   private var unboxed: AnyRef = null
   private var elemClass: Class = null
 
-  def apply(index: Int): AnyRef = synchronized {
+  def apply(index: Int): Any = synchronized {
     if (unboxed eq null)
       boxed(index);
     else if (elemClass eq ScalaRunTime.IntTYPE)
@@ -50,7 +50,8 @@ final class BoxedAnyArray(val length: Int) extends BoxedArray {
       unboxed.asInstanceOf[Array[AnyRef]](index)
   }
 
-  def update(index: Int, elem: AnyRef): Unit = synchronized {
+  def update(index: Int, _elem: Any): Unit = synchronized {
+    val elem = _elem.asInstanceOf[AnyRef]
     if (unboxed eq null)
       boxed(index) = elem
     else if (elemClass eq ScalaRunTime.IntTYPE)
@@ -234,7 +235,7 @@ final class BoxedAnyArray(val length: Int) extends BoxedArray {
     result
   }
 
-  override def filter(p: Any => Boolean): AnyRef = {
+  final override def filter(p: Any => Boolean): BoxedArray = {
     val include = new Array[Boolean](length)
     var len = 0
     var i = 0
diff --git a/src/library/scala/runtime/BoxedArray.scala b/src/library/scala/runtime/BoxedArray.scala
index 7e7d2ba88e..8559dfde18 100644
--- a/src/library/scala/runtime/BoxedArray.scala
+++ b/src/library/scala/runtime/BoxedArray.scala
@@ -14,34 +14,36 @@ package scala.runtime
 
 import Predef.Class
 import Predef.Error
+import collection.mutable.ArrayBuffer
 
 /**
  *  <p>A class representing <code>Array[T]</code></p>
  */
-abstract class BoxedArray extends PartialFunction[Int, AnyRef] with Seq[AnyRef] {
+abstract class BoxedArray extends Seq[Any] {
   /** The length of the array */
   def length: Int
 
   /** The element at given index */
-  def apply(index: Int): AnyRef
+  def apply(index: Int): Any
 
   /** Update element at given index */
-  def update(index: Int, elem: AnyRef): Unit
+  def update(index: Int, elem: Any): Unit
 
   /** Convert to Java array.
    *  @param elemTag    Either one of the tags ".N" where N is the name of a primitive type
    *                    (@see ScalaRunTime), or a full class name.
    */
+  //todo: remove
   def unbox(elemTag: String): AnyRef
 
   def unbox(elemClass: Class): AnyRef
 
   override def isDefinedAt(x: Int): Boolean   =  0 <= x && x < length
 
-  def elements = new Iterator[AnyRef] {
+  def elements = new Iterator[Any] {
     var index = 0
     def hasNext: Boolean = index < length
-    def next: AnyRef = { val i = index; index = i + 1; apply(i) }
+    def next: Any = { val i = index; index = i + 1; apply(i) }
   }
 
   /** The underlying array value
@@ -55,18 +57,25 @@ abstract class BoxedArray extends PartialFunction[Int, AnyRef] with Seq[AnyRef]
     Array.copy(value, from, dest, to, len)
   }
 
-  override def toArray[b>:AnyRef]: Array[b] = {
-    val len = length
-    val res = new Array[b](len)
-    copyTo(0, res, 0, len)
-    res
-  }
+  /** Fills the given array <code>xs</code> with the elements of
+   *  this sequence starting at position <code>start</code>.
+   *
+   *  @param  xs the array to fill.
+   *  @param  start starting index.
+   *  @pre    the array must be large enough to hold all elements.
+   */
+  override def copyToArray[B](xs: Array[B], start: Int): Unit =
+    copyTo(0, xs, start, length)
+
+  // todo: add a copyToBuffer
 
+  // todo: eliminate
   def subArray(from: Int, end: Int): AnyRef
 
-  def filter(p: Any => Boolean): AnyRef
+  override def slice(from: Int, len: Int): Seq[Object] =
+    subArray(from, from + len).asInstanceOf[Seq[Object]]
 
-  final def map[b](f: Any => b): Array[b] = {
+  final override def map[b](f: Any => b): Array[b] = {
     val len = length
     val result = new Array[b](len)
     var i = 0
@@ -77,22 +86,22 @@ abstract class BoxedArray extends PartialFunction[Int, AnyRef] with Seq[AnyRef]
     result
   }
 
-  final def flatMap[b](f: Any => Array[b]): Array[b] = {
+  final override def flatMap[b](f: Any => Iterable[b]): Array[b] = {
+    val buf = new ArrayBuffer[b]
     val len = length
-    val tmp = new Array[Array[b]](len)
     var i = 0
     while (i < len) {
-      tmp(i) = f(apply(i))
+      buf ++= f(apply(i))
       i = i + 1
     }
-    Array.concat(tmp: _*)
+    buf.toArray
   }
 
-  final def zip[b](that: Array[b]): Array[Tuple2[AnyRef,b]] = {
+  final def zip[b](that: Array[b]): Array[Tuple2[Any,b]] = {
     val len = length
     if(len != that.length)
       throw new Error("zipping arrays of different length")
-    val result = new Array[Tuple2[AnyRef,b]](len)
+    val result = new Array[Tuple2[Any,b]](len)
     var i = 0
     while (i < len) {
       result(i) = new Tuple2(this(i), that(i))
@@ -101,9 +110,9 @@ abstract class BoxedArray extends PartialFunction[Int, AnyRef] with Seq[AnyRef]
     result
   }
 
-  final def zipWithIndex: Array[Tuple2[AnyRef,Int]] = {
+  final def zipWithIndex: Array[Tuple2[Any,Int]] = {
     val len = length
-    val result = new Array[Tuple2[AnyRef,Int]](len)
+    val result = new Array[Tuple2[Any,Int]](len)
     var i = 0
     while (i < len) {
       result(i) = new Tuple2(this(i), i)
diff --git a/src/library/scala/runtime/BoxedBooleanArray.scala b/src/library/scala/runtime/BoxedBooleanArray.scala
index 85393f94b1..1dbf6bb987 100644
--- a/src/library/scala/runtime/BoxedBooleanArray.scala
+++ b/src/library/scala/runtime/BoxedBooleanArray.scala
@@ -19,10 +19,10 @@ final class BoxedBooleanArray(val value: Array[Boolean]) extends BoxedArray {
 
   def length: Int = value.length
 
-  def apply(index: Int): AnyRef = Boolean.box(value(index))
+  def apply(index: Int): Any = Boolean.box(value(index))
 
-  def update(index: Int, elem: AnyRef): Unit = {
-    value(index) = Boolean.unbox(elem)
+  def update(index: Int, elem: Any): Unit = {
+    value(index) = Boolean.unbox(elem.asInstanceOf[AnyRef])
   }
 
   def unbox(elemTag: String): AnyRef = value
@@ -40,7 +40,7 @@ final class BoxedBooleanArray(val value: Array[Boolean]) extends BoxedArray {
     result
   }
 
-  def filter(p: Any => Boolean): Array[Boolean] = {
+  final override def filter(p: Any => Boolean): BoxedArray = {
     val include = new Array[Boolean](value.length)
     var len = 0
     var i = 0
@@ -55,6 +55,6 @@ final class BoxedBooleanArray(val value: Array[Boolean]) extends BoxedArray {
       if (include(i)) { result(len) = value(i); len = len + 1 }
       i = i + 1
     }
-    result
+    new BoxedBooleanArray(result)
   }
 }
diff --git a/src/library/scala/runtime/BoxedByteArray.scala b/src/library/scala/runtime/BoxedByteArray.scala
index 0fb36007ae..62407d6974 100644
--- a/src/library/scala/runtime/BoxedByteArray.scala
+++ b/src/library/scala/runtime/BoxedByteArray.scala
@@ -19,10 +19,10 @@ final class BoxedByteArray(val value: Array[Byte]) extends BoxedArray {
 
   def length: Int = value.length
 
-  def apply(index: Int): AnyRef = Byte.box(value(index))
+  def apply(index: Int): Any = Byte.box(value(index))
 
-  def update(index: Int, elem: AnyRef): Unit = {
-    value(index) = Byte.unbox(elem)
+  def update(index: Int, elem: Any): Unit = {
+    value(index) = Byte.unbox(elem.asInstanceOf[AnyRef])
   }
 
   def unbox(elemTag: String): AnyRef = value
@@ -40,7 +40,7 @@ final class BoxedByteArray(val value: Array[Byte]) extends BoxedArray {
     result
   }
 
-  def filter(p: Any => Boolean): Array[Byte] = {
+  final override def filter(p: Any => Boolean): BoxedArray = {
     val include = new Array[Boolean](value.length)
     var len = 0
     var i = 0
@@ -55,6 +55,6 @@ final class BoxedByteArray(val value: Array[Byte]) extends BoxedArray {
       if (include(i)) { result(len) = value(i); len = len + 1 }
       i = i + 1
     }
-    result
+    new BoxedByteArray(result)
   }
 }
diff --git a/src/library/scala/runtime/BoxedCharArray.scala b/src/library/scala/runtime/BoxedCharArray.scala
index 87bc56391d..1f823853eb 100644
--- a/src/library/scala/runtime/BoxedCharArray.scala
+++ b/src/library/scala/runtime/BoxedCharArray.scala
@@ -19,10 +19,10 @@ final class BoxedCharArray(val value: Array[Char]) extends BoxedArray {
 
   def length: Int = value.length;
 
-  def apply(index: Int): AnyRef = Char.box(value(index));
+  def apply(index: Int): Any = Char.box(value(index));
 
-  def update(index: Int, elem: AnyRef): Unit = {
-    value(index) = Char.unbox(elem)
+  def update(index: Int, elem: Any): Unit = {
+    value(index) = Char.unbox(elem.asInstanceOf[AnyRef])
   }
 
   def unbox(elemTag: String): AnyRef = value;
@@ -41,7 +41,7 @@ final class BoxedCharArray(val value: Array[Char]) extends BoxedArray {
     result
   }
 
-  def filter(p: Any => Boolean): Array[Char] = {
+  final override def filter(p: Any => Boolean): BoxedArray = {
     val include = new Array[Boolean](value.length);
     var len = 0;
     var i = 0;
@@ -56,6 +56,6 @@ final class BoxedCharArray(val value: Array[Char]) extends BoxedArray {
       if (include(i)) { result(len) = value(i); len = len + 1 }
       i = i + 1
     }
-    result
+    new BoxedCharArray(result)
   }
 }
diff --git a/src/library/scala/runtime/BoxedDoubleArray.scala b/src/library/scala/runtime/BoxedDoubleArray.scala
index 4744c56774..eca804d76c 100644
--- a/src/library/scala/runtime/BoxedDoubleArray.scala
+++ b/src/library/scala/runtime/BoxedDoubleArray.scala
@@ -19,10 +19,10 @@ final class BoxedDoubleArray(val value: Array[Double]) extends BoxedArray {
 
   def length: Int = value.length
 
-  def apply(index: Int): AnyRef = Double.box(value(index))
+  def apply(index: Int): Any = Double.box(value(index))
 
-  def update(index: Int, elem: AnyRef): Unit = {
-    value(index) = Double.unbox(elem)
+  def update(index: Int, elem: Any): Unit = {
+    value(index) = Double.unbox(elem.asInstanceOf[AnyRef])
   }
 
   def unbox(elemTag: String): AnyRef = value
@@ -40,7 +40,7 @@ final class BoxedDoubleArray(val value: Array[Double]) extends BoxedArray {
     result
   }
 
-  def filter(p: Any => Boolean): Array[Double] = {
+  final override def filter(p: Any => Boolean): BoxedArray = {
     val include = new Array[Boolean](value.length)
     var len = 0
     var i = 0
@@ -55,6 +55,6 @@ final class BoxedDoubleArray(val value: Array[Double]) extends BoxedArray {
       if (include(i)) { result(len) = value(i); len = len + 1 }
       i = i + 1
     }
-    result
+    new BoxedDoubleArray(result)
   }
 }
diff --git a/src/library/scala/runtime/BoxedFloatArray.scala b/src/library/scala/runtime/BoxedFloatArray.scala
index a80643951a..0505a2545d 100644
--- a/src/library/scala/runtime/BoxedFloatArray.scala
+++ b/src/library/scala/runtime/BoxedFloatArray.scala
@@ -19,10 +19,10 @@ final class BoxedFloatArray(val value: Array[Float]) extends BoxedArray {
 
   def length: Int = value.length
 
-  def apply(index: Int): AnyRef = Float.box(value(index))
+  def apply(index: Int): Any = Float.box(value(index))
 
-  def update(index: Int, elem: AnyRef): Unit = {
-    value(index) = Float.unbox(elem)
+  def update(index: Int, elem: Any): Unit = {
+    value(index) = Float.unbox(elem.asInstanceOf[AnyRef])
   }
 
   def unbox(elemTag: String): AnyRef = value
@@ -40,7 +40,7 @@ final class BoxedFloatArray(val value: Array[Float]) extends BoxedArray {
     result
   }
 
-  def filter(p: Any => Boolean): Array[Float] = {
+  final override def filter(p: Any => Boolean): BoxedArray = {
     val include = new Array[Boolean](value.length)
     var len = 0
     var i = 0
@@ -55,6 +55,6 @@ final class BoxedFloatArray(val value: Array[Float]) extends BoxedArray {
       if (include(i)) { result(len) = value(i); len = len + 1 }
       i = i + 1
     }
-    result
+    new BoxedFloatArray(result)
   }
 }
diff --git a/src/library/scala/runtime/BoxedIntArray.scala b/src/library/scala/runtime/BoxedIntArray.scala
index d3c02b2627..2519075a3a 100644
--- a/src/library/scala/runtime/BoxedIntArray.scala
+++ b/src/library/scala/runtime/BoxedIntArray.scala
@@ -19,10 +19,10 @@ final class BoxedIntArray(val value: Array[Int]) extends BoxedArray {
 
   def length: Int = value.length
 
-  def apply(index: Int): AnyRef = Int.box(value(index))
+  def apply(index: Int): Any = Int.box(value(index))
 
-  def update(index: Int, elem: AnyRef): Unit = {
-    value(index) = Int.unbox(elem)
+  def update(index: Int, elem: Any): Unit = {
+    value(index) = Int.unbox(elem.asInstanceOf[AnyRef])
   }
 
   def unbox(elemTag: String): AnyRef = value
@@ -40,7 +40,7 @@ final class BoxedIntArray(val value: Array[Int]) extends BoxedArray {
     result
   }
 
-  def filter(p: Any => Boolean): Array[Int] = {
+  final override def filter(p: Any => Boolean): BoxedArray = {
     val include = new Array[Boolean](value.length)
     var len = 0
     var i = 0
@@ -55,6 +55,6 @@ final class BoxedIntArray(val value: Array[Int]) extends BoxedArray {
       if (include(i)) { result(len) = value(i); len = len + 1 }
       i = i + 1
     }
-    result
+    new BoxedIntArray(result)
   }
 }
diff --git a/src/library/scala/runtime/BoxedLongArray.scala b/src/library/scala/runtime/BoxedLongArray.scala
index 7a2a70758a..f82d1711e1 100644
--- a/src/library/scala/runtime/BoxedLongArray.scala
+++ b/src/library/scala/runtime/BoxedLongArray.scala
@@ -19,10 +19,10 @@ final class BoxedLongArray(val value: Array[Long]) extends BoxedArray {
 
   def length: Int = value.length
 
-  def apply(index: Int): AnyRef = Long.box(value(index))
+  def apply(index: Int): Any = Long.box(value(index))
 
-  def update(index: Int, elem: AnyRef): Unit = {
-    value(index) = Long.unbox(elem)
+  def update(index: Int, elem: Any): Unit = {
+    value(index) = Long.unbox(elem.asInstanceOf[AnyRef])
   }
 
   def unbox(elemTag: String): AnyRef = value
@@ -40,7 +40,7 @@ final class BoxedLongArray(val value: Array[Long]) extends BoxedArray {
     result
   }
 
-  def filter(p: Any => Boolean): Array[Long] = {
+  final override def filter(p: Any => Boolean): BoxedArray = {
     val include = new Array[Boolean](value.length)
     var len = 0
     var i = 0
@@ -55,6 +55,6 @@ final class BoxedLongArray(val value: Array[Long]) extends BoxedArray {
       if (include(i)) { result(len) = value(i); len = len + 1 }
       i = i + 1
     }
-    result
+    new BoxedLongArray(result)
   }
 }
diff --git a/src/library/scala/runtime/BoxedObjectArray.scala b/src/library/scala/runtime/BoxedObjectArray.scala
index e603db8ab8..98f58ea92c 100644
--- a/src/library/scala/runtime/BoxedObjectArray.scala
+++ b/src/library/scala/runtime/BoxedObjectArray.scala
@@ -20,9 +20,11 @@ final class BoxedObjectArray(val value: Array[AnyRef]) extends BoxedArray {
 
   def length: Int = value.length
 
-  def apply(index: Int): AnyRef = value(index)
+  def apply(index: Int): Any = value(index)
 
-  def update(index: Int, elem: AnyRef): Unit = { value(index) = elem }
+  def update(index: Int, elem: Any): Unit = {
+    value(index) = elem.asInstanceOf[AnyRef]
+  }
 
   def unbox(elemTag: String): AnyRef = value
   def unbox(elemClass: Class): AnyRef = value
@@ -43,7 +45,7 @@ final class BoxedObjectArray(val value: Array[AnyRef]) extends BoxedArray {
     result
   }
 
-  override def filter(p: Any => Boolean): Array[AnyRef] = {
+  final override def filter(p: Any => Boolean): BoxedArray = {
     val include = new Array[Boolean](value.length)
     var len = 0
     var i = 0
@@ -58,6 +60,6 @@ final class BoxedObjectArray(val value: Array[AnyRef]) extends BoxedArray {
       if (include(i)) { result(len) = value(i); len = len + 1 }
       i = i + 1
     }
-    result
+    new BoxedObjectArray(result)
   }
 }
diff --git a/src/library/scala/runtime/BoxedShortArray.scala b/src/library/scala/runtime/BoxedShortArray.scala
index 6adea4029b..c3bc7a6125 100644
--- a/src/library/scala/runtime/BoxedShortArray.scala
+++ b/src/library/scala/runtime/BoxedShortArray.scala
@@ -19,10 +19,10 @@ final class BoxedShortArray(val value: Array[Short]) extends BoxedArray {
 
   def length: Int = value.length
 
-  def apply(index: Int): AnyRef = Short.box(value(index))
+  def apply(index: Int): Any = Short.box(value(index))
 
-  def update(index: Int, elem: AnyRef): Unit = {
-    value(index) = Short.unbox(elem)
+  def update(index: Int, elem: Any): Unit = {
+    value(index) = Short.unbox(elem.asInstanceOf[AnyRef])
   }
 
   def unbox(elemTag: String): AnyRef = value
@@ -40,7 +40,7 @@ final class BoxedShortArray(val value: Array[Short]) extends BoxedArray {
     result
   }
 
-  def filter(p: Any => Boolean): Array[Short] = {
+  final override def filter(p: Any => Boolean): BoxedArray = {
     val include = new Array[Boolean](value.length)
     var len = 0
     var i = 0
@@ -55,6 +55,6 @@ final class BoxedShortArray(val value: Array[Short]) extends BoxedArray {
       if (include(i)) { result(len) = value(i); len = len + 1 }
       i = i + 1
     }
-    result
+    new BoxedShortArray(result)
   }
 }
diff --git a/src/library/scala/util/automata/WordBerrySethi.scala b/src/library/scala/util/automata/WordBerrySethi.scala
index e553fde90d..90fad21452 100644
--- a/src/library/scala/util/automata/WordBerrySethi.scala
+++ b/src/library/scala/util/automata/WordBerrySethi.scala
@@ -149,7 +149,7 @@ abstract class WordBerrySethi extends BaseBerrySethi {
   }
 
   protected def initializeAutom(): Unit = {
-    finals   = immutable.TreeMap.Empty[Int, Int] // final states
+    finals   = immutable.TreeMap.empty[Int, Int] // final states
     deltaq   = new Array[mutable.HashMap[_labelT, List[Int]]](pos) // delta
     defaultq = new Array[List[Int]](pos) // default transitions
 
diff --git a/src/library/scala/xml/MetaData.scala b/src/library/scala/xml/MetaData.scala
index 37cf9d996d..cc2b683b18 100644
--- a/src/library/scala/xml/MetaData.scala
+++ b/src/library/scala/xml/MetaData.scala
@@ -116,7 +116,7 @@ abstract class MetaData extends Iterable[MetaData] {
   def equals1(that: MetaData): Boolean
 
   /** filters this sequence of meta data */
-  def filter(f: MetaData => Boolean): MetaData = {
+  override def filter(f: MetaData => Boolean): MetaData = {
     if (f(this)) copy(next filter f) else next filter f
   }
 
diff --git a/src/library/scala/xml/NodeSeq.scala b/src/library/scala/xml/NodeSeq.scala
index ad30b31f94..abcfe7e33c 100644
--- a/src/library/scala/xml/NodeSeq.scala
+++ b/src/library/scala/xml/NodeSeq.scala
@@ -161,7 +161,7 @@ abstract class NodeSeq extends Seq[Node] {
     y
   }
 
-  def filter(f: Node => Boolean): NodeSeq = {
+  override def filter(f: Node => Boolean): NodeSeq = {
     val x = toList filter f
     x
   }
diff --git a/src/library/scala/xml/Null.scala b/src/library/scala/xml/Null.scala
index a95fe4f389..ef15e0973f 100644
--- a/src/library/scala/xml/Null.scala
+++ b/src/library/scala/xml/Null.scala
@@ -24,7 +24,7 @@ case object Null extends MetaData {
   /** returns its argument */
   def copy(next: MetaData) = next
 
-  override def elements = Iterator.empty[MetaData]
+  override def elements = Iterator.empty
 
   override def filter(f: MetaData => Boolean): MetaData = this
 
diff --git a/test/files/jvm/xml01.scala b/test/files/jvm/xml01.scala
index 8c99cfd358..b0a3044fc1 100644
--- a/test/files/jvm/xml01.scala
+++ b/test/files/jvm/xml01.scala
@@ -177,7 +177,7 @@ object Test {
         //Text("John Mitchell"),
         Elem(null,"title",e,sc,Text("Foundations of Programming Languages"))
         //Text("Foundations of Programming Languages")
-      )
+      ): Seq[Node]
   );
 
     // test group node
diff --git a/test/files/neg/bug846.check b/test/files/neg/bug846.check
new file mode 100644
index 0000000000..b60b4c7125
--- /dev/null
+++ b/test/files/neg/bug846.check
@@ -0,0 +1,6 @@
+bug846.scala:9 error: type mismatch;
+ found   : scala.Null(null)
+ required: B
+    if (a != null) f(a) else null
+                             ^
+one error found
diff --git a/test/files/neg/bug846.scala b/test/files/neg/bug846.scala
new file mode 100755
index 0000000000..be105a71aa
--- /dev/null
+++ b/test/files/neg/bug846.scala
@@ -0,0 +1,13 @@
+package test;
+trait Test {
+  type Bar;
+  trait FooImpl;
+  trait Bob {
+    def bar : Bar with FooImpl;
+  }
+  def ifn[A,B](a : A)(f : A => B): B =
+    if (a != null) f(a) else null
+  val bob : Bob = null;
+  val bar = ifn(bob)(.bar);
+  assert(bar == null);
+}
diff --git a/test/files/pos/bounds.scala b/test/files/pos/bounds.scala
new file mode 100755
index 0000000000..5bc5cf89dc
--- /dev/null
+++ b/test/files/pos/bounds.scala
@@ -0,0 +1,11 @@
+trait Map[A, +C] {
+  def ++ [B1 >: C] (kvs: Iterable[Pair[A, B1]]): Map[A, B1] = this
+  def ++ [B1 >: C] (kvs: Iterator[Pair[A, B1]]): Map[A, B1] = this
+}
+
+class ListMap[A, +B] extends Map[A, B] {}
+
+object ListMap {
+  def empty[X, Y] = new ListMap[X, Y]
+  def apply[A1, B2](elems: Pair[A1, B2]*): Map[A1, B2] = empty[A1,B2].++(elems.elements)
+}
diff --git a/test/files/pos/nested2.scala b/test/files/pos/nested2.scala
new file mode 100755
index 0000000000..302688a0ef
--- /dev/null
+++ b/test/files/pos/nested2.scala
@@ -0,0 +1,9 @@
+class C[A] {
+  class D[B] {
+  }
+}
+
+object Test {
+  val x = new C[String]
+  val y: C[String]#D[int] = new x.D[int]
+}
diff --git a/test/files/run/Course-2002-10.scala b/test/files/run/Course-2002-10.scala
index 258b6dc8fd..79c760afee 100644
--- a/test/files/run/Course-2002-10.scala
+++ b/test/files/run/Course-2002-10.scala
@@ -31,9 +31,9 @@ object M1 {
     Stream.cons(s.head, partialSums(s.tail) map (x => x + s.head));
 
   def euler(s: Stream[double]): Stream[double] = {
-    val nm1 = s at 0;
-    val n   = s at 1;
-    val np1 = s at 2;
+    val nm1 = s apply 0;
+    val n   = s apply 1;
+    val np1 = s apply 2;
     Stream.cons(np1 - ((np1 - n)*(np1 - n) / (nm1 - 2*n + np1)),euler(s.tail))
   };
 
@@ -68,9 +68,9 @@ object M1 {
     var i = 0;
     while (i < 10) {
       Console.print("pi("+i+") = ");
-      Console.print(str(pi0.at(i)) + ", ");
-      Console.print(str(pi1.at(i)) + ", ");
-      Console.print(str(pi2.at(i)) + "\n");
+      Console.print(str(pi0.apply(i)) + ", ");
+      Console.print(str(pi1.apply(i)) + ", ");
+      Console.print(str(pi2.apply(i)) + "\n");
       i = i + 1;
     }
     Console.print("pi    = ");
@@ -81,9 +81,9 @@ object M1 {
     i = 0;
     while (i < 10) {
       Console.print("ln("+i+") = ");
-      Console.print(str(ln0.at(i)) + ", ");
-      Console.print(str(ln1.at(i)) + ", ");
-      Console.print(str(ln2.at(i)) + "\n");
+      Console.print(str(ln0.apply(i)) + ", ");
+      Console.print(str(ln1.apply(i)) + ", ");
+      Console.print(str(ln2.apply(i)) + "\n");
       i = i + 1;
     }
     Console.print("ln    = ");
diff --git a/test/files/run/collections.check b/test/files/run/collections.check
new file mode 100644
index 0000000000..ad92767fa6
--- /dev/null
+++ b/test/files/run/collections.check
@@ -0,0 +1,28 @@
+***** immutable.ListSet:
+test1: 14005
+test2: 25005003
+test3: 25005003
+***** immutable.TreeSet:
+test1: 14005
+test2: 25005003
+test3: 25005003
+***** mutable.HashSet:
+test1: 14005
+test2: 25005003
+test3: 25005003
+***** immutable.ListMap:
+test1: 14005
+test2: 1013003
+test3: 1013003
+***** immutable.TreeMap:
+test1: 14005
+test2: 1013003
+test3: 1013003
+***** immutable.UnBalancedTreeMap:
+test1: 14005
+test2: 1013003
+test3: 1013003
+***** mutable.HashMap:
+test1: 14005
+test2: 25005003
+test3: 25005003
diff --git a/test/files/run/collections.scala b/test/files/run/collections.scala
new file mode 100755
index 0000000000..5e97b2df38
--- /dev/null
+++ b/test/files/run/collections.scala
@@ -0,0 +1,100 @@
+import collection._
+
+object Test extends Application {
+
+  val printTime = false
+
+  def sum[A](xs: Iterable[int]) = (0 /: xs)((x, y) => x + y)
+
+  def time(op: => unit): unit = {
+    val start = System.currentTimeMillis;
+    op
+    if (printTime) Console.println("  time = "+(System.currentTimeMillis - start)+"ms")
+  }
+
+  def test(msg: String, s0: collection.immutable.Set[int]) = {
+    Console.println("***** "+msg+":")
+    var s = s0
+    s = s + 2
+    s = s + (3, 4000, 10000)
+    Console.println("test1: "+sum(s))
+    time {
+      s = s ++ (List.range(0, 5000) map (2*))
+      Console.println("test2: "+sum(s))
+    }
+    time {
+      var x = 0
+      for (val i <- (0 to 10000))
+        if (s contains i) x = x + i
+      Console.println("test3: "+x)
+    }
+  }
+
+  def test(msg: String, s0: collection.mutable.Set[int]) = {
+    Console.println("***** "+msg+":")
+    var s = s0
+    s = s + 2
+    s = s + (3, 4000, 10000)
+    Console.println("test1: "+sum(s))
+    time {
+      s = s ++ (List.range(0, 5000) map (2*))
+      Console.println("test2: "+sum(s))
+    }
+    time {
+      var x = 0
+      for (val i <- (0 to 10000))
+        if (s contains i) x = x + i
+      Console.println("test3: "+x)
+    }
+  }
+
+  def test(msg: String, s0: collection.immutable.Map[int, int]) = {
+    Console.println("***** "+msg+":")
+    var s = s0
+    s = s + (2 -> 2)
+    s = s + (3 -> 3, 4000 -> 4000, 10000 -> 10000)
+    Console.println("test1: "+sum(s map (._2)))
+    time {
+      s = s ++ (List.range(0, 1000) map (x => x * 2 -> x * 2))
+      Console.println("test2: "+sum(s map (._2)))
+    }
+    time {
+      var x = 0
+      for (val i <- (0 to 10000))
+        s get i match {
+          case Some(i) => x = x + i
+          case None =>
+        }
+      Console.println("test3: "+x)
+    }
+  }
+
+  def test(msg: String, s0: collection.mutable.Map[int, int]) = {
+    Console.println("***** "+msg+":")
+    var s = s0
+    s = s + (2 -> 2)
+    s = s + (3 -> 3, 4000 -> 4000, 10000 -> 10000)
+    Console.println("test1: "+sum(s map (._2)))
+    time {
+      s = s ++ (List.range(0, 5000) map (x => x * 2 -> x * 2))
+      Console.println("test2: "+sum(s map (._2)))
+    }
+    time {
+      var x = 0
+      for (val i <- (0 to 10000))
+        s get i match {
+          case Some(i) => x = x + i
+          case None =>
+        }
+      Console.println("test3: "+x)
+    }
+  }
+
+  test("immutable.ListSet", new immutable.ListSet[int])
+  test("immutable.TreeSet", new immutable.TreeSet[int])
+  test("mutable.HashSet", new mutable.HashSet[int])
+  test("immutable.ListMap", new immutable.ListMap[int, int])
+  test("immutable.TreeMap", new immutable.TreeMap[int, int])
+  test("immutable.UnBalancedTreeMap", new immutable.UnbalancedTreeMap[int, int])
+  test("mutable.HashMap", new mutable.HashMap[int, int])
+}
diff --git a/test/files/run/infix.check b/test/files/run/infix.check
new file mode 100644
index 0000000000..dd0457b776
--- /dev/null
+++ b/test/files/run/infix.check
@@ -0,0 +1,2 @@
+op(op(op(null,0,0),1,1),2,2)
+OK
diff --git a/test/files/run/infix.scala b/test/files/run/infix.scala
new file mode 100755
index 0000000000..9df07ac317
--- /dev/null
+++ b/test/files/run/infix.scala
@@ -0,0 +1,12 @@
+case class op(x: op, y: int, z: int) {
+  def op(y: int, z: int) = new op(this, y, z)
+}
+
+object Test extends Application {
+  val xs = new op(null, 0, 0) op (1, 1) op (2, 2)
+  Console.println(xs)
+  xs match {
+    case null op (0, 0) op (1, 1) op (2, 2) => Console.println("OK")
+  }
+}
+
diff --git a/test/files/run/tuples.check b/test/files/run/tuples.check
new file mode 100644
index 0000000000..731f2746c9
--- /dev/null
+++ b/test/files/run/tuples.check
@@ -0,0 +1,2 @@
+{1,abc,true}
+OK
diff --git a/test/files/run/tuples.scala b/test/files/run/tuples.scala
new file mode 100755
index 0000000000..c6dcda4af8
--- /dev/null
+++ b/test/files/run/tuples.scala
@@ -0,0 +1,8 @@
+object Test extends Application {
+  var xyz: {int, String, boolean} = _
+  xyz = { 1, "abc", true }
+  Console.println(xyz)
+  xyz match {
+    case { 1, "abc", true } => Console.println("OK")
+  }
+}