You are here: Home ‣ Dive Into Python 3 ‣

Difficulty level: ♦♦♦♦♢

# Advanced Classes

> ❝ FIXME ❞
> — FIXME

## Diving In

FIXME

## Ordered Dictionary: Not An Oxymoron

[FIXME here's why ordered dicts are useful: http://www.gossamer-threads.com/lists/python/dev/656556 ]

[download `ordereddict.py`]

    class OrderedDict(dict, MutableMapping):
        'Dictionary that remembers insertion order'
        # An inherited dict maps keys to values.
        # The inherited dict provides __getitem__, __len__, __contains__, and get.
        # The remaining methods are order-aware.
        # Big-O running times for all methods are the same as for regular dictionaries.

        # The internal self.__map dictionary maps keys to links in a doubly linked list.
        # The circular doubly linked list starts and ends with a sentinel element.
        # The sentinel element never gets deleted (this simplifies the algorithm).
        # The prev/next links are weakref proxies (to prevent circular references).
        # Individual links are kept alive by the hard reference in self.__map.
        # Those hard references disappear when a key is deleted from an OrderedDict.

        def __init__(self, *args, **kwds):
            '''Initialize an ordered dictionary.  Signature is the same as for
            regular dictionaries, but keyword arguments are not recommended
            because their insertion order is arbitrary.

            '''
            if len(args) > 1:
                raise TypeError('expected at most 1 arguments, got %d' % len(args))
            try:
                self.__root
            except AttributeError:
                self.__root = root = _Link()    # sentinel node for the doubly linked list
                root.prev = root.next = root
                self.__map = {}
            self.update(*args, **kwds)

        def clear(self):
            'od.clear() -> None.  Remove all items from od.'
            root = self.__root
            root.prev = root.next = root
            self.__map.clear()
            dict.clear(self)

        def __setitem__(self, key, value):
            'od.__setitem__(i, y) <==> od[i]=y'
            # Setting a new item creates a new link which goes at the end of the linked
            # list, and the inherited dictionary is updated with the new key/value pair.
            if key not in self:
                self.__map[key] = link = _Link()
                root = self.__root
                last = root.prev
                link.prev, link.next, link.key = last, root, key
                last.next = root.prev = _proxy(link)
            dict.__setitem__(self, key, value)

        def __delitem__(self, key):
            'od.__delitem__(y) <==> del od[y]'
            # Deleting an existing item uses self.__map to find the link which is
            # then removed by updating the links in the predecessor and successor nodes.
            dict.__delitem__(self, key)
            link = self.__map.pop(key)
            link.prev.next = link.next
            link.next.prev = link.prev

        def __iter__(self):
            'od.__iter__() <==> iter(od)'
            # Traverse the linked list in order.
            root = self.__root
            curr = root.next
            while curr is not root:
                yield curr.key
                curr = curr.next

        def __reversed__(self):
            'od.__reversed__() <==> reversed(od)'
            # Traverse the linked list in reverse order.
            root = self.__root
            curr = root.prev
            while curr is not root:
                yield curr.key
                curr = curr.prev

        def __reduce__(self):
            'Return state information for pickling'
            items = [[k, self[k]] for k in self]
            tmp = self.__map, self.__root
            del self.__map, self.__root
            inst_dict = vars(self).copy()
            self.__map, self.__root = tmp
            if inst_dict:
                return (self.__class__, (items,), inst_dict)
            return self.__class__, (items,)

        setdefault = MutableMapping.setdefault
        update = MutableMapping.update
        pop = MutableMapping.pop
        keys = MutableMapping.keys
        values = MutableMapping.values
        items = MutableMapping.items

        def popitem(self, last=True):
            '''od.popitem() -> (k, v), return and remove a (key, value) pair.
            Pairs are returned in LIFO order if last is true or FIFO order if false.

            '''
            if not self:
                raise KeyError('dictionary is empty')
            key = next(reversed(self) if last else iter(self))
            value = self.pop(key)
            return key, value

        def __repr__(self):
            'od.__repr__() <==> repr(od)'
            if not self:
                return '%s()' % (self.__class__.__name__,)
            return '%s(%r)' % (self.__class__.__name__, list(self.items()))

        def copy(self):
            'od.copy() -> a shallow copy of od'
            return self.__class__(self)

        @classmethod
        def fromkeys(cls, iterable, value=None):
            '''OD.fromkeys(S[, v]) -> New ordered dictionary with keys from S
            and values equal to v (which defaults to None).

            '''
            d = cls()
            for key in iterable:
                d[key] = value
            return d

        def __eq__(self, other):
            '''od.__eq__(y) <==> od==y.  Comparison to another OD is order-sensitive
            while comparison to a regular mapping is order-insensitive.

            '''
            if isinstance(other, OrderedDict):
                return len(self)==len(other) and \
                       all(p==q for p, q in zip(self.items(), other.items()))
            return dict.__eq__(self, other)

        def __ne__(self, other):
            '''od.__ne__(y) <==> od!=y.  Comparison to another OD is order-sensitive
            while comparison to a regular mapping is order-insensitive.

            '''
            return not self == other

⁂

## Attributes of a Class Object

FIXME

    >>> import ordereddict
    >>> od = ordereddict.OrderedDict()
    >>> klass = od.__class__       ①
    >>> type(klass)
    <class 'abc.ABCMeta'>
    >>> klass.__name__
    'OrderedDict'

    >>> klass.__module__
    'ordereddict'
    >>> klass.__bases__
    (<class 'dict'>, <class '_abcoll.MutableMapping'>)

1. FIXME

    # continued from previous example
    >>> klass.__dict__
    {'__abstractmethods__': frozenset(),
     '__delitem__': <function __delitem__ at 0x00DCB6A8>,
     '__dict__': <attribute '__dict__' of 'OrderedDict' objects>,
     '__doc__': None,
     '__eq__': <function __eq__ at 0x00DD2930>,
     '__hash__': None,
     '__init__': <function __init__ at 0x00DC41E0>,
     '__iter__': <function __iter__ at 0x00DCB618>,
     '__module__': 'ordereddict',
     '__reduce__': <function __reduce__ at 0x00DCB6F0>,
     '__repr__': <function __repr__ at 0x00DCB8E8>,
     '__reversed__': <function __reversed__ at 0x00DCB660>,
     '__setitem__': <function __setitem__ at 0x00DCB5D0>,
     '__weakref__': <attribute '__weakref__' of 'OrderedDict' objects>,
     '_abc_cache': <_weakrefset.WeakSet object at 0x00DCF950>,
     '_abc_negative_cache': <_weakrefset.WeakSet object at 0x00DCF990>,
     '_abc_negative_cache_version': 12,
     '_abc_registry': <_weakrefset.WeakSet object at 0x00DCF910>,
     'clear': <function clear at 0x00DCB7C8>,
     'copy': <function copy at 0x00DD28A0>,
     'fromkeys': <classmethod object at 0x00DCF8F0>,
     'items': <function items at 0x00D60150>,
     'keys': <function keys at 0x00D60108>,
     'pop': <function pop at 0x00D60978>,
     'popitem': <function popitem at 0x00DCB780>,
     'setdefault': <function setdefault at 0x00D60A98>,
     'update': <function update at 0x00D60A50>,
     'values': <function values at 0x00D60198>}

1. FIXME

⁂

## Implementing Fractions

☜ ☞

© 2001–9 Mark Pilgrim