Socket
Socket
Sign inDemoInstall

data-structure-typed

Package Overview
Dependencies
Maintainers
1
Versions
201
Alerts
File Explorer

Advanced tools

License
Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

data-structure-typed - npm Package Compare versions

Comparing version 1.48.8 to 1.48.9

481

benchmark/report.json
{
"avl-tree": {
"benchmarks": [
{
"test name": "10,000 add randomly",
"time taken (ms)": "51.22",
"executions per sec": "19.52",
"sample deviation": "0.00"
},
{
"test name": "10,000 add & delete randomly",
"time taken (ms)": "110.40",
"executions per sec": "9.06",
"sample deviation": "0.00"
},
{
"test name": "10,000 addMany",
"time taken (ms)": "58.39",
"executions per sec": "17.13",
"sample deviation": "6.35e-4"
},
{
"test name": "10,000 get",
"time taken (ms)": "50.59",
"executions per sec": "19.77",
"sample deviation": "3.87e-4"
}
],
"testName": "avl-tree"
},
"binary-tree": {

@@ -35,46 +6,46 @@ "benchmarks": [

"test name": "1,000 add randomly",
"time taken (ms)": "13.83",
"executions per sec": "72.29",
"sample deviation": "1.19e-4"
"time taken (ms)": "17.61",
"executions per sec": "56.79",
"sample deviation": "4.75e-4"
},
{
"test name": "1,000 add & delete randomly",
"time taken (ms)": "21.49",
"executions per sec": "46.54",
"sample deviation": "2.34e-4"
"time taken (ms)": "23.21",
"executions per sec": "43.08",
"sample deviation": "0.00"
},
{
"test name": "1,000 addMany",
"time taken (ms)": "15.93",
"executions per sec": "62.78",
"sample deviation": "1.27e-4"
"time taken (ms)": "17.89",
"executions per sec": "55.90",
"sample deviation": "0.00"
},
{
"test name": "1,000 get",
"time taken (ms)": "18.19",
"executions per sec": "54.98",
"sample deviation": "1.79e-4"
"time taken (ms)": "17.71",
"executions per sec": "56.47",
"sample deviation": "0.00"
},
{
"test name": "1,000 has",
"time taken (ms)": "18.20",
"executions per sec": "54.93",
"sample deviation": "1.71e-4"
"time taken (ms)": "17.15",
"executions per sec": "58.30",
"sample deviation": "2.88e-4"
},
{
"test name": "1,000 dfs",
"time taken (ms)": "161.79",
"executions per sec": "6.18",
"sample deviation": "7.45e-4"
"time taken (ms)": "161.44",
"executions per sec": "6.19",
"sample deviation": "0.00"
},
{
"test name": "1,000 bfs",
"time taken (ms)": "56.68",
"executions per sec": "17.64",
"sample deviation": "4.77e-4"
"time taken (ms)": "57.53",
"executions per sec": "17.38",
"sample deviation": "0.00"
},
{
"test name": "1,000 morris",
"time taken (ms)": "262.64",
"executions per sec": "3.81",
"time taken (ms)": "258.22",
"executions per sec": "3.87",
"sample deviation": "0.00"

@@ -84,409 +55,3 @@ }

"testName": "binary-tree"
},
"bst": {
"benchmarks": [
{
"test name": "10,000 add randomly",
"time taken (ms)": "51.51",
"executions per sec": "19.41",
"sample deviation": "8.70e-4"
},
{
"test name": "10,000 add & delete randomly",
"time taken (ms)": "114.09",
"executions per sec": "8.76",
"sample deviation": "9.66e-4"
},
{
"test name": "10,000 addMany",
"time taken (ms)": "47.86",
"executions per sec": "20.90",
"sample deviation": "2.77e-4"
},
{
"test name": "10,000 get",
"time taken (ms)": "51.93",
"executions per sec": "19.26",
"sample deviation": "6.56e-4"
}
],
"testName": "bst"
},
"rb-tree": {
"benchmarks": [
{
"test name": "100,000 add",
"time taken (ms)": "86.63",
"executions per sec": "11.54",
"sample deviation": "0.00"
},
{
"test name": "100,000 add & delete randomly",
"time taken (ms)": "218.88",
"executions per sec": "4.57",
"sample deviation": "0.01"
},
{
"test name": "100,000 getNode",
"time taken (ms)": "261.16",
"executions per sec": "3.83",
"sample deviation": "0.00"
},
{
"test name": "100,000 add & iterator",
"time taken (ms)": "117.64",
"executions per sec": "8.50",
"sample deviation": "0.00"
}
],
"testName": "rb-tree"
},
"comparison": {
"benchmarks": [
{
"test name": "SRC PQ 10,000 add",
"time taken (ms)": "0.14",
"executions per sec": "6949.20",
"sample deviation": "1.53e-6"
},
{
"test name": "CJS PQ 10,000 add",
"time taken (ms)": "0.14",
"executions per sec": "6943.68",
"sample deviation": "1.74e-6"
},
{
"test name": "MJS PQ 10,000 add",
"time taken (ms)": "0.57",
"executions per sec": "1758.40",
"sample deviation": "6.26e-6"
},
{
"test name": "SRC PQ 10,000 add & pop",
"time taken (ms)": "3.40",
"executions per sec": "293.94",
"sample deviation": "3.50e-5"
},
{
"test name": "CJS PQ 10,000 add & pop",
"time taken (ms)": "3.42",
"executions per sec": "292.69",
"sample deviation": "5.34e-5"
},
{
"test name": "MJS PQ 10,000 add & pop",
"time taken (ms)": "3.30",
"executions per sec": "303.01",
"sample deviation": "3.97e-5"
}
],
"testName": "comparison"
},
"directed-graph": {
"benchmarks": [
{
"test name": "1,000 addVertex",
"time taken (ms)": "0.10",
"executions per sec": "9930.74",
"sample deviation": "1.11e-6"
},
{
"test name": "1,000 addEdge",
"time taken (ms)": "6.13",
"executions per sec": "163.19",
"sample deviation": "1.84e-4"
},
{
"test name": "1,000 getVertex",
"time taken (ms)": "0.05",
"executions per sec": "2.15e+4",
"sample deviation": "5.00e-7"
},
{
"test name": "1,000 getEdge",
"time taken (ms)": "23.57",
"executions per sec": "42.43",
"sample deviation": "0.00"
},
{
"test name": "tarjan",
"time taken (ms)": "252.05",
"executions per sec": "3.97",
"sample deviation": "0.03"
},
{
"test name": "tarjan all",
"time taken (ms)": "221.15",
"executions per sec": "4.52",
"sample deviation": "0.00"
},
{
"test name": "topologicalSort",
"time taken (ms)": "181.07",
"executions per sec": "5.52",
"sample deviation": "0.00"
}
],
"testName": "directed-graph"
},
"hash-map": {
"benchmarks": [
{
"test name": "1,000,000 set",
"time taken (ms)": "122.90",
"executions per sec": "8.14",
"sample deviation": "0.04"
},
{
"test name": "Native Map 1,000,000 set",
"time taken (ms)": "215.97",
"executions per sec": "4.63",
"sample deviation": "0.02"
},
{
"test name": "Native Set 1,000,000 add",
"time taken (ms)": "179.11",
"executions per sec": "5.58",
"sample deviation": "0.02"
},
{
"test name": "1,000,000 set & get",
"time taken (ms)": "123.10",
"executions per sec": "8.12",
"sample deviation": "0.04"
},
{
"test name": "Native Map 1,000,000 set & get",
"time taken (ms)": "271.80",
"executions per sec": "3.68",
"sample deviation": "0.02"
},
{
"test name": "Native Set 1,000,000 add & has",
"time taken (ms)": "176.65",
"executions per sec": "5.66",
"sample deviation": "0.02"
},
{
"test name": "1,000,000 ObjKey set & get",
"time taken (ms)": "341.97",
"executions per sec": "2.92",
"sample deviation": "0.07"
},
{
"test name": "Native Map 1,000,000 ObjKey set & get",
"time taken (ms)": "316.86",
"executions per sec": "3.16",
"sample deviation": "0.04"
},
{
"test name": "Native Set 1,000,000 ObjKey add & has",
"time taken (ms)": "285.14",
"executions per sec": "3.51",
"sample deviation": "0.06"
}
],
"testName": "hash-map"
},
"heap": {
"benchmarks": [
{
"test name": "100,000 add & pop",
"time taken (ms)": "80.37",
"executions per sec": "12.44",
"sample deviation": "0.00"
},
{
"test name": "100,000 add & dfs",
"time taken (ms)": "36.20",
"executions per sec": "27.63",
"sample deviation": "0.00"
},
{
"test name": "10,000 fib add & pop",
"time taken (ms)": "362.24",
"executions per sec": "2.76",
"sample deviation": "0.00"
}
],
"testName": "heap"
},
"doubly-linked-list": {
"benchmarks": [
{
"test name": "1,000,000 push",
"time taken (ms)": "216.09",
"executions per sec": "4.63",
"sample deviation": "0.06"
},
{
"test name": "1,000,000 unshift",
"time taken (ms)": "220.68",
"executions per sec": "4.53",
"sample deviation": "0.02"
},
{
"test name": "1,000,000 unshift & shift",
"time taken (ms)": "172.93",
"executions per sec": "5.78",
"sample deviation": "0.04"
},
{
"test name": "1,000,000 insertBefore",
"time taken (ms)": "332.25",
"executions per sec": "3.01",
"sample deviation": "0.08"
}
],
"testName": "doubly-linked-list"
},
"singly-linked-list": {
"benchmarks": [
{
"test name": "1,000,000 push & shift",
"time taken (ms)": "222.99",
"executions per sec": "4.48",
"sample deviation": "0.10"
},
{
"test name": "10,000 push & pop",
"time taken (ms)": "214.82",
"executions per sec": "4.66",
"sample deviation": "0.01"
},
{
"test name": "10,000 insertBefore",
"time taken (ms)": "251.24",
"executions per sec": "3.98",
"sample deviation": "0.01"
}
],
"testName": "singly-linked-list"
},
"max-priority-queue": {
"benchmarks": [
{
"test name": "10,000 refill & poll",
"time taken (ms)": "8.91",
"executions per sec": "112.19",
"sample deviation": "1.57e-4"
}
],
"testName": "max-priority-queue"
},
"priority-queue": {
"benchmarks": [
{
"test name": "100,000 add & pop",
"time taken (ms)": "101.70",
"executions per sec": "9.83",
"sample deviation": "0.00"
}
],
"testName": "priority-queue"
},
"deque": {
"benchmarks": [
{
"test name": "1,000,000 push",
"time taken (ms)": "13.80",
"executions per sec": "72.47",
"sample deviation": "1.56e-4"
},
{
"test name": "1,000,000 push & pop",
"time taken (ms)": "22.72",
"executions per sec": "44.02",
"sample deviation": "2.02e-4"
},
{
"test name": "100,000 push & shift",
"time taken (ms)": "2.35",
"executions per sec": "425.67",
"sample deviation": "5.80e-5"
},
{
"test name": "Native Array 100,000 push & shift",
"time taken (ms)": "2511.14",
"executions per sec": "0.40",
"sample deviation": "0.36"
},
{
"test name": "100,000 unshift & shift",
"time taken (ms)": "2.23",
"executions per sec": "447.89",
"sample deviation": "3.30e-4"
},
{
"test name": "Native Array 100,000 unshift & shift",
"time taken (ms)": "4140.23",
"executions per sec": "0.24",
"sample deviation": "0.33"
}
],
"testName": "deque"
},
"queue": {
"benchmarks": [
{
"test name": "1,000,000 push",
"time taken (ms)": "43.65",
"executions per sec": "22.91",
"sample deviation": "0.01"
},
{
"test name": "100,000 push & shift",
"time taken (ms)": "4.99",
"executions per sec": "200.28",
"sample deviation": "9.54e-5"
},
{
"test name": "Native Array 100,000 push & shift",
"time taken (ms)": "2335.63",
"executions per sec": "0.43",
"sample deviation": "0.33"
},
{
"test name": "Native Array 100,000 push & pop",
"time taken (ms)": "4.39",
"executions per sec": "227.81",
"sample deviation": "0.00"
}
],
"testName": "queue"
},
"stack": {
"benchmarks": [
{
"test name": "1,000,000 push",
"time taken (ms)": "45.38",
"executions per sec": "22.04",
"sample deviation": "0.01"
},
{
"test name": "1,000,000 push & pop",
"time taken (ms)": "49.52",
"executions per sec": "20.19",
"sample deviation": "0.01"
}
],
"testName": "stack"
},
"trie": {
"benchmarks": [
{
"test name": "100,000 push",
"time taken (ms)": "42.99",
"executions per sec": "23.26",
"sample deviation": "0.00"
},
{
"test name": "100,000 getWords",
"time taken (ms)": "89.78",
"executions per sec": "11.14",
"sample deviation": "0.00"
}
],
"testName": "trie"
}
}

2

CHANGELOG.md

@@ -11,3 +11,3 @@ # Changelog

