import { isEmptyObject } from './base/types' ; import { forEach } from './base/collections' ; export interface Node < T > { data : T ; incoming : { [ key ] : Node < T > ; } ; outgoing : { [ key ] : Node < T > ; } ; } function newNode < T > ( data ) { return { data : data , incoming : Object . create ( null ) , outgoing : Object . create ( null ) } ; } export class Graph < T > { private _nodes : { [ key ] : Node < T > ; } = Object . create ( null ) ; constructor ( private _hashFn ) { } roots ( ) { const ret = [ ] ; forEach ( this . _nodes , entry => { if ( isEmptyObject ( entry . value . outgoing ) ) { ret . push ( entry . value ) ; } } ) ; return ret ; } insertEdge ( from , to ) { const fromNode = this . lookupOrInsertNode ( from ) , toNode = this . lookupOrInsertNode ( to ) ; fromNode . outgoing [ this . _hashFn ( to ) ] = toNode ; toNode . incoming [ this . _hashFn ( from ) ] = fromNode ; } removeNode ( data ) { const key = this . _hashFn ( data ) ; delete this . _nodes [ key ] ; forEach ( this . _nodes , ( entry ) => { delete entry . value . outgoing [ key ] ; delete entry . value . incoming [ key ] ; } ) ; } lookupOrInsertNode ( data ) { const key = this . _hashFn ( data ) ; let node = this . _nodes [ key ] ; if ( ! node ) { node = newNode ( data ) ; this . _nodes [ key ] = node ; } return node ; } lookup ( data ) { return this . _nodes [ this . _hashFn ( data ) ] ; } isEmpty ( ) { for ( const _key in this . _nodes ) { return false ; } return true ; } toString ( ) { let data = [ ] ; forEach ( this . _nodes , entry => { data . push ( `${ entry . key }, (incoming)[${ Object . keys ( entry . value . incoming ) . join ( ', ' ) }], (outgoing)[${ Object . keys ( entry . value . outgoing ) . join ( ',' ) }]` ) ; } ) ; return data . join ( '\n' ) ; } }