CoreFoundation CFTree Based Red-Black Tree

CFRedBlackTreeState.swift

//
//  CFRedBlackTreeState.swift
//  BTree
//
//  Created by 박병관 on 3/5/25.
//


internal struct CFRedBlackTreeState<Key:Comparable> {
    
    var capacity:Int = 0
    var key:Key
    var color:RedBlackColor = .red
    var duplicationCount = 0

    var valueCount = 0
    // left child is nil Node (which is black Node)
    var leftNil = true
    // right child is nil Node (which is black Node)
    var rightNil = true
}

CFRedBlackTreeStorage.swift

//
//  CFRedBlackTreeStorage.swift
//  BTree
//
//  Created by 박병관 on 3/5/25.
//
internal import CoreFoundation

internal final class CFRedBlackTreeStorage<Key:Comparable, Element> {
    

    internal var color:RedBlackColor  {
        get {
            ptr.withUnsafeMutablePointerToHeader{
            $0.pointee.color
            }
        }
        set {
            ptr.withUnsafeMutablePointerToHeader{
                $0.pointee.color = newValue
            }
        }
    }

    internal var leftNil:Bool {
        get {
            ptr.withUnsafeMutablePointerToHeader{
                $0.pointee.leftNil
            }
        }
        set {
            ptr.withUnsafeMutablePointerToHeader{
                $0.pointee.leftNil = newValue
            }
        }
    }

    internal var rightNil:Bool {
        get {
            ptr.withUnsafeMutablePointerToHeader{
                $0.pointee.rightNil
            }
        }
        set {
            ptr.withUnsafeMutablePointerToHeader{
                $0.pointee.rightNil = newValue
            }
        }
    }
    
    class func create(key:Key, capacity:Int) -> CFRedBlackTreeStorage<Key, Element> {
        
        return ManagedBufferPointer<CFRedBlackTreeState<Key>, Element>(bufferClass: Self.self, minimumCapacity: capacity) { buffer, capacity in
            
            CFRedBlackTreeState<Key>(capacity: capacity(buffer) ,key:key)
        }.buffer as! Self
    }
    
    var ptr: ManagedBufferPointer<CFRedBlackTreeState<Key>, Element> {
        .init(unsafeBufferObject: self as AnyObject)
    }
 
    deinit {
        ptr.withUnsafeMutablePointers { header, buffer in
            let bufferPtr = UnsafeMutableBufferPointer(start: buffer, count: header.pointee.capacity)
            bufferPtr[0..<header.pointee.valueCount].deinitialize()
        }
        
    }
    
    var cfContext: CFTreeContext {
        
        .init(
            
            version: 0, info: Unmanaged<AnyObject>.passUnretained(self).toOpaque(), retain: _cfTree_heap_retain, release: _cfTree_heap_release, copyDescription: _cfTree_heap_description
        )
    }
    
}


extension CFRedBlackTreeStorage: CustomStringConvertible {
    
    var description: String {
        ptr.withUnsafeMutablePointerToHeader{
            "\($0.pointee)"
        }
    }
}

CFTree+.swift

//
//  CFTree+.swift
//  BTree
//
//  Created by 박병관 on 3/5/25.
//
internal import CoreFoundation

internal func _cfTree_heap_retain(_ heap: UnsafeRawPointer?) -> UnsafeRawPointer? {
    if let heap {
        return .init(Unmanaged<AnyObject>.fromOpaque(heap).retain().toOpaque())
    } else {
        return nil
    }
}


internal func _cfTree_heap_release(_ heap: UnsafeRawPointer?) {
    if let heap {
        Unmanaged<AnyObject>.fromOpaque(heap).release()
    }
}

internal func _cfTree_heap_description(_ heap: UnsafeRawPointer?) -> Unmanaged<CFString>? {
    if let heap {
        let heap = Unmanaged<AnyObject>.fromOpaque(heap).takeUnretainedValue()
        return Unmanaged.passRetained("\(heap)" as CFString)
    } else {
        return nil
    }
}

RedBlackCFTree.swift

