/*
 * Generate images of interwoven rings.
 *
 * Usage: $0 < description > imagefile
 *
 * Input language is a stream of lines (keywords in lowercase,
 *  metasyntax uppercase, below).  Any line that is empty, all blank,
 *  or whose first nonblank character is NUL, ;, or #, is a comment and
 *  is ignored.  Other than that:
 *
 *	background COLOUR
 *	bg COLOUR
 *		The background has colour COLOUR.  See below for a
 *		discussion of colours.
 *
 *	ring CX CY RAD [OPTIONS]
 *		One ring has centre at (CX,CY).  RAD specifies the
 *		ring's basic radius.  OPTIONS specify various optional
 *		features:
 *
 *		width W
 *			The ring's width is W.
 *
 *		width *
 *			The ring's width is unspecified.
 *
 *		border B
 *			The ring's border width is B.
 *
 *		border *
 *			The ring's border width is unspecified.
 *
 *		colour COLOUR
 *		color COLOUR
 *			The body of the ring has colour COLOUR.  See
 *			below for a discussion of colours.
 *
 *		bordercolour COLOUR
 *		bordercolor COLOUR
 *		bcolour COLOUR
 *		bcolor COLOUR
 *		borderc COLOUR
 *		bc COLOUR
 *			The border of the ring has colour COLOUR.  See
 *			below for a discussion of colours.
 *
 *	ring default [OPTIONS]
 *		Just like the other form of `ring' except it specifies
 *		option settings for rings that don't specify them
 *		themselves.  This applies to ring lines from this line
 *		until the next ring default line, or end of file.  Note
 *		that a ring default line overrides a previous ring
 *		default line for only those options that are specified;
 *		to specify "not specified", use the * syntax.
 *
 *  In the abstract, a ring consists of all points in the plane whose
 *  distance from (CX,CY) is at least RAD-(W/2)-B and at most
 *  RAD+(W/2)+B.  Note that this is a closed set; it includes both
 *  borders.
 *
 * Default colours correspond to
 *	background 0
 *	ring default colour 0 bordercolour 1
 *
 * A COLOUR in the above syntax can be:
 *	- An X11-style hexadecimal spec
 *		#rgb
 *		#rrggbb
 *		#rrrgggbbb
 *		#rrrrggggbbbb
 *	- A single integer, in decimal
 *	- Three integers with slashes
 *	- A single floating-point number
 *	- Three floating-point numbers with slashes
 *  For the floating-point options, at least one number needs to have a
 *  decimal point to distinguish it from the similar integer syntax.
 *  Floating-point values map the range [0-1] to integer [0-256], but
 *  clip at 0 and 255 (so values <0 or >1 are pointless).  Except that
 *  they never generate PBM files, they are equivalent to the
 *  corresponding integer spec.  Integer specs use the range 0-255.
 *  X11-style hexadecimal RGB specs are scaled to the same 0-255 range
 *  and are counted as integer specs, except that they too never
 *  generate PBM files.
 *
 * If all colours are either integer 0 or integer 1, a PBM file is
 *  generated.  Otherwise, if X11-style specs with different primary
 *  values are used, or if either of the "three numbers with slashes"
 *  syntaxes is used, a PPM file is generated.  Otherwise, a PGM file
 *  is generated.  PGM or PPM files always use maxval 255, with pixel
 *  values scaled as necessary.
 *
 * Output is a PBM/PGM/PPM file, on stdout.  It contains the minimum
 *  rectangle that will hold all the rings, plus one pixel of padding
 *  on each edge.  In the units of the input, pixels are 1x1 squares.
 *
 * Arguably, we should antialias by, for pixels that aren't entirely a
 *  single colour, averaging the areas and colours that occur.  That's
 *  something for future work, though.
 */

#include <math.h>
#include <stdio.h>
#include <ctype.h>
#include <errno.h>
#include <stdlib.h>
#include <stdarg.h>
#include <strings.h>

#include "2dmath.h"

extern const char *__progname;

/*
 * A floating-point fuzz factor.
 */
#define EPSILON 1e-6

/*
 * The data structures here are a little confusing.
 *
 * A CROSSING represents a point where two rings cross, from the point
 *  of view of a specific one of the two rings involved.  Thus, two
 *  rings crossing leads to four CROSSINGs: one for each crossing point
 *  from each ring's point of view.  The ring the CROSSING is from the
 *  point of view of is called the `perspective ring'; the other ring
 *  involved is the `crossing ring'.
 */

/*
 * A SLANT represents which direction the crossing ring crosses the
 *  perspective ring in.  SLANT_IN is the crossing ring transitioning
 *  from outside to inside, as angle increases for the perspective
 *  ring; SLANT_OUT is the other way.  For example, consider two rings
 *  of radius 100 with centres at the same Y and 100 apart in X.  If
 *  the left ring is the perspective ring, the crossing above the
 *  centreline is SLANT_IN and the one below is SLANT_OUT.
 */
typedef enum {
	  SLANT_IN = 1,
	  SLANT_OUT
	  } SLANT;

/*
 * An OVERUNDER represents whether a ring goes over (visually in front
 *  of) another ring, or the converse.  See the comment on CROSSING.
 */
typedef enum {
	  OU_UNSET = 1,
	  OU_OVER,
	  OU_UNDER,
	  } OVERUNDER;

typedef struct ring RING;
typedef struct crossing CROSSING;
typedef struct cinfo CINFO;
typedef struct ca CA;
typedef struct csortops CSORTOPS;
typedef struct s3tmp S3TMP;
typedef struct colour COLOUR;

struct colour {
  unsigned char set;
  unsigned char v[3];
  } ;

/*
 * We want to sort lists of CROSSINGSs at least three ways, varying in
 *  where the link fields are stored and how they are compared.  This
 *  encapsulates the differences.
 */
struct csortops {
  // (*next)(c) returns a pointer to c's list link.
  CROSSING **(*next)(CROSSING *);
  // (*lt)(a,b) returns true iff a < b for this sort.
  int (*lt)(CROSSING *, CROSSING *);
  } ;

/*
 * r is the perspective ring.  or is the crossing ring.  a is the
 *  angle, from the X axis to this crossing point, as seen from the
 *  perspective ring's centre.  slant is this crossing's slant.
 *  overunder describes how this crossing is handled in the weave;
 *  OU_OVER if the perspective ring goes over (visually in front of)
 *  the crossing ring, OU_UNDER if under.  other is the CROSSING
 *  describing the same crossing point with the roles of the
 *  perspective ring and the crossing ring swapped.  flink and blink
 *  form a doubly-linked list of all CROSSINGs for a given perspective
 *  ring; this list's root is the ring's crossings, and the list is
 *  two-ended, not circular.  tmp is a pointer to arbitrary data, used
 *  as a temporary where necessary.
 */
struct crossing {
  RING *r;
  RING *or;
  double a;
  SLANT slant;
  OVERUNDER weave;
  CROSSING *other;
  CROSSING *flink;
  CROSSING *blink;
  void *tmp;
  } ;

/*
 * The four angles for the inner (ia?) and outer (oa?) crossing points
 *  for a CROSSING.  The ?a1 angles are the more clockwise, the ?a2
 *  angles the more counterclockwise.
 */
struct ca {
  double ia1;
  double ia2;
  double oa1;
  double oa2;
  } ;

/*
 * A ring.  They are kept in a linked list, linked by link.  c is the
 *  centre.  r is the nominal (middle-of-the-ring) radius.  flags is
 *  flag bits: (HAVE/UNSPEC)_(W/B) are used during setup, with HAVE_x
 *  indicating whether x has been set and, if so, UNSPEC_x indicating
 *  that it's set to "not specified"; xxx_W is width and xxx_B is
 *  border width.  FLAG is a temporary flag used, eg, when computing
 *  the weave.  w holds the width, meaningful only iff HAVE_W; b the
 *  borderwidth (iff HAVE_B).  Once reading in is complete, w and b are
 *  always valid and their flag bits can be ignored.  id is the ring's
 *  index, for PAIRFLAG() and CROSS().  ir and or are the inner and
 *  outer radii, as computed from r, w, and b.  crossing_h and
 *  crossing_t are the head (_h) and tail (_t) of the ring's list of
 *  CROSSINGs.  tlink is used for temporary lists, eg when computing
 *  the weave.
 */
