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