001/*
002 *  Copyright 2018 Anyware Services
003 *
004 *  Licensed under the Apache License, Version 2.0 (the "License");
005 *  you may not use this file except in compliance with the License.
006 *  You may obtain a copy of the License at
007 *
008 *      http://www.apache.org/licenses/LICENSE-2.0
009 *
010 *  Unless required by applicable law or agreed to in writing, software
011 *  distributed under the License is distributed on an "AS IS" BASIS,
012 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 *  See the License for the specific language governing permissions and
014 *  limitations under the License.
015 */
016package org.ametys.cms.search.advanced;
017
018import java.util.Collection;
019import java.util.Collections;
020import java.util.List;
021import java.util.function.BiFunction;
022import java.util.function.Function;
023import java.util.stream.Collectors;
024import java.util.stream.Stream;
025
026import org.ametys.cms.search.query.Query.LogicalOperator;
027
028/**
029 * This abstract class represents a node in a tree data structure. <br>
030 * There are only two allowed sublcasses: {@link TreeLeaf} and {@link TreeInternalNode}
031 * 
032 * @param <T> the type of the values of the leaves of the tree.
033 */
034public abstract class AbstractTreeNode<T>
035{
036    /**
037     * Generic helper method to walk a tree (i.e. traverse a tree) for visiting each node and doing
038     * a recursive treatment
039     * <br>This is a post-order walk (the children are traversed before their respective parents are traversed)
040     * <br>See also <a href="https://en.wikipedia.org/wiki/Tree_traversal#Post-order">this link</a>
041     * @param <T> the type of the values of the leaves of the given tree
042     * @param <R> the type of the object returned by this method.
043     * @param tree The tree to walk
044     * @param leafFunction The operation to perform for a leaf
045     * @param internalNodeFunction The operation to perform for an internal node.
046     * <br>This function takes two arguments: <ul><li>the results for each child as a stream; </li><li>the logical operator of the internal node</li></ul>
047     * @return a result
048     */
049    public static <T, R> R walk(AbstractTreeNode<T> tree, 
050                        Function<TreeLeaf<T>, R> leafFunction, 
051                        BiFunction<Stream<R>, LogicalOperator, R> internalNodeFunction)
052    {
053        if (tree instanceof TreeLeaf<?>)
054        {
055            return leafFunction.apply((TreeLeaf<T>) tree);
056        }
057        else if (tree instanceof TreeInternalNode<?>)
058        {
059            TreeInternalNode<T> internalNode = (TreeInternalNode<T>) tree;
060            // localResult is the result of already walked children, in a stream
061            Stream<R> localResult = internalNode.getChildren()
062                    .stream()
063                    .map(child -> walk(child, leafFunction, internalNodeFunction));
064            // from localResult stream and the current logical operator, apply function to get final result
065            return internalNodeFunction.apply(localResult, internalNode.getLogicalOperator());
066        }
067        else
068        {
069            throw new IllegalArgumentException("Wrong type of TreeNode. It must only be a TreeInternalNode or a TreeLeaf.");
070        }
071    }
072    
073    /**
074     * Gets all leaves of this tree node, recursively flattened.
075     * @return the flattened leaves
076     */
077    public Collection<TreeLeaf<T>> getFlatLeaves()
078    {
079        return walk(this,
080            // leaf => just return it in a singleton
081            Collections::singletonList,
082            // internal node => collect in a list
083            (singletons, operator) -> singletons.flatMap(List<TreeLeaf<T>>::stream)
084                                                .collect(Collectors.toList()));
085    }
086}
087