This is an automated email from the ASF dual-hosted git repository. ahuber pushed a commit to branch dev/2.0.0/ISIS-898-treeview in repository https://gitbox.apache.org/repos/asf/isis.git
commit d337130decc55615a92e7272b5c0100fe6d36bac Author: Andi Huber <ahu...@apache.org> AuthorDate: Sat Apr 14 09:13:34 2018 +0200 ISIS-898 applib: introduces initial tree model --- .../org/apache/isis/applib/tree/TreeAdapter.java | 14 ++++ .../java/org/apache/isis/applib/tree/TreeNode.java | 80 ++++++++++++++++++++++ .../org/apache/isis/applib/tree/TreeNode_Lazy.java | 57 +++++++++++++++ .../applib/tree/TreeNode_iteratorBreadthFirst.java | 42 ++++++++++++ .../applib/tree/TreeNode_iteratorDepthFirst.java | 53 ++++++++++++++ .../applib/tree/TreeNode_iteratorHierarchyUp.java | 35 ++++++++++ 6 files changed, 281 insertions(+) diff --git a/core/applib/src/main/java/org/apache/isis/applib/tree/TreeAdapter.java b/core/applib/src/main/java/org/apache/isis/applib/tree/TreeAdapter.java new file mode 100644 index 0000000..5c39b59 --- /dev/null +++ b/core/applib/src/main/java/org/apache/isis/applib/tree/TreeAdapter.java @@ -0,0 +1,14 @@ +package org.apache.isis.applib.tree; + +import java.util.Optional; +import java.util.stream.Stream; + +public interface TreeAdapter<T> { + + public Optional<T> parentOf(T value); + + public int childCountOf(T value); + + public Stream<T> childrenOf(T value); + +} diff --git a/core/applib/src/main/java/org/apache/isis/applib/tree/TreeNode.java b/core/applib/src/main/java/org/apache/isis/applib/tree/TreeNode.java new file mode 100644 index 0000000..f8f6fc4 --- /dev/null +++ b/core/applib/src/main/java/org/apache/isis/applib/tree/TreeNode.java @@ -0,0 +1,80 @@ +package org.apache.isis.applib.tree; + +import java.util.Iterator; +import java.util.Optional; +import java.util.Spliterator; +import java.util.Spliterators; +import java.util.stream.Stream; +import java.util.stream.StreamSupport; + +public interface TreeNode<T> { + + // -- VALUE + + public T getValue(); + + // -- PARENT + + public Optional<TreeNode<T>> getParent(); + + // -- CHILDREN + + public int getChildCount(); + + public Stream<TreeNode<T>> streamChildren(); + + // -- BASIC PREDICATES + + public default boolean isRoot() { + return !getParent().isPresent(); + } + + public default boolean isLeaf() { + return getChildCount() == 0; + } + + // -- CONSTRUCTION + + public static <T> TreeNode<T> of(T node, TreeAdapter<T> treeAdapter) { + return TreeNode_Lazy.of(node, treeAdapter); + } + + // -- PARENT NODE ITERATION + + public default Iterator<TreeNode<T>> iteratorHierarchyUp(){ + return new TreeNode_iteratorHierarchyUp<>(this); + } + + // -- PARENT NODE STREAMING + + public default Stream<TreeNode<T>> streamHierarchyUp(){ + return StreamSupport.stream( + Spliterators.spliteratorUnknownSize(iteratorHierarchyUp(), Spliterator.ORDERED), + false); // not parallel + } + + // -- CHILD NODE ITERATION + + public default Iterator<TreeNode<T>> iteratorDepthFirst(){ + return new TreeNode_iteratorDepthFirst<>(this); + } + + public default Iterator<TreeNode<T>> iteratorBreadthFirst(){ + return new TreeNode_iteratorBreadthFirst<>(this); + } + + // -- CHILD NODE STREAMING + + public default Stream<TreeNode<T>> streamDepthFirst(){ + return StreamSupport.stream( + Spliterators.spliteratorUnknownSize(iteratorDepthFirst(), Spliterator.ORDERED), + false); // not parallel + } + + public default Stream<TreeNode<T>> streamBreadthFirst(){ + return StreamSupport.stream( + Spliterators.spliteratorUnknownSize(iteratorBreadthFirst(), Spliterator.ORDERED), + false); // not parallel + } + +} diff --git a/core/applib/src/main/java/org/apache/isis/applib/tree/TreeNode_Lazy.java b/core/applib/src/main/java/org/apache/isis/applib/tree/TreeNode_Lazy.java new file mode 100644 index 0000000..83cd503 --- /dev/null +++ b/core/applib/src/main/java/org/apache/isis/applib/tree/TreeNode_Lazy.java @@ -0,0 +1,57 @@ +package org.apache.isis.applib.tree; + +import java.util.Objects; +import java.util.Optional; +import java.util.stream.Stream; + +class TreeNode_Lazy<T> implements TreeNode<T> { + + private final T value; + private final TreeAdapter<T> treeAdapter; + + static <T> TreeNode_Lazy<T> of(T value, TreeAdapter<T> treeAdapter) { + Objects.requireNonNull(value); + Objects.requireNonNull(treeAdapter); + return new TreeNode_Lazy<T>(value, treeAdapter); + } + + private TreeNode_Lazy(T value, TreeAdapter<T> treeAdapter) { + this.value = value; + this.treeAdapter = treeAdapter; + } + + @Override + public T getValue() { + return value; + } + + @Override + public Optional<TreeNode<T>> getParent() { + return treeAdapter.parentOf(getValue()) + .map(this::toTreeNode) + ; + } + + @Override + public int getChildCount() { + return treeAdapter.childCountOf(value); + } + + @Override + public Stream<TreeNode<T>> streamChildren() { + if(isLeaf()) { + return Stream.empty(); + } + return treeAdapter.childrenOf(value) + .map(this::toTreeNode) + ; + } + + // -- HELPER + + private TreeNode<T> toTreeNode(T value){ + return of(value, treeAdapter); + } + + +} diff --git a/core/applib/src/main/java/org/apache/isis/applib/tree/TreeNode_iteratorBreadthFirst.java b/core/applib/src/main/java/org/apache/isis/applib/tree/TreeNode_iteratorBreadthFirst.java new file mode 100644 index 0000000..4f620c2 --- /dev/null +++ b/core/applib/src/main/java/org/apache/isis/applib/tree/TreeNode_iteratorBreadthFirst.java @@ -0,0 +1,42 @@ +package org.apache.isis.applib.tree; + +import java.util.ArrayDeque; +import java.util.Deque; +import java.util.Iterator; +import java.util.NoSuchElementException; + +class TreeNode_iteratorBreadthFirst<T> implements Iterator<TreeNode<T>> { + + private Deque<TreeNode<T>> deque = new ArrayDeque<>(); + private TreeNode<T> next; + + TreeNode_iteratorBreadthFirst(TreeNode<T> treeNode) { + next = treeNode; + } + + @Override + public boolean hasNext() { + return next!=null; + } + + @Override + public TreeNode<T> next() { + if(next==null) { + throw new NoSuchElementException("Iterator has run out of elements."); + } + final TreeNode<T> result = next; + next = fetchNext(next); + return result; + } + + // -- HELPER + + private TreeNode<T> fetchNext(TreeNode<T> current) { + if(!current.isLeaf()) { + current.streamChildren() + .forEach(deque::offerLast); + } + return deque.pollFirst(); + } + +} diff --git a/core/applib/src/main/java/org/apache/isis/applib/tree/TreeNode_iteratorDepthFirst.java b/core/applib/src/main/java/org/apache/isis/applib/tree/TreeNode_iteratorDepthFirst.java new file mode 100644 index 0000000..a9f63d3 --- /dev/null +++ b/core/applib/src/main/java/org/apache/isis/applib/tree/TreeNode_iteratorDepthFirst.java @@ -0,0 +1,53 @@ +package org.apache.isis.applib.tree; + +import java.util.Iterator; +import java.util.NoSuchElementException; +import java.util.Stack; + +class TreeNode_iteratorDepthFirst<T> implements Iterator<TreeNode<T>> { + + private Stack<TreeNode<T>> stack = new Stack<>(); + private TreeNode<T> next; + + TreeNode_iteratorDepthFirst(TreeNode<T> treeNode) { + next = treeNode; + } + + @Override + public boolean hasNext() { + return next!=null; + } + + @Override + public TreeNode<T> next() { + if(next==null) { + throw new NoSuchElementException("Iterator has run out of elements."); + } + final TreeNode<T> result = next; + next = fetchNext(next); + return result; + } + + // -- HELPER + + private TreeNode<T> fetchNext(TreeNode<T> current) { + if(!current.isLeaf()) { + pushChildrenToStackInReverseOrder(current); + } + return stack.isEmpty() ? null : stack.pop(); + } + + private Stack<TreeNode<T>> fifo = new Stack<>(); // declared as field only to reduce heap pollution + + private void pushChildrenToStackInReverseOrder(TreeNode<T> node) { + + node.streamChildren() + .forEach(fifo::push); + + while(!fifo.isEmpty()) { + stack.push(fifo.pop()); + } + } + + +} diff --git a/core/applib/src/main/java/org/apache/isis/applib/tree/TreeNode_iteratorHierarchyUp.java b/core/applib/src/main/java/org/apache/isis/applib/tree/TreeNode_iteratorHierarchyUp.java new file mode 100644 index 0000000..62813b2 --- /dev/null +++ b/core/applib/src/main/java/org/apache/isis/applib/tree/TreeNode_iteratorHierarchyUp.java @@ -0,0 +1,35 @@ +package org.apache.isis.applib.tree; + +import java.util.Iterator; +import java.util.NoSuchElementException; + +class TreeNode_iteratorHierarchyUp<T> implements Iterator<TreeNode<T>> { + + private TreeNode<T> next; + + TreeNode_iteratorHierarchyUp(TreeNode<T> treeNode) { + next = treeNode; + } + + @Override + public boolean hasNext() { + return next!=null; + } + + @Override + public TreeNode<T> next() { + if(next==null) { + throw new NoSuchElementException("Iterator has run out of elements."); + } + final TreeNode<T> result = next; + next = fetchNext(next); + return result; + } + + // -- HELPER + + private TreeNode<T> fetchNext(TreeNode<T> current) { + return current.getParent().orElse(null); + } + +} -- To stop receiving notification emails like this one, please contact ahu...@apache.org.