KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > com > sun > corba > se > impl > orbutil > graph > GraphImpl


1 /*
2  * @(#)GraphImpl.java 1.5 03/12/19
3  *
4  * Copyright 2004 Sun Microsystems, Inc. All rights reserved.
5  * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
6  */
7
8 package com.sun.corba.se.impl.orbutil.graph ;
9
10 import java.util.Collection JavaDoc ;
11 import java.util.AbstractSet JavaDoc ;
12 import java.util.Iterator JavaDoc ;
13 import java.util.Map JavaDoc ;
14 import java.util.HashMap JavaDoc ;
15 import java.util.Set JavaDoc ;
16 import java.util.HashSet JavaDoc ;
17
18 public class GraphImpl extends AbstractSet JavaDoc implements Graph
19 {
20     private Map JavaDoc /* Map<Node,NodeData> */ nodeToData ;
21
22     public GraphImpl()
23     {
24     nodeToData = new HashMap JavaDoc() ;
25     }
26
27     public GraphImpl( Collection JavaDoc coll )
28     {
29     this() ;
30     addAll( coll ) ;
31     }
32     
33 /***********************************************************************************/
34 /************ AbstractSet implementation *******************************************/
35 /***********************************************************************************/
36
37     // Required for AbstractSet
38 public boolean add( Object JavaDoc obj ) // obj must be a Node
39 {
40     if (!(obj instanceof Node))
41         throw new IllegalArgumentException JavaDoc( "Graphs must contain only Node instances" ) ;
42
43     Node node = (Node)obj ;
44     boolean found = nodeToData.keySet().contains( obj ) ;
45
46     if (!found) {
47         NodeData nd = new NodeData() ;
48         nodeToData.put( node, nd ) ;
49     }
50
51     return !found ;
52     }
53
54     // Required for AbstractSet
55 public Iterator JavaDoc iterator()
56     {
57     return nodeToData.keySet().iterator() ;
58     }
59
60     // Required for AbstractSet
61 public int size()
62     {
63     return nodeToData.keySet().size() ;
64     }
65
66 /***********************************************************************************/
67
68     public NodeData getNodeData( Node node )
69     {
70     return (NodeData)nodeToData.get( node ) ;
71     }
72
73     private void clearNodeData()
74     {
75     // Clear every node
76 Iterator JavaDoc iter = nodeToData.entrySet().iterator() ;
77     while (iter.hasNext()) {
78         Map.Entry JavaDoc entry = (Map.Entry JavaDoc)iter.next() ;
79         NodeData nd = (NodeData)(entry.getValue()) ;
80         nd.clear( ) ;
81     }
82     }
83
84     interface NodeVisitor
85     {
86     void visit( Graph graph, Node node, NodeData nd ) ;
87     }
88
89     // This visits every node in the graph exactly once. A
90 // visitor is allowed to modify the graph during the
91 // traversal.
92 void visitAll( NodeVisitor nv )
93     {
94     boolean done = false ;
95
96     // Repeat the traversal until every node has been visited. Since
97 // it takes one pass to determine whether or not each node has
98 // already been visited, this loop always runs at least once.
99 do {
100         done = true ;
101
102         // Copy entries to array to avoid concurrent modification
103 // problem with iterator if the visitor is updating the graph.
104 Map.Entry JavaDoc[] entries =
105         (Map.Entry JavaDoc[])nodeToData.entrySet().toArray( new Map.Entry JavaDoc[0] ) ;
106
107         // Visit each node in the graph that has not already been visited.
108 // If any node is visited in this pass, we must run at least one more
109 // pass.
110 for (int ctr=0; ctr<entries.length; ctr++) {
111         Map.Entry JavaDoc current = entries[ctr] ;
112         Node node = (Node)current.getKey() ;
113         NodeData nd = (NodeData)current.getValue() ;
114
115         if (!nd.isVisited()) {
116             nd.visited() ;
117             done = false ;
118
119             nv.visit( this, node, nd ) ;
120         }
121         }
122     } while (!done) ;
123     }
124
125     private void markNonRoots()
126     {
127     visitAll(
128         new NodeVisitor() {
129         public void visit( Graph graph, Node node, NodeData nd )
130         {
131             Iterator JavaDoc iter = node.getChildren().iterator() ; // Iterator<Node>
132 while (iter.hasNext()) {
133             Node child = (Node)iter.next() ;
134
135             // Make sure the child is in the graph so it can be
136 // visited later if necessary.
137 graph.add( child ) ;
138
139             // Mark the child as a non-root, since a child is never a root.
140 NodeData cnd = graph.getNodeData( child ) ;
141             cnd.notRoot() ;
142             }
143         }
144         } ) ;
145     }
146
147     private Set JavaDoc collectRootSet()
148     {
149     final Set JavaDoc result = new HashSet JavaDoc() ;
150
151     Iterator JavaDoc iter = nodeToData.entrySet().iterator() ;
152     while (iter.hasNext()) {
153         Map.Entry JavaDoc entry = (Map.Entry JavaDoc)iter.next() ;
154         Node node = (Node)entry.getKey() ;
155         NodeData nd = (NodeData)entry.getValue() ;
156         if (nd.isRoot())
157         result.add( node ) ;
158     }
159
160     return result ;
161     }
162
163     public Set JavaDoc /* Set<Node> */ getRoots()
164     {
165     clearNodeData() ;
166     markNonRoots() ;
167     return collectRootSet() ;
168     }
169 }
170
Popular Tags