New Case Study:See how Anthropic automated 95% of dependency reviews with Socket.Learn More →
Socket
Sign inDemoInstall
Socket
Sign inDemoInstall

queue-typed

Package Overview
Dependencies
Maintainers
0
Versions
162
Alerts
File Explorer

Advanced tools

License
Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

queue-typed - npm Package Compare versions

Comparing version 1.53.6 to 1.53.7

dist/common/index.d.ts
dist/common/index.js
src/common/index.ts

17

dist/data-structures/binary-tree/avl-tree-multi-map.js

@@ -99,3 +99,3 @@ "use strict";

createTree(options) {
return new AVLTreeMultiMap([], Object.assign({ iterationType: this.iterationType, isMapMode: this._isMapMode, comparator: this._comparator, toEntryFn: this._toEntryFn }, options));
return new AVLTreeMultiMap([], Object.assign({ iterationType: this.iterationType, isMapMode: this._isMapMode, extractComparable: this._extractComparable, toEntryFn: this._toEntryFn, isReverse: this._isReverse }, options));
}

@@ -136,13 +136,10 @@ /**

}
if (this.isRaw(keyNodeEntryOrRaw)) {
const [key, entryValue] = this._toEntryFn(keyNodeEntryOrRaw);
const finalValue = value !== null && value !== void 0 ? value : entryValue;
if (this.isKey(key))
return [this.createNode(key, finalValue, count), finalValue];
}
if (this.isKey(keyNodeEntryOrRaw))
return [this.createNode(keyNodeEntryOrRaw, value, count), value];
if (this.isRaw(keyNodeEntryOrRaw)) {
if (this._toEntryFn) {
const [key, entryValue] = this._toEntryFn(keyNodeEntryOrRaw);
const finalValue = value !== null && value !== void 0 ? value : entryValue;
if (this.isKey(key))
return [this.createNode(key, finalValue, count), finalValue];
}
return [undefined, undefined];
}
return [undefined, undefined];

@@ -149,0 +146,0 @@ }

4

dist/data-structures/binary-tree/avl-tree.js

@@ -88,3 +88,3 @@ "use strict";

createTree(options) {
return new AVLTree([], Object.assign({ iterationType: this.iterationType, isMapMode: this._isMapMode, comparator: this._comparator, toEntryFn: this._toEntryFn }, options));
return new AVLTree([], Object.assign({ iterationType: this.iterationType, isMapMode: this._isMapMode, extractComparable: this._extractComparable, toEntryFn: this._toEntryFn, isReverse: this._isReverse }, options));
}

@@ -413,3 +413,3 @@ /**

node = this.ensureNode(node);
const path = this.getPathToRoot(node => node, node, false); // first O(log n) + O(log n)
const path = this.getPathToRoot(node, node => node, false); // first O(log n) + O(log n)
for (let i = 0; i < path.length; i++) {

@@ -416,0 +416,0 @@ // second O(log n)

73

dist/data-structures/binary-tree/binary-tree.d.ts

@@ -11,2 +11,3 @@ /**

import { IterableEntryBase } from '../base';
import { Range } from '../../common';
/**

@@ -124,2 +125,9 @@ * Represents a node in a binary tree.

isNode(keyNodeEntryOrRaw: BTNRep<K, V, NODE> | R): keyNodeEntryOrRaw is NODE;
/**
* The function `isRaw` checks if the input parameter is of type `R` by verifying if it is an object.
* @param {BTNRep<K, V, NODE> | R} keyNodeEntryOrRaw - BTNRep<K, V, NODE> | R
* @returns The function `isRaw` is checking if the `keyNodeEntryOrRaw` parameter is of type `R` by
* checking if it is an object. If the parameter is an object, the function will return `true`,
* indicating that it is of type `R`.
*/
isRaw(keyNodeEntryOrRaw: BTNRep<K, V, NODE> | R): keyNodeEntryOrRaw is R;

@@ -155,2 +163,3 @@ /**

isNIL(keyNodeEntryOrRaw: BTNRep<K, V, NODE> | R): boolean;
isRange(keyNodeEntryRawOrPredicate: BTNRep<K, V, NODE> | R | NodePredicate<NODE> | Range<K>): keyNodeEntryRawOrPredicate is Range<K>;
/**

@@ -231,2 +240,11 @@ * The function determines whether a given key, node, entry, or raw data is a leaf node in a binary

*
* The `merge` function in TypeScript merges another binary tree into the current tree by adding all
* elements from the other tree.
* @param anotherTree - `BinaryTree<K, V, R, NODE, TREE>`
*/
merge(anotherTree: BinaryTree<K, V, R, NODE, TREE>): void;
/**
* Time Complexity: O(k * n)
* Space Complexity: O(1)
*
* The `refill` function clears the existing data structure and then adds new key-value pairs based

@@ -261,2 +279,27 @@ * on the provided input.

*
* The `search` function in TypeScript performs a depth-first or breadth-first search on a tree
* structure based on a given predicate or key, with options to return multiple results or just one.
* @param {BTNRep<K, V, NODE> | R | NodePredicate<NODE>} keyNodeEntryRawOrPredicate - The
* `keyNodeEntryRawOrPredicate` parameter in the `search` function can accept three types of values:
* @param [onlyOne=false] - The `onlyOne` parameter in the `search` function is a boolean flag that
* determines whether the search should stop after finding the first matching node. If `onlyOne` is
* set to `true`, the search will return as soon as a matching node is found. If `onlyOne` is
* @param {C} callback - The `callback` parameter in the `search` function is a callback function
* that will be called on each node that matches the search criteria. It is of type `C`, which
* extends `NodeCallback<NODE>`. The default value for `callback` is `this._DEFAULT_NODE_CALLBACK` if
* @param {BTNRep<K, V, NODE> | R} startNode - The `startNode` parameter in the `search` function is
* used to specify the node from which the search operation should begin. It represents the starting
* point in the binary tree where the search will be performed. If no specific `startNode` is
* provided, the search operation will start from the root
* @param {IterationType} iterationType - The `iterationType` parameter in the `search` function
* specifies the type of iteration to be used when searching for nodes in a binary tree. It can have
* two possible values:
* @returns The `search` function returns an array of values that match the provided criteria based
* on the search algorithm implemented within the function.
*/
search<C extends NodeCallback<NODE>>(keyNodeEntryRawOrPredicate: BTNRep<K, V, NODE> | R | NodePredicate<NODE>, onlyOne?: boolean, callback?: C, startNode?: BTNRep<K, V, NODE> | R, iterationType?: IterationType): ReturnType<C>[];
/**
* Time Complexity: O(n)
* Space Complexity: O(k + log n)
*
* The function `getNodes` retrieves nodes from a binary tree based on a key, node, entry, raw data,

@@ -305,16 +348,2 @@ * or predicate, with options for recursive or iterative traversal.

*
* The function `getNodeByKey` retrieves a node by its key from a binary tree structure.
* @param {K} key - The `key` parameter is the value used to search for a specific node in a data
* structure.
* @param {IterationType} iterationType - The `iterationType` parameter is a type of iteration that
* specifies how the tree nodes should be traversed when searching for a node with the given key. It
* is an optional parameter with a default value of `this.iterationType`.
* @returns The `getNodeByKey` function is returning an optional binary tree node
* (`OptNodeOrNull<NODE>`).
*/
getNodeByKey(key: K, iterationType?: IterationType): OptNodeOrNull<NODE>;
/**
* Time Complexity: O(n)
* Space Complexity: O(log n)
*
* This function overrides the `get` method to retrieve the value associated with a specified key,

@@ -487,3 +516,3 @@ * node, entry, raw data, or predicate in a data structure.

*/
getPathToRoot<C extends NodeCallback<OptNodeOrNull<NODE>>>(callback: C | undefined, beginNode: BTNRep<K, V, NODE> | R, isReverse?: boolean): ReturnType<C>[];
getPathToRoot<C extends NodeCallback<OptNodeOrNull<NODE>>>(beginNode: BTNRep<K, V, NODE> | R, callback?: C, isReverse?: boolean): ReturnType<C>[];
/**

@@ -835,12 +864,12 @@ * Time Complexity: O(log n)

*
* The function `_getKey` in TypeScript returns the key from a given input, which can be a node,
* The function `_extractKey` in TypeScript returns the key from a given input, which can be a node,
* entry, raw data, or null/undefined.
* @param {BTNRep<K, V, NODE> | R} keyNodeEntryOrRaw - The `_getKey` method you provided is a
* @param {BTNRep<K, V, NODE> | R} keyNodeEntryOrRaw - The `_extractKey` method you provided is a
* TypeScript method that takes in a parameter `keyNodeEntryOrRaw` of type `BTNRep<K, V, NODE> | R`,
* where `BTNRep` is a generic type with keys `K`, `V`, and `NODE`, and `
* @returns The `_getKey` method returns the key value extracted from the `keyNodeEntryOrRaw`
* @returns The `_extractKey` method returns the key value extracted from the `keyNodeEntryOrRaw`
* parameter. The return value can be a key value of type `K`, `null`, or `undefined`, depending on
* the conditions checked in the method.
*/
protected _getKey(keyNodeEntryOrRaw: BTNRep<K, V, NODE> | R): K | null | undefined;
protected _extractKey(keyNodeEntryOrRaw: BTNRep<K, V, NODE> | R): K | null | undefined;
/**

@@ -862,2 +891,5 @@ * Time Complexity: O(1)

/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*
* The _clearNodes function sets the root node to undefined and resets the size to 0.

@@ -867,2 +899,5 @@ */

/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*
* The _clearValues function clears all values stored in the _store object.

@@ -869,0 +904,0 @@ */

136

dist/data-structures/binary-tree/bst.d.ts