struct ring {
  RING *link;
  XY c;
  double r;
  unsigned int flags;
#define RF_HAVE_W   0x00000001
#define RF_UNSPEC_W 0x00000002 // meaningful only if RF_HAVE_W
#define RF_HAVE_B   0x00000004
#define RF_UNSPEC_B 0x00000008 // meaningful only if RF_HAVE_B
#define RF_FLAG     0x00000010
  double w;
  double b;
  COLOUR wcol;
  COLOUR bcol;
  int id;
  double ir;
  double or;
  double ir2;
  double irb2;
  double orb2;
  double or2;
  CROSSING *crossing_h;
  CROSSING *crossing_t;
  RING *tlink;
  } ;

/*
 * Temporary per-CROSSING data used by check_step3().
 */
struct s3tmp {
  CROSSING *link;
#define S3TLINK(c) (((S3TMP *)(c)->tmp)->link)
  CA ca;
#define S3TCA(c) (((S3TMP *)(c)->tmp)->ca)
  } ;

static RING defring;
static RING *rings;
static int nrings;
static void (*badline_handler)(char *);
/*
 * We always make sure PAIRFLAG(a,b) and PAIRFLAG(b,a) are equal.
 *
 * CROSS(a,b)[] are the CROSSINGs for perspective ring a, crossing ring
 *  b, with [0] the SLANT_IN and [1] the SLANT_OUT.
 */
static unsigned char *pairflags;
#define PAIRFLAG(a,b) pairflags[((a)*nrings)+(b)]
#define PF_CROSS 0x01
static CROSSING *(*crossings)[2];
#define CROSS(a,b) crossings[((a)*nrings)+(b)]
static int o_w;
static int o_h;
static int o_x0;
static int o_y0;
static RING *wpend;
static COLOUR bgcol = { .set = 0 };
#define OTYPE_PBM 'b'
#define OTYPE_PGM 'g'
#define OTYPE_PPM 'p'
static char otype = OTYPE_PBM;
static int debug = 0;
static const char *infile = 0;
static int malsuppress = 1;

#define Cisspace(x) isspace((unsigned char)(x))

/*
 * malloc()-family debugging.  Link with --wrap malloc --wrap calloc
 *  --wrap realloc --wrap free and then run with whatever's needed to
 *  set malsuppress to 0 (-memtrace at this writing).  Link without the
 *  --wrap options and malsuppress gets ignored; run without the
 *  options and the wrappers just pass calls on to the real routines.
 */

void *__wrap_malloc(size_t);
void *__real_malloc(size_t);
void *__wrap_calloc(size_t, size_t);
void *__real_calloc(size_t, size_t);
void *__wrap_realloc(void *, size_t);
void *__real_realloc(void *, size_t);
void __wrap_free(void *);
void __real_free(void *);

void *__wrap_malloc(size_t n)
{
 void *p;

 if (malsuppress) return(__real_malloc(n));
 malsuppress = 1;
 fprintf(stderr,"malloc(%llu)\n",(unsigned long long int)n);
 p = __real_malloc(n);
 fprintf(stderr,"-> %p\n",p);
 malsuppress = 0;
 return(p);
}

void *__wrap_calloc(size_t n1, size_t n2)
{
 void *p;

 if (malsuppress) return(__real_calloc(n1,n2));
 malsuppress = 1;
 fprintf(stderr,"calloc(%llu,%llu)\n",(unsigned long long int)n1,(unsigned long long int)n2);
 p = __real_calloc(n1,n2);
 fprintf(stderr,"-> %p\n",p);
 malsuppress = 0;
 return(p);
}

void *__wrap_realloc(void *p, size_t n)
{
 void *r;

 if (malsuppress) return(__real_realloc(p,n));
 malsuppress = 1;
 fprintf(stderr,"realloc(%p,%llu)\n",p,(unsigned long long int)n);
 r = __real_realloc(p,n);
 fprintf(stderr,"-> %p\n",r);
 malsuppress = 0;
 return(r);
}

void __wrap_free(void *p)
{
 if (malsuppress) return(__real_free(p));
 malsuppress = 1;
 fprintf(stderr,"free(%p)\n",p);
 __real_free(p);
 malsuppress = 0;
}

// END malloc-family debugging

/*
 * Angle range reduction ("arr").  These bring an angle on which
 *  arithmetic has been done back into range.  There are two forms:
 *  arrb, "balanced", which brings it into the range -pi to pi, and
 *  arrp, "positive", which brings it into the range 0 to 2pi.
 */

static double arrb(double a)
{
 while (a > M_PI) a -= 2 * M_PI;
 while (a < -M_PI) a += 2 * M_PI;
 return(a);
}

static double arrp(double a)
{
 while (a > 2*M_PI) a -= 2 * M_PI;
 while (a < 0) a += 2 * M_PI;
 return(a);
}

/*
 * Return a text string for a SLANT.
 */
static const char *slant_text(SLANT s)
{
 switch (s)
  { case SLANT_IN:
       return("IN");
       break;
    case SLANT_OUT:
       return("OUT");
       break;
  }
 abort();
}

/*
 * Read a line of input from f.  Return it as a string.  The string is
 *  owned by getline and may not be valid after the next call to
 *  getline.
 *
 * If f ends with a partial line - that is, if there is text but the
 *  last character is not a newline - then a complaint is printed and
 *  the missing newline is effectively supplied.
 */
static const char *getline(FILE *f)
{
 static char *b = 0;
 static int a = 0;
 int l;
 int ch;

 void savec(char c)
  { if (l >= a) b = realloc(b,a=l+8);
    b[l++] = c;
  }

 l = 0;
 while (1)
  { ch = getc(f);
    if (ch == EOF)
     { if (l > 0)
	{ savec('\0');
	  fprintf(stderr,"%s: missing newline supplied at EOF\n",__progname);
	  return(b);
	}
       return(0);
     }
    if (ch == '\n')
     { savec('\0');
       return(b);
     }
    savec(ch);
  }
}

/*
 * Report a bad input line.  Arguments are a printf-style format and
 *  arguments; it will have __progname prepended to it and the full
 *  line text, and a newline, appended to it.
 */
static void badline(const char *, ...)
	__attribute__((__format__(__printf__,1,2),__noreturn__));
static void badline(const char *fmt, ...)
{
 char *s;
 va_list ap;

 va_start(ap,fmt);
 vasprintf(&s,fmt,ap);
 va_end(ap);
 (*badline_handler)(s);
 abort();
}

/*
 * Promote otype to be at least as general as the type indicated by the
 *  argument.  Since we support only three types, this is fairly
 *  simple.
 */
static void promote_otype(char t)
{
 switch (t)
  { case OTYPE_PBM:
       break;
    case OTYPE_PGM:
       if (t == OTYPE_PBM) otype = OTYPE_PGM;
       break;
    case OTYPE_PPM:
       otype = OTYPE_PPM;
       break;
    default:
       abort();
       break;
  }
}

/*
 * Helper for line_ring() and line_bg(): parse a colour spec.
 *
 * This either returns (on success) or calls badline() (on failure).
 *  It assumes leading whitespace has already been stripped from s,
 *  that n > 0, and that s[n] exists and is either NUL or whitespace.
 */
