import type { Trie , TrieNodeData } from './types' ; /**
 * Options for create trie.
 */ export interface CreateTrieOptions < T = number > { /**
     * The maximum number of children a parent node can have.
     */ SIGMA_SIZE : number ; /**
     * The zero element of the additional value, we may pass in different types
     * of data, and the added value may perform a variety of different
     * mathematical transformations, so we need to specify a zero element.
     */ ZERO : T ; /**
     * Map a character to an integer in the range [0, SIGMA_SIZE)
     */ idx ( c ) : number ; param prevValue param nextValue mergeAdditionalValues ( prevValue , nextValue ) : T ; } export function createTrie < T = number > ( { SIGMA_SIZE , ZERO , idx , mergeAdditionalValues , } ) { let sz ; const ch = [ ] ; const values = [ ZERO ] ; return { init , insert , match , hasPrefixMatched , find , findAll } ; function init ( ) { if ( ch [ 0 ] === undefined ) ch [ 0 ] = new Uint32Array ( SIGMA_SIZE ) ; else ch [ 0 ] . fill ( 0 ) ; sz = 1 ; } function insert ( str , v , start = 0 , end = str . length ) { let u = 0 ; for ( let i = start ; i < end ; ++ i ) { const c = idx ( str [ i ] ) ; if ( ch [ u ] [ c ] === 0 ) { if ( ch [ sz ] === undefined ) ch [ sz ] = new Uint32Array ( SIGMA_SIZE ) ; else ch [ sz ] . fill ( 0 ) ; values [ sz ] = ZERO ; ch [ u ] [ c ] = sz ++ ; } u = ch [ u ] [ c ] ; } values [ u ] = mergeAdditionalValues ( values [ u ] , v ) ; } function match ( str , start = 0 , end = str . length ) { let i = start ; let u = 0 ; for ( ; i < end ; ++ i ) { const c = idx ( str [ i ] ) ; if ( ch [ u ] [ c ] === 0 ) break ; u = ch [ u ] [ c ] ; } const val = values [ u ] ; return i < end || val === ZERO ? null : val ; } function hasPrefixMatched ( str , start = 0 , end = str . length ) { for ( let i = start , u = 0 ; i < end ; ++ i ) { const c = idx ( str [ i ] ) ; if ( ch [ u ] [ c ] === 0 ) return false ; u = ch [ u ] [ c ] ; const val = values [ u ] ; if ( val !== ZERO ) return true ; } return true ; } function find ( str , start = 0 , end = str . length ) { for ( let i = start , u = 0 ; i < end ; ++ i ) { const c = idx ( str [ i ] ) ; if ( ch [ u ] [ c ] === 0 ) break ; u = ch [ u ] [ c ] ; const val = values [ u ] ; if ( val !== ZERO ) return { end : i + 1 , val } ; } return null ; } function findAll ( str , start = 0 , end = str . length ) { const results = [ ] ; for ( let i = start , u = 0 ; i < end ; ++ i ) { const c = idx ( str [ i ] ) ; if ( ch [ u ] [ c ] === 0 ) break ; u = ch [ u ] [ c ] ; const val = values [ u ] ; if ( val !== ZERO ) results . push ( { end : i + 1 , val } ) ; } return results ; } }