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
--
http://mail.python.org/mailman/listinfo/python-list
