export interface SegSpan { start : number ; end : number ; } export interface SegEntry { index : number ; thickness : number ; span : SegSpan ; } export interface SegInsertion { level : number ; levelCoord : number ; lateral : number ; touchingLevel : number ; touchingLateral : number ; touchingEntry : SegEntry ; stackCnt : number ; } export interface SegRect extends SegEntry { levelCoord : number ; } export interface SegEntryGroup { entries : SegEntry [ ] ; span : SegSpan ; } export class SegHierarchy { strictOrder : boolean = false ; allowReslicing : boolean = false ; maxCoord : number = - 1 ; maxStackCnt : number = - 1 ; levelCoords : number [ ] = [ ] ; entriesByLevel : SegEntry [ ] [ ] = [ ] ; stackCnts : { [ entryId ] : number ; } = { } ; addSegs ( inputs ) { let hiddenEntries = [ ] ; for ( let input of inputs ) { this . insertEntry ( input , hiddenEntries ) ; } return hiddenEntries ; } insertEntry ( entry , hiddenEntries ) { let insertion = this . findInsertion ( entry ) ; if ( this . isInsertionValid ( insertion , entry ) ) { this . insertEntryAt ( entry , insertion ) ; return 1 ; } return this . handleInvalidInsertion ( insertion , entry , hiddenEntries ) ; } isInsertionValid ( insertion , entry ) { return ( this . maxCoord === - 1 || insertion . levelCoord + entry . thickness <= this . maxCoord ) && ( this . maxStackCnt === - 1 || insertion . stackCnt < this . maxStackCnt ) ; } handleInvalidInsertion ( insertion , entry , hiddenEntries ) { if ( this . allowReslicing && insertion . touchingEntry ) { return this . splitEntry ( entry , insertion . touchingEntry , hiddenEntries ) ; } hiddenEntries . push ( entry ) ; return 0 ; } splitEntry ( entry , barrier , hiddenEntries ) { let partCnt = 0 ; let splitHiddenEntries = [ ] ; let entrySpan = entry . span ; let barrierSpan = barrier . span ; if ( entrySpan . start < barrierSpan . start ) { partCnt += this . insertEntry ( { index : entry . index , thickness : entry . thickness , span : { start : entrySpan . start , end : barrierSpan . start } , } , splitHiddenEntries ) ; } if ( entrySpan . end > barrierSpan . end ) { partCnt += this . insertEntry ( { index : entry . index , thickness : entry . thickness , span : { start : barrierSpan . end , end : entrySpan . end } , } , splitHiddenEntries ) ; } if ( partCnt ) { hiddenEntries . push ( { index : entry . index , thickness : entry . thickness , span : intersectSpans ( barrierSpan , entrySpan ) , } , ... splitHiddenEntries ) ; return partCnt ; } hiddenEntries . push ( entry ) ; return 0 ; } insertEntryAt ( entry , insertion ) { let { entriesByLevel , levelCoords } = this ; if ( insertion . lateral === - 1 ) { insertAt ( levelCoords , insertion . level , insertion . levelCoord ) ; insertAt ( entriesByLevel , insertion . level , [ entry ] ) ; } else { insertAt ( entriesByLevel [ insertion . level ] , insertion . lateral , entry ) ; } this . stackCnts [ buildEntryKey ( entry ) ] = insertion . stackCnt ; } findInsertion ( newEntry ) { let { levelCoords , entriesByLevel , strictOrder , stackCnts } = this ; let levelCnt = levelCoords . length ; let candidateCoord = 0 ; let touchingLevel = - 1 ; let touchingLateral = - 1 ; let touchingEntry = null ; let stackCnt = 0 ; for ( let trackingLevel = 0 ; trackingLevel < levelCnt ; trackingLevel += 1 ) { let trackingCoord = levelCoords [ trackingLevel ] ; if ( ! strictOrder && trackingCoord >= candidateCoord + newEntry . thickness ) { break ; } let trackingEntries = entriesByLevel [ trackingLevel ] ; let trackingEntry ; let searchRes = binarySearch ( trackingEntries , newEntry . span . start , getEntrySpanEnd ) ; let lateralIndex = searchRes [ 0 ] + searchRes [ 1 ] ; while ( ( trackingEntry = trackingEntries [ lateralIndex ] ) && trackingEntry . span . start < newEntry . span . end ) { let trackingEntryBottom = trackingCoord + trackingEntry . thickness ; if ( trackingEntryBottom > candidateCoord ) { candidateCoord = trackingEntryBottom ; touchingEntry = trackingEntry ; touchingLevel = trackingLevel ; touchingLateral = lateralIndex ; } if ( trackingEntryBottom === candidateCoord ) { stackCnt = Math . max ( stackCnt , stackCnts [ buildEntryKey ( trackingEntry ) ] + 1 ) ; } lateralIndex += 1 ; } } let destLevel = 0 ; if ( touchingEntry ) { destLevel = touchingLevel + 1 ; while ( destLevel < levelCnt && levelCoords [ destLevel ] < candidateCoord ) { destLevel += 1 ; } } let destLateral = - 1 ; if ( destLevel < levelCnt && levelCoords [ destLevel ] === candidateCoord ) { destLateral = binarySearch ( entriesByLevel [ destLevel ] , newEntry . span . end , getEntrySpanEnd ) [ 0 ] ; } return { touchingLevel , touchingLateral , touchingEntry , stackCnt , levelCoord : candidateCoord , level : destLevel , lateral : destLateral , } ; } toRects ( ) { let { entriesByLevel , levelCoords } = this ; let levelCnt = entriesByLevel . length ; let rects = [ ] ; for ( let level = 0 ; level < levelCnt ; level += 1 ) { let entries = entriesByLevel [ level ] ; let levelCoord = levelCoords [ level ] ; for ( let entry of entries ) { rects . push ( { ... entry , levelCoord } ) ; } } return rects ; } } export function getEntrySpanEnd ( entry ) { return entry . span . end ; } export function buildEntryKey ( entry ) { return entry . index + ':' + entry . span . start ; } export function groupIntersectingEntries ( entries ) { let merges = [ ] ; for ( let entry of entries ) { let filteredMerges = [ ] ; let hungryMerge = { span : entry . span , entries : [ entry ] , } ; for ( let merge of merges ) { if ( intersectSpans ( merge . span , hungryMerge . span ) ) { hungryMerge = { entries : merge . entries . concat ( hungryMerge . entries ) , span : joinSpans ( merge . span , hungryMerge . span ) , } ; } else { filteredMerges . push ( merge ) ; } } filteredMerges . push ( hungryMerge ) ; merges = filteredMerges ; } return merges ; } export function joinSpans ( span0 , span1 ) { return { start : Math . min ( span0 . start , span1 . start ) , end : Math . max ( span0 . end , span1 . end ) , } ; } export function intersectSpans ( span0 , span1 ) { let start = Math . max ( span0 . start , span1 . start ) ; let end = Math . min ( span0 . end , span1 . end ) ; if ( start < end ) { return { start , end } ; } return null ; } function insertAt < Item > ( arr , index , item ) { arr . splice ( index , 0 , item ) ; } export function binarySearch < Item > ( a , searchVal , getItemVal ) { let startIndex = 0 ; let endIndex = a . length ; if ( ! endIndex || searchVal < getItemVal ( a [ startIndex ] ) ) { return [ 0 , 0 ] ; } if ( searchVal > getItemVal ( a [ endIndex - 1 ] ) ) { return [ endIndex , 0 ] ; } while ( startIndex < endIndex ) { let middleIndex = Math . floor ( startIndex + ( endIndex - startIndex ) / 2 ) ; let middleVal = getItemVal ( a [ middleIndex ] ) ; if ( searchVal < middleVal ) { endIndex = middleIndex ; } else if ( searchVal > middleVal ) { startIndex = middleIndex + 1 ; } else { return [ middleIndex , 1 ] ; } } return [ startIndex , 0 ] ; }