Cube Library Documentation
Summary
The Cube library is a versatile, high-performance collection of utilities and
data structures designed to simplify the process of building complex software
applications. Written in TypeScript, this library offers a collection of robust,
well-documented classes that cover a wide range of use cases.
The goal behind the Cube library is to provide developers with a set of
foundational tools that can be used to solve complex problems more efficiently.
By doing so, it aims to streamline the process of software development, allowing
developers to focus more on the unique aspects of their applications and less on
reinventing common data structures.
One of the key advantages of the Cube library is its speed. The data structures
provided are highly optimized for performance, ensuring that operations are
performed as quickly as possible. This makes it a suitable choice for
performance-critical applications.
Moreover, the Cube library is designed with flexibility in mind. It not only
supports a wide range of use cases out of the box, but also allows developers to
easily extend and adapt these data structures to suit their specific needs.
Here's a snapshot of the main classes provided by the Cube library:
-
Heap: This class implements a heap data structure, commonly used in
algorithms that require efficient operations on a collection of elements
based on their priorities.
-
Trie: This class provides a Trie (or prefix tree) data structure, which
is especially useful when dealing with string keys.
-
LinkedList: This class implements a doubly-linked list data structure,
which is ideal for scenarios where efficient insertions and deletions are
required.
-
CircularList: This class implements a circular linked list, which is
useful in various applications like computer system resource allocation,
navigation systems, and time-sharing problems in operating systems.
-
Stack: This class offers a stack data structure, following the LIFO (Last
In First Out) principle. It is commonly used in scenarios like parsing,
backtracking algorithms, and function call stacks.
-
Queue, Buffer, and FQueue: These classes provide different types of queue
data structures, supporting use cases from basic FIFO operations to
frequency-based queueing.
-
LFU and LRU: These classes implement LFU (Least Frequently Used) and LRU
(Least Recently Used) caching algorithms, which are useful for optimizing
memory use in applications that deal with large amounts of data.
-
PubSub and Channel: These classes facilitate the Publish-Subscribe
messaging pattern, which is widely used in event-driven architectures.
-
BloomFilter: This class implements a Bloom filter, a probabilistic data
structure that allows for fast membership queries, used in applications like
web browsers, databases, caching systems, and network routers.
-
QuadTree: This class implements a quadtree, a tree data structure that
can be used to partition a two-dimensional space by recursively subdividing
it into four quadrants or regions, useful in applications like geographical
information systems (GIS), image processing, game development, computer
graphics, image recognition, spatial indexing, wireless networking,
geospatial data, and physics simulations.
Each of these classes comes with thorough documentation, including interface
details and usage examples.
Usage Deno
import {
BloomFilter,
Buffer,
Channel,
CircularList,
FQueue,
Heap,
LFU,
LinkedList,
LRU,
PubSub,
QuadTree,
Queue,
Stack,
Trie,
} from "https://deno.land/x/cube/mod.ts";
Usage Node
import * as cube from "@denox/cube";
Heap
Heap is a data structure that maintains a collection of elements, with the
operations to insert a new element, and remove and return the element with the
highest priority according to some comparison function. This is a class
implementation in TypeScript that is generic, meaning it can hold any data type,
not just numbers.
Use Cases
Heaps are used in various algorithms and data structures for efficient
operations, including:
- Priority Queues: Heaps are commonly used to implement priority queues,
where items are removed from the queue in order of their priority.
- Heap Sort: Heap sort is a comparison-based sorting algorithm that uses a
binary heap data structure.
- Graph Algorithms: Many graph algorithms such as Dijkstra's and Prim's use
heaps to select the next node to visit quickly.
- Sliding Window Maximum: In problems where we need to find the maximum
element in every contiguous subarray of a given size, heaps offer an efficient
solution.
Interface Documentation
Constructor
constructor(compareFn: (a: T, b: T) => number, entries?: readonly T[])
Creates a new Heap. The compareFn
parameter is a function used to determine
the order of elements. This function should return a positive number if a
is
considered higher priority than b
, a negative number if b
is considered
higher priority than a
, and 0
if they are considered equal priority.
The entries
parameter is an optional array of elements to initialize the heap.
If provided, the heap is built from these elements.
push
push(item: T): this
Inserts a new item into the heap and returns the heap for chaining.
pop
pop(): T | undefined
Removes and returns the highest priority item according to the comparison
function. If the heap is empty, undefined
is returned.
peek
peek(): T | undefined
Returns the highest priority item according to the comparison function without
removing it from the heap. If the heap is empty, undefined
is returned.
size
get size(): number
Returns the number of elements in the heap.
Examples
import Heap from "./heap";
const maxHeap = new Heap<number>((a, b) => b - a);
maxHeap.push(1).push(2).push(3);
console.log(maxHeap.pop());
console.log(maxHeap.size);
const minHeap = new Heap<number>((a, b) => a - b, [3, 1, 4, 1, 5, 9]);
console.log(minHeap.pop());
console.log(minHeap.peek());
In the first example, a max heap is created where the highest number is
considered the highest priority. In the second example, a min heap is created
from an existing array where the lowest number is considered the highest
priority.
Trie
Trie, also known as a prefix tree, is a tree-like data structure that is used to
store a collection where the keys are usually strings. Each node of the trie
denotes a common prefix of some keys. This particular class implementation in
TypeScript is generic and supports keys as arrays of arbitrary elements, not
just characters, with associated values.
Use Cases
Trie data structures are useful in various scenarios, including:
- Autocomplete: Tries are often used in autocomplete features in IDEs, web
browsers, and text editors. They allow fast retrieval of items given a prefix.
- Spell Checkers: Tries can be used to implement spell checkers. Given a
word, the program can search in the trie to check if the word exists in the
dictionary.
- IP Routing: Tries can be used in IP routing to store routing information,
where the key can be an IP address split into parts.
- Group by Prefix: Given a list of keys, Tries can be used to group them by
common prefixes.
Interface Documentation
Constructor
constructor(entries?: readonly [K[], V][])
Creates a new Trie. The entries
parameter is an optional array of key-value
pairs to initialize the trie. If provided, the trie is built from these
key-value pairs.
set
set(keys: K[], value: V): this
Inserts or updates a key-value pair in the trie.
get
get(keys: K[]): V | undefined
Returns the value associated with a key. If the key is not found, undefined
is
returned.
has
has(keys: K[]): boolean
Checks if the trie contains a key.
delete
delete(keys: K[]): boolean
Removes a key-value pair from the trie. Returns true
if the key was found and
deleted, false
otherwise.
clear
clear(): void
Removes all key-value pairs from the trie.
size
get size(): number
Returns the number of key-value pairs in the trie.
match
*match(keys: K[]): IterableIterator<[K[], V]>
Returns an iterator that yields all key-value pairs in the trie that match the
given prefix. The match method will get all the values that partially match the
path, e.g., ancestor nodes plus the current node.
list
*list(keys: K[]): IterableIterator<[K[], V]>
Returns an iterator that yields all key-value pairs in the trie that are
children of the given prefix. The list method will get all the values starting
with the path, e.g., descendant nodes plus the current node.
keys
*keys(): IterableIterator<K[]>
Returns an iterator that yields all keys in the trie.
values
*values(): IterableIterator<V>
Returns an iterator that yields all values in the trie.
entries
*entries(): IterableIterator<[K[], V]>
Returns an iterator that yields all key-value pairs in the trie.
forEach
forEach(callbackFn: (value: V, key: K[], map: this) => void, thisArg?: unknown): void
Executes a provided function once for each key-value pair in the trie.
Examples
import Trie from "./trie";
const trie = new Trie<string, number>();
trie.set(["h", "e", "l", "l", "o"], 1);
console.log(trie.get(["h", "e", "l", "l", "o"]));
console.log(trie.has(["w", "o", "r", "l", "d"]));
for (const [key, value] of trie) {
console.log(key.join(""), value);
}
trie.delete(["h", "e", "l", "l", "o"]);
console.log(trie.size);
In this example, a new trie is created and a key-value pair is inserted into it.
Then, the value associated with the key is retrieved, and the presence of
another key is checked. The trie is then iterated over, and finally, the
key-value pair is deleted.
LinkedList
A LinkedList is a linear data structure where each element is a separate object.
Each element (node) of a list is comprising of two items - the value and a
reference to the next node. The last node has a reference to null. The entry
point into a linked list is called the head of the list. This TypeScript class
provides a generic implementation of a doubly-linked list, where each node has a
reference to both the next node and the previous node.
Use Cases
LinkedLists are used in various scenarios, including:
- Dynamic Memory Allocation: LinkedLists are used where you need to allocate
memory dynamically.
- Implementing Stacks and Queues: LinkedLists are used to implement other
data structures like stacks and queues.
- Performing operations like insertions and deletions at a specific place:
LinkedLists are preferable over arrays because unlike arrays, we don’t need to
shift elements in case of insertions or deletions.
Interface Documentation
Constructor
constructor(entries?: readonly T[])
Creates a new LinkedList. The entries
parameter is an optional array of
elements to initialize the list. If provided, the list is built from these
elements.
append
append(value: T, prevRef = this.#tail): Ref
Adds a new element to the end of the list and returns a reference to the new
element. The prevRef
parameter is an optional reference to the element to
insert after.
prepend
prepend(value: T, nextRef = this.#head): Ref
Adds a new element to the start of the list and returns a reference to the new
element. The nextRef
parameter is an optional reference to the element to
insert before.
prev
prev(key: Ref): Ref | undefined
Returns a reference to the element before the element with the given reference.
next
next(key: Ref): Ref | undefined
Returns a reference to the element after the element with the given reference.
has
has(key: Ref): boolean
Checks if the list contains an element with the given reference.
get
get(key: Ref): T | undefined
Returns the value of the element with the given reference. If no such element
exists, undefined
is returned.
delete
delete(key: Ref): boolean
Removes the element with the given reference from the list. Returns true
if
the element was found and deleted, false
otherwise.
clear
clear(): void
Removes all elements from the list.
size
get size(): number
Returns the number of elements in the list.
head
get head(): Ref | undefined
Returns a reference to the first element in the list.
tail
get tail(): Ref | undefined
Returns a reference to the last element in the list.
keys
*keys(): IterableIterator<T>
Returns an iterator that yields all elements in the list from first to last.
values
*values(): IterableIterator<T>
Returns an iterator that yields all elements in the list from first to last.
entries
*entries(): IterableIterator<[T, T]>
Returns an iterator that yields all elements in the list from first to last,
with each element paired with itself.
forEach
forEach(callbackFn: (value: T, key: T, map: this) => void, thisArg?: unknown): void
Executes a provided function once for each element in the list from first to
last.
Examples
import LinkedList from "./list";
const list = new LinkedList<number>();
let ref = list.append(1);
list.append(2, ref);
console.log(list.get(ref));
ref = list.next(ref)!;
console.log(list.get(ref));
for (const value of list) {
console.log(value);
}
list.clear();
console.log(list.size);
In this example, a new linked list is created and elements are added to it.
Then, the value of a specific element is retrieved, and the reference is moved
to the next element. The list is then iterated over, and finally, all elements
are removed from the list.
CircularList
The CircularList
class in this TypeScript file is an implementation of a
circular linked list. A circular linked list is a linked list where all nodes
are connected to form a circle. There is no NULL at the end. A circular linked
list can be a singly circular linked list or doubly circular linked list.
Use Cases
Circular linked lists are used in various applications, including:
- Computer system resources allocation: In systems where multiple processes
share resources in a circular manner.
- Navigation systems: Circular linked lists can represent places to visit in
a specific order, allowing for cycling through the list.
- Operating Systems: Used in the implementation of time-sharing problems,
where the currently running process is pushed back to the end of the queue
after the time quantum expires.
Interface Documentation
Constructor
constructor(entries?: readonly T[])
Creates a new CircularList
. The entries
parameter is an optional array to
initialize the circular list.
push
push(value: T): this
Adds a new node with the given value to the circular list.
pop
pop(): T | undefined
Removes the node from the circular list that the internal cursor points to and
returns its value. Returns undefined
if the list is empty.
peek
peek(): T | undefined
Returns the value of the node that the internal cursor points to without
removing it from the list. Returns undefined
if the list is empty.
clear
clear(): void
Clears the circular list.
rotate
protected rotate(): this
Rotates the list by moving the cursor to the next node.
size
get size(): number
Returns the number of nodes in the list.
Symbol.iterator, keys, values
*[Symbol.iterator](): IterableIterator<T>
*keys(): IterableIterator<T>
*values(): IterableIterator<T>
These methods return an iterator that yields all values in the list in the order
they are linked in the list.
entries
*entities(): IterableIterator<[T, T]>
Returns an iterator that yields all key-value pairs in the list, where both the
key and value are the value of the node.
forEach
forEach(callbackFn: (value: T, key: T, map: this) => void, thisArg?: unknown): void
Executes a provided function once for each node in the list.
Examples
import CircularList from "./circular";
const list = new CircularList<number>();
list.push(1).push(2).push(3);
console.log(list.size);
console.log(list.peek());
console.log(list.pop());
console.log(list.size);
for (const value of list) {
console.log(value);
}
list.clear();
console.log(list.size);
In this example, we first create a CircularList
and push some elements into
it. Then, we peek at and pop the next element, and print the size of the list.
After that, we iterate over the list and print each value. Finally, we clear the
list and print its size.
Stack
A Stack is a linear data structure that follows a particular order in which
operations are performed. The order is LIFO (Last In First Out), meaning the
last element inserted will be the first one to get accessed. This TypeScript
class provides a generic implementation of the stack data structure.
Use Cases
Stacks are used in various algorithms and data structures, including:
- Parsing: Stacks are used in compilers and parsers. For instance, they're
used to check whether parentheses in an expression are balanced.
- Undo Mechanism: Stacks can be used to provide the undo mechanism in text
editors or image editing tools.
- Backtracking Algorithms: Stacks are used in algorithms like depth-first
search (DFS) where you need to remember the previous state to backtrack.
- Function Call Stack: Stacks are used in almost every modern programming
language to handle function calls.
Interface Documentation
Constructor
constructor(entries?: readonly T[])
Creates a new Stack. The entries
parameter is an optional array of elements to
initialize the stack. If provided, the stack is built from these elements.
push
push(value: T): this
Adds a new element onto the top of the stack and returns the stack for chaining.
pop
pop(): T | undefined
Removes and returns the top element from the stack. If the stack is empty,
undefined
is returned.
peek
peek(): T | undefined
Returns the top element from the stack without removing it. If the stack is
empty, undefined
is returned.
clear
clear(): void
Removes all elements from the stack.
size
get size(): number
Returns the number of elements in the stack.
keys
*keys(): IterableIterator<T>
Returns an iterator that yields all elements in the stack from top to bottom.
values
*values(): IterableIterator<T>
Returns an iterator that yields all elements in the stack from top to bottom.
entries
*entries(): IterableIterator<[T, T]>
Returns an iterator that yields all elements in the stack from top to bottom,
with each element paired with itself.
forEach
forEach(callbackFn: (value: T, key: T, map: this) => void, thisArg?: unknown): void
Executes a provided function once for each element in the stack from top to
bottom.
Examples
import Stack from "./stack";
const stack = new Stack<number>();
stack.push(1).push(2).push(3);
console.log(stack.pop());
console.log(stack.size);
for (const value of stack) {
console.log(value);
}
stack.clear();
console.log(stack.size);
In this example, a new stack is created and elements are pushed onto it. Then,
the top element is popped from the stack. The stack is then iterated over, and
finally, all elements are removed from the stack.
Queue
A Queue is a linear data structure that follows a particular order in which
operations are performed. The order is FIFO (First In First Out), meaning the
first element inserted will be the first one to get accessed. This TypeScript
class provides a generic implementation of the queue data structure.
Use Cases
Queues are used in various algorithms and data structures, including:
- Scheduling: Queues are used in CPU scheduling, Disk Scheduling, and more.
- Handling requests: Queues are used in servers to handle requests where you
need to maintain the order of execution.
- Breadth-First Search (BFS): In graph algorithms, queues are used to hold
nodes to visit.
- Buffering: Queues are used in many places as buffers. They help in
handling asynchronous data transfer between two processes.
Interface Documentation
Constructor
constructor(entries?: readonly T[])
Creates a new Queue. The entries
parameter is an optional array of elements to
initialize the queue. If provided, the queue is built from these elements.
push
push(value: T): this
Adds a new element to the end of the queue and returns the queue for chaining.
pop
pop(): T | undefined
Removes and returns the first element from the queue. If the queue is empty,
undefined
is returned.
peek
peek(): T | undefined
Returns the first element from the queue without removing it. If the queue is
empty, undefined
is returned.
clear
clear(): void
Removes all elements from the queue.
size
get size(): number
Returns the number of elements in the queue.
keys
*keys(): IterableIterator<T>
Returns an iterator that yields all elements in the queue from first to last.
values
*values(): IterableIterator<T>
Returns an iterator that yields all elements in the queue from first to last.
entries
*entries(): IterableIterator<[T, T]>
Returns an iterator that yields all elements in the queue from first to last,
with each element paired with itself.
forEach
forEach(callbackFn: (value: T, key: T, map: this) => void, thisArg?: unknown): void
Executes a provided function once for each element in the queue from first to
last.
Examples
import Queue from "./queue";
const queue = new Queue<number>();
queue.push(1).push(2).push(3);
console.log(queue.pop());
console.log(queue.size);
for (const value of queue) {
console.log(value);
}
queue.clear();
console.log(queue.size);
In this example, a new queue is created and elements are added to it. Then, the
first element is popped from the queue. The queue is then iterated over, and
finally, all elements are removed from the queue.
Buffer
A Buffer is a variant of the Queue data structure with a fixed size. When the
buffer reaches its maximum size, if a new element is inserted, then the oldest
element in the buffer will be removed automatically. This TypeScript class
provides a generic implementation of a circular buffer or ring buffer.
Use Cases
Buffers are used in various algorithms and data structures, including:
- Data Stream: Buffers can be used when you have a stream of data at a
higher rate than you can process and you don't want to lose any data. The data
can be placed in a buffer and processed at a slower rate.
- Producer-Consumer Problem: In multitasking operating systems where there
are multiple processes, each process might need to communicate with one
another. Buffers are used as a temporary storage place for this data.
- I/O Operations: Buffers are used in I/O operations where data is
temporarily held before it is written to the device.
Interface Documentation
Constructor
constructor(maxSize: number = Infinity, entries?: readonly T[])
Creates a new Buffer. The maxSize
parameter is the maximum number of elements
that the buffer can hold. The entries
parameter is an optional array of
elements to initialize the buffer. If provided, the buffer is built from these
elements, but only the last maxSize
elements are kept.
push
push(value: T): this
Adds a new element to the end of the buffer and returns the buffer for chaining.
If adding the new element causes the buffer to exceed its maxSize
, the oldest
element is automatically removed.
maxSize
readonly maxSize: number
Returns the maximum number of elements that the buffer can hold.
Note: All other methods from the Queue class, such as pop()
, peek()
,
clear()
, size
, keys()
, values()
, entries()
, and forEach()
, are also
available.
Examples
import Buffer from "./buffer";
const buffer = new Buffer<number>(2);
buffer.push(1).push(2).push(3);
console.log(buffer.pop());
console.log(buffer.size);
for (const value of buffer) {
console.log(value);
}
buffer.clear();
console.log(buffer.size);
In this example, a new buffer is created with a maximum size of 2 and elements
are added to it. Note that when the third element is added, the first element is
automatically removed to maintain the maximum size. Then, the last element is
popped from the buffer. The buffer is then iterated over, and finally, all
elements are removed from the buffer.
FQueue
FQueue is a variant of the queue data structure, where elements are organized by
their frequency. Elements with the same frequency are dequeued in the order they
were enqueued. This TypeScript class provides a generic implementation of a
frequency queue.
Use Cases
Frequency queues are used in various scenarios, including:
- Caching: FQueues can be used in caching where you might want to replace
the item that is the least frequently used.
- Data Analysis: In data analysis, FQueues can be used where you want to
keep track of the frequency of items.
- Priority Queues: FQueues can be used as a form of priority queue where the
priority is based on frequency.
Interface Documentation
Constructor
constructor(entries?: readonly T[])
Creates a new FQueue. The entries
parameter is an optional array of elements
to initialize the queue. If provided, the queue is built from these elements.
push
push(value: T): this
Adds a new element to the queue. If the element already exists in the queue, its
frequency is increased.
pop
pop(): T | undefined
Removes and returns the least frequent element from the queue. If there are
multiple elements with the same frequency, the oldest one is returned. If the
queue is empty, undefined
is returned.
peek
peek(): T | undefined
Returns the least frequent element from the queue without removing it. If there
are multiple elements with the same frequency, the oldest one is returned. If
the queue is empty, undefined
is returned.
clear
clear(): void
Removes all elements from the queue.
size
get size(): number
Returns the number of elements in the queue.
keys
*keys(): IterableIterator<T>
Returns an iterator that yields all elements in the queue from least frequent to
most frequent.
values
*values(): IterableIterator<T>
Returns an iterator that yields all elements in the queue from least frequent to
most frequent.
entries
*entries(): IterableIterator<[T, T]>
Returns an iterator that yields all elements in the queue from least frequent to
most frequent, with each element paired with itself.
forEach
forEach(callbackFn: (value: T, key: T, map: this) => void, thisArg?: unknown): void
Executes a provided function once for each element in the queue from least
frequent to most frequent.
Examples
import FQueue from "./fqueue";
const fqueue = new FQueue<number>();
fqueue.push(1).push(2).push(2);
console.log(fqueue.pop());
console.log(fqueue.size);
for (const value of fqueue) {
console.log(value);
}
fqueue.clear();
console.log(fqueue.size);
In this example, a new frequency queue is created and elements are added to it.
Note that when the element 2
is pushed twice, its frequency increases. Then,
the least frequent element is popped from the queue. The queue is then iterated
over, and finally, all elements are removed from the queue.
LFU (Least Frequently Used)
The LFU class is an implementation of the Least Frequently Used (LFU) caching
algorithm. It is a type of cache algorithm used to manage memory within a cache.
When the cache reaches its limit, the LFU algorithm frees up memory by evicting
the least frequently used items first. This TypeScript class provides a generic
implementation of the LFU algorithm.
Use Cases
The LFU is used in various scenarios, including:
- Caching: LFU is a popular caching algorithm used in databases,
filesystems, and caching solutions.
- Web Development: In web development, LFU can be used for HTTP caching,
database query result caching, and more.
- Operating Systems: LFU can be used in page replacement algorithms and in
buffer cache management of a file system.
Interface Documentation
Constructor
constructor(maxSize: number, entries?: readonly (readonly [K, V])[] | null)
Creates a new LFU cache. The maxSize
parameter is the maximum number of
key-value pairs that the cache can hold. The entries
parameter is an optional
array of key-value pairs to initialize the cache. If provided, the cache is
built from these key-value pairs.
peek
peek(key: K): V | undefined
Returns the value associated with a key without affecting the cache state. If
the key is not found, undefined
is returned.
get
get(key: K): V | undefined
Returns the value associated with a key and updates the "used" state of the key.
If the key is not found, undefined
is returned.
set
set(key: K, value: V): this
Inserts or updates a key-value pair in the cache. If the cache is full, the
least frequently used item is removed. It returns the cache object itself, so
you can chain multiple set operations if desired.
keys
*keys(): IterableIterator<K>
Returns an iterator that yields all keys in the cache from least frequently used
to most frequently used.
values
*values(): IterableIterator<V>
Returns an iterator that yields all values in the cache from least frequently
used to most frequently used.
entries
*entries(): IterableIterator<[K, V]>
Returns an iterator that yields all key-value pairs in the cache from least
frequently used to most frequently used.
forEach
forEach(callbackFn: (value: V, key: K, map: this) => void, thisArg?: unknown): void
Executes a provided function once for each key-value pair in the cache from
least frequently used to most frequently used.
Examples
import LFU from "./lfu";
const lfu = new LFU<number, string>(2);
lfu.set(1, "a").set(2, "b").set(2, "b").set(3, "c");
console.log(lfu.get(1));
console.log(lfu.get(2));
for (const [key, value] of lfu) {
console.log(key, value);
}
In this example, a new LFU cache is created with a maximum size of 2 and
key-value pairs are added to it. Note that when the third key-value pair is
added, the key 1
is automatically removed as it is the least frequently used
key. Then, the value associated with key 1
is retrieved, which is undefined
since key 1
was removed from the cache. The value associated with key 2
is
then retrieved. Finally, the cache is iterated over.
LRU (Least Recently Used)
The LRU class is an implementation of the Least Recently Used (LRU) caching
algorithm. It is a type of cache algorithm used to manage memory within a cache.
When the cache reaches its limit, the LRU algorithm frees up memory by evicting
the least recently used items first. This TypeScript class provides a generic
implementation of the LRU algorithm.
Use Cases
The LRU is used in various scenarios, including:
- Caching: LRU is a popular caching algorithm used in databases,
filesystems, and caching solutions.
- Web Development: In web development, LRU can be used for HTTP caching,
database query result caching, and more.
- Operating Systems: LRU can be used in page replacement algorithms and in
buffer cache management of a file system.
Interface Documentation
Constructor
constructor(maxSize: number, entries?: readonly (readonly [K, V])[] | null)
Creates a new LRU cache. The maxSize
parameter is the maximum number of
key-value pairs that the cache can hold. The entries
parameter is an optional
array of key-value pairs to initialize the cache. If provided, the cache is
built from these key-value pairs.
peek
peek(key: K): V | undefined
Returns the value associated with a key without affecting the cache state. If
the key is not found, undefined
is returned.
get
get(key: K): V | undefined
Returns the value associated with a key and updates the "used" state of the key.
If the key is not found, undefined
is returned.
set
set(key: K, value: V): this
Inserts or updates a key-value pair in the cache. If the cache is full, the
least recently used item is removed. It returns the cache object itself, so you
can chain multiple set operations if desired.
keys
*keys(): IterableIterator<K>
Returns an iterator that yields all keys in the cache from least recently used
to most recently used.
values
*values(): IterableIterator<V>
Returns an iterator that yields all values in the cache from least recently used
to most recently used.
entries
*entries(): IterableIterator<[K, V]>
Returns an iterator that yields all key-value pairs in the cache from least
recently used to most recently used.
Examples
import LRU from "./lru";
const lru = new LRU<number, string>(2);
lru.set(1, "a").set(2, "b").set(3, "c");
console.log(lru.get(1));
console.log(lru.get(2));
for (const [key, value] of lru) {
console.log(key, value);
}
In this example, a new LRU cache is created with a maximum size of 2 and
key-value pairs are added to it. Note that when the third key-value pair is
added, the key 1
is automatically removed as it is the least recently used
key. Then, the value associated with key 1
is retrieved, which is undefined
since key 1
was removed from the cache. The value associated with key 2
is
then retrieved. Finally, the cache is iterated over.
PubSub
The PubSub
class is an implementation of the Publish-Subscribe messaging
pattern. It allows any number of publishers to publish messages without
programming them to send the messages to specific receivers (subscribers).
Likewise, subscribers can receive messages without knowing the identity of the
publishers.
Use Cases
The Publish-Subscribe pattern is widely used in asynchronous systems and are
very common in event-driven programming. Some common use cases include:
- Real-time updates: PubSub can be used for pushing real-time updates to
users, such as news updates, weather updates, or stock market information.
- Event-driven architectures: In an event-driven system, different
components of the system publish events, and other components subscribe to
events of interest.
- Decoupling services in a microservices architecture: Different services in
a microservices architecture can communicate with each other using the PubSub
pattern, making the services loosely coupled.
Interface Documentation
Constructor
constructor(maxSize: number = 0, entries?: readonly ([K[], V])[])
Creates a new PubSub
instance. The maxSize
parameter determines the size of
the buffer for the PubSub instance, and the entries
parameter is an optional
array of topic-data pairs to initialize the buffer.
publish
publish(context: V, topic: K[] = []): void
Publishes data to a specific topic. The context
parameter is the data to be
published, and the topic
parameter is the topic to which the data should be
published.
subscribe
subscribe(handler: Handler<K, V>, topic: K[] = []): () => void
Subscribes to a specific topic. The handler
parameter is a function to be
executed whenever data is published to the topic. The topic
parameter is the
topic to which the handler should be subscribed.
The subscribe
method returns a function that, when called, will unsubscribe
the handler from the topic.
Examples
import PubSub from "./pubsub";
const pubsub = new PubSub<string, string>();
const handler = (context, topic) => {
console.log(`Received ${context} on topic ${topic.join("/")}`);
};
const unsubscribe = pubsub.subscribe(handler, ["topic1"]);
pubsub.publish("Hello, world!", ["topic1"]);
unsubscribe();
Channel
The Channel
class in this TypeScript file serves as an interface into a subset
of a dispatcher, specifically a PubSub
instance. It provides methods to
publish messages to a topic and to subscribe a handler to a topic.
Use Cases
The Channel
class is used to encapsulate the Publish-Subscribe pattern with a
particular topic. This can be used to create a more focused interface for a
subset of your application's events. It can be useful in:
- Event-driven architectures: Different components of a system can listen to
specific events without needing to understand the entire event system.
- Real-time updates: Channels can be used to push updates only to
subscribers who are interested in a specific topic.
- Multi-user applications: Each user can have their own channel, allowing
for targeted communication.
Interface Documentation
Constructor
constructor(pubsub: PubSub<string, T> = new PubSub(), topic: Topic = [])
Creates a new Channel
instance. The pubsub
parameter is a PubSub
instance
that the channel should interface with, and the topic
parameter is the topic
that the channel should handle.
publish
publish(context: T): void
Publishes data to the channel's topic. The context
parameter is the data to be
published.
subscribe
subscribe(subscriber: Handler<T>): () => void
Subscribes a handler to the channel's topic. The subscriber
parameter is a
function to be executed whenever data is published to the topic.
The subscribe
method returns a function that, when called, will unsubscribe
the handler from the topic.
channel
channel(topic: Topic): Channel<T>
Creates and returns a new Channel
that shares the PubSub
instance of the
current channel but has a different topic. The topic
parameter is the topic
for the new channel.
Examples
import Channel from "./channel";
const channel = new Channel<string>();
const handler = (context, topic) => {
console.log(`Received ${context} on topic ${topic.join("/")}`);
};
const unsubscribe = channel.subscribe(handler);
channel.publish("Hello, world!");
unsubscribe();
const newChannel = channel.channel(["topic1"]);
const newUnsubscribe = newChannel.subscribe(handler);
newChannel.publish("Hello, topic1!");
newUnsubscribe();
In this example, we first create a Channel
and subscribe a handler to it.
Then, we publish a message to the channel, and the handler logs the message and
the topic. After that, we unsubscribe from the channel. Finally, we create a new
channel with a different topic, subscribe the same handler to the new channel,
publish a message to the new channel, and unsubscribe from the new channel.
BloomFilter
The BloomFilter
class in this TypeScript file is an implementation of a Bloom
filter. A Bloom filter is a data structure that can be used to test whether an
element is a member of a set. It's a probabilistic data structure that provides
fast membership queries and has a compact representation at the cost of some
false positives.
Use Cases
Bloom filters are used in various applications, including:
- Web browsers: Used for safe browsing to check if a URL is in a list of
known malicious URLs.
- Databases: Used to prevent unnecessary disk reads for non-existent rows or
documents.
- Caching systems: Used to avoid expensive operations for items that aren't
in the cache.
- Network routers: Used for packet routing to keep track of data that has
been previously seen.
Interface Documentation
Constructor
constructor(size: number = 2 ** 16, entries?: readonly T[])
Creates a new BloomFilter
. The size
parameter determines the size of the
Bloom filter, and the entries
parameter is an optional array to initialize the
Bloom filter.
add
add(key: string): this
Adds an element to the Bloom filter. The key
parameter is the element to add.
has
has(key: string): boolean
Checks whether an element might be in the set. The key
parameter is the
element to check. Returns true
if the element might be in the set, and false
if the element is definitely not in the set.
hash
#hash(key: string): number[]
Generates three different hash values for the given key. The key
parameter is
the key to hash. The hash functions used are sdbm
, djb2a
, and fnv1a
.
Examples
import BloomFilter from "./bloom";
const bloomFilter = new BloomFilter<string>();
bloomFilter.add("apple").add("banana").add("cherry");
console.log(bloomFilter.has("apple"));
console.log(bloomFilter.has("banana"));
console.log(bloomFilter.has("cherry"));
console.log(bloomFilter.has("durian"));
In this example, we first create a BloomFilter
and add some elements to it.
Then, we check if these elements and an element not added to the filter might be
in the set. Note that while a Bloom filter returns true
if an element might be
in the set, it always returns false
if an element is definitely not in the
set.
QuadTree
The QuadTree
class in this TypeScript file is an implementation of a quadtree,
a tree data structure in which each internal node has exactly four children:
north-west, north-east, south-west and south-east. Quadtree can be used to
partition a two-dimensional space by recursively subdividing it into four
quadrants or regions.
Use Cases
Quadtrees are used in various applications, including:
- Geographical Information Systems (GIS): Quadtrees can be used to represent
spatial data like geographical coordinates, polygons, and points of interest.
- Image Processing: They can be used for image compression, image
representation, and fast image processing operations.
- Game Development: Quadtrees are commonly used in game development for
efficient collision detection, locating objects in a scene, and terrain
representation.
- Computer Graphics: Quad trees can be used to partition a space in a way
that makes it easy to work with 2D graphics and perform operations like
collision detection and viewport culling.
- Image Recognition: Quad trees can be used to process and analyze images,
particularly for hierarchical compression and fast segmentation of images.
- Spatial Indexing: Quad trees are used to partition space into precise
quadrants which can be used to speed up the searching process.
- Wireless Networking: In wireless networking, quad trees can help with the
efficient routing of data.
- Geospatial Data: Quad trees can be used to store and navigate maps in a
GIS, or for storing spatial data like rectangles, points, and polygons which
are used in visualization, collision detection, and area selection.
- Physics Simulations: In physics simulations, quad trees can be used to
handle two-dimensional collision detection by efficiently querying for pairs
of intersecting objects.
Interface Documentation
Functions
createBox
createBox(box: Box): (range: Box) => boolean
Returns a function that takes a range
and checks if it intersects with the
specified box
.
createCircle
createCircle(circle: Circle): (range: Box) => boolean
Returns a function that takes a range
and checks if it intersects with the
specified circle
.
Class: QuadTree
Constructor
constructor(bounds: Box, entries?: readonly [Point, T][])
Creates a new QuadTree
. The bounds
parameter specifies the boundary of the
quadtree, and the entries
parameter is an optional array of points and their
associated data to initialize the quadtree.
set
set(point: Point, value: T): boolean
Inserts an element into the quadtree at a specific point. The point
parameter
is the point at which to insert, and the value
parameter is the data to
insert. Returns true
if the insertion is successful, and false
otherwise.
has
has(point: Point): boolean
Checks whether an element might be in the quadtree. The point
parameter is the
point to check. Returns true
if the point might be in the quadtree, and
false
otherwise.
get
get(point: Point): T | undefined
Retrieves the data at a specific point in the quadtree. The point
parameter is
the point to retrieve. Returns the data if found, and undefined
otherwise.
delete
delete(point: Point): boolean
Deletes the data at a specific point in the quadtree. The point
parameter is
the point to delete. Returns true
if the deletion is successful, and false
otherwise.
clear
clear(): void
Removes all key-value pairs from the tree.
list
list(intersects: (range: Box) => boolean): IterableIterator<[Point, T]>
Returns an iterator that yields all points and their associated data in the
quadtree that intersect with a specific range. The intersects
parameter is a
function that takes a range and returns true
if it intersects with the desired
range, and false
otherwise.
keys, values, entries
keys(): IterableIterator<Point>
values(): IterableIterator<T>
entries(): IterableIterator<[Point, T]>
These methods return iterators that yield all points, all data, and all
point-data pairs in the quadtree, respectively.
forEach
forEach(callbackFn: (value: T, point: Point, map: this) => void, thisArg?: unknown): void
Executes a provided function once for each point-data pair in the quadtree. The
callbackFn
parameter is the function to execute, and the thisArg
parameter
is the value to use as this
when executing the function.
Examples
import QuadTree, { createBox } from "./qtree";
const quadTree = new QuadTree<string>({ x: 0, y: 0, width: 100, height: 100 });
quadTree.set({ x: 10, y: 10 }, "point1");
quadTree.set({ x: 20, y: 20 }, "point2");
console.log(quadTree.has({ x: 10, y: 10 }));
console.log(quadTree.has({ x: 30, y: 30 }));
console.log(quadTree.get({ x: 10, y: 10 }));
console.log(quadTree.get({ x: 30, y: 30 }));
console.log(quadTree.delete({ x: 10, y: 10 }));
console.log(quadTree.delete({ x: 30, y: 30 }));
const range = { x: 0, y: 0, width: 50, height: 50 };
const intersects = createBox(range);
for (const [point, data] of quadTree.list(intersects)) {
console.log(`Point: ${point.x}, ${point.y}, Data: ${data}`);
}
In this example, we first create a QuadTree
and set some data at specific
points. Then, we check if these points might be in the quadtree, get the data at
these points, and delete the data at one of these points. Finally, we list all
points and their associated data that intersect with a specific range.
License
MIT
Disclosures
The documentation provided above has been generated with the assistance of
ChatGPT. While efforts have been made to ensure accuracy and comprehensiveness,
it is essential to review and verify the content for specific use cases and
application requirements. The generated documentation serves as a starting point
and should be tailored to suit individual project needs and objectives. As with
any automated content, caution should be exercised in critical and
security-sensitive applications.