Untitled

#include "color_walk.hpp"

using namespace cs251;


class priority_queue {
 
private :
    
    std:: vector <std:: pair <int, int>> m_arr;
    int m_size = 0;
    void bottom_up(int index) {
        if (index == 0) {
            return;    
        }
        int par = (index-1)/2;
        if(m_arr[par] > m_arr[index]) {
            std:: pair <int, int> temp = m_arr[par];
            m_arr[par] = m_arr[index];
            m_arr[index] = temp;
            bottom_up(par);
        }
    }
    void top_down(int index){
        int left = (2 * index) + 1;
        int right = (2 * index) + 2;
        if (left >= m_size) {
             return;   
        }
        int min_index = index; 
        if (m_arr[index]> m_arr[left]) {
            min_index = left;
        }
        if ((right < m_size) && (m_arr[index] > m_arr[right])) {
            min_index = right;
        }
        if (min_index != index) {
           std:: pair <int, int> temp = m_arr[min_index];
            m_arr[min_index] = m_arr[index];
            m_arr[index] = temp;
            top_down(min_index);
        }
    }
    
    
public :
    
    void push (std:: pair <int, int> node){
        m_arr.push_back(node);
        m_size++;
        bottom_up(m_size -1);
    }
    void pop(){
        std:: pair <int, int> temp = m_arr[0];
        m_arr[0] = m_arr[m_size - 1];
        m_arr[m_size - 1] = temp;
        m_arr.pop_back();
        m_size--;
        top_down(0);
    }
    std:: pair <int, int> top(){
        return m_arr[0];
    }
    int size() {
        return m_size;
    }
    bool empty() {
        return m_size == 0;   
    }
    
    
    
    
    
};

std::vector<std::pair<char, int>> color_walk::calculate(const graph& g, const handle startHandle) {
    // TODO: Implement color walk	
    //throw std::logic_error("color_walk::" + std::string(__FUNCTION__) + "() not implemented");


    int n = g.graph_vertices;
    std:: vector <graph_vertex> adj_list = g.read_graph();


   /* for (int i = 0; i < adj_list.size(); i++) {
        std:: cout << i << " -> ";
        for (int j = 0; j < adj_list[i].m_edges.size(); j++) {
            std:: cout << "{" << adj_list[i].m_edges[j].m_destinationHandle << ", " << adj_list[i].m_edges[j].m_weight << " }, ";
        }  
        std:: cout << "\n";
    } */


    std:: vector <long long> dist(3*n, 1e15);
    dist[startHandle] = 0;
    priority_queue pq;
    pq.push({0, startHandle});

    while (!pq.empty()) {
        int node = pq.top().second;
        int d = pq.top().first;
        pq.pop();
        for (int i=0; i < adj_list[node].m_edges.size(); i++) {
            int v = adj_list[node].m_edges[i].m_destinationHandle;
            int w = adj_list[node].m_edges[i].m_weight;
            color c = adj_list[node].m_edges[i].col;
            if (d + w <= dist[v]){
                dist[v] = d + w;
                pq.push({dist[v], v});
            }
        }
    }

    // std:: cout << "dist after red\n";
    // for (int i =0; i<dist.size(); i++) {
    //     std::cout << "{" << (i%n) << " " << dist[i] << "}, ";
    // }
    // std::cout << std::endl;


    std:: vector <std::pair<char, int>> answer (n, {'-', 1e9});
    
    for (int i = 0; i < n; i++) {
        long long min_dist = 1e12;

        if(dist[i+n] < min_dist) {
            min_dist = dist[i+n];
            
        }

        if(dist[i+ 2*n] < min_dist) {
            min_dist = dist[i + 2*n];
            
        }

        if(dist[i] < min_dist) {
            min_dist = dist[i];
            
        } 
        
        if (min_dist > 1e10) {
            continue;
        }

        answer[i] = {'R', min_dist};
    }
    answer[startHandle] = {'-',0};


    // std:: cout << "answer after red\n";
    // for (auto p : answer) {
	// 		std::cout << p.first << " " << p.second << ", ";
	// 	}
    // std::cout << std::endl;


    dist = std:: vector <long long> (3*n, 1e15);
    dist[startHandle + n] = 0;
    pq.push({0, startHandle + n});
    while (!pq.empty()) {
        int node = pq.top().second;
        int d = pq.top().first;
        pq.pop();
        for (int i=0; i < adj_list[node].m_edges.size(); i++) {
            int v = adj_list[node].m_edges[i].m_destinationHandle;
            int w = adj_list[node].m_edges[i].m_weight;
            color c = adj_list[node].m_edges[i].col;
            if (d + w <= dist[v]){
                dist[v] = d + w;
                pq.push({dist[v], v});
            }
        }
    } 

    // std:: cout << "dist after green\n";
    // for (int i =0; i<dist.size(); i++) {
    //     std::cout << "{" << (i%n) << " " << dist[i] << "}, ";
    // }
    // std::cout << std::endl;

    
    for (int i = 0; i < n; i++) {
        long long min_dist = 1e12;

        if(dist[i] < min_dist) {
            min_dist = dist[i];
        } 

        if(dist[i+n] < min_dist) {
            min_dist = dist[i+n];
        } 

        if(dist[i+ 2*n] < min_dist) {
            min_dist = dist[i + 2*n];
        }
        
        if (min_dist > 1e10) {
            continue;
        }
        
        if (min_dist < answer[i].second) {
            answer[i] = {'G', min_dist};
        } 
    }
    answer[startHandle] = {'-',0};
    
    
    // std:: cout << "answer after green\n";
    // for (auto p : answer) {
    //     std::cout << p.first << " " << p.second << ", ";
    // }
    // std::cout << std::endl;
    
    
    
    dist = std:: vector <long long> (3*n, 1e15);
    dist[startHandle + (2*n)] = 0;
    pq.push({0, startHandle + 2*n});
    while (!pq.empty()) {
        int node = pq.top().second;
        int d = pq.top().first;
        pq.pop();
        for (int i=0; i < adj_list[node].m_edges.size(); i++) {
            int v = adj_list[node].m_edges[i].m_destinationHandle;
            int w = adj_list[node].m_edges[i].m_weight;
            color c = adj_list[node].m_edges[i].col;
            if (d + w <= dist[v]){
                dist[v] = d + w;
                pq.push({dist[v], v});
            }
        }
    } 
    
    // std:: cout << "dist after blue\n";
    // for (int i =0; i<dist.size(); i++) {
    //     std::cout << "{" << (i%n) << " " << dist[i] << "}, ";
    // }
    // std::cout << std::endl;
    
    for (int i = 0; i < n; i++) {
        long long min_dist = 1e12;
        if(dist[i+n] < min_dist) {
            min_dist = dist[i+n];
            
        } 

        if(dist[i+ 2*n] < min_dist) {
            min_dist = dist[i + 2*n];
            
        }

        if(dist[i] < min_dist) {
            min_dist = dist[i];
            
        } 
        
        if (min_dist > 1e10) {
            continue;
        }
        
        if (answer[i].second > min_dist) {
            answer[i] = {'B', min_dist};
        }
    }
    answer[startHandle] = {'-',0};
    
    
    // std:: cout << "answer after blue\n";
    // for (auto p : answer) {
    //     std::cout << p.first << " " << p.second << ", ";
    // }
    // std::cout << std::endl;
    return answer; 
  
    
}