//----------------------------------------------------------------------
// File:			ann2fig.cpp
// Programmer:		David Mount
// Last modified:	05/03/05
// Description:		convert ann dump file to fig file
//----------------------------------------------------------------------
// Copyright (c) 1997-2005 University of Maryland and Sunil Arya and
// David Mount.  All Rights Reserved.
// 
// This software and related documentation is part of the Approximate
// Nearest Neighbor Library (ANN).  This software is provided under
// the provisions of the Lesser GNU Public License (LGPL).  See the
// file ../ReadMe.txt for further information.
// 
// The University of Maryland (U.M.) and the authors make no
// representations about the suitability or fitness of this software for
// any purpose.  It is provided "as is" without express or implied
// warranty.
//----------------------------------------------------------------------
// History:
//	Revision 0.1  03/04/98
//		Initial release
//	Revision 1.0  04/01/05
//		Changed dump file suffix from .ann to .dmp.
//	Revision 1.1  05/03/05
//		Fixed usage output string.
//----------------------------------------------------------------------
//	This program inputs an ann dump file of a search structure
//	perhaps along with point coordinates, and outputs a fig (Ver 3.1)
//	file (see fig2dev (1)) displaying the tree.  The fig file may
//	then be displayed using xfig, or converted to any of a number of
//	other formats using fig2dev.
//
//	If the dimension is 2 then the entire tree is display.  If the
//	dimension is larger than 2 then the user has the option of
//	selecting which two dimensions will be displayed, and the slice
//	value for each of the remaining dimensions.  All leaf cells
//	intersecting the slice are shown along with the points in these
//	cells. See the procedure getArgs() below for the command-line
//	arguments.
//----------------------------------------------------------------------

#include <cstdio>						// C standard I/O
#include <cstdlib>						// standard lib defs
#include <cstring>						// C strings
#include <fstream>						// file I/O
#include <string>						// string manipulation
#include <ANN/ANNx.h>					// all ANN includes

using namespace std;					// make std:: accessible

//----------------------------------------------------------------------
// Globals and their defaults
//----------------------------------------------------------------------

const int		STRING_LEN		= 500;	// string lengths
const int		MAX_DIM			= 1000; // maximum dimension
const double	DEF_SLICE_VAL	= 0;	// default slice value
const char		FIG_HEAD[]		= {"#FIG 3.1"}; // fig file header
const char		DUMP_SUFFIX[]	= {".dmp"};	// suffix for dump file
const char		FIG_SUFFIX[]	= {".fig"};	// suffix for fig file

char			file_name[STRING_LEN];	// (root) file name (say xxx)
char			infile_name[STRING_LEN];// input file name (xxx.dmp)
char			outfile_name[STRING_LEN];// output file name (xxx.fig)
char			caption[STRING_LEN];	// caption line (= command line)
ofstream		ofile;					// output file stream
ifstream		ifile;					// input file stream
int				dim_x = 0;				// horizontal dimension
int				dim_y = 1;				// vertical dimension
double			slice_val[MAX_DIM];		// array of slice values
double			u_per_in = 1200;		// fig units per inch (version 3.1)
double			in_size = 5;			// size of figure (in inches)
double			in_low_x = 1;			// fig upper left corner (in inches)
double			in_low_y = 1;			// fig upper left corner (in inches)
double			u_size = 6000;			// size of figure (in units)
double			u_low_x = 1200;			// fig upper left corner (in units)
double			u_low_y = 1200;			// fig upper left corner (in units)
int				pt_size = 10;			// point size (in fig units)

int				dim;					// dimension
int				n_pts;					// number of points
ANNpointArray	pts = NULL;				// point array

double			scale;					// scale factor for transformation
double			offset_x;				// offsets for transformation
double			offset_y;

										// transformations
#define TRANS_X(p)		(offset_x + scale*(p[dim_x]))
#define TRANS_Y(p)		(offset_y - scale*(p[dim_y]))

//----------------------------------------------------------------------
//	Error handler
//----------------------------------------------------------------------

void Error(const char* msg, ANNerr level)
{
	if (level == ANNabort) {
		cerr << "ann2fig: ERROR------->" << msg << "<-------------ERROR\n";
		exit(1);
	}
	else {
		cerr << "ann2fig: WARNING----->" << msg << "<-------------WARNING\n";
	}
}

//----------------------------------------------------------------------
// set_slice_val - set all slice values to given value
//----------------------------------------------------------------------

void set_slice_val(double val)
{
	for (int i = 0; i < MAX_DIM; i++) {
		slice_val[i] = val;
	}
}

