Scala - изготовление на заказ (комплекс?) Отличие функция в списке множеств случае класса

Question

у меня есть простой класс случая:

case class OneTwo (one: String, two: String) 

У меня есть простой список наборов этого случай класса:

val list = List(Set(OneTwo("a", "b")), Set(OneTwo("a", "b"), OneTwo("c", "d")), Set(OneTwo("e", "f"))) 

Теперь у меня есть необычное «отличное» требование в этом списке: если один набор содержится в другом, они равны, а оставшийся в живых должен быть меньшим. Например. в приведенном выше list процедура «ditsinct» должна возвращать List(Set(OneTwo("a", "b")), Set(OneTwo("e", "f"))), так как Set(OneTwo("a", "b")) содержится в пределах Set(OneTwo("a", "b"), OneTwo("c", "f")) и Set(OneTwo("a", "b")) меньше.

Теперь следующие работы в РЕПЛ и компиляций, (см "но" позже):

def ord: Ordering[Set[OneTwo]] = new Ordering[Set[OneTwo]]() { 
    def compare(set1: Set[OneTwo], set2: Set[OneTwo]): Int = { 
    if (set1.equals(set2) || set1.subsetOf(set2) || set2.subsetOf(set1)) 0 else if (set1.size != set2.size) set1.size compare set2.size else 
     set1.hashCode compare set2.hashCode 
    } 
} 

val listSorted = list.sorted(ord).reverse 

val listDistinct = collection.immutable.SortedSet(listSorted: _*)(ord).toList 

listDistinct 

Дает:

List[scala.collection.immutable.Set[OneTwo]] = List(Set(OneTwo(e,f)), Set(OneTwo(a,b))) 

НО: Это упорядочение нарушает транзитивность requiremnt из при заказе, поэтому во время выполнения это вызовет исключение java.lang.IllegalArgumentException: Comparison method violates its general contract!.

Очень просто понять, почему:

scala> ord.compare(Set(OneTwo("a","b")), Set(OneTwo("e", "f"))) 
res56: Int = -1 

scala> ord.compare(Set(OneTwo("e","f")), Set(OneTwo("a", "b"), OneTwo("c", "d"))) 
res57: Int = -1 

scala> ord.compare(Set(OneTwo("a","b")), Set(OneTwo("a", "b"), OneTwo("c", "d"))) 
res58: Int = 0 

что означает < B, B < C еще A = C. Проблема.

Нижняя строка: есть ли способ, которым я мог бы сделать то, что я хочу сделать, в свой список наборов классов OneTwo? (Мне все равно, что касается окончательного порядка этого списка, это также может привести к набору, и это не должно быть похоже на мою стратегию)

Answer 1

Это прямое решение, м, что есть более элегантный способ сделать это:

list.sortBy(_.size).foldLeft(Set.empty[Set[OneTwo]])((res, set) => { 
    if (res.exists(_.subsetOf(set))) res else res + set 
}).toList 

Сортировка по размеру важно, потому что ваши меньшие наборы будут появляться на фронте таким образом. После этого просто сверните список, добавив только элемент, если он удовлетворит ваше ограничение. Обратите внимание, что мы накапливаем результаты в Set, а не в List, потому что это упрощает и повышает эффективность проверки ограничений.