0001    //
0002    //  BTreeGenerator.swift
0003    //  BTree
0004    //
0005    //  Created by Károly Lőrentey on 2016-02-11.
0006    //  Copyright © 2015–2016 Károly Lőrentey.
0007    //
0008    
0009    /// A generator for all elements stored in a b-tree, in ascending key order.
0010    public struct BTreeGenerator
BTree.swift:51
    public typealias Generator = BTreeGenerator<Key, Payload>
BTreeNode.swift:124
    typealias Generator = BTreeGenerator<Key, Payload>
BTreeNode.swift:129
        return BTreeGenerator(self)
List.swift:89
    internal typealias Base = BTreeGenerator<EmptyKey, Element>
Map.swift:48
    public typealias Generator = BTreeGenerator<Key, Value>
<Key
BTreeGenerator.swift:11
    public typealias Element = (Key, Payload)
BTreeGenerator.swift:12
    typealias Node = BTreeNode<Key, Payload>
: Comparable, Payload
BTreeGenerator.swift:11
    public typealias Element = (Key, Payload)
BTreeGenerator.swift:12
    typealias Node = BTreeNode<Key, Payload>
>: GeneratorType {
0011        public typealias Element
BTreeGenerator.swift:37
    public mutating func next() -> Element? {
BTreeNode.swift:30
    typealias Element = Generator.Element
 = (Key, Payload)
0012        typealias Node
BTreeGenerator.swift:14
    var nodePath: [Node]
BTreeGenerator.swift:17
    init(_ root: Node) {
BTreeGenerator.swift:24
            var path: Array<Node> = []
 = BTreeNode<Key, Payload>
0013    
0014        var nodePath
BTreeGenerator.swift:19
            self.nodePath = []
BTreeGenerator.swift:31
            self.nodePath = path
BTreeGenerator.swift:38
        let level = nodePath.count
BTreeGenerator.swift:40
        let node = nodePath[level - 1]
BTreeGenerator.swift:47
            nodePath.append(n)
BTreeGenerator.swift:51
                nodePath.append(n)
BTreeGenerator.swift:60
            nodePath.removeLast()
BTreeGenerator.swift:62
            while !nodePath.isEmpty && indexPath.last == nodePath.last!.elements.count {
BTreeGenerator.swift:62
            while !nodePath.isEmpty && indexPath.last == nodePath.last!.elements.count {
BTreeGenerator.swift:63
                nodePath.removeLast()
: [Node]
0015        var indexPath
BTreeGenerator.swift:20
            self.indexPath = []
BTreeGenerator.swift:32
            self.indexPath = Array(count: path.count, repeatedValue: 0)
BTreeGenerator.swift:41
        let index = indexPath[level - 1]
BTreeGenerator.swift:45
            indexPath[level - 1] = index + 1
BTreeGenerator.swift:48
            indexPath.append(0)
BTreeGenerator.swift:52
                indexPath.append(0)
BTreeGenerator.swift:56
            indexPath[level - 1] = index + 1
BTreeGenerator.swift:61
            indexPath.removeLast()
BTreeGenerator.swift:62
            while !nodePath.isEmpty && indexPath.last == nodePath.last!.elements.count {
BTreeGenerator.swift:64
                indexPath.removeLast()
: [Int]
0016    
0017        init
BTree.swift:58
        return Generator(self.root)
BTreeNode.swift:129
        return BTreeGenerator(self)
(_ root: Node) {
0018            if root.count == 0 {
0019                self.nodePath = []
0020                self.indexPath = []
0021            }
0022            else {
0023                var node = root
0024                var path: Array<Node> = []
0025                path.reserveCapacity(node.depth + 1)
0026                path.append(root)
0027                while !node.isLeaf {
0028                    node = node.children.first!
0029                    path.append(node)
0030                }
0031                self.nodePath = path
0032                self.indexPath = Array(count: path.count, repeatedValue: 0)
0033            }
0034        }
0035    
0036        /// Advance to the next element and return it, or return `nil` if no next element exists.
0037        public mutating func next
List.swift:97
        return base.next()?.1
() -> Element? {
0038            let level = nodePath.count
0039            guard level > 0 else { return nil }
0040            let node = nodePath[level - 1]
0041            let index = indexPath[level - 1]
0042            let result = node.elements[index]
0043            if !node.isLeaf {
0044                // Descend
0045                indexPath[level - 1] = index + 1
0046                var n = node.children[index + 1]
0047                nodePath.append(n)
0048                indexPath.append(0)
0049                while !n.isLeaf {
0050                    n = n.children.first!
0051                    nodePath.append(n)
0052                    indexPath.append(0)
0053                }
0054            }
0055            else if index < node.elements.count - 1 {
0056                indexPath[level - 1] = index + 1
0057            }
0058            else {
0059                // Ascend
0060                nodePath.removeLast()
0061                indexPath.removeLast()
0062                while !nodePath.isEmpty && indexPath.last == nodePath.last!.elements.count {
0063                    nodePath.removeLast()
0064                    indexPath.removeLast()
0065                }
0066            }
0067            return result
0068        }
0069    }
0070