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.Arrays;
  25 import java.util.BitSet;
  26 import java.util.Iterator;
  27 import java.util.List;
  28 import java.util.concurrent.locks.ReentrantReadWriteLock;
  29
  30 /**
  31  * This class manages the collection of hidden columns associated with an
  32  * alignment. To iterate over the collection, or over visible columns/regions,
  33  * use an iterator obtained from one of:
  34  *
  35  * - getBoundedIterator: iterates over the hidden regions, within some bounds,
  36  * returning absolute positions
  37  *
  38  * - getBoundedStartIterator: iterates over the start positions of hidden
  39  * regions, within some bounds, returning visible positions
  40  *
  41  * - getVisContigsIterator: iterates over visible regions in a range, returning
  42  * absolute positions
  43  *
  44  * - getVisibleColsIterator: iterates over the visible *columns*
  45  *
  46  * For performance reasons, provide bounds where possible. Note that column
  47  * numbering begins at 0 throughout this class.
  48  *
  49  * @author kmourao
  50  *
  51  */
  52 public class HiddenColumns
  53 {
  54   private static final int HASH_MULTIPLIER = 31;
  55
  56   private static final ReentrantReadWriteLock LOCK = new ReentrantReadWriteLock();
  57
  58   /*
  59    * Cursor which tracks the last used hidden columns region, and the number
  60    * of hidden columns up to (but not including) that region.
  61    */
  62   private HiddenColumnsCursor cursor = new HiddenColumnsCursor();
  63
  64   /*
  65    * cache of the number of hidden columns
  66    */
  67   private int numColumns = 0;
  68
  69   /*
  70    * list of hidden column [start, end] ranges; the list is maintained in
  71    * ascending start column order
  72    */
  73   private List<int[]> hiddenColumns = new ArrayList<>();
  74
  75   /**
  76    * Constructor
  77    */
  78   public HiddenColumns()
  79   {
  80   }
  81
  82   /*
  83    * Methods which change the hiddenColumns collection. These methods should
  84    * use a writeLock to prevent other threads accessing the hiddenColumns
  85    * collection while changes are being made. They should also reset the hidden
  86    * columns cursor, and either update the hidden columns count, or set it to 0
  87    * (so that it will later be updated when needed).
  88    */
  89
  90   /**
  91    * Copy constructor
  92    *
  93    * @param copy
  94    *          the HiddenColumns object to copy from
  95    */
  96   public HiddenColumns(HiddenColumns copy)
  97   {
  98     this(copy, Integer.MIN_VALUE, Integer.MAX_VALUE, 0);
  99   }
 100
 101   /**
 102    * Copy constructor within bounds and with offset. Copies hidden column
 103    * regions fully contained between start and end, and offsets positions by
 104    * subtracting offset.
 105    *
 106    * @param copy
 107    *          HiddenColumns instance to copy from
 108    * @param start
 109    *          lower bound to copy from
 110    * @param end
 111    *          upper bound to copy to
 112    * @param offset
 113    *          offset to subtract from each region boundary position
 114    *
 115    */
 116   public HiddenColumns(HiddenColumns copy, int start, int end, int offset)
 117   {
 118     try
 119     {
 120       LOCK.writeLock().lock();
 121       if (copy != null)
 122       {
 123         numColumns = 0;
 124         Iterator<int[]> it = copy.getBoundedIterator(start, end);
 125         while (it.hasNext())
 126         {
 127           int[] region = it.next();
 128           // still need to check boundaries because iterator returns
 129           // all overlapping regions and we need contained regions
 130           if (region[0] >= start && region[1] <= end)
 131           {
 132             hiddenColumns.add(
 133                     new int[]
 134             { region[0] - offset, region[1] - offset });
 135             numColumns += region[1] - region[0] + 1;
 136           }
 137         }
 138         cursor.resetCursor(hiddenColumns);
 139       }
 140     } finally
 141     {
 142       LOCK.writeLock().unlock();
 143     }
 144   }
 145
 146   /**
 147    * Adds the specified column range to the hidden columns collection
 148    *
 149    * @param start
 150    *          start of range to add (absolute position in alignment)
 151    * @param end
 152    *          end of range to add (absolute position in alignment)
 153    */
 154   public void hideColumns(int start, int end)
 155   {
 156     try
 157     {
 158       LOCK.writeLock().lock();
 159
 160       int previndex = 0;
 161       int prevHiddenCount = 0;
 162       int regionindex = 0;
 163       if (!hiddenColumns.isEmpty())
 164       {
 165         // set up cursor reset values
 166         HiddenCursorPosition cursorPos = cursor.findRegionForColumn(start);
 167         regionindex = cursorPos.getRegionIndex();
 168
 169         if (regionindex > 0)
 170         {
 171           // get previous index and hidden count for updating the cursor later
 172           previndex = regionindex - 1;
 173           int[] prevRegion = hiddenColumns.get(previndex);
 174           prevHiddenCount = cursorPos.getHiddenSoFar()
 175                   - (prevRegion[1] - prevRegion[0] + 1);
 176         }
 177       }
 178
 179       /*
 180        * new range follows everything else; check first to avoid looping over whole hiddenColumns collection
 181        */
 182       if (hiddenColumns.isEmpty()
 183               || start > hiddenColumns.get(hiddenColumns.size() - 1)[1])
 184       {
 185         hiddenColumns.add(new int[] { start, end });
 186       }
 187       else
 188       {
 189         /*
 190          * traverse existing hidden ranges and insert / amend / append as
 191          * appropriate
 192          */
 193         boolean added = false;
 194         if (regionindex > 0)
 195         {
 196           added = insertRangeAtRegion(regionindex - 1, start, end);
 197         }
 198         if (!added && regionindex < hiddenColumns.size())
 199         {
 200           insertRangeAtRegion(regionindex, start, end);
 201         }
 202       }
 203
 204       // reset the cursor to just before our insertion point: this saves
 205       // a lot of reprocessing in large alignments
 206       cursor.resetCursor(hiddenColumns, previndex, prevHiddenCount);
 207
 208       // reset the number of columns so they will be recounted
 209       numColumns = 0;
 210
 211     } finally
 212     {
 213       LOCK.writeLock().unlock();
 214     }
 215   }
 216
 217   /**
 218    * Insert [start, range] at the region at index i in hiddenColumns, if
 219    * feasible
 220    *
 221    * @param i
 222    *          index to insert at
 223    * @param start
 224    *          start of range to insert
 225    * @param end
 226    *          end of range to insert
 227    * @return true if range was successfully inserted
 228    */
 229   private boolean insertRangeAtRegion(int i, int start, int end)
 230   {
 231     boolean added = false;
 232
 233     int[] region = hiddenColumns.get(i);
 234     if (end < region[0] - 1)
 235     {
 236       /*
 237        * insert discontiguous preceding range
 238        */
 239       hiddenColumns.add(i, new int[] { start, end });
 240       added = true;
 241     }
 242     else if (end <= region[1])
 243     {
 244       /*
 245        * new range overlaps existing, or is contiguous preceding it - adjust
 246        * start column
 247        */
 248       region[0] = Math.min(region[0], start);
 249       added = true;
 250     }
 251     else if (start <= region[1] + 1)
 252     {
 253       /*
 254        * new range overlaps existing, or is contiguous following it - adjust
 255        * start and end columns
 256        */
 257       region[0] = Math.min(region[0], start);
 258       region[1] = Math.max(region[1], end);
 259
 260       /*
 261        * also update or remove any subsequent ranges
 262        * that are overlapped
 263        */
 264       while (i < hiddenColumns.size() - 1)
 265       {
 266         int[] nextRegion = hiddenColumns.get(i + 1);
 267         if (nextRegion[0] > end + 1)
 268         {
 269           /*
 270            * gap to next hidden range - no more to update
 271            */
 272           break;
 273         }
 274         region[1] = Math.max(nextRegion[1], end);
 275
 276         // in theory this is faster than hiddenColumns.remove(i+1)
 277         // benchmarking results a bit ambivalent
 278         hiddenColumns.subList(i + 1, i + 2).clear();
 279       }
 280       added = true;
 281     }
 282     return added;
 283   }
 284
 285   /**
 286    * hide a list of ranges
 287    *
 288    * @param ranges
 289    */
 290   public void hideList(List<int[]> ranges)
 291   {
 292     try
 293     {
 294       LOCK.writeLock().lock();
 295       for (int[] r : ranges)
 296       {
 297         hideColumns(r[0], r[1]);
 298       }
 299       cursor.resetCursor(hiddenColumns);
 300       numColumns = 0;
 301     } finally
 302     {
 303       LOCK.writeLock().unlock();
 304     }
 305   }
 306
 307   /**
 308    * Unhides, and adds to the selection list, all hidden columns
 309    */
 310   public void revealAllHiddenColumns(ColumnSelection sel)
 311   {
 312     try
 313     {
 314       LOCK.writeLock().lock();
 315
 316       for (int[] region : hiddenColumns)
 317       {
 318         for (int j = region[0]; j < region[1] + 1; j++)
 319         {
 320           sel.addElement(j);
 321         }
 322       }
 323       hiddenColumns.clear();
 324       cursor.resetCursor(hiddenColumns);
 325       numColumns = 0;
 326
 327     } finally
 328     {
 329       LOCK.writeLock().unlock();
 330     }
 331   }
 332
 333   /**
 334    * Reveals, and marks as selected, the hidden column range with the given
 335    * start column
 336    *
 337    * @param start
 338    *          the start column to look for
 339    * @param sel
 340    *          the column selection to add the hidden column range to
 341    */
 342   public void revealHiddenColumns(int start, ColumnSelection sel)
 343   {
 344     try
 345     {
 346       LOCK.writeLock().lock();
 347
 348       if (!hiddenColumns.isEmpty())
 349       {
 350         int regionIndex = cursor.findRegionForColumn(start)
 351                 .getRegionIndex();
 352
 353         if (regionIndex != -1 && regionIndex != hiddenColumns.size())
 354         {
 355           // regionIndex is the region which either contains start
 356           // or lies to the right of start
 357           int[] region = hiddenColumns.get(regionIndex);
 358           if (start == region[0])
 359           {
 360             for (int j = region[0]; j < region[1] + 1; j++)
 361             {
 362               sel.addElement(j);
 363             }
 364             int colsToRemove = region[1] - region[0] + 1;
 365             hiddenColumns.remove(regionIndex);
 366
 367             if (hiddenColumns.isEmpty())
 368             {
 369               hiddenColumns.clear();
 370               numColumns = 0;
 371             }
 372             else
 373             {
 374               numColumns -= colsToRemove;
 375             }
 376             cursor.updateForDeletedRegion(hiddenColumns);
 377           }
 378         }
 379       }
 380     } finally
 381     {
 382       LOCK.writeLock().unlock();
 383     }
 384   }
 385
 386
 387
 388
 389   /*
 390    * Methods which only need read access to the hidden columns collection.
 391    * These methods should use a readLock to prevent other threads changing
 392    * the hidden columns collection while it is in use.
 393    */
 394
 395   /**
 396    * Output regions data as a string. String is in the format:
 397    * reg0[0]<between>reg0[1]<delimiter>reg1[0]<between>reg1[1] ... regn[1]
 398    *
 399    * @param delimiter
 400    *          string to delimit regions
 401    * @param betweenstring
 402    *          to put between start and end region values
 403    * @return regions formatted according to delimiter and between strings
 404    */
 405   public String regionsToString(String delimiter, String between)
 406   {
 407     try
 408     {
 409       LOCK.readLock().lock();
 410       StringBuilder regionBuilder = new StringBuilder();
 411
 412       boolean first = true;
 413       for (int[] range : hiddenColumns)
 414       {
 415         if (!first)
 416         {
 417           regionBuilder.append(delimiter);
 418         }
 419         else
 420         {
 421           first = false;
 422         }
 423         regionBuilder.append(range[0]).append(between).append(range[1]);
 424
 425       }
 426
 427       return regionBuilder.toString();
 428     } finally
 429     {
 430       LOCK.readLock().unlock();
 431     }
 432   }
 433
 434   /**
 435    * Find the number of hidden columns
 436    *
 437    * @return number of hidden columns
 438    */
 439   public int getSize()
 440   {
 441     try
 442     {
 443       LOCK.readLock().lock();
 444
 445       if (numColumns == 0)
 446       {
 447         // numColumns is out of date, so recalculate
 448         int size = 0;
 449
 450         for (int[] range : hiddenColumns)
 451         {
 452           size += range[1] - range[0] + 1;
 453         }
 454
 455         numColumns = size;
 456       }
 457
 458       return numColumns;
 459     } finally
 460     {
 461       LOCK.readLock().unlock();
 462     }
 463   }
 464
 465   /**
 466    * Get the number of distinct hidden regions
 467    *
 468    * @return number of regions
 469    */
 470   public int getNumberOfRegions()
 471   {
 472     try
 473     {
 474       LOCK.readLock().lock();
 475       return hiddenColumns.size();
 476     } finally
 477     {
 478       LOCK.readLock().unlock();
 479     }
 480   }
 481
 482   @Override
 483   public boolean equals(Object obj)
 484   {
 485     try
 486     {
 487       LOCK.readLock().lock();
 488
 489       if (!(obj instanceof HiddenColumns))
 490       {
 491         return false;
 492       }
 493       HiddenColumns that = (HiddenColumns) obj;
 494
 495       /*
 496        * check hidden columns are either both null, or match
 497        */
 498
 499       if (that.hiddenColumns.size() != this.hiddenColumns.size())
 500       {
 501         return false;
 502       }
 503
 504       Iterator<int[]> it = this.iterator();
 505       Iterator<int[]> thatit = that.iterator();
 506       while (it.hasNext())
 507       {
 508         if (!(Arrays.equals(it.next(), thatit.next())))
 509         {
 510           return false;
 511         }
 512       }
 513       return true;
 514
 515     } finally
 516     {
 517       LOCK.readLock().unlock();
 518     }
 519   }
 520
 521   /**
 522    * Return absolute column index for a visible column index
 523    *
 524    * @param column
 525    *          int column index in alignment view (count from zero)
 526    * @return alignment column index for column
 527    */
 528   public int visibleToAbsoluteColumn(int column)
 529   {
 530     try
 531     {
 532       LOCK.readLock().lock();
 533       int result = column;
 534
 535       if (!hiddenColumns.isEmpty())
 536       {
 537         result += cursor.findRegionForVisColumn(column).getHiddenSoFar();
 538       }
 539
 540       return result;
 541     } finally
 542     {
 543       LOCK.readLock().unlock();
 544     }
 545   }
 546
 547   /**
 548    * Use this method to find out where a column will appear in the visible
 549    * alignment when hidden columns exist. If the column is not visible, then the
 550    * index of the next visible column on the left will be returned (or 0 if
 551    * there is no visible column on the left)
 552    *
 553    * @param hiddenColumn
 554    *          the column index in the full alignment including hidden columns
 555    * @return the position of the column in the visible alignment
 556    */
 557   public int absoluteToVisibleColumn(int hiddenColumn)
 558   {
 559     try
 560     {
 561       LOCK.readLock().lock();
 562       int result = hiddenColumn;
 563
 564       if (!hiddenColumns.isEmpty())
 565       {
 566         HiddenCursorPosition cursorPos = cursor
 567                 .findRegionForColumn(hiddenColumn);
 568         int index = cursorPos.getRegionIndex();
 569         int hiddenBeforeCol = cursorPos.getHiddenSoFar();
 570
 571         // just subtract hidden cols count - this works fine if column is
 572         // visible
 573         result = hiddenColumn - hiddenBeforeCol;
 574
 575         // now check in case column is hidden - it will be in the returned
 576         // hidden region
 577         if (index < hiddenColumns.size())
 578         {
 579           int[] region = hiddenColumns.get(index);
 580           if (hiddenColumn >= region[0] && hiddenColumn <= region[1])
 581           {
 582             // actually col is hidden, return region[0]-1
 583             // unless region[0]==0 in which case return 0
 584             if (region[0] == 0)
 585             {
 586               result = 0;
 587             }
 588             else
 589             {
 590               result = region[0] - 1 - hiddenBeforeCol;
 591             }
 592           }
 593         }
 594       }
 595
 596       return result; // return the shifted position after removing hidden
 597                      // columns.
 598     } finally
 599     {
 600       LOCK.readLock().unlock();
 601     }
 602   }
 603
 604   /**
 605    * Find the visible column which is a given visible number of columns to the
 606    * left (negative visibleDistance) or right (positive visibleDistance) of
 607    * startColumn. If startColumn is not visible, we use the visible column at
 608    * the left boundary of the hidden region containing startColumn.
 609    *
 610    * @param visibleDistance
 611    *          the number of visible columns to offset by (left offset = negative
 612    *          value; right offset = positive value)
 613    * @param startColumn
 614    *          the position of the column to start from (absolute position)
 615    * @return the position of the column which is <visibleDistance> away
 616    *         (absolute position)
 617    */
 618   public int offsetByVisibleColumns(int visibleDistance, int startColumn)
 619   {
 620     try
 621     {
 622       LOCK.readLock().lock();
 623       int start = absoluteToVisibleColumn(startColumn);
 624       return visibleToAbsoluteColumn(start + visibleDistance);
 625
 626     } finally
 627     {
 628       LOCK.readLock().unlock();
 629     }
 630   }
 631
 632   /**
 633    * This method returns the rightmost limit of a region of an alignment with
 634    * hidden columns. In otherwords, the next hidden column.
 635    *
 636    * @param alPos
 637    *          the absolute (visible) alignmentPosition to find the next hidden
 638    *          column for
 639    * @return the index of the next hidden column, or alPos if there is no next
 640    *         hidden column
 641    */
 642   public int getHiddenBoundaryRight(int alPos)
 643   {
 644     try
 645     {
 646       LOCK.readLock().lock();
 647       if (!hiddenColumns.isEmpty())
 648       {
 649         int index = cursor.findRegionForColumn(alPos).getRegionIndex();
 650         if (index < hiddenColumns.size())
 651         {
 652           int[] region = hiddenColumns.get(index);
 653           if (alPos < region[0])
 654           {
 655             return region[0];
 656           }
 657           else if ((alPos <= region[1])
 658                   && (index + 1 < hiddenColumns.size()))
 659           {
 660             // alPos is within a hidden region, return the next one
 661             // if there is one
 662             region = hiddenColumns.get(index + 1);
 663             return region[0];
 664           }
 665         }
 666       }
 667       return alPos;
 668     } finally
 669     {
 670       LOCK.readLock().unlock();
 671     }
 672   }
 673
 674   /**
 675    * This method returns the leftmost limit of a region of an alignment with
 676    * hidden columns. In otherwords, the previous hidden column.
 677    *
 678    * @param alPos
 679    *          the absolute (visible) alignmentPosition to find the previous
 680    *          hidden column for
 681    */
 682   public int getHiddenBoundaryLeft(int alPos)
 683   {
 684     try
 685     {
 686       LOCK.readLock().lock();
 687
 688       if (!hiddenColumns.isEmpty())
 689       {
 690         int index = cursor.findRegionForColumn(alPos).getRegionIndex();
 691
 692         if (index > 0)
 693         {
 694           int[] region = hiddenColumns.get(index - 1);
 695           return region[1];
 696         }
 697       }
 698       return alPos;
 699     } finally
 700     {
 701       LOCK.readLock().unlock();
 702     }
 703   }
 704
 705
 706   /**
 707    * Answers if a column in the alignment is visible
 708    *
 709    * @param column
 710    *          absolute position of column in the alignment
 711    * @return true if column is visible
 712    */
 713   public boolean isVisible(int column)
 714   {
 715     try
 716     {
 717       LOCK.readLock().lock();
 718
 719       int regionindex = cursor.findRegionForColumn(column).getRegionIndex();
 720       if (regionindex > -1 && regionindex < hiddenColumns.size())
 721       {
 722         int[] region = hiddenColumns.get(regionindex);
 723         // already know that column <= region[1] as cursor returns containing
 724         // region or region to right
 725         if (column >= region[0])
 726         {
 727           return false;
 728         }
 729       }
 730       return true;
 731
 732     } finally
 733     {
 734       LOCK.readLock().unlock();
 735     }
 736   }
 737
 738   /**
 739    * Get the visible sections of a set of sequences
 740    *
 741    * @param start
 742    *          sequence position to start from
 743    * @param end
 744    *          sequence position to end at
 745    * @param seqs
 746    *          an array of sequences
 747    * @return an array of strings encoding the visible parts of each sequence
 748    */
 749   public String[] getVisibleSequenceStrings(int start, int end,
 750           SequenceI[] seqs)
 751   {
 752     try
 753     {
 754       LOCK.readLock().lock();
 755       int iSize = seqs.length;
 756       String[] selections = new String[iSize];
 757       if (!hiddenColumns.isEmpty())
 758       {
 759         for (int i = 0; i < iSize; i++)
 760         {
 761           StringBuilder visibleSeq = new StringBuilder();
 762
 763           Iterator<int[]> blocks = new VisibleContigsIterator(start,
 764                   end + 1, hiddenColumns);
 765
 766           while (blocks.hasNext())
 767           {
 768             int[] block = blocks.next();
 769             if (blocks.hasNext())
 770             {
 771               visibleSeq
 772                       .append(seqs[i].getSequence(block[0], block[1] + 1));
 773             }
 774             else
 775             {
 776               visibleSeq
 777                       .append(seqs[i].getSequence(block[0], block[1]));
 778             }
 779           }
 780
 781           selections[i] = visibleSeq.toString();
 782         }
 783       }
 784       else
 785       {
 786         for (int i = 0; i < iSize; i++)
 787         {
 788           selections[i] = seqs[i].getSequenceAsString(start, end);
 789         }
 790       }
 791
 792       return selections;
 793     } finally
 794     {
 795       LOCK.readLock().unlock();
 796     }
 797   }
 798
 799   /**
 800    * Locate the first position visible for this sequence. If seq isn't visible
 801    * then return the position of the left side of the hidden boundary region.
 802    *
 803    * @param seq
 804    *          sequence to find position for
 805    * @return visible start position
 806    */
 807   public int locateVisibleStartOfSequence(SequenceI seq)
 808   {
 809     try
 810     {
 811       LOCK.readLock().lock();
 812       int start = 0;
 813
 814       if (hiddenColumns.isEmpty())
 815       {
 816         return seq.findIndex(seq.getStart()) - 1;
 817       }
 818
 819       // Simply walk along the sequence whilst watching for hidden column
 820       // boundaries
 821       Iterator<int[]> regions = hiddenColumns.iterator();
 822       int hideStart = seq.getLength();
 823       int hideEnd = -1;
 824       int visPrev = 0;
 825       int visNext = 0;
 826       boolean foundStart = false;
 827
 828       // step through the non-gapped positions of the sequence
 829       for (int i = seq.getStart(); i <= seq.getEnd() && (!foundStart); i++)
 830       {
 831         // get alignment position of this residue in the sequence
 832         int p = seq.findIndex(i) - 1;
 833
 834         // update hidden region start/end
 835         while (hideEnd < p && regions.hasNext())
 836         {
 837           int[] region = regions.next();
 838           visPrev = visNext;
 839           visNext += region[0] - visPrev;
 840           hideStart = region[0];
 841           hideEnd = region[1];
 842         }
 843         if (hideEnd < p)
 844         {
 845           hideStart = seq.getLength();
 846         }
 847         // update visible boundary for sequence
 848         if (p < hideStart)
 849         {
 850           start = p;
 851           foundStart = true;
 852         }
 853       }
 854
 855       if (foundStart)
 856       {
 857         return absoluteToVisibleColumn(start);
 858       }
 859       // otherwise, sequence was completely hidden
 860       return visPrev;
 861     } finally
 862     {
 863       LOCK.readLock().unlock();
 864     }
 865   }
 866
 867
 868   /**
 869    *
 870    * @return true if there are columns hidden
 871    */
 872   public boolean hasHiddenColumns()
 873   {
 874     try
 875     {
 876       LOCK.readLock().lock();
 877
 878       // we don't use getSize()>0 here because it has to iterate over
 879       // the full hiddenColumns collection and so will be much slower
 880       return (!hiddenColumns.isEmpty());
 881     } finally
 882     {
 883       LOCK.readLock().unlock();
 884     }
 885   }
 886
 887   /**
 888    *
 889    * @return true if there is more than one hidden column region
 890    */
 891   public boolean hasMultiHiddenColumnRegions()
 892   {
 893     try
 894     {
 895       LOCK.readLock().lock();
 896       return !hiddenColumns.isEmpty() && hiddenColumns.size() > 1;
 897     } finally
 898     {
 899       LOCK.readLock().unlock();
 900     }
 901   }
 902
 903
 904   /**
 905    * Returns a hashCode built from hidden column ranges
 906    */
 907   @Override
 908   public int hashCode()
 909   {
 910     try
 911     {
 912       LOCK.readLock().lock();
 913       int hashCode = 1;
 914       for (int[] hidden : hiddenColumns)
 915       {
 916         hashCode = HASH_MULTIPLIER * hashCode + hidden[0];
 917         hashCode = HASH_MULTIPLIER * hashCode + hidden[1];
 918       }
 919       return hashCode;
 920     } finally
 921     {
 922       LOCK.readLock().unlock();
 923     }
 924   }
 925
 926   /**
 927    * Hide columns corresponding to the marked bits
 928    *
 929    * @param inserts
 930    *          - columns mapped to bits starting from zero
 931    */
 932   public void hideColumns(BitSet inserts)
 933   {
 934     try
 935     {
 936       LOCK.writeLock().lock();
 937       for (int firstSet = inserts
 938               .nextSetBit(0), lastSet = 0; firstSet >= 0; firstSet = inserts
 939                       .nextSetBit(lastSet))
 940       {
 941         lastSet = inserts.nextClearBit(firstSet);
 942         hideColumns(firstSet, lastSet - 1);
 943       }
 944       cursor.resetCursor(hiddenColumns);
 945       numColumns = 0;
 946     } finally
 947     {
 948       LOCK.writeLock().unlock();
 949     }
 950   }
 951
 952   /**
 953    * Hide columns corresponding to the marked bits, within the range
 954    * [start,end]. Entries in tohide which are outside [start,end] are ignored.
 955    *
 956    * @param tohide
 957    *          columns mapped to bits starting from zero
 958    * @param start
 959    *          start of range to hide columns within
 960    * @param end
 961    *          end of range to hide columns within
 962    */
 963   public void hideColumns(BitSet tohide, int start, int end)
 964   {
 965     clearHiddenColumnsInRange(start, end);
 966
 967     // make sure only bits between start and end are set
 968     if (!tohide.isEmpty())
 969     {
 970       tohide.clear(0, start);
 971       tohide.clear(Math.min(end + 1, tohide.length() + 1),
 972               tohide.length() + 1);
 973     }
 974
 975     hideColumns(tohide);
 976   }
 977
 978   /**
 979    * Make all columns in the range [start,end] visible
 980    *
 981    * @param start
 982    *          start of range to show columns
 983    * @param end
 984    *          end of range to show columns
 985    */
 986   private void clearHiddenColumnsInRange(int start, int end)
 987   {
 988     try
 989     {
 990       LOCK.writeLock().lock();
 991
 992       if (!hiddenColumns.isEmpty())
 993       {
 994         HiddenCursorPosition pos = cursor.findRegionForColumn(start);
 995         int index = pos.getRegionIndex();
 996         int startindex = index; // first index in hiddenColumns to remove
 997
 998         if (index != -1 && index != hiddenColumns.size())
 999         {
1000           // regionIndex is the region which either contains start
1001           // or lies to the right of start
1002           int[] region = hiddenColumns.get(index);
1003           if (region[0] < start && region[1] >= start)
1004           {
1005             // region contains start, truncate so that it ends just before start
1006             region[1] = start - 1;
1007             startindex++;
1008           }
1009         }
1010
1011         pos = cursor.findRegionForColumn(end);
1012         index = pos.getRegionIndex();
1013         int endindex = index - 1; // last index in hiddenColumns to remove
1014
1015         if (index != -1 && index != hiddenColumns.size())
1016         {
1017           // regionIndex is the region which either contains end
1018           // or lies to the right of end
1019           int[] region = hiddenColumns.get(index);
1020           if (region[0] <= end && region[1] > end)
1021           {
1022             // region contains end, truncate so that it starts just after end
1023             region[0] = end + 1;
1024           }
1025         }
1026
1027         hiddenColumns.subList(startindex, endindex + 1).clear();
1028         cursor.resetCursor(hiddenColumns);
1029         numColumns = 0;
1030       }
1031     } finally
1032     {
1033       LOCK.writeLock().unlock();
1034     }
1035   }
1036
1037   /**
1038    *
1039    * @param updates
1040    *          BitSet where hidden columns will be marked
1041    */
1042   protected void andNot(BitSet updates)
1043   {
1044     try
1045     {
1046       LOCK.writeLock().lock();
1047
1048       BitSet hiddenBitSet = new BitSet();
1049       for (int[] range : hiddenColumns)
1050       {
1051         hiddenBitSet.set(range[0], range[1] + 1);
1052       }
1053       hiddenBitSet.andNot(updates);
1054       hiddenColumns.clear();
1055       hideColumns(hiddenBitSet);
1056     } finally
1057     {
1058       LOCK.writeLock().unlock();
1059     }
1060   }
1061
1062   /**
1063    * Calculate the visible start and end index of an alignment.
1064    *
1065    * @param width
1066    *          full alignment width
1067    * @return integer array where: int[0] = startIndex, and int[1] = endIndex
1068    */
1069   public int[] getVisibleStartAndEndIndex(int width)
1070   {
1071     try
1072     {
1073       LOCK.readLock().lock();
1074
1075       int firstVisible = 0;
1076       int lastVisible = width - 1;
1077
1078       if (!hiddenColumns.isEmpty())
1079       {
1080         // first visible col with index 0, convert to absolute index
1081         firstVisible = visibleToAbsoluteColumn(0);
1082
1083         // last visible column is either immediately to left of
1084         // last hidden region, or is just the last column in the alignment
1085         int[] lastregion = hiddenColumns.get(hiddenColumns.size() - 1);
1086         if (lastregion[1] == width - 1)
1087         {
1088           // last region is at very end of alignment
1089           // last visible column immediately precedes it
1090           lastVisible = lastregion[0] - 1;
1091         }
1092       }
1093       return new int[] { firstVisible, lastVisible };
1094
1095     } finally
1096     {
1097       LOCK.readLock().unlock();
1098     }
1099   }
1100
1101   /**
1102    * Finds the hidden region (if any) which starts or ends at res
1103    *
1104    * @param res
1105    *          visible residue position, unadjusted for hidden columns
1106    * @return region as [start,end] or null if no matching region is found. If
1107    *         res is adjacent to two regions, returns the left region.
1108    */
1109   public int[] getRegionWithEdgeAtRes(int res)
1110   {
1111     try
1112     {
1113       LOCK.readLock().lock();
1114       int adjres = visibleToAbsoluteColumn(res);
1115
1116       int[] reveal = null;
1117
1118       if (!hiddenColumns.isEmpty())
1119       {
1120         // look for a region ending just before adjres
1121         int regionindex = cursor.findRegionForColumn(adjres - 1)
1122                 .getRegionIndex();
1123         if (regionindex < hiddenColumns.size()
1124                 && hiddenColumns.get(regionindex)[1] == adjres - 1)
1125         {
1126           reveal = hiddenColumns.get(regionindex);
1127         }
1128         // check if the region ends just after adjres
1129         else if (regionindex < hiddenColumns.size()
1130                 && hiddenColumns.get(regionindex)[0] == adjres + 1)
1131         {
1132           reveal = hiddenColumns.get(regionindex);
1133         }
1134       }
1135       return reveal;
1136
1137     } finally
1138     {
1139       LOCK.readLock().unlock();
1140     }
1141   }
1142
1143   /**
1144    * Return an iterator over the hidden regions
1145    */
1146   public Iterator<int[]> iterator()
1147   {
1148     try
1149     {
1150       LOCK.readLock().lock();
1151       return new HiddenColsIterator(hiddenColumns);
1152     } finally
1153     {
1154       LOCK.readLock().unlock();
1155     }
1156   }
1157
1158   /**
1159    * Return a bounded iterator over the hidden regions
1160    *
1161    * @param start
1162    *          position to start from (inclusive, absolute column position)
1163    * @param end
1164    *          position to end at (inclusive, absolute column position)
1165    * @return
1166    */
1167   public Iterator<int[]> getBoundedIterator(int start, int end)
1168   {
1169     try
1170     {
1171       LOCK.readLock().lock();
1172       return new HiddenColsIterator(start, end, hiddenColumns);
1173     } finally
1174     {
1175       LOCK.readLock().unlock();
1176     }
1177   }
1178
1179   /**
1180    * Return a bounded iterator over the *visible* start positions of hidden
1181    * regions
1182    *
1183    * @param start
1184    *          position to start from (inclusive, visible column position)
1185    * @param end
1186    *          position to end at (inclusive, visible column position)
1187    */
1188   public Iterator<Integer> getBoundedStartIterator(int start, int end)
1189   {
1190     try
1191     {
1192       LOCK.readLock().lock();
1193
1194       // get absolute position of column in alignment
1195       int absoluteStart = visibleToAbsoluteColumn(start);
1196
1197       // Get cursor position and supply it to the iterator:
1198       // Since we want visible region start, we look for a cursor for the
1199       // (absoluteStart-1), then if absoluteStart is the start of a visible
1200       // region we'll get the cursor pointing to the region before, which is
1201       // what we want
1202       HiddenCursorPosition pos = cursor
1203               .findRegionForColumn(absoluteStart - 1);
1204
1205       return new BoundedStartRegionIterator(pos, start, end,
1206               hiddenColumns);
1207     } finally
1208     {
1209       LOCK.readLock().unlock();
1210     }
1211   }
1212
1213   /**
1214    * Return an iterator over visible *columns* (not regions) between the given
1215    * start and end boundaries
1216    *
1217    * @param start
1218    *          first column (inclusive)
1219    * @param end
1220    *          last column (inclusive)
1221    */
1222   public Iterator<Integer> getVisibleColsIterator(int start, int end)
1223   {
1224     try
1225     {
1226       LOCK.readLock().lock();
1227       return new VisibleColsIterator(start, end, hiddenColumns);
1228     } finally
1229     {
1230       LOCK.readLock().unlock();
1231     }
1232   }
1233
1234   /**
1235    * return an iterator over visible segments between the given start and end
1236    * boundaries
1237    *
1238    * @param start
1239    *          first column, inclusive from 0
1240    * @param end
1241    *          last column - not inclusive
1242    * @param useVisibleCoords
1243    *          if true, start and end are visible column positions, not absolute
1244    *          positions*
1245    */
1246   public VisibleContigsIterator getVisContigsIterator(int start,
1247           int end,
1248           boolean useVisibleCoords)
1249   {
1250     int adjstart = start;
1251     int adjend = end;
1252     if (useVisibleCoords)
1253     {
1254       adjstart = visibleToAbsoluteColumn(start);
1255       adjend = visibleToAbsoluteColumn(end);
1256     }
1257
1258     try
1259     {
1260       LOCK.readLock().lock();
1261       return new VisibleContigsIterator(adjstart, adjend, hiddenColumns);
1262     } finally
1263     {
1264       LOCK.readLock().unlock();
1265     }
1266   }
1267 }