Scala - scalanie wielu iteratorów

Question

Mam wiele iteratorów, które zwracają elementy w posortowany sposób zgodnie z pewnym kryterium sortowania. Teraz chciałbym scalić (multipleksować) iteratory w jeden, połączony iterator. Wiem, jak to zrobić w stylu Java, np. tree-map, ale zastanawiałem się, czy istnieje bardziej funkcjonalne podejście? Chcę zachować lenistwo iteratorów tak bardzo, jak to tylko możliwe.

Answer 1

Można po prostu zrobić:

val it = iter1 ++ iter2 

Tworzy kolejną iterację i nie ocenia elementy, ale opakowuje dwóch istniejących iteratory. Jest w pełni leniwy, więc nie powinieneś używać iter1 lub iter2, gdy to zrobisz.

W ogóle, jeśli masz więcej iteratory do scalania, można użyć składane:

val iterators: Seq[Iterator[T]] = ??? 
val it = iterators.foldLeft(Iterator[T]())(_ ++ _) 

Jeśli masz jakieś zamawiasz na elementach, które chcesz, aby utrzymać w wynikowym iteracyjnej ale chcesz lazyness, możesz konwertować je na strumienie:

def merge[T: Ordering](iter1: Iterator[T], iter2: Iterator[T]): Iterator[T] = { 
    val s1 = iter1.toStream 
    val s2 = iter2.toStream 

    def mergeStreams(s1: Stream[T], s2: Stream[T]): Stream[T] = { 
    if (s1.isEmpty) s2 
    else if (s2.isEmpty) s1 
    else if (s1.head < s2.head) s1.head #:: mergeStreams(s1.tail, s2) 
    else s2.head #:: mergeStreams(s1, s2.tail) 
    } 

    mergeStreams(s1, s2).iterator 
} 

Niekoniecznie szybciej, ale powinieneś to udoskonalić.

Ewentualną alternatywą jest użycie buffered iterators, aby uzyskać ten sam efekt.

Answer 2

można spróbować:

(iterA ++ iterB).toStream.sorted.toIterator 

Na przykład:

 
val i1 = (1 to 100 by 3).toIterator 
val i2 = (2 to 100 by 3).toIterator 
val i3 = (3 to 100 by 3).toIterator 

val merged = (i1 ++ i2 ++ i3).toStream.sorted.toIterator 

merged.next // results in: 1 
merged.next // results in: 2 
merged.next // results in: 3 

Answer 3

@ axel22 Jak wspomniano, można to zrobić z BufferedIterators. Oto jeden strumień wolne rozwiązanie:

def combine[T](rawIterators: List[Iterator[T]])(implicit cmp: Ordering[T]): Iterator[T] = { 
    new Iterator[T] { 
    private val iterators: List[BufferedIterator[T]] = rawIterators.map(_.buffered) 

    def hasNext: Boolean = iterators.exists(_.hasNext) 

    def next(): T = if (hasNext) { 
     iterators.filter(_.hasNext).map(x => (x.head, x)).minBy(_._1)(cmp)._2.next() 
    } else { 
     throw new UnsupportedOperationException("Cannot call next on an exhausted iterator!") 
    } 
}