提出 #62143443
ソースコード 拡げる
import Foundation
private let main: () = {
do { try Answer() } catch { /* WA */ }
}()
public func Answer() throws {
let (H, W, Q): Int3 = Input.read()
let _g1 = RedBlackTreeSet<Int>(0 ..< W)
let _g2 = RedBlackTreeSet<Int>(0 ..< H)
var g1: [RedBlackTreeSet<Int>] = [_g1] * H
var g2: [RedBlackTreeSet<Int>] = [_g2] * W
func erase(_ i: Int, _ j: Int) {
g1[i].remove(j)
g2[j].remove(i)
}
for _ in 0..<Q {
let (R, C): Int2 = (.read() - 1, .read() - 1)
if g1[R].contains(C) {
erase(R, C)
continue
}
if let r = g2[C].lowerBound(R).previous?.pointee {
erase(r, C)
}
if let r = g2[C].lowerBound(R).pointee {
erase(r, C)
}
if let c = g1[R].lowerBound(C).previous?.pointee {
erase(R, c)
}
if let c = g1[R].lowerBound(C).pointee {
erase(R, c)
}
}
var ans = 0
for i in 0..<H {
ans += g1[i].count
}
print(ans)
}
// MARK: - 以下連結
import Foundation
// MARK: - Read
public protocol SingleRead {
@inlinable @inline(__always)
static func read() -> Self
}
public protocol TupleRead: SingleRead { }
public protocol ArrayRead: SingleRead { }
public protocol FullRead: ArrayRead & TupleRead { }
public extension Collection where Element: ArrayRead {
@inlinable @inline(__always)
static func read(columns: Int) -> [Element] {
(0..<columns).map{ _ in Element.read() }
}
@inlinable @inline(__always)
static func read(rows: Int) -> [Element] {
(0..<rows).map{ _ in Element.read() }
}
}
public extension Collection where Element: Collection, Element.Element: ArrayRead {
@inlinable @inline(__always)
static func read(rows: Int, columns: Int) -> [[Element.Element]] {
(0..<rows).map{ _ in Element.read(columns: columns) }
}
}
extension Int: FullRead { }
extension UInt: FullRead { }
extension Double: FullRead { }
extension CInt: FullRead { }
extension CUnsignedInt: FullRead { }
extension CLongLong: FullRead { }
extension CUnsignedLongLong: FullRead { }
extension String: TupleRead { }
extension Character: TupleRead { }
extension UInt8: TupleRead { }
public extension FixedWidthInteger {
@inlinable @inline(__always) static func read() -> Self { .init(ATOL.read()!) }
}
public extension BinaryFloatingPoint {
@inlinable @inline(__always) static func read() -> Self { .init(ATOF.read()!) }
}
public extension String {
@inlinable @inline(__always)
static func read() -> String { ATOS.read() }
@inlinable @inline(__always)
static func read(columns: Int) -> String { ATOS.read(columns: columns) }
}
public extension Array where Element == String {
@inlinable @inline(__always)
static func read(rows: Int, columns: Int) -> [String] {
(0..<rows).map { _ in .read(columns: columns) }
}
}
public extension UInt8 {
static func read() -> UInt8 { ATOB.read(columns: 1).first! }
}
public extension Array where Element == UInt8 {
@inlinable @inline(__always)
static func read() -> [UInt8] { ATOB.read() }
@inlinable @inline(__always)
static func read(columns: Int) -> [UInt8] { ATOB.read(columns: columns) }
}
public extension Array where Element == Array<UInt8> {
@inlinable @inline(__always)
static func read(rows: Int, columns: Int) -> [[UInt8]] {
(0..<rows).map { _ in .read(columns: columns) }
}
}
public extension Character {
static func read() -> Character { Character(String.read(columns: 1)) }
}
public extension Array where Element == Character {
@inlinable @inline(__always)
static func read() -> [Character] {
String.read().map{ $0 }
}
@inlinable @inline(__always)
static func read(columns: Int) -> [Character] {
String.read(columns: columns).map{ $0 }
}
}
public extension Array where Element == Array<Character> {
@inlinable @inline(__always)
static func read(rows: Int, columns: Int) -> [[Character]] {
(0..<rows).map { _ in .read(columns: columns) }
}
}
@usableFromInline protocol IOReader { }
@usableFromInline protocol FixedBufferIOReader: IOReader {
var buffer: [UInt8] { get set }
}
extension FixedWidthInteger {
@inlinable @inline(__always) static var SP: Self { 0x20 }
@inlinable @inline(__always) static var LF: Self { 0x0A }
}
extension FixedWidthInteger {
@inlinable @inline(__always)
static func __readHead() -> Self {
var head: Self
repeat {
head = numericCast(getchar_unlocked())
} while head == .SP || head == .LF;
return head
}
}
extension Array where Element: FixedWidthInteger {
@inlinable @inline(__always)
static func __readBytes(count: Int) -> Self? {
let h: Element = .__readHead()
guard h != EOF else { return nil }
return [h] + (1..<count).map { _ in numericCast(getchar_unlocked()) }
}
}
extension FixedBufferIOReader {
@inlinable @inline(__always)
mutating func _next<T>(_ f: (UnsafePointer<UInt8>) -> T) -> T? {
var current = 0
return buffer.withUnsafeMutableBufferPointer { buffer in
buffer.baseAddress![current] = .__readHead()
while buffer.baseAddress![current] != .SP,
buffer.baseAddress![current] != .LF,
buffer.baseAddress![current] != EOF
{
current += 1
buffer[current] = numericCast(getchar_unlocked())
}
return current == 0 ? nil : f(buffer.baseAddress!)
}
}
}
@usableFromInline protocol VariableBufferIOReader: IOReader {
associatedtype BufferElement: FixedWidthInteger
var buffer: [BufferElement] { get set }
}
extension VariableBufferIOReader {
@inlinable @inline(__always)
mutating func _next<T>(_ f: (UnsafeBufferPointer<BufferElement>, Int) -> T?) -> T? {
var current = 0
buffer[current] = .__readHead()
while buffer[current] != .SP, buffer[current] != .LF, buffer[current] != 0 {
current += 1
if current == buffer.count {
buffer.append(contentsOf: repeatElement(0, count: buffer.count))
}
buffer[current] = BufferElement(truncatingIfNeeded: getchar_unlocked())
}
return buffer.withUnsafeBufferPointer{ f($0, current) }
}
}
@usableFromInline protocol IOReaderInstance: IteratorProtocol {
static var instance: Self { get set }
}
extension IOReaderInstance {
@inlinable @inline(__always) static func read() -> Element! { instance.next() }
}
@usableFromInline struct ATOL: IteratorProtocol, FixedBufferIOReader, IOReaderInstance {
public var buffer = [UInt8](repeating: 0, count: 32)
@inlinable @inline(__always)
public mutating func next() -> Int? { _next { atol($0) } }
public static var instance = Self()
}
@usableFromInline struct ATOF: IteratorProtocol, FixedBufferIOReader, IOReaderInstance {
public var buffer = [UInt8](repeating: 0, count: 64)
@inlinable @inline(__always)
public mutating func next() -> Double? { _next { atof($0) } }
public static var instance = Self()
}
@usableFromInline struct ATOB: IteratorProtocol, VariableBufferIOReader, IOReaderInstance {
public var buffer: [UInt8] = .init(repeating: 0, count: 32)
@inlinable @inline(__always)
public mutating func next() -> Array<UInt8>? { _next { Array($0[0..<$1]) } }
public static var instance = Self()
@inlinable @inline(__always) static func read(columns: Int) -> [UInt8] {
defer { getchar_unlocked() }
return .__readBytes(count: columns) ?? []
}
}
@usableFromInline struct ATOS: IteratorProtocol, VariableBufferIOReader, IOReaderInstance {
public var buffer = [UInt8](repeating: 0, count: 32)
@inlinable @inline(__always)
public mutating func next() -> String? { _next { b,c in String(bytes: b[0..<c], encoding: .ascii) } }
public static var instance = Self()
@inlinable @inline(__always) static func read(columns: Int) -> String! {
defer { getchar_unlocked() }
return String(bytes: Array.__readBytes(count: columns) ?? [], encoding: .ascii)
}
}
import Foundation
struct Pair<A: Hashable,B: Hashable>: Hashable {
init(_ a: A,_ b: B) { (self.a, self.b) = (a,b) }
init(_ ab: (A, B)) { (self.a, self.b) = ab }
var a: A
var b: B
}
import Foundation
// MARK: - dijkstra
enum Dijkstra {
enum Error: Swift.Error {
case cycle
}
struct _edge<Cost: Comparable & AdditiveArithmetic>: Comparable {
@inlinable @inline(__always)
init(to: Int, cost: Cost) {
self.to = to
self.cost = cost
}
@inlinable @inline(__always)
init(_ pair: (Int, Cost)) {
(self.to, self.cost) = pair
}
let to: Int
let cost: Cost
@inlinable @inline(__always)
static func < (lhs: Self, rhs: Self) -> Bool {
lhs.cost < rhs.cost || (lhs.cost == rhs.cost && lhs.to < rhs.to)
}
}
static func dijkstra<Cost: Comparable & AdditiveArithmetic>(_ graph: [[(to: Int, cost: Cost)]], to: Int, INF: Cost) -> [Cost] {
var dist = [Cost](repeating: INF, count: graph.count)
var visited = [false] * graph.count
dist[to] = .zero
var queue = PriorityQueue([_edge<Cost>(to: to, cost: .zero)])
while let now = queue.popMin() {
let u = now.to
if visited[u] { continue }
visited[u] = true
for (v, weight) in graph[u] {
if !visited[v], dist[u] + weight < dist[v] {
dist[v] = dist[u] + weight
queue.insert(.init(to: v, cost: dist[v]))
}
}
}
return dist;
}
static func distances(_ graph: [[Int]], to: Int, INF: Int) -> [Int] {
var dist = [Int](repeating: Int.max, count: graph.count)
var visited = [false] * graph.count
dist[to] = .zero
var queue = PriorityQueue([_edge<Int>(to: to, cost: .zero)])
let cost = 1
while let now = queue.popMin() {
let u = now.to
if visited[u] { continue }
visited[u] = true
for v in graph[u] {
let weight = cost
if !visited[v], dist[u] + weight < dist[v] {
dist[v] = dist[u] + weight
queue.insert(.init(to: v, cost: dist[v]))
}
}
}
return dist;
}
static func distances(pos_to: [[Int:Int]], to: Int, INF: Int) -> [Int] {
var dist = [Int](repeating: INF, count: pos_to.count)
dist[to] = .zero
var queue = PriorityQueue([_edge<Int>(to: to, cost: .zero)])
while let now = queue.popMin() {
if dist[now.to] < now.cost { continue }
for e in pos_to[now.to] {
if dist[e.key] > now.cost + e.value {
dist[e.key] = now.cost + e.value
queue.insert(.init(to: e.key, cost: now.cost + e.value))
}
}
}
return dist;
}
static func distances(pos_to: [[Int]], cost: [[Int]], to: Int, INF: Int) -> [Int] {
var dist = [Int](repeating: Int.max, count: pos_to.count)
var visited = [false] * pos_to.count
dist[to] = .zero
var queue = PriorityQueue([_edge<Int>(to: to, cost: .zero)])
while let now = queue.popMin() {
let u = now.to
if visited[u] { continue }
visited[u] = true
for v in pos_to[u] {
let weight = cost[u][v]
if !visited[v], dist[u] + weight < dist[v] {
dist[v] = dist[u] + weight
queue.insert(.init(to: v, cost: dist[v]))
}
}
}
return dist;
}
static func route<Cost: Comparable & AdditiveArithmetic>(_ graph: [[(to: Int, cost: Cost)]], from: Int, to: Int, INF: Cost, dist: [Cost]) throws -> [Int] {
var visited = [false] * graph.count
var result = [Int]()
var pos = from
visited[from] = true
while pos != to {
pos = graph[pos].first{ dist[$0.to] == dist[pos] - $0.cost }!.to
if visited[pos] {
throw Dijkstra.Error.cycle
}
result.append(pos)
visited[pos] = true
}
return result
}
static func route(_ graph: [[Int:Int]], from: Int, to: Int, INF: Int, dist: [Int]) throws -> [Int] {
var visited = [false] * graph.count
var result = [Int]()
var pos = from
visited[from] = true
while pos != to {
pos = graph[pos].sorted(by: { $0.key < $1.key }).first{ dist[$0.key] == dist[pos] - $0.value }!.key
if visited[pos] {
throw Dijkstra.Error.cycle
}
result.append(pos)
visited[pos] = true
}
return result
}
static func route(pos_to: [[Int]], from: Int, to: Int, dist: [Int]) throws -> [Int] {
var visited = [false] * pos_to.count
var result = [Int]()
var pos = from
visited[from] = true
while pos != to {
pos = pos_to[pos].first{ dist[$0] == dist[pos] - 1 }!
if visited[pos] {
throw Dijkstra.Error.cycle
}
result.append(pos)
visited[pos] = true
}
return result
}
static func route(pos_to: [[Int]], cost: [[Int]], dist: [Int], from: Int, to: Int) throws -> [Int] {
var visited = [false] * pos_to.count
var result = [Int]()
var pos = from
visited[from] = true
while pos != to {
pos = pos_to[pos].first{ dist[$0] == dist[pos] - cost[pos][$0] }!
if visited[pos] {
throw Dijkstra.Error.cycle
}
result.append(pos)
visited[pos] = true
}
return result
}
static func path<Cost: Comparable & AdditiveArithmetic>(_ graph: [[(to: Int, cost: Cost)]], from: Int, to: Int, INF: Cost) throws -> [Int] {
if graph[from].contains(where: { $0.to == to }) {
return [to]
}
let dist = dijkstra(graph, to: to, INF: INF)
return try route(graph, from: from, to: to, INF: INF, dist: dist)
}
static func path(_ graph: [[Int:Int]], from: Int, to: Int, INF: Int) throws -> [Int] {
if graph[from][to, default: 0] > 0 {
return [to]
}
let dist = distances(pos_to: graph, to: to, INF: INF)
return try route(graph, from: from, to: to, INF: INF, dist: dist)
}
static func path(_ graph: [[Int]], from: Int, to: Int, INF: Int) throws -> [Int] {
if graph[from].contains(to) {
return [to]
}
let dist = distances(graph, to: to, INF: INF)
return try route(pos_to: graph, from: from, to: to, dist: dist)
}
static func path(_ pos_to: [[Int]], cost: [[Int]], from: Int, to: Int, INF: Int) throws -> (path: [Int], cost: Int) {
if pos_to[from].contains(to) {
return ([to], cost[from][to])
}
let dist = distances(pos_to: pos_to, cost: cost, to: to, INF: INF)
return try (route(pos_to: pos_to, cost: cost, dist: dist, from: from, to: to), dist[from])
}
}
//
// File.swift
// AtCoderBeginner
//
// Created by narumij on 2024/08/12.
//
import Foundation
/// 累積和1D
func cum<T>(_ A: [T]) -> [T] where T: AdditiveArithmetic, T: ExpressibleByIntegerLiteral {
let N = A.count
var s: [T] = [0] * (N + 1)
for i in 0 ..< N {
s[i + 1] =
s[i]
+ A[i]
}
return s
}
/// 累積和2D
func cum<T>(_ A: [[T]]) -> [[T]] where T: AdditiveArithmetic, T: ExpressibleByIntegerLiteral {
let N = A.count
let M = A[0].count
assert(A.allSatisfy{ $0.count == M })
var s: [[T]] = [0] * (N + 1, M + 1)
for i in 0 ..< N {
for j in 0 ..< M {
s[i + 1][j + 1] =
s[i + 1][j]
+ s[i][j + 1]
- s[i][j]
+ A[i][j]
}
}
return s
}
/// 累積和3D
func cum<T>(_ A: [[[T]]]) -> [[[T]]] where T: AdditiveArithmetic, T: ExpressibleByIntegerLiteral {
let N = A.count
let M = A[0].count
let L = A[0][0].count
assert(A.allSatisfy{ $0.count == M })
assert(A.allSatisfy{ $0.allSatisfy{ $0.count == L } })
var s: [[[T]]] = [0] * (N + 1, M + 1, L + 1)
for i in 0..<N {
for j in 0..<M {
for k in 0..<L {
s[i + 1][j + 1][k + 1] =
s[i + 1][j + 1][k]
+ s[i + 1][j][k + 1]
+ s[i][j + 1][k + 1]
- s[i + 1][j][k]
- s[i][j + 1][k]
- s[i][j][k + 1]
+ s[i][j][k]
+ A[i][j][k]
}
}
}
return s
}
import Foundation
// MARK: - STDERR
extension UnsafeMutablePointer: TextOutputStream where Pointee == FILE {
public mutating func write(_ string: String) {
guard let data = string.data(using: .utf8) else { return }
_ = data.withUnsafeBytes { bytes in
#if os(Linux)
Glibc.write(fileno(self), bytes.baseAddress!, data.count)
#else
Darwin.write(fileno(self), bytes.baseAddress!, data.count)
#endif
}
}
}
import Foundation
// MARK: - Heap
extension Array: BinaryHeap {
@inlinable @inline(__always)
mutating func __update_binary_heap<R>(_ comp: @escaping (Element, Element) -> Bool,
_ body: (BinaryHeapUnsafeHandle<Element>) -> R) -> R {
body(BinaryHeapUnsafeHandle(&self, startIndex: startIndex, endIndex: endIndex, comp))
}
}
protocol BinaryHeap: Sequence {
@inlinable @inline(__always)
mutating func __update_binary_heap<R>(_ comp: @escaping (Element, Element) -> Bool,
_ body: (BinaryHeapUnsafeHandle<Element>) -> R) -> R
}
extension BinaryHeap {
mutating func make_heap(_ end: Int,_ comp: @escaping (Element, Element) -> Bool) {
__update_binary_heap(comp) { $0.make_heap(end) }
}
mutating func push_heap(_ end: Int,_ comp: @escaping (Element, Element) -> Bool) {
__update_binary_heap(comp) { $0.push_heap(end) }
}
mutating func pop_heap(_ comp: @escaping (Element, Element) -> Bool) {
__update_binary_heap(comp) { $0.pop_heap($0.endIndex) }
}
}
extension Int {
// https://en.wikipedia.org/wiki/Binary_heap
@inlinable @inline(__always)
var parent: Int { (self - 1) >> 1 }
@inlinable @inline(__always)
var leftChild: Int { (self << 1) + 1 }
@inlinable @inline(__always)
var rightChild: Int { (self << 1) + 2 }
}
@usableFromInline
struct BinaryHeapUnsafeHandle<Element> {
@inlinable @inline(__always)
internal init(_ buffer: UnsafeMutablePointer<Element>,
startIndex: Int, endIndex: Int,
_ comp: @escaping (Element, Element) -> Bool)
{
self.buffer = buffer
self.startIndex = startIndex
self.endIndex = endIndex
self.comp = comp
}
@usableFromInline
let buffer: UnsafeMutablePointer<Element>
@usableFromInline
let comp: (Element, Element) -> Bool
@usableFromInline
let startIndex: Int
@usableFromInline
let endIndex: Int
}
extension BinaryHeapUnsafeHandle {
@usableFromInline
typealias Index = Int
@inlinable @inline(__always)
func push_heap(_ limit: Index) {
heapifyUp(limit, limit - 1, comp)
}
@inlinable @inline(__always)
func pop_heap(_ limit: Index) {
guard limit > 0, startIndex != limit - 1 else { return }
swap(&buffer[startIndex], &buffer[limit - 1])
heapifyDown(limit - 1, startIndex, comp)
}
@inlinable @inline(__always)
func heapifyUp(_ limit: Index,_ i: Index,_ comp: (Element, Element) -> Bool) {
guard i >= startIndex else { return }
let element = buffer[i]
var current = i
while current > startIndex {
let parent = current.parent
guard !comp(buffer[parent], element) else { break }
(buffer[current], current) = (buffer[parent], parent)
}
buffer[current] = element
}
@inlinable @inline(__always)
func heapifyDown(_ limit: Index,_ i: Index,_ comp: (Element, Element) -> Bool) {
let element = buffer[i]
var (current, selected) = (i,i)
while current < limit {
let leftChild = current.leftChild
let rightChild = leftChild + 1
if leftChild < limit,
comp(buffer[leftChild], element)
{
selected = leftChild
}
if rightChild < limit,
comp(buffer[rightChild], current == selected ? element : buffer[selected])
{
selected = rightChild
}
if selected == current { break }
(buffer[current], current) = (buffer[selected], selected)
}
buffer[current] = element
}
private func heapify(_ limit: Index,_ i: Index,_ comp: (Element, Element) -> Bool) {
guard let index = heapifyIndex(limit, i, comp) else { return }
swap(&buffer[i],&buffer[index])
heapify(limit, index, comp)
}
private func heapifyIndex(_ limit: Index,_ current: Index,_ comp: (Element, Element) -> Bool) -> Index? {
var next = current
if current.leftChild < limit,
comp(buffer[current.leftChild], buffer[next])
{
next = current.leftChild
}
if current.rightChild < limit,
comp(buffer[current.rightChild], buffer[next])
{
next = current.rightChild
}
return next == current ? nil : next
}
func isHeap(_ limit: Index) -> Bool {
(startIndex..<limit).allSatisfy{ heapifyIndex(limit, $0, comp) == nil }
}
func make_heap(_ limit: Index) {
for i in stride(from: limit / 2, through: startIndex, by: -1) {
heapify(limit, i, comp)
}
assert(isHeap(limit))
}
}
import Foundation
// MARK: - Inlined Collections
public protocol ArrayStorage {
associatedtype Element
associatedtype Buffer
static var bytes: Buffer { get }
}
/// とっても危険なので、よい子のみんなはまねしないように。
public struct StackOrHeapArray<Storage: ArrayStorage> {
public typealias Element = Storage.Element
public typealias Buffer = Storage.Buffer
public var buffer: Buffer
public var count: Int
@usableFromInline init() {
buffer = Storage.bytes
count = 0
}
@usableFromInline var inlineCount: Int { MemoryLayout<Buffer>.size }
@usableFromInline var capacity: Int { inlineCount / MemoryLayout<Element>.stride }
public var first: Element? { count == 0 ? nil : self[0] }
@inlinable @inline(__always)
func _read<R>(_ body: (UnsafeBufferPointer<Element>) -> R) -> R {
withUnsafeBytes(of: buffer) { buffer in
buffer.withMemoryRebound(to: Element.self) {
body(UnsafeBufferPointer(start: $0.baseAddress, count: capacity))
}
}
}
@inlinable @inline(__always)
mutating func _update<R>(_ body: (UnsafeMutableBufferPointer<Element>) -> R) -> R {
var buffer = buffer
let result = withUnsafeMutableBytes(of: &buffer) { buffer in
buffer.withMemoryRebound(to: Element.self) {
body(UnsafeMutableBufferPointer(start: $0.baseAddress, count: capacity))
}
}
self.buffer = buffer
return result
}
@inlinable @inline(__always)
public subscript(index: Int) -> Element {
get {
_read { buffer in
buffer[index]
}
}
set {
guard index < capacity else { return }
_update{ buffer in
buffer[index] = newValue
}
}
}
@inlinable @inline(__always)
public mutating func bubbleSort(by comparer: (Element, Element) -> Bool) {
let count = count
_update { buffer in
for i in 0..<count {
for j in 1..<(count - i) {
if comparer(buffer[j], buffer[j - 1]) {
buffer.swapAt(j, j - 1)
}
}
}
}
}
@inlinable @inline(__always)
mutating func append(keyValue: Element) {
self[count] = keyValue
count += 1
}
@inlinable @inline(__always)
func prefix(_ upTo: Int) -> Self {
var result = Self()
for i in 0..<min(count, upTo) {
result.append(keyValue: self[i])
}
return result
}
@inlinable @inline(__always)
func prefix(_ upTo: Int, orderBy comparer: (Element,Element) -> Bool) -> Self {
var source = self
source.bubbleSort(by: comparer)
return source.prefix(2)
}
}
public protocol DictionaryStorage {
associatedtype Key: Equatable
associatedtype Value
associatedtype Buffer
static var bytes: Buffer { get }
}
/// とっても危険なので、よい子のみんなはまねしないように。
public struct StackOrHeapDictionay<Storage: DictionaryStorage> {
public typealias Key = Storage.Key
public typealias Value = Storage.Value
public typealias Element = (key: Key, value: Value)
public typealias Buffer = Storage.Buffer
public var buffer: Buffer
public var count: Int
@usableFromInline init() {
buffer = Storage.bytes
count = 0
}
@usableFromInline var inlineCount: Int { MemoryLayout<Buffer>.size }
@usableFromInline var capacity: Int { inlineCount / MemoryLayout<Element>.stride }
public var first: Element? { count == 0 ? nil : self[raw: 0] }
@inlinable @inline(__always)
func _read<R>(_ body: (UnsafeBufferPointer<Element>) -> R) -> R {
withUnsafeBytes(of: buffer) { buffer in
buffer.withMemoryRebound(to: Element.self) {
body(UnsafeBufferPointer(start: $0.baseAddress, count: capacity))
}
}
}
@inlinable @inline(__always)
mutating func _update<R>(_ body: (UnsafeMutableBufferPointer<Element>) -> R) -> R {
var buffer = buffer
let result = withUnsafeMutableBytes(of: &buffer) { buffer in
buffer.withMemoryRebound(to: Element.self) {
body(UnsafeMutableBufferPointer(start: $0.baseAddress, count: capacity))
}
}
self.buffer = buffer
return result
}
@inlinable @inline(__always)
public subscript(raw index: Int) -> Element {
get {
_read { buffer in
buffer[index]
}
}
set {
guard index < capacity else { return }
_update{ buffer in
buffer[index] = newValue
}
}
}
@inlinable @inline(__always)
public mutating func bubbleSort(by comparer: (Element, Element) -> Bool) {
let count = count
_update { buffer in
for i in 0..<count {
for j in 1..<(count - i) {
if comparer(buffer[j], buffer[j - 1]) {
buffer.swapAt(j, j - 1)
}
}
}
}
}
@inlinable @inline(__always)
mutating func append(keyValue: Element) {
self[raw: count] = keyValue
count += 1
}
@inlinable @inline(__always)
static func index(buffer: UnsafeBufferPointer<Element>, count: Int, of k: Key) -> Int? {
for i in 0..<count {
if buffer[i].key == k {
return i
}
}
return nil
}
@inlinable @inline(__always)
static func index(buffer: UnsafeMutableBufferPointer<Element>, count: Int, of k: Key) -> Int? {
for i in 0..<count {
if buffer[i].key == k {
return i
}
}
return nil
}
@inlinable subscript(key: Key) -> Value? {
@inline(__always) get {
_read {
guard let i = Self.index(buffer: $0, count: count, of: key)
else { return nil }
return $0[i].value
}
}
@inline(__always) set {
if let newValue {
let count = count
let inserted: Bool = _update {
guard let i = Self.index(buffer: $0, count: count, of: key)
else { return false }
$0[i].value = newValue
return true
}
if inserted {
return
}
append(keyValue: (key: key, value: newValue))
} else {
/* remove */
}
}
}
@inlinable subscript(key: Key, default value: Value) -> Value {
@inline(__always) get { self[key] ?? value }
@inline(__always) set { self[key] = newValue }
}
@inlinable @inline(__always)
func prefix(_ upTo: Int) -> Self {
var result = Self()
for i in 0..<min(count, upTo) {
result.append(keyValue: self[raw: i])
}
return result
}
@inlinable @inline(__always)
func prefix(_ upTo: Int, orderBy comparer: (Element,Element) -> Bool) -> Self {
var source = self
source.bubbleSort(by: comparer)
return source.prefix(2)
}
@inlinable @inline(__always)
func merging(_ other: Self) -> Self where Value: AdditiveArithmetic {
var result = self
other._read { rhs in
for i in 0..<other.count {
result[rhs[i].key, default: .zero] += rhs[i].value
}
}
assert(result.count <= count + other.count)
return result
}
}
extension StackOrHeapDictionay: ExpressibleByDictionaryLiteral {
public init(dictionaryLiteral elements: (Key, Value)...) {
self.init()
elements.forEach {
self[$0.0] = $0.1
}
}
}
import Foundation
// MARK: - zip with
public func zip<A,B,C>(_ a: A,_ b: B, with f: (A.Element, B.Element) -> C) -> [C]
where A: Sequence, B: Sequence {
var result = [C]()
var (it0, it1) = (a.makeIterator(), b.makeIterator())
while let x = it0.next(), let y = it1.next() {
result.append(f(x,y))
}
return result
}
public func zip<A,B,C,D>(_ a: A,_ b: B,_ c: C, with f: (A.Element, B.Element, C.Element) -> D) -> [D]
where A: Sequence, B: Sequence, C: Sequence {
var result = [D]()
var it0 = a.makeIterator()
var it1 = b.makeIterator()
var it2 = c.makeIterator()
while
let x = it0.next(),
let y = it1.next(),
let z = it2.next()
{
result.append(f(x,y,z))
}
return result
}
public func zip<A,B,C,D,E>(_ a: A,_ b: B,_ c: C,_ d: D, with f: (A.Element, B.Element, C.Element, D.Element) -> E) -> [E]
where A: Sequence, B: Sequence, C: Sequence, D: Sequence {
var result = [E]()
var it0 = a.makeIterator()
var it1 = b.makeIterator()
var it2 = c.makeIterator()
var it3 = d.makeIterator()
while
let x = it0.next(),
let y = it1.next(),
let z = it2.next(),
let w = it3.next()
{
result.append(f(x,y,z,w))
}
return result
}
extension Array where Element: IteratorProtocol {
fileprivate mutating func next() -> [Element.Element]? {
indices
.map { self[$0].next() }
.reduce([]) { partial, item in
guard let partial, let item else { return nil }
return partial + [item]
}
}
}
extension Sequence where Element: Sequence {
public func transposed() -> [[Element.Element]] {
var result: [[Element.Element]] = []
var iterators = map{ $0.makeIterator() }
while let n = iterators.next() {
result.append(n)
}
return result
}
}
import Foundation
@inlinable
public func fold<A,B>(initial: A,_ f: (A,B) -> A,_ rest: B...) -> A {
var result = initial
for value in rest {
result = f(result, value)
}
return result
}
extension SIMD {
func reduce<T>(initial: T,_ f: (T, Scalar) -> T) -> T {
var result = initial
for index in 0 ..< Self.scalarCount {
result = f(result, self[index])
}
return result
}
}
import Foundation
// MARK: - Range Convinience
infix operator ..<=: RangeFormationPrecedence
public func ..<= <Bound: Comparable>(lhs: Bound, rhs: Bound) -> StrideThrough<Bound> {
stride(from: lhs, through: rhs, by: 1)
}
infix operator ..>=: RangeFormationPrecedence
public func ..>= <Bound: Comparable>(lhs: Bound, rhs: Bound) -> StrideThrough<Bound> {
stride(from: lhs, through: rhs, by: -1)
}
infix operator ..>: RangeFormationPrecedence
public func ..> <Bound: Comparable>(lhs: Bound, rhs: Bound) -> StrideTo<Bound> {
stride(from: lhs, to: rhs, by: -1)
}
import Foundation
struct SIMD4<Scalar: SIMDScalar> {
init(x: Scalar, y: Scalar, z: Scalar, w: Scalar) {
self.x = x
self.y = y
self.z = z
self.w = w
}
init(_ x: Scalar,_ y: Scalar,_ z: Scalar,_ w: Scalar) {
self.x = x
self.y = y
self.z = z
self.w = w
}
var x: Scalar
var y: Scalar
var z: Scalar
var w: Scalar
}
extension SIMD4: Codable where Scalar: SIMDScalar { }
extension SIMD4: SIMDStorage where Scalar: SIMDScalar & AdditiveArithmetic {
init() { x = .zero; y = .zero; z = .zero; w = .zero }
}
extension SIMD4: SIMD where Scalar: SIMDScalar & AdditiveArithmetic {
typealias MaskStorage = SIMD4<Scalar.SIMDMaskScalar>
subscript(index: Int) -> Scalar {
get {
switch index {
case 0: return x
case 1: return y
case 2: return z
case 3: return w
default: fatalError()
}
}
set(newValue) {
switch index {
case 0: x = newValue
case 1: y = newValue
case 2: z = newValue
case 3: w = newValue
default: fatalError()
}
}
}
var scalarCount: Int { 4 }
}
extension SIMD4: Equatable where Scalar: Equatable { }
extension SIMD4: Hashable where Scalar: Hashable { }
extension SIMD4: ExpressibleByArrayLiteral {
init(arrayLiteral elements: Scalar...) {
(x,y,z,w) = (elements[0], elements[1], elements[2], elements[3])
}
}
extension SIMD4: CustomStringConvertible {
var description: String { [x,y,z,w].description }
}
import Foundation
// MARK: - Integer
func floor(_ n: Int,_ d: Int) -> Int { (n - (n % d + d) % d) / d }
func ceil(_ n: Int,_ d: Int) -> Int { (n + (d - n % d) % d) / d }
func mod(_ n: Int,_ d: Int) -> Int { n < 0 ? n % d + d : n % d }
func lcm(_ a: Int,_ b: Int) -> Int { a / gcd(a,b) * b }
func gcd(_ a: Int,_ b: Int) -> Int {
var (a,b) = (a,b)
while a >= 1, b >= 1 {
if a > b {
a %= b
} else {
b %= a
}
}
return a != 0 ? a : b
}
func factorial(_ n: Int) -> Int {
if n <= 1 {
return 1
} else {
return n * factorial(n - 1)
}
}
import Foundation
import Algorithms
// MARK: - Vector
struct SIMD2<Scalar: SIMDScalar> {
var x,y: Scalar
init(x: Scalar, y: Scalar) { self.x = x; self.y = y }
init(_ x: Scalar,_ y: Scalar) { self.x = x; self.y = y }
init(_ v: [Scalar]) { (x,y) = (v[0], v[1]) }
}
extension SIMD2: ExpressibleByArrayLiteral {
init(arrayLiteral elements: Scalar...) {
(x,y) = (elements[0], elements[1])
}
}
extension SIMD2: Codable where Scalar: SIMDScalar { }
extension SIMD2: SIMDStorage where Scalar: SIMDScalar & AdditiveArithmetic {
init() { x = .zero; y = .zero }
}
extension SIMD2: SIMD where Scalar: SIMDScalar & AdditiveArithmetic {
typealias MaskStorage = SIMD2<Scalar.SIMDMaskScalar>
subscript(index: Int) -> Scalar {
get {
index == 0 ? x : y
}
set(newValue) {
x = index == 0 ? newValue : x
y = index != 0 ? newValue : y
}
}
var scalarCount: Int { 2 }
}
extension SIMD2: Equatable where Scalar: Equatable { }
extension SIMD2: Hashable where Scalar: Hashable { }
extension SIMD2: CustomStringConvertible {
var description: String { [x,y].description }
}
extension SIMD2 where Scalar: FixedWidthInteger {
func sum() -> Scalar { x + y }
}
func dot<Scalar>(_ lhs: SIMD2<Scalar>,_ rhs: SIMD2<Scalar>) -> Scalar where Scalar: FixedWidthInteger {
(lhs &* rhs).sum()
}
func dot<Scalar>(_ lhs: SIMD2<Scalar>,_ rhs: SIMD2<Scalar>) -> Scalar where Scalar: FloatingPoint {
(lhs * rhs).sum()
}
func length_squared<Scalar>(_ rhs: SIMD2<Scalar>) -> Scalar where Scalar: FixedWidthInteger {
dot(rhs, rhs)
}
func length_squared<Scalar>(_ rhs: SIMD2<Scalar>) -> Scalar where Scalar: FloatingPoint {
dot(rhs, rhs)
}
func distance_squared<Scalar>(_ lhs: SIMD2<Scalar>,_ rhs: SIMD2<Scalar>) -> Scalar where Scalar: FixedWidthInteger {
length_squared(lhs &- rhs)
}
func distance_squared<Scalar>(_ lhs: SIMD2<Scalar>,_ rhs: SIMD2<Scalar>) -> Scalar where Scalar: FloatingPoint {
length_squared(lhs - rhs)
}
func triangle_area<Scalar>(_ a: SIMD2<Scalar>,_ b: SIMD2<Scalar>,_ c: SIMD2<Scalar>) -> Scalar where Scalar: Numeric {
(b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y)
}
func min<T: Comparable>(_ a: SIMD2<T>,_ b: SIMD2<T>) -> SIMD2<T> {
.init(min(a.x, b.x), min(a.y, b.y))
}
func max<T: Comparable>(_ a: SIMD2<T>,_ b: SIMD2<T>) -> SIMD2<T> {
.init(max(a.x, b.x), max(a.y, b.y))
}
extension SIMD2 where Scalar == Int {
// Z-UP 右ネジ
static var rotate90: [Self] { [[0,-1],[1,0]] }
static var rotate180: [Self] { [[-1,0],[0,-1]] }
static var rotate270: [Self] { [[0,1],[-1,0]] }
}
func mul<Scalar>(_ m: [[Scalar]],_ v: SIMD2<Scalar>) -> SIMD2<Scalar> where Scalar: FixedWidthInteger {
// 行列がcolumn-majorなのかrow-majorなのか、いまいちわかっていない。
// たまたまあってるレベル
[(SIMD2(m[0]) &* v).sum(), (SIMD2(m[1]) &* v).sum()]
}
func &* <Component>(lhs: [[Component]], rhs: SIMD2<Component>) -> SIMD2<Component> where Component: FixedWidthInteger {
mul(lhs, rhs)
}
func product(origin o: SIMD2<Int>, size s: SIMD2<Int>) -> [SIMD2<Int>] {
product(o.x..<(o.x + s.x), o.y..<(o.y + s.y)).map { SIMD2<Int>(x: $0.0, y: $0.1) }
}
typealias VInt2 = SIMD2<Int>
extension SIMD2 {
func reversed() -> Self { .init(y, x) }
}
func manhattanDistance<T>(_ lhs: SIMD2<T>,_ rhs: SIMD2<T>) -> T where T : SignedNumeric, T : Comparable {
(0 ..< SIMD2<Int>.scalarCount).reduce(0) { $0 + abs(lhs[$1] - rhs[$1]) }
}
import Foundation
// MARK: - Priority Queue
public struct PriorityQueue<Element: Comparable> {
@usableFromInline var elements: [Element] = []
}
public extension PriorityQueue {
init<S>(_ elements: S) where S: Sequence, S.Element == Element {
self.init(elements: elements.map{ $0 })
}
}
extension PriorityQueue {
@inlinable @inline(__always)
mutating func __update<R>(_ body: (BinaryHeapUnsafeHandle<Element>) -> R) -> R {
elements.__update_binary_heap(<, body)
}
}
public extension PriorityQueue {
mutating func insert(_ element:Element) {
elements.append(element)
__update { $0.push_heap($0.endIndex) }
}
@discardableResult
mutating func popMin() -> Element? {
guard !elements.isEmpty else { return nil }
__update { $0.pop_heap($0.endIndex) }
return elements.removeLast()
}
var isEmpty: Bool { elements.isEmpty }
var first: Element? { elements.first }
var count: Int { elements.count }
}
import Foundation
// MARK: - ReadHelper
typealias Int2 = (Int,Int)
typealias Int3 = (Int,Int,Int)
typealias Int4 = (Int,Int,Int,Int)
typealias Int5 = (Int,Int,Int,Int,Int)
typealias Int6 = (Int,Int,Int,Int,Int,Int)
public enum Input { }
public extension Input {
@inlinable @inline(__always)
static func read<A>() -> A! where A: SingleRead {
.read()
}
static func read<A,B>() -> (A,B)!
where A: TupleRead, B: TupleRead
{
(.read(), .read())
}
static func read<A,B,C>() -> (A,B,C)!
where A: TupleRead, B: TupleRead, C: TupleRead
{
(.read(), .read(), .read())
}
static func read<A,B,C,D>() -> (A,B,C,D)!
where A: TupleRead, B: TupleRead, C: TupleRead, D: TupleRead
{
(.read(), .read(), .read(), .read())
}
static func read<A,B,C,D,E>() -> (A,B,C,D,E)!
where A: TupleRead, B: TupleRead, C: TupleRead, D: TupleRead, E: TupleRead
{
(.read(), .read(), .read(), .read(), .read())
}
static func read<A,B,C,D,E,F>() -> (A,B,C,D,E,F)!
where A: TupleRead, B: TupleRead, C: TupleRead, D: TupleRead, E: TupleRead, F: TupleRead
{
(.read(), .read(), .read(), .read(), .read(), .read())
}
}
extension Array where Element: RawRepresentable, Element.RawValue == UInt8 {
static func read(columns: Int) -> [Element] {
[UInt8].read(columns: columns)
.compactMap(Element.init)
}
}
extension Array where Element: Sequence, Element.Element: RawRepresentable, Element.Element.RawValue == UInt8 {
static func read(rows: Int, columns: Int) -> [[Element.Element]] {
[[UInt8]].read(rows: rows, columns: columns)
.map {
$0.compactMap(Element.Element.init)
}
}
}
import Foundation
// MARK: - Char Convinience
typealias Char = UInt8
extension UInt8: ExpressibleByStringLiteral {
@inlinable
public init(stringLiteral value: String) {
self = value.utf8.first!
}
}
extension UInt8 {
var character: Character { Character(UnicodeScalar(self)) }
var char: Character { character }
func lowercased() -> Self {
guard
self >= 65,
self <= 90
else {
return self
}
return self + 32
}
func uppercased() -> Self {
guard
self >= 97,
self <= 122
else {
return self
}
return self - 32
}
}
extension Sequence where Element == UInt8 {
func joined() -> String { String(bytes: self, encoding: .ascii)! }
var characters: [Character] { map(\.character) }
}
extension String {
init<S>(ascii: S) where S: Sequence, S.Element == UInt8 {
self = ascii.joined()
}
var asciiValues: [UInt8] { compactMap(\.asciiValue) }
}
// MARK: - Character Convinience
extension Character: Strideable {
public func distance(to other: Character) -> Int {
Int(other.asciiValue!) - Int(asciiValue!)
}
public func advanced(by n: Int) -> Character {
Character(UnicodeScalar(UInt8(Int(asciiValue!) + n)))
}
}
extension Character {
var integerValue: Int { Character("0").distance(to: self) }
}
extension Sequence where Element == Character {
func joined() -> String { String(self) }
var asciiValues: [UInt8] { compactMap(\.asciiValue) }
}
extension String {
var characters: [Character] { map{ $0 } }
}
import Foundation
// MARK: - Binary Search
extension Range where Bound == Int {
@inlinable
func left(_ lowerThan: (Bound) -> Bool) -> Bound {
var (left, right) = (startIndex, endIndex)
while left < right {
let mid = (left + right) >> 1
if lowerThan(mid) {
left = mid + 1
} else {
right = mid
}
}
return left
}
@inlinable
func right(_ greaterThan: (Bound) -> Bool) -> Bound {
var (left, right) = (startIndex, endIndex)
while left < right {
let mid = (left + right) >> 1
if greaterThan(mid) {
right = mid
} else {
left = mid + 1
}
}
return left
}
}
extension Range {
@inlinable
func left<Item>(_ x: Item,_ item: (Element) -> Item) -> Element where Item: Comparable, Bound: BinaryInteger {
var (left, right) = (startIndex, endIndex)
while left < right {
let mid = (left + right) >> 1
if item(mid) < x {
left = mid + 1
} else {
right = mid
}
}
return left
}
@inlinable
func right<Item>(_ x: Item,_ item: (Element) -> Item) -> Element where Item: Comparable, Bound: BinaryInteger {
var (left, right) = (startIndex, endIndex)
while left < right {
let mid = (left + right) >> 1
if x < item(mid) {
right = mid
} else {
left = mid + 1
}
}
return left
}
}
extension Collection where Index == Int {
@inlinable
func left(_ lowerThan: (Element) -> Bool) -> Index {
var (left, right) = (startIndex, endIndex)
while left < right {
let mid = (left + right) >> 1
if lowerThan(self[mid]) {
left = mid + 1
} else {
right = mid
}
}
return left
}
@inlinable
func right(_ greaterThan: (Element) -> Bool) -> Index {
var (left, right) = (startIndex, endIndex)
while left < right {
let mid = (left + right) >> 1
if greaterThan(self[mid]) {
right = mid
} else {
left = mid + 1
}
}
return left
}
@inlinable
func right(_ x: Element, start left: Index, end right: Index) -> Index where Element: Comparable {
var (left, right) = (left, right)
while left < right {
let mid = (left + right) >> 1
if x < self[mid] {
right = mid
} else {
left = mid + 1
}
}
return left
}
@inlinable
func right<T>(_ x: T, start left: Index, end right: Index,_ key: (Element) -> T) -> Index where T: Comparable {
var (left, right) = (startIndex, endIndex)
while left < right {
let mid = (left + right) >> 1
if x < key(self[mid]) {
right = mid
} else {
left = mid + 1
}
}
return left
}
@inlinable
func left(_ x: Element, start left: Index, end right: Index) -> Index where Element: Comparable {
var (left, right) = (left, right)
while left < right {
let mid = (left + right) >> 1
if self[mid] < x {
left = mid + 1
} else {
right = mid
}
}
return left
}
@inlinable
func left<T>(_ x: T, start left: Index, end right: Index,_ key: (Element) -> T) -> Index where T: Comparable {
var (left, right) = (left, right)
while left < right {
let mid = (left + right) >> 1
if key(self[mid]) < x {
left = mid + 1
} else {
right = mid
}
}
return left
}
}
extension Collection where Index == Int, Element: Comparable {
@inlinable
func right(_ x: Element) -> Index { right(x, start: startIndex, end: endIndex) }
@inlinable
func left(_ x: Element) -> Index { left(x, start: startIndex, end: endIndex) }
}
import Foundation
import Algorithms
let INF: Int = 1 << 60
let MOD_998_244_353 = 998_244_353
let MOD_1_000_000_007 = 1_000_000_007
func Yes(_ b: Bool = true) -> String { b ? "Yes" : "No" }
func No(_ b: Bool = true) -> String { Yes(!b) }
func YES(_ b: Bool = true) -> String { b ? "YES" : "NO" }
func NO(_ b: Bool = true) -> String { YES(!b) }
func Takahashi(_ b: Bool = true) -> String { b ? "Takahashi" : "Aoki" }
func Aoki(_ b: Bool = true) -> String { Takahashi(!b) }
let snuke = "snuke"
// MARK: - Integer Convinience
precedencegroup PowerPrecedence {
lowerThan: BitwiseShiftPrecedence
higherThan: MultiplicationPrecedence
associativity: right
assignment: true
}
infix operator ** : PowerPrecedence
func ** <INT>(lhs: INT, rhs: Int) -> INT where INT: FixedWidthInteger {
repeatElement(lhs, count: rhs).product()
}
func ** (lhs: Int, rhs: Double) -> Int {
assert(-(1 << 53 - 1) <= lhs && lhs <= (1 << 53 - 1), "精度不足")
let result = Int(pow(Double(lhs), rhs))
assert(-(1 << 53 - 1) <= result && result <= (1 << 53 - 1), "精度不足")
return result
}
func ** (lhs: Double, rhs: Double) -> Double { pow(lhs, rhs) }
extension FixedWidthInteger {
var last: Self { self - 1 }
var range: Range<Self> { 0 ..< self }
var closedRange: ClosedRange<Self> { 0 ... self }
@discardableResult func rep<T>(_ f: () throws -> T) rethrows -> [T] { try (0..<self).map{ _ in try f() } }
@discardableResult func rep<T>(_ f: (Self) throws -> T) rethrows -> [T] { try (0..<self).map{ i in try f(i) } }
@discardableResult func rep<T>(_ f: (Self) throws -> [T]) rethrows -> [T] { try (0..<self).flatMap{ i in try f(i) } }
}
// MARK: - Bit Convinience
extension FixedWidthInteger {
subscript(position: Int) -> Bool {
get { self & (1 << position) != 0 }
mutating set {
if newValue {
self = self | ( 1 << position)
} else {
self = self & ~(1 << position)
}
}
}
}
// MARK: - Output Convinience
extension Sequence where Element: CustomStringConvertible {
func output() {
print(map(\.description).joined(separator: " "))
}
}
extension Collection where Element == Array<CChar> {
func print() { forEach { Swift.print(String(cString: $0 + [0])) } }
}
// MARK: - Array Init
extension Array {
static func * (lhs: Self, rhs: Int) -> Self {
repeatElement(lhs, count: rhs).flatMap{ $0 }
}
static func * (lhs: Self, rhs: (A:Int, B:Int)) -> [Self] {
[lhs * rhs.B] * rhs.A
}
static func * (lhs: Self, rhs: (A:Int, B:Int, C:Int)) -> [[Self]] {
[[lhs * rhs.C] * rhs.B] * rhs.A
}
static func * (lhs: Self, rhs: (A:Int, B:Int, C:Int, D:Int)) -> [[[Self]]] {
[[[lhs * rhs.D] * rhs.C] * rhs.B] * rhs.A
}
}
extension String {
static func * (lhs: Self, rhs: Int) -> Self {
repeatElement(lhs, count: rhs).joined()
}
static func * (lhs: Self, rhs: (A:Int, B:Int)) -> [Self] {
[lhs * rhs.B] * rhs.A
}
}
// MARK: - Array Convinience
extension Array {
// .suffix(...)が遅いため
@inlinable
public func _suffix(_ maxLength: Int) -> SubSequence {
let amount = Swift.max(0, count - maxLength)
let start = index(startIndex, offsetBy: amount, limitedBy: endIndex) ?? endIndex
return self[start..<endIndex]
}
}
extension Array where Element == Bool {
var all: Bool { reduce(true) { $0 && $1 } }
var any: Bool { contains(true) }
}
extension Sequence {
func count(where f: (Element) -> Bool) -> Int {
reduce(0) { $0 + (f($1) ? 1 : 0) }
}
func count(_ element: Element) -> Int where Element: Equatable {
reduce(0) { $0 + ($1 == element ? 1 : 0) }
}
}
extension Sequence where Element: AdditiveArithmetic {
func sum() -> Element { reduce(.zero, +) }
func acc() -> [Element] { reduce(into: [.zero]) { $0.append( ($0.last ?? .zero) + $1 ) } }
}
extension Sequence where Element: BinaryInteger {
func product() -> Element { reduce(1, *) }
func or() -> Element { reduce(0, |) }
func xor() -> Element { reduce(0, ^) }
}
extension Sequence where Element: BinaryFloatingPoint {
func product() -> Element { reduce(1, *) }
}
public extension Sequence
where Element: Sequence, Element.Element: AdditiveArithmetic {
func acc() -> [[Element.Element]] {
let tail = map{ $0.reductions(.zero,+) }.reductions{ zip($0,$1).map(+) }
let head = [.zero] * tail.first!.count as [Element.Element]
return [head] + tail
}
}
extension Collection where Element: AdditiveArithmetic {
func intervals() -> [Element] {
(0..<(distance(from: startIndex, to: endIndex) - 1)).map {
self[index(startIndex, offsetBy: $0 + 1)] - self[index(startIndex, offsetBy: $0)]
}
}
}
func product(origin o: (Int,Int), size s: (Int,Int)) -> Product2Sequence<Range<Int>,Range<Int>> {
product(o.0..<(o.0 + s.0), o.1..<(o.1 + s.1))
}
func product(origin o: SIMD2<Int>, size s: SIMD2<Int>) -> Product2Sequence<Range<Int>,Range<Int>> {
product(o.x..<(o.x + s.x), o.y..<(o.y + s.y))
}
extension Collection where Index == Int, Element: AdditiveArithmetic & Comparable {
// Maximum Subarray Problem
// kadanes algorithm
func maxSubarraySum() -> Element {
var maxSum = self[0]
var currentSum = self[0]
for num in self[1...] {
currentSum = Swift.max(num, currentSum + num)
maxSum = Swift.max(maxSum, currentSum)
}
return maxSum
}
}
extension Collection where Element: Equatable {
func isSubSequence(of other: Self) -> Bool {
var pos = other.startIndex
for s in self {
guard let p = other[pos..<other.endIndex].firstIndex(of: s) else {
return false
}
pos = other.index(after: p)
}
return true
}
}
extension SIMDMask {
var all: Bool {
for i in 0 ..< scalarCount {
if !self[i] {
return false
}
}
return true
}
var any: Bool {
for i in 0 ..< scalarCount {
if self[i] {
return true
}
}
return false
}
}
import Foundation
struct SIMD3<Scalar: SIMDScalar> {
init(x: Scalar, y: Scalar, z: Scalar) {
self.x = x
self.y = y
self.z = z
}
init(_ x: Scalar,_ y: Scalar,_ z: Scalar) {
self.x = x
self.y = y
self.z = z
}
var x: Scalar
var y: Scalar
var z: Scalar
}
extension SIMD3: Codable where Scalar: SIMDScalar { }
extension SIMD3: SIMDStorage where Scalar: SIMDScalar & AdditiveArithmetic {
init() { x = .zero; y = .zero; z = .zero }
}
extension SIMD3: SIMD where Scalar: SIMDScalar & AdditiveArithmetic {
typealias MaskStorage = SIMD3<Scalar.SIMDMaskScalar>
subscript(index: Int) -> Scalar {
get {
switch index {
case 0: return x
case 1: return y
case 2: return z
default: fatalError()
}
}
set(newValue) {
switch index {
case 0: x = newValue
case 1: y = newValue
case 2: z = newValue
default: fatalError()
}
}
}
var scalarCount: Int { 3 }
}
extension SIMD3: Equatable where Scalar: Equatable { }
extension SIMD3: Hashable where Scalar: Hashable { }
extension SIMD3: ExpressibleByArrayLiteral {
init(arrayLiteral elements: Scalar...) {
(x,y,z) = (elements[0], elements[1], elements[2])
}
}
extension SIMD3: CustomStringConvertible {
var description: String { [x,y,z].description }
}
extension SIMD3 where Scalar: FixedWidthInteger {
func sum() -> Scalar { x + y + z }
}
func dot<Scalar>(_ lhs: SIMD3<Scalar>,_ rhs: SIMD3<Scalar>) -> Scalar where Scalar: FixedWidthInteger {
(lhs &* rhs).sum()
}
func dot<Scalar>(_ lhs: SIMD3<Scalar>,_ rhs: SIMD3<Scalar>) -> Scalar where Scalar: FloatingPoint {
(lhs * rhs).sum()
}
func length_squared<Scalar>(_ rhs: SIMD3<Scalar>) -> Scalar where Scalar: FixedWidthInteger {
dot(rhs, rhs)
}
func length_squared<Scalar>(_ rhs: SIMD3<Scalar>) -> Scalar where Scalar: FloatingPoint {
dot(rhs, rhs)
}
func distance_squared<Scalar>(_ lhs: SIMD3<Scalar>,_ rhs: SIMD3<Scalar>) -> Scalar where Scalar: FixedWidthInteger {
length_squared(lhs &- rhs)
}
func distance_squared<Scalar>(_ lhs: SIMD3<Scalar>,_ rhs: SIMD3<Scalar>) -> Scalar where Scalar: FloatingPoint {
length_squared(lhs - rhs)
}
func min<T: Comparable>(_ a: SIMD3<T>,_ b: SIMD3<T>) -> SIMD3<T> {
.init(min(a.x, b.x), min(a.y, b.y), min(a.z, b.z))
}
func max<T: Comparable>(_ a: SIMD3<T>,_ b: SIMD3<T>) -> SIMD3<T> {
.init(max(a.x, b.x), max(a.y, b.y), max(a.z, b.z))
}
typealias VInt3 = SIMD3<Int>
// Copyright 2024 narumij
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
// This code is based on work originally distributed under the Apache License 2.0 with LLVM Exceptions:
//
// Copyright © 2003-2024 The LLVM Project.
// Licensed under the Apache License, Version 2.0 with LLVM Exceptions.
// The original license can be found at https://llvm.org/LICENSE.txt
//
// This Swift implementation includes modifications and adaptations made by narumij.
import Foundation
// 性能面で不利なはずのもの。
// 性能過敏な部分なので、しばらく保留
// テストでの利用を想定して切り出した
@usableFromInline
protocol ___RedBlackTreeNodePoolProtocol: MemberSetProtocol {
associatedtype Element
var ___destroy_node: _NodePtr { get nonmutating set }
var ___destroy_count: Int { get nonmutating set }
func ___initialize(_ :Element) -> _NodePtr
func ___element(_ p: _NodePtr, _: Element)
}
extension ___RedBlackTreeNodePoolProtocol {
/// O(1)
@inlinable
@inline(__always)
internal func ___pushDestroy(_ p: _NodePtr) {
__left_(p, ___destroy_node)
__right_(p, p)
__parent_(p, .nullptr)
__is_black_(p, false)
___destroy_node = p
___destroy_count += 1
}
/// O(1)
@inlinable
@inline(__always)
internal func ___popDetroy() -> _NodePtr {
let p = __right_(___destroy_node)
___destroy_node = __left_(p)
___destroy_count -= 1
return p
}
/// O(1)
@inlinable
internal func ___clearDestroy() {
___destroy_node = .nullptr
___destroy_count = 0
}
#if AC_COLLECTIONS_INTERNAL_CHECKS
/// O(*k*)
var ___destroyNodes: [_NodePtr] {
if ___destroy_node == .nullptr {
return []
}
var nodes: [_NodePtr] = [___destroy_node]
while let l = nodes.last, __left_(l) != .nullptr {
nodes.append(__left_(l))
}
return nodes
}
#endif
@inlinable
internal func ___recycle(_ k: Element) -> _NodePtr {
let p = ___popDetroy()
___element(p, k)
return p
}
@inlinable
internal func __construct_node(_ k: Element) -> _NodePtr {
___destroy_count > 0 ? ___recycle(k) : ___initialize(k)
}
@inlinable
func destroy(_ p: _NodePtr) {
___pushDestroy(p)
}
}
#if false
extension ___RedBlackTree.___Tree: ___RedBlackTreeNodePoolProtocol {
@usableFromInline
var ___destroy_node: _NodePtr {
get { _header.destroyNode }
_modify {
yield &_header.destroyNode
}
}
@usableFromInline
var ___destroy_count: Int {
get { _header.destroyCount }
_modify {
yield &_header.destroyCount
}
}
@usableFromInline
func ___initialize(_ k: Element) -> _NodePtr
{
assert(capacity - count >= 1)
let index = _header.initializedCount
(__node_ptr + index).initialize(to: Node(__value_: k))
_header.initializedCount += 1
assert(_header.initializedCount <= _header.capacity)
return index
}
}
#endif
// Copyright 2024 narumij
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
// This code is based on work originally distributed under the Apache License 2.0 with LLVM Exceptions:
//
// Copyright © 2003-2024 The LLVM Project.
// Licensed under the Apache License, Version 2.0 with LLVM Exceptions.
// The original license can be found at https://llvm.org/LICENSE.txt
//
// This Swift implementation includes modifications and adaptations made by narumij.
import Foundation
extension String {
@usableFromInline
static var invalidIndex: String {
"Attempting to access RedBlackTree elements using an invalid index"
}
@usableFromInline
static var outOfBounds: String {
"RedBlackTree index is out of Bound."
}
@usableFromInline
static var outOfRange: String {
"RedBlackTree index is out of range."
}
@usableFromInline
static var emptyFirst: String {
"Can't removeFirst from an empty RedBlackTree"
}
@usableFromInline
static var emptyLast: String {
"Can't removeLast from an empty RedBlackTree"
}
}
// メッセージをマッサージに空見するぐらい疲れている
// Copyright 2024 narumij
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
// This code is based on work originally distributed under the Apache License 2.0 with LLVM Exceptions:
//
// Copyright © 2003-2024 The LLVM Project.
// Licensed under the Apache License, Version 2.0 with LLVM Exceptions.
// The original license can be found at https://llvm.org/LICENSE.txt
//
// This Swift implementation includes modifications and adaptations made by narumij.
import Foundation
extension ___RedBlackTree.___Tree {
@frozen
@usableFromInline
struct ___MutablePointer {
@usableFromInline
let _storage: Storage
// __tree_max()を削るとO(1)動作となることが分かったので、
// 一旦それ以外の動作について削っている。
public var __parent: _NodePtr
public var __child: _NodeRef
// MARK: -
@inlinable
@inline(__always)
internal init(_storage: Tree.Storage) {
self._storage = _storage
(__parent, __child) = _storage.tree.___max_ref()
}
@inlinable
var _tree: Tree {
get { _storage.tree }
_modify { yield &_storage.tree }
}
@inlinable
public var pointee: Element {
get { _tree[_tree.__tree_max(_tree.__root())] }
set {
Tree.ensureUniqueAndCapacity(tree: &_tree)
(__parent, __child) = _tree.___emplace_hint_right(__parent, __child, newValue)
assert(_tree.__tree_invariant(_tree.__root()))
}
}
@inlinable
public mutating func ___next() {
// 未実装
}
@inlinable
public mutating func ___prev() {
// 未実装
}
}
}
// Copyright 2024 narumij
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
// This code is based on work originally distributed under the Apache License 2.0 with LLVM Exceptions:
//
// Copyright © 2003-2024 The LLVM Project.
// Licensed under the Apache License, Version 2.0 with LLVM Exceptions.
// The original license can be found at https://llvm.org/LICENSE.txt
//
// This Swift implementation includes modifications and adaptations made by narumij.
import Foundation
// 性能変化の反応が過敏なので、慎重さが必要っぽい。
// 単発削除対策型のイテレータ実装
@usableFromInline
protocol RedBlackTreeIteratorNextProtocol: IteratorProtocol {
associatedtype _Tree: MemberProtocol
var _tree: _Tree { get }
var _current: _NodePtr { get set }
var _next: _NodePtr { get set }
var _end: _NodePtr { get set }
}
extension RedBlackTreeIteratorNextProtocol {
@inlinable
@inline(__always)
internal mutating func _next() -> _NodePtr? {
guard _current != _end else { return nil }
defer {
_current = _next
_next = _next == _end ? _end : _tree.__tree_next(_next)
}
return _current
}
@inlinable
@inline(__always)
internal func _re_initialize(_ start: _NodePtr) -> (next: _NodePtr, nextnext: _NodePtr) {
(start == .end ? .end : _tree.__tree_next(start), _end)
}
}
#if false
// 同一値一括削除対策型のイテレータ実装
@usableFromInline
protocol RedBlackTreeIteratorNextProtocol2: IteratorProtocol {
associatedtype VC: ValueComparer
associatedtype _Tree: ___RedBlackTree.___Tree<VC>
var _tree: _Tree { get }
// 返却予定位置
var _current: _NodePtr { get set }
// 単発削除対策で、次の位置
var _next: _NodePtr { get set }
// 複数削除対策で、次の位置とは値が異なるさらに先の位置を指すもの
var _next_next: _NodePtr { get set }
// 終了位置
var _end: _NodePtr { get set }
}
extension ValueProtocol {
@inlinable
@inline(__always)
func ___value_equal(_ a: _Key, _ b: _Key) -> Bool {
!value_comp(a, b) && !value_comp(b, a)
}
}
extension RedBlackTreeIteratorNextProtocol2 {
// 性能低下する予想だったが、キャッシュの効きがいいのか、手元計測ではむしろ速い
@inlinable
@inline(__always)
internal mutating func _next() -> _NodePtr? {
guard _current != _end else { return nil }
defer {
// カレントをネクスト二つから選ぶ
_next = _next(_next, _next_next)
// 返却予定を更新
_current = _next
// 次を更新
_next = _next(_next)
// 次の予備を更新
_next_next = _next_next(_next)
}
return _current
}
@inlinable
@inline(__always)
internal func _next(_ _next: _NodePtr, _ _next_next: _NodePtr) -> _NodePtr {
_next != _end && _tree.___is_valid(_next) ? _next : _next_next
}
@inlinable
@inline(__always)
internal func _next(_ _next: _NodePtr) -> _NodePtr {
_next == _end ? _end : _tree.__tree_next(_next)
}
@inlinable
@inline(__always)
internal func _next_next(_ _next: _NodePtr) -> _NodePtr {
var _next_next = _next
// _nextと_next_nextの値が異なるところまで、_next_nextを進める
while _next_next != _end,
_tree.___value_equal(
_tree.__value_(_next),
_tree.__value_(_next_next))
{
_next_next = _tree.__tree_next(_next_next)
}
return _next_next
}
@inlinable
@inline(__always)
internal func _re_initialize(_ start: _NodePtr) -> (next: _NodePtr, nextnext: _NodePtr) {
let next = _next(start)
let nextnext = _next_next(start)
return (next, nextnext)
}
}
#endif
extension ___RedBlackTree.___Tree: Sequence {
@frozen
public struct Iterator: RedBlackTreeIteratorNextProtocol {
public typealias Element = Tree.Element
@inlinable
@inline(__always)
internal init(tree: Tree, start: _NodePtr, end: _NodePtr) {
self._tree = tree
self._current = start
self._end = end
self._next = start == .end ? .end : tree.__tree_next(start)
}
@usableFromInline
let _tree: Tree
@usableFromInline
var _current, _next, _end: _NodePtr
@inlinable
@inline(__always)
public mutating func next() -> Element? {
_next().map { _tree[$0] }
}
}
@inlinable
public __consuming func makeIterator() -> Iterator {
.init(tree: self, start: __begin_node, end: __end_node())
}
}
extension ___RedBlackTree.___Tree { // SubSequence不一致でBidirectionalCollectionには適合できない
@usableFromInline
var startIndex: _NodePtr {
__begin_node
}
@usableFromInline
var endIndex: _NodePtr {
__end_node()
}
@usableFromInline
typealias Index = _NodePtr
// この実装がないと、迷子になる
@inlinable
internal func distance(from start: Index, to end: Index) -> Int {
guard start == __end_node() || ___is_valid(start),
end == __end_node() || ___is_valid(end)
else {
fatalError(.invalidIndex)
}
return ___signed_distance(start, end)
}
@inlinable
@inline(__always)
internal func index(after i: Index) -> Index {
guard i != __end_node(), ___is_valid(i) else {
fatalError(.invalidIndex)
}
return __tree_next(i)
}
@inlinable
@inline(__always)
internal func formIndex(after i: inout Index) {
guard i != __end_node(), ___is_valid(i) else { fatalError(.invalidIndex) }
i = __tree_next(i)
}
@inlinable
@inline(__always)
internal func index(before i: Index) -> Index {
guard i != __begin_node, i == __end_node() || ___is_valid(i) else {
fatalError(.invalidIndex)
}
return __tree_prev_iter(i)
}
@inlinable
@inline(__always)
internal func formIndex(before i: inout Index) {
guard i == __end_node() || ___is_valid(i) else { fatalError(.invalidIndex) }
i = __tree_prev_iter(i)
}
@inlinable
@inline(__always)
internal func index(_ i: Index, offsetBy distance: Int) -> Index {
guard i == ___end() || ___is_valid(i) else { fatalError(.invalidIndex) }
var distance = distance
var i = i
while distance != 0 {
if 0 < distance {
guard i != __end_node() else {
fatalError(.outOfBounds)
}
i = index(after: i)
distance -= 1
} else {
guard i != __begin_node else {
fatalError(.outOfBounds)
}
i = index(before: i)
distance += 1
}
}
return i
}
@inlinable
@inline(__always)
internal func formIndex(_ i: inout Index, offsetBy distance: Int) {
guard i == __end_node() || ___is_valid(i) else { fatalError(.invalidIndex) }
i = index(i, offsetBy: distance)
}
@inlinable
@inline(__always)
internal func index(_ i: Index, offsetBy distance: Int, limitedBy limit: Index) -> Index? {
guard i == ___end() || ___is_valid(i) else { fatalError(.invalidIndex) }
var distance = distance
var i = i
while distance != 0 {
if i == limit {
return nil
}
if 0 < distance {
guard i != __end_node() else {
fatalError(.outOfBounds)
}
i = index(after: i)
distance -= 1
} else {
guard i != __begin_node else {
fatalError(.outOfBounds)
}
i = index(before: i)
distance += 1
}
}
return i
}
@inlinable
@inline(__always)
internal func formIndex(_ i: inout Index, offsetBy distance: Int, limitedBy limit: Index) -> Bool
{
guard i == __end_node() || ___is_valid(i) else { fatalError(.invalidIndex) }
if let ii = index(i, offsetBy: distance, limitedBy: limit) {
i = ii
return true
}
return false
}
}
// Copyright 2024 narumij
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
// This code is based on work originally distributed under the Apache License 2.0 with LLVM Exceptions:
//
// Copyright © 2003-2024 The LLVM Project.
// Licensed under the Apache License, Version 2.0 with LLVM Exceptions.
// The original license can be found at https://llvm.org/LICENSE.txt
//
// This Swift implementation includes modifications and adaptations made by narumij.
import Foundation
@usableFromInline
protocol RawPointerBuilderProtocol {}
extension RawPointerBuilderProtocol {
@usableFromInline
internal typealias Index = ___RedBlackTree.RawPointer
@inlinable
@inline(__always)
internal func ___index(_ p: _NodePtr) -> Index {
.init(p)
}
}
#if false
@usableFromInline
protocol TreePointerBuilderProtocol {
associatedtype VC: ValueComparer
var _tree: Tree { get }
}
extension TreePointerBuilderProtocol {
@usableFromInline
internal typealias Tree = ___RedBlackTree.___Tree<VC>
@usableFromInline
internal typealias Index = ___RedBlackTree.___Tree<VC>.Pointer
@inlinable
@inline(__always)
internal func ___index(_ p: _NodePtr) -> Index {
.init(__tree: _tree, pointer: p)
}
}
#endif
extension ___RedBlackTree.___Tree {
#if true
typealias EnumIndexMaker = RawPointerBuilderProtocol
public typealias EnumuratedIndex = ___RedBlackTree.RawPointer
#else
typealias EnumIndexMaker = TreePointerBuilderProtocol
public typealias EnumIndex = TreePointer
#endif
public typealias Enumerated = (offset: EnumuratedIndex, element: Element)
@frozen
public struct EnumIterator: RedBlackTreeIteratorNextProtocol, EnumIndexMaker {
@inlinable
@inline(__always)
internal init(tree: Tree, start: _NodePtr, end: _NodePtr) {
self._tree = tree
self._current = start
self._end = end
self._next = start == .end ? .end : tree.__tree_next(start)
}
@usableFromInline
let _tree: Tree
@usableFromInline
var _current, _next, _end: _NodePtr
@inlinable
@inline(__always)
public mutating func next() -> Enumerated? {
_next().map { (___index($0), _tree[$0]) }
}
}
}
extension ___RedBlackTree.___Tree {
// AnySequence用
@inlinable
__consuming func makeEnumIterator() -> EnumIterator {
.init(tree: self, start: __begin_node, end: __end_node())
}
@inlinable
__consuming func makeEnumeratedIterator(start: _NodePtr, end: _NodePtr) -> EnumIterator {
.init(tree: self, start: start, end: end)
}
}
extension ___RedBlackTree.___Tree {
@frozen
public struct EnumSequence: Sequence, EnumIndexMaker {
public typealias Element = Tree.Enumerated
@usableFromInline
typealias Index = _NodePtr
@inlinable
init(tree: Tree, start: Index, end: Index) {
self._tree = tree
self.startIndex = start
self.endIndex = end
}
@usableFromInline
let _tree: Tree
@usableFromInline
var startIndex: Index
@usableFromInline
var endIndex: Index
@inlinable
public __consuming func makeIterator() -> EnumIterator {
_tree.makeEnumeratedIterator(start: startIndex, end: endIndex)
}
}
}
extension ___RedBlackTree.___Tree {
@inlinable
internal func enumeratedSubsequence() -> EnumSequence {
.init(tree: self, start: __begin_node, end: __end_node())
}
@inlinable
internal func enumeratedSubsequence(from: _NodePtr, to: _NodePtr) -> EnumSequence {
.init(tree: self, start: from, end: to)
}
}
// Copyright 2024 narumij
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
// This code is based on work originally distributed under the Apache License 2.0 with LLVM Exceptions:
//
// Copyright © 2003-2024 The LLVM Project.
// Licensed under the Apache License, Version 2.0 with LLVM Exceptions.
// The original license can be found at https://llvm.org/LICENSE.txt
//
// This Swift implementation includes modifications and adaptations made by narumij.
import Foundation
extension ___RedBlackTree.___Tree {
@inlinable @inline(__always)
public func bitCeil(_ n: Int) -> Int {
n <= 1 ? 1 : 1 << (Int.bitWidth - (n - 1).leadingZeroBitCount)
}
@inlinable @inline(__always)
public func growthFormula(count: Int) -> Int {
// アロケーターにとって負担が軽そうな、2のべき付近を要求することにした。
// ヘッダー込みで確保するべきかどうかは、ManagedBufferのソースをみておらず不明。
// はみ出して大量に無駄にするよりはましなので、ヘッダー込みでサイズ計算することにしている。
let rawSize = bitCeil(MemoryLayout<Header>.stride + MemoryLayout<Node>.stride * count)
return (rawSize - MemoryLayout<Header>.stride) / MemoryLayout<Node>.stride
}
@inlinable
@inline(__always)
func growCapacity(to minimumCapacity: Int, linearly: Bool) -> Int {
if linearly {
return Swift.max(
_header.initializedCount,
minimumCapacity)
}
if minimumCapacity <= 4 {
return Swift.max(
_header.initializedCount,
minimumCapacity
)
}
if minimumCapacity <= 12 {
return Swift.max(
_header.initializedCount,
_header.capacity + (minimumCapacity - _header.capacity) * 2
)
}
// 手元の環境だと、サイズ24まではピタリのサイズを確保することができる
// 小さなサイズの成長を抑制すると、ABC385Dでの使用メモリが抑えられやすい
// 実行時間も抑制されやすいが、なぜなのかはまだ不明
// ABC385Dの場合、アロケータープールなんかで使いまわしが効きやすいからなのではと予想している。
return Swift.max(
_header.initializedCount,
growthFormula(count: minimumCapacity))
}
@inlinable
@inline(__always)
func copy() -> Tree {
copy(minimumCapacity: _header.initializedCount)
}
@inlinable
@inline(__always)
func copy(growthCapacityTo capacity: Int, linearly: Bool) -> Tree {
copy(
minimumCapacity:
growCapacity(to: capacity, linearly: linearly))
}
@inlinable
@inline(__always)
func copy(growthCapacityTo capacity: Int, limit: Int, linearly: Bool) -> Tree {
copy(
minimumCapacity:
Swift.min(
growCapacity(to: capacity, linearly: linearly),
limit))
}
}
extension ___RedBlackTree.___Tree {
@inlinable
@inline(__always)
static func _isKnownUniquelyReferenced(tree: inout Tree) -> Bool {
#if !DISABLE_COPY_ON_WRITE
isKnownUniquelyReferenced(&tree)
#else
true
#endif
}
@inlinable
@inline(__always)
static func ensureUniqueAndCapacity(tree: inout Tree) {
ensureUniqueAndCapacity(tree: &tree, minimumCapacity: tree._header.count + 1)
}
@inlinable
@inline(__always)
static func ensureUniqueAndCapacity(tree: inout Tree, minimumCapacity: Int) {
let shouldExpand = tree._header.capacity < minimumCapacity
if shouldExpand || !_isKnownUniquelyReferenced(tree: &tree) {
tree = tree.copy(growthCapacityTo: minimumCapacity, linearly: false)
}
}
@inlinable
@inline(__always)
static func ensureCapacity(tree: inout Tree) {
ensureCapacity(tree: &tree, minimumCapacity: tree._header.count + 1)
}
@inlinable
@inline(__always)
static func ensureCapacity(tree: inout Tree, minimumCapacity: Int) {
if tree._header.capacity < minimumCapacity {
tree = tree.copy(growthCapacityTo: minimumCapacity, linearly: false)
}
}
}
extension ___RedBlackTree.___Tree {
// コンテナに対するCoW責任をカバーする
// それ以外はTree側の保持の仕方で管理する
@_fixed_layout
@usableFromInline
final class Storage {
@nonobjc
@inlinable
@inline(__always)
init(__tree: Tree) {
tree = __tree
}
@nonobjc
@inlinable
@inline(__always)
init(minimumCapacity: Int) {
tree = .create(minimumCapacity: minimumCapacity)
}
@usableFromInline
typealias _Tree = Tree
@nonobjc
@usableFromInline
final var tree: Tree
@nonobjc
@inlinable
@inline(__always)
final var count: Int { tree.count }
@nonobjc
@inlinable
@inline(__always)
final var capacity: Int { tree.header.capacity }
@nonobjc
@inlinable
@inline(__always)
internal static func create(
withCapacity capacity: Int
) -> Storage {
return .init(minimumCapacity: capacity)
}
@nonobjc
@inlinable
@inline(__always)
final func copy() -> Storage {
.init(__tree: tree.copy())
}
@nonobjc
@inlinable
@inline(__always)
final func copy(growthCapacityTo capacity: Int,
linearly: Bool) -> Storage
{
.init(__tree: tree.copy(growthCapacityTo: capacity,
linearly: linearly))
}
@nonobjc
@inlinable
@inline(__always)
final func copy(growthCapacityTo capacity: Int,
limit: Int,
linearly: Bool) -> Storage
{
.init(__tree: tree.copy(growthCapacityTo: capacity,
limit: limit,
linearly: linearly))
}
@nonobjc
@inlinable
@inline(__always)
final func isKnownUniquelyReferenced_tree() -> Bool {
#if !DISABLE_COPY_ON_WRITE
isKnownUniquelyReferenced(&tree)
#else
true
#endif
}
}
}
@usableFromInline
protocol ___RedBlackTreeStorageLifetime: ValueComparer {
var _storage: Tree.Storage { get set }
}
extension ___RedBlackTreeStorageLifetime {
@inlinable
@inline(__always)
mutating func _isKnownUniquelyReferenced_LV1() -> Bool {
#if !DISABLE_COPY_ON_WRITE
isKnownUniquelyReferenced(&_storage)
#else
true
#endif
}
@inlinable
@inline(__always)
mutating func _isKnownUniquelyReferenced_LV2() -> Bool {
#if !DISABLE_COPY_ON_WRITE
if !_isKnownUniquelyReferenced_LV1() {
return false
}
if !_storage.isKnownUniquelyReferenced_tree() {
return false
}
#endif
return true
}
@inlinable
@inline(__always)
mutating func _ensureUnique() {
if !_isKnownUniquelyReferenced_LV1() {
_storage = _storage.copy()
}
}
@inlinable
@inline(__always)
mutating func _strongEnsureUnique() {
if !_isKnownUniquelyReferenced_LV2() {
_storage = _storage.copy()
}
}
@inlinable
@inline(__always)
mutating func _ensureUniqueAndCapacity() {
_ensureUniqueAndCapacity(to: _storage.count + 1)
assert(_storage.capacity > 0)
}
@inlinable
@inline(__always)
mutating func _ensureUniqueAndCapacity(to minimumCapacity: Int) {
let shouldExpand = _storage.capacity < minimumCapacity
if shouldExpand || !_isKnownUniquelyReferenced_LV1() {
_storage = _storage.copy(growthCapacityTo: minimumCapacity, linearly: false)
}
assert(_storage.capacity >= minimumCapacity)
assert(_storage.tree.header.initializedCount <= _storage.capacity)
}
@inlinable
@inline(__always)
mutating func _ensureUniqueAndCapacity(limit: Int, linearly: Bool = false) {
_ensureUniqueAndCapacity(to: _storage.count + 1, limit: limit, linearly: linearly)
assert(_storage.capacity > 0)
}
@inlinable
@inline(__always)
mutating func _ensureUniqueAndCapacity(to minimumCapacity: Int, limit: Int, linearly: Bool) {
let shouldExpand = _storage.capacity < minimumCapacity
if shouldExpand || !_isKnownUniquelyReferenced_LV1() {
_storage = _storage.copy(growthCapacityTo: minimumCapacity,
limit: limit,
linearly: false)
}
assert(_storage.capacity >= minimumCapacity)
assert(_storage.tree.header.initializedCount <= _storage.capacity)
}
@inlinable
@inline(__always)
mutating func _ensureCapacity() {
let minimumCapacity = _storage.count + 1
if _storage.capacity < minimumCapacity {
_storage = _storage.copy(growthCapacityTo: minimumCapacity,
linearly: false)
}
assert(_storage.capacity >= minimumCapacity)
assert(_storage.tree.header.initializedCount <= _storage.capacity)
}
@inlinable
@inline(__always)
mutating func _ensureCapacity(limit: Int, linearly: Bool = false) {
_ensureCapacity(to: _storage.count + 1, limit: limit, linearly: linearly)
}
@inlinable
@inline(__always)
mutating func _ensureCapacity(to minimumCapacity: Int, limit: Int, linearly: Bool) {
if _storage.capacity < minimumCapacity {
_storage = _storage.copy(growthCapacityTo: minimumCapacity,
limit: limit,
linearly: linearly)
}
assert(_storage.capacity >= minimumCapacity)
assert(_storage.tree.header.initializedCount <= _storage.capacity)
}
}
// Copyright 2024 narumij
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
// This code is based on work originally distributed under the Apache License 2.0 with LLVM Exceptions:
//
// Copyright © 2003-2024 The LLVM Project.
// Licensed under the Apache License, Version 2.0 with LLVM Exceptions.
// The original license can be found at https://llvm.org/LICENSE.txt
//
// This Swift implementation includes modifications and adaptations made by narumij.
import Foundation
extension ___RedBlackTree.___Tree {
@frozen
public struct SubSequence: Sequence {
public typealias Element = Tree.Element
public typealias Index = _NodePtr
@inlinable
init(___tree: Tree, start: Index, end: Index) {
self._tree = ___tree
self.startIndex = start
self.endIndex = end
}
@usableFromInline
let _tree: Tree
public
var startIndex: Index
public
var endIndex: Index
@inlinable
public __consuming func makeIterator() -> Iterator {
Iterator(tree: _tree, start: startIndex, end: endIndex)
}
@inlinable
@inline(__always)
internal var count: Int {
_tree.distance(from: startIndex, to: endIndex)
}
// 断念
// @inlinable
// public func lowerBound(_ member: Element) -> Index {
// base.__lower_bound(base.__key(member), base.__root(), endIndex)
// }
//
// @inlinable
// public func upperBound(_ member: Element) -> Index {
// base.__upper_bound(base.__key(member), base.__root(), endIndex)
// }
@inlinable
@inline(__always)
internal func forEach(_ body: (Element) throws -> Void) rethrows {
var __p = startIndex
while __p != endIndex {
let __c = __p
__p = _tree.__tree_next(__p)
try body(_tree[__c])
}
}
// この実装がないと、迷子になる
@inlinable
@inline(__always)
internal func distance(from start: Index, to end: Index) -> Int {
_tree.distance(from: start, to: end)
}
@inlinable
@inline(__always)
internal func index(after i: Index) -> Index {
// 標準のArrayが単純に加算することにならい、範囲チェックをしない
_tree.index(after: i)
}
@inlinable
@inline(__always)
internal func formIndex(after i: inout Index) {
// 標準のArrayが単純に加算することにならい、範囲チェックをしない
_tree.formIndex(after: &i)
}
@inlinable
@inline(__always)
internal func index(before i: Index) -> Index {
// 標準のArrayが単純に減算することにならい、範囲チェックをしない
_tree.index(before: i)
}
@inlinable
@inline(__always)
internal func formIndex(before i: inout Index) {
// 標準のArrayが単純に減算することにならい、範囲チェックをしない
_tree.formIndex(before: &i)
}
@inlinable
@inline(__always)
internal func index(_ i: Index, offsetBy distance: Int) -> Index {
// 標準のArrayが単純に加減算することにならい、範囲チェックをしない
_tree.index(i, offsetBy: distance)
}
@inlinable
@inline(__always)
internal func formIndex(_ i: inout Index, offsetBy distance: Int) {
// 標準のArrayが単純に加減算することにならい、範囲チェックをしない
_tree.formIndex(&i, offsetBy: distance)
}
@inlinable
@inline(__always)
internal func index(_ i: Index, offsetBy distance: Int, limitedBy limit: Index) -> Index? {
// 標準のArrayが単純に加減算することにならい、範囲チェックをしない
_tree.index(i, offsetBy: distance, limitedBy: limit)
}
@inlinable
@inline(__always)
internal func formIndex(_ i: inout Index, offsetBy distance: Int, limitedBy limit: Self.Index)
-> Bool
{
// 標準のArrayが単純に加減算することにならい、範囲チェックをしない
if let ii = index(i, offsetBy: distance, limitedBy: limit) {
i = ii
return true
}
return false
}
@inlinable
@inline(__always)
internal subscript(position: Index) -> Element {
guard _tree.___ptr_less_than_or_equal(startIndex, position),
_tree.___ptr_less_than(position, endIndex) else {
fatalError(.outOfRange)
}
return _tree[position]
}
@inlinable
@inline(__always)
internal subscript(bounds: Range<Pointer>) -> SubSequence {
guard _tree.___ptr_less_than_or_equal(startIndex, bounds.lowerBound.rawValue),
_tree.___ptr_less_than_or_equal(bounds.upperBound.rawValue, endIndex) else {
fatalError(.outOfRange)
}
return .init(
___tree: _tree,
start: bounds.lowerBound.rawValue,
end: bounds.upperBound.rawValue)
}
}
}
extension ___RedBlackTree.___Tree.SubSequence {
@inlinable
@inline(__always)
internal func ___is_valid_index(index i: _NodePtr) -> Bool {
guard i != .nullptr, _tree.___is_valid(i) else {
return false
}
return _tree.___ptr_closed_range_contains(startIndex, endIndex, i)
}
}
extension ___RedBlackTree.___Tree {
@inlinable
internal func subsequence(from: _NodePtr, to: _NodePtr) -> SubSequence {
.init(
___tree: self,
start: from,
end: to)
}
}
// Copyright 2024 narumij
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
// This code is based on work originally distributed under the Apache License 2.0 with LLVM Exceptions:
//
// Copyright © 2003-2024 The LLVM Project.
// Licensed under the Apache License, Version 2.0 with LLVM Exceptions.
// The original license can be found at https://llvm.org/LICENSE.txt
//
// This Swift implementation includes modifications and adaptations made by narumij.
import Foundation
extension ___RedBlackTree.___Tree {
/// Range<Bound>の左右のサイズ違いでクラッシュすることを避けるためのもの
@frozen
public struct Pointer: Comparable {
public typealias Element = Tree.Element
@usableFromInline
typealias _Tree = Tree
@usableFromInline
let _tree: Tree
@usableFromInline
var rawValue: Int
// MARK: -
public static func == (lhs: Self, rhs: Self) -> Bool {
// _tree比較は、CoWが発生した際に誤判定となり、邪魔となるので、省いている
lhs.rawValue == rhs.rawValue
}
public static func < (lhs: Self, rhs: Self) -> Bool {
// _tree比較は、CoWが発生した際に誤判定となり、邪魔となるので、省いている
lhs._tree.___ptr_comp(lhs.rawValue, rhs.rawValue)
}
// MARK: -
@inlinable
@inline(__always)
internal init(__tree: Tree, rawValue: _NodePtr) {
guard rawValue != .nullptr else {
preconditionFailure("_NodePtr is nullptr")
}
self._tree = __tree
self.rawValue = rawValue
}
// MARK: -
@inlinable
@inline(__always)
public var isValid: Bool {
if rawValue == .end { return true }
if !(0..<_tree.header.initializedCount ~= rawValue) { return false }
return _tree.___is_valid(rawValue)
}
/*
invalidなポインタでの削除は、だんまりがいいように思う
*/
}
}
extension ___RedBlackTree.___Tree.Pointer {
@inlinable
@inline(__always)
public var isStartIndex: Bool {
rawValue == _tree.__begin_node
}
@inlinable
@inline(__always)
internal static func end(_ tree: _Tree) -> Self {
.init(__tree: tree, rawValue: .end)
}
@inlinable
@inline(__always)
public var isEndIndex: Bool {
rawValue == .end
}
// 利用上価値はないが、おまけで。
@inlinable
@inline(__always)
public var isRootIndex: Bool {
rawValue == _tree.__root()
}
}
extension ___RedBlackTree.___Tree.Pointer {
// 名前について検討中
@inlinable
@inline(__always)
public var pointee: Element? {
guard !___is_null_or_end(rawValue), isValid else {
return nil
}
return ___pointee
}
// 名前はXMLNodeを参考にした
@inlinable
@inline(__always)
public var next: Self? {
guard !___is_null_or_end(rawValue), isValid else {
return nil
}
var next = self
next.___next()
return next
}
// 名前はXMLNodeを参考にした
@inlinable
@inline(__always)
public var previous: Self? {
guard rawValue != .nullptr, rawValue != _tree.begin(), isValid else {
return nil
}
var prev = self
prev.___prev()
return prev
}
// 名前はIntの同名を参考にした
@inlinable
@inline(__always)
public func advanced(by distance: Int) -> Self? {
var distance = distance
var result: Self? = self
while distance != 0 {
if 0 < distance {
result = result?.next
distance -= 1
} else {
result = result?.previous
distance += 1
}
}
return result
}
}
extension ___RedBlackTree.___Tree.Pointer {
@inlinable @inline(__always)
var ___pointee: Element {
_tree[rawValue]
}
@inlinable @inline(__always)
mutating func ___next() {
rawValue = _tree.__tree_next_iter(rawValue)
}
@inlinable @inline(__always)
mutating func ___prev() {
rawValue = _tree.__tree_prev_iter(rawValue)
}
}
#if DEBUG
fileprivate extension ___RedBlackTree.___Tree.Pointer {
init(_unsafe_tree: ___RedBlackTree.___Tree<VC>, rawValue: _NodePtr) {
self._tree = _unsafe_tree
self.rawValue = rawValue
}
}
extension ___RedBlackTree.___Tree.Pointer {
static func unsafe(tree: ___RedBlackTree.___Tree<VC>, rawValue: _NodePtr) -> Self {
rawValue == .end ? .end(tree) : .init(_unsafe_tree: tree, rawValue: rawValue)
}
}
#endif
// Copyright 2024 narumij
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
// This code is based on work originally distributed under the Apache License 2.0 with LLVM Exceptions:
//
// Copyright © 2003-2024 The LLVM Project.
// Licensed under the Apache License, Version 2.0 with LLVM Exceptions.
// The original license can be found at https://llvm.org/LICENSE.txt
//
// This Swift implementation includes modifications and adaptations made by narumij.
import Foundation
extension ___RedBlackTree {
/// enumerated()やindices()用のインデックス
///
/// nullptrはオプショナルで表現する想定で、nullptrを保持しない
public
enum RawPointer: Equatable
{
case node(_NodePtr)
case end
@usableFromInline
init(_ node: _NodePtr) {
guard node != .nullptr else {
preconditionFailure("_NodePtr is nullptr")
}
self = node == .end ? .end : .node(node)
}
@usableFromInline
var rawValue: _NodePtr {
switch self {
case .node(let _NodePtr):
return _NodePtr
case .end:
return .end
}
}
}
}
extension Optional where Wrapped == ___RedBlackTree.RawPointer {
@inlinable
init(_ ptr: _NodePtr) {
self = ptr == .nullptr ? .none : .some(___RedBlackTree.RawPointer(ptr))
}
@usableFromInline
var _pointer: _NodePtr {
switch self {
case .none:
return .nullptr
case .some(let ptr):
return ptr.rawValue
}
}
}
#if swift(>=5.5)
extension ___RedBlackTree.RawPointer: @unchecked Sendable {}
#endif
#if DEBUG
extension ___RedBlackTree.RawPointer {
static func unsafe(_ node: _NodePtr) -> Self {
node == .end ? .end : .node(node)
}
}
#endif
//
// ___RedBlackTree+Debug.swift
// swift-ac-collections
//
// Created by narumij on 2025/01/01.
//
import Foundation
#if GRAPHVIZ_DEBUG
extension ___RedBlackTree.___Tree {
/// グラフビズオブジェクトを生成します
func ___graphviz() -> Graphviz.Digraph {
buildGraphviz()
}
}
extension ___RedBlackTreeBase {
/// グラフビズオブジェクトを生成します
///
/// デバッガで、以下のようにすると、Graphvizのソースをコンソールに出力できます。
///
/// ```
/// p print(set.___graphviz())
/// ```
///
/// ```
/// digraph {
/// node [shape = circle style = filled fillcolor = red]; 1 4
/// node [shape = circle style = filled fillcolor = blue fontcolor = white]; begin stack
/// node [shape = circle style = filled fillcolor = black fontcolor = white];
/// end -> 2 [label = "left"]
/// begin -> 0 [label = "left"]
/// stack -> 1 [label = "left"]
/// 2 -> 0 [label = "left"]
/// 1 -> 1 [label = "right"]
/// 2 -> 3 [label = "right"]
/// 3 -> 4 [label = "right"]
/// }
/// ```
///
/// 上のソースは、以下のような操作をした直後のものです。
/// ```
/// var set = RedBlackTreeSet<Int>([0, 1, 2, 3, 4])
/// set.remove(1)
/// ```
///
public func ___graphviz() -> Graphviz.Digraph {
_tree.___graphviz()
}
}
#endif
#if GRAPHVIZ_DEBUG
enum Graphviz {}
extension Graphviz {
struct Digraph {
var options: [Option] = []
var nodes: [Node] = []
var edges: [Edge] = []
}
typealias Node = ([NodeProperty], [String])
enum Shape: String {
case circle
case note
}
enum Style: String {
case filled
}
enum Color: String {
case white
case black
case red
case blue
case lightYellow
}
enum LabelJust: String {
case l
case r
}
enum Port: String {
case n
case nw
case w
case sw
case s
case se
case e
case ne
case none
}
enum Spline: String {
case line
}
enum Option {
case splines(Spline)
}
enum NodeProperty {
case shape(Shape)
case style(Style)
case fillColor(Color)
case fontColor(Color)
case label(String)
case labelJust(LabelJust)
}
struct Edge {
var from: (String, Port)
var to: (String, Port)
var properties: [EdgeProperty]
}
enum EdgeProperty {
case label(String)
case labelAngle(Double)
}
}
extension Array where Element == Graphviz.NodeProperty {
static var red: [Graphviz.NodeProperty] {
[.shape(.circle), .style(.filled), .fillColor(.red)]
}
static var black: Self {
[.shape(.circle), .style(.filled), .fillColor(.black), .fontColor(.white)]
}
static var blue: Self {
[.shape(.circle), .style(.filled), .fillColor(.blue), .fontColor(.white)]
}
var description: String {
"[\(map(\.description).joined(separator: " "))]"
}
}
extension Array where Element == Graphviz.EdgeProperty {
static var left: [Graphviz.EdgeProperty] {
[.label("left"),.labelAngle(45)]
}
static var right: [Graphviz.EdgeProperty] {
[.label("right"),.labelAngle(-45)]
}
}
extension Graphviz.NodeProperty {
var description: String {
switch self {
case .shape(let shape):
return "shape = \(shape.rawValue)"
case .style(let style):
return "style = \(style.rawValue)"
case .fillColor(let color):
return "fillcolor = \(color.rawValue)"
case .fontColor(let color):
return "fontcolor = \(color.rawValue)"
case .label(let s):
return "label = \"\(s)\""
case .labelJust(let l):
return "labeljust = \(l)"
}
}
}
extension Graphviz.EdgeProperty {
var description: String {
switch self {
case .label(let label):
return "label = \"\(label)\""
case .labelAngle(let angle):
return "labelangle = \(angle)"
}
}
}
extension Graphviz.Option {
var description: String {
switch self {
case .splines(let s):
return "splines = \(s)"
}
}
}
extension Graphviz.Edge {
func node(_ p: (String, Graphviz.Port)) -> String {
if p.1 == .none {
return p.0
}
return "\(p.0):\(p.1)"
}
var description: String {
"\(node(from)) -> \(node(to)) [\(properties.map(\.description).joined(separator: " "))]"
}
}
extension Graphviz.Digraph: CustomStringConvertible {
var description: String {
func description(_ properties: [Graphviz.NodeProperty], _ nodes: [String]) -> String {
"node \(properties.description); \(nodes.joined(separator: " "))"
}
return
"""
digraph {
\(options.map(\.description).joined(separator: ";\n"))
\(nodes.map(description).joined(separator: "\n"))
\(edges.map(\.description).joined(separator: "\n"))
}
"""
}
}
extension ___RedBlackTree.___Tree {
func buildGraphviz() -> Graphviz.Digraph {
func isRed(_ i: Int) -> Bool {
!self[node: i].__is_black_
}
func isBlack(_ i: Int) -> Bool {
self[node: i].__is_black_
}
func hasLeft(_ i: Int) -> Bool {
self[node: i].__left_ != .nullptr
}
func hasRight(_ i: Int) -> Bool {
self[node: i].__right_ != .nullptr
}
func offset(_ i: Int) -> Int? {
switch i {
case .end:
return nil
case .nullptr:
return nil
default:
return i
}
}
func leftPair(_ i: Int) -> (Int, Int) {
(i, offset(self[node: i].__left_) ?? -1)
}
func rightPair(_ i: Int) -> (Int, Int) {
(i, offset(self[node: i].__right_) ?? -1)
}
func node(_ i: Int) -> String {
switch i {
case .end:
return "end"
default:
return "\(i)"
}
}
func nodeN(_ i: Int) -> String {
switch i {
case .nullptr:
return "-"
case .end:
return "end"
default:
return "#\(i)"
}
}
func nodeV(_ i: Int) -> String {
if i == .end {
return "end"
} else {
let c = String("\(self[i])".flatMap { $0 == "\n" ? ["\n", "n"] : [$0] })
// let l: String = "\\\"\(c)\\\"\\n#\(i)"
let l: String = "\(c)\\n\\n#\(i)"
return "\(i) [label = \"\(l)\"];"
}
}
func headerNote() -> [Graphviz.NodeProperty] {
// let h = "\(_header)"
// let l = "header\\n\(String(h.flatMap{ $0 == "\n" ? ["\\","n"] : [$0] }))"
var ll: [String] = []
ll.append(contentsOf: [
"[Header]",
"capacity: \(_header.capacity)",
"__left_: \(nodeN(_header.__left_))",
"__begin_node: \(nodeN(_header.__begin_node))",
"initializedCount: \(_header.initializedCount)",
"destroyCount: \(_header.destroyCount)",
"destroyNode: \(nodeN(_header.destroyNode))",
"[etc]",
"__tree_invariant: \(__tree_invariant(__root()))",
])
#if AC_COLLECTIONS_INTERNAL_CHECKS
ll.append("- copyCount: \(_header.copyCount)")
#endif
let l = ll.joined(separator: "\\n")
return [
.shape(.note),
.label(l),
.labelJust(.l),
.style(.filled),
.fillColor(.lightYellow),
.fontColor(.black),
]
}
let reds = (0..<header.initializedCount).filter(isRed).map(nodeV)
let blacks = (0..<header.initializedCount).filter(isBlack).map(nodeV)
let lefts: [(Int, Int)] = (0..<header.initializedCount).filter(hasLeft).map(leftPair)
let rights: [(Int, Int)] = (0..<header.initializedCount).filter(hasRight).map(rightPair)
var digraph = Graphviz.Digraph()
digraph.options.append(.splines(.line))
digraph.nodes.append((.red, reds))
digraph.nodes.append((.blue, ["begin", "stack", "end"]))
digraph.nodes.append((.black, blacks))
digraph.nodes.append((headerNote(), ["header"]))
if __root() != .nullptr {
digraph.edges.append(
.init(from: (node(.end), .sw), to: (node(__root()), .n), properties: .left))
}
if __begin_node != .nullptr {
digraph.edges.append(
.init(from: ("begin", .s), to: (node(__begin_node), .n), properties: .left))
}
if header.destroyNode != .nullptr {
digraph.edges.append(
.init(from: ("stack", .s), to: (node(header.destroyNode), .n), properties: .left))
}
digraph.edges.append(
contentsOf: lefts.map {
.init(from: (node($0), .sw), to: (node($1), .n), properties: .left)
})
digraph.edges.append(
contentsOf: rights.map {
.init(from: (node($0), .se), to: (node($1), .n), properties: .right)
})
return digraph
}
}
#endif
// Copyright 2024 narumij
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
// This code is based on work originally distributed under the Apache License 2.0 with LLVM Exceptions:
//
// Copyright © 2003-2024 The LLVM Project.
// Licensed under the Apache License, Version 2.0 with LLVM Exceptions.
// The original license can be found at https://llvm.org/LICENSE.txt
//
// This Swift implementation includes modifications and adaptations made by narumij.
import Foundation
extension ___RedBlackTree.___Tree {
@frozen
public struct IndexIterator: RawPointerBuilderProtocol, RedBlackTreeIteratorNextProtocol {
@inlinable
@inline(__always)
internal init(tree: Tree, start: _NodePtr, end: _NodePtr) {
self._tree = tree
self._current = start
self._end = end
self._next = start == .end ? .end : tree.__tree_next(start)
}
@usableFromInline
let _tree: Tree
@usableFromInline
var _current, _next, _end: _NodePtr
@inlinable
@inline(__always)
public mutating func next() -> RawPointer? {
_next().map { .init($0) }
}
}
}
extension ___RedBlackTree.___Tree {
@inlinable
__consuming func makeIndexIterator(start: _NodePtr, end: _NodePtr) -> IndexIterator {
.init(tree: self, start: start, end: end)
}
}
extension ___RedBlackTree.___Tree {
@frozen
public struct IndexSequence: Sequence {
public typealias Element = Tree.RawPointer
@usableFromInline
typealias Index = _NodePtr
@inlinable
init(tree: Tree, start: Index, end: Index) {
self._tree = tree
self.startIndex = start
self.endIndex = end
}
@usableFromInline
let _tree: Tree
@usableFromInline
var startIndex: Index
@usableFromInline
var endIndex: Index
@inlinable
public func makeIterator() -> IndexIterator {
_tree.makeIndexIterator(start: startIndex, end: endIndex)
}
@inlinable
@inline(__always)
internal func forEach(_ body: (Element) throws -> Void) rethrows {
var __p = startIndex
while __p != endIndex {
let __c = __p
__p = _tree.__tree_next(__p)
try body(.init(__c))
}
}
}
}
extension ___RedBlackTree.___Tree {
@inlinable
internal func indexSubsequence() -> IndexSequence {
.init(tree: self, start: __begin_node, end: __end_node())
}
@inlinable
internal func indexSubsequence(from: _NodePtr, to: _NodePtr) -> IndexSequence {
.init(tree: self, start: from, end: to)
}
}
// Copyright 2024 narumij
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
// This code is based on work originally distributed under the Apache License 2.0 with LLVM Exceptions:
//
// Copyright © 2003-2024 The LLVM Project.
// Licensed under the Apache License, Version 2.0 with LLVM Exceptions.
// The original license can be found at https://llvm.org/LICENSE.txt
//
// This Swift implementation includes modifications and adaptations made by narumij.
import Foundation
extension ___RedBlackTree {
public final class ___Tree<VC>: ManagedBuffer<
___RedBlackTree.___Tree<VC>.Header,
___RedBlackTree.___Tree<VC>.Node
>
where VC: ValueComparer {
@inlinable
deinit {
self.withUnsafeMutablePointers { header, elements in
elements.deinitialize(count: header.pointee.initializedCount)
header.deinitialize(count: 1)
}
}
}
}
extension ___RedBlackTree.___Tree {
@inlinable
internal static func create(
minimumCapacity capacity: Int
) -> Tree {
let storage = Tree.create(minimumCapacity: capacity) { managedBuffer in
Header(
capacity: managedBuffer.capacity,
__left_: .nullptr,
__begin_node: .end,
__initialized_count: 0,
__destroy_count: 0,
__destroy_node: .nullptr)
}
return unsafeDowncast(storage, to: Tree.self)
}
@inlinable
internal func copy(minimumCapacity: Int? = nil) -> Tree {
let capacity = minimumCapacity ?? self._header.capacity
let __left_ = self._header.__left_
let __begin_node = self._header.__begin_node
let __initialized_count = self._header.initializedCount
let __destroy_count = self._header.destroyCount
let __destroy_node = self._header.destroyNode
#if AC_COLLECTIONS_INTERNAL_CHECKS
let copyCount = self._header.copyCount
#endif
let newStorage = Tree.create(minimumCapacity: capacity)
newStorage._header.__left_ = __left_
newStorage._header.__begin_node = __begin_node
newStorage._header.initializedCount = __initialized_count
newStorage._header.destroyCount = __destroy_count
newStorage._header.destroyNode = __destroy_node
#if AC_COLLECTIONS_INTERNAL_CHECKS
newStorage._header.copyCount = copyCount &+ 1
#endif
self.withUnsafeMutablePointerToElements { oldNodes in
newStorage.withUnsafeMutablePointerToElements { newNodes in
newNodes.initialize(from: oldNodes, count: __initialized_count)
}
}
return newStorage
}
}
extension ___RedBlackTree.___Tree {
public struct Node: ___tree_base_node {
@usableFromInline
internal var __value_: Element
@usableFromInline
internal var __left_: _NodePtr
@usableFromInline
internal var __right_: _NodePtr
@usableFromInline
internal var __parent_: _NodePtr
@usableFromInline
internal var __is_black_: Bool
@inlinable
init(
__is_black_: Bool = false,
__left_: _NodePtr = .nullptr,
__right_: _NodePtr = .nullptr,
__parent_: _NodePtr = .nullptr,
__value_: Element
) {
self.__is_black_ = __is_black_
self.__left_ = __left_
self.__right_ = __right_
self.__parent_ = __parent_
self.__value_ = __value_
}
}
}
extension ___RedBlackTree.___Tree {
public
typealias Tree = ___RedBlackTree.___Tree<VC>
public
typealias RawPointer = ___RedBlackTree.RawPointer
@usableFromInline
internal typealias VC = VC
@usableFromInline
internal typealias Manager = ManagedBufferPointer<Header, Node>
}
extension ___RedBlackTree.___Tree {
public struct Header: ___tree_root_node {
@inlinable
init(
capacity: Int,
__left_: _NodePtr,
__begin_node: _NodePtr,
__initialized_count: Int,
__destroy_count: Int,
__destroy_node: _NodePtr
) {
self.capacity = capacity
self.__left_ = __left_
self.__begin_node = __begin_node
self.initializedCount = __initialized_count
self.destroyCount = __destroy_count
self.destroyNode = __destroy_node
}
@usableFromInline
internal var capacity: Int
@usableFromInline
internal var __left_: _NodePtr = .nullptr
@usableFromInline
internal var __begin_node: _NodePtr = .end
@usableFromInline
internal var initializedCount: Int
@usableFromInline
internal var destroyCount: Int
@usableFromInline
internal var destroyNode: _NodePtr = .end
#if AC_COLLECTIONS_INTERNAL_CHECKS
@usableFromInline
var copyCount: UInt = 0
#endif
}
}
extension ___RedBlackTree.___Tree.Header {
@inlinable
@inline(__always)
internal var count: Int {
initializedCount - destroyCount
}
@inlinable
@inline(__always)
internal mutating func clear() {
__begin_node = .end
__left_ = .nullptr
initializedCount = 0
}
}
extension ___RedBlackTree.___Tree {
@inlinable
internal var __header_ptr: UnsafeMutablePointer<Header> {
withUnsafeMutablePointerToHeader({ $0 })
}
@inlinable
internal var __node_ptr: UnsafeMutablePointer<Node> {
withUnsafeMutablePointerToElements({ $0 })
}
@inlinable
internal var _header: Header {
@inline(__always)
get { __header_ptr.pointee }
@inline(__always)
_modify { yield &__header_ptr.pointee }
}
@inlinable
internal subscript(_ pointer: _NodePtr) -> Element {
@inline(__always)
get {
assert(0 <= pointer && pointer < _header.initializedCount)
return __node_ptr[pointer].__value_
}
@inline(__always)
_modify {
assert(0 <= pointer && pointer < _header.initializedCount)
yield &__node_ptr[pointer].__value_
}
}
#if AC_COLLECTIONS_INTERNAL_CHECKS
@inlinable
internal var copyCount: UInt {
get { __header_ptr.pointee.copyCount }
set { __header_ptr.pointee.copyCount = newValue }
}
#endif
}
extension ___RedBlackTree.___Tree {
/// O(1)
@inlinable
@inline(__always)
internal func ___pushDestroy(_ p: _NodePtr) {
assert(_header.destroyNode != p)
assert(_header.initializedCount <= _header.capacity)
assert(_header.destroyCount <= _header.capacity)
assert(_header.destroyNode != p)
__node_ptr[p].__left_ = _header.destroyNode
__node_ptr[p].__right_ = p
__node_ptr[p].__parent_ = .nullptr
__node_ptr[p].__is_black_ = false
_header.destroyNode = p
_header.destroyCount += 1
}
/// O(1)
@inlinable
@inline(__always)
internal func ___popDetroy() -> _NodePtr {
assert(_header.destroyCount > 0)
let p = __node_ptr[_header.destroyNode].__right_
_header.destroyNode = __node_ptr[p].__left_
_header.destroyCount -= 1
return p
}
/// O(1)
@inlinable
internal func ___clearDestroy() {
_header.destroyNode = .nullptr
_header.destroyCount = 0
}
}
#if AC_COLLECTIONS_INTERNAL_CHECKS
extension ___RedBlackTree.___Tree {
/// O(*k*)
var ___destroyNodes: [_NodePtr] {
if _header.destroyNode == .nullptr {
return []
}
var nodes: [_NodePtr] = [_header.destroyNode]
while let l = nodes.last, __left_(l) != .nullptr {
nodes.append(__left_(l))
}
return nodes
}
}
#endif
extension ___RedBlackTree.___Tree {
@inlinable @inline(__always)
internal func ___is_valid(_ p: _NodePtr) -> Bool {
0..<_header.initializedCount ~= p && __node_ptr[p].__parent_ != .nullptr
}
}
extension ___RedBlackTree.___Tree {
@inlinable
internal func __construct_node(_ k: Element) -> _NodePtr {
if _header.destroyCount > 0 {
let p = ___popDetroy()
__node_ptr[p].__value_ = k
return p
}
assert(capacity - count >= 1)
let index = _header.initializedCount
(__node_ptr + index).initialize(to: Node(__value_: k))
_header.initializedCount += 1
assert(_header.initializedCount <= _header.capacity)
return index
}
@inlinable
internal func destroy(_ p: _NodePtr) {
___pushDestroy(p)
}
}
extension ___RedBlackTree.___Tree {
@inlinable
internal var count: Int {
__header_ptr.pointee.count
}
@inlinable
internal var size: Int {
get { __header_ptr.pointee.count }
set { /* NOP */ }
}
@inlinable
internal var __begin_node: _NodePtr {
get { __header_ptr.pointee.__begin_node }
_modify {
yield &__header_ptr.pointee.__begin_node
}
}
}
extension ___RedBlackTree.___Tree {
@inlinable @inline(__always)
internal func __value_(_ p: _NodePtr) -> _Key {
__key(__node_ptr[p].__value_)
}
}
extension ___RedBlackTree.___Tree {
public typealias Element = VC.Element
@usableFromInline
internal typealias _Key = VC._Key
@inlinable @inline(__always)
internal func value_comp(_ a: _Key, _ b: _Key) -> Bool {
VC.value_comp(a, b)
}
@inlinable @inline(__always)
internal func __key(_ e: VC.Element) -> VC._Key {
VC.__key(e)
}
@inlinable @inline(__always)
internal func ___element(_ p: _NodePtr) -> VC.Element {
__node_ptr[p].__value_
}
@inlinable @inline(__always)
internal func ___element(_ p: _NodePtr, _ __v: VC.Element) {
__node_ptr[p].__value_ = __v
}
}
extension ___RedBlackTree.___Tree: FindProtocol {}
extension ___RedBlackTree.___Tree: FindEqualProtocol {}
extension ___RedBlackTree.___Tree: FindLeafProtocol {}
extension ___RedBlackTree.___Tree: EqualProtocol {}
extension ___RedBlackTree.___Tree: InsertNodeAtProtocol {}
extension ___RedBlackTree.___Tree: InsertMultiProtocol {}
extension ___RedBlackTree.___Tree: InsertLastProtocol {}
extension ___RedBlackTree.___Tree: RemoveProtocol {}
extension ___RedBlackTree.___Tree: MergeProtocol {}
extension ___RedBlackTree.___Tree: HandleProtocol {}
extension ___RedBlackTree.___Tree: EraseProtocol {}
extension ___RedBlackTree.___Tree: EraseUniqueProtocol {}
extension ___RedBlackTree.___Tree: EraseMultiProtocol {}
extension ___RedBlackTree.___Tree: BoundProtocol {}
extension ___RedBlackTree.___Tree: InsertUniqueProtocol {}
extension ___RedBlackTree.___Tree: CountProtocol {}
extension ___RedBlackTree.___Tree: MemberProtocol {}
extension ___RedBlackTree.___Tree: DistanceProtocol {}
extension ___RedBlackTree.___Tree: CompareProtocol {}
extension ___RedBlackTree.___Tree: CompareMultiProtocol {}
extension ___RedBlackTree.___Tree {
@inlinable
@inline(__always)
internal func __parent_(_ p: _NodePtr) -> _NodePtr {
__node_ptr[p].__parent_
}
@inlinable
@inline(__always)
internal func __left_(_ p: _NodePtr) -> _NodePtr {
p == .end ? _header.__left_ : __node_ptr[p].__left_
}
@inlinable
@inline(__always)
internal func __right_(_ p: _NodePtr) -> _NodePtr {
__node_ptr[p].__right_
}
@inlinable
@inline(__always)
internal func __is_black_(_ p: _NodePtr) -> Bool {
__node_ptr[p].__is_black_
}
@inlinable
@inline(__always)
internal func __parent_unsafe(_ p: _NodePtr) -> _NodePtr {
__parent_(p)
}
}
extension ___RedBlackTree.___Tree {
@inlinable
@inline(__always)
internal func __is_black_(_ lhs: _NodePtr, _ rhs: Bool) {
__node_ptr[lhs].__is_black_ = rhs
}
@inlinable
@inline(__always)
internal func __parent_(_ lhs: _NodePtr, _ rhs: _NodePtr) {
__node_ptr[lhs].__parent_ = rhs
}
@inlinable
@inline(__always)
internal func __left_(_ lhs: _NodePtr, _ rhs: _NodePtr) {
if lhs == .end {
_header.__left_ = rhs
} else {
__node_ptr[lhs].__left_ = rhs
}
}
@inlinable
@inline(__always)
internal func __right_(_ lhs: _NodePtr, _ rhs: _NodePtr) {
__node_ptr[lhs].__right_ = rhs
}
}
extension ___RedBlackTree.___Tree {
@inlinable
@inline(__always)
internal func ___for_each(
__p: _NodePtr, __l: _NodePtr, body: (_NodePtr, inout Bool) throws -> Void
)
rethrows
{
var __p = __p
var cont = true
while cont, __p != __l {
let __c = __p
__p = __tree_next(__p)
try body(__c, &cont)
}
}
@inlinable
@inline(__always)
internal func ___for_each_(_ body: (Element) throws -> Void) rethrows {
try ___for_each_(__p: __begin_node, __l: __end_node(), body: body)
}
@inlinable
@inline(__always)
internal func ___for_each_(__p: _NodePtr, __l: _NodePtr, body: (Element) throws -> Void)
rethrows
{
var __p = __p
while __p != __l {
let __c = __p
__p = __tree_next(__p)
try body(self[__c])
}
}
}
extension ___RedBlackTree.___Tree {
@inlinable
internal func
___erase(_ __f: _NodePtr, _ __l: _NodePtr, _ action: (Element) throws -> Void) rethrows
{
var __f = __f
while __f != __l {
try action(self[__f])
__f = erase(__f)
}
}
@inlinable
internal func
___erase<Result>(
_ __f: _NodePtr, _ __l: _NodePtr, _ initialResult: Result,
_ nextPartialResult: (Result, Element) throws -> Result
) rethrows -> Result
{
var result = initialResult
var __f = __f
while __f != __l {
result = try nextPartialResult(result, self[__f])
__f = erase(__f)
}
return result
}
@inlinable
internal func
___erase<Result>(
_ __f: _NodePtr, _ __l: _NodePtr, into initialResult: Result,
_ updateAccumulatingResult: (inout Result, Element) throws -> Void
) rethrows -> Result
{
var result = initialResult
var __f = __f
while __f != __l {
try updateAccumulatingResult(&result, self[__f])
__f = erase(__f)
}
return result
}
}
extension ___RedBlackTree.___Tree {
/// O(1)
@inlinable
internal func __eraseAll() {
_header.clear()
___clearDestroy()
}
}
extension ___RedBlackTree.___Tree {
@inlinable @inline(__always)
internal var ___is_empty: Bool {
count == 0
}
@inlinable @inline(__always)
internal var ___capacity: Int {
_header.capacity
}
@inlinable @inline(__always)
internal func ___begin() -> _NodePtr {
_header.__begin_node
}
@inlinable @inline(__always)
internal func ___end() -> _NodePtr {
.end
}
}
extension ___RedBlackTree.___Tree {
@inlinable
internal func ___is_valid_index(_ i: _NodePtr) -> Bool {
if i == .nullptr { return false }
if i == .end { return true }
return ___is_valid(i)
}
}
extension ___RedBlackTree.___Tree {
@inlinable @inline(__always)
internal var ___sorted: [Element] {
var result = [Element]()
___for_each_ { member in
result.append(member)
}
return result
}
}
// Copyright 2024 narumij
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
// This code is based on work originally distributed under the Apache License 2.0 with LLVM Exceptions:
//
// Copyright © 2003-2024 The LLVM Project.
// Licensed under the Apache License, Version 2.0 with LLVM Exceptions.
// The original license can be found at https://llvm.org/LICENSE.txt
//
// This Swift implementation includes modifications and adaptations made by narumij.
import Foundation
public enum ___RedBlackTree {}
extension ValueComparer {
public typealias Tree = ___RedBlackTree.___Tree<Self>
}
@usableFromInline
protocol ___RedBlackTreeBase: ValueComparer {
associatedtype Element
var _storage: Tree.Storage { get set }
}
extension ___RedBlackTreeBase {
@inlinable @inline(__always)
var _tree: Tree { _storage.tree }
}
extension ___RedBlackTreeBase {
@inlinable @inline(__always)
var ___count: Int {
_tree.count
}
@inlinable @inline(__always)
var ___is_empty: Bool {
_tree.___is_empty
}
@inlinable @inline(__always)
var ___capacity: Int {
_tree.___capacity
}
}
// MARK: - Index
extension ___RedBlackTreeBase {
@usableFromInline
typealias ___Index = Tree.Pointer
@usableFromInline
typealias ___RawIndex = Tree.RawPointer
@inlinable @inline(__always)
func ___index(_ p: _NodePtr) -> ___Index {
.init(__tree: _tree, rawValue: p)
}
@inlinable @inline(__always)
func ___index_or_nil(_ p: _NodePtr) -> ___Index? {
p == .nullptr ? nil : ___index(p)
}
@inlinable @inline(__always)
func ___index_or_nil(_ p: _NodePtr?) -> ___Index? {
p.map { ___index($0) }
}
@inlinable @inline(__always)
func ___index_start() -> ___Index {
___index(_tree.___begin())
}
@inlinable @inline(__always)
func ___index_end() -> ___Index {
___index(_tree.___end())
}
@inlinable @inline(__always)
public func ___ptr_start() -> _NodePtr {
_tree.___begin()
}
@inlinable @inline(__always)
public func ___ptr_end() -> _NodePtr {
_tree.___end()
}
}
extension ___RedBlackTreeBase {
@inlinable @inline(__always)
public func ___ptr_lower_bound(_ __k: _Key) -> _NodePtr {
_tree.lower_bound(__k)
}
@inlinable @inline(__always)
public func ___ptr_upper_bound(_ __k: _Key) -> _NodePtr {
_tree.upper_bound(__k)
}
@inlinable @inline(__always)
public func ___raw_index_lower_bound(_ __k: _Key) -> ___RawIndex {
.init(_tree.lower_bound(__k))
}
@inlinable @inline(__always)
public func ___raw_index_upper_bound(_ __k: _Key) -> ___RawIndex {
.init(_tree.upper_bound(__k))
}
@inlinable @inline(__always)
public func ___index_lower_bound(_ __k: _Key) -> ___Index {
___index(___ptr_lower_bound(__k))
}
@inlinable @inline(__always)
public func ___index_upper_bound(_ __k: _Key) -> ___Index {
___index(___ptr_upper_bound(__k))
}
}
extension ___RedBlackTreeBase {
@inlinable @inline(__always)
func ___index(before i: _NodePtr) -> ___Index {
___index(_tree.index(before: i))
}
@inlinable @inline(__always)
func ___index(after i: _NodePtr) -> ___Index {
___index(_tree.index(after: i))
}
@inlinable @inline(__always)
public func ___form_index(before i: inout _NodePtr) {
_tree.formIndex(before: &i)
}
@inlinable @inline(__always)
public func ___form_index(after i: inout _NodePtr) {
_tree.formIndex(after: &i)
}
}
extension ___RedBlackTreeBase {
@inlinable @inline(__always)
func ___index(_ i: _NodePtr, offsetBy distance: Int) -> ___Index {
___index(_tree.index(i, offsetBy: distance))
}
@inlinable @inline(__always)
func ___index(
_ i: _NodePtr, offsetBy distance: Int, limitedBy limit: _NodePtr
) -> ___Index? {
___index_or_nil(_tree.index(i, offsetBy: distance, limitedBy: limit))
}
@inlinable @inline(__always)
public func ___form_index(_ i: inout _NodePtr, offsetBy distance: Int) {
_tree.formIndex(&i, offsetBy: distance)
}
@inlinable @inline(__always)
public func ___form_index(_ i: inout _NodePtr, offsetBy distance: Int, limitedBy limit: _NodePtr)
-> Bool
{
_tree.formIndex(&i, offsetBy: distance, limitedBy: limit)
}
}
extension ___RedBlackTreeBase {
@inlinable
func ___first_index(of member: _Key) -> ___Index? {
var __parent = _NodePtr.nullptr
let ptr = _tree.__ptr_(_tree.__find_equal(&__parent, member))
return ___index_or_nil(ptr)
}
@inlinable
func ___first_index(where predicate: (Element) throws -> Bool) rethrows -> ___Index? {
var result: ___Index?
try _tree.___for_each(__p: _tree.__begin_node, __l: _tree.__end_node()) { __p, cont in
if try predicate(_tree[__p]) {
result = ___index(__p)
cont = false
}
}
return result
}
}
extension ___RedBlackTreeBase {
@inlinable @inline(__always)
public func ___distance(from start: _NodePtr, to end: _NodePtr) -> Int {
_tree.___signed_distance(start, end)
}
}
// MARK: - Remove
extension ___RedBlackTreeBase {
@inlinable
@inline(__always)
@discardableResult
mutating func ___remove(at ptr: _NodePtr) -> Element? {
guard
!___is_null_or_end(ptr),
_tree.___is_valid_index(ptr)
else {
return nil
}
let e = _tree[ptr]
_ = _tree.erase(ptr)
return e
}
@inlinable
@inline(__always)
@discardableResult
mutating func ___remove(from: _NodePtr, to: _NodePtr) -> _NodePtr {
guard from != .end else {
return .end
}
guard
_tree.___is_valid_index(from),
_tree.___is_valid_index(to)
else {
fatalError(.invalidIndex)
}
return _tree.erase(from, to)
}
@inlinable
@inline(__always)
public mutating func ___remove(
from: _NodePtr, to: _NodePtr, forEach action: (Element) throws -> Void
)
rethrows
{
guard from != .end else {
return
}
guard
_tree.___is_valid_index(from),
_tree.___is_valid_index(to)
else {
fatalError(.invalidIndex)
}
return try _tree.___erase(from, to, action)
}
@inlinable
@inline(__always)
public mutating func ___remove<Result>(
from: _NodePtr, to: _NodePtr,
into initialResult: Result,
_ updateAccumulatingResult: (inout Result, Element) throws -> Void
) rethrows -> Result {
guard from != .end else {
return initialResult
}
guard
_tree.___is_valid_index(from),
_tree.___is_valid_index(to)
else {
fatalError(.invalidIndex)
}
return try _tree.___erase(from, to, into: initialResult, updateAccumulatingResult)
}
@inlinable
@inline(__always)
public mutating func ___remove<Result>(
from: _NodePtr, to: _NodePtr,
_ initialResult: Result,
_ nextPartialResult: (Result, Element) throws -> Result
) rethrows -> Result {
guard from != .end else {
return initialResult
}
guard
_tree.___is_valid_index(from),
_tree.___is_valid_index(to)
else {
fatalError(.invalidIndex)
}
return try _tree.___erase(from, to, initialResult, nextPartialResult)
}
}
extension ___RedBlackTreeBase {
@inlinable
mutating func ___removeAll(keepingCapacity keepCapacity: Bool = false) {
if keepCapacity {
_tree.__eraseAll()
} else {
_storage = .create(withCapacity: 0)
}
}
}
// MARK: - Equatable
extension ___RedBlackTreeBase {
@inlinable
func ___equal_with(_ rhs: Self) -> Bool where Self: Sequence, Element: Equatable {
_tree === rhs._tree || (___count == rhs.___count && zip(_tree, rhs._tree).allSatisfy(==))
}
@inlinable
func ___equal_with<K, V>(_ rhs: Self) -> Bool
where Self: Sequence, K: Equatable, V: Equatable, Element == (key: K, value: V) {
_tree === rhs._tree || (___count == rhs.___count && zip(_tree, rhs._tree).allSatisfy(==))
}
}
// MARK: - Etc
extension ___RedBlackTreeBase {
@inlinable @inline(__always)
func ___contains(_ __k: _Key) -> Bool where _Key: Equatable {
_tree.__count_unique(__k) != 0
}
}
extension ___RedBlackTreeBase {
@inlinable @inline(__always)
func ___min() -> Element? {
_tree.__root() == .nullptr ? nil : _tree[_tree.__tree_min(_tree.__root())]
}
@inlinable @inline(__always)
func ___max() -> Element? {
_tree.__root() == .nullptr ? nil : _tree[_tree.__tree_max(_tree.__root())]
}
}
extension ___RedBlackTreeBase {
@inlinable @inline(__always)
func ___value_for(_ __k: _Key) -> Element? {
let __ptr = _tree.find(__k)
return ___is_null_or_end(__ptr) ? nil : _tree[__ptr]
}
}
extension ___RedBlackTreeBase {
@inlinable
public func ___first(where predicate: (Element) throws -> Bool) rethrows -> Element? {
var result: Element?
try _tree.___for_each(__p: _tree.__begin_node, __l: _tree.__end_node()) { __p, cont in
if try predicate(_tree[__p]) {
result = _tree[__p]
cont = false
}
}
return result
}
}
extension ___RedBlackTreeBase {
@inlinable
public func ___tree_invariant() -> Bool {
_tree.__tree_invariant(_tree.__root())
}
#if AC_COLLECTIONS_INTERNAL_CHECKS
@inlinable
public var _copyCount: UInt {
get { _storage.tree.copyCount }
set { _storage.tree.copyCount = newValue }
}
#endif
}
#if AC_COLLECTIONS_INTERNAL_CHECKS
extension ___RedBlackTreeStorageLifetime {
@inlinable
public mutating func _checkUnique() -> Bool {
_isKnownUniquelyReferenced_LV2()
}
}
#endif
extension ___RedBlackTreeBase {
// C++風の削除コードが書きたい場合にこっそり(!?)つかうもの
@inlinable
@inline(__always)
@discardableResult
public mutating func ___std_erase(_ ptr: Tree.RawPointer) -> Tree.RawPointer {
Tree.RawPointer(_tree.erase(ptr.rawValue))
}
// C++風の削除コードが書きたい場合にこっそり(!?)つかうもの
@inlinable
@inline(__always)
@discardableResult
public mutating func ___std_erase(_ ptr: Tree.Pointer) -> Tree.Pointer {
Tree.Pointer(__tree: _tree, rawValue: _tree.erase(ptr.rawValue))
}
}
// MARK: -
@usableFromInline
protocol ___RedBlackTreeSubSequenceBase {
associatedtype Base: ValueComparer
var _subSequence: Base.Tree.SubSequence { get }
}
extension ___RedBlackTreeSubSequenceBase {
@inlinable
@inline(__always)
internal var _tree: ___Tree { _subSequence._tree }
}
extension ___RedBlackTreeSubSequenceBase {
@usableFromInline
typealias ___Tree = Base.Tree
@usableFromInline
typealias ___Index = Base.Tree.Pointer
@usableFromInline
typealias ___SubSequence = Base.Tree.SubSequence
@usableFromInline
typealias ___Element = Base.Tree.SubSequence.Element
@inlinable @inline(__always)
internal var ___start_index: ___Index {
___Index(__tree: _tree, rawValue: _subSequence.startIndex)
}
@inlinable @inline(__always)
internal var ___end_index: ___Index {
___Index(__tree: _tree, rawValue: _subSequence.endIndex)
}
@inlinable @inline(__always)
internal var ___count: Int {
_subSequence.count
}
@inlinable @inline(__always)
internal func ___for_each(_ body: (___Element) throws -> Void) rethrows {
try _subSequence.forEach(body)
}
@inlinable @inline(__always)
internal func ___distance(from start: ___Index, to end: ___Index) -> Int {
_subSequence.distance(from: start.rawValue, to: end.rawValue)
}
@inlinable @inline(__always)
internal func ___index(after i: ___Index) -> ___Index {
___Index(__tree: _tree, rawValue: _subSequence.index(after: i.rawValue))
}
@inlinable @inline(__always)
internal func ___form_index(after i: inout ___Index) {
_subSequence.formIndex(after: &i.rawValue)
}
@inlinable @inline(__always)
internal func ___index(before i: ___Index) -> ___Index {
___Index(__tree: _tree, rawValue: _subSequence.index(before: i.rawValue))
}
@inlinable @inline(__always)
internal func ___form_index(before i: inout ___Index) {
_subSequence.formIndex(before: &i.rawValue)
}
@inlinable @inline(__always)
internal func ___index(_ i: ___Index, offsetBy distance: Int) -> ___Index {
___Index(__tree: _tree, rawValue: _subSequence.index(i.rawValue, offsetBy: distance))
}
@inlinable @inline(__always)
internal func ___form_index(_ i: inout ___Index, offsetBy distance: Int) {
_subSequence.formIndex(&i.rawValue, offsetBy: distance)
}
@inlinable @inline(__always)
internal func ___index(_ i: ___Index, offsetBy distance: Int, limitedBy limit: ___Index) -> ___Index? {
if let i = _subSequence.index(i.rawValue, offsetBy: distance, limitedBy: limit.rawValue) {
return ___Index(__tree: _tree, rawValue: i)
} else {
return nil
}
}
@inlinable @inline(__always)
internal func ___form_index(_ i: inout ___Index, offsetBy distance: Int, limitedBy limit: ___Index)
-> Bool
{
return _subSequence.formIndex(&i.rawValue, offsetBy: distance, limitedBy: limit.rawValue)
}
}
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
// This code is based on work originally distributed under the Apache License 2.0 with LLVM Exceptions:
//
// Copyright © 2003-2024 The LLVM Project.
// Licensed under the Apache License, Version 2.0 with LLVM Exceptions.
// The original license can be found at https://llvm.org/LICENSE.txt
//
// This Swift implementation includes modifications and adaptations made by narumij.
import Foundation
extension RedBlackTreeSet: SetAlgebra {
@inlinable
public func union(_ other: __owned RedBlackTreeSet<Element>)
-> RedBlackTreeSet<Element>
{
var result = self
result.formUnion(other)
return result
}
@inlinable
public func intersection(_ other: RedBlackTreeSet<Element>)
-> RedBlackTreeSet<Element>
{
var result = self
result.formIntersection(other)
return result
}
@inlinable
public func symmetricDifference(_ other: __owned RedBlackTreeSet<Element>)
-> RedBlackTreeSet<Element>
{
var result = self
result.formSymmetricDifference(other)
return result
}
@inlinable
func ___set_result(_ f: inout Index, _ l: Index, _ r: inout Tree.___MutablePointer) {
while f != l {
r.pointee = f.___pointee
r.___next()
f.___next()
}
}
@inlinable
public mutating func formUnion(_ other: __owned RedBlackTreeSet<Element>) {
let ___storage: Tree.Storage = .create(withCapacity: 0)
var __result: Tree.___MutablePointer = .init(_storage: ___storage)
var (__first1, __last1) = (___index_start(), ___index_end())
var (__first2, __last2) = (other.___index_start(), other.___index_end())
while __first1 != __last1 {
if __first2 == __last2 {
___set_result(&__first1, __last1, &__result)
_storage = ___storage
return
}
defer { __result.___next() }
if _tree.___comp(__first2.___pointee, __first1.___pointee) {
__result.pointee = __first2.___pointee
__first2.___next()
} else {
if !_tree.___comp(__first1.___pointee, __first2.___pointee) {
__first2.___next()
}
__result.pointee = __first1.___pointee
__first1.___next()
}
}
___set_result(&__first2, __last2, &__result)
_storage = ___storage
}
@inlinable
public mutating func formIntersection(_ other: RedBlackTreeSet<Element>) {
// lower_boundを使う方法があるが、一旦楽に実装できそうな方からにしている
let ___storage: Tree.Storage = .create(withCapacity: 0)
var __result: Tree.___MutablePointer = .init(_storage: ___storage)
var (__first1, __last1) = (___index_start(), ___index_end())
var (__first2, __last2) = (other.___index_start(), other.___index_end())
while __first1 != __last1, __first2 != __last2 {
if _tree.___comp(__first1.___pointee, __first2.___pointee) {
__first1.___next()
} else {
if !_tree.___comp(__first2.___pointee, __first1.___pointee) {
__result.pointee = __first1.___pointee
__result.___next()
__first1.___next()
}
__first2.___next()
}
}
_storage = ___storage
}
@inlinable
public mutating func formSymmetricDifference(_ other: __owned RedBlackTreeSet<Element>) {
let ___storage: Tree.Storage = .create(withCapacity: 0)
var __result: Tree.___MutablePointer = .init(_storage: ___storage)
var (__first1, __last1) = (___index_start(), ___index_end())
var (__first2, __last2) = (other.___index_start(), other.___index_end())
while __first1 != __last1 {
if __first2 == __last2 {
___set_result(&__first1, __last1, &__result)
_storage = ___storage
return
}
if Self.___comp(__first1.___pointee, __first2.___pointee) {
__result.pointee = __first1.___pointee
__result.___next()
__first1.___next()
} else {
if Self.___comp(__first2.___pointee, __first1.___pointee) {
__result.pointee = __first2.___pointee
__result.___next()
} else {
let i = RawIndex(__first1.rawValue)
__first1.___next()
remove(at: i)
}
__first2.___next()
}
}
___set_result(&__first2, __last2, &__result)
_storage = ___storage
}
}
// Copyright 2024 narumij
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
// This code is based on work originally distributed under the Apache License 2.0 with LLVM Exceptions:
//
// Copyright © 2003-2024 The LLVM Project.
// Licensed under the Apache License, Version 2.0 with LLVM Exceptions.
// The original license can be found at https://llvm.org/LICENSE.txt
//
// This Swift implementation includes modifications and adaptations made by narumij.
import Foundation
/// `RedBlackTreeDictionary` は、`Key` 型のキーと `Value` 型の値のペアを一意に格納するための
/// 赤黒木（Red-Black Tree）ベースの辞書型です。
///
/// ### 使用例
/// ```swift
/// /// `RedBlackTreeDictionary` を使用する例
/// var dictionary = RedBlackTreeDictionary<String, Int>()
/// dictionary.insert(key: "apple", value: 5)
/// dictionary.insert(key: "banana", value: 3)
/// dictionary.insert(key: "cherry", value: 7)
///
/// // キーを使用して値にアクセス
/// if let value = dictionary.value(forKey: "banana") {
/// print("banana の値は \(value) です。") // 出力例: banana の値は 3 です。
/// }
///
/// // キーと値のペアを削除
/// dictionary.remove(key: "apple")
/// ```
@frozen
public struct RedBlackTreeDictionary<Key: Comparable, Value> {
public
typealias Index = Tree.Pointer
public
typealias KeyValue = (key: Key, value: Value)
public
typealias Element = KeyValue
public
typealias Keys = [Key]
public
typealias Values = [Value]
public
typealias _Key = Key
public
typealias _Value = Value
@usableFromInline
var _storage: Tree.Storage
}
extension RedBlackTreeDictionary {
public typealias RawIndex = Tree.RawPointer
}
extension RedBlackTreeDictionary: ___RedBlackTreeBase {}
extension RedBlackTreeDictionary: ___RedBlackTreeStorageLifetime {}
extension RedBlackTreeDictionary: KeyValueComparer {}
extension RedBlackTreeDictionary {
@inlinable @inline(__always)
public init() {
self.init(minimumCapacity: 0)
}
@inlinable @inline(__always)
public init(minimumCapacity: Int) {
_storage = .create(withCapacity: minimumCapacity)
}
}
extension RedBlackTreeDictionary {
@inlinable
public init<S>(uniqueKeysWithValues keysAndValues: __owned S)
where S: Sequence, S.Element == (Key, Value) {
let count = (keysAndValues as? (any Collection))?.count
var tree: Tree = .create(minimumCapacity: count ?? 0)
// 初期化直後はO(1)
var (__parent, __child) = tree.___max_ref()
// ソートの計算量がO(*n* log *n*)
for __k in keysAndValues.sorted(by: { $0.0 < $1.0 }) {
if count == nil {
Tree.ensureCapacity(tree: &tree)
}
if __parent == .end || tree[__parent].0 != __k.0 {
// バランシングの計算量がO(log *n*)
(__parent, __child) = tree.___emplace_hint_right(__parent, __child, __k)
assert(tree.__tree_invariant(tree.__root()))
} else {
fatalError("Dupricate values for key: '\(__k.0)'")
}
}
self._storage = .init(__tree: tree)
}
}
extension RedBlackTreeDictionary {
@inlinable
public init<S>(
_ keysAndValues: __owned S,
uniquingKeysWith combine: (Value, Value) throws -> Value
) rethrows where S: Sequence, S.Element == (Key, Value) {
let count = (keysAndValues as? (any Collection))?.count
var tree: Tree = .create(minimumCapacity: count ?? 0)
// 初期化直後はO(1)
var (__parent, __child) = tree.___max_ref()
// ソートの計算量がO(*n* log *n*)
for __k in keysAndValues.sorted(by: { $0.0 < $1.0 }) {
if count == nil {
Tree.ensureCapacity(tree: &tree)
}
if __parent == .end || tree[__parent].0 != __k.0 {
// バランシングの計算量がO(log *n*)
(__parent, __child) = tree.___emplace_hint_right(__parent, __child, __k)
assert(tree.__tree_invariant(tree.__root()))
} else {
tree[__parent].value = try combine(tree[__parent].value, __k.1)
}
}
self._storage = .init(__tree: tree)
}
}
extension RedBlackTreeDictionary {
@inlinable
public init<S: Sequence>(
grouping values: __owned S,
by keyForValue: (S.Element) throws -> Key
) rethrows where Value == [S.Element] {
let count = (values as? (any Collection))?.count
var tree: Tree = .create(minimumCapacity: count ?? 0)
// 初期化直後はO(1)
var (__parent, __child) = tree.___max_ref()
// ソートの計算量がO(*n* log *n*)
for (__k, __v) in try values.map({ (try keyForValue($0), $0) }).sorted(by: { $0.0 < $1.0 }) {
if count == nil {
Tree.ensureCapacity(tree: &tree)
}
if __parent == .end || tree[__parent].0 != __k {
// バランシングの計算量がO(log *n*)
(__parent, __child) = tree.___emplace_hint_right(__parent, __child, (__k, [__v]))
assert(tree.__tree_invariant(tree.__root()))
} else {
tree[__parent].value.append(__v)
}
}
self._storage = .init(__tree: tree)
}
}
extension RedBlackTreeDictionary {
/// - 計算量: O(1)
@inlinable
public var isEmpty: Bool {
___is_empty
}
/// - 計算量: O(1)
@inlinable
public var capacity: Int {
___capacity
}
}
extension RedBlackTreeDictionary {
@inlinable
public mutating func reserveCapacity(_ minimumCapacity: Int) {
_ensureUniqueAndCapacity(to: minimumCapacity)
}
}
extension RedBlackTreeDictionary {
@usableFromInline
struct ___ModifyHelper {
@inlinable @inline(__always)
init(pointer: UnsafeMutablePointer<Value>) {
self.pointer = pointer
}
@usableFromInline
var isNil: Bool = false
@usableFromInline
var pointer: UnsafeMutablePointer<Value>
@inlinable
var value: Value? {
@inline(__always)
get { isNil ? nil : pointer.pointee }
@inline(__always)
_modify {
var value: Value? = pointer.move()
defer {
if let value {
isNil = false
pointer.initialize(to: value)
} else {
isNil = true
}
}
yield &value
}
}
}
@inlinable
public subscript(key: Key) -> Value? {
@inline(__always)
get { ___value_for(key)?.value }
@inline(__always)
_modify {
// TODO: もうすこしライフタイム管理に明るくなったら、再度ここのチューニングに取り組む
let (__parent, __child, __ptr) = _prepareForKeyingModify(key)
if __ptr == .nullptr {
var value: Value?
defer {
if let value {
_ensureUniqueAndCapacity()
let __h = _tree.__construct_node((key, value))
_tree.__insert_node_at(__parent, __child, __h)
}
}
yield &value
} else {
_ensureUnique()
var helper = ___ModifyHelper(pointer: &_tree[__ptr].value)
defer {
if helper.isNil {
_ = _tree.erase(__ptr)
}
}
yield &helper.value
}
}
}
@inlinable
public subscript(
key: Key, default defaultValue: @autoclosure () -> Value
) -> Value {
@inline(__always)
get { ___value_for(key)?.value ?? defaultValue() }
@inline(__always)
_modify {
defer { _fixLifetime(self) }
var (__parent, __child, __ptr) = _prepareForKeyingModify(key)
if __ptr == .nullptr {
_ensureUniqueAndCapacity()
assert(_tree.header.capacity > _tree.count)
__ptr = _tree.__construct_node((key, defaultValue()))
_tree.__insert_node_at(__parent, __child, __ptr)
} else {
_ensureUnique()
}
yield &_tree[__ptr].value
}
}
@inlinable
@inline(__always)
internal func _prepareForKeyingModify(
_ key: Key
) -> (__parent: _NodePtr, __child: _NodeRef, __ptr: _NodePtr) {
var __parent = _NodePtr.nullptr
let __child = _tree.__find_equal(&__parent, key)
let __ptr = _tree.__ptr_(__child)
return (__parent, __child, __ptr)
}
}
extension RedBlackTreeDictionary {
public var keys: Keys {
map(\.key)
}
public var values: Values {
map(\.value)
}
}
extension RedBlackTreeDictionary {
@discardableResult
@inlinable
public mutating func updateValue(
_ value: Value,
forKey key: Key
) -> Value? {
_ensureUniqueAndCapacity()
let (__r, __inserted) = _tree.__insert_unique((key, value))
guard !__inserted else { return nil }
let oldMember = _tree[__r]
_tree[__r] = (key, value)
return oldMember.value
}
@inlinable
@discardableResult
public mutating func removeValue(forKey __k: Key) -> Value? {
let __i = _tree.find(__k)
if __i == _tree.end() {
return nil
}
let value = _tree.___element(__i).value
_ensureUnique()
_ = _tree.erase(__i)
return value
}
@inlinable
@discardableResult
public mutating func removeFirst() -> Element {
guard !isEmpty else {
preconditionFailure(.emptyFirst)
}
return remove(at: startIndex)
}
@inlinable
@discardableResult
public mutating func removeLast() -> Element {
guard !isEmpty else {
preconditionFailure(.emptyLast)
}
return remove(at: index(before: endIndex))
}
@inlinable
@discardableResult
public mutating func remove(at index: Index) -> KeyValue {
_ensureUnique()
guard let element = ___remove(at: index.rawValue) else {
fatalError(.invalidIndex)
}
return element
}
@inlinable
@discardableResult
public mutating func remove(at index: RawIndex) -> KeyValue {
_ensureUnique()
guard let element = ___remove(at: index.rawValue) else {
fatalError(.invalidIndex)
}
return element
}
@inlinable
public mutating func removeSubrange(_ range: Range<Index>) {
_ensureUnique()
___remove(from: range.lowerBound.rawValue, to: range.upperBound.rawValue)
}
@inlinable
public mutating func removeAll(keepingCapacity keepCapacity: Bool = false) {
_ensureUnique()
___removeAll(keepingCapacity: keepCapacity)
}
}
extension RedBlackTreeDictionary {
@inlinable
@inline(__always)
public mutating func remove(contentsOf keyRange: Range<Key>) {
let lower = lowerBound(keyRange.lowerBound)
let upper = lowerBound(keyRange.upperBound)
removeSubrange(lower..<upper)
}
@inlinable
@inline(__always)
public mutating func remove(contentsOf keyRange: ClosedRange<Key>) {
let lower = lowerBound(keyRange.lowerBound)
let upper = upperBound(keyRange.upperBound)
removeSubrange(lower..<upper)
}
}
extension RedBlackTreeDictionary {
@inlinable
public func lowerBound(_ p: Key) -> Index {
___index_lower_bound(p)
}
@inlinable
public func upperBound(_ p: Key) -> Index {
___index_upper_bound(p)
}
}
extension RedBlackTreeDictionary {
@inlinable
public var first: Element? {
isEmpty ? nil : self[startIndex]
}
@inlinable
public var last: Element? {
isEmpty ? nil : self[index(before: .end(_tree))]
}
@inlinable
public func first(where predicate: (Element) throws -> Bool) rethrows -> Element? {
try ___first(where: predicate)
}
@inlinable
public func firstIndex(of key: Key) -> Index? {
___first_index(of: key)
}
@inlinable
public func firstIndex(where predicate: (Element) throws -> Bool) rethrows -> Index? {
try ___first_index(where: predicate)
}
}
extension RedBlackTreeDictionary: ExpressibleByDictionaryLiteral {
@inlinable
public init(dictionaryLiteral elements: (Key, Value)...) {
self.init(uniqueKeysWithValues: elements)
}
}
extension RedBlackTreeDictionary: CustomStringConvertible, CustomDebugStringConvertible {
// MARK: - CustomStringConvertible
@inlinable
public var description: String {
let pairs = map { "\($0.key): \($0.value)" }
return "[\(pairs.joined(separator: ", "))]"
}
// MARK: - CustomDebugStringConvertible
@inlinable
public var debugDescription: String {
return "RedBlackTreeDictionary(\(description))"
}
}
// MARK: - Equatable
extension RedBlackTreeDictionary: Equatable where Value: Equatable {
@inlinable
public static func == (lhs: Self, rhs: Self) -> Bool {
lhs.___equal_with(rhs)
}
}
// MARK: - Sequence, BidirectionalCollection
extension RedBlackTreeDictionary: Sequence {
@inlinable
@inline(__always)
public func forEach(_ body: (Element) throws -> Void) rethrows {
try _tree.___for_each_(body)
}
@frozen
public struct Iterator: IteratorProtocol {
@usableFromInline
internal var _iterator: Tree.Iterator
@inlinable
@inline(__always)
internal init(_base: RedBlackTreeDictionary) {
self._iterator = _base._tree.makeIterator()
}
@inlinable
@inline(__always)
public mutating func next() -> Element? {
return self._iterator.next()
}
}
@inlinable
@inline(__always)
public __consuming func makeIterator() -> Iterator {
return Iterator(_base: self)
}
#if false
@inlinable
@inline(__always)
public func enumerated() -> AnySequence<EnumElement> {
AnySequence { _tree.makeEnumIterator() }
}
#else
@inlinable
@inline(__always)
public func enumerated() -> EnumuratedSequence {
EnumuratedSequence(_subSequence: _tree.enumeratedSubsequence())
}
#endif
@inlinable
@inline(__always)
public func indices() -> IndexSequence {
IndexSequence(_subSequence: _tree.indexSubsequence())
}
}
extension RedBlackTreeDictionary: BidirectionalCollection {
@inlinable
@inline(__always)
public var startIndex: Index {
___index_start()
}
@inlinable
@inline(__always)
public var endIndex: Index {
___index_end()
}
@inlinable
@inline(__always)
public var count: Int {
___count
}
@inlinable
@inline(__always)
public func distance(from start: Index, to end: Index) -> Int {
___distance(from: start.rawValue, to: end.rawValue)
}
@inlinable
@inline(__always)
public func index(after i: Index) -> Index {
___index(after: i.rawValue)
}
@inlinable
@inline(__always)
public func formIndex(after i: inout Index) {
___form_index(after: &i.rawValue)
}
@inlinable
@inline(__always)
public func index(before i: Index) -> Index {
___index(before: i.rawValue)
}
@inlinable
@inline(__always)
public func formIndex(before i: inout Index) {
___form_index(before: &i.rawValue)
}
@inlinable
@inline(__always)
public func index(_ i: Index, offsetBy distance: Int) -> Index {
___index(i.rawValue, offsetBy: distance)
}
@inlinable
@inline(__always)
public func formIndex(_ i: inout Index, offsetBy distance: Int) {
___form_index(&i.rawValue, offsetBy: distance)
}
@inlinable
@inline(__always)
public func index(_ i: Index, offsetBy distance: Int, limitedBy limit: Index) -> Index? {
___index(i.rawValue, offsetBy: distance, limitedBy: limit.rawValue)
}
@inlinable
@inline(__always)
public func formIndex(_ i: inout Index, offsetBy distance: Int, limitedBy limit: Index)
-> Bool
{
___form_index(&i.rawValue, offsetBy: distance, limitedBy: limit.rawValue)
}
@inlinable
@inline(__always)
public subscript(position: Index) -> Element {
return _tree[position.rawValue]
}
@inlinable
@inline(__always)
public subscript(position: RawIndex) -> Element {
return _tree[position.rawValue]
}
@inlinable
public subscript(bounds: Range<Index>) -> SubSequence {
SubSequence(
_subSequence:
_tree.subsequence(
from: bounds.lowerBound.rawValue,
to: bounds.upperBound.rawValue)
)
}
@inlinable
public subscript(bounds: Range<Key>) -> SubSequence {
SubSequence(
_subSequence:
_tree.subsequence(
from: ___ptr_lower_bound(bounds.lowerBound),
to: ___ptr_lower_bound(bounds.upperBound)))
}
@inlinable
public subscript(bounds: ClosedRange<Key>) -> SubSequence {
SubSequence(
_subSequence:
_tree.subsequence(
from: ___ptr_lower_bound(bounds.lowerBound),
to: ___ptr_upper_bound(bounds.upperBound)))
}
}
extension RedBlackTreeDictionary {
@frozen
public struct SubSequence {
@usableFromInline
internal typealias _SubSequence = Tree.SubSequence
@usableFromInline
internal let _subSequence: _SubSequence
@inlinable
init(_subSequence: _SubSequence) {
self._subSequence = _subSequence
}
}
}
extension RedBlackTreeDictionary.SubSequence {
public typealias Base = RedBlackTreeDictionary
public typealias SubSequence = Self
public typealias Index = Base.Index
public typealias RawIndex = Base.RawIndex
public typealias Element = Base.Element
public typealias EnumuratedSequence = Base.EnumuratedSequence
public typealias IndexSequence = Base.IndexSequence
}
extension RedBlackTreeDictionary.SubSequence: Sequence {
public struct Iterator: IteratorProtocol {
@usableFromInline
internal var _iterator: _SubSequence.Iterator
@inlinable
@inline(__always)
internal init(_ _iterator: _SubSequence.Iterator) {
self._iterator = _iterator
}
@inlinable
@inline(__always)
public mutating func next() -> Element? {
_iterator.next()
}
}
@inlinable
@inline(__always)
public __consuming func makeIterator() -> Iterator {
Iterator(_subSequence.makeIterator())
}
#if false
@inlinable
@inline(__always)
public func enumerated() -> AnySequence<EnumElement> {
AnySequence {
tree.makeEnumeratedIterator(start: startIndex.rawValue, end: endIndex.rawValue)
}
}
#else
@inlinable
@inline(__always)
public func enumerated() -> EnumuratedSequence {
EnumuratedSequence(
_subSequence: _tree.enumeratedSubsequence(from: startIndex.rawValue, to: endIndex.rawValue))
}
#endif
@inlinable
@inline(__always)
public func indices() -> IndexSequence {
IndexSequence(
_subSequence: _tree.indexSubsequence(from: startIndex.rawValue, to: endIndex.rawValue))
}
}
extension RedBlackTreeDictionary.SubSequence: ___RedBlackTreeSubSequenceBase { }
extension RedBlackTreeDictionary.SubSequence: BidirectionalCollection {
@inlinable
@inline(__always)
public var startIndex: Index {
___start_index
}
@inlinable
@inline(__always)
public var endIndex: Index {
___end_index
}
@inlinable
@inline(__always)
public var count: Int {
___count
}
@inlinable
@inline(__always)
public func forEach(_ body: (Element) throws -> Void) rethrows {
try ___for_each(body)
}
@inlinable
@inline(__always)
public func distance(from start: Index, to end: Index) -> Int {
___distance(from: start, to: end)
}
@inlinable
@inline(__always)
public func index(after i: Index) -> Index {
___index(after: i)
}
@inlinable
@inline(__always)
public func formIndex(after i: inout Index) {
___form_index(after: &i)
}
@inlinable
@inline(__always)
public func index(before i: Index) -> Index {
___index(before: i)
}
@inlinable
@inline(__always)
public func formIndex(before i: inout Index) {
___form_index(before: &i)
}
@inlinable
@inline(__always)
public func index(_ i: Index, offsetBy distance: Int) -> Index {
___index(i, offsetBy: distance)
}
@inlinable
@inline(__always)
public func formIndex(_ i: inout Index, offsetBy distance: Int) {
___form_index(&i, offsetBy: distance)
}
@inlinable
@inline(__always)
public func index(_ i: Index, offsetBy distance: Int, limitedBy limit: Index) -> Index? {
___index(i, offsetBy: distance, limitedBy: limit)
}
@inlinable
@inline(__always)
public func formIndex(_ i: inout Index, offsetBy distance: Int, limitedBy limit: Index)
-> Bool
{
___form_index(&i, offsetBy: distance, limitedBy: limit)
}
@inlinable
@inline(__always)
public subscript(position: Index) -> Element {
_subSequence[position.rawValue]
}
@inlinable
@inline(__always)
public subscript(position: RawIndex) -> Element {
_subSequence[position.rawValue]
}
@inlinable
public subscript(bounds: Range<Index>) -> SubSequence {
SubSequence(
_subSequence:
_subSequence[bounds.lowerBound..<bounds.upperBound])
}
}
// MARK: - Enumerated Sequence
extension RedBlackTreeDictionary {
@frozen
public struct EnumuratedSequence {
public typealias Enumurated = Tree.Enumerated
@usableFromInline
internal typealias _SubSequence = Tree.EnumSequence
@usableFromInline
internal let _subSequence: _SubSequence
@inlinable
init(_subSequence: _SubSequence) {
self._subSequence = _subSequence
}
}
}
extension RedBlackTreeDictionary.EnumuratedSequence: Sequence {
public struct Iterator: IteratorProtocol {
@usableFromInline
internal var _iterator: _SubSequence.Iterator
@inlinable
@inline(__always)
internal init(_ _iterator: _SubSequence.Iterator) {
self._iterator = _iterator
}
@inlinable
@inline(__always)
public mutating func next() -> Enumurated? {
_iterator.next()
}
}
@inlinable
@inline(__always)
public __consuming func makeIterator() -> Iterator {
Iterator(_subSequence.makeIterator())
}
}
extension RedBlackTreeDictionary.EnumuratedSequence {
@inlinable
@inline(__always)
public func forEach(_ body: (Enumurated) throws -> Void) rethrows {
try _subSequence.forEach(body)
}
}
// MARK: - Index Sequence
extension RedBlackTreeDictionary {
@frozen
public struct IndexSequence {
public typealias RawPointer = Tree.RawPointer
@usableFromInline
internal typealias _SubSequence = Tree.IndexSequence
@usableFromInline
internal let _subSequence: _SubSequence
@inlinable
init(_subSequence: _SubSequence) {
self._subSequence = _subSequence
}
}
}
extension RedBlackTreeDictionary.IndexSequence: Sequence {
public struct Iterator: IteratorProtocol {
@usableFromInline
internal var _iterator: _SubSequence.Iterator
@inlinable
@inline(__always)
internal init(_ _iterator: _SubSequence.Iterator) {
self._iterator = _iterator
}
@inlinable
@inline(__always)
public mutating func next() -> RawPointer? {
_iterator.next()
}
}
@inlinable
@inline(__always)
public __consuming func makeIterator() -> Iterator {
Iterator(_subSequence.makeIterator())
}
}
extension RedBlackTreeDictionary.IndexSequence {
@inlinable
@inline(__always)
public func forEach(_ body: (RawPointer) throws -> Void) rethrows {
try _subSequence.forEach(body)
}
}
// MARK: -
extension RedBlackTreeDictionary {
@inlinable
@inline(__always)
public func isValid(index: Index) -> Bool {
_tree.___is_valid_index(index.rawValue)
}
@inlinable
@inline(__always)
public func isValid(index: RawIndex) -> Bool {
_tree.___is_valid_index(index.rawValue)
}
}
extension RedBlackTreeDictionary.SubSequence {
@inlinable
@inline(__always)
public func isValid(index i: Index) -> Bool {
_subSequence.___is_valid_index(index: i.rawValue)
}
@inlinable
@inline(__always)
public func isValid(index i: RawIndex) -> Bool {
_subSequence.___is_valid_index(index: i.rawValue)
}
}
// MARK: -
extension RedBlackTreeDictionary {
@inlinable
@inline(__always)
public mutating func insert(contentsOf other: RedBlackTreeDictionary<Key, Value>) {
_ensureUniqueAndCapacity(to: count + other.count)
_tree.__node_handle_merge_unique(other._tree)
}
}
// Copyright 2024 narumij
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
// This code is based on work originally distributed under the Apache License 2.0 with LLVM Exceptions:
//
// Copyright © 2003-2024 The LLVM Project.
// Licensed under the Apache License, Version 2.0 with LLVM Exceptions.
// The original license can be found at https://llvm.org/LICENSE.txt
//
// This Swift implementation includes modifications and adaptations made by narumij.
import Foundation
@usableFromInline
protocol BoundProtocol: ValueProtocol & RootProtocol & EndNodeProtocol {}
extension BoundProtocol {
@inlinable
@inline(__always)
func lower_bound(_ __v: _Key) -> _NodePtr {
return __lower_bound(__v, __root(), __end_node())
}
@inlinable
@inline(__always)
func upper_bound(_ __v: _Key) -> _NodePtr {
return __upper_bound(__v, __root(), __end_node())
}
}
extension ValueProtocol {
@inlinable
func
__lower_bound(_ __v: _Key, _ __root: _NodePtr, _ __result: _NodePtr) -> _NodePtr
{
var (__root, __result) = (__root, __result)
while __root != .nullptr {
if !value_comp(__value_(__root), __v) {
__result = __root
__root = __left_(__root)
} else {
__root = __right_(__root)
}
}
return __result
}
@inlinable
func
__upper_bound(_ __v: _Key, _ __root: _NodePtr, _ __result: _NodePtr) -> _NodePtr
{
var (__root, __result) = (__root, __result)
while __root != .nullptr {
if value_comp(__v, __value_(__root)) {
__result = __root
__root = __left_(__root)
} else {
__root = __right_(__root)
}
}
return __result
}
}
// Copyright 2024 narumij
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
// This code is based on work originally distributed under the Apache License 2.0 with LLVM Exceptions:
//
// Copyright © 2003-2024 The LLVM Project.
// Licensed under the Apache License, Version 2.0 with LLVM Exceptions.
// The original license can be found at https://llvm.org/LICENSE.txt
//
// This Swift implementation includes modifications and adaptations made by narumij.
import Foundation
@usableFromInline
protocol RemoveProtocol: MemberSetProtocol
& BeginNodeProtocol
& EndNodeProtocol
& SizeProtocol
{}
extension RemoveProtocol {
@inlinable
func __remove_node_pointer(_ __ptr: _NodePtr) -> _NodePtr {
var __r = __ptr
__r = __tree_next_iter(__r)
if __begin_node == __ptr {
__begin_node = __r
}
size -= 1
__tree_remove(__left_(__end_node()), __ptr)
return __r
}
}
// Copyright 2024 narumij
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
// This code is based on work originally distributed under the Apache License 2.0 with LLVM Exceptions:
//
// Copyright © 2003-2024 The LLVM Project.
// Licensed under the Apache License, Version 2.0 with LLVM Exceptions.
// The original license can be found at https://llvm.org/LICENSE.txt
//
// This Swift implementation includes modifications and adaptations made by narumij.
import Foundation
@usableFromInline
protocol FindLeafProtocol: ValueProtocol
& RootProtocol
& RefProtocol
& EndNodeProtocol
{}
extension FindLeafProtocol {
@inlinable
func
__find_leaf_low(_ __parent: inout _NodePtr, _ __v: _Key) -> _NodeRef
{
var __nd: _NodePtr = __root()
if __nd != .nullptr {
while true {
if value_comp(__value_(__nd), __v) {
if __right_(__nd) != .nullptr {
__nd = __right_(__nd)
} else {
__parent = __nd
return __right_ref(__nd)
}
} else {
if __left_(__nd) != .nullptr {
__nd = __left_(__nd)
} else {
__parent = __nd
return __left_ref(__parent)
}
}
}
}
__parent = __end_node()
return __left_ref(__parent)
}
@inlinable
func
__find_leaf_high(_ __parent: inout _NodePtr, _ __v: _Key) -> _NodeRef
{
var __nd: _NodePtr = __root()
if __nd != .nullptr {
while true {
if value_comp(__v, __value_(__nd)) {
if __left_(__nd) != .nullptr {
__nd = __left_(__nd)
} else {
__parent = __nd
return __left_ref(__parent)
}
} else {
if __right_(__nd) != .nullptr {
__nd = __right_(__nd)
} else {
__parent = __nd
return __right_ref(__nd)
}
}
}
}
__parent = __end_node()
return __left_ref(__parent)
}
}
@usableFromInline
protocol FindEqualProtocol: FindProtocol & RefProtocol & RootPtrProrototol {}
extension FindEqualProtocol {
@inlinable
func
__find_equal(_ __parent: inout _NodePtr, _ __v: _Key) -> _NodeRef
{
var __nd = __root()
var __nd_ptr = __root_ptr()
if __nd != .nullptr {
while true {
let __value__nd = __value_(__nd)
if value_comp(__v, __value__nd) {
if __left_(__nd) != .nullptr {
__nd_ptr = __left_ref(__nd)
__nd = __left_(__nd)
} else {
__parent = __nd
return __left_ref(__parent)
}
} else if value_comp(__value__nd, __v) {
if __right_(__nd) != .nullptr {
__nd_ptr = __right_ref(__nd)
__nd = __right_(__nd)
} else {
__parent = __nd
return __right_ref(__nd)
}
} else {
__parent = __nd
return __nd_ptr
}
}
}
__parent = __end_node()
return __left_ref(__parent)
}
}
@usableFromInline
protocol FindProtocol: ValueProtocol
& RootProtocol
& EndNodeProtocol
& EndProtocol
{}
extension FindProtocol {
@inlinable
func find(_ __v: _Key) -> _NodePtr {
let __p = __lower_bound(__v, __root(), __end_node())
if __p != end(), !value_comp(__v, __value_(__p)) {
return __p
}
return end()
}
}
// Copyright 2024 narumij
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
// This code is based on work originally distributed under the Apache License 2.0 with LLVM Exceptions:
//
// Copyright © 2003-2024 The LLVM Project.
// Licensed under the Apache License, Version 2.0 with LLVM Exceptions.
// The original license can be found at https://llvm.org/LICENSE.txt
//
// This Swift implementation includes modifications and adaptations made by narumij.
import Foundation
@usableFromInline
protocol MergeProtocol: KeyProtocol & FindEqualProtocol & FindLeafProtocol & InsertNodeAtProtocol & AllocatorProtocol { }
@usableFromInline
protocol HandleProtocol: AllocatorProtocol & KeyProtocol & ValueProtocol & BeginProtocol & EndProtocol & MemberProtocol & EraseProtocol { }
extension HandleProtocol {
@usableFromInline
typealias __node_pointer = _NodePtr
@inlinable @inline(__always)
func __get_key(_ v: _Key) -> _Key { v }
}
extension MergeProtocol {
@usableFromInline
typealias __parent_pointer = _NodePtr
@inlinable @inline(__always)
func __get_np(_ p: _NodePtr) -> _NodePtr { p }
@inlinable @inline(__always)
func static_cast___node_base_pointer_(_ p: _NodePtr) -> _NodePtr { p }
@inlinable
@inline(__always)
public func __node_handle_merge_unique<_Tree>(_ __source: _Tree)
where _Tree: HandleProtocol, _Tree._Key == _Key, _Tree.Element == Element {
var __i = __source.begin(); while __i != __source.end() {
var __src_ptr: _Tree.__node_pointer = __get_np(__i)
var __parent: __parent_pointer = .zero
print(__source.__value_(__src_ptr))
print(__source.__get_key(__source.__value_(__src_ptr)))
let __child = __find_equal(&__parent, __source.__get_key(__source.__value_(__src_ptr)))
__i = __source.__tree_next_iter(__i)
if (__ptr_(__child) != .nullptr) {
continue; }
#if false
// C++では本物のポインタで動作し、挿入後はノードがポインタを介して共有されるため、削除が行われる
_ = __source.__remove_node_pointer(__src_ptr);
#else
// ポインタを受け取れないので、代わりにノードを作る
__src_ptr = __construct_node(__source.___element(__src_ptr))
#endif
__insert_node_at(__parent, __child, static_cast___node_base_pointer_(__src_ptr))
}
}
@inlinable
@inline(__always)
public func __node_handle_merge_multi<_Tree>(_ __source: _Tree)
where _Tree: HandleProtocol, _Tree._Key == _Key, _Tree.Element == Element {
var __i = __source.begin(); while __i != __source.end() {
var __src_ptr: _Tree.__node_pointer = __get_np(__i)
var __parent: __parent_pointer = .zero
let __child = __find_leaf_high(&__parent, __source.__get_key(__source.__value_(__src_ptr)))
__i = __source.__tree_next_iter(__i)
#if false
// C++では本物のポインタで動作し、挿入後はノードがポインタを介して共有されるため、削除が行われる
_ = __source.__remove_node_pointer(__src_ptr);
#else
// ポインタを受け取れないので、代わりにノードを作る
__src_ptr = __construct_node(__source.___element(__src_ptr))
#endif
__insert_node_at(__parent, __child, static_cast___node_base_pointer_(__src_ptr));
}
}
}
// Copyright 2024 narumij
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
// This code is based on work originally distributed under the Apache License 2.0 with LLVM Exceptions:
//
// Copyright © 2003-2024 The LLVM Project.
// Licensed under the Apache License, Version 2.0 with LLVM Exceptions.
// The original license can be found at https://llvm.org/LICENSE.txt
//
// This Swift implementation includes modifications and adaptations made by narumij.
import Foundation
@usableFromInline
protocol ___tree_root_node {
var __left_: _pointer { get set }
}
extension ___tree_root_node {
public typealias _pointer = _NodePtr
}
@usableFromInline
protocol ___tree_base_node: ___tree_root_node {
var __right_: _pointer { get set }
var __parent_: _pointer { get set }
var __is_black_: Bool { get set }
}
import Foundation
@usableFromInline
protocol CountProtocol: ValueProtocol & RootProtocol & EndNodeProtocol & DistanceProtocol {}
extension CountProtocol {
@usableFromInline
typealias size_type = Int
@usableFromInline
typealias __node_pointer = _NodePtr
@usableFromInline
typealias __iter_pointer = _NodePtr
@inlinable
func __count_unique(_ __k: _Key) -> size_type {
var __rt: __node_pointer = __root()
while __rt != .nullptr {
if value_comp(__k, __value_(__rt)) {
__rt = __left_(__rt)
} else if value_comp(__value_(__rt), __k) {
__rt = __right_(__rt)
} else {
return 1
}
}
return 0
}
@inlinable
func __count_multi(_ __k: _Key) -> size_type {
var __result: __iter_pointer = __end_node()
var __rt: __node_pointer = __root()
while __rt != .nullptr {
if value_comp(__k, __value_(__rt)) {
__result = __rt
__rt = __left_(__rt)
} else if value_comp(__value_(__rt), __k) {
__rt = __right_(__rt)
} else {
return __distance(
__lower_bound(__k, __left_(__rt), __rt),
__upper_bound(__k, __right_(__rt), __result))
}
}
return 0
}
}
import Foundation
@usableFromInline
protocol PointerCompareProtocol: ValueProtocol {
func ___ptr_comp(_ l: _NodePtr, _ r: _NodePtr) -> Bool
}
// 現状使っていない
@usableFromInline
protocol CompareUniqueProtocol: ValueProtocol {}
extension CompareUniqueProtocol {
/// multisetでも、インデックス比較に関して不正な結果だが、レンジで使う限り落ちはしない
@inlinable
@inline(__always)
func ___ptr_comp_unique(_ l: _NodePtr, _ r: _NodePtr) -> Bool {
guard
l != r,
r != .end,
l != .end
else {
return l != .end && r == .end
}
return value_comp(__value_(l), __value_(r))
}
@inlinable
@inline(__always)
func ___ptr_comp(_ l: _NodePtr, _ r: _NodePtr) -> Bool {
___ptr_comp_unique(l, r)
}
}
@usableFromInline
protocol CompareMultiProtocol: MemberProtocol & RootProtocol & EndProtocol {}
extension CompareMultiProtocol {
// ノードの高さを数える
@inlinable
@inline(__always)
func ___ptr_height(_ __p: _NodePtr) -> Int {
assert(__p != .nullptr, "Node shouldn't be null")
var __h = 0
var __p = __p
while __p != __root(), __p != end() {
__p = __parent_(__p)
__h += 1
}
return __h
}
// ノードの大小を比較する
@inlinable
@inline(__always)
func ___ptr_comp_multi(_ __l: _NodePtr, _ __r: _NodePtr) -> Bool {
assert(__l != .nullptr, "Left node shouldn't be null")
assert(__r != .nullptr, "Right node shouldn't be null")
guard
__l != end(),
__r != end(),
__l != __r
else {
return __l != end() && __r == end()
}
var (__l, __lh) = (__l, ___ptr_height(__l))
var (__r, __rh) = (__r, ___ptr_height(__r))
// __rの高さを詰める
while __lh < __rh {
// 共通祖先が__lだった場合
if __parent_(__r) == __l {
// __rが左でなければ（つまり右）、__lが小さい
return !__tree_is_left_child(__r)
}
(__r, __rh) = (__parent_(__r), __rh - 1)
}
// __lの高さを詰める
while __lh > __rh {
// 共通祖先が__rだった場合
if __parent_(__l) == __r {
// __lが左であれば、__lが小さい
return __tree_is_left_child(__l)
}
(__l, __lh) = (__parent_(__l), __lh - 1)
}
// 親が一致するまで、両方の高さを詰める
while __parent_(__l) != __parent_(__r) {
(__l, __r) = (__parent_(__l), __parent_(__r))
}
// 共通祖先が__lと__r以外だった場合
// 共通祖先の左が__lであれば、__lが小さい
return __tree_is_left_child(__l)
}
@inlinable
@inline(__always)
func ___ptr_comp(_ l: _NodePtr, _ r: _NodePtr) -> Bool {
___ptr_comp_multi(l, r)
}
}
@usableFromInline
protocol CompareProtocol: PointerCompareProtocol {}
extension CompareProtocol {
@inlinable
@inline(__always)
func ___ptr_less_than(_ l: _NodePtr, _ r: _NodePtr) -> Bool {
___ptr_comp(l, r)
}
@inlinable
@inline(__always)
func ___ptr_less_than_or_equal(_ l: _NodePtr, _ r: _NodePtr) -> Bool {
return l == r || ___ptr_comp(l, r)
}
@inlinable
@inline(__always)
func ___ptr_greator_than(_ l: _NodePtr, _ r: _NodePtr) -> Bool {
return l != r && !___ptr_comp(l, r)
}
@inlinable
@inline(__always)
func ___ptr_greator_than_or_equal(_ l: _NodePtr, _ r: _NodePtr) -> Bool {
return !___ptr_comp(l, r)
}
@inlinable
@inline(__always)
func ___ptr_closed_range_contains(_ l: _NodePtr, _ r: _NodePtr, _ p: _NodePtr) -> Bool {
l == p || (___ptr_comp(l, p) && !___ptr_comp(r, p))
}
}
// Copyright 2024 narumij
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
// This code is based on work originally distributed under the Apache License 2.0 with LLVM Exceptions:
//
// Copyright © 2003-2024 The LLVM Project.
// Licensed under the Apache License, Version 2.0 with LLVM Exceptions.
// The original license can be found at https://llvm.org/LICENSE.txt
//
// This Swift implementation includes modifications and adaptations made by narumij.
import Foundation
extension MemberProtocol {
@inlinable
@inline(__always)
func
__tree_is_left_child(_ __x: _NodePtr) -> Bool
{
return __x == __left_(__parent_(__x))
}
#if TREE_INVARIANT_CHECKS
@inlinable
func
__tree_sub_invariant(_ __x: _NodePtr) -> UInt
{
if __x == .nullptr {
return 1
}
// parent consistency checked by caller
// check __x->__left_ consistency
if __left_(__x) != .nullptr && __parent_(__left_(__x)) != __x {
return 0
}
// check __x->__right_ consistency
if __right_(__x) != .nullptr && __parent_(__right_(__x)) != __x {
return 0
}
// check __x->__left_ != __x->__right_ unless both are nullptr
if __left_(__x) == __right_(__x) && __left_(__x) != .nullptr {
return 0
}
// If this is red, neither child can be red
if !__is_black_(__x) {
if __left_(__x) != .nullptr && !__is_black_(__left_(__x)) {
return 0
}
if __right_(__x) != .nullptr && !__is_black_(__right_(__x)) {
return 0
}
}
let __h = __tree_sub_invariant(__left_(__x))
if __h == 0 {
return 0
} // invalid left subtree
if __h != __tree_sub_invariant(__right_(__x)) {
return 0
} // invalid or different height right subtree
return __h + (__is_black_(__x) ? 1 : 0) // return black height of this node
}
#endif
#if TREE_INVARIANT_CHECKS
@inlinable
func
__tree_invariant(_ __root: _NodePtr) -> Bool
{
if __root == .nullptr {
return true
}
// check __x->__parent_ consistency
if __parent_(__root) == .nullptr {
return false
}
if !__tree_is_left_child(__root) {
return false
}
// root must be black
if !__is_black_(__root) {
return false
}
// do normal node checks
return __tree_sub_invariant(__root) != 0
}
#else
@inlinable
@inline(__always)
func __tree_invariant(_ __root: _NodePtr) -> Bool { true }
#endif
@inlinable
func
__tree_min(_ __x: _NodePtr) -> _NodePtr
{
assert(__x != .nullptr, "Root node shouldn't be null")
var __x = __x
while __left_(__x) != .nullptr {
__x = __left_(__x)
}
return __x
}
@inlinable
func
__tree_max(_ __x: _NodePtr) -> _NodePtr
{
assert(__x != .nullptr, "Root node shouldn't be null")
var __x = __x
while __right_(__x) != .nullptr {
__x = __right_(__x)
}
return __x
}
@inlinable
func
__tree_next(_ __x: _NodePtr) -> _NodePtr
{
assert(__x != .nullptr, "node shouldn't be null")
var __x = __x
if __right_(__x) != .nullptr {
return __tree_min(__right_(__x))
}
while !__tree_is_left_child(__x) {
__x = __parent_unsafe(__x)
}
return __parent_unsafe(__x)
}
@inlinable
func
__tree_next_iter(_ __x: _NodePtr) -> _NodePtr
{
assert(__x != .nullptr, "node shouldn't be null")
var __x = __x
if __right_(__x) != .nullptr {
return __tree_min(__right_(__x))
}
while !__tree_is_left_child(__x) {
__x = __parent_unsafe(__x)
}
return __parent_(__x)
}
@inlinable
func
__tree_prev_iter(_ __x: _NodePtr) -> _NodePtr
{
assert(__x != .nullptr, "node shouldn't be null")
if __left_(__x) != .nullptr {
return __tree_max(__left_(__x))
}
var __xx = __x
while __tree_is_left_child(__xx) {
__xx = __parent_unsafe(__xx)
}
return __parent_unsafe(__xx)
}
@inlinable
func
__tree_leaf(_ __x: _NodePtr) -> _NodePtr
{
assert(__x != .nullptr, "node shouldn't be null")
var __x = __x
while true {
if __left_(__x) != .nullptr {
__x = __left_(__x)
continue
}
if __right_(__x) != .nullptr {
__x = __right_(__x)
continue
}
break
}
return __x
}
}
// Copyright 2024 narumij
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
// This code is based on work originally distributed under the Apache License 2.0 with LLVM Exceptions:
//
// Copyright © 2003-2024 The LLVM Project.
// Licensed under the Apache License, Version 2.0 with LLVM Exceptions.
// The original license can be found at https://llvm.org/LICENSE.txt
//
// This Swift implementation includes modifications and adaptations made by narumij.
import Foundation
/// 赤黒木の内部Index
///
/// ヒープの代わりに配列を使っているため、実際には内部配列のインデックスを使用している
///
/// インデックスが0からはじまるため、一般的にnullは0で表現するところを、-1で表現している
///
/// endはルートノードを保持するオブジェクトを指すかわりに、-2で表現している
///
/// `__tree`ではポインタとイテレータが使われているが、イテレータはこのインデックスで代替している
public
typealias _NodePtr = Int
public
typealias _Pointer = _NodePtr
extension _NodePtr {
/// 赤黒木のIndexで、nullを表す
@inlinable
static var nullptr: Self { -1 }
/// 赤黒木のIndexで、終端を表す
@inlinable
static var end: Self { -2 }
/// 数値を直接扱うことを避けるための初期化メソッド
@inlinable
static func node(_ p: Int) -> Self { p }
}
@inlinable
@inline(__always)
func ___is_null_or_end(_ ptr: _NodePtr) -> Bool {
ptr < 0
}
/// 赤黒木の参照型を表す内部enum
public
enum _NodeRef: Equatable
{
case nullptr
/// 右ノードへの参照
case __right_(_NodePtr)
/// 左ノードへの参照
case __left_(_NodePtr)
}
// ルートノード相当の機能
@usableFromInline
protocol TreeEndNodeProtocol {
func __left_(_: pointer) -> pointer
func __left_(_ lhs: pointer, _ rhs: pointer)
}
extension TreeEndNodeProtocol {
@usableFromInline
typealias pointer = _Pointer
}
// 一般ノード相当の機能
@usableFromInline
protocol TreeNodeBaseProtocol: TreeEndNodeProtocol {
func __right_(_: pointer) -> pointer
func __right_(_ lhs: pointer, _ rhs: pointer)
func __is_black_(_: pointer) -> Bool
func __is_black_(_ lhs: pointer, _ rhs: Bool)
func __parent_(_: pointer) -> pointer
func __parent_(_ lhs: pointer, _ rhs: pointer)
func __parent_unsafe(_: pointer) -> __parent_pointer
}
extension TreeNodeBaseProtocol {
@usableFromInline
typealias __parent_pointer = _Pointer
}
// 以下は、現在の設計に至る過程で、readハンドルとupdateハンドルに分けていた名残で、
// getとsetが分かれている
@usableFromInline
protocol MemberProtocol {
func __left_(_: _NodePtr) -> _NodePtr
func __right_(_: _NodePtr) -> _NodePtr
func __is_black_(_: _NodePtr) -> Bool
func __parent_(_: _NodePtr) -> _NodePtr
func __parent_unsafe(_: _NodePtr) -> _NodePtr
}
@usableFromInline
protocol MemberSetProtocol: MemberProtocol {
func __left_(_ lhs: _NodePtr, _ rhs: _NodePtr)
func __right_(_ lhs: _NodePtr, _ rhs: _NodePtr)
func __is_black_(_ lhs: _NodePtr, _ rhs: Bool)
func __parent_(_ lhs: _NodePtr, _ rhs: _NodePtr)
}
@usableFromInline
protocol RefProtocol: MemberProtocol {
func __left_ref(_: _NodePtr) -> _NodeRef
func __right_ref(_: _NodePtr) -> _NodeRef
func __ptr_(_ rhs: _NodeRef) -> _NodePtr
}
@usableFromInline
protocol RefSetProtocol: RefProtocol {
func __ptr_(_ lhs: _NodeRef, _ rhs: _NodePtr)
}
@usableFromInline
protocol KeyProtocol {
associatedtype _Key
associatedtype Element
func __key(_ e: Element) -> _Key
}
@usableFromInline
protocol ValueProtocol: MemberProtocol {
associatedtype _Key
func __value_(_: _NodePtr) -> _Key
func value_comp(_: _Key, _: _Key) -> Bool
}
extension ValueProtocol {
@inlinable @inline(__always)
func ___comp(_ a: _Key, _ b: _Key) -> Bool {
value_comp(a, b)
}
}
@usableFromInline
protocol BeginNodeProtocol {
var __begin_node: _NodePtr { get nonmutating set }
}
@usableFromInline
protocol BeginProtocol: BeginNodeProtocol {
func begin() -> _NodePtr
}
extension BeginProtocol {
@inlinable
@inline(__always)
func begin() -> _NodePtr { __begin_node }
}
@usableFromInline
protocol EndNodeProtocol {
func __end_node() -> _NodePtr
}
extension EndNodeProtocol {
@inlinable
@inline(__always)
func __end_node() -> _NodePtr { .end }
}
@usableFromInline
protocol EndProtocol: EndNodeProtocol {
func end() -> _NodePtr
}
extension EndProtocol {
@inlinable
@inline(__always)
func end() -> _NodePtr { __end_node() }
}
@usableFromInline
protocol RootProtocol: MemberProtocol & EndProtocol {
func __root() -> _NodePtr
}
extension RootProtocol {
@inlinable
@inline(__always)
func __root() -> _NodePtr { __left_(__end_node()) }
}
@usableFromInline
protocol RootPtrProrototol: RootProtocol {
func __root_ptr() -> _NodeRef
}
extension RootPtrProrototol {
@inlinable
@inline(__always)
func __root_ptr() -> _NodeRef { __left_ref(__end_node()) }
}
@usableFromInline
protocol SizeProtocol {
var size: Int { get nonmutating set }
}
// MARK: -
@usableFromInline
protocol AllocatorProtocol {
associatedtype Element
func __construct_node(_ k: Element) -> _NodePtr
func destroy(_ p: _NodePtr)
func ___element(_ p: _NodePtr) -> Element
}
// MARK: common
public protocol ValueComparer {
associatedtype _Key
associatedtype Element
static func __key(_: Element) -> _Key
static func value_comp(_: _Key, _: _Key) -> Bool
}
extension ValueComparer where _Key: Comparable {
@inlinable @inline(__always)
public static func value_comp(_ a: _Key, _ b: _Key) -> Bool {
a < b
}
}
extension ValueComparer {
@inlinable @inline(__always)
static func ___comp(_ a: _Key, _ b: _Key) -> Bool {
value_comp(a, b)
}
}
// MARK: key
public protocol ScalarValueComparer: ValueComparer where _Key == Element {}
extension ScalarValueComparer {
@inlinable @inline(__always)
public static func __key(_ e: Element) -> _Key { e }
}
// MARK: key value
public protocol KeyValueComparer: ValueComparer {
associatedtype _Value
static func __key(_ element: Element) -> _Key
}
extension KeyValueComparer {
public typealias _KeyValueTuple = (key: _Key, value: _Value)
}
extension KeyValueComparer where Element == _KeyValueTuple {
@inlinable @inline(__always)
public static func __key(_ element: Element) -> _Key { element.key }
}
// MARK: key value
public
protocol _KeyCustomProtocol
{
associatedtype Parameters
static func value_comp(_ a: Parameters, _ b: Parameters) -> Bool
}
protocol CustomKeyValueComparer: KeyValueComparer where _Key == Custom.Parameters {
associatedtype Custom: _KeyCustomProtocol
}
extension CustomKeyValueComparer {
@inlinable @inline(__always)
public static func value_comp(_ a: _Key, _ b: _Key) -> Bool {
Custom.value_comp(a, b)
}
}
// Copyright 2024 narumij
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
// This code is based on work originally distributed under the Apache License 2.0 with LLVM Exceptions:
//
// Copyright © 2003-2024 The LLVM Project.
// Licensed under the Apache License, Version 2.0 with LLVM Exceptions.
// The original license can be found at https://llvm.org/LICENSE.txt
//
// This Swift implementation includes modifications and adaptations made by narumij.
import Foundation
extension MemberProtocol {
@inlinable
func __ptr_(_ rhs: _NodeRef) -> _NodePtr {
switch rhs {
case .nullptr:
return .nullptr
case .__right_(let basePtr):
return __right_(basePtr)
case .__left_(let basePtr):
return __left_(basePtr)
}
}
@inlinable
@inline(__always)
func __left_ref(_ p: _NodePtr) -> _NodeRef {
.__left_(p)
}
@inlinable
@inline(__always)
func __right_ref(_ p: _NodePtr) -> _NodeRef {
.__right_(p)
}
}
extension MemberSetProtocol {
@inlinable
func __ptr_(_ lhs: _NodeRef, _ rhs: _NodePtr) {
switch lhs {
case .nullptr:
fatalError()
case .__right_(let basePtr):
return __right_(basePtr, rhs)
case .__left_(let basePtr):
return __left_(basePtr, rhs)
}
}
}
// Copyright 2024 narumij
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
// This code is based on work originally distributed under the Apache License 2.0 with LLVM Exceptions:
//
// Copyright © 2003-2024 The LLVM Project.
// Licensed under the Apache License, Version 2.0 with LLVM Exceptions.
// The original license can be found at https://llvm.org/LICENSE.txt
//
// This Swift implementation includes modifications and adaptations made by narumij.
import Foundation
@usableFromInline
protocol EqualProtocol: ValueProtocol, RootProtocol, EndNodeProtocol {}
extension EqualProtocol {
@inlinable
func
__equal_range_multi(_ __k: _Key) -> (_NodePtr, _NodePtr)
{
var __result = __end_node()
var __rt = __root()
while __rt != .nullptr {
if value_comp(__k, __value_(__rt)) {
__result = __rt
__rt = __left_(__rt)
} else if value_comp(__value_(__rt), __k) {
__rt = __right_(__rt)
} else {
return (
__lower_bound(
__k,
__left_(__rt),
__rt),
__upper_bound(
__k,
__right_(__rt),
__result)
)
}
}
return (__result, __result)
}
}
// Copyright 2024 narumij
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
// This code is based on work originally distributed under the Apache License 2.0 with LLVM Exceptions:
//
// Copyright © 2003-2024 The LLVM Project.
// Licensed under the Apache License, Version 2.0 with LLVM Exceptions.
// The original license can be found at https://llvm.org/LICENSE.txt
//
// This Swift implementation includes modifications and adaptations made by narumij.
import Foundation
@usableFromInline
protocol EraseProtocol: AnyObject {
func destroy(_ p: _NodePtr)
func __remove_node_pointer(_ __ptr: _NodePtr) -> _NodePtr
}
extension EraseProtocol {
@inlinable
func
erase(_ __p: _NodePtr) -> _NodePtr
{
let __r = __remove_node_pointer(__p)
destroy(__p)
return __r
}
@inlinable
func
erase(_ __f: _NodePtr, _ __l: _NodePtr) -> _NodePtr
{
var __f = __f
while __f != __l {
__f = erase(__f)
}
return __l
}
}
@usableFromInline
protocol EraseUniqueProtocol: FindProtocol, EraseProtocol { }
extension EraseUniqueProtocol {
@inlinable
internal func ___erase_unique(_ __k: _Key) -> Bool {
let __i = find(__k)
if __i == end() {
return false
}
_ = erase(__i)
return true
}
}
@usableFromInline
protocol EraseMultiProtocol: EqualProtocol, EraseProtocol { }
extension EraseMultiProtocol {
@inlinable
internal func ___erase_multi(_ __k: _Key) -> Int {
var __p = __equal_range_multi(__k)
var __r = 0
while __p.0 != __p.1 {
defer { __r += 1 }
__p.0 = erase(__p.0)
}
return __r
}
}
// Copyright 2024 narumij
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
// This code is based on work originally distributed under the Apache License 2.0 with LLVM Exceptions:
//
// Copyright © 2003-2024 The LLVM Project.
// Licensed under the Apache License, Version 2.0 with LLVM Exceptions.
// The original license can be found at https://llvm.org/LICENSE.txt
//
// This Swift implementation includes modifications and adaptations made by narumij.
import Foundation
@usableFromInline
protocol InsertNodeAtProtocol:
MemberSetProtocol & RefSetProtocol & SizeProtocol & BeginNodeProtocol & EndNodeProtocol
{}
extension InsertNodeAtProtocol {
@inlinable
func
__insert_node_at(
_ __parent: _NodePtr, _ __child: _NodeRef,
_ __new_node: _NodePtr
)
{
__left_(__new_node, .nullptr)
__right_(__new_node, .nullptr)
__parent_(__new_node, __parent)
// __new_node->__is_black_ is initialized in __tree_balance_after_insert
__ptr_(__child, __new_node)
if __left_(__begin_node) != .nullptr {
__begin_node = __left_(__begin_node)
}
__tree_balance_after_insert(__left_(__end_node()), __ptr_(__child))
size += 1
}
}
@usableFromInline
protocol InsertUniqueProtocol:
AllocatorProtocol & KeyProtocol & RefProtocol
{
func
__find_equal(
_ __parent: inout _NodePtr,
_ __v: _Key
) -> _NodeRef
func
__insert_node_at(
_ __parent: _NodePtr, _ __child: _NodeRef,
_ __new_node: _NodePtr)
}
extension InsertUniqueProtocol {
@inlinable
@inline(__always)
public func __insert_unique(_ x: Element) -> (__r: _NodePtr, __inserted: Bool) {
__emplace_unique_key_args(x)
}
#if true
@inlinable
func
__emplace_unique_key_args(_ __k: Element) -> (__r: _NodePtr, __inserted: Bool)
{
var __parent = _NodePtr.nullptr
let __child = __find_equal(&__parent, __key(__k))
let __r = __child
if __ptr_(__child) == .nullptr {
let __h = __construct_node(__k)
__insert_node_at(__parent, __child, __h)
return (__h, true)
} else {
// __insert_node_atで挿入した場合、__rが破損する
// 既存コードの後続で使用しているのが実質Ptrなので、そちらを返すよう一旦修正
// 今回初めて破損したrefを使用したようで既存コードでの破損ref使用は大丈夫そう
return (__ptr_(__r), false)
}
}
#else
@inlinable
func
__emplace_unique_key_args(_ __k: Element) -> (__r: _NodeRef, __inserted: Bool)
{
var __parent = _NodePtr.nullptr
let __child = __find_equal(&__parent, __key(__k))
let __r = __child
var __inserted = false
if __ref_(__child) == .nullptr {
let __h = __construct_node(__k)
__insert_node_at(__parent, __child, __h)
__inserted = true
}
return (__r, __inserted)
}
#endif
}
@usableFromInline
protocol InsertMultiProtocol:
AllocatorProtocol & KeyProtocol
{
func
__find_leaf_high(_ __parent: inout _NodePtr, _ __v: _Key) -> _NodeRef
func
__insert_node_at(
_ __parent: _NodePtr, _ __child: _NodeRef,
_ __new_node: _NodePtr)
}
extension InsertMultiProtocol {
@inlinable
@inline(__always)
public func __insert_multi(_ x: Element) -> _NodePtr {
__emplace_multi(x)
}
@inlinable
func
__emplace_multi(_ __k: Element) -> _NodePtr
{
let __h = __construct_node(__k)
var __parent = _NodePtr.nullptr
let __child = __find_leaf_high(&__parent, __key(__k))
__insert_node_at(__parent, __child, __h)
return __h
}
}
@usableFromInline
protocol InsertLastProtocol:
InsertNodeAtProtocol & AllocatorProtocol & RootProtocol & EndNodeProtocol
{}
extension InsertLastProtocol {
@inlinable
@inline(__always)
func ___max_ref() -> (__parent: _NodePtr, __child: _NodeRef) {
if __root() == .nullptr {
return (__end_node(), __left_ref(__end_node()))
}
let __parent = __tree_max(__root())
return (__parent, __right_ref(__parent))
}
@inlinable
@inline(__always)
func ___emplace_hint_right(_ __parent: _NodePtr, _ __child: _NodeRef, _ __k: Element) -> (
__parent: _NodePtr, __child: _NodeRef
) {
let __p = __construct_node(__k)
__insert_node_at(__parent, __child, __p)
return (__p, __right_ref(__p))
}
// こちらのほうがAPIとしては収まりがいいが、かすかに上のモノの方が速い
// 分岐の有無の差だとおもわれる
@inlinable
@inline(__always)
func ___emplace_hint_right(_ __p: _NodePtr, _ __k: Element) -> _NodePtr {
let __child = __p == .end ? __left_ref(__p) : __right_ref(__p)
// ^--- これの差
let __h = __construct_node(__k)
__insert_node_at(__p, __child, __h)
return __h
}
@inlinable
@inline(__always)
func ___emplace_hint_left(_ __p: _NodePtr, _ __k: Element) -> _NodePtr {
let __child = __left_ref(__p)
let __h = __construct_node(__k)
__insert_node_at(__p, __child, __h)
return __h
}
}
// Copyright 2024 narumij
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
// This code is based on work originally distributed under the Apache License 2.0 with LLVM Exceptions:
//
// Copyright © 2003-2024 The LLVM Project.
// Licensed under the Apache License, Version 2.0 with LLVM Exceptions.
// The original license can be found at https://llvm.org/LICENSE.txt
//
// This Swift implementation includes modifications and adaptations made by narumij.
import Foundation
extension MemberSetProtocol {
@inlinable
@inline(__always)
func
__tree_left_rotate(_ __x: _NodePtr)
{
assert(__x != .nullptr, "node shouldn't be null")
assert(__right_(__x) != .nullptr, "node should have a right child")
let __y = __right_(__x)
__right_(__x, __left_(__y))
if __right_(__x) != .nullptr {
__parent_(__right_(__x), __x)
}
__parent_(__y, __parent_(__x))
if __tree_is_left_child(__x) {
__left_(__parent_(__x), __y)
} else {
__right_(__parent_(__x), __y)
}
__left_(__y, __x)
__parent_(__x, __y)
}
@inlinable
func
__tree_right_rotate(_ __x: _NodePtr)
{
assert(__x != .nullptr, "node shouldn't be null")
assert(__left_(__x) != .nullptr, "node should have a left child")
let __y = __left_(__x)
__left_(__x, __right_(__y))
if __left_(__x) != .nullptr {
__parent_(__left_(__x), __x)
}
__parent_(__y, __parent_(__x))
if __tree_is_left_child(__x) {
__left_(__parent_(__x), __y)
} else {
__right_(__parent_(__x), __y)
}
__right_(__y, __x)
__parent_(__x, __y)
}
@inlinable
func
__tree_balance_after_insert(_ __root: _NodePtr, _ __x: _NodePtr)
{
assert(__root != .nullptr, "Root of the tree shouldn't be null")
assert(__x != .nullptr, "Can't attach null node to a leaf")
var __x = __x
__is_black_(__x, __x == __root)
while __x != __root, !__is_black_(__parent_unsafe(__x)) {
// __x->__parent_ != __root because __x->__parent_->__is_black == false
if __tree_is_left_child(__parent_unsafe(__x)) {
let __y = __right_(__parent_unsafe(__parent_unsafe(__x)))
if __y != .nullptr, !__is_black_(__y) {
__x = __parent_unsafe(__x)
__is_black_(__x, true)
__x = __parent_unsafe(__x)
__is_black_(__x, __x == __root)
__is_black_(__y, true)
} else {
if !__tree_is_left_child(__x) {
__x = __parent_unsafe(__x)
__tree_left_rotate(__x)
}
__x = __parent_unsafe(__x)
__is_black_(__x, true)
__x = __parent_unsafe(__x)
__is_black_(__x, false)
__tree_right_rotate(__x)
break
}
} else {
let __y = __left_(__parent_(__parent_unsafe(__x)))
if __y != .nullptr, !__is_black_(__y) {
__x = __parent_unsafe(__x)
__is_black_(__x, true)
__x = __parent_unsafe(__x)
__is_black_(__x, __x == __root)
__is_black_(__y, true)
} else {
if __tree_is_left_child(__x) {
__x = __parent_unsafe(__x)
__tree_right_rotate(__x)
}
__x = __parent_unsafe(__x)
__is_black_(__x, true)
__x = __parent_unsafe(__x)
__is_black_(__x, false)
__tree_left_rotate(__x)
break
}
}
}
}
@inlinable
func
__tree_remove(_ __root: _NodePtr, _ __z: _NodePtr)
{
assert(__root != .nullptr, "Root node should not be null")
assert(__z != .nullptr, "The node to remove should not be null")
assert(__tree_invariant(__root), "The tree invariants should hold")
var __root = __root
// __z will be removed from the tree. Client still needs to destruct/deallocate it
// __y is either __z, or if __z has two children, __tree_next(__z).
// __y will have at most one child.
// __y will be the initial hole in the tree (make the hole at a leaf)
let __y = (__left_(__z) == .nullptr || __right_(__z) == .nullptr) ? __z : __tree_next(__z)
// __x is __y's possibly null single child
var __x = __left_(__y) != .nullptr ? __left_(__y) : __right_(__y)
// __w is __x's possibly null uncle (will become __x's sibling)
var __w: _NodePtr = .nullptr
// link __x to __y's parent, and find __w
if __x != .nullptr {
__parent_(__x, __parent_(__y))
}
if __tree_is_left_child(__y) {
__left_(__parent_(__y), __x)
if __y != __root {
__w = __right_(__parent_(__y))
} else {
__root = __x
} // __w == nullptr
} else {
__right_(__parent_(__y), __x)
// __y can't be root if it is a right child
__w = __left_(__parent_(__y))
}
let __removed_black = __is_black_(__y)
// If we didn't remove __z, do so now by splicing in __y for __z,
// but copy __z's color. This does not impact __x or __w.
if __y != __z {
// __z->__left_ != nulptr but __z->__right_ might == __x == nullptr
__parent_(__y, __parent_(__z))
if __tree_is_left_child(__z) {
__left_(__parent_(__y), __y)
} else {
__right_(__parent_(__y), __y)
}
__left_(__y, __left_(__z))
__parent_(__left_(__y), __y)
__right_(__y, __right_(__z))
if __right_(__y) != .nullptr {
__parent_(__right_(__y), __y)
}
__is_black_(__y, __is_black_(__z))
if __root == __z {
__root = __y
}
}
// There is no need to rebalance if we removed a red, or if we removed
// the last node.
if __removed_black && __root != .nullptr {
// Rebalance:
// __x has an implicit black color (transferred from the removed __y)
// associated with it, no matter what its color is.
// If __x is __root (in which case it can't be null), it is supposed
// to be black anyway, and if it is doubly black, then the double
// can just be ignored.
// If __x is red (in which case it can't be null), then it can absorb
// the implicit black just by setting its color to black.
// Since __y was black and only had one child (which __x points to), __x
// is either red with no children, else null, otherwise __y would have
// different black heights under left and right pointers.
// if (__x == __root || __x != nullptr && !__x->__is_black_)
if __x != .nullptr {
__is_black_(__x, true)
} else {
// Else __x isn't root, and is "doubly black", even though it may
// be null. __w can not be null here, else the parent would
// see a black height >= 2 on the __x side and a black height
// of 1 on the __w side (__w must be a non-null black or a red
// with a non-null black child).
while true {
if !__tree_is_left_child(__w) // if x is left child
{
if !__is_black_(__w) {
__is_black_(__w, true)
__is_black_(__parent_(__w), false)
__tree_left_rotate(__parent_(__w))
// __x is still valid
// reset __root only if necessary
if __root == __left_(__w) {
__root = __w
}
// reset sibling, and it still can't be null
__w = __right_(__left_(__w))
}
// __w->__is_black_ is now true, __w may have null children
if (__left_(__w) == .nullptr || __is_black_(__left_(__w)))
&& (__right_(__w) == .nullptr || __is_black_(__right_(__w)))
{
__is_black_(__w, false)
__x = __parent_(__w)
// __x can no longer be null
if __x == __root || !__is_black_(__x) {
__is_black_(__x, true)
break
}
// reset sibling, and it still can't be null
__w = __tree_is_left_child(__x) ? __right_(__parent_(__x)) : __left_(__parent_(__x))
// continue;
} else // __w has a red child
{
if __right_(__w) == .nullptr || __is_black_(__right_(__w)) {
// __w left child is non-null and red
__is_black_(__left_(__w), true)
__is_black_(__w, false)
__tree_right_rotate(__w)
// __w is known not to be root, so root hasn't changed
// reset sibling, and it still can't be null
__w = __parent_(__w)
}
// __w has a right red child, left child may be null
__is_black_(__w, __is_black_(__parent_(__w)))
__is_black_(__parent_(__w), true)
__is_black_(__right_(__w), true)
__tree_left_rotate(__parent_(__w))
break
}
} else {
if !__is_black_(__w) {
__is_black_(__w, true)
__is_black_(__parent_(__w), false)
__tree_right_rotate(__parent_(__w))
// __x is still valid
// reset __root only if necessary
if __root == __right_(__w) {
__root = __w
}
// reset sibling, and it still can't be null
__w = __left_(__right_(__w))
}
// __w->__is_black_ is now true, __w may have null children
if (__left_(__w) == .nullptr || __is_black_(__left_(__w)))
&& (__right_(__w) == .nullptr || __is_black_(__right_(__w)))
{
__is_black_(__w, false)
__x = __parent_(__w)
// __x can no longer be null
if !__is_black_(__x) || __x == __root {
__is_black_(__x, true)
break
}
// reset sibling, and it still can't be null
__w = __tree_is_left_child(__x) ? __right_(__parent_(__x)) : __left_(__parent_(__x))
// continue;
} else // __w has a red child
{
if __left_(__w) == .nullptr || __is_black_(__left_(__w)) {
// __w right child is non-null and red
__is_black_(__right_(__w), true)
__is_black_(__w, false)
__tree_left_rotate(__w)
// __w is known not to be root, so root hasn't changed
// reset sibling, and it still can't be null
__w = __parent_(__w)
}
// __w has a left red child, right child may be null
__is_black_(__w, __is_black_(__parent_(__w)))
__is_black_(__parent_(__w), true)
__is_black_(__left_(__w), true)
__tree_right_rotate(__parent_(__w))
break
}
}
}
}
}
}
}
import Foundation
@usableFromInline
protocol DistanceProtocol: MemberProtocol & PointerCompareProtocol {}
extension DistanceProtocol {
@usableFromInline
typealias difference_type = Int
@usableFromInline
typealias _InputIter = Int
@inlinable
func __distance(_ __first: _InputIter, _ __last: _InputIter) -> difference_type {
var __first = __first
var __r = 0
while __first != __last {
__first = __tree_next(__first)
__r += 1
}
return __r
}
@inlinable
func ___signed_distance(_ __first: _InputIter, _ __last: _InputIter) -> difference_type {
guard __first != __last else { return 0 }
var (__first, __last) = (__first, __last)
var sign = 1
if ___ptr_comp(__last, __first) {
swap(&__first, &__last)
sign = -1
}
return sign * __distance(__first, __last)
}
}
// Copyright 2025 narumij
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
// This code is based on work originally distributed under the Apache License 2.0 with LLVM Exceptions:
//
// Copyright © 2003-2024 The LLVM Project.
// Licensed under the Apache License, Version 2.0 with LLVM Exceptions.
// The original license can be found at https://llvm.org/LICENSE.txt
//
// This Swift implementation includes modifications and adaptations made by narumij.
import Foundation
@usableFromInline
protocol _MemoizeCacheMiscellaneous {
var _hits: Int { get set }
var _miss: Int { get set }
var count: Int { get }
mutating func ___removeAll(keepingCapacity keepCapacity: Bool)
}
extension _MemoizeCacheMiscellaneous {
@inlinable
var ___info: (hits: Int, miss: Int, maxCount: Int?, currentCount: Int) {
(_hits, _miss, nil, count)
}
@inlinable
mutating func ___clear(keepingCapacity keepCapacity: Bool) {
(_hits, _miss) = (0, 0)
___removeAll(keepingCapacity: keepCapacity)
}
}
@usableFromInline
protocol _MemoizeCacheLRUMiscellaneous: ___RedBlackTreeBase {
var _hits: Int { get set }
var _miss: Int { get set }
var maxCount: Int { get }
var count: Int { get }
}
extension _MemoizeCacheLRUMiscellaneous {
@inlinable
var ___info: (hits: Int, miss: Int, maxCount: Int?, currentCount: Int) {
(_hits, _miss, maxCount != Int.max ? maxCount : nil, count)
}
@inlinable
mutating func ___clear(keepingCapacity keepCapacity: Bool) {
(_hits, _miss) = (0, 0)
___removeAll(keepingCapacity: keepCapacity)
}
}
// Copyright 2024-2025 narumij
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
// This code is based on work originally distributed under the Apache License 2.0 with LLVM Exceptions:
//
// Copyright © 2003-2024 The LLVM Project.
// Licensed under the Apache License, Version 2.0 with LLVM Exceptions.
// The original license can be found at https://llvm.org/LICENSE.txt
//
// This Swift implementation includes modifications and adaptations made by narumij.
import Foundation
public
protocol _ComparableMemoizationCacheProtocol: _MemoizationCacheProtocol, _KeyCustomProtocol
{}
extension _ComparableMemoizationCacheProtocol {
public typealias Base = _MemoizeCacheBase<Self, Return>
public typealias LRU = _MemoizeCacheLRU<Self, Return>
public typealias CoW = _MemoizeCacheCoW<Self, Return>
}
/// メモ化用途向け
///
/// CustomKeyProtocolで比較方法を供給することで、
/// Comparableプロトコル未適合の型を使うことができる
///
/// 辞書としての機能は削いである
@frozen
public struct _MemoizeCacheBase<Custom, Value>
where Custom: _KeyCustomProtocol {
public
typealias Key = Custom.Parameters
public
typealias Value = Value
public
typealias Element = _KeyValueTuple
public
typealias _Key = Key
public
typealias _Value = Value
@usableFromInline
var _storage: Tree.Storage
@usableFromInline
var _hits: Int
@usableFromInline
var _miss: Int
}
extension _MemoizeCacheBase {
@inlinable
@inline(__always)
public init(minimumCapacity: Int = 0) {
_storage = .create(withCapacity: minimumCapacity)
(_hits, _miss) = (0, 0)
}
@inlinable
public subscript(key: Key) -> Value? {
@inline(__always)
mutating get {
if let v = ___value_for(key)?.value {
_hits &+= 1
return v
} else {
_miss &+= 1
return nil
}
}
@inline(__always)
set {
if let newValue {
_ensureCapacity()
_ = _tree.__insert_unique((key, newValue))
}
}
}
@inlinable
public var count: Int { ___count }
@inlinable
public var capacity: Int { ___capacity }
}
extension _MemoizeCacheBase {
/// statistics
///
/// 確保できたcapacity目一杯使う仕様となってます。
/// このため、currentCountはmaxCountを越える場合があります。
@inlinable
public var info: (hits: Int, miss: Int, maxCount: Int?, currentCount: Int) {
___info
}
@inlinable
public mutating func clear(keepingCapacity keepCapacity: Bool = false) {
___clear(keepingCapacity: keepCapacity)
}
}
extension _MemoizeCacheBase: ___RedBlackTreeBase {}
extension _MemoizeCacheBase: ___RedBlackTreeStorageLifetime {}
extension _MemoizeCacheBase: _MemoizeCacheMiscellaneous {}
extension _MemoizeCacheBase: CustomKeyValueComparer {}
// Copyright 2025 narumij
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
// This code is based on work originally distributed under the Apache License 2.0 with LLVM Exceptions:
//
// Copyright © 2003-2024 The LLVM Project.
// Licensed under the Apache License, Version 2.0 with LLVM Exceptions.
// The original license can be found at https://llvm.org/LICENSE.txt
//
// This Swift implementation includes modifications and adaptations made by narumij.
import Foundation
public protocol _MemoizationCacheProtocol {
associatedtype Parameters
associatedtype Return
}
public protocol _HashableMemoizationCacheProtocol: _MemoizationCacheProtocol
where Parameters: Hashable {}
extension _HashableMemoizationCacheProtocol {
public typealias Standard = _MemoizeCacheStandard<Parameters, Return>
}
public
struct _MemoizeCacheStandard<Parameters: Hashable, Return>
{
@inlinable @inline(__always)
public init() {}
@inlinable
public subscript(key: Parameters) -> Return? {
@inline(__always)
mutating get {
if let r = _cache[key] {
_hits += 1
return r
}
_miss += 1
return nil
}
@inline(__always)
set {
_cache[key] = newValue
}
}
@usableFromInline
var _cache: [Parameters: Return] = [:]
@usableFromInline
var _hits: Int = 0
@usableFromInline
var _miss: Int = 0
@inlinable
public var info: (hits: Int, miss: Int, maxCount: Int?, currentCount: Int) {
___info
}
@inlinable
public mutating func clear(keepingCapacity keepCapacity: Bool = false) {
___clear(keepingCapacity: keepCapacity)
}
}
extension _MemoizeCacheStandard: _MemoizeCacheMiscellaneous {
@usableFromInline
var count: Int { _cache.count }
@usableFromInline
mutating func ___removeAll(keepingCapacity keepCapacity: Bool) {
_cache.removeAll(keepingCapacity: keepCapacity)
}
}
// Copyright 2025 narumij
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
// This code is based on work originally distributed under the Apache License 2.0 with LLVM Exceptions:
//
// Copyright © 2003-2024 The LLVM Project.
// Licensed under the Apache License, Version 2.0 with LLVM Exceptions.
// The original license can be found at https://llvm.org/LICENSE.txt
//
// This Swift implementation includes modifications and adaptations made by narumij.
import Foundation
/// メモ化用途向け、LRU (least recently used) cache 動作
/// https://en.wikipedia.org/wiki/Cache_replacement_policies#Least_Recently_Used_(LRU)
///
/// InlineMemoize動作用。CoWがないので注意
@frozen
public struct _MemoizeCacheLRU<Custom, Value>
where Custom: _KeyCustomProtocol {
public
typealias Key = Custom.Parameters
public
typealias Value = Value
public
typealias KeyValue = _LinkingKeyValueTuple
public
typealias Element = KeyValue
public
typealias _Key = Key
public
typealias _Value = Value
@usableFromInline
var _storage: Tree.Storage
public let maxCount: Int
@usableFromInline
var _rankHighest: _NodePtr
@usableFromInline
var _rankLowest: _NodePtr
@usableFromInline
var _hits: Int
@usableFromInline
var _miss: Int
}
extension _MemoizeCacheLRU {
@inlinable
@inline(__always)
public init(minimumCapacity: Int = 0, maxCount: Int = Int.max) {
_storage = .create(withCapacity: minimumCapacity)
self.maxCount = maxCount
(_rankHighest, _rankLowest) = (.nullptr, .nullptr)
(_hits, _miss) = (0, 0)
}
@inlinable
public subscript(key: Key) -> Value? {
@inline(__always)
mutating get {
let __ptr = _tree.find(key)
if ___is_null_or_end(__ptr) {
_miss &+= 1
return nil
}
_hits &+= 1
___prepend(___pop(__ptr))
return _tree[__ptr].value
}
@inline(__always)
set {
if let newValue {
if _tree.count < maxCount {
// 無条件で更新するとサイズが安定せず、増加してしまう恐れがある
_ensureCapacity(limit: maxCount)
}
if _tree.count == maxCount {
___remove(at: ___popRankLowest())
}
var __parent = _NodePtr.nullptr
let __child = _tree.__find_equal(&__parent, key)
if _tree.__ptr_(__child) == .nullptr {
let __h = _tree.__construct_node((key, .nullptr, .nullptr, newValue))
_tree.__insert_node_at(__parent, __child, __h)
___prepend(__h)
}
}
}
}
@inlinable
public var count: Int { ___count }
@inlinable
public var capacity: Int { ___capacity }
}
extension _MemoizeCacheLRU {
/// statistics
///
/// 確保できたcapacity目一杯使う仕様となってます。
/// このため、currentCountはmaxCountを越える場合があります。
@inlinable
public var info: (hits: Int, miss: Int, maxCount: Int?, currentCount: Int) {
___info
}
@inlinable
public mutating func clear(keepingCapacity keepCapacity: Bool = false) {
___clear(keepingCapacity: keepCapacity)
}
}
extension _MemoizeCacheLRU: ___LRULinkList {}
extension _MemoizeCacheLRU: ___RedBlackTreeStorageLifetime {}
extension _MemoizeCacheLRU: _MemoizeCacheLRUMiscellaneous {}
extension _MemoizeCacheLRU: CustomKeyValueComparer {}
// Copyright 2025 narumij
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
// This code is based on work originally distributed under the Apache License 2.0 with LLVM Exceptions:
//
// Copyright © 2003-2024 The LLVM Project.
// Licensed under the Apache License, Version 2.0 with LLVM Exceptions.
// The original license can be found at https://llvm.org/LICENSE.txt
//
// This Swift implementation includes modifications and adaptations made by narumij.
import Foundation
/// メモ化用途向け、LRU (least recently used) cache 動作
/// https://en.wikipedia.org/wiki/Cache_replacement_policies#Least_Recently_Used_(LRU)
@frozen
public struct _MemoizeCacheCoW<Custom, Value>
where Custom: _KeyCustomProtocol {
public
typealias Key = Custom.Parameters
public
typealias Value = Value
public
typealias KeyValue = _LinkingKeyValueTuple
public
typealias Element = KeyValue
public
typealias _Key = Key
public
typealias _Value = Value
@usableFromInline
var _storage: Tree.Storage
public let maxCount: Int
@usableFromInline
var _rankHighest: _NodePtr
@usableFromInline
var _rankLowest: _NodePtr
@usableFromInline
var _hits: Int
@usableFromInline
var _miss: Int
}
extension _MemoizeCacheCoW {
@inlinable
@inline(__always)
public init(minimumCapacity: Int = 0, maxCount: Int = Int.max) {
_storage = .create(withCapacity: minimumCapacity)
self.maxCount = maxCount
(_rankHighest, _rankLowest) = (.nullptr, .nullptr)
(_hits, _miss) = (0, 0)
}
@inlinable
public subscript(key: Key) -> Value? {
@inline(__always)
mutating get {
let __ptr = _tree.find(key)
if ___is_null_or_end(__ptr) {
_miss &+= 1
return nil
}
_hits &+= 1
___prepend(___pop(__ptr))
return _tree[__ptr].value
}
@inline(__always)
set {
if let newValue {
if _tree.count < maxCount {
// 無条件で更新するとサイズが安定せず、増加してしまう恐れがある
_ensureUniqueAndCapacity(limit: maxCount)
}
if _tree.count == maxCount {
___remove(at: ___popRankLowest())
}
var __parent = _NodePtr.nullptr
let __child = _tree.__find_equal(&__parent, key)
if _tree.__ptr_(__child) == .nullptr {
let __h = _tree.__construct_node((key, .nullptr, .nullptr, newValue))
_tree.__insert_node_at(__parent, __child, __h)
___prepend(__h)
}
}
}
}
@inlinable public var count: Int { ___count }
@inlinable public var capacity: Int { ___capacity }
}
extension _MemoizeCacheCoW {
/// statistics
///
/// 確保できたcapacity目一杯使う仕様となってます。
/// このため、currentCountはmaxCountを越える場合があります。
@inlinable
public var info: (hits: Int, miss: Int, maxCount: Int?, currentCount: Int) {
___info
}
@inlinable
public mutating func clear(keepingCapacity keepCapacity: Bool = false) {
___clear(keepingCapacity: keepCapacity)
}
}
extension _MemoizeCacheCoW: ___RedBlackTreeStorageLifetime {}
extension _MemoizeCacheCoW: ___LRULinkList {}
extension _MemoizeCacheCoW: _MemoizeCacheLRUMiscellaneous {}
extension _MemoizeCacheCoW: CustomKeyValueComparer {}
// Copyright 2025 narumij
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
// This code is based on work originally distributed under the Apache License 2.0 with LLVM Exceptions:
//
// Copyright © 2003-2024 The LLVM Project.
// Licensed under the Apache License, Version 2.0 with LLVM Exceptions.
// The original license can be found at https://llvm.org/LICENSE.txt
//
// This Swift implementation includes modifications and adaptations made by narumij.
import Foundation
extension KeyValueComparer {
public typealias _LinkingKeyValueTuple = (key: _Key, prev: _NodePtr, next: _NodePtr, value: _Value)
}
extension KeyValueComparer where Element == _LinkingKeyValueTuple {
@inlinable @inline(__always)
public static func __key(_ element: Element) -> _Key { element.key }
@inlinable @inline(__always)
static func __value(_ element: Element) -> _Value { element.value }
}
@usableFromInline
protocol ___LRULinkList: ___RedBlackTreeBase, KeyValueComparer
where Element == _LinkingKeyValueTuple {
associatedtype Value
var _tree: Tree { get }
var _rankHighest: _NodePtr { get set }
var _rankLowest: _NodePtr { get set }
var _hits: Int { get set }
var _miss: Int { get set }
var maxCount: Int { get }
var count: Int { get }
}
extension ___LRULinkList {
@inlinable
mutating func ___prepend(_ __p: _NodePtr) {
if _rankHighest == .nullptr {
_tree[__p].next = .nullptr
_tree[__p].prev = .nullptr
_rankLowest = __p
_rankHighest = __p
} else {
_tree[_rankHighest].prev = __p
_tree[__p].next = _rankHighest
_tree[__p].prev = .nullptr
_rankHighest = __p
}
}
@inlinable
mutating func ___pop(_ __p: _NodePtr) -> _NodePtr {
assert(
__p == _rankHighest || _tree[__p].next != .nullptr || _tree[__p].prev != .nullptr,
"did not contain \(__p) ptr.")
defer {
let prev = _tree[__p].prev
let next = _tree[__p].next
if prev != .nullptr {
_tree[prev].next = next
} else {
_rankHighest = next
}
if next != .nullptr {
_tree[next].prev = prev
} else {
_rankLowest = prev
}
}
return __p
}
@inlinable
mutating func ___popRankLowest() -> _NodePtr {
defer {
if _rankLowest != .nullptr {
_rankLowest = _tree[_rankLowest].prev
}
if _rankLowest != .nullptr {
_tree[_rankLowest].next = .nullptr
} else {
_rankHighest = .nullptr
}
}
return _rankLowest
}
}
// Copyright 2024 narumij
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
// This code is based on work originally distributed under the Apache License 2.0 with LLVM Exceptions:
//
// Copyright © 2003-2024 The LLVM Project.
// Licensed under the Apache License, Version 2.0 with LLVM Exceptions.
// The original license can be found at https://llvm.org/LICENSE.txt
//
// This Swift implementation includes modifications and adaptations made by narumij.
import Foundation
/// `RedBlackTreeSet` は、`Element` 型の要素を一意に格納するための
/// 赤黒木（Red-Black Tree）ベースの集合型です。
///
/// ### 使用例
/// ```swift
/// var set: RedBlackTreeSet = [3, 1, 4, 1, 5, 9]
/// print(set) // 出力例: [1, 3, 4, 5, 9]
///
/// set.insert(2)
/// print(set.contains(2)) // 出力例: true
///
/// // 要素の削除
/// set.remove(9)
/// print(set) // 出力例: [1, 2, 3, 4, 5]
///
/// // イテレーション
/// for element in set {
/// print(element)
/// }
/// ```
/// - Important: `RedBlackTreeSet` はスレッドセーフではありません。
@frozen
public struct RedBlackTreeSet<Element: Comparable> {
public
typealias Element = Element
/// `Index` は `RedBlackTreeSet` 内の要素を参照するための型です。
///
/// `Collection` プロトコルに準拠するために用意されており、
/// `startIndex` から `endIndex` の範囲でシーケンシャルに要素を走査できます。
/// また、`index(before:)` や `index(after:)` などのメソッドを使用することで、
/// インデックスを前後に移動できます。
///
/// - Important: `Index` はコレクションの状態が変化（挿入・削除など）すると無効に
/// なる場合があります。無効なインデックスを使用するとランタイムエラーや
/// 不正な参照が発生する可能性があるため注意してください。
///
/// - SeeAlso: `startIndex`, `endIndex`, `index(before:)`, `index(after:)`
public
typealias Index = Tree.Pointer
public
typealias _Key = Element
@usableFromInline
var _storage: Tree.Storage
}
extension RedBlackTreeSet {
public typealias RawIndex = Tree.RawPointer
}
extension RedBlackTreeSet: ___RedBlackTreeBase {}
extension RedBlackTreeSet: ___RedBlackTreeStorageLifetime {}
extension RedBlackTreeSet: ScalarValueComparer {}
extension RedBlackTreeSet {
@inlinable @inline(__always)
public init() {
self.init(minimumCapacity: 0)
}
@inlinable @inline(__always)
public init(minimumCapacity: Int) {
_storage = .create(withCapacity: minimumCapacity)
}
}
extension RedBlackTreeSet {
/// - Complexity: O(*n* log *n*)
@inlinable
public init<Source>(_ sequence: __owned Source)
where Element == Source.Element, Source: Sequence {
let count = (sequence as? (any Collection))?.count
var tree: Tree = .create(minimumCapacity: count ?? 0)
// 初期化直後はO(1)
var (__parent, __child) = tree.___max_ref()
// ソートの計算量がO(*n* log *n*)
for __k in sequence.sorted() {
if count == nil {
Tree.ensureCapacity(tree: &tree)
}
if __parent == .end || tree[__parent] != __k {
// バランシングの計算量がO(log *n*)
(__parent, __child) = tree.___emplace_hint_right(__parent, __child, __k)
assert(tree.__tree_invariant(tree.__root()))
}
}
self._storage = .init(__tree: tree)
}
}
extension RedBlackTreeSet {
/// - Complexity: O(*n* log *n*)
@inlinable
public init<R>(_ range: __owned R)
where R: RangeExpression, R: Collection, R.Element == Element {
precondition(range is Range<Element> || range is ClosedRange<Element>)
let tree: Tree = .create(minimumCapacity: range.count)
// 初期化直後はO(1)
var (__parent, __child) = tree.___max_ref()
for __k in range {
// バランシングの計算量がO(log *n*)
(__parent, __child) = tree.___emplace_hint_right(__parent, __child, __k)
}
assert(tree.__tree_invariant(tree.__root()))
self._storage = .init(__tree: tree)
}
}
extension RedBlackTreeSet {
/// - Complexity: O(1)
@inlinable
public var isEmpty: Bool {
___is_empty
}
/// - Complexity: O(1)
@inlinable
public var capacity: Int {
___capacity
}
}
extension RedBlackTreeSet {
@inlinable
public mutating func reserveCapacity(_ minimumCapacity: Int) {
_ensureUniqueAndCapacity(to: minimumCapacity)
}
}
extension RedBlackTreeSet {
/// - Complexity: O(log *n*)
@discardableResult
@inlinable
public mutating func insert(_ newMember: Element) -> (
inserted: Bool, memberAfterInsert: Element
) {
_ensureUniqueAndCapacity()
let (__r, __inserted) = _tree.__insert_unique(newMember)
return (__inserted, __inserted ? newMember : _tree[__r])
}
/// - Complexity: O(log *n*)
@discardableResult
@inlinable
public mutating func update(with newMember: Element) -> Element? {
_ensureUniqueAndCapacity()
let (__r, __inserted) = _tree.__insert_unique(newMember)
guard !__inserted else { return nil }
let oldMember = _tree[__r]
_tree[__r] = newMember
return oldMember
}
/// - Complexity: O(log *n*)
@discardableResult
@inlinable
public mutating func remove(_ member: Element) -> Element? {
_ensureUnique()
return _tree.___erase_unique(member) ? member : nil
}
/// - Important: 削除後は、これまで使用していたインデックスが無効になります。
///
/// - Complexity: O(log *n*)
@inlinable
@discardableResult
public mutating func remove(at index: Index) -> Element {
_ensureUnique()
guard let element = ___remove(at: index.rawValue) else {
fatalError(.invalidIndex)
}
return element
}
/// - Important: 削除後は、これまで使用していたインデックスが無効になります。
///
/// - Complexity: O(log *n*)
@inlinable
@discardableResult
public mutating func remove(at index: RawIndex) -> Element {
_ensureUnique()
guard let element = ___remove(at: index.rawValue) else {
fatalError(.invalidIndex)
}
return element
}
/// - Complexity: O(log *n*)
@inlinable
@discardableResult
public mutating func removeFirst() -> Element {
guard !isEmpty else {
preconditionFailure(.emptyFirst)
}
return remove(at: startIndex)
}
/// - Complexity: O(log *n*)
@inlinable
@discardableResult
public mutating func removeLast() -> Element {
guard !isEmpty else {
preconditionFailure(.emptyLast)
}
return remove(at: index(before: endIndex))
}
/// 指定した半開区間（`lhs ..< rhs`）に含まれる要素をすべて削除します。
///
/// - Parameter range: `lhs`（含む）から `rhs`（含まない）までを表す `Range`
/// で、削除対象の要素範囲を示します。
/// 範囲が逆転している場合（`lhs >= rhs`）や、木の要素範囲外を指している場合などの
/// “無効な” 状態では動作が未定義となります。
///
/// - Complexity: O(log *n* + *k*)
///
/// - Important: 削除後は、これまで使用していたインデックスが無効になります。
///
/// ### 使用例
/// ```swift
/// var treeSet = RedBlackTreeSet([0,1,2,3,4,5,6])
/// let startIdx = treeSet.lowerBound(2)
/// let endIdx = treeSet.lowerBound(5)
/// // [2, 3, 4] の範囲を削除したい
/// treeSet.removeSubrange(.init(lhs: startIdx, rhs: endIdx))
/// // 結果: treeSet = [0,1,5,6]
/// ```
@inlinable
public mutating func removeSubrange(_ range: Range<Index>) {
_ensureUnique()
___remove(from: range.lowerBound.rawValue, to: range.upperBound.rawValue)
}
/// - Complexity: O(1)
@inlinable
public mutating func removeAll(keepingCapacity keepCapacity: Bool = false) {
_ensureUnique()
___removeAll(keepingCapacity: keepCapacity)
}
}
extension RedBlackTreeSet {
/// - Complexity: O(log *n* + *k*)
@inlinable
@inline(__always)
public mutating func remove(contentsOf elementRange: Range<Element>) {
_ensureUnique()
let lower = lowerBound(elementRange.lowerBound).rawValue
let upper = lowerBound(elementRange.upperBound).rawValue
___remove(from: lower, to: upper)
}
@inlinable
@inline(__always)
public mutating func remove(contentsOf elementRange: ClosedRange<Element>) {
_ensureUnique()
let lower = lowerBound(elementRange.lowerBound).rawValue
let upper = upperBound(elementRange.upperBound).rawValue
___remove(from: lower, to: upper)
}
}
extension RedBlackTreeSet {
/// - Complexity: O(log *n*)
@inlinable
public func contains(_ member: Element) -> Bool {
___contains(member)
}
/// - Complexity: O(log *n*)
@inlinable
public func min() -> Element? {
___min()
}
/// - Complexity: O(log *n*)
@inlinable
public func max() -> Element? {
___max()
}
}
extension RedBlackTreeSet: ExpressibleByArrayLiteral {
@inlinable
public init(arrayLiteral elements: Element...) {
self.init(elements)
}
}
extension RedBlackTreeSet {
/// `lowerBound(_:)` は、指定した要素 `member` 以上の値が格納されている
/// 最初の位置（`Index`）を返します。
///
/// たとえば、ソートされた `[1, 3, 5, 7, 9]` があるとき、
/// - `lowerBound(0)` は最初の要素 `1` の位置を返します。（つまり `startIndex`）
/// - `lowerBound(3)` は要素 `3` の位置を返します。
/// - `lowerBound(4)` は要素 `5` の位置を返します。（`4` 以上で最初に出現する値が `5`）
/// - `lowerBound(10)` は `endIndex` を返します。
///
/// - Parameter member: 二分探索で検索したい要素
/// - Returns: 指定した要素 `member` 以上の値が格納されている先頭の `Index`
/// - Complexity: O(log *n*)
@inlinable
public func lowerBound(_ member: Element) -> Index {
___index_lower_bound(member)
}
/// `upperBound(_:)` は、指定した要素 `member` より大きい値が格納されている
/// 最初の位置（`Index`）を返します。
///
/// たとえば、ソートされた `[1, 3, 5, 5, 7, 9]` があるとき、
/// - `upperBound(3)` は要素 `5` の位置を返します。
/// （`3` より大きい値が最初に現れる場所）
/// - `upperBound(5)` は要素 `7` の位置を返します。
/// （`5` と等しい要素は含まないため、`5` の直後）
/// - `upperBound(9)` は `endIndex` を返します。
///
/// - Parameter member: 二分探索で検索したい要素
/// - Returns: 指定した要素 `member` より大きい値が格納されている先頭の `Index`
/// - Complexity: O(log *n*)
@inlinable
public func upperBound(_ member: Element) -> Index {
___index_upper_bound(member)
}
}
extension RedBlackTreeSet {
/// - Complexity: O(1)
@inlinable
public var first: Element? {
isEmpty ? nil : self[startIndex]
}
/// - Complexity: O(log *n*)
@inlinable
public var last: Element? {
isEmpty ? nil : self[index(before: .end(_tree))]
}
/// - Complexity: O(*n*)
@inlinable
public func first(where predicate: (Element) throws -> Bool) rethrows -> Element? {
try ___first(where: predicate)
}
/// - Complexity: O(log *n*)
@inlinable
public func firstIndex(of member: Element) -> Index? {
___first_index(of: member)
}
/// - Complexity: O(*n*)
@inlinable
public func firstIndex(where predicate: (Element) throws -> Bool) rethrows -> Index? {
try ___first_index(where: predicate)
}
}
extension RedBlackTreeSet {
/// - Complexity: O(*n*)
@inlinable
public func sorted() -> [Element] {
_tree.___sorted
}
}
extension RedBlackTreeSet: CustomStringConvertible, CustomDebugStringConvertible {
@inlinable
public var description: String {
"[\((map {"\($0)"} as [String]).joined(separator: ", "))]"
}
@inlinable
public var debugDescription: String {
"RedBlackTreeSet(\(description))"
}
}
// MARK: - Equatable
extension RedBlackTreeSet: Equatable {
/// - Complexity: O(*n*)
@inlinable
public static func == (lhs: Self, rhs: Self) -> Bool {
lhs.___equal_with(rhs)
}
}
// MARK: - Sequence
extension RedBlackTreeSet: Sequence {
@inlinable
@inline(__always)
public func forEach(_ body: (Element) throws -> Void) rethrows {
try _tree.___for_each_(body)
}
@frozen
public struct Iterator: IteratorProtocol {
@usableFromInline
internal var _iterator: Tree.Iterator
@inlinable
@inline(__always)
internal init(_base: RedBlackTreeSet) {
self._iterator = _base._tree.makeIterator()
}
@inlinable
@inline(__always)
public mutating func next() -> Element? {
return self._iterator.next()
}
}
@inlinable
@inline(__always)
public __consuming func makeIterator() -> Iterator {
return Iterator(_base: self)
}
#if false
@inlinable
@inline(__always)
public func enumerated() -> AnySequence<EnumElement> {
AnySequence { _tree.makeEnumIterator() }
}
#else
@inlinable
@inline(__always)
public func enumerated() -> EnumuratedSequence {
EnumuratedSequence(_subSequence: _tree.enumeratedSubsequence())
}
#endif
@inlinable
@inline(__always)
public func indices() -> IndexSequence {
IndexSequence(_subSequence: _tree.indexSubsequence())
}
}
// MARK: - BidirectionalCollection
extension RedBlackTreeSet: BidirectionalCollection {
@inlinable
@inline(__always)
public var startIndex: Index {
___index_start()
}
@inlinable
@inline(__always)
public var endIndex: Index {
___index_end()
}
@inlinable
@inline(__always)
public var count: Int {
___count
}
@inlinable
@inline(__always)
public func distance(from start: Index, to end: Index) -> Int {
___distance(from: start.rawValue, to: end.rawValue)
}
@inlinable
@inline(__always)
public func index(after i: Index) -> Index {
___index(after: i.rawValue)
}
@inlinable
@inline(__always)
public func formIndex(after i: inout Index) {
___form_index(after: &i.rawValue)
}
@inlinable
@inline(__always)
public func index(before i: Index) -> Index {
___index(before: i.rawValue)
}
@inlinable
@inline(__always)
public func formIndex(before i: inout Index) {
___form_index(before: &i.rawValue)
}
@inlinable
@inline(__always)
public func index(_ i: Index, offsetBy distance: Int) -> Index {
___index(i.rawValue, offsetBy: distance)
}
@inlinable
@inline(__always)
public func formIndex(_ i: inout Index, offsetBy distance: Int) {
___form_index(&i.rawValue, offsetBy: distance)
}
@inlinable
@inline(__always)
public func index(_ i: Index, offsetBy distance: Int, limitedBy limit: Index) -> Index? {
___index(i.rawValue, offsetBy: distance, limitedBy: limit.rawValue)
}
@inlinable
@inline(__always)
public func formIndex(_ i: inout Index, offsetBy distance: Int, limitedBy limit: Index)
-> Bool
{
___form_index(&i.rawValue, offsetBy: distance, limitedBy: limit.rawValue)
}
@inlinable
@inline(__always)
public subscript(position: Index) -> Element {
return _tree[position.rawValue]
}
@inlinable
@inline(__always)
public subscript(position: RawIndex) -> Element {
return _tree[position.rawValue]
}
@inlinable
public subscript(bounds: Range<Index>) -> SubSequence {
SubSequence(
_subSequence:
_tree.subsequence(
from: bounds.lowerBound.rawValue,
to: bounds.upperBound.rawValue)
)
}
@inlinable
public subscript(bounds: Range<Element>) -> SubSequence {
SubSequence(
_subSequence:
_tree.subsequence(
from: ___ptr_lower_bound(bounds.lowerBound),
to: ___ptr_lower_bound(bounds.upperBound)))
}
@inlinable
public subscript(bounds: ClosedRange<Element>) -> SubSequence {
SubSequence(
_subSequence:
_tree.subsequence(
from: ___ptr_lower_bound(bounds.lowerBound),
to: ___ptr_upper_bound(bounds.upperBound)))
}
}
// MARK: - SubSequence
extension RedBlackTreeSet {
@frozen
public struct SubSequence {
@usableFromInline
internal typealias _SubSequence = Tree.SubSequence
@usableFromInline
internal let _subSequence: _SubSequence
@inlinable
init(_subSequence: _SubSequence) {
self._subSequence = _subSequence
}
}
}
extension RedBlackTreeSet.SubSequence {
public typealias Base = RedBlackTreeSet
public typealias SubSequence = Self
public typealias Index = Base.Index
public typealias RawIndex = Base.RawIndex
public typealias Element = Base.Element
public typealias EnumuratedSequence = Base.EnumuratedSequence
public typealias IndexSequence = Base.IndexSequence
}
extension RedBlackTreeSet.SubSequence: Sequence {
public struct Iterator: IteratorProtocol {
@usableFromInline
internal var _iterator: _SubSequence.Iterator
@inlinable
@inline(__always)
internal init(_ _iterator: _SubSequence.Iterator) {
self._iterator = _iterator
}
@inlinable
@inline(__always)
public mutating func next() -> Element? {
_iterator.next()
}
}
@inlinable
@inline(__always)
public __consuming func makeIterator() -> Iterator {
Iterator(_subSequence.makeIterator())
}
#if false
@inlinable
@inline(__always)
public func enumerated() -> AnySequence<EnumElement> {
AnySequence {
tree.makeEnumeratedIterator(start: startIndex.rawValue, end: endIndex.rawValue)
}
}
#else
@inlinable
@inline(__always)
public func enumerated() -> EnumuratedSequence {
EnumuratedSequence(
_subSequence: _tree.enumeratedSubsequence(from: startIndex.rawValue, to: endIndex.rawValue))
}
#endif
@inlinable
@inline(__always)
public func indices() -> IndexSequence {
IndexSequence(
_subSequence: _tree.indexSubsequence(from: startIndex.rawValue, to: endIndex.rawValue))
}
}
extension RedBlackTreeSet.SubSequence: ___RedBlackTreeSubSequenceBase { }
extension RedBlackTreeSet.SubSequence: BidirectionalCollection {
@inlinable
@inline(__always)
public var startIndex: Index {
___start_index
}
@inlinable
@inline(__always)
public var endIndex: Index {
___end_index
}
@inlinable
@inline(__always)
public var count: Int {
___count
}
@inlinable
@inline(__always)
public func forEach(_ body: (Element) throws -> Void) rethrows {
try ___for_each(body)
}
@inlinable
@inline(__always)
public func distance(from start: Index, to end: Index) -> Int {
___distance(from: start, to: end)
}
@inlinable
@inline(__always)
public func index(after i: Index) -> Index {
___index(after: i)
}
@inlinable
@inline(__always)
public func formIndex(after i: inout Index) {
___form_index(after: &i)
}
@inlinable
@inline(__always)
public func index(before i: Index) -> Index {
___index(before: i)
}
@inlinable
@inline(__always)
public func formIndex(before i: inout Index) {
___form_index(before: &i)
}
@inlinable
@inline(__always)
public func index(_ i: Index, offsetBy distance: Int) -> Index {
___index(i, offsetBy: distance)
}
@inlinable
@inline(__always)
public func formIndex(_ i: inout Index, offsetBy distance: Int) {
___form_index(&i, offsetBy: distance)
}
@inlinable
@inline(__always)
public func index(_ i: Index, offsetBy distance: Int, limitedBy limit: Index) -> Index? {
___index(i, offsetBy: distance, limitedBy: limit)
}
@inlinable
@inline(__always)
public func formIndex(_ i: inout Index, offsetBy distance: Int, limitedBy limit: Index)
-> Bool
{
___form_index(&i, offsetBy: distance, limitedBy: limit)
}
@inlinable
@inline(__always)
public subscript(position: Index) -> Element {
_subSequence[position.rawValue]
}
@inlinable
@inline(__always)
public subscript(position: RawIndex) -> Element {
_subSequence[position.rawValue]
}
@inlinable
public subscript(bounds: Range<Index>) -> SubSequence {
SubSequence(
_subSequence:
_subSequence[bounds.lowerBound..<bounds.upperBound])
}
}
// MARK: - Enumerated Sequence
extension RedBlackTreeSet {
@frozen
public struct EnumuratedSequence {
public typealias Enumurated = Tree.Enumerated
@usableFromInline
internal typealias _SubSequence = Tree.EnumSequence
@usableFromInline
internal let _subSequence: _SubSequence
@inlinable
init(_subSequence: _SubSequence) {
self._subSequence = _subSequence
}
}
}
extension RedBlackTreeSet.EnumuratedSequence: Sequence {
public struct Iterator: IteratorProtocol {
@usableFromInline
internal var _iterator: _SubSequence.Iterator
@inlinable
@inline(__always)
internal init(_ _iterator: _SubSequence.Iterator) {
self._iterator = _iterator
}
@inlinable
@inline(__always)
public mutating func next() -> Enumurated? {
_iterator.next()
}
}
@inlinable
@inline(__always)
public __consuming func makeIterator() -> Iterator {
Iterator(_subSequence.makeIterator())
}
}
extension RedBlackTreeSet.EnumuratedSequence {
@inlinable
@inline(__always)
public func forEach(_ body: (Enumurated) throws -> Void) rethrows {
try _subSequence.forEach(body)
}
}
// MARK: - Index Sequence
extension RedBlackTreeSet {
@frozen
public struct IndexSequence {
public typealias RawPointer = Tree.RawPointer
@usableFromInline
internal typealias _SubSequence = Tree.IndexSequence
@usableFromInline
internal let _subSequence: _SubSequence
@inlinable
init(_subSequence: _SubSequence) {
self._subSequence = _subSequence
}
}
}
extension RedBlackTreeSet.IndexSequence: Sequence {
public struct Iterator: IteratorProtocol {
@usableFromInline
internal var _iterator: _SubSequence.Iterator
@inlinable
@inline(__always)
internal init(_ _iterator: _SubSequence.Iterator) {
self._iterator = _iterator
}
@inlinable
@inline(__always)
public mutating func next() -> RawPointer? {
_iterator.next()
}
}
@inlinable
@inline(__always)
public __consuming func makeIterator() -> Iterator {
Iterator(_subSequence.makeIterator())
}
}
extension RedBlackTreeSet.IndexSequence {
@inlinable
@inline(__always)
public func forEach(_ body: (RawPointer) throws -> Void) rethrows {
try _subSequence.forEach(body)
}
}
// MARK: -
extension RedBlackTreeSet {
@inlinable
@inline(__always)
public func isValid(index: Index) -> Bool {
_tree.___is_valid_index(index.rawValue)
}
@inlinable
@inline(__always)
public func isValid(index: RawIndex) -> Bool {
_tree.___is_valid_index(index.rawValue)
}
}
extension RedBlackTreeSet.SubSequence {
@inlinable
@inline(__always)
public func isValid(index i: Index) -> Bool {
_subSequence.___is_valid_index(index: i.rawValue)
}
@inlinable
@inline(__always)
public func isValid(index i: RawIndex) -> Bool {
_subSequence.___is_valid_index(index: i.rawValue)
}
}
// MARK: -
extension RedBlackTreeSet {
@inlinable
@inline(__always)
public mutating func insert(contentsOf other: RedBlackTreeSet<Element>) {
_ensureUniqueAndCapacity(to: count + other.count)
_tree.__node_handle_merge_unique(other._tree)
}
@inlinable
@inline(__always)
public mutating func insert(contentsOf other: RedBlackTreeMultiset<Element>) {
_ensureUniqueAndCapacity(to: count + other.count)
_tree.__node_handle_merge_unique(other._tree)
}
@inlinable
@inline(__always)
public mutating func insert<S>(contentsOf other: S) where S: Sequence, S.Element == Element {
other.forEach { insert($0) }
}
}
#if PERFOMANCE_CHECK
extension RedBlackTreeSet {
// 旧初期化実装
// 性能比較用にのこしてある
/// - Complexity: O(log *n*)
@inlinable
public init<Source>(_sequence sequence: __owned Source)
where Element == Source.Element, Source: Sequence {
let count = (sequence as? (any Collection))?.count
var tree: Tree = .create(minimumCapacity: count ?? 0)
for __k in sequence {
if count == nil {
Tree.ensureCapacity(tree: &tree)
}
var __parent = _NodePtr.nullptr
// 検索の計算量がO(log *n*)
let __child = tree.__find_equal(&__parent, __k)
if tree.__ptr_(__child) == .nullptr {
let __h = tree.__construct_node(__k)
// バランシングの計算量がO(log *n*)
tree.__insert_node_at(__parent, __child, __h)
}
}
self._storage = .init(__tree: tree)
}
}
#endif
// Copyright 2024 narumij
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
// This code is based on work originally distributed under the Apache License 2.0 with LLVM Exceptions:
//
// Copyright © 2003-2024 The LLVM Project.
// Licensed under the Apache License, Version 2.0 with LLVM Exceptions.
// The original license can be found at https://llvm.org/LICENSE.txt
//
// This Swift implementation includes modifications and adaptations made by narumij.
import Foundation
/// `RedBlackTreeMultiset` は、`Element` 型の要素を複数格納するための
/// 赤黒木（Red-Black Tree）ベースのマルチセット型です。
///
/// ### 使用例
/// ```swift
/// var multiset = RedBlackTreeMultiset<Int>()
/// multiset.insert(5)
/// multiset.insert(3)
/// multiset.insert(5) // 重複した要素の挿入
///
/// // 要素の出現回数を確認
/// print(multiset.count(of: 5)) // 出力例: 2
/// print(multiset.count(of: 3)) // 出力例: 1
/// ```
@frozen
public struct RedBlackTreeMultiset<Element: Comparable> {
public
typealias Element = Element
public
typealias Index = Tree.Pointer
public
typealias _Key = Element
@usableFromInline
var _storage: Tree.Storage
}
extension RedBlackTreeMultiset {
public typealias RawIndex = Tree.RawPointer
}
extension RedBlackTreeMultiset: ___RedBlackTreeBase {}
extension RedBlackTreeMultiset: ___RedBlackTreeStorageLifetime {}
extension RedBlackTreeMultiset: ScalarValueComparer {}
extension RedBlackTreeMultiset {
@inlinable @inline(__always)
public init() {
self.init(minimumCapacity: 0)
}
@inlinable @inline(__always)
public init(minimumCapacity: Int) {
_storage = .create(withCapacity: minimumCapacity)
}
}
extension RedBlackTreeMultiset {
/// - Complexity: O(*n* log *n*)
@inlinable
public init<Source>(_ sequence: __owned Source)
where Element == Source.Element, Source: Sequence {
let count = (sequence as? (any Collection))?.count
var tree: Tree = .create(minimumCapacity: count ?? 0)
// 初期化直後はO(1)
var (__parent, __child) = tree.___max_ref()
// ソートの計算量がO(*n* log *n*)
for __k in sequence.sorted() {
if count == nil {
Tree.ensureCapacity(tree: &tree)
}
// バランシングの計算量がO(log *n*)
(__parent, __child) = tree.___emplace_hint_right(__parent, __child, __k)
assert(tree.__tree_invariant(tree.__root()))
}
self._storage = .init(__tree: tree)
}
}
extension RedBlackTreeMultiset {
/// - Complexity: O(*n* log *n*)
@inlinable
public init<R>(_ range: __owned R)
where R: RangeExpression, R: Collection, R.Element == Element {
precondition(range is Range<Element> || range is ClosedRange<Element>)
let tree: Tree = .create(minimumCapacity: range.count)
// 初期化直後はO(1)
var (__parent, __child) = tree.___max_ref()
for __k in range {
// バランシングの計算量がO(log *n*)
(__parent, __child) = tree.___emplace_hint_right(__parent, __child, __k)
}
assert(tree.__tree_invariant(tree.__root()))
self._storage = .init(__tree: tree)
}
}
extension RedBlackTreeMultiset {
/// - 計算量: O(1)
@inlinable
public var isEmpty: Bool {
___is_empty
}
/// - 計算量: O(1)
@inlinable
public var capacity: Int {
___capacity
}
}
extension RedBlackTreeMultiset {
@inlinable
public mutating func reserveCapacity(_ minimumCapacity: Int) {
_ensureUniqueAndCapacity(to: minimumCapacity)
}
}
extension RedBlackTreeMultiset {
/// - Complexity: O(log *n*)
@inlinable
@discardableResult
public mutating func insert(_ newMember: Element) -> (
inserted: Bool, memberAfterInsert: Element
) {
_ensureUniqueAndCapacity()
_ = _tree.__insert_multi(newMember)
return (true, newMember)
}
/// - Complexity: O(log *n*)
@inlinable
@discardableResult
public mutating func remove(_ member: Element) -> Element? {
_strongEnsureUnique()
return _tree.___erase_unique(member) ? member : nil
}
/// - Important: 削除後は、これまで使用していたインデックスが無効になります。
///
/// - Complexity: O(log *n*)
@inlinable
@discardableResult
public mutating func remove(at index: RawIndex) -> Element {
_ensureUnique()
guard let element = ___remove(at: index.rawValue) else {
fatalError(.invalidIndex)
}
return element
}
/// - Important: 削除後は、これまで使用していたインデックスが無効になります。
///
/// - Complexity: O(log *n*)
@inlinable
@discardableResult
public mutating func remove(at index: Index) -> Element {
_ensureUnique()
guard let element = ___remove(at: index.rawValue) else {
fatalError(.invalidIndex)
}
return element
}
/// - Complexity: O(log *n*)
@inlinable
@discardableResult
public mutating func removeFirst() -> Element {
guard !isEmpty else {
preconditionFailure(.emptyFirst)
}
return remove(at: startIndex)
}
/// - Complexity: O(log *n*)
@inlinable
@discardableResult
public mutating func removeLast() -> Element {
guard !isEmpty else {
preconditionFailure(.emptyLast)
}
return remove(at: index(before: endIndex))
}
/// - Complexity: O(log *n* + *k*)
///
/// - Important: 削除後は、これまで使用していたインデックスが無効になります。
@inlinable
public mutating func removeSubrange(_ range: Range<Index>) {
_ensureUnique()
___remove(from: range.lowerBound.rawValue, to: range.upperBound.rawValue)
}
/// - Complexity: O(log *n*)
@inlinable
@discardableResult
public mutating func removeAll(_ member: Element) -> Element? {
_strongEnsureUnique()
return _tree.___erase_multi(member) != 0 ? member : nil
}
/// - Complexity: O(log *n*)
@inlinable
@discardableResult
public mutating func removeAll(_unsafe member: Element) -> Element? {
_ensureUnique()
return _tree.___erase_multi(member) != 0 ? member : nil
}
/// - Complexity: O(1)
@inlinable
public mutating func removeAll(keepingCapacity keepCapacity: Bool = false) {
_ensureUnique()
___removeAll(keepingCapacity: keepCapacity)
}
}
extension RedBlackTreeMultiset {
/// - Complexity: O(log *n* + *k*)
@inlinable
@inline(__always)
public mutating func remove(contentsOf elementRange: Range<Element>) {
let lower = lowerBound(elementRange.lowerBound)
let upper = lowerBound(elementRange.upperBound)
removeSubrange(lower..<upper)
}
@inlinable
@inline(__always)
public mutating func remove(contentsOf elementRange: ClosedRange<Element>) {
let lower = lowerBound(elementRange.lowerBound)
let upper = upperBound(elementRange.upperBound)
removeSubrange(lower..<upper)
}
}
extension RedBlackTreeMultiset {
/// - Complexity: O(*n*)
@inlinable
public func contains(_ member: Element) -> Bool {
___contains(member)
}
/// - Complexity: O(*n*)
@inlinable
public func min() -> Element? {
___min()
}
/// - Complexity: O(*n*)
@inlinable
public func max() -> Element? {
___max()
}
}
extension RedBlackTreeMultiset: ExpressibleByArrayLiteral {
@inlinable
public init(arrayLiteral elements: Element...) {
self.init(elements)
}
}
extension RedBlackTreeMultiset {
/// - Complexity: O(log *n*)
@inlinable
public func lowerBound(_ member: Element) -> Index {
___index_lower_bound(member)
}
/// - Complexity: O(log *n*)
@inlinable
public func upperBound(_ member: Element) -> Index {
___index_upper_bound(member)
}
}
extension RedBlackTreeMultiset {
/// - Complexity: O(1)。
@inlinable
public var first: Element? {
isEmpty ? nil : self[startIndex]
}
/// - Complexity: O(log *n*)
@inlinable
public var last: Element? {
isEmpty ? nil : self[index(before: .end(_tree))]
}
/// - Complexity: O(*n*)
@inlinable
public func first(where predicate: (Element) throws -> Bool) rethrows -> Element? {
try ___first(where: predicate)
}
/// - Complexity: O(log *n*)
@inlinable
public func firstIndex(of member: Element) -> Index? {
___first_index(of: member)
}
/// - Complexity: O(*n*)
@inlinable
public func firstIndex(where predicate: (Element) throws -> Bool) rethrows -> Index? {
try ___first_index(where: predicate)
}
}
extension RedBlackTreeMultiset {
@inlinable
public func sorted() -> [Element] {
_tree.___sorted
}
}
extension RedBlackTreeMultiset {
/// - Complexity: O(log *n* + *k*)
@inlinable
public func count(of element: Element) -> Int {
_tree.__count_multi(element)
}
}
extension RedBlackTreeMultiset: CustomStringConvertible, CustomDebugStringConvertible {
@inlinable
public var description: String {
"[\((map {"\($0)"} as [String]).joined(separator: ", "))]"
}
@inlinable
public var debugDescription: String {
"RedBlackTreeMultiset(\(description))"
}
}
// MARK: - Equatable
extension RedBlackTreeMultiset: Equatable {
@inlinable
public static func == (lhs: Self, rhs: Self) -> Bool {
lhs.___equal_with(rhs)
}
}
// MARK: - Sequence, BidirectionalCollection
extension RedBlackTreeMultiset: Sequence {
@inlinable
@inline(__always)
public func forEach(_ body: (Element) throws -> Void) rethrows {
try _tree.___for_each_(body)
}
@frozen
public struct Iterator: IteratorProtocol {
@usableFromInline
internal var _iterator: Tree.Iterator
@inlinable
@inline(__always)
internal init(_base: RedBlackTreeMultiset) {
self._iterator = _base._tree.makeIterator()
}
@inlinable
@inline(__always)
public mutating func next() -> Element? {
return self._iterator.next()
}
}
@inlinable
@inline(__always)
public __consuming func makeIterator() -> Iterator {
return Iterator(_base: self)
}
#if false
@inlinable
@inline(__always)
public func enumerated() -> AnySequence<EnumElement> {
AnySequence { _tree.makeEnumIterator() }
}
#else
@inlinable
@inline(__always)
public func enumerated() -> EnumuratedSequence {
EnumuratedSequence(_subSequence: _tree.enumeratedSubsequence())
}
#endif
@inlinable
@inline(__always)
public func indices() -> IndexSequence {
IndexSequence(_subSequence: _tree.indexSubsequence())
}
}
extension RedBlackTreeMultiset: BidirectionalCollection {
@inlinable
@inline(__always)
public var startIndex: Index {
___index_start()
}
@inlinable
@inline(__always)
public var endIndex: Index {
___index_end()
}
@inlinable
@inline(__always)
public var count: Int {
___count }
@inlinable
@inline(__always)
public func distance(from start: Index, to end: Index) -> Int {
___distance(from: start.rawValue, to: end.rawValue)
}
@inlinable
@inline(__always)
public func index(after i: Index) -> Index {
___index(after: i.rawValue)
}
@inlinable
@inline(__always)
public func formIndex(after i: inout Index) {
___form_index(after: &i.rawValue)
}
@inlinable
@inline(__always)
public func index(before i: Index) -> Index {
___index(before: i.rawValue)
}
@inlinable
@inline(__always)
public func formIndex(before i: inout Index) {
___form_index(before: &i.rawValue)
}
@inlinable
@inline(__always)
public func index(_ i: Index, offsetBy distance: Int) -> Index {
___index(i.rawValue, offsetBy: distance)
}
@inlinable
@inline(__always)
public func formIndex(_ i: inout Index, offsetBy distance: Int) {
___form_index(&i.rawValue, offsetBy: distance)
}
@inlinable
@inline(__always)
public func index(_ i: Index, offsetBy distance: Int, limitedBy limit: Index) -> Index? {
___index(i.rawValue, offsetBy: distance, limitedBy: limit.rawValue)
}
@inlinable
@inline(__always)
public func formIndex(_ i: inout Index, offsetBy distance: Int, limitedBy limit: Self.Index)
-> Bool
{
___form_index(&i.rawValue, offsetBy: distance, limitedBy: limit.rawValue)
}
@inlinable
@inline(__always)
public subscript(position: Index) -> Element {
return _tree[position.rawValue]
}
@inlinable
@inline(__always)
public subscript(position: RawIndex) -> Element {
return _tree[position.rawValue]
}
@inlinable
public subscript(bounds: Range<Index>) -> SubSequence {
SubSequence(
_subSequence:
_tree.subsequence(
from: bounds.lowerBound.rawValue,
to: bounds.upperBound.rawValue)
)
}
@inlinable
public subscript(bounds: Range<Element>) -> SubSequence {
SubSequence(
_subSequence:
_tree.subsequence(
from: ___ptr_lower_bound(bounds.lowerBound),
to: ___ptr_lower_bound(bounds.upperBound)))
}
@inlinable
public subscript(bounds: ClosedRange<Element>) -> SubSequence {
SubSequence(
_subSequence:
_tree.subsequence(
from: ___ptr_lower_bound(bounds.lowerBound),
to: ___ptr_upper_bound(bounds.upperBound)))
}
}
extension RedBlackTreeMultiset {
@frozen
public struct SubSequence {
@usableFromInline
internal typealias _SubSequence = Tree.SubSequence
@usableFromInline
internal let _subSequence: _SubSequence
@inlinable
init(_subSequence: _SubSequence) {
self._subSequence = _subSequence
}
}
}
extension RedBlackTreeMultiset.SubSequence {
public typealias Base = RedBlackTreeMultiset
public typealias SubSequence = Self
public typealias Index = Base.Index
public typealias RawIndex = Base.RawIndex
public typealias Element = Base.Element
public typealias EnumuratedSequence = Base.EnumuratedSequence
public typealias IndexSequence = Base.IndexSequence
}
extension RedBlackTreeMultiset.SubSequence: Sequence {
public struct Iterator: IteratorProtocol {
@usableFromInline
internal var _iterator: _SubSequence.Iterator
@inlinable
@inline(__always)
internal init(_ _iterator: _SubSequence.Iterator) {
self._iterator = _iterator
}
@inlinable
@inline(__always)
public mutating func next() -> Element? {
_iterator.next()
}
}
@inlinable
@inline(__always)
public __consuming func makeIterator() -> Iterator {
Iterator(_subSequence.makeIterator())
}
#if false
@inlinable
@inline(__always)
public func enumerated() -> AnySequence<EnumElement> {
AnySequence {
tree.makeEnumeratedIterator(start: startIndex.rawValue, end: endIndex.rawValue)
}
}
#else
@inlinable
@inline(__always)
public func enumerated() -> EnumuratedSequence {
EnumuratedSequence(
_subSequence: _tree.enumeratedSubsequence(from: startIndex.rawValue, to: endIndex.rawValue))
}
#endif
@inlinable
@inline(__always)
public func indices() -> IndexSequence {
IndexSequence(
_subSequence: _tree.indexSubsequence(from: startIndex.rawValue, to: endIndex.rawValue))
}
}
extension RedBlackTreeMultiset.SubSequence: ___RedBlackTreeSubSequenceBase { }
extension RedBlackTreeMultiset.SubSequence: BidirectionalCollection {
@inlinable
@inline(__always)
public var startIndex: Index {
___start_index
}
@inlinable
@inline(__always)
public var endIndex: Index {
___end_index
}
@inlinable
@inline(__always)
public var count: Int {
___count
}
@inlinable
@inline(__always)
public func forEach(_ body: (Element) throws -> Void) rethrows {
try ___for_each(body)
}
@inlinable
@inline(__always)
public func distance(from start: Index, to end: Index) -> Int {
___distance(from: start, to: end)
}
@inlinable
@inline(__always)
public func index(after i: Index) -> Index {
___index(after: i)
}
@inlinable
@inline(__always)
public func formIndex(after i: inout Index) {
___form_index(after: &i)
}
@inlinable
@inline(__always)
public func index(before i: Index) -> Index {
___index(before: i)
}
@inlinable
@inline(__always)
public func formIndex(before i: inout Index) {
___form_index(before: &i)
}
@inlinable
@inline(__always)
public func index(_ i: Index, offsetBy distance: Int) -> Index {
___index(i, offsetBy: distance)
}
@inlinable
@inline(__always)
public func formIndex(_ i: inout Index, offsetBy distance: Int) {
___form_index(&i, offsetBy: distance)
}
@inlinable
@inline(__always)
public func index(_ i: Index, offsetBy distance: Int, limitedBy limit: Index) -> Index? {
___index(i, offsetBy: distance, limitedBy: limit)
}
@inlinable
@inline(__always)
public func formIndex(_ i: inout Index, offsetBy distance: Int, limitedBy limit: Index)
-> Bool
{
___form_index(&i, offsetBy: distance, limitedBy: limit)
}
@inlinable
@inline(__always)
public subscript(position: Index) -> Element {
_subSequence[position.rawValue]
}
@inlinable
@inline(__always)
public subscript(position: RawIndex) -> Element {
_subSequence[position.rawValue]
}
@inlinable
public subscript(bounds: Range<Index>) -> SubSequence {
SubSequence(
_subSequence:
_subSequence[bounds.lowerBound..<bounds.upperBound])
}
}
// MARK: - Enumerated Sequence
extension RedBlackTreeMultiset {
@frozen
public struct EnumuratedSequence {
public typealias Enumurated = Tree.Enumerated
@usableFromInline
internal typealias _SubSequence = Tree.EnumSequence
@usableFromInline
internal let _subSequence: _SubSequence
@inlinable
init(_subSequence: _SubSequence) {
self._subSequence = _subSequence
}
}
}
extension RedBlackTreeMultiset.EnumuratedSequence: Sequence {
public struct Iterator: IteratorProtocol {
@usableFromInline
internal var _iterator: _SubSequence.Iterator
@inlinable
@inline(__always)
internal init(_ _iterator: _SubSequence.Iterator) {
self._iterator = _iterator
}
@inlinable
@inline(__always)
public mutating func next() -> Enumurated? {
_iterator.next()
}
}
@inlinable
@inline(__always)
public __consuming func makeIterator() -> Iterator {
Iterator(_subSequence.makeIterator())
}
}
extension RedBlackTreeMultiset.EnumuratedSequence {
@inlinable
@inline(__always)
public func forEach(_ body: (Enumurated) throws -> Void) rethrows {
try _subSequence.forEach(body)
}
}
// MARK: - Index Sequence
extension RedBlackTreeMultiset {
@frozen
public struct IndexSequence {
public typealias RawPointer = Tree.RawPointer
@usableFromInline
internal typealias _SubSequence = Tree.IndexSequence
@usableFromInline
internal let _subSequence: _SubSequence
@inlinable
init(_subSequence: _SubSequence) {
self._subSequence = _subSequence
}
}
}
extension RedBlackTreeMultiset.IndexSequence: Sequence {
public struct Iterator: IteratorProtocol {
@usableFromInline
internal var _iterator: _SubSequence.Iterator
@inlinable
@inline(__always)
internal init(_ _iterator: _SubSequence.Iterator) {
self._iterator = _iterator
}
@inlinable
@inline(__always)
public mutating func next() -> RawPointer? {
_iterator.next()
}
}
@inlinable
@inline(__always)
public __consuming func makeIterator() -> Iterator {
Iterator(_subSequence.makeIterator())
}
}
extension RedBlackTreeMultiset.IndexSequence {
@inlinable
@inline(__always)
public func forEach(_ body: (RawPointer) throws -> Void) rethrows {
try _subSequence.forEach(body)
}
}
// MARK: -
extension RedBlackTreeMultiset {
@inlinable
@inline(__always)
public func isValid(index: Index) -> Bool {
_tree.___is_valid_index(index.rawValue)
}
@inlinable
@inline(__always)
public func isValid(index: RawIndex) -> Bool {
_tree.___is_valid_index(index.rawValue)
}
}
extension RedBlackTreeMultiset.SubSequence {
@inlinable
@inline(__always)
public func isValid(index i: Index) -> Bool {
_subSequence.___is_valid_index(index: i.rawValue)
}
@inlinable
@inline(__always)
public func isValid(index i: RawIndex) -> Bool {
_subSequence.___is_valid_index(index: i.rawValue)
}
}
extension RedBlackTreeMultiset {
@inlinable
@inline(__always)
public mutating func insert(contentsOf other: RedBlackTreeSet<Element>) {
_ensureUniqueAndCapacity(to: count + other.count)
_tree.__node_handle_merge_multi(other._tree)
}
@inlinable
@inline(__always)
public mutating func insert(contentsOf other: RedBlackTreeMultiset<Element>) {
_ensureUniqueAndCapacity(to: count + other.count)
_tree.__node_handle_merge_multi(other._tree)
}
@inlinable
@inline(__always)
public mutating func insert<S>(contentsOf other: S) where S: Sequence, S.Element == Element {
other.forEach { insert($0) }
}
}
提出情報
提出日時
2025-01-27 04:32:19+0900
問題
D - Cross Explosion
ユーザ
narumij
言語
Swift (swift 5.8.1)
得点
400
コード長
287266 Byte
結果
AC
実行時間
274 ms
メモリ
76980 KiB
コンパイルエラー
[0/1] Planning build
Building for production...
[0/2] Compiling _NumericsShims _NumericsShims.c
remark: Incremental compilation has been disabled: it is not compatible with whole module optimization
[2/3] Compiling RealModule AlgebraicField.swift
remark: Incremental compilation has been disabled: it is not compatible with whole module optimization
[4/5] Compiling OrderedCollections _HashTable+Bucket.swift
remark: Incremental compilation has been disabled: it is not compatible with whole module optimization
[6/7] Compiling DequeModule Compatibility.swift
remark: Incremental compilation has been disabled: it is not compatible with whole module optimization
[8/9] Compiling Algorithms AdjacentPairs.swift
remark: Incremental compilation has been disabled: it is not compatible with whole module optimization
[10/11] Compiling Collections Collections.swift
remark: Incremental compilation has been disabled: it is not compatible with whole module optimization
[12/13] Compiling Main main.swift
[13/14] Linking Main
Build complete! (22.55s)
ジャッジ結果
セット名
Sample
All
得点 / 配点
0 / 0
400 / 400
結果
セット名
テストケース
Sample
00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt
All
00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 01_random_00.txt, 01_random_01.txt, 01_random_02.txt, 01_random_03.txt, 01_random_04.txt, 01_random_05.txt, 01_random_06.txt, 01_random_07.txt, 01_random_08.txt, 01_random_09.txt, 01_random_10.txt, 01_random_11.txt, 01_random_12.txt, 01_random_13.txt, 01_random_14.txt, 01_random_15.txt, 01_random_16.txt, 01_random_17.txt, 01_random_18.txt, 01_random_19.txt, 02_all_break_00.txt, 03_hack_00.txt, 03_hack_01.txt
ケース名
結果
実行時間
メモリ
00_sample_00.txt
AC 4 ms
15256 KiB
00_sample_01.txt
AC 4 ms
14960 KiB
00_sample_02.txt
AC 3 ms
15236 KiB
01_random_00.txt
AC 260 ms
51420 KiB
01_random_01.txt
AC 159 ms
50796 KiB
01_random_02.txt
AC 187 ms
51332 KiB
01_random_03.txt
AC 274 ms
51772 KiB
01_random_04.txt
AC 274 ms
47840 KiB
01_random_05.txt
AC 262 ms
50952 KiB
01_random_06.txt
AC 255 ms
51276 KiB
01_random_07.txt
AC 200 ms
51164 KiB
01_random_08.txt
AC 223 ms
72548 KiB
01_random_09.txt
AC 258 ms
46700 KiB
01_random_10.txt
AC 187 ms
52460 KiB
01_random_11.txt
AC 222 ms
47620 KiB
01_random_12.txt
AC 243 ms
56168 KiB
01_random_13.txt
AC 251 ms
47036 KiB
01_random_14.txt
AC 216 ms
46644 KiB
01_random_15.txt
AC 246 ms
46908 KiB
01_random_16.txt
AC 231 ms
46680 KiB
01_random_17.txt
AC 249 ms
56008 KiB
01_random_18.txt
AC 257 ms
46536 KiB
01_random_19.txt
AC 211 ms
46596 KiB
02_all_break_00.txt
AC 166 ms
46568 KiB
03_hack_00.txt
AC 141 ms
76816 KiB
03_hack_01.txt
AC 142 ms
76980 KiB