Why I have to do a deepcopy to the argument?

[Thomas Jollans]

On 06/16/2010 02:02 AM, Dimitris Leventeas wrote:
> from copy import deepcopy
> 
> def access_trie(d, sequence, position=None):
>     [snip]
> 

To see what you're on about, I removed the deepcopies from your code and
ran your examples with doctest:

% python3.1 -m doctest trie.py
**********************************************************************
File "trie.py", line 45, in trie.populate_trie
Failed example:
    populate_trie(trie, 'taspython')
Expected:
    {'t': {'a': {'s': {'p': {'y': {'t': {'h': {'o': {'n': {}}}}}}}}}}
Got:
    {'t': {'a': {...}, 'h': {...}, 'o': {...}, 'n': {...}, 'p': {...},
's': {...}, 't': {...}, 'y': {...}}}
**********************************************************************
File "trie.py", line 48, in trie.populate_trie
Failed example:
    populate_trie(trie, 'kalo', 1)
Expected:
    {'k': [1, {'a': [1, {'l': [1, {'o': [1, {}]}]}]}]}
Got:
    {'k': [4, {'a': [...], 'l': [...], 'o': [...]}]}
**********************************************************************
File "trie.py", line 51, in trie.populate_trie
Failed example:
    populate_trie(trie, 'heh', 2)
Expected:
    {'h': [1, 0, {'e': [1, 0, {'h': [1, 0, {}]}]}]}
Got:
    {'h': [3, 0, {'h': [...], 'e': [...]}]}
**********************************************************************
File "trie.py", line 55, in trie.populate_trie
Failed example:
    populate_trie(trie, 'hah', 1)
Expected:
    {'h': [2, {'a': [1, {'h': [1, {}]}], 'e': [1, {'h': [1, {}]}]}]}
Got:
    {'h': [4, {'a': [2, {'h': [...]}], 'h': [...], 'e': [...]}]}
**********************************************************************
1 items had failures:
   4 of   9 in trie.populate_trie
***Test Failed*** 4 failures.

As you can see, all the letters except the first one are inserted at
level II, not in a nested level.

>             if position is None:
>                 d2[character] = deepcopy(embedded_obj)
>             else:
>                 d2[character] = d2.get(character, deepcopy(embedded_obj))
>                 d2[character][0] += 1

If you don't copy embedded_obj here, you just insert a reference to the
same object into the tree at different points. so you insert
embedded_obj, iterate one level further into the structure, and insert
the exact same embedded_obj, into itself! That's what the [...] and
{...} in the output above mean - it's returning cyclic structures.
Another example of a cyclic structure:

>>> L = list(range(5))
>>> L.append(L)
>>> L
[0, 1, 2, 3, 4, [...]]
>>>

Obviously, it goes on for ever and ever, so Python can't print it
properly, without the ...

-- 
Thomas