/*******
 * linked_list.c
 *
 * See also ./linked_list.h which has the headers 
 * including the typdedef structure defintions.
 *
 * See the comments in ./linked_list.py; this is essentially
 * the same but implemented in C rather than Python.
 *
 * Jim Mahoney | cs.bennington.college | MIT License | March 2021
 ******/

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

// ---- Node --------

/* // in linked_list.h 
typedef struct _mynode *mynode;
struct _mynode {  // named "mynode" so I can use "node" as a variable name.
  int value;
  mynode prev;
  mynode next;
};
*/

mynode new_mynode(int value){
  mynode node = malloc(sizeof(struct _mynode));
  node->value = value;
  node->prev = NULL;
  node->next = NULL;
  return node;
}

void print_node(mynode self){
  // print details of node properties
  printf("  <Node value=%d ", self->value);
  if (self->prev){
    printf("prev=%p ", self->prev);
  }
  else {
    printf("prev=%-14s ", "NULL");
  }
  printf("self=%p ", self);
  if (self->next){
    printf("next=%p ", self->next);    
  }
  else {
    printf("next=%-14s ", "NULL");    
  }
  printf(" >\n");
}

// ---- size functions - recursive and iterative ------------

int size_recursive(mynode node){
  // return size of linked list from this node forward, recursively """
  // i.e. implemented by calling this same function again.
  if (node == NULL){
    return 0;
  }
  else {
    return 1 + size_recursive(node->next);
  }
}

int size_iterative(mynode node){
  // return size of linked list from this node forward, iteratively """
  // i.e. implemented with an iterative explicit loop.
  int count = 0;
  while (node){
    count++;
    node = node->next;
  }
  return count;
}

// ---- linked list --------------------------------

/* // in linked_list.h
typedef struct _linkedlist *linkedlist;
struct _linkedlist {
  mynode begin;
  mynode end;
  int length;
};
*/

linkedlist new_linkedlist(){
  // create, initialize, and return a new linked list
  linkedlist list = malloc(sizeof(struct _linkedlist));
  list->begin = NULL;
  list->end = NULL;
  list->length = 0;
  return list;
}

int length(linkedlist self){
  // return length of list using updated-as-we go property
  return self->length;
}

int is_empty(linkedlist self){
  // return false (i.e. 0) if empty otherwise true (i.e 1)
  return self->begin == NULL;
}

void push_end(linkedlist self, mynode node){
  // push node onto the end of the list
  if (is_empty(self)){
    self->begin = node;
    self->end = node;
  }
  else {
    self->end->next = node;
    node->prev = self->end;
    self->end = node;
  }
  self->length = self->length += 1;   // or just self->length++
}

void push_begin(linkedlist self, mynode node){
  // push node onto the begin of the list
  if (is_empty(self)){
    self->begin = self->end = node; 
  }
  else {
    self->begin->prev = node;
    node->next = self->begin;
    self->begin = node;
  }
  self->length = self->length += 1;   // or just self->length++
}

void push_end_value(linkedlist self, int value){
  // create a node with given value; add to end of the list
  mynode node = new_mynode(value);
  push_end(self, node);
}

void push_begin_value(linkedlist self, int value){
  // create a node with given value; add to begin of the list
  push_begin(self, new_mynode(value));
}

mynode pop_end(linkedlist self){
  // remove and return the (rightmost) end node
  mynode popped;
  if (! self->end){
    return NULL;
  }
  else {
    self->length -= 1;
    popped = self->end;
    self->end = popped->prev;
    if (self->end){
      self->end->next = NULL;
    }
    else {
      self->begin = NULL; // in case list is now empty
    }
    popped->prev = NULL;; // its no longer in the list
    return popped;
  }
}

mynode pop_begin(linkedlist self){
  // remove and return the (leftmost) begin node
  mynode popped;
  if (! self->begin){
    return NULL;
  }
  else {
    self->length -= 1;
    popped = self->begin;
    self->begin = popped->next;
    if (self->begin){
      self->begin->prev = NULL;
    }
    else {
      self->end = NULL;   // in case list is now empty
    }
    popped->next = NULL;; // its no longer in the list
    return popped;
  }
}

