0001    //
0002    //  BTreeIndex.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    private enum WalkDirection
BTreeIndex.swift:60
    private mutating func descend(direction: WalkDirection, node: Node? = nil) {
 {
0010        case Forward
BTreeIndex.swift:34
        descend(.Forward, node: root)
BTreeIndex.swift:64
            let slot = direction == .Forward ? 0 : node.children.count - 1
BTreeIndex.swift:69
        slots.append(direction == .Forward ? 0 : node.elements.count - 1)
BTreeIndex.swift:99
            descend(.Forward)

0011        case Backward
BTreeIndex.swift:106
            descend(.Backward, node: root.value!)
BTreeIndex.swift:126
            descend(.Backward)

0012    }
0013    
0014    /// An index into a collection that uses a b-tree for storage.
0015    ///
0016    /// This index satisfies `CollectionType`'s requirement for O(1) access, but
0017    /// it is only suitable for read-only processing -- most tree mutations will 
0018    /// invalidate all existing indexes.
0019    /// 
0020    /// - SeeAlso: `BTreeCursor` for an efficient way to modify a batch of values in a b-tree.
0021    public struct BTreeIndex
BTree.swift:77
    public typealias Index = BTreeIndex<Key, Payload>
BTreeIndex.swift:134
    public func successor() -> BTreeIndex<Key, Payload> {
BTreeIndex.swift:144
    public func predecessor() -> BTreeIndex<Key, Payload> {
BTreeIndex.swift:151
public func == <Key: Comparable, Payload>(a: BTreeIndex<Key, Payload>, b: BTreeIndex<Key, Payload>) -> Bool {
BTreeIndex.swift:151
public func == <Key: Comparable, Payload>(a: BTreeIndex<Key, Payload>, b: BTreeIndex<Key, Payload>) -> Bool {
Map.swift:47
    public typealias Index = BTreeIndex<Key, Value>
<Key
BTreeIndex.swift:23
    typealias Node = BTreeNode<Key, Payload>
BTreeIndex.swift:134
    public func successor() -> BTreeIndex<Key, Payload> {
BTreeIndex.swift:144
    public func predecessor() -> BTreeIndex<Key, Payload> {
: Comparable, Payload
BTreeIndex.swift:23
    typealias Node = BTreeNode<Key, Payload>
BTreeIndex.swift:134
    public func successor() -> BTreeIndex<Key, Payload> {
BTreeIndex.swift:144
    public func predecessor() -> BTreeIndex<Key, Payload> {
>: BidirectionalIndexType {
0022        public typealias Distance = Int
0023        typealias Node
BTreeIndex.swift:25
    internal private(set) var root: Weak<Node>
BTreeIndex.swift:26
    internal private(set) var path: [Weak<Node>]
BTreeIndex.swift:29
    internal init(startIndexOf root: Node) {
BTreeIndex.swift:37
    internal init(endIndexOf root: Node) {
BTreeIndex.swift:44
    internal init(path: [Weak<Node>], slots: [Int]) {
BTreeIndex.swift:60
    private mutating func descend(direction: WalkDirection, node: Node? = nil) {
 = BTreeNode<Key, Payload>
0024    
0025        internal private(set) var root
BTree.swift:97
            precondition(index.root.value === self.root)
BTreeIndex.swift:30
        self.root = Weak(root)
BTreeIndex.swift:38
        self.root = Weak(root)
BTreeIndex.swift:47
        self.root = path[0]
BTreeIndex.swift:83
        guard root.value != nil else { invalid() }
BTreeIndex.swift:104
        expectValid(root.value != nil)
BTreeIndex.swift:106
            descend(.Backward, node: root.value!)
BTreeIndex.swift:153
    guard let ar = a.root.value, br = b.root.value where ar === br else { return false }
BTreeIndex.swift:153
    guard let ar = a.root.value, br = b.root.value where ar === br else { return false }
: Weak<Node>
0026        internal private(set) var path
BTree.swift:98
            let node = index.path.last!.value!
BTree.swift:240
        index.expectValid(index.path[0].value === root)
BTree.swift:241
        if index.path.count == 0 {
BTree.swift:244
        guard var last = index.path.last?.value else { index.invalid() }
BTree.swift:246
        for i in (0 ..< index.path.count - 1).reverse() {
BTree.swift:247
            guard let node = index.path[i].value else { index.invalid() }
BTreeIndex.swift:31
        self.path = []
BTreeIndex.swift:39
        self.path = []
BTreeIndex.swift:41
        path.reserveCapacity(root.depth + 1)
BTreeIndex.swift:49
        self.path = path
BTreeIndex.swift:61
        var node = node ?? path.last!.value!.children[slots.last!]
BTreeIndex.swift:62
        path.append(Weak(node))
BTreeIndex.swift:67
            path.append(Weak(node))
BTreeIndex.swift:73
        guard let n = path.removeLast().value else { invalid() }
BTreeIndex.swift:75
        if path.count > 0 {
BTreeIndex.swift:76
            guard let p = path.last!.value else { invalid() }
BTreeIndex.swift:84
        guard let node = self.path.last?.value else { invalid() }
BTreeIndex.swift:92
                while slots.count > 0 && slots.last! == path.last!.value!.elements.count {
BTreeIndex.swift:105
        if path.count == 0 {
BTreeIndex.swift:109
        guard let node = self.path.last!.value else { invalid() }
BTreeIndex.swift:155
    for i in 0 ..< a.path.count {
BTreeIndex.swift:156
        guard a.path[i].value === b.path[i].value else { return false }
BTreeIndex.swift:156
        guard a.path[i].value === b.path[i].value else { return false }
: [Weak<Node>]
0027        internal private(set) var slots
BTree.swift:99
            return node.elements[index.slots.last!]
BTree.swift:245
        var position = last.positionOfSlot(index.slots.last!)
BTree.swift:248
            let slot = index.slots[i]
BTreeCursor.swift:75
        cursor.descendToSlots(index.slots)
BTreeIndex.swift:32
        self.slots = []
BTreeIndex.swift:40
        self.slots = []
BTreeIndex.swift:48
        self.slots = slots
BTreeIndex.swift:61
        var node = node ?? path.last!.value!.children[slots.last!]
BTreeIndex.swift:65
            slots.append(slot)
BTreeIndex.swift:69
        slots.append(direction == .Forward ? 0 : node.elements.count - 1)
BTreeIndex.swift:74
        slots.removeLast()
BTreeIndex.swift:77
            let s = slots.last!
BTreeIndex.swift:86
            if slots.last! < node.elements.count - 1 {
BTreeIndex.swift:87
                slots[slots.count - 1] += 1
BTreeIndex.swift:87
                slots[slots.count - 1] += 1
BTreeIndex.swift:92
                while slots.count > 0 && slots.last! == path.last!.value!.elements.count {
BTreeIndex.swift:92
                while slots.count > 0 && slots.last! == path.last!.value!.elements.count {
BTreeIndex.swift:98
            slots[slots.count - 1] += 1
BTreeIndex.swift:98
            slots[slots.count - 1] += 1
BTreeIndex.swift:111
            if slots.last! > 0 {
BTreeIndex.swift:112
                slots[slots.count - 1] -= 1
BTreeIndex.swift:112
                slots[slots.count - 1] -= 1
BTreeIndex.swift:117
                while slots.count > 0 && slots.last! == 0 {
BTreeIndex.swift:117
                while slots.count > 0 && slots.last! == 0 {
BTreeIndex.swift:120
                if slots.count > 0 {
BTreeIndex.swift:121
                    slots[slots.count - 1] -= 1
BTreeIndex.swift:121
                    slots[slots.count - 1] -= 1
BTreeIndex.swift:154
    guard a.slots == b.slots else { return false }
BTreeIndex.swift:154
    guard a.slots == b.slots else { return false }
: [Int]
0028    
0029        internal init
BTree.swift:81
        return Index(startIndexOf: root)
(startIndexOf root: Node) {
0030            self.root = Weak(root)
0031            self.path = []
0032            self.slots = []
0033            guard !root.isEmpty else { return }
0034            descend(.Forward, node: root)
0035        }
0036    
0037        internal init
BTree.swift:86
        return Index(endIndexOf: root)
(endIndexOf root: Node) {
0038            self.root = Weak(root)
0039            self.path = []
0040            self.slots = []
0041            path.reserveCapacity(root.depth + 1)
0042        }
0043    
0044        internal init
BTree.swift:205
        return Index(path: path, slots: slots)
BTree.swift:273
                return Index(path: path, slots: slots)
BTree.swift:282
        return Index(path: path, slots: slots)
(path: [Weak<Node>], slots: [Int]) {
0045            precondition(path.count == slots.count)
0046            precondition(path.count > 0)
0047            self.root = path[0]
0048            self.slots = slots
0049            self.path = path
0050        }
0051    
0052        internal func expectValid
BTree.swift:240
        index.expectValid(index.path[0].value === root)
BTree.swift:249
            index.expectValid(node.children[slot] === last)
BTree.swift:250
            index.expectValid(slot < node.children.count)
BTreeIndex.swift:78
            expectValid(s < p.children.count && p.children[s] === n)
BTreeIndex.swift:104
        expectValid(root.value != nil)
(@autoclosure expression: Void->Bool, file: StaticString = __FILE__, line: UInt = __LINE__) {
0053            precondition(expression(), "Invalid BTreeCursor", file: file, line: line)
0054        }
0055    
0056        @noreturn internal func invalid
BTree.swift:244
        guard var last = index.path.last?.value else { index.invalid() }
BTree.swift:247
            guard let node = index.path[i].value else { index.invalid() }
BTreeIndex.swift:73
        guard let n = path.removeLast().value else { invalid() }
BTreeIndex.swift:76
            guard let p = path.last!.value else { invalid() }
BTreeIndex.swift:83
        guard root.value != nil else { invalid() }
BTreeIndex.swift:84
        guard let node = self.path.last?.value else { invalid() }
BTreeIndex.swift:109
        guard let node = self.path.last!.value else { invalid() }
(file: StaticString = __FILE__, line: UInt = __LINE__) {
0057            preconditionFailure("Invalid BTreeCursor", file: file, line: line)
0058        }
0059    
0060        private mutating func descend
BTreeIndex.swift:34
        descend(.Forward, node: root)
BTreeIndex.swift:99
            descend(.Forward)
BTreeIndex.swift:106
            descend(.Backward, node: root.value!)
BTreeIndex.swift:126
            descend(.Backward)
(direction: WalkDirection, node: Node? = nil) {
0061            var node = node ?? path.last!.value!.children[slots.last!]
0062            path.append(Weak(node))
0063            while !node.isLeaf {
0064                let slot = direction == .Forward ? 0 : node.children.count - 1
0065                slots.append(slot)
0066                node = node.children[slot]
0067                path.append(Weak(node))
0068            }
0069            slots.append(direction == .Forward ? 0 : node.elements.count - 1)
0070        }
0071    
0072        private mutating func popPath
BTreeIndex.swift:91
                popPath()
BTreeIndex.swift:93
                    popPath()
BTreeIndex.swift:116
                popPath()
BTreeIndex.swift:118
                    popPath()
() {
0073            guard let n = path.removeLast().value else { invalid() }
0074            slots.removeLast()
0075            if path.count > 0 {
0076                guard let p = path.last!.value else { invalid() }
0077                let s = slots.last!
0078                expectValid(s < p.children.count && p.children[s] === n)
0079            }
0080        }
0081    
0082        internal mutating func successorInPlace
BTreeIndex.swift:136
        result.successorInPlace()
() {
0083            guard root.value != nil else { invalid() }
0084            guard let node = self.path.last?.value else { invalid() }
0085            if node.isLeaf {
0086                if slots.last! < node.elements.count - 1 {
0087                    slots[slots.count - 1] += 1
0088                }
0089                else {
0090                    // Ascend
0091                    popPath()
0092                    while slots.count > 0 && slots.last! == path.last!.value!.elements.count {
0093                        popPath()
0094                    }
0095                }
0096            }
0097            else {
0098                slots[slots.count - 1] += 1
0099                descend(.Forward)
0100            }
0101        }
0102        
0103        internal mutating func predecessorInPlace
BTreeIndex.swift:146
        result.predecessorInPlace()
() {
0104            expectValid(root.value != nil)
0105            if path.count == 0 {
0106                descend(.Backward, node: root.value!)
0107                return
0108            }
0109            guard let node = self.path.last!.value else { invalid() }
0110            if node.isLeaf {
0111                if slots.last! > 0 {
0112                    slots[slots.count - 1] -= 1
0113                }
0114                else {
0115                    // Ascend
0116                    popPath()
0117                    while slots.count > 0 && slots.last! == 0 {
0118                        popPath()
0119                    }
0120                    if slots.count > 0 {
0121                        slots[slots.count - 1] -= 1
0122                    }
0123                }
0124            }
0125            else {
0126                descend(.Backward)
0127            }
0128        }
0129    
0130        /// Return the next index after `self` in its collection.
0131        ///
0132        /// - Requires: self is valid and not the end index.
0133        /// - Complexity: Amortized O(1).
0134        public func successor() -> BTreeIndex<Key, Payload> {
0135            var result = self
0136            result.successorInPlace()
0137            return result
0138        }
0139    
0140        /// Return the index preceding `self` in its collection.
0141        ///
0142        /// - Requires: self is valid and not the start index.
0143        /// - Complexity: Amortized O(1).
0144        public func predecessor() -> BTreeIndex<Key, Payload> {
0145            var result = self
0146            result.predecessorInPlace()
0147            return result
0148        }
0149    }
0150    
0151    public func == <Key: Comparable, Payload>(a: BTreeIndex<Key, Payload>, b: BTreeIndex<Key, Payload>) -> Bool {
0152        // Invalid indexes should compare unequal to every index, including themselves.
0153        guard let ar = a.root.value, br = b.root.value where ar === br else { return false }
0154        guard a.slots == b.slots else { return false }
0155        for i in 0 ..< a.path.count {
0156            guard a.path[i].value === b.path[i].value else { return false }
0157        }
0158        return true
0159    }
0160