class AssociativeArrayLink < V > { public prev : this ; public next : this ; constructor ( public value ) { this . prev = this ; this . next = this ; } insertBefore ( item ) { const prev = item . prev = this . prev ; const next = item . next = this ; next . prev = item ; prev . next = item ; } remove ( ) { const prev = this . prev ; const next = this . next ; next . prev = prev ; prev . next = next ; } } class AssociativeArray < K , V > { private $keys : Map < K , AssociativeArrayLink < [ K , V ] > > = new Map ( ) ; private $values : Map < V , AssociativeArrayLink < [ K , V ] > > = new Map ( ) ; private pivot = new AssociativeArrayLink < [ K , V ] > ( < any > null ) ; hasKey ( key ) { return this . $keys . has ( key ) ; } hasValue ( value ) { return this . $values . has ( value ) ; } getValue ( key ) { let link = this . $keys . get ( key ) ; if ( ! link ) return null ; return link . value [ 1 ] ; } getKey ( value ) { let link = this . $values . get ( value ) ; if ( ! link ) return null ; return link . value [ 0 ] ; } deleteKey ( key ) { let link = this . $keys . get ( key ) ; if ( ! link ) return this ; this . $keys . delete ( key ) ; this . $values . delete ( link . value [ 1 ] ) ; link . remove ( ) ; return this ; } deleteValue ( value ) { let link = this . $values . get ( value ) ; if ( ! link ) return this ; this . $keys . delete ( link . value [ 0 ] ) ; this . $values . delete ( value ) ; link . remove ( ) ; return this ; } set ( key , value ) { this . deleteKey ( key ) ; this . deleteValue ( value ) ; let link = new AssociativeArrayLink < [ K , V ] > ( [ key , value ] ) ; this . $keys . set ( key , link ) ; this . $values . set ( value , link ) ; this . pivot . insertBefore ( link ) ; } get size ( ) { return this . $keys . size ; } keys ( ) { return this . $keys . keys ( ) ; } values ( ) { return this . $values . keys ( ) ; } * reversedKeys ( ) { let link = this . pivot . prev ; while ( link !== this . pivot ) { yield link . value [ 0 ] ; link = link . prev ; } } * reversedValues ( ) { let link = this . pivot . prev ; while ( link !== this . pivot ) { yield link . value [ 1 ] ; link = link . prev ; } } clear ( ) { this . $keys . clear ( ) ; this . $values . clear ( ) ; this . pivot . next = this . pivot . prev = this . pivot ; } } class Node { protected inbound : DirectedEdge [ ] = [ ] ; protected outbound : DirectedEdge [ ] = [ ] ; addInbound ( edge ) { this . inbound . push ( edge ) ; } addOutbound ( edge ) { this . outbound . push ( edge ) ; } deleteInbound ( edge ) { let i = this . inbound . indexOf ( edge ) ; if ( i === - 1 ) return ; this . inbound . splice ( i , 1 ) ; } deleteOutbound ( edge ) { let i = this . outbound . indexOf ( edge ) ; if ( i === - 1 ) return ; this . outbound . splice ( i , 1 ) ; } isRoot ( ) { return this . inbound . length === 0 ; } isLeaf ( ) { return this . outbound . length === 0 ; } iterateInboundEdges ( ) { return this . inbound [ Symbol . iterator ] ( ) ; } iterateOutboundEdges ( ) { return this . outbound [ Symbol . iterator ] ( ) ; } * iterateAncestors < T extends Node > ( this ) { yield this ; for ( let inboundEdge of this . inbound ) { yield * ( inboundEdge . source as T ) . iterateAncestors ( ) ; } } } class DirectedEdge { constructor ( public readonly source , public readonly target ) { source . addOutbound ( this ) ; target . addInbound ( this ) ; } } class NodeToVisit extends Node { declare protected inbound : EdgeToVisit [ ] ; declare protected outbound : EdgeToVisit [ ] ; protected visitedOutbound : EdgeToVisit [ ] = [ ] ; setAsVisited ( edge ) { let index = this . outbound . indexOf ( edge ) ; if ( index !== - 1 ) { this . outbound . splice ( index , 1 ) ; this . visitedOutbound . push ( edge ) ; } } resetVisited ( ) { Array . prototype . push . apply ( this . outbound , this . visitedOutbound ) ; this . visitedOutbound = [ ] ; } protected decendents : Set < NodeToVisit > = new Set ( ) ; isDecendent ( node ) { if ( ! node ) return false ; return this . decendents . has ( node ) ; } collectDecendentsFromVisitedEdges ( ) { this . decendents . add ( this ) ; for ( let edge of this . visitedOutbound ) { let target = edge . target ; for ( let decendent of target . decendents ) { this . decendents . add ( decendent ) ; } } } } class EdgeToVisit extends DirectedEdge { declare public readonly source : NodeToVisit ; declare public readonly target : NodeToVisit ; setAsVisited ( ) { this . source . setAsVisited ( this ) ; } } class NodeWithLeaf extends Node { protected leafs : Set < NodeWithLeaf > = new Set ( ) ; addLeaf ( leaf ) { this . leafs . add ( leaf ) ; } getLeafs ( ) { return [ ... this . leafs ] ; } } export class CycleError < I > extends Error { constructor ( public cycle ) { super ( ) ; } } export abstract class DirectedTreeBase < I , N extends Node , E extends DirectedEdge > { protected map : AssociativeArray < I , N > = new AssociativeArray ( ) ; protected iterateNodes ( ) { return this . map . values ( ) ; } protected reverseIterateNodes ( ) { return this . map . reversedValues ( ) ; } protected abstract createNode ( ) ; protected abstract createEdge ( source , target ) ; addNodeById ( id ) { if ( this . map . hasKey ( id ) ) return null ; let node = this . createNode ( ) ; this . map . set ( id , node ) ; return node ; } addEdgeById ( source , target ) { let sourceNode = this . getNodeById ( source ) ; let targetNode = this . getNodeById ( target ) ; if ( sourceNode === null || targetNode === null ) return ; this . createEdge ( sourceNode , targetNode ) ; } getNodeById ( id ) { if ( this . map . hasKey ( id ) ) return this . map . getValue ( id ) ; return this . addNodeById ( id ) ; } getIdOfNode ( node ) { return this . map . getKey ( node ) ; } protected static filterLeafs < N extends Node > ( node ) { return node . isLeaf ( ) ; } private getALeaf ( ) { for ( let node of this . iterateNodes ( ) ) { if ( node . isLeaf ( ) ) return node ; } } private getARoot ( ) { for ( let node of this . iterateNodes ( ) ) { if ( node . isRoot ( ) ) return node ; } } sort ( ) { const size = this . map . size ; const map = new AssociativeArray < I , N > ( ) ; const out = [ ] ; let root ; while ( root = this . getARoot ( ) ) { let id = this . getIdOfNode ( root ) ! ; map . set ( id , root ) ; out . push ( id ) ; this . map . deleteValue ( root ) ; for ( let edge of root . iterateOutboundEdges ( ) ) { edge . target . deleteInbound ( edge ) ; } } if ( map . size !== size ) { throw new CycleError ( this . map . keys ( ) ) ; } for ( let node of map . values ( ) ) { for ( let edge of node . iterateOutboundEdges ( ) ) { edge . target . addInbound ( edge ) ; } } this . map = map ; return out ; } } export class DirectedTree < I > extends DirectedTreeBase < I , Node , DirectedEdge > { protected createNode ( ) { return new Node ( ) ; } protected createEdge ( source , target ) { return new DirectedEdge ( source , target ) ; } } export class DirectedTreeWithOrdering < I > extends DirectedTreeBase < I , NodeToVisit , EdgeToVisit > { protected createNode ( ) { return new NodeToVisit ( ) ; } protected createEdge ( source , target ) { return new EdgeToVisit ( source , target ) ; } populateDecendents ( ) { for ( let node of this . reverseIterateNodes ( ) ) { node . collectDecendentsFromVisitedEdges ( ) ; for ( let edge of node . iterateInboundEdges ( ) ) { ( edge as EdgeToVisit ) . setAsVisited ( ) ; } } for ( let node of this . iterateNodes ( ) ) { node . resetVisited ( ) ; } } getInfimum ( idArray ) { for ( let node of this . reverseIterateNodes ( ) ) { if ( idArray . every ( id => node . isDecendent ( this . getNodeById ( id ) ) ) ) { return this . getIdOfNode ( node ) ! ; } } return null ; } } export class DirectedTreeWithLeafs < I > extends DirectedTreeBase < I , NodeWithLeaf , DirectedEdge > { protected createNode ( ) { return new NodeWithLeaf ( ) ; } protected createEdge ( source , target ) { return new DirectedEdge ( source , target ) ; } private * iterateLeafs ( ) { for ( let node of this . iterateNodes ( ) ) { if ( node . isLeaf ( ) ) yield node ; } } populateLeafs ( ) { for ( let leaf of this . iterateLeafs ( ) ) { for ( let node of leaf . iterateAncestors ( ) ) { node . addLeaf ( leaf ) ; } } } getLeafsOfNode ( id ) { return this . getNodeById ( id ) ! . getLeafs ( ) . map ( this . getIdOfNode , this ) as I [ ] ; } }