list/index.js

"use strict";
Object.defineProperty(exports, "__esModule", { value: true });
var branchingFactor = 32;
var branchBits = 5;
var mask = 31;
var elementEquals = function (a, b) {
    return a === b;
};
function setEquals(equals) {
    elementEquals = equals;
}
exports.setEquals = setEquals;
function createPath(depth, value) {
    var current = value;
    for (var i = 0; i < depth; ++i) {
        current = new Node(undefined, [current]);
    }
    return current;
}
// Array helper functions
function copyArray(source) {
    var array = [];
    for (var i = 0; i < source.length; ++i) {
        array[i] = source[i];
    }
    return array;
}
function pushElements(source, target, offset, amount) {
    for (var i = offset; i < offset + amount; ++i) {
        target.push(source[i]);
    }
}
function copyIndices(source, sourceStart, target, targetStart, length) {
    for (var i = 0; i < length; ++i) {
        target[targetStart + i] = source[sourceStart + i];
    }
}
function arrayPrepend(value, array) {
    var newLength = array.length + 1;
    var result = new Array(newLength);
    result[0] = value;
    for (var i = 1; i < newLength; ++i) {
        result[i] = array[i - 1];
    }
    return result;
}
/**
 * Prepends an element to a node
 */
function nodePrepend(value, size, node) {
    var array = arrayPrepend(value, node.array);
    var sizes = undefined;
    if (node.sizes !== undefined) {
        sizes = new Array(node.sizes.length + 1);
        sizes[0] = size;
        for (var i = 0; i < node.sizes.length; ++i) {
            sizes[i + 1] = node.sizes[i] + size;
        }
    }
    return new Node(sizes, array);
}
/**
 * Create a reverse _copy_ of an array.
 */
function reverseArray(array) {
    return array.slice().reverse();
}
function arrayFirst(array) {
    return array[0];
}
function arrayLast(array) {
    return array[array.length - 1];
}
function updateNode(node, depth, index, offset, value) {
    var curOffset = (offset >> (depth * branchBits)) & mask;
    var path = ((index >> (depth * branchBits)) & mask) - curOffset;
    if (node.sizes !== undefined) {
        while (node.sizes[path] <= index) {
            path++;
        }
        var traversed = path === 0 ? 0 : node.sizes[path - 1];
        index -= traversed;
    }
    var array;
    if (path < 0) {
        // TOOD: Once `prepend` no longer uses `update` this should be removed
        array = arrayPrepend(createPath(depth, value), node.array);
    }
    else {
        array = copyArray(node.array);
        if (depth === 0) {
            array[path] = value;
        }
        else {
            array[path] = updateNode(array[path], depth - 1, index, path === 0 ? offset : 0, value);
        }
    }
    return new Node(node.sizes, array);
}
var Node = /** @class */ (function () {
    function Node(sizes, array) {
        this.sizes = sizes;
        this.array = array;
    }
    return Node;
}());
exports.Node = Node;
function nodeNthDense(node, depth, index) {
    var current = node;
    for (; depth >= 0; --depth) {
        current = current.array[(index >> (depth * branchBits)) & mask];
    }
    return current;
}
function handleOffset(depth, offset, index) {
    index += offset;
    for (; depth >= 0; --depth) {
        index = index - (offset & (mask << (depth * branchBits)));
        if (((index >> (depth * branchBits)) & mask) !== 0) {
            break;
        }
    }
    return index;
}
function nodeNth(node, depth, index) {
    var path;
    var current = node;
    while (current.sizes !== undefined) {
        path = (index >> (depth * branchBits)) & mask;
        while (current.sizes[path] <= index) {
            path++;
        }
        var traversed = path === 0 ? 0 : current.sizes[path - 1];
        index -= traversed;
        depth--;
        current = current.array[path];
    }
    return nodeNthDense(current, depth, index);
}
function nth(index, l) {
    var prefixSize = getPrefixSize(l);
    var suffixSize = getSuffixSize(l);
    var offset = l.offset;
    if (index < prefixSize) {
        return l.prefix[prefixSize - index - 1];
    }
    else if (index >= l.length - suffixSize) {
        return l.suffix[index - (l.length - suffixSize)];
    }
    var depth = getDepth(l);
    return l.root.sizes === undefined
        ? nodeNthDense(l.root, depth, offset === 0
            ? index - prefixSize
            : handleOffset(depth, offset, index - prefixSize))
        : nodeNth(l.root, depth, index - prefixSize);
}
exports.nth = nth;
function cloneNode(_a) {
    var sizes = _a.sizes, array = _a.array;
    return new Node(sizes === undefined ? undefined : copyArray(sizes), copyArray(array));
}
function suffixToNode(suffix) {
    // FIXME: should take size and copy
    return new Node(undefined, suffix);
}
function prefixToNode(prefix) {
    // FIXME: should take size and copy
    return new Node(undefined, prefix.reverse());
}
function setSizes(node, height) {
    var sum = 0;
    var sizeTable = [];
    for (var i = 0; i < node.array.length; ++i) {
        sum += sizeOfSubtree(node.array[i], height - 1);
        sizeTable[i] = sum;
    }
    node.sizes = sizeTable;
    return node;
}
/**
 * Returns the number of elements stored in the node.
 */
