Import upstream version 5.3.

[mup] / mup / mup / plutils.c

/* Copyright (c) 1995, 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004,
 * 2005, 2006 by Arkkra Enterprises */
/* All rights reserved */
/*
 * Name:	plutils.c
 *
 * Description:	This file contains utility functions belonging to the placement
 *		phase.  Some of them are also used by other phases.
 */

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

static int phrase_tieslur_note P((struct GRPSYL *gs_p, int nidx, int side,
		int interfere));
static int tied_to_nidx P((struct GRPSYL *gs_p, int nidx));
static int slurred_to_nidx P((struct GRPSYL *gs_p, int nidx, int sidx));
static RATIONAL lefttime P((double count, struct GRPSYL *firstgs_p,
		int timeden));
static RATIONAL righttime P((double count, struct GRPSYL *firstgs_p,
		int timeden));

/*
 * Name:        nextnongrace()
 *
 * Abstract:    Return next nongrace group in a GRPSYL list.
 *
 * Returns:     pointer to GRPSYL of next nongrace group, 0 if none
 *
 * Description: This function loops down the GRPSYL linked list from the given
 *		starting point.  It returns the next nongrace GRPSYL, or 0
 *		if none.
 */

struct GRPSYL *
nextnongrace(gs_p)

struct GRPSYL *gs_p;	/* current group */

{
	gs_p = gs_p->next;
	while (gs_p != 0 && gs_p->grpvalue == GV_ZERO)
		gs_p = gs_p->next;
	return (gs_p);
}
\f
/*
 * Name:        prevnongrace()
 *
 * Abstract:    Return previous nongrace group in a GRPSYL list.
 *
 * Returns:     pointer to GRPSYL of previous nongrace group, 0 if none
 *
 * Description: This function loop up the GRPSYL linked list from the given
 *		starting point.  It returns the previous nongrace GRPSYL, or 0
 *		if none.
 */

struct GRPSYL *
prevnongrace(gs_p)

struct GRPSYL *gs_p;	/* current group */

{
	gs_p = gs_p->prev;
	while (gs_p != 0 && gs_p->grpvalue == GV_ZERO)
		gs_p = gs_p->prev;
	return (gs_p);
}
\f
/*
 * Name:        nextglobnongrace()
 *
 * Abstract:    Return next nongrace group in this voice.
 *
 * Returns:     pointer to GRPSYL of next nongrace group, 0 if none
 *
 * Description: This function, given a nongrace and the MLL structure it hangs
 *		off of, returns the next nongrace in this voice, even if it's in
 *		the next measure.  If it is in the next measure, *mll_p_p gets
 *		updated.  But if that next measure is a second or later ending,
 *		it's not considered to be a "next" measure, so return 0.
 */

struct GRPSYL *
nextglobnongrace(gs_p, mll_p_p)

struct GRPSYL *gs_p;		/* current group */
struct MAINLL **mll_p_p;	/* MLL structure it is hanging off of */

{
	do {
		gs_p = nextgrpsyl(gs_p, mll_p_p);
	} while (gs_p != 0 && gs_p->grpvalue == GV_ZERO);
	return (gs_p);
}
\f
/*
 * Name:        prevglobnongrace()
 *
 * Abstract:    Return previous nongrace group in this voice.
 *
 * Returns:     pointer to GRPSYL of previous nongrace group, 0 if none
 *
 * Description:	This function, given a nongrace and the MLL structure it hangs
 *		off of, returns the prev nongrace in this voice, even if it's
 *		in an earlier measure.  If we are at the start of an ending,
 *		it skips over any previous ending and goes to the measure
 *		preceding the first ending.  If the resulting nongrace is in a
 *		previous measure, *mll_p_p gets updated.
 */

struct GRPSYL *
prevglobnongrace(gs_p, mll_p_p)

struct GRPSYL *gs_p;		/* current group */
struct MAINLL **mll_p_p;	/* MLL structure it is hanging off of */

{
	do {
		gs_p = prevgrpsyl(gs_p, mll_p_p);
	} while (gs_p != 0 && gs_p->grpvalue == GV_ZERO);
	return (gs_p);
}
\f
/*
 * Name:        drmo()
 *
 * Abstract:    Detect rightmost one.
 *
 * Returns:     void
 *
 * Description: This function returns the bit position of the rightmost bit
 *		that is a 1 in the given number, the low order bit being
 *		bit 0.  The given number must not be 0.
 */

int
drmo(num)

register int num;

{
	register int n;

	for (n = 0; n < 8 * sizeof(int); n++) {
		if ( (num & (1 << n)) != 0 )
			return (n);
	}
	pfatal("0 was passed to drmo");
	return (0);	/* dead code, but keeps lint happy */
}
\f
/*
 * Name:        tieslurpad()
 *
 * Abstract:    How much tie/slur padding is needed after this group?
 *
 * Returns:     Padding in inches.
 *
 * Description: This function returns the amount of padding needed after a
 *		group due to ties or slurs, if the given group is tied to the
 *		next group, or any note in it is tied or slurred to a note
 *		in the following group.  Otherwise it returns zero.
 *		NOTE:  This function ignores staffscale.
 */

double
tieslurpad(staff_p, gs_p)

struct STAFF *staff_p;		/* the staff the group is connected to */
struct GRPSYL *gs_p;		/* the group after which padding may occur */

{
	struct NOTE *note_p;	/* point at a note structure */
	struct GRPSYL *gtemp_p;	/* temp GRPSYL pointer */
	struct GRPSYL *this_p;	/* first GRPSYL in this voice */
	struct GRPSYL *that_p;	/* first GRPSYL in other voice */
	RATIONAL starttime;	/* time into measure where *gs_p starts */
	float pad;		/* how much padding is needed */
	int interfere;		/* does other voice have notes/rests here? */
	int stepdiff;		/* vertical reach of a curve */
	int n;			/* index into notes in group */
	int s;			/* index into notes slurred to */


	/* syllables can't have ties or slurs */
	if (gs_p->grpsyl != GS_GROUP)
		return (0);

	/* rests and spaces can't have ties or slurs */
	if (gs_p->grpcont != GC_NOTES)
		return (0);

	/* if last group in measure, don't need any more space */
	if (gs_p->next == 0)
		return (0);

	/*
	 * Find the first group in this measure, and total time preceding the
	 * group we were given.  We need this to figure out which voice we are
	 * in, and, if there is another voice, whether it has only spaces
	 * during the time of our group, which affects how the curves should
	 * look.
	 */
	starttime = Zero;
	for (gtemp_p = gs_p->prev, this_p = gs_p; gtemp_p != 0;
			this_p = gtemp_p, gtemp_p = gtemp_p->prev)
		starttime = radd(starttime, gtemp_p->fulltime);

	/* point at other voice, or null pointer if none */
	if (staff_p->groups_p[0] == this_p)
		that_p = staff_p->groups_p[1];	/* might be 0 */
	else if (staff_p->groups_p[1] == this_p)
		that_p = staff_p->groups_p[0];	/* might be 0 */
	else
		that_p = 0;	/* we are voice 3, ignore other voices */

	if (that_p == 0 || hasspace(that_p, starttime,
				radd(starttime, gs_p->fulltime)))
		interfere = NO;
	else
		interfere = YES;

	pad = 0;		/* start with no padding */

	/*
	 * Loop through every note in this group.  If it's tied, check each
	 * note to see if either it or the note it's tied to is ineligible for
	 * phrase-like curves.  If so, there will be a horizontally aligned
	 * curve, and we need to pad.  The note must be the same in both
	 * groups, so there's no need to consider vertical distances at this
	 * point.  Then loop through the 0 or more slurs from this note to
	 * note(s) in the next group.  For each one, find the vertical distance
	 * between the two notes.  The padding it needs is based on this and on
	 * whether phrase-like curves can be drawn.  Keep track of the maximum
	 * padding needed by any pair of notes.
	 * We also need to pad if the stems are UP-DOWN, because that leaves no
	 * room for the curve.
	 */
	for (n = 0; n < gs_p->nnotes; n++) {
		note_p = &gs_p->notelist[n];
		if (note_p->tie == YES) {
			if (gs_p->stemdir == UP && gs_p->next->stemdir == DOWN
			|| phrase_tieslur_note(gs_p, n, STARTITEM, interfere)
			== NO || phrase_tieslur_note(gs_p->next, tied_to_nidx(
			gs_p, n), ENDITEM, interfere) == NO)
				pad = MAX(pad, TIESLURPAD);
		}
		for (s = 0; s < note_p->nslurto; s++) {
			/*
			 * If it's a slur to/from nowhere, don't deal with it
			 * here.  It is considered along with the width of the
			 * individual note.
			 */
			if (IS_NOWHERE(note_p->slurtolist[s].octave))
				continue;	/* from nowhere */

			stepdiff = abs(
					( note_p->octave * 7 +
					Letshift[ note_p->letter - 'a' ] ) -
					( note_p->slurtolist[s].octave * 7 +
					Letshift[ note_p->slurtolist[s].letter
						- 'a' ] )
					);
			if (gs_p->stemdir == UP && gs_p->next->stemdir == DOWN
			|| phrase_tieslur_note(gs_p, n, STARTITEM, interfere)
			== NO || phrase_tieslur_note(gs_p->next,
			slurred_to_nidx(gs_p, n, s), ENDITEM, interfere) == NO){
				pad = MAX(pad, stepdiff <= 3 ? TIESLURPAD :
				TIESLURPAD + (stepdiff - 3) * STEPSIZE / 2);
			} else {
				pad = MAX(pad, stepdiff <= 3 ? 0 :
				(stepdiff - 3) * STEPSIZE / 2);
			}
		}
	}