//----------------------------------------------------------------------
// getArgs - get input arguments
//
//		Syntax:
//		ann2fig [-upi scale] [-x low_x] [-y low_y] 
//				[-sz size] [-dx dim_x] [-dy dim_y] [-sl dim value]*
//				[-ps pointsize]
//				file
//		
//		where:
//			-upi scale			fig units per inch (default = 1200)
//			-x low_x			x and y offset of upper left corner (inches)
//			-y low_y			...(default = 1)
//			-sz size			maximum side length of figure (in inches)
//								...(default = 5)
//			-dx dim_x			horizontal dimension (default = 0)
//			-dy dim_y			vertical dimension (default = 1)
//			-sv value			default slice value (default = 0)
//			-sl dim value		each such pair defines the value along the
//								...given dimension at which to slice.  This
//								...may be supplied for all dimensions except
//								...dim_x and dim_y.
//			-ps pointsize		size of points in fig units (def = 10)
//			file				file (input=file.dmp, output=file.fig)
//
//----------------------------------------------------------------------

void getArgs(int argc, char **argv)
{
	int i;
	int sl_dim;									// temp slice dimension
	double sl_val;								// temp slice value

	set_slice_val(DEF_SLICE_VAL);				// set initial slice-values

	if (argc <= 1) {
		cerr << "Syntax:\n\
        ann2fig [-upi scale] [-x low_x] [-y low_y]\n\
                [-sz size] [-dx dim_x] [-dy dim_y] [-sl dim value]*\n\
                file\n\
        \n\
        where:\n\
            -upi scale          fig units per inch (default = 1200)\n\
            -x low_x            x and y offset of upper left corner (inches)\n\
            -y low_y            ...(default = 1)\n\
            -sz size            maximum side length of figure (in inches)\n\
                                ...(default = 5)\n\
            -dx dim_x           horizontal dimension (default = 0)\n\
            -dy dim_y           vertical dimension (default = 1)\n\
            -sv value           default slice value (default = 0)\n\
            -sl dim value       each such pair defines the value along the\n\
                                ...given dimension at which to slice.  This\n\
                                ...may be supplied for each dimension except\n\
                                ...dim_x and dim_y.\n\
            -ps pointsize       size of points in fig units (def = 10)\n\
            file                file (input=file.dmp, output=file.fig)\n";
		exit(0);
	}

	ANNbool fileSeen = ANNfalse;				// file argument seen?

	for (i = 1; i < argc; i++) {
		if (!strcmp(argv[i], "-upi")) {			// process -upi option
			sscanf(argv[++i], "%lf", &u_per_in);
		}
		else if (!strcmp(argv[i], "-x")) {		// process -x option
			sscanf(argv[++i], "%lf", &in_low_x);
		}
		else if (!strcmp(argv[i], "-y")) {		// process -y option
			sscanf(argv[++i], "%lf", &in_low_y);
		}
		else if (!strcmp(argv[i], "-sz")) {		// process -sz option
			sscanf(argv[++i], "%lf", &in_size);
		}
		else if (!strcmp(argv[i], "-dx")) {		// process -dx option
			sscanf(argv[++i], "%d", &dim_x);
		}
		else if (!strcmp(argv[i], "-dy")) {		// process -dy option
			sscanf(argv[++i], "%d", &dim_y);
		}
		else if (!strcmp(argv[i], "-sv")) {		// process -sv option
			sscanf(argv[++i], "%lf", &sl_val);
			set_slice_val(sl_val);				// set slice values
		}
		else if (!strcmp(argv[i], "-sl")) {		// process -sl option
			sscanf(argv[++i], "%d", &sl_dim);
			if (sl_dim < 0 || sl_dim >= MAX_DIM) {
				Error("Slice dimension out of bounds", ANNabort);
			}
			sscanf(argv[++i], "%lf", &slice_val[sl_dim]);
		}
		if (!strcmp(argv[i], "-ps")) {			// process -ps option
			sscanf(argv[++i], "%i", &pt_size);
		}
		else {									// must be file name
			fileSeen = ANNtrue;
			sscanf(argv[i], "%s", file_name);
			strcpy(infile_name, file_name);		// copy to input file name
	    	strcat(infile_name, DUMP_SUFFIX);
	    	strcpy(outfile_name, file_name);	// copy to output file name
	    	strcat(outfile_name, FIG_SUFFIX);
		}
	}

	if (!fileSeen) {							// no file seen
		Error("File argument is required", ANNabort);
	}

	ifile.open(infile_name, ios::in);			// open for reading
	if (!ifile) {
		Error("Cannot open input file", ANNabort);
	}
	ofile.open(outfile_name, ios::out);			// open for writing
	if (!ofile) {
		Error("Cannot open output file", ANNabort);
	}

	u_low_x = u_per_in * in_low_x;				// convert inches to fig units
	u_low_y = u_per_in * in_low_y;
	u_size  = u_per_in * in_size;

	strcpy(caption, argv[0]);					// copy command line to caption
	for (i = 1; i < argc; i++) {
		strcat(caption, " ");
		strcat(caption, argv[i]);
	}
}

