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