priority-queue-typed
Advanced tools
Comparing version 1.48.2 to 1.48.3
@@ -9,8 +9,8 @@ /** | ||
import { BST, BSTNode } from './bst'; | ||
import type { AVLTreeNested, AVLTreeNodeNested, AVLTreeOptions, BiTreeDeleteResult, BSTNodeKeyOrNode, BTNKey, BTNodeExemplar } from '../../types'; | ||
import type { AVLTreeNested, AVLTreeNodeNested, AVLTreeOptions, BiTreeDeleteResult, BSTNodeKeyOrNode, BTNodeExemplar } from '../../types'; | ||
import { BTNCallback } from '../../types'; | ||
import { IBinaryTree } from '../../interfaces'; | ||
export declare class AVLTreeNode<V = any, N extends AVLTreeNode<V, N> = AVLTreeNodeNested<V>> extends BSTNode<V, N> { | ||
export declare class AVLTreeNode<K = any, V = any, N extends AVLTreeNode<K, V, N> = AVLTreeNodeNested<K, V>> extends BSTNode<K, V, N> { | ||
height: number; | ||
constructor(key: BTNKey, value?: V); | ||
constructor(key: K, value?: V); | ||
} | ||
@@ -27,6 +27,6 @@ /** | ||
*/ | ||
export declare class AVLTree<V = any, N extends AVLTreeNode<V, N> = AVLTreeNode<V, AVLTreeNodeNested<V>>, TREE extends AVLTree<V, N, TREE> = AVLTree<V, N, AVLTreeNested<V, N>>> extends BST<V, N, TREE> implements IBinaryTree<V, N, TREE> { | ||
export declare class AVLTree<K = any, V = any, N extends AVLTreeNode<K, V, N> = AVLTreeNode<K, V, AVLTreeNodeNested<K, V>>, TREE extends AVLTree<K, V, N, TREE> = AVLTree<K, V, N, AVLTreeNested<K, V, N>>> extends BST<K, V, N, TREE> implements IBinaryTree<K, V, N, TREE> { | ||
/** | ||
* The constructor function initializes an AVLTree object with optional elements and options. | ||
* @param [elements] - The `elements` parameter is an optional iterable of `BTNodeExemplar<V, N>` | ||
* @param [elements] - The `elements` parameter is an optional iterable of `BTNodeExemplar<K, V, N>` | ||
* objects. It represents a collection of elements that will be added to the AVL tree during | ||
@@ -38,6 +38,6 @@ * initialization. | ||
*/ | ||
constructor(elements?: Iterable<BTNodeExemplar<V, N>>, options?: Partial<AVLTreeOptions>); | ||
constructor(elements?: Iterable<BTNodeExemplar<K, V, N>>, options?: Partial<AVLTreeOptions<K>>); | ||
/** | ||
* The function creates a new AVL tree node with the specified key and value. | ||
* @param {BTNKey} key - The key parameter is the key value that will be associated with | ||
* @param {K} key - The key parameter is the key value that will be associated with | ||
* the new node. It is used to determine the position of the node in the binary search tree. | ||
@@ -49,3 +49,3 @@ * @param [value] - The parameter `value` is an optional value that can be assigned to the node. It is of | ||
*/ | ||
createNode(key: BTNKey, value?: V): N; | ||
createNode(key: K, value?: V): N; | ||
/** | ||
@@ -58,9 +58,9 @@ * The function creates a new AVL tree with the specified options and returns it. | ||
*/ | ||
createTree(options?: AVLTreeOptions): TREE; | ||
createTree(options?: AVLTreeOptions<K>): TREE; | ||
/** | ||
* The function checks if an exemplar is an instance of AVLTreeNode. | ||
* @param exemplar - The `exemplar` parameter is of type `BTNodeExemplar<V, N>`. | ||
* @param exemplar - The `exemplar` parameter is of type `BTNodeExemplar<K, V, N>`. | ||
* @returns a boolean value indicating whether the exemplar is an instance of the AVLTreeNode class. | ||
*/ | ||
isNode(exemplar: BTNodeExemplar<V, N>): exemplar is N; | ||
isNode(exemplar: BTNodeExemplar<K, V, N>): exemplar is N; | ||
/** | ||
@@ -80,3 +80,3 @@ * Time Complexity: O(log n) - logarithmic time, where "n" is the number of nodes in the tree. The add method of the superclass (BST) has logarithmic time complexity. | ||
*/ | ||
add(keyOrNodeOrEntry: BTNodeExemplar<V, N>): N | undefined; | ||
add(keyOrNodeOrEntry: BTNodeExemplar<K, V, N>): N | undefined; | ||
/** | ||
@@ -105,5 +105,5 @@ * Time Complexity: O(log n) - logarithmic time, where "n" is the number of nodes in the tree. The add method of the superclass (BST) has logarithmic time complexity. | ||
* tree. | ||
* @param {BTNKey | N | undefined} srcNode - The `srcNode` parameter represents the source node that | ||
* needs to be swapped with the destination node. It can be of type `BTNKey`, `N`, or `undefined`. | ||
* @param {BTNKey | N | undefined} destNode - The `destNode` parameter represents the destination | ||
* @param {K | N | undefined} srcNode - The `srcNode` parameter represents the source node that | ||
* needs to be swapped with the destination node. It can be of type `K`, `N`, or `undefined`. | ||
* @param {K | N | undefined} destNode - The `destNode` parameter represents the destination | ||
* node where the values from the source node will be swapped to. | ||
@@ -113,3 +113,3 @@ * @returns either the `destNode` object if both `srcNode` and `destNode` are defined, or `undefined` | ||
*/ | ||
protected _swapProperties(srcNode: BSTNodeKeyOrNode<N>, destNode: BSTNodeKeyOrNode<N>): N | undefined; | ||
protected _swapProperties(srcNode: BSTNodeKeyOrNode<K, N>, destNode: BSTNodeKeyOrNode<K, N>): N | undefined; | ||
/** | ||
@@ -116,0 +116,0 @@ * Time Complexity: O(1) - constant time, as it performs a fixed number of operations. |
@@ -32,3 +32,3 @@ "use strict"; | ||
* The constructor function initializes an AVLTree object with optional elements and options. | ||
* @param [elements] - The `elements` parameter is an optional iterable of `BTNodeExemplar<V, N>` | ||
* @param [elements] - The `elements` parameter is an optional iterable of `BTNodeExemplar<K, V, N>` | ||
* objects. It represents a collection of elements that will be added to the AVL tree during | ||
@@ -47,3 +47,3 @@ * initialization. | ||
* The function creates a new AVL tree node with the specified key and value. | ||
* @param {BTNKey} key - The key parameter is the key value that will be associated with | ||
* @param {K} key - The key parameter is the key value that will be associated with | ||
* the new node. It is used to determine the position of the node in the binary search tree. | ||
@@ -66,7 +66,7 @@ * @param [value] - The parameter `value` is an optional value that can be assigned to the node. It is of | ||
createTree(options) { | ||
return new AVLTree([], Object.assign({ iterationType: this.iterationType, comparator: this.comparator }, options)); | ||
return new AVLTree([], Object.assign({ iterationType: this.iterationType, variant: this.variant }, options)); | ||
} | ||
/** | ||
* The function checks if an exemplar is an instance of AVLTreeNode. | ||
* @param exemplar - The `exemplar` parameter is of type `BTNodeExemplar<V, N>`. | ||
* @param exemplar - The `exemplar` parameter is of type `BTNodeExemplar<K, V, N>`. | ||
* @returns a boolean value indicating whether the exemplar is an instance of the AVLTreeNode class. | ||
@@ -132,5 +132,5 @@ */ | ||
* tree. | ||
* @param {BTNKey | N | undefined} srcNode - The `srcNode` parameter represents the source node that | ||
* needs to be swapped with the destination node. It can be of type `BTNKey`, `N`, or `undefined`. | ||
* @param {BTNKey | N | undefined} destNode - The `destNode` parameter represents the destination | ||
* @param {K | N | undefined} srcNode - The `srcNode` parameter represents the source node that | ||
* needs to be swapped with the destination node. It can be of type `K`, `N`, or `undefined`. | ||
* @param {K | N | undefined} destNode - The `destNode` parameter represents the destination | ||
* node where the values from the source node will be swapped to. | ||
@@ -137,0 +137,0 @@ * @returns either the `destNode` object if both `srcNode` and `destNode` are defined, or `undefined` |
@@ -8,3 +8,3 @@ /** | ||
*/ | ||
import type { BinaryTreeNodeNested, BinaryTreeOptions, BTNCallback, BTNKey, BTNodeEntry, BTNodeExemplar, BTNodeKeyOrNode } from '../../types'; | ||
import type { BinaryTreeNodeNested, BinaryTreeOptions, BTNCallback, BTNodeEntry, BTNodeExemplar, BTNodeKeyOrNode } from '../../types'; | ||
import { BinaryTreeNested, BinaryTreePrintOptions, BiTreeDeleteResult, DFSOrderPattern, FamilyPosition, IterationType, NodeDisplayLayout, PairCallback } from '../../types'; | ||
@@ -18,7 +18,7 @@ import { IBinaryTree } from '../../interfaces'; | ||
*/ | ||
export declare class BinaryTreeNode<V = any, N extends BinaryTreeNode<V, N> = BinaryTreeNode<V, BinaryTreeNodeNested<V>>> { | ||
key: BTNKey; | ||
export declare class BinaryTreeNode<K = any, V = any, N extends BinaryTreeNode<K, V, N> = BinaryTreeNode<K, V, BinaryTreeNodeNested<K, V>>> { | ||
key: K; | ||
value?: V; | ||
parent?: N; | ||
constructor(key: BTNKey, value?: V); | ||
constructor(key: K, value?: V); | ||
protected _left?: N | null; | ||
@@ -47,3 +47,3 @@ get left(): N | null | undefined; | ||
*/ | ||
export declare class BinaryTree<V = any, N extends BinaryTreeNode<V, N> = BinaryTreeNode<V, BinaryTreeNodeNested<V>>, TREE extends BinaryTree<V, N, TREE> = BinaryTree<V, N, BinaryTreeNested<V, N>>> extends IterablePairBase<BTNKey, V | undefined> implements IBinaryTree<V, N, TREE> { | ||
export declare class BinaryTree<K = any, V = any, N extends BinaryTreeNode<K, V, N> = BinaryTreeNode<K, V, BinaryTreeNodeNested<K, V>>, TREE extends BinaryTree<K, V, N, TREE> = BinaryTree<K, V, N, BinaryTreeNested<K, V, N>>> extends IterablePairBase<K, V | undefined> implements IBinaryTree<K, V, N, TREE> { | ||
iterationType: IterationType; | ||
@@ -59,3 +59,5 @@ /** | ||
*/ | ||
constructor(elements?: Iterable<BTNodeExemplar<V, N>>, options?: Partial<BinaryTreeOptions>); | ||
constructor(elements?: Iterable<BTNodeExemplar<K, V, N>>, options?: Partial<BinaryTreeOptions<K>>); | ||
protected _extractor: (key: K) => number; | ||
get extractor(): (key: K) => number; | ||
protected _root?: N | null; | ||
@@ -67,7 +69,7 @@ get root(): N | null | undefined; | ||
* Creates a new instance of BinaryTreeNode with the given key and value. | ||
* @param {BTNKey} key - The key for the new node. | ||
* @param {K} key - The key for the new node. | ||
* @param {V} value - The value for the new node. | ||
* @returns {N} - The newly created BinaryTreeNode. | ||
*/ | ||
createNode(key: BTNKey, value?: V): N; | ||
createNode(key: K, value?: V): N; | ||
/** | ||
@@ -80,24 +82,24 @@ * The function creates a binary tree with the given options. | ||
*/ | ||
createTree(options?: Partial<BinaryTreeOptions>): TREE; | ||
createTree(options?: Partial<BinaryTreeOptions<K>>): TREE; | ||
/** | ||
* The function "isNode" checks if an exemplar is an instance of the BinaryTreeNode class. | ||
* @param exemplar - The `exemplar` parameter is a variable of type `BTNodeExemplar<V, N>`. | ||
* @param exemplar - The `exemplar` parameter is a variable of type `BTNodeExemplar<K, V,N>`. | ||
* @returns a boolean value indicating whether the exemplar is an instance of the class N. | ||
*/ | ||
isNode(exemplar: BTNodeExemplar<V, N>): exemplar is N; | ||
isNode(exemplar: BTNodeExemplar<K, V, N>): exemplar is N; | ||
/** | ||
* The function `exemplarToNode` converts an exemplar of a binary tree node into an actual node | ||
* object. | ||
* @param exemplar - BTNodeExemplar<V, N> - A generic type representing the exemplar parameter of the | ||
* @param exemplar - BTNodeExemplar<K, V,N> - A generic type representing the exemplar parameter of the | ||
* function. It can be any type. | ||
* @returns a value of type `N` (which represents a node), or `null`, or `undefined`. | ||
*/ | ||
exemplarToNode(exemplar: BTNodeExemplar<V, N>): N | null | undefined; | ||
exemplarToNode(exemplar: BTNodeExemplar<K, V, N>): N | null | undefined; | ||
/** | ||
* The function checks if a given value is an entry in a binary tree node. | ||
* @param kne - BTNodeExemplar<V, N> - A generic type representing a node in a binary tree. It has | ||
* @param kne - BTNodeExemplar<K, V,N> - A generic type representing a node in a binary tree. It has | ||
* two type parameters V and N, representing the value and node type respectively. | ||
* @returns a boolean value. | ||
*/ | ||
isEntry(kne: BTNodeExemplar<V, N>): kne is BTNodeEntry<V>; | ||
isEntry(kne: BTNodeExemplar<K, V, N>): kne is BTNodeEntry<K, V>; | ||
/** | ||
@@ -115,3 +117,3 @@ * Time Complexity O(log n) - O(n) | ||
*/ | ||
add(keyOrNodeOrEntry: BTNodeExemplar<V, N>): N | null | undefined; | ||
add(keyOrNodeOrEntry: BTNodeExemplar<K, V, N>): N | null | undefined; | ||
/** | ||
@@ -129,7 +131,7 @@ * Time Complexity: O(k log n) - O(k * n) | ||
* @param nodes - The `nodes` parameter is an iterable (such as an array or a set) of | ||
* `BTNodeExemplar<V, N>` objects. | ||
* `BTNodeExemplar<K, V,N>` objects. | ||
* @returns The function `addMany` returns an array of values, where each value is either of type | ||
* `N`, `null`, or `undefined`. | ||
*/ | ||
addMany(nodes: Iterable<BTNodeExemplar<V, N>>): (N | null | undefined)[]; | ||
addMany(nodes: Iterable<BTNodeExemplar<K, V, N>>): (N | null | undefined)[]; | ||
/** | ||
@@ -147,3 +149,3 @@ * Time Complexity: O(k * n) "n" is the number of nodes in the tree, and "k" is the number of keys to be inserted. | ||
*/ | ||
refill(nodesOrKeysOrEntries: Iterable<BTNodeExemplar<V, N>>): void; | ||
refill(nodesOrKeysOrEntries: Iterable<BTNodeExemplar<K, V, N>>): void; | ||
/** | ||
@@ -153,3 +155,3 @@ * Time Complexity: O(k * n) "n" is the number of nodes in the tree, and "k" is the number of keys to be inserted. | ||
*/ | ||
delete<C extends BTNCallback<N, BTNKey>>(identifier: BTNKey, callback?: C): BiTreeDeleteResult<N>[]; | ||
delete<C extends BTNCallback<N, K>>(identifier: K, callback?: C): BiTreeDeleteResult<N>[]; | ||
delete<C extends BTNCallback<N, N>>(identifier: N | null | undefined, callback?: C): BiTreeDeleteResult<N>[]; | ||
@@ -166,11 +168,11 @@ delete<C extends BTNCallback<N>>(identifier: ReturnType<C>, callback: C): BiTreeDeleteResult<N>[]; | ||
* The function calculates the depth of a given node in a binary tree. | ||
* @param {BTNKey | N | null | undefined} distNode - The `distNode` parameter represents the node in | ||
* the binary tree whose depth we want to find. It can be of type `BTNKey`, `N`, `null`, or | ||
* @param {K | N | null | undefined} distNode - The `distNode` parameter represents the node in | ||
* the binary tree whose depth we want to find. It can be of type `K`, `N`, `null`, or | ||
* `undefined`. | ||
* @param {BTNKey | N | null | undefined} beginRoot - The `beginRoot` parameter is the starting node | ||
* from which we want to calculate the depth. It can be either a `BTNKey` (binary tree node key) or | ||
* @param {K | N | null | undefined} beginRoot - The `beginRoot` parameter is the starting node | ||
* from which we want to calculate the depth. It can be either a `K` (binary tree node key) or | ||
* `N` (binary tree node) or `null` or `undefined`. If no value is provided for `beginRoot | ||
* @returns the depth of the `distNode` relative to the `beginRoot`. | ||
*/ | ||
getDepth(distNode: BTNodeKeyOrNode<N>, beginRoot?: BTNodeKeyOrNode<N>): number; | ||
getDepth(distNode: BTNodeKeyOrNode<K, N>, beginRoot?: BTNodeKeyOrNode<K, N>): number; | ||
/** | ||
@@ -186,5 +188,5 @@ * Time Complexity: O(n) | ||
* iterative traversal. | ||
* @param {BTNKey | N | null | undefined} beginRoot - The `beginRoot` parameter represents the | ||
* @param {K | N | null | undefined} beginRoot - The `beginRoot` parameter represents the | ||
* starting node of the binary tree from which we want to calculate the height. It can be of type | ||
* `BTNKey`, `N`, `null`, or `undefined`. If not provided, it defaults to `this.root`. | ||
* `K`, `N`, `null`, or `undefined`. If not provided, it defaults to `this.root`. | ||
* @param iterationType - The `iterationType` parameter is used to determine whether to calculate the | ||
@@ -195,3 +197,3 @@ * height of the tree using a recursive approach or an iterative approach. It can have two possible | ||
*/ | ||
getHeight(beginRoot?: BTNodeKeyOrNode<N>, iterationType?: IterationType): number; | ||
getHeight(beginRoot?: BTNodeKeyOrNode<K, N>, iterationType?: IterationType): number; | ||
/** | ||
@@ -208,5 +210,5 @@ * Time Complexity: O(n) | ||
* recursive or iterative approach. | ||
* @param {BTNKey | N | null | undefined} beginRoot - The `beginRoot` parameter represents the | ||
* @param {K | N | null | undefined} beginRoot - The `beginRoot` parameter represents the | ||
* starting node of the binary tree from which we want to calculate the minimum height. It can be of | ||
* type `BTNKey`, `N`, `null`, or `undefined`. If no value is provided, it defaults to `this.root`. | ||
* type `K`, `N`, `null`, or `undefined`. If no value is provided, it defaults to `this.root`. | ||
* @param iterationType - The `iterationType` parameter is used to determine the method of iteration | ||
@@ -216,3 +218,3 @@ * to calculate the minimum height of a binary tree. It can have two possible values: | ||
*/ | ||
getMinHeight(beginRoot?: BTNodeKeyOrNode<N>, iterationType?: IterationType): number; | ||
getMinHeight(beginRoot?: BTNodeKeyOrNode<K, N>, iterationType?: IterationType): number; | ||
/** | ||
@@ -229,8 +231,8 @@ * Time Complexity: O(n) | ||
* height of the tree. | ||
* @param {BTNKey | N | null | undefined} beginRoot - The `beginRoot` parameter is the starting point | ||
* for calculating the height and minimum height of a binary tree. It can be either a `BTNKey` (a key | ||
* @param {K | N | null | undefined} beginRoot - The `beginRoot` parameter is the starting point | ||
* for calculating the height and minimum height of a binary tree. It can be either a `K` (a key | ||
* value of a binary tree node), `N` (a node of a binary tree), `null`, or `undefined`. If | ||
* @returns a boolean value. | ||
*/ | ||
isPerfectlyBalanced(beginRoot?: BTNodeKeyOrNode<N>): boolean; | ||
isPerfectlyBalanced(beginRoot?: BTNodeKeyOrNode<K, N>): boolean; | ||
/** | ||
@@ -240,5 +242,5 @@ * Time Complexity: O(n) | ||
*/ | ||
getNodes<C extends BTNCallback<N, BTNKey>>(identifier: BTNKey, callback?: C, onlyOne?: boolean, beginRoot?: BTNodeKeyOrNode<N>, iterationType?: IterationType): N[]; | ||
getNodes<C extends BTNCallback<N, N>>(identifier: N | null | undefined, callback?: C, onlyOne?: boolean, beginRoot?: BTNodeKeyOrNode<N>, iterationType?: IterationType): N[]; | ||
getNodes<C extends BTNCallback<N>>(identifier: ReturnType<C>, callback: C, onlyOne?: boolean, beginRoot?: BTNodeKeyOrNode<N>, iterationType?: IterationType): N[]; | ||
getNodes<C extends BTNCallback<N, K>>(identifier: K, callback?: C, onlyOne?: boolean, beginRoot?: BTNodeKeyOrNode<K, N>, iterationType?: IterationType): N[]; | ||
getNodes<C extends BTNCallback<N, N>>(identifier: N | null | undefined, callback?: C, onlyOne?: boolean, beginRoot?: BTNodeKeyOrNode<K, N>, iterationType?: IterationType): N[]; | ||
getNodes<C extends BTNCallback<N>>(identifier: ReturnType<C>, callback: C, onlyOne?: boolean, beginRoot?: BTNodeKeyOrNode<K, N>, iterationType?: IterationType): N[]; | ||
/** | ||
@@ -248,5 +250,5 @@ * Time Complexity: O(n) | ||
*/ | ||
has<C extends BTNCallback<N, BTNKey>>(identifier: BTNKey, callback?: C, beginRoot?: BTNodeKeyOrNode<N>, iterationType?: IterationType): boolean; | ||
has<C extends BTNCallback<N, N>>(identifier: N | null | undefined, callback?: C, beginRoot?: BTNodeKeyOrNode<N>, iterationType?: IterationType): boolean; | ||
has<C extends BTNCallback<N>>(identifier: ReturnType<C> | null | undefined, callback: C, beginRoot?: BTNodeKeyOrNode<N>, iterationType?: IterationType): boolean; | ||
has<C extends BTNCallback<N, K>>(identifier: K, callback?: C, beginRoot?: BTNodeKeyOrNode<K, N>, iterationType?: IterationType): boolean; | ||
has<C extends BTNCallback<N, N>>(identifier: N | null | undefined, callback?: C, beginRoot?: BTNodeKeyOrNode<K, N>, iterationType?: IterationType): boolean; | ||
has<C extends BTNCallback<N>>(identifier: ReturnType<C> | null | undefined, callback: C, beginRoot?: BTNodeKeyOrNode<K, N>, iterationType?: IterationType): boolean; | ||
/** | ||
@@ -256,5 +258,5 @@ * Time Complexity: O(n) | ||
*/ | ||
getNode<C extends BTNCallback<N, BTNKey>>(identifier: BTNKey, callback?: C, beginRoot?: BTNodeKeyOrNode<N>, iterationType?: IterationType): N | null | undefined; | ||
getNode<C extends BTNCallback<N, N>>(identifier: N | null | undefined, callback?: C, beginRoot?: BTNodeKeyOrNode<N>, iterationType?: IterationType): N | null | undefined; | ||
getNode<C extends BTNCallback<N>>(identifier: ReturnType<C>, callback: C, beginRoot?: BTNodeKeyOrNode<N>, iterationType?: IterationType): N | null | undefined; | ||
getNode<C extends BTNCallback<N, K>>(identifier: K, callback?: C, beginRoot?: BTNodeKeyOrNode<K, N>, iterationType?: IterationType): N | null | undefined; | ||
getNode<C extends BTNCallback<N, N>>(identifier: N | null | undefined, callback?: C, beginRoot?: BTNodeKeyOrNode<K, N>, iterationType?: IterationType): N | null | undefined; | ||
getNode<C extends BTNCallback<N>>(identifier: ReturnType<C>, callback: C, beginRoot?: BTNodeKeyOrNode<K, N>, iterationType?: IterationType): N | null | undefined; | ||
/** | ||
@@ -270,3 +272,3 @@ * Time Complexity: O(n) | ||
* recursive or iterative iteration. | ||
* @param {BTNKey} key - The `key` parameter is the key value that we are searching for in the tree. | ||
* @param {K} key - The `key` parameter is the key value that we are searching for in the tree. | ||
* It is used to find the node with the matching key value. | ||
@@ -279,3 +281,3 @@ * @param iterationType - The `iterationType` parameter is used to determine whether the search for | ||
*/ | ||
getNodeByKey(key: BTNKey, iterationType?: IterationType): N | undefined; | ||
getNodeByKey(key: K, iterationType?: IterationType): N | undefined; | ||
/** | ||
@@ -288,3 +290,3 @@ * Time Complexity: O(n) | ||
* key, otherwise it returns the key itself. | ||
* @param {BTNKey | N | null | undefined} key - The `key` parameter can be of type `BTNKey`, `N`, | ||
* @param {K | N | null | undefined} key - The `key` parameter can be of type `K`, `N`, | ||
* `null`, or `undefined`. It represents a key used to identify a node in a binary tree. | ||
@@ -297,6 +299,6 @@ * @param iterationType - The `iterationType` parameter is an optional parameter that specifies the | ||
*/ | ||
ensureNode(key: BTNodeKeyOrNode<N>, iterationType?: IterationType): N | null | undefined; | ||
get<C extends BTNCallback<N, BTNKey>>(identifier: BTNKey, callback?: C, beginRoot?: BTNodeKeyOrNode<N>, iterationType?: IterationType): V | undefined; | ||
get<C extends BTNCallback<N, N>>(identifier: N | null | undefined, callback?: C, beginRoot?: BTNodeKeyOrNode<N>, iterationType?: IterationType): V | undefined; | ||
get<C extends BTNCallback<N>>(identifier: ReturnType<C>, callback: C, beginRoot?: BTNodeKeyOrNode<N>, iterationType?: IterationType): V | undefined; | ||
ensureNode(key: BTNodeKeyOrNode<K, N>, iterationType?: IterationType): N | null | undefined; | ||
get<C extends BTNCallback<N, K>>(identifier: K, callback?: C, beginRoot?: BTNodeKeyOrNode<K, N>, iterationType?: IterationType): V | undefined; | ||
get<C extends BTNCallback<N, N>>(identifier: N | null | undefined, callback?: C, beginRoot?: BTNodeKeyOrNode<K, N>, iterationType?: IterationType): V | undefined; | ||
get<C extends BTNCallback<N>>(identifier: ReturnType<C>, callback: C, beginRoot?: BTNodeKeyOrNode<K, N>, iterationType?: IterationType): V | undefined; | ||
/** | ||
@@ -321,4 +323,4 @@ * Time Complexity: O(n) | ||
* structure, with the option to reverse the order of the nodes. | ||
* @param {BTNKey | N | null | undefined} beginRoot - The `beginRoot` parameter represents the | ||
* starting node from which you want to find the path to the root. It can be of type `BTNKey`, `N`, | ||
* @param {K | N | null | undefined} beginRoot - The `beginRoot` parameter represents the | ||
* starting node from which you want to find the path to the root. It can be of type `K`, `N`, | ||
* `null`, or `undefined`. | ||
@@ -330,3 +332,3 @@ * @param [isReverse=true] - The `isReverse` parameter is a boolean flag that determines whether the | ||
*/ | ||
getPathToRoot(beginRoot: BTNodeKeyOrNode<N>, isReverse?: boolean): N[]; | ||
getPathToRoot(beginRoot: BTNodeKeyOrNode<K, N>, isReverse?: boolean): N[]; | ||
/** | ||
@@ -342,4 +344,4 @@ * Time Complexity: O(log n) | ||
* iteratively. | ||
* @param {BTNKey | N | null | undefined} beginRoot - The `beginRoot` parameter is the starting point | ||
* for finding the leftmost node in a binary tree. It can be either a `BTNKey` (a key value), `N` (a | ||
* @param {K | N | null | undefined} beginRoot - The `beginRoot` parameter is the starting point | ||
* for finding the leftmost node in a binary tree. It can be either a `K` (a key value), `N` (a | ||
* node), `null`, or `undefined`. If not provided, it defaults to `this.root`, | ||
@@ -351,3 +353,3 @@ * @param iterationType - The `iterationType` parameter is used to determine the type of iteration to | ||
*/ | ||
getLeftMost(beginRoot?: BTNodeKeyOrNode<N>, iterationType?: IterationType): N | null | undefined; | ||
getLeftMost(beginRoot?: BTNodeKeyOrNode<K, N>, iterationType?: IterationType): N | null | undefined; | ||
/** | ||
@@ -363,4 +365,4 @@ * Time Complexity: O(log n) | ||
* iteratively. | ||
* @param {BTNKey | N | null | undefined} beginRoot - The `beginRoot` parameter represents the | ||
* starting node from which we want to find the rightmost node. It can be of type `BTNKey`, `N`, | ||
* @param {K | N | null | undefined} beginRoot - The `beginRoot` parameter represents the | ||
* starting node from which we want to find the rightmost node. It can be of type `K`, `N`, | ||
* `null`, or `undefined`. If not provided, it defaults to `this.root`, which is a property of the | ||
@@ -373,3 +375,3 @@ * current object. | ||
*/ | ||
getRightMost(beginRoot?: BTNodeKeyOrNode<N>, iterationType?: IterationType): N | null | undefined; | ||
getRightMost(beginRoot?: BTNodeKeyOrNode<K, N>, iterationType?: IterationType): N | null | undefined; | ||
/** | ||
@@ -384,3 +386,3 @@ * Time Complexity: O(log n) | ||
* The function `isSubtreeBST` checks if a given binary tree is a valid binary search tree. | ||
* @param {BTNKey | N | null | undefined} beginRoot - The `beginRoot` parameter represents the root | ||
* @param {K | N | null | undefined} beginRoot - The `beginRoot` parameter represents the root | ||
* node of the binary search tree (BST) that you want to check if it is a subtree of another BST. | ||
@@ -392,3 +394,3 @@ * @param iterationType - The `iterationType` parameter is an optional parameter that specifies the | ||
*/ | ||
isSubtreeBST(beginRoot: BTNodeKeyOrNode<N>, iterationType?: IterationType): boolean; | ||
isSubtreeBST(beginRoot: BTNodeKeyOrNode<K, N>, iterationType?: IterationType): boolean; | ||
/** | ||
@@ -414,5 +416,5 @@ * Time Complexity: O(n) | ||
*/ | ||
subTreeTraverse<C extends BTNCallback<N>>(callback?: C, beginRoot?: BTNodeKeyOrNode<N>, iterationType?: IterationType, includeNull?: false): ReturnType<C>[]; | ||
subTreeTraverse<C extends BTNCallback<N>>(callback?: C, beginRoot?: BTNodeKeyOrNode<N>, iterationType?: IterationType, includeNull?: undefined): ReturnType<C>[]; | ||
subTreeTraverse<C extends BTNCallback<N | null | undefined>>(callback?: C, beginRoot?: BTNodeKeyOrNode<N>, iterationType?: IterationType, includeNull?: true): ReturnType<C>[]; | ||
subTreeTraverse<C extends BTNCallback<N>>(callback?: C, beginRoot?: BTNodeKeyOrNode<K, N>, iterationType?: IterationType, includeNull?: false): ReturnType<C>[]; | ||
subTreeTraverse<C extends BTNCallback<N>>(callback?: C, beginRoot?: BTNodeKeyOrNode<K, N>, iterationType?: IterationType, includeNull?: undefined): ReturnType<C>[]; | ||
subTreeTraverse<C extends BTNCallback<N | null | undefined>>(callback?: C, beginRoot?: BTNodeKeyOrNode<K, N>, iterationType?: IterationType, includeNull?: true): ReturnType<C>[]; | ||
/** | ||
@@ -442,3 +444,3 @@ * Time complexity: O(n) | ||
/** | ||
* The function "isNodeKey" checks if a potential key is a number. | ||
* The function "isNotNodeInstance" checks if a potential key is a number. | ||
* @param {any} potentialKey - The potentialKey parameter is of type any, which means it can be any | ||
@@ -448,6 +450,6 @@ * data type. | ||
*/ | ||
isNodeKey(potentialKey: any): potentialKey is number; | ||
dfs<C extends BTNCallback<N>>(callback?: C, pattern?: DFSOrderPattern, beginRoot?: BTNodeKeyOrNode<N>, iterationType?: IterationType, includeNull?: false): ReturnType<C>[]; | ||
dfs<C extends BTNCallback<N>>(callback?: C, pattern?: DFSOrderPattern, beginRoot?: BTNodeKeyOrNode<N>, iterationType?: IterationType, includeNull?: undefined): ReturnType<C>[]; | ||
dfs<C extends BTNCallback<N | null | undefined>>(callback?: C, pattern?: DFSOrderPattern, beginRoot?: BTNodeKeyOrNode<N>, iterationType?: IterationType, includeNull?: true): ReturnType<C>[]; | ||
isNotNodeInstance(potentialKey: BTNodeKeyOrNode<K, N>): potentialKey is K; | ||
dfs<C extends BTNCallback<N>>(callback?: C, pattern?: DFSOrderPattern, beginRoot?: BTNodeKeyOrNode<K, N>, iterationType?: IterationType, includeNull?: false): ReturnType<C>[]; | ||
dfs<C extends BTNCallback<N>>(callback?: C, pattern?: DFSOrderPattern, beginRoot?: BTNodeKeyOrNode<K, N>, iterationType?: IterationType, includeNull?: undefined): ReturnType<C>[]; | ||
dfs<C extends BTNCallback<N | null | undefined>>(callback?: C, pattern?: DFSOrderPattern, beginRoot?: BTNodeKeyOrNode<K, N>, iterationType?: IterationType, includeNull?: true): ReturnType<C>[]; | ||
/** | ||
@@ -457,5 +459,5 @@ * Time complexity: O(n) | ||
*/ | ||
bfs<C extends BTNCallback<N>>(callback?: C, beginRoot?: BTNodeKeyOrNode<N>, iterationType?: IterationType, includeNull?: false): ReturnType<C>[]; | ||
bfs<C extends BTNCallback<N>>(callback?: C, beginRoot?: BTNodeKeyOrNode<N>, iterationType?: IterationType, includeNull?: undefined): ReturnType<C>[]; | ||
bfs<C extends BTNCallback<N | null | undefined>>(callback?: C, beginRoot?: BTNodeKeyOrNode<N>, iterationType?: IterationType, includeNull?: true): ReturnType<C>[]; | ||
bfs<C extends BTNCallback<N>>(callback?: C, beginRoot?: BTNodeKeyOrNode<K, N>, iterationType?: IterationType, includeNull?: false): ReturnType<C>[]; | ||
bfs<C extends BTNCallback<N>>(callback?: C, beginRoot?: BTNodeKeyOrNode<K, N>, iterationType?: IterationType, includeNull?: undefined): ReturnType<C>[]; | ||
bfs<C extends BTNCallback<N | null | undefined>>(callback?: C, beginRoot?: BTNodeKeyOrNode<K, N>, iterationType?: IterationType, includeNull?: true): ReturnType<C>[]; | ||
/** | ||
@@ -465,5 +467,5 @@ * Time complexity: O(n) | ||
*/ | ||
listLevels<C extends BTNCallback<N>>(callback?: C, beginRoot?: BTNodeKeyOrNode<N>, iterationType?: IterationType, includeNull?: false): ReturnType<C>[][]; | ||
listLevels<C extends BTNCallback<N>>(callback?: C, beginRoot?: BTNodeKeyOrNode<N>, iterationType?: IterationType, includeNull?: undefined): ReturnType<C>[][]; | ||
listLevels<C extends BTNCallback<N | null | undefined>>(callback?: C, beginRoot?: BTNodeKeyOrNode<N>, iterationType?: IterationType, includeNull?: true): ReturnType<C>[][]; | ||
listLevels<C extends BTNCallback<N>>(callback?: C, beginRoot?: BTNodeKeyOrNode<K, N>, iterationType?: IterationType, includeNull?: false): ReturnType<C>[][]; | ||
listLevels<C extends BTNCallback<N>>(callback?: C, beginRoot?: BTNodeKeyOrNode<K, N>, iterationType?: IterationType, includeNull?: undefined): ReturnType<C>[][]; | ||
listLevels<C extends BTNCallback<N | null | undefined>>(callback?: C, beginRoot?: BTNodeKeyOrNode<K, N>, iterationType?: IterationType, includeNull?: true): ReturnType<C>[][]; | ||
/** | ||
@@ -476,7 +478,7 @@ * Time complexity: O(n) | ||
* The function `getSuccessor` returns the next node in a binary tree given a current node. | ||
* @param {BTNKey | N | null} [x] - The parameter `x` can be of type `BTNKey`, `N`, or `null`. | ||
* @param {K | N | null} [x] - The parameter `x` can be of type `K`, `N`, or `null`. | ||
* @returns the successor of the given node or key. The successor is the node that comes immediately | ||
* after the given node in the inorder traversal of the binary tree. | ||
*/ | ||
getSuccessor(x?: BTNKey | N | null): N | null | undefined; | ||
getSuccessor(x?: K | N | null): N | null | undefined; | ||
/** | ||
@@ -493,3 +495,3 @@ * Time complexity: O(n) | ||
* following values: | ||
* @param {BTNKey | N | null | undefined} beginRoot - The `beginRoot` parameter is the starting node | ||
* @param {K | N | null | undefined} beginRoot - The `beginRoot` parameter is the starting node | ||
* for the traversal. It can be specified as a key, a node object, or `null`/`undefined` to indicate | ||
@@ -501,3 +503,3 @@ * the root of the tree. If no value is provided, the default value is the root of the tree. | ||
*/ | ||
morris<C extends BTNCallback<N>>(callback?: C, pattern?: DFSOrderPattern, beginRoot?: BTNodeKeyOrNode<N>): ReturnType<C>[]; | ||
morris<C extends BTNCallback<N>>(callback?: C, pattern?: DFSOrderPattern, beginRoot?: BTNodeKeyOrNode<K, N>): ReturnType<C>[]; | ||
/** | ||
@@ -535,3 +537,3 @@ * Time complexity: O(n) | ||
*/ | ||
filter(predicate: PairCallback<BTNKey, V | undefined, boolean>, thisArg?: any): TREE; | ||
filter(predicate: PairCallback<K, V | undefined, boolean>, thisArg?: any): TREE; | ||
/** | ||
@@ -556,6 +558,6 @@ * Time Complexity: O(n) | ||
*/ | ||
map(callback: PairCallback<BTNKey, V | undefined, V>, thisArg?: any): TREE; | ||
map(callback: PairCallback<K, V | undefined, V>, thisArg?: any): TREE; | ||
/** | ||
* The `print` function is used to display a binary tree structure in a visually appealing way. | ||
* @param {BTNKey | N | null | undefined} [beginRoot=this.root] - The `root` parameter is of type `BTNKey | N | null | | ||
* @param {K | N | null | undefined} [beginRoot=this.root] - The `root` parameter is of type `K | N | null | | ||
* undefined`. It represents the root node of a binary tree. The root node can have one of the | ||
@@ -565,6 +567,6 @@ * following types: | ||
*/ | ||
print(beginRoot?: BTNodeKeyOrNode<N>, options?: BinaryTreePrintOptions): void; | ||
protected _getIterator(node?: N | null | undefined): IterableIterator<[BTNKey, V | undefined]>; | ||
print(beginRoot?: BTNodeKeyOrNode<K, N>, options?: BinaryTreePrintOptions): void; | ||
protected _getIterator(node?: N | null | undefined): IterableIterator<[K, V | undefined]>; | ||
protected _displayAux(node: N | null | undefined, options: BinaryTreePrintOptions): NodeDisplayLayout; | ||
protected _defaultOneParamCallback: (node: N) => number; | ||
protected _defaultOneParamCallback: (node: N) => K; | ||
/** | ||
@@ -576,3 +578,3 @@ * Swap the data of two nodes in the binary tree. | ||
*/ | ||
protected _swapProperties(srcNode: BTNodeKeyOrNode<N>, destNode: BTNodeKeyOrNode<N>): N | undefined; | ||
protected _swapProperties(srcNode: BTNodeKeyOrNode<K, N>, destNode: BTNodeKeyOrNode<K, N>): N | undefined; | ||
/** | ||
@@ -598,3 +600,3 @@ * The function replaces an old node with a new node in a binary tree. | ||
*/ | ||
protected _addTo(newNode: N | null | undefined, parent: BTNodeKeyOrNode<N>): N | null | undefined; | ||
protected _addTo(newNode: N | null | undefined, parent: BTNodeKeyOrNode<K, N>): N | null | undefined; | ||
/** | ||
@@ -601,0 +603,0 @@ * The function sets the root property of an object to a given value, and if the value is not null, |
@@ -8,9 +8,9 @@ /** | ||
*/ | ||
import type { BSTNested, BSTNodeKeyOrNode, BSTNodeNested, BSTOptions, BTNCallback, BTNKey, BTNodeExemplar, Comparator } from '../../types'; | ||
import { CP, IterationType } from '../../types'; | ||
import type { BSTNested, BSTNodeKeyOrNode, BSTNodeNested, BSTOptions, BTNCallback, BTNodeExemplar } from '../../types'; | ||
import { BSTVariant, CP, IterationType } from '../../types'; | ||
import { BinaryTree, BinaryTreeNode } from './binary-tree'; | ||
import { IBinaryTree } from '../../interfaces'; | ||
export declare class BSTNode<V = any, N extends BSTNode<V, N> = BSTNodeNested<V>> extends BinaryTreeNode<V, N> { | ||
export declare class BSTNode<K = any, V = any, N extends BSTNode<K, V, N> = BSTNodeNested<K, V>> extends BinaryTreeNode<K, V, N> { | ||
parent?: N; | ||
constructor(key: BTNKey, value?: V); | ||
constructor(key: K, value?: V); | ||
protected _left?: N; | ||
@@ -46,3 +46,3 @@ /** | ||
*/ | ||
export declare class BST<V = any, N extends BSTNode<V, N> = BSTNode<V, BSTNodeNested<V>>, TREE extends BST<V, N, TREE> = BST<V, N, BSTNested<V, N>>> extends BinaryTree<V, N, TREE> implements IBinaryTree<V, N, TREE> { | ||
export declare class BST<K = any, V = any, N extends BSTNode<K, V, N> = BSTNode<K, V, BSTNodeNested<K, V>>, TREE extends BST<K, V, N, TREE> = BST<K, V, N, BSTNested<K, V, N>>> extends BinaryTree<K, V, N, TREE> implements IBinaryTree<K, V, N, TREE> { | ||
/** | ||
@@ -56,9 +56,10 @@ * This is the constructor function for a binary search tree class in TypeScript, which initializes | ||
*/ | ||
constructor(elements?: Iterable<BTNodeExemplar<V, N>>, options?: Partial<BSTOptions>); | ||
constructor(elements?: Iterable<BTNodeExemplar<K, V, N>>, options?: Partial<BSTOptions<K>>); | ||
protected _root?: N; | ||
get root(): N | undefined; | ||
comparator: Comparator<BTNKey>; | ||
protected _variant: BSTVariant; | ||
get variant(): BSTVariant; | ||
/** | ||
* The function creates a new binary search tree node with the given key and value. | ||
* @param {BTNKey} key - The key parameter is the key value that will be associated with | ||
* @param {K} key - The key parameter is the key value that will be associated with | ||
* the new node. It is used to determine the position of the node in the binary search tree. | ||
@@ -69,3 +70,3 @@ * @param [value] - The parameter `value` is an optional value that can be assigned to the node. It | ||
*/ | ||
createNode(key: BTNKey, value?: V): N; | ||
createNode(key: K, value?: V): N; | ||
/** | ||
@@ -78,16 +79,16 @@ * The function creates a new binary search tree with the specified options. | ||
*/ | ||
createTree(options?: Partial<BSTOptions>): TREE; | ||
createTree(options?: Partial<BSTOptions<K>>): TREE; | ||
/** | ||
* The function checks if an exemplar is an instance of BSTNode. | ||
* @param exemplar - The `exemplar` parameter is a variable of type `BTNodeExemplar<V, N>`. | ||
* @param exemplar - The `exemplar` parameter is a variable of type `BTNodeExemplar<K, V, N>`. | ||
* @returns a boolean value indicating whether the exemplar is an instance of the BSTNode class. | ||
*/ | ||
isNode(exemplar: BTNodeExemplar<V, N>): exemplar is N; | ||
isNode(exemplar: BTNodeExemplar<K, V, N>): exemplar is N; | ||
/** | ||
* The function `exemplarToNode` takes an exemplar and returns a corresponding node if the exemplar | ||
* is valid, otherwise it returns undefined. | ||
* @param exemplar - The `exemplar` parameter is of type `BTNodeExemplar<V, N>`. | ||
* @param exemplar - The `exemplar` parameter is of type `BTNodeExemplar<K, V, N>`. | ||
* @returns a variable `node` which is of type `N` or `undefined`. | ||
*/ | ||
exemplarToNode(exemplar: BTNodeExemplar<V, N>): N | undefined; | ||
exemplarToNode(exemplar: BTNodeExemplar<K, V, N>): N | undefined; | ||
/** | ||
@@ -107,3 +108,3 @@ * Time Complexity: O(log n) - Average case for a balanced tree. In the worst case (unbalanced tree), it can be O(n). | ||
*/ | ||
add(keyOrNodeOrEntry: BTNodeExemplar<V, N>): N | undefined; | ||
add(keyOrNodeOrEntry: BTNodeExemplar<K, V, N>): N | undefined; | ||
/** | ||
@@ -129,29 +130,9 @@ * Time Complexity: O(k log n) - Adding each element individually in a balanced tree. | ||
*/ | ||
addMany(keysOrNodesOrEntries: Iterable<BTNodeExemplar<V, N>>, isBalanceAdd?: boolean, iterationType?: IterationType): (N | undefined)[]; | ||
addMany(keysOrNodesOrEntries: Iterable<BTNodeExemplar<K, V, N>>, isBalanceAdd?: boolean, iterationType?: IterationType): (N | undefined)[]; | ||
/** | ||
* Time Complexity: O(n log n) - Adding each element individually in a balanced tree. | ||
* Space Complexity: O(n) - Additional space is required for the sorted array. | ||
*/ | ||
/** | ||
* Time Complexity: O(log n) - Average case for a balanced tree. | ||
* Space Complexity: O(1) - Constant space is used. | ||
* | ||
* The `lastKey` function returns the key of the rightmost node in a binary tree, or the key of the | ||
* leftmost node if the comparison result is greater than. | ||
* @param {BTNKey | N | undefined} beginRoot - The `beginRoot` parameter is optional and can be of | ||
* type `BTNKey`, `N`, or `undefined`. It represents the starting point for finding the last key in | ||
* the binary tree. If not provided, it defaults to the root of the binary tree (`this.root`). | ||
* @param iterationType - The `iterationType` parameter is used to specify the type of iteration to | ||
* be performed. It can have one of the following values: | ||
* @returns the key of the rightmost node in the binary tree if the comparison result is less than, | ||
* the key of the leftmost node if the comparison result is greater than, and the key of the | ||
* rightmost node otherwise. If no node is found, it returns 0. | ||
*/ | ||
lastKey(beginRoot?: BSTNodeKeyOrNode<N>, iterationType?: IterationType): BTNKey; | ||
/** | ||
* Time Complexity: O(log n) - Average case for a balanced tree. | ||
* Space Complexity: O(1) - Constant space is used. | ||
*/ | ||
/** | ||
* Time Complexity: O(log n) - Average case for a balanced tree. | ||
* Space Complexity: O(log n) - Space for the recursive call stack in the worst case. | ||
@@ -161,3 +142,3 @@ * | ||
* either recursive or iterative methods. | ||
* @param {BTNKey} key - The `key` parameter is the key value that we are searching for in the tree. | ||
* @param {K} key - The `key` parameter is the key value that we are searching for in the tree. | ||
* It is used to identify the node that we want to retrieve. | ||
@@ -170,3 +151,3 @@ * @param iterationType - The `iterationType` parameter is an optional parameter that specifies the | ||
*/ | ||
getNodeByKey(key: BTNKey, iterationType?: IterationType): N | undefined; | ||
getNodeByKey(key: K, iterationType?: IterationType): N | undefined; | ||
/** | ||
@@ -179,3 +160,3 @@ * Time Complexity: O(log n) - Average case for a balanced tree. | ||
* otherwise it returns the key itself. | ||
* @param {BTNKey | N | undefined} key - The `key` parameter can be of type `BTNKey`, `N`, or | ||
* @param {K | N | undefined} key - The `key` parameter can be of type `K`, `N`, or | ||
* `undefined`. | ||
@@ -186,3 +167,3 @@ * @param iterationType - The `iterationType` parameter is an optional parameter that specifies the | ||
*/ | ||
ensureNode(key: BSTNodeKeyOrNode<N>, iterationType?: IterationType): N | undefined; | ||
ensureNode(key: BSTNodeKeyOrNode<K, N>, iterationType?: IterationType): N | undefined; | ||
/** | ||
@@ -204,3 +185,3 @@ * Time Complexity: O(log n) - Average case for a balanced tree. O(n) - Visiting each node once when identifier is not node's key. | ||
* searching for all nodes that match the identifier and return an array containing | ||
* @param {BTNKey | N | undefined} beginRoot - The `beginRoot` parameter represents the starting node | ||
* @param {K | N | undefined} beginRoot - The `beginRoot` parameter represents the starting node | ||
* for the traversal. It can be either a key value or a node object. If it is undefined, the | ||
@@ -212,3 +193,3 @@ * traversal will start from the root of the tree. | ||
*/ | ||
getNodes<C extends BTNCallback<N>>(identifier: ReturnType<C> | undefined, callback?: C, onlyOne?: boolean, beginRoot?: BSTNodeKeyOrNode<N>, iterationType?: IterationType): N[]; | ||
getNodes<C extends BTNCallback<N>>(identifier: ReturnType<C> | undefined, callback?: C, onlyOne?: boolean, beginRoot?: BSTNodeKeyOrNode<K, N>, iterationType?: IterationType): N[]; | ||
/** | ||
@@ -231,3 +212,3 @@ * Time Complexity: O(log n) - Average case for a balanced tree. O(n) - Visiting each node once when identifier is not node's key. | ||
* `lesserOrGreater` are | ||
* @param {BTNKey | N | undefined} targetNode - The `targetNode` parameter represents the node in the | ||
* @param {K | N | undefined} targetNode - The `targetNode` parameter represents the node in the | ||
* binary tree that you want to traverse from. It can be specified either by its key, by the node | ||
@@ -240,3 +221,3 @@ * object itself, or it can be left undefined to start the traversal from the root of the tree. | ||
*/ | ||
lesserOrGreaterTraverse<C extends BTNCallback<N>>(callback?: C, lesserOrGreater?: CP, targetNode?: BSTNodeKeyOrNode<N>, iterationType?: IterationType): ReturnType<C>[]; | ||
lesserOrGreaterTraverse<C extends BTNCallback<N>>(callback?: C, lesserOrGreater?: CP, targetNode?: BSTNodeKeyOrNode<K, N>, iterationType?: IterationType): ReturnType<C>[]; | ||
/** | ||
@@ -285,8 +266,8 @@ * Time Complexity: O(log n) - Average case for a balanced tree. O(n) - Visiting each node once when identifier is not node's key. | ||
* is greater than, less than, or equal to the second value. | ||
* @param {BTNKey} a - The parameter "a" is of type BTNKey. | ||
* @param {BTNKey} b - The parameter "b" in the above code represents a BTNKey. | ||
* @param {K} a - The parameter "a" is of type K. | ||
* @param {K} b - The parameter "b" in the above code represents a K. | ||
* @returns a value of type CP (ComparisonResult). The possible return values are CP.gt (greater | ||
* than), CP.lt (less than), or CP.eq (equal). | ||
*/ | ||
protected _compare(a: BTNKey, b: BTNKey): CP; | ||
protected _compare(a: K, b: K): CP; | ||
} |
@@ -68,7 +68,7 @@ "use strict"; | ||
super([], options); | ||
this.comparator = (a, b) => a - b; | ||
this._variant = types_1.BSTVariant.MIN; | ||
if (options) { | ||
const { comparator } = options; | ||
if (comparator) { | ||
this.comparator = comparator; | ||
const { variant } = options; | ||
if (variant) { | ||
this._variant = variant; | ||
} | ||
@@ -83,5 +83,8 @@ } | ||
} | ||
get variant() { | ||
return this._variant; | ||
} | ||
/** | ||
* The function creates a new binary search tree node with the given key and value. | ||
* @param {BTNKey} key - The key parameter is the key value that will be associated with | ||
* @param {K} key - The key parameter is the key value that will be associated with | ||
* the new node. It is used to determine the position of the node in the binary search tree. | ||
@@ -103,7 +106,7 @@ * @param [value] - The parameter `value` is an optional value that can be assigned to the node. It | ||
createTree(options) { | ||
return new BST([], Object.assign({ iterationType: this.iterationType, comparator: this.comparator }, options)); | ||
return new BST([], Object.assign({ iterationType: this.iterationType, variant: this.variant }, options)); | ||
} | ||
/** | ||
* The function checks if an exemplar is an instance of BSTNode. | ||
* @param exemplar - The `exemplar` parameter is a variable of type `BTNodeExemplar<V, N>`. | ||
* @param exemplar - The `exemplar` parameter is a variable of type `BTNodeExemplar<K, V, N>`. | ||
* @returns a boolean value indicating whether the exemplar is an instance of the BSTNode class. | ||
@@ -117,3 +120,3 @@ */ | ||
* is valid, otherwise it returns undefined. | ||
* @param exemplar - The `exemplar` parameter is of type `BTNodeExemplar<V, N>`. | ||
* @param exemplar - The `exemplar` parameter is of type `BTNodeExemplar<K, V, N>`. | ||
* @returns a variable `node` which is of type `N` or `undefined`. | ||
@@ -138,3 +141,3 @@ */ | ||
} | ||
else if (this.isNodeKey(exemplar)) { | ||
else if (this.isNotNodeInstance(exemplar)) { | ||
node = this.createNode(exemplar); | ||
@@ -247,13 +250,13 @@ } | ||
if (this.isEntry(a)) | ||
aR = a[0]; | ||
aR = this.extractor(a[0]); | ||
else if (this.isRealNode(a)) | ||
aR = a.key; | ||
aR = this.extractor(a.key); | ||
else | ||
aR = a; | ||
aR = this.extractor(a); | ||
if (this.isEntry(b)) | ||
bR = b[0]; | ||
bR = this.extractor(b[0]); | ||
else if (this.isRealNode(b)) | ||
bR = b.key; | ||
bR = this.extractor(b.key); | ||
else | ||
bR = b; | ||
bR = this.extractor(b); | ||
return aR - bR; | ||
@@ -295,36 +298,33 @@ }); | ||
} | ||
// /** | ||
// * Time Complexity: O(n log n) - Adding each element individually in a balanced tree. | ||
// * Space Complexity: O(n) - Additional space is required for the sorted array. | ||
// */ | ||
// | ||
// /** | ||
// * Time Complexity: O(log n) - Average case for a balanced tree. | ||
// * Space Complexity: O(1) - Constant space is used. | ||
// * | ||
// * The `lastKey` function returns the key of the rightmost node in a binary tree, or the key of the | ||
// * leftmost node if the comparison result is greater than. | ||
// * @param {K | N | undefined} beginRoot - The `beginRoot` parameter is optional and can be of | ||
// * type `K`, `N`, or `undefined`. It represents the starting point for finding the last key in | ||
// * the binary tree. If not provided, it defaults to the root of the binary tree (`this.root`). | ||
// * @param iterationType - The `iterationType` parameter is used to specify the type of iteration to | ||
// * be performed. It can have one of the following values: | ||
// * @returns the key of the rightmost node in the binary tree if the comparison result is less than, | ||
// * the key of the leftmost node if the comparison result is greater than, and the key of the | ||
// * rightmost node otherwise. If no node is found, it returns 0. | ||
// */ | ||
// lastKey(beginRoot: BSTNodeKeyOrNode<K,N> = this.root, iterationType = this.iterationType): K { | ||
// if (this._compare(0, 1) === CP.lt) return this.getRightMost(beginRoot, iterationType)?.key ?? 0; | ||
// else if (this._compare(0, 1) === CP.gt) return this.getLeftMost(beginRoot, iterationType)?.key ?? 0; | ||
// else return this.getRightMost(beginRoot, iterationType)?.key ?? 0; | ||
// } | ||
/** | ||
* Time Complexity: O(n log n) - Adding each element individually in a balanced tree. | ||
* Space Complexity: O(n) - Additional space is required for the sorted array. | ||
*/ | ||
/** | ||
* Time Complexity: O(log n) - Average case for a balanced tree. | ||
* Space Complexity: O(1) - Constant space is used. | ||
* | ||
* The `lastKey` function returns the key of the rightmost node in a binary tree, or the key of the | ||
* leftmost node if the comparison result is greater than. | ||
* @param {BTNKey | N | undefined} beginRoot - The `beginRoot` parameter is optional and can be of | ||
* type `BTNKey`, `N`, or `undefined`. It represents the starting point for finding the last key in | ||
* the binary tree. If not provided, it defaults to the root of the binary tree (`this.root`). | ||
* @param iterationType - The `iterationType` parameter is used to specify the type of iteration to | ||
* be performed. It can have one of the following values: | ||
* @returns the key of the rightmost node in the binary tree if the comparison result is less than, | ||
* the key of the leftmost node if the comparison result is greater than, and the key of the | ||
* rightmost node otherwise. If no node is found, it returns 0. | ||
*/ | ||
lastKey(beginRoot = this.root, iterationType = this.iterationType) { | ||
var _a, _b, _c, _d, _e, _f; | ||
if (this._compare(0, 1) === types_1.CP.lt) | ||
return (_b = (_a = this.getRightMost(beginRoot, iterationType)) === null || _a === void 0 ? void 0 : _a.key) !== null && _b !== void 0 ? _b : 0; | ||
else if (this._compare(0, 1) === types_1.CP.gt) | ||
return (_d = (_c = this.getLeftMost(beginRoot, iterationType)) === null || _c === void 0 ? void 0 : _c.key) !== null && _d !== void 0 ? _d : 0; | ||
else | ||
return (_f = (_e = this.getRightMost(beginRoot, iterationType)) === null || _e === void 0 ? void 0 : _e.key) !== null && _f !== void 0 ? _f : 0; | ||
} | ||
/** | ||
* Time Complexity: O(log n) - Average case for a balanced tree. | ||
* Space Complexity: O(1) - Constant space is used. | ||
*/ | ||
/** | ||
* Time Complexity: O(log n) - Average case for a balanced tree. | ||
* Space Complexity: O(log n) - Space for the recursive call stack in the worst case. | ||
@@ -334,3 +334,3 @@ * | ||
* either recursive or iterative methods. | ||
* @param {BTNKey} key - The `key` parameter is the key value that we are searching for in the tree. | ||
* @param {K} key - The `key` parameter is the key value that we are searching for in the tree. | ||
* It is used to identify the node that we want to retrieve. | ||
@@ -381,3 +381,3 @@ * @param iterationType - The `iterationType` parameter is an optional parameter that specifies the | ||
* otherwise it returns the key itself. | ||
* @param {BTNKey | N | undefined} key - The `key` parameter can be of type `BTNKey`, `N`, or | ||
* @param {K | N | undefined} key - The `key` parameter can be of type `K`, `N`, or | ||
* `undefined`. | ||
@@ -389,3 +389,3 @@ * @param iterationType - The `iterationType` parameter is an optional parameter that specifies the | ||
ensureNode(key, iterationType = types_1.IterationType.ITERATIVE) { | ||
return this.isNodeKey(key) ? this.getNodeByKey(key, iterationType) : key; | ||
return this.isNotNodeInstance(key) ? this.getNodeByKey(key, iterationType) : key; | ||
} | ||
@@ -408,3 +408,3 @@ /** | ||
* searching for all nodes that match the identifier and return an array containing | ||
* @param {BTNKey | N | undefined} beginRoot - The `beginRoot` parameter represents the starting node | ||
* @param {K | N | undefined} beginRoot - The `beginRoot` parameter represents the starting node | ||
* for the traversal. It can be either a key value or a node object. If it is undefined, the | ||
@@ -489,3 +489,3 @@ * traversal will start from the root of the tree. | ||
* `lesserOrGreater` are | ||
* @param {BTNKey | N | undefined} targetNode - The `targetNode` parameter represents the node in the | ||
* @param {K | N | undefined} targetNode - The `targetNode` parameter represents the node in the | ||
* binary tree that you want to traverse from. It can be specified either by its key, by the node | ||
@@ -667,4 +667,4 @@ * object itself, or it can be left undefined to start the traversal from the root of the tree. | ||
* is greater than, less than, or equal to the second value. | ||
* @param {BTNKey} a - The parameter "a" is of type BTNKey. | ||
* @param {BTNKey} b - The parameter "b" in the above code represents a BTNKey. | ||
* @param {K} a - The parameter "a" is of type K. | ||
* @param {K} b - The parameter "b" in the above code represents a K. | ||
* @returns a value of type CP (ComparisonResult). The possible return values are CP.gt (greater | ||
@@ -674,11 +674,8 @@ * than), CP.lt (less than), or CP.eq (equal). | ||
_compare(a, b) { | ||
const compared = this.comparator(a, b); | ||
if (compared > 0) | ||
return types_1.CP.gt; | ||
else if (compared < 0) | ||
return types_1.CP.lt; | ||
else | ||
return types_1.CP.eq; | ||
const extractedA = this.extractor(a); | ||
const extractedB = this.extractor(b); | ||
const compared = this.variant === types_1.BSTVariant.MIN ? extractedA - extractedB : extractedB - extractedA; | ||
return compared > 0 ? types_1.CP.gt : compared < 0 ? types_1.CP.lt : types_1.CP.eq; | ||
} | ||
} | ||
exports.BST = BST; |
@@ -8,8 +8,8 @@ /** | ||
*/ | ||
import { BiTreeDeleteResult, BTNCallback, BTNKey, BTNodeExemplar, IterationType, RBTNColor, RBTreeOptions, RedBlackTreeNested, RedBlackTreeNodeNested } from '../../types'; | ||
import { BiTreeDeleteResult, BTNCallback, BTNodeExemplar, IterationType, RBTNColor, RBTreeOptions, RedBlackTreeNested, RedBlackTreeNodeNested } from '../../types'; | ||
import { BST, BSTNode } from './bst'; | ||
import { IBinaryTree } from '../../interfaces'; | ||
export declare class RedBlackTreeNode<V = any, N extends RedBlackTreeNode<V, N> = RedBlackTreeNodeNested<V>> extends BSTNode<V, N> { | ||
export declare class RedBlackTreeNode<K = any, V = any, N extends RedBlackTreeNode<K, V, N> = RedBlackTreeNodeNested<K, V>> extends BSTNode<K, V, N> { | ||
color: RBTNColor; | ||
constructor(key: BTNKey, value?: V, color?: RBTNColor); | ||
constructor(key: K, value?: V, color?: RBTNColor); | ||
} | ||
@@ -23,3 +23,3 @@ /** | ||
*/ | ||
export declare class RedBlackTree<V = any, N extends RedBlackTreeNode<V, N> = RedBlackTreeNode<V, RedBlackTreeNodeNested<V>>, TREE extends RedBlackTree<V, N, TREE> = RedBlackTree<V, N, RedBlackTreeNested<V, N>>> extends BST<V, N, TREE> implements IBinaryTree<V, N, TREE> { | ||
export declare class RedBlackTree<K = any, V = any, N extends RedBlackTreeNode<K, V, N> = RedBlackTreeNode<K, V, RedBlackTreeNodeNested<K, V>>, TREE extends RedBlackTree<K, V, N, TREE> = RedBlackTree<K, V, N, RedBlackTreeNested<K, V, N>>> extends BST<K, V, N, TREE> implements IBinaryTree<K, V, N, TREE> { | ||
Sentinel: N; | ||
@@ -29,3 +29,3 @@ /** | ||
* initializes the tree with optional elements and options. | ||
* @param [elements] - The `elements` parameter is an optional iterable of `BTNodeExemplar<V, N>` | ||
* @param [elements] - The `elements` parameter is an optional iterable of `BTNodeExemplar<K, V, N>` | ||
* objects. It represents the initial elements that will be added to the RBTree during its | ||
@@ -38,3 +38,3 @@ * construction. If this parameter is provided, the `addMany` method is called to add all the | ||
*/ | ||
constructor(elements?: Iterable<BTNodeExemplar<V, N>>, options?: Partial<RBTreeOptions>); | ||
constructor(elements?: Iterable<BTNodeExemplar<K, V, N>>, options?: Partial<RBTreeOptions<K>>); | ||
protected _root: N; | ||
@@ -46,3 +46,3 @@ get root(): N; | ||
* The function creates a new Red-Black Tree node with the specified key, value, and color. | ||
* @param {BTNKey} key - The key parameter is the key value associated with the node. It is used to | ||
* @param {K} key - The key parameter is the key value associated with the node. It is used to | ||
* identify and compare nodes in the Red-Black Tree. | ||
@@ -57,3 +57,3 @@ * @param {V} [value] - The `value` parameter is an optional parameter that represents the value | ||
*/ | ||
createNode(key: BTNKey, value?: V, color?: RBTNColor): N; | ||
createNode(key: K, value?: V, color?: RBTNColor): N; | ||
/** | ||
@@ -66,14 +66,14 @@ * The function creates a Red-Black Tree with the specified options and returns it. | ||
*/ | ||
createTree(options?: RBTreeOptions): TREE; | ||
createTree(options?: RBTreeOptions<K>): TREE; | ||
/** | ||
* The function checks if an exemplar is an instance of the RedBlackTreeNode class. | ||
* @param exemplar - The `exemplar` parameter is of type `BTNodeExemplar<V, N>`. | ||
* @param exemplar - The `exemplar` parameter is of type `BTNodeExemplar<K, V, N>`. | ||
* @returns a boolean value indicating whether the exemplar is an instance of the RedBlackTreeNode | ||
* class. | ||
*/ | ||
isNode(exemplar: BTNodeExemplar<V, N>): exemplar is N; | ||
isNode(exemplar: BTNodeExemplar<K, V, N>): exemplar is N; | ||
/** | ||
* The function `exemplarToNode` takes an exemplar and returns a node if the exemplar is valid, | ||
* otherwise it returns undefined. | ||
* @param exemplar - BTNodeExemplar<V, N> - A generic type representing an exemplar of a binary tree | ||
* @param exemplar - BTNodeExemplar<K, V, N> - A generic type representing an exemplar of a binary tree | ||
* node. It can be either a node itself, an entry (key-value pair), a node key, or any other value | ||
@@ -83,3 +83,3 @@ * that is not a valid exemplar. | ||
*/ | ||
exemplarToNode(exemplar: BTNodeExemplar<V, N>): N | undefined; | ||
exemplarToNode(exemplar: BTNodeExemplar<K, V, N>): N | undefined; | ||
/** | ||
@@ -95,3 +95,3 @@ * Time Complexity: O(log n) on average (where n is the number of nodes in the tree) | ||
*/ | ||
add(keyOrNodeOrEntry: BTNodeExemplar<V, N>): N | undefined; | ||
add(keyOrNodeOrEntry: BTNodeExemplar<K, V, N>): N | undefined; | ||
/** | ||
@@ -122,3 +122,3 @@ * Time Complexity: O(log n) on average (where n is the number of nodes in the tree) | ||
isRealNode(node: N | undefined): node is N; | ||
getNode<C extends BTNCallback<N, BTNKey>>(identifier: BTNKey, callback?: C, beginRoot?: N | undefined, iterationType?: IterationType): N | undefined; | ||
getNode<C extends BTNCallback<N, K>>(identifier: K, callback?: C, beginRoot?: N | undefined, iterationType?: IterationType): N | undefined; | ||
getNode<C extends BTNCallback<N, N>>(identifier: N | undefined, callback?: C, beginRoot?: N | undefined, iterationType?: IterationType): N | undefined; | ||
@@ -125,0 +125,0 @@ getNode<C extends BTNCallback<N>>(identifier: ReturnType<C>, callback: C, beginRoot?: N | undefined, iterationType?: IterationType): N | undefined; |
@@ -32,3 +32,3 @@ "use strict"; | ||
* initializes the tree with optional elements and options. | ||
* @param [elements] - The `elements` parameter is an optional iterable of `BTNodeExemplar<V, N>` | ||
* @param [elements] - The `elements` parameter is an optional iterable of `BTNodeExemplar<K, V, N>` | ||
* objects. It represents the initial elements that will be added to the RBTree during its | ||
@@ -57,3 +57,3 @@ * construction. If this parameter is provided, the `addMany` method is called to add all the | ||
* The function creates a new Red-Black Tree node with the specified key, value, and color. | ||
* @param {BTNKey} key - The key parameter is the key value associated with the node. It is used to | ||
* @param {K} key - The key parameter is the key value associated with the node. It is used to | ||
* identify and compare nodes in the Red-Black Tree. | ||
@@ -79,7 +79,7 @@ * @param {V} [value] - The `value` parameter is an optional parameter that represents the value | ||
createTree(options) { | ||
return new RedBlackTree([], Object.assign({ iterationType: this.iterationType, comparator: this.comparator }, options)); | ||
return new RedBlackTree([], Object.assign({ iterationType: this.iterationType, variant: this.variant }, options)); | ||
} | ||
/** | ||
* The function checks if an exemplar is an instance of the RedBlackTreeNode class. | ||
* @param exemplar - The `exemplar` parameter is of type `BTNodeExemplar<V, N>`. | ||
* @param exemplar - The `exemplar` parameter is of type `BTNodeExemplar<K, V, N>`. | ||
* @returns a boolean value indicating whether the exemplar is an instance of the RedBlackTreeNode | ||
@@ -94,3 +94,3 @@ * class. | ||
* otherwise it returns undefined. | ||
* @param exemplar - BTNodeExemplar<V, N> - A generic type representing an exemplar of a binary tree | ||
* @param exemplar - BTNodeExemplar<K, V, N> - A generic type representing an exemplar of a binary tree | ||
* node. It can be either a node itself, an entry (key-value pair), a node key, or any other value | ||
@@ -117,3 +117,3 @@ * that is not a valid exemplar. | ||
} | ||
else if (this.isNodeKey(exemplar)) { | ||
else if (this.isNotNodeInstance(exemplar)) { | ||
node = this.createNode(exemplar, undefined, types_1.RBTNColor.RED); | ||
@@ -284,3 +284,3 @@ } | ||
* function should take a single parameter of type `N` (the type of the nodes in the binary tree) and | ||
* @param {BTNKey | N | undefined} beginRoot - The `beginRoot` parameter is the starting point for | ||
* @param {K | N | undefined} beginRoot - The `beginRoot` parameter is the starting point for | ||
* searching for a node in a binary tree. It can be either a key value or a node object. If it is not | ||
@@ -287,0 +287,0 @@ * provided, the search will start from the root of the binary tree. |
@@ -8,11 +8,11 @@ /** | ||
*/ | ||
import type { BSTNodeKeyOrNode, BTNKey, BTNodeExemplar, TreeMultimapNodeNested, TreeMultimapOptions } from '../../types'; | ||
import type { BSTNodeKeyOrNode, BTNodeExemplar, TreeMultimapNodeNested, TreeMultimapOptions } from '../../types'; | ||
import { BiTreeDeleteResult, BTNCallback, IterationType, TreeMultimapNested } from '../../types'; | ||
import { IBinaryTree } from '../../interfaces'; | ||
import { AVLTree, AVLTreeNode } from './avl-tree'; | ||
export declare class TreeMultimapNode<V = any, N extends TreeMultimapNode<V, N> = TreeMultimapNodeNested<V>> extends AVLTreeNode<V, N> { | ||
export declare class TreeMultimapNode<K = any, V = any, N extends TreeMultimapNode<K, V, N> = TreeMultimapNodeNested<K, V>> extends AVLTreeNode<K, V, N> { | ||
count: number; | ||
/** | ||
* The constructor function initializes a BinaryTreeNode object with a key, value, and count. | ||
* @param {BTNKey} key - The `key` parameter is of type `BTNKey` and represents the unique identifier | ||
* @param {K} key - The `key` parameter is of type `K` and represents the unique identifier | ||
* of the binary tree node. | ||
@@ -25,3 +25,3 @@ * @param {V} [value] - The `value` parameter is an optional parameter of type `V`. It represents the value of the binary | ||
*/ | ||
constructor(key: BTNKey, value?: V, count?: number); | ||
constructor(key: K, value?: V, count?: number); | ||
} | ||
@@ -31,4 +31,4 @@ /** | ||
*/ | ||
export declare class TreeMultimap<V = any, N extends TreeMultimapNode<V, N> = TreeMultimapNode<V, TreeMultimapNodeNested<V>>, TREE extends TreeMultimap<V, N, TREE> = TreeMultimap<V, N, TreeMultimapNested<V, N>>> extends AVLTree<V, N, TREE> implements IBinaryTree<V, N, TREE> { | ||
constructor(elements?: Iterable<BTNodeExemplar<V, N>>, options?: Partial<TreeMultimapOptions>); | ||
export declare class TreeMultimap<K = any, V = any, N extends TreeMultimapNode<K, V, N> = TreeMultimapNode<K, V, TreeMultimapNodeNested<K, V>>, TREE extends TreeMultimap<K, V, N, TREE> = TreeMultimap<K, V, N, TreeMultimapNested<K, V, N>>> extends AVLTree<K, V, N, TREE> implements IBinaryTree<K, V, N, TREE> { | ||
constructor(elements?: Iterable<BTNodeExemplar<K, V, N>>, options?: Partial<TreeMultimapOptions<K>>); | ||
private _count; | ||
@@ -38,3 +38,3 @@ get count(): number; | ||
* The function creates a new BSTNode with the given key, value, and count. | ||
* @param {BTNKey} key - The key parameter is the unique identifier for the binary tree node. It is used to | ||
* @param {K} key - The key parameter is the unique identifier for the binary tree node. It is used to | ||
* distinguish one node from another in the tree. | ||
@@ -46,14 +46,14 @@ * @param {N} value - The `value` parameter represents the value that will be stored in the binary search tree node. | ||
*/ | ||
createNode(key: BTNKey, value?: V, count?: number): N; | ||
createTree(options?: TreeMultimapOptions): TREE; | ||
createNode(key: K, value?: V, count?: number): N; | ||
createTree(options?: TreeMultimapOptions<K>): TREE; | ||
/** | ||
* The function checks if an exemplar is an instance of the TreeMultimapNode class. | ||
* @param exemplar - The `exemplar` parameter is of type `BTNodeExemplar<V, N>`. | ||
* @param exemplar - The `exemplar` parameter is of type `BTNodeExemplar<K, V, N>`. | ||
* @returns a boolean value indicating whether the exemplar is an instance of the TreeMultimapNode | ||
* class. | ||
*/ | ||
isNode(exemplar: BTNodeExemplar<V, N>): exemplar is N; | ||
isNode(exemplar: BTNodeExemplar<K, V, N>): exemplar is N; | ||
/** | ||
* The function `exemplarToNode` converts an exemplar object into a node object. | ||
* @param exemplar - The `exemplar` parameter is of type `BTNodeExemplar<V, N>`, where `V` represents | ||
* @param exemplar - The `exemplar` parameter is of type `BTNodeExemplar<K, V, N>`, where `V` represents | ||
* the value type and `N` represents the node type. | ||
@@ -64,3 +64,3 @@ * @param [count=1] - The `count` parameter is an optional parameter that specifies the number of | ||
*/ | ||
exemplarToNode(exemplar: BTNodeExemplar<V, N>, count?: number): N | undefined; | ||
exemplarToNode(exemplar: BTNodeExemplar<K, V, N>, count?: number): N | undefined; | ||
/** | ||
@@ -82,3 +82,3 @@ * Time Complexity: O(log n) - logarithmic time, where "n" is the number of nodes in the tree. The add method of the superclass (AVLTree) has logarithmic time complexity. | ||
*/ | ||
add(keyOrNodeOrEntry: BTNodeExemplar<V, N>, count?: number): N | undefined; | ||
add(keyOrNodeOrEntry: BTNodeExemplar<K, V, N>, count?: number): N | undefined; | ||
/** | ||
@@ -98,3 +98,3 @@ * Time Complexity: O(k log n) - logarithmic time, where "n" is the number of nodes in the tree. The add method of the superclass (AVLTree) has logarithmic time complexity. | ||
*/ | ||
addMany(keysOrNodesOrEntries: Iterable<BTNodeExemplar<V, N>>): (N | undefined)[]; | ||
addMany(keysOrNodesOrEntries: Iterable<BTNodeExemplar<K, V, N>>): (N | undefined)[]; | ||
/** | ||
@@ -169,14 +169,14 @@ * Time Complexity: O(1) - constant time, as it performs basic pointer assignments. | ||
* `undefined` if there is no node to add. | ||
* @param {BTNKey | N | undefined} parent - The `parent` parameter represents the parent node to | ||
* @param {K | N | undefined} parent - The `parent` parameter represents the parent node to | ||
* which the new node will be added as a child. It can be either a node object (`N`) or a key value | ||
* (`BTNKey`). | ||
* (`K`). | ||
* @returns The method `_addTo` returns either the `parent.left` or `parent.right` node that was | ||
* added, or `undefined` if no node was added. | ||
*/ | ||
protected _addTo(newNode: N | undefined, parent: BSTNodeKeyOrNode<N>): N | undefined; | ||
protected _addTo(newNode: N | undefined, parent: BSTNodeKeyOrNode<K, N>): N | undefined; | ||
/** | ||
* The `_swapProperties` function swaps the key, value, count, and height properties between two nodes. | ||
* @param {BTNKey | N | undefined} srcNode - The `srcNode` parameter represents the source node from | ||
* which the values will be swapped. It can be of type `BTNKey`, `N`, or `undefined`. | ||
* @param {BTNKey | N | undefined} destNode - The `destNode` parameter represents the destination | ||
* @param {K | N | undefined} srcNode - The `srcNode` parameter represents the source node from | ||
* which the values will be swapped. It can be of type `K`, `N`, or `undefined`. | ||
* @param {K | N | undefined} destNode - The `destNode` parameter represents the destination | ||
* node where the values from the source node will be swapped to. | ||
@@ -186,4 +186,4 @@ * @returns either the `destNode` object if both `srcNode` and `destNode` are defined, or `undefined` | ||
*/ | ||
protected _swapProperties(srcNode: BSTNodeKeyOrNode<N>, destNode: BSTNodeKeyOrNode<N>): N | undefined; | ||
protected _swapProperties(srcNode: BSTNodeKeyOrNode<K, N>, destNode: BSTNodeKeyOrNode<K, N>): N | undefined; | ||
protected _replaceNode(oldNode: N, newNode: N): N; | ||
} |
@@ -9,3 +9,3 @@ "use strict"; | ||
* The constructor function initializes a BinaryTreeNode object with a key, value, and count. | ||
* @param {BTNKey} key - The `key` parameter is of type `BTNKey` and represents the unique identifier | ||
* @param {K} key - The `key` parameter is of type `K` and represents the unique identifier | ||
* of the binary tree node. | ||
@@ -42,3 +42,3 @@ * @param {V} [value] - The `value` parameter is an optional parameter of type `V`. It represents the value of the binary | ||
* The function creates a new BSTNode with the given key, value, and count. | ||
* @param {BTNKey} key - The key parameter is the unique identifier for the binary tree node. It is used to | ||
* @param {K} key - The key parameter is the unique identifier for the binary tree node. It is used to | ||
* distinguish one node from another in the tree. | ||
@@ -54,7 +54,7 @@ * @param {N} value - The `value` parameter represents the value that will be stored in the binary search tree node. | ||
createTree(options) { | ||
return new TreeMultimap([], Object.assign({ iterationType: this.iterationType, comparator: this.comparator }, options)); | ||
return new TreeMultimap([], Object.assign({ iterationType: this.iterationType, variant: this.variant }, options)); | ||
} | ||
/** | ||
* The function checks if an exemplar is an instance of the TreeMultimapNode class. | ||
* @param exemplar - The `exemplar` parameter is of type `BTNodeExemplar<V, N>`. | ||
* @param exemplar - The `exemplar` parameter is of type `BTNodeExemplar<K, V, N>`. | ||
* @returns a boolean value indicating whether the exemplar is an instance of the TreeMultimapNode | ||
@@ -68,3 +68,3 @@ * class. | ||
* The function `exemplarToNode` converts an exemplar object into a node object. | ||
* @param exemplar - The `exemplar` parameter is of type `BTNodeExemplar<V, N>`, where `V` represents | ||
* @param exemplar - The `exemplar` parameter is of type `BTNodeExemplar<K, V, N>`, where `V` represents | ||
* the value type and `N` represents the node type. | ||
@@ -92,3 +92,3 @@ * @param [count=1] - The `count` parameter is an optional parameter that specifies the number of | ||
} | ||
else if (this.isNodeKey(exemplar)) { | ||
else if (this.isNotNodeInstance(exemplar)) { | ||
node = this.createNode(exemplar, undefined, count); | ||
@@ -313,5 +313,5 @@ } | ||
* `undefined` if there is no node to add. | ||
* @param {BTNKey | N | undefined} parent - The `parent` parameter represents the parent node to | ||
* @param {K | N | undefined} parent - The `parent` parameter represents the parent node to | ||
* which the new node will be added as a child. It can be either a node object (`N`) or a key value | ||
* (`BTNKey`). | ||
* (`K`). | ||
* @returns The method `_addTo` returns either the `parent.left` or `parent.right` node that was | ||
@@ -349,5 +349,5 @@ * added, or `undefined` if no node was added. | ||
* The `_swapProperties` function swaps the key, value, count, and height properties between two nodes. | ||
* @param {BTNKey | N | undefined} srcNode - The `srcNode` parameter represents the source node from | ||
* which the values will be swapped. It can be of type `BTNKey`, `N`, or `undefined`. | ||
* @param {BTNKey | N | undefined} destNode - The `destNode` parameter represents the destination | ||
* @param {K | N | undefined} srcNode - The `srcNode` parameter represents the source node from | ||
* which the values will be swapped. It can be of type `K`, `N`, or `undefined`. | ||
* @param {K | N | undefined} destNode - The `destNode` parameter represents the destination | ||
* node where the values from the source node will be swapped to. | ||
@@ -354,0 +354,0 @@ * @returns either the `destNode` object if both `srcNode` and `destNode` are defined, or `undefined` |
import { BinaryTree, BinaryTreeNode } from '../data-structures'; | ||
import { BinaryTreeNested, BinaryTreeNodeNested, BinaryTreeOptions, BiTreeDeleteResult, BTNCallback, BTNKey, BTNodeExemplar } from '../types'; | ||
export interface IBinaryTree<V = any, N extends BinaryTreeNode<V, N> = BinaryTreeNodeNested<V>, TREE extends BinaryTree<V, N, TREE> = BinaryTreeNested<V, N>> { | ||
createNode(key: BTNKey, value?: N['value']): N; | ||
createTree(options?: Partial<BinaryTreeOptions>): TREE; | ||
add(keyOrNodeOrEntry: BTNodeExemplar<V, N>, count?: number): N | null | undefined; | ||
addMany(nodes: Iterable<BTNodeExemplar<V, N>>): (N | null | undefined)[]; | ||
import { BinaryTreeNested, BinaryTreeNodeNested, BinaryTreeOptions, BiTreeDeleteResult, BTNCallback, BTNodeExemplar } from '../types'; | ||
export interface IBinaryTree<K = number, V = any, N extends BinaryTreeNode<K, V, N> = BinaryTreeNodeNested<K, V>, TREE extends BinaryTree<K, V, N, TREE> = BinaryTreeNested<K, V, N>> { | ||
createNode(key: K, value?: N['value']): N; | ||
createTree(options?: Partial<BinaryTreeOptions<K>>): TREE; | ||
add(keyOrNodeOrEntry: BTNodeExemplar<K, V, N>, count?: number): N | null | undefined; | ||
addMany(nodes: Iterable<BTNodeExemplar<K, V, N>>): (N | null | undefined)[]; | ||
delete<C extends BTNCallback<N>>(identifier: ReturnType<C> | null, callback: C): BiTreeDeleteResult<N>[]; | ||
} |
@@ -1,3 +0,6 @@ | ||
import { BTNKey } from "./data-structures"; | ||
export type Comparator<T> = (a: T, b: T) => number; | ||
export type Comparator<K> = (a: K, b: K) => number; | ||
export declare enum BSTVariant { | ||
MIN = "MIN", | ||
MAX = "MAX" | ||
} | ||
export type DFSOrderPattern = 'pre' | 'in' | 'post'; | ||
@@ -22,7 +25,7 @@ export type BTNCallback<N, D = any> = (node: N) => D; | ||
}; | ||
export type BTNodeEntry<T> = [BTNKey | null | undefined, T | undefined]; | ||
export type BTNodeKeyOrNode<N> = BTNKey | null | undefined | N; | ||
export type BTNodeExemplar<T, N> = BTNodeEntry<T> | BTNodeKeyOrNode<N>; | ||
export type BTNodePureExemplar<T, N> = [BTNKey, T | undefined] | BTNodePureKeyOrNode<N>; | ||
export type BTNodePureKeyOrNode<N> = BTNKey | N; | ||
export type BSTNodeKeyOrNode<N> = BTNKey | undefined | N; | ||
export type BTNodeEntry<K, V> = [K | null | undefined, V | undefined]; | ||
export type BTNodeKeyOrNode<K, N> = K | null | undefined | N; | ||
export type BTNodeExemplar<K, V, N> = BTNodeEntry<K, V> | BTNodeKeyOrNode<K, N>; | ||
export type BTNodePureExemplar<K, V, N> = [K, V | undefined] | BTNodePureKeyOrNode<K, N>; | ||
export type BTNodePureKeyOrNode<K, N> = K | N; | ||
export type BSTNodeKeyOrNode<K, N> = K | undefined | N; |
"use strict"; | ||
Object.defineProperty(exports, "__esModule", { value: true }); | ||
exports.CP = void 0; | ||
exports.CP = exports.BSTVariant = void 0; | ||
var BSTVariant; | ||
(function (BSTVariant) { | ||
BSTVariant["MIN"] = "MIN"; | ||
BSTVariant["MAX"] = "MAX"; | ||
})(BSTVariant || (exports.BSTVariant = BSTVariant = {})); | ||
var CP; | ||
@@ -5,0 +10,0 @@ (function (CP) { |
import { AVLTree, AVLTreeNode } from '../../../data-structures'; | ||
import { BSTOptions } from './bst'; | ||
export type AVLTreeNodeNested<T> = AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, any>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>; | ||
export type AVLTreeNested<T, N extends AVLTreeNode<T, N>> = AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, any>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>; | ||
export type AVLTreeOptions = BSTOptions & {}; | ||
export type AVLTreeNodeNested<K, V> = AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, any>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>; | ||
export type AVLTreeNested<K, V, N extends AVLTreeNode<K, V, N>> = AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, any>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>; | ||
export type AVLTreeOptions<K> = BSTOptions<K> & {}; |
@@ -21,3 +21,2 @@ import { BinaryTree, BinaryTreeNode } from '../../../data-structures'; | ||
} | ||
export type BTNKey = number; | ||
export type BiTreeDeleteResult<N> = { | ||
@@ -27,7 +26,8 @@ deleted: N | null | undefined; | ||
}; | ||
export type BinaryTreeNodeNested<T> = BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, any>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>; | ||
export type BinaryTreeNested<T, N extends BinaryTreeNode<T, N>> = BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, any>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>; | ||
export type BinaryTreeOptions = { | ||
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>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>; | ||
export type BinaryTreeNested<K, V, N extends BinaryTreeNode<K, V, N>> = BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, any>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>; | ||
export type BinaryTreeOptions<K> = { | ||
iterationType: IterationType; | ||
extractor: (key: K) => number; | ||
}; | ||
export type NodeDisplayLayout = [string[], number, number, number]; |
import { BST, BSTNode } from '../../../data-structures'; | ||
import type { BinaryTreeOptions, BTNKey } from './binary-tree'; | ||
import { Comparator } from "../../common"; | ||
export type BSTNodeNested<T> = BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, any>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>; | ||
export type BSTNested<T, N extends BSTNode<T, N>> = BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, any>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>; | ||
export type BSTOptions = BinaryTreeOptions & { | ||
comparator: Comparator<BTNKey>; | ||
import type { BinaryTreeOptions } from './binary-tree'; | ||
import { BSTVariant } from "../../common"; | ||
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, N extends BSTNode<K, V, N>> = BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, any>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>; | ||
export type BSTOptions<K> = BinaryTreeOptions<K> & { | ||
variant: BSTVariant; | ||
}; |
@@ -7,4 +7,4 @@ import { RedBlackTree, RedBlackTreeNode } from '../../../data-structures'; | ||
} | ||
export type RedBlackTreeNodeNested<T> = RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, any>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>; | ||
export type RedBlackTreeNested<T, N extends RedBlackTreeNode<T, N>> = RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, any>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>; | ||
export type RBTreeOptions = BSTOptions & {}; | ||
export type RedBlackTreeNodeNested<K, V> = RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, any>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>; | ||
export type RedBlackTreeNested<K, V, N extends RedBlackTreeNode<K, V, N>> = RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, any>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>; | ||
export type RBTreeOptions<K> = BSTOptions<K> & {}; |
import { TreeMultimap, TreeMultimapNode } from '../../../data-structures'; | ||
import { AVLTreeOptions } from './avl-tree'; | ||
export type TreeMultimapNodeNested<T> = TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, any>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>; | ||
export type TreeMultimapNested<T, N extends TreeMultimapNode<T, N>> = TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, any>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>; | ||
export type TreeMultimapOptions = Omit<AVLTreeOptions, 'isMergeDuplicatedNodeByKey'> & {}; | ||
export type TreeMultimapNodeNested<K, V> = TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, any>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>; | ||
export type TreeMultimapNested<K, V, N extends TreeMultimapNode<K, V, N>> = TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, any>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>; | ||
export type TreeMultimapOptions<K> = Omit<AVLTreeOptions<K>, 'isMergeDuplicatedNodeByKey'> & {}; |
{ | ||
"name": "priority-queue-typed", | ||
"version": "1.48.2", | ||
"version": "1.48.3", | ||
"description": "Priority Queue, Min Priority Queue, Max Priority Queue. Javascript & Typescript Data Structure.", | ||
@@ -123,4 +123,4 @@ "main": "dist/index.js", | ||
"dependencies": { | ||
"data-structure-typed": "^1.48.2" | ||
"data-structure-typed": "^1.48.3" | ||
} | ||
} |
@@ -15,3 +15,2 @@ /** | ||
BSTNodeKeyOrNode, | ||
BTNKey, | ||
BTNodeExemplar | ||
@@ -22,6 +21,6 @@ } from '../../types'; | ||
export class AVLTreeNode<V = any, N extends AVLTreeNode<V, N> = AVLTreeNodeNested<V>> extends BSTNode<V, N> { | ||
export class AVLTreeNode<K = any, V = any, N extends AVLTreeNode<K, V, N> = AVLTreeNodeNested<K, V>> extends BSTNode<K, V, N> { | ||
height: number; | ||
constructor(key: BTNKey, value?: V) { | ||
constructor(key: K, value?: V) { | ||
super(key, value); | ||
@@ -42,9 +41,9 @@ this.height = 0; | ||
*/ | ||
export class AVLTree<V = any, N extends AVLTreeNode<V, N> = AVLTreeNode<V, AVLTreeNodeNested<V>>, TREE extends AVLTree<V, N, TREE> = AVLTree<V, N, AVLTreeNested<V, N>>> | ||
extends BST<V, N, TREE> | ||
implements IBinaryTree<V, N, TREE> { | ||
export class AVLTree<K = any, V = any, N extends AVLTreeNode<K, V, N> = AVLTreeNode<K, V, AVLTreeNodeNested<K, V>>, TREE extends AVLTree<K, V, N, TREE> = AVLTree<K, V, N, AVLTreeNested<K, V, N>>> | ||
extends BST<K, V, N, TREE> | ||
implements IBinaryTree<K, V, N, TREE> { | ||
/** | ||
* The constructor function initializes an AVLTree object with optional elements and options. | ||
* @param [elements] - The `elements` parameter is an optional iterable of `BTNodeExemplar<V, N>` | ||
* @param [elements] - The `elements` parameter is an optional iterable of `BTNodeExemplar<K, V, N>` | ||
* objects. It represents a collection of elements that will be added to the AVL tree during | ||
@@ -56,3 +55,3 @@ * initialization. | ||
*/ | ||
constructor(elements?: Iterable<BTNodeExemplar<V, N>>, options?: Partial<AVLTreeOptions>) { | ||
constructor(elements?: Iterable<BTNodeExemplar<K, V, N>>, options?: Partial<AVLTreeOptions<K>>) { | ||
super([], options); | ||
@@ -64,3 +63,3 @@ if (elements) super.addMany(elements); | ||
* The function creates a new AVL tree node with the specified key and value. | ||
* @param {BTNKey} key - The key parameter is the key value that will be associated with | ||
* @param {K} key - The key parameter is the key value that will be associated with | ||
* the new node. It is used to determine the position of the node in the binary search tree. | ||
@@ -72,4 +71,4 @@ * @param [value] - The parameter `value` is an optional value that can be assigned to the node. It is of | ||
*/ | ||
override createNode(key: BTNKey, value?: V): N { | ||
return new AVLTreeNode<V, N>(key, value) as N; | ||
override createNode(key: K, value?: V): N { | ||
return new AVLTreeNode<K, V, N>(key, value) as N; | ||
} | ||
@@ -84,6 +83,6 @@ | ||
*/ | ||
override createTree(options?: AVLTreeOptions): TREE { | ||
return new AVLTree<V, N, TREE>([], { | ||
override createTree(options?: AVLTreeOptions<K>): TREE { | ||
return new AVLTree<K, V, N, TREE>([], { | ||
iterationType: this.iterationType, | ||
comparator: this.comparator, ...options | ||
variant: this.variant, ...options | ||
}) as TREE; | ||
@@ -94,6 +93,6 @@ } | ||
* The function checks if an exemplar is an instance of AVLTreeNode. | ||
* @param exemplar - The `exemplar` parameter is of type `BTNodeExemplar<V, N>`. | ||
* @param exemplar - The `exemplar` parameter is of type `BTNodeExemplar<K, V, N>`. | ||
* @returns a boolean value indicating whether the exemplar is an instance of the AVLTreeNode class. | ||
*/ | ||
override isNode(exemplar: BTNodeExemplar<V, N>): exemplar is N { | ||
override isNode(exemplar: BTNodeExemplar<K, V, N>): exemplar is N { | ||
return exemplar instanceof AVLTreeNode; | ||
@@ -117,3 +116,3 @@ } | ||
*/ | ||
override add(keyOrNodeOrEntry: BTNodeExemplar<V, N>): N | undefined { | ||
override add(keyOrNodeOrEntry: BTNodeExemplar<K, V, N>): N | undefined { | ||
if (keyOrNodeOrEntry === null) return undefined; | ||
@@ -163,5 +162,5 @@ const inserted = super.add(keyOrNodeOrEntry); | ||
* tree. | ||
* @param {BTNKey | N | undefined} srcNode - The `srcNode` parameter represents the source node that | ||
* needs to be swapped with the destination node. It can be of type `BTNKey`, `N`, or `undefined`. | ||
* @param {BTNKey | N | undefined} destNode - The `destNode` parameter represents the destination | ||
* @param {K | N | undefined} srcNode - The `srcNode` parameter represents the source node that | ||
* needs to be swapped with the destination node. It can be of type `K`, `N`, or `undefined`. | ||
* @param {K | N | undefined} destNode - The `destNode` parameter represents the destination | ||
* node where the values from the source node will be swapped to. | ||
@@ -171,3 +170,3 @@ * @returns either the `destNode` object if both `srcNode` and `destNode` are defined, or `undefined` | ||
*/ | ||
protected override _swapProperties(srcNode: BSTNodeKeyOrNode<N>, destNode: BSTNodeKeyOrNode<N>): N | undefined { | ||
protected override _swapProperties(srcNode: BSTNodeKeyOrNode<K, N>, destNode: BSTNodeKeyOrNode<K, N>): N | undefined { | ||
srcNode = this.ensureNode(srcNode); | ||
@@ -174,0 +173,0 @@ destNode = this.ensureNode(destNode); |
@@ -14,8 +14,6 @@ /** | ||
BTNCallback, | ||
BTNKey, | ||
BTNodeExemplar, | ||
BTNodePureExemplar, | ||
Comparator | ||
BTNodePureExemplar | ||
} from '../../types'; | ||
import { CP, IterationType } from '../../types'; | ||
import { BSTVariant, CP, IterationType } from '../../types'; | ||
import { BinaryTree, BinaryTreeNode } from './binary-tree'; | ||
@@ -25,6 +23,6 @@ import { IBinaryTree } from '../../interfaces'; | ||
export class BSTNode<V = any, N extends BSTNode<V, N> = BSTNodeNested<V>> extends BinaryTreeNode<V, N> { | ||
export class BSTNode<K = any, V = any, N extends BSTNode<K, V, N> = BSTNodeNested<K, V>> extends BinaryTreeNode<K, V, N> { | ||
override parent?: N; | ||
constructor(key: BTNKey, value?: V) { | ||
constructor(key: K, value?: V) { | ||
super(key, value); | ||
@@ -86,5 +84,5 @@ this.parent = undefined; | ||
*/ | ||
export class BST<V = any, N extends BSTNode<V, N> = BSTNode<V, BSTNodeNested<V>>, TREE extends BST<V, N, TREE> = BST<V, N, BSTNested<V, N>>> | ||
extends BinaryTree<V, N, TREE> | ||
implements IBinaryTree<V, N, TREE> { | ||
export class BST<K = any, V = any, N extends BSTNode<K, V, N> = BSTNode<K, V, BSTNodeNested<K, V>>, TREE extends BST<K, V, N, TREE> = BST<K, V, N, BSTNested<K, V, N>>> | ||
extends BinaryTree<K, V, N, TREE> | ||
implements IBinaryTree<K, V, N, TREE> { | ||
@@ -100,9 +98,9 @@ | ||
*/ | ||
constructor(elements?: Iterable<BTNodeExemplar<V, N>>, options?: Partial<BSTOptions>) { | ||
constructor(elements?: Iterable<BTNodeExemplar<K, V, N>>, options?: Partial<BSTOptions<K>>) { | ||
super([], options); | ||
if (options) { | ||
const { comparator } = options; | ||
if (comparator) { | ||
this.comparator = comparator; | ||
const { variant } = options; | ||
if (variant) { | ||
this._variant = variant; | ||
} | ||
@@ -122,7 +120,11 @@ } | ||
comparator: Comparator<BTNKey> = (a, b) => a - b | ||
protected _variant = BSTVariant.MIN | ||
get variant() { | ||
return this._variant; | ||
} | ||
/** | ||
* The function creates a new binary search tree node with the given key and value. | ||
* @param {BTNKey} key - The key parameter is the key value that will be associated with | ||
* @param {K} key - The key parameter is the key value that will be associated with | ||
* the new node. It is used to determine the position of the node in the binary search tree. | ||
@@ -133,4 +135,4 @@ * @param [value] - The parameter `value` is an optional value that can be assigned to the node. It | ||
*/ | ||
override createNode(key: BTNKey, value?: V): N { | ||
return new BSTNode<V, N>(key, value) as N; | ||
override createNode(key: K, value?: V): N { | ||
return new BSTNode<K, V, N>(key, value) as N; | ||
} | ||
@@ -145,6 +147,6 @@ | ||
*/ | ||
override createTree(options?: Partial<BSTOptions>): TREE { | ||
return new BST<V, N, TREE>([], { | ||
override createTree(options?: Partial<BSTOptions<K>>): TREE { | ||
return new BST<K, V, N, TREE>([], { | ||
iterationType: this.iterationType, | ||
comparator: this.comparator, ...options | ||
variant: this.variant, ...options | ||
}) as TREE; | ||
@@ -155,6 +157,6 @@ } | ||
* The function checks if an exemplar is an instance of BSTNode. | ||
* @param exemplar - The `exemplar` parameter is a variable of type `BTNodeExemplar<V, N>`. | ||
* @param exemplar - The `exemplar` parameter is a variable of type `BTNodeExemplar<K, V, N>`. | ||
* @returns a boolean value indicating whether the exemplar is an instance of the BSTNode class. | ||
*/ | ||
override isNode(exemplar: BTNodeExemplar<V, N>): exemplar is N { | ||
override isNode(exemplar: BTNodeExemplar<K, V, N>): exemplar is N { | ||
return exemplar instanceof BSTNode; | ||
@@ -166,6 +168,6 @@ } | ||
* is valid, otherwise it returns undefined. | ||
* @param exemplar - The `exemplar` parameter is of type `BTNodeExemplar<V, N>`. | ||
* @param exemplar - The `exemplar` parameter is of type `BTNodeExemplar<K, V, N>`. | ||
* @returns a variable `node` which is of type `N` or `undefined`. | ||
*/ | ||
override exemplarToNode(exemplar: BTNodeExemplar<V, N>): N | undefined { | ||
override exemplarToNode(exemplar: BTNodeExemplar<K, V, N>): N | undefined { | ||
let node: N | undefined; | ||
@@ -183,3 +185,3 @@ if (exemplar === null || exemplar === undefined) { | ||
} | ||
} else if (this.isNodeKey(exemplar)) { | ||
} else if (this.isNotNodeInstance(exemplar)) { | ||
node = this.createNode(exemplar); | ||
@@ -207,3 +209,3 @@ } else { | ||
*/ | ||
override add(keyOrNodeOrEntry: BTNodeExemplar<V, N>): N | undefined { | ||
override add(keyOrNodeOrEntry: BTNodeExemplar<K, V, N>): N | undefined { | ||
const newNode = this.exemplarToNode(keyOrNodeOrEntry); | ||
@@ -276,3 +278,3 @@ if (newNode === undefined) return; | ||
override addMany( | ||
keysOrNodesOrEntries: Iterable<BTNodeExemplar<V, N>>, | ||
keysOrNodesOrEntries: Iterable<BTNodeExemplar<K, V, N>>, | ||
isBalanceAdd = true, | ||
@@ -289,5 +291,5 @@ iterationType = this.iterationType | ||
} | ||
const realBTNExemplars: BTNodePureExemplar<V, N>[] = []; | ||
const realBTNExemplars: BTNodePureExemplar<K, V, N>[] = []; | ||
const isRealBTNExemplar = (kve: BTNodeExemplar<V, N>): kve is BTNodePureExemplar<V, N> => { | ||
const isRealBTNExemplar = (kve: BTNodeExemplar<K, V, N>): kve is BTNodePureExemplar<K, V, N> => { | ||
if (kve === undefined || kve === null) return false; | ||
@@ -302,13 +304,13 @@ return !(this.isEntry(kve) && (kve[0] === undefined || kve[0] === null)); | ||
// TODO this addMany function is inefficient, it should be optimized | ||
let sorted: BTNodePureExemplar<V, N>[] = []; | ||
let sorted: BTNodePureExemplar<K, V, N>[] = []; | ||
sorted = realBTNExemplars.sort((a, b) => { | ||
let aR: number, bR: number; | ||
if (this.isEntry(a)) aR = a[0] | ||
else if (this.isRealNode(a)) aR = a.key | ||
else aR = a; | ||
if (this.isEntry(a)) aR = this.extractor(a[0]) | ||
else if (this.isRealNode(a)) aR = this.extractor(a.key) | ||
else aR = this.extractor(a); | ||
if (this.isEntry(b)) bR = b[0] | ||
else if (this.isRealNode(b)) bR = b.key | ||
else bR = b; | ||
if (this.isEntry(b)) bR = this.extractor(b[0]) | ||
else if (this.isRealNode(b)) bR = this.extractor(b.key) | ||
else bR = this.extractor(b); | ||
@@ -319,3 +321,3 @@ return aR - bR; | ||
const _dfs = (arr: BTNodePureExemplar<V, N>[]) => { | ||
const _dfs = (arr: BTNodePureExemplar<K, V, N>[]) => { | ||
if (arr.length === 0) return; | ||
@@ -355,6 +357,27 @@ | ||
/** | ||
* Time Complexity: O(n log n) - Adding each element individually in a balanced tree. | ||
* Space Complexity: O(n) - Additional space is required for the sorted array. | ||
*/ | ||
// /** | ||
// * Time Complexity: O(n log n) - Adding each element individually in a balanced tree. | ||
// * Space Complexity: O(n) - Additional space is required for the sorted array. | ||
// */ | ||
// | ||
// /** | ||
// * Time Complexity: O(log n) - Average case for a balanced tree. | ||
// * Space Complexity: O(1) - Constant space is used. | ||
// * | ||
// * The `lastKey` function returns the key of the rightmost node in a binary tree, or the key of the | ||
// * leftmost node if the comparison result is greater than. | ||
// * @param {K | N | undefined} beginRoot - The `beginRoot` parameter is optional and can be of | ||
// * type `K`, `N`, or `undefined`. It represents the starting point for finding the last key in | ||
// * the binary tree. If not provided, it defaults to the root of the binary tree (`this.root`). | ||
// * @param iterationType - The `iterationType` parameter is used to specify the type of iteration to | ||
// * be performed. It can have one of the following values: | ||
// * @returns the key of the rightmost node in the binary tree if the comparison result is less than, | ||
// * the key of the leftmost node if the comparison result is greater than, and the key of the | ||
// * rightmost node otherwise. If no node is found, it returns 0. | ||
// */ | ||
// lastKey(beginRoot: BSTNodeKeyOrNode<K,N> = this.root, iterationType = this.iterationType): K { | ||
// if (this._compare(0, 1) === CP.lt) return this.getRightMost(beginRoot, iterationType)?.key ?? 0; | ||
// else if (this._compare(0, 1) === CP.gt) return this.getLeftMost(beginRoot, iterationType)?.key ?? 0; | ||
// else return this.getRightMost(beginRoot, iterationType)?.key ?? 0; | ||
// } | ||
@@ -364,27 +387,6 @@ /** | ||
* Space Complexity: O(1) - Constant space is used. | ||
* | ||
* The `lastKey` function returns the key of the rightmost node in a binary tree, or the key of the | ||
* leftmost node if the comparison result is greater than. | ||
* @param {BTNKey | N | undefined} beginRoot - The `beginRoot` parameter is optional and can be of | ||
* type `BTNKey`, `N`, or `undefined`. It represents the starting point for finding the last key in | ||
* the binary tree. If not provided, it defaults to the root of the binary tree (`this.root`). | ||
* @param iterationType - The `iterationType` parameter is used to specify the type of iteration to | ||
* be performed. It can have one of the following values: | ||
* @returns the key of the rightmost node in the binary tree if the comparison result is less than, | ||
* the key of the leftmost node if the comparison result is greater than, and the key of the | ||
* rightmost node otherwise. If no node is found, it returns 0. | ||
*/ | ||
lastKey(beginRoot: BSTNodeKeyOrNode<N> = this.root, iterationType = this.iterationType): BTNKey { | ||
if (this._compare(0, 1) === CP.lt) return this.getRightMost(beginRoot, iterationType)?.key ?? 0; | ||
else if (this._compare(0, 1) === CP.gt) return this.getLeftMost(beginRoot, iterationType)?.key ?? 0; | ||
else return this.getRightMost(beginRoot, iterationType)?.key ?? 0; | ||
} | ||
/** | ||
* Time Complexity: O(log n) - Average case for a balanced tree. | ||
* Space Complexity: O(1) - Constant space is used. | ||
*/ | ||
/** | ||
* Time Complexity: O(log n) - Average case for a balanced tree. | ||
* Space Complexity: O(log n) - Space for the recursive call stack in the worst case. | ||
@@ -394,3 +396,3 @@ * | ||
* either recursive or iterative methods. | ||
* @param {BTNKey} key - The `key` parameter is the key value that we are searching for in the tree. | ||
* @param {K} key - The `key` parameter is the key value that we are searching for in the tree. | ||
* It is used to identify the node that we want to retrieve. | ||
@@ -403,3 +405,3 @@ * @param iterationType - The `iterationType` parameter is an optional parameter that specifies the | ||
*/ | ||
override getNodeByKey(key: BTNKey, iterationType = IterationType.ITERATIVE): N | undefined { | ||
override getNodeByKey(key: K, iterationType = IterationType.ITERATIVE): N | undefined { | ||
if (!this.root) return undefined; | ||
@@ -437,3 +439,3 @@ if (iterationType === IterationType.RECURSIVE) { | ||
* otherwise it returns the key itself. | ||
* @param {BTNKey | N | undefined} key - The `key` parameter can be of type `BTNKey`, `N`, or | ||
* @param {K | N | undefined} key - The `key` parameter can be of type `K`, `N`, or | ||
* `undefined`. | ||
@@ -444,4 +446,4 @@ * @param iterationType - The `iterationType` parameter is an optional parameter that specifies the | ||
*/ | ||
override ensureNode(key: BSTNodeKeyOrNode<N>, iterationType = IterationType.ITERATIVE): N | undefined { | ||
return this.isNodeKey(key) ? this.getNodeByKey(key, iterationType) : key; | ||
override ensureNode(key: BSTNodeKeyOrNode<K, N>, iterationType = IterationType.ITERATIVE): N | undefined { | ||
return this.isNotNodeInstance(key) ? this.getNodeByKey(key, iterationType) : key; | ||
} | ||
@@ -465,3 +467,3 @@ | ||
* searching for all nodes that match the identifier and return an array containing | ||
* @param {BTNKey | N | undefined} beginRoot - The `beginRoot` parameter represents the starting node | ||
* @param {K | N | undefined} beginRoot - The `beginRoot` parameter represents the starting node | ||
* for the traversal. It can be either a key value or a node object. If it is undefined, the | ||
@@ -477,3 +479,3 @@ * traversal will start from the root of the tree. | ||
onlyOne = false, | ||
beginRoot: BSTNodeKeyOrNode<N> = this.root, | ||
beginRoot: BSTNodeKeyOrNode<K, N> = this.root, | ||
iterationType = this.iterationType | ||
@@ -496,4 +498,4 @@ ): N[] { | ||
if (callback === this._defaultOneParamCallback) { | ||
if (this._compare(cur.key, identifier as number) === CP.gt) cur.left && _traverse(cur.left); | ||
if (this._compare(cur.key, identifier as number) === CP.lt) cur.right && _traverse(cur.right); | ||
if (this._compare(cur.key, identifier as K) === CP.gt) cur.left && _traverse(cur.left); | ||
if (this._compare(cur.key, identifier as K) === CP.lt) cur.right && _traverse(cur.right); | ||
} else { | ||
@@ -518,4 +520,4 @@ cur.left && _traverse(cur.left); | ||
if (callback === this._defaultOneParamCallback) { | ||
if (this._compare(cur.key, identifier as number) === CP.gt) cur.left && queue.push(cur.left); | ||
if (this._compare(cur.key, identifier as number) === CP.lt) cur.right && queue.push(cur.right); | ||
if (this._compare(cur.key, identifier as K) === CP.gt) cur.left && queue.push(cur.left); | ||
if (this._compare(cur.key, identifier as K) === CP.lt) cur.right && queue.push(cur.right); | ||
} else { | ||
@@ -550,3 +552,3 @@ cur.left && queue.push(cur.left); | ||
* `lesserOrGreater` are | ||
* @param {BTNKey | N | undefined} targetNode - The `targetNode` parameter represents the node in the | ||
* @param {K | N | undefined} targetNode - The `targetNode` parameter represents the node in the | ||
* binary tree that you want to traverse from. It can be specified either by its key, by the node | ||
@@ -562,3 +564,3 @@ * object itself, or it can be left undefined to start the traversal from the root of the tree. | ||
lesserOrGreater: CP = CP.lt, | ||
targetNode: BSTNodeKeyOrNode<N> = this.root, | ||
targetNode: BSTNodeKeyOrNode<K, N> = this.root, | ||
iterationType = this.iterationType | ||
@@ -734,13 +736,15 @@ ): ReturnType<C>[] { | ||
* is greater than, less than, or equal to the second value. | ||
* @param {BTNKey} a - The parameter "a" is of type BTNKey. | ||
* @param {BTNKey} b - The parameter "b" in the above code represents a BTNKey. | ||
* @param {K} a - The parameter "a" is of type K. | ||
* @param {K} b - The parameter "b" in the above code represents a K. | ||
* @returns a value of type CP (ComparisonResult). The possible return values are CP.gt (greater | ||
* than), CP.lt (less than), or CP.eq (equal). | ||
*/ | ||
protected _compare(a: BTNKey, b: BTNKey): CP { | ||
const compared = this.comparator(a, b); | ||
if (compared > 0) return CP.gt; | ||
else if (compared < 0) return CP.lt; | ||
else return CP.eq; | ||
protected _compare(a: K, b: K): CP { | ||
const extractedA = this.extractor(a); | ||
const extractedB = this.extractor(b); | ||
const compared = this.variant === BSTVariant.MIN ? extractedA - extractedB : extractedB - extractedA; | ||
return compared > 0 ? CP.gt : compared < 0 ? CP.lt : CP.eq; | ||
} | ||
} |
@@ -13,3 +13,2 @@ /** | ||
BTNCallback, | ||
BTNKey, | ||
BTNodeExemplar, | ||
@@ -26,4 +25,4 @@ IterationType, | ||
export class RedBlackTreeNode<V = any, N extends RedBlackTreeNode<V, N> = RedBlackTreeNodeNested<V>> extends BSTNode< | ||
V, | ||
export class RedBlackTreeNode<K = any, V = any, N extends RedBlackTreeNode<K, V, N> = RedBlackTreeNodeNested<K, V>> extends BSTNode< | ||
K, V, | ||
N | ||
@@ -33,3 +32,3 @@ > { | ||
constructor(key: BTNKey, value?: V, color: RBTNColor = RBTNColor.BLACK) { | ||
constructor(key: K, value?: V, color: RBTNColor = RBTNColor.BLACK) { | ||
super(key, value); | ||
@@ -47,6 +46,6 @@ this.color = color; | ||
*/ | ||
export class RedBlackTree<V = any, N extends RedBlackTreeNode<V, N> = RedBlackTreeNode<V, RedBlackTreeNodeNested<V>>, TREE extends RedBlackTree<V, N, TREE> = RedBlackTree<V, N, RedBlackTreeNested<V, N>>> | ||
extends BST<V, N, TREE> | ||
implements IBinaryTree<V, N, TREE> { | ||
Sentinel: N = new RedBlackTreeNode<V>(NaN) as unknown as N; | ||
export class RedBlackTree<K = any, V = any, N extends RedBlackTreeNode<K, V, N> = RedBlackTreeNode<K, V, RedBlackTreeNodeNested<K, V>>, TREE extends RedBlackTree<K, V, N, TREE> = RedBlackTree<K, V, N, RedBlackTreeNested<K, V, N>>> | ||
extends BST<K, V, N, TREE> | ||
implements IBinaryTree<K, V, N, TREE> { | ||
Sentinel: N = new RedBlackTreeNode<K, V>(NaN as K) as unknown as N; | ||
@@ -56,3 +55,3 @@ /** | ||
* initializes the tree with optional elements and options. | ||
* @param [elements] - The `elements` parameter is an optional iterable of `BTNodeExemplar<V, N>` | ||
* @param [elements] - The `elements` parameter is an optional iterable of `BTNodeExemplar<K, V, N>` | ||
* objects. It represents the initial elements that will be added to the RBTree during its | ||
@@ -65,3 +64,3 @@ * construction. If this parameter is provided, the `addMany` method is called to add all the | ||
*/ | ||
constructor(elements?: Iterable<BTNodeExemplar<V, N>>, options?: Partial<RBTreeOptions>) { | ||
constructor(elements?: Iterable<BTNodeExemplar<K, V, N>>, options?: Partial<RBTreeOptions<K>>) { | ||
super([], options); | ||
@@ -87,3 +86,3 @@ | ||
* The function creates a new Red-Black Tree node with the specified key, value, and color. | ||
* @param {BTNKey} key - The key parameter is the key value associated with the node. It is used to | ||
* @param {K} key - The key parameter is the key value associated with the node. It is used to | ||
* identify and compare nodes in the Red-Black Tree. | ||
@@ -98,4 +97,4 @@ * @param {V} [value] - The `value` parameter is an optional parameter that represents the value | ||
*/ | ||
override createNode(key: BTNKey, value?: V, color: RBTNColor = RBTNColor.BLACK): N { | ||
return new RedBlackTreeNode<V, N>(key, value, color) as N; | ||
override createNode(key: K, value?: V, color: RBTNColor = RBTNColor.BLACK): N { | ||
return new RedBlackTreeNode<K, V, N>(key, value, color) as N; | ||
} | ||
@@ -110,6 +109,6 @@ | ||
*/ | ||
override createTree(options?: RBTreeOptions): TREE { | ||
return new RedBlackTree<V, N, TREE>([], { | ||
override createTree(options?: RBTreeOptions<K>): TREE { | ||
return new RedBlackTree<K, V, N, TREE>([], { | ||
iterationType: this.iterationType, | ||
comparator: this.comparator, ...options | ||
variant: this.variant, ...options | ||
}) as TREE; | ||
@@ -120,7 +119,7 @@ } | ||
* The function checks if an exemplar is an instance of the RedBlackTreeNode class. | ||
* @param exemplar - The `exemplar` parameter is of type `BTNodeExemplar<V, N>`. | ||
* @param exemplar - The `exemplar` parameter is of type `BTNodeExemplar<K, V, N>`. | ||
* @returns a boolean value indicating whether the exemplar is an instance of the RedBlackTreeNode | ||
* class. | ||
*/ | ||
override isNode(exemplar: BTNodeExemplar<V, N>): exemplar is N { | ||
override isNode(exemplar: BTNodeExemplar<K, V, N>): exemplar is N { | ||
return exemplar instanceof RedBlackTreeNode; | ||
@@ -132,3 +131,3 @@ } | ||
* otherwise it returns undefined. | ||
* @param exemplar - BTNodeExemplar<V, N> - A generic type representing an exemplar of a binary tree | ||
* @param exemplar - BTNodeExemplar<K, V, N> - A generic type representing an exemplar of a binary tree | ||
* node. It can be either a node itself, an entry (key-value pair), a node key, or any other value | ||
@@ -138,3 +137,3 @@ * that is not a valid exemplar. | ||
*/ | ||
override exemplarToNode(exemplar: BTNodeExemplar<V, N>): N | undefined { | ||
override exemplarToNode(exemplar: BTNodeExemplar<K, V, N>): N | undefined { | ||
let node: N | undefined; | ||
@@ -153,3 +152,3 @@ | ||
} | ||
} else if (this.isNodeKey(exemplar)) { | ||
} else if (this.isNotNodeInstance(exemplar)) { | ||
node = this.createNode(exemplar, undefined, RBTNColor.RED); | ||
@@ -173,3 +172,3 @@ } else { | ||
*/ | ||
override add(keyOrNodeOrEntry: BTNodeExemplar<V, N>): N | undefined { | ||
override add(keyOrNodeOrEntry: BTNodeExemplar<K, V, N>): N | undefined { | ||
const newNode = this.exemplarToNode(keyOrNodeOrEntry); | ||
@@ -315,4 +314,4 @@ if (newNode === undefined) return; | ||
getNode<C extends BTNCallback<N, BTNKey>>( | ||
identifier: BTNKey, | ||
getNode<C extends BTNCallback<N, K>>( | ||
identifier: K, | ||
callback?: C, | ||
@@ -355,3 +354,3 @@ beginRoot?: N | undefined, | ||
* function should take a single parameter of type `N` (the type of the nodes in the binary tree) and | ||
* @param {BTNKey | N | undefined} beginRoot - The `beginRoot` parameter is the starting point for | ||
* @param {K | N | undefined} beginRoot - The `beginRoot` parameter is the starting point for | ||
* searching for a node in a binary tree. It can be either a key value or a node object. If it is not | ||
@@ -367,3 +366,3 @@ * provided, the search will start from the root of the binary tree. | ||
callback: C = this._defaultOneParamCallback as C, | ||
beginRoot: BSTNodeKeyOrNode<N> = this.root, | ||
beginRoot: BSTNodeKeyOrNode<K, N> = this.root, | ||
iterationType = this.iterationType | ||
@@ -370,0 +369,0 @@ ): N | null | undefined { |
@@ -8,9 +8,3 @@ /** | ||
*/ | ||
import type { | ||
BSTNodeKeyOrNode, | ||
BTNKey, | ||
BTNodeExemplar, | ||
TreeMultimapNodeNested, | ||
TreeMultimapOptions | ||
} from '../../types'; | ||
import type { BSTNodeKeyOrNode, BTNodeExemplar, TreeMultimapNodeNested, TreeMultimapOptions } from '../../types'; | ||
import { BiTreeDeleteResult, BTNCallback, FamilyPosition, IterationType, TreeMultimapNested } from '../../types'; | ||
@@ -21,5 +15,6 @@ import { IBinaryTree } from '../../interfaces'; | ||
export class TreeMultimapNode< | ||
K = any, | ||
V = any, | ||
N extends TreeMultimapNode<V, N> = TreeMultimapNodeNested<V> | ||
> extends AVLTreeNode<V, N> { | ||
N extends TreeMultimapNode<K, V, N> = TreeMultimapNodeNested<K, V> | ||
> extends AVLTreeNode<K, V, N> { | ||
count: number; | ||
@@ -29,3 +24,3 @@ | ||
* The constructor function initializes a BinaryTreeNode object with a key, value, and count. | ||
* @param {BTNKey} key - The `key` parameter is of type `BTNKey` and represents the unique identifier | ||
* @param {K} key - The `key` parameter is of type `K` and represents the unique identifier | ||
* of the binary tree node. | ||
@@ -38,3 +33,3 @@ * @param {V} [value] - The `value` parameter is an optional parameter of type `V`. It represents the value of the binary | ||
*/ | ||
constructor(key: BTNKey, value?: V, count = 1) { | ||
constructor(key: K, value?: V, count = 1) { | ||
super(key, value); | ||
@@ -48,8 +43,8 @@ this.count = count; | ||
*/ | ||
export class TreeMultimap<V = any, N extends TreeMultimapNode<V, N> = TreeMultimapNode<V, TreeMultimapNodeNested<V>>, | ||
TREE extends TreeMultimap<V, N, TREE> = TreeMultimap<V, N, TreeMultimapNested<V, N>>> | ||
extends AVLTree<V, N, TREE> | ||
implements IBinaryTree<V, N, TREE> { | ||
export class TreeMultimap<K = any, V = any, N extends TreeMultimapNode<K, V, N> = TreeMultimapNode<K, V, TreeMultimapNodeNested<K, V>>, | ||
TREE extends TreeMultimap<K, V, N, TREE> = TreeMultimap<K, V, N, TreeMultimapNested<K, V, N>>> | ||
extends AVLTree<K, V, N, TREE> | ||
implements IBinaryTree<K, V, N, TREE> { | ||
constructor(elements?: Iterable<BTNodeExemplar<V, N>>, options?: Partial<TreeMultimapOptions>) { | ||
constructor(elements?: Iterable<BTNodeExemplar<K, V, N>>, options?: Partial<TreeMultimapOptions<K>>) { | ||
super([], options); | ||
@@ -70,3 +65,3 @@ if (elements) this.addMany(elements); | ||
* The function creates a new BSTNode with the given key, value, and count. | ||
* @param {BTNKey} key - The key parameter is the unique identifier for the binary tree node. It is used to | ||
* @param {K} key - The key parameter is the unique identifier for the binary tree node. It is used to | ||
* distinguish one node from another in the tree. | ||
@@ -78,10 +73,10 @@ * @param {N} value - The `value` parameter represents the value that will be stored in the binary search tree node. | ||
*/ | ||
override createNode(key: BTNKey, value?: V, count?: number): N { | ||
override createNode(key: K, value?: V, count?: number): N { | ||
return new TreeMultimapNode(key, value, count) as N; | ||
} | ||
override createTree(options?: TreeMultimapOptions): TREE { | ||
return new TreeMultimap<V, N, TREE>([], { | ||
override createTree(options?: TreeMultimapOptions<K>): TREE { | ||
return new TreeMultimap<K, V, N, TREE>([], { | ||
iterationType: this.iterationType, | ||
comparator: this.comparator, ...options | ||
variant: this.variant, ...options | ||
}) as TREE; | ||
@@ -92,7 +87,7 @@ } | ||
* The function checks if an exemplar is an instance of the TreeMultimapNode class. | ||
* @param exemplar - The `exemplar` parameter is of type `BTNodeExemplar<V, N>`. | ||
* @param exemplar - The `exemplar` parameter is of type `BTNodeExemplar<K, V, N>`. | ||
* @returns a boolean value indicating whether the exemplar is an instance of the TreeMultimapNode | ||
* class. | ||
*/ | ||
override isNode(exemplar: BTNodeExemplar<V, N>): exemplar is N { | ||
override isNode(exemplar: BTNodeExemplar<K, V, N>): exemplar is N { | ||
return exemplar instanceof TreeMultimapNode; | ||
@@ -103,3 +98,3 @@ } | ||
* The function `exemplarToNode` converts an exemplar object into a node object. | ||
* @param exemplar - The `exemplar` parameter is of type `BTNodeExemplar<V, N>`, where `V` represents | ||
* @param exemplar - The `exemplar` parameter is of type `BTNodeExemplar<K, V, N>`, where `V` represents | ||
* the value type and `N` represents the node type. | ||
@@ -110,3 +105,3 @@ * @param [count=1] - The `count` parameter is an optional parameter that specifies the number of | ||
*/ | ||
override exemplarToNode(exemplar: BTNodeExemplar<V, N>, count = 1): N | undefined { | ||
override exemplarToNode(exemplar: BTNodeExemplar<K, V, N>, count = 1): N | undefined { | ||
let node: N | undefined; | ||
@@ -124,3 +119,3 @@ if (exemplar === undefined || exemplar === null) { | ||
} | ||
} else if (this.isNodeKey(exemplar)) { | ||
} else if (this.isNotNodeInstance(exemplar)) { | ||
node = this.createNode(exemplar, undefined, count); | ||
@@ -150,3 +145,3 @@ } else { | ||
*/ | ||
override add(keyOrNodeOrEntry: BTNodeExemplar<V, N>, count = 1): N | undefined { | ||
override add(keyOrNodeOrEntry: BTNodeExemplar<K, V, N>, count = 1): N | undefined { | ||
const newNode = this.exemplarToNode(keyOrNodeOrEntry, count); | ||
@@ -178,3 +173,3 @@ if (newNode === undefined) return; | ||
*/ | ||
override addMany(keysOrNodesOrEntries: Iterable<BTNodeExemplar<V, N>>): (N | undefined)[] { | ||
override addMany(keysOrNodesOrEntries: Iterable<BTNodeExemplar<K, V, N>>): (N | undefined)[] { | ||
return super.addMany(keysOrNodesOrEntries); | ||
@@ -361,9 +356,9 @@ } | ||
* `undefined` if there is no node to add. | ||
* @param {BTNKey | N | undefined} parent - The `parent` parameter represents the parent node to | ||
* @param {K | N | undefined} parent - The `parent` parameter represents the parent node to | ||
* which the new node will be added as a child. It can be either a node object (`N`) or a key value | ||
* (`BTNKey`). | ||
* (`K`). | ||
* @returns The method `_addTo` returns either the `parent.left` or `parent.right` node that was | ||
* added, or `undefined` if no node was added. | ||
*/ | ||
protected override _addTo(newNode: N | undefined, parent: BSTNodeKeyOrNode<N>): N | undefined { | ||
protected override _addTo(newNode: N | undefined, parent: BSTNodeKeyOrNode<K, N>): N | undefined { | ||
parent = this.ensureNode(parent); | ||
@@ -396,5 +391,5 @@ if (parent) { | ||
* The `_swapProperties` function swaps the key, value, count, and height properties between two nodes. | ||
* @param {BTNKey | N | undefined} srcNode - The `srcNode` parameter represents the source node from | ||
* which the values will be swapped. It can be of type `BTNKey`, `N`, or `undefined`. | ||
* @param {BTNKey | N | undefined} destNode - The `destNode` parameter represents the destination | ||
* @param {K | N | undefined} srcNode - The `srcNode` parameter represents the source node from | ||
* which the values will be swapped. It can be of type `K`, `N`, or `undefined`. | ||
* @param {K | N | undefined} destNode - The `destNode` parameter represents the destination | ||
* node where the values from the source node will be swapped to. | ||
@@ -404,3 +399,3 @@ * @returns either the `destNode` object if both `srcNode` and `destNode` are defined, or `undefined` | ||
*/ | ||
protected override _swapProperties(srcNode: BSTNodeKeyOrNode<N>, destNode: BSTNodeKeyOrNode<N>): N | undefined { | ||
protected override _swapProperties(srcNode: BSTNodeKeyOrNode<K, N>, destNode: BSTNodeKeyOrNode<K, N>): N | undefined { | ||
srcNode = this.ensureNode(srcNode); | ||
@@ -407,0 +402,0 @@ destNode = this.ensureNode(destNode); |
@@ -8,16 +8,15 @@ import { BinaryTree, BinaryTreeNode } from '../data-structures'; | ||
BTNCallback, | ||
BTNKey, | ||
BTNodeExemplar, | ||
} from '../types'; | ||
export interface IBinaryTree<V = any, N extends BinaryTreeNode<V, N> = BinaryTreeNodeNested<V>, TREE extends BinaryTree<V, N, TREE> = BinaryTreeNested<V, N>> { | ||
createNode(key: BTNKey, value?: N['value']): N; | ||
export interface IBinaryTree<K = number, V = any, N extends BinaryTreeNode<K, V, N> = BinaryTreeNodeNested<K, V>, TREE extends BinaryTree<K, V, N, TREE> = BinaryTreeNested<K, V, N>> { | ||
createNode(key: K, value?: N['value']): N; | ||
createTree(options?: Partial<BinaryTreeOptions>): TREE; | ||
createTree(options?: Partial<BinaryTreeOptions<K>>): TREE; | ||
add(keyOrNodeOrEntry: BTNodeExemplar<V, N>, count?: number): N | null | undefined; | ||
add(keyOrNodeOrEntry: BTNodeExemplar<K, V, N>, count?: number): N | null | undefined; | ||
addMany(nodes: Iterable<BTNodeExemplar<V, N>>): (N | null | undefined)[]; | ||
addMany(nodes: Iterable<BTNodeExemplar<K, V, N>>): (N | null | undefined)[]; | ||
delete<C extends BTNCallback<N>>(identifier: ReturnType<C> | null, callback: C): BiTreeDeleteResult<N>[]; | ||
} |
@@ -1,4 +0,7 @@ | ||
import { BTNKey } from "./data-structures"; | ||
export type Comparator<K> = (a: K, b: K) => number; | ||
export type Comparator<T> = (a: T, b: T) => number; | ||
export enum BSTVariant { | ||
MIN = 'MIN', | ||
MAX = 'MAX', | ||
} | ||
@@ -27,12 +30,12 @@ export type DFSOrderPattern = 'pre' | 'in' | 'post'; | ||
export type BTNodeEntry<T> = [BTNKey | null | undefined, T | undefined]; | ||
export type BTNodeEntry<K, V> = [K | null | undefined, V | undefined]; | ||
export type BTNodeKeyOrNode<N> = BTNKey | null | undefined | N; | ||
export type BTNodeKeyOrNode<K, N> = K | null | undefined | N; | ||
export type BTNodeExemplar<T, N> = BTNodeEntry<T> | BTNodeKeyOrNode<N> | ||
export type BTNodeExemplar<K, V, N> = BTNodeEntry<K, V> | BTNodeKeyOrNode<K, N> | ||
export type BTNodePureExemplar<T, N> = [BTNKey, T | undefined] | BTNodePureKeyOrNode<N> | ||
export type BTNodePureExemplar<K, V, N> = [K, V | undefined] | BTNodePureKeyOrNode<K, N> | ||
export type BTNodePureKeyOrNode<N> = BTNKey | N; | ||
export type BTNodePureKeyOrNode<K, N> = K | N; | ||
export type BSTNodeKeyOrNode<N> = BTNKey | undefined | N; | ||
export type BSTNodeKeyOrNode<K, N> = K | undefined | N; |
import { AVLTree, AVLTreeNode } from '../../../data-structures'; | ||
import { BSTOptions } from './bst'; | ||
export type AVLTreeNodeNested<T> = AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, AVLTreeNode<T, any>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> | ||
export type AVLTreeNodeNested<K, V> = AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, AVLTreeNode<K, V, any>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> | ||
export type AVLTreeNested<T, N extends AVLTreeNode<T, N>> = AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, AVLTree<T, N, any>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> | ||
export type AVLTreeNested<K, V, N extends AVLTreeNode<K, V, N>> = AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, AVLTree<K, V, N, any>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> | ||
export type AVLTreeOptions = BSTOptions & {}; | ||
export type AVLTreeOptions<K> = BSTOptions<K> & {}; |
@@ -25,12 +25,13 @@ import { BinaryTree, BinaryTreeNode } from '../../../data-structures'; | ||
export type BTNKey = number; | ||
export type BiTreeDeleteResult<N> = { deleted: N | null | undefined; needBalanced: N | null | undefined }; | ||
export type BinaryTreeNodeNested<T> = BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, BinaryTreeNode<T, any>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> | ||
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>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> | ||
export type BinaryTreeNested<T, N extends BinaryTreeNode<T, N>> = BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, BinaryTree<T, N, any>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> | ||
export type BinaryTreeNested<K, V, N extends BinaryTreeNode<K, V, N>> = BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, BinaryTree<K, V, N, any>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> | ||
export type BinaryTreeOptions = { iterationType: IterationType } | ||
export type BinaryTreeOptions<K> = { | ||
iterationType: IterationType, | ||
extractor: (key: K) => number | ||
} | ||
export type NodeDisplayLayout = [string[], number, number, number]; |
import { BST, BSTNode } from '../../../data-structures'; | ||
import type { BinaryTreeOptions, BTNKey } from './binary-tree'; | ||
import { Comparator } from "../../common"; | ||
import type { BinaryTreeOptions } from './binary-tree'; | ||
import { BSTVariant } from "../../common"; | ||
// prettier-ignore | ||
export type BSTNodeNested<T> = BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, BSTNode<T, any>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> | ||
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<T, N extends BSTNode<T, N>> = BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, BST<T, N, any>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> | ||
export type BSTNested<K, V, N extends BSTNode<K, V, N>> = BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, BST<K, V, N, any>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> | ||
export type BSTOptions = BinaryTreeOptions & { | ||
comparator: Comparator<BTNKey> | ||
export type BSTOptions<K> = BinaryTreeOptions<K> & { | ||
variant: BSTVariant | ||
} |
@@ -6,6 +6,6 @@ import { RedBlackTree, RedBlackTreeNode } from '../../../data-structures'; | ||
export type RedBlackTreeNodeNested<T> = RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, RedBlackTreeNode<T, any>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> | ||
export type RedBlackTreeNodeNested<K, V> = RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, RedBlackTreeNode<K, V, any>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> | ||
export type RedBlackTreeNested<T, N extends RedBlackTreeNode<T, N>> = RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, RedBlackTree<T, N, any>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> | ||
export type RedBlackTreeNested<K, V, N extends RedBlackTreeNode<K, V, N>> = RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, RedBlackTree<K, V, N, any>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> | ||
export type RBTreeOptions = BSTOptions & {}; | ||
export type RBTreeOptions<K> = BSTOptions<K> & {}; |
import { TreeMultimap, TreeMultimapNode } from '../../../data-structures'; | ||
import { AVLTreeOptions } from './avl-tree'; | ||
export type TreeMultimapNodeNested<T> = TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, TreeMultimapNode<T, any>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> | ||
export type TreeMultimapNodeNested<K, V> = TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, TreeMultimapNode<K, V, any>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> | ||
export type TreeMultimapNested<T, N extends TreeMultimapNode<T, N>> = TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, TreeMultimap<T, N, any>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> | ||
export type TreeMultimapNested<K, V, N extends TreeMultimapNode<K, V, N>> = TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, TreeMultimap<K, V, N, any>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> | ||
export type TreeMultimapOptions = Omit<AVLTreeOptions, 'isMergeDuplicatedNodeByKey'> & {} | ||
export type TreeMultimapOptions<K> = Omit<AVLTreeOptions<K>, 'isMergeDuplicatedNodeByKey'> & {} |
Sorry, the diff of this file is too big to display
Sorry, the diff of this file is too big to display
License Policy Violation
LicenseThis package is not allowed per your license policy. Review the package's license to ensure compliance.
Found 1 instance in 1 package
License Policy Violation
LicenseThis package is not allowed per your license policy. Review the package's license to ensure compliance.
Found 1 instance in 1 package
1993588
36311
Updateddata-structure-typed@^1.48.3