/* Course: Parallel and Distributed Technology
   Class:  C Revision (Part 1)
   Exercise 1: lists

*/

/* includes */
#include <stdio.h>
#include <stdlib.h>

/* externs */

/* types */
typedef struct _node { int value; struct _node *next; } node;
typedef node *list;
// the above makes list equivalent to (struct node *)

/* prototypes */
void showArr (int len, int *arr);
void showSizes ();
node *mkList(int len, int *arr);
void showList(node *x);
node *append(node *x, node *y);
node *appendShare(node *x, node *y);
node *appendModify(node *x, node *y);
node *reverse(node *x);

/* code */
int main () {

  /* lists */
  printf("\nLists, implemented using structures\n");
  int a[3] = { 1, 2, 3 };
  int b[2] = { 4, 5 };
  node *x, *y, *z, *zz;

  x = mkList(3, a);
  y = mkList(2, b);
  printf("Input: \n");
  printf("List x: ");  showList(x);
  printf("List y: ");  showList(y);

  z = appendModify(x,y);
  printf("z = appendModify(x,y): expect x to be modified ...\n");
  printf("Result: \n");
  printf("List z: ");  showList(z);

  printf("Now, the input lists look like this: \n");
  printf("List x: ");  showList(x);
  printf("List y: ");  showList(y);

  x = mkList(3, a);
  y = mkList(2, b);
  printf("Input: \n");
  printf("List x: ");  showList(x);
  printf("List y: ");  showList(y);

  z = appendShare(x,y);
  printf("z = appendShare(x,y): expect sharing of z and y ...\n");
  printf("Result: \n");
  printf("List z: ");  showList(z);

  printf("Now, the input lists look like this: \n");
  printf("List x: ");  showList(x);
  printf("List y: ");  showList(y);
  printf("\nBecause of sharing, modifying the first element in y to 9 also modifies z ...\n");
  y->value = 9;
  printf("List y: ");  showList(y);
  printf("List z: ");  showList(z);

  x = mkList(3, a);
  y = mkList(2, b);
  printf("Input: \n");
  printf("List x: ");  showList(x);
  printf("List y: ");  showList(y);
  z = append(x,y);
  printf("z = append(x,y): this is a safe version, which copies both x and y ...\n");
  printf("Result: \n");
  printf("List z: ");  showList(z);

  printf("Now, the input lists look like this: \n");
  printf("List x: ");  showList(x);
  printf("List y: ");  showList(y);

  printf("\nModifying the first element in x and y to 9 does not change z ...\n");
  x->value = 9;
  y->value = 9;
  printf("List x: ");  showList(x);
  printf("List y: ");  showList(y);
  printf("List z: ");  showList(z);

  printf("\nNow, in-place reversal of z ...\n");
  zz = reverse(z);
  printf("List zz: ");  showList(zz);
  printf("\nBecause reversal is in-place, z is garbage after this operation (well, it's a pointer to the last element) ...\n");
  printf("List z: ");  showList(z);

  return 0;
}

/* ----------------------------------------------------------------------------- */
/* Aux fcts */

void showArr (int len, int *arr) {
  int i;
  printf("Array at %p: \n", arr);
  for (i=0; i<len; i++) {
    printf("%d: %d\n", i, arr[i]);
  }
}

/* ----------------------------------------------------------------------------- */
/* List data type */

/* Constructor fct ------------------------------------------------------- */

/* generate a list from an array */
/* Adv Exercise: modify the code to eliminate the code 
                 duplication in if and while */
node *mkList(int len, int *arr) {
  int i;
  node *curr, *last, *root;
  if (len>0) {
    last = (node*) malloc(1*sizeof(node));
    last->value = arr[0];
    root = last;
  } else {
    return NULL;
  }
 
  for (i=0; i<len-1; i++) {
    curr = (node*) malloc(1*sizeof(node));
    curr->value = arr[i+1];
    last->next = curr;
    last = curr;
  }
  last->next = NULL;
  return root;
}

/* Printing fct ------------------------------------------------------- */

void showList(node *x) {
  if (x==NULL) {
    printf("List at %p: NIL\n", x);
    return ;
  } else {
    printf("List at %p: %d", x, x->value);
    x=x->next;
  }
  while (x!=NULL) { 
    printf(", %d", x->value);
    x = x->next;
  }
  printf("\n");
}

/* Worker fcts ------------------------------------------------------- */

/* 3 versions of append, to varying degree of safety */

/* this modifies x and shares y with the result */
/* REQUIRES: x!=NULL */
node *appendModify(node *x, node *y) {
  node *root = x;
  while (x->next!=NULL) {
    x=x->next;
  }
  x->next=y;
  return root;
}

/* this shares y with the result */
/* REQUIRES: x!=NULL */
node *appendShare(node *x, node *y) {
  node *root = NULL;
  node *curr = NULL, *last = NULL;
  while (x!=NULL) {
    curr = (node*) malloc(1*sizeof(node));
    *curr = *x; 
    if (root==NULL) { root = curr; }
    x = x->next;
    if (last!=NULL) last->next = curr;
    last = curr;
  }
  curr->next=y;
  return root;
}

/* a safe version without sharing or modification of input */
/* REQUIRES: x!=NULL */
node *append(node *x, node *y) {
  node *root = NULL;
  node *curr = NULL, *last = NULL;
  while (x!=NULL) {
    curr = (node*) malloc(1*sizeof(node));
    *curr = *x; 
    if (root==NULL) { root = curr; }
    x = x->next;
    if (last!=NULL) last->next = curr;
    last = curr;
  }
  /* Adv Exercise: avoid this code duplication! */
  while (y!=NULL) {
    curr = (node*) malloc(1*sizeof(node));
    *curr = *y; 
    y = y->next;
    if (last!=NULL) last->next = curr;
    last = curr;
  }
  curr->next=NULL;
  return root;
}

/* in-place list reversal */
/* REQUIRES: x!=NULL */
node *reverse(node *x) {
  node *last = NULL, *t;
  while (x!=NULL) {
    t = x->next;
    x->next = last; 
    last = x;
    x = t;
  }
  return last;
}