Programming Languages Suite/ProgLangD.iso/VCAFE.3.0A/Main.bin/Matrix.java

Text File | 1998-09-16 | 17KB | 661 lines

package symantec.itools.awt;

import java.util.ResourceBundle;

// ===================================================================================
// = Revision History
// ===================================================================================

// Matrix
//        This class implements a sparse matrix of objects
//

//  03/20/97    RKM    Made the class public as per customer request
//                    Removed bogus debugging code
//                    Removed compaction of empty rows code
//  03/27/97    RKM    Made class final (this class is not made to be extended)
//                    Followed example of Vector, and added JavaDoc, throws, & synchronized
//                    Made final
//                    Tried to make some sense of protection on methods & members
//  03/28/97    RKM    Un-privitized members
//  05/02/97    RKM    Fixed removeRow - made it actually work
//  05/02/97    RKM    Fixed insertRow - one of the loops was not checking for null
//  05/13/97    TNM    Added new interface CompareFuncCB to fix MultiList to not lose selection when sorting
//  05/30/97    RKM    Moved CompareFunc interface into it's own file, at compiler's request
//  07/19/97    LAB    Moved CompareFuncCB interface into it's own file, at compiler's request
//  07/23/97    CAR added java.io.Serializable interface
//  09/16/98    MSH Fixed insertRow - it now works when inserting a row at row 0 (#55390)
//                  Removed references to chicken-blood in the comments

/**
 * This class implements a sparse matrix of objects.
 * @version 1.0, Nov 26, 1996
 * @author    Symantec
 */
public final class Matrix implements java.io.Serializable
{
    //--------------------------------------------------
    // public constructors
    //--------------------------------------------------

    /**
     * Constructs an empty matrix.
     */
    public Matrix()
    {
        rowHead = this;
        errors = ResourceBundle.getBundle("symantec.itools.resources.ErrorsBundle");
    }

    //--------------------------------------------------
    // private constructors
    //--------------------------------------------------

    private Matrix(int r, int c, Object obj)
    {
        this(r, c, obj, null);
    }

    private Matrix(int r, int c, Object obj, Matrix rh, Matrix nr, Matrix ne)
    {
        errors = ResourceBundle.getBundle("symantec.itools.resources.ErrorsBundle");
        if (rh == null)
        {
            if (c != 0)
            {
                rowHead = new Matrix(r, 0, null, null, nr, this);
            }
            else
            {
                rowHead = this;
            }
        }
        else
        {
            rowHead = rh;
        }

        row = r;
        col = c;
        o = obj;
        nextRow = nr;
        nextElt = ne;
    }

    private Matrix(int r, int c, Object obj, Matrix nr, Matrix ne)
    {
        this(r, c, obj, null, nr, ne);
    }

    private Matrix(int r, int c, Object obj, Matrix nr)
    {
        this(r, c, obj, null, nr, null);
    }

    //--------------------------------------------------
    // public methods
    //--------------------------------------------------

    /**
     * Adds the given element to this matrix at the specified row and column.
     * @param r the row of the element to be added
     * @param c the column of the element to added
     * @param o the element to be added
     * @exception IllegalArgumentException if an element is already allocated
     * at [r,c]
     * @see #updateElement
     * @see #removeElementAt
     */
    public synchronized void addElement(int r, int c, Object o)
        throws IllegalArgumentException
    {
        //find the correct row
        Matrix m = nearest(r, c);

        if (m.row != r)
        {
            m.setNextRow(new Matrix(r, c, o, m.nextRow).rowHead);
            return;
        }

        //m must equal row
        if (c == m.col && c == 0)
        {
            if (m.o != null)
            {
                //exception - should call update
                throw new IllegalArgumentException(errors.getString("ElementAlreadyInMatrix"));
            }
            else
            {
                m.o = o;
                return;
            }
        }

        m.nextElt = new Matrix(r, c, o, m.rowHead, m.nextRow, m.nextElt);
    }