	return (pad);		/* max padding needed by any pair of notes */
}
\f
/*
 * Name:        phrase_tieslur_note()
 *
 * Abstract:    Is the given note the end note and eligible for "new" tie/slur?
 *
 * Returns:     YES or NO
 *
 * Description: This function determines whether a tie or slur to/from the
 *		given note is to be drawn like a phrase mark (as opposed to
 *		drawing it vertically aligned with the note).
 */

static int
phrase_tieslur_note(gs_p, nidx, side, interfere)

struct GRPSYL *gs_p;		/* point at note's group */
int nidx;			/* index to this note in notelist */
int side;			/* STARTITEM (curve here to right) or ENDITEM */
int interfere;			/* does the other voice have notes/rests here?*/

{
	/* check for each bad condition, returning NO if it exists */

	/* inner note of a group */
	if (nidx != 0 && nidx != gs_p->nnotes - 1)
		return (NO);

	/* bottom note of voice 1 and other voice interferes */
	if (gs_p->vno == 1 && nidx == gs_p->nnotes - 1 && interfere)
		return (NO);

	/* top note of voice 2 and other voice interferes */
	if (gs_p->vno == 2 && nidx == 0 && interfere)
		return (NO);

	/* antistem note if "with" list is present */
	/*  (don't need to check normwith; if it weren't YES we would have */
	/*  returned above) */
	if (gs_p->nwith != 0 && gs_p->stemdir == UP && nidx == gs_p->nnotes - 1)
		return (NO);

	/* antistem note if "with" list is present */
	/*  (don't need to check normwith; if it weren't YES we would have */
	/*  returned above) */
	if (gs_p->nwith != 0 && gs_p->stemdir == DOWN && nidx == 0)
		return (NO);

	/* stem in the way of left end of curve */
	if (side == STARTITEM && gs_p->basictime >= 2 && gs_p->stemdir == UP &&
			nidx == 0 && gs_p->nnotes > 1)
		return (NO);

	/* stem in the way of right end of curve */
	if (side == ENDITEM && gs_p->basictime >= 2 && gs_p->stemdir == DOWN &&
			nidx == gs_p->nnotes - 1 && gs_p->nnotes > 1)
		return (NO);

	return (YES);
}
\f
/*
 * Name:        tied_to_nidx()
 *
 * Abstract:    Return the note index of the note the given note is tied to.
 *
 * Returns:     index into gs_p->next->notelist
 *
 * Description: This function is given a valid group (not the last one in the
 *		measure) and an index into its notelist to a note that is tied
 *		to the next group.  It returns the index into the next group's
 *		notelist to the note that the first group's note is tied to.
 */

static int
tied_to_nidx(gs_p, nidx)

struct GRPSYL *gs_p;		/* point at note's group */
int nidx;			/* index to this note in notelist */

{
	struct NOTE *nl_ptr;	/* ptr to next group's notelist */
	int n;


	nl_ptr = gs_p->next->notelist;

	for (n = 0; n < gs_p->next->nnotes; n++) {
		if (gs_p->notelist[nidx].letter == nl_ptr[n].letter &&
		    gs_p->notelist[nidx].octave == nl_ptr[n].octave)
			return (n);
	}

	pfatal("tied_to_nidx: can't find note tied to");
	return (0);		/* to keep lint happy */
}
\f
/*
 * Name:        slurred_to_nidx()
 *
 * Abstract:    Return the note index of the note the given note is slurred to.
 *
 * Returns:     index into gs_p->next->notelist
 *
 * Description: This function is given a valid group (not the last one in the
 *		measure) and an index into its notelist to a note that is tied
 *		to the next group.  It returns the index into the next group's
 *		notelist to the note that the first group's note is tied to.
 */

static int
slurred_to_nidx(gs_p, nidx, sidx)

struct GRPSYL *gs_p;		/* point at note's group */
int nidx;			/* index to this note in notelist */
int sidx;			/* index to slurred to note in slurto list */

{
	struct NOTE *nl_ptr;	/* ptr to next group's notelist */
	int n;


	nl_ptr = gs_p->next->notelist;

	for (n = 0; n < gs_p->next->nnotes; n++) {
		if (gs_p->notelist[nidx].slurtolist[sidx].letter ==
					nl_ptr[n].letter &&
		    gs_p->notelist[nidx].slurtolist[sidx].octave ==
					nl_ptr[n].octave)
			return (n);
	}

	pfatal("slurred_to_nidx: can't find note slurred to");
	return (0);		/* to keep lint happy */
}
\f
/*
 * Name:        hasspace()
 *
 * Abstract:    Finds out if the given voice has space during given time.
 *
 * Returns:     YES or NO
 *
 * Description: This function is given a linked list of groups to check
 *		during a given time interval.  If the list consists entirely
 *		of space(s) during the time interval, the function returns
 *		YES.  Otherwise it returns NO.  If vtime2 is greater than the
 *		length of a measure, the extra, nonexistent time is regarded
 *		as all spaces.  If the linked list of groups doesn't exist
 *		(gs_p is a null pointer), the function returns YES, since
 *		there is nothing there but "space".
 */

int
hasspace(gs_p, vtime, vtime2)

register struct GRPSYL *gs_p;	/* starts pointing at the first GRPSYL list */
RATIONAL vtime, vtime2;	/* time when to start and stop checking for space */

{
	RATIONAL t;		/* accumulate time */
	int oldcont;		/* content of previous group */


	/* "no linked list exists" counts as all spaces */
	if (gs_p == 0)
		return (YES);

	oldcont = GC_SPACE;	/* prevent useless 'used before set' warning */

	/* accumulate time until crossing vtime boundary */
	for (t = Zero; LT(t, vtime); gs_p = gs_p->next) {
		if (gs_p->grpvalue == GV_ZERO)
			continue;
		t = radd(t, gs_p->fulltime);
		oldcont = gs_p->grpcont;
	}

	if (GT(t, vtime) && oldcont != GC_SPACE)
		return (NO);

	for ( ; gs_p != 0 && LT(t, vtime2); gs_p = gs_p->next) {
		if (gs_p->grpvalue == GV_ZERO)
			continue;
		if (gs_p->grpcont != GC_SPACE)
			return (NO);
		t = radd(t, gs_p->fulltime);
	}

	return (YES);
}
\f
/*
 * Name:        closestgroup()
 *
 * Abstract:    Find closest nongrace group in this voice to given time value.
 *
 * Returns:     pointer to the closest nongrace GRPSYL
 *
 * Description: This function finds the GRPSYL in the given linked list that is
 *		closest, timewise, to the given count number, ignoring grace
 *		groups.
 */

struct GRPSYL *
closestgroup(count, firstgs_p, timeden)

double count;			/* which count of the measure */
struct GRPSYL *firstgs_p;	/* first GRPSYL of relevant voice in measure */
int timeden;			/* denominator of current time signature */

{
	RATIONAL reqtime;	/* time requested */
	RATIONAL tottime;	/* total time in measure so far */
	RATIONAL otottime;	/* old total time in measure so far */
	struct GRPSYL *gs_p;	/* point along group list */
	struct GRPSYL *ogs_p;	/* (old) point along group list */


	/* skip over any initial grace groups */
	if (firstgs_p->grpvalue == GV_ZERO)
		firstgs_p = nextnongrace(firstgs_p);

	/* if at or before the first count, it's closest to first group */
	if (count <= 1)
		return (firstgs_p);

	/* get requested time to nearest tiny part of a count, in lowest terms*/
	reqtime.n = 4 * MAXBASICTIME * (count - 1) + 0.5;
	reqtime.d = 4 * MAXBASICTIME * timeden;
	rred(&reqtime);

	/*
	 * Loop through this voice accumulating time values.  As soon as we
	 * equal or exceed the requested time value, check whether the
	 * requested time is closer to the new accumulated time, or that before
	 * this last group.  Return the closest one.
	 */
	tottime = Zero;
	for (ogs_p = firstgs_p, gs_p = nextnongrace(ogs_p); gs_p != 0;
				ogs_p = gs_p, gs_p = nextnongrace(gs_p)) {
		otottime = tottime;
		tottime = radd(tottime, ogs_p->fulltime);
		if (GE(tottime, reqtime)) {
			if (GT( rsub(reqtime,otottime), rsub(tottime,reqtime) ))
				return (gs_p);
			else
				return (ogs_p);
		}
	}

	/* requested time is after last group; return last group */
	return (ogs_p);
}
\f
/*
 * Name:        chkallspace()
 *
 * Abstract:    Check if voice is all spaces for the voice this stuff is on.
 *
 * Returns:     YES or NO
 *
 * Description: This function checks where one voice seems to be all spaces
 *		during the duration of a phrase mark, or other stuff which must
 *		be associated with a definite group.  The tricky thing is that
 *		until we've decided which voice the stuff is intended to
 * 		apply to, we don't exactly know what the endpoints of the
 *		stuff are going to be.  All we know is the "count" values the
 *		user asked for, which may or may not equal the positions of
 *		GRPSYLs in the voices.  So we look at voices 1 and 2 and take
 *		the worst (widest) case as the endpoints.  (This is called only
 *		when both of these voices exist.  We ignore any voice 3.)
 */

