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

   1 ;; insertion
   2 5 6 7 8 9 10 11
   3 1 2 3 4 5 6 7 8 9 10 11
   4
   5 ;; initial population for upcoming tests
   6 1 2 3 4 5 6 7 8 9
   7
   8 ;; lookup
   9 #<node #0x0000000f 5>
  10 (nil)
  11 #<node #0x0000000f 5>
  12 (nil)
  13
  14 ;; iteration
  15 1 2 3 4 5 6 7 8 9
  16 9 8 7 6 5 4 3 2 1
  17
  18 ;; path motion and ascension
  19 (#<link root -> node #0x0000001c 4> #<link node #0x0000001c 4 left -> node #0x00000016 3> #<link node #0x00000016 3 left -> node #0x00000015 1>)
  20 1
  21 0
  22 (#<link root -> node #0x0000001c 4> #<link node #0x0000001c 4 left -> node #0x00000016 3> #<link node #0x00000016 3 left -> node #0x00000015 1> #<link node #0x00000015 1 right -> node #0x00000014 2>)
  23 2
  24 1
  25 (#<link root -> node #0x0000001c 4> #<link node #0x0000001c 4 left -> node #0x00000016 3>)
  26 3
  27 2
  28 (#<link root -> node #0x0000001c 4>)
  29 4
  30 3
  31 (#<link root -> node #0x00000016 3> #<link node #0x00000016 3 right -> node #0x0000001b 8> #<link node #0x0000001b 8 right -> node #0x0000001a 9>)
  32 9
  33 7
  34 (#<link root -> node #0x00000016 3> #<link node #0x00000016 3 right -> node #0x0000001b 8>)
  35 8
  36 6
  37 (#<link root -> node #0x00000016 3> #<link node #0x00000016 3 right -> node #0x0000001b 8> #<link node #0x0000001b 8 left -> node #0x00000019 6> #<link node #0x00000019 6 right -> node #0x00000018 7>)
  38 7
  39 5
  40 (#<link root -> node #0x00000016 3> #<link node #0x00000016 3 right -> node #0x0000001b 8> #<link node #0x0000001b 8 left -> node #0x00000019 6> #<link node #0x00000019 6 left -> node #0x00000017 5>)
  41 3
  42 (#<link root -> node #0x00000016 3>)
  43 3
  44 2
  45 (#<link root -> node #0x00000016 3> #<link node #0x00000016 3 right -> node #0x0000001b 8> #<link node #0x0000001b 8 left -> node #0x00000019 6> #<link node #0x00000019 6 left -> node #0x00000017 5> #<link node #0x00000017 5 left -> (nil)>)
  46 3
  47 (#<link root -> node #0x00000016 3>)
  48 2
  49 (#<link root -> node #0x00000016 3> #<link node #0x00000016 3 right -> node #0x0000001b 8> #<link node #0x0000001b 8 left -> node #0x00000019 6> #<link node #0x00000019 6 left -> node #0x00000017 5> #<link node #0x00000017 5 left -> (nil)>)
  50 3
  51 (#<link root -> node #0x00000016 3> #<link node #0x00000016 3 right -> node #0x0000001b 8> #<link node #0x0000001b 8 left -> node #0x00000019 6> #<link node #0x00000019 6 left -> node #0x00000017 5> #<link node #0x00000017 5 left -> (nil)>)
  52 3
  53 (#<link root -> node #0x00000016 3> #<link node #0x00000016 3 right -> node #0x0000001b 8> #<link node #0x0000001b 8 left -> node #0x00000019 6> #<link node #0x00000019 6 left -> node #0x00000017 5>)
  54 3
  55 (#<link root -> node #0x00000016 3> #<link node #0x00000016 3 right -> node #0x0000001b 8> #<link node #0x0000001b 8 left -> node #0x00000019 6> #<link node #0x00000019 6 left -> node #0x00000017 5> #<link node #0x00000017 5 left -> (nil)>)
  56 3
  57 (#<link root -> node #0x00000016 3> #<link node #0x00000016 3 left -> node #0x00000015 1> #<link node #0x00000015 1 left -> (nil)>)
  58 0
  59 (#<link root -> node #0x00000016 3> #<link node #0x00000016 3 left -> node #0x00000015 1>)
  60 0
  61 (#<link root -> node #0x00000016 3> #<link node #0x00000016 3 right -> node #0x0000001b 8> #<link node #0x0000001b 8 right -> node #0x0000001a 9> #<link node #0x0000001a 9 right -> (nil)>)
  62 8
  63 (#<link root -> node #0x00000016 3> #<link node #0x00000016 3 right -> node #0x0000001b 8> #<link node #0x0000001b 8 right -> node #0x0000001a 9>)
  64 7
  65 (#<link root -> node #0x00000016 3> #<link node #0x00000016 3 right -> node #0x0000001b 8> #<link node #0x0000001b 8 left -> node #0x00000019 6> #<link node #0x00000019 6 right -> node #0x00000018 7> #<link node #0x00000018 7 left -> (nil)>)
  66 left
  67 #<node #0x00000018 7>
  68 right
  69 #<node #0x00000019 6>
  70 left
  71 #<node #0x0000001b 8>
  72 right
  73 #<node #0x00000016 3>
  74 root
  75 (nil)
  76 (#<link root -> node #0x00000016 3>)
  77 2
  78 root
  79 (#<link root -> node #0x00000016 3>)
  80 (#<link root -> (nil)>)
  81 0
  82 (#<link root -> (nil)>)
  83 0
  84 (#<link root -> node #0x0000001d 1>)
  85 0
  86 (#<link root -> node #0x0000001d 1>)
  87 0
  88
  89 ;; remove
  90 7
  91 6
  92 4
  93 1
  94 5
  95 2
  96 3
  97 8
  98 9
  99 (empty tree)
 100
 101 ;; join
 102 11 12 13
 103 (no key)
 104 1 2 3 4 5 6 7 8 9 11 12 13
 105 11 12 13
 106 10
 107 1 2 3 4 5 6 7 8 9 10 11 12 13
 108 11
 109 10
 110 1 2 3 4 5 6 7 8 9 10 11
 111 (empty tree)
 112 10
 113 1 2 3 4 5 6 7 8 9 10
 114 (empty tree)
 115 (no key)
 116 1 2 3 4 5 6 7 8 9
 117 11 12 13 14 15 16 17 18 19 20
 118 10
 119 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
 120
 121 ;; split
 122 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
 123 (#<link root -> node #0x000000af 31> #<link node #0x000000af 31 left -> node #0x000000ae 16> #<link node #0x000000ae 16 right -> node #0x000000ad 21> #<link node #0x000000ad 21 left -> node #0x000000a3 18>)
 124 19 20 21 22 23 24 25 26 27 28 29 30 31
 125 18
 126 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
 127 (#<link root -> node #0x000000ce 31> #<link node #0x000000ce 31 left -> node #0x000000cd 16> #<link node #0x000000cd 16 right -> node #0x000000cc 21> #<link node #0x000000cc 21 left -> node #0x000000c2 18> #<link node #0x000000c2 18 left -> node #0x000000bf 17> #<link node #0x000000bf 17 right -> (nil)>)
 128 18 19 20 21 22 23 24 25 26 27 28 29 30 31
 129 (empty tree)
 130 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
 131 (#<link root -> node #0x000000ed 31> #<link node #0x000000ed 31 left -> node #0x000000ec 16> #<link node #0x000000ec 16 right -> node #0x000000eb 21> #<link node #0x000000eb 21 left -> node #0x000000e1 18> #<link node #0x000000e1 18 right -> node #0x000000e0 20> #<link node #0x000000e0 20 left -> node #0x000000df 19> #<link node #0x000000df 19 left -> (nil)>)
 132 19 20 21 22 23 24 25 26 27 28 29 30 31
 133 (empty tree)
 134 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
 135 17
 136 (#<link root -> node #0x0000010c 31> #<link node #0x0000010c 31 left -> node #0x0000010b 16> #<link node #0x0000010b 16 right -> node #0x0000010a 21> #<link node #0x0000010a 21 left -> node #0x00000100 18> #<link node #0x00000100 18 left -> (nil)>)
 137 18 19 20 21 22 23 24 25 26 27 28 29 30 31
 138 (empty tree)
 139 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
 140 19
 141 (#<link root -> node #0x0000012b 31> #<link node #0x0000012b 31 left -> node #0x0000012a 16> #<link node #0x0000012a 16 right -> node #0x00000129 21> #<link node #0x00000129 21 left -> node #0x0000011f 18> #<link node #0x0000011f 18 right -> node #0x0000011e 20> #<link node #0x0000011e 20 left -> (nil)>)
 142 20 21 22 23 24 25 26 27 28 29 30 31
 143 (empty tree)
 144 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
 145
 146 ;; set ops
 147 1 3 5 7 9 11 13 15
 148 2 3 6 7 10 11 14 15
 149 union
 150 1 2 3 5 6 7 9 10 11 13 14 15
 151 intersection
 152 3 7 11 15
 153 a
 154 1 3 5 7 9 11 13 15
 155 b
 156 2 3 6 7 10 11 14 15
 157 difference
 158 2 6 10 14
 159 intersection
 160 3 7 11 15
 161 a original
 162 1 3 5 7 9 11 13 15
 163
 164 ;; clear everything.
 165
 166 ;;;----- That's all, folks -------------------------------------------------