static void parse_colour_spec(const char *s, int n, COLOUR *c)
{
 int n2;
 int n3;
 unsigned long long int xv;
 float fr;
 float fg;
 float fb;
 int ir;
 int ig;
 int ib;

 if (memchr(s,'.',n))
  { // Dot present, must be floating-point (or error).
    n2 = -1;
    n3 = -1;
    sscanf(s,"%g%n/%g/%g%n",&fr,&n2,&fg,&fb,&n3);
    if (n3 > 0)
     { if (n3 < n) badline("junk after floating-point numbers in colour spec");
       if (n3 != n) abort(); // impossible: whitespace absent?
       ir = fr * 256;
       if (ir < 0) ir = 0; else if (ir > 255) ir = 255;
       ig = fg * 256;
       if (ig < 0) ig = 0; else if (ig > 255) ig = 255;
       ib = fb * 256;
       if (ib < 0) ib = 0; else if (ib > 255) ib = 255;
       promote_otype(OTYPE_PPM);
     }
    else if (n2 > 0)
     { if (n2 < n) badline("junk after floating-point number in colour spec");
       if (n2 != n) abort(); // impossible: whitespace absent?
       ir = fr * 256;
       if (ir < 0) ir = 0; else if (ir > 255) ir = 255;
       ig = ir;
       ib = ir;
       promote_otype(OTYPE_PGM);
     }
    else
     { badline("invalid floating-point colour spec");
     }
    c->v[0] = ir;
    c->v[1] = ig;
    c->v[2] = ib;
    c->set = 1;
    return;
  }
 n2 = -1;
 n3 = -1;
 sscanf(s,"# %n%llx%n",&n3,&xv,&n2);
 if (n2 > 0)
  { // Begins with #, must be X11-style spec (or error).
    if (n3 != 1) abort(); // impossible: whitespace present?
    if (n2 != n) abort(); // impossible: whitespace present?
    switch (n2)
     { default:
	  badline("bad number of digits in X11-style colour spec");
	  break;
       case 4:
	  c->v[0] = ((xv >> 8) & 15) * 0x11;
	  c->v[1] = ((xv >> 4) & 15) * 0x11;
	  c->v[2] = ( xv       & 15) * 0x11;
	  break;
       case 7:
	  c->v[0] = (xv >> 16) & 255;
	  c->v[1] = (xv >>  8) & 255;
	  c->v[2] =  xv        & 255;
	  break;
       case 10:
	  c->v[0] = (xv >> 28) & 255;
	  c->v[1] = (xv >> 16) & 255;
	  c->v[2] = (xv >>  4) & 255;
	  break;
       case 13:
	  c->v[0] = (xv >> 32) & 255;
	  c->v[1] = (xv >> 24) & 255;
	  c->v[2] = (xv >> 16) & 255;
	  break;
     }
    c->set = 1;
    promote_otype(((c->v[0]!=c->v[1])||(c->v[0]!=c->v[2]))?OTYPE_PPM:OTYPE_PGM);
    return;
  }
 // Must be integer.
 n2 = -1;
 n3 = -1;
 sscanf(s,"%d%n/%d/%d%n",&ir,&n2,&ig,&ib,&n3);
 if (n3 > 0)
  { if (n3 < n) badline("junk after int/int/int colour spec");
    if (n3 != n) abort(); // impossible: whitespace present?
    if (ir < 0) ir = 0; else if (ir > 255) ir = 255;
    if (ig < 0) ig = 0; else if (ig > 255) ig = 255;
    if (ib < 0) ib = 0; else if (ib > 255) ib = 255;
    promote_otype('p');
  }
 else if (n2 > 0)
  { if (n2 < n) badline("junk after int/int/int colour spec");
    if (n2 != n) abort(); // impossible: whitespace present?
    if (ir < 0) ir = 0; else if (ir > 255) ir = 255;
    ig = ir;
    ib = ir;
    promote_otype((ir>1)?OTYPE_PGM:OTYPE_PBM);
  }
 else
  { badline("incomprehensible colour spec");
  }
 c->v[0] = ir;
 c->v[1] = ig;
 c->v[2] = ib;
 c->set = 1;
}

/*
 * Helper for line_ring(): process a border colour spec.
 */
static int ring_bordercolour(RING *r, const char *text)
{
 int n;
 int n2;

 if (r->bcol.set) badline("bad ring line (border colour specified twice)");
 n = -1;
 sscanf(text," %n%*s%n",&n2,&n);
 if ((n < 0) || (n == n2)) badline("bad ring line (missing border colour spec)");
 parse_colour_spec(text+n2,n-n2,&r->bcol);
 return(n);
}

/*
 * Helper for line_ring(): process a ring colour spec.
 */
static int ring_colour(RING *r, const char *text)
{
 int n;
 int n2;

 if (r->wcol.set) badline("bad ring line (colour specified twice)");
 n = -1;
 sscanf(text," %n%*s%n",&n2,&n);
 if ((n < 0) || (n == n2)) badline("bad ring line (missing colour spec)");
 parse_colour_spec(text+n2,n-n2,&r->wcol);
 return(n);
}

/*
 * Process a `ring' line.
 */
static void line_ring(const char *body)
{
 int n;
 int o0;
 int o;
 int def;
 RING rval;
 RING *r;

 def = 0;
 n = -1;
 sscanf(body,"%lg%lg%lg%n",&rval.c.x,&rval.c.y,&rval.r,&n);
 if (n < 0)
  { sscanf(body," default %n",&n);
    if (n < 0) badline("bad ring line (can't scan centre and radius)");
    def = 1;
  }
 else
  { if ( (fabs(rval.c.x) > 10000) ||
	 (fabs(rval.c.y) > 10000) ) badline("unreasonable centre position");
    if ( (rval.r < 1) ||
	 (rval.r > 10000) ) badline("unreasonable radius");
  }
 rval.flags = 0;
 rval.w = 0;
 rval.b = 0;
 rval.wcol.set = 0;
 rval.bcol.set = 0;
 o = n;
 while (1)
  { while (body[o] && Cisspace(body[o])) o ++;
    if (! body[o]) break;
    o0 = o;
    while (body[o] && !Cisspace(body[o])) o ++;
    do <"cmddone">
     { switch (o - o0)
	{ case 2:
	     if (! bcmp(body+o0,"bc",2))
	      { n = ring_bordercolour(&rval,body+o);
		break <"cmddone">;
	      }
	     break;
	  case 5:
	     switch (body[o0])
	      { case 'c':
		   if (! bcmp(body+o0,"color",5))
		    { n = ring_colour(&rval,body+o);
		      break <"cmddone">;
		    }
		   break;
		case 'w':
		   if (! bcmp(body+o0,"width",5))
		    { if (rval.flags & RF_HAVE_W) badline("bad ring line (width specified twice)");
		      n = -1;
		      sscanf(body+o,"%lg%n",&rval.w,&n);
		      if (n < 0)
		       { sscanf(body," * %n",&n);
			 if (n < 0) badline("bad ring line (can't scan width value)");
			 rval.flags |= RF_UNSPEC_W;
		       }
		      else if (rval.w < 0)
		       { badline("bad ring line (negative width value)");
		       }
		      rval.flags |= RF_HAVE_W;
		      break <"cmddone">;
		    }
		   break;
	      }
	     break;
	  case 6:
	     switch (body[o0+2])
	      { case 'o':
		   if (! bcmp(body+o0,"bcolor",6))
		    { n = ring_bordercolour(&rval,body+o);
		      break <"cmddone">;
		    }
		   break;
		case 'r':
		   if (! bcmp(body+o0,"border",6))
		    { if (rval.flags & RF_HAVE_B) badline("bad ring line (border specified twice)");
		      n = -1;
		      sscanf(body+o,"%lg%n",&rval.b,&n);
		      if (n < 0)
		       { sscanf(body," * %n",&n);
			 if (n < 0) badline("bad ring line (can't scan border value)");
			 rval.flags |= RF_UNSPEC_B;
		       }
		      else if (rval.b < 0)
		       { badline("bad ring line (negative border value)");
		       }
		      rval.flags |= RF_HAVE_B;
		      break <"cmddone">;
		    }
		   break;
		case 'l':
		   if (! bcmp(body+o0,"colour",6))
		    { n = ring_colour(&rval,body+o);
		      break <"cmddone">;
		    }
		   break;
	      }
	     break;
	  case 7:
	     switch (body[o0+1])
	      { case 'c':
		   if (! bcmp(body+o0,"bcolour",7))
		    { n = ring_bordercolour(&rval,body+o);
		      break <"cmddone">;
		    }
		   break;
		case 'o':
		   if (! bcmp(body+o0,"borderc",7))
		    { n = ring_bordercolour(&rval,body+o);
		      break <"cmddone">;
		    }
		   break;
	      }
	     break;
	  case 11:
	     if (! bcmp(body+o0,"bordercolor",11))
	      { n = ring_bordercolour(&rval,body+o);
		break <"cmddone">;
	      }
	     break;
	  case 12:
	     if (! bcmp(body+o0,"bordercolour",12))
	      { n = ring_bordercolour(&rval,body+o);
		break <"cmddone">;
	      }
	     break;
	}
       badline("bad ring line (unrecognized option `%.*s')",o-o0,body+o0);
     } while (0);
    o += n;
  }
 if (def)
  { if (rval.flags & RF_HAVE_W)
     { defring.flags = (defring.flags & ~RF_UNSPEC_W) | (rval.flags & RF_UNSPEC_W) | RF_HAVE_W;
       defring.w = rval.w;
     }
    if (rval.flags & RF_HAVE_B)
     { defring.flags = (defring.flags & ~RF_UNSPEC_B) | (rval.flags & RF_UNSPEC_B) | RF_HAVE_B;
       defring.b = rval.b;
     }
    if (rval.wcol.set) defring.wcol = rval.wcol;
    if (rval.bcol.set) defring.bcol = rval.bcol;
  }
 else
  { if (! (rval.flags & RF_HAVE_W))
     { rval.w = defring.w;
       rval.flags |= (defring.flags & RF_UNSPEC_W) | RF_HAVE_W;
     }
    if (! (rval.flags & RF_HAVE_B))
     { rval.b = defring.b;
       rval.flags |= (defring.flags & RF_UNSPEC_B) | RF_HAVE_B;
     }
    if (! rval.wcol.set) rval.wcol = defring.wcol;
    if (! rval.bcol.set) rval.bcol = defring.bcol;
    rval.ir = rval.r - (rval.w/2) - rval.b;
    if (rval.ir < 0) badline("unreasonable width and border for radius");
    rval.or = rval.r + (rval.w/2) + rval.b;
    rval.ir2 = rval.ir * rval.ir;
    rval.irb2 = (rval.r - (rval.w/2)) * (rval.r - (rval.w/2));
    rval.orb2 = (rval.r + (rval.w/2)) * (rval.r + (rval.w/2));
    rval.or2 = rval.or * rval.or;
    rval.id = nrings++;
    r = malloc(sizeof(RING));
    *r = rval;
    r->link = rings;
    rings = r;
  }
}

