Feature request: SortedList: add_left() + add_right()

[alecov]

Hi Grant,

I've been using your library for some time and I have a few suggestions:

SortedList.bisect_*() returns insertion indexes for elements in the sorted list. However, SortedList.insert() is intentionally left unimplemented, which is an inconsistency.

A common use case for this is to insert elements at the bisect_left() index (whereas add() inserts at bisect_right()).

I believe insert() should be available to the user in the light of "we're all consenting adults and know what we're up to" Python discipline.

Indeed, the user might screw with the structure ordering and this allows the structure to become more of a general list (like native Python's) than a sorted one, but SortedList offers an advantage: it has fast insertions at the middle (akin to blist), so SortedList is still better than Python's list in this regard. It would be up to the caller to decide how the structure will be used.

If you find the above unacceptable, then add add_left() and add_right() functions corresponding to bisect_left() and bisect_right(). (add_left() is more for completude, of course.)

Also, since these functions embed searches, they should actually return the insertion index at which the element was inserted: this is useful to user code and avoids a subsequent bisect_*() or index() to determine that index.

The rationale is straightforward: information originated from costly lookup algorithms should not be discarded and the user ought to have access to them without the need to query the data structure multiple times.

I believe bisect+insert composes better than multiple add functions. This is mostly how data structures operate in standard C++, for example, and they work very well in this regard. add() methods and the like are more like convenience methods which compose two distinct operations (search and insert) in one function call.

Thanks.

[grantjenks]

Insert was provided in a previous major version. It still required the elements remain sorted. It was rarely used and sometimes mislead users to use indexes when they weren’t necessary.

add_left and add_right is reasonable and I think I’ve thought of it myself but wanted to wait for someone to ask for them. What’s your use case?

The insertion index can only be returned if the internal positional index is built (which is not guaranteed).

[alecov]

It still required the elements remain sorted.

This check probably costed a bit. Regardless, I see little point in offering bisects if their indexes cannot really be used as insertion points.

It was rarely used and sometimes mislead users to use indexes when they weren’t necessary.

IMHO this is non-compelling. insert() is really useful and the library is not at fault if users cannot use the functions properly.

add_left and add_right is reasonable and I think I’ve thought of it myself but wanted to wait for someone to ask for them. What’s your use case?

Sometimes business logic makes it needed to insert at the beginning of a same-key tier, instead of at the end. add_left() implements exactly that.

Actual objects being inserted might have distinct values even at the same-key tier (__cmp__ or the key function in SortedKeyList could use only part of the object as key). So the position in which an object gets inserted in matters.

The insertion index can only be returned if the internal positional index is built (which is not guaranteed).

Right. I've checked the source and indeed it is not possible to return it easily in some cases.

[grantjenks]

I like the add left/right functionality but not necessarily those names. I suppose they match the bisect functions but I would’ve made it a parameter. Will need to think on the API