[jalview.git] / src / jalview / datamodel / HiddenColumns.java

/*
 * Jalview - A Sequence Alignment Editor and Viewer ($$Version-Rel$$)
 * Copyright (C) $$Year-Rel$$ The Jalview Authors
 * 
 * This file is part of Jalview.
 * 
 * Jalview is free software: you can redistribute it and/or
 * modify it under the terms of the GNU General Public License 
 * as published by the Free Software Foundation, either version 3
 * of the License, or (at your option) any later version.
 *  
 * Jalview is distributed in the hope that it will be useful, but 
 * WITHOUT ANY WARRANTY; without even the implied warranty 
 * of MERCHANTABILITY or FITNESS FOR A PARTICULAR 
 * PURPOSE.  See the GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with Jalview.  If not, see <http://www.gnu.org/licenses/>.
 * The Jalview Authors are detailed in the 'AUTHORS' file.
 */
package jalview.datamodel;

import java.util.ArrayList;
import java.util.BitSet;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.concurrent.locks.ReentrantReadWriteLock;

public class HiddenColumns
{
  private static final int HASH_MULTIPLIER = 31;

  private static final ReentrantReadWriteLock LOCK = new ReentrantReadWriteLock();

  /*
   * list of hidden column [start, end] ranges; the list is maintained in
   * ascending start column order
   */
  private ArrayList<int[]> hiddenColumns;

  /**
   * Constructor
   */
  public HiddenColumns()
  {
  }

  /**
   * Copy constructor
   * 
   * @param copy
   */
  public HiddenColumns(HiddenColumns copy)
  {
    try
    {
      LOCK.writeLock().lock();
      if (copy != null)
      {
        if (copy.hiddenColumns != null)
        {
          hiddenColumns = new ArrayList<>();
          Iterator<int[]> it = copy.iterator();
          while (it.hasNext())
          {
            hiddenColumns.add(it.next());
          }
        }
      }
    } finally
    {
      LOCK.writeLock().unlock();
    }
  }

  /**
   * Copy constructor within bounds and with offset. Copies hidden column
   * regions fully contained between start and end, and offsets positions by
   * subtracting offset.
   * 
   * @param copy
   *          HiddenColumns instance to copy from
   * @param start
   *          lower bound to copy from
   * @param end
   *          upper bound to copy to
   * @param offset
   *          offset to subtract from each region boundary position
   * 
   */
  public HiddenColumns(HiddenColumns copy, int start, int end, int offset)
  {
    try
    {
      LOCK.writeLock().lock();
      if (copy != null)
      {
        hiddenColumns = new ArrayList<>();
        Iterator<int[]> it = copy.getBoundedIterator(start, end);
        while (it.hasNext())
        {
          int[] region = it.next();
          // still need to check boundaries because iterator returns
          // all overlapping regions and we need contained regions
          if (region[0] >= start && region[1] <= end)
          {
            hiddenColumns.add(
                    new int[]
            { region[0] - offset, region[1] - offset });
          }
        }
      }
    } finally
    {
      LOCK.writeLock().unlock();
    }
  }

  /**
   * Output regions data as a string. String is in the format:
   * reg0[0]<between>reg0[1]<delimiter>reg1[0]<between>reg1[1] ... regn[1]
   * 
   * @param delimiter
   *          string to delimit regions
   * @param betweenstring
   *          to put between start and end region values
   * @return regions formatted according to delimiter and between strings
   */
  public String regionsToString(String delimiter, String between)
  {
    try
    {
      LOCK.readLock().lock();
      StringBuilder regionBuilder = new StringBuilder();
      if (hiddenColumns != null)
      {
        Iterator<int[]> it = hiddenColumns.iterator();
        while (it.hasNext())
        {
          int[] range = it.next();
          regionBuilder.append(delimiter).append(range[0]).append(between)
                  .append(range[1]);
          if (!it.hasNext())
          {
            regionBuilder.deleteCharAt(0);
          }
        }
      }
      return regionBuilder.toString();
    } finally
    {
      LOCK.readLock().unlock();
    }
  }

  /**
   * Find the number of hidden columns
   * 
   * @return number of hidden columns
   */
  public int getSize()
  {
    try
    {
      LOCK.readLock().lock();
      int size = 0;
      if (hiddenColumns != null)
      {
        Iterator<int[]> it = hiddenColumns.iterator();
        while (it.hasNext())
        {
          int[] range = it.next();
          size += range[1] - range[0] + 1;
        }
      }
      return size;
    } finally
    {
      LOCK.readLock().unlock();
    }
  }

  /**
   * Get the number of distinct hidden regions
   * 
   * @return number of regions
   */
  public int getNumberOfRegions()
  {
    try
    {
      LOCK.readLock().lock();
      int num = 0;
      if (hasHiddenColumns())
      {
        num = hiddenColumns.size();
      }
      return num;
    } finally
    {
      LOCK.readLock().unlock();
    }
  }

  @Override
  public boolean equals(Object obj)
  {
    try
    {
      LOCK.readLock().lock();

      if (!(obj instanceof HiddenColumns))
      {
        return false;
      }
      HiddenColumns that = (HiddenColumns) obj;

      /*
       * check hidden columns are either both null, or match
       */
      if (this.hiddenColumns == null)
      {
        return (that.hiddenColumns == null);
      }
      if (that.hiddenColumns == null
              || that.hiddenColumns.size() != this.hiddenColumns.size())
      {
        return false;
      }

      Iterator<int[]> it = hiddenColumns.iterator();
      Iterator<int[]> thatit = that.iterator();
      while (it.hasNext())
      {
        int[] thisRange = it.next();
        int[] thatRange = thatit.next();
        if (thisRange[0] != thatRange[0] || thisRange[1] != thatRange[1])
        {
          return false;
        }
      }
      return true;
    } finally
    {
      LOCK.readLock().unlock();
    }
  }

  /**
   * Return absolute column index for a visible column index
   * 
   * @param column
   *          int column index in alignment view (count from zero)
   * @return alignment column index for column
   */
  public int adjustForHiddenColumns(int column)
  {
    try
    {
      LOCK.readLock().lock();
      int result = column;

      if (hiddenColumns != null)
      {
        Iterator<int[]> it = hiddenColumns.iterator();
        while (it.hasNext())
        {
          int[] region = it.next();
          if (result >= region[0])
          {
            result += region[1] - region[0] + 1;
          }
        }
      }

      return result;
    } finally
    {
      LOCK.readLock().unlock();
    }
  }

