diff options
author | Paul Phillips <paulp@improving.org> | 2009-08-29 00:54:16 +0000 |
---|---|---|
committer | Paul Phillips <paulp@improving.org> | 2009-08-29 00:54:16 +0000 |
commit | a1efb93af42eb87eac6343f23e98911aa0394a0f (patch) | |
tree | 9d4cca048aedb812e8f52fb2b68aa911d0afb8f9 | |
parent | 7e67e62dcaf0afe2a51dcedf0d3768c507116838 (diff) | |
download | scala-a1efb93af42eb87eac6343f23e98911aa0394a0f.tar.gz scala-a1efb93af42eb87eac6343f23e98911aa0394a0f.tar.bz2 scala-a1efb93af42eb87eac6343f23e98911aa0394a0f.zip |
Moves sorting into Iterable, and adds a conveni...
Moves sorting into Iterable, and adds a convenience creation method to
the Ordering object.
4 files changed, 33 insertions, 28 deletions
diff --git a/src/library/scala/Ordering.scala b/src/library/scala/Ordering.scala index d744dc9257..97ba58e37e 100644 --- a/src/library/scala/Ordering.scala +++ b/src/library/scala/Ordering.scala @@ -107,6 +107,10 @@ object Ordering { def apply[T](implicit ord : Ordering[T]) = ord + def fromLessThan[T](cmp: (T, T) => Boolean): Ordering[T] = new Ordering[T] { + def compare(x: T, y: T) = if (cmp(x, y)) -1 else if (cmp(y, x)) 1 else 0 + } + def ordered[A <: Ordered[A]] : Ordering[A] = new Ordering[A] { def compare(x : A, y : A) = x.compare(y); } diff --git a/src/library/scala/collection/generic/IterableTemplate.scala b/src/library/scala/collection/generic/IterableTemplate.scala index 1f20ea3f07..e6d2652ebd 100644 --- a/src/library/scala/collection/generic/IterableTemplate.scala +++ b/src/library/scala/collection/generic/IterableTemplate.scala @@ -10,6 +10,7 @@ package scala.collection.generic import scala.collection._ +import annotation.unchecked.uncheckedVariance import util.control.Breaks._ // import immutable.Stream // !!! @@ -207,6 +208,31 @@ trait IterableTemplate[+A, +This <: IterableTemplate[A, This] with Iterable[A]] b.result } + /** Sort the iterable according to the comparison function + * <code><(e1: a, e2: a) => Boolean</code>, + * which should be true iff <code>e1</code> is smaller than + * <code>e2</code>. + * The sort is stable. That is elements that are equal wrt `lt` appear in the + * same order in the sorted sequence as in the original. + * + * @param lt the comparison function + * @return an iterable sorted according to the comparison function + * <code><(e1: a, e2: a) => Boolean</code>. + * @ex <pre> + * List("Steve", "Tom", "John", "Bob") + * .sortWith((e1, e2) => (e1 compareTo e2) < 0) = + * List("Bob", "John", "Steve", "Tom")</pre> + */ + def sortWith(lt: (A, A) => Boolean)(implicit m: ClassManifest[A @uncheckedVariance]): This = { + // !!! can we supply a default argument to m: ClassManifest ? + val arr = toArray + java.util.Arrays.sort(arr, Ordering fromLessThan lt) + + val b = newBuilder + for (x <- arr) b += x + b.result + } + /** Checks if the other iterable object contains the same elements as this one. * * @note will not terminate for infinite-sized iterables. diff --git a/src/library/scala/collection/generic/SequenceTemplate.scala b/src/library/scala/collection/generic/SequenceTemplate.scala index cdbe827905..e0de4666df 100644 --- a/src/library/scala/collection/generic/SequenceTemplate.scala +++ b/src/library/scala/collection/generic/SequenceTemplate.scala @@ -11,7 +11,6 @@ package scala.collection.generic import scala.collection._ -import annotation.unchecked.uncheckedVariance import mutable.{ListBuffer, HashMap} @@ -520,33 +519,6 @@ trait SequenceTemplate[+A, +This <: IterableTemplate[A, This] with Sequence[A]] */ override def toString = super[IterableTemplate].toString - /** Sort the sequence according to the comparison function - * <code><(e1: a, e2: a) => Boolean</code>, - * which should be true iff <code>e1</code> is smaller than - * <code>e2</code>. - * The sort is stable. That is elements that are equal wrt `lt` appear in the - * same order in the sorted sequence as in the original. - * - * @param lt the comparison function - * @return a sequence sorted according to the comparison function - * <code><(e1: a, e2: a) => Boolean</code>. - * @ex <pre> - * List("Steve", "Tom", "John", "Bob") - * .sortWith((e1, e2) => (e1 compareTo e2) < 0) = - * List("Bob", "John", "Steve", "Tom")</pre> - */ - def sortWith(lt: (A, A) => Boolean)(implicit m: ClassManifest[A @uncheckedVariance]): This = { - val arr = toArray - import java.util.{Arrays, Comparator} - Arrays.sort(arr, new Comparator[A] { - override def compare(a: A, b: A) = - if (lt(a, b)) -1 else if (lt(b, a)) 1 else 0 - }) - val b = newBuilder - for (x <- arr) b += x - b.result - } - /** Returns index of the last element satisying a predicate, or -1. */ @deprecated("use `lastIndexWhere' instead") def findLastIndexOf(p: A => Boolean): Int = lastIndexWhere(p) diff --git a/src/library/scala/collection/immutable/List.scala b/src/library/scala/collection/immutable/List.scala index abd8e31dc3..502fe6273a 100644 --- a/src/library/scala/collection/immutable/List.scala +++ b/src/library/scala/collection/immutable/List.scala @@ -429,6 +429,9 @@ sealed abstract class List[+A] extends LinearSequence[A] ms(this) } + // !!! The above sort could be replaced by: + // def sort(lt: (A, A) => Boolean): List[A] = super.sortWith(lt) + // except that it fails to find a ClassManifest. } /** The empty list. |