bundles/org.simantics.modeling/src/org/simantics/modeling/requests/Nodes.java

   1 package org.simantics.modeling.requests;
   2
   3 import java.util.ArrayDeque;
   4 import java.util.ArrayList;
   5 import java.util.Collection;
   6 import java.util.Collections;
   7 import java.util.Comparator;
   8 import java.util.Deque;
   9 import java.util.List;
  10
  11 import org.eclipse.jface.viewers.IFilter;
  12 import org.simantics.scl.runtime.function.Function1;
  13
  14 /**
  15  * @author Tuukka Lehtonen
  16  */
  17 public class Nodes {
  18
  19     public static Collection<Node> breadthFirstFlatten(IFilter filter, Collection<Node> roots) {
  20         Collection<Node> result = new ArrayList<Node>();
  21         List<Node> sortedRoots = new ArrayList<Node>(roots);
  22         Collections.sort(sortedRoots);
  23         Deque<Node> todo = new ArrayDeque<Node>(sortedRoots);
  24         while (!todo.isEmpty()) {
  25             Node n = todo.removeFirst();
  26             List<Node> sorted = new ArrayList<Node>(n.getChildren());
  27             Collections.sort(sorted);
  28             todo.addAll(sorted);
  29             if (filter == null || filter.select(n))
  30                 result.add(n);
  31         }
  32         return result;
  33     }
  34
  35     public static Collection<Node> depthFirstFlatten(IFilter filter, Collection<Node> roots, Comparator<? super Node> comparator) {
  36         Collection<Node> result = new ArrayList<Node>();
  37         List<Node> sortedRoots = new ArrayList<Node>(roots);
  38         Collections.sort(sortedRoots, comparator);
  39         for (Node n : sortedRoots) {
  40             depthFirstFlattenRec(filter, comparator, n, result);
  41         }
  42         return result;
  43     }
  44
  45     private static Collection<Node> depthFirstFlattenRec(IFilter filter, Comparator<? super Node> comparator, Node n, Collection<Node> result) {
  46         if (filter == null || filter.select(n))
  47             result.add(n);
  48
  49         Collection<Node> children = n.getChildren();
  50         if (children.isEmpty())
  51             return result;
  52
  53         List<Node> sorted = new ArrayList<Node>(children);
  54         Collections.sort(sorted, comparator);
  55         for (Node child : sorted)
  56             depthFirstFlattenRec(filter, comparator, child, result);
  57
  58         return result;
  59     }
  60
  61     /**
  62      * @param f
  63      *            function that takes the walked Node as argument and returns a
  64      *            boolean to describe whether to continue the walk or cancel the
  65      *            walk. The returned value cannot be <code>null</code>.
  66      * @return <code>true</code> if the walk was completed or <code>false</code>
  67      *         if the walk was cancelled
  68      */
  69     public static boolean walkTree(Function1<Node, Boolean> filter, Collection<Node> roots) {
  70         List<Node> sortedRoots = new ArrayList<Node>(roots);
  71         Collections.sort(sortedRoots);
  72         for (Node n : sortedRoots)
  73             if (!walkTreeRec(filter, n))
  74                return false;
  75         return true;
  76    }
  77
  78     private static boolean walkTreeRec(Function1<Node, Boolean> filter, Node n) {
  79         if (!filter.apply(n))
  80             return false;
  81
  82         Collection<Node> children = n.getChildren();
  83         if (!children.isEmpty()) {
  84             List<Node> sorted = new ArrayList<Node>(children);
  85             Collections.sort(sorted);
  86             for (Node child : sorted)
  87                 if (!walkTreeRec(filter, child))
  88                     return false;
  89         }
  90         return true;
  91     }
  92
  93 }