func (t *Tree) DoRangeReverse(fn Operation, from, to Comparable) bool {
	if t.Root == nil {
		return false
	}
	if from.Compare(to) < 0 {
		panic("llrb: inverted range")
	}
	return t.Root.doRangeReverse(fn, from, to)
}
DoRangeReverse performs fn on all values stored in the tree over the interval (to, from] from
right to left. If from is less than to DoRange will panic. A boolean is returned indicating
whether the Do traversal was interrupted by an Operation returning true. If fn alters stored
values' sort relationships future tree operation behaviors are undefined.
package llrb
const (
	TD234 = iota
	BU23
)
const Mode = BU23
func init() {
	if Mode != TD234 && Mode != BU23 {
		panic("llrb: unknown mode")
	}
}
type Comparable interface {
	Compare(Comparable) int
}
type Color bool
func (c Color) String() string {
	if c {
		return "Black"
	}
	return "Red"
}
const (
	Red   Color = false
	Black Color = true
)
type Node struct {
	Elem        Comparable
	Left, Right *Node
	Color       Color
}
type Tree struct {
	Root  *Node  
	Count int    
}
func (n *Node) color() Color {
	if n == nil {
		return Black
	}
	return n.Color
}
func (n *Node) rotateLeft() (root *Node) {
	root = n.Right
	n.Right = root.Left
	root.Left = n
	root.Color = n.Color
	n.Color = Red
	return
}
func (n *Node) rotateRight() (root *Node) {
	root = n.Left
	n.Left = root.Right
	root.Right = n
	root.Color = n.Color
	n.Color = Red
	return
}
func (n *Node) flipColors() {
	n.Color = !n.Color
	n.Left.Color = !n.Left.Color
	n.Right.Color = !n.Right.Color
}
func (n *Node) fixUp() *Node {
	if n.Right.color() == Red {
		if Mode == TD234 && n.Right.Left.color() == Red {
			n.Right = n.Right.rotateRight()
		}
		n = n.rotateLeft()
	}
	if n.Left.color() == Red && n.Left.Left.color() == Red {
		n = n.rotateRight()
	}
	if Mode == BU23 && n.Left.color() == Red && n.Right.color() == Red {
		n.flipColors()
	}
	return n
}
func (n *Node) moveRedLeft() *Node {
	n.flipColors()
	if n.Right.Left.color() == Red {
		n.Right = n.Right.rotateRight()
		n = n.rotateLeft()
		n.flipColors()
		if Mode == TD234 && n.Right.Right.color() == Red {
			n.Right = n.Right.rotateLeft()
		}
	}
	return n
}
func (n *Node) moveRedRight() *Node {
	n.flipColors()
	if n.Left.Left.color() == Red {
		n = n.rotateRight()
		n.flipColors()
	}
	return n
}
func (t *Tree) Len() int {
	return t.Count
}
func (t *Tree) Get(q Comparable) Comparable {
	if t.Root == nil {
		return nil
	}
	n := t.Root.search(q)
	if n == nil {
		return nil
	}
	return n.Elem
}
func (n *Node) search(q Comparable) *Node {
	for n != nil {
		switch c := q.Compare(n.Elem); {
		case c == 0:
			return n
		case c < 0:
			n = n.Left
		default:
			n = n.Right
		}
	}
	return n
}
func (t *Tree) Insert(e Comparable) {
	var d int
	t.Root, d = t.Root.insert(e)
	t.Count += d
	t.Root.Color = Black
}
func (n *Node) insert(e Comparable) (root *Node, d int) {
	if n == nil {
		return &Node{Elem: e}, 1
	} else if n.Elem == nil {
		n.Elem = e
		return n, 1
	}
	if Mode == TD234 {
		if n.Left.color() == Red && n.Right.color() == Red {
			n.flipColors()
		}
	}
	switch c := e.Compare(n.Elem); {
	case c == 0:
		n.Elem = e
	case c < 0:
		n.Left, d = n.Left.insert(e)
	default:
		n.Right, d = n.Right.insert(e)
	}
	if n.Right.color() == Red && n.Left.color() == Black {
		n = n.rotateLeft()
	}
	if n.Left.color() == Red && n.Left.Left.color() == Red {
		n = n.rotateRight()
	}
	if Mode == BU23 {
		if n.Left.color() == Red && n.Right.color() == Red {
			n.flipColors()
		}
	}
	root = n
	return
}
func (t *Tree) DeleteMin() {
	if t.Root == nil {
		return
	}
	var d int
	t.Root, d = t.Root.deleteMin()
	t.Count += d
	if t.Root == nil {
		return
	}
	t.Root.Color = Black
}
func (n *Node) deleteMin() (root *Node, d int) {
	if n.Left == nil {
		return nil, -1
	}
	if n.Left.color() == Black && n.Left.Left.color() == Black {
		n = n.moveRedLeft()
	}
	n.Left, d = n.Left.deleteMin()
	root = n.fixUp()
	return
}
func (t *Tree) DeleteMax() {
	if t.Root == nil {
		return
	}
	var d int
	t.Root, d = t.Root.deleteMax()
	t.Count += d
	if t.Root == nil {
		return
	}
	t.Root.Color = Black
}
func (n *Node) deleteMax() (root *Node, d int) {
	if n.Left != nil && n.Left.color() == Red {
		n = n.rotateRight()
	}
	if n.Right == nil {
		return nil, -1
	}
	if n.Right.color() == Black && n.Right.Left.color() == Black {
		n = n.moveRedRight()
	}
	n.Right, d = n.Right.deleteMax()
	root = n.fixUp()
	return
}
func (t *Tree) Delete(e Comparable) {
	if t.Root == nil {
		return
	}
	var d int
	t.Root, d = t.Root.delete(e)
	t.Count += d
	if t.Root == nil {
		return
	}
	t.Root.Color = Black
}
func (n *Node) delete(e Comparable) (root *Node, d int) {
	if e.Compare(n.Elem) < 0 {
		if n.Left != nil {
			if n.Left.color() == Black && n.Left.Left.color() == Black {
				n = n.moveRedLeft()
			}
			n.Left, d = n.Left.delete(e)
		}
	} else {
		if n.Left.color() == Red {
			n = n.rotateRight()
		}
		if n.Right == nil && e.Compare(n.Elem) == 0 {
			return nil, -1
		}
		if n.Right != nil {
			if n.Right.color() == Black && n.Right.Left.color() == Black {
				n = n.moveRedRight()
			}
			if e.Compare(n.Elem) == 0 {
				n.Elem = n.Right.min().Elem
				n.Right, d = n.Right.deleteMin()
			} else {
				n.Right, d = n.Right.delete(e)
			}
		}
	}
	root = n.fixUp()
	return
}
func (t *Tree) Min() Comparable {
	if t.Root == nil {
		return nil
	}
	return t.Root.min().Elem
}
func (n *Node) min() *Node {
	for ; n.Left != nil; n = n.Left {
	}
	return n
}
func (t *Tree) Max() Comparable {
	if t.Root == nil {
		return nil
	}
	return t.Root.max().Elem
}
func (n *Node) max() *Node {
	for ; n.Right != nil; n = n.Right {
	}
	return n
}
func (t *Tree) Floor(q Comparable) Comparable {
	if t.Root == nil {
		return nil
	}
	n := t.Root.floor(q)
	if n == nil {
		return nil
	}
	return n.Elem
}
func (n *Node) floor(q Comparable) *Node {
	if n == nil {
		return nil
	}
	switch c := q.Compare(n.Elem); {
	case c == 0:
		return n
	case c < 0:
		return n.Left.floor(q)
	default:
		if r := n.Right.floor(q); r != nil {
			return r
		}
	}
	return n
}
func (t *Tree) Ceil(q Comparable) Comparable {
	if t.Root == nil {
		return nil
	}
	n := t.Root.ceil(q)
	if n == nil {
		return nil
	}
	return n.Elem
}
func (n *Node) ceil(q Comparable) *Node {
	if n == nil {
		return nil
	}
	switch c := q.Compare(n.Elem); {
	case c == 0:
		return n
	case c > 0:
		return n.Right.ceil(q)
	default:
		if l := n.Left.ceil(q); l != nil {
			return l
		}
	}
	return n
}
type Operation func(Comparable) (done bool)
func (t *Tree) Do(fn Operation) bool {
	if t.Root == nil {
		return false
	}
	return t.Root.do(fn)
}
func (n *Node) do(fn Operation) (done bool) {
	if n.Left != nil {
		done = n.Left.do(fn)
		if done {
			return
		}
	}
	done = fn(n.Elem)
	if done {
		return
	}
	if n.Right != nil {
		done = n.Right.do(fn)
	}
	return
}
func (t *Tree) DoReverse(fn Operation) bool {
	if t.Root == nil {
		return false
	}
	return t.Root.doReverse(fn)
}
func (n *Node) doReverse(fn Operation) (done bool) {
	if n.Right != nil {
		done = n.Right.doReverse(fn)
		if done {
			return
		}
	}
	done = fn(n.Elem)
	if done {
		return
	}
	if n.Left != nil {
		done = n.Left.doReverse(fn)
	}
	return
}
func (t *Tree) DoRange(fn Operation, from, to Comparable) bool {
	if t.Root == nil {
		return false
	}
	if from.Compare(to) > 0 {
		panic("llrb: inverted range")
	}
	return t.Root.doRange(fn, from, to)
}
func (n *Node) doRange(fn Operation, lo, hi Comparable) (done bool) {
	lc, hc := lo.Compare(n.Elem), hi.Compare(n.Elem)
	if lc <= 0 && n.Left != nil {
		done = n.Left.doRange(fn, lo, hi)
		if done {
			return
		}
	}
	if lc <= 0 && hc > 0 {
		done = fn(n.Elem)
		if done {
			return
		}
	}
	if hc > 0 && n.Right != nil {
		done = n.Right.doRange(fn, lo, hi)
	}
	return
}