function sizeOfSubtree(node, height) {
    if (height !== 0) {
        if (node.sizes !== undefined) {
            return arrayLast(node.sizes);
        }
        else {
            // the node is leftwise dense so all all but the last child are full
            var lastSize = sizeOfSubtree(arrayLast(node.array), height - 1);
            return ((node.array.length - 1) << (height * branchBits)) + lastSize;
        }
    }
    else {
        return node.array.length;
    }
}
// This array should not be mutated. Thus a dummy element is placed in
// it. Thus the affix will not be owned and thus not mutated.
var emptyAffix = [0];
function affixPush(a, array, length) {
    if (array.length === length) {
        array.push(a);
        return array;
    }
    else {
        var newArray = [];
        copyIndices(array, 0, newArray, 0, length);
        newArray.push(a);
        return newArray;
    }
}
// We store a bit field in list. From right to left, the first five
// bits are suffix length, the next five are prefix length and the
// rest is depth. The functions below are for working with the bits in
// a sane way.
var affixBits = 6;
var affixMask = 63;
function getSuffixSize(l) {
    return l.bits & affixMask;
}
function getPrefixSize(l) {
    return (l.bits >> affixBits) & affixMask;
}
function getDepth(l) {
    return l.bits >> (affixBits * 2);
}
function setPrefix(size, bits) {
    return (size << affixBits) | (bits & ~(affixMask << affixBits));
}
function setSuffix(size, bits) {
    return size | (bits & ~affixMask);
}
function setDepth(depth, bits) {
    return ((depth << (affixBits * 2)) | (bits & (affixMask | (affixMask << affixBits))));
}
function incrementPrefix(bits) {
    return bits + (1 << affixBits);
}
function incrementSuffix(bits) {
    return bits + 1;
}
function incrementDepth(bits) {
    return bits + (1 << (affixBits * 2));
}
// function decrementDepth(bits: number): number {
//   return bits - (1 << (affixBits * 2));
// }
function createBits(depth, prefixSize, suffixSize) {
    return (depth << (affixBits * 2)) | (prefixSize << affixBits) | suffixSize;
}
/*
 * Invariants that any list `l` should satisfy
 *
 * 1. If `l.root !== undefined` then `getSuffixSize(l) !== 0` and
 *   `getPrefixSize(l) !== 0`. The invariant ensures that `first` and
 *   `last` never have to look in the root and that they therefore
 *   take O(1) time.
 * 2. If a tree or sub-tree does not have a size-table then all leaf
      nodes in the tree are of size 32.
 */
var List = /** @class */ (function () {
    function List(bits, offset, length, root, suffix, prefix) {
        this.bits = bits;
        this.offset = offset;
        this.length = length;
        this.root = root;
        this.suffix = suffix;
        this.prefix = prefix;
    }
    List.prototype[Symbol.iterator] = function () {
        return new ListIterator(this);
    };
    return List;
}());
exports.List = List;
function cloneList(l) {
    return new List(l.bits, l.offset, l.length, l.root, l.suffix, l.prefix);
}
var ListIterator = /** @class */ (function () {
    function ListIterator(l) {
        this.l = l;
        this.result = { done: false, value: undefined };
        this.idx = -1;
        this.prefixSize = getPrefixSize(l);
        this.middleSize = l.length - getSuffixSize(l);
        if (l.root !== undefined) {
            var depth = getDepth(l);
            this.stack = new Array(depth + 1);
            this.indices = new Array(depth + 1);
            var currentNode = l.root.array;
            for (var i = depth; 0 <= i; --i) {
                this.stack[i] = currentNode;
                this.indices[i] = 0;
                currentNode = currentNode[0].array;
            }
            this.indices[0] = -1;
        }
    }
    ListIterator.prototype.nextInTree = function () {
        var i = 0;
        while (++this.indices[i] === this.stack[i].length) {
            this.indices[i] = 0;
            ++i;
        }
        for (; 0 < i; --i) {
            this.stack[i - 1] = this.stack[i][this.indices[i]].array;
        }
    };
    ListIterator.prototype.next = function () {
        var newVal;
        var idx = ++this.idx;
        if (idx < this.prefixSize) {
            newVal = this.l.prefix[this.prefixSize - idx - 1];
        }
        else if (idx < this.middleSize) {
            this.nextInTree();
            newVal = this.stack[0][this.indices[0]];
        }
        else if (idx < this.l.length) {
            newVal = this.l.suffix[idx - this.middleSize];
        }
        else {
            this.result.done = true;
        }
        this.result.value = newVal;
        return this.result;
    };
    return ListIterator;
}());
// prepend & append
function prepend(value, l) {
    var prefixSize = getPrefixSize(l);
    if (prefixSize < 32) {
        return new List(incrementPrefix(l.bits), l.offset, l.length + 1, l.root, l.suffix, affixPush(value, l.prefix, prefixSize));
    }
    else {
        var newList = cloneList(l);
        prependNodeToTree(newList, reverseArray(l.prefix));
        var newPrefix = [value];
        newList.prefix = newPrefix;
        newList.length++;
        newList.bits = setPrefix(1, newList.bits);
        return newList;
    }
}
exports.prepend = prepend;
/**
 * Traverses down the left edge of the tree and copies k nodes.
 * Returns the last copied node.
 * @param l
 * @param k The number of nodes to copy. Will always be at least 1.
 * @param leafSize The number of elements in the leaf that will be
 * inserted.
 */
function copyLeft(l, k, leafSize) {
    var currentNode = cloneNode(l.root); // copy root
    l.root = currentNode; // install copy of root
    for (var i = 1; i < k; ++i) {
        var index = 0; // go left
        if (currentNode.sizes !== undefined) {
            for (var i_1 = 0; i_1 < currentNode.sizes.length; ++i_1) {
                currentNode.sizes[i_1] += leafSize;
            }
        }
        var newNode = cloneNode(currentNode.array[index]);
        // Install the copied node
        currentNode.array[index] = newNode;
        currentNode = newNode;
    }
    return currentNode;
}
function prependSizes(n, sizes) {
    if (sizes === undefined) {
        return undefined;
    }
    else {
        var newSizes = new Array(sizes.length + 1);
        newSizes[0] = n;
        for (var i = 0; i < sizes.length; ++i) {
            newSizes[i + 1] = sizes[i] + n;
        }
        return newSizes;
    }
}
/**
 * Prepends a node to a tree. Either by shifting the nodes in the root
 * left or by increasing the height
 */
