Как реализовать Tr ie Итератор с Thread run ()

Question

У меня есть уникальное назначение, в котором мне нужно реализовать Trie и его узлы (Node) и итератор.

Итератор должен перебирать узлы, используя StringBuffer для поддержания статус слова, и он должен реализовывать интерфейс Runnable, что означает, что я должен реализовать метод run()!

Я пробовал эту реализацию:

class NodeIterator implements Iterator<String>, Runnable {
    String nextWord;
    boolean terminated;
    Thread thread;

    public NodeIterator() {
        thread = new Thread(this,"Node iterator");
        thread.start();
    }

    @Override
    public void run() {
        terminated = false;

        visit(Trie.this.root);

        synchronized (this) {
            terminated = true;
            handshake();
        }
    }

    private void visit(Node node) {

    }

    private void handshake() {
        notify();

        try {
            wait();
        } catch (InterruptedException e) {

        }
    }

    @Override
    public boolean hasNext() {
        synchronized (this) {
            if(!terminated)
                handshake();
        }

        return nextWord != null;
    }

    @Override
    public String next() {
        String word = nextWord;

        synchronized (this) {
            word = null;
        }

        return word;
    }
}

Мне не хватает реализация метода visit(), поскольку я не уверен, как "посещать" узлы, и я не уверен, что все остальное правильно, поскольку я никогда не работал с потоками.

Должен ли я что-то делать иначе?

Редактировать:

public class Trie implements Iterable<String> {
    Node root;

    ...

    private static class Node {
        private HashMap<Character, Node> children;
        private boolean endOfWord;

        ...
    }
}

Answer 1

Одним из способов реализации visit() является рекурсия. Рекурсивный метод должен отслеживать префикс строки, созданной до сих пор, и, если он находит узел, заканчивающий слово, публикует найденную строку. Предполагая, что вы не можете изменить подпись для visit(Node), вам понадобится вспомогательный метод:

    void visit(Node root) {
        visitRecursive("", root);
    }

    private void visitRecursive(String prefix, Node node) {
        if (node.endOfWord) {
            nextWord = prefix;
            synchronized (this) {
                handshake();
            }
        }
        for (Map.Entry<Character, Node> entry : node.children.entrySet()) {
            visitRecursive(prefix + entry.getKey(), entry.getValue());
        }
    }

Я не уверен, что весь ваш многопоточный код правильный, но по крайней мере это будет повторяться все строки хранятся в tr ie.