{"version":3,"sources":["../../src/data-structures/base/iterable-element-base.ts","../../src/data-structures/trie/trie.ts","../../src/common/index.ts"],"names":["DFSOperation"],"mappings":";;;;;;AAaO,IAAe,sBAAf,MAAgE;AAAA,EAbvE;AAauE,IAAA,MAAA,CAAA,IAAA,EAAA,qBAAA,CAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAU3D,YAAY,OAAA,EAA4C;AAChE,IAAA,IAAI,OAAA,EAAS;AACX,MAAA,MAAM,EAAE,aAAY,GAAI,OAAA;AACxB,MAAA,IAAI,OAAO,WAAA,KAAgB,UAAA,EAAY,IAAA,CAAK,YAAA,GAAe,WAAA;AAAA,WAAA,IAClD,WAAA,EAAa,MAAM,IAAI,SAAA,CAAU,qCAAqC,CAAA;AAAA,IACjF;AAAA,EACF;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQU,YAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EASV,IAAI,WAAA,GAAkD;AACpD,IAAA,OAAO,IAAA,CAAK,YAAA;AAAA,EACd;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAWA,EAAE,MAAA,CAAO,QAAQ,CAAA,CAAA,GAAK,IAAA,EAAsC;AAC1D,IAAA,OAAO,IAAA,CAAK,YAAA,CAAa,GAAG,IAAI,CAAA;AAAA,EAClC;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EASA,CAAC,MAAA,GAA8B;AAC7B,IAAA,KAAA,MAAW,IAAA,IAAQ,MAAM,MAAM,IAAA;AAAA,EACjC;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAaA,KAAA,CAAM,WAA2C,OAAA,EAA4B;AAC3E,IAAA,IAAI,KAAA,GAAQ,CAAA;AACZ,IAAA,KAAA,MAAW,QAAQ,IAAA,EAAM;AACvB,MAAA,IAAI,YAAY,MAAA,EAAW;AACzB,QAAA,IAAI,CAAC,SAAA,CAAU,IAAA,EAAM,KAAA,EAAA,EAAS,IAAI,GAAG,OAAO,KAAA;AAAA,MAC9C,CAAA,MAAO;AACL,QAAA,MAAM,EAAA,GAAK,SAAA;AACX,QAAA,IAAI,CAAC,GAAG,IAAA,CAAK,OAAA,EAAS,MAAM,KAAA,EAAA,EAAS,IAAI,GAAG,OAAO,KAAA;AAAA,MACrD;AAAA,IACF;AACA,IAAA,OAAO,IAAA;AAAA,EACT;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAYA,IAAA,CAAK,WAA2C,OAAA,EAA4B;AAC1E,IAAA,IAAI,KAAA,GAAQ,CAAA;AACZ,IAAA,KAAA,MAAW,QAAQ,IAAA,EAAM;AACvB,MAAA,IAAI,YAAY,MAAA,EAAW;AACzB,QAAA,IAAI,SAAA,CAAU,IAAA,EAAM,KAAA,EAAA,EAAS,IAAI,GAAG,OAAO,IAAA;AAAA,MAC7C,CAAA,MAAO;AACL,QAAA,MAAM,EAAA,GAAK,SAAA;AACX,QAAA,IAAI,GAAG,IAAA,CAAK,OAAA,EAAS,MAAM,KAAA,EAAA,EAAS,IAAI,GAAG,OAAO,IAAA;AAAA,MACpD;AAAA,IACF;AACA,IAAA,OAAO,KAAA;AAAA,EACT;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAYA,OAAA,CAAQ,YAAyC,OAAA,EAAyB;AACxE,IAAA,IAAI,KAAA,GAAQ,CAAA;AACZ,IAAA,KAAA,MAAW,QAAQ,IAAA,EAAM;AACvB,MAAA,IAAI,YAAY,MAAA,EAAW;AACzB,QAAA,UAAA,CAAW,IAAA,EAAM,SAAS,IAAI,CAAA;AAAA,MAChC,CAAA,MAAO;AACL,QAAA,MAAM,EAAA,GAAK,UAAA;AACX,QAAA,EAAA,CAAG,IAAA,CAAK,OAAA,EAAS,IAAA,EAAM,KAAA,EAAA,EAAS,IAAI,CAAA;AAAA,MACtC;AAAA,IACF;AAAA,EACF;AAAA;AAAA,EAwBA,IAAA,CAAK,WAA2C,OAAA,EAAkC;AAChF,IAAA,IAAI,KAAA,GAAQ,CAAA;AACZ,IAAA,KAAA,MAAW,QAAQ,IAAA,EAAM;AACvB,MAAA,IAAI,YAAY,MAAA,EAAW;AACzB,QAAA,IAAI,SAAA,CAAU,IAAA,EAAM,KAAA,EAAA,EAAS,IAAI,GAAG,OAAO,IAAA;AAAA,MAC7C,CAAA,MAAO;AACL,QAAA,MAAM,EAAA,GAAK,SAAA;AACX,QAAA,IAAI,GAAG,IAAA,CAAK,OAAA,EAAS,MAAM,KAAA,EAAA,EAAS,IAAI,GAAG,OAAO,IAAA;AAAA,MACpD;AAAA,IACF;AACA,IAAA;AAAA,EACF;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAWA,IAAI,OAAA,EAAqB;AACvB,IAAA,KAAA,MAAW,GAAA,IAAO,IAAA,EAAM,IAAI,GAAA,KAAQ,SAAS,OAAO,IAAA;AACpD,IAAA,OAAO,KAAA;AAAA,EACT;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EA2BA,MAAA,CAAU,YAA4C,YAAA,EAAqB;AACzE,IAAA,IAAI,KAAA,GAAQ,CAAA;AACZ,IAAA,MAAM,IAAA,GAAO,IAAA,CAAK,MAAA,CAAO,QAAQ,CAAA,EAAE;AACnC,IAAA,IAAI,GAAA;AAEJ,IAAA,IAAI,SAAA,CAAU,UAAU,CAAA,EAAG;AACzB,MAAA,GAAA,GAAM,YAAA;AAAA,IACR,CAAA,MAAO;AACL,MAAA,MAAM,KAAA,GAAQ,KAAK,IAAA,EAAK;AACxB,MAAA,IAAI,KAAA,CAAM,IAAA,EAAM,MAAM,IAAI,UAAU,iDAAiD,CAAA;AACrF,MAAA,GAAA,GAAM,KAAA,CAAM,KAAA;AACZ,MAAA,KAAA,GAAQ,CAAA;AAAA,IACV;AAEA,IAAA,KAAA,MAAW,SAAS,IAAA,EAAgC;AAClD,MAAA,GAAA,GAAM,UAAA,CAAW,GAAA,EAAK,KAAA,EAAO,KAAA,EAAA,EAAS,IAAI,CAAA;AAAA,IAC5C;AACA,IAAA,OAAO,GAAA;AAAA,EACT;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EASA,OAAA,GAAe;AACb,IAAA,OAAO,CAAC,GAAG,IAAI,CAAA;AAAA,EACjB;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAUA,QAAA,GAAgB;AACd,IAAA,OAAO,CAAC,GAAG,IAAI,CAAA;AAAA,EACjB;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EASA,KAAA,GAAc;AACZ,IAAA,OAAA,CAAQ,GAAA,CAAI,IAAA,CAAK,QAAA,EAAU,CAAA;AAAA,EAC7B;AAkFF,CAAA;;;AChVO,IAAM,WAAN,MAAe;AAAA,EAftB;AAesB,IAAA,MAAA,CAAA,IAAA,EAAA,UAAA,CAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAOpB,YAAY,GAAA,EAAa;AACvB,IAAA,IAAA,CAAK,IAAA,GAAO,GAAA;AACZ,IAAA,IAAA,CAAK,MAAA,GAAS,KAAA;AACd,IAAA,IAAA,CAAK,SAAA,uBAAgB,GAAA,EAAsB;AAAA,EAC7C;AAAA,EAEU,IAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQV,IAAI,GAAA,GAAc;AAChB,IAAA,OAAO,IAAA,CAAK,IAAA;AAAA,EACd;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EASA,IAAI,IAAI,KAAA,EAAe;AACrB,IAAA,IAAA,CAAK,IAAA,GAAO,KAAA;AAAA,EACd;AAAA,EAEU,SAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQV,IAAI,QAAA,GAAkC;AACpC,IAAA,OAAO,IAAA,CAAK,SAAA;AAAA,EACd;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EASA,IAAI,SAAS,KAAA,EAA8B;AACzC,IAAA,IAAA,CAAK,SAAA,GAAY,KAAA;AAAA,EACnB;AAAA,EAEU,MAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQV,IAAI,KAAA,GAAiB;AACnB,IAAA,OAAO,IAAA,CAAK,MAAA;AAAA,EACd;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EASA,IAAI,MAAM,KAAA,EAAgB;AACxB,IAAA,IAAA,CAAK,MAAA,GAAS,KAAA;AAAA,EAChB;AACF;AAiKO,IAAM,IAAA,GAAN,cAA4B,mBAAA,CAA+B;AAAA,EAjQlE;AAiQkE,IAAA,MAAA,CAAA,IAAA,EAAA,MAAA,CAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAShE,WAAA,CAAY,KAAA,GAAwC,EAAC,EAAG,OAAA,EAA0B;AAChF,IAAA,KAAA,CAAM,OAAO,CAAA;AACb,IAAA,IAAI,OAAA,EAAS;AACX,MAAA,MAAM,EAAE,eAAc,GAAI,OAAA;AAC1B,MAAA,IAAI,aAAA,KAAkB,MAAA,EAAW,IAAA,CAAK,cAAA,GAAiB,aAAA;AAAA,IACzD;AACA,IAAA,IAAI,KAAA,EAAO;AACT,MAAA,IAAA,CAAK,QAAQ,KAAK,CAAA;AAAA,IACpB;AAAA,EACF;AAAA,EAEU,KAAA,GAAgB,CAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQ1B,IAAI,IAAA,GAAe;AACjB,IAAA,OAAO,IAAA,CAAK,KAAA;AAAA,EACd;AAAA,EAEU,cAAA,GAA0B,IAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQpC,IAAI,aAAA,GAAyB;AAC3B,IAAA,OAAO,IAAA,CAAK,cAAA;AAAA,EACd;AAAA,EAEU,KAAA,GAAkB,IAAI,QAAA,CAAS,EAAE,CAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQ3C,IAAI,IAAA,GAAO;AACT,IAAA,OAAO,IAAA,CAAK,KAAA;AAAA,EACd;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,IAAc,MAAA,GAAS;AACrB,IAAA,OAAO,IAAA,CAAK,KAAA;AAAA,EACd;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EASA,IAAI,IAAA,EAAuB;AACzB,IAAA,IAAA,GAAO,IAAA,CAAK,aAAa,IAAI,CAAA;AAC7B,IAAA,IAAI,MAAM,IAAA,CAAK,IAAA;AACf,IAAA,IAAI,SAAA,GAAY,KAAA;AAChB,IAAA,KAAA,MAAW,KAAK,IAAA,EAAM;AACpB,MAAA,IAAI,KAAA,GAAQ,GAAA,CAAI,QAAA,CAAS,GAAA,CAAI,CAAC,CAAA;AAC9B,MAAA,IAAI,CAAC,KAAA,EAAO;AACV,QAAA,KAAA,GAAQ,IAAI,SAAS,CAAC,CAAA;AACtB,QAAA,GAAA,CAAI,QAAA,CAAS,GAAA,CAAI,CAAA,EAAG,KAAK,CAAA;AAAA,MAC3B;AACA,MAAA,GAAA,GAAM,KAAA;AAAA,IACR;AACA,IAAA,IAAI,CAAC,IAAI,KAAA,EAAO;AACd,MAAA,SAAA,GAAY,IAAA;AACZ,MAAA,GAAA,CAAI,KAAA,GAAQ,IAAA;AACZ,MAAA,IAAA,CAAK,KAAA,EAAA;AAAA,IACP;AACA,IAAA,OAAO,SAAA;AAAA,EACT;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EASA,QAAQ,KAAA,EAAkD;AACxD,IAAA,MAAM,MAAiB,EAAC;AACxB,IAAA,KAAA,MAAW,QAAQ,KAAA,EAAO;AACxB,MAAA,IAAI,KAAK,WAAA,EAAa;AACpB,QAAA,GAAA,CAAI,KAAK,IAAA,CAAK,GAAA,CAAI,KAAK,WAAA,CAAY,IAAS,CAAC,CAAC,CAAA;AAAA,MAChD,CAAA,MAAO;AACL,QAAA,GAAA,CAAI,IAAA,CAAK,IAAA,CAAK,GAAA,CAAI,IAAc,CAAC,CAAA;AAAA,MACnC;AAAA,IACF;AACA,IAAA,OAAO,GAAA;AAAA,EACT;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EASS,IAAI,IAAA,EAAuB;AAClC,IAAA,IAAA,GAAO,IAAA,CAAK,aAAa,IAAI,CAAA;AAC7B,IAAA,IAAI,MAAM,IAAA,CAAK,IAAA;AACf,IAAA,KAAA,MAAW,KAAK,IAAA,EAAM;AACpB,MAAA,MAAM,KAAA,GAAQ,GAAA,CAAI,QAAA,CAAS,GAAA,CAAI,CAAC,CAAA;AAChC,MAAA,IAAI,CAAC,OAAO,OAAO,KAAA;AACnB,MAAA,GAAA,GAAM,KAAA;AAAA,IACR;AACA,IAAA,OAAO,GAAA,CAAI,KAAA;AAAA,EACb;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,OAAA,GAAmB;AACjB,IAAA,OAAO,KAAK,KAAA,KAAU,CAAA;AAAA,EACxB;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,KAAA,GAAc;AACZ,IAAA,IAAA,CAAK,KAAA,GAAQ,CAAA;AACb,IAAA,IAAA,CAAK,KAAA,GAAQ,IAAI,QAAA,CAAS,EAAE,CAAA;AAAA,EAC9B;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EASA,OAAO,IAAA,EAAuB;AAC5B,IAAA,IAAA,GAAO,IAAA,CAAK,aAAa,IAAI,CAAA;AAC7B,IAAA,IAAI,SAAA,GAAY,KAAA;AAChB,IAAA,MAAM,GAAA,mBAAM,MAAA,CAAA,CAAC,GAAA,EAAe,CAAA,KAAuB;AACjD,MAAA,MAAM,IAAA,GAAO,KAAK,CAAC,CAAA;AACnB,MAAA,MAAM,KAAA,GAAQ,GAAA,CAAI,QAAA,CAAS,GAAA,CAAI,IAAI,CAAA;AACnC,MAAA,IAAI,KAAA,EAAO;AACT,QAAA,IAAI,CAAA,KAAM,IAAA,CAAK,MAAA,GAAS,CAAA,EAAG;AACzB,UAAA,IAAI,MAAM,KAAA,EAAO;AACf,YAAA,IAAI,KAAA,CAAM,QAAA,CAAS,IAAA,GAAO,CAAA,EAAG;AAC3B,cAAA,KAAA,CAAM,KAAA,GAAQ,KAAA;AAAA,YAChB,CAAA,MAAO;AACL,cAAA,GAAA,CAAI,QAAA,CAAS,OAAO,IAAI,CAAA;AAAA,YAC1B;AACA,YAAA,SAAA,GAAY,IAAA;AACZ,YAAA,OAAO,IAAA;AAAA,UACT;AACA,UAAA,OAAO,KAAA;AAAA,QACT;AACA,QAAA,MAAM,GAAA,GAAM,GAAA,CAAI,KAAA,EAAO,CAAA,GAAI,CAAC,CAAA;AAC5B,QAAA,IAAI,OAAO,CAAC,GAAA,CAAI,SAAS,KAAA,CAAM,QAAA,CAAS,SAAS,CAAA,EAAG;AAClD,UAAA,GAAA,CAAI,QAAA,CAAS,OAAO,IAAI,CAAA;AACxB,UAAA,OAAO,IAAA;AAAA,QACT;AACA,QAAA,OAAO,KAAA;AAAA,MACT;AACA,MAAA,OAAO,KAAA;AAAA,IACT,CAAA,EAxBY,KAAA,CAAA;AA0BZ,IAAA,GAAA,CAAI,IAAA,CAAK,MAAM,CAAC,CAAA;AAChB,IAAA,IAAI,SAAA,EAAW;AACb,MAAA,IAAA,CAAK,KAAA,EAAA;AAAA,IACP;AACA,IAAA,OAAO,SAAA;AAAA,EACT;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,SAAA,GAAoB;AAClB,IAAA,MAAM,YAAY,IAAA,CAAK,IAAA;AACvB,IAAA,IAAI,QAAA,GAAW,CAAA;AACf,IAAA,IAAI,SAAA,EAAW;AACb,MAAA,MAAM,GAAA,mBAAM,MAAA,CAAA,CAAC,IAAA,EAAgB,KAAA,KAAkB;AAC7C,QAAA,IAAI,QAAQ,QAAA,EAAU;AACpB,UAAA,QAAA,GAAW,KAAA;AAAA,QACb;AACA,QAAA,MAAM,EAAE,UAAS,GAAI,IAAA;AACrB,QAAA,IAAI,QAAA,EAAU;AACZ,UAAA,KAAA,MAAW,KAAA,IAAS,QAAA,CAAS,OAAA,EAAQ,EAAG;AACtC,YAAA,GAAA,CAAI,KAAA,CAAM,CAAC,CAAA,EAAG,KAAA,GAAQ,CAAC,CAAA;AAAA,UACzB;AAAA,QACF;AAAA,MACF,CAAA,EAVY,KAAA,CAAA;AAWZ,MAAA,GAAA,CAAI,WAAW,CAAC,CAAA;AAAA,IAClB;AACA,IAAA,OAAO,QAAA;AAAA,EACT;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EASA,cAAc,KAAA,EAAwB;AACpC,IAAA,KAAA,GAAQ,IAAA,CAAK,aAAa,KAAK,CAAA;AAC/B,IAAA,IAAI,MAAM,IAAA,CAAK,IAAA;AACf,IAAA,KAAA,MAAW,KAAK,KAAA,EAAO;AACrB,MAAA,MAAM,KAAA,GAAQ,GAAA,CAAI,QAAA,CAAS,GAAA,CAAI,CAAC,CAAA;AAChC,MAAA,IAAI,CAAC,OAAO,OAAO,KAAA;AACnB,MAAA,GAAA,GAAM,KAAA;AAAA,IACR;AACA,IAAA,OAAO,CAAC,GAAA,CAAI,KAAA;AAAA,EACd;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EASA,UAAU,KAAA,EAAwB;AAChC,IAAA,KAAA,GAAQ,IAAA,CAAK,aAAa,KAAK,CAAA;AAC/B,IAAA,IAAI,MAAM,IAAA,CAAK,IAAA;AACf,IAAA,KAAA,MAAW,KAAK,KAAA,EAAO;AACrB,MAAA,MAAM,KAAA,GAAQ,GAAA,CAAI,QAAA,CAAS,GAAA,CAAI,CAAC,CAAA;AAChC,MAAA,IAAI,CAAC,OAAO,OAAO,KAAA;AACnB,MAAA,GAAA,GAAM,KAAA;AAAA,IACR;AACA,IAAA,OAAO,IAAA;AAAA,EACT;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EASA,gBAAgB,KAAA,EAAwB;AACtC,IAAA,KAAA,GAAQ,IAAA,CAAK,aAAa,KAAK,CAAA;AAC/B,IAAA,IAAI,SAAA,GAAY,EAAA;AAChB,IAAA,MAAM,GAAA,2BAAO,GAAA,KAAkB;AAC7B,MAAA,SAAA,IAAa,GAAA,CAAI,GAAA;AACjB,MAAA,IAAI,cAAc,KAAA,EAAO;AACzB,MAAA,IAAI,IAAI,KAAA,EAAO;AACf,MAAA,IAAI,OAAO,GAAA,CAAI,QAAA,IAAY,GAAA,CAAI,QAAA,CAAS,SAAS,CAAA,EAAG,GAAA,CAAI,KAAA,CAAM,IAAA,CAAK,IAAI,QAAA,CAAS,MAAA,EAAQ,CAAA,CAAE,CAAC,CAAC,CAAA;AAAA,WACvF;AAAA,IACP,CAAA,EANY,KAAA,CAAA;AAOZ,IAAA,GAAA,CAAI,KAAK,IAAI,CAAA;AACb,IAAA,OAAO,SAAA,KAAc,KAAA;AAAA,EACvB;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,sBAAA,GAAiC;AAC/B,IAAA,IAAI,SAAA,GAAY,EAAA;AAChB,IAAA,MAAM,GAAA,2BAAO,GAAA,KAAkB;AAC7B,MAAA,SAAA,IAAa,GAAA,CAAI,GAAA;AACjB,MAAA,IAAI,IAAI,KAAA,EAAO;AACf,MAAA,IAAI,OAAO,GAAA,CAAI,QAAA,IAAY,GAAA,CAAI,QAAA,CAAS,SAAS,CAAA,EAAG,GAAA,CAAI,KAAA,CAAM,IAAA,CAAK,IAAI,QAAA,CAAS,MAAA,EAAQ,CAAA,CAAE,CAAC,CAAC,CAAA;AAAA,WACvF;AAAA,IACP,CAAA,EALY,KAAA,CAAA;AAMZ,IAAA,GAAA,CAAI,KAAK,IAAI,CAAA;AACb,IAAA,OAAO,SAAA;AAAA,EACT;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAWA,SAAS,MAAA,GAAS,EAAA,EAAI,MAAM,MAAA,CAAO,gBAAA,EAAkB,uBAAuB,KAAA,EAAiB;AAC3F,IAAA,MAAA,GAAS,IAAA,CAAK,aAAa,MAAM,CAAA;AACjC,IAAA,MAAM,QAAkB,EAAC;AACzB,IAAA,IAAI,KAAA,GAAQ,CAAA;AAEZ,IAAA,MAAM,GAAA,mBAAM,MAAA,CAAA,CAAC,IAAA,EAAgB,IAAA,KAAuB;AAClD,MAAA,KAAA,MAAW,CAAC,IAAA,EAAM,SAAS,CAAA,IAAK,KAAK,QAAA,EAAU;AAC7C,QAAA,IAAI,SAAS,GAAA,EAAK;AAClB,QAAA,GAAA,CAAI,SAAA,EAAW,OAAO,IAAI,CAAA;AAAA,MAC5B;AACA,MAAA,IAAI,KAAK,KAAA,EAAO;AACd,QAAA,IAAI,SAAS,GAAA,EAAK;AAClB,QAAA,KAAA,CAAM,KAAK,IAAI,CAAA;AACf,QAAA,KAAA,EAAA;AAAA,MACF;AAAA,IACF,CAAA,EAVY,KAAA,CAAA;AAYZ,IAAA,IAAI,YAAY,IAAA,CAAK,IAAA;AAErB,IAAA,IAAI,MAAA,EAAQ;AACV,MAAA,KAAA,MAAW,KAAK,MAAA,EAAQ;AACtB,QAAA,MAAM,KAAA,GAAQ,SAAA,CAAU,QAAA,CAAS,GAAA,CAAI,CAAC,CAAA;AACtC,QAAA,IAAI,KAAA,EAAO;AACT,UAAA,SAAA,GAAY,KAAA;AAAA,QACd,CAAA,MAAO;AACL,UAAA,OAAO,EAAC;AAAA,QACV;AAAA,MACF;AAAA,IACF;AAEA,IAAA,IAAI,wBAAwB,SAAA,KAAc,IAAA,CAAK,IAAA,EAAM,GAAA,CAAI,WAAW,MAAM,CAAA;AAE1E,IAAA,OAAO,KAAA;AAAA,EACT;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,KAAA,GAAc;AACZ,IAAA,MAAM,IAAA,GAAO,KAAK,eAAA,EAAgB;AAClC,IAAA,KAAA,MAAW,CAAA,IAAK,IAAA,EAAM,IAAA,CAAK,GAAA,CAAI,CAAC,CAAA;AAChC,IAAA,OAAO,IAAA;AAAA,EACT;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAUA,MAAA,CAAO,WAAgD,OAAA,EAAqB;AAC1E,IAAA,MAAM,OAAA,GAAU,KAAK,eAAA,EAAgB;AACrC,IAAA,IAAI,KAAA,GAAQ,CAAA;AACZ,IAAA,KAAA,MAAW,QAAQ,IAAA,EAAM;AACvB,MAAA,IAAI,UAAU,IAAA,CAAK,OAAA,EAAS,IAAA,EAAM,KAAA,EAAO,IAAI,CAAA,EAAG;AAC9C,QAAA,OAAA,CAAQ,IAAI,IAAI,CAAA;AAAA,MAClB;AACA,MAAA,KAAA,EAAA;AAAA,IACF;AACA,IAAA,OAAO,OAAA;AAAA,EACT;AAAA,EAqBA,GAAA,CAAY,QAAA,EAA0C,OAAA,EAA2B,OAAA,EAAoB;AACnG,IAAA,MAAM,OAAA,GAAU,IAAA,CAAK,WAAA,CAAgB,IAAI,OAAO,CAAA;AAChD,IAAA,IAAI,CAAA,GAAI,CAAA;AACR,IAAA,KAAA,MAAW,KAAK,IAAA,EAAM;AACpB,MAAA,MAAM,CAAA,GAAI,OAAA,KAAY,MAAA,GAAY,QAAA,CAAS,CAAA,EAAG,CAAA,EAAA,EAAK,IAAI,CAAA,GAAI,QAAA,CAAS,IAAA,CAAK,OAAA,EAAS,CAAA,EAAG,KAAK,IAAI,CAAA;AAC9F,MAAA,IAAI,OAAO,MAAM,QAAA,EAAU;AACzB,QAAA,MAAM,IAAI,SAAA,CAAU,CAAA,0CAAA,EAA6C,OAAO,CAAC,CAAA,CAAE,CAAA;AAAA,MAC7E;AACA,MAAA,OAAA,CAAQ,IAAI,CAAC,CAAA;AAAA,IACf;AACA,IAAA,OAAO,OAAA;AAAA,EACT;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAUA,OAAA,CAAQ,UAA8C,OAAA,EAAqB;AACzE,IAAA,MAAM,IAAA,GAAO,KAAK,eAAA,EAAgB;AAClC,IAAA,IAAI,CAAA,GAAI,CAAA;AACR,IAAA,KAAA,MAAW,OAAO,IAAA,EAAM;AACtB,MAAA,MAAM,MAAA,GAAS,OAAA,KAAY,MAAA,GAAY,QAAA,CAAS,GAAA,EAAK,CAAA,EAAA,EAAK,IAAI,CAAA,GAAI,QAAA,CAAS,IAAA,CAAK,OAAA,EAAS,GAAA,EAAK,KAAK,IAAI,CAAA;AACvG,MAAA,IAAA,CAAK,IAAI,MAAM,CAAA;AAAA,IACjB;AACA,IAAA,OAAO,IAAA;AAAA,EACT;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EASU,gBAAgB,OAAA,EAAgC;AACxD,IAAA,MAAM,OAAY,IAAA,CAAK,WAAA;AACvB,IAAA,MAAM,IAAA,GAAY,IAAI,IAAA,CAAK,EAAC,EAAG;AAAA,MAC7B,aAAa,IAAA,CAAK,WAAA;AAAA,MAClB,eAAe,IAAA,CAAK,aAAA;AAAA,MACpB,GAAI,WAAW;AAAC,KACjB,CAAA;AACD,IAAA,OAAO,IAAA;AAAA,EACT;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAWU,WAAA,CAAgB,QAAA,GAA4C,EAAC,EAAG,OAAA,EAAqC;AAC7G,IAAA,MAAM,OAAY,IAAA,CAAK,WAAA;AACvB,IAAA,OAAO,IAAI,IAAA,CAAK,QAAA,EAAU,OAAO,CAAA;AAAA,EACnC;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAUU,WAAe,OAAA,EAAqC;AAC5D,IAAA,OAAO,IAAA,CAAK,WAAA,CAAgB,EAAC,EAAG,OAAO,CAAA;AAAA,EACzC;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,CAAW,YAAA,GAAyC;AAClD,IAAA,UAAU,IAAA,CAAK,MAAgB,IAAA,EAAwC;AACrE,MAAA,IAAI,KAAK,KAAA,EAAO;AACd,QAAA,MAAM,IAAA;AAAA,MACR;AACA,MAAA,KAAA,MAAW,CAAC,IAAA,EAAM,SAAS,CAAA,IAAK,KAAK,QAAA,EAAU;AAC7C,QAAA,OAAO,IAAA,CAAK,SAAA,EAAW,IAAA,GAAO,IAAI,CAAA;AAAA,MACpC;AAAA,IACF;AAPU,IAAA,MAAA,CAAA,IAAA,EAAA,MAAA,CAAA;AASV,IAAA,OAAO,IAAA,CAAK,IAAA,CAAK,IAAA,EAAM,EAAE,CAAA;AAAA,EAC3B;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EASU,aAAa,GAAA,EAAa;AAClC,IAAA,IAAI,CAAC,KAAK,cAAA,EAAgB;AACxB,MAAA,GAAA,GAAM,IAAI,WAAA,EAAY;AAAA,IACxB;AACA,IAAA,OAAO,GAAA;AAAA,EACT;AACF;;;ACjvBO,IAAK,YAAA,qBAAAA,aAAAA,KAAL;AACL,EAAAA,aAAAA,CAAAA,aAAAA,CAAA,WAAQ,CAAA,CAAA,GAAR,OAAA;AACA,EAAAA,aAAAA,CAAAA,aAAAA,CAAA,aAAU,CAAA,CAAA,GAAV,SAAA;AAFU,EAAA,OAAAA,aAAAA;AAAA,CAAA,EAAA,YAAA,IAAA,EAAA;AAKL,IAAM,QAAN,MAAe;AAAA,EACpB,YACS,GAAA,EACA,IAAA,EACA,UAAA,GAAsB,IAAA,EACtB,cAAuB,IAAA,EAC9B;AAJO,IAAA,IAAA,CAAA,GAAA,GAAA,GAAA;AACA,IAAA,IAAA,CAAA,IAAA,GAAA,IAAA;AACA,IAAA,IAAA,CAAA,UAAA,GAAA,UAAA;AACA,IAAA,IAAA,CAAA,WAAA,GAAA,WAAA;AAAA,EAIT;AAAA,EAdF;AAKsB,IAAA,MAAA,CAAA,IAAA,EAAA,OAAA,CAAA;AAAA;AAAA;AAAA,EAYpB,SAAA,CAAU,KAAQ,UAAA,EAA6C;AAC7D,IAAA,MAAM,QAAA,GAAW,IAAA,CAAK,UAAA,GAAa,UAAA,CAAW,GAAA,EAAK,IAAA,CAAK,GAAG,CAAA,IAAK,CAAA,GAAI,UAAA,CAAW,GAAA,EAAK,IAAA,CAAK,GAAG,CAAA,GAAI,CAAA;AAChG,IAAA,MAAM,SAAA,GAAY,IAAA,CAAK,WAAA,GAAc,UAAA,CAAW,GAAA,EAAK,IAAA,CAAK,IAAI,CAAA,IAAK,CAAA,GAAI,UAAA,CAAW,GAAA,EAAK,IAAA,CAAK,IAAI,CAAA,GAAI,CAAA;AACpG,IAAA,OAAO,QAAA,IAAY,SAAA;AAAA,EACrB;AACF","file":"index.cjs","sourcesContent":["import type { ElementCallback, IterableElementBaseOptions, ReduceElementCallback } from '../../types';\n\n/**\n * Base class that makes a data structure iterable and provides common\n * element-wise utilities (e.g., map/filter/reduce/find).\n *\n * @template E The public element type yielded by the structure.\n * @template R The underlying \"raw\" element type used internally or by converters.\n *\n * @remarks\n * This class implements the JavaScript iteration protocol (via `Symbol.iterator`)\n * and offers array-like helpers with predictable time/space complexity.\n */\nexport abstract class IterableElementBase implements Iterable {\n /**\n * Create a new iterable base.\n *\n * @param options Optional behavior overrides. When provided, a `toElementFn`\n * is used to convert a raw element (`R`) into a public element (`E`).\n *\n * @remarks\n * Time O(1), Space O(1).\n */\n protected constructor(options?: IterableElementBaseOptions) {\n if (options) {\n const { toElementFn } = options;\n if (typeof toElementFn === 'function') this._toElementFn = toElementFn;\n else if (toElementFn) throw new TypeError('toElementFn must be a function type');\n }\n }\n\n /**\n * The converter used to transform a raw element (`R`) into a public element (`E`).\n *\n * @remarks\n * Time O(1), Space O(1).\n */\n protected _toElementFn?: (rawElement: R) => E;\n\n /**\n * Exposes the current `toElementFn`, if configured.\n *\n * @returns The converter function or `undefined` when not set.\n * @remarks\n * Time O(1), Space O(1).\n */\n get toElementFn(): ((rawElement: R) => E) | undefined {\n return this._toElementFn;\n }\n\n /**\n * Returns an iterator over the structure's elements.\n *\n * @param args Optional iterator arguments forwarded to the internal iterator.\n * @returns An `IterableIterator` that yields the elements in traversal order.\n *\n * @remarks\n * Producing the iterator is O(1); consuming the entire iterator is Time O(n) with O(1) extra space.\n */\n *[Symbol.iterator](...args: unknown[]): IterableIterator {\n yield* this._getIterator(...args);\n }\n\n /**\n * Returns an iterator over the values (alias of the default iterator).\n *\n * @returns An `IterableIterator` over all elements.\n * @remarks\n * Creating the iterator is O(1); full iteration is Time O(n), Space O(1).\n */\n *values(): IterableIterator {\n for (const item of this) yield item;\n }\n\n /**\n * Tests whether all elements satisfy the predicate.\n *\n * @template TReturn\n * @param predicate Function invoked for each element with signature `(value, index, self)`.\n * @param thisArg Optional `this` binding for the predicate.\n * @returns `true` if every element passes; otherwise `false`.\n *\n * @remarks\n * Time O(n) in the worst case; may exit early when the first failure is found. Space O(1).\n */\n every(predicate: ElementCallback, thisArg?: unknown): boolean {\n let index = 0;\n for (const item of this) {\n if (thisArg === undefined) {\n if (!predicate(item, index++, this)) return false;\n } else {\n const fn = predicate as (this: unknown, v: E, i: number, self: this) => boolean;\n if (!fn.call(thisArg, item, index++, this)) return false;\n }\n }\n return true;\n }\n\n /**\n * Tests whether at least one element satisfies the predicate.\n *\n * @param predicate Function invoked for each element with signature `(value, index, self)`.\n * @param thisArg Optional `this` binding for the predicate.\n * @returns `true` if any element passes; otherwise `false`.\n *\n * @remarks\n * Time O(n) in the worst case; may exit early on first success. Space O(1).\n */\n some(predicate: ElementCallback, thisArg?: unknown): boolean {\n let index = 0;\n for (const item of this) {\n if (thisArg === undefined) {\n if (predicate(item, index++, this)) return true;\n } else {\n const fn = predicate as (this: unknown, v: E, i: number, self: this) => boolean;\n if (fn.call(thisArg, item, index++, this)) return true;\n }\n }\n return false;\n }\n\n /**\n * Invokes a callback for each element in iteration order.\n *\n * @param callbackfn Function invoked per element with signature `(value, index, self)`.\n * @param thisArg Optional `this` binding for the callback.\n * @returns `void`.\n *\n * @remarks\n * Time O(n), Space O(1).\n */\n forEach(callbackfn: ElementCallback, thisArg?: unknown): void {\n let index = 0;\n for (const item of this) {\n if (thisArg === undefined) {\n callbackfn(item, index++, this);\n } else {\n const fn = callbackfn as (this: unknown, v: E, i: number, self: this) => void;\n fn.call(thisArg, item, index++, this);\n }\n }\n }\n\n /**\n * Finds the first element that satisfies the predicate and returns it.\n *\n * @overload\n * Finds the first element of type `S` (a subtype of `E`) that satisfies the predicate and returns it.\n * @template S\n * @param predicate Type-guard predicate: `(value, index, self) => value is S`.\n * @param thisArg Optional `this` binding for the predicate.\n * @returns The matched element typed as `S`, or `undefined` if not found.\n *\n * @overload\n * @param predicate Boolean predicate: `(value, index, self) => boolean`.\n * @param thisArg Optional `this` binding for the predicate.\n * @returns The first matching element as `E`, or `undefined` if not found.\n *\n * @remarks\n * Time O(n) in the worst case; may exit early on the first match. Space O(1).\n */\n find(predicate: ElementCallback, thisArg?: unknown): S | undefined;\n find(predicate: ElementCallback, thisArg?: unknown): E | undefined;\n\n // Implementation signature\n find(predicate: ElementCallback, thisArg?: unknown): E | undefined {\n let index = 0;\n for (const item of this) {\n if (thisArg === undefined) {\n if (predicate(item, index++, this)) return item;\n } else {\n const fn = predicate as (this: unknown, v: E, i: number, self: this) => boolean;\n if (fn.call(thisArg, item, index++, this)) return item;\n }\n }\n return;\n }\n\n /**\n * Checks whether a strictly-equal element exists in the structure.\n *\n * @param element The element to test with `===` equality.\n * @returns `true` if an equal element is found; otherwise `false`.\n *\n * @remarks\n * Time O(n) in the worst case. Space O(1).\n */\n has(element: E): boolean {\n for (const ele of this) if (ele === element) return true;\n return false;\n }\n\n reduce(callbackfn: ReduceElementCallback): E;\n reduce(callbackfn: ReduceElementCallback, initialValue: E): E;\n reduce(callbackfn: ReduceElementCallback, initialValue: U): U;\n\n /**\n * Reduces all elements to a single accumulated value.\n *\n * @overload\n * @param callbackfn Reducer of signature `(acc, value, index, self) => nextAcc`. The first element is used as the initial accumulator.\n * @returns The final accumulated value typed as `E`.\n *\n * @overload\n * @param callbackfn Reducer of signature `(acc, value, index, self) => nextAcc`.\n * @param initialValue The initial accumulator value of type `E`.\n * @returns The final accumulated value typed as `E`.\n *\n * @overload\n * @template U The accumulator type when it differs from `E`.\n * @param callbackfn Reducer of signature `(acc: U, value, index, self) => U`.\n * @param initialValue The initial accumulator value of type `U`.\n * @returns The final accumulated value typed as `U`.\n *\n * @remarks\n * Time O(n), Space O(1). Throws if called on an empty structure without `initialValue`.\n */\n reduce(callbackfn: ReduceElementCallback, initialValue?: U): U {\n let index = 0;\n const iter = this[Symbol.iterator]();\n let acc: U;\n\n if (arguments.length >= 2) {\n acc = initialValue as U;\n } else {\n const first = iter.next();\n if (first.done) throw new TypeError('Reduce of empty structure with no initial value');\n acc = first.value as unknown as U;\n index = 1;\n }\n\n for (const value of iter as unknown as Iterable) {\n acc = callbackfn(acc, value, index++, this);\n }\n return acc;\n }\n\n /**\n * Materializes the elements into a new array.\n *\n * @returns A shallow array copy of the iteration order.\n * @remarks\n * Time O(n), Space O(n).\n */\n toArray(): E[] {\n return [...this];\n }\n\n /**\n * Returns a representation of the structure suitable for quick visualization.\n * Defaults to an array of elements; subclasses may override to provide richer visuals.\n *\n * @returns A visual representation (array by default).\n * @remarks\n * Time O(n), Space O(n).\n */\n toVisual(): E[] {\n return [...this];\n }\n\n /**\n * Prints `toVisual()` to the console. Intended for quick debugging.\n *\n * @returns `void`.\n * @remarks\n * Time O(n) due to materialization, Space O(n) for the intermediate representation.\n */\n print(): void {\n console.log(this.toVisual());\n }\n\n /**\n * Indicates whether the structure currently contains no elements.\n *\n * @returns `true` if empty; otherwise `false`.\n * @remarks\n * Expected Time O(1), Space O(1) for most implementations.\n */\n abstract isEmpty(): boolean;\n\n /**\n * Removes all elements from the structure.\n *\n * @returns `void`.\n * @remarks\n * Expected Time O(1) or O(n) depending on the implementation; Space O(1).\n */\n abstract clear(): void;\n\n /**\n * Creates a structural copy with the same element values and configuration.\n *\n * @returns A clone of the current instance (same concrete type).\n * @remarks\n * Expected Time O(n) to copy elements; Space O(n).\n */\n abstract clone(): this;\n\n /**\n * Maps each element to a new element and returns a new iterable structure.\n *\n * @template EM The mapped element type.\n * @template RM The mapped raw element type used internally by the target structure.\n * @param callback Function with signature `(value, index, self) => mapped`.\n * @param options Optional options for the returned structure, including its `toElementFn`.\n * @param thisArg Optional `this` binding for the callback.\n * @returns A new `IterableElementBase` containing mapped elements.\n *\n * @remarks\n * Time O(n), Space O(n).\n */\n abstract map(\n callback: ElementCallback,\n options?: IterableElementBaseOptions,\n thisArg?: unknown\n ): IterableElementBase;\n\n /**\n * Maps each element to the same element type and returns the same concrete structure type.\n *\n * @param callback Function with signature `(value, index, self) => mappedValue`.\n * @param thisArg Optional `this` binding for the callback.\n * @returns A new instance of the same concrete type with mapped elements.\n *\n * @remarks\n * Time O(n), Space O(n).\n */\n abstract mapSame(callback: ElementCallback, thisArg?: unknown): this;\n\n /**\n * Filters elements using the provided predicate and returns the same concrete structure type.\n *\n * @param predicate Function with signature `(value, index, self) => boolean`.\n * @param thisArg Optional `this` binding for the predicate.\n * @returns A new instance of the same concrete type containing only elements that pass the predicate.\n *\n * @remarks\n * Time O(n), Space O(k) where `k` is the number of kept elements.\n */\n abstract filter(predicate: ElementCallback, thisArg?: unknown): this;\n\n /**\n * Internal iterator factory used by the default iterator.\n *\n * @param args Optional iterator arguments.\n * @returns An iterator over elements.\n *\n * @remarks\n * Implementations should yield in O(1) per element with O(1) extra space when possible.\n */\n protected abstract _getIterator(...args: unknown[]): IterableIterator;\n}\n","/**\n * data-structure-typed\n *\n * @author Pablo Zeng\n * @copyright Copyright (c) 2022 Pablo Zeng \n * @license MIT License\n */\n\nimport type { ElementCallback, TrieOptions } from '../../types';\nimport { IterableElementBase } from '../base';\n\n/**\n * Node used by Trie to store one character and its children.\n * @remarks Time O(1), Space O(1)\n */\nexport class TrieNode {\n /**\n * Create a Trie node with a character key.\n * @remarks Time O(1), Space O(1)\n * @returns New TrieNode instance.\n */\n\n constructor(key: string) {\n this._key = key;\n this._isEnd = false;\n this._children = new Map();\n }\n\n protected _key: string;\n\n /**\n * Get the character key of this node.\n * @remarks Time O(1), Space O(1)\n * @returns Character key string.\n */\n\n get key(): string {\n return this._key;\n }\n\n /**\n * Set the character key of this node.\n * @remarks Time O(1), Space O(1)\n * @param value - New character key.\n * @returns void\n */\n\n set key(value: string) {\n this._key = value;\n }\n\n protected _children: Map;\n\n /**\n * Get the child map of this node.\n * @remarks Time O(1), Space O(1)\n * @returns Map from character to child node.\n */\n\n get children(): Map {\n return this._children;\n }\n\n /**\n * Replace the child map of this node.\n * @remarks Time O(1), Space O(1)\n * @param value - New map of character → node.\n * @returns void\n */\n\n set children(value: Map) {\n this._children = value;\n }\n\n protected _isEnd: boolean;\n\n /**\n * Check whether this node marks the end of a word.\n * @remarks Time O(1), Space O(1)\n * @returns True if this node ends a word.\n */\n\n get isEnd(): boolean {\n return this._isEnd;\n }\n\n /**\n * Mark this node as the end of a word or not.\n * @remarks Time O(1), Space O(1)\n * @param value - Whether this node ends a word.\n * @returns void\n */\n\n set isEnd(value: boolean) {\n this._isEnd = value;\n }\n}\n\n/**\n * Prefix tree (Trie) for fast prefix queries and word storage.\n * @remarks Time O(1), Space O(1)\n * @template R\n * 1. Node Structure: Each node in a Trie represents a string (or a part of a string). The root node typically represents an empty string.\n * 2. Child Node Relationship: Each node's children represent the strings that can be formed by adding one character to the string at the current node. For example, if a node represents the string 'ca', one of its children might represent 'cat'.\n * 3. Fast Retrieval: Trie allows retrieval in O(m) time complexity, where m is the length of the string to be searched.\n * 4. Space Efficiency: Trie can store a large number of strings very space-efficiently, especially when these strings share common prefixes.\n * 5. Autocomplete and Prediction: Trie can be used for implementing autocomplete and word prediction features, as it can quickly find all strings with a common prefix.\n * 6. Sorting: Trie can be used to sort a set of strings in alphabetical order.\n * 7. String Retrieval: For example, searching for a specific string in a large set of strings.\n * 8. Autocomplete: Providing recommended words or phrases as a user types.\n * 9. Spell Check: Checking the spelling of words.\n * 10. IP Routing: Used in certain types of IP routing algorithms.\n * 11. Text Word Frequency Count: Counting and storing the frequency of words in a large amount of text data.\n * @example\n * // basic Trie creation and add words\n * // Create a simple Trie with initial words\n * const trie = new Trie(['apple', 'app', 'apply']);\n *\n * // Verify size\n * console.log(trie.size); // 3;\n *\n * // Check if words exist\n * console.log(trie.has('apple')); // true;\n * console.log(trie.has('app')); // true;\n *\n * // Add a new word\n * trie.add('application');\n * console.log(trie.size); // 4;\n * @example\n * // Trie getWords and prefix search\n * const trie = new Trie(['apple', 'app', 'apply', 'application', 'apricot']);\n *\n * // Get all words with prefix 'app'\n * const appWords = trie.getWords('app');\n * console.log(appWords); // contains 'app';\n * console.log(appWords); // contains 'apple';\n * console.log(appWords); // contains 'apply';\n * console.log(appWords); // contains 'application';\n * expect(appWords).not.toContain('apricot');\n * @example\n * // Trie isPrefix and isAbsolutePrefix checks\n * const trie = new Trie(['tree', 'trial', 'trick', 'trip', 'trie']);\n *\n * // Check if string is a prefix of any word\n * console.log(trie.hasPrefix('tri')); // true;\n * console.log(trie.hasPrefix('tr')); // true;\n * console.log(trie.hasPrefix('xyz')); // false;\n *\n * // Check if string is an absolute prefix (not a complete word)\n * console.log(trie.hasPurePrefix('tri')); // true;\n * console.log(trie.hasPurePrefix('tree')); // false; // 'tree' is a complete word\n *\n * // Verify size\n * console.log(trie.size); // 5;\n * @example\n * // Trie delete and iteration\n * const trie = new Trie(['car', 'card', 'care', 'careful', 'can', 'cat']);\n *\n * // Delete a word\n * trie.delete('card');\n * console.log(trie.has('card')); // false;\n *\n * // Word with same prefix still exists\n * console.log(trie.has('care')); // true;\n *\n * // Size decreased\n * console.log(trie.size); // 5;\n *\n * // Iterate through all words\n * const allWords = [...trie];\n * console.log(allWords.length); // 5;\n * @example\n * // Trie for autocomplete search index\n * // Trie is perfect for autocomplete: O(m + k) where m is prefix length, k is results\n * const searchIndex = new Trie(['typescript', 'javascript', 'python', 'java', 'rust', 'ruby', 'golang', 'kotlin']);\n *\n * // User types 'j' - get all suggestions\n * const jResults = searchIndex.getWords('j');\n * console.log(jResults); // contains 'javascript';\n * console.log(jResults); // contains 'java';\n * console.log(jResults.length); // 2;\n *\n * // User types 'ja' - get more specific suggestions\n * const jaResults = searchIndex.getWords('ja');\n * console.log(jaResults); // contains 'javascript';\n * console.log(jaResults); // contains 'java';\n * console.log(jaResults.length); // 2;\n *\n * // User types 'jav' - even more specific\n * const javResults = searchIndex.getWords('jav');\n * console.log(javResults); // contains 'javascript';\n * console.log(javResults); // contains 'java';\n * console.log(javResults.length); // 2;\n *\n * // Check for common prefix\n *\n * console.log(searchIndex.hasCommonPrefix('ja')); // false; // Not all words start with 'ja'\n *\n * // Total words in index\n * console.log(searchIndex.size); // 8;\n *\n * // Get height (depth of tree)\n * const height = searchIndex.getHeight();\n * console.log(typeof height); // 'number';\n * @example\n * // Dictionary: Case-insensitive word lookup\n * // Create a case-insensitive dictionary\n * const dictionary = new Trie([], { caseSensitive: false });\n *\n * // Add words with mixed casing\n * dictionary.add('Hello');\n * dictionary.add('WORLD');\n * dictionary.add('JavaScript');\n *\n * // Test lookups with different casings\n * console.log(dictionary.has('hello')); // true;\n * console.log(dictionary.has('HELLO')); // true;\n * console.log(dictionary.has('Hello')); // true;\n * console.log(dictionary.has('javascript')); // true;\n * console.log(dictionary.has('JAVASCRIPT')); // true;\n * @example\n * // File System Path Operations\n * const fileSystem = new Trie([\n * '/home/user/documents/file1.txt',\n * '/home/user/documents/file2.txt',\n * '/home/user/pictures/photo.jpg',\n * '/home/user/pictures/vacation/',\n * '/home/user/downloads'\n * ]);\n *\n * // Find common directory prefix\n * console.log(fileSystem.getLongestCommonPrefix()); // '/home/user/';\n *\n * // List all files in a directory\n * const documentsFiles = fileSystem.getWords('/home/user/documents/');\n * console.log(documentsFiles); // ['/home/user/documents/file1.txt', '/home/user/documents/file2.txt'];\n * @example\n * // IP Address Routing Table\n * // Add IP address prefixes and their corresponding routes\n * const routes = {\n * '192.168.1': 'LAN_SUBNET_1',\n * '192.168.2': 'LAN_SUBNET_2',\n * '10.0.0': 'PRIVATE_NETWORK_1',\n * '10.0.1': 'PRIVATE_NETWORK_2'\n * };\n *\n * const ipRoutingTable = new Trie(Object.keys(routes));\n *\n * // Check IP address prefix matching\n * console.log(ipRoutingTable.hasPrefix('192.168.1')); // true;\n * console.log(ipRoutingTable.hasPrefix('192.168.2')); // true;\n *\n * // Validate IP address belongs to subnet\n * const ip = '192.168.1.100';\n * const subnet = ip.split('.').slice(0, 3).join('.');\n * console.log(ipRoutingTable.hasPrefix(subnet)); // true;\n */\nexport class Trie extends IterableElementBase {\n /**\n * Create a Trie and optionally bulk-insert words.\n * @remarks Time O(totalChars), Space O(totalChars)\n * @param [words] - Iterable of strings (or raw records if toElementFn is provided).\n * @param [options] - Options such as toElementFn and caseSensitive.\n * @returns New Trie instance.\n */\n\n constructor(words: Iterable | Iterable = [], options?: TrieOptions) {\n super(options);\n if (options) {\n const { caseSensitive } = options;\n if (caseSensitive !== undefined) this._caseSensitive = caseSensitive;\n }\n if (words) {\n this.addMany(words);\n }\n }\n\n protected _size: number = 0;\n\n /**\n * Get the number of stored words.\n * @remarks Time O(1), Space O(1)\n * @returns Word count.\n */\n\n get size(): number {\n return this._size;\n }\n\n protected _caseSensitive: boolean = true;\n\n /**\n * Get whether comparisons are case-sensitive.\n * @remarks Time O(1), Space O(1)\n * @returns True if case-sensitive.\n */\n\n get caseSensitive(): boolean {\n return this._caseSensitive;\n }\n\n protected _root: TrieNode = new TrieNode('');\n\n /**\n * Get the root node.\n * @remarks Time O(1), Space O(1)\n * @returns Root TrieNode.\n */\n\n get root() {\n return this._root;\n }\n\n /**\n * (Protected) Get total count for base class iteration.\n * @remarks Time O(1), Space O(1)\n * @returns Total number of elements.\n */\n\n protected get _total() {\n return this._size;\n }\n\n /**\n * Insert one word into the trie.\n * @remarks Time O(L), Space O(L)\n * @param word - Word to insert.\n * @returns True if the word was newly added.\n */\n\n add(word: string): boolean {\n word = this._caseProcess(word);\n let cur = this.root;\n let isNewWord = false;\n for (const c of word) {\n let nodeC = cur.children.get(c);\n if (!nodeC) {\n nodeC = new TrieNode(c);\n cur.children.set(c, nodeC);\n }\n cur = nodeC;\n }\n if (!cur.isEnd) {\n isNewWord = true;\n cur.isEnd = true;\n this._size++;\n }\n return isNewWord;\n }\n\n /**\n * Insert many words from an iterable.\n * @remarks Time O(ΣL), Space O(ΣL)\n * @param words - Iterable of strings (or raw records if toElementFn is provided).\n * @returns Array of per-word 'added' flags.\n */\n\n addMany(words: Iterable | Iterable): boolean[] {\n const ans: boolean[] = [];\n for (const word of words) {\n if (this.toElementFn) {\n ans.push(this.add(this.toElementFn(word as R)));\n } else {\n ans.push(this.add(word as string));\n }\n }\n return ans;\n }\n\n /**\n * Check whether a word exists.\n * @remarks Time O(L), Space O(1)\n * @param word - Word to search for.\n * @returns True if present.\n */\n\n override has(word: string): boolean {\n word = this._caseProcess(word);\n let cur = this.root;\n for (const c of word) {\n const nodeC = cur.children.get(c);\n if (!nodeC) return false;\n cur = nodeC;\n }\n return cur.isEnd;\n }\n\n /**\n * Check whether the trie is empty.\n * @remarks Time O(1), Space O(1)\n * @returns True if size is 0.\n */\n\n isEmpty(): boolean {\n return this._size === 0;\n }\n\n /**\n * Remove all words and reset to a fresh root.\n * @remarks Time O(1), Space O(1)\n * @returns void\n */\n\n clear(): void {\n this._size = 0;\n this._root = new TrieNode('');\n }\n\n /**\n * Delete one word if present.\n * @remarks Time O(L), Space O(1)\n * @param word - Word to delete.\n * @returns True if a word was removed.\n */\n\n delete(word: string): boolean {\n word = this._caseProcess(word);\n let isDeleted = false;\n const dfs = (cur: TrieNode, i: number): boolean => {\n const char = word[i];\n const child = cur.children.get(char);\n if (child) {\n if (i === word.length - 1) {\n if (child.isEnd) {\n if (child.children.size > 0) {\n child.isEnd = false;\n } else {\n cur.children.delete(char);\n }\n isDeleted = true;\n return true;\n }\n return false;\n }\n const res = dfs(child, i + 1);\n if (res && !cur.isEnd && child.children.size === 0) {\n cur.children.delete(char);\n return true;\n }\n return false;\n }\n return false;\n };\n\n dfs(this.root, 0);\n if (isDeleted) {\n this._size--;\n }\n return isDeleted;\n }\n\n /**\n * Compute the height (max depth) of the trie.\n * @remarks Time O(N), Space O(H)\n * @returns Maximum depth from root to a leaf.\n */\n\n getHeight(): number {\n const startNode = this.root;\n let maxDepth = 0;\n if (startNode) {\n const bfs = (node: TrieNode, level: number) => {\n if (level > maxDepth) {\n maxDepth = level;\n }\n const { children } = node;\n if (children) {\n for (const child of children.entries()) {\n bfs(child[1], level + 1);\n }\n }\n };\n bfs(startNode, 0);\n }\n return maxDepth;\n }\n\n /**\n * Check whether input is a proper prefix of at least one word.\n * @remarks Time O(L), Space O(1)\n * @param input - String to test as prefix.\n * @returns True if input is a prefix but not a full word.\n */\n\n hasPurePrefix(input: string): boolean {\n input = this._caseProcess(input);\n let cur = this.root;\n for (const c of input) {\n const nodeC = cur.children.get(c);\n if (!nodeC) return false;\n cur = nodeC;\n }\n return !cur.isEnd;\n }\n\n /**\n * Check whether any word starts with input.\n * @remarks Time O(L), Space O(1)\n * @param input - String to test as prefix.\n * @returns True if input matches a path from root.\n */\n\n hasPrefix(input: string): boolean {\n input = this._caseProcess(input);\n let cur = this.root;\n for (const c of input) {\n const nodeC = cur.children.get(c);\n if (!nodeC) return false;\n cur = nodeC;\n }\n return true;\n }\n\n /**\n * Check whether the trie’s longest common prefix equals input.\n * @remarks Time O(min(H,L)), Space O(1)\n * @param input - Candidate longest common prefix.\n * @returns True if input equals the common prefix.\n */\n\n hasCommonPrefix(input: string): boolean {\n input = this._caseProcess(input);\n let commonPre = '';\n const dfs = (cur: TrieNode) => {\n commonPre += cur.key;\n if (commonPre === input) return;\n if (cur.isEnd) return;\n if (cur && cur.children && cur.children.size === 1) dfs(Array.from(cur.children.values())[0]);\n else return;\n };\n dfs(this.root);\n return commonPre === input;\n }\n\n /**\n * Return the longest common prefix among all words.\n * @remarks Time O(H), Space O(1)\n * @returns The longest common prefix string.\n */\n\n getLongestCommonPrefix(): string {\n let commonPre = '';\n const dfs = (cur: TrieNode) => {\n commonPre += cur.key;\n if (cur.isEnd) return;\n if (cur && cur.children && cur.children.size === 1) dfs(Array.from(cur.children.values())[0]);\n else return;\n };\n dfs(this.root);\n return commonPre;\n }\n\n /**\n * Collect words under a prefix up to a maximum count.\n * @remarks Time O(K·L), Space O(K·L)\n * @param [prefix] - Prefix to match; default empty string for root.\n * @param [max] - Maximum number of words to return; default is Number.MAX_SAFE_INTEGER.\n * @param [isAllWhenEmptyPrefix] - When true, collect from root even if prefix is empty.\n * @returns Array of collected words (at most max).\n */\n\n getWords(prefix = '', max = Number.MAX_SAFE_INTEGER, isAllWhenEmptyPrefix = false): string[] {\n prefix = this._caseProcess(prefix);\n const words: string[] = [];\n let found = 0;\n\n const dfs = (node: TrieNode, word: string): void => {\n for (const [char, childNode] of node.children) {\n if (found >= max) return;\n dfs(childNode, word + char);\n }\n if (node.isEnd) {\n if (found >= max) return;\n words.push(word);\n found++;\n }\n };\n\n let startNode = this.root;\n\n if (prefix) {\n for (const c of prefix) {\n const nodeC = startNode.children.get(c);\n if (nodeC) {\n startNode = nodeC;\n } else {\n return [];\n }\n }\n }\n\n if (isAllWhenEmptyPrefix || startNode !== this.root) dfs(startNode, prefix);\n\n return words;\n }\n\n /**\n * Deep clone this trie by iterating and inserting all words.\n * @remarks Time O(ΣL), Space O(ΣL)\n * @returns A new trie with the same words and options.\n */\n\n clone(): this {\n const next = this._createInstance();\n for (const x of this) next.add(x);\n return next;\n }\n\n /**\n * Filter words into a new trie of the same class.\n * @remarks Time O(ΣL), Space O(ΣL)\n * @param predicate - Predicate (word, index, trie) → boolean to keep word.\n * @param [thisArg] - Value for `this` inside the predicate.\n * @returns A new trie containing words that satisfy the predicate.\n */\n\n filter(predicate: ElementCallback, thisArg?: any): this {\n const results = this._createInstance();\n let index = 0;\n for (const word of this) {\n if (predicate.call(thisArg, word, index, this)) {\n results.add(word);\n }\n index++;\n }\n return results;\n }\n\n map(callback: ElementCallback, options?: TrieOptions, thisArg?: any): Trie;\n\n /**\n * Map words into a new trie (possibly different record type).\n * @remarks Time O(ΣL), Space O(ΣL)\n * @template EM\n * @template RM\n * @param callback - Mapping function (word, index, trie) → newWord (string).\n * @param [options] - Options for the output trie (e.g., toElementFn, caseSensitive).\n * @param [thisArg] - Value for `this` inside the callback.\n * @returns A new Trie constructed from mapped words.\n */\n\n map(\n callback: ElementCallback,\n options?: TrieOptions,\n thisArg?: any\n ): IterableElementBase;\n\n map(callback: ElementCallback, options?: TrieOptions, thisArg?: any): any {\n const newTrie = this._createLike([], options);\n let i = 0;\n for (const x of this) {\n const v = thisArg === undefined ? callback(x, i++, this) : callback.call(thisArg, x, i++, this);\n if (typeof v !== 'string') {\n throw new TypeError(`Trie.map callback must return string; got ${typeof v}`);\n }\n newTrie.add(v);\n }\n return newTrie;\n }\n\n /**\n * Map words into a new trie of the same element type.\n * @remarks Time O(ΣL), Space O(ΣL)\n * @param callback - Mapping function (word, index, trie) → string.\n * @param [thisArg] - Value for `this` inside the callback.\n * @returns A new trie with mapped words.\n */\n\n mapSame(callback: ElementCallback, thisArg?: any): this {\n const next = this._createInstance();\n let i = 0;\n for (const key of this) {\n const mapped = thisArg === undefined ? callback(key, i++, this) : callback.call(thisArg, key, i++, this);\n next.add(mapped);\n }\n return next;\n }\n\n /**\n * (Protected) Create an empty instance of the same concrete class.\n * @remarks Time O(1), Space O(1)\n * @param [options] - Options forwarded to the constructor.\n * @returns An empty like-kind trie instance.\n */\n\n protected _createInstance(options?: TrieOptions): this {\n const Ctor: any = this.constructor;\n const next: any = new Ctor([], {\n toElementFn: this.toElementFn,\n caseSensitive: this.caseSensitive,\n ...(options ?? {})\n });\n return next as this;\n }\n\n /**\n * (Protected) Create a like-kind trie and seed it from an iterable.\n * @remarks Time O(ΣL), Space O(ΣL)\n * @template RM\n * @param [elements] - Iterable used to seed the new trie.\n * @param [options] - Options forwarded to the constructor.\n * @returns A like-kind Trie instance.\n */\n\n protected _createLike(elements: Iterable | Iterable = [], options?: TrieOptions): Trie {\n const Ctor: any = this.constructor;\n return new Ctor(elements, options) as Trie;\n }\n\n /**\n * (Protected) Spawn an empty like-kind trie instance.\n * @remarks Time O(1), Space O(1)\n * @template RM\n * @param [options] - Options forwarded to the constructor.\n * @returns An empty like-kind Trie instance.\n */\n\n protected _spawnLike(options?: TrieOptions): Trie {\n return this._createLike([], options);\n }\n\n /**\n * (Protected) Iterate all words in lexicographic order of edges.\n * @remarks Time O(ΣL), Space O(H)\n * @returns Iterator of words.\n */\n\n protected *_getIterator(): IterableIterator {\n function* _dfs(node: TrieNode, path: string): IterableIterator {\n if (node.isEnd) {\n yield path;\n }\n for (const [char, childNode] of node.children) {\n yield* _dfs(childNode, path + char);\n }\n }\n\n yield* _dfs(this.root, '');\n }\n\n /**\n * (Protected) Normalize a string according to case sensitivity.\n * @remarks Time O(L), Space O(L)\n * @param str - Input string to normalize.\n * @returns Normalized string based on caseSensitive.\n */\n\n protected _caseProcess(str: string) {\n if (!this._caseSensitive) {\n str = str.toLowerCase();\n }\n return str;\n }\n}\n","export enum DFSOperation {\n VISIT = 0,\n PROCESS = 1\n}\n\nexport class Range {\n constructor(\n public low: K,\n public high: K,\n public includeLow: boolean = true,\n public includeHigh: boolean = true\n ) {\n // if (!(isComparable(low) && isComparable(high))) throw new RangeError('low or high is not comparable');\n // if (low > high) throw new RangeError('low must be less than or equal to high');\n }\n\n // Determine whether a key is within the range\n isInRange(key: K, comparator: (a: K, b: K) => number): boolean {\n const lowCheck = this.includeLow ? comparator(key, this.low) >= 0 : comparator(key, this.low) > 0;\n const highCheck = this.includeHigh ? comparator(key, this.high) <= 0 : comparator(key, this.high) < 0;\n return lowCheck && highCheck;\n }\n}\n"]}