Swift is an increasingly popular language for programming iOS devices, supported on Linux in addition to Mac OS X. A few months ago, Apple decided to make Swift open-source;
the language’s next major release, 3.0, will feature a stabilized ABI, new API design guidelines, and portability to new platforms. Languages vary in their support for data structures, which are ways of efficiently organizing data and (in many cases) utilizing it for specific tasks. Some languages don’t have built-in support for data structures; thousands (maybe millions) of programming hours might have been saved over the years if C, for example, had come with a library of data structures. In this article, we’ll walk through a handful of data structures in Swift, plus a couple of my implementations. All code described and executed is Swift 2.2. Instead of testing this in a Mac Playground, I installed the open-source Swift on Ubuntu 15.04 LTS running in VirtualBox on my Windows 10 PC.
Swift on Linux
A brief side-jaunt before we start: I had wanted to try out
Swift on Linux for quite some time. I set up Ubuntu 14.04 LTS under VirtualBox and installed Swift; there are no gotchas—just remember to correctly spell the name of your home folder when adding the export path to .profile, as you’ll need that so you can type “swift” to run the Swift interpreter or compiler. This is the Linux Swift code for “Hello World!” I thought Foundation would be available, but import Foundation did not work out of the box. But Glibc did:
import Glibc
let msg="Hi World" print(msg)
Swift Comes With?
Out of the box, Swift comes with Dictionaries, Sets and Arrays, to which I added Stacks and Queues. Programming languages such as C# come with a bigger set of classes for Collections; hopefully some of these will be implemented in Swift in the future. For instance, the C# generic collections include:
- Dictionary<TKey, TValue>
- HashSet<T>
- SortedDictionary<TKey, TValue>
- LinkedList<T>, List<T>
- Queue<T>
- SortedList<TKey, TValue>
- SortedSet<T>
- SynchronizedCollection<T>
- SynchronizedKeyedCollection<K, T>
- SynchronizedReadOnlyCollection<T>
(That's not to mention the thread safe versions, as well.)
Arrays
Probably the oldest style of data structure in existence, arrays occur in every mainstream language. In Swift, arrays are much closer to a list; you can change their size at runtime. Swift arrays are mutable or immutable, depending on whether you declare it with a var (mutable) or let (immutable). Change the var odds to let odds, as in the example below, and you will get compile errors:
// Array example
var odds : [Int]=[3,4,5,6] //. mutable array
odds.append(3)
odds += [10] // must be in []
// Display count of the array.
print("# Items = \(odds.count)")
print("Element at index 4 is \(odds[4])" )
// Print the array contents.
print("Array contains \(odds)")
// Or
for item in odds {
print(item)
}
In this code below, I populated an array with the numbers 1 to 10 using a range:
import Glibc
func descending(s1: Int, _ s2: Int) -> Bool {
return s1 > s2
}
var odds : [Int]=Array(1...10)
let output = odds.sort(descending)
print(output)
This produces:
[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
Dictionary
Dictionary is probably one of the most useful data structures in any programming language, as it allows you to store and access data very quickly. (A dictionary also known as an associative array.) I recently used one to pick out a count of all the words from a 46 MB text file. It took 5 seconds to read the file and do the job. Here is an example of Swift’s dictionary at work, using countries and their respective economic indexes (with made-up data!):
import Glibc
var countries = [
"Britain":0.25,
"USA":0.26,
"France":0.02,
"Germany":0.03,
"Italy":0.01,
"Sweden":0.01
]
// remove value
countries.removeValueForKey("Sweden")
// Create empty dictionary with specified type of key and value then add two values.
var allies = [String:Double]()
allies["USA"] = 0.8
allies["Japan"] = 0.9
for country in countries.keys{ // add 10%
countries[country]! += 0.1
}
print("Countries = \(countries)")
print("Allies = \(allies)")
The output is:
Countries = ["Italy": 0.11, "USA": 0.35999999999999999, "France": 0.12000000000000001, "Germany": 0.13, "Britain": 0.34999999999999998]
Allies = ["USA": 0.80000000000000004, "Japan": 0.90000000000000002]
Note how the “for” loop needed the “!” to unwrap the value.
Sets
While sets weren't included in Swift 1.0, they were added on later, in 1.2. Sets store unique and unordered values; they will exclude duplicates (or multiples) of the same item. As with dictionaries and arrays, Swift sets use generics, so standard types can be used. If your custom type is hashable (i.e., it provides an Int value), then you can use it in sets. The code below shows two sets of Ints, one odd and one even:
import Glibc
var odds = Set<Int>()
var evens = Set<Int>()
for i in 1...16{
if i % 2 == 0{
evens.insert(i)
} else {
odds.insert(i)
}
}
print(odds)
print(evens)
if evens.contains(1){
print("Error 1 is not even")
}
let all = odds.union( evens )
print(all)
This outputs:
[13, 9, 5, 7, 15, 3, 11, 1]
[12, 16, 10, 14, 2, 4, 6, 8]
[12, 10, 14, 5, 7, 15, 3, 11, 13, 16, 2, 9, 4, 6, 1, 8]
The Stack Type
Programmers know about stacks: you push values on and pop them off in a particular order. Here's my implementation of a generic stack using an array to hold the items. You may be wondering why there are two constructors; the private init is a copy constructor, so you can create a stack from an existing one. In the code below, note that the stackArray is created by a “let,” and so is immutable. The methods that alter it need a mutating prefix or they won't compile:
struct Stack<T> {
private var stackArray : Array<T>
init() {
stackArray = Array<T>()
}
// creates a copy of an existing one
private init(stackArray : Array<T>?) {
if let list = stackArray {
self.stackArray = list
} else {
self.stackArray = Array()
}
}
}
extension Stack {
mutating func push(item: T) {
stackArray.append(item)
}
mutating func pop() -> T {
return stackArray.popLast()!
}
func head() -> T {
return self.stackArray[0]
}
var size : Int {
get {
return stackArray.count
}
}
}
The Stack.size is a property, not a function, so no brackets are needed. Here's an example of using this class:
var stack = Stack<Int>()
stack.push(0)
stack.push(1)
stack.push(2)
stack.push(47)
print(stack.head())
var stack2 = stack // make copy
while stack2.size > 0 { // empty stack 2
print(stack2.pop())
}
print("Stack size = \(stack.size)")
print("Stack 2 size = \(stack2.size)")
The output is:
0
47
2
1
0
Stack size = 4
Stack 2 size = 0
The Queue Type
A queue is similar to a stack in that it helps the programmer organize data in a particular way (in the queue’s case, putting items on the end and
removing them from the front). Here, I've called the methods to do this: enque() and deque(). I've used the value queueArray.startIndex and queueArray.endIndex, which is one after the last item index, so if there are 10 items, they are index 0-9 and endIndex is 10. Here's the code:
struct Queue<T> {
private var queueArray : Array<T>
init() {
queueArray = Array<T>()
}
private init(queueArray : Array<T>?) {
if let list = queueArray {
self.queueArray = list
} else {
self.queueArray = Array()
}
}
}
extension Queue {
mutating func enque(item: T) {
queueArray.append(item)
}
mutating func deque() -> T { // take it from the front
return queueArray.removeAtIndex(queueArray.startIndex)
}
func head() -> T { // first item
return self.queueArray[queueArray.startIndex]
}
func tail() -> T { // last item
return self.queueArray[queueArray.endIndex-1]
}
var size : Int {
get {
return queueArray.count
}
}
}
The code to test this is identical to that for stack, apart from the name change:
var queue = Queue<Int>()
queue.enque(0)
queue.enque(1)
queue.enque(2)
queue.enque(47)
print(queue.head())
var queue2 = queue
while queue2.size > 0 {
print(queue2.deque())
}
print("queue size = \(queue.size)")
print("queue 2 size = \(queue2.size)")
The output of the deque calls is in reverse order to the stack:
0
0
1
2
47
queue size = 4
queue 2 size = 0
Conclusion
Swift on Linux is fast at compiling. I doubt if there's a 1/10th of a second between issuing the build command and the program running for all of these examples. To compile it, use the swiftc compiler:
swiftc main.swift
swiftc -g main.swift
The -g flag adds debug information so you can debug it with the lldb command. For more information about Swift debugging,
check out Swift.org.
