Hi!
I am trying to understand Python's method of passing arguments, the references
to objects etc. I fail to grasp why in populate_trie I have to make a deepcopy
of trie locally instead of just referencing to it.
If it makes any difference, I use Python 3.
from copy import deepcopy
def access_trie(d, sequence, position=None):
"""
Access the dictionary which is referred by applying consequently each
term of the sequence. In a more python terms, if sequence is 'key',
access: d['k']['e']['y'] Assume that the dictionary is at the
`position` of a list, if `position` is an argument.
>>> a = {'k': [0, {'a': [0, {'l': [0, {'o': [1, {}]}]}]}]}
>>> access_trie(a, 'kal', 1)
{'o': [1, {}]}
>>> access_trie(a, 'kalo', 1)
{}
>>> a = {'d': {'i': {'m': {'i': {'t': {'r': {'i': {'s': 1}}}}}}}}
>>> access_trie(a, 'dimitr')
{'i': {'s': 1}}
>>> access_trie(a, '')
{'d': {'i': {'m': {'i': {'t': {'r': {'i': {'s': 1}}}}}}}}
>>> access_trie(a, 'dimitris')
1
>>> b = access_trie(a, 'dimitr')
>>> b['o'] = {'s': 1}
>>> a
{'d': {'i': {'m': {'i': {'t': {'r': {'i': {'s': 1}, 'o': {'s': 1}}}}}}}}
"""
for c in sequence:
d = d[c]
if position is not None:
d = d[position]
return d
def populate_trie(trie, sequence, position=None):
"""
Populate a trie.
Assume that the counter is always at `position` 0 while the `position`
of the dictionary is the last one.
>>> trie = {}
>>> populate_trie(trie, 'taspython')
{'t': {'a': {'s': {'p': {'y': {'t': {'h': {'o': {'n': {}}}}}}}}}}
>>> trie = {}
>>> populate_trie(trie, 'kalo', 1)
{'k': [1, {'a': [1, {'l': [1, {'o': [1, {}]}]}]}]}
>>> trie = {}
>>> populate_trie(trie, 'heh', 2)
{'h': [1, 0, {'e': [1, 0, {'h': [1, 0, {}]}]}]}
>>> trie = {}
>>> trie = populate_trie(trie, 'heh', 1)
>>> populate_trie(trie, 'hah', 1)
{'h': [2, {'a': [1, {'h': [1, {}]}], 'e': [1, {'h': [1, {}]}]}]}
"""
if (position is not None) and (position >= 1):
embedded_obj = [0] * position
embedded_obj.append({})
else:
embedded_obj = {}
d = deepcopy(trie)
d2 = d
for i, character in enumerate(sequence):
d2 = access_trie(d, sequence[:i], position)
if character not in d2:
if position is None:
d2[character] = deepcopy(embedded_obj)
else:
d2[character] = d2.get(character, deepcopy(embedded_obj))
d2[character][0] += 1
elif position is not None:
d2[character][0] += 1
return d
Best regargs,
Dimitris Leventeas
--
Dimitris Leventeas
http://students.ceid.upatras.gr/~lebenteas/
--
http://mail.python.org/mailman/listinfo/python-list
