0001    //
0002    //  BTreeCursor.swift
0003    //  BTree
0004    //
0005    //  Created by Károly Lőrentey on 2016-02-12.
0006    //  Copyright © 2015–2016 Károly Lőrentey.
0007    //
0008    
0009    //MARK: Cursors
0010    
0011    extension BTree {
0012        public typealias CursorBTreeCursor.swift:20     public mutating func withCursorAtPosition(position: Int, @noescape body: Cursor throws -> Void) rethrows {
BTreeCursor.swift:36     public mutating func withCursorAtStart(@noescape body: Cursor throws -> Void) rethrows {
BTreeCursor.swift:46     public mutating func withCursorAtEnd(@noescape body: Cursor throws -> Void) rethrows {
BTreeCursor.swift:57     public mutating func withCursorAt(key: Key, choosing selector: BTreeKeySelector = .Any, @noescape body: Cursor throws -> Void) rethrows {
BTreeCursor.swift:72     public mutating func withCursorAt(index: Index, @noescape body: Cursor throws -> Void) rethrows { = BTreeCursor<Key, Payload>
0013    
0014        /// Call `body` with a cursor at `position` in this tree.
0015        ///
0016        /// - Warning: Do not rely on anything about `self` (the `BTree` that is the target of this method) during the
0017        ///   execution of body: it will not appear to have the correct value.
0018        ///   Instead, use only the supplied cursor to manipulate the tree.
0019        ///
0020        public mutating func withCursorAtPositionBTreeCursor.swift:37         try withCursorAtPosition(0, body: body)
BTreeCursor.swift:47         try withCursorAtPosition(count, body: body)
List.swift:274         tree.withCursorAtPosition(tree.count) { cursor in
List.swift:283         tree.withCursorAtPosition(tree.count) { cursor in
List.swift:292         tree.withCursorAtPosition(index) { cursor in
List.swift:298         tree.withCursorAtPosition(index) { cursor in
List.swift:315         tree.withCursorAtPosition(0) { cursor in
List.swift:327         tree.withCursorAtPosition(count - n) { cursor in
List.swift:344         tree.withCursorAtPosition(range.startIndex) { cursor in
List.swift:355         tree.withCursorAtPosition(range.startIndex) { cursor in(position: Int, @noescape body: Cursor throws -> Void) rethrows {
0021            precondition(position >= 0 && position <= count)
0022            makeUnique()
0023            let cursor = BTreeCursor(root)
0024            cursor.descendToPosition(position)
0025            root = Node()
0026            defer { self = cursor.finish() }
0027            try body(cursor)
0028        }
0029    
0030        /// Call `body` with a cursor at the start of this tree.
0031        ///
0032        /// - Warning: Do not rely on anything about `self` (the `BTree` that is the target of this method) during the
0033        ///   execution of body: it will not appear to have the correct value.
0034        ///   Instead, use only the supplied cursor to manipulate the tree.
0035        ///
0036        public mutating func withCursorAtStart(@noescape body: Cursor throws -> Void) rethrows {
0037            try withCursorAtPosition(0, body: body)
0038        }
0039    
0040        /// Call `body` with a cursor at the end of this tree.
0041        ///
0042        /// - Warning: Do not rely on anything about `self` (the `BTree` that is the target of this method) during the
0043        ///   execution of body: it will not appear to have the correct value.
0044        ///   Instead, use only the supplied cursor to manipulate the tree.
0045        ///
0046        public mutating func withCursorAtEnd(@noescape body: Cursor throws -> Void) rethrows {
0047            try withCursorAtPosition(count, body: body)
0048        }
0049    
0050        /// Call `body` with a cursor positioned at `key` in this tree.
0051        /// If there are multiple elements with the same key, `selector` indicates which matching element to find.
0052        ///
0053        /// - Warning: Do not rely on anything about `self` (the `BTree` that is the target of this method) during the
0054        ///   execution of body: it will not appear to have the correct value.
0055        ///   Instead, use only the supplied cursor to manipulate the tree.
0056        ///
0057        public mutating func withCursorAt(key: Key, choosing selector: BTreeKeySelector = .Any, @noescape body: Cursor throws -> Void) rethrows {
0058            makeUnique()
0059            let cursor = BTreeCursor(root)
0060            cursor.descendToKey(key, choosing: selector)
0061            root = Node()
0062            defer { self = cursor.finish() }
0063            try body(cursor)
0064        }
0065    
0066        /// Call `body` with a cursor positioned at `index` in this tree.
0067        ///
0068        /// - Warning: Do not rely on anything about `self` (the `BTree` that is the target of this method) during the
0069        ///   execution of body: it will not appear to have the correct value.
0070        ///   Instead, use only the supplied cursor to manipulate the tree.
0071        ///
0072        public mutating func withCursorAt(index: Index, @noescape body: Cursor throws -> Void) rethrows {
0073            makeUnique()
0074            let cursor = BTreeCursor(root)
0075            cursor.descendToSlots(index.slots)
0076            root = Node()
0077            defer { self = cursor.finish() }
0078            try body(cursor)
0079        }
0080    }
0081    
0082    private enum WalkDirection {
0083        case Forward
0084        case Backward
0085    }
0086    
0087    /// A stateful editing interface for efficiently inserting/removing/updating a range of elements in a b-tree.
0088    ///
0089    /// Creating a cursor over a tree takes exclusive ownership of it; the tree is in a transient invalid state
0090    /// while the cursor is active. (In particular, element counts are not finalized until the cursor is deactivated.)
0091    ///
0092    /// The cursor always focuses on a particular spot on the tree: either a particular element, or the empty spot after 
0093    /// the last element. There are methods to move the cursor to the next or previous element, to modify the currently 
0094    /// focused element, to insert a new element before the current position, and to remove the currently focused element
0095    /// from the tree.
0096    ///
0097    /// Note that the cursor does not verify that keys you insert/modify uphold tree invariants -- it is your responsibility
0098    /// to guarantee keys remain in ascending order while you're working with the cursor.
0099    ///
0100    /// Creating a cursor takes O(log(*n*)) steps; once the cursor has been created, the complexity of most manipulations
0101    /// is amortized O(1). For example, appending *k* new elements without a cursor takes O(*k* * log(*n*)) steps;
0102    /// using a cursor to do the same only takes O(log(*n*) + *k*).
0103    public final class BTreeCursorBTreeCursor.swift:12     public typealias Cursor = BTreeCursor<Key, Payload>
BTreeCursor.swift:23         let cursor = BTreeCursor(root)
BTreeCursor.swift:59         let cursor = BTreeCursor(root)
BTreeCursor.swift:74         let cursor = BTreeCursor(root)<KeyBTreeCursor.swift:104     public typealias Element = (Key, Payload)
BTreeCursor.swift:105     public typealias Tree = BTree<Key, Payload>
BTreeCursor.swift:106     internal typealias Node = BTreeNode<Key, Payload>
BTreeCursor.swift:181     internal func reset(root root: Node, key: Key, choosing selector: BTreeKeySelector = .Any) {
BTreeCursor.swift:440     public func moveToKey(key: Key, choosing selector: BTreeKeySelector = .Any) {
BTreeCursor.swift:475     private func descendToKey(key: Key, choosing selector: BTreeKeySelector) {
BTreeCursor.swift:522     public var key: Key {: Comparable, PayloadBTreeCursor.swift:104     public typealias Element = (Key, Payload)
BTreeCursor.swift:105     public typealias Tree = BTree<Key, Payload>
BTreeCursor.swift:106     internal typealias Node = BTreeNode<Key, Payload>
BTreeCursor.swift:536     public var payload: Payload {
BTreeCursor.swift:551     public func setPayload(payload: Payload) -> Payload {
BTreeCursor.swift:551     public func setPayload(payload: Payload) -> Payload {> {
0104        public typealias ElementBTreeCursor.swift:210     internal func finishByCutting() -> (left: Tree, separator: Element, right: Tree) {
BTreeCursor.swift:563     public func insertAfter(element: Element) {
BTreeCursor.swift:585     public func insert(element: Element) {
BTreeCursor.swift:706     public func insert<S: SequenceType where S.Generator.Element == Element>(elements: S) {
BTreeCursor.swift:713     public func remove() -> Element { = (Key, Payload)
0105        public typealias TreeBTreeCursor.swift:193     internal func finish() -> Tree {
BTreeCursor.swift:202         return Tree(root)
BTreeCursor.swift:210     internal func finishByCutting() -> (left: Tree, separator: Element, right: Tree) {
BTreeCursor.swift:210     internal func finishByCutting() -> (left: Tree, separator: Element, right: Tree) {
BTreeCursor.swift:238         return (Tree(left), separator, Tree(right))
BTreeCursor.swift:238         return (Tree(left), separator, Tree(right))
BTreeCursor.swift:246     internal func finishAndKeepPrefix() -> Tree {
BTreeCursor.swift:262         return Tree(left)
BTreeCursor.swift:270     internal func finishAndKeepSuffix() -> Tree {
BTreeCursor.swift:286         return Tree(right)
BTreeCursor.swift:659     public func insert(tree: Tree) {
BTreeCursor.swift:785     public func extract(n: Int) -> Tree {
BTreeCursor.swift:788             return Tree(order: root.order)
BTreeCursor.swift:792             var tree = Tree(order: root.order) = BTree<Key, Payload>
0106        internal typealias NodeBTreeCursor.swift:110     private var root: Node
BTreeCursor.swift:118     private var path: [Node]
BTreeCursor.swift:149     private init(_ root: Node) {
BTreeCursor.swift:159     private func reset(root: Node) {
BTreeCursor.swift:167     internal func reset(startOf root: Node) {
BTreeCursor.swift:171     internal func reset(endOf root: Node) {
BTreeCursor.swift:175     internal func reset(root root: Node, position: Int) {
BTreeCursor.swift:181     internal func reset(root root: Node, key: Key, choosing selector: BTreeKeySelector = .Any) {
BTreeCursor.swift:226                 let l = slot == 1 ? node.makeChildUnique(0) : Node(node: node, slotRange: 0 ..< slot - 1)
BTreeCursor.swift:228                 left = Node.join(left: l, separator: s, right: left)
BTreeCursor.swift:232                 let r = slot == c - 1 ? node.makeChildUnique(c) : Node(node: node, slotRange: slot + 1 ..< c)
BTreeCursor.swift:234                 right = Node.join(left: right, separator: s, right: r)
BTreeCursor.swift:257                 let l = slot == 1 ? node.makeChildUnique(0) : Node(node: node, slotRange: 0 ..< slot - 1)
BTreeCursor.swift:259                 left = Node.join(left: l, separator: s, right: left)
BTreeCursor.swift:281                 let r = slot == c - 1 ? node.makeChildUnique(c) : Node(node: node, slotRange: slot + 1 ..< c)
BTreeCursor.swift:283                 right = Node.join(left: right, separator: s, right: r)
BTreeCursor.swift:293         self.root = Node()
BTreeCursor.swift:307     private func popFromPath() -> Node {
BTreeCursor.swift:315     private func pushToPath() -> Node {
BTreeCursor.swift:642                 self.root = Node(left: left, separator: splinter.separator, right: right)
BTreeCursor.swift:664     private func insertWithoutCloning(root: Node) {
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:762         if n == count { reset(Node(order: root.order)); return }
BTreeCursor.swift:776             reset(root: Node.join(left: left.root, separator: separator, right: right.root), position: position)
BTreeCursor.swift:798             reset(Node(order: tree.root.order))
BTreeCursor.swift:813             reset(root: Node.join(left: cut1.left.root, separator: cut2.separator, right: cut2.right.root), position: position) = BTreeNode<Key, Payload>
0107    
0108        /// The root node in the tree that is being edited. Note that this isn't a valid b-tree while the cursor is active:
0109        /// each node on the current path has an invalid `count` field. (Other b-tree invariants are kept, though.)
0110        private var rootBTreeCursor.swift:150         self.root = root
BTreeCursor.swift:160         self.root = root
BTreeCursor.swift:200         assert(root.count == count)
BTreeCursor.swift:202         return Tree(root)
BTreeCursor.swift:293         self.root = Node()
BTreeCursor.swift:642                 self.root = Node(left: left, separator: splinter.separator, right: right)
BTreeCursor.swift:643                 path.insert(self.root, atIndex: 0)
BTreeCursor.swift:734         while node !== root && node.isTooSmall {
BTreeCursor.swift:740         while targetPosition != count && targetPosition == self.position && node !== root {
BTreeCursor.swift:745         if node === root && node.elements.count == 0 && node.children.count == 1 {
BTreeCursor.swift:747             root = node.makeChildUnique(0)
BTreeCursor.swift:748             path[0] = root
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): Node
0111    
0112        /// The current path in the tree that is being edited.
0113        ///
0114        /// Only the last node on the path has correct `count`; the element count of the currently focused descendant
0115        /// subtree is subtracted from each ancestor's count.
0116        /// I.e., `path[i].count = realCount(path[i]) - realCount(path[i+1])`.
0117        ///
0118        private var pathBTreeCursor.swift:143     public var isValid: Bool { return !path.isEmpty }
BTreeCursor.swift:153         self.path = [root]
BTreeCursor.swift:163         self.path = [root]
BTreeCursor.swift:195         while !path.isEmpty {
BTreeCursor.swift:196             let node = path.removeLast()
BTreeCursor.swift:213         var left = path.removeLast()
BTreeCursor.swift:222         while !path.isEmpty {
BTreeCursor.swift:223             let node = path.removeLast()
BTreeCursor.swift:248         var left = path.removeLast()
BTreeCursor.swift:253         while !path.isEmpty {
BTreeCursor.swift:254             let node = path.removeLast()
BTreeCursor.swift:272         var right = path.removeLast().split(slots.removeLast()).node
BTreeCursor.swift:276         while !path.isEmpty {
BTreeCursor.swift:277             let node = path.removeLast()
BTreeCursor.swift:296         self.path = []
BTreeCursor.swift:301         assert(path.count == slots.count)
BTreeCursor.swift:303         let node = path.last!
BTreeCursor.swift:308         assert(path.count > 1 && path.count == slots.count + 1)
BTreeCursor.swift:308         assert(path.count > 1 && path.count == slots.count + 1)
BTreeCursor.swift:309         let child = path.removeLast()
BTreeCursor.swift:310         let parent = path.last!
BTreeCursor.swift:316         assert(path.count == slots.count)
BTreeCursor.swift:317         let parent = path.last!
BTreeCursor.swift:321         path.append(child)
BTreeCursor.swift:325         assert(path.count == slots.count + 1)
BTreeCursor.swift:326         let node = path.last!
BTreeCursor.swift:339         let node = path.last!
BTreeCursor.swift:349                 } while slots.last! == path.last!.elements.count
BTreeCursor.swift:371         let node = path.last!
BTreeCursor.swift:385             precondition(path.count > 0)
BTreeCursor.swift:386             assert(!path.last!.isLeaf)
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:442         while path.count > 1 && !path.last!.contains(key, choosing: selector) {
BTreeCursor.swift:442         while path.count > 1 && !path.last!.contains(key, choosing: selector) {
BTreeCursor.swift:450         assert(self.path.count == self.slots.count + 1)
BTreeCursor.swift:461         assert(position >= self.position - path.last!.count && position <= self.position)
BTreeCursor.swift:462         assert(self.path.count == self.slots.count + 1)
BTreeCursor.swift:463         var node = path.last!
BTreeCursor.swift:472         assert(path.count == slots.count)
BTreeCursor.swift:476         assert(self.path.count == self.slots.count + 1)
BTreeCursor.swift:482         var node = path.last!
BTreeCursor.swift:491                 match = (depth: path.count, slot: m)
BTreeCursor.swift:495                     for _ in 0 ..< path.count - m.depth {
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:553         let node = path.last!
BTreeCursor.swift:566         if path.last!.isLeaf {
BTreeCursor.swift:567             let node = path.last!
BTreeCursor.swift:575             let node = path.last!
BTreeCursor.swift:588         if path.last!.isLeaf {
BTreeCursor.swift:589             let node = path.last!
BTreeCursor.swift:595             let node = path.last!
BTreeCursor.swift:606         guard path.last!.isTooLarge else { return }
BTreeCursor.swift:609         var i = path.count - 1
BTreeCursor.swift:610         while path[i].isTooLarge {
BTreeCursor.swift:612             let left = path[i]
BTreeCursor.swift:619                 path[i] = right
BTreeCursor.swift:623                 assert(i == path.count - 1)
BTreeCursor.swift:624                 path.removeLast()
BTreeCursor.swift:630                 let parent = path[i - 1]
BTreeCursor.swift:643                 path.insert(self.root, atIndex: 0)
BTreeCursor.swift:650         while i < path.count - 1 {
BTreeCursor.swift:651             path[i].count -= path[i + 1].count
BTreeCursor.swift:651             path[i].count -= path[i + 1].count
BTreeCursor.swift:715         var node = path.last!
BTreeCursor.swift:736             node = path.last!
BTreeCursor.swift:742             node = path.last!
BTreeCursor.swift:746             assert(path.count == 1 && slots.count == 0)
BTreeCursor.swift:748             path[0] = root: [Node]
0119    
0120        /// The slots on the path to the currently focused part of the tree.
0121        private var slotsBTreeCursor.swift:154         self.slots = []
BTreeCursor.swift:164         self.slots = []
BTreeCursor.swift:214         var (separator, right) = left.split(slots.removeLast()).exploded
BTreeCursor.swift:224             let slot = slots.removeLast()
BTreeCursor.swift:249         _ = left.split(slots.removeLast())
BTreeCursor.swift:255             let slot = slots.removeLast()
BTreeCursor.swift:272         var right = path.removeLast().split(slots.removeLast()).node
BTreeCursor.swift:278             let slot = slots.removeLast()
BTreeCursor.swift:297         self.slots = []
BTreeCursor.swift:301         assert(path.count == slots.count)
BTreeCursor.swift:302         let slot = slots.removeLast()
BTreeCursor.swift:308         assert(path.count > 1 && path.count == slots.count + 1)
BTreeCursor.swift:316         assert(path.count == slots.count)
BTreeCursor.swift:318         let slot = slots.last!
BTreeCursor.swift:325         assert(path.count == slots.count + 1)
BTreeCursor.swift:329         self.slots.append(slot)
BTreeCursor.swift:341             if slots.last! < node.elements.count - 1 || _position == count {
BTreeCursor.swift:342                 slots[slots.count - 1] += 1
BTreeCursor.swift:342                 slots[slots.count - 1] += 1
BTreeCursor.swift:347                     slots.removeLast()
BTreeCursor.swift:349                 } while slots.last! == path.last!.elements.count
BTreeCursor.swift:354             slots[slots.count - 1] += 1
BTreeCursor.swift:354             slots[slots.count - 1] += 1
BTreeCursor.swift:357                 slots.append(0)
BTreeCursor.swift:360             slots.append(0)
BTreeCursor.swift:373             if slots.last! > 0 {
BTreeCursor.swift:374                 slots[slots.count - 1] -= 1
BTreeCursor.swift:374                 slots[slots.count - 1] -= 1
BTreeCursor.swift:378                     slots.removeLast()
BTreeCursor.swift:380                 } while slots.last! == 0
BTreeCursor.swift:381                 slots[slots.count - 1] -= 1
BTreeCursor.swift:381                 slots[slots.count - 1] -= 1
BTreeCursor.swift:390                 slots.append(slot)
BTreeCursor.swift:393             slots.append(node.elements.count - 1)
BTreeCursor.swift:450         assert(self.path.count == self.slots.count + 1)
BTreeCursor.swift:462         assert(self.path.count == self.slots.count + 1)
BTreeCursor.swift:472         assert(path.count == slots.count)
BTreeCursor.swift:476         assert(self.path.count == self.slots.count + 1)
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:554         let slot = slots.last!
BTreeCursor.swift:568             let slot = slots.last!
BTreeCursor.swift:570             slots[slots.count - 1] = slot + 1
BTreeCursor.swift:570             slots[slots.count - 1] = slot + 1
BTreeCursor.swift:576             assert(node.isLeaf && slots.last == 0)
BTreeCursor.swift:590             let slot = slots.last!
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:598             slots[slots.count - 1] = node.elements.count - 1
BTreeCursor.swift:613             let slot = slots[i]
BTreeCursor.swift:618                 slots[i] = slot - left.elements.count - 1
BTreeCursor.swift:625                 slots.removeLast()
BTreeCursor.swift:631                 let pslot = slots[i - 1]
BTreeCursor.swift:636                     slots[i - 1] = pslot + 1
BTreeCursor.swift:644                 slots.insert(slot > left.elements.count ? 1 : 0, atIndex: 0)
BTreeCursor.swift:716         let slot = slots.last!
BTreeCursor.swift:746             assert(path.count == 1 && slots.count == 0): [Int]
0122    
0123        /// The current count of elements in the tree. This is always kept up to date, while `root.count` is usually invalid.
0124        public private(set) var countBTreeCursor.swift:145     public var isAtEnd: Bool { return _position == count }
BTreeCursor.swift:151         self.count = root.count
BTreeCursor.swift:161         self.count = root.count
BTreeCursor.swift:200         assert(root.count == count)
BTreeCursor.swift:294         self.count = 0
BTreeCursor.swift:337         precondition(self.position < count)
BTreeCursor.swift:341             if slots.last! < node.elements.count - 1 || _position == count {
BTreeCursor.swift:409         while self.count > self.position + path.last!.count {
BTreeCursor.swift:413         self.descendToPosition(self.count)
BTreeCursor.swift:421         precondition(isValid && position >= 0 && position <= count)
BTreeCursor.swift:422         if position == count {
BTreeCursor.swift:477         if count == 0 {
BTreeCursor.swift:565         count += 1
BTreeCursor.swift:587         count += 1
BTreeCursor.swift:672         if self.count == 0 {
BTreeCursor.swift:678         if position == self.count {
BTreeCursor.swift:731         self.count -= 1
BTreeCursor.swift:740         while targetPosition != count && targetPosition == self.position && node !== root {
BTreeCursor.swift:759         precondition(isValid && n >= 0 && self.position + n <= count)
BTreeCursor.swift:762         if n == count { reset(Node(order: root.order)); return }
BTreeCursor.swift:769         else if position == count - n {
BTreeCursor.swift:786         precondition(isValid && n >= 0 && self.position + n <= count)
BTreeCursor.swift:796         if n == count {
BTreeCursor.swift:803         if position == count - n {: Int
0125    
0126        /// The position of the currently focused element in the tree.
0127        private var _positionBTreeCursor.swift:134             return _position
BTreeCursor.swift:144     public var isAtStart: Bool { return _position == 0 }
BTreeCursor.swift:145     public var isAtEnd: Bool { return _position == count }
BTreeCursor.swift:152         self._position = root.count
BTreeCursor.swift:162         self._position = root.count
BTreeCursor.swift:295         self._position = 0
BTreeCursor.swift:304         self._position += node.count - node.positionOfSlot(slot)
BTreeCursor.swift:328         self._position -= node.count - p
BTreeCursor.swift:338         _position += 1
BTreeCursor.swift:341             if slots.last! < node.elements.count - 1 || _position == count {
BTreeCursor.swift:370         _position -= 1
BTreeCursor.swift:571             _position += 1
BTreeCursor.swift:599             _position += 1: Int
0128    
0129        /// The position of the currently focused element in the tree.
0130        ///
0131        /// - Complexity: O(1) for the getter, O(log(`count`)) for the setter.
0132        public var positionBTreeCursor.swift:337         precondition(self.position < count)
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: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: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:471         assert(self.position == position)
BTreeCursor.swift:677         let position = self.position
BTreeCursor.swift:728         let targetPosition = self.position
BTreeCursor.swift:740         while targetPosition != count && targetPosition == self.position && node !== root {
BTreeCursor.swift:759         precondition(isValid && n >= 0 && self.position + n <= count)
BTreeCursor.swift:764         let position = self.position
BTreeCursor.swift:786         precondition(isValid && n >= 0 && self.position + n <= count)
BTreeCursor.swift:802         let position = self.position
List.swift:357             while cursor.position < range.endIndex {
List.swift:362             if cursor.position < range.endIndex {
List.swift:363                 cursor.remove(range.endIndex - cursor.position): Int {
0133            get {
0134                return _position
0135            }
0136            set {
0137                moveToPosition(newValue)
0138            }
0139        }
0140    
0141        //MARK: Simple properties
0142    
0143        public var isValidBTreeCursor.swift:421         precondition(isValid && position >= 0 && position <= count)
BTreeCursor.swift:586         precondition(self.isValid)
BTreeCursor.swift:665         precondition(isValid)
BTreeCursor.swift:759         precondition(isValid && n >= 0 && self.position + n <= count)
BTreeCursor.swift:786         precondition(isValid && n >= 0 && self.position + n <= count): Bool { return !path.isEmpty }
0144        public var isAtStartBTreeCursor.swift:369         precondition(!isAtStart): Bool { return _position == 0 }
0145        public var isAtEndBTreeCursor.swift:211         precondition(!isAtEnd)
BTreeCursor.swift:247         precondition(!isAtEnd)
BTreeCursor.swift:271         precondition(!isAtEnd)
BTreeCursor.swift:524             precondition(!self.isAtEnd)
BTreeCursor.swift:528             precondition(!self.isAtEnd)
BTreeCursor.swift:538             precondition(!self.isAtEnd)
BTreeCursor.swift:542             precondition(!self.isAtEnd)
BTreeCursor.swift:552         precondition(!self.isAtEnd)
BTreeCursor.swift:564         precondition(!self.isAtEnd)
BTreeCursor.swift:714         precondition(!isAtEnd): Bool { return _position == count }
0146    
0147        //MARK: Initializers
0148    
0149        private initBTreeCursor.swift:23         let cursor = BTreeCursor(root)
BTreeCursor.swift:59         let cursor = BTreeCursor(root)
BTreeCursor.swift:74         let cursor = BTreeCursor(root)(_ root: Node) {
0150            self.root = root
0151            self.count = root.count
0152            self._position = root.count
0153            self.path = [root]
0154            self.slots = []
0155        }
0156    
0157        //MARK: Reset
0158    
0159        private func resetBTreeCursor.swift:177         reset(root)
BTreeCursor.swift:182         reset(root)
BTreeCursor.swift:762         if n == count { reset(Node(order: root.order)); return }
BTreeCursor.swift:798             reset(Node(order: tree.root.order))(root: Node) {
0160            self.root = root
0161            self.count = root.count
0162            self._position = root.count
0163            self.path = [root]
0164            self.slots = []
0165        }
0166    
0167        internal func resetBTreeCursor.swift:767             reset(startOf: finishAndKeepSuffix().root)(startOf root: Node) {
0168            reset(root: root, position: 0)
0169        }
0170    
0171        internal func resetBTreeCursor.swift:673             reset(endOf: root)
BTreeCursor.swift:683             reset(endOf: Node.join(left: left.root, separator: separator, right: root))
BTreeCursor.swift:770             reset(endOf: finishAndKeepPrefix().root)(endOf root: Node) {
0172            reset(root: root, position: root.count)
0173        }
0174    
0175        internal func resetBTreeCursor.swift:168         reset(root: root, position: 0)
BTreeCursor.swift:172         reset(root: root, position: root.count)
BTreeCursor.swift:689             reset(root: Node.join(left: root, separator: separator, right: right.root), position: position + c)
BTreeCursor.swift:698             reset(root: t2, position: position + c)
BTreeCursor.swift:774             reset(root: mid.root, position: n - 1)
BTreeCursor.swift:776             reset(root: Node.join(left: left.root, separator: separator, right: right.root), position: position)
BTreeCursor.swift:805             reset(root: cut.left.root, position: position)
BTreeCursor.swift:811             reset(root: cut1.right.root, position: n - 1)
BTreeCursor.swift:813             reset(root: Node.join(left: cut1.left.root, separator: cut2.separator, right: cut2.right.root), position: position)(root root: Node, position: Int) {
0176            precondition(position >= 0 && position <= root.count)
0177            reset(root)
0178            descendToPosition(position)
0179        }
0180    
0181        internal func reset(root root: Node, key: Key, choosing selector: BTreeKeySelector = .Any) {
0182            reset(root)
0183            descendToKey(key, choosing: selector)
0184        }
0185    
0186        //MARK: Finishing
0187    
0188        /// Finalize editing the tree and return it, deactivating this cursor.
0189        /// You'll need to create a new cursor to continue editing the tree.
0190        ///
0191        /// - Complexity: O(log(`count`))
0192        @warn_unused_result
0193        internal func finishBTreeCursor.swift:26         defer { self = cursor.finish() }
BTreeCursor.swift:62         defer { self = cursor.finish() }
BTreeCursor.swift:77         defer { self = cursor.finish() }
BTreeCursor.swift:682             let left = finish()
BTreeCursor.swift:688             let right = finish()
BTreeCursor.swift:797             let tree = finish()() -> Tree {
0194            var childCount = 0
0195            while !path.isEmpty {
0196                let node = path.removeLast()
0197                node.count += childCount
0198                childCount = node.count
0199            }
0200            assert(root.count == count)
0201            defer { invalidate() }
0202            return Tree(root)
0203        }
0204    
0205        /// Cut the tree into two separate b-trees and a separator at the current position.
0206        /// This operation deactivates the current cursor.
0207        ///
0208        /// - Complexity: O(log(`count`))
0209        @warn_unused_result
0210        internal func finishByCuttingBTreeCursor.swift:695             let (prefix, sep2, suffix) = finishByCutting()
BTreeCursor.swift:773             let (left, _, mid) = finishByCutting()
BTreeCursor.swift:775             let (_, separator, right) = finishByCutting()
BTreeCursor.swift:804             var cut = finishByCutting()
BTreeCursor.swift:810             let cut1 = finishByCutting()
BTreeCursor.swift:812             var cut2 = finishByCutting()() -> (left: Tree, separator: Element, right: Tree) {
0211            precondition(!isAtEnd)
0212    
0213            var left = path.removeLast()
0214            var (separator, right) = left.split(slots.removeLast()).exploded
0215            if left.children.count == 1 {
0216                left = left.makeChildUnique(0)
0217            }
0218            if right.children.count == 1 {
0219                right = right.makeChildUnique(0)
0220            }
0221    
0222            while !path.isEmpty {
0223                let node = path.removeLast()
0224                let slot = slots.removeLast()
0225                if slot >= 1 {
0226                    let l = slot == 1 ? node.makeChildUnique(0) : Node(node: node, slotRange: 0 ..< slot - 1)
0227                    let s = node.elements[slot - 1]
0228                    left = Node.join(left: l, separator: s, right: left)
0229                }
0230                let c = node.elements.count
0231                if slot <= c - 1 {
0232                    let r = slot == c - 1 ? node.makeChildUnique(c) : Node(node: node, slotRange: slot + 1 ..< c)
0233                    let s = node.elements[slot]
0234                    right = Node.join(left: right, separator: s, right: r)
0235                }
0236            }
0237    
0238            return (Tree(left), separator, Tree(right))
0239        }
0240    
0241        /// Discard elements at or after the current position and return the resulting b-tree.
0242        /// This operation deactivates the current cursor.
0243        ///
0244        /// - Complexity: O(log(`count`))
0245        @warn_unused_result
0246        internal func finishAndKeepPrefixBTreeCursor.swift:770             reset(endOf: finishAndKeepPrefix().root)() -> Tree {
0247            precondition(!isAtEnd)
0248            var left = path.removeLast()
0249            _ = left.split(slots.removeLast())
0250            if left.children.count == 1 {
0251                left = left.makeChildUnique(0)
0252            }
0253            while !path.isEmpty {
0254                let node = path.removeLast()
0255                let slot = slots.removeLast()
0256                if slot >= 1 {
0257                    let l = slot == 1 ? node.makeChildUnique(0) : Node(node: node, slotRange: 0 ..< slot - 1)
0258                    let s = node.elements[slot - 1]
0259                    left = Node.join(left: l, separator: s, right: left)
0260                }
0261            }
0262            return Tree(left)
0263        }
0264    
0265        /// Discard elements at or before the current position and return the resulting b-tree.
0266        /// This operation destroys the current cursor.
0267        ///
0268        /// - Complexity: O(log(`count`))
0269        @warn_unused_result
0270        internal func finishAndKeepSuffixBTreeCursor.swift:767             reset(startOf: finishAndKeepSuffix().root)() -> Tree {
0271            precondition(!isAtEnd)
0272            var right = path.removeLast().split(slots.removeLast()).node
0273            if right.children.count == 1 {
0274                right = right.makeChildUnique(0)
0275            }
0276            while !path.isEmpty {
0277                let node = path.removeLast()
0278                let slot = slots.removeLast()
0279                let c = node.elements.count
0280                if slot <= c - 1 {
0281                    let r = slot == c - 1 ? node.makeChildUnique(c) : Node(node: node, slotRange: slot + 1 ..< c)
0282                    let s = node.elements[slot]
0283                    right = Node.join(left: right, separator: s, right: r)
0284                }
0285            }
0286            return Tree(right)
0287        }
0288    
0289        //MARK: Navigation
0290    
0291        /// Invalidate this cursor.
0292        private func invalidateBTreeCursor.swift:201         defer { invalidate() }() {
0293            self.root = Node()
0294            self.count = 0
0295            self._position = 0
0296            self.path = []
0297            self.slots = []
0298        }
0299    
0300        private func popFromSlotsBTreeCursor.swift:408         popFromSlots()
BTreeCursor.swift:411             popFromSlots()
BTreeCursor.swift:427         popFromSlots()
BTreeCursor.swift:430             popFromSlots()
BTreeCursor.swift:441         popFromSlots()
BTreeCursor.swift:444             popFromSlots()
BTreeCursor.swift:497                         popFromSlots()
BTreeCursor.swift:732         popFromSlots()
BTreeCursor.swift:737             let slot = popFromSlots()
BTreeCursor.swift:743             popFromSlots()() -> Int {
0301            assert(path.count == slots.count)
0302            let slot = slots.removeLast()
0303            let node = path.last!
0304            self._position += node.count - node.positionOfSlot(slot)
0305            return slot
0306        }
0307        private func popFromPathBTreeCursor.swift:348                     popFromPath()
BTreeCursor.swift:379                     popFromPath()
BTreeCursor.swift:410             popFromPath()
BTreeCursor.swift:429             popFromPath()
BTreeCursor.swift:443             popFromPath()
BTreeCursor.swift:496                         popFromPath()
BTreeCursor.swift:735             popFromPath()
BTreeCursor.swift:741             popFromPath()() -> Node {
0308            assert(path.count > 1 && path.count == slots.count + 1)
0309            let child = path.removeLast()
0310            let parent = path.last!
0311            parent.count += child.count
0312            return child
0313        }
0314    
0315        private func pushToPathBTreeCursor.swift:355             var node = pushToPath()
BTreeCursor.swift:358                 node = pushToPath()
BTreeCursor.swift:387             var node = pushToPath()
BTreeCursor.swift:391                 node = pushToPath()
BTreeCursor.swift:455                 pushToPath()
BTreeCursor.swift:467             node = pushToPath()
BTreeCursor.swift:511             node = pushToPath()() -> Node {
0316            assert(path.count == slots.count)
0317            let parent = path.last!
0318            let slot = slots.last!
0319            let child = parent.makeChildUnique(slot)
0320            parent.count -= child.count
0321            path.append(child)
0322            return child
0323        }
0324        private func pushToSlotsBTreeCursor.swift:453             pushToSlots(slot)
BTreeCursor.swift:465         pushToSlots(slot.index, positionOfSlot: slot.position)
BTreeCursor.swift:469             pushToSlots(slot.index, positionOfSlot: slot.position)
BTreeCursor.swift:478             pushToSlots(0)
BTreeCursor.swift:488                     pushToSlots(m)
BTreeCursor.swift:499                     pushToSlots(m.slot)
BTreeCursor.swift:502                     pushToSlots(slot.descend)
BTreeCursor.swift:505                     pushToSlots(slot.descend - 1)
BTreeCursor.swift:510             pushToSlots(slot.descend)(slot: Int, positionOfSlot: Int? = nil) {
0325            assert(path.count == slots.count + 1)
0326            let node = path.last!
0327            let p = positionOfSlot ?? node.positionOfSlot(slot)
0328            self._position -= node.count - p
0329            self.slots.append(slot)
0330        }
0331    
0332        /// Position the cursor on the next element in the b-tree.
0333        ///
0334        /// - Requires: `!isAtEnd`
0335        /// - Complexity: Amortized O(1)
0336        public func moveForwardBTreeCursor.swift:506                     moveForward()
BTreeCursor.swift:574             moveForward()
BTreeCursor.swift:602         moveForward()
BTreeCursor.swift:725             moveForward()
List.swift:360                 cursor.moveForward()() {
0337            precondition(self.position < count)
0338            _position += 1
0339            let node = path.last!
0340            if node.isLeaf {
0341                if slots.last! < node.elements.count - 1 || _position == count {
0342                    slots[slots.count - 1] += 1
0343                }
0344                else {
0345                    // Ascend
0346                    repeat {
0347                        slots.removeLast()
0348                        popFromPath()
0349                    } while slots.last! == path.last!.elements.count
0350                }
0351            }
0352            else {
0353                // Descend
0354                slots[slots.count - 1] += 1
0355                var node = pushToPath()
0356                while !node.isLeaf {
0357                    slots.append(0)
0358                    node = pushToPath()
0359                }
0360                slots.append(0)
0361            }
0362        }
0363    
0364        /// Position this cursor to the previous element in the b-tree.
0365        ///
0366        /// - Requires: `!isAtStart`
0367        /// - Complexity: Amortized O(1)
0368        public func moveBackwardBTreeCursor.swift:594             moveBackward()
BTreeCursor.swift:680             moveBackward()
BTreeCursor.swift:693             moveBackward()
BTreeCursor.swift:721             moveBackward()() {
0369            precondition(!isAtStart)
0370            _position -= 1
0371            let node = path.last!
0372            if node.isLeaf {
0373                if slots.last! > 0 {
0374                    slots[slots.count - 1] -= 1
0375                }
0376                else {
0377                    repeat {
0378                        slots.removeLast()
0379                        popFromPath()
0380                    } while slots.last! == 0
0381                    slots[slots.count - 1] -= 1
0382                }
0383            }
0384            else {
0385                precondition(path.count > 0)
0386                assert(!path.last!.isLeaf)
0387                var node = pushToPath()
0388                while !node.isLeaf {
0389                    let slot = node.children.count - 1
0390                    slots.append(slot)
0391                    node = pushToPath()
0392                }
0393                slots.append(node.elements.count - 1)
0394            }
0395        }
0396    
0397        /// Position this cursor to the start of the b-tree.
0398        ///
0399        /// - Complexity: O(log(`position`))
0400        public func moveToStart() {
0401            moveToPosition(0)
0402        }
0403    
0404        /// Position this cursor to the end of the b-tree.
0405        ///
0406        /// - Complexity: O(log(`count` - `position`))
0407        public func moveToEndBTreeCursor.swift:423             moveToEnd()() {
0408            popFromSlots()
0409            while self.count > self.position + path.last!.count {
0410                popFromPath()
0411                popFromSlots()
0412            }
0413            self.descendToPosition(self.count)
0414        }
0415    
0416        /// Move this cursor to the specified position in the b-tree.
0417        ///
0418        /// - Complexity: O(log(*distance*)), where *distance* is the absolute difference between the desired and current
0419        ///   positions.
0420        public func moveToPositionBTreeCursor.swift:137             moveToPosition(newValue)
BTreeCursor.swift:401         moveToPosition(0)
BTreeCursor.swift:766             moveToPosition(n - 1)(position: Int) {
0421            precondition(isValid && position >= 0 && position <= count)
0422            if position == count {
0423                moveToEnd()
0424                return
0425            }
0426            // Pop to ancestor whose subtree contains the desired position.
0427            popFromSlots()
0428            while position < self.position - path.last!.count || position >= self.position {
0429                popFromPath()
0430                popFromSlots()
0431            }
0432            self.descendToPosition(position)
0433        }
0434    
0435        /// Move this cursor to an element with the specified key. 
0436        /// If there are no such elements, the cursor is moved to a spot where .
0437        /// If there are multiple such elements, `selector` specified which one to find.
0438        ///
0439        /// - Complexity: O(log(`count`))
0440        public func moveToKey(key: Key, choosing selector: BTreeKeySelector = .Any) {
0441            popFromSlots()
0442            while path.count > 1 && !path.last!.contains(key, choosing: selector) {
0443                popFromPath()
0444                popFromSlots()
0445            }
0446            self.descendToKey(key, choosing: selector)
0447        }
0448    
0449        private func descendToSlotsBTreeCursor.swift:75         cursor.descendToSlots(index.slots)(slots: [Int]) {
0450            assert(self.path.count == self.slots.count + 1)
0451            for i in 0 ..< slots.count {
0452                let slot = slots[i]
0453                pushToSlots(slot)
0454                if i != slots.count - 1 {
0455                    pushToPath()
0456                }
0457            }
0458        }
0459    
0460        private func descendToPositionBTreeCursor.swift:24         cursor.descendToPosition(position)
BTreeCursor.swift:178         descendToPosition(position)
BTreeCursor.swift:413         self.descendToPosition(self.count)
BTreeCursor.swift:432         self.descendToPosition(position)
BTreeCursor.swift:750         descendToPosition(targetPosition)(position: Int) {
0461            assert(position >= self.position - path.last!.count && position <= self.position)
0462            assert(self.path.count == self.slots.count + 1)
0463            var node = path.last!
0464            var slot = node.slotOfPosition(position - (self.position - node.count))
0465            pushToSlots(slot.index, positionOfSlot: slot.position)
0466            while !slot.match {
0467                node = pushToPath()
0468                slot = node.slotOfPosition(position - (self.position - node.count))
0469                pushToSlots(slot.index, positionOfSlot: slot.position)
0470            }
0471            assert(self.position == position)
0472            assert(path.count == slots.count)
0473        }
0474    
0475        private func descendToKeyBTreeCursor.swift:60         cursor.descendToKey(key, choosing: selector)
BTreeCursor.swift:183         descendToKey(key, choosing: selector)
BTreeCursor.swift:446         self.descendToKey(key, choosing: selector)(key: Key, choosing selector: BTreeKeySelector) {
0476            assert(self.path.count == self.slots.count + 1)
0477            if count == 0 {
0478                pushToSlots(0)
0479                return
0480            }
0481    
0482            var node = path.last!
0483            var match: (depth: Int, slot: Int)? = nil
0484            while true {
0485                let slot = node.slotOf(key, choosing: selector)
0486                if let m = slot.match {
0487                    if node.isLeaf || selector == .Any {
0488                        pushToSlots(m)
0489                        return
0490                    }
0491                    match = (depth: path.count, slot: m)
0492                }
0493                if node.isLeaf {
0494                    if let m = match {
0495                        for _ in 0 ..< path.count - m.depth {
0496                            popFromPath()
0497                            popFromSlots()
0498                        }
0499                        pushToSlots(m.slot)
0500                    }
0501                    else if slot.descend < node.elements.count {
0502                        pushToSlots(slot.descend)
0503                    }
0504                    else {
0505                        pushToSlots(slot.descend - 1)
0506                        moveForward()
0507                    }
0508                    break
0509                }
0510                pushToSlots(slot.descend)
0511                node = pushToPath()
0512            }
0513        }
0514    
0515        //MARK: Editing
0516    
0517        /// Get or set the key of the currently focused element.
0518        ///
0519        /// - Warning: Changing the key is potentially dangerous; it is the caller's responsibility to ensure that
0520        /// keys remain in ascending order. This is not verified at runtime.
0521        /// - Complexity: O(1)
0522        public var keyBTreeCursor.swift:723             self.key = surrogate.0: Key {
0523            get {
0524                precondition(!self.isAtEnd)
0525                return path.last!.elements[slots.last!].0
0526            }
0527            set {
0528                precondition(!self.isAtEnd)
0529                path.last!.elements[slots.last!].0 = newValue
0530            }
0531        }
0532    
0533        /// Get or set the payload of the currently focused element.
0534        ///
0535        /// - Complexity: O(1)
0536        public var payloadBTreeCursor.swift:724             self.payload = surrogate.1
List.swift:359                 cursor.payload = element: Payload {
0537            get {
0538                precondition(!self.isAtEnd)
0539                return path.last!.elements[slots.last!].1
0540            }
0541            set {
0542                precondition(!self.isAtEnd)
0543                path.last!.elements[slots.last!].1 = newValue
0544            }
0545        }
0546    
0547        /// Update the payload stored at the cursor's current position and return the previous value.
0548        /// This method does not change the cursor's position.
0549        ///
0550        /// - Complexity: O(1)
0551        public func setPayload(payload: Payload) -> Payload {
0552            precondition(!self.isAtEnd)
0553            let node = path.last!
0554            let slot = slots.last!
0555            let old = node.elements[slot].1
0556            node.elements[slot].1 = payload
0557            return old
0558        }
0559    
0560        /// Insert a new element after the cursor's current position, and position the cursor on the new element.
0561        ///
0562        /// - Complexity: amortized O(1)
0563        public func insertAfter(element: Element) {
0564            precondition(!self.isAtEnd)
0565            count += 1
0566            if path.last!.isLeaf {
0567                let node = path.last!
0568                let slot = slots.last!
0569                node.insert(element, inSlot: slot + 1)
0570                slots[slots.count - 1] = slot + 1
0571                _position += 1
0572            }
0573            else {
0574                moveForward()
0575                let node = path.last!
0576                assert(node.isLeaf && slots.last == 0)
0577                node.insert(element, inSlot: 0)
0578            }
0579            fixupAfterInsert()
0580        }
0581    
0582        /// Insert a new element at the cursor's current position, and leave the cursor positioned on the original element.
0583        ///
0584        /// - Complexity: amortized O(1)
0585        public func insertBTreeCursor.swift:669             insert(root.elements[0])(element: Element) {
0586            precondition(self.isValid)
0587            count += 1
0588            if path.last!.isLeaf {
0589                let node = path.last!
0590                let slot = slots.last!
0591                node.insert(element, inSlot: slot)
0592            }
0593            else {
0594                moveBackward()
0595                let node = path.last!
0596                assert(node.isLeaf && slots.last == node.elements.count - 1)
0597                node.append(element)
0598                slots[slots.count - 1] = node.elements.count - 1
0599                _position += 1
0600            }
0601            fixupAfterInsert()
0602            moveForward()
0603        }
0604    
0605        private func fixupAfterInsertBTreeCursor.swift:579         fixupAfterInsert()
BTreeCursor.swift:601         fixupAfterInsert()() {
0606            guard path.last!.isTooLarge else { return }
0607    
0608            // Split nodes on the way to the root until we restore the b-tree's size constraints.
0609            var i = path.count - 1
0610            while path[i].isTooLarge {
0611                // Split path[i], which must have correct count.
0612                let left = path[i]
0613                let slot = slots[i]
0614                let splinter = left.split()
0615                let right = splinter.node
0616                if slot > left.elements.count {
0617                    // Focused element is in the new branch; adjust state accordingly.
0618                    slots[i] = slot - left.elements.count - 1
0619                    path[i] = right
0620                }
0621                else if slot == left.elements.count {
0622                    // Focused element is the new separator; adjust state accordingly.
0623                    assert(i == path.count - 1)
0624                    path.removeLast()
0625                    slots.removeLast()
0626                }
0627    
0628                if i > 0 {
0629                    // Insert splinter into parent node and fix its count field.
0630                    let parent = path[i - 1]
0631                    let pslot = slots[i - 1]
0632                    parent.insert(splinter, inSlot: pslot)
0633                    parent.count += left.count + right.count + 1
0634                    if slot > left.elements.count {
0635                        // Focused element is in the new branch; update state accordingly.
0636                        slots[i - 1] = pslot + 1
0637                    }
0638                    i -= 1
0639                }
0640                else {
0641                    // Create new root node.
0642                    self.root = Node(left: left, separator: splinter.separator, right: right)
0643                    path.insert(self.root, atIndex: 0)
0644                    slots.insert(slot > left.elements.count ? 1 : 0, atIndex: 0)
0645                }
0646            }
0647    
0648            // Size constraints are now OK, but counts on path have become valid, so we need to restore 
0649            // cursor state by subtracting focused children.
0650            while i < path.count - 1 {
0651                path[i].count -= path[i + 1].count
0652                i += 1
0653            }
0654        }
0655    
0656        /// Insert the contents of `tree` before the currently focused element, keeping the cursor's position on it.
0657        ///
0658        /// - Complexity: O(log(`count + tree.count`))
0659        public func insertList.swift:275             cursor.insert(list.tree)
List.swift:293             cursor.insert(list.tree)(tree: Tree) {
0660            let root = tree.root.clone()
0661            insertWithoutCloning(root)
0662        }
0663    
0664        private func insertWithoutCloningBTreeCursor.swift:661         insertWithoutCloning(root)
BTreeCursor.swift:707         insertWithoutCloning(BTree(sortedElements: elements).root)(root: Node) {
0665            precondition(isValid)
0666            let c = root.count
0667            if c == 0 { return }
0668            if c == 1 {
0669                insert(root.elements[0])
0670                return
0671            }
0672            if self.count == 0 {
0673                reset(endOf: root)
0674                return
0675            }
0676    
0677            let position = self.position
0678            if position == self.count {
0679                // Append
0680                moveBackward()
0681                let separator = remove()
0682                let left = finish()
0683                reset(endOf: Node.join(left: left.root, separator: separator, right: root))
0684            }
0685            else if position == 0 {
0686                // Prepend
0687                let separator = remove()
0688                let right = finish()
0689                reset(root: Node.join(left: root, separator: separator, right: right.root), position: position + c)
0690            }
0691            else {
0692                // Insert in middle
0693                moveBackward()
0694                let sep1 = remove()
0695                let (prefix, sep2, suffix) = finishByCutting()
0696                let t1 = Node.join(left: prefix.root, separator: sep1, right: root)
0697                let t2 = Node.join(left: t1, separator: sep2, right: suffix.root)
0698                reset(root: t2, position: position + c)
0699            }
0700        }
0701    
0702        /// Insert all elements in a sequence before the currently focused element, keeping the cursor's position on it.
0703        ///
0704        /// - Requires: `self.isValid` and `elements` is sorted by key.
0705        /// - Complexity: O(log(`count`) + *c*), where *c* is the number of elements in the sequence.
0706        public func insertList.swift:284             cursor.insert(elements.lazy.map { (EmptyKey(), $0) })
List.swift:299             cursor.insert(elements.lazy.map { (EmptyKey(), $0) })
List.swift:366                 cursor.insert(GeneratorSequence(generator!).lazy.map { (EmptyKey(), $0) })<S: SequenceType where S.Generator.Element == Element>(elements: S) {
0707            insertWithoutCloning(BTree(sortedElements: elements).root)
0708        }
0709    
0710        /// Remove and return the element at the cursor's current position, and position the cursor on its successor.
0711        ///
0712        /// - Complexity: O(log(`count`))
0713        public func removeBTreeCursor.swift:681             let separator = remove()
BTreeCursor.swift:687             let separator = remove()
BTreeCursor.swift:694             let sep1 = remove()
BTreeCursor.swift:722             let surrogate = remove()
BTreeCursor.swift:761         if n == 1 { remove(); return }
BTreeCursor.swift:791             let element = remove()() -> Element {
0714            precondition(!isAtEnd)
0715            var node = path.last!
0716            let slot = slots.last!
0717            let result = node.elements[slot]
0718            if !node.isLeaf {
0719                // For internal nodes, remove the (leaf) predecessor instead, then put it back in place of the element
0720                // that we actually want to remove.
0721                moveBackward()
0722                let surrogate = remove()
0723                self.key = surrogate.0
0724                self.payload = surrogate.1
0725                moveForward()
0726                return result
0727            }
0728            let targetPosition = self.position
0729            node.elements.removeAtIndex(slot)
0730            node.count -= 1
0731            self.count -= 1
0732            popFromSlots()
0733    
0734            while node !== root && node.isTooSmall {
0735                popFromPath()
0736                node = path.last!
0737                let slot = popFromSlots()
0738                node.fixDeficiency(slot)
0739            }
0740            while targetPosition != count && targetPosition == self.position && node !== root {
0741                popFromPath()
0742                node = path.last!
0743                popFromSlots()
0744            }
0745            if node === root && node.elements.count == 0 && node.children.count == 1 {
0746                assert(path.count == 1 && slots.count == 0)
0747                root = node.makeChildUnique(0)
0748                path[0] = root
0749            }
0750            descendToPosition(targetPosition)
0751            return result
0752        }
0753    
0754        /// Remove `n` elements starting at the cursor's current position, and position the cursor on the successor of
0755        /// the last element that was removed.
0756        ///
0757        /// - Complexity: O(log(`count`))
0758        public func removeList.swift:316             cursor.remove(n)
List.swift:328             cursor.remove(n)
List.swift:345             cursor.remove(range.count)
List.swift:363                 cursor.remove(range.endIndex - cursor.position)(n: Int) {
0759            precondition(isValid && n >= 0 && self.position + n <= count)
0760            if n == 0 { return }
0761            if n == 1 { remove(); return }
0762            if n == count { reset(Node(order: root.order)); return }
0763    
0764            let position = self.position
0765            if position == 0 {
0766                moveToPosition(n - 1)
0767                reset(startOf: finishAndKeepSuffix().root)
0768            }
0769            else if position == count - n {
0770                reset(endOf: finishAndKeepPrefix().root)
0771            }
0772            else {
0773                let (left, _, mid) = finishByCutting()
0774                reset(root: mid.root, position: n - 1)
0775                let (_, separator, right) = finishByCutting()
0776                reset(root: Node.join(left: left.root, separator: separator, right: right.root), position: position)
0777            }
0778        }
0779    
0780        /// Extract `n` elements starting at the cursor's current position, and position the cursor on the successor of
0781        /// the last element that was removed.
0782        ///
0783        /// - Returns: The extracted elements as a new b-tree.
0784        /// - Complexity: O(log(`count`))
0785        public func extract(n: Int) -> Tree {
0786            precondition(isValid && n >= 0 && self.position + n <= count)
0787            if n == 0 {
0788                return Tree(order: root.order)
0789            }
0790            if n == 1 {
0791                let element = remove()
0792                var tree = Tree(order: root.order)
0793                tree.insert(element)
0794                return tree
0795            }
0796            if n == count {
0797                let tree = finish()
0798                reset(Node(order: tree.root.order))
0799                return tree
0800            }
0801    
0802            let position = self.position
0803            if position == count - n {
0804                var cut = finishByCutting()
0805                reset(root: cut.left.root, position: position)
0806                cut.right.insert(cut.separator, at: 0)
0807                return cut.right
0808            }
0809            else {
0810                let cut1 = finishByCutting()
0811                reset(root: cut1.right.root, position: n - 1)
0812                var cut2 = finishByCutting()
0813                reset(root: Node.join(left: cut1.left.root, separator: cut2.separator, right: cut2.right.root), position: position)
0814                cut2.left.insert(cut1.separator, at: 0)
0815                return cut2.left
0816            }
0817        }
0818    
0819    }

BTreeCursor.swift:20	public mutating func withCursorAtPosition(position: Int, @noescape body: Cursor throws -> Void) rethrows {
BTreeCursor.swift:36	public mutating func withCursorAtStart(@noescape body: Cursor throws -> Void) rethrows {
BTreeCursor.swift:46	public mutating func withCursorAtEnd(@noescape body: Cursor throws -> Void) rethrows {
BTreeCursor.swift:57	public mutating func withCursorAt(key: Key, choosing selector: BTreeKeySelector = .Any, @noescape body: Cursor throws -> Void) rethrows {
BTreeCursor.swift:72	public mutating func withCursorAt(index: Index, @noescape body: Cursor throws -> Void) rethrows {

BTreeCursor.swift:37	try withCursorAtPosition(0, body: body)
BTreeCursor.swift:47	try withCursorAtPosition(count, body: body)
List.swift:274	tree.withCursorAtPosition(tree.count) { cursor in
List.swift:283	tree.withCursorAtPosition(tree.count) { cursor in
List.swift:292	tree.withCursorAtPosition(index) { cursor in
List.swift:298	tree.withCursorAtPosition(index) { cursor in
List.swift:315	tree.withCursorAtPosition(0) { cursor in
List.swift:327	tree.withCursorAtPosition(count - n) { cursor in
List.swift:344	tree.withCursorAtPosition(range.startIndex) { cursor in
List.swift:355	tree.withCursorAtPosition(range.startIndex) { cursor in

BTreeCursor.swift:12	public typealias Cursor = BTreeCursor<Key, Payload>
BTreeCursor.swift:23	let cursor = BTreeCursor(root)
BTreeCursor.swift:59	let cursor = BTreeCursor(root)
BTreeCursor.swift:74	let cursor = BTreeCursor(root)

BTreeCursor.swift:104	public typealias Element = (Key, Payload)
BTreeCursor.swift:105	public typealias Tree = BTree<Key, Payload>
BTreeCursor.swift:106	internal typealias Node = BTreeNode<Key, Payload>
BTreeCursor.swift:181	internal func reset(root root: Node, key: Key, choosing selector: BTreeKeySelector = .Any) {
BTreeCursor.swift:440	public func moveToKey(key: Key, choosing selector: BTreeKeySelector = .Any) {
BTreeCursor.swift:475	private func descendToKey(key: Key, choosing selector: BTreeKeySelector) {
BTreeCursor.swift:522	public var key: Key {

BTreeCursor.swift:104	public typealias Element = (Key, Payload)
BTreeCursor.swift:105	public typealias Tree = BTree<Key, Payload>
BTreeCursor.swift:106	internal typealias Node = BTreeNode<Key, Payload>
BTreeCursor.swift:536	public var payload: Payload {
BTreeCursor.swift:551	public func setPayload(payload: Payload) -> Payload {
BTreeCursor.swift:551	public func setPayload(payload: Payload) -> Payload {

BTreeCursor.swift:210	internal func finishByCutting() -> (left: Tree, separator: Element, right: Tree) {
BTreeCursor.swift:563	public func insertAfter(element: Element) {
BTreeCursor.swift:585	public func insert(element: Element) {
BTreeCursor.swift:706	public func insert<S: SequenceType where S.Generator.Element == Element>(elements: S) {
BTreeCursor.swift:713	public func remove() -> Element {

BTreeCursor.swift:193	internal func finish() -> Tree {
BTreeCursor.swift:202	return Tree(root)
BTreeCursor.swift:210	internal func finishByCutting() -> (left: Tree, separator: Element, right: Tree) {
BTreeCursor.swift:210	internal func finishByCutting() -> (left: Tree, separator: Element, right: Tree) {
BTreeCursor.swift:238	return (Tree(left), separator, Tree(right))
BTreeCursor.swift:238	return (Tree(left), separator, Tree(right))
BTreeCursor.swift:246	internal func finishAndKeepPrefix() -> Tree {
BTreeCursor.swift:262	return Tree(left)
BTreeCursor.swift:270	internal func finishAndKeepSuffix() -> Tree {
BTreeCursor.swift:286	return Tree(right)
BTreeCursor.swift:659	public func insert(tree: Tree) {
BTreeCursor.swift:785	public func extract(n: Int) -> Tree {
BTreeCursor.swift:788	return Tree(order: root.order)
BTreeCursor.swift:792	var tree = Tree(order: root.order)

BTreeCursor.swift:110	private var root: Node
BTreeCursor.swift:118	private var path: [Node]
BTreeCursor.swift:149	private init(_ root: Node) {
BTreeCursor.swift:159	private func reset(root: Node) {
BTreeCursor.swift:167	internal func reset(startOf root: Node) {
BTreeCursor.swift:171	internal func reset(endOf root: Node) {
BTreeCursor.swift:175	internal func reset(root root: Node, position: Int) {
BTreeCursor.swift:181	internal func reset(root root: Node, key: Key, choosing selector: BTreeKeySelector = .Any) {
BTreeCursor.swift:226	let l = slot == 1 ? node.makeChildUnique(0) : Node(node: node, slotRange: 0 ..< slot - 1)
BTreeCursor.swift:228	left = Node.join(left: l, separator: s, right: left)
BTreeCursor.swift:232	let r = slot == c - 1 ? node.makeChildUnique(c) : Node(node: node, slotRange: slot + 1 ..< c)
BTreeCursor.swift:234	right = Node.join(left: right, separator: s, right: r)
BTreeCursor.swift:257	let l = slot == 1 ? node.makeChildUnique(0) : Node(node: node, slotRange: 0 ..< slot - 1)
BTreeCursor.swift:259	left = Node.join(left: l, separator: s, right: left)
BTreeCursor.swift:281	let r = slot == c - 1 ? node.makeChildUnique(c) : Node(node: node, slotRange: slot + 1 ..< c)
BTreeCursor.swift:283	right = Node.join(left: right, separator: s, right: r)
BTreeCursor.swift:293	self.root = Node()
BTreeCursor.swift:307	private func popFromPath() -> Node {
BTreeCursor.swift:315	private func pushToPath() -> Node {
BTreeCursor.swift:642	self.root = Node(left: left, separator: splinter.separator, right: right)
BTreeCursor.swift:664	private func insertWithoutCloning(root: Node) {
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:762	if n == count { reset(Node(order: root.order)); return }
BTreeCursor.swift:776	reset(root: Node.join(left: left.root, separator: separator, right: right.root), position: position)
BTreeCursor.swift:798	reset(Node(order: tree.root.order))
BTreeCursor.swift:813	reset(root: Node.join(left: cut1.left.root, separator: cut2.separator, right: cut2.right.root), position: position)

BTreeCursor.swift:150	self.root = root
BTreeCursor.swift:160	self.root = root
BTreeCursor.swift:200	assert(root.count == count)
BTreeCursor.swift:202	return Tree(root)
BTreeCursor.swift:293	self.root = Node()
BTreeCursor.swift:642	self.root = Node(left: left, separator: splinter.separator, right: right)
BTreeCursor.swift:643	path.insert(self.root, atIndex: 0)
BTreeCursor.swift:734	while node !== root && node.isTooSmall {
BTreeCursor.swift:740	while targetPosition != count && targetPosition == self.position && node !== root {
BTreeCursor.swift:745	if node === root && node.elements.count == 0 && node.children.count == 1 {
BTreeCursor.swift:747	root = node.makeChildUnique(0)
BTreeCursor.swift:748	path[0] = root
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:143	public var isValid: Bool { return !path.isEmpty }
BTreeCursor.swift:153	self.path = [root]
BTreeCursor.swift:163	self.path = [root]
BTreeCursor.swift:195	while !path.isEmpty {
BTreeCursor.swift:196	let node = path.removeLast()
BTreeCursor.swift:213	var left = path.removeLast()
BTreeCursor.swift:222	while !path.isEmpty {
BTreeCursor.swift:223	let node = path.removeLast()
BTreeCursor.swift:248	var left = path.removeLast()
BTreeCursor.swift:253	while !path.isEmpty {
BTreeCursor.swift:254	let node = path.removeLast()
BTreeCursor.swift:272	var right = path.removeLast().split(slots.removeLast()).node
BTreeCursor.swift:276	while !path.isEmpty {
BTreeCursor.swift:277	let node = path.removeLast()
BTreeCursor.swift:296	self.path = []
BTreeCursor.swift:301	assert(path.count == slots.count)
BTreeCursor.swift:303	let node = path.last!
BTreeCursor.swift:308	assert(path.count > 1 && path.count == slots.count + 1)
BTreeCursor.swift:308	assert(path.count > 1 && path.count == slots.count + 1)
BTreeCursor.swift:309	let child = path.removeLast()
BTreeCursor.swift:310	let parent = path.last!
BTreeCursor.swift:316	assert(path.count == slots.count)
BTreeCursor.swift:317	let parent = path.last!
BTreeCursor.swift:321	path.append(child)
BTreeCursor.swift:325	assert(path.count == slots.count + 1)
BTreeCursor.swift:326	let node = path.last!
BTreeCursor.swift:339	let node = path.last!
BTreeCursor.swift:349	} while slots.last! == path.last!.elements.count
BTreeCursor.swift:371	let node = path.last!
BTreeCursor.swift:385	precondition(path.count > 0)
BTreeCursor.swift:386	assert(!path.last!.isLeaf)
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:442	while path.count > 1 && !path.last!.contains(key, choosing: selector) {
BTreeCursor.swift:442	while path.count > 1 && !path.last!.contains(key, choosing: selector) {
BTreeCursor.swift:450	assert(self.path.count == self.slots.count + 1)
BTreeCursor.swift:461	assert(position >= self.position - path.last!.count && position <= self.position)
BTreeCursor.swift:462	assert(self.path.count == self.slots.count + 1)
BTreeCursor.swift:463	var node = path.last!
BTreeCursor.swift:472	assert(path.count == slots.count)
BTreeCursor.swift:476	assert(self.path.count == self.slots.count + 1)
BTreeCursor.swift:482	var node = path.last!
BTreeCursor.swift:491	match = (depth: path.count, slot: m)
BTreeCursor.swift:495	for _ in 0 ..< path.count - m.depth {
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:553	let node = path.last!
BTreeCursor.swift:566	if path.last!.isLeaf {
BTreeCursor.swift:567	let node = path.last!
BTreeCursor.swift:575	let node = path.last!
BTreeCursor.swift:588	if path.last!.isLeaf {
BTreeCursor.swift:589	let node = path.last!
BTreeCursor.swift:595	let node = path.last!
BTreeCursor.swift:606	guard path.last!.isTooLarge else { return }
BTreeCursor.swift:609	var i = path.count - 1
BTreeCursor.swift:610	while path[i].isTooLarge {
BTreeCursor.swift:612	let left = path[i]
BTreeCursor.swift:619	path[i] = right
BTreeCursor.swift:623	assert(i == path.count - 1)
BTreeCursor.swift:624	path.removeLast()
BTreeCursor.swift:630	let parent = path[i - 1]
BTreeCursor.swift:643	path.insert(self.root, atIndex: 0)
BTreeCursor.swift:650	while i < path.count - 1 {
BTreeCursor.swift:651	path[i].count -= path[i + 1].count
BTreeCursor.swift:651	path[i].count -= path[i + 1].count
BTreeCursor.swift:715	var node = path.last!
BTreeCursor.swift:736	node = path.last!
BTreeCursor.swift:742	node = path.last!
BTreeCursor.swift:746	assert(path.count == 1 && slots.count == 0)
BTreeCursor.swift:748	path[0] = root

BTreeCursor.swift:408	popFromSlots()
BTreeCursor.swift:411	popFromSlots()
BTreeCursor.swift:427	popFromSlots()
BTreeCursor.swift:430	popFromSlots()
BTreeCursor.swift:441	popFromSlots()
BTreeCursor.swift:444	popFromSlots()
BTreeCursor.swift:497	popFromSlots()
BTreeCursor.swift:732	popFromSlots()
BTreeCursor.swift:737	let slot = popFromSlots()
BTreeCursor.swift:743	popFromSlots()

BTreeCursor.swift:348	popFromPath()
BTreeCursor.swift:379	popFromPath()
BTreeCursor.swift:410	popFromPath()
BTreeCursor.swift:429	popFromPath()
BTreeCursor.swift:443	popFromPath()
BTreeCursor.swift:496	popFromPath()
BTreeCursor.swift:735	popFromPath()
BTreeCursor.swift:741	popFromPath()

BTreeCursor.swift:506	moveForward()
BTreeCursor.swift:574	moveForward()
BTreeCursor.swift:602	moveForward()
BTreeCursor.swift:725	moveForward()
List.swift:360	cursor.moveForward()

BTreeCursor.swift:594	moveBackward()
BTreeCursor.swift:680	moveBackward()
BTreeCursor.swift:693	moveBackward()
BTreeCursor.swift:721	moveBackward()

BTreeCursor.swift:154	self.slots = []
BTreeCursor.swift:164	self.slots = []
BTreeCursor.swift:214	var (separator, right) = left.split(slots.removeLast()).exploded
BTreeCursor.swift:224	let slot = slots.removeLast()
BTreeCursor.swift:249	_ = left.split(slots.removeLast())
BTreeCursor.swift:255	let slot = slots.removeLast()
BTreeCursor.swift:272	var right = path.removeLast().split(slots.removeLast()).node
BTreeCursor.swift:278	let slot = slots.removeLast()
BTreeCursor.swift:297	self.slots = []
BTreeCursor.swift:301	assert(path.count == slots.count)
BTreeCursor.swift:302	let slot = slots.removeLast()
BTreeCursor.swift:308	assert(path.count > 1 && path.count == slots.count + 1)
BTreeCursor.swift:316	assert(path.count == slots.count)
BTreeCursor.swift:318	let slot = slots.last!
BTreeCursor.swift:325	assert(path.count == slots.count + 1)
BTreeCursor.swift:329	self.slots.append(slot)
BTreeCursor.swift:341	if slots.last! < node.elements.count - 1 \|\| _position == count {
BTreeCursor.swift:342	slots[slots.count - 1] += 1
BTreeCursor.swift:342	slots[slots.count - 1] += 1
BTreeCursor.swift:347	slots.removeLast()
BTreeCursor.swift:349	} while slots.last! == path.last!.elements.count
BTreeCursor.swift:354	slots[slots.count - 1] += 1
BTreeCursor.swift:354	slots[slots.count - 1] += 1
BTreeCursor.swift:357	slots.append(0)
BTreeCursor.swift:360	slots.append(0)
BTreeCursor.swift:373	if slots.last! > 0 {
BTreeCursor.swift:374	slots[slots.count - 1] -= 1
BTreeCursor.swift:374	slots[slots.count - 1] -= 1
BTreeCursor.swift:378	slots.removeLast()
BTreeCursor.swift:380	} while slots.last! == 0
BTreeCursor.swift:381	slots[slots.count - 1] -= 1
BTreeCursor.swift:381	slots[slots.count - 1] -= 1
BTreeCursor.swift:390	slots.append(slot)
BTreeCursor.swift:393	slots.append(node.elements.count - 1)
BTreeCursor.swift:450	assert(self.path.count == self.slots.count + 1)
BTreeCursor.swift:462	assert(self.path.count == self.slots.count + 1)
BTreeCursor.swift:472	assert(path.count == slots.count)
BTreeCursor.swift:476	assert(self.path.count == self.slots.count + 1)
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:554	let slot = slots.last!
BTreeCursor.swift:568	let slot = slots.last!
BTreeCursor.swift:570	slots[slots.count - 1] = slot + 1
BTreeCursor.swift:570	slots[slots.count - 1] = slot + 1
BTreeCursor.swift:576	assert(node.isLeaf && slots.last == 0)
BTreeCursor.swift:590	let slot = slots.last!
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:598	slots[slots.count - 1] = node.elements.count - 1
BTreeCursor.swift:613	let slot = slots[i]
BTreeCursor.swift:618	slots[i] = slot - left.elements.count - 1
BTreeCursor.swift:625	slots.removeLast()
BTreeCursor.swift:631	let pslot = slots[i - 1]
BTreeCursor.swift:636	slots[i - 1] = pslot + 1
BTreeCursor.swift:644	slots.insert(slot > left.elements.count ? 1 : 0, atIndex: 0)
BTreeCursor.swift:716	let slot = slots.last!
BTreeCursor.swift:746	assert(path.count == 1 && slots.count == 0)

BTreeCursor.swift:145	public var isAtEnd: Bool { return _position == count }
BTreeCursor.swift:151	self.count = root.count
BTreeCursor.swift:161	self.count = root.count
BTreeCursor.swift:200	assert(root.count == count)
BTreeCursor.swift:294	self.count = 0
BTreeCursor.swift:337	precondition(self.position < count)
BTreeCursor.swift:341	if slots.last! < node.elements.count - 1 \|\| _position == count {
BTreeCursor.swift:409	while self.count > self.position + path.last!.count {
BTreeCursor.swift:413	self.descendToPosition(self.count)
BTreeCursor.swift:421	precondition(isValid && position >= 0 && position <= count)
BTreeCursor.swift:422	if position == count {
BTreeCursor.swift:477	if count == 0 {
BTreeCursor.swift:565	count += 1
BTreeCursor.swift:587	count += 1
BTreeCursor.swift:672	if self.count == 0 {
BTreeCursor.swift:678	if position == self.count {
BTreeCursor.swift:731	self.count -= 1
BTreeCursor.swift:740	while targetPosition != count && targetPosition == self.position && node !== root {
BTreeCursor.swift:759	precondition(isValid && n >= 0 && self.position + n <= count)
BTreeCursor.swift:762	if n == count { reset(Node(order: root.order)); return }
BTreeCursor.swift:769	else if position == count - n {
BTreeCursor.swift:786	precondition(isValid && n >= 0 && self.position + n <= count)
BTreeCursor.swift:796	if n == count {
BTreeCursor.swift:803	if position == count - n {

BTreeCursor.swift:134	return _position
BTreeCursor.swift:144	public var isAtStart: Bool { return _position == 0 }
BTreeCursor.swift:145	public var isAtEnd: Bool { return _position == count }
BTreeCursor.swift:152	self._position = root.count
BTreeCursor.swift:162	self._position = root.count
BTreeCursor.swift:295	self._position = 0
BTreeCursor.swift:304	self._position += node.count - node.positionOfSlot(slot)
BTreeCursor.swift:328	self._position -= node.count - p
BTreeCursor.swift:338	_position += 1
BTreeCursor.swift:341	if slots.last! < node.elements.count - 1 \|\| _position == count {
BTreeCursor.swift:370	_position -= 1
BTreeCursor.swift:571	_position += 1
BTreeCursor.swift:599	_position += 1

BTreeCursor.swift:337	precondition(self.position < count)
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: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: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:471	assert(self.position == position)
BTreeCursor.swift:677	let position = self.position
BTreeCursor.swift:728	let targetPosition = self.position
BTreeCursor.swift:740	while targetPosition != count && targetPosition == self.position && node !== root {
BTreeCursor.swift:759	precondition(isValid && n >= 0 && self.position + n <= count)
BTreeCursor.swift:764	let position = self.position
BTreeCursor.swift:786	precondition(isValid && n >= 0 && self.position + n <= count)
BTreeCursor.swift:802	let position = self.position
List.swift:357	while cursor.position < range.endIndex {
List.swift:362	if cursor.position < range.endIndex {
List.swift:363	cursor.remove(range.endIndex - cursor.position)

BTreeCursor.swift:421	precondition(isValid && position >= 0 && position <= count)
BTreeCursor.swift:586	precondition(self.isValid)
BTreeCursor.swift:665	precondition(isValid)
BTreeCursor.swift:759	precondition(isValid && n >= 0 && self.position + n <= count)
BTreeCursor.swift:786	precondition(isValid && n >= 0 && self.position + n <= count)

BTreeCursor.swift:211	precondition(!isAtEnd)
BTreeCursor.swift:247	precondition(!isAtEnd)
BTreeCursor.swift:271	precondition(!isAtEnd)
BTreeCursor.swift:524	precondition(!self.isAtEnd)
BTreeCursor.swift:528	precondition(!self.isAtEnd)
BTreeCursor.swift:538	precondition(!self.isAtEnd)
BTreeCursor.swift:542	precondition(!self.isAtEnd)
BTreeCursor.swift:552	precondition(!self.isAtEnd)
BTreeCursor.swift:564	precondition(!self.isAtEnd)
BTreeCursor.swift:714	precondition(!isAtEnd)

BTreeCursor.swift:177	reset(root)
BTreeCursor.swift:182	reset(root)
BTreeCursor.swift:762	if n == count { reset(Node(order: root.order)); return }
BTreeCursor.swift:798	reset(Node(order: tree.root.order))

BTreeCursor.swift:673	reset(endOf: root)
BTreeCursor.swift:683	reset(endOf: Node.join(left: left.root, separator: separator, right: root))
BTreeCursor.swift:770	reset(endOf: finishAndKeepPrefix().root)

BTreeCursor.swift:168	reset(root: root, position: 0)
BTreeCursor.swift:172	reset(root: root, position: root.count)
BTreeCursor.swift:689	reset(root: Node.join(left: root, separator: separator, right: right.root), position: position + c)
BTreeCursor.swift:698	reset(root: t2, position: position + c)
BTreeCursor.swift:774	reset(root: mid.root, position: n - 1)
BTreeCursor.swift:776	reset(root: Node.join(left: left.root, separator: separator, right: right.root), position: position)
BTreeCursor.swift:805	reset(root: cut.left.root, position: position)
BTreeCursor.swift:811	reset(root: cut1.right.root, position: n - 1)
BTreeCursor.swift:813	reset(root: Node.join(left: cut1.left.root, separator: cut2.separator, right: cut2.right.root), position: position)

BTreeCursor.swift:26	defer { self = cursor.finish() }
BTreeCursor.swift:62	defer { self = cursor.finish() }
BTreeCursor.swift:77	defer { self = cursor.finish() }
BTreeCursor.swift:682	let left = finish()
BTreeCursor.swift:688	let right = finish()
BTreeCursor.swift:797	let tree = finish()

BTreeCursor.swift:695	let (prefix, sep2, suffix) = finishByCutting()
BTreeCursor.swift:773	let (left, _, mid) = finishByCutting()
BTreeCursor.swift:775	let (_, separator, right) = finishByCutting()
BTreeCursor.swift:804	var cut = finishByCutting()
BTreeCursor.swift:810	let cut1 = finishByCutting()
BTreeCursor.swift:812	var cut2 = finishByCutting()

BTreeCursor.swift:355	var node = pushToPath()
BTreeCursor.swift:358	node = pushToPath()
BTreeCursor.swift:387	var node = pushToPath()
BTreeCursor.swift:391	node = pushToPath()
BTreeCursor.swift:455	pushToPath()
BTreeCursor.swift:467	node = pushToPath()
BTreeCursor.swift:511	node = pushToPath()

BTreeCursor.swift:453	pushToSlots(slot)
BTreeCursor.swift:465	pushToSlots(slot.index, positionOfSlot: slot.position)
BTreeCursor.swift:469	pushToSlots(slot.index, positionOfSlot: slot.position)
BTreeCursor.swift:478	pushToSlots(0)
BTreeCursor.swift:488	pushToSlots(m)
BTreeCursor.swift:499	pushToSlots(m.slot)
BTreeCursor.swift:502	pushToSlots(slot.descend)
BTreeCursor.swift:505	pushToSlots(slot.descend - 1)
BTreeCursor.swift:510	pushToSlots(slot.descend)

BTreeCursor.swift:137	moveToPosition(newValue)
BTreeCursor.swift:401	moveToPosition(0)
BTreeCursor.swift:766	moveToPosition(n - 1)

BTreeCursor.swift:24	cursor.descendToPosition(position)
BTreeCursor.swift:178	descendToPosition(position)
BTreeCursor.swift:413	self.descendToPosition(self.count)
BTreeCursor.swift:432	self.descendToPosition(position)
BTreeCursor.swift:750	descendToPosition(targetPosition)

BTreeCursor.swift:60	cursor.descendToKey(key, choosing: selector)
BTreeCursor.swift:183	descendToKey(key, choosing: selector)
BTreeCursor.swift:446	self.descendToKey(key, choosing: selector)

BTreeCursor.swift:724	self.payload = surrogate.1
List.swift:359	cursor.payload = element

BTreeCursor.swift:579	fixupAfterInsert()
BTreeCursor.swift:601	fixupAfterInsert()

List.swift:275	cursor.insert(list.tree)
List.swift:293	cursor.insert(list.tree)

BTreeCursor.swift:661	insertWithoutCloning(root)
BTreeCursor.swift:707	insertWithoutCloning(BTree(sortedElements: elements).root)