Tinkering with code and algorithms for fun
Unlisted
Edited
Oct 3, 2023
Importers
1 star
{
const cArray = CircularArray.from([-3, -2, -1]);
for (let i = 0; i < 64; i++) {
cArray.push(i);
cArray.shift();
}
return {
cArray,
array: [...cArray] // convert to plain array
};
}
Circular = ({
Array: CircularArray,
F64: CircularF64,
F32: CircularF32,
I32: CircularI32,
U32: CircularU32,
I16: CircularI16,
U16: CircularU16,
I8: CircularI8,
U8: CircularU8,
U8c: CircularU8c
})
new CircularArray(...[10, 2, 3])
// The TypedArray versions of CircularArray are
// pretty much the same as the above bit of code,
// but without value kind tests (because TypedArray)
// and no Array.push calls (also because TypedArray).
// Since the code is identical for all of them except
// for the particular TypedArray constructor being used,
// we use a function to generate the prototypes.
function makeCircularPrototype(arrayConstructor, name) {
// Using a computed property lets us give a custom name
// to a generated prototype.
const { [name]: circularTA } = {
[name]: function (length, capacity) {
if (length === undefined) length = 0;
if (!Number.isInteger(length) || length < 0) throw new Error("length must be a positive integer");
// Force capacity to a power of two, because using bitmasks for modulo is faster
if (capacity === undefined) capacity = Math.max(16, 2 ** Math.ceil(Math.log2(length + 1)));
else capacity = 2 ** (Math.ceil(Math.log2(capacity)));
if (!Number.isInteger(capacity) || capacity < length) throw new Error("Initial capacity must be a positive integer equal or greater to length");
const data = new arrayConstructor(capacity);
this.data = data;
this.length = length;
this.offset = 0;
}
};
circularTA.from = function (array) {
const cta = new circularTA(array.length);
for (let i = 0; i < array.length; i++) {
cta.data[i] = array[i];
}
return cta;
};
Object.assign(circularTA.prototype, {
push(...args) {
if (args.length === 0) args = [0];
this.maybeGrow(args.length);
let { length } = this;
const mod = this.data.length - 1;
for (const val of args) {
this.data[(this.offset + length++) & mod] = val;
}
return (this.length += args.length);
},
unshift(...args) {
if (args.length === 0) args = [0];
this.maybeGrow(args.length);
const offset = this.offset + this.data.length - args.length;
this.offset = offset;
const mod = this.data.length - 1;
for (let i = 0, { data } = this; i < args.length; i++) {
data[(i + offset) & mod] = args[i];
}
return (this.length += args.length);
},
pop() {
if (this.length > 0) {
const idx = (this.offset + --this.length) & (this.data.length - 1);
const val = this.data[idx];
this.maybeShrink();
return val;
}
},
shift() {
if (this.length > 0) {
const val = this.data[this.offset];
this.offset = (this.offset + 1) & (this.data.length - 1);
this.length--;
this.maybeShrink();
return val;
}
},
slice(begin = 0, end = this.length) {
begin = Math.max(begin | 0, 0);
end = Math.min(end | 0, this.length);
const ret = [];
const { offset, data } = this;
const mod = data.length - 1;
for (let i = begin; i < end; i++) {
ret.push(data[(i + offset) & mod]);
}
return circularTA.from(ret);
},
// copy a typed array from the data
sliceTA(begin = 0, end = this.length) {
begin = Math.max(begin | 0, 0);
end = Math.min(end | 0, this.length);
const ret = [];
const { offset, data } = this;
const mod = data.length - 1;
for (let i = begin; i < end; i++) {
ret.push(data[(i + offset) & mod]);
}
return arrayConstructor.from(ret);
},
map(callback) {
const ret = [];
const { offset, length, data } = this;
const mod = data.length - 1;
for (let i = 0; i < length; i++) {
ret.push(callback(data[(i + offset) & mod], i));
}
return circularTA.from(ret);
},
filter(callback) {
const ret = [];
const { offset, length, data } = this;
const mod = data.length - 1;
for (let i = 0; i < length; i++) {
const val = data[(i + offset) & mod];
if (callback(val, i)) ret.push(val);
}
return circularTA.from(ret);
},
mapFilter(
callback,
begin = 0,
end = this.length
) {
const ret = [];
const { offset, data } = this;
const mod = data.length - 1;
const SKIP = Symbol("mapFilter.SKIP");
for (let i = begin; i < end; i++) {
const v = callback(SKIP, data[(i + offset) & mod], i);
if (v !== SKIP) ret.push(/** @type {R} */ v);
}
return circularTA.from(ret);
},
maybeGrow(newLength) {
if (newLength + this.length > this.data.length) {
const { data, length, offset } = this;
const nData = new arrayConstructor(data.length * 2);
const mod = data.length - 1;
for (let i = 0; i < length; i++) {
nData[i] = data[(i + offset) & mod];
}
this.data = nData;
this.offset = 0;
}
},
maybeShrink() {
const capacity = this.data.length;
if (this.length < (3 * capacity) / 8 && capacity > 16) {
const { data, length, offset } = this;
const nData = new arrayConstructor(capacity >> 1);
const mod = capacity - 1;
for (let i = 0; i < length; i++) {
nData[i] = data[(i + offset) & mod];
}
this.data = nData;
this.offset = 0;
}
},
[Symbol.iterator]: function* () {
const { data, length, offset } = this;
const mod = data.length - 1;
for (let i = 0; i < length; i++) {
yield data[(i + offset) & mod];
}
}
});
return circularTA;
}
CircularF64 = makeCircularPrototype(Float64Array, "CircularF64")
CircularF32 = makeCircularPrototype(Float32Array, "CircularF32")
class CircularArray {
constructor(...args) {
// TODO: switch to constructor(length, <valKind constructor>) instantiation method
// TODO: clean up + don't skip holey arrays in push/unshift
const capacity = Math.max(16, 2 ** Math.ceil(Math.log2(args.length + 1)));
// assume all elements are of the same type as the first argument
// See also: https://v8.dev/blog/elements-kinds
const valKind = args.length > 0 ? args[0] : 0;
const data = [valKind];
let i = 1;
// fill up array with initial values
while (i < args.length) data.push(args[i++]);
// fill remaining capacity with same type of element as first value
while (i++ < capacity) {
data.push(valKind);
}
// Note: we don't bother storing the capacity,
// as it will be equivalent to data.length
this.data = data;
this.length = args.length;
this.offset = 0;
this.autoshrink = true;
}
static from(array) {
return new this(...array);
}
push(...args) {
if (args.length === 0) return 0;
this.maybeGrow(args.length);
let i = this.offset + this.length;
const mod = this.data.length - 1;
// TODO: let version to not skip holes in the array
for (const val of args) {
this.data[i++ & mod] = val;
}
return (this.length += args.length);
}
unshift(...args) {
if (args.length === 0) return 0;
this.maybeGrow(args.length);
const mod = this.data.length - 1;
const offset = (this.offset - args.length + this.data.length) & mod;
this.offset = offset;
for (let i = offset; i < args.length + offset; i++) {
this.data[i & mod] = args[i];
}
return (this.length += args.length);
}
pop() {
if (this.length > 0) {
// Note: we're not overwriting the removed element, so this
// is NOT a secure implementation of a circular buffer!
// 1. we need the last element of the buffer (so length-1),
// *and* we need to shrink the length by one because
// we're removing that element. So we might as well
// do --this.length to inline that operation.
// 2. capacity is always a power of two, so instead of using
// modulo we can us a bitmask: by subtracting one from
// the capacity (data.length) we get a 0b111... mask.
const idx = (--this.length + this.offset) & (this.data.length - 1);
const val = this.data[idx];
if (this.autoshrink) this.maybeShrink();
return val;
}
}
shift() {
if (this.length > 0) {
// Note: we're not overwriting the removed element, so this
// is NOT a secure implementation of a circular buffer!
// We have to:
// - return the first element of the buffer (so this.offset)
// - "remove" it from the buffer by:
// - increasing the offset by one
// - decreasing the length by one
const val = this.data[this.offset];
this.offset = (this.offset + 1) & (this.data.length - 1);
this.length--;
if (this.autoshrink) this.maybeShrink();
return val;
}
}
slice(begin = 0, end = this.length) {
begin = Math.max(begin | 0, 0);
end = Math.min(end | 0, this.length);
if (begin >= end) return new CircularArray();
const ret = [];
const { offset, data } = this;
const mod = data.length - 1;
for (let i = begin; i < end; i++) {
ret.push(data[(i + offset) & mod]);
}
return CircularArray.from(ret);
}
map(callback) {
const ret = [];
const { offset, length, data } = this;
const mod = data.length - 1;
for (let i = 0; i < length; i++) {
ret.push(callback(data[(i + offset) & mod], i, this));
}
return CircularArray.from(ret);
}
filter(callback) {
const ret = [];
const { offset, length, data } = this;
const mod = data.length - 1;
for (let i = 0; i < length; i++) {
const val = data[(i + offset) & mod];
if (callback(val, i, this)) ret.push(val);
}
return CircularArray.from(ret);
}
/**
* Convenience function to replace chained calls to `.map`,
* `.filter` and `.slice`, avoiding the allocation of
* intermediate arrays that are immediately discarded.
*
* The `callback` is passed a `SKIP` symbol as its first
* argument. To filter out an element, return this SKIP
* symbol. Example:
*
* ```js
* // extract `obj.value` from a given section of a circular
* // array, but filter out undefined entries of `obj`.
* const callback = (SKIP, obj) => obj ? obj.value : SKIP;
* const values = cArray.mapFilter(array, callback, begin, end);
* ```
*/
mapFilter(callback, begin = 0, end = this.length) {
const ret = [];
const { offset, data } = this;
const mod = data.length - 1;
const SKIP = Symbol("mapFilter.SKIP");
for (let i = begin; i < end; i++) {
const v = callback(SKIP, data[(i + offset) & mod], i);
if (v !== SKIP) ret.push(v);
}
return CircularArray.from(ret);
}
maybeGrow(addedLength) {
if (addedLength + this.length > this.data.length) {
// We have to grow our backing array to be able to
// hold more data. We double its size whenever
// it is filled to capacity.
let { data, length, offset } = this;
const capacity = data.length;
const valKind = data[offset];
for (let i = 0; i < offset; i++) {
data.push(valKind);
}
for (let i = offset; i < capacity; i++) {
data.push(data[i]);
}
offset += capacity;
}
}
maybeShrink() {
// We wish to shrink the backing array if the buffer gets too small,
// but we also want to avoid the situation where a poorly timed
// alternating push/pop will trigger constant re-allocation of
// the backing array. So instead of shrinking the array at
// half capacity (mimicking the doubling of growing
// the backing array in push) we shrink at 3/8 capacity, but shrink
// capacity in half. This results in the new buffer being 3/4
// full, reducing the odds of this disastrous re-allocation,
// while maintaining the fast bitmasked modulo behavior.
if (this.length < (this.data.length * 0.375 && this.data.length > 16)) {
const { data, length, offset } = this;
const valKind = data[offset];
const nData = [valKind];
const mod = data.length - 1;
for (let i = 1; i < length; i++) {
nData.push(data[(i + offset) & mod]);
}
for (let i = length; i < data.length >> 1; i++) {
nData.push(valKind);
}
this.data = nData;
this.offset = 0;
}
}
*[Symbol.iterator]() {
const { data, length, offset } = this;
const mod = data.length - 1;
for (let i = 0; i < length; i++) {
yield data[(i + offset) & mod];
}
}
}
CircularI32 = makeCircularPrototype(Int32Array, "CircularI32")
CircularU32 = makeCircularPrototype(Uint32Array, "CircularU32")
CircularI16 = makeCircularPrototype(Int16Array, "CircularI16")
CircularU16 = makeCircularPrototype(Uint16Array, "CircularU16")
CircularI8 = makeCircularPrototype(Int8Array, "CircularI8")
CircularU8 = makeCircularPrototype(Uint8Array, "CircularU8")
CircularU8c = makeCircularPrototype(Uint8ClampedArray, "CircularU8c")
({[Symbol.toStringTag]: 'foo'}).toString()
{
const bytes = new Uint8Array(83086);
for (let i = 0; i < bytes.length; i++) { bytes[i] = Math.random() * 256 | 0;}
return CircularU8.from(bytes)
}
{
const t = CircularArray.from([4, 5, 6]);
for (let i = 0; i < 16; i++) {
t.push(i);
}
return { t, array: [...t] };
}
{
const t = new CircularArray(4, 5, 6);
for (let i = 0; i < 63; i++) {
t.shift();
t.push(i);
}
return { t, splat: [...t] };
}
{
const t = new CircularArray(4, 5, 6);
for (let i = 0; i < 64; i++) {
t.unshift(i);
}
return t;
}
{
const t = new CircularArray(4, 5, 6);
for (let i = 0; i < 32; i++) {
t.push(i);
t.push(i);
t.unshift(-i);
t.unshift(-i);
t.shift();
t.pop();
}
return { t, splat: [...t] };
}
{
const t = new CircularArray(4, 5, 6);
for (let i = 0; i < 1024; i++) {
t.push(i);
}
for (let i = 0; i < 1024; i++) {
t.shift();
}
return { t, splat: [...t] };
}
{
const t = new CircularArray(-3, -2, -1);
for (let i = 0; i < 1024; i++) {
t.push(i);
}
const t2 = t.filter((v) => v & 1);
const t3 = t2.map((v) => v / 2);
const t4 = t3.slice(10, 20);
return { t, t2, t3, t4 };
}
{
const t = new CircularF64(4, 5, 6);
for (let i = 0; i < 1024; i++) {
t.push(i / 3);
}
for (let i = 0; i < 1024; i++) {
t.shift();
}
return { t, splat: [...t] };
}
{
const t = new CircularF32(4, 5, 6);
for (let i = 0; i < 1024; i++) {
t.push(i / 3);
}
for (let i = 0; i < 1024; i++) {
t.shift();
}
return { t, splat: [...t] };
}
{
const t = new CircularU8(4);
for (let i = 0; i < 1024; i++) {
t.push(i);
}
for (let i = 0; i < 1024; i++) {
t.shift();
}
return { t, splat: [...t] };
}
{
const t = new CircularU8c(4);
for (let i = 0; i < 1024; i++) {
t.push(i);
}
for (let i = 0; i < 1024; i++) {
t.shift();
}
return { t, splat: [...t] };
}
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
