0001 // 0002 // List.swift 0003 // BTree 0004 // 0005 // Created by Károly Lőrentey on 2016-02-11. 0006 // Copyright © 2015–2016 Károly Lőrentey. 0007 // 0008 0009 /// A random-access collection of arbitrary elements. 0010 /// `List` works like an `Array`, but lookup, insertion and removal of elements at any index have 0011 /// logarithmic complexity. (`Array` has O(1) lookup, but removal/insertion at an arbitrary index costs O(count).) 0012 /// 0013 /// `List` is a struct with copy-on-write value semantics, like Swift's standard collection types. 0014 /// It uses an in-memory b-tree for element storage, whose individual nodes may be shared with other lists. 0015 /// Mutating a list whose storage is (partially or completely) shared requires copying of only O(log(`count`)) elements. 0016 /// (Thus, mutation of shared lists may be relatively cheaper than arrays, which need to copy all elements.) 0017 /// 0018 /// Lookup, insertion and removal of individual elements anywhere in a list have logarithmic complexity. 0019 /// Using the batch operations provided by `List` can often be much faster than processing individual elements 0020 /// one by one. For example, splitting a list or concatenating two lists can be done in O(log(n)) time. 0021 /// 0022 /// - Note: While `List` implements all formal requirements of `CollectionType`, it violates the semantic requirement 0023 /// that indexing has O(1) complexity: subscripting a `List` costs `O(log(`count`))`. Collection algorithms that 0024 /// rely on subscripting will have higher complexity than expected. (This does not affect algorithms that use 0025 /// generate() to iterate over elements.) 0026 /// 0027 public struct List<Element
List.swift:45 extension List: MutableCollectionType {List.swift:103 extension List {List.swift:198 public extension List where Element: Equatable {List.swift:222 extension List {List.swift:231 extension List: ArrayLiteralConvertible {List.swift:239 extension List: CustomStringConvertible {List.swift:246 extension List: CustomDebugStringConvertible {List.swift:255 extension List {List.swift:273 public mutating func appendContentsOf(list: List<Element>) {List.swift:291 public mutating func insertContentsOf(list: List<Element>, at index: Int) {List.swift:373 public func ==<Element: Equatable>(a: List<Element>, b: List<Element>) -> Bool {List.swift:373 public func ==<Element: Equatable>(a: List<Element>, b: List<Element>) -> Bool {List.swift:379 public func !=<Element: Equatable>(a: List<Element>, b: List<Element>) -> Bool {List.swift:379 public func !=<Element: Equatable>(a: List<Element>, b: List<Element>) -> Bool {> { 0028 internal typealias Tree
List.swift:28 = BTree<EmptyKey, Element> 0029 0030 /// The root node. 0031 internal private(set) var tree
List.swift:31 List.swift:35 List.swift:350 : Tree 0032 0033 /// Initialize an empty list. 0034 public init
List.swift:35 List.swift:56 List.swift:61 List.swift:66 List.swift:74 List.swift:77 List.swift:84 List.swift:108 try tree.forEach { try body($0.1) }List.swift:187 try self.tree.forEach { element -> Bool inList.swift:204 self.tree.forEach { e -> Bool inList.swift:260 List.swift:260 List.swift:267 List.swift:274 tree.withCursorAtPosition(tree.count) { cursor inList.swift:274 tree.withCursorAtPosition(tree.count) { cursor inList.swift:275 List.swift:283 tree.withCursorAtPosition(tree.count) { cursor inList.swift:283 tree.withCursorAtPosition(tree.count) { cursor inList.swift:292 tree.withCursorAtPosition(index) { cursor inList.swift:293 List.swift:298 tree.withCursorAtPosition(index) { cursor inList.swift:305 List.swift:310 List.swift:315 tree.withCursorAtPosition(0) { cursor inList.swift:322 List.swift:327 tree.withCursorAtPosition(count - n) { cursor inList.swift:334 List.swift:339 List.swift:344 tree.withCursorAtPosition(range.startIndex) { cursor inList.swift:350 List.swift:355 tree.withCursorAtPosition(range.startIndex) { cursor in() { 0035 self.tree = Tree() 0036 } 0037 } 0038 0039 internal struct EmptyKey
List.swift:224 : Comparable { } 0040 internal func ==(a: EmptyKey, b: EmptyKey) -> Bool { return true } 0041 internal func <(a: EmptyKey, b: EmptyKey) -> Bool { return false } 0042 0043 //MARK: CollectionType 0044 0045 extension List: MutableCollectionType { 0046 public typealias Index
List.swift:28 List.swift:40 internal func ==(a: EmptyKey, b: EmptyKey) -> Bool { return true }List.swift:40 internal func ==(a: EmptyKey, b: EmptyKey) -> Bool { return true }List.swift:41 internal func <(a: EmptyKey, b: EmptyKey) -> Bool { return false }List.swift:41 internal func <(a: EmptyKey, b: EmptyKey) -> Bool { return false }List.swift:89 List.swift:260 List.swift:267 List.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) })= Int 0047 public typealias Generator
List.swift:185 public func indexOf(@noescape predicate: (Element) throws -> Bool) rethrows -> Index? {List.swift:202 public func indexOf(element: Element) -> Index? {= ListGenerator<Element> 0048 0049 /// Always zero, which is the index of the first element when non-empty. 0050 public var startIndex: Int { 0051 return 0 0052 } 0053 0054 /// The "past-the-end" element index; the successor of the last valid subscript argument. 0055 public var endIndex: Int { 0056 return tree.count 0057 } 0058 0059 /// The number of elements in this list. 0060 public var count
List.swift:83 public func generate() -> Generator {: Int { 0061 return tree.count 0062 } 0063 0064 /// True iff this list has no elements. 0065 public var isEmpty: Bool { 0066 return tree.count == 0 0067 } 0068 0069 /// Get or set the element at the given index. 0070 /// 0071 /// - Complexity: O(log(`count`)) 0072 public subscript(index: Int) -> Element { 0073 get { 0074 return tree.elementAtPosition(index).1 0075 } 0076 set { 0077 tree.setPayloadAt(index, to: newValue) 0078 } 0079 } 0080 0081 /// Return a generator over all elements in this list. 0082 @warn_unused_result 0083 public func generate() -> Generator { 0084 return ListGenerator(tree.generate()) 0085 } 0086 } 0087 0088 public struct ListGenerator
List.swift:118 List.swift:194 List.swift:211 List.swift:304 List.swift:309 List.swift:314 List.swift:321 List.swift:322 List.swift:326 List.swift:327 tree.withCursorAtPosition(count - n) { cursor inList.swift:333 guard count > 0 else { return nil }List.swift:334 List.swift:338 guard count > 0 else { return nil }List.swift:343 List.swift:354 List.swift:374 guard a.count == b.count else { return false }List.swift:374 guard a.count == b.count else { return false }<Element
List.swift:47 List.swift:84 >: GeneratorType { 0089 internal typealias Base
List.swift:89 List.swift:96 public mutating func next() -> Element? {= BTreeGenerator<EmptyKey, Element> 0090 private var base
List.swift:90 List.swift:92 private init(_ base: Base) {: Base 0091 0092 private init
List.swift:93 List.swift:97 (_ base: Base) { 0093 self.base = base 0094 } 0095 0096 public mutating func next() -> Element? { 0097 return base.next()?.1 0098 } 0099 } 0100 0101 // MARK: Algorithms 0102 0103 extension List { 0104 /// Call `body` on each element in `self` in ascending key order. 0105 /// 0106 /// - Complexity: O(`count`) 0107 public func forEach
List.swift:84 (@noescape body: (Element) throws -> ()) rethrows { 0108 try tree.forEach { try body($0.1) } 0109 } 0110 0111 /// Return an `Array` containing the results of mapping `transform` over all elements in `self`. 0112 /// The elements are transformed in ascending key order. 0113 /// 0114 /// - Complexity: O(`count`) 0115 @warn_unused_result 0116 public func map
List.swift:119 try self.forEach {List.swift:131 try self.forEach { element inList.swift:143 try self.forEach { element inList.swift:161 try self.forEach {List.swift:173 try self.forEach {<T>(@noescape transform: (Element) throws -> T) rethrows -> [T] { 0117 var result: [T] = [] 0118 result.reserveCapacity(self.count) 0119 try self.forEach { 0120 result.append(try transform($0)) 0121 } 0122 return result 0123 } 0124 0125 /// Return an `Array` containing the concatenated results of mapping `transform` over `self`. 0126 /// 0127 /// - Complexity: O(`result.count`) 0128 @warn_unused_result 0129 public func flatMap<S: SequenceType>(transform: (Element) throws -> S) rethrows -> [S.Generator.Element] { 0130 var result: [S.Generator.Element] = [] 0131 try self.forEach { element in 0132 result.appendContentsOf(try transform(element)) 0133 } 0134 return result 0135 } 0136 0137 /// Return an `Array` containing the non-`nil` results of mapping `transform` over `self`. 0138 /// 0139 /// - Complexity: O(`count`) 0140 @warn_unused_result 0141 public func flatMap<T>(@noescape transform: (Element) throws -> T?) rethrows -> [T] { 0142 var result: [T] = [] 0143 try self.forEach { element in 0144 if let t = try transform(element) { 0145 result.append(t) 0146 } 0147 } 0148 return result 0149 } 0150 0151 /// Calculate the left fold of this list over `combine`: 0152 /// return the result of repeatedly calling `combine` with an accumulated value initialized to `initial` 0153 /// and each element of `self`, in turn. 0154 /// 0155 /// I.e., return `combine(combine(...combine(combine(initial, self[0]), self[1]),...self[count-2]), self[count-1])`. 0156 /// 0157 /// - Complexity: O(`count`) 0158 @warn_unused_result 0159 public func reduce<T>(initial: T, @noescape combine: (T, Element) throws -> T) rethrows -> T { 0160 var result = initial 0161 try self.forEach { 0162 result = try combine(result, $0) 0163 } 0164 return result 0165 } 0166 0167 /// Return an `Array` containing the non-`nil` results of mapping `transform` over `self`. 0168 /// 0169 /// - Complexity: O(`count`) 0170 @warn_unused_result 0171 public func filter(@noescape includeElement: (Element) throws -> Bool) rethrows -> [Element] { 0172 var result: [Element] = [] 0173 try self.forEach { 0174 if try includeElement($0) { 0175 result.append($0) 0176 } 0177 } 0178 return result 0179 } 0180 0181 /// Returns the first index where `predicate` returns `true` for the corresponding value, or `nil` if 0182 /// such value is not found. 0183 /// 0184 /// - Complexity: O(`count`) 0185 public func indexOf(@noescape predicate: (Element) throws -> Bool) rethrows -> Index? { 0186 var i = 0 0187 try self.tree.forEach { element -> Bool in 0188 if try predicate(element.1) { 0189 return false 0190 } 0191 i += 1 0192 return true 0193 } 0194 return i < count ? i : nil 0195 } 0196 } 0197 0198 public extension List where Element: Equatable { 0199 /// Returns the first index where the given element appears in `self` or `nil` if the element is not found. 0200 /// 0201 /// - Complexity: O(`count`) 0202 public func indexOf
List.swift:241 let contents = self.map { element in String(reflecting: element) }List.swift:248 let contents = self.map { element in String(reflecting: element) }(element: Element) -> Index? { 0203 var i = 0 0204 self.tree.forEach { e -> Bool in 0205 if element == e.1 { 0206 return false 0207 } 0208 i += 1 0209 return true 0210 } 0211 return i < count ? i : nil 0212 } 0213 0214 /// Return true iff `element` is in `self`. 0215 public func contains(element: Element) -> Bool { 0216 return indexOf(element) != nil 0217 } 0218 } 0219 0220 //MARK: Initializers 0221 0222 extension List { 0223 public init
List.swift:216 <S: SequenceType where S.Generator.Element == Element>(_ elements: S) { 0224 self.init() 0225 self.appendContentsOf(elements) 0226 } 0227 } 0228 0229 //MARK: Literal conversion 0230 0231 extension List: ArrayLiteralConvertible { 0232 public init(arrayLiteral elements: Element...) { 0233 self.init(elements) 0234 } 0235 } 0236 0237 //MARK: String conversion 0238 0239 extension List: CustomStringConvertible { 0240 public var description: String { 0241 let contents = self.map { element in String(reflecting: element) } 0242 return "[" + contents.joinWithSeparator(", ") + "]" 0243 } 0244 } 0245 0246 extension List: CustomDebugStringConvertible { 0247 public var debugDescription: String { 0248 let contents = self.map { element in String(reflecting: element) } 0249 return "[" + contents.joinWithSeparator(", ") + "]" 0250 } 0251 } 0252 0253 //MARK: Insertion 0254 0255 extension List { 0256 /// Append `element` to the end of this list. 0257 /// 0258 /// - Complexity: O(log(`count`)) 0259 public mutating func append(element: Element) { 0260 tree.insert((EmptyKey(), element), at: tree.count) 0261 } 0262 0263 /// Insert `element` into this list at `index`. 0264 /// 0265 /// - Complexity: O(log(`count`)) 0266 public mutating func insert(element: Element, atIndex index: Int) { 0267 tree.insert((EmptyKey(), element), at: index) 0268 } 0269 0270 /// Append `list` to the end of this list. 0271 /// 0272 /// - Complexity: O(log(`self.count + list.count`)) 0273 public mutating func appendContentsOf(list: List<Element>) { 0274 tree.withCursorAtPosition(tree.count) { cursor in 0275 cursor.insert(list.tree) 0276 } 0277 } 0278 0279 /// Append the contents of `elements` to the end of this list. 0280 /// 0281 /// - Complexity: O(log(`count`) + *n*) where *n* is the number of elements in the sequence. 0282 public mutating func appendContentsOf
List.swift:233 <S: SequenceType where S.Generator.Element == Element>(elements: S) { 0283 tree.withCursorAtPosition(tree.count) { cursor in 0284 cursor.insert(elements.lazy.map { (EmptyKey(), $0) }) 0285 } 0286 } 0287 0288 /// Insert the contents of `list` in this list at `index`. 0289 /// 0290 /// - Complexity: O(log(`self.count + list.count`)) 0291 public mutating func insertContentsOf(list: List<Element>, at index: Int) { 0292 tree.withCursorAtPosition(index) { cursor in 0293 cursor.insert(list.tree) 0294 } 0295 } 0296 0297 public mutating func insertContentsOf<S: SequenceType where S.Generator.Element == Element>(elements: S, at index: Int) { 0298 tree.withCursorAtPosition(index) { cursor in 0299 cursor.insert(elements.lazy.map { (EmptyKey(), $0) }) 0300 } 0301 } 0302 0303 public mutating func removeAtIndex(index: Int) -> Element { 0304 precondition(index >= 0 && index < count) 0305 return tree.removeAt(index).1 0306 } 0307 0308 public mutating func removeFirst() -> Element { 0309 precondition(count > 0) 0310 return tree.removeAt(0).1 0311 } 0312 0313 public mutating func removeFirst(n: Int) { 0314 precondition(n <= count) 0315 tree.withCursorAtPosition(0) { cursor in 0316 cursor.remove(n) 0317 } 0318 } 0319 0320 public mutating func removeLast() -> Element { 0321 precondition(count > 0) 0322 return tree.removeAt(count - 1).1 0323 } 0324 0325 public mutating func removeLast(n: Int) { 0326 precondition(n <= count) 0327 tree.withCursorAtPosition(count - n) { cursor in 0328 cursor.remove(n) 0329 } 0330 } 0331 0332 public mutating func popLast() -> Element? { 0333 guard count > 0 else { return nil } 0334 return tree.removeAt(count - 1).1 0335 } 0336 0337 public mutating func popFirst() -> Element? { 0338 guard count > 0 else { return nil } 0339 return tree.removeAt(0).1 0340 } 0341 0342 public mutating func removeRange(range: Range<Int>) { 0343 precondition(range.startIndex >= 0 && range.endIndex <= count) 0344 tree.withCursorAtPosition(range.startIndex) { cursor in 0345 cursor.remove(range.count) 0346 } 0347 } 0348 0349 public mutating func removeAll() { 0350 tree = Tree() 0351 } 0352 0353 public mutating func replaceRange<C: CollectionType where C.Generator.Element == Element>(range: Range<Int>, with elements: C) { 0354 precondition(range.startIndex >= 0 && range.endIndex <= count) 0355 tree.withCursorAtPosition(range.startIndex) { cursor in 0356 var generator = Optional(elements.generate()) 0357 while cursor.position < range.endIndex { 0358 guard let element = generator!.next() else { generator = nil; break } 0359 cursor.payload = element 0360 cursor.moveForward() 0361 } 0362 if cursor.position < range.endIndex { 0363 cursor.remove(range.endIndex - cursor.position) 0364 } 0365 else { 0366 cursor.insert(GeneratorSequence(generator!).lazy.map { (EmptyKey(), $0) }) 0367 } 0368 } 0369 } 0370 } 0371 0372 @warn_unused_result 0373 public func ==<Element: Equatable>(a: List<Element>, b: List<Element>) -> Bool { 0374 guard a.count == b.count else { return false } 0375 return a.elementsEqual(b) 0376 } 0377 0378 @warn_unused_result 0379 public func !=<Element: Equatable>(a: List<Element>, b: List<Element>) -> Bool { 0380 return !(a == b) 0381 } 0382 0383
List.swift:225