/*
 * 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 jalview.util.Comparison;

import java.util.ArrayList;
import java.util.BitSet;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.Vector;
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 = copy.copyHiddenRegionsToArrayList(0);
        }
      }
    } 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();
    }
  }

  /**
   * This method is used to return all the HiddenColumn regions and is intended
   * to remain private. External callers which need a copy of the regions can
   * call getHiddenColumnsCopyAsList.
   * 
   * @return empty list or List of hidden column intervals
   */
  private List<int[]> getHiddenRegions()
  {
    return hiddenColumns == null ? Collections.<int[]> emptyList()
            : hiddenColumns;
  }

  /**
   * 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)
      {
        for (int[] range : hiddenColumns)
        {
          regionBuilder.append(delimiter).append(range[0]).append(between)
                  .append(range[1]);
        }

        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 (hasHiddenColumns())
      {
        for (int[] range : hiddenColumns)
        {
          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;
      }
      int i = 0;
      for (int[] thisRange : hiddenColumns)
      {
        int[] thatRange = that.hiddenColumns.get(i++);
        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)
      {
        for (int i = 0; i < hiddenColumns.size(); i++)
        {
          int[] region = hiddenColumns.get(i);
          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;
      if (hiddenColumns != null)
      {
        int index = 0;
        int[] region;
        do
        {
          region = hiddenColumns.get(index++);
          if (hiddenColumn > region[1])
          {
            result -= region[1] + 1 - region[0];
          }
        } while ((hiddenColumn > region[1])
                && (index < hiddenColumns.size()));

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

      // get index of hidden region to left of start
      int index = getHiddenIndexLeft(start);
      if (index == -1)
      {
        // no hidden regions to left of startColumn
        return start - distance;
      }

      // walk backwards through the alignment subtracting the counts of visible
      // columns from distance
      int[] region;
      int gap = 0;
      int nextstart = start;

      while ((index > -1) && (distance - gap > 0))
      {
        // subtract the gap to right of region from distance
        distance -= gap;
        start = nextstart;

        // calculate the next gap
        region = hiddenColumns.get(index);
        gap = start - region[1];

        // set start to just to left of current region
        nextstart = region[0] - 1;
        index--;
      }

      if (distance - gap > 0)
      {
        // fell out of loop because there are no more hidden regions
        distance -= gap;
        return nextstart - distance;
      }
      return start - distance;
    } finally
    {
      LOCK.readLock().unlock();
    }

  }

  /**
   * Use this method to determine the set of hiddenRegion start positions
   * between absolute position <start> and absolute position <end>
   * 
   * @param start
   *          absolute residue to start from
   * @param end
   *          absolute residue to end at
   * 
   * @return list of column numbers in *visible* view where hidden regions start
   */
  public List<Integer> findHiddenRegionPositions(int start, int end)
  {
    try
    {
      LOCK.readLock().lock();
      List<Integer> positions = null;

      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))
        {
          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))
        {
          int[] region = hiddenColumns.get(i);
          positions.add(region[0] - hiddenSoFar);
          hiddenSoFar += region[1] - region[0] + 1;
          i++;
        }
      }
      else
      {
        positions = new ArrayList<>();
      }

      return positions;
    } 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 index
   *          int
   */
  public int getHiddenBoundaryRight(int alPos)
  {
    try
    {
      LOCK.readLock().lock();
      if (hiddenColumns != null)
      {
        int index = 0;
        do
        {
          int[] region = hiddenColumns.get(index);
          if (alPos < region[0])
          {
            return region[0];
          }

          index++;
        } while (index < hiddenColumns.size());
      }

      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 index
   *          int
   */
  public int getHiddenBoundaryLeft(int alPos)
  {
    try
    {
      LOCK.readLock().lock();

      if (hiddenColumns != null)
      {
        int index = hiddenColumns.size() - 1;
        do
        {
          int[] region = hiddenColumns.get(index);
          if (alPos > region[1])
          {
            return region[1];
          }

          index--;
        } while (index > -1);
      }

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

  /**
   * This method returns the index of the hidden region to the left of a column
   * position. If the column is in a hidden region it returns the index of the
   * region to the left. If there is no hidden region to the left it returns -1.
   * 
   * @param pos
   *          int
   */
  private int getHiddenIndexLeft(int pos)
  {
    try
    {

      LOCK.readLock().lock();
      if (hiddenColumns != null)
      {
        int index = hiddenColumns.size() - 1;
        do
        {
          int[] region = hiddenColumns.get(index);
          if (pos > region[1])
          {
            return index;
          }

          index--;
        } while (index > -1);
      }

      return -1;
    } finally
    {
      LOCK.readLock().unlock();
    }

  }

  /**
   * Adds the specified column range to the hidden columns
   * 
   * @param start
   * @param end
   */
  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<>();
      }

      /*
       * traverse existing hidden ranges and insert / amend / append as
       * appropriate
       */
      for (int i = 0; i < hiddenColumns.size(); i++)
      {
        int[] region = hiddenColumns.get(i);

        if (end < region[0] - 1)
        {
          /*
           * insert discontiguous preceding range
           */
          hiddenColumns.add(i, new int[] { start, end });
          return;
        }

        if (end <= region[1])
        {
          /*
           * new range overlaps existing, or is contiguous preceding it - adjust
           * start column
           */
          region[0] = Math.min(region[0], start);
          return;
        }

        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.remove(i + 1);
          }
          return;
        }
      }

      /*
       * remaining case is that the new range follows everything else
       */
      hiddenColumns.add(new int[] { start, end });
    } finally
    {
      if (!wasAlreadyLocked)
      {
        LOCK.writeLock().unlock();
      }
    }
  }

  public boolean isVisible(int column)
  {
    try
    {
      LOCK.readLock().lock();

      if (hiddenColumns != null)
      {
        for (int[] region : hiddenColumns)
        {
          if (column >= region[0] && column <= region[1])
          {
            return false;
          }
        }
      }

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

  private ArrayList<int[]> copyHiddenRegionsToArrayList(int startIndex)
  {
    int size = 0;
    if (hiddenColumns != null)
    {
      size = hiddenColumns.size();
    }
    ArrayList<int[]> copy = new ArrayList<>(size);

    for (int i = startIndex, j = size; i < j; i++)
    {
      int[] rh;
      int[] cp;
      rh = hiddenColumns.get(i);
      if (rh != null)
      {
        cp = new int[rh.length];
        System.arraycopy(rh, 0, cp, 0, rh.length);
        copy.add(cp);
      }
    }

    return copy;
  }

  /**
   * return all visible segments between the given start and end boundaries
   * 
   * @param start
   *          (first column inclusive from 0)
   * @param end
   *          (last column - not inclusive)
   * @return List<int[]> {[i_start, i_end], ..} where intervals lie in
   *         start<=i_start<=i_end<end
   */
  public List<int[]> getVisibleContigs(int start, int end)
  {
    try
    {
      LOCK.readLock().lock();
      List<int[]> vcontigs = new ArrayList<>();
      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);
      }
      return vcontigs;
    } finally
    {
      LOCK.readLock().unlock();
    }
  }

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

          int blockStart = start;
          int blockEnd = end;
          int hideStart;
          int hideEnd;

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

            if (hideStart < start)
            {
              continue;
            }

            blockStart = Math.min(blockStart, hideEnd + 1);
            blockEnd = Math.min(blockEnd, hideStart);

            if (blockStart > blockEnd)
            {
              break;
            }

            visibleSeq.append(seqs[i].getSequence(blockStart, blockEnd));

            blockStart = hideEnd + 1;
            blockEnd = end;
          }

          if (end > blockStart)
          {
            visibleSeq.append(seqs[i].getSequence(blockStart, end));
          }

          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 and last position visible for this sequence. if seq isn't
   * visible then return the position of the left and right of the hidden
   * boundary region, and the corresponding alignment column indices for the
   * extent of the sequence
   * 
   * @param seq
   * @return int[] { visible start, visible end, first seqpos, last seqpos,
   *         alignment index for seq start, alignment index for seq end }
   */
  public int[] locateVisibleBoundsOfSequence(SequenceI seq)
  {
    try
    {
      LOCK.readLock().lock();
      int fpos = seq.getStart();
      int lpos = seq.getEnd();
      int start = 0;

      if (hiddenColumns == null || hiddenColumns.size() == 0)
      {
        int ifpos = seq.findIndex(fpos) - 1;
        int ilpos = seq.findIndex(lpos) - 1;
        return new int[] { ifpos, ifpos, ilpos };
      }

      // Simply walk along the sequence whilst watching for hidden column
      // boundaries
      List<int[]> regions = getHiddenRegions();
      int spos = fpos;
      int rcount = 0;
      int hideStart = seq.getLength();
      int hideEnd = -1;
      int visPrev = 0;
      int visNext = 0;
      int firstP = -1;
      int lastP = -1;
      boolean foundStart = false;
      for (int p = 0, pLen = seq.getLength(); spos <= seq.getEnd()
              && p < pLen; p++)
      {
        if (!Comparison.isGap(seq.getCharAt(p)))
        {
          // keep track of first/last column
          // containing sequence data regardless of visibility
          if (firstP == -1)
          {
            firstP = p;
          }
          lastP = p;
          // update hidden region start/end
          while (hideEnd < p && rcount < regions.size())
          {
            int[] region = regions.get(rcount++);
            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)
          {
            if (!foundStart)
            {
              fpos = spos;
              start = p;
              foundStart = true;
            }
            lpos = spos;
          }
          // look for next sequence position
          spos++;
        }
      }
      if (foundStart)
      {
        return new int[] { findColumnPosition(start), firstP, lastP };
      }
      // otherwise, sequence was completely hidden
      return new int[] { visPrev, firstP, lastP };
    } finally
    {
      LOCK.readLock().unlock();
    }
  }

  /**
   * delete any columns in alignmentAnnotation that are hidden (including
   * sequence associated annotation).
   * 
   * @param alignmentAnnotation
   */
  public void makeVisibleAnnotation(AlignmentAnnotation alignmentAnnotation)
  {
    makeVisibleAnnotation(-1, -1, 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();
      if (alignmentAnnotation.annotations == null)
      {
        return;
      }
      if (start == end && end == -1)
      {
        start = 0;
        end = alignmentAnnotation.annotations.length;
      }
      if (hiddenColumns != null && hiddenColumns.size() > 0)
      {
        // then mangle the alignmentAnnotation annotation array
        Vector<Annotation[]> annels = new Vector<>();
        Annotation[] els = null;
        int blockStart = start;
        int blockEnd = end;
        int hideStart;
        int hideEnd;
        int w = 0;

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

          if (hideStart < start)
          {
            continue;
          }

          blockStart = Math.min(blockStart, hideEnd + 1);
          blockEnd = Math.min(blockEnd, hideStart);

          if (blockStart > blockEnd)
          {
            break;
          }

          els = new Annotation[blockEnd - blockStart];
          annels.addElement(els);
          System.arraycopy(alignmentAnnotation.annotations, blockStart, els,
                  0, els.length);
          w += els.length;
          blockStart = hideEnd + 1;
          blockEnd = end;
        }

        if (end > blockStart)
        {
          els = new Annotation[end - blockStart + 1];
          annels.addElement(els);
          if ((els.length
                  + blockStart) <= alignmentAnnotation.annotations.length)
          {
            // copy just the visible segment of the annotation row
            System.arraycopy(alignmentAnnotation.annotations, blockStart,
                    els, 0, els.length);
          }
          else
          {
            // copy to the end of the annotation row
            System.arraycopy(alignmentAnnotation.annotations, blockStart,
                    els, 0,
                    (alignmentAnnotation.annotations.length - blockStart));
          }
          w += els.length;
        }
        if (w == 0)
        {
          return;
        }

        alignmentAnnotation.annotations = new Annotation[w];
        w = 0;

        for (Annotation[] chnk : annels)
        {
          System.arraycopy(chnk, 0, alignmentAnnotation.annotations, w,
                  chnk.length);
          w += chnk.length;
        }
      }
      else
      {
        alignmentAnnotation.restrict(start, end);
      }
    } finally
    {
      LOCK.readLock().unlock();
    }
  }

  /**
   * 
   * @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)
      {
        for (int i = 0; i < hiddenColumns.size(); i++)
        {
          int[] region = hiddenColumns.get(i);
          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();
      for (int i = 0; i < hiddenColumns.size(); i++)
      {
        int[] region = hiddenColumns.get(i);
        if (start == region[0])
        {
          for (int j = region[0]; j < region[1] + 1; j++)
          {
            sel.addElement(j);
          }

          hiddenColumns.remove(region);
          break;
        }
      }
      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)
  {
    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 = 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;
  }

  /**
   * 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;
      if (hiddenColumns != null)
      {
        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 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;
      }
      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 == null)
      {
        return new int[] { startPos, endPos };
      }

      for (int[] hiddenCol : hiddenColumns)
      {
        lowestRange = (hiddenCol[0] <= startPos) ? hiddenCol : lowestRange;
        higestRange = (hiddenCol[1] >= endPos) ? hiddenCol : 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;
      if (hiddenColumns != null)
      {
        for (int[] region : hiddenColumns)
        {
          if (adjres + 1 == region[0] || adjres - 1 == region[1])
          {
            reveal = region;
            break;
          }
        }
      }
      return reveal;
    } finally
    {
      LOCK.readLock().unlock();
    }
  }

  public Iterator<int[]> iterator()
  {
    if (hiddenColumns != null)
    {
      int last = hiddenColumns.get(hiddenColumns.size() - 1)[1];
      return new BoundedHiddenColsIterator(0, last, true);
    }
    else
    {
      return new BoundedHiddenColsIterator(0, 0, true);
    }
  }

  public Iterator<int[]> getBoundedIterator(int start, int end)
  {
    return new BoundedHiddenColsIterator(start, end, true);
  }

  public Iterator<Integer> getBoundedStartIterator(int start, int end)
  {
    return new BoundedStartRegionIterator(start, end, true);
  }

  public Iterator<Integer> getVisibleColsIterator(int start, int end)
  {
    return new VisibleColsIterator(start, end, true);
  }

  /**
   * An iterator which iterates over hidden column regions in a range.
   * 
   * @author kmourao
   *
   */
  class BoundedHiddenColsIterator implements Iterator<int[]>
  {
    private int start; // start position to iterate from

    private int end; // end position to iterate to

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

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

    // whether to make a local copy of hiddenColumns
    private final boolean useCopy;

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

    /**
     * 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)
     */
    BoundedHiddenColsIterator(int lowerBound, int upperBound,
            boolean useCopyCols)
    {
      start = lowerBound;
      end = upperBound;
      useCopy = useCopyCols;

      try
      {
        if (useCopy)
        {
          // assume that if useCopy is false the calling code has locked
          // hiddenColumns
          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;
            int[] cp;
            rh = hiddenColumns.get(i);
            if (rh != null)
            {
              cp = new int[rh.length];
              System.arraycopy(rh, 0, cp, 0, rh.length);
              localHidden.add(cp);
            }
            i++;
          }
        }
      }
      finally
      {
        if (useCopy)
        {
          LOCK.readLock().unlock();
        }
      }
    }

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

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

  class BoundedStartRegionIterator implements Iterator<Integer>
  {

    private int start; // start position to iterate from

    private int end; // end position to iterate to

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

    @Override
    public Integer next()
    {
      int result = positions.get(currentPosition);
      currentPosition++;
      return result;
    }
  }

  public class VisibleColsIterator implements Iterator<Integer>
  {
    private int last;

    private int current;

    private int next;

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

    private int lasthiddenregion;

    public VisibleColsIterator(int firstcol, int lastcol, boolean useCopy)
    {
      last = lastcol;
      current = firstcol;
      next = firstcol;
      lasthiddenregion = -1;

      try
      {
        if (useCopy)
        {
          // assume that if useCopy is false the calling code has locked
          // hiddenColumns
          LOCK.readLock().lock();
        }

        if (hiddenColumns != null)
        {
          int i = 0;
          for (i = 0; i < hiddenColumns.size(); ++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;
            }
            if (current < hiddenColumns.get(i)[0])
            {
              break;
            }
          }

          lasthiddenregion = i - 1;

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

          // make a local copy of the bit we need
          i = lasthiddenregion + 1;
          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++;
          }
          lasthiddenregion = -1;
        }
      } finally
      {
        if (useCopy)
        {
          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)
              && (lasthiddenregion + 1 < localHidden.size()))
      {
        // still some more hidden regions
        if (next + 1 < localHidden.get(lasthiddenregion + 1)[0])
        {
          // next+1 is still before the next hidden region
          next++;
        }
        else if ((next + 1 >= localHidden.get(lasthiddenregion + 1)[0])
                && (next + 1 <= localHidden.get(lasthiddenregion + 1)[1]))
        {
          // next + 1 is in the next hidden region
          next = localHidden.get(lasthiddenregion + 1)[1] + 1;
          lasthiddenregion++;
        }
      }
      else
      {
        // finished with hidden regions, just increment normally
        next++;
      }
      return current;
    }

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