Comment utiliser scala.util.Sorting.quickSort() avec des types arbitraires?

Question

J'ai besoin de trier un tableau de paires par second élément. Comment passer le comparateur de mes paires à la fonction quickSort? J'utilise l'approche suivante laide maintenant:

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)) 

Pourquoi QuickSort conçu pour avoir une vue ordonnée au lieu d'argument de comparaison habituelle?

Les solutions de Scala 2,7 sont préférées.

Answer 1

Ok, je ne sais pas exactement ce que vous n'êtes pas satisfait de ce que vous faites actuellement, mais peut-être que tout ce que vous êtes Vous cherchez est-ce?

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

Si, d'autre part, le problème est que le tuple estOrdered et que vous voulez un ordre différent , eh bien, c'est pourquoi il a changé sur Scala 2.8.

* EDIT *

Aïe! Désolé, je réalise seulement maintenant que vous avez dit que vous préférez les solutions Scala 2.7. J'ai édité cette réponse bientôt pour mettre la solution pour 2.7 ci-dessus. Ce qui suit est une solution 2.8. Scala 2.8 attend un Ordering, pas un Ordered, qui est lié au contexte, pas une vue liée. Vous écririez votre code 2.8 comme ceci:

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 
} 

Ou peut-être juste:

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

Et l'utiliser comme:

scala.util.Sorting.quickSort(data) 

D'autre part, la façon habituelle faire le tri dans Scala 2.8 est juste d'appeler l'une des méthodes de tri sur celui-ci, tels que:

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

Answer 2

Demandez à votre type étendre Ordered, comme ceci:

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

Et puis passer à trier, comme ceci:

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

Impression du tableau vous donnera:

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

Answer 3

J'ai tendance à préférer les arguments non implicites à moins d'être utilisé dans plus de quelques endroits.

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 
    } 
}) 

Edit: Après avoir appris les limites de vue dans une autre question, je pense que cette approche pourrait être mieux:

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]) 

De cette façon, OrderTupleBySecond pourrait être utilisé pour tout type Tuple2 où le type de le 2ème membre du tuple a une vue dans la portée qui le convertirait en un comparable.