Как использовать scala.util.Sorting.quickSort () с произвольными типами?

Question

Мне нужно отсортировать массив пар по второму элементу.Как передать компаратор для моих пар в функцию быстрой сортировки?Сейчас я использую следующий уродливый подход:

type AccResult = (AccUnit, Long) // pair
class Comparator(a:AccResult) extends Ordered[AccResult] {
        def compare(that:AccResult) = lessCompare(a, that)
        def lessCompare(a:AccResult, that:AccResult) = if (a._2 == that._2) 0 else if (a._2 < that._2) -1 else 1
}
scala.util.Sorting.quickSort(data)(d => new Comparator(d))

Почему быстрая сортировка имеет упорядоченное представление вместо обычного аргумента компаратора?

Решения Scala 2.7 предпочтительнее.

Answer 1

Хорошо, я не совсем уверен, чем вы недовольны из-за того, что делаете в настоящее время, но, возможно, все, что вы ищете, это?

implicit def toComparator(a: AccResult) = new Comparator(a)
scala.util.Sorting.quickSort(data)

Если, с другой стороны, проблема в том, что кортеж равен Ordered, и вы хотите другой порядок, вот почему он изменился в Scala 2.8. 1009 *

* РЕДАКТИРОВАТЬ *

Ой! Извините, я только сейчас понимаю, что вы сказали, что предпочитаете решения Scala 2.7. Я отредактировал этот ответ в ближайшее время, чтобы поставить решение для 2.7 выше. Далее следует решение 2.8.

Scala 2.8 ожидает Ordering, а не Ordered, который связан с контекстом, а не с представлением. Вы бы написали свой код в 2.8 так:

type AccResult = (AccUnit, Long) // pair 
implicit object AccResultOrdering extends Ordering[AccResult] { 
        def compare(x: AccResult, y: AccResult) = if (x._2 == y._2) 0 else if (x._2 < y._2) -1 else 1 
}

Или, может быть, просто:

type AccResult = (AccUnit, Long) // pair 
implicit val AccResultOrdering = Ordering by ((_: AccResult)._2)

И используйте это как:

scala.util.Sorting.quickSort(data)

С другой стороны, обычный способ выполнить сортировку в Scala 2.8 - просто вызвать один из методов сортировки, например:

data.sortBy((_: AccResult)._2)

Answer 2

Я предпочитаю неявные аргументы, если они не используются более чем в нескольких местах.

type Pair = (String,Int)
val items : Array[Pair] = Array(("one",1),("three",3),("two",2))
quickSort(items)(new Ordering[Pair] {
  def compare(x: Pair, y: Pair) = {
    x._2 compare y._2
  }
})

Редактировать: После изучения границ просмотра в другом вопросе, я думаю, что этот подход может быть лучше:

val items : Array[(String,Int)] = Array(("one",1),("three",3),("two",2))

class OrderTupleBySecond[X,Y <% Comparable[Y]] extends Ordering[(X,Y)] {
  def compare(x: (X,Y), y: (X,Y)) = {
    x._2 compareTo y._2
  }
}

util.Sorting.quickSort(items)(new OrderTupleBySecond[String,Int])

Таким образом, OrderTupleBySecond может использоваться для любого типа Tuple2, где тип 2-го члена кортежа имеет вид в области видимости, который преобразует его в Comparable.

Answer 3

Ваш тип расширения Ordered, вот так:

case class Thing(number : Integer, name: String) extends Ordered[Thing] {
  def compare(that: Thing) = name.compare(that.name)
}

А затем передать его для сортировки, вот так:

val array = Array(Thing(4, "Doll"), Thing(2, "Monkey"), Thing(7, "Green"))
scala.util.Sorting.quickSort(array)

Печать массива даст вам:

array.foreach{ e => print(e) }
>> Thing(4,Doll) Thing(7,Green) Thing(2,Monkey)