/**
 * Utilities related to graph
 * @author Kiminori Matsuzaki
 */

import java.io.*;
import java.util.*;

class Link {
  String fromURL;
  String toURL;

  Link( String fromURL, String toURL ) {
    this.fromURL = fromURL;
    this.toURL = toURL;
  }
}

class GraphNode {
  /** Node URL */
  String url;
  /** Node title */
  String title;
  /** Link indices ( index, count ) */
  HashMap links;

  GraphNode( String url, String title ) {
    this.url = url;
    this.title = title;
    this.links = new HashMap( );
  }
}

class GraphUtil {
  /** Map form a URL (String) to an index (Integer). */
  private HashMap mapURLtoIndex;

  /** List of nodes (GraphNode) */
  private Vector lists;

  GraphUtil( ) {
    mapURLtoIndex = new HashMap( );
    lists = new Vector( );
  }

  /**
   * Add a new node to this graph. If the node is already included,
   * do nothing.
   * @param url: the URL (key) of the node.
   * @param title: the title of the node.
   * @return true if the node is successfully added, false otherwise. 
   */
  boolean addNode( String url, String title ) {
    if ( mapURLtoIndex.containsKey( url ) ) return false;

    int newIndex = lists.size( );
    mapURLtoIndex.put( url, new Integer( newIndex ) );
    lists.add( new GraphNode( url, title ) );

    return true;
  }

  /**
   * Set the title of the node.
   * If there is no node named as url, then a new node is added.
   */
  boolean addAndSetTitle( String url, String title ) {
    if ( mapURLtoIndex.containsKey( url ) ) {
      int index = ( ( Integer ) mapURLtoIndex.get( url ) ).intValue( );
      ( ( GraphNode ) lists.get( index ) ).title = title;
    } else {
      int newIndex = lists.size( );
      mapURLtoIndex.put( url, new Integer( newIndex ) );
      lists.add( new GraphNode( url, title ) );
    }
    return true;
  }
  
  /**
   * Add a link to this graph.
   * @param link: the source URL and dest URL.
   * @return true if the link is successfully added, false otherwise. 
   */
  boolean addLink( Link link ) {
    return addLink( link.fromURL, link.toURL );
  }

  /**
   * Add a link to this graph.
   * @param fromURL: the source URL of the link.
   * @param toURL: the destURL of the link.
   * @return true if the link is successfully added, false otherwise. 
   */
  boolean addLink( String fromURL, String toURL ) {
    if ( !mapURLtoIndex.containsKey( fromURL ) ||
	 !mapURLtoIndex.containsKey( toURL ) ) return false;

    int fromIndex = ( ( Integer ) mapURLtoIndex.get( fromURL ) ).intValue( );
    int toIndex = ( ( Integer ) mapURLtoIndex.get( toURL ) ).intValue( );

    GraphNode from = ( GraphNode ) lists.get( fromIndex );
    if ( from.links.containsKey( new Integer( toIndex ) ) ) {
      int value = ( ( Integer ) from.links.get( new Integer( toIndex ) ) ).intValue( ) + 1;
      from.links.put( new Integer( toIndex ), new Integer( value ) );
    } else {
      from.links.put( new Integer( toIndex ), new Integer( 1 ) );
    }

    return true;
  }

  /**
   * Output the graph to a file. 
   * @param filename: The name of file which the data will be written to.
   */
  void outputToFile( String filename ) throws Exception {
    PrintWriter out = new PrintWriter( new FileWriter( filename ) );

    int size = lists.size( );
    out.println( size );

    for ( int i = 0; i < size; i++ ) {
      GraphNode node = ( GraphNode ) lists.get( i );
      out.println( "Node|" + i + "|" + node.url + "|" + node.title );
    }

    for ( int i = 0; i < size; i++ ) {
      GraphNode node = ( GraphNode ) lists.get( i );
      int[] counts = new int[ size ];
      int numlinks = node.links.size( );
      Iterator it = node.links.keySet( ).iterator( );
      while( it.hasNext( ) ) {
	Integer index = ( Integer ) it.next( );
	Integer count = ( Integer ) node.links.get( index );
	counts[ index.intValue( ) ] = count.intValue( );
      }
      out.print( "Link|" + i + "|" + numlinks );
      for ( int j = 0; j < size; j++ ) {
	if ( counts[ j ] != 0 ) {
	  out.print( "|" + j + " " + counts[ j ] );
	}	   
      }
      out.println( );
    }
    out.flush( );
    
  }

  /**
   * A test and sample code.
   * The structure of the graph is shown in GraphUtil.ps
   */
  public static void main( String[] args ) {
    GraphUtil graph = new GraphUtil( );
    graph.addNode( "http://node1/", "Node 1" );
    graph.addNode( "http://node2/", "Node 2" );

    graph.addLink( "http://node1/", "http://node2/" );
    graph.addLink( "http://node2/", "http://node1/" );
    
    graph.addNode( "http://node3/", "Node 3" );
    graph.addLink( "http://node1/", "http://node3/" );
    graph.addLink( "http://node1/", "http://node3/" );

    try {
      graph.outputToFile( "output.txt" );
    }
    catch ( Exception e ) {
      e.printStackTrace( );
    }
  }
}