io.c

生成直角Steiner树的程序包

/***********************************************************************

	File:	io.c
	Rev:	b-1
	Date:	02/28/2001

	Copyright (c) 1993, 2001 by David M. Warme

************************************************************************

	Routines for Input/Output of point sets and coordinates.
	These routines insulate the rest of the system from the
	exact data type for "coord_t".

	To eliminate errors due to the basic properties of binary
	floating point representation, we scale (i.e., multiply)
	every coordinate by a power of 10 until every coordinate has
	an integral value.  This is done PRIOR to conversion into
	floating point form, and permits us to represent each
	coordinate (as well as delta X and delta Y values) exactly.
	This actually eliminates all numeric errors when computing
	and summing distances in the rectilinear metric (as long as
	the numbers do not exceed the basic precision of a double).

************************************************************************

	Modification Log:

	a-1:	02/20/93	warme
		: Created.
	b-1:	02/28/2001	warme
		: Changes for 3.1 release.
		: Moved Data_Num_Decimal_Places and min_precision
		:  into new struct scale_info.  Now passing this
		:  scale_info explicitly everywhere it is needed.
		: Changed "struct numlist" to be a partially converted
		:  scaled numeric form rather than textual form.
		: Accept scientific notation and leading + signs.
		: Support negative scale factors.

************************************************************************/

#include "steiner.h"


/*
 * Global Routines
 */

int			compute_scaling_factor (struct numlist *);
void			coord_to_string (char *, coord_t, struct scale_info *);
void			dist_to_string (char *, dist_t, struct scale_info *);
struct pset *		get_points (FILE *, struct scale_info *);
void			init_output_conversion (struct pset *,
						int,
						struct scale_info *);
struct numlist *	parse_line_of_numbers (FILE *);
coord_t			read_numlist (struct numlist *, struct scale_info *);
void			set_scale_info (struct scale_info *, int);


/*
 * Local Routines
 */

static struct numlist *	new_numlist (double, int, int);
static int		next_char (FILE *);
static struct numlist *	parse_input_numbers (FILE *);
static struct numlist *	parse_one_number (FILE *, bool);

/*
 * This routine reads in a set of points from the standard input.
 */

	struct pset *
get_points (

FILE *			fp,		/* IN - stream to read from */
struct scale_info *	sip		/* OUT - problem scaling info */
)
{
int			i;
int			n;
int			scaling_factor;
struct pset *		pts;
struct point *		p;
coord_t			x;
coord_t			y;
struct numlist *	list;
struct numlist *	nlp;

	/* Gather all numbers from the input in an accurate scaled form. */

	list = parse_input_numbers (fp);

	/* Determine the coordinate scaling factor to use.		*/
	scaling_factor = compute_scaling_factor (list);

	set_scale_info (sip, scaling_factor);

	n = 0;
	for (nlp = list; nlp NE NULL; nlp = nlp -> next) {
		++n;
	}

	if ((n & 1) NE 0) {
		(void) fprintf (stderr, "X coord without Y coord.\n");
		exit (1);
	}
	n >>= 1;

	pts = NEW_PSET (n);

	/* Zero out the entire point set. */
	ZERO_PSET (pts, n);

	pts -> n = n;

	n = 0;
	p = &(pts -> a [0]);

	while (list NE NULL) {
		nlp = list;
		list = list -> next;

		x = read_numlist (nlp, sip);

		if (list EQ NULL) {
			fatal ("get_points: Bug 1.");
		}

		nlp = list;
		list = list -> next;

		y = read_numlist (nlp, sip);

		p -> x		= x;
		p -> y		= y;
		p -> pnum	= ((pnum_t) n);

		++n;
		++p;
	}

	if (n NE pts -> n) {
		fatal ("get_points: Bug 2.");
	}

	return (pts);
}

/*
 * This routine "parses" all of the numbers in the input into a list
 * of partially converted/scaled numbers in binary (floating point) form.
 */

	static
	struct numlist *
parse_input_numbers (

FILE *		fp		/* IN - input stream to read from */
)
{
struct numlist *	p;
struct numlist *	root;
struct numlist **	hookp;

	root = NULL;
	hookp = &root;

	for (;;) {
		p = parse_one_number (fp, FALSE);
		if (p EQ NULL) break;

		*hookp = p;
		hookp = &(p -> next);
	}

	return (root);
}

/*
 * Read a single text line of numbers.  We ignore blank lines and
 * lines containing only a comment.  Otherwise, this routine collects
 * numbers in a linked list of numlist structures until the first
 * newline after at least one number is read.
 */

	struct numlist *
