/*The weighted graph in lists form
 *-check interface for notes.
*/

package graphADT;

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

public class wGraphLists extends GraphAdjLists implements wGraph
{
    protected ArrayList<ArrayList<Weight>> adjWei;

    public wGraphLists()
    {
        super();
        adjWei = new ArrayList<ArrayList<Weight>>();

    }

    public wGraphLists(wGraphLists G) 	//copy
    {
        adj = new ArrayList<ArrayList<Integer>>();
        adjWei = new ArrayList<ArrayList<Weight>>();

        for (int i=0; i<G.order(); i++)
        {
            ArrayList<Integer> nbrs = G.neighbors(i);
            ArrayList<Weight> wNbrs = G.neighborWeights(i);
            adj.add(nbrs);
            adjWei.add(wNbrs);
        }
    }

    public wGraphLists(wGraph G) 	//convert
    {
        adj = new ArrayList<ArrayList<Integer>>();
        adjWei = new ArrayList<ArrayList<Weight>>();

        for (int i=0; i<G.order(); i++)
        {
            ArrayList<Integer> nbrs = G.neighbors(i);
            ArrayList<Weight> wNbrs = G.neighborWeights(i);
            adj.add(nbrs);
            adjWei.add(wNbrs);
        }
    }

    public wGraphLists(Graph G) //main constructor.
    {
        adj = new ArrayList<ArrayList<Integer>>();
        adjWei = new ArrayList<ArrayList<Weight>>();

        // create a weighted graph by giving all edges the default weight
        //
        for (int i=0; i<G.order(); i++)
        {
            ArrayList<Integer> nbrs = G.neighbors(i);
            ArrayList<Weight> wNbrs = new ArrayList<Weight>();
            for (int j = 0; j < nbrs.size(); j++)
            {
                wNbrs.add(new Weight<Integer>(1));
            }
            adj.add(nbrs);
            adjWei.add(wNbrs);
        }
    }

    public wGraphLists(BufferedReader buffer)
    {
        //input is given in the form
        //n
        //[line 0] nei_0 wei_0 nei_1 wei_1...nei_x-1 wei_x-1
        //[line 1] nei_0 wei_0 nei_1 wei_1...nei_y-1 wei_y-1
        //...
        //[line n-1] nei_0 wei_0 nei_1 wei_1...nei_z-1 wei_z-1

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

            if (tokens.length != 1)
            {
                throw new Error("bad format: number of vertices");
            }

            adj = new ArrayList<ArrayList<Integer>>();
            adjWei = new ArrayList<ArrayList<Weight>>();

            int n = Integer.parseInt(tokens[0]);

            for (int u = 0; u < n; u++)
            {
                ArrayList<Integer> current = new ArrayList<Integer>();
                ArrayList<Weight> currentWei = new ArrayList<Weight>();
                line = buffer.readLine().trim();
                boolean skip = false;
                if (!line.equals(""))
                    tokens = line.split("\\s+");
                else
                    skip = true;

                boolean switcher = true; //alternates - since its nei_1 wei_1...

                if (!skip)
                {
                    for (String s : tokens)
                    {
                        if (switcher)
                        {
                            current.add(Integer.parseInt(s));
                            switcher = false;
                        }
                        else
                        {
                            currentWei.add(new Weight<Integer>(Integer.parseInt(s)));
                            switcher = true;
                        }
                    }
                }
                adj.add(current);
                adjWei.add(currentWei);
            }
        }
        catch (IOException x)
        {
            throw new Error("bad input stream");
        }

    }

    public void addVertices(int n)
    {
        assert(0 <= n);
        if ( n > 0 )
        {
            for (int i = 0; i < n; i++)
            {
                adj.add(new ArrayList<Integer>());
                adjWei.add(new ArrayList<Weight>());
            }
        }
    }

    public void removeVertex(int i)
    {
        assert(0 <= i && i < order());
        adj.remove(i);
        adjWei.remove(i);
        Integer I = new Integer(i);
        for (int u = 0; u < order(); u++)
        {
            ArrayList<Integer> current = adj.get(u);
            ArrayList<Weight> curWei = adjWei.get(u);

            int place = current.indexOf(I);
            if (place >= 0)
            {
                current.remove(place);
                curWei.remove(place);
            }

            for (Integer num: current)
            {
                if (num > i)  // relabel larger indexed nodes
                {
                    int index = current.indexOf(num);
                    current.set(index, num-1);
                }
            }
        }
    }


    public void addArc(int i, int j)
    {
        assert(0 <= i && i < order());
        assert(0 <= j && j < order());
        if (!isArc(i,j))
        {
            (adj.get(i)).add(j);
            (adjWei.get(i)).add(new Weight<Integer>(1)); //default weight
        }
    }
    public void addEdge(int i, int j)
    {
        addArc(i,j); addArc(j,i);
    }

    public void removeArc(int i, int j)
    {
        assert(0 <= i && i < order());
        assert(0 <= j && j < order());
        if (isArc(i,j))
        {
            int place = adj.get(i).indexOf(new Integer(j));
            adj.get(i).remove(place);		//the integer j
            adjWei.get(i).remove(place);
        }
    }
    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());
        if (!isArc(i,j)) 			//don't add the same edge twice
        {
            (adj.get(i)).add(j);
            (adjWei.get(i)).add(weight);
        }
        else if (isArc(i,j))		//if it exists just change the weight
        {
            int place = (adj.get(i)).indexOf(new Integer(j));
            adjWei.get(i).set(place, weight); //replace the weight
        }
    }

    public void setArcWeight(int i, int j, Weight weight)
    {
        assert(isArc(i, j));
        int place = (adj.get(i)).indexOf(new Integer(j));
        adjWei.get(i).set(place, weight);
    }

    public Weight getArcWeight(int i, int j)
    {
        assert(isArc(i, j));  // mjd isEdge -> isArc  12-Oct-2009
        int place = (adj.get(i)).indexOf(new Integer(j));
        return adjWei.get(i).get(place);
    }

    public ArrayList<Weight> neighborWeights(int i)
    {
        assert(0 <= i && i < order());
        ArrayList<Weight> neiWei = new ArrayList<Weight>();
        for (Weight wei : adjWei.get(i))
        {
            neiWei.add(wei);
        }
        return neiWei;
    }

    public String toString() // include weights after each neighbor
    {
        StringBuffer o = new StringBuffer();
        o.append(order()+"\n");

        for (int i = 0; i < order(); i++)
        {
            ArrayList<Integer> nei = adj.get(i);
            ArrayList<Weight> neiW = adjWei.get(i);

            for (int j = 0; j < nei.size(); j++)
            {
                o.append(nei.get(j) + " ");
                o.append(neiW.get(j) + " ");
            }
            o.append("\n");
        }
        return o.toString();
    }

}