Huge News!Announcing our $40M Series B led by Abstract Ventures.Learn More →
Socket
Sign inDemoInstall
Socket
Sign inDemoInstall

mute-structs

Package Overview
Dependencies
Maintainers
2
Versions
47
Alerts
File Explorer

Advanced tools

License
Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

mute-structs - npm Package Compare versions

Comparing version 0.3.3 to 0.4.0-0

dist/src/identifiertuple.d.ts
dist/src/identifiertuple.js

125

dist/src/identifier.d.ts
import { SafeAny } from "safe-any";
import { Ordering } from './ordering';
/**
* Holds the minimum value an integer can have.
*/
* Holds the minimum value an integer can have.
*/
export declare const INT_32_MIN_VALUE = -2147483648;

@@ -11,27 +11,120 @@ /**

export declare const INT_32_MAX_VALUE = 2147483647;
import { IdentifierTuple } from './identifiertuple';
export declare class Identifier {
constructor(base: number[], u: number);
constructor(tuples: IdentifierTuple[]);
static fromPlain(o: SafeAny<Identifier>): Identifier | null;
/**
* Each value of the base is contained in [INT_32_MIN_VALUE, INT_32_MAX_VALUE]
* Generate a new Identifier with the same base as the provided one but with a different offset
*
* @param {Identifier} id The identifier to partly copy
* @param {number} offset The last offset of the new Identifier
* @return {IdentifierTuple} The generated Identifier
*/
static generateWithSameBase(id: Identifier, offset: number): Identifier;
readonly tuples: IdentifierTuple[];
/**
* Shortcut to retrieve the length of the Identifier
*
* @return {number} The length
*/
readonly length: number;
/**
* Retrieve the offset of the last tuple of the identifier
*
* @return {number} The offset
*/
readonly lastOffset: number;
readonly base: number[];
/**
* The value of last is contained in ]INT_32_MIN_VALUE, INT_32_MAX_VALUE]
* Retrieve the longest common prefix shared by this identifier with another one
*
* @param {Identifier} other The other identifier
* @return {IdentifierTuple[]} The longest common prefix
*/
readonly last: number;
compareTo(aOther: Identifier): Ordering;
equals(aOther: Identifier): boolean;
getLongestCommonPrefix(other: Identifier): IdentifierTuple[];
/**
* Check if the identifier's {@link Identifier#base} is equals to another identifier's one
* Retrieve the longest common base shared by this identifier with another one
*
* @param {Identifier} aOther The other identifier
* @returns {boolean} Are the bases equals
* @param {Identifier} other The other identifier
* @return {IdentifierTuple[]} The longest common base
*/
equalsBase(aOther: Identifier): boolean;
getLongestCommonBase(other: Identifier): IdentifierTuple[];
/**
* Check if this identifier is a prefix of another one
*
* @param {Identifier} other The other identifier
* @return {boolean} Is this identifier a prefix of other
*/
isPrefix(other: Identifier): boolean;
/**
* Check if the base of this identifier is a prefix of the other one
*
* @param {Identifier} other The other identifier
* @return {boolean} Is this base a prefix of the other one
*/
isBasePrefix(other: Identifier): boolean;
/**
* Compute the common prefix between this identifier and the other one
* and return its length
*
* @param other The other identifier
* @return {number} The length of the common prefix
*/
getLengthCommonPrefix(other: Identifier): number;
equals(other: Identifier): boolean;
/**
* Check if two identifiers share the same base
* Two identifiers share the same base if only the offset
* of the last tuple of each identifier differs.
*
* @param {Identifier} other The other identifier
* @return {boolean} Are the bases equals
*/
equalsBase(other: Identifier): boolean;
/**
* Compare this identifier to another one to order them
* Ordering.Less means that this is less than other
* Ordering.Greater means that this is greater than other
* Ordering.Equal means that this is equal to other
*
* @param {Identifier} other The identifier to compare
* @return {Ordering} The order of the two identifier
*/
compareTo(other: Identifier): Ordering;
/**
* Check if we can generate new identifiers using
* the same base as this without overflowing
*
* @param {number} length The number of characters we want to add
* @return {boolean}
*/
hasPlaceAfter(length: number): boolean;
/**
* Check if we can generate new identifiers using
* the same base as this without underflowing
*
* @param {number} length The number of characters we want to add
* @return {boolean}
*/
hasPlaceBefore(length: number): boolean;
/**
* Compute the offset of the last identifier we can generate using
* the same base as this without overflowing on next
*
* @param {Identifier} next The next identifier
* @param {number} max The desired offset
* @return {number} The actual offset we can use
*/
maxOffsetBeforeNext(next: Identifier, max: number): number;
/**
* Compute the offset of the last identifier we can generate using
* the same base as this without underflowing on prev
*
* @param {Identifier} prev The previous identifier
* @param {number} min The desired offset
* @return {number} The actual offset we can use
*/
minOffsetAfterPrev(prev: Identifier, min: number): number;
digest(): number;
toString(): string;
hasPlaceAfter(next: Identifier, length: number): boolean;
hasPlaceBefore(prev: Identifier, length: number): boolean;
minOffsetAfterPrev(prev: Identifier, min: number): number;
maxOffsetBeforeNext(next: Identifier, max: number): number;
}

394

dist/src/identifier.js

@@ -22,4 +22,4 @@ "use strict";

/**
* Holds the minimum value an integer can have.
*/
* Holds the minimum value an integer can have.
*/
exports.INT_32_MIN_VALUE = -0x80000000;

