--- /dev/null
+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 = 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 (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 = graph.createNode(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;
+ }
+}
--- /dev/null
+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;
+ }
+}
--- /dev/null
+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;
+ }
+}
--- /dev/null
+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 );
+}
--- /dev/null
+public class EdgeGraphNode extends Node {\r
+ protected HashMap inEdges;\r
+ protected HashMap outEdges;\r
+ protected Object data;\r
+\r
+ EdgeGraphNode() {\r
+ super();\r
+ }\r
+\r
+ EdgeGraphNode(Object d) {\r
+ super();\r
+ inEdges = new HashMap();\r
+ outEdges = new HashMap();\r
+ data = d;\r
+ }\r
+\r
+ protected final boolean hasInNeighbor(EdgeGraphNode n) {\r
+ return inEdges.containsKey(n);\r
+ }\r
+\r
+ protected boolean addInEdge(EdgeGraphNode n, GraphEdge e) {\r
+ if (hasInNeighbor(n)) {\r
+ return false;\r
+ } else {\r
+ inEdges.put(n, e);\r
+ return true;\r
+ }\r
+ }\r
+\r
+ protected boolean removeInEdge(EdgeGraphNode n) {\r
+ if (!hasInNeighbor(n)) {\r
+ return false;\r
+ } else {\r
+ inEdges.remove(n);\r
+ return true;\r
+ }\r
+ }\r
+\r
+ protected GraphEdge getInEdge(EdgeGraphNode n) {\r
+ return (GraphEdge) inEdges.get(n);\r
+ }\r
+\r
+ protected Iterator getInEdges() {\r
+ return inEdges.iterator(1);\r
+ }\r
+\r
+ protected final Iterator getInNeighbors() {\r
+ return inEdges.iterator(0);\r
+ }\r
+\r
+ // TODO someone check this for performance.\r
+ protected final Iterator getInNeighborsCopy() {\r
+ LinkedList l = new LinkedList();\r
+ HashMapIterator o = inEdges.iterator(0);\r
+ while (o.hasNext()) {\r
+ l.addLast(o.next());\r
+ }\r
+ return l.iterator();\r
+ }\r
+\r
+ protected final boolean hasOutNeighbor(EdgeGraphNode n) {\r
+ return outEdges.containsKey(n);\r
+ }\r
+\r
+ protected boolean addOutEdge(EdgeGraphNode n, GraphEdge e) {\r
+ if (hasOutNeighbor(n)) {\r
+ return false;\r
+ } else {\r
+ outEdges.put(n, e);\r
+ return true;\r
+ }\r
+ }\r
+\r
+ protected boolean removeOutEdge(EdgeGraphNode n) {\r
+ if (!hasOutNeighbor(n)) {\r
+ return false;\r
+ } else {\r
+ outEdges.remove(n);\r
+ return true;\r
+ }\r
+ }\r
+\r
+ protected GraphEdge getOutEdge(EdgeGraphNode n) {\r
+ return (GraphEdge) outEdges.get(n);\r
+ }\r
+\r
+ protected Iterator getOutEdges() {\r
+ return outEdges.iterator(1);\r
+ }\r
+\r
+ protected final Iterator getOutNeighbors() {\r
+ return outEdges.iterator(0);\r
+ }\r
+\r
+ // TODO someone check this for performance.\r
+ protected final Iterator getOutNeighborsCopy() {\r
+ LinkedList l = new LinkedList();\r
+ HashMapIterator o = outEdges.iterator(0);\r
+ while (o.hasNext()) {\r
+ l.addLast(o.next());\r
+ }\r
+ return l.iterator();\r
+ }\r
+ }
\ No newline at end of file
--- /dev/null
+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);
+}
--- /dev/null
+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;
+ }
+}
--- /dev/null
+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()+">";
+ }
+}
--- /dev/null
+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();
+}
--- /dev/null
+public class GraphEdge extends Edge_d {\r
+ protected EdgeGraphNode src;\r
+ protected EdgeGraphNode dest;\r
+ protected Object d;\r
+\r
+ public GraphEdge(Object d) {\r
+ super();\r
+ this.d = d;\r
+ }\r
+\r
+ public GraphEdge(EdgeGraphNode src, EdgeGraphNode dest, Object d) {\r
+ this(d);\r
+ this.src = src;\r
+ this.dest = dest;\r
+ }\r
+\r
+ protected final EdgeGraphNode getOpposite(EdgeGraphNode n) {\r
+ return n != src ? src : dest;\r
+ }\r
+\r
+ protected final EdgeGraphNode getSrc() {\r
+ return src;\r
+ }\r
+\r
+ protected final EdgeGraphNode getDest() {\r
+ return dest;\r
+ }\r
+}
\ No newline at end of file
--- /dev/null
+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
--- /dev/null
+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;
+ }
+ }
+}
--- /dev/null
+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);
+}
--- /dev/null
+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();
+ }
+}
--- /dev/null
+/*
+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: <input file> <num workers> [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<numWorkers;i++) {
+ if(worklist.isEmpty()) {
+ nodesForBadTris[i] = null;
+ } else {
+ nodesForBadTris[i] = (Node) worklist.pop();
+ }
+
+ cavities[i] = null;
+ }
+
+ // Phase 2, read mesh and compute cavities in parallel
+ for(int i=0;i<numWorkers;i++) {
+
+ Node nodeForBadTri = nodesForBadTris[i];
+
+ if (nodeForBadTri != null &&
+ nodeForBadTri.inGraph
+ ) {
+
+ sese computeCavity {
+ //takes < 1 sec
+ Cavity cavity = new Cavity(mesh);
+
+ //Appears to only call getters (only possible conflict is inherent in Hashmap)
+ cavity.initialize(nodeForBadTri);
+
+ //Takes up 15% of computation
+ cavity.build();
+
+ //Takes up a whooping 50% of computation time and changes NOTHING but cavity :D
+ cavity.update();
+ }
+
+ sese storeCavity {
+ cavities[i] = cavity;
+ }
+
+ }
+ }
+
+ // Phase 3, apply cavities to mesh, if still applicable
+ // this phase can proceed in parallel when a cavity's
+ // start nodes are still present
+ for(int i=0;i<numWorkers;i++) {
+
+ Cavity cavity = cavities[i];
+ Node nodeForBadTri = nodesForBadTris[i];
+
+
+ sese applyCavity {
+
+ int appliedCavity = 0;
+
+ // go ahead with applying cavity when all of its
+ // pre-nodes are still in
+ if( cavity != null &&
+ cavity.getPre().allNodesAndBorderStillInCompleteGraph() ) {
+
+ appliedCavity = 1;
+
+
+ //remove old data
+ //Takes up 8.9% of runtime
+ Node node;
+ for (Iterator iterator = cavity.getPre().getNodes().iterator();
+ iterator.hasNext();) {
+
+ node = (Node) iterator.next();
+ mesh.removeNode(node);
+ }
+
+ //add new data
+ //Takes up 1.7% of runtime
+ for (Iterator iterator1 = cavity.getPost().getNodes().iterator();
+ iterator1.hasNext();) {
+
+ node = (Node) iterator1.next();
+ mesh.addNode(node);
+ }
+
+ //Takes up 7.8% of runtime
+ Edge_d edge;
+ for (Iterator iterator2 = cavity.getPost().getEdges().iterator();
+ iterator2.hasNext();) {
+
+ edge = (Edge_d) iterator2.next();
+ mesh.addEdge(edge);
+ }
+ }
+ }
+
+
+ sese scheduleMoreBad {
+
+ if( appliedCavity == 1 ) {
+
+ lastAppliedCavity = cavity;
+
+ // we did apply the cavity, and we may
+ // have introduced new bad triangles
+ HashMapIterator it2 = cavity.getPost().newBad(mesh).iterator();
+ while (it2.hasNext()) {
+ worklist.push((Node)it2.next());
+ }
+ }
+
+ // the logic of having this out here seems wacky, and overconservative,
+ // but it matches the original algorithm and it works...
+ if( nodeForBadTri != null && mesh.containsNode( nodeForBadTri ) ) {
+ worklist.push( nodeForBadTri );
+ }
+
+ } // end scheduleMoreBad
+ } // end phase 3
+
+ } // end while( !worklist.isEmpty() )
+
+ System.out.println( "yuh?" );
+ } // end sese workLoop
+
+ // stall before runtime calc, this is an empty method
+ lastAppliedCavity.triggerAbort();
+
+ long time = System.currentTimeMillis() - startTime;
+ System.out.println("runtime: " + time + " ms");
+ //TODO note how we only verify on first run...
+ //TODO verify is outside timing, do it each time
+ // since we MIGHT compute something different when
+ // we have a bug
+ if (//isFirstRun &&
+ args.length > 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;
+ }
+ }
+}
--- /dev/null
+/* 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/*<T>*/ extends Vector/*<T>*/
+{
+ // 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;
+ }
+}
--- /dev/null
+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;
+ }
+}
--- /dev/null
+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];
+ }
+}
--- /dev/null
+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;
+ }
+}
--- /dev/null
+public class UndirectedEdgeGraphNode extends EdgeGraphNode {\r
+\r
+ public int compareTo(UndirectedEdgeGraphNode n) {\r
+ return n.hashCode() - hashCode();\r
+ }\r
+\r
+ public int compareTo(Object obj) {\r
+ return compareTo((UndirectedEdgeGraphNode) obj);\r
+ }\r
+\r
+ UndirectedEdgeGraphNode(Object d) {\r
+ data = d;\r
+ inEdges = new HashMap();\r
+ outEdges = inEdges;\r
+ }\r
+ }
\ No newline at end of file
--- /dev/null
+PROGRAM=SerialDelaunayRefinement
+
+SOURCE_FILES=SerialDelaunayRefinement.java
+
+NUM_OOO_WORKERS=24
+NUM_RCR_WORKERS=7
+
+include ../master-makefile
projects / IRC.git / commitdiff