    /**
     * Adds or updates the element at the specified row and column, as needed.
     * @param r the row of the element to be updated
     * @param c the column of the element to updated
     * @param o the new element
     * @see #addElement
     * @see #removeElementAt
     */
    public synchronized void updateElement(int r, int c, Object obj)
    {
        Matrix m = nearest(r, c);

        try
        {
            if (m == null)
            {
                //first element in matrix
                addElement(r, c, obj);
            }
            else if (m.row != r || m.col != c)
            {
                m.addElement(r, c, obj);
            }
            else
            {
                //must be the element
                m.o = obj;
            }
        }
        catch(IllegalArgumentException iae)
        {
            iae.printStackTrace();
        }
    }

    /**
     * Removes all elements of the matrix. The matrix becomes empty.
     * @see #addElement
     * @see #removeElementAt
     */
    public synchronized void removeAllElements()
    {
        nextRow = null;
        nextElt = null;
        o = null;
    }

    /**
     * Returns the element at the specified row and column.
     * @param r the row of the element to return
     * @param c the column of the element to return
     * @return the element at [r,c]
     * @exception ArrayIndexOutOfBoundsException if an invalid
     * row and/or column was given
     */
    public synchronized Object elementAt(int r, int c)
        throws ArrayIndexOutOfBoundsException
    {
        Matrix m = nearest(r, c);

        if (m == null || m.row != r || m.col != c || m.o == null){
            Object[] args = { new Integer(r), new Integer(c) };
            throw new ArrayIndexOutOfBoundsException(java.text.MessageFormat.format(errors.getString("ElementNotInMatrix"), args));
        }

        return m.o;
    }

    /**
     * Deletes the element at the specified row and column.
     * @param r the row of the element to remove
     * @param c the column of the element to remove
     * @exception ArrayIndexOutOfBoundsException if an invalid
     * row and/or column was given
     */
    public synchronized void removeElementAt(int r, int c)
        throws ArrayIndexOutOfBoundsException
    {
        Matrix m = nearest(r, c);

        if (m == null || m.row != r || m.col != c) {
            Object[] args = { new Integer(r), new Integer(c) };
            throw new ArrayIndexOutOfBoundsException(java.text.MessageFormat.format(errors.getString("ElementNotInMatrix"), args));
        }

        if (c == 0)
        {
            m.o = null;
            return;
        }

        Matrix prev = m = m.rowHead;

        while(m.col != c)
        {
            prev = m;
            m = m.nextElt;
        }

        prev.nextElt = m.nextElt;
    }

    /**
     * Deletes all elements on the specified row.
     * @param r the row of the elements to remove
     * @see #insertRow
     * @see #removeElementAt
     */
    public synchronized void removeRow(int r)
    {
        //Removing zero is a special case, essentially we have to change this
        if (r == 0)
        {
            this.o            = null;
            this.nextElt    = null;
            if (this.nextRow != null)
            {
                //Remove new zero elem from the row list and assign its data into this
                Matrix newZeroElem = this.nextRow;
                this.nextRow    = newZeroElem.nextRow;
                this.nextElt    = newZeroElem.nextElt;
                this.row        = newZeroElem.row;
                this.col        = newZeroElem.col;
                this.o            = newZeroElem.o;

                //Hook up rowHeads of the elements in zero elem (since it's now this)
                {
                    Matrix elemMatrix = this.nextElt;
                    while (elemMatrix != null)
                    {
                        elemMatrix.rowHead = this;
                        elemMatrix = elemMatrix.nextElt;
                    }
                }

                //Decrement row of all matrixs
                Matrix stepMatrix = this;
                while (stepMatrix != null)
                {
                    stepMatrix.updateRowNum(stepMatrix.row - 1);
                    stepMatrix = stepMatrix.nextRow;
                }
            }
        }
        else
        {
            //Find the matrix that comes before the row, if it exists
            Matrix stepMatrix = this.nextRow;
            Matrix lastRow = this;
            while (stepMatrix != null && stepMatrix.row < r)
            {
                lastRow = stepMatrix;
                stepMatrix = stepMatrix.nextRow;
            }

            if (stepMatrix != null)
            {
                //We have an explicit row matrix
                if (stepMatrix.row == r)
                {
                    //Skip it in the chain
                    lastRow.nextRow = stepMatrix.nextRow;

                    stepMatrix.o = null;
                    stepMatrix.nextElt = null;

                    //Advance a row (number changing purposes)
                    stepMatrix = stepMatrix.nextRow;
                }

                //Change the row numbers of all the remaining rows
                while (stepMatrix != null)
                {
                    stepMatrix.updateRowNum(stepMatrix.row - 1);
                    stepMatrix = stepMatrix.nextRow;
                }
            }
        }

        /* RKM Was
        Matrix m = nearest(r, 0);

        if (m.row == r)
        {
            m = m.rowHead;
            m.o = null;
            m.nextElt = null;
        }
        */
    }

