Skip to content →

Tag: Swift 2.2

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.
Leave a Comment

A Generic Swift Queue and ARC

In my current project, I set off to implement a generic queue in Swift, and settled on the use of a linked list for doing so, where my queue is a collection of singly linked nodes. As it turned out, this ended up being fertile ground for illustrating Swift’s use of Automatic Reference Counting (ARC) for memory management, something I take on in this post.

For the visual learners, here is an illustration to assist the discussion, courtesy of Paper by 53 and my iPad Pro (with Apple Pencil, of course):

IMG_0040

The top row represents three people waiting in line at Walmart customer service (who hasn’t been there?). The second row shows the first person has been helped (dequeued), leaving two. And the third row shows two new customers have arrived (enqueued), eager to make their returns, before anyone else has been helped. The orange numbers correspond to reference counts (more on that in a moment).

Queue Node

So to begin, let’s take a look at the building block of the queue, the node (represented by the circles in the diagram):

/**
 The component of a queue that provides the queue's content and sequence.
 */
class QueueNode<T> {

  /// The data element stored in the queue.
  var element: T

  /// The node that is "next in line", or `nil` if there is no subsequent node.
  var next: QueueNode?

  /**
   Wraps the given `element` into a node, leaving `next` set to `nil`.
   */
  init(element: T) {
    self.element = element
  }
}

Being part of a linked list, it is necessary for the node to be a class, as linked lists rely on reference pointers, and only Swift classes—as reference types—can be “pointed” to. (In contrast, any assignment of a structure or enumeration stores a copy of the object in the receiving variable, property, or parameter.)

Queue

Next, let’s begin taking a look at the class that takes the QueueNode building block and with it forms a fully functional Queue data structure:

/**
 A generic collection that provides standard enqueueing and dequeuing functionality.
 As elements are enqueued, they are conceptually added to "the back of the line;" 
 as they are dequeued, they are removed from "the front of the line." 
 */
class Queue<T> {

  /// The first enqueued node or that following the last dequeued node.
  private var front: QueueNode<T>?

  /// The last enqueued node.
  private var back: QueueNode<T>?

  /// The number of elements in the queue.
  private(set) var count = 0
  
  /// True if there are no elements in the queue, false otherwise.
  var isEmpty: Bool {
    return count == 0
  }
 

I want to interrupt here to point out that the class properties front and back defined on lines 9 and 12 are effectively pointers, as is the function variable node on line 28 below (reference the diagram).

  /**
   Adds the given `element` to the back of the queue.
    - complexity: O(1)
   */
  func enqueue(element: T) {
    
    let node = QueueNode<T>(element: element)
    
    // First node
    if front == nil {
      front = node
      back = node
    }
      
    // Subsequent nodes
    else {
      back!.next = node
      back = node
    }

    count += 1
  }
 

It is on line 28 that this class allocates memory for, creates, initializes and assigns a reference to a new QueueNode object (all done behind the scenes by Swift). In accordance with ARC, as long as this object has a property, variable or parameter pointing to it, it will remain allocated. This node is short-lived, though, so the only potential direct references held by Queue are front and back. It is the nodes themselves that maintain the next references keeping the chain of nodes alive (again, the diagram).

