<jupyter_start><jupyter_text>My version<jupyter_code>from copy import deepcopy
from functools import partial

from htools import *
from lolviz import *
class TrieNode:
    
    def __init__(self, data=()):
        self.edges = {}
        self.stop_state = False
        for x in tolist(data):
            self.append(x)
        
    def append(self, seq):
        if not seq: 
            self.stop_state = True
            return
        x = seq[0]
        if x not in self.edges:
            self.edges[x] = TrieNode()
        self.edges[x].append(seq[1:])
        
    def __repr__(self):
        return f'{type(self).__name__}({list(self.edges.keys()) or ""})'
node = TrieNode()
print(node)
objviz(node)
node.append('ask')
objviz(node)
node.append('dog')
objviz(node)
node
node.append('doll')
objviz(node)
node.append('dollar')
objviz(node)
TrieNode(['dog', 'cat'])
TrieNode('cat')
x = 6
type([]).__name__
class Trie:
    
    def __init__(self, values=(), suffix=False):
        """
        Parameters
        ----------
        values: str or list-like Iterable
            If provided, this should be one or more sequences to add to the
            try. Sequences could be strings, lists of strings (like word
            tokens), tuples of integers, etc. As of Dec 2020, this should NOT
            be numpy arrays or torch tensors.
        """
        self.head = TrieNode()
        if suffix:
            self._maybe_reverse = lambda x: x[::-1]
        else:
            self._maybe_reverse = identity
        self.suffix = suffix
            
        # dtype records the type of object present in the trie, and is a
        # string rather than a type because lolviz library has a
        # bug when displaying type attributes. Its visualizations are very
        # helpful here so I don't want to break compatibility.
        self.dtype = ''
        self.child_dtype = ''
        self.postprocess = None
        
        # Use extend rather than passing values directly to TrieNode because 
        # that won't give us validation or preprocessing.
        self._length = 0
        self.extend(tolist(values))
        
    def append(self, seq):
        """Add a sequence to the trie. This operates in place."""
        if not self.postprocess: 
            self.dtype = type(seq).__name__
            self.child_dtype = type(seq[0]).__name__
            self.postprocess = partial(str.join, '') if self.dtype == 'str' \
                else identity
        else:
            self._validate_input(seq)
        self.head.append(self._maybe_reverse(seq))
        self._length += 1
        
    def extend(self, seqs):
        """Add a list-like group of sequences to the Trie."""
        for seq in seqs:
            self.append(seq)
            
    def __add__(self, seq):
        """Allows us to add items to a trie using + operator. This does not 
        alter the trie in place: to do that, use `append` or assign the result
        of this method back to your variable.
        
        Returns
        -------
        Trie
        """
        clone = deepcopy(self)
        clone.append(seq)
        return clone
    
    def _find(self, seq, node=None):
        """Try to find a a sequence in the trie. We provide this helper method
        rather than doing it entirely in __contains__ in case other methods
        want to make use of the found node (perhaps passing it to 
        self._values.)
        
        Returns
        -------
        TrieNode: If node.stop_state=True, the seq is in the trie. If False,
        it's not.
        """
        self._validate_input(seq)
        seq = self._maybe_reverse(seq)
        node = node or self.head
        for x in seq:
            if x not in node.edges: 
                # Return this so __contains__ can check its stop state.
                return TrieNode()
            node = node.edges[x]
        return node
    
    def __contains__(self, seq):
        """Check if a sequence is present in the trie.
        
        Returns
        -------
        bool
        """
        return self._find(seq).stop_state
    
    def _values(self, current=None, node=None):
        """Generator that yields each sequence in the tree one by one. Don't
        rely on the order, but I believe it should be a depth first traversal
        where the order of subtries traversed is determined by insertion 
        order. See examples.
        
        Parameters
        ----------
        current: list or None
            List of partial sequence currently being retrieved. This is used
            internally but should rarely need to be called by the user.
        node: TrieNode or None
            The node to retrieve values from. By default, we use the root 
            node, thereby retrieving values for the whole trie.
        
        Examples
        --------
        >>> t = Trie(['add', 'subtract', 'addition', 'multiply', 'adds'])
        >>> for v in t._values():
               print(v)
            
        add
        addition
        adds
        subtract
        multiply
        """
        node = node or self.head
        current = current or []
        if node.stop_state:
            # Here, reversal is more of a postprocessing step than a 
            # preprocessing one: we're converting the reversed word stored in
            # the suffix tree back to its original order.
            yield self._maybe_reverse(self.postprocess(current))
        for key, node_ in node.edges.items():
            yield from self._values(current+[key], node_)
            
    def __iter__(self):
        """We separate this from self._values because we want the latter to
        be callable with arguments.
        """
        yield from self._values()
    
    def values(self):
        """Get a list of all sequences in the trie. User-facing version of
        `_values` that returns a list rather than a generator. User can also
        simply call `list(my_trie)` and get the same result.
        """
        return list(self)
    
    def __len__(self):
        # Don't just delegate to `self.values()` because __len__ is called 
        # under the hood by list(self), thereby creating a recursion error in
        # `self.values()`. Could do `sum(1 for _ in self) but that gets slow
        # with large tries. There's currently no way to delete items so we
        # don't have to worry about length changing outside of `append`, and 
        # if we do implement that we can simply adjust _length accordingly.
        return self._length
    
    def _startswith(self, seq, node=None):
        """Base behavior for both `startswith` and `endswith`.
        """
        # Validation occurs in `_find`.
        node = self._find(seq, node=node)
        if self.suffix: 
            return [x + seq for x in self._values(node=node)]
        else:
            return [seq + x for x in self._values(node=node)]

    def startswith(self, seq, node=None):
        """Gets all values in a trie that start with a given sequence. (Unlike
        str.startswith, this does NOT return a boolean - consider renaming in
        a future version.)
        
        Parameters
        ----------
        seq: Iterable
            Same type as all the other sequences in the trie.
        node: TrieNode
            If provided, only the subtrie starting with this node will be
            searched. Defaults to the head, i.e. the whole trie will be 
            searched.
            
        Returns
        -------
        list: Each item will be one of the sequences in the trie. If an empty
        list is returned, the trie contains no items sharing any leading
        values with the input `seq`.
        """
        if self.suffix:
            warnings.warn(
                'Suffix trees are optimized for the `endswith` method, but '
                '`startswith` will require walking the whole trie (may be '
                'slow). For an efficient implementation of `startswith`, you '
                'can create a prefix tree by passing `suffix=False` to '
                'Trie.__init__.'
            )
            if self.dtype == 'str':
                return [v for v in self._values(node=node) 
                        if v.startswith(seq)]
            else:
                self._validate_input(seq)
                length = len(seq)
                return [v for v in self._values(node=node)
                        if v[:length] == seq]
        return self._startswith(seq, node=node)

    def endswith(self, seq, node=None):
        """Gets all values in a trie that end with a given sequence. (Unlike
        str.endswith, this does NOT return a boolean - consider renaming in
        a future version.)
        
        Parameters
        ----------
        seq: Iterable
            Same type as all the other sequences in the trie.
        node: TrieNode
            If provided, only the subtrie starting with this node will be
            searched. Defaults to the head, i.e. the whole trie will be 
            searched.
            
        Returns
        -------
        list: Each item will be one of the sequences in the trie. If an empty
        list is returned, the trie contains no items sharing any trailing
        values with the input `seq`.
        """
        if not self.suffix:
            warnings.warn(
                'Prefix trees are optimized for the `startswith` method, but '
                '`endswith` will require walking the whole trie (may be '
                'slow). For an efficient implementation of `endswith`, you '
                'can create a suffix tree by passing `suffix=True` to '
                'Trie.__init__.'
            )
            if self.dtype == 'str':
                return [v for v in self._values(node=node) 
                        if v.endswith(seq)]
            else:
                self._validate_input(seq)
                length = len(seq)
                return [v for v in self._values(node=node) 
                        if v[-length:] == seq]
        return self._startswith(seq, node=node)

    def _longest_common_prefix(self, seq, seen):
        """Base functionality for the efficient version of 
        `longest_common_prefix` for prefix trees and `longest_common_suffix`
        for suffix trees.
        
        Parameters
        ----------
        seq: Iterable
            Input sequence for which you wish to find sequences with matching
            prefixes (or suffixes). Type must match that of the other 
            sequences in the trie.
        seen: list
            Empty list passed in. Seems to be necessary to accumulate matches.
            
        Returns
        -------
        list: Each item in the list is of the same tyep as `seq`. An empty 
        list means no items in the tree share a common prefix with `seq`.
        """
        # Validation and reversal happens in `startswith`.
        matches = self.endswith(seq) if self.suffix else self.startswith(seq)
        if matches: return matches
        node = self.head
        for i, x in enumerate(self._maybe_reverse(seq)):
            if x in node.edges:
                seen.append(x)
                node = node.edges[x]
            elif i == 0:
                # Otherwise, all values are returned when the first item is 
                # not in the trie.
                return []
            else:
                seen = self._maybe_reverse(self.postprocess(seen))
                if self.suffix:
                    matches = [v + seen for v in self._values(node=node)]
                else:
                    matches = [seen + v for v in self._values(node=node)]
                # Otherwise, we get bug where an empty list is returned if
                # the longest matching prefix is a complete sequence and the
                # node has no edges.
                if node.stop_state and not matches: 
                    matches.append(seen)
                return matches
        
        # Case where the input sequence is present in the trie as a complete
        # sequence and it has no edges. This cannot be combined with the
        # case in the else statement above where matches is empty. We avoid
        # handling this upfront with something like 
        # `if seq in self: return [seq]` because we want to capture additional
        # valid sequences in present.
        if node.stop_state:
            return [self._maybe_reverse(self.postprocess(seen))]
    
    def longest_common_prefix(self, seq):
        """Find sequences that share a common prefix with an input sequence.
        For instance, "carry" shares a common prefix of length 3 with "car",
        "carton", and "carsick", a common prefix of length 1 with "chat", and
        no common prefix with "dog". Note that a word shares a common prefix 
        with itself, so if it's present in the trie it will be returned (in 
        addition to any words that begin with that substring: for instance, 
        both "carry" and "carrying" share a common prefix of length 5 with 
        "carry".)
        
        Parameters
        ----------
        seq: Iterable
            Input sequence for which you wish to find sequences with matching
            prefixes. Type must match that of the other 
            sequences in the trie.
            
        Returns
        -------
        list: Each item in the list is of the same tyep as `seq`. An empty 
        list means no items in the tree share a common prefix with `seq`.
        """
        # Validation occurs in self.startswith, often via self._find.
        if not self.suffix:
            return self._longest_common_prefix(seq, [])
        
        warnings.warn(
            'Suffix trees are optimized for the `longest_common_suffix` '
            'method, but `longest_common_prefix` will require walking '
            'the whole trie (may be slow). For an efficient implementation '
            'of `longest_common_prefix`, you can create a prefix tree by '
            'passing `suffix=False` to Trie.__init__.'
        )
        self._validate_input(seq)
        res = []
        for i in range(len(seq), 0, -1):
            for v in self._values():
                if v[:i] == seq[:i]: res.append(v)
            if res: break
        return res
    
    def longest_common_suffix(self, seq):
        """Find sequences that share a common suffix with an input sequence.
        For instance, "carry" shares a common prefix of length 2 with "story",
        "tawdry", and "ornery", a common suffix of length 1 with "slowly", and
        no common suffix with "hate". Note that a word shares a common suffix 
        with itself, so if it's present in the trie it will be returned (in 
        addition to any words that end with that substring: for instance, both
        "carry" and "miscarry" share a common suffix of length 5 with 
        "carry".)
        
        Parameters
        ----------
        seq: Iterable
            Input sequence for which you wish to find sequences with matching
            suffixes. Type must match that of the other sequences in the trie.
            
        Returns
        -------
        list: Each item in the list is of the same tyep as `seq`. An empty 
        list means no items in the tree share a common prefix with `seq`.
        """
        # Validation and reversal occur in self.endswith, often via 
        # self._find.
        if self.suffix:
            return self._longest_common_prefix(seq, [])
        
        warnings.warn(
            'Prefix trees are optimized for the `longest_common_prefix` '
            'method, but `longest_common_suffix` will require walking the '
            'whole trie (may be slow and memory intensive). For an '
            'efficient implementation of `longest_common_suffix`, you can '
            'create a suffix tree by passing `suffix=True` to Trie.__init__.'
        )
        self._validate_input(seq)
        res = []
        for i in range(len(seq), 0, -1):
            for v in self._values():
                if v[-i:] == seq[-i:]: res.append(v)
            if res: break
        return res
    
    def _validate_input(self, seq):
        """This should occur before calling self._maybe_reverse. Seq must be
        the same type as the other items in the trie or an error will be
        raised.
        """
        if type(seq).__name__ != self.dtype:
            raise TypeError('`seq` type doesn\'t match type of other '
                            'sequences.')
        if type(seq[0]).__name__ != self.child_dtype:
            raise TypeError('Type of first item in `seq` doesn\'t match type '
                            'of first item in other sequences.')
            
    def flip(self):
        """Flip trie from a prefix tree to a suffix tree or vice versa. This
        intentionally creates a new object rather than operating in place.
        
        Examples
        --------
        >>> pre_tree = Trie(['dog', 'cat', 'den', 'clean'], suffix=False)
        >>> suff_tree = pre_tree.flip()
        """
        return type(self)(self.values(), suffix=not self.suffix)
    
    def __repr__(self):
        # Display up to 5 values in repr.
        vals = self.values()
        if len(vals) > 5:
            vals = '[' + ', '.join(repr(v) for v in vals[:5]) + ', ...]'
        else:
            vals = str(vals)
        return f'{type(self).__name__}(values={vals}, suffix={self.suffix})'<jupyter_output><empty_output><jupyter_text>Other Ideas- some sort of distance(seq1, seq2) method    [UPDATE: no immediate use case for this and don't have any particular distance measure in mind. Put on hold.]    - typos/neighbors (see Terence's slides)    [UPDATE: No immediate need for this. Put on hold.]    - let user pass in kv pair (e.g. could use this as a w2i dict). However,I think this might require a dramatically different interface. Or could I just make it so that we only use this functionality if you pass in a dict or list of dicts? Prob much slower than a dict so I don't know if we'd actually want to use it in that case. Passing in a dict might also be problematic for my reversal function and type checking.    [UPDATE: put this on hold for now. I've written everything envisioning more of a sequence than a mapping structure. Don't have an immediate use for trie regardless so maybe wait and see what potential use cases come up now that I have this in mind.]  T - str<jupyter_code>t = Trie(['dolphin', 'deer'], suffix=False)
