Wie falte ich einen Scala-Iterator und erhalte als Ergebnis eine träge ausgewertete Sequenz?

Ich habe einen Iterator von Zeichenfolgen, wobei jede Zeichenfolge entweder "H"(Header) oder "D"(Detail) sein kann. Ich möchte diesen Iterator in Blöcke aufteilen, wobei jeder Block mit einem Header beginnt und 0 bis viele Details haben kann.

Ich weiß, wie man dieses Problem löst, indem man alles in den Speicher lädt. Zum Beispiel der folgende Code:

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

gibt 5 Blöcke zurück - List(List(H, D, D, D), List(H, D), List(H), List(H, D, D), List(H, D))- was ich will.

Anstelle des List[List[String]]Ergebnisses möchte ich jedoch eine Iterator[List[String]]oder eine andere Struktur, mit der ich das Ergebnis träge auswerten und nicht die gesamte Eingabe in den Speicher laden kann, wenn der gesamte Iterator verbraucht ist. Ich möchte nur den Block in den Speicher laden, der verbraucht wird zu einem Zeitpunkt (zB: wenn ich anrufe iterator.next).

Wie kann ich den obigen Code ändern, um das gewünschte Ergebnis zu erzielen?

EDIT: Ich brauche dies speziell in Scala 2.11, da die Umgebung, die ich benutze, daran festhält. Ich bin froh, auch Antworten für andere Versionen zu akzeptieren.

Hier ist die einfachste Implementierung, die ich finden konnte (generisch und faul):

/** 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
  }
}

benutze es so:

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

Hier ist die Spezifikation:

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 mit Tests und zusätzlichen Kommentaren: https://scalafiddle.io/sf/q8xbQ9N/11

(Wenn die Antwort hilfreich ist, stimmen Sie bitte ab. Ich habe etwas zu viel Zeit damit verbracht :))

ZWEITE UMSETZUNG:

Sie haben eine Version vorgeschlagen , die nicht verwendet wird sliding . Hier ist es, aber es hat seine eigenen Probleme unten aufgeführt.

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
  }
}

Züge:

• (-) Es funktioniert nur für T>:NullTypen. Wir müssen nur ein Element hinzufügen, das die letzte Sammlung am Ende schließt (null ist perfekt, aber es schränkt unseren Typ ein).
• (~) Es sollte die gleiche Menge an trsh wie in der vorherigen Version erstellen. Wir erstellen nur Tupel im ersten Schritt anstelle des zweiten.
• (+) Die Länge der Liste wird nicht überprüft (und dies ist ein großer Gewinn, um ehrlich zu sein).
• (+) Im Kern ist es Ivan Kurchenkos Antwort, aber ohne zusätzliches Boxen.

Hier ist die Skalafiddle: https://scalafiddle.io/sf/q8xbQ9N/11

Wenn Sie Scala 2.13.x verwenden, können Sie eine neue erstellen, Iteratorindem Sie sie über das Original entfalten 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)
  }
}

testen:

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

Ich denke, die scanLeftBedienung könnte in diesem Fall hilfreich sein, wenn Sie die Scala 2.11-Version verwenden möchten.

Ich würde gerne die nächste Lösung finden, aber ich fürchte, sie sieht komplizierter aus als die ursprüngliche:

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(", "))
  }

Typen hinzugefügt, zum Beispiel Lesbarkeit. Ich hoffe das hilft!