#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
#include <stdint.h>

/**
 * @brief Compares if the integer pointed by a is greater than the one pointed by b
 *
 * @param a
 * @param b
 * @return int >= 0 if a >= b else returns a negative value
 */
static int _cmp_int(const void *a, const void *b)
{
  int x = *((int *)a);
  int y = *((int *)b);
  return x - y;
}

/**
 * A struct representing a node in a priority queue. Each node has a value and a
 * pointer to the next node in the queue.
 */
typedef struct _PQNode
{
  void *a_value;
  struct _PQNode *next;
} PQNode;

/**
 * @brief Add a new node with a_value to the priority queue located at a_head
 * using the function cmp_fn to determine the ordering of the priority queue.
 *
 * @param a_head the head of the priority queue
 * @param a_value the value to be enqueued
 * @param cmp_fn a comparison function to determine the ordering of the priority queue
 * @return PQNode*
 */
PQNode *pq_enqueue(PQNode **a_head, void *a_value, int (*cmp_fn)(const void *, const void *))
{
  // 1. malloc a new PQNode
  // 2. Initialize the new node with a_value and set its next ptr to NULL
  // Now, we need to decide where to insert this new node with "a_value"

  // At a high level, we need to walk the given PQueue; find the right spot by
  // comparing the priority of nodes with the new node that is supposed to be inserted.
  // We will use cmp_fn to compare the priorities.
  // However, there are a few edge cases we need to handle:
  if (*a_head == NULL || cmp_fn == NULL || cmp_fn(a_value, (*a_head)->a_value) < 0)
  {
    // This should be the first node of the list, so set the new node as head of PQueue
  }
  else
  {
    // walk through the PQueue (similar to a linked list) until:
    // either you reach the last element or
    // you find the least element in the (sorted) PQueue with  priority greater than
    // the element being enqueued
    // Think!! How will you manipulate next ptrs to insert a node between two nodes
  }

  // return a pointer to the new PQNode
}

/**
 * @brief Detach the head of the priority queue located at a_head and return it.
 *
 * @param a_head the head of the priority queue
 * @return PQNode*
 */
PQNode *pq_dequeue(PQNode **a_head)
{
  PQNode *removed_PQNode = *a_head;
  // Check if the head is not NULL
  if (removed_PQNode != NULL)
  {
    // 1. if not: appropriately update the new head of the PQueue by updating next ptrs
    // 2. The node being dequeued should not point to the queue any more
  }
  // return the dequeued node
  return removed_PQNode;
}

/**
 * @brief Add a new node with value a_value to the top of the stack located at stack.
 *
 * @param stack a pointer to the first node in the linked list
 * @param a_value the value to be pushed onto the stack
 * @return PQNode*
 */
PQNode *stack_push(PQNode **stack, void *a_value)
{
  // Hint: Similar to pq_enqueue, but the cmp function should simply compare recency!
  // Notice the relevant case in the enqueue operation that does not compare the a_value!
  return pq_enqueue(stack, a_value, NULL);
}

/**
 * @brief Remove the top node from the stack located at stack and return it.
 *
 *
 * @param stack a pointer to the first node in the linked list
 * @return PQNode*
 */
PQNode *stack_pop(PQNode **stack)
{
  // Hint: This function is very similar to pq_dequeue.
}

/**
 * @brief Deallocate all nodes in the linked list starting at a_head.
 *
 * @param a_head the head of the linked list
 */
void destroy_list(PQNode **a_head)
{
  // walk through the list until the end
  while (*a_head != NULL)
  {
    // dequeue the head of the list
    // free the value ptr
    // free the PQNode
  }
}

int main()
{
  PQNode *head = NULL;
  int n1 = 5, n2 = 7, n3 = 6;
  pq_enqueue(&head, &n1, _cmp_int);
  pq_enqueue(&head, &n2, _cmp_int);
  pq_enqueue(&head, &n3, _cmp_int);
  PQNode *first_node = pq_dequeue(&head);
  PQNode *second_node = pq_dequeue(&head);
  PQNode *third_node = pq_dequeue(&head);
  if (*((int *)first_node->a_value) == 5 &&
      *((int *)second_node->a_value) == 6 &&
      *((int *)third_node->a_value) == 7)
  {
    printf("Pass: Successfully enqueued!");
  }

  if (head == NULL)
  {
    printf("Pass: Successfully dequeued!");
  }
  free(first_node);
  free(second_node);
  free(third_node);
}