Java > Open Source Codes > org > netbeans > modules > languages > parser > DGUtils


1 /*
2  * The contents of this file are subject to the terms of the Common Development
3  * and Distribution License (the License). You may not use this file except in
4  * compliance with the License.
5  *
6  * You can obtain a copy of the License at http://www.netbeans.org/cddl.html
7  * or http://www.netbeans.org/cddl.txt.
8  *
9  * When distributing Covered Code, include this CDDL Header Notice in each file
10  * and include the License file at http://www.netbeans.org/cddl.txt.
11  * If applicable, add the following below the CDDL Header, with the fields
12  * enclosed by brackets [] replaced by your own identifying information:
13  * "Portions Copyrighted [year] [name of copyright owner]"
14  *
15  * The Original Software is NetBeans. The Initial Developer of the Original
16  * Software is Sun Microsystems, Inc. Portions Copyright 1997-2006 Sun
17  * Microsystems, Inc. All Rights Reserved.
18  */
19
20 package org.netbeans.modules.languages.parser;
21
22 import java.util.*;
23
24 /**
25  *
26  * @author Jan Jancura
27  */
28 public class DGUtils {
29
30
31     public static <N,E,K,V> DG<N,E,K,V> cloneDG (DG<N,E,K,V> dg, boolean cloneProperties, NodeFactory<N> nodeFactory) {
32         DG<N,E,K,V> ndg = DG.<N,E,K,V>createDG ();
33         Map<N,N> oldToNew = new HashMap<N,N> ();
34         Iterator<N> it = dg.getNodes ().iterator ();
35         while (it.hasNext ()) {
36             N oldNode = it.next ();
37             N newNode = oldToNew.get (oldNode);
38             if (newNode == null) {
39                 newNode = nodeFactory.createNode ();
40                 ndg.addNode (newNode);
41                 oldToNew.put (oldNode, newNode);
42                 if (cloneProperties)
43                     ndg.putAllProperties (newNode, dg.getProperties (oldNode));
44             }
45             Iterator<E> it2 = dg.getEdges (oldNode).iterator ();
46             while (it2.hasNext ()) {
47                 E edge = it2.next ();
48                 N oldEnd = dg.getNode (oldNode, edge);
49                 N newEnd = oldToNew.get (oldEnd);
50                 if (newEnd == null) {
51                     newEnd = nodeFactory.createNode ();
52                     ndg.addNode (newEnd);
53                     oldToNew.put (oldEnd, newEnd);
54                     if (cloneProperties)
55                         ndg.putAllProperties (newEnd, dg.getProperties (oldEnd));
56                 }
57                 ndg.addEdge (newNode, newEnd, edge);
58                 if (cloneProperties)
59                     ndg.putAllProperties (newNode, edge, dg.getProperties (oldNode, edge));
60             }
61             if (dg.getEnds ().contains (oldNode))
62                 ndg.addEnd (newNode);
63         }
64         N newStart = oldToNew.get (dg.getStartNode ());
65         ndg.setStart (newStart);
66         return ndg;
67     }
68     
69     
70     public static <N,E,K,V> DG<N,E,K,V> append (DG<N,E,K,V> dg1, DG<N,E,K,V> dg2, E star, NodeFactory<N> nodeFactory) {
71         DG<N,E,K,V> ndg = DG.<N,E,K,V>createDG ();
72         Set<N> newStart = new HashSet<N> ();
73         newStart.add (dg1.getStartNode ());
74         if (dg1.getEnds ().contains (dg1.getStartNode ()))
75             newStart.add (dg2.getStartNode ());
76         Map<Set<N>,N> newToOld = new HashMap<Set<N>,N> ();
77         merge (dg1, dg2, newStart, ndg, newToOld, dg1.getEnds (), dg2.getStartNode (), false, true, star, nodeFactory);
78         N nnn = newToOld.get (newStart);
79         ndg.setStart (nnn);
80         return ndg;
81     }
82     
83     public static <N,E,K,V> DG<N,E,K,V> plus (DG<N,E,K,V> dg, E star, NodeFactory<N> nodeFactory) {
84         DG<N,E,K,V> ndg = DG.<N,E,K,V>createDG ();
85         N what = dg.getStartNode ();
86         Set<N> where = dg.getEnds ();
87         Set<N> nn = new HashSet<N> ();
88         nn.add (dg.getStartNode ());
89         if (where.contains (dg.getStartNode ()))
90             nn.add (what);
91         Map<Set<N>,N> newToOld = new HashMap<Set<N>,N> ();
92         merge (dg, dg, nn, ndg, newToOld, where, what, true, true, star, nodeFactory);
93         N nnn = newToOld.get (nn);
94         ndg.setStart (nnn);
95         return ndg;
96     }
97     
98     private static <N,E,K,V> void merge (
99         DG<N,E,K,V> dg1,
100         DG<N,E,K,V> dg2,
101         Set<N> nn,
102         DG<N,E,K,V> ndg,
103         Map<Set<N>,N> newToOld,
104         Set<N> where,
105         N what,
106         boolean setEnds1,
107         boolean setEnds2,
108         E star,
109         NodeFactory<N> nodeFactory
110     ) {
111         N nnn = newToOld.get (nn);
112         if (nnn != null) return;
113         nnn = nodeFactory.createNode ();
114         newToOld.put (nn, nnn);
115         ndg.addNode (nnn);
116
117         Map<E,Set<N>> edges = new HashMap<E,Set<N>> ();
118         Map<E,Map<K,V>> properties = new HashMap<E,Map<K,V>> ();
119         Iterator<N> it = nn.iterator ();
120         while (it.hasNext ()) {
121             N n = it.next ();
122             DG<N,E,K,V> cdg = dg1.containsNode (n) ? dg1 : dg2;
123             ndg.putAllProperties (nnn, cdg.getProperties (n));
124             if (setEnds1 && dg1.getEnds ().contains (n))
125                 ndg.addEnd (nnn);
126             if (setEnds2 && dg2.getEnds ().contains (n))
127                 ndg.addEnd (nnn);
128             Iterator<E> it2 = cdg.getEdges (n).iterator ();
129             while (it2.hasNext ()) {
130                 E edge = it2.next ();
131                 Set<N> ends = edges.get (edge);
132                 Map<K,V> props = properties.get (edge);
133                 if (ends == null) {
134                     ends = new HashSet<N> ();
135                     props = new HashMap<K,V> ();
136                     edges.put (edge, ends);
137                     properties.put (edge, props);
138                 }
139                 N en = cdg.getNode (n, edge);
140                 ends.add (en);
141                 props.putAll (cdg.getProperties (n, edge));
142                 if (where.contains (en))
143                     ends.add (what);
144             }
145         }
146         it = nn.iterator ();
147         while (it.hasNext ()) {
148             N n = it.next ();
149             DG<N,E,K,V> cdg = dg1.containsNode (n) ? dg1 : dg2;
150             N en = cdg.getNode (n, star);
151             if (en == null) continue;
152             Iterator<E> it2 = edges.keySet ().iterator ();
153             while (it2.hasNext ()) {
154                 E e = it2.next ();
155                 if (cdg.getNode (n, e) != null) continue;
156                 edges.get (e).add (en);
157                 properties.get (e).putAll (cdg.getProperties (n, e));
158                 if (where.contains (en))
159                     edges.get (e).add (what);
160             }
161         }
162         
163         Iterator<E> it2 = edges.keySet ().iterator ();
164         while (it2.hasNext ()) {
165             E edge = it2.next ();
166             Set<N> en = edges.get (edge);
167             merge (dg1, dg2, en, ndg, newToOld, where, what, setEnds1, setEnds2, star, nodeFactory);
168             N enn = newToOld.get (en);
169             ndg.addEdge (nnn, enn, edge);
170             ndg.putAllProperties (nnn, edge, properties.get (edge));
171         }
172     }
173     
174     public static <N,E,K,V> DG<N,E,K,V> merge (DG<N,E,K,V> dg1, DG<N,E,K,V> dg2, E star, NodeFactory<N> nodeFactory) {
175         DG<N,E,K,V> ndg = DG.<N,E,K,V>createDG ();
176         Map<Set<N>,N> newToOld = new HashMap<Set<N>,N> ();
177         N startNode = merge (
178             dg1, dg2,
179             dg1.getStartNode (),
180             dg2.getStartNode (),
181             ndg,
182             true, true,
183             star,
184             nodeFactory,
185             newToOld,
186             1
187         );
188         ndg.setStart (startNode);
189         return ndg;
190     }
191     
192     private static <N,E,K,V> N merge (
193         DG<N,E,K,V> dg1,
194         DG<N,E,K,V> dg2,
195         N n1,
196         N n2,
197         DG<N,E,K,V> ndg,
198         boolean addEnds1,
199         boolean addEnds2,
200         E star,
201         NodeFactory<N> nodeFactory,
202         Map<Set<N>,N> newToOld,
203         int depth
204     ) {
205         if (depth == 100)
206             System.out.println("sto");
207         Set<N> nNode = new HashSet<N> ();
208         nNode.add (n1);
209         nNode.add (n2);
210         if (newToOld.containsKey (nNode))
211             return newToOld.get (nNode);
212         N dnode = nodeFactory.createNode ();
213         newToOld.put (nNode, dnode);
214         ndg.addNode (dnode);
215         ndg.putAllProperties (dnode, dg1.getProperties (n1));
216         ndg.putAllProperties (dnode, dg2.getProperties (n2));
217         if (addEnds1 && dg1.getEnds ().contains (n1))
218             ndg.addEnd (dnode);
219         if (addEnds2 && dg2.getEnds ().contains (n2))
220             ndg.addEnd (dnode);
221         
222         Set<E> edges2 = new HashSet<E> (dg2.getEdges (n2));
223         Iterator<E> it = dg1.getEdges (n1).iterator ();
224         while (it.hasNext ()) {
225             E edge = it.next ();
226             N nn1 = dg1.getNode (n1, edge);
227             N nn2 = dg2.getNode (n2, edge);
228             Map<K,V> properties = null;
229             if ( !edge.equals (star) &&
230                  edges2.contains (star) &&
231                  nn2 == null
232             ) {
233                 nn2 = dg2.getNode (n2, star);
234                 properties = dg2.getProperties (n2, star);
235             } else
236             if (nn2 != null)
237                 properties = dg2.getProperties (n2, edge);
238             N nnode = nn2 == null ?
239                 merge (dg1, nn1, ndg, addEnds1) :
240                 merge (dg1, dg2, nn1, nn2, ndg, addEnds1, addEnds2, star, nodeFactory, newToOld, depth + 1);
241             ndg.addEdge (dnode, nnode, edge);
242             ndg.putAllProperties (dnode, edge, dg1.getProperties (n1, edge));
243             if (properties != null)
244                 ndg.putAllProperties (dnode, edge, properties);
245             edges2.remove (edge);
246         }
247         it = edges2.iterator ();
248         while (it.hasNext ()) {
249             E edge = it.next ();
250             N nn2 = dg2.getNode (n2, edge);
251             N nnode = null;
252             Map<K,V> properties = null;
253             if ( !edge.equals (star) &&
254                  dg1.getEdges (n1).contains (star)
255             ) {
256                 nnode = merge (dg1, dg2, dg1.getNode (n1, star), nn2, ndg, addEnds1, addEnds2, star, nodeFactory, newToOld, depth + 1);
257                 properties = dg1.getProperties (n1, star);
258             } else
259                 nnode = merge (dg2, nn2, ndg, addEnds2);
260             ndg.addEdge (dnode, nnode, edge);
261             ndg.putAllProperties (dnode, edge, dg2.getProperties (n2, edge));
262             if (properties != null)
263                 ndg.putAllProperties (dnode, edge, properties);
264         }
265         return dnode;
266     }
267     
268     private static <N,E,K,V> N merge (
269         DG<N,E,K,V> dg,
270         N n,
271         DG<N,E,K,V> ndg,
272         boolean addEnds
273     ) {
274         if (ndg.containsNode (n)) return n;
275         ndg.addNode (n);
276         ndg.putAllProperties (n, dg.getProperties (n));
277         if (addEnds && dg.getEnds ().contains (n))
278             ndg.addEnd (n);
279         
280         Iterator<E> it = dg.getEdges (n).iterator ();
281         while (it.hasNext ()) {
282             E edge = it.next ();
283             N nn = dg.getNode (n, edge);
284             N endN = merge (dg, nn, ndg, addEnds);
285             ndg.addEdge (n, endN, edge);
286             ndg.putAllProperties (n, edge, dg.getProperties (n, edge));
287         }
288         return n;
289     }
290     
291     static <N,E,K,V> DG<N,E,K,V> reduce (DG<N,E,K,V> dg, NodeFactory<N> nodeFactory) {
292         Map<Map<K,V>,Set<N>> ends = new HashMap<Map<K,V>,Set<N>> ();
293         Set<N> other = new HashSet<N> ();
294         Iterator<N> it = dg.getNodes ().iterator ();
295         while (it.hasNext ()) {
296             N node = it.next ();
297             if (!dg.getEnds ().contains (node))
298                 other.add (node);
299             else {
300                 Set<N> e = ends.get (dg.getProperties (node));
301                 if (e == null) {
302                     e = new HashSet<N> ();
303                     ends.put (dg.getProperties (node), e);
304                 }
305                 e.add (node);
306             }
307         }
308         Set<Set<N>> newNodes = new HashSet<Set<N>> ();
309         if (other.size () > 0) newNodes.add (other);
310         newNodes.addAll (ends.values ());
311         Map<Set<N>,Map<E,Set<N>>> ng = reduce (dg, newNodes);
312
313         DG<N,E,K,V> ndg = DG.<N,E,K,V>createDG ();
314         Map<Set<N>,N> oldToNewNode = new HashMap<Set<N>,N> ();
315         Iterator<Set<N>> it2 = ng.keySet ().iterator ();
316         while (it2.hasNext ()) {
317             Set<N> node = it2.next ();
318             N newNode = oldToNewNode.get (node);
319             if (newNode == null) {
320                 newNode = nodeFactory.createNode ();
321                 oldToNewNode.put (node, newNode);
322                 ndg.addNode (newNode);
323             }
324             Map<E,Set<N>> edgeToNode = ng.get (node);
325             Iterator<E> it3 = edgeToNode.keySet ().iterator ();
326             while (it3.hasNext ()) {
327                 E edge = it3.next ();
328                 Set<N> end = edgeToNode.get (edge);
329                 N newNode2 = oldToNewNode.get (end);
330                 if (newNode2 == null) {
331                     newNode2 = nodeFactory.createNode ();
332                     oldToNewNode.put (end, newNode2);
333                     ndg.addNode (newNode2);
334                 }
335                 ndg.addEdge (newNode, newNode2, edge);
336             }
337         }
338         ndg.setEnds (new HashSet<N> ());
339         it2 = ng.keySet ().iterator ();
340         while (it2.hasNext ()) {
341             Set<N> node = it2.next ();
342             N newNode = oldToNewNode.get (node);
343             Iterator<N> it3 = node.iterator ();
344             while (it3.hasNext ()) {
345                 N n = it3.next ();
346                 if (dg.containsNode (n) && dg.getProperties (n) != null)
347                     ndg.putAllProperties (newNode, dg.getProperties (n));
348                 Iterator<E> it4 = ndg.getEdges (newNode).iterator ();
349                 while (it4.hasNext ()) {
350                     E edge = it4.next ();
351                     if (dg.containsNode (n) && dg.getProperties (n, edge) != null)
352                         ndg.putAllProperties (newNode, edge, dg.getProperties (n, edge));
353                 }
354                 if (dg.getEnds ().contains (n))
355                     ndg.addEnd (newNode);
356                 if (dg.getStartNode ().equals (n))
357                     ndg.setStart (newNode);
358             }
359         }
360         return ndg;
361     }
362     
363     private static <N,E,K,V> Map<Set<N>,Map<E,Set<N>>> reduce (DG<N,E,K,V> dg, Set<Set<N>> s) {
364         Map<N,Set<N>> m = new HashMap<N,Set<N>> ();
365         Iterator<Set<N>> it = s.iterator ();
366         while (it.hasNext ()) {
367             Set<N> nnode = it.next ();
368             Iterator<N> it2 = nnode.iterator ();
369             while (it2.hasNext ()) {
370                 N node = it2.next ();
371                 m.put (node, nnode);
372             }
373         }
374         
375         Map<Set<N>,Map<E,Set<N>>> nnodes = new HashMap<Set<N>,Map<E,Set<N>>> ();
376         it = s.iterator ();
377         while (it.hasNext ()) {
378             Set<N> nnode = it.next ();
379             Map<Map<E,Set<N>>,Set<N>> nodes = new HashMap<Map<E,Set<N>>,Set<N>> ();
380             Iterator<N> it2 = nnode.iterator ();
381             while (it2.hasNext ()) {
382                 N node = it2.next ();
383                 Map<E,Set<N>> edges = new HashMap<E,Set<N>> ();
384                 Iterator<E> it3 = dg.getEdges (node).iterator ();
385                 while (it3.hasNext ()) {
386                     E edge = it3.next ();
387                     N endNode = dg.getNode (node, edge);
388                     edges.put (edge, m.get (endNode));
389                 }
390                 Set<N> n = nodes.get (edges);
391                 if (n == null) {
392                     n = new HashSet<N> ();
393                     nodes.put (edges, n);
394                 }
395                 n.add (node);
396             }
397             Iterator<Map<E,Set<N>>> it3 = nodes.keySet ().iterator ();
398             while (it3.hasNext ()) {
399                 Map<E,Set<N>> edges = it3.next ();
400                 Set<N> newState = nodes.get (edges);
401                 nnodes.put (newState, edges);
402             }
403         }
404         if (nnodes.size () > s.size ())
405             return reduce (dg, nnodes.keySet ());
406         return nnodes;
407     }
408   
409 // wrong: a*a
410 // static DG append (DG dg1, DG dg2) {
411 // DG ndg = dg1.cloneDG ();
412 //
413 // Iterator it = dg2.getNodes ().iterator ();
414 // while (it.hasNext ()) {
415 // Object node = it.next ();
416 // if (!ndg.containsNode (node)) {
417 // ndg.addNode (node);
418 // ndg.putAllProperties (node, dg2.getProperties (node));
419 // }
420 // Iterator it2 = dg2.getEdges (node).iterator ();
421 // while (it2.hasNext ()) {
422 // Object edge = it2.next ();
423 // Object endN = dg2.getNode (node, edge);
424 // if (!ndg.containsNode (endN)) {
425 // ndg.addNode (endN);
426 // ndg.putAllProperties (endN, dg2.getProperties (endN));
427 // }
428 // ndg.addEdge (node, endN, edge);
429 // ndg.putAllProperties (node, edge, dg2.getProperties (node, edge));
430 // }
431 // }
432 //
433 // Set oldEnds = ndg.getEnds ();
434 // ndg.setEnds (dg2.getEnds ());
435 //
436 // it = oldEnds.iterator ();
437 // while (it.hasNext ()) {
438 // Object n = it.next ();
439 // append (ndg, n, dg2.getStartNode ());
440 // }
441 // it = ndg.getNodes ().iterator ();
442 // while (it.hasNext ()) {
443 // Object node = it.next ();
444 // if ( node instanceof DNode &&
445 // dg2.getEnds ().contains (((DNode) node).n2)
446 // )
447 // ndg.addEnd (node);
448 // }
449 // return reduce (ndg);
450 // }
451 //
452 // private static void append (DG dg, Object n1, Object n2) {
453 // Iterator it = dg.getEdges (n2).iterator ();
454 // while (it.hasNext ()) {
455 // Object edge = it.next ();
456 // Object nn1 = dg.getNode (n1, edge);
457 // Object nn2 = dg.getNode (n2, edge);
458 // if (nn1 != null)
459 // append (dg, nn1, nn2);
460 // else
461 // if (dg.getNode (n1, Pattern.STAR) != null) {
462 // Object en = merge (dg, dg, dg.getNode (n1, Pattern.STAR), nn2, dg);
463 // dg.addEdge (n1, en, edge);
464 // } else
465 // dg.addEdge (n1, nn2, edge);
466 // }
467 // if (dg.getEnds ().contains (n2)) dg.addEnd (n1);
468 // }
469
470 // static DG merge (
471 // DG dg1,
472 // DG dg2,
473 // Object where,
474 // Object what
475 // ) {
476 // try {
477 // // g, ng Map (node > Map (edge > Set (node)))
478 //
479 // // 1) dg1 -> g
480 // Map g = new HashMap ();
481 // Iterator it = dg1.getNodes ().iterator ();
482 // while (it.hasNext ()) {
483 // Object node = it.next ();
484 // Map edgeToNodes = new HashMap ();
485 // g.put (node, edgeToNodes);
486 //
487 // Iterator it2 = dg1.getEdges (node).iterator ();
488 // while (it2.hasNext ()) {
489 // Object edge = it2.next ();
490 // Object end = dg1.getNode (node, edge);
491 // Set ends = new HashSet ();
492 // ends.add (end);
493 // edgeToNodes.put (edge, ends);
494 // }
495 // }
496 //
497 // // 2) dg2 what node to where node in g
498 // Map edgeToNodes = (Map) g.get (where);
499 // it = dg2.getEdges (what).iterator ();
500 // while (it.hasNext ()) {
501 // Object edge = it.next ();
502 // Set ends = (Set) edgeToNodes.get (edge);
503 // if (ends == null) {
504 // ends = new HashSet ();
505 // edgeToNodes.put (edge, ends);
506 // }
507 // Object end = dg2.getNode (what, edge);
508 // if (end == what)
509 // ends.add (where);
510 // else
511 // ends.add (end);
512 // }
513 //
514 // // 3) merge rest of dg2 nodes to g
515 // it = dg2.getNodes ().iterator ();
516 // while (it.hasNext ()) {
517 // Object node = it.next ();
518 // if (node == what) continue;
519 // edgeToNodes = new HashMap ();
520 // g.put (node, edgeToNodes);
521 //
522 // Iterator it2 = dg2.getEdges (node).iterator ();
523 // while (it2.hasNext ()) {
524 // Object edge = it2.next ();
525 // Object end = dg2.getNode (node, edge);
526 // Set ends = new HashSet ();
527 // if (end == what)
528 // ends.add (where);
529 // else
530 // ends.add (end);
531 // edgeToNodes.put (edge, ends);
532 // }
533 // }
534 //
535 // Map ng = new HashMap ();
536 // Set newStart = new HashSet ();
537 // newStart.add (dg1.getStartNode ());
538 // merge (g, newStart, ng);
539 //
540 // DG dg = DG.createDG (newStart);
541 // it = ng.keySet ().iterator ();
542 // while (it.hasNext ()) {
543 // Set node = (Set) it.next ();
544 // if (!dg.containsNode (node))
545 // dg.addNode (node);
546 // Map edgeToNode = (Map) ng.get (node);
547 // Iterator it2 = edgeToNode.keySet ().iterator ();
548 // while (it2.hasNext ()) {
549 // Object edge = it2.next ();
550 // Set end = (Set) edgeToNode.get (edge);
551 // if (!dg.containsNode (end))
552 // dg.addNode (end);
553 // dg.addEdge (node, end, edge);
554 // }
555 // }
556 // dg.setStart (newStart);
557 // dg.setEnds (new HashSet ());
558 // it = dg.getNodes ().iterator ();
559 // while (it.hasNext ()) {
560 // Set node = (Set) it.next ();
561 // Iterator it2 = node.iterator ();
562 // while (it2.hasNext ()) {
563 // Object n = it2.next ();
564 // if (dg1.containsNode (n) && dg1.getProperties (n) != null)
565 // dg.putAllProperties (node, dg1.getProperties (n));
566 // if (dg2.containsNode (n) && dg2.getProperties (n) != null)
567 // dg.putAllProperties (node, dg2.getProperties (n));
568 // Iterator it3 = dg.getEdges (node).iterator ();
569 // while (it3.hasNext ()) {
570 // Object edge = it3.next ();
571 // if (dg1.containsNode (n) && dg1.getProperties (n, edge) != null)
572 // dg.putAllProperties (node, edge, dg1.getProperties (n, edge));
573 // if (dg2.containsNode (n) && dg2.getProperties (n, edge) != null)
574 // dg.putAllProperties (node, edge, dg2.getProperties (n, edge));
575 // if (n == where && dg2.getProperties (what, edge) != null)
576 // dg.putAllProperties (node, edge, dg2.getProperties (what, edge));
577 // }
578 // if (dg1.getEnds ().contains (n) ||
579 // dg2.getEnds ().contains (n)
580 // ) {
581 // dg.addEnd (node);
582 // continue;
583 // }
584 // }
585 // }
586 // return dg;
587 //
588 // } catch (Exception e) {
589 // e.printStackTrace ();
590 // System.out.println("dg1:" + dg1);
591 // System.out.println("dg2:" + dg2);
592 // System.out.println("where:" + where);
593 // return null;
594 // }
595 // }
596
597 // static DG append (
598 // DG dg1,
599 // DG dg2
600 // ) {
601 // System.out.println("append");
602 // System.out.println(dg1);
603 // System.out.println();
604 // System.out.println(dg2);
605 //
606 // try {
607 // // g, ng Map (node > Map (edge > Set (node)))
608 //
609 // // 1) dg1 -> g
610 // Map g = new HashMap ();
611 // Iterator it = dg1.getNodes ().iterator ();
612 // while (it.hasNext ()) {
613 // Object node = it.next ();
614 // Map edgeToNodes = new HashMap ();
615 // g.put (node, edgeToNodes);
616 //
617 // Iterator it2 = dg1.getEdges (node).iterator ();
618 // while (it2.hasNext ()) {
619 // Object edge = it2.next ();
620 // Object end = dg1.getNode (node, edge);
621 // Set ends = new HashSet ();
622 // ends.add (end);
623 // edgeToNodes.put (edge, ends);
624 // }
625 // }
626 //
627 // // 2) dg2 start append to all dg1 ends
628 // it = dg1.getEnds ().iterator ();
629 // while (it.hasNext ()) {
630 // Object end = it.next ();
631 // Map edgeToNodes = (Map) g.get (end);
632 // Iterator it2 = dg2.getEdges (dg2.getStartNode ()).iterator ();
633 // while (it2.hasNext ()) {
634 // Object edge = it2.next ();
635 // Set ends = (Set) edgeToNodes.get (edge);
636 // if (ends == null) {
637 // ends = new HashSet ();
638 // edgeToNodes.put (edge, ends);
639 // }
640 // Object e = dg2.getNode (dg2.getStartNode (), edge);
641 // if (e == dg2.getStartNode ())
642 // ends.add (end);
643 // else
644 // ends.add (e);
645 // }
646 // }
647 //
648 // // 3) merge rest of dg2 nodes to g
649 // it = dg2.getNodes ().iterator ();
650 // while (it.hasNext ()) {
651 // Object node = it.next ();
652 // if (node == dg2.getStartNode ()) continue;
653 // Map edgeToNodes = new HashMap ();
654 // g.put (node, edgeToNodes);
655 //
656 // Iterator it2 = dg2.getEdges (node).iterator ();
657 // while (it2.hasNext ()) {
658 // Object edge = it2.next ();
659 // Object end = dg2.getNode (node, edge);
660 // Set ends = new HashSet ();
661 // if (end == dg2.getStartNode ())
662 // ends.add (dg1.getEnds ().iterator ().next ());
663 // else
664 // ends.add (end);
665 // edgeToNodes.put (edge, ends);
666 // }
667 // }
668 //
669 // Map ng = new HashMap ();
670 // Set newStart = new HashSet ();
671 // newStart.add (dg1.getStartNode ());
672 // merge (g, newStart, ng);
673 //
674 // DG dg = DG.createDG (newStart);
675 // it = ng.keySet ().iterator ();
676 // while (it.hasNext ()) {
677 // Set node = (Set) it.next ();
678 // if (!dg.containsNode (node))
679 // dg.addNode (node);
680 // Map edgeToNode = (Map) ng.get (node);
681 // Iterator it2 = edgeToNode.keySet ().iterator ();
682 // while (it2.hasNext ()) {
683 // Object edge = it2.next ();
684 // Set end = (Set) edgeToNode.get (edge);
685 // if (!dg.containsNode (end))
686 // dg.addNode (end);
687 // dg.addEdge (node, end, edge);
688 // }
689 // }
690 // dg.setStart (newStart);
691 // dg.setEnds (new HashSet ());
692 // it = dg.getNodes ().iterator ();
693 // while (it.hasNext ()) {
694 // Set node = (Set) it.next ();
695 // Iterator it2 = node.iterator ();
696 // while (it2.hasNext ()) {
697 // Object n = it2.next ();
698 // if (dg1.containsNode (n) && dg1.getProperties (n) != null)
699 // dg.putAllProperties (node, dg1.getProperties (n));
700 // if (dg2.containsNode (n) && dg2.getProperties (n) != null)
701 // dg.putAllProperties (node, dg2.getProperties (n));
702 // Iterator it3 = dg.getEdges (node).iterator ();
703 // while (it3.hasNext ()) {
704 // Object edge = it3.next ();
705 // if (dg1.containsNode (n) && dg1.getProperties (n, edge) != null)
706 // dg.putAllProperties (node, edge, dg1.getProperties (n, edge));
707 // if (dg2.containsNode (n) && dg2.getProperties (n, edge) != null)
708 // dg.putAllProperties (node, edge, dg2.getProperties (n, edge));
709 // if (dg1.getEnds ().contains (n) && dg2.getProperties (dg2.getStartNode (), edge) != null)
710 // dg.putAllProperties (node, edge, dg2.getProperties (dg2.getStartNode (), edge));
711 // }
712 //
713 // if (dg2.getEnds ().contains (n)) {
714 // dg.addEnd (node);
715 // continue;
716 // }
717 // if (dg2.getEnds ().contains (dg2.getStartNode ()) &&
718 // dg1.getEnds ().contains (n)
719 // ) {
720 // dg.addEnd (node);
721 // continue;
722 // }
723 // }
724 // }
725 // return reduce (dg);
726 //
727 // } catch (Exception e) {
728 // e.printStackTrace ();
729 // System.out.println("dg1:" + dg1);
730 // System.out.println("dg2:" + dg2);
731 // return null;
732 // }
733 // }
734
735 // static DG star (
736 // DG dg
737 // ) {
738 // try {
739 // // g, ng Map (node > Map (edge > Set (node)))
740 //
741 // // 1) dg -> g
742 // Map g = new HashMap ();
743 // Iterator it = dg.getNodes ().iterator ();
744 // while (it.hasNext ()) {
745 // Object node = it.next ();
746 // Map edgeToNodes = new HashMap ();
747 // g.put (node, edgeToNodes);
748 //
749 // Iterator it2 = dg.getEdges (node).iterator ();
750 // while (it2.hasNext ()) {
751 // Object edge = it2.next ();
752 // Object end = dg.getNode (node, edge);
753 // Set ends = new HashSet ();
754 // ends.add (end);
755 // edgeToNodes.put (edge, ends);
756 // }
757 // }
758 //
759 // // 2) merge start node to all end nodes
760 // Object start = dg.getStartNode ();
761 // it = dg.getEnds ().iterator ();
762 // while (it.hasNext ()) {
763 // Object end = it.next ();
764 // if (end == start) continue;
765 // Map edgeToNodes = (Map) g.get (end);
766 //// wrong:
767 //// if (edgeToNodes.isEmpty ()) {
768 //// Iterator it2 = g.values ().iterator ();
769 //// while (it2.hasNext ()) {
770 //// Map m = (Map) it2.next ();
771 //// Iterator it3 = m.values ().iterator ();
772 //// while (it3.hasNext ()) {
773 //// Set s = (Set) it3.next ();
774 //// if (s.remove (end))
775 //// s.add (start);
776 //// }
777 //// }
778 //// continue;
779 //// }
780 // Iterator it2 = dg.getEdges (start).iterator ();
781 // while (it2.hasNext ()) {
782 // Object edge = it2.next ();
783 // Set ends = (Set) edgeToNodes.get (edge);
784 // if (ends == null) {
785 // ends = new HashSet ();
786 // edgeToNodes.put (edge, ends);
787 // }
788 // Object e = dg.getNode (start, edge);
789 // if (e == start)
790 // ends.add (end);
791 // else
792 // ends.add (e);
793 // }
794 // }
795 //
796 // Map ng = new HashMap ();
797 // Set newStart = new HashSet ();
798 // newStart.add (dg.getStartNode ());
799 // merge (g, newStart, ng);
800 //
801 // DG ndg = DG.createDG (newStart);
802 // it = ng.keySet ().iterator ();
803 // while (it.hasNext ()) {
804 // Set node = (Set) it.next ();
805 // if (!ndg.containsNode (node))
806 // ndg.addNode (node);
807 // Map edgeToNode = (Map) ng.get (node);
808 // Iterator it2 = edgeToNode.keySet ().iterator ();
809 // while (it2.hasNext ()) {
810 // Object edge = it2.next ();
811 // Set end = (Set) edgeToNode.get (edge);
812 // if (!ndg.containsNode (end))
813 // ndg.addNode (end);
814 // ndg.addEdge (node, end, edge);
815 // }
816 // }
817 // ndg.setStart (newStart);
818 // it = ndg.getNodes ().iterator ();
819 // while (it.hasNext ()) {
820 // Set node = (Set) it.next ();
821 // Iterator it2 = node.iterator ();
822 // while (it2.hasNext ()) {
823 // Object n = it2.next ();
824 // if (dg.getProperties (n) != null)
825 // ndg.putAllProperties (node, dg.getProperties (n));
826 // Iterator it3 = ndg.getEdges (node).iterator ();
827 // while (it3.hasNext ()) {
828 // Object edge = it3.next ();
829 // if (dg.getProperties (n, edge) != null)
830 // ndg.putAllProperties (node, edge, dg.getProperties (n, edge));
831 // if (dg.getEnds ().contains (n) && dg.getProperties (dg.getStartNode (), edge) != null)
832 // ndg.putAllProperties (node, edge, dg.getProperties (dg.getStartNode (), edge));
833 // }
834 // if (dg.getEnds ().contains (n)) {
835 // ndg.addEnd (node);
836 // continue;
837 // }
838 // }
839 // }
840 // return reduce (ndg);
841 //
842 // } catch (Exception e) {
843 // e.printStackTrace ();
844 // System.out.println("dg:" + dg);
845 // return null;
846 // }
847 // }
848 //
849 // private static void merge (
850 // Map g,
851 // Set node,
852 // Map ng
853 // ) {
854 // Map newEdgeToNodes = new HashMap ();
855 // ng.put (node, newEdgeToNodes);
856 //
857 // Set dots = new HashSet ();
858 // Iterator it = node.iterator ();
859 // while (it.hasNext ()) {
860 // Object oldNode = it.next ();
861 // Map oldEdgeToNodes = (Map) g.get (oldNode);
862 // Set nodes = (Set)oldEdgeToNodes.get (Pattern.STAR);
863 // if (nodes == null) continue;
864 // dots.addAll (nodes);
865 // }
866 // it = node.iterator ();
867 // while (it.hasNext ()) {
868 // Object oldNode = it.next ();
869 // Map oldEdgeToNodes = (Map) g.get (oldNode);
870 // Set ddots = null;
871 // Iterator it2 = oldEdgeToNodes.keySet ().iterator ();
872 // while (it2.hasNext ()) {
873 // Object edge = it2.next ();
874 // Set nodes = (Set) newEdgeToNodes.get (edge);
875 // if (nodes == null) {
876 // nodes = new HashSet ();
877 // newEdgeToNodes.put (edge, nodes);
878 // }
879 // nodes.addAll ((Set) oldEdgeToNodes.get (edge));
880 // if (edge.equals (Pattern.STAR) || dots.isEmpty ()) continue;
881 // if (ddots == null) {
882 // ddots = new HashSet (dots);
883 // Set pom = (Set) oldEdgeToNodes.get (Pattern.STAR);
884 // if (pom != null)
885 // ddots.removeAll (pom);
886 // }
887 // nodes.addAll (ddots);
888 // }
889 // }
890 //
891 // it = newEdgeToNodes.values ().iterator ();
892 // while (it.hasNext ()) {
893 // Set n = (Set) it.next ();
894 // if (ng.containsKey (n)) continue;
895 // merge (g, n, ng);
896 // }
897 // }
898 }
899

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags