Import upstream version 5.3.

[mup] / mup / mup / beamstem.c

/* Copyright (c) 1995, 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005 by Arkkra Enterprises */
/* All rights reserved */
/*
 * Name:	beamstem.c
 *
 * Description:	This file contains functions for setting lengths of note
 *		stems, which also involves beaming considerations.
 */

#include "defines.h"
#include "structs.h"
#include "globals.h"

/*
 * Several functions need to know the value of the "stemlen" parameter, so
 * instead of them all calling vvpath, define a holding place here.
 */
static float Defstemsteps;

static void proclist P((struct MAINLL *mainll_p, int vno));
static void proctablist P((struct MAINLL *mainll_p, int vno));
static int stemforced P((struct GRPSYL *gs_p, struct GRPSYL *ogs_p));
static void setbeam P((struct GRPSYL *start_p, struct GRPSYL *end_p,
		struct GRPSYL *ogs_p)); 
static void restore_ry P((struct GRPSYL *start_p, struct GRPSYL *end_p));
static double embedgrace P((struct GRPSYL *start_p, double b1, double b0));
static double embedclef P((struct GRPSYL *start_p, double b1, double b0));
static double beamoff P((struct GRPSYL *gs_p, int side, double boundary,
		struct GRPSYL *start_p));
static void embedrest P((struct GRPSYL *start_p, struct GRPSYL *last_p,
		double b1, double b0));
static double avoidothervoice P((struct GRPSYL *start_p, struct GRPSYL *last_p,
		double b1, double b0, struct GRPSYL *ogs_p));
static void setgroupvert P((int, struct GRPSYL *, struct GRPSYL *));
static void settuplet P((struct GRPSYL *start_p, struct STAFF *staff_p));
static void expgroup P((struct GRPSYL *gs_p, struct GRPSYL *ogs_p));
static void applywith P((struct GRPSYL *gs_p, int side));
\f
/*
 * Name:        beamstem()
 *
 * Abstract:    Set stem lengths for all notes that have stems or slash/alt.
 *
 * Returns:     void
 *
 * Description: This function loops through the main linked list.  For each
 *		linked list of groups on each visible staff, it calls proclist
 *		to set stem lengths.
 */

void
beamstem()

{
	register struct MAINLL *mainll_p; /* point along main linked list */
	int n;				/* loop variable */


	debug(16, "beamstem CSSpass=%d", CSSpass);
	initstructs();			/* clean out old SSV info */

	/*
	 * Loop once for each item in the main linked list.  Apply any SSVs
	 * that are found.
	 */
	for (mainll_p = Mainllhc_p; mainll_p != 0; mainll_p = mainll_p->next) {
		if (mainll_p->str == S_SSV) {

			asgnssv(mainll_p->u.ssv_p);

		} else if (mainll_p->str == S_STAFF &&
				mainll_p->u.staff_p->visible == YES &&
				! is_mrpt(mainll_p->u.staff_p->groups_p[0])) {
			/*
			 * For this visible staff, call a subroutine to process
			 * each list of groups on it.
			 */
			for (n = 0; n < MAXVOICES; n++) {
				if (mainll_p->u.staff_p->groups_p[n] != 0) {
					/* set global default stem steps */
					Defstemsteps = vvpath(mainll_p->
						u.staff_p->staffno,
						n + 1, STEMLEN)->stemlen;
					if (is_tab_staff(mainll_p->u.staff_p->
							staffno)) {
						proctablist(mainll_p, n);
					} else {
						proclist(mainll_p, n);
					}
				}
			}
		}
	}
}
\f
/*
 * Name:        proclist()
 *
 * Abstract:    Process linked list of groups.
 *
 * Returns:     void
 *
 * Description: This function loops through the linked list of groups for one
 *		voice for one measure, first handling the grace groups, then
 *		doing a second loop for the nongrace groups.  For each non-
 *		beamed note that needs it, it sets the stem length.  For each
 *		beamed group, it calls setbeam to figure out the equation
 *		of the beam, and set the stem lengths accordingly.  It also
 *		sets the relative vertical coords of the groups.  These coords
 *		then get altered to include "with" lists and tuplet marks.
 */

static void
proclist(mainll_p, vno)

struct MAINLL *mainll_p;	/* MLL struct for staff we're dealing with */
int vno;			/* voice we're to deal with, 0 to MAXVOICES-1 */

{
	struct GRPSYL *gs_p;	/* point to first group in a linked list */
	struct GRPSYL *ogs_p;	/* point to first group in other linked list */
	struct STAFF *staff_p;	/* point to the staff it's connected to */
	struct GRPSYL *savegs_p;/* save incoming gs_p */
	struct GRPSYL *beamst_p;/* point at first group of a beamed set */
	float notedist;		/* distance between outer notes of a group */
	float defsteps;		/* additional default steps long to make stem*/
	int bf;			/* number of beams/flags */


	debug(32, "proclist file=%s line=%d vno=%d", mainll_p->inputfile,
			mainll_p->inputlineno, vno);
	/*
	 * Set pointers to 1st group in our list and in the "other" list, as
	 * appropriate.  Voices 1 and 2 (vno=0,1) refer to each other as the
	 * "other" voice.  (If there is only one voice, ogs_p is set to voice 2
	 * (vno=1) which is a null pointer.)  Voice 3 (vno=2) always ignores
	 * the other voices, so for it, ogs_p is a null pointer.
	 */
	gs_p = mainll_p->u.staff_p->groups_p[ vno ];
	ogs_p = vno == 2 ? (struct GRPSYL *)0 :
			mainll_p->u.staff_p->groups_p[ ! vno ];

	staff_p = mainll_p->u.staff_p;	/* also point at staff */

	/* set globals like Staffscale for use by the rest of the file */
	set_staffscale(staff_p->staffno);

	beamst_p = 0;	/* prevent useless 'used before set' warnings */

	/*
	 * Loop through every group, skipping rests, spaces, and nongrace
	 * groups, setting the stem length of grace groups.
	 */
	for (savegs_p = gs_p; gs_p != 0; gs_p = gs_p->next) {
		if (gs_p->grpcont != GC_NOTES)
			continue;
		if (gs_p->grpvalue == GV_NORMAL)
			continue;

		/*
		 * If we are at the start of a beamed set of groups, remember
		 * this place.  Then, when we find the end of the set, call
		 * setbeam to figure out the equation of the beam and set the
		 * stem lengths.
		 */
		if (gs_p->beamloc != NOITEM) {
			if (gs_p->beamloc == STARTITEM)
				beamst_p = gs_p;
			if (gs_p->beamloc == ENDITEM)
				setbeam(beamst_p, nextsimilar(gs_p), ogs_p);

			continue;
		}

		/* if we get here, this group is not in a beamed set */

		/* if not affected by CSS, do on normal pass, and only then */
		/* if affected by CSS, do on CSS pass, and only then */
		if (css_affects_stemtip(gs_p) != CSSpass) {
			continue;
		}

		/*
		 * If the user specified a nonzero stem length, that's only the
		 * part of it that's not between the notes.  So add the distance
		 * between the outer notes of the group.  However, if they
		 * specified 0, they should get no stem.
		 */
		if (IS_STEMLEN_KNOWN(gs_p->stemlen)) {
			if (gs_p->stemlen != 0.0) {
				gs_p->stemlen *= Staffscale;
				notedist = gs_p->notelist[0].c[RY] - gs_p->
					notelist[ gs_p->nnotes - 1 ].c[RY];
				gs_p->stemlen += notedist;
			}
			continue;
		}

		/*
		 * Grace quarter notes default to just a note head and no stem.
		 * So set their stem length to 0.
		 */
		if (gs_p->basictime == 4) {
			gs_p->stemlen = 0;
			continue;
		}

		/*
		 * If stemlen parm is zero, force length to zero.  This will
		 * look bad for non-quarter notes, but that's what they
		 * asked for.
		 */
		if (Defstemsteps == 0.0) {
			gs_p->stemlen = 0.0;
			continue;
		}

		/*
		 * Set the stems to the requested length, plus the distance
		 * between the highest and lowest note of the group, except
		 * longer for notes with more than 2 flags or beams.  Unlike
		 * nongrace groups, stems need not reach the center line of
		 * the staff.
		 */
		/* find distance between outer notes of the group */
		notedist = gs_p->notelist[0].c[RY] -
			gs_p->notelist[ gs_p->nnotes - 1 ].c[RY];

		/* set len to default length + distance between outer notes */
		gs_p->stemlen = (Defstemsteps * SM_STEMFACTOR) * Stepsize +
				notedist;

		bf = drmo(gs_p->basictime) - 2;	/* no. of beams/flags */
		if (bf > 2)
			gs_p->stemlen += (bf - 2) * Smflagsep;
	}

	/*
	 * Loop through every grace group, skipping rests and spaces,
	 * setting the relative vertical coordinates.
	 */
	setgroupvert(GV_ZERO, savegs_p, ogs_p);

	/*
	 * Loop through every group, skipping rests, spaces and grace groups,
	 * setting the stem length of all nongrace groups.
	 *
	 * WARNING:  The code in this loop is similar to stemroom() in
	 * setgrps.c.  If you change one, you probably will need to change
	 * the other.
	 */
	for (gs_p = savegs_p; gs_p != 0; gs_p = gs_p->next) {
		if (gs_p->grpcont != GC_NOTES)
			continue;
		if (gs_p->grpvalue == GV_ZERO)
			continue;
		/*
		 * If this is cross staff beaming, don't do anything now.  We
		 * can't do anything until the absolute vertical coords are set
		 * in absvert.c.
		 */
		if (gs_p->beamto != CS_SAME) {
			continue;
		}

		/*
		 * If we are at the start of a beamed set of groups, remember
		 * this place.  Then, when we find the end of the set, call
		 * setbeam to figure out the equation of the beam and set the
		 * stem lengths.
		 */
		if (gs_p->beamloc != NOITEM) {
			if (gs_p->beamloc == STARTITEM)
				beamst_p = gs_p;
			if (gs_p->beamloc == ENDITEM)
				setbeam(beamst_p, nextsimilar(gs_p), ogs_p);
			continue;
		}

		/* if we get here, this group is not in a beamed set */

		/* if not affected by CSS, do on normal pass, and only then */
		/* if affected by CSS, do on CSS pass, and only then */
		if (css_affects_stemtip(gs_p) != CSSpass) {
			continue;
		}

		/*
		 * Only half notes and shorter have stems, but whole and double
		 * whole notes still need to have a pseudo stem length set if
		 * alternation beams are to be drawn between two neighboring
		 * groups, or the group has slashes.
		 */
		if (gs_p->basictime <= 1 && gs_p->slash_alt == 0)
			continue;	/* no stem and no pseudo stem */

		/*
		 * If the user specified a nonzero stem length, that's only the
		 * part of it that's not between the notes.  So add the distance
		 * between the outer notes of the group.  But if they specified
		 * 0, leave it as 0.
		 */
		if (IS_STEMLEN_KNOWN(gs_p->stemlen)) {
			if (gs_p->stemlen == 0.0)
				continue;

			gs_p->stemlen *= Staffscale;
			notedist = gs_p->notelist[0].c[RY] -
				gs_p->notelist[ gs_p->nnotes - 1 ].c[RY];
			gs_p->stemlen += notedist;
			continue;
		}

		/* if stemlen parm is zero, force length to zero */
		if (Defstemsteps == 0.0) {
			gs_p->stemlen = 0.0;
			continue;
		}

		/* 
		 * Set the stems initially to one octave long (or 5 stepsizes
		 * for cue notes), plus the distance between the highest and
		 * lowest note of the group, except longer for notes with more
		 * than 2 flags or beams.  In any case, for normal sized notes,
		 * real stems must reach the center line of the staff in most
		 * cases.
		 */
		/* find distance between outer notes of the group */
		notedist = gs_p->notelist[0].c[RY] -
			gs_p->notelist[ gs_p->nnotes - 1 ].c[RY];
		/* set len to default length + distance between outer notes */
		defsteps = Defstemsteps *
			(allsmall(gs_p, gs_p) == YES ? SM_STEMFACTOR : 1.0);
		gs_p->stemlen = defsteps * Stepsize + notedist;

		/* add more, if needed, for flags/beams/slashes/alternations */
		if (gs_p->basictime >= 8)
			bf = drmo(gs_p->basictime) - 2;	/* no. of beams/flags*/
		else
			bf = 0;			/* none on quarter or longer */
		bf += abs(gs_p->slash_alt);	/* slashes or alternations */
		if (gs_p->slash_alt > 0 && gs_p->basictime >= 16)
			bf++;	/* slashes need an extra one if 16, 32, ... */
		if (bf > 2)
			gs_p->stemlen += (bf - 2) * Flagsep;

		/*
		 * If the note may have flag(s), stem up, and has dot(s), we
		 * must prevent the flag(s) from hitting the dot(s), by
		 * lengthening the stem.
		 */
		if (gs_p->basictime >= 8 && gs_p->stemdir == UP &&
				gs_p->dots != 0) {
			if (gs_p->notelist[0].stepsup % 2 == 0) {
				/* note is on a line */
				if (gs_p->basictime == 8)
					gs_p->stemlen += Stepsize;
				else
					gs_p->stemlen += 2 * Stepsize;
			} else {
				/* note is on a space */
				if (gs_p->basictime > 8)
					gs_p->stemlen += Stepsize;
			}
		}

		/*
		 * Real (printed) stems must reach the center line for normal
		 * groups, though they need not for cue groups or voice 3 or
		 * when the stem direction has been forced the "wrong way" or
		 * when all the notes are on another staff.
		 */
		if (gs_p->basictime >= 2 && gs_p->grpsize == GS_NORMAL &&
				vno != 2 && stemforced(gs_p, ogs_p) == NO &&
				NNN(gs_p) > 0) {

			if (gs_p->stemdir == UP && gs_p->notelist[ gs_p->nnotes
					- 1 ].c[RY] < -(gs_p->stemlen)) {
				gs_p->stemlen = -gs_p->notelist[ gs_p->nnotes-1
						].c[RY];
			}

			if (gs_p->stemdir == DOWN && gs_p->notelist[ 0 ].c[RY]
						> gs_p->stemlen) {
				gs_p->stemlen = gs_p->notelist[ 0 ].c[RY];
			}
		}
	}

	/*
	 * Loop through every nongrace group, skipping rests and spaces,
	 * setting the relative vertical coordinates.
	 */
	setgroupvert(GV_NORMAL, savegs_p, ogs_p);

	/*
	 * Loop through every group, looking for tuplets.  When encountering
	 * the first item in a tuplet, call a subroutine to figure out where
	 * the bracket should go, and based on that alter the RN or RS of
	 * the groups in the tuplet.  However, if this is a tuplet whose
	 * number and bracket are not to be printed, don't call the subrountine.
	 * Also, it should not be done when there is cross staff beaming.  Mup
	 * does not automatically print tuplet numbers or brackets in CSB sets.
	 */
	for (gs_p = savegs_p; gs_p != 0; gs_p = gs_p->next) {
		if ((gs_p->tuploc == STARTITEM || gs_p->tuploc == LONEITEM) &&
		    gs_p->beamto == CS_SAME && gs_p->printtup != PT_NEITHER)
			settuplet(gs_p, staff_p);
	}
}
\f
/*
 * Name:        proctablist()
 *
 * Abstract:    Process linked list of groups on a tablature staff.
 *
 * Returns:     void
 *
 * Description: This function loops through the linked list of groups for one
 *		measure of a tablature staff.  It sets the relative vertical
 *		coords of the groups.  These coords then get altered to include
 *		"with" lists and tuplet marks.
 */

