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.concurrent.locks.ReentrantReadWriteLock;
  28
  29 public class HiddenColumns
  30 {
  31   private static final int HASH_MULTIPLIER = 31;
  32
  33   private static final ReentrantReadWriteLock LOCK = new ReentrantReadWriteLock();
  34
  35   private HiddenColumnsCursor cursor = new HiddenColumnsCursor();
  36
  37   /*
  38    * list of hidden column [start, end] ranges; the list is maintained in
  39    * ascending start column order
  40    */
  41   private ArrayList<int[]> hiddenColumns;
  42
  43   /**
  44    * Constructor
  45    */
  46   public HiddenColumns()
  47   {
  48   }
  49
  50   /**
  51    * Copy constructor
  52    *
  53    * @param copy
  54    */
  55   public HiddenColumns(HiddenColumns copy)
  56   {
  57     try
  58     {
  59       LOCK.writeLock().lock();
  60       if (copy != null)
  61       {
  62         if (copy.hiddenColumns != null)
  63         {
  64           hiddenColumns = new ArrayList<>();
  65           Iterator<int[]> it = copy.iterator();
  66           while (it.hasNext())
  67           {
  68             hiddenColumns.add(it.next());
  69           }
  70           cursor.resetCursor(hiddenColumns);
  71         }
  72       }
  73     } finally
  74     {
  75       LOCK.writeLock().unlock();
  76     }
  77   }
  78
  79   /**
  80    * Copy constructor within bounds and with offset. Copies hidden column
  81    * regions fully contained between start and end, and offsets positions by
  82    * subtracting offset.
  83    *
  84    * @param copy
  85    *          HiddenColumns instance to copy from
  86    * @param start
  87    *          lower bound to copy from
  88    * @param end
  89    *          upper bound to copy to
  90    * @param offset
  91    *          offset to subtract from each region boundary position
  92    *
  93    */
  94   public HiddenColumns(HiddenColumns copy, int start, int end, int offset)
  95   {
  96     try
  97     {
  98       LOCK.writeLock().lock();
  99       if (copy != null)
 100       {
 101         hiddenColumns = new ArrayList<>();
 102         Iterator<int[]> it = copy.getBoundedIterator(start, end);
 103         while (it.hasNext())
 104         {
 105           int[] region = it.next();
 106           // still need to check boundaries because iterator returns
 107           // all overlapping regions and we need contained regions
 108           if (region[0] >= start && region[1] <= end)
 109           {
 110             hiddenColumns.add(
 111                     new int[]
 112             { region[0] - offset, region[1] - offset });
 113           }
 114         }
 115         cursor.resetCursor(hiddenColumns);
 116       }
 117     } finally
 118     {
 119       LOCK.writeLock().unlock();
 120     }
 121   }
 122
 123   /**
 124    * Output regions data as a string. String is in the format:
 125    * reg0[0]<between>reg0[1]<delimiter>reg1[0]<between>reg1[1] ... regn[1]
 126    *
 127    * @param delimiter
 128    *          string to delimit regions
 129    * @param betweenstring
 130    *          to put between start and end region values
 131    * @return regions formatted according to delimiter and between strings
 132    */
 133   public String regionsToString(String delimiter, String between)
 134   {
 135     try
 136     {
 137       LOCK.readLock().lock();
 138       StringBuilder regionBuilder = new StringBuilder();
 139       if (hiddenColumns != null)
 140       {
 141         Iterator<int[]> it = hiddenColumns.iterator();
 142         while (it.hasNext())
 143         {
 144           int[] range = it.next();
 145           regionBuilder.append(delimiter).append(range[0]).append(between)
 146                   .append(range[1]);
 147           if (!it.hasNext())
 148           {
 149             regionBuilder.deleteCharAt(0);
 150           }
 151         }
 152       }
 153       return regionBuilder.toString();
 154     } finally
 155     {
 156       LOCK.readLock().unlock();
 157     }
 158   }
 159
 160   /**
 161    * Find the number of hidden columns
 162    *
 163    * @return number of hidden columns
 164    */
 165   public int getSize()
 166   {
 167     try
 168     {
 169       LOCK.readLock().lock();
 170       int size = 0;
 171       if (hiddenColumns != null)
 172       {
 173         Iterator<int[]> it = hiddenColumns.iterator();
 174         while (it.hasNext())
 175         {
 176           int[] range = it.next();
 177           size += range[1] - range[0] + 1;
 178         }
 179       }
 180       return size;
 181     } finally
 182     {
 183       LOCK.readLock().unlock();
 184     }
 185   }
 186
 187   /**
 188    * Get the number of distinct hidden regions
 189    *
 190    * @return number of regions
 191    */
 192   public int getNumberOfRegions()
 193   {
 194     try
 195     {
 196       LOCK.readLock().lock();
 197       int num = 0;
 198       if (hasHiddenColumns())
 199       {
 200         num = hiddenColumns.size();
 201       }
 202       return num;
 203     } finally
 204     {
 205       LOCK.readLock().unlock();
 206     }
 207   }
 208
 209   @Override
 210   public boolean equals(Object obj)
 211   {
 212     try
 213     {
 214       LOCK.readLock().lock();
 215
 216       if (!(obj instanceof HiddenColumns))
 217       {
 218         return false;
 219       }
 220       HiddenColumns that = (HiddenColumns) obj;
 221
 222       /*
 223        * check hidden columns are either both null, or match
 224        */
 225       if (this.hiddenColumns == null)
 226       {
 227         return (that.hiddenColumns == null);
 228       }
 229       if (that.hiddenColumns == null
 230               || that.hiddenColumns.size() != this.hiddenColumns.size())
 231       {
 232         return false;
 233       }
 234
 235       Iterator<int[]> it = hiddenColumns.iterator();
 236       Iterator<int[]> thatit = that.iterator();
 237       while (it.hasNext())
 238       {
 239         int[] thisRange = it.next();
 240         int[] thatRange = thatit.next();
 241         if (thisRange[0] != thatRange[0] || thisRange[1] != thatRange[1])
 242         {
 243           return false;
 244         }
 245       }
 246       return true;
 247     } finally
 248     {
 249       LOCK.readLock().unlock();
 250     }
 251   }
 252
 253   /**
 254    * Return absolute column index for a visible column index
 255    *
 256    * @param column
 257    *          int column index in alignment view (count from zero)
 258    * @return alignment column index for column
 259    */
 260   public int adjustForHiddenColumns(int column)
 261   {
 262     try
 263     {
 264       LOCK.readLock().lock();
 265       int result = column;
 266
 267       if (hiddenColumns != null)
 268       {
 269         result += cursor.getHiddenOffset(column);
 270       }
 271
 272       return result;
 273     } finally
 274     {
 275       LOCK.readLock().unlock();
 276     }
 277   }
 278
 279   /**
 280    * Use this method to find out where a column will appear in the visible
 281    * alignment when hidden columns exist. If the column is not visible, then the
 282    * left-most visible column will always be returned.
 283    *
 284    * @param hiddenColumn
 285    *          the column index in the full alignment including hidden columns
 286    * @return the position of the column in the visible alignment
 287    */
 288   public int findColumnPosition(int hiddenColumn)
 289   {
 290     try
 291     {
 292       LOCK.readLock().lock();
 293       int result = hiddenColumn;
 294       // int[] region = null;
 295       if (hiddenColumns != null)
 296       {
 297         int index = cursor.findRegionForColumn(hiddenColumn);
 298         int hiddenBeforeCol = cursor.getHiddenSoFar();
 299
 300         // just subtract hidden cols count - this works fine if column is
 301         // visible
 302         result = hiddenColumn - hiddenBeforeCol;
 303
 304         // now check in case column is hidden - it will be in the returned
 305         // hidden region
 306         if (index < hiddenColumns.size())
 307         {
 308           int[] region = hiddenColumns.get(index);
 309           if (hiddenColumn >= region[0] && hiddenColumn <= region[1])
 310           {
 311             // actually col is hidden, return region[0]-1
 312             // unless region[0]==0 in which case return 0
 313             if (region[0] == 0)
 314             {
 315               result = 0;
 316             }
 317             else
 318             {
 319               result = region[0] - 1 - hiddenBeforeCol;
 320             }
 321           }
 322         }
 323       }
 324       return result; // return the shifted position after removing hidden
 325                      // columns.
 326     } finally
 327     {
 328       LOCK.readLock().unlock();
 329     }
 330   }
 331
 332   /**
 333    * Find the visible column which is a given visible number of columns to the
 334    * left of another visible column. i.e. for a startColumn x, the column which
 335    * is distance 1 away will be column x-1.
 336    *
 337    * @param visibleDistance
 338    *          the number of visible columns to offset by
 339    * @param startColumn
 340    *          the column to start from
 341    * @return the position of the column in the visible alignment
 342    */
 343   public int subtractVisibleColumns(int visibleDistance, int startColumn)
 344   {
 345     try
 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               hiddenColumns);
 355
 356       while (it.hasNext() && (distance > 0))
 357       {
 358         int[] region = it.next();
 359
 360         if (start > region[1])
 361         {
 362           // subtract the gap to right of region from distance
 363           if (start - region[1] <= distance)
 364           {
 365             distance -= start - region[1];
 366             start = region[0] - 1;
 367           }
 368           else
 369           {
 370             start = start - distance;
 371             distance = 0;
 372           }
 373         }
 374       }
 375
 376       return start - distance;
 377
 378     } finally
 379     {
 380       LOCK.readLock().unlock();
 381     }
 382   }
 383
 384   /**
 385    * This method returns the rightmost limit of a region of an alignment with
 386    * hidden columns. In otherwords, the next hidden column.
 387    *
 388    * @param alPos
 389    *          the absolute (visible) alignmentPosition to find the next hidden
 390    *          column for
 391    */
 392   public int getHiddenBoundaryRight(int alPos)
 393   {
 394     try
 395     {
 396       LOCK.readLock().lock();
 397       if (hiddenColumns != null)
 398       {
 399         int index = cursor.findRegionForColumn(alPos);
 400         if (index < hiddenColumns.size())
 401         {
 402           int[] region = hiddenColumns.get(index);
 403           if (alPos < region[0])
 404           {
 405             return region[0];
 406           }
 407           else if ((alPos <= region[1])
 408                   && (index + 1 < hiddenColumns.size()))
 409           {
 410             // alPos is within a hidden region, return the next one
 411             // if there is one
 412             region = hiddenColumns.get(index + 1);
 413             return region[0];
 414           }
 415         }
 416       }
 417       return alPos;
 418     } finally
 419     {
 420       LOCK.readLock().unlock();
 421     }
 422   }
 423
 424   /**
 425    * This method returns the leftmost limit of a region of an alignment with
 426    * hidden columns. In otherwords, the previous hidden column.
 427    *
 428    * @param alPos
 429    *          the absolute (visible) alignmentPosition to find the previous
 430    *          hidden column for
 431    */
 432   public int getHiddenBoundaryLeft(int alPos)
 433   {
 434     try
 435     {
 436       LOCK.readLock().lock();
 437
 438       if (hiddenColumns != null)
 439       {
 440         int index = cursor.findRegionForColumn(alPos);
 441
 442         if (index > 0)
 443         {
 444           int[] region = hiddenColumns.get(index - 1);
 445           return region[1];
 446         }
 447       }
 448       return alPos;
 449     } finally
 450     {
 451       LOCK.readLock().unlock();
 452     }
 453   }
 454
 455   /**
 456    * Adds the specified column range to the hidden columns collection
 457    *
 458    * @param start
 459    *          start of range to add (absolute position in alignment)
 460    * @param end
 461    *          end of range to add (absolute position in alignment)
 462    */
 463   public void hideColumns(int start, int end)
 464   {
 465     boolean wasAlreadyLocked = false;
 466     try
 467     {
 468       // check if the write lock was already locked by this thread,
 469       // as this method can be called internally in loops within HiddenColumns
 470       if (!LOCK.isWriteLockedByCurrentThread())
 471       {
 472         LOCK.writeLock().lock();
 473       }
 474       else
 475       {
 476         wasAlreadyLocked = true;
 477       }
 478
 479       if (hiddenColumns == null)
 480       {
 481         hiddenColumns = new ArrayList<>();
 482       }
 483
 484       /*
 485        * new range follows everything else; check first to avoid looping over whole hiddenColumns collection
 486        */
 487       if (hiddenColumns.isEmpty()
 488               || start > hiddenColumns.get(hiddenColumns.size() - 1)[1])
 489       {
 490         hiddenColumns.add(new int[] { start, end });
 491       }
 492       else
 493       {
 494         /*
 495          * traverse existing hidden ranges and insert / amend / append as
 496          * appropriate
 497          */
 498         boolean added = false;
 499         for (int i = 0; !added && i < hiddenColumns.size(); i++)
 500         {
 501           added = insertRangeAtRegion(i, start, end);
 502         } // for
 503       }
 504       if (!wasAlreadyLocked)
 505       {
 506         cursor.resetCursor(hiddenColumns);
 507       }
 508     } finally
 509     {
 510       if (!wasAlreadyLocked)
 511       {
 512         LOCK.writeLock().unlock();
 513       }
 514     }
 515   }
 516
 517   /**
 518    * Insert [start, range] at the region at index i in hiddenColumns, if
 519    * feasible
 520    *
 521    * @param i
 522    *          index to insert at
 523    * @param start
 524    *          start of range to insert
 525    * @param end
 526    *          end of range to insert
 527    * @return true if range was successfully inserted
 528    */
 529   private boolean insertRangeAtRegion(int i, int start, int end)
 530   {
 531     boolean added = false;
 532
 533     int[] region = hiddenColumns.get(i);
 534     if (end < region[0] - 1)
 535     {
 536       /*
 537        * insert discontiguous preceding range
 538        */
 539       hiddenColumns.add(i, new int[] { start, end });
 540       added = true;
 541     }
 542     else if (end <= region[1])
 543     {
 544       /*
 545        * new range overlaps existing, or is contiguous preceding it - adjust
 546        * start column
 547        */
 548       region[0] = Math.min(region[0], start);
 549       added = true;
 550     }
 551     else if (start <= region[1] + 1)
 552     {
 553       /*
 554        * new range overlaps existing, or is contiguous following it - adjust
 555        * start and end columns
 556        */
 557       region[0] = Math.min(region[0], start);
 558       region[1] = Math.max(region[1], end);
 559
 560       /*
 561        * also update or remove any subsequent ranges
 562        * that are overlapped
 563        */
 564       while (i < hiddenColumns.size() - 1)
 565       {
 566         int[] nextRegion = hiddenColumns.get(i + 1);
 567         if (nextRegion[0] > end + 1)
 568         {
 569           /*
 570            * gap to next hidden range - no more to update
 571            */
 572           break;
 573         }
 574         region[1] = Math.max(nextRegion[1], end);
 575         hiddenColumns.subList(i + 1, i + 2).clear();
 576       }
 577       added = true;
 578     }
 579     return added;
 580   }
 581
 582   /**
 583    * Answers if a column in the alignment is visible
 584    *
 585    * @param column
 586    *          absolute position of column in the alignment
 587    * @return true if column is visible
 588    */
 589   public boolean isVisible(int column)
 590   {
 591     try
 592     {
 593       LOCK.readLock().lock();
 594
 595       Iterator<int[]> it = new RegionsIterator(column, column,
 596               hiddenColumns, cursor);
 597       while (it.hasNext())
 598       {
 599         int[] region = it.next();
 600         if (column >= region[0] && column <= region[1])
 601         {
 602           return false;
 603         }
 604       }
 605
 606       return true;
 607     } finally
 608     {
 609       LOCK.readLock().unlock();
 610     }
 611   }
 612
 613   /**
 614    * Get the visible sections of a set of sequences
 615    *
 616    * @param start
 617    *          sequence position to start from
 618    * @param end
 619    *          sequence position to end at
 620    * @param seqs
 621    *          an array of sequences
 622    * @return an array of strings encoding the visible parts of each sequence
 623    */
 624   public String[] getVisibleSequenceStrings(int start, int end,
 625           SequenceI[] seqs)
 626   {
 627     try
 628     {
 629       LOCK.readLock().lock();
 630       int iSize = seqs.length;
 631       String[] selections = new String[iSize];
 632       if (hiddenColumns != null && hiddenColumns.size() > 0)
 633       {
 634         for (int i = 0; i < iSize; i++)
 635         {
 636           StringBuffer visibleSeq = new StringBuffer();
 637
 638           Iterator<int[]> blocks = new VisibleContigsIterator(start,
 639                   end + 1, hiddenColumns);
 640
 641           while (blocks.hasNext())
 642           {
 643             int[] block = blocks.next();
 644             if (blocks.hasNext())
 645             {
 646               visibleSeq
 647                       .append(seqs[i].getSequence(block[0], block[1] + 1));
 648             }
 649             else
 650             {
 651               visibleSeq
 652                       .append(seqs[i].getSequence(block[0], block[1]));
 653             }
 654           }
 655
 656           selections[i] = visibleSeq.toString();
 657         }
 658       }
 659       else
 660       {
 661         for (int i = 0; i < iSize; i++)
 662         {
 663           selections[i] = seqs[i].getSequenceAsString(start, end);
 664         }
 665       }
 666
 667       return selections;
 668     } finally
 669     {
 670       LOCK.readLock().unlock();
 671     }
 672   }
 673
 674   /**
 675    * Locate the first position visible for this sequence. If seq isn't visible
 676    * then return the position of the left side of the hidden boundary region.
 677    *
 678    * @param seq
 679    *          sequence to find position for
 680    * @return visible start position
 681    */
 682   public int locateVisibleStartOfSequence(SequenceI seq)
 683   {
 684     try
 685     {
 686       LOCK.readLock().lock();
 687       int start = 0;
 688
 689       if (hiddenColumns == null || hiddenColumns.size() == 0)
 690       {
 691         return seq.findIndex(seq.getStart()) - 1;
 692       }
 693
 694       // Simply walk along the sequence whilst watching for hidden column
 695       // boundaries
 696       Iterator<int[]> regions = hiddenColumns.iterator();
 697       int hideStart = seq.getLength();
 698       int hideEnd = -1;
 699       int visPrev = 0;
 700       int visNext = 0;
 701       boolean foundStart = false;
 702
 703       // step through the non-gapped positions of the sequence
 704       for (int i = seq.getStart(); i <= seq.getEnd() && (!foundStart); i++)
 705       {
 706         // get alignment position of this residue in the sequence
 707         int p = seq.findIndex(i) - 1;
 708
 709         // update hidden region start/end
 710         while (hideEnd < p && regions.hasNext())
 711         {
 712           int[] region = regions.next();
 713           visPrev = visNext;
 714           visNext += region[0] - visPrev;
 715           hideStart = region[0];
 716           hideEnd = region[1];
 717         }
 718         if (hideEnd < p)
 719         {
 720           hideStart = seq.getLength();
 721         }
 722         // update visible boundary for sequence
 723         if (p < hideStart)
 724         {
 725           start = p;
 726           foundStart = true;
 727         }
 728       }
 729
 730       if (foundStart)
 731       {
 732         return findColumnPosition(start);
 733       }
 734       // otherwise, sequence was completely hidden
 735       return visPrev;
 736     } finally
 737     {
 738       LOCK.readLock().unlock();
 739     }
 740   }
 741
 742   /**
 743    * delete any columns in alignmentAnnotation that are hidden (including
 744    * sequence associated annotation).
 745    *
 746    * @param alignmentAnnotation
 747    */
 748   public void makeVisibleAnnotation(AlignmentAnnotation alignmentAnnotation)
 749   {
 750     makeVisibleAnnotation(0, alignmentAnnotation.annotations.length,
 751             alignmentAnnotation);
 752   }
 753
 754   /**
 755    * delete any columns in alignmentAnnotation that are hidden (including
 756    * sequence associated annotation).
 757    *
 758    * @param start
 759    *          remove any annotation to the right of this column
 760    * @param end
 761    *          remove any annotation to the left of this column
 762    * @param alignmentAnnotation
 763    *          the annotation to operate on
 764    */
 765   public void makeVisibleAnnotation(int start, int end,
 766           AlignmentAnnotation alignmentAnnotation)
 767   {
 768     try
 769     {
 770       LOCK.readLock().lock();
 771
 772       int startFrom = start;
 773       int endAt = end;
 774
 775       if (alignmentAnnotation.annotations != null)
 776       {
 777         if (hiddenColumns != null && hiddenColumns.size() > 0)
 778         {
 779           removeHiddenAnnotation(startFrom, endAt, alignmentAnnotation);
 780         }
 781         else
 782         {
 783           alignmentAnnotation.restrict(startFrom, endAt);
 784         }
 785       }
 786     } finally
 787     {
 788       LOCK.readLock().unlock();
 789     }
 790   }
 791
 792   private void removeHiddenAnnotation(int start, int end,
 793           AlignmentAnnotation alignmentAnnotation)
 794   {
 795     // mangle the alignmentAnnotation annotation array
 796     ArrayList<Annotation[]> annels = new ArrayList<>();
 797     Annotation[] els = null;
 798
 799     int w = 0;
 800
 801     Iterator<int[]> blocks = new VisibleContigsIterator(start, end + 1,
 802             hiddenColumns);
 803
 804     int copylength;
 805     int annotationLength;
 806     while (blocks.hasNext())
 807     {
 808       int[] block = blocks.next();
 809       annotationLength = block[1] - block[0] + 1;
 810
 811       if (blocks.hasNext())
 812       {
 813         // copy just the visible segment of the annotation row
 814         copylength = annotationLength;
 815       }
 816       else
 817       {
 818         if (annotationLength + block[0] <= alignmentAnnotation.annotations.length)
 819         {
 820           // copy just the visible segment of the annotation row
 821           copylength = annotationLength;
 822         }
 823         else
 824         {
 825           // copy to the end of the annotation row
 826           copylength = alignmentAnnotation.annotations.length - block[0];
 827         }
 828       }
 829
 830       els = new Annotation[annotationLength];
 831       annels.add(els);
 832       System.arraycopy(alignmentAnnotation.annotations, block[0], els, 0,
 833               copylength);
 834       w += annotationLength;
 835     }
 836
 837     if (w != 0)
 838     {
 839       alignmentAnnotation.annotations = new Annotation[w];
 840
 841       w = 0;
 842       for (Annotation[] chnk : annels)
 843       {
 844         System.arraycopy(chnk, 0, alignmentAnnotation.annotations, w,
 845                 chnk.length);
 846         w += chnk.length;
 847       }
 848     }
 849   }
 850
 851   /**
 852    *
 853    * @return true if there are columns hidden
 854    */
 855   public boolean hasHiddenColumns()
 856   {
 857     try
 858     {
 859       LOCK.readLock().lock();
 860       return hiddenColumns != null && hiddenColumns.size() > 0;
 861     } finally
 862     {
 863       LOCK.readLock().unlock();
 864     }
 865   }
 866
 867   /**
 868    *
 869    * @return true if there are more than one set of columns hidden
 870    */
 871   public boolean hasManyHiddenColumns()
 872   {
 873     try
 874     {
 875       LOCK.readLock().lock();
 876       return hiddenColumns != null && hiddenColumns.size() > 1;
 877     } finally
 878     {
 879       LOCK.readLock().unlock();
 880     }
 881   }
 882
 883   /**
 884    * mark the columns corresponding to gap characters as hidden in the column
 885    * selection
 886    *
 887    * @param sr
 888    */
 889   public void hideInsertionsFor(SequenceI sr)
 890   {
 891     try
 892     {
 893       LOCK.writeLock().lock();
 894       List<int[]> inserts = sr.getInsertions();
 895       for (int[] r : inserts)
 896       {
 897         hideColumns(r[0], r[1]);
 898       }
 899       cursor.resetCursor(hiddenColumns);
 900     } finally
 901     {
 902       LOCK.writeLock().unlock();
 903     }
 904   }
 905
 906   /**
 907    * Unhides, and adds to the selection list, all hidden columns
 908    */
 909   public void revealAllHiddenColumns(ColumnSelection sel)
 910   {
 911     try
 912     {
 913       LOCK.writeLock().lock();
 914       if (hiddenColumns != null)
 915       {
 916         Iterator<int[]> it = hiddenColumns.iterator();
 917         while (it.hasNext())
 918         {
 919           int[] region = it.next();
 920           for (int j = region[0]; j < region[1] + 1; j++)
 921           {
 922             sel.addElement(j);
 923           }
 924         }
 925         hiddenColumns = null;
 926         cursor.resetCursor(hiddenColumns);
 927       }
 928     } finally
 929     {
 930       LOCK.writeLock().unlock();
 931     }
 932   }
 933
 934   /**
 935    * Reveals, and marks as selected, the hidden column range with the given
 936    * start column
 937    *
 938    * @param start
 939    */
 940   public void revealHiddenColumns(int start, ColumnSelection sel)
 941   {
 942     try
 943     {
 944       LOCK.writeLock().lock();
 945       Iterator<int[]> it = new RegionsIterator(start, start, hiddenColumns,
 946               cursor);
 947       while (it.hasNext())
 948       {
 949         int[] region = it.next();
 950         if (start == region[0])
 951         {
 952           for (int j = region[0]; j < region[1] + 1; j++)
 953           {
 954             sel.addElement(j);
 955           }
 956           it.remove();
 957           break;
 958         }
 959         else if (start < region[0])
 960         {
 961           break; // passed all possible matching regions
 962         }
 963       }
 964
 965       if (hiddenColumns.size() == 0)
 966       {
 967         hiddenColumns = null;
 968       }
 969       cursor.resetCursor(hiddenColumns);
 970     } finally
 971     {
 972       LOCK.writeLock().unlock();
 973     }
 974   }
 975
 976   /**
 977    * Add gaps into the sequences aligned to profileseq under the given
 978    * AlignmentView
 979    *
 980    * @param profileseq
 981    * @param al
 982    *          - alignment to have gaps inserted into it
 983    * @param input
 984    *          - alignment view where sequence corresponding to profileseq is
 985    *          first entry
 986    * @return new HiddenColumns for new alignment view, with insertions into
 987    *         profileseq marked as hidden.
 988    */
 989   public static HiddenColumns propagateInsertions(SequenceI profileseq,
 990           AlignmentI al, AlignmentView input)
 991   {
 992     int profsqpos = 0;
 993
 994     char gc = al.getGapCharacter();
 995     Object[] alandhidden = input.getAlignmentAndHiddenColumns(gc);
 996     HiddenColumns nview = (HiddenColumns) alandhidden[1];
 997     SequenceI origseq = ((SequenceI[]) alandhidden[0])[profsqpos];
 998     nview.propagateInsertions(profileseq, al, origseq);
 999     return nview;
1000   }
1001
1002   /**
1003    *
1004    * @param profileseq
1005    *          - sequence in al which corresponds to origseq
1006    * @param al
1007    *          - alignment which is to have gaps inserted into it
1008    * @param origseq
1009    *          - sequence corresponding to profileseq which defines gap map for
1010    *          modifying al
1011    */
1012   private void propagateInsertions(SequenceI profileseq, AlignmentI al,
1013           SequenceI origseq)
1014   {
1015     try
1016     {
1017       LOCK.writeLock().lock();
1018
1019       char gc = al.getGapCharacter();
1020
1021       // take the set of hidden columns, and the set of gaps in origseq,
1022       // and remove all the hidden gaps from hiddenColumns
1023
1024       // first get the gaps as a Bitset
1025       BitSet gaps = origseq.gapBitset();
1026
1027       // now calculate hidden ^ not(gap)
1028       BitSet hidden = new BitSet();
1029       markHiddenRegions(hidden);
1030       hidden.andNot(gaps);
1031       hiddenColumns = null;
1032       this.hideMarkedBits(hidden);
1033
1034       // for each sequence in the alignment, except the profile sequence,
1035       // insert gaps corresponding to each hidden region
1036       // but where each hidden column region is shifted backwards by the number
1037       // of
1038       // preceding visible gaps
1039       // update hidden columns at the same time
1040       Iterator<int[]> regions = hiddenColumns.iterator();
1041       ArrayList<int[]> newhidden = new ArrayList<>();
1042
1043       int numGapsBefore = 0;
1044       int gapPosition = 0;
1045       while (regions.hasNext())
1046       {
1047         // get region coordinates accounting for gaps
1048         // we can rely on gaps not being *in* hidden regions because we already
1049         // removed those
1050         int[] region = regions.next();
1051         while (gapPosition < region[0])
1052         {
1053           gapPosition++;
1054           if (gaps.get(gapPosition))
1055           {
1056             numGapsBefore++;
1057           }
1058         }
1059
1060         int left = region[0] - numGapsBefore;
1061         int right = region[1] - numGapsBefore;
1062         newhidden.add(new int[] { left, right });
1063
1064         // make a string with number of gaps = length of hidden region
1065         StringBuffer sb = new StringBuffer();
1066         for (int s = 0; s < right - left + 1; s++)
1067         {
1068           sb.append(gc);
1069         }
1070         padGaps(sb, left, profileseq, al);
1071
1072       }
1073       hiddenColumns = newhidden;
1074       cursor.resetCursor(hiddenColumns);
1075     } finally
1076     {
1077       LOCK.writeLock().unlock();
1078     }
1079   }
1080
1081   /**
1082    * Pad gaps in all sequences in alignment except profileseq
1083    *
1084    * @param sb
1085    *          gap string to insert
1086    * @param left
1087    *          position to insert at
1088    * @param profileseq
1089    *          sequence not to pad
1090    * @param al
1091    *          alignment to pad sequences in
1092    */
1093   private void padGaps(StringBuffer sb, int pos, SequenceI profileseq,
1094           AlignmentI al)
1095   {
1096     // loop over the sequences and pad with gaps where required
1097     for (int s = 0, ns = al.getHeight(); s < ns; s++)
1098     {
1099       SequenceI sqobj = al.getSequenceAt(s);
1100       if (sqobj != profileseq)
1101       {
1102         String sq = al.getSequenceAt(s).getSequenceAsString();
1103         if (sq.length() <= pos)
1104         {
1105           // pad sequence
1106           int diff = pos - sq.length() - 1;
1107           if (diff > 0)
1108           {
1109             // pad gaps
1110             sq = sq + sb;
1111             while ((diff = pos - sq.length() - 1) > 0)
1112             {
1113               if (diff >= sb.length())
1114               {
1115                 sq += sb.toString();
1116               }
1117               else
1118               {
1119                 char[] buf = new char[diff];
1120                 sb.getChars(0, diff, buf, 0);
1121                 sq += buf.toString();
1122               }
1123             }
1124           }
1125           sq += sb.toString();
1126         }
1127         else
1128         {
1129           al.getSequenceAt(s).setSequence(
1130                   sq.substring(0, pos) + sb.toString() + sq.substring(pos));
1131         }
1132       }
1133     }
1134   }
1135
1136   /**
1137    * Returns a hashCode built from hidden column ranges
1138    */
1139   @Override
1140   public int hashCode()
1141   {
1142     try
1143     {
1144       LOCK.readLock().lock();
1145       int hashCode = 1;
1146       Iterator<int[]> it = hiddenColumns.iterator();
1147       while (it.hasNext())
1148       {
1149         int[] hidden = it.next();
1150         hashCode = HASH_MULTIPLIER * hashCode + hidden[0];
1151         hashCode = HASH_MULTIPLIER * hashCode + hidden[1];
1152       }
1153       return hashCode;
1154     } finally
1155     {
1156       LOCK.readLock().unlock();
1157     }
1158   }
1159
1160   /**
1161    * Hide columns corresponding to the marked bits
1162    *
1163    * @param inserts
1164    *          - columns map to bits starting from zero
1165    */
1166   public void hideMarkedBits(BitSet inserts)
1167   {
1168     try
1169     {
1170       LOCK.writeLock().lock();
1171       for (int firstSet = inserts
1172               .nextSetBit(0), lastSet = 0; firstSet >= 0; firstSet = inserts
1173                       .nextSetBit(lastSet))
1174       {
1175         lastSet = inserts.nextClearBit(firstSet);
1176         hideColumns(firstSet, lastSet - 1);
1177       }
1178       cursor.resetCursor(hiddenColumns);
1179     } finally
1180     {
1181       LOCK.writeLock().unlock();
1182     }
1183   }
1184
1185   /**
1186    *
1187    * @param inserts
1188    *          BitSet where hidden columns will be marked
1189    */
1190   public void markHiddenRegions(BitSet inserts)
1191   {
1192     try
1193     {
1194       LOCK.readLock().lock();
1195       if (hiddenColumns == null)
1196       {
1197         return;
1198       }
1199       Iterator<int[]> it = hiddenColumns.iterator();
1200       while (it.hasNext())
1201       {
1202         int[] range = it.next();
1203         inserts.set(range[0], range[1] + 1);
1204       }
1205     } finally
1206     {
1207       LOCK.readLock().unlock();
1208     }
1209   }
1210
1211   /**
1212    * Calculate the visible start and end index of an alignment.
1213    *
1214    * @param width
1215    *          full alignment width
1216    * @return integer array where: int[0] = startIndex, and int[1] = endIndex
1217    */
1218   public int[] getVisibleStartAndEndIndex(int width)
1219   {
1220     try
1221     {
1222       LOCK.readLock().lock();
1223       int[] alignmentStartEnd = new int[] { 0, width - 1 };
1224       int startPos = alignmentStartEnd[0];
1225       int endPos = alignmentStartEnd[1];
1226
1227       int[] lowestRange = new int[] { -1, -1 };
1228       int[] higestRange = new int[] { -1, -1 };
1229
1230       if (hiddenColumns == null)
1231       {
1232         return new int[] { startPos, endPos };
1233       }
1234
1235       Iterator<int[]> it = hiddenColumns.iterator();
1236       while (it.hasNext())
1237       {
1238         int[] range = it.next();
1239         lowestRange = (range[0] <= startPos) ? range : lowestRange;
1240         higestRange = (range[1] >= endPos) ? range : higestRange;
1241       }
1242
1243       if (lowestRange[0] == -1 && lowestRange[1] == -1)
1244       {
1245         startPos = alignmentStartEnd[0];
1246       }
1247       else
1248       {
1249         startPos = lowestRange[1] + 1;
1250       }
1251
1252       if (higestRange[0] == -1 && higestRange[1] == -1)
1253       {
1254         endPos = alignmentStartEnd[1];
1255       }
1256       else
1257       {
1258         endPos = higestRange[0] - 1;
1259       }
1260       return new int[] { startPos, endPos };
1261     } finally
1262     {
1263       LOCK.readLock().unlock();
1264     }
1265   }
1266
1267   /**
1268    * Finds the hidden region (if any) which starts or ends at res
1269    *
1270    * @param res
1271    *          visible residue position, unadjusted for hidden columns
1272    * @return region as [start,end] or null if no matching region is found
1273    */
1274   public int[] getRegionWithEdgeAtRes(int res)
1275   {
1276     try
1277     {
1278       LOCK.readLock().lock();
1279       int adjres = adjustForHiddenColumns(res);
1280
1281       int[] reveal = null;
1282
1283       if (hiddenColumns != null)
1284       {
1285         int regionindex = cursor.findRegionForColumn(adjres - 1);
1286         if (hiddenColumns.get(regionindex)[1] == adjres - 1)
1287         {
1288           reveal = hiddenColumns.get(regionindex);
1289         }
1290         else
1291         {
1292           regionindex = cursor.findRegionForColumn(adjres + 1);
1293           if (hiddenColumns.get(regionindex)[0] == adjres + 1)
1294           {
1295             reveal = hiddenColumns.get(regionindex);
1296           }
1297         }
1298       }
1299       return reveal;
1300
1301     } finally
1302     {
1303       LOCK.readLock().unlock();
1304     }
1305   }
1306
1307   /**
1308    * Return an iterator over the hidden regions
1309    */
1310   public Iterator<int[]> iterator()
1311   {
1312     try
1313     {
1314       LOCK.readLock().lock();
1315       return new BoundedHiddenColsIterator(hiddenColumns);
1316     } finally
1317     {
1318       LOCK.readLock().unlock();
1319     }
1320   }
1321
1322   /**
1323    * Return a bounded iterator over the hidden regions
1324    *
1325    * @param start
1326    *          position to start from (inclusive, absolute column position)
1327    * @param end
1328    *          position to end at (inclusive, absolute column position)
1329    * @return
1330    */
1331   public Iterator<int[]> getBoundedIterator(int start, int end)
1332   {
1333     try
1334     {
1335       LOCK.readLock().lock();
1336       return new BoundedHiddenColsIterator(start, end, hiddenColumns);
1337     } finally
1338     {
1339       LOCK.readLock().unlock();
1340     }
1341   }
1342
1343   /**
1344    * Return a bounded iterator over the *visible* start positions of hidden
1345    * regions
1346    *
1347    * @param start
1348    *          position to start from (inclusive, visible column position)
1349    * @param end
1350    *          position to end at (inclusive, visible column position)
1351    */
1352   public Iterator<Integer> getBoundedStartIterator(int start, int end)
1353   {
1354     try
1355     {
1356       LOCK.readLock().lock();
1357       return new BoundedStartRegionIterator(start, end, hiddenColumns);
1358     } finally
1359     {
1360       LOCK.readLock().unlock();
1361     }
1362   }
1363
1364   /**
1365    * Return an iterator over visible *columns* (not regions) between the given
1366    * start and end boundaries
1367    *
1368    * @param start
1369    *          first column (inclusive)
1370    * @param end
1371    *          last column (inclusive)
1372    */
1373   public Iterator<Integer> getVisibleColsIterator(int start, int end)
1374   {
1375     try
1376     {
1377       LOCK.readLock().lock();
1378       return new VisibleColsIterator(start, end, hiddenColumns);
1379     } finally
1380     {
1381       LOCK.readLock().unlock();
1382     }
1383   }
1384
1385   /**
1386    * return an iterator over visible segments between the given start and end
1387    * boundaries
1388    *
1389    * @param start
1390    *          (first column inclusive from 0)
1391    * @param end
1392    *          (last column - not inclusive)
1393    */
1394   public Iterator<int[]> getVisContigsIterator(int start, int end)
1395   {
1396     try
1397     {
1398       LOCK.readLock().lock();
1399       return new VisibleContigsIterator(start, end, hiddenColumns);
1400     } finally
1401     {
1402       LOCK.readLock().unlock();
1403     }
1404   }
1405
1406   /**
1407    * return an iterator over visible segments between the given start and end
1408    * boundaries
1409    *
1410    * @param start
1411    *          (first column - inclusive from 0)
1412    * @param end
1413    *          (last column - inclusive)
1414    * @param useVisibleCoords
1415    *          if true, start and end are visible column positions, not absolute
1416    *          positions
1417    */
1418   public Iterator<int[]> getVisibleBlocksIterator(int start, int end,
1419           boolean useVisibleCoords)
1420   {
1421     if (useVisibleCoords)
1422     {
1423       // TODO
1424       // we should really just convert start and end here with
1425       // adjustForHiddenColumns
1426       // and then create a VisibleContigsIterator
1427       // but without a cursor this will be horribly slow in some situations
1428       // ... so until then...
1429       return new VisibleBlocksVisBoundsIterator(start, end, true);
1430     }
1431     else
1432     {
1433       try
1434       {
1435         LOCK.readLock().lock();
1436         return new VisibleContigsIterator(start, end + 1, hiddenColumns);
1437       } finally
1438     {
1439         LOCK.readLock().unlock();
1440       }
1441     }
1442   }
1443
1444   /**
1445    * An iterator which iterates over visible regions in a range. The range is
1446    * specified in terms of visible column positions. Provides a special
1447    * "endsAtHidden" indicator to allow callers to determine if the final visible
1448    * column is adjacent to a hidden region.
1449    */
1450   public class VisibleBlocksVisBoundsIterator implements Iterator<int[]>
1451   {
1452     private List<int[]> vcontigs = new ArrayList<>();
1453
1454     private int currentPosition = 0;
1455
1456     private boolean endsAtHidden = false;
1457
1458     /**
1459      * Constructor for iterator over visible regions in a range.
1460      *
1461      * @param start
1462      *          start position in terms of visible column position
1463      * @param end
1464      *          end position in terms of visible column position
1465      * @param usecopy
1466      *          whether to use a local copy of hidden columns
1467      */
1468     VisibleBlocksVisBoundsIterator(int start, int end, boolean usecopy)
1469     {
1470       /* actually this implementation always uses a local copy but this may change in future */
1471       try
1472       {
1473         if (usecopy)
1474         {
1475           LOCK.readLock().lock();
1476         }
1477
1478         if (hiddenColumns != null && hiddenColumns.size() > 0)
1479         {
1480           int blockStart = start;
1481           int blockEnd = end;
1482           int hiddenSoFar = 0;
1483           int visSoFar = 0;
1484
1485           // iterate until a region begins within (start,end]
1486           int i = 0;
1487           while ((i < hiddenColumns.size())
1488                   && (hiddenColumns.get(i)[0] <= blockStart + hiddenSoFar))
1489           {
1490             hiddenSoFar += hiddenColumns.get(i)[1] - hiddenColumns.get(i)[0]
1491                     + 1;
1492             i++;
1493           }
1494
1495           blockStart += hiddenSoFar; // convert start to absolute position
1496           blockEnd += hiddenSoFar; // convert end to absolute position
1497
1498           // iterate from start to end, adding each visible region. Positions
1499           // are
1500           // absolute, and all hidden regions which overlap [start,end] are
1501           // used.
1502           while (i < hiddenColumns.size()
1503                   && (hiddenColumns.get(i)[0] <= blockEnd))
1504           {
1505             int[] region = hiddenColumns.get(i);
1506
1507             // end position of this visible region is either just before the
1508             // start of the next hidden region, or the absolute position of
1509             // 'end', whichever is lowest
1510             blockEnd = Math.min(blockEnd, region[0] - 1);
1511
1512             vcontigs.add(new int[] { blockStart, blockEnd });
1513
1514             visSoFar += blockEnd - blockStart + 1;
1515
1516             // next visible region starts after this hidden region
1517             blockStart = region[1] + 1;
1518
1519             hiddenSoFar += region[1] - region[0] + 1;
1520
1521             // reset blockEnd to absolute position of 'end', assuming we've now
1522             // passed all hidden regions before end
1523             blockEnd = end + hiddenSoFar;
1524
1525             i++;
1526           }
1527           if (visSoFar < end - start + 1)
1528           {
1529             // the number of visible columns we've accounted for is less than
1530             // the number specified by end-start; work out the end position of
1531             // the last visible region
1532             blockEnd = blockStart + end - start - visSoFar;
1533             vcontigs.add(new int[] { blockStart, blockEnd });
1534
1535             // if the last visible region ends at the next hidden region, set
1536             // endsAtHidden=true
1537             if (i < hiddenColumns.size()
1538                     && hiddenColumns.get(i)[0] - 1 == blockEnd)
1539             {
1540               endsAtHidden = true;
1541             }
1542           }
1543         }
1544         else
1545         {
1546           // there are no hidden columns, return a single visible contig
1547           vcontigs.add(new int[] { start, end });
1548           endsAtHidden = false;
1549         }
1550       } finally
1551       {
1552         if (usecopy)
1553         {
1554           LOCK.readLock().unlock();
1555         }
1556       }
1557     }
1558
1559     @Override
1560     public boolean hasNext()
1561     {
1562       return (currentPosition < vcontigs.size());
1563     }
1564
1565     @Override
1566     public int[] next()
1567     {
1568       int[] result = vcontigs.get(currentPosition);
1569       currentPosition++;
1570       return result;
1571     }
1572
1573     public boolean endsAtHidden()
1574     {
1575       return endsAtHidden;
1576     }
1577   }
1578 }