func (t *IntTree) Ceil(q IntInterface) (o IntInterface, err error) {
	if t.Root == nil {
		return
	}
	n := t.Root.ceil(q.Range().Start, q.ID())
	if n == nil {
		return
	}
	return n.Elem, nil
}
Ceil returns the smallest value equal to or greater than the query q according to
q.Start().Compare(), with ties broken by comparison of ID() values.
package interval
import (
	"github.com/biogo/store/llrb"
)
type IntOverlapper interface {
	Overlap(IntRange) bool
}
type IntRange struct {
	Start, End int
}
type IntInterface interface {
	IntOverlapper
	Range() IntRange
	ID() uintptr  
}
type IntNode struct {
	Elem        IntInterface
	Interval    IntRange
	Range       IntRange
	Left, Right *IntNode
	Color       llrb.Color
}
type IntTree struct {
	Root  *IntNode  
	Count int       
}
func (n *IntNode) color() llrb.Color {
	if n == nil {
		return llrb.Black
	}
	return n.Color
}
func intMaxRange(root, left, right *IntNode) int {
	end := root.Interval.End
	if left != nil && left.Range.End > end {
		end = left.Range.End
	}
	if right != nil && right.Range.End > end {
		end = right.Range.End
	}
	return end
}
func (n *IntNode) rotateLeft() (root *IntNode) {
	root = n.Right
	n.Right = root.Left
	root.Left = n
	root.Color = n.Color
	n.Color = llrb.Red
	root.Left.Range.End = intMaxRange(root.Left, root.Left.Left, root.Left.Right)
	if root.Left == nil {
		root.Range.Start = root.Interval.Start
	} else {
		root.Range.Start = root.Left.Range.Start
	}
	root.Range.End = intMaxRange(root, root.Left, root.Right)
	return
}
func (n *IntNode) rotateRight() (root *IntNode) {
	root = n.Left
	n.Left = root.Right
	root.Right = n
	root.Color = n.Color
	n.Color = llrb.Red
	if root.Right.Left == nil {
		root.Right.Range.Start = root.Right.Interval.Start
	} else {
		root.Right.Range.Start = root.Right.Left.Range.Start
	}
	root.Right.Range.End = intMaxRange(root.Right, root.Right.Left, root.Right.Right)
	root.Range.End = intMaxRange(root, root.Left, root.Right)
	return
}
func (n *IntNode) flipColors() {
	n.Color = !n.Color
	n.Left.Color = !n.Left.Color
	n.Right.Color = !n.Right.Color
}
func (n *IntNode) fixUp(fast bool) *IntNode {
	if !fast {
		n.adjustRange()
	}
	if n.Right.color() == llrb.Red {
		if Mode == TD234 && n.Right.Left.color() == llrb.Red {
			n.Right = n.Right.rotateRight()
		}
		n = n.rotateLeft()
	}
	if n.Left.color() == llrb.Red && n.Left.Left.color() == llrb.Red {
		n = n.rotateRight()
	}
	if Mode == BU23 && n.Left.color() == llrb.Red && n.Right.color() == llrb.Red {
		n.flipColors()
	}
	return n
}
func (n *IntNode) adjustRange() {
	if n.Left == nil {
		n.Range.Start = n.Interval.Start
	} else {
		n.Range.Start = n.Left.Range.Start
	}
	n.Range.End = intMaxRange(n, n.Left, n.Right)
}
func (n *IntNode) moveRedLeft() *IntNode {
	n.flipColors()
	if n.Right.Left.color() == llrb.Red {
		n.Right = n.Right.rotateRight()
		n = n.rotateLeft()
		n.flipColors()
		if Mode == TD234 && n.Right.Right.color() == llrb.Red {
			n.Right = n.Right.rotateLeft()
		}
	}
	return n
}
func (n *IntNode) moveRedRight() *IntNode {
	n.flipColors()
	if n.Left.Left.color() == llrb.Red {
		n = n.rotateRight()
		n.flipColors()
	}
	return n
}
func (t *IntTree) Len() int {
	return t.Count
}
func (t *IntTree) Get(q IntOverlapper) (o []IntInterface) {
	if t.Root != nil && q.Overlap(t.Root.Range) {
		t.Root.doMatch(func(e IntInterface) (done bool) { o = append(o, e); return }, q)
	}
	return
}
func (t *IntTree) AdjustRanges() {
	if t.Root == nil {
		return
	}
	t.Root.adjustRanges()
}
func (n *IntNode) adjustRanges() {
	if n.Left != nil {
		n.Left.adjustRanges()
	}
	if n.Right != nil {
		n.Right.adjustRanges()
	}
	n.adjustRange()
}
func (t *IntTree) Insert(e IntInterface, fast bool) (err error) {
	if r := e.Range(); r.Start > r.End {
		return ErrInvertedRange
	}
	var d int
	t.Root, d = t.Root.insert(e, e.Range(), e.ID(), fast)
	t.Count += d
	t.Root.Color = llrb.Black
	return
}
func (n *IntNode) insert(e IntInterface, r IntRange, id uintptr, fast bool) (root *IntNode, d int) {
	if n == nil {
		return &IntNode{Elem: e, Interval: r, Range: r}, 1
	} else if n.Elem == nil {
		n.Elem = e
		n.Interval = r
		if !fast {
			n.adjustRange()
		}
		return n, 1
	}
	if Mode == TD234 {
		if n.Left.color() == llrb.Red && n.Right.color() == llrb.Red {
			n.flipColors()
		}
	}
	switch c := r.Start - n.Interval.Start; {
	case c == 0:
		switch {
		case id == n.Elem.ID():
			n.Elem = e
			n.Interval = r
			if !fast {
				n.Range.End = r.End
			}
		case id < n.Elem.ID():
			n.Left, d = n.Left.insert(e, r, id, fast)
		default:
			n.Right, d = n.Right.insert(e, r, id, fast)
		}
	case c < 0:
		n.Left, d = n.Left.insert(e, r, id, fast)
	default:
		n.Right, d = n.Right.insert(e, r, id, fast)
	}
	if n.Right.color() == llrb.Red && n.Left.color() == llrb.Black {
		n = n.rotateLeft()
	}
	if n.Left.color() == llrb.Red && n.Left.Left.color() == llrb.Red {
		n = n.rotateRight()
	}
	if Mode == BU23 {
		if n.Left.color() == llrb.Red && n.Right.color() == llrb.Red {
			n.flipColors()
		}
	}
	if !fast {
		n.adjustRange()
	}
	root = n
	return
}
func (t *IntTree) DeleteMin(fast bool) {
	if t.Root == nil {
		return
	}
	var d int
	t.Root, d = t.Root.deleteMin(fast)
	t.Count += d
	if t.Root == nil {
		return
	}
	t.Root.Color = llrb.Black
}
func (n *IntNode) deleteMin(fast bool) (root *IntNode, d int) {
	if n.Left == nil {
		return nil, -1
	}
	if n.Left.color() == llrb.Black && n.Left.Left.color() == llrb.Black {
		n = n.moveRedLeft()
	}
	n.Left, d = n.Left.deleteMin(fast)
	if n.Left == nil {
		n.Range.Start = n.Elem.Range().Start
	}
	root = n.fixUp(fast)
	return
}
func (t *IntTree) DeleteMax(fast bool) {
	if t.Root == nil {
		return
	}
	var d int
	t.Root, d = t.Root.deleteMax(fast)
	t.Count += d
	if t.Root == nil {
		return
	}
	t.Root.Color = llrb.Black
}
func (n *IntNode) deleteMax(fast bool) (root *IntNode, d int) {
	if n.Left != nil && n.Left.color() == llrb.Red {
		n = n.rotateRight()
	}
	if n.Right == nil {
		return nil, -1
	}
	if n.Right.color() == llrb.Black && n.Right.Left.color() == llrb.Black {
		n = n.moveRedRight()
	}
	n.Right, d = n.Right.deleteMax(fast)
	if n.Right == nil {
		n.Range.End = n.Elem.Range().End
	}
	root = n.fixUp(fast)
	return
}
func (t *IntTree) Delete(e IntInterface, fast bool) (err error) {
	if r := e.Range(); r.Start > r.End {
		return ErrInvertedRange
	}
	if t.Root == nil || !e.Overlap(t.Root.Range) {
		return
	}
	var d int
	t.Root, d = t.Root.delete(e.Range().Start, e.ID(), fast)
	t.Count += d
	if t.Root == nil {
		return
	}
	t.Root.Color = llrb.Black
	return
}
func (n *IntNode) delete(m int, id uintptr, fast bool) (root *IntNode, d int) {
	if p := m - n.Interval.Start; p < 0 || (p == 0 && id < n.Elem.ID()) {
		if n.Left != nil {
			if n.Left.color() == llrb.Black && n.Left.Left.color() == llrb.Black {
				n = n.moveRedLeft()
			}
			n.Left, d = n.Left.delete(m, id, fast)
			if n.Left == nil {
				n.Range.Start = n.Interval.Start
			}
		}
	} else {
		if n.Left.color() == llrb.Red {
			n = n.rotateRight()
		}
		if n.Right == nil && id == n.Elem.ID() {
			return nil, -1
		}
		if n.Right != nil {
			if n.Right.color() == llrb.Black && n.Right.Left.color() == llrb.Black {
				n = n.moveRedRight()
			}
			if id == n.Elem.ID() {
				m := n.Right.min()
				n.Elem = m.Elem
				n.Interval = m.Interval
				n.Right, d = n.Right.deleteMin(fast)
			} else {
				n.Right, d = n.Right.delete(m, id, fast)
			}
			if n.Right == nil {
				n.Range.End = n.Interval.End
			}
		}
	}
	root = n.fixUp(fast)
	return
}
func (t *IntTree) Min() IntInterface {
	if t.Root == nil {
		return nil
	}
	return t.Root.min().Elem
}
func (n *IntNode) min() *IntNode {
	for ; n.Left != nil; n = n.Left {
	}
	return n
}
func (t *IntTree) Max() IntInterface {
	if t.Root == nil {
		return nil
	}
	return t.Root.max().Elem
}
func (n *IntNode) max() *IntNode {
	for ; n.Right != nil; n = n.Right {
	}
	return n
}
func (t *IntTree) Floor(q IntInterface) (o IntInterface, err error) {
	if t.Root == nil {
		return
	}
	n := t.Root.floor(q.Range().Start, q.ID())
	if n == nil {
		return
	}
	return n.Elem, nil
}
func (n *IntNode) floor(m int, id uintptr) *IntNode {
	if n == nil {
		return nil
	}
	switch c := m - n.Interval.Start; {
	case c == 0:
		switch {
		case id == n.Elem.ID():
			return n
		case id < n.Elem.ID():
			return n.Left.floor(m, id)
		default:
			if r := n.Right.floor(m, id); r != nil {
				return r
			}
		}
	case c < 0:
		return n.Left.floor(m, id)
	default:
		if r := n.Right.floor(m, id); r != nil {
			return r
		}
	}
	return n
}