router.swift

struct RouteStorage {
    
    var componentsTrie = Trie<Character, Int>()
    var routesTrie = Trie<Int, Route>()
    
    var nextComponentId = 1
    
    init(routes: [Route]) {
        
        for route in routes {
            
            // turn component (string) into an id (integer) for fast comparisons
            let componentIds = route.path.map { component -> Int in
                
                // if it already has a component with the same name, use that id
                if let id = componentsTrie.findPayload(component.characters) {
                    return id
                }
                
                let id: Int
                
                if component.characters.first == ":" {
                    // if component is a parameter, give it a negative id
                    id = -nextComponentId
                } else {
                    // normal component, give it a positive id
                    id = nextComponentId
                }
                
                // increment id for next component
                nextComponentId += 1
                
                // insert the component into the trie with the next id
                componentsTrie.insert(component.characters, payload: id)
                
                return id
            }
            
            // insert the components with the end node containing the route
            routesTrie.insert(componentIds, payload: route)
        }
    }
    
    func routeForRequest(request: String) -> Route? {
        let components = request.components
        
        // topmost route node. children are searched for route matches,
        // if they match, that matching node gets set to head
        var head = routesTrie
        
        var parameters = [(id: Int, value: String)]()
        
        componentLoop: for component in components {
            
            // search for component in the components dictionary
            let id = componentsTrie.findPayload(component.characters)
            
            
            // either parameter or 404
            if id == nil {
                
                for child in head.children {
                    
                    // if the id of the route component is negative,
                    // its a parameter
                    if child.prefix < 0 {
                        head = child
                        parameters.append((id: child.prefix!, value: component))
                        continue componentLoop
                    }
                }
                
                // no routes matched
                return nil
            }
            
            
            // component exists in the routes
            for child in head.children {
                
                // still could be a parameter
                // ex: route.get("/api/:version")
                // request: /api/api
                if child.prefix < 0 {
                    head = child
                    parameters.append((id: child.prefix!, value: component))
                    continue componentLoop
                }
                
                // normal, static route
                if child.prefix == id {
                    head = child
                    continue componentLoop
                }
            }
            
            // no routes matched
            return nil
        }
        
        for (id, value) in parameters {
            guard let parameterChars = componentsTrie.findByPayload(id) else { return nil } // should it return nil?
            let parameter = parameterChars.dropFirst().reduce("") { $0.0 + String($0.1)} // drop colon (":"), then combine characters into string
        }
        
        // if the last node has children,
        // the parameters aren't wrong but aren't long enough
        // ie: route: /api/v1/v2/v3, given: /api/v1/v2
        if !head.children.isEmpty {
            return nil
        }
        
        // find the actual route (ensured to be correct)
        return head.payload!
    }
}

struct Route: CustomStringConvertible {
    let path: [String]
    let handler: Void -> Void
    
    var description: String {
        return "/" + path.joinWithSeparator("/")
    }
}

extension String {
    var components: [String] {
        return self.characters.split("/").map(String.init)
    }
}

struct Router {
    
    class RouterBuilder {
        var routes = [Route]()
        func get(path: String, handler: Void -> Void) {
            routes.append(Route(path: path.components, handler: handler))
        }
    }
    
    let storage: RouteStorage
    
    init(build: RouterBuilder -> Void) {
        let builder = RouterBuilder()
        build(builder)
        self.storage = RouteStorage(routes: builder.routes)
    }
    
    func respond(request: String) -> Void? {
        return storage.routeForRequest(request)?.handler()
    }
}

test.swift

import Foundation

func performanceTest(times times: Int, done: ((Int, Double) -> Void)? = nil, closure: () -> ()) -> Double {
    
    var total: NSTimeInterval = 0

    for i in 0..<times {
        let now = NSDate()
        closure()
        let after = -now.timeIntervalSinceNow
        total += after
        done?(i + 1, after)
    }
    
    return total / Double(times)
}


func testTrie() {
    var trie = Trie<Character, Int>()
    
    trie.insert("12345".characters, payload: 10101)
    trie.insert("12456".characters)
    trie.insert("12346".characters)
    trie.insert("12344".characters)
    trie.insert("92344".characters)
    
    print("beginning trie tests")
    
    assert(trie.contains("12345".characters))
    assert(trie.contains("92344".characters))
    assert(!trie.contains("12".characters))
    assert(!trie.contains("12444".characters))
    assert(trie.findPayload("12345".characters) == 10101)
    assert(trie.findPayload("12346".characters) == nil)
    
    print("all tests passed")
}

