001: /*
002: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
003: *
004: * Copyright 1997-2007 Sun Microsystems, Inc. All rights reserved.
005: *
006: * The contents of this file are subject to the terms of either the GNU
007: * General Public License Version 2 only ("GPL") or the Common
008: * Development and Distribution License("CDDL") (collectively, the
009: * "License"). You may not use this file except in compliance with the
010: * License. You can obtain a copy of the License at
011: * http://www.netbeans.org/cddl-gplv2.html
012: * or nbbuild/licenses/CDDL-GPL-2-CP. See the License for the
013: * specific language governing permissions and limitations under the
014: * License. When distributing the software, include this License Header
015: * Notice in each file and include the License file at
016: * nbbuild/licenses/CDDL-GPL-2-CP. Sun designates this
017: * particular file as subject to the "Classpath" exception as provided
018: * by Sun in the GPL Version 2 section of the License file that
019: * accompanied this code. If applicable, add the following below the
020: * License Header, with the fields enclosed by brackets [] replaced by
021: * your own identifying information:
022: * "Portions Copyrighted [year] [name of copyright owner]"
023: *
024: * Contributor(s):
025: *
026: * The Original Software is NetBeans. The Initial Developer of the Original
027: * Software is Sun Microsystems, Inc. Portions Copyright 1997-2006 Sun
028: * Microsystems, Inc. All Rights Reserved.
029: *
030: * If you wish your version of this file to be governed by only the CDDL
031: * or only the GPL Version 2, indicate your decision by adding
032: * "[Contributor] elects to include this software in this distribution
033: * under the [CDDL or GPL Version 2] license." If you do not indicate a
034: * single choice of license, a recipient has the option to distribute
035: * your version of this file under either the CDDL, the GPL Version 2 or
036: * to extend the choice of license to its licensees as provided above.
037: * However, if you add GPL Version 2 code and therefore, elected the GPL
038: * Version 2 license, then the option applies only if the new code is
039: * made subject to such option by the copyright holder.
040: */
041:
042: package org.netbeans.modules.languages.parser;
043:
044: import java.util.*;
045:
046: /**
047: *
048: * @author Jan Jancura
049: */
050: public class DGUtils {
051:
052: public static <N, E, K, V> DG<N, E, K, V> cloneDG(
053: DG<N, E, K, V> dg, boolean cloneProperties,
054: NodeFactory<N> nodeFactory) {
055: DG<N, E, K, V> ndg = DG.<N, E, K, V> createDG();
056: Map<N, N> oldToNew = new HashMap<N, N>();
057: Iterator<N> it = dg.getNodes().iterator();
058: while (it.hasNext()) {
059: N oldNode = it.next();
060: N newNode = oldToNew.get(oldNode);
061: if (newNode == null) {
062: newNode = nodeFactory.createNode();
063: ndg.addNode(newNode);
064: oldToNew.put(oldNode, newNode);
065: if (cloneProperties)
066: ndg.putAllProperties(newNode, dg
067: .getProperties(oldNode));
068: }
069: Iterator<E> it2 = dg.getEdges(oldNode).iterator();
070: while (it2.hasNext()) {
071: E edge = it2.next();
072: N oldEnd = dg.getNode(oldNode, edge);
073: N newEnd = oldToNew.get(oldEnd);
074: if (newEnd == null) {
075: newEnd = nodeFactory.createNode();
076: ndg.addNode(newEnd);
077: oldToNew.put(oldEnd, newEnd);
078: if (cloneProperties)
079: ndg.putAllProperties(newEnd, dg
080: .getProperties(oldEnd));
081: }
082: ndg.addEdge(newNode, newEnd, edge);
083: if (cloneProperties)
084: ndg.putAllProperties(newNode, edge, dg
085: .getProperties(oldNode, edge));
086: }
087: if (dg.getEnds().contains(oldNode))
088: ndg.addEnd(newNode);
089: }
090: N newStart = oldToNew.get(dg.getStartNode());
091: ndg.setStart(newStart);
092: return ndg;
093: }
094:
095: public static <N, E, K, V> DG<N, E, K, V> append(
096: DG<N, E, K, V> dg1, DG<N, E, K, V> dg2, E star,
097: NodeFactory<N> nodeFactory) {
098: DG<N, E, K, V> ndg = DG.<N, E, K, V> createDG();
099: Set<N> newStart = new HashSet<N>();
100: newStart.add(dg1.getStartNode());
101: if (dg1.getEnds().contains(dg1.getStartNode()))
102: newStart.add(dg2.getStartNode());
103: Map<Set<N>, N> newToOld = new HashMap<Set<N>, N>();
104: merge(dg1, dg2, newStart, ndg, newToOld, dg1.getEnds(), dg2
105: .getStartNode(), false, true, star, nodeFactory);
106: N nnn = newToOld.get(newStart);
107: ndg.setStart(nnn);
108: return ndg;
109: }
110:
111: public static <N, E, K, V> DG<N, E, K, V> plus(DG<N, E, K, V> dg,
112: E star, NodeFactory<N> nodeFactory) {
113: DG<N, E, K, V> ndg = DG.<N, E, K, V> createDG();
114: N what = dg.getStartNode();
115: Set<N> where = dg.getEnds();
116: Set<N> nn = new HashSet<N>();
117: nn.add(dg.getStartNode());
118: if (where.contains(dg.getStartNode()))
119: nn.add(what);
120: Map<Set<N>, N> newToOld = new HashMap<Set<N>, N>();
121: merge(dg, dg, nn, ndg, newToOld, where, what, true, true, star,
122: nodeFactory);
123: N nnn = newToOld.get(nn);
124: ndg.setStart(nnn);
125: return ndg;
126: }
127:
128: private static <N, E, K, V> void merge(DG<N, E, K, V> dg1,
129: DG<N, E, K, V> dg2, Set<N> nn, DG<N, E, K, V> ndg,
130: Map<Set<N>, N> newToOld, Set<N> where, N what,
131: boolean setEnds1, boolean setEnds2, E star,
132: NodeFactory<N> nodeFactory) {
133: N nnn = newToOld.get(nn);
134: if (nnn != null)
135: return;
136: nnn = nodeFactory.createNode();
137: newToOld.put(nn, nnn);
138: ndg.addNode(nnn);
139:
140: Map<E, Set<N>> edges = new HashMap<E, Set<N>>();
141: Map<E, Map<K, V>> properties = new HashMap<E, Map<K, V>>();
142: Iterator<N> it = nn.iterator();
143: while (it.hasNext()) {
144: N n = it.next();
145: DG<N, E, K, V> cdg = dg1.containsNode(n) ? dg1 : dg2;
146: ndg.putAllProperties(nnn, cdg.getProperties(n));
147: if (setEnds1 && dg1.getEnds().contains(n))
148: ndg.addEnd(nnn);
149: if (setEnds2 && dg2.getEnds().contains(n))
150: ndg.addEnd(nnn);
151: Iterator<E> it2 = cdg.getEdges(n).iterator();
152: while (it2.hasNext()) {
153: E edge = it2.next();
154: Set<N> ends = edges.get(edge);
155: Map<K, V> props = properties.get(edge);
156: if (ends == null) {
157: ends = new HashSet<N>();
158: props = new HashMap<K, V>();
159: edges.put(edge, ends);
160: properties.put(edge, props);
161: }
162: N en = cdg.getNode(n, edge);
163: ends.add(en);
164: props.putAll(cdg.getProperties(n, edge));
165: if (where.contains(en))
166: ends.add(what);
167: }
168: }
169: it = nn.iterator();
170: while (it.hasNext()) {
171: N n = it.next();
172: DG<N, E, K, V> cdg = dg1.containsNode(n) ? dg1 : dg2;
173: N en = cdg.getNode(n, star);
174: if (en == null)
175: continue;
176: Iterator<E> it2 = edges.keySet().iterator();
177: while (it2.hasNext()) {
178: E e = it2.next();
179: if (cdg.getNode(n, e) != null)
180: continue;
181: edges.get(e).add(en);
182: properties.get(e).putAll(cdg.getProperties(n, e));
183: if (where.contains(en))
184: edges.get(e).add(what);
185: }
186: }
187:
188: Iterator<E> it2 = edges.keySet().iterator();
189: while (it2.hasNext()) {
190: E edge = it2.next();
191: Set<N> en = edges.get(edge);
192: merge(dg1, dg2, en, ndg, newToOld, where, what, setEnds1,
193: setEnds2, star, nodeFactory);
194: N enn = newToOld.get(en);
195: ndg.addEdge(nnn, enn, edge);
196: ndg.putAllProperties(nnn, edge, properties.get(edge));
197: }
198: }
199:
200: public static <N, E, K, V> DG<N, E, K, V> merge(DG<N, E, K, V> dg1,
201: DG<N, E, K, V> dg2, E star, NodeFactory<N> nodeFactory) {
202: DG<N, E, K, V> ndg = DG.<N, E, K, V> createDG();
203: Map<Set<N>, N> newToOld = new HashMap<Set<N>, N>();
204: N startNode = merge(dg1, dg2, dg1.getStartNode(), dg2
205: .getStartNode(), ndg, true, true, star, nodeFactory,
206: newToOld, 1);
207: ndg.setStart(startNode);
208: return ndg;
209: }
210:
211: private static <N, E, K, V> N merge(DG<N, E, K, V> dg1,
212: DG<N, E, K, V> dg2, N n1, N n2, DG<N, E, K, V> ndg,
213: boolean addEnds1, boolean addEnds2, E star,
214: NodeFactory<N> nodeFactory, Map<Set<N>, N> newToOld,
215: int depth) {
216: Set<N> nNode = new HashSet<N>();
217: nNode.add(n1);
218: nNode.add(n2);
219: if (newToOld.containsKey(nNode))
220: return newToOld.get(nNode);
221: N dnode = nodeFactory.createNode();
222: newToOld.put(nNode, dnode);
223: ndg.addNode(dnode);
224: ndg.putAllProperties(dnode, dg1.getProperties(n1));
225: ndg.putAllProperties(dnode, dg2.getProperties(n2));
226: if (addEnds1 && dg1.getEnds().contains(n1))
227: ndg.addEnd(dnode);
228: if (addEnds2 && dg2.getEnds().contains(n2))
229: ndg.addEnd(dnode);
230:
231: Set<E> edges2 = new HashSet<E>(dg2.getEdges(n2));
232: Iterator<E> it = dg1.getEdges(n1).iterator();
233: while (it.hasNext()) {
234: E edge = it.next();
235: N nn1 = dg1.getNode(n1, edge);
236: N nn2 = dg2.getNode(n2, edge);
237: Map<K, V> properties = null;
238: if (!edge.equals(star) && edges2.contains(star)
239: && nn2 == null) {
240: nn2 = dg2.getNode(n2, star);
241: properties = dg2.getProperties(n2, star);
242: } else if (nn2 != null)
243: properties = dg2.getProperties(n2, edge);
244: N nnode = nn2 == null ? merge(dg1, nn1, ndg, addEnds1)
245: : merge(dg1, dg2, nn1, nn2, ndg, addEnds1,
246: addEnds2, star, nodeFactory, newToOld,
247: depth + 1);
248: ndg.addEdge(dnode, nnode, edge);
249: ndg.putAllProperties(dnode, edge, dg1.getProperties(n1,
250: edge));
251: if (properties != null)
252: ndg.putAllProperties(dnode, edge, properties);
253: edges2.remove(edge);
254: }
255: it = edges2.iterator();
256: while (it.hasNext()) {
257: E edge = it.next();
258: N nn2 = dg2.getNode(n2, edge);
259: N nnode = null;
260: Map<K, V> properties = null;
261: if (!edge.equals(star) && dg1.getEdges(n1).contains(star)) {
262: nnode = merge(dg1, dg2, dg1.getNode(n1, star), nn2,
263: ndg, addEnds1, addEnds2, star, nodeFactory,
264: newToOld, depth + 1);
265: properties = dg1.getProperties(n1, star);
266: } else
267: nnode = merge(dg2, nn2, ndg, addEnds2);
268: ndg.addEdge(dnode, nnode, edge);
269: ndg.putAllProperties(dnode, edge, dg2.getProperties(n2,
270: edge));
271: if (properties != null)
272: ndg.putAllProperties(dnode, edge, properties);
273: }
274: return dnode;
275: }
276:
277: private static <N, E, K, V> N merge(DG<N, E, K, V> dg, N n,
278: DG<N, E, K, V> ndg, boolean addEnds) {
279: if (ndg.containsNode(n))
280: return n;
281: ndg.addNode(n);
282: ndg.putAllProperties(n, dg.getProperties(n));
283: if (addEnds && dg.getEnds().contains(n))
284: ndg.addEnd(n);
285:
286: Iterator<E> it = dg.getEdges(n).iterator();
287: while (it.hasNext()) {
288: E edge = it.next();
289: N nn = dg.getNode(n, edge);
290: N endN = merge(dg, nn, ndg, addEnds);
291: ndg.addEdge(n, endN, edge);
292: ndg.putAllProperties(n, edge, dg.getProperties(n, edge));
293: }
294: return n;
295: }
296:
297: static <N, E, K, V> DG<N, E, K, V> reduce(DG<N, E, K, V> dg,
298: NodeFactory<N> nodeFactory) {
299: Map<Map<K, V>, Set<N>> ends = new HashMap<Map<K, V>, Set<N>>();
300: Set<N> other = new HashSet<N>();
301: Iterator<N> it = dg.getNodes().iterator();
302: while (it.hasNext()) {
303: N node = it.next();
304: if (!dg.getEnds().contains(node))
305: other.add(node);
306: else {
307: Set<N> e = ends.get(dg.getProperties(node));
308: if (e == null) {
309: e = new HashSet<N>();
310: ends.put(dg.getProperties(node), e);
311: }
312: e.add(node);
313: }
314: }
315: Set<Set<N>> newNodes = new HashSet<Set<N>>();
316: if (other.size() > 0)
317: newNodes.add(other);
318: newNodes.addAll(ends.values());
319: Map<Set<N>, Map<E, Set<N>>> ng = reduce(dg, newNodes);
320:
321: DG<N, E, K, V> ndg = DG.<N, E, K, V> createDG();
322: Map<Set<N>, N> oldToNewNode = new HashMap<Set<N>, N>();
323: Iterator<Set<N>> it2 = ng.keySet().iterator();
324: while (it2.hasNext()) {
325: Set<N> node = it2.next();
326: N newNode = oldToNewNode.get(node);
327: if (newNode == null) {
328: newNode = nodeFactory.createNode();
329: oldToNewNode.put(node, newNode);
330: ndg.addNode(newNode);
331: }
332: Map<E, Set<N>> edgeToNode = ng.get(node);
333: Iterator<E> it3 = edgeToNode.keySet().iterator();
334: while (it3.hasNext()) {
335: E edge = it3.next();
336: Set<N> end = edgeToNode.get(edge);
337: N newNode2 = oldToNewNode.get(end);
338: if (newNode2 == null) {
339: newNode2 = nodeFactory.createNode();
340: oldToNewNode.put(end, newNode2);
341: ndg.addNode(newNode2);
342: }
343: ndg.addEdge(newNode, newNode2, edge);
344: }
345: }
346: ndg.setEnds(new HashSet<N>());
347: it2 = ng.keySet().iterator();
348: while (it2.hasNext()) {
349: Set<N> node = it2.next();
350: N newNode = oldToNewNode.get(node);
351: Iterator<N> it3 = node.iterator();
352: while (it3.hasNext()) {
353: N n = it3.next();
354: if (dg.containsNode(n) && dg.getProperties(n) != null)
355: ndg.putAllProperties(newNode, dg.getProperties(n));
356: Iterator<E> it4 = ndg.getEdges(newNode).iterator();
357: while (it4.hasNext()) {
358: E edge = it4.next();
359: if (dg.containsNode(n)
360: && dg.getProperties(n, edge) != null)
361: ndg.putAllProperties(newNode, edge, dg
362: .getProperties(n, edge));
363: }
364: if (dg.getEnds().contains(n))
365: ndg.addEnd(newNode);
366: if (dg.getStartNode().equals(n))
367: ndg.setStart(newNode);
368: }
369: }
370: return ndg;
371: }
372:
373: private static <N, E, K, V> Map<Set<N>, Map<E, Set<N>>> reduce(
374: DG<N, E, K, V> dg, Set<Set<N>> s) {
375: Map<N, Set<N>> m = new HashMap<N, Set<N>>();
376: Iterator<Set<N>> it = s.iterator();
377: while (it.hasNext()) {
378: Set<N> nnode = it.next();
379: Iterator<N> it2 = nnode.iterator();
380: while (it2.hasNext()) {
381: N node = it2.next();
382: m.put(node, nnode);
383: }
384: }
385:
386: Map<Set<N>, Map<E, Set<N>>> nnodes = new HashMap<Set<N>, Map<E, Set<N>>>();
387: it = s.iterator();
388: while (it.hasNext()) {
389: Set<N> nnode = it.next();
390: Map<Map<E, Set<N>>, Set<N>> nodes = new HashMap<Map<E, Set<N>>, Set<N>>();
391: Iterator<N> it2 = nnode.iterator();
392: while (it2.hasNext()) {
393: N node = it2.next();
394: Map<E, Set<N>> edges = new HashMap<E, Set<N>>();
395: Iterator<E> it3 = dg.getEdges(node).iterator();
396: while (it3.hasNext()) {
397: E edge = it3.next();
398: N endNode = dg.getNode(node, edge);
399: edges.put(edge, m.get(endNode));
400: }
401: Set<N> n = nodes.get(edges);
402: if (n == null) {
403: n = new HashSet<N>();
404: nodes.put(edges, n);
405: }
406: n.add(node);
407: }
408: Iterator<Map<E, Set<N>>> it3 = nodes.keySet().iterator();
409: while (it3.hasNext()) {
410: Map<E, Set<N>> edges = it3.next();
411: Set<N> newState = nodes.get(edges);
412: nnodes.put(newState, edges);
413: }
414: }
415: if (nnodes.size() > s.size())
416: return reduce(dg, nnodes.keySet());
417: return nnodes;
418: }
419: }
|