//
//  RedBlackCFTree.swift
//  BTree
//
//  Created by 박병관 on 3/5/25.
//

import Foundation
internal import CoreFoundation


class RedBlackCFTree<Key:Comparable, Element> {
        
    internal var root:CFTree?

    // typealias Element = Void
    
    
    func put(key:Key, value:Element) {
        if let root  {
            
            let a:GenericCFTree<Key,Element> = insertNode(root: root, key: key, value: value, allowDuplication: false)
            self.root = a.tree
        } else {
            let (newRoot, _):(CFTree, Element?) = createRedBlackTreeNode(key: key, value: value, allocator: nil)
            root = newRoot
        }
    }

    func remove(key:Key) -> Element? {
        if let root = root, let node:GenericCFTree<Key,Element> = findNode(root: root, key: key, matching: .equal) {
            let value:Element
            do {
                let storage:CFRedBlackTreeStorage<Key, Element> = getRedBlackTreeStorage(node.tree)!
                value = storage.ptr.withUnsafeMutablePointers { 
                    let bufferPtr = UnsafeMutableBufferPointer(start: $1, count: $0.pointee.capacity)
                    // let buffer = bufferPtr[0..<$0.pointee.valueCount]
                    precondition($0.pointee.valueCount > 0, "invalid access")
                    let value = bufferPtr.moveElement(from: $0.pointee.valueCount - 1)
                    $0.pointee.valueCount -= 1
                    return value
                }
                
            }
            let a:GenericCFTree<Key,Element>? = removeNode(root: root, node: node.tree)
            self.root = a?.tree
            return value
        }
        return nil
    }

    func makeIterator() -> CFTreeIterator<Key, Element> {
        return .init(startNode: root)
    }

    func makeReverseIterator() -> CFTreeReverseIterator<Key, Element> {
        return .init(root: root)
    }

    
}

internal func getRedBlackTreeStorage<Key: Comparable, Element>(_ node: CFTree) -> CFRedBlackTreeStorage<Key, Element>? {
    var context = CFTreeContext()
    CFTreeGetContext(node, &context)

    guard let rawPtr = context.info else { return nil }
    return Unmanaged<CFRedBlackTreeStorage<Key, Element>>.fromOpaque(rawPtr).takeUnretainedValue()
}

internal func createRedBlackTreeNode<Key: Comparable, Element>(key: Key, value:Element, allocator: CFAllocator? = kCFAllocatorDefault) -> (CFTree, Element?) {
    let storage = CFRedBlackTreeStorage<Key, Element>.create(key: key, capacity: 1)
    storage.ptr.withUnsafeMutablePointerToHeader { 
        $0.pointee.color = .black
        $0.pointee.leftNil = true
        $0.pointee.rightNil = true

    }
    storage.ptr.withUnsafeMutablePointers { header, rawbuffer in
        let buffer = UnsafeMutableBufferPointer(start: rawbuffer, count: header.pointee.capacity)
        buffer.initializeElement(at: 0, to: value)
        header.pointee.valueCount += 1
    }
    var context = storage.cfContext
    let tree = CFTreeCreate(allocator, &context)!
    return (tree, nil)
}


