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);
    }
    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;
    dist[startHandle + n] = 0;
    dist[startHandle + (2*n)] = 0;
    priority_queue pq;
    pq.push({0, startHandle});
    pq.push({0, startHandle + n});
    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:: vector <std::pair<char, int>> answer (n, {'-', -1});
    answer[startHandle].second = 0;
    for (int i = 1; i < n; i++) {
        long long min_dist = 1e12;
        char from = '-';
       /* if(dist[i] < min_dist) {
            min_dist = dist[i];
            from = 'B';
        } */
        if(dist[i+n] < min_dist) {
            min_dist = dist[i+n];
            from = 'R';
        } 
        if(dist[i+ 2*n] < min_dist) {
            min_dist = dist[i + 2*n];
            from = 'G';
        } 
        if(dist[i] < min_dist) {
            min_dist = dist[i];
            from = 'B';
        } 
        
        if (min_dist > 1e10) {
            continue;
        }
        answer[i] = {from, min_dist};
    }
    return answer; 
  
    
}