/* wdg_ads_m.c      */
/* Alexander Sinko */
/* 08.11.2009      */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#include "wdg_ads_m.h"

static int *aMatrix; /* =aMatrix[NrOfNodes][NrOfNodes] */
static int NrOfNodes;


int GetElementAt(int row, int col){
  return *((int*)aMatrix + (NrOfNodes * row) + col);
} /*ElementAt*/


void SetElementAt(int row, int col, int value){
  *((int*)aMatrix + (NrOfNodes * row) + col) = value;
  return;
} /*ElementAt*/

bool InitGraph(int numberOfNodes){
  int row, col;
  NrOfNodes = numberOfNodes;
  /* allocate memory for aMatrix[NrOfNodes][NrOfNodes] */
  aMatrix = (int*)malloc(sizeof(int) * NrOfNodes * NrOfNodes);
  if (aMatrix == NULL)
    return false;
  for(row = 0; row < NrOfNodes; row++){
    for(col = 0; col < NrOfNodes; col++){
      SetElementAt(row, col, 0);
    } /*for*/
  } /*for*/
  return true;
} /*InitGraph*/


bool AddEdge(int fromNode, int toNode, int weight){
  /* convert "fromNode" and "toNode" to index of array */
  SetElementAt(fromNode-1, toNode-1, weight);
  return true;
} /*AddEdge*/


void RemoveEdge(int fromNode, int toNode){
  /* convert "fromNode" and "toNode" to index of array */
  SetElementAt(fromNode-1, toNode-1, 0);
  return;
} /*RemoveEdge*/


void PrintGraph(){
  int row, col;
  int valCache;
  printf("Graph:\n   ");
  for (col = 0; col < NrOfNodes; col++)
    printf("%2d ", col+1);
  printf("\n  +");
  for (col = 0; col < NrOfNodes; col++)
    printf("---");
  printf("\n");
  for (row = 0; row < NrOfNodes; row++) {
    printf ("%2d|", row+1);
    for (col = 0; col < NrOfNodes; col++) {
      valCache = GetElementAt(row, col);
      if (valCache == INT_MIN)
        printf(" ? ");
      else if (valCache == 0)
        printf(" - ");
      else
        printf("%2d ", valCache);

    } /*for*/
    printf("\n");
  } /*for*/
  printf("\n");
  return;
} /*PrintGraph*/


void ForEachNode(NodeHandler hdlr) {
  int node;
  for (node = 0; node < NrOfNodes; node++){
    (*hdlr)(node+1);
  } /*for*/
  return;
} /*ForEachNode*/


void ForEachEdge(EdgeHandler hdlr) {
  int fromNode;
  int toNode;
  int weightCache;
  for (fromNode = 0; fromNode < NrOfNodes; fromNode++){
    for(toNode = 0; toNode < NrOfNodes; toNode++){
      weightCache = GetElementAt(fromNode, toNode);
      if (weightCache != 0)
        (*hdlr)(fromNode+1, toNode+1, weightCache);
    } /*for*/
  } /*for*/
  return;
} /*ForEachEdge*/


void DestroyGraph(){
  free(aMatrix);
  return;
} /*DestroyGraph*/


void PrintFWMatrix(){
  int *fwMatrix; /* =fwMatrix[NrOfNodes][NrOfNodes] */
  int i, j, k;
  int valCache;
  int hugeNumber = 9999;

  int FWGetElementAt(int row, int col){
    return *((int*)fwMatrix + (NrOfNodes * row) + col);
  } /*FWGetElementAt*/

  void FWSetElementAt(int row, int col, int value){
    *((int*)fwMatrix + (NrOfNodes * row) + col) = value;
    return;
  } /*FWGetElementAt*/

  void FWPrintGraph(){
    int row, col;
    int valCache;
    printf("Shortest ways:\n   ");
    for (col = 0; col < NrOfNodes; col++)
      printf("%2d ", col+1);
    printf("\n  +");
    for (col = 0; col < NrOfNodes; col++)
      printf("---");
    printf("\n");
    for (row = 0; row < NrOfNodes; row++) {
      printf ("%2d|", row+1);
      for (col = 0; col < NrOfNodes; col++) {
        valCache = FWGetElementAt(row, col);
        if (valCache == hugeNumber)
          printf(" - ");
        else
          printf("%2d ", valCache);
      } /*for*/
      printf("\n");
    } /*for*/
    printf("\n");
    return;
  } /*FWPrintGraph*/

  int Min(int value1, int value2){
    if (value1 < value2)
      return value1;
    else
      return value2;
  } /*Min*/

  /*allocate memory*/
  fwMatrix = (int*)malloc(sizeof(int) * NrOfNodes * NrOfNodes);
  if (fwMatrix == NULL){
    printf("ERROR: Can't allocate memory\n");
    return;
  } /*if*/

  /*copy aMatrix to fwMatrix*/
  for(i = 0; i < NrOfNodes; i++){
    for(j = 0; j < NrOfNodes; j++){
      valCache = GetElementAt(i, j);
      if ((valCache == INT_MIN) ||
          (valCache == 0)){
        /* if no weight is set, insert huge number */
        valCache = hugeNumber;
      } /*if*/
      FWSetElementAt(i, j, valCache);
    } /*for*/
  } /*for*/

  /*calculate shortest ways (FW-Alogithm)*/
  for (k = 0; k < NrOfNodes; k++){
    for (i = 0; i < NrOfNodes; i++){
      for (j = 0; j < NrOfNodes; j++){
        valCache = Min(FWGetElementAt(i, j), FWGetElementAt(i,k) + FWGetElementAt(k,j));
        FWSetElementAt(i, j, valCache);
      } /*for j*/
    } /*for i*/
  } /*for k*/

  /*print matrix*/
  FWPrintGraph();

  /*free memory*/
  free(fwMatrix);

  return;
} /*PrintFWMatrix*/