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

struct point {int x; int y;};
typedef struct point point;

void prnt_point(point p){
  printf("Point: %i, %i\n", p.x, p.y);
}   

struct cons_cell {
  void             *data;
  struct cons_cell *next;
};

typedef struct cons_cell cons_cell;

/* Returns a pointer to a new cons cell, 
   which refers data and next via pointers*/
cons_cell *cons(void *data, cons_cell *next){
 cons_cell *result;
 result = malloc(sizeof(cons_cell));
 result->data = data;
 result->next = next;
 return result;
}

/* Return the head reference of the cons cell */
void *head(cons_cell *cell){
  return cell->data;
}

/* Return the tail refererence f the cons cell */
cons_cell *tail(cons_cell *cell){
  return cell->next;
}   

/* Change the data position of cell to new_head */
void set_head(cons_cell *cell, void *new_head){
  cell->data = new_head;
}

/* Change the next position of cell to new_tail */
void set_tail(cons_cell *cell, cons_cell *new_tail){
  cell->next = new_tail;
}   

/* Return the number of elements in list */
int list_length(cons_cell *list){
  if (list == NULL)
    return 0;
  else return 1 + list_length(tail(list));
}

/* Append list1 and list2. The elements in list2 are shared between
   the appended list and list2 */
cons_cell *append(cons_cell *list1, cons_cell *list2){
  if (list1 == NULL)
    return list2;
  else return cons(head(list1),
                   append(tail(list1),list2));
}

/* Is el member of list as a data element? 
   Comparisons are done by reference equality */
int member(void *el, cons_cell *list){
  if (list == NULL)
    return 0;
  else if (head(list) == el)
    return 1;
  else
    return member(el, tail(list));
}

/* Returned list in reverse order */
cons_cell *reverse(cons_cell *list){
  if (list == NULL)
    return NULL;
  else 
    return append(reverse(tail(list)), cons(head(list), NULL));
}
  

int main(void) {

  cons_cell *points, *more_points, *point_list, *pl;

  point p1 = {1,2}, p2 = {3,4}, p3 = {5,6}, p4 = {6,7},
        p5 = {8,9}, p6 = {10,11}, p7 = {12,13}, p8 = {14,15};

  points = cons(&p1,
                cons(&p2,
                     cons(&p3,
                          cons(&p4,NULL))));

  more_points = 
           cons(&p5,
                cons(&p6,
                     cons(&p7,
                          cons(&p8,NULL))));

  printf("Number of points in the list points: %i\n", 
         list_length(points));

  point_list = append(points, more_points);
  pl = point_list;

  while (pl != NULL) {
    prnt_point(*((point*)(head(pl))));
    pl = tail(pl);
  }

  if (member(&p6, points))
    printf("p6 is member of points\n");
  else  printf("p6 is NOT member of points\n");

  if (member(&p6, more_points))
    printf("p6 is member of more_points\n");
  else  printf("p6 is NOT member of more_points\n");

  if (member(&p6, point_list))
    printf("p6 is member of point_list\n");
  else  printf("p6 is NOT member of point_list\n");


  pl = reverse(points);

  while (pl != NULL) {
    prnt_point(*((point*)(head(pl))));
    pl = tail(pl);
  }
  
  return 0;
}