From d4bbe6fa031a26a4b3d86f455174a6cc0ed1cdd3 Mon Sep 17 00:00:00 2001 From: dougsleite Date: Mon, 10 Aug 2009 23:15:27 +0000 Subject: - 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 --- .../tuscany/sca/guardian/GuardianGroupImpl.java | 146 ++++---------------- .../tuscany/sca/guardian/InvalidNodeException.java | 30 ++++ .../tuscany/sca/guardian/ResolutionTreeUtils.java | 153 +++++++++++++++++++++ .../guardian-model/src/main/resources/lcaTest.xml | 21 +++ .../tuscany/sca/guardian/itests/LCATestCase.java | 114 +++++++++++++++ .../itests/concurrentexceptions/Launch.java | 6 + 6 files changed, 348 insertions(+), 122 deletions(-) create mode 100644 sandbox/dougsleite/guardian-model/src/main/java/org/apache/tuscany/sca/guardian/InvalidNodeException.java create mode 100644 sandbox/dougsleite/guardian-model/src/main/java/org/apache/tuscany/sca/guardian/ResolutionTreeUtils.java create mode 100644 sandbox/dougsleite/guardian-model/src/main/resources/lcaTest.xml create mode 100644 sandbox/dougsleite/guardian-model/src/test/java/org/apache/tuscany/sca/guardian/itests/LCATestCase.java (limited to 'sandbox/dougsleite') 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 concurrentExList; private Map resolutionTreeElements; + private ResolutionTreeUtils resolutionTreeUtils; public GuardianGroupImpl() { guardianList = new LinkedList(); concurrentExList = new LinkedList(); 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 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 exceptionList, Iterator elements, WrapperInteger currentListSize) { - - OMElement el; - OMAttribute at; - String exClass = null; + private GlobalExceptionInterface checkExceptionResolutionTree(List exceptionList, OMElement rootTree) { + + resolutionTreeUtils.setRoot(rootTree); + String ex1, ex2; GlobalExceptionInterface resolvedEx = null; - boolean isLeaf = false; - - while (elements.hasNext()) { - el = (OMElement) elements.next(); - - // - 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 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 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 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 getMatchingParticipantsOriginal(String regularExpression, GlobalExceptionInterface signaledException) { -// List 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: *, .*, , *., *..*, * *..*..*, || * 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 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 levels; + //R: Map of size n such that R contains the index of the first ocurrence of node 'K' in E + private Map 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 getEulerTourDepthFirstSearch() { + + if (root == null) { + throw new NullPointerException("The root musn't be null"); + } + + if (eulerTour == null) { + eulerTour = new LinkedList(); + levels = new LinkedList(); + + eulerTourDFSRecursive(root, 0); + } + + return eulerTour; + } + + public String getLowestCommonAncestor(String node1, String node2) { + String lca = null; + Integer indexNode1, indexNode2; + + Map 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 getRMap() { + if (rMap == null) { + rMap = new Hashtable(); + + List 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 @@ + + + + + + + + + + + + + + + + + + + + + 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 resolutionTrees = policy.getResolutionTreeElements(); + + List 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 getRootElements(Collection resolutionTrees) { + List rootElements = new LinkedList(); + + 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(); -- cgit v1.2.3