class Node:
    def __init__(self):
        self.end = False
        self.children = {}

    def autocomplete(self, prefix):
        # we're at the end of a word, yield the result
        if self.end:
            yield prefix

        # else, recurse over each child-character
        # of the current node and append the 
        # corresponding letter to the prefix
        # -> this will build up the autocompleted string
        for letter, child in self.children.items():
            yield from child.autocomplete(prefix + letter)

class Trie:
    def __init__(self):
        self.root = Node()

    def insert(self, word):
        cur = self.root
        for c in word:
            if c not in cur.children:
                cur.children[c] = Node()
            cur = cur.children[c]
        cur.end = True

    def autocomplete(self, word):
        cur = self.root
        # starting at the root
        # traverse the trie for each 
        # character in `word`
        for c in word:
            cur = cur.children.get(c)
            if cur is None:  # word does not exist in our trie
                return
        
        # recursively autocomplete all possible words
        # starting at the final character node
        yield from cur.autocomplete(word)

if __name__ == '__main__':
    trie = Trie()
    trie.insert('foobar')
    trie.insert('foo')
    trie.insert('foob')
    trie.insert('foor')
    trie.insert('bar')

    print(list(trie.autocomplete('foo')))

apoehlmann:~/workspace/telegram-bot$ python trie.py 
['foo', 'foob', 'foobar', 'foof']

class TelegramBot:
    def __init__(self, api_key, crypto_client):
        self.crypto_client = crypto_client
        self.markets, self.market_names_perp_usd = [], []
        self.update_markets()

        self.trie = None
        self.init_trie(self.market_names_perp_usd)

        # Create the Updater and pass it your bot's token.
        self.updater = Updater(api_key)
        # Get the dispatcher to register handlers
        self.dispatcher = self.updater.dispatcher

        # on different commands - answer in Telegram
        self.dispatcher.add_handler(CommandHandler("cprice", self.cprice))
        self.dispatcher.add_handler(CommandHandler("cp", self.cprice))

        inline_price_handler = InlineQueryHandler(self.inline_price)
        self.dispatcher.add_handler(inline_price_handler)

        unknown_handler = MessageHandler(Filters.command, self.unknown)
        self.dispatcher.add_handler(unknown_handler)

    def update_markets(self, with_trie=False):
        self.markets = [coin for coin in self.crypto_client._get(f"markets")]
        self.market_names_perp_usd = [entry["name"] for entry in self.markets
                                      if entry["name"].endswith('PERP') or
                                      entry["name"].endswith('USD')]
        if with_trie:
            self.update_trie(self.market_names_perp_usd)

    def init_trie(self, words=[]):
        self.trie = Trie()
        self.update_trie(words)

    def update_trie(self, words):
        if self.trie is None:
            self.trie = Trie()
        for word in words:
            self.trie.insert(word)

    def start_bot(self):
        # Start the Bot
        self.updater.start_polling()

        # Run the bot until you press Ctrl-C or the process receives SIGINT,
        # SIGTERM or SIGABRT. This should be used most of the time, since
        # start_polling() is non-blocking and will stop the bot gracefully.
        self.updater.idle()

    def cprice(self, update: Update, context: CallbackContext) -> None:
        # context.args is a list that contains all space separated strings
        # following the command, e.g. /cprice xrp btc -> ["xrp", "btc"]
        coins = context.args
        # get markets data via the crypto client
        # and update the trie at the same time
        # so we add new symbols if any new ones appeared since
        # the last time we queried the exchange
        self.update_markets(with_trie=True)

        # for each coin symbol provided by in the query
        text = ''
        for coin in coins:
            # transform it to uppercase first
            # because the FTX market names are all uppercase
            coin_upper = coin.upper()
            found = False

            # for each market entry fetched from the exchange
            for entry in self.markets:
                # if there's a match with our crypto symbol
                if entry['name'].startswith(coin_upper):
                    found = True
                    # append it to our string result
                    text += f'{entry["name"]} price: {entry["last"]}\n' \
                            f'Last 01h: {100 * entry["change1h"]:.2f}%\n' \
                            f'Last 24h: {100 * entry["change24h"]:.2f}%\n\n'
                    break
            if not found:
                text += f'Sorry, no crypto symbol starting with {coin.upper()} has been found.\n\n'
        context.bot.send_message(chat_id=update.effective_chat.id, text=text)

    def inline_price(self, update, context):
        query = update.inline_query.query.upper()
        if not query:
            return
            
        # get a generator of autocompleted words 
        autocompleted = self.trie.autocomplete(query)
        if autocompleted is not None:
            ac = set(autocompleted)
            # for each crypto coin, create a InlineQueryResultArticle
            # if the name is present in the set of autocompleted symbols
            # finally, sort the result alphabetically 
            results = sorted([
                InlineQueryResultArticle(
                    id=coin['name'],
                    title=coin['name'],
                    input_message_content=InputTextMessageContent(f'/cp {coin["name"]}')
                ) for coin in self.markets if coin['name'] in ac
            ], key=lambda x: x.id)
            context.bot.answer_inline_query(update.inline_query.id, results[:50])

    def unknown(self, update, context):
        context.bot.send_message(chat_id=update.effective_chat.id, text="Sorry, I didn't understand that command.")