/*
 * Process a `bg'/`background' line.
 */
static void line_bg(const char *text)
{
 int l;

 while (*text && Cisspace(*text)) text ++;
 if (! *text) badline("bad background line (missing colour spec)");
 l = strlen(text);
 while ((l > 0) && Cisspace(text[l-1])) l --;
 if (l < 1) abort(); // impossible - checked all-whitespace above
 parse_colour_spec(text,l,&bgcol);
}

/*
 * Process an input line.  This recognizes comments; non-comment lines
 *  have their first whitespace-delimited word taken as a keyword
 *  identifying the line type.
 */
static void process_line(const char *l)
{
 int x;
 int x0;

 x = 0;
 while (l[x] && Cisspace(l[x])) x ++;
 switch (l[x])
  { case '\0': case '#': case ';': return; break;
  }
 x0 = x;
 while (l[x] && !Cisspace(l[x])) x ++;
 do <"handled">
  { switch (x - x0)
     { case 2:
	  if (! bcmp(l+x0,"bg",2))
	   { line_bg(l+x);
	     break <"handled">;
	   }
	  break;
       case 4:
	  if (! bcmp(l+x0,"ring",4))
	   { line_ring(l+x);
	     break <"handled">;
	   }
	  break;
       case 10:
	  if (! bcmp(l+x0,"background",10))
	   { line_bg(l+x);
	     break <"handled">;
	   }
	  break;
     }
    badline("unrecognized line keyword `%.*s'",x-x0,l+x0);
  } while (0);
}

/*
 * Read and process input.  Erroneous input lines end up calling bl(),
 *  here, via badline_handler; this reports the error, records that it
 *  occurred, and throws back to the top level of the read loop.
 */
static void read_input(void)
{
 __label__ bl_throw;

 FILE *f;
 const char *l;
 int ierrs;

 void bl(char *s)
  { fprintf(stderr,"%s: %s: %s\n",__progname,s,l);
    free(s);
    ierrs = 1;
    goto bl_throw;
  }

 if (infile)
  { f = fopen(infile,"r");
    if (! f)
     { fprintf(stderr,"%s: can't open %s: %s\n",__progname,infile,strerror(errno));
       exit(1);
     }
  }
 else
  { f = stdin;
  }
 badline_handler = &bl;
 ierrs = 0;
 while (1)
  { l = getline(f);
    if (! l) break;
    process_line(l);
bl_throw:;
  }
 if (ierrs) exit(1);
 if (f != stdin) fclose(f);
}

/*
 * Print a ring, for purposes such as complaining about intersections.
 */
static void print_ring(RING *r, FILE *to)
{
 fprintf(to,"ring %d (%g,%g) %g",r->id,r->c.x,r->c.y,r->r);
 if (r->flags & RF_UNSPEC_W) fprintf(to," width *"); else fprintf(to," width %g",r->w);
 if (r->flags & RF_UNSPEC_B) fprintf(to," border *"); else fprintf(to," border %g",r->b);
}

/*
 * We've found a three-ring intersection.  Gripe about it.
 */
static void triple_overlap(RING *r1, RING *r2, RING *r3)
{
 fprintf(stderr,"Triple ring overlap\n\t");
 print_ring(r1,stderr);
 fprintf(stderr,"\n\t");
 print_ring(r2,stderr);
 fprintf(stderr,"\n\t");
 print_ring(r3,stderr);
 fprintf(stderr,"\n");
 exit(1);
}

static void dump_rings(void)
{
 RING *r;

 for (r=rings;r;r=r->link)
  { print_ring(r,stderr);
    fprintf(stderr,"\n");
  }
}

/*
 * Check the set of rings, step 1.  We require that any two rings have
 *  either zero or two disjoint crossing regions.
 *
 * Some PS code that illustrates the ways two rings can interact
 *  (atob | bunzip2):
 *
xbtoa Begin
6<\%_0gSqh;csoTo@EsBXkA4)0L>mAi'6\fl<jZX%o`QHBOo1%(kWJKL6s[AacJ84"t!%R0O
^Z=+Cnpi9UZl-8tJkP)cKO/1,Jt3L5&BQObb_IBPE#A,fh=$->HqFkq[*4N<hb*En1^f9(kI
3<UP,`=M2>UbSZiN/OEp.+Ib-`s(hBNK,O#b604J"?G,W1\BC4['b\Q02BB*o1F69<"-^2dk
#WKdd#qRBC?pNd/N2"=YkQD*AJC<me;Y>s^L)dfXf>Mr9bu9hJh+/0Ll<LnYlbp^K\Cbs>&=
UK8H?jRV)=[ji+gF/VYaDU?qJ0))S/\.'Jm[[8gtoA3T>^NEuQ+P&n#ZYKc-..^4o\Q);d52
:7\]6',F.d,p]5!Aot,=k*C]dK<15a#bjKjKC&M"X<r-\#JYpYT$"_N2LWnZE8)5L_6O+F8<
I;;2r^aojRJB(\JaNT67>!K/B5MdJVJM>L`f![g-gO("#0Oqrr/O']KK(1motlnF>,0FNtT:
FH44B+U-dX76&:)QC2#6-U`<9=VTToGR!?F/EnJ8rStlgM#30[j2Nf8G68"op]Z^[`$\Y2lP
T)B0KuN#bfdVN!6$h`\$4L>&"^I"#MST3DjGIoM+>2R7XoJG%
xbtoa End N 497 1f1 E 30 S df90 R 9c8a68a0
 *
 * Conveniently, all we need to make this decision is the distance
 *  between the rings' centres and their inner and outer radii.
 */
