/* dep_remove.cc */

#include "dep_remove.h"
#include <iostream.h>
#include <LEDA/dictionary.h>
#include <strings.h>
#include <LEDA/queue.h>
#include <fstream.h>
#include <sys/ddi.h>  /* for min, max fns */

//#define DIAGNOSTIC_BS

#ifdef DIAGNOSTIC_BS
#include <stdio.h> 
#endif

struct dep_matrix {
private:
  char *m;
  int n;
  int node_off;
  int node_c_off;
public:
  dep_matrix( int N );
  ~dep_matrix( void ) { delete( m ); }
  
  // for nodes : 0 unexplored, 1 explored
  char &node_in_loop( int nd ) { return m[node_off + nd]; }
  char &node_checked( int nd ) { return m[node_c_off + nd]; }
  // for edges : 0 no-edge, 1 edge
  char &edge( int i, int j ) { return m[ i + ( n * j ) ]; } 
  char &operator()( int i, int j ) { return edge( i, j ); }
  void zero_nodes( void ) { bzero( &m[node_off], sizeof( char ) * 2 * n ); }
#ifdef DIAGNOSTIC_BS
  int print( void ) const;
#endif
};

bool zoop( dep_matrix &, const int, const int, int &, int & );

dep_matrix::dep_matrix( int N ) {
  n = N; 
  node_off = n * n; 
  node_c_off = node_off + n;
  int area = node_c_off + n;
  m = new char[ area ];
  bzero( m, sizeof( char ) * area );
}

#ifdef DIAGNOSTIC_BS
int dep_matrix::print( void ) const {
  printf( "      " );
  for( int i = 0 ; i < n ; i++ ) {
    printf( "%-2d ",i );
  }
  printf( "\nNODE: " );
  for( int i = 0 ; i < n ; i++ ) {
    printf( "%c  ", m[node_off + n] ? 'H' : '.' );    
  }
  printf( "\nCHKD: " );
  for( int i = 0 ; i < n ; i++ ) {
    printf( "%c  ", m[node_c_off + n] ? 'H' : '.' );    
  }

  printf( "\n" );
  for( int j = 0 ; j < n ; j++ ) {
    printf( "\n%2d  : ", j );
    for( int i = 0 ; i < n ; i++ ) {
      printf( "%c  ", m[i + n * j] ? 'E' : '.' );
    }
  }
  printf( "\n\n" );
  return 0;
}
#endif

