func (n *Node) Next() *Node {
	return n.walk1(1)
}
Next returns the next Node in an in-order walk
of the Tree holding the Node n.
package avl
import (
	"errors"
	"fmt"
	"reflect"
)
type Node struct {
	val reflect.Value
	c   [2]*Node
	p   *Node
	b   int8
}
type Setter interface {
	SetTree(*Tree)
}
type Tree struct {
	root     *Node
	elemType reflect.Type
	size     int
	cmp      func(a, b reflect.Value) int8
}
type DummyTree struct {
	*Tree
	Insert func(Dummy)
	Delete func(Dummy)
	Lookup func(Dummy) (Dummy, bool)
	Value func(*Node) Dummy
}
func (DummyTree) Compare(a, b Dummy) int {
	return 0
}
func (d *DummyTree) SetTree(t *Tree) {
	d.Tree = t
}
type Dummy interface{}
func Make(treeStruct interface{}) error {
	tsVal := reflect.ValueOf(treeStruct)
	cmp := tsVal.MethodByName("Compare")
	err := checkCompare(cmp)
	if err != nil {
		return err
	}
	t := &Tree{elemType: cmp.Type().In(0)}
	t.cmp = makeCmp(cmp)
	err = t.makeFnImpls(tsVal)
	if err != nil {
		return err
	}
	if setter, ok := treeStruct.(Setter); ok {
		setter.SetTree(t)
	}
	return nil
}
func checkCompare(cmp reflect.Value) error {
	if !cmp.IsValid() {
		return errors.New("Tree interface does not have a Compare method")
	}
	cmpType := cmp.Type()
	if cmpType.Kind() != reflect.Func {
		return errors.New("Compare is not a method")
	}
	if cmpType.NumIn() < 1 {
		return errors.New("Compare method must take two arguments")
	}
	elemType := cmpType.In(0)
	in := []reflect.Type{elemType, elemType}
	out := []reflect.Type{reflect.TypeOf(0)}
	correctType := reflect.FuncOf(in, out, false)
	if cmpType != correctType {
		return fmt.Errorf("Compare method should have signature: %v", correctType)
	}
	return nil
}
func makeCmp(cmp reflect.Value) func(reflect.Value, reflect.Value) int8 {
	args := make([]reflect.Value, 2)
	return func(a, b reflect.Value) int8 {
		args[0] = a
		args[1] = b
		r := cmp.Call(args)[0].Int()
		switch {
		case r < 0:
			return -1
		default:
			return 0
		case r > 0:
			return 1
		}
	}
}
type treeFn struct {
	impl func([]reflect.Value) []reflect.Value
	in   []reflect.Type
	out  []reflect.Type
}
func (t *Tree) makeFnImpls(tsVal reflect.Value) error {
	fns := map[string]treeFn{
		"Insert": {
			t.insert,
			[]reflect.Type{t.elemType},
			[]reflect.Type{},
		},
		"Delete": {
			t.delete,
			[]reflect.Type{t.elemType},
			[]reflect.Type{},
		},
		"Lookup": {
			t.lookup,
			[]reflect.Type{t.elemType},
			[]reflect.Type{t.elemType, reflect.TypeOf(false)},
		},
		"Value": {
			t.value,
			[]reflect.Type{reflect.TypeOf(&Node{})},
			[]reflect.Type{t.elemType},
		},
	}
	for name, tf := range fns {
		fnVal := tsVal.Elem().FieldByName(name)
		if !fnVal.IsValid() {
			continue
		}
		typ := reflect.FuncOf(tf.in, tf.out, false)
		if fnVal.Type() != typ {
			return fmt.Errorf("%s function should have signature: %v", name, typ)
		}
		fnVal.Set(reflect.MakeFunc(typ, tf.impl))
	}
	return nil
}
func (t *Tree) lookup(in []reflect.Value) []reflect.Value {
	val := in[0]
	if val.Type() != t.elemType {
		panic("lookup of wrong type")
	}
	n := t.root
	for n != nil {
		switch t.cmp(val, n.val) {
		case -1:
			n = n.c[0]
		case 0:
			return []reflect.Value{n.val, reflect.ValueOf(true)}
		case 1:
			n = n.c[1]
		}
	}
	return []reflect.Value{reflect.Zero(t.elemType), reflect.ValueOf(false)}
}
func (t *Tree) insert(in []reflect.Value) []reflect.Value {
	val := in[0]
	if val.Type() != t.elemType {
		panic("Inserting wrong type")
	}
	t.insert1(val, nil, &t.root)
	return nil
}
func (t *Tree) insert1(val reflect.Value, p *Node, qp **Node) bool {
	q := *qp
	if q == nil {
		t.size++
		*qp = &Node{val: val, p: p}
		return true
	}
	c := t.cmp(val, q.val)
	if c == 0 {
		q.val = val
		return false
	}
	a := (c + 1) / 2
	fix := t.insert1(val, q, &q.c[a])
	if fix {
		return insertFix(c, qp)
	}
	return false
}
func insertFix(c int8, t **Node) bool {
	s := *t
	if s.b == 0 {
		s.b = c
		return true
	}
	if s.b == -c {
		s.b = 0
		return false
	}
	if s.c[(c+1)/2].b == c {
		s = singlerot(c, s)
	} else {
		s = doublerot(c, s)
	}
	*t = s
	return false
}
func (t *Tree) delete(in []reflect.Value) []reflect.Value {
	val := in[0]
	if val.Type() != t.elemType {
		panic("Deleting wrong type")
	}
	t.delete1(val, &t.root)
	return nil
}
func (t *Tree) delete1(val reflect.Value, qp **Node) bool {
	q := *qp
	if q == nil {
		return false
	}
	c := t.cmp(val, q.val)
	if c == 0 {
		t.size--
		if q.c[1] == nil {
			if q.c[0] != nil {
				q.c[0].p = q.p
			}
			*qp = q.c[0]
			return true
		}
		fix := deleteMin(&q.c[1], &q.val)
		if fix {
			return deleteFix(-1, qp)
		}
		return false
	}
	a := (c + 1) / 2
	fix := t.delete1(val, &q.c[a])
	if fix {
		return deleteFix(-c, qp)
	}
	return false
}
func deleteMin(qp **Node, min *reflect.Value) bool {
	q := *qp
	if q.c[0] == nil {
		*min = q.val
		if q.c[1] != nil {
			q.c[1].p = q.p
		}
		*qp = q.c[1]
		return true
	}
	fix := deleteMin(&q.c[0], min)
	if fix {
		return deleteFix(1, qp)
	}
	return false
}
func deleteFix(c int8, t **Node) bool {
	s := *t
	if s.b == 0 {
		s.b = c
		return false
	}
	if s.b == -c {
		s.b = 0
		return true
	}
	a := (c + 1) / 2
	if s.c[a].b == 0 {
		s = rotate(c, s)
		s.b = -c
		*t = s
		return false
	}
	if s.c[a].b == c {
		s = singlerot(c, s)
	} else {
		s = doublerot(c, s)
	}
	*t = s
	return true
}
func singlerot(c int8, s *Node) *Node {
	s.b = 0
	s = rotate(c, s)
	s.b = 0
	return s
}
func doublerot(c int8, s *Node) *Node {
	a := (c + 1) / 2
	r := s.c[a]
	s.c[a] = rotate(-c, s.c[a])
	p := rotate(c, s)
	if r.p != p || s.p != p {
		panic("doublerot: bad parents")
	}
	switch {
	default:
		s.b = 0
		r.b = 0
	case p.b == c:
		s.b = -c
		r.b = 0
	case p.b == -c:
		s.b = 0
		r.b = c
	}
	p.b = 0
	return p
}
func rotate(c int8, s *Node) *Node {
	a := (c + 1) / 2
	r := s.c[a]
	s.c[a] = r.c[a^1]
	if s.c[a] != nil {
		s.c[a].p = s
	}
	r.c[a^1] = s
	r.p = s.p
	s.p = r
	return r
}
func (t *Tree) value(in []reflect.Value) []reflect.Value {
	n := in[0].Interface().(*Node)
	return []reflect.Value{n.val}
}
func (t *Tree) Size() int {
	return t.size
}
func (t *Tree) Root() *Node {
	return t.root
}
func (t *Tree) Min() *Node {
	return t.bottom(0)
}
func (t *Tree) Max() *Node {
	return t.bottom(1)
}
func (t *Tree) bottom(d int) *Node {
	n := t.root
	if n == nil {
		return nil
	}
	for c := n.c[d]; c != nil; c = n.c[d] {
		n = c
	}
	return n
}
func (n *Node) Prev() *Node {
	return n.walk1(0)
}