  /**
   * Use this method to find out where a column will appear in the visible
   * alignment when hidden columns exist. If the column is not visible, then the
   * left-most visible column will always be returned.
   * 
   * @param hiddenColumn
   *          the column index in the full alignment including hidden columns
   * @return the position of the column in the visible alignment
   */
  public int findColumnPosition(int hiddenColumn)
  {
    try
    {
      LOCK.readLock().lock();
      int result = hiddenColumn;
      int[] region = null;
      if (hiddenColumns != null)
      {
        Iterator<int[]> it = new RegionsIterator(0,
                hiddenColumn);
        while (it.hasNext())
        {
          region = it.next();
          if (hiddenColumn > region[1])
          {
            result -= region[1] + 1 - region[0];
          }
        }

        if (region != null && hiddenColumn >= region[0]
                && hiddenColumn <= region[1])
        {
          // Here the hidden column is within a region, so
          // we want to return the position of region[0]-1, adjusted for any
          // earlier hidden columns.
          // Calculate the difference between the actual hidden col position
          // and region[0]-1, and then subtract from result to convert result
          // from the adjusted hiddenColumn value to the adjusted region[0]-1
          // value.

          // However, if the region begins at 0 we cannot return region[0]-1
          // just return 0
          if (region[0] == 0)
          {
            return 0;
          }
          else
          {
            return result - (hiddenColumn - region[0] + 1);
          }
        }
      }
      return result; // return the shifted position after removing hidden
                     // columns.
    } finally
    {
      LOCK.readLock().unlock();
    }
  }

  /**
   * Find the visible column which is a given visible number of columns to the
   * left of another visible column. i.e. for a startColumn x, the column which
   * is distance 1 away will be column x-1.
   * 
   * @param visibleDistance
   *          the number of visible columns to offset by
   * @param startColumn
   *          the column to start from
   * @return the position of the column in the visible alignment
   */
  public int subtractVisibleColumns(int visibleDistance, int startColumn)
  {
    try
    {
      LOCK.readLock().lock();
      int distance = visibleDistance;

      // in case startColumn is in a hidden region, move it to the left
      int start = adjustForHiddenColumns(findColumnPosition(startColumn));

      Iterator<int[]> it = new ReverseRegionsIterator(0, start);

      while (it.hasNext() && (distance > 0))
      {
        int[] region = it.next();

        if (start > region[1])
        {
          // subtract the gap to right of region from distance
          if (start - region[1] <= distance)
          {
            distance -= start - region[1];
            start = region[0] - 1;
          }
          else
          {
            start = start - distance;
            distance = 0;
          }
        }
      }

      return start - distance;

    } finally
    {
      LOCK.readLock().unlock();
    }
  }

  /**
   * This method returns the rightmost limit of a region of an alignment with
   * hidden columns. In otherwords, the next hidden column.
   * 
   * @param alPos
   *          the (visible) alignmentPosition to find the next hidden column for
   */
  public int getHiddenBoundaryRight(int alPos)
  {
    try
    {
      LOCK.readLock().lock();
      if (hiddenColumns != null)
      {
        Iterator<int[]> it = hiddenColumns.iterator();
        while (it.hasNext())
        {
          int[] region = it.next();
          if (alPos < region[0])
          {
            return region[0];
          }
        }
      }
      return alPos;
    } finally
    {
      LOCK.readLock().unlock();
    }
  }

  /**
   * This method returns the leftmost limit of a region of an alignment with
   * hidden columns. In otherwords, the previous hidden column.
   * 
   * @param alPos
   *          the (visible) alignmentPosition to find the previous hidden column
   *          for
   */
  public int getHiddenBoundaryLeft(int alPos)
  {
    try
    {
      LOCK.readLock().lock();

      Iterator<int[]> it = new ReverseRegionsIterator(0, alPos);
      while (it.hasNext())
      {
        int[] region = it.next();
        if (alPos > region[1])
        {
          return region[1];
        }
      }

      return alPos;
    } finally
    {
      LOCK.readLock().unlock();
    }
  }

  /**
   * Adds the specified column range to the hidden columns collection
   * 
   * @param start
   *          start of range to add (absolute position in alignment)
   * @param end
   *          end of range to add (absolute position in alignment)
   */
  public void hideColumns(int start, int end)
  {
    boolean wasAlreadyLocked = false;
    try
    {
      // check if the write lock was already locked by this thread,
      // as this method can be called internally in loops within HiddenColumns
      if (!LOCK.isWriteLockedByCurrentThread())
      {
        LOCK.writeLock().lock();
      }
      else
      {
        wasAlreadyLocked = true;
      }

      if (hiddenColumns == null)
      {
        hiddenColumns = new ArrayList<>();
      }

      /*
       * new range follows everything else; check first to avoid looping over whole hiddenColumns collection
       */
      if (hiddenColumns.isEmpty()
              || start > hiddenColumns.get(hiddenColumns.size() - 1)[1])
      {
        hiddenColumns.add(new int[] { start, end });
      }
      else
      {
        /*
         * traverse existing hidden ranges and insert / amend / append as
         * appropriate
         */
        boolean added = false;
        for (int i = 0; !added && i < hiddenColumns.size(); i++)
        {
          added = insertRangeAtRegion(i, start, end);
        } // for
      }
    } finally
    {
      if (!wasAlreadyLocked)
      {
        LOCK.writeLock().unlock();
      }
    }
  }

