diff options
Diffstat (limited to 'sandbox/dougsleite/implementation-guardian/src/main/java/org/apache/tuscany/sca/implementation/guardian/common/ResolutionTreeUtils.java')
-rw-r--r-- | sandbox/dougsleite/implementation-guardian/src/main/java/org/apache/tuscany/sca/implementation/guardian/common/ResolutionTreeUtils.java | 153 |
1 files changed, 153 insertions, 0 deletions
diff --git a/sandbox/dougsleite/implementation-guardian/src/main/java/org/apache/tuscany/sca/implementation/guardian/common/ResolutionTreeUtils.java b/sandbox/dougsleite/implementation-guardian/src/main/java/org/apache/tuscany/sca/implementation/guardian/common/ResolutionTreeUtils.java new file mode 100644 index 0000000000..fbf147285e --- /dev/null +++ b/sandbox/dougsleite/implementation-guardian/src/main/java/org/apache/tuscany/sca/implementation/guardian/common/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.implementation.guardian.common; + +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 visited in a depth first 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; + } +} |