1 files changed, 153 insertions, 0 deletions
diff --git a/sandbox/dougsleite/guardian-model/src/main/java/org/apache/tuscany/sca/guardian/ResolutionTreeUtils.java b/sandbox/dougsleite/guardian-model/src/main/java/org/apache/tuscany/sca/guardian/ResolutionTreeUtils.java
new file mode 100644
index 0000000000..e4bd6652c8
--- /dev/null
+++ b/sandbox/dougsleite/guardian-model/src/main/java/org/apache/tuscany/sca/guardian/ResolutionTreeUtils.java
@@ -0,0 +1,153 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you 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 org.apache.tuscany.sca.guardian;
+
+import java.util.Collections;
+import java.util.Hashtable;
+import java.util.Iterator;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Map;
+import org.apache.axiom.om.OMAttribute;
+import org.apache.axiom.om.OMElement;
+
+public class ResolutionTreeUtils {
+
+    //E: Euler tour of the tree obtained by listing the nodes viseted in a depth firts search of the tree starting from the root. Contains 2n-1 elements
+    private List<String> eulerTour;
+    //L: Array of level numbers such that L[i] contains the tree-depth of the node E[i]. Contains 2n-1 elements
+    private List<Integer> levels;
+    //R: Map of size n such that R<K> contains the index of the first ocurrence of node 'K' in E
+    private Map<String, Integer> rMap;
+    private OMElement root;
+    private int treeSize;
+
+    public ResolutionTreeUtils() {
+        init(null);
+    }
+
+    public ResolutionTreeUtils(OMElement root) {
+        init(root);
+    }
+
+    public void setRoot(OMElement root) {
+        init(root);
+    }
+
+    public List<String> getEulerTourDepthFirstSearch() {
+
+        if (root == null) {
+            throw new NullPointerException("The root musn't be null");
+        }
+
+        if (eulerTour == null) {
+            eulerTour = new LinkedList<String>();
+            levels = new LinkedList<Integer>();
+
+            eulerTourDFSRecursive(root, 0);
+        }
+
+        return eulerTour;
+    }
+
+    public String getLowestCommonAncestor(String node1, String node2) {
+        String lca = null;
+        Integer indexNode1, indexNode2;
+
+        Map<String, Integer> r = getRMap();
+
+        indexNode1 = r.get(node1);
+        indexNode2 = r.get(node2);
+
+        //Check nodes existence
+        if (indexNode1 == null && indexNode2 == null) {
+            throw new InvalidNodeException("Could not find the specified nodes: " + node1 + " and " + node2);
+        } else if (indexNode1 == null) {
+            throw new InvalidNodeException("Could not find the specified nodes: " + node1);
+        } else if (indexNode2 == null) {
+            throw new InvalidNodeException("Could not find the specified nodes: " + node2);
+        }
+
+        int indexLCA;
+        if (indexNode1 < indexNode2) {
+            indexLCA = getRangeMinimumQuery(levels, indexNode1, indexNode2);
+        } else {
+            indexLCA = getRangeMinimumQuery(levels, indexNode2, indexNode1);
+        }
+
+        lca = eulerTour.get(indexLCA);
+
+        return lca;
+    }
+
+    //Get the index of the smallest element between beginIndex and endIndex (both inclusive) in the list
+    private int getRangeMinimumQuery(List list, int beginIndex, int endIndex) {
+
+        List sublist = list.subList(beginIndex, endIndex + 1);
+
+        Object elem = Collections.min(sublist);
+
+        return sublist.indexOf(elem) + beginIndex;
+    }
+
+    private void init(OMElement root) {
+        this.root = root;
+        eulerTour = null;
+        levels = null;
+        rMap = null;
+        treeSize = 0;
+    }
+
+    private void eulerTourDFSRecursive(OMElement node, int level) {
+        String classAttribute = ((OMAttribute) node.getAllAttributes().next()).getAttributeValue();
+        eulerTour.add(classAttribute);
+
+        levels.add(level);
+        treeSize++;
+
+        Iterator children = node.getChildElements();
+
+        OMElement child;
+        while (children.hasNext()) {
+            child = (OMElement) children.next();
+            eulerTourDFSRecursive(child, level + 1);
+            eulerTour.add(classAttribute);
+            levels.add(level);
+        }
+    }
+
+    private Map<String, Integer> getRMap() {
+        if (rMap == null) {
+            rMap = new Hashtable<String, Integer>();
+
+            List<String> tour = getEulerTourDepthFirstSearch();
+            for (int i = 0; i < tour.size(); i++) {
+                String key = tour.get(i);
+                if (!rMap.containsKey(key)) {
+                    rMap.put(key, i);
+                }
+
+                if (rMap.size() == treeSize) {
+                    break;
+                }
+            }
+        }
+        return rMap;
+    }
+}