import type { Transition , XEvent , compare } from "../types" ; /** Priority queue */ export abstract class List { public nodes : XEvent [ ] = [ ] ; /** 執行二元搜尋時的比較函數 */ protected abstract check ( ev , that ) ; private search ( x ) { let lo = 0 , hi = this . nodes . length ; while ( lo < hi ) { let mid = lo + hi >>> 1 ; let c = this . check ( x , this . nodes [ mid ] ) ; if ( c > 0 ) hi = mid ; else lo = mid + 1 ; } return lo ; } public getIndex ( node ) { return this . nodes . indexOf ( node ) ; } public isEmpty ( ) { return this . nodes . length === 0 ; } public getHead ( ) { return this . nodes [ 0 ] ; } public findTransition ( node ) { let i = this . search ( node ) ; return { before : i === 0 ? null : this . nodes [ i - 1 ] , after : this . nodes [ i ] || null , insert : ( n ) : XEvent => { this . nodes . splice ( i , 0 , n ) ; return n ; } , } ; } public remove ( node ) { this . nodes . splice ( this . getIndex ( node ) , 1 ) ; } }