static void check_step1(void)
{
 RING *a;
 RING *b;
 double cd;
 double ira;
 double ora;
 double irb;
 double orb;

 for (a=rings;a;a=a->link)
  { ira = a->r - (a->w / 2) - a->b;
    ora = a->r + (a->w / 2) + a->b;
    for (b=rings;b;b=b->link)
     { if (b == a) continue;
       cd = norm2(sub2(a->c,b->c));
       irb = b->r - (b->w / 2) - b->b;
       orb = b->r + (b->w / 2) + b->b;
       /*
	* Two rings are OK if (a) they are too far apart to touch at
	*  all, or (b) one of them is entirely within the other's
	*  central space, or (c) each of them, where it crosses the
	*  line between their centres, is inside the other's central
	*  space.  Test (c) amounts to looking at the intervals where
	*  they cross the line between their centres and seeing if
	*  those intervals look like
	*
	*	---aaa-------bbbbb---aaa--------------bbbbb
	*
	*  where each of them falls into the gap in the other.
	*/
       // Case (a)?
       if (cd >= ora+orb) continue;
       // Case (b)?
       if ((cd+ora <= irb) || (cd+orb <= ira)) continue;
       /*
	* Case (c)?
	*
	* Testing this is less obvious.
	*
	*          a centre v                 v b centre
	*                   |-----------------| cd
	* ora               |-----------|     |
	* ira               |---------|       |
	* ------aaa---------+--bbbbb--aaa-----+----------bbbbb----
	* irb                      |----------| irb
	* orb                  |--------------| orb
	*
	* We test "is left edge of first b interval to the right of
	*  right edge of first a interval" && "is right edge of first b
	*  interval to the left of left edge of second a interval" &&
	*  the same things with a and b swapped.
	*/
       if ( (cd-orb >= -ira) && (cd-irb <= ira) &&
	    (cd-ora >= -irb) && (cd-ira <= irb) )
	{ PAIRFLAG(a->id,b->id) |= PF_CROSS;
	  PAIRFLAG(b->id,a->id) |= PF_CROSS;
	  continue;
	}
       // Must be some kind of forbidden overlap.
       fprintf(stderr,"Invalid overlap:\n\t");
       print_ring(a,stderr);
       fprintf(stderr,"\n\t");
       print_ring(b,stderr);
       fprintf(stderr,"\n");
       exit(1);
     }
  }
}

/*
 * Link a CROSSING into its perspective ring's crossings list.
 */
static void crossing_linkin(CROSSING *c)
{
 c->flink = c->r->crossing_h;
 c->blink = 0;
 if (c->flink) c->flink->blink = c; else c->r->crossing_t = c;
 c->r->crossing_h = c;
}

static void print_crossing_list(CROSSING *, CROSSING **(*)(CROSSING *))
	__attribute__((__unused__));
static void print_crossing_list(CROSSING *list, CROSSING **(*next)(CROSSING *))
{
 CROSSING *e;

 for (e=list;e;e=*(*next)(e)) printf(" %p",(void *)e);
}

/*
 * Sort a ring's list of CROSSINGs, according to ops.
 */
static CROSSING *sort_crossings(CROSSING *list, const CSORTOPS *ops)
{
 CROSSING *a;
 CROSSING *b;
 CROSSING *t;
 CROSSING **tail;

 if (!list || !*(*ops->next)(list)) return(list);
 a = 0;
 b = 0;
 while (list)
  { t = list;
    list = *(*ops->next)(t);
    *(*ops->next)(t) = a;
    a = b;
    b = t;
  }
 a = sort_crossings(a,ops);
 b = sort_crossings(b,ops);
 tail = &list;
 while (1)
  { if (a && (!b || (*ops->lt)(a,b)))
     { t = a;
       a = *(*ops->next)(a);
     }
    else if (b)
     { t = b;
       b = *(*ops->next)(b);
     }
    else
     { break;
     }
    *tail = t;
    tail = (*ops->next)(t);
  }
 *tail = 0;
 return(list);
}

/*
 * We've been treating r's crossings list as a singly-linked list.
 *  This means the blink fields and r's crossings_t are trash.  Fix
 *  them up.
 */
static void backlink_fixup(RING *r)
{
 CROSSING *c;
 CROSSING *p;

 p = 0;
 for (c=r->crossing_h;c;c=c->flink)
  { c->blink = p;
    p = c;
  }
 r->crossing_t = p;
}

/*
 * Functions and CSORTOPS for sorting by flink and nominal angle.
 */

static CROSSING **cross_flink(CROSSING *c)
{
 return(&c->flink);
}

static int cross_lt_a(CROSSING *a, CROSSING *b)
{
 return(a->a<b->a);
}

static const CSORTOPS csops_nominal = { .next = &cross_flink, .lt = &cross_lt_a };

/*
 * Functions and CSORTOPS for sorting in step3.
 */

static CROSSING **cross_s3link(CROSSING *c)
{
 return(&S3TLINK(c));
}

static int cross_lt_s3_i(CROSSING *a, CROSSING *b)
{
 return( S3TCA(a).ia1 < S3TCA(b).ia1 );
}

static const CSORTOPS csops_step3i = { .next = &cross_s3link, .lt = &cross_lt_s3_i };

static int cross_lt_s3_o(CROSSING *a, CROSSING *b)
{
 return( S3TCA(a).oa1 < S3TCA(b).oa1 );
}

static const CSORTOPS csops_step3o = { .next = &cross_s3link, .lt = &cross_lt_s3_o };

/*
 * Check the set of rings, step 2.  We require that there be no point
 *  that belongs to three different rings.  Because this is called
 *  after check_step1() has passed, we know that two-ring intersections
 *  occur in only certain ways.
 *
 * This function checks for some kinds of three-ring overlap and also
 *  prepares the CROSS()[] data structures for use by the check_step3()
 *  and the rendering code.
 *
 * Actually, because rings are closed, we are willing to accept single
 *  points that belong to three rings, but there must be no open ball
 *  belonging to three rings; equivalently (because our set of rings is
 *  finite), the set of points belonging to more than two rings must be
 *  finite.
 *
 * That's the theory.  Numerical errors can provoke slight hiccups
 *  either way.  We don't worry about that; if there somehow is a pixel
 *  that numerically belongs to more than two rings, we just let it end
 *  up getting rendered as whatever is most convenient for the
 *  rendering code.  The major reason we want to forbid spots that
 *  belong to more than two rings is that they make the over-under
 *  alternation that gives us the weave effect difficult to define.  As
 *  long as each ring can be divided into a sequence of segments, each
 *  of which either belongs to only this ring or to exactly one other
 *  ring, with an even number of the latter, over/under alternation is
 *  easy to define.
 *
 * We do this by, for each ring R, ordering R's interesctions around
 *  its circumference.  (If two intersections occur close enough
 *  together that we have trouble ordering them, we've got a three-ring
 *  overlap region already.)
 *
 * Because of check_step1(), we know that two rings intersect iff the
 *  circles at their nominal radii intersect.  And, if R intersects
 *  with A and B, then the whole intersecting sets must appear in the
 *  same order as the interesctions at the nominal radii, or we have a
 *  three-ring overlap area.  Taken together, this means that, if there
 *  is any three-ring overlap with R, there is one where the other two
 *  rings involved are adjacent in terms of order of intersections
 *  around R.
 */
