Home iOS & Swift Books Expert Swift

6
Sequences, Collections & Algorithms Written by Ray Fix

Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as scrambled text.

You can unlock the rest of this book, and our entire catalogue of books and videos, with a raywenderlich.com Professional subscription.

Unlock Now

Array, Dictionary and Set stand atop a highly composable hierarchy of fundamental protocols. These protocols, which include Sequence and Collection among others, capture the essence of these types. The Swift standard library design serves as a case study in Swift generics and protocol-oriented programming that you can learn from and leverage.

The concepts these protocols express are general enough that they appear where you might not expect. For example, the ranges and strides you looked at in the last chapter are sequences and collections, just like arrays are. Although a Range type doesn’t need to allocate memory for elements like an Array does, it shares many of the same capabilities and characteristics. In this chapter, you’ll learn about Sequence, Collection and other related protocols and see how to use them to write generic algorithms that operate across type families.

A family of protocols

By defining primitive notions of a sequence of values, a collection of values and other collection characteristics using protocols, you can write high-performance, generic algorithms. This lets the compiler deal with the specifics of the memory layout that concrete types use to adopt them.

In other languages, the number of implementations for data structures and their algorithms can face what is known as “the M by N problem”. Without a language feature like generics and protocols, the number of implementations for M data structures and N algorithms is the simple product of the two.

Non-generic, non protocol-orientated results in N+M implementations first sorted dropped chunked(by:) Set Array Dictionary Custom code Custom code Custom code Custom code Custom code Custom code Custom code Custom code Custom code Custom code Custom code Custom code N M Custom code QuadTree Custom code Custom code Custom code
M by N implementations

Imagine having to maintain all this code. The above graphic shows just four collection types and four algorithms for a total of sixteen implementations. The truth is that Swift has tons of concrete sequence and collection types such as CollectionOfOne, JoinedSequence, DropWhileSequence and many more.

Thanks to protocols and generics, the number of implementations is only M + N. And that means you never repeat yourself.

sorted first Generic code Generic code dropped Generic code chunked(by:) Generic code Set Array Dictionary QuadTree Generic, protocol-orientated results in only N+M implementations
M plus N implementations

In this world, any type that conforms to the required protocols gets all the algorithm implementations generated on-demand for free. The compiler uses the protocol witness table of protocol declaration to implement function definitions. It can also create specializations for particular concrete types as an optimization. Although there’s programmer complexity cost in knowing about these fundamental protocol types, this knowledge pays for itself handily, as you’ll see.

Sequences and collections

To take full advantage of the system, you need to become familiar with the protocols involved with sequences and collections. Here’s what the hierarchy looks like:

Yep jipjimi uhoculzl Dicioycu Ucbomq zb atnur Wavvijpuet Oqoxudias lsoso OzerogodYwobodev Xhayco utokoqlg BotowreWirvepniop Dabteyv, veyhdofp vmojexfit WadorebmoisobNupdipjiiq Znuvhu fexpeydan NuhnuZektitousgaRobbuvneil Ulocz Ghtumt ehs Wircwgaxy NtkigrBtoraciy Cizvah uxlibv cpadursez MenkomIdpenmJuycahweur xakbb
Fuwuovwo mppey frogiwim daolovydr

Iterators and sequences

Create a custom type that counts down to zero when you loop over it with a for statement. Open the Countdown starter playground for this chapter and add the following:

struct CountdownIterator: IteratorProtocol {
  var count: Int
  mutating func next() -> Int? {
    guard count >= 0 else {  // 1 
      return nil
    }
    defer { count -= 1 }     // 2
    return count
  }
}

struct Countdown: Sequence {
  let start: Int
  func makeIterator() -> CountdownIterator {
    CountdownIterator(count: start)
  }
}

for value in Countdown(start: 5) {
  print(value)
}

StrideThrough and StrideTo

The previous section might have seemed like a lot of code for the job. Yes, there are simpler ways of accomplishing the countdown task. For example, you could have used a simple StrideThrough type, which you create by calling the stride function you saw in the last chapter. Add this to the playground:

print("---")
for value in stride(from: 5, through: 0, by: -1) {
  print(value)
}
print("---")
for value in stride(from: 5, to: -1, by: -1) {
  print(value)
}

UnfoldFirstSequence and UnfoldSequence

