Myself and Zach Wolfe started putting a pitch together a few months ago for adding a new method to RangeReplaceableCollection for removing elements at particular indices. Both of us ran short of time to make this public and push it forwards, but in an effort to not let it die I've decided to publish what we have and give someone else the opportunity to see it to the finish. We both believe it would be a great addition to the standard library and at least deserves to be discussed out in the open.
Draft proposal: Remove Elements At Indices · GitHub
The latest version of the implementation:
extension Collection where Element: Comparable {
@inlinable
internal var _isSorted: Bool {
return _isSorted(by: <)
}
@inlinable
internal func _isSorted(by areInIncreasingOrder: (Element, Element) throws -> Bool) -> Bool {
do {
var iterator = makeIterator()
guard var prevElement = iterator.next() else { return true }
while let element = iterator.next() {
if try areInIncreasingOrder(element, prevElement) { return false }
prevElement = element
}
} catch {
return false
}
return true
}
}
extension RangeReplaceableCollection {
@inlinable
internal mutating func _removeAll<C>(atSorted indicesToRemove: C) where
C: BidirectionalCollection,
C.Element == Index
{
var iterator = indicesToRemove.reversed().makeIterator()
guard let lastIndex = iterator.next() else { return }
var range = lastIndex..<endIndex
while let index = iterator.next() {
precondition(index != range.lowerBound, "Duplicate indices")
precondition(index < range.lowerBound, "Unsorted indices")
let nextIndex = self.index(after: index)
if nextIndex == range.lowerBound {
range = index..<range.upperBound
} else {
removeSubrange(range)
range = index..<nextIndex
}
}
removeSubrange(range)
}
@_transparent
public mutating func removeAll<S>(at indicesToRemove: S, sorted: Bool = false) where
S: Sequence,
S.Element == Index
{
if sorted {
_removeAll(atSorted: Array(indicesToRemove))
} else {
_removeAll(atSorted: indicesToRemove.sorted())
}
}
@_transparent
public mutating func removeAll<C>(at indicesToRemove: C, sorted: Bool = false) where
C: BidirectionalCollection,
C.Element == Index
{
if sorted || indicesToRemove._isSorted {
_removeAll(atSorted: indicesToRemove)
} else {
_removeAll(atSorted: indicesToRemove.sorted())
}
}
}
extension RangeReplaceableCollection where Self: MutableCollection {
@inlinable
mutating func _removeAll<S>(atSorted indicesToRemove: S) where
S: Sequence,
S.Element == Index
{
var indicesToRemove = indicesToRemove.makeIterator()
// Shift the elements we want to keep to the left.
guard var destIndex = indicesToRemove.next() else { return }
precondition(indices.contains(destIndex), "Index out of range")
var srcIndex = index(after: destIndex)
var previousRemovalIndex = destIndex
func shiftLeft(untilIndex index: Index) {
precondition(index != previousRemovalIndex, "Duplicate indices")
precondition(previousRemovalIndex < index, "Unsorted indices")
while srcIndex < index {
swapAt(destIndex, srcIndex)
formIndex(after: &destIndex)
formIndex(after: &srcIndex)
}
formIndex(after: &srcIndex)
}
while let removeIndex = indicesToRemove.next() {
precondition(indices.contains(removeIndex), "Index out of range")
shiftLeft(untilIndex: removeIndex)
}
shiftLeft(untilIndex: endIndex)
// Remove the extra elements from the end of the collection.
removeSubrange(destIndex..<endIndex)
}
@_transparent
public mutating func removeAll<C>(at indicesToRemove: C, sorted: Bool = false) where
C: Collection,
C.Element == Index
{
if sorted || indicesToRemove._isSorted {
_removeAll(atSorted: indicesToRemove)
} else {
_removeAll(atSorted: indicesToRemove.sorted())
}
}
@_transparent
public mutating func removeAll<S>(at indicesToRemove: S, sorted: Bool = false) where
S: Sequence,
S.Element == Index
{
if sorted {
_removeAll(atSorted: indicesToRemove)
} else {
_removeAll(atSorted: indicesToRemove.sorted())
}
}
}
It's also worth noting that it might also be useful to expose the isSorted methods that are used within our solution, but since thats not the reason for this pitch it isn't mentioned anywhere else in the draft proposal and should probably have it's own thread.