@@ -8,5 +8,6 @@ /**

*/
import type { BSTNested, BSTNodeNested, BSTNOptKeyOrNode, BSTOptions, BTNRep, Comparator, CP, DFSOrderPattern, IterationType, NodeCallback, NodePredicate, OptNode } from '../../types';
import type { BSTNested, BSTNodeNested, BSTNOptKeyOrNode, BSTOptions, BTNRep, Comparable, Comparator, CP, DFSOrderPattern, IterationType, NodeCallback, NodePredicate, OptNode } from '../../types';
import { BinaryTree, BinaryTreeNode } from './binary-tree';
import { IBinaryTree } from '../../interfaces';
import { Range } from '../../common';
export declare class BSTNode<K = any, V = any, NODE extends BSTNode<K, V, NODE> = BSTNodeNested<K, V>> extends BinaryTreeNode<K, V, NODE> {

@@ -49,2 +50,50 @@ parent?: NODE;

* 7. No Auto-Balancing: Standard BSTs don't automatically balance themselves.
* @example
* // Find kth smallest element
* // Create a BST with some elements
* const bst = new BST<number>([5, 3, 7, 1, 4, 6, 8]);
* const sortedKeys = bst.dfs(node => node.key, 'IN');
*
* // Helper function to find kth smallest
* const findKthSmallest = (k: number): number | undefined => {
* return sortedKeys[k - 1];
* };
*
* // Assertions
* console.log(findKthSmallest(1)); // 1
* console.log(findKthSmallest(3)); // 4
* console.log(findKthSmallest(7)); // 8
* @example
* // Find elements in a range
* const bst = new BST<number>([10, 5, 15, 3, 7, 12, 18]);
* console.log(bst.search(new Range(5, 10))); // [10, 5, 7]
* console.log(bst.search(new Range(4, 12))); // [10, 12, 5, 7]
* console.log(bst.search(new Range(4, 12, true, false))); // [10, 5, 7]
* console.log(bst.search(new Range(15, 20))); // [15, 18]
* console.log(bst.search(new Range(15, 20, false))); // [18]
* @example
* // Find lowest common ancestor
* const bst = new BST<number>([20, 10, 30, 5, 15, 25, 35, 3, 7, 12, 18]);
*
* function findFirstCommon(arr1: number[], arr2: number[]): number | undefined {
* for (const num of arr1) {
* if (arr2.indexOf(num) !== -1) {
* return num;
* }
* }
* return undefined;
* }
*
* // LCA helper function
* const findLCA = (num1: number, num2: number): number | undefined => {
* const path1 = bst.getPathToRoot(num1);
* const path2 = bst.getPathToRoot(num2);
* // Find the first common ancestor
* return findFirstCommon(path1, path2);
* };
*
* // Assertions
* console.log(findLCA(3, 10)); // 7
* console.log(findLCA(5, 35)); // 15
* console.log(findLCA(20, 30)); // 25
*/

@@ -67,3 +116,10 @@ export declare class BST<K = any, V = any, R = object, NODE extends BSTNode<K, V, NODE> = BSTNode<K, V, BSTNodeNested<K, V>>, TREE extends BST<K, V, R, NODE, TREE> = BST<K, V, R, NODE, BSTNested<K, V, R, NODE>>> extends BinaryTree<K, V, R, NODE, TREE> implements IBinaryTree<K, V, R, NODE, TREE> {

get root(): OptNode<NODE>;
protected _isReverse: boolean;
/**
* The above function is a getter method in TypeScript that returns the value of the private property
* `_isReverse`.
* @returns The `isReverse` property of the object, which is a boolean value.
*/
get isReverse(): boolean;
/**
* The function creates a new BSTNode with the given key and value and returns it.

@@ -124,3 +180,3 @@ * @param {K} key - The key parameter is of type K, which represents the type of the key for the node

* @returns The `override isKey(key: any): key is K` function is returning a boolean value based on
* the result of the `isComparable` function with the condition `this.comparator !==
* the result of the `isComparable` function with the condition `this._compare !==
* this._DEFAULT_COMPARATOR`.

@@ -164,25 +220,40 @@ */

/**
* Time Complexity: O(n)
* Space Complexity: O(1)
*
* The `merge` function overrides the base class method by adding elements from another
* binary search tree.
* @param anotherTree - `anotherTree` is an instance of a Binary Search Tree (BST) with key type `K`,
* value type `V`, return type `R`, node type `NODE`, and tree type `TREE`.
*/
merge(anotherTree: BST<K, V, R, NODE, TREE>): void;
/**
* Time Complexity: O(log n)
* Space Complexity: O(k + log n)
*
* The function `getNodes` in TypeScript overrides the base class method to retrieve nodes based on a
* given keyNodeEntryRawOrPredicate and iteration type.
* @param {BTNRep<K, V, NODE> | R | NodePredicate<NODE>} keyNodeEntryRawOrPredicate - The `keyNodeEntryRawOrPredicate`
* parameter in the `getNodes` method is used to filter the nodes that will be returned. It can be a
* key, a node, an entry, or a custom keyNodeEntryRawOrPredicate function that determines whether a node should be
* included in the result.
* @param [onlyOne=false] - The `onlyOne` parameter in the `getNodes` method is a boolean flag that
* determines whether to return only the first node that matches the keyNodeEntryRawOrPredicate (`true`) or all nodes
* that match the keyNodeEntryRawOrPredicate (`false`). If `onlyOne` is set to `true`, the method will stop iterating
* and
* @param {BTNRep<K, V, NODE> | R} startNode - The `startNode` parameter in the
* `getNodes` method is used to specify the starting point for traversing the tree when searching for
* nodes that match a given keyNodeEntryRawOrPredicate. It represents the root node of the subtree where the search
* should begin. If not explicitly provided, the default value for `begin
* @param {IterationType} iterationType - The `iterationType` parameter in the `getNodes` method
* specifies the type of iteration to be performed when traversing the nodes of a binary tree. It can
* have two possible values:
* @returns The `getNodes` method returns an array of nodes that satisfy the given keyNodeEntryRawOrPredicate.
* The function `search` in TypeScript overrides the search behavior in a binary tree structure based
* on specified criteria.
* @param {BTNRep<K, V, NODE> | R | NodePredicate<NODE>} keyNodeEntryRawOrPredicate - The
* `keyNodeEntryRawOrPredicate` parameter in the `override search` method can accept one of the
* following types:
* @param [onlyOne=false] - The `onlyOne` parameter is a boolean flag that determines whether the
* search should stop after finding the first matching node. If `onlyOne` is set to `true`, the
* search will return as soon as a matching node is found. If `onlyOne` is set to `false`, the
* @param {C} callback - The `callback` parameter in the `override search` function is a function
* that will be called on each node that matches the search criteria. It is of type `C`, which
* extends `NodeCallback<NODE>`. The callback function should accept a node of type `NODE` as its
* argument and
* @param {BTNRep<K, V, NODE> | R} startNode - The `startNode` parameter in the `override search`
* method represents the node from which the search operation will begin. It is the starting point
* for searching within the tree data structure. The method ensures that the `startNode` is a valid
* node before proceeding with the search operation. If the `
* @param {IterationType} iterationType - The `iterationType` parameter in the `override search`
* function determines the type of iteration to be used during the search operation. It can have two
* possible values:
* @returns The `override search` method returns an array of values that match the search criteria
* specified by the input parameters. The method performs a search operation on a binary tree
* structure based on the provided key, predicate, and other options. The search results are
* collected in an array and returned as the output of the method.
*/
getNodes(keyNodeEntryRawOrPredicate: BTNRep<K, V, NODE> | R | NodePredicate<NODE>, onlyOne?: boolean, startNode?: BTNRep<K, V, NODE> | R, iterationType?: IterationType): NODE[];
search<C extends NodeCallback<NODE>>(keyNodeEntryRawOrPredicate: BTNRep<K, V, NODE> | R | NodePredicate<NODE> | Range<K>, onlyOne?: boolean, callback?: C, startNode?: BTNRep<K, V, NODE> | R, iterationType?: IterationType): ReturnType<C>[];
/**

@@ -210,16 +281,2 @@ * Time Complexity: O(log n)

/**
* Time Complexity: O(log n)
* Space Complexity: O(1)
*
* The function `getNodeByKey` returns a node with a specific key from a tree data structure.
* @param {K} key - The key parameter is the value used to search for a specific node in the tree. It
* is typically a unique identifier or a value that can be used to determine the position of the node
* in the tree structure.
* @param {IterationType} [iterationType=ITERATIVE] - The `iterationType` parameter is an optional
* parameter that specifies the type of iteration to be used when searching for a node in the tree.
* It has a default value of `'ITERATIVE'`.
* @returns The method is returning a NODE object or undefined.
*/
getNodeByKey(key: K, iterationType?: IterationType): OptNode<NODE>;
/**
* Time complexity: O(n)

@@ -330,3 +387,2 @@ * Space complexity: O(n)

isAVLBalanced(iterationType?: IterationType): boolean;
protected _DEFAULT_COMPARATOR: (a: K, b: K) => number;
protected _comparator: Comparator<K>;

@@ -338,3 +394,10 @@ /**

get comparator(): Comparator<K>;
protected _extractComparable?: (key: K) => Comparable;
/**
* This function returns the value of the `_extractComparable` property.
* @returns The method `extractComparable()` is being returned, which is a getter method for the
* `_extractComparable` property.
*/
get extractComparable(): ((key: K) => Comparable) | undefined;
/**
* The function sets the root of a tree-like structure and updates the parent property of the new

@@ -345,2 +408,3 @@ * root.

protected _setRoot(v: OptNode<NODE>): void;
protected _compare(a: K, b: K): number;
}

251

dist/data-structures/binary-tree/bst.js

@@ -61,2 +61,50 @@ "use strict";

* 7. No Auto-Balancing: Standard BSTs don't automatically balance themselves.
* @example
* // Find kth smallest element
* // Create a BST with some elements
* const bst = new BST<number>([5, 3, 7, 1, 4, 6, 8]);
* const sortedKeys = bst.dfs(node => node.key, 'IN');
*
* // Helper function to find kth smallest
* const findKthSmallest = (k: number): number | undefined => {
* return sortedKeys[k - 1];
* };
*
* // Assertions
* console.log(findKthSmallest(1)); // 1
* console.log(findKthSmallest(3)); // 4
* console.log(findKthSmallest(7)); // 8
* @example
* // Find elements in a range
* const bst = new BST<number>([10, 5, 15, 3, 7, 12, 18]);
* console.log(bst.search(new Range(5, 10))); // [10, 5, 7]
* console.log(bst.search(new Range(4, 12))); // [10, 12, 5, 7]
* console.log(bst.search(new Range(4, 12, true, false))); // [10, 5, 7]
* console.log(bst.search(new Range(15, 20))); // [15, 18]
* console.log(bst.search(new Range(15, 20, false))); // [18]
* @example
* // Find lowest common ancestor
* const bst = new BST<number>([20, 10, 30, 5, 15, 25, 35, 3, 7, 12, 18]);
*
* function findFirstCommon(arr1: number[], arr2: number[]): number | undefined {
* for (const num of arr1) {
* if (arr2.indexOf(num) !== -1) {
* return num;
* }
* }
* return undefined;
* }
*
* // LCA helper function
* const findLCA = (num1: number, num2: number): number | undefined => {
* const path1 = bst.getPathToRoot(num1);
* const path2 = bst.getPathToRoot(num2);
* // Find the first common ancestor
* return findFirstCommon(path1, path2);
* };
*
* // Assertions
* console.log(findLCA(3, 10)); // 7
* console.log(findLCA(5, 35)); // 15
* console.log(findLCA(20, 30)); // 25
*/

@@ -75,17 +123,29 @@ class BST extends binary_tree_1.BinaryTree {

this._root = undefined;
this._DEFAULT_COMPARATOR = (a, b) => {
this._isReverse = false;
this._comparator = (a, b) => {
if ((0, utils_1.isComparable)(a) && (0, utils_1.isComparable)(b)) {
if (a > b)
return 1;
if (a < b)
return -1;
return 0;
}
if (this._extractComparable) {
if (this._extractComparable(a) > this._extractComparable(b))
return 1;
if (this._extractComparable(a) < this._extractComparable(b))
return -1;
return 0;
}
if (typeof a === 'object' || typeof b === 'object') {
throw TypeError(`When comparing object types, a custom comparator must be defined in the constructor's options parameter.`);
throw TypeError(`When comparing object types, a custom extractComparable must be defined in the constructor's options parameter.`);
}
if (a > b)
return 1;
if (a < b)
return -1;
return 0;
};
this._comparator = this._DEFAULT_COMPARATOR;
if (options) {
const { comparator } = options;
if (comparator)
this._comparator = comparator;
const { extractComparable, isReverse } = options;
if (typeof extractComparable === 'function')
this._extractComparable = extractComparable;
if (isReverse !== undefined)
this._isReverse = isReverse;
}

@@ -103,2 +163,10 @@ if (keysNodesEntriesOrRaws)

/**
* The above function is a getter method in TypeScript that returns the value of the private property
* `_isReverse`.
* @returns The `isReverse` property of the object, which is a boolean value.
*/
get isReverse() {
return this._isReverse;
}
/**
* The function creates a new BSTNode with the given key and value and returns it.

@@ -122,3 +190,3 @@ * @param {K} key - The key parameter is of type K, which represents the type of the key for the node

createTree(options) {
return new BST([], Object.assign({ iterationType: this.iterationType, isMapMode: this._isMapMode, comparator: this._comparator, toEntryFn: this._toEntryFn }, options));
return new BST([], Object.assign({ iterationType: this.iterationType, isMapMode: this._isMapMode, extractComparable: this._extractComparable, toEntryFn: this._toEntryFn, isReverse: this._isReverse }, options));
}

@@ -174,7 +242,7 @@ /**

* @returns The `override isKey(key: any): key is K` function is returning a boolean value based on
* the result of the `isComparable` function with the condition `this.comparator !==
* the result of the `isComparable` function with the condition `this._compare !==
* this._DEFAULT_COMPARATOR`.
*/
isKey(key) {
return (0, utils_1.isComparable)(key, this.comparator !== this._DEFAULT_COMPARATOR);
return (0, utils_1.isComparable)(key, this._extractComparable !== undefined);
}

@@ -205,3 +273,3 @@ /**

while (current !== undefined) {
if (this.comparator(current.key, newNode.key) === 0) {
if (this._compare(current.key, newNode.key) === 0) {
this._replaceNode(current, newNode);

@@ -212,3 +280,3 @@ if (this._isMapMode)

}
else if (this.comparator(current.key, newNode.key) > 0) {
else if (this._compare(current.key, newNode.key) > 0) {
if (current.left === undefined) {

@@ -300,3 +368,3 @@ current.left = newNode;

if (keyA !== undefined && keyA !== null && keyB !== undefined && keyB !== null) {
return this.comparator(keyA, keyB);
return this._compare(keyA, keyB);
}

@@ -340,25 +408,42 @@ return 0;

/**
* Time Complexity: O(n)
* Space Complexity: O(1)
*
* The `merge` function overrides the base class method by adding elements from another
* binary search tree.
* @param anotherTree - `anotherTree` is an instance of a Binary Search Tree (BST) with key type `K`,
* value type `V`, return type `R`, node type `NODE`, and tree type `TREE`.
*/
merge(anotherTree) {
this.addMany(anotherTree, [], false);
}
/**
* Time Complexity: O(log n)
* Space Complexity: O(k + log n)
*
* The function `getNodes` in TypeScript overrides the base class method to retrieve nodes based on a
* given keyNodeEntryRawOrPredicate and iteration type.
* @param {BTNRep<K, V, NODE> | R | NodePredicate<NODE>} keyNodeEntryRawOrPredicate - The `keyNodeEntryRawOrPredicate`
* parameter in the `getNodes` method is used to filter the nodes that will be returned. It can be a
* key, a node, an entry, or a custom keyNodeEntryRawOrPredicate function that determines whether a node should be
* included in the result.
* @param [onlyOne=false] - The `onlyOne` parameter in the `getNodes` method is a boolean flag that
* determines whether to return only the first node that matches the keyNodeEntryRawOrPredicate (`true`) or all nodes
* that match the keyNodeEntryRawOrPredicate (`false`). If `onlyOne` is set to `true`, the method will stop iterating
* and
* @param {BTNRep<K, V, NODE> | R} startNode - The `startNode` parameter in the
* `getNodes` method is used to specify the starting point for traversing the tree when searching for
* nodes that match a given keyNodeEntryRawOrPredicate. It represents the root node of the subtree where the search
* should begin. If not explicitly provided, the default value for `begin
* @param {IterationType} iterationType - The `iterationType` parameter in the `getNodes` method
* specifies the type of iteration to be performed when traversing the nodes of a binary tree. It can
* have two possible values:
* @returns The `getNodes` method returns an array of nodes that satisfy the given keyNodeEntryRawOrPredicate.
* The function `search` in TypeScript overrides the search behavior in a binary tree structure based
* on specified criteria.
* @param {BTNRep<K, V, NODE> | R | NodePredicate<NODE>} keyNodeEntryRawOrPredicate - The
* `keyNodeEntryRawOrPredicate` parameter in the `override search` method can accept one of the
* following types:
* @param [onlyOne=false] - The `onlyOne` parameter is a boolean flag that determines whether the
* search should stop after finding the first matching node. If `onlyOne` is set to `true`, the
* search will return as soon as a matching node is found. If `onlyOne` is set to `false`, the
* @param {C} callback - The `callback` parameter in the `override search` function is a function
* that will be called on each node that matches the search criteria. It is of type `C`, which
* extends `NodeCallback<NODE>`. The callback function should accept a node of type `NODE` as its
* argument and
* @param {BTNRep<K, V, NODE> | R} startNode - The `startNode` parameter in the `override search`
* method represents the node from which the search operation will begin. It is the starting point
* for searching within the tree data structure. The method ensures that the `startNode` is a valid
* node before proceeding with the search operation. If the `
* @param {IterationType} iterationType - The `iterationType` parameter in the `override search`
* function determines the type of iteration to be used during the search operation. It can have two
* possible values:
* @returns The `override search` method returns an array of values that match the search criteria
* specified by the input parameters. The method performs a search operation on a binary tree
* structure based on the provided key, predicate, and other options. The search results are
* collected in an array and returned as the output of the method.
*/
getNodes(keyNodeEntryRawOrPredicate, onlyOne = false, startNode = this._root, iterationType = this.iterationType) {
search(keyNodeEntryRawOrPredicate, onlyOne = false, callback = this._DEFAULT_NODE_CALLBACK, startNode = this._root, iterationType = this.iterationType) {
if (keyNodeEntryRawOrPredicate === undefined)

@@ -371,8 +456,34 @@ return [];

return [];
const callback = this._ensurePredicate(keyNodeEntryRawOrPredicate);
let predicate;
const isRange = this.isRange(keyNodeEntryRawOrPredicate);
// Set predicate based on parameter type
if (isRange) {
predicate = node => keyNodeEntryRawOrPredicate.isInRange(node.key, this._comparator);
}
else {
predicate = this._ensurePredicate(keyNodeEntryRawOrPredicate);
}
const isToLeftByRange = (cur) => {
if (isRange) {
const range = keyNodeEntryRawOrPredicate;
const leftS = this.isReverse ? range.high : range.low;
const leftI = this.isReverse ? range.includeHigh : range.includeLow;
return (leftI && this._compare(cur.key, leftS) >= 0) || (!leftI && this._compare(cur.key, leftS) > 0);
}
return false;
};
const isToRightByRange = (cur) => {
if (isRange) {
const range = keyNodeEntryRawOrPredicate;
const rightS = this.isReverse ? range.low : range.high;
const rightI = this.isReverse ? range.includeLow : range.includeLow;
return (rightI && this._compare(cur.key, rightS) <= 0) || (!rightI && this._compare(cur.key, rightS) < 0);
}
return false;
};
const ans = [];
if (iterationType === 'RECURSIVE') {
const dfs = (cur) => {
if (callback(cur)) {
ans.push(cur);
if (predicate(cur)) {
ans.push(callback(cur));
if (onlyOne)

@@ -383,8 +494,14 @@ return;

return;
if (!this._isPredicate(keyNodeEntryRawOrPredicate)) {
const benchmarkKey = this._getKey(keyNodeEntryRawOrPredicate);
if (isRange) {
if (this.isRealNode(cur.left) && isToLeftByRange(cur))
dfs(cur.left);
if (this.isRealNode(cur.right) && isToRightByRange(cur))
dfs(cur.right);
}
else if (!this._isPredicate(keyNodeEntryRawOrPredicate)) {
const benchmarkKey = this._extractKey(keyNodeEntryRawOrPredicate);
if (this.isRealNode(cur.left) &&
benchmarkKey !== null &&
benchmarkKey !== undefined &&
this.comparator(cur.key, benchmarkKey) > 0)
this._compare(cur.key, benchmarkKey) > 0)
dfs(cur.left);

@@ -394,3 +511,3 @@ if (this.isRealNode(cur.right) &&

benchmarkKey !== undefined &&
this.comparator(cur.key, benchmarkKey) < 0)
this._compare(cur.key, benchmarkKey) < 0)
dfs(cur.right);

@@ -411,13 +528,19 @@ }

const cur = stack.pop();
if (callback(cur)) {
ans.push(cur);
if (predicate(cur)) {
ans.push(callback(cur));
if (onlyOne)
return ans;
}
if (!this._isPredicate(keyNodeEntryRawOrPredicate)) {
const benchmarkKey = this._getKey(keyNodeEntryRawOrPredicate);
if (isRange) {
if (this.isRealNode(cur.left) && isToLeftByRange(cur))
stack.push(cur.left);
if (this.isRealNode(cur.right) && isToRightByRange(cur))
stack.push(cur.right);
}
else if (!this._isPredicate(keyNodeEntryRawOrPredicate)) {
const benchmarkKey = this._extractKey(keyNodeEntryRawOrPredicate);
if (this.isRealNode(cur.right) &&
benchmarkKey !== null &&
benchmarkKey !== undefined &&
this.comparator(cur.key, benchmarkKey) < 0)
this._compare(cur.key, benchmarkKey) < 0)
stack.push(cur.right);

@@ -427,3 +550,3 @@ if (this.isRealNode(cur.left) &&

benchmarkKey !== undefined &&
this.comparator(cur.key, benchmarkKey) > 0)
this._compare(cur.key, benchmarkKey) > 0)
stack.push(cur.left);

@@ -466,18 +589,2 @@ }

/**
* Time Complexity: O(log n)
* Space Complexity: O(1)
*
* The function `getNodeByKey` returns a node with a specific key from a tree data structure.
* @param {K} key - The key parameter is the value used to search for a specific node in the tree. It
* is typically a unique identifier or a value that can be used to determine the position of the node
* in the tree structure.
* @param {IterationType} [iterationType=ITERATIVE] - The `iterationType` parameter is an optional
* parameter that specifies the type of iteration to be used when searching for a node in the tree.
* It has a default value of `'ITERATIVE'`.
* @returns The method is returning a NODE object or undefined.
*/
getNodeByKey(key, iterationType = this.iterationType) {
return this.getNode(key, this._root, iterationType);
}
/**
* Time complexity: O(n)

@@ -577,5 +684,6 @@ * Space complexity: O(n)

const dfs = (cur) => {
const compared = this.comparator(cur.key, targetKey);
const compared = this._compare(cur.key, targetKey);
if (Math.sign(compared) === lesserOrGreater)
ans.push(callback(cur));
// TODO here can be optimized to O(log n)
if (this.isRealNode(cur.left))

@@ -594,3 +702,3 @@ dfs(cur.left);

if (this.isRealNode(cur)) {
const compared = this.comparator(cur.key, targetKey);
const compared = this._compare(cur.key, targetKey);
if (Math.sign(compared) === lesserOrGreater)

@@ -726,2 +834,10 @@ ans.push(callback(cur));

/**
* This function returns the value of the `_extractComparable` property.
* @returns The method `extractComparable()` is being returned, which is a getter method for the
* `_extractComparable` property.
*/
get extractComparable() {
return this._extractComparable;
}
/**
* The function sets the root of a tree-like structure and updates the parent property of the new

@@ -737,3 +853,6 @@ * root.

}
_compare(a, b) {
return this._isReverse ? -this._comparator(a, b) : this._comparator(a, b);
}
}
exports.BST = BST;

4

dist/data-structures/binary-tree/rb-tree.d.ts

@@ -29,2 +29,6 @@ import type { BinaryTreeDeleteResult, BTNRep, CRUD, RBTNColor, RBTreeOptions, RedBlackTreeNested, RedBlackTreeNodeNested } from '../../types';

}
/**
* 1. Efficient self-balancing, but not completely balanced. Compared with AVLTree, the addition and deletion efficiency is high but the query efficiency is slightly lower.
* 2. It is BST itself. Compared with Heap which is not completely ordered, RedBlackTree is completely ordered.
*/
export declare class RedBlackTree<K = any, V = any, R = object, NODE extends RedBlackTreeNode<K, V, NODE> = RedBlackTreeNode<K, V, RedBlackTreeNodeNested<K, V>>, TREE extends RedBlackTree<K, V, R, NODE, TREE> = RedBlackTree<K, V, R, NODE, RedBlackTreeNested<K, V, R, NODE>>> extends BST<K, V, R, NODE, TREE> implements IBinaryTree<K, V, R, NODE, TREE> {

@@ -31,0 +35,0 @@ /**

8

dist/data-structures/binary-tree/rb-tree.js

@@ -37,2 +37,6 @@ "use strict";

exports.RedBlackTreeNode = RedBlackTreeNode;
/**
* 1. Efficient self-balancing, but not completely balanced. Compared with AVLTree, the addition and deletion efficiency is high but the query efficiency is slightly lower.
* 2. It is BST itself. Compared with Heap which is not completely ordered, RedBlackTree is completely ordered.
*/
class RedBlackTree extends bst_1.BST {

@@ -87,3 +91,3 @@ /**

createTree(options) {
return new RedBlackTree([], Object.assign({ iterationType: this.iterationType, isMapMode: this._isMapMode, comparator: this._comparator, toEntryFn: this._toEntryFn }, options));
return new RedBlackTree([], Object.assign({ iterationType: this.iterationType, isMapMode: this._isMapMode, extractComparable: this._extractComparable, toEntryFn: this._toEntryFn }, options));
}

@@ -308,3 +312,3 @@ /**

parent = current;
const compared = this.comparator(node.key, current.key);
const compared = this._compare(node.key, current.key);
if (compared < 0) {

@@ -311,0 +315,0 @@ current = (_a = current.left) !== null && _a !== void 0 ? _a : this.NIL;

4

dist/data-structures/binary-tree/tree-multi-map.js

@@ -102,3 +102,3 @@ "use strict";

createTree(options) {
return new TreeMultiMap([], Object.assign({ iterationType: this.iterationType, isMapMode: this._isMapMode, comparator: this._comparator, toEntryFn: this._toEntryFn }, options));
return new TreeMultiMap([], Object.assign({ iterationType: this.iterationType, isMapMode: this._isMapMode, extractComparable: this._extractComparable, toEntryFn: this._toEntryFn }, options));
}

@@ -130,3 +130,3 @@ /**

}
if (this._toEntryFn) {
if (this.isRaw(keyNodeEntryOrRaw)) {
const [key, entryValue] = this._toEntryFn(keyNodeEntryOrRaw);

@@ -133,0 +133,0 @@ const finalValue = value !== null && value !== void 0 ? value : entryValue;

12

dist/data-structures/heap/heap.d.ts

@@ -22,3 +22,3 @@ /**

* // Use Heap to sort an array
* function heapSort(arr: number[]): number[] {
* function heapSort(arr: number[]): number[] {
* const heap = new Heap<number>(arr, { comparator: (a, b) => a - b });

@@ -36,3 +36,3 @@ * const sorted: number[] = [];

* // Use Heap to solve top k problems
* function topKElements(arr: number[], k: number): number[] {
* function topKElements(arr: number[], k: number): number[] {
* const heap = new Heap<number>([], { comparator: (a, b) => b - a }); // Max heap

@@ -50,3 +50,3 @@ * arr.forEach(num => {

* // Use Heap to merge sorted sequences
* function mergeSortedSequences(sequences: number[][]): number[] {
* function mergeSortedSequences(sequences: number[][]): number[] {
* const heap = new Heap<{ value: number; seqIndex: number; itemIndex: number }>([], {

@@ -88,3 +88,3 @@ * comparator: (a, b) => a.value - b.value // Min heap

* // Use Heap to dynamically maintain the median
* class MedianFinder {
* class MedianFinder {
* private low: MaxHeap<number>; // Max heap, stores the smaller half

@@ -126,3 +126,3 @@ * private high: MinHeap<number>; // Min heap, stores the larger half

* // Use Heap for load balancing
* function loadBalance(requests: number[], servers: number): number[] {
* function loadBalance(requests: number[], servers: number): number[] {
* const serverHeap = new Heap<{ id: number; load: number }>([], { comparator: (a, b) => a.load - b.load }); // min heap

@@ -149,3 +149,3 @@ * const serverLoads = new Array(servers).fill(0);

* // Use Heap to schedule tasks
* type Task = [string, number];
* type Task = [string, number];
*

@@ -152,0 +152,0 @@ * function scheduleTasks(tasks: Task[], machines: number): Map<number, Task[]> {

12

dist/data-structures/heap/heap.js

@@ -24,3 +24,3 @@ "use strict";

* // Use Heap to sort an array
* function heapSort(arr: number[]): number[] {
* function heapSort(arr: number[]): number[] {
* const heap = new Heap<number>(arr, { comparator: (a, b) => a - b });

@@ -38,3 +38,3 @@ * const sorted: number[] = [];

* // Use Heap to solve top k problems
* function topKElements(arr: number[], k: number): number[] {
* function topKElements(arr: number[], k: number): number[] {
* const heap = new Heap<number>([], { comparator: (a, b) => b - a }); // Max heap

@@ -52,3 +52,3 @@ * arr.forEach(num => {

* // Use Heap to merge sorted sequences
* function mergeSortedSequences(sequences: number[][]): number[] {
* function mergeSortedSequences(sequences: number[][]): number[] {
* const heap = new Heap<{ value: number; seqIndex: number; itemIndex: number }>([], {

@@ -90,3 +90,3 @@ * comparator: (a, b) => a.value - b.value // Min heap

* // Use Heap to dynamically maintain the median
* class MedianFinder {
* class MedianFinder {
* private low: MaxHeap<number>; // Max heap, stores the smaller half

@@ -128,3 +128,3 @@ * private high: MinHeap<number>; // Min heap, stores the larger half

* // Use Heap for load balancing
* function loadBalance(requests: number[], servers: number): number[] {
* function loadBalance(requests: number[], servers: number): number[] {
* const serverHeap = new Heap<{ id: number; load: number }>([], { comparator: (a, b) => a.load - b.load }); // min heap

@@ -151,3 +151,3 @@ * const serverLoads = new Array(servers).fill(0);

* // Use Heap to schedule tasks
* type Task = [string, number];
* type Task = [string, number];
*

@@ -154,0 +154,0 @@ * function scheduleTasks(tasks: Task[], machines: number): Map<number, Task[]> {

26

dist/data-structures/linked-list/doubly-linked-list.d.ts

@@ -58,3 +58,3 @@ /**

/**
* 1. Node Structure: Each node contains three parts: a data field, a pointer (or reference) to the previous node, and a pointer to the next node. This structure allows traversal of the linked list in both directions.
*1. Node Structure: Each node contains three parts: a data field, a pointer (or reference) to the previous node, and a pointer to the next node. This structure allows traversal of the linked list in both directions.
* 2. Bidirectional Traversal: Unlike singly linked lists, doubly linked lists can be easily traversed forwards or backwards. This makes insertions and deletions in the list more flexible and efficient.

@@ -65,3 +65,3 @@ * 3. No Centralized Index: Unlike arrays, elements in a linked list are not stored contiguously, so there is no centralized index. Accessing elements in a linked list typically requires traversing from the head or tail node.

* // text editor operation history
* const actions = [
* const actions = [
* { type: 'insert', content: 'first line of text' },

@@ -78,3 +78,3 @@ * { type: 'insert', content: 'second line of text' },

* // Browser history
* const browserHistory = new DoublyLinkedList<string>();
* const browserHistory = new DoublyLinkedList<string>();
*

@@ -90,3 +90,3 @@ * browserHistory.push('home page');

* // Use DoublyLinkedList to implement music player
* // Define the Song interface
* // Define the Song interface
* interface Song {

@@ -216,3 +216,3 @@ * title: string;

* // Use DoublyLinkedList to implement LRU cache
* interface CacheEntry<K, V> {
* interface CacheEntry<K, V> {
* key: K;

@@ -379,3 +379,3 @@ * value: V;

* // finding lyrics by timestamp in Coldplay's "Fix You"
* // Create a DoublyLinkedList to store song lyrics with timestamps
* // Create a DoublyLinkedList to store song lyrics with timestamps
* const lyricsList = new DoublyLinkedList<{ time: number; text: string }>();

@@ -420,3 +420,3 @@ *

* // cpu process schedules
* class Process {
* class Process {
* constructor(

@@ -497,2 +497,12 @@ * public id: number,

export declare class DoublyLinkedList<E = any, R = any> extends IterableElementBase<E, R, DoublyLinkedList<E, R>> {
/**
* This TypeScript constructor initializes a DoublyLinkedList with optional elements and options.
* @param {Iterable<E> | Iterable<R>} elements - The `elements` parameter in the constructor is an
* iterable collection of elements of type `E` or `R`. It is used to initialize the DoublyLinkedList
* with the elements provided in the iterable. If no elements are provided, the default value is an
* empty iterable.
* @param [options] - The `options` parameter in the constructor is of type
* `DoublyLinkedListOptions<E, R>`. It is an optional parameter that allows you to pass additional
* configuration options to customize the behavior of the DoublyLinkedList.
*/
constructor(elements?: Iterable<E> | Iterable<R>, options?: DoublyLinkedListOptions<E, R>);

@@ -740,3 +750,3 @@ protected _head: DoublyLinkedListNode<E> | undefined;

*/
get(elementNodeOrPredicate: E | DoublyLinkedListNode<E> | ((node: DoublyLinkedListNode<E>) => boolean)): E | undefined;
search(elementNodeOrPredicate: E | DoublyLinkedListNode<E> | ((node: DoublyLinkedListNode<E>) => boolean)): E | undefined;
/**

@@ -743,0 +753,0 @@ * Time Complexity: O(n)

34

dist/data-structures/linked-list/doubly-linked-list.js

@@ -67,3 +67,3 @@ "use strict";

/**
* 1. Node Structure: Each node contains three parts: a data field, a pointer (or reference) to the previous node, and a pointer to the next node. This structure allows traversal of the linked list in both directions.
*1. Node Structure: Each node contains three parts: a data field, a pointer (or reference) to the previous node, and a pointer to the next node. This structure allows traversal of the linked list in both directions.
* 2. Bidirectional Traversal: Unlike singly linked lists, doubly linked lists can be easily traversed forwards or backwards. This makes insertions and deletions in the list more flexible and efficient.

@@ -74,3 +74,3 @@ * 3. No Centralized Index: Unlike arrays, elements in a linked list are not stored contiguously, so there is no centralized index. Accessing elements in a linked list typically requires traversing from the head or tail node.

* // text editor operation history
* const actions = [
* const actions = [
* { type: 'insert', content: 'first line of text' },

@@ -87,3 +87,3 @@ * { type: 'insert', content: 'second line of text' },

* // Browser history
* const browserHistory = new DoublyLinkedList<string>();
* const browserHistory = new DoublyLinkedList<string>();
*

@@ -99,3 +99,3 @@ * browserHistory.push('home page');

* // Use DoublyLinkedList to implement music player
* // Define the Song interface
* // Define the Song interface
* interface Song {

@@ -225,3 +225,3 @@ * title: string;

* // Use DoublyLinkedList to implement LRU cache
* interface CacheEntry<K, V> {
* interface CacheEntry<K, V> {
* key: K;

@@ -388,3 +388,3 @@ * value: V;

* // finding lyrics by timestamp in Coldplay's "Fix You"
* // Create a DoublyLinkedList to store song lyrics with timestamps
* // Create a DoublyLinkedList to store song lyrics with timestamps
* const lyricsList = new DoublyLinkedList<{ time: number; text: string }>();

@@ -429,3 +429,3 @@ *

* // cpu process schedules
* class Process {
* class Process {
* constructor(

@@ -506,2 +506,12 @@ * public id: number,

class DoublyLinkedList extends base_1.IterableElementBase {
/**
* This TypeScript constructor initializes a DoublyLinkedList with optional elements and options.
* @param {Iterable<E> | Iterable<R>} elements - The `elements` parameter in the constructor is an
* iterable collection of elements of type `E` or `R`. It is used to initialize the DoublyLinkedList
* with the elements provided in the iterable. If no elements are provided, the default value is an
* empty iterable.
* @param [options] - The `options` parameter in the constructor is of type
* `DoublyLinkedListOptions<E, R>`. It is an optional parameter that allows you to pass additional
* configuration options to customize the behavior of the DoublyLinkedList.
*/
constructor(elements = [], options) {

@@ -795,3 +805,5 @@ super(options);

addBefore(existingElementOrNode, newElementOrNode) {
const existingNode = this.getNode(existingElementOrNode);
const existingNode = this.isNode(existingElementOrNode)
? existingElementOrNode
: this.getNode(existingElementOrNode);
if (existingNode) {

@@ -830,3 +842,5 @@ const newNode = this._ensureNode(newElementOrNode);

addAfter(existingElementOrNode, newElementOrNode) {
const existingNode = this.getNode(existingElementOrNode);
const existingNode = this.isNode(existingElementOrNode)
? existingElementOrNode
: this.getNode(existingElementOrNode);
if (existingNode) {

@@ -969,3 +983,3 @@ const newNode = this._ensureNode(newElementOrNode);

*/
get(elementNodeOrPredicate) {
search(elementNodeOrPredicate) {
const predicate = this._ensurePredicate(elementNodeOrPredicate);

@@ -972,0 +986,0 @@ let current = this.head;

2

dist/data-structures/linked-list/singly-linked-list.d.ts

@@ -126,3 +126,3 @@ /**

*/
get(elementNodeOrPredicate: E | SinglyLinkedListNode<E> | ((node: SinglyLinkedListNode<E>) => boolean)): E | undefined;
search(elementNodeOrPredicate: E | SinglyLinkedListNode<E> | ((node: SinglyLinkedListNode<E>) => boolean)): E | undefined;
/**

@@ -129,0 +129,0 @@ * Time Complexity: O(n)

2

dist/data-structures/linked-list/singly-linked-list.js

@@ -203,3 +203,3 @@ "use strict";

*/
get(elementNodeOrPredicate) {
search(elementNodeOrPredicate) {
const predicate = this._ensurePredicate(elementNodeOrPredicate);

@@ -206,0 +206,0 @@ let current = this.head;

108

dist/data-structures/trie/trie.d.ts

@@ -68,9 +68,96 @@ /**

* 11. Text Word Frequency Count: Counting and storing the frequency of words in a large amount of text data.
* @example
* // Autocomplete: Prefix validation and checking
* const autocomplete = new Trie<string>(['gmail.com', 'gmail.co.nz', 'gmail.co.jp', 'yahoo.com', 'outlook.com']);
*
* // Get all completions for a prefix
* const gmailCompletions = autocomplete.getWords('gmail');
* console.log(gmailCompletions); // ['gmail.com', 'gmail.co.nz', 'gmail.co.jp']
* @example
* // File System Path Operations
* const fileSystem = new Trie<string>([
* '/home/user/documents/file1.txt',
* '/home/user/documents/file2.txt',
* '/home/user/pictures/photo.jpg',
* '/home/user/pictures/vacation/',
* '/home/user/downloads'
* ]);
*
* // Find common directory prefix
* console.log(fileSystem.getLongestCommonPrefix()); // '/home/user/'
*
* // List all files in a directory
* const documentsFiles = fileSystem.getWords('/home/user/documents/');
* console.log(documentsFiles); // ['/home/user/documents/file1.txt', '/home/user/documents/file2.txt']
* @example
* // Autocomplete: Basic word suggestions
* // Create a trie for autocomplete
* const autocomplete = new Trie<string>([
* 'function',
* 'functional',
* 'functions',
* 'class',
* 'classes',
* 'classical',
* 'closure',
* 'const',
* 'constructor'
* ]);
*
* // Test autocomplete with different prefixes
* console.log(autocomplete.getWords('fun')); // ['functional', 'functions', 'function']
* console.log(autocomplete.getWords('cla')); // ['classes', 'classical', 'class']
* console.log(autocomplete.getWords('con')); // ['constructor', 'const']
*
* // Test with non-matching prefix
* console.log(autocomplete.getWords('xyz')); // []
* @example
* // Dictionary: Case-insensitive word lookup
* // Create a case-insensitive dictionary
* const dictionary = new Trie<string>([], { caseSensitive: false });
*
* // Add words with mixed casing
* dictionary.add('Hello');
* dictionary.add('WORLD');
* dictionary.add('JavaScript');
*
* // Test lookups with different casings
* console.log(dictionary.has('hello')); // true
* console.log(dictionary.has('HELLO')); // true
* console.log(dictionary.has('Hello')); // true
* console.log(dictionary.has('javascript')); // true
* console.log(dictionary.has('JAVASCRIPT')); // true
* @example
* // IP Address Routing Table
* // Add IP address prefixes and their corresponding routes
* const routes = {
* '192.168.1': 'LAN_SUBNET_1',
* '192.168.2': 'LAN_SUBNET_2',
* '10.0.0': 'PRIVATE_NETWORK_1',
* '10.0.1': 'PRIVATE_NETWORK_2'
* };
*
* const ipRoutingTable = new Trie<string>(Object.keys(routes));
*
* // Check IP address prefix matching
* console.log(ipRoutingTable.hasPrefix('192.168.1')); // true
* console.log(ipRoutingTable.hasPrefix('192.168.2')); // true
*
* // Validate IP address belongs to subnet
* const ip = '192.168.1.100';
* const subnet = ip.split('.').slice(0, 3).join('.');
* console.log(ipRoutingTable.hasPrefix(subnet)); // true
*/
export declare class Trie<R = any> extends IterableElementBase<string, R, Trie<R>> {
/**
* The constructor function for the Trie class.
* @param words: Iterable string Initialize the trie with a set of words
* @param options?: TrieOptions Allow the user to pass in options for the trie
* @return This
* The constructor initializes a Trie data structure with optional options and words provided as
* input.
* @param {Iterable<string> | Iterable<R>} words - The `words` parameter in the constructor is an
* iterable containing either strings or elements of type `R`. It is used to initialize the Trie with
* a list of words or elements. If no `words` are provided, an empty iterable is used as the default
* value.
* @param [options] - The `options` parameter in the constructor is an optional object that can
* contain configuration options for the Trie data structure. One of the options it can have is
* `caseSensitive`, which is a boolean value indicating whether the Trie should be case-sensitive or
* not. If `caseSensitive` is set to `
*/

@@ -106,2 +193,15 @@ constructor(words?: Iterable<string> | Iterable<R>, options?: TrieOptions<R>);

/**
* Time Complexity: O(n * l)
* Space Complexity: O(1)
*
* The `addMany` function in TypeScript takes an iterable of strings or elements of type R, converts
* them using a provided function if available, and adds them to a data structure while returning an
* array of boolean values indicating success.
* @param {Iterable<string> | Iterable<R>} words - The `words` parameter in the `addMany` function is
* an iterable that contains either strings or elements of type `R`.
* @returns The `addMany` method returns an array of boolean values indicating whether each word in
* the input iterable was successfully added to the data structure.
*/
addMany(words?: Iterable<string> | Iterable<R>): boolean[];
/**
* Time Complexity: O(l), where l is the length of the input word.

@@ -108,0 +208,0 @@ * Space Complexity: O(1) - Constant space.

128

dist/data-structures/trie/trie.js

@@ -77,9 +77,96 @@ "use strict";

* 11. Text Word Frequency Count: Counting and storing the frequency of words in a large amount of text data.
* @example
* // Autocomplete: Prefix validation and checking
* const autocomplete = new Trie<string>(['gmail.com', 'gmail.co.nz', 'gmail.co.jp', 'yahoo.com', 'outlook.com']);
*
* // Get all completions for a prefix
* const gmailCompletions = autocomplete.getWords('gmail');
* console.log(gmailCompletions); // ['gmail.com', 'gmail.co.nz', 'gmail.co.jp']
* @example
* // File System Path Operations
* const fileSystem = new Trie<string>([
* '/home/user/documents/file1.txt',
* '/home/user/documents/file2.txt',
* '/home/user/pictures/photo.jpg',
* '/home/user/pictures/vacation/',
* '/home/user/downloads'
* ]);
*
* // Find common directory prefix
* console.log(fileSystem.getLongestCommonPrefix()); // '/home/user/'
*
* // List all files in a directory
* const documentsFiles = fileSystem.getWords('/home/user/documents/');
* console.log(documentsFiles); // ['/home/user/documents/file1.txt', '/home/user/documents/file2.txt']
* @example
* // Autocomplete: Basic word suggestions
* // Create a trie for autocomplete
* const autocomplete = new Trie<string>([
* 'function',
* 'functional',
* 'functions',
* 'class',
* 'classes',
* 'classical',
* 'closure',
* 'const',
* 'constructor'
* ]);
*
* // Test autocomplete with different prefixes
* console.log(autocomplete.getWords('fun')); // ['functional', 'functions', 'function']
* console.log(autocomplete.getWords('cla')); // ['classes', 'classical', 'class']
* console.log(autocomplete.getWords('con')); // ['constructor', 'const']
*
* // Test with non-matching prefix
* console.log(autocomplete.getWords('xyz')); // []
* @example
* // Dictionary: Case-insensitive word lookup
* // Create a case-insensitive dictionary
* const dictionary = new Trie<string>([], { caseSensitive: false });
*
* // Add words with mixed casing
* dictionary.add('Hello');
* dictionary.add('WORLD');
* dictionary.add('JavaScript');
*
* // Test lookups with different casings
* console.log(dictionary.has('hello')); // true
* console.log(dictionary.has('HELLO')); // true
* console.log(dictionary.has('Hello')); // true
* console.log(dictionary.has('javascript')); // true
* console.log(dictionary.has('JAVASCRIPT')); // true
* @example
* // IP Address Routing Table
* // Add IP address prefixes and their corresponding routes
* const routes = {
* '192.168.1': 'LAN_SUBNET_1',
* '192.168.2': 'LAN_SUBNET_2',
* '10.0.0': 'PRIVATE_NETWORK_1',
* '10.0.1': 'PRIVATE_NETWORK_2'
* };
*
* const ipRoutingTable = new Trie<string>(Object.keys(routes));
*
* // Check IP address prefix matching
* console.log(ipRoutingTable.hasPrefix('192.168.1')); // true
* console.log(ipRoutingTable.hasPrefix('192.168.2')); // true
*
* // Validate IP address belongs to subnet
* const ip = '192.168.1.100';
* const subnet = ip.split('.').slice(0, 3).join('.');
* console.log(ipRoutingTable.hasPrefix(subnet)); // true
*/
class Trie extends base_1.IterableElementBase {
/**
* The constructor function for the Trie class.
* @param words: Iterable string Initialize the trie with a set of words
* @param options?: TrieOptions Allow the user to pass in options for the trie
* @return This
* The constructor initializes a Trie data structure with optional options and words provided as
* input.
* @param {Iterable<string> | Iterable<R>} words - The `words` parameter in the constructor is an
* iterable containing either strings or elements of type `R`. It is used to initialize the Trie with
* a list of words or elements. If no `words` are provided, an empty iterable is used as the default
* value.
* @param [options] - The `options` parameter in the constructor is an optional object that can
* contain configuration options for the Trie data structure. One of the options it can have is
* `caseSensitive`, which is a boolean value indicating whether the Trie should be case-sensitive or
* not. If `caseSensitive` is set to `
*/

@@ -97,10 +184,3 @@ constructor(words = [], options) {

if (words) {
for (const word of words) {
if (this.toElementFn) {
this.add(this.toElementFn(word));
}
else {
this.add(word);
}
}
this.addMany(words);
}

@@ -157,2 +237,26 @@ }

/**
* Time Complexity: O(n * l)
* Space Complexity: O(1)
*
* The `addMany` function in TypeScript takes an iterable of strings or elements of type R, converts
* them using a provided function if available, and adds them to a data structure while returning an
* array of boolean values indicating success.
* @param {Iterable<string> | Iterable<R>} words - The `words` parameter in the `addMany` function is
* an iterable that contains either strings or elements of type `R`.
* @returns The `addMany` method returns an array of boolean values indicating whether each word in
* the input iterable was successfully added to the data structure.
*/
addMany(words = []) {
const ans = [];
for (const word of words) {
if (this.toElementFn) {
ans.push(this.add(this.toElementFn(word)));
}
else {
ans.push(this.add(word));
}
}
return ans;
}
/**
* Time Complexity: O(l), where l is the length of the input word.

@@ -159,0 +263,0 @@ * Space Complexity: O(1) - Constant space.

3

dist/index.d.ts

@@ -11,2 +11,3 @@ /**

export * from './types/common';
export * from './constants';
export * from './types/utils';
export * from './common';

3

dist/index.js

@@ -28,2 +28,3 @@ "use strict";

__exportStar(require("./types/common"), exports);
__exportStar(require("./constants"), exports);
__exportStar(require("./types/utils"), exports);
__exportStar(require("./common"), exports);

2

dist/types/data-structures/binary-tree/binary-tree.d.ts
import { BinaryTree, BinaryTreeNode } from '../../../data-structures';
import { IterationType, OptValue } from '../../common';
import { DFSOperation } from '../../../constants';
import { DFSOperation } from '../../../common';
export type BinaryTreeNodeNested<K, V> = BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, any>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>;

@@ -5,0 +5,0 @@ export type BinaryTreeNested<K, V, R, NODE extends BinaryTreeNode<K, V, NODE>> = BinaryTree<K, V, R, NODE, BinaryTree<K, V, R, NODE, BinaryTree<K, V, R, NODE, BinaryTree<K, V, R, NODE, BinaryTree<K, V, R, NODE, BinaryTree<K, V, R, NODE, BinaryTree<K, V, R, NODE, BinaryTree<K, V, R, NODE, BinaryTree<K, V, R, NODE, BinaryTree<K, V, R, NODE, BinaryTree<K, V, R, NODE, BinaryTree<K, V, R, NODE, BinaryTree<K, V, R, NODE, BinaryTree<K, V, R, NODE, BinaryTree<K, V, R, NODE, BinaryTree<K, V, R, NODE, BinaryTree<K, V, R, NODE, BinaryTree<K, V, R, NODE, BinaryTree<K, V, R, NODE, BinaryTree<K, V, R, NODE, BinaryTree<K, V, R, NODE, BinaryTree<K, V, R, NODE, BinaryTree<K, V, R, NODE, BinaryTree<K, V, R, NODE, BinaryTree<K, V, R, NODE, BinaryTree<K, V, R, NODE, BinaryTree<K, V, R, NODE, BinaryTree<K, V, R, NODE, BinaryTree<K, V, R, NODE, BinaryTree<K, V, R, NODE, BinaryTree<K, V, R, NODE, BinaryTree<K, V, R, NODE, BinaryTree<K, V, R, NODE, BinaryTree<K, V, R, NODE, BinaryTree<K, V, R, NODE, BinaryTree<K, V, R, NODE, BinaryTree<K, V, R, NODE, BinaryTree<K, V, R, NODE, BinaryTree<K, V, R, NODE, BinaryTree<K, V, R, NODE, BinaryTree<K, V, R, NODE, BinaryTree<K, V, R, NODE, BinaryTree<K, V, R, NODE, BinaryTree<K, V, R, NODE, BinaryTree<K, V, R, NODE, BinaryTree<K, V, R, NODE, BinaryTree<K, V, R, NODE, BinaryTree<K, V, R, NODE, BinaryTree<K, V, R, NODE, BinaryTree<K, V, R, NODE, any>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>;

5

dist/types/data-structures/binary-tree/bst.d.ts
import { BST, BSTNode } from '../../../data-structures';
import type { BinaryTreeOptions } from './binary-tree';
import { Comparator } from '../../common';
import { Comparable } from '../../utils';
export type BSTNodeNested<K, V> = BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, any>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>;
export type BSTNested<K, V, R, NODE extends BSTNode<K, V, NODE>> = BST<K, V, R, NODE, BST<K, V, R, NODE, BST<K, V, R, NODE, BST<K, V, R, NODE, BST<K, V, R, NODE, BST<K, V, R, NODE, BST<K, V, R, NODE, BST<K, V, R, NODE, BST<K, V, R, NODE, BST<K, V, R, NODE, BST<K, V, R, NODE, BST<K, V, R, NODE, BST<K, V, R, NODE, BST<K, V, R, NODE, BST<K, V, R, NODE, BST<K, V, R, NODE, BST<K, V, R, NODE, BST<K, V, R, NODE, BST<K, V, R, NODE, BST<K, V, R, NODE, BST<K, V, R, NODE, BST<K, V, R, NODE, BST<K, V, R, NODE, BST<K, V, R, NODE, BST<K, V, R, NODE, BST<K, V, R, NODE, BST<K, V, R, NODE, BST<K, V, R, NODE, BST<K, V, R, NODE, BST<K, V, R, NODE, BST<K, V, R, NODE, BST<K, V, R, NODE, BST<K, V, R, NODE, BST<K, V, R, NODE, BST<K, V, R, NODE, BST<K, V, R, NODE, BST<K, V, R, NODE, BST<K, V, R, NODE, BST<K, V, R, NODE, BST<K, V, R, NODE, BST<K, V, R, NODE, BST<K, V, R, NODE, BST<K, V, R, NODE, BST<K, V, R, NODE, BST<K, V, R, NODE, BST<K, V, R, NODE, BST<K, V, R, NODE, BST<K, V, R, NODE, BST<K, V, R, NODE, BST<K, V, R, NODE, any>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>;
export type BSTOptions<K, V, R> = BinaryTreeOptions<K, V, R> & {
comparator?: Comparator<K>;
extractComparable?: (key: K) => Comparable;
isReverse?: boolean;
};

@@ -9,0 +10,0 @@ export type BSTNOptKey<K> = K | undefined;

2

dist/types/data-structures/binary-tree/rb-tree.d.ts

@@ -6,2 +6,2 @@ import { RedBlackTree, RedBlackTreeNode } from '../../../data-structures';

export type RedBlackTreeNested<K, V, R, NODE extends RedBlackTreeNode<K, V, NODE>> = RedBlackTree<K, V, R, NODE, RedBlackTree<K, V, R, NODE, RedBlackTree<K, V, R, NODE, RedBlackTree<K, V, R, NODE, RedBlackTree<K, V, R, NODE, RedBlackTree<K, V, R, NODE, RedBlackTree<K, V, R, NODE, RedBlackTree<K, V, R, NODE, RedBlackTree<K, V, R, NODE, RedBlackTree<K, V, R, NODE, RedBlackTree<K, V, R, NODE, RedBlackTree<K, V, R, NODE, RedBlackTree<K, V, R, NODE, RedBlackTree<K, V, R, NODE, RedBlackTree<K, V, R, NODE, RedBlackTree<K, V, R, NODE, RedBlackTree<K, V, R, NODE, RedBlackTree<K, V, R, NODE, RedBlackTree<K, V, R, NODE, RedBlackTree<K, V, R, NODE, RedBlackTree<K, V, R, NODE, RedBlackTree<K, V, R, NODE, RedBlackTree<K, V, R, NODE, RedBlackTree<K, V, R, NODE, RedBlackTree<K, V, R, NODE, RedBlackTree<K, V, R, NODE, RedBlackTree<K, V, R, NODE, RedBlackTree<K, V, R, NODE, RedBlackTree<K, V, R, NODE, RedBlackTree<K, V, R, NODE, RedBlackTree<K, V, R, NODE, RedBlackTree<K, V, R, NODE, RedBlackTree<K, V, R, NODE, RedBlackTree<K, V, R, NODE, RedBlackTree<K, V, R, NODE, RedBlackTree<K, V, R, NODE, RedBlackTree<K, V, R, NODE, RedBlackTree<K, V, R, NODE, RedBlackTree<K, V, R, NODE, RedBlackTree<K, V, R, NODE, RedBlackTree<K, V, R, NODE, RedBlackTree<K, V, R, NODE, RedBlackTree<K, V, R, NODE, RedBlackTree<K, V, R, NODE, RedBlackTree<K, V, R, NODE, RedBlackTree<K, V, R, NODE, RedBlackTree<K, V, R, NODE, RedBlackTree<K, V, R, NODE, RedBlackTree<K, V, R, NODE, RedBlackTree<K, V, R, NODE, any>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>;
export type RBTreeOptions<K, V, R> = BSTOptions<K, V, R> & {};
export type RBTreeOptions<K, V, R> = Omit<BSTOptions<K, V, R>, 'isReverse'> & {};

16

dist/types/utils/utils.d.ts

@@ -9,11 +9,15 @@ export type ToThunkFn<R = any> = () => R;

export type Any = string | number | bigint | boolean | symbol | undefined | object;
export type Arithmetic = number | bigint;
export type ComparablePrimitive = number | bigint | string | boolean;
export type ComparableObject = {
[key in string]: any;
} & ({
valueOf: () => ComparablePrimitive | ComparableObject;
export interface BaseComparableObject {
[key: string]: unknown;
}
export interface ValueComparableObject extends BaseComparableObject {
valueOf: () => ComparablePrimitive | ValueComparableObject;
toString?: () => string;
} | {
}
export interface StringComparableObject extends BaseComparableObject {
toString: () => string;
});
}
export type ComparableObject = ValueComparableObject | StringComparableObject;
export type Comparable = ComparablePrimitive | Date | ComparableObject;

6

dist/utils/utils.js

@@ -216,3 +216,4 @@ "use strict";

if (valueType === 'number')
return !Number.isNaN(value);
return true;
// if (valueType === 'number') return !Number.isNaN(value);
return valueType === 'bigint' || valueType === 'string' || valueType === 'boolean';

@@ -269,3 +270,4 @@ }

if (value instanceof Date)
return !Number.isNaN(value.getTime());
return true;
// if (value instanceof Date) return !Number.isNaN(value.getTime());
if (isForceObjectComparable)

@@ -272,0 +274,0 @@ return true;

4

package.json
{
"name": "queue-typed",
"version": "1.53.6",
"version": "1.53.7",
"description": "Queue, ArrayQueue. Javascript & Typescript Data Structure.",

@@ -118,4 +118,4 @@ "main": "dist/index.js",

"dependencies": {
"data-structure-typed": "^1.53.6"
"data-structure-typed": "^1.53.7"
}
}

16

src/data-structures/binary-tree/avl-tree-multi-map.ts

@@ -146,4 +146,5 @@ /**

isMapMode: this._isMapMode,
comparator: this._comparator,
extractComparable: this._extractComparable,
toEntryFn: this._toEntryFn,
isReverse: this._isReverse,
...options

@@ -191,13 +192,10 @@ }) as TREE;

if (this.isKey(keyNodeEntryOrRaw)) return [this.createNode(keyNodeEntryOrRaw, value, count), value];
if (this.isRaw(keyNodeEntryOrRaw)) {
if (this._toEntryFn) {
const [key, entryValue] = this._toEntryFn(keyNodeEntryOrRaw as R);
const finalValue = value ?? entryValue;
if (this.isKey(key)) return [this.createNode(key, finalValue, count), finalValue];
}
return [undefined, undefined];
const [key, entryValue] = this._toEntryFn!(keyNodeEntryOrRaw);
const finalValue = value ?? entryValue;
if (this.isKey(key)) return [this.createNode(key, finalValue, count), finalValue];
}
if (this.isKey(keyNodeEntryOrRaw)) return [this.createNode(keyNodeEntryOrRaw, value, count), value];
return [undefined, undefined];

@@ -204,0 +202,0 @@ }

5

src/data-structures/binary-tree/avl-tree.ts

@@ -116,4 +116,5 @@ /**

isMapMode: this._isMapMode,
comparator: this._comparator,
extractComparable: this._extractComparable,
toEntryFn: this._toEntryFn,
isReverse: this._isReverse,
...options

@@ -438,3 +439,3 @@ }) as TREE;

node = this.ensureNode(node);
const path = this.getPathToRoot(node => node, node, false); // first O(log n) + O(log n)
const path = this.getPathToRoot(node, node => node, false); // first O(log n) + O(log n)
for (let i = 0; i < path.length; i++) {

@@ -441,0 +442,0 @@ // second O(log n)

259

src/data-structures/binary-tree/bst.ts

@@ -14,2 +14,3 @@ /**

BTNRep,
Comparable,
Comparator,

@@ -27,2 +28,3 @@ CP,

import { isComparable } from '../../utils';
import { Range } from '../../common';

@@ -97,2 +99,50 @@ export class BSTNode<K = any, V = any, NODE extends BSTNode<K, V, NODE> = BSTNodeNested<K, V>> extends BinaryTreeNode<

* 7. No Auto-Balancing: Standard BSTs don't automatically balance themselves.
* @example
* // Find kth smallest element
* // Create a BST with some elements
* const bst = new BST<number>([5, 3, 7, 1, 4, 6, 8]);
* const sortedKeys = bst.dfs(node => node.key, 'IN');
*
* // Helper function to find kth smallest
* const findKthSmallest = (k: number): number | undefined => {
* return sortedKeys[k - 1];
* };
*
* // Assertions
* console.log(findKthSmallest(1)); // 1
* console.log(findKthSmallest(3)); // 4
* console.log(findKthSmallest(7)); // 8
* @example
* // Find elements in a range
* const bst = new BST<number>([10, 5, 15, 3, 7, 12, 18]);
* console.log(bst.search(new Range(5, 10))); // [10, 5, 7]
* console.log(bst.search(new Range(4, 12))); // [10, 12, 5, 7]
* console.log(bst.search(new Range(4, 12, true, false))); // [10, 5, 7]
* console.log(bst.search(new Range(15, 20))); // [15, 18]
* console.log(bst.search(new Range(15, 20, false))); // [18]
* @example
* // Find lowest common ancestor
* const bst = new BST<number>([20, 10, 30, 5, 15, 25, 35, 3, 7, 12, 18]);
*
* function findFirstCommon(arr1: number[], arr2: number[]): number | undefined {
* for (const num of arr1) {
* if (arr2.indexOf(num) !== -1) {
* return num;
* }
* }
* return undefined;
* }
*
* // LCA helper function
* const findLCA = (num1: number, num2: number): number | undefined => {
* const path1 = bst.getPathToRoot(num1);
* const path2 = bst.getPathToRoot(num2);
* // Find the first common ancestor
* return findFirstCommon(path1, path2);
* };
*
* // Assertions
* console.log(findLCA(3, 10)); // 7
* console.log(findLCA(5, 35)); // 15
* console.log(findLCA(20, 30)); // 25
*/

@@ -121,4 +171,5 @@ export class BST<

if (options) {
const { comparator } = options;
if (comparator) this._comparator = comparator;
const { extractComparable, isReverse } = options;
if (typeof extractComparable === 'function') this._extractComparable = extractComparable;
if (isReverse !== undefined) this._isReverse = isReverse;
}

@@ -139,3 +190,14 @@

protected _isReverse: boolean = false;
/**
* The above function is a getter method in TypeScript that returns the value of the private property
* `_isReverse`.
* @returns The `isReverse` property of the object, which is a boolean value.
*/
get isReverse(): boolean {
return this._isReverse;
}
/**
* The function creates a new BSTNode with the given key and value and returns it.

@@ -163,4 +225,5 @@ * @param {K} key - The key parameter is of type K, which represents the type of the key for the node

isMapMode: this._isMapMode,
comparator: this._comparator,
extractComparable: this._extractComparable,
toEntryFn: this._toEntryFn,
isReverse: this._isReverse,
...options

@@ -226,7 +289,7 @@ }) as TREE;

* @returns The `override isKey(key: any): key is K` function is returning a boolean value based on
* the result of the `isComparable` function with the condition `this.comparator !==
* the result of the `isComparable` function with the condition `this._compare !==
* this._DEFAULT_COMPARATOR`.
*/
override isKey(key: any): key is K {
return isComparable(key, this.comparator !== this._DEFAULT_COMPARATOR);
return isComparable(key, this._extractComparable !== undefined);
}

@@ -258,7 +321,7 @@

while (current !== undefined) {
if (this.comparator(current.key, newNode.key) === 0) {
if (this._compare(current.key, newNode.key) === 0) {
this._replaceNode(current, newNode);
if (this._isMapMode) this._setValue(current.key, newValue);
return true;
} else if (this.comparator(current.key, newNode.key) > 0) {
} else if (this._compare(current.key, newNode.key) > 0) {
if (current.left === undefined) {

@@ -361,3 +424,3 @@ current.left = newNode;

if (keyA !== undefined && keyA !== null && keyB !== undefined && keyB !== null) {
return this.comparator(keyA, keyB);
return this._compare(keyA, keyB);
}

@@ -405,30 +468,49 @@ return 0;

/**
* Time Complexity: O(n)
* Space Complexity: O(1)
*
* The `merge` function overrides the base class method by adding elements from another
* binary search tree.
* @param anotherTree - `anotherTree` is an instance of a Binary Search Tree (BST) with key type `K`,
* value type `V`, return type `R`, node type `NODE`, and tree type `TREE`.
*/
override merge(anotherTree: BST<K, V, R, NODE, TREE>) {
this.addMany(anotherTree, [], false);
}
/**
* Time Complexity: O(log n)
* Space Complexity: O(k + log n)
*
* The function `getNodes` in TypeScript overrides the base class method to retrieve nodes based on a
* given keyNodeEntryRawOrPredicate and iteration type.
* @param {BTNRep<K, V, NODE> | R | NodePredicate<NODE>} keyNodeEntryRawOrPredicate - The `keyNodeEntryRawOrPredicate`
* parameter in the `getNodes` method is used to filter the nodes that will be returned. It can be a
* key, a node, an entry, or a custom keyNodeEntryRawOrPredicate function that determines whether a node should be
* included in the result.
* @param [onlyOne=false] - The `onlyOne` parameter in the `getNodes` method is a boolean flag that
* determines whether to return only the first node that matches the keyNodeEntryRawOrPredicate (`true`) or all nodes
* that match the keyNodeEntryRawOrPredicate (`false`). If `onlyOne` is set to `true`, the method will stop iterating
* and
* @param {BTNRep<K, V, NODE> | R} startNode - The `startNode` parameter in the
* `getNodes` method is used to specify the starting point for traversing the tree when searching for
* nodes that match a given keyNodeEntryRawOrPredicate. It represents the root node of the subtree where the search
* should begin. If not explicitly provided, the default value for `begin
* @param {IterationType} iterationType - The `iterationType` parameter in the `getNodes` method
* specifies the type of iteration to be performed when traversing the nodes of a binary tree. It can
* have two possible values:
* @returns The `getNodes` method returns an array of nodes that satisfy the given keyNodeEntryRawOrPredicate.
* The function `search` in TypeScript overrides the search behavior in a binary tree structure based
* on specified criteria.
* @param {BTNRep<K, V, NODE> | R | NodePredicate<NODE>} keyNodeEntryRawOrPredicate - The
* `keyNodeEntryRawOrPredicate` parameter in the `override search` method can accept one of the
* following types:
* @param [onlyOne=false] - The `onlyOne` parameter is a boolean flag that determines whether the
* search should stop after finding the first matching node. If `onlyOne` is set to `true`, the
* search will return as soon as a matching node is found. If `onlyOne` is set to `false`, the
* @param {C} callback - The `callback` parameter in the `override search` function is a function
* that will be called on each node that matches the search criteria. It is of type `C`, which
* extends `NodeCallback<NODE>`. The callback function should accept a node of type `NODE` as its
* argument and
* @param {BTNRep<K, V, NODE> | R} startNode - The `startNode` parameter in the `override search`
* method represents the node from which the search operation will begin. It is the starting point
* for searching within the tree data structure. The method ensures that the `startNode` is a valid
* node before proceeding with the search operation. If the `
* @param {IterationType} iterationType - The `iterationType` parameter in the `override search`
* function determines the type of iteration to be used during the search operation. It can have two
* possible values:
* @returns The `override search` method returns an array of values that match the search criteria
* specified by the input parameters. The method performs a search operation on a binary tree
* structure based on the provided key, predicate, and other options. The search results are
* collected in an array and returned as the output of the method.
*/
override getNodes(
keyNodeEntryRawOrPredicate: BTNRep<K, V, NODE> | R | NodePredicate<NODE>,
override search<C extends NodeCallback<NODE>>(
keyNodeEntryRawOrPredicate: BTNRep<K, V, NODE> | R | NodePredicate<NODE> | Range<K>,
onlyOne = false,
callback: C = this._DEFAULT_NODE_CALLBACK as C,
startNode: BTNRep<K, V, NODE> | R = this._root,
iterationType: IterationType = this.iterationType
): NODE[] {
): ReturnType<C>[] {
if (keyNodeEntryRawOrPredicate === undefined) return [];

@@ -438,9 +520,36 @@ if (keyNodeEntryRawOrPredicate === null) return [];

if (!startNode) return [];
const callback = this._ensurePredicate(keyNodeEntryRawOrPredicate);
const ans: NODE[] = [];
let predicate: NodePredicate<NODE>;
const isRange = this.isRange(keyNodeEntryRawOrPredicate);
// Set predicate based on parameter type
if (isRange) {
predicate = node => keyNodeEntryRawOrPredicate.isInRange(node.key, this._comparator);
} else {
predicate = this._ensurePredicate(keyNodeEntryRawOrPredicate);
}
const isToLeftByRange = (cur: NODE) => {
if (isRange) {
const range = keyNodeEntryRawOrPredicate;
const leftS = this.isReverse ? range.high : range.low;
const leftI = this.isReverse ? range.includeHigh : range.includeLow;
return (leftI && this._compare(cur.key, leftS) >= 0) || (!leftI && this._compare(cur.key, leftS) > 0);
}
return false;
};
const isToRightByRange = (cur: NODE) => {
if (isRange) {
const range = keyNodeEntryRawOrPredicate;
const rightS = this.isReverse ? range.low : range.high;
const rightI = this.isReverse ? range.includeLow : range.includeLow;
return (rightI && this._compare(cur.key, rightS) <= 0) || (!rightI && this._compare(cur.key, rightS) < 0);
}
return false;
};
const ans: ReturnType<C>[] = [];
if (iterationType === 'RECURSIVE') {
const dfs = (cur: NODE) => {
if (callback(cur)) {
ans.push(cur);
if (predicate(cur)) {
ans.push(callback(cur));
if (onlyOne) return;

@@ -450,4 +559,8 @@ }

if (!this.isRealNode(cur.left) && !this.isRealNode(cur.right)) return;
if (!this._isPredicate(keyNodeEntryRawOrPredicate)) {
const benchmarkKey = this._getKey(keyNodeEntryRawOrPredicate);
if (isRange) {
if (this.isRealNode(cur.left) && isToLeftByRange(cur)) dfs(cur.left);
if (this.isRealNode(cur.right) && isToRightByRange(cur)) dfs(cur.right);
} else if (!this._isPredicate(keyNodeEntryRawOrPredicate)) {
const benchmarkKey = this._extractKey(keyNodeEntryRawOrPredicate);
if (

@@ -457,3 +570,3 @@ this.isRealNode(cur.left) &&

benchmarkKey !== undefined &&
this.comparator(cur.key, benchmarkKey) > 0
this._compare(cur.key, benchmarkKey) > 0
)

@@ -465,3 +578,3 @@ dfs(cur.left);

benchmarkKey !== undefined &&
this.comparator(cur.key, benchmarkKey) < 0
this._compare(cur.key, benchmarkKey) < 0
)

@@ -480,8 +593,11 @@ dfs(cur.right);

const cur = stack.pop()!;
if (callback(cur)) {
ans.push(cur);
if (predicate(cur)) {
ans.push(callback(cur));
if (onlyOne) return ans;
}
if (!this._isPredicate(keyNodeEntryRawOrPredicate)) {
const benchmarkKey = this._getKey(keyNodeEntryRawOrPredicate);
if (isRange) {
if (this.isRealNode(cur.left) && isToLeftByRange(cur)) stack.push(cur.left);
if (this.isRealNode(cur.right) && isToRightByRange(cur)) stack.push(cur.right);
} else if (!this._isPredicate(keyNodeEntryRawOrPredicate)) {
const benchmarkKey = this._extractKey(keyNodeEntryRawOrPredicate);
if (

@@ -491,3 +607,3 @@ this.isRealNode(cur.right) &&

benchmarkKey !== undefined &&
this.comparator(cur.key, benchmarkKey) < 0
this._compare(cur.key, benchmarkKey) < 0
)

@@ -499,3 +615,3 @@ stack.push(cur.right);

benchmarkKey !== undefined &&
this.comparator(cur.key, benchmarkKey) > 0
this._compare(cur.key, benchmarkKey) > 0
)

@@ -542,19 +658,2 @@ stack.push(cur.left);

/**
* Time Complexity: O(log n)
* Space Complexity: O(1)
*
* The function `getNodeByKey` returns a node with a specific key from a tree data structure.
* @param {K} key - The key parameter is the value used to search for a specific node in the tree. It
* is typically a unique identifier or a value that can be used to determine the position of the node
* in the tree structure.
* @param {IterationType} [iterationType=ITERATIVE] - The `iterationType` parameter is an optional
* parameter that specifies the type of iteration to be used when searching for a node in the tree.
* It has a default value of `'ITERATIVE'`.
* @returns The method is returning a NODE object or undefined.
*/
override getNodeByKey(key: K, iterationType: IterationType = this.iterationType): OptNode<NODE> {
return this.getNode(key, this._root, iterationType);
}
/**
* Time complexity: O(n)

@@ -675,5 +774,5 @@ * Space complexity: O(n)

const dfs = (cur: NODE) => {
const compared = this.comparator(cur.key, targetKey);
const compared = this._compare(cur.key, targetKey);
if (Math.sign(compared) === lesserOrGreater) ans.push(callback(cur));
// TODO here can be optimized to O(log n)
if (this.isRealNode(cur.left)) dfs(cur.left);

@@ -690,3 +789,3 @@ if (this.isRealNode(cur.right)) dfs(cur.right);

if (this.isRealNode(cur)) {
const compared = this.comparator(cur.key, targetKey);
const compared = this._compare(cur.key, targetKey);
if (Math.sign(compared) === lesserOrGreater) ans.push(callback(cur));

@@ -809,15 +908,22 @@

protected _DEFAULT_COMPARATOR = (a: K, b: K): number => {
protected _comparator: Comparator<K> = (a: K, b: K): number => {
if (isComparable(a) && isComparable(b)) {
if (a > b) return 1;
if (a < b) return -1;
return 0;
}
if (this._extractComparable) {
if (this._extractComparable(a) > this._extractComparable(b)) return 1;
if (this._extractComparable(a) < this._extractComparable(b)) return -1;
return 0;
}
if (typeof a === 'object' || typeof b === 'object') {
throw TypeError(
`When comparing object types, a custom comparator must be defined in the constructor's options parameter.`
`When comparing object types, a custom extractComparable must be defined in the constructor's options parameter.`
);
}
if (a > b) return 1;
if (a < b) return -1;
return 0;
};
protected _comparator: Comparator<K> = this._DEFAULT_COMPARATOR;
/**

@@ -831,3 +937,14 @@ * The function returns the value of the _comparator property.

protected _extractComparable?: (key: K) => Comparable;
/**
* This function returns the value of the `_extractComparable` property.
* @returns The method `extractComparable()` is being returned, which is a getter method for the
* `_extractComparable` property.
*/
get extractComparable() {
return this._extractComparable;
}
/**
* The function sets the root of a tree-like structure and updates the parent property of the new

@@ -843,2 +960,6 @@ * root.

}
protected _compare(a: K, b: K) {
return this._isReverse ? -this._comparator(a, b) : this._comparator(a, b);
}
}

8

src/data-structures/binary-tree/rb-tree.ts

@@ -54,2 +54,6 @@ import type {

/**
* 1. Efficient self-balancing, but not completely balanced. Compared with AVLTree, the addition and deletion efficiency is high but the query efficiency is slightly lower.
* 2. It is BST itself. Compared with Heap which is not completely ordered, RedBlackTree is completely ordered.
*/
export class RedBlackTree<

@@ -123,3 +127,3 @@ K = any,

isMapMode: this._isMapMode,
comparator: this._comparator,
extractComparable: this._extractComparable,
toEntryFn: this._toEntryFn,

@@ -356,3 +360,3 @@ ...options

parent = current;
const compared = this.comparator(node.key, current.key);
const compared = this._compare(node.key, current.key);
if (compared < 0) {

@@ -359,0 +363,0 @@ current = current.left ?? this.NIL;

6

src/data-structures/binary-tree/tree-multi-map.ts

@@ -142,3 +142,3 @@ /**

isMapMode: this._isMapMode,
comparator: this._comparator,
extractComparable: this._extractComparable,
toEntryFn: this._toEntryFn,

@@ -177,4 +177,4 @@ ...options

if (this._toEntryFn) {
const [key, entryValue] = this._toEntryFn(keyNodeEntryOrRaw as R);
if (this.isRaw(keyNodeEntryOrRaw)) {
const [key, entryValue] = this._toEntryFn!(keyNodeEntryOrRaw);
const finalValue = value ?? entryValue;

@@ -181,0 +181,0 @@ if (this.isKey(key)) return [this.createNode(key, finalValue, 'BLACK', count), finalValue];

78

src/data-structures/heap/heap.ts

@@ -22,5 +22,5 @@ /**

* 8. Graph Algorithms: Such as Dijkstra's shortest path algorithm and Prime's minimum-spanning tree algorithm, which use heaps to improve performance.
* @example
* // Use Heap to sort an array
* function heapSort(arr: number[]): number[] {
* @example
* // Use Heap to sort an array
* function heapSort(arr: number[]): number[] {
* const heap = new Heap<number>(arr, { comparator: (a, b) => a - b });

@@ -33,8 +33,8 @@ * const sorted: number[] = [];

* }
*
*
* const array = [5, 3, 8, 4, 1, 2];
* console.log(heapSort(array)); // [1, 2, 3, 4, 5, 8]
* @example
* // Use Heap to solve top k problems
* function topKElements(arr: number[], k: number): number[] {
* @example
* // Use Heap to solve top k problems
* function topKElements(arr: number[], k: number): number[] {
* const heap = new Heap<number>([], { comparator: (a, b) => b - a }); // Max heap

@@ -47,12 +47,12 @@ * arr.forEach(num => {

* }
*
*
* const numbers = [10, 30, 20, 5, 15, 25];
* console.log(topKElements(numbers, 3)); // [15, 10, 5]
* @example
* // Use Heap to merge sorted sequences
* function mergeSortedSequences(sequences: number[][]): number[] {
* @example
* // Use Heap to merge sorted sequences
* function mergeSortedSequences(sequences: number[][]): number[] {
* const heap = new Heap<{ value: number; seqIndex: number; itemIndex: number }>([], {
* comparator: (a, b) => a.value - b.value // Min heap
* });
*
*
* // Initialize heap

@@ -64,3 +64,3 @@ * sequences.forEach((seq, seqIndex) => {

* });
*
*
* const merged: number[] = [];

@@ -70,3 +70,3 @@ * while (!heap.isEmpty()) {

* merged.push(value);
*
*
* if (itemIndex + 1 < sequences[seqIndex].length) {

@@ -80,6 +80,6 @@ * heap.add({

* }
*
*
* return merged;
* }
*
*
* const sequences = [

@@ -91,8 +91,8 @@ * [1, 4, 7],

* console.log(mergeSortedSequences(sequences)); // [1, 2, 3, 4, 5, 6, 7, 8, 9]
* @example
* // Use Heap to dynamically maintain the median
* class MedianFinder {
* @example
* // Use Heap to dynamically maintain the median
* class MedianFinder {
* private low: MaxHeap<number>; // Max heap, stores the smaller half
* private high: MinHeap<number>; // Min heap, stores the larger half
*
*
* constructor() {

@@ -102,7 +102,7 @@ * this.low = new MaxHeap<number>([]);

* }
*
*
* addNum(num: number): void {
* if (this.low.isEmpty() || num <= this.low.peek()!) this.low.add(num);
* else this.high.add(num);
*
*
* // Balance heaps

@@ -112,3 +112,3 @@ * if (this.low.size > this.high.size + 1) this.high.add(this.low.poll()!);

* }
*
*
* findMedian(): number {

@@ -119,3 +119,3 @@ * if (this.low.size === this.high.size) return (this.low.peek()! + this.high.peek()!) / 2;

* }
*
*
* const medianFinder = new MedianFinder();

@@ -132,12 +132,12 @@ * medianFinder.addNum(10);

* console.log(medianFinder.findMedian()); // 30
* @example
* // Use Heap for load balancing
* function loadBalance(requests: number[], servers: number): number[] {
* @example
* // Use Heap for load balancing
* function loadBalance(requests: number[], servers: number): number[] {
* const serverHeap = new Heap<{ id: number; load: number }>([], { comparator: (a, b) => a.load - b.load }); // min heap
* const serverLoads = new Array(servers).fill(0);
*
*
* for (let i = 0; i < servers; i++) {
* serverHeap.add({ id: i, load: 0 });
* }
*
*
* requests.forEach(req => {

@@ -149,16 +149,16 @@ * const server = serverHeap.poll()!;

* });
*
*
* return serverLoads;
* }
*
*
* const requests = [5, 2, 8, 3, 7];
* console.log(loadBalance(requests, 3)); // [12, 8, 5]
* @example
* // Use Heap to schedule tasks
* type Task = [string, number];
*
* @example
* // Use Heap to schedule tasks
* type Task = [string, number];
*
* function scheduleTasks(tasks: Task[], machines: number): Map<number, Task[]> {
* const machineHeap = new Heap<{ id: number; load: number }>([], { comparator: (a, b) => a.load - b.load }); // Min heap
* const allocation = new Map<number, Task[]>();
*
*
* // Initialize the load on each machine

@@ -169,3 +169,3 @@ * for (let i = 0; i < machines; i++) {

* }
*
*
* // Assign tasks

@@ -178,6 +178,6 @@ * tasks.forEach(([task, load]) => {

* });
*
*
* return allocation;
* }
*
*
* const tasks: Task[] = [

@@ -184,0 +184,0 @@ * ['Task1', 3],

208

src/data-structures/linked-list/doubly-linked-list.ts

@@ -85,9 +85,9 @@ /**

/**
* 1. Node Structure: Each node contains three parts: a data field, a pointer (or reference) to the previous node, and a pointer to the next node. This structure allows traversal of the linked list in both directions.
*1. Node Structure: Each node contains three parts: a data field, a pointer (or reference) to the previous node, and a pointer to the next node. This structure allows traversal of the linked list in both directions.
* 2. Bidirectional Traversal: Unlike singly linked lists, doubly linked lists can be easily traversed forwards or backwards. This makes insertions and deletions in the list more flexible and efficient.
* 3. No Centralized Index: Unlike arrays, elements in a linked list are not stored contiguously, so there is no centralized index. Accessing elements in a linked list typically requires traversing from the head or tail node.
* 4. High Efficiency in Insertion and Deletion: Adding or removing elements in a linked list does not require moving other elements, making these operations more efficient than in arrays.
* @example
* // text editor operation history
* const actions = [
* @example
* // text editor operation history
* const actions = [
* { type: 'insert', content: 'first line of text' },

@@ -98,20 +98,20 @@ * { type: 'insert', content: 'second line of text' },

* const editorHistory = new DoublyLinkedList<{ type: string; content: string }>(actions);
*
*
* console.log(editorHistory.last?.type); // 'delete'
* console.log(editorHistory.pop()?.content); // 'delete the first line'
* console.log(editorHistory.last?.type); // 'insert'
* @example
* // Browser history
* const browserHistory = new DoublyLinkedList<string>();
*
* @example
* // Browser history
* const browserHistory = new DoublyLinkedList<string>();
*
* browserHistory.push('home page');
* browserHistory.push('search page');
* browserHistory.push('details page');
*
*
* console.log(browserHistory.last); // 'details page'
* console.log(browserHistory.pop()); // 'details page'
* console.log(browserHistory.last); // 'search page'
* @example
* // Use DoublyLinkedList to implement music player
* // Define the Song interface
* @example
* // Use DoublyLinkedList to implement music player
* // Define the Song interface
* interface Song {

@@ -122,7 +122,7 @@ * title: string;

* }
*
*
* class Player {
* private playlist: DoublyLinkedList<Song>;
* private currentSong: ReturnType<typeof this.playlist.getNodeAt> | undefined;
*
*
* constructor(songs: Song[]) {

@@ -133,3 +133,3 @@ * this.playlist = new DoublyLinkedList<Song>();

* }
*
*
* // Play the next song in the playlist

@@ -144,3 +144,3 @@ * playNext(): Song | undefined {

* }
*
*
* // Play the previous song in the playlist

@@ -155,3 +155,3 @@ * playPrevious(): Song | undefined {

* }
*
*
* // Get the current song

@@ -161,3 +161,3 @@ * getCurrentSong(): Song | undefined {

* }
*
*
* // Loop through the playlist twice

@@ -167,3 +167,3 @@ * loopThroughPlaylist(): Song[] {

* const initialNode = this.currentSong;
*
*
* // Loop through the playlist twice

@@ -174,3 +174,3 @@ * for (let i = 0; i < this.playlist.size * 2; i++) {

* }
*
*
* // Reset the current song to the initial song

@@ -181,3 +181,3 @@ * this.currentSong = initialNode;

* }
*
*
* const songs = [

@@ -194,7 +194,7 @@ * { title: 'Bohemian Rhapsody', artist: 'Queen', duration: 354 },

* const nextSong = player.playNext();
*
*
* // Expect the next song to be "Hotel California by Eagles"
* console.log(nextSong); // { title: 'Hotel California', artist: 'Eagles', duration: 391 }
* console.log(firstSong); // { title: 'Bohemian Rhapsody', artist: 'Queen', duration: 354 }
*
*
* // should play the previous song

@@ -205,7 +205,7 @@ * player = new Player(songs);

* const previousSong = player.playPrevious();
*
*
* // Expect the previous song to be "Bohemian Rhapsody by Queen"
* console.log(previousSong); // { title: 'Bohemian Rhapsody', artist: 'Queen', duration: 354 }
* console.log(currentSong); // { title: 'Hotel California', artist: 'Eagles', duration: 391 }
*
*
* // should loop to the first song when playing next from the last song

@@ -216,8 +216,8 @@ * player = new Player(songs);

* player.playNext(); // Move to the fourth song
*
*
* const nextSongToFirst = player.playNext(); // Should loop to the first song
*
*
* // Expect the next song to be "Bohemian Rhapsody by Queen"
* console.log(nextSongToFirst); // { title: 'Bohemian Rhapsody', artist: 'Queen', duration: 354 }
*
*
* // should loop to the last song when playing previous from the first song

@@ -229,12 +229,12 @@ * player = new Player(songs);

* player.playNext(); // Move to the fourth song
*
*
* const previousToLast = player.playPrevious(); // Should loop to the last song
*
*
* // Expect the previous song to be "Billie Jean by Michael Jackson"
* console.log(previousToLast); // { title: 'Billie Jean', artist: 'Michael Jackson', duration: 294 }
*
*
* // should loop through the entire playlist
* player = new Player(songs);
* const playedSongs = player.loopThroughPlaylist();
*
*
* // The expected order of songs for two loops

@@ -251,9 +251,9 @@ * console.log(playedSongs); // [

* // ]
* @example
* // Use DoublyLinkedList to implement LRU cache
* interface CacheEntry<K, V> {
* @example
* // Use DoublyLinkedList to implement LRU cache
* interface CacheEntry<K, V> {
* key: K;
* value: V;
* }
*
*
* class LRUCache<K = string, V = any> {

@@ -263,3 +263,3 @@ * private readonly capacity: number;

* private map: Map<K, DoublyLinkedListNode<CacheEntry<K, V>>>;
*
*
* constructor(capacity: number) {

@@ -273,15 +273,15 @@ * if (capacity <= 0) {

* }
*
*
* // Get cached value
* get(key: K): V | undefined {
* const node = this.map.get(key);
*
*
* if (!node) return undefined;
*
*
* // Move the visited node to the head of the linked list (most recently used)
* this.moveToFront(node);
*
*
* return node.value.value;
* }
*
*
* // Set cache value

@@ -291,3 +291,3 @@ * set(key: K, value: V): void {

* const node = this.map.get(key);
*
*
* if (node) {

@@ -299,3 +299,3 @@ * // Update value and move to head

* }
*
*
* // Check capacity

@@ -310,7 +310,7 @@ * if (this.list.size >= this.capacity) {

* }
*
*
* // Create new node and add to head
* const newEntry: CacheEntry<K, V> = { key, value };
* this.list.unshift(newEntry);
*
*
* // Save node reference in map

@@ -322,3 +322,3 @@ * const newNode = this.list.head;

* }
*
*
* // Move the node to the head of the linked list

@@ -329,3 +329,3 @@ * private moveToFront(node: DoublyLinkedListNode<CacheEntry<K, V>>): void {

* }
*
*
* // Delete specific key

@@ -335,3 +335,3 @@ * delete(key: K): boolean {

* if (!node) return false;
*
*
* // Remove from linked list

@@ -341,6 +341,6 @@ * this.list.delete(node);

* this.map.delete(key);
*
*
* return true;
* }
*
*
* // Clear cache

@@ -351,3 +351,3 @@ * clear(): void {

* }
*
*
* // Get the current cache size

@@ -357,3 +357,3 @@ * get size(): number {

* }
*
*
* // Check if it is empty

@@ -364,3 +364,3 @@ * get isEmpty(): boolean {

* }
*
*
* // should set and get values correctly

@@ -371,7 +371,7 @@ * const cache = new LRUCache<string, number>(3);

* cache.set('c', 3);
*
*
* console.log(cache.get('a')); // 1
* console.log(cache.get('b')); // 2
* console.log(cache.get('c')); // 3
*
*
* // The least recently used element should be evicted when capacity is exceeded

@@ -383,3 +383,3 @@ * cache.clear();

* cache.set('d', 4); // This will eliminate 'a'
*
*
* console.log(cache.get('a')); // undefined

@@ -389,3 +389,3 @@ * console.log(cache.get('b')); // 2

* console.log(cache.get('d')); // 4
*
*
* // The priority of an element should be updated when it is accessed

@@ -396,6 +396,6 @@ * cache.clear();

* cache.set('c', 3);
*
*
* cache.get('a'); // access 'a'
* cache.set('d', 4); // This will eliminate 'b'
*
*
* console.log(cache.get('a')); // 1

@@ -405,3 +405,3 @@ * console.log(cache.get('b')); // undefined

* console.log(cache.get('d')); // 4
*
*
* // Should support updating existing keys

@@ -411,5 +411,5 @@ * cache.clear();

* cache.set('a', 10);
*
*
* console.log(cache.get('a')); // 10
*
*
* // Should support deleting specified keys

@@ -419,7 +419,7 @@ * cache.clear();

* cache.set('b', 2);
*
*
* console.log(cache.delete('a')); // true
* console.log(cache.get('a')); // undefined
* console.log(cache.size); // 1
*
*
* // Should support clearing cache

@@ -430,10 +430,10 @@ * cache.clear();

* cache.clear();
*
*
* console.log(cache.size); // 0
* console.log(cache.isEmpty); // true
* @example
* // finding lyrics by timestamp in Coldplay's "Fix You"
* // Create a DoublyLinkedList to store song lyrics with timestamps
* @example
* // finding lyrics by timestamp in Coldplay's "Fix You"
* // Create a DoublyLinkedList to store song lyrics with timestamps
* const lyricsList = new DoublyLinkedList<{ time: number; text: string }>();
*
*
* // Detailed lyrics with precise timestamps (in milliseconds)

@@ -453,26 +453,26 @@ * const lyrics = [

* ];
*
*
* // Populate the DoublyLinkedList with lyrics
* lyrics.forEach(lyric => lyricsList.push(lyric));
*
*
* // Test different scenarios of lyric synchronization
*
*
* // 1. Find lyric at exact timestamp
* const exactTimeLyric = lyricsList.getBackward(lyric => lyric.value.time <= 36000);
* console.log(exactTimeLyric?.text); // 'And ignite your bones'
*
*
* // 2. Find lyric between timestamps
* const betweenTimeLyric = lyricsList.getBackward(lyric => lyric.value.time <= 22000);
* console.log(betweenTimeLyric?.text); // "When you lose something you can't replace"
*
*
* // 3. Find first lyric when timestamp is less than first entry
* const earlyTimeLyric = lyricsList.getBackward(lyric => lyric.value.time <= -1000);
* console.log(earlyTimeLyric); // undefined
*
*
* // 4. Find last lyric when timestamp is after last entry
* const lateTimeLyric = lyricsList.getBackward(lyric => lyric.value.time <= 50000);
* console.log(lateTimeLyric?.text); // 'And I will try to fix you'
* @example
* // cpu process schedules
* class Process {
* @example
* // cpu process schedules
* class Process {
* constructor(

@@ -482,3 +482,3 @@ * public id: number,

* ) {}
*
*
* execute(): string {

@@ -488,10 +488,10 @@ * return `Process ${this.id} executed.`;

* }
*
*
* class Scheduler {
* private queue: DoublyLinkedList<Process>;
*
*
* constructor() {
* this.queue = new DoublyLinkedList<Process>();
* }
*
*
* addProcess(process: Process): void {

@@ -503,3 +503,3 @@ * // Insert processes into a queue based on priority, keeping priority in descending order

* }
*
*
* if (!current) {

@@ -511,3 +511,3 @@ * this.queue.push(process);

* }
*
*
* executeNext(): string | undefined {

@@ -518,7 +518,7 @@ * // Execute tasks at the head of the queue in order

* }
*
*
* listProcesses(): string[] {
* return this.queue.toArray().map(process => `Process ${process.id} (Priority: ${process.priority})`);
* }
*
*
* clear(): void {

@@ -528,3 +528,3 @@ * this.queue.clear();

* }
*
*
* // should add processes based on priority

@@ -535,3 +535,3 @@ * let scheduler = new Scheduler();

* scheduler.addProcess(new Process(3, 15));
*
*
* console.log(scheduler.listProcesses()); // [

@@ -542,3 +542,3 @@ * // 'Process 2 (Priority: 20)',

* // ]
*
*
* // should execute the highest priority process

@@ -548,6 +548,6 @@ * scheduler = new Scheduler();

* scheduler.addProcess(new Process(2, 20));
*
*
* console.log(scheduler.executeNext()); // 'Process 2 executed.'
* console.log(scheduler.listProcesses()); // ['Process 1 (Priority: 10)']
*
*
* // should clear all processes

@@ -557,3 +557,3 @@ * scheduler = new Scheduler();

* scheduler.addProcess(new Process(2, 20));
*
*
* scheduler.clear();

@@ -563,2 +563,12 @@ * console.log(scheduler.listProcesses()); // []

export class DoublyLinkedList<E = any, R = any> extends IterableElementBase<E, R, DoublyLinkedList<E, R>> {
/**
* This TypeScript constructor initializes a DoublyLinkedList with optional elements and options.
* @param {Iterable<E> | Iterable<R>} elements - The `elements` parameter in the constructor is an
* iterable collection of elements of type `E` or `R`. It is used to initialize the DoublyLinkedList
* with the elements provided in the iterable. If no elements are provided, the default value is an
* empty iterable.
* @param [options] - The `options` parameter in the constructor is of type
* `DoublyLinkedListOptions<E, R>`. It is an optional parameter that allows you to pass additional
* configuration options to customize the behavior of the DoublyLinkedList.
*/
constructor(elements: Iterable<E> | Iterable<R> = [], options?: DoublyLinkedListOptions<E, R>) {

@@ -869,3 +879,5 @@ super(options);

): boolean {
const existingNode: DoublyLinkedListNode<E> | undefined = this.getNode(existingElementOrNode);
const existingNode: DoublyLinkedListNode<E> | undefined = this.isNode(existingElementOrNode)
? existingElementOrNode
: this.getNode(existingElementOrNode);

@@ -907,3 +919,5 @@ if (existingNode) {

addAfter(existingElementOrNode: E | DoublyLinkedListNode<E>, newElementOrNode: E | DoublyLinkedListNode<E>): boolean {
const existingNode: DoublyLinkedListNode<E> | undefined = this.getNode(existingElementOrNode);
const existingNode: DoublyLinkedListNode<E> | undefined = this.isNode(existingElementOrNode)
? existingElementOrNode
: this.getNode(existingElementOrNode);

@@ -1051,3 +1065,3 @@ if (existingNode) {

*/
get(
search(
elementNodeOrPredicate: E | DoublyLinkedListNode<E> | ((node: DoublyLinkedListNode<E>) => boolean)

@@ -1054,0 +1068,0 @@ ): E | undefined {

2

src/data-structures/linked-list/singly-linked-list.ts

@@ -226,3 +226,3 @@ /**

*/
get(
search(
elementNodeOrPredicate: E | SinglyLinkedListNode<E> | ((node: SinglyLinkedListNode<E>) => boolean)

@@ -229,0 +229,0 @@ ): E | undefined {

127

src/data-structures/trie/trie.ts

@@ -95,9 +95,96 @@ /**

* 11. Text Word Frequency Count: Counting and storing the frequency of words in a large amount of text data.
* @example
* // Autocomplete: Prefix validation and checking
* const autocomplete = new Trie<string>(['gmail.com', 'gmail.co.nz', 'gmail.co.jp', 'yahoo.com', 'outlook.com']);
*
* // Get all completions for a prefix
* const gmailCompletions = autocomplete.getWords('gmail');
* console.log(gmailCompletions); // ['gmail.com', 'gmail.co.nz', 'gmail.co.jp']
* @example
* // File System Path Operations
* const fileSystem = new Trie<string>([
* '/home/user/documents/file1.txt',
* '/home/user/documents/file2.txt',
* '/home/user/pictures/photo.jpg',
* '/home/user/pictures/vacation/',
* '/home/user/downloads'
* ]);
*
* // Find common directory prefix
* console.log(fileSystem.getLongestCommonPrefix()); // '/home/user/'
*
* // List all files in a directory
* const documentsFiles = fileSystem.getWords('/home/user/documents/');
* console.log(documentsFiles); // ['/home/user/documents/file1.txt', '/home/user/documents/file2.txt']
* @example
* // Autocomplete: Basic word suggestions
* // Create a trie for autocomplete
* const autocomplete = new Trie<string>([
* 'function',
* 'functional',
* 'functions',
* 'class',
* 'classes',
* 'classical',
* 'closure',
* 'const',
* 'constructor'
* ]);
*
* // Test autocomplete with different prefixes
* console.log(autocomplete.getWords('fun')); // ['functional', 'functions', 'function']
* console.log(autocomplete.getWords('cla')); // ['classes', 'classical', 'class']
* console.log(autocomplete.getWords('con')); // ['constructor', 'const']
*
* // Test with non-matching prefix
* console.log(autocomplete.getWords('xyz')); // []
* @example
* // Dictionary: Case-insensitive word lookup
* // Create a case-insensitive dictionary
* const dictionary = new Trie<string>([], { caseSensitive: false });
*
* // Add words with mixed casing
* dictionary.add('Hello');
* dictionary.add('WORLD');
* dictionary.add('JavaScript');
*
* // Test lookups with different casings
* console.log(dictionary.has('hello')); // true
* console.log(dictionary.has('HELLO')); // true
* console.log(dictionary.has('Hello')); // true
* console.log(dictionary.has('javascript')); // true
* console.log(dictionary.has('JAVASCRIPT')); // true
* @example
* // IP Address Routing Table
* // Add IP address prefixes and their corresponding routes
* const routes = {
* '192.168.1': 'LAN_SUBNET_1',
* '192.168.2': 'LAN_SUBNET_2',
* '10.0.0': 'PRIVATE_NETWORK_1',
* '10.0.1': 'PRIVATE_NETWORK_2'
* };
*
* const ipRoutingTable = new Trie<string>(Object.keys(routes));
*
* // Check IP address prefix matching
* console.log(ipRoutingTable.hasPrefix('192.168.1')); // true
* console.log(ipRoutingTable.hasPrefix('192.168.2')); // true
*
* // Validate IP address belongs to subnet
* const ip = '192.168.1.100';
* const subnet = ip.split('.').slice(0, 3).join('.');
* console.log(ipRoutingTable.hasPrefix(subnet)); // true
*/
export class Trie<R = any> extends IterableElementBase<string, R, Trie<R>> {
/**
* The constructor function for the Trie class.
* @param words: Iterable string Initialize the trie with a set of words
* @param options?: TrieOptions Allow the user to pass in options for the trie
* @return This
* The constructor initializes a Trie data structure with optional options and words provided as
* input.
* @param {Iterable<string> | Iterable<R>} words - The `words` parameter in the constructor is an
* iterable containing either strings or elements of type `R`. It is used to initialize the Trie with
* a list of words or elements. If no `words` are provided, an empty iterable is used as the default
* value.
* @param [options] - The `options` parameter in the constructor is an optional object that can
* contain configuration options for the Trie data structure. One of the options it can have is
* `caseSensitive`, which is a boolean value indicating whether the Trie should be case-sensitive or
* not. If `caseSensitive` is set to `
*/

@@ -111,9 +198,3 @@ constructor(words: Iterable<string> | Iterable<R> = [], options?: TrieOptions<R>) {

if (words) {
for (const word of words) {
if (this.toElementFn) {
this.add(this.toElementFn(word as R));
} else {
this.add(word as string);
}
}
this.addMany(words);
}

@@ -181,2 +262,26 @@ }

/**
* Time Complexity: O(n * l)
* Space Complexity: O(1)
*
* The `addMany` function in TypeScript takes an iterable of strings or elements of type R, converts
* them using a provided function if available, and adds them to a data structure while returning an
* array of boolean values indicating success.
* @param {Iterable<string> | Iterable<R>} words - The `words` parameter in the `addMany` function is
* an iterable that contains either strings or elements of type `R`.
* @returns The `addMany` method returns an array of boolean values indicating whether each word in
* the input iterable was successfully added to the data structure.
*/
addMany(words: Iterable<string> | Iterable<R> = []): boolean[] {
const ans: boolean[] = [];
for (const word of words) {
if (this.toElementFn) {
ans.push(this.add(this.toElementFn(word as R)));
} else {
ans.push(this.add(word as string));
}
}
return ans;
}
/**
* Time Complexity: O(l), where l is the length of the input word.

@@ -183,0 +288,0 @@ * Space Complexity: O(1) - Constant space.

3

src/index.ts

@@ -12,2 +12,3 @@ /**

export * from './types/common';
export * from './constants';
export * from './types/utils';
export * from './common';

2

src/types/data-structures/binary-tree/binary-tree.ts
import { BinaryTree, BinaryTreeNode } from '../../../data-structures';
import { IterationType, OptValue } from '../../common';
import { DFSOperation } from '../../../constants';
import { DFSOperation } from '../../../common';

@@ -5,0 +5,0 @@ export type BinaryTreeNodeNested<K, V> = BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, BinaryTreeNode<K, V, any>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

5

src/types/data-structures/binary-tree/bst.ts
import { BST, BSTNode } from '../../../data-structures';
import type { BinaryTreeOptions } from './binary-tree';
import { Comparator } from '../../common';
import { Comparable } from '../../utils';

@@ -10,3 +10,4 @@ export type BSTNodeNested<K, V> = BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, BSTNode<K, V, any>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

export type BSTOptions<K, V, R> = BinaryTreeOptions<K, V, R> & {
comparator?: Comparator<K>
extractComparable?: (key: K) => Comparable
isReverse?: boolean;
}

@@ -13,0 +14,0 @@

2

src/types/data-structures/binary-tree/rb-tree.ts

@@ -10,2 +10,2 @@ import { RedBlackTree, RedBlackTreeNode } from '../../../data-structures';

export type RBTreeOptions<K, V, R> = BSTOptions<K, V, R> & {};
export type RBTreeOptions<K, V, R> = Omit<BSTOptions<K, V, R>, 'isReverse'> & {};

26

src/types/utils/utils.ts

@@ -10,15 +10,21 @@ export type ToThunkFn<R = any> = () => R;

export type Arithmetic = number | bigint;
export type ComparablePrimitive = number | bigint | string | boolean;
// TODO type safety looks not strict
export type ComparableObject = { [key in string]: any } & (
| {
valueOf: () => ComparablePrimitive | ComparableObject;
toString?: () => string;
}
| {
toString: () => string;
}
);
export interface BaseComparableObject {
[key: string]: unknown;
}
export interface ValueComparableObject extends BaseComparableObject {
valueOf: () => ComparablePrimitive | ValueComparableObject;
toString?: () => string;
}
export interface StringComparableObject extends BaseComparableObject {
toString: () => string;
}
export type ComparableObject = ValueComparableObject | StringComparableObject;
export type Comparable = ComparablePrimitive | Date | ComparableObject;

6

src/utils/utils.ts

@@ -229,3 +229,4 @@ /**

const valueType = typeof value;
if (valueType === 'number') return !Number.isNaN(value);
if (valueType === 'number') return true;
// if (valueType === 'number') return !Number.isNaN(value);
return valueType === 'bigint' || valueType === 'string' || valueType === 'boolean';

@@ -278,3 +279,4 @@ }

if (typeof value !== 'object') return false;
if (value instanceof Date) return !Number.isNaN(value.getTime());
if (value instanceof Date) return true;
// if (value instanceof Date) return !Number.isNaN(value.getTime());
if (isForceObjectComparable) return true;

@@ -281,0 +283,0 @@ const comparableValue = tryObjectToPrimitive(value);

dist/data-structures/binary-tree/binary-tree.js

Sorry, the diff of this file is too big to display

src/data-structures/binary-tree/binary-tree.ts

Sorry, the diff of this file is too big to display

SocketSocket SOC 2 Logo

Product

  • Package Alerts
  • Integrations
  • Docs
  • Pricing
  • FAQ
  • Roadmap
  • Changelog

About

Packages

npm

Go

Maven

PyPI

Rubygems

Stay in touch

Get open source security insights delivered straight into your inbox.

  • Terms
  • Privacy
  • Security

Made with ⚡️ by Socket Inc