;;; Manually constructed tests for red-black trees.

:;;;-------------------------------------------------------------------------
:;;; Insertion.

:
:;; Starting point for the following tests.
=				((((_ 10 _)
			*20
				(_ 30 _))
		40
				((_ 50 _)
			*60 _))
	*70
			(_ *80
				(_ 90 _)))
D

:
:;; Children of a black node.
" V+ 65k+ D V )
" V+ 75k+ D V )

:
:;; Ascend tree.
;;		  p				  p
;;		   (*)				   ( )
;;	    n	 /     \    s		    n	 /     \    s
;;	     ( )	 ( )	--->	     (*)	 (*)
;;	c   /   \	/   \		c   /   \	/   \
;;	 ( )				 ( )
;;	/   \				/   \
" 5k+ 15k+ V+ 0k+
	V:XYLA-RB INSERT red sibling: ascend
	V:XYLA-RB INSERT red sibling: extend tree
  D V )

:
:;; Zig-zig.
;;		  p
;;		   (*)			      n
;;	    n	 /     \		       (*)
;;	     ( )		--->	c    /	   \    p
;;	c   /   \			 ( )	     ( )
;;	 ( )				/   \	    /	\
;;	/   \
" V+ 45k+
	V:XYLA-RB INSERT zig-zig (left child)
  D V )
" V+ 95k+
	V:XYLA-RB INSERT zig-zig (right child)
  D V )

:
:;; Zig-zag.
;;		  p
;;		   (*)			      c
;;	    n	 /     \		       (*)
;;	     ( )		--->	n    /	   \    p
;;	    /   \   c			 ( )	     ( )
;;		 ( )			/   \	    /	\
;;		/   \
" V+ 55k+
	V:XYLA-RB INSERT zig-zag (left child)
  D V )
" V+ 85k+
	V:XYLA-RB INSERT zig-zag (right child)
  D V )

:
:;;;-------------------------------------------------------------------------
:;;; Removal.

;; There are too many cases here.

:
:;; Initial state.
=					((((_ *0 _)
				2
						((_ 4 _)
					*6
						(_ 8 _)))
			*10
					(_ *12 _))
	*14
					((_ *16 _)
			*18
						(((_ 20 _)
					*22
						(_ 24 _))
				26
					(_ *28 _))))
D

:
:;; Red node.
" V- 2k- D V )
" V- 4k- D V )
" V- 8k- D V )
" V- 18k- D V )

:
:;; Red sibling, outer red great-nibling.
;;	      p					      s
;;	       (*)				       (*)
;;     n     /	   \	s			t    /	   \
;;	(* *)	     ( )	--->		 ( )
;;	/   \	t   /   \		    p	/   \   r
;;		 (*)			     (*)     (*)
;;		/   \	r		n   /   \   /	\
;;		     ( )		 (*)
;;		    /	\		/   \
" 8k- D V- 12k-
	V:XYLA-RB REMOVE red sibling, outer red great-nibling (right child)
  D V )
" 20k- D V- 16k-
	V:XYLA-RB REMOVE red sibling, outer red great-nibling (left child)
  D V )

:
:;; Red sibling, inner red great-nibling.
;;	      p					      s
;;	       (*)				       (*)
;;     n     /	   \	s			l    /	   \
;;	(* *)	     ( )	--->		 ( )
;;	/   \	t   /   \		    p	/   \   t
;;		 (*)			     (*)     (*)
;;	    l	/   \			n   /	\   /	\
;;	     ( )			 (*)
;;	    /	\			/   \
" 4k- D V- 12k-
	V:XYLA-RB REMOVE red sibling, inner red great-nibling (right child)
  D V )
" 24k- D V- 16k-
	V:XYLA-RB REMOVE red sibling, inner red great-nibling (left child)
  D V )

:
:;; Red sibling, no red great-nibling.
;;	      p					  s
;;	       (*)				   (*)
;;     n     /	   \	s		    p	 /     \
;;	(* *)	     ( )	--->	     (*)
;;	/   \	t   /   \		n   /	\   t
;;		 (*)			 (*)	 ( )
;;		/   \			/   \	/   \
" 4k- 8k- D V- 12k-
	V:XYLA-RB REMOVE red sibling, no red great-nibling (right child)
  D V )
