Ordered dictionaries?

Jason Orendorff jason at jorendorff.com
Thu Dec 13 18:03:00 EST 2001


> One last Perl module that I need to replace to
> complete my Python toolkit is a custom module that let
> me create a dictionary whose keys were settable and
> retrievable in a particular order.  Essentially, this
> let us have a list whose ordered elements were also
> accessible by name.

Sounds horrible, but you can certainly do it.  :)
Sample code is included below.

In the Language Reference, "Special method names":
http://www.python.org/doc/current/ref/specialnames.html


> Has anyone done this?  If not, what class operators
> would I need to override to create my own class that
> does this?
>
> Example of how it would work, assuming OrderedDict was
> a working class of what I wanted:

Hmm.  In Perl, hashes only have string keys, correct?
You could apply the same restriction to a hypothetical
OrderedDict class; but note that it doesn't apply to
Python dictionaries in general.

Here goes:

class OrderedDict:
    def __init__(self):
        self.__keydict = {}  # Maps strings to integer indices
        self.__keys = []     # Ordered list of the keys
        self.__values = []   # Ordered list of the values

    def __setitem__(self, key, value):
        """ Implements self[key] = value """
        if isinstance(key, str):
            # Assign element by name
            i = self.__keydict.get(key)
            if i is None:
                self.append_item(key, value)
            else:
                self.__values[i] = value
        elif isinstance(key, int):
            # Assign element by number
            n = len(self.__values)
            if -n <= key < n:
                self.__values[n] = value
            elif key < -n:
                raise IndexError("index: %i; len: %i" % (key, n))
            else:
                while n < key:
                    self.append_item(None, None)
                    n += 1
                self.append_item(None, value)
        else:
            raise TypeError("index must be an int or string")

    def __getitem__(self, key):
        """ od.__getitem__(key) <==> self[key] """
        if isinstance(key, int):
            index = key
        else:
            index = self.__keydict[key]
        return self.__values[index]

    def __len__(self):
        """ od.__len__() <==> len(od) """
        return len(self.__values)

    def __contains__(self, value):
        """ od.__contains__(value) <==> value in od """
        return value in self.__values

    def append_item(self, name, value):
        n = len(self.__values)
        if name is None:
            name = n
        self.__keydict[name] = n
        self.__keys.append(name)
        self.__values.append(value)

    def append(self, value):
        self.append_item(None, value)

    def has_key(self, name):
        return self.__keydict.has_key(name)

    def keys(self):
        return self.__keys[:]

    def values(self):
        return self.__values[:]

    def items(self):
        return zip(self.__keys, self.__values)

Works for me.

>>> od = OrderedDict()
>>> od['Alice'] = 'Anderson'
>>> od['Bob'] = 'Bradley'
>>> od.append('Christiansen')
>>> od['Dave'] = 'Dobson'
>>> od.keys()
['Alice', 'Bob', 2, 'Dave']
>>> od.values()
['Anderson', 'Bradley', 'Christiansen', 'Dobson']
>>> od[3]
'Dobson'
>>> od[7] = 'Johnson'
>>> od.values()  ## NOTE: works differently than what you asked for,
                 ## but makes more sense IMHO
['Anderson', 'Bradley', 'Christiansen', 'Dobson', None, None, None,
'Johnson']
>>> len(od)
8
>>> for i in range(len(od)): print od[i]
(yes, this works)
>>> for v in od: print v
(this also works)
>>> 'Anderson' in od
1
>>> 'Orendorff' in od
0
>>> od.items()
[('Alice', 'Angerson'), ('Bob', 'Bradley'), (2, 'Christiansen'),
 ('Dave', 'Dobson'), (4, None), (5, None), (6, None), (7, 'Johnson')]


Note that values() works differently, and od[30] will throw an
exception instead of gracefully returning None.  But this should
be a good starting point and/or tutorial.

You could of course go much farther with this.  Implementations
for the dictionary methods clear(), copy(), update(), get(),
popitem(), and setdefault() are easy exercises.  The list methods
count(), extend(), index(), and pop() are likewise pretty easy.

The list methods insert(), remove(), and sort() might be more
interesting.  Adding support for slices and implementing
__delitem__() and __cmp__() will take some thought - and some
research.

The class should probably also have sensible __init__(),
__repr__(), and __str__() methods.

Happy hacking!

--
Jason Orendorff    http://www.jorendorff.com/





More information about the Python-list mailing list