From jbossws-commits at lists.jboss.org Thu Feb 24 10:49:48 2011 Content-Type: multipart/mixed; boundary="===============2113653858996870148==" MIME-Version: 1.0 From: jbossws-commits at lists.jboss.org To: jbossws-commits at lists.jboss.org Subject: [jbossws-commits] JBossWS SVN: r13798 - in common/trunk/src/main/java/org/jboss/wsf/common: integration and 1 other directories. Date: Thu, 24 Feb 2011 10:49:48 -0500 Message-ID: <201102241549.p1OFnm9E022040@svn01.web.mwc.hst.phx2.redhat.com> --===============2113653858996870148== Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Author: richard.opalka(a)jboss.com Date: 2011-02-24 10:49:48 -0500 (Thu, 24 Feb 2011) New Revision: 13798 Added: common/trunk/src/main/java/org/jboss/wsf/common/sort/ common/trunk/src/main/java/org/jboss/wsf/common/sort/DeploymentAspectSor= ter.java Modified: common/trunk/src/main/java/org/jboss/wsf/common/integration/AbstractDepl= oymentAspect.java Log: providing O(1) DA sorting algorithm Modified: common/trunk/src/main/java/org/jboss/wsf/common/integration/Abstr= actDeploymentAspect.java =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D --- common/trunk/src/main/java/org/jboss/wsf/common/integration/AbstractDep= loymentAspect.java 2011-02-24 15:48:16 UTC (rev 13797) +++ common/trunk/src/main/java/org/jboss/wsf/common/integration/AbstractDep= loymentAspect.java 2011-02-24 15:49:48 UTC (rev 13798) @@ -117,6 +117,10 @@ while (st.hasMoreTokens()) condset.add(st.nextToken()); } + if (!isLast) + { + condset.add("WSObject"); + } return condset; } = @@ -129,6 +133,10 @@ while (st.hasMoreTokens()) condset.add(st.nextToken()); } + if (isLast) + { + condset.add("WSObject"); + } return condset; } = Added: common/trunk/src/main/java/org/jboss/wsf/common/sort/DeploymentAspec= tSorter.java =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D --- common/trunk/src/main/java/org/jboss/wsf/common/sort/DeploymentAspectSo= rter.java (rev 0) +++ common/trunk/src/main/java/org/jboss/wsf/common/sort/DeploymentAspectSo= rter.java 2011-02-24 15:49:48 UTC (rev 13798) @@ -0,0 +1,309 @@ +/* + * JBoss, Home of Professional Open Source + * Copyright (c) 2010, JBoss Inc., and individual contributors as indicated + * by the @authors tag. See the copyright.txt in the distribution for a + * full listing of individual contributors. + * + * This is free software; you can redistribute it and/or modify it + * under the terms of the GNU Lesser General Public License as + * published by the Free Software Foundation; either version 2.1 of + * the License, or (at your option) any later version. + * + * This software is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this software; if not, write to the Free + * Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA + * 02110-1301 USA, or see the FSF site: http://www.fsf.org. + */ +package org.jboss.wsf.common.sort; + +import java.util.HashMap; +import java.util.HashSet; +import java.util.Iterator; +import java.util.LinkedList; +import java.util.List; +import java.util.Map; +import java.util.Set; + +import org.jboss.wsf.spi.deployment.DeploymentAspect; + +/** + * Implements topological sorting for acyclic graphs. + * The algorithm complexity is O(m+n), where m is count of v= ertices and n is count of edges. + * + * @author Richard Opalka + */ +public final class DeploymentAspectSorter = +{ + = + private static final DeploymentAspectSorter INSTANCE =3D new Deployment= AspectSorter(); + + private DeploymentAspectSorter() + { + // forbidden inheritance + } + = + public static DeploymentAspectSorter getInstance() + { + return INSTANCE; + } + = + public List sort(final List aspects) + { + return this.createOrientedGraph(aspects).sort(); + } + + private Graph createOrientedGraph(final List aspects) + { + final Graph graph =3D new Graph(); + + for (final DeploymentAspect aspect : aspects) + { + graph.addVertex(aspect); + } + + graph.createEdges(); + + return graph; + } + + private static class Graph + { + private Map dependencies =3D new HashMap(); + private Set vertices =3D new HashSet(); + + public void addVertex(final DeploymentAspect aspect) + { + // create disjunct sets + final Set inputs =3D new HashSet(); + inputs.addAll(aspect.getRequiresAsSet()); + final Set outputs =3D new HashSet(); + outputs.addAll(aspect.getProvidesAsSet()); + final Set intersection =3D this.getIntersection(inputs, o= utputs); + + // register vertex + final Vertex vertex =3D new Vertex(aspect); + this.vertices.add(vertex); + + // register dependencies + Dependency dependency; + for (final String in : inputs) + { + dependency =3D this.getDependency(in); + dependency.consumers.add(vertex); + } + + for (final String inOut : intersection) + { + dependency =3D this.getDependency(inOut); + dependency.modifiers.add(vertex); + } + + for (final String out : outputs) + { + dependency =3D this.getDependency(out); + dependency.producers.add(vertex); + } + } + + public List sort() + { + // L =E2=86=90 Empty list that will contain the sorted elements + List retVal =3D new LinkedList(); + // S =E2=86=90 Set of all nodes with no incoming edges + List roots =3D this.getRoots(); + + // while S is non-empty do + Vertex root; + List nextLevel; + while(!roots.isEmpty()) + { + // remove a node n from S + root =3D roots.remove(0); + // insert n into L + retVal.add(root.getAspect()); + + // for each node m with an edge e from n to m do + if (root.hasConsumers()) + { + nextLevel =3D new LinkedList(); + for(final Vertex consumer : root.consumers) + { + // remove edge e from the graph + consumer.decrementDegree(); + // if m has no other incoming edges then insert m into S + if (!consumer.hasProducers()) + { + this.remove(consumer); + nextLevel.add(consumer); + } + } + + // append to the end of list in sorted order + roots.addAll(nextLevel); + } + } + + if (this.vertices.size() > 0) + { + // if graph has edges then graph has at least one cycle + throw new IllegalStateException("Cycle detected in subgraph: "= + this.vertices); + } + else + { + // topologically sorted order + return retVal; + } + } + + private Set getIntersection(final Set inputs, final = Set outputs) + { + final Set intersection =3D new HashSet(); + + for (final String input : inputs) + for (final String output : outputs) + if (input.equals(output)) = + intersection.add(input); + + inputs.removeAll(intersection); + outputs.removeAll(intersection); + + return intersection; + } + + private Dependency getDependency(final String name) + { + if (this.dependencies.containsKey(name)) + { + return this.dependencies.get(name); + } + else + { + final Dependency newDependency =3D new Dependency(); + this.dependencies.put(name, newDependency); + return newDependency; + } + } + + private void createEdges() + { + Dependency dependency; + boolean hasModifiers; + + for (final String dependencyName : this.dependencies.keySet()) + { + dependency =3D this.dependencies.get(dependencyName); + hasModifiers =3D dependency.modifiers.size() > 0; + + if (hasModifiers) + { + this.createEdges(dependency.producers, dependency.modifiers= ); + this.createEdges(dependency.modifiers, dependency.consumers= ); + } + else + { + this.createEdges(dependency.producers, dependency.consumers= ); + } + } + } + + private void createEdges(final List producers, final List consumers) + { + for (final Vertex producer : producers) + for (final Vertex consumer : consumers) + { + producer.addConsumer(consumer); + consumer.incrementDegree(); + } + } + + private List getRoots() + { + final List retVal =3D new LinkedList(); + + Vertex current; + for (final Iterator i =3D this.vertices.iterator(); i.has= Next(); ) + { + current =3D i.next(); + if (!current.hasProducers()) + { + retVal.add(current); + i.remove(); + } + } + + return retVal; + } + + private void remove(final Vertex v) + { + this.vertices.remove(v); + } + + private static class Vertex + { + // Wrapped aspect + private DeploymentAspect aspect; + // Incoming edges + private int inDegree; + // Outgoing edges + private List consumers =3D new LinkedList(); + + public Vertex(final DeploymentAspect aspect) + { + this.aspect =3D aspect; + } + + public void incrementDegree() + { + this.inDegree++; + } + + public void decrementDegree() + { + this.inDegree--; + } + + public boolean hasProducers() + { + return this.inDegree > 0; + } + + public void addConsumer(final Vertex v) + { + this.consumers.add(v); + } + + public boolean hasConsumers() + { + return this.consumers.size() > 0; + } + + public DeploymentAspect getAspect() + { + return this.aspect; + } + + public String toString() + { + return this.aspect.toString(); + } + } + + private static class Dependency + { + // aspects creating this dependency + private List producers =3D new LinkedList(); + // aspects modifying this dependency + private List modifiers =3D new LinkedList(); + // aspects consuming this dependency + private List consumers =3D new LinkedList(); + } + + } + +} --===============2113653858996870148==--