const convertHrtime = require('convert-hrtime');
const d3array = require('d3-array')
export function timeit(n: number, f: any, args: any[]) {
let sum = 0.0;
for (i=0; i<n; i++) {
start = process.hrtime();
f.apply(null, args);
end = process.hrtime(start);
sum += convertHrtime(end).milliseconds;
}
return sum/n;
}
namespace Private {
export
function createTriplet(path: number, version: number, store: number): string {
// Split the path into 16-bit values.
let pc = path & 0xFFFF;
let pb = (((path - pc) / 0x10000) | 0) & 0xFFFF;
let pa = (((path - pb - pc) / 0x100000000) | 0) & 0xFFFF;
// Split the version into 16-bit values.
let vc = version & 0xFFFF;
let vb = (((version - vc) / 0x10000) | 0) & 0xFFFF;
let va = (((version - vb - vc) / 0x100000000) | 0) & 0xFFFF;
// Split the store id into 16-bit values.
let sb = store & 0xFFFF;
let sa = (((store - sb) / 0x10000) | 0) & 0xFFFF;
// Convert the parts into a string identifier triplet.
return String.fromCharCode(pa, pb, pc, va, vb, vc, sa, sb);
}
export
function idTripletCount(id: string): number {
return id.length >> 3;
}
export
function idPathAt(id: string, i: number): number {
let j = i << 3;
let a = id.charCodeAt(j + 0);
let b = id.charCodeAt(j + 1);
let c = id.charCodeAt(j + 2);
return a * 0x100000000 + b * 0x10000 + c;
}
export
function idVersionAt(id: string, i: number): number {
let j = i << 3;
let a = id.charCodeAt(j + 3);
let b = id.charCodeAt(j + 4);
let c = id.charCodeAt(j + 5);
return a * 0x100000000 + b * 0x10000 + c;
}
export
function idStoreAt(id: string, i: number): number {
let j = i << 3;
let a = id.charCodeAt(j + 6);
let b = id.charCodeAt(j + 7);
return a * 0x10000 + b;
}
export
function randomPath(min: number, max: number): number {
return min + Math.round(Math.random() * Math.sqrt(max - min));
}
}
export
function createDuplexId(version: number, store: number): string {
// Split the version into 16-bit values.
let vc = version & 0xFFFF;
let vb = (((version - vc) / 0x10000) | 0) & 0xFFFF;
let va = (((version - vb - vc) / 0x100000000) | 0) & 0xFFFF;
// Split the store id into 16-bit values.
let sb = store & 0xFFFF;
let sa = (((store - sb) / 0x10000) | 0) & 0xFFFF;
// Convert the parts into a string identifier duplex.
return String.fromCharCode(va, vb, vc, sa, sb);
}
export
function createTriplexId(version: number, store: number, lower: string, upper: string): string {
// The maximum path in a triplex id.
const MAX_PATH = 0xFFFFFFFFFFFF;
// Set up the variable to hold the id.
let id = '';
// Fetch the triplet counts of the ids.
let lowerCount = lower ? Private.idTripletCount(lower) : 0;
let upperCount = upper ? Private.idTripletCount(upper) : 0;
// Iterate over the id triplets.
for (let i = 0, n = Math.max(lowerCount, upperCount); i < n; ++i) {
// Fetch the lower identifier triplet, padding as needed.
let lp: number;
let lc: number;
let ls: number;
if (i >= lowerCount) {
lp = 0;
lc = 0;
ls = 0;
} else {
lp = Private.idPathAt(lower, i);
lc = Private.idVersionAt(lower, i);
ls = Private.idStoreAt(lower, i);
}
// Fetch the upper identifier triplet, padding as needed.
let up: number;
let uc: number;
let us: number;
if (i >= upperCount) {
up = upperCount === 0 ? MAX_PATH + 1 : 0;
uc = 0;
us = 0;
} else {
up = Private.idPathAt(upper, i);
uc = Private.idVersionAt(upper, i);
us = Private.idStoreAt(upper, i);
}
// If the triplets are the same, copy the triplet and continue.
if (lp === up && lc === uc && ls === us) {
id += Private.createTriplet(lp, lc, ls);
continue;
}
// If the triplets are different, the well-ordered identifiers
// assumption means that the lower triplet compares less than
// the upper triplet. The task now is to find the nearest free
// path slot among the remaining triplets.
// If there is free space between the path portions of the
// triplets, select a new path which falls between them.
if (up - lp > 1) {
let np = Private.randomPath(lp + 1, up - 1);
id += Private.createTriplet(np, version, store);
return id.slice();
}
// Otherwise, copy the left triplet and reset the upper count
// to zero so that the loop chooses the nearest available path
// slot after the current lower triplet.
id += Private.createTriplet(lp, lc, ls);
upperCount = 0;
}
// If this point is reached, the lower and upper identifiers share
// the same path but diverge based on the version or store id. It is
// safe to insert anywhere in an extra triplet.
let np = Private.randomPath(1, MAX_PATH);
id += Private.createTriplet(np, version, store);
return id.slice();
}
export
function createTriplexIds(n: number, version: number, store: number, lower: string, upper: string): string[] {
let ids: string[] = [];
while (ids.length < n) {
let id = createTriplexId(version, store, lower, upper);
ids.push(id);
lower = id;
}
return ids;
}
export function encodeBase64(input: string): string {
const buffer = Buffer.from(input);
return buffer.toString('base64');
}
export function decodeBase64(input: string): string {
return Buffer.from(input, 'base64').toString()
}
const HS_L = '\uD800';
const HS_U = '\uDBFF';
const LS_L = '\uDC00';
const LS_U = '\uDFFF';
const LS_REGEX = new RegExp(`([${LS_L}-${LS_U}])`, 'g');
const UNPAIRED_HS_REGEX = new RegExp(
`([${HS_L}-${HS_U}])(?![${LS_L}-${LS_U}])`,
'g',
);
const PAIRED_LS_REGEX = new RegExp(`X${HS_L}([${LS_L}-${LS_U}])`, 'g');
const PAIRED_HS_REGEX = new RegExp(`([${HS_L}-${HS_U}])${LS_L}X`, 'g');
export
function stripSurrogates(id: string): string {
return id.replace(PAIRED_LS_REGEX, '$1').replace(PAIRED_HS_REGEX, '$1');
}
export
function generateIdString(str: string): string {
str = str.replace(LS_REGEX, `X${HS_L}$1`);
str = str.replace(UNPAIRED_HS_REGEX, `$1${LS_L}X`);
return str;
}
export
function stringToCharCodes(s: string): number[] {
result = new Array<number>();
for (i=0; i<s.length; i++) {
result.push(s.charCodeAt(i))
}
return result
}
ids = createTriplexIds(2**10,1,1)
timesA = ids.map(item => {
return timeit(100, encodeBase64, [item])
})
meanA = d3array.mean(timesA)
timesB = ids.map(item => {
return timeit(100, generateIdString, [item])
})
meanB = d3array.mean(timesB)
meanB/meanA
patchIds = createTriplexIds(2**13, 1, 1, ids[0], ids[1])