Queue
该实现较为复杂，需要有时间仔细去阅读
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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
struct Queue<T>: Sequence {
/// Type of generator.
typealias Generator = AnyIterator<T>
private let _resizeFactor = 2
private var _storage: ContiguousArray<T?>
private var _count = 0
private var _pushNextIndex = 0
private let _initialCapacity: Int
/**
Creates new queue.
- parameter capacity: Capacity of newly created queue.
*/
init(capacity: Int) {
_initialCapacity = capacity
_storage = ContiguousArray<T?>(repeating: nil, count: capacity)
}
private var dequeueIndex: Int {
let index = _pushNextIndex - count
return index < 0 ? index + _storage.count : index
}
/// - returns: Is queue empty.
var isEmpty: Bool {
return count == 0
}
/// - returns: Number of elements inside queue.
var count: Int {
return _count
}
/// - returns: Element in front of a list of elements to `dequeue`.
func peek() -> T {
precondition(count > 0)
return _storage[dequeueIndex]!
}
mutating private func resizeTo(_ size: Int) {
var newStorage = ContiguousArray<T?>(repeating: nil, count: size)
let count = _count
let dequeueIndex = self.dequeueIndex
let spaceToEndOfQueue = _storage.count - dequeueIndex
// first batch is from dequeue index to end of array
let countElementsInFirstBatch = Swift.min(count, spaceToEndOfQueue)
// second batch is wrapped from start of array to end of queue
let numberOfElementsInSecondBatch = count - countElementsInFirstBatch
newStorage[0 ..< countElementsInFirstBatch] = _storage[dequeueIndex ..< (dequeueIndex + countElementsInFirstBatch)]
newStorage[countElementsInFirstBatch ..< (countElementsInFirstBatch + numberOfElementsInSecondBatch)] = _storage[0 ..< numberOfElementsInSecondBatch]
_count = count
_pushNextIndex = count
_storage = newStorage
}
/// Enqueues `element`.
///
/// - parameter element: Element to enqueue.
mutating func enqueue(_ element: T) {
if count == _storage.count {
resizeTo(Swift.max(_storage.count, 1) * _resizeFactor)
}
_storage[_pushNextIndex] = element
_pushNextIndex += 1
_count += 1
if _pushNextIndex >= _storage.count {
_pushNextIndex -= _storage.count
}
}
private mutating func dequeueElementOnly() -> T {
precondition(count > 0)
let index = dequeueIndex
defer {
_storage[index] = nil
_count -= 1
}
return _storage[index]!
}
/// Dequeues element or throws an exception in case queue is empty.
///
/// - returns: Dequeued element.
mutating func dequeue() -> T? {
if self.count == 0 {
return nil
}
defer {
let downsizeLimit = _storage.count / (_resizeFactor * _resizeFactor)
if _count < downsizeLimit && downsizeLimit >= _initialCapacity {
resizeTo(_storage.count / _resizeFactor)
}
}
return dequeueElementOnly()
}
/// - returns: Generator of contained elements.
func makeIterator() -> AnyIterator<T> {
var i = dequeueIndex
var count = _count
return AnyIterator {
if count == 0 {
return nil
}
defer {
count -= 1
i += 1
}
if i >= self._storage.count {
i -= self._storage.count
}
return self._storage[i]
}
}
}
注：文中源码来自RxSwift