Generics

The introduction of the Swift programming language brings a new series of tools that make coding more friendly and expressive. Along with its simplified syntax, Swift borrows from the success of other languages to prevent common programming errors like null pointer exceptions and memory leaks.

To contrast, Objective-C has often been referred to as 'the wild west' of code. While extensive and powerful, many errors in Objective-C apps are discovered at runtime. This delay in error discovery is usually due to programming mistakes with memory management and type cast operations. For this essay, we'll review a new design technique with Swift called generics and will explore how it allows data structures to be more expressive and type-safe.

Building Frameworks

As we've seen, data structures are the building blocks for organizing data. For example, linked lists, binary trees and queues provide a blueprint for data processing and analysis. Just like any well-designed program, data structures should also be designed for extensibility and reuse.

To illustrate, assume you're building a simple app that lists a group of students. The data could be easily organized with a linked list and represented in the following manner:

//student linked list structure
class StudentNode {
    var key: Student?
    var next: StudentNode?
}

The Challenge

While this structure is descriptive and organized, it's not reusable. In other words, the structure is valid for listing students but is unable to manage any other type of data (e.g. teachers). The property Student is an object that may include specific properties such as name, class schedule and grades. If you attempted to reuse the same StudentNode class to manage Teachers, this would cause a complier type mismatch.

The problem could be solved through inheritance, but it still wouldn't meet our primary goal of class reuse. This is where generics helps. Generics allows us to build generic versions of data structures so they can be used in different ways.

Applying Generics

If you've reviewed the other topics in this series you've already seen generics in action. In addition to data structures and algorithms, core Swift functions like arrays and dictionaries also make use of generics. Let's refactor the StudentNode to be resuable:

//refactored linked list structure
class LLNode<T> {
    var key: T?
    var next: LLNode<T>?
}

With this revised structure we can see several changes. The class name StudentNode has been changed to something more general (e.g., LLNode). The syntax <T> seen after the classname is called a placeholder. With generics, values seen inside angled brackets (e.g. T ) are declared variables. Once the placeholder T is established, it can be resued anywhere a class reference would be expected. In this example, we've replaced the class type Student with the generic placeholder T.

The Implementation

The power of generics can be now be seen through its implementation. With the class refactored, LLNode can now manage lists of Students, Teachers, or any other type we decide.

//a new list of students
var studentList = LLNode<Student>()

//a new list of teachers
var teacherList = LLNode<Teacher>()

Here's an expanded view of a linked list implementation using generics. The method addLinkAtIndex adds generic LLNodes at a specified index. Since portions of our code evaluate generic types, the type contraint Equatable is appended to the generic T placeholder. Native to the Swift language, Equatable is a simple protocol that ensures various object types conform to the equatable specification.

//generic linked list implementation
public class LinkedList<T: Equatable> {
    private var head: LLNode<T> = LLNode<T>()

    //add generic nodes at a specified index
    func addLinkAtIndex(key: T, index: Int) {
        //establish the head node
        if (head.key == nil) {
            head.key = key;
            return;
        }

        //establish the trailer, current and new items
        var current: LLNode<T>? = head
        var trailer: LLNode<T>?
        var listIndex: Int = 0

        //iterate through the list to find the insertion point
        while (current != nil) {
            if (index == listIndex) {
                var childToUse: LLNode = LLNode<T>()

                //create the new node
                childToUse.key = key;

                //connect the node infront of the current node
                childToUse.next = current
                childToUse.previous = trailer

                //use optional binding for ading the trailer
                if let linktrailer = trailer {
                    linktrailer.next = childToUse
                    childToUse.previous = linktrailer
                }

                //point new node to the current / previous
                current!.previous = childToUse

                //replace the head node if required
                if (index == 0) {
                    head = childToUse
                }

                break
            } //end if

            //iterate through to the next item
            trailer = current
            current = current?.next
            listIndex += 1
        } //end while
    }