home *** CD-ROM | disk | FTP | other *** search
/ Symantec Visual Cafe for Java 2.5 / symantec-visual-cafe-2.5-database-dev-edition.iso / VCafe / Source.bin / Matrix.java < prev    next >
Encoding:
Java Source  |  1998-09-14  |  16.4 KB  |  669 lines

  1. package symantec.itools.awt;
  2.  
  3. import java.util.ResourceBundle;
  4.  
  5. // ===================================================================================
  6. // = Revision History
  7. // ===================================================================================
  8.  
  9. // Matrix
  10. //        This class implements a sparse matrix of objects
  11. //
  12.  
  13. //  03/20/97    RKM    Made the class public as per customer request
  14. //                    Removed bogus debugging code
  15. //                    Removed compaction of empty rows code
  16. //  03/27/97    RKM    Made class final (this class is not made to be extended)
  17. //                    Followed example of Vector, and added JavaDoc, throws, & synchronized
  18. //                    Made final
  19. //                    Tried to make some sense of protection on methods & members
  20. //  03/28/97    RKM    Un-privitized members
  21. //  05/02/97    RKM    Fixed removeRow - made it actually work
  22. //  05/02/97    RKM    Fixed insertRow - one of the loops was not checking for null
  23. //  05/13/97    TNM    Added new interface CompareFuncCB to fix MultiList to not lose selection when sorting
  24. //  05/30/97    RKM    Moved CompareFunc interface into it's own file, at compiler's request
  25. //  07/19/97    LAB    Moved CompareFuncCB interface into it's own file, at compiler's request
  26. //  07/23/97    CAR added java.io.Serializable interface
  27.  
  28. /**
  29.  * This class implements a sparse matrix of objects.
  30.  * @version 1.0, Nov 26, 1996
  31.  * @author    Symantec
  32.  */
  33. public final class Matrix implements java.io.Serializable
  34. {
  35.     //--------------------------------------------------
  36.     // public constructors
  37.     //--------------------------------------------------
  38.  
  39.     /**
  40.      * Constructs an empty matrix.
  41.      */
  42.     public Matrix()
  43.     {
  44.         rowHead = this;
  45.         
  46.         try
  47.         {
  48.             errors = ResourceBundle.getBundle("symantec.itools.resources.ErrorsBundle");
  49.         }
  50.         catch(Throwable ex)
  51.         {
  52.             errors = new symantec.itools.resources.ErrorsBundle();
  53.         }
  54.     }
  55.  
  56.     //--------------------------------------------------
  57.     // private constructors
  58.     //--------------------------------------------------
  59.  
  60.     private Matrix(int r, int c, Object obj)
  61.     {
  62.         this(r, c, obj, null);
  63.     }
  64.  
  65.     private Matrix(int r, int c, Object obj, Matrix rh, Matrix nr, Matrix ne)
  66.     {        
  67.         try
  68.         {
  69.             errors = ResourceBundle.getBundle("symantec.itools.resources.ErrorsBundle");
  70.         }
  71.         catch(java.util.MissingResourceException ex)
  72.         {
  73.             System.out.println("D'Arcy's resource fix");
  74.             errors = new symantec.itools.resources.ErrorsBundle();
  75.         }
  76.         
  77.         if (rh == null)
  78.         {
  79.             if (c != 0)
  80.             {
  81.                 rowHead = new Matrix(r, 0, null, null, nr, this);
  82.             }
  83.             else
  84.             {
  85.                 rowHead = this;
  86.             }
  87.         }
  88.         else
  89.         {
  90.             rowHead = rh;
  91.         }
  92.  
  93.         row = r;
  94.         col = c;
  95.         o = obj;
  96.         nextRow = nr;
  97.         nextElt = ne;
  98.     }
  99.  
  100.     private Matrix(int r, int c, Object obj, Matrix nr, Matrix ne)
  101.     {
  102.         this(r, c, obj, null, nr, ne);
  103.     }
  104.  
  105.     private Matrix(int r, int c, Object obj, Matrix nr)
  106.     {
  107.         this(r, c, obj, null, nr, null);
  108.     }
  109.  
  110.     //--------------------------------------------------
  111.     // public methods
  112.     //--------------------------------------------------
  113.  
  114.     /**
  115.      * Adds the given element to this matrix at the specified row and column.
  116.      * @param r the row of the element to be added
  117.      * @param c the column of the element to added
  118.      * @param o the element to be added
  119.      * @exception IllegalArgumentException if an element is already allocated
  120.      * at [r,c]
  121.      * @see #updateElement
  122.      * @see #removeElementAt
  123.      */
  124.     public synchronized void addElement(int r, int c, Object o)
  125.         throws IllegalArgumentException
  126.     {
  127.         //find the correct row
  128.         Matrix m = nearest(r, c);
  129.  
  130.         if (m.row != r)
  131.         {
  132.             m.setNextRow(new Matrix(r, c, o, m.nextRow).rowHead);
  133.             return;
  134.         }
  135.  
  136.         //m must equal row
  137.         if (c == m.col && c == 0)
  138.         {
  139.             if (m.o != null)
  140.             {
  141.                 //exception - should call update
  142.                 throw new IllegalArgumentException(errors.getString("ElementAlreadyInMatrix"));
  143.             }
  144.             else
  145.             {
  146.                 m.o = o;
  147.                 return;
  148.             }
  149.         }
  150.  
  151.         m.nextElt = new Matrix(r, c, o, m.rowHead, m.nextRow, m.nextElt);
  152.     }
  153.  
  154.     /**
  155.      * Adds or updates the element at the specified row and column, as needed.
  156.      * @param r the row of the element to be updated
  157.      * @param c the column of the element to updated
  158.      * @param o the new element
  159.      * @see #addElement
  160.      * @see #removeElementAt
  161.      */
  162.     public synchronized void updateElement(int r, int c, Object obj)
  163.     {
  164.         Matrix m = nearest(r, c);
  165.  
  166.         try
  167.         {
  168.             if (m == null)
  169.             {
  170.                 //first element in matrix
  171.                 addElement(r, c, obj);
  172.             }
  173.             else if (m.row != r || m.col != c)
  174.             {
  175.                 m.addElement(r, c, obj);
  176.             }
  177.             else
  178.             {
  179.                 //must be the element
  180.                 m.o = obj;
  181.             }
  182.         }
  183.         catch(IllegalArgumentException iae)
  184.         {
  185.             iae.printStackTrace();
  186.         }
  187.     }
  188.  
  189.     /**
  190.      * Removes all elements of the matrix. The matrix becomes empty.
  191.      * @see #addElement
  192.      * @see #removeElementAt
  193.      */
  194.     public synchronized void removeAllElements()
  195.     {
  196.         nextRow = null;
  197.         nextElt = null;
  198.         o = null;
  199.     }
  200.  
  201.     /**
  202.      * Returns the element at the specified row and column.
  203.      * @param r the row of the element to return
  204.      * @param c the column of the element to return
  205.      * @return the element at [r,c]
  206.      * @exception ArrayIndexOutOfBoundsException if an invalid
  207.      * row and/or column was given
  208.      */
  209.     public synchronized Object elementAt(int r, int c)
  210.         throws ArrayIndexOutOfBoundsException
  211.     {
  212.         Matrix m = nearest(r, c);
  213.  
  214.         if (m == null || m.row != r || m.col != c || m.o == null){
  215.             Object[] args = { new Integer(r), new Integer(c) };
  216.             throw new ArrayIndexOutOfBoundsException(java.text.MessageFormat.format(errors.getString("ElementNotInMatrix"), args));
  217.         }
  218.  
  219.         return m.o;
  220.     }
  221.  
  222.     /**
  223.      * Deletes the element at the specified row and column.
  224.      * @param r the row of the element to remove
  225.      * @param c the column of the element to remove
  226.      * @exception ArrayIndexOutOfBoundsException if an invalid
  227.      * row and/or column was given
  228.      */
  229.     public synchronized void removeElementAt(int r, int c)
  230.         throws ArrayIndexOutOfBoundsException
  231.     {
  232.         Matrix m = nearest(r, c);
  233.  
  234.         if (m == null || m.row != r || m.col != c) {
  235.             Object[] args = { new Integer(r), new Integer(c) };
  236.             throw new ArrayIndexOutOfBoundsException(java.text.MessageFormat.format(errors.getString("ElementNotInMatrix"), args));
  237.         }
  238.  
  239.         if (c == 0)
  240.         {
  241.             m.o = null;
  242.             return;
  243.         }
  244.  
  245.         Matrix prev = m = m.rowHead;
  246.  
  247.         while(m.col != c)
  248.         {
  249.             prev = m;
  250.             m = m.nextElt;
  251.         }
  252.  
  253.         prev.nextElt = m.nextElt;
  254.     }
  255.  
  256.     /**
  257.      * Deletes all elements on the specified row.
  258.      * @param r the row of the elements to remove
  259.      * @see #insertRow
  260.      * @see #removeElementAt
  261.      */
  262.     public synchronized void removeRow(int r)
  263.     {
  264.         //Removing zero is a special case, essentially we have to change this
  265.         if (r == 0)
  266.         {
  267.             this.o            = null;
  268.             this.nextElt    = null;
  269.             if (this.nextRow != null)
  270.             {
  271.                 //Remove new zero elem from the row list and assign its data into this
  272.                 Matrix newZeroElem = this.nextRow;
  273.                 this.nextRow    = newZeroElem.nextRow;
  274.                 this.nextElt    = newZeroElem.nextElt;
  275.                 this.row        = newZeroElem.row;
  276.                 this.col        = newZeroElem.col;
  277.                 this.o            = newZeroElem.o;
  278.  
  279.                 //Hook up rowHeads of the elements in zero elem (since it's now this)
  280.                 {
  281.                     Matrix elemMatrix = this.nextElt;
  282.                     while (elemMatrix != null)
  283.                     {
  284.                         elemMatrix.rowHead = this;
  285.                         elemMatrix = elemMatrix.nextElt;
  286.                     }
  287.                 }
  288.  
  289.                 //Decrement row of all matrixs
  290.                 Matrix stepMatrix = this;
  291.                 while (stepMatrix != null)
  292.                 {
  293.                     stepMatrix.updateRowNum(stepMatrix.row - 1);
  294.                     stepMatrix = stepMatrix.nextRow;
  295.                 }
  296.             }
  297.         }
  298.         else
  299.         {
  300.             //Find the matrix that comes before the row, if it exists
  301.             Matrix stepMatrix = this.nextRow;
  302.             Matrix lastRow = this;
  303.             while (stepMatrix != null && stepMatrix.row < r)
  304.             {
  305.                 lastRow = stepMatrix;
  306.                 stepMatrix = stepMatrix.nextRow;
  307.             }
  308.  
  309.             if (stepMatrix != null)
  310.             {
  311.                 //We have an explicit row matrix
  312.                 if (stepMatrix.row == r)
  313.                 {
  314.                     //Skip it in the chain
  315.                     lastRow.nextRow = stepMatrix.nextRow;
  316.  
  317.                     //???RKM??? I thought I understood this class, until this was required
  318.                     //???RKM??? This is chicken blood - I don't know why it's here !!!
  319.                     stepMatrix.o = null;
  320.                     stepMatrix.nextElt = null;
  321.  
  322.                     //Advance a row (number changing purposes)
  323.                     stepMatrix = stepMatrix.nextRow;
  324.                 }
  325.  
  326.                 //Change the row numbers of all the remaining rows
  327.                 while (stepMatrix != null)
  328.                 {
  329.                     stepMatrix.updateRowNum(stepMatrix.row - 1);
  330.                     stepMatrix = stepMatrix.nextRow;
  331.                 }
  332.             }
  333.         }
  334.  
  335.         /* RKM Was
  336.         Matrix m = nearest(r, 0);
  337.  
  338.         if (m.row == r)
  339.         {
  340.             m = m.rowHead;
  341.             m.o = null;
  342.             m.nextElt = null;
  343.         }
  344.         */
  345.     }
  346.  
  347.     /**
  348.      * Inserts a new row at the given location.
  349.      * It does this by incrementing the row number of all elements with
  350.      * row indexes >= given row number.
  351.      * @param r the number of the row to insert
  352.      * @see #removeRow
  353.      */
  354.     public synchronized void insertRow(int r)
  355.     {
  356.         Matrix m, n;
  357.  
  358.         if (r == 0)
  359.         {
  360.             //???RKM??? I don't see how this can work ???
  361.  
  362.             //want to insert into first row
  363.             m = new Matrix();
  364.             m.setNextRow(this);
  365.         }
  366.         else
  367.         {
  368.             m = nearest(r-1, 0);
  369.             n = new Matrix(r, 0, null, m.nextRow);
  370.             m.setNextRow(n);
  371.             m = n;
  372.         }
  373.  
  374.         if (m.nextRow.row == r)
  375.         {
  376.             //slip and increment row numbers
  377.             m = m.nextRow;
  378.  
  379.             while(m != null)
  380.             {
  381.                 m.updateRowNum(++r);
  382.                 m = m.nextRow;
  383.                 if (m != null && m.row != r) return;
  384.             }
  385.         }
  386.     }
  387.  
  388.     /**
  389.      * Sorts all rows into ascending order.
  390.      * It does this by comparing elements at the given
  391.      * column number using the provided CompareFunc.
  392.      * @param f compares two objects and determines which one is less than the other
  393.      * @param c the column number of elements to compare
  394.      */
  395.     public synchronized void sort(CompareFunc f, int c)
  396.     {
  397.         boolean first = true;
  398.         Matrix  m = this,
  399.                 n = null;
  400.  
  401.         while(m != null)
  402.         {
  403.             n = findLeast(f, m, c, first);
  404.  
  405.             if (n != null)
  406.             {
  407.                 if (m.row == 0 && first)
  408.                 {
  409.                     first = false;
  410.                     if(f instanceof CompareFuncCB)
  411.                         ((CompareFuncCB)f).callBackSwap(m, n.nextRow);
  412.                     swapRows(n);
  413.                     m = this;
  414.                     continue;
  415.                  }
  416.                  else
  417.                  {
  418.                     if(f instanceof CompareFuncCB)
  419.                         ((CompareFuncCB)f).callBackSwap(m.nextRow, n.nextRow);
  420.                     swapRows(m, n);
  421.                  }
  422.             }
  423.  
  424.             if (first)
  425.             {
  426.                 first = false;
  427.                 continue;
  428.             }
  429.  
  430.             m = m.nextRow;
  431.         }
  432.     }
  433.  
  434.     /**
  435.      * Prints the specified row to System.out.
  436.      * This can be handy for debugging purposes.
  437.      * @param r the row to print
  438.      */
  439.     public synchronized void printRow(int r)
  440.     {
  441.         Matrix m = nearest(r, 0);
  442.  
  443.         if (m.row != r)
  444.         {
  445.             m = m.nextRow;
  446.             if (m.row != r)
  447.             {
  448.                 Object[] args = { new Integer(r) };
  449.                 System.out.println(java.text.MessageFormat.format(errors.getString("RowNotInMatrix"), args));
  450.                 return;
  451.             }
  452.         }
  453.  
  454.         System.out.println("-------- Printing row " + r + " ----------");
  455.         while(m != null)
  456.         {
  457.             System.out.println("Row=" + m.row + "  Col=" + m.col + "  value=" + m.o);
  458.             m = m.nextElt;
  459.         }
  460.     }
  461.  
  462.     /**
  463.      * Returns the number of rows in the matrix.
  464.      */
  465.     public synchronized int rows()
  466.     {
  467.         Matrix m = this;
  468.  
  469.         while(m.nextRow != null)
  470.         {
  471.             m = m.nextRow;
  472.         }
  473.  
  474.         return (m.nextElt == null && m.o == null ? m.row : m.row+1);
  475.     }
  476.  
  477.     //only call on row head
  478.     private synchronized void updateRowNum(int r)
  479.     {
  480.         Matrix m = this;
  481.  
  482.         while(m != null)
  483.         {
  484.             m.row = r;
  485.             m = m.nextElt;
  486.         }
  487.     }
  488.  
  489.     /**
  490.      * Returns an enumeration of all the elements. Use the enumeration methods
  491.      * of the returned object to fetch the elements sequentially.
  492.      */
  493.     public synchronized MatrixEnumeration elements()
  494.     {
  495.         return new MatrixEnumeration(this);
  496.     }
  497.  
  498.     /**
  499.      * Returns a string representation of this component.
  500.      * This is a standard Java AWT method which gets called to generate
  501.      * a string that represents this component.
  502.      *
  503.      * @return a meaningful string about this object
  504.      */
  505.     public synchronized String toString()
  506.     {
  507.         return "Matrix: row=" + row + " col=" + col + " o=" + o;
  508.     }
  509.  
  510.     //--------------------------------------------------
  511.     // private members
  512.     //--------------------------------------------------
  513.  
  514.     private synchronized Matrix nearest(int r, int c)
  515.     {
  516.         //find the correct row
  517.         Matrix m = this;
  518.  
  519.         while (r > m.row)
  520.         {
  521.             if (m.nextRow != null && m.nextRow.row <= r)
  522.             {
  523.                 //further down pike so keep climbing
  524.                 m = m.nextRow;
  525.             }
  526.             else
  527.             {
  528.                 return m;
  529.             }
  530.         }
  531.  
  532.         //m must equal row
  533.         while (m.nextElt != null && c >= m.nextElt.col)
  534.         {
  535.             //further down the line
  536.             m = m.nextElt;
  537.         }
  538.  
  539.         return m;
  540.     }
  541.  
  542.     private synchronized void setRowHead()
  543.     {
  544.         Matrix m = nextElt;
  545.         Matrix h = this;
  546.  
  547.         while (m != null)
  548.         {
  549.             m.rowHead = h;
  550.             m = m.nextElt;
  551.         }
  552.     }
  553.  
  554.     private synchronized void setNextRow(Matrix nr)
  555.     {
  556.         Matrix m = this;
  557.  
  558.         while(m != null)
  559.         {
  560.             m.nextRow = nr;
  561.             m = m.nextElt;
  562.         }
  563.     }
  564.  
  565.     //m1 & m2 preceed the two rows to be switched.
  566.     private synchronized void swapRows(Matrix p1, Matrix p2)
  567.     {
  568.         Matrix t1 = p1.nextRow;
  569.         Matrix t1NextRow = t1.nextRow;
  570.         Matrix t2 = p2.nextRow;
  571.         Matrix t2NextRow = t2.nextRow;
  572.  
  573.         p1.setNextRow(t2);
  574.         p2.setNextRow(t1);
  575.  
  576.         if (p2 == t1)
  577.         {
  578.             t2.setNextRow(t1);
  579.         }
  580.         else
  581.         {
  582.             t2.setNextRow(t1NextRow);
  583.         }
  584.  
  585.         t1.setNextRow(t2NextRow);
  586.         int t1Row = t1.row;
  587.         t1.updateRowNum(t2.row);
  588.         t2.updateRowNum(t1Row);
  589.     }
  590.  
  591.     //swap the current row (must be the first) with the row following m2
  592.     private synchronized void swapRows(Matrix m2)
  593.     {
  594.         Matrix t2 = m2.nextRow;
  595.         Matrix t1 = new Matrix(-1, t2.col, o, null, nextElt);
  596.         m2.rowHead.setNextRow(t1);
  597.         t1.setNextRow(t2.nextRow);
  598.         t1.updateRowNum(t2.row);
  599.         t1.setRowHead();
  600.  
  601.         //fixup root node (that is this)
  602.         nextElt = t2.nextElt;
  603.         o = t2.o;
  604.         setNextRow(nextRow);  //this.nextRow never changed so can use for update
  605.         updateRowNum(0);
  606.         setRowHead();
  607.     }
  608.  
  609.     private synchronized Matrix findLeast(CompareFunc f, Matrix m, int c, boolean first)
  610.     {
  611.         //m is row previous to one to be compared to when m.row != 0
  612.         if (!first)
  613.             m = m.nextRow;
  614.  
  615.         if(m == null || m.nextRow == null)
  616.             return null;
  617.  
  618.         Matrix n = m.nextRow.rowHead;
  619.         Matrix prevToN = m.rowHead;
  620.         Matrix prevToLeast = null;
  621.  
  622.         m = m.nearest(m.row, c);
  623.  
  624.         while (n != null)
  625.         {
  626.             n = n.nearest(n.row, c);
  627.  
  628.             if (n.col != c)
  629.             {
  630.                 //no item for column on next row so keep searching
  631.                 prevToN = n.rowHead;
  632.                 n = n.nextRow;
  633.                 continue;
  634.             }
  635.             else if (m.col != c)
  636.             {
  637.                 //no item for first column so automatically sent down
  638.                 m = n;
  639.                 prevToLeast = prevToN;
  640.                 continue;
  641.             }
  642.  
  643.             if (f.lessThan(n.o, m.o))
  644.             {
  645.                 //n < m so put n in for least
  646.                 m = n;
  647.                 prevToLeast = prevToN;
  648.             }
  649.  
  650.             prevToN = n.rowHead;
  651.             n = n.nextRow;
  652.         }
  653.  
  654.         return prevToLeast;
  655.     }
  656.  
  657.     transient protected ResourceBundle errors;
  658.  
  659.     //--------------------------------------------------
  660.     // private members
  661.     //--------------------------------------------------
  662.  
  663.     Matrix        rowHead;
  664.     Matrix        nextRow;
  665.     Matrix        nextElt;
  666.     int            row;
  667.     int            col;
  668.     Object        o;
  669. }