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

deque newEmptyDeque(void);
int isEmpty(deque d);
void printFrontToEnd(deque d);
void insertAfterInDLL(itemtype i, node * nodePtr); /* auxiliary */
void addToFront(itemtype i, deque d);
void addToEnd(itemtype i, deque d);
void printFrontItem(deque d);
void printEndItem(deque d);
itemtype popFrontItem(deque d);
itemtype popEndItem(deque d);
/*----------------------------------------------*/
typedef int itemtype;

struct node {
  struct node * previous;
  itemtype item;
  struct node * next;
};
typedef struct node node;

struct deque {
  node * front;    /* pointer to a dummy node. */
  node * end;      /* pointer to a dummy node. */
};

typedef struct deque deque;

/*----------------------------------------------*/

deque newEmptyDeque(void){
   deque d;
   d.front = malloc(sizeof(node));
   d.end = malloc(sizeof(node));
   (d.front)->next = d.end;
   (d.front)->previous = NULL;
   (d.end)->previous = d.front;
   (d.end)->next = NULL;
   return d;
}

/*----------------------------------------------*/

int isEmpty(deque d){
  return (d.front)->next == d.end;
}

/*----------------------------------------------*/

void printFrontToEnd(deque d){
   node * aux;
   aux = (d.front)->next;
   while( (aux->next) != NULL) {
      printf("%d ", aux->item);
      aux = aux->next;
   }
}

/*----------------------------------------------*/
/* Auxiliary function to insert an item after a given node
   in a doubly linked list.
*/
void insertAfterInDLL(itemtype i, node * nodePtr){
   node * nextPtr; /* next node after *nodePtr. */
   node * newPtr;   /* new node. */
   nextPtr = nodePtr->next;
   newPtr = malloc(sizeof(node));
   newPtr->item = i;
   nodePtr->next = newPtr;
   newPtr->previous = nodePtr;
   newPtr->next = nextPtr;
   nextPtr->previous = newPtr;
}

/*----------------------------------------------*/

void addToFront(itemtype i, deque d){
  insertAfterInDLL(i, d.front);
}

/*----------------------------------------------*/

void addToEnd(itemtype i,deque d){
  insertAfterInDLL(i, (d.end)->previous );
}

/*----------------------------------------------*/

void printFrontItem(deque d){
   node * aux;
   aux = (d.front)->next;
   printf("%d\n ", aux->item);
}

/*----------------------------------------------*/
void printEndItem(deque d){
   node * aux;
   aux = (d.end)->previous;
   printf("%d\n ", aux->item);

}
/*----------------------------------------------*/
itemtype popFrontItem(deque d){
    node * popped;
    node * next;
    itemtype temp;
        popped = d.front->next; // creating node in front of d.front
    next = popped->next; // creating node in front of popped node
    next->previous = d.front; // Pointing next node to point to d.front in previous direction
    temp = popped->item; // put the value of node popped into temp
    free(popped);
    return temp;
}
/*----------------------------------------------*/
itemtype popEndItem(deque d){
    node * popped;
    node * previous;
    itemtype temp;
    popped = d.end->previous;
    previous = popped->previous;
    previous->next = d.end;
    temp = popped->item;
    free(popped);
    return temp;
}