diff options
author | Jason Zaugg <jzaugg@gmail.com> | 2015-06-24 15:19:05 +1000 |
---|---|---|
committer | Jason Zaugg <jzaugg@gmail.com> | 2015-06-24 18:10:42 +1000 |
commit | 1f7417c763fb199cacc6afedc6e54796916fd673 (patch) | |
tree | bd00d7e0e47be310172f01c758c01ca5430063c4 /src/library/scala | |
parent | 73f40564a6b19e8b15f0908c3e24f1a8fe405605 (diff) | |
parent | 1b09e12ef3b3fea1cab56bac893295f74de23b8b (diff) | |
download | scala-1f7417c763fb199cacc6afedc6e54796916fd673.tar.gz scala-1f7417c763fb199cacc6afedc6e54796916fd673.tar.bz2 scala-1f7417c763fb199cacc6afedc6e54796916fd673.zip |
Merge branch '2.11.x' into merge/2.11.x-to-2.12.x-20150624
Diffstat (limited to 'src/library/scala')
-rw-r--r-- | src/library/scala/Function0.scala | 8 | ||||
-rw-r--r-- | src/library/scala/Function1.scala | 7 | ||||
-rw-r--r-- | src/library/scala/Function2.scala | 6 | ||||
-rw-r--r-- | src/library/scala/collection/Iterator.scala | 32 | ||||
-rw-r--r-- | src/library/scala/collection/generic/Sorted.scala | 2 | ||||
-rw-r--r-- | src/library/scala/collection/immutable/List.scala | 2 | ||||
-rw-r--r-- | src/library/scala/collection/immutable/NumericRange.scala | 8 | ||||
-rw-r--r-- | src/library/scala/collection/immutable/Queue.scala | 9 | ||||
-rw-r--r-- | src/library/scala/collection/immutable/Stream.scala | 8 | ||||
-rw-r--r-- | src/library/scala/collection/immutable/Vector.scala | 17 | ||||
-rw-r--r-- | src/library/scala/collection/mutable/ListBuffer.scala | 2 | ||||
-rw-r--r-- | src/library/scala/math/BigDecimal.scala | 4 | ||||
-rw-r--r-- | src/library/scala/math/Numeric.scala | 6 | ||||
-rw-r--r-- | src/library/scala/sys/BooleanProp.scala | 7 | ||||
-rw-r--r-- | src/library/scala/util/Sorting.scala | 712 | ||||
-rw-r--r-- | src/library/scala/util/Try.scala | 7 |
16 files changed, 295 insertions, 542 deletions
diff --git a/src/library/scala/Function0.scala b/src/library/scala/Function0.scala index e13aaad7bc..15d0f14938 100644 --- a/src/library/scala/Function0.scala +++ b/src/library/scala/Function0.scala @@ -6,7 +6,7 @@ ** |/ ** \* */ // GENERATED CODE: DO NOT EDIT. -// genprod generated these sources at: Sun Sep 15 20:42:00 CEST 2013 +// genprod generated these sources at: Mon Jun 08 18:05:40 CEST 2015 package scala @@ -26,12 +26,6 @@ package scala * assert(javaVersion() == anonfun0()) * } * }}} - * - * 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. - */ trait Function0[@specialized(Specializable.Primitives) +R] extends AnyRef { self => /** Apply the body of this function to the arguments. diff --git a/src/library/scala/Function1.scala b/src/library/scala/Function1.scala index 620dcc19aa..572901c6f3 100644 --- a/src/library/scala/Function1.scala +++ b/src/library/scala/Function1.scala @@ -25,11 +25,8 @@ package scala * } * }}} * - * 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. - + * Note that the difference between `Function1` and [[scala.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 => diff --git a/src/library/scala/Function2.scala b/src/library/scala/Function2.scala index 5690adb56a..e2c094ea40 100644 --- a/src/library/scala/Function2.scala +++ b/src/library/scala/Function2.scala @@ -25,12 +25,6 @@ package scala * assert(max(0, 1) == anonfun2(0, 1)) * } * }}} - * - * 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. - */ trait Function2[@specialized(scala.Int, scala.Long, scala.Double) -T1, @specialized(scala.Int, scala.Long, scala.Double) -T2, @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 arguments. diff --git a/src/library/scala/collection/Iterator.scala b/src/library/scala/collection/Iterator.scala index 5c4b15ad0f..e2c271145d 100644 --- a/src/library/scala/collection/Iterator.scala +++ b/src/library/scala/collection/Iterator.scala @@ -619,29 +619,21 @@ trait Iterator[+A] extends TraversableOnce[A] { def span(p: A => Boolean): (Iterator[A], Iterator[A]) = { val self = buffered - /* - * Giving a name to following iterator (as opposed to trailing) because - * anonymous class is represented as a structural type that trailing - * iterator is referring (the finish() method) and thus triggering - * handling of structural calls. It's not what's intended here. - */ + // Must be a named class to avoid structural call to finish from trailing iterator class Leading extends AbstractIterator[A] { - val lookahead = new mutable.Queue[A] - def advance() = { - self.hasNext && p(self.head) && { - lookahead += self.next - true - } + private val drained = new mutable.Queue[A] + private var finished = false + def finish(): Unit = { + require(!finished) + finished = true + while (selfish) drained += self.next } - def finish() = { - while (advance()) () - } - def hasNext = lookahead.nonEmpty || advance() + private def selfish = self.hasNext && p(self.head) + def hasNext = if (finished) drained.nonEmpty else selfish def next() = { - if (lookahead.isEmpty) - advance() - - lookahead.dequeue() + if (finished) drained.dequeue() + else if (selfish) self.next() + else empty.next() } } val leading = new Leading diff --git a/src/library/scala/collection/generic/Sorted.scala b/src/library/scala/collection/generic/Sorted.scala index a0b0e1318b..b2e63daaba 100644 --- a/src/library/scala/collection/generic/Sorted.scala +++ b/src/library/scala/collection/generic/Sorted.scala @@ -36,7 +36,7 @@ trait Sorted[K, +This <: Sorted[K, This]] { /** Creates a ranged projection of this collection. Any mutations in the * ranged projection will update this collection and vice versa. * - * Note: keys are not garuanteed to be consistent between this collection + * Note: keys are not guaranteed to be consistent between this collection * and the projection. This is the case for buffers where indexing is * relative to the projection. * diff --git a/src/library/scala/collection/immutable/List.scala b/src/library/scala/collection/immutable/List.scala index 48a6ca5699..7b1997252d 100644 --- a/src/library/scala/collection/immutable/List.scala +++ b/src/library/scala/collection/immutable/List.scala @@ -462,6 +462,7 @@ object List extends SeqFactory[List] { private class SerializationProxy[A](@transient private var orig: List[A]) extends Serializable { private def writeObject(out: ObjectOutputStream) { + out.defaultWriteObject() var xs: List[A] = orig while (!xs.isEmpty) { out.writeObject(xs.head) @@ -473,6 +474,7 @@ object List extends SeqFactory[List] { // Java serialization calls this before readResolve during de-serialization. // Read the whole list and store it in `orig`. private def readObject(in: ObjectInputStream) { + in.defaultReadObject() val builder = List.newBuilder[A] while (true) in.readObject match { case ListSerializeEnd => diff --git a/src/library/scala/collection/immutable/NumericRange.scala b/src/library/scala/collection/immutable/NumericRange.scala index f1ac161e9a..28e56a6d87 100644 --- a/src/library/scala/collection/immutable/NumericRange.scala +++ b/src/library/scala/collection/immutable/NumericRange.scala @@ -12,6 +12,9 @@ package immutable import mutable.{ Builder, ListBuffer } +// TODO: Now the specialization exists there is no clear reason to have +// separate classes for Range/NumericRange. Investigate and consolidate. + /** `NumericRange` is a more generic version of the * `Range` class which works with arbitrary types. * It must be supplied with an `Integral` implementation of the @@ -28,9 +31,6 @@ import mutable.{ Builder, ListBuffer } * assert(r1 sameElements r2.map(_ - veryBig)) * }}} * - * TODO: Now the specialization exists there is no clear reason to have - * separate classes for Range/NumericRange. Investigate and consolidate. - * * @author Paul Phillips * @version 2.8 * @define Coll `NumericRange` @@ -266,7 +266,7 @@ object NumericRange { // Numbers may be big. val one = num.one val limit = num.fromInt(Int.MaxValue) - def check(t: T): T = + def check(t: T): T = if (num.gt(t, limit)) throw new IllegalArgumentException("More than Int.MaxValue elements.") else t // If the range crosses zero, it might overflow when subtracted diff --git a/src/library/scala/collection/immutable/Queue.scala b/src/library/scala/collection/immutable/Queue.scala index 98266716cc..53af3ce158 100644 --- a/src/library/scala/collection/immutable/Queue.scala +++ b/src/library/scala/collection/immutable/Queue.scala @@ -56,11 +56,12 @@ class Queue[+A] protected(protected val in: List[A], protected val out: List[A]) * @throws java.util.NoSuchElementException if the queue is too short. */ override def apply(n: Int): A = { - val len = out.length - if (n < len) out.apply(n) + val olen = out.length + if (n < olen) out.apply(n) else { - val m = n - len - if (m < in.length) in.reverse.apply(m) + val m = n - olen + val ilen = in.length + if (m < ilen) in.apply(ilen - m - 1) else throw new NoSuchElementException("index out of range") } } diff --git a/src/library/scala/collection/immutable/Stream.scala b/src/library/scala/collection/immutable/Stream.scala index ada3533a60..6c5b10e73b 100644 --- a/src/library/scala/collection/immutable/Stream.scala +++ b/src/library/scala/collection/immutable/Stream.scala @@ -153,7 +153,7 @@ import scala.language.implicitConversions * * - The fact that `tail` works at all is of interest. In the definition of * `fibs` we have an initial `(0, 1, Stream(...))` so `tail` is deterministic. - * If we deinfed `fibs` such that only `0` were concretely known then the act + * If we defined `fibs` such that only `0` were concretely known then the act * of determining `tail` would require the evaluation of `tail` which would * cause an infinite recursion and stack overflow. If we define a definition * where the tail is not initially computable then we're going to have an @@ -1134,7 +1134,13 @@ object Stream extends SeqFactory[Stream] { * to streams. */ class ConsWrapper[A](tl: => Stream[A]) { + /** Construct a stream consisting of a given first element followed by elements + * from a lazily evaluated Stream. + */ def #::(hd: A): Stream[A] = cons(hd, tl) + /** Construct a stream consisting of the concatenation of the given stream and + * a lazily evaluated Stream. + */ def #:::(prefix: Stream[A]): Stream[A] = prefix append tl } diff --git a/src/library/scala/collection/immutable/Vector.scala b/src/library/scala/collection/immutable/Vector.scala index 47a623a616..46d5d0c69c 100644 --- a/src/library/scala/collection/immutable/Vector.scala +++ b/src/library/scala/collection/immutable/Vector.scala @@ -132,19 +132,25 @@ override def companion: GenericCompanion[Vector] = Vector throw new IndexOutOfBoundsException(index.toString) } - + // If we have a default builder, there are faster ways to perform some operations + @inline private[this] def isDefaultCBF[A, B, That](bf: CanBuildFrom[Vector[A], B, That]): Boolean = + (bf eq IndexedSeq.ReusableCBF) || (bf eq collection.immutable.Seq.ReusableCBF) || (bf eq collection.Seq.ReusableCBF) + // SeqLike api override def updated[B >: A, That](index: Int, elem: B)(implicit bf: CanBuildFrom[Vector[A], B, That]): That = - if (bf eq IndexedSeq.ReusableCBF) updateAt(index, elem).asInstanceOf[That] // just ignore bf + if (isDefaultCBF[A, B, That](bf)) + updateAt(index, elem).asInstanceOf[That] // ignore bf--it will just give a Vector, and slowly else super.updated(index, elem)(bf) override def +:[B >: A, That](elem: B)(implicit bf: CanBuildFrom[Vector[A], B, That]): That = - if (bf eq IndexedSeq.ReusableCBF) appendFront(elem).asInstanceOf[That] // just ignore bf + if (isDefaultCBF[A, B, That](bf)) + appendFront(elem).asInstanceOf[That] // ignore bf--it will just give a Vector, and slowly else super.+:(elem)(bf) override def :+[B >: A, That](elem: B)(implicit bf: CanBuildFrom[Vector[A], B, That]): That = - if (bf eq IndexedSeq.ReusableCBF) appendBack(elem).asInstanceOf[That] // just ignore bf + if (isDefaultCBF(bf)) + appendBack(elem).asInstanceOf[That] // ignore bf--it will just give a Vector, and slowly else super.:+(elem)(bf) override def take(n: Int): Vector[A] = { @@ -211,7 +217,8 @@ override def companion: GenericCompanion[Vector] = Vector // concat (suboptimal but avoids worst performance gotchas) override def ++[B >: A, That](that: GenTraversableOnce[B])(implicit bf: CanBuildFrom[Vector[A], B, That]): That = { - if (bf eq IndexedSeq.ReusableCBF) { + if (isDefaultCBF(bf)) { + // We are sure we will create a Vector, so let's do it efficiently import Vector.{Log2ConcatFaster, TinyAppendFaster} if (that.isEmpty) this.asInstanceOf[That] else { diff --git a/src/library/scala/collection/mutable/ListBuffer.scala b/src/library/scala/collection/mutable/ListBuffer.scala index 1906c47f61..2bc6738e53 100644 --- a/src/library/scala/collection/mutable/ListBuffer.scala +++ b/src/library/scala/collection/mutable/ListBuffer.scala @@ -15,7 +15,7 @@ import immutable.{List, Nil, ::} import java.io.{ObjectOutputStream, ObjectInputStream} import scala.annotation.migration -/** A `Buffer` implementation back up by a list. It provides constant time +/** A `Buffer` implementation backed by a list. It provides constant time * prepend and append. Most other operations are linear. * * @author Matthias Zenger diff --git a/src/library/scala/math/BigDecimal.scala b/src/library/scala/math/BigDecimal.scala index d6e2963ad8..6bb35606a6 100644 --- a/src/library/scala/math/BigDecimal.scala +++ b/src/library/scala/math/BigDecimal.scala @@ -49,7 +49,7 @@ object BigDecimal { /** Constructs a `BigDecimal` using the decimal text representation of `Double` value `d`, rounding if necessary. */ def decimal(d: Double, mc: MathContext): BigDecimal = - new BigDecimal(new BigDec(java.lang.Double.toString(d), mc)) + new BigDecimal(new BigDec(java.lang.Double.toString(d), mc), mc) /** Constructs a `BigDecimal` using the decimal text representation of `Double` value `d`. */ def decimal(d: Double): BigDecimal = decimal(d, defaultMathContext) @@ -59,7 +59,7 @@ object BigDecimal { * `0.1 != 0.1f`. */ def decimal(f: Float, mc: MathContext): BigDecimal = - new BigDecimal(new BigDec(java.lang.Float.toString(f), mc)) + new BigDecimal(new BigDec(java.lang.Float.toString(f), mc), mc) /** Constructs a `BigDecimal` using the decimal text representation of `Float` value `f`. * Note that `BigDecimal.decimal(0.1f) != 0.1f` since equality agrees with the `Double` representation, and diff --git a/src/library/scala/math/Numeric.scala b/src/library/scala/math/Numeric.scala index eafbf96993..9245798c17 100644 --- a/src/library/scala/math/Numeric.scala +++ b/src/library/scala/math/Numeric.scala @@ -134,7 +134,7 @@ object Numeric { def div(x: Float, y: Float): Float = x / y } trait FloatAsIfIntegral extends FloatIsConflicted with Integral[Float] { - def quot(x: Float, y: Float): Float = (BigDecimal(x) / BigDecimal(y)).floatValue + def quot(x: Float, y: Float): Float = (BigDecimal(x) quot BigDecimal(y)).floatValue def rem(x: Float, y: Float): Float = (BigDecimal(x) remainder BigDecimal(y)).floatValue } implicit object FloatIsFractional extends FloatIsFractional with Ordering.FloatOrdering @@ -158,7 +158,7 @@ object Numeric { def div(x: Double, y: Double): Double = x / y } trait DoubleAsIfIntegral extends DoubleIsConflicted with Integral[Double] { - def quot(x: Double, y: Double): Double = (BigDecimal(x) / BigDecimal(y)).doubleValue + def quot(x: Double, y: Double): Double = (BigDecimal(x) quot BigDecimal(y)).doubleValue def rem(x: Double, y: Double): Double = (BigDecimal(x) remainder BigDecimal(y)).doubleValue } @@ -178,7 +178,7 @@ object Numeric { def div(x: BigDecimal, y: BigDecimal): BigDecimal = x / y } trait BigDecimalAsIfIntegral extends BigDecimalIsConflicted with Integral[BigDecimal] { - def quot(x: BigDecimal, y: BigDecimal): BigDecimal = x / y + def quot(x: BigDecimal, y: BigDecimal): BigDecimal = x quot y def rem(x: BigDecimal, y: BigDecimal): BigDecimal = x remainder y } diff --git a/src/library/scala/sys/BooleanProp.scala b/src/library/scala/sys/BooleanProp.scala index 74b0a9077b..e5e4668edb 100644 --- a/src/library/scala/sys/BooleanProp.scala +++ b/src/library/scala/sys/BooleanProp.scala @@ -63,12 +63,13 @@ object BooleanProp { def valueIsTrue[T](key: String): BooleanProp = new BooleanPropImpl(key, _.toLowerCase == "true") /** As an alternative, this method creates a BooleanProp which is true - * if the key exists in the map. This way -Dfoo.bar is enough to be - * considered true. + * if the key exists in the map and is not assigned a value other than "true", + * compared case-insensitively, or the empty string. This way -Dmy.property + * results in a true-valued property, but -Dmy.property=false does not. * * @return A BooleanProp with a liberal truth policy */ - def keyExists[T](key: String): BooleanProp = new BooleanPropImpl(key, _ => true) + def keyExists[T](key: String): BooleanProp = new BooleanPropImpl(key, s => s == "" || s.equalsIgnoreCase("true")) /** A constant true or false property which ignores all method calls. */ diff --git a/src/library/scala/util/Sorting.scala b/src/library/scala/util/Sorting.scala index 2e021ad9d9..ee2bdbc4a7 100644 --- a/src/library/scala/util/Sorting.scala +++ b/src/library/scala/util/Sorting.scala @@ -1,6 +1,6 @@ /* __ *\ ** ________ ___ / / ___ Scala API ** -** / __/ __// _ | / / / _ | (c) 2006-2009, Ross Judson ** +** / __/ __// _ | / / / _ | (c) 2006-2015, LAMP/EPFL ** ** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** ** /____/\___/_/ |_/____/_/ | | ** ** |/ ** @@ -9,518 +9,276 @@ package scala package util -import scala.reflect.{ ClassTag, classTag } -import scala.math.{ Ordering, max, min } +import scala.reflect.ClassTag +import scala.math.Ordering -/** The Sorting object provides functions that can sort various kinds of - * objects. You can provide a comparison function, or you can request a sort - * of items that are viewable as [[scala.math.Ordered]]. Some sorts that - * operate directly on a subset of value types are also provided. These - * implementations are derived from those in the Sun JDK. +/** The `Sorting` object provides convenience wrappers for `java.util.Arrays.sort`. + * Methods that defer to `java.util.Arrays.sort` say that they do or under what + * conditions that they do. * - * Note that stability doesn't matter for value types, so use the `quickSort` - * variants for those. `stableSort` is intended to be used with - * objects when the prior ordering should be preserved, where possible. + * `Sorting` also implements a general-purpose quicksort and stable (merge) sort + * for those cases where `java.util.Arrays.sort` could only be used at the cost + * of a large memory penalty. If performance rather than memory usage is the + * primary concern, one may wish to find alternate strategies to use + * `java.util.Arrays.sort` directly e.g. by boxing primitives to use + * a custom ordering on them. + * + * `Sorting` provides methods where you can provide a comparison function, or + * can request a sort of items that are [[scala.math.Ordered]] or that + * otherwise have an implicit or explicit [[scala.math.Ordering]]. + * + * Note also that high-performance non-default sorts for numeric types + * are not provided. If this is required, it is advisable to investigate + * other libraries that cover this use case. * * @author Ross Judson - * @version 1.0 + * @author Adriaan Moors + * @author Rex Kerr + * @version 1.1 */ object Sorting { - /** Quickly sort an array of Doubles. */ - def quickSort(a: Array[Double]) { sort1(a, 0, a.length) } - - /** Quickly sort an array of items with an implicit Ordering. */ - def quickSort[K: Ordering](a: Array[K]) { sort1(a, 0, a.length) } - - /** Quickly sort an array of Ints. */ - def quickSort(a: Array[Int]) { sort1(a, 0, a.length) } - - /** Quickly sort an array of Floats. */ - def quickSort(a: Array[Float]) { sort1(a, 0, a.length) } - - /** Sort an array of K where K is Ordered, preserving the existing order - * where the values are equal. */ - def stableSort[K: ClassTag: Ordering](a: Array[K]) { - stableSort(a, 0, a.length-1, new Array[K](a.length), Ordering[K].lt _) - } + /** Sort an array of Doubles using `java.util.Arrays.sort`. */ + def quickSort(a: Array[Double]): Unit = java.util.Arrays.sort(a) - /** Sorts an array of `K` given an ordering function `f`. - * `f` should return `true` iff its first parameter is strictly less than its second parameter. - */ - def stableSort[K: ClassTag](a: Array[K], f: (K, K) => Boolean) { - stableSort(a, 0, a.length-1, new Array[K](a.length), f) - } + /** Sort an array of Ints using `java.util.Arrays.sort`. */ + def quickSort(a: Array[Int]): Unit = java.util.Arrays.sort(a) - /** Sorts an arbitrary sequence into an array, given a comparison function - * that should return `true` iff parameter one is strictly less than parameter two. - * - * @param a the sequence to be sorted. - * @param f the comparison function. - * @return the sorted sequence of items. - */ - def stableSort[K: ClassTag](a: Seq[K], f: (K, K) => Boolean): Array[K] = { - val ret = a.toArray - stableSort(ret, f) - ret - } + /** Sort an array of Floats using `java.util.Arrays.sort`. */ + def quickSort(a: Array[Float]): Unit = java.util.Arrays.sort(a) + + private final val qsortThreshold = 16 - /** Sorts an arbitrary sequence of items that are viewable as ordered. */ - def stableSort[K: ClassTag: Ordering](a: Seq[K]): Array[K] = - stableSort(a, Ordering[K].lt _) - - /** Stably sorts a sequence of items given an extraction function that will - * return an ordered key from an item. - * - * @param a the sequence to be sorted. - * @param f the comparison function. - * @return the sorted sequence of items. - */ - def stableSort[K: ClassTag, M: Ordering](a: Seq[K], f: K => M): Array[K] = - stableSort(a)(implicitly[ClassTag[K]], Ordering[M] on f) - - private def sort1[K: Ordering](x: Array[K], off: Int, len: Int) { - val ord = Ordering[K] - import ord._ - - def swap(a: Int, b: Int) { - val t = x(a) - x(a) = x(b) - x(b) = t - } - def vecswap(_a: Int, _b: Int, n: Int) { - var a = _a - var b = _b - var i = 0 - while (i < n) { - swap(a, b) - i += 1 - a += 1 - b += 1 - } - } - def med3(a: Int, b: Int, c: Int) = { - if (x(a) < x(b)) { - if (x(b) < x(c)) b else if (x(a) < x(c)) c else a - } else { - if (x(b) > x(c)) b else if (x(a) > x(c)) c else a - } - } - def sort2(off: Int, len: Int) { - // Insertion sort on smallest arrays - if (len < 7) { - var i = off - while (i < len + off) { - var j = i - while (j > off && x(j-1) > x(j)) { - swap(j, j-1) - j -= 1 + /** Sort array `a` with quicksort, using the Ordering on its elements. + * This algorithm sorts in place, so no additional memory is used aside from + * what might be required to box individual elements during comparison. + */ + def quickSort[K: Ordering](a: Array[K]): Unit = { + // Must have iN >= i0 or math will fail. Also, i0 >= 0. + def inner(a: Array[K], i0: Int, iN: Int, ord: Ordering[K]): Unit = { + if (iN - i0 < qsortThreshold) insertionSort(a, i0, iN, ord) + else { + var iK = (i0 + iN) >>> 1 // Unsigned div by 2 + // Find index of median of first, central, and last elements + var pL = + if (ord.compare(a(i0), a(iN - 1)) <= 0) + if (ord.compare(a(i0), a(iK)) < 0) + if (ord.compare(a(iN - 1), a(iK)) < 0) iN - 1 else iK + else i0 + else + if (ord.compare(a(i0), a(iK)) < 0) i0 + else + if (ord.compare(a(iN - 1), a(iK)) <= 0) iN - 1 + else iK + val pivot = a(pL) + // pL is the start of the pivot block; move it into the middle if needed + if (pL != iK) { a(pL) = a(iK); a(iK) = pivot; pL = iK } + // Elements equal to the pivot will be in range pL until pR + var pR = pL + 1 + // Items known to be less than pivot are below iA (range i0 until iA) + var iA = i0 + // Items known to be greater than pivot are at or above iB (range iB until iN) + var iB = iN + // Scan through everything in the buffer before the pivot(s) + while (pL - iA > 0) { + val current = a(iA) + ord.compare(current, pivot) match { + case 0 => + // Swap current out with pivot block + a(iA) = a(pL - 1) + a(pL - 1) = current + pL -= 1 + case x if x < 0 => + // Already in place. Just update indicies. + iA += 1 + case _ if iB > pR => + // Wrong side. There's room on the other side, so swap + a(iA) = a(iB - 1) + a(iB - 1) = current + iB -= 1 + case _ => + // Wrong side and there is no room. Swap by rotating pivot block. + a(iA) = a(pL - 1) + a(pL - 1) = a(pR - 1) + a(pR - 1) = current + pL -= 1 + pR -= 1 + iB -= 1 } - i += 1 } - } else { - // Choose a partition element, v - var m = off + (len >> 1) // Small arrays, middle element - if (len > 7) { - var l = off - var n = off + len - 1 - if (len > 40) { // Big arrays, pseudomedian of 9 - val s = len / 8 - l = med3(l, l+s, l+2*s) - m = med3(m-s, m, m+s) - n = med3(n-2*s, n-s, n) + // Get anything remaining in buffer after the pivot(s) + while (iB - pR > 0) { + val current = a(iB - 1) + ord.compare(current, pivot) match { + case 0 => + // Swap current out with pivot block + a(iB - 1) = a(pR) + a(pR) = current + pR += 1 + case x if x > 0 => + // Already in place. Just update indices. + iB -= 1 + case _ => + // Wrong side and we already know there is no room. Swap by rotating pivot block. + a(iB - 1) = a(pR) + a(pR) = a(pL) + a(pL) = current + iA += 1 + pL += 1 + pR += 1 } - m = med3(l, m, n) // Mid-size, med of 3 } - val v = x(m) - - // Establish Invariant: v* (<v)* (>v)* v* - var a = off - var b = a - var c = off + len - 1 - var d = c - var done = false - while (!done) { - while (b <= c && x(b) <= v) { - if (x(b) equiv v) { - swap(a, b) - a += 1 - } - b += 1 - } - while (c >= b && x(c) >= v) { - if (x(c) equiv v) { - swap(c, d) - d -= 1 - } - c -= 1 - } - if (b > c) { - done = true - } else { - swap(b, c) - c -= 1 - b += 1 - } + // Use tail recursion on large half (Sedgewick's method) so we don't blow up the stack if pivots are poorly chosen + if (iA - i0 < iN - iB) { + inner(a, i0, iA, ord) // True recursion + inner(a, iB, iN, ord) // Should be tail recursion + } + else { + inner(a, iB, iN, ord) // True recursion + inner(a, i0, iA, ord) // Should be tail recursion } - - // Swap partition elements back to middle - val n = off + len - var s = math.min(a-off, b-a) - vecswap(off, b-s, s) - s = math.min(d-c, n-d-1) - vecswap(b, n-s, s) - - // Recursively sort non-partition-elements - s = b - a - if (s > 1) - sort2(off, s) - s = d - c - if (s > 1) - sort2(n-s, s) } } - sort2(off, len) + inner(a, 0, a.length, implicitly[Ordering[K]]) } - - private def sort1(x: Array[Int], off: Int, len: Int) { - def swap(a: Int, b: Int) { - val t = x(a) - x(a) = x(b) - x(b) = t + + private final val mergeThreshold = 32 + + // Ordering[T] might be slow especially for boxed primitives, so use binary search variant of insertion sort + // Caller must pass iN >= i0 or math will fail. Also, i0 >= 0. + private def insertionSort[@specialized T](a: Array[T], i0: Int, iN: Int, ord: Ordering[T]): Unit = { + val n = iN - i0 + if (n < 2) return + if (ord.compare(a(i0), a(i0+1)) > 0) { + val temp = a(i0) + a(i0) = a(i0+1) + a(i0+1) = temp } - def vecswap(_a: Int, _b: Int, n: Int) { - var a = _a - var b = _b - var i = 0 - while (i < n) { - swap(a, b) - i += 1 - a += 1 - b += 1 - } - } - def med3(a: Int, b: Int, c: Int) = { - if (x(a) < x(b)) { - if (x(b) < x(c)) b else if (x(a) < x(c)) c else a - } else { - if (x(b) > x(c)) b else if (x(a) > x(c)) c else a - } - } - def sort2(off: Int, len: Int) { - // Insertion sort on smallest arrays - if (len < 7) { - var i = off - while (i < len + off) { - var j = i - while (j>off && x(j-1) > x(j)) { - swap(j, j-1) - j -= 1 - } - i += 1 + var m = 2 + while (m < n) { + // Speed up already-sorted case by checking last element first + val next = a(i0 + m) + if (ord.compare(next, a(i0+m-1)) < 0) { + var iA = i0 + var iB = i0 + m - 1 + while (iB - iA > 1) { + val ix = (iA + iB) >>> 1 // Use bit shift to get unsigned div by 2 + if (ord.compare(next, a(ix)) < 0) iB = ix + else iA = ix } - } else { - // Choose a partition element, v - var m = off + (len >> 1) // Small arrays, middle element - if (len > 7) { - var l = off - var n = off + len - 1 - if (len > 40) { // Big arrays, pseudomedian of 9 - val s = len / 8 - l = med3(l, l+s, l+2*s) - m = med3(m-s, m, m+s) - n = med3(n-2*s, n-s, n) - } - m = med3(l, m, n) // Mid-size, med of 3 - } - val v = x(m) - - // Establish Invariant: v* (<v)* (>v)* v* - var a = off - var b = a - var c = off + len - 1 - var d = c - var done = false - while (!done) { - while (b <= c && x(b) <= v) { - if (x(b) == v) { - swap(a, b) - a += 1 - } - b += 1 - } - while (c >= b && x(c) >= v) { - if (x(c) == v) { - swap(c, d) - d -= 1 - } - c -= 1 - } - if (b > c) { - done = true - } else { - swap(b, c) - c -= 1 - b += 1 - } + val ix = iA + (if (ord.compare(next, a(iA)) < 0) 0 else 1) + var i = i0 + m + while (i > ix) { + a(i) = a(i-1) + i -= 1 } - - // Swap partition elements back to middle - val n = off + len - var s = math.min(a-off, b-a) - vecswap(off, b-s, s) - s = math.min(d-c, n-d-1) - vecswap(b, n-s, s) - - // Recursively sort non-partition-elements - s = b - a - if (s > 1) - sort2(off, s) - s = d - c - if (s > 1) - sort2(n-s, s) + a(ix) = next } + m += 1 } - sort2(off, len) } - - private def sort1(x: Array[Double], off: Int, len: Int) { - def swap(a: Int, b: Int) { - val t = x(a) - x(a) = x(b) - x(b) = t + + // Caller is required to pass iN >= i0, else math will fail. Also, i0 >= 0. + private def mergeSort[@specialized T: ClassTag](a: Array[T], i0: Int, iN: Int, ord: Ordering[T], scratch: Array[T] = null): Unit = { + if (iN - i0 < mergeThreshold) insertionSort(a, i0, iN, ord) + else { + val iK = (i0 + iN) >>> 1 // Bit shift equivalent to unsigned math, no overflow + val sc = if (scratch eq null) new Array[T](iK - i0) else scratch + mergeSort(a, i0, iK, ord, sc) + mergeSort(a, iK, iN, ord, sc) + mergeSorted(a, i0, iK, iN, ord, sc) } - def vecswap(_a: Int, _b: Int, n: Int) { - var a = _a - var b = _b - var i = 0 - while (i < n) { - swap(a, b) + } + + // Must have 0 <= i0 < iK < iN + private def mergeSorted[@specialized T](a: Array[T], i0: Int, iK: Int, iN: Int, ord: Ordering[T], scratch: Array[T]): Unit = { + // Check to make sure we're not already in order + if (ord.compare(a(iK-1), a(iK)) > 0) { + var i = i0 + val jN = iK - i0 + var j = 0 + while (i < iK) { + scratch (j) = a(i) i += 1 - a += 1 - b += 1 - } - } - def med3(a: Int, b: Int, c: Int) = { - val ab = x(a) compare x(b) - val bc = x(b) compare x(c) - val ac = x(a) compare x(c) - if (ab < 0) { - if (bc < 0) b else if (ac < 0) c else a - } else { - if (bc > 0) b else if (ac > 0) c else a + j += 1 } - } - def sort2(off: Int, len: Int) { - // Insertion sort on smallest arrays - if (len < 7) { - var i = off - while (i < len + off) { - var j = i - while (j > off && (x(j-1) compare x(j)) > 0) { - swap(j, j-1) - j -= 1 - } - i += 1 - } - } else { - // Choose a partition element, v - var m = off + (len >> 1) // Small arrays, middle element - if (len > 7) { - var l = off - var n = off + len - 1 - if (len > 40) { // Big arrays, pseudomedian of 9 - val s = len / 8 - l = med3(l, l+s, l+2*s) - m = med3(m-s, m, m+s) - n = med3(n-2*s, n-s, n) - } - m = med3(l, m, n) // Mid-size, med of 3 - } - val v = x(m) - - // Establish Invariant: v* (<v)* (>v)* v* - var a = off - var b = a - var c = off + len - 1 - var d = c - var done = false - while (!done) { - var bv = x(b) compare v - while (b <= c && bv <= 0) { - if (bv == 0) { - swap(a, b) - a += 1 - } - b += 1 - if (b <= c) bv = x(b) compare v - } - var cv = x(c) compare v - while (c >= b && cv >= 0) { - if (cv == 0) { - swap(c, d) - d -= 1 - } - c -= 1 - if (c >= b) cv = x(c) compare v - } - if (b > c) { - done = true - } else { - swap(b, c) - c -= 1 - b += 1 - } - } - - // Swap partition elements back to middle - val n = off + len - var s = math.min(a-off, b-a) - vecswap(off, b-s, s) - s = math.min(d-c, n-d-1) - vecswap(b, n-s, s) - - // Recursively sort non-partition-elements - s = b - a - if (s > 1) - sort2(off, s) - s = d - c - if (s > 1) - sort2(n-s, s) + var k = i0 + j = 0 + while (i < iN && j < jN) { + if (ord.compare(a(i), scratch(j)) < 0) { a(k) = a(i); i += 1 } + else { a(k) = scratch(j); j += 1 } + k += 1 } + while (j < jN) { a(k) = scratch(j); j += 1; k += 1 } + // Don't need to finish a(i) because it's already in place, k = i } - sort2(off, len) } - - private def sort1(x: Array[Float], off: Int, len: Int) { - def swap(a: Int, b: Int) { - val t = x(a) - x(a) = x(b) - x(b) = t + + // Why would you even do this? + private def booleanSort(a: Array[Boolean]): Unit = { + var i = 0 + var n = 0 + while (i < a.length) { + if (!a(i)) n += 1 + i += 1 } - def vecswap(_a: Int, _b: Int, n: Int) { - var a = _a - var b = _b - var i = 0 - while (i < n) { - swap(a, b) - i += 1 - a += 1 - b += 1 - } + i = 0 + while (i < n) { + a(i) = false + i += 1 } - def med3(a: Int, b: Int, c: Int) = { - val ab = x(a) compare x(b) - val bc = x(b) compare x(c) - val ac = x(a) compare x(c) - if (ab < 0) { - if (bc < 0) b else if (ac < 0) c else a - } else { - if (bc > 0) b else if (ac > 0) c else a - } + while (i < a.length) { + a(i) = true + i += 1 } - def sort2(off: Int, len: Int) { - // Insertion sort on smallest arrays - if (len < 7) { - var i = off - while (i < len + off) { - var j = i - while (j > off && (x(j-1) compare x(j)) > 0) { - swap(j, j-1) - j -= 1 - } - i += 1 - } - } else { - // Choose a partition element, v - var m = off + (len >> 1) // Small arrays, middle element - if (len > 7) { - var l = off - var n = off + len - 1 - if (len > 40) { // Big arrays, pseudomedian of 9 - val s = len / 8 - l = med3(l, l+s, l+2*s) - m = med3(m-s, m, m+s) - n = med3(n-2*s, n-s, n) - } - m = med3(l, m, n) // Mid-size, med of 3 - } - val v = x(m) + } - // Establish Invariant: v* (<v)* (>v)* v* - var a = off - var b = a - var c = off + len - 1 - var d = c - var done = false - while (!done) { - var bv = x(b) compare v - while (b <= c && bv <= 0) { - if (bv == 0) { - swap(a, b) - a += 1 - } - b += 1 - if (b <= c) bv = x(b) compare v - } - var cv = x(c) compare v - while (c >= b && cv >= 0) { - if (cv == 0) { - swap(c, d) - d -= 1 - } - c -= 1 - if (c >= b) cv = x(c) compare v - } - if (b > c) { - done = true - } else { - swap(b, c) - c -= 1 - b += 1 - } - } + // TODO: add upper bound: T <: AnyRef, propagate to callers below (not binary compatible) + // Maybe also rename all these methods to `sort`. + @inline private def sort[T](a: Array[T], ord: Ordering[T]): Unit = a match { + case _: Array[AnyRef] => + // Note that runtime matches are covariant, so could actually be any Array[T] s.t. T is not primitive (even boxed value classes) + if (a.length > 1 && (ord eq null)) throw new NullPointerException("Ordering") + java.util.Arrays.sort(a, ord) + case a: Array[Int] => if (ord eq Ordering.Int) java.util.Arrays.sort(a) else mergeSort[Int](a, 0, a.length, ord) + case a: Array[Double] => mergeSort[Double](a, 0, a.length, ord) // Because not all NaNs are identical, stability is meaningful! + case a: Array[Long] => if (ord eq Ordering.Long) java.util.Arrays.sort(a) else mergeSort[Long](a, 0, a.length, ord) + case a: Array[Float] => mergeSort[Float](a, 0, a.length, ord) // Because not all NaNs are identical, stability is meaningful! + case a: Array[Char] => if (ord eq Ordering.Char) java.util.Arrays.sort(a) else mergeSort[Char](a, 0, a.length, ord) + case a: Array[Byte] => if (ord eq Ordering.Byte) java.util.Arrays.sort(a) else mergeSort[Byte](a, 0, a.length, ord) + case a: Array[Short] => if (ord eq Ordering.Short) java.util.Arrays.sort(a) else mergeSort[Short](a, 0, a.length, ord) + case a: Array[Boolean] => if (ord eq Ordering.Boolean) booleanSort(a) else mergeSort[Boolean](a, 0, a.length, ord) + // Array[Unit] is matched as an Array[AnyRef] due to covariance in runtime matching. Not worth catching it as a special case. + case null => throw new NullPointerException + } - // Swap partition elements back to middle - val n = off + len - var s = math.min(a-off, b-a) - vecswap(off, b-s, s) - s = math.min(d-c, n-d-1) - vecswap(b, n-s, s) + // TODO: remove unnecessary ClassTag (not binary compatible) + /** Sort array `a` using the Ordering on its elements, preserving the original ordering where possible. Uses `java.util.Arrays.sort` unless `K` is a primitive type. */ + def stableSort[K: ClassTag: Ordering](a: Array[K]): Unit = sort(a, Ordering[K]) - // Recursively sort non-partition-elements - s = b - a - if (s > 1) - sort2(off, s) - s = d - c - if (s > 1) - sort2(n-s, s) - } - } - sort2(off, len) + // TODO: Remove unnecessary ClassTag (not binary compatible) + // TODO: make this fast for primitive K (could be specialized if it didn't go through Ordering) + /** Sort array `a` using function `f` that computes the less-than relation for each element. Uses `java.util.Arrays.sort` unless `K` is a primitive type. */ + def stableSort[K: ClassTag](a: Array[K], f: (K, K) => Boolean): Unit = sort(a, Ordering fromLessThan f) + + /** A sorted Array, using the Ordering for the elements in the sequence `a`. Uses `java.util.Arrays.sort` unless `K` is a primitive type. */ + def stableSort[K: ClassTag: Ordering](a: Seq[K]): Array[K] = { + val ret = a.toArray + sort(ret, Ordering[K]) + ret } - private def stableSort[K : ClassTag](a: Array[K], lo: Int, hi: Int, scratch: Array[K], f: (K,K) => Boolean) { - if (lo < hi) { - val mid = (lo+hi) / 2 - stableSort(a, lo, mid, scratch, f) - stableSort(a, mid+1, hi, scratch, f) - var k, t_lo = lo - var t_hi = mid + 1 - while (k <= hi) { - if ((t_lo <= mid) && ((t_hi > hi) || (!f(a(t_hi), a(t_lo))))) { - scratch(k) = a(t_lo) - t_lo += 1 - } else { - scratch(k) = a(t_hi) - t_hi += 1 - } - k += 1 - } - k = lo - while (k <= hi) { - a(k) = scratch(k) - k += 1 - } - } + // TODO: make this fast for primitive K (could be specialized if it didn't go through Ordering) + /** A sorted Array, given a function `f` that computes the less-than relation for each item in the sequence `a`. Uses `java.util.Arrays.sort` unless `K` is a primitive type. */ + def stableSort[K: ClassTag](a: Seq[K], f: (K, K) => Boolean): Array[K] = { + val ret = a.toArray + sort(ret, Ordering fromLessThan f) + ret + } + + /** A sorted Array, given an extraction function `f` that returns an ordered key for each item in the sequence `a`. Uses `java.util.Arrays.sort` unless `K` is a primitive type. */ + def stableSort[K: ClassTag, M: Ordering](a: Seq[K], f: K => M): Array[K] = { + val ret = a.toArray + sort(ret, Ordering[M] on f) + ret } } diff --git a/src/library/scala/util/Try.scala b/src/library/scala/util/Try.scala index 1a13ac2305..b1b9965614 100644 --- a/src/library/scala/util/Try.scala +++ b/src/library/scala/util/Try.scala @@ -24,11 +24,12 @@ import scala.language.implicitConversions * * Example: * {{{ + * import scala.io.StdIn * import scala.util.{Try, Success, Failure} * * def divide: Try[Int] = { - * val dividend = Try(Console.readLine("Enter an Int that you'd like to divide:\n").toInt) - * val divisor = Try(Console.readLine("Enter an Int that you'd like to divide by:\n").toInt) + * val dividend = Try(StdIn.readLine("Enter an Int that you'd like to divide:\n").toInt) + * val divisor = Try(StdIn.readLine("Enter an Int that you'd like to divide by:\n").toInt) * val problem = dividend.flatMap(x => divisor.map(y => x/y)) * problem match { * case Success(v) => @@ -47,7 +48,7 @@ import scala.language.implicitConversions * catching exceptions along the way. The `flatMap` and `map` combinators in the above example each essentially * pass off either their successfully completed value, wrapped in the `Success` type for it to be further operated * upon by the next combinator in the chain, or the exception wrapped in the `Failure` type usually to be simply - * passed on down the chain. Combinators such as `rescue` and `recover` are designed to provide some type of + * passed on down the chain. Combinators such as `recover` and `recoverWith` are designed to provide some type of * default behavior in the case of failure. * * ''Note'': only non-fatal exceptions are caught by the combinators on `Try` (see [[scala.util.control.NonFatal]]). |