packageDocumentation module import { OrderedComparator } from "./Compare" ; import { CloneFunction , shallowClone } from "./SortedArray" ; public export type ComputePriorityFunction < T > = ( value : T ) => number ; public export class PriorityQueue < T > implements Iterable < T > { protected _array : T [ ] = [ ] ; protected readonly _compare : OrderedComparator < T > ; protected readonly _clone : CloneFunction < T > ; param compare param clone note public constructor ( compare , clone = shallowClone ) { this . _compare = compare ; this . _clone = clone ; } /** The number of values in the queue. */ public get length ( ) : number { return this . _array . length ; } /** Returns true if the queue contains no values. */ public get isEmpty ( ) : boolean { return 0 === this . length ; } /** Returns an iterator over the contents of the heap suitable for use in `for-of` loops. */ public [ Symbol . iterator ] ( ) { return this . _array [ Symbol . iterator ] ( ) ; } protected _swap ( a , b ) { const temp = this . _array [ a ] ; this . _array [ a ] = this . _array [ b ] ; this . _array [ b ] = temp ; } protected _heapify ( index ) { let candidate = - 1 ; while ( true ) { const right = 2 * ( index + 1 ) ; const left = right - 1 ; if ( left < this . length && this . _compare ( this . _array [ left ] , this . _array [ index ] ) < 0 ) candidate = left ; else candidate = index ; if ( right < this . length && this . _compare ( this . _array [ right ] , this . _array [ candidate ] ) < 0 ) candidate = right ; if ( candidate !== index ) { this . _swap ( candidate , index ) ; index = candidate ; } else { break ; } } } /**
     * Reorders the queue. This function should only (and *always*) be called when the criteria governing the ordering of items on the queue have changed.
     * For example, a priority queue containing graphics sorted by their distance from the camera would need to be reordered when the position of the camera changes.
     */ public sort ( ) { for ( let i = Math . ceil ( this . length / 2 ) ; i >= 0 ; i -- ) this . _heapify ( i ) ; } param value returns public push ( value ) { const clone = this . _clone ( value ) ; let index = this . length ; this . _array . push ( clone ) ; while ( index !== 0 ) { const parent = Math . floor ( ( index - 1 ) / 2 ) ; if ( this . _compare ( this . _array [ index ] , this . _array [ parent ] ) < 0 ) { this . _swap ( index , parent ) ; index = parent ; } else { break ; } } return clone ; } param value returns public append ( value ) { const clone = this . _clone ( value ) ; this . _array . push ( clone ) ; return clone ; } /** Returns the element at the front of the queue, or `undefined` if the queue is empty. */ public get front ( ) : T | undefined { return this . _peek ( 0 ) ; } returns public pop ( ) { return this . _pop ( 0 ) ; } /** Removes all values from the queue. */ public clear ( ) { this . _array . length = 0 ; } param index returns protected _pop ( index ) { if ( index < 0 || index >= this . length ) return undefined ; const root = this . _array [ index ] ; this . _swap ( index , this . length - 1 ) ; this . _array . length -- ; this . _heapify ( index ) ; return root ; } param index returns protected _peek ( index ) { if ( index < 0 || index >= this . length ) return undefined ; else return this . _array [ index ] ; } }