func insertNode<Key: Comparable, Element>(root: CFTree, key: Key, value:Element, allowDuplication: Bool = true) -> GenericCFTree<Key,Element> {
    let (newNode, _):(CFTree, Element?) = createRedBlackTreeNode(key: key, value: value, allocator: nil)
    do {
        let newNodeStorage:CFRedBlackTreeStorage<Key, Element> = getRedBlackTreeStorage(newNode)!
        newNodeStorage.color = .red
    }
    // 🌳 Find insertion point (BST Insert)
    var current: CFTree? = root

    while let node = current {
        var storage:CFRedBlackTreeStorage<Key, Element> = getRedBlackTreeStorage(node)!
        if key < storage.ptr.header.key {
            let leftIsNilNode = storage.leftNil
            if leftIsNilNode {
                storage.leftNil = false
                CFTreePrependChild(node, newNode)
                break
            }
            /*
                left is not nil
                right is nil
                -> index0
                
                left is not nil
                right is not nil
                -> index0
                */
            // Move left
            current =  CFTreeGetFirstChild(node) 
        } else if key > storage.ptr.header.key {
            let rightIsNilNode = storage.rightNil
            if rightIsNilNode {
                storage.rightNil = false
                CFTreeAppendChild(node, newNode)
                break
            }
            
            /*
                left-nil
                right nonnil
                -> right is index 0
                
                left-nonnil
                right nonil
                -> right is index 1
                
                */
            let isLeftNil = storage.leftNil
            // Move right
            current = CFTreeGetChildAtIndex(current!, isLeftNil ? 0 : 1)
        } else {
            // duplicated!
            if allowDuplication {
                storage.ptr.withUnsafeMutablePointerToHeader {
                    $0.pointee.duplicationCount += 1
                }
                
                if storage.ptr.header.capacity > storage.ptr.header.valueCount {
                    storage.ptr.withUnsafeMutablePointers { header, buffer in
                        let bufferPtr = UnsafeMutableBufferPointer(start: buffer, count: header.pointee.capacity)
                        bufferPtr.initializeElement(at: header.pointee.valueCount , to: value)
                        header.pointee.valueCount += 1
                    }
                } else {
                    let oldCount = storage.ptr.header.valueCount
                    let newStorage = CFRedBlackTreeStorage<Key,Element>.create(key: key, capacity: oldCount + 1)
                    newStorage.ptr.withUnsafeMutablePointers {
                        let bufferPtr = UnsafeMutableBufferPointer(start: $1, count: $0.pointee.capacity)
                        $0.pointee = storage.ptr.header
                        
                        $0.pointee.valueCount += 1

                        storage.ptr.withUnsafeMutablePointerToElements {
                            let oldBuffer = UnsafeMutableBufferPointer(start: $0, count: oldCount)
                            let _ = bufferPtr.moveInitialize(fromContentsOf: oldBuffer)

                        }
                        storage.ptr.withUnsafeMutablePointerToHeader {
                            $0.pointee.valueCount = 0
                        }
                    }
                    storage = newStorage
                    withUnsafePointer(to: storage.cfContext) {
                        CFTreeSetContext(node, $0)
                    }
                }
            } else {
                
                if storage.ptr.header.capacity > 1 {
                    storage.ptr.withUnsafeMutablePointers {
                        let buffer = UnsafeMutableBufferPointer(start: $1, count: $0.pointee.capacity)
                        let slice = buffer[0..<$0.pointee.valueCount]
                        if slice.isEmpty {
                            buffer.initializeElement(at: 0, to: value)
                            $0.pointee.valueCount += 1
                        } else {
                            let index = slice.index(before: slice.endIndex)
                            slice.deinitializeElement(at: index)
                            slice.initializeElement(at: index, to: value)
                        }
                    }
                } else {
                    let oldCount = storage.ptr.header.valueCount
                    let (tree1, _) = createRedBlackTreeNode(key: key, value: value, allocator: nil)
                    let newStorage:CFRedBlackTreeStorage<Key,Element> = getRedBlackTreeStorage(tree1)!
                    storage = newStorage
                    withUnsafePointer(to: storage.cfContext) {
                        CFTreeSetContext(node, $0)
                    }
                    
                }
            }
            
            return .init(tree: root)
            // return root
        }
    }

    let a: GenericCFTree<Key, Element> = fixRedBlackTreeAfterInsert(root: root, node: newNode)
    return a
}


enum GenericToken<K,V> {
    case token
}

