{"version":3,"sources":["jsdelivr-header.js","/npm/doublearray@0.0.2/doublearray.js"],"names":[],"mappings":"AAAA;AACA;AACA;AACA;AACA;AACA;AACA,CCJA,WAEI,aAEA,IAGI,GAAa,EACb,GAAc,EACd,GAAe,EAMf,EAAQ,SAAU,GAEE,MAAhB,IACA,EAAe,MAGnB,IAAI,EAAW,SAAU,EAAO,EAAO,GACnC,IAAK,IAAI,EAAI,EAAO,EAAI,EAAK,IACzB,EAAM,GAAW,EAAJ,EAEjB,GAAI,EAAI,EAAM,MAAM,EAAM,MAAM,OAAS,GAAI,CAEzC,IADA,IAAI,EAAe,EAAM,MAAM,OAAS,EACjC,EAAI,EAAM,MAAM,IACnB,IAEJ,EAAM,IAAW,CACrB,CACJ,EAEI,EAAY,SAAU,EAAQ,EAAO,GACrC,IAAK,IAAI,EAAI,EAAO,EAAI,EAAK,IACzB,EAAO,IAAO,EAAI,CAE1B,EAEI,EAAU,SAAU,GAEpB,IAAI,EA9Bc,EA8BH,EAGX,EAAiB,EAAe,EAAK,OAAQ,EAAK,MAAO,GAC7D,EAAS,EAAgB,EAAK,MAAM,OAAQ,GAC5C,EAAe,IAAI,EAAK,OACxB,EAAK,MAAQ,KACb,EAAK,MAAQ,EAEb,IAAI,EAAkB,EAAe,EAAM,OAAQ,EAAM,MAAO,GAChE,EAAU,EAAiB,EAAM,MAAM,OAAQ,GAC/C,EAAgB,IAAI,EAAM,OAC1B,EAAM,MAAQ,KACd,EAAM,MAAQ,CAClB,EAEI,EAAoB,EAEpB,EAAO,CACP,OAAQ,EACR,MApDS,EAqDT,MAAO,EAAe,EArDb,EAqDsC,IAG/C,EAAQ,CACR,OAAQ,EACR,MAzDU,EA0DV,MAAO,EAAe,EA1DZ,EA0DuC,IAarD,OATA,EAAK,MAnEK,GAmEY,EACtB,EAAM,MApEI,KAuEV,EAAS,EAAK,MAAO,EAAa,EAAK,MAAM,QAG7C,EAAU,EAAM,MAAO,EAAa,EAAM,MAAM,QAEzC,CACH,cAAe,WACX,OAAO,EAAK,KAChB,EACA,eAAgB,WACZ,OAAO,EAAM,KACjB,EACA,eAAgB,SAAU,GAEtB,OADA,EAAK,MAAQ,EACN,IACX,EACA,gBAAiB,SAAU,GAEvB,OADA,EAAM,MAAQ,EACP,IACX,EACA,KAAM,WACF,OAAO,KAAK,IAAI,EAAK,MAAM,OAAQ,EAAM,MAAM,OACnD,EACA,QAAS,SAAU,GACf,OAAI,EAAK,MAAM,OAAS,EAAI,EACP,EAAR,EAON,EAAK,MAAM,EACtB,EACA,SAAU,SAAU,GAChB,OAAI,EAAM,MAAM,OAAS,EAAI,GAChB,EAAQ,EAOd,EAAM,MAAM,EACvB,EACA,QAAS,SAAU,EAAO,GAClB,EAAK,MAAM,OAAS,EAAI,GACxB,EAAQ,GAEZ,EAAK,MAAM,GAAS,CACxB,EACA,SAAU,SAAU,EAAO,GACnB,EAAM,MAAM,OAAS,EAAI,GACzB,EAAQ,GAEZ,EAAM,MAAM,GAAS,CACzB,EACA,mBAAoB,SAAU,GAI1B,EAAoB,CACxB,EACA,mBAAoB,WAIhB,OAAO,CACX,EACA,OAAQ,WAEJ,IADA,IAAI,EAAa,KAAK,OAAS,IAEvB,GAAK,EAAM,MAAM,KAGrB,IAEJ,EAAK,MAAQ,EAAK,MAAM,SAAS,EAAG,EAAa,GACjD,EAAM,MAAQ,EAAM,MAAM,SAAS,EAAG,EAAa,EACvD,EACA,KAAM,WAGF,IAFA,IAAI,EAAe,EACf,EAAO,EAAM,MAAM,OACd,EAAI,EAAG,EAAI,EAAM,IAClB,EAAM,MAAM,GAAK,GACjB,IAGR,MAAO,CACH,IAAK,EACL,OAAQ,EACR,YAAa,EAAO,GAAgB,EAE5C,EACA,KAAM,WAEF,IAGI,EAHA,EAAY,GACZ,EAAa,GAGjB,IAAK,EAAI,EAAG,EAAI,EAAK,MAAM,OAAQ,IAC/B,EAAY,EAAY,IAAM,KAAK,QAAQ,GAE/C,IAAK,EAAI,EAAG,EAAI,EAAM,MAAM,OAAQ,IAChC,EAAa,EAAa,IAAM,KAAK,SAAS,GAMlD,OAHA,QAAQ,IAAI,QAAU,GACtB,QAAQ,IAAI,QAAU,GAEf,QAAU,EAAY,SAAW,CAC5C,EAER,EAMA,SAAS,EAAmB,GACxB,KAAK,GAAK,EAAM,GAChB,KAAK,KAAO,EAChB,CAwQA,SAAS,EAAY,GACjB,KAAK,GAAK,EACV,KAAK,GAAG,QACZ,CAjQA,EAAmB,UAAU,OAAS,SAAU,EAAK,GAEjD,OADA,KAAK,KAAK,KAAK,CAAE,EAAG,EAAK,EAAG,IACrB,IACX,EASA,EAAmB,UAAU,MAAQ,SAAU,EAAM,GAMjD,GAJY,MAAR,IACA,EAAO,KAAK,MAGJ,MAAR,EACA,OAAO,IAAI,EAAY,KAAK,IAGlB,MAAV,IACA,GAAS,GAIb,IAAI,EACA,EAAK,KAAI,SAAU,GACf,MAAO,CACH,EAAG,EAAkB,EAAE,EA3OvB,MA4OA,EAAG,EAAE,EAEb,IAwBJ,OApBI,KAAK,KADL,EACY,EAGR,EAAU,MAAK,SAAU,EAAI,GAIzB,IAHA,IAAI,EAAK,EAAG,EACR,EAAK,EAAG,EACR,EAAa,KAAK,IAAI,EAAG,OAAQ,EAAG,QAC/B,EAAM,EAAG,EAAM,EAAY,IAChC,GAAI,EAAG,KAAS,EAAG,GAGnB,OAAO,EAAG,GAAO,EAAG,GAExB,OAAO,EAAG,OAAS,EAAG,MAC1B,IAGR,EAAY,KAEZ,KAAK,OAnQK,EAmQW,EAAG,EAAG,KAAK,KAAK,QAC9B,IAAI,EAAY,KAAK,GAChC,EAKA,EAAmB,UAAU,OAAS,SAAU,EAAc,EAAU,EAAO,GAE3E,IAAI,EAAgB,KAAK,gBAAgB,EAAU,EAAO,GACtD,EAAQ,KAAK,oBAAoB,GAErC,KAAK,MAAM,EAAc,EAAe,GAExC,IAAK,IAAI,EAAI,EAAG,EAAI,EAAc,OAAQ,GAAQ,EAAG,CACjD,IAAI,EAAa,EAAc,GAC/B,GApRQ,IAoRJ,EAAJ,CAGA,IAAI,EAAc,EAAc,EAAI,GAChC,EAAY,EAAc,EAAI,GAC9B,EAAc,EAAQ,EAC1B,KAAK,OAAO,EAAa,EAAW,EAAG,EAAa,EAJpD,CAKJ,CACJ,EAEA,EAAmB,UAAU,gBAAkB,SAAU,EAAU,EAAO,GACtE,IAAI,EAAe,KAAK,KAAK,GAAO,EAAE,GAClC,EAAI,EACJ,EAAgB,IAAI,WAAoB,EAAT,GAEnC,EAAc,KAAO,EACrB,EAAc,KAAO,EAIrB,IAFA,IAAI,EAAW,EACX,EAAY,EACT,EAAW,EAAQ,EAAQ,IAAY,CAC1C,IAAI,EAAY,KAAK,KAAK,GAAU,EAAE,GAClC,IAAiB,IACjB,EAAc,KAAO,EAAW,EAEhC,EAAc,KAAO,EACrB,EAAc,KAAO,EACrB,EAAe,EACf,EAAY,EAEpB,CAIA,OAHA,EAAc,KAAO,EAAW,EAChC,EAAgB,EAAc,SAAS,EAAG,EAG9C,EAEA,EAAmB,UAAU,MAAQ,SAAU,EAAW,EAAe,GAErE,IAII,EAJA,EAAK,KAAK,GAKd,IAHA,EAAG,QAAQ,EAAW,GAGjB,EAAI,EAAG,EAAI,EAAc,OAAQ,GAAQ,EAAG,CAC7C,IAAI,EAAO,EAAc,GACrB,EAAW,EAAQ,EASnB,GAAmB,EAAG,QAAQ,GAC9B,GAAmB,EAAG,SAAS,GAO/B,IAAa,EAAG,qBAChB,EAAG,SAAS,GAAkB,GAG9B,EAAG,mBAAmB,GAE1B,EAAG,QAAQ,GAAkB,GAE7B,IAAI,EAAQ,EAIZ,GAHA,EAAG,SAAS,EAAU,GA5Vd,IA+VJ,EAAoB,CACpB,IAAI,EAAY,EAAc,EAAI,GAK9B,EAAQ,KAAK,KAAK,GAAW,EAEpB,MAAT,IACA,EAAQ,GAGZ,IAAI,GAAS,EAAQ,EACrB,EAAG,QAAQ,EAAU,EACzB,CACJ,CACJ,EAMA,EAAmB,UAAU,oBAAsB,SAAU,GAoBzD,IAlBA,IAYI,EAZA,EAAK,KAAK,GAaV,EAAO,EAAG,uBAQV,IAFA,EAAQ,EAAO,EAAc,IAEjB,EACR,GAAS,EAAG,SAAS,OADzB,CAWA,IADA,IAAI,GAAmB,EACd,EAAI,EAAG,EAAI,EAAc,OAAQ,GAAQ,EAAG,CACjD,IACI,EAAe,EADR,EAAc,GAGzB,IAAK,KAAK,aAAa,GAAe,CAGlC,GAAS,EAAG,SAAS,GAKrB,GAAmB,EACnB,KACJ,CACJ,CACA,GAAI,EAEA,OAAO,CArBX,CAwBR,EAKA,EAAmB,UAAU,aAAe,SAAU,GAClD,IACI,EADK,KAAK,GACC,SAAS,GAMxB,OAxbU,IAwbN,GAIA,EAAQ,CAOhB,EAkBA,EAAY,UAAU,QAAU,SAAU,GAUtC,IARA,IAAI,EAAK,KAAK,GAGV,EAAS,EADb,GA3dY,MA8dR,EA5dM,EA6dN,EAAQ,EAEH,EAAI,EAAG,EAAI,EAAO,OAAQ,IAAK,CACpC,IAAI,EAAO,EAAO,GAGlB,IADA,EAAQ,KAAK,SAAS,EAAQ,MAChB,EACV,OAAO,EAGX,GAAI,EAAG,QAAQ,IAAU,EAErB,OAAO,EAGP,EAAS,CAGjB,CACA,OAAO,CACX,EASA,EAAY,UAAU,OAAS,SAAU,GAQrC,IALA,IAAI,EAAS,EADb,GA9fY,MAigBR,EA/fM,EAggBN,EAAQ,EAEH,EAAI,EAAG,EAAI,EAAO,OAAQ,IAAK,CACpC,IAAI,EAAO,EAAO,GAElB,IADA,EAAQ,KAAK,SAAS,EAAQ,MAChB,EACV,OAAO,EAEX,EAAS,CACb,CAEA,IAAI,EAAO,KAAK,GAAG,QAAQ,GAC3B,OAAI,GAAQ,GAEC,EAAO,EAGT,CAEf,EAUA,EAAY,UAAU,mBAAqB,SAAU,GASjD,IAPA,IAAI,EAAS,EAAkB,GAE3B,EAjiBM,EAkiBN,EAAQ,EAER,EAAS,GAEJ,EAAI,EAAG,EAAI,EAAO,OAAQ,IAAK,CACpC,IAAI,EAAO,EAAO,GAIlB,IAFA,EAAQ,KAAK,SAAS,EAAQ,MAEhB,EAuBV,MAtBA,EAAS,EAGT,IAAI,EAAc,KAAK,SAAS,EAhjB5B,GAkjBJ,GAAI,IAAgB,EAAW,CAC3B,IAAI,EAAO,KAAK,GAAG,QAAQ,GAEvB,EAAI,CAAC,EAEL,GAAQ,IAER,EAAE,GAAM,EAAO,GAInB,EAAE,EAAI,EAAkB,EAAU,EAAQ,EAAG,EAAI,IAEjD,EAAO,KAAK,EAChB,CAKR,CAEA,OAAO,CACX,EAEA,EAAY,UAAU,SAAW,SAAU,EAAQ,GAC/C,IAAI,EAAQ,KAAK,GAAG,QAAQ,GAAU,EACtC,OAAI,KAAK,GAAG,SAAS,KAAW,EACrB,EAEA,CAEf,EAEA,EAAY,UAAU,KAAO,WACzB,OAAO,KAAK,GAAG,MACnB,EAEA,EAAY,UAAU,KAAO,WACzB,OAAO,KAAK,GAAG,MACnB,EAEA,EAAY,UAAU,KAAO,WACzB,OAAO,KAAK,GAAG,MACnB,EAKA,IAAI,EAAiB,SAAU,EAAQ,EAAO,GAC1C,GAAI,EACA,OAAO,GACH,KAAK,EACL,OAAO,IAAI,UAAU,GACrB,KAAK,EACL,OAAO,IAAI,WAAW,GACtB,KAAK,EACL,OAAO,IAAI,WAAW,GACtB,QACA,MAAM,IAAI,WAAW,4CAA8C,QAGvE,OAAO,GACH,KAAK,EACL,OAAO,IAAI,WAAW,GACtB,KAAK,EACL,OAAO,IAAI,YAAY,GACvB,KAAK,EACL,OAAO,IAAI,YAAY,GACvB,QACA,MAAM,IAAI,WAAW,4CAA8C,GAG/E,EAEI,EAAY,SAAU,EAAK,EAAY,GACvC,IAAI,EAAS,IAAI,YAAY,GACzB,EAAQ,IAAI,WAAW,EAAQ,EAAG,GAClC,EAAQ,EAAI,SAAS,EAAY,GAErC,OADA,EAAM,IAAI,GACH,CACX,EASI,EAAoB,SAAU,GAO9B,IAJA,IAAI,EAAQ,IAAI,WAAW,IAAI,YAAyB,EAAb,EAAI,SAE3C,EAAI,EAAG,EAAI,EAER,EAAI,EAAI,QAAQ,CACnB,IAAI,EAEA,EAAa,EAAI,WAAW,KAChC,GAAI,GAAc,OAAU,GAAc,MAAQ,CAE9C,IAAI,EAAQ,EACR,EAAQ,EAAI,WAAW,KAE3B,KAAI,GAAS,OAAU,GAAS,OAM5B,OAAO,KALP,EACuB,MAAlB,EAAQ,OAAsB,OAC9B,EAAQ,MAKrB,MAEI,EAAe,EAGf,EAAe,IAEf,EAAM,KAAO,EAEN,EAAe,MAEtB,EAAM,KAAQ,IAAiB,EAAK,IACpC,EAAM,KAAuB,GAAf,EAAuB,KAE9B,EAAe,OAEtB,EAAM,KAAQ,IAAiB,GAAM,IACrC,EAAM,KAAS,GAAgB,EAAK,GAAQ,IAC5C,EAAM,KAAuB,GAAf,EAAuB,KAE9B,EAAgB,GAAK,KAE5B,EAAM,KAAQ,IAAiB,GAAM,IACrC,EAAM,KAAS,GAAgB,GAAM,GAAQ,IAC7C,EAAM,KAAS,GAAgB,EAAK,GAAQ,IAC5C,EAAM,KAAuB,GAAf,EAAuB,IAK7C,CAEA,OAAO,EAAM,SAAS,EAAG,EAC7B,EASI,EAAoB,SAAU,GAM9B,IAJA,IACI,EAAM,EAAgB,EAAO,EAD7B,EAAM,GAEN,EAAI,EAED,EAAI,EAAM,SAMT,GAJJ,EAAK,EAAM,MAEF,IAEE,EACC,GAAM,GAAO,GAGP,GAAL,IAAc,EAAW,GAD7B,EAAM,KAEH,GAAM,GAAO,IAIP,GAAL,IAAc,IAAa,GAF/B,EAAM,OAEkC,EAAW,GADnD,EAAM,MAOG,EAAL,IAAc,IAAa,GAH/B,EAAM,OAGkC,IAAa,GAFrD,EAAM,OAEwD,EAAW,GADzE,EAAM,MAIJ,MACV,GAAO,OAAO,aAAa,IAI3B,EAAS,OADT,GAAQ,QACmB,GAC3B,EAAS,MAAiB,KAAP,EACnB,GAAO,OAAO,aAAa,EAAO,IAIvC,OAAO,CACX,EAII,EAAc,CACd,QAAS,SAAU,GACf,OAAO,IAAI,EAAmB,EAClC,EACA,KAAM,SAAU,EAAa,GACzB,IAAI,EAAK,EAAM,GAGf,OAFA,EAAG,eAAe,GAClB,EAAG,gBAAgB,GACZ,IAAI,EAAY,EAC3B,GAGA,oBAAuB,OAEvB,OAAO,YAAc,EAGrB,OAAO,QAAU,CAGxB,CApxBD","file":"/npm/doublearray@0.0.2/doublearray.js","sourceRoot":"","sourcesContent":["/**\n * Minified by jsDelivr using Terser v5.39.0.\n * Original file: /npm/doublearray@0.0.2/doublearray.js\n *\n * Do NOT use SRI with dynamically generated files! More information: https://www.jsdelivr.com/using-sri-with-dynamic-files\n */\n","// Copyright (c) 2014 Takuya Asano All Rights Reserved.\n\n(function () {\n\n    \"use strict\";\n\n    var TERM_CHAR = \"\\u0000\", // terminal character\n        TERM_CODE = 0,        // terminal character code\n        ROOT_ID = 0,          // index of root node\n        NOT_FOUND = -1,       // traverse() returns if no nodes found\n        BASE_SIGNED = true,\n        CHECK_SIGNED = true,\n        BASE_BYTES = 4,\n        CHECK_BYTES = 4,\n        MEMORY_EXPAND_RATIO = 2;\n\n\n    var newBC = function (initial_size) {\n\n        if (initial_size == null) {\n            initial_size = 1024;\n        }\n\n        var initBase = function (_base, start, end) {  // 'end' index does not include\n            for (var i = start; i < end; i++) {\n                _base[i] = - i + 1;  // inversed previous empty node index\n            }\n            if (0 < check.array[check.array.length - 1]) {\n                var last_used_id = check.array.length - 2;\n                while (0 < check.array[last_used_id]) {\n                    last_used_id--;\n                }\n                _base[start] = - last_used_id;\n            }\n        };\n\n        var initCheck = function (_check, start, end) {\n            for (var i = start; i < end; i++) {\n                _check[i] = - i - 1;  // inversed next empty node index\n            }\n        };\n\n        var realloc = function (min_size) {\n            // expand arrays size by given ratio\n            var new_size = min_size * MEMORY_EXPAND_RATIO;\n            // console.log('re-allocate memory to ' + new_size);\n\n            var base_new_array = newArrayBuffer(base.signed, base.bytes, new_size);\n            initBase(base_new_array, base.array.length, new_size);  // init BASE in new range\n            base_new_array.set(base.array);\n            base.array = null;  // explicit GC\n            base.array = base_new_array;\n\n            var check_new_array = newArrayBuffer(check.signed, check.bytes, new_size);\n            initCheck(check_new_array, check.array.length, new_size);  // init CHECK in new range\n            check_new_array.set(check.array);\n            check.array = null;  // explicit GC\n            check.array = check_new_array;\n        };\n\n        var first_unused_node = ROOT_ID + 1;\n\n        var base = {\n            signed: BASE_SIGNED,\n            bytes: BASE_BYTES,\n            array: newArrayBuffer(BASE_SIGNED, BASE_BYTES, initial_size)\n        };\n\n        var check = {\n            signed: CHECK_SIGNED,\n            bytes: CHECK_BYTES,\n            array: newArrayBuffer(CHECK_SIGNED, CHECK_BYTES, initial_size)\n        };\n\n        // init root node\n        base.array[ROOT_ID] = 1;\n        check.array[ROOT_ID] = ROOT_ID;\n\n        // init BASE\n        initBase(base.array, ROOT_ID + 1, base.array.length);\n\n        // init CHECK\n        initCheck(check.array, ROOT_ID + 1, check.array.length);\n\n        return {\n            getBaseBuffer: function () {\n                return base.array;\n            },\n            getCheckBuffer: function () {\n                return check.array;\n            },\n            loadBaseBuffer: function (base_buffer) {\n                base.array = base_buffer;\n                return this;\n            },\n            loadCheckBuffer: function (check_buffer) {\n                check.array = check_buffer;\n                return this;\n            },\n            size: function () {\n                return Math.max(base.array.length, check.array.length);\n            },\n            getBase: function (index) {\n                if (base.array.length - 1 < index) {\n                    return - index + 1;\n                    // realloc(index);\n                }\n                // if (!Number.isFinite(base.array[index])) {\n                //     console.log('getBase:' + index);\n                //     throw 'getBase' + index;\n                // }\n                return base.array[index];\n            },\n            getCheck: function (index) {\n                if (check.array.length - 1 < index) {\n                    return - index - 1;\n                    // realloc(index);\n                }\n                // if (!Number.isFinite(check.array[index])) {\n                //     console.log('getCheck:' + index);\n                //     throw 'getCheck' + index;\n                // }\n                return check.array[index];\n            },\n            setBase: function (index, base_value) {\n                if (base.array.length - 1 < index) {\n                    realloc(index);\n                }\n                base.array[index] = base_value;\n            },\n            setCheck: function (index, check_value) {\n                if (check.array.length - 1 < index) {\n                    realloc(index);\n                }\n                check.array[index] = check_value;\n            },\n            setFirstUnusedNode: function (index) {\n                // if (!Number.isFinite(index)) {\n                //     throw 'assertion error: setFirstUnusedNode ' + index + ' is not finite number';\n                // }\n                first_unused_node = index;\n            },\n            getFirstUnusedNode: function () {\n                // if (!Number.isFinite(first_unused_node)) {\n                //     throw 'assertion error: getFirstUnusedNode ' + first_unused_node + ' is not finite number';\n                // }\n                return first_unused_node;\n            },\n            shrink: function () {\n                var last_index = this.size() - 1;\n                while (true) {\n                    if (0 <= check.array[last_index]) {\n                        break;\n                    }\n                    last_index--;\n                }\n                base.array = base.array.subarray(0, last_index + 2);   // keep last unused node\n                check.array = check.array.subarray(0, last_index + 2); // keep last unused node\n            },\n            calc: function () {\n                var unused_count = 0;\n                var size = check.array.length;\n                for (var i = 0; i < size; i++) {\n                    if (check.array[i] < 0) {\n                        unused_count++;\n                    }\n                }\n                return {\n                    all: size,\n                    unused: unused_count,\n                    efficiency: (size - unused_count) / size\n                };\n            },\n            dump: function () {\n                // for debug\n                var dump_base = \"\";\n                var dump_check = \"\";\n\n                var i;\n                for (i = 0; i < base.array.length; i++) {\n                    dump_base = dump_base + \" \" + this.getBase(i);\n                }\n                for (i = 0; i < check.array.length; i++) {\n                    dump_check = dump_check + \" \" + this.getCheck(i);\n                }\n\n                console.log(\"base:\" + dump_base);\n                console.log(\"chck:\" + dump_check);\n\n                return \"base:\" + dump_base + \" chck:\" + dump_check;\n            }\n        };\n    };\n\n\n    /**\n     * Factory method of double array\n     */\n    function DoubleArrayBuilder(initial_size) {\n        this.bc = newBC(initial_size);  // BASE and CHECK\n        this.keys = [];\n    }\n\n\n    /**\n     * Append a key to initialize set\n     * (This method should be called by dictionary ordered key)\n     *\n     * @param {String} key\n     * @param {Number} value Integer value from 0 to max signed integer number - 1\n     */\n    DoubleArrayBuilder.prototype.append = function (key, record) {\n        this.keys.push({ k: key, v: record });\n        return this;\n    };\n\n    /**\n     * Build double array for given keys\n     *\n     * @param {Array} keys Array of keys. A key is a Object which has properties 'k', 'v'.\n     * 'k' is a key string, 'v' is a record assigned to that key.\n     * @return {DoubleArray} Compiled double array\n     */\n    DoubleArrayBuilder.prototype.build = function (keys, sorted) {\n\n        if (keys == null) {\n            keys = this.keys;\n        }\n\n        if (keys == null) {\n            return new DoubleArray(this.bc);\n        }\n\n        if (sorted == null) {\n            sorted = false;\n        }\n\n        // Convert key string to ArrayBuffer\n        var buff_keys =\n            keys.map(function (k) {\n                return {\n                    k: stringToUtf8Bytes(k.k + TERM_CHAR),\n                    v: k.v\n                };\n            });\n\n        // Sort keys by byte order\n        if (sorted) {\n            this.keys = buff_keys;\n        } else {\n            this.keys =\n                buff_keys.sort(function (k1, k2) {\n                    var b1 = k1.k;\n                    var b2 = k2.k;\n                    var min_length = Math.min(b1.length, b2.length);\n                    for (var pos = 0; pos < min_length; pos++) {\n                        if (b1[pos] === b2[pos]) {\n                            continue;\n                        }\n                        return b1[pos] - b2[pos];\n                    }\n                    return b1.length - b2.length;\n                });\n        }\n\n        buff_keys = null;  // explicit GC\n\n        this._build(ROOT_ID, 0, 0, this.keys.length);\n        return new DoubleArray(this.bc);\n    };\n\n    /**\n     * Append nodes to BASE and CHECK array recursively\n     */\n    DoubleArrayBuilder.prototype._build = function (parent_index, position, start, length) {\n\n        var children_info = this.getChildrenInfo(position, start, length);\n        var _base = this.findAllocatableBase(children_info);\n\n        this.setBC(parent_index, children_info, _base);\n\n        for (var i = 0; i < children_info.length; i = i + 3) {\n            var child_code = children_info[i];\n            if (child_code === TERM_CODE) {\n                continue;\n            }\n            var child_start = children_info[i + 1];\n            var child_len = children_info[i + 2];\n            var child_index = _base + child_code;\n            this._build(child_index, position + 1, child_start, child_len);\n        }\n    };\n\n    DoubleArrayBuilder.prototype.getChildrenInfo = function (position, start, length) {\n        var current_char = this.keys[start].k[position];\n        var i = 0;\n        var children_info = new Int32Array(length * 3);\n\n        children_info[i++] = current_char;  // char (current)\n        children_info[i++] = start;         // start index (current)\n\n        var next_pos = start;\n        var start_pos = start;\n        for (; next_pos < start + length; next_pos++) {\n            var next_char = this.keys[next_pos].k[position];\n            if (current_char !== next_char) {\n                children_info[i++] = next_pos - start_pos;  // length (current)\n\n                children_info[i++] = next_char;             // char (next)\n                children_info[i++] = next_pos;              // start index (next)\n                current_char = next_char;\n                start_pos = next_pos;\n            }\n        }\n        children_info[i++] = next_pos - start_pos;\n        children_info = children_info.subarray(0, i);\n\n        return children_info;\n    };\n\n    DoubleArrayBuilder.prototype.setBC = function (parent_id, children_info, _base) {\n\n        var bc = this.bc;\n\n        bc.setBase(parent_id, _base);  // Update BASE of parent node\n\n        var i;\n        for (i = 0; i < children_info.length; i = i + 3) {\n            var code = children_info[i];\n            var child_id = _base + code;\n\n            // Update linked list of unused nodes\n\n            // Assertion\n            // if (child_id < 0) {\n            //     throw 'assertion error: child_id is negative'\n            // }\n\n            var prev_unused_id = - bc.getBase(child_id);\n            var next_unused_id = - bc.getCheck(child_id);\n            // if (prev_unused_id < 0) {\n            //     throw 'assertion error: setBC'\n            // }\n            // if (next_unused_id < 0) {\n            //     throw 'assertion error: setBC'\n            // }\n            if (child_id !== bc.getFirstUnusedNode()) {\n                bc.setCheck(prev_unused_id, - next_unused_id);\n            } else {\n                // Update first_unused_node\n                bc.setFirstUnusedNode(next_unused_id);\n            }\n            bc.setBase(next_unused_id, - prev_unused_id);\n\n            var check = parent_id;         // CHECK is parent node index\n            bc.setCheck(child_id, check);  // Update CHECK of child node\n\n            // Update record\n            if (code === TERM_CODE) {\n                var start_pos = children_info[i + 1];\n                // var len = children_info[i + 2];\n                // if (len != 1) {\n                //     throw 'assertion error: there are multiple terminal nodes. len:' + len;\n                // }\n                var value = this.keys[start_pos].v;\n\n                if (value == null) {\n                    value = 0;\n                }\n\n                var base = - value - 1;       // BASE is inverted record value\n                bc.setBase(child_id, base);  // Update BASE of child(leaf) node\n            }\n        }\n    };\n\n\n    /**\n     * Find BASE value that all children are allocatable in double array's region\n     */\n    DoubleArrayBuilder.prototype.findAllocatableBase = function (children_info) {\n\n        var bc = this.bc;\n\n        // Assertion: keys are sorted by byte order\n        // var c = -1;\n        // for (var i = 0; i < children_info.length; i = i + 3) {\n        //     if (children_info[i] < c) {\n        //         throw 'assertion error: not sort key'\n        //     }\n        //     c = children_info[i];\n        // }\n\n        // iterate linked list of unused nodes\n        var _base;\n        var curr = bc.getFirstUnusedNode();  // current index\n        // if (curr < 0) {\n        //     throw 'assertion error: getFirstUnusedNode returns negative value'\n        // }\n\n        while (true) {\n            _base = curr - children_info[0];\n\n            if (_base < 0) {\n                curr = - bc.getCheck(curr);  // next\n\n                // if (curr < 0) {\n                //     throw 'assertion error: getCheck returns negative value'\n                // }\n\n                continue;\n            }\n\n            var empty_area_found = true;\n            for (var i = 0; i < children_info.length; i = i + 3) {\n                var code = children_info[i];\n                var candidate_id = _base + code;\n\n                if (!this.isUnusedNode(candidate_id)) {\n                    // candidate_id is used node\n                    // next\n                    curr = - bc.getCheck(curr);\n                    // if (curr < 0) {\n                    //     throw 'assertion error: getCheck returns negative value'\n                    // }\n\n                    empty_area_found = false;\n                    break;\n                }\n            }\n            if (empty_area_found) {\n                // Area is free\n                return _base;\n            }\n        }\n    };\n\n    /**\n     * Check this double array index is unused or not\n     */\n    DoubleArrayBuilder.prototype.isUnusedNode = function (index) {\n        var bc = this.bc;\n        var check = bc.getCheck(index);\n\n        // if (index < 0) {\n        //     throw 'assertion error: isUnusedNode index:' + index;\n        // }\n\n        if (index === ROOT_ID) {\n            // root node\n            return false;\n        }\n        if (check < 0) {\n            // unused\n            return true;\n        }\n\n        // used node (incl. leaf)\n        return false;\n    };\n\n\n    /**\n     * Factory method of double array\n     */\n    function DoubleArray(bc) {\n        this.bc = bc;       // BASE and CHECK\n        this.bc.shrink();\n    }\n\n\n    /**\n     * Look up a given key in this trie\n     *\n     * @param {String} key\n     * @return {Boolean} True if this trie contains a given key\n     */\n    DoubleArray.prototype.contain = function (key) {\n\n        var bc = this.bc;\n\n        key += TERM_CHAR;\n        var buffer = stringToUtf8Bytes(key);\n\n        var parent = ROOT_ID;\n        var child = NOT_FOUND;\n\n        for (var i = 0; i < buffer.length; i++) {\n            var code = buffer[i];\n\n            child = this.traverse(parent, code);\n            if (child === NOT_FOUND) {\n                return false;\n            }\n\n            if (bc.getBase(child) <= 0) {\n                // leaf node\n                return true;\n            } else {\n                // not leaf\n                parent = child;\n                continue;\n            }\n        }\n        return false;\n    };\n\n\n    /**\n     * Look up a given key in this trie\n     *\n     * @param {String} key\n     * @return {Number} Record value assgned to this key, -1 if this key does not contain\n     */\n    DoubleArray.prototype.lookup = function (key) {\n\n        key += TERM_CHAR;\n        var buffer = stringToUtf8Bytes(key);\n\n        var parent = ROOT_ID;\n        var child = NOT_FOUND;\n\n        for (var i = 0; i < buffer.length; i++) {\n            var code = buffer[i];\n            child = this.traverse(parent, code);\n            if (child === NOT_FOUND) {\n                return NOT_FOUND;\n            }\n            parent = child;\n        }\n\n        var base = this.bc.getBase(child);\n        if (base <= 0) {\n            // leaf node\n            return - base - 1;\n        } else {\n            // not leaf\n            return NOT_FOUND;\n        }\n    };\n\n\n    /**\n     * Common prefix search\n     *\n     * @param {String} key\n     * @return {Array} Each result object has 'k' and 'v' (key and record,\n     * respectively) properties assigned to matched string\n     */\n    DoubleArray.prototype.commonPrefixSearch = function (key) {\n\n        var buffer = stringToUtf8Bytes(key);\n\n        var parent = ROOT_ID;\n        var child = NOT_FOUND;\n\n        var result = [];\n\n        for (var i = 0; i < buffer.length; i++) {\n            var code = buffer[i];\n\n            child = this.traverse(parent, code);\n\n            if (child !== NOT_FOUND) {\n                parent = child;\n\n                // look forward by terminal character code to check this node is a leaf or not\n                var grand_child = this.traverse(child, TERM_CODE);\n\n                if (grand_child !== NOT_FOUND) {\n                    var base = this.bc.getBase(grand_child);\n\n                    var r = {};\n\n                    if (base <= 0) {\n                        // If child is a leaf node, add record to result\n                        r.v = - base - 1;\n                    }\n\n                    // If child is a leaf node, add word to result\n                    r.k = utf8BytesToString(arrayCopy(buffer, 0, i + 1));\n\n                    result.push(r);\n                }\n                continue;\n            } else {\n                break;\n            }\n        }\n\n        return result;\n    };\n\n    DoubleArray.prototype.traverse = function (parent, code) {\n        var child = this.bc.getBase(parent) + code;\n        if (this.bc.getCheck(child) === parent) {\n            return child;\n        } else {\n            return NOT_FOUND;\n        }\n    };\n\n    DoubleArray.prototype.size = function () {\n        return this.bc.size();\n    };\n\n    DoubleArray.prototype.calc = function () {\n        return this.bc.calc();\n    };\n\n    DoubleArray.prototype.dump = function () {\n        return this.bc.dump();\n    };\n\n\n    // Array utility functions\n\n    var newArrayBuffer = function (signed, bytes, size) {\n        if (signed) {\n            switch(bytes) {\n                case 1:\n                return new Int8Array(size);\n                case 2:\n                return new Int16Array(size);\n                case 4:\n                return new Int32Array(size);\n                default:\n                throw new RangeError(\"Invalid newArray parameter element_bytes:\" + bytes);\n            }\n        } else {\n            switch(bytes) {\n                case 1:\n                return new Uint8Array(size);\n                case 2:\n                return new Uint16Array(size);\n                case 4:\n                return new Uint32Array(size);\n                default:\n                throw new RangeError(\"Invalid newArray parameter element_bytes:\" + bytes);\n            }\n        }\n    };\n\n    var arrayCopy = function (src, src_offset, length) {\n        var buffer = new ArrayBuffer(length);\n        var dstU8 = new Uint8Array(buffer, 0, length);\n        var srcU8 = src.subarray(src_offset, length);\n        dstU8.set(srcU8);\n        return dstU8;\n    };\n\n\n    /**\n     * Convert String (UTF-16) to UTF-8 ArrayBuffer\n     *\n     * @param {String} str UTF-16 string to convert\n     * @return {Uint8Array} Byte sequence encoded by UTF-8\n     */\n    var stringToUtf8Bytes = function (str) {\n\n        // Max size of 1 character is 4 bytes\n        var bytes = new Uint8Array(new ArrayBuffer(str.length * 4));\n\n        var i = 0, j = 0;\n\n        while (i < str.length) {\n            var unicode_code;\n\n            var utf16_code = str.charCodeAt(i++);\n            if (utf16_code >= 0xD800 && utf16_code <= 0xDBFF) {\n                // surrogate pair\n                var upper = utf16_code;           // high surrogate\n                var lower = str.charCodeAt(i++);  // low surrogate\n\n                if (lower >= 0xDC00 && lower <= 0xDFFF) {\n                    unicode_code =\n                        (upper - 0xD800) * (1 << 10) + (1 << 16) +\n                        (lower - 0xDC00);\n                } else {\n                    // malformed surrogate pair\n                    return null;\n                }\n            } else {\n                // not surrogate code\n                unicode_code = utf16_code;\n            }\n\n            if (unicode_code < 0x80) {\n                // 1-byte\n                bytes[j++] = unicode_code;\n\n            } else if (unicode_code < (1 << 11)) {\n                // 2-byte\n                bytes[j++] = (unicode_code >>> 6) | 0xC0;\n                bytes[j++] = (unicode_code & 0x3F) | 0x80;\n\n            } else if (unicode_code < (1 << 16)) {\n                // 3-byte\n                bytes[j++] = (unicode_code >>> 12) | 0xE0;\n                bytes[j++] = ((unicode_code >> 6) & 0x3f) | 0x80;\n                bytes[j++] = (unicode_code & 0x3F) | 0x80;\n\n            } else if (unicode_code < (1 << 21)) {\n                // 4-byte\n                bytes[j++] = (unicode_code >>> 18) | 0xF0;\n                bytes[j++] = ((unicode_code >> 12) & 0x3F) | 0x80;\n                bytes[j++] = ((unicode_code >> 6) & 0x3F) | 0x80;\n                bytes[j++] = (unicode_code & 0x3F) | 0x80;\n\n            } else {\n                // malformed UCS4 code\n            }\n        }\n\n        return bytes.subarray(0, j);\n    };\n\n\n    /**\n     * Convert UTF-8 ArrayBuffer to String (UTF-16)\n     *\n     * @param {Uint8Array} bytes UTF-8 byte sequence to convert\n     * @return {String} String encoded by UTF-16\n     */\n    var utf8BytesToString = function (bytes) {\n\n        var str = \"\";\n        var code, b1, b2, b3, b4, upper, lower;\n        var i = 0;\n\n        while (i < bytes.length) {\n\n            b1 = bytes[i++];\n\n            if (b1 < 0x80) {\n                // 1 byte\n                code = b1;\n            } else if ((b1 >> 5) === 0x06) {\n                // 2 bytes\n                b2 = bytes[i++];\n                code = ((b1 & 0x1f) << 6) | (b2 & 0x3f);\n            } else if ((b1 >> 4) === 0x0e) {\n                // 3 bytes\n                b2 = bytes[i++];\n                b3 = bytes[i++];\n                code = ((b1 & 0x0f) << 12) | ((b2 & 0x3f) << 6) | (b3 & 0x3f);\n            } else {\n                // 4 bytes\n                b2 = bytes[i++];\n                b3 = bytes[i++];\n                b4 = bytes[i++];\n                code = ((b1 & 0x07) << 18) | ((b2 & 0x3f) << 12) | ((b3 & 0x3f) << 6) | (b4 & 0x3f);\n            }\n\n            if (code < 0x10000) {\n\t            str += String.fromCharCode(code);\n            } else {\n\t            // surrogate pair\n\t            code -= 0x10000;\n\t            upper = (0xD800 | (code >> 10));\n\t            lower = (0xDC00 | (code & 0x3FF));\n\t            str += String.fromCharCode(upper, lower);\n            }\n        }\n\n        return str;\n    };\n\n\n    // public methods\n    var doublearray = {\n        builder: function (initial_size) {\n            return new DoubleArrayBuilder(initial_size);\n        },\n        load: function (base_buffer, check_buffer) {\n            var bc = newBC(0);\n            bc.loadBaseBuffer(base_buffer);\n            bc.loadCheckBuffer(check_buffer);\n            return new DoubleArray(bc);\n        }\n    };\n\n    if (\"undefined\" === typeof module) {\n\t    // In browser\n        window.doublearray = doublearray;\n    } else {\n\t    // In node\n        module.exports = doublearray;\n    }\n\n})();\n"]}