SwiftDataStructures

SwiftDataStructures is a framework of commonly-used data structures for Swift.

Included:

Deque

A Deque is a data structure comprised of two queues. This implementation has a front queue, which is reversed, and a back queue, which is not. Operations at either end of the Deque have the same complexity as operations on the end of either queue.

Three structs conform to the DequeType protocol: Deque, DequeSlice, and ContiguousDeque. These correspond to the standard library array types.

Discussion of this specific implementation is available here.

List

A singly-linked, lazy list. Head-tail decomposition can be accomplished with a switch statement:

extension List {
  public func map<T>(f: Element -> T) -> List<T> {
    switch self {
    case .Nil: return .Nil
    case let .Cons(x, xs): return f(x) |> xs().map(f)
    }
  }
}

Where |> is the cons operator.

Operations on the beginning of the list are O(1), whereas other operations are O(n).

Discussion of this specific implementation is available here.

Trie

A Trie is a prefix tree data structure. It has set-like operations and properties. Instead of storing hashable elements, however, it stores sequences of hashable elements. As well as set operations, the Trie can be searched by prefix. Insertion, deletion, and searching are all O(n), where n is the length of the sequence being searched for.

Discussion of this specific implementation is available here.

Tree

A red-black binary search tree. Adapted from Airspeed Velocity’s implementation, Chris Okasaki’s Purely Functional Data Structures, and Stefan Kahrs’ Red-black trees with types, which is implemented in the Haskell standard library.

Elements must be comparable with Strict total order.