<s> from __future__ import print_function , division , absolute_import <EOL> from functools import reduce as _reduce <EOL> import logging <EOL> log = logging . getLogger ( __name__ ) <EOL> def _toposort ( data ) : <EOL> """<STR_LIT>""" <EOL> if len ( data ) == <NUM_LIT:0> : <EOL> return <EOL> for k , v in data . items ( ) : <EOL> v . discard ( k ) <EOL> extra_items_in_deps = _reduce ( set . union , data . values ( ) ) - set ( data . keys ( ) ) <EOL> data . update ( { item : set ( ) for item in extra_items_in_deps } ) <EOL> while True : <EOL> ordered = sorted ( set ( item for item , dep in data . items ( ) if len ( dep ) == <NUM_LIT:0> ) ) <EOL> if not ordered : <EOL> break <EOL> for item in ordered : <EOL> yield item <EOL> data . pop ( item , None ) <EOL> for dep in sorted ( data . values ( ) ) : <EOL> dep -= set ( ordered ) <EOL> if len ( data ) != <NUM_LIT:0> : <EOL> msg = '<STR_LIT>' <EOL> raise ValueError ( msg . format ( '<STR_LIT>' . join ( repr ( x ) for x in data . keys ( ) ) ) ) <EOL> def pop_key ( data ) : <EOL> '''<STR_LIT>''' <EOL> items = sorted ( data . items ( ) , key = lambda item : ( len ( item [ <NUM_LIT:1> ] ) , item [ <NUM_LIT:0> ] ) ) <EOL> key = items [ <NUM_LIT:0> ] [ <NUM_LIT:0> ] <EOL> data . pop ( key ) <EOL> for dep in data . values ( ) : <EOL> dep . discard ( key ) <EOL> return key <EOL> def _safe_toposort ( data ) : <EOL> """<STR_LIT>""" <EOL> if len ( data ) == <NUM_LIT:0> : <EOL> return <EOL> t = _toposort ( data ) <EOL> while True : <EOL> try : <EOL> value = next ( t ) <EOL> yield value <EOL> except ValueError as err : <EOL> log . debug ( err . args [ <NUM_LIT:0> ] ) <EOL> if not data : <EOL> return <EOL> yield pop_key ( data ) <EOL> t = _toposort ( data ) <EOL> continue <EOL> except StopIteration : <EOL> return <EOL> def toposort ( data , safe = True ) : <EOL> data = { k : set ( v ) for k , v in data . items ( ) } <EOL> if '<STR_LIT>' in data : <EOL> data [ '<STR_LIT>' ] . discard ( '<STR_LIT>' ) <EOL> if safe : <EOL> return list ( _safe_toposort ( data ) ) <EOL> else : <EOL> return list ( _toposort ( data ) ) </s>
