BagKey
1
2
3
4
5
6
7
8
9
struct BagKey {
/**
Unique identifier for object added to `Bag`.
It's underlying type is UInt64. If we assume there in an idealized CPU that works at 4GHz,
it would take ~150 years of continuous running time for it to overflow.
*/
fileprivate let rawValue: UInt64
}
Bag
Data structure that represents a bag of elements typed T.
Single element can be stored multiple times.
Time and space complexity of insertion and deletion is O(n).
It is suitable for storing small number of elements.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
struct Bag<T> : CustomDebugStringConvertible {
/// Type of identifier for inserted elements.
typealias KeyType = BagKey
typealias Entry = (key: BagKey, value: T)
private var _nextKey: BagKey = BagKey(rawValue: 0)
// data
// first fill inline variables
var _key0: BagKey?
var _value0: T?
// then fill "array dictionary"
var _pairs = ContiguousArray<Entry>()
// last is sparse dictionary
var _dictionary: [BagKey: T]?
var _onlyFastPath = true
/// Creates new empty `Bag`.
init() {
}
/**
Inserts `value` into bag.
- parameter element: Element to insert.
- returns: Key that can be used to remove element from bag.
*/
mutating func insert(_ element: T) -> BagKey {
let key = _nextKey
_nextKey = BagKey(rawValue: _nextKey.rawValue &+ 1)
if _key0 == nil {
_key0 = key
_value0 = element
return key
}
_onlyFastPath = false
if _dictionary != nil {
_dictionary![key] = element
return key
}
if _pairs.count < arrayDictionaryMaxSize {
_pairs.append((key: key, value: element))
return key
}
_dictionary = [key: element]
return key
}
/// - returns: Number of elements in bag.
var count: Int {
let dictionaryCount: Int = _dictionary?.count ?? 0
return (_value0 != nil ? 1 : 0) + _pairs.count + dictionaryCount
}
/// Removes all elements from bag and clears capacity.
mutating func removeAll() {
_key0 = nil
_value0 = nil
_pairs.removeAll(keepingCapacity: false)
_dictionary?.removeAll(keepingCapacity: false)
}
/**
Removes element with a specific `key` from bag.
- parameter key: Key that identifies element to remove from bag.
- returns: Element that bag contained, or nil in case element was already removed.
*/
mutating func removeKey(_ key: BagKey) -> T? {
if _key0 == key {
_key0 = nil
let value = _value0!
_value0 = nil
return value
}
if let existingObject = _dictionary?.removeValue(forKey: key) {
return existingObject
}
for i in 0 ..< _pairs.count where _pairs[i].key == key {
let value = _pairs[i].value
_pairs.remove(at: i)
return value
}
return nil
}
}
enumeration
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
extension Bag {
/// Enumerates elements inside the bag.
///
/// - parameter action: Enumeration closure.
func forEach(_ action: (T) -> Void) {
if _onlyFastPath {
if let value0 = _value0 {
action(value0)
}
return
}
let value0 = _value0
let dictionary = _dictionary
if let value0 = value0 {
action(value0)
}
for i in 0 ..< _pairs.count {
action(_pairs[i].value)
}
if dictionary?.count ?? 0 > 0 {
for element in dictionary!.values {
action(element)
}
}
}
}
1
2
3
4
5
extension BagKey: Hashable {
func hash(into hasher: inout Hasher) {
hasher.combine(rawValue)
}
}
注：文中源码来自RxSwift