0001 // 0002 // Map.swift 0003 // BTree 0004 // 0005 // Created by Károly Lőrentey on 2015-12-17. 0006 // Copyright © 2015–2016 Károly Lőrentey. 0007 // 0008 0009 import Foundation 0010 0011 /// An ordered mapping from comparable keys to arbitrary values. 0012 /// Works like `Dictionary`, but provides a well-defined ordering for its elements. 0013 /// 0014 /// `Map` is a struct with copy-on-write value semantics, like Swift's standard collection types. 0015 /// It uses an in-memory b-tree for element storage, whose individual nodes may be shared with other maps. 0016 /// Modifying an element of a map whose storage is (partially or completely) shared requires copying of 0017 /// only O(log(`count`)) elements. (Thus, mutation of shared maps may be relatively cheaper than dictionaries, 0018 /// which need to clone all elements.) 0019 /// 0020 /// Lookup, insertion and removal of individual key-value pairs in a map have logarithmic complexity. 0021 /// This is in contrast to `Dictionary`'s best-case O(1) (worst-case O(n)) implementations for the same operations. 0022 /// To make up for being typically slower, `Map` always keeps its elements in a well-defined order. 0023 /// 0024 /// While independently looking up individual elements takes O(log(n)) time, batch operations on lots of elements 0025 /// often complete faster than you might expect. 0026 /// For example, iterating over a `Map` using the generator API requires O(n) time, just like a dictionary. 0027 /// 0028 /// Due to its tree-based structure, `Map` is able to provide efficient implementations for several operations 0029 /// that would be slower with dictionaries. 0030 /// 0031 public struct Map<Key
Map.swift:46 extension Map: CollectionType {Map.swift:90 extension Map {Map.swift:157 extension Map {Map.swift:160 public var keys: LazyMapCollection<Map<Key, Value>, Key> {Map.swift:165 public var values: LazyMapCollection<Map<Key, Value>, Value> {Map.swift:234 extension Map {Map.swift:250 extension Map: DictionaryLiteralConvertible {Map.swift:257 extension Map: CustomStringConvertible {Map.swift:269 extension Map: CustomDebugStringConvertible {Map.swift:282 public func ==<Key: Comparable, Value: Equatable>(a: Map<Key, Value>, b: Map<Key, Value>) -> Bool {Map.swift:282 public func ==<Key: Comparable, Value: Equatable>(a: Map<Key, Value>, b: Map<Key, Value>) -> Bool {Map.swift:288 public func !=<Key: Comparable, Value: Equatable>(a: Map<Key, Value>, b: Map<Key, Value>) -> Bool {Map.swift:288 public func !=<Key: Comparable, Value: Equatable>(a: Map<Key, Value>, b: Map<Key, Value>) -> Bool {: Comparable, Value
Map.swift:33 > { 0032 // Typealiases 0033 internal typealias Tree
Map.swift:33 = BTree<Key, Value> 0034 0035 /// The root node. 0036 internal private(set) var tree
Map.swift:36 Map.swift:40 Map.swift:230 Map.swift:239 Map.swift:246 Map.swift:253 : Tree 0037 0038 /// Initialize an empty map. 0039 public init() { 0040 self.tree = Tree() 0041 } 0042 } 0043 0044 //MARK: CollectionType 0045 0046 extension Map: CollectionType { 0047 public typealias Index
Map.swift:40 Map.swift:53 Map.swift:58 Map.swift:65 Map.swift:78 Map.swift:84 Map.swift:95 Map.swift:174 Map.swift:191 Map.swift:201 Map.swift:221 Map.swift:230 Map.swift:239 Map.swift:246 Map.swift:253 = BTreeIndex<Key, Value> 0048 public typealias Generator
Map.swift:52 public var startIndex: Index {Map.swift:57 public var endIndex: Index {Map.swift:190 public func indexForKey(key: Key) -> Index? {Map.swift:209 public mutating func removeAtIndex(index: Index) -> (Key, Value) {= BTreeGenerator<Key, Value> 0049 public typealias Element
Map.swift:83 public func generate() -> Generator {= (Key, Value) 0050 0051 /// The index of the first element when non-empty. Otherwise the same as `endIndex`. 0052 public var startIndex: Index { 0053 return tree.startIndex 0054 } 0055 0056 /// The "past-the-end" element index; the successor of the last valid subscript argument. 0057 public var endIndex: Index { 0058 return tree.endIndex 0059 } 0060 0061 /// The number of (key, value) pairs in this map. 0062 /// 0063 /// - Complexity: O(1) 0064 public var count
Map.swift:94 public func forEach(@noescape body: (Element) throws -> ()) rethrows {Map.swift:103 public func map<T>(@noescape transform: (Element) throws -> T) rethrows -> [T] {Map.swift:116 public func flatMap<S: SequenceType>(transform: (Element) throws -> S) rethrows -> [S.Generator.Element] {Map.swift:128 public func flatMap<T>(@noescape transform: (Element) throws -> T?) rethrows -> [T] {Map.swift:146 public func reduce<T>(initial: T, @noescape combine: (T, Element) throws -> T) rethrows -> T {Map.swift:238 public init<S: SequenceType where S.Generator.Element == Element>(elements: S) {Map.swift:245 public init<S: SequenceType where S.Generator.Element == Element>(sortedElements elements: S) {: Int { 0065 return tree.count 0066 } 0067 0068 /// True iff this collection has no elements. 0069 public var isEmpty: Bool { 0070 return count == 0 0071 } 0072 0073 /// Returns the (key, value) pair at the given index. 0074 /// 0075 /// - Requires: `index` originated from an unmutated copy of this map. 0076 /// - Complexity: O(1) 0077 public subscript
Map.swift:70 Map.swift:105 Map.swift:283 guard a.count == b.count else { return false }Map.swift:283 guard a.count == b.count else { return false }(index: Index) -> Element { 0078 return tree[index] 0079 } 0080 0081 /// Return a generator over all (key, value) pairs in this map, in ascending key order. 0082 @warn_unused_result 0083 public func generate() -> Generator { 0084 return tree.generate() 0085 } 0086 } 0087 0088 //MARK: Algorithms 0089 0090 extension Map { 0091 /// Call `body` on each element in `self` in ascending key order. 0092 /// 0093 /// - Complexity: O(`count`) 0094 public func forEach
Map.swift:210 (@noescape body: (Element) throws -> ()) rethrows { 0095 try tree.forEach(body) 0096 } 0097 0098 /// Return an `Array` containing the results of mapping `transform` over all elements in `self`. 0099 /// The elements are transformed in ascending key order. 0100 /// 0101 /// - Complexity: O(`count`) 0102 @warn_unused_result 0103 public func map
Map.swift:106 try self.forEach {Map.swift:118 try self.forEach { element inMap.swift:130 try self.forEach { element inMap.swift:148 try self.forEach {<T>(@noescape transform: (Element) throws -> T) rethrows -> [T] { 0104 var result: [T] = [] 0105 result.reserveCapacity(self.count) 0106 try self.forEach { 0107 result.append(try transform($0)) 0108 } 0109 return result 0110 } 0111 0112 /// Return an `Array` containing the concatenated results of mapping `transform` over `self`. 0113 /// 0114 /// - Complexity: O(`count`) 0115 @warn_unused_result 0116 public func flatMap<S: SequenceType>(transform: (Element) throws -> S) rethrows -> [S.Generator.Element] { 0117 var result: [S.Generator.Element] = [] 0118 try self.forEach { element in 0119 result.appendContentsOf(try transform(element)) 0120 } 0121 return result 0122 } 0123 0124 /// Return an `Array` containing the non-`nil` results of mapping `transform` over `self`. 0125 /// 0126 /// - Complexity: O(`count`) 0127 @warn_unused_result 0128 public func flatMap<T>(@noescape transform: (Element) throws -> T?) rethrows -> [T] { 0129 var result: [T] = [] 0130 try self.forEach { element in 0131 if let t = try transform(element) { 0132 result.append(t) 0133 } 0134 } 0135 return result 0136 } 0137 0138 /// Calculate the left fold of this map over `combine`: 0139 /// return the result of repeatedly calling `combine` with an accumulated value initialized to `initial` 0140 /// and each element of `self`, in turn. 0141 /// 0142 /// I.e., return `combine(combine(...combine(combine(initial, self[0]), self[1]),...self[count-2]), self[count-1])`. 0143 /// 0144 /// - Complexity: O(`count`) 0145 @warn_unused_result 0146 public func reduce<T>(initial: T, @noescape combine: (T, Element) throws -> T) rethrows -> T { 0147 var result = initial 0148 try self.forEach { 0149 result = try combine(result, $0) 0150 } 0151 return result 0152 } 0153 } 0154 0155 //MARK: Dictionary-like methods 0156 0157 extension Map { 0158 0159 /// A collection containing just the keys in this map, in ascending order. 0160 public var keys: LazyMapCollection<Map<Key, Value>, Key> { 0161 return self.lazy.map { $0.0 } 0162 } 0163 0164 /// A collection containing just the values in this map, in order of ascending keys. 0165 public var values: LazyMapCollection<Map<Key, Value>, Value> { 0166 return self.lazy.map { $0.1 } 0167 } 0168 0169 /// Provides access to the value for a given key. Nonexistent values are represented as `nil`. 0170 /// 0171 /// - Complexity: O(log(`count`)) 0172 public subscript(key: Key) -> Value? { 0173 get { 0174 return tree.payloadOf(key) 0175 } 0176 set(value) { 0177 if let value = value { 0178 updateValue(value, forKey: key) 0179 } 0180 else { 0181 removeValueForKey(key) 0182 } 0183 } 0184 } 0185 0186 /// Returns the index for the given key, or `nil` if the key is not present in this map. 0187 /// 0188 /// - Complexity: O(log(`count`)) 0189 @warn_unused_result 0190 public func indexForKey(key: Key) -> Index? { 0191 return tree.indexOf(key) 0192 } 0193 0194 /// Update the value stored in the map for the given key, or, if they key does not exist, add a new key-value pair to the map. 0195 /// Returns the value that was replaced, or `nil` if a new key-value pair was added. 0196 /// 0197 /// This method invalidates all existing indexes into `self`. 0198 /// 0199 /// - Complexity: O(log(`count`)) 0200 public mutating func updateValue
Map.swift:260 let contents = self.map { (key, value) -> String inMap.swift:272 let contents = self.map { (key, value) -> String in(value: Value, forKey key: Key) -> Value? { 0201 return tree.insertOrReplace((key, value)) 0202 } 0203 0204 /// Remove the key-value pair at `index` from this map. 0205 /// 0206 /// This method invalidates all existing indexes into `self`. 0207 /// 0208 /// - Complexity: O(log(`count`)) 0209 public mutating func removeAtIndex(index: Index) -> (Key, Value) { 0210 let key = self[index].0 0211 return (key, self.removeValueForKey(key)!) 0212 } 0213 0214 /// Remove a given key and the associated value from this map. 0215 /// Returns the value that was removed, or `nil` if the key was not present in the map. 0216 /// 0217 /// This method invalidates all existing indexes into `self`. 0218 /// 0219 /// - Complexity: O(log(`count`)) 0220 public mutating func removeValueForKey
Map.swift:178 (key: Key) -> Value? { 0221 return tree.remove(key) 0222 } 0223 0224 /// Remove all elements from this map. 0225 /// 0226 /// This method invalidates all existing indexes into `self`. 0227 /// 0228 /// - Complexity: O(`count`) 0229 public mutating func removeAll() { 0230 tree = Tree() 0231 } 0232 } 0233 0234 extension Map { 0235 /// Initialize a new map from an unsorted sequence of elements. 0236 /// 0237 /// - Complexity: O(*n* * log(*n*)) where *n* is the number of items in `elements`. 0238 public init<S: SequenceType where S.Generator.Element == Element>(elements: S) { 0239 self.tree = Tree(elements: elements) 0240 } 0241 0242 /// Initialize a new map from a sorted sequence of elements. 0243 /// 0244 /// - Complexity: O(*n*) where *n* is the number of items in `elements`. 0245 public init<S: SequenceType where S.Generator.Element == Element>(sortedElements elements: S) { 0246 self.tree = Tree(sortedElements: elements) 0247 } 0248 } 0249 0250 extension Map: DictionaryLiteralConvertible { 0251 /// Initialize a new map from the given elements. 0252 public init(dictionaryLiteral elements: (Key, Value)...) { 0253 self.tree = Tree(elements: elements) 0254 } 0255 } 0256 0257 extension Map: CustomStringConvertible { 0258 /// A textual representation of this map. 0259 public var description: String { 0260 let contents = self.map { (key, value) -> String in 0261 let ks = String(reflecting: key) 0262 let vs = String(reflecting: value) 0263 return "\(ks): \(vs)" 0264 } 0265 return "[" + contents.joinWithSeparator(", ") + "]" 0266 } 0267 } 0268 0269 extension Map: CustomDebugStringConvertible { 0270 /// A textual representation of this map, suitable for debugging. 0271 public var debugDescription: String { 0272 let contents = self.map { (key, value) -> String in 0273 let ks = String(reflecting: key) 0274 let vs = String(reflecting: value) 0275 return "\(ks): \(vs)" 0276 } 0277 return "[" + contents.joinWithSeparator(", ") + "]" 0278 } 0279 } 0280 0281 @warn_unused_result 0282 public func ==<Key: Comparable, Value: Equatable>(a: Map<Key, Value>, b: Map<Key, Value>) -> Bool { 0283 guard a.count == b.count else { return false } 0284 return a.elementsEqual(b, isEquivalent: { ae, be in ae.0 == be.0 && ae.1 == be.1 }) 0285 } 0286 0287 @warn_unused_result 0288 public func !=<Key: Comparable, Value: Equatable>(a: Map<Key, Value>, b: Map<Key, Value>) -> Bool { 0289 return !(a == b) 0290 } 0291
Map.swift:181 Map.swift:211