//----------------------------------------------------------------------
// Graphics utilities for fig output
//
//		writeHeader				write header for fig file
//		writePoint				write a point
//		writeBox				write a box
//		writeLine				write a line
//----------------------------------------------------------------------

void writeHeader()
{
	ofile << FIG_HEAD << "\n"					// fig file header
		 << "Portrait\n"
		 << "Center\n"
		 << "Inches\n"
		 << (int) u_per_in << " 2\n";
}

void writePoint(ANNpoint p)						// write a single point
{
												// filled black point object
	ofile << "1 3 0 1 -1 7 0 0 0 0.000 1 0.0000 ";
	int cent_x = (int) TRANS_X(p);				// transform center coords
	int cent_y = (int) TRANS_Y(p);
	ofile << cent_x << " " << cent_y << " "		// write center, radius, bounds
		 << pt_size << " " << pt_size << " "
		 << cent_x << " " << cent_y << " "
		 << cent_x + pt_size << " " << cent_y + pt_size << "\n";
}

void writeBox(const ANNorthRect &r)				// write box
{
												// unfilled box object
	ofile << "2 2 0 1 -1 7 0 0 -1 0.000 0 0 -1 0 0 5\n";

	int p0_x = (int) TRANS_X(r.lo);				// transform endpoints
	int p0_y = (int) TRANS_Y(r.lo);
	int p1_x = (int) TRANS_X(r.hi);
	int p1_y = (int) TRANS_Y(r.hi);
	ofile << "\t"
		 << p0_x << " " << p0_y << " "			// write vertices
		 << p1_x << " " << p0_y << " "
		 << p1_x << " " << p1_y << " "
		 << p0_x << " " << p1_y << " "
		 << p0_x << " " << p0_y << "\n";
}

void writeLine(ANNpoint p0, ANNpoint p1)		// write line
{
												// unfilled line object
	ofile << "2 1 0 1 -1 7 0 0 -1 0.000 0 0 -1 0 0 2\n";

	int p0_x = (int) TRANS_X(p0);				// transform endpoints
	int p0_y = (int) TRANS_Y(p0);
	int p1_x = (int) TRANS_X(p1);
	int p1_y = (int) TRANS_Y(p1);
	ofile << "\t"
		 << p0_x << " " << p0_y << " "			// write vertices
		 << p1_x << " " << p1_y << "\n";
}

void writeCaption(								// write caption text
	const ANNorthRect	&bnd_box,				// bounding box
	char				*caption)				// caption
{
	if (!strcmp(caption, "\0")) return;			// null string?
	int px = (int) TRANS_X(bnd_box.lo);			// put .5 in. lower left
	int py = (int) (TRANS_Y(bnd_box.lo) + 0.50 * u_per_in); 
	ofile << "4 0 -1 0 0 0 20 0.0000 4 255 2000 ";
	ofile << px << " " << py << " " << caption << "\\001\n";
}

//----------------------------------------------------------------------
// overlap - test whether a box overlap slicing region
//
//		The slicing region is a 2-dimensional plane in space
//		which contains points (x1, x2, ..., xn) satisfying the
//		n-2 linear equalities:
//
//						xi == slice_val[i]		for i != dim_x, dim_y
//
//		This procedure returns true of the box defined by
//		corner points box.lo and box.hi overlap this plane.
//----------------------------------------------------------------------

ANNbool overlap(const ANNorthRect &box)
{
	for (int i = 0; i < dim; i++) {
		if (i != dim_x && i != dim_y &&
		   (box.lo[i] > slice_val[i] || box.hi[i] < slice_val[i]))
			return ANNfalse;
	}
	return ANNtrue;
}

