structurae

Structurae

A collection of data structures for high-performance JavaScript applications that includes:

• Binary Protocol - simple binary protocol based on DataView and defined with JSONSchema
• Bit Structures:
  • BitField & BigBitField - stores and operates on data in Numbers and BigInts treating them as bitfields.
  • BitArray - an array of bits implemented with Uint32Array.
  • Pool - manages availability of objects in object pools.
  • RankedBitArray - extends BitArray with O(1) time rank and O(logN) select methods.
• Graphs:
  • Adjacency Structures - implement adjacency list & matrix data structures.
  • Graph - extends an adjacency list/matrix structure and provides methods for traversal (BFS, DFS), pathfinding (Dijkstra, Bellman-Ford), spanning tree construction (BFS, Prim), etc.
• Grids:
  • BinaryGrid - creates a grid or 2D matrix of bits.
  • Grid - extends built-in indexed collections to handle 2 dimensional data (e.g. nested arrays).
  • SymmetricGrid - a grid to handle symmetric or triangular matrices using half the space required for a normal grid.
• Sorted Structures:
  • BinaryHeap - extends Array to implement the Binary Heap data structure.
  • SortedArray - extends Array to handle sorted data.

Usage

Node.js:

npm i structurae

import {...} from "structurae";

Deno:

import {...} from "https://deno.land/x/structurae/index.ts"

Documentation

• Articles:
  • Structurae: Data Structures for Heigh-Performance JavaScript
  • Structurae 1.0: Graphs, Strings, and WebAssembly
  • Binary Protocol for JavaScript

Overview

Binary Protocol

Binary data in JavaScript is represented by ArrayBuffer and accessed through TypedArrays and DataView. However, both of those interfaces are limited to working with numbers. Structurae offers a set of classes that extend the DataView interface to support using ArrayBuffers for strings, objects, and arrays. These classes ("views") form the basis for a simple binary protocol with the following features:

• smaller and faster than schema-less binary formats (e.g. BSON, MessagePack);
• supports zero-copy operations, e.g. reading and changing object fields without decoding the whole object;
• supports static typing through TypeScript;
• uses JSON Schema for schema definitions;
• does not require compilation unlike most other schema-based formats (e.g. FlatBuffers).

The protocol is operated through the View class that handles creation and caching of necessary structures for a given JSON Schema as well as simplifying serialization of tagged objects.

…

Objects and Maps

Objects by default are treated as C-like structs, the data is laid out sequentially with fixed sizes, all standard JavaScript values are supported, inluding other objects and arrays of fixed size:

…

Objects that support optional fields and fields of variable size ("maps") should additionally specify btype map and list non-optional (fixed sized) fields as required:

…

The size and layout of each map instance is calculated upon creation and stored within the instance (unlike fixed sized objects, where each instance have the same size and layout). Maps are useful for densely packing objects and arrays whose size my vary greatly. There is a limitation, though, since ArrayBuffers cannot be resized, optional fields that were absent upon creation of a map view cannot be set later, and those set cannot be resized, that is, assigned a value that is greater than their current size.

For performance sake, all variable size views are encoded using single global ArrayBuffer that is 8192 bytes long, if you expect to handle bigger views, supply a bigger DataView when instantiating a view protocol:

import { View } from "structurae";

// instantiate a view protocol
const view = new View(new DataView(new ArrayBuffer(65536)));

There are certain requirements for a JSON Schema used for fixed sized objects:

• Each object should have a unique id defined with $id field. Upon initialization, the view class is stored in View.Views and accessed with the id used as the key. References made with $ref are also resolved against the id.
• For fixed sized objects, sizes of strings and arrays should be defined using maxLength and maxItems properties respectfully.
• $ref can be used to reference objects by their $id. The referenced object should be defined either in the same schema or in a schema initialized previously.
• Type number by default resolves to float64 and type integer to int32, you can use any other type by specifying it in btype property.

Objects and maps support setting default values of required fields. Default values are applied upon creation of a view:

interface House {
  size: number;
}
const House = view.create({
  $id: "House",
  type: "object",
  properties: {
    size: { type: "integer", btype: "uint32", default: 100 },
  },
});
const house = House.from({} as House);
house.get("size"); //=> 100

Default values of an object can be overridden when it is nested inside another object:

interface Neighborhood {
  house: House;
  biggerHouse: House;
}
const Neighborhood = view.create({
  $id: "Neighborhood",
  type: "object",
  properties: {
    house: { $ref: "#House" },
    biggerHouse: { $ref: "#House", default: { size: 200 } },
  },
});
const neighborhood = Neighborhood.from({} as Neighborhood);
neighborhood.get("house"); //=> { size: 100 }
neighborhood.get("biggerHouse"); //=> { size: 200 }

Dictionaries

