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