/*
 *This library is free software; you can redistribute it and/or
 *modify it under the terms of the GNU Lesser General Public
 *License as published by the Free Software Foundation; either
 *version 2.1 of the License, or (at your option) any later version.
 *
 *This library 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
 *Lesser General Public License for more details.
 *
 *You should have received a copy of the GNU Lesser General Public
 *License along with this library; if not, write to the Free Software
 *Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
*/

/* 
 * This software was written by Phillip Lord (p.lord@hgmp.mrc.ac.uk)
 * whilst at the University of Manchester as a Pfizer post-doctoral 
 * Research Fellow. 
 *
 * The initial code base is copyright by Pfizer, or the University
 * of Manchester. Modifications to the initial code base are copyright
 * of their respective authors, or their employers as appropriate. 
 * Authorship of the modifications may be determined from the ChangeLog
 * placed at the end of this file
 */

package uk.ac.man.bioinf.sequence.alignment; // Package name inserted by JPack
import uk.ac.man.bioinf.sequence.DefaultSequence;
import uk.ac.man.bioinf.sequence.Element;
import uk.ac.man.bioinf.sequence.Residue;
import uk.ac.man.bioinf.sequence.Sequence;
import uk.ac.man.bioinf.sequence.SequenceType;
import uk.ac.man.bioinf.sequence.Sequences;
import uk.ac.man.bioinf.sequence.alignment.Gap;
import uk.ac.man.bioinf.sequence.identifier.Identifier;
import uk.ac.man.bioinf.sequence.identifier.NoIdentifier;
import uk.ac.man.bioinf.util.IntArrayList;
import uk.ac.man.bioinf.sequence.EmptySequence;


/**
 * DefaultGappedSequence.java
 *
 *
 * Created: Sat Mar  4 12:28:57 2000
 *
 * @author Phillip Lord
 * @version $Id: DefaultGappedSequence.java,v 1.14 2001/04/11 17:04:43 lord Exp $
 */

public class DefaultGappedSequence extends AbstractGappedSequence
{
  protected Sequence sequence;
  
  // maps between the gapped and ungapped position. Ive choosen to
  // just ignore the first element in this list because its not worth
  // bothering with -1's everywhere. A negative number in this list
  // means that there is a gap at that point. Ive havent quite decided
  // what to do with the negative numbers. It might be wise to have it
  // point to the next non gapped element for instance, although it
  // might not be worth the computation of doing that. What is clear
  // however is if its negative its a gap!!!!
  protected IntArrayList toGappedMap;
  
  protected DefaultGappedSequence( Sequence seq, IntArrayList toGappedMap )
  {
    super( seq.getSequenceType() );
    this.sequence = seq;
    this.toGappedMap = toGappedMap;
  }
  
  protected DefaultGappedSequence( Element[] elements, SequenceType type, 
				 IntArrayList toGappedMap, Identifier ident )
  {
    this( new DefaultSequence( elements, type, ident ), toGappedMap );
  }
  
  /**
   * A new gapped sequence, with no gaps in it!
   * @param elements 
   * @param type
   * @param bioInt
   */
  public DefaultGappedSequence( Element[] elements, SequenceType type, Identifier ident )
  {
    this( elements, type, new IntArrayList(), ident );
    
    // fill the array list up with ints the same as the their
    // index. We need to add a zero at the first place, so that we
    // dont have to deal with the - 1 thing....
    toGappedMap.add( 0, 0 );
    
    for( int i = 0; i < elements.length ; i++ ){
      toGappedMap.add( i + 1 );
    } //end for( i toGappedMap )
  }
    
  public DefaultGappedSequence( Element[] elements, SequenceType type )
  {
    this( elements, type, new NoIdentifier() );
  }
  
  // gap editor methods
  protected void deleteGapAtQuietly( int index )
  {
    checkGappedRange( index );
    if( getGappedElementAt( index ) != Gap.GAP ){
      throw new NoGapAtThisPositionException( this, index );
    }
    
    toGappedMap.remove( index );
  }
  
  protected void insertGapAtQuietly( int index )
  {
    checkGappedRangeForInsert( index );
    
    toGappedMap.add( index, -1 );
  }
    
  // gapped accessor methods
  public Element getGappedElementAt( int index )
  {
    try{
      int unGapIndex = toGappedMap.get( index );
    
      if( unGapIndex < 0 )
	return Gap.GAP;
      
      return sequence.getElementAt( unGapIndex );
    }
    catch( ArrayIndexOutOfBoundsException ofbe ){
      throw getGappedSequenceIndexException( index );
    }
  }
  
  public Element[] getGappedSequenceAsElements()
  {
    Element[] elem = new Element[ getGappedLength() ];
    
    for( int i = 0; i < elem.length; i++ ){
      elem[ i ] = getGappedElementAt( i + 1 );
    } //end for( i < elem.length )
    return elem;
  }
  
  public int getGappedLength()
  {
    return toGappedMap.size() - 1;
  }
  
  public int getUngappedPositionOf( int index )
  {
    checkGappedRange( index );
    return toGappedMap.get( index );
  }
  
  public int getGappedPositionOf( int index )
  {
    checkRange( index );

    // the gapped index must be greater or equal to the ungapped
    // index. Therefore start at index in the gap map and work down
    // till we find it. This could be improved significantly by
    // making the negative values meaningful. We could also help out
    // here a lot by doing some sort of binary search
    for( int i = index; i != getGappedLength(); i++ ){
      if( toGappedMap.get( i ) == index ){
	return i;
      }
    }

    // If my calculations have not gone awry if we get here there is a
    // problem with my code!
    throw new Error( "Failed to find ungapped index which should have been there" );
  }
  
  public GappedSequence getGappedSubSequence( int position, int length )
  {
    int startUnGap = position;
    // the end index is the start index, plus the length, which gives
    // the first element NOT to be included, -1 to give the index of
    // the last element to be included!
    int endUnGap = position + length - 1;
    
    // check the ranges to make sure that everything is correct. 
    checkGappedRange( startUnGap );
    checkGappedRange( endUnGap );
    
    // First copy the relevant chunk of the gap map out. 
    IntArrayList newGapMap = toGappedMap.getSubList( position, length );
    
    // now move all the numbers down..
    int numberOfGaps = position - getUngappedPositionOf( position );
    int startPos = position - numberOfGaps; 
    
    for ( int i = 0; i < length; i++ ){
      int val;
      if( (val = newGapMap.get(i)) > 0 ) {
	newGapMap.set( i, val - startPos + 1 );
      }
    }
    
    // We ignore the first element of the IntArrayList in this class
    // so add a new one on.
    newGapMap.add( 0, 0 );
    

    // we now need to chomp the begining and the end positions if
    // there are gaps in the sequence at this point. We move inwards
    // till we get the first none gap from both ends. The gap model
    // should still automatically reflect this. 

    // search for the first non gap position, going upwards
    while( getUngappedPositionOf( startUnGap ) == -1 ){
      startUnGap++;
    }
    
    // search for the first non gap position going downwards
    while( getUngappedPositionOf( endUnGap ) == -1 ){
      endUnGap--;
    }
    
    int interval = endUnGap - startUnGap + 1;
    
    // if this is less than 1 its all gaps
    Sequence seq;
    if( interval < 1 ){
     seq = EmptySequence.getInstance();
    }
    else{
      // now we need a subsequence for internal use
      seq =       
        sequence.getSubSequence
        ( startUnGap - numberOfGaps,
          interval );
    }
    
    // now we can make a new gapped sequence with the private cons
    return new DefaultGappedSequence( seq, newGapMap );
  }
    
  public int getLength()
  {
    return sequence.getLength();
  }

  public Identifier getIdentifier()
  {
    return sequence.getIdentifier();
  }
  
  public Element[] getSequenceAsElements()
  {
    return sequence.getSequenceAsElements();
  }
  
  public Element getElementAt( int index )
  {
    return sequence.getElementAt( index );
  }
  
  public static GappedSequence getElementsAsGappedSequence( Element[] elements, SequenceType type )
  {
    return getElementsAsGappedSequence( elements, type, new NoIdentifier() );
  }
  
  public static GappedSequence getElementsAsGappedSequence
    ( Element[] elements, SequenceType type, Identifier ident )
  {
    
    // first we need to make a gapped model...
    IntArrayList gapModel = getGapModelForElements( elements );
    
    Element[] unGappedElements = stripGapsFromElements
      ( elements, gapModel.get( 0 ) );

    return new DefaultGappedSequence( unGappedElements, type, gapModel, ident );
  }

  public static Residue[] stripGapsFromElements( Element[] elements, int size )
  {
    Residue[] strippedElements = new Residue[ size  ];
    
    int nonGappedPosition = 0;
    
    for( int i = 0; i <  elements.length; i++ ){
      if( elements[ i ] != Gap.GAP ){
	strippedElements[ nonGappedPosition++ ] = (Residue)elements[ i ];
      }
    } //end for( i elements.length )

    return strippedElements;
  }
  

  public static IntArrayList getGapModelForElements( Element[] elements )
  {
    // first we need to make a gapped model...
    IntArrayList gapModel = new IntArrayList( elements.length );
    // profligately throw away the first element
    gapModel.add( 0 );

    int nonGappedPosition = 0;
    
    
    // linear time scan to set up gap model
    for( int i = 0; i < elements.length; i++ ){
      if( elements[ i ] == Gap.GAP ){
	gapModel.add( -1 );
      }
      else{
	gapModel.add( ++nonGappedPosition );
      }
    } //end for( i < elements.length )
    
    // HACK ALERT! HACK ALERT
    // I need this final value of nonGappedPosition, because it tells
    // me how many non-Gap elements there are in the Element array,
    // and I want to use this later. But I have no way of passing this
    // back from this method. Except that I have a spare place in the
    // IntArrayList that I am not using. So I'm going to use that to
    // store this value.

    // This whole classes needs sorting out anyway, with a properly
    // defined GapModel, rather than this hack, so I am not feeling to
    // guilty about doing this. 
    gapModel.set( 0, nonGappedPosition );

    return gapModel;
  }

  public void debugScreenDump()
  {
    System.out.println( "Internal sequence is " );
    Sequences.printSequence( sequence );
    System.out.println( "Internal gap model is  " );
    toGappedMap.print();
  }
  
} // DefaultGappedSequence



/*
 * ChangeLog
 * $Log: DefaultGappedSequence.java,v $
 * Revision 1.14  2001/04/11 17:04:43  lord
 * Added License agreements to all code
 *
 * Revision 1.13  2001/02/19 17:48:04  lord
 * Various bug fixes to the subsequence method
 *
 * Revision 1.12  2001/01/04 15:07:36  lord
 * cosmetic
 *
 * Revision 1.11  2000/12/13 16:34:58  lord
 * Alternations to static methods to make gap models accessible for
 * outside use. This is a temporary hack. The gap model needs re-writing
 * formally.
 *
 * Revision 1.10  2000/11/02 14:56:25  jns
 * o changed creation of NoGapAt...Exception to store information about
 * where the exception was raised and by what.
 *
 * Revision 1.9  2000/09/11 13:18:13  lord
 * Added identifier support
 *
 * Revision 1.8  2000/07/18 12:37:47  lord
 * Import rationalisation
 * Changes due to BioInterface removal
 *
 * Revision 1.7  2000/05/18 17:04:26  lord
 * Added support for passing in BioObject in cons
 *
 * Revision 1.6  2000/03/23 19:51:37  lord
 * Improved range checking for efficiency of access to elements
 *
 * Revision 1.5  2000/03/16 16:14:46  lord
 * Fixed numerous bugs in getGappedSubsequences
 *
 * Revision 1.4  2000/03/14 19:43:43  jns
 * o sorting problem of translation between gapped and ungapped indicies.
 *
 * Revision 1.3  2000/03/14 15:11:34  lord
 * Inserted static getElementsAsGappedSequence
 *
 * Revision 1.2  2000/03/14 13:21:38  lord
 * Can now add at end
 *
 */

