kdim

A collection of interesting data structures and utility types for messing around with mathematical things in Node/JS/TS. No guarantees are made here as to the speed, efficiency, or correctness of tools providied!

Installation

yarn add kdim

or

npm install --save kdim

---

Utility Types

Tuple

A typed tuple of generic length.

import { Tuple } from "kdim";

const threeBoolTuple: Tuple<boolean, 3> = [true, false, false];
const wrongBoolTuple: Tuple<boolean, 3> = [false, true]; // Error: Source has 2 element(s) but target requires 3

This also composes to allow for strongly-typed multidimensional arrays, such as a chess board:

import { Tuple } from "kdim";

type Piece = "pawn" | "rook" | "knight" | "bishop" | "queen" | "king";
type Board = Tuple<Tuple<Piece | null, 8>, 8>;

const board: Board = [
  ["rook", "knight", "bishop", "queen", "king", "bishop", "knight", "rook"],
  ["pawn", "pawn", "pawn", "pawn", "pawn", "pawn", "pawn", "pawn"],
  [null, null, null, null, null, null, null, null],
  [null, null, null, null, null, null, null, null],
  [null, null, null, null, null, null, null, null],
  [null, null, null, null, null, null, null, null],
  ["pawn", "pawn", "pawn", "pawn", "pawn", "pawn", "pawn", "pawn"],
  ["rook", "knight", "bishop", "queen", "king", "bishop", "knight", "rook"],
];

Vec

A convenience type equivalent to Tuple<number, K>, useful for mathematical computation and data structures.

import { Vec } from "kdim";

const position: Vec<3> = [1.0, 69, 420];
const speed: Vec<3> = [-1, 3, 11];
const accel: Vec<3> = [0, 0, "no"]; // Error: type 'string' is not assignable to type 'number'

---

Data Structures

KDTree

A time-efficient data structure for searching higher-dimensional datasets. Inspired by Mike Pound's Computerphile Video.

import { Vec, KDTree } from "kdim";

const data: Vec<5>[] = [
  [0, 1, 1, 0, 1],
  [1, 1, 1, 1, 1],
  [0, 0, 0, 1, 0],
];

const tree = new KDTree<5>(data);
const testPoint: Vec<5> = [1, 0, 1, 1, 1];

tree.has(testPoint); // false

const { point, distance } = tree.nearestNeighbor(testPoint); // { point: [1, 1, 1, 1, 1], distance: 1 }

tree.insert(testPoint);
tree.has(testPoint); // true

tree.remove(testPoint);
tree.has(testPoint); // false

Note: by default, input datasets are shallowly copied during tree construction, and retained within the data structure. If desired, the underlying dataset may be used without copying, using the option copy: false;

RingBuffer

A fixed-capacity FIFO queue that overwrites earliest entries when its capacity is exceeded.

import { RingBuffer } from "kdim";

// Initialized with capacity
const buff = new RingBuffer<string>(10);

buff.enqueue("age");
buff.enqueue("quod");
buff.enqueue("agis");

buff.isFull; // false
buff.isEmpty; // false

buff.dequeue(); // "age"
buff.peek(); // "quod"
buff.drain(); // ["quod", "agis"]

buff.isEmpty; // true

// Initialized with data
const buff2 = RingBuffer.from<number>([12, 24, 36, 48]);

buff.capacity; // 4

buff.enqueue(1);
buff.peek(); // 1
buff.peek(2); // 36
buff.dequeue(); // 1
buff.dequeue(); // 24
buff.drain(); // [36, 48];

---

License

MIT © Tobias Fried