silo/masstree/doc/remove2.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 picture dotdata;
  16 dotdata = btex \xlab{\dots\dots} etex;
  17
  18 pair min_reasonable_cell; min_reasonable_cell := (0,0);
  19 for _i_ = 0 upto 14:
  20   min_reasonable_cell :=
  21     (max(xpart min_reasonable_cell, xpart (urcorner data[_i_] - llcorner data[_i_])),
  22       max(ypart min_reasonable_cell, ypart (urcorner data[_i_] - llcorner data[_i_])));
  23 endfor;
  24 color deletedelement; deletedelement = .5white;
  25 color upperlayer, upperlayerfill; upperlayer = (0,0,.5); upperlayerfill = (.9,.9,1);
  26
  27 picture emptyqueue; emptyqueue := btex \phantom{\elementlabel{Queue}} etex;
  28 picture vemptyqueue; vemptyqueue := emptyqueue rotated 90 xscaled .4;
  29 hardborderscale = 3;
  30
  31 beginfig(1);
  32   % tree with JKL removed
  33   boxjoin(b.w - a.e = (20,0));
  34   leafit.a(data[0], data[1], data[2]);
  35   leafit.d(data[3], data[4], data[5]);
  36   leafit.g(data[6], data[7], data[8]);
  37   leafit.j(data[9], data[10], data[11]);
  38   j.locked = j.deleted = true;
  39   leafit.m(data[12], data[13], data[14]);
  40   boxjoin();
  41   internalnodeit.ina(data[3], data[6], nullpicture);
  42   internalnodeit.inj(data[12], nullpicture, nullpicture);
  43   internalnodeit.root(data[9], nullpicture, nullpicture);
  44   ina.s = .5[a.nw,g.ne] + (0,24);
  45   inj.s = .5[j.nw,m.ne] + (0,24);
  46   root.s = .5[ina.nw,inj.ne] + (0,24);
  47   fixelement(a,d,g,j,m);
  48   fixelement(root,ina,inj);
  49   leafconnect(a,d,g);
  50   fill nodecellsbpath(j,0,2) withcolor deletedelement;
  51   fill leafnextbpath(j) withcolor black;
  52   g.nextpath = g.next .. (j.nw + (0,3)) .. tension 1.5 .. (j.ne + (0,3)) .. (m.nextin + (0,1));
  53   j.prevpath = j.prev -- g.previn;
  54   j.nextpath = j.next -- m.nextin;
  55   m.prevpath = m.prev .. (j.se - (0,3)) .. tension 1.5 .. (j.sw - (0,3)) .. (g.previn - (0,1));
  56   drawelement(a,d,g,j,m,ina,inj,root);
  57   internalnodeconnect(ina,a,d,g);
  58   internalnodeconnect(inj,j,m);
  59   internalnodeconnect(root,ina,inj);
  60 endfig;
  61
  62 beginfig(2);
  63   % bad idea: tree with M in internal node removed
  64   boxjoin(b.w - a.e = (20,0));
  65   leafit.a(data[0], data[1], data[2]);
  66   leafit.d(data[3], data[4], data[5]);
  67   leafit.g(data[6], data[7], data[8]);
  68   leafit.j(data[9], data[10], data[11]);
  69   j.deleted = true;
  70   leafit.m(data[12], data[13], data[14]);
  71   boxjoin();
  72   internalnodeit.ina(data[3], data[6], nullpicture);
  73   internalnodeit.inj(nullpicture, nullpicture, nullpicture);
  74   inj.locked = true;
  75   internalnodeit.root(data[9], nullpicture, nullpicture);
  76   ina.s = .5[a.nw,g.ne] + (0,24);
  77   inj.s = .5[j.nw,m.ne] + (0,24);
  78   root.s = .5[ina.nw,inj.ne] + (0,24);
  79   fixelement(a,d,g,j,m);
  80   fixelement(root,ina,inj);
  81   leafconnect(a,d,g);
  82   fill nodecellsbpath(j,0,2) withcolor deletedelement;
  83   fill leafnextbpath(j) withcolor black;
  84   g.nextpath = g.next .. (j.nw + (0,3)) .. tension 1.5 .. (j.ne + (0,3)) .. (m.nextin + (0,1));
  85   j.prevpath = j.prev -- g.previn;
  86   j.nextpath = j.next -- m.nextin;
  87   m.prevpath = m.prev .. (j.se - (0,3)) .. tension 1.5 .. (j.sw - (0,3)) .. (g.previn - (0,1));
  88   drawelement(a,d,g,j,m,ina,inj,root);
  89   internalnodeconnect(ina,a,d,g);
  90   internalnodeconnect(inj,m);
  91   internalnodeconnect(root,ina,inj);
  92   label.rt(btex \textsf{\textbf{~~XXX}} etex, inj.e);
  93 endfig;
  94
  95 beginfig(3);
  96   % tree with M stubbed out
  97   boxjoin(b.w - a.e = (20,0));
  98   leafit.a(data[0], data[1], data[2]);
  99   leafit.d(data[3], data[4], data[5]);
 100   leafit.g(data[6], data[7], data[8]);
 101   leafit.j(data[9], data[10], data[11]);
 102   j.deleted = true;
 103   leafit.m(data[12], data[13], data[14]);
 104   boxjoin();
 105   internalnodeit.ina(data[3], data[6], nullpicture);
 106   internalnodeit.inj(data[12], nullpicture, nullpicture);
 107   inj.locked = true;
 108   internalnodeit.root(data[9], nullpicture, nullpicture);
 109   ina.s = .5[a.nw,g.ne] + (0,24);
 110   inj.s = .5[j.nw,m.ne] + (0,24);
 111   root.s = .5[ina.nw,inj.ne] + (0,24);
 112   fixelement(a,d,g,j,m);
 113   fixelement(root,ina,inj);
 114   leafconnect(a,d,g);
 115   fill nodecellsbpath(j,0,2) withcolor deletedelement;
 116   fill leafnextbpath(j) withcolor black;
 117   g.nextpath = g.next .. (j.nw + (0,3)) .. tension 1.5 .. (j.ne + (0,3)) .. (m.nextin + (0,1));
 118   j.prevpath = j.prev -- g.previn;
 119   j.nextpath = j.next -- m.nextin;
 120   m.prevpath = m.prev .. (j.se - (0,3)) .. tension 1.5 .. (j.sw - (0,3)) .. (g.previn - (0,1));
 121   drawelement(a,d,g,j,m,ina,inj,root);
 122   internalnodeconnect(ina,a,d,g);
 123   internalnodeconnectone(inj,m,1);
 124   drawterminationarrow(inj.child[0] -- (inj.child[0] - (0,5)));
 125   internalnodeconnect(root,ina,inj);
 126 endfig;
 127
 128 beginfig(4);
 129   % tree with M replacing J at the root
 130   boxjoin(b.w - a.e = (20,0));
 131   leafit.a(data[0], data[1], data[2]);
 132   leafit.d(data[3], data[4], data[5]);
 133   leafit.g(data[6], data[7], data[8]);
 134   leafit.j(data[9], data[10], data[11]);
 135   j.deleted = true;
 136   leafit.m(data[12], data[13], data[14]);
 137   boxjoin();
 138   internalnodeit.ina(data[3], data[6], nullpicture);
 139   internalnodeit.inj(data[12], nullpicture, nullpicture);
 140   internalnodeit.root(data[12], nullpicture, nullpicture);
 141   root.locked = true;
 142   ina.s = .5[a.nw,g.ne] + (0,24);
 143   inj.s = .5[j.nw,m.ne] + (0,24);
 144   root.s = .5[ina.nw,inj.ne] + (0,24);
 145   fixelement(a,d,g,j,m);
 146   fixelement(root,ina,inj);
 147   leafconnect(a,d,g);
 148   fill nodecellsbpath(j,0,2) withcolor deletedelement;
 149   fill leafnextbpath(j) withcolor black;
 150   g.nextpath = g.next .. (j.nw + (0,3)) .. tension 1.5 .. (j.ne + (0,3)) .. (m.nextin + (0,1));
 151   j.prevpath = j.prev -- g.previn;
 152   j.nextpath = j.next -- m.nextin;
 153   m.prevpath = m.prev .. (j.se - (0,3)) .. tension 1.5 .. (j.sw - (0,3)) .. (g.previn - (0,1));
 154   drawelement(a,d,g,j,m,ina,inj,root);
 155   internalnodeconnect(ina,a,d,g);
 156   internalnodeconnectone(inj,m,1);
 157   drawterminationarrow(inj.child[0] -- (inj.child[0] - (0,5)));
 158   internalnodeconnect(root,ina,inj);
 159 endfig;
 160
 161 beginfig(5);
 162   % tree with MNO removed
 163   boxjoin(b.w - a.e = (20,0));
 164   leafit.a(data[0], data[1], data[2]);
 165   leafit.d(data[3], data[4], data[5]);
 166   leafit.g(data[6], data[7], data[8]);
 167   leafit.j(data[9], data[10], data[11]);
 168   j.deleted = true;
 169   leafit.m(data[12], data[13], data[14]);
 170   m.locked = m.deleted = true;
 171   boxjoin();
 172   internalnodeit.ina(data[3], data[6], nullpicture);
 173   internalnodeit.inj(data[12], nullpicture, nullpicture);
 174   internalnodeit.root(data[12], nullpicture, nullpicture);
 175   ina.s = .5[a.nw,g.ne] + (0,24);
 176   inj.s = .5[j.nw,m.ne] + (0,24);
 177   root.s = .5[ina.nw,inj.ne] + (0,24);
 178   fixelement(a,d,g,j,m);
 179   fixelement(root,ina,inj);
 180   leafconnect(a,d,g);
 181   fill nodecellsbpath(m,0,2) withcolor deletedelement;
 182   fill leafnextbpath(m) withcolor black;
 183   m.prevpath = m.prev -- g.previn;
 184   drawelement(a,d,g,m,ina,inj,root);
 185   internalnodeconnect(ina,a,d,g);
 186   internalnodeconnectone(inj,m,1);
 187   drawterminationarrow(inj.child[0] -- (inj.child[0] - (0,5)));
 188   internalnodeconnect(root,ina,inj);
 189 endfig;
 190
 191 beginfig(6);
 192   % tree with MNO removed and internal node removed
 193   boxjoin(b.w - a.e = (20,0));
 194   leafit.a(data[0], data[1], data[2]);
 195   leafit.d(data[3], data[4], data[5]);
 196   leafit.g(data[6], data[7], data[8]);
 197   leafit.j(data[9], data[10], data[11]);
 198   j.deleted = true;
 199   leafit.m(data[12], data[13], data[14]);
 200   m.deleted = true;
 201   boxjoin();
 202   internalnodeit.ina(data[3], data[6], nullpicture);
 203   internalnodeit.inj(nullpicture, nullpicture, nullpicture);
 204   inj.locked = inj.deleted = true;
 205   internalnodeit.root(data[12], nullpicture, nullpicture);
 206   ina.s = .5[a.nw,g.ne] + (0,24);
 207   inj.s = .5[j.nw,m.ne] + (0,24);
 208   root.s = .5[ina.nw,inj.ne] + (0,24);
 209   fixelement(a,d,g,j,m);
 210   fixelement(root,ina,inj);
 211   leafconnect(a,d,g);
 212   fill nodecellsbpath(m,0,2) withcolor deletedelement;
 213   fill leafnextbpath(m) withcolor black;
 214   m.prevpath = m.prev -- g.previn;
 215   drawelement(a,d,g,m,ina,inj,root);
 216   internalnodeconnect(ina,a,d,g);
 217   drawterminationarrow(inj.child[0] -- (inj.child[0] - (0,5)));
 218   internalnodeconnect(root,ina,inj);
 219 endfig;
 220
 221 beginfig(7);
 222   % tree with MNO removed and internal node removed
 223   boxjoin(b.w - a.e = (20,0));
 224   leafit.a(data[0], data[1], data[2]);
 225   leafit.d(data[3], data[4], data[5]);
 226   leafit.g(data[6], data[7], data[8]);
 227   leafit.j(data[9], data[10], data[11]);
 228   j.deleted = true;
 229   leafit.m(data[12], data[13], data[14]);
 230   m.deleted = true;
 231   boxjoin();
 232   internalnodeit.ina(data[3], data[6], nullpicture);
 233   internalnodeit.inj(nullpicture, nullpicture, nullpicture);
 234   inj.deleted = true;
 235   internalnodeit.root(nullpicture, nullpicture, nullpicture);
 236   root.locked = true;
 237   ina.s = .5[a.nw,g.ne] + (0,24);
 238   inj.s = .5[j.nw,m.ne] + (0,24);
 239   root.s = .5[ina.nw,inj.ne] + (0,24);
 240   fixelement(a,d,g,j,m);
 241   fixelement(root,ina,inj);
 242   leafconnect(a,d,g);
 243   fill nodecellsbpath(m,0,2) withcolor deletedelement;
 244   fill leafnextbpath(m) withcolor black;
 245   m.prevpath = m.prev -- g.previn;
 246   drawelement(a,d,g,m,ina,inj,root);
 247   internalnodeconnect(ina,a,d,g);
 248   drawterminationarrow(inj.child[0] -- (inj.child[0] - (0,5)));
 249   internalnodeconnect(root,ina);
 250 endfig;
 251
 252 beginfig(8);
 253   % tree with MNO removed, gclayer begin
 254   boxjoin(b.w - a.e = (20,0));
 255   leafit.a(data[0], data[1], data[2]);
 256   leafit.d(data[3], data[4], data[5]);
 257   leafit.g(data[6], data[7], data[8]);
 258   boxjoin();
 259   leafit.x(dotdata, dotdata, dotdata, dotdata);
 260   x.nextpath = x.prevpath = emptypath;
 261   internalnodeit.ina(data[3], data[6], nullpicture);
 262   internalnodeit.root(nullpicture, nullpicture, nullpicture);
 263   ina.s = .5[a.nw,g.ne] + (0,24);
 264   root.sw = ina.n + (0,24);
 265   .8[x.sw,x.se] = root.n + (0,24);
 266   fixelement(a,d,g);
 267   fixelement(root,ina,x);
 268   leafconnect(a,d,g);
 269   drawelement(a,d,g,ina,root);
 270   fillelement(x)(upperlayerfill); drawelement(x) withcolor upperlayer;
 271   begingroup
 272     interim linecap := butt;
 273     draw (x.sw - (5,10)) -- (x.se + (40,-10)) withpen pencircle scaled 5 dashed evenly scaled 3 withcolor upperlayerfill;
 274   endgroup;
 275   drawconnarrow x.value[1] {down} .. tension 2 .. {down} root.n withpen connectionpen scaled 2 withcolor upperlayer;
 276   internalnodeconnect(ina,a,d,g);
 277   internalnodeconnect(root,ina);
 278 endfig;
 279
 280 beginfig(9);
 281   % tree with MNO removed, gclayer begin
 282   boxjoin(b.w - a.e = (20,0));
 283   leafit.a(data[0], data[1], data[2]);
 284   leafit.d(data[3], data[4], data[5]);
 285   leafit.g(data[6], data[7], data[8]);
 286   boxjoin();
 287   leafit.x(dotdata, dotdata, dotdata, dotdata);
 288   x.locked = true;
 289   x.nextpath = x.prevpath = emptypath;
 290   internalnodeit.ina(data[3], data[6], nullpicture);
 291   internalnodeit.root(nullpicture, nullpicture, nullpicture);
 292   ina.s = .5[a.nw,g.ne] + (0,24);
 293   root.sw = ina.n + (0,24);
 294   .8[x.sw,x.se] = root.n + (0,24);
 295   fixelement(a,d,g);
 296   fixelement(root,ina,x);
 297   leafconnect(a,d,g);
 298   drawelement(a,d,g,ina,root);
 299   fillelement(x)(upperlayerfill); drawelement(x) withcolor upperlayer;
 300   begingroup
 301     interim linecap := butt;
 302     draw (x.sw - (5,10)) -- (x.se + (40,-10)) withpen pencircle scaled 5 dashed evenly scaled 3 withcolor upperlayerfill;
 303   endgroup;
 304   drawconnarrow x.value[1] {down} .. tension 2 .. {down} root.n withpen connectionpen scaled 2 withcolor upperlayer;
 305   internalnodeconnect(ina,a,d,g);
 306   internalnodeconnect(root,ina);
 307 endfig;
 308
 309 beginfig(11);
 310   % tree with MNO removed, gclayer begin
 311   boxjoin(b.w - a.e = (20,0));
 312   leafit.a(data[0], data[1], data[2]);
 313   leafit.d(data[3], data[4], data[5]);
 314   leafit.g(data[6], data[7], data[8]);
 315   boxjoin();
 316   leafit.x(dotdata, dotdata, dotdata, dotdata);
 317   x.locked = true;
 318   x.nextpath = x.prevpath = emptypath;
 319   internalnodeit.ina(data[3], data[6], nullpicture);
 320   internalnodeit.root(nullpicture, nullpicture, nullpicture);
 321   root.locked = true;
 322   ina.s = .5[a.nw,g.ne] + (0,24);
 323   root.sw = ina.n + (0,24);
 324   .8[x.sw,x.se] = root.n + (0,24);
 325   fixelement(a,d,g);
 326   fixelement(root,ina,x);
 327   leafconnect(a,d,g);
 328   drawelement(a,d,g,ina,root);
 329   fillelement(x)(upperlayerfill); drawelement(x) withcolor upperlayer;
 330   begingroup
 331     interim linecap := butt;
 332     draw (x.sw - (5,10)) -- (x.se + (40,-10)) withpen pencircle scaled 5 dashed evenly scaled 3 withcolor upperlayerfill;
 333   endgroup;
 334   drawconnarrow x.value[1] {down} .. tension 2 .. {down} root.n withpen connectionpen scaled 2 withcolor upperlayer;
 335   internalnodeconnect(ina,a,d,g);
 336   internalnodeconnect(root,ina);
 337 endfig;
 338
 339 beginfig(12);
 340   % tree with MNO removed, gclayer begin
 341   boxjoin(b.w - a.e = (20,0));
 342   leafit.a(data[0], data[1], data[2]);
 343   leafit.d(data[3], data[4], data[5]);
 344   leafit.g(data[6], data[7], data[8]);
 345   boxjoin();
 346   leafit.x(dotdata, dotdata, dotdata, dotdata);
 347   x.locked = true;
 348   x.nextpath = x.prevpath = emptypath;
 349   internalnodeit.ina(data[3], data[6], nullpicture);
 350   internalnodeit.root(nullpicture, nullpicture, nullpicture);
 351   root.locked = true;
 352   ina.s = .5[a.nw,g.ne] + (0,24);
 353   root.sw = ina.n + (0,24);
 354   .8[x.sw,x.se] = root.n + (0,24);
 355   fixelement(a,d,g);
 356   fixelement(root,ina,x);
 357   leafconnect(a,d,g);
 358   drawelement(a,d,g,ina,root);
 359   fillelement(x)(upperlayerfill); drawelement(x) withcolor upperlayer;
 360   begingroup
 361     interim linecap := butt;
 362     draw (x.sw - (5,10)) -- (x.se + (40,-10)) withpen pencircle scaled 5 dashed evenly scaled 3 withcolor upperlayerfill;
 363   endgroup;
 364   drawconnarrow x.value[1] {down} .. tension 2 .. {down} (ina.n - (4,0)) withpen connectionpen scaled 2 withcolor upperlayer;
 365   internalnodeconnect(ina,a,d,g);
 366   internalnodeconnect(root,ina);
 367 endfig;
 368
 369 beginfig(15);
 370   % tree with MNO removed, gclayer begin
 371   leafit.a(nullpicture, nullpicture, nullpicture);
 372   boxjoin();
 373   leafit.x(dotdata, dotdata, dotdata, dotdata);
 374   x.locked = true;
 375   x.nextpath = x.prevpath = emptypath;
 376   .5[x.sw,x.se] = a.n + (0,24);
 377   fixelement(a,x);
 378   leafconnect(a);
 379   drawelement(a,x);
 380   fillelement(x)(upperlayerfill); drawelement(x) withcolor upperlayer;
 381   begingroup
 382     interim linecap := butt;
 383     draw (x.sw - (5,10)) -- (x.se + (40,-10)) withpen pencircle scaled 5 dashed evenly scaled 3 withcolor upperlayerfill;
 384   endgroup;
 385   drawconnarrow x.value[1] {down} .. tension 2 .. {down} a.n withpen connectionpen scaled 2 withcolor upperlayer;
 386 endfig;
 387
 388 beginfig(16);
 389   % tree with MNO removed, gclayer begin
 390   leafit.a(nullpicture, nullpicture, nullpicture);
 391   a.locked = true;
 392   boxjoin();
 393   leafit.x(dotdata, dotdata, dotdata, dotdata);
 394   x.locked = true;
 395   x.nextpath = x.prevpath = emptypath;
 396   .5[x.sw,x.se] = a.n + (0,24);
 397   fixelement(a,x);
 398   leafconnect(a);
 399   drawelement(a,x);
 400   fillelement(x)(upperlayerfill); drawelement(x) withcolor upperlayer;
 401   begingroup
 402     interim linecap := butt;
 403     draw (x.sw - (5,10)) -- (x.se + (40,-10)) withpen pencircle scaled 5 dashed evenly scaled 3 withcolor upperlayerfill;
 404   endgroup;
 405   drawconnarrow x.value[1] {down} .. tension 2 .. {down} a.n withpen connectionpen scaled 2 withcolor upperlayer;
 406 endfig;
 407
 408 end