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