/src/swift-nio/Sources/_NIODataStructures/PriorityQueue.swift
Line | Count | Source (jump to first uncovered line) |
1 | | //===----------------------------------------------------------------------===// |
2 | | // |
3 | | // This source file is part of the SwiftNIO open source project |
4 | | // |
5 | | // Copyright (c) 2017-2021 Apple Inc. and the SwiftNIO project authors |
6 | | // Licensed under Apache License v2.0 |
7 | | // |
8 | | // See LICENSE.txt for license information |
9 | | // See CONTRIBUTORS.txt for the list of SwiftNIO project authors |
10 | | // |
11 | | // SPDX-License-Identifier: Apache-2.0 |
12 | | // |
13 | | //===----------------------------------------------------------------------===// |
14 | | |
15 | | public struct PriorityQueue<Element: Comparable> { |
16 | | @usableFromInline |
17 | | internal var _heap: Heap<Element> |
18 | | |
19 | | @inlinable |
20 | 515k | public init() { |
21 | 515k | self._heap = Heap() |
22 | 515k | } |
23 | | |
24 | | @inlinable |
25 | 0 | public mutating func remove(_ key: Element) { |
26 | 0 | self._heap.remove(value: key) |
27 | 0 | } |
28 | | |
29 | | @discardableResult |
30 | | @inlinable |
31 | 0 | public mutating func removeFirst(where shouldBeRemoved: (Element) throws -> Bool) rethrows -> Element? { |
32 | 0 | try self._heap.removeFirst(where: shouldBeRemoved) |
33 | 0 | } |
34 | | |
35 | | @inlinable |
36 | 118k | public mutating func push(_ key: Element) { |
37 | 118k | self._heap.append(key) |
38 | 118k | } |
39 | | |
40 | | @inlinable |
41 | 851k | public func peek() -> Element? { |
42 | 851k | self._heap.storage.first |
43 | 851k | } |
44 | | |
45 | | @inlinable |
46 | 236k | public var isEmpty: Bool { |
47 | 236k | self._heap.storage.isEmpty |
48 | 236k | } |
49 | | |
50 | | @inlinable |
51 | | @discardableResult |
52 | 236k | public mutating func pop() -> Element? { |
53 | 236k | self._heap.removeRoot() |
54 | 236k | } |
55 | | |
56 | | @inlinable |
57 | 0 | public mutating func clear() { |
58 | 0 | self._heap = Heap() |
59 | 0 | } |
60 | | } |
61 | | |
62 | | extension PriorityQueue: Equatable { |
63 | | @inlinable |
64 | 0 | public static func == (lhs: PriorityQueue, rhs: PriorityQueue) -> Bool { |
65 | 0 | lhs.count == rhs.count && lhs.elementsEqual(rhs) |
66 | 0 | } |
67 | | } |
68 | | |
69 | | extension PriorityQueue: Sequence { |
70 | | public struct Iterator: IteratorProtocol { |
71 | | |
72 | | @usableFromInline |
73 | | var _queue: PriorityQueue<Element> |
74 | | |
75 | | @inlinable |
76 | 0 | public init(queue: PriorityQueue<Element>) { |
77 | 0 | self._queue = queue |
78 | 0 | } |
79 | | |
80 | | @inlinable |
81 | 0 | public mutating func next() -> Element? { |
82 | 0 | self._queue.pop() |
83 | 0 | } |
84 | | } |
85 | | |
86 | | @inlinable |
87 | 0 | public func makeIterator() -> Iterator { |
88 | 0 | Iterator(queue: self) |
89 | 0 | } |
90 | | } |
91 | | |
92 | | extension PriorityQueue { |
93 | | @inlinable |
94 | 0 | public var count: Int { |
95 | 0 | self._heap.count |
96 | 0 | } |
97 | | } |
98 | | |
99 | | extension PriorityQueue: CustomStringConvertible { |
100 | | @inlinable |
101 | 0 | public var description: String { |
102 | 0 | "PriorityQueue(count: \(self.count)): \(Array(self))" |
103 | 0 | } |
104 | | } |
105 | | |
106 | | extension PriorityQueue: Sendable where Element: Sendable {} |
107 | | extension PriorityQueue.Iterator: Sendable where Element: Sendable {} |