Socket
Socket
Sign inDemoInstall

directed-graph-typed

Package Overview
Dependencies
Maintainers
1
Versions
147
Alerts
File Explorer

Advanced tools

License
Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

directed-graph-typed - npm Package Compare versions

Comparing version 1.45.3 to 1.46.1

11

dist/data-structures/hash/hash-map.d.ts

@@ -8,3 +8,3 @@ /**

*/
import { HashMapLinkedNode, HashMapOptions, IterateDirection } from '../../types';
import { HashMapLinkedNode, IterableWithSizeOrLength, IterateDirection } from '../../types';
/**

@@ -49,2 +49,3 @@ * Because the implementation of HashMap relies on JavaScript's built-in objects and arrays,

next(): this;
clone(): HashMapIterator<K, V>;
}

@@ -60,7 +61,7 @@ export declare class HashMap<K = any, V = any> {

* The constructor initializes a HashMap object with an optional initial set of key-value pairs.
* @param hashMap - The `hashMap` parameter is an optional parameter of type `HashMapOptions<[K,
* @param {Iterable<[K, V]>} elements - The `hashMap` parameter is an optional parameter of type `HashMapOptions<[K,
* V]>`. It is an array of key-value pairs, where each pair is represented as an array `[K, V]`. The
* `K` represents the type of the key and `V` represents the
*/
constructor(hashMap?: HashMapOptions<[K, V]>);
constructor(elements?: IterableWithSizeOrLength<[K, V]>);
protected _size: number;

@@ -111,3 +112,3 @@ get size(): number;