function prependTopTree(l, depth, node) {
    var newOffset;
    if (l.root.array.length < branchingFactor) {
        // There is space in the root
        newOffset = Math.pow(32, depth) - 32;
        l.root = new Node(prependSizes(32, l.root.sizes), arrayPrepend(createPath(depth - 1, node), l.root.array));
    }
    else {
        // We need to create a new root
        l.bits = incrementDepth(l.bits);
        var sizes = l.root.sizes === undefined
            ? undefined
            : [32, arrayLast(l.root.sizes) + 32];
        newOffset = depth === 0 ? 0 : Math.pow(32, (depth + 1)) - 32;
        l.root = new Node(sizes, [createPath(depth, node), l.root]);
    }
    return newOffset;
}
/**
 * Takes a RRB-tree and a node tail. It then prepends the node to the
 * tree.
 * @param l The subject for prepending. `l` will be mutated. Nodes in
 * the tree will _not_ be mutated.
 * @param node The node that should be prepended to the tree.
 */
function prependNodeToTree(l, array) {
    if (l.root === undefined) {
        if (getSuffixSize(l) === 0) {
            // ensure invariant 1
            l.bits = setSuffix(array.length, l.bits);
            l.suffix = array;
        }
        else {
            l.root = new Node(undefined, array);
        }
        return l;
    }
    else {
        var node = new Node(undefined, array);
        var depth = getDepth(l);
        var newOffset = 0;
        if (l.root.sizes === undefined) {
            if (l.offset !== 0) {
                newOffset = l.offset - branchingFactor;
                l.root = prependDense(l.root, depth - 1, (l.offset - 1) >> 5, l.offset >> 5, node);
            }
            else {
                // in this case we can be sure that the is not room in the tree
                // for the new node
                newOffset = prependTopTree(l, depth, node);
            }
        }
        else {
            // represents how many nodes _with size-tables_ that we should copy.
            var copyableCount = 0;
            // go down while there is size tables
            var nodesTraversed = 0;
            var currentNode = l.root;
            while (currentNode.sizes !== undefined && nodesTraversed < depth) {
                ++nodesTraversed;
                if (currentNode.array.length < 32) {
                    // there is room if offset is > 0 or if the first node does not
                    // contain as many nodes as it possibly can
                    copyableCount = nodesTraversed;
                }
                currentNode = currentNode.array[0];
            }
            if (l.offset !== 0) {
                var copiedNode = copyLeft(l, nodesTraversed, 32);
                for (var i = 0; i < copiedNode.sizes.length; ++i) {
                    copiedNode.sizes[i] += branchingFactor;
                }
                copiedNode.array[0] = prependDense(copiedNode.array[0], depth - nodesTraversed - 1, (l.offset - 1) >> 5, l.offset >> 5, node);
                l.offset = l.offset - branchingFactor;
                return l;
            }
            else {
                if (copyableCount === 0) {
                    l.offset = prependTopTree(l, depth, node);
                }
                else {
                    var parent_1;
                    var prependableNode = void 0;
                    // Copy the part of the path with size tables
                    if (copyableCount > 1) {
                        parent_1 = copyLeft(l, copyableCount - 1, 32);
                        prependableNode = parent_1.array[0];
                    }
                    else {
                        parent_1 = undefined;
                        prependableNode = l.root;
                    }
                    var path = createPath(depth - copyableCount, node);
                    // add offset
                    l.offset = Math.pow(32, (depth - copyableCount + 1)) - 32;
                    var prepended = nodePrepend(path, 32, prependableNode);
                    if (parent_1 === undefined) {
                        l.root = prepended;
                    }
                    else {
                        parent_1.array[0] = prepended;
                    }
                }
                return l;
            }
        }
        l.offset = newOffset;
        return l;
    }
}
function prependDense(node, depth, index, offset, value) {
    var curOffset = (offset >> (depth * branchBits)) & mask;
    var path = ((index >> (depth * branchBits)) & mask) - curOffset;
    var array;
    if (path < 0) {
        array = arrayPrepend(createPath(depth, value), node.array);
    }
    else {
        array = copyArray(node.array);
        if (depth === 0) {
            array[path] = value;
        }
        else {
            array[path] = updateNode(array[path], depth - 1, index, path === 0 ? offset : 0, value);
        }
    }
    return new Node(node.sizes, array);
}
function append(value, l) {
    var suffixSize = getSuffixSize(l);
    if (suffixSize < 32) {
        return new List(incrementSuffix(l.bits), l.offset, l.length + 1, l.root, affixPush(value, l.suffix, suffixSize), l.prefix);
    }
    var newSuffix = [value];
    var suffixNode = suffixToNode(l.suffix);
    var newList = cloneList(l);
    appendNodeToTree(newList, suffixNode);
    newList.suffix = newSuffix;
    newList.length++;
    newList.bits = setSuffix(1, newList.bits);
    return newList;
}
exports.append = append;
function list() {
    var elements = [];
    for (var _i = 0; _i < arguments.length; _i++) {
        elements[_i] = arguments[_i];
    }
    var l = empty();
    for (var _a = 0, elements_1 = elements; _a < elements_1.length; _a++) {
        var element = elements_1[_a];
        l = append(element, l);
    }
    return l;
}
exports.list = list;
function pair(first, second) {
    return new List(2, 0, 2, undefined, [first, second], emptyAffix);
}
exports.pair = pair;
function empty() {
    return new List(0, 0, 0, undefined, emptyAffix, emptyAffix);
}
exports.empty = empty;
function repeat(value, times) {
    var l = empty();
    while (--times >= 0) {
        l = append(value, l);
    }
    return l;
}
exports.repeat = repeat;
function length(l) {
    return l.length;
}
exports.length = length;
function first(l) {
    if (getPrefixSize(l) !== 0) {
        return arrayLast(l.prefix);
    }
    else if (getSuffixSize(l) !== 0) {
        return arrayFirst(l.suffix);
    }
}
exports.first = first;
function last(l) {
    if (getSuffixSize(l) !== 0) {
        return arrayLast(l.suffix);
    }
    else if (getPrefixSize(l) !== 0) {
        return arrayFirst(l.prefix);
    }
}
exports.last = last;
// map
function mapArray(f, array) {
    var result = new Array(array.length);
    for (var i = 0; i < array.length; ++i) {
        result[i] = f(array[i]);
    }
    return result;
}
function mapNode(f, node, depth) {
    if (depth !== 0) {
        var array = node.array;
        var result = new Array(array.length);
        for (var i = 0; i < array.length; ++i) {
            result[i] = mapNode(f, array[i], depth - 1);
        }
        return new Node(node.sizes, result);
    }
    else {
        return new Node(undefined, mapArray(f, node.array));
    }
}
function mapAffix(f, suffix, length) {
    var newSuffix = new Array(length);
    for (var i = 0; i < length; ++i) {
        newSuffix[i] = f(suffix[i]);
    }
    return newSuffix;
}
function map(f, l) {
    return new List(l.bits, l.offset, l.length, l.root === undefined ? undefined : mapNode(f, l.root, getDepth(l)), mapAffix(f, l.suffix, getSuffixSize(l)), mapAffix(f, l.prefix, getPrefixSize(l)));
}
exports.map = map;
function pluck(key, l) {
    return map(function (a) { return a[key]; }, l);
}
exports.pluck = pluck;
function range(start, end) {
    var list = empty();
    for (var i = start; i < end; ++i) {
        list = append(i, list);
    }
    return list;
}
exports.range = range;
// fold
function foldlSuffix(f, acc, array, length) {
    for (var i = 0; i < length; ++i) {
        acc = f(acc, array[i]);
    }
    return acc;
}
function foldlPrefix(f, acc, array, length) {
    for (var i = length - 1; 0 <= i; --i) {
        acc = f(acc, array[i]);
    }
    return acc;
}
function foldlNode(f, acc, node, depth) {
    var array = node.array;
    if (depth === 0) {
        return foldlSuffix(f, acc, array, array.length);
    }
    for (var i = 0; i < array.length; ++i) {
        acc = foldlNode(f, acc, array[i], depth - 1);
    }
    return acc;
}
function foldl(f, initial, l) {
    var suffixSize = getSuffixSize(l);
    var prefixSize = getPrefixSize(l);
    initial = foldlPrefix(f, initial, l.prefix, prefixSize);
    if (l.root !== undefined) {
        initial = foldlNode(f, initial, l.root, getDepth(l));
    }
    return foldlSuffix(f, initial, l.suffix, suffixSize);
}
exports.foldl = foldl;
exports.reduce = foldl;
function filter(predicate, l) {
    return foldl(function (acc, a) { return (predicate(a) ? append(a, acc) : acc); }, empty(), l);
}
exports.filter = filter;
function reject(predicate, l) {
    return foldl(function (acc, a) { return (predicate(a) ? acc : append(a, acc)); }, empty(), l);
}
exports.reject = reject;
function partition(predicate, l) {
    var _a = foldl(function (obj, a) { return (predicate(a) ? obj.fst = append(a, obj.fst) : obj.snd = append(a, obj.snd), obj); }, { fst: empty(), snd: empty() }, l), fst = _a.fst, snd = _a.snd;
    return pair(fst, snd);
}
exports.partition = partition;
function join(separator, l) {
    return foldl(function (a, b) { return (a.length === 0 ? b : a + separator + b); }, "", l);
}
exports.join = join;
function foldrSuffix(f, initial, array, length) {
    var acc = initial;
    for (var i = length - 1; 0 <= i; --i) {
        acc = f(array[i], acc);
    }
    return acc;
}
function foldrPrefix(f, initial, array, length) {
    var acc = initial;
    for (var i = 0; i < length; ++i) {
        acc = f(array[i], acc);
    }
    return acc;
}
function foldrNode(f, initial, _a, depth) {
    var array = _a.array;
    if (depth === 0) {
        return foldrSuffix(f, initial, array, array.length);
    }
    var acc = initial;
    for (var i = array.length - 1; 0 <= i; --i) {
        acc = foldrNode(f, acc, array[i], depth - 1);
    }
    return acc;
}
function foldr(f, initial, l) {
    var suffixSize = getSuffixSize(l);
    var prefixSize = getPrefixSize(l);
    var acc = foldrSuffix(f, initial, l.suffix, suffixSize);
    if (l.root !== undefined) {
        acc = foldrNode(f, acc, l.root, getDepth(l));
    }
    return foldrPrefix(f, acc, l.prefix, prefixSize);
}
exports.foldr = foldr;
exports.reduceRight = foldr;
function flatten(nested) {
    return foldl(concat, empty(), nested);
}
exports.flatten = flatten;
function foldlSuffixCb(cb, state, array, length) {
    for (var i = 0; i < length && cb(array[i], state); ++i) { }
    return i === length;
}
function foldlPrefixCb(cb, state, array, length) {
    for (var i = length - 1; 0 <= i && cb(array[i], state); --i) { }
    return i === -1;
}
function foldlNodeCb(cb, state, node, depth) {
    var array = node.array;
    if (depth === 0) {
        return foldlSuffixCb(cb, state, array, array.length);
    }
    for (var i = 0; i < array.length && foldlNodeCb(cb, state, array[i], depth - 1); ++i) { }
    return i === array.length;
}
/**
 * This function is a lot like a fold. But the reducer function is
 * supposed to mutate its state instead of returning it. Instead of
 * returning a new state it returns a boolean that tells wether or not
 * to continue the fold. `true` indicates that the folding should
 * continue.
 */