  /**
   Removes and returns the element at the front of the queue.
   - complexity: O(1)
   */
  func dequeue() -> T? {
     
    // Queue is empty
    if front == nil { return nil }
     
    // Remove first node/element
    let element = front!.element
    front = front!.next
     
    // Deallocate dequeued back node
    if front == nil {
      back = nil
    }
 
    count -= 1
     
    return element
  }
 

Consider line 56 in dequeue(), where front is reassigned to the object pointed to by its own next property. This leaves the node formerly known as first with nothing referring to it, triggering implicit and immediate deallocation; there’s no need to explicitly deallocate it, such as with a nil assignment.

In contrast, if we have dequeued the last node, we need to explicitly release it by reassigning back to nil (line 60), otherwise back will retain that node until the queue itself is deallocated (at which time it is automatically set to nil).

Automatic Queue Deallocation

In the context of queue deallocation, such as when the reference count for a Queue object drops to zero, front is assigned to nil. When that happens the associated node’s reference count also drops to zero, triggering its deallocation. This causes the setting of the node’s next property to nil, which then decrements its adjacent node’s reference count to zero, thereby triggering that node’s deallocation, and so on. This chain reaction continues until the last node in the linked list is reached.

As discussed in the context of dequeue(), this last node is also pointed to by the queue’s back property, thus preventing its reference count from dropping to zero, and thereby keeping the object alive. It is not until back is set to nil (line 60 above) that the reference count drops to zero and the last node is deallocated.

The process of deallocating the nodes between front and back happens automatically courtesy of ARC memory management built into Swift and Objective-C. You can see it in action by using this script and addition to QueueNode:

class QueueNode<T> { // continued
  deinit {
    print("\(#function)")
  }
}

func testQueue {
  let n = 10
  var queue = Queue<Int>()
  for i in 1...n {
    queue.enqueue(i)
  }
}
testQueue()
print("done")

Once testQueue() exits, you’ll see its queue variable is automatically deallocated as described, which in this case would result in 10 debugger console output lines that read “deinit” before “done” appears.

Large Queues

Now you might find that for large queues, trouble ensues in the form of a EXC_BAD_ACCESS runtime error. I found taking the reigns on deallocating the individual QueueNodes ensured the deallocation of any sized queue works flawlessly.

Returning to our Queue definition, this is a simple matter of adding a deinit method that calls upon a removeAll() method familiar to users of Swift’s collection types:

  /**
   Explicitly deinitializes all enqueued nodes.
   - complexity: O(n)
   */
  deinit {
    removeAll()
  }

  /**
   Removes all elements from the queue.
   - complexity: O(n)
   */
  func removeAll() {
    while front != nil {
      front = front!.next
    }
    back = nil
    count = 0
  }
}

Note we haven’t completely given up on ARC. As it did in line 56 previously, the same implicit deallocation occurs here on line 82: as soon as the front = front!.next assignment is made, the node that was the front node is deallocated. Where we short-circuit the automatic chain-reaction deallocation discussed above is in that front reassignment. Were we to replace lines 81–83 with a simple front = nil, we would be back to the default behavior we had without a deinit method.

And yes, for you lines-of-code hounds out there, I could have written removeAll() as a simple one-liner with the loop while dequeue() != nil { }. I contend, though, the given approach is superior for performance reasons, however negligible. There’s a bit more overhead in calling dequeue() 100 million times, let’s say, than in dereferencing that many nodes directly (in a single test, this amounted to 45 versus 65 seconds…a near 150% increase).

More to Come

That does it for now. In my next post I conform the Queue to SequenceType so it can be iterated with the likes of:

for element in queue {
  // do something with element
}
Leave a Comment

RIP++

When I recently had occasion to “prepare” for Swift 3.0 a third-party library our team is using, it struck me just how useful the C-based post-increment (and decrement) operator is. Consider this simple Swift 2.2 line from that library:

return (String(self.arrayIndex++), JSON(o))

To those not familiar with this post-increment unary operator, the arrayIndex doesn’t get incremented until after it is converted to a String. With the loss of that operator in Swift 3.0, this one-liner grows to this:

let arrayIndexString = String(self.arrayIndex)
self.arrayIndex += 1
return (arrayIndexString, JSON(o))

Can’t say I agree with the stated “disadvantages” of this operator, which appear to focus on a very simplistic use-case that contrasts x += 1 and x++. Sure, in that case, there’s no added utility. And hard to learn? I’ve seen that argument repeated in other “do away with this” arguments; hog wash. Swift contains much more complicated constructs than a post-increment operator!

Alas, I’m a bit late to the party, and the fate of ++ has already been sealed. Thankfully, it’s not “goodbye,” but just “see you later”…when I return to the likes of C++.

Leave a Comment