static void
proctablist(mainll_p, vno)

struct MAINLL *mainll_p;	/* MLL struct for staff we're dealing with */
int vno;			/* voice we're to deal with, 0 to MAXVOICES-1 */

{
	struct GRPSYL *gs_p;	/* point to first group in a linked list */
	struct GRPSYL *ogs_p;	/* point to first group in other linked list */
	int stepdiff;		/* steps between highest & lowest of a group */
	int defsteps;		/* additional default steps long to make stem*/
	int bf;			/* number of beams/flags (really slashes) */


	debug(32, "proctablist file=%s line=%d", mainll_p->inputfile,
			mainll_p->inputlineno);
	/* no such thing as cross staff stemming for tab */
	if (CSSpass == YES) {
		return;
	}

	/*
	 * Set pointers to 1st group in our list and in the "other" list, as
	 * appropriate.  Voices 1 and 2 (vno=0,1) refer to each other as the
	 * "other" voice.  (If there is only one voice, ogs_p is set to voice 2
	 * (vno=1) which is a null pointer.)  Voice 3 (vno=2) always ignores
	 * the other voices, so for it, ogs_p is a null pointer.
	 */
	gs_p = mainll_p->u.staff_p->groups_p[ vno ];
	ogs_p = vno == 2 ? (struct GRPSYL *)0 :
			mainll_p->u.staff_p->groups_p[ ! vno ];

	/*
	 * Loop through every group, setting some group vertical coordinates.
	 */
	for ( ; gs_p != 0; gs_p = gs_p->next) {
		/*
		 * Just as for nontablature groups, RY is always 0, the center
		 * of the staff, even if it falls outside the group's
		 * rectangle.  RN and RS were set in locllnotes() and
		 * intertab() in setnotes.c. 
		 */
		gs_p->c[RY] = 0;

		/*
		 * Slashes and "with" lists are allowed only if there are
		 * frets, so if there aren't any frets, skip the rest.
		 */
		if (gs_p->grpcont != GC_NOTES || gs_p->nnotes == 0)
			continue;

		/*
		 * No tab groups have stems, but we still need to set a pseudo
		 * stem length if the group has slashes and otherwise 0.
		 */
		if (gs_p->slash_alt == 0) {
			gs_p->stemlen = 0;	/* no slashes */
		} else {
			/* find distance between outer frets of the group */
			stepdiff = gs_p->notelist[0].stepsup -
				gs_p->notelist[ gs_p->nnotes - 1 ].stepsup;

			/* default length + distance between outer notes */
			defsteps = Defstemsteps * (allsmall(gs_p, gs_p) == YES
					? SM_STEMFACTOR : 1.0);
			gs_p->stemlen = stepdiff * Stepsize * TABRATIO +
					defsteps * Stepsize;

			bf = abs(gs_p->slash_alt);	/* slashes */
			if (gs_p->basictime >= 16)
				bf++;	/* slashes need extra 1 if 16, 32, ...*/
			if (bf > 2)
				gs_p->stemlen += (bf - 2) * Flagsep;

			if (gs_p->stemdir == UP) {
				gs_p->c[RN] = gs_p->notelist[gs_p->nnotes - 1]
						.c[RN] + gs_p->stemlen;
			} else {
				gs_p->c[RS] = gs_p->notelist[0]
						.c[RY] - gs_p->stemlen;
			}
		}

		/* decrease RS based on "with" lists */
		expgroup(gs_p, ogs_p);
	}
}
\f
/*
 * Name:        stemforced()
 *
 * Abstract:    Did the user force stem(s) to go the wrong way?
 *
 * Returns:     YES	at least one group was forced
 *		NO	no groups were forced
 *
 * Description: This function figures out whether the user forced *gs_p's stem
 *		to go DOWN for voice 1 or UP for voice 2 when the vscheme and
 *		the other voice would normally prevent it; or if *gs_p is at
 *		the start of a beamed set, it checks this for all groups in
 *		the set.
 */

static int
stemforced(gs_p, ogs_p)

struct GRPSYL *gs_p;		/* the group we are asking about */
struct GRPSYL *ogs_p;		/* first group in other voice's linked list */

{
	RATIONAL starttime;	/* of the group in question */
	RATIONAL endtime;	/* of the group in question */
	struct GRPSYL *gs2_p;	/* loop through groups */


	/* voice 3 never cares, so is never considered to be forced */
	if (gs_p->vno == 3) {
		return (NO);
	}

	/* grace cannot be forced */
	if (gs_p->grpvalue == GV_ZERO) {
		return (NO);
	}

	switch (svpath(gs_p->staffno, VSCHEME)->vscheme) {
	case V_1:
		return (NO);	/* no forcing is needed in this vscheme */
	case V_2OPSTEM:
	case V_3OPSTEM:
		/*
		 * If and only if a stem is backwards, we are forced.  Note
		 * that even for the beamed case, we only have to check one
		 * group, since all stems in the set go the same direction.
		 */
		if (gs_p->vno == 1 && gs_p->stemdir == DOWN ||
		    gs_p->vno == 2 && gs_p->stemdir == UP) {
			return (YES);
		}
		return (NO);
	}

	/*
	 * We are in one of the freestem vschemes.
	 */

	/* if the other voice doesn't exist, we know we were not forced */
	if (ogs_p == 0) {
		return (NO);	/* other voice does not exist */
	}

	/* if all stems are normal, we are not forced (only need to check 1) */
	if (gs_p->vno == 1 && gs_p->stemdir == UP ||
	    gs_p->vno == 2 && gs_p->stemdir == DOWN) {
		return (NO);
	}

	/* check if the other voice is all spaces during this time */

	/* find start time of *gs_p by summing all previous groups */
	starttime = Zero;
	for (gs2_p = gs_p->prev; gs2_p != 0; gs2_p = gs2_p->prev) {
		starttime = radd(starttime, gs2_p->fulltime);
	}

	/* find end time of *gs_p (or the whole beamed set) */
	endtime = starttime;
	for (gs2_p = gs_p; gs2_p != 0; gs2_p = gs2_p->next) {
		endtime = radd(endtime, gs2_p->fulltime);
		if (gs2_p->beamloc == NOITEM || gs2_p->beamloc == ENDITEM &&
						gs_p->grpvalue != GV_ZERO) {
			break;
		}
	}

	if (hasspace(ogs_p, starttime, endtime) == YES) {
		return (NO);	/* all spaces, forcing was not needed */
	} else {
		return (YES);	/* notes/rests, we were forced */
	}
}
\f
/*
 * Name:        setbeam()
 *
 * Abstract:    Set stem lengths for a beamed set of groups.
 *
 * Returns:     void
 *
 * Description: This function uses linear regression to figure out where the
 *		best place to put the beam is, for a beamed set of groups, or
 *		two groups that are alted together.  (Although there are
 *		special cases where the beam needs to be forced horizontal
 *		instead of using linear regression.)  But if the user specified
 *		the stem lengths of the first and last group, it just goes with
 *		that, instead of using linear regression.  It then sets the
 *		stem lengths for all the groups in the set.
 *
 *		Groups involved in cross staff beaming should never call here.
 *		That work must be done later in absvert.c.
 */

static void
setbeam(start_p, end_p, ogs_p)

struct GRPSYL *start_p;		/* first in beamed set */
struct GRPSYL *end_p;		/* after last in beamed set */
struct GRPSYL *ogs_p;		/* first group in other voice's GRPSYL list */

{
	struct GRPSYL *gs_p;	/* loop through the groups in the beamed set */
	struct GRPSYL *last_p;	/* point at last valid group before end_p */
	float sx, sy;		/* sum of x and y coords of notes */
	float xbar, ybar;	/* average x and y coords of notes */
	float top, bottom;	/* numerator & denominator for finding b1 */
	float temp;		/* scratch variable */
	float startx, endx;	/* x coord of first and last note */
	float starty, endy;	/* y coord of first and last note */
	float b0, b1;		/* y intercept and slope */
	float maxb0, minb0;	/* max and min y intercepts */
	float stemshift;	/* x distance of stem from center of note */
	float deflen;		/* default len of a stem, based on basictime */
	float shortdist;	/* amount of stem shortening allowed (inches)*/
	float x;		/* x coord of a stem */
	int css_affects_beam;	/* does CSS affect the position of the beam? */
	int all_notes_other_staff; /* all notes in all groups on other staff */
	int one_end_forced;	/* is stem len forced on one end only? */
	int slope_forced;	/* is the slope of the beam forced? */
	float forced_slope;	/* slope that the user forced */
	int bf;			/* number of beams/flags */
	int shortest;		/* basictime of shortest note in group */
	int num;		/* number of notes */
	short *steps;		/* stepsup of beamside notes */
	int patlen;		/* length of a pattern of notes */
	int match;		/* does the pattern match? */
	int k;			/* loop variable */
	int n;			/* loop variable */


