/*
 * @(#)GraphImpl.java	1.5 03/12/19
 *
 * Copyright 2004 Sun Microsystems, Inc. All rights reserved.
 * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 */

package com.sun.corba.se.impl.orbutil.graph ;

import java.util.Collection ;
import java.util.AbstractSet ;
import java.util.Iterator ;
import java.util.Map ;
import java.util.HashMap ;
import java.util.Set ;
import java.util.HashSet ;

public class GraphImpl extends AbstractSet implements Graph 
{
    private Map /* Map<Node,NodeData> */ nodeToData ;

    public GraphImpl()
    {
	nodeToData = new HashMap() ;
    }

    public GraphImpl( Collection coll )
    {
	this() ;
	addAll( coll ) ;
    }
    
/***********************************************************************************/    
/************ AbstractSet implementation *******************************************/    
/***********************************************************************************/    

    // Required for AbstractSet
    public boolean add( Object obj ) // obj must be a Node
    {
	if (!(obj instanceof Node))
	    throw new IllegalArgumentException( "Graphs must contain only Node instances" ) ;

	Node node = (Node)obj ;
	boolean found = nodeToData.keySet().contains( obj ) ;

	if (!found) {
	    NodeData nd = new NodeData() ;
	    nodeToData.put( node, nd ) ;
	}

	return !found ;
    }

    // Required for AbstractSet
    public Iterator iterator()
    {
	return nodeToData.keySet().iterator() ;
    }

    // Required for AbstractSet
    public int size()
    {
	return nodeToData.keySet().size() ;
    }

/***********************************************************************************/    

    public NodeData getNodeData( Node node ) 
    {
	return (NodeData)nodeToData.get( node ) ;
    }

    private void clearNodeData()
    {
	// Clear every node
	Iterator iter = nodeToData.entrySet().iterator() ;
	while (iter.hasNext()) {
	    Map.Entry entry = (Map.Entry)iter.next() ;
	    NodeData nd = (NodeData)(entry.getValue()) ;
	    nd.clear( ) ;
	}
    }

    interface NodeVisitor
    {
	void visit( Graph graph, Node node, NodeData nd ) ;
    }

    // This visits every node in the graph exactly once.  A
    // visitor is allowed to modify the graph during the
    // traversal.
    void visitAll( NodeVisitor nv )
    {
	boolean done = false ;

	// Repeat the traversal until every node has been visited.  Since
	// it takes one pass to determine whether or not each node has 
	// already been visited, this loop always runs at least once.
	do {
	    done = true ;

	    // Copy entries to array to avoid concurrent modification
	    // problem with iterator if the visitor is updating the graph.
	    Map.Entry[] entries = 
		(Map.Entry[])nodeToData.entrySet().toArray( new Map.Entry[0] ) ;

	    // Visit each node in the graph that has not already been visited.
	    // If any node is visited in this pass, we must run at least one more
	    // pass.
	    for (int ctr=0; ctr<entries.length; ctr++) {
		Map.Entry current = entries[ctr] ;
		Node node = (Node)current.getKey() ;
		NodeData nd = (NodeData)current.getValue() ;

		if (!nd.isVisited()) {
		    nd.visited() ;
		    done = false ;

		    nv.visit( this, node, nd ) ;
		}
	    }
	} while (!done) ;	
    }

    private void markNonRoots()
    {
	visitAll( 
	    new NodeVisitor() {
		public void visit( Graph graph, Node node, NodeData nd )
		{
		    Iterator iter = node.getChildren().iterator() ; // Iterator<Node>
		    while (iter.hasNext()) {
			Node child = (Node)iter.next() ;

			// Make sure the child is in the graph so it can be 
			// visited later if necessary.
			graph.add( child ) ;

			// Mark the child as a non-root, since a child is never a root.
			NodeData cnd = graph.getNodeData( child ) ;
			cnd.notRoot() ;
		    }
		}
	    } ) ;
    }

    private Set collectRootSet()
    {
	final Set result = new HashSet() ;

	Iterator iter = nodeToData.entrySet().iterator() ;
	while (iter.hasNext()) {
	    Map.Entry entry = (Map.Entry)iter.next() ;
	    Node node = (Node)entry.getKey() ;
	    NodeData nd = (NodeData)entry.getValue() ;
	    if (nd.isRoot())
		result.add( node ) ;
	}

	return result ;
    }

    public Set /* Set<Node> */ getRoots() 
    {
	clearNodeData() ;
	markNonRoots() ;
	return collectRootSet() ;
    }
}