App State-Change Notifications to Multiple Delegates

In a prior post on Modeling State with Associated Enums, I set up a mechanism for capturing and querying an app’s state, as follows:

AppState.state = .Authentication(.Active)
AppState.state = .DataRetrieval(.Success)
// ...
if AppState.state == .DataRetrieval(.Success) {
  // ...
}

In this post I use the delegate pattern to add state observation by any component of the app that needs to respond to state changes. I begin by defining the delegate protocol:

/**
 An `AppStateDelegate` receives notification when the application's state changes.
 */
protocol AppStateDelegate {

  /// Called when the app state has changed.
  func appStateChanged(state: AppState)

  /// Uniquely identifies the delegate.
  var hashValue: Int { get }
}

The appStateChanged(_:) method will be called any time the state changes (makes sense!). But what about that hashValue on line 11? When it comes to delegates, this is an instance where it is appropriate and, perhaps, necessary to register multiple delegates: there are likely to be multiple places across the app where I need to know about state changes. The hashValue is going to help with that…

My approach for supporting multiple delegates without using NSNotificationCenter is to add to the previously defined AppState enumeration a dictionary of delegates:

enum AppState: Equatable { // excerpt

  /// Delegates registered for `appStateChanged(_:)` notifications.
  private static var delegates = [Int: AppStateDelegate]()
}

(Before getting to the dictionary, note I have chosen to make this and future declarations static. I have done so because, not unreasonably, the state of the app applies to the entire app, and there is only one instance of the app running at a time.)

It is to this AppStateDelegate dictionary that notifications will be made. I have chosen a dictionary here as a meet-me-halfway point between an array and a set. A set would be ideal, but it requires the delegate to conform to the Hashable protocol, something not as easy as it seems, and that I leave for a future exercise. In the meantime, we’ll use the dictionary so as to prevent registration of duplicate delegates.

Delegate registration occurs via the delegate property setter, defined next:

enum AppState: Equatable { // excerpt

  /// Registers the `delegate` with `AppState`.
  /// All delegates are notified upon assignment to `state`. 
  static func addDelegate(delegate: AppStateDelegate) {
    delegates[newValue.hashValue] = newValue
  }
}

The addDelegate(_:) method simply adds the given delegate to the dictionary, relying on the default no-duplicate-keys functionality that comes with a dictionary to ensure no delegate is registered more than once.

A delegate property could be used in lieu of this method, using the setter to make this same dictionary addition, but doing so actually adds a level of unneeded complexity given we’re using multiple delegates: which delegate should the getter return? Using a method avoids that peculiarity.

The dictionary is keyed on the protocol’s hashValue integer. The expectation is any registering delegate itself already conforms to the Hashable protocol (without explicitly requiring such conformance), and thereby has a fitting hashValue implementation that will ensure the uniqueness of the key. If it doesn’t conform, the AppStateDelegate protocol requires a hashValue anyway, so I call it good for now.

With delegates registered, notification is triggered by the following didSet block:

enum AppState: Equatable { // excerpt

  /// The current state of the app. 
  /// Any assigned `AppStateDelegate`s are notified on assignment.
  static var state: AppState = .Ready(false) {
    didSet {
      for delegate in delegates.values {
        delegate.appStateChanged(state)
      }
    }
  }
}

The process of notification is quite simple: call appStateChanged(_:) on each of the delegates in the dictionary. (Note, as explained by the Swift Programming Language Guide, didSet is not called when the value is first initialized.)

Putting all that to use, here is a sample listener implementation that shows registering as a delegate for and receiving app state-change notifications.

import UIKit

class SomeViewController: UIViewController, AppStateDelegate {

  override func viewDidLoad() {
    AppState.delegate = self
  }

  func appStateChanged(state: AppState) {
    if state == .DataRetrieval(.Success) {
      // do something...
    }
  }
}

Note that because a UIViewController already conforms to the Hashable protocol, there is no need to explicitly provide a hashValue implementation. The result? Each time AppState.state is updated, this controller and any other registered delegates are notified via the protocol’s appStateChanged(_:) method.

