Scala или Java-структуры данных для нестандартной сортировки

Question

У меня есть набор предметов с разным равенством и семантикой сортировки.Например,

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

Мне нужно, чтобы элементы в какой-либо коллекции сортировались все время по количеству баллов.Бонус заключается в быстром поиске / проверке членства на равенство (как в хэше / дереве).

Равные элементы могут иметь различную оценку, поэтому я не могу поставить префикс равенства перед равенством оценки (т.е. использовать вид деревахэш-карта).

Есть какие-нибудь идеи по сочетанию коллекций scala или java std для достижения этого с минимальным кодированием?:)

Answer 1

Я бы, вероятно, использовал SortedSet , так как они уже отсортированы.Как указал Woot4Moo, вы можете создать свой собственный Comparable (хотя я бы посоветовал использовать order Scala ).Если вы передадите этот порядок в качестве аргумента в SortedSet, то Set будет все у вас разбирать - SortedSets всегда сортируются.

NB: Это неявный аргумент, который вам понадобится, поэтому он может выглядеть примерно так:1007 *

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

Обратите внимание на последний параметр, указанный в качестве порядка

Answer 2

Возможность состоит в том, чтобы создать свой собственный Set элемент, заключая в себе SortedMap[Int, Set[Item]] (для заказа) и HashSet[Item] (для производительности доступа:

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
}

Модификация набораболезненно, потому что вы синхронизировали 2 коллекции, но все нужные вам функции есть (по крайней мере, я на это надеюсь)

Быстрый пример:

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

Есть также небольшой недостаток, которыйна самом деле не связано с предложенной структурой: вы можете проверить, есть ли элемент в наборе, но вы не можете получить его значение:

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

Ничто в API не позволяет вам получить Item("a", 50) в результате.Если вы хотите сделать это, я предлагаю Map[String, Item] вместо Set[Item] для items (и, конечно, соответственно изменить код).

РЕДАКТИРОВАТЬ: Дляболее любопытно, вот быстро написанная версия предмета, который я использую:

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