Reverted Lex's changes until we fix the type ch...

Reverted Lex's changes until we fix the type checker

9 files changed, 58 insertions, 237 deletions

diff --git a/src/library/scala/Console.scala b/src/library/scala/Console.scala
index 7cc8e9d4e9..bcff65c84c 100644
--- a/src/library/scala/Console.scala
+++ b/src/library/scala/Console.scala
@@ -171,12 +171,12 @@ object Console {
    *  @param args the parameters used to instantiate the format.
    */
   // todo: Uncurry
-  def printf(text: String)(args: Any*): Unit =
+/*  def printf(text: String)(args: Any*): Unit =
     out.print(
       if (text eq null) "null"
       else MessageFormat.format(text, textParams(args))
     )
-
+*/
   /** Read a full line from the terminal.
    *
    *  @return the string read from the terminal.
diff --git a/src/library/scala/collection/immutable/HashTreeMap.scala b/src/library/scala/collection/immutable/HashTreeMap.scala
deleted file mode 100644
index db334310b9..0000000000
--- a/src/library/scala/collection/immutable/HashTreeMap.scala
+++ /dev/null
@@ -1,103 +0,0 @@
-/*                     __                                               *\
-**     ________ ___   / /  ___     Scala API                            **
-**    / __/ __// _ | / /  / _ |    (c) 2003-2007, LAMP/EPFL             **
-**  __\ \/ /__/ __ |/ /__/ __ |                                         **
-** /____/\___/_/ |_/____/_/ | |                                         **
-**                          |/                                          **
-\*                                                                      */
-
-// $Id$
-
-
-
-package scala.collection.immutable
-
-
-object HashTreeMap {
-  /** The empty map of this type */
-  def empty[A, B] = new HashTreeMap[A, B]
-
-  /** The canonical factory for this type
-   */
-  def apply[A, B](elems: Pair[A, B]*) = empty[A, B] ++ elems
-}
-
-/** An immutable tree-based map that uses hashes to order
- * the elements.  While it is not as efficient as
- * a regular TreeMap, it has the advantage of not requiring
- * an Ordered view being available for the key data.
- *
- * The implementation a TreeMap mapping hash codes into
- * ListMap's, where each ListMap is a bucket of entries
- * whose keys have the same hash code.
- */
-class HashTreeMap[Key, +Value](treemap: TreeMap[int, Map[Key, Value]],  val size: int)
-extends Map[Key, Value]
-{
-  /** Create an empty HashTreeMap */
-  def this() = this(new TreeMap, 0)
-
-  /** A central, convenenient updating function.  Given a key,
-    * it finds the bucket for that key, allows the specified
-    * routine to update the bucket, and then creates a new
-    * HashTreeMap using the updated bucket.
-    */
-  private def updateBucket[Value1 >: Value]
-    (key: Key)
-    (upd: Map[Key, Value1] => Map[Key, Value1])
-    : Map[Key, Value1] =
-  {
-    val hash: int = key.hashCode
-    var sizechange = 0
-
-    val newmap =
-      treemap.updatef(
-          hash,
-          maybeBucket => {
-            val oldBucket = maybeBucket match {
-              case None => new ListMap[Key, Value]
-              case Some(oldBucket) => oldBucket
-            }
-            val newBucket = upd(oldBucket)
-            sizechange = newBucket.size - oldBucket.size
-            newBucket
-          })
-
-    new HashTreeMap(newmap, size + sizechange)
-  }
-
-  def update[Value1 >: Value](key: Key, value: Value1) =
-    updateBucket[Value1](key)(b => b + {key, value})
-
-  def get(key: Key) = {
-    treemap.get(key.hashCode) match {
-      case None => None
-      case Some(bucket) => bucket.get(key)
-    }
-  }
-
-  def - (key: Key) = updateBucket(key)(b => b - key)
-
-  def empty[C] = new HashTreeMap[Key, C]
-
-  def elements = new scala.Iterator[Pair[Key,Value]] {
-    val topElements = treemap.elements
-    var bucket: Iterator[Pair[Key, Value]] = null
-
-    def moveToNext = {
-      while(topElements.hasNext &&
-            (bucket == null || !bucket.hasNext))
-        bucket = topElements.next._2.elements
-    }
-
-    def hasNext = {
-      moveToNext
-      (bucket != null) && bucket.hasNext
-    }
-
-    def next = {
-      moveToNext
-      bucket.next
-    }
-  }
-}
\ No newline at end of file
diff --git a/src/library/scala/collection/immutable/HashTreeSet.scala b/src/library/scala/collection/immutable/HashTreeSet.scala
deleted file mode 100644
index c7ceedb66f..0000000000
--- a/src/library/scala/collection/immutable/HashTreeSet.scala
+++ /dev/null
@@ -1,46 +0,0 @@
-/*                     __                                               *\
-**     ________ ___   / /  ___     Scala API                            **
-**    / __/ __// _ | / /  / _ |    (c) 2003-2007, LAMP/EPFL             **
-**  __\ \/ /__/ __ |/ /__/ __ |                                         **
-** /____/\___/_/ |_/____/_/ | |                                         **
-**                          |/                                          **
-\*                                                                      */
-
-// $Id$
-
-
-
-package scala.collection.immutable
-
-
-/** An immutable tree-based set that uses hashes to order
- * the elements.  While it is not as efficient as
- * a regular TreeSet, it has the advantage of not requiring
- * an Ordered view being available for the data.
- *
- * The implementation is a TreeSet mapping hash codes into
- * ListSet's, where each ListSet is a bucket of entries
- * whose elements all have the same hash code.
- */
-class HashTreeSet[T](unitmap: Map[T,Unit])
-extends Set[T]
-{
-  /** Create an empty HashTreeMap */
-  def this() = this(new HashTreeMap)
-
-  def size = unitmap.size
-
-  def +(x: T) = new HashTreeSet(unitmap + {x,()})
-
-  def -(x: T) = new HashTreeSet(unitmap - x)
-
-  def contains(x: T) = unitmap.contains(x)
-
-  def empty[S]: Set[S] = new HashTreeSet[S]
-
-  def elements = new scala.Iterator[T] {
-    val mapElements = unitmap.elements
-    def hasNext = mapElements.hasNext
-    def next = mapElements.next._1
-  }
-}
\ No newline at end of file
diff --git a/src/library/scala/collection/immutable/Map.scala b/src/library/scala/collection/immutable/Map.scala
index 31c0de211b..8c9b3b75b8 100644
--- a/src/library/scala/collection/immutable/Map.scala
+++ b/src/library/scala/collection/immutable/Map.scala
@@ -35,14 +35,12 @@ package scala.collection.immutable
  */
 object Map {
 
-  /** An empty immutable map.  This is implemented with a HashTreeMap.
-   * Note that for key types that have an Ordered view, it is more
-   * efficient to use a TreeMap, instead.
-   */
-  def empty[A, B] = new HashTreeMap[A, B]
+  /** The empty map of this type; this is implemented as a treemap */
+  def empty[A <% Ordered[A], B] = new TreeMap[A, B]
 
-  /** Create an immutable map from a specified sequence of elements.  */
-  def apply[A, B](elems: Pair[A, B]*) = empty[A, B] ++ elems
+  /** The canonical factory for this type
+   */
+  def apply[A <% Ordered[A], B](elems: Pair[A, B]*) = empty[A, B] ++ elems
 }
 
 trait Map[A, +B] extends collection.Map[A, B] {
@@ -65,7 +63,6 @@ trait Map[A, +B] extends collection.Map[A, B] {
    */
   def update [B1 >: B] (key: A, value: B1): Map[A, B1]
 
-
   /** 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
@@ -146,7 +143,6 @@ trait Map[A, +B] extends collection.Map[A, B] {
     res
   }
 
-
   /** This method removes all the mappings for which the predicate
    *  <code>p</code> returns <code>false</code>.
    *
diff --git a/src/library/scala/collection/immutable/RedBlack.scala b/src/library/scala/collection/immutable/RedBlack.scala
index aac583bb2c..dd3c7ebc94 100755
--- a/src/library/scala/collection/immutable/RedBlack.scala
+++ b/src/library/scala/collection/immutable/RedBlack.scala
@@ -18,14 +18,11 @@ abstract class RedBlack[A] {
     def isBlack: boolean
     def lookup(x: A): Tree[B]
     def update[B1 >: B](k: A, v: B1): Tree[B1] = blacken(upd(k, v))
-    def updatef[B1 >: B](k: A, f: Option[B]=>B1): Tree[B1] = blacken(updf(k, f))
     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 updf[B1 >: B](k: A, f: Option[B]=>B1): Tree[B1]
     def del(k: A): Tree[B]
     def smallest: NonEmpty[B]
-    val size: Int
   }
   [serializable]
   abstract class NonEmpty[+B] extends Tree[B] {
@@ -38,37 +35,27 @@ abstract class RedBlack[A] {
       if (isSmaller(k, key)) left.lookup(k)
       else if (isSmaller(key, k)) right.lookup(k)
       else this
-
-    /** helper function for upd and updf */
-    def balanceLeft[B1 >: B](isBlack: boolean, z: A, zv: B1, 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)
-    }
-
-    /** helper function for upd and updf */
-    def balanceRight[B1 >: B](isBlack: boolean, x: A, xv: B1, 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)
-    }
-
     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 updf[B1 >: B](k: A, f: Option[B]=>B1): Tree[B1] = {
-      if (isSmaller(k, key)) balanceLeft(isBlack, key, value, left.updf(k, f), right)
-      else if (isSmaller(key, k)) balanceRight(isBlack, key, value, left, right.updf(k, f))
-      else mkTree(isBlack, k, f(Some(value)), 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))
@@ -82,8 +69,6 @@ abstract class RedBlack[A] {
     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
-
-    val size = left.size + right.size
   }
   [serializable]
   case object Empty extends Tree[Nothing] {
@@ -91,11 +76,9 @@ abstract class RedBlack[A] {
     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 updf[B](k: A, f: Option[Nothing]=>B) = upd(k, f(None))
     def del(k: A): Tree[Nothing] = this
     def smallest: NonEmpty[Nothing] = throw new NoSuchElementException("empty map")
     def elements: Iterator[Pair[A, Nothing]] = Iterator.empty
-    val size = 0
   }
   [serializable]
   case class RedTree[+B](override val key: A,
diff --git a/src/library/scala/collection/immutable/Set.scala b/src/library/scala/collection/immutable/Set.scala
index 42c106eddd..eadc656470 100644
--- a/src/library/scala/collection/immutable/Set.scala
+++ b/src/library/scala/collection/immutable/Set.scala
@@ -25,14 +25,13 @@ package scala.collection.immutable
  *  @version 1.1, 03/05/2004
  */
 object Set {
-  /** An empty immutable set.  This is implemented with a HashTreeSet.
-   * Note that for element types that have an Ordered view, it is more
-   * efficient to use a TreeSet, instead.
+  /** The empty set of this type
    */
-  def empty[A] = new HashTreeSet[A]
+  def empty[A <% Ordered[A]] = new TreeSet[A]
 
-  /** Create an immutable map from a specified sequence of elements.  */
-  def apply[A](elems: A*) = empty[A] ++ elems
+  /** The canonical factory for this type
+   */
+  def apply[A <% Ordered[A]](elems: A*) = empty[A] ++ elems
 }
 
 trait Set[A] extends AnyRef with collection.Set[A] {
diff --git a/src/library/scala/collection/immutable/TreeMap.scala b/src/library/scala/collection/immutable/TreeMap.scala
index cd8210a524..9e43f092df 100644
--- a/src/library/scala/collection/immutable/TreeMap.scala
+++ b/src/library/scala/collection/immutable/TreeMap.scala
@@ -35,19 +35,20 @@ object TreeMap {
  *  @version 1.1, 03/05/2004
  */
 [serializable]
-class TreeMap[A <% Ordered[A], +B](tree: RedBlack[A]#Tree[B])
+class TreeMap[A <% Ordered[A], +B](val size: int, t: RedBlack[A]#Tree[B])
 extends RedBlack[A] with Map[A, B] {
 
   def isSmaller(x: A, y: A) = x < y
 
-  def this() = this(Empty)
-  def size = tree.size
+  def this() = this(0, null)
 
-  private def newMap[B](t: RedBlack[A]#Tree[B]) = new TreeMap[A, B](t)
+  protected val tree: RedBlack[A]#Tree[B] = if (size == 0) Empty else 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.
    */
-  def empty[C] = new TreeMap[A,C]
+  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
@@ -58,16 +59,8 @@ extends RedBlack[A] with Map[A, B] {
    *  @return ...
    */
   def update [B1 >: B](key: A, value: B1): TreeMap[A, B1] = {
-     val newtree = tree.update(key, value)
-     newMap(newtree)
-  }
-
-  /** Update the item at a single key.  This method
-   * is functionally equivalent to: update(key, f(get(key))) .
-   */
-  def updatef [B1 >: B](key: A, f: Option[B]=>B1) = {
-    val newtree = tree.updatef(key, f)
-    newMap(newtree)
+    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,
@@ -75,16 +68,12 @@ extends RedBlack[A] with Map[A, B] {
    */
   def insert [B1 >: B](key: A, value: B1): TreeMap[A, B1] = {
     assert(tree.lookup(key).isEmpty)
-    newMap(tree.update(key, value))
+    newMap(size + 1, tree.update(key, value))
   }
 
-  def - (key:A): TreeMap[A, B] = {
-    val newtree = tree.delete(key)
-    if(newtree eq tree)
-      this
-    else
-      newMap(newtree)
-  }
+  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.
@@ -117,3 +106,7 @@ extends RedBlack[A] with Map[A, B] {
    */
   def elements: Iterator[Pair[A, B]] = tree.elements
 }
+
+
+
+
diff --git a/src/library/scala/collection/immutable/TreeSet.scala b/src/library/scala/collection/immutable/TreeSet.scala
index e5f4ed312b..1226923d66 100644
--- a/src/library/scala/collection/immutable/TreeSet.scala
+++ b/src/library/scala/collection/immutable/TreeSet.scala
@@ -34,23 +34,26 @@ object TreeSet {
  */
 
 [serializable]
-class TreeSet[A <% Ordered[A]](tree: RedBlack[A]#Tree[Unit])
+class TreeSet[A <% Ordered[A]](val size: int, t: RedBlack[A]#Tree[Unit])
 extends RedBlack[A] with Set[A] {
+
   def isSmaller(x: A, y: A) = x < y
-  def this() = this(Empty)
 
-  def size = tree.size
+  def this() = this(0, null)
+
+  protected val tree: RedBlack[A]#Tree[Unit] = if (size == 0) Empty else t
 
-  private def newSet(t: RedBlack[A]#Tree[Unit]) = new TreeSet[A](t)
+  private def newSet(s: int, t: RedBlack[A]#Tree[Unit]) = new TreeSet[A](s, t)
 
-  /** @return an empty set of arbitrary element type
+  /** A factory to create empty maps of the same type of keys.
    */
   def empty[B]: Set[B] = ListSet.empty[B]
 
   /** A new TreeSet with the entry added is returned,
    */
   def + (elem: A): TreeSet[A] = {
-    newSet(tree.update(elem, ()))
+    val newsize = if (tree.lookup(elem).isEmpty) size + 1 else size
+    newSet(newsize, tree.update(elem, ()))
   }
 
   /** A new TreeSet with the entry added is returned,
@@ -58,16 +61,12 @@ extends RedBlack[A] with Set[A] {
    */
   def insert (elem: A): TreeSet[A] = {
     assert(tree.lookup(elem).isEmpty)
-    newSet(tree.update(elem, ()))
+    newSet(size + 1, tree.update(elem, ()))
   }
 
-  def - (elem:A): TreeSet[A] = {
-    val newtree = tree.delete(elem)
-    if(newtree eq tree)
-      this
-    else
-      newSet(newtree)
-  }
+  def - (elem:A): TreeSet[A] =
+    if (tree.lookup(elem).isEmpty) this
+    else newSet(size - 1, tree.delete(elem))
 
   /** Checks if this set contains element <code>elem</code>.
    *
diff --git a/src/library/scala/runtime/BoxedUnit.java b/src/library/scala/runtime/BoxedUnit.java
index bd3361fe56..7ed7c6f1d8 100644
--- a/src/library/scala/runtime/BoxedUnit.java
+++ b/src/library/scala/runtime/BoxedUnit.java
@@ -29,6 +29,6 @@ public final class BoxedUnit
     }
 
     public String toString() {
-	return "{}";
+	return "()";
     }
 }