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 adjustForHiddenColumns(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    * left-most visible column will always be returned.
 761    *
 762    * @param hiddenColumn
 763    *          the column index in the full alignment including hidden columns
 764    * @return the position of the column in the visible alignment
 765    */
 766   public int findColumnPosition(int hiddenColumn)
 767   {
 768     try
 769     {
 770       LOCK.readLock().lock();
 771       int result = hiddenColumn;
 772
 773       if (hiddenColumns != null)
 774       {
 775         HiddenCursorPosition cursorPos = cursor
 776                 .findRegionForColumn(hiddenColumn);
 777         int index = cursorPos.getRegionIndex();
 778         int hiddenBeforeCol = cursorPos.getHiddenSoFar();
 779
 780         // just subtract hidden cols count - this works fine if column is
 781         // visible
 782         result = hiddenColumn - hiddenBeforeCol;
 783
 784         // now check in case column is hidden - it will be in the returned
 785         // hidden region
 786         if (index < hiddenColumns.size())
 787         {
 788           int[] region = hiddenColumns.get(index);
 789           if (hiddenColumn >= region[0] && hiddenColumn <= region[1])
 790           {
 791             // actually col is hidden, return region[0]-1
 792             // unless region[0]==0 in which case return 0
 793             if (region[0] == 0)
 794             {
 795               result = 0;
 796             }
 797             else
 798             {
 799               result = region[0] - 1 - hiddenBeforeCol;
 800             }
 801           }
 802         }
 803       }
 804
 805       return result; // return the shifted position after removing hidden
 806                      // columns.
 807     } finally
 808     {
 809       LOCK.readLock().unlock();
 810     }
 811   }
 812
 813   /**
 814    * Find the visible column which is a given visible number of columns to the
 815    * left of another visible column. i.e. for a startColumn x, the column which
 816    * is distance 1 away will be column x-1.
 817    *
 818    * @param visibleDistance
 819    *          the number of visible columns to offset by
 820    * @param startColumn
 821    *          the column to start from
 822    * @return the position of the column in the visible alignment
 823    */
 824   public int subtractVisibleColumns(int visibleDistance, int startColumn)
 825   {
 826     try
 827     {
 828       LOCK.readLock().lock();
 829       int distance = visibleDistance;
 830
 831       // in case startColumn is in a hidden region, move it to the left
 832       int start = adjustForHiddenColumns(findColumnPosition(startColumn));
 833
 834       Iterator<int[]> it = new ReverseRegionsIterator(0, start,
 835               hiddenColumns);
 836
 837       while (it.hasNext() && (distance > 0))
 838       {
 839         int[] region = it.next();
 840
 841         if (start > region[1])
 842         {
 843           // subtract the gap to right of region from distance
 844           if (start - region[1] <= distance)
 845           {
 846             distance -= start - region[1];
 847             start = region[0] - 1;
 848           }
 849           else
 850           {
 851             start = start - distance;
 852             distance = 0;
 853           }
 854         }
 855       }
 856       return start - distance;
 857
 858     } finally
 859     {
 860       LOCK.readLock().unlock();
 861     }
 862   }
 863
 864   /**
 865    * This method returns the rightmost limit of a region of an alignment with
 866    * hidden columns. In otherwords, the next hidden column.
 867    *
 868    * @param alPos
 869    *          the absolute (visible) alignmentPosition to find the next hidden
 870    *          column for
 871    * @return the index of the next hidden column, or alPos if there is no next
 872    *         hidden column
 873    */
 874   public int getHiddenBoundaryRight(int alPos)
 875   {
 876     try
 877     {
 878       LOCK.readLock().lock();
 879       if (hiddenColumns != null)
 880       {
 881         int index = cursor.findRegionForColumn(alPos).getRegionIndex();
 882         if (index < hiddenColumns.size())
 883         {
 884           int[] region = hiddenColumns.get(index);
 885           if (alPos < region[0])
 886           {
 887             return region[0];
 888           }
 889           else if ((alPos <= region[1])
 890                   && (index + 1 < hiddenColumns.size()))
 891           {
 892             // alPos is within a hidden region, return the next one
 893             // if there is one
 894             region = hiddenColumns.get(index + 1);
 895             return region[0];
 896           }
 897         }
 898       }
 899       return alPos;
 900     } finally
 901     {
 902       LOCK.readLock().unlock();
 903     }
 904   }
 905
 906   /**
 907    * This method returns the leftmost limit of a region of an alignment with
 908    * hidden columns. In otherwords, the previous hidden column.
 909    *
 910    * @param alPos
 911    *          the absolute (visible) alignmentPosition to find the previous
 912    *          hidden column for
 913    */
 914   public int getHiddenBoundaryLeft(int alPos)
 915   {
 916     try
 917     {
 918       LOCK.readLock().lock();
 919
 920       if (hiddenColumns != null)
 921       {
 922         int index = cursor.findRegionForColumn(alPos).getRegionIndex();
 923
 924         if (index > 0)
 925         {
 926           int[] region = hiddenColumns.get(index - 1);
 927           return region[1];
 928         }
 929       }
 930       return alPos;
 931     } finally
 932     {
 933       LOCK.readLock().unlock();
 934     }
 935   }
 936
 937
 938   /**
 939    * Answers if a column in the alignment is visible
 940    *
 941    * @param column
 942    *          absolute position of column in the alignment
 943    * @return true if column is visible
 944    */
 945   public boolean isVisible(int column)
 946   {
 947     try
 948     {
 949       LOCK.readLock().lock();
 950
 951       int regionindex = cursor.findRegionForColumn(column).getRegionIndex();
 952       if (regionindex > -1 && regionindex < hiddenColumns.size())
 953       {
 954         int[] region = hiddenColumns.get(regionindex);
 955         // already know that column <= region[1] as cursor returns containing
 956         // region or region to right
 957         if (column >= region[0])
 958         {
 959           return false;
 960         }
 961       }
 962       return true;
 963
 964     } finally
 965     {
 966       LOCK.readLock().unlock();
 967     }
 968   }
 969
 970   /**
 971    * Get the visible sections of a set of sequences
 972    *
 973    * @param start
 974    *          sequence position to start from
 975    * @param end
 976    *          sequence position to end at
 977    * @param seqs
 978    *          an array of sequences
 979    * @return an array of strings encoding the visible parts of each sequence
 980    */
 981   public String[] getVisibleSequenceStrings(int start, int end,
 982           SequenceI[] seqs)
 983   {
 984     try
 985     {
 986       LOCK.readLock().lock();
 987       int iSize = seqs.length;
 988       String[] selections = new String[iSize];
 989       if (hiddenColumns != null && hiddenColumns.size() > 0)
 990       {
 991         for (int i = 0; i < iSize; i++)
 992         {
 993           StringBuffer visibleSeq = new StringBuffer();
 994
 995           Iterator<int[]> blocks = new VisibleContigsIterator(start,
 996                   end + 1, hiddenColumns);
 997
 998           while (blocks.hasNext())
 999           {
1000             int[] block = blocks.next();
1001             if (blocks.hasNext())
1002             {
1003               visibleSeq
1004                       .append(seqs[i].getSequence(block[0], block[1] + 1));
1005             }
1006             else
1007             {
1008               visibleSeq
1009                       .append(seqs[i].getSequence(block[0], block[1]));
1010             }
1011           }
1012
1013           selections[i] = visibleSeq.toString();
1014         }
1015       }
1016       else
1017       {
1018         for (int i = 0; i < iSize; i++)
1019         {
1020           selections[i] = seqs[i].getSequenceAsString(start, end);
1021         }
1022       }
1023
1024       return selections;
1025     } finally
1026     {
1027       LOCK.readLock().unlock();
1028     }
1029   }
1030
1031   /**
1032    * Locate the first position visible for this sequence. If seq isn't visible
1033    * then return the position of the left side of the hidden boundary region.
1034    *
1035    * @param seq
1036    *          sequence to find position for
1037    * @return visible start position
1038    */
1039   public int locateVisibleStartOfSequence(SequenceI seq)
1040   {
1041     try
1042     {
1043       LOCK.readLock().lock();
1044       int start = 0;
1045
1046       if (hiddenColumns == null || hiddenColumns.size() == 0)
1047       {
1048         return seq.findIndex(seq.getStart()) - 1;
1049       }
1050
1051       // Simply walk along the sequence whilst watching for hidden column
1052       // boundaries
1053       Iterator<int[]> regions = hiddenColumns.iterator();
1054       int hideStart = seq.getLength();
1055       int hideEnd = -1;
1056       int visPrev = 0;
1057       int visNext = 0;
1058       boolean foundStart = false;
1059
1060       // step through the non-gapped positions of the sequence
1061       for (int i = seq.getStart(); i <= seq.getEnd() && (!foundStart); i++)
1062       {
1063         // get alignment position of this residue in the sequence
1064         int p = seq.findIndex(i) - 1;
1065
1066         // update hidden region start/end
1067         while (hideEnd < p && regions.hasNext())
1068         {
1069           int[] region = regions.next();
1070           visPrev = visNext;
1071           visNext += region[0] - visPrev;
1072           hideStart = region[0];
1073           hideEnd = region[1];
1074         }
1075         if (hideEnd < p)
1076         {
1077           hideStart = seq.getLength();
1078         }
1079         // update visible boundary for sequence
1080         if (p < hideStart)
1081         {
1082           start = p;
1083           foundStart = true;
1084         }
1085       }
1086
1087       if (foundStart)
1088       {
1089         return findColumnPosition(start);
1090       }
1091       // otherwise, sequence was completely hidden
1092       return visPrev;
1093     } finally
1094     {
1095       LOCK.readLock().unlock();
1096     }
1097   }
1098
1099   /**
1100    * delete any columns in alignmentAnnotation that are hidden (including
1101    * sequence associated annotation).
1102    *
1103    * @param alignmentAnnotation
1104    */
1105   public void makeVisibleAnnotation(AlignmentAnnotation alignmentAnnotation)
1106   {
1107     if (alignmentAnnotation != null
1108             && alignmentAnnotation.annotations != null)
1109     {
1110       makeVisibleAnnotation(0, alignmentAnnotation.annotations.length,
1111             alignmentAnnotation);
1112     }
1113   }
1114
1115   /**
1116    * delete any columns in alignmentAnnotation that are hidden (including
1117    * sequence associated annotation).
1118    *
1119    * @param start
1120    *          remove any annotation to the right of this column
1121    * @param end
1122    *          remove any annotation to the left of this column
1123    * @param alignmentAnnotation
1124    *          the annotation to operate on
1125    */
1126   public void makeVisibleAnnotation(int start, int end,
1127           AlignmentAnnotation alignmentAnnotation)
1128   {
1129     try
1130     {
1131       LOCK.readLock().lock();
1132
1133       int startFrom = start;
1134       int endAt = end;
1135
1136       if (alignmentAnnotation != null
1137               && alignmentAnnotation.annotations != null)
1138       {
1139         if (hiddenColumns != null && hiddenColumns.size() > 0)
1140         {
1141           removeHiddenAnnotation(startFrom, endAt, alignmentAnnotation);
1142         }
1143         else
1144         {
1145           alignmentAnnotation.restrict(startFrom, endAt);
1146         }
1147       }
1148     } finally
1149     {
1150       LOCK.readLock().unlock();
1151     }
1152   }
1153
1154   private void removeHiddenAnnotation(int start, int end,
1155           AlignmentAnnotation alignmentAnnotation)
1156   {
1157     // mangle the alignmentAnnotation annotation array
1158     ArrayList<Annotation[]> annels = new ArrayList<>();
1159     Annotation[] els = null;
1160
1161     int w = 0;
1162
1163     Iterator<int[]> blocks = new VisibleContigsIterator(start, end + 1,
1164             hiddenColumns);
1165
1166     int copylength;
1167     int annotationLength;
1168     while (blocks.hasNext())
1169     {
1170       int[] block = blocks.next();
1171       annotationLength = block[1] - block[0] + 1;
1172
1173       if (blocks.hasNext())
1174       {
1175         // copy just the visible segment of the annotation row
1176         copylength = annotationLength;
1177       }
1178       else
1179       {
1180         if (annotationLength + block[0] <= alignmentAnnotation.annotations.length)
1181         {
1182           // copy just the visible segment of the annotation row
1183           copylength = annotationLength;
1184         }
1185         else
1186         {
1187           // copy to the end of the annotation row
1188           copylength = alignmentAnnotation.annotations.length - block[0];
1189         }
1190       }
1191
1192       els = new Annotation[annotationLength];
1193       annels.add(els);
1194       System.arraycopy(alignmentAnnotation.annotations, block[0], els, 0,
1195               copylength);
1196       w += annotationLength;
1197     }
1198
1199     if (w != 0)
1200     {
1201       alignmentAnnotation.annotations = new Annotation[w];
1202
1203       w = 0;
1204       for (Annotation[] chnk : annels)
1205       {
1206         System.arraycopy(chnk, 0, alignmentAnnotation.annotations, w,
1207                 chnk.length);
1208         w += chnk.length;
1209       }
1210     }
1211   }
1212
1213   /**
1214    *
1215    * @return true if there are columns hidden
1216    */
1217   public boolean hasHiddenColumns()
1218   {
1219     try
1220     {
1221       LOCK.readLock().lock();
1222
1223       // we don't use getSize()>0 here because it has to iterate over
1224       // the full hiddenColumns collection and so will be much slower
1225       return hiddenColumns != null && hiddenColumns.size() > 0;
1226     } finally
1227     {
1228       LOCK.readLock().unlock();
1229     }
1230   }
1231
1232   /**
1233    *
1234    * @return true if there is more than one hidden column region
1235    */
1236   public boolean hasMultiHiddenColumnRegions()
1237   {
1238     try
1239     {
1240       LOCK.readLock().lock();
1241       return hiddenColumns != null && hiddenColumns.size() > 1;
1242     } finally
1243     {
1244       LOCK.readLock().unlock();
1245     }
1246   }
1247
1248
1249   /**
1250    * Returns a hashCode built from hidden column ranges
1251    */
1252   @Override
1253   public int hashCode()
1254   {
1255     try
1256     {
1257       LOCK.readLock().lock();
1258       int hashCode = 1;
1259       Iterator<int[]> it = hiddenColumns.iterator();
1260       while (it.hasNext())
1261       {
1262         int[] hidden = it.next();
1263         hashCode = HASH_MULTIPLIER * hashCode + hidden[0];
1264         hashCode = HASH_MULTIPLIER * hashCode + hidden[1];
1265       }
1266       return hashCode;
1267     } finally
1268     {
1269       LOCK.readLock().unlock();
1270     }
1271   }
1272
1273   /**
1274    * Hide columns corresponding to the marked bits
1275    *
1276    * @param inserts
1277    *          - columns map to bits starting from zero
1278    */
1279   public void hideMarkedBits(BitSet inserts)
1280   {
1281     try
1282     {
1283       LOCK.writeLock().lock();
1284       for (int firstSet = inserts
1285               .nextSetBit(0), lastSet = 0; firstSet >= 0; firstSet = inserts
1286                       .nextSetBit(lastSet))
1287       {
1288         lastSet = inserts.nextClearBit(firstSet);
1289         hideColumns(firstSet, lastSet - 1);
1290       }
1291       cursor.resetCursor(hiddenColumns);
1292       numColumns = 0;
1293     } finally
1294     {
1295       LOCK.writeLock().unlock();
1296     }
1297   }
1298
1299   /**
1300    *
1301    * @param inserts
1302    *          BitSet where hidden columns will be marked
1303    */
1304   public void markHiddenRegions(BitSet inserts)
1305   {
1306     try
1307     {
1308       LOCK.readLock().lock();
1309       if (hiddenColumns == null)
1310       {
1311         return;
1312       }
1313       Iterator<int[]> it = hiddenColumns.iterator();
1314       while (it.hasNext())
1315       {
1316         int[] range = it.next();
1317         inserts.set(range[0], range[1] + 1);
1318       }
1319     } finally
1320     {
1321       LOCK.readLock().unlock();
1322     }
1323   }
1324
1325   /**
1326    * Calculate the visible start and end index of an alignment.
1327    *
1328    * @param width
1329    *          full alignment width
1330    * @return integer array where: int[0] = startIndex, and int[1] = endIndex
1331    */
1332   public int[] getVisibleStartAndEndIndex(int width)
1333   {
1334     try
1335     {
1336       LOCK.readLock().lock();
1337       int[] alignmentStartEnd = new int[] { 0, width - 1 };
1338       int startPos = alignmentStartEnd[0];
1339       int endPos = alignmentStartEnd[1];
1340
1341       int[] lowestRange = new int[] { -1, -1 };
1342       int[] higestRange = new int[] { -1, -1 };
1343
1344       if (hiddenColumns == null)
1345       {
1346         return new int[] { startPos, endPos };
1347       }
1348
1349       Iterator<int[]> it = hiddenColumns.iterator();
1350       while (it.hasNext())
1351       {
1352         int[] range = it.next();
1353         lowestRange = (range[0] <= startPos) ? range : lowestRange;
1354         higestRange = (range[1] >= endPos) ? range : higestRange;
1355       }
1356
1357       if (lowestRange[0] == -1) // includes (lowestRange[1] == -1)
1358       {
1359         startPos = alignmentStartEnd[0];
1360       }
1361       else
1362       {
1363         startPos = lowestRange[1] + 1;
1364       }
1365
1366       if (higestRange[0] == -1) // includes (higestRange[1] == -1)
1367       {
1368         endPos = alignmentStartEnd[1];
1369       }
1370       else
1371       {
1372         endPos = higestRange[0] - 1;
1373       }
1374       return new int[] { startPos, endPos };
1375     } finally
1376     {
1377       LOCK.readLock().unlock();
1378     }
1379   }
1380
1381   /**
1382    * Finds the hidden region (if any) which starts or ends at res
1383    *
1384    * @param res
1385    *          visible residue position, unadjusted for hidden columns
1386    * @return region as [start,end] or null if no matching region is found
1387    */
1388   public int[] getRegionWithEdgeAtRes(int res)
1389   {
1390     try
1391     {
1392       LOCK.readLock().lock();
1393       int adjres = adjustForHiddenColumns(res);
1394
1395       int[] reveal = null;
1396
1397       if (hiddenColumns != null)
1398       {
1399         // look for a region ending just before adjres
1400         int regionindex = cursor.findRegionForColumn(adjres - 1)
1401                 .getRegionIndex();
1402         if (regionindex < hiddenColumns.size()
1403                 && hiddenColumns.get(regionindex)[1] == adjres - 1)
1404         {
1405           reveal = hiddenColumns.get(regionindex);
1406         }
1407         // check if the region ends just after adjres
1408         else if (regionindex < hiddenColumns.size()
1409                 && hiddenColumns.get(regionindex)[0] == adjres + 1)
1410         {
1411           reveal = hiddenColumns.get(regionindex);
1412         }
1413       }
1414       return reveal;
1415
1416     } finally
1417     {
1418       LOCK.readLock().unlock();
1419     }
1420   }
1421
1422   /**
1423    * Return an iterator over the hidden regions
1424    */
1425   public Iterator<int[]> iterator()
1426   {
1427     try
1428     {
1429       LOCK.readLock().lock();
1430       return new HiddenColsIterator(hiddenColumns);
1431     } finally
1432     {
1433       LOCK.readLock().unlock();
1434     }
1435   }
1436
1437   /**
1438    * Return a bounded iterator over the hidden regions
1439    *
1440    * @param start
1441    *          position to start from (inclusive, absolute column position)
1442    * @param end
1443    *          position to end at (inclusive, absolute column position)
1444    * @return
1445    */
1446   public Iterator<int[]> getBoundedIterator(int start, int end)
1447   {
1448     try
1449     {
1450       LOCK.readLock().lock();
1451       return new HiddenColsIterator(start, end, hiddenColumns);
1452     } finally
1453     {
1454       LOCK.readLock().unlock();
1455     }
1456   }
1457
1458   /**
1459    * Return a bounded iterator over the *visible* start positions of hidden
1460    * regions
1461    *
1462    * @param start
1463    *          position to start from (inclusive, visible column position)
1464    * @param end
1465    *          position to end at (inclusive, visible column position)
1466    */
1467   public Iterator<Integer> getBoundedStartIterator(int start, int end)
1468   {
1469     try
1470     {
1471       LOCK.readLock().lock();
1472
1473       // get absolute position of column in alignment
1474       int absoluteStart = adjustForHiddenColumns(start);
1475
1476       // Get cursor position and supply it to the iterator:
1477       // Since we want visible region start, we look for a cursor for the
1478       // (absoluteStart-1), then if absoluteStart is the start of a visible
1479       // region we'll get the cursor pointing to the region before, which is
1480       // what we want
1481       HiddenCursorPosition pos = cursor
1482               .findRegionForColumn(absoluteStart - 1);
1483
1484       return new BoundedStartRegionIterator(pos, start, end,
1485               hiddenColumns);
1486     } finally
1487     {
1488       LOCK.readLock().unlock();
1489     }
1490   }
1491
1492   /**
1493    * Return an iterator over visible *columns* (not regions) between the given
1494    * start and end boundaries
1495    *
1496    * @param start
1497    *          first column (inclusive)
1498    * @param end
1499    *          last column (inclusive)
1500    */
1501   public Iterator<Integer> getVisibleColsIterator(int start, int end)
1502   {
1503     try
1504     {
1505       LOCK.readLock().lock();
1506       return new VisibleColsIterator(start, end, hiddenColumns);
1507     } finally
1508     {
1509       LOCK.readLock().unlock();
1510     }
1511   }
1512
1513   /**
1514    * return an iterator over visible segments between the given start and end
1515    * boundaries
1516    *
1517    * @param start
1518    *          first column, inclusive from 0
1519    * @param end
1520    *          last column - not inclusive
1521    * @param useVisibleCoords
1522    *          if true, start and end are visible column positions, not absolute
1523    *          positions*
1524    */
1525   public Iterator<int[]> getVisContigsIterator(int start, int end,
1526           boolean useVisibleCoords)
1527   {
1528     int adjstart = start;
1529     int adjend = end;
1530     if (useVisibleCoords)
1531     {
1532       adjstart = adjustForHiddenColumns(start);
1533       adjend = adjustForHiddenColumns(end);
1534     }
1535
1536     try
1537     {
1538       LOCK.readLock().lock();
1539       return new VisibleContigsIterator(adjstart, adjend, hiddenColumns);
1540     } finally
1541     {
1542       LOCK.readLock().unlock();
1543     }
1544   }
1545 }