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

// -*-Mode: Java-*- 
// SimpleGraph.java -- 
// Author: Christine Alvarado <calvarad@ai.mit.edu> 
// Maintainer: Christine Alvarado <calvarad@ai.mit.edu> 
// Version: 
// Created: <Fri Nov 19 19:25:42 1999> 
// Time-stamp: <2001-04-24 10:42:08 moltmans> 
// Keywords: 
package rec.util;

import java.util.*;
import java.lang.*;

/**
 * A simple graph structure, with a hashtable of nodes which have
 * lists of incoming and outgoing edges
 */


public class SimpleGraph implements Cloneable
{
  protected Hashtable m_Nodes;
  protected Hashtable m_LooseObjects;
  
  public SimpleGraph()
  {
    m_Nodes = new Hashtable();
    m_LooseObjects = new Hashtable();
  }
  
  protected Object clone()
  {
    SimpleGraph sg = null;
    try {
      sg = (SimpleGraph)super.clone();
    }
    catch ( Exception e ) {
      System.err.println( e );
      Assert.error("Error in SimpleGraph");
    }

    sg.m_Nodes = new Hashtable();
    sg.m_LooseObjects = new Hashtable();
    
    // copy the nodes
    Iterator it = objects();
    while ( it.hasNext() ) {
      Object o = it.next();
      sg.addNode( o );
    }

    it = objects();
    while ( it.hasNext() ) {
      Object o = it.next();
      Collection reach = getReachable( o );
      Iterator it2 = reach.iterator();
      while ( it2.hasNext() ) {
	sg.addEdge( o, it2.next() );
      }
    }

    return sg;
  }
  
  public void addNode( Object n )
  {
    if ( !m_LooseObjects.contains( n ) && !m_Nodes.containsKey( n ) ) {
      SimpleNode nn = new SimpleNode( n );
      m_Nodes.put( n, nn );
      if ( n instanceof Collection ) {
	Iterator it = ((Collection)n).iterator();
	while ( it.hasNext() ) {
	  m_LooseObjects.put( it.next(), n );
	}
      }
      else {
	m_LooseObjects.put( n, new HashSet() );
      }
    }
    
  }

  /** Remove the node and all the edges which point to it */
  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 nn = (SimpleNode)m_Nodes.remove( n );
    
    Collection back = nn.getBackEdgeNodes();
    Iterator back_it = back.iterator();

    while ( back_it.hasNext() ) {
      ((SimpleNode)back_it.next()).removeToEdge( nn );
    }