int
chkallspace(msbeg_p, stuff_p, vno)

struct MAINLL *msbeg_p;	/* staff at beginning of the stuff */
struct STUFF *stuff_p;	/* the STUFF */
int vno;		/* voice being tested for being all spaces */

{
	static RATIONAL tiny = {1, 4 * MAXBASICTIME};
	struct MAINLL *msend_p;		/* staff at end of the phrase */
	int timeden;			/* denom of time sig at end of stuff */
	RATIONAL begtime, endtime;	/* time into measures of begin & end */
	RATIONAL temptime;		/* temp var for storing time */


	/*
	 * Find what measure this stuff ends in.  Along the way, keep
	 * track of the time signature denominator, in case it changes.
	 */
	msend_p = getendstuff(msbeg_p, stuff_p, &timeden);

	/*
	 * If we hit a multirest, bail out, arbitrarily returning NO.  This
	 * stuff will be thrown away later anyway.
	 */
	if (msend_p == 0)
		return (NO);

	/*
	 * If the second voice doesn't exist (because vscheme changed),
	 * it's like all spaces in that voice.  So if we're asking about that
	 * voice, return YES.  If asking about the first voice, return NO.
	 */
	if (msend_p->u.staff_p->groups_p[1] == NULL) {
		return (vno == 1 ? YES : NO);
	}

	/*
	 * Find time values that are sure to contain the stuff.  Take the
	 * outermost values of the two voices.
	 */
	begtime = lefttime(stuff_p->start.count,
				msbeg_p->u.staff_p->groups_p[0], Score.timeden);
	temptime = lefttime(stuff_p->start.count,
				msbeg_p->u.staff_p->groups_p[1], Score.timeden);
	if (LT(temptime, begtime))
		begtime = temptime;
	endtime = righttime(stuff_p->end.count,
				msend_p->u.staff_p->groups_p[0], timeden);
	temptime = righttime(stuff_p->end.count,
				msend_p->u.staff_p->groups_p[1], timeden);
	if (GT(temptime, endtime))
		endtime = temptime;

	/*
	 * If the beginning and end are in the same measure and at the same
	 * time, this phrase would normally be thrown away later, but we need
	 * to deal with it because the case of a phrase from a grace to its
	 * main note.  It doesn't make sense to ask what a zero time contains,
	 * so to handle this, add a tiny time value to the end time.
	 */
	if (msbeg_p == msend_p && EQ(begtime, endtime))
		endtime = radd(endtime, tiny);

	return (allspace(vno, msbeg_p, begtime, msend_p, endtime));
}
\f
/*
 * Name:        allspace()
 *
 * Abstract:    Finds out if the given voice has space for the given time.
 *
 * Returns:     YES or NO
 *
 * Description: This function is a multi-measure version of hasspace(), and in
 *		fact works by calling hasspace() repeatedly.  It is given the
 *		linked list of groups for the voice in the first measure in
 *		question.  It checks whether the voice consists entirely of
 *		spaces from the duration point given for this first measure,
 *		until the endpoint, which may or may not be in the same measure.
 */

int
allspace(vno, msbeg_p, begtime, msend_p, endtime)

int vno;		/* voice number, numbering from voice 1 == 0 */
struct MAINLL *msbeg_p;	/* point at MLL (staff) where duration begins */
RATIONAL begtime;	/* time where duration begins */
struct MAINLL *msend_p;	/* point at MLL (staff) where duration ends */
RATIONAL endtime;	/* time where duration ends */

{
	struct MAINLL *mainll_p;		/* point along MLL */
	int staffno;


	/* if the time starts and ends in the same measure, let hasspace do it*/
	if (msbeg_p == msend_p) {
		return (hasspace(msbeg_p->u.staff_p->groups_p[vno],
				begtime, endtime));
	}

	/*
	 * If the first measure contains non-spaces, return NO.  Rather than
	 * keeping track of time signatures, we're going to pretend that we
	 * are in the longest possible time.  This relies on the fact that
	 * hasspace() in effect assumes that any phony time past the end of
	 * the actual measure is spaces.
	 */
	if (hasspace(msbeg_p->u.staff_p->groups_p[vno], begtime, Maxtime) == NO)
		return (NO);

	staffno = msbeg_p->u.staff_p->staffno;

	/* if any intermediate measures contain non-spaces, return NO */
	for (mainll_p = msbeg_p->next; mainll_p != 0 && mainll_p != msend_p;
			mainll_p = mainll_p->next) {

		/* skip everything but STAFFs for our staff number */
		if (mainll_p->str != S_STAFF ||
				mainll_p->u.staff_p->staffno != staffno)
			continue;

		if (hasspace(mainll_p->u.staff_p->groups_p[vno], Zero, Maxtime)
				== NO)
			return (NO);
	}

	if (mainll_p == 0)
		pfatal("bug found in allspace");

	/* the result is now determined by the last measure */
	return (hasspace(msend_p->u.staff_p->groups_p[vno], Zero, endtime));
}
\f
/*
 * Name:        getendstuff()
 *
 * Abstract:    Find staff and time signature denominator for end of a stuff.
 *
 * Returns:     pointer to MLL structure for staff containing end of stuff, or 0
 *
 * Description: This function finds the staff for the end of the given stuff.
 *		As a byproduct, it also finds the denominator of the time
 *		signature at that place.  If a multirest is encountered, a null
 *		pointer is returned, and timeden is not guaranteed.
 *		If the end of the piece is encountered, it returns the last
 *		staff.
 */

struct MAINLL *
getendstuff(mainll_p, stuff_p, timeden_p)

struct MAINLL *mainll_p;/* staff at beginning of stuff, gets changed to end */
struct STUFF *stuff_p;	/* the STUFF */
int *timeden_p;		/* gets set to denom of time sig at end of stuff */

{
	int staffno;		/* staff number where stuff is */
	struct MAINLL *mst_p;	/* point at the last staffno staff seen */
	int timenum;		/* remember the last time sig numerator */
	int b;			/* count bar lines */


	/* bail out if multirest */
	if (mainll_p->u.staff_p->groups_p[0]->basictime < -1)
		return (0);

	timenum = Score.timenum;	/* init to current time sig numerator*/
	*timeden_p = Score.timeden;	/* init to current time sig denom */

	/* if stuff doesn't cross any bar lines, we can return right away */
	if (stuff_p->end.bars == 0)
		return (mainll_p);

	mst_p = mainll_p;	/* remember last staff of this number */

	staffno = mainll_p->u.staff_p->staffno;

	/*
	 * Count past the right number of  bar lines, keeping the time sig
	 * denominator up to date.
	 */
	for (b = 0; b < stuff_p->end.bars; b++) {
		for (mainll_p = mainll_p->next;
				mainll_p != 0 && mainll_p->str != S_BAR;
				mainll_p = mainll_p->next) {

			if (mainll_p->str == S_SSV &&
				    mainll_p->u.ssv_p->used[TIME] == YES) {
				timenum = mainll_p->u.ssv_p->timenum;
				*timeden_p = mainll_p->u.ssv_p->timeden;
			}

			/* bail out if multirest encountered */
			if (mainll_p->str == S_STAFF && mainll_p->u.staff_p->
						groups_p[0]->basictime < -1)
				return (0);

			/* remember last staff of this number */
			if (mainll_p->str == S_STAFF && mainll_p->u.staff_p->
						staffno == staffno)
				mst_p = mainll_p;
		}
		/* if end of song, set to last bar line and return this staff*/
		if (mainll_p == 0) {
			stuff_p->end.count = timenum + 1;
			return (mst_p);
		}
	}

	/*
	 * mainll_p points at the bar line preceding the place where the stuff
	 * ends.  Continue forward to find the correct STAFF.
	 */
	for (mainll_p = mainll_p->next ;
			mainll_p != 0 && mainll_p->str != S_BAR;
			mainll_p = mainll_p->next) {

		if (mainll_p->str == S_SSV &&
				mainll_p->u.ssv_p->used[TIME] == YES)
			*timeden_p = mainll_p->u.ssv_p->timeden;

		if (mainll_p->str == S_STAFF &&
				mainll_p->u.staff_p->staffno == staffno)
			break;
	}

	/* if end of song, set to last bar line and return this staff */
	if (mainll_p == 0) {
		stuff_p->end.count = timenum + 1;
		return (mst_p);	/* hit end of song, return last meas */
	}
	if (mainll_p->str == S_BAR)
		pfatal("stuff crosses FEED where number of staffs changes");
	if (mainll_p->u.staff_p->groups_p[0]->basictime < -1)
		return (0);

	return (mainll_p);
}
\f
/*
 * Name:        lefttime()
 *
 * Abstract:    Find time value of the nongrace group left of the given count.
 *
 * Returns:     time value into measure
 *
 * Description: This function finds the nongrace GRPSYL in the given linked
 *		list that is at or left of the given count number.  If the
 *		count is less 1, we return time zero, even though technically
 *		time zero is to the right of the given count number.
 */

static RATIONAL
lefttime(count, firstgs_p, timeden)