func fixRedBlackTreeAfterInsert<Key: Comparable, Element>(root: CFTree, node: CFTree) -> GenericCFTree<Key,Element> {
    var currentNode = node
    var mutableRoot = root
    while let parent = CFTreeGetParent(currentNode) {
        let parentStorage:CFRedBlackTreeStorage<Key, Element> = getRedBlackTreeStorage(parent)!
        
        // Case 1: Parent is Black -> No fix needed
        if parentStorage.ptr.header.color == .black {
            break
        }

        // Case 2: Parent is Red -> Need Fixing
        guard let grandparent = CFTreeGetParent(parent) else {
            // 🌳 If grandparent is nil, stop (root reached)
            break
        }
        let grandParentStorage:CFRedBlackTreeStorage<Key, Element> = getRedBlackTreeStorage(grandparent)!
        
        let is_parent_is_left = !grandParentStorage.leftNil && CFEqual(CFTreeGetFirstChild(grandparent), parent)
        let uncle = (is_parent_is_left)
            ? CFTreeGetNextSibling(parent)
            : CFTreeGetFirstChild(grandparent)

        let uncleIsRed = if let uncle, let uncleStorage:CFRedBlackTreeStorage<Key, Element> = getRedBlackTreeStorage(uncle) {
            uncleStorage.ptr.header.color == .red
        } else {
            false // 🌳 Treat `nil` uncle as Black
        }

        if uncleIsRed {
          // 🌳 Case 2.1: Uncle is Red -> Recolor
            parentStorage.color = .red
            
            if let uncleStorage:CFRedBlackTreeStorage<Key, Element> = getRedBlackTreeStorage(uncle!) {
                uncleStorage.color = .black
            }
            let grandparentStorage:CFRedBlackTreeStorage<Key, Element> = getRedBlackTreeStorage(grandparent)!
            grandparentStorage.color = .red

            currentNode = grandparent
        } else {
            // 🌳 Case 2.2: Uncle is Black -> Rotate

            // current is the right child
            if parentStorage.leftNil || (CFTreeGetChildAtIndex(parent, 1) == currentNode) {
                let _:GenericToken<Key,Element> = rotateLeft(root: &mutableRoot, parent)
                currentNode = parent
            } else if parentStorage.rightNil || CFEqual(CFTreeGetFirstChild(parent), currentNode) {
                // current is the left child

                parentStorage.color = .black
                grandParentStorage.color = .red
                let _:GenericToken<Key,Element> = rotateRight(root: &mutableRoot, currentNode)
            } else {
                assertionFailure("unreachable")
            }
        }
    }

    // Ensure root is always black
    let rootStorage:CFRedBlackTreeStorage<Key, Element> = getRedBlackTreeStorage(mutableRoot)!
    rootStorage.color = .black
    return .init(tree: mutableRoot)
}

func rotateLeft<Key: Comparable, Element>(root: inout CFTree, _ x: CFTree) -> GenericToken<Key,Element> {
    /**
node is X, rightChild is Y, rightLeftChild is Z


   Before Left Rotation
    X
     \
      Y
     / \
   NIL  Z



After Left Rotation
      Y
     / \
    X   Z
   /
 NIL

    */
    
    let xStorage:CFRedBlackTreeStorage<Key, Element> = getRedBlackTreeStorage(x)!
    let xLeftIsNil = xStorage.leftNil
    
    let y = CFTreeGetChildAtIndex(x, xLeftIsNil ? 0 : 1)!// X.right = Y
    let parent = CFTreeGetParent(x)


    // Y
    let yStorage:CFRedBlackTreeStorage<Key, Element> = getRedBlackTreeStorage(y)!
    
    // Move Y.left to X.right
    if !yStorage.leftNil, let rightLeftChild = CFTreeGetFirstChild(y) {
        CFTreeRemove(rightLeftChild)
        CFTreeAppendChild(x, rightLeftChild)
        xStorage.rightNil = false
        yStorage.leftNil = true
    } else {
        xStorage.rightNil = true
    }

    // Remove Y from its current position
    // CFTreeRemoveChild(parent, rightChild)
    //
    // var root = GenericCFTree<Key,Element>?.none

    // Attach Y in place of X
    if let parent {
        let parentStorage:CFRedBlackTreeStorage<Key, Element> = getRedBlackTreeStorage(parent)!
        let xWasLeftChildOfParent =  CFEqual(CFTreeGetFirstChild(parent), x) && !parentStorage.leftNil
        CFTreeRemove(y)
        if xWasLeftChildOfParent {
            CFTreePrependChild(parent, y)
        } else {
            CFTreeAppendChild(parent, y)
        }
    } else {
        CFTreeRemove(y)
        root = y
    }

    // Make X the left child of Y
    CFTreeRemove(x)
    CFTreePrependChild(y, x)
    yStorage.leftNil = false

    return .token
}


