#NEWLINE# def MinSolution( solutions ) : #NEWLINE# #INDENT# 'Form the piecewise minimum of a sequence of Solutions.\n\n  Args:\n    solutions: a non-empty sequence of Solution objects\n  Returns:\n    values Solution object whose cost is the piecewise minimum of the Solutions\n    provided, and which associates the minimum-cost layout with each piece.\n  ' #NEWLINE# if ( len ( solutions ) == 1 ) : #NEWLINE# #INDENT# return solutions [ 0 ] #NEWLINE# #UNINDENT# factory = SolutionFactory ( ) #NEWLINE# for s in solutions : #NEWLINE# #INDENT# s . Reset ( ) #NEWLINE# #UNINDENT# n = len ( solutions ) #NEWLINE# k_l = 0 #NEWLINE# last_i_min_soln = ( - 1 ) #NEWLINE# last_index = ( - 1 ) #NEWLINE# while ( k_l < INFINITY ) : #NEWLINE# #INDENT# k_h = ( min ( ( s . NextKnot ( ) for s in solutions ) ) - 1 ) #NEWLINE# gradients = [ s . CurGradient ( ) for s in solutions ] #NEWLINE# while True : #NEWLINE# #INDENT# values = [ s . CurValueAt ( k_l ) for s in solutions ] #NEWLINE# ( min_value , min_gradient , i_min_soln ) = min ( ( ( values [ i ] , gradients [ i ] , i ) for i in range ( n ) ) ) #NEWLINE# min_soln = solutions [ i_min_soln ] #NEWLINE# if ( ( i_min_soln != last_i_min_soln ) or ( min_soln . CurIndex ( ) != last_index ) ) : #NEWLINE# #INDENT# factory . Append ( k_l , min_soln . CurSpan ( ) , min_value , min_gradient , min_soln . CurLayout ( ) ) #NEWLINE# last_i_min_soln = i_min_soln #NEWLINE# last_index = min_soln . CurIndex ( ) #NEWLINE# #UNINDENT# distances_to_cross = [ math . ceil ( ( ( values [ i ] - min_value ) / ( min_gradient - gradients [ i ] ) ) ) for i in range ( n ) if ( gradients [ i ] < last_index ) ] #NEWLINE# crossovers = [ ( k_l + d ) for d in distances_to_cross if ( ( k_l + d ) <= k_h ) ] #NEWLINE# if crossovers : #NEWLINE# #INDENT# k_l = min ( crossovers ) #NEWLINE# #UNINDENT# else : #NEWLINE# #INDENT# k_l = ( k_h + 1 ) #NEWLINE# if ( k_l < INFINITY ) : #NEWLINE# #INDENT# for s in solutions : #NEWLINE# #INDENT# s . MoveToMargin ( k_l ) #NEWLINE# #UNINDENT# #UNINDENT# break #NEWLINE# #UNINDENT# #UNINDENT# #UNINDENT# return factory . MkSolution ( )