diff options
Diffstat (limited to 'src/library')
32 files changed, 739 insertions, 34 deletions
diff --git a/src/library/scala/Function1.scala b/src/library/scala/Function1.scala index dc8e67bbb0..7517e6604b 100644 --- a/src/library/scala/Function1.scala +++ b/src/library/scala/Function1.scala @@ -24,10 +24,18 @@ package scala * assert(succ(0) == anonfun1(0)) * } * }}} + * + * Note that `Function1` does not define a total function, as might + * be suggested by the existence of [[scala.PartialFunction]]. The only + * distinction between `Function1` and `PartialFunction` is that the + * latter can specify inputs which it will not handle. + * */ @annotation.implicitNotFound(msg = "No implicit view available from ${T1} => ${R}.") trait Function1[@specialized(scala.Int, scala.Long, scala.Float, scala.Double) -T1, @specialized(scala.Unit, scala.Boolean, scala.Int, scala.Float, scala.Long, scala.Double) +R] extends AnyRef { self => - /** Apply the body of this function to the argument. + /** Apply the body of this function to the argument. It may throw an + * exception. + * * @return the result of function application. */ def apply(v1: T1): R diff --git a/src/library/scala/PartialFunction.scala b/src/library/scala/PartialFunction.scala index b2910c2278..70caff0221 100644 --- a/src/library/scala/PartialFunction.scala +++ b/src/library/scala/PartialFunction.scala @@ -13,6 +13,36 @@ package scala * The function `isDefinedAt` allows to test dynamically if a value is in * the domain of the function. * + * Even if `isDefinedAt` returns true for an `a: A`, calling `apply(a)` may + * still throw an exception, so the following code is legal: + * + * {{{ + * val f: PartialFunction[Int, Any] = { case _ => 1/0 } + * }}} + * + * The main distinction between `PartialFunction` and [[scala.Function1]] is + * that the user of a `PartialFunction` may choose to do something different + * with input that is declared to be outside its domain. For example: + * + * {{{ + * val sample = 1 to 10 + * val isEven: PartialFunction[Int, String] = { + * case x if x % 2 == 0 => x+" is even" + * } + * + * // the method collect can use isDefinedAt to select which members to collect + * val evenNumbers = sample collect isEven + * + * val isOdd: PartialFunction[Int, String] = { + * case x if x % 2 == 1 => x+" is odd" + * } + * + * // the method orElse allows chaining another partial function to handle + * // input outside the declared domain + * val numbers = sample map (isEven orElse isOdd) + * }}} + * + * * @author Martin Odersky * @version 1.0, 16/07/2003 */ diff --git a/src/library/scala/StringContext.scala b/src/library/scala/StringContext.scala new file mode 100644 index 0000000000..1f0b4c766e --- /dev/null +++ b/src/library/scala/StringContext.scala @@ -0,0 +1,191 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2002-2012, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +package scala + +import collection.mutable.ArrayBuffer + +/** A class to support string interpolation. + * This class supports string interpolation as outlined in Scala SIP-11. + * It needs to be fully documented once the SIP is accepted. + * + * @param parts The parts that make up the interpolated string, + * without the expressions that get inserted by interpolation. + */ +case class StringContext(parts: String*) { + + import StringContext._ + + /** Checks that the given arguments `args` number one less than the number + * of `parts` supplied to the enclosing `StringContext`. + * @param `args` The arguments to be checked. + * @throws An `IllegalArgumentException` if this is not the case. + */ + def checkLengths(args: Any*): Unit = + if (parts.length != args.length + 1) + throw new IllegalArgumentException("wrong number of arguments for interpolated string") + + + /** The simple string interpolator. + * + * It inserts its arguments between corresponding parts of the string context. + * It also treats standard escape sequences as defined in the Scala specification. + * @param `args` The arguments to be inserted into the resulting string. + * @throws An `IllegalArgumentException` + * if the number of `parts` in the enclosing `StringContext` does not exceed + * the number of arguments `arg` by exactly 1. + * @throws A `StringContext.InvalidEscapeException` if if a `parts` string contains a backslash (`\`) character + * that does not start a valid escape sequence. + */ + def s(args: Any*) = { + checkLengths(args) + val pi = parts.iterator + val ai = args.iterator + val bldr = new java.lang.StringBuilder(treatEscapes(pi.next)) + while (ai.hasNext) { + bldr append ai.next + bldr append treatEscapes(pi.next) + } + bldr.toString + } + + /** The formatted string interpolator. + * + * It inserts its arguments between corresponding parts of the string context. + * It also treats standard escape sequences as defined in the Scala specification. + * Finally, if an interpolated expression is followed by a `parts` string + * that starts with a formatting specifier, the expression is formatted according to that + * specifier. All specifiers allowed in Java format strings are handled, and in the same + * way they are treated in Java. + * + * @param `args` The arguments to be inserted into the resulting string. + * @throws An `IllegalArgumentException` + * if the number of `parts` in the enclosing `StringContext` does not exceed + * the number of arguments `arg` by exactly 1. + * @throws A `StringContext.InvalidEscapeException` if a `parts` string contains a backslash (`\`) character + * that does not start a valid escape sequence. + * + * Note: The `f` method works by assembling a format string from all the `parts` strings and using + * `java.lang.String.format` to format all arguments with that format string. The format string is + * obtained by concatenating all `parts` strings, and performing two transformations: + * + * 1. Let a _formatting position_ be a start of any `parts` string except the first one. + * If a formatting position does not refer to a `%` character (which is assumed to + * start a format specifier), then the string format specifier `%s` is inserted. + * + * 2. Any `%` characters not in formatting positions are left in the resulting + * string literally. This is achieved by replacing each such occurrence by a string + * format specifier `%s` and adding a corresponding argument string `"%"`. + */ + def f(args: Any*) = { + checkLengths(args) + val pi = parts.iterator + val ai = args.iterator + val bldr = new java.lang.StringBuilder + val args1 = new ArrayBuffer[Any] + def copyString(first: Boolean): Unit = { + val str = treatEscapes(pi.next) + var start = 0 + var idx = 0 + if (!first) { + if ((str charAt 0) != '%') + bldr append "%s" + idx = 1 + } + val len = str.length + while (idx < len) { + if (str(idx) == '%') { + bldr append (str substring (start, idx)) append "%s" + args1 += "%" + start = idx + 1 + } + idx += 1 + } + bldr append (str substring (start, idx)) + } + copyString(first = true) + while (pi.hasNext) { + args1 += ai.next + copyString(first = false) + } + bldr.toString format (args1: _*) + } +} + +object StringContext { + + /** An exception that is thrown if a string contains a backslash (`\`) character that + * that does not start a valid escape sequence. + * @param str The offending string + * @param idx The index of the offending backslash character in `str`. + */ + class InvalidEscapeException(str: String, idx: Int) + extends IllegalArgumentException("invalid escape character at index "+idx+" in \""+str+"\"") + + /** Expands standard Scala escape sequences in a string. + * Escape sequences are: + * control: `\b`, `\t`, `\n`, `\f`, `\r` + * escape: `\\`, `\"`, `\'` + * octal: `\d` `\dd` `\ddd` where `d` is an octal digit between `0` and `7`. + * + * @param A string that may contain escape sequences + * @return The string with all escape sequences expanded. + */ + def treatEscapes(str: String): String = { + lazy val bldr = new java.lang.StringBuilder + val len = str.length + var start = 0 + var cur = 0 + var idx = 0 + def output(ch: Char) = { + bldr append str substring (start, cur) + bldr append ch + start = idx + } + while (idx < len) { + cur = idx + if (str(idx) == '\\') { + idx += 1 + if ('0' <= str(idx) && str(idx) <= '7') { + val leadch = str(idx) + var oct = leadch - '0' + idx += 1 + if ('0' <= str(idx) && str(idx) <= '7') { + oct = oct * 8 + str(idx) - '0' + idx += 1 + if (leadch <= '3' && '0' <= str(idx) && str(idx) <= '7') { + oct = oct * 8 + str(idx) - '0' + idx += 1 + } + } + output(oct.toChar) + } else { + val ch = str(idx) + idx += 1 + output { + ch match { + case 'b' => '\b' + case 't' => '\t' + case 'n' => '\n' + case 'f' => '\f' + case 'r' => '\r' + case '\"' => '\"' + case '\'' => '\'' + case '\\' => '\\' + case _ => throw new InvalidEscapeException(str, cur) + } + } + } + } else { + idx += 1 + } + } + if (start == 0) str + else (bldr append str.substring(start, idx)).toString + } +} diff --git a/src/library/scala/Symbol.scala b/src/library/scala/Symbol.scala index 8a17ae87b0..8851f1ab91 100644 --- a/src/library/scala/Symbol.scala +++ b/src/library/scala/Symbol.scala @@ -31,8 +31,8 @@ final class Symbol private (val name: String) extends Serializable { override def equals(other: Any) = this eq other.asInstanceOf[AnyRef] } -object Symbol extends UniquenessCache[String, Symbol] -{ +object Symbol extends UniquenessCache[String, Symbol] { + override def apply(name: String): Symbol = super.apply(name) protected def valueFromKey(name: String): Symbol = new Symbol(name) protected def keyFromValue(sym: Symbol): Option[String] = Some(sym.name) } diff --git a/src/library/scala/collection/GenTraversableLike.scala b/src/library/scala/collection/GenTraversableLike.scala index 122eec2d90..c837775cf9 100644 --- a/src/library/scala/collection/GenTraversableLike.scala +++ b/src/library/scala/collection/GenTraversableLike.scala @@ -177,7 +177,28 @@ trait GenTraversableLike[+A, +Repr] extends GenTraversableOnce[A] with Paralleli def collect[B, That](pf: PartialFunction[A, B])(implicit bf: CanBuildFrom[Repr, B, That]): That /** Builds a new collection by applying a function to all elements of this $coll - * and concatenating the results. + * and using the elements of the resulting collections. For example: + * + * {{{ + * def getWords(lines: Seq[String]): Seq[String] = lines flatMap (line => line split "\\W+") + * }}} + * + * The type of the resulting collection is guided by the static type of $coll. This might + * cause unexpected results sometimes. For example: + * + * {{{ + * // lettersOf will return a Seq[Char] of likely repeated letters, instead of a Set + * def lettersOf(words: Seq[String]) = words flatMap (word => word.toSet) + * + * // lettersOf will return a Set[Char], not a Seq + * def lettersOf(words: Seq[String]) = words.toSet flatMap (word => word.toSeq) + * + * // xs will be a an Iterable[Int] + * val xs = Map("a" -> List(11,111), "b" -> List(22,222)).flatMap(_._2) + * + * // ys will be a Map[Int, Int] + * val ys = Map("a" -> List(1 -> 11,1 -> 111), "b" -> List(2 -> 22,2 -> 222)).flatMap(_._2) + * }}} * * @param f the function to apply to each element. * @tparam B the element type of the returned collection. diff --git a/src/library/scala/collection/GenTraversableOnce.scala b/src/library/scala/collection/GenTraversableOnce.scala index 3e42e7812b..305f8d768d 100644 --- a/src/library/scala/collection/GenTraversableOnce.scala +++ b/src/library/scala/collection/GenTraversableOnce.scala @@ -471,7 +471,7 @@ trait GenTraversableOnce[+A] { * $willNotTerminateInf * @return an indexed sequence containing all elements of this $coll. */ - def toIndexedSeq[A1 >: A]: immutable.IndexedSeq[A1] + def toIndexedSeq: immutable.IndexedSeq[A] /** Converts this $coll to a stream. * $willNotTerminateInf diff --git a/src/library/scala/collection/JavaConverters.scala b/src/library/scala/collection/JavaConverters.scala index 94f7e9701b..d213e60112 100755 --- a/src/library/scala/collection/JavaConverters.scala +++ b/src/library/scala/collection/JavaConverters.scala @@ -48,7 +48,8 @@ package scala.collection * @author Martin Odersky * @since 2.8.1 */ -object JavaConverters { + +trait JavaConverters { import java.{ lang => jl, util => ju } import java.util.{ concurrent => juc } import JavaConversions._ @@ -536,3 +537,5 @@ object JavaConverters { propertiesAsScalaMapConverter(p) } + +object JavaConverters extends JavaConverters
\ No newline at end of file diff --git a/src/library/scala/collection/SeqLike.scala b/src/library/scala/collection/SeqLike.scala index b6b4bfb96d..6d84b4276b 100644 --- a/src/library/scala/collection/SeqLike.scala +++ b/src/library/scala/collection/SeqLike.scala @@ -152,7 +152,7 @@ trait SeqLike[+A, +Repr] extends IterableLike[A, Repr] with GenSeqLike[A, Repr] if (!hasNext) Iterator.empty.next - val result = (self.newBuilder ++= elms).result + val result = (self.newBuilder ++= elms.toList).result var i = idxs.length - 2 while(i >= 0 && idxs(i) >= idxs(i+1)) i -= 1 diff --git a/src/library/scala/collection/TraversableLike.scala b/src/library/scala/collection/TraversableLike.scala index e2acc0b3e0..b4813e6341 100644 --- a/src/library/scala/collection/TraversableLike.scala +++ b/src/library/scala/collection/TraversableLike.scala @@ -709,6 +709,9 @@ trait TraversableLike[+A, +Repr] extends HasNewBuilder[A, Repr] * outer $coll containing this `WithFilter` instance that satisfy * predicate `p` and concatenating the results. * + * The type of the resulting collection will be guided by the static type + * of the outer $coll. + * * @param f the function to apply to each element. * @tparam B the element type of the returned collection. * @tparam That $thatinfo diff --git a/src/library/scala/collection/TraversableOnce.scala b/src/library/scala/collection/TraversableOnce.scala index 908c4c808d..5bb2e563f6 100644 --- a/src/library/scala/collection/TraversableOnce.scala +++ b/src/library/scala/collection/TraversableOnce.scala @@ -245,7 +245,7 @@ trait TraversableOnce[+A] extends GenTraversableOnce[A] { def toSeq: Seq[A] = toStream - def toIndexedSeq[B >: A]: immutable.IndexedSeq[B] = immutable.IndexedSeq() ++ seq + def toIndexedSeq: immutable.IndexedSeq[A] = immutable.IndexedSeq() ++ seq def toBuffer[B >: A]: mutable.Buffer[B] = new ArrayBuffer[B] ++= seq diff --git a/src/library/scala/collection/TraversableProxyLike.scala b/src/library/scala/collection/TraversableProxyLike.scala index 15565e57c6..e7e797391e 100644 --- a/src/library/scala/collection/TraversableProxyLike.scala +++ b/src/library/scala/collection/TraversableProxyLike.scala @@ -77,7 +77,7 @@ trait TraversableProxyLike[+A, +Repr <: TraversableLike[A, Repr] with Traversabl override def toList: List[A] = self.toList override def toIterable: Iterable[A] = self.toIterable override def toSeq: Seq[A] = self.toSeq - override def toIndexedSeq[B >: A] = self.toIndexedSeq + override def toIndexedSeq: immutable.IndexedSeq[A] = self.toIndexedSeq override def toBuffer[B >: A] = self.toBuffer override def toStream: Stream[A] = self.toStream override def toSet[B >: A]: immutable.Set[B] = self.toSet diff --git a/src/library/scala/collection/generic/GenericTraversableTemplate.scala b/src/library/scala/collection/generic/GenericTraversableTemplate.scala index 12c1a75c7a..7333074778 100644 --- a/src/library/scala/collection/generic/GenericTraversableTemplate.scala +++ b/src/library/scala/collection/generic/GenericTraversableTemplate.scala @@ -116,7 +116,19 @@ trait GenericTraversableTemplate[+A, +CC[X] <: GenTraversable[X]] extends HasNew } /** Converts this $coll of traversable collections into - * a $coll in which all element collections are concatenated. + * a $coll formed by the elements of these traversable + * collections. + * + * The resulting collection's type will be guided by the + * static type of $coll. For example: + * + * {{{ + * val xs = List(Set(1, 2, 3), Set(1, 2, 3)) + * // xs == List(1, 2, 3, 1, 2, 3) + * + * val ys = Set(List(1, 2, 3), List(3, 2, 1)) + * // ys == Set(1, 2, 3) + * }}} * * @tparam B the type of the elements of each traversable collection. * @param asTraversable an implicit conversion which asserts that the element diff --git a/src/library/scala/collection/generic/MutableSortedSetFactory.scala b/src/library/scala/collection/generic/MutableSortedSetFactory.scala new file mode 100644 index 0000000000..b235379575 --- /dev/null +++ b/src/library/scala/collection/generic/MutableSortedSetFactory.scala @@ -0,0 +1,33 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2011, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +package scala.collection +package generic + +import scala.collection.mutable.{ Builder, GrowingBuilder } + +/** + * @define Coll mutable.SortedSet + * @define coll mutable sorted + * + * @author Lucien Pereira + * + */ +abstract class MutableSortedSetFactory[CC[A] <: mutable.SortedSet[A] with SortedSetLike[A, CC[A]] with mutable.Set[A] with mutable.SetLike[A, CC[A]]] extends SortedSetFactory[CC] { + + /** + * mutable.SetBuilder uses '+' which is not a primitive for anything extending mutable.SetLike, + * this causes serious perfomances issues since each time 'elems = elems + x' + * is evaluated elems is cloned (which is O(n)). + * + * Fortunately GrowingBuilder comes to rescue. + * + */ + override def newBuilder[A](implicit ord: Ordering[A]): Builder[A, CC[A]] = new GrowingBuilder[A, CC[A]](empty) + +} diff --git a/src/library/scala/collection/generic/TraversableForwarder.scala b/src/library/scala/collection/generic/TraversableForwarder.scala index 6529fe4a79..3d723a1feb 100644 --- a/src/library/scala/collection/generic/TraversableForwarder.scala +++ b/src/library/scala/collection/generic/TraversableForwarder.scala @@ -61,7 +61,7 @@ trait TraversableForwarder[+A] extends Traversable[A] { override def toList: List[A] = underlying.toList override def toIterable: Iterable[A] = underlying.toIterable override def toSeq: Seq[A] = underlying.toSeq - override def toIndexedSeq[B >: A] = underlying.toIndexedSeq + override def toIndexedSeq = underlying.toIndexedSeq override def toBuffer[B >: A] = underlying.toBuffer override def toStream: Stream[A] = underlying.toStream override def toSet[B >: A]: immutable.Set[B] = underlying.toSet diff --git a/src/library/scala/collection/immutable/IndexedSeq.scala b/src/library/scala/collection/immutable/IndexedSeq.scala index bbbef158af..e3939001d8 100644 --- a/src/library/scala/collection/immutable/IndexedSeq.scala +++ b/src/library/scala/collection/immutable/IndexedSeq.scala @@ -22,7 +22,7 @@ trait IndexedSeq[+A] extends Seq[A] with GenericTraversableTemplate[A, IndexedSeq] with IndexedSeqLike[A, IndexedSeq[A]] { override def companion: GenericCompanion[IndexedSeq] = IndexedSeq - override def toIndexedSeq[B >: A]: IndexedSeq[B] = this + override def toIndexedSeq: IndexedSeq[A] = this override def seq: IndexedSeq[A] = this } diff --git a/src/library/scala/collection/interfaces/TraversableOnceMethods.scala b/src/library/scala/collection/interfaces/TraversableOnceMethods.scala index 5e1325fef6..471e977134 100644 --- a/src/library/scala/collection/interfaces/TraversableOnceMethods.scala +++ b/src/library/scala/collection/interfaces/TraversableOnceMethods.scala @@ -48,7 +48,7 @@ trait TraversableOnceMethods[+A] { // conversions def toArray[B >: A : ClassManifest]: Array[B] def toBuffer[B >: A]: mutable.Buffer[B] - def toIndexedSeq[B >: A]: immutable.IndexedSeq[B] + def toIndexedSeq: immutable.IndexedSeq[A] def toIterable: Iterable[A] def toIterator: Iterator[A] def toList: List[A] diff --git a/src/library/scala/collection/mutable/AVLTree.scala b/src/library/scala/collection/mutable/AVLTree.scala new file mode 100644 index 0000000000..0cf6cb06e5 --- /dev/null +++ b/src/library/scala/collection/mutable/AVLTree.scala @@ -0,0 +1,206 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2011, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +package scala.collection +package mutable + +import annotation.tailrec + +/** + * An immutable AVL Tree implementation used by mutable.TreeSet + * + * @author Lucien Pereira + * + */ +private[mutable] sealed trait AVLTree[+A] extends Serializable { + def balance: Int + + def depth: Int + +} + +private case class Node[A](val data: A, val left: AVLTree[A], val right: AVLTree[A]) extends AVLTree[A] { + override val balance: Int = right.depth - left.depth + + override val depth: Int = math.max(left.depth, right.depth) + 1 + +} + +private case object Leaf extends AVLTree[Nothing] { + override val balance: Int = 0 + + override val depth: Int = -1 + +} + +private[mutable] object AVLTree { + + /** + * Returns a new tree containing the given element. + * Thows an IllegalArgumentException if element is already present. + * + */ + def insert[A](value: A, tree: AVLTree[A], ordering: Ordering[A]): AVLTree[A] = { + @tailrec + def insertTC(value: A, tree: AVLTree[A], reassemble: AVLTree[A] => AVLTree[A]): AVLTree[A] = tree match { + case Leaf => reassemble(Node(value, Leaf, Leaf)) + + case Node(a, left, right) => if (0 == ordering.compare(value, a)) { + throw new IllegalArgumentException() + } else if (-1 == ordering.compare(value, a)) { + insertTC(value, left, x => reassemble(rebalance(Node(a, x, right)))) + } else { + insertTC(value, right, x => reassemble(rebalance(Node(a, left, x)))) + } + } + + insertTC(value, tree, x => rebalance(x)) + } + + def contains[A](value: A, tree: AVLTree[A], ordering: Ordering[A]): Boolean = tree match { + case Leaf => false + + case Node(a, left, right) => if (0 == ordering.compare(value, a)) { + true + } else if (-1 == ordering.compare(value, a)) { + contains(value, left, ordering) + } else { + contains(value, right, ordering) + } + } + + /** + * Return a new tree which not contains given element. + * + */ + def remove[A](value: A, tree: AVLTree[A], ordering: Ordering[A]): AVLTree[A] = tree match { + case Leaf => throw new NoSuchElementException() + + case Node(a, Leaf, Leaf) => if (0 == ordering.compare(value, a)) { + Leaf + } else { + throw new NoSuchElementException() + } + + case Node(a, left, right@Node(_, _, _)) => if (0 == ordering.compare(value, a)) { + val (min, newRight) = removeMin(right) + rebalance(Node(min, left, newRight)) + } else if (-1 == ordering.compare(value, a)) { + rebalance(Node(a, remove(value, left, ordering), right)) + } else { + rebalance(Node(a, left, remove(value, right, ordering))) + } + + case Node(a, left@Node(_, _, _), right) => if (0 == ordering.compare(value, a)) { + val (max, newLeft) = removeMax(left) + rebalance(Node(max, newLeft, right)) + } else if (-1 == ordering.compare(value, a)) { + rebalance(Node(a, remove(value, left, ordering), right)) + } else { + rebalance(Node(a, left, remove(value, right, ordering))) + } + } + + /** + * Return a tuple containing the biggest element of the provided tree + * and a new tree from which this element has been extracted. + * + */ + def removeMax[A](tree: Node[A]): (A, AVLTree[A]) = { + @tailrec + def removeMaxTC(tree: AVLTree[A], assemble: (A, AVLTree[A]) => (A, AVLTree[A])): (A, AVLTree[A]) = tree match { + case Node(a, Leaf, Leaf) => assemble(a, Leaf) + case Node(a, left, Leaf) => assemble(a, left) + case Node(a, left, right) => removeMaxTC(right, + (max: A, avl: AVLTree[A]) => assemble(max, rebalance(Node(a, left, avl)))) + case Leaf => sys.error("Should not happen.") + } + + removeMaxTC(tree, (a, b) => (a, b)) + } + + /** + * Return a tuple containing the smallest element of the provided tree + * and a new tree from which this element has been extracted. + * + */ + def removeMin[A](tree: Node[A]): (A, AVLTree[A]) = { + @tailrec + def removeMinTC(tree: AVLTree[A], assemble: (A, AVLTree[A]) => (A, AVLTree[A])): (A, AVLTree[A]) = tree match { + case Node(a, Leaf, Leaf) => assemble(a, Leaf) + case Node(a, Leaf, right) => assemble(a, right) + case Node(a, left, right) => removeMinTC(left, + (min: A, avl: AVLTree[A]) => assemble(min, rebalance(Node(a, avl, right)))) + case Leaf => sys.error("Should not happen.") + } + + removeMinTC(tree, (a, b) => (a, b)) + } + + /** + * Returns a bounded stream of elements in the tree. + * + */ + def toStream[A](tree: AVLTree[A], isLeftAcceptable: A => Boolean, isRightAcceptable: A => Boolean): Stream[A] = tree match { + case Leaf => Stream.empty + + case Node(a, left, right) => if (isLeftAcceptable(a)) { + if (isRightAcceptable(a)) { + toStream(left, isLeftAcceptable, isRightAcceptable) ++ Stream(a) ++ toStream(right, isLeftAcceptable, isRightAcceptable) + } else { + toStream(left, isLeftAcceptable, isRightAcceptable) + } + } else if (isRightAcceptable(a)) { + toStream(right, isLeftAcceptable, isRightAcceptable) + } else { + Stream.empty + } + } + + /** + * Returns a bounded iterator of elements in the tree. + * + */ + def iterator[A](tree: AVLTree[A], isLeftAcceptable: A => Boolean, isRightAcceptable: A => Boolean): Iterator[A] = + toStream(tree, isLeftAcceptable, isRightAcceptable).iterator + + def rebalance[A](tree: AVLTree[A]): AVLTree[A] = (tree, tree.balance) match { + case (node@Node(_, left, _), -2) => left.balance match { + case 1 => doubleRightRotation(node) + case _ => rightRotation(node) + } + + case (node@Node(_, _, right), 2) => right.balance match { + case -1 => doubleLeftRotation(node) + case _ => leftRotation(node) + } + + case _ => tree + } + + def leftRotation[A](tree: Node[A]): AVLTree[A] = tree.right match { + case Node(b, left, right) => Node(b, Node(tree.data, tree.left, left), right) + case _ => sys.error("Should not happen.") + } + + def rightRotation[A](tree: Node[A]): AVLTree[A] = tree.left match { + case Node(b, left, right) => Node(b, left, Node(tree.data, right, tree.right)) + case _ => sys.error("Should not happen.") + } + + def doubleLeftRotation[A](tree: Node[A]): AVLTree[A] = tree.right match { + case right@Node(b, l, r) => leftRotation(Node(tree.data, tree.left, rightRotation(right))) + case _ => sys.error("Should not happen.") + } + + def doubleRightRotation[A](tree: Node[A]): AVLTree[A] = tree.left match { + case left@Node(b, l, r) => rightRotation(Node(tree.data, leftRotation(left), tree.right)) + case _ => sys.error("Should not happen.") + } + +} diff --git a/src/library/scala/collection/mutable/SortedSet.scala b/src/library/scala/collection/mutable/SortedSet.scala new file mode 100644 index 0000000000..d87fc0b4a2 --- /dev/null +++ b/src/library/scala/collection/mutable/SortedSet.scala @@ -0,0 +1,49 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2011, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +package scala.collection +package mutable + +import generic._ + +/** + * Base trait for mutable sorted set. + * + * @define Coll mutable.SortedSet + * @define coll mutable sorted set + * + * @author Lucien Pereira + * + */ +trait SortedSet[A] extends collection.SortedSet[A] with collection.SortedSetLike[A,SortedSet[A]] + with mutable.Set[A] with mutable.SetLike[A, SortedSet[A]] { + + /** Needs to be overridden in subclasses. */ + override def empty: SortedSet[A] = SortedSet.empty[A] + +} + +/** + * A template for mutable sorted set companion objects. + * + * @define Coll mutable.SortedSet + * @define coll mutable sorted set + * @define factoryInfo + * This object provides a set of operations needed to create sorted sets of type mutable.SortedSet. + * @define sortedSetCanBuildFromInfo + * Standard `CanBuildFrom` instance for sorted sets. + * + * @author Lucien Pereira + * + */ +object SortedSet extends MutableSortedSetFactory[SortedSet] { + implicit def canBuildFrom[A](implicit ord: Ordering[A]): CanBuildFrom[Coll, A, SortedSet[A]] = new SortedSetCanBuildFrom[A] + + def empty[A](implicit ord: Ordering[A]): SortedSet[A] = TreeSet.empty[A] + +} diff --git a/src/library/scala/collection/mutable/TreeSet.scala b/src/library/scala/collection/mutable/TreeSet.scala new file mode 100644 index 0000000000..38fa0c953f --- /dev/null +++ b/src/library/scala/collection/mutable/TreeSet.scala @@ -0,0 +1,123 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2011, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +package scala.collection +package mutable + +import generic._ + +/** + * @define Coll mutable.TreeSet + * @define coll mutable tree set + * @factoryInfo + * Companion object of TreeSet providing factory related utilities. + * + * @author Lucien Pereira + * + */ +object TreeSet extends MutableSortedSetFactory[TreeSet] { + /** + * The empty set of this type + */ + def empty[A](implicit ordering: Ordering[A]) = new TreeSet[A]() + +} + +/** + * A mutable SortedSet using an immutable AVL Tree as underlying data structure. + * + * @author Lucien Pereira + * + */ +class TreeSet[A](implicit val ordering: Ordering[A]) extends SortedSet[A] with SetLike[A, TreeSet[A]] + with SortedSetLike[A, TreeSet[A]] with Set[A] with Serializable { + + // Projection constructor + private def this(base: Option[TreeSet[A]], from: Option[A], until: Option[A])(implicit ordering: Ordering[A]) { + this(); + this.base = base + this.from = from + this.until = until + } + + private var base: Option[TreeSet[A]] = None + + private var from: Option[A] = None + + private var until: Option[A] = None + + private var avl: AVLTree[A] = Leaf + + private var cardinality: Int = 0 + + def resolve: TreeSet[A] = base.getOrElse(this) + + private def isLeftAcceptable(from: Option[A], ordering: Ordering[A])(a: A): Boolean = + from.map(x => ordering.gteq(a, x)).getOrElse(true) + + private def isRightAcceptable(until: Option[A], ordering: Ordering[A])(a: A): Boolean = + until.map(x => ordering.lt(a, x)).getOrElse(true) + + /** + * Cardinality store the set size, unfortunately a + * set view (given by rangeImpl) + * cannot take advantage of this optimisation + * + */ + override def size: Int = base.map(_ => super.size).getOrElse(cardinality) + + override def stringPrefix = "TreeSet" + + override def empty: TreeSet[A] = TreeSet.empty + + override def rangeImpl(from: Option[A], until: Option[A]): TreeSet[A] = new TreeSet(Some(this), from, until) + + override def -=(elem: A): this.type = { + try { + resolve.avl = AVLTree.remove(elem, resolve.avl, ordering) + resolve.cardinality = resolve.cardinality - 1 + } catch { + case e: NoSuchElementException => () + } + this + } + + override def +=(elem: A): this.type = { + try { + resolve.avl = AVLTree.insert(elem, resolve.avl, ordering) + resolve.cardinality = resolve.cardinality + 1 + } catch { + case e: IllegalArgumentException => () + } + this + } + + /** + * Thanks to the nature immutable of the + * underlying AVL Tree, we can share it with + * the clone. So clone complexity in time is O(1). + * + */ + override def clone: TreeSet[A] = { + val clone = new TreeSet[A](base, from, until) + clone.avl = resolve.avl + clone.cardinality = resolve.cardinality + clone + } + + override def contains(elem: A): Boolean = { + isLeftAcceptable(from, ordering)(elem) && + isRightAcceptable(until, ordering)(elem) && + AVLTree.contains(elem, resolve.avl, ordering) + } + + override def iterator: Iterator[A] = + AVLTree.iterator(resolve.avl, + isLeftAcceptable(from, ordering), + isRightAcceptable(until, ordering)) +} diff --git a/src/library/scala/collection/parallel/ParIterableLike.scala b/src/library/scala/collection/parallel/ParIterableLike.scala index f0d79ada9d..90b64c17f9 100644 --- a/src/library/scala/collection/parallel/ParIterableLike.scala +++ b/src/library/scala/collection/parallel/ParIterableLike.scala @@ -801,7 +801,7 @@ self: ParIterableLike[T, Repr, Sequential] => override def toList: List[T] = seq.toList - override def toIndexedSeq[U >: T]: collection.immutable.IndexedSeq[U] = seq.toIndexedSeq[U] + override def toIndexedSeq: collection.immutable.IndexedSeq[T] = seq.toIndexedSeq override def toStream: Stream[T] = seq.toStream diff --git a/src/library/scala/io/Codec.scala b/src/library/scala/io/Codec.scala index 1a27df1c10..d9cef0edb1 100644 --- a/src/library/scala/io/Codec.scala +++ b/src/library/scala/io/Codec.scala @@ -38,6 +38,9 @@ class Codec(val charSet: Charset) { private[this] var _decodingReplacement: String = null private[this] var _onCodingException: Handler = e => throw e + /** The name of the Codec. */ + override def toString = name + // these methods can be chained to configure the variables above def onMalformedInput(newAction: Action): this.type = { _onMalformedInput = newAction ; this } def onUnmappableCharacter(newAction: Action): this.type = { _onUnmappableCharacter = newAction ; this } diff --git a/src/library/scala/reflect/ClassManifest.scala b/src/library/scala/reflect/ClassManifest.scala index acd28f04f5..466b57dea7 100644 --- a/src/library/scala/reflect/ClassManifest.scala +++ b/src/library/scala/reflect/ClassManifest.scala @@ -127,7 +127,7 @@ trait ClassManifest[T] extends OptManifest[T] with Equals with Serializable { java.lang.reflect.Array.newInstance(tp, 0).getClass.asInstanceOf[jClass[Array[T]]] def arrayManifest: ClassManifest[Array[T]] = - ClassManifest.classType[Array[T]](arrayClass[T](erasure)) + ClassManifest.classType[Array[T]](arrayClass[T](erasure), this) def newArray(len: Int): Array[T] = java.lang.reflect.Array.newInstance(erasure, len).asInstanceOf[Array[T]] @@ -220,7 +220,7 @@ object ClassManifest { new ClassTypeManifest[T](Some(prefix), clazz, args.toList) def arrayType[T](arg: OptManifest[_]): ClassManifest[Array[T]] = arg match { - case NoManifest => Object.asInstanceOf[ClassManifest[Array[T]]] + case NoManifest => Object.asInstanceOf[ClassManifest[Array[T]]] case m: ClassManifest[_] => m.asInstanceOf[ClassManifest[T]].arrayManifest } diff --git a/src/library/scala/reflect/Manifest.scala b/src/library/scala/reflect/Manifest.scala index 18fd34ed2e..8bd45c0e33 100644 --- a/src/library/scala/reflect/Manifest.scala +++ b/src/library/scala/reflect/Manifest.scala @@ -44,7 +44,7 @@ trait Manifest[T] extends ClassManifest[T] with Equals { override def typeArguments: List[Manifest[_]] = Nil override def arrayManifest: Manifest[Array[T]] = - Manifest.classType[Array[T]](arrayClass[T](erasure)) + Manifest.classType[Array[T]](arrayClass[T](erasure), this) override def canEqual(that: Any): Boolean = that match { case _: Manifest[_] => true @@ -60,7 +60,7 @@ trait Manifest[T] extends ClassManifest[T] with Equals { override def hashCode = this.erasure.## } -sealed abstract class AnyValManifest[T <: AnyVal](override val toString: String) extends Manifest[T] with Equals { +abstract class AnyValManifest[T <: AnyVal](override val toString: String) extends Manifest[T] with Equals { override def <:<(that: ClassManifest[_]): Boolean = (that eq this) || (that eq Manifest.Any) || (that eq Manifest.AnyVal) override def canEqual(other: Any) = other match { diff --git a/src/library/scala/reflect/api/Symbols.scala b/src/library/scala/reflect/api/Symbols.scala index 31bcdebe7e..8b4b170847 100755 --- a/src/library/scala/reflect/api/Symbols.scala +++ b/src/library/scala/reflect/api/Symbols.scala @@ -150,10 +150,10 @@ trait Symbols { self: Universe => */ def asTypeIn(site: Type): Type - /** A fresh symbol with given position `pos` and name `name` that has + /** A fresh symbol with given name `name`, position `pos` and flags `flags` that has * the current symbol as its owner. */ - def newNestedSymbol(pos: Position, name: Name): Symbol // needed by LiftCode + def newNestedSymbol(name: Name, pos: Position, flags: Long): Symbol // needed by LiftCode /** Low-level operation to set the symbol's flags * @return the symbol itself diff --git a/src/library/scala/runtime/AbstractPartialFunction.scala b/src/library/scala/runtime/AbstractPartialFunction.scala index f48d99f5af..cbe778f09b 100644 --- a/src/library/scala/runtime/AbstractPartialFunction.scala +++ b/src/library/scala/runtime/AbstractPartialFunction.scala @@ -26,7 +26,7 @@ abstract class AbstractPartialFunction[-T1, +R] private var fallBackField: PartialFunction[T1 @uncheckedVariance, R @uncheckedVariance] = _ def fallBack: PartialFunction[T1, R] = synchronized { - if (fallBackField == null) fallBackField = PartialFunction.empty + if (fallBackField eq null) fallBackField = PartialFunction.empty fallBackField } @@ -38,7 +38,7 @@ abstract class AbstractPartialFunction[-T1, +R] override def orElse[A1 <: T1, B1 >: R](that: PartialFunction[A1, B1]) : PartialFunction[A1, B1] = { val result = this.clone.asInstanceOf[AbstractPartialFunction[A1, B1]] result.synchronized { - result.fallBackField = this.fallBackField orElse that + result.fallBackField = if (this.fallBackField eq null) that else this.fallBackField orElse that result } } diff --git a/src/library/scala/runtime/BoxesRunTime.java b/src/library/scala/runtime/BoxesRunTime.java index c726c56d0e..b19c8d086c 100644 --- a/src/library/scala/runtime/BoxesRunTime.java +++ b/src/library/scala/runtime/BoxesRunTime.java @@ -769,6 +769,24 @@ public final class BoxesRunTime } throw new NoSuchMethodException(); } + + public static boolean isBoxedNumberOrBoolean(Object arg) { + if (arg instanceof java.lang.Boolean) + return true; + else + return isBoxedNumber(arg); + } + public static boolean isBoxedNumber(Object arg) { + return ( + (arg instanceof java.lang.Integer) + || (arg instanceof java.lang.Long) + || (arg instanceof java.lang.Double) + || (arg instanceof java.lang.Float) + || (arg instanceof java.lang.Short) + || (arg instanceof java.lang.Character) + || (arg instanceof java.lang.Byte) + ); + } /** arg.toChar */ public static java.lang.Character toCharacter(Object arg) throws NoSuchMethodException { diff --git a/src/library/scala/xml/Elem.scala b/src/library/scala/xml/Elem.scala index 127e6e0ab7..df52b34f87 100644 --- a/src/library/scala/xml/Elem.scala +++ b/src/library/scala/xml/Elem.scala @@ -41,7 +41,7 @@ object Elem { class Elem( override val prefix: String, val label: String, - override val attributes: MetaData, + attributes1: MetaData, override val scope: NamespaceBinding, val child: Node*) extends Node with Serializable @@ -49,6 +49,8 @@ extends Node with Serializable final override def doCollectNamespaces = true final override def doTransform = true + override val attributes = MetaData.normalize(attributes1, scope) + if (prefix == "") throw new IllegalArgumentException("prefix of zero length, use null instead") diff --git a/src/library/scala/xml/MetaData.scala b/src/library/scala/xml/MetaData.scala index 98e863eb37..c516747bae 100644 --- a/src/library/scala/xml/MetaData.scala +++ b/src/library/scala/xml/MetaData.scala @@ -38,8 +38,8 @@ object MetaData { def iterate(md: MetaData, normalized_attribs: MetaData, set: Set[String]): MetaData = { lazy val key = getUniversalKey(md, scope) if (md eq Null) normalized_attribs - else if (set(key)) iterate(md.next, normalized_attribs, set) - else iterate(md.next, md copy normalized_attribs, set + key) + else if ((md.value eq null) || set(key)) iterate(md.next, normalized_attribs, set) + else md copy iterate(md.next, normalized_attribs, set + key) } iterate(attribs, Null, Set()) } diff --git a/src/library/scala/xml/PrefixedAttribute.scala b/src/library/scala/xml/PrefixedAttribute.scala index 436dfcda43..b80d6a1c73 100644 --- a/src/library/scala/xml/PrefixedAttribute.scala +++ b/src/library/scala/xml/PrefixedAttribute.scala @@ -13,22 +13,25 @@ package scala.xml * * @param pre ... * @param key ... - * @param value the attribute value, which may not be null + * @param value the attribute value * @param next ... */ class PrefixedAttribute( val pre: String, val key: String, val value: Seq[Node], - val next: MetaData) + val next1: MetaData) extends Attribute { - if (value eq null) - throw new UnsupportedOperationException("value is null") + val next = if (value ne null) next1 else next1.remove(key) - /** same as this(key, Utility.parseAttributeValue(value), next) */ + /** same as this(pre, key, Text(value), next), or no attribute if value is null */ def this(pre: String, key: String, value: String, next: MetaData) = - this(pre, key, Text(value), next) + this(pre, key, if (value ne null) Text(value) else null: NodeSeq, next) + + /** same as this(pre, key, value.get, next), or no attribute if value is None */ + def this(pre: String, key: String, value: Option[Seq[Node]], next: MetaData) = + this(pre, key, value.orNull, next) /** Returns a copy of this unprefixed attribute with the given * next field. diff --git a/src/library/scala/xml/UnprefixedAttribute.scala b/src/library/scala/xml/UnprefixedAttribute.scala index c56fba1e6c..b6800d5ed1 100644 --- a/src/library/scala/xml/UnprefixedAttribute.scala +++ b/src/library/scala/xml/UnprefixedAttribute.scala @@ -22,7 +22,7 @@ extends Attribute final val pre = null val next = if (value ne null) next1 else next1.remove(key) - /** same as this(key, Text(value), next) */ + /** same as this(key, Text(value), next), or no attribute if value is null */ def this(key: String, value: String, next: MetaData) = this(key, if (value ne null) Text(value) else null: NodeSeq, next) diff --git a/src/library/scala/xml/Utility.scala b/src/library/scala/xml/Utility.scala index 9b48f4e1bb..fc20b892b9 100644 --- a/src/library/scala/xml/Utility.scala +++ b/src/library/scala/xml/Utility.scala @@ -61,7 +61,7 @@ object Utility extends AnyRef with parsing.TokenTests { val key = md.key val smaller = sort(md.filter { m => m.key < key }) val greater = sort(md.filter { m => m.key > key }) - smaller.append( Null ).append(md.copy ( greater )) + smaller.copy(md.copy ( greater )) } /** Return the node with its attribute list sorted alphabetically diff --git a/src/library/scala/xml/include/sax/Main.scala b/src/library/scala/xml/include/sax/Main.scala index 6b6f6c1593..f58097bcb9 100644 --- a/src/library/scala/xml/include/sax/Main.scala +++ b/src/library/scala/xml/include/sax/Main.scala @@ -10,11 +10,11 @@ package scala.xml package include.sax -import scala.xml.include._ import scala.util.control.Exception.{ catching, ignoring } import org.xml.sax.XMLReader import org.xml.sax.helpers.XMLReaderFactory +@deprecated("Code example will be moved to documentation.", "2.10.0") object Main { private val namespacePrefixes = "http://xml.org/sax/features/namespace-prefixes" private val lexicalHandler = "http://xml.org/sax/properties/lexical-handler" |