Insert a custom object in a sorted list

Question

I implemented an object with a numerical attribute. I want to keep a list of those objects sorted according to that attribute, without need to run a sort method at each insertion. I took a look to bisect module, but I do not know if I can use it also with an object. What is the best way to do that?

Answer 1

You can do this for your custom object if you implement the __lt__ method, because this is what bisect will use to compare your object.

>>> class Foo(object):
...     def __init__(self, val):
...         self.prop = val # The value to compare
...     def __lt__(self, other):
...         return self.prop < other.prop
...     def __repr__(self):
...         return 'Foo({})'.format(self.prop)
...
>>> sorted_foos = sorted([Foo(7), Foo(1), Foo(3), Foo(9)])
>>> sorted_foos
[Foo(1), Foo(3), Foo(7), Foo(9)]
>>> bisect.insort_left(sorted_foos, Foo(2))
>>> sorted_foos
[Foo(1), Foo(2), Foo(3), Foo(7), Foo(9)]

Answer 2

You may provide a custom implementation of list that override the insert method that make a binary insertion. hose the time to insert an element come from O(1) to O(log2(n)) where n is the number of element in the list.

You may also use an already implemented implementation such as sorted containers [http://www.grantjenks.com/docs/sortedcontainers/].

Anyway, whatever solution you use, you MUST implement comparators methods on your objects ( greater than (__gt__) and lesser than (__lt__) ) that use this numerical attribute to define an order on your objects. Without order, there is no sorting possible.

Here an example :

from sortedcontainers import SortedList

class OrderedObject():

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

    def __gt__(self, other):
        if not isinstance(other,OrderedObject):
            raise Exception("OrderedObject are only comparable to OrderedObject, not to {0}".format(type(other)))
        else:
            return self.value.__gt__(other.value)

    def __lt__(self, other):
        if not isinstance(other,OrderedObject):
            raise Exception("OrderedObject are only comparable to OrderedObject, not to {0}".format(type(other)))
        else:
            return self.value.__lt__(other.value)

    def __repr__(self):
        return "<OrderedObject({0}, {1})>".format(self.id, self.value)

if __name__ == "__main__":
    a = OrderedObject('foo', 1)
    b = OrderedObject('bar', 2)
    c = OrderedObject('-*-', 3)

    mylist = [b,c,a]
    print(mylist)
    mylist.sort()
    print(mylist)

    mylist = SortedList()
    mylist.add(b)
    mylist.add(c)
    mylist.add(a)
    print(mylist)

This give the following results :

[<OrderedObject(bar, 2)>, <OrderedObject(-*-, 3)>, <OrderedObject(foo, 1)>]
[<OrderedObject(foo, 1)>, <OrderedObject(bar, 2)>, <OrderedObject(-*-, 3)>]
SortedList([<OrderedObject(foo, 1)>, <OrderedObject(bar, 2)>, <OrderedObject(-*-, 3)>])

NB : I'm not affiliated to sorted container library in any way

Answer 3

bisect doesn't support keys; read this: http://bugs.python.org/issue4356 and they don't plan to support that either for performance reasons. But I think it should work if you use __gt__, __lt__ etc.