<commit_before># -*- coding: utf-8 -*-

_SENTINEL = ()

class Trie(object) :
    __slots__ = ['root']

    def __init__( self ) :
        self.root = [None,{}]

    def __getstate__( self ) :
        if any(self.root) :
            return self.root
        else :
            return False

    def __setstate__(self, s) :
        self.root = s

    def __contains__( self, s ) :
        if self.find_full_match(s,_SENTINEL) is _SENTINEL :
            return False
        return True

    def add( self, key, value ) :
        curr_node = self.root
        for ch in key :
            node = curr_node[1]
            if ch in node :
                curr_node = node[ch]
            else :
                curr_node = node[ch] = [None,{}]
        curr_node[0] = value

    def _find_prefix_match( self, key ) :
        curr_node = self.root
        remainder = key
        for ch in key :
            if ch in curr_node[1] :
                curr_node = curr_node[1][ch]
            else :
                break
            remainder = remainder[1:]
        return [curr_node,remainder]

    def find_full_match( self, key, fallback=None ) :
        '''
        Returns the value associated with the key if found else, returns fallback
        '''
        r = self._find_prefix_match( key )
        if not r[1] and r[0] :
            return r[0][0]
        return fallback

    def find_prefix_matches( self, prefix ) :
        l = self._find_prefix_match( prefix )
        if l[1] :
            return []
        stack = [l[0]]
        ret = []
        while stack :
            d = stack.pop()
            if d[0] :
                ret.insert(0,d[0])
            for c in d[1] :
                stack.append(d[1][c])
        return ret

def test() :
    d = {
        'python'  : 1,
        'color'   : 2,
        'colorful': 3,
        'pythonic': 4
    }
    t = Trie()
    for k in d :
        t.add(k,d[k])
    assert set(t.find_prefix_matches('py')) == set([d['python'],d['pythonic']])
    assert set(t.find_prefix_matches('colo')) == set([d['color'],d['colorful']])
    assert not t.find_prefix_matches('foo')
    t.add('foobar',5)
    assert t.find_prefix_matches('foo') == [5]

if __name__ == '__main__' :
    test()<commit_msg>Added credits to James Tauber's trie.py and removed the useless test function from trie.py<commit_after># -*- coding: utf-8 -*-
'''
The trie object is based on James Tauber's trie.py
http://jtauber.com/2005/02/trie.py
'''

_SENTINEL = ()

class Trie(object) :
    __slots__ = ['root']

    def __init__( self ) :
        self.root = [None,{}]

    def __getstate__( self ) :
        if any(self.root) :
            return self.root
        else :
            return False

    def __setstate__(self, s) :
        self.root = s

    def __contains__( self, s ) :
        if self.find_full_match(s,_SENTINEL) is _SENTINEL :
            return False
        return True

    def add( self, key, value ) :
        curr_node = self.root
        for ch in key :
            node = curr_node[1]
            if ch in node :
                curr_node = node[ch]
            else :
                curr_node = node[ch] = [None,{}]
        curr_node[0] = value

    def _find_prefix_match( self, key ) :
        curr_node = self.root
        remainder = key
        for ch in key :
            if ch in curr_node[1] :
                curr_node = curr_node[1][ch]
            else :
                break
            remainder = remainder[1:]
        return [curr_node,remainder]

    def find_full_match( self, key, fallback=None ) :
        '''
        Returns the value associated with the key if found else, returns fallback
        '''
        r = self._find_prefix_match( key )
        if not r[1] and r[0] :
            return r[0][0]
        return fallback

    def find_prefix_matches( self, prefix ) :
        l = self._find_prefix_match( prefix )
        if l[1] :
            return []
        stack = [l[0]]
        ret = []
        while stack :
            d = stack.pop()
            if d[0] :
                ret.insert(0,d[0])
            for c in d[1] :
                stack.append(d[1][c])
        return ret
{'fraction_non_alphanumeric': 0.1157920077034184, 'fraction_numerical': 0.011073663938372653, 'mean_word_length': 1.5443968156766688, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 3, '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}}
{'dir': 'git-commits-cleaned', 'id': '6223154', 'n_tokens_mistral': 1350, 'n_tokens_neox': 1321, 'n_words': 347}