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