LinearReadingImprovedQuestion.md

I have an API for reading multi-dimensional arrays, requiring to pass a vector of ranges to read sub-rectangles (or hypercubes) from the backing array. I want to read this array "linearly", all elements in some given order with arbitrary chunk sizes. Thus, the task is with an off and a len, to translate the elements covered by this range into the smallest possible set of hyper-cubes, i.e. the smallest number of read commands issued in the API.

For example, we can calculate index vectors for the set of dimensions giving a linear index:

def calcIndices(off: Int, shape: Vector[Int]): Vector[Int] = {
  val modsDivs = shape zip shape.scanRight(1)(_ * _).tail
  modsDivs.map { case (mod, div) =>
    (off / div) % mod
  }
}

Let's say the shape is this, representing an array with rank 4 and 120 elements in total:

val sz  = Vector(2, 3, 4, 5)
val num = sz.product  // 120

A utility to print these index vectors for a range of linear offsets:

def printIndices(off: Int, len: Int): Unit =
  (off until (off + len)).map(calcIndices(_, sz))
    .map(_.mkString("[", ", ", "]")).foreach(println)

We can generate all those vectors:

printIndices(0, num)

[0, 0, 0, 0]
[0, 0, 0, 1]
[0, 0, 0, 2]
[0, 0, 0, 3]
[0, 0, 0, 4]
[0, 0, 1, 0]
[0, 0, 1, 1]
[0, 0, 1, 2]
[0, 0, 1, 3]
[0, 0, 1, 4]
[0, 0, 2, 0]
[0, 0, 2, 1]
[0, 0, 2, 2]
[0, 0, 2, 3]
[0, 0, 2, 4]
[0, 0, 3, 0]
[0, 0, 3, 1]
[0, 0, 3, 2]
[0, 0, 3, 3]
[0, 0, 3, 4]
[0, 1, 0, 0]
...
[1, 2, 1, 4]
[1, 2, 2, 0]
[1, 2, 2, 1]
[1, 2, 2, 2]
[1, 2, 2, 3]
[1, 2, 2, 4]
[1, 2, 3, 0]
[1, 2, 3, 1]
[1, 2, 3, 2]
[1, 2, 3, 3]
[1, 2, 3, 4]

Let's look at an example chunk that should be read, the first six elements:

val off1 = 0
val len1 = 6
printIndices(off1, len1)

I will already partition the output by hand into hypercubes:

// first hypercube or read
[0, 0, 0, 0]
[0, 0, 0, 1]
[0, 0, 0, 2]
[0, 0, 0, 3]
[0, 0, 0, 4]

// second hypercube or read
[0, 0, 1, 0]

So the task is to define a method

def partition(shape: Vector[Int], off: Int, len: Int): List[Vector[Range]]

which outputs the correct list and uses the smallest possible list size. So for off1 and len1, we have the expected result:

val res1 = List(
  Vector(0 to 0, 0 to 0, 0 to 0, 0 to 4),
  Vector(0 to 0, 0 to 0, 1 to 1, 0 to 0)
)

assert(res1.map(_.map(_.size).product).sum == len1)

A second example, elements at indices 6 until 22, with manual partitioning giving three hypercubes or read commands:

val off2 = 6
val len2 = 16
printIndices(off2, len2)

// first hypercube or read
[0, 0, 1, 1]
[0, 0, 1, 2]
[0, 0, 1, 3]
[0, 0, 1, 4]

// second hypercube or read
[0, 0, 2, 0]
[0, 0, 2, 1]
[0, 0, 2, 2]
[0, 0, 2, 3]
[0, 0, 2, 4]
[0, 0, 3, 0]
[0, 0, 3, 1]
[0, 0, 3, 2]
[0, 0, 3, 3]
[0, 0, 3, 4]

// third hypercube or read
[0, 1, 0, 0]
[0, 1, 0, 1]

expected result:

val res2 = List(
  Vector(0 to 0, 0 to 0, 1 to 1, 1 to 4),
  Vector(0 to 0, 0 to 0, 2 to 3, 0 to 4),
  Vector(0 to 0, 1 to 1, 0 to 0, 0 to 1)
)

assert(res2.map(_.map(_.size).product).sum == len2)

Sciss/LinearReadingImprovedQuestion.md