/*                                                                algorithmic.c
   one of the traditional, non-AI, methods                                   */

#include "utilities.h"
#include "data.h"
#include "algorithmic.h"

float *distances=NULL;
float *eta_heap=NULL;
int *where_in_heap=NULL;
city_record **city_heap=NULL;
int num_in_heap=0;

void insert_in_heap(float eta, city_record *where);
void remove_smallest_from_heap(float *eta, city_record **where);
void fix_heap_top_down(int pos);
void fix_heap_bottom_up(int pos);
void prepare_basic_graph_algorithm(city_record *city2);
void run_basic_graph_algorithm(city_record *city1);

float use_basic_graph_algorithm(city_record *city1, city_record *city2)
{ prepare_basic_graph_algorithm(city2);
  run_basic_graph_algorithm(city1);
  return distances[city1->index]; }

void print_all_algorithmic_distances(city_record *city2)
{ int i;
  printf("\nMinimum distances to %s:\n",city2->name);
  for (i=1; i<=num_cities; i+=1)
    if (distances[i]>-0.01)
      printf("  %6.1f miles from %s\n", distances[i], city_list[i]->name); }

void print_heap(void)
{ int i;
  printf("Heap is:\n");
  for (i=1; i<=num_in_heap; i+=1)
    printf("%4d: %6.1f %s\n",i,eta_heap[i],city_heap[i]->name); }

void print_algorithmic_route(city_record *city1, city_record *city2)
{ city_record *a;
  float total=distances[city1->index];
  float orig_total=total;
  printf("\nShortest route from %s to %s:\n",city1->name,city2->name);
  a=city1;
  while (a!=city2)
  { road_record *r=a->roads;
    city_record *next_city;
    int next_city_index;
    while (r!=NULL)
    { next_city=r->end2;
      next_city_index=next_city->index;
      if (difference(distances[next_city_index],total-r->length)<0.01)
        break;
      r=r->next; }
    if (r==NULL)
    { fprintf(stderr,"\n\nOh No! The program is wrong!\nFailed to find viable route\n");
      return; }
    total-=r->length;
    printf("  From %s: %s %.1f miles %s to %s\n",a->name, r->name, r->length,
                                          direction(a,next_city), next_city->name);
    a=next_city; }
  printf("Total of %.1f miles\n\n",orig_total); }
    
void prepare_basic_graph_algorithm(city_record *city2)
{ int i;
  if (distances==NULL)
  { distances=(float *)malloc((num_cities+1)*sizeof(float));
    eta_heap=(float *)malloc((num_cities+1)*sizeof(float));
    where_in_heap=(int *)malloc((num_cities+1)*sizeof(int));
    city_heap=(city_record **)malloc((num_cities+1)*sizeof(city_record *)); }
  for (i=1; i<=num_cities; i+=1)
    distances[i]=-1;
  eta_heap[1]=0;
  city_heap[1]=city2;
  distances[city2->index]=0;
  where_in_heap[city2->index]=1;
  num_in_heap=1; }

void run_basic_graph_algorithm(city_record *city1)
{ int numops=1;
  while (num_in_heap>0)
  { city_record *here;
    float now;
    road_record *r;
    remove_smallest_from_heap(&now,&here);
    if (here==city1) break;
    r=here->roads;
    while (r!=NULL)
    { city_record *there=r->end2;
      float eta=now+r->length;
      numops+=1;
      if (distances[there->index]<0)
      { distances[there->index]=eta;
        insert_in_heap(eta,there); }
      else if (distances[there->index]>eta)
      { int pos=where_in_heap[there->index];
        distances[there->index]=eta;
        eta_heap[pos]=eta;
        fix_heap_bottom_up(pos); }
      r=r->next;  } }
  printf("\n%d operations were performed\n",numops); }

void remove_smallest_from_heap(float *eta, city_record **where)
{ int here;
  *eta=eta_heap[1];
  *where=city_heap[1];
  where_in_heap[(*where)->index]=0;
  eta_heap[1]=eta_heap[num_in_heap];
  city_heap[1]=city_heap[num_in_heap];
  where_in_heap[city_heap[1]->index]=1;
  num_in_heap-=1;
  here=1;
  fix_heap_top_down(here); }

void fix_heap_top_down(int here)
{ while (1)
  { int smallest_pos=here;
    int left=here*2, right=left+1;
    float tf;
    city_record *tc;
    if (left<=num_in_heap && eta_heap[left]<=eta_heap[here])
      smallest_pos=left;
    if (right<=num_in_heap && eta_heap[right]<=eta_heap[smallest_pos])
      smallest_pos=right;
    if (smallest_pos==here) break;
    tf=eta_heap[smallest_pos];
    eta_heap[smallest_pos]=eta_heap[here];
    eta_heap[here]=tf;
    tc=city_heap[smallest_pos];
    city_heap[smallest_pos]=city_heap[here];
    city_heap[here]=tc;
    where_in_heap[city_heap[here]->index]=here;
    where_in_heap[city_heap[smallest_pos]->index]=smallest_pos;
    here=smallest_pos; } }

void insert_in_heap(float eta, city_record *where)    
{ int here=num_in_heap+1;
  num_in_heap=here;
  eta_heap[here]=eta;
  city_heap[here]=where;
  where_in_heap[where->index]=here;
  fix_heap_bottom_up(here); }

void fix_heap_bottom_up(int here)
{ while (here>1)
  { int parent=here/2;
    float tf;
    city_record *tc;
    if (eta_heap[parent]<=eta_heap[here]) break;
    tf=eta_heap[here];
    eta_heap[here]=eta_heap[parent];
    eta_heap[parent]=tf;
    tc=city_heap[here];
    city_heap[here]=city_heap[parent];
    city_heap[parent]=tc;
    where_in_heap[city_heap[here]->index]=here;
    where_in_heap[city_heap[parent]->index]=parent;
    here=parent; } }