From fb910cc2695dc899a41d49b65c22d4a08ea33ed7 Mon Sep 17 00:00:00 2001 From: stephey Date: Tue, 29 Mar 2011 02:38:47 +0000 Subject: [PATCH] These are the Delaunay Refinement files with the generics removed. It was a bit tedious, so I'm uploading now so we'd have a restart point if something goes wrong. --- .../oooJava/DelaunayRefinement/Cavity.java | 144 ++++++++ .../DelaunayRefinement/DirectedEdgeGraph.java | 293 +++++++++++++++++ .../DelaunayRefinement/DirectedGraph.java | 177 ++++++++++ .../oooJava/DelaunayRefinement/Edge.java | 7 + .../oooJava/DelaunayRefinement/EdgeGraph.java | 27 ++ .../oooJava/DelaunayRefinement/Element.java | 308 ++++++++++++++++++ .../DelaunayRefinement/ElementEdge.java | 71 ++++ .../oooJava/DelaunayRefinement/Graph.java | 36 ++ .../oooJava/DelaunayRefinement/Mesh.java | 159 +++++++++ .../oooJava/DelaunayRefinement/Node.java | 7 + .../oooJava/DelaunayRefinement/Pair.java | 48 +++ .../SerialDelaunayrefinement.java | 103 ++++++ .../oooJava/DelaunayRefinement/Sets.java | 12 + .../oooJava/DelaunayRefinement/Subgraph.java | 65 ++++ .../oooJava/DelaunayRefinement/Time.java | 66 ++++ .../oooJava/DelaunayRefinement/Tuple.java | 144 ++++++++ .../UndirectedEdgeGraph.java | 50 +++ 17 files changed, 1717 insertions(+) create mode 100644 Robust/src/Benchmarks/oooJava/DelaunayRefinement/Cavity.java create mode 100644 Robust/src/Benchmarks/oooJava/DelaunayRefinement/DirectedEdgeGraph.java create mode 100644 Robust/src/Benchmarks/oooJava/DelaunayRefinement/DirectedGraph.java create mode 100644 Robust/src/Benchmarks/oooJava/DelaunayRefinement/Edge.java create mode 100644 Robust/src/Benchmarks/oooJava/DelaunayRefinement/EdgeGraph.java create mode 100644 Robust/src/Benchmarks/oooJava/DelaunayRefinement/Element.java create mode 100644 Robust/src/Benchmarks/oooJava/DelaunayRefinement/ElementEdge.java create mode 100644 Robust/src/Benchmarks/oooJava/DelaunayRefinement/Graph.java create mode 100644 Robust/src/Benchmarks/oooJava/DelaunayRefinement/Mesh.java create mode 100644 Robust/src/Benchmarks/oooJava/DelaunayRefinement/Node.java create mode 100644 Robust/src/Benchmarks/oooJava/DelaunayRefinement/Pair.java create mode 100644 Robust/src/Benchmarks/oooJava/DelaunayRefinement/SerialDelaunayrefinement.java create mode 100644 Robust/src/Benchmarks/oooJava/DelaunayRefinement/Sets.java create mode 100644 Robust/src/Benchmarks/oooJava/DelaunayRefinement/Subgraph.java create mode 100644 Robust/src/Benchmarks/oooJava/DelaunayRefinement/Time.java create mode 100644 Robust/src/Benchmarks/oooJava/DelaunayRefinement/Tuple.java create mode 100644 Robust/src/Benchmarks/oooJava/DelaunayRefinement/UndirectedEdgeGraph.java diff --git a/Robust/src/Benchmarks/oooJava/DelaunayRefinement/Cavity.java b/Robust/src/Benchmarks/oooJava/DelaunayRefinement/Cavity.java new file mode 100644 index 00000000..4fb29fa4 --- /dev/null +++ b/Robust/src/Benchmarks/oooJava/DelaunayRefinement/Cavity.java @@ -0,0 +1,144 @@ +import java.util.*; + +public class Cavity { + + public Cavity(EdgeGraph mesh) { + center = null; + graph = mesh; + } + + 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.clear(); + centerNode = node; + for(centerElement = (Element)graph.getNodeData(centerNode); graph.containsNode(centerNode) && centerElement.isObtuse();) { + Edge oppositeEdge = getOpposite(centerNode); + if(graph.getSource(oppositeEdge) == centerNode) + centerNode = graph.getDest(oppositeEdge); + else + centerNode = graph.getSource(oppositeEdge); + centerElement = (Element)graph.getNodeData(centerNode); + if(centerNode == null) + System.exit(-1); + } + + center = centerElement.center(); + dim = centerElement.getDim(); + pre.addNode(centerNode); + frontier.add(centerNode); + } + + private Edge getOpposite(Node node) { + Element element = (Element)graph.getNodeData(node); + Collection neighbors = graph.getOutNeighbors(node); + if(neighbors.size() != 3) + throw new Error(String.format("neighbors %d", new Object[] { + Integer.valueOf(neighbors.size()) + })); + for(Iterator iterator = neighbors.iterator(); iterator.hasNext();) { + Node neighbor = (Node)iterator.next(); + Edge edge = graph.getEdge(node, neighbor); + Element.Edge edge_data = (Element.Edge)graph.getEdgeData(edge); + if(element.getObtuse().notEquals(edge_data.getPoint(0)) && element.getObtuse().notEquals(edge_data.getPoint(1))) + return edge; + } + + throw new Error("edge"); + } + + public boolean isMember(Node node) { + Element element = (Element)graph.getNodeData(node); + return element.inCircle(center); + } + + public void build() { + while(frontier.size() != 0) { + Node curr = (Node)frontier.poll(); + Collection neighbors = graph.getOutNeighbors(curr); + for(Iterator iterator = neighbors.iterator(); iterator.hasNext();) { + Node next = (Node)iterator.next(); + Element nextElement = (Element)graph.getNodeData(next); + Edge edge = graph.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.add(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 = graph.createNode(ele1); + post.addNode(node1); + Element ele2 = new Element(center, centerElement.getPoint(1)); + Node node2 = graph.createNode(ele2); + post.addNode(node2); + } + Node ne_node; + for(Iterator iterator = connections.iterator(); iterator.hasNext(); post.addNode(ne_node)) { + Edge conn = (Edge)iterator.next(); + Element.Edge edge = (Element.Edge)graph.getEdgeData(conn); + Element new_element = new Element(center, edge.getPoint(0), edge.getPoint(1)); + ne_node = graph.createNode(new_element); + Node ne_connection; + if(pre.existsNode(graph.getDest(conn))) + ne_connection = graph.getSource(conn); + else + ne_connection = graph.getDest(conn); + Element.Edge new_edge = new_element.getRelatedEdge((Element)graph.getNodeData(ne_connection)); + post.addEdge(graph.createEdge(ne_node, ne_connection, new_edge)); + Collection postnodes = (Collection)post.getNodes().clone(); + for(Iterator iterator1 = postnodes.iterator(); iterator1.hasNext();) { + Node node = (Node)iterator1.next(); + Element element = (Element)graph.getNodeData(node); + if(element.isRelated(new_element)) { + Element.Edge ele_edge = new_element.getRelatedEdge(element); + post.addEdge(graph.createEdge(ne_node, node, ele_edge)); + } + } + + } + + } + + protected Tuple center; + protected Node centerNode; + protected Element centerElement; + protected int dim; + protected final Queue frontier = new LinkedList(); + protected final Subgraph pre = new Subgraph(); + protected final Subgraph post = new Subgraph(); + private final EdgeGraph graph; + protected final HashSet connections = new HashSet(); +} diff --git a/Robust/src/Benchmarks/oooJava/DelaunayRefinement/DirectedEdgeGraph.java b/Robust/src/Benchmarks/oooJava/DelaunayRefinement/DirectedEdgeGraph.java new file mode 100644 index 00000000..75084f17 --- /dev/null +++ b/Robust/src/Benchmarks/oooJava/DelaunayRefinement/DirectedEdgeGraph.java @@ -0,0 +1,293 @@ +import java.util.*; + +public class DirectedEdgeGraph + implements EdgeGraph { + protected class EdgeGraphNode + implements Node { + + 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 Collection getInEdges() { + return inEdges.values(); + } + + protected final Collection getInNeighbors() { + return inEdges.keySet(); + } + + protected final Collection getInNeighborsCopy() { + return new ArrayList(inEdges.keySet()); + } + + 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 Collection getOutEdges() { + return outEdges.values(); + } + + protected final Collection getOutNeighbors() { + return outEdges.keySet(); + } + + protected final Collection getOutNeighborsCopy() { + return new ArrayList(outEdges.keySet()); + } + + public Object getData() { + return getNodeData(this); + } + + public Object setData(Object n) { + return setNodeData(this, n); + } + + protected Map inEdges; + protected Map outEdges; + protected Object data; + final DirectedEdgeGraph this$0; + + EdgeGraphNode() { + super(); + this$0 = DirectedEdgeGraph.this; + } + + EdgeGraphNode(Object d) { + super(); + this$0 = DirectedEdgeGraph.this; + inEdges = new HashMap(); + outEdges = new HashMap(); + data = d; + } + } + + protected class GraphEdge + implements Edge { + + protected final EdgeGraphNode getOpposite(EdgeGraphNode n) { + return n != src ? src : dest; + } + + protected final EdgeGraphNode getSrc() { + return src; + } + + protected final EdgeGraphNode getDest() { + return dest; + } + + public Object getData() { + return getEdgeData(this); + } + + public Object setData(Object e) { + return setEdgeData(this, e); + } + + protected EdgeGraphNode src; + protected EdgeGraphNode dest; + protected Object d; + final DirectedEdgeGraph this$0; + + public GraphEdge(Object d) { + super(); + this$0 = DirectedEdgeGraph.this; + this.d = d; + } + + public GraphEdge(EdgeGraphNode src, EdgeGraphNode dest, Object d) { + this(d); + this.src = src; + this.dest = dest; + } + } + + + public DirectedEdgeGraph() { + nodes = Collections.synchronizedSet(new HashSet()); + } + + public boolean addEdge(Edge 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 createEdge(Node src, Node dest, Object e) { + return new GraphEdge((EdgeGraphNode)src, (EdgeGraphNode)dest, e); + } + + public Node getDest(Edge e) { + return ((GraphEdge)e).getDest(); + } + + public Edge getEdge(Node src, Node dest) { + return ((EdgeGraphNode)src).getOutEdge((EdgeGraphNode)dest); + } + + public Collection getInEdges(Node n) { + return ((EdgeGraphNode)n).getInEdges(); + } + + public Collection getOutEdges(Node n) { + return ((EdgeGraphNode)n).getOutEdges(); + } + + public Node getSource(Edge e) { + return ((GraphEdge)e).src; + } + + public boolean hasEdge(Edge e) { + GraphEdge ge = (GraphEdge)e; + return ge.getSrc().hasOutNeighbor(ge.getDest()); + } + + public boolean removeEdge(Edge 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 Collection getInNeighbors(Node src) { + return ((EdgeGraphNode)src).getInNeighbors(); + } + + public Collection getOutNeighbors(Node src) { + return ((EdgeGraphNode)src).getOutNeighbors(); + } + + 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 e) { + return ((GraphEdge)e).d; + } + + public Object setEdgeData(Edge e, Object d) { + GraphEdge ge = (GraphEdge)e; + Object retval = ge.d; + ge.d = d; + return retval; + } + + public Iterator iterator() { + return nodes.iterator(); + } + + public boolean addNode(Node n) { + return nodes.add((EdgeGraphNode)n); + } + + public boolean containsNode(Node n) { + return nodes.contains(n); + } + + public Object getNodeData(Node n) { + EdgeGraphNode egn = (EdgeGraphNode)n; + return egn.data; + } + + public int getNumNodes() { + return nodes.size(); + } + + public Node getRandom() { + return (Node)Sets.getAny(nodes); + } + + public boolean hasNeighbor(Node src, Node dest) { + EdgeGraphNode esrc = (EdgeGraphNode)src; + EdgeGraphNode edest = (EdgeGraphNode)dest; + return esrc.hasOutNeighbor(edest); + } + + public boolean removeNode(Node n) { + removeConnectingEdges((EdgeGraphNode)n); + return nodes.remove(n); + } + + protected void removeConnectingEdges(EdgeGraphNode n) { + Collection outNeighbors = n.getOutNeighborsCopy(); + EdgeGraphNode g; + for(Iterator iterator1 = outNeighbors.iterator(); iterator1.hasNext(); removeNeighbor(n, g)) + g = (EdgeGraphNode)iterator1.next(); + + Collection inNeighbors = n.getInNeighborsCopy(); + for(Iterator iterator2 = inNeighbors.iterator(); iterator2.hasNext(); removeNeighbor(g, n)) + g = (EdgeGraphNode)iterator2.next(); + + } + + 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; + } + + Set nodes; + } diff --git a/Robust/src/Benchmarks/oooJava/DelaunayRefinement/DirectedGraph.java b/Robust/src/Benchmarks/oooJava/DelaunayRefinement/DirectedGraph.java new file mode 100644 index 00000000..6b26cbd6 --- /dev/null +++ b/Robust/src/Benchmarks/oooJava/DelaunayRefinement/DirectedGraph.java @@ -0,0 +1,177 @@ +import java.util.*; + +public class DirectedGraph + implements Graph { + protected class GraphNode + implements Node { + + 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.add(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 Collection getInNeighbors() { + return inNeighbors; + } + + public final Collection getInNeighborsCopy() { + return new ArrayList(inNeighbors); + } + + public final boolean addOutNeighbor(GraphNode n) { + if(outNeighbors.contains(n)) { + return false; + } else { + outNeighbors.add(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 Collection getOutNeighbors() { + return outNeighbors; + } + + public final Collection getOutNeighborsCopy() { + return new ArrayList(outNeighbors); + } + + protected Object data; + protected List inNeighbors; + protected List outNeighbors; + final DirectedGraph this$0; + + protected GraphNode() { + super(); + this$0 = DirectedGraph.this; + } + + public GraphNode(Object n) { + super(); + this$0 = DirectedGraph.this; + data = n; + inNeighbors = new ArrayList(); + outNeighbors = new ArrayList(); + } + } + + + public DirectedGraph() { + nodes = Collections.synchronizedSet(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) { + return nodes.add((GraphNode)n); + } + + public boolean containsNode(Node n) { + return nodes.contains(n); + } + + public Node createNode(Object n) { + return new GraphNode(n); + } + + public Collection getInNeighbors(Node src) { + GraphNode src_c = (GraphNode)src; + return Collections.unmodifiableCollection(src_c.getInNeighbors()); + } + + public int getNumNodes() { + return nodes.size(); + } + + public Collection getOutNeighbors(Node src) { + GraphNode src_c = (GraphNode)src; + return Collections.unmodifiableCollection(src_c.getOutNeighbors()); + } + + public Node getRandom() { + return (Node)Sets.getAny(nodes); + } + + 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) { + removeConnectingEdges((GraphNode)n); + return nodes.remove(n); + } + + protected void removeConnectingEdges(GraphNode n) { + Collection outNeighbors = n.getOutNeighborsCopy(); + GraphNode g; + for(Iterator iterator1 = outNeighbors.iterator(); iterator1.hasNext(); removeNeighbor(n, g)) { + g = (GraphNode)iterator1.next(); + } + + Collection inNeighbors = n.getInNeighborsCopy(); + for(Iterator iterator2 = inNeighbors.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; + } + + protected Set nodes; + } diff --git a/Robust/src/Benchmarks/oooJava/DelaunayRefinement/Edge.java b/Robust/src/Benchmarks/oooJava/DelaunayRefinement/Edge.java new file mode 100644 index 00000000..ff26b1e5 --- /dev/null +++ b/Robust/src/Benchmarks/oooJava/DelaunayRefinement/Edge.java @@ -0,0 +1,7 @@ + +public interface Edge { + + public abstract Object getData(); + + public abstract Object setData(Object obj); +} diff --git a/Robust/src/Benchmarks/oooJava/DelaunayRefinement/EdgeGraph.java b/Robust/src/Benchmarks/oooJava/DelaunayRefinement/EdgeGraph.java new file mode 100644 index 00000000..01c130ef --- /dev/null +++ b/Robust/src/Benchmarks/oooJava/DelaunayRefinement/EdgeGraph.java @@ -0,0 +1,27 @@ +import java.util.Collection; + +public interface EdgeGraph + extends Graph { + + public abstract Edge createEdge(Node node, Node node1, Object obj); + + public abstract Edge getEdge(Node node, Node node1); + + public abstract boolean removeEdge(Edge edge); + + public abstract boolean addEdge(Edge edge); + + public abstract boolean hasEdge(Edge edge); + + public abstract Node getSource(Edge edge); + + public abstract Node getDest(Edge edge); + + public abstract Collection getOutEdges(Node node); + + public abstract Collection getInEdges(Node node); + + public abstract Object getEdgeData(Edge edge); + + public abstract Object setEdgeData(Edge edge, Object obj); + } diff --git a/Robust/src/Benchmarks/oooJava/DelaunayRefinement/Element.java b/Robust/src/Benchmarks/oooJava/DelaunayRefinement/Element.java new file mode 100644 index 00000000..9d1b3133 --- /dev/null +++ b/Robust/src/Benchmarks/oooJava/DelaunayRefinement/Element.java @@ -0,0 +1,308 @@ + +public class Element { + public static class Edge { + + public boolean equals(Object obj) { + if(!(obj instanceof Edge)) + return false; + Edge edge = (Edge)obj; + return p1.equals(edge.p1) && p2.equals(edge.p2); + } + + public int hashCode() { + return hashvalue; + } + + public boolean notEqual(Edge rhs) { + return !equals(rhs); + } + + public boolean lessThan(Edge rhs) { + return p1.lessThan(rhs.p1) || p1.equals(rhs.p1) && p2.lessThan(rhs.p2); + } + + public boolean greaterThan(Edge 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 (new StringBuilder("<")).append(p1.toString()).append(", ").append(p2.toString()).append(">").toString(); + } + + private final Tuple p1; + private final Tuple p2; + private final int hashvalue; + + public Edge() { + p1 = null; + p2 = null; + hashvalue = 1; + } + + public Edge(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 Edge(Edge rhs) { + p1 = rhs.p1; + p2 = rhs.p2; + hashvalue = rhs.hashvalue; + } + } + + + public Element(Tuple a, Tuple b, Tuple c) { + 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 Edge[3]; + edges[0] = new Edge(coords[0], coords[1]); + edges[1] = new Edge(coords[1], coords[2]); + edges[2] = new Edge(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 Edge[2]; + edges[0] = new Edge(coords[0], coords[1]); + edges[1] = new Edge(coords[1], coords[0]); + bBad = false; + bObtuse = false; + obtuse = null; + center = a.add(b).scale(0.5D); + radius_squared = center.distance_squared(a); + } + + 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(); + Edge e_edge2 = null; + Edge my_edge = edges[0]; + Edge e_edge0 = e.edges[0]; + if(my_edge.equals(e_edge0)) + return true; + Edge 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 = (new StringBuilder(String.valueOf(ret))).append(coords[i].toString()).toString(); + if(i != dim - 1) + ret = (new StringBuilder(String.valueOf(ret))).append(", ").toString(); + } + + ret = (new StringBuilder(String.valueOf(ret))).append("]").toString(); + return ret; + } + + 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 Edge 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 Edge getRelatedEdge(Element e) { + int edim = e.getDim(); + Edge e_edge2 = null; + Edge my_edge = edges[0]; + Edge e_edge0 = e.edges[0]; + if(my_edge.equals(e_edge0)) + return my_edge; + Edge 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; + } + + private final boolean bObtuse; + private final boolean bBad; + private final Tuple obtuse; + private final Tuple coords[]; + private final Edge edges[]; + private final int dim; + private final Tuple center; + private final double radius_squared; + private static final double MINANGLE = 30D; +} diff --git a/Robust/src/Benchmarks/oooJava/DelaunayRefinement/ElementEdge.java b/Robust/src/Benchmarks/oooJava/DelaunayRefinement/ElementEdge.java new file mode 100644 index 00000000..5c9af903 --- /dev/null +++ b/Robust/src/Benchmarks/oooJava/DelaunayRefinement/ElementEdge.java @@ -0,0 +1,71 @@ + +public class ElementEdge { + +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 (new StringBuilder("<")).append(p1.toString()).append(", ").append(p2.toString()).append(">").toString(); +} + +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; +} +} diff --git a/Robust/src/Benchmarks/oooJava/DelaunayRefinement/Graph.java b/Robust/src/Benchmarks/oooJava/DelaunayRefinement/Graph.java new file mode 100644 index 00000000..25facac7 --- /dev/null +++ b/Robust/src/Benchmarks/oooJava/DelaunayRefinement/Graph.java @@ -0,0 +1,36 @@ +import java.util.Collection; +import java.util.Iterator; + +public interface Graph + extends Iterable { + + 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 Collection getInNeighbors(Node node); + + public abstract Collection getOutNeighbors(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/DelaunayRefinement/Mesh.java b/Robust/src/Benchmarks/oooJava/DelaunayRefinement/Mesh.java new file mode 100644 index 00000000..f83811e3 --- /dev/null +++ b/Robust/src/Benchmarks/oooJava/DelaunayRefinement/Mesh.java @@ -0,0 +1,159 @@ +import java.io.*; +import java.util.*; +import java.util.zip.GZIPInputStream; + +public class Mesh { + + public Mesh() { + } + + public static HashSet getBad(EdgeGraph 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 static Scanner getScanner(String filename) + throws Exception { + try { + return new Scanner(new GZIPInputStream(new FileInputStream((new StringBuilder(String.valueOf(filename))).append(".gz").toString()))); + } + catch(FileNotFoundException _) { + return new Scanner(new FileInputStream(filename)); + } + } + + private Tuple[] readNodes(String filename) + throws Exception { + Scanner scanner = getScanner((new StringBuilder(String.valueOf(filename))).append(".node").toString()); + int ntups = scanner.nextInt(); + scanner.nextInt(); + scanner.nextInt(); + scanner.nextInt(); + Tuple tuples[] = new Tuple[ntups]; + for(int i = 0; i < ntups; i++) { + int index = scanner.nextInt(); + double x = scanner.nextDouble(); + double y = scanner.nextDouble(); + scanner.nextDouble(); + tuples[index] = new Tuple(x, y, 0.0D); + } + + return tuples; + } + + private void readElements(EdgeGraph mesh, String filename, Tuple tuples[]) + throws Exception { + Scanner scanner = getScanner((new StringBuilder(String.valueOf(filename))).append(".ele").toString()); + int nels = scanner.nextInt(); + scanner.nextInt(); + scanner.nextInt(); + Element elements[] = new Element[nels]; + for(int i = 0; i < nels; i++) { + int index = scanner.nextInt(); + int n1 = scanner.nextInt(); + int n2 = scanner.nextInt(); + int n3 = scanner.nextInt(); + elements[index] = new Element(tuples[n1], tuples[n2], tuples[n3]); + addElement(mesh, elements[index]); + } + + } + + private void readPoly(EdgeGraph mesh, String filename, Tuple tuples[]) + throws Exception { + Scanner scanner = getScanner((new StringBuilder(String.valueOf(filename))).append(".poly").toString()); + scanner.nextInt(); + scanner.nextInt(); + scanner.nextInt(); + scanner.nextInt(); + int nsegs = scanner.nextInt(); + scanner.nextInt(); + Element segments[] = new Element[nsegs]; + for(int i = 0; i < nsegs; i++) { + int index = scanner.nextInt(); + int n1 = scanner.nextInt(); + int n2 = scanner.nextInt(); + scanner.nextInt(); + segments[index] = new Element(tuples[n1], tuples[n2]); + addElement(mesh, segments[index]); + } + + } + + public void read(EdgeGraph mesh, String basename) + throws Exception { + Tuple tuples[] = readNodes(basename); + readElements(mesh, basename, tuples); + readPoly(mesh, basename, tuples); + } + + protected Node addElement(EdgeGraph mesh, Element element) { + Node node = mesh.createNode(element); + mesh.addNode(node); + for(int i = 0; i < element.numEdges(); i++) { + Element.Edge edge = element.getEdge(i); + if(!edge_map.containsKey(edge)) { + edge_map.put(edge, node); + } else { + Edge new_edge = mesh.createEdge(node, (Node)edge_map.get(edge), edge); + mesh.addEdge(new_edge); + edge_map.remove(edge); + } + } + + return node; + } + + public static boolean verify(EdgeGraph 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.getOutNeighbors(node).size() != 1) { + System.out.println((new StringBuilder("-> Segment ")).append(element).append(" has ").append(mesh.getOutNeighbors(node).size()).append(" relation(s)").toString()); + return false; + } + } else + if(element.getDim() == 3) { + if(mesh.getOutNeighbors(node).size() != 3) { + System.out.println((new StringBuilder("-> Triangle ")).append(element).append(" has ").append(mesh.getOutNeighbors(node).size()).append(" relation(s)").toString()); + return false; + } + } else { + System.out.println((new StringBuilder("-> Figures with ")).append(element.getDim()).append(" edges").toString()); + return false; + } + } + + Node start = mesh.getRandom(); + Stack remaining = new Stack(); + 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).iterator(); 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; + } + } + + protected static final HashMap edge_map = new HashMap(); + +} diff --git a/Robust/src/Benchmarks/oooJava/DelaunayRefinement/Node.java b/Robust/src/Benchmarks/oooJava/DelaunayRefinement/Node.java new file mode 100644 index 00000000..897d5549 --- /dev/null +++ b/Robust/src/Benchmarks/oooJava/DelaunayRefinement/Node.java @@ -0,0 +1,7 @@ + +public interface Node { +// +// public abstract Object getData(); +// +// public abstract Object setData(Object obj); +} diff --git a/Robust/src/Benchmarks/oooJava/DelaunayRefinement/Pair.java b/Robust/src/Benchmarks/oooJava/DelaunayRefinement/Pair.java new file mode 100644 index 00000000..d264b402 --- /dev/null +++ b/Robust/src/Benchmarks/oooJava/DelaunayRefinement/Pair.java @@ -0,0 +1,48 @@ + +public class Pair { + + 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 (new StringBuilder("(")).append(first).append(", ").append(second).append(")").toString(); + } + + 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(); + } + + private Object first; + private Object second; +} diff --git a/Robust/src/Benchmarks/oooJava/DelaunayRefinement/SerialDelaunayrefinement.java b/Robust/src/Benchmarks/oooJava/DelaunayRefinement/SerialDelaunayrefinement.java new file mode 100644 index 00000000..5eb72523 --- /dev/null +++ b/Robust/src/Benchmarks/oooJava/DelaunayRefinement/SerialDelaunayrefinement.java @@ -0,0 +1,103 @@ +import java.io.PrintStream; +import java.util.*; + +public class SerialDelaunayrefinement { + + public SerialDelaunayrefinement() { + } + + public static void main(String args[]) { + long runtime = 0L; + long lasttime = 0xffffffffL; + long mintime = 0xffffffffL; + for(long run = 0L; (run < 3L || Math.abs(lasttime - runtime) * 64L > Math.min(lasttime, runtime)) && run < 7L; run++) { + System.gc(); + System.gc(); + System.gc(); + System.gc(); + System.gc(); + runtime = run(args); + if(runtime < mintime) + mintime = runtime; + } + + System.err.println((new StringBuilder("minimum runtime: ")).append(mintime).append(" ms").toString()); + System.err.println(""); + } + + public static long run(String args[]) { + if(isFirstRun) { + System.err.println(); + System.err.println("Lonestar Benchmark Suite v2.1"); + System.err.println("Copyright (C) 2007, 2008, 2009 The University of Texas at Austin"); + System.err.println("http://iss.ices.utexas.edu/lonestar/"); + System.err.println(); + System.err.println("application: Delaunay Mesh Refinement (serial version)"); + System.err.println("Refines a Delaunay triangulation mesh such that no angle"); + System.err.println("in the mesh is less than 30 degrees"); + System.err.println("http://iss.ices.utexas.edu/lonestar/delaunayrefinement.html"); + System.err.println(); + } + if(args.length < 1) + throw new Error("Arguments: [verify]"); + EdgeGraph mesh = new UndirectedEdgeGraph(); + try { + (new Mesh()).read(mesh, args[0]); + } + catch(Exception e) { + throw new Error(e); + } + Stack worklist = new Stack(); + worklist.addAll(Mesh.getBad(mesh)); + Cavity cavity = new Cavity(mesh); + if(isFirstRun) { + System.err.println((new StringBuilder("configuration: ")).append(mesh.getNumNodes()).append(" total triangles, ").append(worklist.size()).append(" bad triangles").toString()); + System.err.println(); + } + long id = Time.getNewTimeId(); + while(!worklist.isEmpty()) { + Node bad_element = (Node)worklist.pop(); + if(bad_element != null && mesh.containsNode(bad_element)) { + cavity.initialize(bad_element); + cavity.build(); + cavity.update(); + Node node; + for(Iterator iterator = cavity.getPre().getNodes().iterator(); iterator.hasNext(); mesh.removeNode(node)) + node = (Node)iterator.next(); + + for(Iterator iterator1 = cavity.getPost().getNodes().iterator(); iterator1.hasNext(); mesh.addNode(node)) + node = (Node)iterator1.next(); + + Edge edge; + for(Iterator iterator2 = cavity.getPost().getEdges().iterator(); iterator2.hasNext(); mesh.addEdge(edge)) + edge = (Edge)iterator2.next(); + + worklist.addAll(cavity.getPost().newBad(mesh)); + if(mesh.containsNode(bad_element)) + worklist.add(bad_element); + } + } + long time = Time.elapsedTime(id); + System.err.println((new StringBuilder("runtime: ")).append(time).append(" ms").toString()); + if(isFirstRun && args.length > 1) + verify(mesh); + isFirstRun = false; + return time; + } + + public static void verify(Object res) { + EdgeGraph result = (EdgeGraph)res; + if(!Mesh.verify(result)) + throw new IllegalStateException("refinement failed."); + int size = Mesh.getBad(result).size(); + if(size != 0) { + throw new IllegalStateException((new StringBuilder("refinement failed\nstill have ")).append(size).append(" bad triangles left.\n").toString()); + } else { + System.out.println("OK"); + return; + } + } + + private static boolean isFirstRun = true; + +} diff --git a/Robust/src/Benchmarks/oooJava/DelaunayRefinement/Sets.java b/Robust/src/Benchmarks/oooJava/DelaunayRefinement/Sets.java new file mode 100644 index 00000000..35d33b99 --- /dev/null +++ b/Robust/src/Benchmarks/oooJava/DelaunayRefinement/Sets.java @@ -0,0 +1,12 @@ +import java.util.*; + +public final class Sets { + + public Sets() { + } + + public static Object getAny(Collection c) + throws NoSuchElementException { + return c.iterator().next(); + } +} diff --git a/Robust/src/Benchmarks/oooJava/DelaunayRefinement/Subgraph.java b/Robust/src/Benchmarks/oooJava/DelaunayRefinement/Subgraph.java new file mode 100644 index 00000000..4fc810d8 --- /dev/null +++ b/Robust/src/Benchmarks/oooJava/DelaunayRefinement/Subgraph.java @@ -0,0 +1,65 @@ +import java.util.*; + +public class Subgraph { + + public Subgraph() { + } + + public boolean existsNode(Node n) { + return nodes.contains(n); + } + + public boolean existsBorder(Node b) { + return border.contains(b); + } + + public boolean existsEdge(Edge e) { + return edges.contains(e); + } + + public boolean addNode(Node n) { + return nodes.add(n); + } + + public boolean addBorder(Node b) { + return border.add(b); + } + + public void addEdge(Edge e) { + edges.add(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 HashSet newBad(EdgeGraph 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; + } + + private final LinkedList nodes = new LinkedList(); + private final LinkedList border = new LinkedList(); + private final LinkedList edges = new LinkedList(); +} diff --git a/Robust/src/Benchmarks/oooJava/DelaunayRefinement/Time.java b/Robust/src/Benchmarks/oooJava/DelaunayRefinement/Time.java new file mode 100644 index 00000000..af710bc2 --- /dev/null +++ b/Robust/src/Benchmarks/oooJava/DelaunayRefinement/Time.java @@ -0,0 +1,66 @@ +import java.lang.management.GarbageCollectorMXBean; +import java.lang.management.ManagementFactory; +import java.util.*; + +public final class Time { + + public Time() { + } + + public static long getNewTimeId() { + return getNewTimeId(5); + } + + public static long getNewTimeId(int collections) { + for(int i = 0; i < collections; i++) + System.gc(); + + counter++; + times.put(Long.valueOf(counter), new Pair(Long.valueOf(milliTime()), Long.valueOf(milliGcTime()))); + return counter; + } + + public static long elapsedTime(long id) { + Pair startTimes = (Pair)times.get(Long.valueOf(id)); + return elapsedTime(((Long)startTimes.getFirst()).longValue(), ((Long)startTimes.getSecond()).longValue()); + } + + private static long elapsedTime(long startTime, long startGcTime) { + return (milliTime() - startTime - milliGcTime()) + startGcTime; + } + + public static long elapsedTime(long id, boolean includeGc) { + Pair elapsedGcTimes = elapsedAndGcTime(id); + long elapsedTime = ((Long)elapsedGcTimes.getFirst()).longValue(); + long gcTime = ((Long)elapsedGcTimes.getSecond()).longValue(); + return includeGc ? elapsedTime : elapsedTime - gcTime; + } + + public static Pair elapsedAndGcTime(long id) { + long milliTime = milliTime(); + long milliGcTime = milliGcTime(); + Pair startTimes = (Pair)times.get(Long.valueOf(id)); + long startTime = ((Long)startTimes.getFirst()).longValue(); + long startGcTime = ((Long)startTimes.getSecond()).longValue(); + return new Pair(Long.valueOf(milliTime - startTime), Long.valueOf(milliGcTime - startGcTime)); + } + + private static long milliTime() { + return System.nanoTime() / 0xf4240L; + } + + public static long milliGcTime() { + long result = 0L; + for(Iterator iterator = garbageCollectorMXBeans.iterator(); iterator.hasNext();) { + GarbageCollectorMXBean garbageCollectorMXBean = (GarbageCollectorMXBean)iterator.next(); + result += Math.max(0L, garbageCollectorMXBean.getCollectionTime()); + } + + return result; + } + + private static final List garbageCollectorMXBeans = ManagementFactory.getGarbageCollectorMXBeans(); + private static long counter = 0x0L; + private static Map times = new HashMap(); + +} diff --git a/Robust/src/Benchmarks/oooJava/DelaunayRefinement/Tuple.java b/Robust/src/Benchmarks/oooJava/DelaunayRefinement/Tuple.java new file mode 100644 index 00000000..fe645107 --- /dev/null +++ b/Robust/src/Benchmarks/oooJava/DelaunayRefinement/Tuple.java @@ -0,0 +1,144 @@ + +public class Tuple { + + 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((new StringBuilder("(")).append(coords[0]).append(", ").append(coords[1]).append(", ").append(coords[2]).append(")").toString()); + } + + 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]; + } + + private final double coords[]; + private final int hashvalue; +} diff --git a/Robust/src/Benchmarks/oooJava/DelaunayRefinement/UndirectedEdgeGraph.java b/Robust/src/Benchmarks/oooJava/DelaunayRefinement/UndirectedEdgeGraph.java new file mode 100644 index 00000000..38837ca3 --- /dev/null +++ b/Robust/src/Benchmarks/oooJava/DelaunayRefinement/UndirectedEdgeGraph.java @@ -0,0 +1,50 @@ +import java.util.HashMap; + + +public class UndirectedEdgeGraph +extends DirectedEdgeGraph +{ + protected class UndirectedEdgeGraphNode + extends DirectedEdgeGraph.EdgeGraphNode + implements Comparable { + + public int compareTo(UndirectedEdgeGraphNode n) { + return n.hashCode() - hashCode(); + } + + public int compareTo(Object obj) { + return compareTo((UndirectedEdgeGraphNode)obj); + } + + final UndirectedEdgeGraph this$0; + + UndirectedEdgeGraphNode(Object d) { + super(UndirectedEdgeGraph.this); + this$0 = UndirectedEdgeGraph.this; + data = d; + inEdges = new HashMap(); + outEdges = inEdges; + } + } + + + public UndirectedEdgeGraph() { + } + + public Edge createEdge(Node src, Node dest, Object e) { + UndirectedEdgeGraphNode gsrc = (UndirectedEdgeGraphNode)src; + UndirectedEdgeGraphNode gdest = (UndirectedEdgeGraphNode)dest; + if(gsrc.compareTo(gdest) > 0) + return new DirectedEdgeGraph.GraphEdge(gsrc, gdest, e); + else + return new DirectedEdgeGraph.GraphEdge(gdest, gsrc, e); + } + + public UndirectedEdgeGraphNode createNode(Object n) { + return new UndirectedEdgeGraphNode(n); + } + + public boolean isDirected() { + return false; + } +} -- 2.34.1