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
|
//===----------------------------------------------------------------------===//
//
// This source file is part of the Swift Collections open source project
//
// Copyright (c) 2021 - 2024 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
//
//===----------------------------------------------------------------------===//
#if !COLLECTIONS_SINGLE_MODULE
import InternalCollectionsUtilities
#endif
extension Heap {
/// True if consistency checking is enabled in the implementation of this
/// type, false otherwise.
///
/// Documented performance promises are null and void when this property
/// returns true -- for example, operations that are documented to take
/// O(1) time might take O(*n*) time, or worse.
public static var _isConsistencyCheckingEnabled: Bool {
_isCollectionsInternalCheckingEnabled
}
#if COLLECTIONS_INTERNAL_CHECKS
/// Visits each item in the heap in depth-first order, verifying that the
/// contents satisfy the min-max heap property.
@inlinable
@inline(never)
internal func _checkInvariants() {
guard count > 1 else { return }
_checkInvariants(node: .root, min: nil, max: nil)
}
@inlinable
internal func _checkInvariants(node: _HeapNode, min: Element?, max: Element?) {
let value = _storage[node.offset]
if let min = min {
precondition(value >= min,
"Element \(value) at \(node) is less than min \(min)")
}
if let max = max {
precondition(value <= max,
"Element \(value) at \(node) is greater than max \(max)")
}
let left = node.leftChild()
let right = node.rightChild()
if node.isMinLevel {
if left.offset < count {
_checkInvariants(node: left, min: value, max: max)
}
if right.offset < count {
_checkInvariants(node: right, min: value, max: max)
}
} else {
if left.offset < count {
_checkInvariants(node: left, min: min, max: value)
}
if right.offset < count {
_checkInvariants(node: right, min: min, max: value)
}
}
}
#else
@inlinable
@inline(__always)
public func _checkInvariants() {}
#endif // COLLECTIONS_INTERNAL_CHECKS
}
|
