src/com/ibm/richtext/styledtext/FastIntBinarySearch.java

/*
*   Copyright (C) 1996-2002, International Business Machines
*   Corporation and others.  All Rights Reserved.
*/

/*
    7/29/96
        Modified to search portions of an integer array.  Should be retested.
*/

package com.ibm.richtext.styledtext;

/**
 * This class searches a segment of an array of integers.  The segment
 * must be sorted in ascending order (but this class does not verify this).
 * Also, this class aliases the array;  if the array is modified later the
 * search results are undefined.
 */
final class FastIntBinarySearch
{
    static final String COPYRIGHT =
                "(C) Copyright IBM Corp. 1998-1999 - All Rights Reserved";
    private int dataArray[];
    private int auxStart;
    private int power;

    private int fFirstIndex;

    private static final int exp2[] = { 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072 };

    public FastIntBinarySearch(int data[])
    {
        this(data, 0, data.length);
    }

    public FastIntBinarySearch(int data[], int firstValidIndex, int validLength)
    {
        setData(data, firstValidIndex, validLength);
    }
    
    public void setData(int data[]) {
        
        setData(data, 0, data.length);
    }
    
    public void setData(int data[], int firstValidIndex, int validLength) {

        if (data.length < 1) throw new IllegalArgumentException();
        if (data.length >= exp2[exp2.length-1]) throw new IllegalArgumentException();

        dataArray = data;
        fFirstIndex = firstValidIndex;

        for (power = exp2.length-1; power > 0 && validLength < exp2[power]; power--) {}

        // at this point, array.length >= 2^power

        auxStart = validLength - exp2[power];
    }
    
    /**
     * Return the index in the array of the first element which is at least
     * as large as <tt>value</tt>.  If value is larger than the largest
     * element in the array the last valid index in the array is returned.
     */
    public int findIndex(int value)
    {
        int index = exp2[power]-1 + fFirstIndex;
        if (value >= dataArray[auxStart + fFirstIndex]) {
            index += auxStart;
        }

        // at this point, index is the "upper limit" of the search

        switch (power) {
        case 17:
            if (value < dataArray[index-65536]) index -= 65536;
        case 16:
            if (value < dataArray[index-32768]) index -= 32768;
        case 15:
            if (value < dataArray[index-16384]) index -= 16384;
        case 14:
            if (value < dataArray[index-8192]) index -= 8192;
        case 13:
            if (value < dataArray[index-4096]) index -= 4096;
        case 12:
            if (value < dataArray[index-2048]) index -= 2048;
        case 11:
            if (value < dataArray[index-1024]) index -= 1024;
        case 10:
            if (value < dataArray[index-512]) index -= 512;
        case 9:
            if (value < dataArray[index-256]) index -= 256;
        case 8:
            if (value < dataArray[index-128]) index -= 128;
        case 7:
            if (value < dataArray[index-64]) index -= 64;
        case 6:
            if (value < dataArray[index-32]) index -= 32;
        case 5:
            if (value < dataArray[index-16]) index -= 16;
        case 4:
            if (value < dataArray[index-8]) index -= 8;
        case 3:
            if (value < dataArray[index-4]) index -= 4;
        case 2:
            if (value < dataArray[index-2]) index -= 2;
        case 1:
            if (value < dataArray[index-1]) index -= 1;
        case 0:
            if (value < dataArray[index]) index -= 1;
        }
        return index;
    }
}