	/*
	 * Find whether CSS affects the position of the beam, and whether all
	 * groups have all their notes on the other staff.  css_affects_stemtip
	 * asks (for this beamed case) whether any group's other-staff notes
	 * are stemside; that is, whether the stem points to the other staff,
	 * because then obviously the coord of the stem tip depends on where
	 * those notes are.  If all of this group's notes are on the other
	 * staff, you might expect that we would have to regard the stem tip as
	 * affected even if the stem is towards the normal staff.  But we
	 * prefer to pretend they aren't, so that we can handle more beamed
	 * sets on the first pass.  We fake out those groups (see the comment a
	 * little later).  And yet, if all the groups are this way, we do
	 * regard the beam as affected, because then we aren't going to enforce
	 * the rule about stems reaching the middle staff line.
	 */
	/* first set normal (non-CSS) values */
	css_affects_beam = NO;
	all_notes_other_staff = NO;
	if (CSSused == YES) {	/* don't waste time looking if CSS not used */
		all_notes_other_staff = YES;
		css_affects_beam = css_affects_stemtip(start_p);
		for (gs_p = start_p; gs_p != end_p; gs_p = nextsimilar(gs_p)) {
			if (NNN(gs_p) != 0) {
				all_notes_other_staff = NO;
			}
		}
		if (all_notes_other_staff == YES) {
			css_affects_beam = YES;
		}
	}

	/*
	 * If the beam is not affected by CSS, handle this beamed set on the
	 * first pass only.  If it is affected, handle it on the second
	 * pass only.
	 */
	if (css_affects_beam != CSSpass) {
		return;
	}

	/*
	 * If the beam is "not affected by CSS", there could still be groups
	 * where all the notes are CSS.  We fake them out here, setting the
	 * BNOTE's RY an octave from the center line.  We need some plausible
	 * value there for finding the beam position.  AY hasn't been used yet,
	 * so use it as a holding area.  We need to restore RY before returning
	 * from this function.
	 */
	if (CSSused == YES && CSSpass == NO) {
		for (gs_p = start_p; gs_p != end_p; gs_p = nextsimilar(gs_p)) {
			if (NNN(gs_p) == 0) {
				BNOTE(gs_p).c[AY] = BNOTE(gs_p).c[RY];
				BNOTE(gs_p).c[RY] = 7 * Stepsize *
					((gs_p->stemdir == UP) ? -1.0 : 1.0);
			}
		}
	}

	last_p = 0;	/* prevent useless 'used before set' warnings */

	/* find the last valid group */
	for (gs_p = start_p; gs_p != end_p; gs_p = nextsimilar(gs_p)) {
		last_p = gs_p;
	}

	/*
	 * If the user specified the stem length on one end (first or last) but
	 * not the other, remember that fact.  In that case we will execute the
	 * normal (both ends unforced) algorithm, but then at the last minute
	 * force the end that was given.
	 */
	one_end_forced = IS_STEMLEN_KNOWN(start_p->stemlen) !=
			 IS_STEMLEN_KNOWN(last_p->stemlen);

	/*
	 * If the user specified the stem length for the first and last groups,
	 * simply use these values to define where the beam is, and set all the
	 * stem lengths.
	 */
	if (IS_STEMLEN_KNOWN(start_p->stemlen) &&
	    IS_STEMLEN_KNOWN(last_p->stemlen)) {

		/*
		 * If the first and last groups had stemlen set to zero, force
		 * all groups to have stemlen zero, and return.  No beam will
		 * be drawn.
		 */
		if (start_p->stemlen == 0.0 && last_p->stemlen == 0.0) {
			for (gs_p = start_p; gs_p != end_p;
					gs_p = nextsimilar(gs_p)) {
				gs_p->stemlen = 0.0;
			}
			restore_ry(start_p, end_p);
			return;
		}

		/* they weren't both zero, so continue on finding the beam */
		start_p->stemlen *= Staffscale;
		stemshift = getstemshift(start_p);
		if (start_p->stemdir == DOWN)
			stemshift = -stemshift;
		last_p->stemlen *= Staffscale;

		/* find coords of the ends of the stems on the outer groups */
		startx = start_p->c[AX] + stemshift;
		endx = last_p->c[AX] + stemshift;
		starty = BNOTE(start_p).c[RY] + start_p->stemlen *
				(start_p->stemdir == UP ? 1.0 : -1.0);
		endy = BNOTE(last_p).c[RY] + last_p->stemlen *
				(last_p->stemdir == UP ? 1.0 : -1.0);

		/* find slope and y intercept of line through those points */
		b1 = (starty - endy) / (startx - endx);
		b0 = starty - b1 * startx;

		/* loop through all groups, setting stem length */
		for (gs_p = start_p; gs_p != end_p; gs_p = nextsimilar(gs_p)) {
			x = gs_p->c[AX] + stemshift;	/* X coord of stem */

			/* first set stemlen to beam's Y coord minus note's */
			gs_p->stemlen = (b0 + b1 * x) - BNOTE(gs_p).c[RY];

			/* if stems are down, reverse it */
			if (gs_p->stemdir == DOWN)
				gs_p->stemlen = -(gs_p->stemlen);

			finalstemadjust(gs_p);
		}

		/* set relative vertical coords of any embedded rests */
		embedrest(start_p, last_p, b1, b0);

		restore_ry(start_p, end_p);
		return;
	}

	/*
	 * If the user forced the beam's angle to some value, find what that is
	 * in terms of slope.  Later we will force this value to be used.  The
	 * 0.001 is to allow for floating point roundoff error.
	 */
	if (fabs(start_p->beamslope - NOBEAMANGLE) < 0.001) {
		slope_forced = NO;
		forced_slope = 0.0;	/* not used, keep lint happy */
	} else {
		slope_forced = YES;
		forced_slope = tan(start_p->beamslope * PI / 180.0);
	}

	/*
	 * When both end groups have stemlen zero, we set all groups' stemlens
	 * to zero, and no beam will be drawn.  Above we handled the case
	 * where the user forced both ends to zero.  Here we handle the case
	 * where the ends are defaulting to zero, or one end is defaulting to
	 * zero and the user forced the other one.  But don't do this if the
	 * slope is forced.
	 */
	if (Defstemsteps == 0.0 && ! slope_forced && ( ! one_end_forced ||
			start_p->stemlen == 0.0 || last_p->stemlen == 0.0)) {
		for (gs_p = start_p; gs_p != end_p; gs_p = nextsimilar(gs_p)) {
			gs_p->stemlen = 0.0;
		}
		restore_ry(start_p, end_p);
		return;
	}

	/*
	 * Use linear regression to find the best-fit line through the centers
	 * of the notes.  In this function, we will always be concerned with
	 * the X coord of the group as a whole (disregarding any notes that are
	 * on the "wrong" side of the stem) but the Y coord of the note of the
	 * group that's nearest to the beam (thus the BNOTE macro).  The X
	 * coords used are absolute, but the Y coords are relative to the
	 * center line of the staff, since we don't know the absolute Y coords
	 * yet, and it wouldn't affect the result anyway.
	 *
 	 * First get sum of x and y coords, to find averages.
	 */
	sx = sy = 0;
	num = 0;
	for (gs_p = start_p; gs_p != end_p; gs_p = nextsimilar(gs_p)) {
		sx += gs_p->c[AX];
		sy += BNOTE(gs_p).c[RY];
		num++;			/* count number of notes */
	}

	xbar = sx / num;
	ybar = sy / num;

	/* accumulate numerator & denominator of regression formula for b1 */
	top = bottom = 0;
	for (gs_p = start_p; gs_p != end_p; gs_p = nextsimilar(gs_p)) {
		temp = gs_p->c[AX] - xbar;
		top += temp * (BNOTE(gs_p).c[RY] - ybar);
		bottom += temp * temp;
	}

	b1 = top / bottom;		/* slope */
	/*
	 * We could also figure:
	 *	b0 = ybar - b1 * xbar;		y intercept
	 * to get the equation of the regression line:  y = b0 + b1 * x
	 * but we're going to change b0 later anyway.  Now, there are certain
	 * cases where we want to override the slope determined by regression,
	 * so revise b1 if that is the case.
	 */

	/* if first and last notes are equal, force horizontal */
	if (BNOTE(start_p).stepsup == BNOTE(last_p).stepsup)
		b1 = 0.0;

	/* check for more reasons to force the beam horizontal */
	if (b1 != 0.0 && num >= 3) {
		/* get an array of each group's beamside note's stepsup */
		MALLOCA(short, steps, num);
		for (n = 0, gs_p = start_p; n < num;
				n++, gs_p = nextsimilar(gs_p)) {
			steps[n] = BNOTE(gs_p).stepsup;
		}

		/*
		 * Check for a repeating pattern of notes.  Try every possible
		 * pattern length <= half as long as set.  If found, force the
		 * beam horizontal.
		 */
		for (patlen = num / 2; patlen >= 2; patlen--) {
			/* must be an integer number of pattern repetitions */
			if (num % patlen != 0) {
				continue;	/* groups were left over */
			}
			/* see if initial pattern repeats perfectly */
			match = YES;
			for (n = 0; n < patlen && match == YES; n++) {
				for (k = n + patlen; k < num; k += patlen) {
					if (steps[k] != steps[n]) {
						match = NO;
						break;
					}
				}
			}
			/* if all repeats matched, force horizontal & break */
			if (match == YES) {
				b1 = 0.0;
				break;
			}
		}

		/*
		 * If still not horizontal, check for the case where all the
		 * beamside notes are the same except for just the first, or
		 * just the last, being different and in the direction
		 * opposite the stemdir.  If so, force horizontal.
		 */
		if (b1 != 0.0) {
			/* make sure all the inner groups are the same */
			match = YES;
			for (n = 2; n < num - 1; n++) {
				if (steps[n] != steps[1]) {
					match = NO;
					break;
				}
			}
			/* if inner groups same, check the other conditions */
			if (match == YES) {
				if (start_p->stemdir == DOWN) {
					if ((steps[0] > steps[1] &&
					    steps[num-1] == steps[1]) ||
					    (steps[0] == steps[1] &&
					    steps[num-1] > steps[1])) {
						b1 = 0.0;
					}
				} else {	/* UP */
					if ((steps[0] < steps[1] &&
					    steps[num-1] == steps[1]) ||
					    (steps[0] == steps[1] &&
					    steps[num-1] < steps[1])) {
						b1 = 0.0;
					}
				}
			}
		}
		FREE(steps);
	}

	/*
	 * Find half the width of a note head; the stems will need to be
	 * shifted by that amount from the center of the notes so that they
	 * will meet the edge of the notes properly.  If the stems are up,
	 * they will be on the right side of (normal) notes, else left.  Set
	 * the X positions for the first and last stems.  (If these are alted
	 * groups, the noteheadchar may not be 4; but this is close enough.)
	 */
	stemshift = getstemshift(start_p);
	if (start_p->stemdir == DOWN)
		stemshift = -stemshift;
	startx = start_p->c[AX] + stemshift;	/* first group's stem */
	endx = last_p->c[AX] + stemshift;	/* last group's stem */

	/*
	 * The original slope derived by linear regression must be adjusted in
	 * certain ways.  First, override it if the user wants that; otherwise
	 * adjust according to the beamslope parameter.
	 */
	if (slope_forced) {
		b1 = forced_slope;
	} else {
		b1 = adjslope(start_p, b1, NO);
	}

