Efficient way of flat mapping a range of a multidimensional random access collection

Question

I've recently answered a question about reading elements from an array of arrays. A way it could be interpreted is that the OP wanted to read a range that could span over multiple subarrays of the 2D array like so :

let a = [["5", "3", ".", ".", "7", "."],
         ["6", ".", ".", "1", "9", "5"]]

a.lazy.flatMap{$0}[1..<7] ["3", ".", ".", "7", ".", "6"]

This way of reading a range would need to at least flatMap all the previous arrays to the lower bound of the range. Which would be wasteful.

A more natural way would be to only read the needed elements from the original array:

func get<T>(_ range: Range<Int>, from array2d: [[T]]) -> [T]? {
    var result: [T] = []
    result.reserveCapacity(range.upperBound - range.lowerBound)

    var count1 = 0

    //Get the index of the first element
    guard var low = array2d
            .firstIndex(where: {
                 count1 += $0.count
                 return range.lowerBound < count1 }),
          count1 != 0
    else { return nil }

    let before = count1 - array2d[low].count
    var count2 = before

    //Get the index of the last element in the range
    guard let high = array2d[low..<array2d.endIndex]
            .firstIndex(where: {
                 count2 += $0.count
                 return range.upperBound <= count2
            }),
          count2 != 0
    else { return nil }

    //Append the elements in the array with the low index
    for i in (range.lowerBound - before)..<min(range.upperBound - before, array2d[low].count) { 
        result.append(array2d[low][i]) 
    }

    //If the range spans over multiple arrays
    if count1 < count2 {
        low += 1

        //Append the elements in the arrays with an index between low and high
        while low < high {
            result.append(contentsOf: array2d[low])
            low += 1
        }

        //Append the elements in the array with the high index
        for i in 0..<(range.upperBound - count2 + array2d[high].count) {
            result.append(array2d[high][i])
        }
    }

    return result
}

Which could be used like so :

let a = [["0", "1", "2", "3", "4", "5"], ["6", "7"], [], ["8","9","10","11", "12"], ["13","14", "15"]]

get(5..<11, from: a) //Optional(["5", "6", "7", "8", "9", "10"])
get(7..<9, from: a) //Optional(["7", "8"])

To me, the above code feels.. on the border of sanity/maintainability...

What I'd like to do is to make it more generic, maybe as an extension to RandomAccessCollection, and making the flattening process recursive for arrays/collections of arbitrary dimensions. I'm stuck here and not sure if this is the appropriate network to ask such a question.

Feedback on all aspects of the code is welcome, such as (but not limited to):

• Efficiency,
• Readability,
• Naming.

Answer 1

I gather that your intent was to write a method that iterates through an array of arrays (but avoiding functional patterns), flattening the results in the process such that given...

let a = [["0", "1", "2", "3", "4", "5"], ["6", "7"], [], ["8","9","10","11", "12"], ["13","14", "15"]]

... that result for 5..<10 would be ["5", "6", "7", "8", "9"]

Assuming that’s what you were trying to do, I think you can simplify it:

extension Array {
    func flattened<T>(range: Range<Int>) -> [T]? where Element == Array<T> {
        var result: [T] = []

        var offset = range.startIndex
        var length = range.upperBound - range.lowerBound

        result.reserveCapacity(length)

        for subarray in self {
            let subarrayCount = subarray.count
            if offset < subarrayCount {
                if length > subarrayCount - offset {
                    result += subarray[offset...]
                    length -= subarrayCount - offset
                } else {
                    return result + subarray[offset..<offset + length]
                }
            }
            offset = Swift.max(0, offset - subarrayCount)
        }

        return nil
    }
}

In terms of observations on your code:

• I wouldn’t advise get method name. It’s not very meaningful name and only conjures up confusion with getters. I’d go with something that captured the “flattening” nature of the routine.

• As a general rule, we should avoid closures with side-effects in functional programming patterns. Even though you’ve written an “iterative” rendition of the OP’s code, you’re using a functional method, firstIndex, and you are updating variables outside the closure. It’s technically allowed but is contrary to the spirit of functional programming patterns and is dependent upon the implementation details of firstIndex.

Answer 2

Functional approach:

Observation: The code presented is a bit complex to read, and could be more reusable. My approach would be to separate the two tasks. First flatten the 3d array with a reusable 3d array flattening method and then get the range from the 1d array. The performance of this approach vs more integrated methods is out of the scope at this moment. But something one should of course take in to account if performance is needed.

extension Collection {
   /**
    * Multidimensional-flat-map...because flatMap only works on "2d arrays". This is for "3d array's"
    * - Note: A 3d array is an array structure that can have nested arrays within nested arrays infinite addendum
    * - Note: Alternate names for this method as suggest by @defrenz and @timvermeulen on slack swift-lang #random: `recursiveFlatten` or `recursiveJoined`
    * ## Examples:
    * let arr:[Any] = [[[1],[2,3]],[[4,5],[6]]] 👈 3d array (3 depths deep)
    * let x2:[Int] = arr.recursiveFlatmap()
    * Swift.print(x2)//[1,2,3,4,5,6]
    */
   public func recursiveFlatmap<T>() -> [T] {
      var results = [T]()
      for element in self {
           if let sublist = element as? [Self.Iterator.Element] { // Array
               results += sublist.recursiveFlatmap()
           } else if let element = element as? T { // Item
               results.append(element)
           }
      }
      return results
   }
}

Answer 3

Extensibility

The following is meant as an addendum to Rob's answer. It is built upon their approach and extends it to work for arrays with arbitrary depth.

extension Array {
    func flattened(range: Range<Int>) -> [Any]? {
        return helper(range).result?.count == range.upperBound - range.lowerBound ?
                helper(range).result :
                nil
    }

    private func helper(_ range: Range<Int>) -> (result: [Any]?, offset: Int) {
        var result: [Any] = []

        var offset = range.startIndex
        let length = range.upperBound - range.lowerBound

        result.reserveCapacity(length)

        for i in self.indices {
            let element = self[i]

            if let sub_a: [Any] = element as? [Any] {
                let tempo = sub_a.helper(offset..<offset + length - result.count)
                if let res = tempo.result {
                    result += res
                    offset = tempo.offset
                } else {
                    return (result: nil, offset: offset)
                }
            } else {
                if offset == 0 {
                    result.append(element)
                }
                offset = Swift.max(0, offset - 1)
            }

            if result.count == length {
                return (result: result, offset: offset)
            }
        }

        return (result: result, offset: offset)
    }
}

It has been tested with all of these arrays :

let a: [Any] = [[["0", "1", "2",   "3",  "4",    "5"], ["6",  "7"], []],
                [["8", "9", "10", "11", "12"], ["13",  "14", "15"]]]

let b: [Any] = [[["0", "1"], ["2", "3", "4"]],
                [[]],
                [["5"], ["6", "7", "8", "9"]],
                [["10", "11", "12"], ["13", "14", "15"]]]

let c: [Any] = [["0", "1", "2", "3", "4", "5", ["6", "7", ["8", "9", "10", "11", "12"]]], [], ["13", "14", "15"]]

The output of all three :

print(a.flattened(range: 3..<15))
print(b.flattened(range: 3..<15))
print(c.flattened(range: 3..<15))

is

Optional(["3", "4", "5", "6", "7", "8", "9", "10", "11", "12", "13", "14"])