  /**
   * Insert [start, range] at the region at index i in hiddenColumns, if
   * feasible
   * 
   * @param i
   *          index to insert at
   * @param start
   *          start of range to insert
   * @param end
   *          end of range to insert
   * @return true if range was successfully inserted
   */
  private boolean insertRangeAtRegion(int i, int start, int end)
  {
    boolean added = false;

    int[] region = hiddenColumns.get(i);
    if (end < region[0] - 1)
    {
      /*
       * insert discontiguous preceding range
       */
      hiddenColumns.add(i, new int[] { start, end });
      added = true;
    }
    else if (end <= region[1])
    {
      /*
       * new range overlaps existing, or is contiguous preceding it - adjust
       * start column
       */
      region[0] = Math.min(region[0], start);
      added = true;
    }
    else if (start <= region[1] + 1)
    {
      /*
       * new range overlaps existing, or is contiguous following it - adjust
       * start and end columns
       */
      region[0] = Math.min(region[0], start);
      region[1] = Math.max(region[1], end);

      /*
       * also update or remove any subsequent ranges 
       * that are overlapped
       */
      while (i < hiddenColumns.size() - 1)
      {
        int[] nextRegion = hiddenColumns.get(i + 1);
        if (nextRegion[0] > end + 1)
        {
          /*
           * gap to next hidden range - no more to update
           */
          break;
        }
        region[1] = Math.max(nextRegion[1], end);
        hiddenColumns.subList(i + 1, i + 2).clear();
      }
      added = true;
    }
    return added;
  }

  /**
   * Answers if a column in the alignment is visible
   * 
   * @param column
   *          absolute position of column in the alignment
   * @return true if column is visible
   */
  public boolean isVisible(int column)
  {
    try
    {
      LOCK.readLock().lock();

      Iterator<int[]> it = new RegionsIterator(column, column);
      while (it.hasNext())
      {
        int[] region = it.next();
        if (column >= region[0] && column <= region[1])
        {
          return false;
        }
      }

      return true;
    } finally
    {
      LOCK.readLock().unlock();
    }
  }

  /**
   * Get the visible sections of a set of sequences
   * 
   * @param start
   *          sequence position to start from
   * @param end
   *          sequence position to end at
   * @param seqs
   *          an array of sequences
   * @return an array of strings encoding the visible parts of each sequence
   */
  public String[] getVisibleSequenceStrings(int start, int end,
          SequenceI[] seqs)
  {
    try
    {
      LOCK.readLock().lock();
      int iSize = seqs.length;
      String[] selections = new String[iSize];
      if (hiddenColumns != null && hiddenColumns.size() > 0)
      {
        for (int i = 0; i < iSize; i++)
        {
          StringBuffer visibleSeq = new StringBuffer();

          Iterator<int[]> blocks = new VisibleContigsIterator(start,
                  end + 1, false);

          while (blocks.hasNext())
          {
            int[] block = blocks.next();
            if (blocks.hasNext())
            {
              visibleSeq
                      .append(seqs[i].getSequence(block[0], block[1] + 1));
            }
            else
            {
              visibleSeq
                      .append(seqs[i].getSequence(block[0], block[1]));
            }
          }

          selections[i] = visibleSeq.toString();
        }
      }
      else
      {
        for (int i = 0; i < iSize; i++)
        {
          selections[i] = seqs[i].getSequenceAsString(start, end);
        }
      }

      return selections;
    } finally
    {
      LOCK.readLock().unlock();
    }
  }

  /**
   * Locate the first position visible for this sequence. If seq isn't visible
   * then return the position of the left side of the hidden boundary region.
   * 
   * @param seq
   *          sequence to find position for
   * @return visible start position
   */
  public int locateVisibleStartOfSequence(SequenceI seq)
  {
    try
    {
      LOCK.readLock().lock();
      int start = 0;

      if (hiddenColumns == null || hiddenColumns.size() == 0)
      {
        return seq.findIndex(seq.getStart()) - 1;
      }

      // Simply walk along the sequence whilst watching for hidden column
      // boundaries
      Iterator<int[]> regions = hiddenColumns.iterator();
      int hideStart = seq.getLength();
      int hideEnd = -1;
      int visPrev = 0;
      int visNext = 0;
      boolean foundStart = false;

      // step through the non-gapped positions of the sequence
      for (int i = seq.getStart(); i <= seq.getEnd() && (!foundStart); i++)
      {
        // get alignment position of this residue in the sequence
        int p = seq.findIndex(i) - 1;

        // update hidden region start/end
        while (hideEnd < p && regions.hasNext())
        {
          int[] region = regions.next();
          visPrev = visNext;
          visNext += region[0] - visPrev;
          hideStart = region[0];
          hideEnd = region[1];
        }
        if (hideEnd < p)
        {
          hideStart = seq.getLength();
        }
        // update visible boundary for sequence
        if (p < hideStart)
        {
          start = p;
          foundStart = true;
        }
      }

      if (foundStart)
      {
        return findColumnPosition(start);
      }
      // otherwise, sequence was completely hidden
      return visPrev;
    } finally
    {
      LOCK.readLock().unlock();
    }
  }

  /**
   * delete any columns in alignmentAnnotation that are hidden (including
   * sequence associated annotation).
   * 
   * @param alignmentAnnotation
   */
  public void makeVisibleAnnotation(AlignmentAnnotation alignmentAnnotation)
  {
    makeVisibleAnnotation(0, alignmentAnnotation.annotations.length,
            alignmentAnnotation);
  }

  /**
   * delete any columns in alignmentAnnotation that are hidden (including
   * sequence associated annotation).
   * 
   * @param start
   *          remove any annotation to the right of this column
   * @param end
   *          remove any annotation to the left of this column
   * @param alignmentAnnotation
   *          the annotation to operate on
   */
  public void makeVisibleAnnotation(int start, int end,
          AlignmentAnnotation alignmentAnnotation)
  {
    try
    {
      LOCK.readLock().lock();

      int startFrom = start;
      int endAt = end;

      if (alignmentAnnotation.annotations != null)
      {
        if (hiddenColumns != null && hiddenColumns.size() > 0)
        {
          removeHiddenAnnotation(startFrom, endAt, alignmentAnnotation);
        }
        else
        {
          alignmentAnnotation.restrict(startFrom, endAt);
        }
      }
    } finally
    {
      LOCK.readLock().unlock();
    }
  }

