← Back to branch summary

~ubuntu-branches/ubuntu/natty/ncbi-tools6/natty

« back to all changes in this revision

Viewing changes to desktop/layout.c

  • Committer: Bazaar Package Importer
  • Author(s): Aaron M. Ucko
  • Date: 2002-04-04 22:13:09 UTC
  • Revision ID: james.westby@ubuntu.com-20020404221309-vfze028rfnlrldct
Tags: upstream-6.1.20011220a
Import upstream version 6.1.20011220a

Show diffs side-by-side

added added

removed removed

Lines of Context:
desktop/layout.c
 
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
 
 
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
 
 
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
 
 
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
 
 
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
 
 
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
 
 
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
 
 
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
*/
 
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
 
 
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
 
 
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
 
 
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
                        
 
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
 
 
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
 
 
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
**************************************************************************/                     
 
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
**************************************************************************/                     
 
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
 
 
814
static Boolean is_inside_interval(Int4 a, Int4 x, Int4 y)
 
815
{
 
816
        return (a >=x && a<=y);
 
817
}
 
818
 
 
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
 
 
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
 
 
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
 
 
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
 
 
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
 
 
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
 
 
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
 
 
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
 
 
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
************************************************************************/
 
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
 
 
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
 
 
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
**********************************************************************/
 
1696
ValNodePtr merge_same_itemID(ValNodePtr PNTR head, Int2 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
 
 
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
*******************************************************************/
 
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
        Uint2 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 */
 
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
        
 
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
 
 
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
 
 
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
 
 
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
 
 
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
 
 
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
 
 
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
 
 
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
 
 
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
***********************************************************************/
 
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
*****************************************************************/
 
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
******************************************************************/
 
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