Skip to content →

extension Queue: SequenceType

Previously, I presented a linked-list-based Queue class in the context of a discussion around Automatic Reference Counting (ARC). Here I extend that class to conform to the SequenceType protocol, and then add some bonus initializers that mirror those given for Swift’s collections.

In simplest terms, it is the SequenceType protocol that allows us to iterate over the elements in the Queue:

for element in queue {
  // do something with element
}

But that’s just the beginning. Taking a look at the Appe documentation and this excellent post by Nate Cook on the Swift Collection Protocols, we find that because of this iterability, we gain significant functionality for free, a subset of which includes the likes of enumerate, map–filter–reduce, reverse, sort, and so on. Good stuff!

Now, a SequenceType makes no guarantees as to whether the sequence is consumed, so if we were interested only in iteration and didn’t care about that (or perhaps wanted it to be consumed), we could destructively iterate like so:

while let element = queue.dequeue() {
  // do something with element
}

However, our Queue is constructed in such a way that it need not be consumed on iteration.

Generator

So let’s give Queue an iterator (generator in Swift vernacular) and declare its conformance to the SequenceType protocol. There’s not much to it, at least as far as Queue is concerned:

extension Queue: SequenceType {

  /**
   Returns a `SequenceType` generator for iterating over the queue.
   */
  func generate() -> QueueGenerator<T> {
    return QueueGenerator(queue: self)
  }
}

Beyond that, we need only define the QueueGenerator returned by generate(). It takes our Queue object and, with its front property and each node’s next property, non-destructively iterates over the elements in the queue:

/**
 The generator by which `Queue` conforms to `SequenceType`.
 */
struct QueueGenerator<T>: GeneratorType {
  
  /// The queue being iterated over.
  var queue: Queue<T>
  
  /// The current node.
  var node: QueueNode<T>?
  
  /**
   Initializes iteration at the front of the given `queue`.
   */
  init(queue: Queue<T>) {
    self.queue = queue
    node = queue.front
  }
  
  /**
   Returns the next element in the queue, or `nil` if the queue is empty or all nodes have been iterated.
   */
  mutating func next() -> T? {
    let element = node?.element
    node = node?.next
    return element
  }
}

Notice that like the previously defined dequeue() method, the next() method is not returning a queue node, but rather the element of type T that is wrapped by the node.

And that’s all there is to for SequenceType conformance!

Initializers

But before we move on, let’s go back to our original Queue definition and drop in some initializers that allow Queue construction to work like Swift’s own Array and Set types:

class Queue<T>: SequenceType, ArrayLiteralConvertible { // continued

  /**
   Construct an empty queue.
   */
  init() { }
  
  /**
   Construct an instance containing `elements`.
   */
  required init(arrayLiteral elements: T...) {
    for element in elements {
      enqueue(element)
    }
  }
  
  /**
   Construct an instance from an arbitrary sequence with elements of type `Element`.
   */
  init<S: SequenceType where S.Generator.Element == T>(_ sequence: S) {
    for element in sequence {
      enqueue(element)
    }
  }
}

The first constructor was implied by the previous omission of any initializers, but now that we’ve added the other two, we must explicitly define it. However, because Queue consists only of optional properties, they are automatically initialized to nil. Since this is the “default” state, there is nothing for it to initialize.

The second initializer uses the Swift ellipses syntax to indicate a comma-separated list of literal values, which it converts into an Array. This is all that’s needed for ArrayLiteralConvertible protocol conformance, so I add that to the class. This in turn necessitates the use of the required modifier on the initializer, as the initializer is required by the protocol.

Finally, the third initializer allows us to build a queue from any SequenceType, such as an Array, Set or Dictionary. The syntax used here is that of the generic parameter clause, which adds a constraint to the Queue‘s generic argument T. That constraint says S conforms to the SequenceType protocol and the associated type S.Generator.Element is of type T. In other words, we can pass in any sequence of type T elements.

Here’s what those initializers look like in application.

let array = [3, 7, 2, 9]
let set = Set(arrayLiteral: 3, 7, 2, 9)
let dict = ["A": 3, "B": 7, "C": 2, "D": 9]
let queue1 = Queue<Int>()
let queue2 = Queue(arrayLiteral: 3, 7, 2, 9)
let queue3 = Queue(array)
let queue4 = Queue(set)
let queue5 = Queue(dict.values)
let queue6 = Queue(queue2)

Some points of note:

  • We’re able to drop the <Int> type specification on any but the first initializer, thanks to Swift’s type inference.
  • We can now initialize one Queue with another.
  • Only the Queue and Array types maintain their order as initialized, so the arrangement of the elements for queue4 and queue5 are not necessarily 3, 7, 2 and 9.

Published in Algorithms Series Swift Language

Comments

Leave a Reply

Your email address will not be published.