Q: sort's key and cmp parameters

[Raymond Hettinger]

[Paul Rubin]
> Example of list of trees (nested dicts).  In practice you could get
> such a list from the simplejson module:
>
>   list_of_trees = [{'value':1, 'left':{'value':3,'left':None,'right':None},
>                                'right':{'value':7,'left':{'value':5, ...}}},
>                    {'value':19, 'left':{'value':23', ...}},
>                    ...
>                   ]

So, it looks like the relevant comparison values can be stored in
nested lists:

   list_of_lists = \
     [[1, [3, [], []],
          [7, [5, [], []], []]],
      [19, [23, [], []],
          []],
     ]

Here I've used a transformation where a tree is stored as:

   [tree['value'], tree['left'], tree['right']]

and the None value indicating an empty tree transformed to:

   []

> > Example comparison function:
>
>    def compare(tree1, tree2):
>       c = cmp(tree1['value'], tree2['value'])
>       if c != 0: return c
>       c = compare(tree1['left'], tree2['left'])
>       if c != 0: return c
>       return compare(tree1['right'], tree2['right])

Hmm, that recursive comparison order looks like how Python
already recursively compares lists.  So, perhaps the
lists can be compared directly:

   if list_of_lists[0] < list_of_lists[1]:
      ...


>> Are the trees user defined classes?
>
> Not in general.  They might be nested tuples, lists, or dictionaries.
> Or they could come from a non-extensible library-defined class, like
> from cElementTree

Are there any of these trees that cannot be transformed
(by a key function) into an equivalent nested list of lists
and values so that the trees can be directly compared to one another
using Python's normal built-in recursive comparison order for lists?


Raymond