如何在Java中构建递归树？

Question

这是我的伪代码：

class Builder implements Callable<T> {
  T obj;
  ManagedExecutorService pool;

  Builder (T obj, ManagedExecutorService pool){
    this.obj = obj;
    this.pool = pool;
  }

  T call(){
    build();
  }

  private void build(){
        // skip if already traversed
        return isTraversed(obj);

        // call db and get obj's one-to-many relationships
        Collection<T> colOfChildObj = DbUtil.getChildrenPOJO(obj);
        for (<Collection>T childObj : colOfChildObj){
            this.pool.submit(new Builder(childObj, this.pool));
        }
        // set children as-is, when the submit above completes,
        // it will update childObj and thus will reflect
        // obj.childObj.itsChidren etc. For this though the caller
        // has to wait until all submits are processed 
        obj.setChildren(colOfChildObj); 
  }
}

因为Java不支持ForkJoinPool，所以这是不可能的。那么，我如何使用ManagedThreadFactory和/或ManagedExecutorService来实现它呢？我真正面临的挑战是无法在Java中调用pool.shutdown()或pool.awaitTermination。所以，打电话的人，如果我这么做了：

class Caller () {
  T getObjGraph(T rootObj){
     pool.submit(new Builder(rootObj));
     T objGraph = pool.get();
     return objGraph;
  }
} 

然后，我的方法不会等待所有的pool.submit(new (childObj，池))，因此我的对象没有设置所有的内容，并且是不完整的。我想把pool.submit返回的所有期货都放到阻塞队列中--但是我不知道如何通知调用者我的树遍历已经完成。当树遍历完成时，我确实有一个计数器达到0，但是由于客户机提交的是一个顶级节点，所以我不知道如何在Java中等待，而不是when (isCounter= 0) --这是一个CPU占优势。

有什么指示吗？

Answer 1

我想我明白你想做什么了。您可以只使用线程安全计数器，每次为给定节点创建和提交新任务时都会增加计数器，并在此节点的任务终止时减少该计数器。

在主线程中，您要等待一个锁，而要处理的剩余节点数为0。在每个任务中，您都会通知锁以指示tack被终止。

以下是一个完整的例子。它从每个节点都有一个名称的树开始，并将这棵树转换为另一棵树，其中每个节点都与原始名称连接在一起。

public class Tree {

    public static void main(String[] args) throws ExecutionException, InterruptedException {
        Node root = new Node("R");

        Node c1 = new Node("C1");
        Node c2 = new Node("C2");

        root.addChild(c1);
        root.addChild(c2);

        Node gc11 = new Node("GC11");
        Node gc12 = new Node("GC12");
        c1.addChild(gc11);
        c1.addChild(gc12);

        Node gc21 = new Node("GC11");
        Node gc22 = new Node("GC12");
        c2.addChild(gc21);
        c2.addChild(gc22);

        System.out.println("root = " + root);

        ExecutorService executor = Executors.newFixedThreadPool(4);
        final Object lock = new Object();
        final AtomicInteger remaining = new AtomicInteger(0);
        Future<Node> result = executor.submit(new HelloTask(root, null, executor, remaining, lock));

        synchronized (lock) {
            while (remaining.get() != 0) {
                lock.wait();
            }
        }

        Node helloRoot = result.get();

        System.out.println("helloRoot = " + helloRoot);

        executor.shutdown();
    }

    private static class HelloTask implements Callable<Node> {
        private final Node source;
        private final Node parent;
        private final ExecutorService executorService;
        private final Object lock;
        private final AtomicInteger remaining;

        public HelloTask(Node source, Node parent, ExecutorService executorService, AtomicInteger remaining, Object lock) {
            this.source = source;
            this.parent = parent;
            this.executorService = executorService;
            this.lock = lock;
            this.remaining = remaining;
            remaining.incrementAndGet();
        }

        @Override
        public Node call() throws Exception {
            // simulate some time
            Thread.sleep(1000L);
            Node result = new Node("Hello " + source.getName());
            if (parent != null) {
                parent.addChild(result);
            }
            for (Node child : source.getChildren()) {
                executorService.submit(new HelloTask(child, result, executorService, remaining, lock));
            }

            remaining.decrementAndGet();
            synchronized (lock) {
                lock.notifyAll();
            }
            return result;
        }
    }

    private static class Node {
        private final String name;
        private final List<Node> children = new CopyOnWriteArrayList<>();

        public Node(String name) {
            this.name = name;
        }

        public String getName() {
            return name;
        }

        public List<Node> getChildren() {
            return children;
        }

        public void addChild(Node child) {
            this.children.add(child);
        }

        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            sb.append(name);
            sb.append('\n');
            children.forEach(sb::append);
            return sb.toString();
        }
    }
}