Space -- basic implementation of poolable double-ended mutable vectors based on hash array mapped tries (HAMTs)

index.html

<script>

    var CERTIFY_INTERNALLY = 0|false;
    var _fleetAssociations = new WeakMap();

    function Fleet (space) {
        this._space = (space instanceof Space) ? space : spaceAllocator(0);
    }

    function _fleetMatch (fleet, owner) {
        return owner === null || owner === void 0 ? fleet : owner;
    }

    function _fleetClaim (fleet, certified, owner) {
        var count = spaceSize(fleet._space);
        if (count < 1) return null;
        else if (certified) return _fleetCertified(fleet, count - 1, owner);
        else return spacePop(fleet._space, null);
    }

    function _fleetCertified (fleet, retries, owner) {
        var limit = 0|retries;
        var match = _fleetMatch(fleet, owner);
        var member = _fleetRegister(match, spacePop(fleet._space, null));
        while (!member && limit-- > 0) {
            member = _fleetRegister(match, spacePop(fleet._space, null));
        }
        return member || null;
    }

    function _fleetRegister (owner, member) {
        if (!(member instanceof Object)) return null;
        else if (_fleetAssociations.has(member)) {
            return _fleetAssociations.get(member) === owner ? member : null;
        }
        _fleetAssociations.set(member, owner);
        return member;
    }

    function _fleetPool (fleet, member, certified, owner) {
        if (!(member instanceof Object)) return null;
        else if (!_fleetValidate(fleet, member, certified, owner)) return null;
        else _fleetAssociations.delete(member);

        if (fleet === _invalidFleet()) return _fleetSpacePush(new Fleet(null), member);
        else return _fleetSpacePush(fleet, member);
    }

    function _fleetValidate (fleet, member, certified, owner) {
        var match = _fleetAssociations.get(member);
        if (match === null || match === void 0) return 0|!certified;
        else return 0|(match === _fleetMatch(fleet, owner));
    }

    function _fleetSpacePush (fleet, member) {
        spacePush(fleet._space, member);
        return fleet;
    }

    function _fleetTotal (fleet) {
        return spaceSize(fleet._space);
    }

    function _fleetDownsize (fleet, limit) {
        var delta = _fleetTotal(fleet) - (limit || 0);
        var count = 0;
        while (total-- > count) spacePop(fleet._space, null);
        spaceTrim(fleet._space, _spaceFleet(0|spaceBits(fleet._space)), 0);
        return delta;
    }



    function spaceAllocator (bits) {
        return new Space(0|bits);
    }

    function Space (bits) {
        var num = 0|bits;
        num = num < 1 ? 5 : num;
        this._bits = num;
        this._count = 0;
        this._omit = 0;
        this._level = 0;
        this._volume = new Array(1 << num);
    }

    Space.prototype.bits = function () {
        return (this instanceof Space) ? 0|spaceBits(this) : 0;
    };

    Space.prototype.at = function (index, sentinel) {
        return (this instanceof Space) ? spaceAt(this, index, sentinel) : sentinel;
    };

    Space.prototype.swap = function (index, value, sentinel) {
        return (this instanceof Space) ? spaceSwap(this, index, value, sentinel) : sentinel;
    };

    Space.prototype.size = function () {
        return (this instanceof Space) ? spaceSize(this) : -1;
    };

    Space.prototype.trim = function (limit) {
        return (this instanceof Space) ? spaceTrim(this, _spaceFleet(spaceBits(this)), 0|limit) : -1;
    };

    Space.prototype.push = function (value) {
        if (this instanceof Space) spacePush(this, value);
        else return null;
        return this;
    };

    Space.prototype.unshift = function (value) {
        if (this instanceof Space) spaceUnshift(this, value);
        else return null;
        return this;
    };

    Space.prototype.pop = function (sentinel) {
        return (this instanceof Space) ? spacePop(this, sentinel) : sentinel;
    };

    Space.prototype.shift = function (sentinel) {
        return (this instanceof Space) ? spaceShift(this, sentinel) : sentinel;
    };



    var _fleetSentinel = new Fleet(spaceAllocator(0));
    var _spaceArmadas = [_fleetSentinel];

    function _invalidFleet () {
        return _fleetSentinel;
    }

    function _spaceFleet (bits) {
        var num = 0|bits;
        if (num < 1) num = spaceBits(_fleetSentinel.space);
        num -= _spaceArmadas.length - 1;
        while (num-- > 0) _spaceArmadas.push(new Fleet(spaceAllocator(0)));
        return _spaceArmadas[0|bits];
    }

    function _claimSpace (bits, armada) {
        var fleet = armada || _spaceFleet(0|bits);
        return _fleetClaim(fleet, 0|CERTIFY_INTERNALLY, fleet) ||
            (CERTIFY_INTERNALLY && _fleetRegister(fleet, spaceAllocator(0|bits))) ||
            spaceAllocator(0|bits);
    }

    function _poolSpace (root, armada) {
        var fleet = armada || _spaceFleet(0|spaceBits(root));
        _spaceVoid(root);
        spaceTrim(root, fleet, 0);
        if (_fleetPool(fleet, _spaceZero(root), 0|CERTIFY_INTERNALLY, fleet)) {
            return 0|true;
        } else return 0|false;
    }



    function spaceBits (space) {
        return 0|space._bits;
    }

    function spaceDimension (space) {
        return 1 << (0|space._bits);
    }

    function spaceSize (root) {
        var dimension = 0|spaceDimension(root);
        return _spaceRear(root, dimension, 0) - _spaceFront(root, dimension, 0);
    }

    function _spaceRear (space, dimension, total) {
        var size = (0|space._count) - 1;
        var sum = size + (total * (0|dimension));
        if (space._level < 1) return sum + 1;
        else return _spaceRear(space._volume[size], 0|dimension, sum);
    }

    function _spaceFront (space, dimension, total) {
        var skip = 0|space._omit;
        var sum = skip + (total * (0|dimension));
        if (space._level < 1) return sum;
        else return _spaceFront(space._volume[skip], 0|dimension, sum);
    }

    function _spaceSkip (root) {
        return _spaceFront(root, 0|spaceDimension(root), 0);
    }



    function _spacePostfixDrill(upper, dimension) {
        var lower = upper;
        if (upper._level < 1) return upper;
        lower = upper._volume[(0|upper._count) - 1] || upper;
        if (lower === upper) return upper;
        lower = _spacePostfixDrill(lower, 0|dimension);
        return (lower._count < dimension) ? lower : (upper._count < dimension) ? upper : lower;
    }

    function _spacePrefixDrill (upper) {
        var lower = upper;
        if (upper._level < 1) return upper;
        lower = upper._volume[0|upper._omit] || upper;
        if (lower === upper) return upper;
        lower = _spacePrefixDrill(lower);
        return (lower._omit > 0) ? lower : (upper._omit > 0) ? upper : lower;
    }

    function _spaceAppend (root, value) {
        var bits = 0|spaceBits(root);
        var dimension = 0|spaceDimension(root);
        var space = _spacePostfixDrill(root, 0|dimension);
        var level = 0|space._level;
        var fleet = _spaceFleet(0|bits);
        if (level < 1 && space._count > dimension - 1) space = _spaceSuspend(root, _claimSpace(0|bits, fleet));
        level = 0|space._level;
        while (level-- > 0) space = _spaceAfter(space, _claimSpace(0|bits, fleet));
        space._volume[0|space._count++] = value;
    }

    function _spacePrepend (root, value) {
        var bits = 0|spaceBits(root);
        var dimension = 0|spaceDimension(root);
        var space = _spacePrefixDrill(root);
        var level = 0|space._level;
        var fleet = _spaceFleet(0|bits);
        if (level < 1 && space._omit < 1) space = _spaceUpend(root, _claimSpace(0|bits, fleet));
        level = 0|space._level;
        while (level-- > 0) space = _spaceBefore(space, _claimSpace(0|bits, fleet), 0|dimension);
        space._volume[0|--space._omit] = value;
    }

    function _spaceAfter (upper, lower) {
        var level = 0|upper._level;
        lower._level = level - 1;
        lower._omit = 0;
        lower._count = 0;
        upper._volume[0|upper._count++] = lower;
        return lower;
    }

    function _spaceBefore (upper, lower, dimension) {
        var level = 0|upper._level;
        lower._level = level - 1;
        lower._omit = 0|dimension;
        lower._count = 0|dimension;
        upper._volume[0|--upper._omit] = lower;
        return lower;
    }

    function _spaceMove (from, to) {
        var meta = from._volume;
        var data = to._volume;
        var amount = meta.length;
        var index = 0;
        for (index; index < amount; index++) {
            data[index] = meta[index];
            meta[index] = null;
        }
    }

    function _spaceSuspend (root, space) {
        var level = 0|root._level;
        _spaceMove(root, space);
        
        space._level = level;
        space._omit = 0|root._omit;
        space._count = 0|root._count;

        root._level = level + 1;
        root._omit = 0;
        root._count = 1;
        root._volume[0] = space;
        
        return root;
    }

    function _spaceUpend (root, space) {
        var level = 0|root._level;
        _spaceMove(root, space);
        
        space._level = level;
        space._omit = 0|root._omit;
        space._count = 0|root._count;

        root._level = level + 1;
        root._omit = 1;
        root._count = 2;
        root._volume[1] = space;
        
        return root;
    }



    function _spaceZero (space) {
        space._count = 0;
        space._omit = 0;
        space._level = 0;
        return space;
    }

    function _spaceVoid (upper, fleet) {
        var lower = upper;
        var count = 0|upper._count;
        var index = (0|upper._omit) - 1;
        if (upper._level < 1) while (++index < count) {
            upper._volume[index] = null;
        } else while (++index < count) {
            lower = upper._volume[index] || upper;
            if (lower === upper) continue;
            _spaceVoid(lower, fleet);
        }
        upper._omit = count;
    }



    function spaceTrim (root, fleet, limit) {
        var dimension = 0|spaceDimension(root);
        var amount = 0|_spaceShaveUp(root, fleet, 0|limit, 0|dimension);
        if (amount < 0) return 0|amount;
        else return 0|_spaceShaveDown(root, fleet, 0|amount, 0|dimension);
    }

    function _spaceShaveUp (upper, fleet, limit, dimension) {
        var amount = 0|limit;
        var index = -1;
        var omit = 0|upper._omit;
        var lower = upper;
        if (upper._level < 1) return 0|amount;
        while (++index < omit) {
            lower = upper._volume[index] || upper;
            if (lower === upper) continue;
            amount = 0|_spaceShaveUp(lower, fleet, 0|amount, 0|dimension);
            if (amount < 0) return 0|amount;
            upper._volume[index] = null;
            _fleetPool(fleet, _spaceZero(lower), 0|CERTIFY_INTERNALLY, fleet);
            if (amount && !--amount) return -1;
        }
        if (index < dimension) return 0|_spaceShaveUp(upper._volume[index], fleet, 0|amount, 0|dimension);
        return 0|amount;
    }

    function _spaceShaveDown (upper, fleet, limit, dimension) {
        var amount = 0|limit;
        var index = 0|(dimension || spaceDimension(upper));
        var count = 0|upper._count;
        var lower = upper;
        if (upper._level < 1) return 0|amount;
        while (index-- > count) {
            lower = upper._volume[index] || upper;
            if (lower === upper) continue;
            amount = 0|_spaceShaveDown(lower, fleet, 0|amount, 0|dimension);
            if (amount < 0) return 0|amount;
            upper._volume[index] = null;
            _fleetPool(fleet, _spaceZero(lower), 0|CERTIFY_INTERNALLY, fleet);
            if (amount && !--amount) return -1;
        }
        if (index < 0) return 0|amount;
        else return 0|_spaceShaveDown(upper._volume[index], fleet, 0|amount, 0|dimension);
    }



    function _spaceEject (root, sentinel) {
        var leaf = _spaceEjectionDrill(root, 0|true);
        var has = 0|(leaf._count > leaf._omit);
        var value = has ? leaf._volume[--leaf._count] : sentinel;
        if (has) leaf._volume[leaf._count] = null;
        return value;
    }

    function _spaceEjectionDrill (upper, constrain) {
        var lower = upper;
        var leaf = upper;
        var omit = 0|upper._omit;
        var count = 0|upper._count;
        var limit = count - 1;
        var permit = 0|(!constrain || limit > omit);
        if (upper._level < 1) return upper;
        else if (count < 1) throw new Error("Corrupt Ejection");
        lower = upper._volume[limit];
        limit = (0|lower._count) - (0|lower._omit);
        leaf = _spaceEjectionDrill(lower, 0|!permit);
        if (permit && _spaceShrinkable(0|limit, lower, leaf)) upper._count--;
        return leaf;
    }

    function _spaceShrinkable (limit, lower, leaf) {
        var size = (0|lower._count) - (0|lower._omit);
        if (lower === leaf) return 0|(size === 1);
        else return 0|(limit > 0 && size === 0);
    }

    function _spaceRejectionDrill (upper, constrain) {
        var lower = upper;
        var leaf = upper;
        var omit = 0|upper._omit;
        var count = 0|upper._count;
        var limit = count - 1;
        var permit = 0|(!constrain || limit > omit);
        if (upper._level < 1) return upper;
        else if (omit > limit) throw new Error("Corrupt Rejection");
        lower = upper._volume[omit];
        limit = (0|lower._count) - (0|lower._omit);
        leaf = _spaceRejectionDrill(lower, 0|!permit);
        if (permit && _spaceShrinkable(0|limit, lower, leaf)) upper._omit++;
        return leaf;
    }

    function _spaceReject (root, constrain, sentinel) {
        var leaf = _spaceRejectionDrill(root, 0|true);
        var has = 0|(leaf._count > leaf._omit);
        var value = has ? leaf._volume[leaf._omit] : sentinel;
        if (has) leaf._volume[leaf._omit++] = null;
        return value;
    }



    function _spaceIndexDrill (root, dimension, level, omissionAdjustedIndex) {
        var space = root;
        var at = omissionAdjustedIndex & ((0|dimension) - 1);
        var num = (omissionAdjustedIndex - at) / (0|dimension);
        if (level < root._level) space = _spaceIndexDrill(root, 0|dimension, (0|level) + 1, num);
        else return root._volume[at] || root;
        if (space === root) return root;
        else return space._volume[at] || root;
    }

    function _spaceTrade (leaf, index, young, sentinel) {
        var at = 0|index;
        var old = young;
        if (at < leaf._count) old = leaf._volume[at];
        else return sentinel;
        leaf._volume[at] = young;
        return old;
    }

    function spaceSwap (root, index, value, sentinel) {
        var dimension = 0|spaceDimension(root);
        var omit = _spaceSkip(root);
        var num = index + omit;
        var at = num & (dimension - 1);
        var leaf = root;
        if (root._level < 1) return _spaceTrade(root, 0|num, value, sentinel);
        leaf = _spaceIndexDrill(root, dimension, 1, (num - at) / dimension);
        if (leaf === root) return sentinel;
        else return _spaceTrade(leaf, 0|at, value, sentinel);
    }

    function spaceAt (root, index, sentinel) {
        var dimension = 0|spaceDimension(root);
        var omit = _spaceSkip(root);
        var num = index + omit;
        var at = num & (dimension - 1);
        var leaf = root;
        if (root._level < 1) return (num < root._count) ? root._volume[0|num] : sentinel;
        leaf = _spaceIndexDrill(root, dimension, 1, (num - at) / dimension);
        if (leaf === root) return sentinel;
        else return (at < leaf._count) ? leaf._volume[0|at] : sentinel;
    }



    function spacePush (root, value) {
        _spaceAppend(root, value);
        return root;
    }

    function spaceUnshift (root, value) {
        _spacePrepend(root, value);
        return root;
    }

    function spacePop (root, sentinel) {
        return _spaceEject(root, 0|true, sentinel);
    }

    function spaceShift (root, sentinel) {
        return _spaceReject(root, 0|true, sentinel);
    }


</script>