// (c) MIT 2003.  All rights reserved.

// -*-Mode: Java-*- 
// OrderGraph.java -- 
// Author: Christine Alvarado <calvarad@ai.mit.edu> 
// Maintainer: Christine Alvarado <calvarad@ai.mit.edu> 
// Version: 
// Created: <Sat Nov 20 15:02:08 1999> 
// Time-stamp: <2001-04-24 10:41:55 moltmans> 
// Keywords: 

package rec.util;

import java.util.*;

/**
 * a directed graph structure with ordering semantics
 */

public class OrderGraph extends SimpleGraph
{
  
  public OrderGraph()
  {
    super();
  }


  public OrderGraph copy()
  {
    return (OrderGraph)clone();
  }

  /** eleminates any edges which are not necesary to maintain the ordering
   * between the nodes.
   */
  public void prune()
  {
    Hashtable infos = new Hashtable();
    
    Iterator it = objects();
    while ( it.hasNext() ) {
      ReachInfo ri = new ReachInfo();
      ri.setColor( "white" );
      infos.put( it.next(), ri );
    }
    
    it = objects();
    while ( it.hasNext() ) {
      pruneBody( it.next(), infos );
    }
  }

  private Collection pruneBody( Object sn, Hashtable infos )
  {
    
    Collection reachable = new HashSet();
    ReachInfo ri = (ReachInfo)infos.get( sn );
    if ( ri.getColor().equals( "white" ) ) {
      ri.setColor( "black" );
      
      Collection direct_reach = getReachable( sn );
      Collection remote_reach = new HashSet();
      Hashtable remote_table = new Hashtable();
      Iterator connected_it = direct_reach.iterator();
      
      while ( connected_it.hasNext() ) {
	Object connected_next = connected_it.next();
	Collection remote = pruneBody( connected_next, infos );
	remote.remove( sn );
	//remote_reach.addAll( remote );
	remote_table.put( connected_next, remote );
      }


      // get rid of single node links
      if ( direct_reach.contains( sn ) ) {
	removeEdge( sn, sn );
	direct_reach.remove( sn );
      }

      // now remove any direct connections that can be reached remotely
      connected_it = direct_reach.iterator();
      while ( connected_it.hasNext() ) {
	Object reach = connected_it.next();

	remote_reach = new HashSet();
	
	Iterator remote_it = remote_table.values().iterator();
	while ( remote_it.hasNext() ) {
	  remote_reach.addAll( (Collection)remote_it.next() );
	}
	
	if ( remote_reach.contains( reach ) ) {
	  removeEdge( sn, reach );
	  connected_it.remove();
	  remote_table.remove( reach );
	}
      }

      remote_reach = new HashSet();
      
      Iterator remote_it = remote_table.values().iterator();
      while ( remote_it.hasNext() ) {
	remote_reach.addAll( (Collection)remote_it.next() );
      }
      
      reachable.addAll( remote_reach );
      reachable.addAll( direct_reach );

      ri.setReachable( reachable );
    }
    else {
      reachable = ri.getReachable();
    }

    return reachable;
  }


  /** Does not preserve the ordering of the edges, just rips the node out
   */
  public void removeNodeSimple( Object n ) {
    super.removeNode( n );
  }
  
  /**
   * Adds edges to maintain the ordering of the nodes
   */
  public void removeNode( Object n )
  {
    if ( !m_Nodes.containsKey( n ) ) {
      Assert.note( "Attempt to remove " + n + " failed.  Not in graph" );
      return;
    }

    if ( n instanceof Collection ) {
      Iterator it = ((Collection)n).iterator();
      while ( it.hasNext() ) {
	m_LooseObjects.remove( it.next() );
      }
    }
    else {
      m_LooseObjects.remove( n );
    }

    
    SimpleNode sn = (SimpleNode)m_Nodes.remove( n );

    Collection backward = sn.getBackEdgeNodes();
    Collection forward = sn.getForwardEdgeNodes();
    Iterator back_it = backward.iterator();

    while ( back_it.hasNext() ) {
      SimpleNode back = (SimpleNode)back_it.next();
      back.removeToEdge( sn );
      
      Iterator forward_it = forward.iterator();
      while ( forward_it.hasNext() ) {
	SimpleNode front = (SimpleNode)forward_it.next();
	front.removeFromEdge( sn );
	// careful not to put the node back into the graph
	if ( !front.equals( sn ) ) {
	  back.addToEdge( front );
	}
	if ( !back.equals( sn ) ) {
	  front.addFromEdge( back );
	}
      }
    }
  }

