{"version":3,"sources":["../../src/data-structures/base/iterable-element-base.ts","../../src/data-structures/heap/heap.ts","../../src/data-structures/priority-queue/priority-queue.ts","../../src/data-structures/priority-queue/min-priority-queue.ts","../../src/utils/utils.ts","../../src/common/index.ts"],"names":["DFSOperation"],"mappings":";;;;;;;;AAaO,IAAe,oBAAA,GAAf,MAAe,oBAAA,CAAiD;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAU3D,YAAY,OAAA,EAA4C;AAclE;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,IAAA,aAAA,CAAA,IAAA,EAAU,cAAA,CAAA;AAbR,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;AAAA,EAiBA,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;AAlVuE,MAAA,CAAA,oBAAA,EAAA,qBAAA,CAAA;AAAhE,IAAe,mBAAA,GAAf,oBAAA;;;ACmLA,IAAM,KAAA,GAAN,MAAM,KAAA,SAA+B,mBAAA,CAA0B;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAWpE,WAAA,CAAY,QAAA,GAA4B,EAAC,EAAG,OAAA,EAA6B;AACvE,IAAA,KAAA,CAAM,OAAO,CAAA;AAXf,IAAA,aAAA,CAAA,IAAA,EAAU,WAAmC,MAAA,CAAO,EAAA,CAAA;AAqBpD,IAAA,aAAA,CAAA,IAAA,EAAU,aAAiB,EAAC,CAAA;AA0X5B,IAAA,aAAA,CAAA,IAAA,EAAU,qBAAA,kBAAsB,MAAA,CAAA,CAAC,CAAA,EAAM,CAAA,KAAiB;AACtD,MAAA,IAAI,OAAO,CAAA,KAAM,QAAA,IAAY,OAAO,MAAM,QAAA,EAAU;AAClD,QAAA,MAAM,UAAU,qEAAqE,CAAA;AAAA,MACvF;AACA,MAAA,IAAK,CAAA,GAA2B,GAAyB,OAAO,CAAA;AAChE,MAAA,IAAK,CAAA,GAA2B,GAAyB,OAAO,EAAA;AAChE,MAAA,OAAO,CAAA;AAAA,IACT,CAAA,EAPgC,qBAAA,CAAA,CAAA;AAShC,IAAA,aAAA,CAAA,IAAA,EAAU,eAA6B,IAAA,CAAK,mBAAA,CAAA;AA3Y1C,IAAA,IAAI,OAAA,EAAS;AACX,MAAA,MAAM,EAAE,YAAW,GAAI,OAAA;AACvB,MAAA,IAAI,UAAA,OAAiB,WAAA,GAAc,UAAA;AAAA,IACrC;AAEA,IAAA,IAAA,CAAK,QAAQ,QAA2B,CAAA;AAAA,EAC1C;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAUA,IAAI,QAAA,GAAgB;AAClB,IAAA,OAAO,IAAA,CAAK,SAAA;AAAA,EACd;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,IAAI,IAAA,GAAe;AACjB,IAAA,OAAO,KAAK,QAAA,CAAS,MAAA;AAAA,EACvB;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,IAAI,IAAA,GAAsB;AAlP5B,IAAA,IAAA,EAAA;AAmPI,IAAA,OAAA,CAAO,UAAK,QAAA,CAAS,IAAA,CAAK,IAAA,GAAO,CAAC,MAA3B,IAAA,GAAA,EAAA,GAAgC,MAAA;AAAA,EACzC;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAaA,OAAO,IAAA,CAEL,QAAA,EACA,OAAA,EACG;AACH,IAAA,OAAO,IAAI,IAAA,CAAK,QAAA,EAAU,OAAO,CAAA;AAAA,EACnC;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAYA,OAAO,OAAA,CAA4B,QAAA,EAAwB,OAAA,EAA4C;AACrG,IAAA,OAAO,IAAI,KAAA,CAAa,QAAA,EAAU,OAAO,CAAA;AAAA,EAC3C;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EASA,IAAI,OAAA,EAAqB;AACvB,IAAA,IAAA,CAAK,SAAA,CAAU,KAAK,OAAO,CAAA;AAC3B,IAAA,OAAO,IAAA,CAAK,SAAA,CAAU,IAAA,CAAK,QAAA,CAAS,SAAS,CAAC,CAAA;AAAA,EAChD;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EASA,QAAQ,QAAA,EAAsC;AAC5C,IAAA,MAAM,QAAmB,EAAC;AAC1B,IAAA,KAAA,MAAW,MAAM,QAAA,EAAU;AACzB,MAAA,IAAI,KAAK,WAAA,EAAa;AACpB,QAAA,MAAM,KAAK,IAAA,CAAK,GAAA,CAAI,IAAA,CAAK,WAAA,CAAY,EAAO,CAAC,CAAA;AAC7C,QAAA,KAAA,CAAM,KAAK,EAAE,CAAA;AAAA,MACf,CAAA,MAAO;AACL,QAAA,MAAM,EAAA,GAAK,IAAA,CAAK,GAAA,CAAI,EAAO,CAAA;AAC3B,QAAA,KAAA,CAAM,KAAK,EAAE,CAAA;AAAA,MACf;AAAA,IACF;AACA,IAAA,OAAO,KAAA;AAAA,EACT;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,IAAA,GAAsB;AACpB,IAAA,IAAI,IAAA,CAAK,QAAA,CAAS,MAAA,KAAW,CAAA,EAAG;AAChC,IAAA,MAAM,KAAA,GAAQ,IAAA,CAAK,QAAA,CAAS,CAAC,CAAA;AAC7B,IAAA,MAAM,IAAA,GAAO,IAAA,CAAK,QAAA,CAAS,GAAA,EAAI;AAC/B,IAAA,IAAI,IAAA,CAAK,SAAS,MAAA,EAAQ;AACxB,MAAA,IAAA,CAAK,QAAA,CAAS,CAAC,CAAA,GAAI,IAAA;AACnB,MAAA,IAAA,CAAK,SAAA,CAAU,CAAA,EAAG,IAAA,CAAK,QAAA,CAAS,UAAU,CAAC,CAAA;AAAA,IAC7C;AACA,IAAA,OAAO,KAAA;AAAA,EACT;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,IAAA,GAAsB;AACpB,IAAA,OAAO,IAAA,CAAK,SAAS,CAAC,CAAA;AAAA,EACxB;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,OAAA,GAAmB;AACjB,IAAA,OAAO,KAAK,IAAA,KAAS,CAAA;AAAA,EACvB;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,KAAA,GAAc;AACZ,IAAA,IAAA,CAAK,YAAY,EAAC;AAAA,EACpB;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EASA,OAAO,QAAA,EAAkC;AACvC,IAAA,IAAA,CAAK,SAAA,GAAY,KAAA,CAAM,IAAA,CAAK,QAAQ,CAAA;AACpC,IAAA,OAAO,KAAK,GAAA,EAAI;AAAA,EAClB;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EASS,IAAI,OAAA,EAAqB;AAChC,IAAA,KAAA,MAAW,EAAA,IAAM,KAAK,QAAA,EAAU,IAAI,KAAK,OAAA,CAAQ,EAAA,EAAI,OAAO,CAAA,EAAG,OAAO,IAAA;AACtE,IAAA,OAAO,KAAA;AAAA,EACT;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EASA,OAAO,OAAA,EAAqB;AAC1B,IAAA,IAAI,KAAA,GAAQ,EAAA;AACZ,IAAA,KAAA,IAAS,IAAI,CAAA,EAAG,CAAA,GAAI,IAAA,CAAK,QAAA,CAAS,QAAQ,CAAA,EAAA,EAAK;AAC7C,MAAA,IAAI,KAAK,OAAA,CAAQ,IAAA,CAAK,SAAS,CAAC,CAAA,EAAG,OAAO,CAAA,EAAG;AAC3C,QAAA,KAAA,GAAQ,CAAA;AACR,QAAA;AAAA,MACF;AAAA,IACF;AACA,IAAA,IAAI,KAAA,GAAQ,GAAG,OAAO,KAAA;AACtB,IAAA,IAAI,UAAU,CAAA,EAAG;AACf,MAAA,IAAA,CAAK,IAAA,EAAK;AAAA,IACZ,CAAA,MAAA,IAAW,KAAA,KAAU,IAAA,CAAK,QAAA,CAAS,SAAS,CAAA,EAAG;AAC7C,MAAA,IAAA,CAAK,SAAS,GAAA,EAAI;AAAA,IACpB,CAAA,MAAO;AACL,MAAA,IAAA,CAAK,SAAS,MAAA,CAAO,KAAA,EAAO,GAAG,IAAA,CAAK,QAAA,CAAS,KAAM,CAAA;AACnD,MAAA,IAAA,CAAK,UAAU,KAAK,CAAA;AACpB,MAAA,IAAA,CAAK,SAAA,CAAU,KAAA,EAAO,IAAA,CAAK,QAAA,CAAS,UAAU,CAAC,CAAA;AAAA,IACjD;AACA,IAAA,OAAO,IAAA;AAAA,EACT;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EASA,SAAS,SAAA,EAAwE;AAC/E,IAAA,IAAI,GAAA,GAAM,EAAA;AACV,IAAA,KAAA,IAAS,IAAI,CAAA,EAAG,CAAA,GAAI,IAAA,CAAK,QAAA,CAAS,QAAQ,CAAA,EAAA,EAAK;AAC7C,MAAA,IAAI,UAAU,IAAA,CAAK,QAAA,CAAS,CAAC,CAAA,EAAG,CAAA,EAAG,IAAI,CAAA,EAAG;AACxC,QAAA,GAAA,GAAM,CAAA;AACN,QAAA;AAAA,MACF;AAAA,IACF;AACA,IAAA,IAAI,GAAA,GAAM,GAAG,OAAO,KAAA;AACpB,IAAA,IAAI,QAAQ,CAAA,EAAG;AACb,MAAA,IAAA,CAAK,IAAA,EAAK;AAAA,IACZ,CAAA,MAAA,IAAW,GAAA,KAAQ,IAAA,CAAK,QAAA,CAAS,SAAS,CAAA,EAAG;AAC3C,MAAA,IAAA,CAAK,SAAS,GAAA,EAAI;AAAA,IACpB,CAAA,MAAO;AACL,MAAA,IAAA,CAAK,SAAS,MAAA,CAAO,GAAA,EAAK,GAAG,IAAA,CAAK,QAAA,CAAS,KAAM,CAAA;AACjD,MAAA,IAAA,CAAK,UAAU,GAAG,CAAA;AAClB,MAAA,IAAA,CAAK,SAAA,CAAU,GAAA,EAAK,IAAA,CAAK,QAAA,CAAS,UAAU,CAAC,CAAA;AAAA,IAC/C;AACA,IAAA,OAAO,IAAA;AAAA,EACT;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EASA,YAAY,MAAA,EAAuC;AACjD,IAAA,IAAA,CAAK,OAAA,GAAU,MAAA;AACf,IAAA,OAAO,IAAA;AAAA,EACT;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EASA,GAAA,CAAI,QAAyB,KAAA,EAAY;AACvC,IAAA,MAAM,SAAc,EAAC;AACrB,IAAA,MAAM,IAAA,2BAAQ,KAAA,KAAkB;AAC9B,MAAA,MAAM,IAAA,GAAO,CAAA,GAAI,KAAA,GAAQ,CAAA,EACvB,QAAQ,IAAA,GAAO,CAAA;AACjB,MAAA,IAAI,KAAA,GAAQ,KAAK,IAAA,EAAM;AACrB,QAAA,IAAI,UAAU,IAAA,EAAM;AAClB,UAAA,IAAA,CAAK,IAAI,CAAA;AACT,UAAA,MAAA,CAAO,IAAA,CAAK,IAAA,CAAK,QAAA,CAAS,KAAK,CAAC,CAAA;AAChC,UAAA,IAAA,CAAK,KAAK,CAAA;AAAA,QACZ,CAAA,MAAA,IAAW,UAAU,KAAA,EAAO;AAC1B,UAAA,MAAA,CAAO,IAAA,CAAK,IAAA,CAAK,QAAA,CAAS,KAAK,CAAC,CAAA;AAChC,UAAA,IAAA,CAAK,IAAI,CAAA;AACT,UAAA,IAAA,CAAK,KAAK,CAAA;AAAA,QACZ,CAAA,MAAA,IAAW,UAAU,MAAA,EAAQ;AAC3B,UAAA,IAAA,CAAK,IAAI,CAAA;AACT,UAAA,IAAA,CAAK,KAAK,CAAA;AACV,UAAA,MAAA,CAAO,IAAA,CAAK,IAAA,CAAK,QAAA,CAAS,KAAK,CAAC,CAAA;AAAA,QAClC;AAAA,MACF;AAAA,IACF,CAAA,EAlBa,MAAA,CAAA;AAmBb,IAAA,IAAA,CAAK,CAAC,CAAA;AACN,IAAA,OAAO,MAAA;AAAA,EACT;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,GAAA,GAAiB;AACf,IAAA,MAAM,UAAqB,EAAC;AAC5B,IAAA,KAAA,IAAS,CAAA,GAAI,IAAA,CAAK,KAAA,CAAM,IAAA,CAAK,IAAA,GAAO,CAAC,CAAA,GAAI,CAAA,EAAG,CAAA,IAAK,CAAA,EAAG,CAAA,EAAA,EAAK;AACvD,MAAA,OAAA,CAAQ,IAAA,CAAK,KAAK,SAAA,CAAU,CAAA,EAAG,KAAK,QAAA,CAAS,MAAA,IAAU,CAAC,CAAC,CAAA;AAAA,IAC3D;AACA,IAAA,OAAO,OAAA;AAAA,EACT;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,IAAA,GAAY;AACV,IAAA,MAAM,UAAe,EAAC;AACtB,IAAA,MAAM,MAAA,GAAS,KAAK,eAAA,EAAgB;AACpC,IAAA,KAAA,MAAW,CAAA,IAAK,IAAA,CAAK,QAAA,EAAU,MAAA,CAAO,IAAI,CAAC,CAAA;AAC3C,IAAA,OAAO,CAAC,MAAA,CAAO,OAAA,EAAQ,EAAG;AACxB,MAAA,MAAM,GAAA,GAAM,OAAO,IAAA,EAAK;AACxB,MAAA,IAAI,GAAA,KAAQ,MAAA,EAAW,OAAA,CAAQ,IAAA,CAAK,GAAG,CAAA;AAAA,IACzC;AACA,IAAA,OAAO,OAAA;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,CAAK,QAAA,EAAU,IAAA,CAAK,IAAI,CAAC,CAAA;AACzC,IAAA,OAAO,IAAA;AAAA,EACT;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAUA,MAAA,CAAO,UAA0C,OAAA,EAAyB;AACxE,IAAA,MAAM,GAAA,GAAM,KAAK,eAAA,EAAgB;AACjC,IAAA,IAAI,CAAA,GAAI,CAAA;AACR,IAAA,KAAA,MAAW,KAAK,IAAA,EAAM;AACpB,MAAA,IAAI,OAAA,KAAY,MAAA,GAAY,QAAA,CAAS,CAAA,EAAG,CAAA,EAAA,EAAK,IAAI,CAAA,GAAI,QAAA,CAAS,IAAA,CAAK,OAAA,EAAS,CAAA,EAAG,CAAA,EAAA,EAAK,IAAI,CAAA,EAAG;AACzF,QAAA,GAAA,CAAI,IAAI,CAAC,CAAA;AAAA,MACX,CAAA,MAAO;AACL,QAAA,CAAA,EAAA;AAAA,MACF;AAAA,IACF;AACA,IAAA,OAAO,GAAA;AAAA,EACT;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAaA,GAAA,CACE,QAAA,EACA,OAAA,EACA,OAAA,EACc;AACd,IAAA,MAAM,EAAE,UAAA,EAAY,WAAA,EAAa,GAAG,IAAA,EAAK,GAAI,4BAAW,EAAC;AACzD,IAAA,IAAI,CAAC,UAAA,EAAY,MAAM,IAAI,UAAU,6CAA6C,CAAA;AAClF,IAAA,MAAM,GAAA,GAAM,IAAA,CAAK,WAAA,CAAoB,EAAC,EAAG,EAAE,GAAG,IAAA,EAAM,UAAA,EAAY,WAAA,EAAa,CAAA;AAC7E,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,GAAA,CAAI,IAAI,CAAC,CAAA;AAAA,IACX;AACA,IAAA,OAAO,GAAA;AAAA,EACT;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAUA,OAAA,CAAQ,UAAoC,OAAA,EAAyB;AACnE,IAAA,MAAM,GAAA,GAAM,KAAK,eAAA,EAAgB;AACjC,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,GAAA,CAAI,IAAI,CAAC,CAAA;AAAA,IACX;AACA,IAAA,OAAO,GAAA;AAAA,EACT;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAsBA,IAAI,UAAA,GAAa;AACf,IAAA,OAAO,IAAA,CAAK,WAAA;AAAA,EACd;AAAA,EAEA,CAAW,YAAA,GAAoC;AAC7C,IAAA,KAAA,MAAW,OAAA,IAAW,IAAA,CAAK,QAAA,EAAU,MAAM,OAAA;AAAA,EAC7C;AAAA,EAEU,UAAU,KAAA,EAAwB;AAC1C,IAAA,MAAM,OAAA,GAAU,IAAA,CAAK,QAAA,CAAS,KAAK,CAAA;AACnC,IAAA,OAAO,QAAQ,CAAA,EAAG;AAChB,MAAA,MAAM,MAAA,GAAU,QAAQ,CAAA,IAAM,CAAA;AAC9B,MAAA,MAAM,UAAA,GAAa,IAAA,CAAK,QAAA,CAAS,MAAM,CAAA;AACvC,MAAA,IAAI,IAAA,CAAK,UAAA,CAAW,UAAA,EAAY,OAAO,KAAK,CAAA,EAAG;AAC/C,MAAA,IAAA,CAAK,QAAA,CAAS,KAAK,CAAA,GAAI,UAAA;AACvB,MAAA,KAAA,GAAQ,MAAA;AAAA,IACV;AACA,IAAA,IAAA,CAAK,QAAA,CAAS,KAAK,CAAA,GAAI,OAAA;AACvB,IAAA,OAAO,IAAA;AAAA,EACT;AAAA,EAEU,SAAA,CAAU,OAAe,UAAA,EAA6B;AAC9D,IAAA,MAAM,OAAA,GAAU,IAAA,CAAK,QAAA,CAAS,KAAK,CAAA;AACnC,IAAA,OAAO,QAAQ,UAAA,EAAY;AACzB,MAAA,IAAI,IAAA,GAAQ,SAAS,CAAA,GAAK,CAAA;AAC1B,MAAA,MAAM,QAAQ,IAAA,GAAO,CAAA;AACrB,MAAA,IAAI,OAAA,GAAU,IAAA,CAAK,QAAA,CAAS,IAAI,CAAA;AAChC,MAAA,IAAI,KAAA,GAAQ,IAAA,CAAK,QAAA,CAAS,MAAA,IAAU,IAAA,CAAK,UAAA,CAAW,OAAA,EAAS,IAAA,CAAK,QAAA,CAAS,KAAK,CAAC,CAAA,GAAI,CAAA,EAAG;AACtF,QAAA,IAAA,GAAO,KAAA;AACP,QAAA,OAAA,GAAU,IAAA,CAAK,SAAS,KAAK,CAAA;AAAA,MAC/B;AACA,MAAA,IAAI,IAAA,CAAK,UAAA,CAAW,OAAA,EAAS,OAAO,KAAK,CAAA,EAAG;AAC5C,MAAA,IAAA,CAAK,QAAA,CAAS,KAAK,CAAA,GAAI,OAAA;AACvB,MAAA,KAAA,GAAQ,IAAA;AAAA,IACV;AACA,IAAA,IAAA,CAAK,QAAA,CAAS,KAAK,CAAA,GAAI,OAAA;AACvB,IAAA,OAAO,IAAA;AAAA,EACT;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EASU,gBAAgB,OAAA,EAAmC;AAC3D,IAAA,MAAM,OAAY,IAAA,CAAK,WAAA;AACvB,IAAA,MAAM,OAAY,IAAI,IAAA,CAAK,EAAC,EAAG,EAAE,UAAA,EAAY,IAAA,CAAK,UAAA,EAAY,WAAA,EAAa,KAAK,WAAA,EAAa,GAAI,OAAA,IAAA,IAAA,GAAA,OAAA,GAAW,IAAK,CAAA;AACjH,IAAA,OAAO,IAAA;AAAA,EACT;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAYU,WAAA,CACR,QAAA,GAAwC,EAAC,EACzC,OAAA,EACc;AACd,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;AAAA,EAWU,WAAmB,OAAA,EAA6C;AACxE,IAAA,OAAO,IAAA,CAAK,WAAA,CAAoB,EAAC,EAAG,OAAO,CAAA;AAAA,EAC7C;AACF,CAAA;AAtfsE,MAAA,CAAA,KAAA,EAAA,MAAA,CAAA;AAA/D,IAAM,IAAA,GAAN;AA6fA,IAAM,kBAAA,GAAN,MAAM,kBAAA,CAAqB;AAAA,EAShC,WAAA,CAAY,OAAA,EAAY,MAAA,GAAS,CAAA,EAAG;AARpC,IAAA,aAAA,CAAA,IAAA,EAAA,SAAA,CAAA;AACA,IAAA,aAAA,CAAA,IAAA,EAAA,QAAA,CAAA;AACA,IAAA,aAAA,CAAA,IAAA,EAAA,MAAA,CAAA;AACA,IAAA,aAAA,CAAA,IAAA,EAAA,OAAA,CAAA;AACA,IAAA,aAAA,CAAA,IAAA,EAAA,OAAA,CAAA;AACA,IAAA,aAAA,CAAA,IAAA,EAAA,QAAA,CAAA;AACA,IAAA,aAAA,CAAA,IAAA,EAAA,QAAA,CAAA;AAGE,IAAA,IAAA,CAAK,OAAA,GAAU,OAAA;AACf,IAAA,IAAA,CAAK,MAAA,GAAS,MAAA;AACd,IAAA,IAAA,CAAK,MAAA,GAAS,KAAA;AAAA,EAChB;AACF,CAAA;AAdkC,MAAA,CAAA,kBAAA,EAAA,mBAAA,CAAA;AAA3B,IAAM,iBAAA,GAAN;AAsBA,IAAM,cAAA,GAAN,MAAM,cAAA,CAAiB;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQ5B,YAAY,UAAA,EAA4B;AAMxC,IAAA,aAAA,CAAA,IAAA,EAAU,OAAA,CAAA;AAYV,IAAA,aAAA,CAAA,IAAA,EAAU,OAAA,EAAQ,CAAA,CAAA;AAKlB,IAAA,aAAA,CAAA,IAAA,EAAU,MAAA,CAAA;AAYV,IAAA,aAAA,CAAA,IAAA,EAAU,aAAA,CAAA;AAlCR,IAAA,IAAA,CAAK,KAAA,EAAM;AACX,IAAA,IAAA,CAAK,WAAA,GAAc,cAAc,IAAA,CAAK,kBAAA;AACtC,IAAA,IAAI,OAAO,IAAA,CAAK,UAAA,KAAe,YAAY,MAAM,IAAI,MAAM,+CAA+C,CAAA;AAAA,EAC5G;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAUA,IAAI,IAAA,GAAyC;AAC3C,IAAA,OAAO,IAAA,CAAK,KAAA;AAAA,EACd;AAAA,EAGA,IAAI,IAAA,GAAe;AACjB,IAAA,OAAO,IAAA,CAAK,KAAA;AAAA,EACd;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAUA,IAAI,GAAA,GAAwC;AAC1C,IAAA,OAAO,IAAA,CAAK,IAAA;AAAA,EACd;AAAA,EAGA,IAAI,UAAA,GAA4B;AAC9B,IAAA,OAAO,IAAA,CAAK,WAAA;AAAA,EACd;AAAA,EAEA,KAAA,GAAc;AACZ,IAAA,IAAA,CAAK,KAAA,GAAQ,MAAA;AACb,IAAA,IAAA,CAAK,IAAA,GAAO,MAAA;AACZ,IAAA,IAAA,CAAK,KAAA,GAAQ,CAAA;AAAA,EACf;AAAA,EAEA,IAAI,OAAA,EAAqB;AACvB,IAAA,IAAA,CAAK,KAAK,OAAO,CAAA;AACjB,IAAA,OAAO,IAAA;AAAA,EACT;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EASA,KAAK,OAAA,EAAkB;AACrB,IAAA,MAAM,IAAA,GAAO,IAAA,CAAK,UAAA,CAAW,OAAO,CAAA;AACpC,IAAA,IAAA,CAAK,IAAA,GAAO,IAAA;AACZ,IAAA,IAAA,CAAK,KAAA,GAAQ,IAAA;AACb,IAAA,IAAA,CAAK,cAAc,IAAI,CAAA;AACvB,IAAA,IAAI,CAAC,IAAA,CAAK,GAAA,IAAO,IAAA,CAAK,UAAA,CAAW,IAAA,CAAK,OAAA,EAAS,IAAA,CAAK,GAAA,CAAI,OAAO,CAAA,IAAK,CAAA,OAAQ,IAAA,GAAO,IAAA;AACnF,IAAA,IAAA,CAAK,KAAA,EAAA;AACL,IAAA,OAAO,IAAA;AAAA,EACT;AAAA,EAEA,IAAA,GAAsB;AACpB,IAAA,OAAO,IAAA,CAAK,GAAA,GAAM,IAAA,CAAK,GAAA,CAAI,OAAA,GAAU,MAAA;AAAA,EACvC;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EASA,kBAAkB,IAAA,EAAqD;AACrE,IAAA,MAAM,WAAmC,EAAC;AAC1C,IAAA,IAAI,CAAC,MAAM,OAAO,QAAA;AAClB,IAAA,IAAI,IAAA,GAAyC,IAAA;AAC7C,IAAA,IAAI,OAAA,GAAU,KAAA;AACd,IAAA,OAAO,IAAA,EAAM;AACX,MAAA,IAAI,IAAA,KAAS,QAAQ,OAAA,EAAS;AAAA,WAAA,IACrB,IAAA,KAAS,MAAM,OAAA,GAAU,IAAA;AAClC,MAAA,QAAA,CAAS,KAAK,IAAK,CAAA;AACnB,MAAA,IAAA,GAAO,IAAA,CAAM,KAAA;AAAA,IACf;AACA,IAAA,OAAO,QAAA;AAAA,EACT;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAUA,cAAA,CAAe,QAA8B,IAAA,EAAkC;AAC7E,IAAA,IAAI,CAAC,MAAA,CAAO,KAAA,EAAO,MAAA,CAAO,KAAA,GAAQ,IAAA;AAAA,SAC7B;AACH,MAAA,IAAA,CAAK,KAAA,GAAQ,OAAO,KAAA,CAAM,KAAA;AAC1B,MAAA,IAAA,CAAK,OAAO,MAAA,CAAO,KAAA;AACnB,MAAA,MAAA,CAAO,KAAA,CAAM,MAAO,IAAA,GAAO,IAAA;AAC3B,MAAA,MAAA,CAAO,MAAM,KAAA,GAAQ,IAAA;AAAA,IACvB;AAAA,EACF;AAAA,EAEA,IAAA,GAAsB;AACpB,IAAA,OAAO,KAAK,GAAA,EAAI;AAAA,EAClB;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,GAAA,GAAqB;AACnB,IAAA,IAAI,IAAA,CAAK,KAAA,KAAU,CAAA,EAAG,OAAO,MAAA;AAC7B,IAAA,MAAM,IAAI,IAAA,CAAK,GAAA;AACf,IAAA,IAAI,EAAE,KAAA,EAAO;AACX,MAAA,MAAM,QAAA,GAAW,IAAA,CAAK,iBAAA,CAAkB,CAAA,CAAE,KAAK,CAAA;AAC/C,MAAA,KAAA,MAAW,QAAQ,QAAA,EAAU;AAC3B,QAAA,IAAA,CAAK,cAAc,IAAI,CAAA;AACvB,QAAA,IAAA,CAAK,MAAA,GAAS,MAAA;AAAA,MAChB;AAAA,IACF;AACA,IAAA,IAAA,CAAK,eAAe,CAAC,CAAA;AACrB,IAAA,IAAI,CAAA,KAAM,EAAE,KAAA,EAAO;AACjB,MAAA,IAAA,CAAK,IAAA,GAAO,MAAA;AACZ,MAAA,IAAA,CAAK,KAAA,GAAQ,MAAA;AAAA,IACf,CAAA,MAAO;AACL,MAAA,IAAA,CAAK,OAAO,CAAA,CAAE,KAAA;AACd,MAAA,IAAA,CAAK,YAAA,EAAa;AAAA,IACpB;AACA,IAAA,IAAA,CAAK,KAAA,EAAA;AACL,IAAA,OAAO,CAAA,CAAE,OAAA;AAAA,EACX;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EASA,MAAM,WAAA,EAAqC;AACzC,IAAA,IAAI,WAAA,CAAY,SAAS,CAAA,EAAG;AAC5B,IAAA,IAAI,IAAA,CAAK,IAAA,IAAQ,WAAA,CAAY,IAAA,EAAM;AACjC,MAAA,MAAM,QAAA,GAAW,IAAA,CAAK,IAAA,EACpB,SAAA,GAAY,WAAA,CAAY,IAAA;AAC1B,MAAA,MAAM,aAAA,GAAgB,QAAA,CAAS,KAAA,EAC7B,aAAA,GAAgB,SAAA,CAAU,IAAA;AAC5B,MAAA,QAAA,CAAS,KAAA,GAAQ,SAAA;AACjB,MAAA,SAAA,CAAU,IAAA,GAAO,QAAA;AACjB,MAAA,aAAA,CAAc,IAAA,GAAO,aAAA;AACrB,MAAA,aAAA,CAAc,KAAA,GAAQ,aAAA;AAAA,IACxB,CAAA,MAAA,IAAW,CAAC,IAAA,CAAK,IAAA,IAAQ,YAAY,IAAA,EAAM;AACzC,MAAA,IAAA,CAAK,QAAQ,WAAA,CAAY,IAAA;AAAA,IAC3B;AACA,IAAA,IAAI,CAAC,IAAA,CAAK,GAAA,IAAQ,WAAA,CAAY,OAAO,IAAA,CAAK,UAAA,CAAW,WAAA,CAAY,GAAA,CAAI,OAAA,EAAS,IAAA,CAAK,GAAA,CAAI,OAAO,IAAI,CAAA,EAAI;AACpG,MAAA,IAAA,CAAK,OAAO,WAAA,CAAY,GAAA;AAAA,IAC1B;AACA,IAAA,IAAA,CAAK,SAAS,WAAA,CAAY,IAAA;AAC1B,IAAA,WAAA,CAAY,KAAA,EAAM;AAAA,EACpB;AAAA,EAEA,WAAW,OAAA,EAAkC;AAC3C,IAAA,OAAO,IAAI,kBAAqB,OAAO,CAAA;AAAA,EACzC;AAAA,EAEA,OAAA,GAAmB;AACjB,IAAA,OAAO,KAAK,KAAA,KAAU,CAAA;AAAA,EACxB;AAAA,EAEU,kBAAA,CAAmB,GAAM,CAAA,EAAc;AAC/C,IAAA,IAAI,CAAA,GAAI,GAAG,OAAO,EAAA;AAClB,IAAA,IAAI,CAAA,GAAI,GAAG,OAAO,CAAA;AAClB,IAAA,OAAO,CAAA;AAAA,EACT;AAAA,EAEU,cAAc,IAAA,EAAkC;AACxD,IAAA,IAAI,CAAC,IAAA,CAAK,IAAA,EAAM,IAAA,CAAK,KAAA,GAAQ,IAAA;AAAA,SACxB;AACH,MAAA,IAAA,CAAK,KAAA,GAAQ,KAAK,IAAA,CAAK,KAAA;AACvB,MAAA,IAAA,CAAK,OAAO,IAAA,CAAK,IAAA;AACjB,MAAA,IAAA,CAAK,IAAA,CAAK,MAAO,IAAA,GAAO,IAAA;AACxB,MAAA,IAAA,CAAK,KAAK,KAAA,GAAQ,IAAA;AAAA,IACpB;AAAA,EACF;AAAA,EAEU,eAAe,IAAA,EAAkC;AACzD,IAAA,IAAI,IAAA,CAAK,IAAA,KAAS,IAAA,EAAM,IAAA,CAAK,QAAQ,IAAA,CAAK,KAAA;AAC1C,IAAA,IAAI,IAAA,CAAK,IAAA,EAAM,IAAA,CAAK,IAAA,CAAK,QAAQ,IAAA,CAAK,KAAA;AACtC,IAAA,IAAI,IAAA,CAAK,KAAA,EAAO,IAAA,CAAK,KAAA,CAAM,OAAO,IAAA,CAAK,IAAA;AAAA,EACzC;AAAA,EAEU,KAAA,CAAM,GAAyB,CAAA,EAA+B;AACtE,IAAA,IAAA,CAAK,eAAe,CAAC,CAAA;AACrB,IAAA,CAAA,CAAE,IAAA,GAAO,CAAA;AACT,IAAA,CAAA,CAAE,KAAA,GAAQ,CAAA;AACV,IAAA,IAAA,CAAK,cAAA,CAAe,GAAG,CAAC,CAAA;AACxB,IAAA,CAAA,CAAE,MAAA,EAAA;AACF,IAAA,CAAA,CAAE,MAAA,GAAS,CAAA;AAAA,EACb;AAAA,EAEU,YAAA,GAAqB;AAC7B,IAAA,MAAM,CAAA,GAA0C,IAAI,KAAA,CAAM,IAAA,CAAK,KAAK,CAAA;AACpE,IAAA,MAAM,QAAA,GAAW,IAAA,CAAK,iBAAA,CAAkB,IAAA,CAAK,IAAI,CAAA;AACjD,IAAA,IAAI,CAAA,EACF,GACA,CAAA,EACA,CAAA;AAEF,IAAA,KAAA,MAAW,QAAQ,QAAA,EAAU;AAC3B,MAAA,CAAA,GAAI,IAAA;AACJ,MAAA,CAAA,GAAI,CAAA,CAAE,MAAA;AACN,MAAA,OAAO,CAAA,CAAE,CAAC,CAAA,EAAG;AACX,QAAA,CAAA,GAAI,EAAE,CAAC,CAAA;AACP,QAAA,IAAI,KAAK,UAAA,CAAW,CAAA,CAAE,SAAS,CAAA,CAAE,OAAO,IAAI,CAAA,EAAG;AAC7C,UAAA,CAAA,GAAI,CAAA;AACJ,UAAA,CAAA,GAAI,CAAA;AACJ,UAAA,CAAA,GAAI,CAAA;AAAA,QACN;AACA,QAAA,IAAA,CAAK,KAAA,CAAM,GAAG,CAAC,CAAA;AACf,QAAA,CAAA,CAAE,CAAC,CAAA,GAAI,MAAA;AACP,QAAA,CAAA,EAAA;AAAA,MACF;AACA,MAAA,CAAA,CAAE,CAAC,CAAA,GAAI,CAAA;AAAA,IACT;AAEA,IAAA,KAAA,IAAS,CAAA,GAAI,CAAA,EAAG,CAAA,GAAI,CAAA,CAAE,QAAQ,CAAA,EAAA,EAAK;AACjC,MAAA,IAAI,CAAA,CAAE,CAAC,CAAA,KAAM,CAAC,KAAK,GAAA,IAAO,IAAA,CAAK,WAAW,CAAA,CAAE,CAAC,EAAG,OAAA,EAAS,IAAA,CAAK,IAAI,OAAO,CAAA,IAAK,IAAI,IAAA,CAAK,IAAA,GAAO,EAAE,CAAC,CAAA;AAAA,IACnG;AAAA,EACF;AACF,CAAA;AAvP8B,MAAA,CAAA,cAAA,EAAA,eAAA,CAAA;AAAvB,IAAM,aAAA,GAAN;;;ACrsBA,IAAM,cAAA,GAAN,MAAM,cAAA,SAAwC,IAAA,CAAW;AAAA,EAC9D,WAAA,CAAY,QAAA,GAAsC,EAAC,EAAG,OAAA,EAAsC;AAC1F,IAAA,KAAA,CAAM,UAAU,OAAO,CAAA;AAAA,EACzB;AACF,CAAA;AAJgE,MAAA,CAAA,cAAA,EAAA,eAAA,CAAA;AAAzD,IAAM,aAAA,GAAN;;;ACIA,IAAM,iBAAA,GAAN,MAAM,iBAAA,SAA2C,aAAA,CAAoB;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAO1E,WAAA,CAAY,QAAA,GAAsC,EAAC,EAAG,OAAA,EAAsC;AAC1F,IAAA,KAAA,CAAM,UAAU,OAAO,CAAA;AAAA,EACzB;AACF,CAAA;AAV4E,MAAA,CAAA,iBAAA,EAAA,kBAAA,CAAA;AAArE,IAAM,gBAAA,GAAN;;;AC2HP,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,MAAA,GAAN,MAAM,MAAA,CAAS;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;AAAA,EAGA,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,CAAA;AAjBsB,MAAA,CAAA,MAAA,EAAA,OAAA,CAAA;AAAf,IAAM,KAAA,GAAN","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 { Comparator, DFSOrderPattern, ElementCallback, HeapOptions } from '../../types';\nimport { IterableElementBase } from '../base';\n\n/**\n * Binary heap with pluggable comparator; supports fast insertion and removal of the top element.\n * @remarks Time O(1), Space O(1)\n * @template E\n * @template R\n * 1. Complete Binary Tree: Heaps are typically complete binary trees, meaning every level is fully filled except possibly for the last level, which has nodes as far left as possible.\n * 2. Heap Properties: Each node in a heap follows a specific order property, which varies depending on the type of heap:\n * Max Heap: The value of each parent node is greater than or equal to the value of its children.\n * Min Heap: The value of each parent node is less than or equal to the value of its children.\n * 3. Root Node Access: In a heap, the largest element (in a max heap) or the smallest element (in a min heap) is always at the root of the tree.\n * 4. Efficient Insertion and Deletion: Due to its structure, a heap allows for insertion and deletion operations in logarithmic time (O(log n)).\n * 5. Managing Dynamic Data Sets: Heaps effectively manage dynamic data sets, especially when frequent access to the largest or smallest elements is required.\n * 6. Non-linear Search: While a heap allows rapid access to its largest or smallest element, it is less efficient for other operations, such as searching for a specific element, as it is not designed for these tasks.\n * 7. Efficient Sorting Algorithms: For example, heap sort. Heap sort uses the properties of a heap to sort elements.\n * 8. Graph Algorithms: Such as Dijkstra's shortest path algorithm and Prime's minimum-spanning tree algorithm, which use heaps to improve performance.\n * @example\n * // Use Heap to sort an array\n * function heapSort(arr: number[]): number[] {\n * const heap = new Heap(arr, { comparator: (a, b) => a - b });\n * const sorted: number[] = [];\n * while (!heap.isEmpty()) {\n * sorted.push(heap.poll()!); // Poll minimum element\n * }\n * return sorted;\n * }\n *\n * const array = [5, 3, 8, 4, 1, 2];\n * console.log(heapSort(array)); // [1, 2, 3, 4, 5, 8]\n * @example\n * // Use Heap to solve top k problems\n * function topKElements(arr: number[], k: number): number[] {\n * const heap = new Heap([], { comparator: (a, b) => b - a }); // Max heap\n * arr.forEach(num => {\n * heap.add(num);\n * if (heap.size > k) heap.poll(); // Keep the heap size at K\n * });\n * return heap.toArray();\n * }\n *\n * const numbers = [10, 30, 20, 5, 15, 25];\n * console.log(topKElements(numbers, 3)); // [15, 10, 5]\n * @example\n * // Use Heap to merge sorted sequences\n * function mergeSortedSequences(sequences: number[][]): number[] {\n * const heap = new Heap<{ value: number; seqIndex: number; itemIndex: number }>([], {\n * comparator: (a, b) => a.value - b.value // Min heap\n * });\n *\n * // Initialize heap\n * sequences.forEach((seq, seqIndex) => {\n * if (seq.length) {\n * heap.add({ value: seq[0], seqIndex, itemIndex: 0 });\n * }\n * });\n *\n * const merged: number[] = [];\n * while (!heap.isEmpty()) {\n * const { value, seqIndex, itemIndex } = heap.poll()!;\n * merged.push(value);\n *\n * if (itemIndex + 1 < sequences[seqIndex].length) {\n * heap.add({\n * value: sequences[seqIndex][itemIndex + 1],\n * seqIndex,\n * itemIndex: itemIndex + 1\n * });\n * }\n * }\n *\n * return merged;\n * }\n *\n * const sequences = [\n * [1, 4, 7],\n * [2, 5, 8],\n * [3, 6, 9]\n * ];\n * console.log(mergeSortedSequences(sequences)); // [1, 2, 3, 4, 5, 6, 7, 8, 9]\n * @example\n * // Use Heap to dynamically maintain the median\n * class MedianFinder {\n * private low: MaxHeap; // Max heap, stores the smaller half\n * private high: MinHeap; // Min heap, stores the larger half\n *\n * constructor() {\n * this.low = new MaxHeap([]);\n * this.high = new MinHeap([]);\n * }\n *\n * addNum(num: number): void {\n * if (this.low.isEmpty() || num <= this.low.peek()!) this.low.add(num);\n * else this.high.add(num);\n *\n * // Balance heaps\n * if (this.low.size > this.high.size + 1) this.high.add(this.low.poll()!);\n * else if (this.high.size > this.low.size) this.low.add(this.high.poll()!);\n * }\n *\n * findMedian(): number {\n * if (this.low.size === this.high.size) return (this.low.peek()! + this.high.peek()!) / 2;\n * return this.low.peek()!;\n * }\n * }\n *\n * const medianFinder = new MedianFinder();\n * medianFinder.addNum(10);\n * console.log(medianFinder.findMedian()); // 10\n * medianFinder.addNum(20);\n * console.log(medianFinder.findMedian()); // 15\n * medianFinder.addNum(30);\n * console.log(medianFinder.findMedian()); // 20\n * medianFinder.addNum(40);\n * console.log(medianFinder.findMedian()); // 25\n * medianFinder.addNum(50);\n * console.log(medianFinder.findMedian()); // 30\n * @example\n * // Use Heap for load balancing\n * function loadBalance(requests: number[], servers: number): number[] {\n * const serverHeap = new Heap<{ id: number; load: number }>([], { comparator: (a, b) => a.load - b.load }); // min heap\n * const serverLoads = new Array(servers).fill(0);\n *\n * for (let i = 0; i < servers; i++) {\n * serverHeap.add({ id: i, load: 0 });\n * }\n *\n * requests.forEach(req => {\n * const server = serverHeap.poll()!;\n * serverLoads[server.id] += req;\n * server.load += req;\n * serverHeap.add(server); // The server after updating the load is re-entered into the heap\n * });\n *\n * return serverLoads;\n * }\n *\n * const requests = [5, 2, 8, 3, 7];\n * console.log(loadBalance(requests, 3)); // [12, 8, 5]\n * @example\n * // Use Heap to schedule tasks\n * type Task = [string, number];\n *\n * function scheduleTasks(tasks: Task[], machines: number): Map {\n * const machineHeap = new Heap<{ id: number; load: number }>([], { comparator: (a, b) => a.load - b.load }); // Min heap\n * const allocation = new Map();\n *\n * // Initialize the load on each machine\n * for (let i = 0; i < machines; i++) {\n * machineHeap.add({ id: i, load: 0 });\n * allocation.set(i, []);\n * }\n *\n * // Assign tasks\n * tasks.forEach(([task, load]) => {\n * const machine = machineHeap.poll()!;\n * allocation.get(machine.id)!.push([task, load]);\n * machine.load += load;\n * machineHeap.add(machine); // The machine after updating the load is re-entered into the heap\n * });\n *\n * return allocation;\n * }\n *\n * const tasks: Task[] = [\n * ['Task1', 3],\n * ['Task2', 1],\n * ['Task3', 2],\n * ['Task4', 5],\n * ['Task5', 4]\n * ];\n * const expectedMap = new Map();\n * expectedMap.set(0, [\n * ['Task1', 3],\n * ['Task4', 5]\n * ]);\n * expectedMap.set(1, [\n * ['Task2', 1],\n * ['Task3', 2],\n * ['Task5', 4]\n * ]);\n * console.log(scheduleTasks(tasks, 2)); // expectedMap\n */\nexport class Heap extends IterableElementBase {\n protected _equals: (a: E, b: E) => boolean = Object.is;\n\n /**\n * Create a Heap and optionally bulk-insert elements.\n * @remarks Time O(N), Space O(N)\n * @param [elements] - Iterable of elements (or raw values if toElementFn is set).\n * @param [options] - Options such as comparator and toElementFn.\n * @returns New Heap instance.\n */\n\n constructor(elements: Iterable = [], options?: HeapOptions) {\n super(options);\n\n if (options) {\n const { comparator } = options;\n if (comparator) this._comparator = comparator;\n }\n\n this.addMany(elements as Iterable);\n }\n\n protected _elements: E[] = [];\n\n /**\n * Get the backing array of the heap.\n * @remarks Time O(1), Space O(1)\n * @returns Internal elements array.\n */\n\n get elements(): E[] {\n return this._elements;\n }\n\n /**\n * Get the number of elements.\n * @remarks Time O(1), Space O(1)\n * @returns Heap size.\n */\n\n get size(): number {\n return this.elements.length;\n }\n\n /**\n * Get the last leaf element.\n * @remarks Time O(1), Space O(1)\n * @returns Last element or undefined.\n */\n\n get leaf(): E | undefined {\n return this.elements[this.size - 1] ?? undefined;\n }\n\n /**\n * Create a heap of the same class from an iterable.\n * @remarks Time O(N), Space O(N)\n * @template T\n * @template R\n * @template S\n * @param [elements] - Iterable of elements or raw records.\n * @param [options] - Heap options including comparator.\n * @returns A new heap instance of this class.\n */\n\n static from = Heap>(\n this: new (elements?: Iterable, options?: HeapOptions) => S,\n elements?: Iterable,\n options?: HeapOptions\n ): S {\n return new this(elements, options);\n }\n\n /**\n * Build a Heap from an iterable in linear time given a comparator.\n * @remarks Time O(N), Space O(N)\n * @template EE\n * @template RR\n * @param elements - Iterable of elements.\n * @param options - Heap options including comparator.\n * @returns A new Heap built from elements.\n */\n\n static heapify(elements: Iterable, options: HeapOptions): Heap {\n return new Heap(elements, options);\n }\n\n /**\n * Insert an element.\n * @remarks Time O(1) amortized, Space O(1)\n * @param element - Element to insert.\n * @returns True.\n */\n\n add(element: E): boolean {\n this._elements.push(element);\n return this._bubbleUp(this.elements.length - 1);\n }\n\n /**\n * Insert many elements from an iterable.\n * @remarks Time O(N log N), Space O(1)\n * @param elements - Iterable of elements or raw values.\n * @returns Array of per-element success flags.\n */\n\n addMany(elements: Iterable): boolean[] {\n const flags: boolean[] = [];\n for (const el of elements) {\n if (this.toElementFn) {\n const ok = this.add(this.toElementFn(el as R));\n flags.push(ok);\n } else {\n const ok = this.add(el as E);\n flags.push(ok);\n }\n }\n return flags;\n }\n\n /**\n * Remove and return the top element.\n * @remarks Time O(log N), Space O(1)\n * @returns Top element or undefined.\n */\n\n poll(): E | undefined {\n if (this.elements.length === 0) return;\n const value = this.elements[0];\n const last = this.elements.pop()!;\n if (this.elements.length) {\n this.elements[0] = last;\n this._sinkDown(0, this.elements.length >> 1);\n }\n return value;\n }\n\n /**\n * Get the current top element without removing it.\n * @remarks Time O(1), Space O(1)\n * @returns Top element or undefined.\n */\n\n peek(): E | undefined {\n return this.elements[0];\n }\n\n /**\n * Check whether the heap 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 elements.\n * @remarks Time O(1), Space O(1)\n * @returns void\n */\n\n clear(): void {\n this._elements = [];\n }\n\n /**\n * Replace the backing array and rebuild the heap.\n * @remarks Time O(N), Space O(N)\n * @param elements - Iterable used to refill the heap.\n * @returns Array of per-node results from fixing steps.\n */\n\n refill(elements: Iterable): boolean[] {\n this._elements = Array.from(elements);\n return this.fix();\n }\n\n /**\n * Check if an equal element exists in the heap.\n * @remarks Time O(N), Space O(1)\n * @param element - Element to search for.\n * @returns True if found.\n */\n\n override has(element: E): boolean {\n for (const el of this.elements) if (this._equals(el, element)) return true;\n return false;\n }\n\n /**\n * Delete one occurrence of an element.\n * @remarks Time O(N), Space O(1)\n * @param element - Element to delete.\n * @returns True if an element was removed.\n */\n\n delete(element: E): boolean {\n let index = -1;\n for (let i = 0; i < this.elements.length; i++) {\n if (this._equals(this.elements[i], element)) {\n index = i;\n break;\n }\n }\n if (index < 0) return false;\n if (index === 0) {\n this.poll();\n } else if (index === this.elements.length - 1) {\n this.elements.pop();\n } else {\n this.elements.splice(index, 1, this.elements.pop()!);\n this._bubbleUp(index);\n this._sinkDown(index, this.elements.length >> 1);\n }\n return true;\n }\n\n /**\n * Delete the first element that matches a predicate.\n * @remarks Time O(N), Space O(1)\n * @param predicate - Function (element, index, heap) → boolean.\n * @returns True if an element was removed.\n */\n\n deleteBy(predicate: (element: E, index: number, heap: this) => boolean): boolean {\n let idx = -1;\n for (let i = 0; i < this.elements.length; i++) {\n if (predicate(this.elements[i], i, this)) {\n idx = i;\n break;\n }\n }\n if (idx < 0) return false;\n if (idx === 0) {\n this.poll();\n } else if (idx === this.elements.length - 1) {\n this.elements.pop();\n } else {\n this.elements.splice(idx, 1, this.elements.pop()!);\n this._bubbleUp(idx);\n this._sinkDown(idx, this.elements.length >> 1);\n }\n return true;\n }\n\n /**\n * Set the equality comparator used by has/delete operations.\n * @remarks Time O(1), Space O(1)\n * @param equals - Equality predicate (a, b) → boolean.\n * @returns This heap.\n */\n\n setEquality(equals: (a: E, b: E) => boolean): this {\n this._equals = equals;\n return this;\n }\n\n /**\n * Traverse the binary heap as a complete binary tree and collect elements.\n * @remarks Time O(N), Space O(H)\n * @param [order] - Traversal order: 'PRE' | 'IN' | 'POST'.\n * @returns Array of visited elements.\n */\n\n dfs(order: DFSOrderPattern = 'PRE'): E[] {\n const result: E[] = [];\n const _dfs = (index: number) => {\n const left = 2 * index + 1,\n right = left + 1;\n if (index < this.size) {\n if (order === 'IN') {\n _dfs(left);\n result.push(this.elements[index]);\n _dfs(right);\n } else if (order === 'PRE') {\n result.push(this.elements[index]);\n _dfs(left);\n _dfs(right);\n } else if (order === 'POST') {\n _dfs(left);\n _dfs(right);\n result.push(this.elements[index]);\n }\n }\n };\n _dfs(0);\n return result;\n }\n\n /**\n * Restore heap order bottom-up (heapify in-place).\n * @remarks Time O(N), Space O(1)\n * @returns Array of per-node results from fixing steps.\n */\n\n fix(): boolean[] {\n const results: boolean[] = [];\n for (let i = Math.floor(this.size / 2) - 1; i >= 0; i--) {\n results.push(this._sinkDown(i, this.elements.length >> 1));\n }\n return results;\n }\n\n /**\n * Return all elements in ascending order by repeatedly polling.\n * @remarks Time O(N log N), Space O(N)\n * @returns Sorted array of elements.\n */\n\n sort(): E[] {\n const visited: E[] = [];\n const cloned = this._createInstance();\n for (const x of this.elements) cloned.add(x);\n while (!cloned.isEmpty()) {\n const top = cloned.poll();\n if (top !== undefined) visited.push(top);\n }\n return visited;\n }\n\n /**\n * Deep clone this heap.\n * @remarks Time O(N), Space O(N)\n * @returns A new heap with the same elements.\n */\n\n clone(): this {\n const next = this._createInstance();\n for (const x of this.elements) next.add(x);\n return next;\n }\n\n /**\n * Filter elements into a new heap of the same class.\n * @remarks Time O(N log N), Space O(N)\n * @param callback - Predicate (element, index, heap) → boolean to keep element.\n * @param [thisArg] - Value for `this` inside the callback.\n * @returns A new heap with the kept elements.\n */\n\n filter(callback: ElementCallback, thisArg?: unknown): this {\n const out = this._createInstance();\n let i = 0;\n for (const x of this) {\n if (thisArg === undefined ? callback(x, i++, this) : callback.call(thisArg, x, i++, this)) {\n out.add(x);\n } else {\n i++;\n }\n }\n return out;\n }\n\n /**\n * Map elements into a new heap of possibly different element type.\n * @remarks Time O(N log N), Space O(N)\n * @template EM\n * @template RM\n * @param callback - Mapping function (element, index, heap) → newElement.\n * @param options - Options for the output heap, including comparator for EM.\n * @param [thisArg] - Value for `this` inside the callback.\n * @returns A new heap with mapped elements.\n */\n\n map(\n callback: ElementCallback,\n options: HeapOptions & { comparator: Comparator },\n thisArg?: unknown\n ): Heap {\n const { comparator, toElementFn, ...rest } = options ?? {};\n if (!comparator) throw new TypeError('Heap.map requires options.comparator for EM');\n const out = this._createLike([], { ...rest, comparator, toElementFn });\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 out.add(v);\n }\n return out;\n }\n\n /**\n * Map elements into a new heap of the same element type.\n * @remarks Time O(N log N), Space O(N)\n * @param callback - Mapping function (element, index, heap) → element.\n * @param [thisArg] - Value for `this` inside the callback.\n * @returns A new heap with mapped elements.\n */\n\n mapSame(callback: ElementCallback, thisArg?: unknown): this {\n const out = this._createInstance();\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 out.add(v);\n }\n return out;\n }\n\n protected _DEFAULT_COMPARATOR = (a: E, b: E): number => {\n if (typeof a === 'object' || typeof b === 'object') {\n throw TypeError('When comparing object types, define a custom comparator in options.');\n }\n if ((a as unknown as number) > (b as unknown as number)) return 1;\n if ((a as unknown as number) < (b as unknown as number)) return -1;\n return 0;\n };\n\n protected _comparator: Comparator = this._DEFAULT_COMPARATOR; /**\n * Get the comparator used to order elements.\n * @remarks Time O(1), Space O(1)\n * @returns Comparator function.\n */\n /**\n * Get the comparator used to order elements.\n * @remarks Time O(1), Space O(1)\n * @returns Comparator function.\n */\n\n get comparator() {\n return this._comparator;\n }\n\n protected *_getIterator(): IterableIterator {\n for (const element of this.elements) yield element;\n }\n\n protected _bubbleUp(index: number): boolean {\n const element = this.elements[index];\n while (index > 0) {\n const parent = (index - 1) >> 1;\n const parentItem = this.elements[parent];\n if (this.comparator(parentItem, element) <= 0) break;\n this.elements[index] = parentItem;\n index = parent;\n }\n this.elements[index] = element;\n return true;\n }\n\n protected _sinkDown(index: number, halfLength: number): boolean {\n const element = this.elements[index];\n while (index < halfLength) {\n let left = (index << 1) | 1;\n const right = left + 1;\n let minItem = this.elements[left];\n if (right < this.elements.length && this.comparator(minItem, this.elements[right]) > 0) {\n left = right;\n minItem = this.elements[right];\n }\n if (this.comparator(minItem, element) >= 0) break;\n this.elements[index] = minItem;\n index = left;\n }\n this.elements[index] = element;\n return true;\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 to override comparator or toElementFn.\n * @returns A like-kind empty heap instance.\n */\n\n protected _createInstance(options?: HeapOptions): this {\n const Ctor: any = this.constructor;\n const next: any = new Ctor([], { comparator: this.comparator, toElementFn: this.toElementFn, ...(options ?? {}) });\n return next as this;\n }\n\n /**\n * (Protected) Create a like-kind instance seeded by elements.\n * @remarks Time O(N log N), Space O(N)\n * @template EM\n * @template RM\n * @param [elements] - Iterable of elements or raw values to seed.\n * @param [options] - Options forwarded to the constructor.\n * @returns A like-kind heap instance.\n */\n\n protected _createLike(\n elements: Iterable | Iterable = [],\n options?: HeapOptions\n ): Heap {\n const Ctor: any = this.constructor;\n return new Ctor(elements, options) as Heap;\n }\n\n /**\n * (Protected) Spawn an empty like-kind heap instance.\n * @remarks Time O(1), Space O(1)\n * @template EM\n * @template RM\n * @param [options] - Options forwarded to the constructor.\n * @returns An empty like-kind heap instance.\n */\n\n protected _spawnLike(options?: HeapOptions): Heap {\n return this._createLike([], options);\n }\n}\n\n/**\n * Node container used by FibonacciHeap.\n * @remarks Time O(1), Space O(1)\n * @template E\n */\nexport class FibonacciHeapNode {\n element: E;\n degree: number;\n left?: FibonacciHeapNode;\n right?: FibonacciHeapNode;\n child?: FibonacciHeapNode;\n parent?: FibonacciHeapNode;\n marked: boolean;\n\n constructor(element: E, degree = 0) {\n this.element = element;\n this.degree = degree;\n this.marked = false;\n }\n}\n\n/**\n * Fibonacci heap (min-heap) optimized for fast merges and amortized operations.\n * @remarks Time O(1), Space O(1)\n * @template E\n * @example examples will be generated by unit test\n */\nexport class FibonacciHeap {\n /**\n * Create a FibonacciHeap.\n * @remarks Time O(1), Space O(1)\n * @param [comparator] - Comparator to order elements (min-heap by default).\n * @returns New FibonacciHeap instance.\n */\n\n constructor(comparator?: Comparator) {\n this.clear();\n this._comparator = comparator || this._defaultComparator;\n if (typeof this.comparator !== 'function') throw new Error('FibonacciHeap: comparator must be a function.');\n }\n\n protected _root?: FibonacciHeapNode;\n\n /**\n * Get the circular root list head.\n * @remarks Time O(1), Space O(1)\n * @returns Root node or undefined.\n */\n\n get root(): FibonacciHeapNode | undefined {\n return this._root;\n }\n\n protected _size = 0;\n get size(): number {\n return this._size;\n }\n\n protected _min?: FibonacciHeapNode;\n\n /**\n * Get the current minimum node.\n * @remarks Time O(1), Space O(1)\n * @returns Min node or undefined.\n */\n\n get min(): FibonacciHeapNode | undefined {\n return this._min;\n }\n\n protected _comparator: Comparator;\n get comparator(): Comparator {\n return this._comparator;\n }\n\n clear(): void {\n this._root = undefined;\n this._min = undefined;\n this._size = 0;\n }\n\n add(element: E): boolean {\n this.push(element);\n return true;\n }\n\n /**\n * Push an element into the root list.\n * @remarks Time O(1) amortized, Space O(1)\n * @param element - Element to insert.\n * @returns This heap.\n */\n\n push(element: E): this {\n const node = this.createNode(element);\n node.left = node;\n node.right = node;\n this.mergeWithRoot(node);\n if (!this.min || this.comparator(node.element, this.min.element) <= 0) this._min = node;\n this._size++;\n return this;\n }\n\n peek(): E | undefined {\n return this.min ? this.min.element : undefined;\n }\n\n /**\n * Collect nodes from a circular doubly linked list starting at head.\n * @remarks Time O(K), Space O(K)\n * @param [head] - Start node of the circular list.\n * @returns Array of nodes from the list.\n */\n\n consumeLinkedList(head?: FibonacciHeapNode): FibonacciHeapNode[] {\n const elements: FibonacciHeapNode[] = [];\n if (!head) return elements;\n let node: FibonacciHeapNode | undefined = head;\n let started = false;\n while (true) {\n if (node === head && started) break;\n else if (node === head) started = true;\n elements.push(node!);\n node = node!.right;\n }\n return elements;\n }\n\n /**\n * Insert a node into a parent's child list (circular).\n * @remarks Time O(1), Space O(1)\n * @param parent - Parent node.\n * @param node - Child node to insert.\n * @returns void\n */\n\n mergeWithChild(parent: FibonacciHeapNode, node: FibonacciHeapNode): void {\n if (!parent.child) parent.child = node;\n else {\n node.right = parent.child.right;\n node.left = parent.child;\n parent.child.right!.left = node;\n parent.child.right = node;\n }\n }\n\n poll(): E | undefined {\n return this.pop();\n }\n\n /**\n * Remove and return the minimum element, consolidating the root list.\n * @remarks Time O(log N) amortized, Space O(1)\n * @returns Minimum element or undefined.\n */\n\n pop(): E | undefined {\n if (this._size === 0) return undefined;\n const z = this.min!;\n if (z.child) {\n const elements = this.consumeLinkedList(z.child);\n for (const node of elements) {\n this.mergeWithRoot(node);\n node.parent = undefined;\n }\n }\n this.removeFromRoot(z);\n if (z === z.right) {\n this._min = undefined;\n this._root = undefined;\n } else {\n this._min = z.right;\n this._consolidate();\n }\n this._size--;\n return z.element;\n }\n\n /**\n * Meld another heap into this heap.\n * @remarks Time O(1), Space O(1)\n * @param heapToMerge - Another FibonacciHeap to meld into this one.\n * @returns void\n */\n\n merge(heapToMerge: FibonacciHeap): void {\n if (heapToMerge.size === 0) return;\n if (this.root && heapToMerge.root) {\n const thisRoot = this.root,\n otherRoot = heapToMerge.root;\n const thisRootRight = thisRoot.right!,\n otherRootLeft = otherRoot.left!;\n thisRoot.right = otherRoot;\n otherRoot.left = thisRoot;\n thisRootRight.left = otherRootLeft;\n otherRootLeft.right = thisRootRight;\n } else if (!this.root && heapToMerge.root) {\n this._root = heapToMerge.root;\n }\n if (!this.min || (heapToMerge.min && this.comparator(heapToMerge.min.element, this.min.element) < 0)) {\n this._min = heapToMerge.min;\n }\n this._size += heapToMerge.size;\n heapToMerge.clear();\n }\n\n createNode(element: E): FibonacciHeapNode {\n return new FibonacciHeapNode(element);\n }\n\n isEmpty(): boolean {\n return this._size === 0;\n }\n\n protected _defaultComparator(a: E, b: E): number {\n if (a < b) return -1;\n if (a > b) return 1;\n return 0;\n }\n\n protected mergeWithRoot(node: FibonacciHeapNode): void {\n if (!this.root) this._root = node;\n else {\n node.right = this.root.right;\n node.left = this.root;\n this.root.right!.left = node;\n this.root.right = node;\n }\n }\n\n protected removeFromRoot(node: FibonacciHeapNode): void {\n if (this.root === node) this._root = node.right;\n if (node.left) node.left.right = node.right;\n if (node.right) node.right.left = node.left;\n }\n\n protected _link(y: FibonacciHeapNode, x: FibonacciHeapNode): void {\n this.removeFromRoot(y);\n y.left = y;\n y.right = y;\n this.mergeWithChild(x, y);\n x.degree++;\n y.parent = x;\n }\n\n protected _consolidate(): void {\n const A: (FibonacciHeapNode | undefined)[] = new Array(this._size);\n const elements = this.consumeLinkedList(this.root);\n let x: FibonacciHeapNode | undefined,\n y: FibonacciHeapNode | undefined,\n d: number,\n t: FibonacciHeapNode | undefined;\n\n for (const node of elements) {\n x = node;\n d = x.degree;\n while (A[d]) {\n y = A[d] as FibonacciHeapNode;\n if (this.comparator(x.element, y.element) > 0) {\n t = x;\n x = y;\n y = t;\n }\n this._link(y, x);\n A[d] = undefined;\n d++;\n }\n A[d] = x;\n }\n\n for (let i = 0; i < A.length; i++) {\n if (A[i] && (!this.min || this.comparator(A[i]!.element, this.min.element) <= 0)) this._min = A[i]!;\n }\n }\n}\n","/**\n * data-structure-typed\n *\n * @author Kirk Qi\n * @copyright Copyright (c) 2022 Kirk Qi \n * @license MIT License\n */\n\nimport type { PriorityQueueOptions } from '../../types';\nimport { Heap } from '../heap';\n\n/**\n * @example\n */\nexport class PriorityQueue extends Heap {\n constructor(elements: Iterable | Iterable = [], options?: PriorityQueueOptions) {\n super(elements, options);\n }\n}\n","/**\n * data-structure-typed\n *\n * @author Kirk Qi\n * @copyright Copyright (c) 2022 Kirk Qi \n * @license MIT License\n */\nimport type { PriorityQueueOptions } from '../../types';\nimport { PriorityQueue } from './priority-queue';\n\n/**\n * Min-oriented priority queue (min-heap) built on {@link PriorityQueue}.\n * The queue removes the smallest element first under the provided comparator.\n * Provide a custom comparator if you store non-primitive objects.\n * @template E Element type stored in the queue.\n * @template R Extra record/metadata associated with each element.\n * @example\n */\nexport class MinPriorityQueue extends PriorityQueue {\n /**\n * Creates a min-priority queue.\n * @param elements Optional initial elements to insert.\n * @param options Optional configuration (e.g., `comparator`, `toElementFn`).\n * @remarks Complexity — Time: O(n log n) when inserting n elements incrementally; Space: O(n).\n */\n constructor(elements: Iterable | Iterable = [], options?: PriorityQueueOptions) {\n super(elements, options);\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"]}