	/*
	 * Calculate a new y intercept (b0).  First pass parallel lines
	 * through each note, and record the maximum and minimum y intercepts
	 * that result.
	 */
	b0 = BNOTE(start_p).c[RY] - b1 * start_p->c[AX];
	maxb0 = minb0 = b0;		/* init to value for first note */
	/* look at rest of them */
	for (gs_p = nextsimilar(start_p); gs_p != end_p;
			gs_p = nextsimilar(gs_p)) {
		b0 = BNOTE(gs_p).c[RY] - b1 * gs_p->c[AX];
		if (b0 > maxb0)
			maxb0 = b0;
		else if (b0 < minb0)
			minb0 = b0;
	}

	/*
	 * Find the basictime of the shortest note in the group, considering
	 * also any slashes or alternations on it.  (Except that slash has a
	 * different meaning on grace groups, and doesn't affect their stem
	 * length.)  Then set the default stem length based on that.
	 */
	shortest = 0;
	for (gs_p = start_p; gs_p != end_p; gs_p = nextsimilar(gs_p)) {
		if (gs_p->basictime >= 8)
			bf = drmo(gs_p->basictime) - 2;	/* no. of beams/flags*/
		else
			bf = 0;			/* none on quarter or longer */
		if (gs_p->grpvalue == GV_NORMAL)
			bf += abs(gs_p->slash_alt);/* slashes or alternations */
		/*
		 * In certain cases where there are accidentals, we need to
		 * artificially increase bf to keep the beams from overlapping
		 * with the accidental.
		 */
		if (gs_p != start_p && gs_p->stemdir == UP &&
				gs_p->notelist[0].accidental != '\0' &&
				gs_p->notelist[0].accidental != 'x' &&
				b1 > 0 && bf > 1) {
			bf += 3.5 * b1 * (Stepsize / Flagsep) * ((bf > 1) +
					(gs_p->notelist[0].accidental == 'B'));
		}
		if (bf > shortest)
			shortest = bf;
	}
	if (allsmall(start_p, last_p) == NO) {
		/* at least one group has a normal size note */
		deflen = Defstemsteps * Stepsize;
		if (shortest > 2)
			deflen += (shortest - 2) * Flagsep;
	} else {
		/* all groups have all small notes */
		deflen = Defstemsteps * SM_STEMFACTOR * Stepsize;
		if (shortest > 2)
			deflen += (shortest - 2) * 4.0 * POINT * Staffscale;
	}

	/*
	 * The outer edge of the beam should be deflen steps away from the
	 * average position of the notes, as defined by the linear regression
	 * line.  But don't allow any note to be closer than a certain number
	 * of steps less than that, the number as given by the stemshorten parm.
	 */
	shortdist = vvpath(start_p->staffno, start_p->vno, STEMSHORTEN)
			->stemshorten * Stepsize;
	if (start_p->stemdir == UP) {
		if (maxb0 - minb0 > shortdist)
			b0 = maxb0 + deflen - shortdist;
		else
			b0 += deflen;
	} else { /* DOWN */
		if (maxb0 - minb0 > shortdist)
			b0 = minb0 - deflen + shortdist;
		else
			b0 -= deflen;
	}

	/*
	 * Another adjustment may be needed so that all stems will reach the
	 * center line of the staff.  (Not to be done for small groups, or when
	 * all notes in all groups are on the other staff [CSS], or when
	 * some stemdirs have been forced wrong way despite the other voice, or
	 * we have alternations and no normal beams, or for voice 3.)
	 */
	starty = b0 + b1 * startx;	/* y coord near left end of beam */
	endy = b0 + b1 * endx;		/* y coord near right end of beam */
	if (start_p->basictime >= 2 && start_p->grpsize == GS_NORMAL &&
			stemforced(start_p, ogs_p) == NO &&
			start_p->vno != 3 && all_notes_other_staff == NO) {
		if (slope_forced) {
			/* move both ends the same amount to preserve slope */
			if (start_p->stemdir == UP) {
				if (starty < 0) {
					endy -= starty;
					starty = 0;
				}
				if (endy < 0) {
					starty -= endy;
					endy = 0;
				}
			} else { /* DOWN */
				if (starty > 0) {
					endy -= starty;
					starty = 0;
				}
				if (endy > 0) {
					starty -= endy;
					endy = 0;
				}
			}
		} else {
			/* move just the end(s) that need to be moved */
			if (start_p->stemdir == UP) {
				if (starty < 0)
					starty = 0;
				if (endy < 0)
					endy = 0;
			} else { /* DOWN */
				if (starty > 0)
					starty = 0;
				if (endy > 0)
					endy = 0;
			}
		}
	}

	/*
	 * If the first and last groups's stems now end at the center line, and
	 * the beam slope used to be nonzero, force one end to be a step beyond
	 * the center line, so that the beam will still have some slope to it.
	 * But don't do this if the user is forcing the beam's slope.
	 */
	if ( ! slope_forced && fabs(starty) < Stdpad &&
				fabs(endy) < Stdpad && b1 != 0.0) {
		if (start_p->stemdir == UP) {
			if (b1 > 0.0) {
				endy = Stepsize;
			} else if (b1 < 0.0) {
				starty = Stepsize;
			}
		} else {	/* DOWN */
			if (b1 > 0.0) {
				starty = -Stepsize;
			} else if (b1 < 0.0) {
				endy = -Stepsize;
			}
		}
	}

	/*
	 * If y at the ends of the beam differs by less than a step (allowing a
	 * fudge factor for roundoff error), force the beam horizontal by
	 * setting one end farther away from the notes.  But don't do it if the
	 * user is forcing a particular slope.
	 */
	if ( ! slope_forced && fabs(starty - endy) < Stepsize - 0.001) {
		if (start_p->stemdir == UP) {
			if (starty > endy) {
				endy = starty;
			} else {
				starty = endy;
			}
		} else {	/* DOWN */
			if (starty < endy) {
				endy = starty;
			} else {
				starty = endy;
			}
		}
	}

	/* recalculate slope and y intercept from (possibly) new endpoints */
	b1 = (endy - starty) / (endx - startx);		/* slope */
	b0 = starty - b1 * startx;			/* y intercept */
	temp = b0;			/* remember this value for later */

	/* do some additional work for nongrace groups */
	if (start_p->grpvalue == GV_NORMAL) {
		/*
		 * If this is not an alted pair, there may be embedded grace
		 * notes, and we may need to lengthen our stems to avoid them.
		 */
		if (start_p->slash_alt >= 0)
			b0 = embedgrace(start_p, b1, b0);

		/* may need to lengthen stems to avoid embedded clefs */
		b0 = embedclef(start_p, b1, b0);

		/* set relative vertical coords of any embedded rests */
		embedrest(start_p, last_p, b1, b0);

		/*
		 * If there is another voice, we might need to lengthen our
		 * stems so their notes won't run into our beam.  If we had
		 * embedded rests, they would also be moved.
		 */
		b0 = avoidothervoice(start_p, last_p, b1, b0, ogs_p);

		/* update these by the amount the y intercept changed */
		starty += temp - b0;
		endy += temp - b0;
	}

	restore_ry(start_p, end_p);

	/*
	 * If one end's stem len was forced but not the other, now is the time
	 * to apply that forcing.  So in effect, we have taken the beam as
	 * determined by the normal algorithm and now we change the vertical
	 * coord of this end.  If the slope was also forced, move the other
	 * end by the same amount so that the slope won't change.
	 */
	if (one_end_forced) {
		if (IS_STEMLEN_KNOWN(start_p->stemlen)) {
			start_p->stemlen *= Staffscale;
			temp = starty;
			starty = BNOTE(start_p).c[RY] + start_p->stemlen *
					(start_p->stemdir == UP ? 1.0 : -1.0);
			if (slope_forced) {
				endy += starty - temp;
			}
		} else {
			last_p->stemlen *= Staffscale;
			temp = endy;
			endy = BNOTE(last_p).c[RY] + last_p->stemlen *
					(last_p->stemdir == UP ? 1.0 : -1.0);
			if (slope_forced) {
				starty += endy - temp;
			}
		}

		/* recalculate */
		b1 = (endy - starty) / (endx - startx);	/* slope */
		b0 = starty - b1 * startx;		/* y intercept */

		/*
		 * Re-do embedded rests now that things have moved.  As for the
		 * other adjustments above, we can't re-do them because they
		 * may force stem lengths to change.  If things collide, too
		 * bad, the user forced the one stem length.  It might be
		 * possible to avoid the collision by moving the other end,
		 * but likely not, and it's too late now anyhow.
		 */
		embedrest(start_p, last_p, b1, b0);
	}

	/*
	 * At this point we know where to put the main beam (the one needed for
	 * eighth notes).  Figure out and set the correct stem lengths for all
	 * of these beamed groups.
	 */
	for (gs_p = start_p; gs_p != end_p; gs_p = nextsimilar(gs_p)) {
		x = gs_p->c[AX] + stemshift;	/* X coord of stem */

		/* first set stemlen to beam's Y coord minus note's */
		gs_p->stemlen = (b0 + b1 * x) - BNOTE(gs_p).c[RY];

		/* if stems down, reverse stemlen, should make it positive */
		if (gs_p->stemdir == DOWN) {
			gs_p->stemlen = -(gs_p->stemlen);
		}
		/* but if negative length, error */
		if (gs_p->stemlen < 0) {
			l_ufatal(gs_p->inputfile, gs_p->inputlineno,
					"stem length was forced negative");
		}

		finalstemadjust(gs_p);
	}
}
\f
/*
 * Name:        restore_ry()
 *
 * Abstract:    Restore RY coordinates if need be.
 *
 * Returns:     void
 *
 * Description: This function undoes what the code near the start of setbeam()
 *		did.  But it doesn't have to set AY back, because it is garbage
 *		and will be overwritten later anyway.
 */

static void
restore_ry(start_p, end_p)

struct GRPSYL *start_p;		/* first in beamed set */
struct GRPSYL *end_p;		/* after last in beamed set */

{
	struct GRPSYL *gs_p;	/* loop through the groups in the beamed set */


	if (CSSused == YES && CSSpass == NO) {
		for (gs_p = start_p; gs_p != end_p; gs_p = nextsimilar(gs_p)) {
			if (NNN(gs_p) == 0) {
				BNOTE(gs_p).c[RY] = BNOTE(gs_p).c[AY];
			}
		}
	}
}
\f
/*
 * Name:        embedgrace()
 *
 * Abstract:    Change the Y intercept if necessary for embedded grace groups.
 *
 * Returns:     new y intercept value (may be no change)
 *
 * Description: When grace groups are embedded inside a set of nongrace groups,
 *		the beam(s) for the nongrace may have to be put farther away
 *		from their note heads, so that these beams won't collide with
 *		the grace groups.  This function returns the new Y intercept
 *		for the equation of the nongraces' main beam, which accom-
 *		plishes this.  When there aren't any embedded grace groups,
 *		or they are in certain positions, this Y intercept will be the
 *		same as the old Y intercept.
 */

static double
embedgrace(start_p, b1, b0)

struct GRPSYL *start_p;	/* first group in nongrace beamed set */
double b1;		/* slope */
double b0;		/* y intercept */

