src/jalview/datamodel/HiddenColumns.java

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