TypeError: '<' not supported between instances of 'State' and 'State' PYTHON 3

Question

I am trying to utilize a PriorityQueue from the queue class. However, i'm having issues putting custom objects into my PQ. I have implemented the __cmp__ function below:

def __cmp__(self, other):
    return (self.priority > other.priority) - (self.priority < other.priority)

I want the PriorityQueue to be sorted by the priority field, as assigned in my init function:

def __init__(self, board, priority=0):
    self.priority = priority
    # Other logic

However, when I run the code to insert a State object into the PQ, I get this error: TypeError: '<' not supported between instances of 'State' and 'State'

Here is the code that runs the PQ.

if op.precond(S):
            new_state = op.state_transf(S)
            if not (OPEN.queue.__contains__(new_state)) and not (new_state in CLOSED):
                GVALUES[Problem.hash(new_state)] = get_distance_value(op, new_state)
                HEUR_VALUES[Problem.hash(new_state)] = get_AStar_value(new_state)
                print("NEW STATE: " + str(new_state))
                OPEN.put(new_state)
                print("OPEN: " + str(OPEN.queue))

Where OPEN is the priorityQueue.

Any help would be greatly appreciated... as it should be pretty straightforward to insert a value into a PQ.

Answer 1

In Python 3 you need to define __lt__ and __eq__ instead of __cmp__.

See https://docs.python.org/3.1/library/stdtypes.html#comparisons.

Answer 2

Instead of __cmp__ you need to implement one of the __lt__, __le__, __gt__, or __ge__ methods and use the functools.total_ordering decorator

functools.total_ordering(cls) 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.

However, a better solution to that would be putting a tuples (priority, state_object) into the queue, as they suggest in docs for PriorityQueue

The lowest valued entries are retrieved first (the lowest valued entry is the one returned by sorted(list(entries))[0]). A typical pattern for entries is a tuple in the form: (priority_number, data).

The pitfall of the first approach is that you can modify priority of items that are already in queue and possibly observe unexpected behavior.

In the second approach this is not an issue, since tuples are immutable.

Answer 3

Expanding on what Sean Fujiwara said, you need to define two functions as follows:

class Widget():
  def __gt__(self, other):
    return self.title > other.title

  def __lt__(self, other):
    return self.title < other.title

  def __init__(self, title):
    self.title = value

In this example, adding the __gt__ __lt__ methods lets us sort by the widget's title.