chiark - git - mdw - xyla/blob - t/treaptest.in

   1 ;;; Manually constructed tests for treaps.
   2
   3 :;;;-------------------------------------------------------------------------
   4 :;;; Insertion and removal.
   5
   6 :
   7 :;; Initial state.
   8 =                               ((((_ 110 _)
   9                         120
  10                                 (_ 130 _))
  11                 140
  12                                 ((_ 150 _)
  13                         160
  14                                 (_ 170 _)))
  15         180
  16                                 (((_ 190 _)
  17                         200
  18                                 (_ 210 _))
  19                 220
  20                                 ((_ 230 _)
  21                         240
  22                                 (_ 250 _))))
  23 D
  24
  25 :
  26 :;; Insertion.
  27 " 0xfff00000$ V+ 155k+
  28   D V )
  29 " 0xffd00000$ V+ 155k+
  30         V:XYLA-TREAP INSERT right child
  31         V:XYLA-TREAP INSERT left child
  32   D V )
  33 " 0xffa00000$ V+ 155k+
  34         V:XYLA-TREAP INSERT right child
  35         V:XYLA-TREAP INSERT left child
  36         V:XYLA-TREAP INSERT right child
  37         V:XYLA-TREAP INSERT left child
  38   D V )
  39
  40 :
  41 :;; Removal.
  42 " V- 170k- D V )
  43 " V- 220k-
  44         V:XYLA-TREAP REMOVE float left child
  45         V:XYLA-TREAP REMOVE float right child
  46         V:XYLA-TREAP REMOVE float left child
  47   D V )
  48 " V- 180k-
  49         V:XYLA-TREAP REMOVE float left child
  50         V:XYLA-TREAP REMOVE float right child
  51         V:XYLA-TREAP REMOVE float left child
  52         V:XYLA-TREAP REMOVE float right child
  53         V:XYLA-TREAP REMOVE float left child
  54   D V )
  55
  56 :
  57 :;;;-------------------------------------------------------------------------
  58 :;;; Splitting and joining.
  59
  60 :
  61 :;; With joining node.
  62 " V/ 200@p/
  63         V:XYLA-TREAP SPLIT left child
  64         V:XYLA-TREAP SPLIT right child
  65   D V % D ) % D %
  66   V~ 0xfff00000$ 199k~
  67         V:XYLA-TREAP JOIN mid float left (next right)
  68         V:XYLA-TREAP JOIN mid float right (next left)
  69         V:XYLA-TREAP JOIN mid float left (next right)
  70         V:XYLA-TREAP JOIN mid float right (next done)
  71   D V )
  72
  73 :
  74 :;; Without joining node.
  75 " V/ 195@p/
  76         V:XYLA-TREAP SPLIT right child
  77         V:XYLA-TREAP SPLIT left child
  78         V:XYLA-TREAP SPLIT left child
  79         V:XYLA-TREAP SPLIT right child
  80   D V % D ) % D %
  81   V~ *k~
  82         V:XYLA-TREAP JOIN stitch right edge
  83         V:XYLA-TREAP JOIN stitch left edge
  84   D V )
  85
  86 :
  87 :;;;----- That's all, folks -------------------------------------------------