    /**
     * Inserts a new row at the given location.
     * It does this by incrementing the row number of all elements with
     * row indexes >= given row number.
     * @param r the number of the row to insert
     * @see #removeRow
     */
    public synchronized void insertRow(int r)
    {
        Matrix m, n;

        if (r == 0)
        {
            m = new Matrix();   // make a new matrix and copy current item at 0,0
            m.rowHead = m;
            m.nextRow = this.nextRow;
            m.nextElt = this.nextElt;
            m.o       = this.o;

            this.nextRow = m;   // set up this to be the new "origin" item
            this.nextElt = null;
            this.o       = null;
            m = this;           // need to do this so row re-numbering happens
        }
        else
        {
            m = nearest(r-1, 0);
            n = new Matrix(r, 0, null, m.nextRow);
            m.setNextRow(n);
            m = n;
        }

        if (m.nextRow.row == r)
        {
            //slip and increment row numbers
            m = m.nextRow;

            while(m != null)
            {
                m.updateRowNum(++r);
                m = m.nextRow;
                if (m != null && m.row != r) return;
            }
        }
    }

    /**
     * Sorts all rows into ascending order.
     * It does this by comparing elements at the given
     * column number using the provided CompareFunc.
     * @param f compares two objects and determines which one is less than the other
     * @param c the column number of elements to compare
     */
    public synchronized void sort(CompareFunc f, int c)
    {
        boolean first = true;
        Matrix  m = this,
                n = null;

        while(m != null)
        {
            n = findLeast(f, m, c, first);

            if (n != null)
            {
                if (m.row == 0 && first)
                {
                    first = false;
                    if(f instanceof CompareFuncCB)
                        ((CompareFuncCB)f).callBackSwap(m, n.nextRow);
                    swapRows(n);
                    m = this;
                    continue;
                 }
                 else
                 {
                    if(f instanceof CompareFuncCB)
                        ((CompareFuncCB)f).callBackSwap(m.nextRow, n.nextRow);
                    swapRows(m, n);
                 }
            }

            if (first)
            {
                first = false;
                continue;
            }

            m = m.nextRow;
        }
    }

    /**
     * Prints the specified row to System.out.
     * This can be handy for debugging purposes.
     * @param r the row to print
     */
    public synchronized void printRow(int r)
    {
        Matrix m = nearest(r, 0);

        if (m.row != r)
        {
            m = m.nextRow;
            if (m.row != r)
            {
                Object[] args = { new Integer(r) };
                System.out.println(java.text.MessageFormat.format(errors.getString("RowNotInMatrix"), args));
                return;
            }
        }

        System.out.println("-------- Printing row " + r + " ----------");
        while(m != null)
        {
            System.out.println("Row=" + m.row + "  Col=" + m.col + "  value=" + m.o);
            m = m.nextElt;
        }
    }

    /**
     * Returns the number of rows in the matrix.
     */
    public synchronized int rows()
    {
        Matrix m = this;

        while(m.nextRow != null)
        {
            m = m.nextRow;
        }

        return (m.nextElt == null && m.o == null ? m.row : m.row+1);
    }

    //only call on row head
    private synchronized void updateRowNum(int r)
    {
        Matrix m = this;

        while(m != null)
        {
            m.row = r;
            m = m.nextElt;
        }
    }

