Copy

[CTMacUser]

Description

This change adds methods that introduces new elements to a collection via overwriting existing elements (instead of inserting more space).

Detailed Design

The are methods that copy across subsequences of the same collection, both in the forward and backward directions. The main versions use a separate object as the source. There are combinations for Sequence vs. Collection source, and copying over the prefix vs. suffix. There is another main version that copies suffix to suffix.

extension MutableCollection {
    /// Copies the prefix of the given sequence on top of the prefix of this collection.
    public mutating func copy<S>(from source: S) -> (copyEnd: Index, sourceTail: S.Iterator) where S : Sequence, Self.Element == S.Element

    /// Copies the prefix of the given collection on top of the prefix of this collection.
    public mutating func copy<C>(collection: C) -> (copyEnd: Index, sourceTailStart: C.Index) where C : Collection, Self.Element == C.Element

    /// Copies, in forward traversal, the prefix of a subsequence on top of the prefix of another, using the given bounds to demarcate the subsequences.
    public mutating func copy<R, S>(forwardsFrom source: R, to destination: S) -> (sourceRead: Range<Index>, destinationWritten: Range<Index>) where R : RangeExpression, S : RangeExpression, Self.Index == R.Bound, R.Bound == S.Bound
}

extension MutableCollection where Self : BidirectionalCollection {
    /// Copies the prefix of the given sequence on top of the suffix of this collection.
    public mutating func copy<S>(asSuffix source: S) -> (copyStart: Index, sourceTail: S.Iterator) where S : Sequence, Self.Element == S.Element

    /// Copies the prefix of the given collection on top of the suffix of this collection.
    public mutating func copy<C>(collectionAsSuffix source: C) -> (copyStart: Index, sourceTailStart: C.Index) where C : Collection, Self.Element == C.Element

    /// Copies the suffix of the given collection on top of the suffix of this collection.
    public mutating func copy<C>(backwards source: C) -> (writtenStart: Index, readStart: C.Index) where C : BidirectionalCollection, Self.Element == C.Element

    /// Copies, in reverse traversal, the suffix of a subsequence on top of the suffix of another, using the given bounds to demarcate the subsequences.
    public mutating func copy<R, S>(backwardsFrom source: R, to destination: S) -> (sourceRead: Range<Index>, destinationWritten: Range<Index>) where R : RangeExpression, S : RangeExpression, Self.Index == R.Bound, R.Bound == S.Bound
}

Documentation Plan

The methods have documentation comments. There is also a guide file.

Test Plan

There is a XC Test file for these methods.

Source Impact

The change adds API.

Checklist

• [x] I've added at least one test that validates that my change is working, if appropriate
• [x] I've followed the code style of the rest of the project
• [x] I've read the Contribution Guidelines
• [x] I've updated the documentation if necessary

[CTMacUser]

1. Naming I wouldn’t have guessed this would be the behavior of a function named copy. This may be because I’ve programmed a lot more Objective-C than C++ recently. I suspect many Swift programmers are also in that same situation.

   Perhaps the naming should include some clarifying words, like “prefix”, or “over”/“overwrite”?

   overwritePrefix(with:)?

Due to the nature of C++'s output iterator concept, its copying includes both memory overwriting and new-space insertion! Swift puts those as two separate collection concepts (MutableCollection vs. RangeReplaceableCollection). RRC already covers copying that inserts new memory spaces, but they don't use "copy" in their names (replaceSubrange, append, and insert), so "copy" was free to use. Maybe "overwrite" or similar would be better.

2. Sequence and Collection I was a bit confused as to why there is a copy(from:) taking a Sequence and a differently named copy(collection:) (omitting the “from” terminology) for Collection.

   If I’m working with two Arrays, it’s not clear which function I should use and why.

   var destination = ["A", "B", "C", "D", "E", "F"]
   let source = ["a", "b", "c"]
   destination.copy(from: source)
   destination.copy(collection: source)
   

   Are these both necessary? And if so, how can it be made more clear which function to use?

The sequence vs. collection methods differ in their return type. Since a Sequence may be single-pass, I can only return an Iterator to the unused elements. For a Collection, I return an Index to the first unused element (or endIndex if all were used). The interfaces for the second member of the return value are obviously incompatible, so I can't/shouldn't reuse a (full) name for both.

Hmm, would a better option than a Sequence be an inout IteratorProtocol parameter instead? But that would put the extra step of converting onto the user. (A similar thing happened when I proposed an initializer to CollectionOfOne that reads the first element from a sequence/iterator. Maybe the same solution will work here.)

3. Return Value Should these functions be marked as @discardableResult? Seems like it’s valid to call these functions without making use of the return value.

I wonder about that, too. Since it's (currently) non-discardable, the user has to think about what if one of the collections/sequences wasn't completely used. If the user knows that the source and destination are the same length, or otherwise doesn't care, they can use the "_ =" syntax.

4. Performance There are a few shortcuts that could probably made depending on the input sizes. As one example, if the source is larger than the destination, why bother going through the items one-by-one when a prefix of self.count can be taken from the source?

Are you implying the existence of a procedure that can do an O(1) bulk overwriting-copy? Otherwise, this wouldn't save any time. And if there is a (refined) protocol that can guarantee this (and also conform to RandomAccessCollection so self.count would be O(1)), that wouldn't help with any other sequence.

Minor:

I’ve noticed that the rest of this repository uses a single between sentences, but these changes include comments and documentation using two. This should be consistent.

I'll check that out.

[CTMacUser]

I renamed the methods from "copy" to "overwrite" and did a lot of the other changes suggested by @mdznr. Check it out.

[adincebic]

@swift-ci Please test