Generic Data Structure and Functions

In this tutorial, you are going to create a generic stack, which is a venerable data structure in computer science. A stack is a last-in, first-out data structure. It supports two basic operations. You can push an item onto the stack, which adds the item to the stack, and you can pop to remove the most recently pushed item off of the stack.

Create a new macOS playground called Generics and make a Stack structure that only stores integers.

Listing 21.1  Setting up a Stack

import Cocoa

var str = "Hello, playground"

struct Stack {
    var items = [Int]()

    mutating func push(_ newItem: Int) {
        items.append(newItem)
    }

    mutating func pop() -> Int? {
        guard !items.isEmpty else { return nil }
        return items.removeLast()
    }
}

This struct has three elements of interest. The items stored property is an array you are using to hold on to the items currently in a stack. The push(_:) method pushes a new item onto the stack by appending it to the end of the items array. Finally, the pop() method pops the top item off of the stack by calling the removeLast() method of an array, which simultaneously removes the last item and returns it. Note that pop() returns an optional Int, because the stack might be empty (in which case there is nothing to pop).

Create a Stack instance to see it in action.

Listing 21.2  Creating an instance of Stack

...
var intStack = Stack()
intStack.push(1)
intStack.push(2)

print(String(describing: intStack.pop()))
print(String(describing: intStack.pop()))
print(String(describing: intStack.pop()))

You create a new Stack instance, push two values on, then try to pop three values off. As expected, the console reports that the pop() calls return the integers you pushed in reverse order, and then pop() returns nil when the stack no longer has any items:

    Optional(2)
    Optional(1)
    nil

Your Stack is useful for storing Ints, but it is currently limited to that type. It would be better if Stack were more general. Modify Stack to be a generic data structure that can hold any type, not just Int.

Listing 21.3  Making Stack generic

struct Stack<Element> {
    var items = [Int Element]()

    mutating func push(_ newItem: Int Element) {
        items.append(newItem)
    }

    mutating func pop() -> Int? Element? {
        guard !items.isEmpty else { return nil }
        return items.removeLast()
    }
}
...

You define a placeholder type, named Element, in the declaration of Stack. Swift’s syntax for declaring a generic uses angle brackets (<>) immediately following the name of the type to enclose the name of the placeholder type: <Element>.

The placeholder type Element can be used inside the Stack structure anywhere a concrete type could be used. By defining the placeholder type Element and then using it in place of Int, you have made your Stack generic. Now, you can have a stack of any type at all, not just integers.

There is now a compiler error where you instantiate a Stack, because you have not specified what concrete type should be substituted for the placeholder type Element. The process of the compiler substituting a concrete type for a placeholder is called specialization. The full details of specialization are outside the scope of this book, but the short summary is that it allows the compiler to make your app faster, because the compiler is able to output code knowing the specific type in use.

Fix the error by specifying that intStack should be an instance of Stack specialized for Int. You will use the same angle bracket syntax to do this.

Listing 21.4  Specializing intStack

...
var intStack = Stack<Int>()
...

This resolves the compiler error.

You can create a stack of any type. Create a Stack of Strings.

Listing 21.5  Creating a Stack of strings

...
print(String(describing: intStack.pop()))
print(String(describing: intStack.pop()))

var stringStack = Stack<String>()
stringStack.push("this is a string")
stringStack.push("another string")

print(String(describing: stringStack.pop()))

The console prints Optional("another string").

It is important to note that while intStack and stringStack are both Stack instances, they do not have the same type. intStack is a Stack<Int>; it would be a compile-time error to pass anything other than an Int to intStack.push(_:). Likewise, stringStack is a Stack<String>, which is distinct from Stack<Int>. This is true even though you have defined only one Stack type.

Generic data structures are both common and extremely useful. Classes and enumerations can also be made generic using the same syntax you used here for structures. In addition, types are not the only element of Swift that can be generic. Functions and methods can also be generic.

Generic Functions and Methods

Given what you just learned about generics, you can now implement a version of this function yourself.

Add the following code to your playground. Some of it may seem unfamiliar; we will walk through it after you have entered it.

Listing 21.6  Your own map function

...
func myMap<T,U>(_ items: [T], _ txform: (T) -> (U)) -> [U] {
    var result = [U]()
    for item in items {
        result.append(f(item))
    }
    return result
}

The declaration of myMap(_:_:) may look pretty ugly if you have not been exposed to generics in other languages. Instead of the concrete types you are familiar with, it just has T and U, and there are more symbol and punctuation characters than letters! But the only new thing is that it declares two placeholder types, T and U, instead of just one.

Figure 21.1 shows a breakdown of the function declaration.

Figure 21.1  myMap declaration

myMap declaration

When defining a generic type or function, you should give your placeholder types descriptive, meaningful names if you can. Array uses Element as its placeholder type name. Optional uses Wrapped. It is common to use T (short for “Type”), U, and so on if you require brevity or if there are not more meaningful names to use.

myMap(_:_:) can be used the same way map(_:) is used. Create an array of Strings, then map it to an array of Ints representing the strings’ lengths.

Listing 21.7  Mapping an array

...
func myMap<T,U>(_ items: [T], _ txform: (T) -> (U)) -> [U] {
    ...
}

let strings = ["one", "two", "three"]
let stringLengths = myMap(strings) { $0.count }
print(stringLengths)

The closure passed to myMap(_:_:) must take a single argument that matches the type contained in the items array, but the type of its return value can be anything. In this call to myMap(_:_:)T is replaced by String and U is replaced by Int. The console confirms the result: [3, 3, 5]. (Note that in real projects there is no need to declare your own mapping function – just use the built-in map(_:).)

Methods can also be generic, even inside types that are already themselves generic. The myMap(_:_:) function you wrote only works on arrays, but it also seems reasonable to want to map a Stack. Create a map(_:) method on Stack.

Listing 21.8  Mapping on a Stack

struct Stack<Element> {
    var items = [Element]()

    mutating func push(_ newItem: Element) {
        items.append(newItem)
    }

    mutating func pop() -> Element? {
        guard !items.isEmpty else { return nil }
        return items.removeLast()
    }

    func map<U>(_ txform: (Element) -> U) -> Stack<U> {
        var mappedItems = [U]()
        for item in items {
            mappedItems.append(f(item))
        }
        return Stack<U>(items: mappedItems)
    }
}
...

This map(_:) method only declares one placeholder type, U, but it uses both Element and U. The Element type is available because map(_:) is inside the Stack structure, which makes the placeholder type Element available. The body of map(_:) is almost identical to myMap(_:_:), differing only in that it returns a new Stack instead of an array. Try out your new method.

Listing 21.9  Using Stack.map(_:)

...
var intStack = Stack<Int>()
intStack.push(1)
intStack.push(2)
var doubledStack = intStack.map { 2 * $0 }

print(String(describing: intStack.pop()))
print(String(describing: intStack.pop()))
print(String(describing: intStack.pop()))

print(String(describing: doubledStack.pop()))
print(String(describing: doubledStack.pop()))
...

The new print() calls show the doubled values in doubledStack:

    Optional(2)
    Optional(1)
    nil
    Optional(4)
    Optional(2)
    Optional("another string")
    [3, 3, 5]

The output from all these print() calls is not needed in the rest of this tutorial, so if you want you can comment them out to keep things tidy.

Written by

XR Developer responsible for end-to-end development of XR solutions spanning multiple domains, by using various XR and WebXR libraries.

Leave a Reply