File: jzcoll.c

package info (click to toggle)
ncbi-tools6 6.0.2-1.1
links: PTS
area: main
in suites: potato
size: 33,932 kB
ctags: 50,922
sloc: ansic: 590,557; sh: 716; makefile: 375; csh: 234; lisp: 81; cpp: 57; perl: 48
file content (4050 lines) | stat: -rw-r--r-- 94,385 bytes
#include <jzcoll.h>



NLM_EXTERN ValNodePtr clean_annot_for_anp(ValNodePtr PNTR head)
{
	ValNodePtr prev, next, anp_list;
	
	prev = NULL;
	anp_list = *head;
	while(anp_list)
	{
		next = anp_list->next;
		if(anp_list->choice == OBJ_SEQANNOT)
		{
			if(prev == NULL)
				*head = next;
			else
				prev->next = next;
			anp_list->next = NULL;
			FreeAlignNode(anp_list);
		}
		else
			prev = anp_list;
		anp_list = next;
	}
	
	return (*head);
}



/***********************************************************************
*
*	FreeFeatureList(list)
*	free a list of FeatNode
*
***********************************************************************/
NLM_EXTERN ValNodePtr FreeFeatureList  (ValNodePtr list)
{
	FeatNodePtr  fnp;
	ValNodePtr   next;

 	while (list != NULL) 
 	{
		next = list->next;
		fnp = list->data.ptrvalue;
		if (fnp != NULL) 
		{
			ValNodeFreeData (fnp->interval);
			MemFree (fnp->label);
			MemFree(fnp->pos_label);
			if(fnp->supress_node != NULL)	/*hidden features*/
				FreeFeatureList(fnp->supress_node);
			MemFree (fnp);
		}
		MemFree (list);

		list = next;
	}
	return NULL;
}

/*********************************************************************
*
*	extract_node_list(head, itemType, entityID, feattype, subtype, 
*	label_type)
*	extract a list of featnode from head which will have the 
*	selected itemType, entityID, feattye, subtype, label_type. 
*	set values to 0 if it is not considered in the selection
*
*********************************************************************/
static Boolean do_collect(ValNodePtr vnp, Uint1 itemType, Uint2 entityID, Uint1 feattype, Uint1 label_type)
{
	Boolean is_num;		/*is the gene mark a number*/
	FeatNodePtr fnp;

	if(vnp->choice != itemType)
		return FALSE;

	fnp = (FeatNodePtr)(vnp->data.ptrvalue);
	if(fnp == NULL)
		return FALSE;

	if(entityID !=0)
		if(fnp->entityID !=entityID)
			return FALSE;


	if(itemType == OBJ_SEQFEAT)
	{
		if((feattype == 0) || (fnp->feattype == feattype))
		{
			if(label_type == ALL_LABEL)
				return TRUE;
			is_num = IS_NUM_GENE(fnp->label);
			if(label_type == STR_LABEL)
				return (is_num == FALSE);
			if(label_type == NUM_LABEL)
				return (is_num == TRUE);
		}
		else
			return FALSE;
	}

	return TRUE;
	
}



NLM_EXTERN ValNodePtr extract_node_list(ValNodePtr PNTR head, Uint1 itemType, Uint2 entityID, Uint1 feattype, Uint1 label_type)
{
	ValNodePtr vnp, prev, list, next;


	list = NULL;
	prev = NULL;
	vnp = *head;
	while(vnp)
	{
		next = vnp->next;
		if(do_collect(vnp, itemType, entityID, feattype, label_type))
		{
			if(prev == NULL)
				*head = vnp->next;
			else
				prev->next = vnp->next;
			vnp->next = NULL;
			ValNodeLink(&list, vnp);
		}
		else
			prev = vnp;
		vnp = next;
	}
	
	return list;

}

NLM_EXTERN ValNodePtr extract_lollipop_feature(ValNodePtr PNTR head, Int4 scale, BoolPtr lolli_feature)
{
	ValNodePtr vnp, prev, list, next;
	FeatNodePtr fnp;
	Boolean extract = FALSE;


	list = NULL;
	prev = NULL;
	vnp = *head;
	while(vnp)
	{
		next = vnp->next;
		extract = FALSE;
		if(vnp->choice == OBJ_SEQFEAT)
		{
			fnp = vnp->data.ptrvalue;
			if((fnp->extremes.right - fnp->extremes.left +1) <= scale)
				extract = TRUE;
			else if(lolli_feature != NULL)
				extract = lolli_feature[fnp->feattype];
		}
		if(extract)
		{
			if(prev == NULL)
				*head = vnp->next;
			else
				prev->next = vnp->next;
			vnp->next = NULL;
			ValNodeLink(&list, vnp);
		}
		else
			prev = vnp;
		vnp = next;
	}
	
	return list;

}

/*deside whether the alignment is of different molecules */
NLM_EXTERN Uint1 get_alignment_type(AnnotInfoPtr annot_info)
{
	if(annot_info->blast_type == ALIGN_BLASTX)
		return ALIGN_DNA_TO_PROT;
	if(annot_info->blast_type == ALIGN_TBLASTN)
		return ALIGN_PROT_TO_DNA;
	if(annot_info->blast_type == ALIGN_TBLASTX)
		return ALIGN_TDNA_TO_TDNA;
	return 0;
}


/*********************************************************************
*
*	FreeAlignNode(list)
*	free a list of AlignNodePtr
*
*********************************************************************/
NLM_EXTERN ValNodePtr FreeAlignNode(ValNodePtr list)
{
	AlignNodePtr anp;
	AlignSegPtr asp, aspnext;
	ValNodePtr   next;
	AlignBlockPtr abp, abpnext;
	AnnotInfoPtr annot_info;

 	while (list != NULL) 
 	{
		next = list->next;
		if(list->choice == OBJ_SEQANNOT)
		{
			annot_info = list->data.ptrvalue;
			MemFree(annot_info);
		}
		else
		{
			anp = list->data.ptrvalue;
			if (anp != NULL) 
			{
				asp = anp->segs;
				while(asp !=NULL)
				{
					aspnext = asp->next;
					asp->next = NULL;
					if(asp->cnp != NULL)
						FreeFeatureList(asp->cnp);
					if(asp->mismatch)
						ValNodeFree(asp->mismatch);
					MemFree(asp);
					asp = aspnext;
				}
				abp = anp->blocks;
				while(abp != NULL)
				{
					abpnext = abp->next;
					MemFree(abp);
					abp = abpnext;
				}
				if(anp->pop_sap !=NULL)
					SeqAnnotFree(anp->pop_sap);
				SeqIdFree(anp->sip);
				MemFree (anp->label);
				MemFree (anp->clone_id);
				MemFree(anp);
			}
		}
		MemFree (list);

		list = next;
	}
	return NULL;
}




/***********************************************************************
*
* 	CollectSegmentSeq(bsp, slp, seqID, offset, head)
*		collect the segments in Bioseq
*	bsp: Bioseq
*	slp: the location on bsp to be collected
*	seqID: the order of bsp in the current list
*	offset: the offset to the graphic
*	head: the head of the previous list
*	return the head of new list
*	if bsp is a segmented sequence, the corresponding segments are recorded
*	in inp. Otherwise there is only one inp for slp.
*	
************************************************************************/


typedef struct collectheader{	/*for collecting data of a sequence display*/
	CollectSeqOptionPtr csop;	/*option for the sequences+features*/
	ValNodePtr features;		/*a list of FeatNode for storing the feature data*/
	ValNodePtr prev_feat;		/*previous node, for speed it up */
	CollectAlignOptionPtr caop;	/*option for the alignment*/
	ValNodePtr aligns;			/*a list of AlignNode for storing alignment data*/
	ValNodePtr prev_align;		/*the previous node for alignment*/	
	SeqLocPtr slp;				/*target Seq-loc*/
	SeqIdPtr maybe_mapid;			/*a possible mapid*/
	
	ObjMgrPtr omp;				/*for save some space in the collection*/
	Char thislabel[101];
	Char ftype[101];
	Uint2 subtype;
	Int2 filter_level;
	GeneDataPtr gdata;
	Uint2 priority;
	Boolean take_all_annot;		/*take everything in a Seq-annot*/
	Boolean load_align;
	Boolean skip_feature;
	Uint1 index;
	Char annotDB[21];
	Boolean is_lod_score;
}CollectHeader, PNTR CollectHeaderPtr;



static void link_data_for_collect (ValNodePtr PNTR head, ValNodePtr PNTR prev, Pointer data, Uint1 type)
{
	ValNodePtr curr;

	curr = ValNodeNew(NULL);
	curr->choice = type;
	curr->data.ptrvalue = data;

	if(*prev == NULL)
		*head = curr;
	else
		(*prev)->next = curr;

	*prev = curr;
}

static ValNodePtr get_last_node (ValNodePtr head)
{
	if(head == NULL)
		return NULL;

	while(head->next != NULL)
		head = head->next;
	return head;
}

static FeatNodePtr CreateFeatNode (ValNodePtr PNTR f_head, ValNodePtr PNTR prev, Uint2 itemType, Uint2 itemID, Uint2 entityID, Uint2 feattype)
{
	FeatNodePtr  fnp;

	fnp = MemNew (sizeof (FeatNode));
	fnp->itemID = itemID;
	fnp->entityID = entityID;
	fnp->feattype = (Uint1)feattype;
	link_data_for_collect(f_head, prev, (Pointer)fnp, (Uint1)(itemType));
	return fnp;
}

static Boolean collect_feature_label(Uint1 format)
{
	return (format <=OM_LABEL_SUMMARY);
}

static Boolean collect_sequence_label(Uint1 format)
{
	return (format >= PRINTID_FASTA_SHORT && format <=PRINTID_REPORT);
}

/*#####################################################################
#
#	functions related to the collection of the features of alignment
#
#####################################################################*/


/****************************************************************
*
*	satcollfunc()
*	callback function for collecting features on Sequence 
*	alignment. It recalculates the feature intervals based on 
*	the intervals in the aligned segments
*
****************************************************************/
typedef struct alignfeat
{
	ObjMgrPtr omp;
	AlignNodePtr anp;
	CollectSeqOptionPtr csop;
	Int2 filter_level;
	Boolean all_feature;
}AlignFeat, PNTR AlignFeatPtr;

static Boolean is_powerblast_feature(SeqAnnotPtr annot)
{
	ValNodePtr desc;

	if(annot->type != 1)
		return FALSE;
	for(desc = annot->desc; desc != NULL; desc = desc->next)
	{
		if(desc->choice == Annot_descr_name)
		{
			if(StringICmp(desc->data.ptrvalue, "powblast") == 0)
				return TRUE;
			if(StringICmp(desc->data.ptrvalue, "powerblast") == 0)
				return TRUE;
			/*powerBlast feature*/
			if(StringNCmp(desc->data.ptrvalue, "PB:", 3) == 0)
				return TRUE;
		}
	}
	return FALSE;
}


static Boolean satcollfunc(GatherContextPtr gcp)
{
	SeqFeatPtr sfp;
	AlignFeatPtr afp;
	CollectSeqOptionPtr csop;
	
	AlignNodePtr anp;
	Uint2 feat_subtype;	/*types defined by objfdef.h*/
	SeqLocPtr slp = NULL;
	Char label[101];
	ObjMgrTypePtr omtp;
	IvalNodePtr new;
	FeatNodePtr fnp;
	AlignSegPtr asp;
	Int4 current_pos;
	Uint1 strand;
	Int4 seglen;
	SeqLocPtr head;
	Int2 label_size;
	Int4 left, right, e_left, e_right;
	Int4 i_left, i_right;
	Int4 ins_len, gap_len;
	GatherRangePtr grp;
	Int2 i;
	ValNodePtr prev;
	
	afp= (AlignFeatPtr)(gcp->userdata);
	if(afp == NULL || afp->csop == NULL)
		return FALSE;

	if(gcp->thistype == OBJ_SEQANNOT)
	{
		afp->all_feature = is_powerblast_feature((SeqAnnotPtr)(gcp->thisitem));
		return TRUE;
	}
	if(gcp->thistype != OBJ_SEQFEAT)
		return TRUE;
		
	if(afp->filter_level == gcp->seglevel+1)
		return TRUE;
	csop = afp->csop;
	label_size = MIN(100, csop->label_size);
	if(csop->features == NULL && afp->all_feature == FALSE)
		return FALSE;

	omtp=ObjMgrTypeFind(afp->omp, OBJ_SEQFEAT, NULL, NULL);
	if(omtp == NULL)
		return TRUE;

	feat_subtype = 0;
	if(omtp->subtypefunc !=NULL)
		feat_subtype =  (*(omtp->subtypefunc)) (gcp->thisitem); 
	if((afp->all_feature == FALSE) && 
		(csop->features[feat_subtype] == FALSE))	/*do not collect the current feature*/
		return TRUE;


	anp = afp->anp;
	current_pos = anp->seqpos;
	if(anp->seqpos < 0)
		strand = Seq_strand_minus;
	else
		strand = Seq_strand_plus;
	sfp = gcp->thisitem;
	label[0] = '\0';
	if(collect_feature_label(csop->flabel_format[feat_subtype]))
		if(omtp->labelfunc !=NULL)
			(*(omtp->labelfunc))(sfp, label, label_size, csop->flabel_format[feat_subtype]);

	/*map to the location of aligned segs*/
	if(gcp->product)	/*for protein sequence alignment*/
		head = sfp->product;
	else
		head = sfp->location;
	left = anp->extremes.left;
	ins_len = 0;
	gap_len = 0;
	e_left = gcp->extremes.left;
	e_right = gcp->extremes.right;
	for(asp = anp->segs; asp !=NULL; asp = asp->next)
	{
		if(asp->type != GAP_SEG)
		{
			prev = get_last_node (asp->cnp);
			if(asp->type == INS_SEG)
			{
				seglen = asp->gr.right;
				/*ins_len += seglen;*/
			}
			else
				seglen = asp->gr.right - asp->gr.left +1;
			right = left + seglen -1;
			if(!(left > e_right || right < e_left))
			{
				fnp = CreateFeatNode (&(asp->cnp), &prev, OBJ_SEQFEAT, gcp->itemID, gcp->entityID, feat_subtype);
				fnp->extremes.left = MAX(left, e_left)  + gap_len;
				fnp->extremes.right = MIN(right, e_right) + gap_len;
				fnp->extremes.left -=ins_len;
				fnp->extremes.right -= ins_len;
				fnp->extremes.strand = gcp->extremes.strand;
				if(label[0] != '\0')
					fnp->label = StringSave(label);
				grp = gcp->rdp;
				for(i=0; (grp!=NULL) && i<gcp->num_interval; ++i)
				{
					i_left = grp->left;
					i_right = grp->right;
					if(!(left > i_right || right < i_left))
					{
						new = MemNew(sizeof(IvalNode));
						new->gr.left = MAX(left, i_left) - ins_len + gap_len;
						new->gr.right = MIN(right, i_right) - ins_len + gap_len;
						new->gr.strand = grp->strand;
						ValNodeAddPointer(&(fnp->interval), 0, new);
					}
					++grp;
				}
			}
			left = right +1;
			if(asp->type == INS_SEG)
				ins_len += seglen;
		}
		else
			gap_len += (asp->gr.right - asp->gr.left +1);
	}
	return TRUE;
}
	
		
/******************************************************************
*
*	CollectFeatureForAlignNode(slp, anp, csop)
*	collect feature for the alignment
*	slp: the target Seq-loc
*	anp: the AlignNode belong to the target Seq-loc
*	csop: the option for gathering the features
*	
******************************************************************/			
NLM_EXTERN Boolean CollectFeatureForAlignNode(SeqLocPtr slp, AlignNodePtr anp, CollectSeqOptionPtr csop)
{
	GatherScope gs;
	AlignFeat af;
	BioseqPtr bsp;
	
	if(slp == NULL || anp == NULL || csop == NULL)
		return FALSE;
		
	if(anp->seq_entityID == 0)
		return FALSE;
	bsp = BioseqLockById(SeqLocId(slp));


	MemSet((Pointer)&gs, 0, sizeof (GatherScope));
	gs.get_feats_location = TRUE;
	gs.get_feats_product =( bsp->mol == Seq_mol_aa);
	MemSet((Pointer)(gs.ignore), (int)TRUE, (size_t)(OBJ_MAX)*sizeof(Boolean));

	gs.ignore[OBJ_SEQANNOT] = FALSE;
	gs.ignore[OBJ_SEQFEAT] = FALSE;

	gs.nointervals = FALSE;	/*need to recalculate the intervals*/
	/* gs.seglevels = 1;
	gs.seglevels = 1;
	gs.stop_on_annot = TRUE;*/
	gs.ignore_top = FALSE;
	gs.currlevel = 0;
	gs.offset = anp->extremes.left;
	gs.target = slp;

	af.anp = anp;
	af.csop = csop;
	af.omp = ObjMgrGet();
	af.filter_level = 0;

	GatherEntity(anp->seq_entityID, (Pointer)(&af), satcollfunc, &gs);
	BioseqUnlock(bsp);
	return TRUE;
}


