1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
|
# -*- coding: utf-8 -*-
from __future__ import absolute_import, unicode_literals
import string
import datrie
WORDS = ['producers', 'pool', 'prepare', 'preview', 'prize', 'produce',
'producer', 'progress']
def _trie():
trie = datrie.Trie(ranges=[(chr(0), chr(127))])
for index, word in enumerate(WORDS, 1):
trie[word] = index
return trie
def test_base_trie_data():
trie = datrie.BaseTrie(string.printable)
trie['x'] = 1
trie['xo'] = 2
state = datrie.BaseState(trie)
state.walk('x')
it = datrie.BaseIterator(state)
it.next()
assert it.data() == 1
state.walk('o')
it = datrie.BaseIterator(state)
it.next()
assert it.data() == 2
def test_next():
trie = _trie()
state = datrie.State(trie)
it = datrie.Iterator(state)
values = []
while it.next():
values.append(it.data())
assert len(values) == 8
assert values == [2, 3, 4, 5, 6, 7, 1, 8]
def test_next_non_root():
trie = _trie()
state = datrie.State(trie)
state.walk('pr')
it = datrie.Iterator(state)
values = []
while it.next():
values.append(it.data())
assert len(values) == 7
assert values == [3, 4, 5, 6, 7, 1, 8]
def test_next_tail():
trie = _trie()
state = datrie.State(trie)
state.walk('poo')
it = datrie.Iterator(state)
values = []
while it.next():
values.append(it.data())
assert values == [2]
def test_keys():
trie = _trie()
state = datrie.State(trie)
it = datrie.Iterator(state)
keys = []
while it.next():
keys.append(it.key())
assert keys == sorted(WORDS)
def test_keys_non_root():
trie = _trie()
state = datrie.State(trie)
state.walk('pro')
it = datrie.Iterator(state)
keys = []
while it.next():
keys.append(it.key())
assert keys == ['duce', 'ducer', 'ducers', 'gress']
def test_keys_tail():
trie = _trie()
state = datrie.State(trie)
state.walk('pro')
it = datrie.Iterator(state)
keys = []
while it.next():
keys.append(it.key())
assert keys == ['duce', 'ducer', 'ducers', 'gress']
|
