tomee-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From dblev...@apache.org
Subject svn commit: r683427 - in /openejb/trunk/openejb3/container/openejb-core/src: main/java/org/apache/openejb/util/CircularReferencesException.java main/java/org/apache/openejb/util/References.java test/java/org/apache/openejb/util/ReferencesTest.java
Date Wed, 06 Aug 2008 22:10:37 GMT
Author: dblevins
Date: Wed Aug  6 15:10:36 2008
New Revision: 683427

URL: http://svn.apache.org/viewvc?rev=683427&view=rev
Log:
utility code for sorting a list of objects where objects in the list have references to other
objects in the list

Added:
    openejb/trunk/openejb3/container/openejb-core/src/main/java/org/apache/openejb/util/CircularReferencesException.java
    openejb/trunk/openejb3/container/openejb-core/src/main/java/org/apache/openejb/util/References.java
    openejb/trunk/openejb3/container/openejb-core/src/test/java/org/apache/openejb/util/ReferencesTest.java

Added: openejb/trunk/openejb3/container/openejb-core/src/main/java/org/apache/openejb/util/CircularReferencesException.java
URL: http://svn.apache.org/viewvc/openejb/trunk/openejb3/container/openejb-core/src/main/java/org/apache/openejb/util/CircularReferencesException.java?rev=683427&view=auto
==============================================================================
--- openejb/trunk/openejb3/container/openejb-core/src/main/java/org/apache/openejb/util/CircularReferencesException.java
(added)
+++ openejb/trunk/openejb3/container/openejb-core/src/main/java/org/apache/openejb/util/CircularReferencesException.java
Wed Aug  6 15:10:36 2008
@@ -0,0 +1,34 @@
+/**
+ * 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.openejb.util;
+
+import java.util.List;
+
+/**
+ * @version $Rev$ $Date$
+ */
+public class CircularReferencesException extends RuntimeException {
+    private final List<List> circuits;
+
+    public CircularReferencesException(List<List> circuits) {
+        this.circuits = circuits;
+    }
+
+    public List<List> getCircuits() {
+        return circuits;
+    }
+}

