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

[Former user]

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')
2
> 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:

OrderedDict.__doc__
'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.

Patch

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:
            try:
                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)
        else:
            self._list.remove(key)
            return dict.pop(self, key)

[Former user]

patch to util.py, adds method OrderedDict.pop(), extends dict.pop()

[Former user]

couple of comments.

pop():
[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)
        else:
            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
        self._list.remove(key)

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

@classmethod
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.

svil

[e-mail]

[jek]

this is fixed in changeset:2844 for 0.3 and changeset:2843 for 0.4.

[Former user]

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

svil

az()svilendobrev.com

[jek]

default support added in 8b6855fc2c833e0ac626718cd08cd08beb947899

[Mike Bayer]

Removing milestone: 0.5.0 (automated comment)