From d932455a653c65de5ddbe15462c24c0601f489c6 Mon Sep 17 00:00:00 2001 From: Iulian Dragos Date: Fri, 19 Jan 2007 15:00:18 +0000 Subject: Reverted Lex's changes until we fix the type ch... Reverted Lex's changes until we fix the type checker --- src/library/scala/Console.scala | 4 +- .../scala/collection/immutable/HashTreeMap.scala | 103 --------------------- .../scala/collection/immutable/HashTreeSet.scala | 46 --------- src/library/scala/collection/immutable/Map.scala | 14 +-- .../scala/collection/immutable/RedBlack.scala | 49 ++++------ src/library/scala/collection/immutable/Set.scala | 11 +-- .../scala/collection/immutable/TreeMap.scala | 39 ++++---- .../scala/collection/immutable/TreeSet.scala | 27 +++--- src/library/scala/runtime/BoxedUnit.java | 2 +- 9 files changed, 58 insertions(+), 237 deletions(-) delete mode 100644 src/library/scala/collection/immutable/HashTreeMap.scala delete mode 100644 src/library/scala/collection/immutable/HashTreeSet.scala 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 * p returns false. * 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 not 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 key 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 elem. * 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 "()"; } } -- cgit v1.2.3