From 8b1cfbc49ca89916ddeaad05c346a27b3b38e6f7 Mon Sep 17 00:00:00 2001
From: Kirill Petrashin <kirill8201@yandex.ru>
Date: Thu, 16 Apr 2026 22:29:58 +0300
Subject: Fix ppq_insert order

---
 priority_queue.c | 14 ++++++++++----
 1 file changed, 10 insertions(+), 4 deletions(-)

(limited to 'priority_queue.c')

diff --git a/priority_queue.c b/priority_queue.c
index eae56dd..7a1fa19 100644
--- a/priority_queue.c
+++ b/priority_queue.c
@@ -11,19 +11,21 @@ PositionPQ *ppq_new(Position pos, size_t priority) {
     return ppq;
 }
 
-/* FIXME: URGENT: check the order PLEAES */
 int ppq_insert(PositionPQ **ppq, Position pos, size_t priority) {
     //printf("Inserting %zu %zu\n", pos.x, pos.y);
     PositionPQ *start = *ppq;
 
+    /* If ppq is empty, create one */
     if ((*ppq) == NULL) {
         (*ppq) = ppq_new(pos, priority);
         return PPQ_INSERT_NEW;
     }
 
+    /* The new node */
     PositionPQ *n = ppq_new(pos, priority);
 
-    if (start->priority > priority) {
+    /* If new priority is better than that of the start, insert in the beginning */
+    if (start->priority >= priority) {
         n->next = start;
         start = n;
         *ppq = start;
@@ -31,21 +33,25 @@ int ppq_insert(PositionPQ **ppq, Position pos, size_t priority) {
         return PPQ_INSERT_SUCCESS;
     }
 
+    /* To avoid changing ppq as it's passed as pointed */
     PositionPQ *temp = *ppq;
 
-    /* The '=' is commented out because we want to insert before, for speed. To insert after, uncomment it*/
-    while(temp->next != NULL && temp->next->priority </*=*/ priority) {
+    /* Skip nodes with smaller priority */
+    while(temp->next != NULL && temp->next->priority < priority) {
+        /* Node is already in ppq */
         if (temp->pos.x == pos.x && temp->pos.y == pos.y && temp->priority <= priority) {
             free(n);
             return PPQ_INSERT_ALREADY;
         }
         temp = temp->next;
     }
+    /* Node is already in ppq */
     if (temp->pos.x == pos.x && temp->pos.y == pos.y && temp->priority <= priority) {
         free(n);
         return PPQ_INSERT_ALREADY;
     }
 
+    /* Insert */
     n->next = temp->next;
     temp->next = n;
 
-- 
cgit v1.2.3