/**
 * @license
 * Copyright 2020 Google LLC. All Rights Reserved.
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 * =============================================================================
 */
/** An implementation of the TopK kernel shared between webgl and cpu. */
import { buffer, util } from '@tensorflow/tfjs-core';
const comparePair = (a, b) => {
    const valueDiff = b.value - a.value;
    return valueDiff === 0 ? a.index - b.index : valueDiff;
};
/**
 * Partitions array where all elements smaller than the (k+1) smallest element
 * are found to the left of it, and all larger to the right of it.
 * Based on the Floyd-Rivest Algorithm, ref:
 * https://en.wikipedia.org/wiki/Floyd%E2%80%93Rivest_algorithm
 * @param array: Array to partition
 * @param left: Left index for the interval
 * @param right: Right index for the interval
 * @param k: Desired index value, where array[k] is the (k+1)th smallest element
 *           when left = 0
 */
function select(array, k, left = 0, right = array.length - 1) {
    while (right > left) {
        // Use select recursively to sample a smaller set of size s
        // the arbitrary constants 600 and 0.5 are used in the original
        // version to minimize execution time.
        if (right - left > 600) {
            const n = right - left + 1;
            const i = k - left + 1;
            const z = Math.log(n);
            const s = 0.5 * Math.exp(2 * z / 3);
            const sd = 0.5 * Math.sqrt(z * s * (n - s) / n) * Math.sign(i - n / 2);
            const newLeft = Math.max(left, Math.floor(k - i * s / n + sd));
            const newRight = Math.min(right, Math.floor(k + (n - i) * s / n + sd));
            select(array, k, newLeft, newRight);
        }
        // partition the elements between left and right around t
        const t = array[k];
        let i = left;
        let j = right;
        util.swap(array, left, k);
        if (comparePair(array[right], t) > 0) {
            util.swap(array, left, right);
        }
        while (i < j) {
            util.swap(array, i, j);
            i++;
            j--;
            while (comparePair(array[i], t) < 0) {
                i = i + 1;
            }
            while (comparePair(array[j], t) > 0) {
                j = j - 1;
            }
        }
        if (comparePair(array[left], t) === 0) {
            util.swap(array, left, j);
        }
        else {
            j = j + 1;
            util.swap(array, j, right);
        }
        // Adjust left and right towards the boundaries of the subset
        // containing the (k - left + 1)th smallest element.
        if (j <= k) {
            left = j + 1;
        }
        if (k <= j) {
            right = j - 1;
        }
    }
}
export function topKImpl(x, xShape, xDtype, k, sorted) {
    // Reshape into a 2d tensor [batch, lastDim] and compute topk along lastDim.
    const lastDim = xShape[xShape.length - 1];
    const [batch, size] = [x.length / lastDim, lastDim];
    const allTopKVals = util.getTypedArrayFromDType(xDtype, batch * k);
    const allTopKIndices = util.getTypedArrayFromDType('int32', batch * k);
    for (let b = 0; b < batch; b++) {
        const offset = b * size;
        const vals = x.subarray(offset, offset + size);
        let valAndInd = new Array(vals.length);
        vals.forEach((value, index) => valAndInd[index] = { value, index });
        if (k < valAndInd.length) {
            select(valAndInd, k);
            valAndInd = valAndInd.slice(0, k);
        }
        if (sorted) {
            valAndInd.sort(comparePair);
        }
        const outOffset = b * k;
        const topKVals = allTopKVals.subarray(outOffset, outOffset + k);
        const topKIndices = allTopKIndices.subarray(outOffset, outOffset + k);
        for (let i = 0; i < k; i++) {
            topKVals[i] = valAndInd[i].value;
            topKIndices[i] = valAndInd[i].index;
        }
    }
    // Reshape back to the original input shape, except that the last
    // dimension is k.
    const outputShape = xShape.slice();
    outputShape[outputShape.length - 1] = k;
    return [
        buffer(outputShape, xDtype, allTopKVals),
        buffer(outputShape, 'int32', allTopKIndices)
    ];
}
//# sourceMappingURL=data:application/json;base64,eyJ2ZXJzaW9uIjozLCJmaWxlIjoiVG9wS19pbXBsLmpzIiwic291cmNlUm9vdCI6IiIsInNvdXJjZXMiOlsiLi4vLi4vLi4vLi4vLi4vLi4vdGZqcy1iYWNrZW5kLWNwdS9zcmMva2VybmVscy9Ub3BLX2ltcGwudHMiXSwibmFtZXMiOltdLCJtYXBwaW5ncyI6IkFBQUE7Ozs7Ozs7Ozs7Ozs7OztHQWVHO0FBRUgseUVBQXlFO0FBRXpFLE9BQU8sRUFBQyxNQUFNLEVBQXFFLElBQUksRUFBQyxNQUFNLHVCQUF1QixDQUFDO0FBT3RILE1BQU0sV0FBVyxHQUFHLENBQUMsQ0FBTyxFQUFFLENBQU8sRUFBRSxFQUFFO0lBQ3ZDLE1BQU0sU0FBUyxHQUFHLENBQUMsQ0FBQyxLQUFLLEdBQUcsQ0FBQyxDQUFDLEtBQUssQ0FBQztJQUNwQyxPQUFPLFNBQVMsS0FBSyxDQUFDLENBQUMsQ0FBQyxDQUFDLENBQUMsQ0FBQyxLQUFLLEdBQUcsQ0FBQyxDQUFDLEtBQUssQ0FBQyxDQUFDLENBQUMsU0FBUyxDQUFDO0FBQ3pELENBQUMsQ0FBQztBQUVGOzs7Ozs7Ozs7O0dBVUc7QUFDSCxTQUFTLE1BQU0sQ0FBQyxLQUFhLEVBQUUsQ0FBUyxFQUFFLElBQUksR0FBRyxDQUFDLEVBQUUsS0FBSyxHQUFHLEtBQUssQ0FBQyxNQUFNLEdBQUcsQ0FBQztJQUMxRSxPQUFPLEtBQUssR0FBRyxJQUFJLEVBQUU7UUFDbkIsMkRBQTJEO1FBQzNELCtEQUErRDtRQUMvRCxzQ0FBc0M7UUFDdEMsSUFBSSxLQUFLLEdBQUcsSUFBSSxHQUFHLEdBQUcsRUFBRTtZQUN0QixNQUFNLENBQUMsR0FBRyxLQUFLLEdBQUcsSUFBSSxHQUFHLENBQUMsQ0FBQztZQUMzQixNQUFNLENBQUMsR0FBRyxDQUFDLEdBQUcsSUFBSSxHQUFHLENBQUMsQ0FBQztZQUN2QixNQUFNLENBQUMsR0FBRyxJQUFJLENBQUMsR0FBRyxDQUFDLENBQUMsQ0FBQyxDQUFDO1lBQ3RCLE1BQU0sQ0FBQyxHQUFHLEdBQUcsR0FBRyxJQUFJLENBQUMsR0FBRyxDQUFDLENBQUMsR0FBRyxDQUFDLEdBQUcsQ0FBQyxDQUFDLENBQUM7WUFDcEMsTUFBTSxFQUFFLEdBQUcsR0FBRyxHQUFHLElBQUksQ0FBQyxJQUFJLENBQUMsQ0FBQyxHQUFHLENBQUMsR0FBRyxDQUFDLENBQUMsR0FBRyxDQUFDLENBQUMsR0FBRyxDQUFDLENBQUMsR0FBRyxJQUFJLENBQUMsSUFBSSxDQUFDLENBQUMsR0FBRyxDQUFDLEdBQUcsQ0FBQyxDQUFDLENBQUM7WUFDdkUsTUFBTSxPQUFPLEdBQUcsSUFBSSxDQUFDLEdBQUcsQ0FBQyxJQUFJLEVBQUUsSUFBSSxDQUFDLEtBQUssQ0FBQyxDQUFDLEdBQUcsQ0FBQyxHQUFHLENBQUMsR0FBRyxDQUFDLEdBQUcsRUFBRSxDQUFDLENBQUMsQ0FBQztZQUMvRCxNQUFNLFFBQVEsR0FBRyxJQUFJLENBQUMsR0FBRyxDQUFDLEtBQUssRUFBRSxJQUFJLENBQUMsS0FBSyxDQUFDLENBQUMsR0FBRyxDQUFDLENBQUMsR0FBRyxDQUFDLENBQUMsR0FBRyxDQUFDLEdBQUcsQ0FBQyxHQUFHLEVBQUUsQ0FBQyxDQUFDLENBQUM7WUFDdkUsTUFBTSxDQUFDLEtBQUssRUFBRSxDQUFDLEVBQUUsT0FBTyxFQUFFLFFBQVEsQ0FBQyxDQUFDO1NBQ3JDO1FBQ0QseURBQXlEO1FBQ3pELE1BQU0sQ0FBQyxHQUFHLEtBQUssQ0FBQyxDQUFDLENBQUMsQ0FBQztRQUNuQixJQUFJLENBQUMsR0FBRyxJQUFJLENBQUM7UUFDYixJQUFJLENBQUMsR0FBRyxLQUFLLENBQUM7UUFFZCxJQUFJLENBQUMsSUFBSSxDQUFDLEtBQUssRUFBRSxJQUFJLEVBQUUsQ0FBQyxDQUFDLENBQUM7UUFFMUIsSUFBSSxXQUFXLENBQUMsS0FBSyxDQUFDLEtBQUssQ0FBQyxFQUFFLENBQUMsQ0FBQyxHQUFHLENBQUMsRUFBRTtZQUNwQyxJQUFJLENBQUMsSUFBSSxDQUFDLEtBQUssRUFBRSxJQUFJLEVBQUUsS0FBSyxDQUFDLENBQUM7U0FDL0I7UUFDRCxPQUFPLENBQUMsR0FBRyxDQUFDLEVBQUU7WUFDWixJQUFJLENBQUMsSUFBSSxDQUFDLEtBQUssRUFBRSxDQUFDLEVBQUUsQ0FBQyxDQUFDLENBQUM7WUFDdkIsQ0FBQyxFQUFFLENBQUM7WUFDSixDQUFDLEVBQUUsQ0FBQztZQUNKLE9BQU8sV0FBVyxDQUFDLEtBQUssQ0FBQyxDQUFDLENBQUMsRUFBRSxDQUFDLENBQUMsR0FBRyxDQUFDLEVBQUU7Z0JBQ25DLENBQUMsR0FBRyxDQUFDLEdBQUcsQ0FBQyxDQUFDO2FBQ1g7WUFDRCxPQUFPLFdBQVcsQ0FBQyxLQUFLLENBQUMsQ0FBQyxDQUFDLEVBQUUsQ0FBQyxDQUFDLEdBQUcsQ0FBQyxFQUFFO2dCQUNuQyxDQUFDLEdBQUcsQ0FBQyxHQUFHLENBQUMsQ0FBQzthQUNYO1NBQ0Y7UUFDRCxJQUFJLFdBQVcsQ0FBQyxLQUFLLENBQUMsSUFBSSxDQUFDLEVBQUUsQ0FBQyxDQUFDLEtBQUssQ0FBQyxFQUFFO1lBQ3JDLElBQUksQ0FBQyxJQUFJLENBQUMsS0FBSyxFQUFFLElBQUksRUFBRSxDQUFDLENBQUMsQ0FBQztTQUMzQjthQUFNO1lBQ0wsQ0FBQyxHQUFHLENBQUMsR0FBRyxDQUFDLENBQUM7WUFDVixJQUFJLENBQUMsSUFBSSxDQUFDLEtBQUssRUFBRSxDQUFDLEVBQUUsS0FBSyxDQUFDLENBQUM7U0FDNUI7UUFDRCw2REFBNkQ7UUFDN0Qsb0RBQW9EO1FBQ3BELElBQUksQ0FBQyxJQUFJLENBQUMsRUFBRTtZQUNWLElBQUksR0FBRyxDQUFDLEdBQUcsQ0FBQyxDQUFDO1NBQ2Q7UUFDRCxJQUFJLENBQUMsSUFBSSxDQUFDLEVBQUU7WUFDVixLQUFLLEdBQUcsQ0FBQyxHQUFHLENBQUMsQ0FBQztTQUNmO0tBQ0Y7QUFDSCxDQUFDO0FBRUQsTUFBTSxVQUFVLFFBQVEsQ0FDcEIsQ0FBYSxFQUFFLE1BQWdCLEVBQUUsTUFBdUIsRUFBRSxDQUFTLEVBQ25FLE1BQWU7SUFFakIsNEVBQTRFO0lBQzVFLE1BQU0sT0FBTyxHQUFHLE1BQU0sQ0FBQyxNQUFNLENBQUMsTUFBTSxHQUFHLENBQUMsQ0FBQyxDQUFDO0lBQzFDLE1BQU0sQ0FBQyxLQUFLLEVBQUUsSUFBSSxDQUFDLEdBQUcsQ0FBQyxDQUFDLENBQUMsTUFBTSxHQUFHLE9BQU8sRUFBRSxPQUFPLENBQUMsQ0FBQztJQUNwRCxNQUFNLFdBQVcsR0FBRyxJQUFJLENBQUMsc0JBQXNCLENBQUMsTUFBTSxFQUFFLEtBQUssR0FBRyxDQUFDLENBQUMsQ0FBQztJQUNuRSxNQUFNLGNBQWMsR0FBRyxJQUFJLENBQUMsc0JBQXNCLENBQUMsT0FBTyxFQUFFLEtBQUssR0FBRyxDQUFDLENBQUMsQ0FBQztJQUV2RSxLQUFLLElBQUksQ0FBQyxHQUFHLENBQUMsRUFBRSxDQUFDLEdBQUcsS0FBSyxFQUFFLENBQUMsRUFBRSxFQUFFO1FBQzlCLE1BQU0sTUFBTSxHQUFHLENBQUMsR0FBRyxJQUFJLENBQUM7UUFDeEIsTUFBTSxJQUFJLEdBQUcsQ0FBQyxDQUFDLFFBQVEsQ0FBQyxNQUFNLEVBQUUsTUFBTSxHQUFHLElBQUksQ0FBQyxDQUFDO1FBRS9DLElBQUksU0FBUyxHQUFXLElBQUksS0FBSyxDQUFDLElBQUksQ0FBQyxNQUFNLENBQUMsQ0FBQztRQUMvQyxJQUFJLENBQUMsT0FBTyxDQUNSLENBQUMsS0FBYSxFQUFFLEtBQWEsRUFBRSxFQUFFLENBQUMsU0FBUyxDQUFDLEtBQUssQ0FBQyxHQUFHLEVBQUMsS0FBSyxFQUFFLEtBQUssRUFBQyxDQUFDLENBQUM7UUFFekUsSUFBSSxDQUFDLEdBQUcsU0FBUyxDQUFDLE1BQU0sRUFBRTtZQUN4QixNQUFNLENBQUMsU0FBUyxFQUFFLENBQUMsQ0FBQyxDQUFDO1lBQ3JCLFNBQVMsR0FBRyxTQUFTLENBQUMsS0FBSyxDQUFDLENBQUMsRUFBRSxDQUFDLENBQUMsQ0FBQztTQUNuQztRQUVELElBQUksTUFBTSxFQUFFO1lBQ1YsU0FBUyxDQUFDLElBQUksQ0FBQyxXQUFXLENBQUMsQ0FBQztTQUM3QjtRQUVELE1BQU0sU0FBUyxHQUFHLENBQUMsR0FBRyxDQUFDLENBQUM7UUFDeEIsTUFBTSxRQUFRLEdBQUcsV0FBVyxDQUFDLFFBQVEsQ0FBQyxTQUFTLEVBQUUsU0FBUyxHQUFHLENBQUMsQ0FBQyxDQUFDO1FBQ2hFLE1BQU0sV0FBVyxHQUFHLGNBQWMsQ0FBQyxRQUFRLENBQUMsU0FBUyxFQUFFLFNBQVMsR0FBRyxDQUFDLENBQUMsQ0FBQztRQUN0RSxLQUFLLElBQUksQ0FBQyxHQUFHLENBQUMsRUFBRSxDQUFDLEdBQUcsQ0FBQyxFQUFFLENBQUMsRUFBRSxFQUFFO1lBQzFCLFFBQVEsQ0FBQyxDQUFDLENBQUMsR0FBRyxTQUFTLENBQUMsQ0FBQyxDQUFDLENBQUMsS0FBSyxDQUFDO1lBQ2pDLFdBQVcsQ0FBQyxDQUFDLENBQUMsR0FBRyxTQUFTLENBQUMsQ0FBQyxDQUFDLENBQUMsS0FBSyxDQUFDO1NBQ3JDO0tBQ0Y7SUFDRCxpRUFBaUU7SUFDakUsa0JBQWtCO0lBQ2xCLE1BQU0sV0FBVyxHQUFHLE1BQU0sQ0FBQyxLQUFLLEVBQUUsQ0FBQztJQUNuQyxXQUFXLENBQUMsV0FBVyxDQUFDLE1BQU0sR0FBRyxDQUFDLENBQUMsR0FBRyxDQUFDLENBQUM7SUFFeEMsT0FBTztRQUNMLE1BQU0sQ0FBQyxXQUEwQixFQUFFLE1BQU0sRUFBRSxXQUFXLENBQUM7UUFDdkQsTUFBTSxDQUFDLFdBQTBCLEVBQUUsT0FBTyxFQUFFLGNBQWMsQ0FBQztLQUM1RCxDQUFDO0FBQ0osQ0FBQyIsInNvdXJjZXNDb250ZW50IjpbIi8qKlxuICogQGxpY2Vuc2VcbiAqIENvcHlyaWdodCAyMDIwIEdvb2dsZSBMTEMuIEFsbCBSaWdodHMgUmVzZXJ2ZWQuXG4gKiBMaWNlbnNlZCB1bmRlciB0aGUgQXBhY2hlIExpY2Vuc2UsIFZlcnNpb24gMi4wICh0aGUgXCJMaWNlbnNlXCIpO1xuICogeW91IG1heSBub3QgdXNlIHRoaXMgZmlsZSBleGNlcHQgaW4gY29tcGxpYW5jZSB3aXRoIHRoZSBMaWNlbnNlLlxuICogWW91IG1heSBvYnRhaW4gYSBjb3B5IG9mIHRoZSBMaWNlbnNlIGF0XG4gKlxuICogaHR0cDovL3d3dy5hcGFjaGUub3JnL2xpY2Vuc2VzL0xJQ0VOU0UtMi4wXG4gKlxuICogVW5sZXNzIHJlcXVpcmVkIGJ5IGFwcGxpY2FibGUgbGF3IG9yIGFncmVlZCB0byBpbiB3cml0aW5nLCBzb2Z0d2FyZVxuICogZGlzdHJpYnV0ZWQgdW5kZXIgdGhlIExpY2Vuc2UgaXMgZGlzdHJpYnV0ZWQgb24gYW4gXCJBUyBJU1wiIEJBU0lTLFxuICogV0lUSE9VVCBXQVJSQU5USUVTIE9SIENPTkRJVElPTlMgT0YgQU5ZIEtJTkQsIGVpdGhlciBleHByZXNzIG9yIGltcGxpZWQuXG4gKiBTZWUgdGhlIExpY2Vuc2UgZm9yIHRoZSBzcGVjaWZpYyBsYW5ndWFnZSBnb3Zlcm5pbmcgcGVybWlzc2lvbnMgYW5kXG4gKiBsaW1pdGF0aW9ucyB1bmRlciB0aGUgTGljZW5zZS5cbiAqID09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09XG4gKi9cblxuLyoqIEFuIGltcGxlbWVudGF0aW9uIG9mIHRoZSBUb3BLIGtlcm5lbCBzaGFyZWQgYmV0d2VlbiB3ZWJnbCBhbmQgY3B1LiAqL1xuXG5pbXBvcnQge2J1ZmZlciwgTnVtZXJpY0RhdGFUeXBlLCBSYW5rLCBTaGFwZU1hcCwgVGVuc29yLCBUZW5zb3JCdWZmZXIsIFR5cGVkQXJyYXksIHV0aWx9IGZyb20gJ0B0ZW5zb3JmbG93L3RmanMtY29yZSc7XG5cbnR5cGUgUGFpciA9IHtcbiAgdmFsdWU6IG51bWJlcixcbiAgaW5kZXg6IG51bWJlclxufTtcblxuY29uc3QgY29tcGFyZVBhaXIgPSAoYTogUGFpciwgYjogUGFpcikgPT4ge1xuICBjb25zdCB2YWx1ZURpZmYgPSBiLnZhbHVlIC0gYS52YWx1ZTtcbiAgcmV0dXJuIHZhbHVlRGlmZiA9PT0gMCA/IGEuaW5kZXggLSBiLmluZGV4IDogdmFsdWVEaWZmO1xufTtcblxuLyoqXG4gKiBQYXJ0aXRpb25zIGFycmF5IHdoZXJlIGFsbCBlbGVtZW50cyBzbWFsbGVyIHRoYW4gdGhlIChrKzEpIHNtYWxsZXN0IGVsZW1lbnRcbiAqIGFyZSBmb3VuZCB0byB0aGUgbGVmdCBvZiBpdCwgYW5kIGFsbCBsYXJnZXIgdG8gdGhlIHJpZ2h0IG9mIGl0LlxuICogQmFzZWQgb24gdGhlIEZsb3lkLVJpdmVzdCBBbGdvcml0aG0sIHJlZjpcbiAqIGh0dHBzOi8vZW4ud2lraXBlZGlhLm9yZy93aWtpL0Zsb3lkJUUyJTgwJTkzUml2ZXN0X2FsZ29yaXRobVxuICogQHBhcmFtIGFycmF5OiBBcnJheSB0byBwYXJ0aXRpb25cbiAqIEBwYXJhbSBsZWZ0OiBMZWZ0IGluZGV4IGZvciB0aGUgaW50ZXJ2YWxcbiAqIEBwYXJhbSByaWdodDogUmlnaHQgaW5kZXggZm9yIHRoZSBpbnRlcnZhbFxuICogQHBhcmFtIGs6IERlc2lyZWQgaW5kZXggdmFsdWUsIHdoZXJlIGFycmF5W2tdIGlzIHRoZSAoaysxKXRoIHNtYWxsZXN0IGVsZW1lbnRcbiAqICAgICAgICAgICB3aGVuIGxlZnQgPSAwXG4gKi9cbmZ1bmN0aW9uIHNlbGVjdChhcnJheTogUGFpcltdLCBrOiBudW1iZXIsIGxlZnQgPSAwLCByaWdodCA9IGFycmF5Lmxlbmd0aCAtIDEpIHtcbiAgd2hpbGUgKHJpZ2h0ID4gbGVmdCkge1xuICAgIC8vIFVzZSBzZWxlY3QgcmVjdXJzaXZlbHkgdG8gc2FtcGxlIGEgc21hbGxlciBzZXQgb2Ygc2l6ZSBzXG4gICAgLy8gdGhlIGFyYml0cmFyeSBjb25zdGFudHMgNjAwIGFuZCAwLjUgYXJlIHVzZWQgaW4gdGhlIG9yaWdpbmFsXG4gICAgLy8gdmVyc2lvbiB0byBtaW5pbWl6ZSBleGVjdXRpb24gdGltZS5cbiAgICBpZiAocmlnaHQgLSBsZWZ0ID4gNjAwKSB7XG4gICAgICBjb25zdCBuID0gcmlnaHQgLSBsZWZ0ICsgMTtcbiAgICAgIGNvbnN0IGkgPSBrIC0gbGVmdCArIDE7XG4gICAgICBjb25zdCB6ID0gTWF0aC5sb2cobik7XG4gICAgICBjb25zdCBzID0gMC41ICogTWF0aC5leHAoMiAqIHogLyAzKTtcbiAgICAgIGNvbnN0IHNkID0gMC41ICogTWF0aC5zcXJ0KHogKiBzICogKG4gLSBzKSAvIG4pICogTWF0aC5zaWduKGkgLSBuIC8gMik7XG4gICAgICBjb25zdCBuZXdMZWZ0ID0gTWF0aC5tYXgobGVmdCwgTWF0aC5mbG9vcihrIC0gaSAqIHMgLyBuICsgc2QpKTtcbiAgICAgIGNvbnN0IG5ld1JpZ2h0ID0gTWF0aC5taW4ocmlnaHQsIE1hdGguZmxvb3IoayArIChuIC0gaSkgKiBzIC8gbiArIHNkKSk7XG4gICAgICBzZWxlY3QoYXJyYXksIGssIG5ld0xlZnQsIG5ld1JpZ2h0KTtcbiAgICB9XG4gICAgLy8gcGFydGl0aW9uIHRoZSBlbGVtZW50cyBiZXR3ZWVuIGxlZnQgYW5kIHJpZ2h0IGFyb3VuZCB0XG4gICAgY29uc3QgdCA9IGFycmF5W2tdO1xuICAgIGxldCBpID0gbGVmdDtcbiAgICBsZXQgaiA9IHJpZ2h0O1xuXG4gICAgdXRpbC5zd2FwKGFycmF5LCBsZWZ0LCBrKTtcblxuICAgIGlmIChjb21wYXJlUGFpcihhcnJheVtyaWdodF0sIHQpID4gMCkge1xuICAgICAgdXRpbC5zd2FwKGFycmF5LCBsZWZ0LCByaWdodCk7XG4gICAgfVxuICAgIHdoaWxlIChpIDwgaikge1xuICAgICAgdXRpbC5zd2FwKGFycmF5LCBpLCBqKTtcbiAgICAgIGkrKztcbiAgICAgIGotLTtcbiAgICAgIHdoaWxlIChjb21wYXJlUGFpcihhcnJheVtpXSwgdCkgPCAwKSB7XG4gICAgICAgIGkgPSBpICsgMTtcbiAgICAgIH1cbiAgICAgIHdoaWxlIChjb21wYXJlUGFpcihhcnJheVtqXSwgdCkgPiAwKSB7XG4gICAgICAgIGogPSBqIC0gMTtcbiAgICAgIH1cbiAgICB9XG4gICAgaWYgKGNvbXBhcmVQYWlyKGFycmF5W2xlZnRdLCB0KSA9PT0gMCkge1xuICAgICAgdXRpbC5zd2FwKGFycmF5LCBsZWZ0LCBqKTtcbiAgICB9IGVsc2Uge1xuICAgICAgaiA9IGogKyAxO1xuICAgICAgdXRpbC5zd2FwKGFycmF5LCBqLCByaWdodCk7XG4gICAgfVxuICAgIC8vIEFkanVzdCBsZWZ0IGFuZCByaWdodCB0b3dhcmRzIHRoZSBib3VuZGFyaWVzIG9mIHRoZSBzdWJzZXRcbiAgICAvLyBjb250YWluaW5nIHRoZSAoayAtIGxlZnQgKyAxKXRoIHNtYWxsZXN0IGVsZW1lbnQuXG4gICAgaWYgKGogPD0gaykge1xuICAgICAgbGVmdCA9IGogKyAxO1xuICAgIH1cbiAgICBpZiAoayA8PSBqKSB7XG4gICAgICByaWdodCA9IGogLSAxO1xuICAgIH1cbiAgfVxufVxuXG5leHBvcnQgZnVuY3Rpb24gdG9wS0ltcGw8VCBleHRlbmRzIFRlbnNvciwgUiBleHRlbmRzIFJhbms+KFxuICAgIHg6IFR5cGVkQXJyYXksIHhTaGFwZTogbnVtYmVyW10sIHhEdHlwZTogTnVtZXJpY0RhdGFUeXBlLCBrOiBudW1iZXIsXG4gICAgc29ydGVkOiBib29sZWFuKTpcbiAgICBbVGVuc29yQnVmZmVyPFIsIE51bWVyaWNEYXRhVHlwZT4sIFRlbnNvckJ1ZmZlcjxSLCAnaW50MzInPl0ge1xuICAvLyBSZXNoYXBlIGludG8gYSAyZCB0ZW5zb3IgW2JhdGNoLCBsYXN0RGltXSBhbmQgY29tcHV0ZSB0b3BrIGFsb25nIGxhc3REaW0uXG4gIGNvbnN0IGxhc3REaW0gPSB4U2hhcGVbeFNoYXBlLmxlbmd0aCAtIDFdO1xuICBjb25zdCBbYmF0Y2gsIHNpemVdID0gW3gubGVuZ3RoIC8gbGFzdERpbSwgbGFzdERpbV07XG4gIGNvbnN0IGFsbFRvcEtWYWxzID0gdXRpbC5nZXRUeXBlZEFycmF5RnJvbURUeXBlKHhEdHlwZSwgYmF0Y2ggKiBrKTtcbiAgY29uc3QgYWxsVG9wS0luZGljZXMgPSB1dGlsLmdldFR5cGVkQXJyYXlGcm9tRFR5cGUoJ2ludDMyJywgYmF0Y2ggKiBrKTtcblxuICBmb3IgKGxldCBiID0gMDsgYiA8IGJhdGNoOyBiKyspIHtcbiAgICBjb25zdCBvZmZzZXQgPSBiICogc2l6ZTtcbiAgICBjb25zdCB2YWxzID0geC5zdWJhcnJheShvZmZzZXQsIG9mZnNldCArIHNpemUpO1xuXG4gICAgbGV0IHZhbEFuZEluZDogUGFpcltdID0gbmV3IEFycmF5KHZhbHMubGVuZ3RoKTtcbiAgICB2YWxzLmZvckVhY2goXG4gICAgICAgICh2YWx1ZTogbnVtYmVyLCBpbmRleDogbnVtYmVyKSA9PiB2YWxBbmRJbmRbaW5kZXhdID0ge3ZhbHVlLCBpbmRleH0pO1xuXG4gICAgaWYgKGsgPCB2YWxBbmRJbmQubGVuZ3RoKSB7XG4gICAgICBzZWxlY3QodmFsQW5kSW5kLCBrKTtcbiAgICAgIHZhbEFuZEluZCA9IHZhbEFuZEluZC5zbGljZSgwLCBrKTtcbiAgICB9XG5cbiAgICBpZiAoc29ydGVkKSB7XG4gICAgICB2YWxBbmRJbmQuc29ydChjb21wYXJlUGFpcik7XG4gICAgfVxuICAgIFxuICAgIGNvbnN0IG91dE9mZnNldCA9IGIgKiBrO1xuICAgIGNvbnN0IHRvcEtWYWxzID0gYWxsVG9wS1ZhbHMuc3ViYXJyYXkob3V0T2Zmc2V0LCBvdXRPZmZzZXQgKyBrKTtcbiAgICBjb25zdCB0b3BLSW5kaWNlcyA9IGFsbFRvcEtJbmRpY2VzLnN1YmFycmF5KG91dE9mZnNldCwgb3V0T2Zmc2V0ICsgayk7XG4gICAgZm9yIChsZXQgaSA9IDA7IGkgPCBrOyBpKyspIHtcbiAgICAgIHRvcEtWYWxzW2ldID0gdmFsQW5kSW5kW2ldLnZhbHVlO1xuICAgICAgdG9wS0luZGljZXNbaV0gPSB2YWxBbmRJbmRbaV0uaW5kZXg7XG4gICAgfVxuICB9XG4gIC8vIFJlc2hhcGUgYmFjayB0byB0aGUgb3JpZ2luYWwgaW5wdXQgc2hhcGUsIGV4Y2VwdCB0aGF0IHRoZSBsYXN0XG4gIC8vIGRpbWVuc2lvbiBpcyBrLlxuICBjb25zdCBvdXRwdXRTaGFwZSA9IHhTaGFwZS5zbGljZSgpO1xuICBvdXRwdXRTaGFwZVtvdXRwdXRTaGFwZS5sZW5ndGggLSAxXSA9IGs7XG5cbiAgcmV0dXJuIFtcbiAgICBidWZmZXIob3V0cHV0U2hhcGUgYXMgU2hhcGVNYXBbUl0sIHhEdHlwZSwgYWxsVG9wS1ZhbHMpLFxuICAgIGJ1ZmZlcihvdXRwdXRTaGFwZSBhcyBTaGFwZU1hcFtSXSwgJ2ludDMyJywgYWxsVG9wS0luZGljZXMpXG4gIF07XG59XG4iXX0=