int pop_begin_value(linkedlist self){
  return pop_begin(self)->value;
}

int pop_end_value(linkedlist self){
  return pop_end(self)->value;
}

void insert_after(linkedlist self, mynode new_node, mynode node){
  mynode old_next;
  // insert a new node into the list after a given node """
  // The links that need to be rearranged are :
  // 2 previous links :   (node => old_next) , (node <= old_next)
  // 4 new links :        (node => new), (node <= new)
  //                      (new => old_next), (new <= old_next)
  self->length += 1;
  old_next = node->next;
  node->next = new_node;                      //  node => new
  new_node->prev = node;                      //  node <= new
  new_node->next = old_next;                  //  new  => old
  if (old_next) old_next->prev = new_node;    //  new  <= old
  if (self->end == node) self->end = new_node;
}

mynode find(linkedlist self, int value){
  mynode node;
  // return the node with the given value, or NULL if not found.
  // ... just for fun, implemented by walking backwards from the end.
  if (! is_empty(self)){
    node = self->end;
    while (node){
      if (node->value == value) return node;
      node = node->prev;
    }
  }
  return NULL; // empy list, or couldn't find value.
}

void print_list(linkedlist self){
  // print values of a list as i.e. "(1 2 3)"
  mynode node = self->begin;
  if (is_empty(self)){
    printf("()\n");
  }
  else {
    printf("(");
    while (node){
      printf("%d ", node->value);
      node = node->next;
    }
  }
  printf(")\n");
}

void print_list_details(linkedlist self){
  // print details of list and all its nodes
  mynode node = self->begin;
  printf("Linked list with length %d : \n", self->length);
  while (node) {
    print_node(node);
    node = node->next;
  }
}

linkedlist new_counting_list(int size){
  // return a linked list with values 1, 2, ..., size.
  linkedlist the_list = new_linkedlist();
  int i;
  for (i=1; i<=size; i++) push_end_value(the_list, i);
  return the_list;
}

// ---- tests ----

void ok(int boolean, char* message){
  // print "ok ..." or "NOT OK ..." for a boolean test
  if (boolean){
    printf("ok       ");
  }
  else {
    printf("NOT OK   ");
  }
  printf("%s\n", message);
}

void linked_list_tests(){
  // test and print results
  linkedlist numbers, singlet;
  mynode two, three, between, root, popped;
  
  ok(1==2, "1 == 2");   // a test that fails on purpose.

  numbers = new_counting_list(4);
  ok(numbers->begin->value == 1, "begin value of (1 2 3 4) is 1");
  ok(numbers->end->value == 4, "end value of (1 2 3 4) is 4");

  two = find(numbers, 2);
  ok(two->value == 2,"find node with given value");

  insert_after(numbers, new_mynode(100), two);
  between = find(numbers, 100);
  three = find(numbers, 3);
  ok(two->next == between && between->prev == two &&
     between->next == three && three->prev == between,
     "insert_after, find give nodes with consistent pointers ");

  root = numbers->begin;
  ok(size_recursive(root) == 5, "size recursive");
  ok(size_iterative(root) == 5, "size iterative");

  popped = pop_begin(numbers);
  ok(popped->value == 1 &&
     popped->prev == NULL &&
     popped->next == NULL, "pop begin gives node without dangling pointers");

  popped = pop_end(numbers);
  ok(popped->value == 4 &&
     popped->prev == NULL &&
     popped->next == NULL, "pop end gives node without dangling pointers");
  
  ok(find(numbers, 100)->value == 100, "find still works after pop_end");

  singlet = new_counting_list(1);
  pop_end(singlet);
  ok(length(singlet) == 0 &&
     singlet->begin == NULL &&
     singlet->end == NULL,  "pop_end to empty list");
  
}

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

/*

// See linked_list_standaline.c , which has main()
// and can be run as a standalone program.

int main(){
  linkedlist numbers = new_counting_list(3);
  print_list_details(numbers);
  linked_list_tests();
  return 0;
}

*/