Submission #62143179
Source Code Expand
import Foundation
//import Algorithms
//import Collections
//import AtCoder
private let main: () = {
do { try Answer() } catch { /* WA */ }
}()
@inlinable
public func Answer() throws {
let (N,M) = (Int.stdin, Int.stdin)
var A = RedBlackTreeMultiset([Int].stdin(columns: N))
var ans = 0
for _ in 0 ..< M {
let b = Int.stdin
let i = A.lowerBound(b)
guard i != A.endIndex else {
ans = -1
break
}
ans += A.remove(at: i)
}
print(ans)
}
// MARK: - 以下連結
import Foundation
// MARK: - Reader
public protocol ScalarIn {
static var stdin: Self { get }
}
public protocol SingleRead {
static func read() throws -> Self
}
public protocol TupleRead: SingleRead {}
public protocol ArrayRead: SingleRead {}
public protocol FullRead: ArrayRead & TupleRead {}
extension Collection where Element: ArrayRead {
@inlinable
static func _read(columns: Int) throws -> [Element] {
try (0..<columns).map { _ in try Element.read() }
}
@inlinable
static func _read(rows: Int) throws -> [Element] {
try (0..<rows).map { _ in try Element.read() }
}
@inlinable @inline(__always)
public static func stdin(columns: Int) -> [Element] {
try! _read(columns: columns)
}
@inlinable @inline(__always)
public static func stdin(rows: Int) -> [Element] {
try! _read(rows: rows)
}
}
extension Collection where Element: Collection, Element.Element: ArrayRead {
@inlinable
static func _read(rows: Int, columns: Int) throws -> [[Element.Element]] {
try (0..<rows).map { _ in try Element._read(columns: columns) }
}
@inlinable @inline(__always)
public static func stdin(rows: Int, columns: Int) -> [[Element.Element]] {
try! _read(rows: rows, columns: columns)
}
}
extension Int: ScalarIn & FullRead {}
extension UInt: ScalarIn & FullRead {}
extension Double: ScalarIn & FullRead {}
extension CInt: ScalarIn & FullRead {}
extension CUnsignedInt: ScalarIn & FullRead {}
extension CLongLong: ScalarIn & FullRead {}
extension CUnsignedLongLong: ScalarIn & FullRead {}
extension String: ScalarIn & TupleRead {}
extension Character: ScalarIn & TupleRead {}
extension UInt8: ScalarIn & TupleRead {}
extension FixedWidthInteger {
@inlinable @inline(__always)
public static func read() throws -> Self { .init(try ATOL.read()!) }
@inlinable @inline(__always)
public static var stdin: Self { try! read() }
}
extension BinaryFloatingPoint {
@inlinable @inline(__always)
public static func read() throws -> Self { .init(try ATOF.read()!) }
@inlinable @inline(__always)
public static var stdin: Self { try! read() }
}
extension String {
@inlinable @inline(__always)
public static func read() throws -> String { ATOS.read() }
@inlinable @inline(__always)
public static var stdin: Self { try! read() }
@inlinable
public static func stdin(columns: Int) -> String { ATOS.read(columns: columns) }
}
extension Array where Element == String {
@inlinable
public static func stdin(rows: Int) -> [String] {
(0..<rows).map { _ in try! .read() }
}
@inlinable
public static func stdin(rows: Int, columns: Int) -> [String] {
(0..<rows).map { _ in .stdin(columns: columns) }
}
}
extension UInt8 {
@inlinable @inline(__always)
public static func read() throws -> UInt8 { ATOB.read(columns: 1).first! }
@inlinable @inline(__always)
public static var stdin: Self { try! read() }
}
extension Array where Element == UInt8 {
@inlinable @inline(__always)
public static func read() throws -> [UInt8] { ATOB.read() }
@inlinable @inline(__always)
public static var stdin: Self { try! read() }
@inlinable
public static func stdin(columns: Int) -> [UInt8] { ATOB.read(columns: columns) }
}
extension Array where Element == [UInt8] {
@inlinable
public static func stdin(rows: Int) -> [[UInt8]] {
(0..<rows).map { _ in try! .read() }
}
@inlinable
public static func stdin(rows: Int, columns: Int) -> [[UInt8]] {
(0..<rows).map { _ in .stdin(columns: columns) }
}
}
extension Character {
@inlinable
public static func read() throws -> Character { Character(String.stdin(columns: 1)) }
@inlinable
public static var stdin: Self { try! read() }
}
extension Array where Element == Character {
@inlinable
public static func read() throws -> [Character] {
try String.read().map { $0 }
}
@inlinable
public static var stdin: Self { try! read() }
@inlinable
public static func stdin(columns: Int) -> [Character] {
String.stdin(columns: columns).map { $0 }
}
}
extension Array where Element == [Character] {
@inlinable
public static func stdin(rows: Int) -> [[Character]] {
(0..<rows).map { _ in try! .read() }
}
@inlinable
public static func stdin(rows: Int, columns: Int) -> [[Character]] {
(0..<rows).map { _ in .stdin(columns: columns) }
}
}
// MARK: - IOReader
@usableFromInline
enum IOReaderError: Swift.Error {
case unexpectedEOF
}
@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) throws -> T? {
var current = 0
return try buffer.withUnsafeMutableBufferPointer { buffer in
buffer.baseAddress![current] = .__readHead()
while buffer.baseAddress![current] != .SP,
buffer.baseAddress![current] != .LF,
buffer.baseAddress![current] != EOF
{
current += 1
let c = getchar_unlocked()
if c == -1 {
throw IOReaderError.unexpectedEOF
}
buffer[current] = numericCast(c)
}
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
protocol IOReaderInstance2 {
associatedtype Element
mutating func next() throws -> Self.Element?
static var instance: Self { get set }
}
extension IOReaderInstance2 {
@inlinable @inline(__always) static func read() throws -> Element! { try instance.next() }
}
@usableFromInline struct ATOL: FixedBufferIOReader, IOReaderInstance2 {
public var buffer = [UInt8](repeating: 0, count: 32)
@inlinable @inline(__always)
public mutating func next() throws -> Int? { try _next { atol($0) } }
public static var instance = Self()
}
@usableFromInline struct ATOF: FixedBufferIOReader, IOReaderInstance2 {
public var buffer = [UInt8](repeating: 0, count: 64)
@inlinable @inline(__always)
public mutating func next() throws -> Double? { try _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() -> [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
// MARK: - sorted set
// Original: https://qiita.com/tatyam/items/492c70ac4c955c055602
// Original Github: https://github.com/tatyam-prime/SortedSet
// ライセンス無し
//class SortedSet(Generic[T]):
enum SortedSetCondition {
// BUCKET_RATIO = 16
// SPLIT_RATIO = 24
static var BUCKET_RATIO: Double = 16
static var SPLIT_RATIO: Int = 24
}
public struct SortedSet<Element: Comparable> {
@usableFromInline
let BUCKET_RATIO: Double = SortedSetCondition.BUCKET_RATIO
@usableFromInline
let SPLIT_RATIO: Int = SortedSetCondition.SPLIT_RATIO
public typealias Index = ArraySlice<Element>.Index
@usableFromInline
typealias BucketIndex = Array<ArraySlice<Element>>.Index
@usableFromInline
var buckets: Array<ArraySlice<Element>>
@usableFromInline
var _count: Int
public var count: Int { _count }
var isEmpty: Bool { _count == 0 }
// def __init__(self, a: Iterable[T] = []) -> None:
// "Make a new SortedSet from iterable. / O(N) if sorted and unique / O(N log N)"
// a = list(a)
// n = len(a)
// if any(a[i] > a[i + 1] for i in range(n - 1)):
// a.sort()
// if any(a[i] >= a[i + 1] for i in range(n - 1)):
// a, b = [], a
// for x in b:
// if not a or a[-1] != x:
// a.append(x)
// n = self.size = len(a)
// num_bucket = int(math.ceil(math.sqrt(n / self.BUCKET_RATIO)))
// self.a = [a[n * i // num_bucket : n * (i + 1) // num_bucket] for i in range(num_bucket)]
@inlinable
init(uniqued a: [Element]) {
let n = a.count
let num_bucket: Int = Int(ceil(sqrt(Double(n) / BUCKET_RATIO)))
buckets = (0..<num_bucket).map{ i in a[n * i / num_bucket ..< n * (i + 1) / num_bucket] }
_count = n
}
public init() {
self.init(uniqued: [])
}
@inlinable
public init(_ range: Range<Element>) where Element: FixedWidthInteger {
self.init(uniqued: range + [])
}
@inlinable
public init<S>(_ _a: S) where S: Collection, S.Element == Element {
var a = _a + []
if (0..<Swift.max(0,a.count - 1)).contains(where: { a[$0] > a[$0 + 1] }) {
a.sort()
}
if (0..<Swift.max(0,a.count - 1)).contains(where: { a[$0] >= a[$0 + 1] }) {
var (c,b): ([Element],[Element]) = ([],a)
for x in b {
if c.isEmpty || c.last != x {
c.append(x)
}
}
a = c
}
self.init(uniqued: a)
}
}
extension SortedSet: Sequence {
// def __iter__(self) -> Iterator[T]:
// for i in self.a:
// for j in i: yield j
public struct Iterator: IteratorProtocol {
public mutating func next() -> Element? {
if b == buckets.endIndex {
return nil
}
defer {
i += 1
if buckets[b].endIndex <= i {
b += 1
if b < buckets.endIndex {
i = buckets[b].startIndex
}
}
}
return buckets[b][i]
}
let buckets: [ArraySlice<Element>]
var i: Index = 0
var b: BucketIndex = 0
}
public func makeIterator() -> Iterator {
Iterator(buckets: buckets)
}
// def __reversed__(self) -> Iterator[T]:
// for i in reversed(self.a):
// for j in reversed(i): yield j
}
extension SortedSet: Equatable {
// def __eq__(self, other) -> bool:
// return list(self) == list(other)
}
extension SortedSet {
// def __len__(self) -> int:
// return self.size
//
// def __repr__(self) -> str:
// return "SortedSet" + str(self.a)
//
// def __str__(self) -> str:
// s = str(list(self))
// return "{" + s[1 : len(s) - 1] + "}"
}
extension SortedSet {
// def _position(self, x: T) -> Tuple[List[T], int, int]:
// "return the bucket, index of the bucket and position in which x should be. self must not be empty."
// for i, a in enumerate(self.a):
// if x <= a[-1]: break
// return (a, i, bisect_left(a, x))
@inlinable
func _position(_ x: Element) -> (ArraySlice<Element>, BucketIndex, Index) {
var (left, right) = (buckets.startIndex, buckets.endIndex)
while left < right {
let mid = (left + right) >> 1
if let l = buckets[mid].last, l < x {
left = mid + 1
} else {
right = mid
}
}
var bucketIndex = left
if bucketIndex == buckets.endIndex {
bucketIndex -= 1
}
return (buckets[bucketIndex], bucketIndex, buckets[bucketIndex].left(x))
}
// def __contains__(self, x: T) -> bool:
// if self.size == 0: return False
// a, _, i = self._position(x)
// return i != len(a) and a[i] == x
@inlinable
public func contains(_ x: Element) -> Bool {
if _count == 0 { return false }
let (bucket,_,i) = _position(x)
return i < bucket.endIndex && bucket[i] == x
}
// def add(self, x: T) -> bool:
// "Add an element and return True if added. / O(√N)"
// if self.size == 0:
// self.a = [[x]]
// self.size = 1
// return True
// a, b, i = self._position(x)
// if i != len(a) and a[i] == x: return False
// a.insert(i, x)
// self.size += 1
// if len(a) > len(self.a) * self.SPLIT_RATIO:
// mid = len(a) >> 1
// self.a[b:b+1] = [a[:mid], a[mid:]]
// return True
@inlinable
public mutating func insert(_ x: Element) -> Bool {
if _count == 0 {
buckets = [[x]]
_count = 1
return true
}
let (b,bi,i) = _position(x)
if i < b.endIndex, b[i] == x { return false }
buckets[bi].insert(x, at: i)
_count += 1
if buckets[bi].count > buckets.count * SPLIT_RATIO {
let mid = buckets[bi].count >> 1
if mid != buckets[bi].startIndex {
buckets[bi ..< bi + 1] = [ buckets[bi][..<mid], buckets[bi][mid...] ]
buckets = buckets.map{ ArraySlice($0) }
}
}
return true
}
// def _pop(self, a: List[T], b: int, i: int) -> T:
// ans = a.pop(i)
// self.size -= 1
// if not a: del self.a[b]
// return ans
@inlinable
mutating func _pop(bucketIndex: BucketIndex, index: Index) -> Element {
let ans = buckets[bucketIndex].remove(at: index)
_count -= 1
if buckets[bucketIndex].isEmpty {
buckets.remove(at: bucketIndex)
}
return ans
}
// def discard(self, x: T) -> bool:
// "Remove an element and return True if removed. / O(√N)"
// if self.size == 0: return False
// a, b, i = self._position(x)
// if i == len(a) or a[i] != x: return False
// self._pop(a, b, i)
// return True
@inlinable
public mutating func remove(_ x: Element) -> Bool {
if _count == 0 { return false }
let (b, bi, i) = _position(x)
if i == b.endIndex || b[i] != x { return false }
_ = _pop(bucketIndex: bi, index: i)
return true
}
// def lt(self, x: T) -> Optional[T]:
// "Find the largest element < x, or None if it doesn't exist."
// for a in reversed(self.a):
// if a[0] < x:
// return a[bisect_left(a, x) - 1]
@inlinable
public func lt(_ x: Element) -> Element? {
for bucket in buckets.reversed() {
if bucket[bucket.startIndex] < x { return bucket[bucket.left(x) - 1] }
}
return nil
}
// def le(self, x: T) -> Optional[T]:
// "Find the largest element <= x, or None if it doesn't exist."
// for a in reversed(self.a):
// if a[0] <= x:
// return a[bisect_right(a, x) - 1]
@inlinable
public func le(_ x: Element) -> Element? {
for bucket in buckets.reversed() {
if bucket[bucket.startIndex] <= x { return bucket[bucket.right(x) - 1] }
}
return nil
}
// def gt(self, x: T) -> Optional[T]:
// "Find the smallest element > x, or None if it doesn't exist."
// for a in self.a:
// if a[-1] > x:
// return a[bisect_right(a, x)]
@inlinable
public func gt(_ x: Element) -> Element? {
for bucket in buckets {
if let l = bucket.last, l > x {
return bucket[bucket.right(x)]
}
}
return nil
}
// def ge(self, x: T) -> Optional[T]:
// "Find the smallest element >= x, or None if it doesn't exist."
// for a in self.a:
// if a[-1] >= x:
// return a[bisect_left(a, x)]
@inlinable
public func ge(_ x: Element) -> Element? {
for bucket in buckets {
if let l = bucket.last, l >= x {
return bucket[bucket.left(x)]
}
}
return nil
}
// def __getitem__(self, i: int) -> T:
// "Return the i-th element."
// if i < 0:
// for a in reversed(self.a):
// i += len(a)
// if i >= 0: return a[i]
// else:
// for a in self.a:
// if i < len(a): return a[i]
// i -= len(a)
// raise IndexError
@inlinable
public subscript(index: Index) -> Element {
var i = index
if i < 0 {
for bucket in buckets.reversed() {
i += bucket.count
if i >= 0 {
return bucket[bucket.startIndex + i]
}
}
}
else {
for bucket in buckets {
if i < bucket.count {
return bucket[bucket.startIndex + i]
}
i -= bucket.count
}
}
fatalError("IndexError")
}
// def pop(self, i: int = -1) -> T:
// "Pop and return the i-th element."
// if i < 0:
// for b, a in enumerate(reversed(self.a)):
// i += len(a)
// if i >= 0: return self._pop(a, ~b, i)
// else:
// for b, a in enumerate(self.a):
// if i < len(a): return self._pop(a, b, i)
// i -= len(a)
// raise IndexError
@inlinable
public mutating func remove(at index: Index) -> Element? {
var i = index
if i < 0 {
for (b,bucket) in buckets.enumerated().reversed() {
i += bucket.count
if i >= 0 {
return _pop(bucketIndex: b, index: bucket.startIndex + i)
}
}
}
else {
for (b,bucket) in buckets.enumerated() {
if i < bucket.count {
return _pop(bucketIndex: b, index: bucket.startIndex + i)
}
i -= bucket.count
}
}
return nil
}
// def index(self, x: T) -> int:
// "Count the number of elements < x."
// ans = 0
// for a in self.a:
// if a[-1] >= x:
// return ans + bisect_left(a, x)
// ans += len(a)
// return ans
@inlinable
public func left(_ x: Element) -> Index {
var ans = 0
for bucket in buckets {
if let l = bucket.last, l >= x {
return ans - bucket.startIndex + bucket.left(x)
}
ans += bucket.count
}
return ans
}
// def index_right(self, x: T) -> int:
// "Count the number of elements <= x."
// ans = 0
// for a in self.a:
// if a[-1] > x:
// return ans + bisect_right(a, x)
// ans += len(a)
// return ans
@inlinable
public func right(_ x: Element) -> Index {
var ans = 0
for bucket in buckets {
if let l = bucket.last, l > x {
return ans - bucket.startIndex + bucket.right(x)
}
ans += bucket.count
}
return ans
}
}
import Foundation
// MARK: - dijkstra
@usableFromInline
enum Dijkstra {
@usableFromInline
enum Error: Swift.Error {
case cycle
}
@inlinable
static func costs<Cost>(
_ g: [[(to: Int, cost: Cost)]],
to: Int,
INF: Cost
) -> [Cost]
where Cost: AdditiveArithmetic & Comparable {
var dist = [Cost](repeating: INF, count: g.count)
dist[to] = .zero
var queue: [(Cost, Int)] = [(.zero, to)]
while let (d, u) = queue.heappop() {
if dist[u] < d { continue }
for (v, c) in g[u] {
if dist[v] > d + c {
dist[v] = d + c
queue.heappush((dist[v], v))
}
}
}
return dist
}
@inlinable
static func route<Cost>(
_ graph: [[(to: Int, cost: Cost)]], from: Int, to: Int, INF: Cost, dist: [Cost]
) throws -> [Int]
where Cost: AdditiveArithmetic & Comparable {
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
}
@inlinable
static func path<Cost>(
_ graph: [[(to: Int, cost: Cost)]], from: Int, to: Int, INF: Cost
) throws -> [Int]
where Cost: AdditiveArithmetic & Comparable {
if graph[from].contains(where: { $0.to == to }) {
return [to]
}
let dist = costs(graph, to: to, INF: INF)
return try route(graph, from: from, to: to, INF: INF, dist: dist)
}
}
//
// File.swift
// AtCoderBeginner
//
// Created by narumij on 2024/08/12.
//
import Foundation
/// 累積和1D
@inlinable
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
@inlinable
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
@inlinable
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 {
@inlinable
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: - 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
@inlinable
init() {
buffer = Storage.bytes
count = 0
}
@inlinable
var inlineCount: Int { MemoryLayout<Buffer>.size }
@inlinable
var capacity: Int { inlineCount / MemoryLayout<Element>.stride }
@inlinable
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
public subscript(index: Int) -> Element {
@inline(__always) get {
_read { buffer in
buffer[index]
}
}
set {
guard index < capacity else { return }
_update{ buffer in
buffer[index] = newValue
}
}
}
@inlinable
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
mutating func append(keyValue: Element) {
self[count] = keyValue
count += 1
}
@inlinable
func prefix(_ upTo: Int) -> Self {
var result = Self()
for i in 0..<min(count, upTo) {
result.append(keyValue: self[i])
}
return result
}
@inlinable
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
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
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
mutating func append(keyValue: Element) {
self[raw: count] = keyValue
count += 1
}
@inlinable
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
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
}
}
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 }
set { self[key] = newValue }
}
@inlinable
func prefix(_ upTo: Int) -> Self {
var result = Self()
for i in 0..<min(count, upTo) {
result.append(keyValue: self[raw: i])
}
return result
}
@inlinable
func prefix(_ upTo: Int, orderBy comparer: (Element,Element) -> Bool) -> Self {
var source = self
source.bubbleSort(by: comparer)
return source.prefix(2)
}
@inlinable
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 {
@inlinable
public init(dictionaryLiteral elements: (Key, Value)...) {
self.init()
elements.forEach {
self[$0.0] = $0.1
}
}
}
import Foundation
// MARK: - zip with
@inlinable
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
}
@inlinable
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
}
@inlinable
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 {
@inlinable
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 {
@inlinable
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 {
@inlinable
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
@inlinable
public func ..<= <Bound: Comparable>(lhs: Bound, rhs: Bound) -> StrideThrough<Bound> {
stride(from: lhs, through: rhs, by: 1)
}
infix operator ..>= : RangeFormationPrecedence
@inlinable
public func ..>= <Bound: Comparable>(lhs: Bound, rhs: Bound) -> StrideThrough<Bound> {
stride(from: lhs, through: rhs, by: -1)
}
infix operator ..> : RangeFormationPrecedence
@inlinable
public func ..> <Bound: Comparable>(lhs: Bound, rhs: Bound) -> StrideTo<Bound> {
stride(from: lhs, to: rhs, by: -1)
}
import Foundation
// MARK: - SIMD8
public struct SIMD8<Scalar: SIMDScalar> {
@inlinable
init(
v0: Scalar, v1: Scalar, v2: Scalar, v3: Scalar,
v4: Scalar, v5: Scalar, v6: Scalar, v7: Scalar
) {
(
self.v0, self.v1, self.v2, self.v3,
self.v4, self.v5, self.v6, self.v7
) = (
v0, v1, v2, v3,
v4, v5, v6, v7
)
}
@usableFromInline
var v0, v1, v2, v3, v4, v5, v6, v7: Scalar
}
extension SIMD8: Codable where Scalar: SIMDScalar {}
extension SIMD8: SIMDStorage where Scalar: SIMDScalar & AdditiveArithmetic {
@inlinable
public init() {
(v0, v1, v2, v3, v4, v5, v6, v7) =
(.zero, .zero, .zero, .zero, .zero, .zero, .zero, .zero)
}
}
extension SIMD8: SIMD where Scalar: SIMDScalar & AdditiveArithmetic {
public typealias MaskStorage = SIMD4<Scalar.SIMDMaskScalar>
@inlinable
public subscript(index: Int) -> Scalar {
@inline(__always) get {
withUnsafePointer(to: self) {
$0.withMemoryRebound(to: Scalar.self, capacity: scalarCount) {
$0[index]
}
}
}
set(newValue) {
let count = scalarCount
withUnsafeMutablePointer(to: &self) {
$0.withMemoryRebound(to: Scalar.self, capacity: count) {
$0[index] = newValue
}
}
}
}
@inlinable
public var scalarCount: Int { 8 }
}
extension SIMD8: Equatable where Scalar: Equatable {}
extension SIMD8: Hashable where Scalar: Hashable {}
extension SIMD8: ExpressibleByArrayLiteral {
@inlinable
public init(arrayLiteral elements: Scalar...) {
(v0, v1, v2, v3, v4, v5, v6, v7) =
(
elements[0], elements[1], elements[2], elements[3],
elements[4], elements[5], elements[6], elements[7]
)
}
}
extension SIMD8: CustomStringConvertible {
@inlinable
public var description: String {
[v0, v1, v2, v3, v4, v5, v6, v7].description
}
}
import Foundation
extension Array {
@inlinable
public mutating func heappush(_ element:Element)
where Element: Comparable
{
heappush(Comparer_A.self, element)
}
@inlinable
public mutating func heappop() -> Element?
where Element: Comparable
{
heappop(Comparer_A.self)
}
@inlinable
public mutating func heapify()
where Element: Comparable
{
heapify(Comparer_A.self)
}
@inlinable
public mutating func isHeap() -> Bool
where Element: Comparable
{
isHeap(Comparer_A.self)
}
@inlinable
public mutating func heappush<A,B>(_ element:Element)
where Element == (A,B),
A: Comparable,
B: Comparable
{
heappush(Comparer_A_B<A,B>.self, element)
}
@inlinable
public mutating func heappop<A,B>() -> Element?
where Element == (A,B),
A: Comparable,
B: Comparable
{
heappop(Comparer_A_B<A,B>.self)
}
@inlinable
public mutating func heappush<A,B,C>(_ element:Element)
where Element == (A,B,C),
A: Comparable,
B: Comparable,
C: Comparable
{
heappush(Comparer_A_B_C<A,B,C>.self, element)
}
@inlinable
public mutating func heappop<A,B,C>() -> Element?
where Element == (A,B,C),
A: Comparable,
B: Comparable,
C: Comparable
{
heappop(Comparer_A_B_C<A,B,C>.self)
}
@usableFromInline
enum Comparer_A: BinaryHeapComparer
where Element: Comparable
{
@inlinable
public static var __heap_value_compare: (Element, Element) -> Bool { (<) }
}
@usableFromInline
enum Comparer_A_B<A,B>: BinaryHeapComparer where A: Comparable, B: Comparable {
@inlinable
static var __heap_value_compare: (Element, Element) -> Bool { (<) }
@usableFromInline
typealias Element = (A,B)
}
@usableFromInline
enum Comparer_A_B_C<A,B,C>: BinaryHeapComparer where A: Comparable, B: Comparable, C: Comparable {
@inlinable
static var __heap_value_compare: (Element, Element) -> Bool { (<) }
@usableFromInline
typealias Element = (A,B,C)
}
}
public protocol BinaryHeapComparer {
associatedtype Element
static var __heap_value_compare: (Element, Element) -> Bool { get }
}
extension Array {
@inlinable
public mutating func heappush<Comp>(_ type: Comp.Type, _ element:Element)
where Comp: BinaryHeapComparer, Self.Element == Comp.Element
{
append(element)
__update_binary_heap(Comp.self) { $0.push_heap($0.endIndex) }
}
@inlinable
public mutating func heappop<Comp>(_ type: Comp.Type) -> Element?
where Comp: BinaryHeapComparer, Self.Element == Comp.Element
{
guard !isEmpty else { return nil }
__update_binary_heap(Comp.self) { $0.pop_heap($0.endIndex) }
return removeLast()
}
@inlinable
public mutating func heapify<Comp>(_ type: Comp.Type)
where Comp: BinaryHeapComparer, Self.Element == Comp.Element
{
__update_binary_heap(Comp.self) { $0.heapify($0.endIndex) }
}
@inlinable
public mutating func isHeap<Comp>(_ type: Comp.Type) -> Bool
where Comp: BinaryHeapComparer, Self.Element == Comp.Element
{
__update_binary_heap(Comp.self) { $0.isHeap($0.endIndex) }
}
}
extension Array {
@inlinable @inline(__always)
mutating func __update_binary_heap<Comp, R>(
_ type: Comp.Type,
_ body: (UnsafeHeapHandle<Comp>) -> R
) -> R
where Comp: BinaryHeapComparer, Self.Element == Comp.Element
{
let (startIndex, endIndex) = (startIndex, endIndex)
return withUnsafeMutableBufferPointer {
body(
UnsafeHeapHandle<Comp>(
$0.baseAddress!,
startIndex: startIndex,
endIndex: endIndex))
}
}
}
@usableFromInline
struct UnsafeHeapHandle<Comparer: BinaryHeapComparer> {
@usableFromInline
typealias Element = Comparer.Element
@usableFromInline
typealias Index = Int
@inlinable @inline(__always)
internal init(_ buffer: UnsafeMutablePointer<Element>,
startIndex: Index, endIndex: Index)
{
self.buffer = buffer
self.startIndex = startIndex
self.endIndex = endIndex
}
@usableFromInline
let buffer: UnsafeMutablePointer<Element>
@usableFromInline
let startIndex: Index
@usableFromInline
let endIndex: Index
}
extension UnsafeHeapHandle {
@inlinable @inline(__always)
var __heap_value_compare: (Element, Element) -> Bool {
Comparer.__heap_value_compare
}
@inlinable @inline(__always)
func __parent(_ p: Int) -> Int { (p - 1) >> 1 }
@inlinable @inline(__always)
func __leftChild(_ p: Int) -> Int { (p << 1) + 1 }
@inlinable @inline(__always)
func __rightChild(_ p: Int) -> Int { (p << 1) + 2 }
@inlinable
func push_heap(_ limit: Index) {
heapifyUp(limit, limit - 1, __heap_value_compare)
}
@inlinable
func pop_heap(_ limit: Index) {
guard limit > 0, startIndex != limit - 1 else { return }
swap(&buffer[startIndex], &buffer[limit - 1])
heapifyDown(limit - 1, startIndex, __heap_value_compare)
}
@inlinable
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 = __parent(current)
guard !comp(buffer[parent], element) else { break }
(buffer[current], current) = (buffer[parent], parent)
}
buffer[current] = element
}
@inlinable
func heapifyDown(_ limit: Index,_ i: Index,_ comp: (Element, Element) -> Bool) {
let element = buffer[i]
var (current, selected) = (i,i)
while current < limit {
let leftChild = __leftChild(current)
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
}
@inlinable
func heapify(_ limit: Index) {
for i in stride(from: limit / 2, through: startIndex, by: -1) {
heapify(limit, i)
}
assert(isHeap(limit))
}
@inlinable
func heapify(_ limit: Index, _ i: Index) {
guard let index = heapifyIndex(limit, i) else { return }
swap(&buffer[i], &buffer[index])
heapify(limit, index)
}
@inlinable
func heapifyIndex(_ limit: Index, _ current: Index) -> Index?
{
var next = current
if __leftChild(current) < limit,
__heap_value_compare(buffer[__leftChild(current)], buffer[next])
{
next = __leftChild(current)
}
if __rightChild(current) < limit,
__heap_value_compare(buffer[__rightChild(current)], buffer[next])
{
next = __rightChild(current)
}
return next == current ? nil : next
}
@inlinable
func isHeap(_ limit: Index) -> Bool {
(startIndex..<limit).allSatisfy { heapifyIndex(limit, $0) == nil }
}
}
import Foundation
// MARK: - SIMD4
#if true
public struct SIMD4<Scalar: SIMDScalar> {
@inlinable
init(x: Scalar, y: Scalar, z: Scalar, w: Scalar) {
(self.x, self.y, self.z, self.w) = (x, y, z, w)
}
@inlinable
init(_ x: Scalar, _ y: Scalar, _ z: Scalar, _ w: Scalar) {
(self.x, self.y, self.z, self.w) = (x, y, z, w)
}
@usableFromInline
var x, y, z, w: Scalar
}
extension SIMD4: Codable where Scalar: SIMDScalar {}
extension SIMD4: SIMDStorage where Scalar: SIMDScalar & AdditiveArithmetic {
@inlinable
public init() {
(x, y, z, w) = (.zero, .zero, .zero, .zero)
}
}
extension SIMD4: SIMD where Scalar: SIMDScalar & AdditiveArithmetic {
public typealias MaskStorage = SIMD4<Scalar.SIMDMaskScalar>
@inlinable
public subscript(index: Int) -> Scalar {
@inline(__always) get {
withUnsafePointer(to: self) {
$0.withMemoryRebound(to: Scalar.self, capacity: scalarCount) {
$0[index]
}
}
}
set(newValue) {
let count = scalarCount
withUnsafeMutablePointer(to: &self) {
$0.withMemoryRebound(to: Scalar.self, capacity: count) {
$0[index] = newValue
}
}
}
}
@inlinable
public var scalarCount: Int { 4 }
}
extension SIMD4: Equatable where Scalar: Equatable {}
extension SIMD4: Hashable where Scalar: Hashable {}
extension SIMD4: ExpressibleByArrayLiteral {
@inlinable
public init(arrayLiteral elements: Scalar...) {
(x, y, z, w) = (elements[0], elements[1], elements[2], elements[3])
}
}
extension SIMD4: CustomStringConvertible {
@inlinable
public var description: String { [x, y, z, w].description }
}
#endif
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 }
infix operator .%: MultiplicationPrecedence
func .% (_ n: Int, _ d: Int) -> Int { mod(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 Algorithms
import Foundation
// MARK: - SIMD2
public
struct SIMD2<Scalar: SIMDScalar>
{
@inlinable
init(x: Scalar, y: Scalar) {
(self.x, self.y) = (x, y)
}
@inlinable
init(_ x: Scalar, _ y: Scalar) {
(self.x, self.y) = (x, y)
}
@inlinable
init(_ v: [Scalar]) {
(x, y) = (v[0], v[1])
}
@usableFromInline
var x, y: Scalar
}
extension SIMD2: ExpressibleByArrayLiteral {
@inlinable
public init(arrayLiteral elements: Scalar...) {
(x, y) = (elements[0], elements[1])
}
}
extension SIMD2: Codable where Scalar: SIMDScalar {}
extension SIMD2: SIMDStorage where Scalar: SIMDScalar & AdditiveArithmetic {
public init() {
(x, y) = (.zero, .zero)
}
}
extension SIMD2: SIMD where Scalar: SIMDScalar & AdditiveArithmetic {
public typealias MaskStorage = SIMD2<Scalar.SIMDMaskScalar>
@inlinable
public subscript(index: Int) -> Scalar {
@inline(__always) get {
withUnsafePointer(to: self) {
$0.withMemoryRebound(to: Scalar.self, capacity: scalarCount) {
$0[index]
}
}
}
set(newValue) {
let count = scalarCount
withUnsafeMutablePointer(to: &self) {
$0.withMemoryRebound(to: Scalar.self, capacity: count) {
$0[index] = newValue
}
}
}
}
@inlinable
public var scalarCount: Int { 2 }
}
extension SIMD2: Equatable where Scalar: Equatable {}
extension SIMD2: Hashable where Scalar: Hashable {}
extension SIMD2: CustomStringConvertible {
@inlinable
public var description: String { [x, y].description }
}
extension SIMD2 where Scalar: FixedWidthInteger {
@inlinable
func sum() -> Scalar { x + y }
}
@inlinable
func dot<Scalar>(_ lhs: SIMD2<Scalar>, _ rhs: SIMD2<Scalar>) -> Scalar
where Scalar: FixedWidthInteger {
(lhs &* rhs).sum()
}
@inlinable
func dot<Scalar>(_ lhs: SIMD2<Scalar>, _ rhs: SIMD2<Scalar>) -> Scalar where Scalar: FloatingPoint {
(lhs * rhs).sum()
}
@inlinable
func length_squared<Scalar>(_ rhs: SIMD2<Scalar>) -> Scalar where Scalar: FixedWidthInteger {
dot(rhs, rhs)
}
@inlinable
func length_squared<Scalar>(_ rhs: SIMD2<Scalar>) -> Scalar where Scalar: FloatingPoint {
dot(rhs, rhs)
}
@inlinable
func distance_squared<Scalar>(_ lhs: SIMD2<Scalar>, _ rhs: SIMD2<Scalar>) -> Scalar
where Scalar: FixedWidthInteger {
length_squared(lhs &- rhs)
}
@inlinable
func distance_squared<Scalar>(_ lhs: SIMD2<Scalar>, _ rhs: SIMD2<Scalar>) -> Scalar
where Scalar: FloatingPoint {
length_squared(lhs - rhs)
}
@inlinable
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)
}
@inlinable
func min<T: Comparable>(_ a: SIMD2<T>, _ b: SIMD2<T>) -> SIMD2<T> {
.init(min(a.x, b.x), min(a.y, b.y))
}
@inlinable
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 右ネジ
@inlinable
static var rotate90: [Self] { [[0, -1], [1, 0]] }
@inlinable
static var rotate180: [Self] { [[-1, 0], [0, -1]] }
@inlinable
static var rotate270: [Self] { [[0, 1], [-1, 0]] }
}
extension SIMD2 where Scalar == Int {
public enum MoveDirection: String {
case D
case U
case L
case R
}
@inlinable
static func move(_ d: MoveDirection) -> Self {
switch d {
case .D:
return [1, 0]
case .U:
return [-1, 0]
case .L:
return [0, -1]
case .R:
return [0, 1]
}
}
@inlinable
static func move(_ d: UInt8) -> Self {
move(.init(rawValue: String(bytes: [d], encoding: .ascii)!)!)
}
}
@inlinable
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()]
}
@inlinable
func &* <Component>(lhs: [[Component]], rhs: SIMD2<Component>) -> SIMD2<Component>
where Component: FixedWidthInteger {
mul(lhs, rhs)
}
@inlinable
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) }
}
extension SIMD2 {
@inlinable
func reversed() -> Self { .init(y, x) }
}
@inlinable
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: - Char Convinience
@usableFromInline
typealias Char = UInt8
extension UInt8: ExpressibleByStringLiteral {
@inlinable
public init(stringLiteral value: String) {
self = value.utf8.first!
}
}
extension UInt8 {
@inlinable
var character: Character { Character(UnicodeScalar(self)) }
@inlinable
var char: Character { character }
@inlinable
func lowercased() -> Self {
guard
self >= 65,
self <= 90
else {
return self
}
return self + 32
}
@inlinable
func uppercased() -> Self {
guard
self >= 97,
self <= 122
else {
return self
}
return self - 32
}
}
extension Sequence where Element == UInt8 {
@inlinable
func joined() -> String { String(bytes: self, encoding: .ascii)! }
var characters: [Character] { map(\.character) }
}
extension String {
@inlinable
init<S>(ascii: S) where S: Sequence, S.Element == UInt8 {
self = ascii.joined()
}
@inlinable
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 {
@inlinable
var integerValue: Int { Character("0").distance(to: self) }
}
extension Sequence where Element == Character {
@inlinable
func joined() -> String { String(self) }
@inlinable
var asciiValues: [UInt8] { compactMap(\.asciiValue) }
}
extension String {
@inlinable
var characters: [Character] { map { $0 } }
}
@inlinable
func < (lhs: [Char], rhs: ArraySlice<Char>) -> Bool {
return lhs.lexicographicallyPrecedes(rhs)
}
@inlinable
func < (lhs: ArraySlice<Char>, rhs: [Char]) -> Bool {
return lhs.lexicographicallyPrecedes(rhs)
}
@inlinable
func == (lhs: [Char], rhs: ArraySlice<Char>) -> Bool {
guard lhs.count == rhs.count else { return false }
return lhs.withUnsafeBufferPointer { lhs in
rhs.withUnsafeBufferPointer { rhs in
for i in 0 ..< lhs.count {
guard lhs[i] == rhs[i] else { return false }
}
return true
}
}
}
@inlinable
func == (lhs: ArraySlice<Char>, rhs: [Char]) -> Bool {
guard lhs.count == rhs.count else { return false }
return lhs.withUnsafeBufferPointer { lhs in
rhs.withUnsafeBufferPointer { rhs in
for i in 0 ..< lhs.count {
guard lhs[i] == rhs[i] else { return false }
}
return true
}
}
}
@inlinable
func <= (lhs: [Char], rhs: ArraySlice<Char>) -> Bool {
return lhs.lexicographicallyPrecedes(rhs) || lhs == rhs
}
@inlinable
func <= (lhs: ArraySlice<Char>, rhs: [Char]) -> Bool {
return lhs.lexicographicallyPrecedes(rhs) || lhs == rhs
}
extension ContiguousArray where Element == CChar {
@inlinable
func putchars_unlocked() {
for c in self {
putchar_unlocked(Int32(c == 0 ? 0x0A : c))
}
}
}
extension Array where Element == Char {
@inlinable
func putchars_unlocked() {
for c in self {
putchar_unlocked(Int32(c))
}
putchar_unlocked(0x0A)
}
}
import Foundation
// MARK: - Binary Search
extension Collection where Index == Int, Element: Comparable {
@inlinable
func left(_ x: Element) -> Index {
var (left, right) = (startIndex, endIndex)
while left < right {
let mid = (left + right) >> 1
if self[mid] < x {
left = mid + 1
} else {
right = mid
}
}
return left
}
@inlinable
func right(_ x: Element) -> Index {
var (left, right) = (startIndex, endIndex)
while left < right {
let mid = (left + right) >> 1
if x < self[mid] {
right = mid
} else {
left = mid + 1
}
}
return left
}
}
extension Collection where Index == Int {
@inlinable
func left<T,U>(_ x: T,_ comparer: (U, T) -> Bool,_ key: (Element) -> U) -> Index {
var (left, right) = (startIndex, endIndex)
while left < right {
let mid = (left + right) >> 1
if comparer(key(self[mid]), x) {
left = mid + 1
} else {
right = mid
}
}
return left
}
@inlinable
func right<T,U>(_ x: T,_ comparer: (T, U) -> Bool,_ key: (Element) -> U) -> Index {
var (left, right) = (startIndex, endIndex)
while left < right {
let mid = (left + right) >> 1
if comparer(x, key(self[mid])) {
right = mid
} else {
left = mid + 1
}
}
return right
}
}
import Algorithms
import Foundation
// MARK: - convinience
@usableFromInline let INF: Int = 1 << 60
@usableFromInline let MOD_998_244_353 = 998_244_353
@usableFromInline let MOD_1_000_000_007 = 1_000_000_007
@usableFromInline
func Yes(_ b: Bool = true) -> String { b ? "Yes" : "No" }
@usableFromInline
func No(_ b: Bool = true) -> String { Yes(!b) }
@usableFromInline
func YES(_ b: Bool = true) -> String { b ? "YES" : "NO" }
@usableFromInline
func NO(_ b: Bool = true) -> String { YES(!b) }
@usableFromInline
func Takahashi(_ b: Bool = true) -> String { b ? "Takahashi" : "Aoki" }
@usableFromInline
func Aoki(_ b: Bool = true) -> String { Takahashi(!b) }
@usableFromInline
let snuke = "snuke"
// MARK: - Integer Convinience
precedencegroup PowerPrecedence {
lowerThan: BitwiseShiftPrecedence
higherThan: MultiplicationPrecedence
associativity: right
assignment: true
}
infix operator ** : PowerPrecedence
@inlinable
func ** <INT>(lhs: INT, rhs: Int) -> INT where INT: FixedWidthInteger {
repeatElement(lhs, count: rhs).product()
}
@inlinable
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
}
@inlinable
func ** (lhs: Double, rhs: Double) -> Double { pow(lhs, rhs) }
extension FixedWidthInteger {
@inlinable
var last: Self { self - 1 }
@inlinable
var range: Range<Self> { 0..<self }
@inlinable
var closedRange: ClosedRange<Self> { 0...self }
@inlinable
@discardableResult
func rep<T>(_ f: () throws -> T) rethrows -> [T] { try (0..<self).map { _ in try f() } }
@inlinable
@discardableResult
func rep<T>(_ f: (Self) throws -> T) rethrows -> [T] { try (0..<self).map { i in try f(i) } }
@inlinable
@discardableResult
func rep<T>(_ f: (Self) throws -> [T]) rethrows -> [T] {
try (0..<self).flatMap { i in try f(i) }
}
}
// MARK: - Bit Convinience
extension FixedWidthInteger {
@inlinable
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 {
@inlinable
func output() {
print(map(\.description).joined(separator: " "))
}
}
extension Collection where Element == [CChar] {
@inlinable
func print() { forEach { Swift.print(String(cString: $0 + [0])) } }
}
// MARK: - Array Init
extension Array {
@inlinable
static func * (lhs: Self, rhs: Int) -> Self {
repeatElement(lhs, count: rhs).flatMap { $0 }
}
@inlinable
static func * (lhs: Self, rhs: (A: Int, B: Int)) -> [Self] {
[lhs * rhs.B] * rhs.A
}
@inlinable
static func * (lhs: Self, rhs: (A: Int, B: Int, C: Int)) -> [[Self]] {
[[lhs * rhs.C] * rhs.B] * rhs.A
}
@inlinable
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 {
@inlinable
static func * (lhs: Self, rhs: Int) -> Self {
repeatElement(lhs, count: rhs).joined()
}
@inlinable
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 {
@inlinable
var all: Bool { reduce(true) { $0 && $1 } }
@inlinable
var any: Bool { contains(true) }
}
extension Sequence {
@inlinable
func count(where f: (Element) -> Bool) -> Int {
reduce(0) { $0 + (f($1) ? 1 : 0) }
}
@inlinable
func count(_ element: Element) -> Int where Element: Equatable {
reduce(0) { $0 + ($1 == element ? 1 : 0) }
}
}
extension Sequence where Element: AdditiveArithmetic {
@inlinable
func sum() -> Element { reduce(.zero, +) }
@inlinable
func acc() -> [Element] { reduce(into: [.zero]) { $0.append(($0.last ?? .zero) + $1) } }
}
extension Sequence where Element: BinaryInteger {
@inlinable
func product() -> Element { reduce(1, *) }
@inlinable
func or() -> Element { reduce(0, |) }
@inlinable
func xor() -> Element { reduce(0, ^) }
}
extension Sequence where Element: BinaryFloatingPoint {
@inlinable
func product() -> Element { reduce(1, *) }
}
extension Sequence
where Element: Sequence, Element.Element: AdditiveArithmetic {
@inlinable
public 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 {
@inlinable
func intervals() -> [Element] {
(0..<(distance(from: startIndex, to: endIndex) - 1)).map {
self[index(startIndex, offsetBy: $0 + 1)] - self[index(startIndex, offsetBy: $0)]
}
}
}
@inlinable
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))
}
@inlinable
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
@inlinable
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 {
@inlinable
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
}
}
// MARK: - Range Convinience
@inlinable
func ..< <Bound>(lhs: Bound, rhs: Bound) -> (lhs: Bound, rhs: Bound)
where Bound: Comparable {
(lhs, rhs)
}
@inlinable
func safe<B>(_ range: (lhs: B, rhs: B)) -> Range<B> {
range.lhs ..< min(range.lhs, range.rhs)
}
extension Array {
@inlinable
subscript(safe range: Range<Index>) -> SubSequence {
var (l,r) = (
Swift.max(startIndex, range.lowerBound),
Swift.min(endIndex, range.upperBound)
)
r = Swift.max(l,r)
return self[l..<r]
}
}
import Foundation
// MARK: - SIMD32
public struct SIMD32<Scalar: SIMDScalar> {
@inlinable
init(
v0: Scalar, v1: Scalar, v2: Scalar, v3: Scalar,
v4: Scalar, v5: Scalar, v6: Scalar, v7: Scalar,
v8: Scalar, v9: Scalar, v10: Scalar, v11: Scalar,
v12: Scalar, v13: Scalar, v14: Scalar, v15: Scalar,
v16: Scalar, v17: Scalar, v18: Scalar, v19: Scalar,
v20: Scalar, v21: Scalar, v22: Scalar, v23: Scalar,
v24: Scalar, v25: Scalar, v26: Scalar, v27: Scalar,
v28: Scalar, v29: Scalar, v30: Scalar, v31: Scalar
) {
(
self.v0, self.v1, self.v2, self.v3,
self.v4, self.v5, self.v6, self.v7,
self.v8, self.v9, self.v10, self.v11,
self.v12, self.v13, self.v14, self.v15,
self.v16, self.v17, self.v18, self.v19,
self.v20, self.v21, self.v22, self.v23,
self.v24, self.v25, self.v26, self.v27,
self.v28, self.v29, self.v30, self.v31
) = (
v0, v1, v2, v3,
v4, v5, v6, v7,
v8, v9, v10, v11,
v12, v13, v14, v15,
v16, v17, v18, v19,
v20, v21, v22, v23,
v24, v25, v26, v27,
v28, v29, v30, v31
)
}
@usableFromInline
var v0, v1, v2, v3, v4, v5, v6, v7,
v8, v9, v10, v11, v12, v13, v14, v15,
v16, v17, v18, v19, v20, v21, v22, v23,
v24, v25, v26, v27, v28, v29, v30, v31: Scalar
}
extension SIMD32: Codable where Scalar: SIMDScalar {}
extension SIMD32: SIMDStorage where Scalar: SIMDScalar & AdditiveArithmetic {
@inlinable
public init() {
(
v0, v1, v2, v3, v4, v5, v6, v7,
v8, v9, v10, v11, v12, v13, v14, v15,
v16, v17, v18, v19, v20, v21, v22, v23,
v24, v25, v26, v27, v28, v29, v30, v31
) =
(
.zero, .zero, .zero, .zero, .zero, .zero, .zero, .zero,
.zero, .zero, .zero, .zero, .zero, .zero, .zero, .zero,
.zero, .zero, .zero, .zero, .zero, .zero, .zero, .zero,
.zero, .zero, .zero, .zero, .zero, .zero, .zero, .zero
)
}
}
extension SIMD32: SIMD where Scalar: SIMDScalar & AdditiveArithmetic {
public typealias MaskStorage = SIMD4<Scalar.SIMDMaskScalar>
@inlinable
public subscript(index: Int) -> Scalar {
@inline(__always) get {
withUnsafePointer(to: self) {
$0.withMemoryRebound(to: Scalar.self, capacity: scalarCount) {
$0[index]
}
}
}
set(newValue) {
let count = scalarCount
withUnsafeMutablePointer(to: &self) {
$0.withMemoryRebound(to: Scalar.self, capacity: count) {
$0[index] = newValue
}
}
}
}
@inlinable
public var scalarCount: Int { 32 }
}
extension SIMD32: Equatable where Scalar: Equatable {}
extension SIMD32: Hashable where Scalar: Hashable {}
extension SIMD32: ExpressibleByArrayLiteral {
@inlinable
public init(arrayLiteral elements: Scalar...) {
(
v0, v1, v2, v3, v4, v5, v6, v7,
v8, v9, v10, v11, v12, v13, v14, v15,
v16, v17, v18, v19, v20, v21, v22, v23,
v24, v25, v26, v27, v28, v29, v30, v31
) =
(
elements[0], elements[1], elements[2], elements[3],
elements[4], elements[5], elements[6], elements[7],
elements[8], elements[9], elements[10], elements[11],
elements[12], elements[13], elements[14], elements[15],
elements[16], elements[17], elements[18], elements[19],
elements[20], elements[21], elements[22], elements[23],
elements[24], elements[25], elements[26], elements[27],
elements[28], elements[29], elements[30], elements[31]
)
}
}
extension SIMD32: CustomStringConvertible {
@inlinable
public var description: String {
[
v0, v1, v2, v3, v4, v5, v6, v7,
v8, v9, v10, v11, v12, v13, v14, v15,
v16, v17, v18, v19, v20, v21, v22, v23,
v24, v25, v26, v27, v28, v29, v30, v31,
].description
}
}
import Foundation
// MARK: - compare
@inlinable
func less<C: Comparable>(lhs: C, rhs: C) -> Bool? {
guard lhs != rhs else { return nil }
return lhs < rhs
}
@inlinable
func < <A,B>(lhs: (A,B), rhs: (A,B)) -> Bool
where A: Comparable,
B: Comparable
{
func _less(_ key: Int) -> Bool? {
switch key {
case 0: return less(lhs: lhs.0, rhs: rhs.0)
case 1: return less(lhs: lhs.1, rhs: rhs.1)
default: fatalError()
}
}
return _less(0) ?? _less(1) ?? false
}
@inlinable
func < <A,B,C>(lhs: (A,B,C), rhs: (A,B,C)) -> Bool
where A: Comparable,
B: Comparable,
C: Comparable
{
func _less(_ key: Int) -> Bool? {
switch key {
case 0: return less(lhs: lhs.0, rhs: rhs.0)
case 1: return less(lhs: lhs.1, rhs: rhs.1)
case 2: return less(lhs: lhs.2, rhs: rhs.2)
default: fatalError()
}
}
return _less(0) ?? _less(1) ?? _less(2) ?? false
}
@inlinable
func < <A,B,C,D>(lhs: (A,B,C,D), rhs: (A,B,C,D)) -> Bool
where A: Comparable,
B: Comparable,
C: Comparable,
D: Comparable
{
func _less(_ key: Int) -> Bool? {
switch key {
case 0: return less(lhs: lhs.0, rhs: rhs.0)
case 1: return less(lhs: lhs.1, rhs: rhs.1)
case 2: return less(lhs: lhs.2, rhs: rhs.2)
case 3: return less(lhs: lhs.3, rhs: rhs.3)
default: fatalError()
}
}
return _less(0) ?? _less(1) ?? _less(2) ?? _less(3) ?? false
}
@inlinable
func greater<C: Comparable>(lhs: C, rhs: C) -> Bool? {
guard lhs != rhs else { return nil }
return lhs > rhs
}
@inlinable
func > <A,B>(lhs: (A,B), rhs: (A,B)) -> Bool
where A: Comparable,
B: Comparable
{
func _greater(_ key: Int) -> Bool? {
switch key {
case 0: return greater(lhs: lhs.0, rhs: rhs.0)
case 1: return greater(lhs: lhs.1, rhs: rhs.1)
default: fatalError()
}
}
return _greater(0) ?? _greater(1) ?? false
}
@inlinable
func > <A,B,C>(lhs: (A,B,C), rhs: (A,B,C)) -> Bool
where A: Comparable,
B: Comparable,
C: Comparable
{
func _greater(_ key: Int) -> Bool? {
switch key {
case 0: return greater(lhs: lhs.0, rhs: rhs.0)
case 1: return greater(lhs: lhs.1, rhs: rhs.1)
case 2: return greater(lhs: lhs.2, rhs: rhs.2)
default: fatalError()
}
}
return _greater(0) ?? _greater(1) ?? _greater(2) ?? false
}
@inlinable
func > <A,B,C,D>(lhs: (A,B,C,D), rhs: (A,B,C,D)) -> Bool
where A: Comparable,
B: Comparable,
C: Comparable,
D: Comparable
{
func _greater(_ key: Int) -> Bool? {
switch key {
case 0: return greater(lhs: lhs.0, rhs: rhs.0)
case 1: return greater(lhs: lhs.1, rhs: rhs.1)
case 2: return greater(lhs: lhs.2, rhs: rhs.2)
case 3: return greater(lhs: lhs.3, rhs: rhs.3)
default: fatalError()
}
}
return _greater(0) ?? _greater(1) ?? _greater(2) ?? _greater(3) ?? false
}
import Foundation
// MARK: - SIMD16
public struct SIMD16<Scalar: SIMDScalar> {
@inlinable
init(
v0: Scalar, v1: Scalar, v2: Scalar, v3: Scalar,
v4: Scalar, v5: Scalar, v6: Scalar, v7: Scalar,
v8: Scalar, v9: Scalar, v10: Scalar, v11: Scalar,
v12: Scalar, v13: Scalar, v14: Scalar, v15: Scalar
) {
(
self.v0, self.v1, self.v2, self.v3,
self.v4, self.v5, self.v6, self.v7,
self.v8, self.v9, self.v10, self.v11,
self.v12, self.v13, self.v14, self.v15
) = (
v0, v1, v2, v3,
v4, v5, v6, v7,
v8, v9, v10, v11,
v12, v13, v14, v15
)
}
@usableFromInline
var v0, v1, v2, v3, v4, v5, v6, v7, v8, v9, v10, v11, v12, v13, v14, v15: Scalar
}
extension SIMD16: Codable where Scalar: SIMDScalar {}
extension SIMD16: SIMDStorage where Scalar: SIMDScalar & AdditiveArithmetic {
@inlinable
public init() {
(v0, v1, v2, v3, v4, v5, v6, v7, v8, v9, v10, v11, v12, v13, v14, v15) =
(
.zero, .zero, .zero, .zero, .zero, .zero, .zero, .zero,
.zero, .zero, .zero, .zero, .zero, .zero, .zero, .zero
)
}
}
extension SIMD16: SIMD where Scalar: SIMDScalar & AdditiveArithmetic {
public typealias MaskStorage = SIMD4<Scalar.SIMDMaskScalar>
@inlinable
public subscript(index: Int) -> Scalar {
@inline(__always) get {
withUnsafePointer(to: self) {
$0.withMemoryRebound(to: Scalar.self, capacity: scalarCount) {
$0[index]
}
}
}
set(newValue) {
let count = scalarCount
withUnsafeMutablePointer(to: &self) {
$0.withMemoryRebound(to: Scalar.self, capacity: count) {
$0[index] = newValue
}
}
}
}
@inlinable
public var scalarCount: Int { 16 }
}
extension SIMD16: Equatable where Scalar: Equatable {}
extension SIMD16: Hashable where Scalar: Hashable {}
extension SIMD16: ExpressibleByArrayLiteral {
@inlinable
public init(arrayLiteral elements: Scalar...) {
(v0, v1, v2, v3, v4, v5, v6, v7, v8, v9, v10, v11, v12, v13, v14, v15) =
(
elements[0], elements[1], elements[2], elements[3],
elements[4], elements[5], elements[6], elements[7],
elements[8], elements[9], elements[10], elements[11],
elements[12], elements[13], elements[14], elements[15]
)
}
}
extension SIMD16: CustomStringConvertible {
@inlinable
public var description: String {
[
v0, v1, v2, v3, v4, v5, v6, v7,
v8, v9, v10, v11, v12, v13, v14, v15,
].description
}
}
import Foundation
// MARK: - SIMDMask
extension SIMDMask {
@inlinable
var all: Bool {
for i in 0..<scalarCount {
if !self[i] {
return false
}
}
return true
}
@inlinable
var any: Bool {
for i in 0..<scalarCount {
if self[i] {
return true
}
}
return false
}
}
import Foundation
extension SIMD2 where Scalar: ScalarIn {
@inlinable
static var stdin: Self {
[Scalar.stdin, Scalar.stdin]
}
}
import Foundation
// MARK: - SIMD3
public struct SIMD3<Scalar: SIMDScalar> {
@inlinable
public init(x: Scalar, y: Scalar, z: Scalar) {
(self.x, self.y, self.z) = (x, y, z)
}
@inlinable
public init(_ x: Scalar, _ y: Scalar, _ z: Scalar) {
(self.x, self.y, self.z) = (x, y, z)
}
@usableFromInline
var x, y, z: Scalar
}
extension SIMD3: Codable where Scalar: SIMDScalar {}
extension SIMD3: SIMDStorage where Scalar: SIMDScalar & AdditiveArithmetic {
@inlinable
public init() {
(x, y, z) = (.zero, .zero, .zero)
}
}
extension SIMD3: SIMD where Scalar: SIMDScalar & AdditiveArithmetic {
public typealias MaskStorage = SIMD3<Scalar.SIMDMaskScalar>
@inlinable
public subscript(index: Int) -> Scalar {
@inline(__always) get {
withUnsafePointer(to: self) {
$0.withMemoryRebound(to: Scalar.self, capacity: scalarCount) {
$0[index]
}
}
}
set(newValue) {
let count = scalarCount
withUnsafeMutablePointer(to: &self) {
$0.withMemoryRebound(to: Scalar.self, capacity: count) {
$0[index] = newValue
}
}
}
}
@inlinable
public var scalarCount: Int { 3 }
}
extension SIMD3: Equatable where Scalar: Equatable {}
extension SIMD3: Hashable where Scalar: Hashable {}
extension SIMD3: ExpressibleByArrayLiteral {
@inlinable
public init(arrayLiteral elements: Scalar...) {
(x, y, z) = (elements[0], elements[1], elements[2])
}
}
extension SIMD3: CustomStringConvertible {
@inlinable
public var description: String { [x, y, z].description }
}
extension SIMD3 where Scalar: FixedWidthInteger {
@inlinable
func sum() -> Scalar { x + y + z }
}
@inlinable
func dot<Scalar>(_ lhs: SIMD3<Scalar>, _ rhs: SIMD3<Scalar>) -> Scalar
where Scalar: FixedWidthInteger {
(lhs &* rhs).sum()
}
@inlinable
func dot<Scalar>(_ lhs: SIMD3<Scalar>, _ rhs: SIMD3<Scalar>) -> Scalar where Scalar: FloatingPoint {
(lhs * rhs).sum()
}
@inlinable
func length_squared<Scalar>(_ rhs: SIMD3<Scalar>) -> Scalar where Scalar: FixedWidthInteger {
dot(rhs, rhs)
}
@inlinable
func length_squared<Scalar>(_ rhs: SIMD3<Scalar>) -> Scalar where Scalar: FloatingPoint {
dot(rhs, rhs)
}
@inlinable
func distance_squared<Scalar>(_ lhs: SIMD3<Scalar>, _ rhs: SIMD3<Scalar>) -> Scalar
where Scalar: FixedWidthInteger {
length_squared(lhs &- rhs)
}
@inlinable
func distance_squared<Scalar>(_ lhs: SIMD3<Scalar>, _ rhs: SIMD3<Scalar>) -> Scalar
where Scalar: FloatingPoint {
length_squared(lhs - rhs)
}
@inlinable
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))
}
@inlinable
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))
}
// 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) }
}
}
Submission Info
Submission Time
2025-01-27 03:53:53+0900
Task
D - Souvenirs
User
narumij
Language
Swift (swift 5.8.1)
Score
350
Code Size
307648 Byte
Status
AC
Exec Time
141 ms
Memory
25264 KiB
Compile Error
[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! (32.21s)
Judge Result
Set Name
Sample
All
Score / Max Score
0 / 0
350 / 350
Status
Set Name
Test Cases
Sample
sample00.txt, sample01.txt, sample02.txt
All
sample00.txt, sample01.txt, sample02.txt, testcase00.txt, testcase01.txt, testcase02.txt, testcase03.txt, testcase04.txt, testcase05.txt, testcase06.txt, testcase07.txt, testcase08.txt, testcase09.txt, testcase10.txt, testcase11.txt, testcase12.txt, testcase13.txt, testcase14.txt, testcase15.txt, testcase16.txt, testcase17.txt, testcase18.txt, testcase19.txt, testcase20.txt, testcase21.txt, testcase22.txt, testcase23.txt, testcase24.txt, testcase25.txt, testcase26.txt, testcase27.txt, testcase28.txt, testcase29.txt
Case Name
Status
Exec Time
Memory
sample00.txt
AC 5 ms
15164 KiB
sample01.txt
AC 5 ms
15428 KiB
sample02.txt
AC 5 ms
15256 KiB
testcase00.txt
AC 39 ms
24872 KiB
testcase01.txt
AC 49 ms
24864 KiB
testcase02.txt
AC 30 ms
24116 KiB
testcase03.txt
AC 50 ms
24824 KiB
testcase04.txt
AC 24 ms
24696 KiB
testcase05.txt
AC 23 ms
24548 KiB
testcase06.txt
AC 92 ms
25076 KiB
testcase07.txt
AC 15 ms
15716 KiB
testcase08.txt
AC 81 ms
25168 KiB
testcase09.txt
AC 12 ms
15636 KiB
testcase10.txt
AC 111 ms
25076 KiB
testcase11.txt
AC 5 ms
15460 KiB
testcase12.txt
AC 56 ms
24956 KiB
testcase13.txt
AC 46 ms
21884 KiB
testcase14.txt
AC 113 ms
24984 KiB
testcase15.txt
AC 18 ms
15928 KiB
testcase16.txt
AC 113 ms
25240 KiB
testcase17.txt
AC 24 ms
16700 KiB
testcase18.txt
AC 94 ms
25264 KiB
testcase19.txt
AC 19 ms
17008 KiB
testcase20.txt
AC 68 ms
25232 KiB
testcase21.txt
AC 37 ms
18732 KiB
testcase22.txt
AC 117 ms
24996 KiB
testcase23.txt
AC 25 ms
16920 KiB
testcase24.txt
AC 68 ms
25032 KiB
testcase25.txt
AC 27 ms
16984 KiB
testcase26.txt
AC 100 ms
25144 KiB
testcase27.txt
AC 38 ms
22580 KiB
testcase28.txt
AC 141 ms
25196 KiB
testcase29.txt
AC 78 ms
24096 KiB