static void check_step2(void)
{
 /*
  * Perspective ring not explicitly present (it's in a separate
  *  variable).  r is the crossing ring.  a is the angle of the nominal
  *  crossing point from the perspective ring's POV, oa from the
  *  crossing ring's.  s is the slant from the perspective ring's POV.
  *  other is the P with the same r but the other s.  i is the index in
  *  p[].
  */
 typedef struct p P;
 struct p {
   RING *r;
   double a;
   double oa;
   SLANT s;
   P *other;
   } ;
 RING *r;
 int ncross;
 RING *o;
 XY cdiff;
 double n;
 XY pu;
 double a;
 double oa;
 double ca;
 double cos_a;
 P **p;
 P *pv;
 int pf;
 int i;
 int j;

 for (r=rings;r;r=r->link)
  { r->crossing_h = 0;
    r->crossing_t = 0;
  }
 for (r=rings;r;r=r->link)
  { ncross = 0;
    for (o=rings;o;o=o->link)
     { if (PAIRFLAG(r->id,o->id) & PF_CROSS) ncross += 2;
     }
    if (debug) fprintf(stderr,"ring %d ncross %d\n",r->id,ncross);
    if (ncross == 0) continue;
    p = malloc(ncross*sizeof(P *));
    pv = malloc(ncross*sizeof(P));
    for (i=ncross-1;i>=0;i--) p[i] = pv + i;
    pf = 0;
    for (o=rings;o;o=o->link)
     { if (PAIRFLAG(r->id,o->id) & PF_CROSS)
	{ cdiff = sub2(o->c,r->c);
	  n = norm2(cdiff);
	  pu = rot90(scale2(cdiff,1/n));
	  cos_a = ((n*n) + (r->r*r->r) - (o->r*o->r)) / (2 * n * r->r);
	  if ((cos_a < -1) || (cos_a > 1))
	   { fprintf(stderr,"Impossible non-intersection 1\n\t");
	     print_ring(r,stderr);
	     fprintf(stderr,"\n\t");
	     print_ring(o,stderr);
	     fprintf(stderr,"\n");
	     exit(1);
	   }
	  a = acos(cos_a);
	  ca = atan2(cdiff.y,cdiff.x);
	  cos_a = ((n*n) + (o->r*o->r) - (r->r*r->r)) / (2 * n * o->r);
	  if ((cos_a < -1) || (cos_a > 1))
	   { fprintf(stderr,"Impossible non-intersection 2\n\t");
	     print_ring(r,stderr);
	     fprintf(stderr,"\n\t");
	     print_ring(o,stderr);
	     fprintf(stderr,"\n");
	     exit(1);
	   }
	  oa = acos(cos_a);
	  if (pf+2 > ncross) abort();
	  p[pf][0] = (P){.r=o,.a=arrb(ca+a),.oa=arrb(ca+M_PI-oa),.s=SLANT_IN,.other=p[pf+1]};
	  p[pf+1][0] = (P){.r=o,.a=arrb(ca-a),.oa=arrb(ca+M_PI+oa),.s=SLANT_OUT,.other=p[pf]};
	  if (debug)
	   { fprintf(stderr,"p[%d] = %p: r=%d a=%g oa=%g s=%s\n",pf,(void *)p[pf],o->id,p[pf]->a,p[pf]->oa,slant_text(p[pf]->s));
	     fprintf(stderr,"p[%d] = %p: r=%d a=%g oa=%g s=%s\n",pf+1,(void *)p[pf+1],o->id,p[pf+1]->a,p[pf+1]->oa,slant_text(p[pf+1]->s));
	   }
	  pf += 2;
	}
     }
    if (pf != ncross) abort();
    do
     { j = 0;
       for (i=ncross-2;i>=0;i--)
	{ P *t;
	  if (p[i]->a > p[i+1]->a)
	   { t = p[i];
	     p[i] = p[i+1];
	     p[i+1] = t;
	     j = 1;
	   }
	}
     } while (j);
    if (debug)
     { fprintf(stderr,"sorted list:\n");
       for (i=0;i<ncross;i++) fprintf(stderr,"  [%d] = %p\n",i,(void *)p[i]);
     }
    for (i=ncross-2;i>=0;i--)
     { if (r->r*(p[i+1]->a-p[i]->a) < .1) triple_overlap(r,p[i]->r,p[i+1]->r);
     }
    if (r->r*fabs(arrb(p[0]->a-p[ncross-1]->a)) < .1) triple_overlap(r,p[0]->r,p[ncross-1]->r);
    for (i=ncross-1;i>=0;i--)
     { if (! CROSS(r->id,p[i]->r->id)[0])
	{ // Four CROSSINGs: perspective cross-product slant.
	  CROSSING *c[2][2];
	  c[0][0] = malloc(sizeof(CROSSING));
	  c[0][0]->r = r;
	  c[0][0]->or = p[i]->r;
	  c[0][0]->a = p[i]->a;
	  c[0][0]->slant = p[i]->s;
	  crossing_linkin(c[0][0]);
	  c[0][1] = malloc(sizeof(CROSSING));
	  c[0][1]->r = r;
	  c[0][1]->or = p[i]->r;
	  c[0][1]->a = p[i]->other->a;
	  c[0][1]->slant = p[i]->other->s;
	  crossing_linkin(c[0][1]);
	  c[1][0] = malloc(sizeof(CROSSING));
	  c[1][0]->r = p[i]->r;
	  c[1][0]->or = r;
	  c[1][0]->a = p[i]->oa;
	  c[1][0]->slant = p[i]->other->s;
	  crossing_linkin(c[1][0]);
	  c[1][1] = malloc(sizeof(CROSSING));
	  c[1][1]->r = p[i]->r;
	  c[1][1]->or = r;
	  c[1][1]->a = p[i]->other->oa;
	  c[1][1]->slant = p[i]->s;
	  crossing_linkin(c[1][1]);
	  c[0][0]->other = c[1][0];
	  c[0][1]->other = c[1][1];
	  c[1][0]->other = c[0][0];
	  c[1][1]->other = c[0][1];
	  if (debug)
	   { fprintf(stderr,"created crossings for p[%d]=%p\n",i,(void *)p[i]);
	     fprintf(stderr,"  [0][0] = %p: r=%d or=%d a=%g slant=%s\n",
			(void *)c[0][0],c[0][0]->r->id,c[0][0]->or->id,c[0][0]->a,slant_text(c[0][0]->slant));
	     fprintf(stderr,"  [0][1] = %p: r=%d or=%d a=%g slant=%s\n",
			(void *)c[0][1],c[0][1]->r->id,c[0][1]->or->id,c[0][1]->a,slant_text(c[0][1]->slant));
	     fprintf(stderr,"  [1][0] = %p: r=%d or=%d a=%g slant=%s\n",
			(void *)c[1][0],c[1][0]->r->id,c[1][0]->or->id,c[1][0]->a,slant_text(c[1][0]->slant));
	     fprintf(stderr,"  [1][1] = %p: r=%d or=%d a=%g slant=%s\n",
			(void *)c[1][1],c[1][1]->r->id,c[1][1]->or->id,c[1][1]->a,slant_text(c[1][1]->slant));
	   }
	  switch (p[i]->s)
	   { default:
		abort();
		break;
	     case SLANT_IN:
		CROSS(r->id,p[i]->r->id)[0] = c[0][0];
		CROSS(r->id,p[i]->r->id)[1] = c[0][1];
		CROSS(p[i]->r->id,r->id)[0] = c[1][0];
		CROSS(p[i]->r->id,r->id)[1] = c[1][1];
		break;
	     case SLANT_OUT:
		CROSS(r->id,p[i]->r->id)[1] = c[0][0];
		CROSS(r->id,p[i]->r->id)[0] = c[0][1];
		CROSS(p[i]->r->id,r->id)[1] = c[1][0];
		CROSS(p[i]->r->id,r->id)[0] = c[1][1];
		break;
	   }
	}
     }
    free(p);
    free(pv);
  }
 for (r=rings;r;r=r->link)
  { r->crossing_h = sort_crossings(r->crossing_h,&csops_nominal);
    backlink_fixup(r);
  }
}

/*
 * Helper for compute_ca: find a crossing-point angle for theoretical
 *  circles, the perspective circle having centre c1 and radius r1, the
 *  crossing circle having centre c2 and radius r2.  amul says which of
 *  the two crossings we want: 1 for the SLANT_IN crossing, -1 for
 *  SLANT_OUT.
 */
