list/dist/index.js

"use strict";
var __extends = (this && this.__extends) || (function () {
    var extendStatics = function (d, b) {
        extendStatics = Object.setPrototypeOf ||
            ({ __proto__: [] } instanceof Array && function (d, b) { d.__proto__ = b; }) ||
            function (d, b) { for (var p in b) if (b.hasOwnProperty(p)) d[p] = b[p]; };
        return extendStatics(d, b);
    };
    return function (d, b) {
        extendStatics(d, b);
        function __() { this.constructor = d; }
        d.prototype = b === null ? Object.create(b) : (__.prototype = b.prototype, new __());
    };
})();
Object.defineProperty(exports, "__esModule", { value: true });
var branchingFactor = 32;
var branchBits = 5;
var mask = 31;
function isSetoid(a) {
    return a && typeof a["fantasy-land/equals"] === "function";
}
function elementEquals(a, b) {
    if (a === b) {
        return true;
    }
    else if (isSetoid(a)) {
        return a["fantasy-land/equals"](b);
    }
    else {
        return false;
    }
}
function createPath(depth, value) {
    var current = value;
    for (var i = 0; i < depth; ++i) {
        current = new Node(undefined, [current]);
    }
    return current;
}
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;
}
function reverseArray(array) {
    return array.slice().reverse();
}
function arrayFirst(array) {
    return array[0];
}
function arrayLast(array) {
    return array[array.length - 1];
}
var pathResult = { path: 0, index: 0, updatedOffset: 0 };
function getPath(index, offset, depth, sizes) {
    if (sizes === undefined && offset !== 0) {
        pathResult.updatedOffset = 0;
        index = handleOffset(depth, offset, index);
    }
    var path = (index >> (depth * branchBits)) & mask;
    if (sizes !== undefined) {
        while (sizes[path] <= index) {
            path++;
        }
        var traversed = path === 0 ? 0 : sizes[path - 1];
        index -= traversed;
        pathResult.updatedOffset = offset;
    }
    pathResult.path = path;
    pathResult.index = index;
    return pathResult;
}
function updateNode(node, depth, index, offset, value) {
    var _a = getPath(index, offset, depth, node.sizes), path = _a.path, newIndex = _a.index, updatedOffset = _a.updatedOffset;
    var array = copyArray(node.array);
    array[path] =
        depth > 0
            ? updateNode(array[path], depth - 1, newIndex, updatedOffset, value)
            : value;
    return new Node(node.sizes, array);
}
var Node = (function () {
    function Node(sizes, array) {
        this.sizes = sizes;
        this.array = array;
    }
    return Node;
}());
exports.Node = Node;
function cloneNode(_a) {
    var sizes = _a.sizes, array = _a.array;
    return new Node(sizes === undefined ? undefined : copyArray(sizes), copyArray(array));
}
var emptyAffix = [0];
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) {
    return bits - (1 << (affixBits * 2));
}
var List = (function () {
    function List(bits, offset, length, prefix, root, suffix) {
        this.bits = bits;
        this.offset = offset;
        this.length = length;
        this.prefix = prefix;
        this.root = root;
        this.suffix = suffix;
    }
    List.prototype[Symbol.iterator] = function () {
        return new ForwardListIterator(this);
    };
    List.prototype.toJSON = function () {
        return toArray(this);
    };
    return List;
}());
exports.List = List;
function cloneList(l) {
    return new List(l.bits, l.offset, l.length, l.prefix, l.root, l.suffix);
}
var ListIterator = (function () {
    function ListIterator(l, direction) {
        this.l = l;
        this.result = { done: false, value: undefined };
        this.idx = direction === 1 ? -1 : l.length;
        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;
                var idx = direction === 1 ? 0 : currentNode.length - 1;
                this.indices[i] = idx;
                currentNode = currentNode[idx].array;
            }
            this.indices[0] -= direction;
        }
    }
    return ListIterator;
}());
var ForwardListIterator = (function (_super) {
    __extends(ForwardListIterator, _super);
    function ForwardListIterator(l) {
        return _super.call(this, l, 1) || this;
    }
    ForwardListIterator.prototype.nextInTree = function () {
        for (var i = 0; ++this.indices[i] === this.stack[i].length; ++i) {
            this.indices[i] = 0;
        }
        for (; 0 < i; --i) {
            this.stack[i - 1] = this.stack[i][this.indices[i]].array;
        }
    };
    ForwardListIterator.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 ForwardListIterator;
}(ListIterator));
var BackwardsListIterator = (function (_super) {
    __extends(BackwardsListIterator, _super);
    function BackwardsListIterator(l) {
        return _super.call(this, l, -1) || this;
    }
    BackwardsListIterator.prototype.prevInTree = function () {
        for (var i = 0; this.indices[i] === 0; ++i) { }
        --this.indices[i];
        for (; 0 < i; --i) {
            var n = this.stack[i][this.indices[i]].array;
            this.stack[i - 1] = n;
            this.indices[i - 1] = n.length - 1;
        }
    };
    BackwardsListIterator.prototype.next = function () {
        var newVal;
        var idx = --this.idx;
        if (this.middleSize <= idx) {
            newVal = this.l.suffix[idx - this.middleSize];
        }
        else if (this.prefixSize <= idx) {
            this.prevInTree();
            newVal = this.stack[0][this.indices[0]];
        }
        else if (0 <= idx) {
            newVal = this.l.prefix[this.prefixSize - idx - 1];
        }
        else {
            this.result.done = true;
        }
        this.result.value = newVal;
        return this.result;
    };
    return BackwardsListIterator;
}(ListIterator));
function backwards(l) {
    var _a;
    return _a = {},
        _a[Symbol.iterator] = function () {
            return new BackwardsListIterator(l);
        },
        _a;
}
exports.backwards = backwards;
function emptyPushable() {
    return new List(0, 0, 0, [], undefined, []);
}
function push(value, l) {
    var suffixSize = getSuffixSize(l);
    if (l.length === 0) {
        l.bits = setPrefix(1, l.bits);
        l.prefix = [value];
    }
    else if (suffixSize < 32) {
        l.bits = incrementSuffix(l.bits);
        l.suffix.push(value);
    }
    else if (l.root === undefined) {
        l.root = new Node(undefined, l.suffix);
        l.suffix = [value];
        l.bits = setSuffix(1, l.bits);
    }
    else {
        var newNode = new Node(undefined, l.suffix);
        var index = l.length - 1 - 32 + 1;
        var current = l.root;
        var depth = getDepth(l);
        l.suffix = [value];
        l.bits = setSuffix(1, l.bits);
        if (index - 1 < Math.pow(branchingFactor, (depth + 1))) {
            for (; depth >= 0; --depth) {
                var path = (index >> (depth * branchBits)) & mask;
                if (path < current.array.length) {
                    current = current.array[path];
                }
                else {
                    current.array.push(createPath(depth - 1, newNode));
                    break;
                }
            }
        }
        else {
            l.bits = incrementDepth(l.bits);
            l.root = new Node(undefined, [l.root, createPath(depth, newNode)]);
        }
    }
    l.length++;
    return l;
}
function list() {
    var elements = [];
    for (var _i = 0; _i < arguments.length; _i++) {
        elements[_i] = arguments[_i];
    }
    var l = emptyPushable();
    for (var _a = 0, elements_1 = elements; _a < elements_1.length; _a++) {
        var element = elements_1[_a];
        push(element, l);
    }
    return l;
}
exports.list = list;
function empty() {
    return new List(0, 0, 0, emptyAffix, undefined, emptyAffix);
}
exports.empty = empty;
function of(a) {
    return list(a);
}
exports.of = of;
function pair(first, second) {
    return new List(2, 0, 2, emptyAffix, undefined, [first, second]);
}
exports.pair = pair;
function from(sequence) {
    var l = emptyPushable();
    if (sequence.length > 0 && (sequence[0] !== undefined || 0 in sequence)) {
        for (var i = 0; i < sequence.length; ++i) {
            push(sequence[i], l);
        }
    }
    else if (Symbol.iterator in sequence) {
        var iterator = sequence[Symbol.iterator]();
        var cur = void 0;
        while (!(cur = iterator.next()).done) {
            push(cur.value, l);
        }
    }
    return l;
}
exports.from = from;
function range(start, end) {
    var list = emptyPushable();
    for (var i = start; i < end; ++i) {
        push(i, list);
    }
    return list;
}
exports.range = range;
function repeat(value, times) {
    var l = emptyPushable();
    while (--times >= 0) {
        push(value, l);
    }
    return l;
}
exports.repeat = repeat;
function times(func, times) {
    var l = emptyPushable();
    for (var i = 0; i < times; i++) {
        push(func(i), l);
    }
    return l;
}
exports.times = times;
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, offset, index) {
    var path;
    var current = node;
    while (current.sizes !== undefined) {
        path = (index >> (depth * branchBits)) & mask;
        while (current.sizes[path] <= index) {
            path++;
        }
        if (path !== 0) {
            index -= current.sizes[path - 1];
            offset = 0;
        }
        depth--;
        current = current.array[path];
    }
    return nodeNthDense(current, depth, offset === 0 ? index : handleOffset(depth, offset, index));
}
function nth(index, l) {
    if (index < 0 || l.length <= index) {
        return undefined;
    }
    var prefixSize = getPrefixSize(l);
    var suffixSize = getSuffixSize(l);
    if (index < prefixSize) {
        return l.prefix[prefixSize - index - 1];
    }
    else if (index >= l.length - suffixSize) {
        return l.suffix[index - (l.length - suffixSize)];
    }
    var offset = l.offset;
    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, offset, index - prefixSize);
}
exports.nth = nth;
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;
}
function sizeOfSubtree(node, height) {
    if (height !== 0) {
        if (node.sizes !== undefined) {
            return arrayLast(node.sizes);
        }
        else {
            var lastSize = sizeOfSubtree(arrayLast(node.array), height - 1);
            return ((node.array.length - 1) << (height * branchBits)) + lastSize;
        }
    }
    else {
        return node.array.length;
    }
}
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;
    }
}
function prepend(value, l) {
    var prefixSize = getPrefixSize(l);
    if (prefixSize < 32) {
        return new List(incrementPrefix(l.bits), l.offset, l.length + 1, affixPush(value, l.prefix, prefixSize), l.root, l.suffix);
    }
    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;
function copyLeft(l, k) {
    var currentNode = cloneNode(l.root);
    l.root = currentNode;
    for (var i = 1; i < k; ++i) {
        var index = 0;
        if (currentNode.sizes !== undefined) {
            for (var i_1 = 0; i_1 < currentNode.sizes.length; ++i_1) {
                currentNode.sizes[i_1] += 32;
            }
        }
        var newNode = cloneNode(currentNode.array[index]);
        currentNode.array[index] = newNode;
        currentNode = newNode;
    }
    return currentNode;
}
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);
}
function prependTopTree(l, depth, node) {
    var newOffset;
    if (l.root.array.length < branchingFactor) {
        newOffset = Math.pow(32, depth) - 32;
        l.root = new Node(undefined, arrayPrepend(createPath(depth - 1, node), l.root.array));
    }
    else {
        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;
}
function prependNodeToTree(l, array) {
    if (l.root === undefined) {
        if (getSuffixSize(l) === 0) {
            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_1 = 0;
        if (l.root.sizes === undefined) {
            if (l.offset !== 0) {
                newOffset_1 = l.offset - branchingFactor;
                l.root = prependDense(l.root, depth, l.offset, node);
            }
            else {
                newOffset_1 = prependTopTree(l, depth, node);
            }
        }
        else {
            var copyableCount = 0;
            var nodesTraversed = 0;
            var currentNode = l.root;
            while (currentNode.sizes !== undefined && nodesTraversed < depth) {
                ++nodesTraversed;
                if (currentNode.array.length < 32) {
                    copyableCount = nodesTraversed;
                }
                currentNode = currentNode.array[0];
            }
            if (l.offset !== 0) {
                var copiedNode = copyLeft(l, nodesTraversed);
                for (var i = 0; i < copiedNode.sizes.length; ++i) {
                    copiedNode.sizes[i] += branchingFactor;
                }
                copiedNode.array[0] = prependDense(copiedNode.array[0], depth - nodesTraversed, l.offset, 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;
                    if (copyableCount > 1) {
                        parent_1 = copyLeft(l, copyableCount - 1);
                        prependableNode = parent_1.array[0];
                    }
                    else {
                        parent_1 = undefined;
                        prependableNode = l.root;
                    }
                    var path = createPath(depth - copyableCount, node);
                    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_1;
        return l;
    }
}
function prependDense(node, depth, offset, value) {
    var curOffset = (offset >> (depth * branchBits)) & mask;
    var path = (((offset - 1) >> (depth * branchBits)) & mask) - curOffset;
    if (path < 0) {
        return new Node(undefined, arrayPrepend(createPath(depth - 1, value), node.array));
    }
    else {
        var array = copyArray(node.array);
        array[0] = prependDense(array[0], depth - 1, offset, value);
        return new Node(undefined, array);
    }
}
function append(value, l) {
    var suffixSize = getSuffixSize(l);
    if (suffixSize < 32) {
        return new List(incrementSuffix(l.bits), l.offset, l.length + 1, l.prefix, l.root, affixPush(value, l.suffix, suffixSize));
    }
    var newSuffix = [value];
    var newList = cloneList(l);
    appendNodeToTree(newList, l.suffix);
    newList.suffix = newSuffix;
    newList.length++;
    newList.bits = setSuffix(1, newList.bits);
    return newList;
}
exports.append = append;
function length(l) {
    return l.length;
}
exports.length = length;
function first(l) {
    var prefixSize = getPrefixSize(l);
    return prefixSize !== 0
        ? l.prefix[prefixSize - 1]
        : l.length !== 0
            ? l.suffix[0]
            : undefined;
}
exports.first = first;
exports.head = first;
function last(l) {
    var suffixSize = getSuffixSize(l);
    return suffixSize !== 0
        ? l.suffix[suffixSize - 1]
        : l.length !== 0
            ? l.prefix[0]
            : undefined;
}
exports.last = last;
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 mapPrefix(f, prefix, length) {
    var newPrefix = new Array(length);
    for (var i = length - 1; 0 <= i; --i) {
        newPrefix[i] = f(prefix[i]);
    }
    return newPrefix;
}
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, mapPrefix(f, l.prefix, getPrefixSize(l)), l.root === undefined ? undefined : mapNode(f, l.root, getDepth(l)), mapAffix(f, l.suffix, getSuffixSize(l)));
}
exports.map = map;
function pluck(key, l) {
    return map(function (a) { return a[key]; }, l);
}
exports.pluck = pluck;
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 traverse(of, f, l) {
    return foldr(function (a, fl) {
        return fl["fantasy-land/ap"](f(a)["fantasy-land/map"](function (a) { return function (l) { return prepend(a, l); }; }));
    }, of["fantasy-land/of"](empty()), l);
}
exports.traverse = traverse;
function sequence(ofObj, l) {
    return traverse(ofObj, function (a) { return a; }, l);
}
exports.sequence = sequence;
function scan(f, initial, l) {
    return foldl(function (l2, a) { return push(f(last(l2), a), l2); }, push(initial, emptyPushable()), l);
}
exports.scan = scan;
function forEach(callback, l) {
    foldl(function (_, element) { return callback(element); }, undefined, l);
}
exports.forEach = forEach;
function filter(predicate, l) {
    return foldl(function (acc, a) { return (predicate(a) ? push(a, acc) : acc); }, emptyPushable(), l);
}
exports.filter = filter;
function reject(predicate, l) {
    return foldl(function (acc, a) { return (predicate(a) ? acc : push(a, acc)); }, emptyPushable(), l);
}
exports.reject = reject;
function partition(predicate, l) {
    return foldl(function (arr, a) { return (predicate(a) ? push(a, arr[0]) : push(a, arr[1]), arr); }, [emptyPushable(), emptyPushable()], l);
}
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 ap(listF, l) {
    return flatten(map(function (f) { return map(f, l); }, listF));
}
exports.ap = ap;
function flatten(nested) {
    return foldl(concat, empty(), nested);
}
exports.flatten = flatten;
function flatMap(f, l) {
    return flatten(map(f, l));
}
exports.flatMap = flatMap;
exports.chain = flatMap;
function foldlArrayCb(cb, state, array, from, to) {
    for (var i = from; i < to && cb(array[i], state); ++i) { }
    return i === to;
}
function foldrArrayCb(cb, state, array, from, to) {
    for (var i = from - 1; to <= i && cb(array[i], state); --i) { }
    return i === to - 1;
}
function foldlNodeCb(cb, state, node, depth) {
    var array = node.array;
    if (depth === 0) {
        return foldlArrayCb(cb, state, array, 0, array.length);
    }
    var to = array.length;
    for (var i = 0; i < to; ++i) {
        if (!foldlNodeCb(cb, state, array[i], depth - 1)) {
            return false;
        }
    }
    return true;
}
function foldlCb(cb, state, l) {
    var prefixSize = getPrefixSize(l);
    if (!foldrArrayCb(cb, state, l.prefix, prefixSize, 0) ||
        (l.root !== undefined && !foldlNodeCb(cb, state, l.root, getDepth(l)))) {
        return state;
    }
    var suffixSize = getSuffixSize(l);
    foldlArrayCb(cb, state, l.suffix, 0, suffixSize);
    return state;
}
function foldrNodeCb(cb, state, node, depth) {
    var array = node.array;
    if (depth === 0) {
        return foldrArrayCb(cb, state, array, array.length, 0);
    }
    for (var i = array.length - 1; 0 <= i; --i) {
        if (!foldrNodeCb(cb, state, array[i], depth - 1)) {
            return false;
        }
    }
    return true;
}
function foldrCb(cb, state, l) {
    var suffixSize = getSuffixSize(l);
    var prefixSize = getPrefixSize(l);
    if (!foldrArrayCb(cb, state, l.suffix, suffixSize, 0) ||
        (l.root !== undefined && !foldrNodeCb(cb, state, l.root, getDepth(l)))) {
        return state;
    }
    var prefix = l.prefix;
    foldlArrayCb(cb, state, l.prefix, prefix.length - prefixSize, prefix.length);
    return state;
}
function foldlWhileCb(a, state) {
    if (state.predicate(state.result, a) === false) {
        return false;
    }
    state.result = state.f(state.result, a);
    return true;
}
function foldlWhile(predicate, f, initial, l) {
    return foldlCb(foldlWhileCb, { predicate: predicate, f: f, result: initial }, l).result;
}
exports.foldlWhile = foldlWhile;
exports.reduceWhile = foldlWhile;
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;
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 findLast(predicate, l) {
    return foldrCb(findCb, { predicate: predicate, result: undefined }, l)
        .result;
}
exports.findLast = findLast;
function indexOfCb(value, state) {
    ++state.index;
    return !(state.found = elementEquals(value, state.element));
}
function indexOf(element, l) {
    var state = { element: element, found: false, index: -1 };
    foldlCb(indexOfCb, state, l);
    return state.found ? state.index : -1;
}
exports.indexOf = indexOf;
function lastIndexOf(element, l) {
    var state = { element: element, found: false, index: 0 };
    foldrCb(indexOfCb, state, l);
    return state.found ? l.length - state.index : -1;
}
exports.lastIndexOf = lastIndexOf;
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;
function equalsCb(value2, state) {
    var value = state.iterator.next().value;
    return (state.equals = state.f(value, value2));
}
function equals(l1, l2) {
    return equalsWith(elementEquals, l1, l2);
}
exports.equals = equals;
function equalsWith(f, l1, l2) {
    if (l1 === l2) {
        return true;
    }
    else if (l1.length !== l2.length) {
        return false;
    }
    else {
        var s = { iterator: l2[Symbol.iterator](), equals: true, f: f };
        return foldlCb(equalsCb, s, l1).equals;
    }
}
exports.equalsWith = equalsWith;
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;
        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;
    }
    while (optimalLength + eMax < n) {
        while (sizes[i] > branchingFactor - eMax / 2) {
            ++i;
        }
        var remaining = sizes[i];
        do {
            var size = Math.min(remaining + sizes[i + 1], branchingFactor);
            sizes[i] = size;
            remaining = remaining - (size - sizes[i + 1]);
            ++i;
        } while (remaining > 0);
        for (var j = i; j <= n - 1; ++j) {
            sizes[j] = sizes[j + 1];
        }
        --i;
        --n;
    }
    sizes.length = n;
    return sizes;
}
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;
    var offset = 0;
    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) {
            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) {
                setSizes(node, height - 1);
            }
            result.push(node);
        }
    }
    return result;
}
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 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;
    }
}
function appendNodeToTree(l, array) {
    if (l.root === undefined) {
        if (getPrefixSize(l) === 0) {
            l.bits = setPrefix(array.length, l.bits);
            l.prefix = reverseArray(array);
        }
        else {
            l.root = new Node(undefined, array);
        }
        return l;
    }
    var depth = getDepth(l);
    var index = handleOffset(depth, l.offset, 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;
        nodesVisited = depth;
    }
    while (shift > 5) {
        var childIndex = void 0;
        if (currentNode.sizes === undefined) {
            childIndex = (index >> shift) & mask;
            index &= ~(mask << shift);
        }
        else {
            childIndex = currentNode.array.length - 1;
            index -= currentNode.sizes[childIndex - 1];
        }
        nodesVisited++;
        if (childIndex < mask) {
            nodesToCopy = nodesVisited;
        }
        currentNode = currentNode.array[childIndex];
        if (currentNode === undefined) {
            nodesToCopy = nodesVisited;
            shift = 5;
        }
        shift -= 5;
    }
    if (shift !== 0) {
        nodesVisited++;
        if (currentNode.array.length < branchingFactor) {
            nodesToCopy = nodesVisited;
        }
    }
    var node = new Node(undefined, array);
    if (nodesToCopy === 0) {
        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, nodesToCopy, array.length);
        copiedNode.array.push(createPath(depth - nodesToCopy, node));
    }
    return l;
}
function copyFirstK(newList, k, leafSize) {
    var currentNode = cloneNode(newList.root);
    newList.root = currentNode;
    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]);
        currentNode.array[index] = newNode;
        currentNode = newNode;
    }
    if (currentNode.sizes !== undefined) {
        currentNode.sizes.push(arrayLast(currentNode.sizes) + leafSize);
    }
    return currentNode;
}
var concatBuffer = new Array(3);
function concatAffixes(left, right) {
    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];
    }
    length = getPrefixSize(right);
    for (i = 0; i < length; ++i) {
        if (arrIdx === 32) {
            arrIdx = 0;
            ++nr;
            concatBuffer[nr] = [];
        }
        concatBuffer[nr][arrIdx++] = right.prefix[length - 1 - i];
    }
    length = getSuffixSize(right);
    for (i = 0; i < length; ++i) {
        if (arrIdx === 32) {
            arrIdx = 0;
            ++nr;
            concatBuffer[nr] = [];
        }
        concatBuffer[nr][arrIdx++] = right.suffix[i];
    }
    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) {
        var nrOfAffixes = concatAffixes(left, right);
        for (var i = 0; i < nrOfAffixes; ++i) {
            newList = appendNodeToTree(newList, concatBuffer[i]);
            newList.length += concatBuffer[i].length;
            concatBuffer[i] = undefined;
        }
        newList.length = newSize;
        newList.suffix = concatBuffer[nrOfAffixes];
        newList.bits = setSuffix(concatBuffer[nrOfAffixes].length, newList.bits);
        concatBuffer[nrOfAffixes] = undefined;
        return newList;
    }
    else {
        var leftSuffixSize = getSuffixSize(left);
        if (leftSuffixSize > 0) {
            newList = appendNodeToTree(newList, left.suffix.slice(0, leftSuffixSize));
            newList.length += leftSuffixSize;
        }
        newList = appendNodeToTree(newList, right.prefix.slice(0, getPrefixSize(right)).reverse());
        var newNode = concatSubTree(newList.root, getDepth(newList), right.root, getDepth(right), true);
        var newDepth = getHeight(newNode);
        setSizes(newNode, newDepth);
        newList.root = newNode;
        newList.offset &= ~(mask << (getDepth(left) * branchBits));
        newList.length = newSize;
        newList.bits = setSuffix(rightSuffixSize, setDepth(newDepth, newList.bits));
        newList.suffix = right.suffix;
        return newList;
    }
}
exports.concat = concat;
function update(index, a, l) {
    if (index < 0 || l.length <= index) {
        return 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, a);
    }
    return newList;
}
exports.update = update;
function adjust(index, f, l) {
    if (index < 0 || l.length <= index) {
        return l;
    }
    return update(index, f(nth(index, l)), l);
}
exports.adjust = adjust;
var newAffix;
function sliceNode(node, index, depth, pathLeft, pathRight, childLeft, childRight) {
    var array = node.array.slice(pathLeft, pathRight + 1);
    if (childLeft !== undefined) {
        array[0] = childLeft;
    }
    if (childRight !== undefined) {
        array[array.length - 1] = childRight;
    }
    var sizes = node.sizes;
    if (sizes !== undefined) {
        sizes = sizes.slice(pathLeft, pathRight + 1);
        var slicedOffLeft = pathLeft !== 0 ? node.sizes[pathLeft - 1] : 0;
        if (childLeft !== undefined) {
            if (childLeft.sizes !== undefined) {
                var oldChild = node.array[pathLeft];
                slicedOffLeft +=
                    arrayLast(oldChild.sizes) - arrayLast(childLeft.sizes);
            }
            else {
                slicedOffLeft += ((index - slicedOffLeft) & ~31) + 32;
            }
        }
        for (var i = 0; i < sizes.length; ++i) {
            sizes[i] -= slicedOffLeft;
        }
        if (childRight !== undefined) {
            var slicedOffRight = sizeOfSubtree(node.array[pathRight], depth - 1) -
                sizeOfSubtree(childRight, depth - 1);
            sizes[sizes.length - 1] -= slicedOffRight;
        }
    }
    return new Node(sizes, array);
}
var newOffset = 0;
function sliceLeft(tree, depth, index, offset, top) {
    var _a = getPath(index, offset, depth, tree.sizes), path = _a.path, newIndex = _a.index, updatedOffset = _a.updatedOffset;
    if (depth === 0) {
        newAffix = tree.array.slice(path).reverse();
        return undefined;
    }
    else {
        var child = sliceLeft(tree.array[path], depth - 1, newIndex, updatedOffset, false);
        if (child === undefined) {
            ++path;
            if (path === tree.array.length) {
                return undefined;
            }
        }
        if (tree.sizes === undefined && top === false) {
            newOffset |= (32 - (tree.array.length - path)) << (depth * branchBits);
        }
        return sliceNode(tree, index, depth, path, tree.array.length - 1, child, undefined);
    }
}
function sliceRight(node, depth, index, offset) {
    var _a = getPath(index, offset, depth, node.sizes), path = _a.path, newIndex = _a.index;
    if (depth === 0) {
        newAffix = node.array.slice(0, path + 1);
        return undefined;
    }
    else {
        var child = sliceRight(node.array[path], depth - 1, newIndex, path === 0 ? offset : 0);
        if (child === undefined) {
            --path;
            if (path === -1) {
                return undefined;
            }
        }
        var array = node.array.slice(0, path + 1);
        if (child !== undefined) {
            array[array.length - 1] = child;
        }
        var sizes = node.sizes;
        if (sizes !== undefined) {
            sizes = sizes.slice(0, path + 1);
            if (child !== undefined) {
                var slicedOff = sizeOfSubtree(node.array[path], depth - 1) -
                    sizeOfSubtree(child, depth - 1);
                sizes[sizes.length - 1] -= slicedOff;
            }
        }
        return new Node(sizes, array);
    }
}
function sliceTreeList(from, to, tree, depth, offset, l) {
    var sizes = tree.sizes;
    var _a = getPath(from, offset, depth, sizes), pathLeft = _a.path, newFrom = _a.index;
    var _b = getPath(to, offset, depth, sizes), pathRight = _b.path, newTo = _b.index;
    if (depth === 0) {
        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) {
        l.bits = decrementDepth(l.bits);
        return sliceTreeList(newFrom, newTo, tree.array[pathLeft], depth - 1, pathLeft === 0 ? offset : 0, l);
    }
    else {
        var childRight = sliceRight(tree.array[pathRight], depth - 1, newTo, 0);
        l.bits = setSuffix(newAffix.length, l.bits);
        l.suffix = newAffix;
        if (childRight === undefined) {
            --pathRight;
        }
        newOffset = 0;
        var childLeft = sliceLeft(tree.array[pathLeft], depth - 1, newFrom, pathLeft === 0 ? offset : 0, pathLeft === pathRight);
        l.offset = newOffset;
        l.bits = setPrefix(newAffix.length, l.bits);
        l.prefix = newAffix;
        if (childLeft === undefined) {
            ++pathLeft;
        }
        if (pathLeft >= pathRight) {
            if (pathLeft > pathRight) {
                l.bits = setDepth(0, l.bits);
                l.root = undefined;
            }
            else {
                l.bits = decrementDepth(l.bits);
                var newRoot = childRight !== undefined
                    ? childRight
                    : childLeft !== undefined
                        ? childLeft
                        : tree.array[pathLeft];
                l.root = new Node(newRoot.sizes, newRoot.array);
            }
        }
        else {
            l.root = sliceNode(tree, from, depth, pathLeft, pathRight, childLeft, childRight);
        }
        return l;
    }
}
function slice(from, to, l) {
    var bits = l.bits, length = l.length;
    to = Math.min(length, to);
    if (from < 0) {
        from = length + from;
    }
    if (to < 0) {
        to = length + to;
    }
    if (to <= from || to <= 0 || length <= from) {
        return empty();
    }
    if (from <= 0 && length <= to) {
        return l;
    }
    var newLength = to - from;
    var prefixSize = getPrefixSize(l);
    var suffixSize = getSuffixSize(l);
    if (to <= prefixSize) {
        return new List(setPrefix(newLength, 0), 0, newLength, l.prefix.slice(prefixSize - to, prefixSize - from), undefined, emptyAffix);
    }
    var suffixStart = length - suffixSize;
    if (suffixStart <= from) {
        return new List(setSuffix(newLength, 0), 0, newLength, emptyAffix, undefined, l.suffix.slice(from - suffixStart, to - suffixStart));
    }
    var newList = cloneList(l);
    newList.length = newLength;
    if (prefixSize <= from && to <= suffixStart) {
        sliceTreeList(from - prefixSize + l.offset, to - prefixSize + l.offset - 1, l.root, getDepth(l), l.offset, newList);
        return newList;
    }
    if (0 < from) {
        if (from < prefixSize) {
            newList.prefix = l.prefix.slice(0, prefixSize - from);
            bits = setPrefix(prefixSize - from, bits);
        }
        else {
            newOffset = 0;
            newList.root = sliceLeft(newList.root, getDepth(l), from - prefixSize, l.offset, true);
            newList.offset = newOffset;
            if (newList.root === undefined) {
                bits = setDepth(0, bits);
            }
            bits = setPrefix(newAffix.length, bits);
            prefixSize = newAffix.length;
            newList.prefix = newAffix;
        }
    }
    if (to < length) {
        if (length - to < suffixSize) {
            bits = setSuffix(suffixSize - (length - to), bits);
            newList.suffix = l.suffix.slice(0, suffixSize - (length - to));
        }
        else {
            newList.root = sliceRight(newList.root, getDepth(l), to - prefixSize - 1, newList.offset);
            if (newList.root === undefined) {
                bits = setDepth(0, bits);
                newList.offset = 0;
            }
            bits = setSuffix(newAffix.length, bits);
            newList.suffix = newAffix;
        }
    }
    newList.bits = bits;
    return newList;
}
exports.slice = slice;
function take(n, l) {
    return slice(0, n, l);
}
exports.take = take;
function findNotIndexCb(value, state) {
    if (state.predicate(value)) {
        ++state.index;
        return true;
    }
    else {
        return false;
    }
}
function takeWhile(predicate, l) {
    var index = foldlCb(findNotIndexCb, { predicate: predicate, index: 0 }, l).index;
    return slice(0, index, l);
}
exports.takeWhile = takeWhile;
function takeLastWhile(predicate, l) {
    var index = foldrCb(findNotIndexCb, { predicate: predicate, index: 0 }, l).index;
    return slice(l.length - index, l.length, l);
}
exports.takeLastWhile = takeLastWhile;
function dropWhile(predicate, l) {
    var index = foldlCb(findNotIndexCb, { predicate: predicate, index: 0 }, l).index;
    return slice(index, l.length, l);
}
exports.dropWhile = dropWhile;
function dropRepeats(l) {
    return dropRepeatsWith(elementEquals, l);
}
exports.dropRepeats = dropRepeats;
function dropRepeatsWith(predicate, l) {
    return foldl(function (acc, a) {
        return acc.length !== 0 && predicate(last(acc), a) ? acc : push(a, acc);
    }, emptyPushable(), l);
}
exports.dropRepeatsWith = dropRepeatsWith;
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 splitWhen(predicate, l) {
    var idx = findIndex(predicate, l);
    return idx === -1 ? [l, empty()] : splitAt(idx, l);
}
exports.splitWhen = splitWhen;
function splitEvery(size, l) {
    var _a = foldl(function (_a, elm) {
        var l2 = _a.l2, buffer = _a.buffer;
        push(elm, buffer);
        if (buffer.length === size) {
            return { l2: push(buffer, l2), buffer: emptyPushable() };
        }
        else {
            return { l2: l2, buffer: buffer };
        }
    }, { l2: emptyPushable(), buffer: emptyPushable() }, l), l2 = _a.l2, buffer = _a.buffer;
    return buffer.length === 0 ? l2 : push(buffer, l2);
}
exports.splitEvery = splitEvery;
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 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;
function reverse(l) {
    return foldl(function (newL, element) { return prepend(element, newL); }, empty(), l);
}
exports.reverse = reverse;
function isList(l) {
    return typeof l === "object" && Array.isArray(l.suffix);
}
exports.isList = isList;
function zip(as, bs) {
    return zipWith(function (a, b) { return [a, b]; }, as, bs);
}
exports.zip = zip;
function zipWith(f, as, bs) {
    var swapped = bs.length < as.length;
    var iterator = (swapped ? as : bs)[Symbol.iterator]();
    return map(function (a) {
        var b = iterator.next().value;
        return swapped ? f(b, a) : f(a, b);
    }, (swapped ? bs : as));
}
exports.zipWith = zipWith;
function isPrimitive(value) {
    return typeof value === "number" || typeof value === "string";
}
function comparePrimitive(a, b) {
    return a === b ? 0 : a < b ? -1 : 1;
}
var ord = "fantasy-land/lte";
function compareOrd(a, b) {
    return a[ord](b) ? (b[ord](a) ? 0 : -1) : 1;
}
function sort(l) {
    if (l.length === 0) {
        return l;
    }
    else if (isPrimitive(first(l))) {
        return from(toArray(l).sort(comparePrimitive));
    }
    else {
        return sortWith(compareOrd, l);
    }
}
exports.sort = sort;
function sortWith(comparator, l) {
    var arr = [];
    var i = 0;
    forEach(function (elm) { return arr.push({ idx: i++, elm: elm }); }, l);
    arr.sort(function (_a, _b) {
        var a = _a.elm, i = _a.idx;
        var b = _b.elm, j = _b.idx;
        var c = comparator(a, b);
        return c !== 0 ? c : i < j ? -1 : 1;
    });
    var newL = emptyPushable();
    for (var i_3 = 0; i_3 < arr.length; ++i_3) {
        push(arr[i_3].elm, newL);
    }
    return newL;
}
exports.sortWith = sortWith;
function sortBy(f, l) {
    if (l.length === 0) {
        return l;
    }
    var arr = [];
    var i = 0;
    forEach(function (elm) { return arr.push({ idx: i++, elm: elm, prop: f(elm) }); }, l);
    var comparator = isPrimitive(arr[0].prop)
        ? comparePrimitive
        : compareOrd;
    arr.sort(function (_a, _b) {
        var a = _a.prop, i = _a.idx;
        var b = _b.prop, j = _b.idx;
        var c = comparator(a, b);
        return c !== 0 ? c : i < j ? -1 : 1;
    });
    var newL = emptyPushable();
    for (var i_4 = 0; i_4 < arr.length; ++i_4) {
        push(arr[i_4].elm, newL);
    }
    return newL;
}
exports.sortBy = sortBy;
function group(l) {
    return groupWith(elementEquals, l);
}
exports.group = group;
function groupWith(f, l) {
    var result = emptyPushable();
    var buffer = emptyPushable();
    forEach(function (a) {
        if (buffer.length !== 0 && !f(last(buffer), a)) {
            push(buffer, result);
            buffer = emptyPushable();
        }
        push(a, buffer);
    }, l);
    return buffer.length === 0 ? result : push(buffer, result);
}
exports.groupWith = groupWith;
function intersperse(separator, l) {
    return pop(foldl(function (l2, a) { return push(separator, push(a, l2)); }, emptyPushable(), l));
}
exports.intersperse = intersperse;
function isEmpty(l) {
    return l.length === 0;
}
exports.isEmpty = isEmpty;