function foldlCb(cb, state, l) {
    var suffixSize = getSuffixSize(l);
    var prefixSize = getPrefixSize(l);
    if (foldlPrefixCb(cb, state, l.prefix, prefixSize)) {
        if (l.root !== undefined) {
            if (foldlNodeCb(cb, state, l.root, getDepth(l))) {
                foldlSuffixCb(cb, state, l.suffix, suffixSize);
            }
        }
        else {
            foldlSuffixCb(cb, state, l.suffix, suffixSize);
        }
    }
    return state;
}
function everyCb(value, state) {
    return (state.result = state.predicate(value));
}
function every(predicate, l) {
    return foldlCb(everyCb, { predicate: predicate, result: true }, l).result;
}
exports.every = every;
exports.all = every;
function someCb(value, state) {
    return !(state.result = state.predicate(value));
}
function some(predicate, l) {
    return foldlCb(someCb, { predicate: predicate, result: false }, l).result;
}
exports.some = some;
// tslint:disable-next-line:variable-name
exports.any = some;
function none(predicate, l) {
    return !some(predicate, l);
}
exports.none = none;
function findCb(value, state) {
    if (state.predicate(value)) {
        state.result = value;
        return false;
    }
    else {
        return true;
    }
}
function find(predicate, l) {
    return foldlCb(findCb, { predicate: predicate, result: undefined }, l)
        .result;
}
exports.find = find;
function indexOfCb(value, state) {
    ++state.index;
    return !(state.found = elementEquals(value, state.element));
}
function indexOf(element, l) {
    var _a = foldlCb(indexOfCb, { element: element, found: false, index: -1 }, l), found = _a.found, index = _a.index;
    return found ? index : -1;
}
exports.indexOf = indexOf;
function findIndexCb(value, state) {
    ++state.index;
    return !(state.found = state.predicate(value));
}
function findIndex(predicate, l) {
    var _a = foldlCb(findIndexCb, { predicate: predicate, found: false, index: -1 }, l), found = _a.found, index = _a.index;
    return found ? index : -1;
}
exports.findIndex = findIndex;
var containsState = {
    element: undefined,
    result: false
};
function containsCb(value, state) {
    return !(state.result = value === state.element);
}
function includes(element, l) {
    containsState.element = element;
    containsState.result = false;
    return foldlCb(containsCb, containsState, l).result;
}
exports.includes = includes;
exports.contains = includes;
var equalsState = {
    iterator: undefined,
    equals: true
};
function equalsCb(value2, state) {
    var value = state.iterator.next().value;
    return (state.equals = elementEquals(value, value2));
}
function equals(firstList, secondList) {
    if (firstList === secondList) {
        return true;
    }
    else if (firstList.length !== secondList.length) {
        return false;
    }
    else {
        equalsState.iterator = secondList[Symbol.iterator]();
        equalsState.equals = true;
        return foldlCb(equalsCb, equalsState, firstList).equals;
    }
}
exports.equals = equals;
// concat
var eMax = 2;
function createConcatPlan(array) {
    var sizes = [];
    var sum = 0;
    for (var i_2 = 0; i_2 < array.length; ++i_2) {
        sum += array[i_2].array.length; // FIXME: maybe only access array once
        sizes[i_2] = array[i_2].array.length;
    }
    var optimalLength = Math.ceil(sum / branchingFactor);
    var n = array.length;
    var i = 0;
    if (optimalLength + eMax >= n) {
        return undefined; // no rebalancing needed
    }
    while (optimalLength + eMax < n) {
        while (sizes[i] > branchingFactor - eMax / 2) {
            // Skip nodes that are already sufficiently balanced
            ++i;
        }
        // the node at this index is too short
        var remaining = sizes[i]; // number of elements to re-distribute
        do {
            var size = Math.min(remaining + sizes[i + 1], branchingFactor);
            sizes[i] = size;
            remaining = remaining - (size - sizes[i + 1]);
            ++i;
        } while (remaining > 0);
        // Shift nodes after
        for (var j = i; j <= n - 1; ++j) {
            sizes[j] = sizes[j + 1];
        }
        --i;
        --n;
    }
    sizes.length = n;
    return sizes;
}
/**
 * Combines the children of three nodes into an array. The last child
 * of `left` and the first child of `right is ignored as they've been
 * concatenated into `center`.
 */