/******************************************************************
*
*	CollectFeatureForAlign(slp, anp, featureOrder, groupOrder)
*	collect feature for the alignment
*	slp: the target Seq-loc
*	anp: the AlignNode belong to the target Seq-loc
*	featureOrder: the order of features
*	groupOrder: the order of the groups
*	it takes the anp->seq_entityID and searches for the features
*	
******************************************************************/			

static Boolean CollectAlignFeature(SeqLocPtr slp, AlignNodePtr anp, Uint1Ptr featureOrder, Uint1Ptr groupOrder, Uint1Ptr flabel_format) 
{
	CollectSeqOption cs_option;
	Boolean show_feature, collect = FALSE;
	Int2 i;
	ValNode vn;
	
	if(featureOrder == NULL || groupOrder == NULL || slp == NULL || anp == NULL)
		return FALSE;
	
	cs_option.nointerval = FALSE;
	cs_option.slabel_format = PRINTID_TEXTID_ACCESSION;
	cs_option.seglevels = 0;
	cs_option.label_size = 10;
	for( i =0; i<FEATDEF_ANY; ++i)	/*for checking the features to load*/
	{
		show_feature = (featureOrder[i] != 0);
		cs_option.features[i] = show_feature;
		if(show_feature)
			collect = TRUE;
	}
	if(collect)
	{
		if(flabel_format == NULL)
			MemSet((Pointer)(cs_option.flabel_format), OM_LABEL_CONTENT, (size_t)FEATDEF_ANY*sizeof(Uint1));
		else
			MemCopy(&(cs_option.flabel_format), &flabel_format, (size_t)FEATDEF_ANY*sizeof(Uint1));
		CollectFeatureForAlignNode(slp, anp, &cs_option);
		vn.choice = OBJ_SEQALIGN;
		vn.data.ptrvalue = anp;
		vn.next = NULL;
		SortAlignmentFeature(&vn, featureOrder, groupOrder);
		return TRUE;
	}
	else
		return FALSE;
}

NLM_EXTERN Boolean CollectFeatureForAlign(SeqLocPtr slp, AlignNodePtr anp, Uint1Ptr featureOrder, Uint1Ptr groupOrder) 
{
	return CollectAlignFeature(slp, anp, featureOrder, groupOrder, NULL);
}

/******************************************************************
*
*	SortAlignmentFeature(anp_node, featureOrder, groupOrder)
*	sort the list of FeatNode in aligned segment (asp->cnp) to the 
*	proper order of featureOrder and groupOrder
*
*******************************************************************/
NLM_EXTERN void SortAlignmentFeature(ValNodePtr anp_node, Uint1Ptr featureOrder, Uint1Ptr groupOrder)
{
	AlignNodePtr anp;
	AlignSegPtr asp;
	
	while(anp_node)
	{
		if(anp_node->choice != OBJ_SEQANNOT)
		{
			anp = anp_node->data.ptrvalue;
			for(asp = anp->segs; asp !=NULL; asp = asp->next)
					if(asp->cnp !=NULL)
						asp->cnp = SortFeatNode(asp->cnp, featureOrder, groupOrder);
		}
		anp_node = anp_node->next;
	}
}
		

static SeqPortPtr make_current_seqport(SeqLocPtr masterloc, Int4 offset, Uint1 code)
{
	SeqLocPtr slp;
	Int4 start, stop;
	Uint1 strand;
	SeqPortPtr spp;


	start = SeqLocStart(masterloc);
	stop = SeqLocStop(masterloc);
	strand = SeqLocStrand(masterloc);

	if(strand == Seq_strand_minus)
		stop -= offset;
	else
		start += offset;
	slp = SeqLocIntNew(start, stop, strand, SeqLocId(masterloc));
	spp = SeqPortNewByLoc(slp, code);
	SeqLocFree(slp);

	return spp;
}


static void add_int_to_node (ValNodePtr PNTR head, ValNodePtr PNTR prev, Int4 val, Uint1 choice)
{
	ValNodePtr curr;

	curr = ValNodeNew(NULL);	
	curr->choice = choice;
	curr->data.intvalue = val;

	if(*prev == NULL)
		*head = curr;
	else
		(*prev)->next = curr;
	*prev = curr;
}


static Boolean CollectMismatchForAlign(AlignNodePtr anp, SeqLocPtr masterloc, BioseqPtr bsp, Int4 offset)
{
	
	AlignSegPtr asp;
	SeqPortPtr spp, mspp;
	Uint1 code;
	Uint1 res, mres;
	Int4 start = 0, stop = 0;
	Uint1 strand;
	Int4 current_pos;
	Int4 seglen, j;
	ValNodePtr prev;


		
	if(anp->is_master || SeqIdForSameBioseq(SeqLocId(masterloc), anp->sip))
		return FALSE;
	if(bsp->mol == Seq_mol_aa)
		code = Seq_code_ncbieaa;
	else
		code = Seq_code_iupacna;
	/* mspp = SeqPortNewByLoc(masterloc, code); */

	current_pos = anp->seqpos;
	if(anp->seqpos < 0)
	{
		strand = Seq_strand_minus;
		if(ABS(anp->seqpos) < bsp->length-1)
			anp->extremes.l_trunc = TRUE;
	}
	else
	{
		strand = Seq_strand_plus;
		if(anp->seqpos > 0)
			anp->extremes.l_trunc = TRUE;
	}
	for(asp = anp->segs; asp !=NULL; asp = asp->next)
	{
		if(asp->type == INS_SEG)
			seglen = asp->gr.right;
		else
			seglen = asp->gr.right - asp->gr.left + 1;
		switch(asp->type)
		{
			case GAP_SEG:
				break;
				
			case INS_SEG:
				current_pos += seglen;
				break;
				
			case REG_SEG:
			case DIAG_SEG:
				prev = get_last_node (asp->mismatch);
				if(strand == Seq_strand_minus)
				{
					stop = - current_pos;
					start = stop - (seglen-1);
				}
				else
				{
					start = current_pos;
					stop = start + (seglen -1);
				}
				spp = SeqPortNew(bsp, start, stop, strand, code);
				
				mspp = make_current_seqport(masterloc, (asp->gr.left - offset), code);
				/* SeqPortSeek(mspp, (asp->gr.left - offset), SEEK_SET); */

				for(j =0; j<seglen; ++j)
				{
					res = SeqPortGetResidue(spp);
					mres = SeqPortGetResidue(mspp);
					while(res == SEQPORT_EOS || res == SEQPORT_VIRT)
						res = SeqPortGetResidue(spp);
					while(mres == SEQPORT_EOS || mres == SEQPORT_VIRT)
						mres = SeqPortGetResidue(mspp);
					if(IS_ALPHA(res) && IS_ALPHA(mres))
					{
						if(res != mres)
						{
							if(bsp->mol != Seq_mol_aa && !StrChr("acgtACGT", res))
								add_int_to_node (&(asp->mismatch), &prev, (j+asp->gr.left), MISMATCH_AMB);
							else
								add_int_to_node (&(asp->mismatch), &prev, (j+asp->gr.left), MISMATCH_LINE);
							/* ValNodeAddInt(&(asp->mismatch), 0, (j+asp->gr.left)); */
						}
					}
					else if(res == SEQPORT_EOF || mres == SEQPORT_EOF)
						break;
					
				}
				current_pos += seglen;
				
				SeqPortFree(spp);
				SeqPortFree(mspp);
				break;
				
			default:
				break;
		}
		/*current_pos += seglen;*/
	}
	/* SeqPortFree(mspp); */
	if(strand == Seq_strand_minus)
	{
		if(start > 0)
			anp->extremes.r_trunc = TRUE;
	}
	else
	{
		if(stop < bsp->length-1)
			anp->extremes.r_trunc = TRUE;
	}
	
	return TRUE;
}


static AlignBlockPtr make_one_block(SeqRangePtr srp, Int4 seq_start, Int4 seq_stop, Int4 left, Int4 right, Int2 order, AlignNodePtr anp)
{
	AlignBlockPtr abp;
	Int4 off_left, off_right;
	
	if(srp == NULL || anp == NULL)
		return NULL;
	if(srp->start > seq_stop || srp->stop < seq_start)
		return NULL;

	if(srp->strand == Seq_strand_minus)
	{
		off_left = MAX(0, (srp->stop - seq_stop));
		off_right = MAX(0, (seq_start - srp->start));
	}
	else
	{
		off_left = MAX(0, (seq_start - srp->start));
		off_right = MAX(0, (srp->stop - seq_stop));
	}
	
	abp = MemNew(sizeof(AlignBlock));
	abp->gr.left = left + off_left;
	abp->gr.right = right - off_right;
	abp->gr.strand = 0;
	if(abp->gr.left == anp->extremes.left&& anp->extremes.strand == Seq_strand_minus)
		abp->gr.strand = Seq_strand_minus;
	if(abp->gr.right == anp->extremes.right && anp->extremes.strand == Seq_strand_plus)
		abp->gr.strand = Seq_strand_plus;
	abp->order = order;
	return abp;
}


static AlignBlockPtr link_align_blocks(AlignBlockPtr PNTR head, AlignBlockPtr new)
{
	AlignBlockPtr curr;

	if(*head == NULL)
		*head = new;
	else
	{
		curr = *head;
		while(curr->next != NULL)
			curr = curr->next;
		curr->next = new;
	}
	return new;
}


static Boolean make_blocks(AlignDataPtr adp, Int4 seq_start, Int4 seq_stop, Int2 order, AlignNodePtr anp)
{
	AlignBlockPtr abp = NULL;
	AlignRangePtr arp;
	

	if(adp == NULL || anp == NULL)
		return FALSE;
	if(adp->arp == NULL)
	{
		abp = make_one_block(&(adp->seqends), seq_start, seq_stop, anp->extremes.left, anp->extremes.right, order, anp);
		if(abp != NULL)
			link_align_blocks(&(anp->blocks), abp);
	}
	else
	{
		for(arp = adp->arp; arp != NULL; arp = arp->next)
		{
			if(arp->segtype == REG_SEG)
			{
				abp = make_one_block(&(arp->sr), seq_start, seq_stop, arp->gr.left, arp->gr.right, order, anp); 
				if(abp != NULL)
				{
					link_align_blocks(&(anp->blocks), abp);
					break;
				}
			}
		}
	}
	return (abp != NULL);
}
		

static Boolean sequence_has_alignment(ValNodePtr align_id_list, SeqIdPtr sip)
{
	Uint1 kludge_factor;
	Int4 gi;
	
	
	kludge_factor = (Uint1)get_kludge_factor(sip, &gi);
	if(gi == -1)
		return FALSE;
		
	while(align_id_list)
	{
		if(align_id_list->choice == kludge_factor)
		{
			if(align_id_list->data.intvalue == gi)
				return TRUE;
		}
		
		align_id_list = align_id_list->next;
	}
	
	return FALSE;
}



static Boolean add_sequence_alignment_info(ValNodePtr align_id_list, ValNodePtr anp_list)
{

	AlignNodePtr anp;
	
	if(align_id_list == NULL || anp_list == NULL)
		return FALSE;
		
	while(anp_list)
	{
		if(anp_list->choice != OBJ_SEQANNOT)
		{
			anp = anp_list->data.ptrvalue;
			if(anp->seq_has_align == FALSE)
				anp->seq_has_align = sequence_has_alignment(align_id_list, anp->sip);
		}
		anp_list = anp_list->next;
	}
	
	return TRUE;
}


typedef struct temp_bsp_data{
	BioseqPtr bsp;
	Uint2 itemID;
	Boolean found;
}TempBsp, PNTR TempBspPtr;

static Boolean bspcountfunc(GatherContextPtr gcp)
{
	TempBspPtr tbp;
	BioseqPtr bsp;

	if(gcp == NULL)
		return FALSE;
	tbp = (TempBspPtr)(gcp->userdata);
	if(tbp == NULL || tbp->bsp == NULL)
		return FALSE;
	if(tbp->found)
		return FALSE;
	bsp = (BioseqPtr)(gcp->thisitem);
	if(tbp->bsp == bsp)
	{
		tbp->itemID= gcp->itemID;
		tbp->found = TRUE;
		return FALSE;
	}
	else
		return TRUE;
}
	
/*****************************************************************
*
*       given the bioseq and its entityID, figure out the 
*       itemID for the Bioseq
*
*****************************************************************/
NLM_EXTERN Uint2 get_bioseq_itemID(BioseqPtr bsp, Uint2 entityID)
{
	GatherScope gs;
	TempBsp tb;


	if(bsp == NULL || entityID == 0)
		return 0;

	tb.bsp = bsp;
	tb.itemID= 0;
	tb.found = FALSE;

	MemSet((Pointer)(&gs), 0, sizeof(GatherScope));
	MemSet((Pointer)(gs.ignore), (int)(TRUE), (size_t)OBJ_MAX * sizeof(Boolean));
	gs.ignore[OBJ_BIOSEQ] = FALSE;
	GatherEntity(entityID, &tb, bspcountfunc, &gs);

	return tb.itemID;
}
	
	
static Boolean stop_collecting_alignment(ValNodePtr anp_list, Int4 max_num)
{
	Int2 i;

	i = 0 ;
	while(anp_list)
	{
		++i;
		if(i > max_num)
		{
			if(anp_list->next == NULL)
				return TRUE;
		}
		anp_list = anp_list->next;
	}

	return FALSE;
}

