1

While testing my generic 2D matrix transposition function, I ran into some strange behaviour for ranges.

extension Collection where Self.Iterator.Element: RandomAccessCollection { 
	func transposed() -> [[Self.Iterator.Element.Iterator.Element]] {
		guard let firstRow = self.first else { return [] }
		return firstRow.indices.map { index in
			self.map{ $0[index] }
		}
	}
}

The algorithm works for normal arrays:

[[1, 2], [3, 4]].transposed().forEach{ print($0) }

But gave quite surprising results for ranges (I would have expected it to behave the same):

[1...2, 3...4].transposed().forEach{ print($0) }
// Output:
// [1, 1]
// [2, 2]

...??? :thinking:

Narrowing it down, it seems that the indices of ranges are not 0 indexed, and that the index you use from one range, when applied to another range, gives the same result (even if it's not found within that second range). Ex:

(1...3).indices.map{ index in (0...0)[index] } // => [1, 2, 3] 🤔

Could somebody explain why this behaviour occurs, what motivated the design, and how I could fix my algorithm?

2

The Swift 3 documentation for CountableRange stated that

INTEGER INDEX AMBIGUITY
Because each element of a CountableRange instance is its own index, for the range (-99..<100) the element at index 0 is 0. This is an unexpected result for those accustomed to zero-based collection indices, who might expect the result to be -99.

In Swift 4, CountableRange is just a type alias

public typealias CountableRange<Bound: Strideable> = Range<Bound>
  where Bound.Stride : SignedInteger

and it seems that the above doc comment got lost with this change. But one can still see from the source code at Range.swift#L189 that the indices of a Range (of Strideable elements) is the range itself

public var indices: Indices {
  return self
}

public subscript(position: Index) -> Element {
  // FIXME: swift-3-indexing-model: tests for the range check.
  _debugPrecondition(self.contains(position), "Index out of range")
  return position
}

Your method would also fail if used with an ArraySlice:

[ [1, 2, 3, 4].dropFirst(), [2, 3, 4]].transposed().forEach{ print($0) }
// Fatal error: Index out of bounds

Generally (I think) it is not safe to use the indices of one collection with any other collection (with the exception of slices, which share their indices with the originating collection).

The problem does not occur with arrays, because array indices are always zero based integers.

You can fix your algorithm by working with offsets relative to the initial position instead. The nested types can also be simplified a bit, since Element == Iterator.Element for sequences:

extension Collection where Element: RandomAccessCollection {
    func transposed() -> [[Element.Element]] {
        guard let firstRow = self.first else { return [] }
        return (0..<firstRow.count).map { offset in
            self.map { $0[$0.index($0.startIndex, offsetBy: offset)] }
        }
    }
}

(Of course this assumes – as your original code – that all “rows” have the same number of elements.)

6 Likes