1 cananian 1.1 // CycleEq.java, created Wed Oct 14 08:15:53 1998 by cananian
2 cananian 1.4 // Copyright (C) 1998 C. Scott Ananian <cananian@alumni.princeton.edu>
3 cananian 1.4 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 cananian 1.1 package harpoon.Analysis;
5 cananian 1.1
6 cananian 1.4.2.6 import harpoon.ClassFile.HCode;
7 cananian 1.4.2.6 import harpoon.ClassFile.HCodeEdge;
8 cananian 1.4.2.6 import harpoon.ClassFile.HCodeElement;
9 cananian 1.4.2.21 import harpoon.IR.Properties.CFGraphable;
10 cananian 1.9 import net.cscott.jutil.UnmodifiableIterator;
11 cananian 1.1 import harpoon.Util.Util;
12 cananian 1.1
13 cananian 1.4.2.8 import java.util.ArrayList;
14 cananian 1.4.2.8 import java.util.Collection;
15 cananian 1.4.2.8 import java.util.Collections;
16 cananian 1.4.2.8 import java.util.HashMap;
17 cananian 1.4.2.8 import java.util.HashSet;
18 cananian 1.4.2.8 import java.util.Iterator;
19 cananian 1.4.2.10 import java.util.LinkedList;
20 cananian 1.4.2.8 import java.util.List;
21 cananian 1.4.2.8 import java.util.Map;
22 sportbilly 1.4.2.18 import java.util.NoSuchElementException;
23 cananian 1.4.2.8 import java.util.Set;
24 cananian 1.1 import java.util.Stack;
25 cananian 1.4.2.8
26 cananian 1.1 /**
27 sportbilly 1.4.2.18 * <code>CycleEq</code> computes cycle equivalence classes for edges in
28 cananian 1.3 * a control flow graph, in O(E) time.
29 cananian 1.1 *
30 cananian 1.4 * @author C. Scott Ananian <cananian@alumni.princeton.edu>
31 cananian 1.9 * @version $Id: CycleEq.java,v 1.9 2004/02/08 01:49:03 cananian Exp $
32 cananian 1.1 */
33 cananian 1.1
34 cananian 1.1 public class CycleEq {
35 sportbilly 1.4.2.18 /* List of <code>HCodeEdge</code>s in DFS order */
36 sportbilly 1.4.2.18 private List elements = new ArrayList();
37 sportbilly 1.4.2.18 /* Mapping of cycle equivalency class object to <code>List</code>
38 sportbilly 1.4.2.18 * of <code>HCodeEdge</code>s in that equivalency class. */
39 sportbilly 1.4.2.18 private Map equiv = new HashMap();
40 sportbilly 1.4.2.18
41 cananian 1.1 public CycleEq(HCode hc) {
42 sportbilly 1.4.2.18 Graph g = new Graph(hc); // compute cycle equivalency
43 sportbilly 1.4.2.18 // DFS search to order elements in cycle-equivalency classes.
44 sportbilly 1.4.2.18 dfs(g, hc.getRootElement(), new HashSet());
45 cananian 1.4.2.9 // make equiv and elements unmodifiable.
46 cananian 1.4.2.8 equiv = Collections.unmodifiableMap(equiv);
47 cananian 1.4.2.9 elements = Collections.unmodifiableList(elements);
48 cananian 1.1 // throw away all temp info now.
49 cananian 1.1 }
50 sportbilly 1.4.2.18 private void dfs(Graph g, HCodeElement hce, Set mark) {
51 cananian 1.4.2.19 Stack s = new Stack();
52 cananian 1.4.2.19 newnode: // this is an obvious hack to allow a 'goto' statement
53 cananian 1.4.2.19 do { // despite java's "prohibition".
54 cananian 1.4.2.19 mark.add(hce);
55 cananian 1.4.2.21 s.push(((CFGraphable)hce).succC().iterator());
56 cananian 1.4.2.19
57 cananian 1.4.2.19 while (!s.isEmpty()) {
58 cananian 1.4.2.19 for (Iterator i = (Iterator) s.pop(); i.hasNext(); ) {
59 cananian 1.4.2.19 HCodeEdge e = (HCodeEdge)i.next();
60 cananian 1.4.2.19 Object cq = g.edge(e).CQclass;
61 cananian 1.4.2.19 List l = (List) equiv.get(cq);
62 cananian 1.4.2.19 if (l==null) { l = new LinkedList(); equiv.put(cq, l); }
63 cananian 1.4.2.19 l.add(e); // append edge to end of list.
64 cananian 1.4.2.19 elements.add(e);
65 cananian 1.4.2.19 // recurse
66 cananian 1.4.2.19 if (!mark.contains(e.to())) {
67 cananian 1.4.2.19 s.push(i);
68 cananian 1.4.2.19 hce = e.to();
69 cananian 1.4.2.19 continue newnode; // recurse to top of procedure.
70 cananian 1.4.2.19 }
71 cananian 1.1 }
72 cananian 1.1 }
73 cananian 1.4.2.24 break;
74 cananian 1.4.2.24 } while(true); // not really a loop. Just a block.
75 sportbilly 1.4.2.18 }
76 cananian 1.4.2.9 /** Return <code>Collection</code> of cycle-equivalency
77 cananian 1.4.2.9 * <code>List</code>s. */
78 cananian 1.4.2.8 public Collection cdClasses() { return equiv.values(); }
79 sportbilly 1.4.2.18 /** Return <code>List</code> of edges in DFS order. */
80 cananian 1.4.2.9 public List elements() { return elements; }
81 cananian 1.1
82 sportbilly 1.4.2.18 /* ----------------------------------------------------- */
83 cananian 1.1
84 sportbilly 1.4.2.18 /** Graph stored edge/node information for cycle-equivalency computation.
85 sportbilly 1.4.2.18 * Also adds synthetic END->START edge to make CFG an SCC. */
86 sportbilly 1.4.2.18 static private class Graph {
87 sportbilly 1.4.2.18 Map hce2node = new HashMap(); // map HCodeElements to nodes.
88 sportbilly 1.4.2.18 Map hce2edge = new HashMap(); // map HCodeEdges to edges
89 sportbilly 1.4.2.18 Map start_edges = new HashMap(); // from synthetic START to root.
90 sportbilly 1.4.2.18 Map end_edges = new HashMap(); // from synthetic END to leaves.
91 sportbilly 1.4.2.18 Node START = new StartNode(); // synthetic START
92 sportbilly 1.4.2.18 Node END = new EndNode(); // synthetic END
93 sportbilly 1.4.2.18 List all_nodes = new ArrayList(); // all nodes, in dfs preorder.
94 sportbilly 1.4.2.18 Graph(HCode c) {
95 sportbilly 1.4.2.18 /* initialize graph */
96 sportbilly 1.4.2.18 HCodeElement root = c.getRootElement();
97 sportbilly 1.4.2.18 start_edges.put(root, new FakeEdge(START, node(root)));
98 sportbilly 1.4.2.18 HCodeElement[] leaves = c.getLeafElements();
99 sportbilly 1.4.2.18 for (int i=0; i<leaves.length; i++)
100 sportbilly 1.4.2.18 end_edges.put(leaves[i], new FakeEdge(node(leaves[i]), END));
101 sportbilly 1.4.2.18 Edge e = new FakeEdge(START, END); // synthetic END->START edge
102 sportbilly 1.4.2.18 start_edges.put(null, e);
103 sportbilly 1.4.2.18 end_edges.put(null, e);
104 sportbilly 1.4.2.18 /* construct depth first spanning tree */
105 sportbilly 1.4.2.18 dfs(START, new HashSet());
106 sportbilly 1.4.2.18 /* compute cycle equivalence */
107 sportbilly 1.4.2.18 for (int i=all_nodes.size()-1; i>=0; i--) // dfs postorder
108 sportbilly 1.4.2.18 cycle((Node)all_nodes.get(i));
109 sportbilly 1.4.2.18 }
110 sportbilly 1.4.2.18 /** Map HCodeElement to Node, creating new RealNode if necessary. */
111 sportbilly 1.4.2.18 Node node(HCodeElement hce) {
112 cananian 1.6.2.1 assert hce!=null;
113 sportbilly 1.4.2.18 Node n = (Node) hce2node.get(hce);
114 sportbilly 1.4.2.18 return (n!=null)?n:new RealNode(hce);
115 sportbilly 1.4.2.18 }
116 sportbilly 1.4.2.18 /** Map HCodeEdge to Edge, creating new RealEdge if necessary. */
117 sportbilly 1.4.2.18 Edge edge(HCodeEdge hce) {
118 cananian 1.6.2.1 assert hce!=null;
119 sportbilly 1.4.2.18 Edge e = (Edge) hce2edge.get(hce);
120 sportbilly 1.4.2.18 return (e!=null)?e:new RealEdge(hce);
121 sportbilly 1.4.2.18 }
122 sportbilly 1.4.2.18 /** Construct depth-first spanning tree. */
123 sportbilly 1.4.2.18 void dfs(Node n, Set mark) {
124 cananian 1.6.2.1 assert !mark.contains(n);
125 sportbilly 1.4.2.18 n.dfsnum = mark.size();
126 sportbilly 1.4.2.18 mark.add(n);
127 sportbilly 1.4.2.18 all_nodes.add(n);
128 sportbilly 1.4.2.18 for (Iterator i=n.adj(); i.hasNext(); ) {
129 sportbilly 1.4.2.18 Edge e = (Edge) i.next();
130 sportbilly 1.4.2.18 Node m = e.otherEnd(n); /* edge from n to m */
131 sportbilly 1.4.2.18 if (!mark.contains(m)) { /* a tree edge (child) */
132 sportbilly 1.4.2.18 n.children = new EdgeSList(e, n.children);
133 sportbilly 1.4.2.18 m.parent = e;
134 sportbilly 1.4.2.18 /* recurse */
135 sportbilly 1.4.2.18 dfs(m, mark);
136 sportbilly 1.4.2.18 } else if (!e.equals(n.parent)) { /* a backedge */
137 sportbilly 1.4.2.18 n.backedges = new EdgeSList(e, n.backedges);
138 cananian 1.1 }
139 cananian 1.1 }
140 cananian 1.4.2.11 }
141 sportbilly 1.4.2.18 /** Compute cycle-equivalency */
142 sportbilly 1.4.2.18 void cycle(Node n) {
143 sportbilly 1.4.2.18 /** Compute hi(n) */
144 sportbilly 1.4.2.18 Node hi0 = null;
145 sportbilly 1.4.2.18 for (EdgeSList el=n.backedges; el!=null; el=el.next)
146 sportbilly 1.4.2.18 if (hi0==null || el.e.otherEnd(n).dfsnum < hi0.dfsnum)
147 sportbilly 1.4.2.18 hi0 = el.e.otherEnd(n);
148 sportbilly 1.4.2.18 Node hi1 = null, hi2 = null;
149 sportbilly 1.4.2.18 for (EdgeSList el=n.children; el!=null; el=el.next)
150 sportbilly 1.4.2.18 if (hi1==null || el.e.otherEnd(n).hi.dfsnum < hi1.dfsnum) {
151 sportbilly 1.4.2.18 if (hi2==null || hi1.dfsnum < hi2.dfsnum) hi2 = hi1;
152 sportbilly 1.4.2.18 hi1 = el.e.otherEnd(n).hi;
153 sportbilly 1.4.2.18 } else if (hi2==null ||
154 sportbilly 1.4.2.18 el.e.otherEnd(n).hi.dfsnum < hi2.dfsnum) {
155 sportbilly 1.4.2.18 hi2 = el.e.otherEnd(n).hi; // second-highest.
156 cananian 1.4.2.3 }
157 cananian 1.1
158 sportbilly 1.4.2.18 n.hi = (hi0==null) ? hi1 : (hi1==null) ? hi0 :
159 sportbilly 1.4.2.18 (hi0.dfsnum < hi1.dfsnum) ? hi0 : hi1;
160 cananian 1.1
161 sportbilly 1.4.2.18 /* compute bracketlist */
162 cananian 1.1 n.blist = new BracketList();
163 sportbilly 1.4.2.18 for (EdgeSList el=n.children; el!=null; el=el.next)
164 sportbilly 1.4.2.18 n.blist.append(el.e.otherEnd(n).blist);
165 sportbilly 1.4.2.18 for (EdgeSList el=n.capping; el!=null; el=el.next)
166 sportbilly 1.4.2.18 n.blist.delete(el.e);
167 sportbilly 1.4.2.18 for (EdgeSList el=n.backedges; el!=null; el=el.next)
168 sportbilly 1.4.2.18 if (el.e.otherEnd(n).dfsnum > n.dfsnum) { /* descendant of n */
169 sportbilly 1.4.2.18 n.blist.delete(el.e);
170 sportbilly 1.4.2.18 if (el.e.CQclass==null)
171 sportbilly 1.4.2.18 el.e.CQclass = new Object(); /* new CQ class */
172 cananian 1.1 }
173 sportbilly 1.4.2.18 for (EdgeSList el=n.backedges; el!=null; el=el.next)
174 cananian 1.4.2.20 if (el.e.otherEnd(n).dfsnum <= n.dfsnum) /*ancestor or itself*/
175 sportbilly 1.4.2.18 n.blist.push(el.e);
176 sportbilly 1.4.2.18 if (hi2!=null &&
177 sportbilly 1.4.2.18 (hi0==null || hi0.dfsnum > hi2.dfsnum)) {
178 sportbilly 1.4.2.18 /* create capping backedge */
179 sportbilly 1.4.2.18 Edge d = new FakeEdge(n, hi2);
180 sportbilly 1.4.2.18 hi2.capping = new EdgeSList(d, hi2.capping);
181 sportbilly 1.4.2.18 n.blist.push(d);
182 sportbilly 1.4.2.18 }
183 sportbilly 1.4.2.18
184 sportbilly 1.4.2.18 /* determine class for edge from parent(n) to n */
185 sportbilly 1.4.2.18 Edge e = n.parent;
186 sportbilly 1.4.2.18 if (e!=null) {
187 sportbilly 1.4.2.18 Edge b = n.blist.top();
188 sportbilly 1.4.2.18 if (b.recentSize != n.blist.size()) {
189 sportbilly 1.4.2.18 b.recentSize = n.blist.size();
190 sportbilly 1.4.2.18 b.recentClass= new Object(); /* new CQ class */
191 cananian 1.1 }
192 sportbilly 1.4.2.18 e.CQclass = b.recentClass;
193 cananian 1.1
194 sportbilly 1.4.2.18 /* handle one tree one backedge case */
195 sportbilly 1.4.2.18 if (b.recentSize==1)
196 sportbilly 1.4.2.18 b.CQclass = e.CQclass;
197 sportbilly 1.4.2.18 }
198 sportbilly 1.4.2.18 }
199 sportbilly 1.4.2.18
200 sportbilly 1.4.2.18 /** Graph node superclass */
201 sportbilly 1.4.2.18 abstract class Node {
202 sportbilly 1.4.2.18 int dfsnum = -1;
203 sportbilly 1.4.2.18 BracketList blist;
204 sportbilly 1.4.2.18 Node hi; // highest reachable from backedge originating below this
205 sportbilly 1.4.2.18 //
206 sportbilly 1.4.2.18 Edge parent = null;
207 sportbilly 1.4.2.18 EdgeSList children = null;
208 sportbilly 1.4.2.18 EdgeSList backedges= null;
209 sportbilly 1.4.2.18 EdgeSList capping = null;
210 sportbilly 1.4.2.18
211 sportbilly 1.4.2.18 abstract Iterator adj(); /* return all edges */
212 sportbilly 1.4.2.18 public abstract boolean equals(Object o);
213 sportbilly 1.4.2.18 public abstract int hashCode();
214 sportbilly 1.4.2.18 public String toString() { return "["+dfsnum+"]"; }
215 sportbilly 1.4.2.18 }
216 sportbilly 1.4.2.18 /** Synthetic START node */
217 sportbilly 1.4.2.18 class StartNode extends Node {
218 sportbilly 1.4.2.18 Iterator adj() { return start_edges.values().iterator(); }
219 sportbilly 1.4.2.18 public boolean equals(Object o) { return o instanceof StartNode; }
220 sportbilly 1.4.2.18 public int hashCode() { return 458543; }
221 sportbilly 1.4.2.18 public String toString() { return "START"; }
222 sportbilly 1.4.2.18 }
223 sportbilly 1.4.2.18 /** Synthetic END node */
224 sportbilly 1.4.2.18 class EndNode extends Node {
225 sportbilly 1.4.2.18 Iterator adj() { return end_edges.values().iterator(); }
226 sportbilly 1.4.2.18 public boolean equals(Object o) { return o instanceof EndNode; }
227 sportbilly 1.4.2.18 public int hashCode() { return 234913; }
228 sportbilly 1.4.2.18 public String toString() { return "END"; }
229 sportbilly 1.4.2.18 }
230 sportbilly 1.4.2.18 /** 'Real' node corresponding to an HCodeElement */
231 sportbilly 1.4.2.18 class RealNode extends Node {
232 sportbilly 1.4.2.18 final HCodeElement hce;
233 sportbilly 1.4.2.18 //
234 sportbilly 1.4.2.18 RealNode(HCodeElement hce) {
235 cananian 1.6.2.1 assert hce!=null;
236 cananian 1.6.2.1 assert !hce2node.containsKey(hce);
237 sportbilly 1.4.2.18 this.hce = hce; hce2node.put(hce, this);
238 sportbilly 1.4.2.18 }
239 sportbilly 1.4.2.18 Iterator adj() {
240 sportbilly 1.4.2.18 return new UnmodifiableIterator() {
241 cananian 1.4.2.21 final HCodeEdge[] pred=((CFGraphable)hce).pred();
242 cananian 1.4.2.21 final HCodeEdge[] succ=((CFGraphable)hce).succ();
243 sportbilly 1.4.2.18 Edge se = (Edge) start_edges.get(hce);
244 sportbilly 1.4.2.18 Edge ee = (Edge) end_edges.get(hce);
245 sportbilly 1.4.2.18 int i=0, j=0;
246 sportbilly 1.4.2.18 public boolean hasNext() {
247 sportbilly 1.4.2.18 return (i<pred.length) || (j<succ.length) ||
248 sportbilly 1.4.2.18 (se != null) || (ee != null);
249 cananian 1.4.2.2 }
250 sportbilly 1.4.2.18 public Object next() {
251 sportbilly 1.4.2.18 if (i<pred.length)
252 sportbilly 1.4.2.18 return edge(pred[i++]);
253 sportbilly 1.4.2.18 if (j<succ.length)
254 sportbilly 1.4.2.18 return edge(succ[j++]);
255 sportbilly 1.4.2.18 if (se!=null) { Edge e=se; se=null; return e; }
256 sportbilly 1.4.2.18 if (ee!=null) { Edge e=ee; ee=null; return e; }
257 sportbilly 1.4.2.18 throw new NoSuchElementException();
258 cananian 1.4.2.2 }
259 cananian 1.4.2.2 };
260 cananian 1.4.2.4 }
261 sportbilly 1.4.2.18 public int hashCode() { return hce.hashCode(); }
262 sportbilly 1.4.2.18 public boolean equals(Object o) {
263 sportbilly 1.4.2.18 RealNode rn;
264 sportbilly 1.4.2.18 if (this==o) return true;
265 sportbilly 1.4.2.18 if (null==o) return false;
266 sportbilly 1.4.2.18 try { rn = (RealNode) o; }
267 sportbilly 1.4.2.18 catch (ClassCastException e) { return false; }
268 sportbilly 1.4.2.18 return rn.hce.equals(hce);
269 sportbilly 1.4.2.18 }
270 sportbilly 1.4.2.18 public String toString()
271 sportbilly 1.4.2.18 { return super.toString()+" "+hce.toString(); }
272 sportbilly 1.4.2.18 }
273 sportbilly 1.4.2.18
274 sportbilly 1.4.2.18 /** Graph edge superclass */
275 sportbilly 1.4.2.18 abstract class Edge {
276 sportbilly 1.4.2.18 Object CQclass = null;
277 sportbilly 1.4.2.18 int recentSize;
278 sportbilly 1.4.2.18 Object recentClass;
279 sportbilly 1.4.2.18 EdgeDList container;
280 sportbilly 1.4.2.18 //
281 sportbilly 1.4.2.18 public abstract Node otherEnd(Node n);
282 sportbilly 1.4.2.18 public int hashCode() { throw new Error("Unimplemented."); }
283 sportbilly 1.4.2.18 public abstract String toString();
284 sportbilly 1.4.2.18 }
285 sportbilly 1.4.2.18 /** 'Real' edge corresponding to HCodeEdge */
286 sportbilly 1.4.2.18 class RealEdge extends Edge {
287 sportbilly 1.4.2.18 final HCodeEdge hce;
288 sportbilly 1.4.2.18 RealEdge(HCodeEdge hce) {
289 cananian 1.6.2.1 assert hce!=null;
290 cananian 1.6.2.1 assert !hce2edge.containsKey(hce);
291 sportbilly 1.4.2.18 this.hce = hce; hce2edge.put(hce, this);
292 sportbilly 1.4.2.18 }
293 sportbilly 1.4.2.18 public Node otherEnd(Node n) {
294 sportbilly 1.4.2.18 RealNode rn = (RealNode) n; /* RealEdge connects RealNodes */
295 sportbilly 1.4.2.18 return node(hce.from().equals(rn.hce)?hce.to():hce.from());
296 sportbilly 1.4.2.18 }
297 sportbilly 1.4.2.18 public String toString() { return hce.toString(); }
298 sportbilly 1.4.2.18 }
299 sportbilly 1.4.2.18 /** Synthetic edge; either capping or connecting Synthetic
300 sportbilly 1.4.2.18 * START or END nodes to each other or to real root/leaves. */
301 sportbilly 1.4.2.18 class FakeEdge extends Edge {
302 sportbilly 1.4.2.18 final Node from, to;
303 sportbilly 1.4.2.18 FakeEdge(Node from, Node to) {
304 cananian 1.6.2.1 assert from!=null && to !=null;
305 sportbilly 1.4.2.18 this.from = from; this.to = to;
306 sportbilly 1.4.2.18 }
307 sportbilly 1.4.2.18 public Node otherEnd(Node n) {
308 sportbilly 1.4.2.18 return from.equals(n)?to:from;
309 sportbilly 1.4.2.18 }
310 sportbilly 1.4.2.18 public String toString() {
311 sportbilly 1.4.2.18 return "Fake: "+from+" -> "+to;
312 sportbilly 1.4.2.18 }
313 sportbilly 1.4.2.18 }
314 sportbilly 1.4.2.18
315 sportbilly 1.4.2.18 /*--------------- Utility classes ----------------*/
316 sportbilly 1.4.2.18 /** Singly-linked lists of edges. */
317 sportbilly 1.4.2.18 static class EdgeSList {
318 sportbilly 1.4.2.18 final Edge e;
319 sportbilly 1.4.2.18 final EdgeSList next;
320 sportbilly 1.4.2.18 EdgeSList(Edge e, EdgeSList next) {
321 sportbilly 1.4.2.18 this.e = e; this.next = next;
322 sportbilly 1.4.2.18 }
323 sportbilly 1.4.2.18 }
324 sportbilly 1.4.2.18 /** Doubly-linked lists of edges. */
325 sportbilly 1.4.2.18 static class EdgeDList {
326 sportbilly 1.4.2.18 final Edge e;
327 sportbilly 1.4.2.18 EdgeDList prev, next;
328 sportbilly 1.4.2.18 EdgeDList(EdgeDList prev, Edge e, EdgeDList next) {
329 sportbilly 1.4.2.18 this.prev = prev; this.e = e; this.next = next;
330 sportbilly 1.4.2.18 }
331 sportbilly 1.4.2.18 }
332 sportbilly 1.4.2.18 /** BracketList structure, based on doubly-linked edge list. */
333 sportbilly 1.4.2.18 static class BracketList {
334 sportbilly 1.4.2.18 EdgeDList first = null;
335 sportbilly 1.4.2.18 EdgeDList last = null;
336 sportbilly 1.4.2.18 int size = 0;
337 sportbilly 1.4.2.18
338 sportbilly 1.4.2.18 public BracketList() { }
339 sportbilly 1.4.2.18 public int size() { return size; }
340 sportbilly 1.4.2.18 public void push(Edge e) {
341 sportbilly 1.4.2.18 first = new EdgeDList(null, e, first);
342 sportbilly 1.4.2.18 if (first.next!=null)
343 sportbilly 1.4.2.18 first.next.prev = first;
344 sportbilly 1.4.2.18 else
345 sportbilly 1.4.2.18 last = first;
346 sportbilly 1.4.2.18 e.container = first;
347 sportbilly 1.4.2.18 size++;
348 sportbilly 1.4.2.18 }
349 sportbilly 1.4.2.18 public Edge top() { return first.e; }
350 sportbilly 1.4.2.18 public void delete(Edge e) {
351 sportbilly 1.4.2.18 delete(e.container);
352 sportbilly 1.4.2.18 }
353 sportbilly 1.4.2.18 private void delete(EdgeDList el) {
354 sportbilly 1.4.2.18 if (first==el) first=el.next;
355 sportbilly 1.4.2.18 else el.prev.next = el.next;
356 sportbilly 1.4.2.18 if (last==el) last = el.prev;
357 sportbilly 1.4.2.18 else el.next.prev = el.prev;
358 sportbilly 1.4.2.18 size--;
359 sportbilly 1.4.2.18 }
360 sportbilly 1.4.2.18 public void append(BracketList bl) {
361 sportbilly 1.4.2.18 if (bl.first!=null) {
362 sportbilly 1.4.2.18 if (first==null) {
363 sportbilly 1.4.2.18 first=bl.first;
364 sportbilly 1.4.2.18 } else { // this and that both length > 0.
365 sportbilly 1.4.2.18 last.next = bl.first;
366 sportbilly 1.4.2.18 bl.first.prev=last;
367 cananian 1.4.2.4 }
368 sportbilly 1.4.2.18 last = bl.last;
369 cananian 1.1 }
370 sportbilly 1.4.2.18 size += bl.size;
371 sportbilly 1.4.2.18 // invalidate the source bracket-list.
372 sportbilly 1.4.2.18 bl.first=bl.last=null; bl.size=0;
373 sportbilly 1.4.2.18 }
374 sportbilly 1.4.2.18 public String toString() {
375 sportbilly 1.4.2.18 StringBuffer sb=new StringBuffer();
376 sportbilly 1.4.2.18 sb.append(size);
377 sportbilly 1.4.2.18 sb.append(": { ");
378 sportbilly 1.4.2.18 for (EdgeDList el=first; el!=null; el=el.next) {
379 sportbilly 1.4.2.18 sb.append(el.e);
380 sportbilly 1.4.2.18 if (el.next!=null)
381 sportbilly 1.4.2.18 sb.append(", ");
382 cananian 1.1 }
383 sportbilly 1.4.2.18 sb.append(" }");
384 sportbilly 1.4.2.18 return sb.toString();
385 cananian 1.1 }
386 sportbilly 1.4.2.18 } /* end class BracketList */
387 sportbilly 1.4.2.18 } /* end class Graph */
388 cananian 1.1 }