The Swift standard library functions sequence(first:next:) and sequence(state:next:) let you define custom sequences without needing to define a new sequence type (and iterator). Try it out by adding this to the end of your playground:

let countDownFrom5 = sequence(first: 5) { value in
  value-1 >= 0 ? value-1 : nil
}
print("---")
for value in countDownFrom5 {
  print(value)
}

let countDownFrom5State = sequence(state: 5) { (state: inout Int) -> Int? in
  defer { state -= 1 }
  return state >= 0 ? state : nil
}
print("---")
for value in countDownFrom5State {
  print(value)
}

Type erasure with AnySequence

To tame complexity, you’ll often want to hide type details of a sequence from users (and yourself). It would be ideal to return an opaque return type, such as some Sequence, from your function. However, opaque return types don’t currently let you constrain associated types, such as the Element, so unfortunately this doesn’t work. But there’s still a way. Hide these unimportant type details and keep your interface clean with the type erasure AnySequence.

extension Sequence {
  func eraseToAnySequence() -> AnySequence<Element> {
    AnySequence(self)
  }
}

let seq = countDownFrom5State.eraseToAnySequence()
print("---")
for value in seq {
  print(value)
}
print(type(of: countDownFrom5State))
print(type(of: seq))

Implementing Sequence with AnySequence and AnyIterator

In the example above, you defined a sequence and then type-erased it, but AnySequence also gives you an initializer to do both in one go. Add this:

let anotherCountdown5 = AnySequence<Int> { () -> AnyIterator<Int> in
  var count = 5
  return AnyIterator<Int> {
    defer { count -= 1}
    return count >= 0 ? count : nil
  }
}
print("---")
for value in anotherCountdown5 {
  print(value)
}

Exercises

Answers to exercises, as always, are in the final download materials. For best results, don’t peek — try it yourself first.

Collections

Collections build on top of sequences and feature an additional guarantee that you can revisit elements. To visit an element, all you need is an index that can access an element in constant time O(1). This complexity guarantee is important because many other algorithms rely on this base level of performance to guarantee their own performance.

A FizzBuzz collection

Like sequences, an excellent way to learn about collections is to create a simple one yourself. Looking at all the protocol requirements of Collection makes creating one seem a daunting task. However, because most of the API has good default protocol implementations, it’s pretty straightforward. In some ways, it’s easier to create a collection than to create a sequence from scratch. What’s more, because Collection is-a Sequence, you get all the sequence functionality for free. You’ll use FizzBuzz to see this in action.

struct FizzBuzz: Collection {
  typealias Index = Int

  var startIndex: Index { 1 }
  var endIndex: Index { 101 }
  func index(after i: Index) -> Index { i + 1 }

  // .... subscript with index ....

}

subscript (index: Index) -> String {
  precondition(indices.contains(index), "out of 1-100")
  switch (index.isMultiple(of: 3), index.isMultiple(of: 5)) {
  case (false, false):
    return String(index)
  case (true, false):
    return "Fizz"
  case (false, true):
    return "Buzz"
  case (true, true):
    return "FizzBuzz"
  }
}

let fizzBuzz = FizzBuzz()
for value in fizzBuzz {
  print(value, terminator: " ")
}
print()

let fizzBuzzPositions = 
  fizzBuzz.enumerated().reduce(into: []) { list, item in
    if item.element == "FizzBuzz" {
      list.append(item.offset + fizzBuzz.startIndex)
    }
  }

print(fizzBuzzPositions)

BidirectionalCollection

Because you only implemented Collection conformance, the standard library algorithms only know how to walk forward through your collection. To see this, add some debug printing to your previous implementation of index(after:):

func index(after i: Index) -> Index {
  print("Calling \(#function) with \(i)")
  return i + 1
}

print(fizzBuzz.dropLast(40).count)

extension FizzBuzz: BidirectionalCollection {
  func index(before i: Index) -> Index {
    print("Calling \(#function) with \(i)")
    return i - 1
  }
}

RandomAccessCollection

You can eliminate all the extra traversing calls by making FizzBuzz a random access collection. Add this to your playground:

extension FizzBuzz: RandomAccessCollection {
}

MutableCollection

Because FizzBuzz is not mutable by definition, change gears with another example. Mutable collections allow you to change elements with a subscript setter. MutableCollection implies that items can be swapped and reordered. This operation doesn’t imply a change in the size of the collection.

The rules of Conway’s Life

As a so-called “zero-player” game, the rules of Conway’s Life are simple:

