TRAVIS_OS_NAME=osx <<<<<< ENV LICENSE Makefile Package.swift Sources/OrderedDictionary/OrderedDictionary.swift Tests/LinuxMain.swift Tests/OrderedDictionaryTests/IndexingTests.swift Tests/OrderedDictionaryTests/OrderedKeysTests.swift Tests/OrderedDictionaryTests/XCTestManifests.swift <<<<<< network # path=OrderedDictionary.framework.coverage.txt 1| |import Foundation 2| |import Dispatch 3| | 4| |private let queue = DispatchQueue(label: "OrderedDictionarySerialQueue") 5| | 6| |/// OrderedDictionary is a thread-safe data structure that preserves 7| |/// key insertion order. 8| |/// 9| |/// Similar to Dictionary, values can be set/read/cleared using subscripting. 10| |/// 11| |/// var dict = OrderedDictionary() 12| |/// dict["key"] = "value" // set 13| |/// dict["key"] // get 14| |/// dict["key"] = nil // remove 15| |/// 16| |/// Both keys and values can be read in-order of insertion. Conformance to 17| |/// `Sequence` protocol allows for easy iteration over keys and values. 18| |public struct OrderedDictionary { 19| | 20| | var store: [Key: Value] = [:] 21| | var indices: [Key: Int] = [:] 22| | var nextIndex = 0 23| | 24| | /// Initialize an empty ordered dictionary. 25| 64| public init() {} 26| | 27| | /// Determine if the dictionary contains any elements 28| | /// - complexity: O(1) 29| 3| public var isEmpty: Bool { 30| 3| return store.isEmpty 31| 3| } 32| | 33| | /// Determine the number of elements contained by the dictionary 34| | /// - complexity: O(1) 35| 20.0k| public var count: Int { 36| 20.0k| return store.count 37| 20.0k| } 38| | 39| | /// Get or set a value using subscripting. 40| | /// 41| | /// var dict = OrderedDictionary() 42| | /// dict["key"] = "value" // set 43| | /// dict["key"] // get 44| | /// dict["key"] = nil // remove 45| | /// 46| | /// - Parameter key: key to retrieve the value. 47| | public subscript(key: Key) -> Value? { 48| 60.0k| get { 49| 60.0k| return getValue(forKey: key) 50| 60.0k| } 51| 90.0k| set { 52| 90.0k| if let value = newValue { 53| 70.0k| set(value: value, forKey: key) 54| 90.0k| } else { 55| 20.0k| remove(key: key) 56| 90.0k| } 57| 90.0k| } 58| | } 59| | 60| | /// Retrieve a value from the dictionary under the given key. 61| | /// 62| | /// - Parameter key: Key to be used to retrieve the value. 63| | /// - Returns: Value if the dictionary contained that key. 64| 60.0k| func getValue(forKey key: Key) -> Value? { 65| 60.0k| var value: Value? 66| 60.0k| queue.sync { 67| 60.0k| value = store[key] 68| 60.0k| } 69| 60.0k| return value 70| 60.0k| } 71| | 72| | /// Store a value in the dictionary under the given key. 73| | /// 74| | /// - Parameters: 75| | /// - value: Value to be stored. 76| | /// - key: Key to be used to retrieve the value. 77| | /// - Complexity: O(n) 78| 70.0k| mutating func set(value: Value, forKey key: Key) { 79| 70.0k| queue.sync { 80| 70.0k| if let _ = indices[key] { 81| 10.0k| // Already in dictionary, keep current index 82| 70.0k| } else { 83| 60.0k| indices[key] = nextIndex 84| 60.0k| nextIndex += 1 85| 70.0k| } 86| 70.0k| store[key] = value 87| 70.0k| } 88| 70.0k| } 89| | 90| | /// Remove an element stored in the dictionary under the given key. 91| | /// 92| | /// - Parameter key: Key where the element is stored under. 93| 20.0k| mutating func remove(key: Key) { 94| 20.0k| queue.sync { 95| 20.0k| indices[key] = nil 96| 20.0k| store[key] = nil 97| 20.0k| reindex() 98| 20.0k| } 99| 20.0k| } 100| | 101| 20.0k| private mutating func reindex() { 102| 20.0k| guard nextIndex - count > reindexThreshold else { 103| 20.0k| return 104| 20.0k| } 105| 0| 106| 0| for (offset, index) in orderedIndices.enumerated() { 107| 0| indices[index.key] = offset 108| 0| } 109| 0| nextIndex = count 110| 0| } 111| | 112| | private let reindexThreshold = 1024 * 1024 113| |} 114| | 115| |extension OrderedDictionary { 116| | 117| 64| private var orderedIndices: [(key: Key, value: Int)] { 118| 455k| return indices.sorted(by: { $0.value < $1.value }) 119| 64| } 120| | 121| | /// Collection of keys sorted by insertion order. 122| 62| public var orderedKeys: [Key] { 123| 62| var keys: [Key] = [] 124| 62| queue.sync { 125| 40.0k| keys = orderedIndices.map { $0.key } 126| 62| } 127| 62| return keys 128| 62| } 129| | 130| | /// Collection of keys sorted by insertion order. 131| 2| public var orderedValues: [Value] { 132| 4| return orderedKeyValuePairs.map { $0.value } 133| 2| } 134| | 135| | /// Collection of key/value pairs sorted by insertion order. 136| 2| public var orderedKeyValuePairs: [(key: Key, value: Value)] { 137| 2| var result: [(key: Key, value: Value)] = [] 138| 2| queue.sync { 139| 4| result = orderedIndices.compactMap { (key, _) in 140| 4| let value = store[key] 141| 4| return value.flatMap { (key: key, value: $0) } 142| 4| } 143| 2| } 144| 2| return result 145| 2| } 146| | 147| |} <<<<<< EOF # path=OrderedDictionaryTests.xctest.coverage.txt /Users/travis/build/eneko/OrderedDictionary/Tests/OrderedDictionaryTests/IndexingTests.swift: 1| |import XCTest 2| |import OrderedDictionary 3| | 4| |class IndexingTests: XCTestCase { 5| | 6| 1| func testIsEmpty() { 7| 1| var dict = OrderedDictionary() 8| 1| XCTAssertTrue(dict.isEmpty) 9| 1| dict["foo"] = "FOO" 10| 1| XCTAssertFalse(dict.isEmpty) 11| 1| dict["foo"] = nil 12| 1| XCTAssertTrue(dict.isEmpty) 13| 1| } 14| | 15| 1| func testCount() { 16| 1| var dict = OrderedDictionary() 17| 1| XCTAssertEqual(dict.count, 0) 18| 1| dict["foo"] = "FOO" 19| 1| XCTAssertEqual(dict.count, 1) 20| 1| dict["foo"] = nil 21| 1| XCTAssertEqual(dict.count, 0) 22| 1| } 23| | 24| 1| func testGetter() { 25| 1| var dict = OrderedDictionary() 26| 1| dict["foo"] = "FOO" 27| 1| dict["bar"] = "BAR" 28| 1| dict["baz"] = nil 29| 1| XCTAssertEqual(dict["foo"], "FOO") 30| 1| XCTAssertEqual(dict["bar"], "BAR") 31| 1| XCTAssertNil(dict["baz"]) 32| 1| } 33| | 34| 1| func testOrderConsistency() { 35| 1| var dict = OrderedDictionary() 36| 1| dict["foo"] = "FOO" 37| 1| dict["bar"] = "BAR" 38| 1| dict["bar"] = nil 39| 1| dict["baz"] = "BAZ" 40| 1| dict["foo"] = "JAX" 41| 1| XCTAssertEqual(dict.orderedKeys, ["foo", "baz"]) 42| 1| XCTAssertEqual(dict.orderedValues, ["JAX", "BAZ"]) 43| 1| dict["foo"] = nil 44| 1| dict["foo"] = "FOO" 45| 1| XCTAssertEqual(dict.orderedKeys, ["baz", "foo"]) 46| 1| XCTAssertEqual(dict.orderedValues, ["BAZ", "FOO"]) 47| 1| } 48| | 49| | static var allTests = [ 50| | ("testCount", testCount), 51| | ("testIsEmpty", testIsEmpty), 52| | ("testGetter", testGetter), 53| | ("testOrderConsistency", testOrderConsistency) 54| | ] 55| |} /Users/travis/build/eneko/OrderedDictionary/Tests/OrderedDictionaryTests/OrderedKeysTests.swift: 1| |import XCTest 2| |import OrderedDictionary 3| | 4| |final class OrderedKeysTests: XCTestCase { 5| | 6| 6.00k| let sourceData = (1...1_000).map { _ in (key: UUID().uuidString, value: UUID().uuidString) } ------------------ | _T022OrderedDictionaryTests0a4KeysC0C10sourceDataSaySS3key_SS5valuetGvpfiSSAE_SSAFtSicfU_: | 6| 6.00k| let sourceData = (1...1_000).map { _ in (key: UUID().uuidString, value: UUID().uuidString) } ------------------ | Unexecuted instantiation: _T022OrderedDictionaryTests0a4KeysC0CACSo12NSInvocationCSg10invocation_tcfC ------------------ | Unexecuted instantiation: _T022OrderedDictionaryTests0a4KeysC0CAC10ObjectiveC8SelectorV8selector_tcfC ------------------ | Unexecuted instantiation: _T022OrderedDictionaryTests0a4KeysC0CACycfC ------------------ 7| | 8| 1| func testOrderedKeys() { 9| 10| measure { 10| 10| var dict = OrderedDictionary() 11| 10.0k| sourceData.forEach { 12| 10.0k| dict[$0.key] = $0.value 13| 10.0k| } 14| 10| 15| 10.0k| XCTAssertEqual(dict.orderedKeys, sourceData.map { $0.key }) 16| 10.0k| sourceData.forEach { 17| 10.0k| XCTAssertEqual(dict[$0.key], $0.value) 18| 10.0k| } 19| 10| } 20| 1| } 21| | 22| 1| func testOrderedKeysConcurrent() { 23| 10| measure { 24| 10| var dict = OrderedDictionary() 25| 9.99k| DispatchQueue.concurrentPerform(iterations: sourceData.count) { iteration in 26| 9.99k| let key = sourceData[iteration].key 27| 9.99k| dict[key] = sourceData[iteration].value 28| 9.99k| } 29| 10| 30| 10| XCTAssertEqual(dict.orderedKeys.count, sourceData.count) 31| 10| 32| 9.99k| DispatchQueue.concurrentPerform(iterations: sourceData.count) { iteration in 33| 9.99k| let pair = sourceData[iteration] 34| 9.99k| XCTAssertEqual(dict[pair.key], pair.value) 35| 9.99k| } 36| 10| } 37| 1| } 38| | 39| 1| func testOrderedKeysAsync() { 40| 10| measure { 41| 10| var dict = OrderedDictionary() 42| 10| 43| 10| let group = DispatchGroup() 44| 10.0k| sourceData.forEach { pair in 45| 10.0k| group.enter() 46| 10.0k| DispatchQueue.global().async { 47| 10.0k| dict[pair.key] = pair.value 48| 10.0k| group.leave() 49| 10.0k| } 50| 10.0k| } 51| 10| group.wait() 52| 10| 53| 10| XCTAssertEqual(dict.orderedKeys.count, sourceData.count) 54| 10| 55| 10.0k| sourceData.forEach { pair in 56| 10.0k| group.enter() 57| 10.0k| DispatchQueue.global().async { 58| 10.0k| XCTAssertEqual(dict[pair.key], pair.value) 59| 10.0k| group.leave() 60| 10.0k| } 61| 10.0k| group.wait() 62| 10.0k| } 63| 10| } 64| 1| } 65| | 66| 1| func testOrderedKeysSetTwice() { 67| 10| measure { 68| 10| var dict = OrderedDictionary() 69| 10.0k| sourceData.forEach { 70| 10.0k| dict[$0.key] = $0.value 71| 10.0k| dict[$0.key] = "foo" 72| 10.0k| } 73| 10| 74| 10.0k| XCTAssertEqual(dict.orderedKeys, sourceData.map { $0.key }) 75| 10.0k| sourceData.forEach { 76| 10.0k| XCTAssertEqual(dict[$0.key], "foo") 77| 10.0k| } 78| 10| } 79| 1| } 80| | 81| 1| func testOrderedKeysSetAndClear() { 82| 10| measure { 83| 10| var dict = OrderedDictionary() 84| 10.0k| sourceData.forEach { 85| 10.0k| dict[$0.key] = $0.value 86| 10.0k| dict[$0.key] = nil 87| 10.0k| } 88| 10| 89| 10| XCTAssertEqual(dict.orderedKeys.count, 0) 90| 10.0k| sourceData.forEach { 91| 10.0k| XCTAssertNil(dict[$0.key]) 92| 10.0k| } 93| 10| } 94| 1| } 95| | 96| 1| func testOrderedKeysSetThenClear() { 97| 10| measure { 98| 10| var dict = OrderedDictionary() 99| 10.0k| sourceData.forEach { 100| 10.0k| dict[$0.key] = $0.value 101| 10.0k| } 102| 10.0k| sourceData.forEach { 103| 10.0k| dict[$0.key] = nil 104| 10.0k| } 105| 10| 106| 10| XCTAssertEqual(dict.orderedKeys.count, 0) 107| 10.0k| sourceData.forEach { 108| 10.0k| XCTAssertNil(dict[$0.key]) 109| 10.0k| } 110| 10| } 111| 1| } 112| | 113| | static var allTests = [ 114| | ("testOrderedKeys", testOrderedKeys), 115| | ("testOrderedKeysConcurrent", testOrderedKeysConcurrent), 116| | ("testOrderedKeysAsync", testOrderedKeysAsync), 117| | ("testOrderedKeysSetTwice", testOrderedKeysSetTwice), 118| | ("testOrderedKeysSetAndClear", testOrderedKeysSetAndClear), 119| | ("testOrderedKeysSetThenClear", testOrderedKeysSetThenClear) 120| | ] 121| |} <<<<<< EOF