Arrays

An array is an ordered collection of elements of the same type, and they are used for pretty much anything that requires storing things in a certain order, such as the contents of lists in apps. It works like similar types in other languages.

Working with Arrays

Follow these steps to work with arrays:

We can create an array like this:
```
let a = [0,1,2,3,4] // array literal
```
We can join two arrays like this:
```
var b = a + [5,6]   // join two arrays
```

We can have a repeated value like this:

let c = Array(repeating: 4.1, count: 3) // repeat one value

To create an array from any sequence, we can do this:

// create from any Sequence (a String is a Sequence of Character)
var d = Array("The ☀ and 🌙 ")

To append a value to an array, use this:
```
b.append(10) // append one element
```
To append an entire array, use this:
```
b += a // append an array
```
Another way to append an array is by using this:
```
b.append(contentsOf: a) // append an array
```
To count the length of an array, we can do this:
```
b.count // the length of the array
```

To assign a value in the array, we can do this:

b[0] // 0
b[0] = 9
b[0] // 9
for nr in b {
  // do something with 'nr'
}

Here are their abilities, represented by some of the protocols they conform to:

A BidirectionalCollection can go backwards from any index (except for the first one).
A MutableCollection can replace any element with a different one, but can't necessarily change the length of the collection.
A RangeReplaceableCollection can add and remove elements. You can also create an empty one.
RandomAccessCollection does not offer any new methods over BidirectionalCollection, but it guarantees that accessing any part of the collection takes the same amount of time, no matter how big it is. Array can do this because all of its elements are the same size, so it can instantly calculate where they are in memory.

Index

The index type of an Array is Int (integer), and its startIndex is always 0. Its endIndex is the same as the length of the array. You can think of an index as something that's pointing to the space between elements, right before the element it refers to. Here is an array of characters:

var characters = Array("The ☀ and 🌙")

endIndex points to the position after the end, so if you ever try to access an element at endIndex with characters[characters.endIndex] (or with any other invalid index), your program will crash. If an array is empty, startIndex and endIndex are both 0.

Utilizing Common Operations with Index

Common operations which are used with index are shown here:

To read an element at a particular index, use this:
```
characters[2] // read element at index 2 ("e")
```
To change the element at a particular index, use this:
```
characters[2] = "a" // change element at index 2
```

To remove and return an element at a particular index, use this:

let removed = characters.remove(at: 8) // remove and return element

To insert an element at a particular index, use this:
```
characters.insert("i", at: 7) // insert element
```

To insert a collection of elements at a particular index, use this:

characters.insert(contentsOf: "t the", at: 9) // insert collection of elements

To print all of the characters, use this:

print(characters)
// ["T", "h", "a", " ", "☀", " ", "a", "i", "n", "t", " ", "t", "h", "e", " ", " 🌙 "]

Note

Many collections use their own custom index type instead of Int, and even those that use Int do not necessarily have a startIndex that is always 0. It is therefore recommended to always use an array's startIndex instead of 0. This also makes the code clearer.

As with all indices, note that they may become invalid or point to the wrong element if the Array is mutated after they are created. To check if an index can still be used, all collections have an indices property, which is a collection of all the current indices:

characters.indices.contains(index)

ArraySlice

All sequences have a SubSequence, a type which represents a subrange of its elements. The Array.SubSequence is an ArraySlice:

It has the same heritage and API as Array. It keeps a reference to the array it was created from, and its startIndex and endIndex represent the subrange within the array:

let characters = Array("The ☀ and 🌙 ")
let slice = characters[4..<9]
print(slice) // ["☀", " ", "a", "n", "d"]

This allows us to have just one copy of a big array in memory, and have as many slices as there are views on it. However, each slice holds on to the array, so if you want to keep a slice around for a while, it is recommended to convert it to an array (using Array(slice)). This will copy the elements of the slice to its own array and release the reference, allowing the big array to be freed if nothing else holds on to it.

If you mutate the array or the slice after the slice has been created, a copy will be made automatically and the change will not be reflected in the other.

Creating Slices

Slices can be created in different ways, as shown here:

To create a slice with the first three elements, use this:
```
characters.prefix(3) // the first three elements
```

To create a slice with all the elements before the first space, use this:

characters.prefix(while: {$0 != " "}) // all elements before the first space

To create a slice with the last two elements, use this:
```
characters.suffix(2) // the last two elements
```

To create a slice with elements from 4, use this:

characters.suffix(from: 4) // elements from number 4 and out

Creating Slices Using Range Operators

We will now see how to use range operators to create slices:

To create a slice from elements 2 to 4 inclusive, use this:
```
characters[2...4] // elements 2 to 4 inclusive
```
To create a slice from element 3 up to, but not including 6, use this:
```
characters[3..<6] // elements 3 up to, but not including 6
```
To create a slice from element 3 to the end, use this:
```
characters[3...] // from element 3 to the end
```
To create a slice from the beginning up to and including element 5, use this:
```
characters[...5] // from the beginning up to and including 5
```
To create a slice from the beginning up to but not including element 5, use this:
```
characters[..<5] // from the beginning up to, but not including 5
```

That ends our look at arrays. Next, we'll work through an activity that solidifies our understanding of arrays and its related concepts.

Activity A: Working with Arrays