    /**
     * Returns an enumeration of all the elements. Use the enumeration methods
     * of the returned object to fetch the elements sequentially.
     */
    public synchronized MatrixEnumeration elements()
    {
        return new MatrixEnumeration(this);
    }

    /**
     * Returns a string representation of this component.
     * This is a standard Java AWT method which gets called to generate
     * a string that represents this component.
     *
     * @return a meaningful string about this object
     */
    public synchronized String toString()
    {
        return "Matrix: row=" + row + " col=" + col + " o=" + o;
    }

    //--------------------------------------------------
    // private members
    //--------------------------------------------------

    private synchronized Matrix nearest(int r, int c)
    {
        //find the correct row
        Matrix m = this;

        while (r > m.row)
        {
            if (m.nextRow != null && m.nextRow.row <= r)
            {
                //further down pike so keep climbing
                m = m.nextRow;
            }
            else
            {
                return m;
            }
        }

        //m must equal row
        while (m.nextElt != null && c >= m.nextElt.col)
        {
            //further down the line
            m = m.nextElt;
        }

        return m;
    }

    private synchronized void setRowHead()
    {
        Matrix m = nextElt;
        Matrix h = this;

        while (m != null)
        {
            m.rowHead = h;
            m = m.nextElt;
        }
    }

    private synchronized void setNextRow(Matrix nr)
    {
        Matrix m = this;

        while(m != null)
        {
            m.nextRow = nr;
            m = m.nextElt;
        }
    }

    //m1 & m2 preceed the two rows to be switched.
    private synchronized void swapRows(Matrix p1, Matrix p2)
    {
        Matrix t1 = p1.nextRow;
        Matrix t1NextRow = t1.nextRow;
        Matrix t2 = p2.nextRow;
        Matrix t2NextRow = t2.nextRow;

        p1.setNextRow(t2);
        p2.setNextRow(t1);

        if (p2 == t1)
        {
            t2.setNextRow(t1);
        }
        else
        {
            t2.setNextRow(t1NextRow);
        }

        t1.setNextRow(t2NextRow);
        int t1Row = t1.row;
        t1.updateRowNum(t2.row);
        t2.updateRowNum(t1Row);
    }

    //swap the current row (must be the first) with the row following m2
    private synchronized void swapRows(Matrix m2)
    {
        Matrix t2 = m2.nextRow;
        Matrix t1 = new Matrix(-1, t2.col, o, null, nextElt);
        m2.rowHead.setNextRow(t1);
        t1.setNextRow(t2.nextRow);
        t1.updateRowNum(t2.row);
        t1.setRowHead();

        //fixup root node (that is this)
        nextElt = t2.nextElt;
        o = t2.o;
        setNextRow(nextRow);  //this.nextRow never changed so can use for update
        updateRowNum(0);
        setRowHead();
    }

    private synchronized Matrix findLeast(CompareFunc f, Matrix m, int c, boolean first)
    {
        //m is row previous to one to be compared to when m.row != 0
        if (!first)
            m = m.nextRow;

        if(m == null || m.nextRow == null)
            return null;

        Matrix n = m.nextRow.rowHead;
        Matrix prevToN = m.rowHead;
        Matrix prevToLeast = null;

        m = m.nearest(m.row, c);

        while (n != null)
        {
            n = n.nearest(n.row, c);

            if (n.col != c)
            {
                //no item for column on next row so keep searching
                prevToN = n.rowHead;
                n = n.nextRow;
                continue;
            }
            else if (m.col != c)
            {
                //no item for first column so automatically sent down
                m = n;
                prevToLeast = prevToN;
                continue;
            }

            if (f.lessThan(n.o, m.o))
            {
                //n < m so put n in for least
                m = n;
                prevToLeast = prevToN;
            }

            prevToN = n.rowHead;
            n = n.nextRow;
        }

        return prevToLeast;
    }

    /**
     * Error strings.
     */
    transient protected ResourceBundle errors;

    //--------------------------------------------------
    // private members
    //--------------------------------------------------

    Matrix        rowHead;
    Matrix        nextRow;
    Matrix        nextElt;
    int            row;
    int            col;
    Object        o;
}