type Treap<'TPayload, 'TRank> =
    | Inner of 'TRank * int * Treap<'TPayload, 'TRank> * Treap<'TPayload, 'TRank>
    | Leaf  of 'TPayload
    | Empty

type TreapSchema<'TPayload, 'TRank>(operation : 'TRank -> 'TRank -> 'TRank,
                                    identity  : 'TRank,
                                    norm      : 'TPayload -> 'TRank) =
    let random = new Random()

    let (|RankAndPriority|) t =
        match t with
        | Inner(rank, prio, _, _) -> (rank, prio)
        | Leaf(payload)           -> (norm payload, Int32.MaxValue)
        | Empty                   -> (identity, 0)

    member this.empty         = Treap<'TPayload, 'TRank>.Empty          // returns an empty sequence
    member this.build payload = Treap<'TPayload, 'TRank>.Leaf(payload)  // returns a single-element sequence
    member this.rankOf t      = (|RankAndPriority|) t |> fst            // returns the aggregate rank of t

    // returns an iterable sequence of leaf payloads in t, or the empty sequence if there are no leaves
    member this.elems t =
        seq {
            match t with
            | Inner(_, _, left, right) ->
                yield! this.elems left
                yield! this.elems right
            | Leaf(payload) -> yield payload
            | Empty -> ()
        }

    // Returns the result of joining t and u by inserting a new inner node with a random priority
    member this.join t u =
        let pivotPrio = random.Next()
        let rec join' t u =
            match t, u with
            | _, Empty -> t
            | Empty, _ -> u
            | Inner(tRank, tPrio, tLeft, tRight), RankAndPriority(uRank, uPrio) when tPrio < uPrio && tPrio < pivotPrio ->
                Inner(operation tRank uRank, tPrio, tLeft, join' tRight u)      // make t local root
            | RankAndPriority(tRank, tPrio), Inner(uRank, uPrio, uLeft, uRight) when uPrio < tPrio && uPrio < pivotPrio ->
                Inner(operation tRank uRank, uPrio, join' t uLeft, uRight)      // make u local root
            | RankAndPriority(tRank, _), RankAndPriority(uRank, _) ->
                Inner(operation tRank uRank, pivotPrio, t, u)         // insert a new local root and finish
        join' t u

    // Returns the two trees that result from splitting t according to a predicate pred. The split is performed so that
    // pred(r) = false for the rank of ALL items stored in the left tree, and pred(r) = true for the rank of the FIRST
    // item in the right tree. Note that for predicates that specify a split "in the middle" of a leaf, you can inspect
    // the rank of the left tree to determine the location of the actual split. Either resulting tree may be empty depending
    // on both t and pred.
    member this.split pred t =
        let rec split' agg t =
            match t with
            | Inner(_, _, left, right) ->
                let localrank = operation agg (this.rankOf left)
                if pred localrank then
                    let left1, left2 = split' agg left              // continue split down left subtree
                    (left1, this.join left2 right)
                else
                    let right1, right2 = split' localrank right     // continue split down right subtree
                    (this.join left right1, right2)
            | RankAndPriority(rank, _) -> if pred (operation agg rank) then (Empty, t) else (t, Empty)
        split' identity t