data-structure-typed
Advanced tools
data-structure-typed - npm Package Compare versions
Comparing version 1.18.5 to 1.18.6
@@ -9,3 +9,3 @@ /** | ||
| import { BST, BSTNode } from './bst'; | ||
| import type { AVLTreeDeleted, BinaryTreeNodeId, RecursiveAVLTreeNode } from '../types'; | ||
| import type { AVLTreeOptions, BinaryTreeDeletedResult, BinaryTreeNodeId, RecursiveAVLTreeNode } from '../types'; | ||
| import { IBinaryTreeNode } from '../interfaces'; | ||
@@ -15,2 +15,3 @@ export declare class AVLTreeNode<T, FAMILY extends AVLTreeNode<T, FAMILY> = RecursiveAVLTreeNode<T>> extends BSTNode<T, FAMILY> implements IBinaryTreeNode<T, FAMILY> { | ||
| export declare class AVLTree<N extends AVLTreeNode<N['val'], N> = AVLTreeNode<number>> extends BST<N> { | ||
| constructor(options?: AVLTreeOptions); | ||
| _createNode(id: BinaryTreeNodeId, val: N['val'], count?: number): N; | ||
@@ -40,3 +41,3 @@ /** | ||
| */ | ||
| remove(id: BinaryTreeNodeId, isUpdateAllLeftSum?: boolean): AVLTreeDeleted<N>[]; | ||
| remove(id: BinaryTreeNodeId, isUpdateAllLeftSum?: boolean): BinaryTreeDeletedResult<N>[]; | ||
| /** | ||
@@ -43,0 +44,0 @@ * The balance factor of a given AVL tree node is calculated by subtracting the height of its left subtree from the |
@@ -48,4 +48,4 @@ "use strict"; | ||
| __extends(AVLTree, _super); | ||
| function AVLTree() { | ||
| return _super !== null && _super.apply(this, arguments) || this; | ||
| function AVLTree(options) { | ||
| return _super.call(this, options) || this; | ||
| } | ||
@@ -52,0 +52,0 @@ AVLTree.prototype._createNode = function (id, val, count) { |
@@ -8,50 +8,10 @@ /** | ||
| */ | ||
| import type { BinaryTreeDeleted, BinaryTreeNodeId, BinaryTreeNodePropertyName, DFSOrderPattern, NodeOrPropertyName, RecursiveBinaryTreeNode, ResultsByProperty } from '../types'; | ||
| import type { BinaryTreeNodeId, RecursiveBinaryTreeNode } from '../types'; | ||
| import { BinaryTreeOptions } from '../types'; | ||
| import { IBinaryTree, IBinaryTreeNode } from '../interfaces'; | ||
| export declare enum FamilyPosition { | ||
| root = 0, | ||
| left = 1, | ||
| right = 2 | ||
| } | ||
| /** | ||
| * Enum representing different loop types. | ||
| * | ||
| * - `iterative`: Indicates the iterative loop type (with loops that use iterations). | ||
| * - `recursive`: Indicates the recursive loop type (with loops that call themselves). | ||
| */ | ||
| export declare enum LoopType { | ||
| iterative = 1, | ||
| recursive = 2 | ||
| } | ||
| export declare class BinaryTreeNode<T, FAMILY extends BinaryTreeNode<T, FAMILY> = RecursiveBinaryTreeNode<T>> implements IBinaryTreeNode<T, FAMILY> { | ||
| constructor(id: BinaryTreeNodeId, val: T, count?: number); | ||
| private _id; | ||
| get id(): BinaryTreeNodeId; | ||
| set id(v: BinaryTreeNodeId); | ||
| private _val; | ||
| get val(): T; | ||
| set val(v: T); | ||
| private _left?; | ||
| get left(): FAMILY | null | undefined; | ||
| set left(v: FAMILY | null | undefined); | ||
| private _right?; | ||
| get right(): FAMILY | null | undefined; | ||
| set right(v: FAMILY | null | undefined); | ||
| private _parent; | ||
| get parent(): FAMILY | null | undefined; | ||
| set parent(v: FAMILY | null | undefined); | ||
| private _familyPosition; | ||
| get familyPosition(): FamilyPosition; | ||
| set familyPosition(v: FamilyPosition); | ||
| private _count; | ||
| get count(): number; | ||
| set count(v: number); | ||
| private _height; | ||
| get height(): number; | ||
| set height(v: number); | ||
| import { AbstractBinaryTree, AbstractBinaryTreeNode } from './abstract-binary-tree'; | ||
| export declare class BinaryTreeNode<T = number, FAMILY extends BinaryTreeNode<T, FAMILY> = RecursiveBinaryTreeNode<T>> extends AbstractBinaryTreeNode<T, FAMILY> implements IBinaryTreeNode<T, FAMILY> { | ||
| _createNode(id: BinaryTreeNodeId, val: T | null, count?: number): FAMILY | null; | ||
| swapLocation(swapNode: FAMILY): FAMILY; | ||
| clone(): FAMILY | null; | ||
| } | ||
| export declare class BinaryTree<N extends BinaryTreeNode<N['val'], N> = BinaryTreeNode<number>> implements IBinaryTree<N> { | ||
| export declare class BinaryTree<N extends BinaryTreeNode<N['val'], N> = BinaryTreeNode> extends AbstractBinaryTree<N> implements IBinaryTree<N> { | ||
| /** | ||
@@ -62,31 +22,3 @@ * The constructor function accepts an optional options object and sets the values of loopType, autoIncrementId, and | ||
| */ | ||
| constructor(options?: { | ||
| loopType?: LoopType; | ||
| autoIncrementId?: boolean; | ||
| isDuplicatedVal?: boolean; | ||
| }); | ||
| private _loopType; | ||
| get loopType(): LoopType; | ||
| private _visitedId; | ||
| get visitedId(): BinaryTreeNodeId[]; | ||
| private _visitedVal; | ||
| get visitedVal(): Array<N['val']>; | ||
| private _visitedNode; | ||
| get visitedNode(): N[]; | ||
| private _visitedCount; | ||
| get visitedCount(): number[]; | ||
| private _visitedLeftSum; | ||
| get visitedLeftSum(): number[]; | ||
| private _autoIncrementId; | ||
| get autoIncrementId(): boolean; | ||
| private _maxId; | ||
| get maxId(): number; | ||
| private _isDuplicatedVal; | ||
| get isDuplicatedVal(): boolean; | ||
| private _root; | ||
| get root(): N | null; | ||
| private _size; | ||
| get size(): number; | ||
| private _count; | ||
| get count(): number; | ||
| constructor(options?: BinaryTreeOptions); | ||
| /** | ||
@@ -104,262 +36,2 @@ * The function creates a new binary tree node with the given id, value, and count if the value is not null, otherwise | ||
| _createNode(id: BinaryTreeNodeId, val: N['val'] | null, count?: number): N | null; | ||
| /** | ||
| * The clear function resets the state of an object by setting its properties to their initial values. | ||
| */ | ||
| clear(): void; | ||
| /** | ||
| * The function checks if the size of an object is equal to zero and returns a boolean value. | ||
| * @returns A boolean value indicating whether the size of the object is 0 or not. | ||
| */ | ||
| isEmpty(): boolean; | ||
| /** | ||
| * The `add` function inserts a new node with a given ID and value into a binary tree, updating the count if the node | ||
| * already exists. | ||
| * @param {BinaryTreeNodeId} id - The id parameter is the identifier of the binary tree node. It is used to uniquely | ||
| * identify each node in the binary tree. | ||
| * @param {N} val - The value to be inserted into the binary tree. | ||
| * @param {number} [count] - The `count` parameter is an optional parameter that specifies the number of times the | ||
| * value should be inserted into the binary tree. If not provided, it defaults to 1. | ||
| * @returns The function `add` returns a `N` object if a new node is inserted, or `null` if no new node | ||
| * is inserted, or `undefined` if the insertion fails. | ||
| */ | ||
| add(id: BinaryTreeNodeId, val: N['val'], count?: number): N | null | undefined; | ||
| /** | ||
| * The function inserts a new node into a binary tree as the left or right child of a given parent node. | ||
| * @param {N | null} newNode - The `newNode` parameter is an instance of the `BinaryTreeNode` class or | ||
| * `null`. It represents the node that needs to be inserted into the binary tree. | ||
| * @param parent - The `parent` parameter is a BinaryTreeNode object representing the parent node to which the new node | ||
| * will be inserted as a child. | ||
| * @returns The method returns the newly inserted node, either as the left child or the right child of the parent node. | ||
| */ | ||
| addTo(newNode: N | null, parent: N): N | null | undefined; | ||
| /** | ||
| * The `addMany` function inserts multiple items into a binary tree and returns an array of the inserted nodes or | ||
| * null/undefined values. | ||
| * @param {N[] | N[]} data - The `data` parameter can be either an array of elements of type `N` or an | ||
| * array of `N` objects. | ||
| * @returns The function `addMany` returns an array of `N`, `null`, or `undefined` values. | ||
| */ | ||
| addMany(data: N[] | Array<N['val']>): (N | null | undefined)[]; | ||
| /** | ||
| * The `fill` function clears the current data and inserts new data, returning a boolean indicating if the insertion | ||
| * was successful. | ||
| * @param {N[] | N[]} data - The `data` parameter can be either an array of elements of type `N` or an | ||
| * array of `N` objects. | ||
| * @returns The method is returning a boolean value. | ||
| */ | ||
| fill(data: N[] | Array<N['val']>): boolean; | ||
| /** | ||
| * The function removes a node from a binary tree and returns information about the deleted node. | ||
| * @param {BinaryTreeNodeId} id - The `id` parameter is the identifier of the binary tree node that you want to remove. | ||
| * It is of type `BinaryTreeNodeId`. | ||
| * @param {boolean} [ignoreCount] - The `ignoreCount` parameter is an optional boolean parameter that determines | ||
| * whether to ignore the count of the node being removed. If `ignoreCount` is set to `true`, the count of the node will | ||
| * not be decremented and the overall count of the binary tree will not be updated. If ` | ||
| * @returns An array of objects is being returned. Each object in the array has two properties: "deleted" and | ||
| * "needBalanced". The "deleted" property contains the deleted node or undefined if no node was deleted. The | ||
| * "needBalanced" property is always null. | ||
| */ | ||
| remove(id: BinaryTreeNodeId, ignoreCount?: boolean): BinaryTreeDeleted<N>[]; | ||
| /** | ||
| * The function calculates the depth of a binary tree node by traversing its parent nodes. | ||
| * @param node - N - This is the node for which we want to calculate the depth. It is a generic type, | ||
| * meaning it can represent any type of data that we want to store in the node. | ||
| * @returns The depth of the given binary tree node. | ||
| */ | ||
| getDepth(node: N): number; | ||
| /** | ||
| * The `getHeight` function calculates the maximum height of a binary tree using either a recursive or iterative | ||
| * approach. | ||
| * @param {N | null} [beginRoot] - The `beginRoot` parameter is an optional parameter of type | ||
| * `N | null`. It represents the starting node from which to calculate the height of the binary tree. | ||
| * If no value is provided for `beginRoot`, the function will use the `root` property of the class instance as | ||
| * @returns the height of the binary tree. | ||
| */ | ||
| getHeight(beginRoot?: N | null): number; | ||
| /** | ||
| * The `getMinHeight` function calculates the minimum height of a binary tree using either a recursive or iterative | ||
| * approach. | ||
| * @param {N | null} [beginRoot] - The `beginRoot` parameter is an optional parameter of type | ||
| * `N | null`. It represents the starting node from which to calculate the minimum height of the binary | ||
| * tree. If no value is provided for `beginRoot`, the function will use the root node of the binary tree. | ||
| * @returns The function `getMinHeight` returns the minimum height of the binary tree. | ||
| */ | ||
| getMinHeight(beginRoot?: N | null): number; | ||
| /** | ||
| * The function checks if a binary tree is balanced by comparing the minimum height and the maximum height of the tree. | ||
| * @param {N | null} [beginRoot] - The `beginRoot` parameter is the root node of a binary tree. It is | ||
| * of type `N | null`, which means it can either be a `BinaryTreeNode` object or `null`. | ||
| * @returns The method is returning a boolean value. | ||
| */ | ||
| isBalanced(beginRoot?: N | null): boolean; | ||
| /** | ||
| * The function `getNodes` returns an array of binary tree nodes that match a given property value, with options for | ||
| * searching recursively or iteratively. | ||
| * @param {BinaryTreeNodeId | N} nodeProperty - The `nodeProperty` parameter can be either a `BinaryTreeNodeId` or a | ||
| * generic type `N`. It represents the property of the binary tree node that you want to search for. | ||
| * @param {BinaryTreeNodePropertyName} [propertyName] - The `propertyName` parameter is an optional parameter that | ||
| * specifies the property name to use when searching for nodes. If not provided, it defaults to 'id'. | ||
| * @param {boolean} [onlyOne] - The `onlyOne` parameter is an optional boolean parameter that determines whether to | ||
| * return only one node that matches the `nodeProperty` or `propertyName` criteria. If `onlyOne` is set to `true`, the | ||
| * function will stop traversing the tree and return the first matching node. If ` | ||
| * @returns The function `getNodes` returns an array of `N | null | undefined` objects. | ||
| */ | ||
| getNodes(nodeProperty: BinaryTreeNodeId | N, propertyName?: BinaryTreeNodePropertyName, onlyOne?: boolean): (N | null | undefined)[]; | ||
| /** | ||
| * The function checks if a binary tree node has a specific property or if any node in the tree has a specific | ||
| * property. | ||
| * @param {BinaryTreeNodeId | N} nodeProperty - The `nodeProperty` parameter can be either a `BinaryTreeNodeId` or a | ||
| * generic type `N`. It represents the property of a binary tree node that you want to check. | ||
| * @param {BinaryTreeNodePropertyName} [propertyName] - The `propertyName` parameter is an optional parameter that | ||
| * specifies the name of the property to check for in the nodes. | ||
| * @returns a boolean value. | ||
| */ | ||
| has(nodeProperty: BinaryTreeNodeId | N, propertyName?: BinaryTreeNodePropertyName): boolean; | ||
| /** | ||
| * The function returns the first binary tree node that matches the given property name and value, or null if no match | ||
| * is found. | ||
| * @param {BinaryTreeNodeId | N} nodeProperty - The `nodeProperty` parameter can be either a `BinaryTreeNodeId` or a | ||
| * generic type `N`. It represents the property of the binary tree node that you want to search for. | ||
| * @param {BinaryTreeNodePropertyName} [propertyName] - The `propertyName` parameter is an optional parameter that | ||
| * specifies the property of the binary tree node to search for. If not provided, it defaults to `'id'`. | ||
| * @returns a BinaryTreeNode object or null. | ||
| */ | ||
| get(nodeProperty: BinaryTreeNodeId | N, propertyName?: BinaryTreeNodePropertyName): N | null; | ||
| /** | ||
| * The function getPathToRoot returns an array of BinaryTreeNode objects representing the path from a given node to the | ||
| * root of a binary tree. | ||
| * @param node - The `node` parameter is a BinaryTreeNode object. | ||
| * @returns The function `getPathToRoot` returns an array of `N` objects, representing the path from | ||
| * the given `node` to the root of the binary tree. | ||
| */ | ||
| getPathToRoot(node: N): N[]; | ||
| getLeftMost(): N | null; | ||
| getLeftMost(node: N): N; | ||
| getRightMost(): N | null; | ||
| getRightMost(node: N): N; | ||
| /** | ||
| * The `isBST` function checks if a binary tree is a binary search tree. | ||
| * @param {N | null} [node] - The `node` parameter is an optional parameter of type `N | ||
| * | null`. It represents the root node of the binary search tree (BST) that we want to check for validity. If no node | ||
| * is provided, the function will default to using the root node of the BST instance that | ||
| * @returns The `isBST` function returns a boolean value. It returns `true` if the binary tree is a valid binary search | ||
| * tree, and `false` otherwise. | ||
| */ | ||
| isBST(node?: N | null): boolean; | ||
| /** | ||
| * The function calculates the size and count of a subtree in a binary tree using either recursive or iterative | ||
| * traversal. | ||
| * @param {N | null | undefined} subTreeRoot - The `subTreeRoot` parameter is the root node of a binary | ||
| * tree. | ||
| * @returns The function `getSubTreeSizeAndCount` returns an array `[number, number]`. The first element of the array | ||
| * represents the size of the subtree, and the second element represents the count of the nodes in the subtree. | ||
| */ | ||
| getSubTreeSizeAndCount(subTreeRoot: N | null | undefined): [number, number]; | ||
| /** | ||
| * The function `subTreeSum` calculates the sum of a specified property in a binary tree, either recursively or | ||
| * iteratively. | ||
| * @param subTreeRoot - The subTreeRoot parameter is the root node of the subtree for which you want to calculate the | ||
| * sum. | ||
| * @param {BinaryTreeNodePropertyName} [propertyName] - The `propertyName` parameter is an optional parameter that | ||
| * specifies the property of the `BinaryTreeNode` object to use for calculating the sum. If `propertyName` is not | ||
| * provided, it defaults to `'val'`. | ||
| * @returns a number, which is the sum of the values of the nodes in the subtree rooted at `subTreeRoot`. | ||
| */ | ||
| subTreeSum(subTreeRoot: N, propertyName?: BinaryTreeNodePropertyName): number; | ||
| /** | ||
| * The function `subTreeAdd` adds a specified delta value to a property of each node in a binary tree. | ||
| * @param subTreeRoot - The `subTreeRoot` parameter is the root node of the subtree where the values will be modified. | ||
| * @param {number} delta - The `delta` parameter is a number that represents the amount by which the property value of | ||
| * each node in the subtree should be increased or decreased. | ||
| * @param {BinaryTreeNodePropertyName} [propertyName] - The `propertyName` parameter is an optional parameter that | ||
| * specifies the property of the `BinaryTreeNode` that should be modified. It defaults to `'id'` if not provided. | ||
| * @returns a boolean value, which is `true`. | ||
| */ | ||
| subTreeAdd(subTreeRoot: N, delta: number, propertyName?: BinaryTreeNodePropertyName): boolean; | ||
| BFS(): BinaryTreeNodeId[]; | ||
| BFS(nodeOrPropertyName: 'id'): BinaryTreeNodeId[]; | ||
| BFS(nodeOrPropertyName: 'val'): N['val'][]; | ||
| BFS(nodeOrPropertyName: 'node'): N[]; | ||
| BFS(nodeOrPropertyName: 'count'): number[]; | ||
| DFS(): BinaryTreeNodeId[]; | ||
| DFS(pattern?: DFSOrderPattern, nodeOrPropertyName?: 'id'): BinaryTreeNodeId[]; | ||
| DFS(pattern?: DFSOrderPattern, nodeOrPropertyName?: 'val'): N[]; | ||
| DFS(pattern?: DFSOrderPattern, nodeOrPropertyName?: 'node'): N[]; | ||
| DFS(pattern?: DFSOrderPattern, nodeOrPropertyName?: 'count'): number[]; | ||
| DFSIterative(): BinaryTreeNodeId[]; | ||
| DFSIterative(pattern?: DFSOrderPattern, nodeOrPropertyName?: 'id'): BinaryTreeNodeId[]; | ||
| DFSIterative(pattern?: DFSOrderPattern, nodeOrPropertyName?: 'val'): N[]; | ||
| DFSIterative(pattern?: DFSOrderPattern, nodeOrPropertyName?: 'node'): N[]; | ||
| DFSIterative(pattern?: DFSOrderPattern, nodeOrPropertyName?: 'count'): number[]; | ||
| levelIterative(node: N | null): BinaryTreeNodeId[]; | ||
| levelIterative(node: N | null, nodeOrPropertyName?: 'id'): BinaryTreeNodeId[]; | ||
| levelIterative(node: N | null, nodeOrPropertyName?: 'val'): N['val'][]; | ||
| levelIterative(node: N | null, nodeOrPropertyName?: 'node'): N[]; | ||
| levelIterative(node: N | null, nodeOrPropertyName?: 'count'): number[]; | ||
| listLevels(node: N | null): BinaryTreeNodeId[][]; | ||
| listLevels(node: N | null, nodeOrPropertyName?: 'id'): BinaryTreeNodeId[][]; | ||
| listLevels(node: N | null, nodeOrPropertyName?: 'val'): N['val'][][]; | ||
| listLevels(node: N | null, nodeOrPropertyName?: 'node'): N[][]; | ||
| listLevels(node: N | null, nodeOrPropertyName?: 'count'): number[][]; | ||
| /** | ||
| * The function returns the predecessor of a given node in a binary tree. | ||
| * @param node - The parameter `node` is a BinaryTreeNode object, representing a node in a binary tree. | ||
| * @returns the predecessor of the given node in a binary tree. | ||
| */ | ||
| getPredecessor(node: N): N; | ||
| morris(): BinaryTreeNodeId[]; | ||
| morris(pattern?: DFSOrderPattern, nodeOrPropertyName?: 'id'): BinaryTreeNodeId[]; | ||
| morris(pattern?: DFSOrderPattern, nodeOrPropertyName?: 'val'): N[]; | ||
| morris(pattern?: DFSOrderPattern, nodeOrPropertyName?: 'node'): N[]; | ||
| morris(pattern?: DFSOrderPattern, nodeOrPropertyName?: 'count'): number[]; | ||
| protected _setLoopType(value: LoopType): void; | ||
| protected _setVisitedId(value: BinaryTreeNodeId[]): void; | ||
| protected _setVisitedVal(value: Array<N>): void; | ||
| protected _setVisitedNode(value: N[]): void; | ||
| protected setVisitedCount(value: number[]): void; | ||
| protected _setVisitedLeftSum(value: number[]): void; | ||
| protected _setAutoIncrementId(value: boolean): void; | ||
| protected _setMaxId(value: number): void; | ||
| protected _setIsDuplicatedVal(value: boolean): void; | ||
| protected _setRoot(v: N | null): void; | ||
| protected _setSize(v: number): void; | ||
| protected _setCount(v: number): void; | ||
| /** | ||
| * The function resets the values of several arrays used for tracking visited nodes and their properties. | ||
| */ | ||
| protected _resetResults(): void; | ||
| /** | ||
| * The function checks if a given property of a binary tree node matches a specified value, and if so, adds the node to | ||
| * a result array. | ||
| * @param cur - The current binary tree node that is being checked. | ||
| * @param {(N | null | undefined)[]} result - An array that stores the matching nodes found during the | ||
| * traversal. | ||
| * @param {BinaryTreeNodeId | N} nodeProperty - The `nodeProperty` parameter is the value that we are searching for in | ||
| * the binary tree nodes. It can be either the `id`, `count`, or `val` property of the node. | ||
| * @param {BinaryTreeNodePropertyName} [propertyName] - The `propertyName` parameter is an optional parameter that | ||
| * specifies the property of the `BinaryTreeNode` object that you want to compare with the `nodeProperty` value. It can | ||
| * be one of the following values: 'id', 'count', or 'val'. If no `propertyName` is provided, | ||
| * @param {boolean} [onlyOne] - The `onlyOne` parameter is an optional boolean parameter that determines whether to | ||
| * stop after finding the first matching node or continue searching for all matching nodes. If `onlyOne` is set to | ||
| * `true`, the function will stop after finding the first matching node and return `true`. If `onlyOne | ||
| * @returns a boolean value indicating whether or not a node was pushed into the result array. | ||
| */ | ||
| protected _pushByPropertyNameStopOrNot(cur: N, result: (N | null | undefined)[], nodeProperty: BinaryTreeNodeId | N, propertyName?: BinaryTreeNodePropertyName, onlyOne?: boolean): boolean | undefined; | ||
| /** | ||
| * The function `_accumulatedByPropertyName` pushes a property value of a binary tree node into an array based on the | ||
| * provided property name or a default property name. | ||
| * @param node - The `node` parameter is of type `N`, which represents a node in a binary tree. | ||
| * @param {NodeOrPropertyName} [nodeOrPropertyName] - The parameter `nodeOrPropertyName` is an optional parameter that | ||
| * can be either a string representing a property name or a reference to a node object. If it is a string, it specifies | ||
| * the property name of the node that should be accumulated. If it is a node object, it specifies the node itself | ||
| */ | ||
| protected _accumulatedByPropertyName(node: N, nodeOrPropertyName?: NodeOrPropertyName): void; | ||
| /** | ||
| * The function `_getResultByPropertyName` returns different results based on the provided property name or defaulting | ||
| * to 'id'. | ||
| * @param {NodeOrPropertyName} [nodeOrPropertyName] - The parameter `nodeOrPropertyName` is an optional parameter that | ||
| * can accept a value of type `NodeOrPropertyName`. | ||
| * @returns The method returns an object of type `ResultsByProperty<T>`. | ||
| */ | ||
| protected _getResultByPropertyName(nodeOrPropertyName?: NodeOrPropertyName): ResultsByProperty<N>; | ||
| } |
@@ -9,175 +9,33 @@ "use strict"; | ||
| */ | ||
| var __values = (this && this.__values) || function(o) { | ||
| var s = typeof Symbol === "function" && Symbol.iterator, m = s && o[s], i = 0; | ||
| if (m) return m.call(o); | ||
| if (o && typeof o.length === "number") return { | ||
| next: function () { | ||
| if (o && i >= o.length) o = void 0; | ||
| return { value: o && o[i++], done: !o }; | ||
| } | ||
| var __extends = (this && this.__extends) || (function () { | ||
| var extendStatics = function (d, b) { | ||
| extendStatics = Object.setPrototypeOf || | ||
| ({ __proto__: [] } instanceof Array && function (d, b) { d.__proto__ = b; }) || | ||
| function (d, b) { for (var p in b) if (Object.prototype.hasOwnProperty.call(b, p)) d[p] = b[p]; }; | ||
| return extendStatics(d, b); | ||
| }; | ||
| throw new TypeError(s ? "Object is not iterable." : "Symbol.iterator is not defined."); | ||
| }; | ||
| var __read = (this && this.__read) || function (o, n) { | ||
| var m = typeof Symbol === "function" && o[Symbol.iterator]; | ||
| if (!m) return o; | ||
| var i = m.call(o), r, ar = [], e; | ||
| try { | ||
| while ((n === void 0 || n-- > 0) && !(r = i.next()).done) ar.push(r.value); | ||
| } | ||
| catch (error) { e = { error: error }; } | ||
| finally { | ||
| try { | ||
| if (r && !r.done && (m = i["return"])) m.call(i); | ||
| } | ||
| finally { if (e) throw e.error; } | ||
| } | ||
| return ar; | ||
| }; | ||
| return function (d, b) { | ||
| if (typeof b !== "function" && b !== null) | ||
| throw new TypeError("Class extends value " + String(b) + " is not a constructor or null"); | ||
| extendStatics(d, b); | ||
| function __() { this.constructor = d; } | ||
| d.prototype = b === null ? Object.create(b) : (__.prototype = b.prototype, new __()); | ||
| }; | ||
| })(); | ||
| Object.defineProperty(exports, "__esModule", { value: true }); | ||
| exports.BinaryTree = exports.BinaryTreeNode = exports.LoopType = exports.FamilyPosition = void 0; | ||
| var utils_1 = require("../../utils"); | ||
| /* This enumeration defines the position of a node within a family tree composed of three associated nodes, where 'root' represents the root node of the family tree, 'left' represents the left child node, and 'right' represents the right child node. */ | ||
| var FamilyPosition; | ||
| (function (FamilyPosition) { | ||
| FamilyPosition[FamilyPosition["root"] = 0] = "root"; | ||
| FamilyPosition[FamilyPosition["left"] = 1] = "left"; | ||
| FamilyPosition[FamilyPosition["right"] = 2] = "right"; | ||
| })(FamilyPosition || (exports.FamilyPosition = FamilyPosition = {})); | ||
| /** | ||
| * Enum representing different loop types. | ||
| * | ||
| * - `iterative`: Indicates the iterative loop type (with loops that use iterations). | ||
| * - `recursive`: Indicates the recursive loop type (with loops that call themselves). | ||
| */ | ||
| var LoopType; | ||
| (function (LoopType) { | ||
| LoopType[LoopType["iterative"] = 1] = "iterative"; | ||
| LoopType[LoopType["recursive"] = 2] = "recursive"; | ||
| })(LoopType || (exports.LoopType = LoopType = {})); | ||
| var BinaryTreeNode = /** @class */ (function () { | ||
| function BinaryTreeNode(id, val, count) { | ||
| this._familyPosition = FamilyPosition.root; | ||
| this._count = 1; | ||
| this._height = 0; | ||
| this._id = id; | ||
| this._val = val; | ||
| this._count = count !== null && count !== void 0 ? count : 1; | ||
| exports.BinaryTree = exports.BinaryTreeNode = void 0; | ||
| var abstract_binary_tree_1 = require("./abstract-binary-tree"); | ||
| var BinaryTreeNode = /** @class */ (function (_super) { | ||
| __extends(BinaryTreeNode, _super); | ||
| function BinaryTreeNode() { | ||
| return _super !== null && _super.apply(this, arguments) || this; | ||
| } | ||
| Object.defineProperty(BinaryTreeNode.prototype, "id", { | ||
| get: function () { | ||
| return this._id; | ||
| }, | ||
| set: function (v) { | ||
| this._id = v; | ||
| }, | ||
| enumerable: false, | ||
| configurable: true | ||
| }); | ||
| Object.defineProperty(BinaryTreeNode.prototype, "val", { | ||
| get: function () { | ||
| return this._val; | ||
| }, | ||
| set: function (v) { | ||
| this._val = v; | ||
| }, | ||
| enumerable: false, | ||
| configurable: true | ||
| }); | ||
| Object.defineProperty(BinaryTreeNode.prototype, "left", { | ||
| get: function () { | ||
| return this._left; | ||
| }, | ||
| set: function (v) { | ||
| if (v) { | ||
| v.parent = this; | ||
| v.familyPosition = FamilyPosition.left; | ||
| } | ||
| this._left = v; | ||
| }, | ||
| enumerable: false, | ||
| configurable: true | ||
| }); | ||
| Object.defineProperty(BinaryTreeNode.prototype, "right", { | ||
| get: function () { | ||
| return this._right; | ||
| }, | ||
| set: function (v) { | ||
| if (v) { | ||
| v.parent = this; | ||
| v.familyPosition = FamilyPosition.right; | ||
| } | ||
| this._right = v; | ||
| }, | ||
| enumerable: false, | ||
| configurable: true | ||
| }); | ||
| Object.defineProperty(BinaryTreeNode.prototype, "parent", { | ||
| get: function () { | ||
| return this._parent; | ||
| }, | ||
| set: function (v) { | ||
| this._parent = v; | ||
| }, | ||
| enumerable: false, | ||
| configurable: true | ||
| }); | ||
| Object.defineProperty(BinaryTreeNode.prototype, "familyPosition", { | ||
| get: function () { | ||
| return this._familyPosition; | ||
| }, | ||
| set: function (v) { | ||
| this._familyPosition = v; | ||
| }, | ||
| enumerable: false, | ||
| configurable: true | ||
| }); | ||
| Object.defineProperty(BinaryTreeNode.prototype, "count", { | ||
| get: function () { | ||
| return this._count; | ||
| }, | ||
| set: function (v) { | ||
| this._count = v; | ||
| }, | ||
| enumerable: false, | ||
| configurable: true | ||
| }); | ||
| Object.defineProperty(BinaryTreeNode.prototype, "height", { | ||
| get: function () { | ||
| return this._height; | ||
| }, | ||
| set: function (v) { | ||
| this._height = v; | ||
| }, | ||
| enumerable: false, | ||
| configurable: true | ||
| }); | ||
| BinaryTreeNode.prototype._createNode = function (id, val, count) { | ||
| return val !== null ? new BinaryTreeNode(id, val, count) : null; | ||
| }; | ||
| BinaryTreeNode.prototype.swapLocation = function (swapNode) { | ||
| var val = swapNode.val, count = swapNode.count, height = swapNode.height; | ||
| var tempNode = this._createNode(swapNode.id, val); | ||
| if (tempNode instanceof BinaryTreeNode) { | ||
| tempNode.val = val; | ||
| tempNode.count = count; | ||
| tempNode.height = height; | ||
| swapNode.id = this.id; | ||
| swapNode.val = this.val; | ||
| swapNode.count = this.count; | ||
| swapNode.height = this.height; | ||
| this.id = tempNode.id; | ||
| this.val = tempNode.val; | ||
| this.count = tempNode.count; | ||
| this.height = tempNode.height; | ||
| } | ||
| return swapNode; | ||
| }; | ||
| BinaryTreeNode.prototype.clone = function () { | ||
| return this._createNode(this.id, this.val, this.count); | ||
| }; | ||
| return BinaryTreeNode; | ||
| }()); | ||
| }(abstract_binary_tree_1.AbstractBinaryTreeNode)); | ||
| exports.BinaryTreeNode = BinaryTreeNode; | ||
| var BinaryTree = /** @class */ (function () { | ||
| var BinaryTree = /** @class */ (function (_super) { | ||
| __extends(BinaryTree, _super); | ||
| /** | ||
@@ -189,105 +47,4 @@ * The constructor function accepts an optional options object and sets the values of loopType, autoIncrementId, and | ||
| function BinaryTree(options) { | ||
| this._loopType = LoopType.iterative; | ||
| this._visitedId = []; | ||
| this._visitedVal = []; | ||
| this._visitedNode = []; | ||
| this._visitedCount = []; | ||
| this._visitedLeftSum = []; | ||
| this._autoIncrementId = false; | ||
| this._maxId = -1; | ||
| this._isDuplicatedVal = false; | ||
| this._root = null; | ||
| this._size = 0; | ||
| this._count = 0; | ||
| if (options !== undefined) { | ||
| var _a = options.loopType, loopType = _a === void 0 ? LoopType.iterative : _a, _b = options.autoIncrementId, autoIncrementId = _b === void 0 ? false : _b, _c = options.isDuplicatedVal, isDuplicatedVal = _c === void 0 ? false : _c; | ||
| this._isDuplicatedVal = isDuplicatedVal; | ||
| this._autoIncrementId = autoIncrementId; | ||
| this._loopType = loopType; | ||
| } | ||
| return _super.call(this) || this; | ||
| } | ||
| Object.defineProperty(BinaryTree.prototype, "loopType", { | ||
| get: function () { | ||
| return this._loopType; | ||
| }, | ||
| enumerable: false, | ||
| configurable: true | ||
| }); | ||
| Object.defineProperty(BinaryTree.prototype, "visitedId", { | ||
| get: function () { | ||
| return this._visitedId; | ||
| }, | ||
| enumerable: false, | ||
| configurable: true | ||
| }); | ||
| Object.defineProperty(BinaryTree.prototype, "visitedVal", { | ||
| get: function () { | ||
| return this._visitedVal; | ||
| }, | ||
| enumerable: false, | ||
| configurable: true | ||
| }); | ||
| Object.defineProperty(BinaryTree.prototype, "visitedNode", { | ||
| get: function () { | ||
| return this._visitedNode; | ||
| }, | ||
| enumerable: false, | ||
| configurable: true | ||
| }); | ||
| Object.defineProperty(BinaryTree.prototype, "visitedCount", { | ||
| get: function () { | ||
| return this._visitedCount; | ||
| }, | ||
| enumerable: false, | ||
| configurable: true | ||
| }); | ||
| Object.defineProperty(BinaryTree.prototype, "visitedLeftSum", { | ||
| get: function () { | ||
| return this._visitedLeftSum; | ||
| }, | ||
| enumerable: false, | ||
| configurable: true | ||
| }); | ||
| Object.defineProperty(BinaryTree.prototype, "autoIncrementId", { | ||
| get: function () { | ||
| return this._autoIncrementId; | ||
| }, | ||
| enumerable: false, | ||
| configurable: true | ||
| }); | ||
| Object.defineProperty(BinaryTree.prototype, "maxId", { | ||
| get: function () { | ||
| return this._maxId; | ||
| }, | ||
| enumerable: false, | ||
| configurable: true | ||
| }); | ||
| Object.defineProperty(BinaryTree.prototype, "isDuplicatedVal", { | ||
| get: function () { | ||
| return this._isDuplicatedVal; | ||
| }, | ||
| enumerable: false, | ||
| configurable: true | ||
| }); | ||
| Object.defineProperty(BinaryTree.prototype, "root", { | ||
| get: function () { | ||
| return this._root; | ||
| }, | ||
| enumerable: false, | ||
| configurable: true | ||
| }); | ||
| Object.defineProperty(BinaryTree.prototype, "size", { | ||
| get: function () { | ||
| return this._size; | ||
| }, | ||
| enumerable: false, | ||
| configurable: true | ||
| }); | ||
| Object.defineProperty(BinaryTree.prototype, "count", { | ||
| get: function () { | ||
| return this._count; | ||
| }, | ||
| enumerable: false, | ||
| configurable: true | ||
| }); | ||
| /** | ||
@@ -308,1171 +65,4 @@ * The function creates a new binary tree node with the given id, value, and count if the value is not null, otherwise | ||
| }; | ||
| /** | ||
| * The clear function resets the state of an object by setting its properties to their initial values. | ||
| */ | ||
| BinaryTree.prototype.clear = function () { | ||
| this._setRoot(null); | ||
| this._setSize(0); | ||
| this._setCount(0); | ||
| this._setMaxId(-1); | ||
| }; | ||
| /** | ||
| * The function checks if the size of an object is equal to zero and returns a boolean value. | ||
| * @returns A boolean value indicating whether the size of the object is 0 or not. | ||
| */ | ||
| BinaryTree.prototype.isEmpty = function () { | ||
| return this.size === 0; | ||
| }; | ||
| /** | ||
| * The `add` function inserts a new node with a given ID and value into a binary tree, updating the count if the node | ||
| * already exists. | ||
| * @param {BinaryTreeNodeId} id - The id parameter is the identifier of the binary tree node. It is used to uniquely | ||
| * identify each node in the binary tree. | ||
| * @param {N} val - The value to be inserted into the binary tree. | ||
| * @param {number} [count] - The `count` parameter is an optional parameter that specifies the number of times the | ||
| * value should be inserted into the binary tree. If not provided, it defaults to 1. | ||
| * @returns The function `add` returns a `N` object if a new node is inserted, or `null` if no new node | ||
| * is inserted, or `undefined` if the insertion fails. | ||
| */ | ||
| BinaryTree.prototype.add = function (id, val, count) { | ||
| var _this = this; | ||
| count = count !== null && count !== void 0 ? count : 1; | ||
| var _bfs = function (root, newNode) { | ||
| var queue = [root]; | ||
| while (queue.length > 0) { | ||
| var cur = queue.shift(); | ||
| if (cur) { | ||
| var inserted_1 = _this.addTo(newNode, cur); | ||
| if (inserted_1 !== undefined) | ||
| return inserted_1; | ||
| if (cur.left) | ||
| queue.push(cur.left); | ||
| if (cur.right) | ||
| queue.push(cur.right); | ||
| } | ||
| else | ||
| return; | ||
| } | ||
| return; | ||
| }; | ||
| var inserted; | ||
| var needInsert = val !== null ? this._createNode(id, val, count) : null; | ||
| var existNode = val !== null ? this.get(id, 'id') : null; | ||
| if (this.root) { | ||
| if (existNode) { | ||
| existNode.count += count; | ||
| existNode.val = val; | ||
| if (needInsert !== null) { | ||
| this._setCount(this.count + count); | ||
| inserted = existNode; | ||
| } | ||
| } | ||
| else { | ||
| inserted = _bfs(this.root, needInsert); | ||
| } | ||
| } | ||
| else { | ||
| this._setRoot(val !== null ? this._createNode(id, val, count) : null); | ||
| if (needInsert !== null) { | ||
| this._setSize(1); | ||
| this._setCount(count); | ||
| } | ||
| inserted = this.root; | ||
| } | ||
| return inserted; | ||
| }; | ||
| /** | ||
| * The function inserts a new node into a binary tree as the left or right child of a given parent node. | ||
| * @param {N | null} newNode - The `newNode` parameter is an instance of the `BinaryTreeNode` class or | ||
| * `null`. It represents the node that needs to be inserted into the binary tree. | ||
| * @param parent - The `parent` parameter is a BinaryTreeNode object representing the parent node to which the new node | ||
| * will be inserted as a child. | ||
| * @returns The method returns the newly inserted node, either as the left child or the right child of the parent node. | ||
| */ | ||
| BinaryTree.prototype.addTo = function (newNode, parent) { | ||
| var _a, _b; | ||
| if (parent) { | ||
| if (parent.left === undefined) { | ||
| if (newNode) { | ||
| newNode.parent = parent; | ||
| newNode.familyPosition = FamilyPosition.left; | ||
| } | ||
| parent.left = newNode; | ||
| if (newNode !== null) { | ||
| this._setSize(this.size + 1); | ||
| this._setCount((_a = this.count + newNode.count) !== null && _a !== void 0 ? _a : 0); | ||
| } | ||
| return parent.left; | ||
| } | ||
| else if (parent.right === undefined) { | ||
| if (newNode) { | ||
| newNode.parent = parent; | ||
| newNode.familyPosition = FamilyPosition.right; | ||
| } | ||
| parent.right = newNode; | ||
| if (newNode !== null) { | ||
| this._setSize(this.size + 1); | ||
| this._setCount((_b = this.count + newNode.count) !== null && _b !== void 0 ? _b : 0); | ||
| } | ||
| return parent.right; | ||
| } | ||
| else { | ||
| return; | ||
| } | ||
| } | ||
| else { | ||
| return; | ||
| } | ||
| }; | ||
| /** | ||
| * The `addMany` function inserts multiple items into a binary tree and returns an array of the inserted nodes or | ||
| * null/undefined values. | ||
| * @param {N[] | N[]} data - The `data` parameter can be either an array of elements of type `N` or an | ||
| * array of `N` objects. | ||
| * @returns The function `addMany` returns an array of `N`, `null`, or `undefined` values. | ||
| */ | ||
| BinaryTree.prototype.addMany = function (data) { | ||
| var e_1, _a, e_2, _b; | ||
| var _c; | ||
| var inserted = []; | ||
| var map = new Map(); | ||
| if (!this._isDuplicatedVal) { | ||
| try { | ||
| for (var data_1 = __values(data), data_1_1 = data_1.next(); !data_1_1.done; data_1_1 = data_1.next()) { | ||
| var i = data_1_1.value; | ||
| map.set(i, ((_c = map.get(i)) !== null && _c !== void 0 ? _c : 0) + 1); | ||
| } | ||
| } | ||
| catch (e_1_1) { e_1 = { error: e_1_1 }; } | ||
| finally { | ||
| try { | ||
| if (data_1_1 && !data_1_1.done && (_a = data_1.return)) _a.call(data_1); | ||
| } | ||
| finally { if (e_1) throw e_1.error; } | ||
| } | ||
| } | ||
| try { | ||
| for (var data_2 = __values(data), data_2_1 = data_2.next(); !data_2_1.done; data_2_1 = data_2.next()) { | ||
| var item = data_2_1.value; | ||
| var count = this._isDuplicatedVal ? 1 : map.get(item); | ||
| if (item instanceof BinaryTreeNode) { | ||
| inserted.push(this.add(item.id, item.val, item.count)); | ||
| } | ||
| else if (typeof item === 'number' && !this._autoIncrementId) { | ||
| if (!this._isDuplicatedVal) { | ||
| if (map.get(item) !== undefined) { | ||
| inserted.push(this.add(item, item, count)); | ||
| map.delete(item); | ||
| } | ||
| } | ||
| else { | ||
| inserted.push(this.add(item, item, 1)); | ||
| } | ||
| } | ||
| else { | ||
| if (item !== null) { | ||
| if (!this._isDuplicatedVal) { | ||
| if (map.get(item) !== undefined) { | ||
| inserted.push(this.add(++this._maxId, item, count)); | ||
| map.delete(item); | ||
| } | ||
| } | ||
| else { | ||
| inserted.push(this.add(++this._maxId, item, 1)); | ||
| } | ||
| } | ||
| else { | ||
| inserted.push(this.add(Number.MAX_SAFE_INTEGER, item, 0)); | ||
| } | ||
| } | ||
| } | ||
| } | ||
| catch (e_2_1) { e_2 = { error: e_2_1 }; } | ||
| finally { | ||
| try { | ||
| if (data_2_1 && !data_2_1.done && (_b = data_2.return)) _b.call(data_2); | ||
| } | ||
| finally { if (e_2) throw e_2.error; } | ||
| } | ||
| return inserted; | ||
| }; | ||
| /** | ||
| * The `fill` function clears the current data and inserts new data, returning a boolean indicating if the insertion | ||
| * was successful. | ||
| * @param {N[] | N[]} data - The `data` parameter can be either an array of elements of type `N` or an | ||
| * array of `N` objects. | ||
| * @returns The method is returning a boolean value. | ||
| */ | ||
| BinaryTree.prototype.fill = function (data) { | ||
| this.clear(); | ||
| return data.length === this.addMany(data).length; | ||
| }; | ||
| /** | ||
| * The function removes a node from a binary tree and returns information about the deleted node. | ||
| * @param {BinaryTreeNodeId} id - The `id` parameter is the identifier of the binary tree node that you want to remove. | ||
| * It is of type `BinaryTreeNodeId`. | ||
| * @param {boolean} [ignoreCount] - The `ignoreCount` parameter is an optional boolean parameter that determines | ||
| * whether to ignore the count of the node being removed. If `ignoreCount` is set to `true`, the count of the node will | ||
| * not be decremented and the overall count of the binary tree will not be updated. If ` | ||
| * @returns An array of objects is being returned. Each object in the array has two properties: "deleted" and | ||
| * "needBalanced". The "deleted" property contains the deleted node or undefined if no node was deleted. The | ||
| * "needBalanced" property is always null. | ||
| */ | ||
| BinaryTree.prototype.remove = function (id, ignoreCount) { | ||
| var nodes = this.getNodes(id, 'id', true); | ||
| var node = nodes[0]; | ||
| if (!node) | ||
| node = undefined; | ||
| else if (node.count > 1 && !ignoreCount) { | ||
| node.count--; | ||
| this._setCount(this.count - 1); | ||
| } | ||
| else if (node instanceof BinaryTreeNode) { | ||
| var _a = __read(this.getSubTreeSizeAndCount(node), 2), subSize = _a[0], subCount = _a[1]; | ||
| switch (node.familyPosition) { | ||
| case 0: | ||
| this._setSize(this.size - subSize); | ||
| this._setCount(this.count - subCount); | ||
| node = undefined; | ||
| break; | ||
| case 1: | ||
| if (node.parent) { | ||
| this._setSize(this.size - subSize); | ||
| this._setCount(this.count - subCount); | ||
| node.parent.left = null; | ||
| } | ||
| break; | ||
| case 2: | ||
| if (node.parent) { | ||
| this._setSize(this.size - subSize); | ||
| this._setCount(this.count - subCount); | ||
| node.parent.right = null; | ||
| } | ||
| break; | ||
| } | ||
| } | ||
| return [{ deleted: node, needBalanced: null }]; | ||
| }; | ||
| /** | ||
| * The function calculates the depth of a binary tree node by traversing its parent nodes. | ||
| * @param node - N - This is the node for which we want to calculate the depth. It is a generic type, | ||
| * meaning it can represent any type of data that we want to store in the node. | ||
| * @returns The depth of the given binary tree node. | ||
| */ | ||
| BinaryTree.prototype.getDepth = function (node) { | ||
| var depth = 0; | ||
| while (node.parent) { | ||
| depth++; | ||
| node = node.parent; | ||
| } | ||
| return depth; | ||
| }; | ||
| /** | ||
| * The `getHeight` function calculates the maximum height of a binary tree using either a recursive or iterative | ||
| * approach. | ||
| * @param {N | null} [beginRoot] - The `beginRoot` parameter is an optional parameter of type | ||
| * `N | null`. It represents the starting node from which to calculate the height of the binary tree. | ||
| * If no value is provided for `beginRoot`, the function will use the `root` property of the class instance as | ||
| * @returns the height of the binary tree. | ||
| */ | ||
| BinaryTree.prototype.getHeight = function (beginRoot) { | ||
| var _a, _b, _c; | ||
| beginRoot = beginRoot !== null && beginRoot !== void 0 ? beginRoot : this.root; | ||
| if (!beginRoot) | ||
| return -1; | ||
| if (this._loopType === LoopType.recursive) { | ||
| var _getMaxHeight_1 = function (cur) { | ||
| if (!cur) | ||
| return -1; | ||
| var leftHeight = _getMaxHeight_1(cur.left); | ||
| var rightHeight = _getMaxHeight_1(cur.right); | ||
| return Math.max(leftHeight, rightHeight) + 1; | ||
| }; | ||
| return _getMaxHeight_1(beginRoot); | ||
| } | ||
| else { | ||
| var stack = []; | ||
| var node = beginRoot, last = null; | ||
| var depths = new Map(); | ||
| while (stack.length > 0 || node) { | ||
| if (node) { | ||
| stack.push(node); | ||
| node = node.left; | ||
| } | ||
| else { | ||
| node = stack[stack.length - 1]; | ||
| if (!node.right || last === node.right) { | ||
| node = stack.pop(); | ||
| if (node) { | ||
| var leftHeight = node.left ? (_a = depths.get(node.left)) !== null && _a !== void 0 ? _a : -1 : -1; | ||
| var rightHeight = node.right ? (_b = depths.get(node.right)) !== null && _b !== void 0 ? _b : -1 : -1; | ||
| depths.set(node, 1 + Math.max(leftHeight, rightHeight)); | ||
| last = node; | ||
| node = null; | ||
| } | ||
| } | ||
| else | ||
| node = node.right; | ||
| } | ||
| } | ||
| return (_c = depths.get(beginRoot)) !== null && _c !== void 0 ? _c : -1; | ||
| } | ||
| }; | ||
| /** | ||
| * The `getMinHeight` function calculates the minimum height of a binary tree using either a recursive or iterative | ||
| * approach. | ||
| * @param {N | null} [beginRoot] - The `beginRoot` parameter is an optional parameter of type | ||
| * `N | null`. It represents the starting node from which to calculate the minimum height of the binary | ||
| * tree. If no value is provided for `beginRoot`, the function will use the root node of the binary tree. | ||
| * @returns The function `getMinHeight` returns the minimum height of the binary tree. | ||
| */ | ||
| BinaryTree.prototype.getMinHeight = function (beginRoot) { | ||
| var _a, _b, _c; | ||
| beginRoot = beginRoot || this.root; | ||
| if (!beginRoot) | ||
| return -1; | ||
| if (this._loopType === LoopType.recursive) { | ||
| var _getMinHeight_1 = function (cur) { | ||
| if (!cur) | ||
| return 0; | ||
| if (!cur.left && !cur.right) | ||
| return 0; | ||
| var leftMinHeight = _getMinHeight_1(cur.left); | ||
| var rightMinHeight = _getMinHeight_1(cur.right); | ||
| return Math.min(leftMinHeight, rightMinHeight) + 1; | ||
| }; | ||
| return _getMinHeight_1(beginRoot); | ||
| } | ||
| else { | ||
| var stack = []; | ||
| var node = beginRoot, last = null; | ||
| var depths = new Map(); | ||
| while (stack.length > 0 || node) { | ||
| if (node) { | ||
| stack.push(node); | ||
| node = node.left; | ||
| } | ||
| else { | ||
| node = stack[stack.length - 1]; | ||
| if (!node.right || last === node.right) { | ||
| node = stack.pop(); | ||
| if (node) { | ||
| var leftMinHeight = node.left ? (_a = depths.get(node.left)) !== null && _a !== void 0 ? _a : -1 : -1; | ||
| var rightMinHeight = node.right ? (_b = depths.get(node.right)) !== null && _b !== void 0 ? _b : -1 : -1; | ||
| depths.set(node, 1 + Math.min(leftMinHeight, rightMinHeight)); | ||
| last = node; | ||
| node = null; | ||
| } | ||
| } | ||
| else | ||
| node = node.right; | ||
| } | ||
| } | ||
| return (_c = depths.get(beginRoot)) !== null && _c !== void 0 ? _c : -1; | ||
| } | ||
| }; | ||
| /** | ||
| * The function checks if a binary tree is balanced by comparing the minimum height and the maximum height of the tree. | ||
| * @param {N | null} [beginRoot] - The `beginRoot` parameter is the root node of a binary tree. It is | ||
| * of type `N | null`, which means it can either be a `BinaryTreeNode` object or `null`. | ||
| * @returns The method is returning a boolean value. | ||
| */ | ||
| BinaryTree.prototype.isBalanced = function (beginRoot) { | ||
| return (this.getMinHeight(beginRoot) + 1 >= this.getHeight(beginRoot)); | ||
| }; | ||
| /** | ||
| * The function `getNodes` returns an array of binary tree nodes that match a given property value, with options for | ||
| * searching recursively or iteratively. | ||
| * @param {BinaryTreeNodeId | N} nodeProperty - The `nodeProperty` parameter can be either a `BinaryTreeNodeId` or a | ||
| * generic type `N`. It represents the property of the binary tree node that you want to search for. | ||
| * @param {BinaryTreeNodePropertyName} [propertyName] - The `propertyName` parameter is an optional parameter that | ||
| * specifies the property name to use when searching for nodes. If not provided, it defaults to 'id'. | ||
| * @param {boolean} [onlyOne] - The `onlyOne` parameter is an optional boolean parameter that determines whether to | ||
| * return only one node that matches the `nodeProperty` or `propertyName` criteria. If `onlyOne` is set to `true`, the | ||
| * function will stop traversing the tree and return the first matching node. If ` | ||
| * @returns The function `getNodes` returns an array of `N | null | undefined` objects. | ||
| */ | ||
| BinaryTree.prototype.getNodes = function (nodeProperty, propertyName, onlyOne) { | ||
| var _this = this; | ||
| if (!this.root) | ||
| return []; | ||
| propertyName = propertyName !== null && propertyName !== void 0 ? propertyName : 'id'; | ||
| var result = []; | ||
| if (this._loopType === LoopType.recursive) { | ||
| var _traverse_1 = function (cur) { | ||
| if (_this._pushByPropertyNameStopOrNot(cur, result, nodeProperty, propertyName, onlyOne)) | ||
| return; | ||
| if (!cur.left && !cur.right) | ||
| return; | ||
| cur.left && _traverse_1(cur.left); | ||
| cur.right && _traverse_1(cur.right); | ||
| }; | ||
| _traverse_1(this.root); | ||
| } | ||
| else { | ||
| var queue = [this.root]; | ||
| while (queue.length > 0) { | ||
| var cur = queue.shift(); | ||
| if (cur) { | ||
| if (this._pushByPropertyNameStopOrNot(cur, result, nodeProperty, propertyName, onlyOne)) | ||
| return result; | ||
| cur.left && queue.push(cur.left); | ||
| cur.right && queue.push(cur.right); | ||
| } | ||
| } | ||
| } | ||
| return result; | ||
| }; | ||
| /** | ||
| * The function checks if a binary tree node has a specific property or if any node in the tree has a specific | ||
| * property. | ||
| * @param {BinaryTreeNodeId | N} nodeProperty - The `nodeProperty` parameter can be either a `BinaryTreeNodeId` or a | ||
| * generic type `N`. It represents the property of a binary tree node that you want to check. | ||
| * @param {BinaryTreeNodePropertyName} [propertyName] - The `propertyName` parameter is an optional parameter that | ||
| * specifies the name of the property to check for in the nodes. | ||
| * @returns a boolean value. | ||
| */ | ||
| BinaryTree.prototype.has = function (nodeProperty, propertyName) { | ||
| return this.getNodes(nodeProperty, propertyName).length > 0; | ||
| }; | ||
| /** | ||
| * The function returns the first binary tree node that matches the given property name and value, or null if no match | ||
| * is found. | ||
| * @param {BinaryTreeNodeId | N} nodeProperty - The `nodeProperty` parameter can be either a `BinaryTreeNodeId` or a | ||
| * generic type `N`. It represents the property of the binary tree node that you want to search for. | ||
| * @param {BinaryTreeNodePropertyName} [propertyName] - The `propertyName` parameter is an optional parameter that | ||
| * specifies the property of the binary tree node to search for. If not provided, it defaults to `'id'`. | ||
| * @returns a BinaryTreeNode object or null. | ||
| */ | ||
| BinaryTree.prototype.get = function (nodeProperty, propertyName) { | ||
| var _a; | ||
| propertyName = propertyName !== null && propertyName !== void 0 ? propertyName : 'id'; | ||
| return (_a = this.getNodes(nodeProperty, propertyName, true)[0]) !== null && _a !== void 0 ? _a : null; | ||
| }; | ||
| /** | ||
| * The function getPathToRoot returns an array of BinaryTreeNode objects representing the path from a given node to the | ||
| * root of a binary tree. | ||
| * @param node - The `node` parameter is a BinaryTreeNode object. | ||
| * @returns The function `getPathToRoot` returns an array of `N` objects, representing the path from | ||
| * the given `node` to the root of the binary tree. | ||
| */ | ||
| BinaryTree.prototype.getPathToRoot = function (node) { | ||
| var result = []; | ||
| while (node.parent) { | ||
| result.unshift(node); | ||
| node = node.parent; | ||
| } | ||
| result.unshift(node); | ||
| return result; | ||
| }; | ||
| /** | ||
| * The `getLeftMost` function returns the leftmost node in a binary tree, either recursively or iteratively using tail | ||
| * recursion optimization. | ||
| * @param {N | null} [node] - The `node` parameter is an optional parameter of type `N | ||
| * | null`. It represents the starting node from which to find the leftmost node in a binary tree. If no node is | ||
| * provided, the function will use the root node of the binary tree. | ||
| * @returns The `getLeftMost` function returns the leftmost node in a binary tree. | ||
| */ | ||
| BinaryTree.prototype.getLeftMost = function (node) { | ||
| node = node !== null && node !== void 0 ? node : this.root; | ||
| if (!node) | ||
| return node; | ||
| if (this._loopType === LoopType.recursive) { | ||
| var _traverse_2 = function (cur) { | ||
| if (!cur.left) | ||
| return cur; | ||
| return _traverse_2(cur.left); | ||
| }; | ||
| return _traverse_2(node); | ||
| } | ||
| else { | ||
| // Indirect implementation of iteration using tail recursion optimization | ||
| var _traverse_3 = (0, utils_1.trampoline)(function (cur) { | ||
| if (!cur.left) | ||
| return cur; | ||
| return _traverse_3.cont(cur.left); | ||
| }); | ||
| return _traverse_3(node); | ||
| } | ||
| }; | ||
| /** | ||
| * The `getRightMost` function returns the rightmost node in a binary tree, either recursively or iteratively using | ||
| * tail recursion optimization. | ||
| * @param {N | null} [node] - The `node` parameter is an optional parameter of type `N | ||
| * | null`. It represents the starting node from which to find the rightmost node in a binary tree. If no node is | ||
| * provided, the function will use the root node of the binary tree. | ||
| * @returns The `getRightMost` function returns the rightmost node in a binary tree. | ||
| */ | ||
| BinaryTree.prototype.getRightMost = function (node) { | ||
| node = node !== null && node !== void 0 ? node : this.root; | ||
| if (!node) | ||
| return node; | ||
| if (this._loopType === LoopType.recursive) { | ||
| var _traverse_4 = function (cur) { | ||
| if (!cur.right) | ||
| return cur; | ||
| return _traverse_4(cur.right); | ||
| }; | ||
| return _traverse_4(node); | ||
| } | ||
| else { | ||
| // Indirect implementation of iteration using tail recursion optimization | ||
| var _traverse_5 = (0, utils_1.trampoline)(function (cur) { | ||
| if (!cur.right) | ||
| return cur; | ||
| return _traverse_5.cont(cur.right); | ||
| }); | ||
| return _traverse_5(node); | ||
| } | ||
| }; | ||
| /** | ||
| * The `isBST` function checks if a binary tree is a binary search tree. | ||
| * @param {N | null} [node] - The `node` parameter is an optional parameter of type `N | ||
| * | null`. It represents the root node of the binary search tree (BST) that we want to check for validity. If no node | ||
| * is provided, the function will default to using the root node of the BST instance that | ||
| * @returns The `isBST` function returns a boolean value. It returns `true` if the binary tree is a valid binary search | ||
| * tree, and `false` otherwise. | ||
| */ | ||
| BinaryTree.prototype.isBST = function (node) { | ||
| node = node !== null && node !== void 0 ? node : this.root; | ||
| if (!node) | ||
| return true; | ||
| if (this._loopType === LoopType.recursive) { | ||
| var dfs_1 = function (cur, min, max) { | ||
| if (!cur) | ||
| return true; | ||
| if (cur.id <= min || cur.id >= max) | ||
| return false; | ||
| return dfs_1(cur.left, min, cur.id) && dfs_1(cur.right, cur.id, max); | ||
| }; | ||
| return dfs_1(node, Number.MIN_SAFE_INTEGER, Number.MAX_SAFE_INTEGER); | ||
| } | ||
| else { | ||
| var stack = []; | ||
| var prev = Number.MIN_SAFE_INTEGER, curr = node; | ||
| while (curr || stack.length > 0) { | ||
| while (curr) { | ||
| stack.push(curr); | ||
| curr = curr.left; | ||
| } | ||
| curr = stack.pop(); | ||
| if (!(curr) || prev >= curr.id) | ||
| return false; | ||
| prev = curr.id; | ||
| curr = curr.right; | ||
| } | ||
| return true; | ||
| } | ||
| }; | ||
| /** | ||
| * The function calculates the size and count of a subtree in a binary tree using either recursive or iterative | ||
| * traversal. | ||
| * @param {N | null | undefined} subTreeRoot - The `subTreeRoot` parameter is the root node of a binary | ||
| * tree. | ||
| * @returns The function `getSubTreeSizeAndCount` returns an array `[number, number]`. The first element of the array | ||
| * represents the size of the subtree, and the second element represents the count of the nodes in the subtree. | ||
| */ | ||
| BinaryTree.prototype.getSubTreeSizeAndCount = function (subTreeRoot) { | ||
| var res = [0, 0]; | ||
| if (!subTreeRoot) | ||
| return res; | ||
| if (this._loopType === LoopType.recursive) { | ||
| var _traverse_6 = function (cur) { | ||
| res[0]++; | ||
| res[1] += cur.count; | ||
| cur.left && _traverse_6(cur.left); | ||
| cur.right && _traverse_6(cur.right); | ||
| }; | ||
| _traverse_6(subTreeRoot); | ||
| return res; | ||
| } | ||
| else { | ||
| var stack = [subTreeRoot]; | ||
| while (stack.length > 0) { | ||
| var cur = stack.pop(); | ||
| res[0]++; | ||
| res[1] += cur.count; | ||
| cur.right && stack.push(cur.right); | ||
| cur.left && stack.push(cur.left); | ||
| } | ||
| return res; | ||
| } | ||
| }; | ||
| // --- start additional methods --- | ||
| /** | ||
| * The function `subTreeSum` calculates the sum of a specified property in a binary tree, either recursively or | ||
| * iteratively. | ||
| * @param subTreeRoot - The subTreeRoot parameter is the root node of the subtree for which you want to calculate the | ||
| * sum. | ||
| * @param {BinaryTreeNodePropertyName} [propertyName] - The `propertyName` parameter is an optional parameter that | ||
| * specifies the property of the `BinaryTreeNode` object to use for calculating the sum. If `propertyName` is not | ||
| * provided, it defaults to `'val'`. | ||
| * @returns a number, which is the sum of the values of the nodes in the subtree rooted at `subTreeRoot`. | ||
| */ | ||
| BinaryTree.prototype.subTreeSum = function (subTreeRoot, propertyName) { | ||
| propertyName = propertyName !== null && propertyName !== void 0 ? propertyName : 'val'; | ||
| if (!subTreeRoot) | ||
| return 0; | ||
| var sum = 0; | ||
| var _sumByProperty = function (cur) { | ||
| var needSum; | ||
| switch (propertyName) { | ||
| case 'id': | ||
| needSum = cur.id; | ||
| break; | ||
| case 'count': | ||
| needSum = cur.count; | ||
| break; | ||
| case 'val': | ||
| needSum = typeof cur.val === 'number' ? cur.val : 0; | ||
| break; | ||
| default: | ||
| needSum = cur.id; | ||
| break; | ||
| } | ||
| return needSum; | ||
| }; | ||
| if (this._loopType === LoopType.recursive) { | ||
| var _traverse_7 = function (cur) { | ||
| sum += _sumByProperty(cur); | ||
| cur.left && _traverse_7(cur.left); | ||
| cur.right && _traverse_7(cur.right); | ||
| }; | ||
| _traverse_7(subTreeRoot); | ||
| } | ||
| else { | ||
| var stack = [subTreeRoot]; | ||
| while (stack.length > 0) { | ||
| var cur = stack.pop(); | ||
| sum += _sumByProperty(cur); | ||
| cur.right && stack.push(cur.right); | ||
| cur.left && stack.push(cur.left); | ||
| } | ||
| } | ||
| return sum; | ||
| }; | ||
| /** | ||
| * The function `subTreeAdd` adds a specified delta value to a property of each node in a binary tree. | ||
| * @param subTreeRoot - The `subTreeRoot` parameter is the root node of the subtree where the values will be modified. | ||
| * @param {number} delta - The `delta` parameter is a number that represents the amount by which the property value of | ||
| * each node in the subtree should be increased or decreased. | ||
| * @param {BinaryTreeNodePropertyName} [propertyName] - The `propertyName` parameter is an optional parameter that | ||
| * specifies the property of the `BinaryTreeNode` that should be modified. It defaults to `'id'` if not provided. | ||
| * @returns a boolean value, which is `true`. | ||
| */ | ||
| BinaryTree.prototype.subTreeAdd = function (subTreeRoot, delta, propertyName) { | ||
| var _this = this; | ||
| propertyName = propertyName !== null && propertyName !== void 0 ? propertyName : 'id'; | ||
| if (!subTreeRoot) | ||
| return false; | ||
| var _addByProperty = function (cur) { | ||
| switch (propertyName) { | ||
| case 'id': | ||
| cur.id += delta; | ||
| break; | ||
| case 'count': | ||
| cur.count += delta; | ||
| _this._setCount(_this.count + delta); | ||
| break; | ||
| default: | ||
| cur.id += delta; | ||
| break; | ||
| } | ||
| }; | ||
| if (this._loopType === LoopType.recursive) { | ||
| var _traverse_8 = function (cur) { | ||
| _addByProperty(cur); | ||
| cur.left && _traverse_8(cur.left); | ||
| cur.right && _traverse_8(cur.right); | ||
| }; | ||
| _traverse_8(subTreeRoot); | ||
| } | ||
| else { | ||
| var stack = [subTreeRoot]; | ||
| while (stack.length > 0) { | ||
| var cur = stack.pop(); | ||
| _addByProperty(cur); | ||
| cur.right && stack.push(cur.right); | ||
| cur.left && stack.push(cur.left); | ||
| } | ||
| } | ||
| return true; | ||
| }; | ||
| /** | ||
| * The BFS function performs a breadth-first search on a binary tree and returns the results based on a specified node | ||
| * or property name. | ||
| * @param {NodeOrPropertyName} [nodeOrPropertyName] - The parameter `nodeOrPropertyName` is an optional parameter that | ||
| * represents either a node or a property name. If a node is provided, the breadth-first search algorithm will be | ||
| * performed starting from that node. If a property name is provided, the breadth-first search algorithm will be | ||
| * performed starting from the root node | ||
| * @returns an object of type `ResultsByProperty<N>`. | ||
| */ | ||
| BinaryTree.prototype.BFS = function (nodeOrPropertyName) { | ||
| nodeOrPropertyName = nodeOrPropertyName !== null && nodeOrPropertyName !== void 0 ? nodeOrPropertyName : 'id'; | ||
| this._resetResults(); | ||
| var queue = [this.root]; | ||
| while (queue.length !== 0) { | ||
| var cur = queue.shift(); | ||
| if (cur) { | ||
| this._accumulatedByPropertyName(cur, nodeOrPropertyName); | ||
| if ((cur === null || cur === void 0 ? void 0 : cur.left) !== null) | ||
| queue.push(cur.left); | ||
| if ((cur === null || cur === void 0 ? void 0 : cur.right) !== null) | ||
| queue.push(cur.right); | ||
| } | ||
| } | ||
| return this._getResultByPropertyName(nodeOrPropertyName); | ||
| }; | ||
| /** | ||
| * The DFS function performs a depth-first search traversal on a binary tree and returns the results based on the | ||
| * specified pattern and node or property name. | ||
| * @param {'in' | 'pre' | 'post'} [pattern] - The "pattern" parameter is used to specify the order in which the nodes | ||
| * of a binary tree are traversed during the Depth-First Search (DFS) algorithm. It can take one of three values: 'in', | ||
| * 'pre', or 'post'. | ||
| * @param {NodeOrPropertyName} [nodeOrPropertyName] - The `nodeOrPropertyName` parameter is a string that represents | ||
| * either the name of a property in the `BinaryTreeNode` object or the value of the `id` property in the | ||
| * `BinaryTreeNode` object. This parameter is used to accumulate the results based on the specified property name. If | ||
| * no value | ||
| * @returns an object of type `ResultsByProperty<N>`. | ||
| */ | ||
| BinaryTree.prototype.DFS = function (pattern, nodeOrPropertyName) { | ||
| var _this = this; | ||
| pattern = pattern !== null && pattern !== void 0 ? pattern : 'in'; | ||
| nodeOrPropertyName = nodeOrPropertyName !== null && nodeOrPropertyName !== void 0 ? nodeOrPropertyName : 'id'; | ||
| this._resetResults(); | ||
| var _traverse = function (node) { | ||
| switch (pattern) { | ||
| case 'in': | ||
| if (node.left) | ||
| _traverse(node.left); | ||
| _this._accumulatedByPropertyName(node, nodeOrPropertyName); | ||
| if (node.right) | ||
| _traverse(node.right); | ||
| break; | ||
| case 'pre': | ||
| _this._accumulatedByPropertyName(node, nodeOrPropertyName); | ||
| if (node.left) | ||
| _traverse(node.left); | ||
| if (node.right) | ||
| _traverse(node.right); | ||
| break; | ||
| case 'post': | ||
| if (node.left) | ||
| _traverse(node.left); | ||
| if (node.right) | ||
| _traverse(node.right); | ||
| _this._accumulatedByPropertyName(node, nodeOrPropertyName); | ||
| break; | ||
| } | ||
| }; | ||
| this.root && _traverse(this.root); | ||
| return this._getResultByPropertyName(nodeOrPropertyName); | ||
| }; | ||
| /** | ||
| * Time complexity is O(n) | ||
| * Space complexity of Iterative DFS equals to recursive DFS which is O(n) because of the stack | ||
| * @param pattern | ||
| * @param nodeOrPropertyName | ||
| * @constructor | ||
| */ | ||
| BinaryTree.prototype.DFSIterative = function (pattern, nodeOrPropertyName) { | ||
| pattern = pattern || 'in'; | ||
| nodeOrPropertyName = nodeOrPropertyName || 'id'; | ||
| this._resetResults(); | ||
| if (!this.root) | ||
| return this._getResultByPropertyName(nodeOrPropertyName); | ||
| // 0: visit, 1: print | ||
| var stack = [{ opt: 0, node: this.root }]; | ||
| while (stack.length > 0) { | ||
| var cur = stack.pop(); | ||
| if (!cur || !cur.node) | ||
| continue; | ||
| if (cur.opt === 1) { | ||
| this._accumulatedByPropertyName(cur.node, nodeOrPropertyName); | ||
| } | ||
| else { | ||
| switch (pattern) { | ||
| case 'in': | ||
| stack.push({ opt: 0, node: cur.node.right }); | ||
| stack.push({ opt: 1, node: cur.node }); | ||
| stack.push({ opt: 0, node: cur.node.left }); | ||
| break; | ||
| case 'pre': | ||
| stack.push({ opt: 0, node: cur.node.right }); | ||
| stack.push({ opt: 0, node: cur.node.left }); | ||
| stack.push({ opt: 1, node: cur.node }); | ||
| break; | ||
| case 'post': | ||
| stack.push({ opt: 1, node: cur.node }); | ||
| stack.push({ opt: 0, node: cur.node.right }); | ||
| stack.push({ opt: 0, node: cur.node.left }); | ||
| break; | ||
| default: | ||
| stack.push({ opt: 0, node: cur.node.right }); | ||
| stack.push({ opt: 1, node: cur.node }); | ||
| stack.push({ opt: 0, node: cur.node.left }); | ||
| break; | ||
| } | ||
| } | ||
| } | ||
| return this._getResultByPropertyName(nodeOrPropertyName); | ||
| }; | ||
| /** | ||
| * The `levelIterative` function performs a level-order traversal on a binary tree and returns the values of the nodes | ||
| * in an array, based on a specified property name. | ||
| * @param {N | null} node - The `node` parameter is a BinaryTreeNode object representing the starting | ||
| * node for the level order traversal. It can be null if no specific node is provided, in which case the root node of | ||
| * the tree is used as the starting node. | ||
| * @param {NodeOrPropertyName} [nodeOrPropertyName] - The `nodeOrPropertyName` parameter is an optional parameter that | ||
| * can be either a `BinaryTreeNode` property name or the string `'id'`. If a property name is provided, the function | ||
| * will accumulate results based on that property. If no property name is provided, the function will default to | ||
| * accumulating results | ||
| * @returns The function `levelIterative` returns an object of type `ResultsByProperty<N>`. | ||
| */ | ||
| BinaryTree.prototype.levelIterative = function (node, nodeOrPropertyName) { | ||
| nodeOrPropertyName = nodeOrPropertyName || 'id'; | ||
| node = node || this.root; | ||
| if (!node) | ||
| return []; | ||
| this._resetResults(); | ||
| var queue = [node]; | ||
| while (queue.length > 0) { | ||
| var cur = queue.shift(); | ||
| if (cur) { | ||
| this._accumulatedByPropertyName(cur, nodeOrPropertyName); | ||
| if (cur.left) { | ||
| queue.push(cur.left); | ||
| } | ||
| if (cur.right) { | ||
| queue.push(cur.right); | ||
| } | ||
| } | ||
| } | ||
| return this._getResultByPropertyName(nodeOrPropertyName); | ||
| }; | ||
| /** | ||
| * The `listLevels` function collects nodes from a binary tree by a specified property and organizes them into levels. | ||
| * @param {N | null} node - The `node` parameter is a BinaryTreeNode object or null. It represents the | ||
| * root node of a binary tree. If it is null, the function will use the root node of the current binary tree instance. | ||
| * @param {NodeOrPropertyName} [nodeOrPropertyName] - The `nodeOrPropertyName` parameter is an optional parameter that | ||
| * specifies the property of the `BinaryTreeNode` object to collect at each level. It can be one of the following | ||
| * values: | ||
| * @returns The function `listLevels` returns a 2D array of `ResultByProperty<N>` objects. | ||
| */ | ||
| BinaryTree.prototype.listLevels = function (node, nodeOrPropertyName) { | ||
| nodeOrPropertyName = nodeOrPropertyName || 'id'; | ||
| node = node || this.root; | ||
| if (!node) | ||
| return []; | ||
| var levelsNodes = []; | ||
| var collectByProperty = function (node, level) { | ||
| switch (nodeOrPropertyName) { | ||
| case 'id': | ||
| levelsNodes[level].push(node.id); | ||
| break; | ||
| case 'val': | ||
| levelsNodes[level].push(node.val); | ||
| break; | ||
| case 'node': | ||
| levelsNodes[level].push(node); | ||
| break; | ||
| case 'count': | ||
| levelsNodes[level].push(node.count); | ||
| break; | ||
| default: | ||
| levelsNodes[level].push(node.id); | ||
| break; | ||
| } | ||
| }; | ||
| if (this._loopType === LoopType.recursive) { | ||
| var _recursive_1 = function (node, level) { | ||
| if (!levelsNodes[level]) | ||
| levelsNodes[level] = []; | ||
| collectByProperty(node, level); | ||
| if (node.left) | ||
| _recursive_1(node.left, level + 1); | ||
| if (node.right) | ||
| _recursive_1(node.right, level + 1); | ||
| }; | ||
| _recursive_1(node, 0); | ||
| } | ||
| else { | ||
| var stack = [[node, 0]]; | ||
| while (stack.length > 0) { | ||
| var head = stack.pop(); | ||
| var _a = __read(head, 2), node_1 = _a[0], level = _a[1]; | ||
| if (!levelsNodes[level]) | ||
| levelsNodes[level] = []; | ||
| collectByProperty(node_1, level); | ||
| if (node_1.right) | ||
| stack.push([node_1.right, level + 1]); | ||
| if (node_1.left) | ||
| stack.push([node_1.left, level + 1]); | ||
| } | ||
| } | ||
| return levelsNodes; | ||
| }; | ||
| /** | ||
| * The function returns the predecessor of a given node in a binary tree. | ||
| * @param node - The parameter `node` is a BinaryTreeNode object, representing a node in a binary tree. | ||
| * @returns the predecessor of the given node in a binary tree. | ||
| */ | ||
| BinaryTree.prototype.getPredecessor = function (node) { | ||
| if (node.left) { | ||
| var predecessor = node.left; | ||
| while (!(predecessor) || predecessor.right && predecessor.right !== node) { | ||
| if (predecessor) { | ||
| predecessor = predecessor.right; | ||
| } | ||
| } | ||
| return predecessor; | ||
| } | ||
| else { | ||
| return node; | ||
| } | ||
| }; | ||
| /** | ||
| * The `morris` function performs an in-order, pre-order, or post-order traversal on a binary tree using the Morris | ||
| * traversal algorithm and returns the results based on the specified property name. | ||
| * The time complexity of Morris traversal is O(n), it's may slower than others | ||
| * The space complexity Morris traversal is O(1) because no using stack | ||
| * @param {'in' | 'pre' | 'post'} [pattern] - The `pattern` parameter is an optional parameter that determines the | ||
| * traversal pattern of the binary tree. It can have one of three values: | ||
| * @param {NodeOrPropertyName} [nodeOrPropertyName] - The `nodeOrPropertyName` parameter is used to specify the | ||
| * property of the nodes that you want to retrieve in the results. It can be either the node itself or the name of the | ||
| * property. If not provided, it defaults to `'id'`. | ||
| * @returns The function `morris` returns an object of type `ResultsByProperty<N>`. | ||
| */ | ||
| BinaryTree.prototype.morris = function (pattern, nodeOrPropertyName) { | ||
| var _this = this; | ||
| if (this.root === null) | ||
| return []; | ||
| pattern = pattern || 'in'; | ||
| nodeOrPropertyName = nodeOrPropertyName || 'id'; | ||
| this._resetResults(); | ||
| var cur = this.root; | ||
| var _reverseEdge = function (node) { | ||
| var pre = null; | ||
| var next = null; | ||
| while (node) { | ||
| next = node.right; | ||
| node.right = pre; | ||
| pre = node; | ||
| node = next; | ||
| } | ||
| return pre; | ||
| }; | ||
| var _printEdge = function (node) { | ||
| var tail = _reverseEdge(node); | ||
| var cur = tail; | ||
| while (cur) { | ||
| _this._accumulatedByPropertyName(cur, nodeOrPropertyName); | ||
| cur = cur.right; | ||
| } | ||
| _reverseEdge(tail); | ||
| }; | ||
| switch (pattern) { | ||
| case 'in': | ||
| while (cur) { | ||
| if (cur.left) { | ||
| var predecessor = this.getPredecessor(cur); | ||
| if (!predecessor.right) { | ||
| predecessor.right = cur; | ||
| cur = cur.left; | ||
| continue; | ||
| } | ||
| else { | ||
| predecessor.right = null; | ||
| } | ||
| } | ||
| this._accumulatedByPropertyName(cur, nodeOrPropertyName); | ||
| cur = cur.right; | ||
| } | ||
| break; | ||
| case 'pre': | ||
| while (cur) { | ||
| if (cur.left) { | ||
| var predecessor = this.getPredecessor(cur); | ||
| if (!predecessor.right) { | ||
| predecessor.right = cur; | ||
| this._accumulatedByPropertyName(cur, nodeOrPropertyName); | ||
| cur = cur.left; | ||
| continue; | ||
| } | ||
| else { | ||
| predecessor.right = null; | ||
| } | ||
| } | ||
| else { | ||
| this._accumulatedByPropertyName(cur, nodeOrPropertyName); | ||
| } | ||
| cur = cur.right; | ||
| } | ||
| break; | ||
| case 'post': | ||
| while (cur) { | ||
| if (cur.left) { | ||
| var predecessor = this.getPredecessor(cur); | ||
| if (predecessor.right === null) { | ||
| predecessor.right = cur; | ||
| cur = cur.left; | ||
| continue; | ||
| } | ||
| else { | ||
| predecessor.right = null; | ||
| _printEdge(cur.left); | ||
| } | ||
| } | ||
| cur = cur.right; | ||
| } | ||
| _printEdge(this.root); | ||
| break; | ||
| } | ||
| return this._getResultByPropertyName(nodeOrPropertyName); | ||
| }; | ||
| BinaryTree.prototype._setLoopType = function (value) { | ||
| this._loopType = value; | ||
| }; | ||
| BinaryTree.prototype._setVisitedId = function (value) { | ||
| this._visitedId = value; | ||
| }; | ||
| BinaryTree.prototype._setVisitedVal = function (value) { | ||
| this._visitedVal = value; | ||
| }; | ||
| BinaryTree.prototype._setVisitedNode = function (value) { | ||
| this._visitedNode = value; | ||
| }; | ||
| BinaryTree.prototype.setVisitedCount = function (value) { | ||
| this._visitedCount = value; | ||
| }; | ||
| BinaryTree.prototype._setVisitedLeftSum = function (value) { | ||
| this._visitedLeftSum = value; | ||
| }; | ||
| BinaryTree.prototype._setAutoIncrementId = function (value) { | ||
| this._autoIncrementId = value; | ||
| }; | ||
| BinaryTree.prototype._setMaxId = function (value) { | ||
| this._maxId = value; | ||
| }; | ||
| BinaryTree.prototype._setIsDuplicatedVal = function (value) { | ||
| this._isDuplicatedVal = value; | ||
| }; | ||
| BinaryTree.prototype._setRoot = function (v) { | ||
| if (v) { | ||
| v.parent = null; | ||
| v.familyPosition = FamilyPosition.root; | ||
| } | ||
| this._root = v; | ||
| }; | ||
| BinaryTree.prototype._setSize = function (v) { | ||
| this._size = v; | ||
| }; | ||
| BinaryTree.prototype._setCount = function (v) { | ||
| this._count = v; | ||
| }; | ||
| /** | ||
| * The function resets the values of several arrays used for tracking visited nodes and their properties. | ||
| */ | ||
| BinaryTree.prototype._resetResults = function () { | ||
| this._visitedId = []; | ||
| this._visitedVal = []; | ||
| this._visitedNode = []; | ||
| this._visitedCount = []; | ||
| this._visitedLeftSum = []; | ||
| }; | ||
| /** | ||
| * The function checks if a given property of a binary tree node matches a specified value, and if so, adds the node to | ||
| * a result array. | ||
| * @param cur - The current binary tree node that is being checked. | ||
| * @param {(N | null | undefined)[]} result - An array that stores the matching nodes found during the | ||
| * traversal. | ||
| * @param {BinaryTreeNodeId | N} nodeProperty - The `nodeProperty` parameter is the value that we are searching for in | ||
| * the binary tree nodes. It can be either the `id`, `count`, or `val` property of the node. | ||
| * @param {BinaryTreeNodePropertyName} [propertyName] - The `propertyName` parameter is an optional parameter that | ||
| * specifies the property of the `BinaryTreeNode` object that you want to compare with the `nodeProperty` value. It can | ||
| * be one of the following values: 'id', 'count', or 'val'. If no `propertyName` is provided, | ||
| * @param {boolean} [onlyOne] - The `onlyOne` parameter is an optional boolean parameter that determines whether to | ||
| * stop after finding the first matching node or continue searching for all matching nodes. If `onlyOne` is set to | ||
| * `true`, the function will stop after finding the first matching node and return `true`. If `onlyOne | ||
| * @returns a boolean value indicating whether or not a node was pushed into the result array. | ||
| */ | ||
| BinaryTree.prototype._pushByPropertyNameStopOrNot = function (cur, result, nodeProperty, propertyName, onlyOne) { | ||
| switch (propertyName) { | ||
| case 'id': | ||
| if (cur.id === nodeProperty) { | ||
| result.push(cur); | ||
| return !!onlyOne; | ||
| } | ||
| break; | ||
| case 'count': | ||
| if (cur.count === nodeProperty) { | ||
| result.push(cur); | ||
| return !!onlyOne; | ||
| } | ||
| break; | ||
| case 'val': | ||
| if (cur.val === nodeProperty) { | ||
| result.push(cur); | ||
| return !!onlyOne; | ||
| } | ||
| break; | ||
| default: | ||
| if (cur.id === nodeProperty) { | ||
| result.push(cur); | ||
| return !!onlyOne; | ||
| } | ||
| break; | ||
| } | ||
| }; | ||
| /** | ||
| * The function `_accumulatedByPropertyName` pushes a property value of a binary tree node into an array based on the | ||
| * provided property name or a default property name. | ||
| * @param node - The `node` parameter is of type `N`, which represents a node in a binary tree. | ||
| * @param {NodeOrPropertyName} [nodeOrPropertyName] - The parameter `nodeOrPropertyName` is an optional parameter that | ||
| * can be either a string representing a property name or a reference to a node object. If it is a string, it specifies | ||
| * the property name of the node that should be accumulated. If it is a node object, it specifies the node itself | ||
| */ | ||
| BinaryTree.prototype._accumulatedByPropertyName = function (node, nodeOrPropertyName) { | ||
| nodeOrPropertyName = nodeOrPropertyName !== null && nodeOrPropertyName !== void 0 ? nodeOrPropertyName : 'id'; | ||
| switch (nodeOrPropertyName) { | ||
| case 'id': | ||
| this._visitedId.push(node.id); | ||
| break; | ||
| case 'val': | ||
| this._visitedVal.push(node.val); | ||
| break; | ||
| case 'node': | ||
| this._visitedNode.push(node); | ||
| break; | ||
| case 'count': | ||
| this._visitedCount.push(node.count); | ||
| break; | ||
| default: | ||
| this._visitedId.push(node.id); | ||
| break; | ||
| } | ||
| }; | ||
| /** | ||
| * The function `_getResultByPropertyName` returns different results based on the provided property name or defaulting | ||
| * to 'id'. | ||
| * @param {NodeOrPropertyName} [nodeOrPropertyName] - The parameter `nodeOrPropertyName` is an optional parameter that | ||
| * can accept a value of type `NodeOrPropertyName`. | ||
| * @returns The method returns an object of type `ResultsByProperty<T>`. | ||
| */ | ||
| BinaryTree.prototype._getResultByPropertyName = function (nodeOrPropertyName) { | ||
| nodeOrPropertyName = nodeOrPropertyName !== null && nodeOrPropertyName !== void 0 ? nodeOrPropertyName : 'id'; | ||
| switch (nodeOrPropertyName) { | ||
| case 'id': | ||
| return this._visitedId; | ||
| case 'val': | ||
| return this._visitedVal; | ||
| case 'node': | ||
| return this._visitedNode; | ||
| case 'count': | ||
| return this._visitedCount; | ||
| default: | ||
| return this._visitedId; | ||
| } | ||
| }; | ||
| return BinaryTree; | ||
| }()); | ||
| }(abstract_binary_tree_1.AbstractBinaryTree)); | ||
| exports.BinaryTree = BinaryTree; |
@@ -8,10 +8,6 @@ /** | ||
| */ | ||
| import type { BinaryTreeNodeId, BinaryTreeNodePropertyName, BSTComparator, BSTDeletedResult, RecursiveBSTNode } from '../types'; | ||
| import { BinaryTree, BinaryTreeNode, LoopType } from './binary-tree'; | ||
| import type { BinaryTreeNodeId, BinaryTreeNodePropertyName, BSTComparator, RecursiveBSTNode } from '../types'; | ||
| import { BinaryTreeDeletedResult, BSTOptions, CP } from '../types'; | ||
| import { BinaryTree, BinaryTreeNode } from './binary-tree'; | ||
| import { IBinaryTree, IBinaryTreeNode } from '../interfaces'; | ||
| export declare enum CP { | ||
| lt = -1, | ||
| eq = 0, | ||
| gt = 1 | ||
| } | ||
| export declare class BSTNode<T, FAMILY extends BSTNode<T, FAMILY> = RecursiveBSTNode<T>> extends BinaryTreeNode<T, FAMILY> implements IBinaryTreeNode<T, FAMILY> { | ||
@@ -24,6 +20,3 @@ } | ||
| */ | ||
| constructor(options?: { | ||
| comparator?: BSTComparator; | ||
| loopType?: LoopType; | ||
| }); | ||
| constructor(options?: BSTOptions); | ||
| _createNode(id: BinaryTreeNodeId, val: N['val'] | null, count?: number): N | null; | ||
@@ -72,3 +65,3 @@ /** | ||
| */ | ||
| remove(id: BinaryTreeNodeId, ignoreCount?: boolean): BSTDeletedResult<N>[]; | ||
| remove(id: BinaryTreeNodeId, ignoreCount?: boolean): BinaryTreeDeletedResult<N>[]; | ||
| /** | ||
@@ -75,0 +68,0 @@ * The function `getNodes` returns an array of binary search tree nodes that match a given property value, with the |
@@ -34,10 +34,5 @@ "use strict"; | ||
| Object.defineProperty(exports, "__esModule", { value: true }); | ||
| exports.BST = exports.BSTNode = exports.CP = void 0; | ||
| exports.BST = exports.BSTNode = void 0; | ||
| var types_1 = require("../types"); | ||
| var binary_tree_1 = require("./binary-tree"); | ||
| var CP; | ||
| (function (CP) { | ||
| CP[CP["lt"] = -1] = "lt"; | ||
| CP[CP["eq"] = 0] = "eq"; | ||
| CP[CP["gt"] = 1] = "gt"; | ||
| })(CP || (exports.CP = CP = {})); | ||
| var BSTNode = /** @class */ (function (_super) { | ||
@@ -99,3 +94,3 @@ __extends(BSTNode, _super); | ||
| if (cur !== null && newNode !== null) { | ||
| if (this._compare(cur.id, id) === CP.eq) { | ||
| if (this._compare(cur.id, id) === types_1.CP.eq) { | ||
| if (newNode) { | ||
@@ -110,3 +105,3 @@ cur.count += newNode.count; | ||
| } | ||
| else if (this._compare(cur.id, id) === CP.gt) { | ||
| else if (this._compare(cur.id, id) === types_1.CP.gt) { | ||
| // Traverse left of the node | ||
@@ -116,3 +111,3 @@ if (cur.left === undefined) { | ||
| newNode.parent = cur; | ||
| newNode.familyPosition = binary_tree_1.FamilyPosition.left; | ||
| newNode.familyPosition = types_1.FamilyPosition.LEFT; | ||
| } | ||
@@ -132,3 +127,3 @@ //Add to the left of the current node | ||
| } | ||
| else if (this._compare(cur.id, id) === CP.lt) { | ||
| else if (this._compare(cur.id, id) === types_1.CP.lt) { | ||
| // Traverse right of the node | ||
@@ -138,3 +133,3 @@ if (cur.right === undefined) { | ||
| newNode.parent = cur; | ||
| newNode.familyPosition = binary_tree_1.FamilyPosition.right; | ||
| newNode.familyPosition = types_1.FamilyPosition.RIGHT; | ||
| } | ||
@@ -186,5 +181,5 @@ //Add to the right of the current node | ||
| var _a, _b, _c, _d, _e, _f; | ||
| if (this._compare(0, 1) === CP.lt) | ||
| if (this._compare(0, 1) === types_1.CP.lt) | ||
| return (_b = (_a = this.getRightMost()) === null || _a === void 0 ? void 0 : _a.id) !== null && _b !== void 0 ? _b : 0; | ||
| else if (this._compare(0, 1) === CP.gt) | ||
| else if (this._compare(0, 1) === types_1.CP.gt) | ||
| return (_d = (_c = this.getLeftMost()) === null || _c === void 0 ? void 0 : _c.id) !== null && _d !== void 0 ? _d : 0; | ||
@@ -225,6 +220,6 @@ else | ||
| switch (curr.familyPosition) { | ||
| case binary_tree_1.FamilyPosition.left: | ||
| case types_1.FamilyPosition.LEFT: | ||
| parent.left = curr.right; | ||
| break; | ||
| case binary_tree_1.FamilyPosition.right: | ||
| case types_1.FamilyPosition.RIGHT: | ||
| parent.right = curr.right; | ||
@@ -275,3 +270,3 @@ break; | ||
| var result = []; | ||
| if (this.loopType === binary_tree_1.LoopType.recursive) { | ||
| if (this.loopType === types_1.LoopType.RECURSIVE) { | ||
| var _traverse_1 = function (cur) { | ||
@@ -283,5 +278,5 @@ if (_this._pushByPropertyNameStopOrNot(cur, result, nodeProperty, propertyName, onlyOne)) | ||
| if (propertyName === 'id') { | ||
| if (_this._compare(cur.id, nodeProperty) === CP.gt) | ||
| if (_this._compare(cur.id, nodeProperty) === types_1.CP.gt) | ||
| cur.left && _traverse_1(cur.left); | ||
| if (_this._compare(cur.id, nodeProperty) === CP.lt) | ||
| if (_this._compare(cur.id, nodeProperty) === types_1.CP.lt) | ||
| cur.right && _traverse_1(cur.right); | ||
@@ -304,5 +299,5 @@ } | ||
| if (propertyName === 'id') { | ||
| if (this._compare(cur.id, nodeProperty) === CP.gt) | ||
| if (this._compare(cur.id, nodeProperty) === types_1.CP.gt) | ||
| cur.left && queue.push(cur.left); | ||
| if (this._compare(cur.id, nodeProperty) === CP.lt) | ||
| if (this._compare(cur.id, nodeProperty) === types_1.CP.lt) | ||
| cur.right && queue.push(cur.right); | ||
@@ -351,6 +346,6 @@ } | ||
| var sum = 0; | ||
| if (this.loopType === binary_tree_1.LoopType.recursive) { | ||
| if (this.loopType === types_1.LoopType.RECURSIVE) { | ||
| var _traverse_2 = function (cur) { | ||
| var compared = _this._compare(cur.id, id); | ||
| if (compared === CP.eq) { | ||
| if (compared === types_1.CP.eq) { | ||
| if (cur.right) | ||
@@ -360,3 +355,3 @@ sum += _this.subTreeSum(cur.right, propertyName); | ||
| } | ||
| else if (compared === CP.lt) { | ||
| else if (compared === types_1.CP.lt) { | ||
| if (cur.left) | ||
@@ -385,3 +380,3 @@ sum += _this.subTreeSum(cur.left, propertyName); | ||
| var compared = this._compare(cur.id, id); | ||
| if (compared === CP.eq) { | ||
| if (compared === types_1.CP.eq) { | ||
| if (cur.right) | ||
@@ -391,3 +386,3 @@ sum += this.subTreeSum(cur.right, propertyName); | ||
| } | ||
| else if (compared === CP.lt) { // todo maybe a bug | ||
| else if (compared === types_1.CP.lt) { // todo maybe a bug | ||
| if (cur.left) | ||
@@ -442,3 +437,3 @@ sum += this.subTreeSum(cur.left, propertyName); | ||
| }; | ||
| if (this.loopType === binary_tree_1.LoopType.recursive) { | ||
| if (this.loopType === types_1.LoopType.RECURSIVE) { | ||
| var _traverse_3 = function (cur) { | ||
@@ -449,5 +444,5 @@ var compared = _this._compare(cur.id, node.id); | ||
| return; | ||
| if (cur.left && compared === CP.gt) | ||
| if (cur.left && compared === types_1.CP.gt) | ||
| _traverse_3(cur.left); | ||
| else if (cur.right && compared === CP.gt) | ||
| else if (cur.right && compared === types_1.CP.gt) | ||
| _traverse_3(cur.right); | ||
@@ -465,5 +460,5 @@ }; | ||
| _sumByPropertyName(cur); | ||
| if (cur.left && compared === CP.gt) | ||
| if (cur.left && compared === types_1.CP.gt) | ||
| queue.push(cur.left); | ||
| else if (cur.right && compared === CP.gt) | ||
| else if (cur.right && compared === types_1.CP.gt) | ||
| queue.push(cur.right); | ||
@@ -486,3 +481,3 @@ } | ||
| return false; | ||
| if (this.loopType === binary_tree_1.LoopType.recursive) { | ||
| if (this.loopType === types_1.LoopType.RECURSIVE) { | ||
| var buildBalanceBST_1 = function (l, r) { | ||
@@ -528,3 +523,3 @@ if (l > r) | ||
| var balanced = true; | ||
| if (this.loopType === binary_tree_1.LoopType.recursive) { | ||
| if (this.loopType === types_1.LoopType.RECURSIVE) { | ||
| var _height_1 = function (cur) { | ||
@@ -581,7 +576,7 @@ if (!cur) | ||
| if (compared > 0) | ||
| return CP.gt; | ||
| return types_1.CP.gt; | ||
| else if (compared < 0) | ||
| return CP.lt; | ||
| return types_1.CP.lt; | ||
| else | ||
| return CP.eq; | ||
| return types_1.CP.eq; | ||
| }; | ||
@@ -588,0 +583,0 @@ return BST; |
@@ -0,1 +1,2 @@ | ||
| export * from './abstract-binary-tree'; | ||
| export * from './binary-tree'; | ||
@@ -2,0 +3,0 @@ export * from './bst'; |
@@ -17,2 +17,3 @@ "use strict"; | ||
| Object.defineProperty(exports, "__esModule", { value: true }); | ||
| __exportStar(require("./abstract-binary-tree"), exports); | ||
| __exportStar(require("./binary-tree"), exports); | ||
@@ -19,0 +20,0 @@ __exportStar(require("./bst"), exports); |
@@ -19,7 +19,3 @@ "use strict"; | ||
| var binary_tree_1 = require("./binary-tree"); | ||
| var RBColor; | ||
| (function (RBColor) { | ||
| RBColor[RBColor["Red"] = 0] = "Red"; | ||
| RBColor[RBColor["Black"] = 1] = "Black"; | ||
| })(RBColor || (RBColor = {})); | ||
| var types_1 = require("../types"); | ||
| var RBNode = /** @class */ (function (_super) { | ||
@@ -32,3 +28,3 @@ __extends(RBNode, _super); | ||
| var _this = _super.call(this, id, val, count) || this; | ||
| _this._color = RBColor.Red; | ||
| _this._color = types_1.RBColor.RED; | ||
| return _this; | ||
@@ -35,0 +31,0 @@ } |
@@ -9,5 +9,11 @@ /** | ||
| import { BST, BSTNode } from './bst'; | ||
| import type { BinaryTreeNodeId, TreeMultiSetDeletedResult } from '../types'; | ||
| import { IBinaryTree } from '../interfaces'; | ||
| import type { BinaryTreeNodeId, RecursiveTreeMultiSetNode, TreeMultiSetOptions } from '../types'; | ||
| import { IBinaryTree, IBinaryTreeNode } from '../interfaces'; | ||
| export declare class TreeMultiSetNode<T, FAMILY extends TreeMultiSetNode<T, FAMILY> = RecursiveTreeMultiSetNode<T>> extends BSTNode<T, FAMILY> implements IBinaryTreeNode<T, FAMILY> { | ||
| } | ||
| /** | ||
| * The only distinction between a TreeMultiSet and a BST lies in the ability of the former to store duplicate nodes through the utilization of counters. | ||
| */ | ||
| export declare class TreeMultiSet<N extends BSTNode<N['val'], N> = BSTNode<number>> extends BST<N> implements IBinaryTree<N> { | ||
| constructor(options?: TreeMultiSetOptions); | ||
| /** | ||
@@ -23,23 +29,2 @@ * The function creates a new BSTNode with the given id, value, and count. | ||
| _createNode(id: BinaryTreeNodeId, val: N['val'], count?: number): N; | ||
| /** | ||
| * The function overrides the add method of the BinarySearchTree class in TypeScript. | ||
| * @param {BinaryTreeNodeId} id - The `id` parameter is the identifier of the binary tree node that you want to add. | ||
| * @param {N | null} val - The `val` parameter represents the value that you want to add to the binary search tree. It | ||
| * can be of type `N` (the generic type) or `null`. | ||
| * @param {number} [count] - The `count` parameter is an optional parameter of type `number`. It represents the number | ||
| * of times the value should be added to the binary search tree. If not provided, the default value is `undefined`. | ||
| * @returns The `add` method is returning a `BSTNode<N>` object or `null`. | ||
| */ | ||
| add(id: BinaryTreeNodeId, val: N | null, count?: number): N | null; | ||
| /** | ||
| * The function overrides the remove method of the superclass and returns the result of calling the superclass's remove | ||
| * method. | ||
| * @param {BinaryTreeNodeId} id - The `id` parameter represents the identifier of the binary tree node that needs to be | ||
| * removed from the tree. | ||
| * @param {boolean} [isUpdateAllLeftSum] - The `isUpdateAllLeftSum` parameter is an optional boolean value that | ||
| * determines whether to update the left sum of all nodes in the tree after removing a node. If `isUpdateAllLeftSum` is | ||
| * set to `true`, the left sum of all nodes will be recalculated. If it | ||
| * @returns The method is returning an array of TreeMultiSetDeletedResult objects. | ||
| */ | ||
| remove(id: BinaryTreeNodeId, isUpdateAllLeftSum?: boolean): TreeMultiSetDeletedResult<N>[]; | ||
| } |
@@ -17,4 +17,15 @@ "use strict"; | ||
| })(); | ||
| var __assign = (this && this.__assign) || function () { | ||
| __assign = Object.assign || function(t) { | ||
| for (var s, i = 1, n = arguments.length; i < n; i++) { | ||
| s = arguments[i]; | ||
| for (var p in s) if (Object.prototype.hasOwnProperty.call(s, p)) | ||
| t[p] = s[p]; | ||
| } | ||
| return t; | ||
| }; | ||
| return __assign.apply(this, arguments); | ||
| }; | ||
| Object.defineProperty(exports, "__esModule", { value: true }); | ||
| exports.TreeMultiSet = void 0; | ||
| exports.TreeMultiSet = exports.TreeMultiSetNode = void 0; | ||
| /** | ||
@@ -28,6 +39,17 @@ * data-structure-typed | ||
| var bst_1 = require("./bst"); | ||
| var TreeMultiSetNode = /** @class */ (function (_super) { | ||
| __extends(TreeMultiSetNode, _super); | ||
| function TreeMultiSetNode() { | ||
| return _super !== null && _super.apply(this, arguments) || this; | ||
| } | ||
| return TreeMultiSetNode; | ||
| }(bst_1.BSTNode)); | ||
| exports.TreeMultiSetNode = TreeMultiSetNode; | ||
| /** | ||
| * The only distinction between a TreeMultiSet and a BST lies in the ability of the former to store duplicate nodes through the utilization of counters. | ||
| */ | ||
| var TreeMultiSet = /** @class */ (function (_super) { | ||
| __extends(TreeMultiSet, _super); | ||
| function TreeMultiSet() { | ||
| return _super !== null && _super.apply(this, arguments) || this; | ||
| function TreeMultiSet(options) { | ||
| return _super.call(this, __assign(__assign({}, options), { isDuplicatedVal: true })) || this; | ||
| } | ||
@@ -44,32 +66,7 @@ /** | ||
| TreeMultiSet.prototype._createNode = function (id, val, count) { | ||
| var node = new bst_1.BSTNode(id, val, count); | ||
| var node = new TreeMultiSetNode(id, val, count); | ||
| return node; | ||
| }; | ||
| /** | ||
| * The function overrides the add method of the BinarySearchTree class in TypeScript. | ||
| * @param {BinaryTreeNodeId} id - The `id` parameter is the identifier of the binary tree node that you want to add. | ||
| * @param {N | null} val - The `val` parameter represents the value that you want to add to the binary search tree. It | ||
| * can be of type `N` (the generic type) or `null`. | ||
| * @param {number} [count] - The `count` parameter is an optional parameter of type `number`. It represents the number | ||
| * of times the value should be added to the binary search tree. If not provided, the default value is `undefined`. | ||
| * @returns The `add` method is returning a `BSTNode<N>` object or `null`. | ||
| */ | ||
| TreeMultiSet.prototype.add = function (id, val, count) { | ||
| return _super.prototype.add.call(this, id, val, count); | ||
| }; | ||
| /** | ||
| * The function overrides the remove method of the superclass and returns the result of calling the superclass's remove | ||
| * method. | ||
| * @param {BinaryTreeNodeId} id - The `id` parameter represents the identifier of the binary tree node that needs to be | ||
| * removed from the tree. | ||
| * @param {boolean} [isUpdateAllLeftSum] - The `isUpdateAllLeftSum` parameter is an optional boolean value that | ||
| * determines whether to update the left sum of all nodes in the tree after removing a node. If `isUpdateAllLeftSum` is | ||
| * set to `true`, the left sum of all nodes will be recalculated. If it | ||
| * @returns The method is returning an array of TreeMultiSetDeletedResult objects. | ||
| */ | ||
| TreeMultiSet.prototype.remove = function (id, isUpdateAllLeftSum) { | ||
| return _super.prototype.remove.call(this, id, isUpdateAllLeftSum); | ||
| }; | ||
| return TreeMultiSet; | ||
| }(bst_1.BST)); | ||
| exports.TreeMultiSet = TreeMultiSet; |
@@ -35,6 +35,4 @@ import { AbstractEdge, AbstractGraph, AbstractVertex } from './abstract-graph'; | ||
| } | ||
| export declare class DirectedGraph<V extends DirectedVertex<any>, E extends DirectedEdge<any>> extends AbstractGraph<V, E> implements IDirectedGraph<V, E> { | ||
| private readonly _vertexConstructor; | ||
| private readonly _edgeConstructor; | ||
| constructor(vertexConstructor: new (id: VertexId, val?: V['val']) => V, edgeConstructor: new (src: VertexId, dest: VertexId, weight?: number, val?: E['val']) => E); | ||
| export declare class DirectedGraph<V extends DirectedVertex<any> = DirectedVertex, E extends DirectedEdge<any> = DirectedEdge> extends AbstractGraph<V, E> implements IDirectedGraph<V, E> { | ||
| constructor(); | ||
| private _outEdgeMap; | ||
@@ -41,0 +39,0 @@ get outEdgeMap(): Map<V, E[]>; |
@@ -125,8 +125,6 @@ "use strict"; | ||
| __extends(DirectedGraph, _super); | ||
| function DirectedGraph(vertexConstructor, edgeConstructor) { | ||
| function DirectedGraph() { | ||
| var _this = _super.call(this) || this; | ||
| _this._outEdgeMap = new Map(); | ||
| _this._inEdgeMap = new Map(); | ||
| _this._vertexConstructor = vertexConstructor; | ||
| _this._edgeConstructor = edgeConstructor; | ||
| return _this; | ||
@@ -155,3 +153,3 @@ } | ||
| DirectedGraph.prototype._createVertex = function (id, val) { | ||
| return new this._vertexConstructor(id, val); | ||
| return new DirectedVertex(id, val !== null && val !== void 0 ? val : id); | ||
| }; | ||
@@ -167,5 +165,3 @@ /** | ||
| DirectedGraph.prototype._createEdge = function (src, dest, weight, val) { | ||
| if (weight === undefined || weight === null) | ||
| weight = 1; | ||
| return new this._edgeConstructor(src, dest, weight, val); | ||
| return new DirectedEdge(src, dest, weight !== null && weight !== void 0 ? weight : 1, val); | ||
| }; | ||
@@ -172,0 +168,0 @@ /** |
@@ -29,6 +29,4 @@ import { AbstractEdge, AbstractGraph, AbstractVertex } from './abstract-graph'; | ||
| } | ||
| export declare class UndirectedGraph<V extends UndirectedVertex<any>, E extends UndirectedEdge<any>> extends AbstractGraph<V, E> { | ||
| private readonly _vertexConstructor; | ||
| private readonly _edgeConstructor; | ||
| constructor(vertexConstructor: new (id: VertexId, val?: V['val']) => V, edgeConstructor: new (src: VertexId, dest: VertexId, weight?: number, val?: E['val']) => E); | ||
| export declare class UndirectedGraph<V extends UndirectedVertex<any> = UndirectedVertex, E extends UndirectedEdge<any> = UndirectedEdge> extends AbstractGraph<V, E> { | ||
| constructor(); | ||
| protected _edges: Map<V, E[]>; | ||
@@ -44,10 +42,14 @@ get edges(): Map<V, E[]>; | ||
| /** | ||
| * In TypeScript, a subclass inherits the interface implementation of its parent class, without needing to implement the same interface again in the subclass. This behavior differs from Java's approach. In Java, if a parent class implements an interface, the subclass needs to explicitly implement the same interface, even if the parent class has already implemented it. | ||
| * This means that using abstract methods in the parent class cannot constrain the grandchild classes. Defining methods within an interface also cannot constrain the descendant classes. When inheriting from this class, developers need to be aware that this method needs to be overridden. | ||
| * @param src | ||
| * @param dest | ||
| * @param weight | ||
| * @param val | ||
| * The function _createEdge creates an undirected edge between two vertices with an optional weight and value. | ||
| * @param {VertexId} v1 - The parameter `v1` represents the first vertex of the edge. It is of type `VertexId`, which | ||
| * could be a unique identifier or label for the vertex. | ||
| * @param {VertexId} v2 - The parameter `v2` represents the second vertex of the edge. It is of type `VertexId`, which | ||
| * is typically a unique identifier for a vertex in a graph. | ||
| * @param {number} [weight] - The weight parameter is an optional number that represents the weight of the edge. If no | ||
| * weight is provided, the default value is 1. | ||
| * @param [val] - The `val` parameter is an optional value that can be assigned to the edge. It can be of any type and | ||
| * is used to store additional information or data associated with the edge. | ||
| * @returns an instance of the UndirectedEdge class, casted as type E. | ||
| */ | ||
| _createEdge(src: VertexId, dest: VertexId, weight?: number, val?: E['val']): E; | ||
| _createEdge(v1: VertexId, v2: VertexId, weight?: number, val?: E['val']): E; | ||
| /** | ||
@@ -54,0 +56,0 @@ * The function `getEdge` returns the first undirected edge that connects two given vertices, or null if no such edge |
@@ -111,6 +111,4 @@ "use strict"; | ||
| __extends(UndirectedGraph, _super); | ||
| function UndirectedGraph(vertexConstructor, edgeConstructor) { | ||
| function UndirectedGraph() { | ||
| var _this = _super.call(this) || this; | ||
| _this._vertexConstructor = vertexConstructor; | ||
| _this._edgeConstructor = edgeConstructor; | ||
| _this._edges = new Map(); | ||
@@ -133,16 +131,18 @@ return _this; | ||
| UndirectedGraph.prototype._createVertex = function (id, val) { | ||
| return new this._vertexConstructor(id, val); | ||
| return new UndirectedVertex(id, val !== null && val !== void 0 ? val : id); | ||
| }; | ||
| /** | ||
| * In TypeScript, a subclass inherits the interface implementation of its parent class, without needing to implement the same interface again in the subclass. This behavior differs from Java's approach. In Java, if a parent class implements an interface, the subclass needs to explicitly implement the same interface, even if the parent class has already implemented it. | ||
| * This means that using abstract methods in the parent class cannot constrain the grandchild classes. Defining methods within an interface also cannot constrain the descendant classes. When inheriting from this class, developers need to be aware that this method needs to be overridden. | ||
| * @param src | ||
| * @param dest | ||
| * @param weight | ||
| * @param val | ||
| * The function _createEdge creates an undirected edge between two vertices with an optional weight and value. | ||
| * @param {VertexId} v1 - The parameter `v1` represents the first vertex of the edge. It is of type `VertexId`, which | ||
| * could be a unique identifier or label for the vertex. | ||
| * @param {VertexId} v2 - The parameter `v2` represents the second vertex of the edge. It is of type `VertexId`, which | ||
| * is typically a unique identifier for a vertex in a graph. | ||
| * @param {number} [weight] - The weight parameter is an optional number that represents the weight of the edge. If no | ||
| * weight is provided, the default value is 1. | ||
| * @param [val] - The `val` parameter is an optional value that can be assigned to the edge. It can be of any type and | ||
| * is used to store additional information or data associated with the edge. | ||
| * @returns an instance of the UndirectedEdge class, casted as type E. | ||
| */ | ||
| UndirectedGraph.prototype._createEdge = function (src, dest, weight, val) { | ||
| if (weight === undefined || weight === null) | ||
| weight = 1; | ||
| return new this._edgeConstructor(src, dest, weight, val); | ||
| UndirectedGraph.prototype._createEdge = function (v1, v2, weight, val) { | ||
| return new UndirectedEdge(v1, v2, weight !== null && weight !== void 0 ? weight : 1, val); | ||
| }; | ||
@@ -149,0 +149,0 @@ /** |
@@ -1,3 +0,2 @@ | ||
| import { BinaryTreeNodeId } from '../types'; | ||
| import { FamilyPosition } from '../binary-tree'; | ||
| import { BinaryTreeNodeId, FamilyPosition } from '../types'; | ||
| export interface IBinaryTreeNode<T, FAMILY extends IBinaryTreeNode<T, FAMILY>> { | ||
@@ -4,0 +3,0 @@ _createNode(id: BinaryTreeNodeId, val: T | null, count?: number): FAMILY | null; |
| import { AVLTreeNode } from '../binary-tree'; | ||
| export type AVLTreeDeleted<N> = { | ||
| deleted: N | null; | ||
| needBalanced: N | null; | ||
| }; | ||
| import { BSTOptions } from './bst'; | ||
| export type RecursiveAVLTreeNode<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 AVLTreeOptions = BSTOptions & {}; |
| import { BinaryTreeNode } from '../binary-tree'; | ||
| export type BinaryTreeNodePropertyName = 'id' | 'val' | 'count'; | ||
| export type NodeOrPropertyName = 'node' | BinaryTreeNodePropertyName; | ||
| export type DFSOrderPattern = 'in' | 'pre' | 'post'; | ||
| export type BinaryTreeNodeId = number; | ||
| export type BinaryTreeDeleted<N> = { | ||
| deleted: N | null | undefined; | ||
| needBalanced: N | null; | ||
| }; | ||
| export type ResultByProperty<N extends BinaryTreeNode<N['val'], N>> = N['val'] | N | number | BinaryTreeNodeId; | ||
| export type ResultsByProperty<N extends BinaryTreeNode<N['val'], N>> = ResultByProperty<N>[]; | ||
| import { AbstractBinaryTreeOptions } from './abstract-binary-tree'; | ||
| export type RecursiveBinaryTreeNode<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 BinaryTreeOptions = AbstractBinaryTreeOptions & {}; |
| import { BSTNode } from '../binary-tree'; | ||
| import type { BinaryTreeNodeId } from './binary-tree'; | ||
| import type { BinaryTreeOptions } from './binary-tree'; | ||
| import { BinaryTreeNodeId } from './abstract-binary-tree'; | ||
| export type BSTComparator = (a: BinaryTreeNodeId, b: BinaryTreeNodeId) => number; | ||
| export type BSTDeletedResult<N extends BSTNode<N['val'], N>> = { | ||
| deleted: N | null; | ||
| needBalanced: N | null; | ||
| export type RecursiveBSTNode<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, BSTNode<T, BSTNode<T, any>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>; | ||
| export type BSTOptions = BinaryTreeOptions & { | ||
| comparator?: BSTComparator; | ||
| }; | ||
| export type RecursiveBSTNode<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, BSTNode<T, BSTNode<T, any>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>; | ||
| export declare enum CP { | ||
| lt = "lt", | ||
| eq = "eq", | ||
| gt = "gt" | ||
| } |
| "use strict"; | ||
| Object.defineProperty(exports, "__esModule", { value: true }); | ||
| exports.CP = void 0; | ||
| var CP; | ||
| (function (CP) { | ||
| CP["lt"] = "lt"; | ||
| CP["eq"] = "eq"; | ||
| CP["gt"] = "gt"; | ||
| })(CP || (exports.CP = CP = {})); |
@@ -7,2 +7,4 @@ export * from './binary-tree'; | ||
| export * from './abstract-graph'; | ||
| export * from './abstract-binary-tree'; | ||
| export * from './rb-tree'; | ||
| export * from './directed-graph'; | ||
@@ -14,1 +16,2 @@ export * from './priority-queue'; | ||
| export * from './navigator'; | ||
| export * from './helpers'; |
@@ -23,2 +23,4 @@ "use strict"; | ||
| __exportStar(require("./abstract-graph"), exports); | ||
| __exportStar(require("./abstract-binary-tree"), exports); | ||
| __exportStar(require("./rb-tree"), exports); | ||
| __exportStar(require("./directed-graph"), exports); | ||
@@ -30,1 +32,2 @@ __exportStar(require("./priority-queue"), exports); | ||
| __exportStar(require("./navigator"), exports); | ||
| __exportStar(require("./helpers"), exports); |
@@ -1,4 +0,6 @@ | ||
| export type TreeMultiSetDeletedResult<N> = { | ||
| deleted: N | null; | ||
| needBalanced: N | null; | ||
| import { BSTOptions } from './bst'; | ||
| import { TreeMultiSetNode } from '../binary-tree'; | ||
| export type RecursiveTreeMultiSetNode<T> = TreeMultiSetNode<T, TreeMultiSetNode<T, TreeMultiSetNode<T, TreeMultiSetNode<T, TreeMultiSetNode<T, TreeMultiSetNode<T, TreeMultiSetNode<T, TreeMultiSetNode<T, TreeMultiSetNode<T, TreeMultiSetNode<T, TreeMultiSetNode<T, TreeMultiSetNode<T, TreeMultiSetNode<T, TreeMultiSetNode<T, TreeMultiSetNode<T, TreeMultiSetNode<T, TreeMultiSetNode<T, TreeMultiSetNode<T, TreeMultiSetNode<T, TreeMultiSetNode<T, TreeMultiSetNode<T, TreeMultiSetNode<T, TreeMultiSetNode<T, TreeMultiSetNode<T, TreeMultiSetNode<T, TreeMultiSetNode<T, TreeMultiSetNode<T, TreeMultiSetNode<T, TreeMultiSetNode<T, TreeMultiSetNode<T, TreeMultiSetNode<T, TreeMultiSetNode<T, TreeMultiSetNode<T, TreeMultiSetNode<T, TreeMultiSetNode<T, TreeMultiSetNode<T, TreeMultiSetNode<T, TreeMultiSetNode<T, TreeMultiSetNode<T, TreeMultiSetNode<T, TreeMultiSetNode<T, TreeMultiSetNode<T, TreeMultiSetNode<T, TreeMultiSetNode<T, TreeMultiSetNode<T, TreeMultiSetNode<T, TreeMultiSetNode<T, TreeMultiSetNode<T, TreeMultiSetNode<T, TreeMultiSetNode<T, any>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>; | ||
| export type TreeMultiSetOptions = Omit<BSTOptions, 'isDuplicatedVal'> & { | ||
| isDuplicatedVal: true; | ||
| }; |
| { | ||
| "name": "data-structure-typed", | ||
| "version": "1.18.5", | ||
| "version": "1.18.6", | ||
| "description": "Explore our comprehensive Javascript Data Structure / TypeScript Data Structure Library, meticulously crafted to empower developers with a versatile set of essential data structures. Our library includes a wide range of data structures, such as Binary Tree, AVL Tree, Binary Search Tree (BST), Tree Multiset, Segment Tree, Binary Indexed Tree, Graph, Directed Graph, Undirected Graph, Singly Linked List, Hash, CoordinateSet, CoordinateMap, Heap, Doubly Linked List, Priority Queue, Max Priority Queue, Min Priority Queue, Queue, ObjectDeque, ArrayDeque, Stack, and Trie. Each data structure is thoughtfully designed and implemented using TypeScript to provide efficient, reliable, and easy-to-use solutions for your programming needs. Whether you're optimizing algorithms, managing data, or enhancing performance, our TypeScript Data Structure Library is your go-to resource. Elevate your coding experience with these fundamental building blocks for software development.", | ||
@@ -5,0 +5,0 @@ "main": "dist/index.js", |
Sorry, the diff of this file is too big to display
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
New alerts
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
Fixed alerts
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
Improved metrics
- Total package byte prevSize
- increased by3.57%
23522497
- Number of package files
- increased by5.11%
391
- Lines of code
- increased by0.5%
21707
No dependency changes