t
save(t, '../data/trie.pkl')
t.append('star')
t.append('study')
t.append('apple')
t.append('larkin')
t.append('app')
t.append('castle')
t.append('lake')
t.append('cake')
t + 'cattle'
t.values()
t.endswith('hin')
# Notice endswith no longer throws warning because it's a suffix tree now.
t.reverse().endswith('hin')
assert 'app' in t
assert 'apple' in t
assert 'ap' not in t
assert 'appleton' not in t
assert 'fox' not in t
tmp = t + 'candy'
assert 'candy' in tmp
assert not 'candy' in t
t += 'car'
t += 'stunning'
t += 'stir'
t += 'sorry'
t.extend(['sturdy', 'stipend', 'cold'])
t.startswith('stu')
t.startswith('ap')
t.startswith('ca')
t.startswith('zzz')
t.endswith('ke')
with assert_raises(TypeError):
    t.startswith(['n'])
with assert_raises(TypeError):
    t += ['a', 'b']
t.values()
# TODO: version of assert that prints result? I like to see output just to 
# make sure even though it shouldn't matter.
res = t.longest_common_prefix('applicable')
print(res)
assert res == ['apple']
res = t.longest_common_prefix('app')
print(res)
assert res == ['app', 'apple']
res = t.longest_common_prefix('apple')
print(res)
assert res == ['apple']
res = t.longest_common_prefix('appleton')
print(res)
assert res == ['apple']
res = t.longest_common_prefix('candid')
print(res)
assert res == ['castle', 'cake', 'car']
res = t.longest_common_prefix('zoo')
print(res)
assert res == []
res = t.longest_common_prefix('castlegate')
print(res)
assert res == ['castle']
res = t.longest_common_prefix('apptive')
print(res)
assert res == ['app', 'apple']
res = t.longest_common_prefix('card')
print(res)
assert res == ['car']
with assert_raises(TypeError):
    t.longest_common_prefix(['abc', 'def'])
