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

/*
 * @(#)$RCSfile: RunArray.java,v $ $Revision: 1.1 $ $Date: 2000/04/20 17:45:10 $
 *
 * (C) Copyright IBM Corp. 1998-1999.  All Rights Reserved.
 *
 * The program is provided "as is" without any warranty express or
 * implied, including the warranty of non-infringement and the implied
 * warranties of merchantibility and fitness for a particular purpose.
 * IBM will not be liable for any damages suffered by you as a result
 * of using the Program. In no event will IBM be liable for any
 * special, indirect or consequential damages or lost profits even if
 * IBM has been advised of the possibility of their occurrence. IBM
 * will not be liable for any third party claims against you.
 */
/**
* This class maintains intervals within a piece of text.  Interval boundaries
* are stored in the fRunStart array.  Interval boundaries may have a
* positive or negative representation.  A positive boundary is given as an offset
* from 0.  A negative boundary is given as a negative offset from the ned of the text.
* The RunArray stores positive boundaries in the entries [0, fPosEnd], and negative
* boundaries in the entries [fNegStart, fLength).  New boundaries may be inserted into
* the undefined middle of the RunArray.  If fPosEnd < 0, there are no positive entries.
* If fNegStart >= fRunArray.length, there are no negative netries.  It's possible to have
* a runarray with neither positive or negative entries.
*
* As an example of how the RunArray works, consider a piece of text with 5 intervals,
* where each interval is 3 characters in length.  The RunArray for this text could
* look like:
*    fCurTextLength = 15, fPosEnd = 5, fNegStart = 10,
*    fRunStart = { 0, 3, 6, 9, 12, U, U, U, U, U };
* where U is an undefined array element.

* An equivalent representation would be:
*    fCurTextLength = 15, fPosEnd = 3, fNegStart = 8,
*    fRunStart = { 0, 3, 6, U, U, U, U, U, -6, -3 };
*
* The RunArray class is used in the StyleBuffer and the ParagraphBuffer.  In the StyleBuffer,
* the entries in fRunStart give the offsets where style runs begin.  In the
* ParagraphBuffer, the fRunStart entries store offsets of paragraph breaks.
*
* This class provides methods for shifting the run table to a particular position, expanding the
* run table, and returning the index of the run containing a particular offset in the text.  All
* other functionality is implemented in the RunArray clients.
*
* RunArray uses FastIntBinarySearch for searches.  The searches are constructed on demand in
* the findRunContaining method.  The searches are invalidated when the run array is shifted;
* however, the RunArray can be modified by other classes.  Thus, if another class modifies
* the entries in fRunArray, or modifies fPosEnd or fNegStart, it is responsible for
* calling runStartsChanged.
*/

package com.ibm.richtext.styledtext;

import java.io.Externalizable;
import java.io.ObjectInput;
import java.io.ObjectOutput;
import java.io.IOException;

final class RunArray implements Externalizable {

    static final String COPYRIGHT =
                "(C) Copyright IBM Corp. 1998-1999 - All Rights Reserved";
    private static final long serialVersionUID = 22356934;

    int[] fRunStart;
    private int fCurTextLength;
    int fPosEnd, fNegStart;
    
    transient private FastIntBinarySearch fPosSearch;
    transient private boolean fPosSearchValid;
    transient private FastIntBinarySearch fNegSearch;
    transient private boolean fNegSearchValid;

    private static final int CURRENT_VERSION = 1;

    RunArray(int initialSize, int curTextLength) {

        fRunStart = new int[initialSize];
        fCurTextLength = curTextLength;
        fPosEnd = -1;
        fNegStart = initialSize;
        
        fPosSearch = new FastIntBinarySearch(fRunStart, 0, 1);
        fNegSearch = new FastIntBinarySearch(fRunStart, 0, 1);
        fPosSearchValid = fNegSearchValid = false;
    }

    /**
     * Note: this constructor is ONLY for use by the Serialization
     * mechanism.  It does not leave this object in a valid state!
     */
    public RunArray() {
    }

    public void writeExternal(ObjectOutput out) throws IOException {

        out.writeInt(CURRENT_VERSION);
        out.writeObject(fRunStart);
        out.writeInt(fCurTextLength);
        out.writeInt(fPosEnd);
        out.writeInt(fNegStart);
    }

