{"_id":"short-tree","_rev":"3-167133dd2fc8b9b3085dff270d7e4c9b","name":"short-tree","dist-tags":{"latest":"3.0.0"},"versions":{"1.0.0":{"name":"short-tree","version":"1.0.0","description":"Keep a tree trimmed from longer-than-necessary branches","author":{"name":"Gustaf Räntilä"},"license":"MIT","bugs":{"url":"https://github.com/grantila/short-tree/issues"},"homepage":"https://github.com/grantila/short-tree#readme","main":"./dist/index.js","types":"./dist/index.d.ts","directories":{},"engines":{"node":">=12"},"scripts":{"build":"rimraf dist && tsc -p tsconfig.prod.json","test":"jest --coverage","cz":"git-cz"},"repository":{"type":"git","url":"git+https://github.com/grantila/short-tree.git"},"keywords":["graph","tree","trim"],"devDependencies":{"@types/jest":"^26.0.20","@types/node":"^14.14.31","cz-conventional-changelog":"^3.1.0","jest":"^26.6.3","rimraf":"^3.0.1","ts-jest":"^26.5.2","typescript":"^4.2.2"},"config":{"commitizen":{"path":"./node_modules/cz-conventional-changelog"}},"dependencies":{"@types/bintrees":"^1.0.3","bintrees":"^1.0.2"},"gitHead":"36388bf8797b6db5b632d699e45fc2c706c8ea6e","_id":"short-tree@1.0.0","_nodeVersion":"14.16.0","_npmVersion":"6.14.11","dist":{"integrity":"sha512-SPhGxbdypMMjYlmdVL/dzBUCT/5FboztmleoS4WPgvCI7DqZXv8xrLSTuJqzmmuAtCTkgxkIKzfZ+jfJR6ODZg==","shasum":"bbf31c2f798ecbf48ecf6656b1bd62d202b43759","tarball":"https://registry.npmjs.org/short-tree/-/short-tree-1.0.0.tgz","fileCount":5,"unpackedSize":7604,"npm-signature":"-----BEGIN PGP SIGNATURE-----\r\nVersion: OpenPGP.js v3.0.13\r\nComment: https://openpgpjs.org\r\n\r\nwsFcBAEBCAAQBQJgZf+vCRA9TVsSAnZWagAAT74P/08F2gA7XhgyeVplJfil\nwFreDbf18GXGFlu2ovG9M5XN1WkpubC4tXfVqdxUHricrhBe7oaXnDes2Qzh\naW2VmXF9wgxkCMF4WG0T7la6bS/tlJutS5soVjHDYe7KYaZwGPCy+Zz8ZBL9\n0KP2/b8zYj0+7sbPXGWUCXFwPil8vsE/6r0fYpiFNYN/x36fuOHFIjpu29Su\nRuoTLqcUOqt9b1WfDNYY/K6bRC4U4EwDLhpfBorNTYEMNBc4CZz8668215IT\n/TL0MG0BRKuMU3Adv0wNHK1HgAIyiwV8EP+yUykY1TfN+uJG1n9XGQJpa6il\nOmXbl3nPkJB4WgYLdCGB772EemdvTlO7nSzJl3QVhtqjKgXo0QqFK6J5IbbW\nUok3Zbf689rDEO4iMhVgJkqt9UR7b6yfNG+v7T4wSmIvnLNUIjvCzSWiiQ6x\nyOGu4VNeSWE5QR3YMfaQgMAU1be1HSceo41T2UAUf30Ivh45bY/XVwMV9QTX\nrlFeqdpUVZX+23u6+guqEEGoaShb1pg3TVKF1gzDnh91npDQIGcisajlw2Oi\nylOr/Y5DQrCxDATp6qKckUVGJ8u5IcvzTpdAph4mSBUKNGkfLFnvnplhblAi\n+bvZtZtKzqVNRyqvejI9s+Q8s6IP1mX8yuTuUv5RrolgastQD21+HD5qCH0N\nQQdm\r\n=UFB6\r\n-----END PGP SIGNATURE-----\r\n","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEQCIGYaaI7YsH2wwCrEyICd42/UQTUszh/wamNYokq3+tw7AiBiyzquUTykgieYi6Yq4YdUK3mZhfZCcgmIfHC67SJHUA=="}]},"_npmUser":{"name":"grantila","email":"g.rantila@gmail.com"},"maintainers":[{"name":"grantila","email":"g.rantila@gmail.com"}],"_npmOperationalInternal":{"host":"s3://npm-registry-packages","tmp":"tmp/short-tree_1.0.0_1617297327093_0.7753082416875885"},"_hasShrinkwrap":false},"2.0.0":{"name":"short-tree","version":"2.0.0","description":"Keep a tree trimmed from longer-than-necessary branches","author":{"name":"Gustaf Räntilä"},"license":"MIT","bugs":{"url":"https://github.com/grantila/short-tree/issues"},"homepage":"https://github.com/grantila/short-tree#readme","exports":"./dist/index.js","main":"./dist/index.js","types":"./dist/index.d.ts","type":"module","sideEffects":false,"engines":{"node":"^12.20.0 || ^14.13.1 || >=16.0.0"},"scripts":{"build":"rimraf dist && tsc -p tsconfig.prod.json","test":"NODE_OPTIONS=--experimental-vm-modules jest --coverage","cz":"git-cz"},"repository":{"type":"git","url":"git+https://github.com/grantila/short-tree.git"},"keywords":["graph","tree","trim"],"devDependencies":{"@babel/preset-env":"^7.15.6","@babel/preset-typescript":"^7.15.0","@types/jest":"^27.0.1","@types/node":"^16.9.1","cz-conventional-changelog":"^3.1.0","jest":"^27.1.1","rimraf":"^3.0.1","typescript":"^4.4.3"},"config":{"commitizen":{"path":"./node_modules/cz-conventional-changelog"}},"dependencies":{"@types/bintrees":"^1.0.3","bintrees":"^1.0.2"},"jest":{"testEnvironment":"node","coverageReporters":["lcov","text","html"]},"gitHead":"16e81adb7c490eaa791cec87d5c2c62b61718f7b","_id":"short-tree@2.0.0","_nodeVersion":"14.17.6","_npmVersion":"6.14.15","dist":{"integrity":"sha512-iMtPBvS0uL9wShaRZgx59Yf59D7MezDQZnkwUofKPg1/zapO5v/qhTAa6t/oI+f/GACkWFJWZwfSjh7dMPdYww==","shasum":"f95821cd5c5a5e13991904ff3046bc57be355779","tarball":"https://registry.npmjs.org/short-tree/-/short-tree-2.0.0.tgz","fileCount":5,"unpackedSize":8494,"npm-signature":"-----BEGIN PGP SIGNATURE-----\r\nVersion: OpenPGP.js v3.0.13\r\nComment: https://openpgpjs.org\r\n\r\nwsFcBAEBCAAQBQJhPvZBCRA9TVsSAnZWagAARMAP/2d9C8d5heEnAEG47IhI\npff1zNNBq7Ha/QNp9o6Zba2QJQXw+jTFBEzzVjJ7qUusW99u05e6V82DeS/C\nkNeTKReXVgYMhbK89Y27Y5KBlWN7jMpcfA3uFhT+TuiHIjVfmNqP6kY9lI2g\n0VJE9WzFanaqadip13ReQtjm7F3J6YkxFJGE8tyfyESd+l1rzKKDTUsyA/6X\nCarTKRdFj1TvMYqOLTq6tMCm67GHIWwkfEcb/fj4Zu2HUJjy0o8fy0DA4nY5\nNi4HoCzSThCDM3itZw9dCxberUgmHuDUgE4opSjgAz5VTcGeRi/epCNezGKE\nsGI0R7UhqpRylCY1m9PhjcPdu9vL0JvLzBgWaYOcv7oB16NXxG6hZnos7R07\n8Gq43yAus/jUS+U4FfmekDcCULgoXzxz+tNXveqfmdqCIiS9L7QD6BJ3YNDF\nD7WScUrJ0H0KLf4w0okDOT80lVhV12ys39x3RskE57+9i/B96/D0NKvdNkFe\nWB9nLmVz3f2Xncdq5j1voVAwkwAiQxfL+RH3T45sh/2nuUI3vaAWNekaJL0y\n1QdyI+gbgm0y2CsjG5gbpPtFwqg3jR2bNkKiXX/CCvtFuDE8BaOtXLYnh34N\npBG39C59DR6ojHVB3JYK3QKepmHKZc9LWOHEpFgAnxcn8tNvb+ISigMxjhpw\nDHBT\r\n=qE5y\r\n-----END PGP SIGNATURE-----\r\n","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEUCIHtezvDkAUPTIhUDz7h7/WdctivSZLqnZ8PY6v8tdFgfAiEApgki2zyx/Mco4uENJKz++oalFzQBBPKFkZNvwvcJ2m8="}]},"_npmUser":{"name":"grantila","email":"g.rantila@gmail.com"},"directories":{},"maintainers":[{"name":"grantila","email":"g.rantila@gmail.com"}],"_npmOperationalInternal":{"host":"s3://npm-registry-packages","tmp":"tmp/short-tree_2.0.0_1631516225357_0.841125974685611"},"_hasShrinkwrap":false},"3.0.0":{"name":"short-tree","version":"3.0.0","description":"Keep a tree trimmed from longer-than-necessary branches","author":{"name":"Gustaf Räntilä"},"license":"MIT","bugs":{"url":"https://github.com/grantila/short-tree/issues"},"homepage":"https://github.com/grantila/short-tree#readme","exports":"./dist/index.js","main":"./dist/index.js","types":"./dist/index.d.ts","type":"module","sideEffects":false,"engines":{"node":"^14.13.1 || >=16.0.0"},"scripts":{"build":"rimraf dist && tsc -p tsconfig.prod.json","test":"NODE_OPTIONS=--experimental-vm-modules jest --coverage","cz":"git-cz"},"repository":{"type":"git","url":"git+https://github.com/grantila/short-tree.git"},"keywords":["graph","tree","trim"],"devDependencies":{"@babel/preset-env":"^7.20.2","@babel/preset-typescript":"^7.18.6","@types/jest":"^29.4.0","@types/node":"^18.11.18","cz-conventional-changelog":"^3.3.0","jest":"^29.4.1","rimraf":"^4.1.2","typescript":"^4.9.5"},"config":{"commitizen":{"path":"./node_modules/cz-conventional-changelog"}},"dependencies":{"@types/bintrees":"^1.0.3","bintrees":"^1.0.2"},"jest":{"testEnvironment":"node","coverageReporters":["lcov","text","html"]},"packageManager":"yarn@3.2.4","gitHead":"7489f9eaa0767f5c76609e74711afddc0a105549","_id":"short-tree@3.0.0","_nodeVersion":"18.13.0","_npmVersion":"8.19.3","dist":{"integrity":"sha512-Yd9NFs/o9QSoH4/wTjxk4Xe0+CIzitDRN1Qg7iBeTSejKjlCg/3PbgiRwDUVuaIxD0RRdv7Iz9jKr7e0HljtUg==","shasum":"f4db4cf9f2d87e9edc5083046c8c0fb59cc4ed1d","tarball":"https://registry.npmjs.org/short-tree/-/short-tree-3.0.0.tgz","fileCount":5,"unpackedSize":8332,"signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEUCIBI8dFW1b0Xr5DRk+D3UneoqQWFyFJzMarq7uoRcx9aXAiEAhFdn5rvIMkfoeEQB3ap/MlG4aMkw93jNffpw+C5NggA="}],"npm-signature":"-----BEGIN PGP SIGNATURE-----\r\nVersion: OpenPGP.js v4.10.10\r\nComment: https://openpgpjs.org\r\n\r\nwsFzBAEBCAAGBQJj3CVsACEJED1NWxICdlZqFiEECWMYAoorWMhJKdjhPU1b\r\nEgJ2VmqBWQ//XwwZasE4N1FKzwiOkClsFSNli9z26GPsTwnutxKjunICPsZG\r\nPg8rBeihlF7PKcrwhmCYKRn9bDHRbl0875LueW6krPbl57p52kWSLLH5qFYl\r\nbUsP8JhMlf4xyrDXKEOVvMeFFkV3OeoVoRKr+ULtEyEi6NbbIbiHz2Z6rtAR\r\nltFJQzJ5E4PJlAj9VaHzEcd6cJfZco8LNnKZ+F/WrQHTxlvi+We+OZF8IyvG\r\no/BzGCdo+clPooIE+XuJm5ktRK4dsXQR9n4LAqL4lM0HcD8CCnEKOeVcisqa\r\niyKb/et1phwUdRy/rSYVolQ1rjiDpPUgqRCTyNbVf5YuJEeJLPz/dRlwPaqa\r\nb3jnvN5KN815WmDEYpZOyyofMBM9zp9bF/UuFykyLDCJaGmBPjd/9wd6r4Wq\r\nJ3lKZjlFK64PnRYu8v6x7eHBm8qHRiS/v4pFgQ0GmdACGi0hKQZMnvrYpcsq\r\nbN7fGBz9ogzxJ1pZgdX0myx9CXvmhP8ngdZQhxXN6yBPxCK0A/eVV5T4QKs5\r\n1EB0liJy0iK7ghX7cAz2tsdPdJVcrdoLmKM7N5BeYzuTRJbUM9WoaKaPoWDx\r\nM3UhpzoP+WYc5gvNKzhHiDSXLS72xoNGwBVywSc4hE3N+qOXpa2909mO6FrC\r\n/69pzRoo5ZdCc1U2uUkkHNejC5h9WY/ml9Y=\r\n=OpGH\r\n-----END PGP SIGNATURE-----\r\n"},"_npmUser":{"name":"grantila","email":"g.rantila@gmail.com"},"directories":{},"maintainers":[{"name":"grantila","email":"g.rantila@gmail.com"}],"_npmOperationalInternal":{"host":"s3://npm-registry-packages","tmp":"tmp/short-tree_3.0.0_1675371884273_0.10743281629191159"},"_hasShrinkwrap":false}},"time":{"created":"2021-04-01T17:15:27.093Z","1.0.0":"2021-04-01T17:15:27.195Z","modified":"2023-02-02T21:04:44.542Z","2.0.0":"2021-09-13T06:57:05.503Z","3.0.0":"2023-02-02T21:04:44.460Z"},"maintainers":[{"name":"grantila","email":"g.rantila@gmail.com"}],"description":"Keep a tree trimmed from longer-than-necessary branches","homepage":"https://github.com/grantila/short-tree#readme","keywords":["graph","tree","trim"],"repository":{"type":"git","url":"git+https://github.com/grantila/short-tree.git"},"author":{"name":"Gustaf Räntilä"},"bugs":{"url":"https://github.com/grantila/short-tree/issues"},"license":"MIT","readme":"[![npm version][npm-image]][npm-url]\n[![downloads][downloads-image]][npm-url]\n[![build status][build-image]][build-url]\n[![coverage status][coverage-image]][coverage-url]\n[![Node.JS version][node-version]][node-url]\n\n\n# short-tree\n\n`ShortTree` is a class extending `RBTree` from [bintrees][bintrees-npm-url], and **works explicitly on nodes of arrays**.\n\nThe `ShortTree< T >` class extends `RBTree< Array< T > >`.\n\n`insert` is overloaded and behaves differently. When adding a node, it will first check if there is another shorter node being the beginning of the to-be-inserted node, and if so, won't insert. It also checks if there are existing longer nodes which begin with the newly inserted node, and deletes them.\n\nA new function is added `values()` which returns `Array< Array< T > >`, i.e. an array of all nodes (and again, each node is an array of `T`).\n\n\n## Versions\n\n * Since v2 this is a [pure ESM][pure-esm] package, and requires Node.js >=12.20. It cannot be used from CommonJS.\n * Since v3 requires Node.js >= 14.13.1.\n\n\n# Algorithm\n\n\nWhen inserting `[ 'a', 'b', 'c', 'd' ]`, **one** node is inserted with this value.\n\nInserting  `[ 'x', 'y' ]`, will insert **one** new node.\n\nIf later, `[ 'a', 'b', 'c', 'd', 'e' ]` is inserted, it won't be - there's already a \"shorter\" version of this node (the first one inserted).\n\nIf later, `[ 'a', 'b' ]` is inserted, the first node `[ 'a', 'b', 'c', 'd' ]` will be removed (or \"chopped off\" after `b`).\n\n\n# API\n\nConstruct a `ShortTree` by giving the comparison function for `T`.\n\nIf `T` is `number` e.g., this could be `(a, b) => a - b`.\n\n\n## Order\n\nThe order when traversing the values is going to depend on the comparison function provided to the constructor.\n\nE.g. a traditional `(a: string, b: string) => a.localeCompare(b)` will ensure an order for your current locale. You can use `Intl` to define string comparison orders for other situations.\n\nIf the *human friendly* order isn't that important, but speed is critical, use [`fast-string-compare`][fast-string-compare-npm-url].\n\n\n## Example\n\n```ts\nimport { compare } from 'fast-string-compare'\nimport { ShortTree } from 'short-tree'\n\n// T is deduced to {string}\nconst tree = new ShortTree( compare );\n\ntree.insert( [ 'a', 'b', 'c', 'd' ] );\ntree.insert( [ 'x', 'y' ] );\n// This will \"chop off\" (i.e. remove) [ 'a', 'b', 'c', 'd' ]\ntree.insert( [ 'a', 'b' ] );\n\ntree.values( ); // [ [ 'a', 'b' ], [ 'x', 'y' ] ]\n```\n\n\n[npm-image]: https://img.shields.io/npm/v/short-tree.svg\n[npm-url]: https://npmjs.org/package/short-tree\n[downloads-image]: https://img.shields.io/npm/dm/short-tree.svg\n[build-image]: https://img.shields.io/github/actions/workflow/status/grantila/short-tree/master.yml?branch=master\n[build-url]: https://github.com/grantila/short-tree/actions?query=workflow%3AMaster\n[coverage-image]: https://coveralls.io/repos/github/grantila/short-tree/badge.svg?branch=master\n[coverage-url]: https://coveralls.io/github/grantila/short-tree?branch=master\n[node-version]: https://img.shields.io/node/v/short-tree\n[node-url]: https://nodejs.org/en/\n\n[bintrees-npm-url]: https://npmjs.org/package/bintrees\n[fast-string-compare-npm-url]: https://npmjs.org/package/fast-string-compare\n[pure-esm]: https://gist.github.com/sindresorhus/a39789f98801d908bbc7ff3ecc99d99c\n","readmeFilename":"README.md"}