    Iterator forward_it = nn.getForwardEdgeNodes().iterator();
    while ( forward_it.hasNext() ) {
      ((SimpleNode)forward_it.next()).removeFromEdge( nn );
    }

  }

  protected Iterator nodes()
  {
    return m_Nodes.values().iterator();
  }

  public int size()
  {
    return m_Nodes.size();
  }
  
  public Iterator objects()
  {
    return m_Nodes.keySet().iterator();
  }

  /* returns the objects in the graph in loose form (not grouped
   * as they are grouped in nodes)
   */
  public Iterator looseObjects()
  {
    return m_LooseObjects.keySet().iterator();
  }

  /**
   * return all the objects reachable in one step from the object in question
   */
  public Collection getReachable( Object o )
  {
    SimpleNode node = (SimpleNode)m_Nodes.get( o );

    Collection reach = node.getForwardEdgeNodes();
    Collection reach_obj = new HashSet();
    
    Iterator reach_it = reach.iterator();
    while ( reach_it.hasNext() ) {
      reach_obj.add( ((SimpleNode)reach_it.next()).getObject() );
    }

    return reach_obj;
  }

  public void addEdge( Object from_obj, Object to_obj )
  {
    
    Assert.check( m_Nodes.containsKey( from_obj ) ||
		  m_LooseObjects.containsKey( from_obj ),
		  "AddEdge: Graph does not contain object " + from_obj );
    Assert.check( m_Nodes.containsKey( to_obj ) ||
		  m_LooseObjects.containsKey( to_obj ),
		  "AddEdge: Graph does not contain object " + to_obj );

    if ( !m_Nodes.containsKey( to_obj ) ) {
      to_obj = m_LooseObjects.get( to_obj );
    }
    if ( !m_Nodes.containsKey( from_obj ) ) {
      from_obj = m_LooseObjects.get( from_obj );
    }
    
    SimpleNode from_node = (SimpleNode)m_Nodes.get( from_obj );
    SimpleNode to_node = (SimpleNode)m_Nodes.get( to_obj );

    from_node.addToEdge( to_node );
    to_node.addFromEdge( from_node );

  }

  public void removeEdge( Object from_obj, Object to_obj )
  {
    Assert.check( m_Nodes.containsKey( from_obj ) ||
		  m_LooseObjects.containsKey( from_obj ),
		  "RemoveEdge: Graph does not contain object " + from_obj );
    Assert.check( m_Nodes.containsKey( to_obj ) ||
		  m_LooseObjects.containsKey( to_obj ),
		  "RemoveEdge: Graph does not contain object " + to_obj );


    if ( !m_Nodes.containsKey( to_obj ) ) {
      to_obj = m_LooseObjects.get( to_obj );
    }
    if ( !m_Nodes.containsKey( from_obj ) ) {
      from_obj = m_LooseObjects.get( from_obj );
    }
    
    SimpleNode from_node = (SimpleNode)m_Nodes.get( from_obj );
    SimpleNode to_node = (SimpleNode)m_Nodes.get( to_obj );

    from_node.removeToEdge( to_node );
    to_node.removeFromEdge( from_node );

  }

  public void transpose()
  {
    Iterator it = nodes();
    while ( it.hasNext() ) {
      SimpleNode nsn = (SimpleNode)it.next();
      nsn.reverse();
    }
  }

  /**
   * Depth first serach on the graph.  Returns info about each *object* in
   * the graph.  Namely, marks each node with a start
   * time and a finish time.
   */
  public Hashtable dfs()
  {
    Vector nodes = new Vector( m_Nodes.keySet() );

    return dfs( nodes );
  }

  /** does the dfs with the nodes guarenteed to be considered in
   *  the order in which they are passed in.
   */
  public Hashtable dfs( List orderedNodes )
  {
    Console.indent();
    
    Hashtable searchInfo = new Hashtable();
    Iterator node_it = orderedNodes.iterator();

    while ( node_it.hasNext() ) {
      Object o = node_it.next();
      
      DFSInfo dfsi = new DFSInfo();
      searchInfo.put( o, dfsi );
    }

    Integer time = new Integer( 0 );
    
    node_it = orderedNodes.iterator();
    
    while ( node_it.hasNext() ) {
      Object o = node_it.next();

      DFSInfo dfsi = (DFSInfo)searchInfo.get( o );
      if ( dfsi.getColor().equals( "white" ) ) {
	time = dfsVisit( o, searchInfo, time );
      }
    }

    Console.outdent();

    return searchInfo;
  }

  private Integer dfsVisit( Object o, Hashtable searchInfo, Integer time )
  {
    // color the node gray
    DFSInfo info = (DFSInfo)searchInfo.get( o );
    info.setColor( "gray" );
    
    // set the discovery time
    info.setStartTime( time.intValue() );

    
    // increment the time
    int new_time = time.intValue() + 1;
    time = new Integer( new_time );
    
    Iterator reachable_it = getReachable( o ).iterator();
    while ( reachable_it.hasNext() ) {
      Object next = reachable_it.next();
      DFSInfo next_info = (DFSInfo)searchInfo.get( next );

      if ( next_info.getColor().equals( "white" ) ) {
	next_info.setSource( o );
	time = dfsVisit( next, searchInfo, time );
      }
    }

    // set the color to black
    info.setColor( "black" );

    // set the finish time
    info.setFinishTime( time.intValue() );

    
    // increment the time
    new_time = time.intValue() + 1;
    time = new Integer( new_time );

    return time;
  }

  protected List sortByFinishTime( Hashtable dfsInfos )
  {
    Object[] array = dfsInfos.keySet().toArray();
    java.util.Comparator comp = new FTimeDecreaseComparator( dfsInfos );
    
    Arrays.sort( array, comp );

    List sorted_infos = Arrays.asList( array );

    return sorted_infos;
  }

  public void print()
  {
    Iterator print_it = objects();
    Console.writeln( "The nodes in graph " + this + " are: " );
    Console.indent();
    while ( print_it.hasNext() ) {
      Object o = print_it.next();
      Console.writeln( "Node: " + o.toString() + " has edges to nodes: " );
      Console.indent();
      
      Iterator it = getReachable( o ).iterator();
      while ( it.hasNext() ) {
	Object o2 = it.next();
	Console.writeln( o2.toString() );
      }
      Console.outdent();
    }
    Console.outdent();
    Console.writeln();
  }
  
  // sorts from GREATEST finish time, to LEAST finish time
  protected class FTimeDecreaseComparator implements java.util.Comparator
  {
    private Hashtable m_DFSInfos;

    FTimeDecreaseComparator( Hashtable table )
    {
      m_DFSInfos = table;
    }

    public int compare( Object o1, Object o2 )
    {
      int ftime1 = ((DFSInfo)m_DFSInfos.get( o1 )).getFinishTime();
      int ftime2 = ((DFSInfo)m_DFSInfos.get( o2 )).getFinishTime();

      if ( ftime1 > ftime2 ) {
	return -1;
      }
      if ( ftime1 == ftime2 ) {
	return 0;
      }
      return 1;
    }

  }

  protected class SimpleNode {
    private HashSet m_ToNodes;
    private HashSet m_FromNodes;

    Object m_Center;

    SimpleNode( Object center )
    {
      m_ToNodes = new HashSet();
      m_FromNodes = new HashSet();

      m_Center = center;

    }

    // all the nodes directly connected to this one
    Collection getForwardEdgeNodes()
    {
      return ( new HashSet( m_ToNodes ) );
    }

    Collection getBackEdgeNodes()
    {
      return ( new HashSet( m_FromNodes ) );
    }
    
    void removeToEdge( SimpleNode n )
    {
      m_ToNodes.remove( n );
    }
    
    void removeFromEdge( SimpleNode n )
    {
      m_FromNodes.remove( n );
    }
    
    void addToEdge( SimpleNode n )
    {
      m_ToNodes.add( n );
    }
    
    void addFromEdge( SimpleNode n )
    {
      m_FromNodes.add( n );
    }

    void reverse()
    {
      HashSet temp = m_ToNodes;
      m_ToNodes = m_FromNodes;
      m_FromNodes = temp;
    }

    Object getObject()
    {
      return m_Center;
    }
    
  }

  protected class ColorInfo
  {
    private String m_Color;

    ColorInfo()
    {
      m_Color = "white";
    }

    void setColor( String color )
    {
      m_Color = color;
    }

    String getColor()
    {
      return m_Color;
    }
    
  }

  protected class ReachInfo extends ColorInfo
  {
    private Collection m_Reachable;

    ReachInfo()
    {
      m_Reachable = new HashSet();
    }

    void setReachable( Collection reach )
    {
      m_Reachable = new HashSet( reach );
    }

    Collection getReachable()
    {
      return m_Reachable;
    } 
  }

  protected class DFSInfo extends ColorInfo
  {
    private int m_Start;
    private int m_Finish;
    private Object m_Source;

    DFSInfo()
    {
      super();
    }
    
    int getStartTime()
    {
      return m_Start;
    }

    int getFinishTime()
    {
      return m_Finish;
    }
    
    void setStartTime( int start )
    {
      m_Start = start;
    }

    void setFinishTime( int finish )
    {
      m_Finish = finish;
    }
    
    void setSource( Object source )
    {
      m_Source = source;
    }

    Object getSource()
    {
      return m_Source;
    }
  }
  
}
