¿Cómo doblar un iterador Scala y obtener una secuencia perezosamente evaluada como resultado?

Tengo un iterador de cadenas, donde cada cadena puede ser "H"(encabezado) o "D"(detalle). Quiero dividir este iterador en bloques, donde cada bloque comienza con un encabezado y puede tener de 0 a muchos detalles.

Sé cómo resolver este problema cargando todo en la memoria. Por ejemplo, el siguiente código:

Seq("H","D","D","D","H","D","H","H","D","D","H","D").toIterator
  .foldLeft(List[List[String]]())((acc, x) => x match {
    case "H" => List(x) :: acc
    case "D" => (x :: acc.head) :: acc.tail })
  .map(_.reverse)
  .reverse

devuelve 5 bloques, List(List(H, D, D, D), List(H, D), List(H), List(H, D, D), List(H, D))que es lo que quiero.

Sin embargo, en lugar de List[List[String]]en el resultado, quiero una Iterator[List[String]]u otra estructura que me permita evaluar el resultado de forma perezosa y no cargar toda la entrada en la memoria si se consume todo el iterador , quiero cargar en la memoria solo el bloque que se consume a la vez (por ejemplo: cuando llamo iterator.next).

¿Cómo puedo modificar el código anterior para lograr el resultado que quiero?

EDITAR: Necesito esto en Scala 2.11 específicamente, ya que el entorno que uso se adhiere a él. Sin embargo, me alegro de aceptar también respuestas para otras versiones.

Aquí está la implementación más simple que pude encontrar (es genérica y perezosa):

/** takes 'it' and groups consecutive elements 
 *  until next item that satisfy 'startGroup' predicate occures. 
 *  It returns Iterator[List[T]] and is lazy 
 *  (keeps in memory only last group, not whole 'it'). 
*/
def groupUsing[T](it:Iterator[T])(startGroup:T => Boolean):Iterator[List[T]] = {
  val sc = it.scanLeft(List.empty[T]) {
    (a,b) => if (startGroup(b)) b::Nil else b::a
  }

  (sc ++ Iterator(Nil)).sliding(2,1).collect { 
    case Seq(a,b) if a.length >= b.length => a.reverse
  }
}

úsalo así:

val exampleIt = Seq("H1","D1","D2","D3","H2","D4","H3","H4","D5","D6","H5","D7").toIterator
groupUsing(exampleIt)(_.startsWith("H"))
// H1 D1 D2 D3 / H2 D4 / H3 / H4 D5 D6 / H5 D7

Aquí está la especificación:

X | GIVEN            | EXPECTED     |
O |                  |              | empty iterator
O | H                | H            | single header
O | D                | D            | single item (not header)
O | HD               | HD           |
O | HH               | H,H          | only headers
O | HHD              | H,HD         |
O | HDDDHD           | HDDD,HD      |
O | DDH              | DD,H         | heading D's have no Header as you can see.
O | HDDDHDHDD        | HDDD,HD,HDD  |

scalafiddle con pruebas y comentarios adicionales: https://scalafiddle.io/sf/q8xbQ9N/11

(si la respuesta es útil, vote por favor, por favor. Pasé demasiado tiempo :))

SEGUNDA APLICACIÓN:

Tiene una versión propuesta que no utiliza sliding . Aquí está, pero tiene sus propios problemas enumerados a continuación.

def groupUsing2[T >: Null](it:Iterator[T])(startGroup:T => Boolean):Iterator[List[T]] = {
  type TT = (List[T], List[T])
  val empty:TT = (Nil, Nil)
  //We need this ugly `++ Iterator(null)` to close last group.
  val sc = (it ++ Iterator(null)).scanLeft(empty) {
    (a,b) => if (b == null || startGroup(b)) (b::Nil, a._1) else (b::a._1, Nil)
  }

  sc.collect { 
    case (_, a) if a.nonEmpty => a.reverse
  }
}

Rasgos:

• (-) Funciona solo para T>:Nulltipos. Solo necesitamos agregar un elemento que cierre la última colección al final (nulo es perfecto pero limita nuestro tipo).
• (~) debería crear la misma cantidad de trsh que la versión anterior. Simplemente creamos tuplas en el primer paso en lugar del segundo.
• (+) no verifica la longitud de la Lista (y para ser honesto, esta es una gran ganancia).
• (+) En esencia, es la respuesta de Ivan Kurchenko, pero sin boxeo adicional.

Aquí está scalafiddle: https://scalafiddle.io/sf/q8xbQ9N/11

Si está utilizando Scala 2.13.x, puede crear uno nuevo Iteratordesplegando sobre el original Iterator.

import scala.collection.mutable.ListBuffer

val data = Seq("H","D","D","D","H","D","H","H","D","D","H","D").iterator

val rslt = Iterator.unfold(data.buffered){itr =>
  Option.when(itr.hasNext) {
    val lb = ListBuffer(itr.next())
    while (itr.hasNext && itr.head == "D")
      lb += itr.next()
    (lb.toList, itr)
  }
}

pruebas:

rslt.next()   //res0: List[String] = List(H, D, D, D)
rslt.next()   //res1: List[String] = List(H, D)
rslt.next()   //res2: List[String] = List(H)
rslt.next()   //res3: List[String] = List(H, D, D)
rslt.next()   //res4: List[String] = List(H, D)
rslt.hasNext  //res5: Boolean = false

Creo que la scanLeftoperación podría ayudar en este caso, si desea utilizar la versión Scala 2.11.

Me gustaría proponer la próxima solución, pero me temo que parece más complicada que la original:

def main(args: Array[String]): Unit = {
    sealed trait SequenceItem
    case class SequenceSymbol(value: String) extends SequenceItem
    case object Termination extends SequenceItem

    /**
      * _1 - HD sequence in progress
      * _2 - HD sequences which is ready
      */
    type ScanResult = (List[String], List[String])
    val init: ScanResult = Nil -> Nil

    val originalIterator: Iterator[SequenceItem] = Seq("H","D","D","D", "H","D", "H", "H","D","D", "H","D")
      .toIterator.map(SequenceSymbol)

    val iteratorWithTermination: Iterator[SequenceItem] = originalIterator ++ Seq(Termination).toIterator
    val result: Iterator[List[String]] = iteratorWithTermination
      .scanLeft(init) {
        case ((progress, _), SequenceSymbol("H")) =>  List("H") -> progress
        case ((progress, _), SequenceSymbol("D")) => ("D" :: progress) -> Nil
        case ((progress, _), Termination) => Nil -> progress
      }
      .collect {
        case (_, ready) if ready.nonEmpty => ready
      }
      .map(_.reverse)

    println(result.mkString(", "))
  }

Tipos añadidos, por ejemplo, legibilidad. ¡Espero que esto ayude!