;;; Regression testing for red-black trees.

:
:;; `rbtree_join' could look for a sibling node's colour without checking
:;; that it actually existed.

= (_ *0 (_ 3 _)) D
( 6k ~ D

:
:;; In `rbtree_split' with an empty path, the root of the initial tree
:;; wasn't forcibly blackened.  Make sure this is done and that the
:;; black heights are correctly tracked.  This causes all manner of
:;; trouble otherwise, including leaking nodes because `rbtree_join'
:;; assumes that a tree with zero black-height must be empty -- which
:;; is true.
=					((((_ *12 _)
			*13
					(_ *14 _))
		16
					((_ *17 _)
			*18
					(_ *19
						(_ 23 _))))
	*24
					(((_ *28 _)
				32
					(_ *35 _))
			*36
					(_ *37
						(_ 39 _))))
D 22@ / D ) D ) D

:
:;; The hairy test case which found both of these bugs.
=						(((((_ 0 _)
					*3 _)
			*6
					(_ *9_))
		11
						(((_ 12 _)
					*21 _)
			*22
					((_ *27
						(_ 28 _))
				31
					(_ *35 _))))
	*41
						(((_ 49 _)
					*50
						(_ 55 _))
			*57
					(_ *59 _)))
D

(
=						(((((_ *0
							(_ 1 _))
				*3
						(_ *4 _))
			6
							(((_ 11 _)
						*12 _)
				*13
						(_ *14 _)))
		*16
						(((_ *17 _)
				*18
						(_ *19
							(_ 23 _)))
			24
						(((_ *28 _)
					32
						(_ *35 _))
				*36
						(_ *37 _))))
	*39
						(((_ *41 _)
				*43
						(_ *44
							(_ 45 _)))
		*52
						(((_ *53 _)
					56
						(_ *58 _))
				*60
						(_ *61 _))))
D

\ D ) D ) D

:
:;; `rbtree_splitroot' just could not track subtree heights correctly.

=						(((((_ *4
							(_ 6 _))
				*10
						(_ *11 _))
			13
						((_ *17 _)
				*18
							((_ 19 _)
						*20 _)))
		*22
						((_ *23 _)
				*25
							((_ 26 _)
						*27 _)))
	*30
							((((_ 32 _)
						*33 _)
				*34
						((_ *36
							(_ 38 _))
					40
						(_ *41 _)))
		*43
							(((_ 45 _)
						*46 _)
				*48
							(((_ 49 _)
						*51 _)
					53
						(_ *61
							(_ 62 _))))))
D

(
=					(((((_ *6 _)
				15
					(_ *16 _))
			*23
					(_ *24 _))
		33
					(((_ *35 _)
				36
					(_ *37
						(_ 39 _)))
			*40
					((_ *43 _)
				47
					(_ *48
						(_ 49 _)))))
	*50
					((_ *57 _)
			*59
						((_ 61 _)
					*62 _)))
D

| D ) D