silo/masstree/doc/remove1.mp

   1 input masstree;
   2 verbatimtex %&latex
   3 \documentclass[12pt]{article}
   4 \usepackage{elemfig,amsmath}
   5 \begin{document}
   6 \newcommand{\xlab}[1]{\mlabel{\textsc{#1}}}
   7 etex;
   8
   9 picture data[];
  10 data[0] = btex \xlab{a} etex; data[1] = btex \xlab{b} etex; data[2] = btex \xlab{c} etex;
  11 data[3] = btex \xlab{d} etex; data[4] = btex \xlab{e} etex; data[5] = btex \xlab{f} etex;
  12 data[6] = btex \xlab{g} etex; data[7] = btex \xlab{h} etex; data[8] = btex \xlab{i} etex;
  13 data[9] = btex \xlab{j} etex; data[10] = btex \xlab{k} etex; data[11] = btex \xlab{l} etex;
  14 data[12] = btex \xlab{m} etex; data[13] = btex \xlab{n} etex; data[14] = btex \xlab{o} etex;
  15
  16 pair min_reasonable_cell; min_reasonable_cell := (0,0);
  17 for _i_ = 0 upto 14:
  18   min_reasonable_cell :=
  19     (max(xpart min_reasonable_cell, xpart (urcorner data[_i_] - llcorner data[_i_])),
  20       max(ypart min_reasonable_cell, ypart (urcorner data[_i_] - llcorner data[_i_])));
  21 endfor;
  22 color deletedelement; deletedelement = .5white;
  23
  24 picture emptyqueue; emptyqueue := btex \phantom{\elementlabel{Queue}} etex;
  25 picture vemptyqueue; vemptyqueue := emptyqueue rotated 90 xscaled .4;
  26 hardborderscale = 3;
  27
  28 beginfig(1);
  29   % initial tree
  30   boxjoin(b.w - a.e = (20,0));
  31   leafit.a(data[0], data[1], data[2]);
  32   leafit.d(data[3], data[4], data[5]);
  33   leafit.g(data[6], data[7], data[8]);
  34   leafit.j(data[9], data[10], data[11]);
  35   leafit.m(data[12], data[13], data[14]);
  36   boxjoin();
  37   internalnodeit.ina(data[3], data[6], nullpicture);
  38   internalnodeit.inj(data[12], nullpicture, nullpicture);
  39   internalnodeit.root(data[9], nullpicture, nullpicture);
  40   ina.s = .5[a.nw,g.ne] + (0,24);
  41   inj.s = .5[j.nw,m.ne] + (0,24);
  42   root.s = .5[ina.nw,inj.ne] + (0,24);
  43   fixelement(a,d,g,j,m);
  44   fixelement(root,ina,inj);
  45   leafconnect(a,d,g,j,m);
  46   drawelement(a,d,g,j,m,ina,inj,root);
  47   internalnodeconnect(ina,a,d,g);
  48   internalnodeconnect(inj,j,m);
  49   internalnodeconnect(root,ina,inj);
  50 endfig;
  51
  52 beginfig(2);
  53   % delete element E
  54   boxjoin(b.w - a.e = (20,0));
  55   leafit.a(data[0], data[1], data[2]);
  56   leafit.d(data[3], data[4], data[5]);
  57   d.locked = true;
  58   leafit.g(data[6], data[7], data[8]);
  59   leafit.j(data[9], data[10], data[11]);
  60   leafit.m(data[12], data[13], data[14]);
  61   boxjoin();
  62   internalnodeit.ina(data[3], data[6], nullpicture);
  63   internalnodeit.inj(data[12], nullpicture, nullpicture);
  64   internalnodeit.root(data[9], nullpicture, nullpicture);
  65   ina.s = .5[a.nw,g.ne] + (0,24);
  66   inj.s = .5[j.nw,m.ne] + (0,24);
  67   root.s = .5[ina.nw,inj.ne] + (0,24);
  68   fixelement(a,d,g,j,m);
  69   fixelement(root,ina,inj);
  70   fill nodecellbpath(d,1) withcolor deletedelement;
  71   leafconnect(a,d,g,j,m);
  72   drawelement(a,d,g,j,m,ina,inj,root);
  73   internalnodeconnect(ina,a,d,g);
  74   internalnodeconnect(inj,j,m);
  75   internalnodeconnect(root,ina,inj);
  76 endfig;
  77
  78 beginfig(3);
  79   % delete node DEF: poison next pointer
  80   boxjoin(b.w - a.e = (20,0));
  81   leafit.a(data[0], data[1], data[2]);
  82   leafit.d(data[3], data[4], data[5]);
  83   d.locked = d.deleted = true;
  84   leafit.g(data[6], data[7], data[8]);
  85   leafit.j(data[9], data[10], data[11]);
  86   leafit.m(data[12], data[13], data[14]);
  87   boxjoin();
  88   internalnodeit.ina(data[3], data[6], nullpicture);
  89   internalnodeit.inj(data[12], nullpicture, nullpicture);
  90   internalnodeit.root(data[9], nullpicture, nullpicture);
  91   ina.s = .5[a.nw,g.ne] + (0,24);
  92   inj.s = .5[j.nw,m.ne] + (0,24);
  93   root.s = .5[ina.nw,inj.ne] + (0,24);
  94   fixelement(a,d,g,j,m);
  95   fixelement(root,ina,inj);
  96   fill nodecellsbpath(d,0,2) withcolor deletedelement;
  97   fill leafnextbpath(d) withcolor black;
  98   leafconnect(a,d,g,j,m);
  99   drawelement(a,d,g,j,m,ina,inj,root);
 100   internalnodeconnect(ina,a,d,g);
 101   internalnodeconnect(inj,j,m);
 102   internalnodeconnect(root,ina,inj);
 103 endfig;
 104
 105 beginfig(31);
 106   % delete node DEF: poison ABC's next pointer
 107   boxjoin(b.w - a.e = (20,0));
 108   leafit.a(data[0], data[1], data[2]);
 109   leafit.d(data[3], data[4], data[5]);
 110   d.locked = d.deleted = true;
 111   leafit.g(data[6], data[7], data[8]);
 112   leafit.j(data[9], data[10], data[11]);
 113   leafit.m(data[12], data[13], data[14]);
 114   boxjoin();
 115   internalnodeit.ina(data[3], data[6], nullpicture);
 116   internalnodeit.inj(data[12], nullpicture, nullpicture);
 117   internalnodeit.root(data[9], nullpicture, nullpicture);
 118   ina.s = .5[a.nw,g.ne] + (0,24);
 119   inj.s = .5[j.nw,m.ne] + (0,24);
 120   root.s = .5[ina.nw,inj.ne] + (0,24);
 121   fixelement(a,d,g,j,m);
 122   fixelement(root,ina,inj);
 123   fill nodecellsbpath(d,0,2) withcolor deletedelement;
 124   fill leafnextbpath(d) withcolor black;
 125   fill leafnextbpath(a) withcolor black;
 126   leafconnect(a,d,g,j,m);
 127   drawelement(a,d,g,j,m,ina,inj,root);
 128   internalnodeconnect(ina,a,d,g);
 129   internalnodeconnect(inj,j,m);
 130   internalnodeconnect(root,ina,inj);
 131 endfig;
 132
 133 beginfig(4);
 134   % delete node DEF: adjust GHI.prev
 135   boxjoin(b.w - a.e = (20,0));
 136   leafit.a(data[0], data[1], data[2]);
 137   leafit.d(data[3], data[4], data[5]);
 138   d.locked = d.deleted = true;
 139   leafit.g(data[6], data[7], data[8]);
 140   leafit.j(data[9], data[10], data[11]);
 141   leafit.m(data[12], data[13], data[14]);
 142   boxjoin();
 143   internalnodeit.ina(data[3], data[6], nullpicture);
 144   internalnodeit.inj(data[12], nullpicture, nullpicture);
 145   internalnodeit.root(data[9], nullpicture, nullpicture);
 146   ina.s = .5[a.nw,g.ne] + (0,24);
 147   inj.s = .5[j.nw,m.ne] + (0,24);
 148   root.s = .5[ina.nw,inj.ne] + (0,24);
 149   fixelement(a,d,g,j,m);
 150   fixelement(root,ina,inj);
 151   fill nodecellsbpath(d,0,2) withcolor deletedelement;
 152   fill leafnextbpath(d) withcolor black;
 153   fill leafnextbpath(a) withcolor black;
 154   leafconnect(a,d);
 155   leafconnect(g,j,m);
 156   g.prevpath = g.prev .. (d.se - (0,3)) .. tension 1.5 .. (d.sw - (0,3)) .. (a.previn - (0,1));
 157   d.nextpath = d.next -- g.nextin;
 158   drawelement(a,d,g,j,m,ina,inj,root);
 159   internalnodeconnect(ina,a,d,g);
 160   internalnodeconnect(inj,j,m);
 161   internalnodeconnect(root,ina,inj);
 162 endfig;
 163
 164 beginfig(5);
 165   % delete node DEF: adjust ABC.next
 166   boxjoin(b.w - a.e = (20,0));
 167   leafit.a(data[0], data[1], data[2]);
 168   leafit.d(data[3], data[4], data[5]);
 169   d.locked = d.deleted = true;
 170   leafit.g(data[6], data[7], data[8]);
 171   leafit.j(data[9], data[10], data[11]);
 172   leafit.m(data[12], data[13], data[14]);
 173   boxjoin();
 174   internalnodeit.ina(data[3], data[6], nullpicture);
 175   internalnodeit.inj(data[12], nullpicture, nullpicture);
 176   internalnodeit.root(data[9], nullpicture, nullpicture);
 177   ina.s = .5[a.nw,g.ne] + (0,24);
 178   inj.s = .5[j.nw,m.ne] + (0,24);
 179   root.s = .5[ina.nw,inj.ne] + (0,24);
 180   fixelement(a,d,g,j,m);
 181   fixelement(root,ina,inj);
 182   fill nodecellsbpath(d,0,2) withcolor deletedelement;
 183   fill leafnextbpath(d) withcolor black;
 184   leafconnect(g,j,m);
 185   a.nextpath = a.next .. (d.nw + (0,3)) .. tension 1.5 .. (d.ne + (0,3)) .. (g.nextin + (0,1));
 186   d.prevpath = d.prev -- a.previn;
 187   d.nextpath = d.next -- g.nextin;
 188   g.prevpath = g.prev .. (d.se - (0,3)) .. tension 1.5 .. (d.sw - (0,3)) .. (a.previn - (0,1));
 189   drawelement(a,d,g,j,m,ina,inj,root);
 190   internalnodeconnect(ina,a,d,g);
 191   internalnodeconnect(inj,j,m);
 192   internalnodeconnect(root,ina,inj);
 193 endfig;
 194
 195 beginfig(6);
 196   % delete node DEF: adjust internal node
 197   boxjoin(b.w - a.e = (20,0));
 198   leafit.a(data[0], data[1], data[2]);
 199   leafit.d(data[3], data[4], data[5]);
 200   d.deleted = true;
 201   leafit.g(data[6], data[7], data[8]);
 202   leafit.j(data[9], data[10], data[11]);
 203   leafit.m(data[12], data[13], data[14]);
 204   boxjoin();
 205   internalnodeit.ina(data[6], nullpicture, nullpicture);
 206   ina.locked = true;
 207   internalnodeit.inj(data[12], nullpicture, nullpicture);
 208   internalnodeit.root(data[9], nullpicture, nullpicture);
 209   ina.s = .5[a.nw,g.ne] + (0,24);
 210   inj.s = .5[j.nw,m.ne] + (0,24);
 211   root.s = .5[ina.nw,inj.ne] + (0,24);
 212   fixelement(a,d,g,j,m);
 213   fixelement(root,ina,inj);
 214   fill nodecellsbpath(d,0,2) withcolor deletedelement;
 215   fill leafnextbpath(d) withcolor black;
 216   leafconnect(g,j,m);
 217   a.nextpath = a.next .. (d.nw + (0,3)) .. tension 1.5 .. (d.ne + (0,3)) .. (g.nextin + (0,1));
 218   d.prevpath = d.prev -- a.previn;
 219   d.nextpath = d.next -- g.nextin;
 220   g.prevpath = g.prev .. (d.se - (0,3)) .. tension 1.5 .. (d.sw - (0,3)) .. (a.previn - (0,1));
 221   drawelement(a,d,g,j,m,ina,inj,root);
 222   internalnodeconnect(ina,a,g);
 223   internalnodeconnect(inj,j,m);
 224   internalnodeconnect(root,ina,inj);
 225 endfig;
 226
 227 beginfig(7);
 228   % delete node GHI: after leaf unlink
 229   boxjoin(b.w - a.e = (20,0));
 230   leafit.a(data[0], data[1], data[2]);
 231   leafit.d(data[3], data[4], data[5]);
 232   d.deleted = true;
 233   leafit.g(data[6], data[7], data[8]);
 234   g.locked = g.deleted = true;
 235   leafit.j(data[9], data[10], data[11]);
 236   leafit.m(data[12], data[13], data[14]);
 237   boxjoin();
 238   internalnodeit.ina(data[6], nullpicture, nullpicture);
 239   internalnodeit.inj(data[12], nullpicture, nullpicture);
 240   internalnodeit.root(data[9], nullpicture, nullpicture);
 241   ina.s = .5[a.nw,g.ne] + (0,24);
 242   inj.s = .5[j.nw,m.ne] + (0,24);
 243   root.s = .5[ina.nw,inj.ne] + (0,24);
 244   fixelement(a,d,g,j,m);
 245   fixelement(root,ina,inj);
 246   fill nodecellsbpath(g,0,2) withcolor deletedelement;
 247   fill leafnextbpath(g) withcolor black;
 248   leafconnect(j,m);
 249   a.nextpath = a.next .. (g.nw + (0,3)) .. tension 1.5 .. (g.ne + (0,3)) .. (j.nextin + (0,1));
 250   g.prevpath = g.prev -- a.previn;
 251   g.nextpath = g.next -- j.nextin;
 252   j.prevpath = j.prev .. (g.se - (0,3)) .. tension 1.5 .. (g.sw - (0,3)) .. (a.previn - (0,2));
 253   drawelement(a,g,j,m,ina,inj,root);
 254   internalnodeconnect(ina,a,g);
 255   internalnodeconnect(inj,j,m);
 256   internalnodeconnect(root,ina,inj);
 257 endfig;
 258
 259 beginfig(8);
 260   % delete node GHI: after internal node
 261   boxjoin(b.w - a.e = (20,0));
 262   leafit.a(data[0], data[1], data[2]);
 263   leafit.d(data[3], data[4], data[5]);
 264   d.deleted = true;
 265   leafit.g(data[6], data[7], data[8]);
 266   g.deleted = true;
 267   leafit.j(data[9], data[10], data[11]);
 268   leafit.m(data[12], data[13], data[14]);
 269   boxjoin();
 270   internalnodeit.ina(nullpicture, nullpicture, nullpicture);
 271   ina.locked = true;
 272   internalnodeit.inj(data[12], nullpicture, nullpicture);
 273   internalnodeit.root(data[9], nullpicture, nullpicture);
 274   ina.s = .5[a.nw,g.ne] + (0,24);
 275   inj.s = .5[j.nw,m.ne] + (0,24);
 276   root.s = .5[ina.nw,inj.ne] + (0,24);
 277   fixelement(a,d,g,j,m);
 278   fixelement(root,ina,inj);
 279   fill nodecellsbpath(g,0,2) withcolor deletedelement;
 280   fill leafnextbpath(g) withcolor black;
 281   leafconnect(j,m);
 282   a.nextpath = a.next .. (g.nw + (0,3)) .. tension 1.5 .. (g.ne + (0,3)) .. (j.nextin + (0,1));
 283   g.prevpath = g.prev -- a.previn;
 284   g.nextpath = g.next -- j.nextin;
 285   j.prevpath = j.prev .. (g.se - (0,3)) .. tension 1.5 .. (g.sw - (0,3)) .. (a.previn - (0,2));
 286   drawelement(a,g,j,m,ina,inj,root);
 287   internalnodeconnect(ina,a);
 288   internalnodeconnect(inj,j,m);
 289   internalnodeconnect(root,ina,inj);
 290 endfig;
 291
 292 beginfig(9);
 293   % delete node GHI: after collapse
 294   boxjoin(b.w - a.e = (20,0));
 295   leafit.a(data[0], data[1], data[2]);
 296   leafit.d(data[3], data[4], data[5]);
 297   d.deleted = true;
 298   leafit.g(data[6], data[7], data[8]);
 299   g.deleted = true;
 300   leafit.j(data[9], data[10], data[11]);
 301   leafit.m(data[12], data[13], data[14]);
 302   boxjoin();
 303   internalnodeit.ina(nullpicture, nullpicture, nullpicture);
 304   ina.deleted = true;
 305   internalnodeit.inj(data[12], nullpicture, nullpicture);
 306   internalnodeit.root(data[9], nullpicture, nullpicture);
 307   root.locked = true;
 308   ina.s = .5[a.nw,g.ne] + (0,24);
 309   inj.s = .5[j.nw,m.ne] + (0,24);
 310   root.s = .5[ina.nw,inj.ne] + (0,24);
 311   fixelement(a,d,g,j,m);
 312   fixelement(root,ina,inj);
 313   fill nodecellsbpath(g,0,2) withcolor deletedelement;
 314   fill leafnextbpath(g) withcolor black;
 315   leafconnect(j,m);
 316   a.nextpath = a.next .. (g.nw + (0,3)) .. tension 1.5 .. (g.ne + (0,3)) .. (j.nextin + (0,1));
 317   g.prevpath = g.prev -- a.previn;
 318   g.nextpath = g.next -- j.nextin;
 319   j.prevpath = j.prev .. (g.se - (0,3)) .. tension 1.5 .. (g.sw - (0,3)) .. (a.previn - (0,2));
 320   drawelement(a,g,j,m,ina,inj,root);
 321   internalnodeconnect(inj,j,m);
 322   drawconnarrow ina.child[0] {down} .. tension 4 .. {down} (a.n + (3,0));
 323   drawconnarrow root.child[0] {down} .. tension 2 and 1 .. (ina.nw + (0,4)) .. {down} a.n;
 324   internalnodeconnectone(root,inj,1);
 325 endfig;
 326
 327 end