parse_line_of_numbers (

FILE *		fp		/* IN - file to read from */
)
{
struct numlist *	root;
struct numlist **	hookp;
struct numlist *	p;

	root = NULL;
	hookp = &root;

	for (;;) {
		p = parse_one_number (fp, TRUE);
		if (p NE NULL) {
			*hookp = p;
			hookp = &(p -> next);
			continue;
		}

		/* We read either EOF or a newline... */
		if (root NE NULL) {
			/* we have one or more numbers -- we don't	*/
			/* really care whether it was newline or EOF!	*/
			break;
		}
		if (feof (fp)) {
			/* It was EOF.  We are not going to get any	*/
			/* more numbers!				*/
			break;
		}
		/* ignore blank/comment line. */
	}

	return (root);
}

/*
 * This routine "parses" the next number from the input stream, and converts
 * it into binary form.  This form is "integerized" to minimize numeric
 * error caused by fractional digits.
 */

	static
	struct numlist *
parse_one_number (

FILE *		fp,		/* IN - input stream to read from */
bool		find_newline	/* IN - fail if newline seen before number */
)
{
int		num_dp;
int		ndig;
int		nsig;
int		nzero;
int		expon;
int		esign;
bool		dot_flag;
int		c;
char *		p;
double		sign;
double		num;
double		fnum;
double		fpow;

#define MAX_INT_DIGITS	14

	if (feof (fp)) return (NULL);

	sign = 1.0;

	do {
		c = next_char (fp);
		if (c < 0) return (NULL);
		if (c EQ '.') break;
		if (c EQ '-') {
			/* Note the minus sign and proceed. */
			sign = -1.0;
			c = next_char (fp);
			break;
		}
		if (c EQ '+') {
			c = next_char (fp);
			break;
		}
		if (ispunct (c)) {
			/* Strip comment line... */
			do {
				c = next_char (fp);
				if (c < 0) return (NULL);
			} while (c NE '\n');
			if (find_newline) return (NULL);
			continue;
		}
		if ((c EQ '\n') AND find_newline) return (NULL);
	} while (NOT isdigit (c));

	num = 0.0;
	fnum = 0.0;
	fpow = 1.0;

	ndig = 0;
	nsig = 0;
	nzero = 0;
	num_dp = 0;
	dot_flag = FALSE;

	for (;;) {
		if (c EQ '.') {
			if (dot_flag) {
				/* OOPS!  More than 1 decimal point	*/
				/* seen in a single number...  Just	*/
				/* terminate this number.		*/
				ungetc (c, fp);
				break;
			}
			dot_flag = TRUE;
		}
		else if (c EQ '0') {
			if (dot_flag) {
				++num_dp;
			}
			if (nsig <= 0) {
				/* Ignore: no non-zero digits yet seen. */
			}
			else {
				/* Don't process these if we don't have to. */
				++nzero;
			}
		}
		else if (isdigit (c)) {
			/* Process any deferred zero digits... */
			while (nzero > 0) {
				if (nsig < MAX_INT_DIGITS) {
					num *= 10.0;
					++nsig;
				}
				else {
					fpow *= 10.0;
					if (dot_flag) {
						--num_dp;
					}
				}
				--nzero;
			}
			if (nsig < MAX_INT_DIGITS) {
				num = 10.0 * num + (c - '0');
				++nsig;
				if (dot_flag) {
					++num_dp;
				}
			}
			else {
				fpow *= 10.0;
				fnum += (c - '0') / fpow;
			}
		}

		c = next_char (fp);
		if (c < 0) break;

		if ((NOT isdigit (c)) AND (c NE '.')) break;
	}

	expon = 0;

	if ((c EQ 'e') OR (c EQ 'E')) {
		/* Read the exponent. */
		esign = 1;
		c = next_char (fp);
		if (c EQ '+') {
			c = next_char (fp);
		}
		else if (c EQ '-') {
			esign = -1;
			c = next_char (fp);
		}
		while ((c >= 0) AND isdigit (c)) {
			expon = 10 * expon + (c - '0');
			c = next_char (fp);
		}
		expon *= esign;
	}
	if (c >= 0) {
		ungetc (c, fp);
	}

	/* Put sign, integral, and fractional parts together. */
	num = sign * (num + fnum);

	expon += nzero;
	expon -= num_dp;

	return (new_numlist (num, expon, nsig));
}

/*
 * This routine creates a scaled number list structure.
 */

	static
	struct numlist *
new_numlist (