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