" 20k- 24k- D V- 16k-
	V:XYLA-RB REMOVE red sibling, no red great-nibling (left child)
  D V )

:
:;; Black sibling, outer red nibling.
;;	      p					   s
;;	       (?)				    (?)
;;     n     /	   \   s		     p	  /     \   r
;;	(* *)	    (*)		--->	      (*)	 (*)
;;	/   \	   /   \   r		n    /	 \	/   \
;;			( )		 (*)
;;		       /   \		/   \
" 4k- D V- 0k-
	V:XYLA-RB REMOVE black sibling, outer red nibling (left child)
  D V )
" 24k- D V- 28k-
	V:XYLA-RB REMOVE black sibling, outer red nibling (right child)
  D V )

:
:;; Black sibling, inner red nibling.
;;	      p					   l
;;	       (?)				    (?)
;;     n     /	   \   s		     p	  /     \   s
;;	(* *)	    (*)		--->	      (*)	 (*)
;;	/   \  l   /   \		n    /	 \	/   \
;;		( )			 (*)
;;	       /   \			/   \
" 8k- D V- 0k-
	V:XYLA-RB REMOVE black sibling, inner red nibling (left child)
  D V )
" 20k- D V- 28k-
	V:XYLA-RB REMOVE black sibling, inner red nibling (right child)
  D V )

:
:;; Black sibling, red parent, no red nibling.
;;	      p					   p
;;	       ( )				    (*)
;;     n     /	   \   s		     n	  /     \   s
;;	(* *)	    (*)		--->	      (*)	 ( )
;;	/   \      /   \		     /	 \	/   \
" 4k- 8k- D V- 0k-
	V:XYLA-RB REMOVE black sibling, red parent, no red nibling (left child)
  D V )
" 20k- 24k- D V- 28k-
	V:XYLA-RB REMOVE black sibling, red parent, no red nibling (right child)
  D V )

:
:;; Black sibling, black parent, no red nibling.
;;	      p					   p
;;	       (*)				   (* *)
;;     n     /	   \   s		     n	  /     \   s
;;	(* *)	    (*)		--->	      (*)	 ( )
;;	/   \      /   \		     /	 \	/   \
" 4k- 8k- 0k- 6k- 20k- 24k- 16k- 28k- D
" V- 12k-
	V:XYLA-RB REMOVE black sibling, black parent, no red nibling (right child)
	V:XYLA-RB REMOVE black sibling, black parent, no red nibling (left child)
	V:XYLA-RB REMOVE shorten tree
  D V )
" V- 18k-
	V:XYLA-RB REMOVE black sibling, black parent, no red nibling (left child)
	V:XYLA-RB REMOVE black sibling, black parent, no red nibling (right child)
	V:XYLA-RB REMOVE shorten tree
  D V )
)

:;;;-------------------------------------------------------------------------
:;;; Joining.

:
:;; Equal heights.
=_ #6 D ( #13-8 D V~ 7k~
	V:XYLA-RB JOIN equal heights
   D V

:
:;; Red sibling.
=_ #8 D ( 10+ D V~ 9k~
	V:XYLA-RB JOIN red sibling (right child): extend tree
   D V
=_ 1+ D ( #10-3 D V~ 2k~
	V:XYLA-RB JOIN red sibling (left child): extend tree
   D V

=_ #12 D ( 14+ D V~ 13k~
	V:XYLA-RB JOIN red sibling (right child): ascend
   D V
=_ 1+ D ( #12-3 D V~ 2k~
	V:XYLA-RB JOIN no red sibling (left child)
   D V

:
:;; No red sibling.
=_ # 7 D ( 9+ D V~ 8k~
	V:XYLA-RB JOIN no red sibling (right child)
   D V
=_ 1+ D ( #9-3 D V~ 2k~
	V:XYLA-RB JOIN no red sibling (left child)
   D V

:
:;;;----- That's all, folks -------------------------------------------------