#ifndef DIJKSTRA_HPP_
#define DIJKSTRA_HPP_

#include <string>
#include <iostream>
#include <fstream>
#include <sstream>
#include <limits>                    //Biggest int: std::numeric_limits<int>::max()
#include "array_queue.hpp"
#include "array_stack.hpp"
#include "heap_adjustable_hash_priority_queue.hpp"
#include "hash_graph.hpp"


namespace ics {


class Info {
  public:
    Info() { }

    Info(std::string a_node) : node(a_node) { }

    bool operator==(const Info &rhs) const { return node == rhs.node && cost == rhs.cost && from == rhs.from; }

    bool operator!=(const Info &rhs) const { return !(*this == rhs); }

    friend std::ostream &operator<<(std::ostream &outs, const Info &i) {
      outs << "Info[" << i.node << "," << i.cost << "," << i.from << "]";
      return outs;
    }

    //Public instance variable definitions
    std::string node = "?";
    int cost = std::numeric_limits<int>::max();
    std::string from = "?";
  };


  bool gt_info(const Info &a, const Info &b) { return a.cost < b.cost; }
  int hash_info(const Info &a){return (a.cost == std::numeric_limits<int>::max()) ? a.cost :  0;}

  //Put needed hashing functions here

  typedef ics::HashGraph<int>                                               DistGraph;
  typedef ics::HeapAdjustableHashPriorityQueue<Info, gt_info,hash_info>     CostPQ;
  typedef ics::HashOpenMap<std::string, Info, DistGraph::hash_str>          CostMap;
  typedef ics::pair<std::string, Info>                                      CostMapEntry;

//Return the final_map as specified in the lecture-note description of
//  extended Dijkstra algorithm
  CostMap extended_dijkstra(const DistGraph &g, std::string start_node) {
        CostMap answer_map;
        HashOpenMap<std::string, Info>  info_map;
        for(auto i: g.all_nodes()) {
            info_map[i.first] = Info();
        }
        info_map[start_node].cost = 0;

        CostPQ info_pq;
        for(auto i:g.all_nodes()){
            info_pq.enqueue(info_map[i.first]);
        }

        while(!info_map.empty()){
            Info current = info_pq.dequeue();
            if(current.cost == std::numeric_limits<int>::max()){
                break;
            }
            std::string min_node = current.node;
            int min_cost = current.cost;
            info_map.erase(min_node);
            answer_map.put(min_node,current);

            for(const auto& d: g.out_nodes(min_node)){
                if(!answer_map.has_key(d)){
                    Info old = info_map[d];
                    if( info_map[d].cost == std::numeric_limits<int>::max() || info_map[d].cost < (min_cost + g.edge_value(min_node,d))){
                        info_map[min_node].cost = info_map[d].cost;
                        info_map[d].from = min_node;
                        info_pq.update(old,info_map[d]);
                    }
                }
            }

        }
        return answer_map;


  }


//Return a queue whose front is the start node (implicit in answer_map) and whose
//  rear is the end node
  ArrayQueue <std::string> recover_path(const CostMap &answer_map, std::string end_node) {
        CostMap temp  = answer_map;
        ArrayStack <std::string>tempStack;
        std::string counter = end_node;
        while(temp[counter].from != "?"){
            tempStack.push(counter);
            counter = temp[counter].from;
        }
        tempStack.push(counter);

        ArrayQueue <std::string> minPath;
        while(!tempStack.empty()){
            minPath.enqueue(tempStack.pop());
        }
        return minPath;

  }


}

#endif /* DIJKSTRA_HPP_ */