src/jalview/datamodel/HiddenColumns.java

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