Creating a Swift Collection

February 16, 2015


Let’s say you’d like to create your own collection class. In this example, it’s going to be a collection of books that only allow the addition of a new book if it’s written by a select list of your favorite authors.

typealias Book = (title: String, author: String)

struct MyCollection {

    private let validAuthors = ["Tom Robbins", "Jim Davis"]
    private var books: [Book] = []

    mutating func addBook(book: Book) -> Bool {
        if (find(validAuthors, book.author) != nil) {
            books.append(book)
            return true
        } else {
            return false
        }
    }
}

So good so far. Now we need to add some accessors. It would be nice to know how many books are in the collection. Indexed access to the books would be great. The ability to iterate over our books in a for x in y block would be fantastic. Let’s go about adding that behavior.

In order to enable using our collection in a for loop, we’ve got to adopt the CollectionType protocol. Let’s add that to our MyCollection declaration.

class MyCollection: CollectionType {

Let’s read the definition of the CollectionType protocol.

protocol CollectionType : _CollectionType, SequenceType {
    subscript (position: Self.Index) -> Self.Generator.Element { get }
}

Well then. That looks simple, except what is Self.Index and Self.Generator.Element? Let’s read the definition of _CollectionType and SequenceType.

protocol _CollectionType : _SequenceType {

    /// A type that represents a valid position in the collection.
    ///
    /// Valid indices consist of the position of every element and a
    /// "past the end" position that's not valid for use as a subscript.
    typealias Index : ForwardIndexType

    /// The position of the first element in a non-empty collection.
    ///
    /// Identical to `endIndex` in an empty collection.
    var startIndex: Index { get }

    /// The collection's "past the end" position.
    ///
    /// `endIndex` is not a valid argument to `subscript`, and is always
    /// reachable from `startIndex` by zero or more applications of
    /// `successor()`.
    var endIndex: Index { get }
    typealias _Element
    subscript (_i: Index) -> _Element { get }
}

protocol SequenceType : _Sequence_Type {

    /// A type that provides the *sequence* 's iteration interface and
    /// encapsulates its iteration state.
    typealias Generator : GeneratorType

    /// Return a *generator* over the elements of this *sequence*.
    ///
    /// Complexity: O(1)
    func generate() -> Generator
}

Informative. Now we need to know what _SequenceType, ForwardIndexType _Sequence_Type, and GeneratorType do.

protocol _SequenceType {
}

protocol ForwardIndexType : _ForwardIndexType {
}

protocol _Sequence_Type : _SequenceType {

    /// A type whose instances can produce the elements of this
    /// sequence, in order.
    typealias Generator : GeneratorType

    /// Return a *generator* over the elements of this *sequence*.  The
    /// *generator* 's next element is the first element of the
    /// sequence.
    ///
    /// Complexity: O(1)
    func generate() -> Generator
}

protocol GeneratorType {

    /// The type of element generated by `self`.
    typealias Element

    /// Advance to the next element and return it, or `nil` if no next
    /// element exists.
    ///
    /// Requires: `next()` has not been applied to a copy of `self`
    /// since the copy was made, and no preceding call to `self.next()`
    /// has returned `nil`.  Specific implementations of this protocol
    /// are encouraged to respond to violations of this requirement by
    /// calling `preconditionFailure("...")`.
    mutating func next() -> Element?
}

Whew. I think we’ve exhausted that rabbit hole. Now we can start building up our collection class. First, let’s create a book generator. Since the specifics of this type only need to be known to MyCollection, we’re free to create it as a private inner struct.

private struct BookGenerator: GeneratorType {
    typealias Element = Book

    private var books: [Book]
    private var idx = 0

    init(_ books: [Book]) {
        self.books = books
    }

    mutating func next() -> Element? {
        if idx == books.endIndex {
            return nil
        } else {
            let obj = books[idx
            idx++
            return obj
        }
    }
}

Fantastic. Now let’s take a look at how we’re going to adopt the _SequenceType protocol.

typealias Generator = GeneratorOf<Book>

func generate() -> Generator {
    return GeneratorOf(BookGenerator(books))
}

This is a bit of trickery. The GeneratorOf<Book> type is a type-erasing generator. GeneratorOf is a GeneratorType that takes a Generator on initialization. Using GeneratorOf as our generator type allows us to declare a public generate() method that returns a known type (GeneratorOf) without exposing to the world the actual Generator type we’re using.

Now, how are we going to adopt _CollectionType?

typealias Index = Array<Book>.Index
typealias _Element = Book
var startIndex: Index {get { return books.startIndex }}
var endIndex: Index {get { return books.endIndex }}
subscript(_i: Index) -> _Element {get { return books[_i] }}

We’re looking great! Let’s test it out.

var mine = MyCollection()
mine.addBook(("Wild Ducks Flying Backwards", "Tom Robbins"))
mine.addBook(("A Garfield Treasury, Vol 14", "Jim Davis"))

for book in mine {
    println(book)
}

Works great! For completeness, here’s all the code from my test playground:

import Cocoa

typealias Book = (title: String, author: String)

struct MyCollection: CollectionType {

    typealias Generator = GeneratorOf<Book>
    typealias Index = Array<Book>.Index
    typealias _Element = Book

    private let validAuthors = ["Tom Robbins", "Jim Davis"]
    private var books: [Book] = []

    var startIndex: Index {get { return books.startIndex }}
    var endIndex: Index {get { return books.endIndex }}

    private struct BookGenerator: GeneratorType {
        typealias Element = Book

        private var books: [Book]
        private var idx = 0

        init(_ books: [Book]) {
            self.books = books
        }

        mutating func next() -> Element? {
            if idx == books.endIndex {
                return nil
            } else {
                let obj = books[idx
                idx++
                return obj
            }
        }
    }

    mutating func addBook(book: Book) -> Bool {
        if (find(validAuthors, book.author) != nil) {
            books.append(book)
            return true
        } else {
            return false
        }
    }

    func generate() -> Generator {
        return GeneratorOf(BookGenerator(books))
    }

    subscript(_i: Index) -> _Element {get { return books[_i] }}
}

var mine = MyCollection()
mine.addBook(("Wild Ducks Flying Backwards", "Tom Robbins"))
mine.addBook(("A Garfield Treasury, Vol 14", "Jim Davis"))

for book in mine {
    println(book)
}

« | Home | »