red-black-map

A 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.

Features

- 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.

Installation

``bash
npm install red-black-map
`

Quick Start

`typescript
import { RedBlackMap, CompareNumbers } from 'red-black-map';

// Create a map with number keys and string values
const redBlackMap = new RedBlackMap(CompareNumbers);

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'
`

API Reference

$3


Creates a new RedBlackMap 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.

License

MIT