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/