func rotateRight<Key: Comparable, Element>(root: inout CFTree, _ x: CFTree) -> GenericToken<Key,Element> {
    /**
node is X, leftChild is Y


   Before Right Rotation
        X
       /
      Y
     /
    Z




After Right Rotation
      Y
     / \
    Z   X


    */
    let x_storage:CFRedBlackTreeStorage<Key, Element> = getRedBlackTreeStorage(x)!
    let y = CFTreeGetFirstChild(x)! // X.left = Y
    let parent = CFTreeGetParent(x)
   
    let y_storage:CFRedBlackTreeStorage<Key, Element> = getRedBlackTreeStorage(y)!

    // Move Y.right to X.left
    if let leftRightChild = CFTreeGetNextSibling(y) {
        CFTreeRemove(leftRightChild)
        CFTreePrependChild(x, leftRightChild)
        x_storage.leftNil = false
    } else {
        y_storage.rightNil = true
        x_storage.leftNil = true
    }

    // Remove Y from its current position
    

    // Attach Y in place of X
    if let parent  {
        let parentStorage:CFRedBlackTreeStorage<Key, Element> = getRedBlackTreeStorage(parent)!
        let xWasLeftChildOfParent =  CFEqual(CFTreeGetFirstChild(parent), x) && !parentStorage.leftNil
        CFTreeRemove(y)
        if xWasLeftChildOfParent {
            CFTreePrependChild(parent, y)
        } else {
            CFTreeAppendChild(parent, y)
        }
    } else {
        CFTreeRemove(y)
        root = y
    }

    // Make X the right child of Y
    CFTreeRemove(x)
    CFTreeAppendChild(y, x)
    y_storage.rightNil = false

    return .token
}




func removeNode<Key: Comparable, Element>(root: CFTree, node: CFTree) -> GenericCFTree<Key,Element>? {

    let storage:CFRedBlackTreeStorage<Key, Element> = getRedBlackTreeStorage(node)!
    
    // 2️⃣ Handle Duplicate Count
    if storage.ptr.withUnsafeMutablePointerToHeader({ $0.pointee.duplicationCount }) > 1 {
        storage.ptr.withUnsafeMutablePointerToHeader { $0.pointee.duplicationCount -= 1 }
        return .init(tree: root) // Just decrement count, don't delete node
    }
    
    // 3️⃣ Determine which case applies
    let leftNil = storage.ptr.withUnsafeMutablePointerToHeader { $0.pointee.leftNil }
    let rightNil = storage.ptr.withUnsafeMutablePointerToHeader { $0.pointee.rightNil }
    
    if leftNil && rightNil {
        // ✅ Case 1: Leaf Node (Delete and Fix)
        return deleteLeaf(root: root, node: node)
        
    } else if leftNil || rightNil {
        // ✅ Case 2: One Child (Replace and Fix)
        return deleteNodeWithOneChild(root: root, node: node)
        
    } else {
        // ✅ Case 3: Two Children (Find Successor and Delete)
        return deleteNodeWithTwoChildren(root: root, node: node)
    }
}



func deleteLeaf<Key: Comparable, Element>(root: CFTree, node: CFTree) -> GenericCFTree<Key,Element>? {
    let storage:CFRedBlackTreeStorage<Key, Element> = getRedBlackTreeStorage(node)!
    
    if CFEqual(node, root) {
        return nil
    }
    if storage.ptr.header.color == .red {
        // 🔴 If the node is Red, simply delete it
        CFTreeRemove(node)
        return .init(tree: root)
    } else {
        // ⚫ If the node is Black, we must fix the double black issue
        return fixDoubleBlack(root: root, node: node)
    }
}

