summaryrefslogtreecommitdiff
path: root/graphics/asymptote/base/drawtree.asy
blob: 832dfc658a198b1d6a4d38eca120d566d46bbe3a (plain)
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
// A simple tree drawing module contributed by adarovsky
// See example treetest.asy

real treeNodeStep = 0.5cm;
real treeLevelStep = 1cm;
real treeMinNodeWidth = 2cm;

struct TreeNode {
  TreeNode parent;
  TreeNode[] children;

  frame content;

  pair pos;
  real adjust;
}

void add( TreeNode child, TreeNode parent )
{
  child.parent = parent;
  parent.children.push( child );
}

TreeNode makeNode( TreeNode parent = null, frame f )
{
  TreeNode child = new TreeNode;
  child.content = f;
  if( parent != null ) {
    add( child, parent );
  }
  return child;
}

TreeNode makeNode( TreeNode parent = null, Label label )
{
  frame f;
  box( f, label);
  return makeNode( parent, f );
}


real layout( int level, TreeNode node )
{
  if( node.children.length > 0 ) {
    real width[] = new real[node.children.length];
    real curWidth = 0;

    for( int i = 0; i < node.children.length; ++i ) {
      width[i] = layout( level+1, node.children[i] );

      node.children[i].pos = (curWidth + width[i]/2,
                              -level*treeLevelStep);
      curWidth += width[i] + treeNodeStep;
    }

    real midPoint = ( sum( width )+treeNodeStep*(width.length-1)) / 2;
    for( int i = 0; i < node.children.length; ++i ) {
      node.children[i].adjust = - midPoint;
    }

    return max( (max(node.content)-min(node.content)).x,
                sum(width)+treeNodeStep*(width.length-1) );
  }
  else {
    return max( treeMinNodeWidth, (max(node.content)-min(node.content)).x );
  }
}

void drawAll( TreeNode node, frame f )
{
  pair pos;
  if( node.parent != null )
    pos = (node.parent.pos.x+node.adjust, 0);
  else
    pos = (node.adjust, 0);
  node.pos += pos;

  node.content = shift(node.pos)*node.content;
  add( f, node.content );


  if( node.parent != null ) {
    path p = point(node.content, N)--point(node.parent.content,S);
    draw( f, p, currentpen );
  }

  for( int i = 0; i < node.children.length; ++i )
    drawAll( node.children[i], f );
}

void draw( TreeNode root, pair pos )
{
  frame f;

  root.pos = (0,0);
  layout( 1, root );

  drawAll( root, f );

  add(f,pos);
}