Added: openejb/trunk/openejb3/container/openejb-core/src/main/java/org/apache/openejb/util/References.java
URL: http://svn.apache.org/viewvc/openejb/trunk/openejb3/container/openejb-core/src/main/java/org/apache/openejb/util/References.java?rev=683427&view=auto
==============================================================================
--- openejb/trunk/openejb3/container/openejb-core/src/main/java/org/apache/openejb/util/References.java
(added)
+++ openejb/trunk/openejb3/container/openejb-core/src/main/java/org/apache/openejb/util/References.java
Wed Aug  6 15:10:36 2008
@@ -0,0 +1,265 @@
+/**
+ * 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.openejb.util;
+
+import javax.ejb.Stateless;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.LinkedHashMap;
+import java.util.LinkedHashSet;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+import java.util.Iterator;
+
+/**
+ * @version $Rev$ $Date$
+ */
+public class References {
+
+    @Stateless
+    public static class TesterBean implements Tester {
+        public Object call(Object object) {
+            return object;
+        }
+    }
+
+    public interface Tester {
+        public Object call(Object object);
+    }
+
+    {
+        Tester tester = null;
+        tester.call(int.class)
+    }
+
+    public static interface Visitor<T> {
+        String getName(T t);
+
+        Set<String> getReferences(T t);
+    }
+
+    /**
+     * Items will be sorted from least amount of references to most amount of references.
+     * Original order will be maintained only within those bounds.
+     *
+     * If one or more circular references are detected a CircularReferenceException will
+     * be thrown containing lists of all circuits sorted from lowest to highest.
+     *
+     * @param objects
+     * @param visitor
+     * @return
+     */
+    public static <T> List<T> sort(List<T> objects, Visitor<T> visitor)
{
+        final Map<String, Node> nodes = new LinkedHashMap<String, Node>();
+
+        // Create nodes
+        for (T obj : objects) {
+            String name = visitor.getName(obj);
+            Node node = new Node(name, obj);
+            nodes.put(name, node);
+        }
+
+        // Link nodes
+        for (Node node : nodes.values()) {
+            for (String name : visitor.getReferences((T) node.object)) {
+                Node ref = nodes.get(name);
+                node.references.add(ref);
+                ref.refernceCount++;
+            }
+
+        }
+
+        // find all initial leaf nodes (and islands)
+        List<Node> sortedNodes = new ArrayList<Node>(nodes.size());
+        LinkedList<Node> leafNodes = new LinkedList<Node>();
+        for (Node n : nodes.values()) {
+            if (n.refernceCount == 0) {
+                // if the node is totally isolated (no in or out refs),
+                // move it directly to the finished list, so they are first
+
+                if (n.references.size() == 0) {
+
+                    sortedNodes.add(n);
+
+
+                } else {
+
+
+                    leafNodes.add(n);
+
+                }
+            }
+        }
+
+        // pluck the leaves until there are no leaves remaining
+        while (!leafNodes.isEmpty()) {
+            Node node = leafNodes.removeFirst();
+            sortedNodes.add(node);
+            for (Node ref : node.references) {
+                ref.refernceCount--;
+                if (ref.refernceCount == 0) {
+                    leafNodes.add(ref);
+                }
+            }
+        }
+
+        // There are no more leaves so if there are there still
+        // unprocessed nodes in the graph, we have one or more curcuits
+        if (sortedNodes.size() != nodes.size()) {
+
+            Set<Circuit> circuits = new LinkedHashSet<Circuit>();
+
+            for (Node node : nodes.values()) {
+                findCircuits(circuits, node, new java.util.Stack<Node>());
+            }
+
+            ArrayList<Circuit> list = new ArrayList<Circuit>(circuits);
+            Collections.sort(list);
+
+            List<List> all = new ArrayList<List>();
+            for (Circuit circuit : list) {
+                all.add((List) unwrap(circuit.nodes));
+            }
+
+            throw new CircularReferencesException(all);
+        }
+
+        List<T> sortedObjects = unwrap(sortedNodes);
+        Collections.reverse(sortedObjects);
+        return sortedObjects;
+    }
+
+    private static <T> List<T> unwrap(List<Node> nodes) {
+        ArrayList<T> referees = new ArrayList<T>(nodes.size());
+        for (Node node : nodes) {
+            referees.add((T) node.object);
+        }
+        return referees;
+    }
+
+    private static void findCircuits(Set<Circuit> circuits, Node node, java.util.Stack<Node>
stack) {
+        if (stack.contains(node)) {
+            int fromIndex = stack.indexOf(node);
+            int toIndex = stack.size();
+            ArrayList<Node> circularity = new ArrayList<Node>(stack.subList(fromIndex,
toIndex));
+
+            // add ending node to list so a full circuit is shown
+            circularity.add(node);
+
+            Circuit circuit = new Circuit(circularity);
+
+            circuits.add(circuit);
+
+            return;
+        }
+
+        stack.push(node);
+
+        for (Node reference : node.references) {
+            findCircuits(circuits, reference, stack);
+        }
+
+        stack.pop();
+    }
+
+    private static class Node implements Comparable<Node> {
+        private final String name;
+        private Object object;
+        private final List<Node> references = new ArrayList<Node>();
+        private int refernceCount;
+
+        public Node(String name, Object object) {
+            this.name = name;
+            this.object = object;
+        }
+
+        public boolean equals(Object o) {
+            if (this == o) return true;
+            if (o == null || getClass() != o.getClass()) return false;
+
+            final Node node = (Node) o;
+
+            return name.equals(node.name);
+        }
+
+        public int hashCode() {
+            return name.hashCode();
+        }
+
+        public int compareTo(Node o) {
+            return this.name.compareTo(o.name);
+        }
+
+        public String toString() {
+            return "Node("+ name +" : "+ Join.join(",", unwrap(references))+")";
+        }
+    }
+
+    private static class Circuit implements Comparable<Circuit> {
+        private final List<Node> nodes;
+        private final List<Node> atomic;
+
+        public Circuit(List<Node> nodes) {
+            this.nodes = nodes;
+            atomic = new ArrayList<Node>(nodes);
+            atomic.remove(atomic.size()-1);
+            Collections.sort(atomic);
+        }
+
+        public List<Node> getNodes() {
+            return nodes;
+        }
+
+        public boolean equals(Object o) {
+            if (this == o) return true;
+            if (o == null || getClass() != o.getClass()) return false;
+
+            final Circuit circuit = (Circuit) o;
+
+            if (!atomic.equals(circuit.atomic)) return false;
+
+            return true;
+        }
+
+        public int hashCode() {
+            return atomic.hashCode();
+        }
+
+        public int compareTo(Circuit o) {
+            int i = atomic.size() - o.atomic.size();
+            if (i != 0) return i;
+
+            Iterator<Node> iterA = atomic.listIterator();
+            Iterator<Node> iterB = o.atomic.listIterator();
+            while (iterA.hasNext() && iterB.hasNext()) {
+                Node a = iterA.next();
+                Node b = iterB.next();
+                i = a.compareTo(b);
+                if (i != 0) return i;
+            }
+
+            return 0;
+        }
+
+        public String toString() {
+            return "Circuit(" + Join.join(",", unwrap(nodes)) + ")";
+        }
+    }
+
+}