Objects and maps described above assume that all properties of encoded objects are known and defined beforehand, however, if the properties are not known, and we are dealing with an object used as a lookup table (also called map, hash map, or records in TypeScript) with varying amount of properties and known type of values, we can use a dictionary view:

…

Arrays and Vectors

The protocol supports arrays of non-nullable fixed sized values (numbers, strings of fixed maximum size, objects) and vectors--arrays with nullable or variable sized values. The type of items held by both "container" views is defined in items field of the schema.

const Street = view.create>({
  type: "array",
  items: {
    type: "object",
    // we can also reference previously created class with $ref
    $ref: "#House",
  },
});
const street = Street.from([{ size: 10 }, { size: 20 }]);
street.byteLength; //=> 8
street.get(0); //=> { size: 10 }
street.getView(0).get("size"); //=> 10
street.size; //=> 2
street.set(0, { size: 100 });
street.get(0); //=> { size: 100 }

For vectors set btype to vector:

const Names = view.create>({
  type: "array",
  btype: "vector",
  items: {
    type: "string",
  },
});
const witches = Names.from([
  "Granny Weatherwax",
  "Nanny Ogg",
  undefined,
  "Magrat Garlick",
]);
witches.byteLength; //=> 64
witches.get(0); //=> "Granny Weatherwax"
witches.get(2); //=> undefined

As with maps, the layout of vectors is calculated upon creation and editing is limited to the items present upon creation.

Strings

The protocol handles strings through StringView, an extension of DataView that handles string serialization. It also offers a handful of convenience methods to operate on encoded strings so that some common operations can be performed without decoding the string:

…

Tagged Objects

When transferring our buffers encoded with views we can often rely on meta information to know what kind of view to use in order to decode a received buffer. However, sometimes we might want our views to carry that information within themselves. To do that, we can prepend or tag each view with a value indicating its class, i.e. add a field that defaults to a certain value for each view class. Now upon receiving a buffer we can read that field using the DataView and convert it into an appropriate view.

The View class offers a few convenience methods to simplify this process:

…

Extending View Types

The view protocol is designed with extensibility in mind. While built-in view types are ample for most cases, creating a special type can reduce boilerplate in certain situations. You can check out a full example of creating and using a custom view type for BitArray in examples/bit-array-view.

To create a new view type, first create a class extending DataView and implementing one of the view type interfaces, for example PrimitiveView:

export class BitArrayView extends DataView implements PrimitiveView {
  ...
}

To let TypeScript know about our new type, we use module augmentation to add our new type name to ViewSchemaTypeMap interface:

declare module "structurae" {
  interface ViewSchemaTypeMap {
    bitarray: "string";
  }
}

This way, it will be a binary subtype (or btype) of JSONSchema type string.

And finally, we add the new class to the list of views used by our protocol instance:

const protocol = new View();
protocol.Views.set("bitarray", BitArrayView);

Now we can use the new type in our schemas, for example:

class UserSettings {
  id = 0;
  settings = new BitArray(3);
}

const UserSettingsView = protocol.create({
  $id: "UserSettings",
  type: "object",
  properties: {
    id: { type: "integer" },
    settings: {
      type: "string",
      btype: "bitarray",
      maxLength: 12,
    },
  },
}, UserSettings);

Bit Structures

BitField & BigBitField

BitField and BigBitField use JavaScript Numbers and BigInts respectively as bitfields to store and operate on data using bitwise operations. By default, BitField operates on 31 bit long bitfield where bits are indexed from least significant to most:

import { BitField } from "structurae";

const bitfield = new BitField(29); // 29 === 0b11101
bitfield.get(0); //=> 1
bitfield.get(1); //=> 0
bitfield.has(2, 3, 4); //=> true

You can use BitFieldMixin or BigBitFieldMixin with your own schema by specifying field names and their respective sizes in bits:

const Field = BitFieldMixin({ width: 8, height: 8 });
const field = new Field({ width: 100, height: 200 });
field.get("width"); //=> 100;
field.get("height"); //=> 200
field.set("width", 18);
field.get("width"); //=> 18
field.toObject(); //=> { width: 18, height: 200 }

If the total size of your fields exceeds 31 bits, use BigBitFieldMixin that internally uses a BigInt to represent the resulting number, however, you can still use normal numbers to set each field and get their value as a number as well:

const LargeField = BitFieldMixin({ width: 20, height: 20 });
const largeField = new LargeField([1048576, 1048576]);
largeField.value; //=> 1099512676352n
largeField.set("width", 1000).get("width"); //=> 1000

If you have to add more fields to your schema later on, you do not have to re-encode your existing values, just add new fields at the end of your new schema:

const OldField = BitFieldMixin({ width: 8, height: 8 });
const oldField = OldField.encode([20, 1]);
//=> oldField === 276

const NewField = BitFieldMixin({ width: 8, height: 8, area: 10 });
c