why not bisect options?

[rbossy at jouy.inra.fr]

Quoting Raymond Hettinger <python at rcn.com>:

> [Robert Bossy]
> > I thought it would be useful if insort and consorts* could accept the
> > same options than list.sort, especially key and cmp.
>
> If you're going to do many insertions or searches, wouldn't it be
> *much* more efficient to store your keys in a separate array?
>
> The sort() function guarantees that it calls the key function exactly
> once for each member of the list.  With and bisect/insort, successive
> searches can call the key function over and over again with the same
> value.

I factored your remark into the code. I actually don't have any particular
question about it, that's just an acknowledgment. Though I feel that if one
uses the default key, then an awkward list of twins is stored...



from operator import itemgetter


def identity(x): return x


class Bisect:
    def __init__(self, it, key=identity, cmp=cmp):
        self.lst = [ (key(x),x,) for x in it ]
        self.lst.sort(cmp=cmp, key=itemgetter(0))
        self.key = key
        self.cmp = cmp

    def insort_right(self, x, lo = 0, hi = None):
        if hi is None:
            hi = len(self.lst)
        xk = self.key(x)
        while lo < hi:
            mid = (lo + hi) // 2
            if self.cmp(xk, self.lst[mid][0]) < 0:
                hi = mid
            else:
                lo = mid + 1
        self.lst.insert(lo, (kx,x,))

    # skipped insort_left, bisect_right, bisect_left
    # also skipped the container methods __len__, __getitem__, __iter__


Cheers,
RB