#include <iostream>
#include <fstream>
#include <map>
#include <set>
#include <string>
#include <queue>
#include <list>
#include <cmath>


using namespace std;
class vertex;

class edge{
public:
    vertex* from, *to;
    float dist;

    edge(vertex *f, vertex *t, float d) : from(f), to(t), dist(d) {};

    vertex* getOposite(vertex* v){
        if(from == v) return to;
        if(to == v) return from;
        return 0;
    }
};

bool sortfunction (edge* p1,edge* p2) {
    return  p1->dist < p2->dist;
}

class vertex{
public:
    vector<edge*> edges;
    string name;
    float x;
    float y;

    vertex(string n, float xova, float yova): name(n), x(xova), y(yova){};

    void sortEdges(){
        sort( edges.begin(), edges.end(), sortfunction);
    }
};

class Graf{
public:
    set<vertex*> allVerteces;
    map<string, vertex*> string_to_Verteces;
    set<vertex*> visitedVertex;
    vector<vertex*> path;
    vector<edge*> allEdges;

    Graf(){};
    Graf(ifstream &file){
        string name;
        float x;
        float y;
        int pom;

        while(!file.eof()){
            file >> name >> pom >> pom >> x >> y;
            addVertex(name, x, y);
        }
        addAllEdges();
    }

    void addVertex(string name, float x, float y){
        if( string_to_Verteces.find(name) == string_to_Verteces.end() )
        {
            vertex *nova = new vertex(name, x, y);
            string_to_Verteces[name] = nova;
            allVerteces.insert(nova);
        }
    }


    void addAllEdges(){
        set<vertex*>::iterator pit;
        set<vertex*>::iterator dit;
        for(pit = allVerteces.begin(); pit!= allVerteces.end(); ++pit){
            for(dit = allVerteces.begin(); dit!= allVerteces.end(); ++dit){
                if(*pit != *dit){
                    vertex* pfrom = *pit;
                    vertex* pto = *dit;

                    float xova,yova;

                    xova = pfrom->x - pto->x;
                    yova = pfrom->y - pto->y;
                    float dlzka = sqrt( xova*xova + yova*yova );

                    edge* hrana = new edge(pfrom,pto,dlzka);
                    pfrom->edges.push_back(hrana);

                    allEdges.push_back(hrana);
                }
            }
        }
        sortAllEdges();
    }

    void sortAllEdges(){
        set<vertex*>::iterator pit;
        for(pit = allVerteces.begin(); pit!= allVerteces.end(); ++pit){
            (*pit)->sortEdges();
        }
    }

    void najblizsie(int pocet){
        set<vertex*>::iterator pit;
        vector<edge*>::iterator eit;

        for(pit = allVerteces.begin(); pit!= allVerteces.end(); ++pit){
            int cyklus = 0;

            cout << (*pit)->name << " >> \t|";

            for(eit = (*pit)->edges.begin(); eit != (*pit)->edges.end(); ++eit){
                if(pocet> cyklus){
                    cout << (*eit)->to->name << " dist \t" << (*eit)->dist << " \t| ";
                    cyklus++;
                }
            }


            cout << endl;
        }
    }


    void doDFS(vertex* temp, list<vertex*> *vrcholy){
        vector<edge*>::iterator it;
        //cout << temp->name << " ";
        vertex *help = temp;
        visitedVertex.insert(temp);
        list<vertex*>::iterator findIter = find((*vrcholy).begin(), (*vrcholy).end(), temp);

        for(it=help->edges.begin(); it != help->edges.end(); it++){
            vertex* hr = (*it)->getOposite(help);
            if(visitedVertex.find(hr) == visitedVertex.end()){
                doDFS(hr, vrcholy);
            }
        }
        vrcholy->erase(findIter);
    }

    int suvislost(){
        list<vertex *> vrcholy;
        set<vertex *>::iterator vit;
        int pocet = 0;
        visitedVertex.clear();

        for(vit= allVerteces.begin(); vit!=allVerteces.end(); ++vit){
            vrcholy.push_back(*vit);
        }

        while(!vrcholy.empty()){
            doDFS(vrcholy.front(), &vrcholy);
            pocet++;
        }
        return pocet;
    }

    void addEdgeToVertex(vertex * from, vertex *to, float dist){
        set<vertex*>::iterator it;
        edge *novy = new edge(from, to, dist);
        for(it = allVerteces.begin(); it!= allVerteces.end(); ++it){
            if(((*it)->name == from->name) || ((*it)->name == to->name) ){
                (*it)->edges.push_back(novy);
            }
        }
    }


    void Kruskal(Graf &G1){
        set<vertex*> vsetkyDocVrcholy;
        vector<edge*> vsetckyDocHrany;
        set<vertex*>::iterator it;
        vector<edge*>::iterator edgit;

        copy(
            G1.allVerteces.begin(), G1.allVerteces.end(),
            std::inserter( allVerteces, allVerteces.begin() ) );
        copy(
            G1.allEdges.begin(), G1.allEdges.end(),
            std::inserter( vsetckyDocHrany, vsetckyDocHrany.begin() ) );
        copy(
            G1.string_to_Verteces.begin(), G1.string_to_Verteces.end(),
            std::inserter( string_to_Verteces, string_to_Verteces.begin() ) );

        for(it=allVerteces.begin(); it != allVerteces.end(); ++it){
            (*it)->edges.clear();
        }

        for(edgit = vsetckyDocHrany.begin(); edgit != vsetckyDocHrany.end(); ++edgit){
            if(suvislost()==1)
                break;
            else{
                allEdges.push_back(*edgit);
                addEdgeToVertex( (*edgit)->from, (*edgit)->to, (*edgit)->dist);
            }
        }
    }

    void dosirky(string name){
        if( string_to_Verteces.find(name) != string_to_Verteces.end() )
            Breadth_first_search(string_to_Verteces[name]);
    }


    void Breadth_first_search(vertex* temp){
        queue<vertex *> fronta;
        vertex* vrchol = temp;
        vector<edge*>::iterator it;
        int prechod = 0;

        visitedVertex.clear();

        fronta.push(vrchol);
        while(!fronta.empty()){

            vrchol = fronta.front();


            if(visitedVertex.find(vrchol) == visitedVertex.end()){
                if(prechod>8){
                    cout << endl;
                    prechod = 0;
                }
                prechod++;
                cout << vrchol->name << "  ";
                visitedVertex.insert(vrchol);
            }

            fronta.pop();


            for(it=vrchol->edges.begin(); it != vrchol->edges.end(); it++){
                vertex* hr = (*it)->getOposite(vrchol);
                if(visitedVertex.find(hr) == visitedVertex.end()){
                    fronta.push(hr);
                }
            }

        }

    }


    void sortVsetky(){
        sort( allEdges.begin(), allEdges.end(), sortfunction);
    }
};




int main(){
    ifstream stanice("suradnice.txt");
    cout << "Vypis najlbizsich susedov : " << endl;
    Graf G1(stanice),G2;
    G1.najblizsie(3);
    G2.Kruskal(G1);
    cout <<endl<<endl<< "Vypis do sirky po kruskalovi : " << endl;
    G2.dosirky("ACTON");
    /*Vertex* stred = G2.stred();
    G2.dosirky(stred.name);*/
    getchar();
    return 1;
}