Swift Performance Example

main.swift

import Foundation


class Node {
    let x: Int
    let y: Int
    var left: Node? = nil
    var right: Node? = nil

    init(x: Int) {
        self.x = x
        self.y = Int.random(in: 0...Int.max)
    }
}

func merge(lower: Node?, greater: Node?) -> Node?
{
    guard let lower = lower else { return greater }
    guard let greater = greater else { return lower }

    if lower.y < greater.y {
        lower.right = merge(lower: lower.right, greater: greater)
        return lower
    } else {
        greater.left = merge(lower: lower, greater: greater.left)
        return greater
    }
}

func splitBinary(orig: Node, value: Int) -> (Node?, Node?)
{
    if orig.x < value, let right = orig.right {
        let splitPair = splitBinary(orig: right, value: value)
        orig.right = splitPair.0
        return (orig, splitPair.1)
    } else if let left = orig.left {
        let splitPair = splitBinary(orig: left, value: value)
        orig.left = splitPair.1
        return (splitPair.0, orig)
    }
    return (nil, nil)
}

func merge(lower: Node?, equal: Node?, greater: Node?) -> Node?
{
    return merge(lower: merge(lower: lower, greater: equal), greater: greater)
}

struct SplitResult {
    var lower: Node?
    var equal: Node?
    var greater: Node?

    init(lower: Node?, equal: Node?, greater: Node?) {
        self.lower = lower
        self.equal = equal
        self.greater = greater
    }
}

func split(orig: Node, value: Int) -> SplitResult
{
    let (lower, other) = splitBinary(orig: orig, value: value)
    guard let equalGreater = other else { return SplitResult(lower: lower, equal: nil, greater: nil) }
    let (equal, greater) = splitBinary(orig: equalGreater, value: value + 1)
    return SplitResult(lower: lower, equal: equal, greater: greater)
}

class Tree
{
    func hasValue(x: Int) -> Bool
    {
        guard let mRoot = mRoot else { return false }
        let splited = split(orig: mRoot, value: x)
        let res = splited.equal != nil
        self.mRoot = merge(lower: splited.lower, equal: splited.equal, greater: splited.greater)
        return res
    }

    func insert(x: Int)
    {
        guard let mRoot = mRoot else {
            self.mRoot = Node(x: x)
            return
        }

        var splited = split(orig: mRoot, value: x)
        if splited.equal == nil {
            splited.equal = Node(x: x)
        }
        self.mRoot = merge(lower: splited.lower, equal: splited.equal, greater: splited.greater)
    }

    func erase(x: Int)
    {
        guard let mRoot = mRoot else {
            return
        }

        let splited = split(orig: mRoot, value: x)
        self.mRoot = merge(lower: splited.lower, greater: splited.greater)
    }

    private var mRoot: Node? = nil
}


func runNaive() -> Int
{
    let tree = Tree()
    var cur = 5;
    var res = 0

    for i in 1..<1000000 {
        let a = i % 3
        cur = (cur * 57 + 43) % 10007
        switch a {
            case 0: tree.insert(x: cur)
            case 1: tree.erase(x: cur)
            case 2: if tree.hasValue(x: cur) { res += 1 }
            default: break
        }
    }
    return res
}

print("Naive result \(runNaive())")