[ python-Bugs-1619060 ] bisect on presorted list

[SourceForge.net]

Bugs item #1619060, was opened at 2006-12-19 16:14
Message generated for change (Comment added) made by rhettinger
You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=105470&aid=1619060&group_id=5470

Please note that this message will contain a full copy of the comment thread,
including the initial issue submission, for this request,
not just the latest update.
Category: Extension Modules
Group: Python 2.6
Status: Open
Resolution: None
Priority: 5
Private: No
Submitted By: Jeffrey C. Jacobs (timehorse)
Assigned to: Nobody/Anonymous (nobody)
Summary: bisect on presorted list

Initial Comment:
The python and c implementation of bisect do not support custom-sorted lists using the list.sort method.

In order to support an arbitrarily sorted list via sort(cmp, key, reverse), I have added 3 corresponding parameters to the bisect methods for bisection and insort (insert-sorted) corresponding to the parameters in sort.  This would be useful if a list is initially sorted by its sort method and then the client wishes to maintain the sort order (or reverse-sort order) while inserting an element.  In this case, being able to use the same, arbitrary binary function cmp, unary function key and boolean reverse flag to preserve the list order.

The change imposes 3 new branch conditions and potential no-op function calls for when key is None.  I have here implemented and partially tested the python implementation and if someone besides me would find this useful, I will update the _bisectmodule.c for this change as well.

The Heap functions may also find use of an arbitrary predicate function so I may look at that later, but because bisect goes hand in hand with sorting, I wanted to tackle that first.

----------------------------------------------------------------------

>Comment By: Raymond Hettinger (rhettinger)
Date: 2006-12-19 16:43

Message:
Logged In: YES 
user_id=80475
Originator: NO

I'm -1 on this patch.  At first blush it would seem nice to progagate
sort's notion of a key= function; however, sort() is an all at once
operation that can guarantee the function gets called only once per key. 
In contrast, bisect() is more granualar so consecutive calls may need to
invoke the same key= function again and again.  This is almost always the
the-wrong-way-to-do-it (the key function should be precomputed and either
stored separately or follow a decorate-sort pattern).  By including custom
sorting in bisect's API we would be diverting users away from better
approaches.

A better idea would be to create a recipe for a SortedList class that
performed pre-calculated custom keys upon insertion and maintained an
internal, decorated list.

----------------------------------------------------------------------

You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=105470&aid=1619060&group_id=5470