Added: openejb/trunk/openejb3/container/openejb-core/src/test/java/org/apache/openejb/util/ReferencesTest.java
URL: http://svn.apache.org/viewvc/openejb/trunk/openejb3/container/openejb-core/src/test/java/org/apache/openejb/util/ReferencesTest.java?rev=683427&view=auto
==============================================================================
--- openejb/trunk/openejb3/container/openejb-core/src/test/java/org/apache/openejb/util/ReferencesTest.java
(added)
+++ openejb/trunk/openejb3/container/openejb-core/src/test/java/org/apache/openejb/util/ReferencesTest.java
Wed Aug  6 15:10:36 2008
@@ -0,0 +1,204 @@
+/**
+ * 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.openejb.util;
+
+import static org.apache.openejb.util.References.sort;
+import junit.framework.TestCase;
+
+import java.util.LinkedHashSet;
+import java.util.Set;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Arrays;
+import java.util.ListIterator;
+import java.util.Iterator;
+
+/**
+ * @version $Rev$ $Date$
+ */
+public class ReferencesTest extends TestCase {
+
+    private BeanVisitor visitor = new BeanVisitor();
+    private List<Bean> beans;
+
+    public void test() {
+
+        beans = new ArrayList<Bean>();
+
+        Bean a = bean("a");
+        Bean b = bean("b", "a");
+        Bean c = bean("c", "b");
+
+        List<Bean> actual = sort(beans, visitor);
+
+        assertEquals(expected(a, b, c), actual);
+    }
+
+    public void testSimple() {
+
+        beans = new ArrayList<Bean>();
+
+        Bean c = bean("c", "b", "a");
+        Bean b = bean("b", "a");
+        Bean a = bean("a");
+
+        List<Bean> actual = sort(beans, visitor);
+
+        assertEquals(expected(a, b, c), actual);
+    }
+
+    public void testOrder() {
+
+        beans = new ArrayList<Bean>();
+
+        Bean c = bean("c", "b", "a");
+        Bean b = bean("b", "a");
+        Bean a = bean("a");
+
+        Bean f = bean("f", "e", "d");
+        Bean e = bean("e", "d");
+        Bean d = bean("d");
+
+        List<Bean> actual = sort(beans, visitor);
+
+        assertEquals(expected(d, a, e, b, f, c), actual);
+    }
+
+    public void testOrder2() {
+
+        beans = new ArrayList<Bean>();
+
+        Bean c = bean("c", "b", "a");
+        Bean a = bean("a");
+        Bean b = bean("b", "a", "d");
+
+        Bean f = bean("f", "e", "d", "c", "b", "a");
+        Bean d = bean("d", "a");
+        Bean e = bean("e", "d", "b", "a");
+
+        List<Bean> actual = sort(beans, visitor);
+
+        assertEquals(expected(a, d, b, c, e, f), actual);
+    }
+
+
+    public void testCircuit() {
+
+        beans = new ArrayList<Bean>();
+
+        Bean a = bean("a", "c");
+        Bean b = bean("b", "a");
+        Bean c = bean("c", "b");
+
+        try {
+            sort(beans, visitor);
+            fail("Ciruit should have been detected");
+        } catch (CircularReferencesException e) {
+            List<List> circuits = e.getCircuits();
+            assertEquals(1, circuits.size());
+            assertEquals(expected(a, c, b, a), circuits.get(0));
+        }
+    }
+
+
+    public void testCircuit2() {
+
+        beans = new ArrayList<Bean>();
+
+        Bean a = bean("a", "c");
+        Bean b = bean("b", "a");
+        Bean c = bean("c", "b");
+
+        Bean d = bean("d", "f");
+        Bean e = bean("e", "d");
+        Bean f = bean("f", "e");
+
+        try {
+            sort(beans, visitor);
+            fail("Ciruit should have been detected");
+        } catch (CircularReferencesException cre) {
+            List<List> circuits = cre.getCircuits();
+            assertEquals(2, circuits.size());
+            assertEquals(expected(a, c, b, a), circuits.get(0));
+            assertEquals(expected(d, f, e, d), circuits.get(1));
+        }
+    }
+
+    public void testCircuit3() {
+
+        beans = new ArrayList<Bean>();
+
+        Bean a = bean("a", "a", "b", "c");
+        Bean b = bean("b", "a", "b", "c");
+        Bean c = bean("c", "a", "b", "c");
+
+        try {
+            sort(beans, visitor);
+            fail("Ciruit should have been detected");
+        } catch (CircularReferencesException cre) {
+            List<List> circuits = cre.getCircuits();
+            assertEquals(7, circuits.size());
+            Iterator<List> actual = circuits.listIterator();
+
+            assertEquals(expected(a, a), actual.next());
+            assertEquals(expected(b, b), actual.next());
+            assertEquals(expected(c, c), actual.next());
+            assertEquals(expected(a, b, a), actual.next());
+            assertEquals(expected(a, c, a), actual.next());
+            assertEquals(expected(b, c, b), actual.next());
+            assertEquals(expected(a, b, c, a), actual.next());
+        }
+    }
+
+    private List<Bean> expected(Bean... beans){
+        return Arrays.asList(beans);
+    }
+
+    private Bean bean(String name, String... refs) {
+        Bean bean = new Bean(name, refs);
+        beans.add(bean);
+        return bean;
+    }
+
+
+    public static class Bean {
+        private final String name;
+        private final Set<String> refs;
+
+        public Bean(String name, String... refs) {
+            this.name = name;
+            this.refs = new LinkedHashSet<String>(refs.length);
+            for (String s : refs) {
+                this.refs.add(s);
+            }
+        }
+
+        public String toString() {
+            return name;
+        }
+    }
+
+    public static class BeanVisitor implements References.Visitor<Bean> {
+        public String getName(Bean t) {
+            return t.name;
+        }
+
+        public Set<String> getReferences(Bean t) {
+            return t.refs;
+        }
+    }
+}



Mime
View raw message