Conway's Life app screenshot
Jagwop'k Lusi ert yfwoobfpuc

Make Bitmap a collection

Open the file Bitmap+Collection.swift and add the following:

extension Bitmap: RandomAccessCollection, MutableCollection {
  @usableFromInline
  struct Index: Comparable {
    @inlinable static func < (lhs: Index, rhs: Index) -> Bool {
      (lhs.row, lhs.column) < (rhs.row, lhs.column)
    }
    var row, column: Int
  }

  // More to come...
}

@inlinable var startIndex: Index {
  Index(row: 0, column: 0)
}

@inlinable var endIndex: Index {
  Index(row: height, column: 0)
}

@inlinable func index(after i: Index) -> Index {
  i.column < width-1 ?
  Index(row: i.row, column: i.column+1) :
  Index(row: i.row+1, column: 0)
}

// More to come...

@inlinable func index(before i: Index) -> Index {
  i.column > 0 ?
    Index(row: i.row,   column: i.column-1) :
    Index(row: i.row-1, column: width-1)
}

// More to come...

@inlinable 
func index(_ i: Index, offsetBy distance: Int) -> Index {
  Index(row: i.row + distance / width, 
        column: i.column + distance % width)
}

@inlinable 
func distance(from start: Index, to end: Index) -> Int {
  (end.row * width + end.column) 
     - (start.row * width + start.column)
}

// More to come...

@inlinable 
func index(of i: Index, rowOffset: Int, columnOffset: Int) -> Index {
  Index(row: i.row + rowOffset, column: i.column + columnOffset)
}

// More to come...

@inlinable func contains(index: Index) -> Bool {
  (0..<width).contains(index.column) &&
   (0..<height).contains(index.row)
}

@inlinable subscript(position: Index) -> Pixel {

  get {
    precondition(contains(index: position), 
                 "out of bounds index \(position)")
    return pixels[position.row * width + position.column]
  }

  set {
    precondition(contains(index: position), 
                 "out of bounds index \(position)")
    pixels[position.row * width + position.column] = newValue
  }
}

Creating the simulation

Implement the simulation using the Bitmap collection. Open LifeSimulation.swift. The model object has three published properties — isRunning, generation and cells — that redraw the user interface every time they change. Add this statement to the end of LifeSimulation’s initializer:

Timer.publish(every: 0.1, on: .main, in: .common)
  .autoconnect()
  .sink { [weak self] _ in
    self?.evolve()
  }
  .store(in: &subscriptions)

func neighborCount(around index: Bitmap<Bool>.Index) -> Int {
  var count = 0
  for rowOffset in -1...1 {
    for columnOffset in -1...1 {
      guard rowOffset != 0 || columnOffset != 0 else {
        continue
      }
      let probe = cells.index(of: index, rowOffset: rowOffset,
                              columnOffset: columnOffset)
      count += cells.contains(index: probe) ?
        (cells[probe] ? 1 : 0) : 0
    }
  }
  return count
}

func evolve() {
  guard isRunning else {
    return
  }
  generation += 1
  let neighbors = cells.indices.map(neighborCount(around:))

  // The core rules of Life.
  zip(cells.indices, neighbors).forEach { index, count in
    switch (cells[index], count) {
    case (true, 0...1):
      cells[index] = false // death by starvation
    case (true, 2...3):
      cells[index] = true  // live on
    case (true, 4...):
      cells[index] = false // death by overcrowding
    case (false, 3):
      cells[index] = true  // birth
    default:
      break // no change
    }
  }

  // automatically stop the simulation if stability is reached
  if previous.contains(cells) {
    isRunning = false
  }
  previous.add(cells)
}

var cellImage: UIImage {
  let pixels = cells.map { $0 ? Self.live : Self.none }
  guard let image = Bitmap(pixels: pixels, width: cells.width)
                      .cgImage else {
    fatalError("could not create a core graphics image")
  }
  return UIImage(cgImage: image)
}

func setLive(row: Int, column: Int) {
  let position = Bitmap<Bool>.Index(row: row, column: column)
  if cells.contains(index: position) {
    cells[position] = true
    previous.reset() // reset automatic stop detection
  }
}
Conway's Life app screenshot
Basbij'v Zati akc hthaiphluj

RangeReplaceableCollection and others

