# A RouteTrieNode will be similar to our autocomplete TrieNode... with one additional element, a handler.
class RouteTrieNode:
    def __init__(self):
        # Initialize the node with children as before, plus a handler
        self.handler = None
        self.children = {}

    def insert(self, segment, handler=None):
        # Insert the node as before
        self.children[segment] = RouteTrieNode()
        self.children[segment].handler = handler
        return self.children[segment]


# A RouteTrie will store our routes and their associated handlers
class RouteTrie:
    def __init__(self):
        # Initialize the trie with an root node and a handler, this is the root path or home page node
        self.root = RouteTrieNode()

    def insert(self, path, handler):
        # Similar to our previous example you will want to recursively add nodes
        # Make sure you assign the handler to only the leaf (deepest) node of this path
        current = self.root
        for segment in path:
            if segment != '':
                if segment not in current.children:
                    current.insert(segment)
                current = current.children[segment]
        current.handler = handler

    def find(self, path):
        # Starting at the root, navigate the Trie to find a match for this path
        # Return the handler for a match, or None for no match
        current = self.root
        for segment in path:
            if segment != '':
                if segment not in current.children:
                    return None
                current = current.children[segment]

        return current.handler


# The Router class will wrap the Trie and handle
class Router:
    def __init__(self, root_handler, handler_404):
        # Create a new RouteTrie for holding our routes
        # You could also add a handler for 404 page not found responses as well!
        # "root handler", "not found handler"
        self.trie = RouteTrie()
        self.root_handler = root_handler
        self.handler_404 = handler_404

    def add_handler(self, path, handler):
        # Add a handler for a path
        # You will need to split the path and pass the pass parts
        # as a list to the RouteTrie
        self.trie.insert(self.split_path(path), handler)

    def lookup(self, path):
        # lookup path (by parts) and return the associated handler
        # you can return None if it's not found or
        # return the "not found" handler if you added one
        # bonus points if a path works with and without a trailing slash
        # e.g. /about and /about/ both return the /about handler
        if path == '/':
            return self.root_handler

        handler = self.trie.find(self.split_path(path))

        if handler is None:
            return self.handler_404

        return handler

    def split_path(self, path):
        # you need to split the path into parts for
        # both the add_handler and loopup functions,
        # so it should be placed in a function here
        return path.split('/')


# Here are some test cases and expected outputs you can use to test your implementation
# create the router and add a route
router = Router("root handler", "not found handler")  # remove the 'not found handler' if you did not implement this
router.add_handler("/home/about", "about handler")  # add a route

# some lookups with the expected output
print(router.lookup("/"))  # should print 'root handler'
print(router.lookup("/home"))  # should print 'not found handler' or None if you did not implement one
print(router.lookup("/home/about"))  # should print 'about handler'
print(router.lookup("/home/about/"))  # should print 'about handler' or None if you did not handle trailing slashes
print(router.lookup("/home/about/me"))  # should print 'not found handler' or None if you did not implement one

# A RouteTrieNode will be similar to our autocomplete TrieNode... with one additional element, a handler.
class RouteTrieNode:
    def __init__(self):
        # Initialize the node with children as before, plus a handler
        self.handler = None
        self.children = {}

    def insert(self, segment, handler=None):
        # Insert the node as before
        self.children[segment] = RouteTrieNode()
        self.children[segment].handler = handler
        return self.children[segment]


# A RouteTrie will store our routes and their associated handlers
class RouteTrie:
    def __init__(self):
        # Initialize the trie with an root node and a handler, this is the root path or home page node
        self.root = RouteTrieNode()

    def insert(self, path, handler):
        # Similar to our previous example you will want to recursively add nodes
        # Make sure you assign the handler to only the leaf (deepest) node of this path
        current = self.root
        for segment in path:
            if segment != '':
                if segment not in current.children:
                    current.insert(segment)
                current = current.children[segment]
        current.handler = handler

    def find(self, path):
        # Starting at the root, navigate the Trie to find a match for this path
        # Return the handler for a match, or None for no match
        current = self.root
        for segment in path:
            if segment != '':
                if segment not in current.children:
                    return None
                current = current.children[segment]

        return current.handler


# The Router class will wrap the Trie and handle
class Router:
    def __init__(self, root_handler, handler_404):
        # Create a new RouteTrie for holding our routes
        # You could also add a handler for 404 page not found responses as well!
        # "root handler", "not found handler"
        self.trie = RouteTrie()
        self.root_handler = root_handler
        self.handler_404 = handler_404

    def add_handler(self, path, handler):
        # Add a handler for a path
        # You will need to split the path and pass the pass parts
        # as a list to the RouteTrie
        self.trie.insert(self.split_path(path), handler)

    def lookup(self, path):
        # lookup path (by parts) and return the associated handler
        # you can return None if it's not found or
        # return the "not found" handler if you added one
        # bonus points if a path works with and without a trailing slash
        # e.g. /about and /about/ both return the /about handler
        if path == '/':
            return self.root_handler

        handler = self.trie.find(self.split_path(path))

        if handler is None:
            return self.handler_404

        return handler

    def split_path(self, path):
        # you need to split the path into parts for
        # both the add_handler and loopup functions,
        # so it should be placed in a function here
        return path.split('/')


# Here are some test cases and expected outputs you can use to test your implementation
# create the router and add a route
router = Router("root handler", "not found handler")  # remove the 'not found handler' if you did not implement this
router.add_handler("/home/about", "about handler")  # add a route

# some lookups with the expected output
print(router.lookup("/"))  # should print 'root handler'
print(router.lookup("/home"))  # should print 'not found handler' or None if you did not implement one
print(router.lookup("/home/about"))  # should print 'about handler'
print(router.lookup("/home/about/"))  # should print 'about handler' or None if you did not handle trailing slashes
print(router.lookup("/home/about/me"))  # should print 'not found handler' or None if you did not implement one

# A RouteTrieNode will be similar to our autocomplete TrieNode... with one additional element, a handler. # Initialize the node with children as before, plus a handler # Insert the node as before # A RouteTrie will store our routes and their associated handlers # Initialize the trie with an root node and a handler, this is the root path or home page node # Similar to our previous example you will want to recursively add nodes # Make sure you assign the handler to only the leaf (deepest) node of this path # Starting at the root, navigate the Trie to find a match for this path # Return the handler for a match, or None for no match # The Router class will wrap the Trie and handle # Create a new RouteTrie for holding our routes # You could also add a handler for 404 page not found responses as well! # "root handler", "not found handler" # Add a handler for a path # You will need to split the path and pass the pass parts # as a list to the RouteTrie # lookup path (by parts) and return the associated handler # you can return None if it's not found or # return the "not found" handler if you added one # bonus points if a path works with and without a trailing slash # e.g. /about and /about/ both return the /about handler # you need to split the path into parts for # both the add_handler and loopup functions, # so it should be placed in a function here # Here are some test cases and expected outputs you can use to test your implementation # create the router and add a route # remove the 'not found handler' if you did not implement this # add a route # some lookups with the expected output # should print 'root handler' # should print 'not found handler' or None if you did not implement one # should print 'about handler' # should print 'about handler' or None if you did not handle trailing slashes # should print 'not found handler' or None if you did not implement one