static double find_crossing_angle(XY c1, XY c2, double r1, double r2, int amul)
{
 XY cdiff;
 double n;
 double a;

 cdiff = sub2(c2,c1);
 n = norm2(cdiff);
 a = ((n*n) + (r1*r1) - (r2*r2)) / (2 * n * r1);
 if ((a < -1) || (a > 1)) abort();
 return(arrb(atan2(cdiff.y,cdiff.x)+(amul*acos(a))));
}

/*
 * Compute the CA for a given CROSSING.
 */
static CA compute_ca(CROSSING *c)
{
 switch (c->slant)
  { default:
       abort();
       break;
    case SLANT_IN:
       return((CA){ .ia1 = find_crossing_angle(c->r->c,c->or->c,c->r->ir,c->or->ir,1),
		    .ia2 = find_crossing_angle(c->r->c,c->or->c,c->r->ir,c->or->or,1),
		    .oa1 = find_crossing_angle(c->r->c,c->or->c,c->r->or,c->or->ir,1),
		    .oa2 = find_crossing_angle(c->r->c,c->or->c,c->r->or,c->or->or,1) });
       break;
    case SLANT_OUT:
       return((CA){ .ia1 = find_crossing_angle(c->r->c,c->or->c,c->r->ir,c->or->or,-1),
		    .ia2 = find_crossing_angle(c->r->c,c->or->c,c->r->ir,c->or->ir,-1),
		    .oa1 = find_crossing_angle(c->r->c,c->or->c,c->r->or,c->or->or,-1),
		    .oa2 = find_crossing_angle(c->r->c,c->or->c,c->r->or,c->or->ir,-1) });
       break;
  }
}

/*
 * Helper routines to get the angle values from a CROSSING (which must
 *  have an S3TMP in its tmp).
 */

static double get_s3ca_i1(CROSSING *c)
{
 return(S3TCA(c).ia1);
}

static double get_s3ca_i2(CROSSING *c)
{
 return(S3TCA(c).ia2);
}

static double get_s3ca_o1(CROSSING *c)
{
 return(S3TCA(c).oa1);
}

static double get_s3ca_o2(CROSSING *c)
{
 return(S3TCA(c).oa2);
}

/*
 * Helper routine for check_step3(): walk the S3TMP list and verify
 *  that its order matches, to within a circular shift, CROSSING flink
 *  order.
 */
static void check_crossings(CROSSING *list, double (*get1)(CROSSING *), double (*get2)(CROSSING *))
{
 CROSSING *c;
 CROSSING *p;
 CROSSING *n;
 double pa;
 double atot;
 double a1;
 double a2;

 p = 0;
 atot = 0;
 pa = - M_PI;
 for (c=list;c;c=S3TLINK(c))
  { if (p)
     { n = p->flink;
       if (! n) n = p->r->crossing_h;
       if (n != c) triple_overlap(p->r,c->or,n->or);
     }
    a1 = (*get1)(c);
    a2 = (*get2)(c);
    if (debug) fprintf(stderr,"atot %g pa %g a1 %g a2 %g -> ",atot,pa,a1,a2);
    atot += arrp(a1-pa) + arrp(a2-a1);
    if (debug) fprintf(stderr,"new %g\n",atot);
    pa = a2;
    p = c;
  }
 /*
  * We have to be careful; even with sorting, pa can be negative (or,
  *  equivalently, greater than pi) if the last a1-a2 interval includes
  *  the -pi/pi cutpoint.  So, instead of the obvious
  *
  *		atot += arrp(M_PI-pa);
  *
  *  we do this.  Note the sign check and the lack of aarp() - but we
  *  do check to make sure pa is indeed in range.
  */
 if ((pa < -M_PI-EPSILON) || (pa > M_PI+EPSILON)) abort();
 atot += ((pa < 0) ? -M_PI : M_PI) - pa;
 if (debug) fprintf(stderr,"final atot %g (%g pi)\n",atot,atot/M_PI);
 n = p->flink;
 if (! n) n = p->r->crossing_h;
 if (n != list) triple_overlap(p->r,list->or,n->or);
 if (fabs(atot-(2*M_PI)) > .1)
  { fprintf(stderr,"Ring crossing disorder (total angle = %g) for\n\t",atot);
    print_ring(list->r,stderr);
    fprintf(stderr,"\n");
    exit(1);
  }
}

/*
 * This does the rest of the checks for three-ring overlap (ie, the
 *  ones check_step2 didn't do).
 *
 * For each crossing, we compute an interval of the inner radius and an
 *  interval of the outer radius (of the perspective ring) covered by
 *  the crossing.  These intervals must be disjoint and must be in the
 *  same order as the nominal-radius intersections, or we have a
 *  forbidden intersection.  (I think we might be able to skip the
 *  ordering test, because any three-ring intersection we miss because
 *  of that would be picked up when we look at a different perspective
 *  ring.)
 *
 * It is possible to have a three-ring intersection without failing
 *  this test, but I believe that all such cases fail an earlier test.
 *
 * It is not simple to check ordering, because of the zone cut at ±180°
 *  and because two adjacent crossings may be >180° apart (consider
 *  perspective ring centre (0,0) radius 100 width 8 border 1, crossing
 *  ring centre (100,0) radius 25 width 8 border 1, no other crossing
 *  rings: the crossing at +ve y is followed by the crossing at -ve y,
 *  some 331° later - we need to be careful to not consider this to be
 *  going backwards by nearly 29°.)  So, what we do is, we sort the
 *  list of CROSSINGs by ia1 and check that, possibly excepting some
 *  circular shift, the order is the same as the nominal crossing
 *  order, and that, stepping from each CROSSING's ia1 to its ia2 and
 *  then the next ia1, etc, considering each step as positive, once
 *  around the circle adds up to 2pi (not, eg, 4pi, which will happen
 *  if one interval steps "backwards").  Then repeat using oa1 and oa2.
 */
static void check_step3(void)
{
 RING *r;
 CROSSING *c;
 S3TMP *t;
 CROSSING *list;

 for (r=rings;r;r=r->link)
  { list = 0;
    for (c=r->crossing_h;c;c=c->flink)
     { t = malloc(sizeof(S3TMP));
       c->tmp = t;
       t->link = list;
       list = c;
       t->ca = compute_ca(c);
       if (debug) fprintf(stderr,"ring %d c %p ia1=%g ia2=%g oa1=%g oa2=%g\n",r->id,(void *)c,S3TCA(c).ia1,S3TCA(c).ia2,S3TCA(c).oa1,S3TCA(c).oa2);
     }
    if (! list) continue;
    list = sort_crossings(list,&csops_step3i);
    if (debug)
     { fprintf(stderr,"step3 i list for ");
       print_ring(r,stderr);
       fprintf(stderr,":");
       for (c=list;c;c=S3TLINK(c)) fprintf(stderr," %p",(void *)c);
       fprintf(stderr,"\n");
     }
    check_crossings(list,&get_s3ca_i1,&get_s3ca_i2);
    list = sort_crossings(list,&csops_step3o);
    if (debug)
     { fprintf(stderr,"step3 o list for ring %d: ",r->id);
       for (c=list;c;c=S3TLINK(c)) fprintf(stderr," %p ",(void *)c);
       fprintf(stderr,"\n");
     }
    check_crossings(list,&get_s3ca_o1,&get_s3ca_o2);
    for (c=r->crossing_h;c;c=c->flink) free(c->tmp);
  }
}

static void check_rings(void)
{
 int i;
 int j;

 pairflags = calloc(nrings*nrings,1);
 crossings = malloc(nrings*nrings*sizeof(*crossings));
 for (i=nrings-1;i>=0;i--)
  { for (j=nrings-1;j>=0;j--)
     { CROSS(i,j)[0] = 0;
       CROSS(i,j)[1] = 0;
     }
  }
 check_step1();
 check_step2();
 check_step3();
}

static OVERUNDER ou_other(OVERUNDER ou)
{
 switch (ou)
  { case OU_OVER:
       return(OU_UNDER);
       break;
    case OU_UNDER:
       return(OU_OVER);
       break;
    default:
       abort();
       break;
  }
}

