src2/fr/orsay/lri/varna/models/rna/VARNASecDraw.java

   1 package fr.orsay.lri.varna.models.rna;
   2
   3 import java.awt.Rectangle;
   4 import java.awt.Shape;
   5 import java.awt.geom.AffineTransform;
   6 import java.awt.geom.Area;
   7 import java.awt.geom.GeneralPath;
   8 import java.awt.geom.PathIterator;
   9 import java.awt.geom.Point2D;
  10 import java.awt.geom.Rectangle2D;
  11 import java.lang.reflect.Array;
  12 import java.util.ArrayList;
  13 import java.util.Arrays;
  14 import java.util.LinkedList;
  15 import java.util.Random;
  16 import java.util.Stack;
  17 import java.util.Vector;
  18
  19 import fr.orsay.lri.varna.VARNAPanel;
  20
  21 public class VARNASecDraw {
  22         public static VARNAPanel _vp = null;
  23
  24
  25         public abstract class Portion
  26         {
  27                 public abstract ArrayList<Integer> getBaseList();
  28                 public abstract int getNumBases();
  29                 public abstract GeneralPath getOutline(RNA r);
  30
  31         };
  32
  33         public class UnpairedPortion extends Portion
  34         {
  35                 int _pos;
  36                 int _len;
  37                 public UnpairedPortion(int pos, int len)
  38                 {
  39                         _len = len;
  40                         _pos = pos;
  41                 }
  42                 @Override
  43                 public ArrayList<Integer> getBaseList() {
  44                         // TODO Auto-generated method stub
  45                         return null;
  46                 }
  47                 public String toString()
  48                 {
  49                         return "U["+_pos+","+(_pos+_len-1)+"]";
  50                 }
  51
  52                 public int getNumBases() {
  53                         return _len;
  54                 }
  55
  56
  57                 public GeneralPath getOutline(RNA r) {
  58
  59                         GeneralPath gp = new GeneralPath();
  60                         ArrayList<ModeleBase> l = r.get_listeBases();
  61                         Point2D.Double p0 = l.get(_pos).getCoords();
  62                         gp.moveTo((float)p0.x, (float)p0.y);
  63                         for (int i=1;i<_len;i++)
  64                         {
  65                                 Point2D.Double p = l.get(_pos+i).getCoords();
  66                                 gp.lineTo((float)p.x, (float)p.y);
  67                         }
  68                         return gp;
  69                 }
  70         };
  71
  72         public class PairedPortion extends Portion
  73         {
  74                 int _pos1;
  75                 int _pos2;
  76                 int _len;
  77                 RNATree _r;
  78
  79                 public PairedPortion(int pos1,int pos2, int len, RNATree r)
  80                 {
  81                         _pos1 = pos1;
  82                         _pos2 = pos2;
  83                         _len = len;
  84                         _r =r;
  85                 }
  86
  87                 @Override
  88                 public ArrayList<Integer> getBaseList() {
  89                         // TODO Auto-generated method stub
  90                         return null;
  91                 }
  92
  93                 public String toString()
  94                 {
  95                         return "H["+_pos1+","+(_pos1+_len-1)+"]["+(_pos2-_len+1)+","+(_pos2)+"]\n"+_r.toString();
  96                 }
  97
  98                 @Override
  99                 public int getNumBases() {
 100                         return 2*_len;
 101                 }
 102
 103                 public GeneralPath getLocalOutline(RNA r) {
 104                         GeneralPath gp = new GeneralPath();
 105                         if (_len>0)
 106                         {
 107                                 ArrayList<ModeleBase> l = r.get_listeBases();
 108                                 Point2D.Double p1 = l.get(_pos1).getCoords();
 109                                 Point2D.Double p2 = l.get(_pos1+_len-1).getCoords();
 110                                 Point2D.Double p3 = l.get(_pos2-_len+1).getCoords();
 111                                 Point2D.Double p4 = l.get(_pos2).getCoords();
 112                                 gp.moveTo((float)p1.x, (float)p1.y);
 113                                 gp.lineTo((float)p2.x, (float)p2.y);
 114                                 gp.lineTo((float)p3.x, (float)p3.y);
 115                                 gp.lineTo((float)p4.x, (float)p4.y);
 116                         }
 117                         return gp;
 118                 }
 119
 120
 121                 public GeneralPath getOutline(RNA r) {
 122                         return getOutline(r,false);
 123                 }
 124
 125                 public GeneralPath getOutline(RNA r, boolean local) {
 126                         ArrayList<ModeleBase> l = r.get_listeBases();
 127                         Point2D.Double p1 = l.get(_pos1).getCoords();
 128                         Point2D.Double p2 = l.get(_pos1+_len-1).getCoords();
 129                         Point2D.Double p3 = l.get(_pos2-_len+1).getCoords();
 130                         Point2D.Double p4 = l.get(_pos2).getCoords();
 131                         GeneralPath gp = new GeneralPath();
 132                         gp.moveTo((float)p1.x, (float)p1.y);
 133                         gp.lineTo((float)p2.x, (float)p2.y);
 134                         if (!local)
 135                                 gp.append(_r.getOutline(r), true);
 136                         gp.lineTo((float)p3.x, (float)p3.y);
 137                         gp.lineTo((float)p4.x, (float)p4.y);
 138
 139                         return gp;
 140
 141                 }
 142         };
 143         public  int   _depth = 0;
 144
 145
 146         public class RNATree
 147         {
 148                 ArrayList<Portion> _portions = new ArrayList<Portion>();
 149                 int _numPairedPortions=0;
 150                 public RNATree()
 151                 {
 152
 153                 }
 154
 155
 156                 public void addPortion(Portion p)
 157                 {
 158                         _portions.add(p);
 159                         if (p instanceof PairedPortion)
 160                         {
 161                                 _numPairedPortions++;
 162                         }
 163                 }
 164
 165                 public int getNumPortions()
 166                 {
 167                         return _portions.size();
 168                 }
 169
 170                 public Portion getPortion(int i)
 171                 {
 172                         return _portions.get(i);
 173                 }
 174
 175                 public String toString()
 176                 {
 177                         String result = "";
 178                         _depth++;
 179                         for (int i=0;i<_portions.size();i++ )
 180                         {
 181                                 result += String.format("%1$#" + _depth + "s", ' ');
 182                                 result += _portions.get(i).toString();
 183                                 if (i<_portions.size()-1)
 184                                   result += "\n";
 185                         }
 186                         _depth--;
 187                         return result;
 188                 }
 189
 190                 public GeneralPath getOutline(RNA r) {
 191                         GeneralPath result = new GeneralPath();
 192                         for (int i=0;i<_portions.size();i++)
 193                         {
 194                                 result.append(_portions.get(i).getOutline(r),true);
 195                         }
 196                         return result;
 197                 }
 198         };
 199
 200
 201         private void buildTree(int i, int j, RNATree parent,  RNA r)
 202         {
 203                 //LinkedList<BuildTreeArgs> s = new LinkedList<BuildTreeArgs>();
 204                 //s.add(new BuildTreeArgs(xi, xj, xparent,xr));
 205                 //while(s.size()!=0)
 206                 //{
 207
 208                         //BuildTreeArgs a = s.removeLast();
 209                         if (i >= j) {
 210                                 parent.addPortion(new UnpairedPortion(i,j-i+1));
 211                         }
 212                         // BasePaired
 213                         if (r.get_listeBases().get(i).getElementStructure() == j)
 214                         {
 215                                 int i1 = i;
 216                                 int j1 = j;
 217                                 boolean over = false;
 218                                 while( (i+1<r.get_listeBases().size())  &&  (j-1>=0)&&  (i+1<=j-1) && !over)
 219                                 {
 220                                         if (r.get_listeBases().get(i).getElementStructure() != j)
 221                                         { over = true; }
 222                                         else
 223                                         { i++;j--; }
 224                                 }
 225                                 int i2 = i;
 226                                 int j2 = j;
 227                                 RNATree t = new RNATree();
 228                                 if (i<j-1)
 229                                   buildTree(i2,j2,t,r);
 230                                 PairedPortion p = new PairedPortion(i1,j1,i2-i1,t);
 231                                 parent.addPortion(p);
 232                         } else
 233                         {
 234                                 int k = i;
 235                                 int l;
 236                                 int start = k;
 237                                 int len = 0;
 238                                 while (k <= j) {
 239                                         l = r.get_listeBases().get(k).getElementStructure();
 240                                         if (l != -1)
 241                                         {
 242                                                 if (len>0)
 243                                                 { parent.addPortion(new UnpairedPortion(start,len)); }
 244                                                 buildTree(k, l, parent,  r);
 245                                                 k = l + 1;
 246                                                 start = k;
 247                                                 len = 0;
 248                                         } else {
 249                                                 len++;
 250                                                 k++;
 251                                         }
 252                                 }
 253                                 if (len>0)
 254                                 {
 255                                         parent.addPortion(new UnpairedPortion(start,len));
 256                                 }
 257                         }
 258                 }
 259
 260         /*
 261         public void drawTree(double x0, double y0, RNATree t, double dir, RNA r, double straightness)
 262         {
 263                 boolean collision = true;
 264                 double x=x0;
 265                 double y=y0;
 266                 double multRadius = 1.0;
 267                 double initCirc = r.BASE_PAIR_DISTANCE+r.LOOP_DISTANCE;
 268                 for (int i=0;i<t.getNumPortions();i++ )
 269                 {
 270                         Portion p = t.getPortion(i);
 271                         if (p instanceof PairedPortion)
 272                         {
 273                                 initCirc += (r.BASE_PAIR_DISTANCE+r.LOOP_DISTANCE);
 274                         }
 275                         else
 276                         {
 277                                 initCirc += r.LOOP_DISTANCE*(p.getNumBases());
 278                         }
 279                 }
 280                 while(collision)
 281                 {
 282                                 double totCirc = r.BASE_PAIR_DISTANCE+straightness*r.LOOP_DISTANCE;
 283                                 for (int i=0;i<t.getNumPortions();i++ )
 284                                 {
 285                                         Portion p = t.getPortion(i);
 286                                         if (p instanceof PairedPortion)
 287                                         {
 288                                                 totCirc += (r.BASE_PAIR_DISTANCE+r.LOOP_DISTANCE);
 289                                         }
 290                                         else
 291                                         {
 292                                                 double mod = 1.0;
 293                                                 if ((i==0) || (i==t.getNumPortions()-1))
 294                                                         mod = straightness;
 295                                                   totCirc += mod*r.LOOP_DISTANCE*(p.getNumBases());
 296                                         }
 297                                 }
 298                                 double radius = multRadius*initCirc/(2.0*Math.PI);
 299                         //radius = 2.0;
 300                         x = x0+radius*Math.cos(dir+Math.PI);
 301                         y = y0+radius*Math.sin(dir+Math.PI);
 302                         dir += 2.0*Math.PI;
 303                         double angleIncr = (2.0*Math.PI)/(totCirc);
 304                         double circ = r.BASE_PAIR_DISTANCE/2.0+straightness*r.LOOP_DISTANCE;
 305                         double ndir;
 306                         ArrayList<GeneralPath> shapes = new ArrayList<GeneralPath>();
 307                         for (int i=0;i<t.getNumPortions();i++ )
 308                         {
 309                                 Portion p = t.getPortion(i);
 310                                 if (p instanceof PairedPortion)
 311                                 {
 312                                         circ+=r.BASE_PAIR_DISTANCE/2.0;
 313                                         ndir = dir + circ*angleIncr;
 314                                         PairedPortion pp = (PairedPortion) p;
 315                                         for(int j=0;j<pp._len;j++)
 316                                         {
 317                                                 int i1 = pp._pos1+j;
 318                                                 int i2 = pp._pos2-j;
 319                                                 double vx = Math.cos(ndir);
 320                                                 double vy = Math.sin(ndir);
 321                                                 double nx = x+((j*r.LOOP_DISTANCE+radius)*vx);
 322                                                 double ny = y+((j*r.LOOP_DISTANCE+radius)*vy);
 323                                                 r.get_listeBases().get(i1).set_coords(new Point2D.Double(nx+r.BASE_PAIR_DISTANCE*vy/ 2.0,ny-r.BASE_PAIR_DISTANCE*vx/ 2.0));
 324                                                 r.get_listeBases().get(i2).set_coords(new Point2D.Double(nx-r.BASE_PAIR_DISTANCE*vy/ 2.0,ny+r.BASE_PAIR_DISTANCE*vx/ 2.0));
 325                                         }
 326                                         double nx = x+(((pp._len-1)*r.LOOP_DISTANCE+radius)*Math.cos(ndir));
 327                                         double ny = y+(((pp._len-1)*r.LOOP_DISTANCE+radius)*Math.sin(ndir));
 328                                         drawTree(nx, ny, pp._r, ndir+Math.PI, r, straightness);
 329                                         shapes.add(pp.getOutline(r));
 330                                         circ += r.LOOP_DISTANCE + r.BASE_PAIR_DISTANCE/2.0;
 331                                 }
 332                                 else if (p instanceof UnpairedPortion)
 333                                 {
 334                                         UnpairedPortion up = (UnpairedPortion) p;
 335                                         double mod = 1.0;
 336                                         if ((i==0) || (i==t.getNumPortions()-1))
 337                                                   mod = straightness;
 338                                         for(int j=0;j<up._len;j++)
 339                                         {
 340                                                 ndir = dir + circ*angleIncr;
 341                                                 double vx = Math.cos(ndir);
 342                                                 double vy = Math.sin(ndir);
 343                                                 double nx = x+((radius)*vx);
 344                                                 double ny = y+((radius)*vy);
 345                                                 r.get_listeBases().get(up._pos+j).set_coords(new Point2D.Double(nx,ny));
 346                                                 circ += mod*r.LOOP_DISTANCE;
 347                                         }
 348                                 }
 349                                 //System.out.println(dir);
 350                         }
 351                         circ += r.BASE_PAIR_DISTANCE/2.0;
 352                         System.out.println(""+circ+"/"+totCirc);
 353                         if(shapes.size()>0)
 354                         {
 355                                 collision = false;
 356                                 for (int i=0;(i<shapes.size()) && !collision;i++)
 357                                 {
 358                                         Area a1 = new Area(shapes.get(i));
 359                                         for (int j=i+1;(j<shapes.size())&& !collision;j++)
 360                                         {
 361                                                 Area a2 = new Area(shapes.get(j));
 362                                                 a1.intersect(a2);
 363                                                 if (!a1.isEmpty())
 364                                                 {
 365                                                         collision = true;
 366                                                 }
 367                                         }
 368                                 }
 369                                 if (collision)
 370                                 {
 371                                         straightness *= 1.2;
 372                                         multRadius *= 1.5;
 373                                 }
 374
 375                         }
 376                         else
 377                         {
 378                                 collision = false;
 379                         }
 380                 }
 381         }
 382         */
 383
 384         public int[] nextPlacement(int[] p) throws Exception
 385         {
 386                  //System.out.println(Arrays.toString(p));
 387                 int i=p.length-1;
 388                 int prev = MAX_NUM_DIR;
 389                 boolean stop = false;
 390                 while((i>=0) && !stop)
 391                 {
 392                         if (p[i]==prev-1)
 393                         {
 394                                 prev = p[i];
 395                                 i--;
 396                         }
 397                         else
 398                         { stop = true; }
 399                 }
 400                 if (i<0)
 401                         throw new Exception("No more placement available");
 402                 p[i]++;
 403                 i++;
 404                 while(i<p.length)
 405                 {
 406                         p[i] = p[i-1]+1;
 407                         i++;
 408                 }
 409                  //System.out.println(Arrays.toString(p));
 410                 return p;
 411         }
 412
 413
 414         public void drawTree(double x0, double y0, RNATree t, double dir, RNA r) throws Exception
 415         {
 416                 boolean collision = true;
 417                 double x=x0;
 418                 double y=y0;
 419                 int numHelices = 0;
 420                 int nbHel = 1;
 421                 int nbUn = 0;
 422                 double totCirc = r.BASE_PAIR_DISTANCE+r.LOOP_DISTANCE;
 423                 for (int i=0;i<t.getNumPortions();i++ )
 424                 {
 425                         Portion p = t.getPortion(i);
 426                         if (p instanceof PairedPortion)
 427                         {
 428                                 totCirc += (r.BASE_PAIR_DISTANCE+r.LOOP_DISTANCE);
 429                                 nbHel += 1;
 430                         }
 431                         else
 432                         {
 433                                 totCirc += r.LOOP_DISTANCE*(p.getNumBases());
 434                                 nbUn += p.getNumBases()+1;
 435                         }
 436                 }
 437                 double radius = r.determineRadius(nbHel, nbUn, totCirc/(2.0*Math.PI));
 438
 439                 for (int i=0;i<t.getNumPortions();i++ )
 440                 {
 441                         Portion p = t.getPortion(i);
 442                         if (p instanceof PairedPortion)
 443                         {
 444                                 numHelices++;
 445                         }
 446                 }
 447                 int[] placement = new int[numHelices];
 448                 double inc = ((double)MAX_NUM_DIR)/((double)numHelices+1);
 449                 double val = inc;
 450                 for (int i=0;i<numHelices;i++ )
 451                 {
 452                         placement[i] = (int)Math.round(val);
 453                         val += inc;
 454                 }
 455                 System.out.println();
 456                 double angleIncr = 2.0*Math.PI/(double)MAX_NUM_DIR;
 457                 while(collision)
 458                 {
 459                         x = x0+radius*Math.cos(dir+Math.PI);
 460                         y = y0+radius*Math.sin(dir+Math.PI);
 461                         ArrayList<GeneralPath> shapes = new ArrayList<GeneralPath>();
 462                         int curH = 0;
 463                         for (int i=0;i<t.getNumPortions();i++ )
 464                         {
 465                                 Portion p = t.getPortion(i);
 466                                 if (p instanceof PairedPortion)
 467                                 {
 468                                         double ndir = dir + placement[curH]*angleIncr;
 469                                         curH++;
 470                                         PairedPortion pp = (PairedPortion) p;
 471                                         for(int j=0;j<pp._len;j++)
 472                                         {
 473                                                 int i1 = pp._pos1+j;
 474                                                 int i2 = pp._pos2-j;
 475                                                 double vx = Math.cos(ndir);
 476                                                 double vy = Math.sin(ndir);
 477                                                 double nx = x+(((j)*r.LOOP_DISTANCE+radius)*vx);
 478                                                 double ny = y+(((j)*r.LOOP_DISTANCE+radius)*vy);
 479                                                 r.get_listeBases().get(i1).setCoords(new Point2D.Double(nx+r.BASE_PAIR_DISTANCE*vy/ 2.0,ny-r.BASE_PAIR_DISTANCE*vx/ 2.0));
 480                                                 r.get_listeBases().get(i2).setCoords(new Point2D.Double(nx-r.BASE_PAIR_DISTANCE*vy/ 2.0,ny+r.BASE_PAIR_DISTANCE*vx/ 2.0));
 481                                         }
 482                                         double nx = x+(((pp._len-1)*r.LOOP_DISTANCE+radius)*Math.cos(ndir));
 483                                         double ny = y+(((pp._len-1)*r.LOOP_DISTANCE+radius)*Math.sin(ndir));
 484                                         drawTree(nx, ny, pp._r, ndir+Math.PI, r);
 485                                         shapes.add(pp.getOutline(r));
 486                                 }
 487                                 else if (p instanceof UnpairedPortion)
 488                                 {
 489                                         UnpairedPortion up = (UnpairedPortion) p;
 490                                         for(int j=0;j<up._len;j++)
 491                                         {
 492                                                 /*ndir = dir + circ*angleIncr;
 493                                                         double vx = Math.cos(ndir);
 494                                                         double vy = Math.sin(ndir);
 495                                                         double nx = x+((radius)*vx);
 496                                                         double ny = y+((radius)*vy);
 497                                                         r.get_listeBases().get(up._pos+j).set_coords(new Point2D.Double(nx,ny));
 498                                                         circ += mod*r.LOOP_DISTANCE;*/
 499                                                 r.get_listeBases().get(up._pos+j).setCoords(new Point2D.Double(x,y));
 500                                         }
 501                                 }
 502                                 //System.out.println(dir);
 503                         }
 504                         if(shapes.size()>0)
 505                         {
 506                                 collision = false;
 507                                 for (int i=0;(i<shapes.size()) && !collision;i++)
 508                                 {
 509                                         Area a1 = new Area(shapes.get(i));
 510                                         for (int j=i+1;(j<shapes.size())&& !collision;j++)
 511                                         {
 512                                                 Area a2 = new Area(shapes.get(j));
 513                                                 a1.intersect(a2);
 514                                                 if (!a1.isEmpty())
 515                                                 {
 516                                                         collision = true;
 517                                                 }
 518                                         }
 519                                 }
 520                                 if (collision)
 521                                 {
 522                                         placement = nextPlacement(placement);
 523                                 }
 524
 525                         }
 526                         else
 527                         {
 528                                 collision = false;
 529                         }
 530                 }
 531         }
 532
 533
 534         private class HelixEmbedding
 535         {
 536                 private GeneralPath _clip;
 537                 Point2D.Double _support;
 538                 ArrayList<HelixEmbedding> _children = new ArrayList<HelixEmbedding>();
 539                 ArrayList<Integer> _indices = new ArrayList<Integer>();
 540                 PairedPortion _p;
 541                 RNA _r;
 542                 HelixEmbedding _parent;
 543
 544                 public HelixEmbedding(Point2D.Double support, PairedPortion p, RNA r, HelixEmbedding parent)
 545                 {
 546                         _support = support;
 547                         _clip = p.getLocalOutline(r);
 548                         _p = p;
 549                         _r = r;
 550                         _parent = parent;
 551                 }
 552
 553                 public void addHelixEmbedding(HelixEmbedding h, int index)
 554                 {
 555                         _children.add(h);
 556                         _indices.add(index);
 557                 }
 558
 559                 public GeneralPath getShape()
 560                 {
 561                         return _clip;
 562                 }
 563
 564
 565                 public int chooseNextMove()
 566                 {
 567                         int i = _parent._children.indexOf(this);
 568                         int min;
 569                         int max;
 570                         if (_parent._children.size()<VARNASecDraw.MAX_NUM_DIR-1)
 571                         {
 572                                 if (_parent._children.size()==1)
 573                                 { min=1;max=VARNASecDraw.MAX_NUM_DIR-1; }
 574                                 else
 575                                 {
 576                                         if (i==0)
 577                                         { min = 1; }
 578                                         else
 579                                         { min = _parent._indices.get(i-1)+1;}
 580                                         if (i==_parent._children.size()-1)
 581                                         { max = VARNASecDraw.MAX_NUM_DIR-1; }
 582                                         else
 583                                         { max = _parent._indices.get(i+1)-1;}
 584                                 }
 585                                 int prevIndex = _parent._indices.get(i);
 586                                 int newIndex = min+_rnd.nextInt(max+1-min);
 587                                 double rot = ((double)(newIndex-prevIndex)*Math.PI*2.0)/MAX_NUM_DIR;
 588                                 _parent._indices.set(i, newIndex);
 589                                 rotate(rot);
 590                                 return newIndex-prevIndex;
 591                         }
 592                         return 0;
 593                 }
 594
 595                 public void cancelMove(int delta)
 596                 {
 597                         int i = _parent._children.indexOf(this);
 598                         int prevIndex = _parent._indices.get(i);
 599                         double rot = ((double)(-delta)*Math.PI*2.0)/MAX_NUM_DIR;
 600                         _parent._indices.set(i, prevIndex-delta);
 601                         rotate(rot);
 602                 }
 603
 604                 public void rotate(double angle)
 605                 {
 606                         transform(AffineTransform.getRotateInstance(angle, _support.x, _support.y));
 607                 }
 608
 609                 private void transform(AffineTransform a)
 610                 {
 611                         _clip.transform(a);
 612                         Point2D p = a.transform(_support, null);
 613                         _support.setLocation(p.getX(), p.getY());
 614                         for (int i=0;i<_children.size();i++)
 615                         {
 616                                 _children.get(i).transform(a);
 617                         }
 618                 }
 619
 620                 public void reflectCoordinates()
 621                 {
 622                         ArrayList<ModeleBase> mbl = _r.get_listeBases();
 623
 624                         if (_p._len>0)
 625                         {
 626                                 PathIterator pi = _clip.getPathIterator(AffineTransform.getRotateInstance(0.0));
 627                                 ArrayList<Point2D.Double> p = new ArrayList<Point2D.Double>();
 628                                 while(!pi.isDone())
 629                                 {
 630                                         double[] args = new double[6];
 631                                         int type= pi.currentSegment(args);
 632                                         if ((type == PathIterator.SEG_MOVETO)  || (type == PathIterator.SEG_LINETO))
 633                                         {
 634
 635                                                 Point2D.Double np = new Point2D.Double(args[0],args[1]);
 636                                                 p.add(np);
 637                                                 System.out.println(Arrays.toString(args));
 638                                         }
 639                                         pi.next();
 640                                 }
 641                                 if (p.size()<4)
 642                                 { return; }
 643
 644                                 Point2D.Double startLeft = p.get(0);
 645                                 Point2D.Double endLeft = p.get(1);
 646                                 Point2D.Double endRight = p.get(2);
 647                                 Point2D.Double startRight = p.get(3);
 648
 649                                 double d = startLeft.distance(endLeft);
 650                                 double vx = endLeft.x-startLeft.x;
 651                                 double vy = endLeft.y-startLeft.y;
 652                                 double interval = 0.0;
 653                                 if (_p._len>1)
 654                                 {
 655                                         vx/=d;
 656                                         vy/=d;
 657                                         interval = d/((double)_p._len-1);
 658                                         System.out.println("DELTA: "+interval+" "+_r.LOOP_DISTANCE);
 659                                 }
 660                                 for (int n=0;n<_p._len;n++)
 661                                 {
 662                                         int i = _p._pos1 + n;
 663                                         int j = _p._pos2 - n;
 664                                         ModeleBase mbLeft = mbl.get(i);
 665                                         mbLeft.setCoords(new Point2D.Double(startLeft.x+n*vx*interval, startLeft.y+n*vy*interval));
 666                                         ModeleBase mbRight = mbl.get(j);
 667                                         mbRight.setCoords(new Point2D.Double(startRight.x+n*vx*interval, startRight.y+n*vy*interval));
 668                                 }
 669                         }
 670                         for (int i=0;i<_children.size();i++)
 671                         {
 672                                 _children.get(i).reflectCoordinates();
 673                         }
 674                         if (_children.size()>0)
 675                         {
 676                                 Point2D.Double center = _children.get(0)._support;
 677                                 for (int i=0;i<_p._r.getNumPortions();i++)
 678                                 {
 679                                         Portion p = _p._r.getPortion(i);
 680                                         if (p instanceof UnpairedPortion)
 681                                         {
 682                                                 UnpairedPortion up = (UnpairedPortion) p;
 683                                                 for (int j=0;j<up._len;j++)
 684                                                 {
 685                                                         int n = up._pos + j;
 686                                                         ModeleBase mbLeft = mbl.get(n);
 687                                                         mbLeft.setCoords(center);
 688                                                 }
 689                                         }
 690                                 }
 691                         }
 692                         else
 693                         {
 694                                 placeTerminalLoop(mbl,_r);
 695                         }
 696                 }
 697
 698                 private void placeTerminalLoop(ArrayList<ModeleBase> mbl, RNA r)
 699                 {
 700                         if ((_children.size()==0)&&(_p._r.getNumPortions()==1))
 701                         {
 702                                 Portion p = _p._r.getPortion(0);
 703                                 if (p instanceof UnpairedPortion)
 704                                 {
 705                                         UnpairedPortion up = (UnpairedPortion) p;
 706                                         double rad = determineRadius(1,up.getNumBases(),_r);
 707                                         int a = _p._pos1+_p._len-1;
 708                                         int b = _p._pos2-(_p._len-1);
 709                                         ModeleBase mbLeft = mbl.get(a);
 710                                         ModeleBase mbRight = mbl.get(b);
 711                                         Point2D.Double pl = mbLeft.getCoords();
 712                                         Point2D.Double pr = mbRight.getCoords();
 713                                         Point2D.Double pm = new Point2D.Double((pl.x+pr.x)/2.0,(pl.y+pr.y)/2.0);
 714                                         double vx = (pl.x-pr.x)/pl.distance(pr);
 715                                         double vy = (pl.y-pr.y)/pl.distance(pr);
 716                                         double vnx = -vy, vny = vx;
 717                                         Point2D.Double pc = new Point2D.Double(pm.x+rad*vnx,pm.y+rad*vny);
 718                                         double circ = r.LOOP_DISTANCE*(1.0+up.getNumBases())+r.BASE_PAIR_DISTANCE;
 719                                         double incrLoop = Math.PI*2.0*r.LOOP_DISTANCE/circ;
 720                                         double angle = Math.PI*2.0*r.BASE_PAIR_DISTANCE/(2.0*circ);
 721                                         for (int j=0;j<up._len;j++)
 722                                         {
 723                                                 int n = up._pos + j;
 724                                                 ModeleBase mb = mbl.get(n);
 725                                                 angle += incrLoop;
 726                                                 double dx = -Math.cos(angle)*vnx+Math.sin(angle)*vx;
 727                                                 double dy = -Math.cos(angle)*vny+Math.sin(angle)*vy;
 728 //                                              Point2D.Double pf = new Point2D.Double(pc.x,pc.y);
 729                                                 Point2D.Double pf = new Point2D.Double(pc.x+rad*dx,pc.y+rad*dy);
 730                                                 mb.setCoords(pf);
 731                                         }
 732
 733                                 }
 734                         }
 735                 }
 736
 737
 738
 739                 public String toString()
 740                 {
 741                         return "Emb.Hel.: "+_p.toString();
 742                 }
 743         }
 744
 745         public double determineRadius(int numHelices, int numUnpaired, RNA r)
 746         {
 747                 double circ = numHelices*r.BASE_PAIR_DISTANCE+(numHelices+numUnpaired)*r.LOOP_DISTANCE;
 748                 return circ/(2.0*Math.PI);
 749         }
 750
 751
 752         public void predrawTree(double x0, double y0, RNATree t, double dir, RNA r, HelixEmbedding parent, ArrayList<HelixEmbedding> all) throws Exception
 753         {
 754                 double x=x0;
 755                 double y=y0;
 756                 int numHelices = 0;
 757                 int numUBases = 0;
 758                 double totCirc = r.BASE_PAIR_DISTANCE+r.LOOP_DISTANCE;
 759                 for (int i=0;i<t.getNumPortions();i++ )
 760                 {
 761                         Portion p = t.getPortion(i);
 762                         if (p instanceof PairedPortion)
 763                         {
 764                                 totCirc += (r.BASE_PAIR_DISTANCE+r.LOOP_DISTANCE);
 765                                 numHelices++;
 766                         }
 767                         else
 768                         {
 769                                   totCirc += r.LOOP_DISTANCE*(p.getNumBases());
 770                                   numUBases += p.getNumBases();
 771                         }
 772                 }
 773                 double radius = determineRadius(numHelices+1,numUBases,r);
 774
 775                 int[] placement = new int[numHelices];
 776                 double inc = ((double)MAX_NUM_DIR)/((double)numHelices+1);
 777                 double val = inc;
 778                 for (int i=0;i<numHelices;i++ )
 779                 {
 780                         placement[i] = (int)Math.round(val);
 781                         val += inc;
 782                 }
 783                 double angleIncr = 2.0*Math.PI/(double)MAX_NUM_DIR;
 784                         x = x0+radius*Math.cos(dir+Math.PI);
 785                         y = y0+radius*Math.sin(dir+Math.PI);
 786                         int curH = 0;
 787                         for (int i=0;i<t.getNumPortions();i++ )
 788                         {
 789                                 Portion p = t.getPortion(i);
 790                                 if (p instanceof PairedPortion)
 791                                 {
 792                                         double ndir = dir + placement[curH]*angleIncr;
 793                                         PairedPortion pp = (PairedPortion) p;
 794                                         for(int j=0;j<pp._len;j++)
 795                                         {
 796                                                 int i1 = pp._pos1+j;
 797                                                 int i2 = pp._pos2-j;
 798                                                 double vx = Math.cos(ndir);
 799                                                 double vy = Math.sin(ndir);
 800                                                 double nx = x+(((j)*r.LOOP_DISTANCE+radius)*vx);
 801                                                 double ny = y+(((j)*r.LOOP_DISTANCE+radius)*vy);
 802                                                 r.get_listeBases().get(i1).setCoords(new Point2D.Double(nx+r.BASE_PAIR_DISTANCE*vy/ 2.0,ny-r.BASE_PAIR_DISTANCE*vx/ 2.0));
 803                                                 r.get_listeBases().get(i2).setCoords(new Point2D.Double(nx-r.BASE_PAIR_DISTANCE*vy/ 2.0,ny+r.BASE_PAIR_DISTANCE*vx/ 2.0));
 804                                         }
 805                                         double nx = x+(((pp._len-1)*r.LOOP_DISTANCE+radius)*Math.cos(ndir));
 806                                         double ny = y+(((pp._len-1)*r.LOOP_DISTANCE+radius)*Math.sin(ndir));
 807                                         HelixEmbedding nh = new HelixEmbedding(new Point2D.Double(x,y),pp,r,parent);
 808                                         parent.addHelixEmbedding(nh,placement[curH]);
 809                                         all.add(nh);
 810                                         predrawTree(nx, ny, pp._r, ndir+Math.PI, r, nh, all);
 811                                         curH++;
 812                                 }
 813                                 else if (p instanceof UnpairedPortion)
 814                                 {
 815                                         UnpairedPortion up = (UnpairedPortion) p;
 816                                         for(int j=0;j<up._len;j++)
 817                                         {
 818                                                 r.get_listeBases().get(up._pos+j).setCoords(new Point2D.Double(x,y));
 819                                         }
 820                                 }
 821                                 //System.out.println(dir);
 822                         }
 823         }
 824
 825
 826         public static Random _rnd = new Random();
 827
 828         private static int MAX_NUM_DIR = 8;
 829
 830         public RNATree drawRNA(double dirAngle, RNA r) {
 831                 RNATree t = new RNATree();
 832                 buildTree(0, r.get_listeBases().size() - 1, t,  r );
 833                 System.out.println(t);
 834                 ArrayList<HelixEmbedding> all = new ArrayList<HelixEmbedding>();
 835                 HelixEmbedding root = null;
 836                 try {
 837                         root = new HelixEmbedding(new Point2D.Double(0.0,0.0),new PairedPortion(0,0,0,t),r,null);
 838                         predrawTree(0,0,t,0.0,r,root,all);
 839                         int steps=1000;
 840                         double prevbadness = Double.MAX_VALUE;
 841                         while((steps>0)&&(prevbadness>0))
 842                         {
 843
 844                                 // Generating new structure
 845                                 HelixEmbedding chosen = all.get(_rnd.nextInt(all.size()));
 846                                 int delta =  chosen.chooseNextMove();
 847                                 // Draw current
 848                                 if (_vp!=null)
 849                                         {
 850                                                 GeneralPath p = new GeneralPath();
 851                                                 for (int i=0;i<all.size();i++)
 852                                                 { p.append(all.get(i).getShape(),false); }
 853                                                 r._debugShape = p;
 854                                                 _vp.paintImmediately(0, 0, _vp.getWidth(), _vp.getHeight());
 855                                         }
 856
 857                                 //Evaluating solution
 858                                 double badness = 0.0;
 859                                 for (int i=0;i<all.size();i++)
 860                                 {
 861                                         Shape s1 = all.get(i).getShape();
 862                                         for (int j=i+1;j<all.size();j++)
 863                                         {
 864                                                 Shape s2 = all.get(j).getShape();
 865                                                 Area a = new Area(s1);
 866                                                 a.intersect(new Area(s2));
 867                                                 if (!a.isEmpty())
 868                                                 {
 869                                                         badness ++;
 870                                                 }
 871                                         }
 872                                 }
 873
 874                                 if (badness-prevbadness>0)
 875                                 {
 876                                         chosen.cancelMove(delta);
 877                                 }
 878                                 else
 879                                 {
 880                                         prevbadness = badness;
 881                                 }
 882
 883                                 System.out.println(badness);
 884
 885                                 steps--;
 886                         }
 887                         if (root!=null)
 888                         { root.reflectCoordinates(); }
 889                 } catch (Exception e) {
 890                         // TODO Auto-generated catch block
 891                         e.printStackTrace();
 892                 }
 893                 return t;
 894         };
 895
 896 }