/*
 *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.util; // Package name inserted by JPack
import java.util.NoSuchElementException;
import java.util.Arrays;


/**
 * IntArrayList.java
 *
 * This class provides something akin to the ArrayList class but with
 * all the methods typed as ints, which avoids the additional bloat of
 * having to create an object for every containined integer.
 *
 * Created: Fri Mar  3 23:28:54 2000
 *
 * @author Phillip Lord
 * @version $Id: IntArrayList.java,v 1.6 2001/04/11 17:04:43 lord Exp $
 */

public class IntArrayList 
{
  private int size;
  private int[] elements;
  
  private IntArrayList( boolean dontMakeArrayWhatEverTheValueOfThisParameter )
  {
  }
  
  public IntArrayList()
  {
    this( 10 );
  }
  
  public IntArrayList( int initialCapacity )
  {
    elements = new int[ initialCapacity ];
  }
  
  public void ensureCapacity( int minCapacity )
  {
    int oldCapacity = elements.length;
    if( minCapacity > oldCapacity ){
      int[] oldElements = elements;
      int newCapacity = oldCapacity * 2;
      if( newCapacity < minCapacity ){
	newCapacity = minCapacity;
      }
      
      elements = new int[ newCapacity ];
      System.arraycopy( oldElements, 0, elements, 0 , size );
    }
  }
  
  public int size()
  {
    return size;
  }
  
  public boolean isEmpty()
  {
    return size == 0;
  }

  public boolean contains( int elem )
  {
    return indexOf( elem ) >= 0;
  }
  
  public int indexOf( int elem )
  {
    for( int i = 0; i < size; i++ ){
      if( elem == elements[ i ] )
	return i;
    }
    return -1;
  }
  
  public int lastIndexOf( int elem )
  {
    for( int i = size - 1; i >= 0; i-- ){
      if( elem == elements[ i ] ){
	return i;
      }
    }
    return -1;
  }
  
  private void checkRange( int index )
  {
    if( index < 0 || index > size ){
      throw new NoSuchElementException( "Attempt to access element " + index + " which doesnt exist" );
    }
  }
  
  public int get( int index )
  {
    checkRange( index );
    return elements[ index ];
  }
  
  public int set( int index, int value )
  {
    checkRange( index );
    
    int old = elements[ index ];
    elements[ index ] = value;
    return old;
  }
  
  public void add( int value )
  {
    ensureCapacity( size + 1 );
    elements[ size++ ] = value;
  }
  
  public void add( int index, int value )
  {
    ensureCapacity( size + 1 );
    System.arraycopy( elements, index, elements, index + 1, size - index );
    elements[ index ] = value;
    size++;
  }
  
  public int remove( int index )
  {
    checkRange( index );
    
    int old = elements[ index ];
    // if its the last element we can ignore things otherwise
    int moved = size - 1 - index;
    if( moved > 0 ){
      System.arraycopy( elements, index + 1, elements, index, size - 1 - index );
    }

    size--;
    return old;
  }
  
  public int[] remove( int index, int length )
  {
    int to = index + length;
    checkRange( index );
    checkRange( to );
    
    int[] old = new int[ length ];
    System.arraycopy( elements, to, old, 0, length );
    System.arraycopy( elements, to, elements, index, length );
    return old;
  }
  
  public void clear()
  {
    size = 0;
  }
  
  public IntArrayList getSubList( int position, int length )
  {
    checkRange( position );
    checkRange( position + length );
    
    IntArrayList retn = new IntArrayList( true );
    
    retn.elements = new int[length];
    retn.size = length;
    
    System.arraycopy( elements, position, retn.elements, 0, length );

    return retn;
  }
  
  public int[] toArray()
  {
    int[] retn = new int[ size ];
    System.arraycopy( elements, 0, retn, 0, size );
    return retn;
  }
  
  /**
   * Sort the contents of this list. Does it via a modified
   * quicksort. Which I didnt write. 
   */
  public void sort()
  {
    Arrays.sort( elements, 0, size - 1 );
  }
  
  /**
   * This method performs a binary search on the list. If you choose
   * to use this method on a list which is not guarenteed to be sorted
   * for instance by the sort method then dealing with the results is 
   * distinctly your problem.
   * @param key the key to search for
   * @return the position the key is at or its insertion point.
   * @see java.util.Arrays#binarySearch(int[],int)
   */
  public int binarySearch( int key )
  {
    /* Surprise surprise. Thought this was going to be implemented by
     * a call to the Arrays class? Well it was going to be but sadly
     * that doesnt allow a search ( int from, int to ). The ints of
     * the end of the list are going to be zero, or the garbage of
     * previous entries if the list has been shrunk (since there is no
     * reason to zero them), so letting them into the sort would be A
     * BAD IDEA(tm). So I blatantly plagarised the code in there (like
     * its rocket science yeah?)
     */
    int low = 0;
    int high = size - 1;
    
    while (low <= high) {
      int mid =(low + high)/2;
      int midVal = elements[mid];
      
      if (midVal < key)
	low = mid + 1;
      else if (midVal > key)
	high = mid - 1;
      else
	return mid; // key found
    }
    return -(low + 1);  // key not found.
  }
  
  /**
   * Provides a linear search. This works even if the list is not
   * sorted, but operates in, well linear, time. 
   * @param key the key to search for
   * @return the index or -1 if not found
   */
  public int linearSearch( int key )
  {
    for( int i = 0; i < size; i++ ){
      if( elements[ i ] == key ){
	return i;
      }
    } //end for( i < size )
    return -1;
  }
  
  public boolean equals( IntArrayList list )
  {
    if( size != list.size ) return false;
    
    for( int i = 0; i < size; i++ ){
      if( elements[ i ] != list.elements[ i ] ) return false;
    }
    
    return true;
  }

  public void print()
  {
    // This is a debug method

    System.out.println( "Index\tValue" );
    for( int i = 0; i < size; i++ ){
      System.out.println( i + "\t" + elements[ i ] );
    } //end for( i < elements.length )
  }
  
} // IntArrayList



/*
 * ChangeLog
 * $Log: IntArrayList.java,v $
 * Revision 1.6  2001/04/11 17:04:43  lord
 * Added License agreements to all code
 *
 * Revision 1.5  2001/01/04 15:00:49  lord
 * Fixed bug in range checking code
 *
 * Revision 1.4  2000/06/05 14:46:43  lord
 * Added linear search method
 *
 * Revision 1.3  2000/05/18 17:01:48  lord
 * Added toArray method
 *
 * Revision 1.2  2000/03/14 19:44:53  jns
 * o sorting a problem of translation of gapped and ungapped indicies.
 *
 * Revision 1.1  2000/03/08 17:26:36  lord
 * To many changes to document
 *
 */


