double count;			/* which count of the measure */
struct GRPSYL *firstgs_p;	/* first GRPSYL of relevant voice in measure */
int timeden;			/* denominator of current time signature */

{
	RATIONAL reqtime;	/* time requested */
	RATIONAL tottime;	/* total time in measure so far */
	RATIONAL otottime;	/* old total time in measure so far */
	struct GRPSYL *gs_p;	/* point along group list */
	struct GRPSYL *ogs_p;	/* (old) point along group list */


	/* skip over any initial grace groups */
	if (firstgs_p->grpvalue == GV_ZERO)
		firstgs_p = nextnongrace(firstgs_p);

	/* if at or before the first count, have to use first group */
	if (count <= 1)
		return (Zero);

	/*
	 * Get requested time to the nearest half of the smallest fraction of a
	 * count that a user can specify, +1, in lowest terms.  The +1 is so
	 * that if the user isn't too accurate, we still land on the intended
	 * group.
	 */
	reqtime.n = 2 * MAXBASICTIME * (count - 1) + 0.5 + 1.0;
	reqtime.d = 2 * MAXBASICTIME * timeden;
	rred(&reqtime);

	/*
	 * Loop through this voice accumulating time values.  As soon as we
	 * equal or exceed the requested time value, return the previous
	 * group's time.
	 */
	otottime = tottime = Zero;
	for (ogs_p = firstgs_p, gs_p = nextnongrace(ogs_p); gs_p != 0;
				ogs_p = gs_p, gs_p = nextnongrace(gs_p)) {
		otottime = tottime;
		tottime = radd(tottime, ogs_p->fulltime);
		if (GE(tottime, reqtime))
			return (otottime);
	}

	/* requested time is after last group; return time of last group */
	return (otottime);
}
\f
/*
 * Name:        righttime()
 *
 * Abstract:    Find time value of the nongrace group right of the given count.
 *
 * Returns:     time value into measure
 *
 * Description: This function finds the nongrace GRPSYL in the given linked
 *		list that is at or right of the given count number.  If the
 *		count is greater then the rightmost group in the measure, we
 *		return the time up to the rightmost group, even though
 *		technically that time is to the left of the given count number.
 */

static RATIONAL
righttime(count, firstgs_p, timeden)

double count;			/* which count of the measure */
struct GRPSYL *firstgs_p;	/* first GRPSYL of relevant voice in measure */
int timeden;			/* denominator of current time signature */

{
	RATIONAL reqtime;	/* time requested */
	RATIONAL tottime;	/* total time in measure so far */
	struct GRPSYL *gs_p;	/* point along group list */
	struct GRPSYL *ogs_p;	/* (old) point along group list */


	/* skip over any initial grace groups */
	if (firstgs_p->grpvalue == GV_ZERO)
		firstgs_p = nextnongrace(firstgs_p);

	/* if at or before the first count, use first group */
	if (count <= 1)
		return (Zero);

	/*
	 * Get requested time to the nearest half of the smallest fraction of a
	 * count that a user can specify, -1, in lowest terms.  The -1 is so
	 * that if the user isn't too accurate, we still land on the intended
	 * group.
	 */
	reqtime.n = 2 * MAXBASICTIME * (count - 1) + 0.5 - 1.0;
	reqtime.d = 2 * MAXBASICTIME * timeden;
	rred(&reqtime);

	/*
	 * Loop through this voice accumulating time values.  As soon as we
	 * equal or exceed the requested time value, return that new time,
	 * although don't go beyond the last group's time value.
	 */
	tottime = Zero;
	for (ogs_p = firstgs_p, gs_p = nextnongrace(ogs_p); gs_p != 0;
				ogs_p = gs_p, gs_p = nextnongrace(gs_p)) {
		tottime = radd(tottime, ogs_p->fulltime);
		if (GE(tottime, reqtime))
			return (tottime);
	}

	/* requested time is after last group; but must return last group */
	return (tottime);
}
\f
/*
 * Name:        accdimen()
 *
 * Abstract:    Find the dimensions of a note's accidental.
 *
 * Returns:     void
 *
 * Description: This function finds the ascent, descent, and width of an
 *		accidental, and returns them through pointers.  If a pointer
 *		is null, it doesn't try to fill it in.  An accidental char of
 *		'\0' gives zero for each dimension.  The function takes into
 *		account whether the accidental is normal or small size, and
 *		whether it has parentheses around it.
 *		NOTE:  This function ignores staffscale.
 */

void
accdimen(note_p, ascent_p, descent_p, width_p)

struct NOTE *note_p;		/* the note whose accidental we're working on*/
float *ascent_p;		/* ascent, to be filled in */
float *descent_p;		/* descent, to be filled in */
float *width_p;			/* width, to be filled in */

{
	char accchar;		/* accidental character number */
	int size;		/* which size of character */
	float halfhigh;		/* half the height of a parenthesis */


	if (note_p->accidental == '\0') {
		if (ascent_p != 0) {
			*ascent_p  = 0.0;
		}
		if (descent_p != 0) {
			*descent_p = 0.0;
		}
		if (width_p != 0) {
			*width_p   = 0.0;
		}
		return;
	}

	/* find character name and size of this accidental */
	accchar = acc2char(note_p->accidental);
	size = (note_p->notesize == GS_NORMAL ? DFLT_SIZE : SMALLSIZE);

	/* get the requested dimensions of this accidental */
	if (ascent_p != 0) {
		*ascent_p  =  ascent(FONT_MUSIC, size, accchar);
	}
	if (descent_p != 0) {
		*descent_p = descent(FONT_MUSIC, size, accchar);
	}
	if (width_p != 0) {
		*width_p   =   width(FONT_MUSIC, size, accchar);
	}

	/*
	 * If it has parentheses around it, account for that.  Assume the left
	 * and right parens are symmetrical.  They will be centered on the line
	 * or space of the note.
	 */
	if (note_p->acc_has_paren) {
		if (width_p != 0) {
			*width_p += 2 * width(FONT_TR, size, '(');
		}
		halfhigh = height(FONT_TR, size, '(') / 2.0;
		if (ascent_p != 0 && halfhigh > *ascent_p) {
			*ascent_p = halfhigh;
		}
		if (descent_p != 0 && halfhigh > *descent_p) {
			*descent_p = halfhigh;
		}
	}
}
\f
/*
 * Name:        staffvertspace()
 *
 * Abstract:    Find the minimum amount of vertical space a staff should have.
 *
 * Returns:     the amount of vertical distance in inches
 *
 * Description: This function finds the minimum amount of vertical space that
 *		should be allocated for a staff, based on how many lines it has
 *		and whether it is tablature.  This does not take into account
 *		the extra space required by things sticking out farther; it's
 *		just for the staff itself, plus the extra white space required
 *		by staffs that have few lines.  The SSVs must be up to date.
 *		NOTE:  This function takes staffscale into account.
 */

double
staffvertspace(s)

int s;				/* staff number */

{
	float space;		/* the answer */


	/*
	 * Base space on number of steps between top and bottom lines.  But for
	 * tablature, it must be scaled because the lines are farther apart.
	 */
	space = (svpath(s, STAFFLINES)->stafflines - 1) * 2 * STEPSIZE;
	if (is_tab_staff(s))
		space *= TABRATIO;

	/* but don't ever return less than a (scaled) regular 5 line staff */
	return (svpath(s, STAFFSCALE)->staffscale * MAX(space, 8.0 * STEPSIZE));
}
\f
/*
 * Name:        halfstaffhi()
 *
 * Abstract:    Find half of the staff height.
 *
 * Returns:     half the staff height in inches
 *
 * Description: This function finds half of the staff's height, based on how
 *		many lines it has and whether it is tablature.  This does not
 *		take into account the extra space required by things sticking
 *		out farther; it's just for the staff itself, except that one
 *		line staffs are given a minimum instead of the zero you would
 *		expect.  The SSVs must be up to date.
 *		NOTE:  This function takes staffscale into account.
 */

double
halfstaffhi(s)

int s;				/* staff number */

{
	float space;		/* the answer */


	/*
	 * Base space on the number of steps between the top line and the
	 * middle of the staff.  But for tablature, it must be scaled because
	 * the lines are farther apart.
	 */
	space = (svpath(s, STAFFLINES)->stafflines - 1) * STEPSIZE;
	if (is_tab_staff(s))
		space *= TABRATIO;

	/* but don't ever return less than one (scaled) stepsize */
	return (MAX(space, STEPSIZE) * svpath(s, STAFFSCALE)->staffscale);
}
\f
/*
 * Name:        ratbend()
 *
 * Abstract:    Convert a bend distance to rational.
 *
 * Returns:     the rational number answer; 0/1 if null bend or no bend
 *
 * Description: This function, given a NOTE structure from a tab staff, returns
 *		the amount of the bend (if any) as a rational number.
 */

RATIONAL
ratbend(note_p)

struct NOTE *note_p;

{
	RATIONAL answer;


	if (note_p->BEND == 0)
		return (Zero);

	answer.d = BENDDEN(*note_p);
	answer.n = BENDNUM(*note_p) + BENDINT(*note_p) * answer.d;
	rred(&answer);

