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 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174
|
//===----------------------------------------------------------------------===//
//
// 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
//
//===----------------------------------------------------------------------===//
@usableFromInline @frozen
internal struct _HeapNode {
@usableFromInline
internal var offset: Int
@usableFromInline
internal var level: Int
@inlinable
internal init(offset: Int, level: Int) {
assert(offset >= 0)
#if COLLECTIONS_INTERNAL_CHECKS
assert(level == Self.level(forOffset: offset))
#endif
self.offset = offset
self.level = level
}
@inlinable
internal init(offset: Int) {
self.init(offset: offset, level: Self.level(forOffset: offset))
}
}
extension _HeapNode: Comparable {
@inlinable @inline(__always)
internal static func ==(left: Self, right: Self) -> Bool {
left.offset == right.offset
}
@inlinable @inline(__always)
internal static func <(left: Self, right: Self) -> Bool {
left.offset < right.offset
}
}
extension _HeapNode: CustomStringConvertible {
@usableFromInline
internal var description: String {
"(offset: \(offset), level: \(level))"
}
}
extension _HeapNode {
@inlinable @inline(__always)
internal static func level(forOffset offset: Int) -> Int {
(offset &+ 1)._binaryLogarithm()
}
@inlinable @inline(__always)
internal static func firstNode(onLevel level: Int) -> _HeapNode {
assert(level >= 0)
return _HeapNode(offset: (1 &<< level) &- 1, level: level)
}
@inlinable @inline(__always)
internal static func lastNode(onLevel level: Int) -> _HeapNode {
assert(level >= 0)
return _HeapNode(offset: (1 &<< (level &+ 1)) &- 2, level: level)
}
@inlinable @inline(__always)
internal static func isMinLevel(_ level: Int) -> Bool {
level & 0b1 == 0
}
}
extension _HeapNode {
/// The root node in the heap.
@inlinable @inline(__always)
internal static var root: Self {
Self.init(offset: 0, level: 0)
}
/// The first max node in the heap. (I.e., the left child of the root.)
@inlinable @inline(__always)
internal static var leftMax: Self {
Self.init(offset: 1, level: 1)
}
/// The second max node in the heap. (I.e., the right child of the root.)
@inlinable @inline(__always)
internal static var rightMax: Self {
Self.init(offset: 2, level: 1)
}
@inlinable @inline(__always)
internal var isMinLevel: Bool {
Self.isMinLevel(level)
}
@inlinable @inline(__always)
internal var isRoot: Bool {
offset == 0
}
}
extension _HeapNode {
/// Returns the parent of this index, or `nil` if the index has no parent
/// (i.e. when this is the root index).
@inlinable @inline(__always)
internal func parent() -> Self {
assert(!isRoot)
return Self(offset: (offset &- 1) / 2, level: level &- 1)
}
/// Returns the grandparent of this index, or `nil` if the index has
/// no grandparent.
@inlinable @inline(__always)
internal func grandParent() -> Self? {
guard offset > 2 else { return nil }
return Self(offset: (offset &- 3) / 4, level: level &- 2)
}
/// Returns the left child of this node.
@inlinable @inline(__always)
internal func leftChild() -> Self {
Self(offset: offset &* 2 &+ 1, level: level &+ 1)
}
/// Returns the right child of this node.
@inlinable @inline(__always)
internal func rightChild() -> Self {
Self(offset: offset &* 2 &+ 2, level: level &+ 1)
}
@inlinable @inline(__always)
internal func firstGrandchild() -> Self {
Self(offset: offset &* 4 &+ 3, level: level &+ 2)
}
@inlinable @inline(__always)
internal func lastGrandchild() -> Self {
Self(offset: offset &* 4 &+ 6, level: level &+ 2)
}
@inlinable
internal static func allNodes(
onLevel level: Int,
limit: Int
) -> ClosedRange<Self>? {
let first = Self.firstNode(onLevel: level)
guard first.offset < limit else { return nil }
var last = self.lastNode(onLevel: level)
if last.offset >= limit {
last.offset = limit &- 1
}
return ClosedRange(uncheckedBounds: (first, last))
}
}
extension ClosedRange where Bound == _HeapNode {
@inlinable @inline(__always)
internal func _forEach(_ body: (_HeapNode) -> Void) {
assert(
isEmpty || _HeapNode.level(forOffset: upperBound.offset) == lowerBound.level)
var node = self.lowerBound
while node.offset <= self.upperBound.offset {
body(node)
node.offset &+= 1
}
}
}
|