silo/masstree/doc/insert1.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 MNO removed, gclayer begin
  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   boxjoin();
  39   leafit.x(dotdata, dotdata, dotdata, dotdata);
  40   x.nextpath = x.prevpath = emptypath;
  41   internalnodeit.ina(data[3], data[6], data[9]);
  42   ina.s = .5[a.nw,j.ne] + (0,24);
  43   .5[x.sw,x.se] = ina.n + (0,24);
  44   fixelement(a,d,g,j,ina,x);
  45   leafconnect(a,d,g,j);
  46   drawelement(a,d,g,j,ina);
  47   fillelement(x)(upperlayerfill); drawelement(x) withcolor upperlayer;
  48   begingroup
  49     interim linecap := butt;
  50     draw (x.sw - (40,10)) -- (x.se + (40,-10)) withpen pencircle scaled 5 dashed evenly scaled 3 withcolor upperlayerfill;
  51   endgroup;
  52   drawconnarrow x.value[1] {down} .. tension 2 .. {down} ina.n withpen connectionpen scaled 2 withcolor upperlayer;
  53   internalnodeconnect(ina,a,d,g,j);
  54 endfig;
  55
  56 beginfig(2);
  57   % tree with MNO removed, gclayer begin
  58   boxjoin(b.w - a.e = (20,0));
  59   leafit.a(data[0], data[1], data[2]);
  60   leafit.d(data[3], data[4], data[5]);
  61   leafit.g(data[6], data[7], data[8]);
  62   leafit.j(data[9], data[10], data[11]);
  63   leafit.m(data[12], nullpicture, nullpicture);
  64   j.locked = m.locked = true;
  65   boxjoin();
  66   leafit.x(dotdata, dotdata, dotdata, dotdata);
  67   x.nextpath = x.prevpath = emptypath;
  68   internalnodeit.ina(data[3], data[6], data[9]);
  69   ina.s = .5[a.nw,j.ne] + (0,24);
  70   .5[x.sw,x.se] = ina.n + (0,24);
  71   fixelement(a,d,g,j,m,ina,x);
  72   leafconnect(a,d,g,j,m);
  73   drawelement(a,d,g,j,m,ina);
  74   fillelement(x)(upperlayerfill); drawelement(x) withcolor upperlayer;
  75   begingroup
  76     interim linecap := butt;
  77     draw (x.sw - (40,10)) -- (x.se + (40,-10)) withpen pencircle scaled 5 dashed evenly scaled 3 withcolor upperlayerfill;
  78   endgroup;
  79   drawconnarrow x.value[1] {down} .. tension 2 .. {down} ina.n withpen connectionpen scaled 2 withcolor upperlayer;
  80   internalnodeconnect(ina,a,d,g,j);
  81 endfig;
  82
  83 beginfig(3);
  84   % tree with MNO removed, gclayer begin
  85   boxjoin(b.w - a.e = (20,0));
  86   leafit.a(data[0], data[1], data[2]);
  87   leafit.d(data[3], data[4], data[5]);
  88   leafit.g(data[6], data[7], data[8]);
  89   leafit.j(data[9], data[10], data[11]);
  90   leafit.m(data[12], nullpicture, nullpicture);
  91   boxjoin();
  92   leafit.x(dotdata, dotdata, dotdata, dotdata);
  93   x.nextpath = x.prevpath = emptypath;
  94   internalnodeit.ina(data[3], data[6], nullpicture);
  95   internalnodeit.inj(data[12], nullpicture, nullpicture);
  96   ina.locked = inj.locked = true;
  97   ina.s = .5[a.nw,g.ne] + (0,24);
  98   inj.s = .5[j.nw,m.ne] + (0,24);
  99   .5[x.sw,x.se] = ina.n + (0,24);
 100   fixelement(a,d,g,j,m,ina,inj,x);
 101   leafconnect(a,d,g,j,m);
 102   drawelement(a,d,g,j,m,ina,inj);
 103   fillelement(x)(upperlayerfill); drawelement(x) withcolor upperlayer;
 104   begingroup
 105     interim linecap := butt;
 106     draw (x.sw - (40,10)) -- (x.se + (40,-10)) withpen pencircle scaled 5 dashed evenly scaled 3 withcolor upperlayerfill;
 107   endgroup;
 108   drawconnarrow x.value[1] {down} .. tension 2 .. {down} ina.n withpen connectionpen scaled 2 withcolor upperlayer;
 109   internalnodeconnect(ina,a,d,g);
 110   internalnodeconnect(inj,j,m);
 111 endfig;
 112
 113 beginfig(4);
 114   % tree with MNO removed, gclayer begin
 115   boxjoin(b.w - a.e = (20,0));
 116   leafit.a(data[0], data[1], data[2]);
 117   leafit.d(data[3], data[4], data[5]);
 118   leafit.g(data[6], data[7], data[8]);
 119   leafit.j(data[9], data[10], data[11]);
 120   leafit.m(data[12], nullpicture, nullpicture);
 121   boxjoin();
 122   leafit.x(dotdata, dotdata, dotdata, dotdata);
 123   x.nextpath = x.prevpath = emptypath;
 124   internalnodeit.ina(data[3], data[6], nullpicture);
 125   internalnodeit.inj(data[12], nullpicture, nullpicture);
 126   internalnodeit.root(data[9], nullpicture, nullpicture);
 127   ina.s = .5[a.nw,g.ne] + (0,24);
 128   inj.s = .5[j.nw,m.ne] + (0,24);
 129   root.sw = .3[ina.n,inj.n] + (0,24);
 130   .8[x.sw,x.se] = root.n + (0,24);
 131   fixelement(a,d,g,j,m,root,ina,inj,x);
 132   leafconnect(a,d,g,j,m);
 133   drawelement(a,d,g,j,m,ina,inj,root);
 134   fillelement(x)(upperlayerfill); drawelement(x) withcolor upperlayer;
 135   begingroup
 136     interim linecap := butt;
 137     draw (x.sw - (40,10)) -- (x.se + (40,-10)) withpen pencircle scaled 5 dashed evenly scaled 3 withcolor upperlayerfill;
 138   endgroup;
 139   drawconnarrow x.value[1] {down} .. tension 2 .. {down} ina.n withpen connectionpen scaled 2 withcolor upperlayer;
 140   internalnodeconnect(ina,a,d,g);
 141   internalnodeconnect(inj,j,m);
 142   ina.connectin := .6[ina.nw,ina.ne];
 143   internalnodeconnect(root,ina,inj);
 144 endfig;
 145
 146 beginfig(5);
 147   % tree with MNO removed, gclayer begin
 148   boxjoin(b.w - a.e = (20,0));
 149   leafit.a(data[0], data[1], data[2]);
 150   leafit.d(data[3], data[4], data[5]);
 151   leafit.g(data[6], data[7], data[8]);
 152   leafit.j(data[9], data[10], data[11]);
 153   leafit.m(data[12], nullpicture, nullpicture);
 154   boxjoin();
 155   leafit.x(dotdata, dotdata, dotdata, dotdata);
 156   x.locked = true;
 157   x.nextpath = x.prevpath = emptypath;
 158   internalnodeit.ina(data[3], data[6], nullpicture);
 159   internalnodeit.inj(data[12], nullpicture, nullpicture);
 160   internalnodeit.root(data[9], nullpicture, nullpicture);
 161   ina.s = .5[a.nw,g.ne] + (0,24);
 162   inj.s = .5[j.nw,m.ne] + (0,24);
 163   root.sw = .3[ina.n,inj.n] + (0,24);
 164   .5[x.sw,x.se] = root.n + (0,24);
 165   fixelement(a,d,g,j,m,root,ina,inj,x);
 166   leafconnect(a,d,g,j,m);
 167   drawelement(a,d,g,j,m,ina,inj,root);
 168   fillelement(x)(upperlayerfill); drawelement(x) withcolor upperlayer;
 169   begingroup
 170     interim linecap := butt;
 171     draw (x.sw - (40,10)) -- (x.se + (40,-10)) withpen pencircle scaled 5 dashed evenly scaled 3 withcolor upperlayerfill;
 172   endgroup;
 173   drawconnarrow x.value[1] {down} .. tension 2 .. {down} root.n withpen connectionpen scaled 2 withcolor upperlayer;
 174   internalnodeconnect(ina,a,d,g);
 175   internalnodeconnect(inj,j,m);
 176   internalnodeconnect(root,ina,inj);
 177 endfig;
 178
 179 end