Array.swift

//===--- Array.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.
//
// - `Array<Element>` is like `ContiguousArray<Element>` when `Element` is not
// a reference type or an Objective-C existential. Otherwise, it may use
// an `NSArray` bridged from Cocoa for storage.
//
//===----------------------------------------------------------------------===//

/// An ordered, random-access collection.
///
/// Arrays are one of the most commonly used data types in an app. You use
/// arrays to organize your app's data. Specifically, you use the `Array` type
/// to hold elements of a single type, the array's `Element` type. An array
/// can store any kind of elements---from integers to strings to classes.
///
/// Swift makes it easy to create arrays in your code using an array literal:
/// simply surround a comma-separated list of values with square brackets.
/// Without any other information, Swift creates an array that includes the
/// specified values, automatically inferring the array's `Element` type. For
/// example:
///
/// // An array of 'Int' elements
/// let oddNumbers = [1, 3, 5, 7, 9, 11, 13, 15]
///
/// // An array of 'String' elements
/// let streets = ["Albemarle", "Brandywine", "Chesapeake"]
///
/// You can create an empty array by specifying the `Element` type of your
/// array in the declaration. For example:
///
/// // Shortened forms are preferred
/// var emptyDoubles: [Double] = []
///
/// // The full type name is also allowed
/// var emptyFloats: Array<Float> = Array()
///
/// If you need an array that is preinitialized with a fixed number of default
/// values, use the `Array(repeating:count:)` initializer.
///
/// var digitCounts = Array(repeating: 0, count: 10)
/// print(digitCounts)
/// // Prints "[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]"
///
/// Accessing Array Values
/// ======================
///
/// When you need to perform an operation on all of an array's elements, use a
/// `for`-`in` loop to iterate through the array's contents.
///
/// for street in streets {
/// print("I don't live on \(street).")
/// }
/// // Prints "I don't live on Albemarle."
/// // Prints "I don't live on Brandywine."
/// // Prints "I don't live on Chesapeake."
///
/// Use the `isEmpty` property to check quickly whether an array has any
/// elements, or use the `count` property to find the number of elements in
/// the array.
///
/// if oddNumbers.isEmpty {
/// print("I don't know any odd numbers.")
/// } else {
/// print("I know \(oddNumbers.count) odd numbers.")
/// }
/// // Prints "I know 8 odd numbers."
///
/// Use the `first` and `last` properties for safe access to the value of the
/// array's first and last elements. If the array is empty, these properties
/// are `nil`.
///
/// if let firstElement = oddNumbers.first, let lastElement = oddNumbers.last {
/// print(firstElement, lastElement, separator: ", ")
/// }
/// // Prints "1, 15"
///
/// print(emptyDoubles.first, emptyDoubles.last, separator: ", ")
/// // Prints "nil, nil"
///
/// You can access individual array elements through a subscript. The first
/// element of a nonempty array is always at index zero. You can subscript an
/// array with any integer from zero up to, but not including, the count of
/// the array. Using a negative number or an index equal to or greater than
/// `count` triggers a runtime error. For example:
///
/// print(oddNumbers[0], oddNumbers[3], separator: ", ")
/// // Prints "1, 7"
///
/// print(emptyDoubles[0])
/// // Triggers runtime error: Index out of range
///
/// Adding and Removing Elements
/// ============================
///
/// Suppose you need to store a list of the names of students that are signed
/// up for a class you're teaching. During the registration period, you need
/// to add and remove names as students add and drop the class.
///
/// var students = ["Ben", "Ivy", "Jordell"]
///
/// To add single elements to the end of an array, use the `append(_:)` method.
/// Add multiple elements at the same time by passing another array or a
/// sequence of any kind to the `append(contentsOf:)` method.
///
/// students.append("Maxime")
/// students.append(contentsOf: ["Shakia", "William"])
/// // ["Ben", "Ivy", "Jordell", "Maxime", "Shakia", "William"]
///
/// You can add new elements in the middle of an array by using the
/// `insert(_:at:)` method for single elements and by using
/// `insert(contentsOf:at:)` to insert multiple elements from another
/// collection or array literal. The elements at that index and later indices
/// are shifted back to make room.
///
/// students.insert("Liam", at: 3)
/// // ["Ben", "Ivy", "Jordell", "Liam", "Maxime", "Shakia", "William"]
///
/// To remove elements from an array, use the `remove(at:)`,
/// `removeSubrange(_:)`, and `removeLast()` methods.
///
/// // Ben's family is moving to another state
/// students.remove(at: 0)
/// // ["Ivy", "Jordell", "Liam", "Maxime", "Shakia", "William"]
///
/// // William is signing up for a different class
/// students.removeLast()
/// // ["Ivy", "Jordell", "Liam", "Maxime", "Shakia"]
///
/// You can replace an existing element with a new value by assigning the new
/// value to the subscript.
///
/// if let i = students.firstIndex(of: "Maxime") {
/// students[i] = "Max"
/// }
/// // ["Ivy", "Jordell", "Liam", "Max", "Shakia"]
///
/// Growing the Size of an Array
/// ----------------------------
///
/// 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.
///
/// If you know approximately how many elements you will need to store, use the
/// `reserveCapacity(_:)` method before appending to the array to avoid
/// intermediate reallocations. Use the `capacity` and `count` properties to
/// determine how many more elements the array can store without allocating
/// larger storage.
///
/// For arrays of most `Element` types, this storage is a contiguous block of
/// memory. For arrays with an `Element` type that is a class or `@objc`
/// protocol type, this storage can be a contiguous block of memory or an
/// instance of `NSArray`. Because any arbitrary subclass of `NSArray` can
/// become an `Array`, there are no guarantees about representation or
/// efficiency in this case.
///
/// Modifying Copies of Arrays
/// ==========================
///
/// Each array has an independent value that includes the values of all of its
/// elements. For simple types such as integers and other structures, this
/// means that when you change a value in one array, the value of that element
/// does not change in any copies of the array. For example:
///
/// var numbers = [1, 2, 3, 4, 5]
/// var numbersCopy = numbers
/// numbers[0] = 100
/// print(numbers)
/// // Prints "[100, 2, 3, 4, 5]"
/// print(numbersCopy)
/// // Prints "[1, 2, 3, 4, 5]"
///
/// If the elements in an array are instances of a class, the semantics are the
/// same, though they might appear different at first. In this case, the
/// values stored in the array are references to objects that live outside the
/// array. If you change a reference to an object in one array, only that
/// array has a reference to the new object. However, if two arrays contain
/// references to the same object, you can observe changes to that object's
/// properties from both arrays. For example:
///
/// // An integer type with reference semantics
/// class IntegerReference {
/// var value = 10
/// }
/// var firstIntegers = [IntegerReference(), IntegerReference()]
/// var secondIntegers = firstIntegers
///
/// // Modifications to an instance are visible from either array
/// firstIntegers[0].value = 100
/// print(secondIntegers[0].value)
/// // Prints "100"
///
/// // Replacements, additions, and removals are still visible
/// // only in the modified array
/// firstIntegers[0] = IntegerReference()
/// print(firstIntegers[0].value)
/// // Prints "10"
/// print(secondIntegers[0].value)
/// // Prints "100"
///
/// Arrays, like all variable-size collections in the standard library, use
/// copy-on-write optimization. Multiple copies of an array share the same
/// storage until you modify one of the copies. When that happens, the array
/// being modified replaces its storage with a uniquely owned copy of itself,
/// which is then modified in place. Optimizations are sometimes applied that
/// can reduce the amount of copying.
///
/// This means that if an array is sharing storage with other copies, the first
/// mutating operation on that array incurs the cost of copying the array. An
/// array that is the sole owner of its storage can perform mutating
/// operations in place.
///
/// In the example below, a `numbers` array is created along with two copies
/// that share the same storage. When the original `numbers` array is
/// modified, it makes a unique copy of its storage before making the
/// modification. Further modifications to `numbers` are made in place, while
/// the two copies continue to share the original storage.
///
/// var numbers = [1, 2, 3, 4, 5]
/// var firstCopy = numbers
/// var secondCopy = numbers
///
/// // The storage for 'numbers' is copied here
/// numbers[0] = 100
/// numbers[1] = 200
/// numbers[2] = 300
/// // 'numbers' is [100, 200, 300, 4, 5]
/// // 'firstCopy' and 'secondCopy' are [1, 2, 3, 4, 5]
///
/// Bridging Between Array and NSArray
/// ==================================
///
/// When you need to access APIs that require data in an `NSArray` instance
/// instead of `Array`, use the type-cast operator (`as`) to bridge your
/// instance. For bridging to be possible, the `Element` type of your array
/// must be a class, an `@objc` protocol (a protocol imported from Objective-C
/// or marked with the `@objc` attribute), or a type that bridges to a
/// Foundation type.
///
/// The following example shows how you can bridge an `Array` instance to
/// `NSArray` to use the `write(to:atomically:)` method. In this example, the
/// `colors` array can be bridged to `NSArray` because the `colors` array's
/// `String` elements bridge to `NSString`. The compiler prevents bridging the
/// `moreColors` array, on the other hand, because its `Element` type is
/// `Optional<String>`, which does *not* bridge to a Foundation type.
///
/// let colors = ["periwinkle", "rose", "moss"]
/// let moreColors: [String?] = ["ochre", "pine"]
///
/// let url = URL(fileURLWithPath: "names.plist")
/// (colors as NSArray).write(to: url, atomically: true)
/// // true
///
/// (moreColors as NSArray).write(to: url, atomically: true)
/// // error: cannot convert value of type '[String?]' to type 'NSArray'
///
/// Bridging from `Array` to `NSArray` takes O(1) time and O(1) space if the
/// array's elements are already instances of a class or an `@objc` protocol;
/// otherwise, it takes O(*n*) time and space.
///
/// When the destination array's element type is a class or an `@objc`
/// protocol, bridging from `NSArray` to `Array` first calls the `copy(with:)`
/// (`- copyWithZone:` in Objective-C) method on the array to get an immutable
/// copy and then performs additional Swift bookkeeping work that takes O(1)
/// time. For instances of `NSArray` that are already immutable, `copy(with:)`
/// usually returns the same array in O(1) time; otherwise, the copying
/// performance is unspecified. If `copy(with:)` returns the same array, the
/// instances of `NSArray` and `Array` share storage using the same
/// copy-on-write optimization that is used when two instances of `Array`
/// share storage.
///
/// When the destination array's element type is a nonclass type that bridges
/// to a Foundation type, bridging from `NSArray` to `Array` performs a
/// bridging copy of the elements to contiguous storage in O(*n*) time. For
/// example, bridging from `NSArray` to `Array<Int>` performs such a copy. No
/// further bridging is required when accessing elements of the `Array`
/// instance.
///
/// - Note: The `ContiguousArray` and `ArraySlice` types are not bridged;
/// instances of those types always have a contiguous block of memory as
/// their storage.
@frozen
publicstructArray<Element>:_DestructorSafeContainer{
#if _runtime(_ObjC)
@usableFromInline
internaltypealias_Buffer=_ArrayBuffer<Element>
#else
@usableFromInline
internaltypealias_Buffer=_ContiguousArrayBuffer<Element>
#endif

@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---------------------------------------------------===//
extensionArray{
 /// Returns `true` if the array is native and does not need a deferred
 /// type check. May be hoisted by the optimizer, which means its
 /// results may be stale by the time they are used if there is an
 /// inout violation in user code.
@inlinable
@_semantics("array.props.isNativeTypeChecked")
public // @testable
func _hoistableIsNativeTypeChecked()->Bool{
return _buffer.arrayPropertyIsNativeTypeChecked
}

@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`.
 ///
 /// This function is not used anymore, but must stay in the library for ABI
 /// compatibility.
@inlinable
@inline(__always)
internalfunc _checkSubscript_native(_ index:Int){
 _ =_checkSubscript(index, wasNativeTypeChecked:true)
}

 /// Check that the given `index` is valid for subscripting, i.e.
 /// `0 ≤ index < count`.
@inlinable
@_semantics("array.check_subscript")
public // @testable
func _checkSubscript(
 _ index:Int, wasNativeTypeChecked:Bool
)->_DependenceToken{
#if _runtime(_ObjC)
 _buffer._checkInoutAndNativeTypeCheckedBounds(
 index, wasNativeTypeChecked: wasNativeTypeChecked)
#else
 _buffer._checkValidSubscript(index)
#endif
return_DependenceToken()
}

 /// 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,"Array index is out of range")
_precondition(index >= startIndex,"Negative Array index is out of range")
}

@_semantics("array.get_element")
@inlinable // FIXME(inline-always)
@inline(__always)
public // @testable
func _getElement(
 _ index:Int,
 wasNativeTypeChecked:Bool,
 matchingSubscriptCheck:_DependenceToken
)->Element{
#if _runtime(_ObjC)
return _buffer.getElement(index, wasNativeTypeChecked: wasNativeTypeChecked)
#else
return _buffer.getElement(index)
#endif
}

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

extensionArray:_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?{
@inlinable // FIXME(inline-always)
@inline(__always)
get{
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 }
}
}

extensionArray: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<Array>

 /// The position of the first element in a nonempty array.
 ///
 /// For an instance of `Array`, `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`.
@inlinable
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 or uses a
 /// bridged `NSArray` instance as its storage, in which case writing is
 /// O(*n*), where *n* is the length of the array.
@inlinable
public subscript(index:Int)->Element{
get{
 // This call may be hoisted or eliminated by the optimizer. If
 // there is an inout violation, this value may be stale so needs to be
 // checked again below.
letwasNativeTypeChecked=_hoistableIsNativeTypeChecked()

 // Make sure the index is in range and wasNativeTypeChecked is
 // still valid.
lettoken=_checkSubscript(
 index, wasNativeTypeChecked: wasNativeTypeChecked)

return_getElement(
 index, wasNativeTypeChecked: wasNativeTypeChecked,
 matchingSubscriptCheck: token)
}
_modify{
_makeMutableAndUnique() // makes the array native, too
_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()
}
}

extensionArray:ExpressibleByArrayLiteral{
 // Optimized implementation for Array
 /// 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 = ["cocoa beans", "sugar", "cocoa butter", "salt"]
 ///
 /// - Parameter elements: A variadic list of elements of the new array.
@inlinable
publicinit(arrayLiteral elements:Element...){
self= elements
}
}

extensionArray: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 cacheImages(withNames names: [String]) {
 /// // custom image loading and caching
 /// }
 ///
 /// let namedHues: [String: Int] = ["Vermillion": 18, "Magenta": 302,
 /// "Gold": 50, "Cerise": 320]
 /// let colorNames = Array(namedHues.keys)
 /// cacheImages(withNames: 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=Array(
 _buffer:_Buffer(
 _buffer: s._copyToContiguousArray()._buffer,
 shiftedToStartIndex:0))
}

 /// 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)=Array._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 an Array of `count` uninitialized elements.
@inlinable
internalinit(_uninitializedCount count:Int){
_precondition(count >=0,"Can't construct Array 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 =Array._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
 /// an Array of `count` uninitialized elements.
@inlinable
@_semantics("array.uninitialized")
internalstaticfunc _allocateUninitialized(
 _ count:Int
)->(Array,UnsafeMutablePointer<Element>){
letresult=Array(_uninitializedCount: count)
return(result, result._buffer.firstElementAddress)
}


 /// Returns an Array of `count` uninitialized elements using the
 /// given `storage`, and a pointer to uninitialized memory for the
 /// first element.
 ///
 /// - Precondition: `storage is _ContiguousArrayStorage`.
@inlinable
@_semantics("array.uninitialized")
internalstaticfunc _adoptStorage(
 _ storage:__owned _ContiguousArrayStorage<Element>, count:Int
)->(Array,UnsafeMutablePointer<Element>){

letinnerBuffer=_ContiguousArrayBuffer<Element>(
 count: count,
 storage: storage)

return(
Array(
 _buffer:_Buffer(_buffer: innerBuffer, shiftedToStartIndex:0)),
 innerBuffer.firstElementAddress)
}

 /// Entry point for aborting literal construction: deallocates
 /// an Array containing only uninitialized elements.
@inlinable
internalmutatingfunc _deallocateUninitialized(){
 // Set the count to zero and just release as normal.
 // Somewhat of a hack.
 _buffer.mutableCount =0
}

 //===--- 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.
 ///
 /// Calling the `reserveCapacity(_:)` method on an array with bridged storage
 /// triggers a copy to contiguous storage even if the existing storage
 /// has room to store `minimumCapacity` 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