## [v1.48.8](https://github.com/zrwusa/data-structure-typed/compare/v1.35.0...main) (upcoming)
## [v1.48.9](https://github.com/zrwusa/data-structure-typed/compare/v1.35.0...main) (upcoming)

@@ -14,0 +14,0 @@ ### Changes

4

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

@@ -40,6 +40,2 @@ /**

* 5. Leaf Nodes: Nodes without children are leaves.
* 6. Internal Nodes: Nodes with at least one child are internal.
* 7. Balanced Trees: The heights of the left and right subtrees of any node differ by no more than one.
* 8. Full Trees: Every node has either 0 or 2 children.
* 9. Complete Trees: All levels are fully filled except possibly the last, filled from left to right.
*/

@@ -46,0 +42,0 @@ export declare class BinaryTree<K = any, V = any, N extends BinaryTreeNode<K, V, N> = BinaryTreeNode<K, V, BinaryTreeNodeNested<K, V>>, TREE extends BinaryTree<K, V, N, TREE> = BinaryTree<K, V, N, BinaryTreeNested<K, V, N>>> extends IterableEntryBase<K, V | undefined> implements IBinaryTree<K, V, N, TREE> {

110

dist/cjs/data-structures/queue/deque.d.ts

@@ -442,111 +442,1 @@ /**

}
export declare class ObjectDeque<E = number> {
constructor(capacity?: number);
protected _nodes: {
[key: number]: E;
};
get nodes(): {
[p: number]: E;
};
protected _capacity: number;
get capacity(): number;
protected _first: number;
get first(): number;
protected _last: number;
get last(): number;
protected _size: number;
get size(): number;
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*
* The "addFirst" function adds an element to the beginning of an array-like data structure.
* @param {E} element - The `element` parameter represents the element that you want to add to the beginning of the data
* structure.
*/
addFirst(element: E): void;
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*
* The addLast function adds an element to the end of an array-like data structure.
* @param {E} element - The `element` parameter represents the element that you want to add to the end of the data structure.
*/
addLast(element: E): void;
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*
* The function `pollFirst()` removes and returns the first element in a data structure.
* @returns The element of the first element in the data structure.
*/
pollFirst(): E | undefined;
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*
* The `getFirst` function returns the first element in an array-like data structure if it exists.
* @returns The element at the first position of the `_nodes` array.
*/
getFirst(): E | undefined;
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*
* The `pollLast()` function removes and returns the last element in a data structure.
* @returns The element that was removed from the data structure.
*/
pollLast(): E | undefined;
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*
* The `getLast()` function returns the last element in an array-like data structure.
* @returns The last element in the array "_nodes" is being returned.
*/
getLast(): E | undefined;
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*
* The get function returns the element at the specified index in an array-like data structure.
* @param {number} index - The index parameter is a number that represents the position of the element you want to
* retrieve from the array.
* @returns The element at the specified index in the `_nodes` array is being returned. If there is no element at that
* index, `undefined` is returned.
*/
get(index: number): NonNullable<E> | undefined;
/**
* The function checks if the size of a data structure is less than or equal to zero.
* @returns The method is returning a boolean element indicating whether the size of the object is less than or equal to 0.
*/
isEmpty(): boolean;
}

173

dist/cjs/data-structures/queue/deque.js

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

Object.defineProperty(exports, "__esModule", { value: true });
exports.ObjectDeque = exports.Deque = void 0;
exports.Deque = void 0;
const utils_1 = require("../../utils");

@@ -796,173 +796,2 @@ const base_1 = require("../base");

exports.Deque = Deque;
// O(1) time complexity of obtaining the element
// O(n) time complexity of adding at the beginning and the end
// todo tested slowest one
class ObjectDeque {
constructor(capacity) {
this._nodes = {};
this._capacity = Number.MAX_SAFE_INTEGER;
this._first = -1;
this._last = -1;
this._size = 0;
if (capacity !== undefined)
this._capacity = capacity;
}
get nodes() {
return this._nodes;
}
get capacity() {
return this._capacity;
}
get first() {
return this._first;
}
get last() {
return this._last;
}
get size() {
return this._size;
}
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*
* The "addFirst" function adds an element to the beginning of an array-like data structure.
* @param {E} element - The `element` parameter represents the element that you want to add to the beginning of the data
* structure.
*/
addFirst(element) {
if (this.size === 0) {
const mid = Math.floor(this.capacity / 2);
this._first = mid;
this._last = mid;
}
else {
this._first--;
}
this.nodes[this.first] = element;
this._size++;
}
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*
* The addLast function adds an element to the end of an array-like data structure.
* @param {E} element - The `element` parameter represents the element that you want to add to the end of the data structure.
*/
addLast(element) {
if (this.size === 0) {
const mid = Math.floor(this.capacity / 2);
this._first = mid;
this._last = mid;
}
else {
this._last++;
}
this.nodes[this.last] = element;
this._size++;
}
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*
* The function `pollFirst()` removes and returns the first element in a data structure.
* @returns The element of the first element in the data structure.
*/
pollFirst() {
if (!this.size)
return;
const element = this.getFirst();
delete this.nodes[this.first];
this._first++;
this._size--;
return element;
}
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*
* The `getFirst` function returns the first element in an array-like data structure if it exists.
* @returns The element at the first position of the `_nodes` array.
*/
getFirst() {
if (this.size)
return this.nodes[this.first];
}
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*
* The `pollLast()` function removes and returns the last element in a data structure.
* @returns The element that was removed from the data structure.
*/
pollLast() {
if (!this.size)
return;
const element = this.getLast();
delete this.nodes[this.last];
this._last--;
this._size--;
return element;
}
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*
* The `getLast()` function returns the last element in an array-like data structure.
* @returns The last element in the array "_nodes" is being returned.
*/
getLast() {
if (this.size)
return this.nodes[this.last];
}
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*
* The get function returns the element at the specified index in an array-like data structure.
* @param {number} index - The index parameter is a number that represents the position of the element you want to
* retrieve from the array.
* @returns The element at the specified index in the `_nodes` array is being returned. If there is no element at that
* index, `undefined` is returned.
*/
get(index) {
return this.nodes[this.first + index] || undefined;
}
/**
* The function checks if the size of a data structure is less than or equal to zero.
* @returns The method is returning a boolean element indicating whether the size of the object is less than or equal to 0.
*/
isEmpty() {
return this.size <= 0;
}
}
exports.ObjectDeque = ObjectDeque;
//# sourceMappingURL=deque.js.map

4

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

@@ -40,6 +40,2 @@ /**

* 5. Leaf Nodes: Nodes without children are leaves.
* 6. Internal Nodes: Nodes with at least one child are internal.
* 7. Balanced Trees: The heights of the left and right subtrees of any node differ by no more than one.
* 8. Full Trees: Every node has either 0 or 2 children.
* 9. Complete Trees: All levels are fully filled except possibly the last, filled from left to right.
*/

@@ -46,0 +42,0 @@ export declare class BinaryTree<K = any, V = any, N extends BinaryTreeNode<K, V, N> = BinaryTreeNode<K, V, BinaryTreeNodeNested<K, V>>, TREE extends BinaryTree<K, V, N, TREE> = BinaryTree<K, V, N, BinaryTreeNested<K, V, N>>> extends IterableEntryBase<K, V | undefined> implements IBinaryTree<K, V, N, TREE> {

110

dist/mjs/data-structures/queue/deque.d.ts

@@ -442,111 +442,1 @@ /**

}
export declare class ObjectDeque<E = number> {
constructor(capacity?: number);
protected _nodes: {
[key: number]: E;
};
get nodes(): {
[p: number]: E;
};
protected _capacity: number;
get capacity(): number;
protected _first: number;
get first(): number;
protected _last: number;
get last(): number;
protected _size: number;
get size(): number;
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*
* The "addFirst" function adds an element to the beginning of an array-like data structure.
* @param {E} element - The `element` parameter represents the element that you want to add to the beginning of the data
* structure.
*/
addFirst(element: E): void;
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*
* The addLast function adds an element to the end of an array-like data structure.
* @param {E} element - The `element` parameter represents the element that you want to add to the end of the data structure.
*/
addLast(element: E): void;
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*
* The function `pollFirst()` removes and returns the first element in a data structure.
* @returns The element of the first element in the data structure.
*/
pollFirst(): E | undefined;
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*
* The `getFirst` function returns the first element in an array-like data structure if it exists.
* @returns The element at the first position of the `_nodes` array.
*/
getFirst(): E | undefined;
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*
* The `pollLast()` function removes and returns the last element in a data structure.
* @returns The element that was removed from the data structure.
*/
pollLast(): E | undefined;
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*
* The `getLast()` function returns the last element in an array-like data structure.
* @returns The last element in the array "_nodes" is being returned.
*/
getLast(): E | undefined;
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*
* The get function returns the element at the specified index in an array-like data structure.
* @param {number} index - The index parameter is a number that represents the position of the element you want to
* retrieve from the array.
* @returns The element at the specified index in the `_nodes` array is being returned. If there is no element at that
* index, `undefined` is returned.
*/
get(index: number): NonNullable<E> | undefined;
/**
* The function checks if the size of a data structure is less than or equal to zero.
* @returns The method is returning a boolean element indicating whether the size of the object is less than or equal to 0.
*/
isEmpty(): boolean;
}

170

dist/mjs/data-structures/queue/deque.js

@@ -792,171 +792,1 @@ /**

}
// O(1) time complexity of obtaining the element
// O(n) time complexity of adding at the beginning and the end
// todo tested slowest one
export class ObjectDeque {
constructor(capacity) {
if (capacity !== undefined)
this._capacity = capacity;
}
_nodes = {};
get nodes() {
return this._nodes;
}
_capacity = Number.MAX_SAFE_INTEGER;
get capacity() {
return this._capacity;
}
_first = -1;
get first() {
return this._first;
}
_last = -1;
get last() {
return this._last;
}
_size = 0;
get size() {
return this._size;
}
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*
* The "addFirst" function adds an element to the beginning of an array-like data structure.
* @param {E} element - The `element` parameter represents the element that you want to add to the beginning of the data
* structure.
*/
addFirst(element) {
if (this.size === 0) {
const mid = Math.floor(this.capacity / 2);
this._first = mid;
this._last = mid;
}
else {
this._first--;
}
this.nodes[this.first] = element;
this._size++;
}
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*
* The addLast function adds an element to the end of an array-like data structure.
* @param {E} element - The `element` parameter represents the element that you want to add to the end of the data structure.
*/
addLast(element) {
if (this.size === 0) {
const mid = Math.floor(this.capacity / 2);
this._first = mid;
this._last = mid;
}
else {
this._last++;
}
this.nodes[this.last] = element;
this._size++;
}
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*
* The function `pollFirst()` removes and returns the first element in a data structure.
* @returns The element of the first element in the data structure.
*/
pollFirst() {
if (!this.size)
return;
const element = this.getFirst();
delete this.nodes[this.first];
this._first++;
this._size--;
return element;
}
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*
* The `getFirst` function returns the first element in an array-like data structure if it exists.
* @returns The element at the first position of the `_nodes` array.
*/
getFirst() {
if (this.size)
return this.nodes[this.first];
}
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*
* The `pollLast()` function removes and returns the last element in a data structure.
* @returns The element that was removed from the data structure.
*/
pollLast() {
if (!this.size)
return;
const element = this.getLast();
delete this.nodes[this.last];
this._last--;
this._size--;
return element;
}
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*
* The `getLast()` function returns the last element in an array-like data structure.
* @returns The last element in the array "_nodes" is being returned.
*/
getLast() {
if (this.size)
return this.nodes[this.last];
}
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*
* The get function returns the element at the specified index in an array-like data structure.
* @param {number} index - The index parameter is a number that represents the position of the element you want to
* retrieve from the array.
* @returns The element at the specified index in the `_nodes` array is being returned. If there is no element at that
* index, `undefined` is returned.
*/
get(index) {
return this.nodes[this.first + index] || undefined;
}
/**
* The function checks if the size of a data structure is less than or equal to zero.
* @returns The method is returning a boolean element indicating whether the size of the object is less than or equal to 0.
*/
isEmpty() {
return this.size <= 0;
}
}

2