# brute force method
res = t.longest_common_suffix('ornery')
print(res)
assert res == ['sorry']
# brute force method
res = t.longest_common_suffix('stir')
print(res)
assert res == ['stir']
# brute force method
res = t.longest_common_suffix('stirring')
print(res)
assert res == ['stunning']
# brute force method
res = t.longest_common_suffix('nest')
print(res)
assert res == []<jupyter_output>[]<jupyter_text>T2: list[str]Each sequence is a list of strings (NOT nested).<jupyter_code>t2 = Trie()
t2.append(['I',  'went', 'to', 'school', 'today', '.'])
t2.append(['I',  'like', 'horses', '.'])
t2.append(['He', 'is', 'home', 'early', '.'])
t2.append(['I', 'went', 'to', 'the', 'beach', '.'])
t2.values()
t2.startswith(['I'])
t2.endswith(['today', '.'])
t2.endswith(['.'])
t2.extend([['Hot', 'chocolate'], ['sandy', 'beach']])
with assert_raises(TypeError):
    t2.startswith('h')
with assert_raises(TypeError):
    t2 += (3, 4)
with assert_raises(TypeError):
    t2.append([1, 2, 3])
res = t2.longest_common_prefix(['I', 'went', 'to', 'the', 'movies', 
                                'yesterday', '.'])
