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