[Tutor] named list

[Kent Johnson]

On Thu, Feb 5, 2009 at 5:09 AM, spir <denis.spir at free.fr> wrote:
> Hello, python world!
>
> I'm looking for a way to implement a kind of "named" list, or named tree, with the following requirements:
>
> * Each item is named (or key-ed), like in a dict.
> * Each item (node) can be either a terminal item (leaf) or a sub-list (branch).
> * There may be items with the same name, unlike in a dict.
> * The item entering order is preserved, unlike in a dict.
>
> * A non-requirement: may be useful that items can be retrieved by name (in case several items have the same name, it's allright to return first one -- it's up to the client code to manage that)
>
> A structural representation of such an object looks like that:
>
> obj
>        n1:val
>        n2:val
>        n3
>                n31:val
>                n32
>                        n321:val
>                        n322:val
>                n33
>        n4
>
> Which is exactly the same as for a list, except that each item gets a name in addition to its value.
> I ask for advices before doing bull**** as I suspect there may be a data structure in language theory that matches that needs. Some questions:
>
> * Do you know of such a structure?
> * What is the difference between a tree and a python list? a tree and an array that allows nesting?
> * Are items in a tree, as defined in theory, supposed to be of homogeneous type?
>
> I cannot implement that simply by giving items an additional attribute, for items can be of an type and can even change. They also need a whole bunch of custom methods. This would require sub-typing averu possible type, including custom ones (this was the cause of a previous, in which I asked if it was possible to sub-type at a type known at runtime). So I plan instead to implement the whole load of necessary behaviour in a container, thus letting the items unchanged.
> A possible design (?) would be to subtype list in order to add such a container object a parallel list of names. So that direct access still directly reaches values, while matching names are accessed by indexing a parallel list:
>
>        obj[n] <-- item
>        obj.names[n] <-- name
>
> And maybe:
>
>        obj.link[n] <-- (name,item)
>        obj[name] <-- item
>        obj.name(item) <-- name

Perhaps a list of (name, value) pairs, where the value could be a leaf
node or another list? Or the nodes could be instances of namedtuple,
so they have .name and .value attributes.

You could subclass list or UserList. UserList gives you bottleneck
methods which make it easy to customize all behaviour. You could also
make your own wrapper class which would implement the above API.

Kent