3
\$\begingroup\$

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.
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ FYI, the above is a simple refactoring of the code snippet in the question, but does not attempt to tackle the question of what changes are needed to handle arbitrary depth in the subarrays. \$\endgroup\$ – Rob Apr 3 at 8:40
0
\$\begingroup\$

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"])

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.