Structurae

Data structures for high-performance JavaScript applications.

README

Structurae

Actions Status npm

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

- Binary Protocol - simple binary protocol based on
  DataView and defined with JSONSchema
  - 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.
  - 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.
  - 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.
  - BinaryHeap - extends Array to implement the Binary Heap data
    structure.
  - SortedArray - extends Array to handle sorted data.

Usage


Node.js:

  1. ```
  2. npm i structurae
  3. ```

  1. ```
  2. import {...} from "structurae";
  3. ```

Deno:

  1. ```
  2. import {...} from "https://deno.land/x/structurae@4.0.0/index.ts"
  3. ```

Documentation


- Articles:
  - [Structurae: Data Structures for Heigh-Performance
    JavaScript](https://blog.usejournal.com/structurae-data-structures-for-high-performance-javascript-9b7da4c73f8)
  - [Structurae 1.0: Graphs, Strings, and
    WebAssembly](https://medium.com/@zandaqo/structurae-1-0-graphs-strings-and-webassembly-25dd964d5a70)

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.

  1. ```typescript
  2. import { View } from "structurae";

  3. // instantiate a view protocol
  4. const view = new View();

  5. // define interface for out animal objects
  6. interface Animal {
  7.   name: string;
  8.   age: number;
  9. }
  10. // create and return a view class (extension of DataView) that handles our Animal objects
  11. const AnimalView = view.create<Animal>({
  12.   $id: "Pet",
  13.   type: "object",
  14.   properties: {
  15.     name: { type: "string", maxLength: 10 },
  16.     // by default, type `number` is treated as int32, but can be further specified usin `btype`
  17.     age: { type: "number", btype: "uint8" },
  18.   },
  19. });
  20. // encode our animal object
  21. const animal = AnimalView.from({ name: "Gaspode", age: 10 });
  22. animal instanceof DataView; //=> true
  23. animal.byteLength; //=> 14
  24. animal.get("age"); //=> 10
  25. animal.set("age", 20);
  26. animal.toJSON(); //=> { name: "Gaspode", age: 20 }
  27. ```

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:

  1. ```typescript
  2. interface Friend {
  3.   name: string;
  4. }
  5. interface Person {
  6.   name: string;
  7.   fullName: Array<string>;
  8.   bestFriend: Friend;
  9.   friends: Array<Friend>;
  10. }
  11. const PersonView = view.create<Person>({
  12.   // each object requires a unique id
  13.   $id: "Person",
  14.   type: "object",
  15.   properties: {
  16.     // the size of a string field is required and defined by maxLength
  17.     name: { type: "string", maxLength: 10 },
  18.     fullName: {
  19.       type: "array",
  20.       // the size of an array is required and defined by maxItems
  21.       maxItems: 2,
  22.       // all items have to be the same type
  23.       items: { type: "string", maxLength: 20 },
  24.     },
  25.     // objects can be referenced with $ref using their $id
  26.     bestFriend: { $ref: "#Friend" },
  27.     friends: {
  28.       type: "array",
  29.       maxItems: 3,
  30.       items: {
  31.         $id: "Friend",
  32.         type: "object",
  33.         properties: {
  34.           name: { type: "string", maxLength: 20 },
  35.         },
  36.       },
  37.     },
  38.   },
  39. });
  40. const person = Person.from({
  41.   name: "Carrot",
  42.   fullName: ["Carrot", "Ironfoundersson"],
  43.   bestFriend: { name: "Sam Vimes" },
  44.   friends: [{ name: "Sam Vimes" }],
  45. });
  46. person.get("name"); //=> Carrot
  47. person.getView("name"); //=> StringView [10]
  48. person.get("fullName"); //=> ["Carrot", "Ironfoundersson"]
  49. person.toJSON();
  50. //=> {
  51. //     name: "Carrot",
  52. //     fullName: ["Carrot", "Ironfoundersson"],
  53. //     bestFriend: { name: "Sam Vimes" },
  54. //     friends: [{ name: "Sam Vimes" }]
  55. //    }
  56. ```

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:

  1. ```typescript
  2. interface Town {
  3.   name: string;
  4.   railstation: boolean;
  5.   clacks?: number;
  6. }
  7. const TownView = view.create<Town>({
  8.     $id: "Town",
  9.     type: "object",
  10.     btype: "map",
  11.     properties: {
  12.       // notice that maxLength is not required for optional fields in maps
  13.       // however, if set, map with truncate longer strings to fit the maxLength
  14.       name: { type: "string" },
  15.       railstation: { type: "boolean" },
  16.       // optional, nullable field
  17.       clacks: { type: "integer" },
  18.     }
  19.     required: ["railstation"],
  20.   });
  21. const lancre = TownView.from({ name: "Lancre", railstation: false });
  22. lancre.get("name") //=> Lancre
  23. lancre.get("clacks") //=> undefined
  24. lancre.byteLength //=> 19
  25. const stoLat = TownView.from({ name: "Sto Lat", railstation: true, clacks: 1 });
  26. stoLat.get("clacks") //=> 1
  27. stoLat.byteLength //=> 24
  28. ```

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:

  1. ```ts
  2. import { View } from "structurae";

  3. // instantiate a view protocol
  4. const view = new View(new DataView(new ArrayBuffer(65536)));
  5. ```

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:

  1. ```typescript
  2. interface House {
  3.   size: number;
  4. }
  5. const House = view.create<House>({
  6.   $id: "House",
  7.   type: "object",
  8.   properties: {
  9.     size: { type: "integer", btype: "uint32", default: 100 },
  10.   },
  11. });
  12. const house = House.from({} as House);
  13. house.get("size"); //=> 100
  14. ```

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

  1. ```typescript
  2. interface Neighborhood {
  3.   house: House;
  4.   biggerHouse: House;
  5. }
  6. const Neighborhood = view.create<Neighborhood>({
  7.   $id: "Neighborhood",
  8.   type: "object",
  9.   properties: {
  10.     house: { $ref: "#House" },
  11.     biggerHouse: { $ref: "#House", default: { size: 200 } },
  12.   },
  13. });
  14. const neighborhood = Neighborhood.from({} as Neighborhood);
  15. neighborhood.get("house"); //=> { size: 100 }
  16. neighborhood.get("biggerHouse"); //=> { size: 200 }
  17. ```

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:

  1. ```typescript
  2. const NumberDict = view.create<Record<number, string | undefined>>({
  3.   $id: "NumberDict",
  4.   type: "object",
  5.   btype: "dict", // dictionaries use btype dict
  6.   // the type of keys are defined in the `propertyNames` field of a schema
  7.   // the keys must be either fixed sized strings or numbers
  8.   propertyNames: { type: "number", btype: "uint8" },
  9.   // the type of values defined in `addtionalProperties` field
  10.   // values can be of any supported type
  11.   additionalProperties: { type: "string" },
  12. });
  13. const dict = NumberDict.from({ 1: "a", 2: "bcd", 3: undefined });
  14. dict.get(1); //=> "a"
  15. dict.get(3); //=> undefined
  16. dict.get(10); //=> undefined
  17. dict.get(2); //=> "bcd"
  18. ```

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.

  1. ```typescript
  2. const Street = view.create<Array<House>>({
  3.   type: "array",
  4.   items: {
  5.     type: "object",
  6.     // we can also reference previously created class with $ref
  7.     $ref: "#House",
  8.   },
  9. });
  10. const street = Street.from([{ size: 10 }, { size: 20 }]);
  11. street.byteLength; //=> 8
  12. street.get(0); //=> { size: 10 }
  13. street.getView(0).get("size"); //=> 10
  14. street.size; //=> 2
  15. street.set(0, { size: 100 });
  16. street.get(0); //=> { size: 100 }
  17. ```

For vectors set btype to vector:

  1. ```typescript
  2. const Names = view.create<Array<string | undefined>>({
  3.   type: "array",
  4.   btype: "vector",
  5.   items: {
  6.     type: "string",
  7.   },
  8. });
  9. const witches = Names.from([
  10.   "Granny Weatherwax",
  11.   "Nanny Ogg",
  12.   undefined,
  13.   "Magrat Garlick",
  14. ]);
  15. witches.byteLength; //=> 64
  16. witches.get(0); //=> "Granny Weatherwax"
  17. witches.get(2); //=> undefined
  18. ```

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:

  1. ``` js
  2. import { StringView } from "structurae";

  3. let stringView = StringView.from("abc😀a");
  4. //=> StringView [ 97, 98, 99, 240, 159, 152, 128, 97 ]
  5. stringView.toString(); //=> "abc😀a"
  6. stringView == "abc😀a"; //=> true

  7. stringView = StringView.from("abc😀");
  8. // length of the view in bytes
  9. stringView.length; //=> 8
  10. // the amount of characters in the string
  11. stringView.size; //=> 4
  12. // get the first character in the string
  13. stringView.charAt(0); //=> "a"
  14. // get the fourth character in the string
  15. stringView.charAt(3); //=> "😀"
  16. // iterate over characters
  17. [...stringView.characters()]; //=> ["a", "b", "c", "😀"]
  18. stringView.substring(0, 4); //=> "abc😀"

  19. stringView = StringView.from("abc😀a");
  20. const searchValue = StringView.from("😀");
  21. stringView.indexOf(searchValue); //=> 3
  22. const replacement = StringView.from("d");
  23. stringView.replace(searchValue, replacement).toString(); //=> "abcda"
  24. stringView.reverse().toString(); //=> "adcba"
  25. ```

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:

  1. ```typescript
  2. import { View } from "structurae";
  3. interface Dog {
  4.   tag: 0;
  5.   name: string;
  6. }
  7. interface Cat {
  8.   tag: 1;
  9.   name: string;
  10. }
  11. const DogView = view.create<Dog>({
  12.   type: "object",
  13.   $id: "Dog",
  14.   properties: {
  15.     // the tag field with default value
  16.     tag: { type: "number", btype: "uint8", default: 0 }
  17.     name: { type: "string", maxLength: 10 }
  18.   },
  19. });
  20. const CatView = view.create<Cat>({
  21.   type: "object",
  22.   $id: "Cat",
  23.   properties: {
  24.     // the tag field with default value
  25.     tag: { type: "number", btype: "uint8", default: 1 }
  26.     name: { type: "string", maxLength: 10 }
  27.   },
  28. });

  29. // now we can encode tagged objects without specifying views first:
  30. const animal = view.encode({ tag: 0, name: "Gaspode" });
  31. // and decode them:
  32. view.decode(animal) //=> { tag: 0, name: "Gaspode" }
  33. ```

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

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

  1. ```ts
  2. export class BitArrayView extends DataView implements PrimitiveView<BitArray> {
  3.   ...
  4. }
  5. ```

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

  1. ```ts
  2. declare module "structurae" {
  3.   interface ViewSchemaTypeMap {
  4.     bitarray: "string";
  5.   }
  6. }
  7. ```

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:

  1. ```ts
  2. const protocol = new View();
  3. protocol.Views.set("bitarray", BitArrayView);
  4. ```

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

  1. ```ts
  2. class UserSettings {
  3.   id = 0;
  4.   settings = new BitArray(3);
  5. }

  6. const UserSettingsView = protocol.create<UserSettings>({
  7.   $id: "UserSettings",
  8.   type: "object",
  9.   properties: {
  10.     id: { type: "integer" },
  11.     settings: {
  12.       type: "string",
  13.       btype: "bitarray",
  14.       maxLength: 12,
  15.     },
  16.   },
  17. }, UserSettings);
  18. ```

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:

  1. ``` js
  2. import { BitField } from "structurae";

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

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

  1. ``` js
  2. const Field = BitFieldMixin({ width: 8, height: 8 });
  3. const field = new Field({ width: 100, height: 200 });
  4. field.get("width"); //=> 100;
  5. field.get("height"); //=> 200
  6. field.set("width", 18);
  7. field.get("width"); //=> 18
  8. field.toObject(); //=> { width: 18, height: 200 }
  9. ```

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:

  1. ``` js
  2. const LargeField = BitFieldMixin({ width: 20, height: 20 });
  3. const largeField = new LargeField([1048576, 1048576]);
  4. largeField.value; //=> 1099512676352n
  5. largeField.set("width", 1000).get("width"); //=> 1000
  6. ```

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:

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

  5. const NewField = BitFieldMixin({ width: 8, height: 8, area: 10 });
  6. const newField = new NewField(oldField);
  7. newField.get("width"); //=> 20
  8. newField.get("height"); //=> 1
  9. newField.set("weight", 100).get("weight"); //=> 100
  10. ```

If you only want to encode or decode a set of field values without creating an
instance, you can do so by using static methods BitField.encode and
BitField.decode respectively:

  1. ``` js
  2. const Field = BitFieldMixin({ width: 7, height: 1 });

  3. Field.encode([20, 1]); //=> 41
  4. Field.encode({ height: 1, width: 20 }); //=> 41
  5. Field.decode(41); //=> { width: 20, height: 1 }
  6. ```

If you don't know beforehand how many bits you need for your field, you can call
BitField.getMinSize with the maximum possible value of your field to find out:

  1. ``` js
  2. BitField.getMinSize(100); //=> 7
  3. const Field = BitFieldMixin({ width: BitField.getMinSize(250), height: 8 });
  4. ```

For performance sake, BitField doesn't check the size of values being set and
setting values that exceed the specified field size will lead to undefined
behavior. If you want to check whether values fit their respective fields, you
can use BitField.isValid:

  1. ``` js
  2. const Field = BitFieldMixin({ width: 7, height: 1 });

  3. Field.isValid({ width: 100 }); //=> true
  4. Field.isValid({ width: 100, height: 3 }); //=> false
  5. ```

BitField#match (and its static variation BitField.match) can be used to
check values of multiple fields at once:

  1. ``` js
  2. const Field = BitFieldMixin({ width: 7, height: 1 });
  3. const field = new Field([20, 1]);
  4. field.match({ width: 20 }); //=> true
  5. field.match({ height: 1, width: 20 }); //=> true
  6. field.match({ height: 1, width: 19 }); //=> false
  7. Field.match(field.valueOf(), { height: 1, width: 20 }); //=> true
  8. ```

If you have to check multiple BitField instances for the same values, create a
special matcher with BitField.getMatcher and use it in the match method, that
way each check will require only one bitwise operation and a comparison:

  1. ``` js
  2. const Field = BitFieldMixin({ width: 7, height: 1 });
  3. const matcher = Field.getMatcher({ height: 1, width: 20 });
  4. Field.match(new Field([20, 1]).valueOf(), matcher); //=> true
  5. Field.match(new Field([19, 1]).valueOf(), matcher); //=> false
  6. ```

BitArray


BitArray uses Uint32Array as an array or vector of bits. It's a simpler version
of BitField that only sets and checks individual bits:

  1. ``` js
  2. const array = new BitArray(10);
  3. array.getBit(0); //=> 0
  4. array.setBit(0).getBit(0); //=> 1
  5. array.size; //=> 10
  6. array.length; //=> 1
  7. ```

BitArray is the base class for
Pool and
It's useful in cases where one needs more bits than can be stored in a number,
but doesn't want to use BigInts as it is done by

Pool


Implements a fast algorithm to manage availability of objects in an object pool
using a BitArray.

  1. ``` js
  2. const { Pool } = require("structurae");

  3. // create a pool of 1600 indexes
  4. const pool = new Pool(100 * 16);

  5. // get the next available index and make it unavailable
  6. pool.get(); //=> 0
  7. pool.get(); //=> 1

  8. // set index available
  9. pool.free(0);
  10. pool.get(); //=> 0
  11. pool.get(); //=> 2
  12. ```

RankedBitArray


RankedBitArray is an extension of BitArray with methods to efficiently calculate
rank and select. The rank is calculated in constant time where as select has
O(logN) time complexity. This is often used as a basic element in implementing
succinct data structures.

  1. ``` js
  2. const array = new RankedBitArray(10);
  3. array.setBit(1).setBit(3).setBit(7);
  4. array.rank(2); //=> 1
  5. array.rank(7); //=> 2
  6. array.select(2); //=> 3
  7. ```

Graphs


Structurae offers classes that implement adjacency list (AdjacencyList) and
adjacency matrix (AdjacencyMatrixUnweightedDirected,
AdjacencyMatrixUnweightedUndirected, AdjacencyMatrixWeightedDirected,
AdjacencyMatrixWeightedUnirected) as basic primitives to represent graphs
using TypedArrays, and the Graph class that extends the adjacency structures
to offer methods for traversing graphs (BFS, DFS), pathfinding (Dijkstra,
Bellman-Ford), and spanning tree construction (BFS, Prim).

Adjacency Structures


AdjacencyList implements adjacency list data structure extending a TypedArray
class. The adjacency list requires less storage space: number of vertices +
number of edges * 2 (for a weighted list). However, adding and removing edges is
much slower since it involves shifting/unshifting values in the underlying typed
array.

  1. ``` js
  2. import { AdjacencyListMixin } from "structurae";

  3. const List = AdjacencyListMixin(Int32Array);
  4. const graph = List.create(6, 6);

  5. // the length of a weighted graph is vertices + edges * 2 + 1
  6. graph.length; //=> 19
  7. graph.addEdge(0, 1, 5);
  8. graph.addEdge(0, 2, 1);
  9. graph.addEdge(2, 4, 1);
  10. graph.addEdge(2, 5, 2);
  11. graph.hasEdge(0, 1); //=> true
  12. graph.hasEdge(0, 4); //=> false
  13. graph.outEdges(2); //=> [4, 5]
  14. graph.inEdges(2); //=> [0]
  15. graph.hasEdge(0, 1); //=> true
  16. graph.getEdge(0, 1); //=> 5
  17. ```

Since the maximum amount of edges in AdjacencyList is limited to the number
specified at creation, adding edges can overflow throwing a RangeError. If
that's a possibility, use AdjacencyList#isFull method to check if the limit is
reached before adding an edge.

AdjacencyMatrixUnweightedDirected and AdjacencyMatrixUnweightedUndirected
implement adjacency matrix data structure for unweighted graphs representing
each edge by a single bit in an underlying ArrayBuffer.

AdjacencyMatrixWeightedDirected and AdjacencyMatrixWeightedUnirected
implement adjacency matrix for weighted graphs extending a given TypedArray to
store the weights akin to Grid.

  1. ``` js
  2. import {
  3.   AdjacencyMatrixUnweightedDirected,
  4.   AdjacencyMatrixWeightedDirectedMixin,
  5. } from "structurae";

  6. // creates a class for directed graphs that uses Int32Array for edge weights
  7. const Matrix = AdjacencyMatrixWeightedDirectedMixin(Int32Array);

  8. const unweightedMatrix = new AdjacencyMatrixUnweightedDirected.create(6);
  9. unweightedMatrix.addEdge(0, 1);
  10. unweightedMatrix.addEdge(0, 2);
  11. unweightedMatrix.addEdge(0, 3);
  12. unweightedMatrix.addEdge(2, 4);
  13. unweightedMatrix.addEdge(2, 5);
  14. unweightedMatrix.hasEdge(0, 1); //=> true
  15. unweightedMatrix.hasEdge(0, 4); //=> false
  16. unweightedMatrix.outEdges(2); //=> [4, 5]
  17. unweightedMatrix.inEdges(2); //=> [0]

  18. const weightedMatrix = Matrix.create(6);
  19. weightedMatrix.addEdge(0, 1, 3);
  20. weightedMatrix.hasEdge(0, 1); //=> true
  21. weightedMatrix.hasEdge(1, 0); //=> false
  22. weightedMatrix.getEdge(1, 0); //=> 3
  23. ```

Graph


Graph extends a provided adjacency structure with methods for traversing,
pathfinding, and spanning tree construction that use various graph algorithms.

  1. ``` js
  2. import {
  3.   AdjacencyMatrixUnweightedDirected,
  4.   AdjacencyMatrixWeightedDirectedMixin,
  5.   GraphMixin,
  6. } from "structurae";

  7. // create a graph for directed unweighted graphs that use adjacency list structure
  8. const UnweightedGraph = GraphMixin(AdjacencyMatrixUnweightedDirected);

  9. // for directed weighted graphs that use adjacency matrix structure
  10. const WeightedGraph = GraphMixin(
  11.   AdjacencyMatrixWeightedDirectedMixin(Int32Array),
  12. );
  13. ```

The traversal is done by a generator function Graph#traverse that can be
configured to use Breadth-First or Depth-First traversal, as well as returning
vertices on various stages of processing, i.e. only return vertices that are
fully processed (black), or being processed (gray), or just encountered
(white):

  1. ``` js
  2. const graph = WeightedGraph.create(6);
  3. graph.addEdge(0, 1, 3);
  4. graph.addEdge(0, 2, 2);
  5. graph.addEdge(0, 3, 1);
  6. graph.addEdge(2, 4, 8);
  7. graph.addEdge(2, 5, 6);

  8. // a BFS traversal results
  9. [...graph.traverse()]; //=> [0, 1, 2, 3, 4, 5]

  10. // DFS
  11. [...graph.traverse(true)]; //=> [0, 3, 2, 5, 4, 1]

  12. // BFS yeilding only non-encountered ("white") vertices starting from 0
  13. [...graph.traverse(false, 0, false, true)]; //=> [1, 2, 3, 4, 5]
  14. ```

Graph#path returns the list of vertices constituting the shortest path between
two given vertices. By default, the class uses BFS based search for unweighted
graphs, and Bellman-Ford algorithm for weighted graphs. However, the method can
be configured to use other algorithms by specifying arguments of the function:

  1. ``` js
  2. graph.path(0, 5); // uses Bellman-Ford by default
  3. graph.path(0, 5, true); // the graph is acyclic, uses DFS
  4. graph.path(0, 5, false, true); // the graph might have cycles, but has no negative edges, uses Dijkstra
  5. ```

Grids


BinaryGrid


BinaryGrid creates a grid or 2D matrix of bits and provides methods to operate
on it:

  1. ``` js
  2. import { BinaryGrid } from "structurae";

  3. // create a grid of 2 rows and 8 columns
  4. const bitGrid = BinaryGrid.create(2, 8);
  5. bitGrid.setValue(0, 0).setValue(0, 2).setValue(0, 5);
  6. bitGrid.getValue(0, 0); //=> 1
  7. bitGrid.getValue(0, 1); //=> 0
  8. bitGrid.getValue(0, 2); //=> 1
  9. ```

BinaryGrid packs bits into numbers like
BitField and holds them in an
ArrayBuffer, thus occupying the smallest possible space.

Grid


Grid extends a provided Array or TypedArray class to efficiently handle 2
dimensional data without creating nested arrays. Grid "unrolls" nested arrays
into a single array and pads its "columns" to the nearest power of 2 in order to
employ quick lookups with bitwise operations.

  1. ``` js
  2. import { GridMixin } from "structurae";

  3. const ArrayGrid = GridMixin(Array);

  4. // create a grid of 5 rows and 4 columns
  5. const grid = ArrayGrid.create(5, 4);
  6. grid.length; //=> 20
  7. grid[0]; //=> 0

  8. // create a grid from existing data:
  9. const dataGrid = new ArrayGrid([
  10.   1,
  11.   2,
  12.   3,
  13.   4,
  14.   5,
  15.   6,
  16.   7,
  17.   8,
  18. ]);
  19. // set columns number:
  20. dataGrid.columns = 4;
  21. dataGrid.getValue(1, 0); //=> 5

  22. // you can change dimensions of the grid by setting columns number at any time:
  23. dataGrid.columns = 2;
  24. dataGrid.getValue(1, 0); //=> 3
  25. ```

You can get and set elements using their row and column indexes:

  1. ``` js
  2. //=> ArrayGrid [1, 2, 3, 4, 5, 6, 7, 8]
  3. grid.getValue(0, 1); //=> 2
  4. grid.setValue(0, 1, 10);
  5. grid.getValue(0, 1); //=> 10

  6. // use `getIndex` to get an array index of an element at given coordinates
  7. grid.getIndex(0, 1); //=> 1

  8. // use `getCoordinates` to find out row and column indexes of a given element by its array index:
  9. grid.getCoordinates(0); //=> [0, 0]
  10. grid.getCoordinates(1); //=> [0, 1]
  11. ```

A grid can be turned to and from an array of nested arrays using respectively
Grid.fromArrays and Grid#toArrays methods:

  1. ``` js
  2. const grid = ArrayGrid.fromArrays([[1, 2], [3, 4]]);
  3. //=> ArrayGrid [ 1, 2, 3, 4 ]
  4. grid.getValue(1, 1); //=> 4

  5. // if arrays are not the same size or their size is not equal to a power two, Grid will pad them with 0 by default
  6. // the value for padding can be specified as the second argument
  7. const grid = ArrayGrid.fromArrays([[1, 2], [3, 4, 5]]);
  8. //=> ArrayGrid [ 1, 2, 0, 0, 3, 4, 5, 0 ]
  9. grid.getValue(1, 1); //=> 4
  10. grid.toArrays(); //=> [ [1, 2], [3, 4, 5] ]

  11. // you can choose to keep the padding values
  12. grid.toArrays(true); //=> [ [1, 2, 0, 0], [3, 4, 5, 0] ]
  13. ```

SymmetricGrid


SymmetricGrid is a Grid that offers a more compact way of encoding symmetric or
triangular square matrices using half as much space.

  1. ``` js
  2. import { SymmetricGrid } from "structurae";

  3. const grid = ArrayGrid.create(100, 100);
  4. grid.length; //=> 12800
  5. const symmetricGrid = SymmetricGrid.create(100);
  6. symmetricGrid.length; //=> 5050
  7. ```

Since the grid is symmetric, it returns the same value for a given pair of
coordinates regardless of their position:

  1. ``` js
  2. symmetricGrid.setValue(0, 5, 10);
  3. symmetricGrid.getValue(0, 5); //=> 10
  4. symmetricGrid.getValue(5, 0); //=> 10
  5. ```

Sorted Structures


BinaryHeap


BinaryHeap extends built-in Array to implement the binary heap data structure.
All the mutating methods (push, shift, splice, etc.) do so while maintaining the
valid heap structure. By default, BinaryHeap implements min-heap, but it can be
changed by providing a different comparator function:

  1. ``` js
  2. import { BinaryHeap } from "structurae";

  3. class MaxHeap extends BinaryHeap {}
  4. MaxHeap.compare = (a, b) => a > b;
  5. ```

In addition to all array methods, BinaryHeap provides a few methods to traverse
or change the heap:

  1. ``` js
  2. const heap = new BinaryHeap(10, 1, 20, 3, 9, 8);
  3. heap[0]; //=> 1
  4. // the left child of the first (minimal) element of the heap
  5. heap.left(0); //=> 3
  6. // the right child of the first (minimal) element of the heap
  7. heap.right(0); //=> 8
  8. // the parent of the second element of the heap
  9. heap.parent(1); //=> 1
  10. // returns the first element and adds a new element in one operation
  11. heap.replace(4); //=> 1
  12. heap[0]; //=> 3
  13. heap[0] = 6;
  14. // BinaryHeap [ 6, 4, 8, 10, 9, 20 ]
  15. heap.update(0); // updates the position of an element in the heap
  16. // BinaryHeap [ 4, 6, 8, 10, 9, 20 ]
  17. ```

SortedArray


SortedArray extends Array with methods to efficiently handle sorted data. The
methods that change the contents of an array do so while preserving the sorted
order:

  1. ``` js
  2. import { SortedArray } from "structurae";

  3. const sortedArray = new SortedArray();
  4. sortedArray.push(1);
  5. //=> SortedArray [ 1, 2, 3, 4, 5, 9 ]
  6. sortedArray.unshift(8);
  7. //=> SortedArray [ 1, 2, 3, 4, 5, 8, 9 ]
  8. sortedArray.splice(0, 2, 6);
  9. //=> SortedArray [ 3, 4, 5, 6, 8, 9 ]
  10. ```

uniquify can be used to remove duplicating elements from the array:

  1. ``` js
  2. const a = SortedArray.from([1, 1, 2, 2, 3, 4]);
  3. a.uniquify();
  4. //=> SortedArray [ 1, 2, 3, 4 ]
  5. ```

If the instance property unique of an array is set to true, the array will
behave as a set and avoid duplicating elements:

  1. ``` js
  2. const a = new SortedArray();
  3. a.unique = true;
  4. a.push(1); //=> 1
  5. a.push(2); //=> 2
  6. a.push(1); //=> 2
  7. a; //=> SortedArray [ 1, 2 ]
  8. ```

To create a sorted collection from unsorted array-like objects or items use
from and of static methods respectively:

  1. ``` js
  2. SortedArray.from([3, 2, 9, 5, 4]);
  3. //=> SortedArray [ 2, 3, 4, 5, 9 ]
  4. SortedArray.of(8, 5, 6);
  5. //=> SortedArray [ 5, 6, 8 ]
  6. ```

new SortedArray behaves the same way as new Array and should be used with
already sorted elements:

  1. ``` js
  2. new SortedArray(...[1, 2, 3, 4, 8]);
  3. //=> SortedArray [ 1, 2, 3, 4, 8 ];
  4. ```

indexOf and includes use binary search that increasingly outperforms the
built-in methods as the size of the array grows.

SortedArray provides isSorted method to check if the collection is sorted, and
range method to get elements of the collection whose values are between the
specified range:

  1. ``` js
  2. //=> SortedArray [ 2, 3, 4, 5, 9 ]
  3. sortedArray.range(3, 5);
  4. // => SortedArray [ 3, 4, 5 ]
  5. sortedArray.range(undefined, 4);
  6. // => SortedArray [ 2, 3, 4 ]
  7. sortedArray.range(4);
  8. // => SortedArray [ 4, 5, 8 ]
  9. ```

SortedArray also provides a set of functions to perform common set operations
and find statistics of any sorted array-like objects.

License