heapq push TypeError: '<' not supported between instances

Question

I am working in python and I have some problem with heapq. When I push an element into the heap I receive this error :

TypeError: '<' not supported between instances of 'Point' and 'Point'

Point is my internal class. I push a tuple formed by (float,Point), in according with documentation, heapq should use float as a key, but it doesn't. To be more precise sometimes use float but not always. What is the problem?

Answer 1

heapq will use the <= operator on whatever stuff you put into it.

Tuples are compared position by position: the first item of the first tuple is compared to the first item of the second tuple; if they are not equal (i.e. the first is greater or smaller than the second) then that's the result of the comparison, else the second item is considered, then the third and so on.

If the first item of each tuple is unique, comparison will always happen only on the first item:

>>> x = (1, object())
>>> y = (2, object())
>>> x <= y
True

(note: I used object() to create an anonymous object, which does not implement the comparison operators)

The problem appears when the first item of the tuple is not unique (i.e. the first tuple item will be equal for some pair of tuples), then comparison will have to compare the second item of the tuple:

>>> z = (1, object())
>>> x <= z
Traceback (most recent call last):
  File "<input>", line 1, in <module>
    x <= z
TypeError: '<=' not supported between instances of 'object' and 'object'

So, either you implement comparison operators in your object:

• __lt__(self, other) for <
• __le__(self, other) for <=
• (optional) __gt__(self, other) for >
• (optional) __ge__(self, other) for >=

or otherwise you make sure the preceding items in the tuple are always comparable and together are unique.

For example, you could add the object's id to the tuple, so that your tuples become:

(priority, id(obj), obj)

as the object id is unique. (beware: you'll hit this problem again if adding two instances of the same object with the same priority).

Answer 2

You need to define relative comparison operations in your Point class. This means:

__lt__(self, other) for <

__le__(self,other) for <=

and optionaly

__gt__(self, other) for >

__ge__(self, other) for >=.

The last two are optional because, if not specified, negation of le and lt are taken.

General structure of these methods is __name__(self, other), where other is object which will be compared to the self. Also, they return True or False.

You can also define __eq__ instead of all four above, which works like comparator in Java. This method should return positive integer if self is greater than other, 0 in case they are equal and negative integer if other is larger than self.