/*                                                                    aiutils.c
        Utilities to help with basic AI techniques                           */

#include "utilities.h"
#include "data.h"
#include "aiutils.h"

list_of_cities *empty_list_of_cities(void)
{ list_of_cities *r=(list_of_cities *)malloc(sizeof(list_of_cities));
  r->first=NULL;
  r->last=NULL;
  r->num_entries=0;
  return r; }

int is_city_list_empty(list_of_cities *list)
{ return (list->first==NULL); }

int number_of_cities_in_list(list_of_cities *list)
{ return (list->num_entries); }

void add_city_to_front_of_list(list_of_cities *list, city_record *city)
{ struct city_list_link *s=(struct city_list_link *)malloc(sizeof(struct city_list_link));
  s->this=city;
  s->next=list->first;
  list->first=s;
  if (list->last==NULL)
    list->last=s;
  list->num_entries+=1; }

city_record *first_city_in_list(list_of_cities *list)
{ if (list->first==NULL)
    return NULL;
  return (list->first->this); }

city_record *remove_first_city_from_list(list_of_cities *list)
{ struct city_list_link *c;
  if (list->first==NULL)
    return NULL;
  c=list->first;
  list->first=c->next;
  if (list->first==NULL)
    list->last=NULL;
  list->num_entries-=1;
  return (c->this); }

void add_city_to_end_of_list(list_of_cities *list, city_record *city)
{ struct city_list_link *s=(struct city_list_link *)malloc(sizeof(struct city_list_link));
  s->this=city;
  s->next=NULL;
  if (list->last==NULL)
  { list->last=s;
    list->first=s; }
  else
  { list->last->next=s;
    list->last=s; }
  list->num_entries+=1; }

city_record *last_city_in_list(list_of_cities *list)
{ if (list->last==NULL)
    return NULL;
  return (list->last->this); }

list_of_roads *empty_list_of_roads(void)
{ list_of_roads *r=(list_of_roads *)malloc(sizeof(list_of_roads));
  r->first=NULL;
  r->last=NULL;
  r->total_length=0;
  r->num_entries=0;
  return r; }

void print_list_of_roads(list_of_roads *list)
{ struct road_list_link *r=list->first;
  int i=1;
  if (r==NULL)
  { printf("  <empty route>\n");
    return; }
  while (r!=NULL)
  { road_record *rr=r->this;
    printf("%3d: %s, %.1f miles to %s\n", i, rr->name, rr->length, rr->end2->name);
    i+=1; 
    r=r->next; } }

int is_road_list_empty(list_of_roads *list)
{ return (list->first==NULL); }

int number_of_roads_in_list(list_of_roads *list)
{ return (list->num_entries); }

float total_length_of_path(list_of_roads *list)
{ return (list->total_length); }

void add_road_to_front_of_list(list_of_roads *list, road_record *road)
{ struct road_list_link *s=(struct road_list_link *)malloc(sizeof(struct road_list_link));
  s->this=road;
  s->next=list->first;
  list->first=s;
  if (list->last==NULL)
    list->last=s;
  list->total_length+=road->length;
  list->num_entries+=1; }

road_record *first_road_in_list(list_of_roads *list)
{ if (list->first==NULL)
    return NULL;
  return (list->first->this); }

road_record *remove_first_road_from_list(list_of_roads *list)
{ struct road_list_link *r;
  if (list->first==NULL)
    return NULL;
  r=list->first;
  list->first=r->next;
  if (list->first==NULL)
    list->last=NULL;
  list->num_entries-=1;
  list->total_length-=r->this->length;
  return (r->this); }

void add_road_to_end_of_list(list_of_roads *list, road_record *road)
{ struct road_list_link *s=(struct road_list_link *)malloc(sizeof(struct road_list_link));
  s->this=road;
  s->next=NULL;
  if (list->last==NULL)
  { list->last=s;
    list->first=s; }
  else
  { list->last->next=s;
    list->last=s; }
  list->total_length+=road->length;
  list->num_entries+=1; }

road_record *last_road_in_list(list_of_roads *list)
{ if (list->last==NULL)
    return NULL;
  return (list->last->this); }

int is_empty_set(set_of_states *set)
{ return (set->size==0); }

set_of_states *empty_set(void)
{ set_of_states *result=(set_of_states *)malloc(sizeof(set_of_states));
  result->links=NULL;
  result->size=0;
  return result; }

void add_to_set(set_of_states *set, state *addition)
{ struct state_set_link *newlink=(struct state_set_link *)malloc(sizeof(struct state_set_link));
  newlink->this=addition;
  newlink->next=set->links;
  set->links=newlink;
  set->size+=1; }

int size_of_set(set_of_states *set)
{ return (set->size); }

state *remove_random_member_from_set(set_of_states *set)
{ int i, k, n;
  struct state_set_link **ptr, *oldlink;
  state *answer;
  n=set->size;
  if (n==0)
    return NULL;
  k=random_in_range(1,n);
  ptr=&(set->links);
  for (i=1; i<k; i+=1)
    ptr=&((*ptr)->next);
  oldlink=*ptr;
  answer=oldlink->this;
  *ptr=(*ptr)->next;
  set->size-=1;
  free(oldlink);
  return answer; }

state *new_state(city_record *from, city_record *to)
{ state *r=(state *)malloc(sizeof(state));
  r->route=empty_list_of_roads();
  r->from=from;
  r->to=to;
  return r; }

state *duplicate_state(state *orig)
{ state *s=(state *)malloc(sizeof(state));
  s->from=orig->from;
  s->to=orig->to;
  s->route=duplicate_list_of_roads(orig->route);
  return s; }

list_of_roads *duplicate_list_of_roads(list_of_roads *orig)
{ struct road_list_link *rll;
  list_of_roads *s=empty_list_of_roads();
  rll=orig->first;
  while (rll!=NULL)
  { add_road_to_end_of_list(s,rll->this);
    rll=rll->next; }  
  return s; }

list_of_cities *duplicate_list_of_cities(list_of_cities *orig)
{ struct city_list_link *cll;
  list_of_cities *s=empty_list_of_cities();
  cll=orig->first;
  while (cll!=NULL)
  { add_city_to_end_of_list(s,cll->this);
    cll=cll->next; }  
  return s; }

int city_appears_in_list_of_roads(list_of_roads *lr, city_record *c)
{ struct road_list_link *rll=lr->first;
  while (rll!=NULL)
  { road_record *rr=rll->this;
    if (rr->end1==c || rr->end2==c)
      return 1;
    rll=rll->next; }
  return 0; }