• file
• revisions
• annotate
• diff
• comparison
• raw

src/share/classes/com/sun/corba/se/impl/orbutil/graph/GraphImpl.java@6845b95cba6b (annotated)

src/share/classes/com/sun/corba/se/impl/orbutil/graph/GraphImpl.java

Thu, 31 Aug 2017 18:10:36 +0800

author

aoqi

date

Thu, 31 Aug 2017 18:10:36 +0800

changeset 748

6845b95cba6b

parent 158

91006f157c46

parent 0

7ef37b2cdcad

permissions

-rw-r--r--

merge

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