  private void removeHiddenAnnotation(int start, int end,
          AlignmentAnnotation alignmentAnnotation)
  {
    // mangle the alignmentAnnotation annotation array
    ArrayList<Annotation[]> annels = new ArrayList<>();
    Annotation[] els = null;

    int w = 0;
    
    Iterator<int[]> blocks = new VisibleContigsIterator(start, end + 1,
            false);

    int copylength;
    int annotationLength;
    while (blocks.hasNext())
    {
      int[] block = blocks.next();
      annotationLength = block[1] - block[0] + 1;
    
      if (blocks.hasNext())
      {
        // copy just the visible segment of the annotation row
        copylength = annotationLength;
      }
      else
      {
        if (annotationLength + block[0] <= alignmentAnnotation.annotations.length)
        {
          // copy just the visible segment of the annotation row
          copylength = annotationLength;
        }
        else
        {
          // copy to the end of the annotation row
          copylength = alignmentAnnotation.annotations.length - block[0];
        }
      }
      
      els = new Annotation[annotationLength];
      annels.add(els);
      System.arraycopy(alignmentAnnotation.annotations, block[0], els, 0,
              copylength);
      w += annotationLength;
    }
    
    if (w != 0)
    {
      alignmentAnnotation.annotations = new Annotation[w];

      w = 0;
      for (Annotation[] chnk : annels)
      {
        System.arraycopy(chnk, 0, alignmentAnnotation.annotations, w,
                chnk.length);
        w += chnk.length;
      }
    }
  }

  /**
   * 
   * @return true if there are columns hidden
   */
  public boolean hasHiddenColumns()
  {
    try
    {
      LOCK.readLock().lock();
      return hiddenColumns != null && hiddenColumns.size() > 0;
    } finally
    {
      LOCK.readLock().unlock();
    }
  }

  /**
   * 
   * @return true if there are more than one set of columns hidden
   */
  public boolean hasManyHiddenColumns()
  {
    try
    {
      LOCK.readLock().lock();
      return hiddenColumns != null && hiddenColumns.size() > 1;
    } finally
    {
      LOCK.readLock().unlock();
    }
  }

  /**
   * mark the columns corresponding to gap characters as hidden in the column
   * selection
   * 
   * @param sr
   */
  public void hideInsertionsFor(SequenceI sr)
  {
    try
    {
      LOCK.writeLock().lock();
      List<int[]> inserts = sr.getInsertions();
      for (int[] r : inserts)
      {
        hideColumns(r[0], r[1]);
      }
    } finally
    {
      LOCK.writeLock().unlock();
    }
  }

  /**
   * Unhides, and adds to the selection list, all hidden columns
   */
  public void revealAllHiddenColumns(ColumnSelection sel)
  {
    try
    {
      LOCK.writeLock().lock();
      if (hiddenColumns != null)
      {
        Iterator<int[]> it = hiddenColumns.iterator();
        while (it.hasNext())
        {
          int[] region = it.next();
          for (int j = region[0]; j < region[1] + 1; j++)
          {
            sel.addElement(j);
          }
        }
        hiddenColumns = null;
      }
    } finally
    {
      LOCK.writeLock().unlock();
    }
  }

  /**
   * Reveals, and marks as selected, the hidden column range with the given
   * start column
   * 
   * @param start
   */
  public void revealHiddenColumns(int start, ColumnSelection sel)
  {
    try
    {
      LOCK.writeLock().lock();
      Iterator<int[]> it = new RegionsIterator(start, start);
      while (it.hasNext())
      {
        int[] region = it.next();
        if (start == region[0])
        {
          for (int j = region[0]; j < region[1] + 1; j++)
          {
            sel.addElement(j);
          }
          it.remove();
          break;
        }
        else if (start < region[0])
        {
          break; // passed all possible matching regions
        }
      }

      if (hiddenColumns.size() == 0)
      {
        hiddenColumns = null;
      }
    } finally
    {
      LOCK.writeLock().unlock();
    }
  }

  /**
   * Add gaps into the sequences aligned to profileseq under the given
   * AlignmentView
   * 
   * @param profileseq
   * @param al
   *          - alignment to have gaps inserted into it
   * @param input
   *          - alignment view where sequence corresponding to profileseq is
   *          first entry
   * @return new HiddenColumns for new alignment view, with insertions into
   *         profileseq marked as hidden.
   */
  public static HiddenColumns propagateInsertions(SequenceI profileseq,
          AlignmentI al, AlignmentView input)
  {
    int profsqpos = 0;

    char gc = al.getGapCharacter();
    Object[] alandhidden = input.getAlignmentAndHiddenColumns(gc);
    HiddenColumns nview = (HiddenColumns) alandhidden[1];
    SequenceI origseq = ((SequenceI[]) alandhidden[0])[profsqpos];
    nview.propagateInsertions(profileseq, al, origseq);
    return nview;
  }

  /**
   * 
   * @param profileseq
   *          - sequence in al which corresponds to origseq
   * @param al
   *          - alignment which is to have gaps inserted into it
   * @param origseq
   *          - sequence corresponding to profileseq which defines gap map for
   *          modifying al
   */
  private void propagateInsertions(SequenceI profileseq, AlignmentI al,
          SequenceI origseq)
  {
    try
    {
      LOCK.writeLock().lock();

      char gc = al.getGapCharacter();

      // take the set of hidden columns, and the set of gaps in origseq,
      // and remove all the hidden gaps from hiddenColumns

      // first get the gaps as a Bitset
      BitSet gaps = origseq.gapBitset();

      // now calculate hidden ^ not(gap)
      BitSet hidden = new BitSet();
      markHiddenRegions(hidden);
      hidden.andNot(gaps);
      hiddenColumns = null;
      this.hideMarkedBits(hidden);

      // for each sequence in the alignment, except the profile sequence,
      // insert gaps corresponding to each hidden region
      // but where each hidden column region is shifted backwards by the number
      // of
      // preceding visible gaps
      // update hidden columns at the same time
      Iterator<int[]> regions = hiddenColumns.iterator();
      ArrayList<int[]> newhidden = new ArrayList<>();

      int numGapsBefore = 0;
      int gapPosition = 0;
      while (regions.hasNext())
      {
        // get region coordinates accounting for gaps
        // we can rely on gaps not being *in* hidden regions because we already
        // removed those
        int[] region = regions.next();
        while (gapPosition < region[0])
        {
          gapPosition++;
          if (gaps.get(gapPosition))
          {
            numGapsBefore++;
          }
        }

        int left = region[0] - numGapsBefore;
        int right = region[1] - numGapsBefore;
        newhidden.add(new int[] { left, right });

        // make a string with number of gaps = length of hidden region
        StringBuffer sb = new StringBuffer();
        for (int s = 0; s < right - left + 1; s++)
        {
          sb.append(gc);
        }
        padGaps(sb, left, profileseq, al);

      }
      hiddenColumns = newhidden;
    } finally
    {
      LOCK.writeLock().unlock();
    }
  }

