tree ``package''

[Marc van Dongen <dongen@cs.ucc.ie>]

[-- Attachment #1: Type: text/plain, Size: 547 bytes --]

Hi there,

I have hacked a package \'a la boxes for
drawing trees. It's pretty primitive but
it works. In due time I'll improve the
package and add different methods to draw
trees.

The major difference between the boxes and
tree package is that the boxit equivalent
(treeit) of the tree package returns a picture.

I've attached the package and the example.

Regards,

Marc
-- 
     Marc van Dongen, CS Dept | phone:  +353 21 4903578
University College Cork, NUIC | Fax:    +353 21 4903113
  College Road, Cork, Ireland | Email: dongen@cs.ucc.ie

[-- Attachment #2: marctree.mp --]
[-- Type: text/plain, Size: 2178 bytes --]

input mp-tool;
input boxes;    % for generic_declare
input marctool;

numeric nrtrees;
picture node_[];
numeric depth_[];
numeric width_[];
numeric nrbranches_[];
numeric branch_[][];

nrtrees := 0;

vardef tree@#( expr pic ) =
  _n_ := str @#;
  generic_declare(numeric) _n.number, _n.scal, _n.distx, _n.disty;
  % numeric @#number, @#scal, @#distx, @#disty;
  @#distx  := 1cm;
  @#disty  := 1cm;
  @#number := nrtrees + 1;
  numerictree( @#number, pic );
enddef;

def numerictree( expr nr, pic ) =
  nrtrees := nr;
  node_[ nr ] := pic;
  depth_[ nr ] := 0;
  width_[ nr ] := 0;
  nrbranches_[ nr ] := 0;
enddef;

vardef branches@#( text ns ) =
  forsuffixes $$ = ns:
    numericbranch( @#number, $$.number );
  endfor;
enddef;

def numericbranch( expr nr, nrnr ) =
  begingroup
    save d, w;
    nrbranches_[ nr ] := nrbranches_[ nr ] + 1;
    branch_[ nr ][ nrbranches_[ nr ] ] := nrnr;
    d := 0;
    w := 0;
    for b = 1 upto nrbranches_[ nr ]:
      d := max( d, depth_[ branch_[ nr ][ b ] ] );
      w := w + width_[ branch_[ nr ][ b ] ];
    endfor;
    depth_[ nr ] := 1 + d;
    width_[ nr ] := w;
  endgroup;
enddef;

def treeit( suffix $ ) =
  treeitpicture( $.number, (0,0), $.distx, $.disty )
enddef;

vardef treeitpicture( expr nr, pos, distx, disty ) =
  save bp, ts, pic, w;
  picture pic, ts[];
  pic := node_[ nr ]
         % centreofbox
         shifted (pos - centreofbox( node_[ nr ] ));
  w := -distx;
  for b = 1 upto nrbranches_[ nr ]:
    ts[ b ] = treeitpicture( branch_[ nr ][ b ], (0,0), distx, disty );
    w := w + widthofbox( ts[ b ] ) + distx;
  endfor;
  w := -0.5*w;
  for b = 1 upto nrbranches_[ nr ]:
    addto pic also
          (ts[ b ] shifted (w+0.5*widthofbox( ts[ b ] ),disty));
    addto pic
          doublepath (pos + (0,0.5*heightofbox( node_[ nr ] ) + 1mm)--
                      (w+0.5*widthofbox( ts[ b ] ),
                       disty - 0.5heightofbox( node_[ branch_[ nr ][ b ] ] ) - 1mm));
    w := w + widthofbox( ts[ b ] ) + distx;
  endfor;
  pic
enddef;

vardef leaf@#( expr pic ) =
  tree.@#( pic )
enddef;

vardef node@# =
  tree.@#( nullpicture )
enddef;

vardef branch@#( text bs ) =
  branches@#( bs )
enddef;

[-- Attachment #3: drawtree.mp --]
[-- Type: text/plain, Size: 1912 bytes --]

verbatimtex
\documentclass[12pt]{article}
\usepackage[T1]{fontenc}
\usepackage{euler}
\usepackage{times}
\begin{document}
etex;

defaultfont := "cmr12";
defaultscale := 12pt /fontsize defaultfont;
input mp-tool;
prologues := 2;
input marctree;

beginfig( 0 );
  picture t[];
  numeric len;
  len = 5cm;

  leaf.t0( btex 0 etex );
  leaf.t1( btex 1 etex );
  for i = 2 upto 15:
    node.t[i];
    branches.t[i]( t[ i div 2 ], t[ i mod 2 ] );
    t[i].distx := 0.5cm;
    t[i].disty := 0.5cm;
  endfor;
  for i = 0 upto 15:
    drawarrow 4mm*up rotated (i * 360 / 16)--(len-1cm)*up rotated (i * 360 / 16)
              withpen pencircle scaled 1pt
              withcolor red;
    label( decimal( i ), (len-5mm)*up rotated (i * 360 / 16) );
    draw treeit( t[ i ] )
         rotated (i * 360 / 16)
         shifted (len*up rotated (i * 360 / 16))
         withcolor blue;
  endfor;
  setbounds currentpicture to boundingbox currentpicture enlarged 2pt; 
endfig;

beginfig( 1 );
  picture d, h, e, l, o, r, w, hello, space, bang;

  leaf.d( btex d etex );
  leaf.h( btex H etex );
  leaf.e( btex e etex );
  leaf.l( btex l etex );
  leaf.o( btex o etex );
  leaf.r( btex r etex );
  leaf.w( btex w etex );
  leaf.bang( btex ! etex );
  node.space;
  node.hello;
  branches.hello( h, e, l, l, o, space, w, o, r, l, d, bang );
  hello.distx := 1.2mm;

  draw treeit( hello );
  setbounds currentpicture to boundingbox currentpicture enlarged 2pt; 
endfig;

beginfig( 2 );
  picture b, c, d, e, f;

  leaf.a( btex a etex );
  leaf.b( btex b etex );
  leaf.c( btex c etex );
  leaf.d( btex d etex );
  leaf.f( btex f etex );
  leaf.g( btex g etex );
  branches.f( g );
  branches.e( f, g );
  branches.d( e, f, g );
  branches.c( d, e, f, g );
  branches.b( c, d, e, f, g );
  b.distx :=  5mm;
  b.disty := 15mm;
  draw treeit( b );
  setbounds currentpicture to boundingbox currentpicture enlarged 2pt; 
endfig;

end