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