Help me fix the compile error: Type 'Self.SubSequence' has no member 'init'

extension Array where Element: Numeric {
//extension BidirectionalCollection where Self: MutableCollection, Element: Numeric {    // swap this in to see the compile error below
    mutating func moveZerosToTheFront() -> Index {
        if isEmpty {
            return endIndex
        }
        // skip non-zero values at the end (don't need to move them)
        // there is no suffix(while:) (the Algorithm package does), so use this kludge:
        let noneZeroSuffixCount = reversed().prefix(while: { $0 != 0 }).count
        let insertIndexInitialValue = index(endIndex, offsetBy: -noneZeroSuffixCount)
        var insertIndex = insertIndexInitialValue

        let r = indices.dropLast(noneZeroSuffixCount).reversed()
        for i in r where self[i] != 0 {
            formIndex(before: &insertIndex)
            self[insertIndex] = self[i]
        }
        if insertIndex != insertIndexInitialValue {
            self[..<insertIndex] = .init(repeating: 0, count: distance(from: startIndex, to: insertIndex))  // Compile error: Type 'Self.SubSequence' has no member 'init'
        }
        return insertIndex
    }
}

The code works for Array, but I want it to work on BidirectionCollection. Changing to that cause a compile error. How to solve?

This code is my attempt to make a more "Swift" version of this: Moving zeros to the beginning of an array - #6 by michelf, just for exercise. I don't think we should write this kind of code and should just rely on pre-made algorithm.

Something to keep in mind when changing the implementation requirement is that it also changes associated types.

As a hint, remember that Self.SubSequence is ArraySlice when Self == Array, but it is only some BidirectionalCollection if Self == BidirectionalCollection.

PS

I think it's fine to use your own implementation if the provided one proves inadequate. Standard Library is just there for your convenience (and perhaps interoperability with other libraries).

In this case, though, I doubt you would gain much from custom implementation (aside from some practice & experience).

1 Like

init(repeating:count:) is a requirement on RangeReplaceableCollection, so you could simply make a requirement that Self.SubSequence is a RangeReplaceableCollection, like so.

extension BidirectionalCollection where Self: MutableCollection, SubSequence: RangeReplaceableCollection, Element: Numeric {
    mutating func moveZerosToTheFront() -> Index {
        if isEmpty {
            return endIndex
        }
        // skip non-zero values at the end (don't need to move them)
        // there is no suffix(while:) (the Algorithm package does), so use this kludge:
        let noneZeroSuffixCount = reversed().prefix(while: { $0 != 0 }).count
        let insertIndexInitialValue = index(endIndex, offsetBy: -noneZeroSuffixCount)
        var insertIndex = insertIndexInitialValue
        
        let r = indices.dropLast(noneZeroSuffixCount).reversed()
        for i in r where self[i] != 0 {
            formIndex(before: &insertIndex)
            self[insertIndex] = self[i]
        }
        if insertIndex != insertIndexInitialValue {
            self[..<insertIndex] = .init(repeating: 0, count: distance(from: startIndex, to: insertIndex))
        }
        return insertIndex
    }
}

However, this code will allocate an unnecessary instance of SubSequence. For better performance (and to remove the RangeReplaceableCollection requirement), I’d suggest assigning zero in a loop.

extension BidirectionalCollection where Self: MutableCollection, Element: Numeric {
    mutating func moveZerosToTheFront() -> Index {
        if isEmpty {
            return endIndex
        }
        // skip non-zero values at the end (don't need to move them)
        // there is no suffix(while:) (the Algorithm package does), so use this kludge:
        let noneZeroSuffixCount = reversed().prefix(while: { $0 != 0 }).count
        let insertIndexInitialValue = index(endIndex, offsetBy: -noneZeroSuffixCount)
        var insertIndex = insertIndexInitialValue
        
        let r = indices.dropLast(noneZeroSuffixCount).reversed()
        for i in r where self[i] != 0 {
            formIndex(before: &insertIndex)
            self[insertIndex] = self[i]
        }
        if insertIndex != insertIndexInitialValue {
            var index = startIndex
            while index != insertIndex {
                self[index] = 0
                formIndex(after: &index)
            }
        }
        return insertIndex
    }
}

