python bisect, it is possible to work with descending sorted lists?

Question

How can I use bisect module on lists that are sorted descending? eg.

import bisect

x = [1.0,2.0,3.0,4.0] # normal, ascending
bisect.insort(x,2.5)  # -->  x is [1.0, 2.0, 2.5, 3.0, 4.0]     ok, works fine for ascending list

# however
x = [1.0,2.0,3.0,4.0]
x.reverse()           # -->  x is [4.0, 3.0, 2.0, 1.0]          descending list
bisect.insort(x,2.5)  # -->  x is [4.0, 3.0, 2.0, 1.0, 2.5]     2.5 at end, not what I want really   

The only methods are insort (insort_right) or insort_left - none of which work for me. Any suggestions? thank you

Answer 1

I've never used to the bisect package. But if it only works in ascending order and you're always keeping your list sorted (whether ascending or descending) then you could simply sort beforehand and then invert (if you want to keep it descending).

x.sort() bisect.insort(x,2.5) x.reverse()

Obviously more a hack then a real solution but at least it would work.

Answer 2

Probably the easiest thing is to borrow the code from the library and make your own version

def reverse_insort(a, x, lo=0, hi=None):
    """Insert item x in list a, and keep it reverse-sorted assuming a
    is reverse-sorted.

    If x is already in a, insert it to the right of the rightmost x.

    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """
    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if x > a[mid]: hi = mid
        else: lo = mid+1
    a.insert(lo, x)

Answer 3

From the documentation:

Unlike the sorted() function, it does not make sense for the bisect() functions to have key or reversed arguments because that would lead to an inefficent design (successive calls to bisect functions would not “remember” all of the previous key lookups).

Therefore, if you have a list with inverse order, then you are out of luck.

The main usecase for bisect is the efficient update of an already ordered list.
You may want either to change the data format of your list (e.g. maintaining it in direct order as much as possible, and then reversing it at the very end), either to implement your own version of bisect.
Or, if you are not in the main usecase, you can opt not to use it at all, e.g. by inserting all elements and then sorting them at the very end.