diff options
| -rw-r--r-- | src/library/scala/math/Ordering.scala | 24 | ||||
| -rw-r--r-- | src/library/scala/util/Sorting.scala | 44 | ||||
| -rw-r--r-- | test/files/run/comparable-comparator.scala | 28 |
3 files changed, 55 insertions, 41 deletions
diff --git a/src/library/scala/math/Ordering.scala b/src/library/scala/math/Ordering.scala index fdfc4915d9..047b0c3d11 100644 --- a/src/library/scala/math/Ordering.scala +++ b/src/library/scala/math/Ordering.scala @@ -108,20 +108,23 @@ trait Ordering[T] extends Comparator[T] with PartialOrdering[T] { implicit def mkOrderingOps(lhs: T): Ops = new Ops(lhs) } -/** This would conflict with all the nice implicit Orderings - * available, but thanks to the magic of prioritized implicits - * via subclassing we can make Ordered[A] => Ordering[A] only - * turn up if nothing else works. - */ trait LowPriorityOrderingImplicits { - implicit def ordered[A <: Ordered[A]]: Ordering[A] = new Ordering[A] { - def compare(x: A, y: A) = x.compare(y) + /** This would conflict with all the nice implicit Orderings + * available, but thanks to the magic of prioritized implicits + * via subclassing we can make Ordered[A] => Ordering[A] only + * turn up if nothing else works. Since Ordered[A] extends + * Comparable[A] anyway, we can throw in some java interop too. + */ + implicit def ordered[A <% Comparable[A]]: Ordering[A] = new Ordering[A] { + def compare(x: A, y: A): Int = x compareTo y + } + implicit def comparatorToOrdering[A](implicit cmp: Comparator[A]): Ordering[A] = new Ordering[A] { + def compare(x: A, y: A) = cmp.compare(x, y) } } object Ordering extends LowPriorityOrderingImplicits { - - def apply[T](implicit ord : Ordering[T]) = ord + 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 @@ -132,7 +135,8 @@ object Ordering extends LowPriorityOrderingImplicits { override def lteq(x: T, y: T): Boolean = !cmp(y, x) } - def by[T, S: Ordering](f: T => S): Ordering[T] = fromLessThan((x, y) => implicitly[Ordering[S]].lt(f(x), f(y))) + def by[T, S](f: T => S)(implicit ord: Ordering[S]): Ordering[T] = + fromLessThan((x, y) => ord.lt(f(x), f(y))) trait UnitOrdering extends Ordering[Unit] { def compare(x: Unit, y: Unit) = 0 diff --git a/src/library/scala/util/Sorting.scala b/src/library/scala/util/Sorting.scala index 8174a0e711..e687335b65 100644 --- a/src/library/scala/util/Sorting.scala +++ b/src/library/scala/util/Sorting.scala @@ -6,9 +6,8 @@ ** |/ ** \* */ - - package scala.util + import scala.reflect.ClassManifest /** The Sorting object provides functions that can sort various kinds of @@ -25,18 +24,11 @@ import scala.reflect.ClassManifest * @version 1.0 */ object Sorting { - - /** Provides implicit access to sorting on arbitrary sequences of orderable - * items. This doesn't quite work the way that I want yet -- K should be - * bounded as viewable, but the compiler rejects that. - */ - // implicit def seq2RichSort[K <: Ordered[K] : ClassManifest](s: Seq[K]) = new RichSorting[K](s) - /** 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](a: Array[K])(implicit ord: Ordering[K]) { sort1(a, 0, a.length) } + 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) } @@ -46,15 +38,15 @@ object Sorting { /** Sort an array of K where K is Ordered, preserving the existing order * where the values are equal. */ - def stableSort[K](a: Array[K])(implicit m: ClassManifest[K], ord: Ordering[K]) { - stableSort(a, 0, a.length-1, new Array[K](a.length), ord.lt _) + def stableSort[K: ClassManifest: Ordering](a: Array[K]) { + stableSort(a, 0, a.length-1, new Array[K](a.length), Ordering[K].lt _) } /** Sorts an array of <code>K</code> given an ordering function * <code>f</code>. <code>f</code> should return <code>true</code> iff * its first parameter is strictly less than its second parameter. */ - def stableSort[K : ClassManifest](a: Array[K], f: (K,K) => Boolean) { + def stableSort[K: ClassManifest](a: Array[K], f: (K, K) => Boolean) { stableSort(a, 0, a.length-1, new Array[K](a.length), f) } @@ -66,15 +58,15 @@ object Sorting { * @param f the comparison function. * @return the sorted sequence of items. */ - def stableSort[K : ClassManifest](a: Seq[K], f: (K,K) => Boolean): Array[K] = { + def stableSort[K: ClassManifest](a: Seq[K], f: (K, K) => Boolean): Array[K] = { val ret = a.toArray stableSort(ret, f) ret } /** Sorts an arbitrary sequence of items that are viewable as ordered. */ - def stableSort[K](a: Seq[K])(implicit m: ClassManifest[K], ord: Ordering[K]): Array[K] = - stableSort(a, ord.lt _) + def stableSort[K: ClassManifest: 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. @@ -83,11 +75,13 @@ object Sorting { * @param f the comparison function. * @return the sorted sequence of items. */ - def stableSort[K, M](a: Seq[K], f: K => M)(implicit m: ClassManifest[K], ord: Ordering[M]): Array[K] = - stableSort(a)(m, ord on f) + def stableSort[K: ClassManifest, M: Ordering](a: Seq[K], f: K => M): Array[K] = + stableSort(a)(implicitly[ClassManifest[K]], Ordering[M] on f) - private def sort1[K](x: Array[K], off: Int, len: Int)(implicit ord: Ordering[K]) { + 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) @@ -530,15 +524,3 @@ object Sorting { } } } - -/** <p> - * A <code>RichSorting</code> object is generally created implicitly through - * the use of the <code>sort</code> function on an arbitrary sequence, where - * the items are ordered. - * </p> - */ -class RichSorting[K](s: Seq[K])(implicit m: ClassManifest[K], ord: Ordering[K]) { - /** Returns an array with a sorted copy of the RichSorting's sequence. - */ - def sort = Sorting.stableSort(s) -} diff --git a/test/files/run/comparable-comparator.scala b/test/files/run/comparable-comparator.scala new file mode 100644 index 0000000000..aafe10eb59 --- /dev/null +++ b/test/files/run/comparable-comparator.scala @@ -0,0 +1,28 @@ + +object Test { + import java.util.Comparator + + class C1(val s: String) extends Comparable[C1] { + def compareTo(other: C1) = s compareTo other.s + override def toString = s + } + class C2(val s: String) { + def compareTo(other: C2) = s compareTo other.s + override def toString = s + } + + implicit val cmp: Comparator[C2] = new Comparator[C2] { + def compare(p1: C2, p2: C2) = p2.s compareTo p1.s + } + + val strs = "zip foo bar baz aggle bing bong" split ' ' toList + val c1s = strs map (x => new C1(x)) + val c2s = strs map (x => new C2(x)) + + val sorted1 = c1s.sorted map (_.s) + val sorted2 = c2s.sorted map (_.s) + + def main(args: Array[String]): Unit = { + assert(sorted1 == sorted2.reverse) + } +} |