import { Rectangle } from '@pixi/math' ; import { Area , AreaOrientation } from './Area' ; import type { AreaAllocator } from './AreaAllocator' ; import type { AreaField } from './Area' ; public ignore export type AreaNode = [ AreaNode , AreaField , boolean ] | [ AreaNode , AreaField , AreaNode [ ] ] ; public ignore export type AreaPtr = { __mem_area : AreaNode ; } ; public ignore export enum SPLIT_ORIENTATION { HOR = 0 , VERT = 1 , NONE = 2 } const tempRect = new Rectangle ( ) ; public export class GuilloteneAllocator implements AreaAllocator < AreaPtr > { protected _root : AreaNode ; private _width : number ; private _height : number ; constructor ( width , height ) { this . _width = width ; this . _height = height ; this . _root = [ null , Area . makeArea ( 0 , this . _height , AreaOrientation . HORIZONTAL ) , false ] ; } param width param height param rect return allocate ( width , height , rect ? ) { const area = this . findArea ( width , height ) ; if ( ! area ) { return null ; } if ( ! rect ) { rect = new Rectangle ( ) ; } this . getFrame ( area , rect ) ; const hole = new Rectangle ( rect . x , rect . y , width , height ) ; const node = this . split ( area , rect , hole ) ; rect . copyFrom ( hole ) ; ( rect as any ) . __mem_area = node ; return rect as ( Rectangle & AreaPtr ) ; } /**
     * Frees the area represented by the given area pointer. The original rectangle returned by
     *  GuilloteneAllocator included this pointer (the `__mem_area` property).
     *
     *  param areaPtr free ( areaPtr ) { const area = areaPtr . __mem_area ; area [ 2 ] = false ; this . merge ( area ) ; } get width ( ) : number { return this . _width ; } get height ( ) : number { return this . _height ; } /**
     * Returns the [area] Area data for the node.
     *
     *  param node returns protected getAreaField ( node ) { return node [ 1 ] ; } param node param rect return protected getFrame ( node , rect ? ) { if ( ! rect ) { rect = new Rectangle ( ) ; } const nodeArea = this . getAreaField ( node ) ; const nodeParent = this . getParent ( node ) ; const nodeOrientation = Area . getOrientation ( nodeArea ) ; const nodeOpen = Area . getOpenOffset ( nodeArea ) ; const nodeClose = Area . getCloseOffset ( nodeArea ) ; const parentOpen = nodeParent ? Area . getOpenOffset ( nodeParent [ 1 ] ) : 0 ; const parentClose = nodeParent ? Area . getCloseOffset ( nodeParent [ 1 ] ) : this . _width ; if ( nodeOrientation ) { rect . x = nodeOpen ; rect . y = parentOpen ; rect . width = nodeClose - rect . x ; rect . height = parentClose - parentOpen ; } else { rect . x = parentOpen ; rect . y = nodeOpen ; rect . width = parentClose - rect . x ; rect . height = nodeClose - rect . y ; } return rect ; } param node return protected getParent ( node ) { return node [ 0 ] ; } param node return protected hasChildren ( node ) { return ( Array . isArray ( node [ 2 ] ) && ( node [ 2 ] . length !== 0 ) ) ; } param node protected getChildren ( node ) { if ( ! Array . isArray ( node [ 2 ] ) ) { throw new Error ( "Children don't exist" ) ; } return node [ 2 ] ; } protected addChild ( parent , ... nodes ) { parent [ 2 ] = Array . isArray ( parent [ 2 ] ) ? parent [ 2 ] : [ ] ; parent [ 2 ] . push ( ... nodes ) ; } param aw param ah protected findArea ( aw , ah ) { return this . findAreaRecursive ( this . _root , aw , ah ) ; } /**
     * The recursive implementation for  AreaAllocator .
     *
     *  param rootArea param aw param ah protected findAreaRecursive ( rootArea , aw , ah ) { const frame = this . getFrame ( rootArea , tempRect ) ; if ( frame . width < aw || frame . height < ah ) { return null ; } if ( ! this . hasChildren ( rootArea ) ) { const dx = frame . width - aw ; const dy = frame . height - ah ; if ( dx < 0 || dy < 0 || rootArea [ 2 ] ) { return null ; } return rootArea ; } const children = this . getChildren ( rootArea ) ; let bestCandidate = null ; let bestCandidateScore = Infinity ; for ( let i = 0 , j = children . length ; i < j ; i ++ ) { const candidate = this . findAreaRecursive ( children [ i ] , aw , ah ) ; if ( ! candidate ) { continue ; } const candidateFrame = this . getFrame ( candidate , tempRect ) ; const dx = candidateFrame . width - aw ; const dy = candidateFrame . height - ah ; if ( dx < 0 || dy < 0 ) { continue ; } if ( ! dx && ! dy ) { return candidate ; } const score = Math . min ( dx , dy ) ; if ( bestCandidateScore > score ) { bestCandidate = candidate ; bestCandidateScore = score ; } } return bestCandidate ; } /**
     * Returns the orientation of the primary split of host.
     */ protected splitOrientation ( host , hole ) { if ( hole . width === host . width && hole . height === host . height ) { return SPLIT_ORIENTATION . NONE ; } if ( hole . width === host . width ) { return SPLIT_ORIENTATION . VERT ; } if ( hole . height === host . height ) { return SPLIT_ORIENTATION . HOR ; } const horAreaDiff = Math . abs ( ( host . width - hole . width ) * host . height - hole . width * ( host . height - hole . height ) ) ; const verAreaDiff = Math . abs ( host . width * ( host . height - hole . height ) - ( host . width - hole . width ) * hole . height ) ; if ( horAreaDiff > verAreaDiff ) { return SPLIT_ORIENTATION . HOR ; } else { return SPLIT_ORIENTATION . VERT ; } } protected split ( area , areaFrame , holeFrame , orientation = this . getParent ( area ) ? this . splitOrientation ( areaFrame , holeFrame ) : SPLIT_ORIENTATION . HOR ) { if ( area [ 2 ] === true ) { throw new Error ( 'Cannot deallocate' ) ; } if ( orientation === SPLIT_ORIENTATION . NONE ) { area [ 2 ] = true ; return area ; } return this [ orientation === SPLIT_ORIENTATION . HOR ? 'splitPrimaryHorizontal' : 'splitPrimaryVertical' ] ( area , areaFrame , holeFrame ) ; } private splitPrimaryHorizontal ( area , areaFrame , holeFrame ) { const field = this . getAreaField ( area ) ; const axis = Area . getOrientation ( field ) ; const parent = this . getParent ( area ) ; if ( this . hasChildren ( area ) ) { throw new Error ( "Can't split non-leaf node" ) ; } const firstChild = [ area , Area . makeArea ( areaFrame . left , areaFrame . x + holeFrame . width , AreaOrientation . VERTICAL ) , [ ] ] ; const secondChild = [ area , Area . makeArea ( areaFrame . x + holeFrame . width , areaFrame . right , AreaOrientation . VERTICAL ) , false ] ; if ( axis === AreaOrientation . HORIZONTAL ) { this . addChild ( area , firstChild , secondChild ) ; } else { const i = this . getChildren ( parent ) . indexOf ( area ) ; firstChild [ 0 ] = parent ; secondChild [ 0 ] = parent ; this . getChildren ( parent ) . splice ( i , 1 , firstChild , secondChild ) ; } if ( holeFrame . height !== areaFrame . height ) { const secondaryFirstChild = [ firstChild , Area . makeArea ( areaFrame . top , areaFrame . y + holeFrame . height , AreaOrientation . HORIZONTAL ) , true ] ; const secondarySecondChild = [ firstChild , Area . makeArea ( areaFrame . y + holeFrame . height , areaFrame . bottom , AreaOrientation . HORIZONTAL ) , false ] ; this . addChild ( firstChild , secondaryFirstChild , secondarySecondChild ) ; return secondaryFirstChild ; } else { ( firstChild as AreaNode ) [ 2 ] = true ; } return firstChild ; } private splitPrimaryVertical ( area , areaFrame , holeFrame ) { const field = this . getAreaField ( area ) ; const axis = Area . getOrientation ( field ) ; const parent = this . getParent ( area ) ; if ( this . hasChildren ( area ) ) { throw new Error ( "Can't split non-leaf node" ) ; } const primaryFirstChild = [ area , Area . makeArea ( areaFrame . top , areaFrame . y + holeFrame . height , AreaOrientation . HORIZONTAL ) , [ ] ] ; const primarySecondChild = [ area , Area . makeArea ( areaFrame . y + holeFrame . height , areaFrame . bottom , AreaOrientation . HORIZONTAL ) , false ] ; if ( axis === AreaOrientation . VERTICAL ) { this . addChild ( area , primaryFirstChild , primarySecondChild ) ; } else { const i = this . getChildren ( parent ) . indexOf ( area ) ; primaryFirstChild [ 0 ] = parent ; primarySecondChild [ 0 ] = parent ; this . getChildren ( parent ) . splice ( i , 1 , primaryFirstChild , primarySecondChild ) ; } if ( holeFrame . width !== areaFrame . height ) { const secondaryFirstChild = [ primaryFirstChild , Area . makeArea ( areaFrame . left , areaFrame . x + holeFrame . width , AreaOrientation . VERTICAL ) , true ] ; const secondarySecondChild = [ primaryFirstChild , Area . makeArea ( areaFrame . x + holeFrame . width , areaFrame . right , AreaOrientation . VERTICAL ) , false ] ; this . addChild ( primaryFirstChild , secondaryFirstChild , secondarySecondChild ) ; return secondaryFirstChild ; } else { ( primaryFirstChild as AreaNode ) [ 2 ] = true ; } return primaryFirstChild ; } protected merge ( area ) { if ( this . hasChildren ( area ) ) { throw new Error ( "Cannot merge a non-leaf node" ) ; } const parent = this . getParent ( area ) ; if ( ! parent ) { return ; } const siblings = this . getChildren ( parent ) ; const i = siblings . indexOf ( area ) ; const leftSibling = siblings [ i - 1 ] ; const rightSibling = siblings [ i + 1 ] ; if ( rightSibling && rightSibling [ 2 ] === false ) { area [ 1 ] = Area . setCloseOffset ( area [ 1 ] , Area . getCloseOffset ( rightSibling [ 1 ] ) ) ; siblings . splice ( i + 1 , 1 ) ; } if ( leftSibling && leftSibling [ 2 ] === false ) { area [ 1 ] = Area . setOpenOffset ( area [ 1 ] , Area . getOpenOffset ( leftSibling [ 1 ] ) ) ; siblings . splice ( i - 1 , 1 ) ; } if ( siblings . length === 1 ) { parent [ 2 ] = false ; this . merge ( parent ) ; } } private printState ( area ) { if ( ! this . hasChildren ( area ) ) { console . log ( { ... this . getFrame ( area ) } , area [ 2 ] ) ; } else { this . getChildren ( area ) . forEach ( n => this . printState ( n ) ) ; } } }