  /**
   * Pad gaps in all sequences in alignment except profileseq
   * 
   * @param sb
   *          gap string to insert
   * @param left
   *          position to insert at
   * @param profileseq
   *          sequence not to pad
   * @param al
   *          alignment to pad sequences in
   */
  private void padGaps(StringBuffer sb, int pos, SequenceI profileseq,
          AlignmentI al)
  {
    // loop over the sequences and pad with gaps where required
    for (int s = 0, ns = al.getHeight(); s < ns; s++)
    {
      SequenceI sqobj = al.getSequenceAt(s);
      if (sqobj != profileseq)
      {
        String sq = al.getSequenceAt(s).getSequenceAsString();
        if (sq.length() <= pos)
        {
          // pad sequence
          int diff = pos - sq.length() - 1;
          if (diff > 0)
          {
            // pad gaps
            sq = sq + sb;
            while ((diff = pos - sq.length() - 1) > 0)
            {
              if (diff >= sb.length())
              {
                sq += sb.toString();
              }
              else
              {
                char[] buf = new char[diff];
                sb.getChars(0, diff, buf, 0);
                sq += buf.toString();
              }
            }
          }
          sq += sb.toString();
        }
        else
        {
          al.getSequenceAt(s).setSequence(
                  sq.substring(0, pos) + sb.toString() + sq.substring(pos));
        }
      }
    }
  }

  /**
   * Returns a hashCode built from hidden column ranges
   */
  @Override
  public int hashCode()
  {
    try
    {
      LOCK.readLock().lock();
      int hashCode = 1;
      Iterator<int[]> it = hiddenColumns.iterator();
      while (it.hasNext())
      {
        int[] hidden = it.next();
        hashCode = HASH_MULTIPLIER * hashCode + hidden[0];
        hashCode = HASH_MULTIPLIER * hashCode + hidden[1];
      }
      return hashCode;
    } finally
    {
      LOCK.readLock().unlock();
    }
  }

  /**
   * Hide columns corresponding to the marked bits
   * 
   * @param inserts
   *          - columns map to bits starting from zero
   */
  public void hideMarkedBits(BitSet inserts)
  {
    try
    {
      LOCK.writeLock().lock();
      for (int firstSet = inserts
              .nextSetBit(0), lastSet = 0; firstSet >= 0; firstSet = inserts
                      .nextSetBit(lastSet))
      {
        lastSet = inserts.nextClearBit(firstSet);
        hideColumns(firstSet, lastSet - 1);
      }
    } finally
    {
      LOCK.writeLock().unlock();
    }
  }

  /**
   * 
   * @param inserts
   *          BitSet where hidden columns will be marked
   */
  public void markHiddenRegions(BitSet inserts)
  {
    try
    {
      LOCK.readLock().lock();
      if (hiddenColumns == null)
      {
        return;
      }
      Iterator<int[]> it = hiddenColumns.iterator();
      while (it.hasNext())
      {
        int[] range = it.next();
        inserts.set(range[0], range[1] + 1);
      }
    } finally
    {
      LOCK.readLock().unlock();
    }
  }

  /**
   * Calculate the visible start and end index of an alignment.
   * 
   * @param width
   *          full alignment width
   * @return integer array where: int[0] = startIndex, and int[1] = endIndex
   */
  public int[] getVisibleStartAndEndIndex(int width)
  {
    try
    {
      LOCK.readLock().lock();
      int[] alignmentStartEnd = new int[] { 0, width - 1 };
      int startPos = alignmentStartEnd[0];
      int endPos = alignmentStartEnd[1];

      int[] lowestRange = new int[] { -1, -1 };
      int[] higestRange = new int[] { -1, -1 };

      if (hiddenColumns == null)
      {
        return new int[] { startPos, endPos };
      }

      Iterator<int[]> it = hiddenColumns.iterator();
      while (it.hasNext())
      {
        int[] range = it.next();
        lowestRange = (range[0] <= startPos) ? range : lowestRange;
        higestRange = (range[1] >= endPos) ? range : higestRange;
      }

      if (lowestRange[0] == -1 && lowestRange[1] == -1)
      {
        startPos = alignmentStartEnd[0];
      }
      else
      {
        startPos = lowestRange[1] + 1;
      }

      if (higestRange[0] == -1 && higestRange[1] == -1)
      {
        endPos = alignmentStartEnd[1];
      }
      else
      {
        endPos = higestRange[0] - 1;
      }
      return new int[] { startPos, endPos };
    } finally
    {
      LOCK.readLock().unlock();
    }

  }

  /**
   * Finds the hidden region (if any) which starts or ends at res
   * 
   * @param res
   *          visible residue position, unadjusted for hidden columns
   * @return region as [start,end] or null if no matching region is found
   */
  public int[] getRegionWithEdgeAtRes(int res)
  {
    try
    {
      LOCK.readLock().lock();
      int adjres = adjustForHiddenColumns(res);

      int[] reveal = null;
      Iterator<int[]> it = new RegionsIterator(adjres - 2,
              adjres + 2);
      while (it.hasNext())
      {
        int[] region = it.next();
        if (adjres + 1 == region[0] || adjres - 1 == region[1])
        {
          reveal = region;
          break;
        }
      }
      return reveal;
    } finally
    {
      LOCK.readLock().unlock();
    }
  }

  /**
   * Return an iterator over the hidden regions
   */
  public Iterator<int[]> iterator()
  {
    return new BoundedHiddenColsIterator();
  }

  /**
   * Return a bounded iterator over the hidden regions
   * 
   * @param start
   *          position to start from (inclusive, absolute column position)
   * @param end
   *          position to end at (inclusive, absolute column position)
   * @return
   */
  public Iterator<int[]> getBoundedIterator(int start, int end)
  {
    return new BoundedHiddenColsIterator(start, end);
  }

