Registry / data / splaytree-ts

splaytree-ts

library1.0.2jsnpmunverified

splaytree-ts is a TypeScript library that provides efficient implementations of Splay Tree data structures, specifically `SplayTreeMap` and `SplayTreeSet`. Splay trees are self-balancing binary search trees with the distinct characteristic that recently accessed elements are more quickly accessible again, offering O(log(n)) amortized time complexity for fundamental operations like insertion, lookup, and removal. The current stable version is 1.0.2. Its key differentiation lies in the splaying heuristic, which optimizes for temporal locality of reference, making it particularly performant for workloads with skewed access patterns. The library supports custom comparison functions and key validation predicates for flexible use with various data types, enhancing its utility beyond simple primitive comparisons.

data

npm install splaytree-ts

github ↗package ↗

INSTALL

IMPORT

SIG · SPLAYTREE-TS

splaytree-ts

datajavascriptv1.0.2

Install

—

Import

—

Disk

—

Pass rate

0/ 6

Env Coverage0 / 6

glibc

18–22

musl

18–22

Install & Compatibility

Where this runs

tested against v? · npm install

Install × environment matrix

Each cell = how many times install + import succeeded across repeated harness runs. Partial = flaky.
glibc = Debian/Ubuntu slim · musl = Alpine Linux

musl

node 18–226 runs

build_error

glibc

node 18–226 runs

build_error

Code

Verified usage

Verified import paths — ran on the pinned version, not inferred.

SplayTreeSet

✓ import { SplayTreeSet } from 'splaytree-ts';

✗ const SplayTreeSet = require('splaytree-ts').SplayTreeSet;

The library is written in TypeScript and primarily consumed via ES Modules with named exports.

SplayTreeMap

✓ import { SplayTreeMap } from 'splaytree-ts';

✗ import SplayTreeMap from 'splaytree-ts';

Use named import for SplayTreeMap. Direct CommonJS require() may not provide optimal type inference or tree-shaking.

Demonstrates basic usage of SplayTreeSet for number operations and SplayTreeMap with a custom comparison function for object keys.

import { SplayTreeSet, SplayTreeMap } from 'splaytree-ts'; // Example 1: Using SplayTreeSet for numbers const ages = new SplayTreeSet<number>(); for (const age of [33, 45, 25, 35, 59, 18, 62]) { ages.add(age); } console.log('Ages in set:', Array.from(ages.values())); // [18, 25, 33, 35, 45, 59, 62] console.log('First age after 35:', ages.firstAfter(35)); // Expected: 45 console.log('Last age before 33:', ages.lastBefore(33)); // Expected: 25 ages.delete(59); // true console.log('Has 59 after deletion:', ages.has(59)); // false // Example 2: Using SplayTreeMap with custom comparison for objects interface User { id: number; name: string; } const users = new SplayTreeMap<number, User>( (a, b) => a - b // Compare by user ID ); users.set(101, { id: 101, name: 'Alice' }); users.set(50, { id: 50, name: 'Bob' }); users.set(200, { id: 200, name: 'Charlie' }); console.log('User with ID 50:', users.get(50)); // { id: 50, name: 'Bob' }

Debug

Known issues

gotchaUsing a custom `compare` function that is inconsistent (e.g., doesn't define a total order or violates transitivity) will lead to an improperly balanced or ordered tree, resulting in incorrect lookup and iteration behavior.

fix

Ensure your custom `compare(a, b)` function returns a negative number if `a < b`, a positive number if `a > b`, and zero if `a == b`, and maintains consistency across all comparisons.

affects: >=1.0.0

gotchaAttempting to use `SplayTreeMap` or `SplayTreeSet` with complex object keys without providing a custom `compare` function in the constructor will result in incorrect behavior, as the default comparison assumes natural ordering which is typically only valid for primitives (numbers, strings).

fix

Provide a `compare` function to the constructor, e.g., `new SplayTreeMap((a, b) => a.id - b.id)` if `id` is the key. For deep comparison, a more complex function might be required.

affects: >=1.0.0

gotchaThe `isValidKey` predicate function is essential when keys might include `null`, `undefined`, or types not directly handled by your `compare` function. Omitting it can lead to `TypeError`s during operations like `get`, `has`, or `delete` if an invalid key type is passed.

fix

Supply a `isValidKey` function to the constructor that explicitly checks for valid key types: `new SplayTreeMap(compareFn, (val) => typeof val === 'object' && val !== null)`.

affects: >=1.0.0

gotchaModifying a `SplayTreeMap` or `SplayTreeSet` (adding or removing elements) while iterating over it using `forEach` can lead to unpredictable behavior or infinite loops, as the internal structure of the tree changes during iteration.

fix

Avoid modifying the tree directly within a `forEach` callback. If modifications are necessary, collect items to be modified and perform changes after the iteration completes, or use an alternative iteration strategy.

affects: >=1.0.0

Errors

Common errors & fixes

TypeError: Cannot read properties of undefined (reading 'compare')

An operation was attempted with a key type that the default or supplied `compare` function could not handle, often when passing a complex object without a custom `compare` function.

fix

Provide a custom `compare` function to the `SplayTreeMap` or `SplayTreeSet` constructor that knows how to compare your specific key objects.

Elements are not in expected order or some elements are missing after insertion/deletion.

The custom `compare` function provided to the Splay Tree constructor is inconsistent, meaning it doesn't correctly define a total order for the keys or violates comparison rules (e.g., `a < b` and `b < a` for distinct `a, b`).

fix

Review and correct your custom `compare` function to ensure it always returns a consistent negative, positive, or zero value based on the relative order of `a` and `b`.

TypeError: Cannot read properties of null (reading 'has')

A method like `has`, `get`, or `delete` was called with `null`, `undefined`, or a key type not supported by the `compare` function, and no `isValidKey` predicate was provided or it failed to catch the invalid type.

fix

Implement and supply an `isValidKey` predicate function to the `SplayTreeMap`/`SplayTreeSet` constructor to explicitly validate input key types before comparison, preventing operations with unsupported values.

Upgrade

Version history

1.0.2latest on npm

Audit

Dependencies

No dependency data recorded yet.

Agent activity

13 hits · last 30 days

node

OpenAI (training)

Resources

githubhttps://github.com/SBanksX/splaytree-ts ↗

packagehttps://www.npmjs.com/package/splaytree-ts ↗