ContiguousArray.swift

//===--- ContiguousArray.swift --------------------------------*- swift -*-===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2018 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
// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//
//
// Three generic, mutable array-like types with value semantics.
//
// - `ContiguousArray<Element>` is a fast, contiguous array of `Element` with
// a known backing store.
//
//===----------------------------------------------------------------------===//

/// A contiguously stored array.
///
/// The `ContiguousArray` type is a specialized array that always stores its
/// elements in a contiguous region of memory. This contrasts with `Array`,
/// which can store its elements in either a contiguous region of memory or an
/// `NSArray` instance if its `Element` type is a class or `@objc` protocol.
///
/// If your array's `Element` type is a class or `@objc` protocol and you do
/// not need to bridge the array to `NSArray` or pass the array to Objective-C
/// APIs, using `ContiguousArray` may be more efficient and have more
/// predictable performance than `Array`. If the array's `Element` type is a
/// struct or enumeration, `Array` and `ContiguousArray` should have similar
/// efficiency.
///
/// For more information about using arrays, see `Array` and `ArraySlice`, with
/// which `ContiguousArray` shares most properties and methods.
@frozen
publicstructContiguousArray<Element>:_DestructorSafeContainer{
@usableFromInline
internaltypealias_Buffer=_ContiguousArrayBuffer<Element>

@usableFromInline
internalvar_buffer:_Buffer

 /// Initialization from an existing buffer does not have "array.init"
 /// semantics because the caller may retain an alias to buffer.
@inlinable
internalinit(_buffer:_Buffer){
self._buffer = _buffer
}
}

//===--- private helpers---------------------------------------------------===//
extensionContiguousArray{
@inlinable
@_semantics("array.get_count")
internalfunc _getCount()->Int{
return _buffer.immutableCount
}

@inlinable
@_semantics("array.get_capacity")
internalfunc _getCapacity()->Int{
return _buffer.immutableCapacity
}

@inlinable
@_semantics("array.make_mutable")
internalmutatingfunc _makeMutableAndUnique(){
if_slowPath(!_buffer.beginCOWMutation()){
 _buffer = _buffer._consumeAndCreateNew()
}
}

 /// Marks the end of an Array mutation.
 ///
 /// After a call to `_endMutation` the buffer must not be mutated until a call
 /// to `_makeMutableAndUnique`.
@_alwaysEmitIntoClient
@_semantics("array.end_mutation")
internalmutatingfunc _endMutation(){
 _buffer.endCOWMutation()
}

 /// Check that the given `index` is valid for subscripting, i.e.
 /// `0 ≤ index < count`.
@inlinable
@inline(__always)
internalfunc _checkSubscript_native(_ index:Int){
 _buffer._checkValidSubscript(index)
}

 /// Check that the given `index` is valid for subscripting, i.e.
 /// `0 ≤ index < count`.
 ///
 /// - Precondition: The buffer must be uniquely referenced and native.
@_alwaysEmitIntoClient
@_semantics("array.check_subscript")
internalfunc _checkSubscript_mutating(_ index:Int){
 _buffer._checkValidSubscriptMutating(index)
}

 /// Check that the specified `index` is valid, i.e. `0 ≤ index ≤ count`.
@inlinable
@_semantics("array.check_index")
internalfunc _checkIndex(_ index:Int){
_precondition(index <= endIndex,"ContiguousArray index is out of range")
_precondition(index >= startIndex,"Negative ContiguousArray index is out of range")
}

@inlinable
@_semantics("array.get_element_address")
internalfunc _getElementAddress(_ index:Int)->UnsafeMutablePointer<Element>{
return _buffer.firstElementAddress + index
}
}

extensionContiguousArray:_ArrayProtocol{
 /// The total number of elements that the array can contain without
 /// allocating new storage.
 ///
 /// Every array reserves a specific amount of memory to hold its contents.
 /// When you add elements to an array and that array begins to exceed its
 /// reserved capacity, the array allocates a larger region of memory and
 /// copies its elements into the new storage. The new storage is a multiple
 /// of the old storage's size. This exponential growth strategy means that
 /// appending an element happens in constant time, averaging the performance
 /// of many append operations. Append operations that trigger reallocation
 /// have a performance cost, but they occur less and less often as the array
 /// grows larger.
 ///
 /// The following example creates an array of integers from an array literal,
 /// then appends the elements of another collection. Before appending, the
 /// array allocates new storage that is large enough store the resulting
 /// elements.
 ///
 /// var numbers = [10, 20, 30, 40, 50]
 /// // numbers.count == 5
 /// // numbers.capacity == 5
 ///
 /// numbers.append(contentsOf: stride(from: 60, through: 100, by: 10))
 /// // numbers.count == 10
 /// // numbers.capacity == 10
@inlinable
publicvarcapacity:Int{
return_getCapacity()
}

 /// An object that guarantees the lifetime of this array's elements.
@inlinable
public // @testable
var_owner:AnyObject?{
return _buffer.owner
}

 /// If the elements are stored contiguously, a pointer to the first
 /// element. Otherwise, `nil`.
@inlinable
publicvar_baseAddressIfContiguous:UnsafeMutablePointer<Element>?{
@inline(__always) // FIXME(TODO: JIRA): Hack around test failure
get{return _buffer.firstElementAddressIfContiguous }
}

@inlinable
internalvar_baseAddress:UnsafeMutablePointer<Element>{
return _buffer.firstElementAddress
}
}

