New Ordered Dictionery to Criticise

[Fuzzyman]

Fuzzyman wrote:
> Sorry for this hurried message - I've done a new implementation of out
> ordered dict. This comes out of the discussion on this newsgroup (see
> blog entry for link to archive of discussion).
>
> See the latest blog entry to get at it :
> http://www.voidspace.org.uk/python/weblog/index.shtml
>

Hello all,

I've just done a new "beta 2" version. It has a full version of
FancyODict with the custome "callable sequence objects" for keys,
values and items. They are almost completely covered by tests.

You can download the new(er) version from :
http://www.voidspace.org.uk/cgi-bin/voidspace/downman.py?file=odictbeta2.py

Full discussion of the remaining issues below, or at :
http://www.voidspace.org.uk/python/weblog/arch_d7_2005_11_26.shtml#e147

Progress on the updated implementation of dict continues. (I hestitate
to say *new* version, as it's just a heavy makeover for the old code -
which was basically sound).

``FancyODict`` is now a full implementation of an Ordered Dictionary,
with custom *callable sequence objects* for ``keys``, ``values``, and
``items``. These can be called like normal methods, but can also be
accessed directly as sequence objects. This includes assigning to,
indexing, and slicing - as well as all the other relevant sequence
methods. {sm;:-)}

I've also added an optional index to ``OrderedDict.popitem``.

I'm sure there are lots of ways this can be optimised for efficiency -
but the new objects have got pretty full test coverage.

You can download the new version (for testing) from `odict Beta 2
<http://www.voidspace.org.uk/cgi-bin/voidspace/downman.py?file=odictbeta2.py>`_

The following issues still remain :

* ``FancyOdict`` is a separate class from ``OrderedDict``.

    Because this version is *undoubtably* less efficient than
OrderedDict, my current thinking is that I should leave them separate
(and have both available). Being able to operate on the
keys/values/items as sequences is for convenience only.

    Anyone got a suggestion for a better name than ``FancyODict`` ?

* You can no longer access the key order directly. The old ``sequence``
attribute is depracated and will eventually go away.

    You can currently alter the order (of keys, values *and* items) by
passing an iterable into those methods.

    Someone has suggested that this "smells bad" - and it ought to be
done through separate `setkeys``, ``setvalues``, and ``setitems``
methods.

    I'm *inclined* to agree, but I don't feel strongly about it. Anyone
else got any opinions ?

* ``repr`` ought to return a value that ``eval`` could use to turn back
into an OrderedDict.

    I have actually done an implementation of this, but it would mean
that *all* the doctests need to be changed. I *will* do this at some
point.

* Slice assignment.

    The semantics for slice assignment are fiddly.

    For example, what do you do if in a slice assignment a key collides
with an existing key ?

    My current implementation does what an ordinary dictionary does,
the new value overwrites the previous one. This means that the
dictionary can reduce in size as the assignment progresses. {sm;:?}

    I think this is preferable to raising an error and preventing
assignment. It does prevent an optimisation whereby I calculate the
indexes of all the new items in advance.

    It also means you can't rely on the index of a key from a slice
assignment, unless you know that there will be no key collisions.

     In general I'm *against* preventing programmers from doing things,
so long as the documentation carries an appropriate warning.

    An example will probably help illustrate this :

.. raw:: html

    {+coloring}

    d = OrderedDict()
    d[1] = 1
    d[2] = 2
    d[3] = 3
    d[4] = 4
    d.keys()
    [1, 2, 3]

    # fetching every other key
    # using an extended slice
    # this actually returns an OrderedDict
    d[::2]
    {1: 1, 3: 3}

    # we can assign to every other key
    # using an ordered dict
    d[::2] = OrderedDict([(2, 9), (4, 8)])
    len(d) == 4
    False

    d
    {2: 9, 4: 8}

    """
    Because of the key collisions the length of
    d has changed - it now only has two keys instead
    of four.
    """

   {-coloring}


> Criticism solicited (honestly) :-)
>
> We (Nicola Larosa and I) haven't yet made any optimisations - but there
> are two implementations to play with.
>
> One allows you to access the keys attribute as if it was a sequence (as
> well as a method).
>
> All the best,
> 
> Fuzzyman
>  http://www.voidspace.org.uk/python/index.shtml