I need to maintain a PriorityQueue with some data. The ordering of the data is not the ordering I want maintained in the PriorityQueue (the two different orderings serve different purposes). In fact, the order in which I want elements in the queue is determined by three functions:
1) Scoring function A.
2) Scoring function B.
3) Order in which the elements were added to the queue.
I order to keep this ordering of the queue, I wrote something like the following:
import queue
s = State(...)
id = s.immutableID
pq = queue.PriorityQueue()
counter = 0
priority = (A(s), B(s), counter)
pq.put( (priority, id) )
counter += 1
This shows the rough strategy behind trying to get the PriorityQueue to maintain the order that I want. Later in the code I create several new instances of State, score their priorities, increment the counter, and loop.
If I do this, will it basically use the "dictionary ordering" on tuples? That is to say, will the PriorityQueue determine that all elements with an earlier first coordinate are inserted earliest, and of the ties, all elements with an earlier second coordinate are inserted earliest, and so on?
I'm pretty sure that the answer is "yes" based on the documentation, since it uses the sort function and sort uses <= and <= uses the dictionary ordering on tuples. But just in case any one of those inferences is missing something I should be aware of, I wanted to ask.
Yes, the order will be based upon the complex sort of tuples which you called "dictionary ordering". According to the docs on PriorityQueue,
The lowest valued entries are retrieved first (the lowest valued entry is the one returned by
sorted(list(entries))[0]).
and sorting, particularly list.sort() and sorted(), is guaranteed to be stable.