static void FindCloneCallback(SeqEntryPtr sep, Pointer data, Int4 index, Int2 indent)
{
	AlignNodePtr anp;
	BioseqPtr bsp;
	BioseqSetPtr bssp;
	ValNodePtr descr;
	ValNodePtr curr;
	OrgRefPtr orp;
	ValNodePtr mod;
	CharPtr str;

	BioSourcePtr source;
	SubSourcePtr ssp;

	anp = (AlignNodePtr)data;
	if(anp->clone_id != NULL)
		return;


	if(sep->choice == 1)
	{
		bsp = (BioseqPtr)(sep->data.ptrvalue);
		descr = bsp->descr;
	}
	else
	{
		bssp = (BioseqSetPtr)(sep->data.ptrvalue);
		descr = bssp->descr;
	}

	for(curr = descr; curr != NULL; curr = curr->next)
	{
		if(curr->choice == Seq_descr_source)
		{
			source = curr->data.ptrvalue;
			/* search for /chromosome= */
			for(ssp = source->subtype; ssp != NULL; ssp = ssp->next)
			{
				if(ssp->subtype == 3 && ssp->name != NULL)
				{	/* 3 == clone */
					anp->clone_id = StringSave(ssp->name);
					return;
				}
			}
		}
		else if(curr->choice == Seq_descr_org)
		{
			orp = curr->data.ptrvalue;
			if(orp)
			{
				for(mod = orp->mod; mod != NULL; mod = mod->next)
				{
					str = mod->data.ptrvalue;
					if(StringNCmp(str, "clone=", 6) == 0)
					{
						anp->clone_id = StringSave(str+6);
					}
				}
			}
		}
	}
}

static Boolean LoadIndexLabelBlock(AlignNodePtr anp)

{
	AlignBlockPtr abp;
	SeqIdPtr sip;
	ObjectIdPtr oip;
	DbtagPtr db_tag;

	sip = anp->sip;
	if(sip == NULL || sip->choice != SEQID_GENERAL)
		return FALSE;

	db_tag = sip->data.ptrvalue;
	if(db_tag == NULL || db_tag->db == NULL)
		return FALSE;
	oip = db_tag->tag;
	if(oip== NULL || oip->id <= 0)
		return FALSE;
	
	
	abp = MemNew(sizeof(AlignBlock));
	MemCopy((Pointer)(&(abp->gr)), (Pointer)(&(anp->extremes)), sizeof(GatherRange));
	abp->order = (Uint2)oip->id;
	anp->blocks = abp;

	anp->label = StringSave(db_tag->db);
	return TRUE;
}


/***********************************************************************
*
*	coll_align_data(align, m_sip, adp, clone, featureOrder, show_mismatch, 
*	itemID, entityID, anp_list)
*	convert all the alignment data stored in adp into the drawing 
*	structure AlignNode
*
*	align: the current Seq-align
*	m_sip: the master sequence, also the target sequence in gather
*	adp: the collected structure from gather
*	clone: for filtering out unwanted clone type. set to NULL for all
*	featureOrder: for features to be displayed together with alignment
*	show_mismatch: show the mismatched base-pairs
*	itemID: itemID for the current align
*	entityID: entityID for the Seq-entry of m_sip
*
*	NOTE: if either show_mismatch or featureOrder is selected, it puts 
*	the newly retrieved sequence for itemID and entityID 
*	
*	anp_list: the list of AlignNodePtr to stored the coverted result
*
************************************************************************/	

static Boolean coll_align_data(SeqAlignPtr align, Uint1 index, AlignDataPtr adp, CollectAlignOptionPtr caop, Int2 itemID, Int2 entityID, Int2 itemType, SeqLocPtr mloc, ValNodePtr PNTR anp_list, ValNodePtr PNTR prev)
{
	Char label[41];
	
	SeqLocPtr slp, extloc;
	SeqIdPtr sip;
	Boolean feat;	/*collect any features?*/
	Boolean show_mismatch;
	Boolean is_master;
	
	AlignRangePtr arp;
	AlignNodePtr anp;
	AlignSegPtr asp, pasp;

	BioseqPtr bsp;
	Uint2 order;
	Int4 e_left = 0, e_right = 0;
	Boolean match_seg;
	Int2 label_size;
	Int4 offset = 0;
	SeqIdPtr best_id;
	SeqEntryPtr sep;

  

	label_size = MIN(caop->label_size, 100);
	feat = caop->show_feature;
	if(align->segtype == 3)	/*for std-seg, no feature or mismatch*/
	{
		show_mismatch = FALSE;
		feat = FALSE;
	}
	else
		show_mismatch = caop->show_mismatch;

	if(align->segtype == 2)	/*for Dense-seg or Dense-diag only*/
	{
		if(caop->align_num != -1)
		{
			/* if(stop_collecting_alignment(*anp_list, caop->align_num)) */
			if(caop->curr_align_num > caop->align_num)
			{
				/* ErrPostEx (SEV_WARNING, 0, 0, "The top %ld alignments are displayed. The rest are truncated", caop->align_num);
				return FALSE; */
				feat = FALSE;
				show_mismatch = FALSE;
			}
		}
	}

	while(adp)
	{
		++(caop->curr_align_num);
		anp = MemNew(sizeof (AlignNode));
		anp->pop_sap = NULL;
		anp->itemID = itemID;
		anp->entityID = entityID;
		anp->seqOrder = adp->order;
		anp->chain = adp->chain;
		anp->seq_has_align = FALSE;
		anp->index = index;
		MemCopy(&(anp->extremes), &(adp->extremes), sizeof(GatherRange));

		if(adp->seqends.strand == Seq_strand_minus)
			anp->seqpos = -(adp->seqends.stop);
		else
			anp->seqpos = adp->seqends.start;
			
		pasp = NULL;
		for(arp = adp->arp; arp !=NULL; arp = arp->next)
		{
			asp = MemNew(sizeof(AlignSeg));
			MemCopy(&(asp->gr), &(arp->gr), sizeof(GatherRange));
			asp->type = arp->segtype;
			if(asp->type == INS_SEG)
				asp->ins_pos = asp->gr.left;
			if(pasp == NULL)
				anp->segs = asp;
			else
				pasp->next = asp;
			pasp = asp;
		}
		
		if(index == ALIGN_NON_INDEX  && (feat|| show_mismatch))
		{
			bsp = BioseqLockById(adp->sip);
			if(bsp != NULL)
			{
				if(adp->sip->choice == SEQID_GI)
				{
					sep = SeqEntryFind(adp->sip);
					if(sep != NULL)
						SeqEntryExplore(sep, (Pointer)anp, FindCloneCallback);
				}
				if(bsp->hist && bsp->hist->assembly)
					anp->seq_has_align = TRUE;
				anp->seq_entityID = ObjMgrGetEntityIDForPointer((Pointer)bsp);
				anp->bsp_itemID = get_bioseq_itemID(bsp, anp->seq_entityID);
				best_id = SeqIdFindBest(bsp->id, SEQID_GI);
				if(best_id == NULL)
					best_id = bsp->id;
				anp->sip = SeqIdDup(best_id);
				
				if(feat)
				{
					if(BioseqHasFeature(bsp))
						caop->csop->seglevels = 0;
					else
						caop->csop->seglevels = 1;
					slp = SeqLocIntNew(adp->seqends.start, adp->seqends.stop, adp->seqends.strand, best_id);
					CollectFeatureForAlignNode(slp, anp, caop->csop);
					SeqLocFree(slp);
				}
				if(show_mismatch && bsp->repr != Seq_repr_map)
					CollectMismatchForAlign(anp, mloc, bsp, offset+caop->graphic_offset);

				BioseqUnlock(bsp);
			}
			/* else
				printf("fail to get sequence for %ld\n", adp->sip->data.intvalue);  */
		}
		if(anp->sip == NULL)
			anp->sip = SeqIdDup(adp->sip);
			


		/*collecting matching piece to show the content of a segmented sequence*/			
		if(caop->segloc != NULL && index == ALIGN_NON_INDEX )	
		{
			is_master = SeqIdForSameBioseq(adp->sip, SeqLocId(mloc));
			if(is_master)
			{
				e_left = 0;
				e_right = -1;
			}
			order = 0;
			for(extloc = caop->segloc; extloc != NULL; extloc = extloc->next)
			{
				++order;
				match_seg = FALSE;
				if(is_master)
				{
					e_right += SeqLocLen(extloc);
					match_seg = TRUE;
				}
				else
				{
					sip = SeqLocId(extloc);
					match_seg = SeqIdForSameBioseq(sip, anp->sip);
						
				}
				if(match_seg)
				{
					if(!is_master)
					{
						e_left = SeqLocStart(extloc);
						e_right = SeqLocStop(extloc);
					}
					match_seg = make_blocks(adp, e_left, e_right, order, anp);
				}
				if(is_master)
					e_left = e_right +1;
				if(match_seg)
					if(e_right > adp->seqends.stop)
						break;
			}
		}

		/*store the index information in the blocks*/
		if(index != ALIGN_NON_INDEX)
			LoadIndexLabelBlock(anp);
		else if(label_size > 0)
		{
			if(MuskSeqIdWrite (anp->sip, label, label_size, caop->slabel_format, TRUE, TRUE))
				anp->label = StringSave(label);
		}

		link_data_for_collect (anp_list, prev, (Pointer)anp, (Uint1)itemType);
		adp = adp->next;
	}
	return TRUE;
}
	
static Boolean does_annot_match_target (SeqLocPtr target, SeqAnnotPtr annot)
{
	SeqAlignPtr sap;
	SeqIdPtr sip;
	DenseDiagPtr ddp;
	DenseSegPtr dsp;
	StdSegPtr ssp;
	SeqIdPtr target_id;
	SeqLocPtr slp;

	if(target == NULL || annot == NULL || annot->type != 2)
		return FALSE;
	target_id = SeqLocId(target);
	sap = annot->data;
	if(sap == NULL)
		return FALSE;
	switch(sap->segtype)
	{
		case 1:
			ddp = sap->segs;
			for(sip = ddp->id; sip != NULL; sip = sip->next)
				if(SeqIdForSameBioseq(sip, target_id))
					return TRUE;
			break;
		case 2:
			dsp = sap->segs;
			for(sip = dsp->ids; sip != NULL; sip = sip->next)
				if(SeqIdForSameBioseq(sip, target_id))
					return TRUE;
			break;
		case 3:
			ssp = sap->segs;
			for(slp = ssp->loc; slp != NULL; slp = slp->next)
				if(SeqIdForSameBioseq(SeqLocId(slp), target_id))
					return TRUE;
			break;
		default:
			break;
	}

	return FALSE;
}
			
static Boolean collalignfunc(GatherContextPtr gcp)
{
	SeqAnnotPtr annot;
	CollectHeaderPtr chp;
	AnnotInfoPtr info;
	SeqAlignPtr align;
	Uint1 annot_type;
	
	
	chp= (CollectHeaderPtr)(gcp->userdata);

	switch(gcp->thistype)
	{
	case OBJ_SEQANNOT:
		annot = (SeqAnnotPtr)(gcp->thisitem);
		if(annot->type == 2)
		{
		chp->caop->curr_align_num = 0;
		chp->load_align = TRUE;
		chp->index = 0;
		if(!chp->take_all_annot)
		{
			if(!is_annot_for_hist_alignment(annot))
			{
				chp->load_align = FALSE;
				return TRUE;
			}
		}
		info = MemNew(sizeof(AnnotInfo));
		info->annotDB[0] = '\0';
		info->displayOrder = get_align_annot_qual(annot, info->annotDB, 20, &annot_type);
		info->annot_type = annot_type;
		if(annot_type == ANNOT_BLAST)
			info->blast_type = info->displayOrder;
		/*load the index values*/
		if(info->annotDB[0] != '\0')
		{
			if(StringCmp(info->annotDB, "Sequencing Status") == 0)
				chp->index = ALIGN_SEQ_INDEX;
			else if(StringCmp(info->annotDB, "Mapping Status") == 0)
				chp->index = ALING_MAP_INDEX;
		}

		/* Eric Green's un-aligned guys */
		if(annot_type == ANNOT_CONSIST)
		{
			info->consistent = info->displayOrder;
			if(info->consistent == ALIGN_UNKNOWN)
			{	/*un-aligned guys, check if the Seq-loc matches */
				if(!does_annot_match_target (chp->slp, annot))
					info = MemFree(info);
				chp->load_align = FALSE;
			}
		}
		else if(annot_type == ANNOT_FISH)
			info->is_fish_align= TRUE;
		if(info != NULL)
		{
			info->entityID = gcp->entityID;
			info->itemID = gcp->itemID;
			link_data_for_collect (&(chp->aligns), &(chp->prev_align), (Pointer)info, (Uint1)(gcp->thistype));
		}
		}
		return TRUE;

	case OBJ_SEQALIGN:
		align = (SeqAlignPtr)(gcp->thisitem);
		if(chp->load_align)
			return coll_align_data(align, chp->index, gcp->adp, chp->caop, gcp->itemID, gcp->entityID, gcp->thistype, chp->slp, &(chp->aligns), &(chp->prev_align));
		else
			return TRUE;
	case OBJ_SEQHIST_ALIGN:
		align = (SeqAlignPtr)(gcp->thisitem);
		return coll_align_data(align, chp->index, gcp->adp, chp->caop, gcp->itemID, gcp->entityID, gcp->thistype, chp->slp, &(chp->aligns), &(chp->prev_align));
	case OBJ_SEQHIST:
		chp->caop->curr_align_num = 0;
		return TRUE;
	default:
		return TRUE;
	}
}

	
/*********************************************************************
*
*	CollectItemForAlignment(slp, entityID, left, caop)
*	return a list of AlignNode for the alignment in the target seqloc
*	slp: the target Seq-loc
*	entityID: the entity source for collection
*	left: the left offset on the graphic
*	caop: the option for alignment collection
*
**********************************************************************/
NLM_EXTERN ValNodePtr CollectItemForAlignment(SeqLocPtr slp, Uint2 entityID, Int4 left, CollectAlignOptionPtr caop, Boolean take_all_annot)
{
	GatherScope gs;
	CollectHeader ch;
	BioseqPtr mbsp;
	SeqIdPtr sip;
	ValNodePtr align_id_list = NULL;
	SeqLocPtr curr, next;

	if(slp == NULL || entityID == 0 || caop == NULL)
		return NULL;

	sip = SeqLocId(slp);
	ch.aligns = NULL;
	ch.caop = caop;
	ch.take_all_annot = take_all_annot;
	ch.load_align = TRUE;
	ch.prev_feat = NULL;
	ch.prev_align = NULL;
	ch.index = 0;
	/*ch.slp = slp;*/
	

	MemSet((Pointer)&gs, 0, sizeof (GatherScope));
	MemSet((Pointer)(gs.ignore), (int)TRUE, (size_t)(OBJ_MAX)*sizeof(Boolean));

	if(caop->only_history == FALSE)
	{
		gs.ignore[OBJ_SEQANNOT] = FALSE;
		gs.ignore[OBJ_SEQALIGN] = FALSE;
	}
	gs.ignore[OBJ_SEQHIST] = FALSE;
	gs.ignore[OBJ_SEQHIST_ALIGN] = FALSE;
	

	gs.nointervals = caop->nointerval;
	gs.seglevels = 0;
	gs.currlevel = 0;
	gs.split_packed_pnt = FALSE;
	gs.mapinsert = caop->map_insert;


	curr = slp;
	while(curr)
	{
		next = curr->next;
		curr->next = NULL;
		gs.offset = left;
		gs.target = curr;
		ch.slp = curr;
		caop->graphic_offset = left;
		GatherEntity(entityID, (Pointer)(&ch), collalignfunc, &gs);
		left += SeqLocLen(curr);
		curr->next = next;
		curr = next;
	}
	
	if(ch.aligns != NULL)
	{
		mbsp = BioseqLockById(sip);
		align_id_list = get_seqids_with_alignment(mbsp);
		if(align_id_list != NULL)
		{
			add_sequence_alignment_info(align_id_list, ch.aligns);
			ValNodeFree(align_id_list);
		}
		BioseqUnlock(mbsp);
	}
			
	
	return ch.aligns;
}


