GraphImpl.java revision 608:7e06bf1dcb09
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 26package com.sun.corba.se.impl.orbutil.graph ; 27 28import java.util.Collection ; 29import java.util.AbstractSet ; 30import java.util.Iterator ; 31import java.util.Map ; 32import java.util.HashMap ; 33import java.util.Set ; 34import java.util.HashSet ; 35 36public 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} 188