BioInfWeb - TreeGraph / Version 1 / Show File - tgf-tree.cc

TreeGraph subversion repository

sventon subversion web client - http://www.sventon.org
[show recent changes]
 
  Help
Rev: HEAD (2) - https://secure.bioinfweb.info/Code/svn/TreeGraph / trunk / main / tgf-tree.cc
Show File - tgf-tree.cc  [show properties]
spinner
/*
 tgf-tree.cc, part of
 treegraph
 Tree formatting program
 Generates vector graphics (SVG,EPS) from .tgf-tree description files.
10   Copyright (c) 2003-04 by Joern Mueller
11 
12 
13   This program is free software; you can redistribute it and/or
14   modify it under the terms of the GNU General Public License
15   as published by the Free Software Foundation; either version 2
16   of the License, or (at your option) any later version.
17 
18   This program is distributed in the hope that it will be useful,
19   but WITHOUT ANY WARRANTY; without even the implied warranty of
20   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
21   GNU General Public License for more details.
22 
23   You should have received a copy of the GNU General Public License
24   along with this program (GPL.html); if not, write to the Free Software
25   Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
26   (also: http://www.gnu.org)
27  */
28 
29 
30 
31 
32 
33 
34 
35 
36  #include "tgf-main.h"
37  #include "tgf-tree.h"
38  #include "tgf-render.h"
39 
40 
41  float klammer::breite=40.0;
42  fontface fontstyle::stdface=fs_plain;
43  float fontstyle::stdsize=12;
44 
45 
46  int bound(const char *s, tnode **ls, int n);
47 
48  void astbreiten(vector<float>& a, int n, float w);
49  float min_astbreite(const vector<float>& a, int n, float w);
50 
51  tnode::tnode(tnode *prv, float l) : prev(prv), len(l)
52  {
53   next=down=0;
54   lbl=0;
55   prune=false;
56   userset[0]=userset[1]=userset[2]=false;
57   minlen= minabove=minbelow=autolength;
58  }
59 
60 
61 
62  void tnode::setlabel(const string &a)
63  {
64   if(has_label()) delete [] lbl;
65   lbl=new char [a.length()+1];
66   strncpy(lbl,a.c_str(),a.length()+1);
67  }
68 
69  int tnode::nchildren(void) const
70  {
71 
72   int nc=0;
73 
74   tnode *p=next;
75   while(p){
76    ++nc;
77    p=p->down;
78   }
79   return nc;
80  }
81 
82  int tnode::nterminals(void) const
83  {
84   if(terminal()) return 1;
85   int nt=0;
86   tnode *p=next;
87   while(p){
88    nt+=p->nterminals();
89    p=p->down;
90   }
91   return nt;
92 
93 
94  }
95 
96 
97  void tnode::calcdepth_sichtbar(void)
98  {
99   depth=0;
100   if(!prune){
101    tnode *p=next;
102    while(p){
103     p->calcdepth_sichtbar();
104     if(p->depth+1>depth)
105      depth=p->depth+1;
106     p=p->down;
107    }
108   }
109  }
110 
111 
112  void tnode::selection_sort_children(int sgn)
113  {
114   int nn=nchildren();
115   if(nn<2) return;
116 
117   tnode **nl=new tnode* [nn];
118   nl[0]=next;
119   int i=1;
120   for(; i<nn; i++)
121    nl[i]=nl[i-1]->down;
122  //selection sort
123   for(i=0; i<nn-1; i++){
124    int mn=i;
125    for(int j=i+1;j<nn;j++)
126     if(sgn*(nl[j]->depth-nl[mn]->depth)>0) mn=j;
127    tnode *tmp=nl[mn]; nl[mn]=nl[i]; nl[i]=tmp;
128   }
129  //Verbindungen richtig machen
130   next=nl[0];
131   for(i=1; i<nn; i++){
132    nl[i-1]->down=nl[i];
133   }
134   nl[nn-1]->down=0;
135 
136   delete [] nl;
137  }
138 
139  bool tnode::permute(list<int>& perm)
140  {
141  // Testen, ob wirklich Permutation von {1,..,nchildren} vorliegt
142   int nn=nchildren();
143   if(nn<2 || perm.size()!=nn) return false;
144   list<int>::const_iterator iit=perm.begin();
145   int mi= *iit;
146   int ma=mi;
147   while(++iit!=perm.end()){
148    int nu= *iit;
149    if(nu>ma) ma= nu;
150    else if(nu<mi) mi= nu;
151   }
152   if(mi!=1 || ma!=nn)
153    return false; //keine Permutation
154 
155   tnode **nl=new tnode* [nn];
156   tnode *p=next;
157   iit=perm.begin();
158   while(p){
159    nl[(*iit)-1]=p;
160    p=p->down;
161    ++iit;
162   }
163  //Verbindungen
164   next=nl[0];
165   for(int i=1; i<nn; i++)
166    nl[i-1]->down=nl[i];
167   nl[nn-1]->down=0;
168 
169   delete [] nl;
170   return true;
171  }
172 
173 
174  void tnode::swap_children(void)
175  {
176   int nn=nchildren();
177   if(nn!=2){
178    cout << "Warning: tnode::swap_children: Node must have exactly 2 children.\n";
179    return;
180   }
181 
182   tnode *tmp1=next;
183   tnode *tmp2=next->down;
184 
185   tmp1->down=0;
186   tmp2->down=tmp1;
187   next=tmp2;
188  }
189 
190  void tnode::collapse(void)
191  {
192   if(prev==0) return;
193   tnode *adown=down;
194   down=next;
195   tnode *t=next;
196   tnode *zt=t;
197   while(t){
198    t->prev=prev;
199    zt=t;
200    t=t->down;
201 
202   }
203   zt->down=adown;
204 
205   next=0;
206   prev->removechild(this);
207  }
208 
209 
210  void tnode::ladderize_sichtbare(int d)
211  {
212   if(prune) return;
213 
214   selection_sort_children(d);
215   tnode *p=next;
216   while(p){
217    p->ladderize_sichtbare(d);
218    p=p->down;
219   }
220  }
221 
222  void tnode::symladderize(int d)
223  {
224 
225   selection_sort_children(d);
226   int i=1;
227   int n=nchildren();
228  // Permutation n-1 n-3 .. > < .. n-2 n anwenden
229   if(n>=3){
230    list<int> il;
231    list<int>::iterator it=il.end();
232    for(i=0; i<n; i++){
233     il.insert(it,n-i);
234     if(i%2==0) --it;
235 
236    }
237    permute(il);
238   } else if(n==1){
239    next->symladderize(d);
240    return;
241   }
242   i=0;
243   tnode *p=next;
244   if(prune) return;
245   while(p){
246    p->symladderize(i<n/2?1:-1);
247    ++i;
248    p=p->down;
249   }
250  }
251 
252 
253  const tnode *tnode::unterster_sichtbarer(void) const
254  {
255   const tnode *u=this;
256   while(u->next && !u->prune){
257    u=u->next;
258    while(u->down) u=u->down;
259   }
260   return u;
261  }
262 
263  const tnode *tnode::oberster_sichtbarer(void) const
264  {
265   const tnode *u=this;
266   while(u->next && !u->prune){
267    u=u->next;
268   }
269   return u;
270  }
271 
272  void tnode::removechild(tnode *ch)
273  //setzt voraus, dass ch als child existiert, insbesondere nchildren()>0
274  {
275 
276   if(next==ch){
277    next=ch->down;
278   }else {
279    tnode *p=next;
280    while(p->down){
281     if(p->down==ch){
282      p->down=ch->down;
283      break;
284     }
285     p=p->down;
286    }
287   }
288   ch->prev=0;
289   ch->down=0;
290  }
291 
292 
293  void tnode::insertchild(tnode *ch)
294  // setzt ch->down=ch->prev=0 voraus
295  {
296   ch->down=next;
297   next=ch;
298   ch->prev=this;
299 
300  }
301 
302 
303 
304  label_list::label_list()
305  {
306   nd=0;
307   nnodes=nlabel=0;
308  }
309 
310  label_list::~label_list()
311  {
312   if(nd) delete [] nd;
313  }
314 
315 
316  void label_list::init(int a)
317  {
318   if(nd) delete [] nd;
319   nd = new tnode* [nnodes=a];
320   for(int i=0; i<nnodes; i++) nd[i]=0;
321   nlabel=0;
322 
323   autovar=1;//fuer auto_label
324  }
325 
326  int label_namecompare(const char *s1, const tnode *p2)
327  {
328   return strcmp(s1,p2->label());
329  }
330 
331 
332  void label_list::einsortiere_label(tnode *p)
333  {
334   if(nlabel<1){
335    nd[0]=p;
336    nlabel=1;
337    return;
338   }
339 
340   if(nlabel>=nnodes){
341    cout << "Error: Label buffer overflow.\n";
342    throw label_err();
343   }
344   int nb=bound(p->label(),nd,nlabel);
345   for(int i=nlabel-1; i>nb; i--)
346    nd[i+1]=nd[i];
347   nd[nb+1]=p;
348   ++nlabel;
349   if(nb>=0 && label_namecompare(p->label(),nd[nb])==0){
350    cout << "Error: Duplicate label '" << p->label() << "'\n";
351    throw label_err();
352   }
353  }
354 
355  void label_list::kill_label(const char *s)
356  {
357   if(nlabel<1){
358    return;
359   }
360 
361 
362   int nb=bound(s,nd,nlabel);
363   if(nb<0) return;
364   if(label_namecompare(s,nd[nb])!=0)
365    return;
366 
367   for(int i=nb; i<nlabel-1; i++)
368    nd[i]=nd[i+1];
369   --nlabel;
370  }
371 
372 
373 
374  void label_list::random_label(char s[])
375  {
376   char tmp[12];
377   do {
378    sprintf(tmp,"n%d",autovar++);
379   }while(bfind_label(tmp));
380   strncpy(s,tmp,12);
381  }
382 
383 
384  int bound(const char *s, tnode **ls, int n)
385  //groesstes i, 0<=i<n, so dass ls[i]<=s, oder -1, falls s<ls[0]
386  {
387   if(n<1) return 0;
388 
389   if(label_namecompare(s,ls[0])<0) return -1;
390   int l=0,h=n;
391   while(h-l>1){
392    int m=(h+l)/2;
393    if(label_namecompare(s,ls[m])<0) h=m;
394    else l=m;
395   }
396   return l;
397 
398  }
399 
400 
401  const tnode *label_list::bfind_label(const char *s) const
402  {
403   int nb=bound(s,nd,nlabel);
404   if(nb<0) return 0;
405   if(label_namecompare(s,nd[nb])!=0)
406    return 0;
407   return nd[nb];
408  }
409 
410 
411  float tnode::maxrund(void) const
412  //erst nach calcpos aufrufen!
413  {
414   if(terminal()) return -1.0;
415   if(nchildren()==1) return next->maxrund();
416 
417   tnode *p=next;
418   tnode *p2=p->down;
419   float mr=min((float)abs(p2->pos.y-p->pos.y),p->pos.x-pos.x);
420   mr=min((float)abs(pos.y-p->pos.y),mr);
421   while(p2->down){
422    p=p2;
423    p2=p2->down;
424   }
425   mr=min((float)abs(p2->pos.y-p->pos.y),mr);
426   mr=min((float)abs(pos.y-p2->pos.y),mr);
427 
428   p=next;
429   while(p){
430    float r2=p->maxrund();
431    if(r2>0 && r2<mr) mr=r2;
432    p=p->down;
433   }
434   return mr;
435 
436  }
437 
438  tree_desc::tree_desc(void)
439  {
440   uselength=false;
441   shownumbers=false;
442   roundness=0;
443   setstyle("r","plain",12.0);
444   setstyle("u","plain",11.0);
445   setstyle("d","plain",11.0);
446   setstyle("br","italic",14.0);
447 
448   extrasep=helv_stringwidth(string("x"));
449   picheight=200*millimeter;
450   picwidth=150*millimeter;
451   variablelength=false;
452   thickness=0.33*millimeter;
453   scale=1;
454   bracketcolwidth=autolength;
455   colsep=" ";
456 
457 
458  }
459 
460  void tree_desc::show(void) const
461  {
462   cout << "\\thickness{" << thickness/millimeter << "}\n";
463  // float klammerrand;//breite des klammerrands.
464   cout << "\\width{"<<picwidth/millimeter<<"}\n";
465   cout << "\\height{"<<picheight/millimeter<<"}\n";
466  // float scale;
467   cout << "\\roundness{"<< roundness << "}\n";
468  // float bracketcolwidth; //Platz fuer Klammern am rechten Rand
469   cout << "\\margin{"<<Rand.left/millimeter<<"}{"<<Rand.top/millimeter<<"}{";
470   cout << Rand.right/millimeter <<"}{"<< Rand.bottom/millimeter << "}\n";
471   if(forceauto) cout << "\\autolength\n";
472   else cout << "\\autolength not set\n";
473   if(variablelength) cout << "\\variable\n";
474   else cout << "\\variable not set\n";
475   if(shownumbers) cout << "\\proof\n";
476   else cout << "\\proof not set\n";
477   cout << "\\separator{"<<colsep<<"}\n";
478 
479   showstyle("r",rstyle);
480   char *str[]={"u1","u2","u3","u4","d1","d2","d3","d4"};
481   for(int i=0;i<8;i++){
482    showstyle(str[i],(i<4)?ustyle[i]:dstyle[i-4]);
483   }
484   showstyle("br",brstyle);
485   string colsep; //Trennung zwischen Spalten ueber Ast
486 
487  }
488 
489  void tree_desc::showstyle(const string& id,const fontstyle& f) const
490  {
491   cout << "\\style{"<<id<<"}{";
492   if(f.face==fs_italic)
493    cout << "italic";
494   else if(f.face==fs_bold)
495    cout << "bold";
496   else cout << "plain";
497   cout << "}{" << f.fontsize<< "}\n";
498 
499  }
500 
501 
502  void tree_desc::setstyle(const string& ident,const string& typ,float sz)
503  {
504   fontstyle fs;
505   if(typ=="italic")
506    fs.face=fs_italic;
507   else if(typ=="bold")
508    fs.face=fs_bold;
509   else
510    fs.face=fs_plain;
511 
512   fs.fontsize=sz;
513 
514   if(ident=="r"){
515    rstyle=fs;
516   } else if(ident[0]=='u'){
517    if(ident[1]==0){
518     for(int i=0;i<4;i++)
519      ustyle[i]=fs;
520    } else {
521     int q=ident[1]-'0'-1;
522     if(q>=0 && q<4)
523      ustyle[q]=fs;
524    }
525   } else if(ident[0]=='d'){
526    if(ident[1]==0){
527     for(int i=0;i<4;i++)
528      dstyle[i]=fs;
529    } else {
530     int q=ident[1]-'0'-1;
531     if(q>=0 && q<4)
532      dstyle[q]=fs;
533    }
534 
535   } else if(ident=="br"){
536    brstyle=fs;
537   }
538 
539 
540  }
541 
542 
543  tree::tree() : tnode(0)
544  {
545   drty=true;
546   definition_part="";
547  }
548 
549  tree::~tree()
550  {
551   if(has_label()) lb.kill_label(label());
552   remove_subtree(this);
553  }
554 
555 
556  void tree::read_definitions(parser& P)
557  //alles zwischen (Dateianfang) und \enddef
558  {
559   int mode=0;
560   dsc.Rand=fRect();
561 
562   P.startecho();
563 
564   while(!P.eof() && P.good()){
565    P.skipspaces();
566    int ch=P.get();
567    if(ch=='%'){
568     P.skipcomment();
569    } else if(ch=='\\'){
570     string wort;
571     P.readcommand(wort);
572     if(mode==0){
573      if(wort!="begindef"){
574       cout << "Missing \\begindef\n";
575       throw syntax(P.curline());
576      }
577      mode=1;
578     } else if(wort=="enddef"){
579      if(mode!=1){
580       cout << "Missing \\enddef\n";
581       throw syntax(P.curline());
582      }
583      P.stopecho();
584      P.readecho(definition_part);
585      break;
586     } else if(wort=="width"){
587      dsc.picwidth=P.readbracefloat()*millimeter;
588     } else if(wort=="height"){
589      dsc.picheight=P.readbracefloat()*millimeter;
590     } else if(wort=="autolength"){
591      dsc.forceauto=true;
592     } else if(wort=="style"){
593      string ident,typ;
594      P.readbracestring(ident);
595      P.readbracestring(typ);
596      float sz=P.readbracefloat();
597      dsc.setstyle(ident,typ,sz);
598     } else if(wort=="thickness"){
599      dsc.thickness=P.readbracefloat()*millimeter;
600    // } else if(wort=="scale"){
601    // dsc.scale=P.readbracefloat();
602     } else if(wort=="variable"){
603      dsc.variablelength=true;
604     } else if(wort=="proof"){
605      dsc.shownumbers=true;
606     } else if(wort=="roundness"){
607      dsc.roundness=P.readbracefloat();
608     } else if(strncmp(wort.c_str(),"brac",4)==0) {
609      //Randklammer: (\brace|\bracket|\brace*|\bracket*){spalte}{lb1}{lb2}{name}
610      klammer nk;
611      if(strncmp(wort.c_str(),"brace",5)==0) nk.style=klammer::geschweift;
612      else nk.style=klammer::eckig;
613      if(wort[wort.length()-1]=='*') nk.style+=klammer::gedreht;
614      nk.sp=P.readbracefloat();
615      P.readbracestring(nk.lb[0]);
616      P.readbracestring(nk.lb[1]);
617      string kltxt;
618      P.readbracestring(kltxt);
619      nk.text=fstring(kltxt,dsc.brstyle);
620      kl.push_back(nk);
621     } else if(wort=="margin") {
622      dsc.Rand.left=P.readbracefloat()*millimeter;
623      dsc.Rand.top=P.readbracefloat()*millimeter;
624      dsc.Rand.right=P.readbracefloat()*millimeter;
625      dsc.Rand.bottom=P.readbracefloat()*millimeter;
626     } else if(wort=="separator"){
627      P.readbracestring(dsc.colsep);
628     } else {
629      cout << "Warning: Unknown command \\" << wort << " in line "<<P.curline()<<".\n";
630      int arg=0;
631      while(P.skipbracestring()){++arg;}
632      if(arg>0){
633       cout << "--> Ignored ";
634       if(arg==1) cout << "argument";
635       else cout << arg << " arguments";
636       cout << " of \\" << wort << ".\n";
637 
638      }
639     }
640 
641    } else {
642     cout << "Error: Illegal character "<< ch << "\n";
643     throw syntax(P.curline());
644    }
645 
646   }
647 
648 
649  /*
650   cout << "width " <<dsc.picwidth*dsc.scale/millimeter << "mm\n";
651   cout << "height " << dsc.picheight*dsc.scale/millimeter << "mm\n";
652   if(dsc.forceauto) cout << "ignoring dimensions\n";
653   if(dsc.variablelength) cout << "variable lengths.\n";
654  */
655 
656  }
657 
658 
659  void tree::read(istream& input)
660  // alles zwischen '(' und ')' einlesen
661  {
662 
663   dsc.uselength=dsc.forceauto=false;
664 
665   parser P(input);
666   read_definitions(P);
667 
668   tnode *cp=this;
669 
670   int knoten=1;
671 
672   float ff;
673   parser::ttoken lastt=parser::kInit;
674   string plaintxt="";//Position noch nicht zugeordnet
675   while(lastt!=parser::kEOF){
676    string s;
677    parser::ttoken was=P.readnextword(s,ff);
678 
679    if(cp==0){
680     cout << "Fehler tree::read::1\n";
681     throw syntax(P.curline());
682    }
683 
684    switch(was){
685    case parser::kNextTree:
686     cp->down=new tnode(cp->prev);
687     ++knoten;
688     if(plaintxt.length()>0){
689      cp->r=fstring(plaintxt,dsc.rstyle);
690      plaintxt="";
691     }
692     cp=cp->down;
693     break;
694    case parser::kOpenTree:
695     cp->next=new tnode(cp);
696     ++knoten;
697     if(plaintxt.length()>0){
698      cp->u[0]=fstring(plaintxt,dsc.ustyle[0]);
699      plaintxt="";
700     }
701     cp=cp->next;
702     break;
703    case parser::kCloseTree:
704     if(plaintxt.length()>0){
705      cp->r=fstring(plaintxt,dsc.rstyle);
706      plaintxt="";
707     }
708     cp=cp->prev;
709     break;
710    case parser::kText:
711     plaintxt=s;
712     break;
713    case parser::kTextR: cp->r=fstring(s,dsc.rstyle); break;
714    case parser::kTextU1: cp->u[0]=fstring(s,dsc.ustyle[0]); break;
715    case parser::kTextU2: cp->u[1]=fstring(s,dsc.ustyle[1]); break;
716    case parser::kTextU3: cp->u[2]=fstring(s,dsc.ustyle[2]); break;
717    case parser::kTextU4: cp->u[3]=fstring(s,dsc.ustyle[3]); break;
718    case parser::kTextD1: cp->d[0]=fstring(s,dsc.dstyle[0]); break;
719    case parser::kTextD2: cp->d[1]=fstring(s,dsc.dstyle[1]); break;
720    case parser::kTextD3: cp->d[2]=fstring(s,dsc.dstyle[2]); break;
721    case parser::kTextD4: cp->d[3]=fstring(s,dsc.dstyle[3]); break;
722    case parser::kLength:
723     cp->len=ff;
724     dsc.uselength=true;
725     break;
726    case parser::kLabel:
727     cp->setlabel(s);
728     break;
729    case parser::kPruned:
730    cout << "\nWARNING! \\prune is NOT TESTED!!\n\n";
731     cp->prune=true;
732     break;
733    case parser::kMinLength:
734     cp->minlen=ff;
735     cp->userset[0]=true;
736     break;
737    case parser::kSpaceAbove:
738     cp->userset[1]=true;
739     cp->minabove=ff;
740     break;
741    case parser::kSpaceBelow:
742     cp->userset[2]=true;
743     cp->minbelow=ff;
744     break;
745    case parser::kEOF: break;
746    default:
747     cout << "Error " << was << " in tree::read\n";
748     throw syntax(P.curline());
749     break;
750    }
751 
752 
753    lastt=was;
754   }
755 
756 
757   if(dsc.forceauto)
758    dsc.uselength=false;
759 
760   if(dsc.uselength){
761    if(dsc.roundness > 0){
762     cout << "Warning: Rounded corners are not allowed in this mode.\n";
763     cout << "--> Using \\roundness{0}.\n";
764     dsc.roundness=0;
765    }
766   }
767 
768   cout << "Total number of nodes: " << knoten << endl;
769 
770   drty=false;
771   fill_labels(knoten);
772 
773 
774   calcpos();
775 
776  }
777 
778  void tree::write(ostream& aus, const tnode *tn)
779  {
780   aus << definition_part;
781 
782   writenodes(aus,tn);
783 
784 
785   if(tn==0) drty=false; //ganzer Baum wird gespeichert
786 
787   flush(aus);
788  }
789 
790 
791  void tree::writenodes(ostream& aus, const tnode *tn) const
792  {
793   const tnode *nd=(tn==0)?this:tn;
794   const tnode *here=nd;
795 
796   const int maxindent=25;
797 
798   char *sp=new char[maxindent+3];
799   int i;
800   for(i=0; i<maxindent+2; i++)
801    sp[i]=' ';
802   sp[maxindent+2]=0;
803   sp[0]='\n';
804   sp[1]=0;
805 
806   int level=0;
807   do{
808 
809 
810    if(nd->len!=autolength)
811     aus << sp <<"\\len{" << nd->len << '}';
812    if(nd->r.length()>0)
813     aus << sp << "\\r{" << nd->r << '}';
814    for(i=0; i<4; i++){
815     if(nd->u[i].length()>0)
816      aus << sp << "\\u"<<i+1<<'{' << nd->u[i] << '}';
817 
818    }
819    for(i=0; i<4; i++){
820     if(nd->d[i].length()>0)
821      aus << sp << "\\d"<<i+1<<'{' << nd->d[i] << '}';
822 
823    }
824 
825    if(nd->minlen>=0 && nd->userset[0]) //Auch explizites 0 soll erlaubt sein
826     aus << sp <<"\\min_length{" << nd->minlen/millimeter << '}';
827    if(nd->minabove>=0 && nd->userset[1])
828     aus << sp <<"\\space_above{" << nd->minabove/millimeter << '}';
829    if(nd->minbelow>=0 && nd->userset[2])
830     aus << sp <<"\\space_below{" << nd->minbelow/millimeter << '}';
831 
832 
833    if(nd->prune){
834     aus << sp << "\\prune";
835    }
836 
837    if(nd->has_label()){
838     aus << sp << "\\label{" << nd->label() << '}';
839    }
840    int l;
841    if(nd->next){
842     aus << sp << '(';
843     ++level;
844     for(l=1; l<min(level,maxindent)+1; l++) sp[l]=' ';
845     sp[0]='\n'; sp[l]=0;
846     nd=nd->next;
847    } else {
848     int j=0;
849     while(!nd->down && nd!=here){
850      nd=nd->prev;
851      ++j;
852     }
853     level-=j;
854     for(l=1; l<min(level,maxindent)+1; l++) sp[l]=' ';
855     sp[0]='\n'; sp[l]=0;
856     if(j>0){
857      aus << sp;
858      while(j-- >0) aus << ')';
859     }
860     if(nd!=here){
861      nd=nd->down;
862      aus << ',';
863     }
864    }
865   } while(nd!=here);
866   aus << endl;
867   delete [] sp;
868  }
869 
870 
871 
872 
873 
874  void tree::fill_labels(int nnodes1)
875  {
876   lb.init(nnodes1);
877   setlabel("root"); //ggf. user-label ueberschreiben
878 
879   user_labels(this,lb);
880   auto_labels(this,lb);
881 
882  }
883 
884 
885 
886 
887  void tree::user_labels(tnode *q, label_list& lbl)
888  {
889   if(q->has_label()){
890    lbl.einsortiere_label(q);
891   }
892   tnode *p=q->next;
893   while(p){
894    user_labels(p,lbl);
895    p=p->down;
896   }
897 
898  }
899 
900  void tree::auto_labels(tnode *q, label_list& lbl)
901  {
902   if(!q->has_label()){
903    char tmp[12];
904    lbl.random_label(tmp);
905    q->setlabel(tmp);
906    lbl.einsortiere_label(q);
907    if(!drty){
908     cout << "Note: Consecutively numbered labels have been added\n";
909     cout << " where labels were missing\n";
910    }
911    drty=true;
912   }
913   tnode *p=q->next;
914   while(p){
915    auto_labels(p,lbl);
916    p=p->down;
917   }
918  }
919 
920 
921  void tree::remove_subtree(tnode *p)
922  // alle children von p loeschen
923  {
924   tnode *q=p;
925   p=p->next;
926   while(p){
927    if(p->has_label()){
928     lb.kill_label(p->label());
929     delete [] p->lbl;
930    }
931    remove_subtree(p);
932    p=p->down;
933   }
934   q->next=0;
935 
936  }
937 
938 
939 
940  void tree::calc_mindimensions(void)
941  //minimale Astlaengen und minimale Baumbreite bestimmen
942  {
943   dsc.min_treewidth=0;
944   dsc.min_treeheight=0;
945   float nw=0;
946   tnode *p=this;
947   if(minlen<=0) minlen=0;//root hat Laenge 0
948   for(;;){
949    while(!p->terminal()){
950     if(p->minlen==autolength)
951      p->minlen=min_node_width(p,dsc.colsep);
952     nw+=p->minlen;
953     p=p->next;
954    }
955    //Randknoten
956    if(p->minlen==autolength)
957     p->minlen=min_node_width(p,dsc.colsep);
958    nw+=p->minlen;
959    if(nw>dsc.min_treewidth) dsc.min_treewidth=nw;
960 
961    dsc.min_treeheight+=max(p->minabove,(float)0.6*dsc.rstyle.fontsize);
962    dsc.min_treeheight+=max(p->minbelow,(float)0.6*dsc.rstyle.fontsize);
963 
964    while(p->down==0){
965     nw-=p->minlen;
966     p=p->prev;
967     if(p==0){
968      return;
969     }
970    }
971    nw-=p->minlen;
972    p=p->down;
973   }
974  }
975 
976  void tree::calc_treewidth(void)
977  //Maximal moegliche Breite bestimmen
978  {
979  //Randklammern ausmessen
980   dsc.klammerrand=0;
981   for(list<klammer>::const_iterator it=kl.begin(); it!=kl.end(); ++it){
982    float wd=(*it).sp*klammer::breite;//kann auch <0 sein
983 
984    if(it->style & klammer::gedreht)
985     wd+=helv_stringwidth(fstring(it->text,dsc.brstyle))+12.0;//12:klammer selbst
986    else
987     wd+=klammer::breite;
988    if(wd>dsc.klammerrand) dsc.klammerrand=wd;
989 
990   }
991 
992 
993  //Randtexte ausmessen
994   if(dsc.uselength){
995    dsc.treewidth=dsc.picwidth-dsc.Rand.left-dsc.Rand.right//
996     -2*dsc.extrasep-dsc.klammerrand;
997    return;
998   }
999 
1000   float randw=0;
1001   tnode *p=this;
1002   for(;;){
1003    while(p->next && !p->prune){
1004     p=p->next;
1005    }
1006    //Randknoten erreicht
1007    float textb=helv_stringwidth(p->r);
1008    if(textb>randw) randw=textb;
1009 
1010    while(p->down==0){
1011     p=p->prev;
1012     if(p==0){
1013      dsc.treewidth=dsc.picwidth-dsc.Rand.left//
1014       -dsc.Rand.right-randw-2*dsc.extrasep
1015       -dsc.klammerrand;
1016      return;
1017     }
1018    }
1019    p=p->down;
1020   }
1021  }
1022 
1023 
1024  inline float zentrum(float a, float b, float c)
1025  //zweitgroesster Wert von a,b,c
1026  //Voraussetzung: a<c
1027  {
1028   if(b<=a) return a;
1029   else if(b>=c) return c;
1030 
1031   return b;
1032  }
1033 
1034  void tree::calcvpos(void)
1035  //vertikal-Koordinaten
1036  // beruecksichtigt space_above/below nur bei terminal-Knoten
1037  {
1038   int nt=nterminals();
1039   vector<float> ht(nt);
1040   vector<fPoint> pt(nt); //x->above,y->below
1041  //minimale hoehen der Randknoten sammeln
1042   int i=0;
1043   tnode *p=this;
1044   for(;;){
1045    while(!p->terminal()) p=p->next;
1046    pt[i].x=max(p->minabove,(float)0.6*dsc.rstyle.fontsize);
1047    pt[i].y=max(p->minbelow,(float)0.6*dsc.rstyle.fontsize);
1048    ht[i]=pt[i].x+pt[i].y;
1049    i++;
1050 
1051    while(p->down==0){
1052     p=p->prev;
1053     if(p==0) break;
1054    }
1055    if(p) p=p->down;
1056    else break;
1057   }
1058  //optimale hoehen der Randknoten berechnen.
1059   astbreiten(ht,nt,dsc.picheight-dsc.Rand.top-dsc.Rand.bottom);
1060 
1061  //vertikale Positionen
1062   p=this;
1063   i=0;
1064   float v1=0;
1065   float v0=0;
1066   for(;;){
1067    while(p->next && !p->prune) p=p->next;
1068 
1069    //Position moeglichst zentral in [v0,v0+ht[i]]
1070    p->pos.y=v0+zentrum(pt[i].x,ht[i]/2,ht[i]-pt[i].y);
1071    v0+=ht[i];
1072    i++;
1073    while(p->down==0){
1074     v1=p->pos.y;
1075     p=p->prev;
1076     if(p==0) return;
1077     p->pos.y=0.5*(p->next->pos.y+v1);
1078    }
1079    p=p->down;
1080   }
1081 
1082 
1083  }
1084 
1085  struct _fi
1086  {
1087   float f;
1088   int i;
1089  };
1090 
1091  int _ficomp(const void *a, const void *b)
1092  {
1093   float d=((_fi*)a)->f-((_fi*)b)->f;
1094   return (int)d;
1095  }
1096 
1097  int _floatcomp(const void *a, const void *b)
1098  {
1099   float d=*((float*)a)- *((float*)b);
1100   return (int)d;
1101  }
1102 
1103 
1104  void astbreiten(vector<float>& a, int n, float w)
1105  {
1106   if(n>a.size()){//may not happen
1107    throw fehler();
1108   }
1109 
1110 
1111   _fi *b=new _fi[n];
1112   int i;
1113   for(i=0;i<n; i++){
1114    b[i].i=i;
1115    if(a[i]<0) b[i].f=0;
1116    else b[i].f=a[i];
1117   }
1118   qsort(b,n,sizeof(_fi),_ficomp);
1119 
1120   float r=w/((float)n);
1121   for(i=n-1; i>=0; i--){
1122    if(b[i].f>r){
1123     w-=b[i].f;
1124     if(i==0){
1125      delete [] b;
1126      cout << "Error: astbreiten(): "<< -w/millimeter<<"mm too wide\n";
1127      throw fehler();
1128     }
1129     r=w/((float)i);
1130    } else b[i].f=r;
1131 
1132   }
1133 
1134   for(i=0;i<n; i++){
1135    a[b[i].i]=b[i].f;
1136   }
1137   delete [] b;
1138 
1139 
1140  }
1141 
1142  float min_astbreite(const vector<float>& a, int n, float w)
1143  {
1144   if(n>a.size()){//may not happen
1145    throw fehler();
1146   }
1147 
1148 
1149   float *b=new float [n];
1150   int i;
1151   for(i=0;i<n; i++){
1152    if(a[i]<0) b[i]=0;
1153    else b[i]=a[i];
1154   }
1155   qsort(b,n,sizeof(float),_floatcomp);
1156 
1157   float r=w/((float)n);
1158   for(i=n-1; i>=0; i--){
1159    if(b[i]>r){
1160     w-=b[i];
1161     if(i==0){
1162      delete [] b;
1163      cout << "Error: min_astbreite(): "<< -w/millimeter<<"mm too wide\n";
1164      throw fehler();
1165     }
1166     r=w/((float)i);
1167    } else b[i]=r;
1168 
1169   }
1170 
1171   float f=b[0];
1172   delete [] b;
1173 
1174   return f;
1175  }
1176 
1177 
1178 
1179  int tree::calchpos(void)
1180  //automatisch, gleichmaessig verteilte Astlaenge (\variable)
1181  {
1182 
1183 
1184   vector<float> ml(depth+1,0.0); //depth von root 1 zu klein
1185  //
1186  // Hier kann nicht einfach
1187  // sethpos(dsc.Rand.left,dsc.treewidth);
1188  // aufgerufen werden, weil root immer Laenge 0 hat.
1189  // stattdessen fuer alle root-Nachfolger.
1190 
1191   pos.x=dsc.Rand.left; //root
1192   tnode *p=next;
1193   if(!p || prune){
1194    return 1; //nur ein root-Knoten
1195   }
1196   while(p){
1197    p->sethpos(pos.x,dsc.treewidth);
1198    p=p->down;
1199   }
1200 
1201   return 1;
1202  }
1203 
1204 
1205  float tnode::optlen(vector<float>& x,int tief,float w)
1206  {
1207   if(tief>=x.size()){//may not happen
1208    throw fehler();
1209   }
1210   x[tief]=minlen;
1211 
1212   tnode *q=next;
1213   if(q==0 || prune){
1214    vector<float> ls=x;
1215    astbreiten(ls,tief+1,w);
1216    return ls[0];
1217   }
1218 
1219   float ol=q->optlen(x,tief+1,w);
1220   while(q->down){
1221    q=q->down;
1222    float ol1=q->optlen(x,tief+1,w);
1223    if(ol1<ol) ol=ol1;
1224   }
1225   return ol;
1226  }
1227 
1228 
1229  void tnode::sethpos(float xprev,float w)
1230  {
1231   if(w<=0){
1232    cout << "Error: tnode::sethpos: no space for node.\n";
1233    throw fehler();
1234   }
1235   vector<float> x(depth+1,0.0); //an der root-Tiefe soll's nicht scheitern
1236   float opt=optlen(x,0,w);
1237   pos.x=xprev+opt;
1238   w-=opt;
1239 
1240   tnode *q=next;
1241   if(q==0 || prune){
1242    return;
1243   }
1244   q->sethpos(pos.x,w);
1245   while(q->down){
1246    q=q->down;
1247    q->sethpos(pos.x,w);
1248   }
1249  }
1250 
1251 
1252 
1253  int tree::calchpos_fixed(void)
1254  //automatisch, aber mit fester Standardlaenge
1255  {
1256 
1257 
1258   vector<float> ml(depth+1,0.0); //depth von root 1 zu klein
1259 
1260  //kleinste tatsaechliche Laenge berechnen
1261   pos.x=dsc.Rand.left; //root
1262   tnode *p=next;
1263   if(!p || prune){
1264    return 1; //nur ein root-Knoten
1265   }
1266   float fl=dsc.treewidth;
1267   while(p){
1268    float f10=p->normlen_fixed(ml,0,dsc.treewidth);
1269    if(f10<fl) fl=f10;
1270    p=p->down;
1271   }
1272 
1273   p=next;
1274   while(p){
1275    p->sethpos_fixed(dsc.Rand.left,dsc.Rand.left+dsc.treewidth,fl);
1276    p=p->down;
1277   }
1278 
1279 
1280   return 1;
1281  }
1282 
1283 
1284  float tnode::normlen_fixed(vector<float>& x,int tief,float w)
1285  {
1286   if(tief>=x.size()){//may not happen
1287 
1288    throw fehler();
1289   }
1290   x[tief]=minlen;
1291 
1292   tnode *q=next;
1293   if(terminal()){
1294    vector<float> ls=x;
1295    return min_astbreite(ls,tief+1,w);
1296   }
1297 
1298   float ol=q->normlen_fixed(x,tief+1,w);
1299   while(q->down){
1300    q=q->down;
1301    float ol1=q->normlen_fixed(x,tief+1,w);
1302    if(ol1<ol) ol=ol1;
1303   }
1304   return ol;
1305  }
1306 
1307 
1308  float tnode::sethpos_fixed(float x0,float w,float stdw)
1309  {
1310 
1311   float l=stdw;
1312   if(minlen>l) l=minlen;
1313   tnode *q=next;
1314   if(q==0 || prune){
1315    pos.x=w;
1316    return pos.x-l;
1317   }
1318 
1319   float minh= q->sethpos_fixed(x0,w,stdw);
1320   while(q->down){
1321    q=q->down;
1322    float f2=q->sethpos_fixed(x0,w,stdw);
1323    if(f2<minh) minh=f2;
1324   }
1325   pos.x=minh;
1326   if(pos.x<x0){
1327    cout << "Error: tnode::sethpos_fixed: no space for node.\n";
1328    throw fehler();
1329   }
1330   return pos.x-l;
1331  }
1332 
1333 
1334 
1335  int tree::calchpos_len(void)
1336  //Astlaengen aus \len
1337  {
1338   if(terminal()){
1339    cout << "Error: tree::calchpos_len: Only one node (root)\n";
1340    throw fehler();
1341   }
1342 
1343  //Noetige Skalierung der \len-Laengen ermitteln
1344 
1345   float smin=0, smax=1e10;
1346 
1347   len=0; //root
1348   minlen=autolength; //wenn len==0, keine minlen>0 erlaubt
1349 
1350   getoptlenscale(0, smin, smax, dsc);
1351   if(smin>smax){
1352    float f=(smin/smax-1.0)*dsc.treewidth;
1353    cout << "Warning: Tree is " << f/millimeter << "mm too wide\n";
1354    cout << "--> Ignoring width of node labels and \\min_length.\n";
1355   }
1356 
1357   sethpos_len(dsc.Rand.left,smax);
1358   dsc.lenscale=smax;
1359 
1360   return 1;
1361  }
1362 
1363  void tnode::getoptlenscale(float zweigl, float& smin, float& smax, const tree_desc& dsc)
1364  //smax durch Baumbreite, smin durch minlen
1365  {
1366   if(len==autolength){
1367    cout << "Error: Missing \\len in node '"<<r<<"' (Label "<<label()<<")\n";
1368    throw fehler();
1369   }
1370   if(minlen!=autolength && minlen>0){
1371    if(len==0){
1372     cout << "Error: Node with \\len{0} must not have positive \\min_length.\n";
1373     throw fehler();
1374    }
1375    float f=minlen/len;
1376    if(f>smin) smin=f;
1377   }
1378   zweigl+=len;
1379   if(terminal()) {
1380   //Achtung. Bei prune muss dann Text auch in r stehen
1381    float f=(dsc.treewidth-helv_stringwidth(this->r))/zweigl;
1382    if(f<smax) smax=f;
1383   } else {
1384    tnode *p=next;
1385    while(p){
1386     p->getoptlenscale(zweigl,smin,smax,dsc);
1387     p=p->down;
1388    }
1389   }
1390 
1391 
1392  }
1393 
1394  void tnode::sethpos_len(float x0,float sc)
1395  {
1396   pos.x=x0+sc*len;
1397   if(terminal()) return;
1398   tnode *p=next;
1399   while(p){
1400    p->sethpos_len(pos.x,sc);
1401    p=p->down;
1402   }
1403 
1404 
1405 
1406  }
1407 
1408  void tree::vrescale(float f)
1409  {
1410   float m[4]={1,0,0,1};
1411   m[3]=f;
1412   float v[2]={0,0};
1413   affine_transform(m,v);
1414  }
1415 
1416  void tree::affine_transform(float m[4], float v[2])
1417  {
1418   tnode *p=this;
1419   for(;;){
1420    fPoint q;
1421    q.x=m[0]*p->pos.x+m[1]*p->pos.y+v[0];
1422    q.y=m[2]*p->pos.x+m[3]*p->pos.y+v[1];
1423    p->pos=q;
1424    while(p->next && !p->prune){
1425     p=p->next;
1426     q.x=m[0]*p->pos.x+m[1]*p->pos.y+v[0];
1427     q.y=m[2]*p->pos.x+m[3]*p->pos.y+v[1];
1428     p->pos=q;
1429    }
1430    while(p->down==0){
1431     p=p->prev;
1432     if(p==0) return;
1433    }
1434    p=p->down;
1435   }
1436 
1437  }
1438 
1439 
1440 
1441 
1442 
1443  void tree::calcpos(void)
1444  {
1445 
1446   calcdepth_sichtbar();
1447   bool fits=true;
1448   do{
1449    fits=true;
1450    calc_treewidth();
1451    calc_mindimensions();
1452    if(dsc.min_treewidth>dsc.treewidth){
1453     cout <<"Warning: Tree is " <<(dsc.min_treewidth-dsc.treewidth)/millimeter << "mm too wide.\n";
1454     float nw=ceil((dsc.picwidth+dsc.min_treewidth-dsc.treewidth)/millimeter)*millimeter;
1455     cout << "--> Using \\width{" << nw/millimeter << "}\n";
1456     dsc.picwidth=nw;
1457     fits=false;
1458    }
1459    float mh=dsc.picheight-dsc.Rand.top-dsc.Rand.bottom;
1460    if(dsc.min_treeheight>mh){
1461     cout <<"Warning: Tree is " <<(dsc.min_treeheight-mh)/millimeter << "mm too wide.\n";
1462     float nw=ceil((dsc.picheight+dsc.min_treeheight-mh)/millimeter)*millimeter;
1463     cout << "--> Using \\height{" << nw/millimeter << "}\n";
1464     dsc.picheight=nw;
1465     fits=false;
1466    }
1467   }while(!fits);
1468 
1469   if(dsc.uselength){
1470    calchpos_len();
1471   } else {
1472    if(dsc.variablelength){
1473     calchpos();
1474    } else {
1475     calchpos_fixed();
1476    }
1477   }
1478   calcvpos();
1479 
1480  //maximalen Rundungsradius bestimmen
1481   dsc.maxrund=maxrund();
1482  }
1483 
1484 
1485 
1486 
1487  bool tree::reroot(tnode *nd)
1488  //fuegt neue root vor nd ein
1489  {
1490 
1491   if(nd==0) return false;
1492   tnode *p=nd->prev;
1493   if(p==0) return false; //alte Wurzel
1494   if(nchildren()!=2){
1495    cout << "Error: Original root must have 2 children\n";
1496    return false;
1497   }
1498 
1499  //Auf Weg von nr bis root durchlaufrichtung aendern
1500   tnode *q=nd;
1501 
1502   list<tnode*> tnd;
1503   while(p){
1504    p->removechild(q);
1505    tnd.push_back(q);
1506    q=p;
1507    p=p->prev;
1508   }
1509   tnd.push_back(next);
1510   removechild(next);
1511   list<tnode*>::iterator it=tnd.begin();
1512   insertchild(*it);
1513   ++it;
1514   insertchild(*it);
1515   p=(*it);
1516   for(++it; it!=tnd.end(); ++it){
1517    p->insertchild(*it);
1518    p=(*it);
1519   }
1520 
1521   fill_labels(lb.total_nodes());
1522   return true;
1523  }


feed icon

sventon 2.5.1

Valid XHTML 1.0 Strict   CSS ist valide!
bioinfweb RSS feed bioinfweb on twitter
bioinfweb - Biology & Informatics Website