Переписывание последовательности путем разбиения и свертывания

Каков самый элегантный и простой алгоритм для отображения последовательной коллекции таким образом, что смежные элементы, удовлетворяющие одному предикату, сворачиваются в другой элемент, а те, которые не удовлетворяют предикату, отображаются 1:1 в другой элемент?

вот пример:

sealed trait A  // say the input elements are of this type
sealed trait B  // say the output elements are of this type
case class C(i: Int) extends A // these are the input elements satisfying the predicate
case class D(s: C*) extends B // they should be collapsed into this
case class E(i: Int) extends A with B // these are input elems that are left as such

учитывая эту входную последовательность:

val input  = Seq(C(1), C(2), C(3), E(4), E(5), C(6), E(7), C(8), C(9))

ожидаемый результат:

val output = Seq(D(C(1), C(2), C(3)), E(4), E(5), D(C(6)), E(7), D(C(8), C(9)))
//                ---------------       -    -      -       -      --------
// the dashes indicate how the sequence is regrouped (collapsed)

вот один из способов сделать это, но я не уверен, что это особенно элегантно:

def split(xs: Seq[A]): Seq[B] = split1(Seq.empty[B], true, xs)
@annotation.tailrec def split1(done: Seq[B], test: Boolean, rem: Seq[A]) : Seq[B] = {
    val (pre, post) = rem.span { case _: C => test; case _ => !test }
    val add = if(test) {
        D(pre.collect({ case x: C => x }): _*) :: Nil
    } else {
        pre.collect({ case x: E => x })
    }
    val done2 = done ++ add
    if(post.isEmpty) done2 else split1(done2, !test, post)
}

проверять:

val output2 = split(input)
output2 == output  // ok

collections scala grouping
person 0__    schedule 03.03.2011    source источник

Ответы (2)


arrow_upward
1
arrow_downward

Я бы добавил к D удобный метод, чтобы вы могли «добавить» еще один C и получить новый D обратно. Тогда было бы легко использовать простой foldLeft или около того для создания нового Seq.

person Landei    schedule 03.03.2011

arrow_upward
0
arrow_downward

@Landei да, действительно, это хороший подход!

val output2 = input.foldLeft(Seq.empty[B]) {
  case (res, c: C) => res.lastOption match {
    case Some(D(x @ _*)) => res.dropRight(1) :+ D((x :+ c): _*)
    case _ => res :+ D(c)
  }
  case (res, e: E) => res :+ e
}

output2 == output // ok

(Конечно, IndexedSeq лучше для lastOption, dropRight и добавления.)

person 0__    schedule 04.03.2011
comment
Вы можете использовать init вместо dropRight(1) - person Peter Schmitz; 08.03.2011