#include <gp-bnb/greedy_packing.hpp>
#include <iostream>


greedy_packing::greedy_packing(const graph& g, std::vector<node_id> a, std::vector<node_id> b)
    : graph_(g), a(a), b(b) {
};

//breadth-first-search to determine neighbors of B
void greedy_packing::bfs(){

    x.resize(graph_.num_nodes() - (a.size() + b.size()));
    std::vector<bool> visited(graph_.num_nodes() +1, false);
    
    for(node_id node : b){
        q.push(node);
        visited[node] = true;
    }
    for(node_id node: a){
        visited[node] = true;
    }
    unsigned int last_node = b.size();
    unsigned int count = 0;

    while(!q.empty()){
        node_id node = q.front();
        q.pop();

        std::vector<node_id> neighbors = graph_.get_adjacency(node);

        for(node_id v : neighbors){
            if(v == last_node)
                end_of_neighbors = count;
            
            if(visited[v] == false){
                q.push(v);
                x[count++] = v;
            }
            visited[v] = true;
        }
    }

    return;

};


void greedy_packing::run(){

    //x konstruieren: enthält alle unpartitionierten knoten
    //zuerst die nachbarn von b bis zum index end_of_neighbors
    //ab end_of_neighbors +1 kommen alle anderen unpartitionierten knoten
    bfs();
    /*
    std::cerr << x.size() << std::endl;
    for(int i = 0; i < x.size(); i++){
        std::cerr << x[i] << "  ";
    }
    std::cerr << " end_of_neighbors: " << end_of_neighbors << std::endl;
    */
   
    //P konstruieren
    //dafür für jeden nachbarn von B einen eigenen Block
    //dann jeweils kleinsten block um einen nachbarn erweitern
    //danach lokale suche um balance zu verbessern
    //knoten aus x die in keinem block von P sind sind unerreichbar von B
    partitioning.resize(end_of_neighbors+1);
    for(unsigned int i = 0; i <= end_of_neighbors; i++){
        partitioning[i].push_back(x[i]);
    }
    

    //füge von B unerreichbar knoten zu a hinzu (sind die knoten die
    //bei konstruktion von P "übrig bleiben")
    //danach füge Knoten aus größtem Block hinzu bis A* < n/2
    /*while(a_count < graph_.num_nodes()/2){

    }
    */
    return;

};