data-structure-typed

What is data-structure-typed?

data-structure-typed is a library providing a comprehensive set of specialized data structures for JavaScript and TypeScript. It aims to fill the gap in the JS/TS standard library by offering high-performance, standardized implementations of structures that are typically missing or inefficiently simulated using built-in Array or Map objects.

Key Problem Solved: Efficient Alternatives to Array/Map

In standard JS/TS, developers often use Array to simulate other structures, which can lead to performance bottlenecks:

• Queue/Deque: Using Array.shift() results in $O(n)$ time complexity. This library provides Queue and Deque with $O(1)$ enqueue and dequeue operations.
• HashMap: The built-in Map is a LinkedHashMap (preserving insertion order), which can be slower than a pure HashMap. This library provides a dedicated HashMap for algorithm acceleration.

Supported Data Structures

The library includes several advanced structures:

• Heap / Priority Queue: Supports $O(\log n)$ insertion, deletion, and search, with $O(1)$ access to the extremum (min/max).
• Red Black Tree: A balanced binary search tree providing optimal performance for CRUD operations.
• Linked List: Useful for efficient insertions or deletions at a known index within an ordered set.
• Trie: Optimized for high-speed string searching and efficient string storage.
• Graph: For modeling complex relationships between nodes.
• Stack: While Array can be used, this library provides a formal implementation.

When choosing a data structure from data-structure-typed, consider the Big O complexity and the specific performance gains over native JavaScript types.

Key Performance Gains

• Deque vs Array: Using a Deque is up to 484x faster than Array.shift() when handling 100K elements due to $O(1)$ head/tail operations compared to Array's $O(n)$.
• RedBlackTree vs Array: In workloads requiring repeated "update + resort", RedBlackTree can be 40x–308x faster than using a native Array.

Complexity Reference

Note: LinkedList insert/delete is $O(1)$ if the pointer to the node is already known.

When choosing a data structure in data-structure-typed, consider the following performance characteristics compared to native JavaScript implementations:

• Deque vs Array: A Deque is up to 484x faster than Array.shift() when handling 100K elements.
• RedBlackTree vs Array: For workloads involving repeated "update + resort" operations, RedBlackTree is 40x–308x faster than using an Array.
• Complexity Guarantees:
  • All balanced tree operations provide O(log n) complexity.
  • Deque head and tail operations provide O(1) complexity.

Note on Cross-Language Comparisons: Benchmarks comparing JavaScript structures to C++ (like js-sdsl) should be treated as directional. Differences are often due to the JavaScript runtime (GC, boxed numbers, dynamic dispatch) rather than the library implementation itself. For practical decision-making, prioritize within-JS comparisons.

Overview

data-structure-typed is a high-performance data structures library for JavaScript and TypeScript designed to fill gaps in the native language standard library.

When to use it

You should use this library instead of native JavaScript structures when:

1. Performance is critical: When using Array.shift() for queue operations, which is O(n), you should switch to the library's Queue or Deque to achieve O(1) complexity.
2. Ordering is not required: If you need a high-performance HashMap and do not require the insertion-order preservation (and associated overhead) of the native JavaScript Map.
3. Missing structures are needed: When your algorithm requires structures not natively available in JS/TS, such as:
   • Heap / Priority Queue: For $O(\log n)$ insertion/deletion and $O(1)$ access to min/max values.
   • Red-Black Tree: For balanced binary search tree performance in lookups, insertions, and deletions.
   • Graph and AVL Tree: For complex relational or balanced tree operations.

Key Advantages

• Superior Performance: Implementations are optimized to surpass native JS structures in specific use cases and aim for parity with C++ or Java standard libraries.
• Standardized API: All structures follow a uniform interface including standard methods like forEach, filter, map, reduce, find, and clear.

When using MapMode, the internal node is the single source of truth for values. This introduces a specific semantic behavior regarding undefined:

1. Presence vs. Value: MapMode distinguishes between a missing key and a key that exists with an undefined value. has(key) will return true even if the value is undefined because the index tracks the node, not the value.
2. set(key, undefined): Calling set with undefined will overwrite the existing value on that node. The key remains in the _store index, and get(key) will return undefined.
3. TreeSet Compatibility: This design ensures that TreeSet (where values are always undefined) functions correctly, as the index tracks the existence of the key regardless of the value.

Warning: To maintain MapMode correctness, keys must be treated as logically immutable. Mutating a node.key externally will break the _store index mapping.

A TreeMultiSet is an ordered multiset (bag) where each element x has a non-negative integer count c(x). It is backed by a RedBlackTree.

Key Concepts:

• Size vs Distinct Size: size returns the total number of occurrences ($\sum$ counts), while distinctSize returns the number of unique keys.
• Iteration: Default iteration is expanded, meaning it yields each element c(x) times.
• Navigable Methods: Methods like ceiling, floor, higher, and lower return the element K (or undefined).
• Polling: pollFirst() and pollLast() perform a deleteAll on the respective extreme element and return it.

const scores = new TreeMultiSet([100, 95, 100, 87, 95, 100]);
// { 87: 1, 95: 2, 100: 3 }

scores.size;          // 6 (total)
scores.distinctSize;  // 3 (unique)
scores.count(100);    // 3
scores.first();       // 87
scores.last();        // 100
scores.ceiling(90);   // 95

// Functional operations
const highScores = scores.filter((k, c) => k >= 95);
// { 95: 2, 100: 3 }

const doubled = scores.map((k, c) => [k * 2, c]);
// { 174: 1, 190: 2, 200: 3 }