package org.simantics.modeling.requests;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.Deque;
import java.util.List;

import org.eclipse.jface.viewers.IFilter;
import org.simantics.scl.runtime.function.Function1;

/**
 * @author Tuukka Lehtonen
 */
public class Nodes {

    public static Collection<Node> breadthFirstFlatten(IFilter filter, Collection<Node> roots) {
        Collection<Node> result = new ArrayList<Node>();
        List<Node> sortedRoots = new ArrayList<Node>(roots);
        Collections.sort(sortedRoots);
        Deque<Node> todo = new ArrayDeque<Node>(sortedRoots);
        while (!todo.isEmpty()) {
            Node n = todo.removeFirst();
            List<Node> sorted = new ArrayList<Node>(n.getChildren());
            Collections.sort(sorted);
            todo.addAll(sorted);
            if (filter == null || filter.select(n))
                result.add(n);
        }
        return result;
    }

    public static Collection<Node> depthFirstFlatten(IFilter filter, Collection<Node> roots, Comparator<? super Node> comparator) {
        Collection<Node> result = new ArrayList<Node>();
        List<Node> sortedRoots = new ArrayList<Node>(roots);
        Collections.sort(sortedRoots, comparator);
        for (Node n : sortedRoots) {
            depthFirstFlattenRec(filter, comparator, n, result);
        }
        return result;
    }

    private static Collection<Node> depthFirstFlattenRec(IFilter filter, Comparator<? super Node> comparator, Node n, Collection<Node> result) {
        if (filter == null || filter.select(n))
            result.add(n);

        Collection<Node> children = n.getChildren();
        if (children.isEmpty())
            return result;

        List<Node> sorted = new ArrayList<Node>(children);
        Collections.sort(sorted, comparator);
        for (Node child : sorted)
            depthFirstFlattenRec(filter, comparator, child, result);

        return result;
    }

    /**
     * @param f
     *            function that takes the walked Node as argument and returns a
     *            boolean to describe whether to continue the walk or cancel the
     *            walk. The returned value cannot be <code>null</code>.
     * @return <code>true</code> if the walk was completed or <code>false</code>
     *         if the walk was cancelled
     */
    public static boolean walkTree(Function1<Node, Boolean> filter, Collection<Node> roots) {
        List<Node> sortedRoots = new ArrayList<Node>(roots);
        Collections.sort(sortedRoots);
        for (Node n : sortedRoots)
            if (!walkTreeRec(filter, n))
               return false;
        return true;
   }

    private static boolean walkTreeRec(Function1<Node, Boolean> filter, Node n) {
        if (!filter.apply(n))
            return false;

        Collection<Node> children = n.getChildren();
        if (!children.isEmpty()) {
            List<Node> sorted = new ArrayList<Node>(children);
            Collections.sort(sorted);
            for (Node child : sorted)
                if (!walkTreeRec(filter, child))
                    return false;
        }
        return true;
    }

}