#include "structures.h"

struct list *cons(void *t,  struct list *tail)
{
  struct list *temp;
  temp=(struct list *)malloc(sizeof(struct term));
  if (temp==NULL)exit(0);
  temp->object=t;
  temp->next=tail;
  return temp;
}

/* used for constructing lists that are later garbage_collected */
struct list *g_cons(void *t, struct list *tail, garbage_lists *g)
{
  struct list *res;
  res=cons(t,tail);
  g->garbage_list_cells=cons(res,g->garbage_list_cells);
  return res;
}
     
struct list *append(struct list *l1, struct list *l2)
{
  struct list *l1_original=l1;
  if (l1==NULL) return l2;
  while (l1->next)
    l1=l1->next;
  l1->next=l2;
  return l1_original;
}
  
void *nth_element(struct list *l, int i)
{
  for(;i>=1;i--) l=l->next;
  return l->object;
}

int list_length(struct list *l)
{
  int i;
  for(i=0;(l);i++)
    l=l->next;
  return i;
}

/* merges two ordered lists */
struct list *merge(struct list *l1, struct list *l2)
{
  struct list *res;
  if (l1==NULL) return l2;
  if (l2==NULL) return l1;
  if (l1->object < l2->object)
    {
      res=l1;
      res->next=merge(l1->next,l2);
    }
  else if (l1->object==l2->object)
    {
      res=l1;
      res->next=merge(l1->next,l2->next);
    }
  else
    {
      res=l2;
      res->next=merge(l1,l2->next);
    }
  return res;
}

/* determine the position of an element on a list */
int position(int t, struct list *l)
{
  int res=0;
  while (l && ((int)l->object)!=t)
    {
      l=l->next;
      res++;
    }
  return res;
}
  
/* checks to see if a term occurs on a list of terms (using
   'loose_match' for comparison, and dereferencing */
int term_on_list(struct term *t, var_array *vars,struct list *l)
{
   struct term *dref_t=dereference(t,vars);
   while(l && !loose_match(dref_t,l->object))
      l=l->next;
   free_term(dref_t);
   return (l!=NULL);
}

/* checks to see if a term occurs on a list of terms (using
   'identical' for comparison */
int nodef_term_on_list(struct term *dref_t, struct list *l)
{
   while(l && !identical(dref_t,l->object))
      l=l->next;
   return (l!=NULL);
}

/* prints a list of integers */
void print_int_list(struct list *l)
{
  for(;l;l=l->next)
    printf("%d ",l->object);
  printf("\n");
}


/*
============================================================
|                      sorted_insert()                     |
|----------------------------------------------------------|
| Params : 1) the address of a list pointer                |
|          2) an element                                   |
|          3) the address of a function to compare elements|
| Desc   : inserts the element in the list at the position
           which would make the list ordered according to
           the comparison function (the first element of
           the list is the highest according to the comp
           function
|                                                          |
|==========================================================|
*/
void sorted_insert(struct list **address, void *element, comp_funct greater)
{
   if (*address==NULL||!(*greater)((*address)->object,element))
      *address=cons(element,*address);
   else
   {
      struct list *temp=*address;
      while(temp->next&& (*greater)(temp->next->object,element))
      {
         temp=temp->next;
      }
      temp->next=cons(element,temp->next);
   }
}