This is an automated email from the ASF dual-hosted git repository. potiuk pushed a commit to branch master in repository https://gitbox.apache.org/repos/asf/airflow-cancel-workflow-runs.git
commit a38415f9b1bd6df21448f98b429f51cc2f3c412f Author: Jason T. Greene <[email protected]> AuthorDate: Tue Feb 18 22:48:39 2020 -0600 optimize queries to only pull active statuses --- __tests__/main.test.ts | 8 +- dist/index.js | 3951 +++++++++++++++++++++++++++++++++++++++++++++++- package-lock.json | 5 + package.json | 3 +- src/main.ts | 137 +- 5 files changed, 3996 insertions(+), 108 deletions(-) diff --git a/__tests__/main.test.ts b/__tests__/main.test.ts index 819d5d4..ab5dc2b 100644 --- a/__tests__/main.test.ts +++ b/__tests__/main.test.ts @@ -8,13 +8,13 @@ test('no op', () => {}) // test('test runs', () => { // const ip = path.join(__dirname, '..', 'lib', 'main.js') // process.env['INPUT_TOKEN'] = '' -// //process.env['INPUT_WORKFLOW'] = 'ci-actions.yml' +// process.env['INPUT_WORKFLOW'] = 'ci-actions.yml' // process.env['GITHUB_RUN_ID'] = '41374869' //'33782469' // process.env['GITHUB_REPOSITORY'] = '' // //process.env['GITHUB_HEAD_REF'] = 'refs/heads/n1hility-patch-5' -// process.env['GITHUB_REF'] = 'refs/heads/master' -// process.env['GITHUB_EVENT_NAME'] = 'push' -// // process.env['GITHUB_EVENT_NAME'] = 'schedule' +// //process.env['GITHUB_REF'] = 'refs/heads/master' +// // process.env['GITHUB_EVENT_NAME'] = 'push' +// process.env['GITHUB_EVENT_NAME'] = 'schedule' // // process.env['GITHUB_RUN_ID'] = '35599067' // // process.env['GITHUB_REPOSITORY'] = '' diff --git a/dist/index.js b/dist/index.js index 16c7215..ac890d9 100644 --- a/dist/index.js +++ b/dist/index.js @@ -1465,12 +1465,33 @@ var __importStar = (this && this.__importStar) || function (mod) { Object.defineProperty(exports, "__esModule", { value: true }); const github = __importStar(__webpack_require__(469)); const core = __importStar(__webpack_require__(393)); +const treemap = __importStar(__webpack_require__(706)); +function createRunsQuery(octokit, owner, repo, workflowId, status, branch, event) { + const request = branch === undefined + ? { + owner, + repo, + // eslint-disable-next-line @typescript-eslint/camelcase + workflow_id: workflowId, + status + } + : { + owner, + repo, + // eslint-disable-next-line @typescript-eslint/camelcase + workflow_id: workflowId, + status, + branch, + event + }; + return octokit.actions.listWorkflowRuns.endpoint.merge(request); +} function cancelDuplicates(token, selfRunId, owner, repo, workflowId, branch, event) { var e_1, _a; return __awaiter(this, void 0, void 0, function* () { const octokit = new github.GitHub(token); // Deteermind the workflow to reduce the result set, or reference anothre workflow - let resolvedId; + let resolvedId = ''; if (workflowId === undefined) { const reply = yield octokit.actions.getWorkflowRun({ owner, @@ -1478,69 +1499,65 @@ function cancelDuplicates(token, selfRunId, owner, repo, workflowId, branch, eve // eslint-disable-next-line @typescript-eslint/camelcase run_id: Number.parseInt(selfRunId) }); - resolvedId = reply.data.workflow_url.split('/').pop(); + resolvedId = reply.data.workflow_url.split('/').pop() || ''; + if (!(resolvedId.length > 0)) { + throw new Error('Could not resolve workflow'); + } } else { resolvedId = workflowId; } core.info(`Workflow ID is: ${resolvedId}`); - const request = branch === undefined - ? { - owner, - repo, - // eslint-disable-next-line @typescript-eslint/camelcase - workflow_id: resolvedId + // eslint-disable-next-line @typescript-eslint/no-explicit-any + const sorted = new treemap.TreeMap(); + for (const status of ['queued', 'in_progress']) { + const listRuns = createRunsQuery(octokit, owner, repo, resolvedId, status, branch, event); + try { + for (var _b = __asyncValues(octokit.paginate.iterator(listRuns)), _c; _c = yield _b.next(), !_c.done;) { + const item = _c.value; + // There is some sort of bug where the pagination URLs point to a + // different endpoint URL which trips up the resulting representation + // In that case, fallback to the actual REST 'workflow_runs' property + const elements = item.data.length === undefined ? item.data.workflow_runs : item.data; + for (const element of elements) { + sorted.set(element.run_number, element); + } + } } - : { - owner, - repo, - // eslint-disable-next-line @typescript-eslint/camelcase - workflow_id: resolvedId, - branch, - event - }; - const listRuns = octokit.actions.listWorkflowRuns.endpoint.merge(request); + catch (e_1_1) { e_1 = { error: e_1_1 }; } + finally { + try { + if (_c && !_c.done && (_a = _b.return)) yield _a.call(_b); + } + finally { if (e_1) throw e_1.error; } + } + } // If a workflow was provided process everything let matched = workflowId !== undefined; const heads = new Set(); - try { - for (var _b = __asyncValues(octokit.paginate.iterator(listRuns)), _c; _c = yield _b.next(), !_c.done;) { - const item = _c.value; - // There is some sort of bug where the pagination URLs point to a - // different endpoint URL which trips up the resulting representation - // In that case, fallback to the actual REST 'workflow_runs' property - const elements = item.data.length === undefined ? item.data.workflow_runs : item.data; - for (const element of elements) { - core.info(`${element.id} : ${element.workflow_url} : ${element.status} : ${element.run_number}`); - if (!matched) { - if (element.id.toString() !== selfRunId) { - // Skip everything up to this run - continue; - } - matched = true; - core.info(`Matched ${selfRunId}`); - } - if ('completed' === element.status.toString()) { - continue; - } - // This is a set of one in the non-schedule case, otherwise everything is a candidate - const head = `${element.head_repository.full_name}/${element.head_branch}`; - if (!heads.has(head)) { - core.info(`First: ${head}`); - heads.add(head); - continue; - } - core.info(`Cancelling: ${head}`); - yield cancelRun(octokit, owner, repo, element.id); + for (const entry of sorted.backward()) { + const element = entry[1]; + core.info(`${element.id} : ${element.workflow_url} : ${element.status} : ${element.run_number}`); + if (!matched) { + if (element.id.toString() !== selfRunId) { + // Skip everything up to this run + continue; } + matched = true; + core.info(`Matched ${selfRunId}`); } - } - catch (e_1_1) { e_1 = { error: e_1_1 }; } - finally { - try { - if (_c && !_c.done && (_a = _b.return)) yield _a.call(_b); + if ('completed' === element.status.toString()) { + continue; + } + // This is a set of one in the non-schedule case, otherwise everything is a candidate + const head = `${element.head_repository.full_name}/${element.head_branch}`; + if (!heads.has(head)) { + core.info(`First: ${head}`); + heads.add(head); + continue; } - finally { if (e_1) throw e_1.error; } + core.info(`Cancelling: ${head}`); + yield cancelRun(octokit, owner, repo, element.id); } }); } @@ -8711,6 +8728,3836 @@ module.exports = (promise, onFinally) => { /***/ }), +/***/ 706: +/***/ (function(module) { + +(function webpackUniversalModuleDefinition(root, factory) { + if(true) + module.exports = factory(); + else { var i, a; } +})(typeof self !== 'undefined' ? self : this, function() { +return /******/ (function(modules) { // webpackBootstrap +/******/ // The module cache +/******/ var installedModules = {}; +/******/ +/******/ // The require function +/******/ function __webpack_require__(moduleId) { +/******/ +/******/ // Check if module is in cache +/******/ if(installedModules[moduleId]) { +/******/ return installedModules[moduleId].exports; +/******/ } +/******/ // Create a new module (and put it into the cache) +/******/ var module = installedModules[moduleId] = { +/******/ i: moduleId, +/******/ l: false, +/******/ exports: {} +/******/ }; +/******/ +/******/ // Execute the module function +/******/ modules[moduleId].call(module.exports, module, module.exports, __webpack_require__); +/******/ +/******/ // Flag the module as loaded +/******/ module.l = true; +/******/ +/******/ // Return the exports of the module +/******/ return module.exports; +/******/ } +/******/ +/******/ +/******/ // expose the modules object (__webpack_modules__) +/******/ __webpack_require__.m = modules; +/******/ +/******/ // expose the module cache +/******/ __webpack_require__.c = installedModules; +/******/ +/******/ // define getter function for harmony exports +/******/ __webpack_require__.d = function(exports, name, getter) { +/******/ if(!__webpack_require__.o(exports, name)) { +/******/ Object.defineProperty(exports, name, { +/******/ configurable: false, +/******/ enumerable: true, +/******/ get: getter +/******/ }); +/******/ } +/******/ }; +/******/ +/******/ // getDefaultExport function for compatibility with non-harmony modules +/******/ __webpack_require__.n = function(module) { +/******/ var getter = module && module.__esModule ? +/******/ function getDefault() { return module['default']; } : +/******/ function getModuleExports() { return module; }; +/******/ __webpack_require__.d(getter, 'a', getter); +/******/ return getter; +/******/ }; +/******/ +/******/ // Object.prototype.hasOwnProperty.call +/******/ __webpack_require__.o = function(object, property) { return Object.prototype.hasOwnProperty.call(object, property); }; +/******/ +/******/ // __webpack_public_path__ +/******/ __webpack_require__.p = ""; +/******/ +/******/ // Load entry module and return exports +/******/ return __webpack_require__(__webpack_require__.s = 5); +/******/ }) +/************************************************************************/ +/******/ ([ +/* 0 */ +/***/ (function(module, exports, __nested_webpack_require_2850__) { + +"use strict"; + + +/** + * @private + */ +const RED = 1; +/** + * @private + */ +const BLACK = 2; + +/** + * @private + * A node for a red-black tree + */ +class TreeNode { + + /** + * Default constructor + */ + constructor() { + /** left child */ + this.left = null; + /** right child */ + this.right = null; + /** parent node */ + this.parent = null; + /** key object (additional 'value' data member is added in map-like classes) */ + this.key = null; + /** by default new node is red */ + this.color = RED; + } + + /** + * @returns parent of parent + */ + grandparent() { + let p = this.parent; + if (p === null) { + return null; + } // No parent means no grandparent + return p.parent; + } + + /** + * @returns the other child of the same parent + */ + sibling() { + let p = this.parent; + if (p === null) { + return null; + } // No parent means no sibling + if (this === p.left) { + return p.right; + } + else { + return p.left; + } + } + + /** + * @returns another child of the grandparent + */ + uncle() { + let p = this.parent; + if (p === null) { + return null; + } // No parent means no uncle + let g = p.parent; + if (g === null) { + return null; + } // No grandparent means no uncle + return p.sibling(); + } +} + +module.exports = { + TreeNode: TreeNode, + BLACK: BLACK, + RED: RED +}; + +/***/ }), +/* 1 */ +/***/ (function(module, exports) { + +/** + * Used by sets + * @private + */ +class KeyOnlyPolicy { + /** + * Returns key data from the specified node + * @param {*} n + */ + fetch(n) { + return n.key; + } + + /** + * Copies key data from one node to another + * @param {*} dst + * @param {*} src + */ + copy(dst, src) { + dst.key = src.key; + } + + /** + * @returns string representation of the key + * @param {*} node + */ + toString(node) { + return String(node.key); + } +} + +/** + * Used by maps + * @private + */ +class KeyValuePolicy { + /** + * Returns key-value data from the specified node + * @param {*} n + */ + fetch(n) { + return [n.key, n.value]; + } + + /** + * Copies key-value data from one node to another + * @param {*} dst + * @param {*} src + */ + copy(dst, src) { + dst.key = src.key; + dst.value = src.value; + } + + /** + * @returns string representation of key-value pair + * @param {*} node + */ + toString(node) { + return String(node.key) + ':' + String(node.value); + } +} + +/** + * Used for iteration through values of a map + * @private + */ +class ValueOnlyPolicy { + /** + * Returns data from the specified node + * @param {*} n + */ + fetch(n) { + return n.value; + } + + /** + * Copies value data from one node to another + * @param {*} dst + * @param {*} src + */ + copy(dst, src) { + dst.value = src.value; + } + + /** + * @returns string representation of node's value + * @param {*} node + */ + toString(node) { + return String(node.value); + } +} + +module.exports = { + KeyOnlyPolicy: KeyOnlyPolicy, + ValueOnlyPolicy: ValueOnlyPolicy, + KeyValuePolicy: KeyValuePolicy +}; + +/***/ }), +/* 2 */ +/***/ (function(module, exports, __nested_webpack_require_6477__) { + +"use strict"; + + +/** @ignore */ +const {TreeNode, RED, BLACK} = __nested_webpack_require_6477__(0); +/** @ignore */ +const {JsIterator, JsReverseIterator} = __nested_webpack_require_6477__(3); +/** @ignore */ +const {Iterator, ReverseIterator} = __nested_webpack_require_6477__(4); +/** @ignore */ +const {KeyOnlyPolicy, ValueOnlyPolicy, KeyValuePolicy} = __nested_webpack_require_6477__(1); +/** @ignore */ +const {InsertionResult} = __nested_webpack_require_6477__(8); + +/** insertion mode of a multimap, nodes with the same keys can be added */ +const INSERT_MULTI = 1; +/** if a node with the same key already exists then the subsequent attempts are ignored */ +const INSERT_UNIQUE = 2; +/** if a node with the same key already exists then it's value is replaced on subsequent attempts */ +const INSERT_REPLACE = 3; + +/** + * @private + * Special node in a tree is created for performance reasons + */ +class Head { + /** default constructor */ + constructor() { + /** node with the smallest key */ + this.leftmost = this; + /** node with the largest key */ + this.rightmost = this; + /** root node of the tree */ + this.root = this; + /** number of nodes in the tree */ + this.size = 0; + /** extra tag used in debuggin of unit tests */ + this.id = 'HEAD'; + } +} + +/** + * @private + * 3-way comparison, similar to strcmp and memcp in C programming language + * @returns +1 if the value of rhs is greater than lhs + * -1 if the value of rhs is less than lhs + * 0 if values are the same + */ +function compare(lhs, rhs) { + if (lhs < rhs) { + return -1; + } + else if (lhs === rhs) { + return 0; + } + else { + return 1; + } +} + +/** + * Red-black tree + * @access private + */ +class Tree { + /** default constructor of an empty tree */ + constructor() { + /** head */ + this.head = new Head(); + /** 3-way comparison function */ + this.compare = compare; + /** must be an instance of KeyOnlyPolicy for sets, or KeyValuePolicy for maps */ + this.valuePolicy = new KeyOnlyPolicy(); + } + + /** + * Deletes all nodes in the tree + */ + clear() { + this.head = new Head(); + } + + /** + * @returns number of nodes in the tree + */ + size() { + return this.head.size; + } + + /** + * @private + * A wrapper that calls 3-way comparison of node keys + * @param {*} lhs + * @param {*} rhs + */ + compareNodes(lhs, rhs) { + return this.compare(lhs.key, rhs.key); + } + + /** + * @private + * used by rotation operations + */ + replaceNode(oldNode, newNode) { + if (oldNode === newNode) { + return; + } + if (oldNode.parent === null) { + this.head.root = newNode; + } + else { + if (oldNode === oldNode.parent.left) { + oldNode.parent.left = newNode; + } + else { + oldNode.parent.right = newNode; + } + } + + if (!this.isLeaf(newNode)) { + newNode.parent = oldNode.parent; + } + } + + /** + * Rebalances tree as described below + + X Y + / \ / \ + Y c right rotate --> a X + / \ <-- left rotate / \ + a b b c + * @private + */ + rotateLeft(node) { + let right = node.right; + if (this.isLeaf(right)) { + throw new Error('rotateLeft can\'t be performed. The tree is corrupted'); + } + this.replaceNode(node, right); + + node.right = right.left; + if (right.left !== null) { + right.left.parent = node; + } + + right.left = node; + node.parent = right; + } + + /** + * Rebalances tree as described in rotateLeft + * @param {*} node - parent node + */ + rotateRight(node) { + let left = node.left; + if (this.isLeaf(left)) { + throw new Error('rotateRight can\'t be performed. The tree is corrupted'); + } + this.replaceNode(node, left); + + node.left = left.right; + if (left.right !== null) { + left.right.parent = node; + } + + left.right = node; + node.parent = left; + } + + /** + * @returns true - for null pointers and head node; false - for all other nodes + * @param {*} node + */ + isLeaf(node) { + if (node === null || node === this.head) { + return true; + } + return false; + } + + /** + * Leaf nodes are considered 'black'. All real nodes contain 'color' data member + * @param {*} node + */ + fetchColor(node) { + if (this.isLeaf(node)) { + return BLACK; + } + else { + return node.color; + } + } + + /** + * Tests a node for 'blackness'. + * @param {*} node + */ + isBlack(node) { + return (this.fetchColor(node) === BLACK); + } + + /** + * Tests node for 'redness'. + * @param {*} node + */ + isRed(node) { + return (this.fetchColor(node) === RED); + } + + /* =========================== + INSERT + =========================== */ + /** + * A node will be inserted into the tree even if nodes with the same key already exist + * @param {*} node + * @returns {InsertionResult} - indicates whether a node was added and provides iterator to it. + */ + insertMulti(node) { + return this.insertNode(node, INSERT_MULTI); + } + + /** + * The node is inserted into the tree only if nodes with the same key do not exist there + * @param {*} node + * @returns {InsertionResult} - indicates whether a node was added and provides iterator to it. + */ + insertUnique(node) { + return this.insertNode(node, INSERT_UNIQUE); + } + + /** + * The node is inserted. If a node with the same key exists it's value will be replaced by the value of the new node + * @param {*} node + * @returns {InsertionResult} - indicates whether a node was added and provides iterator to it. + */ + insertOrReplace(node) { + return this.insertNode(node, INSERT_REPLACE); + } + + /** + * @private + * Inserts node. Updates head node. Rebalances tree. + * @param {*} n - node + * @param {*} mode - one of INSERT_MULTI, INSERT_UNIQUE, INSERT_REPLACE + * @returns {InsertionResult} - indicates whether a node was added and provides iterator to it. + */ + insertNode(n, mode = INSERT_MULTI) { + let res = this.insertNodeInternal(this.head.root, n, mode); + if (res.wasAdded) { + if (this.head.size === 0) { + this.head.root = n; + this.head.leftmost = n; + this.head.rightmost = n; + + n.left = this.head; + n.right = this.head; + } + else if (this.head.leftmost.left === n) { + this.head.leftmost = n; + n.left = this.head; + } + else if (this.head.rightmost.right === n) { + this.head.rightmost = n; + n.right = this.head; + } + this.insertRepairTree(n); + this.head.size = this.head.size + 1; + } + return res; + } + + /** + * @private + * Inserts node according to the mode + * @param {*} root - root node of the tree + * @param {*} n - node to be inserted + * @param {*} mode - one of INSERT_MULTI, INSERT_UNIQUE, INSERT_REPLACE + * @returns {InsertionResult} - indicates whether a node was added and provides iterator to it. + */ + insertNodeInternal(root, n, mode) { + // recursively descend the tree until a leaf is found + let x = root; + let y = null; + let rc = -1; + // find matching node + while (!this.isLeaf(x)) { + y = x; + rc = this.compareNodes(n, y); + if (rc < 0) { + x = y.left; + } + else if (rc > 0) { + x = y.right; + } + else { + // node with the same key value + switch (mode) { + case INSERT_UNIQUE: + // it's a duplicate + return new InsertionResult(false, false, undefined); + case INSERT_REPLACE: + this.valuePolicy.copy(y, n); + return new InsertionResult(false, true, new Iterator(y, this)); + default: + // INSERT_MULTI + x = y.right; + } + } + } + if (this.isLeaf(y)) { + n.parent = null; + n.left = this.head; + n.right = this.head; + } + else { + n.parent = y; + if (rc < 0) { + y.left = n; + } + else { + y.right = n; + } + } + return new InsertionResult(true, false, new Iterator(n, this)); + } + + /** + * @private + * The method is decribed at: https://en.wikipedia.org/wiki/Red%E2%80%93black_tree#Insertion + * @param {*} n - node + */ + insertRepairTree(n) { + if (n.parent === null) { + this.repairCase1(n); + } + else if (this.isBlack(n.parent)) { + /* insert_case2(n); + // do nothing */ + } + else if (this.isRed(n.uncle())) { + this.repairCase3(n); + } + else { + this.repairCase4(n); + } + } + + /** + * @private + * The method is decribed at: https://en.wikipedia.org/wiki/Red%E2%80%93black_tree#Insertion + * @param {*} n - node + */ + repairCase1(n) { + n.color = BLACK; + } + + /** + * @private + * The method is decribed at: https://en.wikipedia.org/wiki/Red%E2%80%93black_tree#Insertion + * @param {*} n - node + */ + repairCase3(n) { + n.parent.color = BLACK; + n.uncle().color = BLACK; + n.grandparent().color = RED; + this.insertRepairTree(n.grandparent()); + } + + /** + * @private + * The method is decribed at: https://en.wikipedia.org/wiki/Red%E2%80%93black_tree#Insertion + * @param {*} n - node + */ + repairCase4(n) { + let p = n.parent; + let g = n.grandparent(); + + let nr = null; + if ((g.left !== null) + && (n === g.left.right)) { + this.rotateLeft(p); + n = n.left; + } + else if ((g.right !== null) + && (n === g.right.left)) { + this.rotateRight(p); + n = n.right; + } + + p = n.parent; + g = n.grandparent(); + if (n === p.left) { + this.rotateRight(g); + } + else { + this.rotateLeft(g); + } + + p.color = BLACK; + g.color = RED; + } + + /** + * @returns the node with the highest key for the subtree of the specified root node + * @param {*} node - root node of the subtree to be evaluated + */ + fetchMaximum(node) { + while (!this.isLeaf(node.right)) { + node = node.right; + } + + return node; + } + + /** + * @returns the node with the lowest key for the subtree of the specified root node + * @param {*} node - root node of the subtree to be evaluated + */ + fetchMinimum(node) { + while (!this.isLeaf(node.left)) { + node = node.left; + } + + return node; + } + + /* =========================== + ERASE + =========================== */ + /** + * Removes node from the tree + * @param {*} node + */ + erase(node) { + if (this.isLeaf(node)) { + return; + } + + this.eraseInternal(node); + let h = this.head; + h.size = h.size - 1; + } + + /** + * @private + * The method is decribed at: https://en.wikipedia.org/wiki/Red%E2%80%93black_tree#Removal + * @param {*} node - node + */ + eraseInternal(node) { + if (!this.isLeaf(node.left) + && !this.isLeaf(node.right)) { + let pred = this.fetchMaximum(node.left); + + this.valuePolicy.copy(node, pred); + node = pred; + } + + let child = (this.isLeaf(node.right)) ? node.left : node.right; + + if (this.isBlack(node)) { + this.eraseCase1(node); + } + this.replaceNode(node, child); + if (this.head.size === 2) { + if (!this.isLeaf(child)) { + // Root node must be BLACK + child.color = BLACK; + } + } + + let h = this.head; + if (this.isLeaf(child)) { + /* The node didn't have children and it was removed + the head needs to update leftmost, rightmost pointers */ + if (h.leftmost === node) { + let p = node.parent; + if (p !== null) { + h.leftmost = p; + p.left = h; + } + else { + h.leftmost = h; + } + } + if (h.rightmost === node) { + let p = node.parent; + if (p !== null) { + h.rightmost = p; + p.right = h; + } + else { + h.rightmost = h; + } + } + } + else { + // the node had a child. Now node is removed. Any references should point to the child now + if (h.leftmost === node) { + h.leftmost = child; + child.left = h; + } + if (h.rightmost === node) { + h.rightmost = child; + child.right = h; + } + } + } + + /** + * @private + * The method is decribed at: https://en.wikipedia.org/wiki/Red%E2%80%93black_tree#Removal + * @param {*} node + */ + eraseCase1(node) { + if (node.parent === null) { + return; + } + else { + this.eraseCase2(node); + } + } + + /** + * @private + * The method is decribed at: https://en.wikipedia.org/wiki/Red%E2%80%93black_tree#Removal + * @param {*} node + */ + eraseCase2(node) { + let s = node.sibling(); + + if (this.isRed(s)) { + node.parent.color = RED; + s.color = BLACK; + + if (node === node.parent.left) { + this.rotateLeft(node.parent); + } + else { + this.rotateRight(node.parent); + } + } + this.eraseCase3(node); + } + + /** + * @private + * The method is decribed at: https://en.wikipedia.org/wiki/Red%E2%80%93black_tree#Removal + * @param {*} node + */ + eraseCase3(node) { + let s = node.sibling(); + let p = node.parent; + if (this.isBlack(p) + && this.isBlack(s) + && this.isBlack(s.left) + && this.isBlack(s.right)) { + + s.color = RED; + this.eraseCase1(p); + } + else { + this.eraseCase4(node); + } + } + + /** + * @private + * The method is decribed at: https://en.wikipedia.org/wiki/Red%E2%80%93black_tree#Removal + * @param {*} node + */ + eraseCase4(node) { + let s = node.sibling(); + let p = node.parent; + if (this.isRed(p) + && this.isBlack(s) + && this.isBlack(s.left) + && this.isBlack(s.right)) { + + s.color = RED; + p.color = BLACK; + } + else { + this.eraseCase5(node); + } + } + + /** + * @private + * The method is decribed at: https://en.wikipedia.org/wiki/Red%E2%80%93black_tree#Removal + * @param {*} node + */ + eraseCase5(node) { + let s = node.sibling(); + let p = node.parent; + /* The check below is unnecessary + due to case 2 (even though case 2 changed the sibling to a sibling's child, + the sibling's child can't be red, since no red parent can have a red child). */ + /* if ((!this.isLeaf(s)) + && this.isBlack(s)) { */ + + /* the following statements just force the red to be on the left of the left of the parent, + or right of the right, so case six will rotate correctly. */ + if (node === p.left + && this.isRed(s.left) + && this.isBlack(s.right)) { + + s.color = RED; + s.left.color = BLACK; + this.rotateRight(s); + } + else if (node === p.right + && this.isBlack(s.left) + && this.isRed(s.right)) { + + s.color = RED; + s.right.color = BLACK; + this.rotateLeft(s); + } + //} + this.eraseCase6(node); + } + + /** + * @private + * The method is decribed at: https://en.wikipedia.org/wiki/Red%E2%80%93black_tree#Removal + * @param {*} node + */ + eraseCase6(node) { + let s = node.sibling(); + let p = node.parent; + s.color = this.fetchColor(p); + p.color = BLACK; + + if (node === p.left) { + s.right.color = BLACK; + this.rotateLeft(p); + } + else { + s.left.color = BLACK; + this.rotateRight(p); + } + } + + /* =========================== + SEARCH BY KEY + =========================== */ + /** + * @returns an iterator pointin to a node with matching key value. If node is not found then end() iterator is returned. + * @param {*} k - key value + */ + find(k) { + let y = this.head; + let x = y.root; + while (!this.isLeaf(x)) { + let rc = this.compare(x.key, k); + if (rc > 0) { + y = x; + x = x.left; + } + else if (rc < 0) { + y = x; + x = x.right; + } + else { + return new Iterator(x, this); + } + } + return new Iterator(this.head, this); + } + + /** + * @returns an iterator pointing to the first node in the tree that is not less than + * (i.e. greater or equal to) the specified key value, or end() if no such node is found. + * @param {*} k - key value + */ + lowerBound(k) { + let y = this.head; + let x = y.root; + while (!this.isLeaf(x)) { + let rc = this.compare(x.key, k); + if (rc >= 0) { + y = x; + x = x.left; + } + else { + x = x.right; + } + } + return new Iterator(y, this); + } + + /** + * @returns an iterator pointing to the first node in the tree that is greater than + * the specified key value, or end() if no such node is found. + * @param {*} k - key value + */ + upperBound(k) { + let y = this.head; + let x = y.root; + while (!this.isLeaf(x)) { + let rc = this.compare(x.key, k); + if (rc > 0) { + y = x; + x = x.left; + } + else { + x = x.right; + } + } + return new Iterator(y, this); + } + + /* =========================== + ITERATORS + =========================== */ + + /** + * @returns iterator pointing to the node with the lowest key + */ + begin() { + return new Iterator(this.head.leftmost, this); + } + + /** + * @returns iterator pointing to the node following the node with the highest key + */ + end() { + return new Iterator(this.head, this); + } + + /** + * @returns iterator pointing to the node with the highest key + */ + rbegin() { + return new ReverseIterator(this.head.rightmost, this); + } + + /** + * @returns iterator pointing to the node preceding the node with the lowest key + */ + rend() { + return new ReverseIterator(this.head, this); + } + + /** + * @private + * provides support for ES6 forward iteration + */ + jsBegin() { + return this.head.leftmost; + } + + /** + * @private + * provides support for ES6 forward iteration + */ + jsEnd() { + return this.head; + } + + /** + * @private + * provides support for ES6 reverse iteration + */ + jsRbegin() { + return this.head.rightmost; + } + + /** + * @private + * provides support for ES6 forward iteration + */ + jsRend() { + return this.head; + } + + /** + * @returns node following the specified node in ascending order of their keys + * @param {*} n - node + */ + next(n) { + if (n === this.head) { + return this.head.leftmost; + } + if (n.right === this.head) { + return this.head; + } + if (n.right !== null) { + let res = this.fetchMinimum(n.right); + return res; + } + else { + while (n.parent.left !== n) { + n = n.parent; + } + return n.parent; + } + } + + /** + * @returns node preceding the specified node in ascending order of their keys + * @param {*} n - node + */ + prev(n) { + if (n === this.head) { + return this.head.rightmost; + } + if (n.left === this.head) { + return this.head; + } + if (n.left !== null) { + let res = this.fetchMaximum(n.left); + return res; + } + else { + while (n.parent.right !== n) { + n = n.parent; + } + return n.parent; + } + } + + /** + * ES6 forward iteration + */ + [Symbol.iterator]() { + return new JsIterator(this); + } + + /** + * ES6 reverse iteration + */ + backward() { + return new JsReverseIterator(this); + } + + /** + * @returns a new JsIterator object that contains the [key, value] pairs for each element in the order of the keys. + */ + entries() { + return new JsIterator(this); + } + + /** + * @returns a new JsIterator object that contains the keys for each element in the order of the keys. + */ + keys() { + return new JsIterator(this, new KeyOnlyPolicy()); + } + + /** + * @returns a new JsIterator object that contains the values for each element in the order of the keys. + */ + values() { + return new JsIterator(this, new ValueOnlyPolicy()); + } + + /** + * @returns first element of the container, or undefined if container is empty + */ + first() { + if (this.size() === 0) { + return undefined; + } + else { + let it = this.begin(); + return this.valuePolicy.fetch(it.node); + } + } + + /** + * @returns last element of the container, or undefined if container is empty + */ + last() { + if (this.size() === 0) { + return undefined; + } + else { + let it = this.rbegin(); + return this.valuePolicy.fetch(it.node); + } + } + + /** + * @returns String representation of the container + */ + toString() { + let parts = []; + for (let it = this.begin(); !it.equals(this.end()); it.next()) { + // convert each key-value pair + parts.push(this.valuePolicy.toString(it.node)); + } + return '{' + parts.join(',') + '}'; + } + + /** + * @returns String tag of this class + */ + get [Symbol.toStringTag]() { + return 'Tree'; + } + + /** + * @returns constructor object for this class + */ + static get [Symbol.species]() { + return Tree; + } + +} + +module.exports = { + Tree: Tree, + compare: compare +}; + + +/***/ }), +/* 3 */ +/***/ (function(module, exports, __nested_webpack_require_31214__) { + +"use strict"; + + +/* Containers are expected to support the following methods: + jsBegin() - returns the very first node + jsEnd() - returns the node beyond the last one + next(node) - returns the next node + prev(node) - returns the previous node + valuePolicy - an instance of KeyOnlyPolicy, or KeyValuePolicy */ +/** + * ES6-style forward iterator. + * + * @example + * let m = new TreeMap(); + * ... + * for (let [key, value] of m) { + * console.log(`key: ${key}, value: ${value}`); + * } + * // iterate values + * for (let value of m.values()) { + * console.log(`value: ${value}`); + * } + */ +class JsIterator { + /** + * @param {*} container + */ + constructor(container, valuePolicy = container.valuePolicy) { + /** + * @private + * Internal reference to a container + */ + this.container = container; + /** + * @private + * valuePolicy implements what members of the node will be returned: key, value, or key and value + */ + this.valuePolicy = valuePolicy; + /** + * @private + * current node + */ + this.node = container.jsBegin(); + } + + /** + * As documented in ES6 iteration protocol. It can be used for manual iteration. + * Iterators are documented here: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Guide/Iterators_and_Generators + * + * @example + * let m = new TreeMap(); + * ... + * let jsIt = m.entries(); + * while (true) { + * let res = it.next(); + * if (res.done) { + * break; + * } + * console.log(`key: ${res.value[0]}, value: ${res.value[1]`}); + * } + */ + next() { + let res = {}; + res.done = (this.node === this.container.jsEnd()); + if (!res.done) { + res.value = this.valuePolicy.fetch(this.node); + this.node = this.container.next(this.node); + } + return res; + } + + /** + * Support for ES6 for-of loops. + * @returns {JsIterator} + */ + [Symbol.iterator]() { + return this; + } + + /** + * A reverse iterator for the same container. + * @returns {JsReverseIterator} + * @example + * let m = new TreeMap(); + * ... + * // iterate all key-value pairs in reverse order + * for (let [key, value] of m.backwards()) { + * console.log(`key: ${key}, value: ${value}`); + * } + */ + backwards() { + // eslint-disable-next-line no-use-before-define + return new JsReverseIterator(this.container, this.valuePolicy); + } +} + +/* Containers are expected to support the following methods: + jsRbegin() - returns the very first node in reverse order (e.g. the very last node) + jsrEnd() - returns the node beyond the last one in reverse order (e.g. the node before the first one) + next(node) - returns the next node + prev(node) - returns the previous node + valuePolicy - an instance of KeyOnlyPolicy, or KeyValuePolicy */ +/** + * ES6-style backward iterator + * @example + * let m = new TreeMap(); + * ... + * // iterate all key-value pairs in reverse order + * for (let [key, value] of m.backwards()) { + * console.log(`key: ${key}, value: ${value}`); + * } + * // iterate keys in reverse order + * for (let key of m.keys().backwards()) { + * console.log(`key: ${key}`); + * } + */ +class JsReverseIterator { + /** + * @param {*} container + */ + constructor(container, valuePolicy = container.valuePolicy) { + /** + * @private + * Internal reference to a container + */ + this.container = container; + /** + * @private + * valuePolicy implements what members of the node will be returned: key, value, or key and value + */ + this.valuePolicy = valuePolicy; + /** + * @private + * current node + */ + this.node = container.jsRbegin(); + } + + /** + * As documented in ES6 iteration protocol. It can be used for manual iteration. + * Iterators are documented here: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Guide/Iterators_and_Generators + * + * @example + * let m = new TreeMap(); + * ... + * let jsIt = m.entries().backwards(); + * while (true) { + * let res = it.next(); + * if (res.done) { + * break; + * } + * console.log(`key: ${res.value[0]}, value: ${res.value[1]`}); + * } + */ + next() { + let res = {}; + res.done = (this.node === this.container.jsRend()); + if (!res.done) { + res.value = this.valuePolicy.fetch(this.node); + this.node = this.container.prev(this.node); + } + return res; + } + + /** + * Support for ES6 for-of loops. + * @returns {JsReverseIterator} + */ + [Symbol.iterator]() { + return this; + } + + /** + * A forward iterator for the same container + * @returns {JsIterator} + * @example + * let m = new TreeMap(); + * ... + * // iterate all key-value pairs in direct order + * for (let [key, value] of m.backwards().backwards()) { + * console.log(`key: ${key}, value: ${value}`); + */ + backwards() { + return new JsIterator(this.container, this.valuePolicy); + } +} + +module.exports = { + JsIterator: JsIterator, + JsReverseIterator: JsReverseIterator +}; + +/***/ }), +/* 4 */ +/***/ (function(module, exports, __nested_webpack_require_36806__) { + +"use strict"; + +/** + * Base class for STL-like iterators. It references a node (or index) and a container. + * Navigation is achieved by calling container's prev() and next() methods. + */ +class BaseIterator { + /** + * @param {*} node - current node + * @param {*} container - container + */ + constructor(node, container) { + /** + * @private + * __n - internal node reference + */ + this.__n = node; + /** + * @private + * __c - internal container reference + */ + this.__c = container; + } + + /** + * Two iterators are considered to be equal if they point to the same node of the same container + * @param {BaseIterator} rhs - object on the 'right-hand side' of .eq. operator + * @returns {boolean} + */ + equals(rhs) { + let lhsClass = this.constructor.name; + let rhsClass = rhs.constructor.name; + if (lhsClass !== rhsClass) { + throw new Error(`Can't compare an instance of ${lhsClass} with an instance of ${rhsClass}`); + } + if (this.__c !== rhs.__c) { + throw new Error('Iterators belong to different containers'); + } + return this.__n === rhs.__n; + } + + /** + * @private + * @returns current node + */ + get node() { + return this.__n; + } + + /** + * @private + * @returns key of the current node + */ + get key() { + return this.__n.key; + } + + /** + * @private + * @returns value of the current node + */ + get value() { + return this.__n.value; + } + + /** + * @private + * @returns container that holds current node + */ + get container() { + return this.__c; + } +} + +/** + * STL-like forward iterator. It's more verbose than ES6 iterators, but allows iteration over any part of the container + * + * @example + * let m = new TreeMap(); + * ... + * for (let it = m.begin(); !it.equals(m.end()); it.next()) { + * console.log(`key: ${it.key}, value: ${it.value}`); + * } + */ +class Iterator extends BaseIterator { + /** + * There are 3 ways to construct an iterator: + * + * 1. Using a node and a container + * 2. Copy constructor / clone + * 3. Copy constructor / clone from ReverseIterator instance + * @param {*} args + * + * @example + * // Using a node and a container + * let it = new Iterator(node, container); + * + * // Copy constructor / clone + * let it1 = new Iterator(node, container); + * let it2 = new Iterator(it1); + * + * // Copy constructor / clone from ReverseIterator instance + * let it1 = new ReverseIterator(node, container); + * let it2 = new Iterator(it1); + */ + constructor(...args) { + if (args.length === 2) { + let [node, container] = args; + super(node, container); + } + else if (args.length === 1) { + let [obj] = args; + let className = obj.constructor.name; + if (className === Iterator.name) { + super(obj.__n, obj.__c); + } + // eslint-disable-next-line no-use-before-define + else if (className === ReverseIterator.name) { + let c = obj.__c; + super(c.next(obj.__n), c); + } + else { + throw new Error(`Can't create an Iterator from ${className}`); + } + } + else { + throw new Error('Can\'t create an Iterator with provided parameters'); + } + } + + /** + * Replaces node reference with the reference of the next node in the container. + * Can be used for manual iteration over a range of key-value pairs. + * @example + * let m = new TreeMap(); + * ... // add key-value pairs., using numbers as keys + * let from = t.lowerBound(0); + * let to = t.upperBound(50); + * let it = from; + * while (!it.equals(to)) { + * console.log(it.key); + * it.next(); + * } + */ + next() { + /** + * __n and __c are defined in the base class + */ + this.__n = this.__c.next(this.__n); + } + + /** + * Replaces node reference with the reference of the previous node in the container + * Can be used for manual reverse iteration over a range of key-value pairs. + * @example + * let m = new TreeMap(); + * ... // add key-value pairs., using numbers as keys + * let from = t.lowerBound(0); + * let to = t.upperBound(50); + * let it = to; + * while (!it.equals(from)) { + * it.prev(); + * console.log(it.key); + * } + */ + prev() { + this.__n = this.__c.prev(this.__n); + } +} + +/** + * STL-like backward iterator. Can be used to traverse container or a range in the reverse order. + * It's more verbose than ES6 iterators, but allows iteration over any part of the container + * + * @example + * let m = new TreeMap(); + * ... + * for (let it = m.rbegin(); !it.equals(m.rend()); it.next()) { + * console.log(`key: ${it.key}, value: ${it.value}`); + * } + */ +class ReverseIterator extends BaseIterator { + /** + * There are 3 ways to construct a reverse iterator: + * + * 1. Using a node and a container + * 2. Copy constructor / clone + * 3. Copy constructor / clone from forward Iterator instance + * @param {*} args + * + * @example + * // Using a node and a container + * let it = new ReverseIterator(node, container); + * + * // Copy constructor / clone + * let it1 = new ReverseIterator(node, container); + * let it2 = new ReverseIterator(it1); + * + * // Copy constructor / clone from forward Iterator instance + * let it1 = new Iterator(node, container); + * let it2 = new ReverseIterator(it1); + */ + constructor(...args) { + if (args.length === 2) { + let [node, container] = args; + super(node, container); + } + else if (args.length === 1) { + let [obj] = args; + let className = obj.constructor.name; + if (className === ReverseIterator.name) { + super(obj.__n, obj.__c); + } + else if (className === Iterator.name) { + let c = obj.__c; + super(c.prev(obj.__n), c); + } + else { + throw new Error(`Can't create an ReverseIterator from ${className}`); + } + } + else { + throw new Error('Can\'t create a Reverse Iterator with provided parameters'); + } + } + + /** + * Replaces node reference with the reference of the previous node in the container, because it works in reverse order + * Can be used for manual reverse iteration over a range of key-value pairs. + * @example + * let m = new TreeMap(); + * ... // add key-value pairs., using numbers as keys + * let from = new ReverseIterator(t.upperBound(50)); + * let to = new ReverseIterator(t.lowerBound(0)); + * let it = from; + * while (!it.equals(to)) { + * console.log(it.key); + * it.next(); + * } + */ + next() { + /** + * __n and __c are defined in the base class + */ + this.__n = this.__c.prev(this.__n); + } + + /** + * Replaces node reference with the reference of the next node in the container, because it works in reverse order + * Can be used for manual forward iteration over a range of key-value pairs. + * @example + * let m = new TreeMap(); + * ... // add key-value pairs., using numbers as keys + * let from = new ReverseIterator(t.upperBound(50)); + * let to = new ReverseIterator(t.lowerBound(0)); + * let it = to; + * while (!it.equals(from)) { + * it.prev(); + * console.log(it.key); + * } + */ + prev() { + this.__n = this.__c.next(this.__n); + } +} + +module.exports = { + Iterator: Iterator, + ReverseIterator: ReverseIterator +}; + +/***/ }), +/* 5 */ +/***/ (function(module, exports, __nested_webpack_require_45031__) { + +module.exports = __nested_webpack_require_45031__(6); + + +/***/ }), +/* 6 */ +/***/ (function(module, exports, __nested_webpack_require_45149__) { + +/* This is an entry point to the library. + It collects all public classes and re-exports them */ +/**@private */ +const {TreeMap} = __nested_webpack_require_45149__(7); +/**@private */ +const {TreeMultiMap} = __nested_webpack_require_45149__(9); +/**@private */ +const {TreeSet} = __nested_webpack_require_45149__(10); +/**@private */ +const {TreeMultiSet} = __nested_webpack_require_45149__(11); +/**@private */ +const {Iterator, ReverseIterator} = __nested_webpack_require_45149__(4); +/**@private */ +const {JsIterator, JsReverseIterator} = __nested_webpack_require_45149__(3); + +module.exports = { + Iterator: Iterator, + ReverseIterator: ReverseIterator, + JsIterator: JsIterator, + JsReverseIterator: JsReverseIterator, + TreeMap: TreeMap, + TreeMultiMap: TreeMultiMap, + TreeSet: TreeSet, + TreeMultiSet: TreeMultiSet, +}; + +/***/ }), +/* 7 */ +/***/ (function(module, exports, __nested_webpack_require_46005__) { + +/** An implementation of red-black tree */ +const {Tree} = __nested_webpack_require_46005__(2); +/** Classes that regulate whether tree nodes hold keys only, or key-value pairs */ +const {KeyValuePolicy} = __nested_webpack_require_46005__(1); +/** Node for a red-black tree */ +const {TreeNode} = __nested_webpack_require_46005__(0); + +/** + * TreeMap is an associative container that stores elements formed + * by a combination of a key value and a mapped value, following a specific order. + * + * In a TreeMap, the key values are generally used to sort and uniquely identify + * the elements, while the mapped values store the content associated to this key. + * The types of key and mapped value may differ. + * + * ## Container properties + * * **Associative** - Elements in associative containers are referenced by their key + * and not by their absolute position in the container. + * * **Ordered** - The elements in the container follow a strict order at all times. + * All inserted elements are given a position in this order. + * * **Map** - Each element associates a key to a mapped value. Keys are meant + * to identify the elements whose main content is the mapped value. + * * **Unique keys** - No two elements in the container can have equivalent keys. + * + * @example + * let map = new TreeMap(); + * // add few values + * map.set(1, 'a'); + * map.set(2, 'b'); + * // find a value by key + * let v = map.get(1); // << 'a' + * // print all key-value pairs + * for (let [key, value] of map) { + * console.log(`key: ${key}, value: ${value}`); + * } + */ +class TreeMap { + /*====================================================== + * Methods of ES6 Map + *======================================================*/ + + /** + * Creates an empty, or a pre-initialized map. + * @param {*} [iterable] Another iterable object whose key-value pairs are added into the newly created map. + * @example + * // Create an empty map + * let map1 = new TreeMap(); + * // Create and initialize map + * let map2 = new TreeMap([[1, 'A'], [2, 'B'], [3, 'C']]); + */ + constructor(iterable) { + /** Internal tree */ + this.__t = new Tree(); + this.__t.valuePolicy = new KeyValuePolicy(); + if ((iterable !== undefined) + && (iterable !== null)) { + if (iterable[Symbol.iterator] !== undefined) { + // copy contents + for (let [k, v] of iterable) { + this.set(k, v); + } + } + else { + throw new Error('TreeMap constructor accepts only iterable objects'); + } + } + } + + /** + * String tag of this class + * @returns {String} + * @example + * Object.prototype.toString.call(new TreeMap()); // "[object TreeMap]" + */ + get [Symbol.toStringTag]() { + return 'TreeMap'; + } + + /** + * Allows to create programmatically an instance of the same class + * @returns constructor object for this class. + * @example + * let map = new TreeMap(); + * let constrFunc = Object.getPrototypeOf(map).constructor[Symbol.species]; + * let map2 = new constrFunc(); + */ + static get [Symbol.species]() { + return TreeMap; + } + + /** + * Removes all key-value pairs. + * @example + * let map = new TreeMap([[1, 'A'], [2, 'B'], [3, 'C']]); + * map.clear(); + * console.log(map.size); // 0 + */ + clear() { + this.__t.clear(); + } + + /** + * Removes key-value pair with the specified key if such entry exists. Does nothing otherwise. + * @example + * let map = new TreeMap([[1, 'A'], [2, 'B'], [3, 'C']]); + * map.delete(2); + * console.log(map.toString()); // {1:A,3:C} + */ + delete(key) { + let it = this.__t.find(key); + if (!it.equals(this.__t.end())) { + this.__t.erase(it.node); + } + } + + /** + * Forward ES6 iterator for all key-value pairs in ascending order of the keys. + * @returns {JsIterator} + * @example + * let map = new TreeMap([[1, 'A'], [2, 'B'], [3, 'C']]); + * for (let [key,value] of map.entries()) { + * console.log(`key: ${key}, value: ${value}`); + * } + */ + entries() { + return this.__t.entries(); + } + + /** + * Iterates all key-value pairs using a callback in ascending order of the keys. + * Note that ES6 specifies the order of key value parameters in the callback differently from for-of loop. + * @example + * let map = new TreeMap([[1, 'A'], [2, 'B'], [3, 'C']]); + * map.forEach(function(value, key, container) { + * console.log(`key: ${key}, value: ${value}`); + * }); + */ + forEach(callback) { + for (let [k, v] of this.__t) { + callback(v, k, this); + } + } + + /** + * Finds value associated with the specified key. If specified key does not exist then undefined is returned. + * @returns {*} + * @param {*} key a value of any type that can be compared with a key + * @example + * let map = new TreeMap([[1, 'A'], [2, 'B'], [3, 'C']]); + * let v = map.get(3); // 'C' + * * let v = map.get(4); // returns undefined + */ + get(key) { + let it = this.__t.find(key); + if (!it.equals(this.__t.end())) { + return it.value; + } + else { + return undefined; + } + } + + /** + * A boolean indicator whether map contains a key-value pair with the specified key + * @returns {Boolean} + * @param {*} key a value of any type that can be compared with a key + * @example + * let map = new TreeMap([[1, 'A'], [2, 'B'], [3, 'C']]); + * let b = map.get(3); // true + */ + has(key) { + let it = this.__t.find(key); + if (!it.equals(this.__t.end())) { + return true; + } + else { + return false; + } + } + + /** + * Forward ES6 iterator for all keys in ascending order of the keys. + * @returns {JsIterator} + * @example + * // iterate all keys + * let map = new TreeMap([[1, 'A'], [2, 'B'], [3, 'C']]); + * for (let k of map.keys()) { + * console.log(k); // 1, 2, 3 + * } + * // iterate all keys in reverse order + * let map = new TreeMap([[1, 'A'], [2, 'B'], [3, 'C']]); + * for (let k of map.keys().backward()) { + * console.log(k); // 3, 2, 1 + * } + */ + keys() { + return this.__t.keys(); + } + + /** + * Adds or updates key-value pair to the map. + * @param {*} key + * @param {*} value + * @example + * let map = new TreeMap(); + * map.set(1, 'A'); + */ + set(key, value) { + let n = new TreeNode(); + n.key = key; + n.value = value; + this.__t.insertOrReplace(n); + } + + /** + * Number of key-value pairs in the map. + * @returns {Number} + */ + get size() { + return this.__t.size(); + } + + /** + * Forward ES6 iterator for all values in ascending order of the keys. + * @returns {JsITerator} + * @example + * // iterate all values + * let map = new TreeMap([[1, 'A'], [2, 'B'], [3, 'C']]); + * for (let v of map.values()) { + * console.log(v); // 'A', 'B', 'C' + * } + * // iterate all values in reverse order + * let map = new TreeMap([[1, 'A'], [2, 'B'], [3, 'C']]); + * for (let v of map.values().backward()) { + * console.log(v); // 'C', 'B', 'A' + * } + */ + values() { + return this.__t.values(); + } + + /** + * Forward ES6 iterator for all key-value pairs in ascending order of the keys. The same as entries() method + * @returns {JsIterator} + * @example + * let map = new TreeMap([[1, 'A'], [2, 'B'], [3, 'C']]); + * for (let [key,value] of map) { + * console.log(`key: ${key}, value: ${value}`); + * } + */ + [Symbol.iterator]() { + return this.__t[Symbol.iterator](); + } + + /*====================================================== + * More methods + *======================================================*/ + /** + * ES6 reverse iterator for all key-value pairs in descending order of the keys. + * @returns {JsReverseIterator} + * @example + * let map = new TreeMap([[1, 'A'], [2, 'B'], [3, 'C']]); + * for (let [key,value] of map.backwards()) { + * console.log(`key: ${key}, value: ${value}`); + * } + */ + backward() { + return this.__t.backward(); + } + + /** + * Sets custom comparison function if key values are not of primitive types. + * Callback is a 3-way comparison function accepts two key values (lhs, rhs). It is expected to return + * +1 if the value of rhs is greater than lhs + * -1 if the value of rhs is less than lhs + * 0 if values are the same + */ + set compareFunc(func) { + this.clear(); + this.__t.compare = func; + } + + /*====================================================== + * STL-like methods + *======================================================*/ + + /** + * Forward iterator to the first element + * @returns {Iterator} + * @example + * let m = new TreeMap(); + * ... + * for (let it = m.begin(); !it.equals(m.end()); it.next()) { + * console.log(`key: ${it.key}, value: ${it.value}`); + * } + */ + begin() { + return this.__t.begin(); + } + + /** + * Forward iterator to the element following the last element + * @returns {Iterator} + * @example + * let m = new TreeMap(); + * ... + * for (let it = m.begin(); !it.equals(m.end()); it.next()) { + * console.log(`key: ${it.key}, value: ${it.value}`); + * } + */ + end() { + return this.__t.end(); + } + + /** + * Finds an element with key equivalent to the specified one. If such key does not exist end() iterator is returned. + * @param {*} key + * @returns {Iterator} + * @example + * let m = new TreeMap([[1, 'A'], [2, 'B'], [3, 'C']]); + * ... + * let it = m.find(1); + * if (!it.equals(m.end())) { + * console.log(`key: ${it.key}, value: ${it.value}`); // 1, 'A' + * } + */ + find(key) { + return this.__t.find(key); + } + + /** + * Adds key-value pair if such key does not exist in the map + * @param {*} key + * @param {*} value + * @returns {InsertionResult} - indicates whether a node was added and provides iterator to it. + * @example + * let m = new TreeMap(); + * let res = m.insertUnique(1, 'A'); + * if (res.wasInserted) { + * console.log(`Inserted ${res.iterator.value}`); // prints A + * } + * res = m.insertUnique(1, 'B') // this step has no effect on the map + * if (res.wasInserted) { + * console.log(`Inserted ${res.iterator.key}`); // not executed + * } + */ + insertUnique(key, value) { + let n = new TreeNode(); + n.key = key; + n.value = value; + return this.__t.insertUnique(n); + } + + /** + * Adds key-value pair if such key does not exist in the map. Replaces value if such key exists + * @param {*} key + * @param {*} value + * @returns {InsertionResult} - indicates whether a node was added and provides iterator to it. + * @example + * let m = new TreeMap(); + * let res = m.insertOrReplace(1, 'A'); + * if (res.wasInserted) { + * console.log(`Inserted ${res.iterator.value}`); // prints A + * } + * res = m.insertOrReplace(1, 'B') // replaces value on the existing node + * if (res.wasInserted) { + * console.log(`Inserted ${res.iterator.key}`); // prints B + * } + */ + insertOrReplace(key, value) { + let n = new TreeNode(); + n.key = key; + n.value = value; + return this.__t.insertOrReplace(n); + } + + /** + * Removes key-value pair for the specified iterator. + * @param {Iterator} iterator + * @example + * let map = new TreeMap([[1, 'A'], [2, 'B'], [3, 'C']]); + * let it = map.find(2); + * it.prev(); + * map.erase(it); // removes a node with key 1 + * console.log(map.toString()); // {2:B,3:C} + */ + erase(iterator) { + this.__t.erase(iterator.node); + } + + /** + * Iterator pointing to the first element that is not less than specified key. If no such element is found, see end() iterator is returned. + * @param {*} key + * @returns {Iterator} + * @example + * let m = new TreeMap(); + * ... // add key-value pairs., using numbers as keys + * // iterate through all key-value pairs with keys between 0 and 50 inclusive + * let from = m.lowerBound(0); + * let to = m.upperBound(50); + * let it = from; + * while (!it.equals(to)) { + * console.log(it.key); + * it.next(); + * } + * + * let m = new TreeMap(); + * ... // add key-value pairs., using numbers as keys + * // iterate through all key-value pairs with keys between 0 and 50 inclusive in reverse order + * let from = new ReverseIterator(m.upperBound(50)); + * let to = new ReverseIterator(m.lowerBound(0)); + * let it = from; + * while (!it.equals(to)) { + * console.log(it.key); + * it.next(); + * } + */ + lowerBound(key) { + return this.__t.lowerBound(key); + } + + /** + * Reverse iterator to the last element. + * @returns {ReverseIterator} + * @example + * let m = new TreeMap(); + * ... + * for (let it = m.rbegin(); !it.equals(m.rend()); it.next()) { + * console.log(`key: ${it.key}, value: ${it.value}`); + * } + */ + rbegin() { + return this.__t.rbegin(); + } + + /** + * Reverse iterator pointing to before the first element. + * @returns {ReverseIterator} + * @example + * let m = new TreeMap(); + * ... + * for (let it = m.rbegin(); !it.equals(m.rend()); it.next()) { + * console.log(`key: ${it.key}, value: ${it.value}`); + * } + */ + rend() { + return this.__t.rend(); + } + + /** + * Iterator pointing to the first element that is greater than key. If no such element is found end() iterator is returned. + * @param {*} key + * @returns {Iterator} + * @example + * let m = new TreeMap(); + * ... // add key-value pairs., using numbers as keys + * // iterate through all key-value pairs with keys between 0 and 50 inclusive + * let from = m.lowerBound(0); + * let to = m.upperBound(50); + * let it = from; + * while (!it.equals(to)) { + * console.log(it.key); + * it.next(); + * } + * + * let m = new TreeMap(); + * ... // add key-value pairs., using numbers as keys + * // iterate through all key-value pairs with keys between 0 and 50 inclusive in reverse order + * let from = new ReverseIterator(m.upperBound(50)); + * let to = new ReverseIterator(m.lowerBound(0)); + * let it = from; + * while (!it.equals(to)) { + * console.log(it.key); + * it.next(); + * } + */ + upperBound(key) { + return this.__t.upperBound(key); + } + + /** + * @returns first key/value pair of the container, or undefined if container is empty + * @example + * let m = new TreeMap([[1, 'A'], [2, 'B'], [3, 'C']]); + * let first = m.first(); + * if (first) { + * let key = first[0]; // 1 + * let value = first[1]; // 'A' + * } + */ + first() { + return this.__t.first(); + } + + /** + * @returns last key/value pair of the container, or undefined if container is empty + * @example + * let m = new TreeMap([[1, 'A'], [2, 'B'], [3, 'C']]); + * let last = m.last(); + * if (last) { + * let key = last[0]; // 3 + * let value = last[1]; // 'C' + * } + */ + last() { + return this.__t.last(); + } + + /** + * Serializes contents of the map in the form {key1:value1,key2:value2,...} + * @returns {String} + */ + toString() { + return this.__t.toString(); + } +} + +module.exports = { + TreeMap: TreeMap, +}; + +/***/ }), +/* 8 */ +/***/ (function(module, exports) { + +/** + * An instance of this class reports whether insert operation was successful. + * if a node was added, or an existing one replaced then an iterator is provided. Otherwise the value of iterator is undefined + */ +class InsertionResult { + /** + * Default constructor + * @param {Boolean} wasAdded + * @param {Boolean} wasReplaced + * @param {Iterator} iterator only provided if the node was added, or replaced + */ + constructor(wasAdded, wasReplaced, iterator) { + /** + * Boolean flag indicating whether an element was added + */ + this.wasAdded = wasAdded; + /** + * Boolean flag indicating whether an existing node was updated + */ + this.wasReplaced = wasReplaced; + /** + * {Iterator} instance pointing to the newly added node + */ + this.iterator = iterator; + } +} + +module.exports = { + InsertionResult: InsertionResult +}; + +/***/ }), +/* 9 */ +/***/ (function(module, exports, __nested_webpack_require_63461__) { + +/** An implementation of red-black tree */ +const {Tree} = __nested_webpack_require_63461__(2); +/** Classes that regulate whether tree nodes hold keys only, or key-value pairs */ +const {KeyValuePolicy} = __nested_webpack_require_63461__(1); +/** Node for a red-black tree */ +const {TreeNode} = __nested_webpack_require_63461__(0); + +/** + * TreeMultiMap is an associative container that stores elements formed by + * a combination of a key value and a mapped value, following a specific order, + * and where multiple elements can have equivalent keys. + * + * In a TreeMultiMap, the key values are generally used to sort and uniquely + * identify the elements, while the mapped values store the content + * associated to this key. The types of key and mapped value may differ. + * + * ## Container properties + * * **Associative** - Elements in associative containers are referenced + * by their key and not by their absolute position in the container. + * * **Ordered** - The elements in the container follow a strict order + * at all times. All inserted elements are given a position in this order. + * * **Map** - Each element associates a key to a mapped value. Keys are meant + * to identify the elements whose main content is the mapped value. + * * **Multiple equivalent keys** - Multiple elements in the container + * can have equivalent keys. + * + * @example + * let map = new TreeMultiMap(); + * // add few values + * map.set(1, 'a'); + * map.set(2, 'b'); + * map.set(2, 'c'); + * // find a value by key + * let v = map.get(1); // << 'a' + * find all values for a given key + * // print all key-value pairs + * let from = map.lowerBound(2); + * let to = map.upperBound(2); + * let it = from; + * while (!it.equals(to)) { + * console.log(it.key); + * it.next(); + * } + */ +class TreeMultiMap { + /*====================================================== + * Methods of ES6 Map + *======================================================*/ + + /** + * Creates an empty, or a pre-initialized map. + * @param {*} [iterable] Another iterable object whose key-value pairs are added into the newly created map. + * @example + * // Create an empty map + * let map1 = new TreeMultiMap(); + * // Create and initialize map + * let map2 = new TreeMultiMap([[1, 'A'], [2, 'B'], [3, 'C']]); + */ + constructor(iterable) { + /** Internal tree */ + this.__t = new Tree(); + this.__t.valuePolicy = new KeyValuePolicy(); + if ((iterable !== undefined) + && (iterable !== null)) { + if (iterable[Symbol.iterator] !== undefined) { + // copy contents + for (let [k, v] of iterable) { + this.set(k, v); + } + } + else { + throw new Error('TreeMultiMap constructor accepts only iterable objects'); + } + } + } + + /** + * String tag of this class + * @returns {String} + * @example + * Object.prototype.toString.call(new TreeMultiMap()); // "[object TreeMultiMap]" + */ + get [Symbol.toStringTag]() { + return 'TreeMultiMap'; + } + + /** + * Allows to create programmatically an instance of the same class + * @returns constructor object for this class. + * @example + * let map = new TreeMultiMap(); + * let constrFunc = Object.getPrototypeOf(map).constructor[Symbol.species]; + * let map2 = new constrFunc(); + */ + static get [Symbol.species]() { + return TreeMultiMap; + } + + /** + * Removes all key-value pairs. + * @example + * let map = new TreeMultiMap([[1, 'A'], [2, 'B'], [3, 'C']]); + * map.clear(); + * console.log(map.size); // 0 + */ + clear() { + this.__t.clear(); + } + + /** + * Removes key-value pair with the specified key if such entry exists. Does nothing otherwise. + * @example + * let map = new TreeMultiMap([[1, 'A'], [2, 'B'], [3, 'C']]); + * map.delete(2); + * console.log(map.toString()); // {1:A,3:C} + */ + delete(key) { + let it = this.__t.find(key); + if (!it.equals(this.__t.end())) { + this.__t.erase(it.node); + } + } + + /** + * Forward ES6 iterator for all key-value pairs in ascending order of the keys. + * @returns {JsIterator} + * @example + * let map = new TreeMultiMap([[1, 'A'], [2, 'B'], [3, 'C']]); + * for (let [key,value] of map.entries()) { + * console.log(`key: ${key}, value: ${value}`); + * } + */ + entries() { + return this.__t.entries(); + } + + /** + * Iterates all key-value pairs using a callback in ascending order of the keys. + * Note that ES6 specifies the order of key value parameters in the callback differently from for-of loop. + * @example + * let map = new TreeMultiMap([[1, 'A'], [2, 'B'], [3, 'C']]); + * map.forEach(function(value, key, container) { + * console.log(`key: ${key}, value: ${value}`); + * }); + */ + forEach(callback) { + for (let [k, v] of this.__t) { + callback(v, k, this); + } + } + + /** + * Finds value associated with the specified key. If specified key does not exist then undefined is returned. + * @returns {*} + * @param {*} key a value of any type that can be compared with a key + * @example + * let map = new TreeMultiMap([[1, 'A'], [2, 'B'], [3, 'C']]); + * let v = map.get(3); // 'C' + * * let v = map.get(4); // returns undefined + */ + get(key) { + let it = this.__t.find(key); + if (!it.equals(this.__t.end())) { + return it.value; + } + else { + return undefined; + } + } + + /** + * A boolean indicator whether map contains a key-value pair with the specified key + * @returns {Boolean} + * @param {*} key a value of any type that can be compared with a key + * @example + * let map = new TreeMultiMap([[1, 'A'], [2, 'B'], [3, 'C']]); + * let b = map.get(3); // true + */ + has(key) { + let it = this.__t.find(key); + if (!it.equals(this.__t.end())) { + return true; + } + else { + return false; + } + } + + /** + * Forward ES6 iterator for all keys in ascending order of the keys. + * @returns {JsIterator} + * @example + * // iterate all keys + * let map = new TreeMultiMap([[1, 'A'], [2, 'B'], [3, 'C']]); + * for (let k of map.keys()) { + * console.log(k); // 1, 2, 3 + * } + * // iterate all keys in reverse order + * let map = new TreeMultiMap([[1, 'A'], [2, 'B'], [3, 'C']]); + * for (let k of map.keys().backward()) { + * console.log(k); // 3, 2, 1 + * } + */ + keys() { + return this.__t.keys(); + } + + /** + * Adds a key-value pair to the map. Multiple key-value pairs with the same key are allowed in TreeMultiMap. + * @param {*} key + * @param {*} value + * @example + * let map = new TreeMultiMap(); + * map.set(1, 'A'); + * map.set(1, 'B'); + * map.set(2, 'C'); + * for (let k of map.values()) { + * console.log(k); // A, B, C + * } + */ + set(key, value) { + let n = new TreeNode(); + n.key = key; + n.value = value; + this.__t.insertMulti(n); + } + + /** + * Number of key-value pairs in the map. + * @returns {Number} + */ + get size() { + return this.__t.size(); + } + + /** + * Forward ES6 iterator for all values in ascending order of the keys. + * @returns {JsITerator} + * @example + * // iterate all values + * let map = new TreeMultiMap([[1, 'A'], [2, 'B'], [3, 'C']]); + * for (let v of map.values()) { + * console.log(v); // 'A', 'B', 'C' + * } + * // iterate all values in reverse order + * let map = new TreeMultiMap([[1, 'A'], [2, 'B'], [3, 'C']]); + * for (let v of map.values().backward()) { + * console.log(v); // 'C', 'B', 'A' + * } + */ + values() { + return this.__t.values(); + } + + /** + * Forward ES6 iterator for all key-value pairs in ascending order of the keys. The same as entries() method + * @returns {JsIterator} + * @example + * let map = new TreeMultiMap([[1, 'A'], [2, 'B'], [3, 'C']]); + * for (let [key,value] of map) { + * console.log(`key: ${key}, value: ${value}`); + * } + */ + [Symbol.iterator]() { + return this.__t[Symbol.iterator](); + } + + /*====================================================== + * More methods + *======================================================*/ + /** + * ES6 reverse iterator for all key-value pairs in descending order of the keys. + * @returns {JsReverseIterator} + * @example + * let map = new TreeMultiMap([[1, 'A'], [2, 'B'], [3, 'C']]); + * for (let [key,value] of map.backwards()) { + * console.log(`key: ${key}, value: ${value}`); + * } + */ + backward() { + return this.__t.backward(); + } + + /** + * Sets custom comparison function if key values are not of primitive types. + * Callback is a 3-way comparison function accepts two key values (lhs, rhs). It is expected to return + * +1 if the value of rhs is greater than lhs + * -1 if the value of rhs is less than lhs + * 0 if values are the same + */ + set compareFunc(func) { + this.clear(); + this.__t.compare = func; + } + + /*====================================================== + * STL-like methods + *======================================================*/ + + /** + * Forward iterator to the first element + * @returns {Iterator} + * @example + * let m = new TreeMultiMap(); + * ... + * for (let it = m.begin(); !it.equals(m.end()); it.next()) { + * console.log(`key: ${it.key}, value: ${it.value}`); + * } + */ + begin() { + return this.__t.begin(); + } + + /** + * Forward iterator to the element following the last element + * @returns {Iterator} + * @example + * let m = new TreeMultiMap(); + * ... + * for (let it = m.begin(); !it.equals(m.end()); it.next()) { + * console.log(`key: ${it.key}, value: ${it.value}`); + * } + */ + end() { + return this.__t.end(); + } + + /** + * Finds an element with key equivalent to the specified one. If such key does not exist end() iterator is returned. + * @param {*} key + * @returns {Iterator} + * @example + * let m = new TreeMultiMap([[1, 'A'], [2, 'B'], [3, 'C']]); + * ... + * let it = m.find(1); + * if (!it.equals(m.end())) { + * console.log(`key: ${it.key}, value: ${it.value}`); // 1, 'A' + * } + */ + find(key) { + return this.__t.find(key); + } + + /** + * Adds key-value pair if such key does not exist in the map + * @param {*} key + * @param {*} value + * @returns {InsertionResult} - indicates whether a node was added and provides iterator to it. + * @example + * let m = new TreeMultiMap(); + * let res = m.insertUnique(1, 'A'); + * if (res.wasInserted) { + * console.log(`Inserted ${res.iterator.value}`); // prints A + * } + * res = m.insertUnique(1, 'B') // this step has no effect on the map + * if (res.wasInserted) { + * console.log(`Inserted ${res.iterator.key}`); // not executed + * } + */ + insertUnique(key, value) { + let n = new TreeNode(); + n.key = key; + n.value = value; + return this.__t.insertUnique(n); + } + + /** + * Adds key-value pair if such key does not exist in the map. Replaces value if such key exists + * @param {*} key + * @param {*} value + * @returns {InsertionResult} - indicates whether a node was added and provides iterator to it. + * @example + * let m = new TreeMultiMap(); + * let res = m.insertOrReplace(1, 'A'); + * if (res.wasInserted) { + * console.log(`Inserted ${res.iterator.value}`); // prints A + * } + * res = m.insertOrReplace(1, 'B') // replaces value on the existing node + * if (res.wasInserted) { + * console.log(`Inserted ${res.iterator.key}`); // prints B + * } + */ + insertOrReplace(key, value) { + let n = new TreeNode(); + n.key = key; + n.value = value; + return this.__t.insertOrReplace(n); + } + + /** + * Adds key-value pair. If such key already exists in the map then adds another node with the same key and a new value. + * @param {*} key + * @param {*} value + * @returns {InsertionResult} - indicates whether a node was added and provides iterator to it. + * @example + * let m = new TreeMultiMap(); + * let res = m.insertMulti(1, 'A'); + * if (res.wasInserted) { + * console.log(`Inserted ${res.iterator.value}`); // prints A + * } + * res = m.insertMulti(1, 'B') // adds a new node + * if (res.wasInserted) { + * console.log(`Inserted ${res.iterator.value}`); // prints B + * it.prev(); + * console.log(`Previously inserted ${res.iterator.value}`); // prints A + * } + */ + insertMulti(key, value) { + let n = new TreeNode(); + n.key = key; + n.value = value; + return this.__t.insertMulti(n); + } + + /** + * Removes key-value pair for the specified iterator. + * @param {Iterator} iterator + * @example + * let map = new TreeMultiMap([[1, 'A'], [2, 'B'], [3, 'C']]); + * let it = map.find(2); + * it.prev(); + * map.erase(it); // removes a node with key 1 + * console.log(map.toString()); // {2:B,3:C} + */ + erase(iterator) { + this.__t.erase(iterator.node); + } + + /** + * Iterator pointing to the first element that is not less than specified key. If no such element is found, see end() iterator is returned. + * @param {*} key + * @returns {Iterator} + * @example + * let m = new TreeMultiMap(); + * ... // add key-value pairs., using numbers as keys + * // iterate through all key-value pairs with keys between 0 and 50 inclusive + * let from = m.lowerBound(0); + * let to = m.upperBound(50); + * let it = from; + * while (!it.equals(to)) { + * console.log(it.key); + * it.next(); + * } + * + * let m = new TreeMultiMap(); + * ... // add key-value pairs., using numbers as keys + * // iterate through all key-value pairs with keys between 0 and 50 inclusive in reverse order + * let from = new ReverseIterator(m.upperBound(50)); + * let to = new ReverseIterator(m.lowerBound(0)); + * let it = from; + * while (!it.equals(to)) { + * console.log(it.key); + * it.next(); + * } + */ + lowerBound(key) { + return this.__t.lowerBound(key); + } + + /** + * Reverse iterator to the last element. + * @returns {ReverseIterator} + * @example + * let m = new TreeMultiMap(); + * ... + * for (let it = m.rbegin(); !it.equals(m.rend()); it.next()) { + * console.log(`key: ${it.key}, value: ${it.value}`); + * } + */ + rbegin() { + return this.__t.rbegin(); + } + + /** + * Reverse iterator pointing to before the first element. + * @returns {ReverseIterator} + * @example + * let m = new TreeMultiMap(); + * ... + * for (let it = m.rbegin(); !it.equals(m.rend()); it.next()) { + * console.log(`key: ${it.key}, value: ${it.value}`); + * } + */ + rend() { + return this.__t.rend(); + } + + /** + * Iterator pointing to the first element that is greater than key. If no such element is found end() iterator is returned. + * @param {*} key + * @returns {Iterator} + * @example + * let m = new TreeMultiMap(); + * ... // add key-value pairs., using numbers as keys + * // iterate through all key-value pairs with keys between 0 and 50 inclusive + * let from = m.lowerBound(0); + * let to = m.upperBound(50); + * let it = from; + * while (!it.equals(to)) { + * console.log(it.key); + * it.next(); + * } + * + * let m = new TreeMultiMap(); + * ... // add key-value pairs., using numbers as keys + * // iterate through all key-value pairs with keys between 0 and 50 inclusive in reverse order + * let from = new ReverseIterator(m.upperBound(50)); + * let to = new ReverseIterator(m.lowerBound(0)); + * let it = from; + * while (!it.equals(to)) { + * console.log(it.key); + * it.next(); + * } + */ + upperBound(key) { + return this.__t.upperBound(key); + } + + /** + * @returns first key/value pair of the container, or undefined if container is empty + * @example + * let m = new TreeMultiMap([[1, 'A'], [2, 'B'], [3, 'C']]); + * let first = m.first(); + * if (first) { + * let key = first[0]; // 1 + * let value = first[1]; // 'A' + * } + */ + first() { + return this.__t.first(); + } + + /** + * @returns last key/value pair of the container, or undefined if container is empty + * @example + * let m = new TreeMultiMap([[1, 'A'], [2, 'B'], [3, 'C']]); + * let last = m.last(); + * if (last) { + * let key = last[0]; // 3 + * let value = last[1]; // 'C' + * } + */ + last() { + return this.__t.last(); + } + + /** + * Serializes contents of the map in the form {key1:value1,key2:value2,...} + * @returns {String} + */ + toString() { + return this.__t.toString(); + } +} + +module.exports = { + TreeMultiMap: TreeMultiMap, +}; + +/***/ }), +/* 10 */ +/***/ (function(module, exports, __nested_webpack_require_81431__) { + +/** An implementation of red-black tree */ +const {Tree} = __nested_webpack_require_81431__(2); +/** Classes that regulate whether tree nodes hold keys only, or key-value pairs */ +const {KeyOnlyPolicy} = __nested_webpack_require_81431__(1); +/** Node for a red-black tree */ +const {TreeNode} = __nested_webpack_require_81431__(0); + +/** + * TreeSet is a container that stores unique elements following a specific order. + * + * In a TreeSet, the value of an element also identifies it (the value is itself the key), + * and each value must be unique. The value of the elements in a TreeSet cannot be modified + * once in the container (the elements are immutable), but they can be inserted or removed + * from the container. + * + * ## Container properties + * * **Associative** - Elements in associative containers are referenced by their key and + * not by their absolute position in the container.</li> + * * **Ordered** - The elements in the container follow a strict order at all times. + * All inserted elements are given a position in this order.</li> + * * **Set** - The value of an element is also the key used to identify it.</li> + * * **Unique keys** - No two elements in the container can have equivalent keys.</li> + * + * + * @example + * let set = new TreeSet(); + * // add few values + * set.add(1); + * set.add(2); + * // check whether key exists + * let flag = set.has(1); // << true + * // print all keys + * for (let key of set) { + * console.log(`key: ${key}`); + * } + */ +class TreeSet { + /*====================================================== + * Methods of ES6 Set + *======================================================*/ + + /** + * Creates an empty, or a pre-initialized set. + * @param {*} [iterable] Another iterable object whose values are added into the newly created set. + * @example + * // Create an empty set + * let set = new TreeSet(); + * // Create and initialize set + * let set2 = new TreeSet([1, 2, 3]); + */ + constructor(iterable) { + /** Internal tree */ + this.__t = new Tree(); + this.__t.valuePolicy = new KeyOnlyPolicy(); + if ((iterable !== undefined) + && (iterable !== null)) { + if (iterable[Symbol.iterator] !== undefined) { + // copy contents + for (let k of iterable) { + this.add(k); + } + } + else { + throw new Error('TreeSet constructor accepts only iterable objects'); + } + } + } + + /** + * String tag of this class + * @returns {String} + * @example + * Object.prototype.toString.call(new TreeSet()); // "[object TreeSet]" + */ + get [Symbol.toStringTag]() { + return 'TreeSet'; + } + + /** + * Allows to create programmatically an instance of the same class + * @returns constructor object for this class. + * @example + * let set = new TreeSet(); + * let constrFunc = Object.getPrototypeOf(set).constructor[Symbol.species]; + * let set2 = new constrFunc(); + */ + static get [Symbol.species]() { + return TreeSet; + } + + /** + * Removes all key-value pairs. + * @example + * let set = new TreeSet([1, 2, 3]); + * set.clear(); + * console.log(set.size); // 0 + */ + clear() { + this.__t.clear(); + } + + /** + * Removes key-value pair with the specified key if such entry exists. Does nothing otherwise. + * @example + * let set = new TreeSet([1, 2, 3]); + * set.delete(2); + * console.log(set.toString()); // {1,3} + */ + delete(key) { + let it = this.__t.find(key); + if (!it.equals(this.__t.end())) { + this.__t.erase(it.node); + } + } + + /** + * Forward ES6 iterator for all values in ascending order. + * @returns {JsIterator} + * @example + * let set = new TreeSet([1, 2, 3]); + * for (let key of set.entries()) { + * console.log(`key: ${key}`); + * } + */ + entries() { + return this.__t.entries(); + } + + /** + * Iterates all values using a callback in ascending order. + * Note that ES6 specifies the order of key parameters in the callback differently from for-of loop. + * @example + * let set = new TreeSet([1, 2, 3]); + * set.forEach(function(value, key, container) { + * // value is the same as key + * console.log(`key: ${key}, value: ${value}`); + * }); + */ + forEach(callback) { + for (let k of this.__t) { + callback(k, k, this); + } + } + + /** + * A boolean indicator whether set contains the specified key. + * @returns {Boolean} + * @param {*} key a value of any type that can be compared with a key + * @example + * let set = new TreeSet([1, 2, 3]); + * let b = set.get(3); // true + * b = set.get(4); // false + */ + has(key) { + let it = this.__t.find(key); + if (!it.equals(this.__t.end())) { + return true; + } + else { + return false; + } + } + + /** + * Forward ES6 iterator for all keys in ascending order. + * @returns {JsIterator} + * @example + * // iterate all keys + * let set = new TreeSet([1, 2, 3]); + * for (let k of set.keys()) { + * console.log(k); // 1, 2, 3 + * } + * // iterate all keys in reverse order + * let set = new TreeSet([1, 2, 3]); + * for (let k of set.keys().backward()) { + * console.log(k); // 3, 2, 1 + * } + */ + keys() { + return this.__t.keys(); + } + + /** + * Adds a key to the set, unless the key already exists. + * @param {*} key + * @example + * let set = new TreeSet(); + * set.add(1); + */ + add(key) { + let n = new TreeNode(); + n.key = key; + this.__t.insertUnique(n); + } + + /** + * Number of keys in the set. + * @returns {Number} + */ + get size() { + return this.__t.size(); + } + + /** + * Forward ES6 iterator for all keys in ascending order. It is the same as keys() method + * @returns {JsITerator} + * @example + * // iterate all values + * let set = new TreeSet([1, 2, 3]); + * for (let v of set.values()) { + * console.log(v); // '1', '2', '3' + * } + * // iterate all values in reverse order + * let set = new TreeSet([1, 2, 3]); + * for (let v of set.values().backward()) { + * console.log(v); // '3', '2', '1' + * } + */ + values() { + return this.__t.keys(); + } + + /** + * Forward ES6 iterator for all keys in ascending order. The same as entries() method + * @returns {JsIterator} + * @example + * let set = new TreeSet([1, 2, 3]); + * for (let key of set) { + * console.log(`key: ${key}, value: ${value}`); + * } + */ + [Symbol.iterator]() { + return this.__t[Symbol.iterator](); + } + + /*====================================================== + * More methods + *======================================================*/ + /** + * ES6 reverse iterator for all keys in descending order. + * @returns {JsReverseIterator} + * @example + * let set = new TreeSet([1, 2, 3]); + * for (let key of set.backwards()) { + * console.log(`key: ${key}`); + * } + */ + backward() { + return this.__t.backward(); + } + + /** + * Sets custom comparison function if key values are not of primitive types. + * Callback is a 3-way comparison function accepts two key values (lhs, rhs). It is expected to return + * +1 if the value of rhs is greater than lhs + * -1 if the value of rhs is less than lhs + * 0 if values are the same + */ + set compareFunc(func) { + this.clear(); + this.__t.compare = func; + } + + /*====================================================== + * STL-like methods + *======================================================*/ + + /** + * Forward iterator to the first element + * @returns {Iterator} + * @example + * let set = new TreeSet(); + * ... + * for (let it = set.begin(); !it.equals(set.end()); it.next()) { + * console.log(`key: ${it.key}`); + * } + */ + begin() { + return this.__t.begin(); + } + + /** + * Forward iterator to the element following the last element + * @returns {Iterator} + * @example + * let set = new TreeSet(); + * ... + * for (let it = set.begin(); !it.equals(set.end()); it.next()) { + * console.log(`key: ${it.key}`); + * } + */ + end() { + return this.__t.end(); + } + + /** + * Finds an element with key equivalent to the specified one. If such key does not exist end() iterator is returned. + * @param {*} key + * @returns {Iterator} + * @example + * let set = new TreeSet([1, 2, 3]); + * ... + * let it = set.find(1); + * if (!it.equals(set.end())) { + * console.log(`Found key: ${it.key}`); // 1 + * } + */ + find(key) { + return this.__t.find(key); + } + + /** + * Adds a key if it doesn't exist + * @param {*} key + * @returns {InsertionResult} - indicates whether a node was added and provides iterator to it. + * @example + * let set = new TreeSet(); + * let res = set.insertUnique(1); + * if (res.wasInserted) { + * console.log(`Inserted ${res.iterator.key}`); // prints 1 + * } + * res = set.insertUnique(1); // this step has no effect on the set + * if (res.wasInserted) { + * console.log(`Inserted ${res.iterator.key}`); // not executed + * } + */ + insertUnique(key) { + let n = new TreeNode(); + n.key = key; + return this.__t.insertUnique(n); + } + + /** + * Adds key-value pair if such key does not exist in the map. Replaces value if such key exists + * @param {*} key + * @returns {InsertionResult} - indicates whether a node was added and provides iterator to it. + * @example + * let set = new TreeSet(); + * let res = set.insertOrReplace(1); + * if (res.wasInserted) { + * console.log(`Inserted ${res.iterator.key}`); // prints 1 + * } + * res = set.insertOrReplace(1) // returns iterator to the previously added node + * if (res.wasInserted) { + * console.log(`Inserted ${res.iterator.key}`); // prints 1 + * } + */ + insertOrReplace(key) { + let n = new TreeNode(); + n.key = key; + return this.__t.insertOrReplace(n); + } + + /** + * Removes value for the specified iterator. + * @param {Iterator} iterator + * @example + * let set = new TreeSet([1,2,3]); + * let it = set.find(2); + * it.prev(); + * set.erase(it); // removes a node with key 1 + * console.log(set.toString()); // {2,3} + */ + erase(iterator) { + this.__t.erase(iterator.node); + } + + /** + * Iterator pointing to the first element that is not less than specified key. If no such element is found, see end() iterator is returned. + * @param {*} key + * @returns {Iterator} + * @example + * let set = new TreeSet(); + * ... // add key-value pairs., using numbers as keys + * // iterate through all key-value pairs with keys between 0 and 50 inclusive + * let from = set.lowerBound(0); + * let to = set.upperBound(50); + * let it = from; + * while (!it.equals(to)) { + * console.log(it.key); + * it.next(); + * } + * + * let set = new TreeSet(); + * ... // add key-value pairs., using numbers as keys + * // iterate through all key-value pairs with keys between 0 and 50 inclusive in reverse order + * let from = new ReverseIterator(set.upperBound(50)); + * let to = new ReverseIterator(set.lowerBound(0)); + * let it = from; + * while (!it.equals(to)) { + * console.log(it.key); + * it.next(); + * } + */ + lowerBound(key) { + return this.__t.lowerBound(key); + } + + /** + * Reverse iterator to the last element. + * @returns {ReverseIterator} + * @example + * let set = new TreeSet(); + * ... + * for (let it = set.rbegin(); !it.equals(set.rend()); it.next()) { + * console.log(`key: ${it.key}`); + * } + */ + rbegin() { + return this.__t.rbegin(); + } + + /** + * Reverse iterator pointing to before the first element. + * @returns {ReverseIterator} + * @example + * let set = new TreeSet(); + * ... + * for (let it = set.rbegin(); !it.equals(set.rend()); it.next()) { + * console.log(`key: ${it.key}`); + * } + */ + rend() { + return this.__t.rend(); + } + + /** + * Iterator pointing to the first element that is greater than key. If no such element is found end() iterator is returned. + * @param {*} key + * @returns {Iterator} + * @example + * let set = new TreeSet(); + * ... // add key-value pairs., using numbers as keys + * // iterate through all key-value pairs with keys between 0 and 50 inclusive + * let from = set.lowerBound(0); + * let to = set.upperBound(50); + * let it = from; + * while (!it.equals(to)) { + * console.log(it.key); + * it.next(); + * } + * + * let set = new TreeSet(); + * ... // add key-value pairs., using numbers as keys + * // iterate through all key-value pairs with keys between 0 and 50 inclusive in reverse order + * let from = new ReverseIterator(set.upperBound(50)); + * let to = new ReverseIterator(set.lowerBound(0)); + * let it = from; + * while (!it.equals(to)) { + * console.log(it.key); + * it.next(); + * } + */ + upperBound(key) { + return this.__t.upperBound(key); + } + + /** + * @returns first element of the container, or undefined if container is empty + * @example + * let set = new TreeSet([1, 2, 3]); + * let first = set.first(); // 1 + */ + first() { + return this.__t.first(); + } + + /** + * @returns last element of the container, or undefined if container is empty + * @example + * let set = new TreeSet([1, 2, 3]); + * let last = set.last(); // 3 + */ + last() { + return this.__t.last(); + } + + /** + * Serializes contents of the set in the form {key1,key2,...} + * @returns {String} + */ + toString() { + return this.__t.toString(); + } +} + +module.exports = { + TreeSet: TreeSet, +}; + +/***/ }), +/* 11 */ +/***/ (function(module, exports, __nested_webpack_require_96249__) { + +/** An implementation of red-black tree */ +const {Tree} = __nested_webpack_require_96249__(2); +/** Classes that regulate whether tree nodes hold keys only, or key-value pairs */ +const {KeyOnlyPolicy} = __nested_webpack_require_96249__(1); +/** Node for a red-black tree */ +const {TreeNode} = __nested_webpack_require_96249__(0); + +/** + * TreeMultiSet is a container that stores elements following a specific order, + * and where multiple elements can have equivalent values. + * + * In a TreeMultiSet, the value of an element also identifies it + * (the value is itself the key). The value of the elements in a multiset + * cannot be modified once in the container (the elements are always immutable), + * but they can be inserted or removed from the container. + * + * ## Container properties + * * **Associative** - Elements in associative containers are referenced + * by their key and not by their absolute position in the container. + * * **Ordered** - The elements in the container follow a strict order + * at all times. All inserted elements are given a position in this order. + * * **Set** - The value of an element is also the key used to identify it. + * * **Multiple equivalent keys** - Multiple elements in the container + * can have equivalent keys. + * + * @example + * let set = new TreeMultiSet(); + * // add few values + * set.add(1); + * set.add(2); + * set.add(2); + * // check whether key exists + * let flag = set.has(1); // << true + * // print all keys + * for (let key of set) { + * console.log(`key: ${key}`); // 1, 2, 2 + * } + */ +class TreeMultiSet { + /*====================================================== + * Methods of ES6 Set + *======================================================*/ + + /** + * Creates an empty, or a pre-initialized set. + * @param {*} [iterable] Another iterable object whose values are added into the newly created set. + * @example + * // Create an empty set + * let set = new TreeMultiSet(); + * // Create and initialize set + * let set2 = new TreeMultiSet([1, 2, 3]); + */ + constructor(iterable) { + /** Internal tree */ + this.__t = new Tree(); + this.__t.valuePolicy = new KeyOnlyPolicy(); + if ((iterable !== undefined) + && (iterable !== null)) { + if (iterable[Symbol.iterator] !== undefined) { + // copy contents + for (let k of iterable) { + this.add(k); + } + } + else { + throw new Error('TreeMultiSet constructor accepts only iterable objects'); + } + } + } + + /** + * String tag of this class + * @returns {String} + * @example + * Object.prototype.toString.call(new TreeMultiSet()); // "[object TreeMultiSet]" + */ + get [Symbol.toStringTag]() { + return 'TreeMultiSet'; + } + + /** + * Allows to create programmatically an instance of the same class + * @returns constructor object for this class. + * @example + * let set = new TreeMultiSet(); + * let constrFunc = Object.getPrototypeOf(set).constructor[Symbol.species]; + * let set2 = new constrFunc(); + */ + static get [Symbol.species]() { + return TreeMultiSet; + } + + /** + * Removes all key-value pairs. + * @example + * let set = new TreeMultiSet([1, 2, 3]); + * set.clear(); + * console.log(set.size); // 0 + */ + clear() { + this.__t.clear(); + } + + /** + * Removes key-value pair with the specified key if such entry exists. Does nothing otherwise. + * @example + * let set = new TreeMultiSet([1, 2, 2, 3]); + * set.delete(2); + * console.log(set.toString()); // {1,2,3} + * set.delete(2); / remove the second copy of the key + * console.log(set.toString()); // {1,3} + */ + delete(key) { + let it = this.__t.find(key); + if (!it.equals(this.__t.end())) { + this.__t.erase(it.node); + } + } + + /** + * Forward ES6 iterator for all values in ascending order. + * @returns {JsIterator} + * @example + * let set = new TreeMultiSet([1, 2, 3]); + * for (let key of set.entries()) { + * console.log(`key: ${key}`); + * } + */ + entries() { + return this.__t.entries(); + } + + /** + * Iterates all values using a callback in ascending order. + * Note that ES6 specifies the order of key parameters in the callback differently from for-of loop. + * @example + * let set = new TreeMultiSet([1, 2, 3]); + * set.forEach(function(value, key, container) { + * // value is the same as key + * console.log(`key: ${key}, value: ${value}`); + * }); + */ + forEach(callback) { + for (let k of this.__t) { + callback(k, k, this); + } + } + + /** + * A boolean indicator whether set contains the specified key. + * @returns {Boolean} + * @param {*} key a value of any type that can be compared with a key + * @example + * let set = new TreeMultiSet([1, 2, 3]); + * let b = set.get(3); // true + * b = set.get(4); // false + */ + has(key) { + let it = this.__t.find(key); + if (!it.equals(this.__t.end())) { + return true; + } + else { + return false; + } + } + + /** + * Forward ES6 iterator for all keys in ascending order. + * @returns {JsIterator} + * @example + * // iterate all keys + * let set = new TreeMultiSet([1, 2, 3]); + * for (let k of set.keys()) { + * console.log(k); // 1, 2, 3 + * } + * // iterate all keys in reverse order + * let set = new TreeMultiSet([1, 2, 3]); + * for (let k of set.keys().backward()) { + * console.log(k); // 3, 2, 1 + * } + */ + keys() { + return this.__t.keys(); + } + + /** + * Adds a key to the set. If the key already exists then another entry with the same value is added. + * @param {*} key + * @example + * let set = new TreeMultiSet(); + * set.add(1); + * set.add(1); + * set.add(2); + * // print all keys + * for (let key of set) { + * console.log(`key: ${key}`); // 1, 1, 2 + * } + */ + add(key) { + let n = new TreeNode(); + n.key = key; + this.__t.insertMulti(n); + } + + /** + * Number of keys in the set. + * @returns {Number} + */ + get size() { + return this.__t.size(); + } + + /** + * Forward ES6 iterator for all keys in ascending order. It is the same as keys() method + * @returns {JsITerator} + * @example + * // iterate all values + * let set = new TreeMultiSet([1, 2, 3]); + * for (let v of set.values()) { + * console.log(v); // '1', '2', '3' + * } + * // iterate all values in reverse order + * let set = new TreeMultiSet([1, 2, 3]); + * for (let v of set.values().backward()) { + * console.log(v); // '3', '2', '1' + * } + */ + values() { + return this.__t.keys(); + } + + /** + * Forward ES6 iterator for all keys in ascending order. The same as entries() method + * @returns {JsIterator} + * @example + * let set = new TreeMultiSet([1, 2, 3]); + * for (let key of set) { + * console.log(`key: ${key}, value: ${value}`); + * } + */ + [Symbol.iterator]() { + return this.__t[Symbol.iterator](); + } + + /*====================================================== + * More methods + *======================================================*/ + /** + * ES6 reverse iterator for all keys in descending order. + * @returns {JsReverseIterator} + * @example + * let set = new TreeMultiSet([1, 2, 3]); + * for (let key of set.backwards()) { + * console.log(`key: ${key}`); + * } + */ + backward() { + return this.__t.backward(); + } + + /** + * Sets custom comparison function if key values are not of primitive types. + * Callback is a 3-way comparison function accepts two key values (lhs, rhs). It is expected to return + * +1 if the value of rhs is greater than lhs + * -1 if the value of rhs is less than lhs + * 0 if values are the same + */ + set compareFunc(func) { + this.clear(); + this.__t.compare = func; + } + + /*====================================================== + * STL-like methods + *======================================================*/ + + /** + * Forward iterator to the first element + * @returns {Iterator} + * @example + * let set = new TreeMultiSet(); + * ... + * for (let it = set.begin(); !it.equals(set.end()); it.next()) { + * console.log(`key: ${it.key}`); + * } + */ + begin() { + return this.__t.begin(); + } + + /** + * Forward iterator to the element following the last element + * @returns {Iterator} + * @example + * let set = new TreeMultiSet(); + * ... + * for (let it = set.begin(); !it.equals(set.end()); it.next()) { + * console.log(`key: ${it.key}`); + * } + */ + end() { + return this.__t.end(); + } + + /** + * Finds an element with key equivalent to the specified one. If such key does not exist end() iterator is returned. + * @param {*} key + * @returns {Iterator} + * @example + * let set = new TreeMultiSet([1, 2, 3]); + * ... + * let it = set.find(1); + * if (!it.equals(set.end())) { + * console.log(`Found key: ${it.key}`); // 1 + * } + */ + find(key) { + return this.__t.find(key); + } + + /** + * Adds key if such key does not exist in the set. + * @param {*} key + * @returns {InsertionResult} - indicates whether a node was added and provides iterator to it. + * @example + * let set = new TreeMultiSet(); + * set.insertUnique(1); + * set.insertUnique(1); // this step has no effect on the set + * let flag = set.has(1); // true + * let size = set.size; // 1 + */ + insertUnique(key) { + let n = new TreeNode(); + n.key = key; + return this.__t.insertUnique(n); + } + + /** + * Adds key if such key does not exist in the set. Same as insertUnique() + * @param {*} key + * @returns {InsertionResult} - indicates whether a node was added and provides iterator to it. + * @example + * let set = new TreeMultiSet(); + * set.insertOrReplace(1); + * set.insertOrReplace(1); // this step has no effect on the set + * let flag = set.has(1); // true + * let size = set.size; // 1 + */ + insertOrReplace(key) { + let n = new TreeNode(); + n.key = key; + return this.__t.insertOrReplace(n); + } + + /** + * Adds key whether it exists or not in the set. + * @param {*} key + * @returns {InsertionResult} - indicates whether a node was added and provides iterator to it. + * @example + * let set = new TreeMultiSet(); + * set.insertMulti(1); + * set.insertMulti(1); // this step has no effect on the map + * let flag = set.has(1); // true + * let size = set.size; // 2 + */ + insertMulti(key) { + let n = new TreeNode(); + n.key = key; + return this.__t.insertMulti(n); + } + + /** + * Removes value for the specified iterator. + * @param {Iterator} iterator + * @example + * let set = new TreeMultiSet([1,2,3]); + * let it = set.find(2); + * it.prev(); + * set.erase(it); // removes a node with key 1 + * console.log(set.toString()); // {2,3} + */ + erase(iterator) { + this.__t.erase(iterator.node); + } + + /** + * Iterator pointing to the first element that is not less than specified key. If no such element is found, see end() iterator is returned. + * @param {*} key + * @returns {Iterator} + * @example + * let set = new TreeMultiSet(); + * ... // add key-value pairs., using numbers as keys + * // iterate through all key-value pairs with keys between 0 and 50 inclusive + * let from = set.lowerBound(0); + * let to = set.upperBound(50); + * let it = from; + * while (!it.equals(to)) { + * console.log(it.key); + * it.next(); + * } + * + * let set = new TreeMultiSet(); + * ... // add key-value pairs., using numbers as keys + * // iterate through all key-value pairs with keys between 0 and 50 inclusive in reverse order + * let from = new ReverseIterator(set.upperBound(50)); + * let to = new ReverseIterator(set.lowerBound(0)); + * let it = from; + * while (!it.equals(to)) { + * console.log(it.key); + * it.next(); + * } + */ + lowerBound(key) { + return this.__t.lowerBound(key); + } + + /** + * Reverse iterator to the last element. + * @returns {ReverseIterator} + * @example + * let set = new TreeMultiSet(); + * ... + * for (let it = set.rbegin(); !it.equals(set.rend()); it.next()) { + * console.log(`key: ${it.key}`); + * } + */ + rbegin() { + return this.__t.rbegin(); + } + + /** + * Reverse iterator pointing to before the first element. + * @returns {ReverseIterator} + * @example + * let set = new TreeMultiSet(); + * ... + * for (let it = set.rbegin(); !it.equals(set.rend()); it.next()) { + * console.log(`key: ${it.key}`); + * } + */ + rend() { + return this.__t.rend(); + } + + /** + * Iterator pointing to the first element that is greater than key. If no such element is found end() iterator is returned. + * @param {*} key + * @returns {Iterator} + * @example + * let set = new TreeMultiSet(); + * ... // add key-value pairs., using numbers as keys + * // iterate through all key-value pairs with keys between 0 and 50 inclusive + * let from = set.lowerBound(0); + * let to = set.upperBound(50); + * let it = from; + * while (!it.equals(to)) { + * console.log(it.key); + * it.next(); + * } + * + * let set = new TreeMultiSet(); + * ... // add key-value pairs., using numbers as keys + * // iterate through all key-value pairs with keys between 0 and 50 inclusive in reverse order + * let from = new ReverseIterator(set.upperBound(50)); + * let to = new ReverseIterator(set.lowerBound(0)); + * let it = from; + * while (!it.equals(to)) { + * console.log(it.key); + * it.next(); + * } + */ + upperBound(key) { + return this.__t.upperBound(key); + } + + /** + * @returns first element of the container, or undefined if container is empty + * @example + * let set = new TreeMultiSet([1, 2, 3]); + * let first = set.first(); // 1 + */ + first() { + return this.__t.first(); + } + + /** + * @returns last element of the container, or undefined if container is empty + * @example + * let set = new TreeMultiSet([1, 2, 3]); + * let last = set.last(); // 3 + */ + last() { + return this.__t.last(); + } + + /** + * Serializes contents of the set in the form {key1,key2,...} + * @returns {String} + */ + toString() { + return this.__t.toString(); + } +} + +module.exports = { + TreeMultiSet: TreeMultiSet, +}; + +/***/ }) +/******/ ]); +}); + +/***/ }), + /***/ 742: /***/ (function(module, __unusedexports, __webpack_require__) { diff --git a/package-lock.json b/package-lock.json index 672aeff..121b6fc 100644 --- a/package-lock.json +++ b/package-lock.json @@ -4435,6 +4435,11 @@ "verror": "1.10.0" } }, + "jstreemap": { + "version": "1.28.2", + "resolved": "https://registry.npmjs.org/jstreemap/-/jstreemap-1.28.2.tgz";, + "integrity": "sha512-JYVDYwLat+OVXLpIXgUPy06wPSEkQafGOeotpGFodkM5+K8x3IrVPGaTw+Fd9MmZy092cLG/N+3q90oSBHZoQQ==" + }, "jsx-ast-utils": { "version": "2.2.3", "resolved": "https://registry.npmjs.org/jsx-ast-utils/-/jsx-ast-utils-2.2.3.tgz";, diff --git a/package.json b/package.json index a3b4877..b8c4043 100644 --- a/package.json +++ b/package.json @@ -27,7 +27,8 @@ "license": "MIT", "dependencies": { "@actions/core": "^1.2.2", - "@actions/github": "^2.1.0" + "@actions/github": "^2.1.0", + "jstreemap": "^1.28.2" }, "devDependencies": { "@types/jest": "^24.0.23", diff --git a/src/main.ts b/src/main.ts index 9ae7083..560f836 100644 --- a/src/main.ts +++ b/src/main.ts @@ -1,5 +1,38 @@ import * as github from '@actions/github' import * as core from '@actions/core' +import Octokit from '@octokit/rest' +import * as treemap from 'jstreemap' + +function createRunsQuery( + octokit: github.GitHub, + owner: string, + repo: string, + workflowId: string, + status: string, + branch?: string, + event?: string +): Octokit.RequestOptions { + const request = + branch === undefined + ? { + owner, + repo, + // eslint-disable-next-line @typescript-eslint/camelcase + workflow_id: workflowId, + status + } + : { + owner, + repo, + // eslint-disable-next-line @typescript-eslint/camelcase + workflow_id: workflowId, + status, + branch, + event + } + + return octokit.actions.listWorkflowRuns.endpoint.merge(request) +} async function cancelDuplicates( token: string, @@ -13,7 +46,7 @@ async function cancelDuplicates( const octokit = new github.GitHub(token) // Deteermind the workflow to reduce the result set, or reference anothre workflow - let resolvedId + let resolvedId = '' if (workflowId === undefined) { const reply = await octokit.actions.getWorkflowRun({ owner, @@ -22,73 +55,75 @@ async function cancelDuplicates( run_id: Number.parseInt(selfRunId) }) - resolvedId = reply.data.workflow_url.split('/').pop() + resolvedId = reply.data.workflow_url.split('/').pop() || '' + if (!(resolvedId.length > 0)) { + throw new Error('Could not resolve workflow') + } } else { resolvedId = workflowId } core.info(`Workflow ID is: ${resolvedId}`) - const request = - branch === undefined - ? { - owner, - repo, - // eslint-disable-next-line @typescript-eslint/camelcase - workflow_id: resolvedId - } - : { - owner, - repo, - // eslint-disable-next-line @typescript-eslint/camelcase - workflow_id: resolvedId, - branch, - event - } - - const listRuns = octokit.actions.listWorkflowRuns.endpoint.merge(request) + // eslint-disable-next-line @typescript-eslint/no-explicit-any + const sorted = new treemap.TreeMap<number, any>() + for (const status of ['queued', 'in_progress']) { + const listRuns = createRunsQuery( + octokit, + owner, + repo, + resolvedId, + status, + branch, + event + ) + for await (const item of octokit.paginate.iterator(listRuns)) { + // There is some sort of bug where the pagination URLs point to a + // different endpoint URL which trips up the resulting representation + // In that case, fallback to the actual REST 'workflow_runs' property + const elements = + item.data.length === undefined ? item.data.workflow_runs : item.data + + for (const element of elements) { + sorted.set(element.run_number, element) + } + } + } // If a workflow was provided process everything let matched = workflowId !== undefined const heads = new Set() - for await (const item of octokit.paginate.iterator(listRuns)) { - // There is some sort of bug where the pagination URLs point to a - // different endpoint URL which trips up the resulting representation - // In that case, fallback to the actual REST 'workflow_runs' property - const elements = - item.data.length === undefined ? item.data.workflow_runs : item.data - - for (const element of elements) { - core.info( - `${element.id} : ${element.workflow_url} : ${element.status} : ${element.run_number}` - ) - - if (!matched) { - if (element.id.toString() !== selfRunId) { - // Skip everything up to this run - continue - } - - matched = true - core.info(`Matched ${selfRunId}`) - } + for (const entry of sorted.backward()) { + const element = entry[1] + core.info( + `${element.id} : ${element.workflow_url} : ${element.status} : ${element.run_number}` + ) - if ('completed' === element.status.toString()) { + if (!matched) { + if (element.id.toString() !== selfRunId) { + // Skip everything up to this run continue } - // This is a set of one in the non-schedule case, otherwise everything is a candidate - const head = `${element.head_repository.full_name}/${element.head_branch}` - if (!heads.has(head)) { - core.info(`First: ${head}`) - heads.add(head) - continue - } + matched = true + core.info(`Matched ${selfRunId}`) + } - core.info(`Cancelling: ${head}`) + if ('completed' === element.status.toString()) { + continue + } - await cancelRun(octokit, owner, repo, element.id) + // This is a set of one in the non-schedule case, otherwise everything is a candidate + const head = `${element.head_repository.full_name}/${element.head_branch}` + if (!heads.has(head)) { + core.info(`First: ${head}`) + heads.add(head) + continue } + + core.info(`Cancelling: ${head}`) + + await cancelRun(octokit, owner, repo, element.id) } }
