Algorithm for multithreaded construction of immutable trees in java

Question

I would like to create an immutable tree data structure representing an arbitrary subset of the file system directory structure. There will usually be a filter that knows about include / exclude, and basically I would like to have some streaming support in the construct.

It sounds like pure botanical fun to code yourself, but I'm really curious if there are any good examples, texts or the like on this subject? The source code is good;)

Answer 1

This book has all the answers: http://www.amazon.co.uk/Purely-Functional-Structures-Chris-Okasaki/dp/0521663504

Answer 2

I do not know if this is useful. Java SortedMap uses red ebony and you can view the source code here.

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

For unmodifiable SortedMap. u can see the source code for Collections.unmodifiableSortepMap here

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

Answer 3

I would suggest maintaining a queue of work items. Each work item encapsulates the directory being examined and the existing parent node (if any) to associate the resulting node tree with. Each thread runs in a loop, pulls items from the front of the queue, runs them, and clicks any subdirectories at the end of the queue as new work items.

You start the process by clicking the root directory (without the parent node tree) as the first work item. The process ends when the queue is empty and all threads are not working / waiting.

The above assumes that the tree will be unchanged after its construction, but changed during construction. If this is not the case, you need to build the tree from the bottom up, so you need a temporary mutable structure to store the nodes to which they are added. Otherwise, the process must be the same.

Answer 4

To Kroshenvold:

I think you did not understand my intention. Maybe I should make myself clearer.

It is assumed that Tree and TreeBuilder are in the same package.

As you can see, the Tree constructor and freeze () method has access to the package level. Thus, you cannot create it outside the package, and you also cannot freeze it outside the package.

The only way to do this is to use the build () method. Only TreeBuilder can create a Tree using a build method that is synchronized.

Now I even realized that you can even simplify removing the flag for reading and modify the Tree.addChild () method to also display visibility. Therefore, you get a tree that does not have public mutators, only accessors.

As I said, Tree is not syncing. TreeBuilder is the place where your synchronization takes place. Get to know accessories and mutators. Look where the public and batch modifiers are located, and you will see that the only way to change the tree is when you are in the same package, so only the tree builder can do it.

 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

Hi, I don’t know what exactly you would like to achieve, especially from the point of view of thread safety, but perhaps it could be used as a draft under the pseudo-code.

 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); } } 

Instead of doing synchronization on the tree, perhaps you could focus on synchronizing on the tree builder

 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; } }