print(res)
assert res == [['I', 'went', 'to', 'the', 'beach', '.']]
res = t2.longest_common_prefix(['I', 'went', 'to', 'an', 'amusement', 'park',
                                '.'])
print(res)
assert res == [['I', 'went', 'to', 'school', 'today', '.'],
               ['I', 'went', 'to', 'the', 'beach', '.']]
res = t2.longest_common_prefix(['You', 'can', 'sometimes', 'tell', 'the', 
                                'difference', '.'])
print(res)
assert res == []
# brute force
res = t2.longest_common_suffix(['Who', 'is', 'there', '?'])
print(res)
assert res == []
# brute force
res = t2.longest_common_suffix(['Hmm', '.'])
print(res)
assert res == [['I', 'went', 'to', 'school', 'today', '.'],
               ['I', 'went', 'to', 'the', 'beach', '.'],
               ['I', 'like', 'horses', '.'],
               ['He', 'is', 'home', 'early', '.']]
t2.values()<jupyter_output><empty_output><jupyter_text>T3: list[tuple[str]]Each sequence is a list of tuples where each tuple contains one or more strings (nested).<jupyter_code>ex = [
    'It is cold and windy.',
    'The food was still hot.',
    'It is not warm.',
    'The cow mooed loudly.',
    'It is cold and snowy.'
]

