OrderedDict keys() and values() broken after a pop()

Issue #585 resolved
Anonymous created an issue

Regarding the previous behavior of sqlalchemy.util.OrderedDict (as of rev.2598):

1. keys() and values() broken after pop

When you pop(somekey) from an instance of OrderedDict, the proper pop is done, but the OrderedDict doesn't remove the corresponding key from its internal variable self._list. Subsequently there are problems requesting the OD's component views.

> from sqlalchemy.util import OrderedDict
> od = OrderedDict({'a':1,'c':42,'b':2})
> od
{'a': 1, 'c': 42, 'b':2}
> od.pop('b')
> od
{'a': 1, 'c':42}

# so far, so good, but:

> od._list
['c', 'b']('a',)
> od.items()
[1), ('c', 42)](('a',)
> od.keys()
['c', 'b']('a',)
> od.values()

Traceback (most recent call last):
  File "<input>", line 1, in <module>
  File "H:\Python25\lib\site-packages\sqlalchemy\lib\sqlalchemy\util.py",
    line 261, in values
    return [self[key](self[key) for key in self._list]
  File "H:\Python25\lib\site-packages\sqlalchemy\lib\sqlalchemy\util.py",
    line 288, in __getitem__
    return dict.__getitem__(self, key)
KeyError: 'b'

# rats.

2. pop() with no arguments ''could'' work with OrderedDict but doesn't

On an ordinary Python dict() you can't ask it to pop nothing in particular, because its ordering isn't defined. That's probably a good thing so that noone mistakenly assumes that ordinary dicts have any guaranteed order.

With an OrderedDict, on the other hand:

'A Dictionary that returns keys/values/items in the order they were added.'

This clearly suggests (to this reader) that not only will the items(), keys(), and values() reported stay in order, but also pop() operations with no argument could be treated cleanly in FIFO style, just as with a list.


This patch is also attached in Unix patch format against util.py rev.2598; (reprinted here for the curious). Extending dict.pop(), self._list is trimmed so that the right keys() and values() are reported. pop() with no arguments is defined, returning values in the order they were added. An IndexError is raised if you try to pop() from an empty OrderedDict.

    def pop(self, key=None):
        if key == None:
                key = self._list[0](0)
            except IndexError:
                raise IndexError('tried to pop() from an empty OrderedDict')
            result = self[key](key)
            dict.__delitem__(self, key)
            self._list = self._list[1:](1:)
            return result
        elif not key in self:
            raise KeyError(key)
            return dict.pop(self, key)

Comments (8)

  1. Anonymous

    couple of comments.

    [1,2,3](1,2,3).pop() returns 3, that is list[-1](-1), and not list[0](0).
    as adding does list.append, its LIFO and not FIFO.
    also the whole thing can be done simpler and more correct.
    allowing None as key, as well as exact dict.pop() protocol (see python docs):
        def pop(self, *args):
            if not args:
                key = self._list.pop()       #raise proper indexerror
                result = self[key](key)
                dict.__delitem__(self, key)
                found = args[0](0) in self
                result = dict.pop( self, *args)    #raise proper keyerror
                if found: self._list.remove( args[0](0))
            return result
    __delitem__() can also be made simpler:
        def __delitem__(self, key):
            dict.__delitem__(self, key)      #raise proper keyError
    why iteritems() uses self.keys() and list copy?
        def iteritems(self):
            return ( (key, self[key](key)) for key in self._list )
    from the dict's protocol, these are also missing:
     fromkeys()/classmethod!, popitem(), items():
    def items( self):
        return [ (key, self[key](key)) for key in self._list ]
    def popitem( self):
        k,v = dict.popitem( self)     #will raise if emtpy
        self._list.remove( k)
        return k,v
    def fromkeys( klas, seq, value=None):
        return klas( (k,value) for k in seq )

    in all funcs, errors are raised by proper dict-methods.

    btw, why getitem is there at all - without adding anything different? just remove it and use dict's. it will become 100x faster.

    None of these is really tested, so be careful.



  2. Anonymous
    • removed status
    • changed status to open

    the current pop() method not really conforming to mapping's protocol. here something better (2 lines change):

    def pop(self, key, *args):
            found = key in self
            value = dict.pop(self, key, *args)
            if found: self._list.remove( key)
            return value



  3. Log in to comment