func deleteNodeWithOneChild<Key: Comparable, Element>(root: CFTree, node: CFTree) -> GenericCFTree<Key,Element> {
    let storage:CFRedBlackTreeStorage<Key, Element> = getRedBlackTreeStorage(node)!
    precondition(CFTreeGetChildCount(node) == 1, "node must contains only one child left or right")
    // storage.leftNil ? (storage.rightNil ? nil : CFTreeGetFirstChild(node)) : CFTreeGetFirstChild(node)
    let child = CFTreeGetFirstChild(node)!
    let parent = CFTreeGetParent(node)
    
    if CFEqual(node, root) {
        
        return .init(tree: child)
    }
    
    // Replace node with child
   
    if let parent {
        let parentStorage:CFRedBlackTreeStorage<Key, Element> = getRedBlackTreeStorage(parent)!
        let nodeIsLeft = !parentStorage.leftNil && CFEqual(CFTreeGetFirstChild(parent), node)
        CFTreeRemove(node)
        CFTreeRemove(child)
        if nodeIsLeft {
            CFTreePrependChild(parent, child)
        } else {
            CFTreeAppendChild(parent, child)
        }
    } else {
        CFTreeRemove(node)
    }
    
    // Fix tree if needed
    if storage.color == .black {
        return fixDoubleBlack(root: root, node: child)
    }
    
    return .init(tree: root)
}



func deleteNodeWithTwoChildren<Key: Comparable, Element>(root: CFTree, node: CFTree) -> GenericCFTree<Key,Element>? {
    precondition(CFTreeGetChildCount(node) == 2, "node must contains two children")
    var successor = CFTreeGetChildAtIndex(node, 1)! // Find inorder successor
    do {
        let sequence = sequence(first: CFTreeGetChildAtIndex(node, 1)!) {
            let storage:CFRedBlackTreeStorage<Key, Element> = getRedBlackTreeStorage($0)!
            if storage.leftNil {
                return nil
            } else {
                return CFTreeGetFirstChild($0)
            }
        }
        for i in sequence {
            successor = i
        }
    }
    let storage:CFRedBlackTreeStorage<Key, Element> = getRedBlackTreeStorage(node)!
    let successorStorage:CFRedBlackTreeStorage<Key, Element> = getRedBlackTreeStorage(successor)!

    // Swap values
    storage.ptr.withUnsafeMutablePointerToHeader { $0.pointee.key = successorStorage.ptr.header.key }

    // Delete successor (which will be a leaf or have 1 child)
    return removeNode(root: root, node: successor)
}


