/*
 * priority queue by singly linked list
*/
#include <stdio.h>
#include <malloc.h>

typedef struct node {
  int data;
  int priority;
  struct node *next;
} qnode;

void enqueue(qnode **, int, int);
void dequeue(qnode **);
qnode *peek(qnode *);
void clean(qnode **);
void display(qnode *);

int main() {
  qnode *start = NULL;
  int i;
  for (i = 1; i < 5; i++) {
    enqueue(&start, i, 5 - i);
  }
  printf("Display all:\n");  
  display(start);
  
  printf("Dequeue:\n");  
  dequeue(&start);
  
  qnode *p = peek(start);
  printf("Peek: data=%d;priority=%d\n", p->data, p->priority);  
  
  printf("Display all:\n");  
  display(start);
  clean(&start);

  return 0;
}

void enqueue(qnode **startp, int val, int pri) {
  qnode *ptr = (qnode *) malloc(sizeof(qnode));
  ptr->data = val;
  ptr->priority = pri;
  
  if (*startp == NULL || pri < (*startp)->priority) {
    ptr->next = *startp;
    *startp = ptr;
  } else {
    qnode *p = *startp;
    while (p->next != NULL && p->next->priority <= pri)
      p = p->next;
    
	ptr->next = p->next;
    p->next = ptr;
  }
}

void dequeue(qnode **startp) {
  if (*startp == NULL) {
    printf("\nUNDERFLOW");
  } else {
    qnode *p = *startp;
	*startp = p->next;
	free(p);
  }
}

void dequeue_low(qnode **startp) {
  if (*startp == NULL) {
    printf("\nUNDERFLOW");
  } else {
    qnode *p = *startp, *prev = NULL;
    while (p->next != NULL) {
      prev = p;
      p = p->next;
    }
    
    if (prev == NULL) {
      free(p);
      *startp = NULL;
    } else {
      prev->next = NULL;
      free(p);
    }
  }
}

qnode *peek(qnode *start) {
  return start;
}

void display(qnode *start) {
  qnode *ptr;
  ptr = start;
  if (start == NULL)
    printf("\nQUEUE IS EMPTY");
  else {
    while (ptr != NULL) {
      printf("%d[priority=%d]\n", ptr->data, ptr->priority);
      ptr = ptr->next;
    }
  }
}

void clean(qnode **startp) {
  if (*startp == NULL) {
    printf("\n UNDERFLOW");
  } else {
    qnode *p = *startp, *temp;
    while (p != NULL) {
      temp = p;
      p = p->next;
      free(temp);
    }
    *startp = NULL;
  }
}

/*
Display all:
4[priority=1]
3[priority=2]
2[priority=3]
1[priority=4]
Dequeue:
Peek: data=3;priority=2
Display all:
3[priority=2]
2[priority=3]
1[priority=4]
*/