const LinkedList = require ( './linkedlist' ) . LinkedList ; exports . linebreak = function ( ) { preserve var linebreak = function ( nodes , lines , settings ) { var options = { demerits : { line : settings && settings . demerits && settings . demerits . line || 10 , flagged : settings && settings . demerits && settings . demerits . flagged || 100 , fitness : settings && settings . demerits && settings . demerits . fitness || 3000 } , tolerance : settings && settings . tolerance || 2 } , activeNodes = new LinkedList ( ) , sum = { width : 0 , stretch : 0 , shrink : 0 } , lineLengths = lines , breaks = [ ] , tmp = { data : { demerits : Infinity } } ; function breakpoint ( position , demerits , ratio , line , fitnessClass , totals , previous ) { return { position : position , demerits : demerits , ratio : ratio , line : line , fitnessClass : fitnessClass , totals : totals || { width : 0 , stretch : 0 , shrink : 0 } , previous : previous } ; } function computeCost ( start , end , active , currentLine ) { var width = sum . width - active . totals . width , stretch = 0 , shrink = 0 , lineLength = lineLengths ( currentLine - 1 ) ; if ( lineLength === null ) { return null ; } if ( nodes [ end ] . type === 'penalty' ) { width += nodes [ end ] . width ; } if ( width < lineLength ) { stretch = sum . stretch - active . totals . stretch ; if ( stretch > 0 ) { return ( lineLength - width ) / stretch ; } else { return linebreak . infinity ; } } else if ( width > lineLength ) { shrink = sum . shrink - active . totals . shrink ; if ( shrink > 0 ) { return ( lineLength - width ) / shrink ; } else { return linebreak . infinity ; } } else { return 0 ; } } function computeSum ( breakPointIndex ) { var result = { width : sum . width , stretch : sum . stretch , shrink : sum . shrink } , i = 0 ; for ( i = breakPointIndex ; i < nodes . length ; i += 1 ) { if ( nodes [ i ] . type === 'glue' ) { result . width += nodes [ i ] . width ; result . stretch += nodes [ i ] . stretch ; result . shrink += nodes [ i ] . shrink ; } else if ( nodes [ i ] . type === 'box' || ( nodes [ i ] . type === 'penalty' && nodes [ i ] . penalty === - linebreak . infinity && i > breakPointIndex ) ) { break ; } } return result ; } function mainLoop ( node , index , nodes ) { var active = activeNodes . first ( ) , next = null , ratio = 0 , demerits = 0 , candidates = [ ] , badness , currentLine = 0 , tmpSum , currentClass = 0 , fitnessClass , candidate , newNode ; while ( active !== null ) { candidates = [ { demerits : Infinity } , { demerits : Infinity } , { demerits : Infinity } , { demerits : Infinity } ] ; while ( active !== null ) { next = active . next ; currentLine = active . data . line + 1 ; ratio = computeCost ( active . data . position , index , active . data , currentLine ) ; if ( ratio === null ) { active = null ; break ; } if ( ratio < - 1 || ( node . type === 'penalty' && node . penalty === - linebreak . infinity ) ) { activeNodes . remove ( active ) ; } if ( - 1 <= ratio && ratio <= options . tolerance ) { badness = 100 * Math . pow ( Math . abs ( ratio ) , 3 ) ; if ( node . type === 'penalty' && node . penalty >= 0 ) { demerits = Math . pow ( options . demerits . line + badness , 2 ) + Math . pow ( node . penalty , 2 ) ; } else if ( node . type === 'penalty' && node . penalty !== - linebreak . infinity ) { demerits = Math . pow ( options . demerits . line + badness , 2 ) - Math . pow ( node . penalty , 2 ) ; } else { demerits = Math . pow ( options . demerits . line + badness , 2 ) ; } if ( node . type === 'penalty' && nodes [ active . data . position ] . type === 'penalty' ) { demerits += options . demerits . flagged * node . flagged * nodes [ active . data . position ] . flagged ; } if ( ratio < - 0.5 ) { currentClass = 0 ; } else if ( ratio <= 0.5 ) { currentClass = 1 ; } else if ( ratio <= 1 ) { currentClass = 2 ; } else { currentClass = 3 ; } if ( Math . abs ( currentClass - active . data . fitnessClass ) > 1 ) { demerits += options . demerits . fitness ; } demerits += active . data . demerits ; if ( demerits < candidates [ currentClass ] . demerits ) { candidates [ currentClass ] = { active : active , demerits : demerits , ratio : ratio } ; } } active = next ; if ( active !== null && active . data . line >= currentLine ) { break ; } } tmpSum = computeSum ( index ) ; for ( fitnessClass = 0 ; fitnessClass < candidates . length ; fitnessClass += 1 ) { candidate = candidates [ fitnessClass ] ; if ( candidate . demerits < Infinity ) { newNode = new LinkedList . Node ( breakpoint ( index , candidate . demerits , candidate . ratio , candidate . active . data . line + 1 , fitnessClass , tmpSum , candidate . active ) ) ; if ( active !== null ) { activeNodes . insertBefore ( active , newNode ) ; } else { activeNodes . push ( newNode ) ; } } } } } activeNodes . push ( new LinkedList . Node ( breakpoint ( 0 , 0 , 0 , 0 , 0 , undefined , null ) ) ) ; nodes . forEach ( function ( node , index , nodes ) { if ( node . type === 'box' ) { sum . width += node . width ; } else if ( node . type === 'glue' ) { if ( index > 0 && nodes [ index - 1 ] . type === 'box' ) { mainLoop ( node , index , nodes ) ; } sum . width += node . width ; sum . stretch += node . stretch ; sum . shrink += node . shrink ; } else if ( node . type === 'penalty' && node . penalty !== linebreak . infinity ) { mainLoop ( node , index , nodes ) ; } } ) ; if ( activeNodes . size ( ) !== 0 ) { activeNodes . forEach ( function ( node ) { if ( node . data . demerits < tmp . data . demerits ) { tmp = node ; } } ) ; while ( tmp !== null ) { breaks . push ( { position : tmp . data . position , ratio : tmp . data . ratio } ) ; tmp = tmp . data . previous ; } return breaks . reverse ( ) ; } return [ ] ; } ; linebreak . infinity = 10000 ; linebreak . glue = function ( width , stretch , shrink ) { return { type : 'glue' , width : width , stretch : stretch , shrink : shrink } ; } ; linebreak . box = function ( width , value ) { return { type : 'box' , width : width , value : value } ; } ; linebreak . penalty = function ( width , penalty , flagged ) { return { type : 'penalty' , width : width , penalty : penalty , flagged : flagged } ; } ; return linebreak ; } ;