function concatNodeMerge(left, center, right) {
    var array = [];
    if (left !== undefined) {
        for (var i = 0; i < left.array.length - 1; ++i) {
            array.push(left.array[i]);
        }
    }
    for (var i = 0; i < center.array.length; ++i) {
        array.push(center.array[i]);
    }
    if (right !== undefined) {
        for (var i = 1; i < right.array.length; ++i) {
            array.push(right.array[i]);
        }
    }
    return array;
}
function executeConcatPlan(merged, plan, height) {
    var result = [];
    var sourceIdx = 0; // the current node we're copying from
    var offset = 0; // elements in source already used
    for (var _i = 0, plan_1 = plan; _i < plan_1.length; _i++) {
        var toMove = plan_1[_i];
        var source = merged[sourceIdx].array;
        if (toMove === source.length && offset === 0) {
            // source matches target exactly, reuse source
            result.push(merged[sourceIdx]);
            ++sourceIdx;
        }
        else {
            var node = new Node(undefined, []);
            while (toMove > 0) {
                var available = source.length - offset;
                var itemsToCopy = Math.min(toMove, available);
                pushElements(source, node.array, offset, itemsToCopy);
                if (toMove >= available) {
                    ++sourceIdx;
                    source = merged[sourceIdx].array;
                    offset = 0;
                }
                else {
                    offset += itemsToCopy;
                }
                toMove -= itemsToCopy;
            }
            if (height > 1) {
                // Set sizes on children unless they are leaf nodes
                setSizes(node, height - 1);
            }
            result.push(node);
        }
    }
    return result;
}
/**
 * Takes three nodes and returns a new node with the content of the
 * three nodes. Note: The returned node does not have its size table
 * set correctly. The caller must do that.
 */
