java中多线程构造不可变树的算法

Question

我想构建一个不可变树数据结构来表示filsystem目录结构的任意子集。通常会有一个知道包含/排除的过滤器，我基本上希望在构造中拥有一些线程支持。

这听起来像是我自己编写代码的纯粹书呆子的乐趣，但我实际上想知道关于这个主题是否有任何好的例子、文本或类似的东西？源代码很好;)

Answer 1

这本书有所有答案：http://www .amazon.co.uk/Purely-Functional-Structures-Chris-Okasaki/dp/0521663504

Answer 2

我不知道这是否有帮助。
Java SortedMap 使用红黑树，您可以在此处查看源代码。

 https://www.docjar.com/html/api/org/eclipse/ant/internal/ui/dtd/util/SortedMap.java.html

对于不可修改的 SortedMap。你可以在这里看到 Collections.unmodifyingSortepMap 的源代码

http://www.docjar.com/html/api/java/util/Collections.java.html

Answer 3

我建议维护一个“工作项目”队列。每个工作项都封装了一个要探索的目录，以及一个要将生成的树节点附加到的现有父节点（如果有）。每个线程都在循环中执行，从队列前端拉出项目，执行它们，并将任何子目录作为新工作项目推送到队列末尾。

您可以通过将根目录（没有父树节点）作为第一个工作项来启动该过程。当队列为空并且所有线程都处于空闲/等待状态时，该过程结束。

上面假设树一旦构造成不可变，但在构造过程中是可变的。如果情况并非如此，您需要“自下而上”构建树，因此您需要一个临时的可变结构来保存要附加的节点。否则，过程应该是相同的。

Answer 4

To krosenvold：

我认为你还没有理解我的意图。也许我应该把自己说得更清楚。

假设 Tree 和 TreeBuilder 位于同一个包中。

正如您所看到的，Tree 构造函数和 freeze() 方法具有包级别访问权限。因此，您不能在包外创建它，也不能在包外冻结它。

唯一的方法是通过 build() 方法。只有 TreeBuilder 可以使用同步的 build 方法创建 Tree。

现在我什至意识到，您甚至可以更简单地删除只读标志并更改 Tree.addChild() 方法以打包可见性。因此，您将得到一棵没有公共变异器、只有访问器的树。

就像我说的，树不同步。 TreeBuilder 是进行同步的地方。仔细看看访问器和修改器。查看公共和包修饰符的位置，您会发现修改树的唯一方法是当您位于同一个包中时，因此只有树构建器能够执行此操作。

public class Tree<T extends Filterable>{
   private final T data;
   private Tree<T> parent;
   private List<Tree<T>> children;
   private List<FilterChain<T>> filterChain;
   private boolean readonly = false;  
   /*package*/ Tree(T data) {...} 
   /*package*/ Tree(Tree<T> parent, T data) {...}

   /*package*/ void addChild(Tree<T> child){
       children.add(child);
   }
   public List<?> getResults(){
       return data.returnResults(filterChain);
   }

}

public class TreeBuilder<T>{
  public synchronized TreeNode createRoot(T data);
  public synchronized void addSubElement(TreeNode parentNode ,T data);
  public synchronized void addFilter(TreeNode node, Filter<T> filter);
  public Tree<T> synchronized build(){
     Tree<T> tree= ... 
     //build your tree
     //build filter chain for specific tree node
     return tree;
  }

}

Answer 5

您好，我不知道您到底想要实现什么，特别是在线程安全方面，但也许下面的伪代码可以用作草案。

public interface Filterable {
     List<?> returnResults(FilterChain chain);
} 

public class Tree<T extends Filterable>{
   private final T data;
   private Tree<T> parent;
   private List<Tree<T>> children;
   private List<FilterChain<T>> filterChain;
   private boolean readonly = false;  
   /*package*/ Tree(T data) {...} 
   /*package*/ Tree(Tree<T> parent, T data) {...}

   //freeze mtd makes object read-only
   /*package*/ void freeze(){         
          readonly = true;
      for(Tree<T> child: children){
          child.freeze();
      }
   }
   public void addChild(Tree<T> child){
       if(readonly){
           throws new NonModifiableException(...);
       }
       children.add(child);
   }
   public List<?> getResults(){
       return data.returnResults(filterChain);
   }

}

也许您可以专注于在树的构建器上进行同步，而不是在树上进行同步

public class TreeBuilder<T>{
    public synchronized TreeNode createRoot(T data);
    public synchronized void addSubElement(TreeNode parentNode ,T data);
    public synchronized void addFilter(TreeNode node, Filter<T> filter);
    public Tree<T> synchronized build(){
       Tree<T> tree= ... 
       //build your tree
       //build filter chain for specific tree node
       tree.freeze(); //make your tree readonly
       return tree;
    }
}