static void merge_master_head(ValNodePtr head, ValNodePtr new_node)
{
	AlignNodePtr anp_head, anp;
	AlignSegPtr asp;
	AlignBlockPtr block;

	if(head == NULL || new_node == NULL)
		return;
	anp_head = head->data.ptrvalue;
	anp = new_node->data.ptrvalue;
	
	if(anp_head == NULL || anp == NULL)
		return;

	anp_head->extremes.right = anp->extremes.right;
	asp = anp_head->segs;
	if(asp == NULL)
		anp_head->segs = anp->segs;
	else
	{
		while(asp->next != NULL)
			asp = asp->next;
		asp->next = anp->segs;
	}
	anp->segs = NULL;

	block = anp_head->blocks;
	if(block == NULL)
		anp_head->blocks = anp->blocks;
	else
	{
		while(block->next != NULL)
			block = block->next;
		if(anp->blocks != NULL)
			block->gr.strand = 0;
		block->next = anp->blocks;
	}
	anp->blocks = NULL;

	FreeAlignNode(new_node);
}
	

/*****************************************************************************
*
*	cllect_master_align_node(m_loc, featureOrder, groupOrder)
*	in the master-slave alignment, a fake Seq-align is created for the 
*	master sequence where the master is aligned to itself. The AlignNode
*	can be computed for this faked alignment. When this is done, the fake
*	Seq-align will be freed
*
*	m_loc: the Seq-loc for the master sequence
*	featureOrder: the selected features
*
*******************************************************************************/
NLM_EXTERN ValNodePtr collect_master_align_node(CollectAlignOptionPtr caop, SeqLocPtr m_loc, Uint1 obj_type, Uint2 entityID)
{
	SeqAlignPtr align;
	DenseSegPtr dsp;
	SeqIdPtr m_sip;
	ValNodePtr anp_node, anp_head = NULL, curr;
	ValNodePtr prev = NULL;
	AlignNodePtr anp;
	AlignDataPtr adp;
	Int4 left =0;
	Boolean show_mismatch;

	if(caop == NULL || m_loc == NULL)
		return NULL;
		
	show_mismatch = caop->show_mismatch;
	caop->show_mismatch = FALSE;
   while(m_loc)
   {
	m_sip = SeqLocId(m_loc);

	dsp = DenseSegNew();
	dsp->dim = 2;
	dsp->numseg =1;
	dsp->strands = MemNew((size_t)2*sizeof(Uint1));
	dsp->strands[0] = Seq_strand_plus;
	dsp->strands[1] = SeqLocStrand(m_loc);
	dsp->ids = SeqIdDup(m_sip);
	dsp->ids->next = SeqIdDup(m_sip);
	dsp->starts = MemNew((size_t)2*sizeof(Int4));
	dsp->starts[0] = SeqLocStart(m_loc);
	dsp->starts[1] = SeqLocStart(m_loc);
	dsp->lens = MemNew(sizeof(Int4));
	dsp->lens[0] = SeqLocLen(m_loc);

	align = SeqAlignNew();
	align->type = 3;
	align->segtype = 2;
	align->dim = 2;
	align->segs = dsp;

	anp_node = NULL;
	adp = gather_align_data(m_loc, align, left, TRUE, TRUE);
	if(adp !=NULL)
	{
		coll_align_data(align, 0, adp, caop, 0, entityID, obj_type, m_loc, &anp_node, &prev);
		FreeAlignData(adp);
	}
	if(anp_head == NULL)
		anp_head = anp_node;
	else
		merge_master_head(anp_head, anp_node);
	SeqAlignFree(align);
	left = SeqLocLen(m_loc);
	m_loc = m_loc->next;
   }
   for(curr = anp_head; curr != NULL; curr = curr->next)
   {
	anp = curr->data.ptrvalue;
	anp->use_seq_ids = TRUE; /*use the Seq-id as the itemID for graphic display*/
	anp->is_master = TRUE;
   }
	caop->show_mismatch = show_mismatch;
   return anp_head;
}

NLM_EXTERN Boolean set_option_for_collect_align(CollectAlignOptionPtr caop, Int2 label_size, Uint1 style)
{
	if(caop == NULL)
		return FALSE;
		
	MemSet((Pointer)caop, 0, sizeof(CollectAlignOption));
	if(style < COLLECT_HISTORY || style > COLLECT_FIXED)
	{
		Message(MSG_ERROR, "Illegal style for alignment display %d", (int)style);
		return FALSE;
	}
	
	caop->nointerval = FALSE;
	caop->label_size= label_size;
	if(style == COLLECT_MD || style == COLLECT_FIXED)
	{
		caop->only_history = FALSE;
		caop->map_insert = FALSE;
	}
	else
	{
		caop->only_history = TRUE;
		caop->map_insert = TRUE;
	}
	caop->map_graphic = (style != COLLECT_FIXED);
	caop->show_mismatch = (style != COLLECT_HISTORY);
	caop->show_feature = FALSE;
	caop->slabel_format = PRINTID_TEXTID_ACCESSION;
	caop->segloc = NULL;
	caop->align_num = DEFAULT_ALIGN_NUM;
	caop->graphic_offset = 0;
	return TRUE;
}

static Boolean alignment_are_blast_hits(BioseqPtr bsp)
{
	SeqAnnotPtr annot;
	Char label[101];
	Uint1 annot_type;

	if(bsp == NULL || bsp->annot == NULL)
		return FALSE;
	for(annot = bsp->annot; annot != NULL; annot = annot->next)
	{
		if(annot->type == 2)
		{
			label[0] = '\0';
			get_align_annot_qual(annot, label, 20, &annot_type);
			if(label[0] != '\0' && StringNCmp(label, "BLAST", 5) == 0)
				return TRUE;
		}
	}
	return FALSE;
}

NLM_EXTERN ValNodePtr collect_anpnode_with_option(CollectAlignOptionPtr caop, SeqLocPtr m_loc, Uint2 entityID, Int4 style, Uint1 itemType, Uint1Ptr f_order, Uint1Ptr g_order, Boolean take_all_annot)
{
	ValNodePtr anp_list = NULL, list;
	BioseqPtr mbsp;
	Uint1 featureOrder[FEATDEF_ANY];
	Uint1 groupOrder[FEATDEF_ANY];
	Int2 i;
	CollectSeqOptionPtr csop = NULL;
	ValNodePtr align_id_list = NULL;
	AlignNodePtr anp;
	Boolean show_feature;
	ValNodePtr prev = NULL;



	if(caop == NULL || m_loc == NULL || entityID == 0)
		return NULL;
	if(style < COLLECT_HISTORY || style > COLLECT_MD)
		return NULL;
	mbsp = BioseqLockById(SeqLocId(m_loc));
	if(mbsp == NULL)
		return NULL;

	if(mbsp->repr == Seq_repr_seg)
		caop->segloc  = (SeqLocPtr)(mbsp->seq_ext);
	else
		caop->segloc = NULL;

	show_feature = FALSE;
	if(style != COLLECT_HISTORY)
	{
		if(f_order != NULL && g_order != NULL)
		{
			MemCopy((Pointer)(featureOrder), (Pointer)f_order, (size_t)(FEATDEF_ANY* sizeof(Uint1)));
			MemCopy((Pointer)(groupOrder), (Pointer)g_order, (size_t)(FEATDEF_ANY* sizeof(Uint1)));
		}
		else	/*use the default features*/
		{
			if(mbsp->mol == Seq_mol_aa)
			{
				MemSet((Pointer)(featureOrder), 1, (size_t)(FEATDEF_ANY* sizeof(Uint1)));
				MemSet((Pointer)(groupOrder), 1, (size_t)(FEATDEF_ANY* sizeof(Uint1)));
				featureOrder[FEATDEF_BAD] = 0;
				/* featureOrder[FEATDEF_ANY] = 0; */ /* out of bounds */
				featureOrder[FEATDEF_PUB] = 0;
				featureOrder[FEATDEF_source] = 0;
				featureOrder[FEATDEF_NUM] = 0;
				featureOrder[FEATDEF_BIOSRC] = 0;
				featureOrder[FEATDEF_ORG] = 0;
				featureOrder[FEATDEF_CDS] =0;
				featureOrder[FEATDEF_PROT] =0;
			}
			else
			{
				MemSet((Pointer)(featureOrder), 0, (size_t)(FEATDEF_ANY* sizeof(Uint1)));
				MemSet((Pointer)(groupOrder), 0, (size_t)(FEATDEF_ANY* sizeof(Uint1)));
				featureOrder[FEATDEF_Imp_CDS] = 1;
				groupOrder[FEATDEF_Imp_CDS] = 1;
				featureOrder[FEATDEF_CDS] = 1;
				groupOrder[FEATDEF_CDS] = 1;
			}
		}

		csop = caop->csop;
		for(i =0; i<FEATDEF_ANY; ++i)
		{
			if(featureOrder[i] != 0)
			{
				csop->features[i] = TRUE;
				show_feature = TRUE;
			}
			else
				csop->features[i] = FALSE;
		}
	}
	else
		caop->show_mismatch = FALSE;



	if(style == COLLECT_MP)
	{
		if(csop->features[FEATDEF_repeat_region] == FALSE || 
			csop->features[FEATDEF_repeat_unit] == FALSE)
		{
			if(mbsp->repr == Seq_repr_seg || mbsp->repr == Seq_repr_raw 
				|| mbsp->repr == Seq_repr_const)
			{
	
				if(alignment_are_blast_hits(mbsp))
				{
					csop->features[FEATDEF_repeat_region] = TRUE;
					csop->features[FEATDEF_repeat_unit] = TRUE;
					csop->features[FEATDEF_repeat_region] = TRUE;
					csop->features[FEATDEF_repeat_unit] = TRUE;
					caop->show_feature = TRUE;
				}
			}
		} 
		anp_list = collect_master_align_node(caop, m_loc, itemType, entityID);
		if(anp_list == NULL)
		{
			BioseqUnlock(mbsp);
			Message(MSG_ERROR, "Fail to make AlignNode for the master sequence");
			return NULL;
		}
		/* if(caop->map_graphic == FALSE)
		{
			csop->features[FEATDEF_repeat_region] = FALSE;
			csop->features[FEATDEF_repeat_unit] = FALSE;
		} */

	}
	caop->show_feature = show_feature;
	
	
	list = CollectItemForAlignment(m_loc, entityID, 0, caop, take_all_annot);
	if(caop->no_sort == FALSE)
		list = SortAlignNode(list);
	ValNodeLink(&anp_list, list);
	if(style == COLLECT_MD)
	{
		for(list = anp_list; list != NULL; list = list->next)
		{
			if(list->choice != OBJ_SEQANNOT)
			{
				anp = list->data.ptrvalue;
				if(anp != NULL)
					anp->use_seq_ids = TRUE;
			}
		}
	}

		
	if(caop->show_feature)
		SortAlignmentFeature(anp_list, featureOrder, groupOrder);
	align_id_list = get_seqids_with_alignment(mbsp);
	if(align_id_list != NULL)
	{
		add_sequence_alignment_info(align_id_list, anp_list);
		ValNodeFree(align_id_list);
	}
	if(style == COLLECT_MP && caop->flat_insert)
		FlatAlignNode(anp_list);

	BioseqUnlock(mbsp);
	return anp_list;
}



/***************************************************************
*
*	CollAlignFromSeqAnnot(annot, m_loc, featureOrder, groupOrder, 
*	style,graphic)
*
*	collect the AlignNode for Seq-aligns stored in Seq-annot
*	annot: the Seq-annot
*	m_loc: the target sequence
*	left: the offset of the leftmost position
*	featureOrder, groupOrde: the features selected to be displayed together 
*	with alignment
*	style: the style of the display. Only valid for multiple-pairwise 
*	and multiple dimension for now
*	graphic: if TRUE, it is designed to show the display on graphic, 
*	so the mismatch data will be collected. Otherwise, it will not 
*	collect mismatch data
*
****************************************************************/
NLM_EXTERN ValNodePtr CollAlignFromSeqAnnot(SeqAnnotPtr annot, SeqLocPtr m_loc, Uint1Ptr featureOrder, Uint1Ptr groupOrder, Uint1 style, Boolean graphic, Boolean sort, Boolean flat_insert)
{
	Uint2 entityID;

	CollectAlignOption ca_option;
	CollectSeqOption cs_option;
	Int2 label_size = 32;

	if(annot->type !=2)	/*it is not an alignment*/
		return NULL;
		
	entityID = ObjMgrRegister(OBJ_SEQANNOT, (Pointer)annot);
	if(entityID == 0)
		return NULL;

		
	if(style == COLLECT_MP || style == COLLECT_MD)
	{
		set_option_for_collect_align(&ca_option, label_size, style);
		cs_option.nointerval = FALSE;
		cs_option.slabel_format = PRINTID_TEXTID_ACCESSION;
		MemSet((Pointer)&(cs_option.flabel_format), OM_LABEL_CONTENT, (size_t)FEATDEF_ANY * sizeof(Uint1));
		cs_option.label_size = label_size;
		cs_option.seglevels = 0;
		ca_option.csop = &cs_option;
		ca_option.no_sort = 1- sort;
		if(style == COLLECT_MP && flat_insert)
			ca_option.flat_insert = TRUE;
		else
			ca_option.flat_insert = FALSE;

		ca_option.only_history = FALSE;
		if(!graphic)
		{
			ca_option.show_mismatch = FALSE;
			ca_option.align_num = -1;
		}
		return collect_anpnode_with_option(&ca_option, m_loc, entityID, style, OBJ_SEQALIGN, featureOrder, groupOrder, TRUE);
	}
	else
		return NULL;


}
	
/*###################################################################
#
#	functions related to collect Seq-feat, Bioseq and Bioseq-seg
#
###################################################################*/


