Splay Tree Data Structures for TypeScript

Common errors

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

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

  cause 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')

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

Warnings

• gotcha Using 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.
• gotcha Attempting 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.
• gotcha The `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)`.
• gotcha Modifying 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.

Install

• npm install splaytree-ts npm
• yarn add splaytree-ts yarn
• pnpm add splaytree-ts pnpm

Imports

• SplayTreeSet
  wrong:

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

  correct:

  import { SplayTreeSet } from 'splaytree-ts';

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

  import SplayTreeMap from 'splaytree-ts';

  correct:

  import { SplayTreeMap } from 'splaytree-ts';

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

Quickstart

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