0001    //
0002    //  BTreeNode.swift
0003    //  BTree
0004    //
0005    //  Created by Károly Lőrentey on 2016-01-13.
0006    //  Copyright © 2015–2016 Károly Lőrentey.
0007    //
0008    
0009    // `bTreeNodeSize` is the maximum size (in bytes) of the keys in a single, fully loaded b-tree node.
0010    // This is related to the order of the b-tree, i.e., the maximum number of children of an internal node.
0011    //
0012    // Common sense indicates (and benchmarking verifies) that the fastest b-tree order depends on `strideof(key)`:
0013    // doubling the size of the key roughly halves the optimal order. So there is a certain optimal overall node size that
0014    // is independent of the key; this value is supposed to be that size.
0015    //
0016    // Obviously, the optimal node size depends on the hardware we're running on.
0017    // Benchmarks performed on various systems (Apple A5X, A8X, A9; Intel Core i5 Sandy Bridge, Core i7 Ivy Bridge) 
0018    // indicate that 8KiB is a good overall choice.
0019    // (This may be related to the size of the L1 cache, which is frequently 16kiB or 32kiB.)
0020    //
0021    // It is not a good idea to use powers of two as the b-tree order, as that would lead to Array reallocations just before
0022    // a node is split. A node size that's just below 2^n seems like a good choice.
0023    internal let bTreeNodeSizeBTreeNode.swift:67         return max(bTreeNodeSize / strideof(Key), 32) = 8191
0024    
0025    //MARK: BTreeNode definition
0026    
0027    /// A node in an in-memory b-tree data structure, efficiently mapping `Comparable` keys to arbitrary payloads.
0028    /// Iterating over the elements in a b-tree returns them in ascending order of their keys.
0029    internal final class BTreeNodeBTree.swift:12     internal typealias Node = BTreeNode<Key, Payload>
BTreeCursor.swift:106     internal typealias Node = BTreeNode<Key, Payload>
BTreeGenerator.swift:12     typealias Node = BTreeNode<Key, Payload>
BTreeIndex.swift:23     typealias Node = BTreeNode<Key, Payload>
BTreeNode.swift:31     typealias Node = BTreeNode<Key, Payload>
BTreeNode.swift:38     internal var children: Array<BTreeNode>
BTreeNode.swift:51     internal init(order: Int, elements: Array<Element>, children: Array<BTreeNode>, count: Int) {
BTreeNode.swift:65 extension BTreeNode {
BTreeNode.swift:84     internal convenience init(node: BTreeNode, slotRange: Range<Int>) {
BTreeNode.swift:94 extension BTreeNode {
BTreeNode.swift:95     func makeChildUnique(index: Int) -> BTreeNode {
BTreeNode.swift:102     func clone() -> BTreeNode {
BTreeNode.swift:103         return BTreeNode(order: order, elements: elements, children: children, count: count)
BTreeNode.swift:109 extension BTreeNode {
BTreeNode.swift:123 extension BTreeNode: SequenceType {
BTreeNode.swift:171 extension BTreeNode {
BTreeNode.swift:313 extension BTreeNode {
BTreeNode.swift:328     let node: BTreeNode<Key, Payload>
BTreeNode.swift:330     var exploded: (separator: (Key, Payload), node: BTreeNode<Key, Payload>) {
BTreeNode.swift:335 extension BTreeNode {
BTreeNode.swift:353         let node = BTreeNode(node: self, slotRange: median + 1 ..< count)
BTreeNode.swift:374 extension BTreeNode {
BTreeNode.swift:447 extension BTreeNode {
BTreeNode.swift:455     internal static func join(left left: BTreeNode, separator: (Key, Payload), right: BTreeNode) -> BTreeNode {
BTreeNode.swift:455     internal static func join(left left: BTreeNode, separator: (Key, Payload), right: BTreeNode) -> BTreeNode {
BTreeNode.swift:455     internal static func join(left left: BTreeNode, separator: (Key, Payload), right: BTreeNode) -> BTreeNode {
BTreeNode.swift:497                 return BTreeNode(left: stock, separator: s.separator, right: s.node)<KeyBTreeNode.swift:31     typealias Node = BTreeNode<Key, Payload>: Comparable, PayloadBTreeNode.swift:31     typealias Node = BTreeNode<Key, Payload>>: NonObjectiveCBase {
0030        typealias ElementBTreeNode.swift:36     internal var elements: Array<Element>
BTreeNode.swift:51     internal init(order: Int, elements: Array<Element>, children: Array<BTreeNode>, count: Int) {
BTreeNode.swift:133     func forEach(@noescape body: (Element) throws -> ()) rethrows {
BTreeNode.swift:151     func forEach(@noescape body: (Element) throws -> Bool) rethrows -> Bool {
BTreeNode.swift:172     internal func setElementInSlot(slot: Int, to element: Element) -> Element {
BTreeNode.swift:172     internal func setElementInSlot(slot: Int, to element: Element) -> Element {
BTreeNode.swift:178     internal func insert(element: Element, inSlot slot: Int) {
BTreeNode.swift:183     internal func append(element: Element) {
BTreeNode.swift:188     internal func removeSlot(slot: Int) -> Element { = Generator.Element
0031        typealias NodeBTreeNode.swift:70     convenience init(order: Int = Node.defaultOrder) {
BTreeNode.swift:74     internal convenience init(left: Node, separator: (Key, Payload), right: Node) {
BTreeNode.swift:74     internal convenience init(left: Node, separator: (Key, Payload), right: Node) {
BTreeNode.swift:314     internal func edit(@noescape descend descend: Node -> Int?, @noescape ascend: (Node, Int) -> Void) {
BTreeNode.swift:314     internal func edit(@noescape descend descend: Node -> Int?, @noescape ascend: (Node, Int) -> Void) { = BTreeNode<Key, Payload>
0032    
0033        /// FIXME: Allocate keys/payloads/children in a single buffer
0034    
0035        /// The elements stored in this node, sorted by key.
0036        internal var elementsBTree.swift:99             return node.elements[index.slots.last!]
BTree.swift:131                 return node.elements[slot.index]
BTree.swift:137         return node.elements[position]
BTree.swift:151                     return node.elements[m].1
BTree.swift:165                     lastmatch = node.elements[m].1
BTree.swift:280         assert(position < node.elements.count)
BTree.swift:335                 assert(slot.index == 0 || node.elements[slot.index - 1].0 <= element.0)
BTree.swift:336                 assert(slot.index == node.elements.count || node.elements[slot.index].0 >= element.0)
BTree.swift:336                 assert(slot.index == node.elements.count || node.elements[slot.index].0 >= element.0)
BTree.swift:390                 old = node.elements[slot.index].1
BTree.swift:391                 node.elements[slot.index].1 = payload
BTree.swift:552             assert(root.elements.count == 0)
BTree.swift:578                         old = node.removeSlot(slot.descend == node.elements.count ? slot.descend - 1 : slot.descend)
BTree.swift:601             assert(root.elements.count == 0)
BTree.swift:648             while seedling.elements.count < keysPerNode {
BTree.swift:652                 seedling.elements.append(element)
BTree.swift:656             while !saplings.isEmpty && seedling.elements.count == keysPerNode {
BTree.swift:659                 if sapling.depth == seedling.depth + 1 && sapling.elements.count < keysPerNode {
BTree.swift:663                     sapling.elements.append(separator)
BTree.swift:668                 else if sapling.depth == seedling.depth && sapling.elements.count == keysPerNode {
BTreeCursor.swift:227                 let s = node.elements[slot - 1]
BTreeCursor.swift:230             let c = node.elements.count
BTreeCursor.swift:233                 let s = node.elements[slot]
BTreeCursor.swift:258                 let s = node.elements[slot - 1]
BTreeCursor.swift:279             let c = node.elements.count
BTreeCursor.swift:282                 let s = node.elements[slot]
BTreeCursor.swift:341             if slots.last! < node.elements.count - 1 || _position == count {
BTreeCursor.swift:349                 } while slots.last! == path.last!.elements.count
BTreeCursor.swift:393             slots.append(node.elements.count - 1)
BTreeCursor.swift:501                 else if slot.descend < node.elements.count {
BTreeCursor.swift:525             return path.last!.elements[slots.last!].0
BTreeCursor.swift:529             path.last!.elements[slots.last!].0 = newValue
BTreeCursor.swift:539             return path.last!.elements[slots.last!].1
BTreeCursor.swift:543             path.last!.elements[slots.last!].1 = newValue
BTreeCursor.swift:555         let old = node.elements[slot].1
BTreeCursor.swift:556         node.elements[slot].1 = payload
BTreeCursor.swift:596             assert(node.isLeaf && slots.last == node.elements.count - 1)
BTreeCursor.swift:598             slots[slots.count - 1] = node.elements.count - 1
BTreeCursor.swift:616             if slot > left.elements.count {
BTreeCursor.swift:618                 slots[i] = slot - left.elements.count - 1
BTreeCursor.swift:621             else if slot == left.elements.count {
BTreeCursor.swift:634                 if slot > left.elements.count {
BTreeCursor.swift:644                 slots.insert(slot > left.elements.count ? 1 : 0, atIndex: 0)
BTreeCursor.swift:669             insert(root.elements[0])
BTreeCursor.swift:717         let result = node.elements[slot]
BTreeCursor.swift:729         node.elements.removeAtIndex(slot)
BTreeCursor.swift:745         if node === root && node.elements.count == 0 && node.children.count == 1 {
BTreeGenerator.swift:42         let result = node.elements[index]
BTreeGenerator.swift:55         else if index < node.elements.count - 1 {
BTreeGenerator.swift:62             while !nodePath.isEmpty && indexPath.last == nodePath.last!.elements.count {
BTreeIndex.swift:69         slots.append(direction == .Forward ? 0 : node.elements.count - 1)
BTreeIndex.swift:86             if slots.last! < node.elements.count - 1 {
BTreeIndex.swift:92                 while slots.count > 0 && slots.last! == path.last!.value!.elements.count {
BTreeNode.swift:54         self.elements = elements
BTreeNode.swift:85         let elements = Array(node.elements[slotRange])
BTreeNode.swift:103         return BTreeNode(order: order, elements: elements, children: children, count: count)
BTreeNode.swift:116     internal var isTooSmall: Bool { return elements.count < minKeys }
BTreeNode.swift:117     internal var isTooLarge: Bool { return elements.count > maxKeys }
BTreeNode.swift:118     internal var isBalanced: Bool { return elements.count >= minKeys && elements.count <= maxKeys }
BTreeNode.swift:118     internal var isBalanced: Bool { return elements.count >= minKeys && elements.count <= maxKeys }
BTreeNode.swift:135             for element in elements {
BTreeNode.swift:140             for i in 0 ..< elements.count {
BTreeNode.swift:142                 try body(elements[i])
BTreeNode.swift:144             try children[elements.count].forEach(body)
BTreeNode.swift:153             for element in elements {
BTreeNode.swift:158             for i in 0 ..< elements.count {
BTreeNode.swift:160                 guard try body(elements[i]) else { return false }
BTreeNode.swift:162             guard try children[elements.count].forEach(body) else { return false }
BTreeNode.swift:173         let old = elements[slot]
BTreeNode.swift:174         elements[slot] = element
BTreeNode.swift:179         elements.insert(element, atIndex: slot)
BTreeNode.swift:184         elements.append(element)
BTreeNode.swift:190         return elements.removeAtIndex(slot)
BTreeNode.swift:202             var end = elements.count
BTreeNode.swift:205                 if elements[mid].0 < key {
BTreeNode.swift:212             return (start < elements.count && elements[start].0 == key ? start : nil, start)
BTreeNode.swift:212             return (start < elements.count && elements[start].0 == key ? start : nil, start)
BTreeNode.swift:215             var end = elements.count - 1
BTreeNode.swift:218                 if elements[mid].0 > key {
BTreeNode.swift:225             return (start >= 0 && elements[start].0 == key ? start : nil, start + 1)
BTreeNode.swift:233             return (index: elements.count, match: true, position: count)
BTreeNode.swift:274         let c = elements.count
BTreeNode.swift:293         let firstKey = elements.first!.0
BTreeNode.swift:294         let lastKey = elements.last!.0
BTreeNode.swift:342         return split(elements.count / 2)
BTreeNode.swift:351         let count = elements.count
BTreeNode.swift:352         let separator = elements[median]
BTreeNode.swift:354         elements.removeRange(median ..< count)
BTreeNode.swift:367         elements.insert(splinter.separator, atIndex: slot)
BTreeNode.swift:380         if slot > 0 && children[slot - 1].elements.count > minKeys {
BTreeNode.swift:383         else if slot < children.count - 1 && children[slot + 1].elements.count > minKeys {
BTreeNode.swift:400         children[slot].elements.insert(elements[slot - 1], atIndex: 0)
BTreeNode.swift:400         children[slot].elements.insert(elements[slot - 1], atIndex: 0)
BTreeNode.swift:408         elements[slot - 1] = children[slot - 1].elements.removeLast()
BTreeNode.swift:408         elements[slot - 1] = children[slot - 1].elements.removeLast()
BTreeNode.swift:417         children[slot].elements.append(elements[slot])
BTreeNode.swift:417         children[slot].elements.append(elements[slot])
BTreeNode.swift:425         elements[slot] = children[slot + 1].elements.removeAtIndex(0)
BTreeNode.swift:425         elements[slot] = children[slot + 1].elements.removeAtIndex(0)
BTreeNode.swift:434         children[slot].elements.append(elements.removeAtIndex(slot))
BTreeNode.swift:434         children[slot].elements.append(elements.removeAtIndex(slot))
BTreeNode.swift:436         children[slot].elements.appendContentsOf(next.elements)
BTreeNode.swift:436         children[slot].elements.appendContentsOf(next.elements)
BTreeNode.swift:478             node.elements.append(separator)
BTreeNode.swift:479             node.elements.appendContentsOf(right.elements)
BTreeNode.swift:479             node.elements.appendContentsOf(right.elements)
BTreeNode.swift:483             node.elements = left.elements + [separator] + node.elements
BTreeNode.swift:483             node.elements = left.elements + [separator] + node.elements
BTreeNode.swift:483             node.elements = left.elements + [separator] + node.elements
BTreeNode.swift:493                 node.insert(s, inSlot: append ? node.elements.count : 0): Array<Element>
0037        /// An empty array (when this is a leaf), or `elements.count + 1` child nodes (when this is an internal node).
0038        internal var childrenBTree.swift:133             let child = node.children[slot.index]
BTree.swift:156                 node = node.children[slot.descend]
BTree.swift:170                 node = node.children[slot.descend]
BTree.swift:195             node = node.children[slot.descend]
BTree.swift:218             let child = node.children[slot.descend]
BTree.swift:222                 position += p - (m == slot.descend ? node.children[m].count : 0)
BTree.swift:249             index.expectValid(node.children[slot] === last)
BTree.swift:250             index.expectValid(slot < node.children.count)
BTree.swift:275             let child = node.children[slot.index]
BTree.swift:354                     pos = node.children[slot.index + 1].count
BTree.swift:534                     pos = node.children[slot.index + 1].count
BTree.swift:546                 if node.children[slot].isTooSmall {
BTree.swift:551         if root.children.count == 1 {
BTree.swift:553             root = root.children[0]
BTree.swift:594                     if node.children[slot].isTooSmall {
BTree.swift:600         if root.children.count == 1 {
BTree.swift:602             root = root.children[0]
BTree.swift:664                     sapling.children.append(seedling)
BTreeCursor.swift:215         if left.children.count == 1 {
BTreeCursor.swift:218         if right.children.count == 1 {
BTreeCursor.swift:250         if left.children.count == 1 {
BTreeCursor.swift:273         if right.children.count == 1 {
BTreeCursor.swift:389                 let slot = node.children.count - 1
BTreeCursor.swift:745         if node === root && node.elements.count == 0 && node.children.count == 1 {
BTreeGenerator.swift:28                 node = node.children.first!
BTreeGenerator.swift:46             var n = node.children[index + 1]
BTreeGenerator.swift:50                 n = n.children.first!
BTreeIndex.swift:61         var node = node ?? path.last!.value!.children[slots.last!]
BTreeIndex.swift:64             let slot = direction == .Forward ? 0 : node.children.count - 1
BTreeIndex.swift:66             node = node.children[slot]
BTreeIndex.swift:78             expectValid(s < p.children.count && p.children[s] === n)
BTreeIndex.swift:78             expectValid(s < p.children.count && p.children[s] === n)
BTreeNode.swift:55         self.children = children
BTreeNode.swift:86         let children = node.isLeaf ? [] : Array(node.children[slotRange.startIndex ... slotRange.endIndex])
BTreeNode.swift:96         guard !isUniquelyReferenced(&children[index]) else { return children[index] }
BTreeNode.swift:96         guard !isUniquelyReferenced(&children[index]) else { return children[index] }
BTreeNode.swift:97         let clone = children[index].clone()
BTreeNode.swift:98         children[index] = clone
BTreeNode.swift:103         return BTreeNode(order: order, elements: elements, children: children, count: count)
BTreeNode.swift:115     internal var isLeaf: Bool { return children.isEmpty }
BTreeNode.swift:141                 try children[i].forEach(body)
BTreeNode.swift:144             try children[elements.count].forEach(body)
BTreeNode.swift:159                 guard try children[i].forEach(body) else { return false }
BTreeNode.swift:162             guard try children[elements.count].forEach(body) else { return false }
BTreeNode.swift:240             for i in 0 ..< children.count - 1 {
BTreeNode.swift:241                 let c = children[i].count
BTreeNode.swift:250             let c = children.last!.count
BTreeNode.swift:252             return (index: children.count - 1, match: false, position: count)
BTreeNode.swift:256             for i in (1 ..< children.count).reverse() {
BTreeNode.swift:257                 let c = children[i].count
BTreeNode.swift:266             let c = children.first!.count
BTreeNode.swift:283             return children[0...slot].reduce(slot) { $0 + $1.count }
BTreeNode.swift:285         return count - children[slot + 1 ... c].reduce(c - slot) { $0 + $1.count }
BTreeNode.swift:359             children.removeRange(median + 1 ..< count + 1)
BTreeNode.swift:360             self.count = median + children.reduce(0, combine: { $0 + $1.count })
BTreeNode.swift:368         children.insert(splinter.node, atIndex: slot + 1)
BTreeNode.swift:379         assert(!isLeaf && children[slot].isTooSmall)
BTreeNode.swift:380         if slot > 0 && children[slot - 1].elements.count > minKeys {
BTreeNode.swift:383         else if slot < children.count - 1 && children[slot + 1].elements.count > minKeys {
BTreeNode.swift:383         else if slot < children.count - 1 && children[slot + 1].elements.count > minKeys {
BTreeNode.swift:400         children[slot].elements.insert(elements[slot - 1], atIndex: 0)
BTreeNode.swift:401         if !children[slot].isLeaf {
BTreeNode.swift:402             let lastGrandChildBeforeSlot = children[slot - 1].children.removeLast()
BTreeNode.swift:402             let lastGrandChildBeforeSlot = children[slot - 1].children.removeLast()
BTreeNode.swift:403             children[slot].children.insert(lastGrandChildBeforeSlot, atIndex: 0)
BTreeNode.swift:403             children[slot].children.insert(lastGrandChildBeforeSlot, atIndex: 0)
BTreeNode.swift:405             children[slot - 1].count -= lastGrandChildBeforeSlot.count
BTreeNode.swift:406             children[slot].count += lastGrandChildBeforeSlot.count
BTreeNode.swift:408         elements[slot - 1] = children[slot - 1].elements.removeLast()
BTreeNode.swift:409         children[slot - 1].count -= 1
BTreeNode.swift:410         children[slot].count += 1
BTreeNode.swift:414         assert(slot < children.count - 1)
BTreeNode.swift:417         children[slot].elements.append(elements[slot])
BTreeNode.swift:418         if !children[slot].isLeaf {
BTreeNode.swift:419             let firstGrandChildAfterSlot = children[slot + 1].children.removeAtIndex(0)
BTreeNode.swift:419             let firstGrandChildAfterSlot = children[slot + 1].children.removeAtIndex(0)
BTreeNode.swift:420             children[slot].children.append(firstGrandChildAfterSlot)
BTreeNode.swift:420             children[slot].children.append(firstGrandChildAfterSlot)
BTreeNode.swift:422             children[slot + 1].count -= firstGrandChildAfterSlot.count
BTreeNode.swift:423             children[slot].count += firstGrandChildAfterSlot.count
BTreeNode.swift:425         elements[slot] = children[slot + 1].elements.removeAtIndex(0)
BTreeNode.swift:426         children[slot].count += 1
BTreeNode.swift:427         children[slot + 1].count -= 1
BTreeNode.swift:431         assert(slot < children.count - 1)
BTreeNode.swift:433         let next = children.removeAtIndex(slot + 1)
BTreeNode.swift:434         children[slot].elements.append(elements.removeAtIndex(slot))
BTreeNode.swift:435         children[slot].count += 1
BTreeNode.swift:436         children[slot].elements.appendContentsOf(next.elements)
BTreeNode.swift:437         children[slot].count += next.count
BTreeNode.swift:439             children[slot].children.appendContentsOf(next.children)
BTreeNode.swift:439             children[slot].children.appendContentsOf(next.children)
BTreeNode.swift:439             children[slot].children.appendContentsOf(next.children)
BTreeNode.swift:441         assert(children[slot].isBalanced)
BTreeNode.swift:470             node = node.makeChildUnique(append ? node.children.count - 1 : 0)
BTreeNode.swift:480             node.children.appendContentsOf(right.children)
BTreeNode.swift:480             node.children.appendContentsOf(right.children)
BTreeNode.swift:484             node.children = left.children + node.children
BTreeNode.swift:484             node.children = left.children + node.children
BTreeNode.swift:484             node.children = left.children + node.children: Array<BTreeNode>
0039    
0040        /// The number of elements in this b-tree.
0041        internal var countBTree.swift:54     public var isEmpty: Bool { return root.count == 0 }
BTree.swift:91         return root.count
BTree.swift:134             position -= slot.position - child.count
BTree.swift:222                 position += p - (m == slot.descend ? node.children[m].count : 0)
BTree.swift:225                 position += node.positionOfSlot(slot.descend) - child.count
BTree.swift:277             position -= slot.position - child.count
BTree.swift:334                 let slot = node.slotOfPosition(node.count - pos)
BTree.swift:339                     pos -= node.count - slot.position
BTree.swift:354                     pos = node.children[slot.index + 1].count
BTree.swift:359                 node.count += 1
BTree.swift:384                 let slot = node.slotOfPosition(node.count - pos)
BTree.swift:387                     pos -= node.count - slot.position
BTree.swift:423                 node.count += 1
BTree.swift:486                     node.count += 1
BTree.swift:517                 let slot = node.slotOfPosition(node.count - pos)
BTree.swift:521                     pos -= node.count - slot.position
BTree.swift:534                     pos = node.children[slot.index + 1].count
BTree.swift:539                 node.count -= 1
BTree.swift:589                     node.count -= 1
BTree.swift:653                 seedling.count += 1
BTree.swift:665                     sapling.count += seedling.count + 1
BTree.swift:665                     sapling.count += seedling.count + 1
BTree.swift:684             assert(seedling.count == 0)
BTreeCursor.swift:151         self.count = root.count
BTreeCursor.swift:152         self._position = root.count
BTreeCursor.swift:161         self.count = root.count
BTreeCursor.swift:162         self._position = root.count
BTreeCursor.swift:172         reset(root: root, position: root.count)
BTreeCursor.swift:176         precondition(position >= 0 && position <= root.count)
BTreeCursor.swift:197             node.count += childCount
BTreeCursor.swift:198             childCount = node.count
BTreeCursor.swift:200         assert(root.count == count)
BTreeCursor.swift:304         self._position += node.count - node.positionOfSlot(slot)
BTreeCursor.swift:311         parent.count += child.count
BTreeCursor.swift:311         parent.count += child.count
BTreeCursor.swift:320         parent.count -= child.count
BTreeCursor.swift:320         parent.count -= child.count
BTreeCursor.swift:328         self._position -= node.count - p
BTreeCursor.swift:409         while self.count > self.position + path.last!.count {
BTreeCursor.swift:428         while position < self.position - path.last!.count || position >= self.position {
BTreeCursor.swift:461         assert(position >= self.position - path.last!.count && position <= self.position)
BTreeCursor.swift:464         var slot = node.slotOfPosition(position - (self.position - node.count))
BTreeCursor.swift:468             slot = node.slotOfPosition(position - (self.position - node.count))
BTreeCursor.swift:633                 parent.count += left.count + right.count + 1
BTreeCursor.swift:633                 parent.count += left.count + right.count + 1
BTreeCursor.swift:633                 parent.count += left.count + right.count + 1
BTreeCursor.swift:651             path[i].count -= path[i + 1].count
BTreeCursor.swift:651             path[i].count -= path[i + 1].count
BTreeCursor.swift:666         let c = root.count
BTreeCursor.swift:730         node.count -= 1
BTreeGenerator.swift:18         if root.count == 0 {
BTreeNode.swift:56         self.count = count
BTreeNode.swift:81             count: left.count + 1 + right.count)
BTreeNode.swift:81             count: left.count + 1 + right.count)
BTreeNode.swift:87         let count = children.reduce(elements.count) { $0 + $1.count }
BTreeNode.swift:103         return BTreeNode(order: order, elements: elements, children: children, count: count)
BTreeNode.swift:126     var isEmpty: Bool { return count == 0 }
BTreeNode.swift:180         count += 1
BTreeNode.swift:185         count += 1
BTreeNode.swift:189         count -= 1
BTreeNode.swift:231         assert(position >= 0 && position <= count)
BTreeNode.swift:232         if position == count {
BTreeNode.swift:233             return (index: elements.count, match: true, position: count)
BTreeNode.swift:238         else if position <= count / 2 {
BTreeNode.swift:241                 let c = children[i].count
BTreeNode.swift:250             let c = children.last!.count
BTreeNode.swift:251             precondition(count == p + c, "Invalid B-Tree")
BTreeNode.swift:252             return (index: children.count - 1, match: false, position: count)
BTreeNode.swift:255             var p = count
BTreeNode.swift:257                 let c = children[i].count
BTreeNode.swift:266             let c = children.first!.count
BTreeNode.swift:280             return count
BTreeNode.swift:283             return children[0...slot].reduce(slot) { $0 + $1.count }
BTreeNode.swift:285         return count - children[slot + 1 ... c].reduce(c - slot) { $0 + $1.count }
BTreeNode.swift:285         return count - children[slot + 1 ... c].reduce(c - slot) { $0 + $1.count }
BTreeNode.swift:356             self.count = median
BTreeNode.swift:360             self.count = median + children.reduce(0, combine: { $0 + $1.count })
BTreeNode.swift:360             self.count = median + children.reduce(0, combine: { $0 + $1.count })
BTreeNode.swift:405             children[slot - 1].count -= lastGrandChildBeforeSlot.count
BTreeNode.swift:405             children[slot - 1].count -= lastGrandChildBeforeSlot.count
BTreeNode.swift:406             children[slot].count += lastGrandChildBeforeSlot.count
BTreeNode.swift:406             children[slot].count += lastGrandChildBeforeSlot.count
BTreeNode.swift:409         children[slot - 1].count -= 1
BTreeNode.swift:410         children[slot].count += 1
BTreeNode.swift:422             children[slot + 1].count -= firstGrandChildAfterSlot.count
BTreeNode.swift:422             children[slot + 1].count -= firstGrandChildAfterSlot.count
BTreeNode.swift:423             children[slot].count += firstGrandChildAfterSlot.count
BTreeNode.swift:423             children[slot].count += firstGrandChildAfterSlot.count
BTreeNode.swift:426         children[slot].count += 1
BTreeNode.swift:427         children[slot + 1].count -= 1
BTreeNode.swift:435         children[slot].count += 1
BTreeNode.swift:437         children[slot].count += next.count
BTreeNode.swift:437         children[slot].count += next.count
BTreeNode.swift:467         let c = scion.count
BTreeNode.swift:468         node.count += c + 1
BTreeNode.swift:472             node.count += c + 1: Int
0042    
0043        /// The order of this b-tree. An internal node will have at most this many children.
0044        internal var _orderBTreeNode.swift:49     internal var order: Int { return numericCast(_order) }
BTreeNode.swift:53         self._order = numericCast(order): Int32
0045        /// The depth of this b-tree.
0046        internal var _depthBTreeNode.swift:48     internal var depth: Int { return numericCast(_depth) }
BTreeNode.swift:57         self._depth = (children.count == 0 ? 0 : children[0]._depth + 1)
BTreeNode.swift:57         self._depth = (children.count == 0 ? 0 : children[0]._depth + 1)
BTreeNode.swift:59         assert(children.indexOf { $0._depth + 1 != self._depth } == nil)
BTreeNode.swift:59         assert(children.indexOf { $0._depth + 1 != self._depth } == nil): Int32
0047    
0048        internal var depthBTree.swift:30     public var depth: Int { return root.depth }
BTree.swift:658                 assert(sapling.depth >= seedling.depth)
BTree.swift:658                 assert(sapling.depth >= seedling.depth)
BTree.swift:659                 if sapling.depth == seedling.depth + 1 && sapling.elements.count < keysPerNode {
BTree.swift:659                 if sapling.depth == seedling.depth + 1 && sapling.elements.count < keysPerNode {
BTree.swift:668                 else if sapling.depth == seedling.depth && sapling.elements.count == keysPerNode {
BTree.swift:668                 else if sapling.depth == seedling.depth && sapling.elements.count == keysPerNode {
BTreeGenerator.swift:25             path.reserveCapacity(node.depth + 1)
BTreeIndex.swift:41         path.reserveCapacity(root.depth + 1)
BTreeNode.swift:76         assert(left.depth == right.depth)
BTreeNode.swift:76         assert(left.depth == right.depth)
BTreeNode.swift:362         assert(node.depth == self.depth)
BTreeNode.swift:362         assert(node.depth == self.depth)
BTreeNode.swift:457         let depthDelta = left.depth - right.depth
BTreeNode.swift:457         let depthDelta = left.depth - right.depth: Int { return numericCast(_depth) }
0049        internal var orderBTree.swift:28     public var order: Int { return root.order }
BTreeCursor.swift:762         if n == count { reset(Node(order: root.order)); return }
BTreeCursor.swift:788             return Tree(order: root.order)
BTreeCursor.swift:792             var tree = Tree(order: root.order)
BTreeCursor.swift:798             reset(Node(order: tree.root.order))
BTreeNode.swift:75         assert(left.order == right.order)
BTreeNode.swift:75         assert(left.order == right.order)
BTreeNode.swift:78             order: left.order,
BTreeNode.swift:88         self.init(order: node.order, elements: elements, children: children, count: count)
BTreeNode.swift:103         return BTreeNode(order: order, elements: elements, children: children, count: count)
BTreeNode.swift:110     internal var maxChildren: Int { return order }
BTreeNode.swift:456         precondition(left.order == right.order)
BTreeNode.swift:456         precondition(left.order == right.order): Int { return numericCast(_order) }
0050    
0051        internal initBTreeNode.swift:71         self.init(order: order, elements: [], children: [], count: 0)
BTreeNode.swift:77         self.init(
BTreeNode.swift:88         self.init(order: node.order, elements: elements, children: children, count: count)
BTreeNode.swift:103         return BTreeNode(order: order, elements: elements, children: children, count: count)(order: Int, elements: Array<Element>, children: Array<BTreeNode>, count: Int) {
0052            assert(children.count == 0 || elements.count == children.count - 1)
0053            self._order = numericCast(order)
0054            self.elements = elements
0055            self.children = children
0056            self.count = count
0057            self._depth = (children.count == 0 ? 0 : children[0]._depth + 1)
0058            super.init()
0059            assert(children.indexOf { $0._depth + 1 != self._depth } == nil)
0060        }
0061    }
0062    
0063    //MARK: Convenience initializers
0064    
0065    extension BTreeNode {
0066        static var defaultOrderBTree.swift:23     public init(order: Int = Node.defaultOrder) {
BTree.swift:619     public init<S: SequenceType where S.Generator.Element == Element>(sortedElements elements: S, order: Int = Node.defaultOrder, fillFactor: Double = 1) {
BTree.swift:704     public init<S: SequenceType where S.Generator.Element == Element>(elements: S, order: Int = Node.defaultOrder, fillFactor: Double = 1) {
BTreeNode.swift:70     convenience init(order: Int = Node.defaultOrder) {: Int {
0067            return max(bTreeNodeSize / strideof(Key), 32)
0068        }
0069    
0070        convenience initBTree.swift:24         self.root = Node(order: order)
BTree.swift:638         var seedling = Node(order: order)
BTree.swift:679             seedling = Node(order: order)
BTreeCursor.swift:25         root = Node()
BTreeCursor.swift:61         root = Node()
BTreeCursor.swift:76         root = Node()
BTreeCursor.swift:293         self.root = Node()
BTreeCursor.swift:762         if n == count { reset(Node(order: root.order)); return }
BTreeCursor.swift:798             reset(Node(order: tree.root.order))(order: Int = Node.defaultOrder) {
0071            self.init(order: order, elements: [], children: [], count: 0)
0072        }
0073    
0074        internal convenience initBTree.swift:367             root = Node(left: root, separator: s.separator, right: s.node)
BTree.swift:431             root = Node(left: root, separator: s.separator, right: s.node)
BTree.swift:495             root = Node(left: root, separator: s.separator, right: s.node)
BTree.swift:672                     seedling = Node(left: sapling, separator: separator, right: seedling)
BTreeCursor.swift:642                 self.root = Node(left: left, separator: splinter.separator, right: right)
BTreeNode.swift:497                 return BTreeNode(left: stock, separator: s.separator, right: s.node)(left: Node, separator: (Key, Payload), right: Node) {
0075            assert(left.order == right.order)
0076            assert(left.depth == right.depth)
0077            self.init(
0078                order: left.order,
0079                elements: [separator],
0080                children: [left, right],
0081                count: left.count + 1 + right.count)
0082        }
0083    
0084        internal convenience initBTreeCursor.swift:226                 let l = slot == 1 ? node.makeChildUnique(0) : Node(node: node, slotRange: 0 ..< slot - 1)
BTreeCursor.swift:232                 let r = slot == c - 1 ? node.makeChildUnique(c) : Node(node: node, slotRange: slot + 1 ..< c)
BTreeCursor.swift:257                 let l = slot == 1 ? node.makeChildUnique(0) : Node(node: node, slotRange: 0 ..< slot - 1)
BTreeCursor.swift:281                 let r = slot == c - 1 ? node.makeChildUnique(c) : Node(node: node, slotRange: slot + 1 ..< c)
BTreeNode.swift:353         let node = BTreeNode(node: self, slotRange: median + 1 ..< count)(node: BTreeNode, slotRange: Range<Int>) {
0085            let elements = Array(node.elements[slotRange])
0086            let children = node.isLeaf ? [] : Array(node.children[slotRange.startIndex ... slotRange.endIndex])
0087            let count = children.reduce(elements.count) { $0 + $1.count }
0088            self.init(order: node.order, elements: elements, children: children, count: count)
0089        }
0090    }
0091    
0092    //MARK: Uniqueness
0093    
0094    extension BTreeNode {
0095        func makeChildUniqueBTreeCursor.swift:216             left = left.makeChildUnique(0)
BTreeCursor.swift:219             right = right.makeChildUnique(0)
BTreeCursor.swift:226                 let l = slot == 1 ? node.makeChildUnique(0) : Node(node: node, slotRange: 0 ..< slot - 1)
BTreeCursor.swift:232                 let r = slot == c - 1 ? node.makeChildUnique(c) : Node(node: node, slotRange: slot + 1 ..< c)
BTreeCursor.swift:251             left = left.makeChildUnique(0)
BTreeCursor.swift:257                 let l = slot == 1 ? node.makeChildUnique(0) : Node(node: node, slotRange: 0 ..< slot - 1)
BTreeCursor.swift:274             right = right.makeChildUnique(0)
BTreeCursor.swift:281                 let r = slot == c - 1 ? node.makeChildUnique(c) : Node(node: node, slotRange: slot + 1 ..< c)
BTreeCursor.swift:319         let child = parent.makeChildUnique(slot)
BTreeCursor.swift:747             root = node.makeChildUnique(0)
BTreeNode.swift:317             let child = makeChildUnique(slot)
BTreeNode.swift:398         makeChildUnique(slot)
BTreeNode.swift:399         makeChildUnique(slot - 1)
BTreeNode.swift:415         makeChildUnique(slot)
BTreeNode.swift:416         makeChildUnique(slot + 1)
BTreeNode.swift:432         makeChildUnique(slot)
BTreeNode.swift:470             node = node.makeChildUnique(append ? node.children.count - 1 : 0)(index: Int) -> BTreeNode {
0096            guard !isUniquelyReferenced(&children[index]) else { return children[index] }
0097            let clone = children[index].clone()
0098            children[index] = clone
0099            return clone
0100        }
0101    
0102        func cloneBTree.swift:44         root = root.clone()
BTreeCursor.swift:660         let root = tree.root.clone()
BTreeNode.swift:97         let clone = children[index].clone()() -> BTreeNode {
0103            return BTreeNode(order: order, elements: elements, children: children, count: count)
0104        }
0105    }
0106    
0107    //MARK: Basic limits and properties
0108    
0109    extension BTreeNode {
0110        internal var maxChildrenBTreeNode.swift:111     internal var minChildren: Int { return (maxChildren + 1) / 2 }
BTreeNode.swift:112     internal var maxKeys: Int { return maxChildren - 1 }: Int { return order }
0111        internal var minChildrenBTreeNode.swift:113     internal var minKeys: Int { return minChildren - 1 }: Int { return (maxChildren + 1) / 2 }
0112        internal var maxKeysBTreeNode.swift:117     internal var isTooLarge: Bool { return elements.count > maxKeys }
BTreeNode.swift:118     internal var isBalanced: Bool { return elements.count >= minKeys && elements.count <= maxKeys }: Int { return maxChildren - 1 }
0113        internal var minKeysBTreeNode.swift:116     internal var isTooSmall: Bool { return elements.count < minKeys }
BTreeNode.swift:118     internal var isBalanced: Bool { return elements.count >= minKeys && elements.count <= maxKeys }
BTreeNode.swift:380         if slot > 0 && children[slot - 1].elements.count > minKeys {
BTreeNode.swift:383         else if slot < children.count - 1 && children[slot + 1].elements.count > minKeys {: Int { return minChildren - 1 }
0114    
0115        internal var isLeafBTree.swift:128         while !node.isLeaf {
BTree.swift:153                 if node.isLeaf {
BTree.swift:167                 if node.isLeaf {
BTree.swift:192             if node.isLeaf {
BTree.swift:216         while !node.isLeaf {
BTree.swift:269         while !node.isLeaf {
BTree.swift:342                 else if node.isLeaf {
BTree.swift:413                 if !node.isLeaf {
BTree.swift:449                 if node.isLeaf {
BTree.swift:520                     assert(!node.isLeaf)
BTree.swift:524                 else if node.isLeaf {
BTree.swift:572                 if node.isLeaf {
BTreeCursor.swift:340         if node.isLeaf {
BTreeCursor.swift:356             while !node.isLeaf {
BTreeCursor.swift:372         if node.isLeaf {
BTreeCursor.swift:386             assert(!path.last!.isLeaf)
BTreeCursor.swift:388             while !node.isLeaf {
BTreeCursor.swift:487                 if node.isLeaf || selector == .Any {
BTreeCursor.swift:493             if node.isLeaf {
BTreeCursor.swift:566         if path.last!.isLeaf {
BTreeCursor.swift:576             assert(node.isLeaf && slots.last == 0)
BTreeCursor.swift:588         if path.last!.isLeaf {
BTreeCursor.swift:596             assert(node.isLeaf && slots.last == node.elements.count - 1)
BTreeCursor.swift:718         if !node.isLeaf {
BTreeGenerator.swift:27             while !node.isLeaf {
BTreeGenerator.swift:43         if !node.isLeaf {
BTreeGenerator.swift:49             while !n.isLeaf {
BTreeIndex.swift:63         while !node.isLeaf {
BTreeIndex.swift:85         if node.isLeaf {
BTreeIndex.swift:110         if node.isLeaf {
BTreeNode.swift:86         let children = node.isLeaf ? [] : Array(node.children[slotRange.startIndex ... slotRange.endIndex])
BTreeNode.swift:134         if isLeaf {
BTreeNode.swift:152         if isLeaf {
BTreeNode.swift:235         if isLeaf {
BTreeNode.swift:276         guard !isLeaf else {
BTreeNode.swift:355         if isLeaf {
BTreeNode.swift:379         assert(!isLeaf && children[slot].isTooSmall)
BTreeNode.swift:401         if !children[slot].isLeaf {
BTreeNode.swift:418         if !children[slot].isLeaf {
BTreeNode.swift:438         if !next.isLeaf {
BTreeNode.swift:476         assert(node.isLeaf == scion.isLeaf)
BTreeNode.swift:476         assert(node.isLeaf == scion.isLeaf): Bool { return children.isEmpty }
0116        internal var isTooSmallBTree.swift:546                 if node.children[slot].isTooSmall {
BTree.swift:594                     if node.children[slot].isTooSmall {
BTreeCursor.swift:734         while node !== root && node.isTooSmall {
BTreeNode.swift:379         assert(!isLeaf && children[slot].isTooSmall): Bool { return elements.count < minKeys }
0117        internal var isTooLargeBTree.swift:345                     if node.isTooLarge {
BTree.swift:362                     splinter = node.isTooLarge ? node.split() : nil
BTree.swift:417                 if node.isTooLarge {
BTree.swift:426                     splinter = node.isTooLarge ? node.split() : nil
BTree.swift:458                         if node.isTooLarge {
BTree.swift:489                         splinter = node.isTooLarge ? node.split() : nil
BTreeCursor.swift:606         guard path.last!.isTooLarge else { return }
BTreeCursor.swift:610         while path[i].isTooLarge {
BTreeNode.swift:341         assert(isTooLarge)
BTreeNode.swift:488         if node.isTooLarge {
BTreeNode.swift:494                 splinter = node.isTooLarge ? node.split() : nil: Bool { return elements.count > maxKeys }
0118        internal var isBalancedBTreeNode.swift:441         assert(children[slot].isBalanced): Bool { return elements.count >= minKeys && elements.count <= maxKeys }
0119    }
0120    
0121    //MARK: SequenceType
0122    
0123    extension BTreeNode: SequenceType {
0124        typealias GeneratorBTreeNode.swift:30     typealias Element = Generator.Element
BTreeNode.swift:128     func generate() -> Generator { = BTreeGenerator<Key, Payload>
0125    
0126        var isEmptyBTreeIndex.swift:33         guard !root.isEmpty else { return }: Bool { return count == 0 }
0127    
0128        func generate() -> Generator {
0129            return BTreeGenerator(self)
0130        }
0131    
0132        /// Call `body` on each element in self in the same order as a for-in loop.
0133        func forEachBTree.swift:63         try root.forEach(body)
BTreeNode.swift:141                 try children[i].forEach(body)
BTreeNode.swift:144             try children[elements.count].forEach(body)(@noescape body: (Element) throws -> ()) rethrows {
0134            if isLeaf {
0135                for element in elements {
0136                    try body(element)
0137                }
0138            }
0139            else {
0140                for i in 0 ..< elements.count {
0141                    try children[i].forEach(body)
0142                    try body(elements[i])
0143                }
0144                try children[elements.count].forEach(body)
0145            }
0146        }
0147    
0148        /// A version of `forEach` that allows `body` to interrupt iteration by returning `false`.
0149        /// 
0150        /// - Returns: `true` iff `body` returned true for all elements in the tree.
0151        func forEachBTree.swift:70         return try root.forEach(body)
BTreeNode.swift:159                 guard try children[i].forEach(body) else { return false }
BTreeNode.swift:162             guard try children[elements.count].forEach(body) else { return false }(@noescape body: (Element) throws -> Bool) rethrows -> Bool {
0152            if isLeaf {
0153                for element in elements {
0154                    guard try body(element) else { return false }
0155                }
0156            }
0157            else {
0158                for i in 0 ..< elements.count {
0159                    guard try children[i].forEach(body) else { return false }
0160                    guard try body(elements[i]) else { return false }
0161                }
0162                guard try children[elements.count].forEach(body) else { return false }
0163            }
0164            return true
0165        }
0166    
0167    }
0168    
0169    //MARK: Slots
0170    
0171    extension BTreeNode {
0172        internal func setElementInSlotBTree.swift:353                     element = node.setElementInSlot(slot.index, to: element)
BTree.swift:452                         old = node.setElementInSlot(m, to: element).1
BTree.swift:467                         old = node.setElementInSlot(m, to: element).1
BTree.swift:480                         old = node.setElementInSlot(m.slot, to: element).1
BTree.swift:543                     old = node.setElementInSlot(m.slot, to: old!)
BTree.swift:591                         old = node.setElementInSlot(m.slot, to: o)(slot: Int, to element: Element) -> Element {
0173            let old = elements[slot]
0174            elements[slot] = element
0175            return old
0176        }
0177    
0178        internal func insertBTree.swift:344                     node.insert(element, inSlot: slot.index)
BTree.swift:416                 node.insert(element, inSlot: slot.descend)
BTree.swift:457                         node.insert(element, inSlot: slot.descend)
BTreeCursor.swift:569             node.insert(element, inSlot: slot + 1)
BTreeCursor.swift:577             node.insert(element, inSlot: 0)
BTreeCursor.swift:591             node.insert(element, inSlot: slot)(element: Element, inSlot slot: Int) {
0179            elements.insert(element, atIndex: slot)
0180            count += 1
0181        }
0182    
0183        internal func appendBTreeCursor.swift:597             node.append(element)(element: Element) {
0184            elements.append(element)
0185            count += 1
0186        }
0187    
0188        internal func removeSlotBTree.swift:526                     old = node.removeSlot(slot.index)
BTree.swift:574                         old = node.removeSlot(m)
BTree.swift:578                         old = node.removeSlot(slot.descend == node.elements.count ? slot.descend - 1 : slot.descend)(slot: Int) -> Element {
0189            count -= 1
0190            return elements.removeAtIndex(slot)
0191        }
0192    
0193        /// Does one step toward looking up an element with `key`, returning the slot index of a direct match (if any), 
0194        /// and the slot index to use to continue descending.
0195        ///
0196        /// - Complexity: O(log(order))
0197        @inline(__always)
0198        internal func slotOfBTree.swift:149                 let slot = node.slotOf(key, choosing: .First)
BTree.swift:163                 let slot = node.slotOf(key, choosing: selector)
BTree.swift:187             let slot = node.slotOf(key, choosing: selector)
BTree.swift:217             let slot = node.slotOf(key, choosing: selector)
BTree.swift:229         let slot = node.slotOf(key, choosing: selector)
BTree.swift:412                 let slot = node.slotOf(element.0, choosing: selector)
BTree.swift:448                 let slot = node.slotOf(element.0, choosing: selector)
BTree.swift:571                 let slot = node.slotOf(key, choosing: selector)
BTreeCursor.swift:485             let slot = node.slotOf(key, choosing: selector)(key: Key, choosing selector: BTreeKeySelector = .First) -> (match: Int?, descend: Int) {
0199            switch selector {
0200            case .First, .Any:
0201                var start = 0
0202                var end = elements.count
0203                while start < end {
0204                    let mid = start + (end - start) / 2
0205                    if elements[mid].0 < key {
0206                        start = mid + 1
0207                    }
0208                    else {
0209                        end = mid
0210                    }
0211                }
0212                return (start < elements.count && elements[start].0 == key ? start : nil, start)
0213            case .Last:
0214                var start = -1
0215                var end = elements.count - 1
0216                while start < end {
0217                    let mid = start + (end - start + 1) / 2
0218                    if elements[mid].0 > key {
0219                        end = mid - 1
0220                    }
0221                    else {
0222                        start = mid
0223                    }
0224                }
0225                return (start >= 0 && elements[start].0 == key ? start : nil, start + 1)
0226            }
0227        }
0228    
0229        /// Return the slot towards of the element at `position` in the subtree rooted at this node.
0230        internal func slotOfPositionBTree.swift:129             let slot = node.slotOfPosition(position)
BTree.swift:270             let slot = node.slotOfPosition(position)
BTree.swift:334                 let slot = node.slotOfPosition(node.count - pos)
BTree.swift:384                 let slot = node.slotOfPosition(node.count - pos)
BTree.swift:517                 let slot = node.slotOfPosition(node.count - pos)
BTreeCursor.swift:464         var slot = node.slotOfPosition(position - (self.position - node.count))
BTreeCursor.swift:468             slot = node.slotOfPosition(position - (self.position - node.count))(position: Int) -> (index: Int, match: Bool, position: Int) {
0231            assert(position >= 0 && position <= count)
0232            if position == count {
0233                return (index: elements.count, match: true, position: count)
0234            }
0235            if isLeaf {
0236                return (position, true, position)
0237            }
0238            else if position <= count / 2 {
0239                var p = 0
0240                for i in 0 ..< children.count - 1 {
0241                    let c = children[i].count
0242                    if position == p + c {
0243                        return (index: i, match: true, position: p + c)
0244                    }
0245                    if position < p + c {
0246                        return (index: i, match: false, position: p + c)
0247                    }
0248                    p += c + 1
0249                }
0250                let c = children.last!.count
0251                precondition(count == p + c, "Invalid B-Tree")
0252                return (index: children.count - 1, match: false, position: count)
0253            }
0254            else {
0255                var p = count
0256                for i in (1 ..< children.count).reverse() {
0257                    let c = children[i].count
0258                    if position == p - (c + 1) {
0259                        return (index: i - 1, match: true, position: position)
0260                    }
0261                    if position > p - (c + 1) {
0262                        return (index: i, match: false, position: p)
0263                    }
0264                    p -= c + 1
0265                }
0266                let c = children.first!.count
0267                precondition(p - c == 0, "Invalid B-Tree")
0268                return (index: 0, match: false, position: c)
0269            }
0270        }
0271    
0272        /// Return the position of the element at `slot` in the subtree rooted at this node.
0273        internal func positionOfSlotBTree.swift:220                 let p = node.positionOfSlot(m)
BTree.swift:225                 position += node.positionOfSlot(slot.descend) - child.count
BTree.swift:245         var position = last.positionOfSlot(index.slots.last!)
BTree.swift:252                 position += node.positionOfSlot(slot - 1) + 1
BTreeCursor.swift:304         self._position += node.count - node.positionOfSlot(slot)
BTreeCursor.swift:327         let p = positionOfSlot ?? node.positionOfSlot(slot)(slot: Int) -> Int {
0274            let c = elements.count
0275            assert(slot >= 0 && slot <= c)
0276            guard !isLeaf else {
0277                return slot
0278            }
0279            if slot == c {
0280                return count
0281            }
0282            if slot <= c / 2 {
0283                return children[0...slot].reduce(slot) { $0 + $1.count }
0284            }
0285            return count - children[slot + 1 ... c].reduce(c - slot) { $0 + $1.count }
0286        }
0287    
0288        /// Returns true iff the subtree at this node is guaranteed to contain the specified element 
0289        /// with `key` (if it exists).
0290        /// Returns false if the key falls into the first or last child subtree, so containment depends
0291        /// on the contents of the ancestors of this node.
0292        internal func containsBTreeCursor.swift:442         while path.count > 1 && !path.last!.contains(key, choosing: selector) {(key: Key, choosing selector: BTreeKeySelector) -> Bool {
0293            let firstKey = elements.first!.0
0294            let lastKey = elements.last!.0
0295            if key < firstKey {
0296                return false
0297            }
0298            if key == firstKey {
0299                return selector != .First
0300            }
0301            if key > lastKey {
0302                return false
0303            }
0304            if key == lastKey {
0305                return selector != .Last
0306            }
0307            return true
0308        }
0309    }
0310    
0311    //MARK: Editing
0312    
0313    extension BTreeNode {
0314        internal func editBTree.swift:312         root.edit(descend: descend, ascend: ascend)
BTreeNode.swift:318             child.edit(descend: descend, ascend: ascend)(@noescape descend descend: Node -> Int?, @noescape ascend: (Node, Int) -> Void) {
0315            guard let slot = descend(self) else { return }
0316            do {
0317                let child = makeChildUnique(slot)
0318                child.edit(descend: descend, ascend: ascend)
0319            }
0320            ascend(self, slot)
0321        }
0322    }
0323    
0324    //MARK: Splitting
0325    
0326    internal struct BTreeSplinterBTree.swift:330         var splinter: BTreeSplinter<Key, Payload>? = nil
BTree.swift:409         var splinter: BTreeSplinter<Key, Payload>? = nil
BTree.swift:445         var splinter: BTreeSplinter<Key, Payload>? = nil
BTreeNode.swift:340     internal func split() -> BTreeSplinter<Key, Payload> {
BTreeNode.swift:350     internal func split(median: Int) -> BTreeSplinter<Key, Payload> {
BTreeNode.swift:363         return BTreeSplinter(separator: separator, node: node)
BTreeNode.swift:366     internal func insert(splinter: BTreeSplinter<Key, Payload>, inSlot slot: Int) {<KeyBTreeNode.swift:327     let separator: (Key, Payload)
BTreeNode.swift:328     let node: BTreeNode<Key, Payload>
BTreeNode.swift:330     var exploded: (separator: (Key, Payload), node: BTreeNode<Key, Payload>) {
BTreeNode.swift:330     var exploded: (separator: (Key, Payload), node: BTreeNode<Key, Payload>) {: Comparable, PayloadBTreeNode.swift:327     let separator: (Key, Payload)
BTreeNode.swift:328     let node: BTreeNode<Key, Payload>
BTreeNode.swift:330     var exploded: (separator: (Key, Payload), node: BTreeNode<Key, Payload>) {
BTreeNode.swift:330     var exploded: (separator: (Key, Payload), node: BTreeNode<Key, Payload>) {> {
0327        let separatorBTree.swift:367             root = Node(left: root, separator: s.separator, right: s.node)
BTree.swift:431             root = Node(left: root, separator: s.separator, right: s.node)
BTree.swift:495             root = Node(left: root, separator: s.separator, right: s.node)
BTreeCursor.swift:642                 self.root = Node(left: left, separator: splinter.separator, right: right)
BTreeNode.swift:331         return (separator, node)
BTreeNode.swift:367         elements.insert(splinter.separator, atIndex: slot)
BTreeNode.swift:497                 return BTreeNode(left: stock, separator: s.separator, right: s.node): (Key, Payload)
0328        let nodeBTree.swift:367             root = Node(left: root, separator: s.separator, right: s.node)
BTree.swift:431             root = Node(left: root, separator: s.separator, right: s.node)
BTree.swift:495             root = Node(left: root, separator: s.separator, right: s.node)
BTreeCursor.swift:272         var right = path.removeLast().split(slots.removeLast()).node
BTreeCursor.swift:615             let right = splinter.node
BTreeNode.swift:331         return (separator, node)
BTreeNode.swift:368         children.insert(splinter.node, atIndex: slot + 1)
BTreeNode.swift:497                 return BTreeNode(left: stock, separator: s.separator, right: s.node): BTreeNode<Key, Payload>
0329    
0330        var explodedBTreeCursor.swift:214         var (separator, right) = left.split(slots.removeLast()).exploded: (separator: (Key, Payload), node: BTreeNode<Key, Payload>) {
0331            return (separator, node)
0332        }
0333    }
0334    
0335    extension BTreeNode {
0336        /// Split this node into two, removing the high half of the nodes and putting them in a splinter.
0337        ///
0338        /// - Returns: A splinter containing the higher half of the original node.
0339        @warn_unused_result
0340        internal func splitBTree.swift:346                         splinter = node.split()
BTree.swift:362                     splinter = node.isTooLarge ? node.split() : nil
BTree.swift:418                     splinter = node.split()
BTree.swift:426                     splinter = node.isTooLarge ? node.split() : nil
BTree.swift:459                             splinter = node.split()
BTree.swift:489                         splinter = node.isTooLarge ? node.split() : nil
BTreeCursor.swift:614             let splinter = left.split()
BTreeNode.swift:490             var splinter = Optional(node.split())
BTreeNode.swift:494                 splinter = node.isTooLarge ? node.split() : nil() -> BTreeSplinter<Key, Payload> {
0341            assert(isTooLarge)
0342            return split(elements.count / 2)
0343        }
0344    
0345        /// Split this node into two at the key at index `median`, removing all elements at or above `median` 
0346        /// and putting them in a splinter.
0347        ///
0348        /// - Returns: A splinter containing the higher half of the original node.
0349        @warn_unused_result
0350        internal func splitBTreeCursor.swift:214         var (separator, right) = left.split(slots.removeLast()).exploded
BTreeCursor.swift:249         _ = left.split(slots.removeLast())
BTreeCursor.swift:272         var right = path.removeLast().split(slots.removeLast()).node
BTreeNode.swift:342         return split(elements.count / 2)(median: Int) -> BTreeSplinter<Key, Payload> {
0351            let count = elements.count
0352            let separator = elements[median]
0353            let node = BTreeNode(node: self, slotRange: median + 1 ..< count)
0354            elements.removeRange(median ..< count)
0355            if isLeaf {
0356                self.count = median
0357            }
0358            else {
0359                children.removeRange(median + 1 ..< count + 1)
0360                self.count = median + children.reduce(0, combine: { $0 + $1.count })
0361            }
0362            assert(node.depth == self.depth)
0363            return BTreeSplinter(separator: separator, node: node)
0364        }
0365    
0366        internal func insertBTree.swift:361                     node.insert(s, inSlot: slot)
BTree.swift:425                     node.insert(s, inSlot: slot)
BTree.swift:488                         node.insert(s, inSlot: slot)
BTreeCursor.swift:632                 parent.insert(splinter, inSlot: pslot)
BTreeNode.swift:493                 node.insert(s, inSlot: append ? node.elements.count : 0)(splinter: BTreeSplinter<Key, Payload>, inSlot slot: Int) {
0367            elements.insert(splinter.separator, atIndex: slot)
0368            children.insert(splinter.node, atIndex: slot + 1)
0369        }
0370    }
0371    
0372    //MARK: Removal
0373    
0374    extension BTreeNode {
0375        /// Reorganize the tree rooted at `self` so that the undersize child in `slot` is corrected.
0376        /// As a side effect of the process, `self` may itself become undersized, but all of its descendants
0377        /// become balanced.
0378        internal func fixDeficiencyBTree.swift:547                     node.fixDeficiency(slot)
BTree.swift:595                         node.fixDeficiency(slot)
BTreeCursor.swift:738             node.fixDeficiency(slot)(slot: Int) {
0379            assert(!isLeaf && children[slot].isTooSmall)
0380            if slot > 0 && children[slot - 1].elements.count > minKeys {
0381                rotateRight(slot)
0382            }
0383            else if slot < children.count - 1 && children[slot + 1].elements.count > minKeys {
0384                rotateLeft(slot)
0385            }
0386            else if slot > 0 {
0387                // Collapse deficient slot into previous slot.
0388                collapse(slot - 1)
0389            }
0390            else {
0391                // Collapse next slot into deficient slot.
0392                collapse(slot)
0393            }
0394        }
0395    
0396        internal func rotateRightBTreeNode.swift:381             rotateRight(slot)(slot: Int) {
0397            assert(slot > 0)
0398            makeChildUnique(slot)
0399            makeChildUnique(slot - 1)
0400            children[slot].elements.insert(elements[slot - 1], atIndex: 0)
0401            if !children[slot].isLeaf {
0402                let lastGrandChildBeforeSlot = children[slot - 1].children.removeLast()
0403                children[slot].children.insert(lastGrandChildBeforeSlot, atIndex: 0)
0404    
0405                children[slot - 1].count -= lastGrandChildBeforeSlot.count
0406                children[slot].count += lastGrandChildBeforeSlot.count
0407            }
0408            elements[slot - 1] = children[slot - 1].elements.removeLast()
0409            children[slot - 1].count -= 1
0410            children[slot].count += 1
0411        }
0412        
0413        internal func rotateLeftBTreeNode.swift:384             rotateLeft(slot)(slot: Int) {
0414            assert(slot < children.count - 1)
0415            makeChildUnique(slot)
0416            makeChildUnique(slot + 1)
0417            children[slot].elements.append(elements[slot])
0418            if !children[slot].isLeaf {
0419                let firstGrandChildAfterSlot = children[slot + 1].children.removeAtIndex(0)
0420                children[slot].children.append(firstGrandChildAfterSlot)
0421    
0422                children[slot + 1].count -= firstGrandChildAfterSlot.count
0423                children[slot].count += firstGrandChildAfterSlot.count
0424            }
0425            elements[slot] = children[slot + 1].elements.removeAtIndex(0)
0426            children[slot].count += 1
0427            children[slot + 1].count -= 1
0428        }
0429    
0430        internal func collapseBTreeNode.swift:388             collapse(slot - 1)
BTreeNode.swift:392             collapse(slot)(slot: Int) {
0431            assert(slot < children.count - 1)
0432            makeChildUnique(slot)
0433            let next = children.removeAtIndex(slot + 1)
0434            children[slot].elements.append(elements.removeAtIndex(slot))
0435            children[slot].count += 1
0436            children[slot].elements.appendContentsOf(next.elements)
0437            children[slot].count += next.count
0438            if !next.isLeaf {
0439                children[slot].children.appendContentsOf(next.children)
0440            }
0441            assert(children[slot].isBalanced)
0442        }
0443    }
0444    
0445    //MARK: Join
0446    
0447    extension BTreeNode {
0448        /// Create and return a new b-tree consisting of elements of `left`,`separator` and the elements of `right`, 
0449        /// in this order.
0450        ///
0451        /// If you need to keep `left` and `right` intact, clone them before calling this function.
0452        ///
0453        /// - Requires: `l <= separator.0 && separator.0 <= r` for all keys `l` in `left` and all keys `r` in `right`.
0454        /// - Complexity: O(log(left.count + right.count))
0455        internal static func joinBTree.swift:692             self.root = Node.join(left: saplings.removeLast(), separator: separators.removeLast(), right: self.root)
BTreeCursor.swift:228                 left = Node.join(left: l, separator: s, right: left)
BTreeCursor.swift:234                 right = Node.join(left: right, separator: s, right: r)
BTreeCursor.swift:259                 left = Node.join(left: l, separator: s, right: left)
BTreeCursor.swift:283                 right = Node.join(left: right, separator: s, right: r)
BTreeCursor.swift:683             reset(endOf: Node.join(left: left.root, separator: separator, right: root))
BTreeCursor.swift:689             reset(root: Node.join(left: root, separator: separator, right: right.root), position: position + c)
BTreeCursor.swift:696             let t1 = Node.join(left: prefix.root, separator: sep1, right: root)
BTreeCursor.swift:697             let t2 = Node.join(left: t1, separator: sep2, right: suffix.root)
BTreeCursor.swift:776             reset(root: Node.join(left: left.root, separator: separator, right: right.root), position: position)
BTreeCursor.swift:813             reset(root: Node.join(left: cut1.left.root, separator: cut2.separator, right: cut2.right.root), position: position)(left left: BTreeNode, separator: (Key, Payload), right: BTreeNode) -> BTreeNode {
0456            precondition(left.order == right.order)
0457            let depthDelta = left.depth - right.depth
0458            let append = depthDelta >= 0
0459            
0460            let stock = append ? left : right
0461            let scion = append ? right : left
0462            // We'll graft the scion onto the stock.
0463    
0464            // First, find the insertion point, and preemptively update node counts on the way there.
0465            var path = [stock]
0466            var node = stock
0467            let c = scion.count
0468            node.count += c + 1
0469            for _ in 0 ..< abs(depthDelta) {
0470                node = node.makeChildUnique(append ? node.children.count - 1 : 0)
0471                path.append(node)
0472                node.count += c + 1
0473            }
0474    
0475            // Graft the scion into the stock by inserting the contents of its root into `node`.
0476            assert(node.isLeaf == scion.isLeaf)
0477            if append {
0478                node.elements.append(separator)
0479                node.elements.appendContentsOf(right.elements)
0480                node.children.appendContentsOf(right.children)
0481            }
0482            else {
0483                node.elements = left.elements + [separator] + node.elements
0484                node.children = left.children + node.children
0485            }
0486    
0487            // Split nodes if necessary to restore balance.
0488            if node.isTooLarge {
0489                path.removeLast()
0490                var splinter = Optional(node.split())
0491                while let s = splinter where !path.isEmpty {
0492                    let node = path.removeLast()
0493                    node.insert(s, inSlot: append ? node.elements.count : 0)
0494                    splinter = node.isTooLarge ? node.split() : nil
0495                }
0496                if let s = splinter {
0497                    return BTreeNode(left: stock, separator: s.separator, right: s.node)
0498                }
0499            }
0500            return stock
0501        }
0502    }
0503    
0504

BTree.swift:12	internal typealias Node = BTreeNode<Key, Payload>
BTreeCursor.swift:106	internal typealias Node = BTreeNode<Key, Payload>
BTreeGenerator.swift:12	typealias Node = BTreeNode<Key, Payload>
BTreeIndex.swift:23	typealias Node = BTreeNode<Key, Payload>
BTreeNode.swift:31	typealias Node = BTreeNode<Key, Payload>
BTreeNode.swift:38	internal var children: Array<BTreeNode>
BTreeNode.swift:51	internal init(order: Int, elements: Array<Element>, children: Array<BTreeNode>, count: Int) {
BTreeNode.swift:65	extension BTreeNode {
BTreeNode.swift:84	internal convenience init(node: BTreeNode, slotRange: Range<Int>) {
BTreeNode.swift:94	extension BTreeNode {
BTreeNode.swift:95	func makeChildUnique(index: Int) -> BTreeNode {
BTreeNode.swift:102	func clone() -> BTreeNode {
BTreeNode.swift:103	return BTreeNode(order: order, elements: elements, children: children, count: count)
BTreeNode.swift:109	extension BTreeNode {
BTreeNode.swift:123	extension BTreeNode: SequenceType {
BTreeNode.swift:171	extension BTreeNode {
BTreeNode.swift:313	extension BTreeNode {
BTreeNode.swift:328	let node: BTreeNode<Key, Payload>
BTreeNode.swift:330	var exploded: (separator: (Key, Payload), node: BTreeNode<Key, Payload>) {
BTreeNode.swift:335	extension BTreeNode {
BTreeNode.swift:353	let node = BTreeNode(node: self, slotRange: median + 1 ..< count)
BTreeNode.swift:374	extension BTreeNode {
BTreeNode.swift:447	extension BTreeNode {
BTreeNode.swift:455	internal static func join(left left: BTreeNode, separator: (Key, Payload), right: BTreeNode) -> BTreeNode {
BTreeNode.swift:455	internal static func join(left left: BTreeNode, separator: (Key, Payload), right: BTreeNode) -> BTreeNode {
BTreeNode.swift:455	internal static func join(left left: BTreeNode, separator: (Key, Payload), right: BTreeNode) -> BTreeNode {
BTreeNode.swift:497	return BTreeNode(left: stock, separator: s.separator, right: s.node)

BTreeNode.swift:36	internal var elements: Array<Element>
BTreeNode.swift:51	internal init(order: Int, elements: Array<Element>, children: Array<BTreeNode>, count: Int) {
BTreeNode.swift:133	func forEach(@noescape body: (Element) throws -> ()) rethrows {
BTreeNode.swift:151	func forEach(@noescape body: (Element) throws -> Bool) rethrows -> Bool {
BTreeNode.swift:172	internal func setElementInSlot(slot: Int, to element: Element) -> Element {
BTreeNode.swift:172	internal func setElementInSlot(slot: Int, to element: Element) -> Element {
BTreeNode.swift:178	internal func insert(element: Element, inSlot slot: Int) {
BTreeNode.swift:183	internal func append(element: Element) {
BTreeNode.swift:188	internal func removeSlot(slot: Int) -> Element {

BTreeNode.swift:70	convenience init(order: Int = Node.defaultOrder) {
BTreeNode.swift:74	internal convenience init(left: Node, separator: (Key, Payload), right: Node) {
BTreeNode.swift:74	internal convenience init(left: Node, separator: (Key, Payload), right: Node) {
BTreeNode.swift:314	internal func edit(@noescape descend descend: Node -> Int?, @noescape ascend: (Node, Int) -> Void) {
BTreeNode.swift:314	internal func edit(@noescape descend descend: Node -> Int?, @noescape ascend: (Node, Int) -> Void) {

BTree.swift:99	return node.elements[index.slots.last!]
BTree.swift:131	return node.elements[slot.index]
BTree.swift:137	return node.elements[position]
BTree.swift:151	return node.elements[m].1
BTree.swift:165	lastmatch = node.elements[m].1
BTree.swift:280	assert(position < node.elements.count)
BTree.swift:335	assert(slot.index == 0 \|\| node.elements[slot.index - 1].0 <= element.0)
BTree.swift:336	assert(slot.index == node.elements.count \|\| node.elements[slot.index].0 >= element.0)
BTree.swift:336	assert(slot.index == node.elements.count \|\| node.elements[slot.index].0 >= element.0)
BTree.swift:390	old = node.elements[slot.index].1
BTree.swift:391	node.elements[slot.index].1 = payload
BTree.swift:552	assert(root.elements.count == 0)
BTree.swift:578	old = node.removeSlot(slot.descend == node.elements.count ? slot.descend - 1 : slot.descend)
BTree.swift:601	assert(root.elements.count == 0)
BTree.swift:648	while seedling.elements.count < keysPerNode {
BTree.swift:652	seedling.elements.append(element)
BTree.swift:656	while !saplings.isEmpty && seedling.elements.count == keysPerNode {
BTree.swift:659	if sapling.depth == seedling.depth + 1 && sapling.elements.count < keysPerNode {
BTree.swift:663	sapling.elements.append(separator)
BTree.swift:668	else if sapling.depth == seedling.depth && sapling.elements.count == keysPerNode {
BTreeCursor.swift:227	let s = node.elements[slot - 1]
BTreeCursor.swift:230	let c = node.elements.count
BTreeCursor.swift:233	let s = node.elements[slot]
BTreeCursor.swift:258	let s = node.elements[slot - 1]
BTreeCursor.swift:279	let c = node.elements.count
BTreeCursor.swift:282	let s = node.elements[slot]
BTreeCursor.swift:341	if slots.last! < node.elements.count - 1 \|\| _position == count {
BTreeCursor.swift:349	} while slots.last! == path.last!.elements.count
BTreeCursor.swift:393	slots.append(node.elements.count - 1)
BTreeCursor.swift:501	else if slot.descend < node.elements.count {
BTreeCursor.swift:525	return path.last!.elements[slots.last!].0
BTreeCursor.swift:529	path.last!.elements[slots.last!].0 = newValue
BTreeCursor.swift:539	return path.last!.elements[slots.last!].1
BTreeCursor.swift:543	path.last!.elements[slots.last!].1 = newValue
BTreeCursor.swift:555	let old = node.elements[slot].1
BTreeCursor.swift:556	node.elements[slot].1 = payload
BTreeCursor.swift:596	assert(node.isLeaf && slots.last == node.elements.count - 1)
BTreeCursor.swift:598	slots[slots.count - 1] = node.elements.count - 1
BTreeCursor.swift:616	if slot > left.elements.count {
BTreeCursor.swift:618	slots[i] = slot - left.elements.count - 1
BTreeCursor.swift:621	else if slot == left.elements.count {
BTreeCursor.swift:634	if slot > left.elements.count {
BTreeCursor.swift:644	slots.insert(slot > left.elements.count ? 1 : 0, atIndex: 0)
BTreeCursor.swift:669	insert(root.elements[0])
BTreeCursor.swift:717	let result = node.elements[slot]
BTreeCursor.swift:729	node.elements.removeAtIndex(slot)
BTreeCursor.swift:745	if node === root && node.elements.count == 0 && node.children.count == 1 {
BTreeGenerator.swift:42	let result = node.elements[index]
BTreeGenerator.swift:55	else if index < node.elements.count - 1 {
BTreeGenerator.swift:62	while !nodePath.isEmpty && indexPath.last == nodePath.last!.elements.count {
BTreeIndex.swift:69	slots.append(direction == .Forward ? 0 : node.elements.count - 1)
BTreeIndex.swift:86	if slots.last! < node.elements.count - 1 {
BTreeIndex.swift:92	while slots.count > 0 && slots.last! == path.last!.value!.elements.count {
BTreeNode.swift:54	self.elements = elements
BTreeNode.swift:85	let elements = Array(node.elements[slotRange])
BTreeNode.swift:103	return BTreeNode(order: order, elements: elements, children: children, count: count)
BTreeNode.swift:116	internal var isTooSmall: Bool { return elements.count < minKeys }
BTreeNode.swift:117	internal var isTooLarge: Bool { return elements.count > maxKeys }
BTreeNode.swift:118	internal var isBalanced: Bool { return elements.count >= minKeys && elements.count <= maxKeys }
BTreeNode.swift:118	internal var isBalanced: Bool { return elements.count >= minKeys && elements.count <= maxKeys }
BTreeNode.swift:135	for element in elements {
BTreeNode.swift:140	for i in 0 ..< elements.count {
BTreeNode.swift:142	try body(elements[i])
BTreeNode.swift:144	try children[elements.count].forEach(body)
BTreeNode.swift:153	for element in elements {
BTreeNode.swift:158	for i in 0 ..< elements.count {
BTreeNode.swift:160	guard try body(elements[i]) else { return false }
BTreeNode.swift:162	guard try children[elements.count].forEach(body) else { return false }
BTreeNode.swift:173	let old = elements[slot]
BTreeNode.swift:174	elements[slot] = element
BTreeNode.swift:179	elements.insert(element, atIndex: slot)
BTreeNode.swift:184	elements.append(element)
BTreeNode.swift:190	return elements.removeAtIndex(slot)
BTreeNode.swift:202	var end = elements.count
BTreeNode.swift:205	if elements[mid].0 < key {
BTreeNode.swift:212	return (start < elements.count && elements[start].0 == key ? start : nil, start)
BTreeNode.swift:212	return (start < elements.count && elements[start].0 == key ? start : nil, start)
BTreeNode.swift:215	var end = elements.count - 1
BTreeNode.swift:218	if elements[mid].0 > key {
BTreeNode.swift:225	return (start >= 0 && elements[start].0 == key ? start : nil, start + 1)
BTreeNode.swift:233	return (index: elements.count, match: true, position: count)
BTreeNode.swift:274	let c = elements.count
BTreeNode.swift:293	let firstKey = elements.first!.0
BTreeNode.swift:294	let lastKey = elements.last!.0
BTreeNode.swift:342	return split(elements.count / 2)
BTreeNode.swift:351	let count = elements.count
BTreeNode.swift:352	let separator = elements[median]
BTreeNode.swift:354	elements.removeRange(median ..< count)
BTreeNode.swift:367	elements.insert(splinter.separator, atIndex: slot)
BTreeNode.swift:380	if slot > 0 && children[slot - 1].elements.count > minKeys {
BTreeNode.swift:383	else if slot < children.count - 1 && children[slot + 1].elements.count > minKeys {
BTreeNode.swift:400	children[slot].elements.insert(elements[slot - 1], atIndex: 0)
BTreeNode.swift:400	children[slot].elements.insert(elements[slot - 1], atIndex: 0)
BTreeNode.swift:408	elements[slot - 1] = children[slot - 1].elements.removeLast()
BTreeNode.swift:408	elements[slot - 1] = children[slot - 1].elements.removeLast()
BTreeNode.swift:417	children[slot].elements.append(elements[slot])
BTreeNode.swift:417	children[slot].elements.append(elements[slot])
BTreeNode.swift:425	elements[slot] = children[slot + 1].elements.removeAtIndex(0)
BTreeNode.swift:425	elements[slot] = children[slot + 1].elements.removeAtIndex(0)
BTreeNode.swift:434	children[slot].elements.append(elements.removeAtIndex(slot))
BTreeNode.swift:434	children[slot].elements.append(elements.removeAtIndex(slot))
BTreeNode.swift:436	children[slot].elements.appendContentsOf(next.elements)
BTreeNode.swift:436	children[slot].elements.appendContentsOf(next.elements)
BTreeNode.swift:478	node.elements.append(separator)
BTreeNode.swift:479	node.elements.appendContentsOf(right.elements)
BTreeNode.swift:479	node.elements.appendContentsOf(right.elements)
BTreeNode.swift:483	node.elements = left.elements + [separator] + node.elements
BTreeNode.swift:483	node.elements = left.elements + [separator] + node.elements
BTreeNode.swift:483	node.elements = left.elements + [separator] + node.elements
BTreeNode.swift:493	node.insert(s, inSlot: append ? node.elements.count : 0)

BTree.swift:133	let child = node.children[slot.index]
BTree.swift:156	node = node.children[slot.descend]
BTree.swift:170	node = node.children[slot.descend]
BTree.swift:195	node = node.children[slot.descend]
BTree.swift:218	let child = node.children[slot.descend]
BTree.swift:222	position += p - (m == slot.descend ? node.children[m].count : 0)
BTree.swift:249	index.expectValid(node.children[slot] === last)
BTree.swift:250	index.expectValid(slot < node.children.count)
BTree.swift:275	let child = node.children[slot.index]
BTree.swift:354	pos = node.children[slot.index + 1].count
BTree.swift:534	pos = node.children[slot.index + 1].count
BTree.swift:546	if node.children[slot].isTooSmall {
BTree.swift:551	if root.children.count == 1 {
BTree.swift:553	root = root.children[0]
BTree.swift:594	if node.children[slot].isTooSmall {
BTree.swift:600	if root.children.count == 1 {
BTree.swift:602	root = root.children[0]
BTree.swift:664	sapling.children.append(seedling)
BTreeCursor.swift:215	if left.children.count == 1 {
BTreeCursor.swift:218	if right.children.count == 1 {
BTreeCursor.swift:250	if left.children.count == 1 {
BTreeCursor.swift:273	if right.children.count == 1 {
BTreeCursor.swift:389	let slot = node.children.count - 1
BTreeCursor.swift:745	if node === root && node.elements.count == 0 && node.children.count == 1 {
BTreeGenerator.swift:28	node = node.children.first!
BTreeGenerator.swift:46	var n = node.children[index + 1]
BTreeGenerator.swift:50	n = n.children.first!
BTreeIndex.swift:61	var node = node ?? path.last!.value!.children[slots.last!]
BTreeIndex.swift:64	let slot = direction == .Forward ? 0 : node.children.count - 1
BTreeIndex.swift:66	node = node.children[slot]
BTreeIndex.swift:78	expectValid(s < p.children.count && p.children[s] === n)
BTreeIndex.swift:78	expectValid(s < p.children.count && p.children[s] === n)
BTreeNode.swift:55	self.children = children
BTreeNode.swift:86	let children = node.isLeaf ? [] : Array(node.children[slotRange.startIndex ... slotRange.endIndex])
BTreeNode.swift:96	guard !isUniquelyReferenced(&children[index]) else { return children[index] }
BTreeNode.swift:96	guard !isUniquelyReferenced(&children[index]) else { return children[index] }
BTreeNode.swift:97	let clone = children[index].clone()
BTreeNode.swift:98	children[index] = clone
BTreeNode.swift:103	return BTreeNode(order: order, elements: elements, children: children, count: count)
BTreeNode.swift:115	internal var isLeaf: Bool { return children.isEmpty }
BTreeNode.swift:141	try children[i].forEach(body)
BTreeNode.swift:144	try children[elements.count].forEach(body)
BTreeNode.swift:159	guard try children[i].forEach(body) else { return false }
BTreeNode.swift:162	guard try children[elements.count].forEach(body) else { return false }
BTreeNode.swift:240	for i in 0 ..< children.count - 1 {
BTreeNode.swift:241	let c = children[i].count
BTreeNode.swift:250	let c = children.last!.count
BTreeNode.swift:252	return (index: children.count - 1, match: false, position: count)
BTreeNode.swift:256	for i in (1 ..< children.count).reverse() {
BTreeNode.swift:257	let c = children[i].count
BTreeNode.swift:266	let c = children.first!.count
BTreeNode.swift:283	return children[0...slot].reduce(slot) { $0 + $1.count }
BTreeNode.swift:285	return count - children[slot + 1 ... c].reduce(c - slot) { $0 + $1.count }
BTreeNode.swift:359	children.removeRange(median + 1 ..< count + 1)
BTreeNode.swift:360	self.count = median + children.reduce(0, combine: { $0 + $1.count })
BTreeNode.swift:368	children.insert(splinter.node, atIndex: slot + 1)
BTreeNode.swift:379	assert(!isLeaf && children[slot].isTooSmall)
BTreeNode.swift:380	if slot > 0 && children[slot - 1].elements.count > minKeys {
BTreeNode.swift:383	else if slot < children.count - 1 && children[slot + 1].elements.count > minKeys {
BTreeNode.swift:383	else if slot < children.count - 1 && children[slot + 1].elements.count > minKeys {
BTreeNode.swift:400	children[slot].elements.insert(elements[slot - 1], atIndex: 0)
BTreeNode.swift:401	if !children[slot].isLeaf {
BTreeNode.swift:402	let lastGrandChildBeforeSlot = children[slot - 1].children.removeLast()
BTreeNode.swift:402	let lastGrandChildBeforeSlot = children[slot - 1].children.removeLast()
BTreeNode.swift:403	children[slot].children.insert(lastGrandChildBeforeSlot, atIndex: 0)
BTreeNode.swift:403	children[slot].children.insert(lastGrandChildBeforeSlot, atIndex: 0)
BTreeNode.swift:405	children[slot - 1].count -= lastGrandChildBeforeSlot.count
BTreeNode.swift:406	children[slot].count += lastGrandChildBeforeSlot.count
BTreeNode.swift:408	elements[slot - 1] = children[slot - 1].elements.removeLast()
BTreeNode.swift:409	children[slot - 1].count -= 1
BTreeNode.swift:410	children[slot].count += 1
BTreeNode.swift:414	assert(slot < children.count - 1)
BTreeNode.swift:417	children[slot].elements.append(elements[slot])
BTreeNode.swift:418	if !children[slot].isLeaf {
BTreeNode.swift:419	let firstGrandChildAfterSlot = children[slot + 1].children.removeAtIndex(0)
BTreeNode.swift:419	let firstGrandChildAfterSlot = children[slot + 1].children.removeAtIndex(0)
BTreeNode.swift:420	children[slot].children.append(firstGrandChildAfterSlot)
BTreeNode.swift:420	children[slot].children.append(firstGrandChildAfterSlot)
BTreeNode.swift:422	children[slot + 1].count -= firstGrandChildAfterSlot.count
BTreeNode.swift:423	children[slot].count += firstGrandChildAfterSlot.count
BTreeNode.swift:425	elements[slot] = children[slot + 1].elements.removeAtIndex(0)
BTreeNode.swift:426	children[slot].count += 1
BTreeNode.swift:427	children[slot + 1].count -= 1
BTreeNode.swift:431	assert(slot < children.count - 1)
BTreeNode.swift:433	let next = children.removeAtIndex(slot + 1)
BTreeNode.swift:434	children[slot].elements.append(elements.removeAtIndex(slot))
BTreeNode.swift:435	children[slot].count += 1
BTreeNode.swift:436	children[slot].elements.appendContentsOf(next.elements)
BTreeNode.swift:437	children[slot].count += next.count
BTreeNode.swift:439	children[slot].children.appendContentsOf(next.children)
BTreeNode.swift:439	children[slot].children.appendContentsOf(next.children)
BTreeNode.swift:439	children[slot].children.appendContentsOf(next.children)
BTreeNode.swift:441	assert(children[slot].isBalanced)
BTreeNode.swift:470	node = node.makeChildUnique(append ? node.children.count - 1 : 0)
BTreeNode.swift:480	node.children.appendContentsOf(right.children)
BTreeNode.swift:480	node.children.appendContentsOf(right.children)
BTreeNode.swift:484	node.children = left.children + node.children
BTreeNode.swift:484	node.children = left.children + node.children
BTreeNode.swift:484	node.children = left.children + node.children

BTree.swift:54	public var isEmpty: Bool { return root.count == 0 }
BTree.swift:91	return root.count
BTree.swift:134	position -= slot.position - child.count
BTree.swift:222	position += p - (m == slot.descend ? node.children[m].count : 0)
BTree.swift:225	position += node.positionOfSlot(slot.descend) - child.count
BTree.swift:277	position -= slot.position - child.count
BTree.swift:334	let slot = node.slotOfPosition(node.count - pos)
BTree.swift:339	pos -= node.count - slot.position
BTree.swift:354	pos = node.children[slot.index + 1].count
BTree.swift:359	node.count += 1
BTree.swift:384	let slot = node.slotOfPosition(node.count - pos)
BTree.swift:387	pos -= node.count - slot.position
BTree.swift:423	node.count += 1
BTree.swift:486	node.count += 1
BTree.swift:517	let slot = node.slotOfPosition(node.count - pos)
BTree.swift:521	pos -= node.count - slot.position
BTree.swift:534	pos = node.children[slot.index + 1].count
BTree.swift:539	node.count -= 1
BTree.swift:589	node.count -= 1
BTree.swift:653	seedling.count += 1
BTree.swift:665	sapling.count += seedling.count + 1
BTree.swift:665	sapling.count += seedling.count + 1
BTree.swift:684	assert(seedling.count == 0)
BTreeCursor.swift:151	self.count = root.count
BTreeCursor.swift:152	self._position = root.count
BTreeCursor.swift:161	self.count = root.count
BTreeCursor.swift:162	self._position = root.count
BTreeCursor.swift:172	reset(root: root, position: root.count)
BTreeCursor.swift:176	precondition(position >= 0 && position <= root.count)
BTreeCursor.swift:197	node.count += childCount
BTreeCursor.swift:198	childCount = node.count
BTreeCursor.swift:200	assert(root.count == count)
BTreeCursor.swift:304	self._position += node.count - node.positionOfSlot(slot)
BTreeCursor.swift:311	parent.count += child.count
BTreeCursor.swift:311	parent.count += child.count
BTreeCursor.swift:320	parent.count -= child.count
BTreeCursor.swift:320	parent.count -= child.count
BTreeCursor.swift:328	self._position -= node.count - p
BTreeCursor.swift:409	while self.count > self.position + path.last!.count {
BTreeCursor.swift:428	while position < self.position - path.last!.count \|\| position >= self.position {
BTreeCursor.swift:461	assert(position >= self.position - path.last!.count && position <= self.position)
BTreeCursor.swift:464	var slot = node.slotOfPosition(position - (self.position - node.count))
BTreeCursor.swift:468	slot = node.slotOfPosition(position - (self.position - node.count))
BTreeCursor.swift:633	parent.count += left.count + right.count + 1
BTreeCursor.swift:633	parent.count += left.count + right.count + 1
BTreeCursor.swift:633	parent.count += left.count + right.count + 1
BTreeCursor.swift:651	path[i].count -= path[i + 1].count
BTreeCursor.swift:651	path[i].count -= path[i + 1].count
BTreeCursor.swift:666	let c = root.count
BTreeCursor.swift:730	node.count -= 1
BTreeGenerator.swift:18	if root.count == 0 {
BTreeNode.swift:56	self.count = count
BTreeNode.swift:81	count: left.count + 1 + right.count)
BTreeNode.swift:81	count: left.count + 1 + right.count)
BTreeNode.swift:87	let count = children.reduce(elements.count) { $0 + $1.count }
BTreeNode.swift:103	return BTreeNode(order: order, elements: elements, children: children, count: count)
BTreeNode.swift:126	var isEmpty: Bool { return count == 0 }
BTreeNode.swift:180	count += 1
BTreeNode.swift:185	count += 1
BTreeNode.swift:189	count -= 1
BTreeNode.swift:231	assert(position >= 0 && position <= count)
BTreeNode.swift:232	if position == count {
BTreeNode.swift:233	return (index: elements.count, match: true, position: count)
BTreeNode.swift:238	else if position <= count / 2 {
BTreeNode.swift:241	let c = children[i].count
BTreeNode.swift:250	let c = children.last!.count
BTreeNode.swift:251	precondition(count == p + c, "Invalid B-Tree")
BTreeNode.swift:252	return (index: children.count - 1, match: false, position: count)
BTreeNode.swift:255	var p = count
BTreeNode.swift:257	let c = children[i].count
BTreeNode.swift:266	let c = children.first!.count
BTreeNode.swift:280	return count
BTreeNode.swift:283	return children[0...slot].reduce(slot) { $0 + $1.count }
BTreeNode.swift:285	return count - children[slot + 1 ... c].reduce(c - slot) { $0 + $1.count }
BTreeNode.swift:285	return count - children[slot + 1 ... c].reduce(c - slot) { $0 + $1.count }
BTreeNode.swift:356	self.count = median
BTreeNode.swift:360	self.count = median + children.reduce(0, combine: { $0 + $1.count })
BTreeNode.swift:360	self.count = median + children.reduce(0, combine: { $0 + $1.count })
BTreeNode.swift:405	children[slot - 1].count -= lastGrandChildBeforeSlot.count
BTreeNode.swift:405	children[slot - 1].count -= lastGrandChildBeforeSlot.count
BTreeNode.swift:406	children[slot].count += lastGrandChildBeforeSlot.count
BTreeNode.swift:406	children[slot].count += lastGrandChildBeforeSlot.count
BTreeNode.swift:409	children[slot - 1].count -= 1
BTreeNode.swift:410	children[slot].count += 1
BTreeNode.swift:422	children[slot + 1].count -= firstGrandChildAfterSlot.count
BTreeNode.swift:422	children[slot + 1].count -= firstGrandChildAfterSlot.count
BTreeNode.swift:423	children[slot].count += firstGrandChildAfterSlot.count
BTreeNode.swift:423	children[slot].count += firstGrandChildAfterSlot.count
BTreeNode.swift:426	children[slot].count += 1
BTreeNode.swift:427	children[slot + 1].count -= 1
BTreeNode.swift:435	children[slot].count += 1
BTreeNode.swift:437	children[slot].count += next.count
BTreeNode.swift:437	children[slot].count += next.count
BTreeNode.swift:467	let c = scion.count
BTreeNode.swift:468	node.count += c + 1
BTreeNode.swift:472	node.count += c + 1

BTreeNode.swift:49	internal var order: Int { return numericCast(_order) }
BTreeNode.swift:53	self._order = numericCast(order)

BTreeNode.swift:48	internal var depth: Int { return numericCast(_depth) }
BTreeNode.swift:57	self._depth = (children.count == 0 ? 0 : children[0]._depth + 1)
BTreeNode.swift:57	self._depth = (children.count == 0 ? 0 : children[0]._depth + 1)
BTreeNode.swift:59	assert(children.indexOf { $0._depth + 1 != self._depth } == nil)
BTreeNode.swift:59	assert(children.indexOf { $0._depth + 1 != self._depth } == nil)

BTree.swift:30	public var depth: Int { return root.depth }
BTree.swift:658	assert(sapling.depth >= seedling.depth)
BTree.swift:658	assert(sapling.depth >= seedling.depth)
BTree.swift:659	if sapling.depth == seedling.depth + 1 && sapling.elements.count < keysPerNode {
BTree.swift:659	if sapling.depth == seedling.depth + 1 && sapling.elements.count < keysPerNode {
BTree.swift:668	else if sapling.depth == seedling.depth && sapling.elements.count == keysPerNode {
BTree.swift:668	else if sapling.depth == seedling.depth && sapling.elements.count == keysPerNode {
BTreeGenerator.swift:25	path.reserveCapacity(node.depth + 1)
BTreeIndex.swift:41	path.reserveCapacity(root.depth + 1)
BTreeNode.swift:76	assert(left.depth == right.depth)
BTreeNode.swift:76	assert(left.depth == right.depth)
BTreeNode.swift:362	assert(node.depth == self.depth)
BTreeNode.swift:362	assert(node.depth == self.depth)
BTreeNode.swift:457	let depthDelta = left.depth - right.depth
BTreeNode.swift:457	let depthDelta = left.depth - right.depth

BTree.swift:28	public var order: Int { return root.order }
BTreeCursor.swift:762	if n == count { reset(Node(order: root.order)); return }
BTreeCursor.swift:788	return Tree(order: root.order)
BTreeCursor.swift:792	var tree = Tree(order: root.order)
BTreeCursor.swift:798	reset(Node(order: tree.root.order))
BTreeNode.swift:75	assert(left.order == right.order)
BTreeNode.swift:75	assert(left.order == right.order)
BTreeNode.swift:78	order: left.order,
BTreeNode.swift:88	self.init(order: node.order, elements: elements, children: children, count: count)
BTreeNode.swift:103	return BTreeNode(order: order, elements: elements, children: children, count: count)
BTreeNode.swift:110	internal var maxChildren: Int { return order }
BTreeNode.swift:456	precondition(left.order == right.order)
BTreeNode.swift:456	precondition(left.order == right.order)

BTreeNode.swift:71	self.init(order: order, elements: [], children: [], count: 0)
BTreeNode.swift:77	self.init(
BTreeNode.swift:88	self.init(order: node.order, elements: elements, children: children, count: count)
BTreeNode.swift:103	return BTreeNode(order: order, elements: elements, children: children, count: count)

BTree.swift:23	public init(order: Int = Node.defaultOrder) {
BTree.swift:619	public init<S: SequenceType where S.Generator.Element == Element>(sortedElements elements: S, order: Int = Node.defaultOrder, fillFactor: Double = 1) {
BTree.swift:704	public init<S: SequenceType where S.Generator.Element == Element>(elements: S, order: Int = Node.defaultOrder, fillFactor: Double = 1) {
BTreeNode.swift:70	convenience init(order: Int = Node.defaultOrder) {

BTree.swift:24	self.root = Node(order: order)
BTree.swift:638	var seedling = Node(order: order)
BTree.swift:679	seedling = Node(order: order)
BTreeCursor.swift:25	root = Node()
BTreeCursor.swift:61	root = Node()
BTreeCursor.swift:76	root = Node()
BTreeCursor.swift:293	self.root = Node()
BTreeCursor.swift:762	if n == count { reset(Node(order: root.order)); return }
BTreeCursor.swift:798	reset(Node(order: tree.root.order))

BTree.swift:367	root = Node(left: root, separator: s.separator, right: s.node)
BTree.swift:431	root = Node(left: root, separator: s.separator, right: s.node)
BTree.swift:495	root = Node(left: root, separator: s.separator, right: s.node)
BTree.swift:672	seedling = Node(left: sapling, separator: separator, right: seedling)
BTreeCursor.swift:642	self.root = Node(left: left, separator: splinter.separator, right: right)
BTreeNode.swift:497	return BTreeNode(left: stock, separator: s.separator, right: s.node)

BTreeCursor.swift:226	let l = slot == 1 ? node.makeChildUnique(0) : Node(node: node, slotRange: 0 ..< slot - 1)
BTreeCursor.swift:232	let r = slot == c - 1 ? node.makeChildUnique(c) : Node(node: node, slotRange: slot + 1 ..< c)
BTreeCursor.swift:257	let l = slot == 1 ? node.makeChildUnique(0) : Node(node: node, slotRange: 0 ..< slot - 1)
BTreeCursor.swift:281	let r = slot == c - 1 ? node.makeChildUnique(c) : Node(node: node, slotRange: slot + 1 ..< c)
BTreeNode.swift:353	let node = BTreeNode(node: self, slotRange: median + 1 ..< count)

BTreeCursor.swift:216	left = left.makeChildUnique(0)
BTreeCursor.swift:219	right = right.makeChildUnique(0)
BTreeCursor.swift:226	let l = slot == 1 ? node.makeChildUnique(0) : Node(node: node, slotRange: 0 ..< slot - 1)
BTreeCursor.swift:232	let r = slot == c - 1 ? node.makeChildUnique(c) : Node(node: node, slotRange: slot + 1 ..< c)
BTreeCursor.swift:251	left = left.makeChildUnique(0)
BTreeCursor.swift:257	let l = slot == 1 ? node.makeChildUnique(0) : Node(node: node, slotRange: 0 ..< slot - 1)
BTreeCursor.swift:274	right = right.makeChildUnique(0)
BTreeCursor.swift:281	let r = slot == c - 1 ? node.makeChildUnique(c) : Node(node: node, slotRange: slot + 1 ..< c)
BTreeCursor.swift:319	let child = parent.makeChildUnique(slot)
BTreeCursor.swift:747	root = node.makeChildUnique(0)
BTreeNode.swift:317	let child = makeChildUnique(slot)
BTreeNode.swift:398	makeChildUnique(slot)
BTreeNode.swift:399	makeChildUnique(slot - 1)
BTreeNode.swift:415	makeChildUnique(slot)
BTreeNode.swift:416	makeChildUnique(slot + 1)
BTreeNode.swift:432	makeChildUnique(slot)
BTreeNode.swift:470	node = node.makeChildUnique(append ? node.children.count - 1 : 0)

BTree.swift:44	root = root.clone()
BTreeCursor.swift:660	let root = tree.root.clone()
BTreeNode.swift:97	let clone = children[index].clone()

BTreeNode.swift:111	internal var minChildren: Int { return (maxChildren + 1) / 2 }
BTreeNode.swift:112	internal var maxKeys: Int { return maxChildren - 1 }

BTreeNode.swift:117	internal var isTooLarge: Bool { return elements.count > maxKeys }
BTreeNode.swift:118	internal var isBalanced: Bool { return elements.count >= minKeys && elements.count <= maxKeys }

BTreeNode.swift:116	internal var isTooSmall: Bool { return elements.count < minKeys }
BTreeNode.swift:118	internal var isBalanced: Bool { return elements.count >= minKeys && elements.count <= maxKeys }
BTreeNode.swift:380	if slot > 0 && children[slot - 1].elements.count > minKeys {
BTreeNode.swift:383	else if slot < children.count - 1 && children[slot + 1].elements.count > minKeys {

BTree.swift:128	while !node.isLeaf {
BTree.swift:153	if node.isLeaf {
BTree.swift:167	if node.isLeaf {
BTree.swift:192	if node.isLeaf {
BTree.swift:216	while !node.isLeaf {
BTree.swift:269	while !node.isLeaf {
BTree.swift:342	else if node.isLeaf {
BTree.swift:413	if !node.isLeaf {
BTree.swift:449	if node.isLeaf {
BTree.swift:520	assert(!node.isLeaf)
BTree.swift:524	else if node.isLeaf {
BTree.swift:572	if node.isLeaf {
BTreeCursor.swift:340	if node.isLeaf {
BTreeCursor.swift:356	while !node.isLeaf {
BTreeCursor.swift:372	if node.isLeaf {
BTreeCursor.swift:386	assert(!path.last!.isLeaf)
BTreeCursor.swift:388	while !node.isLeaf {
BTreeCursor.swift:487	if node.isLeaf \|\| selector == .Any {
BTreeCursor.swift:493	if node.isLeaf {
BTreeCursor.swift:566	if path.last!.isLeaf {
BTreeCursor.swift:576	assert(node.isLeaf && slots.last == 0)
BTreeCursor.swift:588	if path.last!.isLeaf {
BTreeCursor.swift:596	assert(node.isLeaf && slots.last == node.elements.count - 1)
BTreeCursor.swift:718	if !node.isLeaf {
BTreeGenerator.swift:27	while !node.isLeaf {
BTreeGenerator.swift:43	if !node.isLeaf {
BTreeGenerator.swift:49	while !n.isLeaf {
BTreeIndex.swift:63	while !node.isLeaf {
BTreeIndex.swift:85	if node.isLeaf {
BTreeIndex.swift:110	if node.isLeaf {
BTreeNode.swift:86	let children = node.isLeaf ? [] : Array(node.children[slotRange.startIndex ... slotRange.endIndex])
BTreeNode.swift:134	if isLeaf {
BTreeNode.swift:152	if isLeaf {
BTreeNode.swift:235	if isLeaf {
BTreeNode.swift:276	guard !isLeaf else {
BTreeNode.swift:355	if isLeaf {
BTreeNode.swift:379	assert(!isLeaf && children[slot].isTooSmall)
BTreeNode.swift:401	if !children[slot].isLeaf {
BTreeNode.swift:418	if !children[slot].isLeaf {
BTreeNode.swift:438	if !next.isLeaf {
BTreeNode.swift:476	assert(node.isLeaf == scion.isLeaf)
BTreeNode.swift:476	assert(node.isLeaf == scion.isLeaf)

BTree.swift:345	if node.isTooLarge {
BTree.swift:362	splinter = node.isTooLarge ? node.split() : nil
BTree.swift:417	if node.isTooLarge {
BTree.swift:426	splinter = node.isTooLarge ? node.split() : nil
BTree.swift:458	if node.isTooLarge {
BTree.swift:489	splinter = node.isTooLarge ? node.split() : nil
BTreeCursor.swift:606	guard path.last!.isTooLarge else { return }
BTreeCursor.swift:610	while path[i].isTooLarge {
BTreeNode.swift:341	assert(isTooLarge)
BTreeNode.swift:488	if node.isTooLarge {
BTreeNode.swift:494	splinter = node.isTooLarge ? node.split() : nil

BTreeNode.swift:30	typealias Element = Generator.Element
BTreeNode.swift:128	func generate() -> Generator {

BTree.swift:63	try root.forEach(body)
BTreeNode.swift:141	try children[i].forEach(body)
BTreeNode.swift:144	try children[elements.count].forEach(body)

BTree.swift:70	return try root.forEach(body)
BTreeNode.swift:159	guard try children[i].forEach(body) else { return false }
BTreeNode.swift:162	guard try children[elements.count].forEach(body) else { return false }

BTree.swift:353	element = node.setElementInSlot(slot.index, to: element)
BTree.swift:452	old = node.setElementInSlot(m, to: element).1
BTree.swift:467	old = node.setElementInSlot(m, to: element).1
BTree.swift:480	old = node.setElementInSlot(m.slot, to: element).1
BTree.swift:543	old = node.setElementInSlot(m.slot, to: old!)
BTree.swift:591	old = node.setElementInSlot(m.slot, to: o)

BTree.swift:344	node.insert(element, inSlot: slot.index)
BTree.swift:416	node.insert(element, inSlot: slot.descend)
BTree.swift:457	node.insert(element, inSlot: slot.descend)
BTreeCursor.swift:569	node.insert(element, inSlot: slot + 1)
BTreeCursor.swift:577	node.insert(element, inSlot: 0)
BTreeCursor.swift:591	node.insert(element, inSlot: slot)

BTree.swift:526	old = node.removeSlot(slot.index)
BTree.swift:574	old = node.removeSlot(m)
BTree.swift:578	old = node.removeSlot(slot.descend == node.elements.count ? slot.descend - 1 : slot.descend)

BTree.swift:149	let slot = node.slotOf(key, choosing: .First)
BTree.swift:163	let slot = node.slotOf(key, choosing: selector)
BTree.swift:187	let slot = node.slotOf(key, choosing: selector)
BTree.swift:217	let slot = node.slotOf(key, choosing: selector)
BTree.swift:229	let slot = node.slotOf(key, choosing: selector)
BTree.swift:412	let slot = node.slotOf(element.0, choosing: selector)
BTree.swift:448	let slot = node.slotOf(element.0, choosing: selector)
BTree.swift:571	let slot = node.slotOf(key, choosing: selector)
BTreeCursor.swift:485	let slot = node.slotOf(key, choosing: selector)

BTree.swift:129	let slot = node.slotOfPosition(position)
BTree.swift:270	let slot = node.slotOfPosition(position)
BTree.swift:334	let slot = node.slotOfPosition(node.count - pos)
BTree.swift:384	let slot = node.slotOfPosition(node.count - pos)
BTree.swift:517	let slot = node.slotOfPosition(node.count - pos)
BTreeCursor.swift:464	var slot = node.slotOfPosition(position - (self.position - node.count))
BTreeCursor.swift:468	slot = node.slotOfPosition(position - (self.position - node.count))