t3 = Trie()
for e in ex:
    item = list(map(tuple, ngrams(e.split(), 2, 2, False)))
    print(item)
    t3.append(item)
objviz(t3)
t3.values()
with assert_raises(TypeError):
    t3.append(('It', 'is'))
with assert_raises(TypeError):
    t3.append(['It', 'is'])
t3.append([('It', 'is')])
t3.startswith([('It', 'is')])
t3.startswith([('It', 'is'), ('cold', 'and')])
with assert_raises(TypeError):
    t3.startswith(['It', 'is', 'cold', 'and'])
res = t3.endswith([('mooed', 'loudly.')])
print(res)
assert res == [[('The', 'cow'), ('mooed', 'loudly.')]]
res = t3.endswith([('mooed',)])
print(res)
assert not res
t3.values()
res = t3.longest_common_prefix([('The', 'food'), ('never', 'came'), ('.',)])
print(res)
assert res == [[('The', 'food'), ('was', 'still'), ('hot.',)]]
res = t3.longest_common_prefix([('It', 'is'), ('cold', 'and'),
                                ('rainy', '.',)])
print(res)
assert res == [[('It', 'is'), ('cold', 'and'), ('windy.',)],
               [('It', 'is'), ('cold', 'and'), ('snowy.',)]]
res = t3.longest_common_prefix([('It', 'is'), ('cold', 'and'), ('windy.',)])
print(res)
assert res == [[('It', 'is'), ('cold', 'and'), ('windy.',)]]
res = t3.longest_common_prefix([('zigzag', 'hope')])
print(res)
assert not res
res = t3.longest_common_suffix([('So',), ('It', 'is')])
print(res)
assert res == [[('It', 'is')]]<jupyter_output>[[('It', 'is')]]<jupyter_text>T4: list[int]Each sequence is a list of integers (NOT nested).<jupyter_code>t4 = Trie([[2, 3, 5], [2, 3, 4]])
objviz(t4)
res = t4.startswith([2])
print(res)
assert res == [[2, 3, 5], [2, 3, 4]]
res = t4.endswith([3, 5])
print(res)
assert res == [[2, 3, 5]]
t4.append([1, 4, 9, 7, 5])
t4.extend([[2, 3, 5, 7], [2, 3, 1, 4, 99]])
t4.values()
res = t4.longest_common_prefix([2, 3, 1, 700, -1, 11])
print(res)
assert res == [[2, 3, 1, 4, 99]]
# Consider what desired behavior is here. ValueError is an option too. 
with assert_raises(IndexError):
    t4.longest_common_prefix([])