	return (answer);
}
\f
/*
 * Name:        notehorz()
 *
 * Abstract:    Find horizontal boundary of note and associated things.
 *
 * Returns:     the RE or RW
 *
 * Description: This function finds the horizontal boundary of a note,
 *		including accidentals, dots, etc., all the things that can be
 *		on the note.  The note's own RE and RW only tell about the note
 *		head itself.
 *		NOTE:  This function takes staffscale into account.  The SSVs
 *		need not be up to date, but Staffscale and Stdpad must be set.
 */

double
notehorz(gs_p, note_p, coord)

struct GRPSYL *gs_p;		/* the group the note is in */
struct NOTE *note_p;		/* point at the note */
int coord;			/* RE or RW */

{
	int s;			/* index into slurtolist */
	double h;		/* the answer */


	if (coord == RE) {
		if (note_p->note_has_paren == YES &&
					! is_tab_staff(gs_p->staffno)) {
			/*
			 * If there are parens around the note, start there.
			 * Note: this field does not apply on tab staff; it
			 * is only there for carrying over to tabnote staff.
			 * Tab staff uses FRET_HAS_PAREN, and this distance is
			 * included in the size of the "note" (fret) itself.
			 */
			h = note_p->erparen;
		} else  {
			/*
			 * If non-tablature and there are dots, start from the
			 * first dot.  Otherwise start from the note.
			 */
			if (is_tab_staff(gs_p->staffno) == NO &&
					gs_p->dots > 0) {
				h = gs_p->xdotr + 6 * Stdpad;
				if (gs_p->dots > 1) {
					h += (gs_p->dots - 1) * (2 * Stdpad +
					width(FONT_MUSIC, DFLT_SIZE, C_DOT));
				}
			} else {
				h = note_p->c[RE] + Stdpad;
			}
		}

		/*
		 * If this note has a slur to nowhere (and there can be at most
		 * one such), include its length.
		 */
		for (s = 0; s < note_p->nslurto; s++) {
			if (note_p->slurtolist[s].octave == OUT_UPWARD ||
			    note_p->slurtolist[s].octave == OUT_DOWNWARD) {
				h += Staffscale * (SLIDEXLEN + STDPAD);
				break;
			}
		}

	} else {	/* RW */

		if (note_p->note_has_paren == YES &&
					! is_tab_staff(gs_p->staffno)) {
			/* if parens around note, start there */
			h = note_p->wlparen;
		} else if (is_tab_staff(gs_p->staffno) == NO &&
				note_p->accidental != '\0') {
			/* if there's an accidental, start there */
			/* (this includes any parens around the accidental) */
			h = note_p->waccr;
		} else {
			/* the note head itself, with padding */
			h = note_p->c[RW] - Stdpad;
		}

		/*
		 * If this note has a slur from nowhere (and there can be at
		 * most one such), include its length.
		 */
		for (s = 0; s < note_p->nslurto; s++) {
			if (note_p->slurtolist[s].octave == IN_UPWARD ||
			    note_p->slurtolist[s].octave == IN_DOWNWARD) {
				h -= Staffscale * (SLIDEXLEN + STDPAD);
				break;
			}
		}
	}

	return (h);
}
\f
/*
 * Name:        allsmall()
 *
 * Abstract:    Do the given groups (of notes) consist entirely of small notes?
 *
 * Returns:     YES or NO
 *
 * Description: This function is given pointer to two GRPSYLs in a linked list.
 *		They may point to the same GRPSYL, or the second may point to a
 *		later GRPSYL in the list.  The function returns YES if all the
 *		notes in these GRPSYLs and any intervening GRPSYLs are small.
 *		Any GRPSYLs that are not for notes are ignored.
 */

int
allsmall(gs1_p, gs2_p)

struct GRPSYL *gs1_p;	/* starting group */
struct GRPSYL *gs2_p;	/* ending group (may be same as starting group) */

{
	struct GRPSYL *gs_p;	/* point along the list */
	int n;			/* index into notelist */


	/* check every group, and return NO if anything is normal size */
	for (gs_p = gs1_p; gs_p != gs2_p->next; gs_p = gs_p->next) {
		if (gs_p->grpcont == GC_NOTES && gs_p->grpsize == GS_NORMAL) {
			for (n = 0; n < gs_p->nnotes; n++) {
				if (gs_p->notelist[n].notesize == GS_NORMAL)
					return (NO);
			}
		}
	}

	return (YES);	/* everything must have been small */
}
\f
/*
 * Name:        finalstemadjust()
 *
 * Abstract:    Make final adjustments to the stem length.
 *
 * Returns:     void
 *
 * Description: This function makes final adjustments to the stem length that
 *		all the cases have in common.  Coming in, it is set to the
 *		stem length not counting the part between notes of a multinote
 *		group, and it doesn't account for the thickness of a beam.
 *		The SSVs must be up to date.
 *		NOTE:  This function takes staffscale into account.
 */

void
finalstemadjust(gs_p)

struct GRPSYL *gs_p;	/* group whose stemlen should be adjusted */

{
	float stepdiff;		/* distance between outer notes in steps */


	/* if it is negative (note on wrong side of beam), zap it */
	if (gs_p->stemlen < 0)
		gs_p->stemlen = 0;

	/* add distance between outer notes of group */
	stepdiff = gs_p->notelist[0].c[RY] -
			gs_p->notelist[ gs_p->nnotes - 1 ].c[RY];
	gs_p->stemlen += stepdiff;

	/*
	 * Decr the length by half the thickness of the beam, but don't let it
	 * get less than the distance between the outer notes of the group.
	 */
	gs_p->stemlen -= (W_WIDE * POINT / 2.0) *
			(gs_p->grpsize == GS_NORMAL ? 1.0 : SM_FACTOR) *
			svpath(gs_p->staffno, STAFFSCALE)->staffscale;
	gs_p->stemlen = MAX(gs_p->stemlen, stepdiff);
}
\f
/*
 * Name:        getstemshift()
 *
 * Abstract:    Find how far a stem is from the group's X coordinate.
 *
 * Returns:     the distance in inches
 *
 * Description: This function finds how far a group's stem is shifted
 *		horizontally from the group's X coordinate.
 *		NOTE:  This function takes staffscale into account.
 */

double
getstemshift(gs_p)

struct GRPSYL *gs_p;	/* group whose stemlen should be adjusted */

{
	/* return half the width of the widest note in the group */
	return (svpath(gs_p->staffno, STAFFSCALE)->staffscale *
			widest_head(gs_p) / 2.0);
}
\f
/*
 * Name:        vscheme_voices()
 *
 * Abstract:    Given a vscheme, how many voices are in it?
 *
 * Returns:     number of voices
 *
 * Description: This function is given one of the valid vschemes, and it
 *		returns the number of voices that vscheme allows.
 */

int
vscheme_voices(vscheme)

int vscheme;		/* the given vscheme */

{
	switch (vscheme) {
	case V_1:
		return (1);

	case V_2OPSTEM:
	case V_2FREESTEM:
		return (2);

	case V_3OPSTEM:
	case V_3FREESTEM:
		return (3);

	default:
		pfatal("invalid vscheme in vscheme_voices()");
	}

	return (0);
}
\f
/*
 * Name:        chmgrp2staffm()
 *
 * Abstract:    Given a chord and group, find the group's staff.
 *
 * Returns:     pointer to staff's MLL item
 *
 * Description: This function is given the MLL item for a chord, and a group
 *		connected to the chord.  It returns the MLL item for the staff
 *		that the group is connected to.  The group can belong to any of
 *		the staff's voices.
 */

struct MAINLL *
chmgrp2staffm(mll_p, gs_p)

struct MAINLL *mll_p;		/* starts as MLL for the chord */
struct GRPSYL *gs_p;		/* starts as GRPSYL the given group */

{
	/* find the first group in this measure */
	for ( ; gs_p->prev != 0; gs_p = gs_p->prev)
		;

	/* find the staff that it belongs to */
	for ( ; mll_p != 0; mll_p = mll_p->next) {

		if (mll_p->str == S_STAFF &&
		(mll_p->u.staff_p->groups_p[0] == gs_p ||
		 mll_p->u.staff_p->groups_p[1] == gs_p ||
		 mll_p->u.staff_p->groups_p[2] == gs_p))
			break;
	}
	if (mll_p == 0)
		pfatal("can't find staff in chmgrp2staffm");

	return (mll_p);
}
\f
/*
 * Name:        shiftgs()
 *
 * Abstract:    Shift a GRPSYL's relative horizontal coords.
 *
 * Returns:     void
 *
 * Description: This function is a GRPSYL and a shift amount.  It shifts the
 *		GRPSYL's relative horizontal coords by that amount, also
 *		including any preceding grace GRPSYLs.
 */

void
shiftgs(gs_p, shift)

struct GRPSYL *gs_p;		/* the main GRPSYL */
double shift;

{
	struct GRPSYL *ggs_p;		/* point at a grace group */


	gs_p->c[RX] += shift;
	gs_p->c[RW] += shift;
	gs_p->c[RE] += shift;

	/* apply shift to any preceding grace groups */
	for (ggs_p = gs_p->prev; ggs_p != 0 && ggs_p->grpvalue == GV_ZERO;
				ggs_p = ggs_p->prev) {
		ggs_p->c[RX] += shift;
		ggs_p->c[RW] += shift;
		ggs_p->c[RE] += shift;
	}
}
\f
/*
 * Name:        nearestline()
 *
 * Abstract:    Round a vertical offset to the nearest staff line.
 *
 * Returns:     the resulting offset
 *
 * Description: This function rounds its parameter off to a multiple of 2
 *		stepsizes.
 *		NOTE:  This function takes staffscale into account.  The SSVs
 *		need not be up to date, but Stepsize must be set.
 */

