Changing a comparison function to use keys for sorting

Question

I have the following code written in Python 2.6, with a Task class that has an optional due_date:

class Task(models.Model):
    due_date = models.DateField(null = True, blank = True)

    @staticmethod
    def compare_by_due_date(t1, t2):
        return due_date_cmp(t1.due_date, t2.due_date)

def due_date_cmp(t1, t2):
    if t1 is None and t2 is None:
        return 0;
    if t1 is None:
        return 1
    if t2 is None:
        return -1
    return (t1 - t2).days

The reason why I extracted the comparison function outside the class is that I wanted to be able to test it without needing to build Task instances. I use compare_by_due_date in the following code to order tasks by increasing due date, with tasks having no due date at the end of the list:

tasks = Task.objects.all()
tasks.sort(Task.compare_by_due_date)

I understood from this answer on Code Review that I should be able to use keys instead of comparison function? Can you show me how?

It's conventional to use 'is' instead of '==' with None.

Fred Nurk
– Fred Nurk

2011-02-02 20:12:32 +00:00
Commented Feb 2, 2011 at 20:12 — Fred Nurk
– Fred Nurk, Commented Feb 2, 2011 at 20:12

Fred Nurk · Accepted Answer · 2011-02-02 20:30:58Z

4

You can't compare objects of all different types (such as datetime.date to None) even though 2.x does allow more comparisons between different types than 3.x, so the direct comparison of due_dates won't work.

def due_date_key(t):
  return (t.due_date is None, t.due_date)

tasks.sort(key=due_date_key)

This works by chaining the comparison through a tuple, so later items are only considered if earlier items are equal.

edited Feb 2, 2011 at 20:30

answered Feb 2, 2011 at 20:18

Fred Nurk

14.3k4 gold badges40 silver badges63 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Xavier Nodet Over a year ago

I get the 'tuple' idea. Thanks! But it does not work here: None gets sorted before datetime.date, and my need is for the reverse...

Fred Nurk Over a year ago

@XavierNodet: This should sort them later, since False < True for the first item. My previous version tried to be too general, but if only None and datetime.date types are needed, this is simpler.

unutbu · Accepted Answer · 2011-02-02 20:26:17Z

2

It looks like due_date_cmp sorts a list composed of datetime.date and None objects, placing the Nones at the end of the list.

You could do the same using a key which converts None objects to the maximum possible datetime.date object:

old way (using cmp):

import datetime as dt

def due_date_cmp(t1, t2):
    if t1 == None and t2 == None:
        return 0;
    if t1 == None:
        return 1
    if t2 == None:
        return -1
    return (t1 - t2).days


dates=[dt.date(2000,1,1),None,dt.date(1999,1,1),None,dt.date(2002,1,1)]
dates.sort(cmp=due_date_cmp)
print(dates)
# [datetime.date(1999, 1, 1), datetime.date(2000, 1, 1), datetime.date(2002, 1, 1), None, None]

new way (using key):

def due_date_key(t):
    if t is None:
        return dt.date(dt.MAXYEAR,12,31)
    else:
        return t

dates=[dt.date(2000,1,1),None,dt.date(1999,1,1),None,dt.date(2002,1,1)]
dates.sort(key=due_date_key)
print(dates)

# [datetime.date(1999, 1, 1), datetime.date(2000, 1, 1), datetime.date(2002, 1, 1), None, None]

Thus, you might use due_date_key in your code like this:

import operator
class Task(models.Model):
    @property
    def due_date_key(self):
        due_date=self.due_date
        if due_date is None:
            return dt.date(dt.MAXYEAR,12,31)
        else:
            return due_date

tasks = Task.objects.all()
tasks.sort(key=operator.attrgetter('due_date_key'))

edited Feb 2, 2011 at 20:26

answered Feb 2, 2011 at 20:10

unutbu

886k197 gold badges1.9k silver badges1.7k bronze badges

1 Comment

Xavier Nodet Over a year ago

+1 for the way to 'replace None with the largest possible date', and showing how to use operator.attrgetter.

Collectives™ on Stack Overflow

Changing a comparison function to use keys for sorting

2 Answers 2

2 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related