SwiftDataStructures

install

It’s a CocoaPod. For the time being, only the pre-release beta of CocoaPods 0.36 is capable of working with Swift code. To install it, use gem install cocoapods --pre.

Podfile:

pod 'SwiftDataStructures'

Command line:

$ pod install

Currently implemented:

• OrderedDictionary: Implemented using LinkedList rather than one of Swift’s built-in types. Hopefully a bit faster this way.
• Set: Finally!
• Stack: Also implemented with a LinkedList.
• Queue: Like Stack, this has also been implemented using a LinkedList.
• List: An abstraction over a LinkedList that hides its implementation using LinkedListNodes. A List’s interface is basically identical to that of an Array.
• LinkedList (serves as a base for a lot of the other data structures)

Forthcoming:

• OrderedSet
• A complete test suite
• Performance tests

Comments, ideas, and pull requests are very welcome!

The tests are coming along, but any contributions towards those would be awesome as well. Even just a second set of eyes would go a long way.

example usage

You can check out the tests for more information (better instructions are continually evolving). It’s all pretty intuitive, though … the types all do pretty much what you would expect.

LinkedList<T>

Initialization:

// Empty list
let list = LinkedList<Int>()

// You can initialize a LinkedList using any type that conforms to Sequence
let someArray = [10, 20, 30]
let list = LinkedList<Int>(someArray)

let someSequence = SequenceOf([10, 20, 30])
let list = LinkedList<Int>(someSequence)

// LinkedList also implements ArrayLiteralConvertible
let list : LinkedList<Int> = [10, 20, 30]

LinkedListNode<T>

LinkedList’s elements are LinkedListNode objects, which are simple boxes/wrappers around whatever type T you’re storing in the list. A LinkedListNode has an item property for retrieving the wrapped value, as well as previous and next pointers for traversing the list.

public class LinkedListNode<T>
{
    public let item: T

    public private(set) var previous: LinkedListNode<T>?
    public private(set) var next:     LinkedListNode<T>?

    public init(_ theItem:T) {
        item = theItem
    }
}

Accessing elements

LinkedList defines a subscript getter as well as func at(index:Index) -> LinkedListNode<T> for accessing elements at particular indices. The subscript operator will fail when passed an out-of-bounds index, while at() will simply return nil.

let someNode = list[2]
let someNode = list.at(2)

Traversing the list

LinkedList implements SequenceType, allowing you to use for...in loops, among many other things.

for node in list {
    println("node.item = \(node.item)")
}

A list also maintains first and last pointers:

list.first // an optional LinkedListNode<T>
list.last  // an optional LinkedListNode<T>

Finding a particular item

let foundNode = list.find { $0.item == 1337 } // returns an optional LinkedListNode<T>
foundNode?.item // == 1337 (or nil if the node wasn't found)

Manipulating the list

Note: LinkedList’s Index type is a simple Int.

Adding new elements (append and prepend):

list.append(LinkedListNode(30))
list.prepend(LinkedListNode(30))
list.insert(LinkedListNode(30), atIndex:5)

Removing elements:

let removed = list.removeAtIndex(3) // removed == the removed LinkedListNode object

contributors / authors

bryn austin bellomy < bryn.bellomy@gmail.com >