Supporting collection slice by slices of a given size parameter

Evolution Pitches
,
21

Sorry, something about this part bugs me. What about:

extension ChunkedCollection: BidirectionalCollection where Base: RandomAccessCollection {
    func index(before i: Index) -> Index {
        let stragglerCount = base.count % size
        let lastChunkCount = straggerCount == 0 ? size : stragglerCount
        let offset = (i == base.endIndex) ? lastChunkCount : size
        return base.index(i, offsetBy: -offset)
    }

    var count: Int {
       let (wholeChunkCount, stragglerCount) = base.count.quotientAndRemainder(dividingBy: size)
       return wholeChunkCount + stragglerCount.signum()
    }
}

But looking at this, maybe we can go full random-access:

extension ChunkedCollection: RandomAccessCollection where Base: RandomAccessCollection {
    func index(before i: Index) -> Index {
        let stragglerCount = base.count % size
        let lastChunkCount = straggerCount == 0 ? size : stragglerCount
        let offset = (i == base.endIndex) ? lastChunkCount : size
        return base.index(i, offsetBy: -offset)
    }

    func distance(from start: Index, to end: Index) -> Int {
        let (chunkDelta, stragglerDelta) = base.distance(from: start, to: end).quotientAndRemainder(dividingBy: size)
        return chunkDelta + stragglerDelta.signum()
    }

    func index(_ i: Index, offsetBy distance: Int) -> Index {
        let stragglerCount = base.count % size
        let lastExactIndex = base.index(base.endIndex, offsetBy: -stragglerCount)
        if stragglerCount != 0, distance == 1 + distance(from: i, to: lastExactIndex) {
            return base.endIndex
        } else {
            return base.index(i, offsetBy: distance * size)
        }
    }
}

(Warning: I'm not sure I got the mod-for-negative-numbers correct for distance(from: to:).)

(Warning: I wrote both clips in the forum panel; neither has been compiled or tested.)

22

Hey Daryle :)
Those are really interesting materials and for sure they can help we move forward with this proposal.
I'll definitely take a look on the links and on the sectioned sequences implementation :))

23

Those are interesting implementations :))
About going full RandomAccessCollection, that's an interesting point. Can you elaborate more on the pros and cons of that?

About your index(before:) suggestion, one maybe is that we don't have to calculate base.count % size on every iteration since it's only be used when i == base.endIndex. That's why I put the if i == base.endIndex && base.count%size != 0 statement so when the i is not the same as base.endIndex it doesn't even execute the other part of the statement. I know it seems like doing the same operation twice but maybe another way to do it will be

func index(before i: Index) -> Index {
        var offset = size
        if i == base.endIndex  {
            let reminder = base.count%size 
            if remainder != 0 {
                offset = remainder
            }
        }
        return base.index(i, offsetBy: -offset)
    }

That way we don't execute the same operation twice and also don't calculate it on every iteration and I believe it could be a improvement to the proposal :))

About the count suggestion, since base.count is O(1) I think that the two are just different styled implementations with the same cost.

24

Yes, the collection should definitely be random access if its underlying collection is random access. But note, you have to explicitly conform to both because it's a conditional conformance i.e.:

extension ChunkedCollection: BidirectionalCollection, RandomAccessCollection 
where Base: RandomAccessCollection {
  // etc
}

This seems surprising at first because normally you get base protocol conformance "for free" when you conform to a protocol. But with conditional conformance you have to spell it out. See the relevant part of SE-0143 for details.

25

Pro vs. cons doesn't really apply here. Can the results be done in constant time instead of linear time; i.e. with calculations instead of resorting to single steps then counting those? If the answer is yes, then we can switch to RandomAccessCollection.

1 Like
26

Here is the proposal PR to the Swift Evolution.
Any feedback is welcome :))