structures

Common structures.

Install

``sh
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) => void

class 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
| Generator

class 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
| AsyncGenerator

class 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
}
``