//----------------------------------------------------------------------
// readTree, recReadTree - inputs tree and outputs figure
//
//		readTree procedure initializes things and then calls recReadTree
//		which does all the work.
//
//		recReadTree reads in a node of the tree, makes any recursive
//		calls as needed to input the children of this node (if internal)
//		and maintains the bounding box.  Note that the bounding box
//		is modified within this procedure, but it is the responsibility
//		of the procedure that it be restored to its original value
//		on return.
//
//		Recall that these are the formats.  The tree is given in
//		preorder.
//
//		Leaf node:
//				leaf <n_pts> <bkt[0]> <bkt[1]> ... <bkt[n-1]>
//		Splitting nodes:
//				split <cut_dim> <cut_val> <lo_bound> <hi_bound>
//		Shrinking nodes:
//				shrink <n_bnds>
//						<cut_dim> <cut_val> <side>
//						<cut_dim> <cut_val> <side>
//						... (repeated n_bnds times)
//
//		On reading a leaf we determine whether we should output the
//		cell's points (if dimension = 2 or this cell overlaps the
//		slicing region).  For splitting nodes we check whether the
//		current cell overlaps the slicing plane and whether the
//		cutting dimension coincides with either the x or y drawing
//		dimensions.  If so, we output the corresponding splitting
//		segment.
//----------------------------------------------------------------------

void recReadTree(ANNorthRect &box)
{
	char tag[STRING_LEN];						// tag (leaf, split, shrink)
	int n_pts;									// number of points in leaf
	int idx;									// point index
	int cd;										// cut dimension
	ANNcoord cv;								// cut value
	ANNcoord lb;								// low bound
	ANNcoord hb;								// high bound
	int n_bnds;									// number of bounding sides
	int sd;										// which side

	ifile >> tag;								// input node tag
	if (strcmp(tag, "leaf") == 0) {				// leaf node

		ifile >> n_pts;							// input number of points
												// check for overlap
		if (dim == 2 || overlap(box)) { 
			for (int i = 0; i < n_pts; i++) {	// yes, write the points
				ifile >> idx;
				writePoint(pts[idx]);
			}
		}
		else {									// input but ignore points
			for (int i = 0; i < n_pts; i++) {
				ifile >> idx;
			}
		}
	}
	else if (strcmp(tag, "split") == 0) {		// splitting node

		ifile >> cd >> cv >> lb >> hb;
		if (lb != box.lo[cd] || hb != box.hi[cd]) {
			Error("Bounding box coordinates are fishy", ANNwarn);
		}

		ANNcoord lv = box.lo[cd];				// save bounds for cutting dim
		ANNcoord hv = box.hi[cd];

		//--------------------------------------------------------------
		//	The following code is rather fragile so modify at your
		//	own risk.  We first decrease the high-end of the bounding
		//	box down to the cutting plane and then read the left subtree.
		//	Then we increase the low-end of the bounding box up to the
		//	cutting plane (thus collapsing the bounding box to a d-1
		//	dimensional hyperrectangle).  Then we draw the projection of
		//	its diagonal if it crosses the slicing plane.  This will have
		//	the effect of drawing its intersection on the slicing plane.
		//	Then we restore the high-end of the bounding box and read
		//	the right subtree.  Finally we restore the low-end of the
		//	bounding box, before returning.
		//--------------------------------------------------------------
		box.hi[cd] = cv;						// decrease high bounds
		recReadTree(box);						// read left subtree
												// check for overlap
		box.lo[cd] = cv;						// increase low bounds
		if (dim == 2 || overlap(box)) {			// check for overlap
			if (cd == dim_x || cd == dim_y) {	// cut through slice plane
				writeLine(box.lo, box.hi);		// draw cutting line
			}
		}
		box.hi[cd] = hv;						// restore high bounds

		recReadTree(box);						// read right subtree
		box.lo[cd] = lv;						// restore low bounds
	}
	else if (strcmp(tag, "shrink") == 0) {		// splitting node

		ANNorthRect inner(dim, box);			// copy bounding box
		ifile >> n_bnds;						// number of bounding sides
		for (int i = 0; i < n_bnds; i++) {
			ifile >> cd >> cv >> sd;			// input bounding halfspace
			ANNorthHalfSpace hs(cd, cv, sd);	// create orthogonal halfspace
			hs.project(inner.lo);				// intersect by projecting
			hs.project(inner.hi);
		}
		if (dim == 2 || overlap(inner)) {
			writeBox(inner);					// draw inner rectangle
		}
		recReadTree(inner);						// read inner subtree
		recReadTree(box);						// read outer subtree
	}
	else {
		Error("Illegal node type in dump file", ANNabort);
	}
}

void readTree(ANNorthRect &bnd_box)
{
	writeHeader();								// output header
	writeBox(bnd_box);							// draw bounding box
	writeCaption(bnd_box, caption);				// write caption
	recReadTree(bnd_box);						// do it
}

