// Lab34st.java
// This is the student version of the Lab34 assignment.  This program implements a "sparse matrix" class using a linked list of linked lists.

import java.io.*;
import java.util.LinkedList;


public class Chp34Sparse
{
    public static void main (String args[]) throws IOException
    {
        System.out.println("\nLAB34 100 POINT VERSION\n");
        Sparse sparse = new Sparse();
        sparse.enterSparse();
        sparse.displaySparse();
        System.out.println("\n\n");
    }
}



class Sparse
{
    private ColNode[] arr;      // points to the header node of the first linked list
    private boolean first;      // determines if first node is created or not

    public Sparse()
    {
        arr=new ColNode[1000];
        first = true;
    }

    public void enterSparse() throws IOException
    {
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        System.out.println("\nEnter [ -999 <cr> ] after last data entry to exit\n");
        boolean done = false;
        do
        {
            System.out.println();
            System.out.print("Enter row number   ===>>  ");
            int row = Integer.parseInt(input.readLine());
            done = row == -999;
            if (!done)
            {
                System.out.print("Enter col number   ===>>  ");
                int col = Integer.parseInt(input.readLine());
                System.out.print("Enter sparse value ===>>  ");
                int val = Integer.parseInt(input.readLine());
                if (first)
                {
                    firstNode(val,row,col);
                    first = false;
                }
                else
                {
                    insertNode(val,row,col);
                }
            }
        }
        while (!done);

    }

    public void firstNode(int value, int row, int col)
    {
        ColNode temp = new ColNode(value,col,null);
        arr[row] = temp;
    }

    public void insertNode(int value, int row, int col)
    {
        if(arr[row]==null){
            firstNode(value,row,col);


        }
        else if(arr[row].getColNumber()>col)
        {
            ColNode g=new ColNode(value,col,arr[row].getNextCol());

            g.setNextCol(arr[row]);
            arr[row]=g;
        }
        else {
            ColNode p= arr[row];
            boolean TF=false;
            while(p!=null && !TF)
            {

                if (p.getColNumber() < col){
                    if(p.getNextCol()==null){
                        p.setNextCol(new ColNode(value,col,null));
                        TF=true;
                    }
                    else
                    p=p.getNextCol();

                }
                else{
                    ColNode temp=new ColNode(value,col,p.getNextCol());
                    p.setNextCol(temp);
                    p=p.getNextCol();
                    TF=true;
                }

            }


        }

    }

    public void displaySparse()
    {
        System.out.println();
        int r=0;
        ColNode c = null;
        while (r != 1000)
        {
            c = arr[r];
            while (c != null)
            {
                int row = r;
                int col = c.getColNumber();
                int val = c.getValue();
                System.out.println("[" + row + "," + col + "]   \t=  " + val);
                c = c.getNextCol();
            }
            r++;
        }
    }

}




class ColNode
{
    public ColNode (int initValue, int initColNumber, ColNode initNextCol)
    {
        value = initValue;
        colNumber = initColNumber;
        nextCol = initNextCol;
    }

    public int getValue ()                          { return value;             }
    public int getColNumber ()                      { return colNumber;         }
    public ColNode getNextCol ()                    { return nextCol;           }
    public void setValue (int theNewValue)          { value = theNewValue;      }
    public void setNextCol (ColNode theNewNextCol)  { nextCol = theNewNextCol;  }

    private int colNumber;
    private ColNode nextCol;
    private int value;
}