#! /bin/awk -f
#
# 2004 Steven Gustafson smg@cs.nott.ac.uk
#
# Description: depth-first search, preorder, of text file containing two 
# columns, where each line contains an <x y z> tuple.  The term `z` 
# indicates if there is a node at location <x y>.  The output is intended
# for a plotting program, like GNUPLOT, that plots lines.
#
# Inputs: file containing lattice points plus [1,0] to indicate node present 
# Outputs: the set of points, to connect with lines in order, for the
#          GNUPLOT program, or other suitable plotting program.  A
#          script tree.gpi is provided for gnuplot at the bottom of file.


function preorder(i,x,w,z,max)
{

	print x[i], w[i], z[i] 
	if( (i*2) <= max )
   {
	   if( z[i*2] != 0 )	
         preorder(i*2,x,w,z,max)
		else
		{
			print x[i], w[i], 0	
			print x[i], w[i], z[i]	
		}		
		print x[i], w[i], z[i] 
	   if( z[(i*2)+1] != 0 )	
    	   preorder((i*2)+1,x,w,z,max)
		else
		{
			print x[i], w[i], 0	
			print x[i], w[i], z[i]	
		}		
	}
	else
	{
		print x[i], w[i], 0	
		print x[i], w[i], z[i]	
	}		
	print x[i], w[i], z[i] 
}
    
function dfs(i,x,w,z,max)
{
	if( z[i] != 0 )
	{ 
		print x[i], w[i], z[i] 
   	preorder(i*2,x,w,z,max)
		print x[i], w[i], z[i] 
		preorder((i*2)+1,x,w,z,max)
	}
}

BEGIN{RS= "\n"};  

{
x[NR] = $1
w[NR] = $2
z[NR] = $3
}

END{ 
		dfs(1,x,w,z,NR) 	
}


# BEGIN GNUPLOT script
# run by typing `gnuplot tree.gpi' 
#
#set terminal postscript eps 22; set output 'tree.eps'
#
#set nokey
#set noxtics
#set noytics
#set noztics
#
#set noborder
#
#set pointsize 1.5
#
#set size 0.8,1.0
#
##set xrange [-10:10]
##set yrange [-10:10]
#
#plot 'points' u 1:2 with linesp pt 7