Hierarchical data (#8842)

* Initial HierarchicalDataProvider for TreeGrid
* Initial in-memory hierarchical data implementation
* TreeGrid declarative support

Fixes #8611, Fixes #8620 

1 files changed, 445 insertions, 0 deletions

diff --git a/server/src/main/java/com/vaadin/data/provider/HierarchyMapper.java b/server/src/main/java/com/vaadin/data/provider/HierarchyMapper.java
new file mode 100644
index 0000000000..7f423b39c9
--- /dev/null
+++ b/server/src/main/java/com/vaadin/data/provider/HierarchyMapper.java
@@ -0,0 +1,445 @@
+/*
+ * Copyright 2000-2016 Vaadin Ltd.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License"); you may not
+ * use this file except in compliance with the License. You may obtain a copy of
+ * the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+ * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+ * License for the specific language governing permissions and limitations under
+ * the License.
+ */
+package com.vaadin.data.provider;
+
+import java.io.Serializable;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Objects;
+import java.util.Optional;
+import java.util.TreeSet;
+import java.util.concurrent.atomic.AtomicInteger;
+import java.util.function.BiConsumer;
+import java.util.logging.Logger;
+import java.util.stream.Collectors;
+import java.util.stream.Stream;
+
+/**
+ * Mapper for hierarchical data.
+ * <p>
+ * Keeps track of the expanded nodes, and size of of the subtrees for each
+ * expanded node.
+ * <p>
+ * This class is framework internal implementation details, and can be changed /
+ * moved at any point. This means that you should not directly use this for
+ * anything.
+ *
+ * @author Vaadin Ltd
+ * @since
+ */
+class HierarchyMapper implements Serializable {
+
+    private static final Logger LOGGER = Logger
+            .getLogger(HierarchyMapper.class.getName());
+
+    /**
+     * A POJO that represents a query data for a certain tree level.
+     */
+    static class TreeLevelQuery { // not serializable since not stored
+        /**
+         * The tree node that the query is for. Only used for fetching parent
+         * key.
+         */
+        final TreeNode node;
+        /** The start index of the query, from 0 to level's size - 1. */
+        final int startIndex;
+        /** The number of rows to fetch. s */
+        final int size;
+        /** The depth of this node. */
+        final int depth;
+        /** The first row index in grid, including all the nodes. */
+        final int firstRowIndex;
+        /** The direct subtrees for the node that effect the indexing. */
+        final List<TreeNode> subTrees;
+
+        TreeLevelQuery(TreeNode node, int startIndex, int size, int depth,
+                int firstRowIndex, List<TreeNode> subTrees) {
+            this.node = node;
+            this.startIndex = startIndex;
+            this.size = size;
+            this.depth = depth;
+            this.firstRowIndex = firstRowIndex;
+            this.subTrees = subTrees;
+        }
+    }
+
+    /**
+     * A level in the tree, either the root level or an expanded subtree level.
+     * <p>
+     * Comparable based on the {@link #startIndex}, which is flat from 0 to data
+     * size - 1.
+     */
+    static class TreeNode implements Serializable, Comparable<TreeNode> {
+
+        /** The key for the expanded item that this is a subtree of. */
+        private final String parentKey;
+        /** The first index on this level. */
+        private int startIndex;
+        /** The last index on this level, INCLUDING subtrees. */
+        private int endIndex;
+
+        TreeNode(String parentKey, int startIndex, int size) {
+            this.parentKey = parentKey;
+            this.startIndex = startIndex;
+            endIndex = startIndex + size - 1;
+        }
+
+        TreeNode(int startIndex) {
+            parentKey = "INVALID";
+            this.startIndex = startIndex;
+        }
+
+        int getStartIndex() {
+            return startIndex;
+        }
+
+        int getEndIndex() {
+            return endIndex;
+        }
+
+        String getParentKey() {
+            return parentKey;
+        }
+
+        private void push(int offset) {
+            startIndex += offset;
+            endIndex += offset;
+        }
+
+        private void pushEnd(int offset) {
+            endIndex += offset;
+        }
+
+        @Override
+        public int compareTo(TreeNode other) {
+            return Integer.valueOf(startIndex).compareTo(other.startIndex);
+        }
+
+        @Override
+        public String toString() {
+            return "TreeNode [parent=" + parentKey + ", start=" + startIndex
+                    + ", end=" + getEndIndex() + "]";
+        }
+
+    }
+
+    /** The expanded nodes in the tree. */
+    private final TreeSet<TreeNode> nodes = new TreeSet<>();
+
+    /**
+     * Resets the tree, sets given the root level size.
+     *
+     * @param rootLevelSize
+     *            the number of items in the root level
+     */
+    public void reset(int rootLevelSize) {
+        nodes.clear();
+        nodes.add(new TreeNode(null, 0, rootLevelSize));
+    }
+
+    /**
+     * Returns the complete size of the tree, including all expanded subtrees.
+     *
+     * @return the size of the tree
+     */
+    public int getTreeSize() {
+        TreeNode rootNode = getNodeForKey(null)
+                .orElse(new TreeNode(null, 0, 0));
+        return rootNode.endIndex + 1;
+    }
+
+    /**
+     * Returns whether the node with the given is collapsed or not.
+     *
+     * @param itemKey
+     *            the key of node to check
+     * @return {@code true} if collapsed, {@code false} if expanded
+     */
+    public boolean isCollapsed(String itemKey) {
+        return !getNodeForKey(itemKey).isPresent();
+    }
+
+    /**
+     * Return the depth of expanded node's subtree.
+     * <p>
+     * The root node depth is 0.
+     *
+     * @param expandedNodeKey
+     *            the item key of the expanded node
+     * @return the depth of the expanded node
+     * @throws IllegalArgumentException
+     *             if the node was not expanded
+     */
+    protected int getDepth(String expandedNodeKey) {
+        Optional<TreeNode> node = getNodeForKey(expandedNodeKey);
+        if (!node.isPresent()) {
+            throw new IllegalArgumentException("No node with given key "
+                    + expandedNodeKey + " was expanded.");
+        }
+        TreeNode treeNode = node.get();
+        AtomicInteger start = new AtomicInteger(treeNode.startIndex);
+        AtomicInteger end = new AtomicInteger(treeNode.getEndIndex());
+        AtomicInteger depth = new AtomicInteger();
+        nodes.headSet(treeNode, false).descendingSet().forEach(higherNode -> {
+            if (higherNode.startIndex < start.get()
+                    && higherNode.getEndIndex() >= end.get()) {
+                start.set(higherNode.startIndex);
+                depth.incrementAndGet();
+            }
+        });
+
+        return depth.get();
+    }
+
+    /**
+     * Returns the tree node for the given expanded item key, or an empty
+     * optional if the item was not expanded.
+     *
+     * @param expandedNodeKey
+     *            the key of the item
+     * @return the tree node for the expanded item, or an empty optional if not
+     *         expanded
+     */
+    protected Optional<TreeNode> getNodeForKey(String expandedNodeKey) {
+        return nodes.stream()
+                .filter(node -> Objects.equals(node.parentKey, expandedNodeKey))
+                .findAny();
+    }
+
+    /**
+     * Expands the node in the given index and with the given key.
+     *
+     * @param expanedRowKey
+     *            the key of the expanded item
+     * @param expandedRowIndex
+     *            the index of the expanded item
+     * @param expandedNodeSize
+     *            the size of the subtree of the expanded node
+     * @throws IllegalStateException
+     *             if the node was expanded already
+     */
+    protected void expand(String expanedRowKey, int expandedRowIndex,
+            int expandedNodeSize) {
+        if (expandedNodeSize < 1) {
+            throw new IllegalArgumentException(
+                    "The expanded node's size cannot be less than 1, was "
+                            + expandedNodeSize);
+        }
+        TreeNode newNode = new TreeNode(expanedRowKey, expandedRowIndex + 1,
+                expandedNodeSize);
+
+        boolean added = nodes.add(newNode);
+        if (!added) {
+            throw new IllegalStateException("Node in index " + expandedRowIndex
+                    + " was expanded already.");
+        }
+
+        // push end indexes for parent nodes
+        List<TreeNode> updated = nodes.headSet(newNode, false).stream()
+                .filter(node -> node.getEndIndex() >= expandedRowIndex)
+                .collect(Collectors.toList());
+        nodes.removeAll(updated);
+        updated.stream().forEach(node -> node.pushEnd(expandedNodeSize));
+        nodes.addAll(updated);
+
+        // push start and end indexes for later nodes
+        updated = nodes.tailSet(newNode, false).stream()
+                .collect(Collectors.toList());
+        nodes.removeAll(updated);
+        updated.stream().forEach(node -> node.push(expandedNodeSize));
+        nodes.addAll(updated);
+    }
+
+    /**
+     * Collapses the node in the given index.
+     *
+     * @param key
+     *            the key of the collapsed item
+     * @param collapsedRowIndex
+     *            the index of the collapsed item
+     * @return the size of the complete subtree that was collapsed
+     * @throws IllegalStateException
+     *             if the node was not collapsed, or if the given key is not the
+     *             same as it was when the node has been expanded
+     */
+    protected int collapse(String key, int collapsedRowIndex) {
+        Objects.requireNonNull(key,
+                "The key for the item to collapse cannot be null.");
+        TreeNode collapsedNode = nodes
+                .ceiling(new TreeNode(collapsedRowIndex + 1));
+        if (collapsedNode == null
+                || collapsedNode.startIndex != collapsedRowIndex + 1) {
+            throw new IllegalStateException(
+                    "Could not find expanded node for index "
+                            + collapsedRowIndex + ", node was not collapsed");
+        }
+        if (!Objects.equals(key, collapsedNode.parentKey)) {
+            throw new IllegalStateException("The expected parent key " + key
+                    + " is different for the collapsed node " + collapsedNode);
+        }
+
+        // remove complete subtree
+        AtomicInteger removedSubTreeSize = new AtomicInteger(
+                collapsedNode.getEndIndex() - collapsedNode.startIndex + 1);
+        nodes.tailSet(collapsedNode, false).removeIf(
+                node -> node.startIndex <= collapsedNode.getEndIndex());
+
+        final int offset = -1 * removedSubTreeSize.get();
+        // adjust parent end indexes
+        List<TreeNode> updated = nodes.headSet(collapsedNode, false).stream()
+                .filter(node -> node.getEndIndex() >= collapsedRowIndex)
+                .collect(Collectors.toList());
+        nodes.removeAll(updated);
+        updated.stream().forEach(node -> node.pushEnd(offset));
+        nodes.addAll(updated);
+
+        // adjust start and end indexes for latter nodes
+        updated = nodes.tailSet(collapsedNode, false).stream()
+                .collect(Collectors.toList());
+        nodes.removeAll(updated);
+        updated.stream().forEach(node -> node.push(offset));
+        nodes.addAll(updated);
+
+        nodes.remove(collapsedNode);
+
+        return removedSubTreeSize.get();
+    }
+
+    /**
+     * Splits the given range into queries per tree level.
+     *
+     * @param firstRow
+     *            the first row to fetch
+     * @param lastRow
+     *            the last row to fetch
+     * @return a stream of query data per level
+     * @see #reorderLevelQueryResultsToFlatOrdering(BiConsumer, TreeLevelQuery,
+     *      List)
+     */
+    protected Stream<TreeLevelQuery> splitRangeToLevelQueries(
+            final int firstRow, final int lastRow) {
+        return nodes.stream()
+                // filter to parts intersecting with the range
+                .filter(node -> node.startIndex <= lastRow
+                        && firstRow <= node.getEndIndex())
+                // split into queries per level with level based indexing
+                .map(node -> {
+
+                    // calculate how subtrees effect indexing and size
+                    int depth = getDepth(node.parentKey);
+                    List<TreeNode> directSubTrees = nodes.tailSet(node, false)
+                            .stream()
+                            // find subtrees
+                            .filter(subTree -> node.startIndex < subTree
+                                    .getEndIndex()
+                                    && subTree.startIndex < node.getEndIndex())
+                            // filter to direct subtrees
+                            .filter(subTree -> getDepth(
+                                    subTree.parentKey) == (depth + 1))
+                            .collect(Collectors.toList());
+                    // first intersecting index in flat order
+                    AtomicInteger firstIntersectingRowIndex = new AtomicInteger(
+                            Math.max(node.startIndex, firstRow));
+                    // last intersecting index in flat order
+                    final int lastIntersectingRowIndex = Math
+                            .min(node.getEndIndex(), lastRow);
+                    // start index for this level
+                    AtomicInteger start = new AtomicInteger(
+                            firstIntersectingRowIndex.get() - node.startIndex);
+                    // how many nodes should be fetched for this level
+                    AtomicInteger size = new AtomicInteger(
+                            lastIntersectingRowIndex
+                                    - firstIntersectingRowIndex.get() + 1);
+
+                    // reduce subtrees before requested index
+                    directSubTrees.stream().filter(subtree -> subtree
+                            .getEndIndex() < firstIntersectingRowIndex.get())
+                            .forEachOrdered(subtree -> {
+                                start.addAndGet(-1 * (subtree.getEndIndex()
+                                        - subtree.startIndex + 1));
+                            });
+                    // if requested start index is in the middle of a
+                    // subtree, start is after that
+                    List<TreeNode> intersectingSubTrees = new ArrayList<>();
+                    directSubTrees.stream()
+                            .filter(subtree -> subtree.startIndex <= firstIntersectingRowIndex
+                                    .get() && firstIntersectingRowIndex
+                                            .get() <= subtree.getEndIndex())
+                            .findFirst().ifPresent(subtree -> {
+                                int previous = firstIntersectingRowIndex
+                                        .getAndSet(subtree.getEndIndex() + 1);
+                                int delta = previous
+                                        - firstIntersectingRowIndex.get();
+                                start.addAndGet(subtree.startIndex - previous);
+                                size.addAndGet(delta);
+                                intersectingSubTrees.add(subtree);
+                            });
+                    // reduce size of subtrees after first row that intersect
+                    // with requested range
+                    directSubTrees.stream()
+                            .filter(subtree -> firstIntersectingRowIndex
+                                    .get() < subtree.startIndex
+                                    && subtree.endIndex <= lastIntersectingRowIndex)
+                            .forEachOrdered(subtree -> {
+                                // reduce subtree size that is part of the
+                                // requested range from query size
+                                size.addAndGet(
+                                        -1 * (Math.min(subtree.getEndIndex(),
+                                                lastIntersectingRowIndex)
+                                                - subtree.startIndex + 1));
+                                intersectingSubTrees.add(subtree);
+                            });
+                    return new TreeLevelQuery(node, start.get(), size.get(),
+                            depth, firstIntersectingRowIndex.get(),
+                            intersectingSubTrees);
+
+                }).filter(query -> query.size > 0);
+
+    }
+
+    /**
+     * Merges the tree level query results into flat grid ordering.
+     *
+     * @param rangePositionCallback
+     *            the callback to place the results into
+     * @param query
+     *            the query data for the results
+     * @param results
+     *            the results to reorder
+     * @param <T>
+     *            the type of the results
+     */
+    protected <T> void reorderLevelQueryResultsToFlatOrdering(
+            BiConsumer<T, Integer> rangePositionCallback, TreeLevelQuery query,
+            List<T> results) {
+        AtomicInteger nextPossibleIndex = new AtomicInteger(
+                query.firstRowIndex);
+        for (T item : results) {
+            // search for any intersecting subtrees and push index if necessary
+            query.subTrees.stream().filter(
+                    subTree -> subTree.startIndex <= nextPossibleIndex.get()
+                            && nextPossibleIndex.get() <= subTree.getEndIndex())
+                    .findAny().ifPresent(intersecting -> {
+                        nextPossibleIndex.addAndGet(intersecting.getEndIndex()
+                                - intersecting.startIndex + 1);
+                        query.subTrees.remove(intersecting);
+                    });
+            rangePositionCallback.accept(item,
+                    nextPossibleIndex.getAndIncrement());
+        }
+    }
+
+}