0001    // Trie.swift
0002    //
0003    // The MIT License (MIT)
0004    //
0005    // Copyright (c) 2016 Dan Appel
0006    //
0007    // Permission is hereby granted, free of charge, to any person obtaining a copy
0008    // of this software and associated documentation files (the "Software"), to deal
0009    // in the Software without restriction, including without limitation the rights
0010    // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
0011    // copies of the Software, and to permit persons to whom the Software is
0012    // furnished to do so, subject to the following conditions:
0013    //
0014    // The above copyright notice and this permission notice shall be included in all
0015    // copies or substantial portions of the Software.
0016    //
0017    // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
0018    // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
0019    // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
0020    // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
0021    // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
0022    // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
0023    // SOFTWARE.
0024    
0025    public struct Trie
Trie.swift:29
    var children: [Trie<Element, Payload>]
Trie.swift:38
    init(prefix: Element, payload: Payload?, ending: Bool, children: [Trie<Element, Payload>]) {
Trie.swift:47
public func ==<Element, Payload where Element: Comparable>(lhs: Trie<Element, Payload>, rhs: Trie<Element, Payload>) -> Bool {
Trie.swift:47
public func ==<Element, Payload where Element: Comparable>(lhs: Trie<Element, Payload>, rhs: Trie<Element, Payload>) -> Bool {
Trie.swift:51
public func <<Element, Payload where Element: Comparable>(lhs: Trie<Element, Payload>, rhs: Trie<Element, Payload>) -> Bool {
Trie.swift:51
public func <<Element, Payload where Element: Comparable>(lhs: Trie<Element, Payload>, rhs: Trie<Element, Payload>) -> Bool {
Trie.swift:55
extension Trie: Comparable { }
Trie.swift:57
extension Trie {
Trie.swift:91
extension Trie {
Trie.swift:117
        var new = Trie<Element, Payload>(prefix: element, payload: nil, ending: false, children: [])
Trie.swift:127
extension Trie {
Trie.swift:128
    func findLast<Sequence: SequenceType where Sequence.Generator.Element == Element>(sequence: Sequence) -> Trie<Element, Payload>? {
Trie.swift:132
    func findLast<Generator: GeneratorType where Generator.Element == Element>(generator: Generator) -> Trie<Element, Payload>? {
Trie.swift:167
extension Trie {
Trie.swift:176
extension Trie {
Trie.swift:186
extension Trie where Payload: Equatable {
TrieRouteMatcher.swift:28
    private var componentsTrie = Trie<Character, Int>()
TrieRouteMatcher.swift:29
    private var routesTrie = Trie<Int, Route>()
<Element
Trie.swift:26
    let prefix: Element?
Trie.swift:29
    var children: [Trie<Element, Payload>]
Trie.swift:38
    init(prefix: Element, payload: Payload?, ending: Bool, children: [Trie<Element, Payload>]) {
Trie.swift:38
    init(prefix: Element, payload: Payload?, ending: Bool, children: [Trie<Element, Payload>]) {
: Comparable, Payload
Trie.swift:27
    var payload: Payload?
Trie.swift:29
    var children: [Trie<Element, Payload>]
Trie.swift:38
    init(prefix: Element, payload: Payload?, ending: Bool, children: [Trie<Element, Payload>]) {
Trie.swift:38
    init(prefix: Element, payload: Payload?, ending: Bool, children: [Trie<Element, Payload>]) {
> {
0026        let prefix
Trie.swift:32
        self.prefix = nil
Trie.swift:39
        self.prefix = prefix
Trie.swift:48
    return lhs.prefix == rhs.prefix
Trie.swift:48
    return lhs.prefix == rhs.prefix
Trie.swift:52
    return lhs.prefix < rhs.prefix
Trie.swift:52
    return lhs.prefix < rhs.prefix
Trie.swift:66
        if let k = self.prefix {
Trie.swift:109
            if child.prefix == element {
Trie.swift:148
            guard let current = child.prefix else { continue }
Trie.swift:191
            if let prefix = self.prefix {
Trie.swift:199
                if let prefix = self.prefix {
: Element?
0027        var payload
Trie.swift:33
        self.payload = nil
Trie.swift:40
        self.payload = payload
Trie.swift:73
        if let p = self.payload {
Trie.swift:101
            self.payload = self.payload ?? payload
Trie.swift:101
            self.payload = self.payload ?? payload
Trie.swift:172
        return findLast(generator)?.payload
Trie.swift:189
        if self.payload == payload {
: Payload?
0028        var ending
Trie.swift:34
        self.ending = false
Trie.swift:41
        self.ending = ending
Trie.swift:102
            self.ending = true
Trie.swift:137
            guard ending == true else { return nil }
: Bool
0029        var children
Trie.swift:35
        self.children = []
Trie.swift:42
        self.children = children
Trie.swift:43
        self.children.sortInPlace()
Trie.swift:79
        let children = self.children
Trie.swift:107
        for (index, child) in children.enumerate() {
Trie.swift:111
                self.children[index] = child
Trie.swift:112
                self.children.sortInPlace()
Trie.swift:121
        self.children.append(new)
Trie.swift:123
        self.children.sortInPlace()
Trie.swift:143
        var higher = children.count - 1
Trie.swift:147
            let child = children[middle]
Trie.swift:197
        for child in children {
: [Trie<Element, Payload>]
0030        
0031        init() {
0032            self.prefix = nil
0033            self.payload = nil
0034            self.ending = false
0035            self.children = []
0036        }
0037        
0038        init(prefix: Element, payload: Payload?, ending: Bool, children: [Trie<Element, Payload>]) {
0039            self.prefix = prefix
0040            self.payload = payload
0041            self.ending = ending
0042            self.children = children
0043            self.children.sortInPlace()
0044        }
0045    }
0046    
0047    public func ==<Element, Payload where Element: Comparable>(lhs: Trie<Element, Payload>, rhs: Trie<Element, Payload>) -> Bool {
0048        return lhs.prefix == rhs.prefix
0049    }
0050    
0051    public func <<Element, Payload where Element: Comparable>(lhs: Trie<Element, Payload>, rhs: Trie<Element, Payload>) -> Bool {
0052        return lhs.prefix < rhs.prefix
0053    }
0054    
0055    extension Trie: Comparable { }
0056    
0057    extension Trie {
0058        
0059        var description
TrieRouteMatcher.swift:221
        return componentsTrie.description + "\n" + routesTrie.description
: String {
0060            return pretty(depth: 0)
0061        }
0062        
0063        func pretty
Trie.swift:60
        return pretty(depth: 0)
Trie.swift:80
            .map { $0.pretty(depth: depth + 1) }
(depth depth: Int) -> String {
0064            
0065            let key: String
0066            if let k = self.prefix {
0067                key = "\(k)"
0068            } else {
0069                key = "head"
0070            }
0071            
0072            let payload: String
0073            if let p = self.payload {
0074                payload = ":\(p)"
0075            } else {
0076                payload = ""
0077            }
0078            
0079            let children = self.children
0080                .map { $0.pretty(depth: depth + 1) }
0081                .reduce("", combine: +)
0082            
0083            let pretty = "- \(key)\(payload)" + "\n" + "\(children)"
0084            
0085            let indentation = (0..<depth).reduce("", combine: {$0.0 + "  "})
0086            
0087            return "\(indentation)\(pretty)"
0088        }
0089    }
0090    
0091    extension Trie {
0092        mutating func insert<Sequence: SequenceType where Sequence.Generator.Element == Element>(sequence: Sequence, payload: Payload? = nil) {
0093            insert(sequence.generate(), payload: payload)
0094        }
0095        
0096        mutating func insert
Trie.swift:93
        insert(sequence.generate(), payload: payload)
Trie.swift:110
                child.insert(generator, payload: payload)
Trie.swift:119
        new.insert(generator, payload: payload)
<Generator: GeneratorType where Generator.Element == Element>(generator: Generator, payload: Payload? = nil) {
0097            
0098            var generator = generator
0099            
0100            guard let element = generator.next() else {
0101                self.payload = self.payload ?? payload
0102                self.ending = true
0103                
0104                return
0105            }
0106            
0107            for (index, child) in children.enumerate() {
0108                var child = child
0109                if child.prefix == element {
0110                    child.insert(generator, payload: payload)
0111                    self.children[index] = child
0112                    self.children.sortInPlace()
0113                    return
0114                }
0115            }
0116            
0117            var new = Trie<Element, Payload>(prefix: element, payload: nil, ending: false, children: [])
0118            
0119            new.insert(generator, payload: payload)
0120            
0121            self.children.append(new)
0122    
0123            self.children.sortInPlace()
0124        }
0125    }
0126    
0127    extension Trie {
0128        func findLast<Sequence: SequenceType where Sequence.Generator.Element == Element>(sequence: Sequence) -> Trie<Element, Payload>? {
0129            return findLast(sequence.generate())
0130        }
0131        
0132        func findLast
Trie.swift:129
        return findLast(sequence.generate())
Trie.swift:151
                return child.findLast(generator)
Trie.swift:172
        return findLast(generator)?.payload
Trie.swift:182
        return findLast(generator) != nil
<Generator: GeneratorType where Generator.Element == Element>(generator: Generator) -> Trie<Element, Payload>? {
0133            
0134            var generator = generator
0135            
0136            guard let target = generator.next() else {
0137                guard ending == true else { return nil }
0138                return self
0139            }
0140    
0141            // binary search
0142            var lower = 0
0143            var higher = children.count - 1
0144    
0145            while (lower <= higher) {
0146                let middle = (lower + higher) / 2
0147                let child = children[middle]
0148                guard let current = child.prefix else { continue }
0149    
0150                if (current == target) {
0151                    return child.findLast(generator)
0152                }
0153    
0154                if (current < target) {
0155                    lower = middle + 1
0156                }
0157    
0158                if (current > target) {
0159                    higher = middle - 1
0160                }
0161            }
0162            
0163            return nil
0164        }
0165    }
0166    
0167    extension Trie {
0168        func findPayload<Sequence: SequenceType where Sequence.Generator.Element == Element>(sequence: Sequence) -> Payload? {
0169            return findPayload(sequence.generate())
0170        }
0171        func findPayload
Trie.swift:169
        return findPayload(sequence.generate())
<Generator: GeneratorType where Generator.Element == Element>(generator: Generator) -> Payload? {
0172            return findLast(generator)?.payload
0173        }
0174    }
0175    
0176    extension Trie {
0177        func contains<Sequence: SequenceType where Sequence.Generator.Element == Element>(sequence: Sequence) -> Bool {
0178            return contains(sequence.generate())
0179        }
0180        
0181        func contains
Trie.swift:178
        return contains(sequence.generate())
<Generator: GeneratorType where Generator.Element == Element>(generator: Generator) -> Bool {
0182            return findLast(generator) != nil
0183        }
0184    }
0185    
0186    extension Trie where Payload: Equatable {
0187        func findByPayload
Trie.swift:198
            if let prefixes = child.findByPayload(payload) {
(payload: Payload) -> [Element]? {
0188            
0189            if self.payload == payload {
0190                // not sure what to do if it doesnt have a prefix
0191                if let prefix = self.prefix {
0192                    return [prefix]
0193                }
0194                return []
0195            }
0196            
0197            for child in children {
0198                if let prefixes = child.findByPayload(payload) {
0199                    if let prefix = self.prefix {
0200                        return [prefix] + prefixes
0201                    }
0202                    return prefixes
0203                }
0204            }
0205            return nil
0206        }
0207    }
0208