func testRouter() {
    let router = Router() { route in
        route.get("/hello/world") {print("1")}
        route.get("/hello/dan") {print("2")}
        route.get("/api/:version") {print("3")}
    }
    
    print("beginning router matching tests")
    
    print(router.storage.componentsTrie.description)
    print(router.storage.routesTrie.description)
    
    assert(router.respond("/hello/world") != nil)
    assert(router.respond("/hello/dan") != nil)
    assert(router.respond("/hello/world/dan") == nil)
    assert(router.respond("/api/v1") != nil)
    assert(router.respond("/api/v2") != nil)
    assert(router.respond("/api/v1/v1") == nil)
    assert(router.respond("/api/api") != nil)
    
    
    print("all tests passed")
    
}

func performanceTestParameters() {
    
    let staticRouter = Router() { route in
        route.get("/hello/world/dan") {}
    }
    
    let paramRouter = Router() { route in
        route.get("/:par/:ame/:ter") {}
    }
    
    let staticTime = performanceTest(times: 100000) {
        staticRouter.respond("/hello/world/dan")
    }
    
    let paramTime = performanceTest(times: 100000) {
        paramRouter.respond("/hello/world/dan")
    }
    
    print("static: \(staticTime*100000)")
    print("param: \(paramTime*100000)")
}


