TypeScript library for optimized data structures (prefabs).
First, edit existing or create new .npmrc file in your project root, and add:
@zimmed:registry=https://npm.pkg.github.com
Then you can use:
$ npm i --save @zimmed/prefab
Nope! You can import into any ES6 project using the same import syntax listed below, into Node.js using const { LinkedList } = require('@zimmed/prefab'), or directly into a modern browser environment using <script src="prefab.umd.js" /><script>const list = new prefab.LinkedList();</script>. If you want ES5 backward compatibility, you will need to bundle this library with your own transpilation process (see babel).
There are many JavaScript examples and libraries for various datastructures, but very few with full typing support, and even fewer that are optimized for raw performance. These prefabs take advantage of the highly-optimized ES5+ builtins, like Set and Map and extend their behavior to be
a bit more versatile, as in the case of the LinkedSet, which sparked this library because I wanted the performance advantages of the JavaScript Set object, but needed to be able to pop elements from it (which the Set does not do natively).
If you still need convincing, perhaps the performance benchmarks that will be published with the upcoming 0.2.0 release will help clarify. In preliminary tests on Node.js 16.4, the LinkedSet maintained overall Set performance, while DRASTICALLY (to the tune of 60x) outperformed even the native Array on unshift and shift operations, thanks to the doubly-LinkedList.
Report any bugs you come across on the issues page, or suggest enhancements.
Not a question, but I completely agree. Object composition is a much better pattern. That said, because TypeScript is geared more towards the traditional (read: wrong) OOP opproach, it works much better for these kinds of libraries when you have a lot of generic types to use a hierarchical approach. It also makes the code very familiar for a larger set of developers.
I considered adding parallel factory patterns instead of instance-based structures, but this library is really about performance, which is optimized very well on any modern JavaScript engine for class instantiation, and switching to a more robust and testable stateless factory pattern would hurt that peformance. I may still do this anyway at some point, but it's not a priority.
LinkedList
┃
┣━ SizedLinkedList
┃ ┻━ Queue [Future]
┃
┣━ LinkedSet
┃ ┃
┃ ╋━ UniQueue [Future]
┃ ┃
┃ ╋━ SortedSet [Future]
┃ ╹ ┻━ PriorityQueue [Future]
┃
┣━ LinkedCollection
┃ ┃
╹ ┻━ SortedCollection [Future]
ObjectPool < LinkedList
For all your linked-list needs!
import { LinkedList } from '@zimmed/prefab';
const foo = new LinkedList<string>()
.add('green')
.add('eggs')
.add('and')
.cycle()
.add('spam')
.cycle()
.join(' '); // -> "spam and green eggs"
const bar = LinkedList.from('green eggs and spam'.split(' ')); // -> LinkedList { 'green' 'eggs' 'and' 'spam' }
for (const s of bar) {
// ... iteration
}(extends LinkedList)
A very slight extension to the LinkedList prefab that tracks the size of the list.
import { SizedLinkedList as LinkedList } from '@zimmed/prefab';
const baz = LinkedList.from('green eggs and spam'.split(' ')).size; // -> 4(extends LinkedList)
Combines the optimized functionality of the builtin Set, with the versatility of a linked list: Best of both worlds! Blazing fast unique list operations and lookups while supporting additional functionality that the native Set does not support, such as insert, pop, shift, and more.
import { LinkedSet } from '@zimmed/prefab';
const set = new LinkedSet(['one', 'two', 'three', 'two', 'four', 'one']); // -> LinkedSet { 'one' 'two' 'three' 'four' }
set.add('five');
set.size; // -> 5
const obj = set.reduce(
(
accum,
key,
idx /** Note: 2nd param to callbacks is INDEX not the redundant key as it is in the builtin Set **/
) => ({
...accum,
[key]: idx,
}),
{} as { [k: string]: number }
);
const five = set.pop(); // -> 'five'
set.size; // -> 4(extends LinkedList)
Similar to the LinkedSet, but uses primary key lookups and identifiers, and requires items to be objects. Useful for keeping key -> value records with constant lookups, as well as linked list iterations.
import { LinkedCollection } from '@zimmed/prefab';
class Item {
constructor(
public readonly id: string,
public data?: any,
public readonly cat: string = 'default'
) {}
}
const collection = new LinkedCollection('id', [
new Item('one'),
new Item('two'),
new Item('three'),
new Item('two'),
]); // -> LinkedCollection { Item('one'), Item('two'), Item('three') }
collection.add(new Item('four'));
collection.size; // -> 4
for (const item of collection) {
// same as collection.values()
// -> Item('one'), Item('two'), Item('three'), ...
}
for (const key of collection.keys()) {
// -> 'one', 'two', 'three', ...
}
for (const [key, item] of collection.entries()) {
// -> ['one', Item('one')], ...
}
// Respects same Set methods
const four = collection.pop(); // -> Item('four')
collection.size; // -> 4
// Introduces expected Map method and changes signatures to be key lookups instead of item lookups
collection.select('two'); // -> Item('two')
collection.has('one'); // -> true
collection.delete('three'); // -> true
// Upserting / Uppending
// Safely update existing item or add/insert new one
collection.uppend(new Item('seven')); // -> same as collection.add or collection.append
collection.uppend(new Item('seven', { foo: 'bar' })); // -> replaces existing Item('seven') with new Item('seven', { foo: 'bar' }) maintaining link position
collection.upsert(new Item('zero')); // -> same as collection.insert or collection.unshift
collection.upsert(new Item('zero', 14)); // -> updates existing Item('zero') with new Item('zero', 14) maintaining link position
// Additional groupBy Helper
// Groups items into arrays based on provided key
new LinkedCollection('id', [
new Item('one'),
new Item('two'),
new Item('three', undefined, 'special'),
]).groupBy('cat'); // -> { default: [Item('one'), Item('two')], special: [Item('three')] }
// if key is the collection identifier key, returns a key->value object
new LinkedCollection('id', [new Item('one'), new Item('two')]).groupBy('id'); // -> { one: Item('one'), two: Item('two') }(uses LinkedList)
A pooled object manager for consistent memory signatures.
import { ObjectPool } from '@zimmed/prefab';
let counter = 0;
export class MyEntity extends ObjectPool.Object {
id = 'entity:my';
uid = ++counter;
location = [-1, -1];
health = 0;
name = 'unnamed';
get alive() {
return this.health > 0;
}
distance([x, y]: [number, number]) {
return Math.sqrt((x - this.location[0]) ** 2 + (y - this.location[1]) ** 2);
}
onInit(name: string, x: number, y: number, health = 100) {
this.name = name;
this.health = health;
this.location[0] = x;
this.location[1] = y;
}
// Be sure to free up any references that are no longer needed so they can be garbage collected.
onClean() {
this.health = 0;
this.location[0] = -1;
this.location[1] = -1;
}
}
const entityPool = ObjectPool.create(MyEntity, 1000); // pre-allocates 1000 entities
entityPool.alloc(1000); // allocates 1000 more entities
entityPool.size; // -> 2000
// Take and initialize objects for use from pool
const dude = entityPool.spawn('Dude', 4, 5);
const body = entityPool.spawn('Dead Guy', 3, 3, 0);
Array(1998)
.fill(0)
.map(() => entityPool.spawn('Used Entity', 100, 100)); // Use up entire pool
let newEntity = entityPool.spawn('Another entity', 1, 1); // No entity created! Returns undefined when all objects used up.
newEntity = entityPool.forceSpawn('Another entity', 1, 1); // Entity created! Forces a creation when no objects available and increases the max size of the pool.
entityPool.size; // -> 2001
entityPool.realloc(1000); // No change to pool
// entityPool.reallocUnsafe(1000);
// This will release all entities over the new maximum, keeping the most recently allocated first.
// This would break the game loop, as `dude` and `body` would all be cleaned and orphaned objects.
// The same can also be achieved with `entityPool.dealloc(1001);`
// Alternatively, `entityPool.clear()` will free all pooled objects.
entityPool.realloc(1e6); // Set pool size to 1,000,000 (keeps existing entities)
function gameLoop(player) {
if (body.distance(player.location) === 0) {
entityPool.free(body); // Frees object back into pool for re-use later
console.log(body.location); // -> [-1, -1];
}
}(coming soon...)