Using Queue.priorityqueue, Not Caring About Comparisons

I'm trying to use queue.PriorityQueue in Python 3(.6). I would like to store objects with a given priority. But if two objects have the same priority, I don't mind PriorityQueue.g

Solution 1:

dataclasses is just a convenience method to avoid having to create a lot of boilerplate code.

You don't actually have to create a class. A tuple with a unique counter value too:

from itertools import count

unique=count()

q.put((priority, next(unique), item))

so that ties between equal priority are broken by the integer that follows; because it is always unique the item value is never consulted.

You can also create a class using straight-up rich comparison methods, made simpler with @functools.total_ordering:

from functools import total_ordering

@total_orderingclassPrioritizedItem:
    def__init__(self, priority, item):
        self.priority = priority
        self.item = item

    def__eq__(self, other):
        ifnotisinstance(other, __class__):
            returnNotImplementedreturn self.priority == other.priority

    def__lt__(self, other):
        ifnotisinstance(other, __class__):
            returnNotImplementedreturn self.priority < other.priority

Solution 2:

See priority queue implementation notes - just before the section you quoted (regarding using dataclasses) it tells you how to do it whitout them:

... is to store entries as 3-element list including the priority, an entry count, and the task. The entry count serves as a tie-breaker so that two tasks with the same priority are returned in the order they were added. And since no two entry counts are the same, the tuple comparison will never attempt to directly compare two tasks.

So simply add your items as 3rd element in a tuple (Prio, Count, YourElem) when adding to your queue.

Contreived example:

from queue import PriorityQueue

classCompareError(ValueError): passclassO:
    def__init__(self,n):
        self.n = n

    def__lq__(self):
        raise CompareError

    def__repr__(self): returnstr(self)
    def__str__(self): return self.n

defadd(prioqueue,prio,item):
    """Adds the 'item' with 'prio' to the 'priorqueue' adding a unique value that
    is stored as member of this method 'add.n' which is incremented on each usage."""
    prioqueue.put( (prio, add.n, item))
    add.n += 1# no len() on PrioQueue - we ensure our unique integer via method-param# if you forget to declare this, you get an AttributeError
add.n = 0

h = PriorityQueue()

add(h, 7, O('release product'))
add(h, 1, O('write spec 3'))
add(h, 1, O('write spec 2'))
add(h, 1, O('write spec 1'))
add(h, 3, O('create tests'))

for _ inrange(4):
    item = h.get()
    print(item)

Using h.put( (1, O('write spec 1')) ) leads to

TypeError: '<' not supported between instances of'O' and 'int'`

Using def add(prioqueue,prio,item): pushes triplets as items wich have guaranteed distinct 2nd values so our O()-instances are never used as tie-breaker.

Output:

(1, 2, write spec 3)
(1, 3, write spec 2)
(1, 4, write spec 1)
(3, 5, create tests)

---

see MartijnPieters answer @here for a nicer unique 2nd element.

Solution 3:

Let's assume that we don't want to write a decorator with equivalent functionality to dataclass. The problem is that we don't want to have to define all of the comparison operators in order to make our custom class comparable based on priority. The @functools.total_ordering decorator can help. Excerpt:

Given a class defining one or more rich comparison ordering methods, this class decorator supplies the rest. This simplifies the effort involved in specifying all of the possible rich comparison operations:

The class must define one of __lt__(), __le__(), __gt__(), or __ge__(). In addition, the class should supply an __eq__() method.

Using the provided example:

from functools import total_ordering

@total_orderingclassPrioritizedItem:
    # ...def__eq__(self, other):
        return self.priority == other.priority

    def__lt__(self, other):
        return self.priority < other.priority

Solution 4:

All you need is a wrapper class that implements __lt__ in order for PriorityQueue to work correctly. This is noted here:

The sort routines are guaranteed to use __lt__() when making comparisons between two objects. So, it is easy to add a standard sort order to a class by defining an __lt__() method

It's as simple as something like this

classPriorityElem:def__init__(self, elem_to_wrap):
        self.wrapped_elem = elem_to_wrap

    def__lt__(self, other):
        returnself.wrapped_elem.priority < other.wrapped_elem.priority

If your elements do not have priorities then it's as simple as:

classPriorityElem:def__init__(self, elem_to_wrap, priority):
        self.wrapped_elem = elem_to_wrap
        self.priority = other.priority

    def__lt__(self, other):
        returnself.priority <  other.priority

Now you can use PriorityQueue like so

queue = PriorityQueue()
queue.put(PriorityElem(my_custom_class1, 10))
queue.put(PriorityElem(my_custom_class2, 10))
queue.put(PriorityElem(my_custom_class3, 30))

first_returned_elem = queue.get()
# first_returned_elem is PriorityElem(my_custom_class1, 10)
second_returned_elem = queue.get()
# second_returned_elem is PriorityElem(my_custom_class2, 10)
third_returned_elem = queue.get()
# third_returned_elem is PriorityElem(my_custom_class3, 30)

Getting at your original elements in that case would be as simple as

elem = queue.get().wrapped_elem

Since you don't care about sort stability that's all you need.

Edit: As noted in the comments and confirmed here, heappush is not stable:

unlike sorted(), this implementation is not stable.