--  Authors:     Robert Walsh and Mark Trisko
--  Class:       CSCI 375
--  Assignment:  Assignment #1
--  Due Date:    September 19, 1995
--  Title:       Sparse Matrix Implementation using a single linked list.

with TEXT_IO; use TEXT_IO;

package sparse is
   
    type S_MAT is limited private;

    Matrix_Bounds : EXCEPTION;

    procedure CREATE ( Matrix : out S_MAT;
		       RowMax : in INTEGER;
                       ColMax : in INTEGER );

    --  Pretest:  This procedure receives the INTEGERs RowMax and ColMax that
    --            represent the extrema of the matrix.

    --  Postest:  This procedure will return the beginning of the MATRIX.

    --  Discription:  This procedure will initialize the MaxRow and MaxCol
    --                to RowMax and ColMax, the count to 0, and the pointer to
    --                null. 

    procedure ASSIGN ( Matrix : in out S_MAT;
                       Row    : in INTEGER;
                       Column : in INTEGER;
                       Value  : in INTEGER );

    --  Pretest:  The procedure will receive the Row and Column coordinates of
    --            the Matrix where the Matrix Value is to be placed.

    --  Postest:  The procedure will return the updated Matrix.

    --  Discription:  The procedure will insert a new node at its ordered place
    --                as determined by the numerical order of the rows and 
    --                columns.

    function RETRIEVE ( Matrix  : in S_MAT;
                        Row     : in INTEGER;
                        Column  : in INTEGER) return INTEGER;

    --  Pretest:  The procedure will receive the Matrix and the coordinates of
    --            the element it is to find.

    --  Postest:  The function will return the Value located at the passed in
    --            coordinates.

    --  Discription:  The function will scan the list until it finds the
    --                correct node.  It will return the value located in that
    --                node.

    procedure OUT_MAT ( Matrix : in S_MAT );

    --  Pretest:  The procedure will receive the Matrix.
  
    --  Postest:  None.

    --  Discription:  This procedure will print out the sparse matrix.

    procedure DELETE ( Matrix : in out S_MAT);

    --  Pretest:  The procedure will receive the Sparce_MATrix Matrix.

    --  Postest:  The procedure will return an updated version of that Matrix.

    --  Discription:  The procedure will assign the Matrix pointer a null
    --                value.

    function MATCOUNT ( Matrix : in S_MAT ) return INTEGER;

    --  Pretest:  This function will receive the Matrix.

    --  Postest:  This function will return the INTEGER Count value.

    --  Discription:  The function will return the Count field in the
    --                MATRIX_HEAD node.

    procedure CLEAR (Matrix : in out S_MAT);

    private

       type MATRIX_NODE;
       type S_NODE is access MATRIX_NODE;
       type MATRIX_NODE is
          record
            Row    : INTEGER;
            Column : INTEGER;
            Value  : INTEGER;
            Next   : S_NODE;
          end record;

       type MATRIX_HEAD is
          record
            MaxRow: INTEGER;
            MaxCol: INTEGER;
            Count : INTEGER;
            Next  : S_NODE;
          end record;

       type S_MAT is access MATRIX_HEAD;

end sparse;


package body sparse is

--============================================================================= 
     
      procedure CREATE ( Matrix : out S_MAT;
                         RowMax : in INTEGER;
                         ColMax : in INTEGER ) is

      begin

        Matrix := new MATRIX_HEAD'(RowMax, ColMax, 0, null);

      end CREATE;

--=============================================================================
	procedure CLEAR(Matrix : in out S_MAT) is
	begin
	  Matrix.Count := 0;
	  Matrix.Next := null;
	end CLEAR;
