Skip to content

Instantly share code, notes, and snippets.

@davidallsopp
Last active August 29, 2015 13:57
Show Gist options
  • Save davidallsopp/9764705 to your computer and use it in GitHub Desktop.
Save davidallsopp/9764705 to your computer and use it in GitHub Desktop.
Lazily generate all subsequences of an Iterator or Iterable, up to the specified length, returning a new Iterator.
import scala.collection.mutable.ListBuffer
// See also http://stackoverflow.com/questions/22633598/creating-an-iterator-of-subsequences-from-an-iterator-of-items/
/** Lazily generate all subsequences of an Iterator or Iterable, up to the specified length, returning a new Iterator. */
class Subseqs[A](n: Int)(i: Iterator[A]) extends Iterator[List[A]] {
val buffer = new ListBuffer[A]()
//buffer ++= i.take(n) // NO - inconsistent behaviour of take() with iterators
// see http://stackoverflow.com/questions/7619642/consume-items-from-a-scala-iterator
(1 to n).foreach(_ => buffer += i.next())
var index = 1
def hasNext = buffer.length > 1
def next = {
def increment() = { val i = index; index += 1; i }
if (index > buffer.length) {
index = 1
buffer.remove(0)
if (i.hasNext) buffer += i.next()
}
buffer.slice(0, increment()).toList
}
}
/** Pimp my library*/
object Subseqs {
implicit class SubseqIterable[A](i: Iterable[A]) {
def subseqs(n: Int) = new Subseqs(n)(i.iterator)
}
implicit class SubseqIterator[A](i: Iterator[A]) {
def subseqs(n: Int) = new Subseqs(n)(i)
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment