import java.util.Arrays;

/**
 * Wrapper class that manages a dynamic-sized array of double values
 */
public class DoubleArray
{
	private double[] elements = null;
	
	private int count = 0;
	
	public static final int INITIAL_CAPACITY = 10;

	public static final int INCREASE_FACTOR = 10;
	
	public DoubleArray()
	{
		this(INITIAL_CAPACITY);
	}
	
	public DoubleArray(int initialCapacity)
	{
		this.elements = new double[initialCapacity];
	}
	
	public void append(double element)
	{
		if ( this.count == this.getCapacity() )
		{
			this.increaseCapacity();
		}
		
		this.elements[ this.count++ ] = element;
	}
	
	public void insertAt(int index, double element)
	{
		if ( this.count == this.getCapacity() )
		{
			this.increaseCapacity();
		}
		
		for ( int current = count; current > index; --current )
		{
			this.elements[current] = this.elements[current - 1];
		}
		
		this.elements[index] = element;
		++this.count;
	}
	
	public int getCount()
	{
		return this.count;
	}
	
	public int getCapacity()
	{
		return this.elements.length;
	}
	
	public double getAt(int index)
	{
		return this.elements[index];
	}
	
	private void increaseCapacity()
	{
		double[] newElements = new double[ INCREASE_FACTOR * this.getCapacity() ];
		
		for ( int index = 0; index < this.count; ++index )
		{
			newElements[index] = this.elements[index];
		}
		
		this.elements = newElements;
	}
	
	public void sort()
	{
		Arrays.sort( this.elements, 0, this.getCount() );
	}
	
	public void bubbleSort()
	{
		int changes = -1;
		int pass = 0;
		
		//for ( int pass = 0; pass < this.getCount(); ++pass )
		while ( changes != 0 )
		{
			changes = 0;
			for ( int index = 1; index < this.getCount() - pass; ++index )
			{
				if ( this.elements[index - 1] > this.elements[index] )
				{
					this.swap(index - 1, index);
					++changes;
				}
			}
			++pass;
		}
	}
	
	private void swap(int index1, int index2)
	{
		double copy1 = this.elements[index1];
		this.elements[index1] = this.elements[index2];
		this.elements[index2] = copy1;
	}
	
	/**
	 * Sequential search in O(n)
	 * @param element
	 * @return
	 */
	public int searchFirst(double element)
	{
		int position = -1;
		for ( int index = 0; index < this.getCount() && position == -1; ++index )
		{
			if ( this.elements[index] == element )
			{
				position = index;
			}
		}
		
		return position;
	}
	
	public int binarySearch(double element)
	{
		int low = 0;
		int high = this.getCount();
		
		while ( low < high )
		{
			int middle = (low + high) / 2;
			if ( element == this.elements[middle] )
				return middle;
			else if ( element < this.elements[middle] )
				high = middle;
			else
				low = middle + 1;
		}
		
		return -1;
	}
}