# cython: language_level=2

cdef class RBNode:
    cdef public object obj
    cdef public double start, end
    cdef public int red
    cdef public RBNode left, right, parent

cdef class RBTree:
    cdef public RBNode nil, root

    cpdef getroot(RBTree self)
    cdef void __rotate_left(RBTree self, RBNode x)
    cdef void __rotate_right(RBTree self, RBNode y)
    cdef RBNode __successor(RBTree self, RBNode x)
    cpdef RBNode successor(RBTree self, RBNode x)
    cdef RBNode __predecessor(RBTree self, RBNode x)
    cpdef RBNode predecessor(RBTree self, RBNode x)
    cpdef insert(RBTree self, RBNode z)
    cdef void __insert_fixup(RBTree self, RBNode x)
    cpdef delete(RBTree self, RBNode z)
    cdef inline void __delete_fixup(RBTree self, RBNode x)
    cpdef RBNode find(RBTree self, double start, double end)
    cpdef RBNode find_left_end(RBTree self, double t)
    cpdef RBNode find_right_start(RBTree self, double t)
