1 /*
2 * Copyright (c) 2003, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 package com.sun.corba.se.impl.orbutil.graph ;
27
28 import java.util.Collection ;
29 import java.util.AbstractSet ;
30 import java.util.Iterator ;
31 import java.util.Map ;
32 import java.util.HashMap ;
33 import java.util.Set ;
34 import java.util.HashSet ;
35
36 public class GraphImpl extends AbstractSet implements Graph
37 {
38 private Map /* Map<Node,NodeData> */ nodeToData ;
39
40 public GraphImpl()
41 {
42 nodeToData = new HashMap() ;
43 }
44
45 public GraphImpl( Collection coll )
46 {
47 this() ;
48 addAll( coll ) ;
49 }
50
51 /***********************************************************************************/
52 /************ AbstractSet implementation *******************************************/
53 /***********************************************************************************/
54
55 // Required for AbstractSet
56 public boolean add( Object obj ) // obj must be a Node
57 {
58 if (!(obj instanceof Node))
59 throw new IllegalArgumentException( "Graphs must contain only Node instances" ) ;
60
61 Node node = (Node)obj ;
62 boolean found = nodeToData.keySet().contains( obj ) ;
63
64 if (!found) {
65 NodeData nd = new NodeData() ;
66 nodeToData.put( node, nd ) ;
67 }
68
69 return !found ;
70 }
71
72 // Required for AbstractSet
73 public Iterator iterator()
74 {
75 return nodeToData.keySet().iterator() ;
76 }
77
78 // Required for AbstractSet
79 public int size()
80 {
81 return nodeToData.keySet().size() ;
82 }
83
84 /***********************************************************************************/
85
86 public NodeData getNodeData( Node node )
87 {
88 return (NodeData)nodeToData.get( node ) ;
89 }
90
91 private void clearNodeData()
92 {
93 // Clear every node
94 Iterator iter = nodeToData.entrySet().iterator() ;
95 while (iter.hasNext()) {
96 Map.Entry entry = (Map.Entry)iter.next() ;
97 NodeData nd = (NodeData)(entry.getValue()) ;
98 nd.clear( ) ;
99 }
100 }
101
102 interface NodeVisitor
103 {
104 void visit( Graph graph, Node node, NodeData nd ) ;
105 }
106
107 // This visits every node in the graph exactly once. A
108 // visitor is allowed to modify the graph during the
109 // traversal.
110 void visitAll( NodeVisitor nv )
111 {
112 boolean done = false ;
113
114 // Repeat the traversal until every node has been visited. Since
115 // it takes one pass to determine whether or not each node has
116 // already been visited, this loop always runs at least once.
117 do {
118 done = true ;
119
120 // Copy entries to array to avoid concurrent modification
121 // problem with iterator if the visitor is updating the graph.
122 Map.Entry[] entries =
123 (Map.Entry[])nodeToData.entrySet().toArray( new Map.Entry[0] ) ;
124
125 // Visit each node in the graph that has not already been visited.
126 // If any node is visited in this pass, we must run at least one more
127 // pass.
128 for (int ctr=0; ctr<entries.length; ctr++) {
129 Map.Entry current = entries[ctr] ;
130 Node node = (Node)current.getKey() ;
131 NodeData nd = (NodeData)current.getValue() ;
132
133 if (!nd.isVisited()) {
134 nd.visited() ;
135 done = false ;
136
137 nv.visit( this, node, nd ) ;
138 }
139 }
140 } while (!done) ;
141 }
142
143 private void markNonRoots()
144 {
145 visitAll(
146 new NodeVisitor() {
147 public void visit( Graph graph, Node node, NodeData nd )
148 {
149 Iterator iter = node.getChildren().iterator() ; // Iterator<Node>
150 while (iter.hasNext()) {
151 Node child = (Node)iter.next() ;
152
153 // Make sure the child is in the graph so it can be
154 // visited later if necessary.
155 graph.add( child ) ;
156
157 // Mark the child as a non-root, since a child is never a root.
158 NodeData cnd = graph.getNodeData( child ) ;
159 cnd.notRoot() ;
160 }
161 }
162 } ) ;
163 }
164
165 private Set collectRootSet()
166 {
167 final Set result = new HashSet() ;
168
169 Iterator iter = nodeToData.entrySet().iterator() ;
170 while (iter.hasNext()) {
171 Map.Entry entry = (Map.Entry)iter.next() ;
172 Node node = (Node)entry.getKey() ;
173 NodeData nd = (NodeData)entry.getValue() ;
174 if (nd.isRoot())
175 result.add( node ) ;
176 }
177
178 return result ;
179 }
180
181 public Set /* Set<Node> */ getRoots()
182 {
183 clearNodeData() ;
184 markNonRoots() ;
185 return collectRootSet() ;
186 }
187 }