{
	struct GRPSYL *gs_p;	/* point to grace group being looked at */
	struct GRPSYL *prev_p;	/* point to nongrace group preceding gs_p */
	struct GRPSYL *next_p;	/* point to nongrace group following gs_p */
	float beamthick;	/* total thickness of beams and space between*/
	float ycross;		/* where grace stem would hit nongrace beam */


	/*
	 * Loop through all the grace groups that are embedded somewhere
	 * between the first and last groups of this nongrace beamed set.
	 * If their stems point the opposite way, there is no problem.  But
	 * if not, we may need to move the main beam(s) out of the way.
	 */
	for (gs_p = start_p; gs_p->grpvalue == GV_ZERO ||
				gs_p->beamloc != ENDITEM; gs_p = gs_p->next) {
		if (gs_p->grpvalue == GV_NORMAL)
			continue;	/* ignore nongrace groups */

		/*
		 * Find the preceding and following nongrace group.  Whichever
		 * has the least (slowest) basictime, that determines how many
		 * full beams will connect those two groups.  (You take log2 of
		 * it and subtract 2.)
		 */
		prev_p = prevnongrace(gs_p);
		next_p = nextnongrace(gs_p);

		/* thickness of relevant beams at right side of grace */
		beamthick = beamoff(next_p, PB_LEFT, gs_p->c[AE], start_p);

		/*
		 * Find the AX and RY coords of the end of the grace group
		 * stem that is nearest the nongrace beam(s).  Then, if this
		 * point would run into or beyond the nongrace beam(s), change
		 * the Y intercept (b0) so that it won't.
		 */
		ycross = b1 * gs_p->c[AE] + b0;
		if (start_p->stemdir == UP) {
			if (ycross - beamthick < gs_p->c[RN])
				b0 += gs_p->c[RN] - (ycross - beamthick);
		} else {	/* stemdir == DOWN */
			if (ycross + beamthick > gs_p->c[RS])
				b0 -= (ycross + beamthick) - gs_p->c[RS];
		}

		/* thickness of relevant beams at left side of grace */
		beamthick = beamoff(prev_p, PB_RIGHT, gs_p->c[AW], start_p);

		ycross = b1 * gs_p->c[AW] + b0;
		if (start_p->stemdir == UP) {
			if (ycross - beamthick < gs_p->c[RN])
				b0 += gs_p->c[RN] - (ycross - beamthick);
		} else {	/* stemdir == DOWN */
			if (ycross + beamthick > gs_p->c[RS])
				b0 -= (ycross + beamthick) - gs_p->c[RS];
		}
	}

	return (b0);	/* new (possibly changed) Y intercept */
}
\f
/*
 * Name:        embedclef()
 *
 * Abstract:    Change the Y intercept if necessary for embedded clefs.
 *
 * Returns:     new y intercept value (may be no change)
 *
 * Description: When clef changes occur before groups in a beamed set, the
 *		beam(s) for the set may have to be put farther away from their
 *		note heads, so that these beams won't collide with the clefs.
 *		This function returns the new Y intercept for the equation of
 *		the nongraces' main beam, which accomplishes this.  When there
 *		aren't any embedded clefs, or they are in certain positions,
 *		this Y intercept will be the same as the old Y intercept.
 */

static double
embedclef(start_p, b1, b0)

struct GRPSYL *start_p;	/* first group in nongrace beamed set */
double b1;		/* slope */
double b0;		/* y intercept */

{
	struct GRPSYL *gs_p;	/* point to group being looked at */
	struct GRPSYL *pbgs_p;	/* group whose partial beams may impact us */
	float north, south;	/* top and bottom edge of a clef */
	float horizontal;	/* left or right edge of a clef */
	float beamthick;	/* total thickness of beams and space between*/
	float ycross;		/* where grace stem would hit nongrace beam */


	/*
	 * Loop through all the groups between the first and last groups of
	 * this nongrace beamed set, including the last but not the first, and
	 * including any embedded graces.  If any are preceded by a clef, we
	 * may need to move the beam(s) out of the way.
	 */
	for (gs_p = start_p->next; gs_p != 0 && ! (gs_p->prev->grpvalue ==
			GV_NORMAL && gs_p->prev->beamloc == ENDITEM);
			gs_p = gs_p->next) {

		if (gs_p->clef == NOCLEF) {
			continue;	/* ignore groups with no clef */
		}

		/* find the vertical edges of the clef */
		(void)clefvert(gs_p->clef, YES, &north, &south);
		north *= Staffscale;
		south *= Staffscale;

		/*
		 * Make sure the right side of the clef doesn't collide with
		 * the beams.
		 */
		/* find right side of the clef */
		horizontal = gs_p->c[AW] - CLEFPAD * Staffscale;

		/* group whose partial beams we need to worry about */
		pbgs_p = gs_p->grpvalue == GV_ZERO ? nextnongrace(gs_p) : gs_p;

		/* thickness of relevant beams at right side of clef */
		beamthick = beamoff(pbgs_p, PB_LEFT, horizontal, start_p);

		/* Find RY where right edge of clef would hit the main beam. If
		 * that edge of clef would hit any beam, change Y intercept. */
		ycross = b1 * horizontal + b0;
		if (start_p->stemdir == UP) {
			if (ycross - beamthick < north) {
				b0 += north - (ycross - beamthick);
			}
		} else {	/* stemdir == DOWN */
			if (ycross + beamthick > south) {
				b0 -= (ycross + beamthick) - south;
			}
		}

		/*
		 * Make sure the left side of the clef doesn't collide with
		 * the beams.
		 */
		/* find left side of the clef */
		horizontal -= clefwidth(gs_p->clef, YES) * Staffscale;

		/* group whose partial beams we need to worry about */
		pbgs_p = prevnongrace(gs_p);

		/* thickness of relevant beams at left side of clef */
		beamthick = beamoff(pbgs_p, PB_RIGHT, horizontal, start_p);

		/* Find RY where left edge of clef would hit main beam.  If
		 * that edge of clef would hit any beam, change Y intercept. */
		ycross = b1 * horizontal + b0;
		if (start_p->stemdir == UP) {
			if (ycross - beamthick < north) {
				b0 += north - (ycross - beamthick);
			}
		} else {	/* stemdir == DOWN */
			if (ycross + beamthick > south) {
				b0 -= (ycross + beamthick) - south;
			}
		}
	}

	return (b0);	/* new (possibly changed) Y intercept */
}
\f
/*
 * Name:        beamoff()
 *
 * Abstract:    On one side of group, get height of beams and spaces between.
 *
 * Returns:     height in inches
 *
 * Description: This function is called with a nongrace group in beamed set, to
 *		find out how many beams it has on one side of it and how high
 *		they are.  If the group is the first or last in the set, the
 *		side must be the interior side.  Partial beams are also figured
 *		in, if they might extend far enough to reach the "boundary"
 *		coordinate.
 */

static double
beamoff(gs_p, side, boundary, start_p)

struct GRPSYL *gs_p;	/* group we are concerned with */
int side;		/* which side of the group, PB_LEFT or PB_RIGHT */
double boundary;	/* X coord of edge of thing that must not collide */
struct GRPSYL *start_p;	/* first group in nongrace beamed set */

{
	struct GRPSYL *ogs_p;	/* nongrace group on "side" side of gs_p */
	struct GRPSYL *o2gs_p;	/* nongrace group on other side of gs_p */
	int beams;		/* number of beams for figuring collision */
	int minbasic;		/* minimum (longest) basictime */


	/*
	 * If it's the left side of this group we're worried about, set ogs_p
	 * to the previous nongrace, and o2gs_p to the next.  If right, do the
	 * opposite.
	 */
	if (side == PB_LEFT) {
		ogs_p = prevnongrace(gs_p);
		o2gs_p = nextnongrace(gs_p);
	} else {
		ogs_p = nextnongrace(gs_p);
		o2gs_p = prevnongrace(gs_p);
	}

	/*
	 * Whichever of the two groups {this group, the group on the side
	 * that we're worried about} has the least (slowest) basictime, that
	 * determines how many full beams will connect those two groups.  (You
	 * take log2 of it and subtract 2.)
	 */
	minbasic = MIN(gs_p->basictime, ogs_p->basictime);
	if (minbasic >= 8) {
		beams = drmo(MIN(gs_p->basictime, ogs_p->basictime)) - 2;
	} else {
		beams = 0;	/* must be an alternation */
	}

	/* add the number of alternation beams, if any */
	if (gs_p->slash_alt < 0) {
		beams -= gs_p->slash_alt;
	}

	/*
	 * If our group needs more beams than the group on the requested side,
	 * and the stem is in the direction where partial beams would stick out
	 * beyond our GRPSYL boundary and the partial beams are long enough to
	 * possibly collide with the thing we're trying to avoid . . .
	 */
	if (gs_p->basictime > ogs_p->basictime &&
			(side == PB_LEFT && gs_p->stemdir == DOWN &&
				gs_p->c[AW] - 5.0 * Stepsize < boundary ||
			side == PB_RIGHT && gs_p->stemdir == UP &&
				gs_p->c[AE] + 5.0 * Stepsize > boundary)) {
		/*
		 * If we are the start or end of this beamed set, or we need
		 * more beams than the group on the other side . . .
		 */
		if (gs_p->beamloc == STARTITEM || gs_p->beamloc == ENDITEM ||
				gs_p->basictime > o2gs_p->basictime) {
			/*
			 * We have partial beam(s); if on the side that matters
			 * to us, reset the number of beams to include partials.
			 */
			if (pbeamside(gs_p, start_p) == side) {
				beams = drmo(gs_p->basictime) - 2;
			}
		}
	}

	/*
 	 * To get total beam thickness, multiply the size of one beam by the
	 * number of beams.  Also add in a small fudge factor.
	 */
	return (Flagsep * beams + Stepsize / 2.0);
}
\f
/*
 * Name:        embedrest()
 *
 * Abstract:    Set relative vertical coords of rests embedded in beamed sets.
 *
 * Returns:     void
 *
 * Description: Rests' vertical coords were set in restsyl.c.  But when a rest
 *		is embedded in a beamed set, its coords may have to be changed
 *		now so that it fits well.
 */

static void
embedrest(start_p, last_p, b1, b0)

struct GRPSYL *start_p;	/* first group in nongrace beamed set */
struct GRPSYL *last_p;	/* last group in nongrace beamed set */
double b1;		/* slope */
double b0;		/* y intercept */

