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