SOLVED Priority Queue deciding to turn into a Stack

Currently I'm trying to make a menu which will display different characters the player has unlocked. Each of these characters have rarities and I would like to sort them in a way where it goes lowest rarity to highest but with all the unlocked characters first then all the locked characters after. The best way I thought to do this was with arrays to store the values and a priority queue to re-order them. However I'm having some issues with the way it is ordered.

So I created a bunch of macros which have the ID of the character and their rarity. Counter-intuitively, the lowest rarity has the highest priority (4) and the highest has the lowest priority (1). This is then taken from the 2D array holding it and put into a priority queue using the following code:
Code:
for (var i = 0; i < array_length(livery_array); i++)
{
    ds_priority_add(livery_queue, i, livery_array[i][1] + (10 * livery_get_unlocked(i)));
    show_message(string(i) + ", " + string(livery_array[i][1] + (10 * livery_get_unlocked(i))));
}
The way this works is it loops through the array containing the values and adds their ID to the queue. The priority is then taken and added by 10 multiplied by if the livery is unlocked. So if it is not unlocked, that function will return 0 hence not adding anything to the priority. If it returns 1, 10 will be added to the priority boosting it to be at the top of the list (For the purposes of trying to get this to work, the function has been changed to always return 1). Checking the show_message contents as it's being added shows they are added in the following order:

ID : Priority
0 : 14
1 : 13
2 : 13
3 : 13
4 : 13
5 : 13
6 : 13
7 : 13
8 : 13
9 : 13
10 : 13
11 : 14
12 : 14
13 : 12
14 : 12
15 : 12
16 : 11

This is correct and exactly as it should be so I know I haven't declared the array incorrectly. Otherwise I would show it too. I also deliberately put IDs 11 and 12 in the wrong place in terms of priority to see if the queue would organise them correctly.
I then used this function to pull them out of the queue and into another array which would then be drawn on screen:
Code:
for (var i = 0; !ds_priority_empty(livery_queue); i++)
{
    livery_ordered[i] = ds_priority_delete_max(livery_queue);
    show_message(string(livery_ordered[i]));
}
ds_priority_clear(livery_queue);
In the for loop I did try both array_length and ds_priority_length and both gave the same result so that's why it's !ds_priority_empty since I thought I'd try that.

With the priorities above you would expect that the output would be as follows:
0, 11, 12, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 13, 14, 15, 16

However when I look at the message the order starts well until it gets to 4:
0, 11, 12, 1, 2, 3, 4, 10, 9, 8, 7, 6, 5, 13, 15, 14, 16

It seems to reverse half way through so instead of being first in first out, turns into a stack and reverses it for some reason and I can't see why since the show_message above confirms they're being added with the correct order and priority. These two bits of code are right next to each other so the queue is never altered outside of this. This is in the create event of a control object so it's not running constantly. I just don't understand why it decides to not be a queue anymore...

I just don't understand why this is happening so I'm hoping someone can see what I can't or tell me that I'm doing it all wrong and there's a much easier way to do this.

Thank you
 

Nidoking

Member
The priorities are equal, so why does it matter what the order is? If the order matters, then they should have different priorities.

From the Manual:
If more than one value has the same priority, then any one of them could be returned in any order, but all other values with the same priority will still be in the queue.
 
I did want to keep them in an order but I didn't know if more than one had the same priority then any one could be returned. I thought that the first in first out rule of queues also applied to priority ones if one or more items have the same priority like in other languages but I guess I'll have to change up my strategy. Thanks anyways!
 
Top