double
nearestline(offset)

double offset;			/* offset from center staff line */

{
	if (offset >= 0) {
		offset /= (2 * Stepsize);
		offset = (int)(offset + 0.5);
		offset *= (2 * Stepsize);
	} else {
		offset = -offset;
		offset /= (2 * Stepsize);
		offset = (int)(offset + 0.5);
		offset *= (2 * Stepsize);
		offset = -offset;
	}

	return (offset);
}
\f
/*
 * Name:        vfyoffset()
 *
 * Abstract:    Verify horizontal offsets are not in conflict.
 *
 * Returns:     void
 *
 * Description: This function prints a warning if the horizontal offsets of
 *		voices 1 and 2 are in conflict.  In that case it also zaps
 *		the bad offsets.
 */

void
vfyoffset(g_p)

struct GRPSYL *g_p[];		/* array of pointers to two groups */

{
	/* the only errors are cases where "+" and "-" are used */
	if (g_p[0]->ho_usage != HO_LEFT && g_p[0]->ho_usage != HO_RIGHT)
		return;

	/* can't both be "+" or both be "-" */
	if (g_p[0]->ho_usage == g_p[1]->ho_usage) {

		l_warning(
			g_p[1]->inputfile, g_p[1]->inputlineno,
			"voices 1 and 2 cannot both have horizontal offset '%c'; ignoring them",
			g_p[0]->ho_usage == HO_LEFT ? '-' :'+');

		g_p[0]->ho_usage = HO_NONE;
		g_p[1]->ho_usage = HO_NONE;
	}
}
\f
/*
 * Name:        adjslope()
 *
 * Abstract:    Adjust the slope of a beam.
 *
 * Returns:     the new slope
 *
 * Description: This function is given the slope of a beam as determined by
 *		linear regression.  It adjusts it according to the "beamslope"
 *		parameter.
 */

double
adjslope(g_p, oldslope, betweencsb)

struct GRPSYL *g_p;	/* pointer to GRPSYL to get staff and voice from */
double oldslope;	/* the given slope */
int betweencsb;		/* is this beam CSB and between the staffs? */

{
	struct SSV *ssv_p;	/* for getting fact and max */
	float beamfact;		/* to multiply by */
	float beammax;		/* max angle in degrees */
	float newangle;		/* the adjusted angle */


	/* find parameter values */
	ssv_p = vvpath(g_p->staffno, g_p->vno, BEAMSLOPE);
	beamfact = ssv_p->beamfact;
	beammax  = ssv_p->beammax;

	/*
	 * If cross staff beaming and the beam is between the staffs, we allow
	 * a somewhat bigger angle, because it may be necessary to avoid
	 * collisions.
	 */
	if (betweencsb == YES)
		beammax *= 1.4;

	/* new angle = old angle * beamfact */
	newangle = (atan(oldslope) * 180.0 / PI) * beamfact;

	/* force it to stay within the limit */
	if (newangle > beammax)
		newangle = beammax;
	else if (newangle < -beammax)
		newangle = -beammax;

	/* return as slope */
	return (tan(newangle * PI / 180.0));
}
\f
/*
 * Name:	curve_y_at_x()
 *
 * Abstract:	Given a curve and an X value, return the Y value there.
 *
 * Returns:	the Y value
 *
 * Description:	This function should only be called for curves where the X
 *		value of each point in the curve list is greater than the
 *		previous point's X value, although it's okay if the curve
 *		itself is not strictly increasing in X value all the time as
 *		you go from the start to the end.
 *
 *		If the X value given is less than the first point's, it returns
 *		the Y of the first point.  If the X value is greater than the
 *		last point's, it returns the Y of the last point.  Otherwise,
 *		it returns a Y value of the curve at that X value.  I say "a"
 *		Y value, because if the curve isn't strictly increasing, there
 *		can be multiple answers, and it just returns one of them.
 *
 *		The function assumes that the curve points will be connected by
 *		cubic curves, according to the algorithm in calccurve() and
 *		findcontrol().
 */

double
curve_y_at_x(first_p, x)

struct CRVLIST *first_p;	/* left endpoint of curve */
double x;			/* X coord at which we need Y */

{
	float y;		/* the answer */
	float a, b, c;		/* coefficients for a cubic */
	struct CRVLIST *left_p, *right_p; /* endpoints of a cubic segment */
	float rotangle;		/* rotate new system to get old (in radians) */
	float tranx, trany;	/* a point translated to another coord system */
	float pointx, pointy;	/* trans & rotated in another coord system */
	float lineslope, intercept;	/* of a line through the given x */
	float cos_rotangle, sin_rotangle;	/* for saving these values */
	float deltax, deltay;	/* of endpoints of segment between 2 points */
	float len;		/* length of segment between 2 points */


	/*
	 * If the first point of the curve is at or already beyond the given x,
	 * return the first point's y.
	 */
	if (first_p->x >= x) {
		return (first_p->y);
	}
	right_p = 0;	/* for lint */
	for (left_p = first_p; left_p->next != 0; left_p = left_p->next) {
		right_p = left_p->next;
		/* if x is right at this point, use this point's y */
		if (right_p->x == x) {
			return (right_p->y);
		}
		/* if x is within this interval, break out */
		if (left_p->x < x && x < right_p->x) {
			break;
		}
	}
	/* if this happens, x is beyond the last point, so use last point's y */
	if (left_p->next == 0) {
		return (left_p->y);
	}

	/*
	 * The given x is between the x coords of two of the points in the
	 * curvelist.  So we need to find the cubic arc that calccurve() and
	 * findcontrol() would use, if this curve is going to be used.  The
	 * cubic arc is determined in a translated/rotated coordinate system
	 * where left_p is (0,0) and right_p is on the positive X axix.
	 * rotangle is the angle from the segment between left_p and right_p
	 * to the real X axis.  The cubic, in the translated/rotated system, is
	 * y = a x^3 + b x^2 + c x.  It turns out that the constant term is
	 * always zero.
	 */
	rotangle = findcubic(left_p, right_p, &a, &b, &c);

	/*
	 * If left_p->y == right_p->y, rotangle is zero, meaning no rotation was
	 * necessary, only translation.  In that case we can simply plug into
	 * the cubic we found, adjusting for the translation.  A fudge factor is
	 * needed so that we don't take the tangent of almost 90 degrees below.
	 */
	if (fabs(rotangle) < 0.001) {
		pointx = x - left_p->x;
		pointy = ((a * pointx + b) * pointx + c) * pointx;
		y = pointy + left_p->y;
		return (y);
	}

	/*
	 * Rotation was necessary.  In the original coord system, picture a
	 * vertical line at the given x value.  It intersects the cubic,
	 * possibly in more than one place.  We want the y value at the
	 * intersection.  In the translated/rotated system, this line has a
	 * slope as determine below.
	 */
	if (rotangle < 0.0) {
		lineslope = tan(PI / 2.0 + rotangle);
	} else {
		lineslope = tan(-PI / 2.0 + rotangle);
	}

	/*
	 * In the real coord system, the vertical line hits (x, 0).  Find this
	 * point in the translated/rotated system.
	 */
	/* first translate */
	tranx = x - left_p->x;
	trany = -left_p->y;
	/* then rotate */
	cos_rotangle = cos(rotangle);	/* save to avoid recalculation */
	sin_rotangle = sin(rotangle);
	pointx = tranx * cos_rotangle - trany * sin_rotangle;
	pointy = trany * cos_rotangle + tranx * sin_rotangle;

	/* find Y intercept in the translated/rotated system */
	intercept = pointy - lineslope * pointx;

	/*
	 * Now, in the tran/rot coord system, we need to find the intersection
	 * of this line
	 *	y  =  lineslope * x  +  intercept
	 * and the cubic
	 *	y  =  a * x^3  +  b * x^2  +  c * x
	 * Setting the two values of y equal, we get
	 *	lineslope * x  +  intercept  =  a * x^3  +  b * x^2  +  c * x
	 * or
	 *	a * x^3  +  b * x^2  + (c - lineslope) * x  -  intercept  =  0
	 */
	/* find intersection point in the tran/rot coord system */
	deltax = right_p->x - left_p->x;
	deltay = right_p->y - left_p->y;
	len = sqrt(SQUARED(deltax) + SQUARED(deltay));
	pointx = solvecubic(a, b, c-lineslope, -intercept,
			0.0, len, Stdpad / 2.0);
	pointy = lineslope * pointx + intercept;

	/* rotate backwards, getting Y value */
	trany = pointy * cos_rotangle - pointx * sin_rotangle;

	/* translate back to the original coord system */
	y = trany + left_p->y;

	return (y);
}
\f
/*
 * Name:	findcubic()
 *
 * Abstract:	Given neighboring curve points, find cubic and rotation angle.
 *
 * Returns:	angle from new coord system's X axis to old system's (radians)
 *
 * Description:	This function uses a new coordinate system, where the left
 *		curve point is (0, 0), and the right curve point is on the
 *		positive X axis.  It finds the coefficients for the cubic arc
 *		that will be put through these points.  It returns the angle
 *		that the old coord system needs to be rotated by to get to
 *		the new system.
 */

