chiark - git - mdw - xyla/blob - rb-test-simple.ref

   1 ;; insertion
   2 tree dump, ht = 2
   3         #0x00000000 (n =   1)           (*) 5
   4         #0x00000001 (n =   7)   (*) 6
   5         #0x00000002 (n =   1)           (*) 7
   6         #0x00000003 (n =   5)       ( ) 8
   7         #0x00000004 (n =   1)               ( ) 9
   8         #0x00000005 (n =   3)           (*) 10
   9         #0x00000006 (n =   1)               ( ) 11
  10 tree dump, ht = 2
  11         #0x00000007 (n =   1)           (*) 1
  12         #0x00000008 (n =   5)       ( ) 2
  13         #0x00000009 (n =   1)               ( ) 3
  14         #0x0000000a (n =   3)           (*) 4
  15         #0x00000000 (n =   1)               ( ) 5
  16         #0x00000001 (n =  11)   (*) 6
  17         #0x00000002 (n =   1)           (*) 7
  18         #0x00000003 (n =   5)       ( ) 8
  19         #0x00000004 (n =   1)               ( ) 9
  20         #0x00000005 (n =   3)           (*) 10
  21         #0x00000006 (n =   1)               ( ) 11
  22 ;; initial population for upcoming tests
  23 tree dump, ht = 2
  24         #0x0000000b (n =   1)           (*) 1
  25         #0x0000000c (n =   3)       ( ) 2
  26         #0x0000000d (n =   1)           (*) 3
  27         #0x0000000e (n =   9)   (*) 4
  28         #0x0000000f (n =   1)           (*) 5
  29         #0x00000010 (n =   5)       ( ) 6
  30         #0x00000011 (n =   1)               ( ) 7
  31         #0x00000012 (n =   3)           (*) 8
  32         #0x00000013 (n =   1)               ( ) 9
  33
  34 ;; lookup
  35 #<node #0x0000000f 5>
  36 (nil)
  37
  38 ;; path motion
  39 (#<link root -> node #0x00000014 4> #<link node #0x00000014 4 left -> node #0x00000015 2> #<link node #0x00000015 2 left -> node #0x00000016 1>)
  40 1
  41 (#<link root -> node #0x00000014 4> #<link node #0x00000014 4 left -> node #0x00000015 2>)
  42 2
  43 (#<link root -> node #0x00000014 4> #<link node #0x00000014 4 left -> node #0x00000015 2> #<link node #0x00000015 2 right -> node #0x00000017 3>)
  44 3
  45 (#<link root -> node #0x00000014 4>)
  46 4
  47 (#<link root -> node #0x00000019 5> #<link node #0x00000019 5 right -> node #0x0000001a 8> #<link node #0x0000001a 8 right -> node #0x0000001c 9>)
  48 9
  49 (#<link root -> node #0x00000019 5> #<link node #0x00000019 5 right -> node #0x0000001a 8>)
  50 8
  51 (#<link root -> node #0x00000019 5> #<link node #0x00000019 5 right -> node #0x0000001a 8> #<link node #0x0000001a 8 left -> node #0x00000018 6> #<link node #0x00000018 6 right -> node #0x0000001b 7>)
  52 7
  53 (#<link root -> node #0x00000019 5>)
  54 (#<link root -> node #0x00000019 5> #<link node #0x00000019 5 left -> node #0x00000015 2> #<link node #0x00000015 2 right -> node #0x00000017 3>)
  55 3
  56 (#<link root -> node #0x00000019 5> #<link node #0x00000019 5 left -> node #0x00000015 2> #<link node #0x00000015 2 right -> node #0x00000017 3> #<link node #0x00000017 3 right -> (nil)>)
  57 (#<link root -> node #0x00000019 5> #<link node #0x00000019 5 left -> node #0x00000015 2> #<link node #0x00000015 2 right -> node #0x00000017 3>)
  58 (#<link root -> node #0x00000019 5> #<link node #0x00000019 5 left -> node #0x00000015 2> #<link node #0x00000015 2 right -> node #0x00000017 3> #<link node #0x00000017 3 right -> (nil)>)
  59 (#<link root -> node #0x00000019 5>)
  60 (#<link root -> node #0x00000019 5> #<link node #0x00000019 5 left -> node #0x00000015 2> #<link node #0x00000015 2 left -> node #0x00000016 1> #<link node #0x00000016 1 left -> (nil)>)
  61 (#<link root -> node #0x00000019 5> #<link node #0x00000019 5 left -> node #0x00000015 2> #<link node #0x00000015 2 left -> node #0x00000016 1>)
  62 (#<link root -> node #0x00000019 5> #<link node #0x00000019 5 right -> node #0x0000001a 8> #<link node #0x0000001a 8 right -> node #0x0000001c 9> #<link node #0x0000001c 9 right -> (nil)>)
  63 (#<link root -> node #0x00000019 5> #<link node #0x00000019 5 right -> node #0x0000001a 8> #<link node #0x0000001a 8 right -> node #0x0000001c 9>)
  64
  65 ;; remove
  66 7
  67 6
  68 4
  69 1
  70 5
  71 2
  72 3
  73 8
  74 9
  75 (empty tree)
  76
  77 ;; join
  78 1 2 3 4 5 6 7 8 9
  79 11 12 13
  80 (no key)
  81 tree dump, ht = 3
  82         #0x00000028 (n =   1)                   (*) 1
  83         #0x00000027 (n =   3)           (*) 2
  84         #0x00000029 (n =   1)                   (*) 3
  85         #0x00000026 (n =  12)   (*) 4
  86         #0x0000002b (n =   1)                   (*) 5
  87         #0x0000002a (n =   8)           (*) 6
  88         #0x0000002d (n =   1)                       ( ) 7
  89         #0x0000002c (n =   3)                   (*) 8
  90         #0x0000002e (n =   1)                       ( ) 9
  91         #0x0000002f (n =   6)               ( ) 11
  92         #0x00000031 (n =   2)                   (*) 12
  93         #0x00000030 (n =   1)                       ( ) 13
  94 1 2 3 4 5 6 7 8 9
  95 11 12 13
  96 10
  97 tree dump, ht = 3
  98         #0x00000034 (n =   1)                   (*) 1
  99         #0x00000033 (n =   3)           (*) 2
 100         #0x00000035 (n =   1)                   (*) 3
 101         #0x00000032 (n =  13)   (*) 4
 102         #0x00000037 (n =   1)                   (*) 5
 103         #0x00000036 (n =   9)           (*) 6
 104         #0x00000039 (n =   1)                       ( ) 7
 105         #0x00000038 (n =   3)                   (*) 8
 106         #0x0000003a (n =   1)                       ( ) 9
 107         #0x0000003e (n =   7)               ( ) 10
 108         #0x0000003b (n =   1)                       ( ) 11
 109         #0x0000003d (n =   3)                   (*) 12
 110         #0x0000003c (n =   1)                       ( ) 13
 111 1 2 3 4 5 6 7 8 9
 112 11
 113 10
 114 tree dump, ht = 3
 115         #0x00000041 (n =   1)                   (*) 1
 116         #0x00000040 (n =   3)           (*) 2
 117         #0x00000042 (n =   1)                   (*) 3
 118         #0x0000003f (n =  11)   (*) 4
 119         #0x00000044 (n =   1)                   (*) 5
 120         #0x00000043 (n =   7)           (*) 6
 121         #0x00000046 (n =   1)                       ( ) 7
 122         #0x00000045 (n =   3)                   (*) 8
 123         #0x00000047 (n =   1)                       ( ) 9
 124         #0x00000049 (n =   5)               ( ) 10
 125         #0x00000048 (n =   1)                   (*) 11
 126 1 2 3 4 5 6 7 8 9
 127 (empty tree)
 128 10
 129 tree dump, ht = 3
 130         #0x0000004c (n =   1)                   (*) 1
 131         #0x0000004b (n =   3)           (*) 2
 132         #0x0000004d (n =   1)                   (*) 3
 133         #0x0000004a (n =  10)   (*) 4
 134         #0x0000004f (n =   1)                   (*) 5
 135         #0x0000004e (n =   6)           (*) 6
 136         #0x00000051 (n =   1)                   (*) 7
 137         #0x00000050 (n =   4)               ( ) 8
 138         #0x00000052 (n =   2)                   (*) 9
 139         #0x00000053 (n =   1)                       ( ) 10
 140 1 2 3 4 5 6 7 8 9
 141 (empty tree)
 142 (no key)
 143 tree dump, ht = 2
 144         #0x00000056 (n =   1)           (*) 1
 145         #0x00000055 (n =   3)       ( ) 2
 146         #0x00000057 (n =   1)           (*) 3
 147         #0x00000054 (n =   9)   (*) 4
 148         #0x00000059 (n =   1)           (*) 5
 149         #0x00000058 (n =   5)       ( ) 6
 150         #0x0000005b (n =   1)               ( ) 7
 151         #0x0000005a (n =   3)           (*) 8
 152         #0x0000005c (n =   1)               ( ) 9
 153 1 2 3 4 5 6 7 8 9
 154 11 12 13 14 15 16 17 18 19 20
 155 10
 156 tree dump, ht = 3
 157         #0x0000005f (n =   1)                   (*) 1
 158         #0x0000005e (n =   3)               ( ) 2
 159         #0x00000060 (n =   1)                   (*) 3
 160         #0x0000005d (n =   9)           (*) 4
 161         #0x00000062 (n =   1)                   (*) 5
 162         #0x00000061 (n =   5)               ( ) 6
 163         #0x00000064 (n =   1)                       ( ) 7
 164         #0x00000063 (n =   3)                   (*) 8
 165         #0x00000065 (n =   1)                       ( ) 9
 166         #0x00000070 (n =  13)       ( ) 10
 167         #0x00000066 (n =   1)                   (*) 11
 168         #0x00000067 (n =   3)           (*) 12
 169         #0x00000068 (n =   1)                   (*) 13
 170         #0x00000069 (n =  20)   (*) 14
 171         #0x0000006a (n =   1)                   (*) 15
 172         #0x0000006b (n =   6)           (*) 16
 173         #0x0000006c (n =   1)                   (*) 17
 174         #0x0000006d (n =   4)               ( ) 18
 175         #0x0000006e (n =   2)                   (*) 19
 176         #0x0000006f (n =   1)                       ( ) 20
 177
 178 ;; split
 179 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
 180 (#<link root -> node #0x00000078 8> #<link node #0x00000078 8 right -> node #0x00000080 16> #<link node #0x00000080 16 right -> node #0x00000084 20> #<link node #0x00000084 20 left -> node #0x00000082 18>)
 181 tree dump, ht = 3
 182         #0x00000083 (n =   1)                   (*) 19
 183         #0x00000084 (n =   3)               ( ) 20
 184         #0x00000085 (n =   1)                   (*) 21
 185         #0x00000086 (n =   5)           (*) 22
 186         #0x00000087 (n =   1)                   (*) 23
 187         #0x00000088 (n =  13)   (*) 24
 188         #0x00000089 (n =   1)                   (*) 25
 189         #0x0000008a (n =   7)           (*) 26
 190         #0x0000008b (n =   1)                   (*) 27
 191         #0x0000008c (n =   5)               ( ) 28
 192         #0x0000008d (n =   1)                       ( ) 29
 193         #0x0000008e (n =   3)                   (*) 30
 194         #0x0000008f (n =   1)                       ( ) 31
 195 tree dump, ht = 1
 196         #0x00000082 (n =   1)   (*) 18
 197 tree dump, ht = 4
 198         #0x00000071 (n =   1)                           (*) 1
 199         #0x00000072 (n =   3)                   (*) 2
 200         #0x00000073 (n =   1)                           (*) 3
 201         #0x00000074 (n =   7)           (*) 4
 202         #0x00000075 (n =   1)                           (*) 5
 203         #0x00000076 (n =   3)                   (*) 6
 204         #0x00000077 (n =   1)                           (*) 7
 205         #0x00000078 (n =  17)   (*) 8
 206         #0x00000079 (n =   1)                           (*) 9
 207         #0x0000007a (n =   3)                   (*) 10
 208         #0x0000007b (n =   1)                           (*) 11
 209         #0x0000007c (n =   9)           (*) 12
 210         #0x0000007d (n =   1)                           (*) 13
 211         #0x0000007e (n =   5)                   (*) 14
 212         #0x0000007f (n =   1)                           (*) 15
 213         #0x00000080 (n =   3)                       ( ) 16
 214         #0x00000081 (n =   1)                           (*) 17
 215 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 18 19 20 21 22 23 24 25 26 27 28 29 30 31
 216 (#<link root -> node #0x00000097 8> #<link node #0x00000097 8 right -> node #0x0000009f 16> #<link node #0x0000009f 16 right -> node #0x000000a7 24> #<link node #0x000000a7 24 left -> node #0x000000a3 20> #<link node #0x000000a3 20 left -> node #0x000000a1 18> #<link node #0x000000a1 18 left -> (nil)>)
 217 tree dump, ht = 3
 218         #0x000000a1 (n =   2)                   (*) 18
 219         #0x000000a2 (n =   1)                       ( ) 19
 220         #0x000000a3 (n =   6)           (*) 20
 221         #0x000000a4 (n =   1)                   (*) 21
 222         #0x000000a5 (n =   3)               ( ) 22
 223         #0x000000a6 (n =   1)                   (*) 23
 224         #0x000000a7 (n =  14)   (*) 24
 225         #0x000000a8 (n =   1)                   (*) 25
 226         #0x000000a9 (n =   7)           (*) 26
 227         #0x000000aa (n =   1)                   (*) 27
 228         #0x000000ab (n =   5)               ( ) 28
 229         #0x000000ac (n =   1)                       ( ) 29
 230         #0x000000ad (n =   3)                   (*) 30
 231         #0x000000ae (n =   1)                       ( ) 31
 232 tree dump, ht = 0
 233         (tree empty)
 234 tree dump, ht = 4
 235         #0x00000090 (n =   1)                           (*) 1
 236         #0x00000091 (n =   3)                   (*) 2
 237         #0x00000092 (n =   1)                           (*) 3
 238         #0x00000093 (n =   7)           (*) 4
 239         #0x00000094 (n =   1)                           (*) 5
 240         #0x00000095 (n =   3)                   (*) 6
 241         #0x00000096 (n =   1)                           (*) 7
 242         #0x00000097 (n =  16)   (*) 8
 243         #0x00000098 (n =   1)                           (*) 9
 244         #0x00000099 (n =   3)                   (*) 10
 245         #0x0000009a (n =   1)                           (*) 11
 246         #0x0000009b (n =   8)           (*) 12
 247         #0x0000009c (n =   1)                           (*) 13
 248         #0x0000009d (n =   4)                   (*) 14
 249         #0x0000009e (n =   2)                           (*) 15
 250         #0x0000009f (n =   1)                               ( ) 16
 251 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 20 21 22 23 24 25 26 27 28 29 30 31
 252 (#<link root -> node #0x000000b6 8> #<link node #0x000000b6 8 right -> node #0x000000be 16> #<link node #0x000000be 16 right -> node #0x000000c6 24> #<link node #0x000000c6 24 left -> node #0x000000c2 20> #<link node #0x000000c2 20 left -> node #0x000000c0 18> #<link node #0x000000c0 18 right -> (nil)>)
 253 tree dump, ht = 3
 254         #0x000000c2 (n =   1)                       ( ) 20
 255         #0x000000c3 (n =   2)                   (*) 21
 256         #0x000000c4 (n =   4)           (*) 22
 257         #0x000000c5 (n =   1)                   (*) 23
 258         #0x000000c6 (n =  12)   (*) 24
 259         #0x000000c7 (n =   1)                   (*) 25
 260         #0x000000c8 (n =   7)           (*) 26
 261         #0x000000c9 (n =   1)                   (*) 27
 262         #0x000000ca (n =   5)               ( ) 28
 263         #0x000000cb (n =   1)                       ( ) 29
 264         #0x000000cc (n =   3)                   (*) 30
 265         #0x000000cd (n =   1)                       ( ) 31
 266 tree dump, ht = 0
 267         (tree empty)
 268 tree dump, ht = 4
 269         #0x000000af (n =   1)                           (*) 1
 270         #0x000000b0 (n =   3)                   (*) 2
 271         #0x000000b1 (n =   1)                           (*) 3
 272         #0x000000b2 (n =   7)           (*) 4
 273         #0x000000b3 (n =   1)                           (*) 5
 274         #0x000000b4 (n =   3)                   (*) 6
 275         #0x000000b5 (n =   1)                           (*) 7
 276         #0x000000b6 (n =  18)   (*) 8
 277         #0x000000b7 (n =   1)                           (*) 9
 278         #0x000000b8 (n =   3)                   (*) 10
 279         #0x000000b9 (n =   1)                           (*) 11
 280         #0x000000ba (n =  10)           (*) 12
 281         #0x000000bb (n =   1)                           (*) 13
 282         #0x000000bc (n =   6)                   (*) 14
 283         #0x000000bd (n =   1)                           (*) 15
 284         #0x000000be (n =   4)                       ( ) 16
 285         #0x000000bf (n =   1)                               ( ) 17
 286         #0x000000c0 (n =   2)                           (*) 18
 287
 288 ;; set ops
 289 1 3 5 7 9 11 13 15
 290 2 3 6 7 10 11 14 15
 291 union
 292 tree dump, ht = 3
 293         #0x000000ce (n =   1)                       ( ) 1
 294         #0x000000d6 (n =   2)                   (*) 2
 295         #0x000000cf (n =   5)           (*) 3
 296         #0x000000d0 (n =   1)                       ( ) 5
 297         #0x000000d8 (n =   2)                   (*) 6
 298         #0x000000d1 (n =  12)   (*) 7
 299         #0x000000d2 (n =   1)                       ( ) 9
 300         #0x000000da (n =   2)                   (*) 10
 301         #0x000000d3 (n =   6)           (*) 11
 302         #0x000000d4 (n =   1)                       ( ) 13
 303         #0x000000dc (n =   3)                   (*) 14
 304         #0x000000d5 (n =   1)                       ( ) 15
 305 intersection
 306 tree dump, ht = 2
 307         #0x000000d7 (n =   1)           (*) 3
 308         #0x000000d9 (n =   4)   (*) 7
 309         #0x000000db (n =   1)               ( ) 11
 310         #0x000000dd (n =   2)           (*) 15
 311 a
 312 1 3 5 7 9 11 13 15
 313 b
 314 2 3 6 7 10 11 14 15
 315 difference
 316 tree dump, ht = 2
 317         #0x000000e6 (n =   2)           (*) 2
 318         #0x000000e8 (n =   1)               ( ) 6
 319         #0x000000ea (n =   4)   (*) 10
 320         #0x000000ec (n =   1)           (*) 14
 321 intersection
 322 tree dump, ht = 2
 323         #0x000000e7 (n =   1)           (*) 3
 324         #0x000000e9 (n =   4)   (*) 7
 325         #0x000000eb (n =   1)               ( ) 11
 326         #0x000000ed (n =   2)           (*) 15
 327 a original
 328 tree dump, ht = 2
 329         #0x000000de (n =   1)           (*) 1
 330         #0x000000df (n =   3)       ( ) 3
 331         #0x000000e0 (n =   1)           (*) 5
 332         #0x000000e1 (n =   8)   (*) 7
 333         #0x000000e2 (n =   1)           (*) 9
 334         #0x000000e3 (n =   4)       ( ) 11
 335         #0x000000e4 (n =   2)           (*) 13
 336         #0x000000e5 (n =   1)               ( ) 15
 337
 338 ;; clear everything.