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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
|
#!/usr/bin/python
"""trie module example code."""
__author__ = 'Michal Nazarewicz <mina86@mina86.com>'
__copyright__ = 'Copyright 2014 Google Inc.'
# pylint: disable=invalid-name,superfluous-parens
import os
import stat
import sys
import pygtrie
print('Storing file information in the trie')
print('====================================\n')
ROOT_DIR = '/usr/local'
SUB_DIR = os.path.join(ROOT_DIR, 'lib')
SUB_DIRS = tuple(os.path.join(ROOT_DIR, d)
for d in ('lib', 'lib32', 'lib64', 'share'))
t = pygtrie.StringTrie(separator=os.path.sep)
# Read sizes regular files into a Trie
for dirpath, unused_dirnames, filenames in os.walk(ROOT_DIR):
for filename in filenames:
filename = os.path.join(dirpath, filename)
try:
filestat = os.stat(filename)
except OSError:
continue
if stat.S_IFMT(filestat.st_mode) == stat.S_IFREG:
t[filename] = filestat.st_size
# Size of all files we've scanned
print('Size of %s: %d' % (ROOT_DIR, sum(t.itervalues())))
# Size of all files of a sub-directory
print('Size of %s: %d' % (SUB_DIR, sum(t.itervalues(prefix=SUB_DIR))))
# Check existence of some directories
for directory in SUB_DIRS:
print(directory, 'exists' if t.has_subtrie(directory) else 'does not exist')
# Drop a subtrie
print('Dropping', SUB_DIR)
del t[SUB_DIR:]
print('Size of %s: %d' % (ROOT_DIR, sum(t.itervalues())))
for directory in SUB_DIRS:
print(directory, 'exists' if t.has_subtrie(directory) else 'does not exist')
print('\nStoring URL handlers map')
print('========================\n')
t = pygtrie.CharTrie()
t['/'] = lambda url: sys.stdout.write('Root handler: %s\n' % url)
t['/foo'] = lambda url: sys.stdout.write('Foo handler: %s\n' % url)
t['/foobar'] = lambda url: sys.stdout.write('FooBar handler: %s\n' % url)
t['/baz'] = lambda url: sys.stdout.write('Baz handler: %s\n' % url)
for url in ('/', '/foo', '/foot', '/foobar', 'invalid', '/foobarbaz', '/ba'):
key, handler = t.longest_prefix(url)
if key is not None:
handler(url)
else:
print('Unable to handle', repr(url))
if not os.isatty(0):
sys.exit(0)
try:
import termios
import tty
def getch():
"""Reads single character from standard input."""
attr = termios.tcgetattr(0)
try:
tty.setraw(0)
return sys.stdin.read(1)
finally:
termios.tcsetattr(0, termios.TCSADRAIN, attr)
except ImportError:
try:
from msvcrt import getch # pylint: disable=import-error
except ImportError:
sys.exit(0)
print('\nPrefix set')
print('==========\n')
ps = pygtrie.PrefixSet(factory=pygtrie.StringTrie)
ps.add('/etc/rc.d')
ps.add('/usr/local/share')
ps.add('/usr/local/lib')
ps.add('/usr') # Will handle the above two as well
ps.add('/usr/lib') # Does not change anything
print('Path prefixes:', ', '.join(iter(ps)))
for path in ('/etc', '/etc/rc.d', '/usr', '/usr/local', '/usr/local/lib'):
print('Is', path, 'in the set:', ('yes' if path in ps else 'no'))
print('\nDictionary test')
print('===============\n')
t = pygtrie.CharTrie()
t['cat'] = True
t['caterpillar'] = True
t['car'] = True
t['bar'] = True
t['exit'] = False
print('Start typing a word, "exit" to stop')
print('(Other words you might want to try: %s)\n' % ', '.join(sorted(
k for k in t if k != 'exit')))
text = ''
while True:
ch = getch()
if ord(ch) < 32:
print('Exiting')
break
text += ch
value = t.get(text)
if value is False:
print('Exiting')
break
if value is not None:
print(repr(text), 'is a word')
if t.has_subtrie(text):
print(repr(text), 'is a prefix of a word')
else:
print(repr(text), 'is not a prefix, going back to empty string')
text = ''
|
