import Algorithms as algo;
import Text as text;

class DirectedGraph {
	_adjecentVertices = {};
	add_vertex( vertex_ ) {
		_adjecentVertices[vertex_] = [];
	}
	add_edge( from_, to_ ) {
		_adjecentVertices[from_].push( to_ );
	}
	adjecent_vertices( vertex_ ) {
		return ( vertex_ ∈ _adjecentVertices ? _adjecentVertices.get( vertex_ ) : [] );
	}
}

class DepthFirstSearch {
	_visited = set();
	_postOrder = [];
	_cycleDetector = set();
	run( graph_, start_ ) {
		_cycleDetector.insert( start_ );
		_visited.insert( start_ );
		for ( vertex : graph_.adjecent_vertices( start_ ) ) {
			if ( vertex == start_ ) {
				continue;
			}
			if ( vertex ∈ _cycleDetector ) {
				throw Exception( "A cycle involving vertices {} found!".format( _cycleDetector ) );
			}
			if ( vertex ∉ _visited ) {
				run( graph_, vertex );
			}
		}
		_postOrder.push( start_ );
		_cycleDetector.erase( start_ );
	}
	topological_sort( graph_ ) {
		for ( vertex : graph_._adjecentVertices ) {
			if ( vertex ∉ _visited ) {
				run( graph_, vertex );
			}
		}
		return ( _postOrder );
	}
}

main() {
	rawdata =
		"des_system_lib  | std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee\n"
		"dw01            | ieee dw01 dware gtech\n"
		"dw02            | ieee dw02 dware\n"
		"dw03            | std synopsys dware dw03 dw02 dw01 ieee gtech\n"
		"dw04            | dw04 ieee dw01 dware gtech\n"
		"dw05            | dw05 ieee dware\n"
		"dw06            | dw06 ieee dware\n"
		"dw07            | ieee dware\n"
		"dware           | ieee dware\n"
		"gtech           | ieee gtech\n"
		"ramlib          | std ieee\n"
		"std_cell_lib    | ieee std_cell_lib\n"
		"synopsys        |\n";
	dg = DirectedGraph();
	for ( l : algo.filter( text.split( rawdata, "\n" ), @( x ) { size( x ) > 0; } ) ) {
		def = algo.materialize( algo.map( text.split( l, "|" ), string.strip ), list );
		dg.add_vertex( def[0] );
		for ( n : algo.filter( algo.map( text.split( def[1], " " ), string.strip ), @( x ) { size( x ) > 0; } ) ) {
			dg.add_edge( def[0], n );
		}
	}
	dfs = DepthFirstSearch();
	print( "{}\n".format( dfs.topological_sort( dg ) ) );
}