res = t4.longest_common_suffix([1, 2, 5])
print(res)
assert res == [[2, 3, 5], [1, 4, 9, 7, 5]]<jupyter_output>[[2, 3, 5], [1, 4, 9, 7, 5]]<jupyter_text>T5: list[tuple[int]]Each sequence is a list of tuples where each tuple contains one or more ints (nested).<jupyter_code>t5 = Trie([[(2, 3, 5), (2, 3, 4)]])
t5.append([(4, 3, 4), (1, 1, 1)])
t5.extend([[(-1, 0, 100)], [(9, 99)]])
t5 += [(0,)]
t5 = t5 + [(4, 4, 4, 4), ()]
t5.append([(2, 3, 5), (-100, -100)])
objviz(t5)
t5.startswith([(2, 3, 5)])
t5.longest_common_prefix([(2, 3, 5), (9, 100)])
# Consider if this is desired behavior. We check each item in the sequence
# but we don't check subcomponents of each item (e.g. you could argue that
# [(2, 3, 5), (2, 3, 4)] should be the only result because it shares more)
# digits with the input. But I suppose we should treat each item as a 
# standalone element - otherwise we could pass in a list of ints rather than
# a list of tuples of ints. I think this is working as it should.
t5.longest_common_prefix([(2, 3, 5), (2, 3, 100000)])
res = t5.longest_common_suffix([(1, 100), (9, 99)])
print(res)
assert res == [[(9, 99)]]<jupyter_output>[[(9, 99)]]<jupyter_text>T6: list[str], suffixSuffix tree where each sequence is a string (NOT nested).<jupyter_code>t6 = Trie(['dolphin', 'deer'], suffix=True)
t6.append('star')
t6 += 'study'
t6 = t6 + 'apple'
t6.extend(['larkin', 'app'])
t6.append('castle')
t6.append('lake')
t6.append('cake')

objviz(t6)
assert all(term in t6
           for term in ('dolphin', 'star', 'study', 'apple', 'larkin', 'app'))
assert 'zebra' not in t6
assert 'dolphin'[::-1] not in t6
res = t6.startswith('ap')
print(res)
assert res == ['apple', 'app']
res = t6.endswith('in')
print(res)
assert res == ['dolphin', 'larkin']
res = t6.startswith('ni')
print(res)
assert not res
t6.values()
res = t6.longest_common_prefix('lard')
print(res)
assert res == ['larkin']
res = t6.longest_common_prefix('kin')
print(res)
assert not res
res = t6.longest_common_suffix('zzxlkj')
print(res)
assert not res
res = t6.longest_common_suffix('fantastle')
print(res)
assert res == ['castle']
res = t6.longest_common_suffix('tle')
print(res)
assert res == ['castle']
res = t6.longest_common_suffix('acastle')
print(res)
assert res == ['castle']
def _longest_common_prefix(self, seq, seen):    
    # Validation and reversal happens in `startswith`.
    matches = self.startswith(seq)
    if matches: return matches
    node = self.head
    for i, x in enumerate(seq):
        if x in node.edges:
            seen.append(x)
            node = node.edges[x]
        elif i == 0:
            # Otherwise, all values are returned when the first item is 
            # not in the trie.
            return []
        else:
            matches = [self.postprocess(seen + list(v)) 
                       for v in self._values([], [], node)]
            # Otherwise, we get bug where an empty list is returned if
            # the longest matching prefix is a complete sequence and the
            # node has no edges.
            if node.stop_state and not matches: 
                matches.append(self.postprocess(seen))
            return matches
               
    # Case where the input sequence is present in the trie as a complete
    # sequence and it has no edges. This cannot be combined with the
    # case in the else statement above where matches is empty. We avoid
    # handling this upfront with something like 
    # `if seq in self: return [seq]` because we want to capture additional
    # valid sequences in present.
    if node.stop_state:
        return [self.postprocess(seen)]