double
findcubic(left_p, right_p, a_p, b_p, c_p)

struct CRVLIST *left_p;		/* left endpoint of cubic arc */
struct CRVLIST *right_p;	/* right endpoint of cubic arc */
float *a_p, *b_p, *c_p;		/* return the answers here, the coefficients */

{
	double langle;		/* half angle from prev segment to this one */
	double rangle;		/* half angle from this segment to next one */
	float deltax, deltay;	/* for this segment */
	float len;		/* of this segment */
	float lslope, rslope;	/* slope of tangent line at left & right point*/
	float thisang, prevang, nextang; /* angle of segment with horizontal */


	langle = rangle = 0.0;	/* for lint */

	/* get angle of this segment */
	thisang = atan((right_p->y - left_p->y) / (right_p->x - left_p->x));

	if (left_p->prev != 0) {
		/* there is a previous segment; find its angle */
		prevang = atan((left_p->y - left_p->prev->y) /
			       (left_p->x - left_p->prev->x));
		/* half the change in angle */
		langle = (thisang - prevang) / 2.0;
	}
	if (right_p->next != 0) {
		/* there is a next segment; find its angle */
		nextang = atan((right_p->next->y - right_p->y) /
			       (right_p->next->x - right_p->x));
		/* half the change in angle */
		rangle = (nextang - thisang) / 2.0;
	}
	if (left_p->prev == 0) {
		/* no previous segment; use same angle as on the right */
		langle = rangle;
	}
	if (right_p->next == 0) {
		/* no next segment; use same angle as on the left */
		rangle = langle;
	}

	/* get lengths of this segment */
	deltax = right_p->x - left_p->x;
	deltay = right_p->y - left_p->y;
	len = sqrt(SQUARED(deltax) + SQUARED(deltay));

	/*
	 * Rotate and translate the axes so that the starting point (left_p)
	 * is at the origin, and the ending point (right_p) is on the positive
	 * x axis.  Their coords are (0, 0) and (len, 0).  We are going to
	 * find a cubic equation that intersects the endpoints, and has the
	 * required slope at those points.  The equation is
	 *	y  =  a x^3  +  b x^2  +  c x  +  d
	 * so the slope is
	 *	y' =  3 a x^2  +  2 b x  +  c
	 * By plugging the two points into these, you get 4 equations in the 4
	 * unknowns a, b, c, d.
	 */
	/* find the slope of the tangent lines at the first & second points */
	lslope = -tan(langle);
	rslope = tan(rangle);

	/* set values of a, b, c (d turns out to be always 0) */
	*a_p = (lslope + rslope) / SQUARED(len);
	*b_p = (-2.0 * lslope - rslope) / len;
	*c_p = lslope;

	return (-thisang);
}
\f
/*
 * Name:	solvecubic()
 *
 * Abstract:	Find a solution to a cubic equation within a given interval.
 *
 * Returns:	the solution
 *
 * Description:	This function is given the coefficients of a cubic equation and
 *		the boundaries of an interval.  The function must be positive
 *		at one end and negative at the other (or zero is okay at
 *		either).  It uses the "modified regula falsi" algorithm to find
 *		a solution, meaning that it keeps narrowing down the interval.
 *		It stops when the inverval size <= the threshhold given.  But
 *		in case something goes wrong, it also stops after 20 loops.
 */

double
solvecubic(a, b, c, d, lo, hi, thresh)

double a, b, c, d;	/* in equation   a x^3 + b x^2 + c x + d = 0  */
double lo, hi;		/* low and high boundaries of interval to look in */
double thresh;		/* how close must result be to the true answer */

#define FUNC(x) (((a * x + b) * x + c) * x + d)
{
	float lovert, hivert;	/* y values */
	float mid, midvert;	/* a point in the middle and its y value */
	float oldmidvert;	/* midvert in previous loop */
	int n;


	lovert = FUNC(lo);
	hivert = FUNC(hi);

	/*
	 * If the function is positive at both endpoints or negative at both
	 * endpoints, it was called incorrectly.  But we're going to allow for
	 * a small violation of this due to presumed roundoff error.  If one
	 * endpoint if "very near" zero, we'll pretend it was zero and return
	 * it as the solution.
	 */
	if (lovert * hivert > 0.0) {
		if (fabs(lovert) < thresh)
			return (lo);
		if (fabs(hivert) < thresh)
			return (hi);
		pfatal("solvecubic was called with an invalid interval");
	}

	mid = lo;
	midvert = lovert;

	for (n = 0; n < 20 && hi - lo > thresh; n++) {
		oldmidvert = midvert;

		/*
		 * Find a point somewhere in the interval by passing a segment
		 * through (lo, lovert) and (hi, hivert) and seeing where it
		 * hits the X axis.
		 */
		mid = (lovert * hi - hivert * lo) / (lovert - hivert);
		midvert = FUNC(mid);

		/*
		 * Set either the hi or the lo equal to the mid.  If the value
		 * at mid is the same sign as the previous one, divide the
		 * vert value by 2, so we can eventually get the segment to
		 * hit on the other side.
		 */
		if ((lovert > 0.0) != (midvert > 0.0)) {
			hi = mid;
			hivert = midvert;
			if ((midvert > 0.0) == (oldmidvert > 0.0)) {
				lovert /= 2.0;
			}
		} else {
			lo = mid;
			lovert = midvert;
			if ((midvert > 0.0) == (oldmidvert > 0.0)) {
				hivert /= 2.0;
			}
		}
	}

	return (mid);
}
\f
/*
 * Name:        css_affects_stemtip()
 *
 * Abstract:    Do CSS notes (if any) affect the position of the stem's tip?
 *
 * Returns:     YES or NO
 *
 * Description: This function is given a pointer to a GRPSYL.  It must be a
 *		note group, but can be grace or nongrace.  It may be a member
 *		of a beamed set, or not a member of a beamed set.  It decides
 *		whether the position of the tip of the stem (or where the stem
 *		would be for a non-stemmed note) is affected by CSS notes.
 */

int
css_affects_stemtip(gs_p)

struct GRPSYL *gs_p;	/* starts at the given group */

{
	/*
	 * For the single (unbeamed) group case, the position of the tip of the
	 * stem is affected if either the CSS notes are on the stem side, or if
	 * all the notes are CSS.
	 */
	if (gs_p->beamloc == NOITEM) {
		return (STEMSIDE_CSS(gs_p) || NNN(gs_p) == 0 ? YES : NO);
	}

	/* CSB is never CSS */
	if (gs_p->beamto != CS_SAME) {
		return (NO);
	}

	/*
	 * For the beamed case, either all or none of the groups can have CSS
	 * notes on the stem side, if there are any other-staff notes at all
	 * in the group.  This is because all the groups' stems go
	 * the same direction, and we don't allow the beaming together of
	 * groups where some have stemto == CS_ABOVE and others have CS_BELOW.
	 * Theoretically a group with all CSS notes could affect the position
	 * of the beam regardless of whether its CSS notes are stemside or not;
	 * but we will pretend that it can't.  We'll fake things out in
	 * setbeam().  This way, we can handle beaming and set the beam
	 * position and good group boundaries on the beamside during the
	 * CSSpss==NO pass.  Then the placement of "stuff" on that side will
	 * be better.
	 */
	/* if we're not at the start of the beamed set, go back to there */
	while (gs_p->beamloc != STARTITEM) {
		gs_p = prevsimilar(gs_p);
	}
	/* check each member to see if any have stemside CSS */
	while (gs_p != 0) {
		if (STEMSIDE_CSS(gs_p)) {
			return (YES);
		}
		if (gs_p->beamloc == ENDITEM) {
			break;
		}
		gs_p = nextsimilar(gs_p);
	}
	return (NO);
}
\f
/*
 * Name:        css_affects_tieslurbend()
 *
 * Abstract:    Do CSS notes (if any) affect the position of this tie/slur/bend?
 *
 * Returns:     YES or NO
 *
 * Description: This function decides whether the given tie, slur, or bend is
 *		affected by CSS notes in any of the groups it covers.
 */

int
css_affects_tieslurbend(stuff_p, mll_p)

struct STUFF *stuff_p;	/* the tie, slur, or bend */
struct MAINLL *mll_p;	/* MLL item where this tie/slur/bend starts */

{
	struct GRPSYL *sg_p;	/* starting group of the tie/slur/bend */
	struct GRPSYL *eg_p;	/* starting group of the tie/slur/bend */
	struct NOTE *snote_p;	/* starting note of the tie/slur/bend */
	struct NOTE *enote_p;	/* ending note of the tie/slur/bend */
	int idx;		/* index of note in the group */


	/* if not cross staff stemming, don't waste time checking */
	if (CSSused == NO) {
		return (NO);
	}

	/* second half (after crossing scorefeed); was handled by first half */
	if (stuff_p->carryin == YES) {
		return (NO);
	}

	sg_p = stuff_p->beggrp_p;
	snote_p = stuff_p->begnote_p;

	/* find the index of the note in the group */
	for (idx = 0; idx < sg_p->nnotes; idx++) {
		if (&sg_p->notelist[idx] == snote_p) {
			break;
		}
	}
	if (idx == sg_p->nnotes) {
		pfatal("can't find tied/slurred/bent note in group");
	}

