Building a Custom Collection with Protocols in Swift

Enforcing Non-destructive Iteration

One caveat: Sequence does not require conforming types to be non-destructive. This means that after iteration, there’s no guarantee that future iterations will start from the beginning. That’s a huge issue if you plan on iterating over your data more than once.

To enforce non-destructive iteration, your object needs to conform to the Collection protocol.

Collection inherits from Indexable and Sequence.

The main difference is that a collection is a sequence you can traverse multiple times and access by index.

You’ll get many methods and properties for free by conforming to Collection. Some examples are:

• isEmpty: Returns a boolean indicating if the collection is empty or not.
• first: Returns the first element in the collection.
• count: Returns the number of elements in the collection.

There are many more available based on the type of elements in the collection. Check them out in Apple’s documentation on the Collection Protocol.

Grab your Bag and adopt these protocols!

Adopting the Sequence Protocol

The most common action performed on a collection type is iterating through its elements. For example, add the following to the end of the playground:

for element in shoppingCart {
  print(element)
}

As with Array and Dictionary, you should be able to loop through a Bag. This won’t compile because currently the Bag type doesn’t conform to Sequence.

Time to fix that now.

Conforming to Sequence

Add the following just after the ExpressibleByDictionaryLiteral extension:

extension Bag: Sequence {
  // 1
  typealias Iterator = DictionaryIterator<Element, Int>

  // 2
  func makeIterator() -> Iterator {
    // 3
    return contents.makeIterator()
  }
}

There’s not too much needed to conform to Sequence. In the code above, you:

1. Create a typealias named Iterator as DictionaryIterator. Sequence requires this to know how you iterate your sequence. DictionaryIterator is the type that Dictionary objects use to iterate through their elements. You’re using this type because Bag stores its underlying data in a Dictionary.
2. Define makeIterator() as a method that returns an Iterator for stepping through each element of the sequence.
3. Return an iterator by delegating to makeIterator() on contents, which itself conforms to Sequence.

That’s all you need to make Bag conform to Sequence!

You can now iterate through each element of a Bag and get the count for each object. Add the following to the end of the playground after the previous for-in loop:

for (element, count) in shoppingCart {
  print("Element: \(element), Count: \(count)")
}

Press Command-Shift-Enter to run the playground. Open the playground console and you’ll see the printout of the elements and their count in the sequence.

Viewing Benefits of Sequence

Being able to iterate through a Bag enables many useful methods implemented by Sequence. Add the following to the end of the playground to see some of these in action:

// Find all elements with a count greater than 1
let moreThanOne = shoppingCart.filter { $0.1 > 1 }
moreThanOne
precondition(
  moreThanOne.first!.key == "Banana" && moreThanOne.first!.value == 2,
  "Expected moreThanOne contents to be [(\"Banana\", 2)]")

// Get an array of all elements without their counts
let itemList = shoppingCart.map { $0.0 }
itemList
precondition(
  itemList == ["Orange", "Banana"] ||
    itemList == ["Banana", "Orange"],
  "Expected itemList contents to be [\"Orange\", \"Banana\"] or [\"Banana\", \"Orange\"]")

// Get the total number of items in the bag
let numberOfItems = shoppingCart.reduce(0) { $0 + $1.1 }
numberOfItems
precondition(numberOfItems == 3,
  "Expected numberOfItems contents to be 3")

// Get a sorted array of elements by their count in descending order
let sorted = shoppingCart.sorted { $0.0 < $1.0 }
sorted
precondition(
  sorted.first!.key == "Banana" && moreThanOne.first!.value == 2,
  "Expected sorted contents to be [(\"Banana\", 2), (\"Orange\", 1)]")

Press Command-Shift-Enter to run the playground and see these in action.

These are all useful methods for working with sequences — and you got them practically for free!

Now, you could be content with the way things are with Bag, but where's the fun in that?! You can definitely improve the current Sequence implementation.

Improving Sequence

Currently, you're relying on Dictionary to handle the heavy lifting for you. That's fine because it makes creating powerful collections of your own easy. The problem is that it creates strange and confusing situations for Bag users. For example, it's not intuitive that Bag returns an iterator of type DictionaryIterator.

But Swift comes to the rescue again! Swift provides the type AnyIterator to hide the underlying iterator from the outside world.

Replace the implementation of the Sequence extension with the following:

extension Bag: Sequence {
  // 1
  typealias Iterator = AnyIterator<(element: Element, count: Int)>

  func makeIterator() -> Iterator {
    // 2
    var iterator = contents.makeIterator()

    // 3
    return AnyIterator {
      return iterator.next()
    }
  }
}

In this revised Sequence extension, you:

1. Define Iterator as conforming to AnyIterator instead of DictionaryIterator. Then, as before, you create makeIterator() to return an Iterator.
2. Create iteratorby calling makeIterator() on contents. You'll need this variable for the next step.
3. Wrap iterator in a new AnyIterator object to forward its next() method. The next() method is what is called on an iterator to get the next object in the sequence.

Press Command-Shift-Enter to run the playground. You'll notice a couple of errors:

Before, you were using the DictionaryIterator with tuple names of key and value. You've hidden DictionaryIterator from the outside world and renamed the exposed tuple names to element and count.

To fix the errors, replace key and value with element and count respectively. Run the playground now and your precondition blocks will pass just as they did before.

Now no one will know that you're just using Dictionary to the hard work for you!

It's time to bring your Bag home. OK, OK, collect your excitement, it's Collection time! :]

Adopting the Collection Protocol

Without further ado, here's the real meat of creating a collection: the Collection protocol! To reiterate, a Collection is a sequence that you can access by index and traverse multiple times.

To adopt Collection, you'll need to provide the following details:

• startIndex and endIndex: Defines the bounds of a collection and exposes starting points for transversal.
• subscript (position:): Enables access to any element within the collection using an index. This access should run in O(1) time complexity.
• index(after:): Returns the index immediately after the passed in index.

You're only four details away from having a working collection. You got this; it's in the Bag!

Add the following code just after the Sequence extension:

extension Bag: Collection {
  // 1
  typealias Index = DictionaryIndex<Element, Int>

  // 2
  var startIndex: Index {
    return contents.startIndex
  }

  var endIndex: Index {
    return contents.endIndex
  }

  // 3
  subscript (position: Index) -> Iterator.Element {
    precondition(indices.contains(position), "out of bounds")
    let dictionaryElement = contents[position]
    return (element: dictionaryElement.key,
      count: dictionaryElement.value)
  }

  // 4
  func index(after i: Index) -> Index {
    return contents.index(after: i)
  }
}

This is fairly straightforward. Here, you:

1. Declare the Index type defined in Collection as DictionaryIndex. You'll pass these indices through to contents.
2. Return the start and end indices from contents.
3. Use a precondition to enforce valid indices. You return the value from contents at that index as a new tuple.
4. Return the value of index(after:) called on contents.

By simply adding these properties and methods, you've created a fully functional collection!