quick-avl - npm Package Compare versions

Comparing version 0.0.2 to 0.0.3

dist/avl-tree-node.d.ts

 export interface AvlTreeNode<K, V> {
-    key: K;
-    value: V;
+    readonly key: K;
+    readonly value: V;
     parent?: AvlTreeNode<K, V>;
@@ -5,0 +5,0 @@ left?: AvlTreeNode<K, V>;

dist/avl-tree.d.ts

 import { AvlTreeNode } from './avl-tree-node';
-export declare class AvlTree<K = any, V = any> {
+/**
+ * An AVL tree, a self-balancing binary search tree.
+ * Acts as a key-value map.
+ */
+export declare class AvlTree<K = any, V = any> implements Map<K, V> {
     private compareFunction;
     private _root?;
     private _size;
+    /**
+     * Creates an AVL tree.
+     * @param compareFunction A comparison function that enforces a total ordering:
+     *  i.e. if fn(a, b) < 0 then fn(b, a) > 0.
+     */
     constructor(compareFunction?: CompareFunction<K>);
+    /**
+     * The number of elements in the AVL tree.
+     */
     get size(): number;
+    /**
+     * The root node of the tree.
+     */
     get root(): AvlTreeNode<K, V> | undefined;
+    clear(): void;
+    /**
+     * Converts the tree to a structure that can be serialized to JSON
+     * (i.e. has no circular structure)
+     * @returns A JSON-friendly represenation of this tree.
+     */
     toJSON(): AvlTreeNode<K, V> | undefined;
-    contains(key: K): boolean;
-    findNode(key: K): AvlTreeNode<K, V> | undefined;
-    find(key: K): V | undefined;
     /**
+     * Checks if the tree contains a certain key.
+     * @param key The key to check
+     * @returns True if the key exists in this tree, false otherwise.
+     */
+    has(key: K): boolean;
+    /**
+     * Finds a node with a specified key.
+     * @param key Key to search for.
+     * @returns The node, or undefined if not found
+     */
+    getNode(key: K): AvlTreeNode<K, V> | undefined;
+    /**
+     * Finds a value associated with a specified key.
+     * @param key Key to search for.
+     * @returns The value, or undefined if not found.
+     */
+    get(key: K): V | undefined;
+    /**
+     * Inserts a key-value pair into the AVL tree. Throws
+     * an error if the key already exists
+     * @param key The key used to determine the order in the tree
+     * @param value The value attached to the key
+     * @returns The tree itself (for chaining)
+     */
+    set(key: K, value: V): this;
+    /**
      * Inserts a key-value pair into the AVL tree.
@@ -26,10 +70,44 @@ * @param key The key used to determine the order in the tree
      */
-    remove(key: K): boolean;
+    delete(key: K): boolean;
+    /**
+     * Removes a node from the tree.
+     * @param node The node to remove.
+     */
+    deleteNode(node: AvlTreeNode<K, V>): void;
+    /**
+     * Converts the tree to a human-readable representation.
+     * @returns A nice visualisation.
+     */
     toString(): string;
+    get [Symbol.toStringTag](): string;
+    /**
+     * Prints a human-readable representation to the console.
+     */
     print(): void;
-    keys(): K[];
-    values(): V[];
-    forEach(fn: (node: AvlTreeNode<K, V>, index: number) => void): void;
-    map<T>(fn: (node: AvlTreeNode<K, V>, index: number) => T): T[];
-    entries(): [K, V][];
+    /**
+     * Gets an array with the keys in this tree.
+     * @returns The keys
+     */
+    keys(): Generator<K>;
+    keyList(): K[];
+    /**
+     * Gets an array with the values in this tree.
+     * @returns The values,
+     */
+    values(): Generator<V>;
+    valueList(): V[];
+    /**
+     * Executes a function on each node in the tree.
+     * @param fn The iteration function
+     */
+    forEach(fn: (value: V, key: K, map: AvlTree<K, V>) => void, thisArg?: any): void;
+    /**
+     * Calls a defined callback function on each tree node, and returns
+     * an array that contains the results.
+     * @param fn A function that accepts up to two arguments. The map method calls the callbackfn function one time for each node in the tree.
+     * @returns An array containing the results
+     */
+    map<T>(fn: (entry: [K, V], index: number) => T): T[];
+    entries(): Generator<[K, V]>;
+    entryList(): [K, V][];
     minKey(): K | undefined;
@@ -41,4 +119,4 @@ minValue(): V | undefined;
     maxNode(): AvlTreeNode<K, V> | undefined;
-    at(index: number): AvlTreeNode<K, V> | undefined;
-    walk(fn: (node: AvlTreeNode<K, V>, index: number, done: () => void) => void): void;
+    at(index: number): [K, V] | undefined;
+    walk(fn: (entry: [K, V], index: number, done: () => void) => void): void;
     predecessor(node: AvlTreeNode<K, V>): AvlTreeNode<K, V> | undefined;
@@ -50,3 +128,3 @@ successor(node: AvlTreeNode<K, V>): AvlTreeNode<K, V> | undefined;
      */
-    [Symbol.iterator](): Generator<AvlTreeNode<K, V>>;
+    [Symbol.iterator](): Generator<[K, V]>;
     private rebalanceAfterInsertion;
@@ -53,0 +131,0 @@ /**

dist/avl-tree.js

@@ -5,3 +5,12 @@ "use strict";
 const avl_tree_utils_1 = require("./avl-tree-utils");
+/**
+ * An AVL tree, a self-balancing binary search tree.
+ * Acts as a key-value map.
+ */
 class AvlTree {
+    /**
+     * Creates an AVL tree.
+     * @param compareFunction A comparison function that enforces a total ordering:
+     *  i.e. if fn(a, b) < 0 then fn(b, a) > 0.
+     */
     constructor(compareFunction = defaultCompareFunction) {
@@ -11,15 +20,40 @@ this.compareFunction = compareFunction;
     }
+    /**
+     * The number of elements in the AVL tree.
+     */
     get size() {
         return this._size;
     }
+    /**
+     * The root node of the tree.
+     */
     get root() {
         return this._root;
     }
+    clear() {
+        this._root = undefined;
+        this._size = 0;
+    }
+    /**
+     * Converts the tree to a structure that can be serialized to JSON
+     * (i.e. has no circular structure)
+     * @returns A JSON-friendly represenation of this tree.
+     */
     toJSON() {
         return this._root && avl_tree_utils_1.nodeToJson(this._root);
     }
-    contains(key) {
-        return !!this.findNode(key);
+    /**
+     * Checks if the tree contains a certain key.
+     * @param key The key to check
+     * @returns True if the key exists in this tree, false otherwise.
+     */
+    has(key) {
+        return !!this.getNode(key);
     }
-    findNode(key) {
+    /**
+     * Finds a node with a specified key.
+     * @param key Key to search for.
+     * @returns The node, or undefined if not found
+     */
+    getNode(key) {
         let current = this._root;
@@ -41,7 +75,25 @@ while (current) {
     }
-    find(key) {
+    /**
+     * Finds a value associated with a specified key.
+     * @param key Key to search for.
+     * @returns The value, or undefined if not found.
+     */
+    get(key) {
         var _a;
-        return (_a = this.findNode(key)) === null || _a === void 0 ? void 0 : _a.value;
+        return (_a = this.getNode(key)) === null || _a === void 0 ? void 0 : _a.value;
     }
     /**
+     * Inserts a key-value pair into the AVL tree. Throws
+     * an error if the key already exists
+     * @param key The key used to determine the order in the tree
+     * @param value The value attached to the key
+     * @returns The tree itself (for chaining)
+     */
+    set(key, value) {
+        if (!this.insert(key, value)) {
+            throw new Error(`Key already exists: ${key}`);
+        }
+        return this;
+    }
+    /**
      * Inserts a key-value pair into the AVL tree.
@@ -108,8 +160,16 @@ * @param key The key used to determine the order in the tree
      */
-    remove(key) {
-        var _a, _b, _c;
-        const node = this.findNode(key);
+    delete(key) {
+        const node = this.getNode(key);
         if (!node) {
             return false;
         }
+        this.deleteNode(node);
+        return true;
+    }
+    /**
+     * Removes a node from the tree.
+     * @param node The node to remove.
+     */
+    deleteNode(node) {
+        var _a, _b, _c;
         let rebalanceStartNode;
@@ -233,7 +293,16 @@ let removedNodeWasOnLeft;
         }
-        return true;
     }
+    /**
+     * Converts the tree to a human-readable representation.
+     * @returns A nice visualisation.
+     */
     toString() {
         return avl_tree_utils_1.printTreeNode(this._root);
     }
+    get [Symbol.toStringTag]() {
+        return 'AvlTree';
+    }
+    /**
+     * Prints a human-readable representation to the console.
+     */
     /* istanbul ignore next */
@@ -243,28 +312,47 @@ print() {
     }
-    keys() {
-        const results = [];
-        for (const node of this) {
-            results.push(node.key);
+    /**
+     * Gets an array with the keys in this tree.
+     * @returns The keys
+     */
+    *keys() {
+        for (const [key] of this) {
+            yield key;
         }
-        return results;
     }
-    values() {
-        const results = [];
-        for (const node of this) {
-            results.push(node.value);
+    keyList() {
+        return Array.from(this.keys());
+    }
+    /**
+     * Gets an array with the values in this tree.
+     * @returns The values,
+     */
+    *values() {
+        for (const [, value] of this) {
+            yield value;
         }
-        return results;
     }
-    forEach(fn) {
-        let index = 0;
-        for (const node of this) {
-            fn(node, index);
-            index += 1;
+    valueList() {
+        return Array.from(this.values());
+    }
+    /**
+     * Executes a function on each node in the tree.
+     * @param fn The iteration function
+     */
+    // eslint-disable-next-line @typescript-eslint/explicit-module-boundary-types
+    forEach(fn, thisArg) {
+        for (const [key, value] of this) {
+            fn.apply(thisArg, [value, key, this]);
         }
     }
+    /**
+     * Calls a defined callback function on each tree node, and returns
+     * an array that contains the results.
+     * @param fn A function that accepts up to two arguments. The map method calls the callbackfn function one time for each node in the tree.
+     * @returns An array containing the results
+     */
     map(fn) {
         const results = [];
         let index = 0;
-        for (const node of this) {
-            results.push(fn(node, index));
+        for (const entry of this) {
+            results.push(fn(entry, index));
             index += 1;
@@ -274,9 +362,10 @@ }
     }
-    entries() {
-        const results = [];
-        for (const node of this) {
-            results.push([node.key, node.value]);
+    *entries() {
+        for (const [key, value] of this) {
+            yield [key, value];
         }
-        return results;
     }
+    entryList() {
+        return Array.from(this.entries());
+    }
     minKey() {
@@ -323,5 +412,5 @@ var _a;
         let selected;
-        this.walk((node, i, done) => {
+        this.walk((entry, i, done) => {
             if (index === i) {
-                selected = node;
+                selected = entry;
                 done();
@@ -335,4 +424,4 @@ }
         let isDone = false;
-        for (const n of this) {
-            fn(n, i, () => (isDone = true));
+        for (const entry of this) {
+            fn(entry, i, () => (isDone = true));
             i += 1;
@@ -395,3 +484,3 @@ if (isDone) {
                 current = stack.pop();
-                yield current;
+                yield [current.key, current.value];
                 current = current.right;
@@ -398,0 +487,0 @@ }

package.json

 {
   "name": "quick-avl",
-  "version": "0.0.2",
+  "version": "0.0.3",
   "description": "AVL tree: a self-balancing binary search tree",
@@ -5,0 +5,0 @@ "keywords": [

README.md

@@ -5,2 +5,4 @@ # quick-avl
 
+Implements the Map interface.
+
 Named after the inventors [Adelson-Velsky and Landis](https://en.wikipedia.org/wiki/AVL_tree), an AVL tree enforces an invariant where the heights of the subtrees of a node differ by at most one. Rebalancing is performed after each insert or remove operation, if that operation made the tree imbalanced.
@@ -34,16 +36,18 @@
 
-users.insert(100, 'Bob'); // --> AvlTreeNode
-users.insert(200, 'Carol'); // --> AvlTreeNode
-users.insert(0, 'Alice'); // --> AvlTreeNode
+users.set(100, 'Bob').set(200, 'Carol').set(0, 'Alice');
 
-users.find(100); // --> 'Bob'
-users.contains(100); // --> true
+users.get(100); // --> 'Bob'
+users.has(100); // --> true
 
-users.remove(200); // --> true
+users.delete(200); // --> true
 
-users.values(); // --> ['Alice', 'Carol']
+users.valueList(); // --> ['Alice', 'Carol']
 
-for (const node of users) {
-  console.log(`Key: ${node.key}, value: ${node.value}`);
+for (const [key, value] of users) {
+  console.log(`Key: ${key}, value: ${value}`);
 }
 ```
+
+## Why another AVL library
+
+While there are some excellent AVL libraries available within NPM, these libraries swap out tree node values while performing tree balancing. I required an AVL library that does not replace keys or values within a node. That way, a reference to a tree node will always keep the same value.

No alert changes

Improved metrics

Total package byte prevSize

46077

increased by13.33%

Lines of code

1164

increased by16.75%

Number of lines in readme file

52

increased by8.33%

No dependency changes