static void get_mapmarker_info(UserObjectPtr uop, Uint4Ptr extra, Uint2Ptr bin_order)
{
	ObjectIdPtr oip;
	Int4 val;
	Uint4 temp;
	UserFieldPtr ufp;

	temp = *extra;

	while(uop)
	{
		oip = uop->type;
		if(oip && oip->str != NULL)
		{
			if(StringCmp(oip->str, "MapMarkerInfo") == 0)
			{
				ufp = uop->data;
				while(ufp)
				{
					oip = ufp->label;
					if(StringCmp(oip->str, "Marker Type") == 0)
					{
						if(ufp->choice == 2)
						{
							val = ufp->data.intvalue;
							switch(val)
							{
								case FRAME_WORK:
									temp |= EXTRA_FRAME_WORK;
									break;
								case RECMIN:
									temp |= EXTRA_RECMIN;
									break;
								case LIKELY:
									temp |= EXTRA_LIKELY;
									break;
								case MDUP:
									temp |= EXTRA_MDUP;
									break;
								case DUP:
									temp |= EXTRA_DUP;
									break;

								case CONTIG_STS:
									temp |= EXTRA_CONTIG_STS;
									break;
								default:
									break;
							}
							*extra = temp;
						}
					}
					if(StringCmp(oip->str, "Bin Order") == 0)
					{
						if(ufp->choice == 2)
							*bin_order = (Uint2)(ufp->data.intvalue);
					}

					if(StringCmp(oip->str, "Marker Category") == 0)
					{
						if(ufp->choice == 2)
						{
							val = ufp->data.intvalue;
							switch(val)
							{
								case EG_YAC_END:
									temp |= EXTRA_YAC_END;
									break;
								case EG_RANDOME:
									temp |= EXTRA_RANDOM;
									break;
	
								case EG_GENETIC:
									temp |= EXTRA_GENETIC;
									break;
	
								case EG_GENE:
									temp |= EXTRA_GENE;
									break;
								case EG_EST:
									temp |= EXTRA_EST;
									break;
								case EG_MISC:
									temp |= EXTRA_MISC;
									break;
								default:
									break;
							}
						}
					}
					ufp = ufp->next;
				}
			}
			else if(StringCmp(oip->str, "Marker Category") == 0)
			{
				ufp = uop->data;
				while(ufp)
				{
					if(ufp->choice == 2)
					{
						val = ufp->data.intvalue;
						switch(val)
						{
							case EG_YAC_END:
								temp |= EXTRA_YAC_END;
								break;
							case EG_RANDOME:
								temp |= EXTRA_RANDOM;
								break;

							case EG_GENETIC:
								temp |= EXTRA_GENETIC;
								break;

							case EG_GENE:
								temp |= EXTRA_GENE;
								break;
							case EG_EST:
								temp |= EXTRA_EST;
								break;
							case EG_MISC:
								temp |= EXTRA_MISC;
								break;
							default:
								break;
						}
					}
					ufp = ufp->next;
				}
			}
		}
		uop = uop->next;
	}
	*extra = temp;
}
	

/*******************************************************************
*
*	ck_seqfeat_extra: check if there is  extra data, such as 
*	Genbank accessions assocated with a GeneRef or Medlines 
*	associated with a Seq-feat
*
*******************************************************************/
NLM_EXTERN Uint4 ck_seqfeat_extra(SeqFeatPtr sfp)
{
	GeneRefPtr grp;
	ValNodePtr db;
	DbtagPtr db_tag;
	ValNodePtr cit;
	ValNodePtr pub;
	Boolean has_gb = FALSE, has_med = FALSE;
	Uint4 extra_data = 0;
	

	if(sfp->data.choice == 1)
	{
		grp = sfp->data.value.ptrvalue;

		for(db = grp->db; db!=NULL; db = db->next)
		{
			db_tag = db->data.ptrvalue;
			if(StringICmp(db_tag->db, "GenBank") == 0)
			{
				extra_data |= EXTRA_GENBANK;
				break;
			}
		}
	}
	for(cit = sfp->cit; !has_med && cit!=NULL; cit = cit->next)
	{
		if(cit->choice == 3)
			has_med = TRUE;
		if(cit->choice ==1)
		{
			pub = (ValNodePtr)(cit->data.ptrvalue);
			while(pub)
			{
				if(pub->choice == PUB_Muid)
				{
					has_med = TRUE;
					break;
				}
				pub = pub->next;
			}
		}
	}

	if(has_med)
		extra_data |= EXTRA_MEDLINE;
	return extra_data;
}
		
			 
		
/******************************************************************
*
*	get_bin_order(sfp)
*	get the 1000:1 bin data()
*
*******************************************************************/
static Uint2 get_bin_order(SeqFeatPtr sfp)
{
	GeneRefPtr grp;
	ValNodePtr db;
	DbtagPtr db_tag;
	ObjectIdPtr oip;

	if(sfp->data.choice != 1)
		return 0;
	grp = sfp->data.value.ptrvalue;
	if(grp == NULL)
		return 0;

	for(db = grp->db; db != NULL; db = db->next)
	{
		db_tag = db->data.ptrvalue;
		if(db_tag != NULL && StringCmp(db_tag->db, "1000:1 Bin") ==0)
		{
			oip = db_tag->tag;
			return (Uint2)(oip->id);
		}
	}

	return 0;
}
	
		
static Boolean load_annot_name(SeqAnnotPtr annot, CharPtr annot_db)
{
	ValNodePtr desc;
	CharPtr name, title;
	Int4 len;

	annot_db[0] = '\0';
	if(annot == NULL)
		return FALSE;
	name = NULL;
	title = NULL;
	for(desc = annot->desc; desc != NULL; desc = desc->next)
	{
		if(desc->choice == Annot_descr_name)
		{
			if(name == NULL)
				name = (CharPtr)(desc->data.ptrvalue);
		}
		if(desc->choice == Annot_descr_title)
		{
			if(title == NULL)
				title = (CharPtr)(desc->data.ptrvalue);
		}
	}

	if(name != NULL)
		StringNCpy_0(annot_db, name, 20);
	len = StringLen(annot_db);
	if(title != NULL && len < 19)
	{
		StringCat(annot_db, ":");
		++len;
		StringNCpy_0(annot_db+len, title, 20-len);
	}

	return (annot_db[0] != '\0');
}


static Boolean check_feature_for_landmark(CharPtr label, GeneDataPtr gdata, SeqFeatPtr sfp, GatherContextPtr gcp, Uint2 priority)
{
	Boolean found;
	GeneDataPtr c_gdp;

	if(gdata == NULL || sfp == NULL)
		return FALSE;
	found = FALSE;
	c_gdp = NULL;
	if(label[0] != '\0')
	{
		for(c_gdp = gdata; c_gdp != NULL; c_gdp = c_gdp->next)
		{
			if(StringICmp(c_gdp->symbol, label) == 0)
			{
				found = TRUE;
				break;
			}
		}
	}
					
	if(!found && sfp->data.choice == 1)
	{
		for(c_gdp = gdata; c_gdp != NULL; c_gdp = c_gdp->next)
		{
			if(check_landmark(sfp, c_gdp->symbol))
			{
				found = TRUE;
				break;
			}
		}
	}

	if(!found)
		return FALSE;
	
	if(c_gdp->priority == 0 || priority < c_gdp->priority)
	{
		c_gdp->entityID = gcp->entityID;
		c_gdp->itemID = gcp->itemID;
		c_gdp->itemType = gcp->thistype;
		c_gdp->priority = priority;
	}

	StringCpy(label, c_gdp->symbol);
	return TRUE;
}



/*******************************************************************
*
*	collseqfunc( )
*	callback function for collecting sequence related data in 
*	gather, such as segments, features
*
*******************************************************************/
static Boolean collseqfunc(GatherContextPtr gcp)
{
	SeqFeatPtr sfp;
	SeqLocPtr slp;
	BioseqPtr bsp;
	CollectHeaderPtr chp;
	FeatNodePtr fnp;
	CollectSeqOptionPtr csop;
	ObjMgrTypePtr   omtp;
	
	UserObjectPtr uop;
	UserFieldPtr ufp;
	GatherRangePtr grp;
	IvalNodePtr inp;
	Uint1 band;
	Int2 i;
	Int2 label_size;
	ValNodePtr delta_node;
	Boolean is_gap;
	SeqLitPtr slitp;


	chp= (CollectHeaderPtr)(gcp->userdata);
	chp->subtype = 0;
	chp->thislabel[0] = '\0';
	chp->ftype [0] = '\0';
	csop = chp->csop;
	label_size = MIN(100, (Int2)(csop->label_size));
		
		
	switch (gcp->thistype)
	{
		case OBJ_SEQANNOT:	/*for the cytogenetic map, skip certain 
						Seq-annot*/
			chp->annotDB[0] = '\0';
			chp->is_lod_score = is_lod_score_annot((SeqAnnotPtr)(gcp->thisitem));
			load_annot_name((SeqAnnotPtr)(gcp->thisitem), chp->annotDB);
			if(csop->bsp_type == CYTO_MAP)
			{
				if(!annot_is_user_defined((SeqAnnotPtr)(gcp->thisitem)))
					chp->skip_feature = TRUE;
				else
					chp->skip_feature = FALSE;
			}
			break;
				
		case OBJ_BIOSEQ_SEG:
			slp = (SeqLocPtr)(gcp->thisitem);
			if(is_map_segment(slp))	/*not very reliable*/
				return TRUE;
			if(chp->maybe_mapid != NULL)
				if(SeqIdMatch(chp->maybe_mapid, SeqLocId(slp)))
					return TRUE;
			fnp = CreateFeatNode (&(chp->features), &(chp->prev_feat), gcp->thistype, gcp->itemID, gcp->entityID, 0);
			MemCopy(&(fnp->extremes), &(gcp->extremes), sizeof(GatherRange));
			if(slp->choice == SEQLOC_NULL || slp->choice == SEQLOC_EMPTY)
				fnp->follower = TRUE;	/*used to present the empty Seq-loc*/
			else
			{
				if(MuskSeqIdWrite (SeqLocId(slp), chp->thislabel, label_size, csop->slabel_format, TRUE, TRUE))
					fnp->label = StringSave(chp->thislabel);
			}
			break;
		case OBJ_BIOSEQ_DELTA:
			delta_node = (ValNodePtr)(gcp->thisitem);
			is_gap = FALSE;
			chp->thislabel[0] = '\0';
			if(delta_node->choice ==1)
			{
				slp = delta_node->data.ptrvalue;
				if(slp->choice == SEQLOC_NULL || slp->choice == SEQLOC_EMPTY)
					is_gap = TRUE;
				else
					MuskSeqIdWrite (SeqLocId(slp), chp->thislabel, label_size, csop->slabel_format, TRUE, TRUE);

			}
			else
			{
				slitp = delta_node->data.ptrvalue;
				if(slitp->length == 0 || slitp->seq_data == NULL)
				{
					is_gap = TRUE;
					if(slitp->length > 0)
						return TRUE;
				}
			}

			fnp = CreateFeatNode (&(chp->features), &(chp->prev_feat), gcp->thistype, gcp->itemID, gcp
->entityID, 0);
			MemCopy(&(fnp->extremes), &(gcp->extremes), sizeof(GatherRange));
			if(is_gap)
				fnp->follower = TRUE;
			else if(chp->thislabel[0] != '\0')
				fnp->label = StringSave(chp->thislabel);
			break;
		
		case OBJ_BIOSEQ:
			fnp = CreateFeatNode (&(chp->features), &(chp->prev_feat), gcp->thistype, gcp->itemID, gcp->entityID, 0);
			MemCopy(&(fnp->extremes), &(gcp->extremes), sizeof(GatherRange));
			bsp = (BioseqPtr) gcp->thisitem;
			if(MuskSeqIdWrite(bsp->id, chp->thislabel, label_size, csop->slabel_format, TRUE, FALSE))
				fnp->label = StringSave(chp->thislabel);
			break;
			
		case OBJ_BIOSEQ_MAPFEAT:
		case OBJ_SEQFEAT:
			if(gcp->thistype == OBJ_SEQFEAT && chp->skip_feature)
				return TRUE;
			sfp = (SeqFeatPtr) gcp->thisitem;
			/* if(gcp->thistype == OBJ_SEQFEAT)
			{
				if(chp->filter_level == gcp->seglevel +1)
					return TRUE;
			} */
			omtp = ObjMgrTypeFind (chp->omp, OBJ_SEQFEAT, NULL, NULL);
			if(omtp == NULL)
				return TRUE;
			if (omtp->subtypefunc != NULL)
				chp->subtype = (*(omtp->subtypefunc)) (gcp->thisitem);
			else
				chp->subtype = 0;
			if(gcp->thistype == OBJ_SEQFEAT && 
				csop->features[chp->subtype] == 0)	/*filter unwanted features*/
				return TRUE;
				
			/*tolerate the unknown band*/
			/*
			if(sfp->data.choice == 14 && gcp->thistype == OBJ_BIOSEQ_MAPFEAT)
			{
				uop = sfp->data.value.ptrvalue;
				band = get_band_type(uop);
				if(band == 0)
					return TRUE;
			}
			*/
			fnp = CreateFeatNode (&(chp->features), &(chp->prev_feat), gcp->thistype, gcp->itemID, gcp->entityID, chp->subtype);

			/*special collection for the LOD scores*/
			if(chp->is_lod_score && gcp->thistype == OBJ_SEQFEAT)	/*it is the LOD score data*/
			{
				fnp->extra_data = EXTRA_LOD_SCORE;
				fnp->bin_order = GetLODScoreBitValue(sfp);
				StringCpy(fnp->annotDB, chp->annotDB);
				MemCopy(&(fnp->extremes), &(gcp->extremes), sizeof(GatherRange));
				return TRUE;
			}

			fnp->has_product = (sfp->product !=NULL);
			fnp->extra_data = ck_seqfeat_extra(sfp);	/*extra data associated with a Gene-ref*/
			get_mapmarker_info(sfp->ext, &(fnp->extra_data), &(fnp->bin_order));
			if(fnp->bin_order == 0)	/*just as a backup*/
				fnp->bin_order = get_bin_order(sfp);
			if(gcp->thistype == OBJ_SEQFEAT && chp->annotDB[0] != '\0')
				StringCpy(fnp->annotDB, chp->annotDB);
			else
				fnp->annotDB[0]= '\0';
			MemCopy(&(fnp->extremes), &(gcp->extremes), sizeof(GatherRange));

			/*special collection for cytogenetic band*/			
			if(sfp->data.choice == 14 && gcp->thistype == OBJ_BIOSEQ_MAPFEAT)
			{
				uop = sfp->data.value.ptrvalue;
				band = get_band_type(uop);
				fnp->band = band;
				fnp->label = StringSave(get_band_name(uop));
				if(band < POINT)	/*for flybase*/
				{
					for(ufp = uop->data; ufp!=NULL; ufp=ufp->next)
					{
						if(is_label_match(ufp->label, "Subdivision"))
							fnp->pos_label = StringSave(ufp->data.ptrvalue);
					}	
				}
			}
			else	/*for non-cyto band*/
			{
				/* if((gcp->thistype == OBJ_BIOSEQ_MAPFEAT) || collect_feature_label(csop->flabel_format[chp->subtype])) */
				/* check the landmark genes*/

				if(collect_feature_label(csop->flabel_format[chp->subtype]))
				{
					if(omtp->labelfunc !=NULL)
						(*(omtp->labelfunc)) (gcp->thisitem, chp->thislabel, label_size, OM_LABEL_CONTENT);
						fnp->landmark = check_feature_for_landmark(chp->thislabel, chp->gdata, sfp, gcp, chp->priority);
					if(fnp->landmark == FALSE && omtp->labelfunc != NULL && 
						csop->flabel_format[chp->subtype] != OM_LABEL_CONTENT)
						(*(omtp->labelfunc)) (gcp->thisitem, chp->thislabel, label_size, csop->flabel_format[chp->subtype]);

				}					

				if(chp->thislabel[0] != '\0')
					fnp->label = StringSave(chp->thislabel);
				slp = sfp->location;	/*collect the intervals*/
				if(slp->choice == SEQLOC_PACKED_PNT || csop->nointerval == FALSE)
				{
					grp = gcp->rdp;
					for(i=0; (grp!=NULL) && i<gcp->num_interval; ++i)
					{
						inp = MemNew(sizeof(IvalNode));
						MemCopy(&(inp->gr), grp, sizeof(GatherRange));
						ValNodeAddPointer(&(fnp->interval), (Uint1)(i+1), (Pointer)inp);
						++grp;
					}
				}
			}
			break;
		default:
			break;
	}
	
	return TRUE;
}


