package edu.cmu.cs.l3.graph;

import java.util.*;

public abstract class DirectedGraph extends Graph {

    public DirectedGraph() {

    }

    public void createEdge(Vertex u, Vertex v) {
        List ulist = (List) m_adjlists.get(u.getID());
        List vlist = (List) m_adjlists.get(v.getID());

        if (!ulist.contains(v)) {
            ulist.add(v);
            if (!u.getOutList().contains(v)) {
                u.getOutList().add(v);
            }
            if (!v.getInList().contains(u)) {
                v.getInList().add(u);
            }
        }
    }

    public void removeVertex(Vertex v) {
        List adjs;
        int i;

        adjs = getAdjacents(v);
        for (i = 0; i < adjs.size(); i++) {
            Vertex u = (Vertex) adjs.get(i);
            removeEdge(u,v);
            removeEdge(v,u);
        }

        v.deadMark();
    }

    public void removeEdge(Vertex u, Vertex v) {
        List ulist = (List)m_adjlists.get(u.getID());
        if (ulist.contains(v)) {
            ulist.remove(v);
            u.getOutList().remove(v);
            v.getInList().remove(u);
        }
    }

    public List getDFSTrace(Vertex v, boolean forward) throws GraphException {
        int i;
        for (i = 0; i < m_vertices.size(); i++) {
            Vertex u = (Vertex) m_vertices.get(i);
            u.auxUnmark();
        }
        return DFS(v, forward);
    }

    private List DFS(Vertex start, boolean forward) throws GraphException {
        List children, trace = new ArrayList();
        Stack callstack = new Stack();
        Vertex v;
        int i;

        callstack.push(start);
        while (!callstack.empty()) {
            v = (Vertex) callstack.pop();
            v.auxMark();
            trace.add(v);

            if (forward)
                children = getChildren(v);
            else
                children = getParents(v);

            for (i = 0; i < children.size(); i++) {
                Vertex u = (Vertex) children.get(i);
                if (!u.auxIsMarked())
                    callstack.push(u);
            }
        }
        return trace;
    }

    public int getDegree(Vertex v, int type) throws GraphException {
        switch (type) {
            case INDEGREE:
                return v.getInList().size();
            case OUTDEGREE:
                return v.getOutList().size();
            case DEGREE:
                return v.getInList().size() + v.getOutList().size();
        }

        throw new GraphException("Unknown degree type");
    }

    public boolean isAdjacent(Vertex v, Vertex u) {
        return (((List)m_adjlists.get(v.getID())).contains(u) ||
               ((List)m_adjlists.get(u.getID())).contains(v));
    }

    public List getParents(Vertex v) {
        return v.getInList();
    }

    public List getChildren(Vertex v) {
        return (List)m_adjlists.get(v.getID());
    }

    public List getAdjacents(Vertex v) {
        List adjs = new ArrayList();
        adjs.addAll(getChildren(v)); adjs.addAll(getParents(v));
        return adjs;
    }

}