/*
 *  dijkstra.cpp 
 * 
 *  (c) Daniel Jackson 2004. 
 *  CIS 11 Data Structures & Algorithms 
 * 
 
Implementation for class providing Dijkstra's Algorithm. 
 
Class Invariant:

  start is equal to the starting vertex for the algorithm. 
  theGraph is the graph passed to the class. 
  distances is a dynamic array holding the distance from start to [index] vertex along  
  the shortest path. distance == -1 if unreachable. 
  predecessor is a dynamic array holding the predecessor to [index] along the shortest path 
  from the start vertex. The predecessor is size()+1 if unreachable. 
 
void calculate():

  Fills the distances and predecessor arrays with correct values for the current start vertex. 
  It performs Dijkstra's Algorithm. 
 
bool compare(const int lval, const int rval):

  Returns the less than (lval < rval) result. It treats -1 as infinity. Used because -1 represents 
  infinity in the distances array.
  
*/ 

#include <algorithm> //Provides copy()
#include <vector>    //Provides vector
#include <stack>     //Provides stack
#include <set>       //Provides set
#include "graph.h"   //Provides graph

template <class Item>
Dijkstra<Item>::Dijkstra(graph<Item>* aGraph, std::size_t startVertex) {
  theGraph = aGraph;
  start = startVertex;
  assert(start < theGraph->size());
  distances = new int[theGraph->size()];
  predecessor = new std::size_t[theGraph->size()];
  for (std::size_t i = 0; i < theGraph->size(); ++i) {
    distances[i] = -1;
    predecessor[i] = theGraph->size() + 1; }
  calculate();
}

template <class Item>
void Dijkstra<Item>::GetDistances(int* array) {
  std::copy(distances, distances + theGraph->size(), array);
}

template <class Item>
void Dijkstra<Item>::GetPaths(std::size_t* array) {
  std::copy(predecessor, predecessor + theGraph->size(), array);
}

template <class Item>
int Dijkstra<Item>::Distance(std::size_t target) {
  return distances[target];
}

template <class Item>
std::vector<std::size_t> Dijkstra<Item>::Path(std::size_t target) {
  std::stack<std::size_t> theStack;
  std::vector<std::size_t> answer;
  if (Distance(target) < 0)
    return answer;
  theStack.push(target);
  while (theStack.top() != start)
    theStack.push(predecessor[theStack.top()]);
  while (!theStack.empty()) {
    answer.push_back(theStack.top());
    theStack.pop(); }
  return answer;
}

template <class Item>
void Dijkstra<Item>::ChangeStart(std::size_t newStart) {
  start = newStart;
  for (std::size_t i = 0; i < theGraph->size(); ++i) {
    distances[i] = -1;
    predecessor[i] = theGraph->size() + 1; }
  calculate();
}

template <class Item>
bool Dijkstra<Item>::compare(const int lval, const int rval) {
  if (lval == -1)
    return false;
  if (rval == -1)
    return true;
  return lval < rval;
}

template <class Item>
void Dijkstra<Item>::calculate() {
  //
  // To be written by the student.
  //
}