1
2 #include <layout.h>
3 #include <fstyle.h>
4 #define MAX_INS 40 /*maximum levels for insertions*/
5 #define MAX_STACK 5 /*maximum allowed level of stacks*/
6 #include <vibrant.h>
7
8 /**********************************************************************
9 *
10 * LayoutNodeFlat(head, maxScale, top, seq_pos, downward, label_pos)
11 * layout the FeatNode as a stacked layout
12 * head: the list of FeatNode. Will be resorted
13 * maxScale: the maximum scale in the picture
14 * top: current available position at y-axis
15 * seq_pos: store the position for drawing the sequence after the
16 * stacking is over
17 * downward: stack the genes below the sequence line
18 * label_pos: if(TRUE), label the map position for each cluster
19 *
20 **********************************************************************/
21
22 /***********************************************************************
23 *
24 * ModLabelInterval(left, right, maxScale, label)
25 * Modify left, right position to take the StringWidth of label into
26 * account.
27 *
28 ************************************************************************/
29
ModLabelInterval(Int4Ptr left,Int4Ptr right,Int4 maxScale,Int4 label_len,Uint1 label_align)30 static Boolean ModLabelInterval(Int4Ptr left, Int4Ptr right, Int4 maxScale, Int4 label_len, Uint1 label_align)
31 {
32
33 Int4 center;
34 Int4 p_left, p_right;
35
36
37 if(maxScale <=0 || label_len == 0)
38 return FALSE;
39 switch (label_align)
40 {
41 case MSM_LABEL_TOP:
42 case MSM_LABEL_BOTTOM:
43 p_left = (*left)/maxScale;
44 p_right = (*right)/maxScale;
45 if(label_len > (p_right - p_left))
46 {
47 center = (*left + (*right))/2;
48 *left = center - (label_len/2) * maxScale;
49 *right = center + (label_len/2) * maxScale;
50 }
51 break;
52
53 case MSM_LABEL_LEFT:
54 *left -= (label_len +1)*maxScale;
55 break;
56 case MSM_LABEL_RIGHT:
57 *right += (label_len +1)*maxScale;
58 break;
59 default:
60 return FALSE;
61 }
62 return TRUE;
63 }
64
65
get_current_class(FeatNodePtr fnp)66 Int2 get_current_class(FeatNodePtr fnp)
67 {
68 Int2 c_class;
69 Boolean has_gb, has_medline;
70
71 c_class = (fnp->feattype == 0) ? MSM_SEQUENCE: (Int2)(fnp->feattype);
72 has_gb = (Boolean)((fnp->extra_data) & EXTRA_GENBANK);
73 has_medline = (Boolean)((fnp->extra_data) & EXTRA_MEDLINE);
74 if(has_gb && has_medline)
75 return MSM_EXTRA_BOTH;
76 if(has_gb)
77 return MSM_EXTRA_GENBANK;
78 if(has_medline)
79 return MSM_EXTRA_MEDLINE;
80 return c_class;
81 }
82
83
modify_label_for_supress(FeatNodePtr c_fnp)84 static void modify_label_for_supress(FeatNodePtr c_fnp)
85 {
86 Char label[101];
87
88 if(c_fnp->supress_node != NULL)
89 {
90 if(c_fnp->label != NULL)
91 {
92 sprintf(label, "[%s]", c_fnp->label);
93 MemFree(c_fnp->label);
94 c_fnp->label = StringSave(label);
95 }
96 }
97 }
98
is_Dseg_label(CharPtr label)99 static Boolean is_Dseg_label(CharPtr label)
100 {
101 CharPtr str;
102 Boolean has_number;
103
104 if(label == NULL)
105 return FALSE;
106 if(*label != 'D')
107 return FALSE;
108 has_number = FALSE;
109 for(str = label+1; str != NULL && *str != '\0'; ++str)
110 {
111 if(has_number)
112 {
113 if(IS_ALPHA(*str))
114 return (*str == 'S');
115 }
116 else
117 {
118 if(!IS_DIGIT(*str))
119 return FALSE;
120 has_number = TRUE;
121 }
122 }
123
124 return FALSE;
125 }
126
127
128
load_supress_node(ValNodePtr head,ValNodePtr s_node)129 static Boolean load_supress_node(ValNodePtr head, ValNodePtr s_node)
130 {
131 FeatNodePtr fnp;
132 FeatNodePtr s_fnp;
133 Int4 s_pos, pos;
134 ValNodePtr vnp;
135 Int4 i;
136 Boolean has_gb;
137 Boolean has_med;
138 Uint1 merge_code; /*1=merge_to_exiting 2=exiting_merge_to_me */
139
140 s_fnp = s_node->data.ptrvalue;
141 if(!is_Dseg_label(s_fnp->label))
142 return FALSE;
143 has_gb = (Boolean)((s_fnp->extra_data) & EXTRA_GENBANK);
144 has_med = (Boolean)((s_fnp->extra_data) & EXTRA_MEDLINE);
145
146 s_pos = s_fnp->extremes.left;
147 vnp = head;
148 i = 0;
149 merge_code = 0;
150 while(vnp)
151 {
152 fnp = vnp->data.ptrvalue;
153 pos = fnp->extremes.left;
154 if(pos == s_pos)
155 {
156 if(is_Dseg_label(fnp->label))
157 /* if(StringNCmp(fnp->label, s_fnp->label, 3) == 0) */
158 {
159 ++i;
160 if(!has_gb && !has_med)
161 merge_code = 1;
162 else
163 {
164 if(((fnp->extra_data) & EXTRA_GENBANK) == 0)
165 {
166 if(has_gb)
167 merge_code = 2;
168 else
169 {
170 if(((fnp->extra_data) & EXTRA_MEDLINE) == 0)
171 merge_code = 2;
172 else
173 merge_code = 1;
174 }
175 }
176 else if(!has_gb)
177 merge_code = 1;
178 }
179 /*deal with the landmark genes*/
180 if(s_fnp->landmark) /*it is a landmark gene*/
181 {
182 if(fnp->landmark)
183 merge_code = 0;
184 else if(merge_code == 1)
185 merge_code = 0;
186 }
187 else if(fnp->landmark && merge_code == 2)
188 merge_code = 0;
189
190
191 if(merge_code == 1)
192 {
193 ValNodeLink(&(fnp->supress_node), s_node);
194 return TRUE;
195 }
196 if(merge_code == 2)
197 {
198 s_fnp->supress_node = fnp->supress_node;
199 fnp->supress_node = NULL;
200 vnp->data.ptrvalue = s_fnp;
201 s_node->data.ptrvalue = fnp;
202
203 ValNodeLink(&(s_fnp->supress_node), s_node);
204 return TRUE;
205 }
206 }
207 }
208 vnp = vnp->next;
209 }
210
211 if(i < MAX_STACK)
212 return FALSE;
213 vnp = head;
214 while(vnp)
215 {
216 fnp = vnp->data.ptrvalue;
217 pos = fnp->extremes.left;
218 if(pos == s_pos)
219 {
220 /* if(StringNCmp(fnp->label, s_fnp->label, 3) == 0) */
221 if(is_Dseg_label(fnp->label))
222 {
223 if(!fnp->landmark)
224 {
225 if(s_fnp->landmark)
226 merge_code = 2;
227 else
228 merge_code = 1;
229 if(merge_code == 1)
230 {
231 ValNodeLink(&(fnp->supress_node), s_node);
232 return TRUE;
233 }
234 if(merge_code == 2)
235 {
236 s_fnp->supress_node = fnp->supress_node;
237 fnp->supress_node = NULL;
238 vnp->data.ptrvalue = s_fnp;
239 s_node->data.ptrvalue = fnp;
240 return TRUE;
241 }
242 }
243 }
244 }
245 vnp = vnp->next;
246 }
247
248 return FALSE;
249
250 }
251
252
find_flat_line(Int4 left,Int4 right,ValNodePtr PNTR lines,Int4 space,Int4 num,ValNodePtr curr)253 static Int2 find_flat_line(Int4 left, Int4 right, ValNodePtr PNTR lines, Int4 space, Int4 num, ValNodePtr curr)
254 {
255 Int4 i;
256 ValNodePtr vnp, next, prev;
257 FeatNodePtr fnp, n_fnp;
258 Int4 space_l, space_r;
259
260 for(i = 0; i<num; ++i)
261 {
262 vnp = lines[i];
263 if(vnp == NULL)
264 {
265 lines[i] = curr;
266 return (Int2)i;
267 }
268 else
269 {
270 prev = NULL;
271 while(vnp)
272 {
273 next = vnp->next;
274 fnp = vnp->data.ptrvalue;
275 if(prev == NULL)
276 {
277 if(right+space <= fnp->ef_left)
278 {
279 lines[i] = curr;
280 curr->next = vnp;
281 return (Int2)i;
282 }
283 }
284
285 if(next == NULL)
286 {
287 if(fnp->ef_right + space <= left)
288 {
289 vnp->next = curr;
290 return (Int2)i;
291 }
292 }
293 else
294 {
295 n_fnp = next->data.ptrvalue;
296 space_l = fnp->ef_right + space;
297 space_r = n_fnp->ef_left - space;
298 if(left >=space_l && right <= space_r)
299 {
300 vnp->next = curr;
301 curr->next = next;
302 return (Int2)i;
303 }
304 }
305 prev = vnp;
306 vnp = next;
307 }
308 }
309 }
310
311 return -1;
312 }
313
LayoutNodeFlat(ValNodePtr PNTR head,Int4 maxScale,Int4 top,Uint1 label_type,Boolean supress)314 Int4 LayoutNodeFlat(ValNodePtr PNTR head, Int4 maxScale, Int4 top, Uint1 label_type, Boolean supress)
315 {
316 Uint1 labelstyle;
317 Int4Ptr y_height;
318 Int4 num, k, i, j;
319 Boolean has_prev = FALSE;
320 FonT font;
321 Int2 p_class, ptype = 0;
322 Int4 font_height = 0;
323 Int4 currentHeight;
324 Int4 y_max;
325 Int4 left, right, center;
326 ValNodePtr vnp, next, prev;
327 FeatNodePtr fnp;
328 Int4 symbol_width, symbol_height;
329 Int4 label_len;
330 Uint1 label_align;
331 Int4 next_y;
332 ValNodePtr maptype_list[MARK_TYPE_NUM];
333 ValNodePtr PNTR lines;
334 Uint1 map_mark_type;
335 Uint1 display_order[MARK_TYPE_NUM];
336
337
338 if(label_type != UPPER_LABEL && label_type != LOWER_LABEL)
339 return top;
340 if(label_type == UPPER_LABEL)
341 label_align = MSM_LABEL_TOP;
342 if(label_type == LOWER_LABEL)
343 label_align = MSM_LABEL_BOTTOM;
344
345 /*pre-treat the supress node*/
346 if(supress)
347 {
348 vnp = *head;
349 *head = NULL;
350 while(vnp)
351 {
352 next = vnp->next;
353 vnp->next = NULL;
354 if(!load_supress_node(*head, vnp))
355 ValNodeLink(head, vnp);
356 vnp = next;
357 }
358 for(vnp = *head; vnp != NULL; vnp = vnp->next)
359 {
360 fnp = vnp->data.ptrvalue;
361 modify_label_for_supress(fnp);
362 }
363
364 }
365 for(num = 0; num<MARK_TYPE_NUM; ++num)
366 display_order[num] = (Uint1)num;
367 display_order[1] = NO_TYPE; /*reverse the order of FRAME_WORK*/
368 display_order[0] = FRAME_WORK;
369
370 for(num = 0; num<MARK_TYPE_NUM; ++num)
371 maptype_list[num] = NULL;
372
373 num = 0;
374 vnp = *head;
375 while(vnp)
376 {
377 next = vnp->next;
378 fnp = vnp->data.ptrvalue;
379 center = (fnp->extremes.left + fnp->extremes.right)/2;
380 fnp->extremes.left = center;
381 fnp->extremes.right = center;
382 map_mark_type = get_map_type(fnp->extra_data);
383 vnp->next = NULL;
384 ValNodeLink(&(maptype_list[map_mark_type]), vnp);
385 ++num;
386 vnp = next;
387 }
388 if(num == 0)
389 return top;
390
391 lines = MemNew((size_t)(num) * sizeof(ValNodePtr));
392 y_height = MemNew((size_t)(2*num) * sizeof (Int4));
393 symbol_width = 8; /*temporary*/
394 symbol_height = 8; /*temporary*/
395
396 k =0; i =0;
397 labelstyle = NO_LABEL;
398 for(j = 0; j<MARK_TYPE_NUM; ++j)
399 {
400
401 vnp = maptype_list[display_order[j]];
402 prev = NULL;
403 while(vnp)
404 {
405 next = vnp->next;
406 vnp->next = NULL;
407 fnp = vnp->data.ptrvalue;
408
409 /*get the height of the box and the font of label*/
410 p_class = get_current_class(fnp);
411 if(!has_prev || (p_class != ptype))
412 {
413 has_prev = TRUE;
414 labelstyle = (Uint1)GetMuskCParam(p_class, MSM_FLABEL, MSM_STYLE);
415 if(labelstyle != NO_LABEL)
416 {
417 font = (FonT)GetMuskCParam(p_class, MSM_FLABEL, MSM_FONT);
418 SelectFont(font);
419 font_height = FontHeight();
420 }
421 ptype = p_class;
422 }
423 left = fnp->extremes.left;
424 right = fnp->extremes.right;
425 label_len = symbol_width * 3;
426 if(fnp->label == NULL)
427 fnp->labelHeight = 0;
428 else
429 {
430 fnp->labelHeight = font_height;
431 fnp->label_len = StringWidth(fnp->label);
432 label_len = MAX(label_len, fnp->label_len);
433 }
434 ModLabelInterval(&left, &right, maxScale, label_len, label_align);
435
436 fnp->ef_left = left;
437 fnp->ef_right = right;
438 i = find_flat_line(left, right, lines, 2L*maxScale, num, vnp);
439 fnp->line = i;
440 currentHeight = fnp->labelHeight + symbol_width;
441 y_height[i] = MAX(y_height[i], currentHeight);
442 k = MAX(k, i);
443 vnp = next;
444 }
445 }
446
447 *head = NULL;
448 for(i = 0; i<=k; ++i)
449 {
450 ValNodeLink(head, lines[i]);
451 }
452 MemFree(lines);
453
454
455 y_max = TICK_LEN;
456 for(i =0; i<= k; ++i)
457 y_max += y_height[i];
458
459 next_y = top - y_max;
460 if(label_align == MSM_LABEL_TOP)
461 top -= y_max;
462
463
464 for(i =0; i<= k; ++i)
465 {
466 for(vnp = (*head); vnp !=NULL; vnp = vnp->next)
467 {
468 fnp = vnp->data.ptrvalue;
469 if(fnp)
470 {
471 if(fnp->line == i)
472 {
473 switch(label_align)
474 {
475 case MSM_LABEL_TOP:
476 fnp->top = top + symbol_height;
477 break;
478
479 case MSM_LABEL_BOTTOM:
480 fnp->top = top;
481 break;
482 default:
483 fnp->top = top;
484 break;
485 }
486 fnp->bottom = fnp->top - symbol_width;
487 }
488 }
489 }
490 if(label_align == MSM_LABEL_TOP)
491 top += y_height[i];
492 else
493 top -= y_height[i];
494 }
495
496 MemFree(y_height);
497 return next_y;
498 }
499
500 /*for each alignnode, only use the symbol to indicate the center of its left/right
501 * border. No label
502 */
LayoutAlignFlat(ValNodePtr head,Int4 maxScale,Int4 top)503 Int4 LayoutAlignFlat(ValNodePtr head, Int4 maxScale, Int4 top)
504 {
505 Int2 num_line, line;
506 Int4 next_line;
507 Int4Ptr y_pos;
508 AlignNodePtr anp;
509 Int4 symbol_height;
510 Int4 left, right;
511
512 num_line = get_vnp_num(head);
513 if(num_line <= 0)
514 return top;
515 next_line = top;
516 y_pos = MemNew((size_t)2*num_line * sizeof (Int4));
517 symbol_height = 8 + 2; /*8 is the height of symbol, 2 is for separation space*/
518 while(head)
519 {
520 if(head->choice != OBJ_SEQANNOT)
521 {
522 anp = head->data.ptrvalue;
523 left = anp->extremes.left;
524 right = left + symbol_height * maxScale;
525 line = find_f_pos(left, right, y_pos, 0, (Int2)num_line);
526 anp->line = top - (line + 1) * symbol_height;
527 next_line = MIN(anp->line, next_line);
528 }
529 head = head->next;
530 }
531 MemFree(y_pos);
532 return next_line;
533
534 }
535
count_one_interval(GatherRange gr_1,GatherRange gr_2)536 static Int4 count_one_interval(GatherRange gr_1, GatherRange gr_2)
537 {
538 Int4 count = 0;
539
540 count += ABS(gr_1.left - gr_2.left);
541 count += ABS(gr_1.right - gr_2.right);
542 return count;
543 }
544
count_mismatch(FeatNodePtr fnp_1,FeatNodePtr fnp_2,BoolPtr same_num)545 static Int4 count_mismatch(FeatNodePtr fnp_1, FeatNodePtr fnp_2, BoolPtr same_num)
546 {
547 Int2 num_1, num_2;
548 ValNodePtr vnp_1, vnp_2;
549 Int4 count = 0;
550 IvalNodePtr inp_1, inp_2;
551
552
553 *same_num = FALSE;
554 if(fnp_1->interval != NULL && fnp_2->interval != NULL)
555 {
556 num_1 = get_vnp_num(fnp_1->interval);
557 num_2 = get_vnp_num(fnp_2->interval);
558 if(num_1 == num_2)
559 {
560 vnp_1 = fnp_1->interval;
561 vnp_2 = fnp_2->interval;
562 while(vnp_1 && vnp_2)
563 {
564 inp_1 = vnp_1->data.ptrvalue;
565 inp_2 = vnp_2->data.ptrvalue;
566 count += count_one_interval(inp_1->gr, inp_2->gr);
567 vnp_1 = vnp_1->next;
568 vnp_2 = vnp_2->next;
569 *same_num = TRUE;
570 }
571 return count;
572 }
573 }
574
575 return count_one_interval(fnp_1->extremes, fnp_2->extremes);
576 }
577
calculate_overlap(Int4 left_1,Int4 right_1,Int4 left_2,Int4 right_2)578 static FloatHi calculate_overlap(Int4 left_1, Int4 right_1, Int4 left_2, Int4 right_2)
579 {
580 Int4 temp1, temp2;
581
582 temp1 = MAX(left_1, left_2);
583 temp2 = MIN(right_1, right_2);
584 if ( right_1 == left_1 ) return 1.0;
585 return (FloatHi)(temp2 - temp1 +1)/(FloatHi)(right_1 - left_1 +1);
586
587 }
588
589
link_to_group(ValNodePtr this_group,ValNodePtr new)590 static void link_to_group(ValNodePtr this_group, ValNodePtr new)
591 {
592 FeatNodePtr n_fnp;
593 FeatNodePtr fnp;
594 ValNodePtr my_node = NULL, curr, prev, next;
595 Int4 count, p_count;
596 Boolean same, p_same;
597 Boolean found;
598
599 if(this_group == NULL || new == NULL)
600 return;
601 n_fnp = new->data.ptrvalue;
602
603 n_fnp->follower= TRUE;
604 curr = this_group;
605 while(curr)
606 {
607 fnp = curr->data.ptrvalue;
608 count = count_mismatch(fnp, n_fnp, &same);
609 if(curr != this_group && !(fnp->follower))
610 break;
611 found = FALSE;
612 if(fnp->feattype != n_fnp->feattype)
613 {
614 if(my_node == NULL)
615 found = TRUE;
616 else
617 {
618 if(same != p_same)
619 found = same;
620 else
621 found = (p_count >= count);
622 }
623 }
624 if(found)
625 {
626 my_node = curr;
627 p_count = count;
628 p_same = same;
629 }
630 prev = curr;
631 curr = curr->next;
632 }
633 if(my_node == NULL)
634 {
635 next = prev->next;
636 prev->next = new;
637 new->next = next;
638 }
639 else
640 {
641 curr = this_group;
642 while(curr)
643 {
644 next =curr->next;
645 if(curr == my_node)
646 {
647 curr->next = new;
648 new->next = next;
649 break;
650 }
651 curr = curr->next;
652 }
653 }
654 }
655
ordered_link(ValNodePtr PNTR head,ValNodePtr new)656 static void ordered_link(ValNodePtr PNTR head, ValNodePtr new)
657 {
658 ValNodePtr group, prev = NULL;
659 FeatNodePtr g_fnp, fnp;
660 Int4 left;
661
662 if(*head == NULL)
663 *head = new;
664 else
665 {
666 group = *head;
667 fnp = new->data.ptrvalue;
668 left = fnp->extremes.left;
669 while(group!= NULL)
670 {
671 g_fnp = group->data.ptrvalue;
672 if(!(g_fnp->follower))
673 if(g_fnp->extremes.left > left)
674 break;
675 prev = group;
676 group = group->next;
677 }
678 if(prev == NULL)
679 {
680 new->next = *head;
681 *head = new;
682 }
683 else
684 {
685 new->next = prev->next;
686 prev->next = new;
687 }
688 }
689 }
690
make_prev_group(ValNodePtr PNTR h_group,ValNodePtr new)691 static void make_prev_group(ValNodePtr PNTR h_group, ValNodePtr new)
692 {
693 ValNodePtr next, group;
694 FeatNodePtr fnp, n_fnp;
695 Int4 e_left, e_right, left, right;
696 ValNodePtr this_group;
697 FloatHi g_overlap = 0.0, t_overlap = 0.0;
698 FloatHi overlap_1, overlap_2;
699 Boolean found;
700 ValNodePtr head_group;
701
702 head_group = *h_group;
703 if(new == NULL || head_group == NULL)
704 return;
705 while(new)
706 {
707 next = new->next;
708 n_fnp = new->data.ptrvalue;
709 e_left = n_fnp->extremes.left;
710 e_right = n_fnp->extremes.right;
711 this_group = NULL;
712 g_overlap = 0.0;
713 t_overlap = 0.0;
714 for(group = head_group; group != NULL; group = group->next)
715 {
716 fnp = group->data.ptrvalue;
717 if(!(fnp->follower) && (fnp->extremes.strand == n_fnp->extremes.strand)) /*only checks the leaders*/
718 {
719 left = fnp->extremes.left;
720 right = fnp->extremes.right;
721 if(!(left > e_right || right < e_left)) /*overlaps*/
722 {
723
724 overlap_1 = calculate_overlap(left, right, e_left, e_right);
725 overlap_2 = calculate_overlap(e_left, e_right, left, right);
726 if(overlap_1 < 0.50 && overlap_2 < 0.50)
727 found = FALSE;
728 else
729 {
730 if(fnp->feattype == n_fnp->feattype)
731 /*found = (overlap_1 == 1.00 && overlap_2 == 1.00);*/
732 found = FALSE;
733 else
734 found = TRUE;
735 }
736 if(found)
737 {
738 if(this_group != NULL)
739 {
740 if(overlap_1 > t_overlap)
741 found = TRUE;
742 else
743 {
744 if(overlap_1 == t_overlap)
745 found = (overlap_2 > g_overlap);
746 }
747 }
748 }
749 if(found)
750 {
751 this_group = group;
752 g_overlap = overlap_2;
753 t_overlap = overlap_1;
754 }
755 }
756 }
757 }
758
759 new->next = NULL;
760 if(this_group != NULL)
761 link_to_group(this_group, new);
762 else /*link to the end*/
763 {
764 n_fnp->follower= FALSE;
765 ordered_link(h_group, new);
766 /*ValNodeLink(&head_group, new);*/
767 }
768
769 new = next;
770 }
771 }
772
773 /*************************************************************************
774 *
775 * ReSetFeatNode(fnp_node): set all the fnp->line = 0. Before the layout,
776 * fnp->line == 0 indicate the start of a new group.
777 *
778 **************************************************************************/
ReSetFeatNode(ValNodePtr fnp_node)779 void ReSetFeatNode(ValNodePtr fnp_node)
780 {
781 ValNodePtr curr;
782 FeatNodePtr fnp;
783
784 for(curr = fnp_node; curr != NULL; curr = curr->next)
785 {
786 fnp = curr->data.ptrvalue;
787 fnp->follower = FALSE;
788 }
789 }
790
791
792 /*************************************************************************
793 *
794 * GroupFeatNode(head, new_group)
795 * Add a new list of FeatNode (from the same feattype) to the head
796 * of its group. The new group will be sorted
797 *
798 **************************************************************************/
GroupFeatNode(ValNodePtr PNTR head)799 ValNodePtr GroupFeatNode(ValNodePtr PNTR head)
800 {
801
802 ValNodePtr next;
803 ValNodePtr new_group;
804
805 if(head == NULL || *head == NULL)
806 return NULL;
807 new_group = *head;
808 next = new_group->next;
809 new_group->next = NULL;
810 make_prev_group(head, next);
811 return (*head);
812 }
813
is_inside_interval(Int4 a,Int4 x,Int4 y)814 static Boolean is_inside_interval(Int4 a, Int4 x, Int4 y)
815 {
816 return (a >=x && a<=y);
817 }
818
is_mRNA_CDS_compatible(FeatNodePtr cds_node,FeatNodePtr mRNA_node,Int4Ptr offset,Int2Ptr interval_missed)819 static Boolean is_mRNA_CDS_compatible(FeatNodePtr cds_node, FeatNodePtr mRNA_node, Int4Ptr offset, Int2Ptr interval_missed)
820 {
821 Int2 cds_num, mRNA_num;
822 ValNodePtr cds_interval, mRNA_interval;
823 IvalNodePtr cds_inp, mRNA_inp;
824 Boolean found;
825
826 if(cds_node->interval == NULL || mRNA_node->interval == NULL)
827 return FALSE;
828 *offset = 0;
829 *interval_missed = 0;
830
831 cds_num = get_vnp_num(cds_node->interval);
832 mRNA_num = get_vnp_num(mRNA_node->interval);
833
834 if(mRNA_num < cds_num)
835 return FALSE;
836
837 if(cds_node->extremes.strand == Seq_strand_minus)
838 {
839 if(mRNA_node->extremes.strand != Seq_strand_minus)
840 return FALSE;
841 }
842 if(mRNA_node->extremes.strand == Seq_strand_minus)
843 {
844 if(cds_node->extremes.strand != Seq_strand_minus)
845 return FALSE;
846 }
847
848
849 found = FALSE;
850 cds_interval = cds_node->interval;
851 cds_inp = cds_interval->data.ptrvalue;
852 mRNA_interval = mRNA_node->interval;
853 while(mRNA_interval != NULL)
854 {
855 mRNA_inp = mRNA_interval->data.ptrvalue;
856 if(is_inside_interval(cds_inp->gr.left, mRNA_inp->gr.left, mRNA_inp->gr.right))
857 {
858 if(is_inside_interval(cds_inp->gr.right, mRNA_inp->gr.left, mRNA_inp->gr.right))
859 {
860 found = TRUE;
861 if(cds_interval->next != NULL) /*there is more than one exon in CDS*/
862 {
863 if(cds_inp->gr.strand == Seq_strand_minus)
864 found = (cds_inp->gr.left == mRNA_inp->gr.left);
865 else
866 found = (cds_inp->gr.right == mRNA_inp->gr.right);
867 }
868 if(found)
869 {
870 *offset += (cds_inp->gr.left - mRNA_inp->gr.left);
871 *offset += (mRNA_inp->gr.right - cds_inp->gr.right);
872 }
873 }
874 }
875 if(found)
876 break;
877 else
878 {
879 ++(*interval_missed);
880 mRNA_interval = mRNA_interval->next;
881 }
882 }
883
884 if(!found || mRNA_interval == NULL)
885 return FALSE;
886
887 cds_num = get_vnp_num(cds_interval->next);
888 mRNA_num = get_vnp_num(mRNA_interval->next);
889 if(cds_num > mRNA_num)
890 return FALSE;
891
892 if(cds_num == 0)
893 return TRUE;
894
895 cds_interval = cds_interval->next;
896 mRNA_interval = mRNA_interval->next;
897 while(cds_interval && mRNA_interval)
898 {
899 cds_inp = cds_interval->data.ptrvalue;
900 mRNA_inp = mRNA_interval->data.ptrvalue;
901 if(cds_interval->next == NULL) /*the last CDS*/
902 {
903 if(cds_inp->gr.strand == Seq_strand_minus)
904 {
905 if(mRNA_inp->gr.right!= cds_inp->gr.right)
906 return FALSE;
907 if(cds_inp->gr.left< mRNA_inp->gr.left)
908 return FALSE;
909 }
910 else
911 {
912 if(mRNA_inp->gr.left != cds_inp->gr.left)
913 return FALSE;
914 if(cds_inp->gr.right > mRNA_inp->gr.right)
915 return FALSE;
916 }
917 *offset += (mRNA_inp->gr.right - cds_inp->gr.right);
918 }
919 else
920 {
921 if(cds_inp->gr.right != mRNA_inp->gr.right)
922 return FALSE;
923 if(cds_inp->gr.left != mRNA_inp->gr.left)
924 return FALSE;
925 }
926
927 cds_interval = cds_interval->next;
928 mRNA_interval = mRNA_interval->next;
929 }
930
931 return TRUE;
932 }
933
insert_CDS_to_best_mRNA(ValNodePtr mRNA_head,ValNodePtr cds)934 static Boolean insert_CDS_to_best_mRNA(ValNodePtr mRNA_head, ValNodePtr cds)
935 {
936 ValNodePtr curr, next;
937 FeatNodePtr fnp, c_fnp;
938 ValNodePtr best_mRNA = NULL;
939 Int4 offset, m_offset = -1;
940 Int2 missed, m_missed; /*number of exons missed at both end*/
941
942 if(mRNA_head == NULL || cds == NULL)
943 return FALSE;
944 else
945 {
946 c_fnp = cds->data.ptrvalue;
947 curr = mRNA_head;
948 while(curr)
949 {
950 fnp = curr->data.ptrvalue;
951 if(fnp->feattype == FEATDEF_mRNA)
952 {
953 if(is_mRNA_CDS_compatible(c_fnp, fnp, &offset, &missed))
954 {
955 if(best_mRNA == NULL)
956 {
957 best_mRNA = curr;
958 m_offset = offset;
959 m_missed = missed;
960 }
961 else
962 {
963 if(missed < m_missed)
964 {
965 best_mRNA = curr;
966 m_offset = offset;
967 m_missed = missed;
968 }
969 else if(missed == m_missed && m_offset > offset)
970 {
971 best_mRNA = curr;
972 m_offset = offset;
973 m_missed = missed;
974 }
975
976 }
977 }
978 }
979
980 curr = curr->next;
981 }
982 }
983
984 if(best_mRNA != NULL)
985 {
986 curr = mRNA_head;
987 c_fnp->follower = TRUE;
988 while(curr)
989 {
990 if(curr == best_mRNA)
991 {
992 next = curr->next;
993 curr->next = cds;
994 cds->next = next;
995 return TRUE;
996 }
997
998 curr = curr->next;
999 }
1000 }
1001
1002 return FALSE;
1003 }
1004
find_best_gene(ValNodePtr curr,Int4 cds_left,Int4 cds_right)1005 static ValNodePtr find_best_gene(ValNodePtr curr, Int4 cds_left, Int4 cds_right)
1006 {
1007 FeatNodePtr fnp;
1008 ValNodePtr best_gene = NULL;
1009 Int4 offset, m_offset = -1;
1010 Int4 left, right;
1011
1012 if(curr == NULL)
1013 return NULL;
1014 else
1015 {
1016 while(curr)
1017 {
1018 fnp = curr->data.ptrvalue;
1019 if(fnp->feattype == FEATDEF_GENE)
1020 {
1021 if(!(fnp->extremes.left > cds_right|| fnp->extremes.right < cds_left))
1022 {
1023 offset = 0;
1024 left = fnp->extremes.left;
1025 right = fnp->extremes.right;
1026 offset += ABS(left - cds_left);
1027 offset += ABS(cds_right - right);
1028
1029 if(best_gene == NULL)
1030 {
1031 best_gene = curr;
1032 m_offset = offset;
1033 }
1034 else if(offset < m_offset)
1035 {
1036 best_gene = curr;
1037 m_offset = offset;
1038 }
1039 }
1040 }
1041
1042 curr = curr->next;
1043 }
1044 }
1045
1046 return best_gene;
1047 }
1048
1049
find_next_group(ValNodePtr head,Int4Ptr left,Int4Ptr right,ValNodePtr PNTR prev)1050 static ValNodePtr find_next_group(ValNodePtr head, Int4Ptr left, Int4Ptr right, ValNodePtr PNTR prev)
1051 {
1052 ValNodePtr list;
1053 FeatNodePtr fnp;
1054
1055 *left = -1;
1056 *right = -1;
1057
1058 list = head;
1059 *prev = NULL;
1060 while(list)
1061 {
1062 fnp = list->data.ptrvalue;
1063 if(!fnp->follower && list != head)
1064 return list;
1065 else
1066 {
1067 if(*left == -1)
1068 *left = fnp->extremes.left;
1069 else
1070 *left = MIN(*left, fnp->extremes.left);
1071 if(*right == -1)
1072 *right = fnp->extremes.right;
1073 else
1074 *right = MAX(*right, fnp->extremes.right);
1075 }
1076
1077 *prev = list;
1078 list = list->next;
1079 }
1080
1081 return NULL;
1082 }
1083
make_group_follower(ValNodePtr first,ValNodePtr last)1084 static void make_group_follower(ValNodePtr first, ValNodePtr last)
1085 {
1086 FeatNodePtr fnp;
1087
1088 while(first)
1089 {
1090 fnp = first->data.ptrvalue;
1091 fnp->follower = TRUE;
1092 if(first == last)
1093 break;
1094 else
1095 first = first->next;
1096 }
1097
1098 }
1099
insert_cds_mRNA_to_gene(ValNodePtr PNTR g_head,ValNodePtr PNTR cds_head)1100 static void insert_cds_mRNA_to_gene(ValNodePtr PNTR g_head, ValNodePtr PNTR cds_head)
1101 {
1102 ValNodePtr cds_list, prev_list = NULL, prev;
1103 ValNodePtr best_gene, curr;
1104 ValNodePtr next, g_next;
1105 Int4 left, right;
1106
1107 if(*g_head == NULL)
1108 {
1109 *g_head = *cds_head;
1110 return;
1111 }
1112
1113 cds_list = *cds_head;
1114 while(cds_list)
1115 {
1116 next = find_next_group(cds_list, &left, &right, &prev);
1117 best_gene = NULL;
1118 if(left != -1 && right != -1)
1119 {
1120 best_gene = find_best_gene(*g_head, left, right);
1121 if(best_gene != NULL)
1122 {
1123 make_group_follower(cds_list, prev);
1124 if(prev_list == NULL)
1125 *cds_head = prev->next;
1126 else
1127 prev_list->next = prev->next;
1128 prev->next = NULL;
1129 curr = *g_head;
1130 while(curr)
1131 {
1132 if(curr == best_gene)
1133 {
1134 g_next = curr->next;
1135 curr->next = cds_list;
1136 prev->next = g_next;
1137 break;
1138 }
1139 else
1140 curr = curr->next;
1141 }
1142 }
1143 }
1144 if(best_gene == NULL)
1145 prev_list = prev;
1146 cds_list = next;
1147 }
1148
1149 if(*cds_head != NULL) /*there is some leftovers*/
1150 {
1151 ValNodeLink(g_head, *cds_head);
1152 *cds_head = NULL;
1153 }
1154 }
1155
1156
1157
OrderCdsmRNA(ValNodePtr PNTR head)1158 ValNodePtr OrderCdsmRNA(ValNodePtr PNTR head)
1159 {
1160 ValNodePtr g_head;
1161 ValNodePtr cds_head, curr, next, prev;
1162 ValNodePtr mRNA_head;
1163
1164 if(head == NULL || *head == NULL)
1165 return NULL;
1166
1167 ReSetFeatNode(*head);
1168 *head = SortFeatNode(*head, NULL, NULL);
1169
1170 mRNA_head = NULL;
1171 g_head = NULL;
1172 cds_head = NULL;
1173
1174 g_head = extract_node_list(head, OBJ_SEQFEAT, 0, FEATDEF_GENE, ALL_LABEL);
1175 mRNA_head = extract_node_list(head, OBJ_SEQFEAT, 0, FEATDEF_mRNA, ALL_LABEL);
1176 cds_head = extract_node_list(head, OBJ_SEQFEAT, 0, FEATDEF_CDS, ALL_LABEL);
1177
1178 if(cds_head != NULL) /*try to group the CDS feature to the mRNA*/
1179 {
1180 curr = cds_head;
1181 prev = NULL;
1182 while(curr)
1183 {
1184 next = curr->next;
1185 curr->next = NULL;
1186 if(insert_CDS_to_best_mRNA(mRNA_head, curr))
1187 {
1188 if(prev == NULL)
1189 cds_head = next;
1190 else
1191 prev->next = next;
1192 }
1193 else
1194 {
1195 curr->next = next;
1196 prev = curr;
1197 }
1198
1199 curr = next;
1200 }
1201 }
1202
1203 if(cds_head != NULL)
1204 ValNodeLink(&mRNA_head, cds_head);
1205
1206 insert_cds_mRNA_to_gene(&g_head, &mRNA_head);
1207 if(*head != NULL)
1208 ValNodeLink(&g_head, *head);
1209
1210 *head = g_head;
1211 return g_head;
1212 }
1213
1214
1215
get_interval_height(Int4 p_class)1216 static Int4 get_interval_height(Int4 p_class)
1217 {
1218 Int4 segstyle, style;
1219
1220 style = GetMuskCParam((Int2)p_class, MSM_SEGMENT, MSM_STYLE);
1221 segstyle = (style & MSM_SEG_FORM);
1222 switch (segstyle)
1223 {
1224 case MSM_SEG_LINE:
1225 return GetMuskCParam(MSM_SEQUENCE, (Int2)segstyle, MSM_PENWIDTH);
1226 case MSM_SEG_BOX:
1227 return GetMuskCParam((Int2)p_class, MSM_SEGMENT, MSM_HEIGHT);
1228 default:
1229 return 8; /*8 is the value for the symbols*/
1230 }
1231 }
1232
1233
layout_uncompressed_group(ValNodePtr prev,ValNodePtr next,Int4Ptr y_pos,Int4Ptr group_value,Int4 next_sp,Int2 num_line,Int4Ptr com_height)1234 static Int4 layout_uncompressed_group(ValNodePtr prev, ValNodePtr next, Int4Ptr y_pos, Int4Ptr group_value, Int4 next_sp, Int2 num_line, Int4Ptr com_height)
1235 {
1236 /*this will allow the layout among the features of the same type
1237 within the group */
1238 ValNodePtr curr;
1239 ValNodePtr t_prev, t_curr;
1240 FeatNodePtr c_fnp, t_fnp;
1241 Uint1 p_feattype;
1242 Int2 group_size;
1243 Boolean has_prev = FALSE;
1244 Int2 group_start, group_stop;
1245 Int2 i;
1246 Int4 y_offset;
1247 Int4 maxline;
1248 Boolean is_end;
1249 Int4 left, right;
1250 Boolean process;
1251
1252 if(prev == NULL)
1253 return 0;
1254 p_feattype = 0;
1255 group_size = 0;
1256 group_start = 0;
1257 group_stop = 0;
1258 y_offset = 0; /*after the first line, everything should be layed down*/
1259 maxline = 0;
1260 t_prev = NULL;
1261 is_end = FALSE;
1262 curr = prev;
1263 while(!is_end)
1264 {
1265 is_end = (curr == next || curr == NULL);
1266 process = TRUE;
1267 if(!is_end)
1268 {
1269 c_fnp = curr->data.ptrvalue;
1270 if(p_feattype != c_fnp->feattype || t_prev == NULL)
1271 { /*need to find everything in the group*/
1272 ++group_size;
1273 process = FALSE;
1274 }
1275 }
1276 if(!process) /*linking it to the current size*/
1277 {
1278 if(t_prev == NULL)
1279 t_prev = curr;
1280 }
1281 else if(t_prev != NULL)
1282 {
1283 /*either the running to the end or mapped to
1284 the same type of Seq-feat*/
1285
1286 if(group_size == 1) /*there is only one sequence*/
1287 {
1288 left = group_value[2*group_start];
1289 right = group_value[2*group_start +1];
1290 i = find_f_pos(left, right, y_pos+2*y_offset, next_sp, (Int2)(num_line - y_offset));
1291 }
1292 else
1293 i = find_group_pos(y_pos+2*y_offset, next_sp, (Int2)(num_line -y_offset), group_size, group_value + group_start*2);
1294
1295
1296 if(!has_prev)
1297 {
1298 y_offset = i+group_size -1;
1299 has_prev = TRUE;
1300 }
1301 else
1302 {
1303 i+= (Int2)(y_offset);
1304 }
1305 maxline = MAX(i+group_size-1, maxline);
1306 for(t_curr = t_prev; t_curr != curr; t_curr = t_curr->next)
1307 {
1308 t_fnp = t_curr->data.ptrvalue;
1309 t_fnp->line = i+1;
1310 if(i != -1)
1311 {
1312 com_height[i] = MAX(com_height[i], t_fnp->bottom);
1313 ++i;
1314 }
1315 }
1316 t_prev = curr;
1317 group_start += group_size;
1318 group_size = 1;
1319 }
1320
1321 p_feattype = c_fnp->feattype;
1322 if(!is_end)
1323 curr = curr->next;
1324 }
1325
1326 return maxline;
1327 }
1328
1329 /***********************************************************************
1330 *
1331 * Int4 LayoutFeatNode(head, top, next_sp, space, maxScale, check_interval)
1332 * Layout the fnp->line, inp->line according to Maximun packing, return
1333 * the next availabel space for drawing
1334 * head: the FeatNode. will be sorted
1335 * top: the current y position
1336 * next_sp: min. space for separating two neibouring objects
1337 * space: the vertical space consumed by each line
1338 * maxScale: max scale for the picture
1339 * check_interval: layout each interval?
1340 *
1341 *
1342 ************************************************************************/
LayoutFeatNode(ValNodePtr head,Int4 top,Int4 maxScale,Int4 next_sp,Boolean show_label,Boolean compress)1343 Int4 LayoutFeatNode(ValNodePtr head, Int4 top, Int4 maxScale, Int4 next_sp, Boolean show_label, Boolean compress)
1344 {
1345 Int4Ptr y_pos, com_height; /*com_height: storing height for compressed layout*/
1346
1347 Int4 maxHeight = 0;
1348 Int4 height;
1349 Int2 maxline = 0, group_size;
1350 Int2 i, k;
1351 Int4 left, right, p_left, p_right;
1352 Int4 line_scale; /*scale for showing only the two-ends of interval*/
1353 Boolean drawline; /*draw a line between the two ends of the interval*/
1354
1355 Int2 num_line = 0;
1356 ValNodePtr vnp, curr, prev;
1357 FeatNodePtr fnp, c_fnp;
1358 Int2 ptype = 0; /*previous feature type. to save some time*/
1359 Int2 p_class;
1360 FonT font = NULL;
1361 Int4 font_height = 0;
1362 Int4 f_space; /*space separate features at different level*/
1363 Boolean show_trunc = FALSE;
1364 Int4 segstyle, labelstyle;
1365 Int4 cur_line, y_next;
1366 Boolean has_prev = FALSE;
1367 Int4 label_len;
1368 Uint1 label_align; /*the alignment of a labe: top, left, bottom, right*/
1369 Int4Ptr group_value;
1370
1371 if(head == NULL)
1372 return top;
1373
1374 line_scale = GetMuskCParam(MSM_TOPSTYLE, MSM_ENDS, MSM_SCALE);
1375 drawline = (maxScale >= line_scale);
1376 f_space = GetMuskCParam(MSM_TOPSTYLE, MSM_SPACE, MSM_HEIGHT);
1377 /*the alignment of a label in relation to the object*/
1378 label_align = (Uint1)GetMuskCParam(MSM_TOPSTYLE, MSM_LABEL, MSM_STYLE);
1379
1380 num_line = (Int2)get_vnp_num(head);
1381
1382 /*for layout each level*/
1383 y_pos = MemNew((size_t)2*num_line * sizeof (Int4));
1384 com_height = MemNew((size_t)num_line* sizeof (Int4));
1385 group_value = MemNew((size_t)2*num_line* sizeof (Int4));
1386
1387 k = 0;
1388 labelstyle = NO_LABEL;
1389 vnp = head;
1390 prev = NULL;
1391 label_len = 0;
1392 group_size = 0;
1393 while(vnp)
1394 {
1395 fnp = vnp->data.ptrvalue;
1396
1397 /*get the height of the box and the font of label*/
1398 p_class = get_current_class(fnp);
1399 if(p_class == MSM_SEQUENCE) /*assume it is a sequence*/
1400 drawline = FALSE;
1401 if(!has_prev || (p_class != ptype)) /*get the styles*/
1402 {
1403 has_prev = TRUE;
1404 if(drawline && fnp->landmark == FALSE)
1405 height = GetMuskCParam(p_class, MSM_SEG_BORD, MSM_PENWIDTH);
1406 else
1407 {
1408 height = get_interval_height(p_class);
1409 segstyle = GetMuskCParam(p_class, MSM_SEGMENT, MSM_STYLE);
1410 labelstyle = GetMuskCParam(p_class, MSM_FLABEL, MSM_STYLE);
1411 show_trunc = (Boolean)(segstyle & (Int4)MSM_SEG_SHOWTRUNC);
1412 if(show_label)
1413 {
1414 font = (FonT)GetMuskCParam(p_class, MSM_FLABEL, MSM_FONT);
1415 SelectFont(font);
1416 font_height = FontHeight();
1417 }
1418 }
1419 ptype = p_class;
1420 }
1421
1422 /*convert label to type, content, both, summary format*/
1423 left = fnp->extremes.left;
1424 right = fnp->extremes.right;
1425 /*if(fnp->extremes.l_trunc && show_trunc)
1426 left -= (6*maxScale);
1427 if(fnp->extremes.r_trunc && show_trunc)
1428 right += (6*maxScale);*/
1429 fnp->labelHeight = font_height;
1430 if(compress && fnp->follower)
1431 {
1432 fnp->labelHeight = 0;
1433 if(label_align == MSM_LABEL_LEFT)
1434 {
1435 if(left < p_left)
1436 {
1437 fnp->labelHeight = font_height;
1438 if(prev != NULL)
1439 {
1440 c_fnp = prev->data.ptrvalue;
1441 c_fnp->labelHeight = 0;
1442 }
1443 }
1444 }
1445 if(label_align == MSM_LABEL_RIGHT)
1446 {
1447 if(right > p_right)
1448 {
1449 fnp->labelHeight = font_height;
1450 if(prev != NULL)
1451 {
1452 c_fnp = prev->data.ptrvalue;
1453 c_fnp->labelHeight = 0;
1454 }
1455 }
1456 }
1457
1458 }
1459
1460 /*temporary store the value*/
1461 fnp->bottom = height;
1462 if(fnp->labelHeight!= 0)
1463 {
1464 label_len = StringWidth(fnp->label);
1465 fnp->label_len = label_len;
1466 ModLabelInterval(&left, &right, maxScale, label_len, label_align);
1467 }
1468
1469 /*load the data for each level*/
1470 if(!(fnp->follower)) /*start of a new group*/
1471 {
1472 if( prev != NULL) /*process the previous group*/
1473 {
1474 if(compress)
1475 {
1476 i = find_f_pos(p_left, p_right, y_pos, next_sp, (Int2)num_line);
1477 com_height[i] = MAX(com_height[i], maxHeight);
1478 maxline = MAX(i, maxline);
1479 for(curr = prev; curr != vnp; curr = curr->next)
1480 {
1481 c_fnp = curr->data.ptrvalue;
1482 c_fnp->line = i+1;
1483 }
1484 }
1485 else
1486 {
1487 i = (Int2)layout_uncompressed_group(prev, vnp, y_pos, group_value, next_sp, num_line, com_height);
1488 maxline = MAX(i, maxline);
1489 }
1490
1491 }
1492 p_left = left;
1493 p_right = right;
1494 prev = vnp;
1495 group_size = 1;
1496 group_value[2*(group_size-1)] = left;
1497 group_value[2*(group_size-1) +1] = right;
1498 maxHeight = height;
1499 }
1500 else
1501 {
1502 p_left = MIN(left, p_left);
1503 p_right = MAX(right, p_right);
1504 maxHeight = MAX(height, maxHeight);
1505 ++ group_size;
1506 group_value[2*(group_size-1)] = left;
1507 group_value[2*(group_size-1) +1] = right;
1508 }
1509 vnp = vnp->next;
1510 }
1511
1512 if(prev != NULL) /*process the last one*/
1513 {
1514 if(compress)
1515 {
1516 i = find_f_pos(p_left, p_right, y_pos, next_sp, (Int2)num_line);
1517 com_height[i] = MAX(com_height[i], maxHeight);
1518 maxline = MAX(i, maxline);
1519 for(curr = prev; curr != vnp; curr = curr->next)
1520 {
1521 c_fnp = curr->data.ptrvalue;
1522 c_fnp->line = i+1;
1523 }
1524 }
1525 else
1526 {
1527 i = (Int2)layout_uncompressed_group(prev, vnp, y_pos, group_value, next_sp, num_line, com_height);
1528 maxline = MAX(i, maxline);
1529 }
1530 }
1531
1532 MemFree(y_pos);
1533 MemFree(group_value);
1534
1535
1536 cur_line = top;
1537 y_next = top;
1538 for(i = 0; i<= maxline; ++i) /*Layout each line in each level*/
1539 {
1540 maxHeight = 0;
1541 for(vnp = head; vnp != NULL; vnp = vnp->next)
1542 {
1543 fnp = vnp->data.ptrvalue;
1544 if(fnp->line == i+1)
1545 {
1546 if(!(fnp->follower))
1547 font_height = fnp->labelHeight;
1548 maxHeight = MAX(maxHeight, font_height);
1549 top = cur_line;
1550 top -= (com_height[i] - fnp->bottom)/2;
1551 switch(label_align)
1552 {
1553 case MSM_LABEL_TOP:
1554 top -= font_height;
1555 break;
1556 case MSM_LABEL_LEFT:
1557 case MSM_LABEL_RIGHT:
1558 if(font_height > com_height[i])
1559 top -= (font_height - com_height[i])/2;
1560 break;
1561 default:
1562 break;
1563 }
1564 fnp->top = top;
1565 fnp->bottom = top - fnp->bottom;
1566 }
1567 }
1568 switch(label_align)
1569 {
1570 case MSM_LABEL_TOP:
1571 case MSM_LABEL_BOTTOM:
1572 cur_line -= (maxHeight + com_height[i]);
1573 break;
1574 case MSM_LABEL_LEFT:
1575 case MSM_LABEL_RIGHT:
1576 cur_line -= MAX(maxHeight, com_height[i]);
1577 break;
1578 default:
1579 break;
1580 }
1581 cur_line -= f_space;
1582 }
1583
1584 MemFree(com_height);
1585
1586 return cur_line;
1587 }
1588
1589
1590
1591
modify_insert_fnode(ValNodePtr fnode,Int4 offset)1592 void modify_insert_fnode(ValNodePtr fnode, Int4 offset)
1593 {
1594 FeatNodePtr fnp;
1595 ValNodePtr ival;
1596 IvalNodePtr inp;
1597
1598 while(fnode)
1599 {
1600 fnp = fnode->data.ptrvalue;
1601 (fnp->extremes.left) += offset;
1602 (fnp->extremes.right) += offset;
1603
1604 for(ival = fnp->interval; ival!=NULL; ival = ival->next)
1605 {
1606 inp = ival->data.ptrvalue;
1607 (inp->gr.left) += offset;
1608 (inp->gr.right) += offset;
1609 }
1610
1611 fnode = fnode->next;
1612 }
1613 }
1614
LayoutInsertions(AlignNodePtr anp,Int4 maxScale,Int4 cur_line,Int4 height,Int4 space,Int4 l_bound,Int4 r_bound)1615 static Int4 LayoutInsertions(AlignNodePtr anp, Int4 maxScale, Int4 cur_line, Int4 height, Int4 space, Int4 l_bound, Int4 r_bound)
1616 {
1617 AlignSegPtr asp;
1618 Int4 insert_ypos[MAX_INS];
1619 Int2 i,level;
1620 Int4 left, seglen, ins;
1621 Int4 next_line, feat_line;
1622 Boolean has_insertion = FALSE;
1623 Int4 offset; /*offset between the left pos and the insert pos*/
1624 ValNodePtr repeat_node;
1625
1626
1627 if(anp == NULL || anp->segs== NULL)
1628 return cur_line;
1629
1630 MemSet((Pointer)(insert_ypos), 0, (size_t)MAX_INS * sizeof(Int4));
1631 level = 0;
1632 for(asp = anp->segs; asp !=NULL; asp = asp->next)
1633 {
1634 if(asp->type == INS_SEG)
1635 {
1636 has_insertion = TRUE;
1637 ins = asp->ins_pos;
1638 seglen = asp->gr.right;
1639
1640 asp->line = find_insert_ypos(&left, seglen, ins, l_bound, r_bound, insert_ypos, 0, MAX_INS);
1641 /*asp->line = find_insert_ypos(&left, seglen, ins, l_bound, r_bound, insert_ypos, 3*maxScale, MAX_INS);*/
1642
1643 /*resume the previous layout for FeatNode*/
1644 /*offset = asp->gr.left - asp->ins_pos;
1645 if(offset != 0)
1646 modify_insert_fnode(asp->cnp, (-offset));*/
1647 asp->gr.left = left;
1648 level = MAX((Int2)(asp->line), level);
1649 }
1650 }
1651
1652 if(!has_insertion)
1653 return cur_line;
1654
1655 for(i = 0; i<(level+1); ++i)
1656 {
1657 next_line = cur_line - space - height - space;
1658 for(asp = anp->segs; asp !=NULL; asp = asp->next)
1659 {
1660 if(asp->type == INS_SEG && asp->line == i)
1661 {
1662 asp->top = cur_line;
1663 asp->bottom = asp->top - height;
1664 if(asp->cnp != NULL)
1665 {
1666 /*offset = asp->gr.left - (asp->ins_pos - asp->gr.right +1);*/
1667 offset = asp->gr.left - asp->ins_pos;
1668 modify_insert_fnode(asp->cnp, offset);
1669 ReSetFeatNode(asp->cnp);
1670 repeat_node = strip_repeat_feature(&(asp->cnp));
1671 feat_line = LayoutFeatNode(asp->cnp, (asp->bottom - space), maxScale, 0, FALSE, FALSE);
1672 if(repeat_node != NULL)
1673 ValNodeLink(&(asp->cnp), repeat_node);
1674 next_line = MIN(feat_line, next_line);
1675 }
1676 }
1677 }
1678 cur_line = next_line ;
1679 }
1680
1681 return cur_line;
1682 }
1683
1684
1685
1686 /**********************************************************************
1687 *
1688 * merge_same_itemID(head, itemID)
1689 * search in the list of FeatNode to link all the FeatNode that has
1690 * the same itemID.
1691 * head: the list of FeatNode
1692 * itemID: the itemID in search
1693 * return the list of FeatNode with the same itemID
1694 *
1695 **********************************************************************/
merge_same_itemID(ValNodePtr PNTR head,Uint4 itemID)1696 ValNodePtr merge_same_itemID(ValNodePtr PNTR head, Uint4 itemID)
1697 {
1698 FeatNodePtr fnp, l_fnp;
1699 ValNodePtr curr, prev = NULL, next;
1700 ValNodePtr list = NULL;
1701
1702 curr = *head;
1703 while(curr)
1704 {
1705 fnp = curr->data.ptrvalue;
1706 next = curr->next;
1707 if(fnp->itemID == (Uint2)itemID)
1708 {
1709 if(prev == NULL)
1710 *head = curr->next;
1711 else
1712 prev->next = curr->next;
1713 curr->next = NULL;
1714 if(list == NULL)
1715 list = curr;
1716 else
1717 {
1718 l_fnp = list->data.ptrvalue;
1719 l_fnp->extremes.right = fnp->extremes.right;
1720 l_fnp->extremes.r_trunc = fnp->extremes.r_trunc;
1721 if(fnp->interval != NULL)
1722 {
1723 ValNodeLink(&(l_fnp->interval), (fnp->interval));
1724 fnp->interval = NULL;
1725 }
1726 FreeFeatureList(curr);
1727 }
1728
1729 curr = next;
1730 }
1731 else
1732 {
1733 prev = curr;
1734 curr = curr->next;
1735 }
1736 }
1737
1738 return list;
1739 }
1740
strip_repeat_feature(ValNodePtr PNTR f_node)1741 ValNodePtr strip_repeat_feature(ValNodePtr PNTR f_node)
1742 {
1743 ValNodePtr list = NULL, curr;
1744 ValNodePtr next;
1745 ValNodePtr prev;
1746 FeatNodePtr fnp;
1747
1748 prev = NULL;
1749 curr = *f_node;
1750 if(curr == NULL)
1751 return NULL;
1752 while(curr)
1753 {
1754 next = curr->next;
1755 fnp = curr->data.ptrvalue;
1756 if(fnp->feattype == FEATDEF_repeat_region || fnp->feattype == FEATDEF_repeat_unit)
1757 {
1758 curr->next = NULL;
1759 ValNodeLink(&list, curr);
1760 if(prev == NULL)
1761 *f_node = next;
1762 else
1763 prev->next = next;
1764 }
1765 else
1766 prev = curr;
1767 curr = next;
1768 }
1769
1770 return list;
1771 }
1772
1773 /******************************************************************
1774 *
1775 * check to see if the master line has any follower. If does,
1776 * add the length of the followers
1777 *
1778 *******************************************************************/
modify_master_line(ValNodePtr vnp,Int4Ptr m_left,Int4Ptr m_right,Int4 maxScale,Uint1 label_align)1779 static Boolean modify_master_line(ValNodePtr vnp, Int4Ptr m_left, Int4Ptr m_right, Int4 maxScale, Uint1 label_align)
1780 {
1781 AlignNodePtr anp;
1782 Int4 left, right;
1783 Int4 label_len;
1784 Boolean retval = FALSE;
1785
1786 while(vnp)
1787 {
1788 anp = vnp->data.ptrvalue;
1789 if(anp->follower == FALSE)
1790 return retval;
1791 else
1792 retval = TRUE;
1793 anp = vnp->data.ptrvalue;
1794 left = anp->extremes.left;
1795 right = anp->extremes.right;
1796 if(anp->label != NULL)
1797 {
1798 label_len = StringWidth(anp->label);
1799 ModLabelInterval(&left, &right, maxScale, label_len, label_align);
1800 }
1801 if(anp->extremes.l_trunc == TRUE)
1802 left -= (6*maxScale);
1803 if(anp->extremes.r_trunc == TRUE)
1804 right += (6*maxScale);
1805 *m_left = MIN(*m_left, left);
1806 *m_right = MAX(*m_right, right);
1807
1808 vnp = vnp->next;
1809 }
1810 return retval;
1811 }
1812
1813 typedef struct align_feature{
1814 Uint4 itemID;
1815 Int4 pos;
1816 Int4 e_left, e_right;
1817 Int4 p_left, p_right;
1818 FeatNodePtr fnp;
1819 }AlignFeature, PNTR AlignFeaturePtr;
1820
1821 /*create a summarry of the features in alignment. Get the extremities. So,
1822 it only needed to be layed out once */
load_align_feature_list(ValNodePtr PNTR list,ValNodePtr fnp_list)1823 static void load_align_feature_list(ValNodePtr PNTR list, ValNodePtr fnp_list)
1824 {
1825 ValNodePtr curr;
1826 FeatNodePtr fnp;
1827 ValNodePtr prev = NULL;
1828 AlignFeaturePtr afp;
1829
1830 curr = *list;
1831 fnp = fnp_list->data.ptrvalue;
1832 if(fnp->feattype == FEATDEF_repeat_region || fnp->feattype == FEATDEF_repeat_unit)
1833 return;
1834 while(curr)
1835 {
1836 if(curr->choice == fnp_list->choice)
1837 {
1838 afp = curr->data.ptrvalue;
1839
1840 if(afp->itemID == fnp->itemID)
1841 {
1842 afp->e_left = MIN(afp->e_left, fnp->extremes.left);
1843 afp->e_right = MAX(afp->e_right, fnp->extremes.right);
1844 return;
1845 }
1846 }
1847
1848 prev = curr;
1849 curr = curr->next;
1850 }
1851
1852 curr = ValNodeNew(NULL);
1853 curr->choice = fnp_list->choice;
1854 afp = MemNew(sizeof(AlignFeature));
1855 afp->itemID = fnp->itemID;
1856 afp->e_left = fnp->extremes.left;
1857 afp->e_right = fnp->extremes.right;
1858 afp->fnp = fnp;
1859 curr->data.ptrvalue = afp;
1860
1861 if(prev == NULL)
1862 *list = curr;
1863 else
1864 prev->next = curr;
1865 }
1866
1867
1868
LayoutAlignmentFeature(AlignSegPtr h_asp,Int4 top,Int4 space,Int4 maxScale)1869 static Int4 LayoutAlignmentFeature (AlignSegPtr h_asp, Int4 top, Int4 space, Int4 maxScale)
1870 {
1871 ValNodePtr list, curr;
1872 ValNodePtr fnp_list;
1873 FeatNodePtr fnp;
1874 ValNodePtr layout_list;
1875 AlignFeaturePtr afp;
1876 Int4 n_y_pos;
1877 AlignSegPtr asp;
1878
1879 list = NULL;
1880 n_y_pos = top;
1881 asp = h_asp;
1882 while(asp)
1883 {
1884 if(asp->type != INS_SEG)
1885 {
1886 fnp_list = asp->cnp;
1887 while(fnp_list)
1888 {
1889 load_align_feature_list(&list, fnp_list);
1890 fnp_list = fnp_list->next;
1891 }
1892 }
1893 asp = asp->next;
1894 }
1895
1896 if(list == NULL)
1897 return top;
1898
1899 top -= space;
1900
1901 layout_list = NULL;
1902 for(curr = list; curr != NULL; curr = curr->next)
1903 {
1904 afp = curr->data.ptrvalue;
1905 afp->p_left = afp->fnp->extremes.left;
1906 afp->p_right = afp->fnp->extremes.right;
1907 afp->fnp->extremes.left = afp->e_left;
1908 afp->fnp->extremes.right = afp->e_right;
1909
1910 ValNodeAddPointer(&layout_list, curr->choice, afp->fnp);
1911 }
1912
1913 if(layout_list != NULL)
1914 {
1915 n_y_pos = LayoutFeatNode (layout_list, top, maxScale, 0, FALSE, FALSE);
1916 for(curr = list; curr != NULL; curr = curr->next)
1917 {
1918 afp = curr->data.ptrvalue;
1919 afp->fnp->extremes.left = afp->p_left;
1920 afp->fnp->extremes.right = afp->p_right;
1921
1922 for(asp = h_asp; asp != NULL; asp = asp->next)
1923 {
1924 if(asp->type != INS_SEG)
1925 {
1926 for(fnp_list = asp->cnp; fnp_list != NULL; fnp_list =
1927 fnp_list->next)
1928 {
1929 fnp = fnp_list->data.ptrvalue;
1930 if(fnp != afp->fnp && fnp->itemID == afp->fnp->itemID
1931 && fnp_list->choice == curr->choice)
1932 {
1933 fnp->top = afp->fnp->top;
1934 fnp->bottom = afp->fnp->bottom;
1935 }
1936 }
1937 }
1938 }
1939 }
1940 ValNodeFree(layout_list);
1941 }
1942
1943 if(list != NULL)
1944 ValNodeFreeData(list);
1945 return n_y_pos;
1946 }
1947
load_status_flag(ValNodePtr prev,ValNodePtr curr,Int4 left,Int4 right)1948 static void load_status_flag(ValNodePtr prev, ValNodePtr curr, Int4 left, Int4 right)
1949 {
1950 ValNodePtr vnp;
1951 BoolPtr status;
1952
1953 for(vnp = prev; vnp != NULL; vnp = vnp->next)
1954 {
1955 status = (BoolPtr)(vnp->data.ptrvalue);
1956 MemSet(status+left, 1, (size_t)(right - left + 1) *sizeof(Boolean));
1957 if(vnp == curr)
1958 break;
1959 }
1960 }
1961
init_new_status_list(Int4 level,Int4 size)1962 static ValNodePtr init_new_status_list(Int4 level, Int4 size)
1963 {
1964 ValNodePtr list;
1965 Int4 i;
1966 BoolPtr status;
1967
1968 list = NULL;
1969 for(i = 0; i<level; ++i)
1970 {
1971 status = MemNew((size_t)(size+1) * sizeof(Boolean));
1972 ValNodeAddPointer(&list, 0, status);
1973 }
1974
1975 return list;
1976 }
1977
figure_alignment_level(ValNodePtr PNTR line_status_list,Int4 left,Int4 right,Int4 num_seq,Int4 size)1978 static Int4 figure_alignment_level(ValNodePtr PNTR line_status_list, Int4 left, Int4 right, Int4 num_seq, Int4 size)
1979 {
1980 Int4 i;
1981 Int4 c_num_seq;
1982 Int4 max_level = 0;
1983 BoolPtr line_status;
1984 ValNodePtr list;
1985 Boolean found;
1986 ValNodePtr p_node, n_node;
1987
1988 c_num_seq = 0;
1989 p_node = NULL;
1990 max_level = 0;
1991 for(list = *line_status_list; list != NULL; list = list->next)
1992 {
1993 line_status = list->data.ptrvalue;
1994 found = TRUE;
1995 for(i = left; i<= right; ++i)
1996 {
1997 if(line_status[i])
1998 {
1999 found = FALSE;
2000 break;
2001 }
2002 }
2003 if(!found)
2004 {
2005 c_num_seq = 0;
2006 p_node = NULL;
2007 }
2008 else
2009 {
2010 ++c_num_seq;
2011 if(p_node == NULL)
2012 p_node = list;
2013 if(c_num_seq == num_seq)
2014 {
2015 load_status_flag(p_node, list, left, right);
2016 return (max_level + 1 - (c_num_seq -1));
2017 }
2018 }
2019 ++max_level;
2020 }
2021
2022 n_node = init_new_status_list(num_seq-c_num_seq, size);
2023 if(p_node == NULL)
2024 p_node = n_node;
2025 ValNodeLink(line_status_list, n_node);
2026 load_status_flag(p_node, NULL, left, right);
2027 return (max_level - c_num_seq + 1);
2028
2029
2030 }
2031
2032
mod_left_right_by_scale(Int4Ptr left,Int4Ptr right,Int4 maxScale)2033 static void mod_left_right_by_scale(Int4Ptr left, Int4Ptr right, Int4 maxScale)
2034 {
2035 Int4 t_left, t_right;
2036
2037 t_left = *left;
2038 t_right = *right;
2039
2040 if(maxScale > 1)
2041 {
2042 *left = t_left/maxScale;
2043 if(t_left%maxScale > 0)
2044 *left -=1;
2045 *right = t_right/maxScale;
2046 if(t_right%maxScale > 0)
2047 *right +=1;
2048
2049 }
2050 }
2051
figure_alignment_boundary(AlignNodePtr anp,Int4Ptr pleft,Int4Ptr pright,Int4 max_len,Uint1 label_align,Int4 maxScale)2052 static void figure_alignment_boundary(AlignNodePtr anp, Int4Ptr pleft,
2053 Int4Ptr pright, Int4 max_len, Uint1 label_align, Int4 maxScale)
2054 {
2055 Int4 left, right;
2056 Int4 label_len;
2057
2058 left = anp->extremes.left;
2059 right = anp->extremes.right;
2060 mod_left_right_by_scale(&left, &right, maxScale);
2061
2062
2063 if(anp->label != NULL)
2064 {
2065 label_len = StringWidth(anp->label);
2066 ModLabelInterval(&left, &right, 1, label_len, label_align);
2067 }
2068 if(anp->extremes.l_trunc == TRUE)
2069 left -= 14;
2070
2071 if(anp->extremes.r_trunc == TRUE)
2072 right += 14;
2073 else
2074 right += 2;
2075 *pleft = MAX(left, 0);
2076 *pright = MIN(right, max_len);
2077 }
2078
2079
is_level_overlap(ValNodePtr PNTR pleft_list,ValNodePtr PNTR pright_list,Int4 left,Int4 right,AlignNodePtr anp)2080 static Boolean is_level_overlap(ValNodePtr PNTR pleft_list,
2081 ValNodePtr PNTR pright_list, Int4 left, Int4 right, AlignNodePtr anp)
2082 {
2083 Int4 l_left, l_right;
2084 Int4 level = 0;
2085 ValNodePtr left_list, right_list;
2086
2087 left_list = *pleft_list;
2088 right_list = *pright_list;
2089 anp->line = 0;
2090 while(left_list && right_list)
2091 {
2092 l_left = left_list->data.intvalue;
2093 l_right = right_list->data.intvalue;
2094
2095 if(left >= l_right || right <= l_left)
2096 {
2097 left_list->data.intvalue = MIN(l_left, left);
2098 right_list->data.intvalue = MAX(l_right, right);
2099 anp->line = level;
2100 return FALSE;
2101 }
2102
2103 left_list = left_list->next;
2104 right_list = right_list->next;
2105 ++level;
2106 }
2107
2108 ValNodeAddInt(pleft_list, 0, left);
2109 ValNodeAddInt(pright_list, 0, right);
2110 anp->line = level;
2111 return TRUE;
2112 }
2113
find_align_line_number(AlignNodePtr anp,ValNodePtr t_next_list,Uint1 label_align,ValNodePtr PNTR pnext,ValNodePtr PNTR line_status_list,Int4 size,Int4 maxScale)2114 static Int4 find_align_line_number(AlignNodePtr anp,
2115 ValNodePtr t_next_list, Uint1 label_align, ValNodePtr PNTR pnext,
2116 ValNodePtr PNTR line_status_list, Int4 size, Int4 maxScale )
2117 {
2118 Int4 m_left, m_right;
2119 Int4 left, right;
2120 AlignNodePtr n_anp;
2121 ValNodePtr left_list= NULL, right_list = NULL;
2122 Int4 level = 0;
2123 Int4 line;
2124 ValNodePtr next_list;
2125
2126 if(anp == NULL)
2127 return -1;
2128
2129 *pnext = t_next_list;
2130
2131 figure_alignment_boundary(anp, &left, &right, size, label_align, maxScale);
2132 ValNodeAddInt(&left_list, 1, left);
2133 ValNodeAddInt(&right_list, 1, right);
2134 m_left = left;
2135 m_right = right;
2136 level = 1;
2137 anp->line = 0;
2138 next_list = t_next_list;
2139
2140 while(next_list)
2141 {
2142 n_anp = next_list->data.ptrvalue;
2143 if(n_anp->follower == TRUE)
2144 {
2145 n_anp->line = 0;
2146 figure_alignment_boundary(n_anp, &left, &right, size, label_align, maxScale);
2147 if(is_level_overlap(&left_list, &right_list, left, right, n_anp))
2148 ++level;
2149 m_left = MIN(m_left, left);
2150 m_right = MAX(m_right, right);
2151 *pnext = next_list->next;
2152 next_list = next_list->next;
2153 }
2154 else
2155 break;
2156 }
2157
2158 line = figure_alignment_level(line_status_list,
2159 m_left, m_right, level, size);
2160 line -= 1;
2161 anp->line += line;
2162 for(next_list = t_next_list; next_list != NULL && next_list != *pnext; next_list = next_list->next)
2163 {
2164 n_anp = next_list->data.ptrvalue;
2165 n_anp->line += line;
2166 }
2167 ValNodeFree(left_list);
2168 ValNodeFree(right_list);
2169 return (line + level -1);
2170 }
2171
get_anp_extremes(ValNodePtr anp_list,Int4Ptr m_left,Int4Ptr m_right)2172 static Boolean get_anp_extremes(ValNodePtr anp_list, Int4Ptr m_left, Int4Ptr m_right)
2173 {
2174 AlignNodePtr anp;
2175
2176 *m_left = -1;
2177 *m_right = -1;
2178 while(anp_list)
2179 {
2180 anp = anp_list->data.ptrvalue;
2181 if(*m_left == -1 || *m_left > anp->extremes.left)
2182 *m_left = anp->extremes.left;
2183
2184 if(*m_right == -1 || *m_right < anp->extremes.right)
2185 *m_right = anp->extremes.right;
2186
2187 anp_list = anp_list->next;
2188 }
2189
2190 return (*m_left != -1);
2191 }
2192
2193
2194
2195
2196
2197 /**********************************************************************
2198 *
2199 * LayoutAlignNode(head, top, maxScale)
2200 * head: the list of AlignNode
2201 * top: the current y position
2202 * maxScale: the maximum scale
2203 * the labels on the features of a sequence is not counted in the layout
2204 *
2205 ***********************************************************************/
LayoutAlignNode(ValNodePtr head,Int4 top,Int4 maxScale,Int4 height)2206 Int4 LayoutAlignNode (ValNodePtr head, Int4 top, Int4 maxScale, Int4 height)
2207 {
2208 Int4 num = 0;
2209 Int4 i, j, k;
2210 Int4 left, right, m_left, m_right;
2211
2212 ValNodePtr vnp, curr, next;
2213 AlignNodePtr anp;
2214 AlignSegPtr asp;
2215 Int4 cur_line, next_line;
2216 Int4 ins_line;
2217 Int4 font_height = 0; /*height of the Font*/
2218 Int4 h_font_height, h_height;
2219 Int4 master_height;
2220 Int4 space; /*the space separate the two object*/
2221 FonT font;
2222 Uint1 label_align;
2223 Int4 font_offset = 0, h_font_offset;
2224 Boolean is_first;
2225 ValNodePtr line_status_list = NULL;
2226
2227
2228
2229 curr = head;
2230 if(curr == NULL)
2231 return top;
2232 SortSameSeqInAlignNode(head);
2233
2234 space = GetMuskCParam(MSM_TOPSTYLE, MSM_SPACE, MSM_HEIGHT);
2235 label_align = (Uint1)GetMuskCParam(MSM_TOPSTYLE, MSM_LABEL, MSM_STYLE);
2236 font = (FonT)GetMuskCParam(MSM_SEQUENCE, MSM_SLABEL, MSM_FONT);
2237 SelectFont(font);
2238 font_height = FontHeight();
2239 master_height = GetMuskCParam(MSM_SEQUENCE, MSM_SEGMENT, MSM_HEIGHT);
2240
2241 get_anp_extremes(head, &m_left, &m_right);
2242 mod_left_right_by_scale(&m_left, &m_right, maxScale);
2243
2244
2245 vnp = head;
2246 k = -1;
2247 line_status_list = NULL;
2248 while(vnp)
2249 {
2250 anp = vnp->data.ptrvalue;
2251 i = find_align_line_number(anp, vnp->next,
2252 label_align, &next, &line_status_list, m_right, maxScale);
2253 if(i > k)
2254 k = i;
2255 vnp = next;
2256 }
2257
2258 if(line_status_list != NULL)
2259 ValNodeFreeData(line_status_list);
2260
2261
2262 font_offset = 0;
2263 switch(label_align)
2264 {
2265 case MSM_LABEL_TOP:
2266 case MSM_LABEL_BOTTOM:
2267 font_offset = font_height;
2268 break;
2269 case MSM_LABEL_LEFT:
2270 case MSM_LABEL_RIGHT:
2271 if(font_height > height)
2272 font_offset = (font_height - height);
2273 break;
2274 default:
2275 break;
2276 }
2277
2278 cur_line = top; /*layout the actural y positions*/
2279 h_font_height = font_height;
2280 h_font_offset = font_offset;
2281 h_height = height;
2282 for(j=0; j<=k; ++j)
2283 {
2284 is_first = TRUE;
2285 for(vnp=(head); vnp!=NULL; vnp=vnp->next)
2286 {
2287 anp = vnp->data.ptrvalue;
2288 if(anp->line == j)
2289 {
2290 font_height = (anp->label) ? h_font_height : 0;
2291 font_offset= (anp->label) ? h_font_offset : 0;
2292 if(anp->is_master)
2293 height = master_height;
2294 else
2295 height = h_height;
2296 if(is_first)
2297 {
2298 next_line = cur_line - height - font_offset - space;
2299 is_first = FALSE;
2300 }
2301 switch(label_align)
2302 {
2303 case MSM_LABEL_TOP:
2304 anp->top = cur_line - font_height;
2305 break;
2306 case MSM_LABEL_BOTTOM:
2307 anp->top = cur_line;
2308 break;
2309 case MSM_LABEL_LEFT:
2310 case MSM_LABEL_RIGHT:
2311 anp->top = cur_line - font_offset/2;
2312 break;
2313 default:
2314 break;
2315 }
2316
2317 anp->bottom = anp->top- height;
2318
2319 left = anp->extremes.left;
2320 right = anp->extremes.right;
2321 ins_line = anp->bottom - space;
2322
2323 /*Layout the Non-insertions*/
2324 /*collect all the features in the alignment */
2325 for(asp = anp->segs; asp !=NULL; asp = asp->next)
2326 {
2327 if(asp->type != INS_SEG)
2328 {
2329 if(asp->type == GAP_SEG)
2330 {
2331 asp->bottom = anp->bottom + height/2;
2332 asp->top = asp->bottom;
2333 }
2334 else
2335 {
2336 asp->bottom = anp->bottom;
2337 asp->top = asp->bottom + height;
2338 }
2339 }
2340 }
2341 ins_line = LayoutAlignmentFeature (anp->segs, anp->bottom, space, maxScale);
2342 ins_line = LayoutInsertions(anp, maxScale, ins_line, height, space, left, right);
2343 if(anp->extremes.l_trunc == TRUE|| anp->extremes.r_trunc == TRUE)
2344 ins_line = MIN(ins_line, anp->bottom - space - 8);
2345 next_line = MIN(next_line, ins_line);
2346
2347 }
2348 }
2349 cur_line = next_line;
2350 }
2351
2352 return next_line;
2353 }
2354
2355
2356 /****************************************************************
2357 *
2358 * extract a list of AlignNode that matches the sip
2359 * or things with the same clone id
2360 *
2361 *****************************************************************/
extract_match_seqid_list(ValNodePtr PNTR n_curr,SeqIdPtr sip,CharPtr clone_id,Int2Ptr num_follower)2362 static ValNodePtr extract_match_seqid_list(ValNodePtr PNTR n_curr, SeqIdPtr sip, CharPtr clone_id, Int2Ptr num_follower)
2363 {
2364 ValNodePtr curr, prev, next;
2365 ValNodePtr list;
2366 AlignNodePtr anp;
2367
2368 list = NULL;
2369 prev = NULL;
2370 curr = *n_curr;
2371 *num_follower = 0;
2372 while(curr)
2373 {
2374 next = curr->next;
2375 anp = curr->data.ptrvalue;
2376 if(SeqIdMatch(anp->sip, sip) ||
2377 (clone_id != NULL && StringCmp(anp->clone_id, clone_id) == 0))
2378 {
2379 anp->follower = TRUE;
2380 if(prev == NULL)
2381 *n_curr = curr->next;
2382 else
2383 prev->next = curr->next;
2384 curr->next = NULL;
2385 ValNodeLink(&list, curr);
2386 ++(*num_follower);
2387 }
2388 else
2389 prev = curr;
2390 curr= next;
2391 }
2392
2393 return list;
2394 }
2395 /******************************************************************
2396 *
2397 * SortSameSeqInAlignNode(anp_list)
2398 * if the same sequence appears multiple times in the anp_list,
2399 * it will be moved to the sequence that are the head of this
2400 * list. The field anp->follower is set as the order of the
2401 * repeats in this list
2402 *
2403 ******************************************************************/
SortSameSeqInAlignNode(ValNodePtr anp_list)2404 void SortSameSeqInAlignNode(ValNodePtr anp_list)
2405 {
2406 ValNodePtr curr, n_curr;
2407 AlignNodePtr anp;
2408 ValNodePtr same_list;
2409 Int2 num_follower;
2410
2411 curr = anp_list;
2412 while(curr)
2413 {
2414 anp = curr->data.ptrvalue;
2415 n_curr = curr->next;
2416 if(n_curr != NULL)
2417 {
2418 same_list = extract_match_seqid_list(&n_curr, anp->sip, anp->clone_id, &num_follower);
2419 if(same_list != NULL)
2420 {
2421 anp->num_follower = num_follower;
2422 ValNodeLink(&same_list, n_curr);
2423 curr->next = same_list;
2424 }
2425 }
2426 curr = n_curr;
2427 }
2428 }
2429
2430