trie

// interface
add-word(word)
bool is-word(word)
string[] get-all-words()
string[] get-words-by(prefix)
string[] get-longest-words()
remove-word(word)

trienode:
    // members
    char c
    map<char, trienode> children
    int wordcount
    trienode parent
    
    // ctors
    trienode(c, parent):
        c = c
        children = new
        wordcount = 0
        parent = parent
    
    // methods
    is-word():
        return wordcount > 0

trie:
    // members
    root = new trienode(' ', parent: null)
    
    // methods
    add-word(word):
        node = root
        foreach c in word:
            child = node.children[c]
            if child == null:
                child = new trienode(c: c, parent: node)
                node.children[c] = child
            node = child
        node.wordcount++
    
    is-word(word):
        node = get-trienode-by(word)
        return node != null && node.is-word()
    
    get-all-words():
        return get-words-wrapper(root, prefix: "")
    get-words-by(prefix):
        node = get-trienode-by(prefix)
        if node != null:
            words = get-words-wrapper(node, prefix)
        else:
            words = new // empty if prefix does not exists
        return words
    get-words-wrapper(node, prefix):
        words = new
        get-words-recursive(words, node, new buffer(prefix))
        return words
    get-words-recursive(words, node, buffer):
        if node.is-word():
            words.add(buffer.tostring())
        foreach child in node.children:
            buffer.append(child.c)
            get-words-recursive(words, child, buffer):
            buffer.length--
    get-trienode-by(s):
        node = root
        foreach c in s:
            node = node.children[c]
            if node == null:
                break
        return node
    
    get-longest-words():
        words = new
        length = 0
        get-longest-words-recursive(words, root, new buffer(), ref length):
        return words
    get-longest-words-recursive(words, node, buffer, ref length):
        if node.is-word():
            if buffer.length > length:
                words.clear()
                length = buffer.length
            if buffer.length == length:
                words.add(buffer.tostring())
        foreach child in node.children:
            buffer.append(child.c)
            get-longest-words-recursive(words, child, buffer, ref length):
            buffer.length--
    
    remove-word(word):
        node = get-trienode-by(word)
        if node == null || !node.is-word():
            throw
        node.wordcount = 0
        while node.children.count == 0 && !node.is-word() && node != root:
            parent = node.parent
            parent.children.remove(node.c)
            node.parent = null
            node = parent