0001 // 0002 // BTree.swift 0003 // BTree 0004 // 0005 // Created by Károly Lőrentey on 2016-02-19. 0006 // Copyright © 2015–2016 Károly Lőrentey. 0007 // 0008 0009 /// B-trees are search trees that provide an ordered key-value store with excellent performance characteristics. 0010 public struct BTree<Key
BTree.swift:35 public extension BTree {BTree.swift:50 extension BTree: SequenceType {BTree.swift:76 extension BTree: CollectionType {BTree.swift:119 public extension BTree {BTree.swift:289 extension BTree {BTree.swift:318 extension BTree {BTree.swift:503 extension BTree {BTree.swift:610 extension BTree {BTreeCursor.swift:11 extension BTree {BTreeCursor.swift:105 BTreeCursor.swift:707 List.swift:28 Map.swift:33 : Comparable, Payload
BTree.swift:11 BTree.swift:12 > { 0011 public typealias Element
BTree.swift:11 BTree.swift:12 = (Key, Payload) 0012 internal typealias Node
BTree.swift:62 public func forEach(@noescape body: (Element) throws -> ()) rethrows {BTree.swift:69 public func forEach(@noescape body: (Element) throws -> Bool) rethrows -> Bool {BTree.swift:124 public func elementAtPosition(position: Int) -> Element {BTree.swift:326 public mutating func insert(element: Element, at position: Int) {BTree.swift:406 public mutating func insert(element: Element, at selector: BTreeKeySelector = .Any) {BTree.swift:441 public mutating func insertOrReplace(element: Element, at selector: BTreeKeySelector = .Any) -> Payload? {BTree.swift:509 public mutating func removeAt(position: Int) -> Element {BTree.swift:514 BTree.swift:567 BTree.swift:619 public init<S: SequenceType where S.Generator.Element == Element>(sortedElements elements: S, order: Int = Node.defaultOrder, fillFactor: Double = 1) {BTree.swift:635 BTree.swift:704 public init<S: SequenceType where S.Generator.Element == Element>(elements: S, order: Int = Node.defaultOrder, fillFactor: Double = 1) {= BTreeNode<Key, Payload> 0013 0014 internal var root
BTree.swift:14 BTree.swift:16 internal init(_ root: Node) {BTree.swift:23 public init(order: Int = Node.defaultOrder) {BTree.swift:24 BTree.swift:310 internal mutating func edit(@noescape descend descend: Node -> Int?, @noescape ascend: (Node, Int) -> Void) {BTree.swift:310 internal mutating func edit(@noescape descend descend: Node -> Int?, @noescape ascend: (Node, Int) -> Void) {BTree.swift:367 BTree.swift:431 BTree.swift:444 BTree.swift:495 BTree.swift:513 BTree.swift:568 BTree.swift:619 public init<S: SequenceType where S.Generator.Element == Element>(sortedElements elements: S, order: Int = Node.defaultOrder, fillFactor: Double = 1) {BTree.swift:634 BTree.swift:638 BTree.swift:672 BTree.swift:679 BTree.swift:692 BTree.swift:704 public init<S: SequenceType where S.Generator.Element == Element>(elements: S, order: Int = Node.defaultOrder, fillFactor: Double = 1) {BTreeCursor.swift:25 BTreeCursor.swift:61 BTreeCursor.swift:76 : Node 0015 0016 internal init
BTree.swift:17 BTree.swift:24 BTree.swift:28 public var order: Int { return root.order }BTree.swift:30 public var depth: Int { return root.depth }BTree.swift:38 BTree.swift:44 BTree.swift:44 BTree.swift:54 public var isEmpty: Bool { return root.count == 0 }BTree.swift:58 BTree.swift:63 BTree.swift:70 BTree.swift:81 BTree.swift:86 BTree.swift:91 BTree.swift:97 BTree.swift:127 BTree.swift:147 BTree.swift:160 BTree.swift:181 BTree.swift:182 BTree.swift:213 BTree.swift:240 BTree.swift:266 BTree.swift:268 BTree.swift:312 BTree.swift:367 BTree.swift:367 BTree.swift:431 BTree.swift:431 BTree.swift:495 BTree.swift:495 BTree.swift:551 if root.children.count == 1 {BTree.swift:552 BTree.swift:553 BTree.swift:553 BTree.swift:600 if root.children.count == 1 {BTree.swift:601 BTree.swift:602 BTree.swift:602 BTree.swift:685 BTree.swift:688 BTree.swift:692 BTree.swift:692 BTreeCursor.swift:23 BTreeCursor.swift:25 BTreeCursor.swift:59 BTreeCursor.swift:61 BTreeCursor.swift:74 BTreeCursor.swift:76 BTreeCursor.swift:660 BTreeCursor.swift:683 BTreeCursor.swift:689 BTreeCursor.swift:696 BTreeCursor.swift:697 BTreeCursor.swift:707 BTreeCursor.swift:767 BTreeCursor.swift:770 BTreeCursor.swift:774 BTreeCursor.swift:776 BTreeCursor.swift:776 BTreeCursor.swift:798 BTreeCursor.swift:805 BTreeCursor.swift:811 BTreeCursor.swift:813 BTreeCursor.swift:813 (_ root: Node) { 0017 self.root = root 0018 } 0019 0020 /// Initialize a new b-tree with no elements. 0021 /// 0022 /// - Parameter order: The maximum number of children for tree nodes. 0023 public init
BTreeCursor.swift:202 BTreeCursor.swift:238 BTreeCursor.swift:238 BTreeCursor.swift:262 BTreeCursor.swift:286 (order: Int = Node.defaultOrder) { 0024 self.root = Node(order: order) 0025 } 0026 0027 /// The order of this tree, i.e., the maximum number of children for tree nodes. 0028 public var order: Int { return root.order } 0029 /// The depth of this tree. Depth starts at 0 for a tree that has a single root node. 0030 public var depth: Int { return root.depth } 0031 } 0032 0033 //MAKE: Uniquing 0034 0035 public extension BTree { 0036 internal var isUnique
BTreeCursor.swift:788 BTreeCursor.swift:792 List.swift:35 List.swift:350 Map.swift:40 Map.swift:230 : Bool { 0037 mutating get { 0038 return isUniquelyReferenced(&root) 0039 } 0040 } 0041 0042 internal mutating func makeUnique
BTree.swift:43 guard !isUnique else { return }() { 0043 guard !isUnique else { return } 0044 root = root.clone() 0045 } 0046 } 0047 0048 //MARK: SequenceType 0049 0050 extension BTree: SequenceType { 0051 public typealias Generator
BTree.swift:311 BTree.swift:328 BTree.swift:379 BTree.swift:407 BTree.swift:442 BTree.swift:511 BTree.swift:566 BTreeCursor.swift:22 BTreeCursor.swift:58 BTreeCursor.swift:73 = BTreeGenerator<Key, Payload> 0052 0053 /// Returns true iff this tree has no elements. 0054 public var isEmpty: Bool { return root.count == 0 } 0055 0056 /// Returns a generator over the elements of this b-tree. Elements are sorted by key. 0057 public func generate
BTree.swift:57 public func generate() -> Generator {BTree.swift:58 () -> Generator { 0058 return Generator(self.root) 0059 } 0060 0061 /// Call `body` on each element in self in the same order as a for-in loop. 0062 public func forEach
List.swift:84 Map.swift:84 (@noescape body: (Element) throws -> ()) rethrows { 0063 try root.forEach(body) 0064 } 0065 0066 /// A version of `forEach` that allows `body` to interrupt iteration by returning `false`. 0067 /// 0068 /// - Returns: `true` iff `body` returned true for all elements in the tree. 0069 public func forEach
List.swift:108 try tree.forEach { try body($0.1) }Map.swift:95 (@noescape body: (Element) throws -> Bool) rethrows -> Bool { 0070 return try root.forEach(body) 0071 } 0072 } 0073 0074 //MARK: CollectionType 0075 0076 extension BTree: CollectionType { 0077 public typealias Index
List.swift:187 try self.tree.forEach { element -> Bool inList.swift:204 self.tree.forEach { e -> Bool in= BTreeIndex<Key, Payload> 0078 0079 /// The index of the first element of this tree. Elements are sorted by key. 0080 public var startIndex
BTree.swift:81 BTree.swift:80 public var startIndex: Index {BTree.swift:86 BTree.swift:85 public var endIndex: Index {BTree.swift:180 public func indexOf(key: Key, choosing selector: BTreeKeySelector = .Any) -> Index? {BTree.swift:205 BTree.swift:239 public func positionOfIndex(index: Index) -> Int {BTree.swift:263 public func indexOfPosition(position: Int) -> Index {BTree.swift:273 BTree.swift:282 BTreeCursor.swift:72 public mutating func withCursorAt(index: Index, @noescape body: Cursor throws -> Void) rethrows {: Index { 0081 return Index(startIndexOf: root) 0082 } 0083 0084 /// The index after the last element of this tree. (Equals `startIndex` when the tree is empty.) 0085 public var endIndex
Map.swift:53 : Index { 0086 return Index(endIndexOf: root) 0087 } 0088 0089 /// The number of elements in this tree. 0090 public var count
Map.swift:58 : Int { 0091 return root.count 0092 } 0093 0094 /// Returns the element at `index`. 0095 public subscript
BTree.swift:125 BTree.swift:242 BTree.swift:264 BTree.swift:327 BTree.swift:329 BTree.swift:378 BTree.swift:380 BTree.swift:510 BTree.swift:512 BTreeCursor.swift:21 BTreeCursor.swift:47 List.swift:56 List.swift:61 List.swift:66 List.swift:260 List.swift:274 tree.withCursorAtPosition(tree.count) { cursor inList.swift:283 tree.withCursorAtPosition(tree.count) { cursor inMap.swift:65 (index: Index) -> Element { 0096 get { 0097 precondition(index.root.value === self.root) 0098 let node = index.path.last!.value! 0099 return node.elements[index.slots.last!] 0100 } 0101 } 0102 } 0103 0104 //MARK: Lookups 0105 0106 /// When the tree contains multiple elements with the same key, you can use a key selector to specify 0107 /// that you want to use the first or last matching element, or that you don't care which element you get. 0108 /// (The latter is sometimes faster.) 0109 public enum BTreeKeySelector
Map.swift:78 { 0110 /// Look for the first element that matches the key, or insert a new element before existing matches. 0111 case First
BTree.swift:144 public func payloadOf(key: Key, choosing selector: BTreeKeySelector = .Any) -> Payload? {BTree.swift:180 public func indexOf(key: Key, choosing selector: BTreeKeySelector = .Any) -> Index? {BTree.swift:212 public func positionOf(key: Key, choosing selector: BTreeKeySelector = .Any) -> Int? {BTree.swift:406 public mutating func insert(element: Element, at selector: BTreeKeySelector = .Any) {BTree.swift:441 public mutating func insertOrReplace(element: Element, at selector: BTreeKeySelector = .Any) -> Payload? {BTree.swift:565 public mutating func remove(key: Key, at selector: BTreeKeySelector = .Any) -> Payload? {BTreeCursor.swift:57 public mutating func withCursorAt(key: Key, choosing selector: BTreeKeySelector = .Any, @noescape body: Cursor throws -> Void) rethrows {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) {BTreeNode.swift:198 internal func slotOf(key: Key, choosing selector: BTreeKeySelector = .First) -> (match: Int?, descend: Int) {BTreeNode.swift:292 internal func contains(key: Key, choosing selector: BTreeKeySelector) -> Bool {0112 /// Look for the last element that matches the key, or insert a new element after existing matches. 0113 case Last
BTree.swift:149 BTree.swift:159 BTreeNode.swift:198 internal func slotOf(key: Key, choosing selector: BTreeKeySelector = .First) -> (match: Int?, descend: Int) {BTreeNode.swift:200 BTreeNode.swift:299 0114 /// Accept any element that matches the key. This is sometimes faster, because the search may stop before reaching 0115 /// a leaf node. 0116 case Any
BTree.swift:159 BTree.swift:408 BTreeNode.swift:213 BTreeNode.swift:305 0117 } 0118 0119 public extension BTree { 0120 /// Returns the element at `position`. 0121 /// 0122 /// - Requires: `position >= 0 && position < count` 0123 /// - Complexity: O(log(`count`)) 0124 public func elementAtPosition
BTree.swift:144 public func payloadOf(key: Key, choosing selector: BTreeKeySelector = .Any) -> Payload? {BTree.swift:146 BTree.swift:180 public func indexOf(key: Key, choosing selector: BTreeKeySelector = .Any) -> Index? {BTree.swift:212 public func positionOf(key: Key, choosing selector: BTreeKeySelector = .Any) -> Int? {BTree.swift:406 public mutating func insert(element: Element, at selector: BTreeKeySelector = .Any) {BTree.swift:408 BTree.swift:441 public mutating func insertOrReplace(element: Element, at selector: BTreeKeySelector = .Any) -> Payload? {BTree.swift:465 if selector == .Any {BTree.swift:565 public mutating func remove(key: Key, at selector: BTreeKeySelector = .Any) -> Payload? {BTreeCursor.swift:57 public mutating func withCursorAt(key: Key, choosing selector: BTreeKeySelector = .Any, @noescape body: Cursor throws -> Void) rethrows {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:487 if node.isLeaf || selector == .Any {BTreeNode.swift:200 (position: Int) -> Element { 0125 precondition(position >= 0 && position < count) 0126 var position = position 0127 var node = root 0128 while !node.isLeaf { 0129 let slot = node.slotOfPosition(position) 0130 if slot.match { 0131 return node.elements[slot.index] 0132 } 0133 let child = node.children[slot.index] 0134 position -= slot.position - child.count 0135 node = child 0136 } 0137 return node.elements[position] 0138 } 0139 0140 /// Returns the payload of an element of this tree with the specified key, or `nil` if there is no such element. 0141 /// If there are multiple elements with the same key, `selector` indicates which matching element to find. 0142 /// 0143 /// - Complexity: O(log(`count`)) 0144 public func payloadOf
List.swift:74 (key: Key, choosing selector: BTreeKeySelector = .Any) -> Payload? { 0145 switch selector { 0146 case .Any: 0147 var node = root 0148 while true { 0149 let slot = node.slotOf(key, choosing: .First) 0150 if let m = slot.match { 0151 return node.elements[m].1 0152 } 0153 if node.isLeaf { 0154 break 0155 } 0156 node = node.children[slot.descend] 0157 } 0158 return nil 0159 case .First, .Last: 0160 var node = root 0161 var lastmatch: Payload? = nil 0162 while true { 0163 let slot = node.slotOf(key, choosing: selector) 0164 if let m = slot.match { 0165 lastmatch = node.elements[m].1 0166 } 0167 if node.isLeaf { 0168 break 0169 } 0170 node = node.children[slot.descend] 0171 } 0172 return lastmatch 0173 } 0174 } 0175 0176 /// Returns an index to an element in this tree with the specified key, or `nil` if there is no such element. 0177 /// If there are multiple elements with the same key, `selector` indicates which matching element to find. 0178 /// 0179 /// - Complexity: O(log(`count`)) 0180 public func indexOf
Map.swift:174 (key: Key, choosing selector: BTreeKeySelector = .Any) -> Index? { 0181 var node = root 0182 var path = [Weak(root)] 0183 var slots: [Int] = [] 0184 var match = 0 0185 var matchSlot = 0 0186 while true { 0187 let slot = node.slotOf(key, choosing: selector) 0188 if let m = slot.match { 0189 match = path.count 0190 matchSlot = m 0191 } 0192 if node.isLeaf { 0193 break 0194 } 0195 node = node.children[slot.descend] 0196 slots.append(slot.descend) 0197 path.append(Weak(node)) 0198 } 0199 if match == 0 { 0200 return nil 0201 } 0202 path.removeRange(match ..< path.count) 0203 slots.removeRange(match - 1 ..< slots.count) 0204 slots.append(matchSlot) 0205 return Index(path: path, slots: slots) 0206 } 0207 0208 /// Returns the position of the first element in this tree with the specified key, or `nil` if there is no such element. 0209 /// If there are multiple elements with the same key, `selector` indicates which matching element to find. 0210 /// 0211 /// - Complexity: O(log(`count`)) 0212 public func positionOf(key: Key, choosing selector: BTreeKeySelector = .Any) -> Int? { 0213 var node = root 0214 var position = 0 0215 var match: Int? = nil 0216 while !node.isLeaf { 0217 let slot = node.slotOf(key, choosing: selector) 0218 let child = node.children[slot.descend] 0219 if let m = slot.match { 0220 let p = node.positionOfSlot(m) 0221 match = position + p 0222 position += p - (m == slot.descend ? node.children[m].count : 0) 0223 } 0224 else { 0225 position += node.positionOfSlot(slot.descend) - child.count 0226 } 0227 node = child 0228 } 0229 let slot = node.slotOf(key, choosing: selector) 0230 if let m = slot.match { 0231 return position + m 0232 } 0233 return match 0234 } 0235 0236 /// Returns the position of the element at `index`. 0237 /// 0238 /// - Complexity: O(log(`count`)) 0239 public func positionOfIndex(index: Index) -> Int { 0240 index.expectValid(index.path[0].value === root) 0241 if index.path.count == 0 { 0242 return self.count 0243 } 0244 guard var last = index.path.last?.value else { index.invalid() } 0245 var position = last.positionOfSlot(index.slots.last!) 0246 for i in (0 ..< index.path.count - 1).reverse() { 0247 guard let node = index.path[i].value else { index.invalid() } 0248 let slot = index.slots[i] 0249 index.expectValid(node.children[slot] === last) 0250 index.expectValid(slot < node.children.count) 0251 if slot > 0 { 0252 position += node.positionOfSlot(slot - 1) + 1 0253 } 0254 last = node 0255 } 0256 return position 0257 } 0258 0259 /// Returns the index of the element at `position`. 0260 /// 0261 /// - Requires: `position >= 0 && position < count` 0262 /// - Complexity: O(log(`count`)) 0263 public func indexOfPosition(position: Int) -> Index { 0264 precondition(position >= 0 && position < count) 0265 var position = position 0266 var path = [Weak(root)] 0267 var slots: [Int] = [] 0268 var node = root 0269 while !node.isLeaf { 0270 let slot = node.slotOfPosition(position) 0271 slots.append(slot.index) 0272 if slot.match { 0273 return Index(path: path, slots: slots) 0274 } 0275 let child = node.children[slot.index] 0276 path.append(Weak(child)) 0277 position -= slot.position - child.count 0278 node = child 0279 } 0280 assert(position < node.elements.count) 0281 slots.append(position) 0282 return Index(path: path, slots: slots) 0283 } 0284 } 0285 0286 0287 //MARK: Editing 0288 0289 extension BTree { 0290 /// Edit the tree at a path that is to be discovered on the way down, ensuring that all nodes on the path are 0291 /// uniquely held by this tree. 0292 /// This is a simple (but not easy, alas) interface that allows implementing basic editing operations using 0293 /// recursion without adding a separate method on `BTreeNode` for each operation. 0294 /// 0295 /// Editing is split into two phases: the descent phase and the ascend phase. 0296 /// 0297 /// - During descent, the `descend` closure is called repeatedly to get the next child slot to drill down into. 0298 /// When the closure returns `nil`, the phase stops and the ascend phase begins. 0299 /// - During ascend, the `ascend` closure is called for each node for which `descend` returned non-nil, in reverse 0300 /// order. 0301 /// 0302 /// - Parameter descend: A closure that, when given a node, returns the child slot toward which the editing should 0303 /// continue descending, or `nil` if the descent should stop. The closure may set outside references to the 0304 /// node it gets, and may modify the node as it likes; however, it shouldn't modify anything in the tree outside 0305 /// the node's subtree, and it should not set outside references to the node's descendants. 0306 /// - Parameter ascend: A closure that processes a step of ascending back towards the root. It receives a parent node 0307 /// and the child slot from which this step is ascending. The closure may set outside references to the 0308 /// node it gets, and may modify the subtree as it likes; however, it shouldn't modify anything in the tree outside 0309 /// the node's subtree. 0310 internal mutating func edit
Map.swift:191 (@noescape descend descend: Node -> Int?, @noescape ascend: (Node, Int) -> Void) { 0311 makeUnique() 0312 root.edit(descend: descend, ascend: ascend) 0313 } 0314 } 0315 0316 //MARK: Insertion 0317 0318 extension BTree { 0319 /// Insert the specified element into the tree at `position`. 0320 /// 0321 /// - Requires: The key of the supplied element does not violate the b-tree's ordering requirement. 0322 /// (This is only verified in non-optimized builds.) 0323 /// - Note: When you need to perform multiple modifications on the same tree, 0324 /// `BTreeCursor` provides an alternative interface that's often more efficient. 0325 /// - Complexity: O(log(`count`)) 0326 public mutating func insert
BTree.swift:332 BTree.swift:382 BTree.swift:410 BTree.swift:446 BTree.swift:515 BTree.swift:569 (element: Element, at position: Int) { 0327 precondition(position >= 0 && position <= count) 0328 makeUnique() 0329 var pos = count - position 0330 var splinter: BTreeSplinter<Key, Payload>? = nil 0331 var element = element 0332 edit( 0333 descend: { node in 0334 let slot = node.slotOfPosition(node.count - pos) 0335 assert(slot.index == 0 || node.elements[slot.index - 1].0 <= element.0) 0336 assert(slot.index == node.elements.count || node.elements[slot.index].0 >= element.0) 0337 if !slot.match { 0338 // Continue descending. 0339 pos -= node.count - slot.position 0340 return slot.index 0341 } 0342 else if node.isLeaf { 0343 // Found the insertion point. Insert, then start ascending. 0344 node.insert(element, inSlot: slot.index) 0345 if node.isTooLarge { 0346 splinter = node.split() 0347 } 0348 return nil 0349 } 0350 else { 0351 // For internal nodes, put the new element in place of the old at the same position, 0352 // then continue descending toward the next position, inserting the old element. 0353 element = node.setElementInSlot(slot.index, to: element) 0354 pos = node.children[slot.index + 1].count 0355 return slot.index + 1 0356 } 0357 }, 0358 ascend: { node, slot in 0359 node.count += 1 0360 if let s = splinter { 0361 node.insert(s, inSlot: slot) 0362 splinter = node.isTooLarge ? node.split() : nil 0363 } 0364 } 0365 ) 0366 if let s = splinter { 0367 root = Node(left: root, separator: s.separator, right: s.node) 0368 } 0369 } 0370 0371 /// Set the payload at `position`, and return the payload originally stored there. 0372 /// 0373 /// - Requires: `position < count` 0374 /// - Note: When you need to perform multiple modifications on the same tree, 0375 /// `BTreeCursor` provides an alternative interface that's often more efficient. 0376 /// - Complexity: O(log(`count`)) 0377 public mutating func setPayloadAt
BTreeCursor.swift:806 BTreeCursor.swift:814 List.swift:260 List.swift:267 (position: Int, to payload: Payload) -> Payload { 0378 precondition(position >= 0 && position < count) 0379 makeUnique() 0380 var pos = count - position 0381 var old: Payload? = nil 0382 edit( 0383 descend: { node in 0384 let slot = node.slotOfPosition(node.count - pos) 0385 if !slot.match { 0386 // Continue descending. 0387 pos -= node.count - slot.position 0388 return slot.index 0389 } 0390 old = node.elements[slot.index].1 0391 node.elements[slot.index].1 = payload 0392 return nil 0393 }, 0394 ascend: { node, slot in 0395 } 0396 ) 0397 return old! 0398 } 0399 0400 /// Insert `element` into the tree as a new element. 0401 /// If the tree already contains elements with the same key, `selector` specifies where to put the new element. 0402 /// 0403 /// - Note: When you need to perform multiple modifications on the same tree, 0404 /// `BTreeCursor` provides an alternative interface that's often more efficient. 0405 /// - Complexity: O(log(`count`)) 0406 public mutating func insert
List.swift:77 (element: Element, at selector: BTreeKeySelector = .Any) { 0407 makeUnique() 0408 let selector = selector == .Any ? .Last : selector 0409 var splinter: BTreeSplinter<Key, Payload>? = nil 0410 edit( 0411 descend: { node in 0412 let slot = node.slotOf(element.0, choosing: selector) 0413 if !node.isLeaf { 0414 return slot.descend 0415 } 0416 node.insert(element, inSlot: slot.descend) 0417 if node.isTooLarge { 0418 splinter = node.split() 0419 } 0420 return nil 0421 }, 0422 ascend: { node, slot in 0423 node.count += 1 0424 if let s = splinter { 0425 node.insert(s, inSlot: slot) 0426 splinter = node.isTooLarge ? node.split() : nil 0427 } 0428 } 0429 ) 0430 if let s = splinter { 0431 root = Node(left: root, separator: s.separator, right: s.node) 0432 } 0433 } 0434 0435 /// Insert `element` into the tree, replacing an element with the same key if there is one. 0436 /// If the tree already contains multiple elements with the same key, `selector` specifies which one to replace. 0437 /// 0438 /// - Note: When you need to perform multiple modifications on the same tree, 0439 /// `BTreeCursor` provides an alternative interface that's often more efficient. 0440 /// - Complexity: O(log(`count`)) 0441 public mutating func insertOrReplace
BTreeCursor.swift:793 (element: Element, at selector: BTreeKeySelector = .Any) -> Payload? { 0442 makeUnique() 0443 var old: Payload? = nil 0444 var match: (node: Node, slot: Int)? = nil 0445 var splinter: BTreeSplinter<Key, Payload>? = nil 0446 edit( 0447 descend: { node in 0448 let slot = node.slotOf(element.0, choosing: selector) 0449 if node.isLeaf { 0450 if let m = slot.match { 0451 // We found the element we want to replace. 0452 old = node.setElementInSlot(m, to: element).1 0453 match = nil 0454 } 0455 else if old == nil && match == nil { 0456 // The tree contains no matching elements; insert a new one. 0457 node.insert(element, inSlot: slot.descend) 0458 if node.isTooLarge { 0459 splinter = node.split() 0460 } 0461 } 0462 return nil 0463 } 0464 if let m = slot.match { 0465 if selector == .Any { 0466 // When we don't care about which element to replace, we stop the descent at the first match. 0467 old = node.setElementInSlot(m, to: element).1 0468 return nil 0469 } 0470 // Otherwise remember this match and replace it during ascend if it's the last one. 0471 match = (node, m) 0472 } 0473 return slot.descend 0474 }, 0475 ascend: { node, slot in 0476 if let m = match { 0477 // We're looking for the node that contains the last match. 0478 if m.node === node { 0479 // Found it; replace the matching element and cancel the search. 0480 old = node.setElementInSlot(m.slot, to: element).1 0481 match = nil 0482 } 0483 } 0484 else if old == nil { 0485 // We're ascending from an insertion. 0486 node.count += 1 0487 if let s = splinter { 0488 node.insert(s, inSlot: slot) 0489 splinter = node.isTooLarge ? node.split() : nil 0490 } 0491 } 0492 } 0493 ) 0494 if let s = splinter { 0495 root = Node(left: root, separator: s.separator, right: s.node) 0496 } 0497 return old 0498 } 0499 } 0500 0501 //MARK: Removal 0502 0503 extension BTree { 0504 /// Remove and return the element at the specified position. 0505 /// 0506 /// - Note: When you need to perform multiple modifications on the same tree, 0507 /// `BTreeCursor` provides an alternative interface that's often more efficient. 0508 /// - Complexity: O(log(`count`)) 0509 public mutating func removeAt
Map.swift:201 (position: Int) -> Element { 0510 precondition(position >= 0 && position < count) 0511 makeUnique() 0512 var pos = count - position 0513 var matching: (node: Node, slot: Int)? = nil 0514 var old: Element? = nil 0515 edit( 0516 descend: { node in 0517 let slot = node.slotOfPosition(node.count - pos) 0518 if !slot.match { 0519 // No match yet; continue descending. 0520 assert(!node.isLeaf) 0521 pos -= node.count - slot.position 0522 return slot.index 0523 } 0524 else if node.isLeaf { 0525 // The position we're looking for is in a leaf node; we can remove it directly. 0526 old = node.removeSlot(slot.index) 0527 return nil 0528 } 0529 else { 0530 // When the position happens to fall into an internal node, remember the match and continue 0531 // removing the next position (which is guaranteed to be in a leaf node). 0532 // We'll replace the removed element with this one during the ascend. 0533 matching = (node, slot.index) 0534 pos = node.children[slot.index + 1].count 0535 return slot.index + 1 0536 } 0537 }, 0538 ascend: { node, slot in 0539 node.count -= 1 0540 if let m = matching where m.node === node { 0541 // We've removed the element at the next position; put it back in place of the 0542 // element we actually want to remove. 0543 old = node.setElementInSlot(m.slot, to: old!) 0544 matching = nil 0545 } 0546 if node.children[slot].isTooSmall { 0547 node.fixDeficiency(slot) 0548 } 0549 } 0550 ) 0551 if root.children.count == 1 { 0552 assert(root.elements.count == 0) 0553 root = root.children[0] 0554 } 0555 return old! 0556 } 0557 0558 /// Remove an element with the specified key, if it exists. 0559 /// If there are multiple elements with the same key, `selector` indicates which matching element to remove. 0560 /// 0561 /// - Returns: The payload of the removed element, or `nil` if there was no element with `key` in the tree. 0562 /// - Note: When you need to perform multiple modifications on the same tree, 0563 /// `BTreeCursor` provides an alternative interface that's often more efficient. 0564 /// - Complexity: O(log(`count`)) 0565 public mutating func remove
List.swift:305 List.swift:310 List.swift:322 List.swift:334 List.swift:339 (key: Key, at selector: BTreeKeySelector = .Any) -> Payload? { 0566 makeUnique() 0567 var old: Element? = nil 0568 var matching: (node: Node, slot: Int)? = nil 0569 edit( 0570 descend: { node in 0571 let slot = node.slotOf(key, choosing: selector) 0572 if node.isLeaf { 0573 if let m = slot.match { 0574 old = node.removeSlot(m) 0575 matching = nil 0576 } 0577 else if matching != nil { 0578 old = node.removeSlot(slot.descend == node.elements.count ? slot.descend - 1 : slot.descend) 0579 } 0580 return nil 0581 } 0582 if let m = slot.match { 0583 matching = (node, m) 0584 } 0585 return slot.descend 0586 }, 0587 ascend: { node, slot in 0588 if let o = old { 0589 node.count -= 1 0590 if let m = matching where m.node === node { 0591 old = node.setElementInSlot(m.slot, to: o) 0592 matching = nil 0593 } 0594 if node.children[slot].isTooSmall { 0595 node.fixDeficiency(slot) 0596 } 0597 } 0598 } 0599 ) 0600 if root.children.count == 1 { 0601 assert(root.elements.count == 0) 0602 root = root.children[0] 0603 } 0604 return old?.1 0605 } 0606 } 0607 0608 //MARK: Bulk loading 0609 0610 extension BTree { 0611 /// Create a new b-tree from elements of a sequence sorted by key. 0612 /// 0613 /// - Parameter sortedElements: A sequence of arbitrary length, sorted by key. 0614 /// - Parameter order: The desired b-tree order. If not specified (recommended), the default order is used. 0615 /// - Parameter fillFactor: The desired fill factor in each node of the new tree. Must be between 0.5 and 1.0. 0616 /// If not specified, a value of 1.0 is used, i.e., nodes will be loaded with as many elements as possible. 0617 /// - Complexity: O(count) 0618 /// - SeeAlso: `init(elements:order:fillFactor:)` for a (slower) unsorted variant. 0619 public init
Map.swift:221 <S: SequenceType where S.Generator.Element == Element>(sortedElements elements: S, order: Int = Node.defaultOrder, fillFactor: Double = 1) { 0620 precondition(order > 1) 0621 precondition(fillFactor >= 0.5 && fillFactor <= 1) 0622 let keysPerNode = Int(fillFactor * Double(order - 1) + 0.5) 0623 assert(keysPerNode >= (order - 1) / 2 && keysPerNode <= order - 1) 0624 0625 var generator = elements.generate() 0626 0627 // This bulk loading algorithm works growing a line of perfectly loaded saplings, in order of decreasing depth, 0628 // with a separator element between each of them. 0629 // In each step, a new separator and a new 0-depth, fully loaded node is loaded from the sequence as a new seedling. 0630 // The seedling is then appended to or recursively merged into the list of saplings. 0631 // Finally, at the end of the sequence, the final list of saplings plus the last partial seedling is joined 0632 // into a single tree, which becomes the root. 0633 0634 var saplings: [Node] = [] 0635 var separators: [Element] = [] 0636 0637 var lastKey: Key? = nil 0638 var seedling = Node(order: order) 0639 outer: while true { 0640 // Create new separator. 0641 if saplings.count > 0 { 0642 guard let element = generator.next() else { break outer } 0643 precondition(lastKey <= element.0) 0644 lastKey = element.0 0645 separators.append(element) 0646 } 0647 // Load new seedling. 0648 while seedling.elements.count < keysPerNode { 0649 guard let element = generator.next() else { break outer } 0650 precondition(lastKey <= element.0) 0651 lastKey = element.0 0652 seedling.elements.append(element) 0653 seedling.count += 1 0654 } 0655 // Append seedling into saplings, combining the last few seedlings when possible. 0656 while !saplings.isEmpty && seedling.elements.count == keysPerNode { 0657 let sapling = saplings.last! 0658 assert(sapling.depth >= seedling.depth) 0659 if sapling.depth == seedling.depth + 1 && sapling.elements.count < keysPerNode { 0660 // Graft current seedling under the last sapling, as a new child branch. 0661 saplings.removeLast() 0662 let separator = separators.removeLast() 0663 sapling.elements.append(separator) 0664 sapling.children.append(seedling) 0665 sapling.count += seedling.count + 1 0666 seedling = sapling 0667 } 0668 else if sapling.depth == seedling.depth && sapling.elements.count == keysPerNode { 0669 // We have two full nodes; add them as two branches of a new, deeper seedling. 0670 saplings.removeLast() 0671 let separator = separators.removeLast() 0672 seedling = Node(left: sapling, separator: separator, right: seedling) 0673 } 0674 else { 0675 break 0676 } 0677 } 0678 saplings.append(seedling) 0679 seedling = Node(order: order) 0680 } 0681 0682 // Merge saplings and seedling into a single tree. 0683 if separators.count == saplings.count - 1 { 0684 assert(seedling.count == 0) 0685 self.root = saplings.removeLast() 0686 } 0687 else { 0688 self.root = seedling 0689 } 0690 assert(separators.count == saplings.count) 0691 while !saplings.isEmpty { 0692 self.root = Node.join(left: saplings.removeLast(), separator: separators.removeLast(), right: self.root) 0693 } 0694 } 0695 0696 /// Create a new b-tree from elements of an unsorted sequence. 0697 /// 0698 /// - Parameter elements: An unsorted sequence of arbitrary length. 0699 /// - Parameter order: The desired b-tree order. If not specified (recommended), the default order is used. 0700 /// - Parameter fillFactor: The desired fill factor in each node of the new tree. Must be between 0.5 and 1.0. 0701 /// If not specified, a value of 1.0 is used, i.e., nodes will be loaded with as many elements as possible. 0702 /// - Complexity: O(count * log(`count`)) 0703 /// - SeeAlso: `init(sortedElements:order:fillFactor:)` for a (faster) variant that can be used if the sequence is already sorted. 0704 public init
BTree.swift:705 self.init(sortedElements: elements.sort { $0.0 < $1.0 }, order: order, fillFactor: fillFactor)BTreeCursor.swift:707 Map.swift:246 <S: SequenceType where S.Generator.Element == Element>(elements: S, order: Int = Node.defaultOrder, fillFactor: Double = 1) { 0705 self.init(sortedElements: elements.sort { $0.0 < $1.0 }, order: order, fillFactor: fillFactor) 0706 } 0707 } 0708
Map.swift:239 Map.swift:253