Common structures.
npm install @blackglory/structuressh
npm install --save @blackglory/structures
or
yarn add @blackglory/structures
`API
$3
`ts
class Box {
get [Symbol.toStringTag](): string constructor(value: T)
get(): T
set(value: T): void
}
`$3
#### convertConsToArray
`ts
function convertConsToArray([value, next]: Cons): T[]
`#### convertArrayToCons
`ts
function convertArrayToCons([value, ...next]: T[]): Cons
`$3
#### sliceArrayLeft
`ts
function sliceArrayLeft(arr: readonly T[], num: number): T[]
`#### sliceArrayRight
`ts
function sliceArrayRight(arr: readonly T[], num: number): T[]
`#### truncateArrayLeft
`ts
function truncateArrayLeft(arr: unknown[], num: number): void
`#### truncateArrayRight
`ts
function truncateArrayRight(arr: unknown[], num: number): void
`#### clearArray
`ts
function clearArray(arr: unknown[]): void
`$3
`ts
type Listener = (...args: Args) => voidclass Emitter<
EventToArgs extends Record = Record<
string | number | symbol
, unknown[]
>
, Event extends string | number | symbol = keyof EventToArgs
> {
get [Symbol.toStringTag](): string
on(event: T, listener: Listener): () => void
once(event: T, listener: Listener): () => void
emit(event: T, ...args: EventToArgs[T]): void
removeAllListeners(event: T): void
}
`$3
`ts
type Listener = (...args: Args) =>
| void
| Generatorclass GeneratorEmitter<
EventToArgs extends Record = Record<
string | number | symbol
, unknown[]
>
, Event extends string | number | symbol = keyof EventToArgs
, Yield = unknown
, Next = unknown
> {
get [Symbol.toStringTag](): string
on(
event: T
, listener: Listener
): () => void
once(
event: T
, listener: Listener
): () => void
emit(
event: T
, ...args: EventToArgs[T]
): Generator
removeAllListeners(event: T): void
}
`$3
`ts
type Listener = (...args: Args) =>
| void
| Generator
| AsyncGeneratorclass AsyncGeneratorEmitter<
EventToArgs extends Record = Record<
string | number | symbol
, unknown[]
>
, Event extends string | number | symbol = keyof EventToArgs
, Yield = unknown
, Next = unknown
> {
get [Symbol.toStringTag](): string
on(event: T
, listener: Listener
): () => void
once(
event: T
, listener: Listener
): () => void
emit(
event: T
, ...args: EventToArgs[T]
): AsyncGenerator
removeAllListeners(event: T): void
}
`$3
`ts
class BigMap implements Iterable<[K, V]> {
get [Symbol.toStringTag](): string get size(): number
set(key: K, value: V): void
has(key: K): boolean
get(key: K): V | undefined
delete(key: K): boolean
clear(): void
entries(): IterableIterator<[K, V]>
keys(): IterableIterator
values(): IterableIterator
}
`The
Map that supports unlimited elements.Note that
BigMap cannot preserve the insertion order of elements.`ts
// Map
const map = new Map()
for (let i = 0; i < 100_000_000; i++) {
map.set(i, null) // RangeError
}
console.log('Never')// BigMap
const { BigMap } = require('.')
const map = new BigMap()
for (let i = 0; i < 100_000_000; i++) {
map.set(i, null)
}
console.log('Done')
`$3
`ts
class BigSet implements Iterable {
get [Symbol.toStringTag]: string get size(): number
add(value: T): this
has(value: T): boolean
delete(value: T): boolean
clear(): void
values(): IterableIterator
}
`The
Set that supports unlimited elements.Note that
BigSet cannot preserve the insertion order of elements.`ts
// Set
const set = new Set()
for (let i = 0; i < 100_000_000; i++) {
set.add(i) // RangeError
}
console.log('Never')// BigSet
const set = new BigSet()
for (let i = 0; i < 100_000_000; i++) {
set.add(i)
}
console.log('Done')
`$3
`ts
class HashMap {
get [Symbol.toStringTag](): string
get size(): number constructor(hash: (key: K) => Hash)
set(key: K, value: V): this
has(key: K): boolean
get(key: K): V | undefined
delete(key: K): boolean
clear(): void
}
`$3
`ts
class HashSet implements Iterable {
get [Symbol.toStringTag](): string
get size(): number
[Symbol.iterator](): IterableIterator constructor(hash: (value: V) => Hash)
add(value: V): this
delete(value: V): boolean
has(value: V): boolean
get(value: V): V | undefined
clear(): void
keys(): IterableIterator
values(): IterableIterator
}
`$3
`ts
class LRUMap {
get [Symbol.toStringTag](): string
get size(): number constructor(limit: number)
set(key: K, value: V): this
has(key: K): boolean
get(key: K): V | undefined
delete(key: K): boolean
clear(): void
}
`$3
`ts
class ExpirableMap {
get[Symbol.toStringTag](): string
get size(): number constructor()
set(key: K, value: V, timeToLive?: number = Infinity): this
has(key: K): boolean
get(key: K): V | undefined
delete(key: K): boolean
clear(): void
}
`$3
`ts
class TLRUMap {
get[Symbol.toStringTag](): string
get size(): number constructor(limit: number)
set(key: K, value: V, timeToLive?: number = Infinity): this
has(key: K): boolean
get(key: K): V | undefined
delete(key: K): boolean
clear(): void
}
`$3
`ts
class Queue {
get [Symbol.toStringTag](): string
get size(): number empty(): void
enqueue(...items: T[]): void
dequeue(): T | undefined
remove(item: T): void
}
`$3
`ts
class TrieMap, V, T = unknown> {
get [Symbol.toStringTag](): string keys(): IterableIterator
values(): IterableIterator
entries(): IterableIterator<[key: T[], value: V]>
set(key: K, value: V): this
has(key: K): boolean
get(key: K): V | undefined
delete(key: K): boolean
}
`Note that you might expect this data structure to be more space efficient than
BigMap, but it doesn't.
In V8, it can only store about 80% of data of BigMap.$3
`ts
class StringTrieMap {
get [Symbol.toStringTag](): string keys(): IterableIterator
values(): IterableIterator
entries(): IterableIterator<[key: string, value: T]>
set(key: string, value: T): this
has(key: string): boolean
get(key: string): T | undefined
delete(key: string): boolean
}
`Note that you might expect this data structure to be more space efficient than
BigMap, but it doesn't.
In V8, it can only store about 80% of data of BigMap.$3
`ts
class RadixTree, V, T = unknown> {
get [Symbol.toStringTag](): string entries(): IterableIterator<[key: T[], value: V]>
keys(): IterableIterator
values(): IterableIterator
set(key: K, value: V): this
has(key: K): boolean
get(key: K): V | undefined
delete(key: K): boolean
}
`Note that you might expect this data structure to be more space efficient than
BigMap, but it doesn't.
In V8, it can only store about 80% of data of BigMap.$3
`ts
class StringRadixTree {
get [Symbol.toStringTag](): string keys(): IterableIterator
values(): IterableIterator
entries(): IterableIterator<[key: string, value: T]>
set(key: string, value: T): this
has(key: string): boolean
get(key: string): T | undefined
delete(key: string): boolean
}
`Note that you might expect this data structure to be more space efficient than
BigMap, but it doesn't.
In V8, it can only store about 80% of data of BigMap.$3
`ts
class SparseSet implements Iterable {
get [Symbol.toStringTag](): string
get [Symbol.iterator](): IterableIterator
get size(): number constructor(array?: number[])
values(): IterableIterator
has(value: number): boolean
add(value: number): void
delete(value: number): boolean
clear(): void
clone(): SparseSet
}
`$3
`ts
class SparseMap {
get [Symbol.toStringTag](): string
get size(): number /**
*
SparseMap cannot respond to any operations on the internal array,
* you must ensure that indexes accessed are less than the length of SparseMap.
*
* Keys do not correspond to indexes of the array.
*/
get internalArray(): T[] entries(): IterableIterator<[key: number, value: T]>
keys(): IterableIterator
values(): IterableIterator
getInternalIndexOfKey(key: number): number | undefined
has(key: number): boolean
get(key: number): T | undefined
set(key: number, value: T): void
delete(key: number): void
clear(): void
}
`$3
`ts
class DynamicTypedArray {
get [Symbol.toStringTag](): string
get BYTES_PER_ELEMENT(): number
get capacity(): number
get length(): number
readonly growthFactor: number /**
*
DynamicTypedArray cannot respond to any operations on the internal array,
* you must ensure that indexes accessed are less than the length of DynamicTypedArray.
*/
get internalTypedArray(): TypedArrayOfConstructor constructor(
typedArrayConstructor: T
, options?: {
capacity?: number = 0
growthFactor?: number = 1.5
}
)
set(index: number, value: number): void
setValues(index: number, values: TypedArrayOfConstructor): void
get(index: number): number | undefined
push(...values: number[]): void
pop(): number | undefined
clear(): void
sort(compare?: (a: number, b: number) => number): void
}
`$3
`ts
class TypedSparseSet {
get [Symbol.toStringTag](): string
get [Symbol.iterator](): IterableIterator
get size(): number constructor(array: DynamicTypedArray)
values(): IterableIterator
has(value: number): boolean
add(value: number): void
delete(value: number): boolean
clear(): void
}
`$3
`ts
class TypedSparseMap {
get [Symbol.toStringTag](): string
get size(): number /**
*
SparseMap cannot respond to any operations on the internal array,
* you must ensure that indexes accessed are less than the length of SparseMap.
*
* Keys do not correspond to indexes of the array.
*/
get internalTypedArray(): TypedArrayOfConstructor constructor(array: DynamicTypedArray)
entries(): IterableIterator<[key: number, value: number]>
keys(): IterableIterator
values(): IterableIterator
getInternalIndexOfKey(key: number): number | undefined
has(key: number): boolean
get(key: number): T | undefined
set(key: number, value: number): void
delete(key: number): void
clear(): void
}
`$3
`ts
class SortedSet {
get [Symbol.toStringTag](): string
[Symbol.iterator](): IterableIterator constructor(compare: (a: T, b: T) => number)
values(): IterableIterator
has(value: T): boolean
add(value: T): void
delete(value: T): void
}
`$3
`ts
class BitSet {
get [Symbol.toStringTag](): string
get size(): number
[Symbol.iterator](): IterableIterator constructor(bitsPerElement: number = 8)
values(): IterableIterator
has(value: number): boolean
add(value: number): boolean
delete(value: number): boolean
clear(): void
clone(): BitSet
}
`Due to the length of arrays supported by JavaScript,
BitSet cannot support very large values.$3
`ts
class TypedBitSet {
get [Symbol.toStringTag](): string
get size(): number
[Symbol.iterator](): IterableIterator constructor(array: DynamicTypedArray)
values(): IterableIterator
has(value: number): boolean
add(value: number): boolean
delete(value: number): boolean
clear(): void
}
`Due to the length of arrays supported by JavaScript,
TypedBitSit cannot support very large values.$3
`ts
class DisjointSet {
has(value: number): boolean
sets(): number[][] makeSet(value: number): number
union(a: number, b: number): void
find(value: number): number
}
``