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