#ifndef DMCGRATH_LINKED_LIST_H
#define DMCGRATH_LINKED_LIST_H


/*!
 * A struct which represents each node within the list.  Note that
 * this node is suitable for a doubly linked list structure.
 */
struct node{
  /*! Pointer to the next item in the list */
  struct node *next; 
        
  /*! Pointer to the previous item in the list */
  struct node *previous; 
        
  /*! Float value used to store actual data within the list */
  float data; 
};


/*!
 * A funtion to add the value to a given location in the list  
 * @param head - the head of the list
 * @param value - the data to store in the list
 * @param location - the location to store the value: 0 for tail, 
 *                   location < 0 for backwards FROM TAIL, 
 *                   location > 0 for forwards FROM HEAD
 */
struct node* add_value(struct node* head, float value, int location){
  struct node *tmp;
  struct node *cursor;
        
  if (head == NULL){
    /* this means the list is empty, so just create a node, and add the value to it */
    head = (struct node*) malloc(sizeof(struct node));
                
    /* error check */
    if (head == NULL) return head;    
                
    head->data = value;
    head->next = head;
    head->previous = head;
    return head;
  }else{
    /* find the new location--since it's circular, just loop over that many times */
    cursor = head;
    if (location > 0){
      /* if value is positive, move forwards */
      for (int i = 0; i < location; ++i){
	cursor = cursor->next;
      }
    } else if (location < 0){
      /* else move backwards */
      location *= -1;
      cursor = head->previous;
      for (int i = 0; i < location; ++i){
	cursor = cursor->previous;
      }
    }
                
    /* insert the new node in the correct location */
    tmp = (struct node*) malloc(sizeof(struct node));
                
    /* error check */
    if (tmp == NULL) return tmp;
                
    tmp->data = value;
    tmp->next = cursor;
    tmp->previous = cursor->previous;
    cursor->previous->next = tmp;
    cursor->previous = tmp;
  }
  return head;
}

/*!
 *  Add to the tail of the list, by calling add_value with position 0
 */
struct node* add_tail(struct node *head, float value){
  return add_value(head, value, 0);
}

/*!
 * return the value stored at head
 * @param head - the head of the list
 */
float head_value(struct node *head){
  return head->data;
}

/*!
 * return the value stored at tail
 * @param head - the head of the list
 */
float tail_value(struct node *head){
  return head->previous->data;
}

/*!
 * Return the nth value in the list, modulo the length
 * returns FLT_EPSILON on head == NULL
 * @param head - the head of the list
 * @param location - the location to store the value: 0 for tail, 
 *                   location < 0 for backwards FROM TAIL, 
 *                   location > 0 for forwards FROM HEAD
 */
float nth_value(struct node *head, int location){
  if (head == NULL){
    return FLT_EPSILON;
  }
        
  struct node *cursor = head;
        
  if (location > 0){
    /* if value is positive, move forwards */
    for (int i = 0; i < location; ++i){
      cursor = cursor->next;
    }
  } else{
    /* else move backwards */
    cursor = head->previous;
    location *= -1;
    for (int i = 0; i < location; ++i){
      cursor = cursor->previous;
    }
  }
        
  return cursor->data;
}

/*! 
 * Get the length of the list
 * @param head - the head of the list
 */
int list_length(struct node *head){
  struct node *cursor = head;
  if (cursor == NULL) return 0;
  int length = 1;
        
  /* count the first value, then loop until you return */
  cursor = cursor->next;
  while(cursor != head){
    ++length;
    cursor = cursor->next;
  }
  return length;  
}


/*!
 * Print the list, in order
 * Make sure not to print more than once
 * @param head - the head of the list
 */
void print_list(struct node *head){
  struct node *cursor = head;
  int length = list_length(head);
        
  if (length == 0) return;
        
  //if (cursor == NULL) return;
        
  for (; length > 0; --length){
    printf("%f%s", cursor->data, (cursor==head->previous) ? "\n" : ", ");
    cursor = cursor->next;
  }
  /* end the line after the final element */
  //  printf("%f\n", cursor->data);
        
  return;
}


/*!
 * remove the nth element from the list, modulo the length
 * and return the pointer to the node
 * @param head - the head of the list
 * @param location - the location to store the value: 0 for tail, 
 *                   location < 0 for backwards FROM TAIL, 
 *                   location > 0 for forwards FROM HEAD
 * @param nth - location to store the removed value
 */
struct node* pop_nth(struct node *head, int location, struct node *nth){
  if (head == NULL){
    return head;
  }
        
  struct node *cursor = head;
        
  if (location >= 0){
    for (int i = 0; i < location; ++i){
      cursor = cursor->next;
    }
  } else{
    location *= -1;
    for (int i = 0; i < location; ++i){
      cursor = cursor->previous;
    }
  }
        
  /* remove the node */
        
  if (cursor == head){
    /* if the length is 1, this is still head, but that's ok */
    head = cursor->next;
  }
        
  if (list_length(head) > 1){
    /* if the length of the list is greater than 1, remove the node */
    cursor->next->previous = cursor->previous;
    cursor->previous->next = cursor->next;
  } else{
    /* otherwise it's just the head */
    head = NULL;
  }  
        
        
  /* copy the deleted node to a new location */
  *nth = *cursor;
        
  /* free up the node */
  free(cursor);
        
  return head;
}

/*!
 * delete the whole list, making use of pop_nth
 * @param head - the head of the list
 */
struct node* delete_list(struct node *head){
  struct node nth;
        
  while(list_length(head) != 0){
    head = pop_nth(head, list_length(head), &nth);
  }
        
  return head;
}


#endif