{"_id":"@abeedoo/fractional-nested-sets","name":"@abeedoo/fractional-nested-sets","dist-tags":{"latest":"0.1.0"},"versions":{"0.1.0":{"name":"@abeedoo/fractional-nested-sets","version":"0.1.0","type":"module","description":"Tree manipulation using fractional (IEEE 754 float) nested set values for O(1) moves","author":{"name":"Clifford Meece"},"license":"MIT","main":"dist/index.js","types":"dist/index.d.ts","exports":{".":{"import":"./dist/index.js","types":"./dist/index.d.ts"}},"scripts":{"build":"tsc","check":"tsc --noEmit","test":"vitest run","test:watch":"vitest","bench":"tsx benchmarks/run.ts","prepublishOnly":"npm run build"},"publishConfig":{"access":"public","registry":"https://registry.npmjs.org/"},"repository":{"type":"git","url":"git+https://github.com/abeedoolabs/fractional-nested-sets.git"},"keywords":["tree","nested-sets","mptt","hierarchy","fractional","data-structure"],"devDependencies":{"tsx":"^4.21.0","typescript":"^5.7.0","vitest":"^2.1.0"},"_id":"@abeedoo/fractional-nested-sets@0.1.0","gitHead":"17fed271bcd5cb062254640b66e0f263d9291f48","bugs":{"url":"https://github.com/abeedoolabs/fractional-nested-sets/issues"},"homepage":"https://github.com/abeedoolabs/fractional-nested-sets#readme","_nodeVersion":"22.18.0","_npmVersion":"10.9.3","dist":{"integrity":"sha512-nL5of3x+yUdgob7haV8eARaHxS/YFCk8RvHHikCJqnpoRyZZXzqJA1+0A5X3nifW0a8nWvdVH/fJrCppqzl1ZQ==","shasum":"4a7e15c64fe38619c35ffae2a476385958f7b285","tarball":"https://registry.npmjs.org/@abeedoo/fractional-nested-sets/-/fractional-nested-sets-0.1.0.tgz","fileCount":18,"unpackedSize":42761,"signatures":[{"keyid":"SHA256:DhQ8wR5APBvFHLF/+Tc+AYvPOdTpcIDqOhxsBHRwC7U","sig":"MEQCIGqwf9iuT6268ab39G/oXHc3A44qRfr6PBHoiWFwYo6pAiAN5aQKPghLxslDlrMNzpq46MHJLyjb4PHamdUxFzQjJQ=="}]},"_npmUser":{"name":"meecect","email":"clifford.meece@me.com"},"directories":{},"maintainers":[{"name":"meecect","email":"clifford.meece@me.com"}],"_npmOperationalInternal":{"host":"s3://npm-registry-packages-npm-production","tmp":"tmp/fractional-nested-sets_0.1.0_1778619303827_0.5723002782439486"},"_hasShrinkwrap":false}},"time":{"created":"2026-05-12T20:55:03.690Z","0.1.0":"2026-05-12T20:55:03.962Z","modified":"2026-05-12T20:55:04.244Z"},"maintainers":[{"name":"meecect","email":"clifford.meece@me.com"}],"description":"Tree manipulation using fractional (IEEE 754 float) nested set values for O(1) moves","homepage":"https://github.com/abeedoolabs/fractional-nested-sets#readme","keywords":["tree","nested-sets","mptt","hierarchy","fractional","data-structure"],"repository":{"type":"git","url":"git+https://github.com/abeedoolabs/fractional-nested-sets.git"},"author":{"name":"Clifford Meece"},"bugs":{"url":"https://github.com/abeedoolabs/fractional-nested-sets/issues"},"license":"MIT","readme":"# fractional-nested-sets\n\nA tree data structure library that uses IEEE 754 floating-point `lft`/`rgt` values instead of integers. This eliminates the O(n) node-shifting penalty of traditional MPTT (Modified Preorder Tree Traversal) when inserting or moving nodes, while preserving O(1) subtree and ancestor queries.\n\n**Zero dependencies. Works in-memory or with any database via a pluggable storage adapter.**\n\n## The Problem\n\nTraditional nested sets (MPTT) store integer `lft`/`rgt` boundaries. Every time you insert or move a node, every node to the right of the insertion point must be renumbered:\n\n```\nInsert \"Tablets\" under \"Electronics\" (1000-node tree)\n→ MPTT: UPDATE 500+ rows to shift lft/rgt values\n→ FNS:  INSERT 1 row with a fractional lft/rgt\n```\n\nFor read-heavy trees (menus, categories, org charts) that occasionally change, this write amplification is the bottleneck.\n\n## The Solution\n\nFractional Nested Sets place new `lft`/`rgt` values at the **midpoint** of adjacent boundaries using IEEE 754 floating-point arithmetic. No other nodes need to change.\n\nWhen gaps eventually shrink below a precision threshold (~1e-7), a one-time rebalance reassigns clean integer values. In practice this happens rarely — roughly every few hundred mutations — and the amortized cost remains far below MPTT's per-operation penalty.\n\n## Install\n\n```bash\nnpm install @abeedoo/fractional-nested-sets\n```\n\n## Quick Start\n\n```ts\nimport { FractionalNestedSet } from '@abeedoo/fractional-nested-sets';\n\nconst tree = new FractionalNestedSet();\n\ntree.addRoot('electronics');\ntree.addChild('electronics', 'phones');\ntree.addChild('electronics', 'laptops');\ntree.addChild('phones', 'iphones');\ntree.addChild('phones', 'android');\ntree.addChild('laptops', 'macbooks');\n\n// Subtree query — all descendants\ntree.getSubtree('phones');\n// → [phones, iphones, android]\n\n// Ancestor query — breadcrumb path from root\ntree.getAncestors('macbooks');\n// → [electronics, laptops, macbooks]\n\n// Move a node — only the moved subtree is modified\ntree.moveNode('macbooks', 'phones');\n\n// Remove a subtree — no renumbering\ntree.removeNode('android');\n```\n\n## API\n\n### `TreeOperations` Interface\n\nAll three included implementations share this interface:\n\n| Method | Description |\n|--------|-------------|\n| `addRoot(id)` | Insert a new root node |\n| `addChild(parentId, childId)` | Insert a child as the last child of a parent |\n| `moveNode(nodeId, newParentId)` | Move a subtree to a new parent |\n| `removeNode(nodeId)` | Remove a node and all its descendants |\n| `getSubtree(nodeId)` | All descendants (inclusive), O(1) filter on lft/rgt |\n| `getAncestors(nodeId)` | Path from root to node (inclusive) |\n| `getChildren(parentId)` | Direct children only |\n| `getAllNodes()` | Every node, sorted by `lft` |\n| `getNode(id)` | Single node lookup |\n\nEvery mutating method returns `{ nodesModified: number }` — the count of nodes whose `lft`/`rgt` values actually changed. This is the key metric that demonstrates FNS's advantage.\n\n### Implementations\n\n```ts\nimport { FractionalNestedSet } from '@abeedoo/fractional-nested-sets';\nimport { TraditionalMPTT } from '@abeedoo/fractional-nested-sets';\nimport { AdjacencyList } from '@abeedoo/fractional-nested-sets';\n```\n\n| Implementation | Writes | Reads | Use Case |\n|----------------|--------|-------|----------|\n| `FractionalNestedSet` | O(1) amortized | O(1) subtree/ancestor | **Production use** — best of both worlds |\n| `TraditionalMPTT` | O(n) per mutation | O(1) subtree/ancestor | Comparison baseline |\n| `AdjacencyList` | O(1) per mutation | O(n) subtree/ancestor | Comparison baseline |\n\n### Utility Functions\n\n```ts\nimport { buildNested, printTree, validate } from '@abeedoo/fractional-nested-sets';\n\n// Build a nested JSON structure (great for API responses)\nconst nested = buildNested(tree.getAllNodes());\n// → [{ id: 'electronics', children: [{ id: 'phones', children: [...] }] }]\n\n// Pretty-print for debugging\nconsole.log(printTree(tree.getAllNodes()));\n// electronics [1, 12]\n//   phones [2, 9]\n//     iphones [3, 4]\n//     android [5, 6]\n//   laptops [10, 11]\n\n// Validate nested-set invariants\nconst errors = validate(store);\n// → [] (empty array = valid tree)\n```\n\n### Precision Utilities\n\n```ts\nimport { bisect, hasAdequateGap, needsRebalance, PRECISION_THRESHOLD } from '@abeedoo/fractional-nested-sets';\n\nbisect(1, 2);           // → 1.5\nhasAdequateGap(1, 2);   // → true\nhasAdequateGap(1, 1 + 1e-8); // → false (below threshold)\n```\n\n## Custom Storage Adapter\n\nBy default, everything runs in-memory. To persist to a database, implement the `StorageAdapter` interface:\n\n```ts\nimport { FractionalNestedSet, type StorageAdapter, type TreeNode } from '@abeedoo/fractional-nested-sets';\n\nconst adapter: StorageAdapter = {\n  get(id: string): TreeNode | undefined { /* SELECT by id */ },\n  getAll(): TreeNode[] { /* SELECT * */ },\n  set(node: TreeNode): void { /* UPSERT */ },\n  delete(id: string): void { /* DELETE by id */ },\n  clear(): void { /* TRUNCATE */ },\n};\n\nconst tree = new FractionalNestedSet(adapter);\n```\n\nThe `TreeNode` shape your table needs:\n\n| Column | Type | Notes |\n|--------|------|-------|\n| `id` | `string` | Primary key |\n| `parentId` | `string \\| null` | Foreign key to self |\n| `lft` | `float8` / `double` | Left boundary — **use a float type, not integer** |\n| `rgt` | `float8` / `double` | Right boundary |\n| `depth` | `integer` | Nesting level (0 = root) |\n\nIndex `lft` and `rgt` for fast range queries:\n\n```sql\nCREATE INDEX idx_tree_lft ON categories (lft);\nCREATE INDEX idx_tree_rgt ON categories (rgt);\n```\n\n## How It Works\n\nTraditional MPTT assigns contiguous integers:\n\n```\nElectronics [1, 12]\n  Phones [2, 7]\n    iPhone [3, 4]\n    Android [5, 6]\n  Laptops [8, 11]\n    MacBook [9, 10]\n```\n\nInserting \"Tablets\" after \"Laptops\" requires shifting `lft`/`rgt` for every node with values >= 12 to make room for `[12, 13]`. In a 10,000-node tree, that's thousands of updates.\n\nFractional Nested Sets instead **bisect** the available gap:\n\n```\nElectronics [1, 12]\n  Phones [2, 7]\n    iPhone [3, 4]\n    Android [5, 6]\n  Laptops [8, 11]\n    MacBook [9, 10]\n  Tablets [11.5, 11.75]    ← placed in the gap, nothing else moves\n```\n\nThe nested-set query semantics are identical — `WHERE lft >= 11.5 AND rgt <= 11.75` still returns the correct subtree. But zero other rows were touched.\n\n### Auto-Rebalance\n\nAfter many bisections in the same region, gaps shrink toward zero. When any gap falls below `1e-7` (configurable), the library triggers a full rebalance that reassigns clean integer values in a single DFS pass. This is O(n) but happens rarely — the amortized cost per operation remains O(1).\n\n```ts\n// Custom threshold (default is 1e-7)\nconst tree = new FractionalNestedSet(undefined, 1e-5);\n```\n\n## Benchmarks\n\nRun locally:\n\n```bash\nnpm run bench\n```\n\nResults from a 200-node tree with 50 moves:\n\n| Operation | FNS `nodesModified` | MPTT `nodesModified` | Reduction |\n|-----------|--------------------:|---------------------:|----------:|\n| 200 inserts | 285 | 8,799 | **97%** |\n| 50 moves | 50 | 8,052 | **99%** |\n\nThe `nodesModified` count represents how many nodes had their `lft`/`rgt` values rewritten. This directly translates to database UPDATE statements in a real application.\n\n## Development\n\n```bash\nnpm test              # Run all tests\nnpm run test:watch    # Watch mode\nnpm run bench         # Run benchmarks\nnpm run build         # Compile TypeScript\nnpm run check         # Type-check without emitting\n```\n\n## License\n\nMIT\n","readmeFilename":"README.md","_rev":"1-0e57b8112f68fd19c1521fdba697d29e"}