sortedlist needs a non-throwing index()

[erikfrey]

I'd like to know the index at which an item would be inserted - similar to bisect_left - I can't find a way to do this without getting ValueError.

[DanielStutzbach]

I agree that this is a good feature idea. Could you write a patch?

[erikfrey]

I'm pretty short on free time right now - but if I do, what do you suggest the method name be?

[DanielStutzbach]

Why don't we mirror the bisect module's names: .bisect_left and .bisect_right, with .bisect aliasing .bisect_right?

http://docs.python.org/library/bisect.html

[ghost]

I'd like to have this feature too. If nobody's working on it, I think I'd get started (to un-rust my leet C skills :) )

[erikfrey]

Please do!

[ghost]

After having started to work on it, it looks like my leet C skills won't be required...

I have a question and I'm wondering if Daniel can answer: Why a python bisect implementation instead of the stdlib module which is implemented in C? The internal representation is already in the form of (key, value), which would work for stdlib bisect. Am I missing something?

[DanielStutzbach]

That would work much of the time, but it won't work if the value type cannot be safely compared and the keys are equal.

For example, suppose that the value is a complex number and that the key is the magnitude of the complex number. Then, the following comparison throws a TypeError: (5, complex(2, 3)) < (5, complex(3, 2))

[ghost]

Oh yeah, true. Maybe that a solution would be that instead of using a simple tuple for the internal representation, we could use a tuple subclass for which the comparison methods only consider the first element of the tuple.

[DanielStutzbach]

I have a bit of conundrum. I made sortedlist insert equal elements to the left of the other equal elements, but the standard library's bisect.insort inserts equal elements to the right of other equal elements. How would you feel if I change the behavior of sortedlist to match bisect.insort?

[ghost]

??? the bisect module has both left and right variants (insort_left) available, I don't see where the problem is.

[DanielStutzbach]

It has insort_left() and insort_right(), but it also insort() which is an alias for insort_right() not insort_left().

(and likewise bisect() is an alias for bisect_right(), not bisect_left()

[ghost]

Oh, I get what you mean now (I hadn't noticed, I though bisect aliased to bisect_left).

I don't know if consistency with stdlib is worth that change in blist. Doing so might break stuff for users (I'm not a user of blist yet as I need the bisect functionality first...).

[DanielStutzbach]

In blist 1.3, bisect_left and bisect_right methods were added to the sortedlist and sortedset family of classes, and to the KeysView class (returned by sorteddict's .keys() method).

Thanks hsoft for the patch!