    public void readExternal(ObjectInput in) throws IOException,
                                            ClassNotFoundException {

        if (in.readInt() != CURRENT_VERSION) {
            throw new IOException("Invalid version of RunArray");
        }
        fRunStart = (int[]) in.readObject();
        fCurTextLength = in.readInt();
        fPosEnd = in.readInt();
        fNegStart = in.readInt();
        
        fPosSearch = new FastIntBinarySearch(fRunStart, 0, 1);
        fNegSearch = new FastIntBinarySearch(fRunStart, 0, 1);
        fPosSearchValid = fNegSearchValid = false;
    }

    public int getCurTextLength() {

        return fCurTextLength;
    }

    public void setCurTextLength(int curTextLength) {

        fCurTextLength = curTextLength;
    }

    public void addToCurTextLength(int delta) {

        fCurTextLength += delta;
    }

    public void runStartsChanged() {

        fPosSearchValid = fNegSearchValid = false;
    }

/**
* Returns the index of the last valid run.
*/
    int lastRun() {

        return (fNegStart == fRunStart.length)? fPosEnd : fRunStart.length-1;
    }

/**
* Returns the length of the run array.  Replaces old fLength member.
*/
    int getArrayLength() {

        return fRunStart.length;
    }

/**
* Shifts style table such that the last positive run
* starts before pos.
*/
    void shiftTableTo(int pos) {

        int oldPosEnd = fPosEnd;

        while (fPosEnd >= 0 && fRunStart[fPosEnd] >= pos) {

            fNegStart--;
            fRunStart[fNegStart] = fRunStart[fPosEnd] - fCurTextLength;
            fPosEnd--;

        }

        pos -= fCurTextLength;

        while (fNegStart<fRunStart.length && fRunStart[fNegStart] < pos) {

            fPosEnd++;
            fRunStart[fPosEnd] = fRunStart[fNegStart] + fCurTextLength;
            fNegStart++;
        }

        if (oldPosEnd != fPosEnd) {
            fPosSearchValid = fNegSearchValid = false;
        }
    }

/**
* Returns index of style run containing pos.  If first style run starts before
* pos, -1 is returned.  If pos is greater than text length, lastrun is returned.
*/
    int findRunContaining(int pos) {

        FastIntBinarySearch search;
        final int length = fRunStart.length;

        if (fNegStart < length && (pos-fCurTextLength >= fRunStart[fNegStart])) {

            pos -= fCurTextLength;

            if (!fNegSearchValid) {
                fNegSearch.setData(fRunStart, fNegStart, length-fNegStart);
            }
            search = fNegSearch;
        }
        else if (fPosEnd >= 0) {

            if (!fPosSearchValid) {
                fPosSearch.setData(fRunStart, 0, fPosEnd+1);
            }
            search = fPosSearch;
        }
        else
            return -1;

        int run = search.findIndex(pos);

        return run;
    }

    int getLogicalRunStart(int run) {

        if (run == -1) {
            return 0;
        }
        else if (run == fRunStart.length) {
            return fCurTextLength;
        }
        else {
            if (run <= fPosEnd) {
                return fRunStart[run];
            }
            else if (run >= fNegStart) {
                return fRunStart[run] + fCurTextLength;
            }
            else {
                throw new IllegalArgumentException("Illegal run");
            }
        }
    }

/**
* Increases size of run table.  Current implementation doubles the run table's size.
*/
    void expandRunTable() {

        resizeRunTable(fRunStart.length * 2);
    }

/**
* Return the minimum number of elements possible in fRunStart.
*/
    private int getMinSize() {

        return Math.max(fPosEnd + (fRunStart.length-fNegStart) + 1, 1);
    }

    void compress() {

        int minSize = getMinSize();
        if (fRunStart.length > minSize) {
            resizeRunTable(minSize);
        }
    }

    private void resizeRunTable(int newSize) {

        if (newSize < getMinSize()) {
            throw new IllegalArgumentException("Attempt to make RunArray too small.");
        }

        final int oldLength = fRunStart.length;

        int newRunStart[] = new int[newSize];
        System.arraycopy(fRunStart, 0, newRunStart, 0, fPosEnd+1);
        int newNegStart = newRunStart.length - (oldLength-fNegStart);
        System.arraycopy(fRunStart, fNegStart, newRunStart, newNegStart, (oldLength-fNegStart));

        fNegStart = newNegStart;
        fRunStart = newRunStart;

        fPosSearchValid = fNegSearchValid = false;
    }
}