package.json
{
"name": "data-structure-typed",
"version": "1.48.8",
"version": "1.48.9",
"description": "Data Structures of Javascript & TypeScript. Heap, Binary Tree, Red Black Tree, Linked List, Deque, Trie, HashMap, Directed Graph, Undirected Graph, Binary Search Tree(BST), AVL Tree, Priority Queue, Graph, Queue, Tree Multiset, Singly Linked List, Doubly Linked List, Max Heap, Max Priority Queue, Min Heap, Min Priority Queue, Stack. Benchmark compared with C++ STL. API aligned with ES6 and Java.util. Usability is comparable to Python",

@@ -5,0 +5,0 @@ "main": "dist/cjs/index.js",

114

README_zh-CN.md

@@ -7,2 +7,3 @@ # data-structure-typed

![GitHub top language](https://img.shields.io/github/languages/top/zrwusa/data-structure-typed)
![GITHUB Star](https://img.shields.io/github/stars/zrwusa/data-structure-typed)
![eslint](https://aleen42.github.io/badges/src/eslint.svg)

@@ -831,57 +832,2 @@ ![NPM](https://img.shields.io/npm/l/data-structure-typed)

## 基准测试
[//]: # (No deletion!!! Start of Replace Section)
<div class="json-to-html-collapse clearfix 0">
<div class='collapsible level0' ><span class='json-to-html-label'>avl-tree</span></div>
<div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>10,000 add randomly</td><td>72.48</td><td>13.80</td><td>0.03</td></tr><tr><td>10,000 add & delete randomly</td><td>144.14</td><td>6.94</td><td>0.03</td></tr><tr><td>10,000 addMany</td><td>69.71</td><td>14.35</td><td>0.02</td></tr><tr><td>10,000 get</td><td>54.21</td><td>18.45</td><td>0.01</td></tr></table></div>
</div><div class="json-to-html-collapse clearfix 0">
<div class='collapsible level0' ><span class='json-to-html-label'>binary-tree</span></div>
<div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>1,000 add randomly</td><td>15.84</td><td>63.14</td><td>0.00</td></tr><tr><td>1,000 add & delete randomly</td><td>24.62</td><td>40.62</td><td>0.00</td></tr><tr><td>1,000 addMany</td><td>17.85</td><td>56.01</td><td>0.00</td></tr><tr><td>1,000 get</td><td>20.83</td><td>48.00</td><td>0.00</td></tr><tr><td>1,000 has</td><td>20.78</td><td>48.13</td><td>0.00</td></tr><tr><td>1,000 dfs</td><td>186.06</td><td>5.37</td><td>0.02</td></tr><tr><td>1,000 bfs</td><td>66.58</td><td>15.02</td><td>0.02</td></tr><tr><td>1,000 morris</td><td>298.23</td><td>3.35</td><td>0.02</td></tr></table></div>
</div><div class="json-to-html-collapse clearfix 0">
<div class='collapsible level0' ><span class='json-to-html-label'>bst</span></div>
<div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>10,000 add randomly</td><td>55.04</td><td>18.17</td><td>0.01</td></tr><tr><td>10,000 add & delete randomly</td><td>129.85</td><td>7.70</td><td>0.01</td></tr><tr><td>10,000 addMany</td><td>50.40</td><td>19.84</td><td>0.01</td></tr><tr><td>10,000 get</td><td>63.39</td><td>15.78</td><td>0.01</td></tr></table></div>
</div><div class="json-to-html-collapse clearfix 0">
<div class='collapsible level0' ><span class='json-to-html-label'>rb-tree</span></div>
<div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>100,000 add</td><td>113.25</td><td>8.83</td><td>0.02</td></tr><tr><td>100,000 add & delete randomly</td><td>305.28</td><td>3.28</td><td>0.03</td></tr><tr><td>100,000 getNode</td><td>73.20</td><td>13.66</td><td>0.03</td></tr><tr><td>100,000 add & iterator</td><td>159.80</td><td>6.26</td><td>0.06</td></tr></table></div>
</div><div class="json-to-html-collapse clearfix 0">
<div class='collapsible level0' ><span class='json-to-html-label'>comparison</span></div>
<div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>SRC PQ 10,000 add</td><td>0.17</td><td>5872.02</td><td>4.08e-5</td></tr><tr><td>CJS PQ 10,000 add</td><td>0.20</td><td>4961.22</td><td>1.14e-4</td></tr><tr><td>MJS PQ 10,000 add</td><td>0.74</td><td>1351.47</td><td>2.98e-4</td></tr><tr><td>SRC PQ 10,000 add & pop</td><td>4.62</td><td>216.49</td><td>0.00</td></tr><tr><td>CJS PQ 10,000 add & pop</td><td>4.36</td><td>229.40</td><td>0.00</td></tr><tr><td>MJS PQ 10,000 add & pop</td><td>3.92</td><td>255.23</td><td>0.00</td></tr></table></div>
</div><div class="json-to-html-collapse clearfix 0">
<div class='collapsible level0' ><span class='json-to-html-label'>directed-graph</span></div>
<div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>1,000 addVertex</td><td>0.12</td><td>8557.70</td><td>2.46e-5</td></tr><tr><td>1,000 addEdge</td><td>7.37</td><td>135.70</td><td>0.00</td></tr><tr><td>1,000 getVertex</td><td>0.05</td><td>1.91e+4</td><td>1.12e-5</td></tr><tr><td>1,000 getEdge</td><td>22.75</td><td>43.96</td><td>0.00</td></tr><tr><td>tarjan</td><td>196.98</td><td>5.08</td><td>0.01</td></tr><tr><td>tarjan all</td><td>217.25</td><td>4.60</td><td>0.03</td></tr><tr><td>topologicalSort</td><td>177.30</td><td>5.64</td><td>0.02</td></tr></table></div>
</div><div class="json-to-html-collapse clearfix 0">
<div class='collapsible level0' ><span class='json-to-html-label'>hash-map</span></div>
<div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>1,000,000 set</td><td>153.74</td><td>6.50</td><td>0.07</td></tr><tr><td>1,000,000 Map set</td><td>330.02</td><td>3.03</td><td>0.16</td></tr><tr><td>1,000,000 Set add</td><td>258.64</td><td>3.87</td><td>0.06</td></tr><tr><td>1,000,000 set & get</td><td>138.80</td><td>7.20</td><td>0.06</td></tr><tr><td>1,000,000 Map set & get</td><td>352.63</td><td>2.84</td><td>0.05</td></tr><tr><td>1,000,000 Set add & has</td><td>217.97</td><td>4.59</td><td>0.02</td></tr><tr><td>1,000,000 ObjKey set & get</td><td>414.87</td><td>2.41</td><td>0.06</td></tr><tr><td>1,000,000 Map ObjKey set & get</td><td>389.17</td><td>2.57</td><td>0.07</td></tr><tr><td>1,000,000 Set ObjKey add & has</td><td>352.67</td><td>2.84</td><td>0.03</td></tr></table></div>
</div><div class="json-to-html-collapse clearfix 0">
<div class='collapsible level0' ><span class='json-to-html-label'>heap</span></div>
<div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>100,000 add & pop</td><td>90.67</td><td>11.03</td><td>0.02</td></tr><tr><td>100,000 add & dfs</td><td>40.30</td><td>24.81</td><td>0.01</td></tr><tr><td>10,000 fib add & pop</td><td>414.94</td><td>2.41</td><td>0.02</td></tr></table></div>
</div><div class="json-to-html-collapse clearfix 0">
<div class='collapsible level0' ><span class='json-to-html-label'>doubly-linked-list</span></div>
<div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>1,000,000 push</td><td>290.62</td><td>3.44</td><td>0.10</td></tr><tr><td>1,000,000 unshift</td><td>253.88</td><td>3.94</td><td>0.10</td></tr><tr><td>1,000,000 unshift & shift</td><td>259.65</td><td>3.85</td><td>0.14</td></tr><tr><td>1,000,000 insertBefore</td><td>463.16</td><td>2.16</td><td>0.10</td></tr></table></div>
</div><div class="json-to-html-collapse clearfix 0">
<div class='collapsible level0' ><span class='json-to-html-label'>singly-linked-list</span></div>
<div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>1,000,000 push & shift</td><td>250.27</td><td>4.00</td><td>0.08</td></tr><tr><td>10,000 push & pop</td><td>261.13</td><td>3.83</td><td>0.03</td></tr><tr><td>10,000 insertBefore</td><td>282.46</td><td>3.54</td><td>0.02</td></tr></table></div>
</div><div class="json-to-html-collapse clearfix 0">
<div class='collapsible level0' ><span class='json-to-html-label'>max-priority-queue</span></div>
<div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>10,000 refill & poll</td><td>10.49</td><td>95.29</td><td>0.00</td></tr></table></div>
</div><div class="json-to-html-collapse clearfix 0">
<div class='collapsible level0' ><span class='json-to-html-label'>priority-queue</span></div>
<div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>100,000 add & pop</td><td>110.63</td><td>9.04</td><td>0.01</td></tr></table></div>
</div><div class="json-to-html-collapse clearfix 0">
<div class='collapsible level0' ><span class='json-to-html-label'>deque</span></div>
<div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>1,000,000 push</td><td>15.89</td><td>62.92</td><td>0.00</td></tr><tr><td>1,000,000 push & pop</td><td>26.45</td><td>37.81</td><td>0.01</td></tr><tr><td>1,000,000 push & shift</td><td>27.52</td><td>36.34</td><td>0.00</td></tr><tr><td>1,000,000 unshift & shift</td><td>28.82</td><td>34.70</td><td>0.01</td></tr></table></div>
</div><div class="json-to-html-collapse clearfix 0">
<div class='collapsible level0' ><span class='json-to-html-label'>queue</span></div>
<div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>1,000,000 push</td><td>51.21</td><td>19.53</td><td>0.02</td></tr><tr><td>1,000,000 push & shift</td><td>105.56</td><td>9.47</td><td>0.05</td></tr></table></div>
</div><div class="json-to-html-collapse clearfix 0">
<div class='collapsible level0' ><span class='json-to-html-label'>stack</span></div>
<div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>1,000,000 push</td><td>43.57</td><td>22.95</td><td>0.01</td></tr><tr><td>1,000,000 push & pop</td><td>55.18</td><td>18.12</td><td>0.01</td></tr></table></div>
</div><div class="json-to-html-collapse clearfix 0">
<div class='collapsible level0' ><span class='json-to-html-label'>trie</span></div>
<div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>100,000 push</td><td>54.08</td><td>18.49</td><td>0.01</td></tr><tr><td>100,000 getWords</td><td>77.77</td><td>12.86</td><td>0.02</td></tr></table></div>
</div>
[//]: # (No deletion!!! End of Replace Section)
## 内建的经典算法

@@ -971,3 +917,2 @@

## 软件工程标准

@@ -1022,2 +967,59 @@

## 基准测试
[//]: # (No deletion!!! Start of Replace Section)
<div class="json-to-html-collapse clearfix 0">
<div class='collapsible level0' ><span class='json-to-html-label'>avl-tree</span></div>
<div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>10,000 add randomly</td><td>72.48</td><td>13.80</td><td>0.03</td></tr><tr><td>10,000 add & delete randomly</td><td>144.14</td><td>6.94</td><td>0.03</td></tr><tr><td>10,000 addMany</td><td>69.71</td><td>14.35</td><td>0.02</td></tr><tr><td>10,000 get</td><td>54.21</td><td>18.45</td><td>0.01</td></tr></table></div>
</div><div class="json-to-html-collapse clearfix 0">
<div class='collapsible level0' ><span class='json-to-html-label'>binary-tree</span></div>
<div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>1,000 add randomly</td><td>15.84</td><td>63.14</td><td>0.00</td></tr><tr><td>1,000 add & delete randomly</td><td>24.62</td><td>40.62</td><td>0.00</td></tr><tr><td>1,000 addMany</td><td>17.85</td><td>56.01</td><td>0.00</td></tr><tr><td>1,000 get</td><td>20.83</td><td>48.00</td><td>0.00</td></tr><tr><td>1,000 has</td><td>20.78</td><td>48.13</td><td>0.00</td></tr><tr><td>1,000 dfs</td><td>186.06</td><td>5.37</td><td>0.02</td></tr><tr><td>1,000 bfs</td><td>66.58</td><td>15.02</td><td>0.02</td></tr><tr><td>1,000 morris</td><td>298.23</td><td>3.35</td><td>0.02</td></tr></table></div>
</div><div class="json-to-html-collapse clearfix 0">
<div class='collapsible level0' ><span class='json-to-html-label'>bst</span></div>
<div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>10,000 add randomly</td><td>55.04</td><td>18.17</td><td>0.01</td></tr><tr><td>10,000 add & delete randomly</td><td>129.85</td><td>7.70</td><td>0.01</td></tr><tr><td>10,000 addMany</td><td>50.40</td><td>19.84</td><td>0.01</td></tr><tr><td>10,000 get</td><td>63.39</td><td>15.78</td><td>0.01</td></tr></table></div>
</div><div class="json-to-html-collapse clearfix 0">
<div class='collapsible level0' ><span class='json-to-html-label'>rb-tree</span></div>
<div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>100,000 add</td><td>113.25</td><td>8.83</td><td>0.02</td></tr><tr><td>100,000 add & delete randomly</td><td>305.28</td><td>3.28</td><td>0.03</td></tr><tr><td>100,000 getNode</td><td>73.20</td><td>13.66</td><td>0.03</td></tr><tr><td>100,000 add & iterator</td><td>159.80</td><td>6.26</td><td>0.06</td></tr></table></div>
</div><div class="json-to-html-collapse clearfix 0">
<div class='collapsible level0' ><span class='json-to-html-label'>comparison</span></div>
<div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>SRC PQ 10,000 add</td><td>0.17</td><td>5872.02</td><td>4.08e-5</td></tr><tr><td>CJS PQ 10,000 add</td><td>0.20</td><td>4961.22</td><td>1.14e-4</td></tr><tr><td>MJS PQ 10,000 add</td><td>0.74</td><td>1351.47</td><td>2.98e-4</td></tr><tr><td>SRC PQ 10,000 add & pop</td><td>4.62</td><td>216.49</td><td>0.00</td></tr><tr><td>CJS PQ 10,000 add & pop</td><td>4.36</td><td>229.40</td><td>0.00</td></tr><tr><td>MJS PQ 10,000 add & pop</td><td>3.92</td><td>255.23</td><td>0.00</td></tr></table></div>
</div><div class="json-to-html-collapse clearfix 0">
<div class='collapsible level0' ><span class='json-to-html-label'>directed-graph</span></div>
<div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>1,000 addVertex</td><td>0.12</td><td>8557.70</td><td>2.46e-5</td></tr><tr><td>1,000 addEdge</td><td>7.37</td><td>135.70</td><td>0.00</td></tr><tr><td>1,000 getVertex</td><td>0.05</td><td>1.91e+4</td><td>1.12e-5</td></tr><tr><td>1,000 getEdge</td><td>22.75</td><td>43.96</td><td>0.00</td></tr><tr><td>tarjan</td><td>196.98</td><td>5.08</td><td>0.01</td></tr><tr><td>tarjan all</td><td>217.25</td><td>4.60</td><td>0.03</td></tr><tr><td>topologicalSort</td><td>177.30</td><td>5.64</td><td>0.02</td></tr></table></div>
</div><div class="json-to-html-collapse clearfix 0">
<div class='collapsible level0' ><span class='json-to-html-label'>hash-map</span></div>
<div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>1,000,000 set</td><td>153.74</td><td>6.50</td><td>0.07</td></tr><tr><td>1,000,000 Map set</td><td>330.02</td><td>3.03</td><td>0.16</td></tr><tr><td>1,000,000 Set add</td><td>258.64</td><td>3.87</td><td>0.06</td></tr><tr><td>1,000,000 set & get</td><td>138.80</td><td>7.20</td><td>0.06</td></tr><tr><td>1,000,000 Map set & get</td><td>352.63</td><td>2.84</td><td>0.05</td></tr><tr><td>1,000,000 Set add & has</td><td>217.97</td><td>4.59</td><td>0.02</td></tr><tr><td>1,000,000 ObjKey set & get</td><td>414.87</td><td>2.41</td><td>0.06</td></tr><tr><td>1,000,000 Map ObjKey set & get</td><td>389.17</td><td>2.57</td><td>0.07</td></tr><tr><td>1,000,000 Set ObjKey add & has</td><td>352.67</td><td>2.84</td><td>0.03</td></tr></table></div>
</div><div class="json-to-html-collapse clearfix 0">
<div class='collapsible level0' ><span class='json-to-html-label'>heap</span></div>
<div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>100,000 add & pop</td><td>90.67</td><td>11.03</td><td>0.02</td></tr><tr><td>100,000 add & dfs</td><td>40.30</td><td>24.81</td><td>0.01</td></tr><tr><td>10,000 fib add & pop</td><td>414.94</td><td>2.41</td><td>0.02</td></tr></table></div>
</div><div class="json-to-html-collapse clearfix 0">
<div class='collapsible level0' ><span class='json-to-html-label'>doubly-linked-list</span></div>
<div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>1,000,000 push</td><td>290.62</td><td>3.44</td><td>0.10</td></tr><tr><td>1,000,000 unshift</td><td>253.88</td><td>3.94</td><td>0.10</td></tr><tr><td>1,000,000 unshift & shift</td><td>259.65</td><td>3.85</td><td>0.14</td></tr><tr><td>1,000,000 insertBefore</td><td>463.16</td><td>2.16</td><td>0.10</td></tr></table></div>
</div><div class="json-to-html-collapse clearfix 0">
<div class='collapsible level0' ><span class='json-to-html-label'>singly-linked-list</span></div>
<div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>1,000,000 push & shift</td><td>250.27</td><td>4.00</td><td>0.08</td></tr><tr><td>10,000 push & pop</td><td>261.13</td><td>3.83</td><td>0.03</td></tr><tr><td>10,000 insertBefore</td><td>282.46</td><td>3.54</td><td>0.02</td></tr></table></div>
</div><div class="json-to-html-collapse clearfix 0">
<div class='collapsible level0' ><span class='json-to-html-label'>max-priority-queue</span></div>
<div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>10,000 refill & poll</td><td>10.49</td><td>95.29</td><td>0.00</td></tr></table></div>
</div><div class="json-to-html-collapse clearfix 0">
<div class='collapsible level0' ><span class='json-to-html-label'>priority-queue</span></div>
<div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>100,000 add & pop</td><td>110.63</td><td>9.04</td><td>0.01</td></tr></table></div>
</div><div class="json-to-html-collapse clearfix 0">
<div class='collapsible level0' ><span class='json-to-html-label'>deque</span></div>
<div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>1,000,000 push</td><td>15.89</td><td>62.92</td><td>0.00</td></tr><tr><td>1,000,000 push & pop</td><td>26.45</td><td>37.81</td><td>0.01</td></tr><tr><td>1,000,000 push & shift</td><td>27.52</td><td>36.34</td><td>0.00</td></tr><tr><td>1,000,000 unshift & shift</td><td>28.82</td><td>34.70</td><td>0.01</td></tr></table></div>
</div><div class="json-to-html-collapse clearfix 0">
<div class='collapsible level0' ><span class='json-to-html-label'>queue</span></div>
<div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>1,000,000 push</td><td>51.21</td><td>19.53</td><td>0.02</td></tr><tr><td>1,000,000 push & shift</td><td>105.56</td><td>9.47</td><td>0.05</td></tr></table></div>
</div><div class="json-to-html-collapse clearfix 0">
<div class='collapsible level0' ><span class='json-to-html-label'>stack</span></div>
<div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>1,000,000 push</td><td>43.57</td><td>22.95</td><td>0.01</td></tr><tr><td>1,000,000 push & pop</td><td>55.18</td><td>18.12</td><td>0.01</td></tr></table></div>
</div><div class="json-to-html-collapse clearfix 0">
<div class='collapsible level0' ><span class='json-to-html-label'>trie</span></div>
<div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>100,000 push</td><td>54.08</td><td>18.49</td><td>0.01</td></tr><tr><td>100,000 getWords</td><td>77.77</td><td>12.86</td><td>0.02</td></tr></table></div>
</div>
[//]: # (No deletion!!! End of Replace Section)

113

README.md

@@ -7,2 +7,3 @@ # data-structure-typed

![GitHub top language](https://img.shields.io/github/languages/top/zrwusa/data-structure-typed)
![GITHUB Star](https://img.shields.io/github/stars/zrwusa/data-structure-typed)
![eslint](https://aleen42.github.io/badges/src/eslint.svg)

@@ -828,57 +829,2 @@ ![NPM](https://img.shields.io/npm/l/data-structure-typed)

## Benchmark
[//]: # (No deletion!!! Start of Replace Section)
<div class="json-to-html-collapse clearfix 0">
<div class='collapsible level0' ><span class='json-to-html-label'>avl-tree</span></div>
<div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>10,000 add randomly</td><td>51.22</td><td>19.52</td><td>0.00</td></tr><tr><td>10,000 add & delete randomly</td><td>110.40</td><td>9.06</td><td>0.00</td></tr><tr><td>10,000 addMany</td><td>58.39</td><td>17.13</td><td>6.35e-4</td></tr><tr><td>10,000 get</td><td>50.59</td><td>19.77</td><td>3.87e-4</td></tr></table></div>
</div><div class="json-to-html-collapse clearfix 0">
<div class='collapsible level0' ><span class='json-to-html-label'>binary-tree</span></div>
<div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>1,000 add randomly</td><td>13.83</td><td>72.29</td><td>1.19e-4</td></tr><tr><td>1,000 add & delete randomly</td><td>21.49</td><td>46.54</td><td>2.34e-4</td></tr><tr><td>1,000 addMany</td><td>15.93</td><td>62.78</td><td>1.27e-4</td></tr><tr><td>1,000 get</td><td>18.19</td><td>54.98</td><td>1.79e-4</td></tr><tr><td>1,000 has</td><td>18.20</td><td>54.93</td><td>1.71e-4</td></tr><tr><td>1,000 dfs</td><td>161.79</td><td>6.18</td><td>7.45e-4</td></tr><tr><td>1,000 bfs</td><td>56.68</td><td>17.64</td><td>4.77e-4</td></tr><tr><td>1,000 morris</td><td>262.64</td><td>3.81</td><td>0.00</td></tr></table></div>
</div><div class="json-to-html-collapse clearfix 0">
<div class='collapsible level0' ><span class='json-to-html-label'>bst</span></div>
<div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>10,000 add randomly</td><td>51.51</td><td>19.41</td><td>8.70e-4</td></tr><tr><td>10,000 add & delete randomly</td><td>114.09</td><td>8.76</td><td>9.66e-4</td></tr><tr><td>10,000 addMany</td><td>47.86</td><td>20.90</td><td>2.77e-4</td></tr><tr><td>10,000 get</td><td>51.93</td><td>19.26</td><td>6.56e-4</td></tr></table></div>
</div><div class="json-to-html-collapse clearfix 0">
<div class='collapsible level0' ><span class='json-to-html-label'>rb-tree</span></div>
<div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>100,000 add</td><td>86.63</td><td>11.54</td><td>0.00</td></tr><tr><td>100,000 add & delete randomly</td><td>218.88</td><td>4.57</td><td>0.01</td></tr><tr><td>100,000 getNode</td><td>261.16</td><td>3.83</td><td>0.00</td></tr><tr><td>100,000 add & iterator</td><td>117.64</td><td>8.50</td><td>0.00</td></tr></table></div>
</div><div class="json-to-html-collapse clearfix 0">
<div class='collapsible level0' ><span class='json-to-html-label'>comparison</span></div>
<div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>SRC PQ 10,000 add</td><td>0.14</td><td>6949.20</td><td>1.53e-6</td></tr><tr><td>CJS PQ 10,000 add</td><td>0.14</td><td>6943.68</td><td>1.74e-6</td></tr><tr><td>MJS PQ 10,000 add</td><td>0.57</td><td>1758.40</td><td>6.26e-6</td></tr><tr><td>SRC PQ 10,000 add & pop</td><td>3.40</td><td>293.94</td><td>3.50e-5</td></tr><tr><td>CJS PQ 10,000 add & pop</td><td>3.42</td><td>292.69</td><td>5.34e-5</td></tr><tr><td>MJS PQ 10,000 add & pop</td><td>3.30</td><td>303.01</td><td>3.97e-5</td></tr></table></div>
</div><div class="json-to-html-collapse clearfix 0">
<div class='collapsible level0' ><span class='json-to-html-label'>directed-graph</span></div>
<div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>1,000 addVertex</td><td>0.10</td><td>9930.74</td><td>1.11e-6</td></tr><tr><td>1,000 addEdge</td><td>6.13</td><td>163.19</td><td>1.84e-4</td></tr><tr><td>1,000 getVertex</td><td>0.05</td><td>2.15e+4</td><td>5.00e-7</td></tr><tr><td>1,000 getEdge</td><td>23.57</td><td>42.43</td><td>0.00</td></tr><tr><td>tarjan</td><td>252.05</td><td>3.97</td><td>0.03</td></tr><tr><td>tarjan all</td><td>221.15</td><td>4.52</td><td>0.00</td></tr><tr><td>topologicalSort</td><td>181.07</td><td>5.52</td><td>0.00</td></tr></table></div>
</div><div class="json-to-html-collapse clearfix 0">
<div class='collapsible level0' ><span class='json-to-html-label'>hash-map</span></div>
<div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>1,000,000 set</td><td>122.90</td><td>8.14</td><td>0.04</td></tr><tr><td>Native Map 1,000,000 set</td><td>215.97</td><td>4.63</td><td>0.02</td></tr><tr><td>Native Set 1,000,000 add</td><td>179.11</td><td>5.58</td><td>0.02</td></tr><tr><td>1,000,000 set & get</td><td>123.10</td><td>8.12</td><td>0.04</td></tr><tr><td>Native Map 1,000,000 set & get</td><td>271.80</td><td>3.68</td><td>0.02</td></tr><tr><td>Native Set 1,000,000 add & has</td><td>176.65</td><td>5.66</td><td>0.02</td></tr><tr><td>1,000,000 ObjKey set & get</td><td>341.97</td><td>2.92</td><td>0.07</td></tr><tr><td>Native Map 1,000,000 ObjKey set & get</td><td>316.86</td><td>3.16</td><td>0.04</td></tr><tr><td>Native Set 1,000,000 ObjKey add & has</td><td>285.14</td><td>3.51</td><td>0.06</td></tr></table></div>
</div><div class="json-to-html-collapse clearfix 0">
<div class='collapsible level0' ><span class='json-to-html-label'>heap</span></div>
<div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>100,000 add & pop</td><td>80.37</td><td>12.44</td><td>0.00</td></tr><tr><td>100,000 add & dfs</td><td>36.20</td><td>27.63</td><td>0.00</td></tr><tr><td>10,000 fib add & pop</td><td>362.24</td><td>2.76</td><td>0.00</td></tr></table></div>
</div><div class="json-to-html-collapse clearfix 0">
<div class='collapsible level0' ><span class='json-to-html-label'>doubly-linked-list</span></div>
<div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>1,000,000 push</td><td>216.09</td><td>4.63</td><td>0.06</td></tr><tr><td>1,000,000 unshift</td><td>220.68</td><td>4.53</td><td>0.02</td></tr><tr><td>1,000,000 unshift & shift</td><td>172.93</td><td>5.78</td><td>0.04</td></tr><tr><td>1,000,000 insertBefore</td><td>332.25</td><td>3.01</td><td>0.08</td></tr></table></div>
</div><div class="json-to-html-collapse clearfix 0">
<div class='collapsible level0' ><span class='json-to-html-label'>singly-linked-list</span></div>
<div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>1,000,000 push & shift</td><td>222.99</td><td>4.48</td><td>0.10</td></tr><tr><td>10,000 push & pop</td><td>214.82</td><td>4.66</td><td>0.01</td></tr><tr><td>10,000 insertBefore</td><td>251.24</td><td>3.98</td><td>0.01</td></tr></table></div>
</div><div class="json-to-html-collapse clearfix 0">
<div class='collapsible level0' ><span class='json-to-html-label'>max-priority-queue</span></div>
<div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>10,000 refill & poll</td><td>8.91</td><td>112.19</td><td>1.57e-4</td></tr></table></div>
</div><div class="json-to-html-collapse clearfix 0">
<div class='collapsible level0' ><span class='json-to-html-label'>priority-queue</span></div>
<div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>100,000 add & pop</td><td>101.70</td><td>9.83</td><td>0.00</td></tr></table></div>
</div><div class="json-to-html-collapse clearfix 0">
<div class='collapsible level0' ><span class='json-to-html-label'>deque</span></div>
<div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>1,000,000 push</td><td>13.80</td><td>72.47</td><td>1.56e-4</td></tr><tr><td>1,000,000 push & pop</td><td>22.72</td><td>44.02</td><td>2.02e-4</td></tr><tr><td>100,000 push & shift</td><td>2.35</td><td>425.67</td><td>5.80e-5</td></tr><tr><td>Native Array 100,000 push & shift</td><td>2511.14</td><td>0.40</td><td>0.36</td></tr><tr><td>100,000 unshift & shift</td><td>2.23</td><td>447.89</td><td>3.30e-4</td></tr><tr><td>Native Array 100,000 unshift & shift</td><td>4140.23</td><td>0.24</td><td>0.33</td></tr></table></div>
</div><div class="json-to-html-collapse clearfix 0">
<div class='collapsible level0' ><span class='json-to-html-label'>queue</span></div>
<div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>1,000,000 push</td><td>43.65</td><td>22.91</td><td>0.01</td></tr><tr><td>100,000 push & shift</td><td>4.99</td><td>200.28</td><td>9.54e-5</td></tr><tr><td>Native Array 100,000 push & shift</td><td>2335.63</td><td>0.43</td><td>0.33</td></tr><tr><td>Native Array 100,000 push & pop</td><td>4.39</td><td>227.81</td><td>0.00</td></tr></table></div>
</div><div class="json-to-html-collapse clearfix 0">
<div class='collapsible level0' ><span class='json-to-html-label'>stack</span></div>
<div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>1,000,000 push</td><td>45.38</td><td>22.04</td><td>0.01</td></tr><tr><td>1,000,000 push & pop</td><td>49.52</td><td>20.19</td><td>0.01</td></tr></table></div>
</div><div class="json-to-html-collapse clearfix 0">
<div class='collapsible level0' ><span class='json-to-html-label'>trie</span></div>
<div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>100,000 push</td><td>42.99</td><td>23.26</td><td>0.00</td></tr><tr><td>100,000 getWords</td><td>89.78</td><td>11.14</td><td>0.00</td></tr></table></div>
</div>
[//]: # (No deletion!!! End of Replace Section)
## Built-in classic algorithms

@@ -1034,1 +980,58 @@

## Benchmark
[//]: # (No deletion!!! Start of Replace Section)
<div class="json-to-html-collapse clearfix 0">
<div class='collapsible level0' ><span class='json-to-html-label'>avl-tree</span></div>
<div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>10,000 add randomly</td><td>51.22</td><td>19.52</td><td>0.00</td></tr><tr><td>10,000 add & delete randomly</td><td>110.40</td><td>9.06</td><td>0.00</td></tr><tr><td>10,000 addMany</td><td>58.39</td><td>17.13</td><td>6.35e-4</td></tr><tr><td>10,000 get</td><td>50.59</td><td>19.77</td><td>3.87e-4</td></tr></table></div>
</div><div class="json-to-html-collapse clearfix 0">
<div class='collapsible level0' ><span class='json-to-html-label'>binary-tree</span></div>
<div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>1,000 add randomly</td><td>13.83</td><td>72.29</td><td>1.19e-4</td></tr><tr><td>1,000 add & delete randomly</td><td>21.49</td><td>46.54</td><td>2.34e-4</td></tr><tr><td>1,000 addMany</td><td>15.93</td><td>62.78</td><td>1.27e-4</td></tr><tr><td>1,000 get</td><td>18.19</td><td>54.98</td><td>1.79e-4</td></tr><tr><td>1,000 has</td><td>18.20</td><td>54.93</td><td>1.71e-4</td></tr><tr><td>1,000 dfs</td><td>161.79</td><td>6.18</td><td>7.45e-4</td></tr><tr><td>1,000 bfs</td><td>56.68</td><td>17.64</td><td>4.77e-4</td></tr><tr><td>1,000 morris</td><td>262.64</td><td>3.81</td><td>0.00</td></tr></table></div>
</div><div class="json-to-html-collapse clearfix 0">
<div class='collapsible level0' ><span class='json-to-html-label'>bst</span></div>
<div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>10,000 add randomly</td><td>51.51</td><td>19.41</td><td>8.70e-4</td></tr><tr><td>10,000 add & delete randomly</td><td>114.09</td><td>8.76</td><td>9.66e-4</td></tr><tr><td>10,000 addMany</td><td>47.86</td><td>20.90</td><td>2.77e-4</td></tr><tr><td>10,000 get</td><td>51.93</td><td>19.26</td><td>6.56e-4</td></tr></table></div>
</div><div class="json-to-html-collapse clearfix 0">
<div class='collapsible level0' ><span class='json-to-html-label'>rb-tree</span></div>
<div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>100,000 add</td><td>86.63</td><td>11.54</td><td>0.00</td></tr><tr><td>100,000 add & delete randomly</td><td>218.88</td><td>4.57</td><td>0.01</td></tr><tr><td>100,000 getNode</td><td>261.16</td><td>3.83</td><td>0.00</td></tr><tr><td>100,000 add & iterator</td><td>117.64</td><td>8.50</td><td>0.00</td></tr></table></div>
</div><div class="json-to-html-collapse clearfix 0">
<div class='collapsible level0' ><span class='json-to-html-label'>comparison</span></div>
<div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>SRC PQ 10,000 add</td><td>0.14</td><td>6949.20</td><td>1.53e-6</td></tr><tr><td>CJS PQ 10,000 add</td><td>0.14</td><td>6943.68</td><td>1.74e-6</td></tr><tr><td>MJS PQ 10,000 add</td><td>0.57</td><td>1758.40</td><td>6.26e-6</td></tr><tr><td>SRC PQ 10,000 add & pop</td><td>3.40</td><td>293.94</td><td>3.50e-5</td></tr><tr><td>CJS PQ 10,000 add & pop</td><td>3.42</td><td>292.69</td><td>5.34e-5</td></tr><tr><td>MJS PQ 10,000 add & pop</td><td>3.30</td><td>303.01</td><td>3.97e-5</td></tr></table></div>
</div><div class="json-to-html-collapse clearfix 0">
<div class='collapsible level0' ><span class='json-to-html-label'>directed-graph</span></div>
<div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>1,000 addVertex</td><td>0.10</td><td>9930.74</td><td>1.11e-6</td></tr><tr><td>1,000 addEdge</td><td>6.13</td><td>163.19</td><td>1.84e-4</td></tr><tr><td>1,000 getVertex</td><td>0.05</td><td>2.15e+4</td><td>5.00e-7</td></tr><tr><td>1,000 getEdge</td><td>23.57</td><td>42.43</td><td>0.00</td></tr><tr><td>tarjan</td><td>252.05</td><td>3.97</td><td>0.03</td></tr><tr><td>tarjan all</td><td>221.15</td><td>4.52</td><td>0.00</td></tr><tr><td>topologicalSort</td><td>181.07</td><td>5.52</td><td>0.00</td></tr></table></div>
</div><div class="json-to-html-collapse clearfix 0">
<div class='collapsible level0' ><span class='json-to-html-label'>hash-map</span></div>
<div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>1,000,000 set</td><td>122.90</td><td>8.14</td><td>0.04</td></tr><tr><td>Native Map 1,000,000 set</td><td>215.97</td><td>4.63</td><td>0.02</td></tr><tr><td>Native Set 1,000,000 add</td><td>179.11</td><td>5.58</td><td>0.02</td></tr><tr><td>1,000,000 set & get</td><td>123.10</td><td>8.12</td><td>0.04</td></tr><tr><td>Native Map 1,000,000 set & get</td><td>271.80</td><td>3.68</td><td>0.02</td></tr><tr><td>Native Set 1,000,000 add & has</td><td>176.65</td><td>5.66</td><td>0.02</td></tr><tr><td>1,000,000 ObjKey set & get</td><td>341.97</td><td>2.92</td><td>0.07</td></tr><tr><td>Native Map 1,000,000 ObjKey set & get</td><td>316.86</td><td>3.16</td><td>0.04</td></tr><tr><td>Native Set 1,000,000 ObjKey add & has</td><td>285.14</td><td>3.51</td><td>0.06</td></tr></table></div>
</div><div class="json-to-html-collapse clearfix 0">
<div class='collapsible level0' ><span class='json-to-html-label'>heap</span></div>
<div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>100,000 add & pop</td><td>80.37</td><td>12.44</td><td>0.00</td></tr><tr><td>100,000 add & dfs</td><td>36.20</td><td>27.63</td><td>0.00</td></tr><tr><td>10,000 fib add & pop</td><td>362.24</td><td>2.76</td><td>0.00</td></tr></table></div>
</div><div class="json-to-html-collapse clearfix 0">
<div class='collapsible level0' ><span class='json-to-html-label'>doubly-linked-list</span></div>
<div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>1,000,000 push</td><td>216.09</td><td>4.63</td><td>0.06</td></tr><tr><td>1,000,000 unshift</td><td>220.68</td><td>4.53</td><td>0.02</td></tr><tr><td>1,000,000 unshift & shift</td><td>172.93</td><td>5.78</td><td>0.04</td></tr><tr><td>1,000,000 insertBefore</td><td>332.25</td><td>3.01</td><td>0.08</td></tr></table></div>
</div><div class="json-to-html-collapse clearfix 0">
<div class='collapsible level0' ><span class='json-to-html-label'>singly-linked-list</span></div>
<div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>1,000,000 push & shift</td><td>222.99</td><td>4.48</td><td>0.10</td></tr><tr><td>10,000 push & pop</td><td>214.82</td><td>4.66</td><td>0.01</td></tr><tr><td>10,000 insertBefore</td><td>251.24</td><td>3.98</td><td>0.01</td></tr></table></div>
</div><div class="json-to-html-collapse clearfix 0">
<div class='collapsible level0' ><span class='json-to-html-label'>max-priority-queue</span></div>
<div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>10,000 refill & poll</td><td>8.91</td><td>112.19</td><td>1.57e-4</td></tr></table></div>
</div><div class="json-to-html-collapse clearfix 0">
<div class='collapsible level0' ><span class='json-to-html-label'>priority-queue</span></div>
<div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>100,000 add & pop</td><td>101.70</td><td>9.83</td><td>0.00</td></tr></table></div>
</div><div class="json-to-html-collapse clearfix 0">
<div class='collapsible level0' ><span class='json-to-html-label'>deque</span></div>
<div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>1,000,000 push</td><td>13.80</td><td>72.47</td><td>1.56e-4</td></tr><tr><td>1,000,000 push & pop</td><td>22.72</td><td>44.02</td><td>2.02e-4</td></tr><tr><td>100,000 push & shift</td><td>2.35</td><td>425.67</td><td>5.80e-5</td></tr><tr><td>Native Array 100,000 push & shift</td><td>2511.14</td><td>0.40</td><td>0.36</td></tr><tr><td>100,000 unshift & shift</td><td>2.23</td><td>447.89</td><td>3.30e-4</td></tr><tr><td>Native Array 100,000 unshift & shift</td><td>4140.23</td><td>0.24</td><td>0.33</td></tr></table></div>
</div><div class="json-to-html-collapse clearfix 0">
<div class='collapsible level0' ><span class='json-to-html-label'>queue</span></div>
<div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>1,000,000 push</td><td>43.65</td><td>22.91</td><td>0.01</td></tr><tr><td>100,000 push & shift</td><td>4.99</td><td>200.28</td><td>9.54e-5</td></tr><tr><td>Native Array 100,000 push & shift</td><td>2335.63</td><td>0.43</td><td>0.33</td></tr><tr><td>Native Array 100,000 push & pop</td><td>4.39</td><td>227.81</td><td>0.00</td></tr></table></div>
</div><div class="json-to-html-collapse clearfix 0">
<div class='collapsible level0' ><span class='json-to-html-label'>stack</span></div>
<div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>1,000,000 push</td><td>45.38</td><td>22.04</td><td>0.01</td></tr><tr><td>1,000,000 push & pop</td><td>49.52</td><td>20.19</td><td>0.01</td></tr></table></div>
</div><div class="json-to-html-collapse clearfix 0">
<div class='collapsible level0' ><span class='json-to-html-label'>trie</span></div>
<div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>100,000 push</td><td>42.99</td><td>23.26</td><td>0.00</td></tr><tr><td>100,000 getWords</td><td>89.78</td><td>11.14</td><td>0.00</td></tr></table></div>
</div>
[//]: # (No deletion!!! End of Replace Section)

192

src/data-structures/queue/deque.ts

@@ -852,192 +852,2 @@ /**

}
}
// O(1) time complexity of obtaining the element
// O(n) time complexity of adding at the beginning and the end
// todo tested slowest one
export class ObjectDeque<E = number> {
constructor(capacity?: number) {
if (capacity !== undefined) this._capacity = capacity;
}
protected _nodes: { [key: number]: E } = {};
get nodes(): { [p: number]: E } {
return this._nodes;
}
protected _capacity = Number.MAX_SAFE_INTEGER;
get capacity(): number {
return this._capacity;
}
protected _first = -1;
get first(): number {
return this._first;
}
protected _last = -1;
get last(): number {
return this._last;
}
protected _size = 0;
get size(): number {
return this._size;
}
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*
* The "addFirst" function adds an element to the beginning of an array-like data structure.
* @param {E} element - The `element` parameter represents the element that you want to add to the beginning of the data
* structure.
*/
addFirst(element: E) {
if (this.size === 0) {
const mid = Math.floor(this.capacity / 2);
this._first = mid;
this._last = mid;
} else {
this._first--;
}
this.nodes[this.first] = element;
this._size++;
}
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*
* The addLast function adds an element to the end of an array-like data structure.
* @param {E} element - The `element` parameter represents the element that you want to add to the end of the data structure.
*/
addLast(element: E) {
if (this.size === 0) {
const mid = Math.floor(this.capacity / 2);
this._first = mid;
this._last = mid;
} else {
this._last++;
}
this.nodes[this.last] = element;
this._size++;
}
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*
* The function `pollFirst()` removes and returns the first element in a data structure.
* @returns The element of the first element in the data structure.
*/
pollFirst() {
if (!this.size) return;
const element = this.getFirst();
delete this.nodes[this.first];
this._first++;
this._size--;
return element;
}
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*
* The `getFirst` function returns the first element in an array-like data structure if it exists.
* @returns The element at the first position of the `_nodes` array.
*/
getFirst() {
if (this.size) return this.nodes[this.first];
}
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*
* The `pollLast()` function removes and returns the last element in a data structure.
* @returns The element that was removed from the data structure.
*/
pollLast() {
if (!this.size) return;
const element = this.getLast();
delete this.nodes[this.last];
this._last--;
this._size--;
return element;
}
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*
* The `getLast()` function returns the last element in an array-like data structure.
* @returns The last element in the array "_nodes" is being returned.
*/
getLast() {
if (this.size) return this.nodes[this.last];
}
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*
* The get function returns the element at the specified index in an array-like data structure.
* @param {number} index - The index parameter is a number that represents the position of the element you want to
* retrieve from the array.
* @returns The element at the specified index in the `_nodes` array is being returned. If there is no element at that
* index, `undefined` is returned.
*/
get(index: number) {
return this.nodes[this.first + index] || undefined;
}
/**
* The function checks if the size of a data structure is less than or equal to zero.
* @returns The method is returning a boolean element indicating whether the size of the object is less than or equal to 0.
*/
isEmpty() {
return this.size <= 0;
}
}
}

23

test/unit/data-structures/binary-tree/binary-tree.test.ts
import { BinaryTree, BinaryTreeNode, FamilyPosition, IterationType } from '../../../../src';
import { getRandomIntArray } from '../../../utils';
// import {isDebugTest} from '../../../config';
import { isDebugTest } from '../../../config';
// const isDebug = isDebugTest;
const isDebug = isDebugTest;

@@ -109,3 +109,3 @@ describe('BinaryTreeNode', () => {

expect(tree.getMinHeight()).toBe(-1);
const node = tree.add(1);
const node1 = tree.add(1);
expect(tree.size).toBe(1);

@@ -131,6 +131,6 @@

if (node) {
const result = tree.delete(node);
if (node1) {
const result = tree.delete(node1);
expect(result).toHaveLength(1);
expect(tree.size).toBe(3);
expect(tree.size).toBe(4);
expect(tree.getMinHeight(tree.root, IterationType.RECURSIVE)).toBe(1);

@@ -265,2 +265,9 @@ }

});
it('should duplicated nodes just replace the node exists', function () {
tree.clear();
tree.addMany([-10, -10, -10, 9, 9, 20, null, null, 15, 7, 8, null, 2, null, 6, null, null, 8, 8, 8]);
expect(tree.bfs(node => node ? node.key : null, undefined, undefined, true)).toEqual([-10, 9, 20, null, null, 15, 7, 8, null, 2, null, 6, null, null])
});
});

@@ -270,3 +277,3 @@

// Create a binary tree
const tree = new BinaryTree<number, BinaryTreeNode<number>>();
const tree = new BinaryTree<number>();
tree.add(1);

@@ -455,3 +462,3 @@ tree.add(2);

tree.add([5, 'A']);
tree.add([3, 'B']);
tree.add(3, 'B');
tree.add([7, 'C']);

@@ -458,0 +465,0 @@

2

test/unit/data-structures/binary-tree/bst.test.ts

@@ -8,3 +8,3 @@ import { BinaryTreeNode, BST, BSTNode, CP, IterationType } from '../../../../src';

it('should perform various operations on a Binary Search Tree with numeric values', () => {
const bst = new BST();
const bst = new BST<number, number>();
expect(bst).toBeInstanceOf(BST);

@@ -11,0 +11,0 @@ bst.add([11, 11]);

10

test/unit/data-structures/binary-tree/rb-tree.test.ts

@@ -9,6 +9,6 @@ import { BinaryTreeNode, BSTNode, IterationType, RBTNColor, RedBlackTree, RedBlackTreeNode } from '../../../../src';

describe('RedBlackTree', () => {
let tree: RedBlackTree;
let tree: RedBlackTree<number>;
beforeEach(() => {
tree = new RedBlackTree();
tree = new RedBlackTree<number>();
});

@@ -145,6 +145,6 @@

describe('RedBlackTree', () => {
let tree: RedBlackTree;
let tree: RedBlackTree<number>;
beforeEach(() => {
tree = new RedBlackTree();
tree = new RedBlackTree<number>();
});

@@ -516,3 +516,3 @@

rbTree.add([1, 'a']);
rbTree.add([2, 'b']);
rbTree.add(2, 'b');
rbTree.add([3, 'c']);

@@ -519,0 +519,0 @@ });

632

test/unit/data-structures/queue/deque.test.ts
import { Deque } from '../../../../src';
import { bigO } from '../../../utils';
import { isDebugTest } from '../../../config';
const isDebug = isDebugTest;
describe('Deque Tests', () => {
// Test cases for the Deque class (DoublyLinkedList-based)
describe('Deque (DoublyLinkedList-based)', () => {
let deque: Deque<number>;
beforeEach(() => {
deque = new Deque<number>();
});
it('should add elements at the beginning and end', () => {
deque.addFirst(1);
deque.addLast(2);
expect(deque.first).toBe(1);
expect(deque.last).toBe(2);
});
it('should delete elements from the beginning and end', () => {
deque.addFirst(1);
deque.addLast(2);
deque.pollFirst();
deque.pollLast();
expect(deque.isEmpty()).toBe(true);
});
it('should handle edge case when removing from an empty deque', () => {
const result = deque.pollFirst();
expect(result).toBeUndefined();
});
it('should correctly report its size', () => {
deque.addFirst(1);
deque.addLast(2);
expect(deque.size).toBe(2);
});
it('should handle adding and removing elements alternately', () => {
deque.addFirst(1);
expect(deque.pollFirst()).toBe(1);
deque.addLast(2);
expect(deque.pollLast()).toBe(2);
expect(deque.isEmpty()).toBe(true);
});
it('should handle adding and removing elements in a cyclic manner', () => {
deque.addFirst(1);
deque.addLast(2);
expect(deque.pollFirst()).toBe(1);
deque.addFirst(3);
expect(deque.pollLast()).toBe(2);
expect(deque.size).toBe(1);
});
// Add more test cases as needed
});
// // Test cases for the ObjectDeque class
// describe('ObjectDeque', () => {
// let objectDeque: ObjectDeque<string>;
//
// beforeEach(() => {
// objectDeque = new ObjectDeque<string>();
// });
//
// it('should add elements at the beginning and end', () => {
// objectDeque.addFirst('one');
// objectDeque.addLast('two');
// expect(objectDeque.getFirst()).toBe('one');
// expect(objectDeque.getLast()).toBe('two');
// });
//
// it('should delete elements from the beginning and end', () => {
// objectDeque.addFirst('one');
// objectDeque.addLast('two');
// objectDeque.pollFirst();
// objectDeque.pollLast();
// expect(objectDeque.isEmpty()).toBe(true);
// });
//
// it('should handle edge case when removing from an empty deque', () => {
// const result = objectDeque.pollFirst();
// expect(result).toBeUndefined();
// });
//
// it('should correctly report its size', () => {
// objectDeque.addFirst('one');
// objectDeque.addLast('two');
// expect(objectDeque.size).toBe(2);
// });
//
// // Add more test cases as needed
// });
});
describe('Deque Performance Test', () => {
const dataSize = 10000;
it('should numeric queue be efficient', function () {
const startTime = performance.now();
const queue = new Deque<number>();
for (let i = 0; i < dataSize; i++) {
queue.unshift(i);
}
for (let i = 0; i < dataSize; i++) {
queue.pop();
}
isDebug && console.log(`Queue Deque Test: ${performance.now() - startTime} ms`);
expect(performance.now() - startTime).toBeLessThan(bigO.LINEAR * 100);
});
});
describe('Deque', () => {
describe('Deque - Basic Operations', () => {
let deque: Deque<number>;
beforeEach(() => {
deque = new Deque<number>();
deque = new Deque<number>([1, 2]);
});
it('should initialize an empty deque', () => {
expect(deque.size).toBe(0);
expect(deque.isEmpty()).toBe(true);
test('push should add elements to the end', () => {
expect(deque.size).toBe(2);
expect(deque.last).toBe(2);
});
it('should add elements to the front and back', () => {
deque.addFirst(1);
deque.addLast(2);
test('pop should remove elements from the end', () => {
expect(deque.pop()).toBe(2);
expect(deque.size).toBe(1);
expect(deque.pop()).toBe(1);
expect(deque.isEmpty()).toBeTruthy();
});
test('unshift should add elements to the beginning', () => {
deque.clear();
deque.unshift(1);
deque.unshift(2);
expect(deque.size).toBe(2);
expect(deque.first).toBe(1);
expect(deque.last).toBe(2);
expect(deque.first).toBe(2);
});
it('should remove elements from the front and back', () => {
deque.addFirst(1);
deque.addLast(2);
const firstElement = deque.pollFirst();
const lastElement = deque.pollLast();
expect(deque.size).toBe(0);
expect(firstElement).toBe(1);
expect(lastElement).toBe(2);
test('shift should remove elements from the beginning', () => {
deque.clear();
deque.unshift(1);
deque.unshift(2);
expect(deque.shift()).toBe(2);
expect(deque.size).toBe(1);
expect(deque.shift()).toBe(1);
expect(deque.isEmpty()).toBeTruthy();
});
it('should get elements by index', () => {
deque.addLast(1);
deque.addLast(2);
deque.addLast(3);
test('getAt should retrieve the correct element', () => {
expect(deque.getAt(0)).toBe(1);
expect(deque.getAt(1)).toBe(2);
expect(deque.getAt(2)).toBe(3);
});
it('should return undefined for out-of-bounds index', () => {
// expect(deque.getAt(0)).toThrowError('Index out of bounds.');
// expect(deque.getAt(1)).toThrow('Index out of bounds');
// expect(deque.getAt(-1)).toThrow('Index out of bounds');
test('setAt should set the correct element', () => {
deque.setAt(0, 3);
expect(deque.getAt(0)).toBe(3);
});
it('should check if the deque is empty', () => {
expect(deque.isEmpty()).toBe(true);
deque.addLast(1);
expect(deque.isEmpty()).toBe(false);
deque.pollFirst();
expect(deque.isEmpty()).toBe(true);
});
});
// describe('ObjectDeque', () => {
// let deque: ObjectDeque<number>;
//
// beforeEach(() => {
// deque = new ObjectDeque<number>();
// });
//
// it('should add elements to the front of the deque', () => {
// deque.addFirst(1);
// deque.addFirst(2);
//
// expect(deque.size).toBe(2);
// expect(deque.getFirst()).toBe(2);
// expect(deque.getLast()).toBe(1);
// });
//
// it('should add elements to the end of the deque', () => {
// deque.addLast(1);
// deque.addLast(2);
//
// expect(deque.size).toBe(2);
// expect(deque.getFirst()).toBe(1);
// expect(deque.getLast()).toBe(2);
// });
//
// it('should remove elements from the front of the deque', () => {
// deque.addLast(1);
// deque.addLast(2);
//
// const removedElement = deque.pollFirst();
//
// expect(deque.size).toBe(1);
// expect(removedElement).toBe(1);
// expect(deque.getFirst()).toBe(2);
// });
//
// it('should remove elements from the end of the deque', () => {
// deque.addLast(1);
// deque.addLast(2);
//
// const removedElement = deque.pollFirst();
//
// expect(deque.size).toBe(1);
// expect(removedElement).toBe(1);
// expect(deque.getLast()).toBe(2);
// });
//
// it('should return the element at the front of the deque without removing it', () => {
// deque.addFirst(1);
// deque.addFirst(2);
//
// expect(deque.getFirst()).toBe(2);
// expect(deque.size).toBe(2);
// });
//
// it('should return the element at the end of the deque without removing it', () => {
// deque.addLast(1);
// deque.addLast(2);
//
// expect(deque.getLast()).toBe(2);
// expect(deque.size).toBe(2);
// });
//
// it('should return the correct size of the deque', () => {
// deque.addFirst(1);
// deque.addLast(2);
// deque.addLast(3);
//
// expect(deque.size).toBe(3);
// });
//
// it('should check if the deque is empty', () => {
// expect(deque.isEmpty()).toBe(true);
//
// deque.addFirst(1);
//
// expect(deque.isEmpty()).toBe(false);
// });
//
// it('should set elements at a specific index', () => {
// deque.addFirst(1);
// deque.addLast(2);
// deque.addLast(3);
//
// expect(deque.getFirst()).toBe(1);
// expect(deque.get(1)).toBe(2);
// expect(deque.getLast()).toBe(3);
// });
//
// it('should insert elements at a specific index', () => {
// deque.addFirst(1);
// deque.addLast(2);
// deque.addLast(3);
//
// expect(deque.size).toBe(3);
// expect(deque.getFirst()).toBe(1);
// expect(deque.get(1)).toBe(2);
// expect(deque.get(2)).toBe(3);
// expect(deque.getLast()).toBe(3);
// });
// });
describe('Deque', () => {
describe('Deque - Complex Operations', () => {
let deque: Deque<number>;

@@ -284,193 +60,315 @@

// test('initializes with default capacity', () => {
// expect(deque.capacity).toBe(10);
// });
// test('initializes with given capacity', () => {
// const customDeque = new Deque(20);
// expect(customDeque.capacity).toBe(20);
// });
test('is initially empty', () => {
expect(deque.isEmpty()).toBe(true);
test('insertAt should insert elements at the specified position', () => {
deque.push(1);
deque.push(3);
deque.insertAt(1, 2);
expect(deque.toArray()).toEqual([1, 2, 3]);
});
test('pushes and pops elements', () => {
test('cut should remove elements after the specified position', () => {
deque.push(1);
deque.push(2);
expect(deque.pop()).toBe(2);
expect(deque.pop()).toBe(1);
expect(deque.pop()).toBeUndefined();
deque.push(3);
deque.cut(1);
expect(deque.toArray()).toEqual([1, 2]);
});
test('unshifts and shifts elements', () => {
deque.unshift(1);
deque.unshift(2);
expect(deque.shift()).toBe(2);
expect(deque.shift()).toBe(1);
expect(deque.shift()).toBeUndefined();
test('deleteAt should remove the element at the specified position', () => {
deque.push(1);
deque.push(2);
deque.push(3);
deque.deleteAt(1);
expect(deque.toArray()).toEqual([1, 3]);
});
test('correctly reports size', () => {
expect(deque.size).toBe(0);
test('delete should remove all instances of an element', () => {
deque.push(1);
deque.push(2);
expect(deque.size).toBe(2);
deque.push(2);
deque.push(3);
deque.delete(2);
expect(deque.toArray()).toEqual([1, 3]);
});
test('gets first and last elements', () => {
test('reverse should reverse the order of elements', () => {
deque.push(1);
deque.push(2);
deque.push(3);
expect(deque.first).toBe(1);
expect(deque.last).toBe(3);
deque.reverse();
expect(deque.toArray()).toEqual([3, 2, 1]);
});
test('handles resizing automatically', () => {
for (let i = 0; i < 12; i++) {
deque.push(i);
}
expect(deque.size).toBe(12);
// expect(deque.capacity).toBeGreaterThan(10);
});
test('converts to array', () => {
test('unique should remove duplicate elements', () => {
deque.push(1);
deque.push(2);
deque.push(2);
deque.push(3);
deque.unique();
expect(deque.toArray()).toEqual([1, 2, 3]);
});
test('clears the deque', () => {
test('sort should sort elements according to a comparator', () => {
deque.push(3);
deque.push(1);
deque.push(2);
deque.clear();
expect(deque.isEmpty()).toBe(true);
deque.sort((a, b) => a - b);
expect(deque.toArray()).toEqual([1, 2, 3]);
});
test('inserts and deletes at specific index', () => {
deque.push(1);
deque.push(3);
deque.insertAt(1, 2);
expect(deque.toArray()).toEqual([1, 2, 3]);
expect(deque.deleteAt(1)).toBe(2);
expect(deque.toArray()).toEqual([1, 3]);
test('shrinkToFit should reduce the memory footprint', () => {
});
});
describe('Deque - Utility Operations', () => {
let deque: Deque<number>;
test('finds elements with a callback', () => {
beforeEach(() => {
deque = new Deque<number>();
});
test('find should return the first element that matches the condition', () => {
deque.push(1);
deque.push(2);
deque.push(3);
expect(deque.find(el => el > 1)).toBe(2);
const found = deque.find(element => element > 1);
expect(found).toBe(2);
});
test('performs forEach operation', () => {
test('indexOf should return the index of the first occurrence of an element', () => {
deque.push(1);
deque.push(2);
let sum = 0;
deque.forEach(el => {
sum += el;
});
expect(sum).toBe(3);
deque.push(3);
const index = deque.indexOf(2);
expect(index).toBe(1);
});
test('maps to a new deque', () => {
test('toArray should convert the deque to an array', () => {
deque.push(1);
deque.push(2);
const newDeque = deque.map(el => el * el);
expect(newDeque.toArray()).toEqual([1, 4]);
deque.push(3);
expect(deque.toArray()).toEqual([1, 2, 3]);
});
test('filters elements', () => {
test('filter should filter elements based on a predicate', () => {
deque.push(1);
deque.push(2);
deque.push(3);
const newDeque = deque.filter(el => el % 2 === 0);
expect(newDeque.toArray()).toEqual([2]);
const filtered = deque.filter(element => element > 1);
expect(filtered.toArray()).toEqual([2, 3]);
});
test('reduces elements', () => {
test('map should apply a function to all elements', () => {
deque.push(1);
deque.push(2);
deque.push(3);
const sum = deque.reduce((acc, el) => acc + el, 0);
expect(sum).toBe(6);
const mapped = deque.map(element => element * 2);
expect(mapped.toArray()).toEqual([2, 4, 6]);
});
test('reverses elements', () => {
test('print should print the deque elements', () => {
const consoleSpy = jest.spyOn(console, 'log');
deque.push(1);
deque.push(2);
deque.push(3);
deque.reverse();
expect(deque.toArray()).toEqual([3, 2, 1]);
deque.print();
expect(consoleSpy).toHaveBeenCalledWith([1, 2]);
});
test('gets element at a specific index', () => {
});
describe('Deque - Additional Operations', () => {
let deque: Deque<number>;
beforeEach(() => {
deque = new Deque<number>();
});
test('addLast should add an element to the end', () => {
deque.addLast(1);
deque.addLast(2);
expect(deque.last).toBe(2);
expect(deque.size).toBe(2);
});
test('pollLast should remove and return the last element', () => {
deque.addLast(1);
deque.addLast(2);
expect(deque.pollLast()).toBe(2);
expect(deque.size).toBe(1);
});
test('addFirst should add an element to the beginning', () => {
deque.addFirst(1);
deque.addFirst(2);
expect(deque.first).toBe(2);
expect(deque.size).toBe(2);
});
test('pollFirst should remove and return the first element', () => {
deque.addFirst(1);
deque.addFirst(2);
expect(deque.pollFirst()).toBe(2);
expect(deque.size).toBe(1);
});
test('clear should reset the deque', () => {
deque.addFirst(1);
deque.clear();
expect(deque.size).toBe(0);
expect(deque.isEmpty()).toBeTruthy();
});
test('begin should yield elements from the beginning', () => {
deque.addLast(1);
deque.addLast(2);
const iterator = deque.begin();
expect(iterator.next().value).toBe(1);
expect(iterator.next().value).toBe(2);
});
test('reverseBegin should yield elements in reverse order', () => {
deque.addLast(1);
deque.addLast(2);
const iterator = deque.reverseBegin();
expect(iterator.next().value).toBe(2);
expect(iterator.next().value).toBe(1);
});
});
describe('Deque - push Method', () => {
let deque: Deque<number>;
const bucketSize = 10; // 假设的 bucket 大小
beforeEach(() => {
deque = new Deque<number>([], bucketSize);
});
test('push should add an element when deque is empty', () => {
deque.push(1);
deque.push(2);
deque.push(3);
expect(deque.getAt(1)).toBe(2);
// expect(deque.getAt(5)).toThrow();
expect(deque.last).toBe(1);
expect(deque.size).toBe(1);
});
test('finds the index of an element', () => {
test('push should add an element when lastInBucket is not at max', () => {
for (let i = 0; i < bucketSize - 1; i++) {
deque.push(i);
}
deque.push(bucketSize);
expect(deque.last).toBe(bucketSize);
expect(deque.size).toBe(bucketSize);
});
test('push should add an element and move to next bucket when last bucket is full', () => {
for (let i = 0; i < bucketSize; i++) {
deque.push(i);
}
deque.push(bucketSize + 1);
expect(deque.last).toBe(bucketSize + 1);
expect(deque.size).toBe(bucketSize + 1);
});
test('push should add an element and reallocate when last bucket and lastInBucket are at max', () => {
for (let i = 0; i < 100; i++) {
deque.push(i);
}
deque.push(100);
expect(deque.last).toBe(100);
expect(deque.size).toBeGreaterThan(bucketSize);
});
});
describe('Deque - pop Method', () => {
let deque: Deque<number>;
const bucketSize = 10;
beforeEach(() => {
deque = new Deque<number>([], bucketSize);
});
test('pop should remove and return the last element', () => {
deque.push(1);
deque.push(2);
deque.push(3);
expect(deque.indexOf(2)).toBe(1);
expect(deque.indexOf(4)).toBe(-1);
expect(deque.pop()).toBe(2);
expect(deque.size).toBe(1);
});
test('pop should handle popping the only element', () => {
deque.push(1);
expect(deque.pop()).toBe(1);
expect(deque.isEmpty()).toBeTruthy();
});
//Test begin method
describe('begin()', () => {
it('should return an iterator at the beginning of the deque', () => {
deque.push(1);
deque.push(2);
deque.push(3);
test('pop should adjust bucketLast and lastInBucket correctly', () => {
for (let i = 0; i < 100; i++) {
deque.push(i);
}
for (let i = 0; i < 1001; i++) {
const lastElement = deque.last;
expect(deque.pop()).toBe(lastElement);
}
const iterator = deque.begin();
expect(iterator.next().value).toBe(1);
});
});
});
describe('Deque - unshift Method', () => {
let deque: Deque<number>;
const bucketSize = 10;
// Test the reverse Begin method
describe('reverseBegin()', () => {
it('should return a reverse iterator at the beginning of the deque', () => {
deque.push(1);
deque.push(2);
deque.push(3);
beforeEach(() => {
deque = new Deque<number>([], bucketSize);
});
const iterator = deque.reverseBegin();
test('unshift should add an element to the beginning when deque is empty', () => {
deque.unshift(1);
expect(deque.first).toBe(1);
expect(deque.size).toBe(1);
});
expect(iterator.next().value).toBe(3);
});
test('unshift should add an element to the beginning and adjust firstInBucket', () => {
for (let i = 0; i < 100; i++) {
deque.unshift(i);
}
deque.unshift(0);
expect(deque.first).toBe(0);
});
describe('iterable methods', () => {
it('should forEach, some, every, filter, map, reduce of the deque', () => {
deque.push(1);
deque.push(2);
deque.push(3);
test('unshift should add an element and reallocate when needed', () => {
for (let i = 0; i < 100; i++) {
deque.unshift(i);
}
deque.unshift(-1);
expect(deque.first).toBe(-1);
});
});
describe('Deque - shift Method', () => {
let deque: Deque<number>;
const mockCallback = jest.fn();
deque.forEach((element) => {
mockCallback(element);
});
const bucketSize = 10;
expect(mockCallback.mock.calls.length).toBe(3);
expect(mockCallback.mock.calls[0]).toEqual([1]);
expect(mockCallback.mock.calls[1]).toEqual([2]);
expect(mockCallback.mock.calls[2]).toEqual([3]);
beforeEach(() => {
deque = new Deque<number>([], bucketSize);
});
expect(deque.every(element => element > 0)).toBe(true);
expect(deque.every(element => element > 1)).toBe(false);
expect(deque.some(element => element > 2)).toBe(true);
test('shift should remove and return the first element', () => {
deque.push(1);
deque.push(2);
expect(deque.shift()).toBe(1);
expect(deque.size).toBe(1);
});
expect([...deque.filter(element => element > 2)]).toEqual([3]);
expect([...deque.map(element => element * 2)]).toEqual([2, 4, 6]);
expect(deque.reduce((accumulator, element) => accumulator + element, 0)).toEqual(6);
});
test('shift should handle shifting the only element', () => {
deque.push(1);
expect(deque.shift()).toBe(1);
expect(deque.isEmpty()).toBeTruthy();
});
test('shift should adjust bucketFirst and firstInBucket correctly', () => {
for (let i = 0; i < 100; i++) {
deque.push(i);
}
for (let i = 0; i < 100; i++) {
const firstElement = deque.first;
expect(deque.shift()).toBe(firstElement);
}
});
});

316

test/unit/data-structures/queue/queue.test.ts
import { LinkedListQueue, Queue } from '../../../../src';
import { bigO } from '../../../utils';
import { isDebugTest } from '../../../config';
const isDebug = isDebugTest;
describe('Queue Operation Test', () => {
it('should validate a queue', () => {
const queue = new Queue<number>();
for (let i = 0; i < 1000; i++) {
queue.enqueue(i);
}
let last: number | undefined = 0;
for (let i = 0; i < 1000; i++) {
last = queue.dequeue();
}
expect(last).toBe(999);
});
});

@@ -27,15 +13,84 @@ describe('Queue', () => {

it('should initialize an empty queue', () => {
test('new Queue() should create an empty queue', () => {
expect(queue.size).toBe(0);
expect(queue.isEmpty()).toBeTruthy();
});
it('should push elements to the end of the queue', () => {
test('push should add elements to the queue', () => {
queue.push(1);
queue.push(2);
expect(queue.size).toBe(2);
});
test('shift should remove the first element', () => {
queue.push(1);
queue.enqueue(2);
expect(queue.shift()).toBe(1);
expect(queue.size).toBe(1);
});
test('shift should return undefined if queue is empty', () => {
expect(queue.dequeue()).toBeUndefined();
});
test('peek should return the first element without removing it', () => {
queue.push(1);
queue.push(2);
expect(queue.peek()).toBe(1);
expect(queue.size).toBe(2);
});
test('peek should return undefined if queue is empty', () => {
expect(queue.peek()).toBeUndefined();
});
test('size should return the number of elements', () => {
queue.push(1);
queue.push(2);
expect(queue.size).toBe(2);
});
test('isEmpty should return true if the queue is empty', () => {
expect(queue.isEmpty()).toBeTruthy();
});
test('isEmpty should return false if the queue is not empty', () => {
queue.push(1);
expect(queue.isEmpty()).toBeFalsy();
});
test('toArray should return an array of queue elements', () => {
queue.push(1);
queue.push(2);
expect(queue.toArray()).toEqual([1, 2]);
});
test('clear should remove all elements from the queue', () => {
queue.push(1);
queue.push(2);
queue.clear();
expect(queue.size).toBe(0);
});
test('forEach should iterate over all elements', () => {
const arr: number[] = [];
queue.push(1);
queue.push(2);
queue.forEach(element => arr.push(element));
expect(arr).toEqual([1, 2]);
});
// Boundary value testing
test('push and shift with many elements', () => {
for (let i = 0; i < 1000; i++) {
queue.push(i);
}
for (let i = 0; i < 1000; i++) {
expect(queue.shift()).toBe(i);
}
expect(queue.isEmpty()).toBeTruthy();
});
});
describe('Queue', () => {
describe('Queue - Advanced Methods', () => {
let queue: Queue<number>;

@@ -47,94 +102,117 @@

it('should initialize an empty queue', () => {
expect(queue.size).toBe(0);
expect(queue.isEmpty()).toBe(true);
test('reduce should apply a function against an accumulator and each element', () => {
queue.push(1);
queue.push(2);
queue.push(3);
const sum = queue.reduce((acc, val) => acc + val, 0);
expect(sum).toBe(6);
});
it('should push elements to the end of the queue', () => {
test('reduce should return initial value for empty queue', () => {
const initialValue = 0;
const sum = queue.reduce((acc, val) => acc + val, initialValue);
expect(sum).toBe(initialValue);
});
test('filter should return a new queue with all elements that pass the test implemented by provided function', () => {
queue.push(1);
queue.push(2);
expect(queue.size).toBe(2);
expect(queue.peek()).toBe(1);
expect(queue.getLast()).toBe(2);
queue.push(3);
const filteredQueue = queue.filter(val => val > 1);
expect(filteredQueue.toArray()).toEqual([2, 3]);
});
it('should shift elements from the front of the queue', () => {
test('filter should return an empty queue for empty queue', () => {
const filteredQueue = queue.filter(val => val > 1);
expect(filteredQueue.isEmpty()).toBeTruthy();
});
test('map should create a new queue with the results of calling a provided function on every element', () => {
queue.push(1);
queue.push(2);
const shifted = queue.shift();
expect(shifted).toBe(1);
expect(queue.size).toBe(1);
expect(queue.peek()).toBe(2);
expect(queue.getLast()).toBe(2);
queue.push(3);
const mappedQueue = queue.map(val => val * 2);
expect(mappedQueue.toArray()).toEqual([2, 4, 6]);
});
it('should handle shifting when queue reaches half size', () => {
for (let i = 1; i <= 5; i++) {
queue.push(i);
}
for (let i = 1; i <= 3; i++) {
queue.shift();
}
// Queue size should be 2, but internal array size is still 5.
// Test that shifting optimizes the internal array.
test('map should return an empty queue for empty queue', () => {
const mappedQueue = queue.map(val => val * 2);
expect(mappedQueue.isEmpty()).toBeTruthy();
});
});
describe('Queue - Additional Methods', () => {
let queue: Queue<number>;
beforeEach(() => {
queue = new Queue<number>();
});
test('peekLast should return the last element without removing it', () => {
queue.push(1);
queue.push(2);
expect(queue.peekLast()).toBe(2);
expect(queue.size).toBe(2);
expect(queue.nodes.length).toBe(2);
expect(queue.peek()).toBe(4);
});
it('should peek at the front and end of the queue', () => {
test('peekLast should return undefined if queue is empty', () => {
expect(queue.peekLast()).toBeUndefined();
});
test('getAt should return the element at the specified index', () => {
queue.push(1);
queue.push(2);
expect(queue.peek()).toBe(1);
expect(queue.getLast()).toBe(2);
queue.push(3);
expect(queue.getAt(1)).toBe(2);
});
it('should handle shifting when the queue is empty', () => {
const shifted = queue.shift();
expect(shifted).toBeUndefined();
expect(queue.size).toBe(0);
expect(queue.peek()).toBeUndefined();
test('getAt should return undefined for an invalid index', () => {
queue.push(1);
expect(queue.getAt(3)).toBeUndefined();
expect(queue.getAt(-1)).toBeUndefined();
});
it('should handle peeking when the queue is empty', () => {
expect(queue.peek()).toBeUndefined();
expect(queue.getLast()).toBeUndefined();
test('print should not throw any errors', () => {
expect(() => {
queue.push(1);
queue.print();
}).not.toThrow();
});
});
it('should handle clearing the queue', () => {
for (let i = 1; i <= 3; i++) {
queue.push(i);
}
queue.clear();
expect(queue.size).toBe(0);
expect(queue.peek()).toBeUndefined();
expect(queue.getLast()).toBeUndefined();
describe('Queue - Static and Clone Methods', () => {
test('fromArray should create a new queue from an array', () => {
const array = [1, 2, 3];
const queue = Queue.fromArray(array);
expect(queue.toArray()).toEqual(array);
expect(queue.size).toBe(array.length);
});
it('should clone the queue', () => {
for (let i = 1; i <= 3; i++) {
queue.push(i);
}
const clonedQueue = queue.clone();
expect(clonedQueue.size).toBe(3);
expect(clonedQueue.peek()).toBe(1);
expect(clonedQueue.getLast()).toBe(3);
test('fromArray should create an empty queue from an empty array', () => {
const queue = Queue.fromArray([]);
expect(queue.isEmpty()).toBeTruthy();
});
it('should handle creating a queue from an array', () => {
const elements = [1, 2, 3, 4, 5];
const newQueue = Queue.fromArray(elements);
expect(newQueue.size).toBe(5);
expect(newQueue.peek()).toBe(1);
expect(newQueue.getLast()).toBe(5);
test('clone should create a new queue with the same elements', () => {
const originalQueue = new Queue<number>();
originalQueue.push(1);
originalQueue.push(2);
const clonedQueue = originalQueue.clone();
expect(clonedQueue.toArray()).toEqual(originalQueue.toArray());
expect(clonedQueue.size).toBe(originalQueue.size);
});
it('should iterate through the queue', () => {
for (let i = 1; i <= 3; i++) {
queue.push(i);
}
const values = Array.from(queue);
expect(values).toEqual([1, 2, 3]);
test('clone should not affect the original queue when mutated', () => {
const originalQueue = new Queue<number>();
originalQueue.push(1);
originalQueue.push(2);
const clonedQueue = originalQueue.clone();
clonedQueue.push(3);
expect(clonedQueue.size).not.toBe(originalQueue.size);
expect(originalQueue.toArray()).not.toContain(3);
});
});
describe('LinkedListQueue', () => {

@@ -168,80 +246,2 @@ let queue: LinkedListQueue<string>;

});
});
describe('Queue Performance Test', () => {
const dataSize = 10000;
it('should numeric queue be efficient', function () {
const startTime = performance.now();
const queue = new Queue<number>();
for (let i = 0; i < dataSize; i++) {
queue.enqueue(i);
}
for (let i = 0; i < dataSize; i++) {
queue.dequeue();
}
isDebug && console.log(`Queue Performance Test: ${performance.now() - startTime} ms`);
expect(performance.now() - startTime).toBeLessThan(bigO.LINEAR * 100);
});
it('should numeric Array be more efficient than Queue when the data size is 10000', function () {
const startTime2 = performance.now();
const queue2: number[] = [];
for (let i = 0; i < dataSize; i++) {
queue2.push(i);
}
for (let i = 0; i < dataSize; i++) {
queue2.shift();
}
expect(performance.now() - startTime2).toBeLessThan(bigO.CUBED * 100);
});
it('should numeric LinkedListQueue be efficient', function () {
const startTime = performance.now();
const queue = new LinkedListQueue<number>();
for (let i = 0; i < dataSize; i++) {
queue.enqueue(i);
}
for (let i = 0; i < dataSize; i++) {
queue.dequeue();
}
// console.log(`LinkedListQueue Performance Test: ${performance.now() - startTime} ms`);
expect(performance.now() - startTime).toBeLessThan(bigO.LINEAR * 100);
});
});
describe('Queue iterative methods', () => {
let queue: Queue<number>;
beforeEach(() => {
queue = new Queue();
for (let i = 0; i < 10; i++) {
queue.enqueue(i);
}
});
test('iterator should provide access to all elements', () => {
const elements = [];
for (const item of queue) {
elements.push(item);
}
expect(elements).toEqual([0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
});
test('forEach should apply the callback to each element', () => {
const elements: number[] = [];
queue.forEach((element) => elements.push(element * 2));
expect(elements).toEqual([0, 2, 4, 6, 8, 10, 12, 14, 16, 18]);
});
test('filter should return a new queue with only the elements that satisfy the predicate', () => {
const filteredQueue = queue.filter(element => element % 2 === 0);
expect([...filteredQueue]).toEqual([0, 2, 4, 6, 8]);
});
test('map should return a new queue with the transformed elements', () => {
const mappedQueue = queue.map(element => element * 2);
expect([...mappedQueue]).toEqual([0, 2, 4, 6, 8, 10, 12, 14, 16, 18]);
});
});
benchmark/report.html

Sorry, the diff of this file is not supported yet

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

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

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

Sorry, the diff of this file is not supported yet

dist/cjs/data-structures/queue/deque.js.map

Sorry, the diff of this file is not supported yet

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

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

dist/umd/data-structure-typed.js

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

dist/umd/data-structure-typed.min.js

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

dist/umd/data-structure-typed.min.js.map

Sorry, the diff of this file is not supported yet

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

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

SocketSocket SOC 2 Logo

Product

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

About

Packages

npm

Go

Maven

PyPI

Rubygems

Stay in touch

Get open source security insights delivered straight into your inbox.

  • Terms
  • Privacy
  • Security

Made with ⚡️ by Socket Inc