Many operations on arrays can be done far more efficiently if the array is sorted. We will add methods that take advantage of this for insertion, finding the index of the first or last occurrence of an element, and checking if the array contains an element.

We will just add methods to an array in an extension, but ideally this should be its own type with an internal array so that we can guarantee that it is always sorted. Check out ole/SortedArray (https://github.com/ole/SortedArray) for an example of this.

To perform basic array operations such as, inserting elements into an array and searching an element in an array.

Open the CollectionsExtra Xcode project, and go to SortedArray.swift.

Create an extension to Range to find the middle of it. This will be used with the indices of the array:

public extension Range where Bound == Int {
  /// The value in the middle of this range. Returns nil if the range is empty.
  var middle: Int? {
    guard !isEmpty else { return nil }
    return lowerBound + count / 2
  }
}

We will assume that the array has been sorted using the < operator (ascending), and we will assure that elements can be used with this operator by constraining the extension to arrays with elements that adopt the Comparable protocol. This also means they can be used with >, ==, !=, >=, and <=:
```
extension Array where Element: Comparable {
```

Next, we need to find the insertion point if we were to insert an element into the sorted array. We can use this for insertion and checking if the array contains a specific element. This is a standard binary search, implemented with recursion:

  /// The index to use if you were to insert this element into a sorted array.
  ///
  /// - Parameters:
  ///   - element: The element to potentially insert.
  ///   - range: The range to search in.
  /// - Note: If the element already occurs once or more, the index to one of those will be returned.
  func insertionIndex(for element: Element, in range: Range<Index>) -> Index {
    guard let middle = range.middle else { return range.upperBound }
    if self[middle] < element {
      return insertionIndex(for: element, in: index(after: middle)..<range.upperBound)
    } else if self[middle] > element {
      return insertionIndex(for: element, in: range.lowerBound..<middle)
    }
    return middle
  }

Note that when returning middle, we do not check if the element in that position is the one we are searching for. This is because the Comparable protocol demands that if an element is neither bigger than or smaller than another element, then they must be equal.

The range will normally start as the entire array.

Inserting an element is now very simple:

  /// Inserts the element in the correct position in a sorted array.
  ///
  /// - Parameter element: The element to insert.
  /// - Returns: The index where the element was inserted.
  @discardableResult
  public mutating func sorted_insert(_ element: Element) -> Index {
    let index = insertionIndex(for: element, in: startIndex..<endIndex)
    self.insert(element, at: index)
    return index
  }

When checking if the array contains a specific element, we can first get the insertion index, check that it is not the endIndex (if the element does not exist and is larger than all the other elements), and see if the element at the index is the one we are searching for:
```
   /// Checks if a sorted array contains an element.
  public func sorted_contains(_ element: Element) -> Bool {
    let index = insertionIndex(for: element, in: startIndex..<endIndex)
    return (index != endIndex) && (self[index] == element)
  }
```
When searching for the first occurrence of an element in the array, we can't use insertionIndex. This is because if the element occurs more than once, it may return the index to any of those occurrences. Instead, we will use a slightly modified version (https://github.com/raywenderlich/swift-algorithm-club/blob/master/Count%20Occurrences/README.markdown):
```
  /// The index of the first occurrence of this element in a sorted array.
  ///
  /// - Parameters:
  ///   - element: The element to search for.
  ///   - range: The range to search within.
  /// - Returns: The index, or nil if not found.
  public func sorted_index(of element: Element, in range: Range<Index>? = nil) -> Index? {
    let range = range ?? startIndex..<endIndex
    guard let middle = range.middle else {
      let index = range.upperBound
      return (self.indices.contains(index) && self[index] == element) ? index : nil
    }
    if self[middle] < element {
      return sorted_index(of: element, in: index(after: middle)..<range.upperBound)
    }
    return sorted_index(of: element, in: range.lowerBound..<middle)
  }
```
The main difference is that we only check if the element in the middle is less than what we are searching for, not both less than and greater than, like in insertionIndex. We can do this because, in a sorted array, all equal elements are grouped together. Even if middle happens to point to an equal element, there may still be more of those to the left, so we continue searching there. If there aren't, we still end up with the index in the correct place.
Since we are using properties of self for the default value of the range parameter, we cannot provide them in the function header. Instead, we set the default value to nil, and then create a new local variable called range which is set to the default value startIndex..<endIndex if no other value was provided when the function was called.

The code for finding the last index of an element is almost identical:

  /// The index of the last occurrence of this element in a sorted array.
  ///
  /// - Parameters:
  ///   - element: The element to search for.
  ///   - range: The range to search within.
  /// - Returns: The index, or nil if not found.
  public func sorted_lastIndex(of element: Element, in range: Range<Index>? = nil) -> Index? {
    let range = range ?? startIndex..<endIndex
    guard let middle = range.middle else {
      let index = self.index(before: range.upperBound)
      return (self.indices.contains(index) && self[index] == element) ? index : nil
    }
    if self[middle] > element {
      return sorted_lastIndex(of: element, in: range.lowerBound..<middle)
    }
    return sorted_lastIndex(of: element, in: index(after: middle)..<range.upperBound)
  }
}

Here, we check if middle points to an element that is greater than what we are searching for. If it isn't, we go to the right. When we have finally found an index, we use the index before it.

Go to SortedArrayTests.swift, uncomment the unit tests, and run them all.