//===----------------------------------------------------------------------===// // // This source file is part of the Swift Collections open source project // // Copyright (c) 2024 - 2026 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 // // SPDX-License-Identifier: Apache-2.0 WITH Swift-exception // //===----------------------------------------------------------------------===// #if !COLLECTIONS_SINGLE_MODULE import InternalCollectionsUtilities import ContainersPreview #endif #if compiler(>=6.2) @available(SwiftStdlib 5.0, *) extension UniqueArray where Element: ~Copyable { /// Inserts a new element into the array at the specified position. /// /// If the array does not have sufficient capacity to hold any more elements, /// then this reallocates storage to extend its capacity, using a geometric /// growth rate. /// /// The new element is inserted before the element currently at the specified /// index. If you pass the array's `endIndex` as the `index` parameter, then /// the new element is appended to the container. /// /// All existing elements at or following the specified position are moved to /// make room for the new item. /// /// - Parameter item: The new element to insert into the array. /// - Parameter i: The position at which to insert the new element. /// `index` must be a valid index in the array. /// /// - Complexity: O(`self.count`) @inlinable public mutating func insert(_ item: consuming Element, at index: Int) { precondition(index >= 0 && index <= count) // FIXME: Avoid moving the subsequent elements twice. _ensureFreeCapacity(1) _storage.insert(item, at: index) } } @available(SwiftStdlib 5.0, *) extension UniqueArray where Element: ~Copyable { /// Inserts a given number of new items into this array at the specified /// position, using a callback to directly initialize array storage by /// populating an output span. /// /// Existing elements in the array's storage are moved towards the back as /// needed to make room for the new items. /// /// If the array does not have sufficient capacity to hold the new elements, /// then this operation reallocates storage to extend its capacity, using a /// geometric growth rate. /// /// var buffer = UniqueArray() /// buffer.append([-999, 999]) /// var i = 0 /// buffer.insert(capacity: 3, at: 1) { target in /// while !target.isFull { /// target.append(i) /// i += 1 /// } /// } /// // `buffer` now contains [-999, 0, 1, 2, 999] /// /// - Parameters: /// - count: The number of items to insert into the array. /// - index: The position at which to insert the new items. /// `index` must be a valid index in the array. /// - body: A callback that gets called at most once to directly /// populate newly reserved storage within the array. The function /// is called with an empty output span of capacity matching the /// supplied count, and it must fully populate it before returning. /// /// - Complexity: O(`self.count` + `count`) @_alwaysEmitIntoClient @inline(__always) public mutating func insert( addingCount newItemCount: Int, at index: Int, initializingWith initializer: (inout OutputSpan) throws(E) -> Void ) throws(E) { _ensureFreeCapacity(newItemCount) try _storage.insert( addingCount: newItemCount, at: index, initializingWith: initializer) } } @available(SwiftStdlib 5.0, *) extension UniqueArray where Element: ~Copyable { /// Moves the elements of a fully initialized buffer into this array, /// starting at the specified position, and leaving the buffer /// uninitialized. /// /// If the array does not have sufficient capacity to hold all elements, /// then this reallocates storage to extend its capacity, using a geometric /// growth rate. /// /// - Parameters: /// - items: A fully initialized buffer whose contents to move into /// the array. /// /// - Complexity: O(`self.count` + `items.count`) @_alwaysEmitIntoClient public mutating func insert( moving items: UnsafeMutableBufferPointer, at index: Int ) { // FIXME: Avoid moving the subsequent elements twice. _ensureFreeCapacity(items.count) _storage.insert(moving: items, at: index) } #if UnstableContainersPreview /// Moves the elements of an input span into this array, /// starting at the specified position, and leaving the span empty. /// /// All existing elements at or following the specified position are moved to /// make room for the new items. /// /// If the array does not have sufficient capacity to hold the new elements, /// then this reallocates storage to extend its capacity, using a geometric /// growth rate. /// /// - Parameters: /// - items: An input span whose contents to move into /// the array. /// - index: The position at which to insert the new items. /// `index` must be a valid index in the array. /// /// - Complexity: O(`self.count` + `items.count`) @_alwaysEmitIntoClient public mutating func insert( moving items: inout InputSpan, at index: Int ) { _ensureFreeCapacity(items.count) _storage.insert(moving: &items, at: index) } #endif /// Moves the elements of an output span into this array, /// starting at the specified position, and leaving the span empty. /// /// All existing elements at or following the specified position are moved to /// make room for the new items. /// /// If the array does not have sufficient capacity to hold the new elements, /// then this reallocates storage to extend its capacity, using a geometric /// growth rate. /// /// - Parameters: /// - items: An output span whose contents to move into /// the array. /// - index: The position at which to insert the new items. /// `index` must be a valid index in the array. /// /// - Complexity: O(`self.count` + `items.count`) @_alwaysEmitIntoClient public mutating func insert( moving items: inout OutputSpan, at index: Int ) { _ensureFreeCapacity(items.count) _storage.insert(moving: &items, at: index) } /// Inserts the elements of a given array into the given position in this /// array by moving them between the containers. On return, the input array /// becomes empty, but it is not destroyed, and it preserves its original /// storage capacity. /// /// If the array does not have sufficient capacity to hold all elements, /// then this reallocates storage to extend its capacity, using a geometric /// growth rate. /// /// - Parameters: /// - items: An array whose contents to move into `self`. /// /// - Complexity: O(`self.count` + `items.count`) @_alwaysEmitIntoClient public mutating func insert( moving items: inout RigidArray, at index: Int ) { // FIXME: Avoid moving the subsequent elements twice. _ensureFreeCapacity(items.count) _storage.insert(moving: &items, at: index) } } @available(SwiftStdlib 5.0, *) extension UniqueArray where Element: ~Copyable { #if UnstableContainersPreview /// Inserts the elements of a given array into the given position in this /// array by consuming the source container. /// /// If the array does not have sufficient capacity to hold all elements, /// then this reallocates storage to extend its capacity, using a geometric /// growth rate. /// /// - Parameters: /// - items: A fully initialized buffer whose contents to move into /// the array. /// /// - Complexity: O(`self.count` + `items.count`) @_alwaysEmitIntoClient public mutating func insert( consuming items: consuming RigidArray, at index: Int ) { // FIXME: Remove this in favor of a generic algorithm over consumable containers // FIXME: Avoid moving the subsequent elements twice. _ensureFreeCapacity(items.count) _storage.insert(consuming: items, at: index) } #endif } @available(SwiftStdlib 5.0, *) extension UniqueArray where Element: ~Copyable { #if compiler(>=6.4) && UnstableContainersPreview /// Inserts at most `newItemCount` items generated by a producer into this /// array, starting at the given index. /// /// Existing elements in the array's storage are moved as needed to make room /// for the new items. /// /// If the array does not have sufficient capacity to hold enough items, /// then this reallocates the array's storage to grow its capacity, using a /// geometric growth rate. /// /// This operation inserts as many items as the producer can generate before /// either reaching `newItemCount`, or the producer hitting its end, or /// throwing an error. If the producer has more than `newItemCount` items /// left in its underlying sequence, then extra items remain available after /// this method returns. /// /// If the operation inserts fewer than `newItemCount` items, then it results /// in a gap in array storage that needs to be closed by moving some /// items to their correct positions given the adjusted count. This adds some /// overhead compared to adding exactly as many items as promised. /// /// - Parameters: /// - newItemCount: The maximum number of items to insert into the array. /// - index: The position at which to insert the new items. /// `index` must be a valid index in the array. /// - producer: A producer that generates the items to append. /// /// - Complexity: O(`self.count` + `newItemCount`) when amortized over many /// similar invocations on the same array. @_alwaysEmitIntoClient public mutating func insert< E: Error, P: Producer & ~Copyable & ~Escapable >( addingCount newItemCount: Int, from producer: inout P, at index: Int ) throws(E) where P.Element: ~Copyable { try insert(addingCount: newItemCount, at: index) { target throws(E) in while !target.isFull, try producer.generate(into: &target) { // Do nothing } } } #endif } @available(SwiftStdlib 5.0, *) extension UniqueArray { /// Copies the elements of a fully initialized buffer pointer into this /// array at the specified position. /// /// The new elements are inserted before the element currently at the /// specified index. If you pass the array's `endIndex` as the `index` /// parameter, then the new elements are appended to the end of the array. /// /// All existing elements at or following the specified position are moved to /// make room for the new item. /// /// If the array does not have sufficient capacity to hold enough elements, /// then this reallocates the array's storage to extend its capacity, using a /// geometric growth rate. /// /// - Parameters: /// - newElements: The new elements to insert into the array. The buffer /// must be fully initialized. /// - index: The position at which to insert the new elements. It must be /// a valid index of the array. /// /// - Complexity: O(`self.count` + `newElements.count`) @inlinable public mutating func insert( copying newElements: UnsafeBufferPointer, at index: Int ) { // FIXME: Avoid moving the subsequent elements twice. _ensureFreeCapacity(newElements.count) unsafe _storage.insert(copying: newElements, at: index) } /// Copies the elements of a fully initialized buffer pointer into this /// array at the specified position. /// /// The new elements are inserted before the element currently at the /// specified index. If you pass the array's `endIndex` as the `index` /// parameter, then the new elements are appended to the end of the array. /// /// All existing elements at or following the specified position are moved to /// make room for the new item. /// /// If the array does not have sufficient capacity to hold enough elements, /// then this reallocates the array's storage to extend its capacity, using a /// geometric growth rate. /// /// - Parameters: /// - newElements: The new elements to insert into the array. The buffer /// must be fully initialized. /// - index: The position at which to insert the new elements. It must be /// a valid index of the array. /// /// - Complexity: O(`self.count` + `newElements.count`) @inlinable public mutating func insert( copying newElements: UnsafeMutableBufferPointer, at index: Int ) { unsafe self.insert(copying: UnsafeBufferPointer(newElements), at: index) } /// Copies the elements of a span into this array at the specified position. /// /// The new elements are inserted before the element currently at the /// specified index. If you pass the array's `endIndex` as the `index` /// parameter, then the new elements are appended to the end of the array. /// /// All existing elements at or following the specified position are moved to /// make room for the new item. /// /// If the array does not have sufficient capacity to hold enough elements, /// then this reallocates the array's storage to extend its capacity, using a /// geometric growth rate. /// /// - Parameters: /// - newElements: The new elements to insert into the array. /// - index: The position at which to insert the new elements. It must be /// a valid index of the array. /// /// - Complexity: O(`self.count` + `newElements.count`) @inlinable public mutating func insert( copying newElements: Span, at index: Int ) { // FIXME: Avoid moving the subsequent elements twice. _ensureFreeCapacity(newElements.count) _storage.insert(copying: newElements, at: index) } #if compiler(>=6.4) && UnstableContainersPreview /// Copies the elements of a container into this array at the specified /// position. /// /// The new elements are inserted before the element currently at the /// specified index. If you pass the array's `endIndex` as the `index` /// parameter, then the new elements are appended to the end of the array. /// /// All existing elements at or following the specified position are moved to /// make room for the new item. /// /// If the array does not have sufficient capacity to hold enough elements, /// then this reallocates the array's storage to extend its capacity, using a /// geometric growth rate. /// /// - Parameters: /// - newElements: The new elements to insert into the array. /// - index: The position at which to insert the new elements. It must be /// a valid index of the array. /// /// - Complexity: O(*n* + *m*), where *n* is count of this array and /// *m* is the count of `newElements`. @_alwaysEmitIntoClient @inline(__always) public mutating func insert< C: Container & ~Copyable & ~Escapable >( copying newElements: borrowing C, at index: Int ) { // FIXME: Avoid moving the subsequent elements twice. let c = newElements.count _ensureFreeCapacity(c) _storage._insertContainer(at: index, copying: newElements, newCount: c) } #endif /// Copies the elements of a collection into this array at the specified /// position. /// /// The new elements are inserted before the element currently at the /// specified index. If you pass the array's `endIndex` as the `index` /// parameter, then the new elements are appended to the end of the array. /// /// All existing elements at or following the specified position are moved /// to make room for the new item. /// /// If the array does not have sufficient capacity to hold enough elements, /// then this reallocates the array's storage to extend its capacity, using a /// geometric growth rate. /// /// - Parameters: /// - newElements: The new elements to insert into the array. /// - index: The position at which to insert the new elements. It must be /// a valid index of the array. /// /// - Complexity: O(`self.count` + `newElements.count`) @inlinable public mutating func insert( copying newElements: some Collection, at index: Int ) { // FIXME: Avoid moving the subsequent elements twice. let newCount = newElements.count _ensureFreeCapacity(newCount) _storage._insertCollection( at: index, copying: newElements, newCount: newCount) } #if compiler(>=6.4) && UnstableContainersPreview /// Copies the elements of a container into this array at the specified /// position. /// /// The new elements are inserted before the element currently at the /// specified index. If you pass the array's `endIndex` as the `index` /// parameter, then the new elements are appended to the end of the array. /// /// All existing elements at or following the specified position are moved to /// make room for the new item. /// /// If the array does not have sufficient capacity to hold enough elements, /// then this reallocates the array's storage to extend its capacity, using a /// geometric growth rate. /// /// - Parameters: /// - newElements: The new elements to insert into the array. /// - index: The position at which to insert the new elements. It must be /// a valid index of the array. /// /// - Complexity: O(*n* + *m*), where *n* is count of this array and /// *m* is the count of `newElements`. @_alwaysEmitIntoClient @inline(__always) public mutating func insert< C: Container & Collection >( copying newElements: borrowing C, at index: Int ) { // FIXME: Avoid moving the subsequent elements twice. let c = newElements.count _ensureFreeCapacity(c) _storage._insertContainer(at: index, copying: newElements, newCount: c) } #endif } #endif