extensionContiguousArray:RandomAccessCollection,MutableCollection{
 /// The index type for arrays, `Int`.
publictypealiasIndex=Int

 /// The type that represents the indices that are valid for subscripting an
 /// array, in ascending order.
publictypealiasIndices=Range<Int>

 /// The type that allows iteration over an array's elements.
publictypealiasIterator=IndexingIterator<ContiguousArray>

 /// The position of the first element in a nonempty array.
 ///
 /// For an instance of `ContiguousArray`, `startIndex` is always zero. If the array
 /// is empty, `startIndex` is equal to `endIndex`.
@inlinable
publicvarstartIndex:Int{
return0
}

 /// The array's "past the end" position---that is, the position one greater
 /// than the last valid subscript argument.
 ///
 /// When you need a range that includes the last element of an array, use the
 /// half-open range operator (`..<`) with `endIndex`. The `..<` operator
 /// creates a range that doesn't include the upper bound, so it's always
 /// safe to use with `endIndex`. For example:
 ///
 /// let numbers = [10, 20, 30, 40, 50]
 /// if let i = numbers.firstIndex(of: 30) {
 /// print(numbers[i ..< numbers.endIndex])
 /// }
 /// // Prints "[30, 40, 50]"
 ///
 /// If the array is empty, `endIndex` is equal to `startIndex`.
publicvarendIndex:Int{
@inlinable
get{
return_getCount()
}
}

 /// Returns the position immediately after the given index.
 ///
 /// - Parameter i: A valid index of the collection. `i` must be less than
 /// `endIndex`.
 /// - Returns: The index immediately after `i`.
@inlinable
publicfunc index(after i:Int)->Int{
 // NOTE: this is a manual specialization of index movement for a Strideable
 // index that is required for Array performance. The optimizer is not
 // capable of creating partial specializations yet.
 // NOTE: Range checks are not performed here, because it is done later by
 // the subscript function.
return i +1
}

 /// Replaces the given index with its successor.
 ///
 /// - Parameter i: A valid index of the collection. `i` must be less than
 /// `endIndex`.
@inlinable
publicfunc formIndex(after i:inoutInt){
 // NOTE: this is a manual specialization of index movement for a Strideable
 // index that is required for Array performance. The optimizer is not
 // capable of creating partial specializations yet.
 // NOTE: Range checks are not performed here, because it is done later by
 // the subscript function.
 i +=1
}

 /// Returns the position immediately before the given index.
 ///
 /// - Parameter i: A valid index of the collection. `i` must be greater than
 /// `startIndex`.
 /// - Returns: The index immediately before `i`.
@inlinable
publicfunc index(before i:Int)->Int{
 // NOTE: this is a manual specialization of index movement for a Strideable
 // index that is required for Array performance. The optimizer is not
 // capable of creating partial specializations yet.
 // NOTE: Range checks are not performed here, because it is done later by
 // the subscript function.
return i -1
}

 /// Replaces the given index with its predecessor.
 ///
 /// - Parameter i: A valid index of the collection. `i` must be greater than
 /// `startIndex`.
@inlinable
publicfunc formIndex(before i:inoutInt){
 // NOTE: this is a manual specialization of index movement for a Strideable
 // index that is required for Array performance. The optimizer is not
 // capable of creating partial specializations yet.
 // NOTE: Range checks are not performed here, because it is done later by
 // the subscript function.
 i -=1
}

 /// Returns an index that is the specified distance from the given index.
 ///
 /// The following example obtains an index advanced four positions from an
 /// array's starting index and then prints the element at that position.
 ///
 /// let numbers = [10, 20, 30, 40, 50]
 /// let i = numbers.index(numbers.startIndex, offsetBy: 4)
 /// print(numbers[i])
 /// // Prints "50"
 ///
 /// The value passed as `distance` must not offset `i` beyond the bounds of
 /// the collection.
 ///
 /// - Parameters:
 /// - i: A valid index of the array.
 /// - distance: The distance to offset `i`.
 /// - Returns: An index offset by `distance` from the index `i`. If
 /// `distance` is positive, this is the same value as the result of
 /// `distance` calls to `index(after:)`. If `distance` is negative, this
 /// is the same value as the result of `abs(distance)` calls to
 /// `index(before:)`.
@inlinable
publicfunc index(_ i:Int, offsetBy distance:Int)->Int{
 // NOTE: this is a manual specialization of index movement for a Strideable
 // index that is required for Array performance. The optimizer is not
 // capable of creating partial specializations yet.
 // NOTE: Range checks are not performed here, because it is done later by
 // the subscript function.
return i + distance
}

 /// Returns an index that is the specified distance from the given index,
 /// unless that distance is beyond a given limiting index.
 ///
 /// The following example obtains an index advanced four positions from an
 /// array's starting index and then prints the element at that position. The
 /// operation doesn't require going beyond the limiting `numbers.endIndex`
 /// value, so it succeeds.
 ///
 /// let numbers = [10, 20, 30, 40, 50]
 /// if let i = numbers.index(numbers.startIndex,
 /// offsetBy: 4,
 /// limitedBy: numbers.endIndex) {
 /// print(numbers[i])
 /// }
 /// // Prints "50"
 ///
 /// The next example attempts to retrieve an index ten positions from
 /// `numbers.startIndex`, but fails, because that distance is beyond the
 /// index passed as `limit`.
 ///
 /// let j = numbers.index(numbers.startIndex,
 /// offsetBy: 10,
 /// limitedBy: numbers.endIndex)
 /// print(j)
 /// // Prints "nil"
 ///
 /// The value passed as `distance` must not offset `i` beyond the bounds of
 /// the collection, unless the index passed as `limit` prevents offsetting
 /// beyond those bounds.
 ///
 /// - Parameters:
 /// - i: A valid index of the array.
 /// - distance: The distance to offset `i`.
 /// - limit: A valid index of the collection to use as a limit. If
 /// `distance > 0`, `limit` has no effect if it is less than `i`.
 /// Likewise, if `distance < 0`, `limit` has no effect if it is greater
 /// than `i`.
 /// - Returns: An index offset by `distance` from the index `i`, unless that
 /// index would be beyond `limit` in the direction of movement. In that
 /// case, the method returns `nil`.
 ///
 /// - Complexity: O(1)
@inlinable
publicfunc index(
 _ i:Int, offsetBy distance:Int, limitedBy limit:Int
)->Int?{
 // NOTE: this is a manual specialization of index movement for a Strideable
 // index that is required for Array performance. The optimizer is not
 // capable of creating partial specializations yet.
 // NOTE: Range checks are not performed here, because it is done later by
 // the subscript function.
letl= limit - i
if distance >0? l >=0 && l < distance : l <=0 && distance < l {
returnnil
}
return i + distance
}

 /// Returns the distance between two indices.
 ///
 /// - Parameters:
 /// - start: A valid index of the collection.
 /// - end: Another valid index of the collection. If `end` is equal to
 /// `start`, the result is zero.
 /// - Returns: The distance between `start` and `end`.
@inlinable
publicfunc distance(from start:Int, to end:Int)->Int{
 // NOTE: this is a manual specialization of index movement for a Strideable
 // index that is required for Array performance. The optimizer is not
 // capable of creating partial specializations yet.
 // NOTE: Range checks are not performed here, because it is done later by
 // the subscript function.
return end - start
}

@inlinable
publicfunc _failEarlyRangeCheck(_ index:Int, bounds:Range<Int>){
 // NOTE: This method is a no-op for performance reasons.
}

@inlinable
publicfunc _failEarlyRangeCheck(_ range:Range<Int>, bounds:Range<Int>){
 // NOTE: This method is a no-op for performance reasons.
}

 /// Accesses the element at the specified position.
 ///
 /// The following example uses indexed subscripting to update an array's
 /// second element. After assigning the new value (`"Butler"`) at a specific
 /// position, that value is immediately available at that same position.
 ///
 /// var streets = ["Adams", "Bryant", "Channing", "Douglas", "Evarts"]
 /// streets[1] = "Butler"
 /// print(streets[1])
 /// // Prints "Butler"
 ///
 /// - Parameter index: The position of the element to access. `index` must be
 /// greater than or equal to `startIndex` and less than `endIndex`.
 ///
 /// - Complexity: Reading an element from an array is O(1). Writing is O(1)
 /// unless the array's storage is shared with another array, in which case
 /// writing is O(*n*), where *n* is the length of the array.
@inlinable
public subscript(index:Int)->Element{
get{
_checkSubscript_native(index)
return _buffer.getElement(index)
}
_modify{
_makeMutableAndUnique()
_checkSubscript_mutating(index)
letaddress= _buffer.mutableFirstElementAddress + index
 yield &address.pointee
_endMutation();
}
}

 /// Accesses a contiguous subrange of the array's elements.
 ///
 /// The returned `ArraySlice` instance uses the same indices for the same
 /// elements as the original array. In particular, that slice, unlike an
 /// array, may have a nonzero `startIndex` and an `endIndex` that is not
 /// equal to `count`. Always use the slice's `startIndex` and `endIndex`
 /// properties instead of assuming that its indices start or end at a
 /// particular value.
 ///
 /// This example demonstrates getting a slice of an array of strings, finding
 /// the index of one of the strings in the slice, and then using that index
 /// in the original array.
 ///
 /// let streets = ["Adams", "Bryant", "Channing", "Douglas", "Evarts"]
 /// let streetsSlice = streets[2 ..< streets.endIndex]
 /// print(streetsSlice)
 /// // Prints "["Channing", "Douglas", "Evarts"]"
 ///
 /// let i = streetsSlice.firstIndex(of: "Evarts") // 4
 /// print(streets[i!])
 /// // Prints "Evarts"
 ///
 /// - Parameter bounds: A range of integers. The bounds of the range must be
 /// valid indices of the array.
@inlinable
public subscript(bounds:Range<Int>)->ArraySlice<Element>{
get{
_checkIndex(bounds.lowerBound)
_checkIndex(bounds.upperBound)
returnArraySlice(_buffer:_buffer[bounds])
}
set(rhs){
_checkIndex(bounds.lowerBound)
_checkIndex(bounds.upperBound)
 // If the replacement buffer has same identity, and the ranges match,
 // then this was a pinned in-place modification, nothing further needed.
ifself[bounds]._buffer.identity != rhs._buffer.identity
 || bounds != rhs.startIndex..<rhs.endIndex {
self.replaceSubrange(bounds, with: rhs)
}
}
}

 /// The number of elements in the array.
@inlinable
publicvarcount:Int{
return_getCount()
}
}

