/*The weighted graph in matrix representation
 *-check interface for notes.
*/

package graphADT;

import java.util.ArrayList;
import java.io.*;

public class wGraphMatrix implements wGraph
{
    protected int order;
    protected Weight[][] adjW;  // null entry means no arc

    public wGraphMatrix()
    {
       order = 0;
    }

    public wGraphMatrix(wGraphMatrix G)
    {
        int n = order = G.order();
        if ( n > 0 )
        {
            adjW = new Weight[n][n];
        }

        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                adjW[i][j] = G.adjW[i][j];
            }
        }
    }

    public wGraphMatrix(wGraph G) //convert implementation
    {
        int n = order = G.order();
        adjW = new Weight[n][n];

        for (int i = 0; i < n; i++)
        {
            ArrayList<Integer> nbrs = G.neighbors(i);
            ArrayList<Weight> wNbrs = G.neighborWeights(i);
            for (int j = 0; j < nbrs.size(); j++)
            {
                int index = nbrs.get(j);
                adjW[i][index] = wNbrs.get(j);
            }
        }
    }

    public wGraphMatrix(Graph G) // promote and/or copy
    {
        int n = order = G.order();
        if ( n > 0 )
        {
            adjW = new Weight[n][n];
        }

        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (G.isArc(i, j))
                {
                    adjW[i][j] = new Weight<Integer>(1);
                }
            }
        }
    }

    public wGraphMatrix(BufferedReader buffer) 
    {
        try
        {
            String line = buffer.readLine().trim();
            String[] tokens = line.split("\\s+");

            if (tokens.length != 1)
            {
                throw new Error("bad format: number of vertices");
            }
            int n = order = Integer.parseInt(tokens[0]);

            if ( n > 0 )
            {
                adjW = new Weight[n][n];
            }

            for (int i = 0; i < n; i++)
            {
                line = buffer.readLine().trim();
                tokens = line.split("\\s+");
                if (tokens.length != n)
                {
                    throw new Error("bad format: adjacency matrix");
                }

                for (int j = 0; j < n; j++)
                {
                    int entry = Integer.parseInt(tokens[j]); // Integer type!
                    if (entry != 0)
                    {
                      adjW[i][j] = new Weight<Integer>(entry);
                    }
                }
            }
        }
        catch (IOException x)
        {
            throw new Error("bad input stream");
        }

    }

    // mutator methods

    public void addVertices(int n)
    {
        assert(0 <= n );
        Weight weights[][] = new Weight[order+n][order+n];

        for (int i = 0; i < order; i++)
        {
            for (int j = 0; j < order; j++)
            {
	            weights[i][j] = adjW[i][j];
            }
        }
        order += n;
        adjW = weights;
    }

    public void removeVertex(int v)
    {
        assert(0 <= v && v < order);
        order--;

        for (int i = 0; i < v; i++)
        {
            for (int j = v; j < order; j++)
            {
                adjW[i][j] = adjW[i][j+1];
            }
        }

        for (int i = v; i < order; i++)
        {
            for (int j = 0; j < v; j++)
            {
                adjW[i][j] = adjW[i+1][j];
            }
            for (int j = v; j < order; j++)
            {
                adjW[i][j] = adjW[i+1][j+1];
            }
        }
    }

    public void addArc(int i, int j)
    {
        assert(0 <= i && i < order());
        assert(0 <= j && j < order());
        adjW[i][j] = new Weight<Integer>(1); //default weight
    }

    public void removeArc(int i, int j)
    {
        assert(0 <= i && i < order());
        assert(0 <= j && j < order());
        adjW[i][j] = null;
    }

    public void addEdge(int i, int j)
    {
        addArc(i,j); addArc(j,i);
    }

    public void removeEdge(int i, int j)
    {
        removeArc(i,j); removeArc(j,i);
    }

    public void addArc(int i, int j, Weight weight)
    {
        assert(0 <= i && i < order());
        assert(0 <= j && j < order());
        adjW[i][j] = weight;
    }

    public void setArcWeight(int i, int j, Weight weight)
    {
        assert(isArc(i, j));
        adjW[i][j] = weight;
    }

    public Weight<?> getArcWeight(int i, int j)
    {
        assert(isArc(i, j));
        return adjW[i][j];
    }

    // accessor methods

    public boolean isArc(int i, int j)
    {
        assert(0 <= i && i < order);
        assert(0 <= j && j < order);
        return adjW[i][j] != null;
    }

    public boolean isEdge(int i, int j)
    {
        assert(0 <= i && i < order);
        assert(0 <= j && j < order);
        return isArc(i,j) && isArc(j,i);
    }

    public int inDegree(int i) // column count
    {
        assert(0 <= i && i < order);
        int sz = 0;
        for (int j = 0; j < order; j++)
        {
            if (adjW[j][i] != null) sz++;
        }
        return sz;
    }

    public int degree(int i) // row count
    {
        assert(0 <= i && i < order);
        int sz = 0;
        for (int j = 0; j < order; j++)
        {
            if (adjW[i][j] != null) sz++;
        }
        return sz;
    }

    public int order()
    {
        return order;
    }

    public int size()                           // Number of arcs (edges count twice)
    {
        int sz = 0;
        for (int i = 0; i< order; i++)
        {
            for (int j = 0; j< order; j++)
            {
                if (adjW[i][j] != null) sz++;
            }
        }
        return sz;  // undirected ? sz / 2 : sz;
    }

    public ArrayList<Integer> neighbors(int i)
    {
        assert(0 <= i && i < order);
        ArrayList<Integer> nbrs = new ArrayList<Integer>();

        for (int j = 0; j < order; j++)
        {
            if (adjW[i][j] != null) nbrs.add(j); 
        }
        return nbrs;
    }

    public ArrayList<Weight> neighborWeights(int i)
    {
        ArrayList<Weight> nbrsWei = new ArrayList<Weight>();

        for (int j = 0; j < order(); j++)
        {
            if (adjW[i][j] != null)
            {
               nbrsWei.add(adjW[i][j]); // corresponding weight
            }
        }
        return nbrsWei;
    }

    public String toString()  // print weights in n-by-n matrix 
    {
        StringBuffer o = new StringBuffer();
        o.append(order()+"\n");

        for (int i = 0; i < order(); i++)
        {
            for (int j = 0; j < order(); j++)
            {
                if (adjW[i][j] != null)
                {
                    o.append(adjW[i][j] + " ");
                }
                else
                {
                    o.append(0 + " ");
                }
            }
            o.append("\n");
        }
        return o.toString();
    }
 
}