static void setweave(CROSSING *c, OVERUNDER ou)
{
 switch (ou)
  { case OU_OVER:
    case OU_UNDER:
       break;
    default:
       abort();
       break;
  }
 if ((c->weave == ou) && (c->other->weave == ou_other(ou))) return;
 if ((c->weave != OU_UNSET) || (c->other->weave != OU_UNSET)) abort();
 c->weave = ou;
 c->other->weave = ou_other(ou);
}

static void set_pending(RING *r)
{
 if (r->flags & RF_FLAG) return;
 r->flags |= RF_FLAG;
 r->tlink = wpend;
 wpend = r;
}

static void do_weave(void)
{
 RING *r;
 CROSSING *c;
 CROSSING *c0;
 OVERUNDER ou;

 for (r=rings;r;r=r->link)
  { for (c=r->crossing_h;c;c=c->flink) c->weave = OU_UNSET;
    r->flags &= RF_FLAG;
  }
 wpend = 0;
 while <"weaving"> (1)
  { do <"found">
     { for (r=rings;r;r=r->link)
	{ if (! (r->flags & RF_FLAG)) break <"found">;
	}
       break <"weaving">;
     } while (0);
    if (! r->crossing_h)
     { r->flags |= RF_FLAG;
       continue;
     }
    setweave(r->crossing_h,OU_OVER);
    set_pending(r);
    while (wpend)
     { r = wpend;
       wpend = r->tlink;
       for (c0=r->crossing_h;;c0=c0->flink)
	{ if (! c0) abort();
	  if (c0->weave != OU_UNSET) break;
	}
       ou = c0->weave;
       for (c=c0->flink;c;c=c->flink)
	{ ou = ou_other(ou);
	  setweave(c,ou);
	  set_pending(c->or);
	}
       ou = c0->weave;
       for (c=c0->blink;c;c=c->blink)
	{ ou = ou_other(ou);
	  setweave(c,ou);
	  set_pending(c->or);
	}
     }
  }
 for (r=rings;r;r=r->link)
  { if (! (r->flags & RF_FLAG)) abort();
    for (c=r->crossing_h;c;c=c->flink)
     { if (c->weave == OU_UNSET) abort();
     }
  }
}

static void setup_output(void)
{
 RING *r;
 double xmin;
 double xmax;
 double ymin;
 double ymax;
 double v;
 double or;
 int ixmin;
 int ixmax;
 int iymin;
 int iymax;

 xmin = rings->c.x;
 xmax = xmin;
 ymin = rings->c.y;
 ymax = ymin;
 for (r=rings;r;r=r->link)
  { or = r->r + (r->w/2) + r->b;
    v = r->c.x - or;
    if (v < xmin) xmin = v;
    v = r->c.y - or;
    if (v < ymin) ymin = v;
    v = r->c.x + or;
    if (v > xmax) xmax = v;
    v = r->c.y + or;
    if (v > ymax) ymax = v;
  }
 ixmin = floor(xmin) - 1;
 iymin = floor(ymin) - 1;
 ixmax = ceil(xmax) + 1;
 iymax = ceil(ymax) + 1;
 o_x0 = ixmin;
 o_y0 = iymin;
 o_w = ixmax - ixmin;
 o_h = iymax - iymin;
}

static void print_pixel(char otype, COLOUR c)
{
 if (! c.set) abort();
 switch (otype)
  { default:
       abort();
       break;
    case OTYPE_PBM:
       printf("%d",c.v[0]);
       break;
    case OTYPE_PGM:
       putchar(c.v[0]);
       break;
    case OTYPE_PPM:
       putchar(c.v[0]);
       putchar(c.v[1]);
       putchar(c.v[2]);
       break;
  }
}

static void gen_output(void)
{
 RING *r;
 RING *r2;
 RING *r3;
 int ix;
 int iy;
 double x;
 double y;
 double d;

 switch (otype)
  { default:
       abort();
       break;
    case OTYPE_PBM:
       printf("P1\n%d %d\n",o_w,o_h);
       break;
    case OTYPE_PGM:
       printf("P5\n%d %d\n255\n",o_w,o_h);
       break;
    case OTYPE_PPM:
       printf("P6\n%d %d\n255\n",o_w,o_h);
       break;
  }
 for (iy=0;iy<o_h;iy++)
  { y = iy + o_y0;
    for (ix=0;ix<o_w;ix++)
     { x = ix + o_x0;
       r2 = 0;
       r3 = 0;
       for (r=rings;r;r=r->link)
	{ d = ((r->c.x - x) * (r->c.x - x)) + ((r->c.y - y) * (r->c.y - y));
	  if ((d < r->ir2) || (d > r->or2)) continue;
	  if (r2)
	   { if (r3)
	      { fprintf(stderr,"Triple-overlap pixel\n\t");
		print_ring(r,stderr);
		fprintf(stderr,"\n\t");
		print_ring(r2,stderr);
		fprintf(stderr,"\n\t");
		print_ring(r3,stderr);
		fprintf(stderr,"\n");
		exit(1);
	      }
	     r3 = r;
	   }
	  else
	   { r2 = r;
	   }
	}
       if (r2)
	{ if (r3)
	   { // Two rings.  Figure out which one to use.
	     // First figure out which CROSSING to use!
	     CROSSING *c;
	     XY cd;
	     XY pd;
	     // r2 is perspective ring, r3 crossing ring
	     // Is pixel CW or CCW of line between centres?
	     cd = sub2(r3->c,r2->c);
	     pd = sub2((XY){.x=x,.y=y},r2->c);
	     c = CROSS(r2->id,r3->id)[(cd.x*pd.y)<(cd.y*pd.x)];
	     if (c->weave == OU_UNDER) r2 = r3;
	   }
	  // Exactly one ring, or we've made sure r2 is ring to use.
	  d = ((r2->c.x - x) * (r2->c.x - x)) + ((r2->c.y - y) * (r2->c.y - y));
	  if ((d <= r2->orb2) && (d >= r2->irb2))
	   { // In width
	     print_pixel(otype,r2->wcol);
	   }
	  else
	   { // In border
	     print_pixel(otype,r2->bcol);
	   }
	}
       else
	{ // No rings
	  print_pixel(otype,bgcol);
	}
     }
  }
}

static void handleargs(int ac, char **av)
{
 int skip;
 int errs;

 skip = 0;
 errs = 0;
 for (ac--,av++;ac;ac--,av++)
  { if (skip > 0)
     { skip --;
       continue;
     }
    if (**av != '-')
     { if (! infile)
	{ infile = *av;
	}
       else
	{ fprintf(stderr,"%s: stray argument `%s'\n",__progname,*av);
	  errs = 1;
	}
       continue;
     }
    if (0)
     {
needarg:;
       fprintf(stderr,"%s: %s needs a following argument\n",__progname,*av);
       errs = 1;
       continue;
     }
#define WANTARG() do { if (++skip >= ac) goto needarg; } while (0)
    if (!strcmp(*av,"-in"))
     { WANTARG();
       if (infile)
	{ fprintf(stderr,"%s: input file already specified\n",__progname);
	  errs = 1;
	}
       infile = av[skip];
       continue;
     }
    if (!strcmp(*av,"-debug"))
     { debug = 1;
       continue;
     }
    if (!strcmp(*av,"-memtrace"))
     { malsuppress = 0;
       continue;
     }
#undef WANTARG
    fprintf(stderr,"%s: unrecognized option `%s'\n",__progname,*av);
    errs = 1;
  }
 if (errs) exit(1);
}

int main(int, char **);
int main(int ac, char **av)
{
 handleargs(ac,av);
 rings = 0;
 nrings = 0;
 defring.flags = RF_HAVE_W | RF_UNSPEC_W | RF_HAVE_B | RF_UNSPEC_B;
 defring.wcol.set = 0;
 parse_colour_spec("0",1,&defring.wcol);
 defring.bcol.set = 0;
 parse_colour_spec("1",1,&defring.bcol);
 bgcol.set = 0;
 parse_colour_spec("0",1,&bgcol);
 read_input();
 if (debug) dump_rings();
 check_rings();
 do_weave();
 setup_output();
 gen_output();
 return(0);
}