{
	struct GRPSYL *gs_p;	/* point to group in the set */
	struct GRPSYL *gp_p, *gpp_p; /* prev nongrace note, and prev to that */
	struct GRPSYL *gn_p, *gnn_p; /* next nongrace note, and next to that */
	int bp, bn;		/* beams on gp_p and gn_p */
	int partial;		/* partial beams in our way */
	char rchar;		/* char for the rest */
	int size;		/* font size */
	float asc, des;		/* ascent and descent of a rest */
	float beamthick;	/* total thickness of beams and space between*/
	float ycross;		/* where rest would hit beam */
	int beams;		/* number of beams joining two groups */


	/*
	 * Loop through the interior groups of this set, setting relative
	 * vertical coords of rest groups.  (Outer groups are never rests.)
	 */
	for (gs_p = start_p->next; gs_p != last_p; gs_p = gs_p->next) {

		/* skip nonrests */
		if (gs_p->grpcont != GC_REST)
			continue;

		/* skip cases where the user is forcing the coords */
		if (gs_p->restdist != NORESTDIST)
			continue;

		rchar = restchar(gs_p->basictime);
		size = (gs_p->grpsize == GS_NORMAL ? DFLT_SIZE : SMALLSIZE);
		asc = ascent(FONT_MUSIC, size, rchar) * Staffscale;
		des = descent(FONT_MUSIC, size, rchar) * Staffscale;


		/* find prev nongrace note group; will be in this beamed set */
		for (gp_p = gs_p->prev; gp_p->grpcont != GC_NOTES ||
				gp_p->grpvalue == GV_ZERO; gp_p = gp_p->prev)
			;

		/* find prev nongrace note group to that, if any */
		for (gpp_p = gp_p->prev; gpp_p != 0 && (gpp_p->grpcont !=
				GC_NOTES || gpp_p->grpvalue == GV_ZERO);
				gpp_p= gpp_p->prev)
			;
		/* but if it's not in this beamed set, forget it */
		if (gpp_p != 0 && gpp_p->beamloc != INITEM &&
				  gpp_p->beamloc != STARTITEM)
			gpp_p = 0;


		/* find next nongrace note group; will be in this beamed set */
		for (gn_p = gs_p->next; gn_p->grpcont != GC_NOTES ||
				gn_p->grpvalue == GV_ZERO; gn_p = gn_p->next)
			;

		/* find next nongrace note group to that, if any */
		for (gnn_p = gn_p->next; gnn_p != 0 && (gnn_p->grpcont !=
				GC_NOTES || gnn_p->grpvalue == GV_ZERO);
				gnn_p= gnn_p->next)
			;
		/* but if it's not in this beamed set, forget it */
		if (gnn_p != 0 && gnn_p->beamloc != INITEM &&
				  gnn_p->beamloc != ENDITEM)
			gnn_p = 0;


		/* get number of beams needed by prev and next */
		bp = numbeams(gp_p->basictime);
		bn = numbeams(gn_p->basictime);

		partial = 0;	/* init to no partial beams */

		/*
		 * If the group just before our rest is notes, and this beamed
		 * set's stems are up, and the prev note needs more beams than
		 * the next note, we may have to deal with partial beams.
		 */
		if (gs_p->prev->grpcont == GC_NOTES && start_p->stemdir == UP
				&& bp > bn) {
			if (gpp_p == 0) {
				/* definitely partial beams on this side */
				partial = bp - bn;
			} else {
				/* maybe partial beams on this side */
				if (numbeams(gpp_p->basictime) < bp &&
				pbeamside(gp_p, start_p) == PB_RIGHT)
					partial = bp - bn;
			}
			/* but if far enough away horizontally, we can ignore */
			if (gs_p->c[AW] - gp_p->c[AE] > 1.5 * Stepsize)
				partial = 0;
		}

		/*
		 * If the group just after our rest is notes, and this beamed
		 * set's stems are down, and the next note needs more beams than
		 * the prev note, we may have to deal with partial beams.  If
		 * the next group is grace, we might fall into this block, but
		 * that's okay; the next nongrace (gn_p) will be far enough
		 * away that partial will (correctly) be forced back to 0.
		 */
		if (gs_p->next->grpcont == GC_NOTES && start_p->stemdir == DOWN
				&& bn > bp) {
			if (gnn_p == 0) {
				/* definitely partial beams on this side */
				partial = bn - bp;
			} else {
				/* maybe partial beams on this side */
				if (numbeams(gnn_p->basictime) < bn &&
				pbeamside(gn_p, start_p) == PB_LEFT)
					partial = bn - bp;
			}
			/* but if far enough away horizontally, we can ignore */
			if (gn_p->c[AW] - gs_p->c[AE] > 1.5 * Stepsize)
				partial = 0;
		}

		/* full beams joining prev and next, plus relevant partials */
		beams = MIN(bp, bn) + partial;

		/*
 		 * To get total beam thickness, multiply the size of one beam
		 * by the number of beams.
		 */
		beamthick = Flagsep * beams;

		/* find where outer beam hits our rest's X coord */
		ycross = b1 * gs_p->c[AX] + b0;

		/* find vertical coord, quantizing the results */
		if (start_p->stemdir == UP) {
			gs_p->c[RY] = nearestline(ycross - beamthick -
					asc - Stepsize);
		} else {	/* stemdir == DOWN */
			gs_p->c[RY] = nearestline(ycross + beamthick +
					des + Stepsize);
		}

		gs_p->c[RN] = gs_p->c[RY] + asc;
		gs_p->c[RS] = gs_p->c[RY] - des;
	}
}
\f
/*
 * Name:        avoidothervoice()
 *
 * Abstract:    Change the Y intercept if necessary to avoid the other voice.
 *
 * Returns:     new y intercept value (may be no change)
 *
 * Description: When there is another voice, its groups might collide with our
 *		voice's beams, unless we lengthen our groups' stems.  This
 *		function returns the new Y intercept for the equation of the
 *		our voice's main beam, which accomplishes this.  When there is
 *		no other voice, or its groups don't interfere with our beam,
 *		this Y intercept will be the same as the old Y intercept.
 *		When it changes, embedded rests' coords need to be changed too.
 */

static double
avoidothervoice(start_p, last_p, b1, b0, ogs_p)

struct GRPSYL *start_p;	/* first group in nongrace beamed set */
struct GRPSYL *last_p;	/* last group in nongrace beamed set */
double b1;		/* slope */
double b0;		/* y intercept */
struct GRPSYL *ogs_p;	/* first group in the other voice */

{
	struct GRPSYL *prev_p;	/* point to nongrace group preceding gs_p */
	struct GRPSYL *prev2_p;	/* point to nongrace group before that one */
	struct GRPSYL *next_p;	/* point to nongrace group following gs_p */
	struct GRPSYL *next2_p;	/* point to nongrace group after that one */
	struct GRPSYL *gs_p;	/* point to group being looked at */
	float beamthick;	/* total thickness of beams and space between*/
	float ycross;		/* where grace stem would hit nongrace beam */
	float fary;		/* farthest y coord of other voice's group */
	int beams;		/* number of beams joining two nongrace groups*/
	float thismove;		/* how far one item requires the beam to move*/
	float move;		/* distance to move intercept */


	move = 0.0;		/* init to no move */

	/*
	 * Loop through all the groups in the other voice.  (If there is no
	 * other voice, this loop will execute zero times.)  If any of its
	 * groups land on or beyond our beam, move our beam farther away so
	 * they don't.
	 */
	for (gs_p = ogs_p; gs_p != 0; gs_p = gs_p->next) {

		/* spaces and rests can't interfere with anything */
		if (gs_p->grpcont != GC_NOTES)
			continue;

		/* if this group is outside our beamed set, ignore it */
		if (gs_p->c[AX] <= start_p->c[AX] ||
		    gs_p->c[AX] >=  last_p->c[AX])
			continue;

		/*
		 * Find which groups in our set immediately preceed and follow
		 * the other voice's group.  These will be prev_p and next_p.
		 */
		for (prev_p = next_p = start_p;
		     next_p->c[AX] < gs_p->c[AX];
		     prev_p = next_p, next_p = nextnongrace(next_p))
			;

		/*
		 * If next_p is lined up with gs_p, and is a note group, that
		 * means these groups were "compatible" (see setgrps.c), and so
		 * there can be no way that we would have to move our beam.
		 * But if next_p is a rest, handle the situation and continue.
		 */
		if (next_p->c[AX] == gs_p->c[AX]) {
			if (next_p->grpcont == GC_NOTES)
				continue;	/* compatible, no problem */

			/*
			 * Find the AX and RY coords of the outer edge of the
			 * outer note of the other voice's group that is the
			 * farthest in the direction of our beam.  Then, if
			 * this point would run into or beyond the rest, find
			 * how far to move the Y intercept (b0) so that it
			 * won't.  Remember the farthest move needed.
			 */
			if (start_p->stemdir == UP) {
				fary = gs_p->notelist[0].c[RN] + Stdpad;
				if (next_p->c[RS] < fary) {
					thismove = fary - next_p->c[RS];
					move = MAX(move, thismove);
				}
			} else { /* stemdir == DOWN */
				fary = gs_p->notelist[ gs_p->nnotes-1 ].c[RS]
						- Stdpad;
				if (next_p->c[RN] > fary) {
					thismove = fary - next_p->c[RN];
					move = MIN(move, thismove);
				}
			}

			continue;
		}

		/*
		 * Find which of prev_p and next_p has the least (slowest)
		 * basictime.  That determines how many full beams will connect
		 * those two groups.  (You take log2 of it and subtract 2.)
		 * Then add in any alternation beams.
		 */
		if (prev_p->basictime >= 8)
			beams = drmo(MIN(prev_p->basictime, next_p->basictime))
					- 2;
		else
			beams = 0;

		if (prev_p->slash_alt < 0)
			beams -= prev_p->slash_alt;

		/*
		 * Find out if there are partial beams on the left side of the
		 * following group or right side of the preceding group.  If
		 * so, that group's basictime may determine the total number of
		 * beams that could interfere with our group, if it's close
		 * enough.
		 */
		if (prev_p->basictime < next_p->basictime && next_p->stemdir ==
		    DOWN && next_p->c[AX] - gs_p->c[AX] < 5 * Stepsize) {

			/* find nongrace group after "next", if one exists */
			next2_p = nextnongrace(next_p);

			/* if "next" group has partial beams . . . */
			if (next2_p == 0 || next_p->beamloc == ENDITEM ||
				next_p->basictime > next2_p->basictime) {

				/* if on its left side, reset total beams */
				if (pbeamside(next_p, start_p) == PB_LEFT)
					beams = drmo(next_p->basictime) - 2;
			}
		} else if (prev_p->basictime > next_p->basictime && prev_p->
		stemdir == UP && gs_p->c[AX] - prev_p->c[AX] < 5 * Stepsize) {

			/* find nongrace group before "prev", if one exists */
			prev2_p = prevnongrace(prev_p);

			/* if "prev" group has partial beams . . . */
			if (prev2_p == 0 || prev_p->beamloc == STARTITEM ||
				prev_p->basictime > prev2_p->basictime) {

				/* if on its right side, reset total beams */
				if (pbeamside(prev_p, start_p) == PB_RIGHT)
					beams = drmo(prev_p->basictime) - 2;
			}
		}

		beamthick = Flagsep * beams + Stepsize;

		/*
		 * Find the AX and RY coords of the outer edge of the outer
		 * note of the other voice's group that is the farthest in the
		 * direction of our beam.  Then, if this point would run into
		 * or beyond the nongrace beam(s), find how much the Y
		 * intercept (b0) would have to move to avoid the collision.
		 * Remember the farthest move found so far.
		 */
		ycross = b1 * gs_p->c[AX] + b0;
		if (start_p->stemdir == UP) {

			fary = gs_p->notelist[0].c[RN] + Stdpad;
			if (ycross - beamthick < fary) {
				thismove = fary - (ycross - beamthick);
				move = MAX(move, thismove);
			}

		} else { /* stemdir == DOWN */

			fary = gs_p->notelist[ gs_p->nnotes-1 ].c[RS] - Stdpad;
			if (ycross + beamthick > fary) {
				thismove = fary - (ycross + beamthick);
				move = MIN(move, thismove);
			}
		}
	}

	if (move == 0.0)
		return (b0);		/* no change; return old intercept */

	/*
	 * If our beamed set has any embedded rests, we want to move the rests
	 * too.  We really only have to move rests that the other voice is
	 * bumping into, but it will probably look better to move them all.
	 * We need to move everything by a multiple of 2 stepsizes, since rests
	 * should be positioned that way.
	 */
	for (gs_p = start_p->next; gs_p != last_p; gs_p = gs_p->next) {
		/* break out if we find a rest */
		if (gs_p->grpcont == GC_REST)
			break;
	}
	if (gs_p != last_p) {
		/*
		 * We found a rest.  Round the amount the intercept moved up to
		 * a multiple of 2 stepsizes.
		 */
		move = (move < 0.0 ? -1.0 : 1.0) * 2.0 * Stepsize *
			((int)(fabs(move) / (2.0 * Stepsize)) + 1);

		/* move every embedded rest by this amount */
		for (gs_p = start_p->next; gs_p != last_p; gs_p = gs_p->next) {
			if (gs_p->grpcont == GC_REST) {
				gs_p->c[RN] += move;
				gs_p->c[RY] += move;
				gs_p->c[RS] += move;
			}
		}
	}

	return (b0 + move);	/* new Y intercept */
}
\f
/*
 * Name:        setgroupvert()
 *
 * Abstract:    Set RN and RS for each group of given type in a linked list.
 *
 * Returns:     void
 *
 * Description: This function loops through the linked list of groups for one
 *		voice for one measure.  It handles either grace groups or non-
 *		grace groups, whichever it is told to do.  It sets the RN and
 *		RS for the groups.
 */

static void
setgroupvert(grpvalue, firstgs_p, ogs_p)

int grpvalue;			/* should we do grace groups or normal groups?*/
struct GRPSYL *firstgs_p;	/* point to first group in a linked list */
struct GRPSYL *ogs_p;		/* point to first group in other linked list */

{
	struct GRPSYL *gs_p;	/* point along groups in a linked list */
	float outstem;	/* the part of the stemlen outside notes of group */
	float stemtip;	/* coord of the end of the stem */
	float old;		/* old group boundary */
	float delta;		/* change in group boundary */


