{"ScriptPreparationCode":"var Trie = class Trie {\r\n constructor() {\r\n this.root = { children: {} };\r\n this.size = 0;\r\n }\r\n\r\n add(key, value) {\r\n let node = this.root;\r\n for (let i = 0; i \u003C key.length; \u002B\u002Bi) {\r\n if (!node.children[key[i]]) node.children[key[i]] = { children: {} };\r\n node = node.children[key[i]];\r\n }\r\n node.value = value;\r\n this.size \u002B= 1;\r\n return value;\r\n }\r\n\r\n get(key) {\r\n let node = this.root;\r\n for (let i = 0; i \u003C key.length; \u002B\u002Bi) {\r\n if (!node.children[key[i]]) return undefined;\r\n node = node.children[key[i]];\r\n }\r\n return node.value;\r\n }\r\n\r\n remove(key) {\r\n this._remove(this.root, key, 0);\r\n }\r\n\r\n _remove(node, key, index) {\r\n if (!node) return undefined;\r\n\r\n if (index === key.length) {\r\n delete node.value;\r\n this.size -= 1;\r\n } else {\r\n const c = key[index];\r\n const child = this._remove(node.children[c], key, index \u002B 1);\r\n if (child) node.children[c] = child;\r\n else delete node.children[c];\r\n }\r\n\r\n if (Object.keys(node.children).length === 0 \u0026\u0026 node.value === undefined)\r\n return undefined;\r\n return node;\r\n }\r\n}\r\n\r\nfunction pseudoRandom() {\r\n pseudoRandom.value = (pseudoRandom.value ** 2 \u002B 3 * pseudoRandom.value \u002B 1) % 26\r\n return pseudoRandom.value\r\n}\r\n\r\npseudoRandom.value = 0\r\n\r\nfunction createRandomString(length) {\r\n let s = \u0027\u0027\r\n for (let i = 0; i \u003C length; \u002B\u002Bi) {\r\n s \u002B= String.fromCharCode(\u0027a\u0027.charCodeAt(0) \u002B pseudoRandom())\r\n }\r\n return s\r\n}\r\n\r\nconst N = 10000\r\nconst L = 1000\r\nconst strs = new Array(N)\r\nfor (let n = 0; n \u003C N; \u002B\u002Bn) strs[n] = createRandomString(L)\r\n\r\nvar ObjectWrapper = class ObjectWrapper {\r\n constructor() { this.data = {} }\r\n \r\n add(key, value) {\r\n this.data[key] = value\r\n }\r\n \r\n remove(key, value) {\r\n delete this.data[key]\r\n }\r\n \r\n get(key) {\r\n return this.data[key]\r\n }\r\n}\r\n\r\nfunction test(ds) {\r\n for (const s of strs) {\r\n ds.add(s, s)\r\n }\r\n for (const s of strs) {\r\n ds.get(s)\r\n }\r\n for (const s of strs) {\r\n ds.remove(s)\r\n }\r\n}","TestCases":[{"Name":"Trie","Code":"test(new Trie())","IsDeferred":false},{"Name":"Native Object","Code":"test(new ObjectWrapper())","IsDeferred":false}]}