Leave a Comment

Modeling State with Associated Enums

Shortly after writing a recent post on enums with associated values, I came upon another use case for such: representing transitory app states.

Here is the scenario. I have an app that goes through an authentication process: attempting to authenticate, successfully authenticated, or failed to authenticate. Similarly, upon authentication, it goes through a second series of steps for data retrieval: requesting and receiving the data, data received, or retrieval failed. Finally, book-ending those two processes, the app has a ready state: either it is or it isn’t ready.

Here’s how I represent these states with associated enum values:

enum AppState {

  case Authentication(OperationState)
  case DataRetrieval(OperationState)
  case Ready(bool)

  enum OperationState {
    case Active
    case Success
    case Failure
  }

  static var state: AppState = .Ready(false)
}

First, AppState captures as case statements the two processes for authentication and data retrieval, and the ready state. The associated value for the processes is the nested OperationState enumeration that captures one of the three states of each of those processes: Active, Success, or Failure. The Ready state need only be represented as true or false. It is the static state property on line 13 that allows me to capture any of those mutually exclusive transitory state values for the app.

Now I can establish that app state and test it like so:

AppState.state = .Authentication(.Active)
AppState.state = .DataRetrieval(.Success)

// ...

switch AppState.state {
case .Authentication(let state):
  switch state {
  case .Active:
    break // stand by
  case .Success:
    break // proceed with data retrieval
  case .Failure:
    break // can't retrieve the data
  }
case .DataRetrieval(let state):
  if state == .Success {
    // refresh the table view
  }
case .Ready(let ready):
  if ready { //...
  }
}

There are two types of comparison here: a switch statement and an if statement. Actually, the if statement on line 17 won’t work out of the box. We first need to conform our AppState to the Equatable protocol (if you’re doing this in a playground, it must go above the AppState definition):

func ==(left: AppState, right: AppState) -> Bool {
  switch (left, right) {
  case (.Authentication(let l), .Authentication(let r)): return l == r
  case (.DataRetrieval(let l), .DataRetrieval(let r)): return l == r
  case (.Ready(let l), .Ready(let r)): return l == r
  default: return false
  }
}

enum AppState: Equatable {
  // The external func ==(left:right:) satisfies Equatable
}

The default case is necessary here because we’re not testing every combination of left and right AppStates; with out it, we’d have to be more explicit, adding these cases:

  case (.Ready, .Authentication): return false
  case (.Ready, .DataRetrieval): return false
  case (.Authentication, .Ready): return false
  case (.Authentication, .DataRetrieval): return false
  case (.DataRetrieval, .Ready): return false
  case (.DataRetrieval, .Authentication): return false

In those instances, we’d in effect be comparing apples and oranges, which are not equal; so we return false. And clearly, having a default return value of false in lieu of all those case statements is preferable.

That’s it! In this illustration I employed associated value enums to represent in a very clean, readable way a series of states that various operations of the app can be in.

In a follow-up post I extend this with a delegate pattern for making notifications when the app’s state changes.

Leave a Comment

Nested Enumerations as Dictionary Keys

Type of expression is ambiguous without more context.

This may be an error you have seen before. It apparently occurs in more than one circumstance, this being one example of such:

struct Foo {
  enum Bar {
    case Alpha
    case Beta
  }
}
var outer = [Foo.Bar: String]() // Error

There are three ways I found to get that enum to work as a dictionary key. The first is to use it within the enclosing type:

struct Foo {
  enum Bar {
    case Alpha
    case Beta
  }
  var inner = [Bar: String]()
}

That’s hardly a solution, however, if you need a dictionary outside the context of Foo. What’s more, this usage doesn’t align with the Swift Programming Language Guide‘s statement:

To use a nested type outside of its definition context, prefix its name with the name of the type it is nested within: let heartsSymbol = BlackjackCard.Suit.Hearts.rawValue.