func performanceTestRouter() {
    let paths = ["/foo/bar/baz",
        "/foo/bar/qux",
        "/foo/bar/quux",
        "/foo/bar/corge",
        "/foo/bar/grault",
        "/foo/bar/garply",
        "/foo/baz/bar",
        "/foo/baz/qux",
        "/foo/baz/quux",
        "/foo/baz/corge",
        "/foo/baz/grault",
        "/foo/baz/garply",
        "/foo/qux/bar",
        "/foo/qux/baz",
        "/foo/qux/quux",
        "/foo/qux/corge",
        "/foo/qux/grault",
        "/foo/qux/garply",
        "/foo/quux/bar",
        "/foo/quux/baz",
        "/foo/quux/qux",
        "/foo/quux/corge",
        "/foo/quux/grault",
        "/foo/quux/garply",
        "/foo/corge/bar",
        "/foo/corge/baz",
        "/foo/corge/qux",
        "/foo/corge/quux",
        "/foo/corge/grault",
        "/foo/corge/garply",
        "/foo/grault/bar",
        "/foo/grault/baz",
        "/foo/grault/qux",
        "/foo/grault/quux",
        "/foo/grault/corge",
        "/foo/grault/garply",
        "/foo/garply/bar",
        "/foo/garply/baz",
        "/foo/garply/qux",
        "/foo/garply/quux",
        "/foo/garply/corge",
        "/foo/garply/grault",
        "/bar/foo/baz",
        "/bar/foo/qux",
        "/bar/foo/quux",
        "/bar/foo/corge",
        "/bar/foo/grault",
        "/bar/foo/garply",
        "/bar/baz/foo",
        "/bar/baz/qux",
        "/bar/baz/quux",
        "/bar/baz/corge",
        "/bar/baz/grault",
        "/bar/baz/garply",
        "/bar/qux/foo",
        "/bar/qux/baz",
        "/bar/qux/quux",
        "/bar/qux/corge",
        "/bar/qux/grault",
        "/bar/qux/garply",
        "/bar/quux/foo",
        "/bar/quux/baz",
        "/bar/quux/qux",
        "/bar/quux/corge",
        "/bar/quux/grault",
        "/bar/quux/garply",
        "/bar/corge/foo",
        "/bar/corge/baz",
        "/bar/corge/qux",
        "/bar/corge/quux",
        "/bar/corge/grault",
        "/bar/corge/garply",
        "/bar/grault/foo",
        "/bar/grault/baz",
        "/bar/grault/qux",
        "/bar/grault/quux",
        "/bar/grault/corge",
        "/bar/grault/garply",
        "/bar/garply/foo",
        "/bar/garply/baz",
        "/bar/garply/qux",
        "/bar/garply/quux",
        "/bar/garply/corge",
        "/bar/garply/grault",
        "/baz/foo/bar",
        "/baz/foo/qux",
        "/baz/foo/quux",
        "/baz/foo/corge",
        "/baz/foo/grault",
        "/baz/foo/garply",
        "/baz/bar/foo",
        "/baz/bar/qux",
        "/baz/bar/quux",
        "/baz/bar/corge",
        "/baz/bar/grault",
        "/baz/bar/garply",
        "/baz/qux/foo",
        "/baz/qux/bar",
        "/baz/qux/quux",
        "/baz/qux/corge",
        "/baz/qux/grault",
        "/baz/qux/garply",
        "/baz/quux/foo",
        "/baz/quux/bar",
        "/baz/quux/qux",
        "/baz/quux/corge",
        "/baz/quux/grault",
        "/baz/quux/garply",
        "/baz/corge/foo",
        "/baz/corge/bar",
        "/baz/corge/qux",
        "/baz/corge/quux",
        "/baz/corge/grault",
        "/baz/corge/garply",
        "/baz/grault/foo",
        "/baz/grault/bar",
        "/baz/grault/qux",
        "/baz/grault/quux",
        "/baz/grault/corge",
        "/baz/grault/garply",
        "/baz/garply/foo",
        "/baz/garply/bar",
        "/baz/garply/qux",
        "/baz/garply/quux",
        "/baz/garply/corge",
        "/baz/garply/grault",
        "/qux/foo/bar",
        "/qux/foo/baz",
        "/qux/foo/quux",
        "/qux/foo/corge",
        "/qux/foo/grault",
        "/qux/foo/garply",
        "/qux/bar/foo",
        "/qux/bar/baz",
        "/qux/bar/quux",
        "/qux/bar/corge",
        "/qux/bar/grault",
        "/qux/bar/garply",
        "/qux/baz/foo",
        "/qux/baz/bar",
        "/qux/baz/quux",
        "/qux/baz/corge",
        "/qux/baz/grault",
        "/qux/baz/garply",
        "/qux/quux/foo",
        "/qux/quux/bar",
        "/qux/quux/baz",
        "/qux/quux/corge",
        "/qux/quux/grault",
        "/qux/quux/garply",
        "/qux/corge/foo",
        "/qux/corge/bar",
        "/qux/corge/baz",
        "/qux/corge/quux",
        "/qux/corge/grault",
        "/qux/corge/garply",
        "/qux/grault/foo",
        "/qux/grault/bar",
        "/qux/grault/baz",
        "/qux/grault/quux",
        "/qux/grault/corge",
        "/qux/grault/garply",
        "/qux/garply/foo",
        "/qux/garply/bar",
        "/qux/garply/baz",
        "/qux/garply/quux",
        "/qux/garply/corge",
        "/qux/garply/grault",
        "/quux/foo/bar",
        "/quux/foo/baz",
        "/quux/foo/qux",
        "/quux/foo/corge",
        "/quux/foo/grault",
        "/quux/foo/garply",
        "/quux/bar/foo",
        "/quux/bar/baz",
        "/quux/bar/qux",
        "/quux/bar/corge",
        "/quux/bar/grault",
        "/quux/bar/garply",
        "/quux/baz/foo",
        "/quux/baz/bar",
        "/quux/baz/qux",
        "/quux/baz/corge",
        "/quux/baz/grault",
        "/quux/baz/garply",
        "/quux/qux/foo",
        "/quux/qux/bar",
        "/quux/qux/baz",
        "/quux/qux/corge",
        "/quux/qux/grault",
        "/quux/qux/garply",
        "/quux/corge/foo",
        "/quux/corge/bar",
        "/quux/corge/baz",
        "/quux/corge/qux",
        "/quux/corge/grault",
        "/quux/corge/garply",
        "/quux/grault/foo",
        "/quux/grault/bar",
        "/quux/grault/baz",
        "/quux/grault/qux",
        "/quux/grault/corge",
        "/quux/grault/garply",
        "/quux/garply/foo",
        "/quux/garply/bar",
        "/quux/garply/baz",
        "/quux/garply/qux",
        "/quux/garply/corge",
        "/quux/garply/grault",
        "/corge/foo/bar",
        "/corge/foo/baz",
        "/corge/foo/qux",
        "/corge/foo/quux",
        "/corge/foo/grault",
        "/corge/foo/garply",
        "/corge/bar/foo",
        "/corge/bar/baz",
        "/corge/bar/qux",
        "/corge/bar/quux",
        "/corge/bar/grault",
        "/corge/bar/garply",
        "/corge/baz/foo",
        "/corge/baz/bar",
        "/corge/baz/qux",
        "/corge/baz/quux",
        "/corge/baz/grault",
        "/corge/baz/garply",
        "/corge/qux/foo",
        "/corge/qux/bar",
        "/corge/qux/baz",
        "/corge/qux/quux",
        "/corge/qux/grault",
        "/corge/qux/garply",
        "/corge/quux/foo",
        "/corge/quux/bar",
        "/corge/quux/baz",
        "/corge/quux/qux",
        "/corge/quux/grault",
        "/corge/quux/garply",
        "/corge/grault/foo",
        "/corge/grault/bar",
        "/corge/grault/baz",
        "/corge/grault/qux",
        "/corge/grault/quux",
        "/corge/grault/garply",
        "/corge/garply/foo",
        "/corge/garply/bar",
        "/corge/garply/baz",
        "/corge/garply/qux",
        "/corge/garply/quux",
        "/corge/garply/grault",
        "/grault/foo/bar",
        "/grault/foo/baz",
        "/grault/foo/qux",
        "/grault/foo/quux",
        "/grault/foo/corge",
        "/grault/foo/garply",
        "/grault/bar/foo",
        "/grault/bar/baz",
        "/grault/bar/qux",
        "/grault/bar/quux",
        "/grault/bar/corge",
        "/grault/bar/garply",
        "/grault/baz/foo",
        "/grault/baz/bar",
        "/grault/baz/qux",
        "/grault/baz/quux",
        "/grault/baz/corge",
        "/grault/baz/garply",
        "/grault/qux/foo",
        "/grault/qux/bar",
        "/grault/qux/baz",
        "/grault/qux/quux",
        "/grault/qux/corge",
        "/grault/qux/garply",
        "/grault/quux/foo",
        "/grault/quux/bar",
        "/grault/quux/baz",
        "/grault/quux/qux",
        "/grault/quux/corge",
        "/grault/quux/garply",
        "/grault/corge/foo",
        "/grault/corge/bar",
        "/grault/corge/baz",
        "/grault/corge/qux",
        "/grault/corge/quux",
        "/grault/corge/garply",
        "/grault/garply/foo",
        "/grault/garply/bar",
        "/grault/garply/baz",
        "/grault/garply/qux",
        "/grault/garply/quux",
        "/grault/garply/corge",
        "/garply/foo/bar",
        "/garply/foo/baz",
        "/garply/foo/qux",
        "/garply/foo/quux",
        "/garply/foo/corge",
        "/garply/foo/grault",
        "/garply/bar/foo",
        "/garply/bar/baz",
        "/garply/bar/qux",
        "/garply/bar/quux",
        "/garply/bar/corge",
        "/garply/bar/grault",
        "/garply/baz/foo",
        "/garply/baz/bar",
        "/garply/baz/qux",
        "/garply/baz/quux",
        "/garply/baz/corge",
        "/garply/baz/grault",
        "/garply/qux/foo",
        "/garply/qux/bar",
        "/garply/qux/baz",
        "/garply/qux/quux",
        "/garply/qux/corge",
        "/garply/qux/grault",
        "/garply/quux/foo",
        "/garply/quux/bar",
        "/garply/quux/baz",
        "/garply/quux/qux",
        "/garply/quux/corge",
        "/garply/quux/grault",
        "/garply/corge/foo",
        "/garply/corge/bar",
        "/garply/corge/baz",
        "/garply/corge/qux",
        "/garply/corge/quux",
        "/garply/corge/grault",
        "/garply/grault/foo",
        "/garply/grault/bar",
        "/garply/grault/baz",
        "/garply/grault/qux",
        "/garply/grault/quux",
        "/garply/grault/corge"
    ]
    
    let router = Router() { route in
        for path in paths {
            route.get(path, handler: {})
        }
    }
    
//    print(router.storage.componentsTrie.description)
//    print(router.storage.routesTrie.description)
//    
    print("beginning router performance tests")
    
    let time = performanceTest(times: 5, done: { print("\($0): took \($1) seconds") } ) {
        for path in paths {
            for _ in 0..<1000 {
                router.respond(path)
            }
        }
    }
    
    print("average of 5 times: \(time)")
}

