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

npm install red-black-map

Quick Start

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

// Create a map with number keys and string values
const redBlackMap = new RedBlackMap<number, string>(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

new RedBlackMap(comparator, entries?)

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.

.size

A read-only property that returns the number of key-value pairs in the map.

.set(key, value)

Adds or updates an element with a specified key and value. Returns the map instance for chaining.

.get(key)

Returns the value associated with the specified key, or undefined if the key does not exist.

.has(key)

Returns true if an element with the specified key exists, otherwise false.

.delete(key)

Removes the specified element from the map. Returns true if the element was found and removed, otherwise false.

.shift()

Removes the first element (minimum key) from the map and returns it as a [key, value] pair. Returns undefined if the map is empty.

.pop()

Removes the last element (maximum key) from the map and returns it as a [key, value] pair. Returns undefined if the map is empty.

.clear()

Removes all elements from the map.

.keys(options?) / .keysReversed(options?)

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.

.values(options?) / .valuesReversed(options?)

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.

.entries(options?) / .entriesReversed(options?)

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.

.forEach(callback, thisArg?) / .forEachReversed(callback, thisArg?)

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:

import { RedBlackMap, CompareStrings, CompareDates } from 'red-black-map';

const redBlackMap1 = new RedBlackMap<string, number>(CompareStrings);
const redBlackMap2 = new RedBlackMap<Date, any>(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:

type User = { id: number; name: string; };

const redBlackMap = new RedBlackMap<User, string>((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:

// 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:

1. Constructor Signature

• Native Map: new Map(iterable?)
• RedBlackMap: new RedBlackMap(comparator, iterable?)

2. Key Equality (SameValueZero vs. Comparator)

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

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.

4. Class Identity (instanceof)

• RedBlackMap does not extend the native Map class. Therefore, redBlackMap instanceof Map will return false.

5. String Tag (toString)

• Object.prototype.toString.call(redBlackMap) returns [object Object] instead of [object Map].

6. Iterator Return Type

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