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       Iterator<int[]> it = hiddenColumns.iterator();
 925       while (it.hasNext())
 926       {
 927         int[] region = it.next();
 928         for (int j = region[0]; j < region[1] + 1; j++)
 929         {
 930           sel.addElement(j);
 931         }
 932       }
 933       hiddenColumns = null;
 934       cursor.resetCursor(hiddenColumns);
 935     } finally
 936     {
 937       LOCK.writeLock().unlock();
 938     }
 939   }
 940
 941   /**
 942    * Reveals, and marks as selected, the hidden column range with the given
 943    * start column
 944    *
 945    * @param start
 946    */
 947   public void revealHiddenColumns(int start, ColumnSelection sel)
 948   {
 949     try
 950     {
 951       LOCK.writeLock().lock();
 952       Iterator<int[]> it = new RegionsIterator(start, start, hiddenColumns,
 953               cursor);
 954       while (it.hasNext())
 955       {
 956         int[] region = it.next();
 957         if (start == region[0])
 958         {
 959           for (int j = region[0]; j < region[1] + 1; j++)
 960           {
 961             sel.addElement(j);
 962           }
 963           it.remove();
 964           break;
 965         }
 966         else if (start < region[0])
 967         {
 968           break; // passed all possible matching regions
 969         }
 970       }
 971
 972       if (hiddenColumns.size() == 0)
 973       {
 974         hiddenColumns = null;
 975       }
 976       cursor.resetCursor(hiddenColumns);
 977     } finally
 978     {
 979       LOCK.writeLock().unlock();
 980     }
 981   }
 982
 983   /**
 984    * Add gaps into the sequences aligned to profileseq under the given
 985    * AlignmentView
 986    *
 987    * @param profileseq
 988    * @param al
 989    *          - alignment to have gaps inserted into it
 990    * @param input
 991    *          - alignment view where sequence corresponding to profileseq is
 992    *          first entry
 993    * @return new HiddenColumns for new alignment view, with insertions into
 994    *         profileseq marked as hidden.
 995    */
 996   public static HiddenColumns propagateInsertions(SequenceI profileseq,
 997           AlignmentI al, AlignmentView input)
 998   {
 999     int profsqpos = 0;
1000
1001     char gc = al.getGapCharacter();
1002     Object[] alandhidden = input.getAlignmentAndHiddenColumns(gc);
1003     HiddenColumns nview = (HiddenColumns) alandhidden[1];
1004     SequenceI origseq = ((SequenceI[]) alandhidden[0])[profsqpos];
1005     nview.propagateInsertions(profileseq, al, origseq);
1006     return nview;
1007   }
1008
1009   /**
1010    *
1011    * @param profileseq
1012    *          - sequence in al which corresponds to origseq
1013    * @param al
1014    *          - alignment which is to have gaps inserted into it
1015    * @param origseq
1016    *          - sequence corresponding to profileseq which defines gap map for
1017    *          modifying al
1018    */
1019   private void propagateInsertions(SequenceI profileseq, AlignmentI al,
1020           SequenceI origseq)
1021   {
1022     try
1023     {
1024       LOCK.writeLock().lock();
1025
1026       char gc = al.getGapCharacter();
1027
1028       // take the set of hidden columns, and the set of gaps in origseq,
1029       // and remove all the hidden gaps from hiddenColumns
1030
1031       // first get the gaps as a Bitset
1032       BitSet gaps = origseq.gapBitset();
1033
1034       // now calculate hidden ^ not(gap)
1035       BitSet hidden = new BitSet();
1036       markHiddenRegions(hidden);
1037       hidden.andNot(gaps);
1038       hiddenColumns = null;
1039       this.hideMarkedBits(hidden);
1040
1041       // for each sequence in the alignment, except the profile sequence,
1042       // insert gaps corresponding to each hidden region
1043       // but where each hidden column region is shifted backwards by the number
1044       // of
1045       // preceding visible gaps
1046       // update hidden columns at the same time
1047       Iterator<int[]> regions = hiddenColumns.iterator();
1048       ArrayList<int[]> newhidden = new ArrayList<>();
1049
1050       int numGapsBefore = 0;
1051       int gapPosition = 0;
1052       while (regions.hasNext())
1053       {
1054         // get region coordinates accounting for gaps
1055         // we can rely on gaps not being *in* hidden regions because we already
1056         // removed those
1057         int[] region = regions.next();
1058         while (gapPosition < region[0])
1059         {
1060           gapPosition++;
1061           if (gaps.get(gapPosition))
1062           {
1063             numGapsBefore++;
1064           }
1065         }
1066
1067         int left = region[0] - numGapsBefore;
1068         int right = region[1] - numGapsBefore;
1069         newhidden.add(new int[] { left, right });
1070
1071         // make a string with number of gaps = length of hidden region
1072         StringBuffer sb = new StringBuffer();
1073         for (int s = 0; s < right - left + 1; s++)
1074         {
1075           sb.append(gc);
1076         }
1077         padGaps(sb, left, profileseq, al);
1078
1079       }
1080       hiddenColumns = newhidden;
1081       cursor.resetCursor(hiddenColumns);
1082     } finally
1083     {
1084       LOCK.writeLock().unlock();
1085     }
1086   }
1087
1088   /**
1089    * Pad gaps in all sequences in alignment except profileseq
1090    *
1091    * @param sb
1092    *          gap string to insert
1093    * @param left
1094    *          position to insert at
1095    * @param profileseq
1096    *          sequence not to pad
1097    * @param al
1098    *          alignment to pad sequences in
1099    */
1100   private void padGaps(StringBuffer sb, int pos, SequenceI profileseq,
1101           AlignmentI al)
1102   {
1103     // loop over the sequences and pad with gaps where required
1104     for (int s = 0, ns = al.getHeight(); s < ns; s++)
1105     {
1106       SequenceI sqobj = al.getSequenceAt(s);
1107       if (sqobj != profileseq)
1108       {
1109         String sq = al.getSequenceAt(s).getSequenceAsString();
1110         if (sq.length() <= pos)
1111         {
1112           // pad sequence
1113           int diff = pos - sq.length() - 1;
1114           if (diff > 0)
1115           {
1116             // pad gaps
1117             sq = sq + sb;
1118             while ((diff = pos - sq.length() - 1) > 0)
1119             {
1120               if (diff >= sb.length())
1121               {
1122                 sq += sb.toString();
1123               }
1124               else
1125               {
1126                 char[] buf = new char[diff];
1127                 sb.getChars(0, diff, buf, 0);
1128                 sq += buf.toString();
1129               }
1130             }
1131           }
1132           sq += sb.toString();
1133         }
1134         else
1135         {
1136           al.getSequenceAt(s).setSequence(
1137                   sq.substring(0, pos) + sb.toString() + sq.substring(pos));
1138         }
1139       }
1140     }
1141   }
1142
1143   /**
1144    * Returns a hashCode built from hidden column ranges
1145    */
1146   @Override
1147   public int hashCode()
1148   {
1149     try
1150     {
1151       LOCK.readLock().lock();
1152       int hashCode = 1;
1153       Iterator<int[]> it = hiddenColumns.iterator();
1154       while (it.hasNext())
1155       {
1156         int[] hidden = it.next();
1157         hashCode = HASH_MULTIPLIER * hashCode + hidden[0];
1158         hashCode = HASH_MULTIPLIER * hashCode + hidden[1];
1159       }
1160       return hashCode;
1161     } finally
1162     {
1163       LOCK.readLock().unlock();
1164     }
1165   }
1166
1167   /**
1168    * Hide columns corresponding to the marked bits
1169    *
1170    * @param inserts
1171    *          - columns map to bits starting from zero
1172    */
1173   public void hideMarkedBits(BitSet inserts)
1174   {
1175     try
1176     {
1177       LOCK.writeLock().lock();
1178       for (int firstSet = inserts
1179               .nextSetBit(0), lastSet = 0; firstSet >= 0; firstSet = inserts
1180                       .nextSetBit(lastSet))
1181       {
1182         lastSet = inserts.nextClearBit(firstSet);
1183         hideColumns(firstSet, lastSet - 1);
1184       }
1185       cursor.resetCursor(hiddenColumns);
1186     } finally
1187     {
1188       LOCK.writeLock().unlock();
1189     }
1190   }
1191
1192   /**
1193    *
1194    * @param inserts
1195    *          BitSet where hidden columns will be marked
1196    */
1197   public void markHiddenRegions(BitSet inserts)
1198   {
1199     try
1200     {
1201       LOCK.readLock().lock();
1202       if (hiddenColumns == null)
1203       {
1204         return;
1205       }
1206       Iterator<int[]> it = hiddenColumns.iterator();
1207       while (it.hasNext())
1208       {
1209         int[] range = it.next();
1210         inserts.set(range[0], range[1] + 1);
1211       }
1212     } finally
1213     {
1214       LOCK.readLock().unlock();
1215     }
1216   }
1217
1218   /**
1219    * Calculate the visible start and end index of an alignment.
1220    *
1221    * @param width
1222    *          full alignment width
1223    * @return integer array where: int[0] = startIndex, and int[1] = endIndex
1224    */
1225   public int[] getVisibleStartAndEndIndex(int width)
1226   {
1227     try
1228     {
1229       LOCK.readLock().lock();
1230       int[] alignmentStartEnd = new int[] { 0, width - 1 };
1231       int startPos = alignmentStartEnd[0];
1232       int endPos = alignmentStartEnd[1];
1233
1234       int[] lowestRange = new int[] { -1, -1 };
1235       int[] higestRange = new int[] { -1, -1 };
1236
1237       if (hiddenColumns == null)
1238       {
1239         return new int[] { startPos, endPos };
1240       }
1241
1242       Iterator<int[]> it = hiddenColumns.iterator();
1243       while (it.hasNext())
1244       {
1245         int[] range = it.next();
1246         lowestRange = (range[0] <= startPos) ? range : lowestRange;
1247         higestRange = (range[1] >= endPos) ? range : higestRange;
1248       }
1249
1250       if (lowestRange[0] == -1 && lowestRange[1] == -1)
1251       {
1252         startPos = alignmentStartEnd[0];
1253       }
1254       else
1255       {
1256         startPos = lowestRange[1] + 1;
1257       }
1258
1259       if (higestRange[0] == -1 && higestRange[1] == -1)
1260       {
1261         endPos = alignmentStartEnd[1];
1262       }
1263       else
1264       {
1265         endPos = higestRange[0] - 1;
1266       }
1267       return new int[] { startPos, endPos };
1268     } finally
1269     {
1270       LOCK.readLock().unlock();
1271     }
1272   }
1273
1274   /**
1275    * Finds the hidden region (if any) which starts or ends at res
1276    *
1277    * @param res
1278    *          visible residue position, unadjusted for hidden columns
1279    * @return region as [start,end] or null if no matching region is found
1280    */
1281   public int[] getRegionWithEdgeAtRes(int res)
1282   {
1283     try
1284     {
1285       LOCK.readLock().lock();
1286       int adjres = adjustForHiddenColumns(res);
1287
1288       int[] reveal = null;
1289       Iterator<int[]> it = new RegionsIterator(adjres - 2,
1290               adjres + 2, hiddenColumns, cursor);
1291       while (it.hasNext())
1292       {
1293         int[] region = it.next();
1294         if (adjres + 1 == region[0] || adjres - 1 == region[1])
1295         {
1296           reveal = region;
1297           break;
1298         }
1299       }
1300       return reveal;
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)
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 }