A TypeScript Map implementation that maintains keys in sorted order using an underlying red-black tree
npm install red-black-mapA TypeScript Map implementation that maintains keys in sorted order using an underlying red-black tree. RedBlackMap closely follows the native JavaScript Map API, providing a familiar and efficient interface for use cases that require sorted iteration or range searches.
- Native-like API: Familiar methods like .set(), .get(), .has(), .delete(), and .forEach().
- Sorted Iteration: Iterate through keys, values, or entries in both ascending and descending order.
- Balanced Tree: Guaranteed $O(\log n)$ time complexity for insertions, deletions, and lookups.
- Iteration Modification Safety: Robust against additions and deletions during iteration. Iterators automatically re-sync when the tree structure changes, maintaining consistency similar to the native Map.
- Custom Comparators: Support for any key type via custom comparison functions.
- Pre-defined Comparators: Includes optimized comparators for Numbers, Strings, Dates, Booleans, and BigInts.
- Type Safe: Written in TypeScript with full type definitions.
``bash`
npm install red-black-map
`typescript
import { RedBlackMap, CompareNumbers } from 'red-black-map';
// Create a map with number keys and string values
const redBlackMap = new RedBlackMap
redBlackMap.set(3, 'three');
redBlackMap.set(1, 'one');
redBlackMap.set(2, 'two');
console.log(redBlackMap.size);// 3
console.log(redBlackMap.get(2));// 'two'
// Iteration is always sorted by key
for (const [key, value] of redBlackMap.entries()) {
console.log(key, value);
}
// Output:
// 1 'one'
// 2 'two'
// 3 'three'
`
instance.
- comparator: A function (a, b) => number that defines the sort order of the keys.
- entries: An optional iterable of [key, value] pairs to initialize the map.$3
A read-only property that returns the number of key-value pairs in the map.$3
Adds or updates an element with a specified key and value. Returns the map instance for chaining.$3
Returns the value associated with the specified key, or undefined if the key does not exist.$3
Returns true if an element with the specified key exists, otherwise false.$3
Removes the specified element from the map. Returns true if the element was found and removed, otherwise false.$3
Removes the first element (minimum key) from the map and returns it as a [key, value] pair. Returns undefined if the map is empty.$3
Removes the last element (maximum key) from the map and returns it as a [key, value] pair. Returns undefined if the map is empty.$3
Removes all elements from the map.$3
Returns a generator that yields keys in ascending or descending order.
- Options: { gte?, gt?, lte?, lt? }.
- If no options are provided, iterates over all keys.$3
Returns a generator that yields values in ascending or descending order.
- Options: { gte?, gt?, lte?, lt? }.
- If no options are provided, iterates over all values.$3
Returns a generator that yields [key, value] pairs in ascending or descending order.
- Options: { gte?, gt?, lte?, lt? }.
- If no options are provided, iterates over all entries.$3
Executes a provided function once for each key-value pair in the map, in ascending or descending order.
- callback: Function to execute for each element: (value, key, redBlackMap) => void.
- thisArg: Value to use as this when executing callback.Using Common Comparators
The library exports several optimized comparator functions for common types:
`typescript
import { RedBlackMap, CompareStrings, CompareDates } from 'red-black-map';const redBlackMap1 = new RedBlackMap(CompareStrings);
const redBlackMap2 = new RedBlackMap(CompareDates);
`| Comparator | Description | Example Sorted Data |
| :--- | :--- | :--- |
|
CompareNumbers | Performance-optimized numeric comparison | [-Infinity, -1, 0, 1, Infinity] |
| CompareStrings | Deterministic Unicode code point comparison | ['apple', 'banana'] |
| CompareStringsLocale | Language-sensitive (linguistic) comparison | ['apple', 'banana'] |
| CompareDates | Comparison for Date objects | [2023-01-01, 2023-01-02] |
| CompareBooleans | false before true | [false, true] |
| CompareBigInts | Standard bigint comparison | [1n, 2n, 5n] |Custom Comparators
You can provide your own comparator function for complex objects:
`typescript
type User = { id: number; name: string; };const redBlackMap = new RedBlackMap((a, b) => a.id - b.id);
`Finding Nearest Neighbors (Lower / Higher / Floor / Ceil)
You can efficiently find nearest neighbors using
entries or entriesReversed with an options object:`typescript
// Lower (strictly < 15):
const lowerEntry = redBlackMap.entriesReversed({ lt: 15 }).next().value;// Floor (<= 15):
const floorEntry = redBlackMap.entriesReversed({ lte: 15 }).next().value;
// Higher (strictly > 15):
const higherEntry = redBlackMap.entries({ gt: 15 }).next().value;
// Ceil (>= 15):
const ceilEntry = redBlackMap.entries({ gte: 15 }).next().value;
// First: smallest key in the map
const firstEntry = redBlackMap.entries().next().value;
// Last: largest key in the map
const lastEntry = redBlackMap.entriesReversed().next().value;
`Complexity
| Operation |
RedBlackMap (Tree) | Native Map (Hash) |
| :--- | :--- | :--- |
| Insert (set) | $O(\log n)$ | $O(1)$ |
| Delete (delete) | $O(\log n)$ | $O(1)$ |
| Search (get / has) | $O(\log n)$ | $O(1)$ |
| Find Min/Max | $O(\log n)$ | $O(n)$ |
| Nearest Neighbor | $O(\log n)$ | $O(n)$ |
| Sorted Iteration | $O(n)$ | $O(n \log n)$ |Unexpected Differences from Native Map
While
RedBlackMap aims to follow the native Map API where possible, there are several key differences:$3
- Native Map: new Map(iterable?)
- RedBlackMap: new RedBlackMap(comparator, iterable?)$3
Native Map uses the SameValueZero algorithm for key equality. RedBlackMap relies entirely on your provided comparator.- Objects: Native
Map uses reference equality. RedBlackMap can use value equality if your comparator is designed for it.
- Zeros: The provided numeric comparators (CompareNumbers, etc.) treat 0 and -0 as the same key, consistent with native Map.
- NaN: Native Map treats NaN as equal to itself. By default, RedBlackMap (using CompareNumbers) treats NaN as an incomparable key and will throw a TypeError. Use a custom comparator if you need NaN support.$3
Mutating an object that is used as a key in a RedBlackMap can corrupt the internal tree structure if the mutation changes the result of the comparison.$3
- RedBlackMap does not extend the native Map class. Therefore, redBlackMap instanceof Map will return false.$3
- Object.prototype.toString.call(redBlackMap) returns [object Object] instead of [object Map].$3
Native Map methods like .keys(), .values(), and .entries() return a native MapIterator. RedBlackMap implements these using generators, so they return a Generator object.What this means for you:
- Compatibility: For 99% of use cases, there is no difference. You can use
for...of loops, Array.from(), and spread syntax [...] exactly as you would with a native Map.
- Advanced API: The Generator type includes additional methods like .throw() and .return(). These are niche features for manual iteration control that native MapIterator` does not typically support.