AVL Tree

       

Flexible AVL Tree for TypeScript and JavaScript

$3

``bash
npm i @alexaegis/avl
`

$3

`TypeScript
import { Tree } from '@alexaegis/avl';

const tree = new Tree(); // Create
tree.set(key, value); // Set
const result: Value = tree.get(key) // Get
`

Usage

Although the typing does not enforce the key to have a compareTo method (to allow using any type of object as keys, not just what you created and have control over) The tree will throw runtime errors if it can't order the keys.

> The most basic case is that the key is a string or a number, then the value itself can be directly converted to a string or a number (Implicit or explicit, either having a convertTo(): K method on the objects prototyle or supply a converter function to the Tree object), and then if the key is an object it has to be comparable (Implicit or explicit, either having a comparable(a: K, b: K): number method on the objects prototype or supply a converter function to the Tree object)

> These functions you supply will al have their this value bound to the object the are getting applied on. For this reason if you want to use this in you comparator and/or converter methods use regular functions instead of lambdas.

Implicit keys - Comparable, Comparator

if the object you are using as a key contains a compareTo(T) method then it will work just fine

`TypeScript
class Key {
constructor(public key: number) {}
}
const tree = new Tree();
tree.set(new Key(2), new Value(4)); // Cannot compare error
`

$3

`TypeScript
class Key implements Comparable {
constructor(public key: number) {}
compareTo(other: Key): number {
return this.key - other.key;
}
}
const tree = new Tree();
tree.set(new Key(2), new Value(4)); // 👌 the key will be valid
`

$3

Very important, if using a lambda as a comparator you cant use the this keyword in it (as usual),
and the only type of comparator you can write is the 'two argumen' one as seen below.
But you can use this if you use a regular anonym function. This will act the same as the one you
would write while implementing the interface. There is an optional second argument here too, that's gonna be the same as a. But you don't need to use it.

`TypeScript
class Key {
constructor(public key: number) {}
}

let tree = new Tree((a: Key, b: Key) => a.key - b.key); // Using Lambdas
// Because of the fancy inner binding, you can even write this. It's basically the same
tree = new Tree(function (b: Key) { return this.key - b.key; });

tree.set(new Key(2), new Value(4)); // 👌 the key will be valid
`

Explicit keys - Convertable, Converter

$3

> Only using Converters/Convertables allows the usage of the push method! You can even convert to a comparable!

`TypeScript
const tree = new Tree();
tree.push(new Value(4)); // Cannot convert error
`

`TypeScript
export class Value implements Convertable {
constructor(public n: number) {}
convertTo(): number | string {
return this.n;
}
}

const tree = new Tree();
tree.push(new Value(4)); // 👌 the key will be 4

`

$3

Alternatively you can supply a function to act as the converter

`TypeScript
export class Value {
constructor(public n: number) {}
}
export class AnotherValue {
constructor(public n: number) {}
}

const tree = new Tree(undefined, (val: Value) => val.n);
tree.push(new Value(4));
tree.push(new AnotherValue(1)); // You can do messy things like this without implementing a single interface

`

$3

This is great when you have a bunch of objects you want to quickly access by keys that are encapsulated within the object.

`TypeScript
export class Coord implements Comparable {
constructor(public x: number = 0, public y: number = 0) {}
compareTo(other: Coord): number {
return this.y === other.y ? this.x - other.x : this.y - other.y;
}
}

export class BasicConvertableToComparable implements Convertable {
constructor(private coord: Coord) {}
convertTo(): Coord {
return this.coord;
}
}

const tree: Tree;
tree.push(new BasicConvertableToComparable(new Coord(1, 1)));
tree.get(new Coord(1, 1)); // The BasicConvertableToComparable object you pushed in

`

$3

You can search for either nearest on left and nearest on right values if the one you search for might be missing.

`typescript
const tree = new Tree();
tree.set(1, 1);
tree.set(2, 2);
tree.set(4, 4);
tree.set(8, 8);
tree.set(7, 7);
tree.set(10, 10);
tree.set(14, 14);
tree.set(12, 12);

const last = tree.lastBefore(13.66); // 12
const first = tree.firstFrom(13.66); // 14
const enclosing = tree.enclosing(13.66); // {last: 12, first: 14}

// When you might need the keys too
const lastNode = tree.lastNodeBefore(13.66); // Node {h: 1, k: 12, v: 12}
const firstNode = tree.firstNodeFrom(13.66); // Node {h: 2, k: 14, v: 14, …}
const enclosingNodes = tree.enclosingNodes(13.66); // Object {last: Node {h: 1, k: 12, v: 12}, first: Node {h: 2, k: 14, v: 14, …}}
``

For more examples check the mocha tests

---

Technologies

$3

> JavaScript runtime

$3

> Package manager for Node

$3

> Typed superset of JavaScript

$3

> Linting tool

$3

> Behaviour driven testing framework

$3

> Assertion library

$3

> Code coverage tool

Recommendations

$3

> IDE for everything. Settings

$3

> Font with ligatures

Services

$3

> Continuous Integration solution

$3

> Code Quality monitoring

$3

> Maintainability and Coverage reports

$3

> Vulnerability detection

$3

> Badges to look cool