chiark - git - mdw - xyla/blob - t/treap-treaptest.ref

   1 ;;;-------------------------------------------------------------------------
   2 ;;; Insertion and removal.
   3
   4 ;; Initial state.
   5 tree dump
   6         #0x00000000 (n =   1)               (*) 0xffe00000$ 110
   7         #0x00000002 (n =   3)           (*) 0xffd00002$ 120
   8         #0x00000001 (n =   1)               (*) 0xffe00001$ 130
   9         #0x00000006 (n =   7)       (*) 0xffc00006$ 140
  10         #0x00000003 (n =   1)               (*) 0xffe00003$ 150
  11         #0x00000005 (n =   3)           (*) 0xffd00005$ 160
  12         #0x00000004 (n =   1)               (*) 0xffe00004$ 170
  13         #0x0000000e (n =  15)   (*) 0xffb0000e$ 180
  14         #0x00000007 (n =   1)               (*) 0xffe00007$ 190
  15         #0x00000009 (n =   3)           (*) 0xffd00009$ 200
  16         #0x00000008 (n =   1)               (*) 0xffe00008$ 210
  17         #0x0000000d (n =   7)       (*) 0xffc0000d$ 220
  18         #0x0000000a (n =   1)               (*) 0xffe0000a$ 230
  19         #0x0000000c (n =   3)           (*) 0xffd0000c$ 240
  20         #0x0000000b (n =   1)               (*) 0xffe0000b$ 250
  21
  22 ;; Insertion.
  23 0xfff00000$ 155
  24 tree dump
  25         #0x0000000f (n =   1)               (*) 0xffe00000$ 110
  26         #0x00000011 (n =   3)           (*) 0xffd00002$ 120
  27         #0x00000010 (n =   1)               (*) 0xffe00001$ 130
  28         #0x00000015 (n =   8)       (*) 0xffc00006$ 140
  29         #0x00000012 (n =   2)               (*) 0xffe00003$ 150
  30         #0x0000001e (n =   1)                   (*) 0xfff00000$ 155
  31         #0x00000014 (n =   4)           (*) 0xffd00005$ 160
  32         #0x00000013 (n =   1)               (*) 0xffe00004$ 170
  33         #0x0000001d (n =  16)   (*) 0xffb0000e$ 180
  34         #0x00000016 (n =   1)               (*) 0xffe00007$ 190
  35         #0x00000018 (n =   3)           (*) 0xffd00009$ 200
  36         #0x00000017 (n =   1)               (*) 0xffe00008$ 210
  37         #0x0000001c (n =   7)       (*) 0xffc0000d$ 220
  38         #0x00000019 (n =   1)               (*) 0xffe0000a$ 230
  39         #0x0000001b (n =   3)           (*) 0xffd0000c$ 240
  40         #0x0000001a (n =   1)               (*) 0xffe0000b$ 250
  41 0xffd00000$ 155
  42 XYLA-TREAP INSERT right child
  43 XYLA-TREAP INSERT left child
  44 tree dump
  45         #0x0000001f (n =   1)               (*) 0xffe00000$ 110
  46         #0x00000021 (n =   3)           (*) 0xffd00002$ 120
  47         #0x00000020 (n =   1)               (*) 0xffe00001$ 130
  48         #0x00000025 (n =   8)       (*) 0xffc00006$ 140
  49         #0x00000022 (n =   1)               (*) 0xffe00003$ 150
  50         #0x0000002e (n =   4)           (*) 0xffd00000$ 155
  51         #0x00000024 (n =   2)               (*) 0xffd00005$ 160
  52         #0x00000023 (n =   1)                   (*) 0xffe00004$ 170
  53         #0x0000002d (n =  16)   (*) 0xffb0000e$ 180
  54         #0x00000026 (n =   1)               (*) 0xffe00007$ 190
  55         #0x00000028 (n =   3)           (*) 0xffd00009$ 200
  56         #0x00000027 (n =   1)               (*) 0xffe00008$ 210
  57         #0x0000002c (n =   7)       (*) 0xffc0000d$ 220
  58         #0x00000029 (n =   1)               (*) 0xffe0000a$ 230
  59         #0x0000002b (n =   3)           (*) 0xffd0000c$ 240
  60         #0x0000002a (n =   1)               (*) 0xffe0000b$ 250
  61 0xffa00000$ 155
  62 XYLA-TREAP INSERT right child
  63 XYLA-TREAP INSERT left child
  64 XYLA-TREAP INSERT right child
  65 XYLA-TREAP INSERT left child
  66 tree dump
  67         #0x0000002f (n =   1)               (*) 0xffe00000$ 110
  68         #0x00000031 (n =   3)           (*) 0xffd00002$ 120
  69         #0x00000030 (n =   1)               (*) 0xffe00001$ 130
  70         #0x00000035 (n =   5)       (*) 0xffc00006$ 140
  71         #0x00000032 (n =   1)           (*) 0xffe00003$ 150
  72         #0x0000003e (n =  16)   (*) 0xffa00000$ 155
  73         #0x00000034 (n =   2)           (*) 0xffd00005$ 160
  74         #0x00000033 (n =   1)               (*) 0xffe00004$ 170
  75         #0x0000003d (n =  10)       (*) 0xffb0000e$ 180
  76         #0x00000036 (n =   1)                   (*) 0xffe00007$ 190
  77         #0x00000038 (n =   3)               (*) 0xffd00009$ 200
  78         #0x00000037 (n =   1)                   (*) 0xffe00008$ 210
  79         #0x0000003c (n =   7)           (*) 0xffc0000d$ 220
  80         #0x00000039 (n =   1)                   (*) 0xffe0000a$ 230
  81         #0x0000003b (n =   3)               (*) 0xffd0000c$ 240
  82         #0x0000003a (n =   1)                   (*) 0xffe0000b$ 250
  83
  84 ;; Removal.
  85 170
  86 tree dump
  87         #0x0000003f (n =   1)               (*) 0xffe00000$ 110
  88         #0x00000041 (n =   3)           (*) 0xffd00002$ 120
  89         #0x00000040 (n =   1)               (*) 0xffe00001$ 130
  90         #0x00000045 (n =   6)       (*) 0xffc00006$ 140
  91         #0x00000042 (n =   1)               (*) 0xffe00003$ 150
  92         #0x00000044 (n =   2)           (*) 0xffd00005$ 160
  93         #0x0000004d (n =  14)   (*) 0xffb0000e$ 180
  94         #0x00000046 (n =   1)               (*) 0xffe00007$ 190
  95         #0x00000048 (n =   3)           (*) 0xffd00009$ 200
  96         #0x00000047 (n =   1)               (*) 0xffe00008$ 210
  97         #0x0000004c (n =   7)       (*) 0xffc0000d$ 220
  98         #0x00000049 (n =   1)               (*) 0xffe0000a$ 230
  99         #0x0000004b (n =   3)           (*) 0xffd0000c$ 240
 100         #0x0000004a (n =   1)               (*) 0xffe0000b$ 250
 101 220
 102 XYLA-TREAP REMOVE float left child
 103 XYLA-TREAP REMOVE float right child
 104 XYLA-TREAP REMOVE float left child
 105 tree dump
 106         #0x0000004e (n =   1)               (*) 0xffe00000$ 110
 107         #0x00000050 (n =   3)           (*) 0xffd00002$ 120
 108         #0x0000004f (n =   1)               (*) 0xffe00001$ 130
 109         #0x00000054 (n =   7)       (*) 0xffc00006$ 140
 110         #0x00000051 (n =   1)               (*) 0xffe00003$ 150
 111         #0x00000053 (n =   3)           (*) 0xffd00005$ 160
 112         #0x00000052 (n =   1)               (*) 0xffe00004$ 170
 113         #0x0000005c (n =  14)   (*) 0xffb0000e$ 180
 114         #0x00000055 (n =   1)           (*) 0xffe00007$ 190
 115         #0x00000057 (n =   6)       (*) 0xffd00009$ 200
 116         #0x00000056 (n =   2)               (*) 0xffe00008$ 210
 117         #0x00000058 (n =   1)                   (*) 0xffe0000a$ 230
 118         #0x0000005a (n =   4)           (*) 0xffd0000c$ 240
 119         #0x00000059 (n =   1)               (*) 0xffe0000b$ 250
 120 180
 121 XYLA-TREAP REMOVE float left child
 122 XYLA-TREAP REMOVE float right child
 123 XYLA-TREAP REMOVE float left child
 124 XYLA-TREAP REMOVE float right child
 125 XYLA-TREAP REMOVE float left child
 126 tree dump
 127         #0x0000005d (n =   1)           (*) 0xffe00000$ 110
 128         #0x0000005f (n =   3)       (*) 0xffd00002$ 120
 129         #0x0000005e (n =   1)           (*) 0xffe00001$ 130
 130         #0x00000063 (n =  14)   (*) 0xffc00006$ 140
 131         #0x00000060 (n =   1)               (*) 0xffe00003$ 150
 132         #0x00000062 (n =   6)           (*) 0xffd00005$ 160
 133         #0x00000061 (n =   2)                   (*) 0xffe00004$ 170
 134         #0x00000064 (n =   1)                       (*) 0xffe00007$ 190
 135         #0x00000066 (n =   4)               (*) 0xffd00009$ 200
 136         #0x00000065 (n =   1)                   (*) 0xffe00008$ 210
 137         #0x0000006a (n =  10)       (*) 0xffc0000d$ 220
 138         #0x00000067 (n =   1)               (*) 0xffe0000a$ 230
 139         #0x00000069 (n =   3)           (*) 0xffd0000c$ 240
 140         #0x00000068 (n =   1)               (*) 0xffe0000b$ 250
 141
 142 ;;;-------------------------------------------------------------------------
 143 ;;; Splitting and joining.
 144
 145 ;; With joining node.
 146 (#<link root -> node #0x0000007a 180> #<link node #0x0000007a 180 right -> node #0x00000079 220> #<link node #0x00000079 220 left -> node #0x00000075 200>)
 147 XYLA-TREAP SPLIT left child
 148 XYLA-TREAP SPLIT right child
 149 tree dump
 150         #0x00000074 (n =   1)       (*) 0xffe00008$ 210
 151         #0x00000079 (n =   5)   (*) 0xffc0000d$ 220
 152         #0x00000076 (n =   1)           (*) 0xffe0000a$ 230
 153         #0x00000078 (n =   3)       (*) 0xffd0000c$ 240
 154         #0x00000077 (n =   1)           (*) 0xffe0000b$ 250
 155 tree dump
 156         #0x00000075 (n =   1)   (*) 0xffd00009$ 200
 157 tree dump
 158         #0x0000006c (n =   1)               (*) 0xffe00000$ 110
 159         #0x0000006e (n =   3)           (*) 0xffd00002$ 120
 160         #0x0000006d (n =   1)               (*) 0xffe00001$ 130
 161         #0x00000072 (n =   7)       (*) 0xffc00006$ 140
 162         #0x0000006f (n =   1)               (*) 0xffe00003$ 150
 163         #0x00000071 (n =   3)           (*) 0xffd00005$ 160
 164         #0x00000070 (n =   1)               (*) 0xffe00004$ 170
 165         #0x0000007a (n =   9)   (*) 0xffb0000e$ 180
 166         #0x00000073 (n =   1)       (*) 0xffe00007$ 190
 167 0xfff00000$ 199
 168 XYLA-TREAP JOIN mid float left (next right)
 169 XYLA-TREAP JOIN mid float right (next left)
 170 XYLA-TREAP JOIN mid float left (next right)
 171 XYLA-TREAP JOIN mid float right (next done)
 172 tree dump
 173         #0x0000006c (n =   1)               (*) 0xffe00000$ 110
 174         #0x0000006e (n =   3)           (*) 0xffd00002$ 120
 175         #0x0000006d (n =   1)               (*) 0xffe00001$ 130
 176         #0x00000072 (n =   7)       (*) 0xffc00006$ 140
 177         #0x0000006f (n =   1)               (*) 0xffe00003$ 150
 178         #0x00000071 (n =   3)           (*) 0xffd00005$ 160
 179         #0x00000070 (n =   1)               (*) 0xffe00004$ 170
 180         #0x0000007a (n =  15)   (*) 0xffb0000e$ 180
 181         #0x00000073 (n =   3)           (*) 0xffe00007$ 190
 182         #0x0000007b (n =   1)                   (*) 0xfff00000$ 199
 183         #0x00000074 (n =   2)               (*) 0xffe00008$ 210
 184         #0x00000079 (n =   7)       (*) 0xffc0000d$ 220
 185         #0x00000076 (n =   1)               (*) 0xffe0000a$ 230
 186         #0x00000078 (n =   3)           (*) 0xffd0000c$ 240
 187         #0x00000077 (n =   1)               (*) 0xffe0000b$ 250
 188
 189 ;; Without joining node.
 190 (#<link root -> node #0x0000008a 180> #<link node #0x0000008a 180 right -> node #0x00000089 220> #<link node #0x00000089 220 left -> node #0x00000085 200> #<link node #0x00000085 200 left -> node #0x00000083 190> #<link node #0x00000083 190 right -> (nil)>)
 191 XYLA-TREAP SPLIT right child
 192 XYLA-TREAP SPLIT left child
 193 XYLA-TREAP SPLIT left child
 194 XYLA-TREAP SPLIT right child
 195 tree dump
 196         #0x00000085 (n =   2)       (*) 0xffd00009$ 200
 197         #0x00000084 (n =   1)           (*) 0xffe00008$ 210
 198         #0x00000089 (n =   6)   (*) 0xffc0000d$ 220
 199         #0x00000086 (n =   1)           (*) 0xffe0000a$ 230
 200         #0x00000088 (n =   3)       (*) 0xffd0000c$ 240
 201         #0x00000087 (n =   1)           (*) 0xffe0000b$ 250
 202 tree dump
 203         (tree empty)
 204 tree dump
 205         #0x0000007c (n =   1)               (*) 0xffe00000$ 110
 206         #0x0000007e (n =   3)           (*) 0xffd00002$ 120
 207         #0x0000007d (n =   1)               (*) 0xffe00001$ 130
 208         #0x00000082 (n =   7)       (*) 0xffc00006$ 140
 209         #0x0000007f (n =   1)               (*) 0xffe00003$ 150
 210         #0x00000081 (n =   3)           (*) 0xffd00005$ 160
 211         #0x00000080 (n =   1)               (*) 0xffe00004$ 170
 212         #0x0000008a (n =   9)   (*) 0xffb0000e$ 180
 213         #0x00000083 (n =   1)       (*) 0xffe00007$ 190
 214 (no key)
 215 XYLA-TREAP JOIN stitch right edge
 216 XYLA-TREAP JOIN stitch left edge
 217 tree dump
 218         #0x0000007c (n =   1)               (*) 0xffe00000$ 110
 219         #0x0000007e (n =   3)           (*) 0xffd00002$ 120
 220         #0x0000007d (n =   1)               (*) 0xffe00001$ 130
 221         #0x00000082 (n =   7)       (*) 0xffc00006$ 140
 222         #0x0000007f (n =   1)               (*) 0xffe00003$ 150
 223         #0x00000081 (n =   3)           (*) 0xffd00005$ 160
 224         #0x00000080 (n =   1)               (*) 0xffe00004$ 170
 225         #0x0000008a (n =  15)   (*) 0xffb0000e$ 180
 226         #0x00000083 (n =   1)               (*) 0xffe00007$ 190
 227         #0x00000085 (n =   3)           (*) 0xffd00009$ 200
 228         #0x00000084 (n =   1)               (*) 0xffe00008$ 210
 229         #0x00000089 (n =   7)       (*) 0xffc0000d$ 220
 230         #0x00000086 (n =   1)               (*) 0xffe0000a$ 230
 231         #0x00000088 (n =   3)           (*) 0xffd0000c$ 240
 232         #0x00000087 (n =   1)               (*) 0xffe0000b$ 250
 233
 234 ;;;----- That's all, folks -------------------------------------------------