public class ToolsetArrayComparable<E extends Comparable<E>>
{
	private boolean sortedBetween (E[] array, int left, int right)
	{
		assert array != null                            : "precondition";
		assert left >= 0				: "precondition";
		assert right < array.length			: "precondition";
		while (left < right && array[left].compareTo(array[left + 1]) <= 0)
		{
			++left;
		}
		return left >= right;
	}
        
	public boolean sorted (E[] array)
	{
		assert array != null                            : "precondition";
		return sortedBetween(array, 0, array.length - 1);
	}
        
	private boolean hasBetween 
                (E[] array, E item, int left, int right)
	{
		assert array != null                            : "precondition";
		assert left >= 0				: "precondition";
		assert right < array.length                     : "precondition";
		assert sortedBetween(array, left, right)        : "precondition";
		if (left > right)
		{
			return false;
		} 
		else 
		{
			int mid = (left + right) / 2;
			if (item.compareTo(array[mid]) < 0) 
			{
				return hasBetween(array, item, left, mid - 1);
			} 
			else if (item.compareTo(array[mid]) > 0) 
			{
				return hasBetween(array, item, mid + 1, right);
			} 
			else 
			{
				return true;
			}
		}
	}

	public boolean has (E[] array, E item) 
	{
		assert array != null                            : "precondition";
		assert sorted(array)                            : "precondition";
		return hasBetween(array, item, 0, array.length - 1);
	}
        
        private static final double SHRINK_FACTOR = 1.3;
        
        public void gapsort (E[] array)
        {
		assert array != null                            : "precondition";
                boolean swapped = true;
                int gap = array.length;
                while (swapped || gap > 1) 
                {
                        swapped = false;
                        gap = Math.max((int)(gap / SHRINK_FACTOR), 1);
                        for (int index1 = 0; index1 + gap < array.length; ++index1)
                        {
                                int index2 = index1 + gap;
                                if (array[index1].compareTo(array[index2]) > 0)
                                {
                                        E temp = array[index1];
                                        array[index1] = array[index2];
                                        array[index2] = temp;
                                        swapped = true;
                                }
                        }
                }
                assert sorted(array) : "postcondition";
        }        
        
	private int	maxLow,
			maxHigh;

	private int	maxSum;

	public int maxLow () 
	{
		return maxLow;
	}

	public int maxHigh () 
	{
		return maxHigh;
	}

	public int maxSum () 
	{
		return maxSum;
	}

	public void determineRangeWithMaxSum (int[] array) 
	{
		assert array != null : "precondition";
		int low = 0; 
		int sum = array[low];
		maxLow = low;
		maxHigh = low;
		maxSum = sum;
		for (int high = low + 1; high < array.length; ++high) 
		{
			if (sum <= 0) 
			{
				low = high;
				sum = 0;
			}
			sum += array[high];
			if (sum > maxSum) 
			{
				maxLow = low;
				maxHigh = high;
				maxSum = sum;
			}
		}
		assert 0 <= maxLow()			: "postcondition";
		assert maxLow() <= maxHigh()		: "postcondition";
		assert maxHigh() < array.length		: "postcondition";
	}

}