[Python-Dev] PEP 372 -- Adding an ordered directory to collections ready for pronouncement

[Lie Ryan]

Terry Reedy wrote:
> Lie Ryan wrote:
> 
>> Isn't ordered dictionary essentially also an "always sorted" 
>> container? It is always sorted depending on the order of insertion? I 
>> can't see any technical reason why the data structure can't 
>> accommodate them both. Can you point me to a discussion on this?
> 
> Appending an item at the end of a sequence is O(1), no search required. 
>  Inserting an item at a random 'sorted' point requires at best an 
> O(logN) search.  Insertion itself is O(1) to O(N) depending on the 
> structure.

Yeah, but with a proper algorithm[1] it is possible to get a O(1) append 
(which is the characteristic we want for insertion order dictionary, 
while falling back to O(log n) if we explicitly give comparer function 
(or comparison key extractor).

[1] The insertion algorithm will test for where to insert from the end 
of the list. This way, insertion-order dict will still be O(1) (with an 
increased constant), else if custom order is specified insertion it will 
be O(n)

#UNTESTED BECAUSE I DON'T HAVE PYTHON CURRENTLY

# Note that it derives from OrderDict
class MyOrderDict(OrderDict):
     def __init__(*args, **kwds):
         if len(args) > 2:
             raise TypeError('expected at most 2 arguments')
         if len(args) == 2:
             self._cmp, args = args[0], args[1:]
         else:
             self._cmp = lambda a, b: True
         if not hasattr(self, '_keys'):
             self._keys = []
         self.update(*args, **kwds)

     def __setitem__(self, key, value):
         if key not in self:
             self._key.append(None)
             for i, k in enumerate(reversed(self._key)):
                 i = -i - 1
                 if self._cmp((k, self[k]), (key, value)):
                     self._key[i], self._key[i - 1] = k, key
                 else:
                     self._key[i] = k
         dict.__setitem__(self, key, value)