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