static Boolean ignore_feature(BoolPtr f_list)
{
	Int2 i;

	if(f_list == NULL)
		return TRUE;
	for(i = 0; i<FEATDEF_ANY; ++i)
		if(f_list[i])
			return FALSE;
	return TRUE;
}
			
/***********************************************************************
*
*	CollectItemForSeqLoc(slp, entityID, left, is_aa, csop)
*	Collect sequences, features for a Seq-loc
*	slp: the target Seq-loc
*	entityID: the top level entityID for the current sequence
*	left: the left offset on the graph
*	is_aa: if TRUE, set get_feats_product flag to TRUE
*	csop: the collection option
*
*
***********************************************************************/	
NLM_EXTERN ValNodePtr CollectItemForSeqLocEx(SeqLocPtr slp, Uint2 entityID, Int4 left, Boolean is_aa, SeqIdPtr maybe_mapid, CollectSeqOptionPtr csop, GeneDataPtr gdata, Uint2 priority, Boolean forceSeglevelsTo1)
{
	GatherScope gs;
	CollectHeader ch;

	if(slp == NULL || entityID == 0 || csop == NULL)
		return NULL;
	ch.omp = ObjMgrGet();	/*set up the options*/
	ch.features = NULL;
	ch.csop = csop;
	ch.maybe_mapid = maybe_mapid;
	ch.filter_level = csop->filter_level;
	ch.gdata = gdata;
	ch.priority = priority;
	ch.skip_feature = FALSE;
	ch.prev_feat = NULL;
	ch.prev_align = NULL;
	ch.index = 0;
	ch.annotDB[0] = '\0';
	ch.is_lod_score = FALSE;
	

	MemSet((Pointer)&gs, 0, sizeof (GatherScope));
	gs.get_feats_location = TRUE;
	gs.get_feats_product = is_aa;
	MemSet((Pointer)(gs.ignore), (int)TRUE, (size_t)(OBJ_MAX)*sizeof(Boolean));

	gs.ignore[OBJ_SEQENTRY] = FALSE;
	gs.ignore[OBJ_BIOSEQ_SEG] = FALSE;
	gs.ignore[OBJ_BIOSEQ] = FALSE;
	gs.ignore[OBJ_BIOSEQ_MAPFEAT] = FALSE;
	gs.ignore[OBJ_BIOSEQ_DELTA] = FALSE;
	if(!ignore_feature(csop->features))
	{
		gs.ignore[OBJ_SEQANNOT] = FALSE;
		gs.ignore[OBJ_SEQFEAT] = FALSE;
	}

	gs.nointervals = csop->nointerval;
	gs.seglevels = csop->seglevels;
	/*gs.stop_on_annot = TRUE;*/
	if(gs.seglevels == 0)
	{
		gs.ignore_top = FALSE;
		gs.stop_on_annot = FALSE;
		/* gs.ignore_top = FALSE;
		gs.stop_on_annot = TRUE; */
	}
	else if (forceSeglevelsTo1)
	{
		gs.ignore_top = TRUE; /* JK */
		gs.stop_on_annot = FALSE; /* JK */
	}
	else
	{
		gs.ignore_top = FALSE;
		gs.stop_on_annot = TRUE;
	}
	gs.currlevel = 0;
	gs.split_packed_pnt = TRUE;


	for(; slp!= NULL; slp = slp->next)
	{
		gs.offset = left;
		gs.target = slp;
		GatherEntity(entityID, (Pointer)(&ch), collseqfunc, &gs);
		left += SeqLocLen(slp);
	}
	return ch.features;
}

NLM_EXTERN ValNodePtr CollectItemForSeqLoc(SeqLocPtr slp, Uint2 entityID, Int4 left, Boolean is_aa, SeqIdPtr maybe_mapid, CollectSeqOptionPtr csop, GeneDataPtr gdata, Uint2 priority)
{
	return CollectItemForSeqLocEx(slp, entityID, left, is_aa, maybe_mapid, csop, gdata, priority, FALSE);
}

static Uint1 is_segmap_align_annot(SeqAnnotPtr annot)
{
	UserObjectPtr uop;
	ValNodePtr desc;
	ObjectIdPtr oip;
	UserFieldPtr ufp;
	
	if(annot == NULL)
		return 0;
	if(annot->type != 2)
		return 0;
	if(is_annot_for_hist_alignment(annot))
		return 0;

	desc =annot->desc;
	while(desc)
	{
		if(desc->choice == Annot_descr_user)
		{
			uop = desc->data.ptrvalue;
			if(uop->type)
			{
				oip = uop->type;
				if(StringCmp(oip->str, "SegMap STS Alignment") == 0)
				{
					ufp = uop->data;
					if(ufp && ufp->choice == 2)
						return (Uint1)(ufp->data.intvalue);
				}
			}
		}
		desc = desc->next;
	}
	return 0;
}

static GatherRangePtr create_gr_data(SeqAlignPtr align, SeqLocPtr m_loc, Int4 m_left)
{
	Int2 i, num;
	SeqAlignPtr curr;
	GatherRangePtr grp;

	for(num = 0, curr = align; curr!= NULL; curr = curr->next)
		++num;
	if( num == 0)
		return NULL;

	grp = MemNew((size_t)num * sizeof(GatherRange));
	for(i =0, curr = align; curr != NULL; curr = curr->next, ++i)
	{
		if(!SeqLocOffset (m_loc, curr->bounds, &(grp[i]), m_left))
		{
			grp[i].left = -1;
			grp[i].right = -1;
		}
	}
	return grp;
}

static void add_int_with_order(ValNodePtr PNTR head, Uint1 type, Int4 pos)
{
	ValNodePtr prev, curr;
	ValNodePtr cnew;

	if(*head == NULL)
		ValNodeAddInt(head, type, pos);
	else
	{
		prev = NULL;
		curr = *head;
		cnew = ValNodeNew(NULL);
		cnew->choice = type;
		cnew->data.intvalue = pos;
		while(curr)
		{
			if(pos < curr->data.intvalue)
			{
				if(prev == NULL)
					*head = cnew;
				else
					prev->next = cnew;
				cnew->next = curr;
				return;
			}

			prev = curr;
			curr = curr->next;
		}
		if(prev != NULL)
			prev->next = cnew;
	}
}
					
	
					
static void load_open_close_sts_mark(SeqAlignPtr halign, ValNodePtr anp_list, Uint1 annot_type, SeqLocPtr m_loc, Int4 m_left)
{
	SeqAlignPtr align;
	AlignNodePtr anp;
	AlignSegPtr asp;
	SeqIdPtr sip;
	SeqLocPtr slp;
	GatherRange gr;
	GatherRangePtr grp;
	Int4 start, stop;
	Uint1 strand;
	SeqInt sint;
	SeqLoc sl;
	Boolean collected = FALSE;
	StdSegPtr ssp;
	Int4 e_left, e_right;
	Int2 i;
	
	grp = create_gr_data(halign, m_loc, m_left);
	if(grp == NULL)
		return;
	while(anp_list)
	{
		if(anp_list->choice != OBJ_SEQANNOT)
		{
			anp = anp_list->data.ptrvalue;
			sip = anp->sip;
			if(!SeqIdForSameBioseq(sip, SeqLocId(m_loc)))
			{
			if(anp->seqpos < 0)	/*minus strand*/
			{
				stop = ABS(anp->seqpos);
				start = stop - (anp->extremes.right - anp->extremes.left);
				strand = Seq_strand_minus;
			}
			else
			{
				start = anp->seqpos;
				stop = start + (anp->extremes.right - anp->extremes.left);
				strand = Seq_strand_plus;
			}

			sint.from = start;
			sint.to = stop;
			sint.strand = strand;
			sint.id = sip;
			sl.choice = SEQLOC_INT;
			sl.data.ptrvalue = &sint;
			sl.next = NULL;

			e_left = anp->extremes.left;
			e_right = anp->extremes.right;
			asp = anp->segs;
			for(align = halign, i=0; align != NULL; align = align->next, ++i)
			{
				if(grp[i].left != -1)
				{
					if(!(e_left > grp[i].right || e_right < grp[i].left))
					{
						for(ssp = align->segs; ssp != NULL; ssp = ssp->next)
						{
							/*slp = ssp->loc->next;*/
							slp = ssp->loc;
							while(slp)
							{
								if(SeqIdMatch(SeqLocId(slp), sip))
									break;
								else
									slp = slp->next;
							}
					
							if(slp != NULL)
							{
								if(SeqLocOffset (&sl, slp, &gr, e_left))
								{
									if(asp == NULL)
									{
										asp = MemNew(sizeof(AlignSeg));
										MemCopy(&(asp->gr), &(anp->extremes), sizeof(GatherRange));
										asp->type = REG_SEG;
										anp->segs = asp;
									}
											
									/*ValNodeAddInt(&(asp->mismatch), annot_type, gr.left);*/
									add_int_with_order(&(asp->mismatch), annot_type, gr.left);
									collected = TRUE;
								}
							}
				
						}
					}
					/*if(grp[i].left> e_right)
						break;*/
				}
			}
			}
		}
		anp_list = anp_list->next;
	}
	MemFree(grp);
	
}
					
					
typedef struct segmap_data{
	ValNodePtr anp_list;
	SeqLocPtr m_loc;
	Int4 left;
}SegMapData, PNTR SegMapDataPtr;

static Boolean coll_segmap_func(GatherContextPtr gcp)
{
	ValNodePtr anp_list;
	SeqAnnotPtr annot;
	Uint1 annot_type;
	SeqAlignPtr align;
	SegMapDataPtr smdp;
	
	smdp = (SegMapDataPtr)(gcp->userdata);
	if(smdp == NULL || smdp->anp_list == NULL || smdp->m_loc == NULL)
		return FALSE;
	anp_list = smdp->anp_list;

	annot = (SeqAnnotPtr)(gcp->thisitem);
	if(annot == NULL || annot->type != 2)
		return TRUE;
	annot_type = is_segmap_align_annot(annot);
	if(annot_type == 0)
		return TRUE;
	align = annot->data;
	load_open_close_sts_mark(align, anp_list, annot_type, smdp->m_loc, smdp->left);
	
	return TRUE;
}


/*******************************************************************
*
*	void CollectSegMapSTSAlign( entityID, anp_list)
*	look for the sts alignment from segmap stored as Seq-annot in 
*	in entityID. Add the alignment as the mismatch marker in the 
*	AlignSeg of the anp_list
*
*******************************************************************/
NLM_EXTERN void CollectSegMapSTSAlign( Uint2 entityID, ValNodePtr anp_list, SeqLocPtr m_loc, Int4 m_left)
{
	GatherScope gs;
	SegMapData smd;

	if(entityID == 0 || anp_list == NULL)
		return;

	MemSet((Pointer)&gs, 0, sizeof (GatherScope));
	MemSet((Pointer)(gs.ignore), (int)TRUE, (size_t)(OBJ_MAX)*sizeof(Boolean));
	gs.ignore[OBJ_SEQANNOT] = FALSE;

	smd.anp_list = anp_list;
	smd.m_loc = m_loc;
	smd.left = m_left;
	GatherEntity(entityID, (Pointer)(&smd), coll_segmap_func, &gs);
}


/*#####################################################################
#
#	functions related to the layout for FeatNode
#
######################################################################*/



/***********************************************************************
*  SortFeatNode(list)
*	HeapSort the FeatNode list to the accending order of fnp->left
*	return the head of the sorted list
*	
************************************************************************/
static Uint1Ptr featureSortOrder;
static Uint1Ptr groupSortOrder;

static int FeatNodeIntervalCompare (ValNodePtr vnp1, ValNodePtr vnp2)

{
  GatherRangePtr  grp1, grp2;

  while (vnp1 != NULL && vnp2 != NULL) {
    grp1 = (GatherRangePtr) vnp1->data.ptrvalue;
    grp2 = (GatherRangePtr) vnp2->data.ptrvalue;
    if (grp1 != NULL && grp2 != NULL) {
      /*
      if (grp1->left > grp2->left) {
        return 1;
      } else if (grp1->left < grp2->left) {
        return -1;
      } else if (grp1->right > grp2->right) {
        return 1;
      } else if (grp1->right < grp2->right) {
        return -1;
      }
      */
      if (grp1->left > grp2->left) {
        return -1;
      } else if (grp1->left < grp2->left) {
        return 1;
      } else if (grp1->right > grp2->right) {
        return -1;
      } else if (grp1->right < grp2->right) {
        return 1;
      }
    }
    vnp1 = vnp1->next;
    vnp2 = vnp2->next;
  }
  if (vnp1 != NULL) {
    return -1;
  } else if (vnp2 != NULL) {
    return 1;
  } else {
    return 0;
  }
}

static int LIBCALLBACK FeatNodeCompProc (VoidPtr ptr1, VoidPtr ptr2)
{
  FeatNodePtr  fnp1;
  FeatNodePtr  fnp2;
  ValNodePtr   vnp1;
  ValNodePtr   vnp2;
  GatherRange	gr1, gr2;
  Uint1 group1, group2;
  Uint1 order1, order2;
  int rsult;

  if (ptr1 != NULL && ptr2 != NULL) {
    vnp1 = *((ValNodePtr PNTR) ptr1);
    vnp2 = *((ValNodePtr PNTR) ptr2);
    if (vnp1 != NULL && vnp2 != NULL) {
      fnp1 = (FeatNodePtr) vnp1->data.ptrvalue;
      fnp2 = (FeatNodePtr) vnp2->data.ptrvalue;
      if (fnp1 != NULL && fnp2 != NULL) {
	gr1 = fnp1->extremes;
	gr2 = fnp2->extremes;
        /*
        if (gr1.left > gr2.left) {
          return 1;
        } else if (gr1.left < gr2.left) {
          return -1;
        } else if (gr1.right > gr2.right) {
          return 1;
        } else if (gr1.right < gr2.right) {
          return -1;
        } else */
        if ((rsult = FeatNodeIntervalCompare (fnp1->interval, fnp2->interval)) != 0) {
          return rsult;
        } else {
	  if(featureSortOrder == NULL || groupSortOrder == NULL)
          	return 0;
	  else
	  {
		group1 = groupSortOrder[fnp1->feattype];
		group2 = groupSortOrder[fnp2->feattype];
		if(group1 !=group2)
			return -1;
		order1 = featureSortOrder[fnp1->feattype];
		order2 = featureSortOrder[fnp2->feattype];
		if(order1 < order2)
			return -1;
		if(order1 > order2)
			return 1;
		return 0;
	  }
        }
      } else {
        return 0;
      }
    } else {
      return 0;
    }
  } else {
    return 0;
  }
}