Also, I don’t think it’s wrong for programmers to create their own algorithms — creating your own algorithms can make your code perform better. For example, the algorithm above will run in O(n) time, while an algorithm like stablePartition(by:) in Swift Algorithms will run in O(n log n) time. However, making your own algorithms does shift the burden of correctness and performance onto you rather than the maintainer of a library.

1 Like

Where is this unnecessary instance of SubSequence? I din't think you mean this:

.init(repeating: 0, count: distance(from: startIndex, to: insertIndex))

?

How to find this out if you don't already know? The compiler error doesn't give any hint :frowning:

The assign zero loop can be simplified:

for i in self[..<insertIndex].indices {
    self[i] = 0
}

:pray:

Finish version
    mutating func moveZerosToTheFront() -> Index {
        if isEmpty {
            return endIndex
        }
        // skip non-zero values at the end (don't need to move them)
        // there is no suffix(while:) (the Algorithm package does), so use this kludge:
        let noneZeroSuffixCount = reversed().prefix(while: { $0 != 0 }).count
        let insertIndexInitialValue = index(endIndex, offsetBy: -noneZeroSuffixCount)
        var insertIndex = insertIndexInitialValue

        let r = indices.dropLast(noneZeroSuffixCount).reversed()
        for i in r where self[i] != 0 {
            formIndex(before: &insertIndex)
            self[insertIndex] = self[i]
            self[i] = 0
        }
        return insertIndex
    }
}

That is a performance trap.

In generic code, one must assume that self.indices may hold onto self, thus rendering the backing storage no longer uniquely referenced. Then, mutating self within the loop can trigger a copy-on-write, duplicating the memory.

This is specifically called out in the documentation for Collection.indices:

A collection’s indices property can hold a strong reference to the collection itself, causing the collection to be nonuniquely referenced. If you mutate the collection while iterating over its indices, a strong reference can result in an unexpected copy of the collection. To avoid the unexpected copy, use the index(after:) method starting with startIndex to produce indices instead.

3 Likes

I do mean that code. That code will create a new instance of SubSequence, fill that SubSequence with instances of 0, copy the contents of that SubSequence into the specified range, then destroy the SubSequence. Using a loop will avoid creating a SubSequence, instead filling the specified range with instances of 0 directly. (As @Nevin has pointed out, though, using indices might create an unnecessary copy of the collection).

This requirement is listed in the documentation for RangeReplaceableCollection. If you’re not sure which protocol a method is on, then the best way to find out is to use the documentation for sequence and collection protocols and use the protocol descriptions to guide you towards the correct protocol. Find-on-page can also help here (Control-F on Windows and Command-F on Mac or on iPad with a keyboard. For iOS or iPadOS without a keyboard go to the “Search the Page” section on this support document).

1 Like

That make sense not knowing what's inside that SubSequence. But can that SubSequence when created this way holds just the repeating value and count and not a fully expanded element by element data sequence? If it's such, then it's constant small size.

Where is the source? is it somewhere here: GitHub - apple/swift: The Swift Programming Language?

okay, it's a whole array, I think: swift/Array.swift at main · apple/swift · GitHub

So you are right: it's not a good idea to create SubSequence

1 Like

Yep! The standard library is available within apple/swift at stdlib/public/core. RangeReplaceableCollection is defined in RangeReplaceableCollection.swift.

1 Like

How about the for loop above that?

        let r = indices.dropLast(noneZeroSuffixCount).reversed()
        for i in r where self[i] != 0 {
            formIndex(before: &insertIndex)
            self[insertIndex] = self[i]
        }

It gets the range from indices from itself, so it's uniquely referenced, and the mutate is with insertIndex, there is no risk of extra copying, right?

What if I change to this:

            for i in indices[..<insertIndex] {
                self[i] = 0
            }

this still increase ref, have the same problem, I think?

Terms of Service

Privacy Policy

Cookie Policy