This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

Author rhettinger
Recipients bls, mark.dickinson, milko.krachounov, rhettinger, tebeka, terry.reedy
Date 2010-04-15.00:30:19
SpamBayes Score 1.71859e-07
Marked as misclassified No
Message-id <1271291423.2.0.552881960464.issue4356@psf.upfronthosting.co.za>
In-reply-to
Content
What would you guys think about adding a class that uses bisect internally so that the keyfunc() never gets called more than once per key?  This could be added to the docs as a cut-and-pastable recipe or it could be added to the module directly:

sd = SortedCollection(iterable, key=keyfunc)
s[i]                  --> getitem at position i
len(s)                --> length
sd.insert_left(item)  --> None
sd.insert_right(item) --> None
sd.find_left(key)     --> item
sd.find_right(key)    --> item
sd.keyfunc            --> the key function 
list(sd)              --> sorted list of items
list(reversed(sd))    --> reverse sorted list of items
s.clear()


The implementation would follow this pattern:

 def insert_left(self, item):
   key = self._keyfunc(item)
   i = bisect_left(self._keys, key)
   self._keys.insert(i, key)
   self._items.insert(i, item)

 def find_left(self, key):
   i = bisect_left(self._keys, key)
   return self._items[i]

 def __iter__(self):
   return iter(self._items)

 def __getitem__(self, i):
   return self._items[i]
History
Date User Action Args
2010-04-15 00:30:23rhettingersetrecipients: + rhettinger, terry.reedy, tebeka, mark.dickinson, milko.krachounov, bls
2010-04-15 00:30:23rhettingersetmessageid: <1271291423.2.0.552881960464.issue4356@psf.upfronthosting.co.za>
2010-04-15 00:30:20rhettingerlinkissue4356 messages
2010-04-15 00:30:19rhettingercreate