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