Adding upstream version 1.21.8.upstream/1.21.8

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

2 files changed, 1532 insertions, 0 deletions

diff --git a/src/cmd/compile/internal/abt/avlint32.go b/src/cmd/compile/internal/abt/avlint32.go
new file mode 100644
index 0000000..28c1642
--- /dev/null
+++ b/src/cmd/compile/internal/abt/avlint32.go
@@ -0,0 +1,832 @@
+// Copyright 2022 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package abt
+
+import (
+	"fmt"
+	"strconv"
+	"strings"
+)
+
+const (
+	LEAF_HEIGHT = 1
+	ZERO_HEIGHT = 0
+	NOT_KEY32   = int32(-0x80000000)
+)
+
+// T is the exported applicative balanced tree data type.
+// A T can be used as a value; updates to one copy of the value
+// do not change other copies.
+type T struct {
+	root *node32
+	size int
+}
+
+// node32 is the internal tree node data type
+type node32 struct {
+	// Standard conventions hold for left = smaller, right = larger
+	left, right *node32
+	data        interface{}
+	key         int32
+	height_     int8
+}
+
+func makeNode(key int32) *node32 {
+	return &node32{key: key, height_: LEAF_HEIGHT}
+}
+
+// IsEmpty returns true iff t is empty.
+func (t *T) IsEmpty() bool {
+	return t.root == nil
+}
+
+// IsSingle returns true iff t is a singleton (leaf).
+func (t *T) IsSingle() bool {
+	return t.root != nil && t.root.isLeaf()
+}
+
+// VisitInOrder applies f to the key and data pairs in t,
+// with keys ordered from smallest to largest.
+func (t *T) VisitInOrder(f func(int32, interface{})) {
+	if t.root == nil {
+		return
+	}
+	t.root.visitInOrder(f)
+}
+
+func (n *node32) nilOrData() interface{} {
+	if n == nil {
+		return nil
+	}
+	return n.data
+}
+
+func (n *node32) nilOrKeyAndData() (k int32, d interface{}) {
+	if n == nil {
+		k = NOT_KEY32
+		d = nil
+	} else {
+		k = n.key
+		d = n.data
+	}
+	return
+}
+
+func (n *node32) height() int8 {
+	if n == nil {
+		return 0
+	}
+	return n.height_
+}
+
+// Find returns the data associated with x in the tree, or
+// nil if x is not in the tree.
+func (t *T) Find(x int32) interface{} {
+	return t.root.find(x).nilOrData()
+}
+
+// Insert either adds x to the tree if x was not previously
+// a key in the tree, or updates the data for x in the tree if
+// x was already a key in the tree.  The previous data associated
+// with x is returned, and is nil if x was not previously a
+// key in the tree.
+func (t *T) Insert(x int32, data interface{}) interface{} {
+	if x == NOT_KEY32 {
+		panic("Cannot use sentinel value -0x80000000 as key")
+	}
+	n := t.root
+	var newroot *node32
+	var o *node32
+	if n == nil {
+		n = makeNode(x)
+		newroot = n
+	} else {
+		newroot, n, o = n.aInsert(x)
+	}
+	var r interface{}
+	if o != nil {
+		r = o.data
+	} else {
+		t.size++
+	}
+	n.data = data
+	t.root = newroot
+	return r
+}
+
+func (t *T) Copy() *T {
+	u := *t
+	return &u
+}
+
+func (t *T) Delete(x int32) interface{} {
+	n := t.root
+	if n == nil {
+		return nil
+	}
+	d, s := n.aDelete(x)
+	if d == nil {
+		return nil
+	}
+	t.root = s
+	t.size--
+	return d.data
+}
+
+func (t *T) DeleteMin() (int32, interface{}) {
+	n := t.root
+	if n == nil {
+		return NOT_KEY32, nil
+	}
+	d, s := n.aDeleteMin()
+	if d == nil {
+		return NOT_KEY32, nil
+	}
+	t.root = s
+	t.size--
+	return d.key, d.data
+}
+
+func (t *T) DeleteMax() (int32, interface{}) {
+	n := t.root
+	if n == nil {
+		return NOT_KEY32, nil
+	}
+	d, s := n.aDeleteMax()
+	if d == nil {
+		return NOT_KEY32, nil
+	}
+	t.root = s
+	t.size--
+	return d.key, d.data
+}
+
+func (t *T) Size() int {
+	return t.size
+}
+
+// Intersection returns the intersection of t and u, where the result
+// data for any common keys is given by f(t's data, u's data) -- f need
+// not be symmetric.  If f returns nil, then the key and data are not
+// added to the result.  If f itself is nil, then whatever value was
+// already present in the smaller set is used.
+func (t *T) Intersection(u *T, f func(x, y interface{}) interface{}) *T {
+	if t.Size() == 0 || u.Size() == 0 {
+		return &T{}
+	}
+
+	// For faster execution and less allocation, prefer t smaller, iterate over t.
+	if t.Size() <= u.Size() {
+		v := t.Copy()
+		for it := t.Iterator(); !it.Done(); {
+			k, d := it.Next()
+			e := u.Find(k)
+			if e == nil {
+				v.Delete(k)
+				continue
+			}
+			if f == nil {
+				continue
+			}
+			if c := f(d, e); c != d {
+				if c == nil {
+					v.Delete(k)
+				} else {
+					v.Insert(k, c)
+				}
+			}
+		}
+		return v
+	}
+	v := u.Copy()
+	for it := u.Iterator(); !it.Done(); {
+		k, e := it.Next()
+		d := t.Find(k)
+		if d == nil {
+			v.Delete(k)
+			continue
+		}
+		if f == nil {
+			continue
+		}
+		if c := f(d, e); c != d {
+			if c == nil {
+				v.Delete(k)
+			} else {
+				v.Insert(k, c)
+			}
+		}
+	}
+
+	return v
+}
+
+// Union returns the union of t and u, where the result data for any common keys
+// is given by f(t's data, u's data) -- f need not be symmetric.  If f returns nil,
+// then the key and data are not added to the result.  If f itself is nil, then
+// whatever value was already present in the larger set is used.
+func (t *T) Union(u *T, f func(x, y interface{}) interface{}) *T {
+	if t.Size() == 0 {
+		return u
+	}
+	if u.Size() == 0 {
+		return t
+	}
+
+	if t.Size() >= u.Size() {
+		v := t.Copy()
+		for it := u.Iterator(); !it.Done(); {
+			k, e := it.Next()
+			d := t.Find(k)
+			if d == nil {
+				v.Insert(k, e)
+				continue
+			}
+			if f == nil {
+				continue
+			}
+			if c := f(d, e); c != d {
+				if c == nil {
+					v.Delete(k)
+				} else {
+					v.Insert(k, c)
+				}
+			}
+		}
+		return v
+	}
+
+	v := u.Copy()
+	for it := t.Iterator(); !it.Done(); {
+		k, d := it.Next()
+		e := u.Find(k)
+		if e == nil {
+			v.Insert(k, d)
+			continue
+		}
+		if f == nil {
+			continue
+		}
+		if c := f(d, e); c != d {
+			if c == nil {
+				v.Delete(k)
+			} else {
+				v.Insert(k, c)
+			}
+		}
+	}
+	return v
+}
+
+// Difference returns the difference of t and u, subject to the result
+// of f applied to data corresponding to equal keys.  If f returns nil
+// (or if f is nil) then the key+data are excluded, as usual.  If f
+// returns not-nil, then that key+data pair is inserted. instead.
+func (t *T) Difference(u *T, f func(x, y interface{}) interface{}) *T {
+	if t.Size() == 0 {
+		return &T{}
+	}
+	if u.Size() == 0 {
+		return t
+	}
+	v := t.Copy()
+	for it := t.Iterator(); !it.Done(); {
+		k, d := it.Next()
+		e := u.Find(k)
+		if e != nil {
+			if f == nil {
+				v.Delete(k)
+				continue
+			}
+			c := f(d, e)
+			if c == nil {
+				v.Delete(k)
+				continue
+			}
+			if c != d {
+				v.Insert(k, c)
+			}
+		}
+	}
+	return v
+}
+
+func (t *T) Iterator() Iterator {
+	return Iterator{it: t.root.iterator()}
+}
+
+func (t *T) Equals(u *T) bool {
+	if t == u {
+		return true
+	}
+	if t.Size() != u.Size() {
+		return false
+	}
+	return t.root.equals(u.root)
+}
+
+func (t *T) String() string {
+	var b strings.Builder
+	first := true
+	for it := t.Iterator(); !it.Done(); {
+		k, v := it.Next()
+		if first {
+			first = false
+		} else {
+			b.WriteString("; ")
+		}
+		b.WriteString(strconv.FormatInt(int64(k), 10))
+		b.WriteString(":")
+		fmt.Fprint(&b, v)
+	}
+	return b.String()
+}
+
+func (t *node32) equals(u *node32) bool {
+	if t == u {
+		return true
+	}
+	it, iu := t.iterator(), u.iterator()
+	for !it.done() && !iu.done() {
+		nt := it.next()
+		nu := iu.next()
+		if nt == nu {
+			continue
+		}
+		if nt.key != nu.key {
+			return false
+		}
+		if nt.data != nu.data {
+			return false
+		}
+	}
+	return it.done() == iu.done()
+}
+
+func (t *T) Equiv(u *T, eqv func(x, y interface{}) bool) bool {
+	if t == u {
+		return true
+	}
+	if t.Size() != u.Size() {
+		return false
+	}
+	return t.root.equiv(u.root, eqv)
+}
+
+func (t *node32) equiv(u *node32, eqv func(x, y interface{}) bool) bool {
+	if t == u {
+		return true
+	}
+	it, iu := t.iterator(), u.iterator()
+	for !it.done() && !iu.done() {
+		nt := it.next()
+		nu := iu.next()
+		if nt == nu {
+			continue
+		}
+		if nt.key != nu.key {
+			return false
+		}
+		if !eqv(nt.data, nu.data) {
+			return false
+		}
+	}
+	return it.done() == iu.done()
+}
+
+type iterator struct {
+	parents []*node32
+}
+
+type Iterator struct {
+	it iterator
+}
+
+func (it *Iterator) Next() (int32, interface{}) {
+	x := it.it.next()
+	if x == nil {
+		return NOT_KEY32, nil
+	}
+	return x.key, x.data
+}
+
+func (it *Iterator) Done() bool {
+	return len(it.it.parents) == 0
+}
+
+func (t *node32) iterator() iterator {
+	if t == nil {
+		return iterator{}
+	}
+	it := iterator{parents: make([]*node32, 0, int(t.height()))}
+	it.leftmost(t)
+	return it
+}
+
+func (it *iterator) leftmost(t *node32) {
+	for t != nil {
+		it.parents = append(it.parents, t)
+		t = t.left
+	}
+}
+
+func (it *iterator) done() bool {
+	return len(it.parents) == 0
+}
+
+func (it *iterator) next() *node32 {
+	l := len(it.parents)
+	if l == 0 {
+		return nil
+	}
+	x := it.parents[l-1] // return value
+	if x.right != nil {
+		it.leftmost(x.right)
+		return x
+	}
+	// discard visited top of parents
+	l--
+	it.parents = it.parents[:l]
+	y := x // y is known visited/returned
+	for l > 0 && y == it.parents[l-1].right {
+		y = it.parents[l-1]
+		l--
+		it.parents = it.parents[:l]
+	}
+
+	return x
+}
+
+// Min returns the minimum element of t.
+// If t is empty, then (NOT_KEY32, nil) is returned.
+func (t *T) Min() (k int32, d interface{}) {
+	return t.root.min().nilOrKeyAndData()
+}
+
+// Max returns the maximum element of t.
+// If t is empty, then (NOT_KEY32, nil) is returned.
+func (t *T) Max() (k int32, d interface{}) {
+	return t.root.max().nilOrKeyAndData()
+}
+
+// Glb returns the greatest-lower-bound-exclusive of x and the associated
+// data.  If x has no glb in the tree, then (NOT_KEY32, nil) is returned.
+func (t *T) Glb(x int32) (k int32, d interface{}) {
+	return t.root.glb(x, false).nilOrKeyAndData()
+}
+
+// GlbEq returns the greatest-lower-bound-inclusive of x and the associated
+// data.  If x has no glbEQ in the tree, then (NOT_KEY32, nil) is returned.
+func (t *T) GlbEq(x int32) (k int32, d interface{}) {
+	return t.root.glb(x, true).nilOrKeyAndData()
+}
+
+// Lub returns the least-upper-bound-exclusive of x and the associated
+// data.  If x has no lub in the tree, then (NOT_KEY32, nil) is returned.
+func (t *T) Lub(x int32) (k int32, d interface{}) {
+	return t.root.lub(x, false).nilOrKeyAndData()
+}
+
+// LubEq returns the least-upper-bound-inclusive of x and the associated
+// data.  If x has no lubEq in the tree, then (NOT_KEY32, nil) is returned.
+func (t *T) LubEq(x int32) (k int32, d interface{}) {
+	return t.root.lub(x, true).nilOrKeyAndData()
+}
+
+func (t *node32) isLeaf() bool {
+	return t.left == nil && t.right == nil && t.height_ == LEAF_HEIGHT
+}
+
+func (t *node32) visitInOrder(f func(int32, interface{})) {
+	if t.left != nil {
+		t.left.visitInOrder(f)
+	}
+	f(t.key, t.data)
+	if t.right != nil {
+		t.right.visitInOrder(f)
+	}
+}
+
+func (t *node32) find(key int32) *node32 {
+	for t != nil {
+		if key < t.key {
+			t = t.left
+		} else if key > t.key {
+			t = t.right
+		} else {
+			return t
+		}
+	}
+	return nil
+}
+
+func (t *node32) min() *node32 {
+	if t == nil {
+		return t
+	}
+	for t.left != nil {
+		t = t.left
+	}
+	return t
+}
+
+func (t *node32) max() *node32 {
+	if t == nil {
+		return t
+	}
+	for t.right != nil {
+		t = t.right
+	}
+	return t
+}
+
+func (t *node32) glb(key int32, allow_eq bool) *node32 {
+	var best *node32 = nil
+	for t != nil {
+		if key <= t.key {
+			if allow_eq && key == t.key {
+				return t
+			}
+			// t is too big, glb is to left.
+			t = t.left
+		} else {
+			// t is a lower bound, record it and seek a better one.
+			best = t
+			t = t.right
+		}
+	}
+	return best
+}
+
+func (t *node32) lub(key int32, allow_eq bool) *node32 {
+	var best *node32 = nil
+	for t != nil {
+		if key >= t.key {
+			if allow_eq && key == t.key {
+				return t
+			}
+			// t is too small, lub is to right.
+			t = t.right
+		} else {
+			// t is an upper bound, record it and seek a better one.
+			best = t
+			t = t.left
+		}
+	}
+	return best
+}
+
+func (t *node32) aInsert(x int32) (newroot, newnode, oldnode *node32) {
+	// oldnode default of nil is good, others should be assigned.
+	if x == t.key {
+		oldnode = t
+		newt := *t
+		newnode = &newt
+		newroot = newnode
+		return
+	}
+	if x < t.key {
+		if t.left == nil {
+			t = t.copy()
+			n := makeNode(x)
+			t.left = n
+			newnode = n
+			newroot = t
+			t.height_ = 2 // was balanced w/ 0, sibling is height 0 or 1
+			return
+		}
+		var new_l *node32
+		new_l, newnode, oldnode = t.left.aInsert(x)
+		t = t.copy()
+		t.left = new_l
+		if new_l.height() > 1+t.right.height() {
+			newroot = t.aLeftIsHigh(newnode)
+		} else {
+			t.height_ = 1 + max(t.left.height(), t.right.height())
+			newroot = t
+		}
+	} else { // x > t.key
+		if t.right == nil {
+			t = t.copy()
+			n := makeNode(x)
+			t.right = n
+			newnode = n
+			newroot = t
+			t.height_ = 2 // was balanced w/ 0, sibling is height 0 or 1
+			return
+		}
+		var new_r *node32
+		new_r, newnode, oldnode = t.right.aInsert(x)
+		t = t.copy()
+		t.right = new_r
+		if new_r.height() > 1+t.left.height() {
+			newroot = t.aRightIsHigh(newnode)
+		} else {
+			t.height_ = 1 + max(t.left.height(), t.right.height())
+			newroot = t
+		}
+	}
+	return
+}
+
+func (t *node32) aDelete(key int32) (deleted, newSubTree *node32) {
+	if t == nil {
+		return nil, nil
+	}
+
+	if key < t.key {
+		oh := t.left.height()
+		d, tleft := t.left.aDelete(key)
+		if tleft == t.left {
+			return d, t
+		}
+		return d, t.copy().aRebalanceAfterLeftDeletion(oh, tleft)
+	} else if key > t.key {
+		oh := t.right.height()
+		d, tright := t.right.aDelete(key)
+		if tright == t.right {
+			return d, t
+		}
+		return d, t.copy().aRebalanceAfterRightDeletion(oh, tright)
+	}
+
+	if t.height() == LEAF_HEIGHT {
+		return t, nil
+	}
+
+	// Interior delete by removing left.Max or right.Min,
+	// then swapping contents
+	if t.left.height() > t.right.height() {
+		oh := t.left.height()
+		d, tleft := t.left.aDeleteMax()
+		r := t
+		t = t.copy()
+		t.data, t.key = d.data, d.key
+		return r, t.aRebalanceAfterLeftDeletion(oh, tleft)
+	}
+
+	oh := t.right.height()
+	d, tright := t.right.aDeleteMin()
+	r := t
+	t = t.copy()
+	t.data, t.key = d.data, d.key
+	return r, t.aRebalanceAfterRightDeletion(oh, tright)
+}
+
+func (t *node32) aDeleteMin() (deleted, newSubTree *node32) {
+	if t == nil {
+		return nil, nil
+	}
+	if t.left == nil { // leaf or left-most
+		return t, t.right
+	}
+	oh := t.left.height()
+	d, tleft := t.left.aDeleteMin()
+	if tleft == t.left {
+		return d, t
+	}
+	return d, t.copy().aRebalanceAfterLeftDeletion(oh, tleft)
+}
+
+func (t *node32) aDeleteMax() (deleted, newSubTree *node32) {
+	if t == nil {
+		return nil, nil
+	}
+
+	if t.right == nil { // leaf or right-most
+		return t, t.left
+	}
+
+	oh := t.right.height()
+	d, tright := t.right.aDeleteMax()
+	if tright == t.right {
+		return d, t
+	}
+	return d, t.copy().aRebalanceAfterRightDeletion(oh, tright)
+}
+
+func (t *node32) aRebalanceAfterLeftDeletion(oldLeftHeight int8, tleft *node32) *node32 {
+	t.left = tleft
+
+	if oldLeftHeight == tleft.height() || oldLeftHeight == t.right.height() {
+		// this node is still balanced and its height is unchanged
+		return t
+	}
+
+	if oldLeftHeight > t.right.height() {
+		// left was larger
+		t.height_--
+		return t
+	}
+
+	// left height fell by 1 and it was already less than right height
+	t.right = t.right.copy()
+	return t.aRightIsHigh(nil)
+}
+
+func (t *node32) aRebalanceAfterRightDeletion(oldRightHeight int8, tright *node32) *node32 {
+	t.right = tright
+
+	if oldRightHeight == tright.height() || oldRightHeight == t.left.height() {
+		// this node is still balanced and its height is unchanged
+		return t
+	}
+
+	if oldRightHeight > t.left.height() {
+		// left was larger
+		t.height_--
+		return t
+	}
+
+	// right height fell by 1 and it was already less than left height
+	t.left = t.left.copy()
+	return t.aLeftIsHigh(nil)
+}
+
+// aRightIsHigh does rotations necessary to fix a high right child
+// assume that t and t.right are already fresh copies.
+func (t *node32) aRightIsHigh(newnode *node32) *node32 {
+	right := t.right
+	if right.right.height() < right.left.height() {
+		// double rotation
+		if newnode != right.left {
+			right.left = right.left.copy()
+		}
+		t.right = right.leftToRoot()
+	}
+	t = t.rightToRoot()
+	return t
+}
+
+// aLeftIsHigh does rotations necessary to fix a high left child
+// assume that t and t.left are already fresh copies.
+func (t *node32) aLeftIsHigh(newnode *node32) *node32 {
+	left := t.left
+	if left.left.height() < left.right.height() {
+		// double rotation
+		if newnode != left.right {
+			left.right = left.right.copy()
+		}
+		t.left = left.rightToRoot()
+	}
+	t = t.leftToRoot()
+	return t
+}
+
+// rightToRoot does that rotation, modifying t and t.right in the process.
+func (t *node32) rightToRoot() *node32 {
+	//    this
+	// left  right
+	//      rl   rr
+	//
+	// becomes
+	//
+	//       right
+	//    this   rr
+	// left  rl
+	//
+	right := t.right
+	rl := right.left
+	right.left = t
+	// parent's child ptr fixed in caller
+	t.right = rl
+	t.height_ = 1 + max(rl.height(), t.left.height())
+	right.height_ = 1 + max(t.height(), right.right.height())
+	return right
+}
+
+// leftToRoot does that rotation, modifying t and t.left in the process.
+func (t *node32) leftToRoot() *node32 {
+	//     this
+	//  left  right
+	// ll  lr
+	//
+	// becomes
+	//
+	//    left
+	//   ll  this
+	//      lr  right
+	//
+	left := t.left
+	lr := left.right
+	left.right = t
+	// parent's child ptr fixed in caller
+	t.left = lr
+	t.height_ = 1 + max(lr.height(), t.right.height())
+	left.height_ = 1 + max(t.height(), left.left.height())
+	return left
+}
+
+func max(a, b int8) int8 {
+	if a > b {
+		return a
+	}
+	return b
+}
+
+func (t *node32) copy() *node32 {
+	u := *t
+	return &u
+}
diff --git a/src/cmd/compile/internal/abt/avlint32_test.go b/src/cmd/compile/internal/abt/avlint32_test.go
new file mode 100644
index 0000000..7fa9ed4
--- /dev/null
+++ b/src/cmd/compile/internal/abt/avlint32_test.go
@@ -0,0 +1,700 @@
+// Copyright 2022 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package abt
+
+import (
+	"fmt"
+	"strconv"
+	"testing"
+)
+
+func makeTree(te *testing.T, x []int32, check bool) (t *T, k int, min, max int32) {
+	t = &T{}
+	k = 0
+	min = int32(0x7fffffff)
+	max = int32(-0x80000000)
+	history := []*T{}
+
+	for _, d := range x {
+		d = d + d // double everything for Glb/Lub testing.
+
+		if check {
+			history = append(history, t.Copy())
+		}
+
+		t.Insert(d, stringer(fmt.Sprintf("%v", d)))
+
+		k++
+		if d < min {
+			min = d
+		}
+		if d > max {
+			max = d
+		}
+
+		if !check {
+			continue
+		}
+
+		for j, old := range history {
+			s, i := old.wellFormed()
+			if s != "" {
+				te.Errorf("Old tree consistency problem %v at k=%d, j=%d, old=\n%v, t=\n%v", s, k, j, old.DebugString(), t.DebugString())
+				return
+			}
+			if i != j {
+				te.Errorf("Wrong tree size %v, expected %v for old %v", i, j, old.DebugString())
+			}
+		}
+		s, i := t.wellFormed()
+		if s != "" {
+			te.Errorf("Tree consistency problem at %v", s)
+			return
+		}
+		if i != k {
+			te.Errorf("Wrong tree size %v, expected %v for %v", i, k, t.DebugString())
+			return
+		}
+		if t.Size() != k {
+			te.Errorf("Wrong t.Size() %v, expected %v for %v", t.Size(), k, t.DebugString())
+			return
+		}
+	}
+	return
+}
+
+func applicInsert(te *testing.T, x []int32) {
+	makeTree(te, x, true)
+}
+
+func applicFind(te *testing.T, x []int32) {
+	t, _, _, _ := makeTree(te, x, false)
+
+	for _, d := range x {
+		d = d + d // double everything for Glb/Lub testing.
+		s := fmt.Sprintf("%v", d)
+		f := t.Find(d)
+
+		// data
+		if s != fmt.Sprint(f) {
+			te.Errorf("s(%v) != f(%v)", s, f)
+		}
+	}
+}
+
+func applicBounds(te *testing.T, x []int32) {
+	t, _, min, max := makeTree(te, x, false)
+	for _, d := range x {
+		d = d + d // double everything for Glb/Lub testing.
+		s := fmt.Sprintf("%v", d)
+
+		kg, g := t.Glb(d + 1)
+		kge, ge := t.GlbEq(d)
+		kl, l := t.Lub(d - 1)
+		kle, le := t.LubEq(d)
+
+		// keys
+		if d != kg {
+			te.Errorf("d(%v) != kg(%v)", d, kg)
+		}
+		if d != kl {
+			te.Errorf("d(%v) != kl(%v)", d, kl)
+		}
+		if d != kge {
+			te.Errorf("d(%v) != kge(%v)", d, kge)
+		}
+		if d != kle {
+			te.Errorf("d(%v) != kle(%v)", d, kle)
+		}
+		// data
+		if s != fmt.Sprint(g) {
+			te.Errorf("s(%v) != g(%v)", s, g)
+		}
+		if s != fmt.Sprint(l) {
+			te.Errorf("s(%v) != l(%v)", s, l)
+		}
+		if s != fmt.Sprint(ge) {
+			te.Errorf("s(%v) != ge(%v)", s, ge)
+		}
+		if s != fmt.Sprint(le) {
+			te.Errorf("s(%v) != le(%v)", s, le)
+		}
+	}
+
+	for _, d := range x {
+		d = d + d // double everything for Glb/Lub testing.
+		s := fmt.Sprintf("%v", d)
+		kge, ge := t.GlbEq(d + 1)
+		kle, le := t.LubEq(d - 1)
+		if d != kge {
+			te.Errorf("d(%v) != kge(%v)", d, kge)
+		}
+		if d != kle {
+			te.Errorf("d(%v) != kle(%v)", d, kle)
+		}
+		if s != fmt.Sprint(ge) {
+			te.Errorf("s(%v) != ge(%v)", s, ge)
+		}
+		if s != fmt.Sprint(le) {
+			te.Errorf("s(%v) != le(%v)", s, le)
+		}
+	}
+
+	kg, g := t.Glb(min)
+	kge, ge := t.GlbEq(min - 1)
+	kl, l := t.Lub(max)
+	kle, le := t.LubEq(max + 1)
+	fmin := t.Find(min - 1)
+	fmax := t.Find(max + 1)
+
+	if kg != NOT_KEY32 || kge != NOT_KEY32 || kl != NOT_KEY32 || kle != NOT_KEY32 {
+		te.Errorf("Got non-error-key for missing query")
+	}
+
+	if g != nil || ge != nil || l != nil || le != nil || fmin != nil || fmax != nil {
+		te.Errorf("Got non-error-data for missing query")
+	}
+}
+
+func applicDeleteMin(te *testing.T, x []int32) {
+	t, _, _, _ := makeTree(te, x, false)
+	_, size := t.wellFormed()
+	history := []*T{}
+	for !t.IsEmpty() {
+		k, _ := t.Min()
+		history = append(history, t.Copy())
+		kd, _ := t.DeleteMin()
+		if kd != k {
+			te.Errorf("Deleted minimum key %v not equal to minimum %v", kd, k)
+		}
+		for j, old := range history {
+			s, i := old.wellFormed()
+			if s != "" {
+				te.Errorf("Tree consistency problem %s at old after DeleteMin, old=\n%stree=\n%v", s, old.DebugString(), t.DebugString())
+				return
+			}
+			if i != len(x)-j {
+				te.Errorf("Wrong old tree size %v, expected %v after DeleteMin, old=\n%vtree\n%v", i, len(x)-j, old.DebugString(), t.DebugString())
+				return
+			}
+		}
+		size--
+		s, i := t.wellFormed()
+		if s != "" {
+			te.Errorf("Tree consistency problem at %v after DeleteMin, tree=\n%v", s, t.DebugString())
+			return
+		}
+		if i != size {
+			te.Errorf("Wrong tree size %v, expected %v after DeleteMin", i, size)
+			return
+		}
+		if t.Size() != size {
+			te.Errorf("Wrong t.Size() %v, expected %v for %v", t.Size(), i, t.DebugString())
+			return
+		}
+	}
+}
+
+func applicDeleteMax(te *testing.T, x []int32) {
+	t, _, _, _ := makeTree(te, x, false)
+	_, size := t.wellFormed()
+	history := []*T{}
+
+	for !t.IsEmpty() {
+		k, _ := t.Max()
+		history = append(history, t.Copy())
+		kd, _ := t.DeleteMax()
+		if kd != k {
+			te.Errorf("Deleted maximum key %v not equal to maximum %v", kd, k)
+		}
+
+		for j, old := range history {
+			s, i := old.wellFormed()
+			if s != "" {
+				te.Errorf("Tree consistency problem %s at old after DeleteMin, old=\n%stree=\n%v", s, old.DebugString(), t.DebugString())
+				return
+			}
+			if i != len(x)-j {
+				te.Errorf("Wrong old tree size %v, expected %v after DeleteMin, old=\n%vtree\n%v", i, len(x)-j, old.DebugString(), t.DebugString())
+				return
+			}
+		}
+
+		size--
+		s, i := t.wellFormed()
+		if s != "" {
+			te.Errorf("Tree consistency problem at %v after DeleteMax, tree=\n%v", s, t.DebugString())
+			return
+		}
+		if i != size {
+			te.Errorf("Wrong tree size %v, expected %v after DeleteMax", i, size)
+			return
+		}
+		if t.Size() != size {
+			te.Errorf("Wrong t.Size() %v, expected %v for %v", t.Size(), i, t.DebugString())
+			return
+		}
+	}
+}
+
+func applicDelete(te *testing.T, x []int32) {
+	t, _, _, _ := makeTree(te, x, false)
+	_, size := t.wellFormed()
+	history := []*T{}
+
+	missing := t.Delete(11)
+	if missing != nil {
+		te.Errorf("Returned a value when there should have been none, %v", missing)
+		return
+	}
+
+	s, i := t.wellFormed()
+	if s != "" {
+		te.Errorf("Tree consistency problem at %v after delete of missing value, tree=\n%v", s, t.DebugString())
+		return
+	}
+	if size != i {
+		te.Errorf("Delete of missing data should not change tree size, expected %d, got %d", size, i)
+		return
+	}
+
+	for _, d := range x {
+		d += d // double
+		vWant := fmt.Sprintf("%v", d)
+		history = append(history, t.Copy())
+		v := t.Delete(d)
+
+		for j, old := range history {
+			s, i := old.wellFormed()
+			if s != "" {
+				te.Errorf("Tree consistency problem %s at old after DeleteMin, old=\n%stree=\n%v", s, old.DebugString(), t.DebugString())
+				return
+			}
+			if i != len(x)-j {
+				te.Errorf("Wrong old tree size %v, expected %v after DeleteMin, old=\n%vtree\n%v", i, len(x)-j, old.DebugString(), t.DebugString())
+				return
+			}
+		}
+
+		if v.(*sstring).s != vWant {
+			te.Errorf("Deleted %v expected %v but got %v", d, vWant, v)
+			return
+		}
+		size--
+		s, i := t.wellFormed()
+		if s != "" {
+			te.Errorf("Tree consistency problem at %v after Delete %d, tree=\n%v", s, d, t.DebugString())
+			return
+		}
+		if i != size {
+			te.Errorf("Wrong tree size %v, expected %v after Delete", i, size)
+			return
+		}
+		if t.Size() != size {
+			te.Errorf("Wrong t.Size() %v, expected %v for %v", t.Size(), i, t.DebugString())
+			return
+		}
+	}
+
+}
+
+func applicIterator(te *testing.T, x []int32) {
+	t, _, _, _ := makeTree(te, x, false)
+	it := t.Iterator()
+	for !it.Done() {
+		k0, d0 := it.Next()
+		k1, d1 := t.DeleteMin()
+		if k0 != k1 || d0 != d1 {
+			te.Errorf("Iterator and deleteMin mismatch, k0, k1, d0, d1 = %v, %v, %v, %v", k0, k1, d0, d1)
+			return
+		}
+	}
+	if t.Size() != 0 {
+		te.Errorf("Iterator ended early, remaining tree = \n%s", t.DebugString())
+		return
+	}
+}
+
+func equiv(a, b interface{}) bool {
+	sa, sb := a.(*sstring), b.(*sstring)
+	return *sa == *sb
+}
+
+func applicEquals(te *testing.T, x, y []int32) {
+	t, _, _, _ := makeTree(te, x, false)
+	u, _, _, _ := makeTree(te, y, false)
+	if !t.Equiv(t, equiv) {
+		te.Errorf("Equiv failure, t == t, =\n%v", t.DebugString())
+		return
+	}
+	if !t.Equiv(t.Copy(), equiv) {
+		te.Errorf("Equiv failure, t == t.Copy(), =\n%v", t.DebugString())
+		return
+	}
+	if !t.Equiv(u, equiv) {
+		te.Errorf("Equiv failure, t == u, =\n%v", t.DebugString())
+		return
+	}
+	v := t.Copy()
+
+	v.DeleteMax()
+	if t.Equiv(v, equiv) {
+		te.Errorf("!Equiv failure, t != v, =\n%v\nand%v\n", t.DebugString(), v.DebugString())
+		return
+	}
+
+	if v.Equiv(u, equiv) {
+		te.Errorf("!Equiv failure, v != u, =\n%v\nand%v\n", v.DebugString(), u.DebugString())
+		return
+	}
+
+}
+
+func tree(x []int32) *T {
+	t := &T{}
+	for _, d := range x {
+		t.Insert(d, stringer(fmt.Sprintf("%v", d)))
+	}
+	return t
+}
+
+func treePlus1(x []int32) *T {
+	t := &T{}
+	for _, d := range x {
+		t.Insert(d, stringer(fmt.Sprintf("%v", d+1)))
+	}
+	return t
+}
+func TestApplicInsert(t *testing.T) {
+	applicInsert(t, []int32{24, 22, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25})
+	applicInsert(t, []int32{1, 2, 3, 4})
+	applicInsert(t, []int32{1, 2, 3, 4, 5, 6, 7, 8, 9})
+	applicInsert(t, []int32{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25})
+	applicInsert(t, []int32{25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1})
+	applicInsert(t, []int32{25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1})
+	applicInsert(t, []int32{1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24})
+	applicInsert(t, []int32{1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 24, 22, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2})
+}
+
+func TestApplicFind(t *testing.T) {
+	applicFind(t, []int32{24, 22, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25})
+	applicFind(t, []int32{1, 2, 3, 4})
+	applicFind(t, []int32{1, 2, 3, 4, 5, 6, 7, 8, 9})
+	applicFind(t, []int32{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25})
+	applicFind(t, []int32{25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1})
+	applicFind(t, []int32{25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1})
+	applicFind(t, []int32{1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24})
+	applicFind(t, []int32{1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 24, 22, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2})
+}
+
+func TestBounds(t *testing.T) {
+	applicBounds(t, []int32{24, 22, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25})
+	applicBounds(t, []int32{1, 2, 3, 4})
+	applicBounds(t, []int32{1, 2, 3, 4, 5, 6, 7, 8, 9})
+	applicBounds(t, []int32{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25})
+	applicBounds(t, []int32{25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1})
+	applicBounds(t, []int32{25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1})
+	applicBounds(t, []int32{1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24})
+	applicBounds(t, []int32{1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 24, 22, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2})
+}
+func TestDeleteMin(t *testing.T) {
+	applicDeleteMin(t, []int32{1, 2, 3, 4})
+	applicDeleteMin(t, []int32{24, 22, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25})
+	applicDeleteMin(t, []int32{1, 2, 3, 4, 5, 6, 7, 8, 9})
+	applicDeleteMin(t, []int32{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25})
+	applicDeleteMin(t, []int32{25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1})
+	applicDeleteMin(t, []int32{25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1})
+	applicDeleteMin(t, []int32{1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24})
+	applicDeleteMin(t, []int32{1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 24, 22, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2})
+}
+func TestDeleteMax(t *testing.T) {
+	applicDeleteMax(t, []int32{24, 22, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25})
+	applicDeleteMax(t, []int32{1, 2, 3, 4})
+	applicDeleteMax(t, []int32{1, 2, 3, 4, 5, 6, 7, 8, 9})
+	applicDeleteMax(t, []int32{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25})
+	applicDeleteMax(t, []int32{25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1})
+	applicDeleteMax(t, []int32{25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1})
+	applicDeleteMax(t, []int32{1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24})
+	applicDeleteMax(t, []int32{1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 24, 22, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2})
+}
+func TestDelete(t *testing.T) {
+	applicDelete(t, []int32{24, 22, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25})
+	applicDelete(t, []int32{1, 2, 3, 4})
+	applicDelete(t, []int32{1, 2, 3, 4, 5, 6, 7, 8, 9})
+	applicDelete(t, []int32{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25})
+	applicDelete(t, []int32{25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1})
+	applicDelete(t, []int32{25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1})
+	applicDelete(t, []int32{1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24})
+	applicDelete(t, []int32{1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 24, 22, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2})
+}
+func TestIterator(t *testing.T) {
+	applicIterator(t, []int32{1, 2, 3, 4})
+	applicIterator(t, []int32{1, 2, 3, 4, 5, 6, 7, 8, 9})
+	applicIterator(t, []int32{24, 22, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25})
+	applicIterator(t, []int32{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25})
+	applicIterator(t, []int32{25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1})
+	applicIterator(t, []int32{25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1})
+	applicIterator(t, []int32{1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24})
+	applicIterator(t, []int32{1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 24, 22, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2})
+}
+func TestEquals(t *testing.T) {
+	applicEquals(t, []int32{1, 2, 3, 4}, []int32{4, 3, 2, 1})
+
+	applicEquals(t, []int32{24, 22, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25},
+		[]int32{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25})
+	applicEquals(t, []int32{25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1},
+		[]int32{25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1})
+	applicEquals(t, []int32{1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24},
+		[]int32{1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 24, 22, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2})
+}
+
+func first(x, y interface{}) interface{} {
+	return x
+}
+func second(x, y interface{}) interface{} {
+	return y
+}
+func alwaysNil(x, y interface{}) interface{} {
+	return nil
+}
+func smaller(x, y interface{}) interface{} {
+	xi, _ := strconv.Atoi(fmt.Sprint(x))
+	yi, _ := strconv.Atoi(fmt.Sprint(y))
+	if xi < yi {
+		return x
+	}
+	return y
+}
+func assert(t *testing.T, expected, got *T, what string) {
+	s, _ := got.wellFormed()
+	if s != "" {
+		t.Errorf("Tree consistency problem %v for 'got' in assert for %s, tree=\n%v", s, what, got.DebugString())
+		return
+	}
+
+	if !expected.Equiv(got, equiv) {
+		t.Errorf("%s fail, expected\n%vgot\n%v\n", what, expected.DebugString(), got.DebugString())
+	}
+}
+
+func TestSetOps(t *testing.T) {
+	A := tree([]int32{1, 2, 3, 4})
+	B := tree([]int32{3, 4, 5, 6, 7})
+
+	AIB := tree([]int32{3, 4})
+	ADB := tree([]int32{1, 2})
+	BDA := tree([]int32{5, 6, 7})
+	AUB := tree([]int32{1, 2, 3, 4, 5, 6, 7})
+	AXB := tree([]int32{1, 2, 5, 6, 7})
+
+	aib1 := A.Intersection(B, first)
+	assert(t, AIB, aib1, "aib1")
+	if A.Find(3) != aib1.Find(3) {
+		t.Errorf("Failed aliasing/reuse check, A/aib1")
+	}
+	aib2 := A.Intersection(B, second)
+	assert(t, AIB, aib2, "aib2")
+	if B.Find(3) != aib2.Find(3) {
+		t.Errorf("Failed aliasing/reuse check, B/aib2")
+	}
+	aib3 := B.Intersection(A, first)
+	assert(t, AIB, aib3, "aib3")
+	if A.Find(3) != aib3.Find(3) {
+		// A is smaller, intersection favors reuse from smaller when function is "first"
+		t.Errorf("Failed aliasing/reuse check, A/aib3")
+	}
+	aib4 := B.Intersection(A, second)
+	assert(t, AIB, aib4, "aib4")
+	if A.Find(3) != aib4.Find(3) {
+		t.Errorf("Failed aliasing/reuse check, A/aib4")
+	}
+
+	aub1 := A.Union(B, first)
+	assert(t, AUB, aub1, "aub1")
+	if B.Find(3) != aub1.Find(3) {
+		// B is larger, union favors reuse from larger when function is "first"
+		t.Errorf("Failed aliasing/reuse check, A/aub1")
+	}
+	aub2 := A.Union(B, second)
+	assert(t, AUB, aub2, "aub2")
+	if B.Find(3) != aub2.Find(3) {
+		t.Errorf("Failed aliasing/reuse check, B/aub2")
+	}
+	aub3 := B.Union(A, first)
+	assert(t, AUB, aub3, "aub3")
+	if B.Find(3) != aub3.Find(3) {
+		t.Errorf("Failed aliasing/reuse check, B/aub3")
+	}
+	aub4 := B.Union(A, second)
+	assert(t, AUB, aub4, "aub4")
+	if A.Find(3) != aub4.Find(3) {
+		t.Errorf("Failed aliasing/reuse check, A/aub4")
+	}
+
+	axb1 := A.Union(B, alwaysNil)
+	assert(t, AXB, axb1, "axb1")
+	axb2 := B.Union(A, alwaysNil)
+	assert(t, AXB, axb2, "axb2")
+
+	adb := A.Difference(B, alwaysNil)
+	assert(t, ADB, adb, "adb")
+	bda := B.Difference(A, nil)
+	assert(t, BDA, bda, "bda")
+
+	Ap1 := treePlus1([]int32{1, 2, 3, 4})
+
+	ada1_1 := A.Difference(Ap1, smaller)
+	assert(t, A, ada1_1, "ada1_1")
+	ada1_2 := Ap1.Difference(A, smaller)
+	assert(t, A, ada1_2, "ada1_2")
+
+}
+
+type sstring struct {
+	s string
+}
+
+func (s *sstring) String() string {
+	return s.s
+}
+
+func stringer(s string) interface{} {
+	return &sstring{s}
+}
+
+// wellFormed ensures that a red-black tree meets
+// all of its invariants and returns a string identifying
+// the first problem encountered. If there is no problem
+// then the returned string is empty. The size is also
+// returned to allow comparison of calculated tree size
+// with expected.
+func (t *T) wellFormed() (s string, i int) {
+	if t.root == nil {
+		s = ""
+		i = 0
+		return
+	}
+	return t.root.wellFormedSubtree(nil, -0x80000000, 0x7fffffff)
+}
+
+// wellFormedSubtree ensures that a red-black subtree meets
+// all of its invariants and returns a string identifying
+// the first problem encountered. If there is no problem
+// then the returned string is empty. The size is also
+// returned to allow comparison of calculated tree size
+// with expected.
+func (t *node32) wellFormedSubtree(parent *node32, keyMin, keyMax int32) (s string, i int) {
+	i = -1 // initialize to a failing value
+	s = "" // s is the reason for failure; empty means okay.
+
+	if keyMin >= t.key {
+		s = " min >= t.key"
+		return
+	}
+
+	if keyMax <= t.key {
+		s = " max <= t.key"
+		return
+	}
+
+	l := t.left
+	r := t.right
+
+	lh := l.height()
+	rh := r.height()
+	mh := max(lh, rh)
+	th := t.height()
+	dh := lh - rh
+	if dh < 0 {
+		dh = -dh
+	}
+	if dh > 1 {
+		s = fmt.Sprintf(" dh > 1, t=%d", t.key)
+		return
+	}
+
+	if l == nil && r == nil {
+		if th != LEAF_HEIGHT {
+			s = " leaf height wrong"
+			return
+		}
+	}
+
+	if th != mh+1 {
+		s = " th != mh + 1"
+		return
+	}
+
+	if l != nil {
+		if th <= lh {
+			s = " t.height <= l.height"
+		} else if th > 2+lh {
+			s = " t.height > 2+l.height"
+		} else if t.key <= l.key {
+			s = " t.key <= l.key"
+		}
+		if s != "" {
+			return
+		}
+
+	}
+
+	if r != nil {
+		if th <= rh {
+			s = " t.height <= r.height"
+		} else if th > 2+rh {
+			s = " t.height > 2+r.height"
+		} else if t.key >= r.key {
+			s = " t.key >= r.key"
+		}
+		if s != "" {
+			return
+		}
+	}
+
+	ii := 1
+	if l != nil {
+		res, il := l.wellFormedSubtree(t, keyMin, t.key)
+		if res != "" {
+			s = ".L" + res
+			return
+		}
+		ii += il
+	}
+	if r != nil {
+		res, ir := r.wellFormedSubtree(t, t.key, keyMax)
+		if res != "" {
+			s = ".R" + res
+			return
+		}
+		ii += ir
+	}
+	i = ii
+	return
+}
+
+func (t *T) DebugString() string {
+	if t.root == nil {
+		return ""
+	}
+	return t.root.DebugString(0)
+}
+
+// DebugString prints the tree with nested information
+// to allow an eyeball check on the tree balance.
+func (t *node32) DebugString(indent int) string {
+	s := ""
+	if t.left != nil {
+		s = s + t.left.DebugString(indent+1)
+	}
+	for i := 0; i < indent; i++ {
+		s = s + "    "
+	}
+	s = s + fmt.Sprintf("%v=%v:%d\n", t.key, t.data, t.height_)
+	if t.right != nil {
+		s = s + t.right.DebugString(indent+1)
+	}
+	return s
+}