- Modifying the Lowest Common Ancestor (LCA) algorithm. The algorithm is an implementation of the Bender and Farach's LCA algorithm.

git-svn-id: http://svn.us.apache.org/repos/asf/tuscany@802952 13f79535-47bb-0310-9956-ffa450edef68

6 files changed, 348 insertions, 122 deletions

diff --git a/sandbox/dougsleite/guardian-model/src/main/java/org/apache/tuscany/sca/guardian/GuardianGroupImpl.java b/sandbox/dougsleite/guardian-model/src/main/java/org/apache/tuscany/sca/guardian/GuardianGroupImpl.java
index c8964f2b98..53bbeb08ff 100644
--- a/sandbox/dougsleite/guardian-model/src/main/java/org/apache/tuscany/sca/guardian/GuardianGroupImpl.java
+++ b/sandbox/dougsleite/guardian-model/src/main/java/org/apache/tuscany/sca/guardian/GuardianGroupImpl.java
@@ -48,11 +48,13 @@ public class GuardianGroupImpl implements GuardianGroup {
     private InnerGuardianGroupThread innerThread;
     private List<GlobalExceptionInterface> concurrentExList;
     private Map<String, OMElement> resolutionTreeElements;
+    private ResolutionTreeUtils resolutionTreeUtils;
 
     public GuardianGroupImpl() {
         guardianList = new LinkedList<GuardianMember>();
         concurrentExList = new LinkedList<GlobalExceptionInterface>();
         innerThread = new InnerGuardianGroupThread();
+        resolutionTreeUtils = new ResolutionTreeUtils();
     }
 
     @Property(name = "recovery_rules", required = false)
@@ -228,12 +230,6 @@ public class GuardianGroupImpl implements GuardianGroup {
 
                         gmList = getMatchingParticipants(participantMatch, ex);
 
-                        //TESTING--------------------------------------------
-                        for (GuardianMember gm : gmList) {
-                            System.out.println(gm.getParticipantIdentifier());
-                        }
-                        //---------------------------------------------------
-
                         if (!gmList.isEmpty()) {
                             throwExceptionTag(gmList, ex);
                         }
@@ -414,6 +410,7 @@ public class GuardianGroupImpl implements GuardianGroup {
         private GlobalExceptionInterface checkExceptionResolutionTrees(List<GlobalExceptionInterface> exceptionList, Iterator resolutionTreesElements) {
 
             OMElement tree;
+            OMElement root;
             String exceptionLevel = null;
             GlobalExceptionInterface resolvedEx = null;
 
@@ -421,7 +418,8 @@ public class GuardianGroupImpl implements GuardianGroup {
                 tree = (OMElement) resolutionTreesElements.next();
                 exceptionLevel = tree.getAttributeValue(Constants.EXCEPTION_LEVEL_QNAME);
 
-                resolvedEx = checkExceptionResolutionTree(exceptionList, tree.getChildElements(), new WrapperInteger(exceptionList.size()));
+                root = (OMElement) tree.getChildElements().next();
+                resolvedEx = checkExceptionResolutionTree(exceptionList, root);
 
                 if (resolvedEx != null) {
                     break;
@@ -432,56 +430,29 @@ public class GuardianGroupImpl implements GuardianGroup {
         }
 
         //Search for the root of the smallest subtree that contains all the concurrently signaled exceptions. If not found, return null.
-        //FIXME: Check for equal exception classes on the tree
-        //FIXME: Implement the Lowest common ancestor algorithm
-        private GlobalExceptionInterface checkExceptionResolutionTree(List<GlobalExceptionInterface> exceptionList, Iterator elements, WrapperInteger currentListSize) {
-
-            OMElement el;
-            OMAttribute at;
-            String exClass = null;
+        private GlobalExceptionInterface checkExceptionResolutionTree(List<GlobalExceptionInterface> exceptionList, OMElement rootTree) {
+            
+            resolutionTreeUtils.setRoot(rootTree);
+            String ex1, ex2;
             GlobalExceptionInterface resolvedEx = null;
-            boolean isLeaf = false;
-
-            while (elements.hasNext()) {
-                el = (OMElement) elements.next();
-
-                //<exception class="">
-                if (el.getLocalName().equals(Constants.EXCEPTION)) {
-
-                    Iterator it = el.getAllAttributes();
-                    while (it.hasNext()) {
-                        at = (OMAttribute) it.next();
-                        if (at.getLocalName().equals(Constants.CLASS)) {
-                            exClass = at.getAttributeValue();
-                        }
-                    }
 
-                    try {
-                        for (GlobalExceptionInterface ex : exceptionList) {
-                            if (Class.forName(exClass).equals(ex.getClass())) {
-                                currentListSize.decrement();
-                                break;
-                            }
-                        }
+            ex1 = exceptionList.get(0).getClass().getName();
+            for (int i = 1; i < exceptionList.size(); i++) {
+                ex2 = exceptionList.get(i).getClass().getName();
 
-                    } catch (ClassNotFoundException ex1) {
-                        Logger.getLogger(GuardianGroupImpl.class.getName()).log(Level.SEVERE, null, ex1);
-                    }
-
-                    Iterator children = el.getChildElements();
-                    if (children.hasNext()) {
-                        resolvedEx = checkExceptionResolutionTree(exceptionList, children, currentListSize);
-                    } else {
-                        isLeaf = true;
-                    }
+                try {
+                    ex1 = resolutionTreeUtils.getLowestCommonAncestor(ex1, ex2);
+                } catch (InvalidNodeException invalidNodeException) {
+                    ex1 = null;
+                    break;
                 }
             }
 
-            if (resolvedEx == null && currentListSize.getValue() == 0 && !isLeaf) {
+            if (ex1 != null) {
                 Class exceptionClass;
 
                 try {
-                    exceptionClass = Class.forName(exClass);
+                    exceptionClass = Class.forName(ex1);
                     resolvedEx = (GlobalException) exceptionClass.newInstance();
 
                     for (GlobalExceptionInterface ex : exceptionList) {
@@ -495,8 +466,12 @@ public class GuardianGroupImpl implements GuardianGroup {
                 } catch (ClassNotFoundException ex) {
                     Logger.getLogger(GuardianGroupImpl.class.getName()).log(Level.SEVERE, null, ex);
                 }
+
+                return resolvedEx;
+
+            } else {
+                return null;
             }
-            return resolvedEx;
         }
 
         private List<GuardianMember> getMatchingParticipants(String regularExpression, GlobalExceptionInterface signaledException) {
@@ -516,16 +491,10 @@ public class GuardianGroupImpl implements GuardianGroup {
                         if (signaledException.getSignalingParticipants().contains(gm.getParticipantIdentifier())) {
                             matchingParticipants.add(gm);
                         }
-
-                        /*//All concurrent signaler were found
-                        if (matchingParticipants.size() == signaledException.getSignalingParticipants().size()) {
-                        break;
-                        }*/
                     }
                 } else if (regularExpression.toUpperCase().equals("!SIGNALER")) {
                     for (GuardianMember gm : guardianList) {
                         if (!signaledException.getSignalingParticipants().contains(gm.getParticipantIdentifier())) {
-                            //if (!gm.getParticipantIdentifier().equals(signaledException.getSignalingParticipant())) {
                             matchingParticipants.add(gm);
                         }
                     }
@@ -575,47 +544,11 @@ public class GuardianGroupImpl implements GuardianGroup {
                             if (signaledException.getSignalingParticipants().contains(gm.getParticipantIdentifier())) {
                                 matchingParticipants.add(gm);
                             }
-
-                            /*//All concurrent signaler were found
-                            if (matchingParticipants.size() == signaledException.getSignalingParticipants().size()) {
-                            break;
-                            }*/
-
-//                            //ConcurrentGlobalException: there are more than one signaler
-//                            if (signaledException instanceof ConcurrentGlobalException) {
-//                                List<String> signalingPartcipants = ((ConcurrentGlobalException) signaledException).getSignalingParticipants();
-//
-//                                if (signalingPartcipants.contains(gm.getParticipantIdentifier())) {
-//                                    matchingParticipants.add(gm);
-//                                    count++;
-//                                }
-//
-//                                //All concurrent signaler were found
-//                                if (count == signalingPartcipants.size()) {
-//                                    break;
-//                                }
-//
-//                            } else if (gm.getParticipantIdentifier().equals(signaledException.getSignalingParticipant())) {
-//                                matchingParticipants.add(gm);
-//                                break;
-//                            }
                         } //Test if the participant is not Signaler
                         else {
                             if (!signaledException.getSignalingParticipants().contains(gm.getParticipantIdentifier())) {
                                 matchingParticipants.add(gm);
                             }
-
-//                            //ConcurrentGlobalException: there are more than one signaler
-//                            if (signaledException instanceof ConcurrentGlobalException) {
-//                                List<String> signalingPartcipants = ((ConcurrentGlobalException) signaledException).getSignalingParticipants();
-//
-//                                if (!(signalingPartcipants.contains(gm.getParticipantIdentifier()))) {
-//                                    matchingParticipants.add(gm);
-//                                }
-//
-//                            } else if (!gm.getParticipantIdentifier().equals(signaledException.getSignalingParticipant())) {
-//                                matchingParticipants.add(gm);
-//                            }
                         }
                     }
                 }
@@ -625,37 +558,6 @@ public class GuardianGroupImpl implements GuardianGroup {
             return matchingParticipants;
         }
 
-//        private List<GuardianMember> getMatchingParticipantsOriginal(String regularExpression, GlobalExceptionInterface signaledException) {
-//            List<GuardianMember> matchingParticipants = new LinkedList();
-//
-//            if (regularExpression.toUpperCase().equals("SIGNALER")) {
-//                for (GuardianMember gm : guardianList) {
-//                    if (gm.getParticipantIdentifier().equals(signaledException.getSignalingParticipant())) {
-//                        matchingParticipants.add(gm);
-//                        break;
-//                    }
-//                }
-//            } else if (regularExpression.toUpperCase().equals("!SIGNALER")) {
-//                for (GuardianMember gm : guardianList) {
-//                    if (!gm.getParticipantIdentifier().equals(signaledException.getSignalingParticipant())) {
-//                        matchingParticipants.add(gm);
-//                    }
-//                }
-//
-//            } else {
-//                //Create an java regular expression
-//                String re = createJavaRegularExpression(regularExpression);
-//
-//                for (GuardianMember gm : guardianList) {
-//                    if (gm.getParticipantIdentifier().matches(re)) {
-//                        matchingParticipants.add(gm);
-//                    }
-//                }
-//            }
-//
-//            return matchingParticipants;
-//        }
-
         /* Valid expressions: *, <Context>.*, <Context>, *.<Context>, *.<Context>.*,
          *                    *.<Context>.*.<Context>.*, <REG_EXP> || <REG_EXP>
          *
diff --git a/sandbox/dougsleite/guardian-model/src/main/java/org/apache/tuscany/sca/guardian/InvalidNodeException.java b/sandbox/dougsleite/guardian-model/src/main/java/org/apache/tuscany/sca/guardian/InvalidNodeException.java
new file mode 100644
index 0000000000..3df76b0596
--- /dev/null
+++ b/sandbox/dougsleite/guardian-model/src/main/java/org/apache/tuscany/sca/guardian/InvalidNodeException.java
@@ -0,0 +1,30 @@
+/*
+ * 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;
+
+public class InvalidNodeException extends RuntimeException {
+
+    public InvalidNodeException() {
+        super();
+    }
+
+    public InvalidNodeException(String message) {
+        super(message);
+    }
+}
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;
+    }
+}
diff --git a/sandbox/dougsleite/guardian-model/src/main/resources/lcaTest.xml b/sandbox/dougsleite/guardian-model/src/main/resources/lcaTest.xml
new file mode 100644
index 0000000000..e528760ad8
--- /dev/null
+++ b/sandbox/dougsleite/guardian-model/src/main/resources/lcaTest.xml
@@ -0,0 +1,21 @@
+<resolution_trees>
+	<resolution_tree exception_level="1">
+		<exception class="Exception1">
+			<exception class="Exception2">
+				<exception class="Exception4"/>
+				<exception class="Exception5"/>
+			</exception>
+			<exception class="Exception3">
+				<exception class="Exception6"/>
+				<exception class="Exception7"/>
+				<exception class="Exception8"/>
+			</exception>
+		</exception>
+	</resolution_tree>
+</resolution_trees>
+
+
+
+
+
+
diff --git a/sandbox/dougsleite/guardian-model/src/test/java/org/apache/tuscany/sca/guardian/itests/LCATestCase.java b/sandbox/dougsleite/guardian-model/src/test/java/org/apache/tuscany/sca/guardian/itests/LCATestCase.java
new file mode 100644
index 0000000000..bdcb7ac97d
--- /dev/null
+++ b/sandbox/dougsleite/guardian-model/src/test/java/org/apache/tuscany/sca/guardian/itests/LCATestCase.java
@@ -0,0 +1,114 @@
+/*
+ * 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.itests;
+
+import java.io.FileInputStream;
+import org.apache.tuscany.sca.policy.resolutiontrees.*;
+import org.apache.tuscany.sca.guardian.ResolutionTreeUtils;
+import java.util.Collection;
+import java.util.LinkedList;
+import java.util.Map;
+import javax.xml.stream.XMLInputFactory;
+import javax.xml.stream.XMLStreamReader;
+import org.junit.Test;
+import org.apache.axiom.om.OMElement;
+import java.util.List;
+import junit.framework.Assert;
+import org.junit.Before;
+
+public class LCATestCase {
+
+    private ResolutionTreeUtils treeUtils;
+
+    @Before
+    public void init() throws Exception {
+        ResolutionTreesPolicyProcessor processor = new ResolutionTreesPolicyProcessor(null, null);
+
+        FileInputStream fileInputStream = new FileInputStream("src/main/resources/lcaTest.xml");
+        XMLStreamReader reader = XMLInputFactory.newInstance().createXMLStreamReader(fileInputStream);
+
+
+        ResolutionTreesPolicy policy = processor.read(reader);
+        Map<String, OMElement> resolutionTrees = policy.getResolutionTreeElements();
+
+        List<OMElement> rootElements = getRootElements(resolutionTrees.values());
+
+        treeUtils = new ResolutionTreeUtils();
+        treeUtils.setRoot(rootElements.get(0));
+    }
+
+    @Test
+    public void testLCAEx2Ex2() throws Exception {
+        String lca = treeUtils.getLowestCommonAncestor("Exception2", "Exception2");
+        System.out.println("lca: " + lca);
+        Assert.assertEquals("Exception2", lca);
+    }
+
+    @Test
+    public void testLCAEx2Ex3() throws Exception {
+        String lca = treeUtils.getLowestCommonAncestor("Exception2", "Exception3");
+        Assert.assertEquals("Exception1", lca);
+    }
+
+    @Test
+    public void testLCAEx2Ex8() throws Exception {
+        String lca = treeUtils.getLowestCommonAncestor("Exception2", "Exception8");
+        Assert.assertEquals("Exception1", lca);
+    }
+
+    @Test
+    public void testLCAEx4Ex3() throws Exception {
+        String lca = treeUtils.getLowestCommonAncestor("Exception4", "Exception3");
+        Assert.assertEquals("Exception1", lca);
+    }
+
+    @Test
+    public void testLCAEx4Ex5() throws Exception {
+        String lca = treeUtils.getLowestCommonAncestor("Exception4", "Exception5");
+        Assert.assertEquals("Exception2", lca);
+    }
+
+    @Test
+    public void testLCAEx6Ex7() throws Exception {
+        String lca = treeUtils.getLowestCommonAncestor("Exception6", "Exception7");
+        Assert.assertEquals("Exception3", lca);
+    }
+
+    @Test
+    public void testLCAEx1Ex8() throws Exception {
+        String lca = treeUtils.getLowestCommonAncestor("Exception1", "Exception8");
+        Assert.assertEquals("Exception1", lca);
+    }
+
+    @Test
+    public void testLCAEx2Ex5() throws Exception {
+        String lca = treeUtils.getLowestCommonAncestor("Exception2", "Exception5");
+        Assert.assertEquals("Exception2", lca);
+    }
+
+    private List<OMElement> getRootElements(Collection<OMElement> resolutionTrees) {
+        List<OMElement> rootElements = new LinkedList<OMElement>();
+
+        for (OMElement resolutionTree : resolutionTrees) {
+            rootElements.add(resolutionTree.getFirstElement());
+        }
+
+        return rootElements;
+    }
+}
diff --git a/sandbox/dougsleite/guardian-model/src/test/java/org/apache/tuscany/sca/guardian/itests/concurrentexceptions/Launch.java b/sandbox/dougsleite/guardian-model/src/test/java/org/apache/tuscany/sca/guardian/itests/concurrentexceptions/Launch.java
index ff9a0e0b4b..9ac2e9113b 100644
--- a/sandbox/dougsleite/guardian-model/src/test/java/org/apache/tuscany/sca/guardian/itests/concurrentexceptions/Launch.java
+++ b/sandbox/dougsleite/guardian-model/src/test/java/org/apache/tuscany/sca/guardian/itests/concurrentexceptions/Launch.java
@@ -46,6 +46,12 @@ public class Launch {
 
         System.in.read();
 
+        System.out.println("Starting participant4...");
+        Node c4 = scaDomain.getService(Node.class, "Participant4");
+        c4.execute();
+
+        System.in.read();
+
         System.out.println("Forcing exception ocurrence at participant1...");
         TestInterface t = scaDomain.getService(TestInterface.class, "Participant1");
         t.forcePrimaryServiceFailureException();