import { FactRecord , FactReference } from '../storage' ; export class TopologicalSorter < T > { private factsVisited : { [ key ] : boolean ; } = { } ; private factsWaiting : { [ key ] : FactRecord [ ] ; } = { } ; private factValue : { [ key ] : T ; } = { } ; sort ( facts , map ) { let factsReceived = [ ] ; let factQueue = facts . slice ( 0 ) ; while ( factQueue . length > 0 ) { const fact = factQueue . shift ( ) ; const predecessorKeys = this . allPredecessors ( fact ) ; const waitingPredecessors = predecessorKeys . filter ( key => { return ! this . factsVisited [ key ] ; } ) ; if ( waitingPredecessors . length === 0 ) { const key = this . factKey ( fact ) ; this . factsVisited [ key ] = true ; const predecessorValues = predecessorKeys . map ( k => { return this . factValue [ k ] ; } ) ; const factValue = map ( predecessorValues , fact ) ; this . factValue [ key ] = factValue ; factsReceived . push ( factValue ) ; const retry = this . factsWaiting [ key ] ; if ( retry ) { retry . forEach ( r => { if ( ! factQueue . some ( f => f . type === r . type && f . hash === r . hash ) ) { factQueue . push ( r ) ; } } ) ; this . factsWaiting [ key ] = null ; } } else { waitingPredecessors . forEach ( key => { let list = this . factsWaiting [ key ] ; if ( ! list ) { list = [ ] ; this . factsWaiting [ key ] = list ; } if ( ! list . some ( f => f . type === fact . type && f . hash === fact . hash ) ) { list . push ( fact ) ; } } ) ; } } return factsReceived ; } finished ( ) { for ( const key in this . factsWaiting ) { if ( this . factsWaiting [ key ] ) { return false ; } } return true ; } private allPredecessors ( fact ) { let predecessors = [ ] ; for ( const role in fact . predecessors ) { const references = fact . predecessors [ role ] ; if ( Array . isArray ( references ) ) { predecessors = predecessors . concat ( references . map ( r => this . factKey ( r ) ) ) ; } else { predecessors . push ( this . factKey ( references ) ) ; } } return predecessors ; } private factKey ( fact ) { return `${ fact . type }:${ fact . hash }` ; } }