/***********************************************************************
*
*	SortFeatNode(list)
*	sort a list of FeatNode to the ascending order of (extremes.left, 
*	extremes.right)
*
**********************************************************************/

NLM_EXTERN ValNodePtr SortFeatNode(ValNodePtr fnp_list, Uint1Ptr featureOrder, Uint1Ptr groupOrder)
{
	featureSortOrder = featureOrder;
	groupSortOrder = groupOrder;
	return SortValNode(fnp_list, FeatNodeCompProc);
}


static int LIBCALLBACK AlignNodeCompProc (VoidPtr ptr1, VoidPtr ptr2)
{
  AlignNodePtr  anp1, anp2;
  ValNodePtr   vnp1;
  ValNodePtr   vnp2;
  GatherRange	gr1, gr2;

  if (ptr1 != NULL && ptr2 != NULL) {
    vnp1 = *((ValNodePtr PNTR) ptr1);
    vnp2 = *((ValNodePtr PNTR) ptr2);
    if (vnp1 != NULL && vnp2 != NULL) {
      anp1 = (AlignNodePtr) vnp1->data.ptrvalue;
      anp2 = (AlignNodePtr) vnp2->data.ptrvalue;
      if (anp1 != NULL && anp2 != NULL) {
	gr1 = anp1->extremes;
	gr2 = anp2->extremes;
	/* len1 = anp1->extremes.right - anp1->extremes.left;
	len2 = anp2->extremes.right - anp2->extremes.left;
        if(len1 > len2)
          return -1;
        else if(len1 < len2)
          return 1; */

        if (gr1.left > gr2.left) {
          return 1;
        } else if (gr1.left < gr2.left) {
          return -1;
        } else if (gr1.right < gr2.right) {
          return 1;
        } else if (gr1.right > gr2.right) {
          return -1;
        } else {
          return 0;
        }
      } else {
        return 0;
      }
    } else {
      return 0;
    }
  } else {
    return 0;
  }
}

/*sort to make the display showing the alignment that are 
* consistuent of the master sequence first
*/
static ValNodePtr modify_align_node_block(ValNodePtr anp_list)
{
	ValNodePtr block_list = NULL;
	ValNodePtr curr, next, prev = NULL;
	AlignNodePtr anp;

	if(anp_list == NULL)
		return NULL;

	curr = anp_list;
	while(curr)
	{
		next = curr->next;
		anp = curr->data.ptrvalue;
		if(anp->blocks != NULL)
		{
			if(prev == NULL)
				anp_list = curr->next;
			else
				prev->next = curr->next;
			curr->next = NULL;
			ValNodeLink(&block_list, curr);
		}
		else
			prev = curr;
		curr = next;
	}

	if(block_list == NULL)
		return anp_list;
	else
	{
		ValNodeLink(&block_list, anp_list);
		return block_list;
	}
}

		

/***********************************************************************
*
*	SortAlignNode(anp_list)
*	sort a list of AlignNode to the ascending order of (extremes.left, 
*	extremes.right)
*
**********************************************************************/
NLM_EXTERN ValNodePtr SortAlignNode(ValNodePtr anp_list)
{
	ValNodePtr list, curr, prev, last, next;
	ValNodePtr head;

	if(anp_list == NULL)
		return NULL;
	list = anp_list;
	prev = NULL;
	head = NULL;
	while(list != NULL)
	{
		if(prev != NULL)
			prev->next = list;
		while(list && list->choice == OBJ_SEQANNOT)
		{
			if(head == NULL)
				head = list;
			prev = list;
			list = list->next;
		}
		if(list != NULL)
		{
			curr = list;
			last = NULL;
			while(curr && curr->choice != OBJ_SEQANNOT)
			{
				last = curr;
				curr = curr->next;
			}
			next = last->next;
			last->next = NULL;
			list = SortValNode(list, AlignNodeCompProc);
			list = modify_align_node_block(list);
			if(prev == NULL)
				head = 	list;
			else
				prev->next = list;
			while(list->next != NULL)
				list = list->next;
			prev = list;
			list = next;
		}
	}

	return head;
}



/*#######################################################################
#
#	function related to Layout of AlignNode
#
########################################################################*/


/***********************************************************************
*
*	find_insert_ypos(left, seglen, ins, l_bound, r_bound, p_pos, space
*	num)
*	find the level for placing the insertions. Used in both the layout
*	for text and graphic
*	left: to store the left-most position calculated for an insertion
*	seglen: length of the insertion
*	ins: the position for insertions
*	l_bound: the leftmost position in the current line
*	r_bound: the rightmost position in the current line
*	p_pos: position for storing all the layout info
*	num: number of elements in p_pos
*	return the current level found for an insertion
*
***********************************************************************/
NLM_EXTERN Int2 find_insert_ypos(Int4Ptr left, Int4 seglen, Int4 ins, Int4 l_bound, Int4 r_bound, Int4Ptr p_pos, Int4 space, Int2 num)
{
 	Int2 i =0;
	Int4 start, stop;

	--seglen;
	*left = MAX(l_bound, (ins-seglen));
	start = *left;
        for(i =0; i<num; ++i)
	{
		if(p_pos[i] == 0)
		{
			p_pos[i] = (*left + seglen);
             		return i;
		}

		if(ins > (p_pos[i]+space))
		{
			start = (*left);
			start +=MAX(0, (seglen - (ins - (p_pos[i]+space))));
			stop = start+seglen;
			if(stop <= r_bound)
			{
				*left = start;
				p_pos[i] = (*left) + seglen;
				return i;
			}
		}


	}

	return -1;
}


		
/************************************************************************
*
*	convert_gdata_for_featnode(gdata, cyto_loc, offset)
*	gdata: the GeneDataPtr
*	cyto_loc: the current location on the cytogenetic map
*	offset: the offset of cyto_loc to the graphic viewer1
*	for human cytogenetic map, the markers are not shown. But for 
*	the markers that were queried, it will display the interval for 
*	gene data
*
************************************************************************/

NLM_EXTERN ValNodePtr convert_gdata_to_featnode (GeneDataPtr gdata, SeqLocPtr cyto_loc, Int4 offset)
{
	ValNodePtr fnp_node;
	ValNodePtr prev;
	FeatNodePtr fnp;
	SeqLocPtr slp;
	SeqPntPtr spp;
	Boolean mod_fuzz;	/*for the old style of FeatNode. To modify the 
					fuzziness on a point*/
	IntFuzzPtr fuzz;
	GatherRange gr;
	SeqFeatPtr sfp;


	if(gdata == NULL || cyto_loc == NULL)
		return NULL;
	fnp_node = NULL;
	prev = NULL;
	while(gdata)
	{
		slp = NULL;
		sfp = gdata->sfp;
		if(sfp != NULL && sfp->location != NULL)
		{
			mod_fuzz = FALSE;
			if(sfp->location->choice == SEQLOC_PNT)
			{
				spp = sfp->location->data.ptrvalue;
				if(spp->fuzz != NULL)
				{
					fuzz = spp->fuzz;
					if(fuzz->choice == 2)	/*range */
					{
						mod_fuzz = TRUE;
						slp = SeqLocIntNew(fuzz->b, fuzz->a, 0, spp->id);
					}
				}
			}
			if(!mod_fuzz)
				slp = sfp->location;
			if(SeqLocOffset(cyto_loc, slp, &gr, offset))
			{
				fnp = CreateFeatNode (&fnp_node, &prev, gdata->itemType, gdata->itemID, gdata->entityID, gdata->subtype);
				MemCopy(&(fnp->extremes), &gr,  sizeof(GatherRange));
				fnp->label = StringSave(gdata->symbol);
				fnp->landmark = TRUE;
				if(gdata->sfp != NULL)
				{
					fnp->extra_data = ck_seqfeat_extra(gdata->sfp);
					get_mapmarker_info(gdata->sfp->ext, &(fnp->extra_data), &(fnp->bin_order));
				}
			}


			if(mod_fuzz)
				SeqLocFree(slp);
		}
		gdata = gdata->next;
	}

	return fnp_node;
}

				
/*
*	for AlignNode that includes insertions, map the insertion 
*	to gaps on the master sequence
*/

/*the data structure for storing the insertion information*/
typedef struct insert_list {
	Int4 max_size;
	Int4 master_pos;	/*position on the master sequence*/
	Boolean  used;	/* this position is acturally at an inserted segment*/
	Boolean after;	/*does the insertion occurs after the master_pos*/
	struct insert_list PNTR next;
}InsertList, PNTR InsertListPtr;


static void load_insertion_list(InsertListPtr PNTR head, Int4 insert_pos, Int4 insert_size, Boolean after)
{
	InsertListPtr curr, prev, ilp;

	prev = NULL;
	curr = *head;
	while(curr)
	{
		if(curr->master_pos == insert_pos)
		{
			curr->max_size = MAX(curr->max_size, insert_size);
			return;
		}
		if(curr->master_pos > insert_pos)
			break;
		else
			prev = curr;
		curr = curr->next;
	}

	ilp = MemNew(sizeof(InsertList));
	ilp->max_size = insert_size;
	ilp->master_pos = insert_pos;
	ilp->next = curr;
	ilp->after = after;

	if(prev == NULL)
		*head = ilp;
	else
		prev->next = ilp;
}

static void add_offset_to_featnode(ValNodePtr fnp_node, Int4 offset)
{
	FeatNodePtr fnp;
	ValNodePtr interval;
	IvalNodePtr inp;

	while(fnp_node)
	{
		fnp = fnp_node->data.ptrvalue;
		fnp->extremes.left += offset;
		fnp->extremes.right += offset;

		for (interval = fnp->interval; interval != NULL; interval = interval->next)
		{
			inp = interval->data.ptrvalue;
			inp->gr.left += offset;
			inp->gr.right += offset;
		}
		fnp_node = fnp_node->next;
	}
}

NLM_EXTERN void AddOffsetToAlignNode(AlignNodePtr anp, Int4 offset)
{
	AlignSegPtr asp;
	AlignBlockPtr abp;

	anp->extremes.left += offset;
	anp->extremes.right += offset;
	for(abp = anp->blocks; abp != NULL; abp = abp->next)
	{
		abp->gr.left += offset;
		abp->gr.right += offset;
	}

	for(asp = anp->segs; asp != NULL; asp = asp->next)
	{
		if(asp->type == INS_SEG)
		{
			asp->ins_pos += offset;
			asp->gr.left += offset;
		}
		else
		{
			asp->gr.left += offset;
			asp->gr.right += offset;
		}
		if(asp->cnp != NULL)
			add_offset_to_featnode(asp->cnp, offset);
	}
}

static ValNodePtr split_feature_interval(ValNodePtr PNTR p_interval, Int4 offset, 
										 Int4 ins_pos, Int4 ins_size)
{
	ValNodePtr interval, next, prev;
	ValNodePtr second_list = NULL;
	IvalNodePtr inp, new_inp;


	prev = NULL;
	interval = *p_interval; 
	while(interval != NULL)
	{
		next = interval->next;
		inp = interval->data.ptrvalue;
		if(inp->gr.right <= ins_pos)
		{
			inp->gr.left += offset;
			inp->gr.right += offset;
			prev = interval;
		}
		else if(inp->gr.left > ins_pos)
		{
			if(prev == NULL)
				*p_interval = NULL;
			else
				prev->next = NULL;
			return interval;
		}
		else
		{	/*there is overlap */
			new_inp = MemNew(sizeof(IvalNode));
			new_inp->gr.strand = inp->gr.strand;
			/* new_inp->gr.right = inp->gr.right + offset + ins_size;
			new_inp->gr.left = ins_pos + offset + ins_size;	 */
			new_inp->gr.right = inp->gr.right;
			new_inp->gr.left = ins_pos +1;

			inp->gr.left += offset;
			inp->gr.right = ins_pos + offset;
			interval->next = NULL;

			ValNodeAddPointer(&second_list, 0, new_inp);
			ValNodeLink(&second_list, next);
			return second_list;
		}
		interval = next;
	}

	return NULL;
}

static ValNodePtr add_insertion_to_featnode(ValNodePtr PNTR pfnp_node, Int4 offset, 
											Int4 ins_pos, Int4 ins_size)
{
	ValNodePtr fnp_node, next, prev;
	ValNodePtr second_list;
	FeatNodePtr fnp, new_fnp;
	ValNodePtr interval;
	IvalNodePtr inp;

	fnp_node = *pfnp_node;
	second_list = NULL;
	prev = NULL;
	while(fnp_node)
	{
		next = fnp_node->next;
		fnp = fnp_node->data.ptrvalue;
		if(fnp->extremes.right <= ins_pos)
		{
			for (interval = fnp->interval; interval != NULL; interval = interval->next)
			{
				inp = interval->data.ptrvalue;
				inp->gr.left += offset;
				inp->gr.right += offset;
			}
			fnp->extremes.left += offset;
			fnp->extremes.right += offset;
			prev = fnp_node;
		}
		else if(fnp->extremes.left > ins_pos)
		{
			/* fnp->extremes.left += offset + ins_size;
			fnp->extremes.right += offset + ins_size;

			for (interval = fnp->interval; interval != NULL; interval = interval->next)
			{
				inp = interval->data.ptrvalue;
				inp->gr.left += offset + ins_size;
				inp->gr.right += offset + ins_size;
			} */

			fnp_node->next = NULL;
			ValNodeLink(&second_list, fnp_node);
			if(prev == NULL)
				*pfnp_node = next;
			else
				prev->next = next;
		}
		else	/*resides between the insertion points, needs to split the featnode*/
		{
			new_fnp = MemNew(sizeof(FeatNode));
			MemCopy((Pointer)new_fnp, fnp, sizeof(FeatNode));
			if(fnp->label != NULL)
				new_fnp->label = StringSave	(fnp->label);
			if(fnp->pos_label != NULL)
				new_fnp->pos_label = StringSave	(fnp->pos_label);
			if(fnp->annotDB[0] != '\0')
				StringCpy(new_fnp->annotDB, fnp->annotDB);
			/* new_fnp->extremes.right = fnp->extremes.right + offset + ins_size;
			new_fnp->extremes.left = ins_pos + ins_size + offset; */
			new_fnp->extremes.right = fnp->extremes.right;
			new_fnp->extremes.left = ins_pos + 1;
			new_fnp->extremes.strand = fnp->extremes.strand;

			ValNodeAddPointer(&second_list, fnp_node->choice, new_fnp);

			fnp->extremes.left += offset;
			fnp->extremes.right = ins_pos + offset;

			new_fnp->interval = split_feature_interval(&(fnp->interval), offset, 
										 ins_pos, ins_size);

			prev = fnp_node;
		}
		fnp_node = next;
	}

	return second_list;
}