int remove_dependencies( const dep_list &dependencies, dep_list &to_remove ) {
  to_remove.clear();

  // dump deps to file
  ofstream file( "dep_file.txt" );
  bool src = true;
  tag d, dset = 0;
  int len;
  forall( d, dependencies ) {
    string descrip = tag_descrip( d );

    if( src ) {
      if (dset == d) {
	file << descrip;
	len = descrip.length();
      } else {
	len = 20;
      }
      dset = d;
      int n = max( 40 - len, 1 );
      for( int i = 0 ; i < n ; i++ ) {
	file << ' ';
      }
    }
    else {
      file << descrip;
      file << "\n";
    }
    src = !src;
  }
  file.close();

  tag dep;
  /* assign an index to each unique tag */
  dictionary<tag,int> tag_to_index; /* maps tags to indices */
  int n = 0; /* number of unique tags */
  forall( dep, dependencies ) {
    if( !tag_to_index.lookup( dep ) ) {
#ifdef DIAGNOSTIC_BS
      printf( "mapping tag %ld to %d\n", dep, n );
#endif
      tag_to_index.insert( dep, n++ );
    }
  }
  tag *index_to_tag = new tag[n];
  dic_item di;
  forall_items( di, tag_to_index ) {
    index_to_tag[ tag_to_index.inf( di ) ] = tag_to_index.key( di );
  }

#ifdef DIAGNOSTIC_BS  
  printf( "INDEX\tTAG\n" );
  for( int i = 0 ; i < n ; i++ ) {
    printf( "%-5d\t%-5ld\n", i, index_to_tag[i] );
  }
#endif
  
  dep_matrix d_mx( n );

  list_item it_from = dependencies.first(), it_to;
  tag dep_from, dep_to;
  while( it_from ) {
    dep_from = dependencies.inf( it_from );
    if( ( it_to = dependencies.succ( it_from ) ) == nil ) {
      cerr << "remove_dependencies -- invalid dep_list\n";
      exit( 1 );
    }
    dep_to = dependencies.inf( it_to );
    int f_indx = tag_to_index.access( dep_from );
    int t_indx = tag_to_index.access( dep_to );
    // uncomment if need to remove duplicate dependencies
    //     if( d_mx( f_indx, t_indx ) ) {
    // #ifdef DIAGNOSTIC_BS
    //       printf( "REMOVING DUPLICATE OF ( %ld, %ld )\n", dep_from, dep_to );
    // #endif
    //       list_item tmp_it = it_from;
    //       it_from = dependencies.succ( it_to );
    //       dependencies.del_item( tmp_it );
    //       dependencied.del_item( it_to );
    //     } else {
    d_mx( f_indx, t_indx ) = 1;
    it_from = dependencies.succ( it_to );
    //     }
  }

#ifdef DIAGNOSTIC_BS  
  printf( "INITIAL\n" );
  d_mx.print();
#endif

  int num_deps = 0;
  bool removed;
  do {
#ifdef DIAGNOSTIC_BS  
    printf( "\n\nSTART\n" );
    d_mx.print();
#endif
    removed = false;

    for( int i = 0 ; i < n ; i++ ) { /* for each node i */
      if( !d_mx.node_checked( i ) ) {
	int from, to;
	if( ( removed = zoop( d_mx, i, n, from, to ) ) == true ) {
	  d_mx( from, to ) = 0;
	  d_mx.zero_nodes();
	  dep_from = index_to_tag[from];
	  dep_to = index_to_tag[to];
	  to_remove.append( dep_from );
	  to_remove.append( dep_to );

	  //#ifdef DIAGNOSTIC_BS
	  cerr << "REMOVING ( " << dep_from << ", " <<  dep_to << " )\n";
	  //#endif
	  num_deps++;
	  //	  if( dep_from == dep_to ) return num_deps;
	  break;
	}
      }
    }
  } while( removed );

  cerr << "DONE\n";
  return num_deps;
}

bool zoop( dep_matrix &d_mx, const int i, const int n, int &from, int &to ) {
#ifdef DIAGNOSTIC_BS  
  printf( "node = %d\n", i );
#endif
  d_mx.node_in_loop( i ) = 1;
  for( int j = 0 ; j < n ; j++ ) {
    if( d_mx( i, j ) ) {
#ifdef DIAGNOSTIC_BS  
      printf( "checking %d->%d\n", i, j );
#endif
      if( d_mx.node_in_loop( j ) ) {
#ifdef DIAGNOSTIC_BS
	printf( "removing %d->%d\n", i, j );
#endif
	from = i; to = j;
	return true;
      } else {
	if( zoop( d_mx, j, n, from, to ) ) return true;
      }
    }
  }
  d_mx.node_in_loop( i ) = 0;
  d_mx.node_checked( i ) = 1;
  return false;
}

/* TEST */
/*#include <LEDA/basic.h>
int main( void ) {
  dep_list dependencies;
  dep_list to_remove;
  
  printf( "enter dep_list\n " );
  dep_pair dep;
  while( scanf( "%ld,%ld", &( dep.from ), &( dep.to ) ) == 2 ) {
    dependencies.append( dep );
    printf( "APPENDED ( %ld, %ld )\n> ", dep.from, dep.to );
  }
  
  int n = remove_dependencies( dependencies, to_remove );
  printf( "\n\nREMOVED %d TOTAL\n", n );
  
  forall( dep, to_remove ) {
    printf( "REMOVED ( %ld, %ld )\n", dep.from, dep.to );
  }
  
  return 0;
}*/

#ifdef DIAGNOSTIC_BS
#undef DIAGNOSTIC_BS
#endif
