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

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