0.1.1 • Published 1 year ago

# @anchor-logoot/dtst-js v0.1.1

7
LGPL-3.0-or-later
Repository
-
Last release
1 year ago

## dtst-js

Differential Ternary Search Tree JS

## 🚧 Work In Progress 🚧

Currently, there is no tree balancing done, no optimizations have been considered, and documentation is relatively poor. This is because this package was pulled out of the code base of `logootish-js` and I haven't had time to go through and make proper examples.

## What is it?

TL;DR it's an algorithm for storing, finding, and quickly applying offsets to a number for an ordered list of nodes.

This is a custom algorithm derived from a binary search tree. It was designed to model text sequences that may require nodes to be shifted over in bulk. Let's assume that each node in a traditional BST has a numeric position. Shifting many of these positions is quite expensive since one would need to iterate over every node after the position being shifted. Instead, it would be quite a bit easier if we could make positions of nodes relative to one another. This is exactly what this algorithm does. Each node must have an integer `value`. The primary method of sorting nodes is by their value. Once added to the tree, a node's value may be computed by using the `absolute_value` getter.

However, note that I'm calling this a differential ternary search tree, not binary. As it turns out, if you have nodes that are being shifted around that may potentially have the same value, it's quite easy to corrupt the tree. To make this easier, instead of placing nodes with equal value to a parent in the left side of the tree, an array is added to each node to store nodes with the same value. This means that all nodes to the left of a node have a lower value and nodes to the right have a greater value. However, in the case of zero length nodes, it is often desireable to keep them in order so that they stay in order when you offset them. In other words, if you have five nodes of zero length and you offset the middle node, you often want to keep these five nodes in order so that you know which three nodes will be offset as a result. This is done by defining a `preferential_cmp` method in the abstract class. This will be used to determine order when nodes have the same value. This must return the same order as `value` in all cases. You also can just set it to return 0 all the time if you don't plan on having nodes with the same value.

So, there you have it. To add custom data, just extend the `DTstNode` class (the type parameter is just the type of your new class) and start adding your nodes to a `DTst` (the type paramater is just the type of your nodes). Note that nodes can only be added to a single `DTst`.

## Docs and examples

For now, there's just the JSDoc. Sorry.

## Development

``````# Install deps
yarn

# Check types
yarn run check-types

# Just lint
yarn run lint

# Build for production (and lint)
yarn run build

# Build jsdoc
yarn run build:docs

# Test
yarn run test