//Successor with delete. Given a set of nn integers S={0,1,...,n−1} and a sequence of requests of the following form:
//
//Remove x from S
//Find the successor of x: the smallest y in S such that y≥x.
//design a data type so that all operations (except construction) take logarithmic time or better in the worst case.

import Foundation


class Seq {
    var dict = [Int: Int]()
    init(_ set: Set<Int>) {
        dict[-1] = -1
        for item in set {
            dict[item] = item
        }
    }

    private func root(x: Int) -> Int {
        var i = x
        while i != dict[i] {
            dict[i] = dict[dict[i]!]
            i = dict[i]!
        }
        return i
    }

    func remove(_ x: Int) {
        guard x >= 0 else {
            return
        }
        dict[x] = root(x: x - 1)
    }

    func find(_ x: Int) -> Int? {
        let r = root(x: x)
        return r >= 0 ? r : nil
    }
}

let seq = Seq(Set<Int>([0,1,2,3,4,5,6]))
seq.remove(1)
seq.remove(2)
seq.remove(3)
seq.find(3)
//[0:0, 1:1, 2:2, 3:3, 4:4, 5:5]