--=============================================================================

      procedure ASSIGN ( Matrix   : in out S_MAT;
                         Row      : in INTEGER;
                         Column   : in INTEGER;
                         Value    : in INTEGER ) is

      P : S_NODE := Matrix.Next;

      begin

        if ( (Row < 1) or (Row > Matrix.MaxRow) ) or
           ( (Column < 1) or (Column > Matrix.MaxCol) )  then         
           raise Matrix_Bounds;  
        end if;

        if Matrix.Next = null then                                --  No elements
           Matrix.Next := new MATRIX_NODE'(Row, Column, Value, Matrix.Next);
           Matrix.Count := Matrix.Count + 1;

        elsif (Row = Matrix.Next.Row) and (Column = Matrix.Next.Column) then
           
           if Value/=0 then
             Matrix.Next.Value := Value;
           else
             Matrix.Next := Matrix.Next.Next;
             Matrix.Count:= Matrix.Count - 1;
           end if;

        elsif (Row < Matrix.Next.Row) or                        --  New 1st element
              (Row = Matrix.Next.Row and Column < Matrix.Next.Column) then
           Matrix.Next := new MATRIX_NODE'(Row, Column, Value, Matrix.Next);
           Matrix.Count := Matrix.Count + 1;

        else                                                 --  Orders subsequent row values
           while (P.Next /= null) and then (P.Next.Row < Row) loop
              P := P.Next;
           end loop;
                                                             --  If there are duplicate rows, 
                                                             --  it will order the column values.
           while (P.Next /= null) and then
                 ( (P.Next.Row = Row) and (P.Next.Column < Column) ) loop
              P := P.Next;
           end loop;

           if ( P.Next /= null ) and then 
              ( ( P.Next.Row = Row ) and ( P.Next.Column = Column ) ) then

             if Value /= 0 then
                P.Next.Value := Value;
             else
                P.Next := P.Next.Next;
                Matrix.Count := Matrix.Count - 1;
             end if;
 
           else

             P.Next := new MATRIX_NODE'(Row, Column, Value, P.Next);
             Matrix.Count := Matrix.Count + 1;

           end if;

        end if;
   
        end Assign;

--==============================================================================

        function RETRIEVE ( Matrix  : in S_MAT;
                            Row     : in INTEGER;
                            Column  : in INTEGER) return INTEGER is

        P : S_NODE := Matrix.Next;

        begin

          if ( (Row < 1) or (Row > Matrix.MaxRow) ) or
             ( (Column < 1) or (Column > Matrix.MaxCol) ) then
            raise Matrix_Bounds;
          end if;

          while ( P /= null ) and then
                ( (P.Row /= Row) or (P.Column /= Column) ) loop
             P := P.Next;
          end loop;

          if ( P /= null ) then 
            return P.Value;
          else
            return 0;
          end if;

        end RETRIEVE;

--==============================================================================

        procedure OUT_MAT ( Matrix : in S_MAT ) is

        P : S_Node := Matrix.Next;
        RowCount : INTEGER := 1;
        ColCount : INTEGER := 1;

        begin

          NEW_LINE;
          PUT_LINE("                         The MATRIX");
          PUT_LINE("-----------------------------------------------------------");

          while ( ( P /= null ) and ( RowCount <= Matrix.MaxRow ) ) loop
                                                    --  Prints as long as there 
                                                    --  elements remaining in
                                                    --  the Matrix.
              if RowCount /= P.Row then
               PUT(" O ");                        --  If Row isn't present.
              elsif ColCount /= P.Column then
               PUT(" O ");                        --  if Column of certain
              elsif ColCount = P.Column then        --  row is not present.
               PUT(" X ");
               P := P.Next;                         --  if Column of row is
              end if;                               --  present.

              if ColCount = Matrix.MaxCol then      --  Upon reaching end of
                RowCount := RowCount + 1;           --  row, advance to new row
                ColCount := 0;
                NEW_LINE;
              end if;

              ColCount := ColCount + 1;

           end loop;

           if ( P = null ) then                     --  If Sparce_Matrix did
                                                    --  not contain last rows,
              for i in RowCount..Matrix.MaxRow loop --  loop will print off
                                                    --  many O's.
                 for j in ColCount..Matrix.MaxCol loop
                     PUT(" O ");
                 end loop;

                 NEW_LINE;

                 ColCount :=1;

              end loop;

           end if;

           end OUT_MAT;

--==============================================================================

           procedure DELETE ( Matrix : in out S_MAT ) is

           begin

              Matrix := null;

           end DELETE;

--==============================================================================

           function MATCOUNT ( Matrix : in S_MAT ) return INTEGER is

           begin

             return Matrix.Count;

           end MATCOUNT;
end sparse;