def _longest_common_suffix(self, seq, seen):
    # TODO: refactor this into _longest_common_prefix. Just 
    # experimenting for now to get longest_common_suffix working.
    # AHA: Validation and reversal happens in `startswith` but if no matches
    # are found, we then act on the original sequence in the for loop.
    matches = self.endswith(seq) # diff: endswith vs startswith
    if matches: 
        print('found matches')
        return matches
    node = self.head
    for i, x in enumerate(self._maybe_reverse(seq)): # diff: reverse
        if x in node.edges:
            print('found x', x)
            seen.append(x)
            node = node.edges[x]
        elif i == 0:
            # Otherwise, all values are returned when the first item is 
            # not in the trie.
            print('first char not found')
            return []
        else:
            # Case where item not found in edges, i.e. the rest of the 
            # sequence will diverge from whatever is present in the trie.
            print('NOT FOUND', x, 'seen', seen)
            print('values', self._values([], [], node))
            # _values returns items postprocessed and reversed if necessary,
            # so do this to `seen` before combining.
            seen = self._maybe_reverse(self.postprocess(seen))
            matches = [v + seen for v in self._values([], [], node)]
            if node.stop_state and not matches: 
                print('no edges')
                matches.append(seen)
            return matches
        
    if node.stop_state:
        print('after for')
        return [self._maybe_reverse(self.postprocess(seen))] # diff: post
res = t6.longest_common_suffix('acastle')
print(res)
assert res == ['castle']
res = t6.longest_common_suffix('jastle')
print(res)
assert res == ['castle']
res = t6.longest_common_suffix('haloparkin')
print(res)
assert res == ['larkin']
res = t6.longest_common_suffix('truly')
print(res)
assert res == ['study']
res = t6.longest_common_suffix('xyz')
print(res)
assert not res
res = t6.longest_common_suffix('deer')
print(res)
assert res == ['deer']
res = t6.longest_common_prefix('dollar')
print(res)
assert res == ['dolphin']
res = t6.longest_common_prefix('blink')
print(res)
assert not res<jupyter_output>[]<jupyter_text>Like startswith, there is no efficient implementation of longest_common_prefix for suffix tree. Need to do it brute force way.<jupyter_code>def brute_longest_common_prefix(self, seq):
    res = []
    for i in range(len(seq), 0, -1):
        for v in self.values():
            if v[:i] == seq[:i]: res.append(v)
        if res: break
    return res
brute_longest_common_prefix(t6, 'zzz')
brute_longest_common_prefix(t6, 'dolphin')
brute_longest_common_prefix(t6, 'skid')
brute_longest_common_prefix(t6, 'stack')
brute_longest_common_prefix(t6, 'star')
brute_longest_common_prefix(t6, 'starring')<jupyter_output><empty_output><jupyter_text>T7: list[str], suffixSuffix tree where each sequence is a list of strings (NOT nested).<jupyter_code>t7 = Trie(suffix=True)
t7.append(['I',  'went', 'to', 'school', 'today', '.'])
t7.append(['I',  'like', 'horses', '.'])
t7.append(['He', 'is', 'home', 'early', '.'])
t7.append(['I', 'went', 'to', 'the', 'beach', '.'])
t7.append(['I', 'went', 'to', 'bed', 'early', '.'])
objviz(t7)
t7.values()
res = t7.startswith(['I', 'went'])
print(res)
assert res == [['I', 'went', 'to', 'school', 'today', '.'],
               ['I', 'went', 'to', 'bed', 'early', '.'],
               ['I', 'went', 'to', 'the', 'beach', '.']]
res = t7.endswith(['like', 'horses', '.'])
print(res)
assert res == [['I', 'like', 'horses', '.']]
res = t7.endswith(['I'])
print(res)
assert not res
res = t7.endswith(['early', '.'])
print(res)
assert res == [['He', 'is', 'home', 'early', '.'], 
               ['I', 'went', 'to', 'bed', 'early', '.']]
