{"id":16906,"library":"splaytree-ts","title":"Splay Tree Data Structures for TypeScript","description":"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.","status":"active","version":"1.0.2","language":"javascript","source_language":"en","source_url":"https://github.com/SBanksX/splaytree-ts","tags":["javascript","splay","tree","map","set","self-balancing","binary","search","typescript"],"install":[{"cmd":"npm install splaytree-ts","lang":"bash","label":"npm"},{"cmd":"yarn add splaytree-ts","lang":"bash","label":"yarn"},{"cmd":"pnpm add splaytree-ts","lang":"bash","label":"pnpm"}],"dependencies":[],"imports":[{"note":"The library is written in TypeScript and primarily consumed via ES Modules with named exports.","wrong":"const SplayTreeSet = require('splaytree-ts').SplayTreeSet;","symbol":"SplayTreeSet","correct":"import { SplayTreeSet } from 'splaytree-ts';"},{"note":"Use named import for SplayTreeMap. Direct CommonJS require() may not provide optimal type inference or tree-shaking.","wrong":"import SplayTreeMap from 'splaytree-ts';","symbol":"SplayTreeMap","correct":"import { SplayTreeMap } from 'splaytree-ts';"}],"quickstart":{"code":"import { SplayTreeSet, SplayTreeMap } from 'splaytree-ts';\n\n// Example 1: Using SplayTreeSet for numbers\nconst ages = new SplayTreeSet<number>();\nfor (const age of [33, 45, 25, 35, 59, 18, 62]) {\n  ages.add(age);\n}\n\nconsole.log('Ages in set:', Array.from(ages.values())); // [18, 25, 33, 35, 45, 59, 62]\nconsole.log('First age after 35:', ages.firstAfter(35));  // Expected: 45\nconsole.log('Last age before 33:', ages.lastBefore(33));   // Expected: 25\n\nages.delete(59);      // true\nconsole.log('Has 59 after deletion:', ages.has(59)); // false\n\n// Example 2: Using SplayTreeMap with custom comparison for objects\ninterface User { id: number; name: string; }\nconst users = new SplayTreeMap<number, User>(\n  (a, b) => a - b // Compare by user ID\n);\n\nusers.set(101, { id: 101, name: 'Alice' });\nusers.set(50, { id: 50, name: 'Bob' });\nusers.set(200, { id: 200, name: 'Charlie' });\n\nconsole.log('User with ID 50:', users.get(50)); // { id: 50, name: 'Bob' }","lang":"typescript","description":"Demonstrates basic usage of SplayTreeSet for number operations and SplayTreeMap with a custom comparison function for object keys."},"warnings":[{"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.","message":"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.","severity":"gotcha","affected_versions":">=1.0.0"},{"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.","message":"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).","severity":"gotcha","affected_versions":">=1.0.0"},{"fix":"Supply a `isValidKey` function to the constructor that explicitly checks for valid key types: `new SplayTreeMap(compareFn, (val) => typeof val === 'object' && val !== null)`.","message":"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.","severity":"gotcha","affected_versions":">=1.0.0"},{"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.","message":"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.","severity":"gotcha","affected_versions":">=1.0.0"}],"env_vars":null,"last_verified":"2026-04-22T00:00:00.000Z","next_check":"2026-07-21T00:00:00.000Z","problems":[{"fix":"Provide a custom `compare` function to the `SplayTreeMap` or `SplayTreeSet` constructor that knows how to compare your specific key objects.","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.","error":"TypeError: Cannot read properties of undefined (reading 'compare')"},{"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`.","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`).","error":"Elements are not in expected order or some elements are missing after insertion/deletion."},{"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.","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.","error":"TypeError: Cannot read properties of null (reading 'has')"}],"ecosystem":"npm","meta_description":null}