  /**
   * Return a bounded iterator over the *visible* start positions of hidden
   * regions
   * 
   * @param start
   *          position to start from (inclusive, visible column position)
   * @param end
   *          position to end at (inclusive, visible column position)
   */
  public Iterator<Integer> getBoundedStartIterator(int start, int end)
  {
    return new BoundedStartRegionIterator(start, end, true);
  }

  /**
   * Return an iterator over visible *columns* (not regions) between the given
   * start and end boundaries
   * 
   * @param start
   *          first column (inclusive)
   * @param end
   *          last column (inclusive)
   */
  public Iterator<Integer> getVisibleColsIterator(int start, int end)
  {
    return new VisibleColsIterator(start, end);
  }

  /**
   * return an iterator over visible segments between the given start and end
   * boundaries
   * 
   * @param start
   *          (first column inclusive from 0)
   * @param end
   *          (last column - not inclusive)
   */
  public Iterator<int[]> getVisContigsIterator(int start, int end)
  {
    // return new VisibleBlocksIterator(start, end, true)
    return new VisibleContigsIterator(start, end, true);
  }

  /**
   * return an iterator over visible segments between the given start and end
   * boundaries
   * 
   * @param start
   *          (first column - inclusive from 0)
   * @param end
   *          (last column - inclusive)
   * @param useVisibleCoords
   *          if true, start and end are visible column positions, not absolute
   *          positions
   */
  public Iterator<int[]> getVisibleBlocksIterator(int start, int end,
          boolean useVisibleCoords)
  {
    if (useVisibleCoords)
    {
      // TODO
      // we should really just convert start and end here with
      // adjustForHiddenColumns
      // and then create a VisibleContigsIterator
      // but without a cursor this will be horribly slow in some situations
      // ... so until then...
      return new VisibleBlocksVisBoundsIterator(start, end, true);
    }
    else
    {
      return new VisibleContigsIterator(start, end + 1, true);
    }
  }

  /**
   * A local iterator which iterates over hidden column regions in a range.
   * Intended for use ONLY within the HiddenColumns class, because it works
   * directly with the hiddenColumns collection without locking (callers should
   * lock hiddenColumns).
   */
  private class RegionsIterator implements Iterator<int[]>
  {
    // start position to iterate from
    private int start;

    // end position to iterate to
    private int end;

    // current index in hiddenColumns
    private int currentPosition = 0;

    // current column in hiddenColumns
    private int[] nextRegion = null;

    private int[] currentRegion = null;

    private int removedIndex = -1;

    // Constructor with bounds
    RegionsIterator(int lowerBound, int upperBound)
    {
      start = lowerBound;
      end = upperBound;

      if (hiddenColumns != null)
      {
        // iterate until a region overlaps with [start,end]
        currentPosition = 0;
        while ((currentPosition < hiddenColumns.size())
                && (hiddenColumns.get(currentPosition)[1] < start))
        {
          currentPosition++;
        }
        if (currentPosition < hiddenColumns.size())
        {
          nextRegion = hiddenColumns.get(currentPosition);
        }
      }
    }

    @Override
    public boolean hasNext()
    {
      return (hiddenColumns != null) && (nextRegion != null)
              && (nextRegion[0] <= end);
    }

    @Override
    public int[] next()
    {
      currentRegion = nextRegion;
      currentPosition++;
      if (currentPosition < hiddenColumns.size())
      {
        nextRegion = hiddenColumns.get(currentPosition);
      }
      else
      {
        nextRegion = null;
      }
      return currentRegion;
    }

    @Override
    public void remove()
    {
      if ((currentRegion != null) && (removedIndex != currentPosition))
      {
        currentPosition--;
        hiddenColumns.subList(currentPosition, currentPosition + 1).clear();
        removedIndex = currentPosition;
      }
      else
      {
        // already removed element last returned by next()
        // or next() has not yet been called
        throw new IllegalStateException();
      }
    }

  }

  /**
   * A local iterator which reverse iterates over hidden column regions in a
   * range. Intended for use ONLY within the HiddenColumns class, because it
   * works directly with the hiddenColumns collection without locking (callers
   * should lock hiddenColumns).
   */
  private class ReverseRegionsIterator implements Iterator<int[]>
  {
    // start position to iterate to
    private int start;

    // end position to iterate from
    private int end;

    // current index in hiddenColumns
    private int currentPosition = 0;

    // current column in hiddenColumns
    private int[] nextRegion = null;

    // Constructor with bounds
    ReverseRegionsIterator(int lowerBound, int upperBound)
    {
      init(lowerBound, upperBound);
    }

    /**
     * Construct an iterator over hiddenColums bounded at
     * [lowerBound,upperBound]
     * 
     * @param lowerBound
     *          lower bound to iterate to
     * @param upperBound
     *          upper bound to iterate from
     */
    private void init(int lowerBound, int upperBound)
    {
      start = lowerBound;
      end = upperBound;

      if (hiddenColumns != null)
      {
        // iterate until a region overlaps with [start,end]
        currentPosition = hiddenColumns.size() - 1;
        while (currentPosition >= 0
                && hiddenColumns.get(currentPosition)[1] > end)
        {
          currentPosition--;
        }
        if (currentPosition >= 0)
        {
          nextRegion = hiddenColumns.get(currentPosition);
        }
      }
    }

    @Override
    public boolean hasNext()
    {
      return (hiddenColumns != null) && (nextRegion != null)
              && (nextRegion[1] >= start);
    }

    @Override
    public int[] next()
    {
      int[] region = nextRegion;
      currentPosition--;
      if (currentPosition >= 0)
      {
        nextRegion = hiddenColumns.get(currentPosition);
      }
      else
      {
        nextRegion = null;
      }
      return region;
    }

  }

  /**
   * An iterator which iterates over hidden column regions in a range. Works
   * with a copy of the hidden columns collection. Intended to be used by
   * callers OUTSIDE of HiddenColumns.
   */
  private class BoundedHiddenColsIterator implements Iterator<int[]>
  {
    // start position to iterate from
    private int start;

    // end position to iterate to
    private int end;

    // current index in hiddenColumns
    private int currentPosition = 0;

    // current column in hiddenColumns
    private int[] currentRegion;

    // local copy or reference to hiddenColumns
    private List<int[]> localHidden;

