src/jalview/datamodel/HiddenColumns.java

   1 /*
   2  * Jalview - A Sequence Alignment Editor and Viewer ($$Version-Rel$$)
   3  * Copyright (C) $$Year-Rel$$ The Jalview Authors
   4  *
   5  * This file is part of Jalview.
   6  *
   7  * Jalview is free software: you can redistribute it and/or
   8  * modify it under the terms of the GNU General Public License
   9  * as published by the Free Software Foundation, either version 3
  10  * of the License, or (at your option) any later version.
  11  *
  12  * Jalview is distributed in the hope that it will be useful, but
  13  * WITHOUT ANY WARRANTY; without even the implied warranty
  14  * of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  15  * PURPOSE.  See the GNU General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU General Public License
  18  * along with Jalview.  If not, see <http://www.gnu.org/licenses/>.
  19  * The Jalview Authors are detailed in the 'AUTHORS' file.
  20  */
  21 package jalview.datamodel;
  22
  23 import java.util.ArrayList;
  24 import java.util.BitSet;
  25 import java.util.Iterator;
  26 import java.util.List;
  27 import java.util.concurrent.locks.ReentrantReadWriteLock;
  28
  29 public class HiddenColumns
  30 {
  31   private static final int HASH_MULTIPLIER = 31;
  32
  33   private static final ReentrantReadWriteLock LOCK = new ReentrantReadWriteLock();
  34
  35   private HiddenColumnsCursor cursor = new HiddenColumnsCursor();
  36
  37   /*
  38    * list of hidden column [start, end] ranges; the list is maintained in
  39    * ascending start column order
  40    */
  41   private ArrayList<int[]> hiddenColumns;
  42
  43   /**
  44    * Constructor
  45    */
  46   public HiddenColumns()
  47   {
  48   }
  49
  50   /**
  51    * Copy constructor
  52    *
  53    * @param copy
  54    */
  55   public HiddenColumns(HiddenColumns copy)
  56   {
  57     try
  58     {
  59       LOCK.writeLock().lock();
  60       if (copy != null)
  61       {
  62         if (copy.hiddenColumns != null)
  63         {
  64           hiddenColumns = new ArrayList<>();
  65           Iterator<int[]> it = copy.iterator();
  66           while (it.hasNext())
  67           {
  68             hiddenColumns.add(it.next());
  69           }
  70           cursor.resetCursor(hiddenColumns);
  71         }
  72       }
  73     } finally
  74     {
  75       LOCK.writeLock().unlock();
  76     }
  77   }
  78
  79   /**
  80    * Copy constructor within bounds and with offset. Copies hidden column
  81    * regions fully contained between start and end, and offsets positions by
  82    * subtracting offset.
  83    *
  84    * @param copy
  85    *          HiddenColumns instance to copy from
  86    * @param start
  87    *          lower bound to copy from
  88    * @param end
  89    *          upper bound to copy to
  90    * @param offset
  91    *          offset to subtract from each region boundary position
  92    *
  93    */
  94   public HiddenColumns(HiddenColumns copy, int start, int end, int offset)
  95   {
  96     try
  97     {
  98       LOCK.writeLock().lock();
  99       if (copy != null)
 100       {
 101         hiddenColumns = new ArrayList<>();
 102         Iterator<int[]> it = copy.getBoundedIterator(start, end);
 103         while (it.hasNext())
 104         {
 105           int[] region = it.next();
 106           // still need to check boundaries because iterator returns
 107           // all overlapping regions and we need contained regions
 108           if (region[0] >= start && region[1] <= end)
 109           {
 110             hiddenColumns.add(
 111                     new int[]
 112             { region[0] - offset, region[1] - offset });
 113           }
 114         }
 115         cursor.resetCursor(hiddenColumns);
 116       }
 117     } finally
 118     {
 119       LOCK.writeLock().unlock();
 120     }
 121   }
 122
 123   /**
 124    * Output regions data as a string. String is in the format:
 125    * reg0[0]<between>reg0[1]<delimiter>reg1[0]<between>reg1[1] ... regn[1]
 126    *
 127    * @param delimiter
 128    *          string to delimit regions
 129    * @param betweenstring
 130    *          to put between start and end region values
 131    * @return regions formatted according to delimiter and between strings
 132    */
 133   public String regionsToString(String delimiter, String between)
 134   {
 135     try
 136     {
 137       LOCK.readLock().lock();
 138       StringBuilder regionBuilder = new StringBuilder();
 139       if (hiddenColumns != null)
 140       {
 141         Iterator<int[]> it = hiddenColumns.iterator();
 142         while (it.hasNext())
 143         {
 144           int[] range = it.next();
 145           regionBuilder.append(delimiter).append(range[0]).append(between)
 146                   .append(range[1]);
 147           if (!it.hasNext())
 148           {
 149             regionBuilder.deleteCharAt(0);
 150           }
 151         }
 152       }
 153       return regionBuilder.toString();
 154     } finally
 155     {
 156       LOCK.readLock().unlock();
 157     }
 158   }
 159
 160   /**
 161    * Find the number of hidden columns
 162    *
 163    * @return number of hidden columns
 164    */
 165   public int getSize()
 166   {
 167     try
 168     {
 169       LOCK.readLock().lock();
 170       int size = 0;
 171       if (hiddenColumns != null)
 172       {
 173         Iterator<int[]> it = hiddenColumns.iterator();
 174         while (it.hasNext())
 175         {
 176           int[] range = it.next();
 177           size += range[1] - range[0] + 1;
 178         }
 179       }
 180       return size;
 181     } finally
 182     {
 183       LOCK.readLock().unlock();
 184     }
 185   }
 186
 187   /**
 188    * Get the number of distinct hidden regions
 189    *
 190    * @return number of regions
 191    */
 192   public int getNumberOfRegions()
 193   {
 194     try
 195     {
 196       LOCK.readLock().lock();
 197       int num = 0;
 198       if (hasHiddenColumns())
 199       {
 200         num = hiddenColumns.size();
 201       }
 202       return num;
 203     } finally
 204     {
 205       LOCK.readLock().unlock();
 206     }
 207   }
 208
 209   @Override
 210   public boolean equals(Object obj)
 211   {
 212     try
 213     {
 214       LOCK.readLock().lock();
 215
 216       if (!(obj instanceof HiddenColumns))
 217       {
 218         return false;
 219       }
 220       HiddenColumns that = (HiddenColumns) obj;
 221
 222       /*
 223        * check hidden columns are either both null, or match
 224        */
 225       if (this.hiddenColumns == null)
 226       {
 227         return (that.hiddenColumns == null);
 228       }
 229       if (that.hiddenColumns == null
 230               || that.hiddenColumns.size() != this.hiddenColumns.size())
 231       {
 232         return false;
 233       }
 234
 235       Iterator<int[]> it = hiddenColumns.iterator();
 236       Iterator<int[]> thatit = that.iterator();
 237       while (it.hasNext())
 238       {
 239         int[] thisRange = it.next();
 240         int[] thatRange = thatit.next();
 241         if (thisRange[0] != thatRange[0] || thisRange[1] != thatRange[1])
 242         {
 243           return false;
 244         }
 245       }
 246       return true;
 247     } finally
 248     {
 249       LOCK.readLock().unlock();
 250     }
 251   }
 252
 253   /**
 254    * Return absolute column index for a visible column index
 255    *
 256    * @param column
 257    *          int column index in alignment view (count from zero)
 258    * @return alignment column index for column
 259    */
 260   public int adjustForHiddenColumns(int column)
 261   {
 262     try
 263     {
 264       LOCK.readLock().lock();
 265       int result = column;
 266
 267       if (hiddenColumns != null)
 268       {
 269         result += cursor.getHiddenOffset(column);
 270       }
 271
 272       return result;
 273     } finally
 274     {
 275       LOCK.readLock().unlock();
 276     }
 277   }
 278
 279   /**
 280    * Use this method to find out where a column will appear in the visible
 281    * alignment when hidden columns exist. If the column is not visible, then the
 282    * left-most visible column will always be returned.
 283    *
 284    * @param hiddenColumn
 285    *          the column index in the full alignment including hidden columns
 286    * @return the position of the column in the visible alignment
 287    */
 288   public int findColumnPosition(int hiddenColumn)
 289   {
 290     try
 291     {
 292       LOCK.readLock().lock();
 293       int result = hiddenColumn;
 294       int[] region = null;
 295       if (hiddenColumns != null)
 296       {
 297         Iterator<int[]> it = new RegionsIterator(0,
 298                 hiddenColumn, hiddenColumns, cursor);
 299         while (it.hasNext())
 300         {
 301           region = it.next();
 302           if (hiddenColumn > region[1])
 303           {
 304             result -= region[1] + 1 - region[0];
 305           }
 306         }
 307
 308         if (region != null && hiddenColumn >= region[0]
 309                 && hiddenColumn <= region[1])
 310         {
 311           // Here the hidden column is within a region, so
 312           // we want to return the position of region[0]-1, adjusted for any
 313           // earlier hidden columns.
 314           // Calculate the difference between the actual hidden col position
 315           // and region[0]-1, and then subtract from result to convert result
 316           // from the adjusted hiddenColumn value to the adjusted region[0]-1
 317           // value.
 318
 319           // However, if the region begins at 0 we cannot return region[0]-1
 320           // just return 0
 321           if (region[0] == 0)
 322           {
 323             return 0;
 324           }
 325           else
 326           {
 327             return result - (hiddenColumn - region[0] + 1);
 328           }
 329         }
 330       }
 331       return result; // return the shifted position after removing hidden
 332                      // columns.
 333     } finally
 334     {
 335       LOCK.readLock().unlock();
 336     }
 337   }
 338
 339   /**
 340    * Find the visible column which is a given visible number of columns to the
 341    * left of another visible column. i.e. for a startColumn x, the column which
 342    * is distance 1 away will be column x-1.
 343    *
 344    * @param visibleDistance
 345    *          the number of visible columns to offset by
 346    * @param startColumn
 347    *          the column to start from
 348    * @return the position of the column in the visible alignment
 349    */
 350   public int subtractVisibleColumns(int visibleDistance, int startColumn)
 351   {
 352     try
 353     {
 354       LOCK.readLock().lock();
 355       int distance = visibleDistance;
 356
 357       // in case startColumn is in a hidden region, move it to the left
 358       int start = adjustForHiddenColumns(findColumnPosition(startColumn));
 359
 360       Iterator<int[]> it = new ReverseRegionsIterator(0, start,
 361               hiddenColumns);
 362
 363       while (it.hasNext() && (distance > 0))
 364       {
 365         int[] region = it.next();
 366
 367         if (start > region[1])
 368         {
 369           // subtract the gap to right of region from distance
 370           if (start - region[1] <= distance)
 371           {
 372             distance -= start - region[1];
 373             start = region[0] - 1;
 374           }
 375           else
 376           {
 377             start = start - distance;
 378             distance = 0;
 379           }
 380         }
 381       }
 382
 383       return start - distance;
 384
 385     } finally
 386     {
 387       LOCK.readLock().unlock();
 388     }
 389   }
 390
 391   /**
 392    * This method returns the rightmost limit of a region of an alignment with
 393    * hidden columns. In otherwords, the next hidden column.
 394    *
 395    * @param alPos
 396    *          the absolute (visible) alignmentPosition to find the next hidden
 397    *          column for
 398    */
 399   public int getHiddenBoundaryRight(int alPos)
 400   {
 401     try
 402     {
 403       LOCK.readLock().lock();
 404       if (hiddenColumns != null)
 405       {
 406         int index = cursor.findRegionForColumn(alPos);
 407         if (index < hiddenColumns.size())
 408         {
 409           int[] region = hiddenColumns.get(index);
 410           if (alPos < region[0])
 411           {
 412             return region[0];
 413           }
 414           else if ((alPos <= region[1])
 415                   && (index + 1 < hiddenColumns.size()))
 416           {
 417             // alPos is within a hidden region, return the next one
 418             // if there is one
 419             region = hiddenColumns.get(index + 1);
 420             return region[0];
 421           }
 422         }
 423       }
 424       return alPos;
 425     } finally
 426     {
 427       LOCK.readLock().unlock();
 428     }
 429   }
 430
 431   /**
 432    * This method returns the leftmost limit of a region of an alignment with
 433    * hidden columns. In otherwords, the previous hidden column.
 434    *
 435    * @param alPos
 436    *          the absolute (visible) alignmentPosition to find the previous
 437    *          hidden column for
 438    */
 439   public int getHiddenBoundaryLeft(int alPos)
 440   {
 441     try
 442     {
 443       LOCK.readLock().lock();
 444
 445       if (hiddenColumns != null)
 446       {
 447         int index = cursor.findRegionForColumn(alPos);
 448
 449         if (index > 0)
 450         {
 451           int[] region = hiddenColumns.get(index - 1);
 452           return region[1];
 453         }
 454       }
 455       return alPos;
 456     } finally
 457     {
 458       LOCK.readLock().unlock();
 459     }
 460   }
 461
 462   /**
 463    * Adds the specified column range to the hidden columns collection
 464    *
 465    * @param start
 466    *          start of range to add (absolute position in alignment)
 467    * @param end
 468    *          end of range to add (absolute position in alignment)
 469    */
 470   public void hideColumns(int start, int end)
 471   {
 472     boolean wasAlreadyLocked = false;
 473     try
 474     {
 475       // check if the write lock was already locked by this thread,
 476       // as this method can be called internally in loops within HiddenColumns
 477       if (!LOCK.isWriteLockedByCurrentThread())
 478       {
 479         LOCK.writeLock().lock();
 480       }
 481       else
 482       {
 483         wasAlreadyLocked = true;
 484       }
 485
 486       if (hiddenColumns == null)
 487       {
 488         hiddenColumns = new ArrayList<>();
 489       }
 490
 491       /*
 492        * new range follows everything else; check first to avoid looping over whole hiddenColumns collection
 493        */
 494       if (hiddenColumns.isEmpty()
 495               || start > hiddenColumns.get(hiddenColumns.size() - 1)[1])
 496       {
 497         hiddenColumns.add(new int[] { start, end });
 498       }
 499       else
 500       {
 501         /*
 502          * traverse existing hidden ranges and insert / amend / append as
 503          * appropriate
 504          */
 505         boolean added = false;
 506         for (int i = 0; !added && i < hiddenColumns.size(); i++)
 507         {
 508           added = insertRangeAtRegion(i, start, end);
 509         } // for
 510       }
 511       if (!wasAlreadyLocked)
 512       {
 513         cursor.resetCursor(hiddenColumns);
 514       }
 515     } finally
 516     {
 517       if (!wasAlreadyLocked)
 518       {
 519         LOCK.writeLock().unlock();
 520       }
 521     }
 522   }
 523
 524   /**
 525    * Insert [start, range] at the region at index i in hiddenColumns, if
 526    * feasible
 527    *
 528    * @param i
 529    *          index to insert at
 530    * @param start
 531    *          start of range to insert
 532    * @param end
 533    *          end of range to insert
 534    * @return true if range was successfully inserted
 535    */
 536   private boolean insertRangeAtRegion(int i, int start, int end)
 537   {
 538     boolean added = false;
 539
 540     int[] region = hiddenColumns.get(i);
 541     if (end < region[0] - 1)
 542     {
 543       /*
 544        * insert discontiguous preceding range
 545        */
 546       hiddenColumns.add(i, new int[] { start, end });
 547       added = true;
 548     }
 549     else if (end <= region[1])
 550     {
 551       /*
 552        * new range overlaps existing, or is contiguous preceding it - adjust
 553        * start column
 554        */
 555       region[0] = Math.min(region[0], start);
 556       added = true;
 557     }
 558     else if (start <= region[1] + 1)
 559     {
 560       /*
 561        * new range overlaps existing, or is contiguous following it - adjust
 562        * start and end columns
 563        */
 564       region[0] = Math.min(region[0], start);
 565       region[1] = Math.max(region[1], end);
 566
 567       /*
 568        * also update or remove any subsequent ranges
 569        * that are overlapped
 570        */
 571       while (i < hiddenColumns.size() - 1)
 572       {
 573         int[] nextRegion = hiddenColumns.get(i + 1);
 574         if (nextRegion[0] > end + 1)
 575         {
 576           /*
 577            * gap to next hidden range - no more to update
 578            */
 579           break;
 580         }
 581         region[1] = Math.max(nextRegion[1], end);
 582         hiddenColumns.subList(i + 1, i + 2).clear();
 583       }
 584       added = true;
 585     }
 586     return added;
 587   }
 588
 589   /**
 590    * Answers if a column in the alignment is visible
 591    *
 592    * @param column
 593    *          absolute position of column in the alignment
 594    * @return true if column is visible
 595    */
 596   public boolean isVisible(int column)
 597   {
 598     try
 599     {
 600       LOCK.readLock().lock();
 601
 602       Iterator<int[]> it = new RegionsIterator(column, column,
 603               hiddenColumns, cursor);
 604       while (it.hasNext())
 605       {
 606         int[] region = it.next();
 607         if (column >= region[0] && column <= region[1])
 608         {
 609           return false;
 610         }
 611       }
 612
 613       return true;
 614     } finally
 615     {
 616       LOCK.readLock().unlock();
 617     }
 618   }
 619
 620   /**
 621    * Get the visible sections of a set of sequences
 622    *
 623    * @param start
 624    *          sequence position to start from
 625    * @param end
 626    *          sequence position to end at
 627    * @param seqs
 628    *          an array of sequences
 629    * @return an array of strings encoding the visible parts of each sequence
 630    */
 631   public String[] getVisibleSequenceStrings(int start, int end,
 632           SequenceI[] seqs)
 633   {
 634     try
 635     {
 636       LOCK.readLock().lock();
 637       int iSize = seqs.length;
 638       String[] selections = new String[iSize];
 639       if (hiddenColumns != null && hiddenColumns.size() > 0)
 640       {
 641         for (int i = 0; i < iSize; i++)
 642         {
 643           StringBuffer visibleSeq = new StringBuffer();
 644
 645           Iterator<int[]> blocks = new VisibleContigsIterator(start,
 646                   end + 1, hiddenColumns);
 647
 648           while (blocks.hasNext())
 649           {
 650             int[] block = blocks.next();
 651             if (blocks.hasNext())
 652             {
 653               visibleSeq
 654                       .append(seqs[i].getSequence(block[0], block[1] + 1));
 655             }
 656             else
 657             {
 658               visibleSeq
 659                       .append(seqs[i].getSequence(block[0], block[1]));
 660             }
 661           }
 662
 663           selections[i] = visibleSeq.toString();
 664         }
 665       }
 666       else
 667       {
 668         for (int i = 0; i < iSize; i++)
 669         {
 670           selections[i] = seqs[i].getSequenceAsString(start, end);
 671         }
 672       }
 673
 674       return selections;
 675     } finally
 676     {
 677       LOCK.readLock().unlock();
 678     }
 679   }
 680
 681   /**
 682    * Locate the first position visible for this sequence. If seq isn't visible
 683    * then return the position of the left side of the hidden boundary region.
 684    *
 685    * @param seq
 686    *          sequence to find position for
 687    * @return visible start position
 688    */
 689   public int locateVisibleStartOfSequence(SequenceI seq)
 690   {
 691     try
 692     {
 693       LOCK.readLock().lock();
 694       int start = 0;
 695
 696       if (hiddenColumns == null || hiddenColumns.size() == 0)
 697       {
 698         return seq.findIndex(seq.getStart()) - 1;
 699       }
 700
 701       // Simply walk along the sequence whilst watching for hidden column
 702       // boundaries
 703       Iterator<int[]> regions = hiddenColumns.iterator();
 704       int hideStart = seq.getLength();
 705       int hideEnd = -1;
 706       int visPrev = 0;
 707       int visNext = 0;
 708       boolean foundStart = false;
 709
 710       // step through the non-gapped positions of the sequence
 711       for (int i = seq.getStart(); i <= seq.getEnd() && (!foundStart); i++)
 712       {
 713         // get alignment position of this residue in the sequence
 714         int p = seq.findIndex(i) - 1;
 715
 716         // update hidden region start/end
 717         while (hideEnd < p && regions.hasNext())
 718         {
 719           int[] region = regions.next();
 720           visPrev = visNext;
 721           visNext += region[0] - visPrev;
 722           hideStart = region[0];
 723           hideEnd = region[1];
 724         }
 725         if (hideEnd < p)
 726         {
 727           hideStart = seq.getLength();
 728         }
 729         // update visible boundary for sequence
 730         if (p < hideStart)
 731         {
 732           start = p;
 733           foundStart = true;
 734         }
 735       }
 736
 737       if (foundStart)
 738       {
 739         return findColumnPosition(start);
 740       }
 741       // otherwise, sequence was completely hidden
 742       return visPrev;
 743     } finally
 744     {
 745       LOCK.readLock().unlock();
 746     }
 747   }
 748
 749   /**
 750    * delete any columns in alignmentAnnotation that are hidden (including
 751    * sequence associated annotation).
 752    *
 753    * @param alignmentAnnotation
 754    */
 755   public void makeVisibleAnnotation(AlignmentAnnotation alignmentAnnotation)
 756   {
 757     makeVisibleAnnotation(0, alignmentAnnotation.annotations.length,
 758             alignmentAnnotation);
 759   }
 760
 761   /**
 762    * delete any columns in alignmentAnnotation that are hidden (including
 763    * sequence associated annotation).
 764    *
 765    * @param start
 766    *          remove any annotation to the right of this column
 767    * @param end
 768    *          remove any annotation to the left of this column
 769    * @param alignmentAnnotation
 770    *          the annotation to operate on
 771    */
 772   public void makeVisibleAnnotation(int start, int end,
 773           AlignmentAnnotation alignmentAnnotation)
 774   {
 775     try
 776     {
 777       LOCK.readLock().lock();
 778
 779       int startFrom = start;
 780       int endAt = end;
 781
 782       if (alignmentAnnotation.annotations != null)
 783       {
 784         if (hiddenColumns != null && hiddenColumns.size() > 0)
 785         {
 786           removeHiddenAnnotation(startFrom, endAt, alignmentAnnotation);
 787         }
 788         else
 789         {
 790           alignmentAnnotation.restrict(startFrom, endAt);
 791         }
 792       }
 793     } finally
 794     {
 795       LOCK.readLock().unlock();
 796     }
 797   }
 798
 799   private void removeHiddenAnnotation(int start, int end,
 800           AlignmentAnnotation alignmentAnnotation)
 801   {
 802     // mangle the alignmentAnnotation annotation array
 803     ArrayList<Annotation[]> annels = new ArrayList<>();
 804     Annotation[] els = null;
 805
 806     int w = 0;
 807
 808     Iterator<int[]> blocks = new VisibleContigsIterator(start, end + 1,
 809             hiddenColumns);
 810
 811     int copylength;
 812     int annotationLength;
 813     while (blocks.hasNext())
 814     {
 815       int[] block = blocks.next();
 816       annotationLength = block[1] - block[0] + 1;
 817
 818       if (blocks.hasNext())
 819       {
 820         // copy just the visible segment of the annotation row
 821         copylength = annotationLength;
 822       }
 823       else
 824       {
 825         if (annotationLength + block[0] <= alignmentAnnotation.annotations.length)
 826         {
 827           // copy just the visible segment of the annotation row
 828           copylength = annotationLength;
 829         }
 830         else
 831         {
 832           // copy to the end of the annotation row
 833           copylength = alignmentAnnotation.annotations.length - block[0];
 834         }
 835       }
 836
 837       els = new Annotation[annotationLength];
 838       annels.add(els);
 839       System.arraycopy(alignmentAnnotation.annotations, block[0], els, 0,
 840               copylength);
 841       w += annotationLength;
 842     }
 843
 844     if (w != 0)
 845     {
 846       alignmentAnnotation.annotations = new Annotation[w];
 847
 848       w = 0;
 849       for (Annotation[] chnk : annels)
 850       {
 851         System.arraycopy(chnk, 0, alignmentAnnotation.annotations, w,
 852                 chnk.length);
 853         w += chnk.length;
 854       }
 855     }
 856   }
 857
 858   /**
 859    *
 860    * @return true if there are columns hidden
 861    */
 862   public boolean hasHiddenColumns()
 863   {
 864     try
 865     {
 866       LOCK.readLock().lock();
 867       return hiddenColumns != null && hiddenColumns.size() > 0;
 868     } finally
 869     {
 870       LOCK.readLock().unlock();
 871     }
 872   }
 873
 874   /**
 875    *
 876    * @return true if there are more than one set of columns hidden
 877    */
 878   public boolean hasManyHiddenColumns()
 879   {
 880     try
 881     {
 882       LOCK.readLock().lock();
 883       return hiddenColumns != null && hiddenColumns.size() > 1;
 884     } finally
 885     {
 886       LOCK.readLock().unlock();
 887     }
 888   }
 889
 890   /**
 891    * mark the columns corresponding to gap characters as hidden in the column
 892    * selection
 893    *
 894    * @param sr
 895    */
 896   public void hideInsertionsFor(SequenceI sr)
 897   {
 898     try
 899     {
 900       LOCK.writeLock().lock();
 901       List<int[]> inserts = sr.getInsertions();
 902       for (int[] r : inserts)
 903       {
 904         hideColumns(r[0], r[1]);
 905       }
 906       cursor.resetCursor(hiddenColumns);
 907     } finally
 908     {
 909       LOCK.writeLock().unlock();
 910     }
 911   }
 912
 913   /**
 914    * Unhides, and adds to the selection list, all hidden columns
 915    */
 916   public void revealAllHiddenColumns(ColumnSelection sel)
 917   {
 918     try
 919     {
 920       LOCK.writeLock().lock();
 921       if (hiddenColumns != null)
 922       {
 923         Iterator<int[]> it = hiddenColumns.iterator();
 924         while (it.hasNext())
 925         {
 926           int[] region = it.next();
 927           for (int j = region[0]; j < region[1] + 1; j++)
 928           {
 929             sel.addElement(j);
 930           }
 931         }
 932         hiddenColumns = null;
 933         cursor.resetCursor(hiddenColumns);
 934       }
 935     } finally
 936     {
 937       LOCK.writeLock().unlock();
 938     }
 939   }
 940
 941   /**
 942    * Reveals, and marks as selected, the hidden column range with the given
 943    * start column
 944    *
 945    * @param start
 946    */
 947   public void revealHiddenColumns(int start, ColumnSelection sel)
 948   {
 949     try
 950     {
 951       LOCK.writeLock().lock();
 952       Iterator<int[]> it = new RegionsIterator(start, start, hiddenColumns,
 953               cursor);
 954       while (it.hasNext())
 955       {
 956         int[] region = it.next();
 957         if (start == region[0])
 958         {
 959           for (int j = region[0]; j < region[1] + 1; j++)
 960           {
 961             sel.addElement(j);
 962           }
 963           it.remove();
 964           break;
 965         }
 966         else if (start < region[0])
 967         {
 968           break; // passed all possible matching regions
 969         }
 970       }
 971
 972       if (hiddenColumns.size() == 0)
 973       {
 974         hiddenColumns = null;
 975       }
 976       cursor.resetCursor(hiddenColumns);
 977     } finally
 978     {
 979       LOCK.writeLock().unlock();
 980     }
 981   }
 982
 983   /**
 984    * Add gaps into the sequences aligned to profileseq under the given
 985    * AlignmentView
 986    *
 987    * @param profileseq
 988    * @param al
 989    *          - alignment to have gaps inserted into it
 990    * @param input
 991    *          - alignment view where sequence corresponding to profileseq is
 992    *          first entry
 993    * @return new HiddenColumns for new alignment view, with insertions into
 994    *         profileseq marked as hidden.
 995    */
 996   public static HiddenColumns propagateInsertions(SequenceI profileseq,
 997           AlignmentI al, AlignmentView input)
 998   {
 999     int profsqpos = 0;
1000
1001     char gc = al.getGapCharacter();
1002     Object[] alandhidden = input.getAlignmentAndHiddenColumns(gc);
1003     HiddenColumns nview = (HiddenColumns) alandhidden[1];
1004     SequenceI origseq = ((SequenceI[]) alandhidden[0])[profsqpos];
1005     nview.propagateInsertions(profileseq, al, origseq);
1006     return nview;
1007   }
1008
1009   /**
1010    *
1011    * @param profileseq
1012    *          - sequence in al which corresponds to origseq
1013    * @param al
1014    *          - alignment which is to have gaps inserted into it
1015    * @param origseq
1016    *          - sequence corresponding to profileseq which defines gap map for
1017    *          modifying al
1018    */
1019   private void propagateInsertions(SequenceI profileseq, AlignmentI al,
1020           SequenceI origseq)
1021   {
1022     try
1023     {
1024       LOCK.writeLock().lock();
1025
1026       char gc = al.getGapCharacter();
1027
1028       // take the set of hidden columns, and the set of gaps in origseq,
1029       // and remove all the hidden gaps from hiddenColumns
1030
1031       // first get the gaps as a Bitset
1032       BitSet gaps = origseq.gapBitset();
1033
1034       // now calculate hidden ^ not(gap)
1035       BitSet hidden = new BitSet();
1036       markHiddenRegions(hidden);
1037       hidden.andNot(gaps);
1038       hiddenColumns = null;
1039       this.hideMarkedBits(hidden);
1040
1041       // for each sequence in the alignment, except the profile sequence,
1042       // insert gaps corresponding to each hidden region
1043       // but where each hidden column region is shifted backwards by the number
1044       // of
1045       // preceding visible gaps
1046       // update hidden columns at the same time
1047       Iterator<int[]> regions = hiddenColumns.iterator();
1048       ArrayList<int[]> newhidden = new ArrayList<>();
1049
1050       int numGapsBefore = 0;
1051       int gapPosition = 0;
1052       while (regions.hasNext())
1053       {
1054         // get region coordinates accounting for gaps
1055         // we can rely on gaps not being *in* hidden regions because we already
1056         // removed those
1057         int[] region = regions.next();
1058         while (gapPosition < region[0])
1059         {
1060           gapPosition++;
1061           if (gaps.get(gapPosition))
1062           {
1063             numGapsBefore++;
1064           }
1065         }
1066
1067         int left = region[0] - numGapsBefore;
1068         int right = region[1] - numGapsBefore;
1069         newhidden.add(new int[] { left, right });
1070
1071         // make a string with number of gaps = length of hidden region
1072         StringBuffer sb = new StringBuffer();
1073         for (int s = 0; s < right - left + 1; s++)
1074         {
1075           sb.append(gc);
1076         }
1077         padGaps(sb, left, profileseq, al);
1078
1079       }
1080       hiddenColumns = newhidden;
1081       cursor.resetCursor(hiddenColumns);
1082     } finally
1083     {
1084       LOCK.writeLock().unlock();
1085     }
1086   }
1087
1088   /**
1089    * Pad gaps in all sequences in alignment except profileseq
1090    *
1091    * @param sb
1092    *          gap string to insert
1093    * @param left
1094    *          position to insert at
1095    * @param profileseq
1096    *          sequence not to pad
1097    * @param al
1098    *          alignment to pad sequences in
1099    */
1100   private void padGaps(StringBuffer sb, int pos, SequenceI profileseq,
1101           AlignmentI al)
1102   {
1103     // loop over the sequences and pad with gaps where required
1104     for (int s = 0, ns = al.getHeight(); s < ns; s++)
1105     {
1106       SequenceI sqobj = al.getSequenceAt(s);
1107       if (sqobj != profileseq)
1108       {
1109         String sq = al.getSequenceAt(s).getSequenceAsString();
1110         if (sq.length() <= pos)
1111         {
1112           // pad sequence
1113           int diff = pos - sq.length() - 1;
1114           if (diff > 0)
1115           {
1116             // pad gaps
1117             sq = sq + sb;
1118             while ((diff = pos - sq.length() - 1) > 0)
1119             {
1120               if (diff >= sb.length())
1121               {
1122                 sq += sb.toString();
1123               }
1124               else
1125               {
1126                 char[] buf = new char[diff];
1127                 sb.getChars(0, diff, buf, 0);
1128                 sq += buf.toString();
1129               }
1130             }
1131           }
1132           sq += sb.toString();
1133         }
1134         else
1135         {
1136           al.getSequenceAt(s).setSequence(
1137                   sq.substring(0, pos) + sb.toString() + sq.substring(pos));
1138         }
1139       }
1140     }
1141   }
1142
1143   /**
1144    * Returns a hashCode built from hidden column ranges
1145    */
1146   @Override
1147   public int hashCode()
1148   {
1149     try
1150     {
1151       LOCK.readLock().lock();
1152       int hashCode = 1;
1153       Iterator<int[]> it = hiddenColumns.iterator();
1154       while (it.hasNext())
1155       {
1156         int[] hidden = it.next();
1157         hashCode = HASH_MULTIPLIER * hashCode + hidden[0];
1158         hashCode = HASH_MULTIPLIER * hashCode + hidden[1];
1159       }
1160       return hashCode;
1161     } finally
1162     {
1163       LOCK.readLock().unlock();
1164     }
1165   }
1166
1167   /**
1168    * Hide columns corresponding to the marked bits
1169    *
1170    * @param inserts
1171    *          - columns map to bits starting from zero
1172    */
1173   public void hideMarkedBits(BitSet inserts)
1174   {
1175     try
1176     {
1177       LOCK.writeLock().lock();
1178       for (int firstSet = inserts
1179               .nextSetBit(0), lastSet = 0; firstSet >= 0; firstSet = inserts
1180                       .nextSetBit(lastSet))
1181       {
1182         lastSet = inserts.nextClearBit(firstSet);
1183         hideColumns(firstSet, lastSet - 1);
1184       }
1185       cursor.resetCursor(hiddenColumns);
1186     } finally
1187     {
1188       LOCK.writeLock().unlock();
1189     }
1190   }
1191
1192   /**
1193    *
1194    * @param inserts
1195    *          BitSet where hidden columns will be marked
1196    */
1197   public void markHiddenRegions(BitSet inserts)
1198   {
1199     try
1200     {
1201       LOCK.readLock().lock();
1202       if (hiddenColumns == null)
1203       {
1204         return;
1205       }
1206       Iterator<int[]> it = hiddenColumns.iterator();
1207       while (it.hasNext())
1208       {
1209         int[] range = it.next();
1210         inserts.set(range[0], range[1] + 1);
1211       }
1212     } finally
1213     {
1214       LOCK.readLock().unlock();
1215     }
1216   }
1217
1218   /**
1219    * Calculate the visible start and end index of an alignment.
1220    *
1221    * @param width
1222    *          full alignment width
1223    * @return integer array where: int[0] = startIndex, and int[1] = endIndex
1224    */
1225   public int[] getVisibleStartAndEndIndex(int width)
1226   {
1227     try
1228     {
1229       LOCK.readLock().lock();
1230       int[] alignmentStartEnd = new int[] { 0, width - 1 };
1231       int startPos = alignmentStartEnd[0];
1232       int endPos = alignmentStartEnd[1];
1233
1234       int[] lowestRange = new int[] { -1, -1 };
1235       int[] higestRange = new int[] { -1, -1 };
1236
1237       if (hiddenColumns == null)
1238       {
1239         return new int[] { startPos, endPos };
1240       }
1241
1242       Iterator<int[]> it = hiddenColumns.iterator();
1243       while (it.hasNext())
1244       {
1245         int[] range = it.next();
1246         lowestRange = (range[0] <= startPos) ? range : lowestRange;
1247         higestRange = (range[1] >= endPos) ? range : higestRange;
1248       }
1249
1250       if (lowestRange[0] == -1 && lowestRange[1] == -1)
1251       {
1252         startPos = alignmentStartEnd[0];
1253       }
1254       else
1255       {
1256         startPos = lowestRange[1] + 1;
1257       }
1258
1259       if (higestRange[0] == -1 && higestRange[1] == -1)
1260       {
1261         endPos = alignmentStartEnd[1];
1262       }
1263       else
1264       {
1265         endPos = higestRange[0] - 1;
1266       }
1267       return new int[] { startPos, endPos };
1268     } finally
1269     {
1270       LOCK.readLock().unlock();
1271     }
1272   }
1273
1274   /**
1275    * Finds the hidden region (if any) which starts or ends at res
1276    *
1277    * @param res
1278    *          visible residue position, unadjusted for hidden columns
1279    * @return region as [start,end] or null if no matching region is found
1280    */
1281   public int[] getRegionWithEdgeAtRes(int res)
1282   {
1283     try
1284     {
1285       LOCK.readLock().lock();
1286       int adjres = adjustForHiddenColumns(res);
1287
1288       int[] reveal = null;
1289
1290       if (hiddenColumns != null)
1291       {
1292         int regionindex = cursor.findRegionForColumn(adjres - 1);
1293         if (hiddenColumns.get(regionindex)[1] == adjres - 1)
1294         {
1295           reveal = hiddenColumns.get(regionindex);
1296         }
1297         else
1298         {
1299           regionindex = cursor.findRegionForColumn(adjres + 1);
1300           if (hiddenColumns.get(regionindex)[0] == adjres + 1)
1301           {
1302             reveal = hiddenColumns.get(regionindex);
1303           }
1304         }
1305       }
1306       return reveal;
1307
1308     } finally
1309     {
1310       LOCK.readLock().unlock();
1311     }
1312   }
1313
1314   /**
1315    * Return an iterator over the hidden regions
1316    */
1317   public Iterator<int[]> iterator()
1318   {
1319     try
1320     {
1321       LOCK.readLock().lock();
1322       return new BoundedHiddenColsIterator(hiddenColumns);
1323     } finally
1324     {
1325       LOCK.readLock().unlock();
1326     }
1327   }
1328
1329   /**
1330    * Return a bounded iterator over the hidden regions
1331    *
1332    * @param start
1333    *          position to start from (inclusive, absolute column position)
1334    * @param end
1335    *          position to end at (inclusive, absolute column position)
1336    * @return
1337    */
1338   public Iterator<int[]> getBoundedIterator(int start, int end)
1339   {
1340     try
1341     {
1342       LOCK.readLock().lock();
1343       return new BoundedHiddenColsIterator(start, end, hiddenColumns);
1344     } finally
1345     {
1346       LOCK.readLock().unlock();
1347     }
1348   }
1349
1350   /**
1351    * Return a bounded iterator over the *visible* start positions of hidden
1352    * regions
1353    *
1354    * @param start
1355    *          position to start from (inclusive, visible column position)
1356    * @param end
1357    *          position to end at (inclusive, visible column position)
1358    */
1359   public Iterator<Integer> getBoundedStartIterator(int start, int end)
1360   {
1361     try
1362     {
1363       LOCK.readLock().lock();
1364       return new BoundedStartRegionIterator(start, end, hiddenColumns);
1365     } finally
1366     {
1367       LOCK.readLock().unlock();
1368     }
1369   }
1370
1371   /**
1372    * Return an iterator over visible *columns* (not regions) between the given
1373    * start and end boundaries
1374    *
1375    * @param start
1376    *          first column (inclusive)
1377    * @param end
1378    *          last column (inclusive)
1379    */
1380   public Iterator<Integer> getVisibleColsIterator(int start, int end)
1381   {
1382     try
1383     {
1384       LOCK.readLock().lock();
1385       return new VisibleColsIterator(start, end, hiddenColumns);
1386     } finally
1387     {
1388       LOCK.readLock().unlock();
1389     }
1390   }
1391
1392   /**
1393    * return an iterator over visible segments between the given start and end
1394    * boundaries
1395    *
1396    * @param start
1397    *          (first column inclusive from 0)
1398    * @param end
1399    *          (last column - not inclusive)
1400    */
1401   public Iterator<int[]> getVisContigsIterator(int start, int end)
1402   {
1403     try
1404     {
1405       LOCK.readLock().lock();
1406       return new VisibleContigsIterator(start, end, hiddenColumns);
1407     } finally
1408     {
1409       LOCK.readLock().unlock();
1410     }
1411   }
1412
1413   /**
1414    * return an iterator over visible segments between the given start and end
1415    * boundaries
1416    *
1417    * @param start
1418    *          (first column - inclusive from 0)
1419    * @param end
1420    *          (last column - inclusive)
1421    * @param useVisibleCoords
1422    *          if true, start and end are visible column positions, not absolute
1423    *          positions
1424    */
1425   public Iterator<int[]> getVisibleBlocksIterator(int start, int end,
1426           boolean useVisibleCoords)
1427   {
1428     if (useVisibleCoords)
1429     {
1430       // TODO
1431       // we should really just convert start and end here with
1432       // adjustForHiddenColumns
1433       // and then create a VisibleContigsIterator
1434       // but without a cursor this will be horribly slow in some situations
1435       // ... so until then...
1436       return new VisibleBlocksVisBoundsIterator(start, end, true);
1437     }
1438     else
1439     {
1440       try
1441       {
1442         LOCK.readLock().lock();
1443         return new VisibleContigsIterator(start, end + 1, hiddenColumns);
1444       } finally
1445     {
1446         LOCK.readLock().unlock();
1447       }
1448     }
1449   }
1450
1451   /**
1452    * An iterator which iterates over visible regions in a range. The range is
1453    * specified in terms of visible column positions. Provides a special
1454    * "endsAtHidden" indicator to allow callers to determine if the final visible
1455    * column is adjacent to a hidden region.
1456    */
1457   public class VisibleBlocksVisBoundsIterator implements Iterator<int[]>
1458   {
1459     private List<int[]> vcontigs = new ArrayList<>();
1460
1461     private int currentPosition = 0;
1462
1463     private boolean endsAtHidden = false;
1464
1465     /**
1466      * Constructor for iterator over visible regions in a range.
1467      *
1468      * @param start
1469      *          start position in terms of visible column position
1470      * @param end
1471      *          end position in terms of visible column position
1472      * @param usecopy
1473      *          whether to use a local copy of hidden columns
1474      */
1475     VisibleBlocksVisBoundsIterator(int start, int end, boolean usecopy)
1476     {
1477       /* actually this implementation always uses a local copy but this may change in future */
1478       try
1479       {
1480         if (usecopy)
1481         {
1482           LOCK.readLock().lock();
1483         }
1484
1485         if (hiddenColumns != null && hiddenColumns.size() > 0)
1486         {
1487           int blockStart = start;
1488           int blockEnd = end;
1489           int hiddenSoFar = 0;
1490           int visSoFar = 0;
1491
1492           // iterate until a region begins within (start,end]
1493           int i = 0;
1494           while ((i < hiddenColumns.size())
1495                   && (hiddenColumns.get(i)[0] <= blockStart + hiddenSoFar))
1496           {
1497             hiddenSoFar += hiddenColumns.get(i)[1] - hiddenColumns.get(i)[0]
1498                     + 1;
1499             i++;
1500           }
1501
1502           blockStart += hiddenSoFar; // convert start to absolute position
1503           blockEnd += hiddenSoFar; // convert end to absolute position
1504
1505           // iterate from start to end, adding each visible region. Positions
1506           // are
1507           // absolute, and all hidden regions which overlap [start,end] are
1508           // used.
1509           while (i < hiddenColumns.size()
1510                   && (hiddenColumns.get(i)[0] <= blockEnd))
1511           {
1512             int[] region = hiddenColumns.get(i);
1513
1514             // end position of this visible region is either just before the
1515             // start of the next hidden region, or the absolute position of
1516             // 'end', whichever is lowest
1517             blockEnd = Math.min(blockEnd, region[0] - 1);
1518
1519             vcontigs.add(new int[] { blockStart, blockEnd });
1520
1521             visSoFar += blockEnd - blockStart + 1;
1522
1523             // next visible region starts after this hidden region
1524             blockStart = region[1] + 1;
1525
1526             hiddenSoFar += region[1] - region[0] + 1;
1527
1528             // reset blockEnd to absolute position of 'end', assuming we've now
1529             // passed all hidden regions before end
1530             blockEnd = end + hiddenSoFar;
1531
1532             i++;
1533           }
1534           if (visSoFar < end - start + 1)
1535           {
1536             // the number of visible columns we've accounted for is less than
1537             // the number specified by end-start; work out the end position of
1538             // the last visible region
1539             blockEnd = blockStart + end - start - visSoFar;
1540             vcontigs.add(new int[] { blockStart, blockEnd });
1541
1542             // if the last visible region ends at the next hidden region, set
1543             // endsAtHidden=true
1544             if (i < hiddenColumns.size()
1545                     && hiddenColumns.get(i)[0] - 1 == blockEnd)
1546             {
1547               endsAtHidden = true;
1548             }
1549           }
1550         }
1551         else
1552         {
1553           // there are no hidden columns, return a single visible contig
1554           vcontigs.add(new int[] { start, end });
1555           endsAtHidden = false;
1556         }
1557       } finally
1558       {
1559         if (usecopy)
1560         {
1561           LOCK.readLock().unlock();
1562         }
1563       }
1564     }
1565
1566     @Override
1567     public boolean hasNext()
1568     {
1569       return (currentPosition < vcontigs.size());
1570     }
1571
1572     @Override
1573     public int[] next()
1574     {
1575       int[] result = vcontigs.get(currentPosition);
1576       currentPosition++;
1577       return result;
1578     }
1579
1580     public boolean endsAtHidden()
1581     {
1582       return endsAtHidden;
1583     }
1584   }
1585 }