@@ -30,21 +30,29 @@ /**

exports.INT_32_MAX_VALUE = 0x7fffffff;
var identifiertuple_1 = require("./identifiertuple");
var Identifier = /** @class */ (function () {
// Creation
function Identifier(base, u) {
console.assert(base instanceof Array, "base = ", base);
console.assert(base.every(function (a) { return Number.isInteger(a); }), "Every item is an integer. base = ", base);
console.assert(base.every(function (a) { return a >= exports.INT_32_MIN_VALUE && a <= exports.INT_32_MAX_VALUE; }), "Every item ∈ [INT_32_MIN_VALUE, INT_32_MAX_VALUE]");
console.assert(Number.isInteger(u), "u = ", u);
console.assert(u > exports.INT_32_MIN_VALUE && u <= exports.INT_32_MAX_VALUE, "u ∈ ]INT_32_MIN_VALUE, INT_32_MAX_VALUE]");
this.base = base;
this.last = u;
function Identifier(tuples) {
console.assert(tuples.length > 0, "tuples must not be empty");
this.tuples = tuples;
}
Identifier.fromPlain = function (o) {
if (typeof o === "object" && o !== null) {
var base = o.base;
var last = o.last;
if (base instanceof Array &&
base.every(function (n) { return typeof n === "number" && Number.isInteger(n); }) &&
typeof last === "number" && Number.isInteger(last)) {
return new Identifier(base, last);
var plainTuples = o.tuples;
if (plainTuples instanceof Array && plainTuples.length > 0) {
var isOk = true;
var i = 0;
var tuples = [];
while (isOk && i < plainTuples.length) {
var tuple = identifiertuple_1.IdentifierTuple.fromPlain(plainTuples[i]);
if (tuple !== null) {
tuples.push(tuple);
}
else {
isOk = false;
}
i++;
}
if (isOk) {
return new Identifier(tuples);
}
}

@@ -54,143 +62,271 @@ }

};
Identifier.prototype.compareTo = function (aOther) {
console.assert(aOther instanceof Identifier, "aOther = ", aOther);
var extended = this.base.concat(this.last);
var otherExtended = aOther.base.concat(aOther.last);
var minLength = Math.min(extended.length, otherExtended.length);
/**
* Generate a new Identifier with the same base as the provided one but with a different offset
*
* @param {Identifier} id The identifier to partly copy
* @param {number} offset The last offset of the new Identifier
* @return {IdentifierTuple} The generated Identifier
*/
Identifier.generateWithSameBase = function (id, offset) {
console.assert(Number.isInteger(offset), "offset must be an integer");
console.assert(offset > exports.INT_32_MIN_VALUE && offset <= exports.INT_32_MAX_VALUE, "offset ∈ ]INT_32_MIN_VALUE, INT_32_MAX_VALUE]");
var tuples = id.tuples.map(function (tuple, i) {
if (i === id.length - 1) {
return identifiertuple_1.IdentifierTuple.generateWithSameBase(tuple, offset);
}
return tuple;
});
return new Identifier(tuples);
};
Object.defineProperty(Identifier.prototype, "length", {
/**
* Shortcut to retrieve the length of the Identifier
*
* @return {number} The length
*/
get: function () {
return this.tuples.length;
},
enumerable: true,
configurable: true
});
Object.defineProperty(Identifier.prototype, "lastOffset", {
/**
* Retrieve the offset of the last tuple of the identifier
*
* @return {number} The offset
*/
get: function () {
return this.tuples[this.length - 1].offset;
},
enumerable: true,
configurable: true
});
Object.defineProperty(Identifier.prototype, "base", {
get: function () {
return this.tuples
.reduce(function (acc, tuple, index) {
return acc.concat(tuple.asArray());
}, [])
.filter(function (value, index, array) {
return index !== array.length - 1;
});
},
enumerable: true,
configurable: true
});
/**
* Retrieve the longest common prefix shared by this identifier with another one
*
* @param {Identifier} other The other identifier
* @return {IdentifierTuple[]} The longest common prefix
*/
Identifier.prototype.getLongestCommonPrefix = function (other) {
var commonPrefix = [];
var minLength = Math.min(this.tuples.length, other.tuples.length);
var i = 0;
while (i < minLength && extended[i] === otherExtended[i]) {
while (i < minLength && this.tuples[i].equals(other.tuples[i])) {
commonPrefix.push(this.tuples[i]);
i++;
}
if (i === minLength) {
if (extended.length > minLength) {
return 1 /* Greater */;
return commonPrefix;
};
/**
* Retrieve the longest common base shared by this identifier with another one
*
* @param {Identifier} other The other identifier
* @return {IdentifierTuple[]} The longest common base
*/
Identifier.prototype.getLongestCommonBase = function (other) {
var commonBase = [];
var minLength = Math.min(this.tuples.length, other.tuples.length);
var i = 0;
var stop = false;
while (!stop && i < minLength) {
var tuple = this.tuples[i];
var otherTuple = other.tuples[i];
if (tuple.equals(otherTuple)) {
commonBase.push(tuple);
}
else if (otherExtended.length > minLength) {
return -1 /* Less */;
}
else {
return 0 /* Equal */;
stop = true;
if (tuple.equalsBase(otherTuple)) {
commonBase.push(tuple);
}
}
i++;
}
else {
if (extended[i] < otherExtended[i]) {
return -1 /* Less */;
}
else {
return 1 /* Greater */;
}
return commonBase;
};
/**
* Check if this identifier is a prefix of another one
*
* @param {Identifier} other The other identifier
* @return {boolean} Is this identifier a prefix of other
*/
Identifier.prototype.isPrefix = function (other) {
return this.isBasePrefix(other) &&
this.lastOffset === other.tuples[this.length - 1].offset;
};
/**
* Check if the base of this identifier is a prefix of the other one
*
* @param {Identifier} other The other identifier
* @return {boolean} Is this base a prefix of the other one
*/
Identifier.prototype.isBasePrefix = function (other) {
var _this = this;
return this.length <= other.length &&
this.tuples.every(function (tuple, index) {
var otherTuple = other.tuples[index];
if (index === _this.tuples.length - 1) {
return tuple.equalsBase(otherTuple);
}
return tuple.equals(otherTuple);
});
};
/**
* Compute the common prefix between this identifier and the other one
* and return its length
*
* @param other The other identifier
* @return {number} The length of the common prefix
*/
Identifier.prototype.getLengthCommonPrefix = function (other) {
var minLength = Math.min(this.tuples.length, other.tuples.length);
var i = 0;
while (i < minLength && this.tuples[i].equals(other.tuples[i])) {
i++;
}
return i;
};
Identifier.prototype.equals = function (aOther) {
return this.equalsBase(aOther) && this.last === aOther.last;
Identifier.prototype.equals = function (other) {
return this.equalsBase(other) &&
this.lastOffset === other.lastOffset;
};
/**
* Check if the identifier's {@link Identifier#base} is equals to another identifier's one
* Check if two identifiers share the same base
* Two identifiers share the same base if only the offset
* of the last tuple of each identifier differs.
*
* @param {Identifier} aOther The other identifier
* @returns {boolean} Are the bases equals
* @param {Identifier} other The other identifier
* @return {boolean} Are the bases equals
*/
Identifier.prototype.equalsBase = function (aOther) {
return this.base.length === aOther.base.length
&& this.base.every(function (value, index) { return aOther.base[index] === value; });
Identifier.prototype.equalsBase = function (other) {
var _this = this;
return this.length === other.length &&
this.tuples.every(function (tuple, index) {
var otherTuple = other.tuples[index];
if (index < _this.length - 1) {
return tuple.equals(otherTuple);
}
return tuple.equalsBase(otherTuple);
});
};
Identifier.prototype.toString = function () {
return "Id[" + this.base.concat(this.last).join(", ") + ']';
};
Identifier.prototype.hasPlaceAfter = function (next, length) {
console.assert(next instanceof Identifier, "next = ", next);
console.assert(typeof length === "number", "length = ", length);
var base = this.base;
if (this.last > exports.INT_32_MAX_VALUE - length) {
// last should never be greater than INT_32_MAX_VALUE because of its constraints
return false;
/**
* Compare this identifier to another one to order them
* Ordering.Less means that this is less than other
* Ordering.Greater means that this is greater than other
* Ordering.Equal means that this is equal to other
*
* @param {Identifier} other The identifier to compare
* @return {Ordering} The order of the two identifier
*/
Identifier.prototype.compareTo = function (other) {
if (this.equals(other)) {
return 0 /* Equal */;
}
else if (base.length > next.base.length) {
return true;
if (this.isPrefix(other)) {
return -1 /* Less */;
}
else {
var nextExtended = next.base.concat(next.last);
var minLength = Math.min(base.length, nextExtended.length);
var i = 0;
while (i < minLength && base[i] === nextExtended[i]) {
i++;
}
if (i !== minLength) {
// Bases differ
return true;
}
else {
var max = length + this.last;
return nextExtended[i] >= max;
}
if (other.isPrefix(this)) {
return 1 /* Greater */;
}
var index = this.getLengthCommonPrefix(other);
return this.tuples[index].compareTo(other.tuples[index]);
};
Identifier.prototype.hasPlaceBefore = function (prev, length) {
console.assert(prev instanceof Identifier, "prv = ", prev);
console.assert(typeof length === "number" && Number.isInteger(length), "length = ", length);
var base = this.base;
if (this.last <= exports.INT_32_MIN_VALUE + length) {
// last should never be less than or equal to INT_32_MIN_VALUE because of its constraints
return false;
/**
* Check if we can generate new identifiers using
* the same base as this without overflowing
*
* @param {number} length The number of characters we want to add
* @return {boolean}
*/
Identifier.prototype.hasPlaceAfter = function (length) {
// Precondition: the node which contains this identifier must be appendableAfter()
console.assert(Number.isInteger(length), "length must be an integer");
console.assert(length > 0, "length must be superior to 0 ");
// Prevent an overflow when computing lastOffset + length
return this.lastOffset <= exports.INT_32_MAX_VALUE - length;
};
/**
* Check if we can generate new identifiers using
* the same base as this without underflowing
*
* @param {number} length The number of characters we want to add
* @return {boolean}
*/
Identifier.prototype.hasPlaceBefore = function (length) {
// Precondition: the node which contains this identifier must be appendableBefore()
console.assert(Number.isInteger(length), "length must be an integer");
console.assert(length > 0, "length must be superior to 0 ");
// Prevent an underflow when computing lastOffset - length
return this.lastOffset > exports.INT_32_MIN_VALUE + length;
};
/**
* Compute the offset of the last identifier we can generate using
* the same base as this without overflowing on next
*
* @param {Identifier} next The next identifier
* @param {number} max The desired offset
* @return {number} The actual offset we can use
*/
Identifier.prototype.maxOffsetBeforeNext = function (next, max) {
console.assert(Number.isInteger(max), "max must be an integer");
console.assert(this.compareTo(next) === -1 /* Less */, "this must be less than next");
if (this.equalsBase(next)) {
// Happen if we receive append/prepend operations in causal disorder
console.assert(max < next.lastOffset, "max must be less than next.lastOffset");
return max;
}
else if (base.length > prev.base.length) {
return true;
if (this.isBasePrefix(next)) {
// Happen if we receive split operations in causal disorder
var offset = next.tuples[this.length - 1].offset;
return Math.min(offset, max);
}
else {
var prevExtended = prev.base.concat(prev.last);
var minLength = Math.min(base.length, prevExtended.length);
var i = 0;
while (i < minLength && base[i] === prevExtended[i]) {
i++;
}
if (i !== minLength) {
// Bases differ
return true;
}
else {
var min = this.last - length;
return prevExtended[i] < min;
}
}
// Bases differ
return max;
};
/**
* Compute the offset of the last identifier we can generate using
* the same base as this without underflowing on prev
*
* @param {Identifier} prev The previous identifier
* @param {number} min The desired offset
* @return {number} The actual offset we can use
*/
Identifier.prototype.minOffsetAfterPrev = function (prev, min) {
console.assert(prev instanceof Identifier, "prev = ", prev);
console.assert(typeof min === "number" && Number.isInteger(min), "min = ", min);
var base = this.base;
var prevExtended = prev.base.concat(prev.last);
var minLength = Math.min(base.length, prevExtended.length);
var i = 0;
while (i < minLength && base[i] === prevExtended[i]) {
i++;
}
if (i === minLength && i < prevExtended.length) {
// base is a prefix of prevBase
return Math.max(prevExtended[i] + 1, min);
}
else {
if (this.equalsBase(prev)) {
// Happen if we receive append/prepend operations in causal disorder
console.assert(min > prev.lastOffset, "min must be greater than prev.lastOffset");
return min;
}
};
Identifier.prototype.maxOffsetBeforeNext = function (next, max) {
console.assert(next instanceof Identifier, "next = ", next);
console.assert(typeof max === "number" && Number.isInteger(max), "max = ", max);
var base = this.base;
var nextExtended = next.base.concat(next.last);
var minLength = Math.min(base.length, nextExtended.length);
var i = 0;
while (i < minLength && base[i] === nextExtended[i]) {
i++;
if (this.isBasePrefix(prev)) {
// Happen if we receive split operations in causal disorder
var offset = prev.tuples[this.length - 1].offset;
return Math.max(offset + 1, min);
}
if (i === minLength && i < nextExtended.length) {
// base is a prefix of nextBase
if (base.length < next.base.length) {
// length of base is less than length of nextBase
return Math.min(nextExtended[i], max);
}
return Math.min(nextExtended[i] - 1, max);
}
else {
return max;
}
// Bases differ
return min;
};
Identifier.prototype.digest = function () {
return this.tuples.reduce(function (prev, tuple) {
return (prev * 17 + tuple.digest()) | 0;
}, 0);
};
Identifier.prototype.toString = function () {
return "Id[" + this.tuples.join(",") + "]";
};
return Identifier;

@@ -197,0 +333,0 @@ }());

52

dist/src/identifierinterval.d.ts
import { SafeAny } from "safe-any";
import { Identifier } from './identifier';
/**
* Define an interval between two identifiers sharing the same base
*/
export declare class IdentifierInterval {
constructor(base: number[], begin: number, end: number);
constructor(idBegin: Identifier, end: number);
static fromPlain(o: SafeAny<IdentifierInterval>): IdentifierInterval | null;
readonly idBegin: Identifier;
readonly end: number;
/**
* Shortcut to retrieve the offset of the last tuple of idBegin
* This offset also corresponds to the beginning of the interval
*
* @return {number} The offset
*/
readonly begin: number;
/**
* Shortcut to retrieve the last identifier of the interval
*
* @return {Identifier} The last identifier of the interval
*/
readonly idEnd: Identifier;
/**
* Shortcut to compute the length of the interval
*
* @return {number} The length
*/
readonly length: number;
readonly base: number[];
readonly begin: number;
readonly end: number;
equals(aOther: IdentifierInterval): boolean;
/**
* Compute the union between this interval and [aBegin, aEnd]
*
* @param {number} aBegin
* @param {number} aEnd
* @return {IdentifierInterval} this U [aBegin, aEnd]
*/
union(aBegin: number, aEnd: number): IdentifierInterval;
getBaseId(u: number): Identifier;
getBeginId(): Identifier;
getEndId(): Identifier;
/**
* Check if the provided identifier belongs to this interval
*
* @param {Identifier} id
* @return {boolean} Does the identifier belongs to this interval
*/
containsId(id: Identifier): boolean;
/**
* Retrieve a identifier from the interval from its offset
*
* @param {number} offset The offset of the identifier
* @return {Identifier} The identifier
*/
getBaseId(offset: number): Identifier;
digest(): number;
toString(): string;
}

122

dist/src/identifierinterval.js

@@ -22,11 +22,11 @@ "use strict";

var identifier_1 = require("./identifier");
/**
* Define an interval between two identifiers sharing the same base
*/
var IdentifierInterval = /** @class */ (function () {
// Creation
function IdentifierInterval(base, begin, end) {
console.assert(base instanceof Array, "base = ", base);
console.assert(typeof begin === "number" && Number.isInteger(begin), "begin = ", begin);
console.assert(typeof end === "number" && Number.isInteger(end), "end = ", end);
console.assert(begin <= end, "begin <= end: " + begin + " <= ", end);
this.base = base;
this.begin = begin;
function IdentifierInterval(idBegin, end) {
console.assert(Number.isInteger(end), "end must be an integer");
console.assert(idBegin.lastOffset <= end, "idBegin must be less than or equal to idEnd");
this.idBegin = idBegin;
this.end = end;

@@ -36,12 +36,6 @@ }

if (typeof o === "object" && o !== null) {
var base = o.base;
var begin = o.begin;
var end = o.end;
if (base instanceof Array && base.every(function (n) {
return typeof n === "number" && Number.isInteger(n);
}) &&
typeof begin === "number" && typeof end === "number" &&
Number.isInteger(begin) && Number.isInteger(end) &&
begin <= end) {
return new IdentifierInterval(base, begin, end);
var idBegin = identifier_1.Identifier.fromPlain(o.idBegin);
if (idBegin !== null && typeof o.end === "number" &&
Number.isInteger(o.end) && idBegin.lastOffset <= o.end) {
return new IdentifierInterval(idBegin, o.end);
}

@@ -51,32 +45,92 @@ }

};
Object.defineProperty(IdentifierInterval.prototype, "begin", {
/**
* Shortcut to retrieve the offset of the last tuple of idBegin
* This offset also corresponds to the beginning of the interval
*
* @return {number} The offset
*/
get: function () {
return this.idBegin.lastOffset;
},
enumerable: true,
configurable: true
});
Object.defineProperty(IdentifierInterval.prototype, "idEnd", {
/**
* Shortcut to retrieve the last identifier of the interval
*
* @return {Identifier} The last identifier of the interval
*/
get: function () {
return this.getBaseId(this.end);
},
enumerable: true,
configurable: true
});
Object.defineProperty(IdentifierInterval.prototype, "length", {
/**
* Shortcut to compute the length of the interval
*
* @return {number} The length
*/
get: function () {
return this.end - this.begin + 1;
},
enumerable: true,
configurable: true
});
Object.defineProperty(IdentifierInterval.prototype, "base", {
get: function () {
return this.idBegin.base;
},
enumerable: true,
configurable: true
});
IdentifierInterval.prototype.equals = function (aOther) {
return this.base.length === aOther.base.length &&
this.base.every(function (value, index) {
return value === aOther.base[index];
}) &&
return this.idBegin.equals(aOther.idBegin) &&
this.begin === aOther.begin && this.end === aOther.end;
};
/**
* Compute the union between this interval and [aBegin, aEnd]
*
* @param {number} aBegin
* @param {number} aEnd
* @return {IdentifierInterval} this U [aBegin, aEnd]
*/
IdentifierInterval.prototype.union = function (aBegin, aEnd) {
console.assert(Number.isInteger(aBegin), "aBegin must be an integer");
console.assert(Number.isInteger(aEnd), "aEnd must be an integer");
var minBegin = Math.min(this.begin, aBegin);
var maxEnd = Math.max(this.end, aEnd);
return new IdentifierInterval(this.base, minBegin, maxEnd);
var newIdBegin = identifier_1.Identifier.generateWithSameBase(this.idBegin, minBegin);
return new IdentifierInterval(newIdBegin, maxEnd);
};
IdentifierInterval.prototype.getBaseId = function (u) {
console.assert(typeof u === "number" && Number.isInteger(u), "u = ", u);
return new identifier_1.Identifier(this.base, u);
/**
* Check if the provided identifier belongs to this interval
*
* @param {Identifier} id
* @return {boolean} Does the identifier belongs to this interval
*/
IdentifierInterval.prototype.containsId = function (id) {
return this.idBegin.compareTo(id) === -1 /* Less */ &&
this.idEnd.compareTo(id) === 1 /* Greater */;
};
IdentifierInterval.prototype.getBeginId = function () {
return this.getBaseId(this.begin);
/**
* Retrieve a identifier from the interval from its offset
*
* @param {number} offset The offset of the identifier
* @return {Identifier} The identifier
*/
IdentifierInterval.prototype.getBaseId = function (offset) {
console.assert(Number.isInteger(offset), "offset must be an integer");
console.assert(this.begin <= offset && offset <= this.end, "offset must be included in the interval");
return identifier_1.Identifier.generateWithSameBase(this.idBegin, offset);
};
IdentifierInterval.prototype.getEndId = function () {
return this.getBaseId(this.end);
};
IdentifierInterval.prototype.digest = function () {
// '| 0' converts to 32bits integer
var baseDigest = this.base.reduce(function (prev, v) { return (prev * 17 + v) | 0; }, 0);
return ((this.begin * 17 + this.end) * 17 + baseDigest) | 0;
return (this.idBegin.digest() * 17 + this.end) | 0;
};
IdentifierInterval.prototype.toString = function () {
return 'Id[' + this.base.join(",") + ', ' +
this.begin + ' .. ' + this.end + ']';
return "IdInterval[" + this.idBegin.tuples.join(",") + " .. " + this.end + "]";
};

@@ -83,0 +137,0 @@ return IdentifierInterval;

4

dist/src/idfactory.d.ts
import { Identifier } from './identifier';
export declare function isMine(replica: number): (b: number[]) => boolean;
export declare function createBetweenPosition(id1: Identifier | null, id2: Identifier | null, replicaNumber: number, clock: number): number[];
export declare function isMine(replica: number): (id: Identifier) => boolean;
export declare function createBetweenPosition(id1: Identifier | null, id2: Identifier | null, replicaNumber: number, clock: number): Identifier;

106

dist/src/idfactory.js

@@ -20,24 +20,54 @@ "use strict";

*/
var __generator = (this && this.__generator) || function (thisArg, body) {
var _ = { label: 0, sent: function() { if (t[0] & 1) throw t[1]; return t[1]; }, trys: [], ops: [] }, f, y, t, g;
return g = { next: verb(0), "throw": verb(1), "return": verb(2) }, typeof Symbol === "function" && (g[Symbol.iterator] = function() { return this; }), g;
function verb(n) { return function (v) { return step([n, v]); }; }
function step(op) {
if (f) throw new TypeError("Generator is already executing.");
while (_) try {
if (f = 1, y && (t = y[op[0] & 2 ? "return" : op[0] ? "throw" : "next"]) && !(t = t.call(y, op[1])).done) return t;
if (y = 0, t) op = [0, t.value];
switch (op[0]) {
case 0: case 1: t = op; break;
case 4: _.label++; return { value: op[1], done: false };
case 5: _.label++; y = op[1]; op = [0]; continue;
case 7: op = _.ops.pop(); _.trys.pop(); continue;
default:
if (!(t = _.trys, t = t.length > 0 && t[t.length - 1]) && (op[0] === 6 || op[0] === 2)) { _ = 0; continue; }
if (op[0] === 3 && (!t || (op[1] > t[0] && op[1] < t[3]))) { _.label = op[1]; break; }
if (op[0] === 6 && _.label < t[1]) { _.label = t[1]; t = op; break; }
if (t && _.label < t[2]) { _.label = t[2]; _.ops.push(op); break; }
if (t[2]) _.ops.pop();
_.trys.pop(); continue;
}
op = body.call(thisArg, _);
} catch (e) { op = [6, e]; y = 0; } finally { f = t = 0; }
if (op[0] & 5) throw op[1]; return { value: op[0] ? op[1] : void 0, done: true };
}
};
Object.defineProperty(exports, "__esModule", { value: true });
var identifier_1 = require("./identifier");
var infinitestring_1 = require("./infinitestring");
var identifiertuple_1 = require("./identifiertuple");
function isMine(replica) {
return function (base) { return base[base.length - 2] === replica; };
return function (id) { return id.tuples[id.length - 1].replicaNumber === replica; };
}
exports.isMine = isMine;
function createBetweenPosition(id1, id2, replicaNumber, clock) {
console.assert(id1 === null || id1 instanceof identifier_1.Identifier, "id1 = " + id1);
console.assert(id2 === null || id2 instanceof identifier_1.Identifier, "id2 = ", id2);
console.assert(typeof replicaNumber === "number", "replicaNumber = ", replicaNumber);
console.assert(typeof clock === "number", "clock = ", clock);
var s1 = new infinitestring_1.InfiniteString(id1 !== null ? id1.base.concat(id1.last) : [], identifier_1.INT_32_MIN_VALUE);
var s2 = new infinitestring_1.InfiniteString(id2 !== null ? id2.base.concat(id2.last) : [], identifier_1.INT_32_MAX_VALUE);
var sb = [];
console.assert(Number.isInteger(replicaNumber), "replicaNumber must be an integer");
console.assert(Number.isInteger(clock) && clock >= 0, "clock must be a positive integer");
var minTuple = new identifiertuple_1.IdentifierTuple(identifier_1.INT_32_MIN_VALUE, 0, 0, 0);
var maxTuple = new identifiertuple_1.IdentifierTuple(identifier_1.INT_32_MAX_VALUE, 0, 0, 0);
var tuples1 = id1 !== null ? id1.tuples : [];
var seq1 = infiniteSequence(tuples1, minTuple);
var tuples2 = id2 !== null ? id2.tuples : [];
var seq2 = infiniteSequence(tuples2, maxTuple);
var tuples = [];
do {
var b1 = s1.next();
var b2 = s2.next();
if (b2 - b1 > 2) {
var f = (Math.random() * (b2 - b1 - 2)) + b1 + 1; // Generate a random number ∈ ]b1, b2[
var i = f | 0; // Truncate the float in order to get a 32bits int
sb.push(i);
var tuple1 = seq1.next().value;
var tuple2 = seq2.next().value;
if (tuple2.random - tuple1.random > 2) {
// Can insert a new tuple between tuple1 and tuple2
var newRandom = (Math.random() * (tuple2.random - tuple1.random - 2)) + tuple1.random + 1; // Generate a random number ∈ ]b1, b2[
var i = newRandom | 0; // Truncate the float in order to get a 32bits int
tuples.push(new identifiertuple_1.IdentifierTuple(i, replicaNumber, clock, 0));
break;

@@ -47,15 +77,43 @@ }

// Copy the whole tuple <random, replicaNumber, clock, offset>
sb.push(b1);
for (var i = 0; i < 3; i++) {
sb.push(s1.next());
s2.next();
}
tuples.push(tuple1);
}
} while (true);
sb.push(replicaNumber);
sb.push(clock);
console.assert(isMine(replicaNumber)(sb), "replica = " + replicaNumber + " base = ", sb);
return sb;
var id = new identifier_1.Identifier(tuples);
console.assert(isMine(replicaNumber)(id), "the generated identifier must belong to me");
return id;
}
exports.createBetweenPosition = createBetweenPosition;
/**
* Generate an infinite sequence of tuples
*
* @param tuples
* @param defaultValue
*/
function infiniteSequence(tuples, defaultValue) {
var _i, tuples_1, tuple;
return __generator(this, function (_a) {
switch (_a.label) {
case 0:
_i = 0, tuples_1 = tuples;
_a.label = 1;
case 1:
if (!(_i < tuples_1.length)) return [3 /*break*/, 4];
tuple = tuples_1[_i];
return [4 /*yield*/, tuple];
case 2:
_a.sent();
_a.label = 3;
case 3:
_i++;
return [3 /*break*/, 1];
case 4:
if (!true) return [3 /*break*/, 6];
return [4 /*yield*/, defaultValue];
case 5:
_a.sent();
return [3 /*break*/, 4];
case 6: return [2 /*return*/];
}
});
}
//# sourceMappingURL=idfactory.js.map

1

dist/src/index.d.ts

@@ -0,1 +1,2 @@

export { IdentifierTuple } from './identifiertuple';
export { Identifier } from './identifier';

@@ -2,0 +3,0 @@ export { IdentifierInterval } from './identifierinterval';

2

dist/src/index.js

@@ -21,2 +21,4 @@ "use strict";

Object.defineProperty(exports, "__esModule", { value: true });
var identifiertuple_1 = require("./identifiertuple");
exports.IdentifierTuple = identifiertuple_1.IdentifierTuple;
var identifier_1 = require("./identifier");

@@ -23,0 +25,0 @@ exports.Identifier = identifier_1.Identifier;

105

dist/src/iteratorhelperidentifier.js

@@ -22,78 +22,57 @@ "use strict";

function compareBase(idInterval1, idInterval2) {
var b1 = idInterval1.base;
var id1 = idInterval1.idBegin;
var begin1 = idInterval1.begin;
var end1 = idInterval1.end;
var b2 = idInterval2.base;
var id2 = idInterval2.idBegin;
var begin2 = idInterval2.begin;
var end2 = idInterval2.end;
var minLength = Math.min(b1.length, b2.length);
var i = 0;
while (i < minLength && b1[i] === b2[i]) {
i++;
}
if (i === minLength) {
if (b1.length > minLength) {
var offset = b1[i];
if (offset < begin2) {
return 1 /* B1_BEFORE_B2 */;
}
else if (offset >= end2) {
return 0 /* B1_AFTER_B2 */;
}
else {
return 2 /* B1_INSIDE_B2 */;
}
if (id1.equalsBase(id2)) {
if (begin1 === begin2 && end1 === end2) {
return 6 /* B1_EQUALS_B2 */;
}
else if (b2.length > minLength) {
var offset = b2[i];
if (offset < begin1) {
return 0 /* B1_AFTER_B2 */;
}
else if (offset >= end1) {
return 1 /* B1_BEFORE_B2 */;
}
else {
return 3 /* B2_INSIDE_B1 */;
}
else if ((end1 + 1) === begin2) {
return 4 /* B1_CONCAT_B2 */;
}
else if (begin1 === (end2 + 1)) {
return 5 /* B2_CONCAT_B1 */;
}
else if (end1 < begin2) {
return 1 /* B1_BEFORE_B2 */;
}
else if (end2 < begin1) {
return 0 /* B1_AFTER_B2 */;
}
else {
if (begin1 === begin2 && end1 === end2) {
return 6 /* B1_EQUALS_B2 */;
}
else if ((end1 + 1) === begin2) {
return 4 /* B1_CONCAT_B2 */;
}
else if (begin1 === (end2 + 1)) {
return 5 /* B2_CONCAT_B1 */;
}
else if (end1 < begin2) {
return 1 /* B1_BEFORE_B2 */;
}
else if (end2 < begin1) {
return 0 /* B1_AFTER_B2 */;
}
else {
/*
(B2 ⊂ B1) || (B1 ⊂ B2) || (B1 ∩ B2 !== {})
It happens only in the following cases:
- An already applied operation is delivered again,
but the interval has since then been updated
(append, prepend, deletion at the bounds)
- It is a malicious operation which try to insert
again some identifiers
For now, do not do anything in both cases.
*/
console.warn('Trying to duplicate existing identifiers: ', idInterval1, idInterval2);
return 6 /* B1_EQUALS_B2 */;
}
/*
(B2 ⊂ B1) || (B1 ⊂ B2) || (B1 ∩ B2 !== {})
It happens only in the following cases:
- An already applied operation is delivered again,
but the interval has since then been updated
(append, prepend, deletion at the bounds)
- It is a malicious operation which try to insert
again some identifiers
For now, do not do anything in both cases.
*/
console.warn('Trying to duplicate existing identifiers: ', idInterval1, idInterval2);
return 6 /* B1_EQUALS_B2 */;
}
}
else if (b1[i] > b2[i]) {
return 0 /* B1_AFTER_B2 */;
return compareIntervalsDifferentBases(idInterval1, idInterval2);
}
exports.compareBase = compareBase;
function compareIntervalsDifferentBases(idInterval1, idInterval2) {
var id1 = idInterval1.idBegin;
var id2 = idInterval2.idBegin;
console.assert(!id1.equalsBase(id2), "the bases of the ids must be different");
if (idInterval1.containsId(id2)) {
return 3 /* B2_INSIDE_B1 */;
}
else {
if (idInterval2.containsId(id1)) {
return 2 /* B1_INSIDE_B2 */;
}
if (id1.compareTo(id2) === -1 /* Less */) {
return 1 /* B1_BEFORE_B2 */;
}
return 0 /* B1_AFTER_B2 */;
}
exports.compareBase = compareBase;
//# sourceMappingURL=iteratorhelperidentifier.js.map

4

dist/src/logootsropes.d.ts

@@ -22,3 +22,3 @@ import { SafeAny } from "safe-any";

str: string;
getBlock(id: IdentifierInterval): LogootSBlock;
getBlock(idInterval: IdentifierInterval): LogootSBlock;
/**

@@ -43,3 +43,3 @@ * Add a interval of identifiers and its corresponding string to the model

ascendentUpdate(path: RopesNodes[], length: number): void;
delBlock(id: IdentifierInterval): TextDelete[];
delBlock(idInterval: IdentifierInterval): TextDelete[];
delLocal(begin: number, end: number): LogootSDel;

@@ -46,0 +46,0 @@ delNode(path: RopesNodes[]): void;

77

dist/src/logootsropes.js

@@ -79,6 +79,5 @@ "use strict";

};
LogootSRopes.prototype.getBlock = function (id) {
console.assert(id instanceof identifierinterval_1.IdentifierInterval, "id = ", id);
LogootSRopes.prototype.getBlock = function (idInterval) {
var mapBaseToBlock = this.mapBaseToBlock;
var key = id.base.join(",");
var key = idInterval.base.join(",");
var result;

@@ -89,3 +88,3 @@ if (mapBaseToBlock.hasOwnProperty(key)) {

else {
result = new logootsblock_1.LogootSBlock(id, 0);
result = new logootsblock_1.LogootSBlock(idInterval, 0);
this.mapBaseToBlock[key] = result;

@@ -147,4 +146,4 @@ }

// split b2 the object node
var indexOffset = from.getIdBegin().base.length;
var offsetToSplit = idi.base[indexOffset];
var indexOffset = from.getIdBegin().length - 1;
var offsetToSplit = idi.idBegin.tuples[indexOffset].offset;
var rp = ropesnodes_1.RopesNodes.leaf(this.getBlock(idi), idi.begin, str.length);

@@ -159,6 +158,6 @@ path.push(from.split(offsetToSplit - from.actualBegin + 1, rp));

// split b1 the node to insert
var indexOffset = idi.base.length;
var offsetToSplit = from.getIdBegin().base[indexOffset];
var indexOffset = idi.idBegin.length - 1;
var offsetToSplit = from.getIdBegin().tuples[indexOffset].offset;
var ls = str.substr(0, offsetToSplit + 1 - idi.begin);
var idi1 = new identifierinterval_1.IdentifierInterval(idi.base, idi.begin, offsetToSplit);
var idi1 = new identifierinterval_1.IdentifierInterval(idi.idBegin, offsetToSplit);
if (from.left === null) {

@@ -173,3 +172,4 @@ from.left = ropesnodes_1.RopesNodes.leaf(this.getBlock(idi1), idi1.begin, ls.length);

ls = str.substr(offsetToSplit + 1 - idi.begin, str.length);
idi1 = new identifierinterval_1.IdentifierInterval(idi.base, offsetToSplit + 1, idi.end);
var newIdBegin = identifier_1.Identifier.generateWithSameBase(idi.idBegin, offsetToSplit + 1);
idi1 = new identifierinterval_1.IdentifierInterval(newIdBegin, idi.end);
i = i + from.leftSubtreeSize() + from.length;

@@ -197,3 +197,3 @@ if (from.right === null) {

str = str.substr(0, split - idi.begin);
idi = new identifierinterval_1.IdentifierInterval(idi.base, idi.begin, split - 1);
idi = new identifierinterval_1.IdentifierInterval(idi.idBegin, split - 1);
from = from.left;

@@ -224,3 +224,4 @@ }

str = str.substr(split + 1 - idi.begin, str.length);
idi = new identifierinterval_1.IdentifierInterval(idi.base, split + 1, idi.end);
var newIdBegin = identifier_1.Identifier.generateWithSameBase(idi.idBegin, split + 1);
idi = new identifierinterval_1.IdentifierInterval(newIdBegin, idi.end);
from = from.right;

@@ -263,7 +264,7 @@ i = i + l.length;

console.assert(id instanceof identifier_1.Identifier, "id = ", id);
var idi = new identifierinterval_1.IdentifierInterval(id.base, id.last, id.last + str.length - 1);
var idi = new identifierinterval_1.IdentifierInterval(id, id.lastOffset + str.length - 1);
if (this.root === null) {
var bl = new logootsblock_1.LogootSBlock(idi, 0);
this.mapBaseToBlock[bl.idInterval.base.join(",")] = bl;
this.root = ropesnodes_1.RopesNodes.leaf(bl, id.last, str.length);
this.root = ropesnodes_1.RopesNodes.leaf(bl, id.lastOffset, str.length);
var textInsert = new textinsert_1.TextInsert(0, str);

@@ -282,4 +283,4 @@ this.applyTextInsert(textInsert);

console.assert(length > 0, "" + length, " > 0");
var base = IDFactory.createBetweenPosition(id1, id2, this.replicaNumber, this.clock++);
var idi = new identifierinterval_1.IdentifierInterval(base, 0, length - 1);
var id = IDFactory.createBetweenPosition(id1, id2, this.replicaNumber, this.clock++);
var idi = new identifierinterval_1.IdentifierInterval(id, length - 1);
var newBlock = logootsblock_1.LogootSBlock.mine(idi, 0);

@@ -345,3 +346,3 @@ this.mapBaseToBlock[idi.base.join(",")] = newBlock;

if (inPos.node.isAppendableBefore() &&
inPos.node.getIdBegin().hasPlaceBefore(prev.node.getIdEnd(), l.length)) {
inPos.node.getIdBegin().hasPlaceBefore(l.length)) {
// append before

@@ -353,3 +354,3 @@ var id5 = inPos.node.appendBegin(l.length);

else if (prev.node.isAppendableAfter() &&
prev.node.getIdEnd().hasPlaceAfter(inPos.node.getIdBegin(), l.length)) {
prev.node.getIdEnd().hasPlaceAfter(l.length)) {
// append after

@@ -445,5 +446,4 @@ var id4 = prev.node.appendEnd(l.length);

};
LogootSRopes.prototype.delBlock = function (id) {
LogootSRopes.prototype.delBlock = function (idInterval) {
var _this = this;
console.assert(id instanceof identifierinterval_1.IdentifierInterval, "id = ", id);
var l = [];

@@ -453,8 +453,10 @@ var i;

var path = [];
i = this.searchPos(id.getBeginId(), path);
i = this.searchPos(idInterval.idBegin, path);
if (i === -1) {
// Could not find the first identifier from the interval
if (id.begin < id.end) {
if (idInterval.begin < idInterval.end) {
// Shifting the interval and resuming the search
id = new identifierinterval_1.IdentifierInterval(id.base, id.begin + 1, id.end);
var newIdBegin = identifier_1.Identifier.generateWithSameBase(idInterval.idBegin, idInterval.begin + 1);
idInterval =
new identifierinterval_1.IdentifierInterval(newIdBegin, idInterval.end);
}

@@ -468,7 +470,7 @@ else {

var node = path[path.length - 1]; // Retrieving the node containing the identifier
var end = Math.min(id.end, node.actualEnd);
var pos = i + id.begin - node.actualBegin;
var length = end - id.begin + 1;
var end = Math.min(idInterval.end, node.actualEnd);
var pos = i + idInterval.begin - node.actualBegin;
var length = end - idInterval.begin + 1;
l.push(new textdelete_1.TextDelete(pos, length));
var t = node.deleteOffsets(id.begin, end);
var t = node.deleteOffsets(idInterval.begin, end);
if (node.length === 0) {

@@ -483,5 +485,5 @@ this.delNode(path);

// TODO: Check second argument
this.ascendentUpdate(path, id.begin - end - 1);
this.ascendentUpdate(path, idInterval.begin - end - 1);
}
if (end === id.end) {
if (end === idInterval.end) {
break;

@@ -491,3 +493,4 @@ }

// TODO: Check if still valid
id = new identifierinterval_1.IdentifierInterval(id.base, end, id.end);
var newIdBegin = identifier_1.Identifier.generateWithSameBase(idInterval.idBegin, end);
idInterval = new identifierinterval_1.IdentifierInterval(newIdBegin, idInterval.end);
}

@@ -511,7 +514,9 @@ }

if (start !== null) {
var be = start.node.actualBegin + start.i;
var en = Math.min(be + length - 1, start.node.actualEnd);
li.push(new identifierinterval_1.IdentifierInterval(start.node.block.idInterval.base, be, en));
var r = start.node.deleteOffsets(be, en);
length -= en - be + 1;
var newBegin = start.node.actualBegin + start.i;
var newEnd = Math.min(newBegin + length - 1, start.node.actualEnd);
var prevIdBegin = start.node.getIdBegin();
var newIdBegin = identifier_1.Identifier.generateWithSameBase(prevIdBegin, newBegin);
li.push(new identifierinterval_1.IdentifierInterval(newIdBegin, newEnd));
var r = start.node.deleteOffsets(newBegin, newEnd);
length -= newEnd - newBegin + 1;
if (start.node.length === 0) {

@@ -525,3 +530,3 @@ this.delNode(start.path);

else {
this.ascendentUpdate(start.path, be - en - 1);
this.ascendentUpdate(start.path, newBegin - newEnd - 1);
}

@@ -528,0 +533,0 @@ }

6

dist/src/ropesnodes.js

@@ -209,3 +209,3 @@ "use strict";

RopesNodes.prototype.toString = function () {
var current = (new identifierinterval_1.IdentifierInterval(this.block.idInterval.base, this.actualBegin, this.actualEnd)).toString();
var current = this.getIdentifierInterval().toString();
var leftToString = (this.left !== null) ? this.left.toString() : "\t#";

@@ -221,3 +221,3 @@ var rightToString = (this.right !== null) ? this.right.toString() : "\t#";

RopesNodes.prototype.toList = function () {
var idInterval = new identifierinterval_1.IdentifierInterval(this.block.idInterval.base, this.actualBegin, this.actualEnd);
var idInterval = this.getIdentifierInterval();
var leftList = (this.left !== null) ? this.left.toList() : [];

@@ -228,3 +228,3 @@ var rightList = (this.right !== null) ? this.right.toList() : [];

RopesNodes.prototype.getIdentifierInterval = function () {
return new identifierinterval_1.IdentifierInterval(this.block.idInterval.base, this.actualBegin, this.actualEnd);
return new identifierinterval_1.IdentifierInterval(this.getIdBegin(), this.actualEnd);
};

@@ -231,0 +231,0 @@ RopesNodes.prototype.getBlocks = function () {

2

package.json
{
"name": "mute-structs",
"version": "0.3.3",
"version": "0.4.0-0",
"description": "NodeJS module providing an implementation of the LogootSplit CRDT algorithm",

@@ -5,0 +5,0 @@ "main": "./dist/src/index.js",

dist/src/infinitestring.d.ts
dist/src/infinitestring.js
SocketSocket SOC 2 Logo

Product

  • Package Alerts
  • Integrations
  • Docs
  • Pricing
  • FAQ
  • Roadmap
  • Changelog

About

Packages

npm

Go

Maven

PyPI

Rubygems

Stay in touch

Get open source security insights delivered straight into your inbox.

  • Terms
  • Privacy
  • Security

Made with ⚡️ by Socket Inc