Сортировка коллекции по индексам внутренних элементов коллекции в Scala

Question

Позвольте нам иметь коллекцию коллекций, как показано ниже:

type Row = IndexedSeq[Any]
type RowTable = IndexedSeq[Row]

val table: RowTable = IndexedSeq(
    IndexedSeq(2, "b", ... /* some elements of type Any*/),
    IndexedSeq(1, "a", ...),
    IndexedSeq(2, "c", ...))

Каждый Row в RowTable "имеет ту же схему", что означает, как в примере, если первая строка в таблице содержит Int, String, ..., то вторая строка таблицы содержит элементы одного типа в том же порядке, т. Е. Int, String, ....

. Я бы хотел отсортировать Row s в RowTable по заданные индексы элементов Row и направление сортировки (сортировка по возрастанию или убыванию) для этого элемента.

Например, вышеупомянутая коллекция будет отсортирована таким образом для индекса 0 по возрастанию и индекса 1 по убыванию и остальные элементы не важны при сортировке:

1, "a", ...
2, "c", ...
2, "b", ...

Поскольку Row равно IndexedSeq[Any], мы не знаем тип каждого элемента для сравнения; однако мы знаем, что он может быть приведен к Comparable[Any] и, таким образом, имеет метод compareTo() для сравнения его с элементом с таким же индексом в другой строке.

Индексы, как упоминалось выше, что будет определять порядок сортировки неизвестно, прежде чем мы начнем сортировку. Как я могу кодировать это в Scala?

Answer 1

Прежде всего, это плохой дизайн для сравнения пары Any.

По умолчанию scala не предоставляет никакого способа получить Ordering[Any]. Следовательно, если вы хотите сравнить пару Any, вы должны реализовать Ordering[Any] самостоятельно:

object AnyOrdering extends Ordering[Any] {
  override def compare(xRaw: Any, yRaw: Any): Int = {
    (xRaw, yRaw) match {
      case (x: Int, y: Int) => Ordering.Int.compare(x, y)
      case (_: Int, _) => 1
      case (_, _: Int) => -1
      ...
      case (x: String, y: String) => Ordering.String.compare(x, y)
      case (_: String, _) => 1
      case (_, _: String) => -1
      ...
      case (_, _) => 0
    }
  }
}

В вашем примере вы хотите сравнить два IndexedSeq[T] рекурсивно. Scala не предоставляет никаких рекурсивных Ordering, и вам нужно реализовать это тоже:

def recOrdering[T](implicit ordering: Ordering[T]): Ordering[IndexedSeq[T]] = new Ordering[IndexedSeq[T]] {
  override def compare(x: IndexedSeq[T], y: IndexedSeq[T]): Int = compareRec(x, y)

  @tailrec
  private def compareRec(x: IndexedSeq[T], y: IndexedSeq[T]): Int = {
    (x.headOption, y.headOption) match {
      case (Some(xHead), Some(yHead)) =>
        val compare = ordering.compare(xHead, yHead)
        if (compare == 0) {
          compareRec(x.tail, y.tail)
        } else {
          compare
        }
      case (Some(_), None) => 1
      case (None, Some(_)) => -1
    }
  }
}

После этого вы можете наконец отсортировать свою коллекцию:

table.sorted(recOrdering(AnyOrdering))

Answer 2

(извините за код unidiomati c (возможно, не компилируется); возможно, я могу помочь с ним по запросу)

Мы можем использовать приведенный ниже код для сортировки таблицы

table.sortWith {
   case (tupleL, tupleR) => isLessThan(tupleL, tupleR)
}

где isLessThan определяется следующим образом (unidiomati c до Scala, ik):

def isLessThan(tupleL: Row, tupleR: Row): Boolean = {
      var i = 0
      while (i < sortInfos.length) {
        val sortInfo = sortInfos(i)
        val result = tupleL(sortInfo.fieldIndex)
            .asInstanceOf[Comparable[Any]].compareTo(
          tupleR(sortInfo.fieldIndex)
            .asInstanceOf[Comparable[Any]])

        if (result != 0) {
          if (sortInfo.isDescending) {
            if (result > 0)
              return true
            else
              return false
          } else {
            if (result < 0)
              return true
            else
              return false
          }
        }

        i += 1
      }
      true
    }

, где sortInfos равно IndexedSeq[SortInfo] и

case class SortInfo(val fieldIndex: Int, val isDescending: Boolean)

Answer 3

Вот пример работы с Ordering[IndexedSeq[Any]]:

val table: IndexedSeq[IndexedSeq[Any]] = IndexedSeq(
  IndexedSeq(2, "b", "a"),
  IndexedSeq(2, "b"),
  IndexedSeq("c", 2), 
  IndexedSeq(1, "c"),
  IndexedSeq("c", "c"), 
  //IndexedSeq((), "c"), //it will blow in runtime
  IndexedSeq(2, "a"),
)


implicit val isaOrdering:Ordering[IndexedSeq[Any]] = { (a, b) => 
 a.zip(b).filter {case (a, b)=> a != b}.collectFirst {
   case (a:Int, b:Int) => a compare b
   case (a:String, b:String) => a compare b
   case (a:String, b:Int) => 1 //prefere ints over strings
   case (a:Int, b:String) => -1 //prefere ints over strings
   case _ => throw new RuntimeException(s"cannot compare $a to $b")
 }.getOrElse(a.length compare b.length) //shorter will be first
}

println(table.sorted) //used implicitly
println(table.sorted(isaOrdering)) 
//Vector(Vector(1, c), Vector(2, a), Vector(2, b), Vector(2, b, a), Vector(c, 2), Vector(c, c))

https://scalafiddle.io/sf/yvLEnYL/4

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

implicit val isaOrdering:Ordering[IndexedSeq[Any]] = { (a, b) => 
 a.zip(b).filter {case (a, b)=> a != b}.collectFirst {
   case (a:Int, b:Int) => a compare b
   case (a:String, b:String) => a compare b
   //add your known types here
   // ...
   //below is rule that cares about unknown cases. 
   //We don't know types at all, at best what we can do is compare equality.
   //If they are equal then return 0... if not we throw
   //this could be also very slow (don't tested)  
   case (a, b) => 
   //not nice but it is stable at least
    val ac = a.getClass.getName
    val bc = b.getClass.getName
    ac.compare(bc) match {
      case 0 => if (ac == bc) 0 else throw new RuntimeException(s"cannot compare $a to $b")
      case x => x
    } 
 }.getOrElse(a.length compare b.length) //shorter will be first
}

https://scalafiddle.io/sf/yvLEnYL/5

Эта реализация завершится с ошибкой во время выполнения, когда мы не смогли их сравнить.