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