    /**
     * Unbounded constructor
     */
    BoundedHiddenColsIterator()
    {
      if (hiddenColumns != null)
      {
        int last = hiddenColumns.get(hiddenColumns.size() - 1)[1];
        init(0, last);
      }
      else
      {
        init(0, 0);
      }
    }

    /**
     * Construct an iterator over hiddenColums bounded at
     * [lowerBound,upperBound]
     * 
     * @param lowerBound
     *          lower bound to iterate from
     * @param upperBound
     *          upper bound to iterate to
     */
    BoundedHiddenColsIterator(int lowerBound, int upperBound)
    {
      init(lowerBound, upperBound);
    }

    /**
     * Construct an iterator over hiddenColums bounded at
     * [lowerBound,upperBound]
     * 
     * @param lowerBound
     *          lower bound to iterate from
     * @param upperBound
     *          upper bound to iterate to
     */
    private void init(int lowerBound, int upperBound)
    {
      start = lowerBound;
      end = upperBound;

      try
      {
        LOCK.readLock().lock();
        
        if (hiddenColumns != null)
        {
          localHidden = new ArrayList<>();

          // iterate until a region overlaps with [start,end]
          int i = 0;
          while ((i < hiddenColumns.size())
                  && (hiddenColumns.get(i)[1] < start))
          {
            i++;
          }

          // iterate from start to end, adding each hidden region. Positions are
          // absolute, and all regions which *overlap* [start,end] are added.
          while (i < hiddenColumns.size()
                  && (hiddenColumns.get(i)[0] <= end))
          {
            int[] rh = hiddenColumns.get(i);
            int[] cp = new int[2];
            System.arraycopy(rh, 0, cp, 0, rh.length);
            localHidden.add(cp);
            i++;
          }
        }
      }
      finally
      {
        LOCK.readLock().unlock();
      }
    }

    @Override
    public boolean hasNext()
    {
      return (localHidden != null)
              && (currentPosition < localHidden.size());
    }

    @Override
    public int[] next()
    {
      currentRegion = localHidden.get(currentPosition);
      currentPosition++;
      return currentRegion;
    }
  }

  /**
   * An iterator which iterates over visible start positions of hidden column
   * regions in a range.
   */
  private class BoundedStartRegionIterator implements Iterator<Integer>
  {
    // start position to iterate from
    private int start;

    // end position to iterate to
    private int end;

    // current index in hiddenColumns
    private int currentPosition = 0;

    // local copy or reference to hiddenColumns
    private List<Integer> positions = null;

    /**
     * Construct an iterator over hiddenColums bounded at
     * [lowerBound,upperBound]
     * 
     * @param lowerBound
     *          lower bound to iterate from
     * @param upperBound
     *          upper bound to iterate to
     * @param useCopyCols
     *          whether to make a local copy of hiddenColumns for iteration (set
     *          to true if calling from outwith the HiddenColumns class)
     */
    BoundedStartRegionIterator(int lowerBound, int upperBound,
            boolean useCopy)
    {
      start = lowerBound;
      end = upperBound;
      
      try
      {
        if (useCopy)
        {
          // assume that if useCopy is false the calling code has locked
          // hiddenColumns
          LOCK.readLock().lock();
        }

        if (hiddenColumns != null)
        {
          positions = new ArrayList<>(hiddenColumns.size());

          // navigate to start, keeping count of hidden columns
          int i = 0;
          int hiddenSoFar = 0;
          while ((i < hiddenColumns.size())
                  && (hiddenColumns.get(i)[0] < start + hiddenSoFar))
          {
            int[] region = hiddenColumns.get(i);
            hiddenSoFar += region[1] - region[0] + 1;
            i++;
          }

          // iterate from start to end, adding start positions of each
          // hidden region. Positions are visible columns count, not absolute
          while (i < hiddenColumns.size()
                  && (hiddenColumns.get(i)[0] <= end + hiddenSoFar))
          {
            int[] region = hiddenColumns.get(i);
            positions.add(region[0] - hiddenSoFar);
            hiddenSoFar += region[1] - region[0] + 1;
            i++;
          }
        }
        else
        {
          positions = new ArrayList<>();
        }
      } finally
      {
        if (useCopy)
        {
          LOCK.readLock().unlock();
        }
      }
    }

    @Override
    public boolean hasNext()
    {
      return (currentPosition < positions.size());
    }

    /**
     * Get next hidden region start position
     * 
     * @return the start position in *visible* coordinates
     */
    @Override
    public Integer next()
    {
      int result = positions.get(currentPosition);
      currentPosition++;
      return result;
    }
  }

  /**
   * Iterator over the visible *columns* (not regions) as determined by the set
   * of hidden columns. Uses a local copy of hidden columns.
   * 
   * @author kmourao
   *
   */
  private class VisibleColsIterator implements Iterator<Integer>
  {
    private int last;

    private int current;

    private int next;

    private List<int[]> localHidden = new ArrayList<>();

    private int nexthiddenregion;

    VisibleColsIterator(int firstcol, int lastcol)
    {
      last = lastcol;
      current = firstcol;
      next = firstcol;
      nexthiddenregion = 0;

      LOCK.readLock().lock();

      if (hiddenColumns != null)
      {
        int i = 0;
        for (i = 0; i < hiddenColumns.size()
                && (current <= hiddenColumns.get(i)[0]); ++i)
        {
          if (current >= hiddenColumns.get(i)[0]
                  && current <= hiddenColumns.get(i)[1])
          {
            // current is hidden, move to right
            current = hiddenColumns.get(i)[1] + 1;
            next = current;
            nexthiddenregion = i + 1;
          }
        }

        for (i = hiddenColumns.size() - 1; i >= 0
                && (last >= hiddenColumns.get(i)[1]); --i)
        {
          if (last >= hiddenColumns.get(i)[0]
                  && last <= hiddenColumns.get(i)[1])
          {
            // last is hidden, move to left
            last = hiddenColumns.get(i)[0] - 1;
          }
        }

        // make a local copy of the bit we need
        i = nexthiddenregion;
        while (i < hiddenColumns.size() && hiddenColumns.get(i)[0] <= last)
        {
          int[] region = new int[] { hiddenColumns.get(i)[0],
              hiddenColumns.get(i)[1] };
          localHidden.add(region);
          i++;
        }
      }

      LOCK.readLock().unlock();
    }

