Scala oder Java Datenstrukturen für benutzerdefinierte "nicht-strikte" Sortierung

Question

Ich habe eine Reihe von Elementen mit unterschiedlichen Gleichheit und Sortierung Semantik. Z.B.

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

Was ich brauche ist, dass die Elemente in einer Sammlung ständig nach Punkten sortiert sind. Bonus ist eine schnelle Suche/Mitgliedschaft Prüfung von Gleichheit (wie in Hash/Baum).

Gleiche Elemente können unterschiedliche Werte haben, daher kann ich keine Gleichheit mit einer Score-Gleichheit voranstellen (d. H. Eine Art Tree/Hash-Map verwenden).

Irgendwelche Ideen zu Kombinationen von Scala oder Java STD-Sammlungen, um dies mit minimaler Codierung zu erreichen? :)

Answer 1

Ich würde wahrscheinlich eine verwenden, da sie bereits sortiert sind. Wie Woot4Moo darauf hingewiesen hat, kannst du dein eigenes Vergleichbares erstellen (obwohl ich Scala ordering empfehlen würde). Wenn Sie diese Sortierung als Argument an SortedSet übergeben, sortiert das Set alles für Sie - SortedSets werden immer sortiert.

NB: Es ist das implizite Argument werden Sie wollen, so könnte es in etwa so aussehen:

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

Hinweis der letzte Parameter wie die Bestellung

gegeben

Answer 2

Eine Möglichkeit ist, Ihre eigene Set von Artikel zu bauen , Verpackung sowohl ein SortedMap[Int, Set[Item]] (zur Bestellung) und eine HashSet[Item] (für Zugriffsleistung:

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 
} 

Modi fizierung des Satzes ist schmerzhaft, weil Sie zwei Sammlungen synchronisiert, aber alle Funktionen, die Sie wollen, gibt es (zumindest hoffe ich)

Ein kurzes Beispiel:

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

Es gibt auch einen kleinen Nachteil, die tatsächlich ist nicht auf die vorgeschlagene Struktur verbunden: Sie können überprüfen, ob ein Element in dem Satz ist, aber man kann nicht seinen Wert erhalten:

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

Nichts in der API Sie Item("a", 50) als Ergebnis erhalten können. Wenn Sie dies möchten, schlage ich vor, Map[String, Item] anstelle von Set[Item] für items (und natürlich, um den Code entsprechend zu ändern).

EDIT: Für die Neugierigen, hier ist die Quicky schriftliche Fassung von Artikel Ich verwende:

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