// GraphAdjLists (graphADT) -- adjacency lists implementation

// Update  '07 - uses ArrayList not the depreciated Vector object
//             - no longer uses depreciated StringTokenizer
//             - java 1.6 Type casting
//             - removeVertex remade with for each loop
//             - note, line 156 - is cloning necessary? Xlint unchecked cast

// recent change: -toStringAdjLists now prints the elements as they are stored; i.e. out of order
//                this avoids the n^2 running time it used to have
//                -asserts added

package graphADT;

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

/*
 * Current implementation uses adjacency lists form of a graph.
 */

public class GraphAdjLists implements Graph
{
    //  Internal Representation and Constructors
    //
    protected ArrayList<ArrayList<Integer>> adj;

    public GraphAdjLists()
    {
        adj = new ArrayList<ArrayList<Integer>>();
    }

    public GraphAdjLists(Graph G)
    {
        int n = G.order();
        adj = new ArrayList<ArrayList<Integer>>();
        for (int i = 0; i < n; i++)
        {
            adj.add(G.neighbors(i));
        }
    }

/* -- same as Graph constructor
    public GraphAdjLists(GraphAdjLists G)
    {
        int n = G.order();
        adj = new ArrayList<ArrayList<Integer>>();
        for (int i = 0; i < n; i++)
        {
            adj.add(G.neighbors(i));
        }
    }
*/

    public GraphAdjLists(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");
            }

            adj = new ArrayList<ArrayList<Integer>>();
            int n = Integer.parseInt(tokens[0]);

            for (int u = 0; u < n; u++)
            {
                ArrayList<Integer> current = new ArrayList<Integer>();
                line = buffer.readLine().trim();
                int limit = 0;
                if (!line.equals(""))
                {
                    tokens = line.split("\\s+");
                    limit = tokens.length;
                }

                for (int i = 0; i < limit; i++)
                {
                    current.add(Integer.parseInt(tokens[i]));
                }
                adj.add(current);
            }
        }
        catch (IOException x)
        {
            throw new Error("bad input stream");
        }
    }


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

    public void removeVertex(int i)
    {
        assert(0 <= i && i < order());
        adj.remove(i);
        Integer I = new Integer(i);
        for (int u = 0; u < order(); u++)
        {
            ArrayList<Integer> current = adj.get(u);
            current.remove(I); // remove i from adj lists
            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)) return;
        (adj.get(i)).add(j);
    }

    public void removeArc(int i, int j)
    {
        assert(0 <= i && i < order());
        assert(0 <= j && j < order());
        if (!isArc(i,j)) return;
        (adj.get(i)).remove(new Integer(j));
    }

    public void addEdge(int i, int j)
    {
        assert(0 <= i && i < order());
        assert(0 <= j && j < order());
        if (!isArc(i,j)) (adj.get(i)).add(j);
        if (!isArc(j,i)) (adj.get(j)).add(i);
    }

    public void removeEdge(int i, int j)
    {
        assert(0 <= i && i < order());
        assert(0 <= j && j < order());
        if (isArc(i,j)) (adj.get(i)).remove(new Integer(j));
        if (isArc(j,i)) (adj.get(j)).remove(new Integer(i));
    }


    //  Access Methods
    //
    public boolean isArc(int i, int j)
    {
        assert(0 <= i && i < order());
        assert(0 <= j && j < order());
        return (adj.get(i)).contains(new Integer(j));
    }

    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)
    {
        assert(0 <= i && i < order());
        int sz = 0;
        for (int j = 0; j < order(); j++)
        {
            if (isArc(j,i))  sz++; 
        }
        return sz;
    }

    public int degree(int i)
    {
        assert(0 <= i && i < order());
        return (adj.get(i)).size();
    }

    public ArrayList<Integer> neighbors(int i)
    {
        assert(0 <= i && i < order());
        ArrayList<Integer> nei = new ArrayList<Integer>();
        for (Integer vert : adj.get(i))
        {
            nei.add(vert);
        }
        return nei;
        //return (ArrayList<Integer>)(adj.get(i)).clone(); <-- -Xlint doesn't like this. [Unchecked cast]
    }

    public int order()
    {
        return adj.size();
    }

    public int size() 		// Number of arcs (counts edges twice).
    {
        int sz = 0;
        for (int i=0; i<order(); i++)
        {
            sz += (adj.get(i)).size();
        }
        return sz;
    }

    // default output readable by constructor
    //
    public String toString()
    {
        return toStringAdjLists();
    }
    public String toStringAdjLists()
    {
        StringBuffer o = new StringBuffer();
        o.append(order()+"\n");

        for (int i = 0; i < order(); i++)
        {
            ArrayList<Integer> nei = neighbors(i);
            for (int j : nei)
            {
                o.append(j + " ");
            }
            o.append("\n");
        }
        return o.toString();
    }
}