The second workaround is to move the Bar enum outside of Foo:

enum Bar {
  case Alpha
  case Beta
}

var dict = [Bar: String]()

Unfortunately, this forces Bar to lose its Foo context, which is the Guide’s primary stated purpose for having nested types in the first place:

Enumerations are often created to support a specific class or structure’s functionality. Similarly, it can be convenient to define utility classes and structures purely for use within the context of a more complex type. To accomplish this, Swift enables you to define nested types, whereby you nest supporting enumerations, classes, and structures within the definition of the type they support.

The third workaround is less a workaround than a solution, and that is to use the full notation for a dictionary declaration:

struct Foo {
  enum Bar: String {
    case Alpha
    case Beta
  }
}
var outer = Dictionary<Foo.Bar, String>() // Works!

Why the abbreviated syntax leads to an ambiguous type reference remains unclear, but using the full syntax does the trick.

Leave a Comment

Naming Swift Methods

How to name methods in Swift is a fairly common discussion point with my team, and one of repeated frustration for those members new to iOS development. Largely at issue is named parameters: that we use them at all (what is their value?), and how to use them.

To illustrate their value, I present a brief example. Consider this method I wrote that needs to communicate to a delegate when a document object has finished processing an XML representation of a weather layer with a certain name. I named this method as so:

func capabilitiesDocument(document: CapabilitiesDocument, 
  didProcessXMLLayer xmlLayer: XMLElement, 
  withName name: String)

The signature for this method reads:

capabilitiesDocument(_:didProcessXMLLayer:withName:)

I would argue this name communicates very clearly the intent of that method (it’s not unlike the UITableViewDelegate method tableView(_:didSelectRowAtIndexPath:)). In contrast, consider the omission of the external argument names: capabilitiesDocument(_:xmlLayer:name:). Here the method’s purpose is completely lost; named parameters clearly communicate that intent.

Naming methods in this manner may be somewhat of an art; it is not always clear cut. Thankfully, we are not without authoritative guidance.

First, understand Swift has its heritage in the Objective-C community, and Apple has made it clear that Swift adopts the Objective-C style. To this point, the Swift Programming Language Guide states in its discussion on Methods:

Methods in Swift are very similar to their counterparts in Objective-C. As in Objective-C, the name of a method in Swift typically refers to the method’s first parameter using a preposition such as withfor, or by, as seen in the incrementBy(_:) method from the preceding Counter class example. The use of a preposition enables the method to be read as a sentence when it is called.

You don’t need to define an external parameter name for the first argument value, because its purpose is clear from the function name incrementBy(_:numberOfTimes:). The second argument, however, is qualified by an external parameter name to make its purpose clear when the method is called.

The behavior described above means that method definitions in Swift are written with the same grammatical style as Objective-C, and are called in a natural, expressive way.

So there you have it. The goal is a Swift method definition that can be called in a natural, expressive way, as is done with Objective-C.

Given that Apple establishes this link between Swift and Objective-C method naming guidelines, it is reasonable to turn to their Coding Guidelines for Cocoa as an authoritative source for naming not only methods, but also variables, types, delegates, etc. While the guidelines are not 100% applicable to Swift (such as the naming of accessors, which Swift makes implicit), for the most part they are.

Apple does provide some discussion of this in a Swift-specific context in their API Design Guidelines. You will not find any contradictions between this and the Cocoa guidelines, but perhaps some clarifications.

Finally, in the spirit of leading by example, an extremely good source for a practical application of these guidelines are Apple’s framework references, such as the UIKit Framework Reference. These give hundreds upon hundreds of examples of method and property names that follow these conventions.

Happy Swifting!

Leave a Comment

Property Value Observing of Struct Types

The Swift Programming Language Guide has this to say about property value observing:

You have the option to define either or both of these observers on a property:

  • willSet is called just before the value is stored.

  • didSet is called immediately after the new value is stored.

Given that, how many times would you expect the following snippet to produce an output, “didSet dict”?