*/
get front(): [K, V] | undefined;
get first(): [K, V] | undefined;
/**

@@ -121,3 +122,3 @@ * Time Complexity: O(1)

*/
get back(): [K, V] | undefined;
get last(): [K, V] | undefined;
/**

@@ -124,0 +125,0 @@ * Time Complexity: O(1)

15

dist/data-structures/hash/hash-map.js

@@ -112,2 +112,5 @@ "use strict";

}
clone() {
return new HashMapIterator(this._node, this._sentinel, this.hashMap, this.iterateDirection);
}
}

@@ -118,7 +121,7 @@ exports.HashMapIterator = HashMapIterator;

* The constructor initializes a HashMap object with an optional initial set of key-value pairs.
* @param hashMap - The `hashMap` parameter is an optional parameter of type `HashMapOptions<[K,
* @param {Iterable<[K, V]>} elements - The `hashMap` parameter is an optional parameter of type `HashMapOptions<[K,
* V]>`. It is an array of key-value pairs, where each pair is represented as an array `[K, V]`. The
* `K` represents the type of the key and `V` represents the
*/
constructor(hashMap = []) {
constructor(elements = []) {
this.OBJ_KEY_INDEX = Symbol('OBJ_KEY_INDEX');

@@ -131,5 +134,5 @@ this._nodes = [];

this._sentinel.prev = this._sentinel.next = this._head = this._tail = this._sentinel;
hashMap.forEach(el => {
for (const el of elements) {
this.set(el[0], el[1]);
});
}
}

@@ -190,3 +193,3 @@ get size() {

*/
get front() {
get first() {
if (this._size === 0)

@@ -204,3 +207,3 @@ return;

*/
get back() {
get last() {
if (this._size === 0)

@@ -207,0 +210,0 @@ return;

106

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

@@ -11,6 +11,6 @@ /**

comparator: Comparator<E>;
nodes?: E[];
elements?: E[];
});
protected _nodes: E[];
get nodes(): E[];
protected _elements: E[];
get elements(): E[];
protected _comparator: Comparator<E>;

@@ -28,3 +28,3 @@ get comparator(): Comparator<E>;

/**
* Static method that creates a binary heap from an array of nodes and a comparison function.
* Static method that creates a binary heap from an array of elements and a comparison function.
* @returns A new Heap instance.

@@ -34,11 +34,11 @@ * @param options

static heapify<E>(options: {
nodes: E[];
elements: E[];
comparator: Comparator<E>;
}): Heap<E>;
/**
* Time Complexity: O(log n), where n is the number of nodes in the heap.
* Time Complexity: O(log n), where n is the number of elements in the heap.
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(log n), where n is the number of nodes in the heap.
* Time Complexity: O(log n), where n is the number of elements in the heap.
* Space Complexity: O(1)

@@ -51,7 +51,7 @@ *

/**
* Time Complexity: O(log n), where n is the number of nodes in the heap.
* Time Complexity: O(log n), where n is the number of elements in the heap.
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(log n), where n is the number of nodes in the heap.
* Time Complexity: O(log n), where n is the number of elements in the heap.
* Space Complexity: O(1)

@@ -64,7 +64,7 @@ *

/**
* Time Complexity: O(log n), where n is the number of nodes in the heap.
* Time Complexity: O(log n), where n is the number of elements in the heap.
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(log n), where n is the number of nodes in the heap.
* Time Complexity: O(log n), where n is the number of elements in the heap.
* Space Complexity: O(1)

@@ -77,7 +77,7 @@ *

/**
* Time Complexity: O(log n), where n is the number of nodes in the heap.
* Time Complexity: O(log n), where n is the number of elements in the heap.
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(log n), where n is the number of nodes in the heap.
* Time Complexity: O(log n), where n is the number of elements in the heap.
* Space Complexity: O(1)

@@ -100,23 +100,23 @@ *

/**
* Reset the nodes of the heap. Make the nodes empty.
* Reset the elements of the heap. Make the elements empty.
*/
clear(): void;
/**
* Time Complexity: O(n), where n is the number of elements in the nodes array.
* Time Complexity: O(n), where n is the number of elements in the elements array.
* Space Complexity: O(n)
*/
/**
* Time Complexity: O(n), where n is the number of elements in the nodes array.
* Time Complexity: O(n), where n is the number of elements in the elements array.
* Space Complexity: O(n)
*
* Clear and add nodes of the heap
* @param nodes
* Clear and add elements of the heap
* @param elements
*/
refill(nodes: E[]): void;
refill(elements: E[]): void;
/**
* Time Complexity: O(n), where n is the number of nodes in the heap.
* Time Complexity: O(n), where n is the number of elements in the heap.
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(n), where n is the number of nodes in the heap.
* Time Complexity: O(n), where n is the number of elements in the heap.
* Space Complexity: O(1)

@@ -130,7 +130,23 @@ *

/**
* Time Complexity: O(n), where n is the number of nodes in the heap.
* Time Complexity: O(n). The worst-case O(n), where n is the number of elements in the heap. This is because, in the worst case, the element to be deleted is located at the end of the heap (not the root), and after deletion, we may need to reorganize the elements by performing a sinkDown operation.
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(n). The worst-case O(n), where n is the number of elements in the heap. This is because, in the worst case, the element to be deleted is located at the end of the heap (not the root), and after deletion, we may need to reorganize the elements by performing a sinkDown operation.
* Space Complexity: O(1)
*
* The `delete` function removes an element from an array-like data structure, maintaining the order
* and structure of the remaining elements.
* @param {E} element - The `element` parameter represents the element that you want to delete from
* the array `this.elements`.
* @returns The `delete` function is returning a boolean value. It returns `true` if the element was
* successfully deleted from the array, and `false` if the element was not found in the array.
*/
delete(element: E): boolean;
/**
* Time Complexity: O(n), where n is the number of elements in the heap.
* Space Complexity: O(h), where h is the height of the heap.
*/
/**
* Time Complexity: O(n), where n is the number of nodes in the heap.
* Time Complexity: O(n), where n is the number of elements in the heap.
* Space Complexity: O(h), where h is the height of the heap.

@@ -156,7 +172,2 @@ *

/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*/
getNodes(): E[];
/**
* Time Complexity: O(n)

@@ -190,9 +201,8 @@ * Space Complexity: O(n)

/**
* Time Complexity: O(log n)
* Time Complexity: O(n)
* Space Complexity: O(1)
*
* Float operation to maintain heap properties after adding an element.
* @param index - The index of the newly added element.
* Fix the entire heap to maintain heap properties.
*/
protected bubbleUp(index: number): void;
fix(): void;
/**

@@ -206,6 +216,6 @@ * Time Complexity: O(log n)

*
* Sinking operation to maintain heap properties after removing the top element.
* @param index - The index from which to start sinking.
* Float operation to maintain heap properties after adding an element.
* @param index - The index of the newly added element.
*/
protected sinkDown(index: number): void;
protected _bubbleUp(index: number): void;
/**

@@ -216,8 +226,10 @@ * Time Complexity: O(n)

/**
* Time Complexity: O(n)
* Time Complexity: O(log n)
* Space Complexity: O(1)
*
* Fix the entire heap to maintain heap properties.
* Sinking operation to maintain heap properties after removing the top element.
* @param index - The index from which to start sinking.
* @param halfLength
*/
protected fix(): void;
protected _sinkDown(index: number, halfLength: number): void;
}

@@ -289,7 +301,7 @@ export declare class FibonacciHeapNode<E> {

/**
* Time Complexity: O(n), where n is the number of nodes in the linked list.
* Time Complexity: O(n), where n is the number of elements in the linked list.
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(n), where n is the number of nodes in the linked list.
* Time Complexity: O(n), where n is the number of elements in the linked list.
* Space Complexity: O(1)

@@ -300,3 +312,3 @@ *

* @protected
* @returns FibonacciHeapNode<E>[] - An array containing the nodes of the linked list.
* @returns FibonacciHeapNode<E>[] - An array containing the elements of the linked list.
*/

@@ -313,7 +325,7 @@ consumeLinkedList(head?: FibonacciHeapNode<E>): FibonacciHeapNode<E>[];

/**
* Time Complexity: O(log n), where n is the number of nodes in the heap.
* Time Complexity: O(log n), where n is the number of elements in the heap.
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(log n), where n is the number of nodes in the heap.
* Time Complexity: O(log n), where n is the number of elements in the heap.
* Space Complexity: O(1)

@@ -326,7 +338,7 @@ *

/**
* Time Complexity: O(log n), where n is the number of nodes in the heap.
* Time Complexity: O(log n), where n is the number of elements in the heap.
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(log n), where n is the number of nodes in the heap.
* Time Complexity: O(log n), where n is the number of elements in the heap.
* Space Complexity: O(1)

@@ -403,7 +415,7 @@ *

/**
* Time Complexity: O(n log n), where n is the number of nodes in the heap.
* Time Complexity: O(n log n), where n is the number of elements in the heap.
* Space Complexity: O(n)
*/
/**
* Time Complexity: O(n log n), where n is the number of nodes in the heap.
* Time Complexity: O(n log n), where n is the number of elements in the heap.
* Space Complexity: O(n)

@@ -410,0 +422,0 @@ *

254

dist/data-structures/heap/heap.js

@@ -12,11 +12,11 @@ "use strict";

constructor(options) {
this._nodes = [];
this._elements = [];
this._comparator = options.comparator;
if (options.nodes && options.nodes.length > 0) {
this._nodes = options.nodes;
if (options.elements && options.elements.length > 0) {
this._elements = options.elements;
this.fix();
}
}
get nodes() {
return this._nodes;
get elements() {
return this._elements;
}

@@ -30,3 +30,3 @@ get comparator() {

get size() {
return this.nodes.length;
return this.elements.length;
}

@@ -39,6 +39,6 @@ /**

var _a;
return (_a = this.nodes[this.size - 1]) !== null && _a !== void 0 ? _a : undefined;
return (_a = this.elements[this.size - 1]) !== null && _a !== void 0 ? _a : undefined;
}
/**
* Static method that creates a binary heap from an array of nodes and a comparison function.
* Static method that creates a binary heap from an array of elements and a comparison function.
* @returns A new Heap instance.

@@ -51,7 +51,7 @@ * @param options

/**
* Time Complexity: O(log n), where n is the number of nodes in the heap.
* Time Complexity: O(log n), where n is the number of elements in the heap.
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(log n), where n is the number of nodes in the heap.
* Time Complexity: O(log n), where n is the number of elements in the heap.
* Space Complexity: O(1)

@@ -66,7 +66,7 @@ *

/**
* Time Complexity: O(log n), where n is the number of nodes in the heap.
* Time Complexity: O(log n), where n is the number of elements in the heap.
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(log n), where n is the number of nodes in the heap.
* Time Complexity: O(log n), where n is the number of elements in the heap.
* Space Complexity: O(1)

@@ -78,12 +78,12 @@ *

push(element) {
this.nodes.push(element);
this.bubbleUp(this.nodes.length - 1);
this._elements.push(element);
this._bubbleUp(this.elements.length - 1);
return this;
}
/**
* Time Complexity: O(log n), where n is the number of nodes in the heap.
* Time Complexity: O(log n), where n is the number of elements in the heap.
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(log n), where n is the number of nodes in the heap.
* Time Complexity: O(log n), where n is the number of elements in the heap.
* Space Complexity: O(1)

@@ -95,19 +95,18 @@ *

poll() {
if (this.nodes.length === 0) {
return undefined;
if (this.elements.length === 0)
return;
const value = this.elements[0];
const last = this.elements.pop();
if (this.elements.length) {
this.elements[0] = last;
this._sinkDown(0, this.elements.length >> 1);
}
if (this.nodes.length === 1) {
return this.nodes.pop();
}
const topValue = this.nodes[0];
this.nodes[0] = this.nodes.pop();
this.sinkDown(0);
return topValue;
return value;
}
/**
* Time Complexity: O(log n), where n is the number of nodes in the heap.
* Time Complexity: O(log n), where n is the number of elements in the heap.
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(log n), where n is the number of nodes in the heap.
* Time Complexity: O(log n), where n is the number of elements in the heap.
* Space Complexity: O(1)

@@ -126,6 +125,3 @@ *

peek() {
if (this.nodes.length === 0) {
return undefined;
}
return this.nodes[0];
return this.elements[0];
}

@@ -140,28 +136,28 @@ /**

/**
* Reset the nodes of the heap. Make the nodes empty.
* Reset the elements of the heap. Make the elements empty.
*/
clear() {
this._nodes = [];
this._elements = [];
}
/**
* Time Complexity: O(n), where n is the number of elements in the nodes array.
* Time Complexity: O(n), where n is the number of elements in the elements array.
* Space Complexity: O(n)
*/
/**
* Time Complexity: O(n), where n is the number of elements in the nodes array.
* Time Complexity: O(n), where n is the number of elements in the elements array.
* Space Complexity: O(n)
*
* Clear and add nodes of the heap
* @param nodes
* Clear and add elements of the heap
* @param elements
*/
refill(nodes) {
this._nodes = nodes;
refill(elements) {
this._elements = elements;
this.fix();
}
/**
* Time Complexity: O(n), where n is the number of nodes in the heap.
* Time Complexity: O(n), where n is the number of elements in the heap.
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(n), where n is the number of nodes in the heap.
* Time Complexity: O(n), where n is the number of elements in the heap.
* Space Complexity: O(1)

@@ -174,10 +170,42 @@ *

has(element) {
return this.nodes.includes(element);
return this.elements.includes(element);
}
/**
* Time Complexity: O(n), where n is the number of nodes in the heap.
* Time Complexity: O(n). The worst-case O(n), where n is the number of elements in the heap. This is because, in the worst case, the element to be deleted is located at the end of the heap (not the root), and after deletion, we may need to reorganize the elements by performing a sinkDown operation.
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(n). The worst-case O(n), where n is the number of elements in the heap. This is because, in the worst case, the element to be deleted is located at the end of the heap (not the root), and after deletion, we may need to reorganize the elements by performing a sinkDown operation.
* Space Complexity: O(1)
*
* The `delete` function removes an element from an array-like data structure, maintaining the order
* and structure of the remaining elements.
* @param {E} element - The `element` parameter represents the element that you want to delete from
* the array `this.elements`.
* @returns The `delete` function is returning a boolean value. It returns `true` if the element was
* successfully deleted from the array, and `false` if the element was not found in the array.
*/
delete(element) {
const index = this.elements.indexOf(element);
if (index < 0)
return false;
if (index === 0) {
this.pop();
}
else if (index === this.elements.length - 1) {
this.elements.pop();
}
else {
this.elements.splice(index, 1, this.elements.pop());
this._bubbleUp(index);
this._sinkDown(index, this.elements.length >> 1);
}
return true;
}
/**
* Time Complexity: O(n), where n is the number of elements in the heap.
* Space Complexity: O(h), where h is the height of the heap.
*/
/**
* Time Complexity: O(n), where n is the number of nodes in the heap.
* Time Complexity: O(n), where n is the number of elements in the heap.
* Space Complexity: O(h), where h is the height of the heap.

@@ -196,7 +224,7 @@ *

dfsHelper(2 * index + 1);
result.push(this.nodes[index]);
result.push(this.elements[index]);
dfsHelper(2 * index + 2);
}
else if (order === 'pre') {
result.push(this.nodes[index]);
result.push(this.elements[index]);
dfsHelper(2 * index + 1);

@@ -208,3 +236,3 @@ dfsHelper(2 * index + 2);

dfsHelper(2 * index + 2);
result.push(this.nodes[index]);
result.push(this.elements[index]);
}

@@ -228,12 +256,5 @@ }

toArray() {
return [...this.nodes];
return [...this.elements];
}
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*/
getNodes() {
return this.nodes;
}
/**
* Time Complexity: O(n)

@@ -251,3 +272,3 @@ * Space Complexity: O(n)

const clonedHeap = new Heap({ comparator: this.comparator });
clonedHeap._nodes = [...this.nodes];
clonedHeap._elements = [...this.elements];
return clonedHeap;

@@ -281,4 +302,18 @@ }

/**
* Time Complexity: O(n)
* Space Complexity: O(1)
*
* Fix the entire heap to maintain heap properties.
*/
fix() {
for (let i = Math.floor(this.size / 2); i >= 0; i--)
this._sinkDown(i, this.elements.length >> 1);
}
/**
* Time Complexity: O(log n)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(log n)
* Space Complexity: O(1)
*

@@ -288,28 +323,16 @@ * Float operation to maintain heap properties after adding an element.

*/
bubbleUp(index) {
// const element = this.nodes[index];
// while (index > 0) {
// const parentIndex = (index - 1) >> 1;
// const parent = this.nodes[parentIndex];
// if (this.comparator(element, parent) < 0) {
// this.nodes[index] = parent;
// this.nodes[parentIndex] = element;
// index = parentIndex;
// } else {
// break;
// }
// }
const item = this.nodes[index];
_bubbleUp(index) {
const element = this.elements[index];
while (index > 0) {
const parent = (index - 1) >> 1;
const parentItem = this.nodes[parent];
if (this.comparator(parentItem, item) <= 0)
const parentItem = this.elements[parent];
if (this._comparator(parentItem, element) <= 0)
break;
this.nodes[index] = parentItem;
this.elements[index] = parentItem;
index = parent;
}
this.nodes[index] = item;
this.elements[index] = element;
}
/**
* Time Complexity: O(log n)
* Time Complexity: O(n)
* Space Complexity: O(1)

@@ -323,35 +346,22 @@ */

* @param index - The index from which to start sinking.
* @param halfLength
*/
sinkDown(index) {
const leftChildIndex = index << 1 | 1;
const rightChildIndex = leftChildIndex + 1;
const length = this.nodes.length;
let targetIndex = index;
if (leftChildIndex < length && this.comparator(this.nodes[leftChildIndex], this.nodes[targetIndex]) < 0) {
targetIndex = leftChildIndex;
_sinkDown(index, halfLength) {
const element = this.elements[index];
while (index < halfLength) {
let left = index << 1 | 1;
const right = left + 1;
let minItem = this.elements[left];
if (right < this.elements.length &&
this._comparator(minItem, this.elements[right]) > 0) {
left = right;
minItem = this.elements[right];
}
if (this._comparator(minItem, element) >= 0)
break;
this.elements[index] = minItem;
index = left;
}
if (rightChildIndex < length && this.comparator(this.nodes[rightChildIndex], this.nodes[targetIndex]) < 0) {
targetIndex = rightChildIndex;
}
if (targetIndex !== index) {
const temp = this.nodes[index];
this.nodes[index] = this.nodes[targetIndex];
this.nodes[targetIndex] = temp;
this.sinkDown(targetIndex);
}
this.elements[index] = element;
}
/**
* Time Complexity: O(n)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(n)
* Space Complexity: O(1)
*
* Fix the entire heap to maintain heap properties.
*/
fix() {
for (let i = Math.floor(this.size / 2); i >= 0; i--)
this.sinkDown(i);
}
}

@@ -451,7 +461,7 @@ exports.Heap = Heap;

/**
* Time Complexity: O(n), where n is the number of nodes in the linked list.
* Time Complexity: O(n), where n is the number of elements in the linked list.
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(n), where n is the number of nodes in the linked list.
* Time Complexity: O(n), where n is the number of elements in the linked list.
* Space Complexity: O(1)

@@ -462,8 +472,8 @@ *

* @protected
* @returns FibonacciHeapNode<E>[] - An array containing the nodes of the linked list.
* @returns FibonacciHeapNode<E>[] - An array containing the elements of the linked list.
*/
consumeLinkedList(head) {
const nodes = [];
const elements = [];
if (!head)
return nodes;
return elements;
let node = head;

@@ -477,7 +487,7 @@ let flag = false;

if (node) {
nodes.push(node);
elements.push(node);
node = node.right;
}
}
return nodes;
return elements;
}

@@ -503,7 +513,7 @@ /**

/**
* Time Complexity: O(log n), where n is the number of nodes in the heap.
* Time Complexity: O(log n), where n is the number of elements in the heap.
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(log n), where n is the number of nodes in the heap.
* Time Complexity: O(log n), where n is the number of elements in the heap.
* Space Complexity: O(1)

@@ -518,7 +528,7 @@ *

/**
* Time Complexity: O(log n), where n is the number of nodes in the heap.
* Time Complexity: O(log n), where n is the number of elements in the heap.
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(log n), where n is the number of nodes in the heap.
* Time Complexity: O(log n), where n is the number of elements in the heap.
* Space Complexity: O(1)

@@ -534,4 +544,4 @@ *

if (z.child) {
const nodes = this.consumeLinkedList(z.child);
for (const node of nodes) {
const elements = this.consumeLinkedList(z.child);
for (const node of elements) {
this.mergeWithRoot(node);

@@ -673,7 +683,7 @@ node.parent = undefined;

/**
* Time Complexity: O(n log n), where n is the number of nodes in the heap.
* Time Complexity: O(n log n), where n is the number of elements in the heap.
* Space Complexity: O(n)
*/
/**
* Time Complexity: O(n log n), where n is the number of nodes in the heap.
* Time Complexity: O(n log n), where n is the number of elements in the heap.
* Space Complexity: O(n)

@@ -686,5 +696,5 @@ *

const A = new Array(this.size);
const nodes = this.consumeLinkedList(this.root);
const elements = this.consumeLinkedList(this.root);
let x, y, d, t;
for (const node of nodes) {
for (const node of elements) {
x = node;

@@ -691,0 +701,0 @@ d = x.degree;

295

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

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

*/
import { DoublyLinkedList } from '../linked-list';
export declare class Deque<E = any> extends DoublyLinkedList<E> {
import { IterableWithSizeOrLength, IterateDirection } from "../../types";
/**
* Deque can provide random access with O(1) time complexity
* Deque is usually more compact and efficient in memory usage because it does not require additional space to store pointers.
* Deque may experience performance jitter, but DoublyLinkedList will not
* Deque is implemented using a dynamic array. Inserting or deleting beyond both ends of the array may require moving elements or reallocating space.
*/
export declare class DequeIterator<E> {
iterateDirection: IterateDirection;
index: number;
readonly deque: Deque<E>;
constructor(index: number, deque: Deque<E>, iterateDirection?: IterateDirection);
get current(): E;
set current(newElement: E);
isAccessible(): boolean;
prev(): DequeIterator<E>;
next(): DequeIterator<E>;
clone(): DequeIterator<E>;
}
export declare class Deque<E> {
protected _bucketFirst: number;
protected _firstInBucket: number;
protected _bucketLast: number;
protected _lastInBucket: number;
protected _bucketCount: number;
protected readonly _bucketSize: number;
constructor(elements?: IterableWithSizeOrLength<E>, bucketSize?: number);
protected _buckets: E[][];
get buckets(): E[][];
protected _size: number;
get size(): number;
get first(): E | undefined;
get last(): E | undefined;
/**
* Time Complexity: Amortized O(1) - Generally constant time, but resizing when the deque is full leads to O(n).
* Space Complexity: O(n) - In worst case, resizing doubles the array size.
*/
empty(): boolean;
/**
* Time Complexity: O(1) - Removes the last element.
* Space Complexity: O(1) - Operates in-place.
*/
isEmpty(): boolean;
/**
* Time Complexity: Amortized O(1) - Similar to push, resizing leads to O(n).
* Space Complexity: O(n) - Due to potential resizing.
*/
/**
* Time Complexity: O(1)
* Space Complexity: O(n) - In worst case, resizing doubles the array size.
*
* The addLast function adds an element to the end of an array.
* @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) - Removes the first element.
* Space Complexity: O(1) - In-place operation.
*/
/**
* Time Complexity: O(1) - Removes the last element.
* Space Complexity: O(1) - Operates in-place.
*
* The function "popLast" removes and returns the last element of an array.
* @returns The last element of the array is being returned.
*/
popLast(): E | undefined;
/**
* Time Complexity: O(1).
* Space Complexity: O(n) - Due to potential resizing.
*
* The "addFirst" function adds an element to the beginning of an array.
* @param {E} element - The parameter "element" represents the element that you want to add to the
* beginning of the data structure.
*/
addFirst(element: E): void;
/**
* Time Complexity: O(1) - Removes the first element.
* Space Complexity: O(1) - In-place operation.
*
* The function "popFirst" removes and returns the first element of an array.
* @returns The method `popFirst()` is returning the first element of the array after removing it
* from the beginning. If the array is empty, it will return `undefined`.
*/
popFirst(): E | undefined;
clear(): void;
begin(): DequeIterator<E>;
end(): DequeIterator<E>;
reverseBegin(): DequeIterator<E>;
reverseEnd(): DequeIterator<E>;
push(element: E): number;
pop(): E | undefined;
unshift(element: E): number;
shift(): E | undefined;
getAt(pos: number): E;
setAt(pos: number, element: E): void;
insertAt(pos: number, element: E, num?: number): number;
cut(pos: number): number;
deleteAt(pos: number): number;
delete(element: E): number;
deleteByIterator(iter: DequeIterator<E>): DequeIterator<E>;
findIterator(element: E): DequeIterator<E>;
reverse(): this;
unique(): number;
sort(comparator?: (x: E, y: E) => number): this;
shrinkToFit(): void;
forEach(callback: (element: E, index: number, deque: Deque<E>) => void): void;
find(callback: (element: E, index: number, deque: Deque<E>) => boolean): E | undefined;
toArray(): E[];
map<T>(callback: (element: E, index: number, deque: Deque<E>) => T): Deque<T>;
filter(predicate: (element: E, index: number, deque: Deque<E>) => boolean): Deque<E>;
reduce<T>(callback: (accumulator: T, element: E, index: number, deque: Deque<E>) => T, initialValue: T): T;
indexOf(element: E): number;
[Symbol.iterator](): Generator<E, void, unknown>;
protected _reallocate(needBucketNum?: number): void;
protected _getBucketAndPosition(pos: number): {
bucketIndex: number;
indexInBucket: number;
};
}
export declare class ObjectDeque<E = number> {

@@ -36,7 +154,7 @@ constructor(capacity?: number);

*
* The "addFirst" function adds a value to the beginning of an array-like data structure.
* @param {E} value - The `value` parameter represents the value that you want to add to the beginning of the data
* 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(value: E): void;
addFirst(element: E): void;
/**

@@ -50,6 +168,6 @@ * Time Complexity: O(1)

*
* The addLast function adds a value to the end of an array-like data structure.
* @param {E} value - The `value` parameter represents the value that you want to add to the end of the data structure.
* 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(value: E): void;
addLast(element: E): void;
/**

@@ -64,3 +182,3 @@ * Time Complexity: O(1)

* The function `popFirst()` removes and returns the first element in a data structure.
* @returns The value of the first element in the data structure.
* @returns The element of the first element in the data structure.
*/

@@ -89,3 +207,3 @@ popFirst(): E | undefined;

* The `popLast()` function removes and returns the last element in a data structure.
* @returns The value that was removed from the data structure.
* @returns The element that was removed from the data structure.
*/

@@ -117,161 +235,10 @@ popLast(): E | undefined;

* @returns The element at the specified index in the `_nodes` array is being returned. If there is no element at that
* index, `null` is returned.
* index, `undefined` is returned.
*/
get(index: number): NonNullable<E> | null;
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 value indicating whether the size of the object is less than or equal to 0.
* @returns The method is returning a boolean element indicating whether the size of the object is less than or equal to 0.
*/
isEmpty(): boolean;
}
export declare class ArrayDeque<E> {
protected _nodes: E[];
get nodes(): E[];
get size(): number;
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*
* The function "addLast" adds a value to the end of an array.
* @param {E} value - The value parameter represents the value that you want to add to the end of the array.
* @returns The return value is the new length of the array after the value has been added.
*/
addLast(value: E): number;
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*
* The function "popLast" returns and removes the last element from an array, or returns null if the array is empty.
* @returns The method `popLast()` returns the last element of the `_nodes` array, or `null` if the array is empty.
*/
popLast(): E | null;
/**
* Time Complexity: O(n)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(n)
* Space Complexity: O(1)
*
* The `popFirst` function removes and returns the first element from an array, or returns null if the array is empty.
* @returns The `popFirst()` function returns the first element of the `_nodes` array, or `null` if the array is
* empty.
*/
popFirst(): E | null;
/**
* Time Complexity: O(n)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(n)
* Space Complexity: O(1)
*
* The function "addFirst" adds a value to the beginning of an array.
* @param {E} value - The value parameter represents the value that you want to add to the beginning of the array.
* @returns The return value of the `addFirst` function is the new length of the array `_nodes` after adding the
* `value` at the beginning.
*/
addFirst(value: E): number;
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*
* The `getFirst` function returns the first element of an array or null if the array is empty.
* @returns The function `getFirst()` is returning the first element (`E`) of the `_nodes` array. If the array is
* empty, it will return `null`.
*/
getFirst(): E | null;
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*
* The `getLast` function returns the last element of an array or null if the array is empty.
* @returns The method `getLast()` returns the last element of the `_nodes` array, or `null` if the array is empty.
*/
getLast(): E | null;
/**
* 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, or null if the index is out of bounds.
* @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 method is returning the element at the specified index in the `_nodes` array. If the element exists, it
* will be returned. If the element does not exist (i.e., the index is out of bounds), `null` will be returned.
*/
get(index: number): E | null;
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*
* The set function assigns a value to a specific index in an array.
* @param {number} index - The index parameter is a number that represents the position of the element in the array
* that you want to set a new value for.
* @param {E} value - The value parameter represents the new value that you want to set at the specified index in the
* _nodes array.
* @returns The value that is being set at the specified index in the `_nodes` array.
*/
set(index: number, value: E): E;
/**
* Time Complexity: O(n)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(n)
* Space Complexity: O(1)
*
* The insert function adds a value at a specified index in an array.
* @param {number} index - The index parameter specifies the position at which the value should be inserted in the
* array. It is a number that represents the index of the array where the value should be inserted. The index starts
* from 0, so the first element of the array has an index of 0, the second element has
* @param {E} value - The value parameter represents the value that you want to insert into the array at the specified
* index.
* @returns The splice method returns an array containing the removed elements, if any. In this case, since no elements
* are being removed, an empty array will be returned.
*/
insert(index: number, value: E): E[];
/**
* Time Complexity: O(n)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(n)
* Space Complexity: O(1)
*
* The delete function removes an element from an array at a specified index.
* @param {number} index - The index parameter specifies the position of the element to be removed from the array. It
* is a number that represents the index of the element to be removed.
* @returns The method is returning an array containing the removed element.
*/
delete(index: number): E[];
/**
* The function checks if an array called "_nodes" is empty.
* @returns The method `isEmpty()` is returning a boolean value. It returns `true` if the length of the `_nodes` array
* is 0, indicating that the array is empty. Otherwise, it returns `false`.
*/
isEmpty(): boolean;
}

754

dist/data-structures/queue/deque.js
"use strict";
Object.defineProperty(exports, "__esModule", { value: true });
exports.ArrayDeque = exports.ObjectDeque = exports.Deque = void 0;
/**

@@ -11,9 +9,530 @@ * data-structure-typed

*/
const linked_list_1 = require("../linked-list");
// O(n) time complexity of obtaining the value
// O(1) time complexity of adding at the beginning and the end
class Deque extends linked_list_1.DoublyLinkedList {
Object.defineProperty(exports, "__esModule", { value: true });
exports.ObjectDeque = exports.Deque = exports.DequeIterator = void 0;
const utils_1 = require("../../utils");
/**
* Deque can provide random access with O(1) time complexity
* Deque is usually more compact and efficient in memory usage because it does not require additional space to store pointers.
* Deque may experience performance jitter, but DoublyLinkedList will not
* Deque is implemented using a dynamic array. Inserting or deleting beyond both ends of the array may require moving elements or reallocating space.
*/
class DequeIterator {
constructor(index, deque, iterateDirection = 0 /* IterateDirection.DEFAULT */) {
this.index = index;
this.iterateDirection = iterateDirection;
if (this.iterateDirection === 0 /* IterateDirection.DEFAULT */) {
this.prev = function () {
if (this.index === 0) {
(0, utils_1.throwRangeError)();
}
this.index -= 1;
return this;
};
this.next = function () {
if (this.index === this.deque.size) {
(0, utils_1.throwRangeError)();
}
this.index += 1;
return this;
};
}
else {
this.prev = function () {
if (this.index === this.deque.size - 1) {
(0, utils_1.throwRangeError)();
}
this.index += 1;
return this;
};
this.next = function () {
if (this.index === -1) {
(0, utils_1.throwRangeError)();
}
this.index -= 1;
return this;
};
}
this.deque = deque;
}
get current() {
return this.deque.getAt(this.index);
}
set current(newElement) {
this.deque.setAt(this.index, newElement);
}
isAccessible() {
return this.index !== this.deque.size;
}
prev() {
return this;
}
next() {
return this;
}
clone() {
return new DequeIterator(this.index, this.deque, this.iterateDirection);
}
}
exports.DequeIterator = DequeIterator;
class Deque {
constructor(elements = [], bucketSize = (1 << 12)) {
this._bucketFirst = 0;
this._firstInBucket = 0;
this._bucketLast = 0;
this._lastInBucket = 0;
this._bucketCount = 0;
this._buckets = [];
this._size = 0;
let _size;
if ('length' in elements) {
_size = elements.length;
}
else {
_size = elements.size;
}
this._bucketSize = bucketSize;
this._bucketCount = (0, utils_1.calcMinUnitsRequired)(_size, this._bucketSize) || 1;
for (let i = 0; i < this._bucketCount; ++i) {
this._buckets.push(new Array(this._bucketSize));
}
const needBucketNum = (0, utils_1.calcMinUnitsRequired)(_size, this._bucketSize);
this._bucketFirst = this._bucketLast = (this._bucketCount >> 1) - (needBucketNum >> 1);
this._firstInBucket = this._lastInBucket = (this._bucketSize - _size % this._bucketSize) >> 1;
for (const element of elements) {
this.push(element);
}
}
get buckets() {
return this._buckets;
}
get size() {
return this._size;
}
get first() {
if (this.size === 0)
return;
return this._buckets[this._bucketFirst][this._firstInBucket];
}
get last() {
if (this.size === 0)
return;
return this._buckets[this._bucketLast][this._lastInBucket];
}
/**
* Time Complexity: Amortized O(1) - Generally constant time, but resizing when the deque is full leads to O(n).
* Space Complexity: O(n) - In worst case, resizing doubles the array size.
*/
empty() {
return this._size === 0;
}
/**
* Time Complexity: O(1) - Removes the last element.
* Space Complexity: O(1) - Operates in-place.
*/
isEmpty() {
return this.size === 0;
}
/**
* Time Complexity: Amortized O(1) - Similar to push, resizing leads to O(n).
* Space Complexity: O(n) - Due to potential resizing.
*/
/**
* Time Complexity: O(1)
* Space Complexity: O(n) - In worst case, resizing doubles the array size.
*
* The addLast function adds an element to the end of an array.
* @param {E} element - The element parameter represents the element that you want to add to the end of the
* data structure.
*/
addLast(element) {
this.push(element);
}
/**
* Time Complexity: O(1) - Removes the first element.
* Space Complexity: O(1) - In-place operation.
*/
/**
* Time Complexity: O(1) - Removes the last element.
* Space Complexity: O(1) - Operates in-place.
*
* The function "popLast" removes and returns the last element of an array.
* @returns The last element of the array is being returned.
*/
popLast() {
return this.pop();
}
/**
* Time Complexity: O(1).
* Space Complexity: O(n) - Due to potential resizing.
*
* The "addFirst" function adds an element to the beginning of an array.
* @param {E} element - The parameter "element" represents the element that you want to add to the
* beginning of the data structure.
*/
addFirst(element) {
this.unshift(element);
}
/**
* Time Complexity: O(1) - Removes the first element.
* Space Complexity: O(1) - In-place operation.
*
* The function "popFirst" removes and returns the first element of an array.
* @returns The method `popFirst()` is returning the first element of the array after removing it
* from the beginning. If the array is empty, it will return `undefined`.
*/
popFirst() {
return this.shift();
}
clear() {
this._buckets = [new Array(this._bucketSize)];
this._bucketCount = 1;
this._bucketFirst = this._bucketLast = this._size = 0;
this._firstInBucket = this._lastInBucket = this._bucketSize >> 1;
}
begin() {
return new DequeIterator(0, this);
}
end() {
return new DequeIterator(this.size, this);
}
reverseBegin() {
return new DequeIterator(this.size - 1, this, 1 /* IterateDirection.REVERSE */);
}
reverseEnd() {
return new DequeIterator(-1, this, 1 /* IterateDirection.REVERSE */);
}
push(element) {
if (this.size) {
if (this._lastInBucket < this._bucketSize - 1) {
this._lastInBucket += 1;
}
else if (this._bucketLast < this._bucketCount - 1) {
this._bucketLast += 1;
this._lastInBucket = 0;
}
else {
this._bucketLast = 0;
this._lastInBucket = 0;
}
if (this._bucketLast === this._bucketFirst &&
this._lastInBucket === this._firstInBucket)
this._reallocate();
}
this._size += 1;
this._buckets[this._bucketLast][this._lastInBucket] = element;
return this.size;
}
pop() {
if (this.size === 0)
return;
const element = this._buckets[this._bucketLast][this._lastInBucket];
if (this.size !== 1) {
if (this._lastInBucket > 0) {
this._lastInBucket -= 1;
}
else if (this._bucketLast > 0) {
this._bucketLast -= 1;
this._lastInBucket = this._bucketSize - 1;
}
else {
this._bucketLast = this._bucketCount - 1;
this._lastInBucket = this._bucketSize - 1;
}
}
this._size -= 1;
return element;
}
unshift(element) {
if (this.size) {
if (this._firstInBucket > 0) {
this._firstInBucket -= 1;
}
else if (this._bucketFirst > 0) {
this._bucketFirst -= 1;
this._firstInBucket = this._bucketSize - 1;
}
else {
this._bucketFirst = this._bucketCount - 1;
this._firstInBucket = this._bucketSize - 1;
}
if (this._bucketFirst === this._bucketLast &&
this._firstInBucket === this._lastInBucket)
this._reallocate();
}
this._size += 1;
this._buckets[this._bucketFirst][this._firstInBucket] = element;
return this.size;
}
shift() {
if (this.size === 0)
return;
const element = this._buckets[this._bucketFirst][this._firstInBucket];
if (this.size !== 1) {
if (this._firstInBucket < this._bucketSize - 1) {
this._firstInBucket += 1;
}
else if (this._bucketFirst < this._bucketCount - 1) {
this._bucketFirst += 1;
this._firstInBucket = 0;
}
else {
this._bucketFirst = 0;
this._firstInBucket = 0;
}
}
this._size -= 1;
return element;
}
getAt(pos) {
utils_1.rangeCheck(pos, 0, this.size - 1);
const { bucketIndex, indexInBucket } = this._getBucketAndPosition(pos);
return this._buckets[bucketIndex][indexInBucket];
}
setAt(pos, element) {
utils_1.rangeCheck(pos, 0, this.size - 1);
const { bucketIndex, indexInBucket } = this._getBucketAndPosition(pos);
this._buckets[bucketIndex][indexInBucket] = element;
}
insertAt(pos, element, num = 1) {
const length = this.size;
utils_1.rangeCheck(pos, 0, length);
if (pos === 0) {
while (num--)
this.unshift(element);
}
else if (pos === this.size) {
while (num--)
this.push(element);
}
else {
const arr = [];
for (let i = pos; i < this.size; ++i) {
arr.push(this.getAt(i));
}
this.cut(pos - 1);
for (let i = 0; i < num; ++i)
this.push(element);
for (let i = 0; i < arr.length; ++i)
this.push(arr[i]);
}
return this.size;
}
cut(pos) {
if (pos < 0) {
this.clear();
return 0;
}
const { bucketIndex, indexInBucket } = this._getBucketAndPosition(pos);
this._bucketLast = bucketIndex;
this._lastInBucket = indexInBucket;
this._size = pos + 1;
return this.size;
}
deleteAt(pos) {
utils_1.rangeCheck(pos, 0, this.size - 1);
if (pos === 0)
this.shift();
else if (pos === this.size - 1)
this.pop();
else {
const length = this.size - 1;
let { bucketIndex: curBucket, indexInBucket: curPointer } = this._getBucketAndPosition(pos);
for (let i = pos; i < length; ++i) {
const { bucketIndex: nextBucket, indexInBucket: nextPointer } = this._getBucketAndPosition(pos + 1);
this._buckets[curBucket][curPointer] = this._buckets[nextBucket][nextPointer];
curBucket = nextBucket;
curPointer = nextPointer;
}
this.pop();
}
return this.size;
}
delete(element) {
const size = this.size;
if (size === 0)
return 0;
let i = 0;
let index = 0;
while (i < size) {
const oldElement = this.getAt(i);
if (oldElement !== element) {
this.setAt(index, oldElement);
index += 1;
}
i += 1;
}
this.cut(index - 1);
return this.size;
}
deleteByIterator(iter) {
const index = iter.index;
this.deleteAt(index);
iter = iter.next();
return iter;
}
findIterator(element) {
for (let i = 0; i < this.size; ++i) {
if (this.getAt(i) === element) {
return new DequeIterator(i, this);
}
}
return this.end();
}
reverse() {
this._buckets.reverse().forEach(function (bucket) {
bucket.reverse();
});
const { _bucketFirst, _bucketLast, _firstInBucket, _lastInBucket } = this;
this._bucketFirst = this._bucketCount - _bucketLast - 1;
this._bucketLast = this._bucketCount - _bucketFirst - 1;
this._firstInBucket = this._bucketSize - _lastInBucket - 1;
this._lastInBucket = this._bucketSize - _firstInBucket - 1;
return this;
}
unique() {
if (this.size <= 1) {
return this.size;
}
let index = 1;
let prev = this.getAt(0);
for (let i = 1; i < this.size; ++i) {
const cur = this.getAt(i);
if (cur !== prev) {
prev = cur;
this.setAt(index++, cur);
}
}
this.cut(index - 1);
return this.size;
}
sort(comparator) {
const arr = [];
for (let i = 0; i < this.size; ++i) {
arr.push(this.getAt(i));
}
arr.sort(comparator);
for (let i = 0; i < this.size; ++i) {
this.setAt(i, arr[i]);
}
return this;
}
shrinkToFit() {
if (this.size === 0)
return;
const newBuckets = [];
if (this._bucketFirst === this._bucketLast)
return;
else if (this._bucketFirst < this._bucketLast) {
for (let i = this._bucketFirst; i <= this._bucketLast; ++i) {
newBuckets.push(this._buckets[i]);
}
}
else {
for (let i = this._bucketFirst; i < this._bucketCount; ++i) {
newBuckets.push(this._buckets[i]);
}
for (let i = 0; i <= this._bucketLast; ++i) {
newBuckets.push(this._buckets[i]);
}
}
this._bucketFirst = 0;
this._bucketLast = newBuckets.length - 1;
this._buckets = newBuckets;
}
forEach(callback) {
for (let i = 0; i < this.size; ++i) {
callback(this.getAt(i), i, this);
}
}
find(callback) {
for (let i = 0; i < this.size; ++i) {
const element = this.getAt(i);
if (callback(element, i, this)) {
return element;
}
}
return undefined;
}
toArray() {
const arr = [];
for (let i = 0; i < this.size; ++i) {
arr.push(this.getAt(i));
}
return arr;
}
map(callback) {
const newDeque = new Deque([], this._bucketSize);
for (let i = 0; i < this.size; ++i) {
newDeque.push(callback(this.getAt(i), i, this));
}
return newDeque;
}
filter(predicate) {
const newDeque = new Deque([], this._bucketSize);
for (let i = 0; i < this.size; ++i) {
const element = this.getAt(i);
if (predicate(element, i, this)) {
newDeque.push(element);
}
}
return newDeque;
}
reduce(callback, initialValue) {
let accumulator = initialValue;
for (let i = 0; i < this.size; ++i) {
accumulator = callback(accumulator, this.getAt(i), i, this);
}
return accumulator;
}
indexOf(element) {
for (let i = 0; i < this.size; ++i) {
if (this.getAt(i) === element) {
return i;
}
}
return -1;
}
*[Symbol.iterator]() {
for (let i = 0; i < this.size; ++i) {
yield this.getAt(i);
}
}
_reallocate(needBucketNum) {
const newBuckets = [];
const addBucketNum = needBucketNum || this._bucketCount >> 1 || 1;
for (let i = 0; i < addBucketNum; ++i) {
newBuckets[i] = new Array(this._bucketSize);
}
for (let i = this._bucketFirst; i < this._bucketCount; ++i) {
newBuckets[newBuckets.length] = this._buckets[i];
}
for (let i = 0; i < this._bucketLast; ++i) {
newBuckets[newBuckets.length] = this._buckets[i];
}
newBuckets[newBuckets.length] = [...this._buckets[this._bucketLast]];
this._bucketFirst = addBucketNum;
this._bucketLast = newBuckets.length - 1;
for (let i = 0; i < addBucketNum; ++i) {
newBuckets[newBuckets.length] = new Array(this._bucketSize);
}
this._buckets = newBuckets;
this._bucketCount = newBuckets.length;
}
_getBucketAndPosition(pos) {
let bucketIndex;
let indexInBucket;
const overallIndex = this._firstInBucket + pos;
bucketIndex = this._bucketFirst + Math.floor(overallIndex / this._bucketSize);
if (bucketIndex >= this._bucketCount) {
bucketIndex -= this._bucketCount;
}
indexInBucket = (overallIndex + 1) % this._bucketSize - 1;
if (indexInBucket < 0) {
indexInBucket = this._bucketSize - 1;
}
return { bucketIndex, indexInBucket };
}
}
exports.Deque = Deque;
// O(1) time complexity of obtaining the value
// O(1) time complexity of obtaining the element
// O(n) time complexity of adding at the beginning and the end

@@ -54,7 +573,7 @@ // todo tested slowest one

*
* The "addFirst" function adds a value to the beginning of an array-like data structure.
* @param {E} value - The `value` parameter represents the value that you want to add to the beginning of the data
* 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(value) {
addFirst(element) {
if (this.size === 0) {

@@ -68,3 +587,3 @@ const mid = Math.floor(this.capacity / 2);

}
this.nodes[this.first] = value;
this.nodes[this.first] = element;
this._size++;

@@ -80,6 +599,6 @@ }

*
* The addLast function adds a value to the end of an array-like data structure.
* @param {E} value - The `value` parameter represents the value that you want to add to the end of the data structure.
* 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(value) {
addLast(element) {
if (this.size === 0) {

@@ -93,3 +612,3 @@ const mid = Math.floor(this.capacity / 2);

}
this.nodes[this.last] = value;
this.nodes[this.last] = element;
this._size++;

@@ -106,3 +625,3 @@ }

* The function `popFirst()` removes and returns the first element in a data structure.
* @returns The value of the first element in the data structure.
* @returns The element of the first element in the data structure.
*/

@@ -112,7 +631,7 @@ popFirst() {

return;
const value = this.getFirst();
const element = this.getFirst();
delete this.nodes[this.first];
this._first++;
this._size--;
return value;
return element;
}

@@ -143,3 +662,3 @@ /**

* The `popLast()` function removes and returns the last element in a data structure.
* @returns The value that was removed from the data structure.
* @returns The element that was removed from the data structure.
*/

@@ -149,7 +668,7 @@ popLast() {

return;
const value = this.getLast();
const element = this.getLast();
delete this.nodes[this.last];
this._last--;
this._size--;
return value;
return element;
}

@@ -183,10 +702,10 @@ /**

* @returns The element at the specified index in the `_nodes` array is being returned. If there is no element at that
* index, `null` is returned.
* index, `undefined` is returned.
*/
get(index) {
return this.nodes[this.first + index] || null;
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 value indicating whether the size of the object is less than or equal to 0.
* @returns The method is returning a boolean element indicating whether the size of the object is less than or equal to 0.
*/

@@ -198,188 +717,1 @@ isEmpty() {

exports.ObjectDeque = ObjectDeque;
// O(1) time complexity of obtaining the value
// O(n) time complexity of adding at the beginning and the end
class ArrayDeque {
constructor() {
this._nodes = [];
}
get nodes() {
return this._nodes;
}
get size() {
return this.nodes.length;
}
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*
* The function "addLast" adds a value to the end of an array.
* @param {E} value - The value parameter represents the value that you want to add to the end of the array.
* @returns The return value is the new length of the array after the value has been added.
*/
addLast(value) {
return this.nodes.push(value);
}
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*
* The function "popLast" returns and removes the last element from an array, or returns null if the array is empty.
* @returns The method `popLast()` returns the last element of the `_nodes` array, or `null` if the array is empty.
*/
popLast() {
var _a;
return (_a = this.nodes.pop()) !== null && _a !== void 0 ? _a : null;
}
/**
* Time Complexity: O(n)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(n)
* Space Complexity: O(1)
*
* The `popFirst` function removes and returns the first element from an array, or returns null if the array is empty.
* @returns The `popFirst()` function returns the first element of the `_nodes` array, or `null` if the array is
* empty.
*/
popFirst() {
var _a;
return (_a = this.nodes.shift()) !== null && _a !== void 0 ? _a : null;
}
/**
* Time Complexity: O(n)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(n)
* Space Complexity: O(1)
*
* The function "addFirst" adds a value to the beginning of an array.
* @param {E} value - The value parameter represents the value that you want to add to the beginning of the array.
* @returns The return value of the `addFirst` function is the new length of the array `_nodes` after adding the
* `value` at the beginning.
*/
addFirst(value) {
return this.nodes.unshift(value);
}
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*
* The `getFirst` function returns the first element of an array or null if the array is empty.
* @returns The function `getFirst()` is returning the first element (`E`) of the `_nodes` array. If the array is
* empty, it will return `null`.
*/
getFirst() {
var _a;
return (_a = this.nodes[0]) !== null && _a !== void 0 ? _a : null;
}
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*
* The `getLast` function returns the last element of an array or null if the array is empty.
* @returns The method `getLast()` returns the last element of the `_nodes` array, or `null` if the array is empty.
*/
getLast() {
var _a;
return (_a = this.nodes[this.nodes.length - 1]) !== null && _a !== void 0 ? _a : null;
}
/**
* 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, or null if the index is out of bounds.
* @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 method is returning the element at the specified index in the `_nodes` array. If the element exists, it
* will be returned. If the element does not exist (i.e., the index is out of bounds), `null` will be returned.
*/
get(index) {
var _a;
return (_a = this.nodes[index]) !== null && _a !== void 0 ? _a : null;
}
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*
* The set function assigns a value to a specific index in an array.
* @param {number} index - The index parameter is a number that represents the position of the element in the array
* that you want to set a new value for.
* @param {E} value - The value parameter represents the new value that you want to set at the specified index in the
* _nodes array.
* @returns The value that is being set at the specified index in the `_nodes` array.
*/
set(index, value) {
return (this.nodes[index] = value);
}
/**
* Time Complexity: O(n)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(n)
* Space Complexity: O(1)
*
* The insert function adds a value at a specified index in an array.
* @param {number} index - The index parameter specifies the position at which the value should be inserted in the
* array. It is a number that represents the index of the array where the value should be inserted. The index starts
* from 0, so the first element of the array has an index of 0, the second element has
* @param {E} value - The value parameter represents the value that you want to insert into the array at the specified
* index.
* @returns The splice method returns an array containing the removed elements, if any. In this case, since no elements
* are being removed, an empty array will be returned.
*/
insert(index, value) {
return this.nodes.splice(index, 0, value);
}
/**
* Time Complexity: O(n)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(n)
* Space Complexity: O(1)
*
* The delete function removes an element from an array at a specified index.
* @param {number} index - The index parameter specifies the position of the element to be removed from the array. It
* is a number that represents the index of the element to be removed.
* @returns The method is returning an array containing the removed element.
*/
delete(index) {
return this.nodes.splice(index, 1);
}
/**
* The function checks if an array called "_nodes" is empty.
* @returns The method `isEmpty()` is returning a boolean value. It returns `true` if the length of the `_nodes` array
* is 0, indicating that the array is empty. Otherwise, it returns `false`.
*/
isEmpty() {
return this.nodes.length === 0;
}
}
exports.ArrayDeque = ArrayDeque;

9

dist/types/data-structures/hash/hash-map.d.ts

@@ -1,10 +0,1 @@

export declare const enum IterateDirection {
DEFAULT = 0,
REVERSE = 1
}
export type HashMapOptions<T> = {
sizeFunction?: number | (() => number);
fixedLength?: number;
forEach: (callback: (el: T) => void) => void;
};
export type HashMapLinkedNode<K, V> = {

@@ -11,0 +2,0 @@ key: K;

11

dist/types/helpers.d.ts

@@ -9,1 +9,12 @@ export type Comparator<T> = (a: T, b: T) => number;

}
export declare const enum IterateDirection {
DEFAULT = 0,
REVERSE = 1
}
export interface IterableWithSize<T> extends Iterable<T> {
size: number;
}
export interface IterableWithLength<T> extends Iterable<T> {
length: number;
}
export type IterableWithSizeOrLength<T> = IterableWithSize<T> | IterableWithLength<T>;

1

dist/utils/utils.d.ts

@@ -24,1 +24,2 @@ /**

export declare const isObjOrFunc: (input: unknown) => input is Record<string, unknown> | ((...args: any[]) => any);
export declare const calcMinUnitsRequired: (totalQuantity: number, unitSize: number) => number;

4

dist/utils/utils.js

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

Object.defineProperty(exports, "__esModule", { value: true });
exports.isObjOrFunc = exports.throwRangeError = exports.rangeCheck = exports.getMSB = exports.trampolineAsync = exports.trampoline = exports.toThunk = exports.isThunk = exports.THUNK_SYMBOL = exports.arrayRemove = exports.uuidV4 = void 0;
exports.calcMinUnitsRequired = exports.isObjOrFunc = exports.throwRangeError = exports.rangeCheck = exports.getMSB = exports.trampolineAsync = exports.trampoline = exports.toThunk = exports.isThunk = exports.THUNK_SYMBOL = exports.arrayRemove = exports.uuidV4 = void 0;
const uuidV4 = function () {

@@ -89,1 +89,3 @@ return 'xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx'.replace(/[x]/g, function (c) {

exports.isObjOrFunc = isObjOrFunc;
const calcMinUnitsRequired = (totalQuantity, unitSize) => Math.floor((totalQuantity + unitSize - 1) / unitSize);
exports.calcMinUnitsRequired = calcMinUnitsRequired;

4

package.json
{
"name": "directed-graph-typed",
"version": "1.45.3",
"version": "1.46.1",
"description": "Directed Graph. Javascript & Typescript Data Structure.",

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

"dependencies": {
"data-structure-typed": "^1.45.3"
"data-structure-typed": "^1.46.0"
}
}

18

src/data-structures/hash/hash-map.ts

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

import { isObjOrFunc, rangeCheck, throwRangeError } from '../../utils';
import { HashMapLinkedNode, HashMapOptions, IterateDirection } from '../../types';
import { HashMapLinkedNode, IterableWithSizeOrLength, IterateDirection } from '../../types';

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

}
clone() {
return new HashMapIterator<K, V>(this._node, this._sentinel, this.hashMap, this.iterateDirection)
}
}

@@ -139,7 +143,7 @@

* The constructor initializes a HashMap object with an optional initial set of key-value pairs.
* @param hashMap - The `hashMap` parameter is an optional parameter of type `HashMapOptions<[K,
* @param {Iterable<[K, V]>} elements - The `hashMap` parameter is an optional parameter of type `HashMapOptions<[K,
* V]>`. It is an array of key-value pairs, where each pair is represented as an array `[K, V]`. The
* `K` represents the type of the key and `V` represents the
*/
constructor(hashMap: HashMapOptions<[K, V]> = []) {
constructor(elements: IterableWithSizeOrLength<[K, V]> = []) {
Object.setPrototypeOf(this._orgMap, null);

@@ -149,5 +153,5 @@ this._sentinel = <HashMapLinkedNode<K, V>>{};

hashMap.forEach(el => {
for (const el of elements) {
this.set(el[0], el[1]);
});
}
}

@@ -216,3 +220,3 @@

*/
get front() {
get first() {
if (this._size === 0) return;

@@ -230,3 +234,3 @@ return <[K, V]>[this._head.key, this._head.value];

*/
get back() {
get last() {
if (this._size === 0) return;

@@ -233,0 +237,0 @@ return <[K, V]>[this._tail.key, this._tail.value];

258

src/data-structures/heap/heap.ts

@@ -11,6 +11,6 @@ /**

export class Heap<E = any> {
constructor(options: { comparator: Comparator<E>; nodes?: E[] }) {
constructor(options: { comparator: Comparator<E>; elements?: E[] }) {
this._comparator = options.comparator;
if (options.nodes && options.nodes.length > 0) {
this._nodes = options.nodes;
if (options.elements && options.elements.length > 0) {
this._elements = options.elements;
this.fix();

@@ -20,6 +20,6 @@ }

protected _nodes: E[] = [];
protected _elements: E[] = [];
get nodes(): E[] {
return this._nodes;
get elements(): E[] {
return this._elements;
}

@@ -37,3 +37,3 @@

get size(): number {
return this.nodes.length;
return this.elements.length;
}

@@ -46,11 +46,11 @@

get leaf(): E | undefined {
return this.nodes[this.size - 1] ?? undefined;
return this.elements[this.size - 1] ?? undefined;
}
/**
* Static method that creates a binary heap from an array of nodes and a comparison function.
* Static method that creates a binary heap from an array of elements and a comparison function.
* @returns A new Heap instance.
* @param options
*/
static heapify<E>(options: { nodes: E[]; comparator: Comparator<E> }): Heap<E> {
static heapify<E>(options: { elements: E[]; comparator: Comparator<E> }): Heap<E> {
return new Heap<E>(options);

@@ -60,3 +60,3 @@ }

/**
* Time Complexity: O(log n), where n is the number of nodes in the heap.
* Time Complexity: O(log n), where n is the number of elements in the heap.
* Space Complexity: O(1)

@@ -66,3 +66,3 @@ */

/**
* Time Complexity: O(log n), where n is the number of nodes in the heap.
* Time Complexity: O(log n), where n is the number of elements in the heap.
* Space Complexity: O(1)

@@ -78,3 +78,3 @@ *

/**
* Time Complexity: O(log n), where n is the number of nodes in the heap.
* Time Complexity: O(log n), where n is the number of elements in the heap.
* Space Complexity: O(1)

@@ -84,3 +84,3 @@ */

/**
* Time Complexity: O(log n), where n is the number of nodes in the heap.
* Time Complexity: O(log n), where n is the number of elements in the heap.
* Space Complexity: O(1)

@@ -92,4 +92,4 @@ *

push(element: E): Heap<E> {
this.nodes.push(element);
this.bubbleUp(this.nodes.length - 1);
this._elements.push(element);
this._bubbleUp(this.elements.length - 1);
return this;

@@ -99,3 +99,3 @@ }

/**
* Time Complexity: O(log n), where n is the number of nodes in the heap.
* Time Complexity: O(log n), where n is the number of elements in the heap.
* Space Complexity: O(1)

@@ -105,3 +105,3 @@ */

/**
* Time Complexity: O(log n), where n is the number of nodes in the heap.
* Time Complexity: O(log n), where n is the number of elements in the heap.
* Space Complexity: O(1)

@@ -113,17 +113,14 @@ *

poll(): E | undefined {
if (this.nodes.length === 0) {
return undefined;
if (this.elements.length === 0) return;
const value = this.elements[0];
const last = this.elements.pop()!;
if (this.elements.length) {
this.elements[0] = last;
this._sinkDown(0, this.elements.length >> 1);
}
if (this.nodes.length === 1) {
return this.nodes.pop() as E;
}
const topValue = this.nodes[0];
this.nodes[0] = this.nodes.pop() as E;
this.sinkDown(0);
return topValue;
return value;
}
/**
* Time Complexity: O(log n), where n is the number of nodes in the heap.
* Time Complexity: O(log n), where n is the number of elements in the heap.
* Space Complexity: O(1)

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

/**
* Time Complexity: O(log n), where n is the number of nodes in the heap.
* Time Complexity: O(log n), where n is the number of elements in the heap.
* Space Complexity: O(1)

@@ -149,6 +146,3 @@ *

peek(): E | undefined {
if (this.nodes.length === 0) {
return undefined;
}
return this.nodes[0];
return this.elements[0];
}

@@ -165,10 +159,10 @@

/**
* Reset the nodes of the heap. Make the nodes empty.
* Reset the elements of the heap. Make the elements empty.
*/
clear() {
this._nodes = [];
this._elements = [];
}
/**
* Time Complexity: O(n), where n is the number of elements in the nodes array.
* Time Complexity: O(n), where n is the number of elements in the elements array.
* Space Complexity: O(n)

@@ -178,10 +172,10 @@ */

/**
* Time Complexity: O(n), where n is the number of elements in the nodes array.
* Time Complexity: O(n), where n is the number of elements in the elements array.
* Space Complexity: O(n)
*
* Clear and add nodes of the heap
* @param nodes
* Clear and add elements of the heap
* @param elements
*/
refill(nodes: E[]) {
this._nodes = nodes;
refill(elements: E[]) {
this._elements = elements;
this.fix();

@@ -191,3 +185,3 @@ }

/**
* Time Complexity: O(n), where n is the number of nodes in the heap.
* Time Complexity: O(n), where n is the number of elements in the heap.
* Space Complexity: O(1)

@@ -197,3 +191,3 @@ */

/**
* Time Complexity: O(n), where n is the number of nodes in the heap.
* Time Complexity: O(n), where n is the number of elements in the heap.
* Space Complexity: O(1)

@@ -206,7 +200,38 @@ *

has(element: E): boolean {
return this.nodes.includes(element);
return this.elements.includes(element);
}
/**
* Time Complexity: O(n), where n is the number of nodes in the heap.
* Time Complexity: O(n). The worst-case O(n), where n is the number of elements in the heap. This is because, in the worst case, the element to be deleted is located at the end of the heap (not the root), and after deletion, we may need to reorganize the elements by performing a sinkDown operation.
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(n). The worst-case O(n), where n is the number of elements in the heap. This is because, in the worst case, the element to be deleted is located at the end of the heap (not the root), and after deletion, we may need to reorganize the elements by performing a sinkDown operation.
* Space Complexity: O(1)
*
* The `delete` function removes an element from an array-like data structure, maintaining the order
* and structure of the remaining elements.
* @param {E} element - The `element` parameter represents the element that you want to delete from
* the array `this.elements`.
* @returns The `delete` function is returning a boolean value. It returns `true` if the element was
* successfully deleted from the array, and `false` if the element was not found in the array.
*/
delete(element: E) {
const index = this.elements.indexOf(element);
if (index < 0) return false;
if (index === 0) {
this.pop();
} else if (index === this.elements.length - 1) {
this.elements.pop();
} else {
this.elements.splice(index, 1, this.elements.pop()!);
this._bubbleUp(index);
this._sinkDown(index, this.elements.length >> 1);
}
return true;
}
/**
* Time Complexity: O(n), where n is the number of elements in the heap.
* Space Complexity: O(h), where h is the height of the heap.

@@ -216,3 +241,3 @@ */

/**
* Time Complexity: O(n), where n is the number of nodes in the heap.
* Time Complexity: O(n), where n is the number of elements in the heap.
* Space Complexity: O(h), where h is the height of the heap.

@@ -232,6 +257,6 @@ *

dfsHelper(2 * index + 1);
result.push(this.nodes[index]);
result.push(this.elements[index]);
dfsHelper(2 * index + 2);
} else if (order === 'pre') {
result.push(this.nodes[index]);
result.push(this.elements[index]);
dfsHelper(2 * index + 1);

@@ -242,3 +267,3 @@ dfsHelper(2 * index + 2);

dfsHelper(2 * index + 2);
result.push(this.nodes[index]);
result.push(this.elements[index]);
}

@@ -266,14 +291,6 @@ }

toArray(): E[] {
return [...this.nodes];
return [...this.elements];
}
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*/
getNodes(): E[] {
return this.nodes;
}
/**
* Time Complexity: O(n)

@@ -292,3 +309,3 @@ * Space Complexity: O(n)

const clonedHeap = new Heap<E>({ comparator: this.comparator });
clonedHeap._nodes = [...this.nodes];
clonedHeap._elements = [...this.elements];
return clonedHeap;

@@ -325,31 +342,9 @@ }

/**
* Time Complexity: O(log n)
* Time Complexity: O(n)
* Space Complexity: O(1)
*
* Float operation to maintain heap properties after adding an element.
* @param index - The index of the newly added element.
* Fix the entire heap to maintain heap properties.
*/
protected bubbleUp(index: number): void {
// const element = this.nodes[index];
// while (index > 0) {
// const parentIndex = (index - 1) >> 1;
// const parent = this.nodes[parentIndex];
// if (this.comparator(element, parent) < 0) {
// this.nodes[index] = parent;
// this.nodes[parentIndex] = element;
// index = parentIndex;
// } else {
// break;
// }
// }
const item = this.nodes[index];
while (index > 0) {
const parent = (index - 1) >> 1;
const parentItem = this.nodes[parent];
if (this.comparator(parentItem, item) <= 0) break;
this.nodes[index] = parentItem;
index = parent;
}
this.nodes[index] = item;
fix() {
for (let i = Math.floor(this.size / 2); i >= 0; i--) this._sinkDown(i, this.elements.length >> 1);
}

@@ -366,24 +361,15 @@

*
* Sinking operation to maintain heap properties after removing the top element.
* @param index - The index from which to start sinking.
* Float operation to maintain heap properties after adding an element.
* @param index - The index of the newly added element.
*/
protected sinkDown(index: number): void {
const leftChildIndex = index << 1 | 1;
const rightChildIndex = leftChildIndex + 1;
const length = this.nodes.length;
let targetIndex = index;
if (leftChildIndex < length && this.comparator(this.nodes[leftChildIndex], this.nodes[targetIndex]) < 0) {
targetIndex = leftChildIndex;
protected _bubbleUp(index: number) {
const element = this.elements[index];
while (index > 0) {
const parent = (index - 1) >> 1;
const parentItem = this.elements[parent];
if (this._comparator(parentItem, element) <= 0) break;
this.elements[index] = parentItem;
index = parent;
}
if (rightChildIndex < length && this.comparator(this.nodes[rightChildIndex], this.nodes[targetIndex]) < 0) {
targetIndex = rightChildIndex;
}
if (targetIndex !== index) {
const temp = this.nodes[index];
this.nodes[index] = this.nodes[targetIndex];
this.nodes[targetIndex] = temp;
this.sinkDown(targetIndex);
}
this.elements[index] = element;
}

@@ -397,9 +383,27 @@

/**
* Time Complexity: O(n)
* Time Complexity: O(log n)
* Space Complexity: O(1)
*
* Fix the entire heap to maintain heap properties.
* Sinking operation to maintain heap properties after removing the top element.
* @param index - The index from which to start sinking.
* @param halfLength
*/
protected fix() {
for (let i = Math.floor(this.size / 2); i >= 0; i--) this.sinkDown(i);
protected _sinkDown(index: number, halfLength: number) {
const element = this.elements[index];
while (index < halfLength) {
let left = index << 1 | 1;
const right = left + 1;
let minItem = this.elements[left];
if (
right < this.elements.length &&
this._comparator(minItem, this.elements[right]) > 0
) {
left = right;
minItem = this.elements[right];
}
if (this._comparator(minItem, element) >= 0) break;
this.elements[index] = minItem;
index = left;
}
this.elements[index] = element;
}

@@ -530,3 +534,3 @@ }

/**
* Time Complexity: O(n), where n is the number of nodes in the linked list.
* Time Complexity: O(n), where n is the number of elements in the linked list.
* Space Complexity: O(1)

@@ -536,3 +540,3 @@ */

/**
* Time Complexity: O(n), where n is the number of nodes in the linked list.
* Time Complexity: O(n), where n is the number of elements in the linked list.
* Space Complexity: O(1)

@@ -543,7 +547,7 @@ *

* @protected
* @returns FibonacciHeapNode<E>[] - An array containing the nodes of the linked list.
* @returns FibonacciHeapNode<E>[] - An array containing the elements of the linked list.
*/
consumeLinkedList(head?: FibonacciHeapNode<E>): FibonacciHeapNode<E>[] {
const nodes: FibonacciHeapNode<E>[] = [];
if (!head) return nodes;
const elements: FibonacciHeapNode<E>[] = [];
if (!head) return elements;

@@ -558,3 +562,3 @@ let node: FibonacciHeapNode<E> | undefined = head;

if (node) {
nodes.push(node);
elements.push(node);
node = node.right;

@@ -564,3 +568,3 @@ }

return nodes;
return elements;
}

@@ -587,3 +591,3 @@

/**
* Time Complexity: O(log n), where n is the number of nodes in the heap.
* Time Complexity: O(log n), where n is the number of elements in the heap.
* Space Complexity: O(1)

@@ -593,3 +597,3 @@ */

/**
* Time Complexity: O(log n), where n is the number of nodes in the heap.
* Time Complexity: O(log n), where n is the number of elements in the heap.
* Space Complexity: O(1)

@@ -605,3 +609,3 @@ *

/**
* Time Complexity: O(log n), where n is the number of nodes in the heap.
* Time Complexity: O(log n), where n is the number of elements in the heap.
* Space Complexity: O(1)

@@ -611,3 +615,3 @@ */

/**
* Time Complexity: O(log n), where n is the number of nodes in the heap.
* Time Complexity: O(log n), where n is the number of elements in the heap.
* Space Complexity: O(1)

@@ -623,4 +627,4 @@ *

if (z.child) {
const nodes = this.consumeLinkedList(z.child);
for (const node of nodes) {
const elements = this.consumeLinkedList(z.child);
for (const node of elements) {
this.mergeWithRoot(node);

@@ -777,3 +781,3 @@ node.parent = undefined;

/**
* Time Complexity: O(n log n), where n is the number of nodes in the heap.
* Time Complexity: O(n log n), where n is the number of elements in the heap.
* Space Complexity: O(n)

@@ -783,3 +787,3 @@ */

/**
* Time Complexity: O(n log n), where n is the number of nodes in the heap.
* Time Complexity: O(n log n), where n is the number of elements in the heap.
* Space Complexity: O(n)

@@ -792,3 +796,3 @@ *

const A: (FibonacciHeapNode<E> | undefined)[] = new Array(this.size);
const nodes = this.consumeLinkedList(this.root);
const elements = this.consumeLinkedList(this.root);
let x: FibonacciHeapNode<E> | undefined,

@@ -799,3 +803,3 @@ y: FibonacciHeapNode<E> | undefined,

for (const node of nodes) {
for (const node of elements) {
x = node;

@@ -802,0 +806,0 @@ d = x.degree;

831

src/data-structures/queue/deque.ts

@@ -8,10 +8,592 @@ /**

*/
import { DoublyLinkedList } from '../linked-list';
// O(n) time complexity of obtaining the value
// O(1) time complexity of adding at the beginning and the end
export class Deque<E = any> extends DoublyLinkedList<E> {
import { IterableWithSizeOrLength, IterateDirection } from "../../types";
import { calcMinUnitsRequired, rangeCheck, throwRangeError } from "../../utils";
/**
* Deque can provide random access with O(1) time complexity
* Deque is usually more compact and efficient in memory usage because it does not require additional space to store pointers.
* Deque may experience performance jitter, but DoublyLinkedList will not
* Deque is implemented using a dynamic array. Inserting or deleting beyond both ends of the array may require moving elements or reallocating space.
*/
export class DequeIterator<E> {
iterateDirection: IterateDirection;
index: number;
readonly deque: Deque<E>;
constructor(index: number, deque: Deque<E>, iterateDirection = IterateDirection.DEFAULT) {
this.index = index;
this.iterateDirection = iterateDirection;
if (this.iterateDirection === IterateDirection.DEFAULT) {
this.prev = function () {
if (this.index === 0) {
throwRangeError();
}
this.index -= 1;
return this;
};
this.next = function () {
if (this.index === this.deque.size) {
throwRangeError();
}
this.index += 1;
return this;
};
} else {
this.prev = function () {
if (this.index === this.deque.size - 1) {
throwRangeError();
}
this.index += 1;
return this;
};
this.next = function () {
if (this.index === -1) {
throwRangeError();
}
this.index -= 1;
return this;
};
}
this.deque = deque;
}
get current() {
return this.deque.getAt(this.index);
}
set current(newElement: E) {
this.deque.setAt(this.index, newElement);
}
isAccessible() {
return this.index !== this.deque.size;
}
prev(): DequeIterator<E> {
return this;
}
next(): DequeIterator<E> {
return this;
}
clone() {
return new DequeIterator<E>(this.index, this.deque, this.iterateDirection);
}
}
// O(1) time complexity of obtaining the value
export class Deque<E> {
protected _bucketFirst = 0;
protected _firstInBucket = 0;
protected _bucketLast = 0;
protected _lastInBucket = 0;
protected _bucketCount = 0;
protected readonly _bucketSize: number;
constructor(elements: IterableWithSizeOrLength<E> = [], bucketSize = (1 << 12)) {
let _size;
if ('length' in elements) {
_size = elements.length;
} else {
_size = elements.size;
}
this._bucketSize = bucketSize;
this._bucketCount = calcMinUnitsRequired(_size, this._bucketSize) || 1;
for (let i = 0; i < this._bucketCount; ++i) {
this._buckets.push(new Array(this._bucketSize));
}
const needBucketNum = calcMinUnitsRequired(_size, this._bucketSize);
this._bucketFirst = this._bucketLast = (this._bucketCount >> 1) - (needBucketNum >> 1);
this._firstInBucket = this._lastInBucket = (this._bucketSize - _size % this._bucketSize) >> 1;
for (const element of elements) {
this.push(element);
}
}
protected _buckets: E[][] = [];
get buckets() {
return this._buckets;
}
protected _size = 0;
get size() {
return this._size;
}
get first(): E | undefined {
if (this.size === 0) return;
return this._buckets[this._bucketFirst][this._firstInBucket];
}
get last(): E | undefined {
if (this.size === 0) return;
return this._buckets[this._bucketLast][this._lastInBucket];
}
/**
* Time Complexity: Amortized O(1) - Generally constant time, but resizing when the deque is full leads to O(n).
* Space Complexity: O(n) - In worst case, resizing doubles the array size.
*/
empty() {
return this._size === 0;
}
/**
* Time Complexity: O(1) - Removes the last element.
* Space Complexity: O(1) - Operates in-place.
*/
isEmpty() {
return this.size === 0;
}
/**
* Time Complexity: Amortized O(1) - Similar to push, resizing leads to O(n).
* Space Complexity: O(n) - Due to potential resizing.
*/
/**
* Time Complexity: O(1)
* Space Complexity: O(n) - In worst case, resizing doubles the array size.
*
* The addLast function adds an element to the end of an array.
* @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 {
this.push(element);
}
/**
* Time Complexity: O(1) - Removes the first element.
* Space Complexity: O(1) - In-place operation.
*/
/**
* Time Complexity: O(1) - Removes the last element.
* Space Complexity: O(1) - Operates in-place.
*
* The function "popLast" removes and returns the last element of an array.
* @returns The last element of the array is being returned.
*/
popLast(): E | undefined {
return this.pop();
}
/**
* Time Complexity: O(1).
* Space Complexity: O(n) - Due to potential resizing.
*
* The "addFirst" function adds an element to the beginning of an array.
* @param {E} element - The parameter "element" represents the element that you want to add to the
* beginning of the data structure.
*/
addFirst(element: E): void {
this.unshift(element);
}
/**
* Time Complexity: O(1) - Removes the first element.
* Space Complexity: O(1) - In-place operation.
*
* The function "popFirst" removes and returns the first element of an array.
* @returns The method `popFirst()` is returning the first element of the array after removing it
* from the beginning. If the array is empty, it will return `undefined`.
*/
popFirst(): E | undefined {
return this.shift();
}
clear() {
this._buckets = [new Array(this._bucketSize)];
this._bucketCount = 1;
this._bucketFirst = this._bucketLast = this._size = 0;
this._firstInBucket = this._lastInBucket = this._bucketSize >> 1;
}
begin() {
return new DequeIterator<E>(0, this);
}
end() {
return new DequeIterator<E>(this.size, this);
}
reverseBegin() {
return new DequeIterator<E>(this.size - 1, this, IterateDirection.REVERSE);
}
reverseEnd() {
return new DequeIterator<E>(-1, this, IterateDirection.REVERSE);
}
push(element: E) {
if (this.size) {
if (this._lastInBucket < this._bucketSize - 1) {
this._lastInBucket += 1;
} else if (this._bucketLast < this._bucketCount - 1) {
this._bucketLast += 1;
this._lastInBucket = 0;
} else {
this._bucketLast = 0;
this._lastInBucket = 0;
}
if (
this._bucketLast === this._bucketFirst &&
this._lastInBucket === this._firstInBucket
) this._reallocate();
}
this._size += 1;
this._buckets[this._bucketLast][this._lastInBucket] = element;
return this.size;
}
pop() {
if (this.size === 0) return;
const element = this._buckets[this._bucketLast][this._lastInBucket];
if (this.size !== 1) {
if (this._lastInBucket > 0) {
this._lastInBucket -= 1;
} else if (this._bucketLast > 0) {
this._bucketLast -= 1;
this._lastInBucket = this._bucketSize - 1;
} else {
this._bucketLast = this._bucketCount - 1;
this._lastInBucket = this._bucketSize - 1;
}
}
this._size -= 1;
return element;
}
unshift(element: E) {
if (this.size) {
if (this._firstInBucket > 0) {
this._firstInBucket -= 1;
} else if (this._bucketFirst > 0) {
this._bucketFirst -= 1;
this._firstInBucket = this._bucketSize - 1;
} else {
this._bucketFirst = this._bucketCount - 1;
this._firstInBucket = this._bucketSize - 1;
}
if (
this._bucketFirst === this._bucketLast &&
this._firstInBucket === this._lastInBucket
) this._reallocate();
}
this._size += 1;
this._buckets[this._bucketFirst][this._firstInBucket] = element;
return this.size;
}
shift() {
if (this.size === 0) return;
const element = this._buckets[this._bucketFirst][this._firstInBucket];
if (this.size !== 1) {
if (this._firstInBucket < this._bucketSize - 1) {
this._firstInBucket += 1;
} else if (this._bucketFirst < this._bucketCount - 1) {
this._bucketFirst += 1;
this._firstInBucket = 0;
} else {
this._bucketFirst = 0;
this._firstInBucket = 0;
}
}
this._size -= 1;
return element;
}
getAt(pos: number): E {
rangeCheck!(pos, 0, this.size - 1);
const {
bucketIndex,
indexInBucket
} = this._getBucketAndPosition(pos);
return this._buckets[bucketIndex][indexInBucket]!;
}
setAt(pos: number, element: E) {
rangeCheck!(pos, 0, this.size - 1);
const {
bucketIndex,
indexInBucket
} = this._getBucketAndPosition(pos);
this._buckets[bucketIndex][indexInBucket] = element;
}
insertAt(pos: number, element: E, num = 1) {
const length = this.size;
rangeCheck!(pos, 0, length);
if (pos === 0) {
while (num--) this.unshift(element);
} else if (pos === this.size) {
while (num--) this.push(element);
} else {
const arr: E[] = [];
for (let i = pos; i < this.size; ++i) {
arr.push(this.getAt(i));
}
this.cut(pos - 1);
for (let i = 0; i < num; ++i) this.push(element);
for (let i = 0; i < arr.length; ++i) this.push(arr[i]);
}
return this.size;
}
cut(pos: number) {
if (pos < 0) {
this.clear();
return 0;
}
const {
bucketIndex,
indexInBucket
} = this._getBucketAndPosition(pos);
this._bucketLast = bucketIndex;
this._lastInBucket = indexInBucket;
this._size = pos + 1;
return this.size;
}
deleteAt(pos: number) {
rangeCheck!(pos, 0, this.size - 1);
if (pos === 0) this.shift();
else if (pos === this.size - 1) this.pop();
else {
const length = this.size - 1;
let {
bucketIndex: curBucket,
indexInBucket: curPointer
} = this._getBucketAndPosition(pos);
for (let i = pos; i < length; ++i) {
const {
bucketIndex: nextBucket,
indexInBucket: nextPointer
} = this._getBucketAndPosition(pos + 1);
this._buckets[curBucket][curPointer] = this._buckets[nextBucket][nextPointer];
curBucket = nextBucket;
curPointer = nextPointer;
}
this.pop();
}
return this.size;
}
delete(element: E) {
const size = this.size;
if (size === 0) return 0;
let i = 0;
let index = 0;
while (i < size) {
const oldElement = this.getAt(i);
if (oldElement !== element) {
this.setAt(index, oldElement!);
index += 1;
}
i += 1;
}
this.cut(index - 1);
return this.size;
}
deleteByIterator(iter: DequeIterator<E>) {
const index = iter.index;
this.deleteAt(index);
iter = iter.next();
return iter;
}
findIterator(element: E) {
for (let i = 0; i < this.size; ++i) {
if (this.getAt(i) === element) {
return new DequeIterator<E>(i, this);
}
}
return this.end();
}
reverse() {
this._buckets.reverse().forEach(function (bucket) {
bucket.reverse();
});
const { _bucketFirst, _bucketLast, _firstInBucket, _lastInBucket } = this;
this._bucketFirst = this._bucketCount - _bucketLast - 1;
this._bucketLast = this._bucketCount - _bucketFirst - 1;
this._firstInBucket = this._bucketSize - _lastInBucket - 1;
this._lastInBucket = this._bucketSize - _firstInBucket - 1;
return this;
}
unique() {
if (this.size <= 1) {
return this.size;
}
let index = 1;
let prev = this.getAt(0);
for (let i = 1; i < this.size; ++i) {
const cur = this.getAt(i);
if (cur !== prev) {
prev = cur;
this.setAt(index++, cur);
}
}
this.cut(index - 1);
return this.size;
}
sort(comparator?: (x: E, y: E) => number) {
const arr: E[] = [];
for (let i = 0; i < this.size; ++i) {
arr.push(this.getAt(i));
}
arr.sort(comparator);
for (let i = 0; i < this.size; ++i) {
this.setAt(i, arr[i]);
}
return this;
}
shrinkToFit() {
if (this.size === 0) return;
const newBuckets = [];
if (this._bucketFirst === this._bucketLast) return;
else if (this._bucketFirst < this._bucketLast) {
for (let i = this._bucketFirst; i <= this._bucketLast; ++i) {
newBuckets.push(this._buckets[i]);
}
} else {
for (let i = this._bucketFirst; i < this._bucketCount; ++i) {
newBuckets.push(this._buckets[i]);
}
for (let i = 0; i <= this._bucketLast; ++i) {
newBuckets.push(this._buckets[i]);
}
}
this._bucketFirst = 0;
this._bucketLast = newBuckets.length - 1;
this._buckets = newBuckets;
}
forEach(callback: (element: E, index: number, deque: Deque<E>) => void) {
for (let i = 0; i < this.size; ++i) {
callback(this.getAt(i), i, this);
}
}
find(callback: (element: E, index: number, deque: Deque<E>) => boolean): E | undefined {
for (let i = 0; i < this.size; ++i) {
const element = this.getAt(i);
if (callback(element, i, this)) {
return element;
}
}
return undefined;
}
toArray(): E[] {
const arr: E[] = [];
for (let i = 0; i < this.size; ++i) {
arr.push(this.getAt(i));
}
return arr;
}
map<T>(callback: (element: E, index: number, deque: Deque<E>) => T): Deque<T> {
const newDeque = new Deque<T>([], this._bucketSize);
for (let i = 0; i < this.size; ++i) {
newDeque.push(callback(this.getAt(i), i, this));
}
return newDeque;
}
filter(predicate: (element: E, index: number, deque: Deque<E>) => boolean): Deque<E> {
const newDeque = new Deque<E>([], this._bucketSize);
for (let i = 0; i < this.size; ++i) {
const element = this.getAt(i);
if (predicate(element, i, this)) {
newDeque.push(element);
}
}
return newDeque;
}
reduce<T>(callback: (accumulator: T, element: E, index: number, deque: Deque<E>) => T, initialValue: T): T {
let accumulator = initialValue;
for (let i = 0; i < this.size; ++i) {
accumulator = callback(accumulator, this.getAt(i), i, this);
}
return accumulator;
}
indexOf(element: E): number {
for (let i = 0; i < this.size; ++i) {
if (this.getAt(i) === element) {
return i;
}
}
return -1;
}
* [Symbol.iterator]() {
for (let i = 0; i < this.size; ++i) {
yield this.getAt(i);
}
}
protected _reallocate(needBucketNum?: number) {
const newBuckets = [];
const addBucketNum = needBucketNum || this._bucketCount >> 1 || 1;
for (let i = 0; i < addBucketNum; ++i) {
newBuckets[i] = new Array(this._bucketSize);
}
for (let i = this._bucketFirst; i < this._bucketCount; ++i) {
newBuckets[newBuckets.length] = this._buckets[i];
}
for (let i = 0; i < this._bucketLast; ++i) {
newBuckets[newBuckets.length] = this._buckets[i];
}
newBuckets[newBuckets.length] = [...this._buckets[this._bucketLast]];
this._bucketFirst = addBucketNum;
this._bucketLast = newBuckets.length - 1;
for (let i = 0; i < addBucketNum; ++i) {
newBuckets[newBuckets.length] = new Array(this._bucketSize);
}
this._buckets = newBuckets;
this._bucketCount = newBuckets.length;
}
protected _getBucketAndPosition(pos: number) {
let bucketIndex: number;
let indexInBucket: number;
const overallIndex = this._firstInBucket + pos;
bucketIndex = this._bucketFirst + Math.floor(overallIndex / this._bucketSize);
if (bucketIndex >= this._bucketCount) {
bucketIndex -= this._bucketCount;
}
indexInBucket = (overallIndex + 1) % this._bucketSize - 1;
if (indexInBucket < 0) {
indexInBucket = this._bucketSize - 1;
}
return { bucketIndex, indexInBucket };
}
}
// O(1) time complexity of obtaining the element
// O(n) time complexity of adding at the beginning and the end

@@ -63,7 +645,7 @@ // todo tested slowest one

*
* The "addFirst" function adds a value to the beginning of an array-like data structure.
* @param {E} value - The `value` parameter represents the value that you want to add to the beginning of the data
* 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(value: E) {
addFirst(element: E) {
if (this.size === 0) {

@@ -76,3 +658,3 @@ const mid = Math.floor(this.capacity / 2);

}
this.nodes[this.first] = value;
this.nodes[this.first] = element;
this._size++;

@@ -90,6 +672,6 @@ }

*
* The addLast function adds a value to the end of an array-like data structure.
* @param {E} value - The `value` parameter represents the value that you want to add to the end of the data structure.
* 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(value: E) {
addLast(element: E) {
if (this.size === 0) {

@@ -102,3 +684,3 @@ const mid = Math.floor(this.capacity / 2);

}
this.nodes[this.last] = value;
this.nodes[this.last] = element;
this._size++;

@@ -117,11 +699,11 @@ }

* The function `popFirst()` removes and returns the first element in a data structure.
* @returns The value of the first element in the data structure.
* @returns The element of the first element in the data structure.
*/
popFirst() {
if (!this.size) return;
const value = this.getFirst();
const element = this.getFirst();
delete this.nodes[this.first];
this._first++;
this._size--;
return value;
return element;
}

@@ -155,7 +737,7 @@

* The `popLast()` function removes and returns the last element in a data structure.
* @returns The value that was removed from the data structure.
* @returns The element that was removed from the data structure.
*/
popLast() {
if (!this.size) return;
const value = this.getLast();
const element = this.getLast();
delete this.nodes[this.last];

@@ -165,3 +747,3 @@ this._last--;

return value;
return element;
}

@@ -198,6 +780,6 @@

* @returns The element at the specified index in the `_nodes` array is being returned. If there is no element at that
* index, `null` is returned.
* index, `undefined` is returned.
*/
get(index: number) {
return this.nodes[this.first + index] || null;
return this.nodes[this.first + index] || undefined;
}

@@ -207,3 +789,3 @@

* The function checks if the size of a data structure is less than or equal to zero.
* @returns The method is returning a boolean value indicating whether the size of the object is less than or equal to 0.
* @returns The method is returning a boolean element indicating whether the size of the object is less than or equal to 0.
*/

@@ -213,205 +795,2 @@ isEmpty() {

}
}
// O(1) time complexity of obtaining the value
// O(n) time complexity of adding at the beginning and the end
export class ArrayDeque<E> {
protected _nodes: E[] = [];
get nodes(): E[] {
return this._nodes;
}
get size() {
return this.nodes.length;
}
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*
* The function "addLast" adds a value to the end of an array.
* @param {E} value - The value parameter represents the value that you want to add to the end of the array.
* @returns The return value is the new length of the array after the value has been added.
*/
addLast(value: E) {
return this.nodes.push(value);
}
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*
* The function "popLast" returns and removes the last element from an array, or returns null if the array is empty.
* @returns The method `popLast()` returns the last element of the `_nodes` array, or `null` if the array is empty.
*/
popLast(): E | null {
return this.nodes.pop() ?? null;
}
/**
* Time Complexity: O(n)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(n)
* Space Complexity: O(1)
*
* The `popFirst` function removes and returns the first element from an array, or returns null if the array is empty.
* @returns The `popFirst()` function returns the first element of the `_nodes` array, or `null` if the array is
* empty.
*/
popFirst(): E | null {
return this.nodes.shift() ?? null;
}
/**
* Time Complexity: O(n)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(n)
* Space Complexity: O(1)
*
* The function "addFirst" adds a value to the beginning of an array.
* @param {E} value - The value parameter represents the value that you want to add to the beginning of the array.
* @returns The return value of the `addFirst` function is the new length of the array `_nodes` after adding the
* `value` at the beginning.
*/
addFirst(value: E) {
return this.nodes.unshift(value);
}
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*
* The `getFirst` function returns the first element of an array or null if the array is empty.
* @returns The function `getFirst()` is returning the first element (`E`) of the `_nodes` array. If the array is
* empty, it will return `null`.
*/
getFirst(): E | null {
return this.nodes[0] ?? null;
}
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*
* The `getLast` function returns the last element of an array or null if the array is empty.
* @returns The method `getLast()` returns the last element of the `_nodes` array, or `null` if the array is empty.
*/
getLast(): E | null {
return this.nodes[this.nodes.length - 1] ?? null;
}
/**
* 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, or null if the index is out of bounds.
* @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 method is returning the element at the specified index in the `_nodes` array. If the element exists, it
* will be returned. If the element does not exist (i.e., the index is out of bounds), `null` will be returned.
*/
get(index: number): E | null {
return this.nodes[index] ?? null;
}
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(1)
* Space Complexity: O(1)
*
* The set function assigns a value to a specific index in an array.
* @param {number} index - The index parameter is a number that represents the position of the element in the array
* that you want to set a new value for.
* @param {E} value - The value parameter represents the new value that you want to set at the specified index in the
* _nodes array.
* @returns The value that is being set at the specified index in the `_nodes` array.
*/
set(index: number, value: E) {
return (this.nodes[index] = value);
}
/**
* Time Complexity: O(n)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(n)
* Space Complexity: O(1)
*
* The insert function adds a value at a specified index in an array.
* @param {number} index - The index parameter specifies the position at which the value should be inserted in the
* array. It is a number that represents the index of the array where the value should be inserted. The index starts
* from 0, so the first element of the array has an index of 0, the second element has
* @param {E} value - The value parameter represents the value that you want to insert into the array at the specified
* index.
* @returns The splice method returns an array containing the removed elements, if any. In this case, since no elements
* are being removed, an empty array will be returned.
*/
insert(index: number, value: E) {
return this.nodes.splice(index, 0, value);
}
/**
* Time Complexity: O(n)
* Space Complexity: O(1)
*/
/**
* Time Complexity: O(n)
* Space Complexity: O(1)
*
* The delete function removes an element from an array at a specified index.
* @param {number} index - The index parameter specifies the position of the element to be removed from the array. It
* is a number that represents the index of the element to be removed.
* @returns The method is returning an array containing the removed element.
*/
delete(index: number) {
return this.nodes.splice(index, 1);
}
/**
* The function checks if an array called "_nodes" is empty.
* @returns The method `isEmpty()` is returning a boolean value. It returns `true` if the length of the `_nodes` array
* is 0, indicating that the array is empty. Otherwise, it returns `false`.
*/
isEmpty() {
return this.nodes.length === 0;
}
}
}

11

src/types/data-structures/hash/hash-map.ts

@@ -1,12 +0,1 @@

export const enum IterateDirection {
DEFAULT = 0,
REVERSE = 1
}
export type HashMapOptions<T> = {
sizeFunction?: number | (() => number);
fixedLength?: number;
forEach: (callback: (el: T) => void) => void;
};
export type HashMapLinkedNode<K, V> = {

@@ -13,0 +2,0 @@ key: K;

15

src/types/helpers.ts

@@ -12,1 +12,16 @@ export type Comparator<T> = (a: T, b: T) => number;

}
export const enum IterateDirection {
DEFAULT = 0,
REVERSE = 1
}
export interface IterableWithSize<T> extends Iterable<T> {
size: number;
}
export interface IterableWithLength<T> extends Iterable<T> {
length: number;
}
export type IterableWithSizeOrLength<T> = IterableWithSize<T> | IterableWithLength<T>

2

src/utils/utils.ts

@@ -100,1 +100,3 @@ /**

};
export const calcMinUnitsRequired = (totalQuantity: number, unitSize: number) => Math.floor((totalQuantity + unitSize - 1) / unitSize)
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