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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
|
% Figures for MetaPost doc, by John Hobby. Public domain.
input boxes
filenametemplate "%j-%c.mps";
%%% This redefinition of dotlabel draws dots as a closed path
%%% which are rendered more smoothly in Adobe Reader.
vardef dotlabel@#(expr s,z) text t_ =
label@#(s,z) t_;
addto currentpicture
contour (makepath pencircle scaled dotlabeldiam) shifted z t_;
enddef;
beginfig(48);
fill unitsquare xscaled 1.1in yscaled .7in withcolor .9white;
boxit(currentpicture);
dx = dy = .25in;
clearit; drawboxed();
forsuffixes $=n,c: makelabel.top(str $, $); endfor
makelabel.bot("s",s);
forsuffixes $=ne,e,se: makelabel.rt(str $, $); endfor
forsuffixes $=nw,w,sw: makelabel.lft(str $, $); endfor
pickup pencircle scaled .3bp;
vardef larrow@#(expr a, da, s) =
drawdblarrow a..a+da; label@#(s,a+.5da); enddef;
larrow.rt(n, (0,-dy), "dy");
larrow.rt(s, (0,dy), "dy");
larrow.top(e, (-dx,0), "dx");
larrow.top(w, (dx,0), "dx");
endfig;
beginfig(49);
boxjoin(a.se=b.sw; a.ne=b.nw);
boxit.a(btex\strut$\cdots$ etex); boxit.ni(btex\strut$n_i$ etex);
boxit.di(btex\strut$d_i$ etex); boxit.ni1(btex\strut$n_{i+1}$ etex);
boxit.di1(btex\strut$d_{i+1}$ etex); boxit.aa(btex\strut$\cdots$ etex);
boxit.nk(btex\strut$n_k$ etex); boxit.dk(btex\strut$d_k$ etex);
drawboxed(di,a,ni,ni1,di1,aa,nk,dk); label.lft("ndtable:", a.w);
interim defaultdy:=7bp;
boxjoin(a.sw=b.nw; a.se=b.ne);
boxit.ba(); boxit.bb(); boxit.bc();
boxit.bd(btex $\vdots$ etex); boxit.be(); boxit.bf();
bd.dx=8bp; ba.ne=a.sw-(15bp,10bp);
drawboxed(ba,bb,bc,bd,be,bf); label.lft("hashtab:",ba.w);
vardef ndblock suffix $ =
boxjoin(a.sw=b.nw; a.se=b.ne);
forsuffixes $$=$1,$2,$3: boxit$$(); ($$dx,$$dy)=(5.5bp,4bp);
endfor; enddef;
ndblock nda; ndblock ndb; ndblock ndc;
nda1.c-bb.c = ndb1.c-nda3.c = (whatever,0);
xpart ndb3.se = xpart ndc1.ne = xpart di.c;
ndc1.c - be.c = (whatever,0);
drawboxed(nda1,nda2,nda3, ndb1,ndb2,ndb3, ndc1,ndc2,ndc3);
drawarrow bb.c -- nda1.w;
drawarrow be.c -- ndc1.w;
drawarrow nda3.c -- ndb1.w;
drawarrow nda1.c{right}..{curl0}ni.c cutafter bpath ni;
drawarrow nda2.c{right}..{curl0}di.c cutafter bpath di;
drawarrow ndc1.c{right}..{curl0}ni1.c cutafter bpath ni1;
drawarrow ndc2.c{right}..{curl0}di1.c cutafter bpath di1;
drawarrow ndb1.c{right}..nk.c cutafter bpath nk;
drawarrow ndb2.c{right}..dk.c cutafter bpath dk;
x.ptr=xpart aa.c; y.ptr=ypart ndc1.ne;
drawarrow subpath (0,.7) of (z.ptr..{left}ndc3.c) dashed evenly;
label.rt(btex \strut ndblock etex, z.ptr); endfig;
\beginfig(50)
interim circmargin := .07in;
fill unitsquare xscaled 1.1in yscaled .7in withcolor .9white;
circleit(currentpicture);
dx = dy;
clearit; drawboxed();
forsuffixes $=n,c: makelabel.top(str $, $); endfor
makelabel.bot("s",s);
makelabel.rt("e", e);
makelabel.lft("w", w);
pickup pencircle scaled .3bp;
vardef larrow@#(expr a, da, s) =
drawdblarrow a..a+da; label@#(s,a+.5da); enddef;
larrow.rt(n, (0,-dy), "dy");
larrow.rt(s, (0,dy), "dy");
larrow.top(e, (-dx,0), "dx");
larrow.top(w, (dx,0), "dx");
endfig;
vardef drawshadowed(text t) =
fixsize(t);
forsuffixes s=t:
fill bpath.s shifted (1pt,-1pt);
unfill bpath.s;
drawboxed(s);
endfor
enddef;
beginfig(51)
circleit.a(btex Box 1 etex);
circleit.b(btex Box 2 etex);
b.n = a.s - (0,20pt);
drawshadowed(a,b);
drawarrow a.s -- b.n;
endfig;
vardef cuta(suffix a,b) expr p =
drawarrow p cutbefore bpath.a cutafter bpath.b;
point .5*length p of p
enddef;
vardef self@# expr p =
cuta(@#,@#) @#.c{curl0}..@#.c+p..{curl0}@#.c enddef;
beginfig(52);
verbatimtex \def\stk#1#2{$\displaystyle{\matrix{#1\cr#2\cr}}$} etex
circleit.aa(btex\strut Start etex); aa.dx=aa.dy;
circleit.bb(btex \stk B{(a|b)^*a} etex);
circleit.cc(btex \stk C{b^*} etex);
circleit.dd(btex \stk D{(a|b)^*ab} etex);
circleit.ee(btex\strut Stop etex); ee.dx=ee.dy;
numeric hsep;
bb.c-aa.c = dd.c-bb.c = ee.c-dd.c = (hsep,0);
cc.c-bb.c = (0,.8hsep);
xpart(ee.e - aa.w) = 3.8in;
drawboxed(aa,bb,cc,dd,ee);
label.ulft(btex$b$etex, cuta(aa,cc) aa.c{dir50}..cc.c);
label.top(btex$b$etex, self.cc(0,30pt));
label.rt(btex$a$etex, cuta(cc,bb) cc.c..bb.c);
label.top(btex$a$etex, cuta(aa,bb) aa.c..bb.c);
label.llft(btex$a$etex, self.bb(-20pt,-35pt));
label.top(btex$b$etex, cuta(bb,dd) bb.c..dd.c);
label.top(btex$b$etex, cuta(dd,ee) dd.c..ee.c);
label.lrt(btex$a$etex, cuta(dd,bb) dd.c..{dir140}bb.c);
label.bot(btex$a$etex, cuta(ee,bb) ee.c..tension1.3 ..{dir115}bb.c);
label.urt(btex$b$etex, cuta(ee,cc) ee.c{(cc.c-ee.c)rotated-15}..cc.c);
endfig;
end
|