func fixDoubleBlack<Key: Comparable, Element>(root: CFTree, node: CFTree) ->  GenericCFTree<Key, Element> {
    var currentNode = node
    var mutableRoot = root
    
    while let parent = CFTreeGetParent(currentNode) {
        let parentStorage:CFRedBlackTreeStorage<Key, Element> = getRedBlackTreeStorage(parent)!
        let currentIsLeft = !parentStorage.leftNil && CFEqual(CFTreeGetFirstChild(parent), currentNode)
        guard let sibling = CFTreeGetChildCount(parent) == 2 ? CFTreeGetChildAtIndex(parent, currentIsLeft ? 1 : 0) : nil else {
            currentNode = parent
            continue
        }
        let siblingStorage:CFRedBlackTreeStorage<Key, Element> = getRedBlackTreeStorage(sibling)!
    
        if siblingStorage.color == .red {
            parentStorage.color = .red
            siblingStorage.color = .black
            if currentIsLeft {
                // sibling is right
                let _:GenericToken<Key,Element> = rotateLeft(root: &mutableRoot, parent)
            } else {
                let _:GenericToken<Key,Element> = rotateRight(root: &mutableRoot, parent)
            }
            continue
        }
        // below sibling is Black
        
        

        let siblingLeft:CFTree?
        let siblingRight:CFTree?
        let siblingLeftStorage:CFRedBlackTreeStorage<Key, Element>?
        let siblingRightStorage:CFRedBlackTreeStorage<Key, Element>?

        do {
            if CFTreeGetChildCount(sibling) > 1 {
                siblingLeft = siblingStorage.leftNil ? nil : CFTreeGetFirstChild(sibling)
                siblingRight = siblingStorage.rightNil ? nil : CFTreeGetChildAtIndex(sibling, siblingStorage.leftNil ? 0 : 1)
                siblingLeftStorage = siblingLeft == nil ? nil : getRedBlackTreeStorage(siblingLeft!)
                siblingRightStorage = siblingRight == nil ? nil : getRedBlackTreeStorage(siblingRight!)
            } else {
                siblingLeft = nil
                siblingRight = nil
                siblingLeftStorage = nil
                siblingRightStorage = nil
            }
        }
        let siblingLeftColor:RedBlackColor = siblingLeftStorage?.color ?? .black
        let siblingRightColor:RedBlackColor = siblingRightStorage?.color ?? .black
        
        if siblingLeftColor == .black, siblingRightColor == .black {
            siblingStorage.color = .red
            if parentStorage.color == .red {
                parentStorage.color = .black
                break
            } else {
                currentNode = parent
                continue
            }
        }
        
        if currentIsLeft, siblingRightColor == .red {
            siblingRightStorage?.color = siblingStorage.color
            siblingStorage.color = parentStorage.color
            let _:GenericToken<Key,Element> = rotateLeft(root: &mutableRoot, parent)
            break
        }
        if !currentIsLeft, siblingLeftColor == .red {
            siblingLeftStorage?.color = siblingStorage.color
            siblingStorage.color = parentStorage.color
            let _:GenericToken<Key,Element> = rotateRight(root: &mutableRoot, parent)
            break
        }
        if currentIsLeft, siblingLeftColor == .red {
            siblingLeftStorage?.color = parentStorage.color
            let _:GenericToken<Key,Element> = rotateRight(root: &mutableRoot, sibling)
            let _:GenericToken<Key,Element> = rotateLeft(root: &mutableRoot, parent)
            break
        }
        if !currentIsLeft, siblingRightColor == .red {
            siblingRightStorage?.color = parentStorage.color
            let _:GenericToken<Key,Element> = rotateLeft(root: &mutableRoot, sibling)
            let _:GenericToken<Key,Element> = rotateRight(root: &mutableRoot, parent)
            break
        }
        
    }

    let storage:CFRedBlackTreeStorage<Key, Element> = getRedBlackTreeStorage(mutableRoot)!
    storage.color = .black
    return .init(tree: mutableRoot)
}


struct GenericCFTree<Key,Element> {

    var tree:CFTree
}




enum SearchDirection {
    
    case successor
    case predecessor
    case equal
    case equalOrSuccessor
    case equalOrPredecessor
}




struct CFTreeReverseIterator<Key: Comparable, Element>: IteratorProtocol {
     var stack: [CFTree] = []

    init(root: CFTree?) {
        var node = root
        while let currentNode = node {
            stack.append(currentNode) // Push all right nodes onto stack
            let storage:CFRedBlackTreeStorage<Key,Element> = getRedBlackTreeStorage(currentNode)!
            let isLeftNil = storage.ptr.withUnsafeMutablePointerToHeader { $0.pointee.leftNil }
            // pick right
            node = storage.rightNil ? nil : CFTreeGetChildAtIndex(currentNode, isLeftNil ? 0 : 1)
        }
    }

    mutating func next() -> (Key)? {
        guard let node = stack.popLast() else { return nil }
        let storage:CFRedBlackTreeStorage<Key,Element> = getRedBlackTreeStorage(node)!
        
        let key = storage.ptr.header.key
   //     let value = storage.ptr.withUnsafeMutablePointerToElements { $0[0] }

        // // Move to left subtree (previous inorder node)
        var nextNode = storage.leftNil ? nil : CFTreeGetFirstChild(node)
        while let currentNode = nextNode {
            stack.append(currentNode)
            let nodeStorage:CFRedBlackTreeStorage<Key,Element> = getRedBlackTreeStorage(currentNode)!
            
            nextNode = nodeStorage.rightNil ? nil : CFTreeGetChildAtIndex(node, nodeStorage.leftNil ? 0 : 1)
        }

        return (key)
    }
}

