projects
/
python_utils.git
/ blobdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
|
commitdiff
|
tree
raw
|
inline
| side by side
Remove whitespace from trie's repr_brief.
[python_utils.git]
/
collect
/
trie.py
diff --git
a/collect/trie.py
b/collect/trie.py
index b9a5a1adbcd91cb96b593ac62b9eb5db7bdb6cc5..fef28cb40ddfbad3ea1c4d45f341f8e5c7407127 100644
(file)
--- a/
collect/trie.py
+++ b/
collect/trie.py
@@
-1,6
+1,11
@@
#!/usr/bin/env python3
#!/usr/bin/env python3
-from typing import Any, Sequence
+"""This is a Trie class, see: https://en.wikipedia.org/wiki/Trie.
+
+ It attempts to follow Pythonic container patterns. See doctests
+ for examples."""
+
+from typing import Any, Generator, Sequence
class Trie(object):
class Trie(object):
@@
-11,10
+16,13
@@
class Trie(object):
for examples.
"""
for examples.
"""
+
def __init__(self):
self.root = {}
self.end = "~END~"
self.length = 0
def __init__(self):
self.root = {}
self.end = "~END~"
self.length = 0
+ self.viz = ''
+ self.content_generator: Generator[str] = None
def insert(self, item: Sequence[Any]):
"""
def insert(self, item: Sequence[Any]):
"""
@@
-240,7
+248,43
@@
class Trie(object):
return None
return [x for x in node if x != self.end]
return None
return [x for x in node if x != self.end]
- def repr_recursive(self, node, delimiter):
+ def repr_fancy(
+ self,
+ padding: str,
+ pointer: str,
+ node: Any,
+ has_sibling: bool,
+ ):
+ if node is None:
+ return ''
+ if node is not self.root:
+ ret = f'\n{padding}{pointer}'
+ if has_sibling:
+ padding += '│ '
+ else:
+ padding += ' '
+ else:
+ ret = f'{pointer}'
+
+ child_count = 0
+ for child in node:
+ if child != self.end:
+ child_count += 1
+
+ for child in node:
+ if child != self.end:
+ if child_count > 1:
+ pointer = "├──"
+ has_sibling = True
+ else:
+ pointer = "└──"
+ has_sibling = False
+ pointer += f'{child}'
+ child_count -= 1
+ ret += self.repr_fancy(padding, pointer, node[child], has_sibling)
+ return ret
+
+ def repr_brief(self, node, delimiter):
"""
A friendly string representation of the contents of the Trie.
"""
A friendly string representation of the contents of the Trie.
@@
-249,10
+293,8
@@
class Trie(object):
>>> t.insert([10, 0, 0, 2])
>>> t.insert([10, 10, 10, 1])
>>> t.insert([10, 10, 10, 2])
>>> t.insert([10, 0, 0, 2])
>>> t.insert([10, 10, 10, 1])
>>> t.insert([10, 10, 10, 2])
- >>> t.repr_recursive(t.root, '.')
- '10.[0.0.[1, 2], 10.10.[1, 2]]'
- >>> print(t)
- 10[00[1, 2], 1010[1, 2]]
+ >>> t.repr_brief(t.root, '.')
+ '10.[0.0.[1,2],10.10.[1,2]]'
"""
child_count = 0
"""
child_count = 0
@@
-260,13
+302,13
@@
class Trie(object):
for child in node:
if child != self.end:
child_count += 1
for child in node:
if child != self.end:
child_count += 1
- child_rep = self.repr_
recursive
(node[child], delimiter)
+ child_rep = self.repr_
brief
(node[child], delimiter)
if len(child_rep) > 0:
if len(child_rep) > 0:
- my_rep += str(child) + delimiter + child_rep + ",
"
+ my_rep += str(child) + delimiter + child_rep + ","
else:
else:
- my_rep += str(child) + ",
"
+ my_rep += str(child) + ","
if len(my_rep) > 1:
if len(my_rep) > 1:
- my_rep = my_rep[:-
2
]
+ my_rep = my_rep[:-
1
]
if child_count > 1:
my_rep = f'[{my_rep}]'
return my_rep
if child_count > 1:
my_rep = f'[{my_rep}]'
return my_rep
@@
-274,7
+316,7
@@
class Trie(object):
def __repr__(self):
"""
A friendly string representation of the contents of the Trie. Under
def __repr__(self):
"""
A friendly string representation of the contents of the Trie. Under
- the covers uses repr_
recursive with no delimiter
+ the covers uses repr_
fancy.
>>> t = Trie()
>>> t.insert([10, 0, 0, 1])
>>> t = Trie()
>>> t.insert([10, 0, 0, 1])
@@
-282,12
+324,22
@@
class Trie(object):
>>> t.insert([10, 10, 10, 1])
>>> t.insert([10, 10, 10, 2])
>>> print(t)
>>> t.insert([10, 10, 10, 1])
>>> t.insert([10, 10, 10, 2])
>>> print(t)
- 10[00[1, 2], 1010[1, 2]]
+ *
+ └──10
+ ├──0
+ │ └──0
+ │ ├──1
+ │ └──2
+ └──10
+ └──10
+ ├──1
+ └──2
"""
"""
- return self.repr_
recursive(self.root, ''
)
+ return self.repr_
fancy('', '*', self.root, False
)
if __name__ == '__main__':
import doctest
if __name__ == '__main__':
import doctest
+
doctest.testmod()
doctest.testmod()