//----------------------------------------------------------------------
// readANN - read the ANN dump file
//
//		This procedure reads in the dump file.  See the format below.
//		It first reads the header line with version number.  If the
//		points section is present it reads them (otherwise just leaves
//		points = NULL), and then it reads the tree section.  It inputs
//		the bounding box and determines the parameters for transforming
//		the image to figure units.  It then invokes the procedure
//		readTree to do all the real work.
//
//		Dump File Format: <xxx> = coordinate value (ANNcoord)
//
//		#ANN <version number> <comments> [END_OF_LINE]
//		points <dim> <n_pts>			(point coordinates: this is optional)
//		0 <xxx> <xxx> ... <xxx>			(point indices and coordinates)
//		1 <xxx> <xxx> ... <xxx>
//		  ...
//		tree <dim> <n_pts> <bkt_size>
//		<xxx> <xxx> ... <xxx>			(lower end of bounding box)
//		<xxx> <xxx> ... <xxx>			(upper end of bounding box)
//				If the tree is null, then a single line "null" is
//				output.  Otherwise the nodes of the tree are printed
//				one per line in preorder.  Leaves and splitting nodes 
//				have the following formats:
//		Leaf node:
//				leaf <n_pts> <bkt[0]> <bkt[1]> ... <bkt[n-1]>
//		Splitting nodes:
//				split <cut_dim> <cut_val> <lo_bound> <hi_bound>
//		Shrinking nodes:
//				shrink <n_bnds>
//						<cut_dim> <cut_val> <side>
//						<cut_dim> <cut_val> <side>
//						... (repeated n_bnds times)
//
//		Note: Infinite lo_ and hi_bounds are printed as the special
//				values "-INF" and "+INF", respectively.  We do not
//				check for this, because the current version of ANN
//				starts with a finite bounding box if the tree is
//				nonempty.
//----------------------------------------------------------------------

void readANN()
{
	int j;
	char str[STRING_LEN];						// storage for string
    char version[STRING_LEN];					// storage for version
	int  bkt_size;								// bucket size

	ifile >> str;								// input header
	if (strcmp(str, "#ANN") != 0) {				// incorrect header
		Error("Incorrect header for dump file", ANNabort);
	}
    ifile.getline(version, STRING_LEN);			// get version (ignore)
	ifile >> str;								// get major heading
	if (strcmp(str, "points") == 0) {			// points section
		ifile >> dim;							// read dimension
		ifile >> n_pts;							// number of points
		pts = annAllocPts(n_pts, dim);			// allocate points
		for (int i = 0; i < n_pts; i++) {		// input point coordinates
			int idx;							// point index
			ifile >> idx;						// input point index
			if (idx < 0 || idx >= n_pts) {
				Error("Point index is out of range", ANNabort);
			}
			for (j = 0; j < dim; j++) {
				ifile >> pts[idx][j];			// read point coordinates
			}
		}
		ifile >> str;							// get next major heading
	}
	if (strcmp(str, "tree") == 0) {				// tree section
		ifile >> dim;							// read dimension
		if (dim_x > dim || dim_y > dim) {
			Error("Dimensions out of bounds", ANNabort);
		}
		ifile >> n_pts;							// number of points
		ifile >> bkt_size;						// bucket size (ignored)
												// read bounding box
		ANNorthRect bnd_box(dim);				// create bounding box
		for (j = 0; j < dim; j++) {
			ifile >> bnd_box.lo[j];				// read box low coordinates
		}
		for (j = 0; j < dim; j++) {
			ifile >> bnd_box.hi[j];				// read box high coordinates
		}
												// compute scaling factors
		double box_len_x = bnd_box.hi[dim_x] - bnd_box.lo[dim_x];
		double box_len_y = bnd_box.hi[dim_y] - bnd_box.lo[dim_y];
												// longer side determines scale
		if (box_len_x > box_len_y) scale = u_size/box_len_x;
		else					   scale = u_size/box_len_y;
												// compute offsets
		offset_x = u_low_x - scale*bnd_box.lo[dim_x];
		offset_y = u_low_y + scale*bnd_box.hi[dim_y];
		readTree(bnd_box);						// read the tree and process
	}
	else if (strcmp(str, "null") == 0) return;	// empty tree
	else {
		cerr << "Input string: " << str << "\n";
		Error("Illegal ann format.  Expecting section heading", ANNabort);
	}
}

//----------------------------------------------------------------------
// Main program
//
// Gets the command-line arguments and invokes the main scanning
// procedure.
//----------------------------------------------------------------------

main(int argc, char **argv)
{
	getArgs(argc, argv);						// get input arguments
	readANN();									// read the dump file
}