class SomeClass {
  var dict: [String: String]? {
    didSet {
      print("didSet dict")
    }
  }
}
let myClass = SomeClass()
myClass.dict = [:]
myClass.dict?["A"] = "alpha"
myClass.dict?.removeValueForKey("A")

What the documentation does not make clear is that for structures, which are value types, property observers are triggered both on assignment and on mutation; for classes, which are reference types, they are only triggered on assignment.

So for this example, where dict is a structure, didSet is called three times: once for the initial assignment, and twice for the two mutations. Good to know!

Leave a Comment

Duplicate XML Elements and Associated Enum Values

This is the third in a series of articles on parsing an online XML document. In the previous post, Parsing an XML Document, I focused on how to use NSXMLParser and NSXMLParserDelegate to assist in parsing, but left a bit of unfinished business: capturing the hierarchy of the document. This is something NSXMLParser and its delegate methods do not do. I was planning to address the entirety of a solution here, but a bit of other (but related) business intervened.

For now, I look at a few approaches to representing a collection of child elements within the XMLElement I have been building so far, and will further build upon the chosen approach in the next article to discuss actual construction of the XML tree object.

Common to all approaches is for each XMLElement to have a collection of child XMLElements. This makes sense because every child of an XML element is itself an XML element.

Unfortunately, things are complicated by the fact that not all element names are unique within a given collection of elements. Consider this excerpt that expounds upon the XML document example introduced in the first article, which did not show any keywords:

<KeywordList>
  <Keyword>WCS</Keyword>
  <Keyword>GeoTIFF</Keyword>
  <Keyword>AerialOK_SP_LL84_HalfFoot_5-7-2015></Keyword>
</KeywordList>

This is relevant because if we are to want to store child elements in a dictionary (presumably by their name) so that we can easily reference them, duplicate names would be prohibitive. We could store child elements for all element types within an array, but then we lose the inherent ability to reference them by name that a dictionary provides.

The first solution to addressing the duplicate element names is to store XMLElement child elements in an array within a dictionary, like so (this adds to the XMLElement class defined so far in this series):

class XMLElement { // excerpt

  /// Stores an array of one or more child elements for a given element name.
  var elements: [String: [XMLElement]] = [:]

  /**
   Adds an `element` with `name` to the collection of child `elements`.
   */
  func addElement(element: XMLElement, withName name: String) {

    // First element with this name, create elements array
    if elements[name] == nil {
      elements[name] = [XMLElement]()
    }

    // Add element to dictionary array
    elements[name]!.append(element)
  }

  /**
   Returns the first child element from `elements` with `name`.
   */
  func firstElementWithName(name: String) -&gt; XMLElement? {
    return elements[name]?[0]
  }
}

I provide firstElementWithName(_:) on line 23 for illustration. To return all the elements with a particular name is simply a matter of directly querying elements. Determining which element in the array you need after that point is really up to how the XML is being utilized, and I don’t address that here.

This approach does have the benefit of simplicity. However, I do not like that those elements appearing only once are stored in an array…an array with only one element. So I sought a native Swift solution that might let me, in effect, return either a single XMLElement or an array of XMLElements.

In the below excerpt (which replaces the prior one), a data structure like that given on line 4 would eliminate the explicit array, where Any can now be an XMLElement or an array of XMLElements.

class XMLElement { // excerpt

  /// Dictionary of `XMLElement` or `XMLElement` arrays, keyed on element name.
  private(set) var elements: [String: Any] = [:]

  /** 
   Adds an element to an array of child `XMLElement`s.
   */
  func addElement(element: XMLElement, withName name: String) {

    // Add to a single element
    if let existingElement = elements["Name"] as? XMLElement {
      elements["Name"] = [existingElement, element]
    }

    // Add to an array of elements
    else if var elementsWithName = elements["Name"] as? [XMLElement] {
      elementsWithName.append(element)
      elements["Name"] = elementsWithName
    }

    // Add the first single
    else {
      elements["Name"] = element
    }
  }