extensionContiguousArray:ExpressibleByArrayLiteral{
 /// Creates an array from the given array literal.
 ///
 /// Do not call this initializer directly. It is used by the compiler when
 /// you use an array literal. Instead, create a new array by using an array
 /// literal as its value. To do this, enclose a comma-separated list of
 /// values in square brackets.
 ///
 /// Here, an array of strings is created from an array literal holding only
 /// strings:
 ///
 /// let ingredients: ContiguousArray =
 /// ["cocoa beans", "sugar", "cocoa butter", "salt"]
 ///
 /// - Parameter elements: A variadic list of elements of the new array.
@inlinable
publicinit(arrayLiteral elements:Element...){
self.init(_buffer:ContiguousArray(elements)._buffer)
}
}


extensionContiguousArray:RangeReplaceableCollection{
 /// Creates a new, empty array.
 ///
 /// This is equivalent to initializing with an empty array literal.
 /// For example:
 ///
 /// var emptyArray = Array<Int>()
 /// print(emptyArray.isEmpty)
 /// // Prints "true"
 ///
 /// emptyArray = []
 /// print(emptyArray.isEmpty)
 /// // Prints "true"
@inlinable
@_semantics("array.init.empty")
publicinit(){
 _buffer =_Buffer()
}

 /// Creates an array containing the elements of a sequence.
 ///
 /// You can use this initializer to create an array from any other type that
 /// conforms to the `Sequence` protocol. For example, you might want to
 /// create an array with the integers from 1 through 7. Use this initializer
 /// around a range instead of typing all those numbers in an array literal.
 ///
 /// let numbers = Array(1...7)
 /// print(numbers)
 /// // Prints "[1, 2, 3, 4, 5, 6, 7]"
 ///
 /// You can also use this initializer to convert a complex sequence or
 /// collection type back to an array. For example, the `keys` property of
 /// a dictionary isn't an array with its own storage, it's a collection
 /// that maps its elements from the dictionary only when they're
 /// accessed, saving the time and space needed to allocate an array. If
 /// you need to pass those keys to a method that takes an array, however,
 /// use this initializer to convert that list from its type of
 /// `LazyMapCollection<Dictionary<String, Int>, Int>` to a simple
 /// `[String]`.
 ///
 /// func cacheImagesWithNames(names: [String]) {
 /// // custom image loading and caching
 /// }
 ///
 /// let namedHues: [String: Int] = ["Vermillion": 18, "Magenta": 302,
 /// "Gold": 50, "Cerise": 320]
 /// let colorNames = Array(namedHues.keys)
 /// cacheImagesWithNames(colorNames)
 ///
 /// print(colorNames)
 /// // Prints "["Gold", "Cerise", "Magenta", "Vermillion"]"
 ///
 /// - Parameter s: The sequence of elements to turn into an array.
@inlinable
publicinit<S:Sequence>(_ s:S)where S.Element ==Element{
self.init(_buffer: s._copyToContiguousArray()._buffer)
}

 /// Creates a new array containing the specified number of a single, repeated
 /// value.
 ///
 /// Here's an example of creating an array initialized with five strings
 /// containing the letter *Z*.
 ///
 /// let fiveZs = Array(repeating: "Z", count: 5)
 /// print(fiveZs)
 /// // Prints "["Z", "Z", "Z", "Z", "Z"]"
 ///
 /// - Parameters:
 /// - repeatedValue: The element to repeat.
 /// - count: The number of times to repeat the value passed in the
 /// `repeating` parameter. `count` must be zero or greater.
@inlinable
@_semantics("array.init")
publicinit(repeating repeatedValue:Element, count:Int){
varp:UnsafeMutablePointer<Element>
(self, p)=ContiguousArray._allocateUninitialized(count)
for_in0..<count {
 p.initialize(to: repeatedValue)
 p +=1
}
_endMutation()
}

@inline(never)
@usableFromInline
internalstaticfunc _allocateBufferUninitialized(
 minimumCapacity:Int
)->_Buffer{
letnewBuffer=_ContiguousArrayBuffer<Element>(
 _uninitializedCount:0, minimumCapacity: minimumCapacity)
return_Buffer(_buffer: newBuffer, shiftedToStartIndex:0)
}

 /// Construct a ContiguousArray of `count` uninitialized elements.
@inlinable
internalinit(_uninitializedCount count:Int){
_precondition(count >=0,"Can't construct ContiguousArray with count < 0")
 // Note: Sinking this constructor into an else branch below causes an extra
 // Retain/Release.
 _buffer =_Buffer()
if count >0{
 // Creating a buffer instead of calling reserveCapacity saves doing an
 // unnecessary uniqueness check. We disable inlining here to curb code
 // growth.
 _buffer =ContiguousArray._allocateBufferUninitialized(minimumCapacity: count)
 _buffer.mutableCount = count
}
 // Can't store count here because the buffer might be pointing to the
 // shared empty array.
}

 /// Entry point for `Array` literal construction; builds and returns
 /// a ContiguousArray of `count` uninitialized elements.
@inlinable
@_semantics("array.uninitialized")
internalstaticfunc _allocateUninitialized(
 _ count:Int
)->(ContiguousArray,UnsafeMutablePointer<Element>){
letresult=ContiguousArray(_uninitializedCount: count)
return(result, result._buffer.firstElementAddress)
}

 //===--- basic mutations ------------------------------------------------===//

 /// Reserves enough space to store the specified number of elements.
 ///
 /// If you are adding a known number of elements to an array, use this method
 /// to avoid multiple reallocations. This method ensures that the array has
 /// unique, mutable, contiguous storage, with space allocated for at least
 /// the requested number of elements.
 ///
 /// For performance reasons, the size of the newly allocated storage might be
 /// greater than the requested capacity. Use the array's `capacity` property
 /// to determine the size of the new storage.
 ///
 /// Preserving an Array's Geometric Growth Strategy
 /// ===============================================
 ///
 /// If you implement a custom data structure backed by an array that grows
 /// dynamically, naively calling the `reserveCapacity(_:)` method can lead
 /// to worse than expected performance. Arrays need to follow a geometric
 /// allocation pattern for appending elements to achieve amortized
 /// constant-time performance. The `Array` type's `append(_:)` and
 /// `append(contentsOf:)` methods take care of this detail for you, but
 /// `reserveCapacity(_:)` allocates only as much space as you tell it to
 /// (padded to a round value), and no more. This avoids over-allocation, but
 /// can result in insertion not having amortized constant-time performance.
 ///
 /// The following code declares `values`, an array of integers, and the
 /// `addTenQuadratic()` function, which adds ten more values to the `values`
 /// array on each call.
 ///
 /// var values: [Int] = [0, 1, 2, 3]
 ///
 /// // Don't use 'reserveCapacity(_:)' like this
 /// func addTenQuadratic() {
 /// let newCount = values.count + 10
 /// values.reserveCapacity(newCount)
 /// for n in values.count..<newCount {
 /// values.append(n)
 /// }
 /// }
 ///
 /// The call to `reserveCapacity(_:)` increases the `values` array's capacity
 /// by exactly 10 elements on each pass through `addTenQuadratic()`, which
 /// is linear growth. Instead of having constant time when averaged over
 /// many calls, the function may decay to performance that is linear in
 /// `values.count`. This is almost certainly not what you want.
 ///
 /// In cases like this, the simplest fix is often to simply remove the call
 /// to `reserveCapacity(_:)`, and let the `append(_:)` method grow the array
 /// for you.
 ///
 /// func addTen() {
 /// let newCount = values.count + 10
 /// for n in values.count..<newCount {
 /// values.append(n)
 /// }
 /// }
 ///
 /// If you need more control over the capacity of your array, implement your
 /// own geometric growth strategy, passing the size you compute to
 /// `reserveCapacity(_:)`.
 ///
 /// - Parameter minimumCapacity: The requested number of elements to store.
 ///
 /// - Complexity: O(*n*), where *n* is the number of elements in the array.
@inlinable
@_semantics("array.mutate_unknown")
publicmutatingfunc reserveCapacity(_ minimumCapacity:Int){
_reserveCapacityImpl(minimumCapacity: minimumCapacity,
 growForAppend:false)
_endMutation()
}

 /// Reserves enough space to store `minimumCapacity` elements.
 /// If a new buffer needs to be allocated and `growForAppend` is true,
 /// the new capacity is calculated using `_growArrayCapacity`.
@_alwaysEmitIntoClient
internalmutatingfunc _reserveCapacityImpl(
 minimumCapacity:Int, growForAppend:Bool
){
letisUnique= _buffer.beginCOWMutation()
if_slowPath(!isUnique || _buffer.mutableCapacity < minimumCapacity){
_createNewBuffer(bufferIsUnique: isUnique,
 minimumCapacity:Swift.max(minimumCapacity, _buffer.count),
 growForAppend: growForAppend)
}
_internalInvariant(_buffer.mutableCapacity >= minimumCapacity)
_internalInvariant(_buffer.mutableCapacity ==0 || _buffer.isUniquelyReferenced())
}

 /// Creates a new buffer, replacing the current buffer.
 ///
 /// If `bufferIsUnique` is true, the buffer is assumed to be uniquely
 /// referenced by this array and the elements are moved - instead of copied -
 /// to the new buffer.
 /// The `minimumCapacity` is the lower bound for the new capacity.
 /// If `growForAppend` is true, the new capacity is calculated using
 /// `_growArrayCapacity`.
@_alwaysEmitIntoClient
@inline(never)
internalmutatingfunc _createNewBuffer(
 bufferIsUnique:Bool, minimumCapacity:Int, growForAppend:Bool
){
_internalInvariant(!bufferIsUnique || _buffer.isUniquelyReferenced())
 _buffer = _buffer._consumeAndCreateNew(bufferIsUnique: bufferIsUnique,
 minimumCapacity: minimumCapacity,
 growForAppend: growForAppend)
}

 /// Copy the contents of the current buffer to a new unique mutable buffer.
 /// The count of the new buffer is set to `oldCount`, the capacity of the
 /// new buffer is big enough to hold 'oldCount' + 1 elements.
@inline(never)
@inlinable // @specializable
internalmutatingfunc _copyToNewBuffer(oldCount:Int){
letnewCount= oldCount +1
varnewBuffer= _buffer._forceCreateUniqueMutableBuffer(
 countForNewBuffer: oldCount, minNewCapacity: newCount)
 _buffer._arrayOutOfPlaceUpdate(
&newBuffer, oldCount,0)
}

@inlinable
@_semantics("array.make_mutable")
internalmutatingfunc _makeUniqueAndReserveCapacityIfNotUnique(){
if_slowPath(!_buffer.beginCOWMutation()){
_createNewBuffer(bufferIsUnique:false,
 minimumCapacity: count +1,
 growForAppend:true)
}
}

@inlinable
@_semantics("array.mutate_unknown")
internalmutatingfunc _reserveCapacityAssumingUniqueBuffer(oldCount:Int){
 // Due to make_mutable hoisting the situation can arise where we hoist
 // _makeMutableAndUnique out of loop and use it to replace
 // _makeUniqueAndReserveCapacityIfNotUnique that preceeds this call. If the
 // array was empty _makeMutableAndUnique does not replace the empty array
 // buffer by a unique buffer (it just replaces it by the empty array
 // singleton).
 // This specific case is okay because we will make the buffer unique in this
 // function because we request a capacity > 0 and therefore _copyToNewBuffer
 // will be called creating a new buffer.
letcapacity= _buffer.mutableCapacity
_internalInvariant(capacity ==0 || _buffer.isMutableAndUniquelyReferenced())

if_slowPath(oldCount +1> capacity){
_createNewBuffer(bufferIsUnique: capacity >0,
 minimumCapacity: oldCount +1,
 growForAppend:true)
}
}

@inlinable
@_semantics("array.mutate_unknown")
internalmutatingfunc _appendElementAssumeUniqueAndCapacity(
 _ oldCount:Int,
 newElement:__owned Element
){
_internalInvariant(_buffer.isMutableAndUniquelyReferenced())
_internalInvariant(_buffer.mutableCapacity >= _buffer.mutableCount +1)

 _buffer.mutableCount = oldCount +1
(_buffer.mutableFirstElementAddress + oldCount).initialize(to: newElement)
}

 /// Adds a new element at the end of the array.
 ///
 /// Use this method to append a single element to the end of a mutable array.
 ///
 /// var numbers = [1, 2, 3, 4, 5]
 /// numbers.append(100)
 /// print(numbers)
 /// // Prints "[1, 2, 3, 4, 5, 100]"
 ///
 /// Because arrays increase their allocated capacity using an exponential
 /// strategy, appending a single element to an array is an O(1) operation
 /// when averaged over many calls to the `append(_:)` method. When an array
 /// has additional capacity and is not sharing its storage with another
 /// instance, appending an element is O(1). When an array needs to
 /// reallocate storage before appending or its storage is shared with
 /// another copy, appending is O(*n*), where *n* is the length of the array.
 ///
 /// - Parameter newElement: The element to append to the array.
 ///
 /// - Complexity: O(1) on average, over many calls to `append(_:)` on the
 /// same array.
@inlinable
@_semantics("array.append_element")
publicmutatingfunc append(_ newElement:__owned Element){
 // Separating uniqueness check and capacity check allows hoisting the
 // uniqueness check out of a loop.
_makeUniqueAndReserveCapacityIfNotUnique()
letoldCount= _buffer.mutableCount
_reserveCapacityAssumingUniqueBuffer(oldCount: oldCount)
_appendElementAssumeUniqueAndCapacity(oldCount, newElement: newElement)
_endMutation()
}

 /// Adds the elements of a sequence to the end of the array.
 ///
 /// Use this method to append the elements of a sequence to the end of this
 /// array. This example appends the elements of a `Range<Int>` instance
 /// to an array of integers.
 ///
 /// var numbers = [1, 2, 3, 4, 5]
 /// numbers.append(contentsOf: 10...15)
 /// print(numbers)
 /// // Prints "[1, 2, 3, 4, 5, 10, 11, 12, 13, 14, 15]"
 ///
 /// - Parameter newElements: The elements to append to the array.
 ///
 /// - Complexity: O(*m*) on average, where *m* is the length of
 /// `newElements`, over many calls to `append(contentsOf:)` on the same
 /// array.
@inlinable
@_semantics("array.append_contentsOf")
publicmutatingfunc append<S:Sequence>(contentsOf newElements:__owned S)
where S.Element ==Element{

defer{
_endMutation()
}

letnewElementsCount= newElements.underestimatedCount
_reserveCapacityImpl(minimumCapacity:self.count + newElementsCount,
 growForAppend:true)

letoldCount= _buffer.mutableCount
letstartNewElements= _buffer.mutableFirstElementAddress + oldCount
letbuf=UnsafeMutableBufferPointer(
 start: startNewElements,
 count: _buffer.mutableCapacity - oldCount)

var(remainder,writtenUpTo)= buf.initialize(from: newElements)

 // trap on underflow from the sequence's underestimate:
letwrittenCount= buf.distance(from: buf.startIndex, to: writtenUpTo)
_precondition(newElementsCount <= writtenCount,
"newElements.underestimatedCount was an overestimate")
 // can't check for overflow as sequences can underestimate

 // This check prevents a data race writing to _swiftEmptyArrayStorage
if writtenCount >0{
 _buffer.mutableCount = _buffer.mutableCount + writtenCount
}

if writtenUpTo == buf.endIndex {
 // there may be elements that didn't fit in the existing buffer,
 // append them in slow sequence-only mode
varnewCount= _buffer.mutableCount
varnextItem= remainder.next()
while nextItem !=nil{
_reserveCapacityAssumingUniqueBuffer(oldCount: newCount)

letcurrentCapacity= _buffer.mutableCapacity
letbase= _buffer.mutableFirstElementAddress

 // fill while there is another item and spare capacity
whilelet next = nextItem, newCount < currentCapacity {
(base + newCount).initialize(to: next)
 newCount +=1
 nextItem = remainder.next()
}
 _buffer.mutableCount = newCount
}
}
}

@inlinable
@_semantics("array.reserve_capacity_for_append")
internalmutatingfunc reserveCapacityForAppend(newElementsCount:Int){
 // Ensure uniqueness, mutability, and sufficient storage. Note that
 // for consistency, we need unique self even if newElements is empty.
_reserveCapacityImpl(minimumCapacity:self.count + newElementsCount,
 growForAppend:true)
_endMutation()
}

@inlinable
@_semantics("array.mutate_unknown")
publicmutatingfunc _customRemoveLast()->Element?{
_makeMutableAndUnique()
letnewCount= _buffer.mutableCount -1
_precondition(newCount >=0,"Can't removeLast from an empty ContiguousArray")
letpointer=(_buffer.mutableFirstElementAddress + newCount)
letelement= pointer.move()
 _buffer.mutableCount = newCount
_endMutation()
return element
}

 /// Removes and returns the element at the specified position.
 ///
 /// All the elements following the specified position are moved up to
 /// close the gap.
 ///
 /// var measurements: [Double] = [1.1, 1.5, 2.9, 1.2, 1.5, 1.3, 1.2]
 /// let removed = measurements.remove(at: 2)
 /// print(measurements)
 /// // Prints "[1.1, 1.5, 1.2, 1.5, 1.3, 1.2]"
 ///
 /// - Parameter index: The position of the element to remove. `index` must
 /// be a valid index of the array.
 /// - Returns: The element at the specified index.
 ///
 /// - Complexity: O(*n*), where *n* is the length of the array.
@inlinable
@discardableResult
@_semantics("array.mutate_unknown")
publicmutatingfunc remove(at index:Int)->Element{
_makeMutableAndUnique()
letcurrentCount= _buffer.mutableCount
_precondition(index < currentCount,"Index out of range")
_precondition(index >=0,"Index out of range")
letnewCount= currentCount -1
letpointer=(_buffer.mutableFirstElementAddress + index)
letresult= pointer.move()
 pointer.moveInitialize(from: pointer +1, count: newCount - index)
 _buffer.mutableCount = newCount
_endMutation()
return result
}

 /// Inserts a new element at the specified position.
 ///
 /// The new element is inserted before the element currently at the specified
 /// index. If you pass the array's `endIndex` property as the `index`
 /// parameter, the new element is appended to the array.
 ///
 /// var numbers = [1, 2, 3, 4, 5]
 /// numbers.insert(100, at: 3)
 /// numbers.insert(200, at: numbers.endIndex)
 ///
 /// print(numbers)
 /// // Prints "[1, 2, 3, 100, 4, 5, 200]"
 ///
 /// - Parameter newElement: 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 of the array or equal to its `endIndex`
 /// property.
 ///
 /// - Complexity: O(*n*), where *n* is the length of the array. If
 /// `i == endIndex`, this method is equivalent to `append(_:)`.
@inlinable
publicmutatingfunc insert(_ newElement:__owned Element, at i:Int){
_checkIndex(i)
self.replaceSubrange(i..<i, with:CollectionOfOne(newElement))
}

 /// Removes all elements from the array.
 ///
 /// - Parameter keepCapacity: Pass `true` to keep the existing capacity of
 /// the array after removing its elements. The default value is
 /// `false`.
 ///
 /// - Complexity: O(*n*), where *n* is the length of the array.
@inlinable
publicmutatingfunc removeAll(keepingCapacity keepCapacity:Bool=false){
if !keepCapacity {
 _buffer =_Buffer()
}
else{
self.replaceSubrange(indices, with:EmptyCollection())
}
}

 //===--- algorithms -----------------------------------------------------===//

@inlinable
publicmutatingfunc _withUnsafeMutableBufferPointerIfSupported<R>(
 _ body:(inoutUnsafeMutableBufferPointer<Element>)throws->R
)rethrows->R?{
returntrywithUnsafeMutableBufferPointer{
(bufferPointer)->Rin
returntrybody(&bufferPointer)
}
}

@inlinable
publicmutatingfunc withContiguousMutableStorageIfAvailable<R>(
 _ body:(inoutUnsafeMutableBufferPointer<Element>)throws->R
)rethrows->R?{
returntrywithUnsafeMutableBufferPointer{
(bufferPointer)->Rin
returntrybody(&bufferPointer)
}
}