    @Override
    public boolean hasNext()
    {
      return next <= last;
    }

    @Override
    public Integer next()
    {
      if (next > last)
      {
        throw new NoSuchElementException();
      }
      current = next;
      if ((localHidden != null)
              && (nexthiddenregion < localHidden.size()))
      {
        // still some more hidden regions
        if (next + 1 < localHidden.get(nexthiddenregion)[0])
        {
          // next+1 is still before the next hidden region
          next++;
        }
        else if ((next + 1 >= localHidden.get(nexthiddenregion)[0])
                && (next + 1 <= localHidden.get(nexthiddenregion)[1]))
        {
          // next + 1 is in the next hidden region
          next = localHidden.get(nexthiddenregion)[1] + 1;
          nexthiddenregion++;
        }
      }
      else
      {
        // finished with hidden regions, just increment normally
        next++;
      }
      return current;
    }

    @Override
    public void remove()
    {
      throw new UnsupportedOperationException();
    }
  }

  /**
   * An iterator which iterates over visible regions in a range.
   */
  private class VisibleContigsIterator implements Iterator<int[]>
  {
    private List<int[]> vcontigs = new ArrayList<>();

    private int currentPosition = 0;

    VisibleContigsIterator(int start, int end, boolean usecopy)
    {
      try
      {
        if (usecopy)
        {
          LOCK.readLock().lock();
        }

        if (hiddenColumns != null && hiddenColumns.size() > 0)
        {
          int vstart = start;
          int hideStart;
          int hideEnd;

          for (int[] region : hiddenColumns)
          {
            hideStart = region[0];
            hideEnd = region[1];

            // navigate to start
            if (hideEnd < vstart)
            {
              continue;
            }
            if (hideStart > vstart)
            {
              int[] contig = new int[] { vstart, hideStart - 1 };
              vcontigs.add(contig);
            }
            vstart = hideEnd + 1;

            // exit if we're past the end
            if (vstart >= end)
            {
              break;
            }
          }

          if (vstart < end)
          {
            int[] contig = new int[] { vstart, end - 1 };
            vcontigs.add(contig);
          }
        }
        else
        {
          int[] contig = new int[] { start, end - 1 };
          vcontigs.add(contig);
        }
      } finally
      {
        if (usecopy)
        {
          LOCK.readLock().unlock();
        }
      }
    }

    @Override
    public boolean hasNext()
    {
      return (currentPosition < vcontigs.size());
    }

    @Override
    public int[] next()
    {
      int[] result = vcontigs.get(currentPosition);
      currentPosition++;
      return result;
    }
  }

  /**
   * An iterator which iterates over visible regions in a range. The range is
   * specified in terms of visible column positions. Provides a special
   * "endsAtHidden" indicator to allow callers to determine if the final visible
   * column is adjacent to a hidden region.
   */
  public class VisibleBlocksVisBoundsIterator implements Iterator<int[]>
  {
    private List<int[]> vcontigs = new ArrayList<>();

    private int currentPosition = 0;

    private boolean endsAtHidden = false;

    /**
     * Constructor for iterator over visible regions in a range.
     * 
     * @param start
     *          start position in terms of visible column position
     * @param end
     *          end position in terms of visible column position
     * @param usecopy
     *          whether to use a local copy of hidden columns
     */
    VisibleBlocksVisBoundsIterator(int start, int end, boolean usecopy)
    {
      /* actually this implementation always uses a local copy but this may change in future */
      try
      {
        if (usecopy)
        {
          LOCK.readLock().lock();
        }

        if (hiddenColumns != null && hiddenColumns.size() > 0)
        {
          int blockStart = start;
          int blockEnd = end;
          int hiddenSoFar = 0;
          int visSoFar = 0;

          // iterate until a region begins within (start,end]
          int i = 0;
          while ((i < hiddenColumns.size())
                  && (hiddenColumns.get(i)[0] <= blockStart + hiddenSoFar))
          {
            hiddenSoFar += hiddenColumns.get(i)[1] - hiddenColumns.get(i)[0]
                    + 1;
            i++;
          }

          blockStart += hiddenSoFar; // convert start to absolute position
          blockEnd += hiddenSoFar; // convert end to absolute position

          // iterate from start to end, adding each visible region. Positions
          // are
          // absolute, and all hidden regions which overlap [start,end] are
          // used.
          while (i < hiddenColumns.size()
                  && (hiddenColumns.get(i)[0] <= blockEnd))
          {
            int[] region = hiddenColumns.get(i);

            // end position of this visible region is either just before the
            // start of the next hidden region, or the absolute position of
            // 'end', whichever is lowest
            blockEnd = Math.min(blockEnd, region[0] - 1);

            vcontigs.add(new int[] { blockStart, blockEnd });

            visSoFar += blockEnd - blockStart + 1;

            // next visible region starts after this hidden region
            blockStart = region[1] + 1;

            hiddenSoFar += region[1] - region[0] + 1;

            // reset blockEnd to absolute position of 'end', assuming we've now
            // passed all hidden regions before end
            blockEnd = end + hiddenSoFar;

            i++;
          }
          if (visSoFar < end - start)
          {
            // the number of visible columns we've accounted for is less than
            // the number specified by end-start; work out the end position of
            // the last visible region
            blockEnd = blockStart + end - start - visSoFar;
            vcontigs.add(new int[] { blockStart, blockEnd });

            // if the last visible region ends at the next hidden region, set
            // endsAtHidden=true
            if (i < hiddenColumns.size()
                    && hiddenColumns.get(i)[0] - 1 == blockEnd)
            {
              endsAtHidden = true;
            }
          }
        }
        else
        {
          // there are no hidden columns, return a single visible contig
          vcontigs.add(new int[] { start, end });
          endsAtHidden = false;
        }
      } finally
      {
        if (usecopy)
        {
          LOCK.readLock().unlock();
        }
      }
    }

    @Override
    public boolean hasNext()
    {
      return (currentPosition < vcontigs.size());
    }

    @Override
    public int[] next()
    {
      int[] result = vcontigs.get(currentPosition);
      currentPosition++;
      return result;
    }

    public boolean endsAtHidden()
    {
      return endsAtHidden;
    }
  }
}