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.BitSet;
  25 import java.util.Iterator;
  26 import java.util.List;
  27 import java.util.NoSuchElementException;
  28 import java.util.concurrent.locks.ReentrantReadWriteLock;
  29
  30 public class HiddenColumns
  31 {
  32   private static final int HASH_MULTIPLIER = 31;
  33
  34   private static final ReentrantReadWriteLock LOCK = new ReentrantReadWriteLock();
  35
  36   /*
  37    * list of hidden column [start, end] ranges; the list is maintained in
  38    * ascending start column order
  39    */
  40   private ArrayList<int[]> hiddenColumns;
  41
  42   /**
  43    * Constructor
  44    */
  45   public HiddenColumns()
  46   {
  47   }
  48
  49   /**
  50    * Copy constructor
  51    *
  52    * @param copy
  53    */
  54   public HiddenColumns(HiddenColumns copy)
  55   {
  56     try
  57     {
  58       LOCK.writeLock().lock();
  59       if (copy != null)
  60       {
  61         if (copy.hiddenColumns != null)
  62         {
  63           hiddenColumns = copy.copyHiddenRegionsToArrayList(0);
  64         }
  65       }
  66     } finally
  67     {
  68       LOCK.writeLock().unlock();
  69     }
  70   }
  71
  72   /**
  73    * Copy constructor within bounds and with offset. Copies hidden column
  74    * regions fully contained between start and end, and offsets positions by
  75    * subtracting offset.
  76    *
  77    * @param copy
  78    *          HiddenColumns instance to copy from
  79    * @param start
  80    *          lower bound to copy from
  81    * @param end
  82    *          upper bound to copy to
  83    * @param offset
  84    *          offset to subtract from each region boundary position
  85    *
  86    */
  87   public HiddenColumns(HiddenColumns copy, int start, int end, int offset)
  88   {
  89     try
  90     {
  91       LOCK.writeLock().lock();
  92       if (copy != null)
  93       {
  94         hiddenColumns = new ArrayList<>();
  95         Iterator<int[]> it = copy.getBoundedIterator(start, end);
  96         while (it.hasNext())
  97         {
  98           int[] region = it.next();
  99           // still need to check boundaries because iterator returns
 100           // all overlapping regions and we need contained regions
 101           if (region[0] >= start && region[1] <= end)
 102           {
 103             hiddenColumns.add(
 104                     new int[]
 105             { region[0] - offset, region[1] - offset });
 106           }
 107         }
 108       }
 109     } finally
 110     {
 111       LOCK.writeLock().unlock();
 112     }
 113   }
 114
 115   /**
 116    * Output regions data as a string. String is in the format:
 117    * reg0[0]<between>reg0[1]<delimiter>reg1[0]<between>reg1[1] ... regn[1]
 118    *
 119    * @param delimiter
 120    *          string to delimit regions
 121    * @param betweenstring
 122    *          to put between start and end region values
 123    * @return regions formatted according to delimiter and between strings
 124    */
 125   public String regionsToString(String delimiter, String between)
 126   {
 127     try
 128     {
 129       LOCK.readLock().lock();
 130       StringBuilder regionBuilder = new StringBuilder();
 131       Iterator<int[]> it = new LocalBoundedHiddenColsIterator();
 132       while (it.hasNext())
 133       {
 134         int[] range = it.next();
 135         regionBuilder.append(delimiter).append(range[0]).append(between)
 136                   .append(range[1]);
 137         if (!it.hasNext())
 138         {
 139           regionBuilder.deleteCharAt(0);
 140         }
 141       }
 142       return regionBuilder.toString();
 143     } finally
 144     {
 145       LOCK.readLock().unlock();
 146     }
 147   }
 148
 149   /**
 150    * Find the number of hidden columns
 151    *
 152    * @return number of hidden columns
 153    */
 154   public int getSize()
 155   {
 156     try
 157     {
 158       LOCK.readLock().lock();
 159       int size = 0;
 160       Iterator<int[]> it = new LocalBoundedHiddenColsIterator();
 161       while (it.hasNext())
 162       {
 163         int[] range = it.next();
 164         size += range[1] - range[0] + 1;
 165       }
 166
 167       return size;
 168     } finally
 169     {
 170       LOCK.readLock().unlock();
 171     }
 172   }
 173
 174   /**
 175    * Get the number of distinct hidden regions
 176    *
 177    * @return number of regions
 178    */
 179   public int getNumberOfRegions()
 180   {
 181     try
 182     {
 183       LOCK.readLock().lock();
 184       int num = 0;
 185       if (hasHiddenColumns())
 186       {
 187         num = hiddenColumns.size();
 188       }
 189       return num;
 190     } finally
 191     {
 192       LOCK.readLock().unlock();
 193     }
 194   }
 195
 196   @Override
 197   public boolean equals(Object obj)
 198   {
 199     try
 200     {
 201       LOCK.readLock().lock();
 202
 203       if (!(obj instanceof HiddenColumns))
 204       {
 205         return false;
 206       }
 207       HiddenColumns that = (HiddenColumns) obj;
 208
 209       /*
 210        * check hidden columns are either both null, or match
 211        */
 212       if (this.hiddenColumns == null)
 213       {
 214         return (that.hiddenColumns == null);
 215       }
 216       if (that.hiddenColumns == null
 217               || that.hiddenColumns.size() != this.hiddenColumns.size())
 218       {
 219         return false;
 220       }
 221
 222       Iterator<int[]> it = new LocalBoundedHiddenColsIterator();
 223       Iterator<int[]> thatit = that.iterator();
 224       while (it.hasNext())
 225       {
 226         int[] thisRange = it.next();
 227         int[] thatRange = thatit.next();
 228         if (thisRange[0] != thatRange[0] || thisRange[1] != thatRange[1])
 229         {
 230           return false;
 231         }
 232       }
 233       return true;
 234     } finally
 235     {
 236       LOCK.readLock().unlock();
 237     }
 238   }
 239
 240   /**
 241    * Return absolute column index for a visible column index
 242    *
 243    * @param column
 244    *          int column index in alignment view (count from zero)
 245    * @return alignment column index for column
 246    */
 247   public int adjustForHiddenColumns(int column)
 248   {
 249     try
 250     {
 251       LOCK.readLock().lock();
 252       int result = column;
 253
 254       Iterator<int[]> it = new LocalBoundedHiddenColsIterator();
 255       while (it.hasNext())
 256       {
 257         int[] region = it.next();
 258         if (result >= region[0])
 259         {
 260           result += region[1] - region[0] + 1;
 261         }
 262       }
 263
 264       return result;
 265     } finally
 266     {
 267       LOCK.readLock().unlock();
 268     }
 269   }
 270
 271   /**
 272    * Use this method to find out where a column will appear in the visible
 273    * alignment when hidden columns exist. If the column is not visible, then the
 274    * left-most visible column will always be returned.
 275    *
 276    * @param hiddenColumn
 277    *          the column index in the full alignment including hidden columns
 278    * @return the position of the column in the visible alignment
 279    */
 280   public int findColumnPosition(int hiddenColumn)
 281   {
 282     try
 283     {
 284       LOCK.readLock().lock();
 285       int result = hiddenColumn;
 286       int[] region = null;
 287       if (hiddenColumns != null)
 288       {
 289         Iterator<int[]> it = new LocalBoundedHiddenColsIterator(0,
 290                 hiddenColumn);
 291         while (it.hasNext())
 292         {
 293           region = it.next();
 294           if (hiddenColumn > region[1])
 295           {
 296             result -= region[1] + 1 - region[0];
 297           }
 298         }
 299
 300         if (region != null && hiddenColumn >= region[0]
 301                 && hiddenColumn <= region[1])
 302         {
 303           // Here the hidden column is within a region, so
 304           // we want to return the position of region[0]-1, adjusted for any
 305           // earlier hidden columns.
 306           // Calculate the difference between the actual hidden col position
 307           // and region[0]-1, and then subtract from result to convert result
 308           // from
 309           // the adjusted hiddenColumn value to the adjusted region[0]-1 value
 310
 311           // However, if the region begins at 0 we cannot return region[0]-1
 312           // just return 0
 313           if (region[0] == 0)
 314           {
 315             return 0;
 316           }
 317           else
 318           {
 319             return result - (hiddenColumn - region[0] + 1);
 320           }
 321         }
 322       }
 323       return result; // return the shifted position after removing hidden
 324                      // columns.
 325     } finally
 326     {
 327       LOCK.readLock().unlock();
 328     }
 329   }
 330
 331   /**
 332    * Find the visible column which is a given visible number of columns to the
 333    * left of another visible column. i.e. for a startColumn x, the column which
 334    * is distance 1 away will be column x-1.
 335    *
 336    * @param visibleDistance
 337    *          the number of visible columns to offset by
 338    * @param startColumn
 339    *          the column to start from
 340    * @return the position of the column in the visible alignment
 341    */
 342   public int subtractVisibleColumns(int visibleDistance, int startColumn)
 343   {
 344     try
 345     {
 346
 347       LOCK.readLock().lock();
 348       int distance = visibleDistance;
 349
 350       // in case startColumn is in a hidden region, move it to the left
 351       int start = adjustForHiddenColumns(findColumnPosition(startColumn));
 352
 353       // get index of hidden region to left of start
 354       int index = getHiddenIndexLeft(start);
 355       if (index == -1)
 356       {
 357         // no hidden regions to left of startColumn
 358         return start - distance;
 359       }
 360
 361       // walk backwards through the alignment subtracting the counts of visible
 362       // columns from distance
 363       int[] region;
 364       int gap = 0;
 365       int nextstart = start;
 366
 367       while ((index > -1) && (distance - gap > 0))
 368       {
 369         // subtract the gap to right of region from distance
 370         distance -= gap;
 371         start = nextstart;
 372
 373         // calculate the next gap
 374         region = hiddenColumns.get(index);
 375         gap = start - region[1];
 376
 377         // set start to just to left of current region
 378         nextstart = region[0] - 1;
 379         index--;
 380       }
 381
 382       if (distance - gap > 0)
 383       {
 384         // fell out of loop because there are no more hidden regions
 385         distance -= gap;
 386         return nextstart - distance;
 387       }
 388       return start - distance;
 389     } finally
 390     {
 391       LOCK.readLock().unlock();
 392     }
 393
 394   }
 395
 396
 397
 398   /**
 399    * This method returns the rightmost limit of a region of an alignment with
 400    * hidden columns. In otherwords, the next hidden column.
 401    *
 402    * @param index
 403    *          int
 404    */
 405   public int getHiddenBoundaryRight(int alPos)
 406   {
 407     try
 408     {
 409       LOCK.readLock().lock();
 410       if (hiddenColumns != null)
 411       {
 412         int index = 0;
 413         do
 414         {
 415           int[] region = hiddenColumns.get(index);
 416           if (alPos < region[0])
 417           {
 418             return region[0];
 419           }
 420
 421           index++;
 422         } while (index < hiddenColumns.size());
 423       }
 424
 425       return alPos;
 426     } finally
 427     {
 428       LOCK.readLock().unlock();
 429     }
 430
 431   }
 432
 433   /**
 434    * This method returns the leftmost limit of a region of an alignment with
 435    * hidden columns. In otherwords, the previous hidden column.
 436    *
 437    * @param index
 438    *          int
 439    */
 440   public int getHiddenBoundaryLeft(int alPos)
 441   {
 442     try
 443     {
 444       LOCK.readLock().lock();
 445
 446       if (hiddenColumns != null)
 447       {
 448         int index = hiddenColumns.size() - 1;
 449         do
 450         {
 451           int[] region = hiddenColumns.get(index);
 452           if (alPos > region[1])
 453           {
 454             return region[1];
 455           }
 456
 457           index--;
 458         } while (index > -1);
 459       }
 460
 461       return alPos;
 462     } finally
 463     {
 464       LOCK.readLock().unlock();
 465     }
 466   }
 467
 468   /**
 469    * This method returns the index of the hidden region to the left of a column
 470    * position. If the column is in a hidden region it returns the index of the
 471    * region to the left. If there is no hidden region to the left it returns -1.
 472    *
 473    * @param pos
 474    *          int
 475    */
 476   private int getHiddenIndexLeft(int pos)
 477   {
 478     try
 479     {
 480
 481       LOCK.readLock().lock();
 482       if (hiddenColumns != null)
 483       {
 484         int index = hiddenColumns.size() - 1;
 485         do
 486         {
 487           int[] region = hiddenColumns.get(index);
 488           if (pos > region[1])
 489           {
 490             return index;
 491           }
 492
 493           index--;
 494         } while (index > -1);
 495       }
 496
 497       return -1;
 498     } finally
 499     {
 500       LOCK.readLock().unlock();
 501     }
 502
 503   }
 504
 505   /**
 506    * Adds the specified column range to the hidden columns
 507    *
 508    * @param start
 509    * @param end
 510    */
 511   public void hideColumns(int start, int end)
 512   {
 513     boolean wasAlreadyLocked = false;
 514     try
 515     {
 516       // check if the write lock was already locked by this thread,
 517       // as this method can be called internally in loops within HiddenColumns
 518       if (!LOCK.isWriteLockedByCurrentThread())
 519       {
 520         LOCK.writeLock().lock();
 521       }
 522       else
 523       {
 524         wasAlreadyLocked = true;
 525       }
 526
 527       if (hiddenColumns == null)
 528       {
 529         hiddenColumns = new ArrayList<>();
 530       }
 531
 532       /*
 533        * new range follows everything else; check first to avoid looping over whole hiddenColumns collection
 534        */
 535       if (hiddenColumns.isEmpty()
 536               || start > hiddenColumns.get(hiddenColumns.size() - 1)[1])
 537       {
 538         hiddenColumns.add(new int[] { start, end });
 539       }
 540       else
 541       {
 542         /*
 543          * traverse existing hidden ranges and insert / amend / append as
 544          * appropriate
 545          */
 546         boolean added = false;
 547         for (int i = 0; !added && i < hiddenColumns.size(); i++)
 548         {
 549           int[] region = hiddenColumns.get(i);
 550
 551           if (end < region[0] - 1)
 552           {
 553             /*
 554              * insert discontiguous preceding range
 555              */
 556             hiddenColumns.add(i, new int[] { start, end });
 557             added = true;
 558           }
 559           else if (end <= region[1])
 560           {
 561             /*
 562              * new range overlaps existing, or is contiguous preceding it - adjust
 563              * start column
 564              */
 565             region[0] = Math.min(region[0], start);
 566             added = true;
 567           }
 568           else if (start <= region[1] + 1)
 569           {
 570             /*
 571              * new range overlaps existing, or is contiguous following it - adjust
 572              * start and end columns
 573              */
 574             region[0] = Math.min(region[0], start);
 575             region[1] = Math.max(region[1], end);
 576
 577             /*
 578              * also update or remove any subsequent ranges
 579              * that are overlapped
 580              */
 581             while (i < hiddenColumns.size() - 1)
 582             {
 583               int[] nextRegion = hiddenColumns.get(i + 1);
 584               if (nextRegion[0] > end + 1)
 585               {
 586                 /*
 587                  * gap to next hidden range - no more to update
 588                  */
 589                 break;
 590               }
 591               region[1] = Math.max(nextRegion[1], end);
 592               hiddenColumns.remove(i + 1);
 593             }
 594             added = true;
 595           }
 596         } // for
 597       }
 598     } finally
 599     {
 600       if (!wasAlreadyLocked)
 601       {
 602         LOCK.writeLock().unlock();
 603       }
 604     }
 605   }
 606
 607   public boolean isVisible(int column)
 608   {
 609     try
 610     {
 611       LOCK.readLock().lock();
 612
 613       Iterator<int[]> it = new LocalBoundedHiddenColsIterator();
 614       while (it.hasNext())
 615       {
 616         int[] region = it.next();
 617         if (column >= region[0] && column <= region[1])
 618         {
 619           return false;
 620         }
 621       }
 622
 623       return true;
 624     } finally
 625     {
 626       LOCK.readLock().unlock();
 627     }
 628   }
 629
 630   private ArrayList<int[]> copyHiddenRegionsToArrayList(int startIndex)
 631   {
 632     int size = 0;
 633     if (hiddenColumns != null)
 634     {
 635       size = hiddenColumns.size();
 636     }
 637     ArrayList<int[]> copy = new ArrayList<>(size);
 638
 639     for (int i = startIndex, j = size; i < j; i++)
 640     {
 641       int[] rh;
 642       int[] cp;
 643       rh = hiddenColumns.get(i);
 644       if (rh != null)
 645       {
 646         cp = new int[rh.length];
 647         System.arraycopy(rh, 0, cp, 0, rh.length);
 648         copy.add(cp);
 649       }
 650     }
 651
 652     return copy;
 653   }
 654
 655   public String[] getVisibleSequenceStrings(int start, int end,
 656           SequenceI[] seqs)
 657   {
 658     try
 659     {
 660       LOCK.readLock().lock();
 661       int iSize = seqs.length;
 662       String[] selections = new String[iSize];
 663       if (hiddenColumns != null && hiddenColumns.size() > 0)
 664       {
 665         for (int i = 0; i < iSize; i++)
 666         {
 667           StringBuffer visibleSeq = new StringBuffer();
 668
 669           Iterator<int[]> blocks = new VisibleContigsIterator(start,
 670                   end + 1, false);
 671
 672           while (blocks.hasNext())
 673           {
 674             int[] block = blocks.next();
 675             if (blocks.hasNext())
 676             {
 677               visibleSeq
 678                       .append(seqs[i].getSequence(block[0], block[1] + 1));
 679             }
 680             else
 681             {
 682               visibleSeq
 683                       .append(seqs[i].getSequence(block[0], block[1]));
 684             }
 685           }
 686
 687           selections[i] = visibleSeq.toString();
 688         }
 689       }
 690       else
 691       {
 692         for (int i = 0; i < iSize; i++)
 693         {
 694           selections[i] = seqs[i].getSequenceAsString(start, end);
 695         }
 696       }
 697
 698       return selections;
 699     } finally
 700     {
 701       LOCK.readLock().unlock();
 702     }
 703   }
 704
 705   /**
 706    * Locate the first position visible for this sequence. If seq isn't visible
 707    * then return the position of the left side of the hidden boundary region.
 708    *
 709    * @param seq
 710    *          sequence to find position for
 711    * @return visible start position
 712    */
 713   public int locateVisibleStartOfSequence(SequenceI seq)
 714   {
 715     try
 716     {
 717       LOCK.readLock().lock();
 718       int start = 0;
 719
 720       if (hiddenColumns == null || hiddenColumns.size() == 0)
 721       {
 722         return seq.findIndex(seq.getStart()) - 1;
 723       }
 724
 725       // Simply walk along the sequence whilst watching for hidden column
 726       // boundaries
 727       Iterator<int[]> regions = new LocalBoundedHiddenColsIterator();
 728       int hideStart = seq.getLength();
 729       int hideEnd = -1;
 730       int visPrev = 0;
 731       int visNext = 0;
 732       boolean foundStart = false;
 733
 734       // step through the non-gapped positions of the sequence
 735       for (int i = seq.getStart(); i <= seq.getEnd() && (!foundStart); i++)
 736       {
 737         // get alignment position of this residue in the sequence
 738         int p = seq.findIndex(i) - 1;
 739
 740         // update hidden region start/end
 741         while (hideEnd < p && regions.hasNext())
 742         {
 743           int[] region = regions.next();
 744           visPrev = visNext;
 745           visNext += region[0] - visPrev;
 746           hideStart = region[0];
 747           hideEnd = region[1];
 748         }
 749         if (hideEnd < p)
 750         {
 751           hideStart = seq.getLength();
 752         }
 753         // update visible boundary for sequence
 754         if (p < hideStart)
 755         {
 756           start = p;
 757           foundStart = true;
 758         }
 759       }
 760
 761       if (foundStart)
 762       {
 763         return findColumnPosition(start);
 764       }
 765       // otherwise, sequence was completely hidden
 766       return visPrev;
 767     } finally
 768     {
 769       LOCK.readLock().unlock();
 770     }
 771   }
 772
 773   /**
 774    * delete any columns in alignmentAnnotation that are hidden (including
 775    * sequence associated annotation).
 776    *
 777    * @param alignmentAnnotation
 778    */
 779   public void makeVisibleAnnotation(AlignmentAnnotation alignmentAnnotation)
 780   {
 781     makeVisibleAnnotation(0, alignmentAnnotation.annotations.length,
 782             alignmentAnnotation);
 783   }
 784
 785   /**
 786    * delete any columns in alignmentAnnotation that are hidden (including
 787    * sequence associated annotation).
 788    *
 789    * @param start
 790    *          remove any annotation to the right of this column
 791    * @param end
 792    *          remove any annotation to the left of this column
 793    * @param alignmentAnnotation
 794    *          the annotation to operate on
 795    */
 796   public void makeVisibleAnnotation(int start, int end,
 797           AlignmentAnnotation alignmentAnnotation)
 798   {
 799     try
 800     {
 801       LOCK.readLock().lock();
 802
 803       int startFrom = start;
 804       int endAt = end;
 805
 806       if (alignmentAnnotation.annotations != null)
 807       {
 808         if (hiddenColumns != null && hiddenColumns.size() > 0)
 809         {
 810           removeHiddenAnnotation(startFrom, endAt, alignmentAnnotation);
 811         }
 812         else
 813         {
 814           alignmentAnnotation.restrict(startFrom, endAt);
 815         }
 816       }
 817     } finally
 818     {
 819       LOCK.readLock().unlock();
 820     }
 821   }
 822
 823   private void removeHiddenAnnotation(int start, int end,
 824           AlignmentAnnotation alignmentAnnotation)
 825   {
 826     // mangle the alignmentAnnotation annotation array
 827     ArrayList<Annotation[]> annels = new ArrayList<>();
 828     Annotation[] els = null;
 829
 830     int w = 0;
 831
 832     Iterator<int[]> blocks = new VisibleContigsIterator(start, end + 1,
 833             false);
 834
 835     int copylength;
 836     int annotationLength;
 837     while (blocks.hasNext())
 838     {
 839       int[] block = blocks.next();
 840       annotationLength = block[1] - block[0] + 1;
 841
 842       if (blocks.hasNext())
 843       {
 844         // copy just the visible segment of the annotation row
 845         copylength = annotationLength;
 846       }
 847       else
 848       {
 849         if (annotationLength + block[0] <= alignmentAnnotation.annotations.length)
 850         {
 851           // copy just the visible segment of the annotation row
 852           copylength = annotationLength;
 853         }
 854         else
 855         {
 856           // copy to the end of the annotation row
 857           copylength = alignmentAnnotation.annotations.length - block[0];
 858         }
 859       }
 860
 861       els = new Annotation[annotationLength];
 862       annels.add(els);
 863       System.arraycopy(alignmentAnnotation.annotations, block[0], els, 0,
 864               copylength);
 865       w += annotationLength;
 866     }
 867
 868     if (w != 0)
 869     {
 870       alignmentAnnotation.annotations = new Annotation[w];
 871
 872       w = 0;
 873       for (Annotation[] chnk : annels)
 874       {
 875         System.arraycopy(chnk, 0, alignmentAnnotation.annotations, w,
 876                 chnk.length);
 877         w += chnk.length;
 878       }
 879     }
 880   }
 881
 882   /**
 883    *
 884    * @return true if there are columns hidden
 885    */
 886   public boolean hasHiddenColumns()
 887   {
 888     try
 889     {
 890       LOCK.readLock().lock();
 891       return hiddenColumns != null && hiddenColumns.size() > 0;
 892     } finally
 893     {
 894       LOCK.readLock().unlock();
 895     }
 896   }
 897
 898   /**
 899    *
 900    * @return true if there are more than one set of columns hidden
 901    */
 902   public boolean hasManyHiddenColumns()
 903   {
 904     try
 905     {
 906       LOCK.readLock().lock();
 907       return hiddenColumns != null && hiddenColumns.size() > 1;
 908     } finally
 909     {
 910       LOCK.readLock().unlock();
 911     }
 912   }
 913
 914   /**
 915    * mark the columns corresponding to gap characters as hidden in the column
 916    * selection
 917    *
 918    * @param sr
 919    */
 920   public void hideInsertionsFor(SequenceI sr)
 921   {
 922     try
 923     {
 924       LOCK.writeLock().lock();
 925       List<int[]> inserts = sr.getInsertions();
 926       for (int[] r : inserts)
 927       {
 928         hideColumns(r[0], r[1]);
 929       }
 930     } finally
 931     {
 932       LOCK.writeLock().unlock();
 933     }
 934   }
 935
 936   /**
 937    * Unhides, and adds to the selection list, all hidden columns
 938    */
 939   public void revealAllHiddenColumns(ColumnSelection sel)
 940   {
 941     try
 942     {
 943       LOCK.writeLock().lock();
 944       Iterator<int[]> it = new LocalBoundedHiddenColsIterator();
 945       while (it.hasNext())
 946       {
 947         int[] region = it.next();
 948         for (int j = region[0]; j < region[1] + 1; j++)
 949         {
 950           sel.addElement(j);
 951         }
 952       }
 953
 954       hiddenColumns = null;
 955     } finally
 956     {
 957       LOCK.writeLock().unlock();
 958     }
 959   }
 960
 961   /**
 962    * Reveals, and marks as selected, the hidden column range with the given
 963    * start column
 964    *
 965    * @param start
 966    */
 967   public void revealHiddenColumns(int start, ColumnSelection sel)
 968   {
 969     try
 970     {
 971       LOCK.writeLock().lock();
 972       Iterator<int[]> it = new LocalBoundedHiddenColsIterator();
 973       while (it.hasNext())
 974       {
 975         int[] region = it.next();
 976         if (start == region[0])
 977         {
 978           for (int j = region[0]; j < region[1] + 1; j++)
 979           {
 980             sel.addElement(j);
 981           }
 982
 983           hiddenColumns.remove(region);
 984           break;
 985         }
 986         else if (start < region[0])
 987         {
 988           break; // passed all possible matching regions
 989         }
 990       }
 991
 992       if (hiddenColumns.size() == 0)
 993       {
 994         hiddenColumns = null;
 995       }
 996     } finally
 997     {
 998       LOCK.writeLock().unlock();
 999     }
1000   }
1001
1002   /**
1003    * Add gaps into the sequences aligned to profileseq under the given
1004    * AlignmentView
1005    *
1006    * @param profileseq
1007    * @param al
1008    *          - alignment to have gaps inserted into it
1009    * @param input
1010    *          - alignment view where sequence corresponding to profileseq is
1011    *          first entry
1012    * @return new HiddenColumns for new alignment view, with insertions into
1013    *         profileseq marked as hidden.
1014    */
1015   public static HiddenColumns propagateInsertions(SequenceI profileseq,
1016           AlignmentI al, AlignmentView input)
1017   {
1018     int profsqpos = 0;
1019
1020     char gc = al.getGapCharacter();
1021     Object[] alandhidden = input.getAlignmentAndHiddenColumns(gc);
1022     HiddenColumns nview = (HiddenColumns) alandhidden[1];
1023     SequenceI origseq = ((SequenceI[]) alandhidden[0])[profsqpos];
1024     nview.propagateInsertions(profileseq, al, origseq);
1025     return nview;
1026   }
1027
1028   /**
1029    *
1030    * @param profileseq
1031    *          - sequence in al which corresponds to origseq
1032    * @param al
1033    *          - alignment which is to have gaps inserted into it
1034    * @param origseq
1035    *          - sequence corresponding to profileseq which defines gap map for
1036    *          modifying al
1037    */
1038   private void propagateInsertions(SequenceI profileseq, AlignmentI al,
1039           SequenceI origseq)
1040   {
1041     try
1042     {
1043       LOCK.writeLock().lock();
1044
1045       char gc = al.getGapCharacter();
1046
1047       // take the set of hidden columns, and the set of gaps in origseq,
1048       // and remove all the hidden gaps from hiddenColumns
1049
1050       // first get the gaps as a Bitset
1051       BitSet gaps = origseq.gapBitset();
1052
1053       // now calculate hidden ^ not(gap)
1054       BitSet hidden = new BitSet();
1055       markHiddenRegions(hidden);
1056       hidden.andNot(gaps);
1057       hiddenColumns = null;
1058       this.hideMarkedBits(hidden);
1059
1060       // for each sequence in the alignment, except the profile sequence,
1061       // insert gaps corresponding to each hidden region
1062       // but where each hidden column region is shifted backwards by the number
1063       // of
1064       // preceding visible gaps
1065       // update hidden columns at the same time
1066       Iterator<int[]> regions = new LocalBoundedHiddenColsIterator();
1067       ArrayList<int[]> newhidden = new ArrayList<>();
1068
1069       int numGapsBefore = 0;
1070       int gapPosition = 0;
1071       while (regions.hasNext())
1072       {
1073         // get region coordinates accounting for gaps
1074         // we can rely on gaps not being *in* hidden regions because we already
1075         // removed those
1076         int[] region = regions.next();
1077         while (gapPosition < region[0])
1078         {
1079           gapPosition++;
1080           if (gaps.get(gapPosition))
1081           {
1082             numGapsBefore++;
1083           }
1084         }
1085
1086         int left = region[0] - numGapsBefore;
1087         int right = region[1] - numGapsBefore;
1088         newhidden.add(new int[] { left, right });
1089
1090         // make a string with number of gaps = length of hidden region
1091         StringBuffer sb = new StringBuffer();
1092         for (int s = 0; s < right - left + 1; s++)
1093         {
1094           sb.append(gc);
1095         }
1096         padGaps(sb, left, profileseq, al);
1097
1098       }
1099       hiddenColumns = newhidden;
1100     } finally
1101     {
1102       LOCK.writeLock().unlock();
1103     }
1104   }
1105
1106   /**
1107    * Pad gaps in all sequences in alignment except profileseq
1108    *
1109    * @param sb
1110    *          gap string to insert
1111    * @param left
1112    *          position to insert at
1113    * @param profileseq
1114    *          sequence not to pad
1115    * @param al
1116    *          alignment to pad sequences in
1117    */
1118   private void padGaps(StringBuffer sb, int pos, SequenceI profileseq,
1119           AlignmentI al)
1120   {
1121     // loop over the sequences and pad with gaps where required
1122     for (int s = 0, ns = al.getHeight(); s < ns; s++)
1123     {
1124       SequenceI sqobj = al.getSequenceAt(s);
1125       if (sqobj != profileseq)
1126       {
1127         String sq = al.getSequenceAt(s).getSequenceAsString();
1128         if (sq.length() <= pos)
1129         {
1130           // pad sequence
1131           int diff = pos - sq.length() - 1;
1132           if (diff > 0)
1133           {
1134             // pad gaps
1135             sq = sq + sb;
1136             while ((diff = pos - sq.length() - 1) > 0)
1137             {
1138               if (diff >= sb.length())
1139               {
1140                 sq += sb.toString();
1141               }
1142               else
1143               {
1144                 char[] buf = new char[diff];
1145                 sb.getChars(0, diff, buf, 0);
1146                 sq += buf.toString();
1147               }
1148             }
1149           }
1150           sq += sb.toString();
1151         }
1152         else
1153         {
1154           al.getSequenceAt(s).setSequence(
1155                   sq.substring(0, pos) + sb.toString() + sq.substring(pos));
1156         }
1157       }
1158     }
1159   }
1160
1161   /**
1162    * Returns a hashCode built from hidden column ranges
1163    */
1164   @Override
1165   public int hashCode()
1166   {
1167     try
1168     {
1169       LOCK.readLock().lock();
1170       int hashCode = 1;
1171       Iterator<int[]> it = new LocalBoundedHiddenColsIterator();
1172       while (it.hasNext())
1173       {
1174         int[] hidden = it.next();
1175         hashCode = HASH_MULTIPLIER * hashCode + hidden[0];
1176         hashCode = HASH_MULTIPLIER * hashCode + hidden[1];
1177       }
1178       return hashCode;
1179     } finally
1180     {
1181       LOCK.readLock().unlock();
1182     }
1183   }
1184
1185   /**
1186    * Hide columns corresponding to the marked bits
1187    *
1188    * @param inserts
1189    *          - columns map to bits starting from zero
1190    */
1191   public void hideMarkedBits(BitSet inserts)
1192   {
1193     try
1194     {
1195       LOCK.writeLock().lock();
1196       for (int firstSet = inserts
1197               .nextSetBit(0), lastSet = 0; firstSet >= 0; firstSet = inserts
1198                       .nextSetBit(lastSet))
1199       {
1200         lastSet = inserts.nextClearBit(firstSet);
1201         hideColumns(firstSet, lastSet - 1);
1202       }
1203     } finally
1204     {
1205       LOCK.writeLock().unlock();
1206     }
1207   }
1208
1209   /**
1210    *
1211    * @param inserts
1212    *          BitSet where hidden columns will be marked
1213    */
1214   public void markHiddenRegions(BitSet inserts)
1215   {
1216     try
1217     {
1218       LOCK.readLock().lock();
1219       if (hiddenColumns == null)
1220       {
1221         return;
1222       }
1223       Iterator<int[]> it = new LocalBoundedHiddenColsIterator();
1224       while (it.hasNext())
1225       {
1226         int[] range = it.next();
1227         inserts.set(range[0], range[1] + 1);
1228       }
1229     } finally
1230     {
1231       LOCK.readLock().unlock();
1232     }
1233   }
1234
1235   /**
1236    * Calculate the visible start and end index of an alignment.
1237    *
1238    * @param width
1239    *          full alignment width
1240    * @return integer array where: int[0] = startIndex, and int[1] = endIndex
1241    */
1242   public int[] getVisibleStartAndEndIndex(int width)
1243   {
1244     try
1245     {
1246       LOCK.readLock().lock();
1247       int[] alignmentStartEnd = new int[] { 0, width - 1 };
1248       int startPos = alignmentStartEnd[0];
1249       int endPos = alignmentStartEnd[1];
1250
1251       int[] lowestRange = new int[] { -1, -1 };
1252       int[] higestRange = new int[] { -1, -1 };
1253
1254       if (hiddenColumns == null)
1255       {
1256         return new int[] { startPos, endPos };
1257       }
1258
1259       Iterator<int[]> it = new LocalBoundedHiddenColsIterator();
1260       while (it.hasNext())
1261       {
1262         int[] range = it.next();
1263         lowestRange = (range[0] <= startPos) ? range : lowestRange;
1264         higestRange = (range[1] >= endPos) ? range : higestRange;
1265       }
1266
1267       if (lowestRange[0] == -1 && lowestRange[1] == -1)
1268       {
1269         startPos = alignmentStartEnd[0];
1270       }
1271       else
1272       {
1273         startPos = lowestRange[1] + 1;
1274       }
1275
1276       if (higestRange[0] == -1 && higestRange[1] == -1)
1277       {
1278         endPos = alignmentStartEnd[1];
1279       }
1280       else
1281       {
1282         endPos = higestRange[0] - 1;
1283       }
1284       return new int[] { startPos, endPos };
1285     } finally
1286     {
1287       LOCK.readLock().unlock();
1288     }
1289
1290   }
1291
1292   /**
1293    * Finds the hidden region (if any) which starts or ends at res
1294    *
1295    * @param res
1296    *          visible residue position, unadjusted for hidden columns
1297    * @return region as [start,end] or null if no matching region is found
1298    */
1299   public int[] getRegionWithEdgeAtRes(int res)
1300   {
1301     try
1302     {
1303       LOCK.readLock().lock();
1304       int adjres = adjustForHiddenColumns(res);
1305
1306       int[] reveal = null;
1307       Iterator<int[]> it = new LocalBoundedHiddenColsIterator(adjres - 2,
1308               adjres + 2);
1309       while (it.hasNext())
1310       {
1311         int[] region = it.next();
1312         if (adjres + 1 == region[0] || adjres - 1 == region[1])
1313         {
1314           reveal = region;
1315           break;
1316         }
1317       }
1318       return reveal;
1319     } finally
1320     {
1321       LOCK.readLock().unlock();
1322     }
1323   }
1324
1325   /**
1326    * Return an iterator over the hidden regions
1327    */
1328   public Iterator<int[]> iterator()
1329   {
1330     return new BoundedHiddenColsIterator();
1331   }
1332
1333   /**
1334    * Return a bounded iterator over the hidden regions
1335    *
1336    * @param start
1337    *          position to start from (inclusive, absolute column position)
1338    * @param end
1339    *          position to end at (inclusive, absolute column position)
1340    * @return
1341    */
1342   public Iterator<int[]> getBoundedIterator(int start, int end)
1343   {
1344     return new BoundedHiddenColsIterator(start, end);
1345   }
1346
1347   /**
1348    * Return a bounded iterator over the *visible* start positions of hidden
1349    * regions
1350    *
1351    * @param start
1352    *          position to start from (inclusive, visible column position)
1353    * @param end
1354    *          position to end at (inclusive, visible column position)
1355    */
1356   public Iterator<Integer> getBoundedStartIterator(int start, int end)
1357   {
1358     return new BoundedStartRegionIterator(start, end, true);
1359   }
1360
1361   /**
1362    * Return an iterator over visible *columns* (not regions) between the given
1363    * start and end boundaries
1364    *
1365    * @param start
1366    *          first column (inclusive)
1367    * @param end
1368    *          last column (inclusive)
1369    */
1370   public Iterator<Integer> getVisibleColsIterator(int start, int end)
1371   {
1372     return new VisibleColsIterator(start, end);
1373   }
1374
1375   /**
1376    * return an iterator over visible segments between the given start and end
1377    * boundaries
1378    *
1379    * @param start
1380    *          (first column inclusive from 0)
1381    * @param end
1382    *          (last column - not inclusive)
1383    */
1384   public Iterator<int[]> getVisContigsIterator(int start, int end)
1385   {
1386     // return new VisibleBlocksIterator(start, end, true)
1387     return new VisibleContigsIterator(start, end, true);
1388   }
1389
1390   /**
1391    * return an iterator over visible segments between the given start and end
1392    * boundaries
1393    *
1394    * @param start
1395    *          (first column - inclusive from 0)
1396    * @param end
1397    *          (last column - inclusive)
1398    * @param useVisibleCoords
1399    *          if true, start and end are visible column positions, not absolute
1400    *          positions
1401    */
1402   public Iterator<int[]> getVisibleBlocksIterator(int start, int end,
1403           boolean useVisibleCoords)
1404   {
1405     if (useVisibleCoords)
1406     {
1407       // TODO
1408       // we should really just convert start and end here with
1409       // adjustForHiddenColumns
1410       // and then create a VisibleContigsIterator
1411       // but without a cursor this will be horribly slow in some situations
1412       // ... so until then...
1413       return new VisibleBlocksVisBoundsIterator(start, end, true);
1414     }
1415     else
1416     {
1417       return new VisibleContigsIterator(start, end - 1, true);
1418     }
1419   }
1420
1421   /**
1422    * A local iterator which iterates over hidden column regions in a range.
1423    * Works with the actual hidden columns collection (so locking before use may
1424    * be required).
1425    */
1426   private class LocalBoundedHiddenColsIterator implements Iterator<int[]>
1427   {
1428     private int start; // start position to iterate from
1429
1430     private int end; // end position to iterate to
1431
1432     // current index in hiddenColumns
1433     private int currentPosition = 0;
1434
1435     // current column in hiddenColumns
1436     private int[] nextRegion = null;
1437
1438     LocalBoundedHiddenColsIterator(int lowerBound, int upperBound)
1439     {
1440       init(lowerBound, upperBound);
1441     }
1442
1443     LocalBoundedHiddenColsIterator()
1444     {
1445       if (hiddenColumns != null)
1446       {
1447         int last = hiddenColumns.get(hiddenColumns.size() - 1)[1];
1448         init(0, last);
1449       }
1450       else
1451       {
1452         init(0, 0);
1453       }
1454     }
1455
1456     /**
1457      * Construct an iterator over hiddenColums bounded at
1458      * [lowerBound,upperBound]
1459      *
1460      * @param lowerBound
1461      *          lower bound to iterate from
1462      * @param upperBound
1463      *          upper bound to iterate to
1464      * @param useCopyCols
1465      *          whether to make a local copy of hiddenColumns for iteration (set
1466      *          to true if calling from outwith the HiddenColumns class)
1467      */
1468     private void init(int lowerBound, int upperBound)
1469     {
1470       start = lowerBound;
1471       end = upperBound;
1472
1473       if (hiddenColumns != null)
1474       {
1475         // iterate until a region overlaps with [start,end]
1476         currentPosition = 0;
1477         while ((currentPosition < hiddenColumns.size())
1478                 && (hiddenColumns.get(currentPosition)[1] < start))
1479         {
1480           currentPosition++;
1481         }
1482         if (currentPosition < hiddenColumns.size())
1483         {
1484           nextRegion = hiddenColumns.get(currentPosition);
1485         }
1486       }
1487     }
1488
1489     @Override
1490     public boolean hasNext()
1491     {
1492       return (hiddenColumns != null) && (nextRegion != null)
1493               && (nextRegion[0] <= end);
1494     }
1495
1496     @Override
1497     public int[] next()
1498     {
1499       int[] region = nextRegion;
1500       currentPosition++;
1501       if (currentPosition < hiddenColumns.size())
1502       {
1503         nextRegion = hiddenColumns.get(currentPosition);
1504       }
1505       else
1506       {
1507         nextRegion = null;
1508       }
1509       return region;
1510     }
1511
1512   }
1513
1514   /**
1515    * An iterator which iterates over hidden column regions in a range. Works
1516    * with a copy of the hidden columns collection.
1517    */
1518   private class BoundedHiddenColsIterator implements Iterator<int[]>
1519   {
1520     private int start; // start position to iterate from
1521
1522     private int end; // end position to iterate to
1523
1524     // current index in hiddenColumns
1525     private int currentPosition = 0;
1526
1527     // current column in hiddenColumns
1528     private int[] currentRegion;
1529
1530     // local copy or reference to hiddenColumns
1531     private List<int[]> localHidden;
1532
1533     BoundedHiddenColsIterator()
1534     {
1535       if (hiddenColumns != null)
1536       {
1537         int last = hiddenColumns.get(hiddenColumns.size() - 1)[1];
1538         init(0, last);
1539       }
1540       else
1541       {
1542         init(0, 0);
1543       }
1544     }
1545
1546     /**
1547      * Construct an iterator over hiddenColums bounded at
1548      * [lowerBound,upperBound]
1549      *
1550      * @param lowerBound
1551      *          lower bound to iterate from
1552      * @param upperBound
1553      *          upper bound to iterate to
1554      */
1555     BoundedHiddenColsIterator(int lowerBound, int upperBound)
1556     {
1557       init(lowerBound, upperBound);
1558     }
1559
1560     /**
1561      * Construct an iterator over hiddenColums bounded at
1562      * [lowerBound,upperBound]
1563      *
1564      * @param lowerBound
1565      *          lower bound to iterate from
1566      * @param upperBound
1567      *          upper bound to iterate to
1568      */
1569     private void init(int lowerBound, int upperBound)
1570     {
1571       start = lowerBound;
1572       end = upperBound;
1573
1574       try
1575       {
1576         LOCK.readLock().lock();
1577
1578         if (hiddenColumns != null)
1579         {
1580           localHidden = new ArrayList<>();
1581
1582           // iterate until a region overlaps with [start,end]
1583           int i = 0;
1584           while ((i < hiddenColumns.size())
1585                   && (hiddenColumns.get(i)[1] < start))
1586           {
1587             i++;
1588           }
1589
1590           // iterate from start to end, adding each hidden region. Positions are
1591           // absolute, and all regions which *overlap* [start,end] are added.
1592           while (i < hiddenColumns.size()
1593                   && (hiddenColumns.get(i)[0] <= end))
1594           {
1595             int[] rh = hiddenColumns.get(i);
1596             int[] cp = new int[2];
1597             System.arraycopy(rh, 0, cp, 0, rh.length);
1598             localHidden.add(cp);
1599             i++;
1600           }
1601         }
1602       }
1603       finally
1604       {
1605         LOCK.readLock().unlock();
1606       }
1607     }
1608
1609     @Override
1610     public boolean hasNext()
1611     {
1612       return (localHidden != null)
1613               && (currentPosition < localHidden.size());
1614     }
1615
1616     @Override
1617     public int[] next()
1618     {
1619       currentRegion = localHidden.get(currentPosition);
1620       currentPosition++;
1621       return currentRegion;
1622     }
1623   }
1624
1625   /**
1626    * An iterator which iterates over visible start positions of hidden column
1627    * regions in a range.
1628    */
1629   private class BoundedStartRegionIterator implements Iterator<Integer>
1630   {
1631     // start position to iterate from
1632     private int start;
1633
1634     // end position to iterate to
1635     private int end;
1636
1637     // current index in hiddenColumns
1638     private int currentPosition = 0;
1639
1640     // local copy or reference to hiddenColumns
1641     private List<Integer> positions = null;
1642
1643     /**
1644      * Construct an iterator over hiddenColums bounded at
1645      * [lowerBound,upperBound]
1646      *
1647      * @param lowerBound
1648      *          lower bound to iterate from
1649      * @param upperBound
1650      *          upper bound to iterate to
1651      * @param useCopyCols
1652      *          whether to make a local copy of hiddenColumns for iteration (set
1653      *          to true if calling from outwith the HiddenColumns class)
1654      */
1655     BoundedStartRegionIterator(int lowerBound, int upperBound,
1656             boolean useCopy)
1657     {
1658       start = lowerBound;
1659       end = upperBound;
1660
1661       try
1662       {
1663         if (useCopy)
1664         {
1665           // assume that if useCopy is false the calling code has locked
1666           // hiddenColumns
1667           LOCK.readLock().lock();
1668         }
1669
1670         if (hiddenColumns != null)
1671         {
1672           positions = new ArrayList<>(hiddenColumns.size());
1673
1674           // navigate to start, keeping count of hidden columns
1675           int i = 0;
1676           int hiddenSoFar = 0;
1677           while ((i < hiddenColumns.size())
1678                   && (hiddenColumns.get(i)[0] < start + hiddenSoFar))
1679           {
1680             int[] region = hiddenColumns.get(i);
1681             hiddenSoFar += region[1] - region[0] + 1;
1682             i++;
1683           }
1684
1685           // iterate from start to end, adding start positions of each
1686           // hidden region. Positions are visible columns count, not absolute
1687           while (i < hiddenColumns.size()
1688                   && (hiddenColumns.get(i)[0] <= end + hiddenSoFar))
1689           {
1690             int[] region = hiddenColumns.get(i);
1691             positions.add(region[0] - hiddenSoFar);
1692             hiddenSoFar += region[1] - region[0] + 1;
1693             i++;
1694           }
1695         }
1696         else
1697         {
1698           positions = new ArrayList<>();
1699         }
1700       } finally
1701       {
1702         if (useCopy)
1703         {
1704           LOCK.readLock().unlock();
1705         }
1706       }
1707     }
1708
1709     @Override
1710     public boolean hasNext()
1711     {
1712       return (currentPosition < positions.size());
1713     }
1714
1715     /**
1716      * Get next hidden region start position
1717      *
1718      * @return the start position in *visible* coordinates
1719      */
1720     @Override
1721     public Integer next()
1722     {
1723       int result = positions.get(currentPosition);
1724       currentPosition++;
1725       return result;
1726     }
1727   }
1728
1729   /**
1730    * Iterator over the visible *columns* (not regions) as determined by the set
1731    * of hidden columns. Uses a local copy of hidden columns.
1732    *
1733    * @author kmourao
1734    *
1735    */
1736   private class VisibleColsIterator implements Iterator<Integer>
1737   {
1738     private int last;
1739
1740     private int current;
1741
1742     private int next;
1743
1744     private List<int[]> localHidden = new ArrayList<>();
1745
1746     private int nexthiddenregion;
1747
1748     VisibleColsIterator(int firstcol, int lastcol)
1749     {
1750       last = lastcol;
1751       current = firstcol;
1752       next = firstcol;
1753       nexthiddenregion = 0;
1754
1755       LOCK.readLock().lock();
1756
1757       if (hiddenColumns != null)
1758       {
1759         int i = 0;
1760         for (i = 0; i < hiddenColumns.size()
1761                 && (current <= hiddenColumns.get(i)[0]); ++i)
1762         {
1763           if (current >= hiddenColumns.get(i)[0]
1764                   && current <= hiddenColumns.get(i)[1])
1765           {
1766             // current is hidden, move to right
1767             current = hiddenColumns.get(i)[1] + 1;
1768             next = current;
1769             nexthiddenregion = i + 1;
1770           }
1771         }
1772
1773         for (i = hiddenColumns.size() - 1; i >= 0
1774                 && (last >= hiddenColumns.get(i)[1]); --i)
1775         {
1776           if (last >= hiddenColumns.get(i)[0]
1777                   && last <= hiddenColumns.get(i)[1])
1778           {
1779             // last is hidden, move to left
1780             last = hiddenColumns.get(i)[0] - 1;
1781           }
1782         }
1783
1784         // make a local copy of the bit we need
1785         i = nexthiddenregion;
1786         while (i < hiddenColumns.size() && hiddenColumns.get(i)[0] <= last)
1787         {
1788           int[] region = new int[] { hiddenColumns.get(i)[0],
1789               hiddenColumns.get(i)[1] };
1790           localHidden.add(region);
1791           i++;
1792         }
1793       }
1794
1795       LOCK.readLock().unlock();
1796     }
1797
1798     @Override
1799     public boolean hasNext()
1800     {
1801       return next <= last;
1802     }
1803
1804     @Override
1805     public Integer next()
1806     {
1807       if (next > last)
1808       {
1809         throw new NoSuchElementException();
1810       }
1811       current = next;
1812       if ((localHidden != null)
1813               && (nexthiddenregion < localHidden.size()))
1814       {
1815         // still some more hidden regions
1816         if (next + 1 < localHidden.get(nexthiddenregion)[0])
1817         {
1818           // next+1 is still before the next hidden region
1819           next++;
1820         }
1821         else if ((next + 1 >= localHidden.get(nexthiddenregion)[0])
1822                 && (next + 1 <= localHidden.get(nexthiddenregion)[1]))
1823         {
1824           // next + 1 is in the next hidden region
1825           next = localHidden.get(nexthiddenregion)[1] + 1;
1826           nexthiddenregion++;
1827         }
1828       }
1829       else
1830       {
1831         // finished with hidden regions, just increment normally
1832         next++;
1833       }
1834       return current;
1835     }
1836
1837     @Override
1838     public void remove()
1839     {
1840       throw new UnsupportedOperationException();
1841     }
1842   }
1843
1844   /**
1845    * An iterator which iterates over visible regions in a range.
1846    */
1847   private class VisibleContigsIterator implements Iterator<int[]>
1848   {
1849     private List<int[]> vcontigs = new ArrayList<>();
1850
1851     private int currentPosition = 0;
1852
1853     VisibleContigsIterator(int start, int end, boolean usecopy)
1854     {
1855       try
1856       {
1857         if (usecopy)
1858         {
1859           LOCK.readLock().lock();
1860         }
1861
1862         if (hiddenColumns != null && hiddenColumns.size() > 0)
1863         {
1864           int vstart = start;
1865           int hideStart;
1866           int hideEnd;
1867
1868           for (int[] region : hiddenColumns)
1869           {
1870             hideStart = region[0];
1871             hideEnd = region[1];
1872
1873             // navigate to start
1874             if (hideEnd < vstart)
1875             {
1876               continue;
1877             }
1878             if (hideStart > vstart)
1879             {
1880               int[] contig = new int[] { vstart, hideStart - 1 };
1881               vcontigs.add(contig);
1882             }
1883             vstart = hideEnd + 1;
1884
1885             // exit if we're past the end
1886             if (vstart >= end)
1887             {
1888               break;
1889             }
1890           }
1891
1892           if (vstart < end)
1893           {
1894             int[] contig = new int[] { vstart, end - 1 };
1895             vcontigs.add(contig);
1896           }
1897         }
1898         else
1899         {
1900           int[] contig = new int[] { start, end - 1 };
1901           vcontigs.add(contig);
1902         }
1903       } finally
1904       {
1905         if (usecopy)
1906         {
1907           LOCK.readLock().unlock();
1908         }
1909       }
1910     }
1911
1912     @Override
1913     public boolean hasNext()
1914     {
1915       return (currentPosition < vcontigs.size());
1916     }
1917
1918     @Override
1919     public int[] next()
1920     {
1921       int[] result = vcontigs.get(currentPosition);
1922       currentPosition++;
1923       return result;
1924     }
1925   }
1926
1927   /**
1928    * An iterator which iterates over visible regions in a range. The range is
1929    * specified in terms of visible column positions. Provides a special
1930    * "endsAtHidden" indicator to allow callers to determine if the final visible
1931    * column is adjacent to a hidden region.
1932    */
1933   public class VisibleBlocksVisBoundsIterator implements Iterator<int[]>
1934   {
1935     private List<int[]> vcontigs = new ArrayList<>();
1936
1937     private int currentPosition = 0;
1938
1939     private boolean endsAtHidden = false;
1940
1941     /**
1942      * Constructor for iterator over visible regions in a range.
1943      *
1944      * @param start
1945      *          start position in terms of visible column position
1946      * @param end
1947      *          end position in terms of visible column position
1948      * @param usecopy
1949      *          whether to use a local copy of hidden columns
1950      */
1951     VisibleBlocksVisBoundsIterator(int start, int end, boolean usecopy)
1952     {
1953       /* actually this implementation always uses a local copy but this may change in future */
1954       try
1955       {
1956         if (usecopy)
1957         {
1958           LOCK.readLock().lock();
1959         }
1960
1961         if (hiddenColumns != null && hiddenColumns.size() > 0)
1962         {
1963           int blockStart = start;
1964           int blockEnd = end;
1965           int hiddenSoFar = 0;
1966           int visSoFar = 0;
1967
1968           // iterate until a region begins within (start,end]
1969           int i = 0;
1970           while ((i < hiddenColumns.size())
1971                   && (hiddenColumns.get(i)[0] <= blockStart + hiddenSoFar))
1972           {
1973             hiddenSoFar += hiddenColumns.get(i)[1] - hiddenColumns.get(i)[0]
1974                     + 1;
1975             i++;
1976           }
1977
1978           blockStart += hiddenSoFar; // convert start to absolute position
1979           blockEnd += hiddenSoFar; // convert end to absolute position
1980
1981           // iterate from start to end, adding each visible region. Positions
1982           // are
1983           // absolute, and all hidden regions which overlap [start,end] are
1984           // used.
1985           while (i < hiddenColumns.size()
1986                   && (hiddenColumns.get(i)[0] <= blockEnd))
1987           {
1988             int[] region = hiddenColumns.get(i);
1989
1990             // end position of this visible region is either just before the
1991             // start of the next hidden region, or the absolute position of
1992             // 'end', whichever is lowest
1993             blockEnd = Math.min(blockEnd, region[0] - 1);
1994
1995             vcontigs.add(new int[] { blockStart, blockEnd });
1996
1997             visSoFar += blockEnd - blockStart + 1;
1998
1999             // next visible region starts after this hidden region
2000             blockStart = region[1] + 1;
2001
2002             hiddenSoFar += region[1] - region[0] + 1;
2003
2004             // reset blockEnd to absolute position of 'end', assuming we've now
2005             // passed all hidden regions before end
2006             blockEnd = end + hiddenSoFar;
2007
2008             i++;
2009           }
2010           if (visSoFar < end - start)
2011           {
2012             // the number of visible columns we've accounted for is less than
2013             // the number specified by end-start; work out the end position of
2014             // the last visible region
2015             blockEnd = blockStart + end - start - visSoFar;
2016             vcontigs.add(new int[] { blockStart, blockEnd });
2017
2018             // if the last visible region ends at the next hidden region, set
2019             // endsAtHidden=true
2020             if (i < hiddenColumns.size()
2021                     && hiddenColumns.get(i)[0] - 1 == blockEnd)
2022             {
2023               endsAtHidden = true;
2024             }
2025           }
2026         }
2027         else
2028         {
2029           // there are no hidden columns, return a single visible contig
2030           vcontigs.add(new int[] { start, end });
2031           endsAtHidden = false;
2032         }
2033       } finally
2034       {
2035         if (usecopy)
2036         {
2037           LOCK.readLock().unlock();
2038         }
2039       }
2040     }
2041
2042     @Override
2043     public boolean hasNext()
2044     {
2045       return (currentPosition < vcontigs.size());
2046     }
2047
2048     @Override
2049     public int[] next()
2050     {
2051       int[] result = vcontigs.get(currentPosition);
2052       currentPosition++;
2053       return result;
2054     }
2055
2056     public boolean endsAtHidden()
2057     {
2058       return endsAtHidden;
2059     }
2060   }
2061 }