Structures de données Scala ou Java pour un tri "non strict" personnalisé

Question

Je dispose d'un ensemble d'éléments dont l'égalité et la sémantique de tri sont différentes. Par exemple

class Item( 
  val uid: String, // equality
  val score: Int   // sorting
)

Ce dont j'ai besoin, c'est d'avoir des éléments dans une collection triés en permanence par score. En prime, une vérification rapide de l'appartenance par égalité (comme dans un hash/tree).

Des éléments égaux peuvent avoir des scores différents, je ne peux donc pas préfixer l'égalité par une égalité de score (c'est-à-dire utiliser une sorte d'arbre/carte de hachage).

Des idées sur des combinaisons de collections scala ou java std pour réaliser cela avec un minimum de codage :)

Answer 1

J'utiliserais probablement un SortedSet puisqu'ils sont déjà triés. Comme l'a souligné Woot4Moo, vous pouvez créer votre propre Comparable (bien que je suggère d'utiliser la fonction Scala commande ). Si vous passez cet ordre en argument au SortedSet, ce dernier triera tout pour vous - les SortedSets sont toujours triés.

NB : C'est l'argument implicite que vous voudrez, il pourrait donc ressembler à quelque chose comme ceci :

val ordering = Ordering[...]
val set = SortedSet(1, 2, 3, ... n)(ordering)

Notez le dernier paramètre donné comme ordre

Answer 2

Il est possible de construire son propre Set de l'article, enveloppant à la fois un SortedMap[Int, Set[Item]] (pour les commandes) et un HashSet[Item] (pour les performances d'accès) :

class MyOrderedSet(items: Set[Item], byPrice: collection.SortedMap[Int, Set[Item]]) extends Set[Item] {

  def contains(key: Item) = items contains key

  def iterator = byPrice map {_._2.iterator} reduceOption {_ ++ _} getOrElse Iterator.empty

  def +(elem: Item) =
    new MyOrderedSet(items + elem, byPrice + (elem.score -> (byPrice.getOrElse(elem.score, Set.empty) + elem)))

  def -(elem: Item) =
    new MyOrderedSet(items - elem, byPrice + (elem.score -> (byPrice.getOrElse(elem.score, Set.empty) - elem)))

  // override any other methods for your convenience
}

object MyOrderedSet {
  def empty = new MyOrderedSet(Set.empty, collection.SortedMap.empty)

  // add any other factory method
}

La modification de l'ensemble est douloureuse car vous avez synchronisé 2 collections, mais toutes les fonctionnalités que vous souhaitez sont présentes (du moins je l'espère).

Un exemple rapide :

scala> MyOrderedSet.empty + Item("a", 50) + Item("b", 20) + Item("c", 100)
res44: MyOrderedSet = Set(Item(b,20), Item(a,50), Item(c,100))

Il y a également un petit inconvénient, qui n'est en fait pas lié à la structure proposée : Il est possible de vérifier si un élément fait partie de l'ensemble, mais il n'est pas possible d'obtenir sa valeur :

scala> res44 contains Item("a", 100)
res45: Boolean = true

Rien dans l'API ne vous permet d'obtenir Item("a", 50) en conséquence. Si vous souhaitez le faire, je vous propose de Map[String, Item] au lieu de Set[Item] para items (et bien sûr, de modifier le code en conséquence).

EDIT : Pour les plus curieux, voici la version écrite rapide d'Item que j'utilise :

case class Item(id: String, score: Int) {
  override def equals(y: Any) =
    y != null && {
      PartialFunction.cond(y) {
        case Item(`id`, _) => true
      }
    }
}