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

public class Graph
{
    private ArrayList<Node> nodes;
    private ArrayList<Edge> edges;

    public Graph(){
        this.nodes = new ArrayList<Node> ();
        this.edges = new ArrayList<Edge>();
    }

    public void addNode(Node n) {
        this.nodes.add(n);
    }

    public void addNode(int nr){
        this.nodes.add(new Node(nr));
    }

    public void addNode(int nr, int x, int y){
        this.nodes.add(new Node(nr, x, y));
    } 

    public void addEdge(Edge e){
        this.edges.add(e);
        e.getAnfang().addEdge(e);
        e.getEnde().addEdge(e);
    }

    public ArrayList<Node> getNodes(){
        return this.nodes;
    }
    
    public ArrayList<Edge> getEdges(){
        return this.edges;
    }
    
    public void addEdge(int a, int e, int w, boolean g){
        Node an = null;
        Node en = null;
        for (int i = 0; i < this.nodes.size(); i++){
            if (this.nodes.get(i).getNumber() == a){
                an = this.nodes.get(i);
            }
            if (this.nodes.get(i).getNumber()== e){
                en = this.nodes.get(i);
            }
        }
        if (an == null || en == null){
            return;
        }
        this.addEdge(new Edge(an, en, w, g));
    }

    public Node getNode(int nr){
        for (Node n : this.nodes){
            if (n.getNumber() == nr){
                return n;
            }
        }
        return null;
    }
    
    public Node getNode(int x, int y){
        for(Node n: this.nodes){
            int dx = n.x - x; 
            int dy = n.y -y;      
            if (dx * dx + dy * dy <= 100) return n;
        }
        return null;
    }
    
    public ArrayList<Node> breitensuche(int start){
        ArrayList<Node> ergebnis = new ArrayList<Node>();
        LinkedList<Node> q = new LinkedList<Node>();
        q.add(this.getNode(start));

        while(!q.isEmpty()){
            Node aktuell = q.removeFirst();
            if (ergebnis.contains(aktuell)){
                continue;
            }

            ArrayList<Node> erreichbar = aktuell.getTargets();
            Collections.sort(erreichbar);
            q.addAll(erreichbar);

            ergebnis.add(aktuell);
        }

        return ergebnis;
    }
    
    public void tiefensucheGraphisch(){
        ArrayList<Node> ergebnis = new ArrayList<Node>();
        LinkedList<Node> q = new LinkedList<Node>();
        //q.add(this.getNode(start));

        while(!q.isEmpty()){
            Node aktuell = q.removeLast();
            if (ergebnis.contains(aktuell)){
                continue;
            }

            ArrayList<Node> erreichbar = aktuell.getTargets();
            Collections.sort(erreichbar, Collections.reverseOrder());
            q.addAll(erreichbar);

            ergebnis.add(aktuell);
        }
    }
    
    public ArrayList<Node> tiefensuche(int start){
        ArrayList<Node> ergebnis = new ArrayList<Node>();
        LinkedList<Node> q = new LinkedList<Node>();
        q.add(this.getNode(start));

        while(!q.isEmpty()){
            Node aktuell = q.removeLast();
            if (ergebnis.contains(aktuell)){
                continue;
            }

            ArrayList<Node> erreichbar = aktuell.getTargets();
            Collections.sort(erreichbar, Collections.reverseOrder());
            q.addAll(erreichbar);

            ergebnis.add(aktuell);
        }

        return ergebnis;
    }

    public ArrayList<Node> dijkstra (int start, int ziel){
        Node s = this.getNode(start);
        s.entfernung=0;
        ArrayList<Edge> edges = s.getEdges();
        for (Edge e : edges){
            Node n;

            if (e.getAnfang() == s ) n= e.getEnde();
            else n = e.getAnfang();
            int neu = s.entfernung +e.getWert();
            if (n.entfernung==-1 || neu < n.entfernung){
                n.entfernung = neu;
                n.vorgaenger = s;  
            }
        }

        s.bearbeitet = true;

        while(true){
            Node next = null; 
            for (Node n : this.nodes){
                if (!n.bearbeitet) continue;
                if (n.entfernung == -1) continue; 

                if (next == null || next.entfernung > n.entfernung){
                    next = n;
                }
            }
            if (next == null) break;
            edges = next.getEdges();
            for (Edge e : edges){
                Node n;

                if (e.getAnfang() == s ) n= e.getEnde();
                else n = e.getAnfang();
                int neu = s.entfernung +e.getWert();
                if (n.entfernung==-1 || neu < n.entfernung){
                    n.entfernung = neu;
                    n.vorgaenger = next;  
                }
            }
            next.bearbeitet = true;
        }
        Node z = this.getNode(ziel);
        ArrayList<Node> ergebnis = new ArrayList<Node> ();
        while (z != null){
            ergebnis.add(z);
            z=z.vorgaenger;
        }
        return ergebnis;

    }

    private boolean istBaum(int start){
        ArrayList<Node> ergebnis = new ArrayList<Node>();
        LinkedList<Node> q = new LinkedList<Node>();
        q.add(this.getNode(start));

        while(!q.isEmpty()){
            Node aktuell = q.removeFirst();
            if (ergebnis.contains(aktuell)){
                return false;
            }

            ArrayList<Node> erreichbar = aktuell.getTargets();
            Collections.sort(erreichbar);
            q.addAll(erreichbar);

            ergebnis.add(aktuell);
        }
        return true;
    }

    public Graph prim(){
        Graph sb = new Graph(); 
        for (Node n: this.nodes){
            sb.addNode(n.getNumber());
        }

        ArrayList<Edge> available = new ArrayList<Edge>();
        ArrayList<Node> done = new ArrayList<Node>();
        ArrayList<Edge> added = new ArrayList<Edge>();
        done.add(this.getNode(1));
        while(true){
            for (int i = 0; i < done.size(); i++){
                Node n = done.get(i);
                for (Edge e : n.getEdges()){
                    if (!done.contains(e.getEnde())||!added.contains(e))available.add(e);
                }
                Collections.sort(available);
            }
            if(available.isEmpty())break;
            Edge p = available.get(0);
            ArrayList<Node> erreichbar = sb.tiefensuche(1);
            sb.addEdge(p);
            added.add(p);
            done.add(p.getEnde());
        }
        return sb;
    }
    
    public void save (String filename){
        try{
            FileWriter f = new FileWriter(filename);
            for(Node n : this.nodes){
                f.write(n.toString() + "\n");
            }
            for(Edge e : this.edges){
                f.write(e.toString() + "\n");
            }
            f.close();
        }catch(IOException e){}
        
    }
    
    public int load (String filename){
        int max = 0;
        try{
            BufferedReader f = new BufferedReader(new FileReader(filename));
            String line = f.readLine();
            while(line != null){
                String[] data = line.split(" ");
                if(data[0].equals("N")) {
                    this.addNode(Integer.parseInt(data[1]),Integer.parseInt(data[2]),Integer.parseInt(data[3]));
                    if (Integer.parseInt(data[1]) > max) max = Integer.parseInt(data[1]);
                }
                if(data[0].equals("E")) {
                    this.addEdge(Integer.parseInt(data[1]),Integer.parseInt(data[2]),Integer.parseInt(data[3]),data[4].equals("1"));
                }
                line = f.readLine();
            }
            f.close();
        } catch(IOException e){}
        return max;
    }
}