/**********
 * linked_lists_basics.c
 *
 *  a linked list in C - the basics
 *
 *  See ./linked_list_basics.py for the corresponding Python code.
 *
 *      $ gcc linked_list_basic.c -o linked_list_basic
 *      $ ./linked_list_basic
 *      Linked List : 
 *        <Node value=30 id=0x7fb952405b20 next=0x7fb952405b10 >
 *        <Node value=20 id=0x7fb952405b10 next=0x7fb952405b00 >
 *        <Node value=10 id=0x7fb952405b00 next=0x0 >
 *
 *      Finding its length : 
 *         recursive gives 3 
 *         iterative gives 3 
 *
 *      Popping until empty : 30 20 10 
 *
 * Jim Mahoney | cs.bennington.college | MIT License | March 2021
 *********/

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

// ----  class Node in python  ---------------

typedef struct _node *Node;  // a Node is a pointer to a (struct _node)
struct _node {
  int value;
  Node next;
};

Node newNode(int value){
  Node self = malloc(sizeof(struct _node));
  self->value = value;
  self->next = NULL;
  return self;
}

void printNode(Node self){
  printf("  <Node value=%d id=%p next=%p >\n", self->value, self, self->next);
}

// ----- class LinkedList -----------------

typedef struct _linkedlist *LinkedList;
struct _linkedlist {
  Node begin;
};

LinkedList newLinkedList(){
  LinkedList self = malloc(sizeof(struct _linkedlist));
  self->begin = NULL;
  return self;
}

void push(LinkedList self, Node node){
  // push a node onto a list
  node->next = self->begin;
  self->begin = node;
}

Node pop(LinkedList self){
  // remove and return a node from a list
  Node popped = self->begin;
  if (popped){
    self->begin = popped->next;
    popped->next = NULL;
  }
  return popped;
}

int isEmpty(LinkedList self){
  // return 1 if the list is empty; 0 otherwise
  return self->begin == NULL;
}

void printLinkedList(LinkedList self){
  Node node = self->begin;
  printf("Linked List : \n");
  while (node){
    printNode(node);
    node = node->next;
  }
}

// --- length functions -----------------

int lengthIterative(Node node){
  // Return length of chain of nodes, iterative implementation
  int count = 0;
  while (node){
    count++;
    node = node->next;
  }
  return count;
}

int lengthRecursive(Node node){
  // Return length of chain of nodes, recursive implementation """
  if (!node){
    return 0;
  }
  else {
    return 1 + lengthRecursive(node->next);
  }
}

// --- main --------------------------

int main(){
  int i;
  LinkedList linky;
  int numbers[] = {10, 20, 30};
  
  linky = newLinkedList();
  for (i=0; i<3; i++){
    push(linky, newNode(numbers[i]));
  }
  printLinkedList(linky);
  printf("\n");

  printf("Finding its length : \n");
  printf("  recursive gives %d \n", lengthRecursive(linky->begin));
  printf("  iterative gives %d \n", lengthIterative(linky->begin));
  printf("\n");
    
  printf("Popping until empty : ");
  while (! isEmpty(linky)){
    printf("%d ", pop(linky)->value);
  }
  printf("\n");
  
  return 0;
}