  /**
   * collapse the cycles in a graph to create a new graph
   * which have nodes of groups of objects
   */
  public void collapseCycles()
  {
    Hashtable dfsInfos = dfs();
    
    OrderGraph trans = null;
    try {
      trans = (OrderGraph)clone();
    }
    catch (Exception e) {
      System.err.println( e );
      Assert.error("Error while collapsing cycles");
    }
    
    trans.transpose();
    
    List ordered_nodes = trans.sortByFinishTime( dfsInfos );
    Hashtable trans_infos = trans.dfs( ordered_nodes );  

    Collection roots = new HashSet();
    Hashtable links = new Hashtable();
    
    Iterator node_it = objects();

    
    while ( node_it.hasNext() ) {
      Object o = node_it.next();
      Assert.check( trans_infos.containsKey( o ),
		    "info graph does not contain " + o );
      DFSInfo info = (DFSInfo)trans_infos.get( o );

      Assert.check( info != null, "Info for " + o + " is null." );
      Object source = info.getSource();

      if ( source == null ) {
	roots.add( o );
      }
      else {
	Collection level = (Collection)links.get( source );
	if ( level == null ) {
	  level = new HashSet(); 
	  links.put( source, level );
	}
	level.add( o );
      }
    }

    // now collapse the nodes in the graph
    Iterator roots_it = roots.iterator();
    while ( roots_it.hasNext() ) {
      Object root_obj = roots_it.next();

      // find the SCCs of this root in the DFS tree
      Vector scc = new Vector();
      scc.add( root_obj );

      int i = 0;
      while ( i < scc.size() ) {
	Object next_child = scc.elementAt( i );
	Collection next_children = (Collection)links.get( next_child );
	if ( next_children != null ) {
	  scc.addAll( next_children );
	}
	i++;
      }

      collapseSCC( scc );
    }
    
    
  }

  private void collapseSCC( Collection scc )
  {

    Collection for_links = new HashSet();
    Collection back_links = new HashSet();
    Collection objects = new HashSet();
    Iterator scc_it = scc.iterator();

    OrderGraph trans_graph = null;
    try {
      trans_graph = (OrderGraph)this.clone();
    }
    catch (Exception e) {
      System.err.println( e );
      Assert.error("Error doing collapseSCC");
    }

    trans_graph.transpose();

    
    while( scc_it.hasNext() ) {
      Object member = scc_it.next();

      if ( member instanceof Collection ) {
	objects.addAll( (Collection)member );
      }
      else {
	objects.add( member );
      }

      for_links.addAll( getReachable( member ) );
      back_links.addAll( trans_graph.getReachable( member ) );

      
      // remove the node, and its edges
      super.removeNode( member );
    }
    
    addNode( objects );    

    // now link up the new node
    Iterator for_it = for_links.iterator();
    while ( for_it.hasNext() ) {
      Object forward = for_it.next();
      if ( !scc.contains( forward ) ) {
	addEdge( objects, forward );
      }
    }
    Iterator back_it = back_links.iterator();
    while ( back_it.hasNext() ) {
      Object backward  = back_it.next();
      if ( !scc.contains( backward ) ) {
	addEdge( backward, objects );
      }
    }
    
  }
  
  /**
   * topologically sorts the graph and then returns a list of the nodes
   * in order
   */
  public List topSort()
  {
    Hashtable dfs_info = dfs();

    List sorted = sortByFinishTime( dfs_info );
    
    //Collections.reverse( sorted );

    return sorted;
  }

  /**
   * Sort the graph, and then collapse any nodes which are not explicitly
   * ranked in the sorted list
   **/
  // (i.e. given the graph with nodes a, b, c
  // and edges (a,b) and (a, c) a legal sort would be a, b, c, but the
  // buckets would be (a) and (b, c)
  public List bucket()
  {
    List sorted = topSort();

    OrderGraph trans = null;
    try {
      trans = (OrderGraph)clone();
    }
    catch ( Exception e ) {
      System.err.println( e );
      Assert.error("Error in OrderGraph");
    }
    
    trans.transpose();

    Vector buckets = new Vector();

    Hashtable bucket_assigned = new Hashtable();
    
    Iterator sorted_it = sorted.iterator();

    while ( sorted_it.hasNext() ) {
      Object o = sorted_it.next();

      Collection reach = trans.getReachable( o );

      if ( reach.isEmpty() ) {
	Collection elemts;
	if ( buckets.size() > 0 ) {
	  elemts = (Collection)buckets.elementAt( 0 );
	}
	else {
	  elemts = new HashSet();
	  buckets.add( elemts );
	}
	if ( o instanceof Collection ) {
	  elemts.addAll( (Collection)o );
	}
	else {
	  elemts.add( o );
	}
	bucket_assigned.put( o, new Integer( 0 ) );
      }
      else {
	int max_bucket = -1;
	Iterator reach_it = reach.iterator();

	while ( reach_it.hasNext() ) {
	  Object reached  = reach_it.next();

	  Assert.check( bucket_assigned.containsKey( reached ),
			"We should have already assigned " + reached
			+ " to a bucket" );

	  Integer curr_bucket_int = (Integer)bucket_assigned.get( reached );
	  int curr_bucket = curr_bucket_int.intValue();
	  if ( curr_bucket > max_bucket ) {
	    max_bucket = curr_bucket;
	  }
	}
	Collection elemts;
	if ( max_bucket+1 < buckets.size() ) {
	  elemts = (Collection)buckets.elementAt( max_bucket+1 );
	}
	else {
	  elemts = new HashSet();
	  buckets.add( elemts );
	}
	if ( o instanceof Collection ) {
	  elemts.addAll( (Collection)o );
	}
	else {
	  elemts.add( o );
	}
	bucket_assigned.put( o, new Integer( max_bucket+1 ) );
	
      }
      
    }

    return buckets;
  }

}