struct CFTreeIterator<Key: Comparable, Element>: IteratorProtocol {
    private var stack: [CFTree] = []

    init(startNode: CFTree?) {
        var node = startNode
        while let currentNode = node {
            stack.append(currentNode) // Push all left nodes onto stack
            let storage:CFRedBlackTreeStorage<Key,Element> = getRedBlackTreeStorage(currentNode)!
            node = storage.leftNil ? nil : CFTreeGetFirstChild(currentNode)
        }
    }

    mutating func next() -> (Key)? {
        guard let node = stack.popLast() else { return nil }
        let storage:CFRedBlackTreeStorage<Key,Element> = getRedBlackTreeStorage(node)!
        
        let key = storage.ptr.header.key
      //  let value = storage.ptr.withUnsafeMutablePointerToElements { $0[0] }

        // Move to right subtree (next inorder node)
        var nextNode = storage.rightNil ? nil : CFTreeGetChildAtIndex(node, storage.leftNil ? 0 : 1)
        while let currentNode = nextNode {
            stack.append(currentNode)
            let nodeStorage:CFRedBlackTreeStorage<Key,Element> = getRedBlackTreeStorage(currentNode)!
            
            nextNode = nodeStorage.leftNil ? nil : CFTreeGetFirstChild(currentNode)
        }

        return (key)
    }
}

func findNode<Key: Comparable, Element>(root: CFTree, key: Key, matching: SearchDirection) -> GenericCFTree<Key, Element>? {
    var current: CFTree? = root
    var targetNode: CFTree? = nil

    while let node = current {
        let storage: CFRedBlackTreeStorage<Key, Element> = getRedBlackTreeStorage(node)!
        let nodeKey = storage.ptr.header.key

        switch matching {
        case .equal:
            if key == nodeKey {
                return .init(tree: node) // Exact match found
            }
            current = key < nodeKey ? CFTreeGetFirstChild(node) : CFTreeGetChildAtIndex(node, storage.leftNil ? 0 : 1)

        case .successor, .equalOrSuccessor:
            if key < nodeKey {
                targetNode = node // Potential successor
                current = CFTreeGetFirstChild(node)
            } else if key > nodeKey {
                current = CFTreeGetChildAtIndex(node, storage.leftNil ? 0 : 1)
            } else { // key == nodeKey
                if matching == .equalOrSuccessor {
                    return .init(tree: node) // Exact match
                }
                
                // If exact key found, get its inorder successor
                if var successor = CFTreeGetChildAtIndex(node, storage.leftNil ? 0 : 1) {
                    while let left = CFTreeGetFirstChild(successor) {
                        successor = left
                    }
                    targetNode = successor
                }
                current = nil
            }

        case .predecessor, .equalOrPredecessor:
            if key > nodeKey {
                targetNode = node // Potential predecessor
                let isLeftNil = storage.ptr.withUnsafeMutablePointerToHeader { $0.pointee.leftNil }
                current = CFTreeGetChildAtIndex(node, isLeftNil ? 0 : 1)
            } else if key < nodeKey {
                current = CFTreeGetFirstChild(node)
            } else { // key == nodeKey
                if matching == .equalOrPredecessor {
                    return .init(tree: node) // Exact match
                }
                // If exact key found, get its inorder predecessor
                if var predecessor = CFTreeGetFirstChild(node) {
                    
                    while let right = CFTreeGetNextSibling(predecessor) {
                        predecessor = right
                    }
                    targetNode = predecessor
                }
                current = nil
            }
        }
    }
    if let targetNode {
        return .init(tree: targetNode)
    }
    return nil
}

RedBlackColor.swift

//
//  RedBlackColor.swift
//  BTree
//
//  Created by 박병관 on 3/5/25.
//


internal enum RedBlackColor: Hashable {
    case red
    case black
}