Range replaceable collections allow you to add and remove values from a collection. Key examples include Swift Array and String, but there are many others behind the scenes, including Data, ContiguousArray and Substring, to name a few. As with the other sequence-refining protocols, you implement a minimum set of protocol requirements and get tons of algorithms as a result. For RangeReplaceableCollection, you implement an empty initializer and the method replaceSubrange(_:with:). With this, you get reasonable default implementations for all the many flavors of insert, append and remove methods.

Subsequences and slices

It’s common to want to deal with a subset of a sequence or collection. The Collection protocol defines a default associated type this way:

associatedtype SubSequence: Collection = Slice<Self> where  // 1
       Self.Element == Self.SubSequence.Element,            // 2
       Self.SubSequence == Self.SubSequence.SubSequence     // 3

let slice = fizzBuzz[20...30]
slice.startIndex
slice.endIndex
slice.count
for item in slice.enumerated() {
  print("\(item.offset):\(item.element)", terminator: " ")
}

let sliceOfSlice = slice[22...24]
sliceOfSlice.startIndex                // value of 22
sliceOfSlice[sliceOfSlice.startIndex]

Memory management

Slices don’t allocate new memory but reference the memory of the original collection. This reference means they’re cheap O(1) to create because they don’t copy elements and can be used to construct efficient, generic algorithms.

let numbers = Array(0..<100)
let upperHalf = numbers[(numbers.count/2)...]
let newNumbers = Array(upperHalf)

The world of lazy evaluation

Collections use slice types to control the timing of allocations and copies into new collections. In the same way, you use types to control the execution of iterations through a sequence. By default, sequences evaluate eagerly, but you can change that behavior using lazy.

let firstThree = FizzBuzz()
  .compactMap(Int.init)
  .filter { $0.isMultiple(of: 2) }
  .prefix(3)

print(firstThree)

let firstThreeLazy = FizzBuzz()
  .lazy
  .compactMap(Int.init)
  .filter { $0.isMultiple(of: 2) }
  .prefix(3)

print(Array(firstThreeLazy))

Generic algorithms

The Swift standard library contains a bevy of algorithms that automatically apply to sequences and collections that meet the appropriate requirements. For example, first, forEach, map, reduce, sort and zip are standard library algorithms.

let values: [Int] = [1, 3, 4, 1, 3, 4, 7, 5]

extension Array {
  func chunks(ofCount chunkCount: Int) -> [[Element]] {
    var result: [[Element]] = []
    for index in stride(from: 0, to: count, by: chunkCount) {
      let lastIndex = Swift.min(count, index + chunkCount)
      result.append(Array(self[index ..< lastIndex]))
    }
    return result
  }
}

values.chunks(ofCount: 3)

extension Collection {
  func chunks(ofCount chunkCount: Int) -> [SubSequence] {
    var result: [SubSequence] = []
    result.reserveCapacity(count / chunkCount 
                           + (count % chunkCount).signum())
    var idx = startIndex
    while idx < endIndex {
      let lastIndex = index(idx, offsetBy: chunkCount, 
                            limitedBy: endIndex) ?? endIndex
      result.append(self[idx ..< lastIndex])
      idx = lastIndex
    }
    return result
  }
}

values.chunks(ofCount: 3)
Array(FizzBuzz().chunks(ofCount: 5).last!)
"Hello world".chunks(ofCount: 2)

Key points

The Swift standard library’s sequence and collection protocols fully leverage the generic system to make a consistent and predictable (and incredible) programming model. Here are some key points to take away:

Where to go from here?

The more you write code, the more you start seeing algorithms. There’s a spectacular WWDC talk by Dave Abrahams, called Embracing Algorithms (https://apple.co/2NHyCcG), that you should watch if you haven’t already. In it, he makes a compelling case that you look hard at all your for loops and try to replace them with named algorithms.

7. Strings 5. Numerics & Ranges

Have a technical question? Want to report a bug? You can ask questions and report bugs to the book authors in our official book forum here.

Have feedback to share about the online reading experience? If you have feedback about the UI, UX, highlighting, or other features of our online readers, you can send them to the design team with the form below:

© 2021 Razeware LLC

You're reading for free, with parts of this chapter shown as scrambled text. Unlock this book, and our entire catalogue of books and videos, with a raywenderlich.com Professional subscription.

Unlock Now

To highlight or take notes, you’ll need to own this book in a subscription or purchased by itself.

Read for Free with a Subscription

Buy this book for $59.99