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