	/* if this starting note is CSS, return YES */
	if (IS_CSS_NOTE(sg_p, idx)) {
		return (YES);
	}

	/*
	 * Find the end note of the tie/slur/bend.  If none, we don't care
	 * about the end note.
	 */
	eg_p = nextgrpsyl(sg_p, &mll_p);
	if (eg_p == 0) {
		return (NO);
	}

	/* find the note tied/slurred/bent to */
	if (stuff_p->curveno == -1) {	/* this is a tie */
		enote_p = find_matching_note(eg_p, snote_p->letter,
				snote_p->octave, (char *)0);
	} else {			/* this is a slur or bend */
		enote_p = find_matching_note(eg_p,
				snote_p->slurtolist[stuff_p->curveno].letter,
				snote_p->slurtolist[stuff_p->curveno].octave,
				(char *)0);
	}

	if (enote_p == 0) {
		return (NO);
	}

	/* find the index of the note in the group */
	for (idx = 0; idx < eg_p->nnotes; idx++) {
		if (&eg_p->notelist[idx] == enote_p) {
			break;
		}
	}
	if (idx == eg_p->nnotes) {
		pfatal("can't find tied/slurred/bent-to note in group");
	}

	/* if this ending note is CSS, return YES */
	if (IS_CSS_NOTE(eg_p, idx)) {
		return (YES);
	}

	return (NO);
}
/*
 * Name:        css_affects_phrase()
 *
 * Abstract:    Do CSS notes (if any) affect the position of this phrase mark?
 *
 * Returns:     YES or NO
 *
 * Description: This function decides whether the given phrase mark is
 *		affected by CSS notes in any of the groups it covers.
 */

int
css_affects_phrase(stuff_p, mll_p)

struct STUFF *stuff_p;	/* the phrase */
struct MAINLL *mll_p;	/* for the group at start of phrase */

{
	struct GRPSYL *gs_p;	/* point at end group covered by phrase */
	int place;		/* PL_ABOVE or PL_BELOW */
	int staffno;		/* staff number */
	int vidx;		/* voice index */


	place = stuff_p->place;
	gs_p = stuff_p->beggrp_p;
	staffno = gs_p->staffno;
	vidx = gs_p->vno - 1;
	
	/* loop once for each group covered by the phrase */
	while (gs_p != 0) {
		/* return YES right away if we find an affected group */
		switch (gs_p->stemto) {
		case CS_SAME:
			break;
		case CS_ABOVE:
			if (place == PL_ABOVE || NNN(gs_p) == 0) {
				return (YES);
			}
			break;
		case CS_BELOW:
			if (place == PL_BELOW || NNN(gs_p) == 0) {
				return (YES);
			}
			break;
		}

		/* if we've seen the last group, we are done */
		if (gs_p == stuff_p->endgrp_p) {
			break;
		}

		/* find the next note group in this voice */
		do {
			gs_p = gs_p->next;
		} while (gs_p != 0 && gs_p->grpcont != GC_NOTES);

		/* if we hit the end of the measure, look for next measure */
		if (gs_p == 0) {
			/* find the bar line */
			while (mll_p != 0 && mll_p->str != S_BAR) {
				mll_p = mll_p->next;
			}
			/* find the matching staff in the next measure */
			while (mll_p != 0 && ! (mll_p->str == S_STAFF &&
					mll_p->u.staff_p->staffno == staffno)) {
				mll_p = mll_p->next;
			}
			/* defensive check, should not happen */
			if (mll_p == 0) {
				break;
			}
			/* point at the first group in new measure */
			gs_p = mll_p->u.staff_p->groups_p[vidx];
		}
	}

	return (NO);
}
\f
/*
 * Name:        nextsimilar()
 *
 * Abstract:    Return next group in a GRPSYL list that is "like" the current.
 *
 * Returns:     pointer to GRPSYL of next desired group, 0 if none
 *
 * Description: This function loop down the GRPSYL linked list from the given
 *		starting point.  It returns the next GRPSYL in the list that has
 *		the same grpcont and grpvalue as the given one, or 0 if none.
 */

struct GRPSYL *
nextsimilar(gs_p)

struct GRPSYL *gs_p;	/* current group */

{
	int curvalue;
	int curcont;

	curvalue = gs_p->grpvalue;
	curcont = gs_p->grpcont;
	gs_p = gs_p->next;
	while (gs_p != 0 &&
	      (gs_p->grpvalue != curvalue || gs_p->grpcont != curcont)) {
		gs_p = gs_p->next;
	}
	return (gs_p);
}
\f
/*
 * Name:        prevsimilar()
 *
 * Abstract:    Return prev group in a GRPSYL list that is "like" the current.
 *
 * Returns:     pointer to GRPSYL of previous desired group, 0 if none
 *
 * Description: This function loops down the GRPSYL linked list from the given
 *		starting point.  It returns the prev GRPSYL in the list that has
 *		the same grpcont and grpvalue as the given one, or 0 if none.
 */

struct GRPSYL *
prevsimilar(gs_p)

struct GRPSYL *gs_p;	/* current group */

{
	int curvalue;
	int curcont;

	curvalue = gs_p->grpvalue;
	curcont = gs_p->grpcont;
	gs_p = gs_p->prev;
	while (gs_p != 0 &&
	      (gs_p->grpvalue != curvalue || gs_p->grpcont != curcont)) {
		gs_p = gs_p->prev;
	}
	return (gs_p);
}
\f
/*
 * Name:        gs2ch()
 *
 * Abstract:    Given a GRPSYL and its staff's MLL, find chord for that time.
 *
 * Returns:     pointer to CHORD structure
 *
 * Description: This function is given a GRPSYL and the MLL structure for the
 *		GRPSYL's staff.  It finds the CHORD structure that heads the
 *		list of GRPSYLs occurring at that time in that measure.  Note
 *		that if the given GRPSYL is grace, it won't actually occur in
 *		that linked list of GRPSYLs; but in that case the following
 *		non-grace GRPSYL will.
 */

struct CHORD *
gs2ch(mll_p, gs_p)

struct MAINLL *mll_p;	/* the MLL for the given GRPSYL */
struct GRPSYL *gs_p;	/* the given GRPSYL */

{
	struct CHORD *ch_p;		/* loop through chords */
	struct GRPSYL *gs2_p;		/* point along a GRPSYL list */
	RATIONAL time;			/* time offset where our group is */


	/* find chord headcell for this measure */
	while (mll_p != 0 && mll_p->str == S_STAFF) {
		mll_p = mll_p->prev;
	}
	if (mll_p == 0 || mll_p->str != S_CHHEAD) {
		pfatal("missing chord head cell in gs2ch");
	}

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

	/*
	 * Find the chord that contains our group (or, if we are a grace group,
	 * the following normal group).
	 */
	for (ch_p = mll_p->u.chhead_p->ch_p;
			ch_p != 0 && NE(ch_p->starttime, time);
			ch_p = ch_p->ch_p) {
		;
	}
	if (ch_p == 0) {
		pfatal("can't find chord in gs2ch");
	}

	return (ch_p);
}
\f
/*
 * Name:        stemroom()
 *
 * Abstract:    Try to find how much room a "wrong way" stem needs.
 *
 * Returns:     The room needed, measured in stepsizes.
 *
 * Description: This function is given a nongrace note group whose stem has
 *		been forced the wrong way (down for the top group or up for the
 *		bottom group) despite the other voice being nonspace.  It tries
 *		to find how long the stem will be so that we can decide whether
 *		the groups need to be horizontally offset.  It works well for
 *		nonbeamed groups, but for beamed groups it can only guess.  It
 *		is to be used in places where we need to know the stem length
 *		(to the extent possible) even though beamstem.c hasn't run yet.
 *
 *		WARNING:  This code is similar to the nongrace section of
 *		proclist() in beamstem.c.  If you change one, you probably
 *		will need to change the other.
 */

double
stemroom(gs_p)

struct GRPSYL *gs_p;		/* the group in question */

{
	float room;		/* the answer, in stepsizes */
	int bf;			/* number of beams/flags */


	/*
	 * If user specified stem length, use that.
	 */
	if (IS_STEMLEN_KNOWN(gs_p->stemlen)) {
		return (gs_p->stemlen / STEPSIZE);
	}

	/*
	 * If this group is part of a beamed set, there is no way to know how
	 * long the stem will be, since the beaming hasn't been done yet, and
	 * can't be done until all horizontal placement has been done.  So
	 * return the default stem length and hope for the best.
	 */
	if (gs_p->beamloc != NOITEM) {
		return (DEFSTEMLEN);
	}

	/*
	 * 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) {
		/* no (pseudo)stem */
		return (0.0);
	}

	/* find default stemlen for this voice */
	room = vvpath(gs_p->staffno, gs_p->vno, STEMLEN)->stemlen;
	if (room == 0.0) {
		return (0.0);
	}

	/* if small notes, reduce this default */
	room *= (allsmall(gs_p, gs_p) == YES ? SM_STEMFACTOR : 1.0);

	/* 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) {
		room += (bf - 2) * FLAGSEP / STEPSIZE;
	}

	/*
	 * If the note may have flag(s), is 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) {
				room += 1.0;
			} else {
				room += 2.0;
			}
		} else {
			/* note is on a space */
			if (gs_p->basictime > 8) {
				room += 1.0;
			}
		}
	}

	return (room);
}