testTrie()
testRouter()
performanceTestParameters()
performanceTestRouter()

trie.swift

struct Trie<Element: Comparable, Payload> {
    let prefix: Element?
    var payload: Payload?
    var ending: Bool
    var children: [Trie<Element, Payload>]
    
    init() {
        self.prefix = nil
        self.payload = nil
        self.ending = false
        self.children = []
    }
    
    init(prefix: Element, payload: Payload?, ending: Bool, children: [Trie<Element, Payload>]) {
        self.prefix = prefix
        self.payload = payload
        self.ending = ending
        self.children = children
    }
}

func ==<Element, Payload where Element: Comparable>(lhs: Trie<Element, Payload>, rhs: Trie<Element, Payload>) -> Bool {
    return lhs.prefix == rhs.prefix
}

func <<Element, Payload where Element: Comparable>(lhs: Trie<Element, Payload>, rhs: Trie<Element, Payload>) -> Bool {
    return lhs.prefix < rhs.prefix
}

extension Trie: Comparable { }

extension Trie {
    
    var description: String {
        return pretty(depth: 0)
    }
    
    func pretty(depth depth: Int) -> String {
        
        let key: String
        if let k = self.prefix {
            key = "\(k)"
        } else {
            key = "head"
        }
        
        let payload: String
        if let p = self.payload {
            payload = ":\(p)"
        } else {
            payload = ""
        }
        
        let children = self.children
            .map { $0.pretty(depth: depth + 1) }
            .reduce("", combine: +)
        
        let pretty = "- \(key)\(payload)" + "\n" + "\(children)"
        
        let indentation = (0..<depth).reduce("", combine: {$0.0 + "  "})
        
        return "\(indentation)\(pretty)"
    }
}

