Add method to copy elements

Add method to element-mutable collections that takes a sequence of the same element type to read its elements and assign them on top of the collection's current elements. The copying stops upon reaching the end of the shorter sequence. The method returns two items. The first is one index past the last destination element written over. The second is an iterator for the elements of the source sequence that were not used for copying.
apple · CTMacUser · Nov 27, 2020 · Dec 17, 2020 · Dec 17, 2020 · Dec 18, 2020
commit e8f7bf376aed38141b3643ad1c708b181d44bb83
diff --git a/CHANGELOG.md b/CHANGELOG.md
@@ -12,7 +12,14 @@ package updates, you can specify your package dependency using
 
 ## [Unreleased]
 
-*No changes yet.*
+### Additions
+
+- The `copy(from:)` method has been added, applying to types conforming to
+  `MutableCollection`.  It takes a sequence with the same element type as its
+  only parameter, whose elements will be copied on top of the existing
+  elements.  The return values are the past-the-end index in the receiver where
+  the copying ended and an iterator for the source sequence after the elements
+  that were copied.
 
 ---
 

diff --git a/Guides/Copy.md b/Guides/Copy.md
@@ -0,0 +1,58 @@
+# Copy
+
+[[Source](../Sources/Algorithms/Copy.swift) |
+ [Tests](../Tests/SwiftAlgorithmsTests/CopyTests.swift)]
+
+Copy a sequence onto an element-mutable collection.
+
+```swift
+var destination = [1, 2, 3, 4, 5]
+let source = [6, 7, 8, 9, 10]
+print(destination)  // "[1, 2, 3, 4, 5]
+
+let (_, sourceSuffix) = destination.copy(from: source)
+print(destination)  // "[6, 7, 8, 9, 10]"
+print(Array(IteratorSequence(sourceSuffix)))  // "[]"
+```
+
+`copy(from:)` takes a source sequence and overlays its first *k* elements'
+values over the first `k` elements of the receiver, where `k` is the smaller of
+the two sequences' lengths.
+
+## Detailed Design
+
+A new method is added to element-mutable collections:
+
+```swift
+extension MutableCollection {
+  mutating func copy<S: Sequence>(from source: S)
+   -> (copyEnd: Index, sourceTail: S.Iterator) where S.Element == Element
+}
+```
+
+The methods return two values.  The first member is the index of the receiver
+defining the non-anchored endpoint of the elements that were actually written
+over.  The second member is for reading the suffix of the source that wasn't
+actually used.
+
+### Complexity
+
+Calling these methods is O(_k_), where _k_ is the length of the shorter
+sequence between the receiver and `source`.
+
+### Naming
+
+This method’s name matches the term of art used in other languages and
+libraries.
+
+### Comparison with other languages
+
+**C++:** Has a [`copy`][C++Copy] function in the `algorithm` library that takes
+a bounding pair of input iterators for the source and a single output iterator
+for the destination, returning one-past the last output iterator written over.
+The `copy_if` function does not have an analogue, since it can be simulated by
+submitting the result from `filter(_:)` as the source.
+
+<!-- Link references for other languages -->
+
+[C++Copy]: https://en.cppreference.com/w/cpp/algorithm/copy
diff --git a/README.md b/README.md
@@ -15,6 +15,7 @@ Read more about the package, and the intent behind it, in the [announcement on s
 
 - [`rotate(toStartAt:)`, `rotate(subrange:toStartAt:)`](https://github.com/apple/swift-algorithms/blob/main/Guides/Rotate.md): In-place rotation of elements.
 - [`stablePartition(by:)`, `stablePartition(subrange:by:)`](https://github.com/apple/swift-algorithms/blob/main/Guides/Partition.md): A partition that preserves the relative order of the resulting prefix and suffix.
+- [`copy(from:)`](./Guides/Copy.md): Copying from a sequence via overwriting elements.
 
 #### Combining collections
 

diff --git a/Sources/Algorithms/Copy.swift b/Sources/Algorithms/Copy.swift
@@ -0,0 +1,48 @@
+//===----------------------------------------------------------------------===//
+//
+// This source file is part of the Swift Algorithms open source project
+//
+// Copyright (c) 2020 Apple Inc. and the Swift project authors
+// Licensed under Apache License v2.0 with Runtime Library Exception
+//
+// See https://swift.org/LICENSE.txt for license information
+//
+//===----------------------------------------------------------------------===//
+
+//===----------------------------------------------------------------------===//
+// copy(from:)
+//===----------------------------------------------------------------------===//
+
+extension MutableCollection {
+  /// Copies the elements from the given sequence on top of the elements of this
+  /// collection, until the shorter one is exhausted.
+  ///
+  /// If you want to limit how much of this collection can be overrun, call this
+  /// method on the limiting subsequence instead.
+  ///
+  /// - Parameters:
+  ///   - source: The sequence to read the replacement values from.
+  /// - Returns: A two-member tuple where the first member is the index of the
+  ///   first element of this collection that was not assigned a copy.  It will
+  ///   be `startIndex` if no copying was done and `endIndex` if every element
+  ///   was written over.  The second member is an iterator covering all the
+  ///   elements of `source` that where not used as part of the copying.  It
+  ///   will be empty if every element was used.
+  /// - Postcondition: Let *k* be the element count of the shorter of `self` and
+  ///   source.  Then `prefix(k)` will be equivalent to `source.prefix(k)`,
+  ///   while `dropFirst(k)` is unchanged.
+  ///
+  /// - Complexity: O(*n*), where *n* is the length of the shorter sequence
+  ///   between `self` and `source`.
+  public mutating func copy<S: Sequence>(
+    from source: S
+  ) -> (copyEnd: Index, sourceTail: S.Iterator) where S.Element == Element {
+    var current = startIndex, iterator = source.makeIterator()
+    let end = endIndex
+    while current < end, let source = iterator.next() {
+      self[current] = source
+      formIndex(after: &current)
+    }
+    return (current, iterator)
+  }
+}
diff --git a/Tests/SwiftAlgorithmsTests/CopyTests.swift b/Tests/SwiftAlgorithmsTests/CopyTests.swift
@@ -0,0 +1,118 @@
+//===----------------------------------------------------------------------===//
+//
+// This source file is part of the Swift Algorithms open source project
+//
+// Copyright (c) 2020 Apple Inc. and the Swift project authors
+// Licensed under Apache License v2.0 with Runtime Library Exception
+//
+// See https://swift.org/LICENSE.txt for license information
+//
+//===----------------------------------------------------------------------===//
+
+import XCTest
+import Algorithms
+
+/// Unit tests for the `copy(from:)` method.
+final class CopyTests: XCTestCase {
+  /// Test empty source and destination.
+  func testBothEmpty() {
+    var empty1 = EmptyCollection<Double>()
+    let empty2 = EmptyCollection<Double>()
+    XCTAssertEqualSequences(empty1, [])
+
+    let result = empty1.copy(from: empty2)
+    XCTAssertEqual(result.copyEnd, empty1.startIndex)
+    XCTAssertEqualSequences(IteratorSequence(result.sourceTail), [])
+    XCTAssertEqualSequences(empty1, [])
+  }
+
+  /// Test nonempty source and empty destination.
+  func testOnlyDestinationEmpty() {
+    var empty = EmptyCollection<Double>()
+    let single = CollectionOfOne(1.1)
+    XCTAssertEqualSequences(empty, [])
+
+    let result = empty.copy(from: single)
+    XCTAssertEqual(result.copyEnd, empty.endIndex)
+    XCTAssertEqualSequences(IteratorSequence(result.sourceTail), [1.1])
+    XCTAssertEqualSequences(empty, [])
+  }
+
+  /// Test empty source and nonempty destination.
+  func testOnlySourceEmpty() {
+    var single = CollectionOfOne(2.2)
+    let empty = EmptyCollection<Double>()
+    XCTAssertEqualSequences(single, [2.2])
+
+    let result = single.copy(from: empty)
+    XCTAssertEqual(result.copyEnd, single.startIndex)
+    XCTAssertEqualSequences(IteratorSequence(result.sourceTail), [])
+    XCTAssertEqualSequences(single, [2.2])
+  }
+
+  /// Test two one-element collections.
+  func testTwoSingles() {
+    var destination = CollectionOfOne(3.3)
+    let source = CollectionOfOne(4.4)
+    XCTAssertEqualSequences(destination, [3.3])
+
+    let result = destination.copy(from: source)
+    XCTAssertEqual(result.copyEnd, destination.endIndex)
+    XCTAssertEqualSequences(IteratorSequence(result.sourceTail), [])
+    XCTAssertEqualSequences(destination, [4.4])
+  }
+
+  /// Test two equal-length multi-element collections.
+  func testTwoWithEqualLength() {
+    var destination = Array("ABCDE")
+    let source = "fghij"
+    XCTAssertEqualSequences(destination, "ABCDE")
+
+    let result = destination.copy(from: source)
+    XCTAssertEqual(result.copyEnd, destination.endIndex)
+    XCTAssertEqualSequences(IteratorSequence(result.sourceTail), [])
+    XCTAssertEqualSequences(destination, "fghij")
+  }
+
+  /// Test a source longer than a multi-element destination.
+  func testLongerDestination() {
+    var destination = Array(1...5)
+    let source = 10...100
+    XCTAssertEqualSequences(destination, 1...5)
+
+    let result = destination.copy(from: source)
+    XCTAssertEqual(result.copyEnd, destination.endIndex)
+    XCTAssertEqualSequences(IteratorSequence(result.sourceTail), 15...100)
+    XCTAssertEqualSequences(destination, 10..<15)
+  }
+
+  /// Test a multi-element source shorter than the destination.
+  func testShorterDestination() {
+    var destination = Array("abcdefghijklm")
+    let source = "NOPQR"
+    XCTAssertEqualSequences(destination, "abcdefghijklm")
+
+    let result = destination.copy(from: source)
+    XCTAssertEqual(result.copyEnd, destination.index(destination.startIndex,
+                                                 offsetBy: source.count))
+    XCTAssertEqualSequences(IteratorSequence(result.sourceTail), [])
+    XCTAssertEqualSequences(destination, "NOPQRfghijklm")
+  }
+
+  /// Test copying over part of the destination.
+  func testPartial() {
+    var destination = Array("abcdefghijklm")
+    let source = "STUVWXYZ"
+    XCTAssertEqualSequences(destination, "abcdefghijklm")
+
+    let result = destination[3..<7].copy(from: source)
+    XCTAssertEqual(result.copyEnd, 7)
+    XCTAssertEqualSequences(IteratorSequence(result.sourceTail), "WXYZ")
+    XCTAssertEqualSequences(destination, "abcSTUVhijklm")
+
+    let result2 = destination[3..<7].copy(from: "12")
+    XCTAssertEqual(result2.copyEnd, 5)
+    XCTAssertEqualSequences(IteratorSequence(result2.sourceTail), [])
+    XCTAssertEqualSequences(destination, "abc12UVhijklm")
+  }
+}