class UnsubscribeRequest {
        private final Topic topicFilter;
        private final String clientId;
        private boolean shared = false;
        private ShareName shareName;

        private UnsubscribeRequest(String clientId, Topic topicFilter) {
            this.topicFilter = topicFilter;
            this.clientId = clientId;
        }

        public static UnsubscribeRequest buildNonShared(String clientId, Topic topicFilter) {
            return new UnsubscribeRequest(clientId, topicFilter);
        }

        public static UnsubscribeRequest buildShared(ShareName shareName, Topic topicFilter, String clientId) {
            if (topicFilter.headToken().name().startsWith("$share")) {
                throw new IllegalArgumentException("Topic filter of a shared subscription can't contains $share and share name");
            }

            UnsubscribeRequest request = new UnsubscribeRequest(clientId, topicFilter);
            request.shared = true;
            request.shareName = shareName;
            return request;
        }

        public Topic getTopicFilter() {
            return topicFilter;
        }

        public boolean isShared() {
            return shared;
        }

        public ShareName getSharedName() {
            return shareName;
        }

        public String getClientId() {
            return clientId;
        }
    }

    interface IVisitor<T> {

        void visit(CNode node, int deep);

        T getResult();
    }

    private static final Token ROOT = new Token("root");
    private static final INode NO_PARENT = null;

    private enum Action {
        OK, REPEAT,
        OK_NEW // used to indicate that the action was successful and the subscription created a new branch
    }

    INode root;

    CTrie() {
        final CNode mainNode = new CNode(ROOT);
        this.root = new INode(mainNode);
    }

    Optional<CNode> lookup(Topic topic) {
        INode inode = this.root;
        Token token = topic.headToken();
        while (!topic.isEmpty()) {
            Optional<INode> child = inode.mainNode().childOf(token);
            if (!child.isPresent()) {
                break;
            }
            topic = topic.exceptHeadToken();
            inode = child.get();
            token = topic.headToken();
        }
        if (inode == null || !topic.isEmpty()) {
            return Optional.empty();
        }
        return Optional.of(inode.mainNode());
    }

    enum NavigationAction {
        MATCH, GODEEP, STOP
    }

    private NavigationAction evaluate(Topic topicName, CNode cnode, int depth) {
        // depth 0 is the root node of all the topics, so for topic filter
        // monitor/sensor we have <root> -> monitor -> sensor
        final boolean isFirstLevel = depth == 1;
        if (Token.MULTI.equals(cnode.getToken())) {
            Token token = topicName.headToken();
            if (token != null && token.isReserved() && isFirstLevel) {
                // [MQTT-4.7.2-1] single wildcard can't match reserved topics
                // if reserved token is the first of the topicName
                return NavigationAction.STOP;
            }
            return NavigationAction.MATCH;
        }
        if (topicName.isEmpty()) {
            return NavigationAction.STOP;
        }
        final Token token = topicName.headToken();
        if (Token.SINGLE.equals(cnode.getToken()) || cnode.getToken().equals(token) || ROOT.equals(cnode.getToken())) {
            if (Token.SINGLE.equals(cnode.getToken()) && token.isReserved() && isFirstLevel) {
                // [MQTT-4.7.2-1] single wildcard can't match reserved topics
                return NavigationAction.STOP;
            }
            return NavigationAction.GODEEP;
        }
        return NavigationAction.STOP;
    }

    public List<Subscription> recursiveMatch(Topic topicName) {
        return recursiveMatch(topicName, this.root, 0);
    }

    private List<Subscription> recursiveMatch(Topic topicName, INode inode, int depth) {
        CNode cnode = inode.mainNode();
        if (cnode instanceof TNode) {
            return Collections.emptyList();
        }
        NavigationAction action = evaluate(topicName, cnode, depth);
        if (action == NavigationAction.MATCH) {
            return cnode.sharedAndNonSharedSubscriptions();
        }
        if (action == NavigationAction.STOP) {
            return Collections.emptyList();
        }
        Topic remainingTopic = (ROOT.equals(cnode.getToken())) ? topicName : topicName.exceptHeadToken();
        List<Subscription> subscriptions = new ArrayList<>();

        // We should only consider the maximum three children children of
        // type #, + or exact match
        Optional<INode> subInode = cnode.childOf(Token.MULTI);
        if (subInode.isPresent()) {
            subscriptions.addAll(recursiveMatch(remainingTopic, subInode.get(), depth + 1));
        }
        subInode = cnode.childOf(Token.SINGLE);
        if (subInode.isPresent()) {
            subscriptions.addAll(recursiveMatch(remainingTopic, subInode.get(), depth + 1));
        }
        if (remainingTopic.isEmpty()) {
            subscriptions.addAll(cnode.sharedAndNonSharedSubscriptions());
        } else {
            subInode = cnode.childOf(remainingTopic.headToken());
            if (subInode.isPresent()) {
                subscriptions.addAll(recursiveMatch(remainingTopic, subInode.get(), depth + 1));
            }
        }
        return subscriptions;
    }

    /**
     * @return true if the subscription didn't exist.
     * */
    public boolean addToTree(SubscriptionRequest request) {
        Action res;
        do {
            res = insert(request.getTopicFilter(), this.root, request);
        } while (res == Action.REPEAT);
        return res == Action.OK_NEW;
    }

    private Action insert(Topic topic, final INode inode, SubscriptionRequest request) {<FILL_FUNCTION_BODY>

        final Token token = topic.headToken();
        final CNode cnode = inode.mainNode();
        if (!topic.isEmpty()) {
            Optional<INode> nextInode = cnode.childOf(token);
            if (nextInode.isPresent()) {
                Topic remainingTopic = topic.exceptHeadToken();
                return insert(remainingTopic, nextInode.get(), request);
            }
        }
        if (topic.isEmpty()) {
            return insertSubscription(inode, cnode, request);
        } else {
            return createNodeAndInsertSubscription(topic, inode, cnode, request);
        }
    
<no_super_class>