From 2e6514ec34061c3c4b2aecae539ac06b1988398b Mon Sep 17 00:00:00 2001 From: jjenista Date: Fri, 8 Apr 2011 22:35:26 +0000 Subject: [PATCH] commit the temporarily abandoned version of Delaunay refinement --- Robust/src/Benchmarks/oooJava/D3/Cavity.java | 190 ++++++++++++ .../oooJava/D3/DirectedEdgeGraph.java | 208 +++++++++++++ .../Benchmarks/oooJava/D3/DirectedGraph.java | 108 +++++++ .../src/Benchmarks/oooJava/D3/EdgeGraph.java | 28 ++ .../Benchmarks/oooJava/D3/EdgeGraphNode.java | 104 +++++++ Robust/src/Benchmarks/oooJava/D3/Edge_d.java | 6 + Robust/src/Benchmarks/oooJava/D3/Element.java | 237 +++++++++++++++ .../Benchmarks/oooJava/D3/ElementEdge.java | 69 +++++ Robust/src/Benchmarks/oooJava/D3/Graph.java | 36 +++ .../src/Benchmarks/oooJava/D3/GraphEdge.java | 28 ++ .../src/Benchmarks/oooJava/D3/GraphNode.java | 75 +++++ Robust/src/Benchmarks/oooJava/D3/Mesh.java | 160 ++++++++++ Robust/src/Benchmarks/oooJava/D3/Node.java | 12 + Robust/src/Benchmarks/oooJava/D3/Pair.java | 47 +++ .../oooJava/D3/SerialDelaunayRefinement.java | 277 ++++++++++++++++++ Robust/src/Benchmarks/oooJava/D3/Stack.java | 161 ++++++++++ .../src/Benchmarks/oooJava/D3/Subgraph.java | 84 ++++++ Robust/src/Benchmarks/oooJava/D3/Tuple.java | 154 ++++++++++ .../oooJava/D3/UndirectedEdgeGraph.java | 22 ++ .../oooJava/D3/UndirectedEdgeGraphNode.java | 16 + Robust/src/Benchmarks/oooJava/D3/makefile | 8 + 21 files changed, 2030 insertions(+) create mode 100755 Robust/src/Benchmarks/oooJava/D3/Cavity.java create mode 100755 Robust/src/Benchmarks/oooJava/D3/DirectedEdgeGraph.java create mode 100755 Robust/src/Benchmarks/oooJava/D3/DirectedGraph.java create mode 100755 Robust/src/Benchmarks/oooJava/D3/EdgeGraph.java create mode 100755 Robust/src/Benchmarks/oooJava/D3/EdgeGraphNode.java create mode 100755 Robust/src/Benchmarks/oooJava/D3/Edge_d.java create mode 100755 Robust/src/Benchmarks/oooJava/D3/Element.java create mode 100755 Robust/src/Benchmarks/oooJava/D3/ElementEdge.java create mode 100755 Robust/src/Benchmarks/oooJava/D3/Graph.java create mode 100755 Robust/src/Benchmarks/oooJava/D3/GraphEdge.java create mode 100755 Robust/src/Benchmarks/oooJava/D3/GraphNode.java create mode 100755 Robust/src/Benchmarks/oooJava/D3/Mesh.java create mode 100755 Robust/src/Benchmarks/oooJava/D3/Node.java create mode 100755 Robust/src/Benchmarks/oooJava/D3/Pair.java create mode 100755 Robust/src/Benchmarks/oooJava/D3/SerialDelaunayRefinement.java create mode 100755 Robust/src/Benchmarks/oooJava/D3/Stack.java create mode 100755 Robust/src/Benchmarks/oooJava/D3/Subgraph.java create mode 100755 Robust/src/Benchmarks/oooJava/D3/Tuple.java create mode 100755 Robust/src/Benchmarks/oooJava/D3/UndirectedEdgeGraph.java create mode 100755 Robust/src/Benchmarks/oooJava/D3/UndirectedEdgeGraphNode.java create mode 100755 Robust/src/Benchmarks/oooJava/D3/makefile diff --git a/Robust/src/Benchmarks/oooJava/D3/Cavity.java b/Robust/src/Benchmarks/oooJava/D3/Cavity.java new file mode 100755 index 00000000..ab611468 --- /dev/null +++ b/Robust/src/Benchmarks/oooJava/D3/Cavity.java @@ -0,0 +1,190 @@ +public class Cavity { + + protected Tuple center; + protected Node centerNode; + protected Element centerElement; + protected int dim; + protected LinkedList frontier; + protected Subgraph pre; + protected Subgraph post; + private final UndirectedEdgeGraph graph; + protected HashSet connections; + + public Cavity(UndirectedEdgeGraph mesh) { + center = null; + graph = mesh; + connections = new HashSet(); + frontier = new LinkedList(); + pre = new Subgraph(); + post = new Subgraph(); + } + + public Subgraph getPre() { + return pre; + } + + public Subgraph getPost() { + return post; + } + + public void triggerAbort() { + } + + public void triggerBorderConflict() { + } + + public void initialize(Node node) { + pre.reset(); + post.reset(); + connections.clear(); + frontier = new LinkedList(); + centerNode = node; + for (centerElement = (Element) getNodeData(centerNode); graph.containsNode(centerNode) + && centerElement.isObtuse();) { + Edge_d oppositeEdge = getOpposite(centerNode); + if (getSource(oppositeEdge) == centerNode) + centerNode = getDest(oppositeEdge); + else + centerNode = getSource(oppositeEdge); + centerElement = (Element) getNodeData(centerNode); + if (centerNode == null) + System.exit(-1); + } + + center = centerElement.center(); + dim = centerElement.getDim(); + pre.addNode(centerNode); + frontier.addLast(centerNode); + } + + private Edge_d getOpposite(Node node) { + Element element = (Element) graph.getNodeData(node); + + // Don't think we'd run into it but.. + // TODO check this. + // if(neighbors.size() != 3) + // throw new Error(String.format("neighbors %d", new Object[] { + // Integer.valueOf(neighbors.size()) + // })); + + int cntOutNeighbors = 0; + + for (Iterator iterator = graph.getOutNeighbors(node); iterator.hasNext();) { + ++cntOutNeighbors; + Node neighbor = (Node) iterator.next(); + Edge_d edge = graph.getEdge(node, neighbor); + ElementEdge edge_data = (ElementEdge) graph.getEdgeData(edge); + if (element.getObtuse().notEquals(edge_data.getPoint(0)) + && element.getObtuse().notEquals(edge_data.getPoint(1))) + return edge; + } + + System.out.println("Error: \"Edge\" in Cavity.java getOpposite(Node)"); + System.out.println(" tri="+element+" has "+cntOutNeighbors+" out-neighbors"); + System.out.println(" obtuse="+element.getObtuse()); + System.exit(-1); + return null; // it's here so the compiler doesn't complain. + } + + public boolean isMember(Node node) { + Element element = (Element) getNodeData(node); + return element.inCircle(center); + } + + public void build() { + while (frontier.size() != 0) { + Node curr = (Node) frontier.removeFirst(); + for (Iterator iterator = getOutNeighbors(curr); iterator.hasNext();) { + Node next = (Node) iterator.next(); + Element nextElement = (Element) getNodeData(next); + Edge_d edge = getEdge(curr, next); + if ((dim != 2 || nextElement.getDim() != 2 || next == centerNode) && isMember(next)) { + if (nextElement.getDim() == 2 && dim != 2) { + initialize(next); + build(); + return; + } + if (!pre.existsNode(next)) { + pre.addNode(next); + pre.addEdge(edge); + frontier.addLast(next); + } + } else if (!connections.contains(edge)) { + connections.add(edge); + pre.addBorder(next); + } + } + + } + } + + public void update() { + if (centerElement.getDim() == 2) { + Element ele1 = new Element(center, centerElement.getPoint(0)); + Node node1 = new UndirectedEdgeGraphNode(ele1); + post.addNode(node1); + Element ele2 = new Element(center, centerElement.getPoint(1)); + Node node2 = new UndirectedEdgeGraphNode(ele2); + post.addNode(node2); + } + Node ne_node; + for (HashMapIterator iterator = connections.iterator(); iterator.hasNext(); post.addNode(ne_node)) { + Edge_d conn = (Edge_d) iterator.next(); + ElementEdge edge = (ElementEdge) getEdgeData(conn); + Element new_element = new Element(center, edge.getPoint(0), edge.getPoint(1)); + ne_node = new UndirectedEdgeGraphNode(new_element); + Node ne_connection; + if (pre.existsNode(getDest(conn))) + ne_connection = getSource(conn); + else + ne_connection = getDest(conn); + ElementEdge new_edge = + new_element.getRelatedEdge((Element) getNodeData(ne_connection)); + post.addEdge(createEdge(ne_node, ne_connection, new_edge)); + + // Collection postnodes = (Collection)post.getNodes().clone(); + LinkedList postnodes = new LinkedList(); + for (Iterator it = post.getNodes().iterator(); it.hasNext();) { + postnodes.addLast(it.next()); + } + + for (Iterator iterator1 = postnodes.iterator(); iterator1.hasNext();) { + Node node = (Node) iterator1.next(); + Element element = (Element) getNodeData(node); + if (element.isRelated(new_element)) { + ElementEdge ele_edge = new_element.getRelatedEdge(element); + post.addEdge(createEdge(ne_node, node, ele_edge)); + } + } + } + } + + private Object getNodeData(Node n) { + return ((EdgeGraphNode) n).data; + } + + public Node getSource(Edge_d e) { + return ((GraphEdge) e).getSrc(); + } + + public Node getDest(Edge_d e) { + return ((GraphEdge) e).getDest(); + } + + public Edge_d getEdge(Node src, Node dest) { + return ((EdgeGraphNode) src).getOutEdge((EdgeGraphNode) dest); + } + + + public Edge_d createEdge(Node src, Node dest, Object e) { + return new GraphEdge((EdgeGraphNode) src, (EdgeGraphNode) dest, e); + } + + public Iterator getOutNeighbors(Node src) { + return ((EdgeGraphNode) src).getOutNeighbors(); + } + + public Object getEdgeData(Edge_d e) { + return ((GraphEdge) e).d; + } +} diff --git a/Robust/src/Benchmarks/oooJava/D3/DirectedEdgeGraph.java b/Robust/src/Benchmarks/oooJava/D3/DirectedEdgeGraph.java new file mode 100755 index 00000000..9252a22c --- /dev/null +++ b/Robust/src/Benchmarks/oooJava/D3/DirectedEdgeGraph.java @@ -0,0 +1,208 @@ +public class DirectedEdgeGraph implements EdgeGraph { + + // jjenista - we need this set to find all nodes in a graph + // (as hard a problem as keeping a reference to one node that + // is in the graph from which to do a traversal and find all + // nodes currently in the graph). + // + // Problem: when you add or remove one node, the obvious update + // is to add or remove it to this set as well. That is a conflict + // for concurrent add and remove ops that don't collide in terms of + // modifying the graph elements though. + // + // SOLUTION: the all-nodes set is invalid after node add/remove ops + // until you run discoverAllNodes(src) + protected HashSet nodes; + + // only use when the nodes set is up-to-date + public DirectedEdgeGraph() { nodes = new HashSet(); } + public Iterator iterator() { return nodes.iterator(); } + public int getNumNodes() { return nodes.size(); } + public Node getRandom() { return (Node) nodes.iterator().next(); } + + // make the node set up to date + public void discoverAllNodes( Node src ) { + nodes.clear(); + Stack toVisit = new Stack(); + toVisit.push( src ); + nodes.add( src ); + + while( !toVisit.isEmpty() ) { + EdgeGraphNode n =(EdgeGraphNode) toVisit.pop(); + + if( !n.inGraph ) { + System.out.println( "Error: found a node actual in the graph but not marked!" ); + System.exit( -1 ); + } + + for( Iterator itrInNei = n.getInNeighbors(); itrInNei.hasNext(); ) { + Node nNei = (Node) itrInNei.next(); + if (nNei==null) { + System.out.println("NULLIN"); + continue; + } + + if( !nodes.contains( nNei ) ) { + toVisit.push( nNei ); + nodes.add(nNei); + } + } + for( Iterator itrOutNei = n.getOutNeighbors(); itrOutNei.hasNext(); ) { + Node nNei = (Node) itrOutNei.next(); + if (nNei==null) { + System.out.println("NULLOUT"); + continue; + } + if( !nodes.contains( nNei ) ) { + toVisit.push( nNei ); + nodes.add(nNei); + } + } + } + } + + // these are the normal methods for truly adding and removing nodes + // from the graph, nodes know locally if they are in and out but they + // haven't been added or removed from the nodes set until ABOVE methods + public boolean addNode(Node n) { + boolean notInAlready = !n.inGraph; + n.inGraph = true; + return notInAlready; + } + + public boolean removeNode(Node n) { + boolean wasIn = n.inGraph; + n.inGraph = false; + removeConnectingEdges((EdgeGraphNode) n); + return wasIn; + } + + public boolean containsNode(Node n) { + return n.inGraph; + } + + + + + + public boolean addEdge(Edge_d e) { + GraphEdge ge = (GraphEdge) e; + EdgeGraphNode src = ge.getSrc(); + EdgeGraphNode dest = ge.getDest(); + return src.addOutEdge(dest, ge) ? dest.addInEdge(src, ge) : false; + } + + public Edge_d createEdge(Node src, Node dest, Object e) { + return new GraphEdge((EdgeGraphNode) src, (EdgeGraphNode) dest, e); + } + + public Node getDest(Edge_d e) { + return ((GraphEdge) e).getDest(); + } + + public Edge_d getEdge(Node src, Node dest) { + return ((EdgeGraphNode) src).getOutEdge((EdgeGraphNode) dest); + } + + public Iterator getInEdges(Node n) { + return ((EdgeGraphNode) n).getInEdges(); + } + + public Iterator getOutEdges(Node n) { + return ((EdgeGraphNode) n).getOutEdges(); + } + + public Node getSource(Edge_d e) { + return ((GraphEdge) e).src; + } + + public boolean hasEdge(Edge_d e) { + GraphEdge ge = (GraphEdge) e; + return ge.getSrc().hasOutNeighbor(ge.getDest()); + } + + public boolean removeEdge(Edge_d e) { + GraphEdge ge = (GraphEdge) e; + EdgeGraphNode src = ge.getSrc(); + EdgeGraphNode dest = ge.getDest(); + return src.removeOutEdge(dest) ? dest.removeInEdge(src) : false; + } + + public boolean addNeighbor(Node src, Node dest) { + throw new UnsupportedOperationException( + "addNeighbor not supported in EdgeGraphs. Use createEdge/addEdge instead"); + } + + public Node createNode(Object n) { + return new EdgeGraphNode(n); + } + + public Iterator getInNeighbors(Node src) { + return ((EdgeGraphNode) src).getInNeighbors(); + } + + public int getInNeighborsSize(Node node) { + return ((EdgeGraphNode) node).inEdges.size(); + } + + public Iterator getOutNeighbors(Node src) { + return ((EdgeGraphNode) src).getOutNeighbors(); + } + + public int getOutNeighborsSize(Node node) { + return ((EdgeGraphNode)node).outEdges.size(); + } + + public boolean removeNeighbor(Node src, Node dest) { + EdgeGraphNode gsrc = (EdgeGraphNode) src; + EdgeGraphNode gdest = (EdgeGraphNode) dest; + return gsrc.removeOutEdge(gdest) ? gdest.removeInEdge(gsrc) : false; + } + + public Object getEdgeData(Edge_d e) { + return ((GraphEdge) e).d; + } + + public Object setEdgeData(Edge_d e, Object d) { + GraphEdge ge = (GraphEdge) e; + Object retval = ge.d; + ge.d = d; + return retval; + } + + public Object getNodeData(Node n) { + EdgeGraphNode egn = (EdgeGraphNode) n; + return egn.data; + } + + public boolean hasNeighbor(Node src, Node dest) { + EdgeGraphNode esrc = (EdgeGraphNode) src; + EdgeGraphNode edest = (EdgeGraphNode) dest; + return esrc.hasOutNeighbor(edest); + } + + protected void removeConnectingEdges(EdgeGraphNode n) { + EdgeGraphNode g; + for (Iterator iterator1 = n.getOutNeighborsCopy(); iterator1.hasNext();) { + g = (EdgeGraphNode) iterator1.next(); + removeNeighbor(n, g); + } + + for (Iterator iterator2 = n.getInNeighborsCopy(); iterator2.hasNext(); ) { + g = (EdgeGraphNode) iterator2.next(); + removeNeighbor(g, n); + } + + } + + public Object setNodeData(Node n, Object d) { + EdgeGraphNode egn = (EdgeGraphNode) n; + Object retval = egn.data; + egn.data = d; + return retval; + } + + public boolean isDirected() { + return true; + } +} diff --git a/Robust/src/Benchmarks/oooJava/D3/DirectedGraph.java b/Robust/src/Benchmarks/oooJava/D3/DirectedGraph.java new file mode 100755 index 00000000..89aece39 --- /dev/null +++ b/Robust/src/Benchmarks/oooJava/D3/DirectedGraph.java @@ -0,0 +1,108 @@ +public class DirectedGraph implements Graph { + //protected HashSet nodes; + + public DirectedGraph() { + // nodes = Collections.synchronizedSet(new HashSet()); + //nodes = new HashSet(); + } + + public boolean addNeighbor(Node src, Node dest) { + GraphNode src_c = (GraphNode) src; + GraphNode dest_c = (GraphNode) dest; + return src_c.addOutNeighbor(dest_c) ? dest_c.addInNeighbor(src_c) : false; + } + + public boolean addNode(Node n) { + boolean notInAlready = !n.inGraph; + n.inGraph = true; + return notInAlready; + } + + public boolean containsNode(Node n) { + n.inGraph; + } + + public Node createNode(Object n) { + return new GraphNode(n); + } + + // Not proper way to do it, but it seems that no code uses it, so + // this should be okay. + public Iterator getInNeighbors(Node src) { + GraphNode src_c = (GraphNode) src; + // return Collections.unmodifiableCollection(src_c.getInNeighbors()); + return src_c.getInNeighborsCopy().iterator(); + } + + public int getInNeighborsSize(Node node) { + return ((GraphNode)node).inNeighbors.size(); + } + + //public int getNumNodes() { + // return nodes.size(); + //} + + public Iterator getOutNeighbors(Node src) { + GraphNode src_c = (GraphNode) src; + // return Collections.unmodifiableCollection(src_c.getOutNeighbors()); + return src_c.getOutNeighborsCopy().iterator(); + } + + public int getOutNeighborsSize(Node node) { + return ((GraphNode)node).outNeighbors.size(); + } + + public Node getRandom() { + return (Node) nodes.iterator().next(); + } + + public boolean hasNeighbor(Node src, Node dest) { + GraphNode src_c = (GraphNode) src; + GraphNode dest_c = (GraphNode) dest; + return src_c.hasOutNeighbor(dest_c); + } + + public boolean removeNeighbor(Node src, Node dest) { + GraphNode src_c = (GraphNode) src; + GraphNode dest_c = (GraphNode) dest; + return src_c.removeOutNeighbor(dest_c) ? dest_c.removeInNeighbor(src_c) : false; + } + + public boolean removeNode(Node n) { + boolean wasIn = n.inGraph; + removeConnectingEdges((GraphNode) n); + return wasIn; + } + + protected void removeConnectingEdges(GraphNode n) { + GraphNode g; + + for (Iterator iterator1 = n.getOutNeighborsCopy().iterator(); iterator1.hasNext(); removeNeighbor(n, g)) { + g = (GraphNode) iterator1.next(); + } + + for (Iterator iterator2 = n.getInNeighborsCopy().iterator(); iterator2.hasNext(); removeNeighbor(g, n)) { + g = (GraphNode) iterator2.next(); + } + + } + + public Object getNodeData(Node n) { + return ((GraphNode) n).data; + } + + public Object setNodeData(Node n, Object d) { + GraphNode gn = (GraphNode) n; + Object retval = gn.data; + gn.data = d; + return retval; + } + + //public Iterator iterator() { + // return nodes.iterator(); + //} + + public boolean isDirected() { + return true; + } +} diff --git a/Robust/src/Benchmarks/oooJava/D3/EdgeGraph.java b/Robust/src/Benchmarks/oooJava/D3/EdgeGraph.java new file mode 100755 index 00000000..add48bdc --- /dev/null +++ b/Robust/src/Benchmarks/oooJava/D3/EdgeGraph.java @@ -0,0 +1,28 @@ +public interface EdgeGraph extends Graph { + + public abstract Edge_d createEdge(Node node, Node node1, Object obj); + + public abstract Edge_d getEdge(Node node, Node node1); + + public abstract boolean removeEdge(Edge_d edge); + + public abstract boolean addEdge(Edge_d edge); + + public abstract boolean hasEdge(Edge_d edge); + + public abstract Node getSource(Edge_d edge); + + public abstract Node getDest(Edge_d edge); + + public abstract Iterator getOutEdges(Node node); + + public abstract Iterator getInEdges(Node node); + + public abstract Object getEdgeData(Edge_d edge); + + public abstract Object setEdgeData(Edge_d edge, Object obj); + + public abstract void discoverAllNodes( Node src ); + //public abstract void addNodeToAllNodesSet( Node n ); + //public abstract void removeNodeFromAllNodesSet( Node n ); +} diff --git a/Robust/src/Benchmarks/oooJava/D3/EdgeGraphNode.java b/Robust/src/Benchmarks/oooJava/D3/EdgeGraphNode.java new file mode 100755 index 00000000..5139aed1 --- /dev/null +++ b/Robust/src/Benchmarks/oooJava/D3/EdgeGraphNode.java @@ -0,0 +1,104 @@ +public class EdgeGraphNode extends Node { + protected HashMap inEdges; + protected HashMap outEdges; + protected Object data; + + EdgeGraphNode() { + super(); + } + + EdgeGraphNode(Object d) { + super(); + inEdges = new HashMap(); + outEdges = new HashMap(); + data = d; + } + + protected final boolean hasInNeighbor(EdgeGraphNode n) { + return inEdges.containsKey(n); + } + + protected boolean addInEdge(EdgeGraphNode n, GraphEdge e) { + if (hasInNeighbor(n)) { + return false; + } else { + inEdges.put(n, e); + return true; + } + } + + protected boolean removeInEdge(EdgeGraphNode n) { + if (!hasInNeighbor(n)) { + return false; + } else { + inEdges.remove(n); + return true; + } + } + + protected GraphEdge getInEdge(EdgeGraphNode n) { + return (GraphEdge) inEdges.get(n); + } + + protected Iterator getInEdges() { + return inEdges.iterator(1); + } + + protected final Iterator getInNeighbors() { + return inEdges.iterator(0); + } + + // TODO someone check this for performance. + protected final Iterator getInNeighborsCopy() { + LinkedList l = new LinkedList(); + HashMapIterator o = inEdges.iterator(0); + while (o.hasNext()) { + l.addLast(o.next()); + } + return l.iterator(); + } + + protected final boolean hasOutNeighbor(EdgeGraphNode n) { + return outEdges.containsKey(n); + } + + protected boolean addOutEdge(EdgeGraphNode n, GraphEdge e) { + if (hasOutNeighbor(n)) { + return false; + } else { + outEdges.put(n, e); + return true; + } + } + + protected boolean removeOutEdge(EdgeGraphNode n) { + if (!hasOutNeighbor(n)) { + return false; + } else { + outEdges.remove(n); + return true; + } + } + + protected GraphEdge getOutEdge(EdgeGraphNode n) { + return (GraphEdge) outEdges.get(n); + } + + protected Iterator getOutEdges() { + return outEdges.iterator(1); + } + + protected final Iterator getOutNeighbors() { + return outEdges.iterator(0); + } + + // TODO someone check this for performance. + protected final Iterator getOutNeighborsCopy() { + LinkedList l = new LinkedList(); + HashMapIterator o = outEdges.iterator(0); + while (o.hasNext()) { + l.addLast(o.next()); + } + return l.iterator(); + } + } \ No newline at end of file diff --git a/Robust/src/Benchmarks/oooJava/D3/Edge_d.java b/Robust/src/Benchmarks/oooJava/D3/Edge_d.java new file mode 100755 index 00000000..a421dbb9 --- /dev/null +++ b/Robust/src/Benchmarks/oooJava/D3/Edge_d.java @@ -0,0 +1,6 @@ +public class Edge_d { + //None of the program actually uses getData/setData so I use leave Edge as a + //wrapper interface. +// public abstract Object getData(); +// public abstract Object setData(Object obj); +} diff --git a/Robust/src/Benchmarks/oooJava/D3/Element.java b/Robust/src/Benchmarks/oooJava/D3/Element.java new file mode 100755 index 00000000..d449df16 --- /dev/null +++ b/Robust/src/Benchmarks/oooJava/D3/Element.java @@ -0,0 +1,237 @@ +public class Element { + private final boolean bObtuse; + private final boolean bBad; + private final Tuple obtuse; + private final Tuple coords[]; + private final ElementEdge edges[]; + private final int dim; + private final Tuple center; + private final double radius_squared; + private final double MINANGLE; + + public Element(Tuple a, Tuple b, Tuple c) { + MINANGLE = 30D; + dim = 3; + coords = new Tuple[3]; + coords[0] = a; + coords[1] = b; + coords[2] = c; + if (b.lessThan(a) || c.lessThan(a)) + if (b.lessThan(c)) { + coords[0] = b; + coords[1] = c; + coords[2] = a; + } else { + coords[0] = c; + coords[1] = a; + coords[2] = b; + } + edges = new ElementEdge[3]; + edges[0] = new ElementEdge(coords[0], coords[1]); + edges[1] = new ElementEdge(coords[1], coords[2]); + edges[2] = new ElementEdge(coords[2], coords[0]); + boolean l_bObtuse = false; + boolean l_bBad = false; + Tuple l_obtuse = null; + for (int i = 0; i < 3; i++) { + double angle = getAngle(i); + if (angle > 90.099999999999994D) { + l_bObtuse = true; + l_obtuse = new Tuple(coords[i]); + } else if (angle < 30D) + l_bBad = true; + } + + bBad = l_bBad; + bObtuse = l_bObtuse; + obtuse = l_obtuse; + Tuple x = b.subtract(a); + Tuple y = c.subtract(a); + double xlen = a.distance(b); + double ylen = a.distance(c); + double cosine = x.dotp(y) / (xlen * ylen); + double sine_sq = 1.0D - cosine * cosine; + double plen = ylen / xlen; + double s = plen * cosine; + double t = plen * sine_sq; + double wp = (plen - cosine) / (2D * t); + double wb = 0.5D - wp * s; + Tuple tmpval = a.scale(1.0D - wb - wp); + tmpval = tmpval.add(b.scale(wb)); + center = tmpval.add(c.scale(wp)); + radius_squared = center.distance_squared(a); + } + + public Element(Tuple a, Tuple b) { + dim = 2; + coords = new Tuple[2]; + coords[0] = a; + coords[1] = b; + if (b.lessThan(a)) { + coords[0] = b; + coords[1] = a; + } + edges = new ElementEdge[2]; + edges[0] = new ElementEdge(coords[0], coords[1]); + edges[1] = new ElementEdge(coords[1], coords[0]); + bBad = false; + bObtuse = false; + obtuse = null; + center = a.add(b).scale(0.5D); + radius_squared = center.distance_squared(a); + } + + + + public Tuple center() { + return center; + } + + public boolean inCircle(Tuple p) { + double ds = center.distance_squared(p); + return ds <= radius_squared; + } + + public double getAngle(int i) { + int j = i + 1; + if (j == dim) + j = 0; + int k = j + 1; + if (k == dim) + k = 0; + Tuple a = coords[i]; + Tuple b = coords[j]; + Tuple c = coords[k]; + return Tuple.angle(b, a, c); + } + + public ElementEdge getEdge(int i) { + return edges[i]; + } + + public Tuple getPoint(int i) { + return coords[i]; + } + + public Tuple getObtuse() { + return obtuse; + } + + public boolean isBad() { + return bBad; + } + + public int getDim() { + return dim; + } + + public int numEdges() { + return (dim + dim) - 3; + } + + public boolean isObtuse() { + return bObtuse; + } + + public ElementEdge getRelatedEdge(Element e) { + int edim = e.getDim(); + ElementEdge e_edge2 = null; + ElementEdge my_edge = edges[0]; + ElementEdge e_edge0 = e.edges[0]; + if (my_edge.equals(e_edge0)) + return my_edge; + ElementEdge e_edge1 = e.edges[1]; + if (my_edge.equals(e_edge1)) + return my_edge; + if (edim == 3) { + e_edge2 = e.edges[2]; + if (my_edge.equals(e_edge2)) + return my_edge; + } + my_edge = edges[1]; + if (my_edge.equals(e_edge0)) + return my_edge; + if (my_edge.equals(e_edge1)) + return my_edge; + if (edim == 3 && my_edge.equals(e_edge2)) + return my_edge; + if (dim == 3) { + my_edge = edges[2]; + if (my_edge.equals(e_edge0)) + return my_edge; + if (my_edge.equals(e_edge1)) + return my_edge; + if (edim == 3 && my_edge.equals(e_edge2)) + return my_edge; + } + return null; + } + + public Element getCopy() { + if (dim == 3) + return new Element(coords[0], coords[1], coords[2]); + else + return new Element(coords[0], coords[1]); + } + + public boolean lessThan(Element e) { + if (dim < e.getDim()) + return false; + if (dim > e.getDim()) + return true; + for (int i = 0; i < dim; i++) { + if (coords[i].lessThan(e.coords[i])) + return true; + if (coords[i].greaterThan(e.coords[i])) + return false; + } + + return false; + } + + public boolean isRelated(Element e) { + int edim = e.getDim(); + ElementEdge e_edge2 = null; + ElementEdge my_edge = edges[0]; + ElementEdge e_edge0 = e.edges[0]; + if (my_edge.equals(e_edge0)) + return true; + ElementEdge e_edge1 = e.edges[1]; + if (my_edge.equals(e_edge1)) + return true; + if (edim == 3) { + e_edge2 = e.edges[2]; + if (my_edge.equals(e_edge2)) + return true; + } + my_edge = edges[1]; + if (my_edge.equals(e_edge0)) + return true; + if (my_edge.equals(e_edge1)) + return true; + if (edim == 3 && my_edge.equals(e_edge2)) + return true; + if (dim == 3) { + my_edge = edges[2]; + if (my_edge.equals(e_edge0)) + return true; + if (my_edge.equals(e_edge1)) + return true; + if (edim == 3 && my_edge.equals(e_edge2)) + return true; + } + return false; + } + + public String toString() { + String ret = "["; + for (int i = 0; i < dim; i++) { + ret += coords[i].toString(); + if (i != (dim - 1)) { + ret += ", "; + } + } + ret += "]"; + return ret; + } +} diff --git a/Robust/src/Benchmarks/oooJava/D3/ElementEdge.java b/Robust/src/Benchmarks/oooJava/D3/ElementEdge.java new file mode 100755 index 00000000..9806ffc3 --- /dev/null +++ b/Robust/src/Benchmarks/oooJava/D3/ElementEdge.java @@ -0,0 +1,69 @@ +public class ElementEdge { + private final Tuple p1; + private final Tuple p2; + private final int hashvalue; + + public ElementEdge() { + p1 = null; + p2 = null; + hashvalue = 1; + } + + public ElementEdge(Tuple a, Tuple b) { + if (a.lessThan(b)) { + p1 = a; + p2 = b; + } else { + p1 = b; + p2 = a; + } + int tmphashval = 17; + tmphashval = 37 * tmphashval + p1.hashCode(); + tmphashval = 37 * tmphashval + p2.hashCode(); + hashvalue = tmphashval; + } + + public ElementEdge(ElementEdge rhs) { + p1 = rhs.p1; + p2 = rhs.p2; + hashvalue = rhs.hashvalue; + } + + public boolean equals(Object obj) { + if (!(obj instanceof ElementEdge)) + return false; + ElementEdge edge = (ElementEdge) obj; + return p1.equals(edge.p1) && p2.equals(edge.p2); + } + + public int hashCode() { + return hashvalue; + } + + public boolean notEqual(ElementEdge rhs) { + return !equals(rhs); + } + + public boolean lessThan(ElementEdge rhs) { + return p1.lessThan(rhs.p1) || p1.equals(rhs.p1) && p2.lessThan(rhs.p2); + } + + public boolean greaterThan(ElementEdge rhs) { + return p1.greaterThan(rhs.p1) || p1.equals(rhs.p1) && p2.greaterThan(rhs.p2); + } + + public Tuple getPoint(int i) { + if (i == 0) + return p1; + if (i == 1) { + return p2; + } else { + System.exit(-1); + return null; + } + } + + public String toString() { + return "<"+p1.toString()+(", ")+p2.toString()+">"; + } +} diff --git a/Robust/src/Benchmarks/oooJava/D3/Graph.java b/Robust/src/Benchmarks/oooJava/D3/Graph.java new file mode 100755 index 00000000..96dc0fff --- /dev/null +++ b/Robust/src/Benchmarks/oooJava/D3/Graph.java @@ -0,0 +1,36 @@ +public interface Graph { + + public abstract Node createNode(Object obj); + + public abstract boolean addNode(Node node); + + public abstract boolean removeNode(Node node); + + public abstract boolean containsNode(Node node); + + public abstract Node getRandom(); + + public abstract boolean addNeighbor(Node node, Node node1); + + public abstract boolean removeNeighbor(Node node, Node node1); + + public abstract boolean hasNeighbor(Node node, Node node1); + + public abstract Iterator getInNeighbors(Node node); + + public abstract int getInNeighborsSize(Node node); + + public abstract Iterator getOutNeighbors(Node node); + + public abstract int getOutNeighborsSize(Node node); + + public abstract int getNumNodes(); + + public abstract Object getNodeData(Node node); + + public abstract Object setNodeData(Node node, Object obj); + + public abstract boolean isDirected(); + + public abstract Iterator iterator(); +} diff --git a/Robust/src/Benchmarks/oooJava/D3/GraphEdge.java b/Robust/src/Benchmarks/oooJava/D3/GraphEdge.java new file mode 100755 index 00000000..c17e8c3c --- /dev/null +++ b/Robust/src/Benchmarks/oooJava/D3/GraphEdge.java @@ -0,0 +1,28 @@ +public class GraphEdge extends Edge_d { + protected EdgeGraphNode src; + protected EdgeGraphNode dest; + protected Object d; + + public GraphEdge(Object d) { + super(); + this.d = d; + } + + public GraphEdge(EdgeGraphNode src, EdgeGraphNode dest, Object d) { + this(d); + this.src = src; + this.dest = dest; + } + + protected final EdgeGraphNode getOpposite(EdgeGraphNode n) { + return n != src ? src : dest; + } + + protected final EdgeGraphNode getSrc() { + return src; + } + + protected final EdgeGraphNode getDest() { + return dest; + } +} \ No newline at end of file diff --git a/Robust/src/Benchmarks/oooJava/D3/GraphNode.java b/Robust/src/Benchmarks/oooJava/D3/GraphNode.java new file mode 100755 index 00000000..755d4534 --- /dev/null +++ b/Robust/src/Benchmarks/oooJava/D3/GraphNode.java @@ -0,0 +1,75 @@ +public class GraphNode extends Node { + protected Object data; + // protected List inNeighbors; + // protected List outNeighbors; + protected Vector inNeighbors; + protected Vector outNeighbors; + + protected GraphNode() { + super(); + } + + public GraphNode(Object n) { + super(); + data = n; + inNeighbors = new Vector(); + outNeighbors = new Vector(); + } + +// public Object getData() { +// return getNodeData(this); +// } +// +// public Object setData(Object n) { +// return setNodeData(this, n); +// } + + public final boolean addInNeighbor(GraphNode n) { + if (inNeighbors.contains(n)) { + return false; + } else { + inNeighbors.addElement(n); + return true; + } + } + + public final boolean removeInNeighbor(GraphNode n) { + return inNeighbors.remove(n); + } + + public final boolean hasInNeighbor(GraphNode n) { + return inNeighbors.contains(n); + } + + public final Vector getInNeighbors() { + return inNeighbors; + } + + public final Vector getInNeighborsCopy() { + return inNeighbors.clone(); + } + + public final boolean addOutNeighbor(GraphNode n) { + if (outNeighbors.contains(n)) { + return false; + } else { + outNeighbors.addElement(n); + return true; + } + } + + public final boolean removeOutNeighbor(GraphNode n) { + return outNeighbors.remove(n); + } + public final boolean hasOutNeighbor(GraphNode n) { + return outNeighbors.contains(n); + } + + public final Vector getOutNeighbors() { + return outNeighbors; + } + + public final Vector getOutNeighborsCopy() { + return outNeighbors.clone(); + } +} \ No newline at end of file diff --git a/Robust/src/Benchmarks/oooJava/D3/Mesh.java b/Robust/src/Benchmarks/oooJava/D3/Mesh.java new file mode 100755 index 00000000..e4a97490 --- /dev/null +++ b/Robust/src/Benchmarks/oooJava/D3/Mesh.java @@ -0,0 +1,160 @@ +public class Mesh { + + protected HashMap edge_map; + protected Node aNode; + + + public Mesh() { + edge_map = new HashMap(); + aNode = null; + } + + public HashSet getBad(UndirectedEdgeGraph mesh) { + HashSet ret = new HashSet(); + for (Iterator iterator = mesh.iterator(); iterator.hasNext();) { + Node node = (Node) iterator.next(); + Element element = (Element) mesh.getNodeData(node); + if (element.isBad()) + ret.add(node); + } + + return ret; + } + + private FileInputStream getScanner(String filename) { + return new FileInputStream(filename); + } + + private Tuple[] readNodes(String filename) { + FileInputStream scanner = getScanner(filename + ".node"); + StringTokenizer st = new StringTokenizer(scanner.readLine()); + + int ntups = Integer.parseInt(st.nextToken()); + Tuple tuples[] = new Tuple[ntups]; + for (int i = 0; i < ntups; i++) { + st = new StringTokenizer(scanner.readLine()); + int index = Integer.parseInt(st.nextToken()); + double x = Double.parseDouble(st.nextToken()); + double y = Double.parseDouble(st.nextToken()); + // we don't parse the z axis + tuples[index] = new Tuple(x, y, 0.0D); + } + return tuples; + } + + private void readElements(UndirectedEdgeGraph mesh, String filename, Tuple tuples[]) { + FileInputStream scanner =getScanner(filename + ".ele"); + StringTokenizer st = new StringTokenizer(scanner.readLine()); + int nels = Integer.parseInt(st.nextToken()); + Element elements[] = new Element[nels]; + for (int i = 0; i < nels; i++) { + st = new StringTokenizer(scanner.readLine()); + int index = Integer.parseInt(st.nextToken()); + int n1 = Integer.parseInt(st.nextToken()); + int n2 = Integer.parseInt(st.nextToken()); + int n3 = Integer.parseInt(st.nextToken()); + elements[index] = new Element(tuples[n1], tuples[n2], tuples[n3]); + addElement(mesh, elements[index]); + } + } + + private void readPoly(UndirectedEdgeGraph mesh, String filename, Tuple tuples[]) { + FileInputStream scanner = getScanner(filename + ".poly"); + StringTokenizer st = new StringTokenizer(scanner.readLine()); + // discard line 1 + st = new StringTokenizer(scanner.readLine()); + int nsegs = Integer.parseInt(st.nextToken()); + + Element segments[] = new Element[nsegs]; + for (int i = 0; i < nsegs; i++) { + st = new StringTokenizer(scanner.readLine()); + int index = Integer.parseInt(st.nextToken()); + int n1 = Integer.parseInt(st.nextToken()); + int n2 = Integer.parseInt(st.nextToken()); + // don't parse z value + segments[index] = new Element(tuples[n1], tuples[n2]); + addElement(mesh, segments[index]); + } + + } + + public void read(UndirectedEdgeGraph mesh, String basename) { + Tuple tuples[] = readNodes(basename); + readElements(mesh, basename, tuples); + readPoly(mesh, basename, tuples); + + // after building the initial graph, discover all the nodes + mesh.discoverAllNodes( aNode ); + } + + protected Node addElement(UndirectedEdgeGraph mesh, Element element) { + Node node = mesh.createNode(element); + mesh.addNode(node); + //mesh.addNodeToAllNodesSet( node ); + for (int i = 0; i < element.numEdges(); i++) { + ElementEdge edge = element.getEdge(i); + if (!edge_map.containsKey(edge)) { + edge_map.put(edge, node); + } else { + Edge_d new_edge = mesh.createEdge(node, (Node) edge_map.get(edge), edge); + mesh.addEdge(new_edge); + edge_map.remove(edge); + } + } + + // just remember one node to use for discovering all nodes + // in the graph + aNode = node; + + return node; + } + + public boolean verify(UndirectedEdgeGraph mesh) { + + + for (Iterator iterator = mesh.iterator(); iterator.hasNext();) { + Node node = (Node) iterator.next(); + Element element = (Element) mesh.getNodeData(node); + if (element.getDim() == 2) { + if (mesh.getOutNeighborsSize(node) != 1) { + System.out.println("-> Segment " + element + " has " + mesh.getOutNeighborsSize(node) + " relation(s)"); + return false; + } + } else if (element.getDim() == 3) { + if (mesh.getOutNeighborsSize(node) != 3) { + System.out.println("-> Triangle " + element + " has " + mesh.getOutNeighborsSize(node) + " relation(s)"); + return false; + } + } else { + System.out.println("-> Figures with " + element.getDim() + " edges"); + return false; + } + + + } + + Node start = mesh.getRandom(); + Stack remaining = new Stack(); + // LinkedList remaining = new LinkedList(); + HashSet found = new HashSet(); + remaining.push(start); + while (!remaining.isEmpty()) { + Node node = (Node) remaining.pop(); + if (!found.contains(node)) { + found.add(node); + Node neighbor; + + + for (Iterator iterator1 = mesh.getOutNeighbors(node); iterator1.hasNext(); remaining.push(neighbor)) + neighbor = (Node) iterator1.next(); + + } + } + if (found.size() != mesh.getNumNodes()) { + System.out.println("Not all elements are reachable"); + return false; + } else { + return true; + } + } +} diff --git a/Robust/src/Benchmarks/oooJava/D3/Node.java b/Robust/src/Benchmarks/oooJava/D3/Node.java new file mode 100755 index 00000000..68ac2f06 --- /dev/null +++ b/Robust/src/Benchmarks/oooJava/D3/Node.java @@ -0,0 +1,12 @@ +public class Node { + public boolean inGraph; + + public Node() { + inGraph = false; + } + + //None of the program actually uses getData/setData so I use leave Node as a + //wrapper interface. +// public abstract Object getData(); +// public abstract Object setData(Object obj); +} diff --git a/Robust/src/Benchmarks/oooJava/D3/Pair.java b/Robust/src/Benchmarks/oooJava/D3/Pair.java new file mode 100755 index 00000000..6b3ea4cd --- /dev/null +++ b/Robust/src/Benchmarks/oooJava/D3/Pair.java @@ -0,0 +1,47 @@ +public class Pair { + private Object first; + private Object second; + + public Pair(Object first, Object second) { + this.first = first; + this.second = second; + } + + public Object getFirst() { + return first; + } + + public Object getSecond() { + return second; + } + + public void setFirst(Object first) { + this.first = first; + } + + public void setSecond(Object second) { + this.second = second; + } + + public String toString() { + return "(" + first + ", " + second + ")"; + } + + private static boolean equals(Object x, Object y) { + return x == null && y == null || x != null && x.equals(y); + } + + public boolean equals(Object other) { + return (other instanceof Pair) && equals(first, ((Pair) other).first) + && equals(second, ((Pair) other).second); + } + + public int hashCode() { + if (first == null) + return second != null ? second.hashCode() + 1 : 0; + if (second == null) + return first.hashCode() + 2; + else + return first.hashCode() * 17 + second.hashCode(); + } +} diff --git a/Robust/src/Benchmarks/oooJava/D3/SerialDelaunayRefinement.java b/Robust/src/Benchmarks/oooJava/D3/SerialDelaunayRefinement.java new file mode 100755 index 00000000..1c81d569 --- /dev/null +++ b/Robust/src/Benchmarks/oooJava/D3/SerialDelaunayRefinement.java @@ -0,0 +1,277 @@ +/* +Lonestar Benchmark Suite for irregular applications that exhibit +amorphous data-parallelism. + +Center for Grid and Distributed Computing +The University of Texas at Austin + +Copyright (C) 2007, 2008, 2009 The University of Texas at Austin + +Licensed under the Eclipse Public License, Version 1.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.eclipse.org/legal/epl-v10.html + +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. + +File: UndirectedEdgeGraph.java + +*/ + +public class SerialDelaunayRefinement { + public boolean isFirstRun; + public SerialDelaunayRefinement() { + isFirstRun = true; + } + + public static void main(String args[]) { + SerialDelaunayRefinement sdr = new SerialDelaunayRefinement(); + sdr.runMain(args); + } + + public void runMain(String args[]) { + long runtime = 0; + //Numbers below are Long.Max_Value + long lasttime = 0x7fffffffffffffffL; + long mintime = 0x7fffffffffffffffL; + + for (long run = 0; ((run < 3) || Math.abs(lasttime - runtime) * 64 > Math.min(lasttime, runtime)) && run < 7; run++) { + runtime = run(args); + if (runtime < mintime) { + mintime = runtime; + } + System.out.println( "Post-run garbage collection started..." ); + System.gc(); + System.out.println( "done gc" ); + } + + System.out.println("minimum runtime: " + mintime + " ms"); + System.out.println(""); + } + + + public long run(String args[]) { + if (isFirstRun) { + System.out.println(); + System.out.println("Lonestar Benchmark Suite v2.1"); + System.out.println("Copyright (C) 2007, 2008, 2009 The University of Texas at Austin"); + System.out.println("http://iss.ices.utexas.edu/lonestar/"); + System.out.println(); + System.out.println("application: Delaunay Mesh Refinement (serial version)"); + System.out.println("Refines a Delaunay triangulation mesh such that no angle"); + System.out.println("in the mesh is less than 30 degrees"); + System.out.println("http://iss.ices.utexas.edu/lonestar/delaunayrefinement.html"); + System.out.println(); + } + if (args.length < 2) { + System.out.println("Arguments: [verify]"); + System.exit(-1); + } + + UndirectedEdgeGraph mesh = new UndirectedEdgeGraph(); + + Mesh m = new Mesh(); + m.read(mesh, args[0]); + + int numWorkers = Integer.parseInt( args[1] ); + + Stack worklist = new Stack(); + + HashMapIterator it = m.getBad(mesh).iterator(); + while (it.hasNext()) { + worklist.push(it.next()); + } + + if (isFirstRun) { + System.out.println("configuration: " + + mesh.getNumNodes() + " total triangles, " + + worklist.size() + " bad triangles"); + System.out.println(); + } + + System.out.println( "Post-config garbage collection started..." ); + System.gc(); + System.out.println( "done gc" ); + + + long startTime = System.currentTimeMillis(); + + + sese workLoop { + + Node [] nodesForBadTris = new Node [numWorkers]; + Cavity[] cavities = new Cavity[numWorkers]; + Cavity lastAppliedCavity = null; + + while (!worklist.isEmpty()) { + + // Phase 1, grab enough work from list for + // each worker in the parent + for(int i=0;i 2) { + + Node aNode = (Node)lastAppliedCavity.getPost().getNodes().iterator().next(); + mesh.discoverAllNodes( aNode ); + + verify(mesh); + } + isFirstRun = false; + return time; + } + + + public void verify(UndirectedEdgeGraph result) { + //Put in cuz of static issues. + Mesh m = new Mesh(); + if (!m.verify(result)) { + System.out.println("Refinement Failed."); + System.exit(-1); + } + + int size = m.getBad(result).size(); + if (size != 0) { + System.out.println("refinement failed\nstill have "+size+" bad triangles left.\n"); + System.exit(-1); + } else { + System.out.println("OK"); + return; + } + } +} diff --git a/Robust/src/Benchmarks/oooJava/D3/Stack.java b/Robust/src/Benchmarks/oooJava/D3/Stack.java new file mode 100755 index 00000000..751dcb18 --- /dev/null +++ b/Robust/src/Benchmarks/oooJava/D3/Stack.java @@ -0,0 +1,161 @@ +/* Stack.java - Class that provides a Last In First Out (LIFO) + datatype, known more commonly as a Stack + Copyright (C) 1998, 1999, 2001, 2004, 2005 + Free Software Foundation, Inc. + +This file is part of GNU Classpath. + +GNU Classpath is free software; you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 2, or (at your option) +any later version. + +GNU Classpath 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 +General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GNU Classpath; see the file COPYING. If not, write to the +Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA +02110-1301 USA. + +Linking this library statically or dynamically with other modules is +making a combined work based on this library. Thus, the terms and +conditions of the GNU General Public License cover the whole +combination. + +As a special exception, the copyright holders of this library give you +permission to link this library with independent modules to produce an +executable, regardless of the license terms of these independent +modules, and to copy and distribute the resulting executable under +terms of your choice, provided that you also meet, for each linked +independent module, the terms and conditions of the license of that +module. An independent module is a module which is not derived from +or based on this library. If you modify this library, you may extend +this exception to your version of the library, but you are not +obligated to do so. If you do not wish to do so, delete this +exception statement from your version. */ + + +package java.util; + +/* Written using "Java Class Libraries", 2nd edition, ISBN 0-201-31002-3 + * "The Java Language Specification", ISBN 0-201-63451-1 + * plus online API docs for JDK 1.2 beta from http://www.javasoft.com. + * Status: Believed complete and correct + +/** + * Stack provides a Last In First Out (LIFO) data type, commonly known + * as a Stack. Stack itself extends Vector and provides the additional + * methods for stack manipulation (push, pop, peek). You can also seek for + * the 1-based position of an element on the stack. + * + * @author Warren Levy (warrenl@cygnus.com) + * @author Eric Blake (ebb9@email.byu.edu) + * @see List + * @see AbstractList + * @see LinkedList + * @since 1.0 + * @status updated to 1.4 + */ +public class Stack/**/ extends Vector/**/ +{ + // We could use Vector methods internally for the following methods, + // but have used Vector fields directly for efficiency (i.e. this + // often reduces out duplicate bounds checking). + + /** + * Compatible with JDK 1.0+. + */ + private static final long serialVersionUID = 1224463164541339165L; + + /** + * This constructor creates a new Stack, initially empty + */ + public Stack() + { + super(); + } + + /** + * Pushes an Object onto the top of the stack. This method is effectively + * the same as addElement(item). + * + * @param item the Object to push onto the stack + * @return the Object pushed onto the stack + * @see Vector#addElement(Object) + */ + public Object push(Object item) + { + // When growing the Stack, use the Vector routines in case more + // memory is needed. + // Note: spec indicates that this method *always* returns obj passed in! + + addElement(item); + return item; + } + + /** + * Pops an item from the stack and returns it. The item popped is + * removed from the Stack. + * + * @return the Object popped from the stack + * @throws EmptyStackException if the stack is empty + */ + //@SuppressWarnings("unchecked") + public synchronized Object pop() + { + if (size == 0) + throw new /*EmptyStack*/Exception("EmptyStackException"); + + Object obj = array[--size]; + + // Set topmost element to null to assist the gc in cleanup. + array[size] = null; + return obj; + } + + /** + * Returns the top Object on the stack without removing it. + * + * @return the top Object on the stack + * @throws EmptyStackException if the stack is empty + */ + //@SuppressWarnings("unchecked") + public synchronized Object peek() + { + if (size == 0) + throw new /*EmptyStack*/Exception("EmptyStackException"); + + return array[size - 1]; + } + + /** + * Tests if the stack is empty. + * + * @return true if the stack contains no items, false otherwise + */ + public synchronized boolean empty() + { + return size == 0; + } + + /** + * Returns the position of an Object on the stack, with the top + * most Object being at position 1, and each Object deeper in the + * stack at depth + 1. + * + * @param o The object to search for + * @return The 1 based depth of the Object, or -1 if the Object + * is not on the stack + */ + public synchronized int search(Object o) + { + int i = size; + while (--i >= 0) + if (o.equals(array[i])) + return size - i; + return -1; + } +} diff --git a/Robust/src/Benchmarks/oooJava/D3/Subgraph.java b/Robust/src/Benchmarks/oooJava/D3/Subgraph.java new file mode 100755 index 00000000..92ba1b5b --- /dev/null +++ b/Robust/src/Benchmarks/oooJava/D3/Subgraph.java @@ -0,0 +1,84 @@ +public class Subgraph { + + private final LinkedList nodes; + private final LinkedList border; + private final LinkedList edges; + + + public Subgraph() { + nodes = new LinkedList(); + border = new LinkedList(); + edges = new LinkedList(); + } + + public boolean existsNode(Node n) { + return nodes.contains(n); + } + + public boolean existsBorder(Node b) { + return border.contains(b); + } + + public boolean existsEdge(Edge_d e) { + return edges.contains(e); + } + + public void addNode(Node n) { + nodes.addLast(n); + } + + public void addBorder(Node b) { + border.addLast(b); + } + + public void addEdge(Edge_d e) { + edges.addLast(e); + } + + public LinkedList getNodes() { + return nodes; + } + + public LinkedList getBorder() { + return border; + } + + public LinkedList getEdges() { + return edges; + } + + public void reset() { + nodes.clear(); + border.clear(); + edges.clear(); + } + + + public boolean allNodesAndBorderStillInCompleteGraph() { + for( Iterator i = nodes.iterator(); i.hasNext(); ) { + Node node = (Node) i.next(); + if( !node.inGraph ) { + return false; + } + } + for( Iterator i = border.iterator(); i.hasNext(); ) { + Node node = (Node) i.next(); + if( !node.inGraph ) { + return false; + } + } + return true; + } + + public HashSet newBad(UndirectedEdgeGraph mesh) { + HashSet ret = new HashSet(); + for (Iterator iter = nodes.iterator(); iter.hasNext();) { + Node node = (Node) iter.next(); + Element element = (Element) mesh.getNodeData(node); + if (element.isBad()) + ret.add(node); + } + + return ret; + } +} diff --git a/Robust/src/Benchmarks/oooJava/D3/Tuple.java b/Robust/src/Benchmarks/oooJava/D3/Tuple.java new file mode 100755 index 00000000..5ab0723a --- /dev/null +++ b/Robust/src/Benchmarks/oooJava/D3/Tuple.java @@ -0,0 +1,154 @@ +public class Tuple { + + private final double coords[]; + private final int hashvalue; + + + public Tuple(double a, double b, double c) { + coords = new double[3]; + coords[0] = a; + coords[1] = b; + coords[2] = c; + int tmphashvalue = 17; + long tmp = Double.doubleToLongBits(coords[0]); + tmphashvalue = 37 * tmphashvalue + (int) (tmp ^ tmp >>> 32); + tmp = Double.doubleToLongBits(coords[1]); + tmphashvalue = 37 * tmphashvalue + (int) (tmp ^ tmp >>> 32); + tmp = Double.doubleToLongBits(coords[2]); + tmphashvalue = 37 * tmphashvalue + (int) (tmp ^ tmp >>> 32); + hashvalue = tmphashvalue; + } + + public Tuple(Tuple rhs) { + coords = new double[3]; + coords[0] = rhs.coords[0]; + coords[1] = rhs.coords[1]; + coords[2] = rhs.coords[2]; + hashvalue = rhs.hashvalue; + } + + public Tuple() { + coords = new double[3]; + hashvalue = 1; + } + + public double[] getCoords() { + return coords; + } + + public boolean equals(Object obj) { + if (!(obj instanceof Tuple)) + return false; + Tuple t = (Tuple) obj; + double rhs_coords[] = t.getCoords(); + return coords[0] == rhs_coords[0] && coords[1] == rhs_coords[1] && coords[2] == rhs_coords[2]; + } + + public int hashCode() { + return hashvalue; + } + + public boolean notEquals(Tuple rhs) { + return !equals(rhs); + } + + public boolean lessThan(Tuple rhs) { + double rhs_coords[] = rhs.getCoords(); + if (coords[0] < rhs_coords[0]) + return true; + if (coords[0] > rhs_coords[0]) + return false; + if (coords[1] < rhs_coords[1]) + return true; + if (coords[1] > rhs_coords[1]) + return false; + return coords[2] < rhs_coords[2]; + } + + public boolean greaterThan(Tuple rhs) { + double rhs_coords[] = rhs.getCoords(); + if (coords[0] > rhs_coords[0]) + return true; + if (coords[0] < rhs_coords[0]) + return false; + if (coords[1] > rhs_coords[1]) + return true; + if (coords[1] < rhs_coords[1]) + return false; + return coords[2] > rhs_coords[2]; + } + + public Tuple add(Tuple rhs) { + double rhs_coords[] = rhs.getCoords(); + return new Tuple(coords[0] + rhs_coords[0], coords[1] + rhs_coords[1], coords[2] + + rhs_coords[2]); + } + + public Tuple subtract(Tuple rhs) { + double rhs_coords[] = rhs.getCoords(); + return new Tuple(coords[0] - rhs_coords[0], coords[1] - rhs_coords[1], coords[2] + - rhs_coords[2]); + } + + public double dotp(Tuple rhs) { + double rhs_coords[] = rhs.getCoords(); + return coords[0] * rhs_coords[0] + coords[1] * rhs_coords[1] + coords[2] * rhs_coords[2]; + } + + public Tuple scale(double s) { + return new Tuple(s * coords[0], s * coords[1], s * coords[2]); + } + + public int cmp(Tuple x) { + if (equals(x)) + return 0; + return !greaterThan(x) ? -1 : 1; + } + + public double distance(Tuple rhs) { + return Math.sqrt(distance_squared(rhs)); + } + + public double distance_squared(Tuple rhs) { + double rhs_coords[] = rhs.getCoords(); + double x = coords[0] - rhs_coords[0]; + double y = coords[1] - rhs_coords[1]; + double z = coords[2] - rhs_coords[2]; + return x * x + y * y + z * z; + } + + public double angle(Tuple a, Tuple c) { + Tuple va = a.subtract(this); + Tuple vc = c.subtract(this); + double d = va.dotp(vc) / Math.sqrt(distance_squared(a) * distance_squared(c)); + return 57.295779513082323D * Math.acos(d); + } + + public String toString() { + //return new String("(" + coords[0] + ", " + coords[1] + ", " + coords[2] + ")"); + + String x = ""+coords[0]; + x = x.substring( 0, 4 ); + + String y = ""+coords[1]; + y = y.substring( 0, 4 ); + + return new String("("+x+", "+y+")"); + } + + public static int cmp(Tuple a, Tuple b) { + return a.cmp(b); + } + + public static double distance(Tuple a, Tuple b) { + return a.distance(b); + } + + public static double angle(Tuple a, Tuple b, Tuple c) { + return b.angle(a, c); + } + + public double get(int i) { + return coords[i]; + } +} diff --git a/Robust/src/Benchmarks/oooJava/D3/UndirectedEdgeGraph.java b/Robust/src/Benchmarks/oooJava/D3/UndirectedEdgeGraph.java new file mode 100755 index 00000000..9ed3aabb --- /dev/null +++ b/Robust/src/Benchmarks/oooJava/D3/UndirectedEdgeGraph.java @@ -0,0 +1,22 @@ +public class UndirectedEdgeGraph extends DirectedEdgeGraph { + public UndirectedEdgeGraph() { + super(); + } + + public Edge_d createEdge(Node src, Node dest, Object e) { + UndirectedEdgeGraphNode gsrc = (UndirectedEdgeGraphNode) src; + UndirectedEdgeGraphNode gdest = (UndirectedEdgeGraphNode) dest; + if (gsrc.compareTo(gdest) > 0) + return new GraphEdge(gsrc, gdest, e); + else + return new GraphEdge(gdest, gsrc, e); + } + + public UndirectedEdgeGraphNode createNode(Object n) { + return new UndirectedEdgeGraphNode(n); + } + + public boolean isDirected() { + return false; + } +} diff --git a/Robust/src/Benchmarks/oooJava/D3/UndirectedEdgeGraphNode.java b/Robust/src/Benchmarks/oooJava/D3/UndirectedEdgeGraphNode.java new file mode 100755 index 00000000..1709a2a2 --- /dev/null +++ b/Robust/src/Benchmarks/oooJava/D3/UndirectedEdgeGraphNode.java @@ -0,0 +1,16 @@ +public class UndirectedEdgeGraphNode extends EdgeGraphNode { + + public int compareTo(UndirectedEdgeGraphNode n) { + return n.hashCode() - hashCode(); + } + + public int compareTo(Object obj) { + return compareTo((UndirectedEdgeGraphNode) obj); + } + + UndirectedEdgeGraphNode(Object d) { + data = d; + inEdges = new HashMap(); + outEdges = inEdges; + } + } \ No newline at end of file diff --git a/Robust/src/Benchmarks/oooJava/D3/makefile b/Robust/src/Benchmarks/oooJava/D3/makefile new file mode 100755 index 00000000..7c9f2e3a --- /dev/null +++ b/Robust/src/Benchmarks/oooJava/D3/makefile @@ -0,0 +1,8 @@ +PROGRAM=SerialDelaunayRefinement + +SOURCE_FILES=SerialDelaunayRefinement.java + +NUM_OOO_WORKERS=24 +NUM_RCR_WORKERS=7 + +include ../master-makefile -- 2.34.1