summaryrefslogtreecommitdiffstats
path: root/misc/drawtree.pl
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2018-01-29 14:31:24 (GMT)
committerDavid A. Madore <david+git@madore.org>2018-01-29 14:31:24 (GMT)
commitd1a7e0acc7c78ec3d2bf473b4b4739315b8a2f1f (patch)
treef119b2f49198d04b462276c87224172d1b38f1b1 /misc/drawtree.pl
parent5ae6d7fbf72a36f7891d14399c0d4fc9cfb370b8 (diff)
downloadinf105-d1a7e0acc7c78ec3d2bf473b4b4739315b8a2f1f.zip
inf105-d1a7e0acc7c78ec3d2bf473b4b4739315b8a2f1f.tar.gz
inf105-d1a7e0acc7c78ec3d2bf473b4b4739315b8a2f1f.tar.bz2
Simple Perl program used to generate TikZ trees.
Diffstat (limited to 'misc/drawtree.pl')
-rwxr-xr-xmisc/drawtree.pl116
1 files changed, 116 insertions, 0 deletions
diff --git a/misc/drawtree.pl b/misc/drawtree.pl
new file mode 100755
index 0000000..7243595
--- /dev/null
+++ b/misc/drawtree.pl
@@ -0,0 +1,116 @@
+#! /usr/local/bin/perl -w
+
+use strict;
+use warnings;
+
+my $str = <>;
+chomp $str;
+
+my $cursor = 0;
+sub parse {
+ my $nodelabel = "";
+ while (substr($str,$cursor,1) ne "<" && substr($str,$cursor,1) ne ".") {
+ die if $cursor >= length($str);
+ $nodelabel .= substr($str,$cursor,1);
+ $cursor++;
+ }
+ $cursor++ if substr($str,$cursor,1) eq "<";
+ my %node = ();
+ $node{label} = $nodelabel;
+ die if $nodelabel eq "";
+ my @children = ();
+ $node{t} = \@children;
+ while (substr($str,$cursor,1) ne ">" && substr($str,$cursor,1) ne ".") {
+ die if $cursor >= length($str);
+ my $child = parse();
+ $child->{parent} = \%node;
+ push @children, $child;
+ }
+ $cursor++;
+ return \%node;
+}
+
+my $tree = parse;
+
+my @leafnodes = ();
+my @pfxnodes = ();
+my @sfxnodes = ();
+sub donodes {
+ my $node = shift;
+ die unless defined($node->{label});
+ die unless defined($node->{t});
+ die unless ref($node->{t}) eq "ARRAY";
+ $node->{depth} = defined($node->{parent}) ? $node->{parent}->{depth} + 1 : 0;
+ push @pfxnodes, $node; $node->{pfx} = $#pfxnodes;
+ if ( scalar(@{$node->{t}}) ) {
+ foreach my $n (@{$node->{t}}) {
+ donodes($n);
+ }
+ } else {
+ push @leafnodes, $node;
+ }
+ push @sfxnodes, $node; $node->{sfx} = $#sfxnodes;
+}
+donodes $tree;
+
+for ( my $i=0 ; $i<scalar(@leafnodes) ; $i++ ) {
+ $leafnodes[$i]->{x} = $i * 20;
+}
+
+my %nodenames;
+
+for ( my $i=0 ; $i<scalar(@pfxnodes) ; $i++ ) {
+ my $node = $pfxnodes[$i];
+ my $base = $node->{label};
+ $base = "o" if $base eq "\#" || $base eq "\@";
+ $base = "p" if $base eq "\(" || $base eq "\)";
+ my $j;
+ for ( $j=0 ; ; $j++ ) {
+ last unless defined($nodenames{$base.$j});
+ }
+ my $name = $base.$j;
+ $node->{name} = $name;
+ $nodenames{$name} = $node;
+ my $ltxlabel = $node->{label};
+ $ltxlabel = "\\" . $ltxlabel if $ltxlabel eq "\#";
+ $node->{ltxlabel} = $ltxlabel;
+}
+
+for ( my $i=0 ; $i<scalar(@pfxnodes) ; $i++ ) {
+ my $node = $pfxnodes[$i];
+ if ( defined($node->{parent}) ) {
+ my $p = $node->{parent};
+ die unless defined $p->{y};
+ if ( scalar(@{$p->{t}}) > 1 ) {
+ $node->{y} = $p->{y} + 30;
+ } else {
+ $node->{y} = $p->{y} + 20;
+ }
+ } else {
+ $node->{y} = 0;
+ }
+}
+
+for ( my $i=0 ; $i<scalar(@sfxnodes) ; $i++ ) {
+ my $node = $sfxnodes[$i];
+ if ( scalar(@{$node->{t}}) ) {
+ my $sum = 0; my $cnt = 0;
+ foreach my $n (@{$node->{t}}) {
+ die unless defined $n->{x};
+ $sum += $n->{x}; $cnt++;
+ }
+ $node->{x} = $sum/$cnt;
+ }
+}
+
+printf "\\begin{tikzpicture}\[line join=bevel,baseline=(%s.base)\]\n", $tree->{name};
+for ( my $i=0 ; $i<scalar(@pfxnodes) ; $i++ ) {
+ my $node = $pfxnodes[$i];
+ printf "\\node (%s) at (%.3fbp,%.3fbp) \[draw=none\] {\$%s\$};", $node->{name}, $node->{x}, -$node->{y}, $node->{ltxlabel};
+ if ( defined($node->{parent}) ) {
+ printf " \\draw (%s) -- (%s);\n", $node->{parent}->{name}, $node->{name};
+ } else {
+ printf "\n";
+ }
+}
+print "\\end{tikzpicture}\n";