/*

  This file contains a simple double-linked list implementation.

  DISCLAIMER: that there are much better ways to implement
  this data structure.

  Written by Leonardo Tamiano on 2020-11-30.

 */

// ----------------------------------
// -- libraries 

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

// ----------------------------------
// -- data structure

typedef struct node {
  int key;
  struct node *prev, *next;
} node;

// ----------------------------------
// -- function signatures

node *list_init(int k);

node *list_add_head(node *head, int k);
node *_list_add_after_head(node *head, int new_key);
node *list_add_pos(node *head, int new_key, int pos);

node *list_del_head(node *head);

node *list_elem_pos(node *head, int pos);
node *list_elem_key(node *head, int key);

void list_print(node *head);

// ----------------------------------
// -- insertion functions


/**
 * list_init()
 *
 * @k: value to insert for first node of the list
 * 
 * Initializes a list by alocating the first node with the given key.
 */
node *list_init(int k)
{
  node *new_head;

  new_head = malloc(sizeof(node));

  if(!new_head) {
    fprintf(stderr, "Failed to allocate memory during list_innit()\n");
    return NULL;
  }

  new_head->key = k;
  new_head->prev = NULL;
  new_head->next = NULL;  
  
  return new_head;
}

/**
 * list_add_head()
 *
 * @head: ptr to head of the list
 * @new_key: new value to insert
 *
 * inserts the new value before the first element of the list pointed
 * by head. Returns the new head of the list.
 */
node *list_add_head(node *head, int new_key)
{
  node *new_head;

  new_head = malloc(sizeof(node));
  
  if(!new_head) {
    fprintf(stderr, "Failed to allocate memory during list_add_head()\n");     
    return head;
  } 

  // initialize new elem
  new_head->key = new_key;
  new_head->next = head;
  new_head->prev = NULL;

  if(head) {
    head->prev = new_head;
  }

  return new_head;
}

/**
 * _list_add_after_head()
 *
 * @head: ptr to head of the list
 * @new_key: new value to insert
 *
 * inserts the new value right after the head of the list pointed by
 * head. Returns the new head of the list.
 */
node *_list_add_after_head(node *head, int new_key)
{
  node *new_node;

  if(!head) {
    fprintf(stderr, "Cannot add a second element to an empty list!\n"); 
    return head;
  }
  
  new_node = malloc(sizeof(node));
  
  if(!new_node) {
    fprintf(stderr, "Failed to allocate memory during _list_add_after_head()\n"); 
    return head;
  }

  // initialize new node
  new_node->key = new_key;
  new_node->prev = head;
  new_node->next = head->next;

  // if the original list has a second element, update its previous
  // pointer
  if(head->next) {
    head->next->prev = new_node;
  } 

  // now we can update the head's next
  head->next = new_node;

  return head;
}


/**
 * list_add_pos()
 *
 * @head: ptr to head of the list
 * @new_key: new value to insert
 * @pos: position in which to insert the new value
 *
 * inserts the new value at position pos in list pointed
 * by head. Returns the new head of the list.
 */
node *list_add_pos(node *head, int new_key, int pos)
{
  node *elem;
  
  if(pos < 0) {
    fprintf(stderr, "ERROR: negative pos not supported for AddElem()\n");
  } else if(pos == 0) {
    head = list_add_head(head, new_key);
  } else {
    elem = list_elem_pos(head, pos-1);
    _list_add_after_head(elem, new_key);
  }

  return head;
}

// ---------------------
// -- deletion functions


/**
 * list_del_head()
 *
 * @head: ptr to head of the list
 *
 * Deletes the first element of a list and returns the new head of the
 * list.
 */
node *list_del_head(node *head)
{
  node *new_head;

  if(!head) {
    return NULL;
  }

  new_head = head->next;

  if(new_head) {
    new_head->prev = NULL;
  }

  // deallocate mem for old head
  free(head);

  return new_head;
}

// ---------------------
// -- "getter" functions

/**
 * list_elem_pos()
 *
 * @head: ptr to head of the list
 * @pos: position of the element we want to return
 *
 * Returns the element of the list at position pos.
 */
node *list_elem_pos(node *head, int pos)
{
  node *elem;
  
  if (pos < 0) {
    fprintf(stderr, "Cannot have negative position in list_elem_pos()\n");
    return NULL;
  }

  elem = head;
  while(elem != NULL && pos > 0) {
    elem = elem->next;
    pos -= 1;
  }

  if(pos > 0) {
    fprintf(stderr, "Position given is too high in list_elem_pos()\n");
    return NULL;    
  } else {
    return elem;
  }
}

/**
 * list_elem_key()
 *
 * @head: ptr to head of the list
 * @key: key of the element we want to return
 *
 * Returns the first element of the list with the given key.
 */
node *list_elem_key(node *head, int key)
{
  node *elem;

  if(!head) {
    return NULL;
  }

  for(elem = head; elem != NULL; elem = elem->next) {
    if(elem->key == key) {
      break;
    }
  }
  
  return elem;
}

// ---------------------
// -- utils functions

void list_print(node *head)
{
  printf("{ ");
  while(head != NULL) {
    if(head->next != NULL) {
      printf("%d, ", head->key);
    } else {
      printf("%d ", head->key);      
    }
    head = head->next;
  }
  printf("}\n");
}


// ----------------------------------
// -- testing area

// int main(int argc, char **argv)
// {
//   node *l, *s;

//   l = list_init(5);
//   list_add_head(l, 7); // { 7 5 }
//   // l = list_add_head(l, 4); // { 4 7 5 }
//   list_print(l);

//   return 0;
// }