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