Tree.swift

import Foundation

typealias Forest = Tree[]

protocol Tree {
    func parent() -> Tree?
    func nodes() -> Forest
}

func nodes(tree: Tree) -> Forest {
    return tree.nodes()
}

func root(tree: Tree) -> Tree {
    let parent = parent(tree)
    if parent { return root(parent!) }
    return tree
}

func parent(tree: Tree) -> Tree? {
    return tree.parent()
}

func siblings<T where T: Tree, T: AnyObject>(tree: T) -> Forest {
    if let parent = parent(tree) {
        let siblings = (nodes(parent) as NSArray).mutableCopy() as NSMutableArray
        siblings.removeObject(tree)
        return siblings.copy() as Array
    }
    return []
}

func leaves(tree: Tree) -> Forest {
    return nodes(tree).filter { nodes($0).isEmpty }
}

func internalNodes(tree: Tree) -> Forest {
    return nodes(tree).filter { !nodes($0).isEmpty }
}

func degree(tree: Tree) -> Int {
    return nodes(tree).count
}

func level(tree: Tree) -> Int {
    var level = 0
    var node: Tree? = tree
    while node {
        level++
        node = parent(tree)
    }
    return level
}

func height(tree: Tree) -> Int {
    if nodes(tree).isEmpty { return 0 }
    return 1 + maxElement(nodes(tree).map(height))
}