Python Class Methods – Implementing Ordered Dictionary

“It is the time you have wasted for your rose that makes your rose so important.” ― Antoine de Saint-Exupéry, The Little Prince

1. Introduction

The python class system supports a number of special methods which allows class implementations to mimic built-in python objects objects. These special methods are invoked by the python run-time system in a way similar to the built-in classes. For example, the method __len__() can be defined by a user class which will be invoked when the client code attempts to find the length of the object using len(obj).

In this article, we take a look at implementing an ordered dictionary – a dictionary which remembers the order in which the items (key – value pairs) were inserted and allows you to iterate on the items in the same order. We do this by storing the items in an array as well as in a dict. We also illustrate the use of some of the python special class methods to mimic the behavior of dict as closely as possible.

Note: The python standard library includes a module collections.OrderedDict which is a much more complete implementation of the concepts discussed here, and should be used in all real code. The article and code presented here is intended as a learning aid rather than a complete implementation.

2. Implementing an Ordered Dictionary

Here is a basic class for implementing an ordered dictionary. It starts with an inner class for representing a key-value pair. The class stores the (key, value) pairs in an array, and also maintains a dict for fast lookup of the keys. The array serves to store the order in which the items were inserted. We want our ordered_dict to work as much as possible like a standard dict.

class ordered_dict:
    class _item:
        def __init__(self, key, value):
            self.k = key
            self.v = value

    def __init__(self):
        self.d = {}
        self.a = []

    def _find(self, key):
        for i in self.a:
            if i.k == key: return i
        return None

    def __setitem__(self, key, value):
        if key in self.d:
            item = self._find(key)
            item.v = value
        else:
            self.d[key] = value
            self.a.append(ordered_dict._item(key, value))

    def __getitem__(self, key):
        return self.d[key]

Let us see how to use this class.

d = ordered_dict()
d['jim'] = 4
d['cat'] = 'fink'
d['dog'] = 'dink'
d['joe'] = 1
print d
# <odict.ordered_dict instance at 0x7fbe502c2368>

3. Improving String Representation

We don’t like the string representation of the class – it is a default representation of an object in python. Let us improve it to look just like dict. We do that by defining the __str__() method.

class ordered_dict:
...
    def __str__(self):
        s = ''
        for i in self.a:
            if s: s += ', '
            if isinstance(i.v, (int, long, float)):
                v = str(i.v)
            else:
                v = "'" + str(i.v) + "'"
            s += "'" + str(i.k) + "'" + ': ' + v
        return '{' + s + '}'

Now we get a nice representation similar to dict.

print d
# {'jim': 4, 'cat': 'fink', 'dog': 'dink', 'joe': 1}

4. Adding Iteration

The main purpose of our ordered dict class is to be able to fetch items in the same order as inserted. For this, we need to add iteration to our class. We do this by defining an inner class (called _iter) which handles the iteration using the array member.

class ordered_dict:
...
    class _iter:
        def __init__(self, arr):
            self.a = arr
            self.c = 0;

        def next(self):
            i = self.c
            if i >= len(self.a):
                raise StopIteration
            self.c += 1
            return self.a[i].k
...
    def __iter__(self):
        return ordered_dict._iter(self.a)

By comparison, here is what happens with an ordinary dict. As you can see, dict returns items in no particular order.

c = {}
c['jim'] = 4
c['cat'] = 'fink'
c['dog'] = 'dink'
c['joe'] = 1
print c

for i in c:
    print ' ', i
# prints
{'joe': 1, 'jim': 4, 'dog': 'dink', 'cat': 'fink'}
  joe
  jim
  dog
  cat

5. Deleting an Item

Deleting an item needs to be handled specially. Since the items are being maintained in an array as well as an internal dict, we need to delete the item from both.

class ordered_dict:
    def __delitem__(self, key):
        del self.d[key]
        # above stmt raises exception if no key so following code not executed
        a = []
        for i in self.a:
            if i.k != key: a.append(i)
        self.a = a

Checking if it works:

d = ordered_dict()
d['jim'] = 4
d['cat'] = 'fink'
d['dog'] = 'dink'
d['joe'] = 1
print d
del d['joe']
print d
# prints
{'jim': 4, 'cat': 'fink', 'dog': 'dink', 'joe': 1}
{'jim': 4, 'cat': 'fink', 'dog': 'dink'}

6. Delegated Implementations

Let us look into implementing methods for handling len(obj) and key in obj check. These are done using __len__() and __contains__() respectively, and is quite simple – just delegate to the underlying dict.

class ordered_dict:
...
    def __contains__(self, key):
        return dict.__contains__(self.d, key)

    def __iter__(self):
        return ordered_dict._iter(self.a)

    def __len__(self):
        return len(self.d)
...

And of course, verify that it works as normal.

d = ordered_dict()
d['jim'] = 4
d['cat'] = 'fink'
d['dog'] = 'dink'
d['joe'] = 1
print d, 'has', len(d), 'items.'
print 'does d have "joe"?', 'joe' in d
print 'does d have "jack"?', 'jack' in d

Conclusion

In this article, we learnt some special methods in python and how to use these to enhance your class to behave in an idiomatic way in python.