res = t7.longest_common_prefix(['I', 'went', 'to', 'the', 'hospital', '.'])
print(res)
assert res == [['I', 'went', 'to', 'the', 'beach', '.']]
res = t7.longest_common_suffix(['I', 'went', 'to', 'the', 'hospital', '.'])
print(res)
assert res == [['I', 'went', 'to', 'school', 'today', '.'],
               ['I', 'like', 'horses', '.'],
               ['He', 'is', 'home', 'early', '.'],
               ['I', 'went', 'to', 'bed', 'early', '.'],
               ['I', 'went', 'to', 'the', 'beach', '.']]
res = t7.longest_common_suffix(['I', 'went', 'to', 'sleep', 'early', '.'])
print(res)
assert res == [['He', 'is', 'home', 'early', '.'], 
               ['I', 'went', 'to', 'bed', 'early', '.']]
res = t7.longest_common_suffix(['I', 'went', 'to', 'bed', 'early', '.'])
print(res)
assert res == [['I', 'went', 'to', 'bed', 'early', '.']]
res = t7.longest_common_prefix(['I', 'went', 'home', 'late', '.'])
print(res)
assert res == [['I', 'went', 'to', 'school', 'today', '.'],
               ['I', 'went', 'to', 'bed', 'early', '.'],
               ['I', 'went', 'to', 'the', 'beach', '.']]
res = t7.longest_common_prefix(['I', 'went', 'to'])
print(res)
assert res == [['I', 'went', 'to', 'school', 'today', '.'],
               ['I', 'went', 'to', 'bed', 'early', '.'],
               ['I', 'went', 'to', 'the', 'beach', '.']]
res = t7.longest_common_prefix(['I', 'went', 'to', 'school', 'today', '.'])
print(res)
assert res == [['I', 'went', 'to', 'school', 'today', '.']]
res = t7.longest_common_prefix(['I', 'went', 'to', 'school', 'today', '.', 
                                'Test'])
print(res)
assert res == [['I', 'went', 'to', 'school', 'today', '.']]
# @debug
def _values(self, current=None, node=None):
    """Traverse all values starting from a given node and return them as a
    list. If a node is not explicitly provided, the head will be used and
    all values in the trie will be retrieved.
    """
    node = node or self.head
    current = current or []
    if node.stop_state:
        # Here, reversal is more of a postprocessing step than a 
        # preprocessing one: we're converting the reversed word stored in
        # the suffix tree back to its original order.
        yield self._maybe_reverse(self.postprocess(current))
    for key, node_ in node.edges.items():
        yield from _values(self, current+[key], node_)
for v in _values(t):
    print('V', v)
for x in _values(t):
    print(x, end=' ')
glove = load('/Users/hmamin/data/glove/glove.6B.50d.txt')
words = [line.split()[0] for line in glove.splitlines()]
words[:8]
'zoo' in words
t8 = Trie(words)
t8
'zoo' in t8
len(t8)
assert len(t8) == len(words)
't' in words, 'th' in words
eprint(sorted(t8.head.edges.keys()))
[w for w in words if w.startswith('diag')]
# ~1/7 the time with list
t8.startswith('diag')
# Much slower than even a list.
t8.endswith('iag')
# Flipping to suffix trie is even slower.
t8.flip().endswith('iag')
t8.longest_common_prefix('fantasm')
'fantasm' in t8
# ~30x slower than longest_common_prefix bc we're using a prefix tree.
t8.longest_common_suffix('fantasm')<jupyter_output>/Users/hmamin/anaconda3/lib/python3.7/site-packages/ipykernel_launcher.py:359: UserWarning: Prefix trees are optimized for the `longest_common_prefix` method, but `longest_common_suffix` will require walking the whole trie (may be slow and memory intensive). For an efficient implementation of `longest_common_suffix`, you can create a suffix tree by passing `suffix=True` to Trie.__init__.
{'fraction_non_alphanumeric': 0.1382948630911971, 'fraction_numerical': 0.009391264992079656, 'mean_word_length': 2.4487367086137937, 'pattern_counts': {'":': 0, '<': 31, '<?xml version=': 0, '>': 44, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '9', 'dir': 'jupyter-structured-clean-dedup', 'id': '548873', 'license': 'MIT', 'n_tokens_mistral': 11258, 'n_tokens_neox': 10762, 'n_words': 3754, 'path': 'notebooks/trie.ipynb', 'repo_name': 'hdmamin/htools', 'size': '35352'}