	debug(32, "setgroupvert file=%s line=%d grpvalue=%d",
			firstgs_p->inputfile, firstgs_p->inputlineno, grpvalue);
	/*
	 * Loop through every group, skipping rests, spaces, and groups of the
	 * wrong type (grace vs. nongrace), setting the relative vertical
	 * coordinates.
	 */
	for (gs_p = firstgs_p; gs_p != 0; gs_p = gs_p->next) {
		if (gs_p->grpcont != GC_NOTES)
			continue;
		if (gs_p->grpvalue != grpvalue)
			continue;

		/*
		 * Back in setnotes.c, we set RY to 0, the center line of the
		 * staff.  N was set to the top of the highest note, plus
		 * padding, excluding any CSS notes.  S is the analogous thing,
		 * below.  But if all notes are CSS, N and S were set to 0.
		 */

		/*
		 * Now we want to set the stemlen, as well as we can.  For
		 * groups whose step tips are not affected by CSS, we do it in
		 * the non-CSS pass; otherwise we do it in the CSS pass.
		 */
		if (css_affects_stemtip(gs_p) == CSSpass) {

			/*
			 * If the group has a stem or pseudostem, we do this
			 * work.  Extend the appropriate group boundary to
			 * reach to the end of the stem.  Do this for all
			 * groups with real stems or pseudostems, excluding
			 * cross staff beaming (where we don't know yet how
			 * long the stems will be and we don't want to include
			 * them in the group boundary anyway, since it would
			 * prevent stem overlapping that we want).  That means
			 * half notes or shorter (excluding grace quarter
			 * notes), or anything with slash/alternations.
			 */
			if (gs_p->beamto == CS_SAME &&
			   (gs_p->basictime >= 2 || gs_p->slash_alt != 0) &&
			    gs_p->stemlen != 0.0) {

				outstem = gs_p->stemlen
					- (gs_p->notelist[0].c[RY]
					- gs_p->notelist[gs_p->nnotes-1].c[RY]);
				/*
				 * In the CSS pass we also have to adjust the
				 * absolute coords, by the same amount as the
				 * relative, since those have been set by now.
				 */
				if (gs_p->stemdir == UP) {
					stemtip = gs_p->notelist[0].c[RY]
						+ outstem;
					old = gs_p->c[RN];
					gs_p->c[RN] = MAX(stemtip, gs_p->c[RN])
						+ Stdpad;
					if (CSSpass == YES) {
						delta = gs_p->c[RN] - old;
						gs_p->c[AN] += delta;
					}
				} else {
					stemtip = gs_p->notelist[gs_p->nnotes-1]
						.c[RY] - outstem;
					old = gs_p->c[RS];
					gs_p->c[RS] = MIN(stemtip, gs_p->c[RS])
						- Stdpad;
					if (CSSpass == YES) {
						delta = gs_p->c[RS] - old;
						gs_p->c[AS] += delta;

					}
				}
			}
		}

		if (CSSpass == NO) {
			/*
			 * Increase RN and decrease RS based on "with" lists.
			 * Do this only in the first pass.  This depends on the
			 * fact that "with" lists are always put on the side
			 * away from the other staff, when CSS is involved.
			 */
			expgroup(gs_p, ogs_p);
		} else {
			/*
			 * In the CSS pass, various group boundaries need more
			 * adjustment.
			 */
			if (gs_p->stemdir == UP) {
				if (gs_p->stemto == CS_ABOVE && NNN(gs_p) == 0){
					gs_p->c[RS] = gs_p->notelist[
						gs_p->nnotes-1].c[RS] - Stdpad;
					gs_p->c[AS] += gs_p->c[RS];
				}
				if (gs_p->stemto == CS_BELOW && NNN(gs_p) == 0){
					gs_p->c[RN] = gs_p->notelist[
						gs_p->nnotes-1].c[RY] +
						gs_p->stemlen;
					expgroup(gs_p, ogs_p);
					gs_p->c[AN] = gs_p->c[AY] + gs_p->c[RN];
				}
				if (gs_p->stemto == CS_SAME &&
						gs_p->stemlen > 0) {
					gs_p->c[RN] = gs_p->notelist
					[gs_p->nnotes-1].c[RY] + gs_p->stemlen
					+ Stdpad;

					gs_p->c[AN] = gs_p->notelist
					[gs_p->nnotes-1].c[AY] + gs_p->stemlen
					+ Stdpad;
				}
				if (gs_p->stemto == CS_ABOVE &&
						gs_p->stemlen == 0) {
					gs_p->c[RN] = gs_p->notelist[0].c[RN]
						+ Stdpad;
					gs_p->c[AN] = gs_p->notelist[0].c[AN]
						+ Stdpad;
				}
			} else {
				if (gs_p->stemto == CS_BELOW && NNN(gs_p) == 0){
					gs_p->c[RN] = gs_p->notelist[0].c[RN]
						+ Stdpad;
					gs_p->c[AN] += gs_p->c[RN];
				}
				if (gs_p->stemto == CS_ABOVE && NNN(gs_p) == 0){
					gs_p->c[RS] = gs_p->notelist[0].c[RY] -
						gs_p->stemlen;
					expgroup(gs_p, ogs_p);
					gs_p->c[AS] = gs_p->c[AY] + gs_p->c[RS];
				}
				if (gs_p->stemto == CS_SAME &&
						gs_p->stemlen > 0) {
					gs_p->c[RS] = gs_p->notelist[0].c[RY]
						- gs_p->stemlen - Stdpad;

					gs_p->c[AS] = gs_p->notelist[0].c[AY]
						- gs_p->stemlen - Stdpad;
				}
				if (gs_p->stemto == CS_BELOW &&
						gs_p->stemlen == 0) {
					gs_p->c[RS] = gs_p->notelist
						[gs_p->nnotes-1].c[RS] - Stdpad;
					gs_p->c[AS] = gs_p->notelist
						[gs_p->nnotes-1].c[AS] - Stdpad;
				}
			}
		}
	}
}
\f
/*
 * Name:        settuplet()
 *
 * Abstract:    Figure out where tuplet bracket goes and change RN and RS.
 *
 * Returns:     void
 *
 * Description: This function is given a pointer to the first GRPSYL in a
 *		tuplet whose bracket is to be printed.  It figures out where
 *		the tuplet bracket and number should go, and sets tupextend for
 *		all the groups, to show where the tuplet bracket would go.
 *		Even if the bracket ends up not getting printed, this is needed
 *		for placing the number.
 */

static void
settuplet(start_p, staff_p)

struct GRPSYL *start_p;		/* first group in the tuplet */
struct STAFF *staff_p;		/* staff the tuplet is on */

{
	struct GRPSYL *gs_p;	/* loop through the groups in the tuplet */
	struct GRPSYL *last_p;	/* point the last group in the tuplet */
	struct GRPSYL *end_p;	/* point beyond the last group in the tuplet */
	struct NOTE *note_p;	/* pointer to an outside note of a group */
	float sx, sy;		/* sum of x and y coords of north or south */
	float xbar, ybar;	/* average x and y coords of north or south */
	float top, bottom;	/* numerator & denominator for finding b1 */
	float temp;		/* scratch variable */
	float startx, endx;	/* x coord of first and last north or south */
	float starty, endy;	/* y coord of first and last north or south */
	float b0, b1;		/* y intercept and slope */
	float maxb0, minb0;	/* max and min y intercepts */
	float shift;		/* x dist bracket reaches beyond end groups */
	float acceast, accwest;	/* horizontal coords of an accidental */
	float accvert;		/* north or south of an accidental */
	float asc, des, wid;	/* ascent, descent, and width of an acc */
	float numeast, numwest;	/* horizontal coords of the tuplet number */
	float numvert;		/* vertical edge of number closest to staff */
	float height;		/* height of the tuplet number */
	int css_affects_tup;	/* does CSS affect any group in the tuplet? */
	int coord;		/* RN or RS, depending on where bracket goes */
				/* or AN or AS if CSSpass == YES */
	int halfstaff;		/* half the height of staff, in stepsizes */
	int num;		/* number of groups in tuplet */
	float vert[2];		/* vertical coords of two groups */
	int n;			/* loop variable */


	debug(32, "settuplet file=%s line=%d", start_p->inputfile,
			start_p->inputlineno);
	/*
	 * If start_p is pointing at a grace group that precedes the first real
	 * group of the tuplet, move start_p forward to the first real group.
	 * Actually, this shouldn't be necessary; the parser is doing it now.
	 */
	while (start_p->grpvalue == GV_ZERO)
		start_p = start_p->next;

	/*
	 * Find out which side the tuplet number (and bracket, if needed)
	 * should go on.  That determines which coord we pay attention to.
	 * The other determining factor is whether this is the CSS pass.
	 */
	if (tupdir(start_p, staff_p) == PL_ABOVE) {
		coord = CSSpass == YES ? AN : RN;
	} else {
		coord = CSSpass == YES ? AS : RS;
	}

	/* find whether CSS affects any group in the set */
	css_affects_tup = NO;
	if (CSSused == YES) {	/* don't waste time looking if CSS not used */
		for (gs_p = start_p; gs_p != 0 && ! (gs_p != start_p &&
					gs_p->prev->tuploc == ENDITEM);
					gs_p = gs_p->next) {
			if (gs_p->stemto == CS_ABOVE &&
						(coord == AN || coord == AN) ||
			    gs_p->stemto == CS_BELOW &&
						(coord == AS || coord == AS)) {
				css_affects_tup = YES;
				break;
			}
		}
	}

	/*
	 * If no groups are affected by CSS, handle this tuplet on the
	 * first pass only.  If some are affected, handle it on the second
	 * pass only.
	 */
	if (css_affects_tup != CSSpass) {
		return;
	}

	last_p = 0;	/* prevent useless 'used before set' warnings */

	/*
	 * If the first group is STARTITEM, there are multiple groups in the
	 * tuplet.  If it is LONEITEM, there is only one.
	 */
	if (start_p->tuploc == STARTITEM) {
		/*
		 * Use linear regression to find the best-fit line through the
		 * RN or RS, or AN or AS, of the groups, as the case may be.
		 * The X coords used are absolute, but the Y coords are, in the
		 * normal (non-CSSpass case) relative to the center line of the
		 * staff, since we don't know the absolute Y coords yet, and it
		 * wouldn't affect the result anyway.  But if this is the CSS
		 * pass, we do know the absolute vertical coords, and we have
		 * to use them, since we are dealing with two staffs.
		 *
	 	 * First get sum of x and y coords, to find averages.  Remember
		 * where last valid group is.  Only nongrace groups can be
		 * tuplet members, although there could be grace groups before
		 * a tuplet member.  We ignored any grace group before the
		 * first real tuplet member, but any others must be dealt with.
		 */
		sx = sy = 0;
		num = 0;
		for (gs_p = start_p; gs_p != 0 && ! (gs_p != start_p &&
					gs_p->prev->tuploc == ENDITEM);
					gs_p = gs_p->next) {
			sx += gs_p->c[AX];
			sy += gs_p->c[coord];
			num++;			/* count number of groups */
			last_p = gs_p;
		}
		/* last_p now points at last valid group */

		end_p = gs_p;	/* point end_p beyond last tuplet member */

		xbar = sx / num;
		ybar = sy / num;

		/* accum numerator & denominator of regression formula for b1 */
		top = bottom = 0;
		for (gs_p = start_p; gs_p != end_p; gs_p = gs_p->next) {
			temp = gs_p->c[AX] - xbar;
			top += temp * (gs_p->c[coord] - ybar);
			bottom += temp * temp;
		}

		b1 = top / bottom;		/* slope */
		/*
		 * We could also figure:
		 *	b0 = ybar - b1 * xbar;		y intercept
		 * to get the equation of the regression line:  y = b0 + b1 * x
		 * but we're going to change b0 later anyway.  Now, there are
		 * certain cases where we want to override the slope determined
		 * by regression, so revise b1 if that is the case.
		 */

		/* if first and last groups are equal, force horizontal */
		if (start_p->c[coord] == last_p->c[coord])
			b1 = 0.0;

		/* if repeating pattern of two coords, force horizontal */
		if (b1 != 0.0 && num >= 4 && num % 2 == 0) {
			vert[0] = start_p->c[coord];
			vert[1] = start_p->next->c[coord];
			for (n = 0, gs_p = start_p; n < num;
					n++, gs_p = gs_p->next) {
				if (n >= 2 && gs_p->c[coord] != vert[n % 2])
					break;
			}
			if (n == num)
				b1 = 0.0;
		}

	} else {	/* LONEITEM */
		/*
		 * There's only one group, so there's no need to apply linear
		 * regression.  But we need to set up certain variables so that
		 * later code in this function can treat both cases the same.
		 */
		last_p = start_p;	/* point at last tuplet member */
		end_p = start_p->next;	/* point beyond last tuplet member */
		b1 = 0;			/* set horizontal slope */
		b0 = start_p->c[coord];	/* y intercept based on this group */
	}

