{"_id":"tlhunter-sorted-set","name":"tlhunter-sorted-set","dist-tags":{"latest":"0.1.0"},"versions":{"0.1.0":{"name":"tlhunter-sorted-set","version":"0.1.0","main":"./lib/set.js","author":{"name":"Thomas Hunter II","email":"tlhunter@datadog.com"},"bugs":{"url":"https://github.com/tlhunter/node-sorted-set/issues"},"description":"A skip list implementation inspired by the Sorted Set in Redis.","devDependencies":{"chai":"^4.3.10","mocha":"^10.2.0"},"directories":{"example":"example","lib":"lib","test":"test"},"homepage":"https://github.com/tlhunter/node-sorted-set","keywords":["set","linked-list","skip-list","map","redis"],"license":"MIT","repository":{"type":"git","url":"git+https://github.com/tlhunter/node-sorted-set.git"},"scripts":{"test":"mocha"},"_id":"tlhunter-sorted-set@0.1.0","gitHead":"6838b27811c2a687f8134e89901e9fb7ce14cf52","_nodeVersion":"20.10.0","_npmVersion":"10.2.3","dist":{"integrity":"sha512-eGYW4bjf1DtrHzUYxYfAcSytpOkA44zsr7G2n3PV7yOUR23vmkGe3LL4R+1jL9OsXtbsFOwe8XtbCrabeaEFnw==","shasum":"1c3eae28c0fa4dff97e9501d2e3c204b86406f4b","tarball":"https://registry.npmjs.org/tlhunter-sorted-set/-/tlhunter-sorted-set-0.1.0.tgz","fileCount":6,"unpackedSize":24939,"signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEUCIAO5Fkwz5ZUrxSmfMK/AUzE2/FVtiwLzpfOv49YAwVqFAiEA5ML3cdXh5MA532WUwGR1KPrl5xQRqpG6Doff4h4KumA="}]},"_npmUser":{"name":"tlhunter","email":"me@thomashunter.name"},"maintainers":[{"name":"tlhunter","email":"me@thomashunter.name"}],"_npmOperationalInternal":{"host":"s3://npm-registry-packages","tmp":"tmp/tlhunter-sorted-set_0.1.0_1702077931825_0.7438726489531535"},"_hasShrinkwrap":false}},"time":{"created":"2023-12-08T23:25:31.824Z","0.1.0":"2023-12-08T23:25:32.075Z","modified":"2023-12-08T23:25:32.380Z"},"maintainers":[{"name":"tlhunter","email":"me@thomashunter.name"}],"description":"A skip list implementation inspired by the Sorted Set in Redis.","homepage":"https://github.com/tlhunter/node-sorted-set","keywords":["set","linked-list","skip-list","map","redis"],"repository":{"type":"git","url":"git+https://github.com/tlhunter/node-sorted-set.git"},"author":{"name":"Thomas Hunter II","email":"tlhunter@datadog.com"},"bugs":{"url":"https://github.com/tlhunter/node-sorted-set/issues"},"license":"MIT","readme":"# tlhunter-sorted-set\n\nA JavaScript implementation of Redis' [Sorted Sets](https://redis.io/commands#sorted_set). Keeps a collection of \"members\" in order based on their score. Uses skip lists under the hood, [like Redis does](http://stackoverflow.com/a/9626334/638546).\n\nThis is a fork of the brilliant but abandoned [redis-sorted-map](https://www.npmjs.com/package/redis-sorted-map) package by [Akseli Palén](https://github.com/axelpale) which was itself a fork of the brilliant but abandoned [sorted-map](https://www.npmjs.com/package/sorted-map) package by [Eli Skeggs](https://github.com/skeggse).\n\n![A Skip List](/doc/skip-list.png?raw=true)\n\nImage: The skip list data structure allows search, insert, and removal in O(log(n)) time in average.\n\n## Install\n\n```sh\n$ npm install tlhunter-sorted-set\n```\n\n\n## Test\n\nRun any of the following:\n\n```sh\n$ npm test\n```\n\n_Note:_ remember to `npm install`!\n\n\n## API\n\nThe API mostly follows Redis' [Sorted Set Commands](https://redis.io/commands#sorted_set), with a few additional methods such as `.has(member)`.\n\nMembers can be strings, symbols, objects, or really any primitive value.\n\n```js\nconst SortedSet = require('tlhunter-sorted-set');\n\nconst z = new SortedSet();\n\n// average O(log(N))\nz.add('Terminator', 8.0); // => null\nz.add('District 9', 8.0); // => null\nz.add('Ex Machina', 0.7); // => null\nz.add('Ex Machina', 7.7); // => 0.7\n// alias\nz.set('The Matrix', 8.7); // => null\n\n// average O(1)\nz.has('Terminator'); // => true\nz.has('Blade Runner'); // => false\n\n// average O(1)\nz.score('Ex Machina'); // => 7.7\nz.score('Blade Runner'); // => null\n// alias\nz.get('The Matrix'); // => 8.7\n\n// average O(log(N))\nz.rem('Ex Machina'); // => 7.7\n// average O(1)\nz.rem('Ex Machina'); // => null\n// alias\nz.del('Ex Machina'); // => null\n\n// average O(log(N)+M) where M is the number of elements between min and max\nz.rangeByScore(7, 8);\n// => ['Ex Machina', 'District 9', 'Terminator']\nz.rangeByScore(8); // [8.0-∞)\n// => ['District 9', 'Terminator', 'The Matrix']\nz.rangeByScore(8, null, { withScores: true });\n// => [['District 9', 8.0], ['Terminator', 8.0], ['The Matrix', 8.7]]\n\n// average O(log(N)+log(M)) where M as in rangeByScore\nz.count(7, 8); // => 3\n\n// average O(log(N))\nz.rank('Ex Machina'); // => 0\nz.rank('Terminator'); // => 2\nz.rank('Blade Runner'); // => null\n\n// average O(log(N)+M) where M as in range\nz.range(0, 2);\n// => ['Ex Machina', 'District 9', 'Terminator']\nz.range(0, 2, { withScores: true });\n// => [['Ex Machina', 7.7],\n//     ['District 9', 8],\n//     ['Terminator', 8]]\nz.range(-1); // => ['The Matrix']\n// almost alias\nz.slice(0, 3);\n// => ['Ex Machina', 'District 9', 'Terminator']\n\n// Set cardinality (number of elements)\n// average O(1)\nz.card(); // => 4\n// alias\nz.length // => 4\n\n```\n\n\n## Intersection\n\n```js\nconst a = new SortedSet(), b = new SortedSet();\n\na.add('5a600e10', 16);\na.add('5a600e12', 10);\na.add('5a600e14', 9);\na.add('5a600e15', 14);\na.add('5a600e17', 20);\na.add('5a600e18', 13);\na.add('5a600e19', 15);\na.add('5a600e1a', 19);\na.add('5a600e1b', 7);\na.add('5a600e1c', 13);\na.add('5a600e1e', 10);\n\nb.add('5a600e10', 0);\nb.add('5a600e11', 15);\nb.add('5a600e13', 5);\nb.add('5a600e14', 3);\nb.add('5a600e15', 14);\nb.add('5a600e17', 12);\nb.add('5a600e19', 12);\nb.add('5a600e1b', 16);\nb.add('5a600e1c', 12);\nb.add('5a600e1d', 17);\nb.add('5a600e1f', 3);\n\nSortedSet.intersect(a, b);\n// => ['5a600e10', '5a600e14', '5a600e17', '5a600e19', '5a600e1c', '5a600e15', '5a600e1b']\n\nSortedSet.intersect(b, a);\n// => ['5a600e1b', '5a600e14', '5a600e1c', '5a600e15', '5a600e19', '5a600e10', '5a600e17']\n\n// works, but not preferred\na.intersect(b);\n// => ['5a600e10', '5a600e14', '5a600e17', '5a600e19', '5a600e1c', '5a600e15', '5a600e1b']\n\nconst c = new SortedSet();\n\nc.add('5a600e10', 7);\nc.add('5a600e12', 20);\nc.add('5a600e13', 9);\nc.add('5a600e14', 19);\nc.add('5a600e16', 19);\nc.add('5a600e17', 1);\nc.add('5a600e18', 18);\nc.add('5a600e1a', 6);\nc.add('5a600e1c', 15);\nc.add('5a600e1f', 4);\n\n// for best performance, the smallest set should be first\nSortedSet.intersect(c, a, b);\n// => ['5a600e10', '5a600e14', '5a600e17', '5a600e1c']\n```\n\n\n## Unique\n\nYou can enable unique values with the unique option, which causes `set` to throw an error if the value provided already belongs to a different key.\n\n```js\nconst z = new SortedSet({unique: true});\n\nz.add('5a600e10', 16);\nz.add('5a600e11', 6);\nz.add('5a600e12', 17);\nz.add('5a600e13', 11);\nz.add('5a600e14', 14);\nz.add('5a600e15', 19);\nz.add('5a600e16', 3);\nz.add('5a600e17', 12);\nz.add('5a600e18', 10);\n\n// currently O(log(N)) because it needs to attempt to insert the value\nz.add('5a600e19', 11); // throws\nz.add('5a600e14', 14); // => 14\n```\n\n\n## Licence\n\nMIT\n","readmeFilename":"README.md"}