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] };
}
One platform to build and deploy the best data apps
Experiment and prototype by building visualizations in live JavaScript notebooks. Collaborate with your team and decide which concepts to build out.
Use Observable Framework to build data apps locally. Use data loaders to build in any language or library, including Python, SQL, and R.
Seamlessly deploy to Observable. Test before you ship, use automatic deploy-on-commit, and ensure your projects are always up-to-date.