	/*
	 * Find half the width of a note head; the end of the tuplet bracket
	 * reaches that far beyond the X coords of the outer groups.  Set
	 * the X positions for these ends.
	 */
	shift = getstemshift(last_p);
	startx = start_p->c[AX] - shift;	/* start of tuplet bracket */
	endx = last_p->c[AX] + shift;		/* end of tuplet bracket */

	/*
	 * The original line derived by linear regression must be adjusted in
	 * certain ways.  First, don't let the slope exceed plus or minus 0.7,
	 * since that would look bad.
	 */
	if (b1 > 0.7)
		b1 = 0.7;
	else if (b1 < -0.7)
		b1 = -0.7;

	/*
	 * Calculate a new y intercept (b0).  First pass parallel lines
	 * through each group's extremity, and record the maximum and minimum
	 * y intercepts that result.
	 */
	b0 = start_p->c[coord] - b1 * start_p->c[AX];
	maxb0 = minb0 = b0;		/* init to value for first group */
	/* look at rest of them */
	for (gs_p = start_p; gs_p != end_p; gs_p = gs_p->next) {
		b0 = gs_p->c[coord] - b1 * gs_p->c[AX];
		if (b0 > maxb0)
			maxb0 = b0;
		else if (b0 < minb0)
			minb0 = b0;
	}

	/*
	 * The outer edge of the tuplet bracket, including the number, should
	 * be TUPHEIGHT away from the group that sticks out the farthest.
	 */
	if (coord == RN || coord == AN) {
		b0 = maxb0 + Tupheight;
	} else {	/* RS or AS */ 
		b0 = minb0 - Tupheight;
	}

	/*
	 * Calculate the Y positions of the start and end of the bracket from
	 * the X positions, and the slope and Y intercept we have tentatively
	 * chosen.  If, however, the bracket is going to fall within the staff,
	 * make adjustments so it won't.
	 */
	starty = b0 + b1 * startx;	/* y coord near left end of beam */
	endy = b0 + b1 * endx;		/* y coord near right end of beam */
	halfstaff = svpath(staff_p->staffno, STAFFLINES)->stafflines == 5
			? 4 : 1;

	if (coord == RN) {
		if (starty < halfstaff * Stepsize + Tupheight)
			starty = halfstaff * Stepsize + Tupheight;
		if (endy < halfstaff * Stepsize + Tupheight)
			endy = halfstaff * Stepsize + Tupheight;
	} else if (coord == RS) {
		if (starty > -halfstaff * Stepsize - Tupheight)
			starty = -halfstaff * Stepsize - Tupheight;
		if (endy > -halfstaff * Stepsize - Tupheight)
			endy = -halfstaff * Stepsize - Tupheight;
	}

	/*
	 * If y at the ends of the bracket only differs by less than 2 points,
	 * set end equal to the start to avoid a jagged look.
	 */
	if (endy - starty < 2 * POINT && endy - starty > -2 * POINT) {
		endy = (starty + endy) / 2.;
		starty = endy;
	}

	/* recalculate slope and y intercept from (possibly) new endpoints */
	b1 = (endy - starty) / (endx - startx);		/* slope */
	b0 = starty - b1 * startx;			/* y intercept */

	/*
	 * The vertical extension of accidentals is not included in group
	 * boundaries, and so the calculation of the tuplet bracket's equation
	 * has ignored them so far.  In general, this is no problem.  If an
	 * accidental touches or slightly crosses that line, who cares?  But we
	 * would like to keep it from running into the tuplet number.  So scan
	 * through the notes closest to the bracket, checking for accidentals.
	 * (Notes a step or more from there would never really be a problem.)
	 * Also, accidentals on the first group can never be a problem.
	 */
	(void)tupnumsize(start_p, &numwest, &numeast, &height, staff_p);
	numvert = (starty + endy) / 2 + (coord == RN || coord == AN ?
			-height : height) / 2;

	for (gs_p = start_p->next; gs_p != end_p; gs_p = gs_p->next) {

		if (gs_p->grpcont != GC_NOTES)
			continue;

		note_p = &gs_p->notelist[ coord == RN || coord == AN ?
				0 : gs_p->nnotes - 1 ];
		if (note_p->accidental == '\0')
			continue;

		/*
		 * The note of this group nearest the bracket has an acci-
		 * dental.  Find its horizontal midpoint, and vertical coord
		 * nearest the bracket.  Add padding to the vertical coord.
		 */
		accdimen(note_p, &asc, &des, &wid);
		asc *= Staffscale;
		des *= Staffscale;
		wid *= Staffscale;

		accwest = gs_p->c[AX] + note_p->waccr;
		acceast = accwest + wid;

		if (coord == RN || coord == AN) {
			accvert = note_p->c[CSSpass == YES ? AY : RY]
					+ asc + Stepsize;
		} else {
			accvert = note_p->c[CSSpass == YES ? AY : RY]
					- des - Stepsize;
		}

		/* if acc is completely to the left of the number, try next */
		if (acceast < numwest)
			continue;

		/* if acc is completely to the right, get out */
		if (accwest > numeast)
			break;

		/*
		 * If acc sticks out beyond the edge of the number, change the
		 * y intercept by that amount to prevent it.  Then get out,
		 * since no later groups could be that nearby.
		 */
		if ((coord == RN || coord == AN) && accvert > numvert ||
		    (coord == RS || coord == AS) && accvert < numvert) {
			b0 += accvert - numvert;
			break;
		}
	}

	/*
	 * At this point we know where to put the tuplet bracket.  Set
	 * tupextend in all the groups, to reach the tuplet bracket.
	 */
	for (gs_p = start_p; gs_p != end_p; gs_p = gs_p->next)
		gs_p->tupextend = (b0 + b1 * gs_p->c[AX]) - gs_p->c[coord];
}
\f
/*
 * Name:        expgroup()
 *
 * Abstract:    Decide side for "with" list & expand vertical group vertically.
 *
 * Returns:     void
 *
 * Description: This function decides which side of the group a "with" list
 *		should be put, and calls applywith() to alter the group's
 *		vertical boundaries accordingly.
 */

static void
expgroup(gs_p, ogs_p)

struct GRPSYL *gs_p;	/* the group to be worked on */
struct GRPSYL *ogs_p;	/* the other group */

{
	struct GRPSYL *g_p;	/* earlier GRPSYLs in *gs_p's list */
	RATIONAL vtime;		/* time preceding this group in measure */
	int side;		/* side to put things on (1=top, -1=bottom) */


	side = 0;	/* prevent useless 'used before set' warnings */

	/*
	 * Define a chunk of code for the cases where the stem may be allowed
	 * to go either way.  It goes opposite the stem for normal, with the
	 * stem for tab.
	 */
#define FREESTEM							\
	{								\
		if (is_tab_staff(gs_p->staffno) == YES) {		\
			side = -1;	/* we know stemdir is DOWN */	\
			gs_p->normwith = NO;				\
		} else {						\
			side = gs_p->stemdir == UP ? -1 : 1;		\
			gs_p->normwith = YES;				\
		}							\
	}

	/*
	 * Define a chunk of code for the cases where the stem has to go a
	 * certain way, determined by which voice this is, unless forced by the
	 * user.  The "with" items are always above a voice acting as voice 1,
	 * and below a voice acting as voice 2.
	 */
#define FIXEDSTEM							\
	{								\
		if (gs_p->pvno == 1) {					\
			side = 1;					\
			gs_p->normwith = gs_p->stemdir == UP ? NO : YES;\
		} else {						\
			side = -1;					\
			gs_p->normwith = gs_p->stemdir == DOWN ? NO : YES;\
		}							\
	}

	/*
	 * If there is cross staff stemming, that consideration overrides all
	 * others.  We want to keep the "with" items towards our staff, hoping
	 * they will be less likely to collide with something there.
	 */
	if (gs_p->stemto != CS_SAME) {
		if (gs_p->stemto == CS_ABOVE) {
			gs_p->normwith = gs_p->stemdir == UP ? YES : NO;
			side = -1;
		} else {	/*  CS_BELOW */
			gs_p->normwith = gs_p->stemdir == UP ? NO : YES;
			side = 1;
		}
		applywith(gs_p, side);
		return;
	}

	/*
	 * Switch on vscheme to decide which side of the group the "with"
	 * things will be put on.
	 */
	switch (svpath(gs_p->staffno, VSCHEME)->vscheme) {
	case V_1:
		FREESTEM
		break;

	case V_2OPSTEM:
		FIXEDSTEM
		break;

	case V_2FREESTEM:
		/*
		 * Figure out where this group starts by adding up the time
		 * values of all previous groups in the measure.  Then, treat
		 * this like V_1 or V_2OPSTEM, based on whether the other
		 * voice has space here.
		 */
		vtime = Zero;
		for (g_p = gs_p->prev; g_p != 0; g_p = g_p->prev)
			vtime = radd(vtime, g_p->fulltime);

		if (hasspace(ogs_p, vtime, radd(vtime, gs_p->fulltime))) {
			FREESTEM
		} else {
			FIXEDSTEM
		}
		break;

	case V_3OPSTEM:
		if (gs_p->pvno == 3) {
			FREESTEM	/* voice 3 is always like V_1 */
		} else {
			FIXEDSTEM
		}
		break;

	case V_3FREESTEM:
		if (gs_p->pvno == 3) {
			FREESTEM	/* voice 3 is always like V_1 */
		} else {
			/* voices 1 and 2 act like V_2FREESTEM */
			vtime = Zero;
			for (g_p = gs_p->prev; g_p != 0; g_p = g_p->prev)
				vtime = radd(vtime, g_p->fulltime);

			if (hasspace(ogs_p, vtime, radd(vtime, gs_p->fulltime))) {
				FREESTEM
			} else {
				FIXEDSTEM
			}
		}
		break;
	}

	/*
	 * If there is cross staff beaming and the "with" items are to be on
	 * the beam side, we can't do anything yet since we don't know yet
	 * where the beam will be.
	 */
	if (gs_p->beamto != CS_SAME && gs_p->normwith == NO) {
		return;
	}

	applywith(gs_p, side);
}
\f
/*
 * Name:        applywith()
 *
 * Abstract:    Expand vertical boundaries of group, based on "with" list.
 *
 * Returns:     void
 *
 * Description: This function adds to the RN coord of a group and/or subtracts
 *		from the RS coord, if a "with" list is present.
 */

static void
applywith(gs_p, side)

struct GRPSYL *gs_p;	/* the group to be worked on */
int side;		/* side to put things on (1=top, -1=bottom) */

{
	int n;			/* loop variable */
	float hi;		/* height of a list item */


	/*
	 * Loop through all the "with" items, expanding the N or S coord of
	 * the group.  Each item is allowed enough space for its height, or
	 * MINWITHHEIGHT, whichever is greater.  In the print phase, items of
	 * height less than MINWITHHEIGHT will be placed so as to avoid staff
	 * lines as much as possible.
	 */
	for (n = 0; n < gs_p->nwith; n++) {
		hi = strheight(gs_p->withlist[n]);
		hi = MAX(hi, Staffscale * MINWITHHEIGHT);
		if (side == 1)
			gs_p->c[RN] += hi;
		else
			gs_p->c[RS] -= hi;
	}
}