Debian Codegraph @

texmf-dist/doc/latex/circuit-macros/examples/Btree.m4

raw
1 .PS
2 # Btree.m4
3 # One way to draw a binary tree using pic macros
4 gen_init
5 sinclude(tst.dim)
6 s_init(Ttree)
7
8 circlerad = 0.30
9
10 define n { [C: circle fill_(0.9) $1
11 if "$2" != "" then {
12 L: $2 with .ne at C.s-(circlerad/20, circlerad/2)
13 line from C to L.C chop }
14 if "$3" != "" then {
15 R: $3 with .nw at C.s+(circlerad/20,-circlerad/2)
16 line from C to R.C chop }
17 ] }
18
19 # Redrawn from T. A. Standish, "Data Structure Techniques," Addison-Wesley 1980.
20 # Node data:
21 define Sirius { n("Sirius",Canopus,Vega) }
22 define Canopus { n("Canopus",AlphaCentauri,Capella) }
23 define AlphaCentauri { n("Alpha" "Centauri",Achernar,Arcturus) }
24 define Arcturus { n("Arcturus",Betelgeux) }
25 define Betelgeux { n("Betelgeux",BetaCentauri) }
26 define Capella { n("Capella",Rigel) }
27 define Rigel { n("Rigel",Procyon) }
28 define Achernar { n("Achernar") }
29 define BetaCentauri { n("Beta" "Centauri") }
30 define Procyon { n("Procyon") }
31 define Vega { n("Vega") }
32
33 # Build the tree from the root
34 S: Sirius
35 #.PE
36
37 #.PS
38 ## Ttree.m4
39 ## A binary tree using m4
40 #gen_init
41 #sinclude(tst.dim)
42 #s_init(Ttree)
43
44 T: [
45 # `Node(no in row, head [location],
46 # displacement of top of body (.n) wrt head,
47 # body Node 1, body Node 2, ...) '
48 define(`Node',`
49 Head`$1': `$2'
50 ifelse(`$3',,,`Body`$1': [
51 Loopover_(`v',`v; define(`m4ct',m4Lx)',shift(shift(shift($@))))
52 ] with .n at Head`$1' + `$3'
53 connect(`$1',m4ct)')')
54
55 define(`connect',`Bot: move from Head$1.sw to Head$1.se
56 for_(1,`$2',1,
57 `Top: move from Body$1.Head`'m4x.nw to Body$1.Head`'m4x.ne
58 Move: move from Head$1 to Body$1.Head`'m4x
59 if Bot.len*Top.len*Move.len > 0 then {
60 line from Intersect_(Move,Top) to Intersect_(Move,Bot)}')')
61
62 vsep = 0.75
63
64 Node(1,s_box($`h(h(h(x_1,x_2),h(x_3,x_4)),h(h(x_5,x_6),h(x_7,x_8)))'$),
65 (0,-vsep),
66 Node(1,s_box($`h(h(x_1,x_2),h(x_3,x_4))'$),
67 (0,-vsep),
68 Node(1,s_box($`h(x_1,x_2)'$),
69 (0,-vsep),
70 Node(1,s_box($`x_1:=((A,pk_A),h_1)'$)),
71 Node(2,s_box($`x_2:=((B,pk_B),h_2)'$) \
72 with .n at last "".ne+(0.2,-vsep*2/3))),
73 Node(2,s_box($`h(x_3,x_4)'$) with .nw at Head1.ne+(Body1.wid/2+0.1,0),
74 (0,-vsep),
75 Node(1,s_box($`x_3:=((A,pk_A^\prime),h_3)'$)),
76 Node(2,s_box($`x_4:=((D,pk_D),h_4)'$) \
77 with .n at last "".ne+(0.2,-vsep*2/3)))),
78 Node(2,s_box($`h(h(x_5,x_6),h(x_7,x_8))'$) \
79 with .nw at Head1.ne+(Body1.wid/2,0),
80 (0,-vsep),
81 Node(1,s_box($`h(x_5,x_6)'$),
82 (0,-vsep*5/4),
83 Node(1,s_box($`x_5:=((E,pk_E),h_5)'$)),
84 Node(2,s_box($`x_6:=((H,pk_H),h_6)'$) \
85 with .n at last "".ne+(0.2,-vsep*2/3))),
86 Node(2,s_box($`h(x_7,x_8)'$) with .nw at Head1.ne+(Body1.wid/2+0.1,0),
87 (0,-vsep*5/4),
88 Node(1,s_box($`x_7:=((D,pk_D^\prime),h_7)'$)),
89 Node(2,s_box($`x_8:=((K,pk_K),h_8)'$) \
90 with .n at last "".ne+(0.2,-vsep*2/3))),
91 Node(3,s_box($`h(x_9)'$) at 0.5 between Head1 and Head2)))
92 ] with .n at S.s + (1.2,0.5)
93
94 .PE