  /**
   Returns the first of the named `XMLElement` array, 
   or `nil` if no such named elements exist.
   */
  func firstElementWithName(name: String) -&gt; Any? {

    // A single element
    if let element = elements["Name"] as? XMLElement {
      return element
    }

    // An array of elements
    else if let elements = elements["Name"] as? [XMLElement] {
      return elements[0]
    }

    // No element with this name
    return nil
  } 
}

This is considerably more complex than the former approach, but while it has the benefit of eliminating the array for single XMLElement values with a specific name, it gains some type ambiguity. The private setter on line 4 mitigates any mis-assignments to the elements dictionary, but the return value on firstElementWithName(_:) is not an explicit XMLElement or [XMLElement]. This may be good solution, but I sought something better.

The last approach I discuss came from me exploring how I could return or represent in Swift an either/or value…without opening it up to Any. What came to mind was my prior reading on associated enumuration values. I had yet to have the opportunity to use those, and this application for them seemed to have potential.

class XMLElement { // excerpt

  /**
   Restricts the valid forms a child `XMLElement` can take: 
   a single element or a collection of them.
   */
  enum XMLElements {
    case Single(XMLElement)
    case Collection([XMLElement])
  }

  /// Dictionary of `XMLElements`, keyed on element name.
  var elements: [String: XMLElements] = [:]

  /**
   Adds an element to an dictionary of child `XMLElements`.
   */
  func addElement(element: XMLElement, withName name: String) {

    // Sibling elements with same name
    if let elementsForName = elements[name] {
      switch elementsForName {

      // Create collection
      case .Single(let existingElement):
        elements[name] = .Collection([existingElement, element])

      // Add to collection
      case .Collection(var existingElements):
        existingElements.append(element)
        elements[name] = .Collection(existingElements)
      }
    }

    // First element with this name
    else {
      elements[name] = .Single(element)
    }
  }

  /**
   Returns the first named child `XMLElement`, or `nil` if no such element exists.
   */
  func firstElementWithName(name: String) -> XMLElement? {

    if let elements = elements[name] {
      switch elements {

      case .Single(let element):
        return element

      case .Collection(let elements):
        return elements[0]
      }
    }

    // No elements with this name
    else {
      return nil
    }
  }
}

This is very similar to the preceding Any approach, in that it avoids storing an array of XMLElements for every element, but it has the benefit of strong typing and being a bit more self-documenting. While it does have the greatest complexity of the three approaches, we can know with certainty the elements property of an XMLElement will contain nothing but XMLElements, if anything at all, and the return value from firstElementWithName(_:) is non-ambiguous.

I will press ahead with that implementation in the fourth installment in this series where I use it to build a document tree object.

Leave a Comment

Parsing an XML Document

Using NSXMLParser to parse an XML document is the focus of this second installment in a series of posts that began with using NSURLRequest to retrieve a document from the web and continues with building an object tree representation of the document.

Apple makes parsing the text of an XML document rather trivial via its NSXMLParser and NSXMLParserDelegate Foundation classes. The two very much work hand-in-hand, as it is the delegate the parser notifies when it finds the opening and closing tag of an XML element, among several other events.

In the previous post, I introduced the XMLElement class and method retrieveXmlDataForURL(_:completionHandler:). This method retrieves into an xmlData property an NSData representation of an XML document. That xmlData property is used as input for the parsing operation I am now discussing here.

The first thing I do is extend XMLElement to install the NSXMLParser by adding this simple parseDocument() method (note, this adds to the XMLElement class defined so in the previous article):

class XMLElement { // excerpt

  /**
   Parse the XML document previously assigned to property `xmlData`. 
   If `xmlData` is `nil`, this method takes no action.
   */
  func parseDocument() {
    guard let xmlData = xmlData else { return }
    let xmlParser = NSXMLParser(data: xmlData)
    xmlParser.delegate = self
    xmlParser.parse()
  }
}

That will get the machine going, but stopping there would be a case of a letting a tree fall in the forest with no one to hear it. So I add some properties and an NSXMLParserDelegate method to capture the values NSXMLParser has found:

class XMLElement { // excerpt

  /// The element name, such as "BoundingBox". Every element has a name.
  var name: String!

  /// The element attributes, such as ["maxx": "180", "maxy": "90"]. 
  /// If `nil`, the element has no attributes.
  var attributes: [String: String]?

  /**
   Records the element name and attributes found by the `NSXMLParser`.
   */
  func parser(parser: NSXMLParser, didStartElement elementName: String,
    namespaceURI: String?, qualifiedName qName: String?, 
    attributes attributeDict: [String : String]) {

    name = elementName
    attributes = attributeDict
  }
}

Of the parameters given in those methods, the ones of interest to me are elementName and attributeDict. In the XML snippet:

<Layer queryable="0" opaque="0" cascaded="1">
  <BoundingBox SRS="EPSG:4326" minx="-180.0" miny="-90.0" maxx="180.0" maxy="90.0"</BoundingBox>
  <Abstract>Observed River Stages</Abstract>
</Layer>

the elementName on line 2 is “BoundingBox” and the attributeDict contains the key-value pairs ["minx": -180.0, "miny": -90.0, ...]. For the element on line 3, the name is “Abstract”, and the attribute dicitonary is nil.

There are two components of this particular XML example that are not represented in the parameter lists of those methods. The first is the content of an element; i.e., the text between the opening and closing tags, such as “Observed River Stages” in the Abstract element. The second is the hierarchy of or relationship between the elements: there’s nothing in those delegate methods that point to the parent element; nothing tells us BoundingBox is a child of Layer or a sibling of Abstract. I’ll address the first now, and leave the second for the next post in this series.

In order to pass the content of an XML element, NSXMLParser calls its delegate’s parser(_:foundCharacters:) method. What the API documentation tells us about this method is it may be called multiple times as the parser makes its way through the content of a single element; it does not provide a single aggregated string representing the entirety of the content. You have to do that yourself.

So next I add to the XMLElement class the delegate method and supporting property to build an aggregated content string followed by the didEndElement delegate method to clean up the aggregated content:

class XMLElement { // excerpt

  /// The string content within an element pair, or `nil` if there is no content.
  var content: String?

  /**
   Accumulates an element's content character strings.
   */
  func parser(parser: NSXMLParser, foundCharacters string: String) {
    content = (content ?? "").appendContentsOf(string)
  }

  /**
   Ensures the content for an element pair contains non-whitespace characters,
   or is `nil` otherwise.
   */
  func parser(parser: NSXMLParser, didEndElement elementName: String, 
    namespaceURI: String?, qualifiedName qName: String?) {

    // Store fully composed content string, trimming whitespace
    content = content?.stringByTrimmingCharactersInSet(
      NSCharacterSet.whitespaceAndNewlineCharacterSet())
    if content == "" {
      content = nil
    }
  }
}

I found that if the XML was formatted with newlines, even when there was no actual content, those newlines were passed along to the delegate method. Trimming leading and trailing whitespace ensures we’re extracting legitimate content from the element.

Not directly related to capturing the values of an element, but important nonetheless, is the delegate method for capturing errors:

class XMLElement { // excerpt

  /// If an error occurs during parsing, this value describes that error.
  var parseError: NSError?

  /**
   Captures the error state in response to a fatal parsing error.
   */
  func parser(parser: NSXMLParser, parseErrorOccurred parseError: NSError) {
    self.parseError = parseError
  }
}

Once NSXMLParser encounters an error, it immediately terminates parsing and calls this method. This will leave our parseError in the proper state for determining whether a parse error occurred.

And that does it for now.

Note that with this current implementation, the NSXMLParser will call on the single XMLElement delegate assigned in the parseDocument() method as it works its way through the entire XML document. This means the name, attributes, and content properties will be overwritten with each new element. This is something I will address in a forthcoming article, which will focus on how to capture the hierarchical relationships between the elements.

Leave a Comment