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