changed collection libraries

11 files changed, 170 insertions, 25 deletions

diff --git a/src/library/scala/Iterable.scala b/src/library/scala/Iterable.scala
index 13699db23a..7accb35f6c 100644
--- a/src/library/scala/Iterable.scala
+++ b/src/library/scala/Iterable.scala
@@ -99,6 +99,13 @@ trait Iterable[+A] {
     buf
   }
 
+  def ++ [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.
    *
diff --git a/src/library/scala/Seq.scala b/src/library/scala/Seq.scala
index df8ba7e35c..da45be6c9c 100644
--- a/src/library/scala/Seq.scala
+++ b/src/library/scala/Seq.scala
@@ -86,6 +86,13 @@ trait Seq[+A] extends AnyRef with PartialFunction[Int, A] with Iterable[A] {
     buf
   }
 
+  override def ++ [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>?
    *
    *  @return true, iff <code>x</code> is a legal sequence index.
diff --git a/src/library/scala/collection/Set.scala b/src/library/scala/collection/Set.scala
index 3d3cb9bece..951b6616aa 100644
--- a/src/library/scala/collection/Set.scala
+++ b/src/library/scala/collection/Set.scala
@@ -29,7 +29,7 @@ package scala.collection
  *  @author  Martin Odersky
  *  @version 2.0, 01/01/2007
  */
-trait Set[A] extends AnyRef with (A => Boolean) with Iterable[A] {
+trait Set[A] extends (A => Boolean) with Iterable[A] {
 
   /** Returns the number of elements in this set.
    *
diff --git a/src/library/scala/collection/immutable/Map.scala b/src/library/scala/collection/immutable/Map.scala
index 41f9126fd6..64e9e3e04f 100644
--- a/src/library/scala/collection/immutable/Map.scala
+++ b/src/library/scala/collection/immutable/Map.scala
@@ -73,7 +73,8 @@ trait Map[A, +B] extends collection.Map[A, B] {
    *  @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
+  def ++ [B1 >: B] (kvs: Iterable[Pair[A, B1]]): Map[A, B1] =
+    ((this: Map[A, B1]) /: kvs) ((m, kv) => m + kv)
 
   /** Add a sequence of key/value pairs to this map.
    *  @param    kvs the iterator containing all key/value pairs.
diff --git a/src/library/scala/collection/immutable/RedBlack.scala b/src/library/scala/collection/immutable/RedBlack.scala
index 67c933af57..c95b16dc67 100755
--- a/src/library/scala/collection/immutable/RedBlack.scala
+++ b/src/library/scala/collection/immutable/RedBlack.scala
@@ -67,6 +67,7 @@ abstract class RedBlack[A] {
     def elements: Iterator[Pair[A, B]] =
       left.elements append Iterator.single(Pair(key, value)) append right.elements
   }
+  [serializable]
   case object Empty extends Tree[Nothing] {
     def isEmpty = true
     def isBlack = true
@@ -76,12 +77,14 @@ abstract class RedBlack[A] {
     def smallest: NonEmpty[Nothing] = throw new NoSuchElementException("empty map")
     def elements: Iterator[Pair[A, Nothing]] = Iterator.empty
   }
+  [serializable]
   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
   }
+  [serializable]
   case class BlackTree[+B](override val key: A,
                            override val value: B,
                            override val left: Tree[B],
diff --git a/src/library/scala/collection/immutable/Set.scala b/src/library/scala/collection/immutable/Set.scala
index da647a363a..81ff1b4718 100644
--- a/src/library/scala/collection/immutable/Set.scala
+++ b/src/library/scala/collection/immutable/Set.scala
@@ -49,7 +49,8 @@ trait Set[A] extends AnyRef with collection.Set[A] {
    *  @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
+  def ++ (elems: Iterable[A]): Set[A] =
+    (this /: elems) ((s, elem) => s + elem)
 
   /** Add all the elements provided by an iterator to the set.
    *  @param elems  the iterator containing the elements to be added
diff --git a/src/library/scala/collection/immutable/TreeMap.scala b/src/library/scala/collection/immutable/TreeMap.scala
index 3b5e245cb5..5386575f9c 100644
--- a/src/library/scala/collection/immutable/TreeMap.scala
+++ b/src/library/scala/collection/immutable/TreeMap.scala
@@ -35,28 +35,16 @@ object TreeMap {
  *  @version 1.1, 03/05/2004
  */
 [serializable]
-class TreeMap[A <% Ordered[A], +B] extends Map[A, B] {
+class TreeMap[A <% Ordered[A], +B](val size: int, t: RedBlack[A]#Tree[B])
+extends RedBlack[A] with Map[A, B] {
 
-  def size: int = 0
+  def isSmaller(x: A, y: A) = x < y
 
-  [serializable]
-  class RB extends RedBlack[A] {
-    def isSmaller(x: A, y: A) = x < y
-  }
-
-  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
-  }
+  def this() = this(0, null)
 
+  protected val tree: RedBlack[A]#Tree[B] = if (size == 0) Empty else t
 
-  private def newMap[B](s: int, t: rb.Tree[B]) = new NonEmptyTreeMap[B](s, t)
+  private def newMap[B](s: int, t: RedBlack[A]#Tree[B]) = new TreeMap[A, B](s, t)
 
   /** A factory to create empty maps of the same type of keys.
    */
@@ -94,7 +82,7 @@ class TreeMap[A <% Ordered[A], +B] extends Map[A, B] {
    *  @return the value of the mapping, if it exists
    */
   override def get(key: A): Option[B] = tree.lookup(key) match {
-    case n: rb.NonEmpty[b] => Some(n.value)
+    case n: NonEmpty[b] => Some(n.value)
     case _ => None
   }
 
@@ -107,7 +95,7 @@ class TreeMap[A <% Ordered[A], +B] extends Map[A, B] {
    *  @throws Error("key not found").
    */
   override def apply(key: A): B = tree.lookup(key) match {
-    case n: rb.NonEmpty[b] => n.value
+    case n: NonEmpty[b] => n.value
     case _ => super.apply(key)
   }
 
diff --git a/src/library/scala/collection/immutable/UnbalancedTreeMap.scala b/src/library/scala/collection/immutable/UnbalancedTreeMap.scala
new file mode 100755
index 0000000000..c96d1b7f66
--- /dev/null
+++ b/src/library/scala/collection/immutable/UnbalancedTreeMap.scala
@@ -0,0 +1,137 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2006, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |                                         **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id: TreeMap.scala 8997 2006-10-19 20:52:30Z odersky $
+
+// todo: make balanced once Tree.scala is updated to be covariant.
+
+package scala.collection.immutable
+
+
+object UnbalancedTreeMap {
+  def Empty[A <% Ordered[A], B] = new UnbalancedTreeMap[A, B]
+}
+
+/** This class implements immutable maps using a tree.
+ *
+ *  @author  Martin Odersky
+ *  @version 1.1, 02/01/2007
+ */
+
+[serializable]
+class UnbalancedTreeMap[A <% Ordered[A], +B] extends Map[A, B] {
+
+  /** A factory to create empty maps of the same type of keys.
+   */
+  def empty[C] = UnbalancedTreeMap.Empty[A, C]
+
+  def size: Int = 0
+
+  override def isEmpty: boolean = true
+
+  protected def add [B1 >: B](key: A, value: B1) = new Node(key, value, this, this)
+  protected def findValue (key: A): UnbalancedTreeMap[A, B] = this
+
+  protected def key: A = throw new NoSuchElementException("empty map")
+  protected def value: B = throw new NoSuchElementException("empty map")
+  protected def smallest: UnbalancedTreeMap[A, B] = throw new NoSuchElementException("empty map")
+
+  /** 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) = add(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: B1) = add(key, value)
+
+  def - (key:A): UnbalancedTreeMap[A, B] = this
+
+  /** 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] = {
+    val t = findValue(key)
+    if (t.isEmpty) None
+    else Some(t.value)
+  }
+
+  /** 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 = {
+    val t = findValue(key)
+    if (!t.isEmpty) t.value
+    else super.apply(key)
+  }
+
+  /** Creates a new iterator over all elements contained in this
+   *  object.
+   *
+   *  @return the new iterator
+   */
+  def elements: Iterator[Pair[A, B]] = Iterator.empty
+
+  protected class Node[+B](override protected val key: A,
+                           override protected val value: B,
+                           left: UnbalancedTreeMap[A, B],
+                           right: UnbalancedTreeMap[A, B]) extends UnbalancedTreeMap[A, B]
+  {
+    override def size = left.size + right.size + 1
+
+    override def isEmpty = false
+
+    override protected def add [B1 >: B](k: A, v: B1) =
+      if (k < key) new Node[B1](key, value, left.add(k, v), right)
+      else if (k > key) new Node[B1](key, value, left, right.add(k, v))
+      else new Node[B1](k, v, left, right)
+
+    override protected def findValue (k: A): UnbalancedTreeMap[A, B] =
+      if (k < key) left.findValue(k)
+      else if (k > key) right.findValue(k)
+      else this
+
+    override protected def smallest: UnbalancedTreeMap[A, B] =
+      if (left.isEmpty) this else left.smallest
+
+    override def - (k: A): UnbalancedTreeMap[A, B] =
+      if (k < key) new Node(key, value, left - k, right)
+      else if (k > key) new Node(key, value, left, right - k)
+      else combine(left, right)
+
+    private def combine[B](l: UnbalancedTreeMap[A, B], r: UnbalancedTreeMap[A, B]) = {
+      if (l.isEmpty) r
+      else if (r.isEmpty) l
+      else {
+        val s = r.smallest
+        new Node(s.key, s.value, l, r - s.key)
+      }
+    }
+
+    override def elements: Iterator[Pair[A, B]] =
+      left.elements append Iterator.single(Pair(key, value)) append right.elements
+  }
+}
+
+
+
+
diff --git a/src/library/scala/xml/NodeSeq.scala b/src/library/scala/xml/NodeSeq.scala
index 3e35cfe56f..3bed37b5c4 100644
--- a/src/library/scala/xml/NodeSeq.scala
+++ b/src/library/scala/xml/NodeSeq.scala
@@ -153,7 +153,6 @@ abstract class NodeSeq extends Seq[Node] {
   override def toString(): String = theSeq.elements.foldLeft ("") {
     (s: String, x: Node) => s + x.toString()
   }
-
 /*
   def map(f: Node => NodeSeq): NodeSeq = flatMap(f)
 
@@ -167,6 +166,7 @@ abstract class NodeSeq extends Seq[Node] {
     x
   }
 */
+
   def text: String = {
     val sb = new compat.StringBuilder()
     val it = elements
diff --git a/test/files/jvm/serialization.scala b/test/files/jvm/serialization.scala
index 17fc54aecf..ed815ad2e4 100644
--- a/test/files/jvm/serialization.scala
+++ b/test/files/jvm/serialization.scala
@@ -129,6 +129,7 @@ object Test2_immutable {
   catch {
     case e: Exception =>
       System.out.println("Error in Test2_immutable: " + e);
+      throw e
   }
 }
 
diff --git a/test/files/jvm/xml01.scala b/test/files/jvm/xml01.scala
index b0a3044fc1..8c99cfd358 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