#include <ncbi.h>
#include <gishlib.h>
#include "blastapp.h"
/* ckoverlap - remove overlapping HSPs */
/*
   ckoverlap discards HSPs that overlap.  An HSP is said to "contain"
another, if one (or both) of the segments in the segment pair spans the
entirety of the corresponding segment in the other HSP.

The overlap algorithm ensures that two HSPs will never appear together
in the output if one of them "contains" the other.  An old HSP may be
replaced by a new HSP, if either HSP contains the other AND:  (a) the
new HSP has a higher score; or (b) the new HSP has the same score but
is shorter.  Conversely, the new HSP will be discarded, if either HSP
contains the other AND:  (a) the old HSP has a higher score; or (b)
the old HSP has the same score but is shorter.

In any case, a newly found HSP is never used to discard an old HSP until
it is known that the new HSP should not itself be discarded due to some
other old HSP.

At present, the pruning of HSPs occurs as the HSPs are found, rather than
accumulating all HSPs until the end of the search and trying to optimize
the process in another way.
*/
void
ckoverlap(MPC hp)
	MPDEF
	register HSPPtr	hp;
{
	register HSPPtr	hp2, firstov = NULL;
	register HSPPtr	hpnext, hpprev;
	register int	ovcnt;

	/* Make sure the new HSP is not excluded by an HSP already in the list */
	for (hp2 = MPPTR curhl.hp, firstov = NULL; hp2 != NULL; hp2 = hp2->next) {
		if ((*ovlap)(hp, hp2) == TRUE) {
			if (hp->score > hp2->score) {
				if (firstov == NULL)
					firstov = hp2;
				continue;
			}
			/* There is already an equal or better HSP in the list */
			++MPPTR overcnt;
			return;
		}
	}

	if (firstov == NULL) {
		/* No overlaps at all -- save the new HSP and return */
		(*hsp_save)(MPC hp);
		return;
	}

	/* Save the new HSP in existing storage, overwriting an overlapping HSP */
	hp->next = firstov->next; /* prepare to copy back this important value */
	*firstov = *hp;

	/* Discard any HSPs overlapped or contained by the new one */
	for (ovcnt = 0, hpprev = firstov, hp2 = firstov->next; hp2 != NULL;
				hp2 = hpnext) {
		hpnext = hp2->next;
		if ((*ovlap)(hp, hp2) == TRUE) {
			++ovcnt;
			hpprev->next = hpnext;
			HSPPoolReturn(MPPTR poolp, hp2);
			continue;
		}
		hpprev = hp2;
	}
	MPPTR curhl.hspcnt -= ovcnt;
	MPPTR overcnt += ovcnt+1;
}


/* hsp_save_default -- default routine for saving an HSP */
void
hsp_save_default(MPC hp)
	MPDEF
	HSPPtr	hp;
{
	HSPPtr	hpnew;

	if (MPPTR curhl.hspcnt >= maxHSP)
		bfatal(ERR_HSPCNT, "Too many matches against one sequence; raise HSP_MAX and recompile the program, try a shorter query sequence, or raise the cutoff score.");

	hpnew = HSPPoolGet(MPPTR poolp);
	*hpnew = *hp;
	hpnew->next = MPPTR curhl.hp;
	MPPTR curhl.hp = hpnew;
	MPPTR curhl.hspcnt++;
}