"Deinterlacing" a list in Scala

Question

I have a list of bytes that represent raw samples read in from an audio interface. Depending on the use case and H/W, each sample can be anywhere from 1 to 4 bytes long, and the total number of channels in the "stream" can be more or less arbitrary. The amount of channels and bits per sample are both known at runtime.

I'll give an example of what I mean. There are four channels in the stream and each sample is two bytes.

List(A1, A2, B1, B2, C1, C2, D1, D2, A3, A4, B3, B4, C3, C4, D3, D4)

so A1 is the first byte of channel A's first sample, A2 is the second byte of the same sample and so on.

What I need to do is extract each channel's samples into their own lists, like this:

List(List(A1, A2, A3, A4), List(B1, B2, B3, B4), List(C1, C2, C3, C4), List(D1, D2, D3, D4))

How would I go about doing this in idiomatic Scala? I just started learning Scala a few hours ago, and the only non-imperative solution I've come up with is clearly nonoptimal:

def uninterleave(samples: Array[Byte], numChannels: Int, bytesPerSample: Int) = {
val dropAmount = numChannels * bytesPerSample
  def extractChannel(n: Int) = {
    def extrInner(in: Seq[Byte], acc: Seq[Byte]): Seq[Byte] = {
      if(in == List()) acc
      else extrInner(in.drop(dropAmount), in.take(bytesPerSample) ++ acc)
    }
    extrInner(samples.drop(n * bytesPerSample), Nil)
  }

  for(i <- 0 until numChannels) yield extractChannel(i)
}

Answer 1

I would do

samples.grouped(bytesPerSample).grouped(numChannels).toList
  .transpose.map(_.flatten)

I would not vouch for its performance though. I would rather avoid lists, unfortunately grouped produces them.

Maybe

samples.grouped(bytesPerSample).map(_.toArray)
  .grouped(numChannels).map(_.toArray)
  .toArray
  .transpose
  .map(flatten)

Still, lots of lists.

Answer 2

didierd's answer is just about perfect, but, alas, I think one can improve it a bit. He is concerned with all the list creation, and transpose is a rather heavy operation as well. If you can process all the data at the same time, it might well be good enough.

However, I'm going with Stream, and use a little trick to avoid transposing.

First of all, the grouping is the same, only I'm turning stuff into streams:

def getChannels[T](input: Iterator[T], elementsPerSample: Int, numOfChannels: Int) =
  input.toStream.grouped(elementsPerSample).toStream.grouped(numOfChannels).toStream

Next, I'll give you a function to extract one channel from that:

def streamN[T](s: Stream[Stream[Stream[T]]])(channel: Int) = s flatMap (_(channel))

With those, we can decode the streams like this:

// Sample input
val input = List('A1, 'A2, 'B1, 'B2, 'C1, 'C2, 'D1, 'D2, 'A3, 'A4, 'B3, 'B4, 'C3, 'C4, 'D3, 'D4)

// Save streams to val, to avoid recomputing the groups
val streams = getChannels(input.iterator, elementsPerSample = 2, numOfChannels = 4)

// Decode each one
def demuxer = streamN(streams) _
val aa = demuxer(0)
val bb = demuxer(1)
val cc = demuxer(2)
val dd = demuxer(3)

This will return separate streams for each channel without having the whole stream at hand. This might be useful if you need to process the input in real time. Here's some input source to test how far into the input it reads to get at a particular element:

def source(elementsPerSample: Int, numOfChannels: Int) = Iterator.from(0).map { x =>
  "" + ('A' + x / elementsPerSample % numOfChannels).toChar +
  (x % elementsPerSample 
   + (x / (numOfChannels * elementsPerSample)) * elementsPerSample 
   + 1)
}.map { x => println("Saw "+x); x }

You can then try stuff like this:

val streams = getChannels(source(2, 4), elementsPerSample = 2, numOfChannels = 4)
def demuxer = streamN(streams) _
val cc = demuxer(2)
println(cc take 20 toList)
val bb = demuxer(1)
println(bb take 30 toList)