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