;;; Manually constructed tests for splay trees.

:;;;-------------------------------------------------------------------------
:;;; Search and splaying.

:
:;; Initial state
=_ 2+ 4+ 6+ 8+ 10+ 12+ 14+ 16+ 18+ 20+ 22+ 24+ B D

:
:;; Root.
" VZ 16k? Dn V )

:
:;; Zig.
;;	       n				c
;;		 (*)			    ( )
;;       c     /     \			  /     \     n
;;         ( )			--->	l	  (*)
;;	  /   \					 /   \
;;	l	r			       r
" VZ  8k?
	V:XYLA-SPLAY SPLAY zig left child
  Dn V )
" VZ 24k?
	V:XYLA-SPLAY SPLAY zig right child
  Dn V )

:
:;; Zig-zig.
;;
;;		   p				c
;;		     (*)		    ( )
;;	     n     /     \		  /     \     n
;;	       (*)			l	  (*)
;;       c    /	\		--->		 /   \	  p
;;	   ( )				       r      (*)
;;	  /   \					     /   \
;;	l	r
" VZ  4k?
	V:XYLA-SPLAY SPLAY zig-zig left/left child
  Dn V )
" VZ  2k?
	V:XYLA-SPLAY SPLAY zig-zig left/left child
	V:XYLA-SPLAY SPLAY zig left child
  Dn V )
" VZ 14k?
	V:XYLA-SPLAY SPLAY zig-zig right/right child
	V:XYLA-SPLAY SPLAY zig left child
  Dn V )

:
:;; Zig-zag.
;;	     p
;;	       (*)			     c
;;     n     /	   \			       ( )
;;	 (*)			       n     /	   \	p
;;	/   \	 c		--->	 (*)	    (*)
;;	     ( )			/   \	   /   \
;;	    /	\			      l  r
;;	  l	  r
" VZ 12k?
	V:XYLA-SPLAY SPLAY zig-zag left/right child
  Dn V )
" VZ 20k?
	V:XYLA-SPLAY SPLAY zig-zag right/left child
  Dn V )

:
:;; Misses.
" VZ  1k?
	V:XYLA-SPLAY SPLAY zig-zig left/left child
	V:XYLA-SPLAY SPLAY zig left child
  Dn V )
" VZ 11k?
	V:XYLA-SPLAY SPLAY zig-zag right/left child
	V:XYLA-SPLAY SPLAY zig left child
  Dn V )
" VZ 15k?
	V:XYLA-SPLAY SPLAY zig-zig right/right child
	V:XYLA-SPLAY SPLAY zig left child
  Dn V )
" VZ 17k?
	V:XYLA-SPLAY SPLAY zig-zig left/left child
	V:XYLA-SPLAY SPLAY zig right child
  Dn V )
" VZ 23k?
	V:XYLA-SPLAY SPLAY zig-zag left/right child
	V:XYLA-SPLAY SPLAY zig right child
  Dn V )

:
:;; Splaying example from the paper.
=
		    (((((_ 5 _)
		10
			    (((_ 15 _)
			20
				((_ 25 _)
			    30
				    ((_ 35 _)
				40
					((_ 45 _)
				    50
					(_ 55 _)))))
		    60
			(_ 65 _)))
	    70
		(_ 75 _))
	80
	    (_ 85 _))
    90
	(_ 95 _))

D 50k? Dn

:
:;; All zig-zig example from the paper.
=				((((((((_ 5 _)
			    10
				(_ 15 _))
			20
			    (_ 25 _))
		    30
			(_ 35 _))
		40
		    (_ 45 _))
            50
		(_ 55 _))
	60
	    (_ 65 _))
    70
	(_ 75 _))
D 10k? Dn

:
:;; All zig-zag example from the paper.
=	    (((_ 5 _)
	10
		    (((_ 15 _)
		20
			    (((_ 25 _)
			30
				((_ 35 _)
			    40
				(_ 45 _)))
		    50
			(_ 55 _)))
            60
		(_ 65 _)))
    70
	(_ 75 _))

D 40k? Dn

:
:;; Unsuccessful search example from the paper.  The same setup is used for
:;; some later examples, and I've modified it because I consistently use the
:;; leftmost node of the right tree as the joining node, rather than the
:;; rightmost node of the left tree.
=	    (((_ 10 _)
	20
	    (_ 30
		    ((_ 35 _)
		40 _)))
    50
	(_ 60
		((_ 70 _)
	    90
		(_ 100 _))))
" D 80k? Dn

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

:
:;; Initial state.
=_ 2+ 4+ 6+ 8+ 10+ 12+ 14+ 16+ 18+ 20+ 22+ 24+ B D

:
:;; Zig-zig.
" V+Z 25k+
	V:XYLA-SPLAY SPLAY zig-zig right/right child
  D V )

:
:;; Zig-zag.
" V+Z 23k+
	V:XYLA-SPLAY SPLAY zig-zig right/right child
	V:XYLA-SPLAY SPLAY zig-zag right/left child
  D V )

:
:;; Insertion example from the paper.
) D 80k+ D (

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

:
:;; Initial state.
=_ 2+ 4+ 6+ 8+ 10+ 12+ 14+ 16+ 18+ 20+ 22+ 24+ B D

:
:;; Root.
" V-Z 16k-
	V:XYLA-SPLAY SPLAY zig-zig left/left child
  D V )

:
:;; Internal node.
" V-Z 8k-
	V:XYLA-SPLAY SPLAY zig left child
  D V )

:
:;; Leaf node.
" V-Z 14k-
	V:XYLA-SPLAY SPLAY zig-zag left/right child
  D V )
" V-Z 18k-
	V:XYLA-SPLAY SPLAY zig-zag right/left child
  D V )

:
:;; Removal example from the paper, modified for difference in join policy.
) D 20k- D

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

:
:;; With joining node.  (Trivial!)
=_ #12B D ( #14-25B D V~ 13k~ D V

:
:;; Without joining node.
=_ #12B D ( #14-25B D V~ *k~ D V

:
:;;;-------------------------------------------------------------------------
:;;; Rebalancing.

:
:;; Initial state: right-trailing vine.
=_ #15-1 D

:
:;; No path.
" *p B Dp )

:
:;; Full path tracking.
" 12@p B Dp )

:
:;; Empty path tracking.
" 12@p { B Dp )
" 12@p } B Dp )

:
:;; A tree with a very long left-leaning tentril in the middle.
=_ #101-115B
( 117+
  ( #490-624 118~
  ( #921-923B 920~
  ( #925-931B 924~
116~
D

:
:;; Iteration rebalance.
( #200 Vi i V 101@ p )
" Vi i V 598@ p )

:
:;; Path manoeuvre rebalance.
( #200 Vp [ p V )
( #200-1 Vp ] p V )
" 500@ Vp < p V )
" 500@ Vp { p V )
( #130-0 
  " 128@ Vp > p V )
  " 128@ Vp } p V )
)

:
:;; Lookup rebalance.
( #200 
  " V@ 1? V n 99@ p )
  " V@ 1@ V p )
)

:
:;; Removal rebalance.
" V- 118- V 118@ p )

:
:;; Join rebalance.
( #15B ( #100-300 K V~ *k~ V K )

:
:;; Set op rebalance.
" ( #1-20 #80-120 #480-510 #910-920 B V| |
	V:XYLA-SPLAY UNISECT rebalance
  V K ) K )
" ( #1-20 #80-120 #480-510 #910-920 B V\ \
	V:XYLA-SPLAY DIFFSECT rebalance
  V K ) K ))

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