function rebalance(left, center, right, height, top) {
    var merged = concatNodeMerge(left, center, right);
    var plan = createConcatPlan(merged);
    var balanced = plan !== undefined ? executeConcatPlan(merged, plan, height) : merged;
    if (balanced.length <= branchingFactor) {
        if (top === true) {
            return new Node(undefined, balanced);
        }
        else {
            // Return a single node with extra height for balancing at next
            // level
            return new Node(undefined, [
                setSizes(new Node(undefined, balanced), height)
            ]);
        }
    }
    else {
        return new Node(undefined, [
            setSizes(new Node(undefined, balanced.slice(0, branchingFactor)), height),
            setSizes(new Node(undefined, balanced.slice(branchingFactor)), height)
        ]);
    }
}
function concatSubTree(left, lDepth, right, rDepth, isTop) {
    if (lDepth > rDepth) {
        var c = concatSubTree(arrayLast(left.array), lDepth - 1, right, rDepth, false);
        return rebalance(left, c, undefined, lDepth, isTop);
    }
    else if (lDepth < rDepth) {
        var c = concatSubTree(left, lDepth, arrayFirst(right.array), rDepth - 1, false);
        return rebalance(undefined, c, right, rDepth, isTop);
    }
    else if (lDepth === 0) {
        return new Node(undefined, [left, right]);
    }
    else {
        var c = concatSubTree(arrayLast(left.array), lDepth - 1, arrayFirst(right.array), rDepth - 1, false);
        return rebalance(left, c, right, lDepth, isTop);
    }
}
function getHeight(node) {
    if (node.array[0] instanceof Node) {
        return 1 + getHeight(node.array[0]);
    }
    else {
        return 0;
    }
}
/**
 * Takes a RRB-tree and a node tail. It then appends the node to the
 * tree.
 * @param l The subject for appending. `l` will be mutated. Nodes in
 * the tree will _not_ be mutated.
 * @param node The node that should be appended to the tree.
 */
function appendNodeToTree(l, node) {
    if (l.root === undefined) {
        // The old list has no content in tree, all content is in affixes
        if (getPrefixSize(l) === 0) {
            l.bits = setPrefix(node.array.length, l.bits);
            l.prefix = reverseArray(node.array);
        }
        else {
            l.root = node;
        }
        return l;
    }
    var depth = getDepth(l);
    var index = l.length - 1 - getPrefixSize(l);
    var nodesToCopy = 0;
    var nodesVisited = 0;
    var shift = depth * 5;
    var currentNode = l.root;
    if (Math.pow(32, (depth + 1)) < index) {
        shift = 0; // there is no room
        nodesVisited = depth;
    }
    while (shift > 5) {
        var childIndex = void 0;
        if (currentNode.sizes === undefined) {
            // does not have size table
            childIndex = (index >> shift) & mask;
            index &= ~(mask << shift); // wipe just used bits
        }
        else {
            childIndex = currentNode.array.length - 1;
            index -= currentNode.sizes[childIndex - 1];
        }
        nodesVisited++;
        if (childIndex < mask) {
            // we are not going down the far right path, this implies that
            // there is still room in the current node
            nodesToCopy = nodesVisited;
        }
        currentNode = currentNode.array[childIndex];
        if (currentNode === undefined) {
            // This will only happened in a pvec subtree. The index does not
            // exist so we'll have to create a new path from here on.
            nodesToCopy = nodesVisited;
            shift = 5; // Set shift to break out of the while-loop
        }
        shift -= 5;
    }
    if (shift !== 0) {
        nodesVisited++;
        if (currentNode.array.length < branchingFactor) {
            // there is room in the found node
            nodesToCopy = nodesVisited;
        }
    }
    if (nodesToCopy === 0) {
        // there was no room in the found node
        var newPath = nodesVisited === 0 ? node : createPath(nodesVisited, node);
        var newRoot = new Node(undefined, [l.root, newPath]);
        l.root = newRoot;
        l.bits = incrementDepth(l.bits);
    }
    else {
        var copiedNode = copyFirstK(l, l, nodesToCopy, node.array.length);
        var leaf = appendEmpty(copiedNode, depth - nodesToCopy);
        leaf.array.push(node);
    }
    return l;
}
/**
 * Traverses down the right edge of the tree and copies k nodes
 * @param oldList
 * @param newList
 * @param k The number of nodes to copy. Will always be at least 1.
 * @param leafSize The number of elements in the leaf that will be inserted.
 */
