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

   1 ;;; Manually constructed tests for splay trees.
   2
   3 :;;;-------------------------------------------------------------------------
   4 :;;; Search and splaying.
   5
   6 :
   7 :;; Initial state
   8 =_ 2+ 4+ 6+ 8+ 10+ 12+ 14+ 16+ 18+ 20+ 22+ 24+ B D
   9
  10 :
  11 :;; Root.
  12 " VZ 16k? Dn V )
  13
  14 :
  15 :;; Zig.
  16 ;;             n                                c
  17 ;;               (*)                        ( )
  18 ;;       c     /     \                    /     \     n
  19 ;;         ( )                  --->    l         (*)
  20 ;;        /   \                                  /   \
  21 ;;      l       r                              r
  22 " VZ  8k?
  23         V:XYLA-SPLAY SPLAY zig left child
  24   Dn V )
  25 " VZ 24k?
  26         V:XYLA-SPLAY SPLAY zig right child
  27   Dn V )
  28
  29 :
  30 :;; Zig-zig.
  31 ;;
  32 ;;                 p                            c
  33 ;;                   (*)                    ( )
  34 ;;           n     /     \                /     \     n
  35 ;;             (*)                      l         (*)
  36 ;;       c    / \               --->             /   \    p
  37 ;;         ( )                                 r      (*)
  38 ;;        /   \                                      /   \
  39 ;;      l       r
  40 " VZ  4k?
  41         V:XYLA-SPLAY SPLAY zig-zig left/left child
  42   Dn V )
  43 " VZ  2k?
  44         V:XYLA-SPLAY SPLAY zig-zig left/left child
  45         V:XYLA-SPLAY SPLAY zig left child
  46   Dn V )
  47 " VZ 14k?
  48         V:XYLA-SPLAY SPLAY zig-zig right/right child
  49         V:XYLA-SPLAY SPLAY zig left child
  50   Dn V )
  51
  52 :
  53 :;; Zig-zag.
  54 ;;           p
  55 ;;             (*)                           c
  56 ;;     n     /     \                           ( )
  57 ;;       (*)                           n     /     \    p
  58 ;;      /   \    c              --->     (*)        (*)
  59 ;;           ( )                        /   \      /   \
  60 ;;          /   \                             l  r
  61 ;;        l       r
  62 " VZ 12k?
  63         V:XYLA-SPLAY SPLAY zig-zag left/right child
  64   Dn V )
  65 " VZ 20k?
  66         V:XYLA-SPLAY SPLAY zig-zag right/left child
  67   Dn V )
  68
  69 :
  70 :;; Misses.
  71 " VZ  1k?
  72         V:XYLA-SPLAY SPLAY zig-zig left/left child
  73         V:XYLA-SPLAY SPLAY zig left child
  74   Dn V )
  75 " VZ 11k?
  76         V:XYLA-SPLAY SPLAY zig-zag right/left child
  77         V:XYLA-SPLAY SPLAY zig left child
  78   Dn V )
  79 " VZ 15k?
  80         V:XYLA-SPLAY SPLAY zig-zig right/right child
  81         V:XYLA-SPLAY SPLAY zig left child
  82   Dn V )
  83 " VZ 17k?
  84         V:XYLA-SPLAY SPLAY zig-zig left/left child
  85         V:XYLA-SPLAY SPLAY zig right child
  86   Dn V )
  87 " VZ 23k?
  88         V:XYLA-SPLAY SPLAY zig-zag left/right child
  89         V:XYLA-SPLAY SPLAY zig right child
  90   Dn V )
  91
  92 :
  93 :;; Splaying example from the paper.
  94 =
  95                     (((((_ 5 _)
  96                 10
  97                             (((_ 15 _)
  98                         20
  99                                 ((_ 25 _)
 100                             30
 101                                     ((_ 35 _)
 102                                 40
 103                                         ((_ 45 _)
 104                                     50
 105                                         (_ 55 _)))))
 106                     60
 107                         (_ 65 _)))
 108             70
 109                 (_ 75 _))
 110         80
 111             (_ 85 _))
 112     90
 113         (_ 95 _))
 114
 115 D 50k? Dn
 116
 117 :
 118 :;; All zig-zig example from the paper.
 119 =                               ((((((((_ 5 _)
 120                             10
 121                                 (_ 15 _))
 122                         20
 123                             (_ 25 _))
 124                     30
 125                         (_ 35 _))
 126                 40
 127                     (_ 45 _))
 128             50
 129                 (_ 55 _))
 130         60
 131             (_ 65 _))
 132     70
 133         (_ 75 _))
 134 D 10k? Dn
 135
 136 :
 137 :;; All zig-zag example from the paper.
 138 =           (((_ 5 _)
 139         10
 140                     (((_ 15 _)
 141                 20
 142                             (((_ 25 _)
 143                         30
 144                                 ((_ 35 _)
 145                             40
 146                                 (_ 45 _)))
 147                     50
 148                         (_ 55 _)))
 149             60
 150                 (_ 65 _)))
 151     70
 152         (_ 75 _))
 153
 154 D 40k? Dn
 155
 156 :
 157 :;; Unsuccessful search example from the paper.  The same setup is used for
 158 :;; some later examples, and I've modified it because I consistently use the
 159 :;; leftmost node of the right tree as the joining node, rather than the
 160 :;; rightmost node of the left tree.
 161 =           (((_ 10 _)
 162         20
 163             (_ 30
 164                     ((_ 35 _)
 165                 40 _)))
 166     50
 167         (_ 60
 168                 ((_ 70 _)
 169             90
 170                 (_ 100 _))))
 171 " D 80k? Dn
 172
 173 :
 174 :;;;-------------------------------------------------------------------------
 175 :;;; Insertion.
 176
 177 :
 178 :;; Initial state.
 179 =_ 2+ 4+ 6+ 8+ 10+ 12+ 14+ 16+ 18+ 20+ 22+ 24+ B D
 180
 181 :
 182 :;; Zig-zig.
 183 " V+Z 25k+
 184         V:XYLA-SPLAY SPLAY zig-zig right/right child
 185   D V )
 186
 187 :
 188 :;; Zig-zag.
 189 " V+Z 23k+
 190         V:XYLA-SPLAY SPLAY zig-zig right/right child
 191         V:XYLA-SPLAY SPLAY zig-zag right/left child
 192   D V )
 193
 194 :
 195 :;; Insertion example from the paper.
 196 ) D 80k+ D (
 197
 198 :
 199 :;;;-------------------------------------------------------------------------
 200 :;;; Removal.
 201
 202 :
 203 :;; Initial state.
 204 =_ 2+ 4+ 6+ 8+ 10+ 12+ 14+ 16+ 18+ 20+ 22+ 24+ B D
 205
 206 :
 207 :;; Root.
 208 " V-Z 16k-
 209         V:XYLA-SPLAY SPLAY zig-zig left/left child
 210   D V )
 211
 212 :
 213 :;; Internal node.
 214 " V-Z 8k-
 215         V:XYLA-SPLAY SPLAY zig left child
 216   D V )
 217
 218 :
 219 :;; Leaf node.
 220 " V-Z 14k-
 221         V:XYLA-SPLAY SPLAY zig-zag left/right child
 222   D V )
 223 " V-Z 18k-
 224         V:XYLA-SPLAY SPLAY zig-zag right/left child
 225   D V )
 226
 227 :
 228 :;; Removal example from the paper, modified for difference in join policy.
 229 ) D 20k- D
 230
 231 :
 232 :;;;-------------------------------------------------------------------------
 233 :;;; Joining.
 234
 235 :
 236 :;; With joining node.  (Trivial!)
 237 =_ #12B D ( #14-25B D V~ 13k~ D V
 238
 239 :
 240 :;; Without joining node.
 241 =_ #12B D ( #14-25B D V~ *k~ D V
 242
 243 :
 244 :;;;-------------------------------------------------------------------------
 245 :;;; Rebalancing.
 246
 247 :
 248 :;; Initial state: right-trailing vine.
 249 =_ #15-1 D
 250
 251 :
 252 :;; No path.
 253 " *p B Dp )
 254
 255 :
 256 :;; Full path tracking.
 257 " 12@p B Dp )
 258
 259 :
 260 :;; Empty path tracking.
 261 " 12@p { B Dp )
 262 " 12@p } B Dp )
 263
 264 :
 265 :;; A tree with a very long left-leaning tentril in the middle.
 266 =_ #101-115B
 267 ( 117+
 268   ( #490-624 118~
 269   ( #921-923B 920~
 270   ( #925-931B 924~
 271 116~
 272 D
 273
 274 :
 275 :;; Iteration rebalance.
 276 ( #200 Vi i V 101@ p )
 277 " Vi i V 598@ p )
 278
 279 :
 280 :;; Path manoeuvre rebalance.
 281 ( #200 Vp [ p V )
 282 ( #200-1 Vp ] p V )
 283 " 500@ Vp < p V )
 284 " 500@ Vp { p V )
 285 ( #130-0
 286   " 128@ Vp > p V )
 287   " 128@ Vp } p V )
 288 )
 289
 290 :
 291 :;; Lookup rebalance.
 292 ( #200
 293   " V@ 1? V n 99@ p )
 294   " V@ 1@ V p )
 295 )
 296
 297 :
 298 :;; Removal rebalance.
 299 " V- 118- V 118@ p )
 300
 301 :
 302 :;; Join rebalance.
 303 ( #15B ( #100-300 K V~ *k~ V K )
 304
 305 :
 306 :;; Set op rebalance.
 307 " ( #1-20 #80-120 #480-510 #910-920 B V| |
 308         V:XYLA-SPLAY UNISECT rebalance
 309   V K ) K )
 310 " ( #1-20 #80-120 #480-510 #910-920 B V\ \
 311         V:XYLA-SPLAY DIFFSECT rebalance
 312   V K ) K ))
 313
 314 :
 315 :;;;----- That's all, folks -------------------------------------------------