From d1042e7f425c352e20cec779377b895faefb9521 Mon Sep 17 00:00:00 2001 From: Martin Odersky Date: Thu, 4 Jan 2007 13:08:19 +0000 Subject: changed collection libraries --- src/library/scala/Iterable.scala | 7 ++ src/library/scala/Seq.scala | 7 ++ src/library/scala/collection/Set.scala | 2 +- src/library/scala/collection/immutable/Map.scala | 3 +- .../scala/collection/immutable/RedBlack.scala | 3 + src/library/scala/collection/immutable/Set.scala | 3 +- .../scala/collection/immutable/TreeMap.scala | 28 ++--- .../collection/immutable/UnbalancedTreeMap.scala | 137 +++++++++++++++++++++ src/library/scala/xml/NodeSeq.scala | 2 +- 9 files changed, 168 insertions(+), 24 deletions(-) create mode 100755 src/library/scala/collection/immutable/UnbalancedTreeMap.scala (limited to 'src/library') 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 f 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 x? * * @return true, iff x 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 not 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 not 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 key 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 -- cgit v1.2.3