function copyFirstK(oldList, newList, k, leafSize) {
    var currentNode = cloneNode(oldList.root); // copy root
    newList.root = currentNode; // install root
    for (var i = 1; i < k; ++i) {
        var index = currentNode.array.length - 1;
        if (currentNode.sizes !== undefined) {
            currentNode.sizes[index] += leafSize;
        }
        var newNode = cloneNode(currentNode.array[index]);
        // Install the copied node
        currentNode.array[index] = newNode;
        currentNode = newNode;
    }
    if (currentNode.sizes !== undefined) {
        currentNode.sizes.push(arrayLast(currentNode.sizes) + leafSize);
    }
    return currentNode;
}
function appendEmpty(node, depth) {
    if (depth === 0) {
        return node;
    }
    var current = new Node(undefined, []);
    node.array.push(current);
    for (var i = 1; i < depth; ++i) {
        var newNode = new Node(undefined, []);
        current.array[0] = newNode;
        current = newNode;
    }
    return current;
}
/*
function concatSuffix<A>(
  left: A[], lSize: number, right: A[], rSize: number
): A[] {
  const newArray = new Array(lSize + rSize);
  for (let i = 0; i < lSize; ++i) {
    newArray[i] = left[i];
  }
  for (let i = 0; i < rSize; ++i) {
    newArray[lSize + i] = right[i];
  }
  return newArray;
}
*/
var concatBuffer = new Array(3);
function concatAffixes(left, right) {
    // TODO: Try and find a neat way to reduce the LOC here
    var nr = 0;
    var arrIdx = 0;
    var i = 0;
    var length = getSuffixSize(left);
    concatBuffer[nr] = [];
    for (i = 0; i < length; ++i) {
        concatBuffer[nr][arrIdx] = left.suffix[i];
        if (++arrIdx === 32) {
            arrIdx = 0;
            ++nr;
            concatBuffer[nr] = [];
        }
    }
    length = getPrefixSize(right);
    for (i = 0; i < length; ++i) {
        concatBuffer[nr][arrIdx] = right.prefix[right.prefix.length - 1 - i];
        if (++arrIdx === 32) {
            arrIdx = 0;
            ++nr;
            concatBuffer[nr] = [];
        }
    }
    length = getSuffixSize(right);
    for (i = 0; i < length; ++i) {
        concatBuffer[nr][arrIdx] = right.suffix[i];
        if (++arrIdx === 32) {
            arrIdx = 0;
            ++nr;
            concatBuffer[nr] = [];
        }
    }
    return nr;
}
function concat(left, right) {
    if (left.length === 0) {
        return right;
    }
    else if (right.length === 0) {
        return left;
    }
    var newSize = left.length + right.length;
    var rightSuffixSize = getSuffixSize(right);
    var newList = cloneList(left);
    if (right.root === undefined) {
        // right is nothing but a prefix and a suffix
        var nrOfAffixes = concatAffixes(left, right);
        for (var i = 0; i < nrOfAffixes; ++i) {
            newList = appendNodeToTree(newList, new Node(undefined, concatBuffer[i]));
            newList.length += concatBuffer[i].length;
            // wipe pointer, otherwise it might end up keeping the array alive
            concatBuffer[i] = undefined;
        }
        newList.length = newSize;
        newList.suffix = concatBuffer[nrOfAffixes];
        newList.bits = setSuffix(concatBuffer[nrOfAffixes].length, newList.bits);
        concatBuffer[nrOfAffixes] = undefined;
        return newList;
    }
    else {
        newList = appendNodeToTree(newList, suffixToNode(left.suffix));
        newList.length += getSuffixSize(left);
        newList = appendNodeToTree(newList, prefixToNode(right.prefix));
        var newNode = concatSubTree(newList.root, getDepth(newList), right.root, getDepth(right), true);
        var newDepth = getHeight(newNode);
        setSizes(newNode, newDepth);
        var bits = createBits(newDepth, getPrefixSize(newList), rightSuffixSize);
        // FIXME: Return `newList` here
        return new List(bits, 0, newSize, newNode, right.suffix, newList.prefix);
    }
}
exports.concat = concat;
function update(index, a, l) {
    var prefixSize = getPrefixSize(l);
    var suffixSize = getSuffixSize(l);
    var newList = cloneList(l);
    if (index < prefixSize) {
        var newPrefix = copyArray(newList.prefix);
        newPrefix[newPrefix.length - index - 1] = a;
        newList.prefix = newPrefix;
    }
    else if (index >= l.length - suffixSize) {
        var newSuffix = copyArray(newList.suffix);
        newSuffix[index - (l.length - suffixSize)] = a;
        newList.suffix = newSuffix;
    }
    else {
        newList.root = updateNode(l.root, getDepth(l), index - prefixSize + l.offset, l.offset, a);
    }
    return newList;
}
exports.update = update;
function adjust(f, index, l) {
    return update(index, f(nth(index, l)), l);
}
exports.adjust = adjust;
// slice and slice based functions
var newAffix;
function sliceLeft(tree, depth, index, offset) {
    var curOffset = (offset >> (depth * branchBits)) & mask;
    var path = ((index >> (depth * branchBits)) & mask) - curOffset;
    if (depth === 0) {
        newAffix = tree.array.slice(path).reverse();
        // this leaf node is moved up as a suffix so there is nothing here
        // after slicing
        return undefined;
    }
    else {
        // slice the child
        var child = sliceLeft(tree.array[path], depth - 1, index, path === 0 ? offset : 0);
        if (child === undefined) {
            // there is nothing in the child after slicing so we don't include it
            ++path;
            if (path === tree.array.length) {
                return undefined;
            }
        }
        var array = tree.array.slice(path);
        if (child !== undefined) {
            array[0] = child;
        }
        return new Node(tree.sizes, array); // FIXME: handle the size table
    }
}
function sliceRight(tree, depth, index, offset) {
    var curOffset = (offset >> (depth * branchBits)) & mask;
    var path = ((index >> (depth * branchBits)) & mask) - curOffset;
    if (depth === 0) {
        newAffix = tree.array.slice(0, path + 1);
        // this leaf node is moved up as a suffix so there is nothing here
        // after slicing
        return undefined;
    }
    else {
        // slice the child, note that we subtract 1 then the radix lookup
        // algorithm can find the last element that we want to include
        // and sliceRight will do a slice that is inclusive on the index.
        var child = sliceRight(tree.array[path], depth - 1, index, path === 0 ? offset : 0);
        if (child === undefined) {
            // there is nothing in the child after slicing so we don't include it
            --path;
            if (path === -1) {
                return undefined;
            }
        }
        // note that we add 1 to the path since we want the slice to be
        // inclusive on the end index. Only at the leaf level do we want
        // to do an exclusive slice.
        var array = tree.array.slice(0, path + 1);
        if (child !== undefined) {
            array[array.length - 1] = child;
        }
        return new Node(tree.sizes, array); // FIXME: handle the size table
    }
}
function sliceTreeList(from, to, tree, depth, offset, l) {
    var curOffset = (offset >> (depth * branchBits)) & mask;
    var pathLeft = ((from >> (depth * branchBits)) & mask) - curOffset;
    var pathRight = ((to >> (depth * branchBits)) & mask) - curOffset;
    if (depth === 0) {
        // we are slicing a piece off a leaf node
        l.prefix = emptyAffix;
        l.suffix = tree.array.slice(pathLeft, pathRight + 1);
        l.root = undefined;
        l.bits = setSuffix(pathRight - pathLeft + 1, 0);
        return l;
    }
    else if (pathLeft === pathRight) {
        // Both ends are located in the same subtree, this means that we
        // can reduce the height
        // l.bits = decrementDepth(l.bits);
        // return sliceTreeList(from, to, tree.array[pathLeft], depth - 1, pathLeft === 0 ? offset : 0, l);
        var rec = sliceTreeList(from, to, tree.array[pathLeft], depth - 1, pathLeft === 0 ? offset : 0, l);
        if (rec.root !== undefined) {
            rec.root = new Node(undefined, [rec.root]);
        }
        return rec;
    }
    else {
        var childLeft = sliceLeft(tree.array[pathLeft], depth - 1, from, pathLeft === 0 ? offset : 0);
        l.bits = setPrefix(newAffix.length, l.bits);
        l.prefix = newAffix;
        var childRight = sliceRight(tree.array[pathRight], depth - 1, to, 0);
        l.bits = setSuffix(newAffix.length, l.bits);
        l.suffix = newAffix;
        if (childLeft === undefined) {
            ++pathLeft;
        }
        if (childRight === undefined) {
            --pathRight;
        }
        if (pathLeft > pathRight) {
            // there is no tree left
            l.bits = setDepth(0, l.bits);
            l.root = undefined;
            // } else if (pathLeft === pathRight) {
            // height can be reduced
            // l.bits = decrementDepth(l.bits);
            // l.root = childLeft === undefined ? childRight : childLeft;
        }
        else {
            var array = tree.array.slice(pathLeft, pathRight + 1);
            if (childLeft !== undefined) {
                array[0] = childLeft;
            }
            if (childRight !== undefined) {
                array[array.length - 1] = childRight;
            }
            l.root = new Node(tree.sizes, array);
        }
        return l;
    }
}
function slice(from, to, l) {
    var bits = l.bits, length = l.length;
    to = Math.min(length, to);
    // handle negative indices
    if (from < 0) {
        from = length + from;
    }
    if (to < 0) {
        to = length + to;
    }
    if (to <= from || to <= 0 || length <= from) {
        return empty();
    }
    // return list unchanged if we are slicing nothing off
    if (from <= 0 && length <= to) {
        return l;
    }
    var newLength = to - from;
    var prefixSize = getPrefixSize(l);
    var suffixSize = getSuffixSize(l);
    // both indices lie in the prefix
    if (to <= prefixSize) {
        return new List(setPrefix(newLength, 0), 0, newLength, undefined, emptyAffix, l.prefix.slice(l.prefix.length - to, l.prefix.length - from));
    }
    var suffixStart = length - suffixSize;
    // both indices lie in the suffix
    if (suffixStart <= from) {
        return new List(setSuffix(newLength, 0), 0, newLength, undefined, l.suffix.slice(from - suffixStart, to - suffixStart), emptyAffix);
    }
    var newList = cloneList(l);
    // both indices lie in the tree
    if (prefixSize <= from && to <= length - suffixSize) {
        sliceTreeList(from - prefixSize + l.offset, to - prefixSize + l.offset - 1, l.root, getDepth(l), l.offset, newList);
        if (newList.root !== undefined) {
            newList.offset += from - prefixSize + getPrefixSize(newList);
        }
        newList.length = to - from;
        return newList;
    }
    // we need to slice something off of the left
    if (0 < from) {
        if (from < prefixSize) {
            // do a cheap slice by setting prefix length
            bits = setPrefix(prefixSize - from, bits);
        }
        else {
            // if we're here `to` can't lie in the tree, so we can set the
            // root
            newList.root = sliceLeft(newList.root, getDepth(l), from - prefixSize + l.offset, l.offset);
            bits = setPrefix(newAffix.length, bits);
            newList.offset += from - prefixSize + newAffix.length;
            prefixSize = newAffix.length;
            newList.prefix = newAffix;
        }
        newList.length -= from;
    }
    if (to < length) {
        if (length - to < suffixSize) {
            bits = setSuffix(suffixSize - (length - to), bits);
        }
        else {
            newList.root = sliceRight(newList.root, getDepth(l), to - prefixSize + newList.offset - 1, newList.offset);
            if (newList.root === undefined) {
                bits = setDepth(0, bits);
            }
            bits = setSuffix(newAffix.length, bits);
            newList.suffix = newAffix;
        }
        newList.length -= length - to;
    }
    newList.bits = bits;
    return newList;
}
exports.slice = slice;
function take(n, l) {
    return slice(0, n, l);
}
exports.take = take;
function findNotIndexCb(value, state) {
    ++state.index;
    return state.predicate(value);
}
function takeWhile(predicate, l) {
    var index = foldlCb(findNotIndexCb, { predicate: predicate, index: -1 }, l).index;
    return slice(0, index, l);
}
exports.takeWhile = takeWhile;
function dropWhile(predicate, l) {
    var index = foldlCb(findNotIndexCb, { predicate: predicate, index: -1 }, l).index;
    return slice(index, l.length, l);
}
exports.dropWhile = dropWhile;
function takeLast(n, l) {
    return slice(l.length - n, l.length, l);
}
exports.takeLast = takeLast;
function splitAt(index, l) {
    return [slice(0, index, l), slice(index, l.length, l)];
}
exports.splitAt = splitAt;
function remove(from, amount, l) {
    return concat(slice(0, from, l), slice(from + amount, l.length, l));
}
exports.remove = remove;
function drop(n, l) {
    return slice(n, l.length, l);
}
exports.drop = drop;
function dropLast(n, l) {
    return slice(0, l.length - n, l);
}
exports.dropLast = dropLast;
function pop(l) {
    return slice(0, -1, l);
}
exports.pop = pop;
exports.init = pop;
function tail(l) {
    return slice(1, l.length, l);
}
exports.tail = tail;
function arrayPush(array, a) {
    array.push(a);
    return array;
}
function toArray(l) {
    return foldl(arrayPush, [], l);
}
exports.toArray = toArray;
function fromArray(array) {
    var l = empty();
    for (var i = 0; i < array.length; ++i) {
        l = append(array[i], l);
    }
    return l;
}
exports.fromArray = fromArray;
function fromIterable(iterable) {
    var l = empty();
    var iterator = iterable[Symbol.iterator]();
    var cur;
    // tslint:disable-next-line:no-conditional-assignment
    while ((cur = iterator.next()).done === false) {
        l = append(cur.value, l);
    }
    return l;
}
exports.fromIterable = fromIterable;
function insert(index, element, l) {
    return concat(append(element, slice(0, index, l)), slice(index, l.length, l));
}
exports.insert = insert;
function insertAll(index, elements, l) {
    return concat(concat(slice(0, index, l), elements), slice(index, l.length, l));
}
exports.insertAll = insertAll;
//# sourceMappingURL=index.js.map