static Int4 find_insertion_size (InsertListPtr ilp, Int4Ptr ins_pos)
{
	while(ilp)
	{
		if(ilp->master_pos == *ins_pos)
		{
			if(ilp->after == FALSE)
				-- (*ins_pos);
			return ilp->max_size;
		}
		ilp = ilp->next;
	}

	return 0;
}
static Int4 get_max_insert_size (InsertListPtr ilp, Int4 from, Int4 to, Int4Ptr insert_pos)
{
	Int4 t_from, t_to;

	while(ilp)
	{
		if(ilp->used == FALSE)	/*it is not used by insertion and mapping*/
		{
			t_from = from;
			t_to = to;
			if(ilp->after == FALSE)
			{
				t_from +=1;
				t_to += 1;
			}
			if(ilp->master_pos >= from && ilp->master_pos <= to)
			{
				*insert_pos = ilp->master_pos;
				if(ilp->after == FALSE)
					--(*insert_pos);
				ilp->used = TRUE;
				return ilp->max_size;
			}
		}
		else if(ilp->master_pos > to)
			return -1;
		ilp = ilp->next;
	}

	return -1;
}

static Int4 get_max_gap_size(InsertListPtr ilp, Int4 from, Int4 to)
{
	Int4 max_size = 0;

	while(ilp)
	{
		if(ilp->used == FALSE)
		{
			if(ilp->master_pos >= from && ilp->master_pos <= to)
			{
				ilp->used = TRUE;
				max_size += ilp->max_size;
			}
		}
		if(ilp->master_pos > to)
			return max_size;

		ilp = ilp->next;
	}
	return max_size;
}


static ValNodePtr add_offset_to_mismatch(ValNodePtr PNTR mismatch, Int4 offset, Int4 ins_pos, Int4 ins_size)
{
	ValNodePtr second_list, prev, curr;

	second_list = NULL;
	curr = *mismatch;
	prev = NULL;
	while(curr)
	{
		if(curr->data.intvalue <= ins_pos || ins_pos == -1)
			curr->data.intvalue += offset;
		else
		{
			ValNodeLink(&second_list, curr);
			if(prev == NULL)
				*mismatch = NULL;
			else
				prev->next = NULL;
			return second_list;

		}
		prev = curr;
		curr = curr->next;
	}
	return second_list;
}

static void reset_insertion_list(InsertListPtr ilp, AlignSegPtr asp)
{
	AlignSegPtr curr;

	while(ilp)
	{
		ilp->used = FALSE;
		for(curr = asp; curr != NULL; curr = curr->next)
		{
			if(curr->ins_pos == ilp->master_pos)
			{
				ilp->used = TRUE;
				break;
			}
		}

		ilp = ilp->next;
	}
}

static void refresh_insertion_list(InsertListPtr ilp)
{
	while(ilp)
	{
		ilp->used = FALSE;
		ilp = ilp->next;
	}
}

static Int4 get_offset_of_insertion(InsertListPtr ilp, Int4 left)
{
	Int4 offset = 0;

	while(ilp)
	{
		if(ilp->master_pos >= left)
			return offset;
		else
			offset += ilp->max_size;
		ilp = ilp->next;
	}

	return offset;
}

static void modify_anp_with_insertion(AlignNodePtr anp, InsertListPtr ilp)
{
	Int4 offset;
	Int4 leftover;
	AlignSegPtr asp, next, new_asp, t_asp, prev;
	Int4 max_insert_size;
	Int4 insert_pos;
	AlignBlockPtr abp, new_abp, next_abp;
	ValNodePtr second_ms_list;


	asp = anp->segs;
	prev = NULL;
	reset_insertion_list(ilp, asp);
	offset = get_offset_of_insertion(ilp, anp->extremes.left);
	anp->extremes.left += offset;
	while(asp)
	{
		next = asp->next;
		if(asp->type == INS_SEG)
		{
			max_insert_size = find_insertion_size (ilp, &(asp->ins_pos));
			if(max_insert_size >0)
			{
				leftover = max_insert_size - asp->gr.right;	/*gr.right is the size of the insertion*/
				/*convert the insertion into a REG_SEG */
				asp->gr.left = asp->ins_pos + offset + 1;	/*insert after */
				asp->gr.right += (asp->gr.left -1);
				asp->type = REG_SEG;
				add_offset_to_featnode(asp->cnp, offset +1);

				/*insert the additional one for gaps*/
				if(leftover > 0)
				{
					new_asp = MemNew(sizeof(AlignSeg));
					new_asp->type = GAP_SEG;
					new_asp->gr.left = asp->gr.right + 1;
					new_asp->gr.right = new_asp->gr.left + leftover -1;
					asp->next = new_asp;
					new_asp->next = next;
				}
				offset += max_insert_size;
			}
			prev = asp;
		}
		else if(asp->type == GAP_SEG)
		{ /*a gap */
			max_insert_size = get_max_gap_size(ilp, asp->gr.left, asp->gr.right);
			asp->gr.left += offset;
			asp->gr.right += max_insert_size + offset;
			offset += max_insert_size;
			prev = asp;
		}
		else if(asp->type == REG_SEG)
		{	/* a diagnol */
			while( asp != NULL && (max_insert_size = 
				get_max_insert_size (ilp, asp->gr.left, 
				asp->gr.right, &insert_pos)) >0)
			{
				/*insertion at the very begining */
				if(insert_pos == -1)
				{
					new_asp = MemNew(sizeof(AlignSeg));
					new_asp->type = GAP_SEG;
					new_asp->gr.left = asp->gr.left;
					new_asp->gr.right = asp->gr.left + max_insert_size -1;
					if(prev == NULL)
						anp->segs = new_asp;
					else
						prev->next = new_asp;
					prev = new_asp;
					new_asp->next = asp;
				}
				else
				{
				if(asp->mismatch != NULL)
					second_ms_list = add_offset_to_mismatch(&(asp->mismatch), offset, 
						insert_pos, max_insert_size);
				else
					second_ms_list = NULL;

				leftover = asp->gr.right - insert_pos;
				asp->gr.left += offset;
				asp->gr.right = insert_pos + offset;

				new_asp = MemNew(sizeof(AlignSeg));
				new_asp->type = GAP_SEG;
				new_asp->gr.left = asp->gr.right + 1;
				new_asp->gr.right = insert_pos + offset + max_insert_size;
				new_asp->next = next;
				t_asp = asp;
				asp->next = new_asp;
				asp = new_asp;

				if(leftover > 0)
				{
					new_asp = MemNew(sizeof(AlignSeg));
					new_asp->type = REG_SEG;
					new_asp->gr.left = insert_pos +1;
					new_asp->gr.right = insert_pos + leftover;
					asp->next = new_asp;
					new_asp->next = next;
					new_asp->cnp = add_insertion_to_featnode(&(t_asp->cnp), offset, 
										insert_pos, max_insert_size);
					new_asp->mismatch = second_ms_list;
					new_asp->next = next;
					asp->next = new_asp;
					asp = new_asp;
					prev = new_asp;
				}
				else
				{
					add_offset_to_featnode(asp->cnp, offset);
					prev = asp;
					asp = NULL;
					break;
				}
				}

				offset += max_insert_size;
			}	/*end of while*/
			if(asp != NULL)
			{

				asp->gr.left += offset;
				asp->gr.right += offset;
				if(asp->cnp)
					add_offset_to_featnode(asp->cnp, offset);
				if(asp->mismatch != NULL)
					add_offset_to_mismatch(&(asp->mismatch), offset, -1, -1);
				prev = asp;
			}
		}
		asp = next;
	}
	anp->extremes.right += offset;

	if(offset > 0 && anp->blocks != NULL)
	{
		refresh_insertion_list(ilp);
		abp = anp->blocks;
		while(abp)
		{
			next_abp = abp->next;
			abp->next = NULL;
			offset = get_offset_of_insertion(ilp, abp->gr.left);
			while( abp && (max_insert_size = get_max_insert_size (ilp, 
					abp->gr.left, abp->gr.right, &insert_pos)) > 0)
			{
				/*insertion at the very begining */
				if(insert_pos == -1)
					offset += max_insert_size;
				else
				{
					leftover = abp->gr.right - insert_pos;
					if(leftover > 0)
					{
						new_abp = MemNew(sizeof(AlignBlock));
						new_abp->gr.left = insert_pos + 1;
						new_abp->gr.right = abp->gr.right;
						new_abp->order = abp->order;
						new_abp->next = next_abp;

						abp->gr.left += offset;
						abp->gr.right = insert_pos + offset;
						abp->next = new_abp;
						if(abp->gr.strand != Seq_strand_minus)
						{
							new_abp->gr.strand = abp->gr.strand;
							abp->gr.strand = 0;
						}
						abp = new_abp;
						offset += max_insert_size;
					}
					else	/*reach the end */
						break;
				}
			}
			if(abp != NULL)
			{
				abp->gr.left += offset;
				abp->gr.right += offset;
				abp->next = next_abp;
			}
			abp = next_abp;
		}
	}
}

static void free_insert_list(InsertListPtr ilp)
{
	InsertListPtr next;

	while(ilp)
	{
		next = ilp->next;
		MemFree(ilp);
		ilp = next;
	}
}


NLM_EXTERN Boolean FlatAlignNode(ValNodePtr anp_list)
{
	ValNodePtr curr;
	AlignNodePtr master_anp, anp;
	AnnotInfoPtr annot_info;
	Uint1 align_type;
	InsertListPtr ilp;
	AlignSegPtr asp;
	Int4 p_pos;

	
	master_anp = NULL;
	for(curr = anp_list; curr != NULL; curr = curr->next)
	{
		if(curr->choice == OBJ_SEQANNOT)
		{
			annot_info = curr->data.ptrvalue;
			align_type = get_alignment_type (annot_info);
			if(align_type == ALIGN_DNA_TO_PROT || 
				align_type == ALIGN_PROT_TO_DNA || align_type == ALIGN_TDNA_TO_TDNA)
				return FALSE;
		}
		else
		{
			anp = curr->data.ptrvalue;
			if(anp->is_master)
				master_anp = anp;
		}
	}
	if(master_anp == NULL)
		return FALSE;

	/*load all the insertions in the alignments*/
	ilp = NULL;
	for(curr = anp_list; curr != NULL; curr = curr->next)
	{
		if(curr->choice != OBJ_SEQANNOT)
		{
			anp = curr->data.ptrvalue;
			if(anp != master_anp)
			{
				p_pos = -1;
				for(asp = anp->segs; asp != NULL; asp = asp->next)
				{
					if(asp->type == INS_SEG)
						load_insertion_list(&ilp, asp->ins_pos, asp->gr.right, (Boolean)(p_pos == asp->ins_pos));
					else if(asp->type != GAP_SEG)
						p_pos = asp->gr.right;
				}
			}
		}
	}

	if(ilp == NULL)
		return FALSE;

	/*do the real flatting*/
	for(curr = anp_list; curr != NULL; curr = curr->next)
	{
		if(curr->choice != OBJ_SEQANNOT)
		{
			anp = curr->data.ptrvalue;
			modify_anp_with_insertion(anp, ilp);
		}
	}


	free_insert_list(ilp);
	return TRUE;
}


/*
*	Delete all the bad YACs from the list
*	anything on the NHGRI map that is recorded inconsistent will 
*	be considered inconsistent. For the Whitehead map, the 
*	inconsistent+ambiguous is inconsistent. Inconsistent alone 
*	is not considered inconsistent
*/
static Boolean is_ambiguous_annot(AnnotInfoPtr info, Uint1 db)
{
	if(info == NULL)
		return FALSE;
	if(info->annot_type == ANNOT_CONSIST)
	{
		if(info->consistent == ALIGN_CONSISTENT)
			return FALSE;
		else
		{
			if(info->consistent == ALIGN_INCONSISTENT)
			{
				if(db == YAC_NHGRI)
					return TRUE;
				else if(db == YAC_MIT)
				{	/*inconsistent and ambiguous are different*/
					if(StringCmp(info->annotDB, "Ambiguous") == 0)
					
						return TRUE;
					else
						return FALSE;
				}
			}
		}
	}

	return FALSE;
}

/*
*	delete any of the whitehead yacs that only contains 
*	ambiguous STS hits
*/
static Boolean delete_alignnode (AlignNodePtr anp, Uint1 db)
{
	AlignSegPtr asp;
	ValNodePtr curr;
	Boolean has_sts_hits;

	has_sts_hits = FALSE;
	for(asp = anp->segs; asp != NULL; asp = asp->next)
	{
		if(asp->mismatch != NULL)
		{
			for(curr = asp->mismatch; curr != NULL; curr = curr->next)
			{
				if(curr->choice == MISMATCH_CLOSE)	/*unambiguous hits*/
					return FALSE;
				if(curr->choice == MISMATCH_SQUARE)
				{
					if(db == YAC_NHGRI)
						return FALSE;
				}
			}
			has_sts_hits = TRUE;
		}
	}

	return (has_sts_hits == FALSE);
}


/*
*	Delete all the bad YACs from the list
*	anything on the NHGRI map that is recorded inconsistent will 
*	be considered inconsistent. For the Whitehead map, the 
*	inconsistent+ambiguous is inconsistent. Inconsistent alone 
*	is not considered inconsistent
*/
NLM_EXTERN void CleanUpAmbiguousYAC (ValNodePtr PNTR anp_node, Uint1 db, SeqIdPtr chr_id)
{
	AnnotInfoPtr info;
	AlignNodePtr anp;
	ValNodePtr curr, prev, next;
	Boolean del_annot;
	Boolean del;

	prev = NULL;
	del_annot = FALSE;

	curr = *anp_node;
	while(curr)
	{
		next = curr->next;
		del = FALSE;
		if(curr->choice == OBJ_SEQANNOT)
		{
			info = curr->data.ptrvalue;
			del_annot = is_ambiguous_annot(info, db);
		}
		else if(!del_annot || chr_id != NULL)
		{
			anp = curr->data.ptrvalue;
			if(chr_id != NULL)
			{
				if(anp->sip != NULL)
				{
					if(SeqIdMatch(chr_id, anp->sip))
						del = TRUE;
				}
			}
			if(!del)
				del = delete_alignnode (anp, db);
		}
		if(del_annot)
			del = TRUE;

		if(del)
		{
			if(prev == NULL)
				*anp_node = next;
			else
				prev->next = next;
			curr->next = NULL;
			FreeAlignNode(curr);
		}
		else
			prev = curr;
		curr = next;
	}
}


	
/*****************************************************************
*
*	check if the AlignNode only contains Seq-annot or it 
*	has real sequence alignment. 
*	the empty Seq-annot may be the unaligned contigs in 
*	Eric Green's map
*
******************************************************************/
NLM_EXTERN Boolean alignode_has_alignments(ValNodePtr aligns)
{
	while(aligns)
	{
		if(aligns->choice != OBJ_SEQANNOT)
			return TRUE;
		aligns = aligns->next;
	}

	return FALSE;
}