#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include "graph.h"

/* implement the functions you declare in graph.h here */
//used to check tours for completeness
int tot_vert = 0;

//you can use this to start the list, but you have to capture the return value
vertex_t* add_edge(vertex_t *vtxhead, char *v1_name, char *v2_name, int weight) {
   if((vtxhead)==NULL){
      vtxhead=add_vert((vtxhead),v1_name);
      add_vert((vtxhead),v2_name);
      add_link((vtxhead),(vtxhead)->next,weight);
      return vtxhead;
   }
   if(find_vert((vtxhead),v1_name)==NULL)
      add_vert((vtxhead),v1_name);
   if(find_vert((vtxhead),v2_name)==NULL)
      add_vert((vtxhead),v2_name);
   add_link(find_vert((vtxhead),v1_name),find_vert((vtxhead),v2_name),weight);
   return NULL;
}
//can be used to start the graph, is also used internally
vertex_t* add_vert(vertex_t *curr, char *name){
   if(curr==NULL){
      curr = malloc(sizeof(vertex_t));
      curr->name = (name);
      curr->adj_list=NULL;
      ++tot_vert;
      return curr;
   }
   if(curr->next == NULL){
      curr->next = malloc(sizeof(vertex_t));
      curr->next->name=(name);
      curr->next->adj_list=NULL;
      ++tot_vert;
      return curr;
   }
   return(add_vert(curr->next, name));
}
//wrapper that does not have the count var.
void add_link(vertex_t *v1, vertex_t *v2, int weight){
   add_link_help(v1, v2, weight, 0);
}
//uses a counter to allow input flipping once
void add_link_help(vertex_t *v1, vertex_t *v2, int weight, int count){
   if(v1->adj_list==NULL){
      v1->adj_list=malloc(sizeof(adj_vertex_t));
      v1->adj_list->edge_weight = weight;
      v1->adj_list->vertex = v2;
      v1->adj_list->next = NULL;
      if(count == 0){
         return add_link_help(v2,v1,weight,++count);
      }
      return;
   }
   adj_vertex_t *tmp = (find_last(v1->adj_list))->next = malloc(sizeof(adj_vertex_t));
   tmp->edge_weight = weight;
   tmp->vertex = v2;
   tmp->next = NULL;
   if(count == 0){
      //flip inputs and add links the other way
      return add_link_help(v2,v1,weight,++count);
   }
   return;
}
//where am I adding this link?
adj_vertex_t* find_last(adj_vertex_t *curr){
   if(curr->next == NULL) return curr;
   return (find_last(curr->next));
}
//does this vertex allready exist?
vertex_t* find_vert(vertex_t *curr, char *name){
   if(curr==NULL){
      return NULL;
   }
   if(strcmp(curr->name, name)==0){
      return curr;
   }
   return find_vert(curr->next,name);
}

/* 
   BEGIN TOURING CODE




 */
tour_t* tour(vertex_t* curr){
   tour_t* head = make_tour_node(curr,NULL);
   if(search(head)==0){
      printf("No tours found\n");
      return head;
   }
   printf("Tour:\n");
   print_tour(head);
   return head;
}

void print_tour(tour_t* head){
   int sum=0;
   while(head!=NULL){
      printf("%s\n",head->node->name);
      if(head->next!=NULL)
         sum+=get_weight(head->curr,head->node->adj_list);
      head=head->next;
   }
   printf("Sum: %d \n", sum);
}
   
tour_t* make_tour_node(vertex_t* curr, tour_t* prev){
   tour_t* head = malloc(sizeof(tour_t));
   head->node=curr;
   head->links = count_adj(curr->adj_list);
   head->curr = 1;
   head->prev=prev;
   head->next=NULL;
   if(prev!=NULL){
      head->length = prev->length +1;
   }
   else
      head->length = 1;
   return head;
}

int search(tour_t* head){
   if(head->length==tot_vert)
      return 1;
   while((head->curr)<=(head->links)){
      if(is_in_tour(head,get_adj(head->curr,head->node->adj_list))){
         ++(head->curr);
         continue;
      }

      if(head->next!=NULL)
         free(head->next);

      head->next=make_tour_node(get_adj(head->curr,head->node->adj_list),head);
      int result = search(head->next);
      if(result==0){
         ++(head->curr);
         continue;
      }
      return result;

   }
   return 0;
}

int count_adj(adj_vertex_t * curr){
   if(curr==NULL)
      return 0;
   return 1+count_adj(curr->next);
}
int is_in_tour(tour_t* curr, vertex_t *key){
   if(curr->node==key)
      return 1;
   if(curr->prev==NULL)
      return 0;
   return is_in_tour(curr->prev,key);
}
vertex_t* get_adj(int spot, adj_vertex_t * curr){
   if(spot==1)
      return curr->vertex;
   return get_adj(spot-1,curr->next);
}
int get_weight(int spot, adj_vertex_t * curr){
   if(spot==1)
      return curr->edge_weight;
   return get_weight(--spot,curr->next);
}

/* 
   BEGIN FREEING CODE



 */
void free_all(vertex_t *curr){
   if(curr==NULL){
      return;
   }
   free_all(curr->next);
   if(curr->adj_list!=NULL)
      free_adj(curr->adj_list);
   free(curr);
   return;
}
void free_adj(adj_vertex_t *curr){
   if(curr==NULL)
      return;
   free_adj(curr->next);
   free(curr);
   return;
}
void free_tour(tour_t * curr){
   if(curr==NULL)
      return;
   free_tour(curr->next);
   free(curr);
   return;
}