{"version":3,"sources":["../../src/data-structures/base/iterable-element-base.ts","../../src/data-structures/trie/trie.ts","../../src/utils/utils.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,SAAS,GAAA,CAAI,MAAgB,IAAA,EAAc;AACzC,MAAA,KAAA,MAAW,IAAA,IAAQ,IAAA,CAAK,QAAA,CAAS,IAAA,EAAK,EAAG;AACvC,QAAA,MAAM,QAAA,GAAW,IAAA,CAAK,QAAA,CAAS,GAAA,CAAI,IAAI,CAAA;AACvC,QAAA,IAAI,aAAa,MAAA,EAAW;AAC1B,UAAA,GAAA,CAAI,QAAA,EAAU,IAAA,CAAK,MAAA,CAAO,IAAI,CAAC,CAAA;AAAA,QACjC;AAAA,MACF;AACA,MAAA,IAAI,KAAK,KAAA,EAAO;AACd,QAAA,IAAI,KAAA,GAAQ,MAAM,CAAA,EAAG;AACrB,QAAA,KAAA,CAAM,KAAK,IAAI,CAAA;AACf,QAAA,KAAA,EAAA;AAAA,MACF;AAAA,IACF;AAZS,IAAA,MAAA,CAAA,GAAA,EAAA,KAAA,CAAA;AAcT,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;;;ACtmBA,SAAS,sBAAsB,KAAA,EAA8C;AAC3E,EAAA,MAAM,YAAY,OAAO,KAAA;AACzB,EAAA,IAAI,SAAA,KAAc,UAAU,OAAO,IAAA;AAEnC,EAAA,OAAO,SAAA,KAAc,QAAA,IAAY,SAAA,KAAc,QAAA,IAAY,SAAA,KAAc,SAAA;AAC3E;AALS,MAAA,CAAA,qBAAA,EAAA,uBAAA,CAAA;AAkBT,SAAS,qBAAqB,GAAA,EAAyC;AACrE,EAAA,IAAI,OAAO,GAAA,CAAI,OAAA,KAAY,UAAA,EAAY;AACrC,IAAA,MAAM,aAAA,GAAgB,IAAI,OAAA,EAAQ;AAClC,IAAA,IAAI,kBAAkB,GAAA,EAAK;AACzB,MAAA,IAAI,qBAAA,CAAsB,aAAa,CAAA,EAAG,OAAO,aAAA;AACjD,MAAA,IAAI,OAAO,aAAA,KAAkB,QAAA,IAAY,kBAAkB,IAAA,EAAM,OAAO,qBAAqB,aAAa,CAAA;AAAA,IAC5G;AAAA,EACF;AACA,EAAA,IAAI,OAAO,GAAA,CAAI,QAAA,KAAa,UAAA,EAAY;AACtC,IAAA,MAAM,YAAA,GAAe,IAAI,QAAA,EAAS;AAClC,IAAA,IAAI,YAAA,KAAiB,mBAAmB,OAAO,YAAA;AAAA,EACjD;AACA,EAAA,OAAO,IAAA;AACT;AAbS,MAAA,CAAA,oBAAA,EAAA,sBAAA,CAAA;AA4BF,SAAS,YAAA,CAAa,KAAA,EAAgB,uBAAA,GAA0B,KAAA,EAA4B;AACjG,EAAA,IAAI,KAAA,KAAU,IAAA,IAAQ,KAAA,KAAU,MAAA,EAAW,OAAO,KAAA;AAClD,EAAA,IAAI,qBAAA,CAAsB,KAAK,CAAA,EAAG,OAAO,IAAA;AAEzC,EAAA,IAAI,OAAO,KAAA,KAAU,QAAA,EAAU,OAAO,KAAA;AACtC,EAAA,IAAI,KAAA,YAAiB,MAAM,OAAO,IAAA;AAElC,EAAA,IAAI,yBAAyB,OAAO,IAAA;AACpC,EAAA,MAAM,eAAA,GAAkB,qBAAqB,KAAK,CAAA;AAClD,EAAA,IAAI,eAAA,KAAoB,IAAA,IAAQ,eAAA,KAAoB,MAAA,EAAW,OAAO,KAAA;AACtE,EAAA,OAAO,sBAAsB,eAAe,CAAA;AAC9C;AAXgB,MAAA,CAAA,YAAA,EAAA,cAAA,CAAA;;;ACzLT,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;AAEP,IAAA,IAAI,EAAE,YAAA,CAAa,GAAG,CAAA,IAAK,YAAA,CAAa,IAAI,CAAA,CAAA,EAAI,MAAM,IAAI,UAAA,CAAW,+BAA+B,CAAA;AACpG,IAAA,IAAI,GAAA,GAAM,IAAA,EAAM,MAAM,IAAI,WAAW,wCAAwC,CAAA;AAAA,EAC/E;AAAA,EAhBF;AAOsB,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 function dfs(node: TrieNode, word: string) {\n for (const char of node.children.keys()) {\n const charNode = node.children.get(char);\n if (charNode !== undefined) {\n dfs(charNode, word.concat(char));\n }\n }\n if (node.isEnd) {\n if (found > max - 1) 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","/**\n * data-structure-typed\n *\n * @author Pablo Zeng\n * @copyright Copyright (c) 2022 Pablo Zeng \n * @license MIT License\n */\nimport type { Comparable, ComparablePrimitive, Trampoline, TrampolineThunk } from '../types';\n\n/**\n * The function generates a random UUID (Universally Unique Identifier) in TypeScript.\n * @returns A randomly generated UUID (Universally Unique Identifier) in the format\n * 'xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx' where each 'x' is replaced with a random hexadecimal\n * character.\n */\nexport const uuidV4 = function () {\n return 'xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx'.replace(/[x]/g, function (c) {\n const r = (Math.random() * 16) | 0,\n v = c == 'x' ? r : (r & 0x3) | 0x8;\n return v.toString(16);\n });\n};\n\n/**\n * The `arrayRemove` function removes elements from an array based on a specified predicate function\n * and returns the removed elements.\n * @param {T[]} array - An array of elements that you want to filter based on the provided predicate\n * function.\n * @param predicate - The `predicate` parameter is a function that takes three arguments:\n * @returns The `arrayRemove` function returns an array containing the elements that satisfy the given\n * `predicate` function.\n */\nexport const arrayRemove = function (array: T[], predicate: (item: T, index: number, array: T[]) => boolean): T[] {\n let i = -1,\n len = array ? array.length : 0;\n const result = [];\n\n while (++i < len) {\n const value = array[i];\n if (predicate(value, i, array)) {\n result.push(value);\n Array.prototype.splice.call(array, i--, 1);\n len--;\n }\n }\n\n return result;\n};\n\n/**\n * The function `getMSB` returns the most significant bit of a given number.\n * @param {number} value - The `value` parameter is a number for which we want to find the position of\n * the Most Significant Bit (MSB). The function `getMSB` takes this number as input and calculates the\n * position of the MSB in its binary representation.\n * @returns The function `getMSB` returns the most significant bit (MSB) of the input `value`. If the\n * input value is less than or equal to 0, it returns 0. Otherwise, it calculates the position of the\n * MSB using the `Math.clz32` function and bitwise left shifts 1 to that position.\n */\nexport const getMSB = (value: number): number => {\n if (value <= 0) {\n return 0;\n }\n return 1 << (31 - Math.clz32(value));\n};\n\n/**\n * The `rangeCheck` function in TypeScript is used to validate if an index is within a specified range\n * and throws a `RangeError` with a custom message if it is out of bounds.\n * @param {number} index - The `index` parameter represents the value that you want to check if it\n * falls within a specified range.\n * @param {number} min - The `min` parameter represents the minimum value that the `index` should be\n * compared against in the `rangeCheck` function.\n * @param {number} max - The `max` parameter in the `rangeCheck` function represents the maximum value\n * that the `index` parameter is allowed to have. If the `index` is greater than this `max` value, a\n * `RangeError` will be thrown.\n * @param [message=Index out of bounds.] - The `message` parameter is a string that represents the\n * error message to be thrown if the index is out of bounds. By default, if no message is provided when\n * calling the `rangeCheck` function, the message \"Index out of bounds.\" will be used.\n */\nexport const rangeCheck = (index: number, min: number, max: number, message = 'Index out of bounds.'): void => {\n if (index < min || index > max) throw new RangeError(message);\n};\n\n/**\n * The function `throwRangeError` throws a RangeError with a custom message if called.\n * @param [message=The value is off-limits.] - The `message` parameter is a string that represents the\n * error message to be displayed when a `RangeError` is thrown. If no message is provided, the default\n * message is 'The value is off-limits.'.\n */\nexport const throwRangeError = (message = 'The value is off-limits.'): void => {\n throw new RangeError(message);\n};\n\n/**\n * The function `isWeakKey` checks if the input is an object or a function in TypeScript.\n * @param {unknown} input - The `input` parameter in the `isWeakKey` function is of type `unknown`,\n * which means it can be any type. The function checks if the `input` is an object (excluding `null`)\n * or a function, and returns a boolean indicating whether the `input` is a weak\n * @returns The function `isWeakKey` returns a boolean value indicating whether the input is an object\n * or a function.\n */\nexport const isWeakKey = (input: unknown): input is object => {\n const inputType = typeof input;\n return (inputType === 'object' && input !== null) || inputType === 'function';\n};\n\n/**\n * The function `calcMinUnitsRequired` calculates the minimum number of units required to accommodate a\n * given total quantity based on a specified unit size.\n * @param {number} totalQuantity - The `totalQuantity` parameter represents the total quantity of items\n * that need to be processed or handled.\n * @param {number} unitSize - The `unitSize` parameter represents the size of each unit or package. It\n * is used in the `calcMinUnitsRequired` function to calculate the minimum number of units required to\n * accommodate a total quantity of items.\n */\nexport const calcMinUnitsRequired = (totalQuantity: number, unitSize: number) =>\n Math.floor((totalQuantity + unitSize - 1) / unitSize);\n\n/**\n * The `roundFixed` function in TypeScript rounds a number to a specified number of decimal places.\n * @param {number} num - The `num` parameter is a number that you want to round to a certain number of\n * decimal places.\n * @param {number} [digit=10] - The `digit` parameter in the `roundFixed` function specifies the number\n * of decimal places to round the number to. By default, it is set to 10 if not provided explicitly.\n * @returns The function `roundFixed` returns a number that is rounded to the specified number of\n * decimal places (default is 10 decimal places).\n */\nexport const roundFixed = (num: number, digit: number = 10) => {\n const multiplier = Math.pow(10, digit);\n return Math.round(num * multiplier) / multiplier;\n};\n\n/**\n * The function `isPrimitiveComparable` checks if a value is a primitive type that can be compared.\n * @param {unknown} value - The `value` parameter in the `isPrimitiveComparable` function is of type\n * `unknown`, which means it can be any type. The function checks if the `value` is a primitive type\n * that can be compared, such as number, bigint, string, or boolean.\n * @returns The function `isPrimitiveComparable` returns a boolean value indicating whether the input\n * `value` is a primitive value that can be compared using standard comparison operators (<, >, <=,\n * >=).\n */\nfunction isPrimitiveComparable(value: unknown): value is ComparablePrimitive {\n const valueType = typeof value;\n if (valueType === 'number') return true;\n // if (valueType === 'number') return !Number.isNaN(value);\n return valueType === 'bigint' || valueType === 'string' || valueType === 'boolean';\n}\n\n/**\n * The function `tryObjectToPrimitive` attempts to convert an object to a comparable primitive value by\n * first checking the `valueOf` method and then the `toString` method.\n * @param {object} obj - The `obj` parameter in the `tryObjectToPrimitive` function is an object that\n * you want to convert to a primitive value. The function attempts to convert the object to a primitive\n * value by first checking if the object has a `valueOf` method. If the `valueOf` method exists, it\n * @returns The function `tryObjectToPrimitive` returns a value of type `ComparablePrimitive` if a\n * primitive comparable value is found within the object, or a string value if the object has a custom\n * `toString` method that does not return `'[object Object]'`. If neither condition is met, the\n * function returns `null`.\n */\nfunction tryObjectToPrimitive(obj: object): ComparablePrimitive | null {\n if (typeof obj.valueOf === 'function') {\n const valueOfResult = obj.valueOf();\n if (valueOfResult !== obj) {\n if (isPrimitiveComparable(valueOfResult)) return valueOfResult;\n if (typeof valueOfResult === 'object' && valueOfResult !== null) return tryObjectToPrimitive(valueOfResult);\n }\n }\n if (typeof obj.toString === 'function') {\n const stringResult = obj.toString();\n if (stringResult !== '[object Object]') return stringResult;\n }\n return null;\n}\n\n/**\n * The function `isComparable` in TypeScript checks if a value is comparable, handling primitive values\n * and objects with optional force comparison.\n * @param {unknown} value - The `value` parameter in the `isComparable` function represents the value\n * that you want to check if it is comparable. It can be of any type (`unknown`), and the function will\n * determine if it is comparable based on certain conditions.\n * @param [isForceObjectComparable=false] - The `isForceObjectComparable` parameter in the\n * `isComparable` function is a boolean flag that determines whether to treat non-primitive values as\n * comparable objects. When set to `true`, it forces the function to consider non-primitive values as\n * comparable objects, regardless of their type.\n * @returns The function `isComparable` returns a boolean value indicating whether the `value` is\n * considered comparable or not.\n */\nexport function isComparable(value: unknown, isForceObjectComparable = false): value is Comparable {\n if (value === null || value === undefined) return false;\n if (isPrimitiveComparable(value)) return true;\n\n if (typeof value !== 'object') return false;\n if (value instanceof Date) return true;\n // if (value instanceof Date) return !Number.isNaN(value.getTime());\n if (isForceObjectComparable) return true;\n const comparableValue = tryObjectToPrimitive(value);\n if (comparableValue === null || comparableValue === undefined) return false;\n return isPrimitiveComparable(comparableValue);\n}\n\n/**\n * Creates a trampoline thunk object.\n *\n * A \"thunk\" is a deferred computation — instead of performing a recursive call immediately,\n * it wraps the next step of the computation in a function. This allows recursive processes\n * to be executed iteratively, preventing stack overflows.\n *\n * @template T - The type of the final computation result.\n * @param computation - A function that, when executed, returns the next trampoline step.\n * @returns A TrampolineThunk object containing the deferred computation.\n */\nexport const makeTrampolineThunk = (computation: () => Trampoline): TrampolineThunk => ({\n isThunk: true, // Marker indicating this is a thunk\n fn: computation // The deferred computation function\n});\n\n/**\n * Type guard to check whether a given value is a TrampolineThunk.\n *\n * This function is used to distinguish between a final computation result (value)\n * and a deferred computation (thunk).\n *\n * @template T - The type of the value being checked.\n * @param value - The value to test.\n * @returns True if the value is a valid TrampolineThunk, false otherwise.\n */\nexport const isTrampolineThunk = (value: Trampoline): value is TrampolineThunk =>\n typeof value === 'object' && // Must be an object\n value !== null && // Must not be null\n 'isThunk' in value && // Must have the 'isThunk' property\n value.isThunk; // The flag must be true\n\n/**\n * Executes a trampoline computation until a final (non-thunk) result is obtained.\n *\n * The trampoline function repeatedly invokes the deferred computations (thunks)\n * in an iterative loop. This avoids deep recursive calls and prevents stack overflow,\n * which is particularly useful for implementing recursion in a stack-safe manner.\n *\n * @template T - The type of the final result.\n * @param initial - The initial Trampoline value or thunk to start execution from.\n * @returns The final result of the computation (a non-thunk value).\n */\nexport function trampoline(initial: Trampoline): T {\n let current = initial; // Start with the initial trampoline value\n while (isTrampolineThunk(current)) {\n // Keep unwrapping while we have thunks\n current = current.fn(); // Execute the deferred function to get the next step\n }\n return current; // Once no thunks remain, return the final result\n}\n\n/**\n * Wraps a recursive function inside a trampoline executor.\n *\n * This function transforms a potentially recursive function (that returns a Trampoline)\n * into a *stack-safe* function that executes iteratively using the `trampoline` runner.\n *\n * In other words, it allows you to write functions that look recursive,\n * but actually run in constant stack space.\n *\n * @template Args - The tuple type representing the argument list of the original function.\n * @template Result - The final return type after all trampoline steps are resolved.\n *\n * @param fn - A function that performs a single step of computation\n * and returns a Trampoline (either a final value or a deferred thunk).\n *\n * @returns A new function with the same arguments, but which automatically\n * runs the trampoline process and returns the *final result* instead\n * of a Trampoline.\n *\n * @example\n * // Example: Computing factorial in a stack-safe way\n * const factorial = makeTrampoline(function fact(n: number, acc: number = 1): Trampoline {\n * return n === 0\n * ? acc\n * : makeTrampolineThunk(() => fact(n - 1, acc * n));\n * });\n *\n * console.log(factorial(100000)); // Works without stack overflow\n */\nexport function makeTrampoline(\n fn: (...args: Args) => Trampoline // A function that returns a trampoline step\n): (...args: Args) => Result {\n // Return a wrapped function that automatically runs the trampoline execution loop\n return (...args: Args) => trampoline(fn(...args));\n}\n\n/**\n * Executes an asynchronous trampoline computation until a final (non-thunk) result is obtained.\n *\n * This function repeatedly invokes asynchronous deferred computations (thunks)\n * in an iterative loop. Each thunk may return either a Trampoline or a Promise>.\n *\n * It ensures that asynchronous recursive functions can run without growing the call stack,\n * making it suitable for stack-safe async recursion.\n *\n * @template T - The type of the final result.\n * @param initial - The initial Trampoline or Promise of Trampoline to start execution from.\n * @returns A Promise that resolves to the final result (a non-thunk value).\n */\nexport async function asyncTrampoline(initial: Trampoline | Promise>): Promise {\n let current = await initial; // Wait for the initial step to resolve if it's a Promise\n\n // Keep executing thunks until we reach a non-thunk (final) value\n while (isTrampolineThunk(current)) {\n current = await current.fn(); // Execute the thunk function (may be async)\n }\n\n // Once the final value is reached, return it\n return current;\n}\n\n/**\n * Wraps an asynchronous recursive function inside an async trampoline executor.\n *\n * This helper transforms a recursive async function that returns a Trampoline\n * (or Promise>) into a *stack-safe* async function that executes\n * iteratively via the `asyncTrampoline` runner.\n *\n * @template Args - The tuple type representing the argument list of the original function.\n * @template Result - The final return type after all async trampoline steps are resolved.\n *\n * @param fn - An async or sync function that performs a single step of computation\n * and returns a Trampoline (either a final value or a deferred thunk).\n *\n * @returns An async function with the same arguments, but which automatically\n * runs the trampoline process and resolves to the *final result*.\n *\n * @example\n * // Example: Async factorial using trampoline\n * const asyncFactorial = makeAsyncTrampoline(async function fact(\n * n: number,\n * acc: number = 1\n * ): Promise> {\n * return n === 0\n * ? acc\n * : makeTrampolineThunk(() => fact(n - 1, acc * n));\n * });\n *\n * asyncFactorial(100000).then(console.log); // Works without stack overflow\n */\nexport function makeAsyncTrampoline(\n fn: (...args: Args) => Trampoline | Promise>\n): (...args: Args) => Promise {\n // Return a wrapped async function that runs through the async trampoline loop\n return async (...args: Args): Promise => {\n return asyncTrampoline(fn(...args));\n };\n}\n","import { isComparable } from '../utils';\n\nexport 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"]}