extension Trie {
    mutating func insert<Sequence: SequenceType where Sequence.Generator.Element == Element>(sequence: Sequence, payload: Payload? = nil) {
        insert(sequence.generate(), payload: payload)
    }
    
    mutating func insert<Generator: GeneratorType where Generator.Element == Element>(generator: Generator, payload: Payload? = nil) {
        
        var generator = generator
        
        guard let element = generator.next() else {
            
            self.payload = self.payload ?? payload
            self.ending = true
            
            return
        }
        
        for (index, child) in children.enumerate() {
            var child = child
            if child.prefix == element {
                child.insert(generator, payload: payload)
                self.children[index] = child
                self.children.sortInPlace()
                return
            }
        }
        
        var new = Trie<Element, Payload>(prefix: element, payload: nil, ending: false, children: [])
        
        new.insert(generator, payload: payload)
        
        self.children.append(new)
    }
}

extension Trie {
    func findLast<Sequence: SequenceType where Sequence.Generator.Element == Element>(sequence: Sequence) -> Trie<Element, Payload>? {
        return findLast(sequence.generate())
    }
    
    func findLast<Generator: GeneratorType where Generator.Element == Element>(generator: Generator) -> Trie<Element, Payload>? {
        
        var generator = generator
        
        guard let element = generator.next() else {
            guard ending == true else { return nil }
            return self
        }
        
        for child in children {
            if child.prefix == element {
                return child.findLast(generator)
            }
        }
        
        return nil
    }
}

extension Trie {
    func findPayload<Sequence: SequenceType where Sequence.Generator.Element == Element>(sequence: Sequence) -> Payload? {
        return findPayload(sequence.generate())
    }
    func findPayload<Generator: GeneratorType where Generator.Element == Element>(generator: Generator) -> Payload? {
        return findLast(generator)?.payload
    }
}

extension Trie {
    func contains<Sequence: SequenceType where Sequence.Generator.Element == Element>(sequence: Sequence) -> Bool {
        return contains(sequence.generate())
    }
    
    func contains<Generator: GeneratorType where Generator.Element == Element>(generator: Generator) -> Bool {
        return findLast(generator) != nil
    }
}

extension Trie where Payload: Equatable {
    func findByPayload(payload: Payload) -> [Element]? {
        
        if self.payload == payload {
            // not sure what to do if it doesnt have a prefix
            if let prefix = self.prefix {
                return [prefix]
            }
            return []
        }
        
        for child in children {
            if let prefixes = child.findByPayload(payload) {
                if let prefix = self.prefix {
                    return [prefix] + prefixes
                }
                return prefixes
            }
        }
        return nil
    }
}