JAL-2759 setup hideBitSet over range for hideInsertions

[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.concurrent.locks.ReentrantReadWriteLock;

/**
 * This class manages the collection of hidden columns associated with an
 * alignment. To iterate over the collection, or over visible columns/regions,
 * use an iterator obtained from one of:
 * 
 * - getBoundedIterator: iterates over the hidden regions, within some bounds,
 * returning absolute positions
 * 
 * - getBoundedStartIterator: iterates over the start positions of hidden
 * regions, within some bounds, returning visible positions
 * 
 * - getVisContigsIterator: iterates over visible regions in a range, returning
 * absolute positions
 * 
 * - getVisibleColsIterator: iterates over the visible *columns*
 * 
 * For performance reasons, provide bounds where possible. Note that column
 * numbering begins at 0 throughout this class.
 * 
 * @author kmourao
 *
 */
public class HiddenColumns
{
  private static final int HASH_MULTIPLIER = 31;

  private static final ReentrantReadWriteLock LOCK = new ReentrantReadWriteLock();

  /*
   * Cursor which tracks the last used hidden columns region, and the number 
   * of hidden columns up to (but not including) that region.
   */
  private HiddenColumnsCursor cursor = new HiddenColumnsCursor();

  /*
   * cache of the number of hidden columns
   */
  private int numColumns = 0;

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

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

  /* 
   * Methods which change the hiddenColumns collection. These methods should 
   * use a writeLock to prevent other threads accessing the hiddenColumns
   * collection while changes are being made. They should also reset the hidden
   * columns cursor, and either update the hidden columns count, or set it to 0 
   * (so that it will later be updated when needed).
   */

  /**
   * Copy constructor
   * 
   * @param copy
   *          the HiddenColumns object to copy from
   */
  public HiddenColumns(HiddenColumns copy)
  {
    this(copy, Integer.MIN_VALUE, Integer.MAX_VALUE, 0);
  }

  /**
   * 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)
      {
        numColumns = 0;
        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 });
            numColumns += region[1] - region[0] + 1;
          }
        }
        cursor.resetCursor(hiddenColumns);
      }
    } finally
    {
      LOCK.writeLock().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;
      }

      int previndex = 0;
      int prevHiddenCount = 0;
      int regionindex = 0;
      if (!hiddenColumns.isEmpty())
      {
        // set up cursor reset values
        HiddenCursorPosition cursorPos = cursor.findRegionForColumn(start);
        regionindex = cursorPos.getRegionIndex();

        if (regionindex > 0)
        {
          // get previous index and hidden count for updating the cursor later
          previndex = regionindex - 1;
          int[] prevRegion = hiddenColumns.get(previndex);
          prevHiddenCount = cursorPos.getHiddenSoFar()
                  - (prevRegion[1] - prevRegion[0] + 1);
        }
      }

      /*
       * 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;
        if (regionindex > 0)
        {
          added = insertRangeAtRegion(regionindex - 1, start, end);
        }
        if (!added && regionindex < hiddenColumns.size())
        {
          insertRangeAtRegion(regionindex, start, end);
        }
      }

      // reset the cursor to just before our insertion point: this saves
      // a lot of reprocessing in large alignments
      cursor.resetCursor(hiddenColumns, previndex, prevHiddenCount);

      // reset the number of columns so they will be recounted
      numColumns = 0;

    } 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);

        // in theory this is faster than hiddenColumns.remove(i+1)
        // benchmarking results a bit ambivalent
        hiddenColumns.subList(i + 1, i + 2).clear();
      }
      added = true;
    }
    return added;
  }

  /**
   * hide a list of ranges
   * 
   * @param ranges
   */
  public void hideList(List<int[]> ranges)
  {
    try
    {
      LOCK.writeLock().lock();
      for (int[] r : ranges)
      {
        hideColumns(r[0], r[1]);
      }
      cursor.resetCursor(hiddenColumns);
      numColumns = 0;
    } finally
    {
      LOCK.writeLock().unlock();
    }
  }

  /**
   * Unhides, and adds to the selection list, all hidden columns
   */
  public void revealAllHiddenColumns(ColumnSelection sel)
  {
    try
    {
      LOCK.writeLock().lock();

      for (int[] region : hiddenColumns)
      {
        for (int j = region[0]; j < region[1] + 1; j++)
        {
          sel.addElement(j);
        }
      }
      hiddenColumns.clear();
      cursor.resetCursor(hiddenColumns);
      numColumns = 0;

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

  /**
   * Reveals, and marks as selected, the hidden column range with the given
   * start column
   * 
   * @param start
   *          the start column to look for
   * @param sel
   *          the column selection to add the hidden column range to
   */
  public void revealHiddenColumns(int start, ColumnSelection sel)
  {
    try
    {
      LOCK.writeLock().lock();

      if (!hiddenColumns.isEmpty())
      {
        int regionIndex = cursor.findRegionForColumn(start)
                .getRegionIndex();

        if (regionIndex != -1 && regionIndex != hiddenColumns.size())
        {
          // regionIndex is the region which either contains start
          // or lies to the right of start
          int[] region = hiddenColumns.get(regionIndex);
          if (start == region[0])
          {
            for (int j = region[0]; j < region[1] + 1; j++)
            {
              sel.addElement(j);
            }
            int colsToRemove = region[1] - region[0] + 1;
            hiddenColumns.remove(regionIndex);

            if (hiddenColumns.isEmpty())
            {
              hiddenColumns.clear();
              numColumns = 0;
            }
            else
            {
              numColumns -= colsToRemove;
            }
            cursor.updateForDeletedRegion(hiddenColumns);
          }
        }
      }
    } finally
    {
      LOCK.writeLock().unlock();
    }
  }

  /**
   * Add gaps into the sequences aligned to profileseq under the given
   * AlignmentView
   * 
   * @param profileseq
   *          sequence in al which sequences are aligned to
   * @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.clear();
      this.hideColumns(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
      List<int[]> newhidden = new ArrayList<>();

      int numGapsBefore = 0;
      int gapPosition = 0;
      for (int[] region : hiddenColumns)
      {
        // get region coordinates accounting for gaps
        // we can rely on gaps not being *in* hidden regions because we already
        // removed those
        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
        StringBuilder sb = new StringBuilder();
        for (int s = 0; s < right - left + 1; s++)
        {
          sb.append(gc);
        }
        padGaps(sb, left, profileseq, al);

      }
      hiddenColumns = newhidden;
      cursor.resetCursor(hiddenColumns);
      numColumns = 0;
    } 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(StringBuilder 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));
        }
      }
    }
  }

  /*
   * Methods which only need read access to the hidden columns collection. 
   * These methods should use a readLock to prevent other threads changing
   * the hidden columns collection while it is in use.
   */

  /**
   * 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();

      boolean first = true;
      for (int[] range : hiddenColumns)
      {
        if (!first)
        {
          regionBuilder.append(delimiter);
        }
        else
        {
          first = false;
        }
        regionBuilder.append(range[0]).append(between).append(range[1]);

      }

      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();

      if (numColumns == 0)
      {
        // numColumns is out of date, so recalculate
        int size = 0;

        for (int[] range : hiddenColumns)
        {
          size += range[1] - range[0] + 1;
        }

        numColumns = size;
      }

      return numColumns;
    } 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 (that.hiddenColumns.size() != this.hiddenColumns.size())
      {
        return false;
      }

      Iterator<int[]> thatit = that.iterator();
      for (int[] thisRange : hiddenColumns)
      {
        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 visibleToAbsoluteColumn(int column)
  {
    try
    {
      LOCK.readLock().lock();
      int result = column;

      if (!hiddenColumns.isEmpty())
      {
        result += cursor.findRegionForVisColumn(column).getHiddenSoFar();
      }

      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
   * index of the next visible column on the left will be returned (or 0 if
   * there is no visible column on the left)
   * 
   * @param hiddenColumn
   *          the column index in the full alignment including hidden columns
   * @return the position of the column in the visible alignment
   */
  public int absoluteToVisibleColumn(int hiddenColumn)
  {
    try
    {
      LOCK.readLock().lock();
      int result = hiddenColumn;

      if (!hiddenColumns.isEmpty())
      {
        HiddenCursorPosition cursorPos = cursor
                .findRegionForColumn(hiddenColumn);
        int index = cursorPos.getRegionIndex();
        int hiddenBeforeCol = cursorPos.getHiddenSoFar();
    
        // just subtract hidden cols count - this works fine if column is
        // visible
        result = hiddenColumn - hiddenBeforeCol;
    
        // now check in case column is hidden - it will be in the returned
        // hidden region
        if (index < hiddenColumns.size())
        {
          int[] region = hiddenColumns.get(index);
          if (hiddenColumn >= region[0] && hiddenColumn <= region[1])
          {
            // actually col is hidden, return region[0]-1
            // unless region[0]==0 in which case return 0
            if (region[0] == 0)
            {
              result = 0;
            }
            else
            {
              result = region[0] - 1 - hiddenBeforeCol;
            }
          }
        }
      }

      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 = visibleToAbsoluteColumn(absoluteToVisibleColumn(startColumn));

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

      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 absolute (visible) alignmentPosition to find the next hidden
   *          column for
   * @return the index of the next hidden column, or alPos if there is no next
   *         hidden column
   */
  public int getHiddenBoundaryRight(int alPos)
  {
    try
    {
      LOCK.readLock().lock();
      if (!hiddenColumns.isEmpty())
      {
        int index = cursor.findRegionForColumn(alPos).getRegionIndex();
        if (index < hiddenColumns.size())
        {
          int[] region = hiddenColumns.get(index);
          if (alPos < region[0])
          {
            return region[0];
          }
          else if ((alPos <= region[1])
                  && (index + 1 < hiddenColumns.size()))
          {
            // alPos is within a hidden region, return the next one
            // if there is one
            region = hiddenColumns.get(index + 1);
            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 absolute (visible) alignmentPosition to find the previous
   *          hidden column for
   */
  public int getHiddenBoundaryLeft(int alPos)
  {
    try
    {
      LOCK.readLock().lock();

      if (!hiddenColumns.isEmpty())
      {
        int index = cursor.findRegionForColumn(alPos).getRegionIndex();

        if (index > 0)
        {
          int[] region = hiddenColumns.get(index - 1);
          return region[1];
        }
      }
      return alPos;
    } finally
    {
      LOCK.readLock().unlock();
    }
  }


  /**
   * 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();

      int regionindex = cursor.findRegionForColumn(column).getRegionIndex();
      if (regionindex > -1 && regionindex < hiddenColumns.size())
      {
        int[] region = hiddenColumns.get(regionindex);
        // already know that column <= region[1] as cursor returns containing
        // region or region to right
        if (column >= region[0])
        {
          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.isEmpty())
      {
        for (int i = 0; i < iSize; i++)
        {
          StringBuilder visibleSeq = new StringBuilder();

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

          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.isEmpty())
      {
        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 absoluteToVisibleColumn(start);
      }
      // otherwise, sequence was completely hidden
      return visPrev;
    } finally
    {
      LOCK.readLock().unlock();
    }
  }


  /**
   * 
   * @return true if there are columns hidden
   */
  public boolean hasHiddenColumns()
  {
    try
    {
      LOCK.readLock().lock();

      // we don't use getSize()>0 here because it has to iterate over
      // the full hiddenColumns collection and so will be much slower
      return (!hiddenColumns.isEmpty());
    } finally
    {
      LOCK.readLock().unlock();
    }
  }

  /**
   * 
   * @return true if there is more than one hidden column region
   */
  public boolean hasMultiHiddenColumnRegions()
  {
    try
    {
      LOCK.readLock().lock();
      return !hiddenColumns.isEmpty() && hiddenColumns.size() > 1;
    } finally
    {
      LOCK.readLock().unlock();
    }
  }


  /**
   * Returns a hashCode built from hidden column ranges
   */
  @Override
  public int hashCode()
  {
    try
    {
      LOCK.readLock().lock();
      int hashCode = 1;
      for (int[] hidden : hiddenColumns)
      {
        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 mapped to bits starting from zero
   */
  public void hideColumns(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);
      }
      cursor.resetCursor(hiddenColumns);
      numColumns = 0;
    } finally
    {
      LOCK.writeLock().unlock();
    }
  }

  /**
   * Hide columns corresponding to the marked bits, within the range
   * [start,end]. Entries in tohide which are outside [start,end] are ignored.
   * 
   * @param tohide
   *          columns mapped to bits starting from zero
   * @param start
   *          start of range to hide columns within
   * @param end
   *          end of range to hide columns within
   */
  public void hideColumns(BitSet tohide, int start, int end)
  {
    clearHiddenColumnsInRange(start, end);

    // make sure only bits between start and end are set
    tohide.clear(0, start - 1);
    tohide.clear(Math.min(end + 1, tohide.length() - 1),
            tohide.length() - 1);

    hideColumns(tohide);
  }

  /**
   * Make all columns in the range [start,end] visible
   * 
   * @param start
   *          start of range to show columns
   * @param end
   *          end of range to show columns
   */
  private void clearHiddenColumnsInRange(int start, int end)
  {
    try
    {
      LOCK.writeLock().lock();
      
      HiddenCursorPosition pos = cursor.findRegionForColumn(start);
      int index = pos.getRegionIndex();
      int startindex = index; // first index in hiddenColumns to remove
      
      if (index != -1 && index != hiddenColumns.size())
      {
        // regionIndex is the region which either contains start
        // or lies to the right of start
        int[] region = hiddenColumns.get(index);
        if (region[0] < start && region[1] >= start)
        {
          // region contains start, truncate so that it ends just before start
          region[1] = start - 1;
          startindex++;
        }
      }
      
      pos = cursor.findRegionForColumn(end);
      index = pos.getRegionIndex();
      int endindex = index - 1; // last index in hiddenColumns to remove

      if (index != -1 && index != hiddenColumns.size())
      {
        // regionIndex is the region which either contains end
        // or lies to the right of end
        int[] region = hiddenColumns.get(index);
        if (region[0] <= end && region[1] > end)
        {
          // region contains end, truncate so that it starts just after end
          region[0] = end + 1;
        }
      }
      
      hiddenColumns.subList(startindex, endindex + 1).clear();
      cursor.resetCursor(hiddenColumns);
      numColumns = 0;
    } finally
    {
      LOCK.writeLock().unlock();
    }
  }

  /**
   * 
   * @param inserts
   *          BitSet where hidden columns will be marked
   */
  public void markHiddenRegions(BitSet inserts)
  {
    try
    {
      LOCK.readLock().lock();

      for (int[] range : hiddenColumns)
      {
        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.isEmpty())
      {
        return new int[] { startPos, endPos };
      }

      for (int[] range : hiddenColumns)
      {
        lowestRange = (range[0] <= startPos) ? range : lowestRange;
        higestRange = (range[1] >= endPos) ? range : higestRange;
      }

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

      if (higestRange[0] == -1) // includes (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. If
   *         res is adjacent to two regions, returns the left region.
   */
  public int[] getRegionWithEdgeAtRes(int res)
  {
    try
    {
      LOCK.readLock().lock();
      int adjres = visibleToAbsoluteColumn(res);

      int[] reveal = null;

      if (!hiddenColumns.isEmpty())
      {
        // look for a region ending just before adjres
        int regionindex = cursor.findRegionForColumn(adjres - 1)
                .getRegionIndex();
        if (regionindex < hiddenColumns.size()
                && hiddenColumns.get(regionindex)[1] == adjres - 1)
        {
          reveal = hiddenColumns.get(regionindex);
        }
        // check if the region ends just after adjres
        else if (regionindex < hiddenColumns.size()
                && hiddenColumns.get(regionindex)[0] == adjres + 1)
        {
          reveal = hiddenColumns.get(regionindex);
        }
      }
      return reveal;

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

  /**
   * Return an iterator over the hidden regions
   */
  public Iterator<int[]> iterator()
  {
    try
    {
      LOCK.readLock().lock();
      return new HiddenColsIterator(hiddenColumns);
    } finally
    {
      LOCK.readLock().unlock();
    }
  }

  /**
   * 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)
  {
    try
    {
      LOCK.readLock().lock();
      return new HiddenColsIterator(start, end, hiddenColumns);
    } finally
    {
      LOCK.readLock().unlock();
    }
  }

  /**
   * 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)
  {
    try
    {
      LOCK.readLock().lock();

      // get absolute position of column in alignment
      int absoluteStart = visibleToAbsoluteColumn(start);

      // Get cursor position and supply it to the iterator:
      // Since we want visible region start, we look for a cursor for the
      // (absoluteStart-1), then if absoluteStart is the start of a visible
      // region we'll get the cursor pointing to the region before, which is
      // what we want
      HiddenCursorPosition pos = cursor
              .findRegionForColumn(absoluteStart - 1);

      return new BoundedStartRegionIterator(pos, start, end,
              hiddenColumns);
    } finally
    {
      LOCK.readLock().unlock();
    }
  }

  /**
   * 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)
  {
    try
    {
      LOCK.readLock().lock();
      return new VisibleColsIterator(start, end, hiddenColumns);
    } finally
    {
      LOCK.readLock().unlock();
    }
  }

  /**
   * 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
   * @param useVisibleCoords
   *          if true, start and end are visible column positions, not absolute
   *          positions*
   */
  public VisibleContigsIterator getVisContigsIterator(int start,
          int end,
          boolean useVisibleCoords)
  {
    int adjstart = start;
    int adjend = end;
    if (useVisibleCoords)
    {
      adjstart = visibleToAbsoluteColumn(start);
      adjend = visibleToAbsoluteColumn(end);
    }

    try
    {
      LOCK.readLock().lock();
      return new VisibleContigsIterator(adjstart, adjend, hiddenColumns);
    } finally
    {
      LOCK.readLock().unlock();
    }
  }
}