{"_id":"@data-structs/skip-list","_rev":"3-468b17ad9e30cf00b36fea9ddc3f3346","name":"@data-structs/skip-list","dist-tags":{"latest":"1.0.2"},"versions":{"1.0.0":{"name":"@data-structs/skip-list","version":"1.0.0","main":"dist/cjs/index.js","author":{"name":"Jared Lunde","email":"jared@BeStellar.co","url":"https://BeStellar.co"},"license":"MIT","sideEffects":false,"module":"dist/es/index.js","repository":{"type":"git","url":"https://github.com/jaredLunde/data-structs/tree/master/packages/skip-list"},"scripts":{"build":"yarn run build:es && yarn run build:cjs","build:es":"rimraf dist/es && cross-env NODE_ENV=production BABEL_ENV=es babel src --out-dir dist/es --ignore **/*.test.js && npm run prettier:es","build:cjs":"rimraf dist/cjs && cross-env NODE_ENV=production BABEL_ENV=cjs babel src --out-dir dist/cjs --ignore **/*.test.js && npm run prettier:cjs","watch":"rimraf dist/es && cross-env NODE_ENV=production BABEL_ENV=es babel src -w --out-dir dist/es --ignore **/*.test.js","prettier":"prettier --single-quote --no-semi --no-bracket-spacing --trailing-comma es5 --write","prettier:es":"yarn prettier \"dist/es/**/*.js\"","prettier:cjs":"yarn prettier \"dist/cjs/**/*.js\"","prepublishOnly":"yarn test && yarn build","test":"BABEL_ENV=cjs ava -v"},"ava":{"files":["src/**/*.test.js"],"require":["@babel/register"]},"devDependencies":{"@babel/register":"^7.4.0","@stellar-apps/babel-preset-es":"^1.0.4","ava":"^1.4.1","chalk":"^2.4.2","performance-now":"^2.1.0","prettier":"^1.17.0","rimraf":"^2.6.3"},"dependencies":{"@data-structs/doubly-linked-list":"^1.0.5","@data-structs/linked-list":"^1.0.13"},"description":"A generalized self-balancing skip list implemented in Javascript. You can insert any value types you wish so long as you provide your own comparator function. The default comparator is `(a, b) => a - b` which only allows for numeric comparisons.","licenseText":"The MIT License (MIT)\n\nCopyright (c) 2019 Jared Lunde\n\nPermission is hereby granted, free of charge, to any person obtaining a copy\nof this software and associated documentation files (the \"Software\"), to deal\nin the Software without restriction, including without limitation the rights\nto use, copy, modify, merge, publish, distribute, sublicense, and/or sell\ncopies of the Software, and to permit persons to whom the Software is\nfurnished to do so, subject to the following conditions:\n\nThe above copyright notice and this permission notice shall be included in all\ncopies or substantial portions of the Software.\n\nTHE SOFTWARE IS PROVIDED \"AS IS\", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR\nIMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,\nFITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE\nAUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER\nLIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,\nOUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE\nSOFTWARE.","_id":"@data-structs/skip-list@1.0.0","dist":{"shasum":"24cff8f1c80295ec9a9c68a9d78a2ef52bc29fc5","integrity":"sha512-eJCdbLuufkT1quRkiogTNULs2c5VKqX0BL6Zo0DhCzV0LwA37MIigk+TZuqY5tpbaXZeH/Y60BFff+YIIxKA4Q==","tarball":"https://registry.npmjs.org/@data-structs/skip-list/-/skip-list-1.0.0.tgz","fileCount":14,"unpackedSize":80423,"npm-signature":"-----BEGIN PGP SIGNATURE-----\r\nVersion: OpenPGP.js v3.0.4\r\nComment: https://openpgpjs.org\r\n\r\nwsFcBAEBCAAQBQJctjchCRA9TVsSAnZWagAAL1gP/1gOUpaYVY8xjAdYc62r\n6mO9xTdpYPOIdhol93XLiUGvr67hmu3sqGQPa7NWBm+tzFg9xaKiuAiBnMGL\nCCNx3uIuy8HTEPC57Xg+nCBZe/8/u46V8CQDKbiaZWpN6GPtkRA+8ZgNb/oT\nl03RzdunmQbIFwbU/rRicFkPa/myrrk7/brzUUqXhbxG8sKVMA90NNrkTw49\ncf/w2XEiErHvoIG1UBE8VA0NCFspv4kEskmHvGQLNGRR5L4qhZdjZcmTTIz+\nMZ6Qmz4XnU3CFa9btSK8iV2eXkI+18zn4GVLpDrvZr3+6TpOjIdilusyvcJ4\nDXfabmCRQj1CqURS5zL7rLHd0iLvueDqjkILTxWNNaj9BxwSXzwnBE3ZQ6TO\nKRXGlS1HTgch+vqpzWse0eVNqeW/n2UQUTuO9FU9WXTJv6ZUTl6b7pFo3sE2\n48WAdpku1xw55Q3mQgF2pKpgzKE+f27BeLvz69LPUc9wzU9sVugJRA66Z1D7\nJLNAzGyGG5QOofDLLZkb3euiqWN3WBqSlv8VvVZxWG9345nv6pB5zoWc41ZQ\nVqyjv6lRRx2PSEAKaRl7DoGdMxg9tE3smb/5y4w/iZuvI4aPUV6EZIxNVizA\njw0dpyIfMuZ6EDIRHGTNUYnk4ZNdSBd624mkdQ0mU0lJFQ4YPpO3EcLa//UI\nCfcJ\r\n=HjAD\r\n-----END PGP SIGNATURE-----\r\n","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEYCIQD2iFRxDqr3wvmPtxHkKAKvybCXf3uji7XBiNpcmDIciwIhAOMTkulhycmiEsLgcVz3k8RH9INYGBJ0TTfIJcds2uEN"}]},"maintainers":[{"name":"jaredlunde","email":"jared@BeStellar.co"}],"_npmUser":{"name":"jaredlunde","email":"jared@BeStellar.co"},"directories":{},"_npmOperationalInternal":{"host":"s3://npm-registry-packages","tmp":"tmp/skip-list_1.0.0_1555445537082_0.403827055435936"},"_hasShrinkwrap":false},"1.0.1":{"name":"@data-structs/skip-list","version":"1.0.1","main":"dist/cjs/index.js","author":{"name":"Jared Lunde","email":"jared@BeStellar.co","url":"https://BeStellar.co"},"license":"MIT","sideEffects":false,"module":"dist/es/index.js","repository":{"type":"git","url":"https://github.com/jaredLunde/data-structs/tree/master/packages/skip-list"},"scripts":{"build":"yarn run build:es && yarn run build:cjs","build:es":"rimraf dist/es && cross-env NODE_ENV=production BABEL_ENV=es babel src --out-dir dist/es --ignore **/*.test.js && npm run prettier:es","build:cjs":"rimraf dist/cjs && cross-env NODE_ENV=production BABEL_ENV=cjs babel src --out-dir dist/cjs --ignore **/*.test.js && npm run prettier:cjs","watch":"rimraf dist/es && cross-env NODE_ENV=production BABEL_ENV=es babel src -w --out-dir dist/es --ignore **/*.test.js","prettier":"prettier --single-quote --no-semi --no-bracket-spacing --trailing-comma es5 --write","prettier:es":"yarn prettier \"dist/es/**/*.js\"","prettier:cjs":"yarn prettier \"dist/cjs/**/*.js\"","prepublishOnly":"yarn test && yarn build","test":"BABEL_ENV=cjs ava -v"},"ava":{"files":["src/**/*.test.js"],"require":["@babel/register"]},"devDependencies":{"@babel/register":"^7.4.0","@essentials/benchmark":"^1.0.4","@stellar-apps/babel-preset-es":"^1.0.4","ava":"^1.4.1","chalk":"^2.4.2","performance-now":"^2.1.0","prettier":"^1.17.0","rimraf":"^2.6.3"},"dependencies":{"@data-structs/doubly-linked-list":"^1.0.5","@data-structs/linked-list":"^1.0.13"},"description":"A generalized self-balancing skip list implemented in Javascript. You can insert any value types you wish so long as you provide your own comparator function. The default comparator is `(a, b) => a - b` which only allows for numeric comparisons. As you mi","licenseText":"The MIT License (MIT)\n\nCopyright (c) 2019 Jared Lunde\n\nPermission is hereby granted, free of charge, to any person obtaining a copy\nof this software and associated documentation files (the \"Software\"), to deal\nin the Software without restriction, including without limitation the rights\nto use, copy, modify, merge, publish, distribute, sublicense, and/or sell\ncopies of the Software, and to permit persons to whom the Software is\nfurnished to do so, subject to the following conditions:\n\nThe above copyright notice and this permission notice shall be included in all\ncopies or substantial portions of the Software.\n\nTHE SOFTWARE IS PROVIDED \"AS IS\", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR\nIMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,\nFITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE\nAUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER\nLIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,\nOUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE\nSOFTWARE.","_id":"@data-structs/skip-list@1.0.1","dist":{"shasum":"c7f8dd8f1ba8c815fdb23ecadc0c62ce19f43ae8","integrity":"sha512-7JdAL247Z89QtUNwNPEhuTRonWb3v38iioTiFC14hiEO85Tp+Rj6eQuRXbf627cF5NAnN+88yb2KpZfo5OUu8A==","tarball":"https://registry.npmjs.org/@data-structs/skip-list/-/skip-list-1.0.1.tgz","fileCount":13,"unpackedSize":53239,"npm-signature":"-----BEGIN PGP SIGNATURE-----\r\nVersion: OpenPGP.js v3.0.4\r\nComment: https://openpgpjs.org\r\n\r\nwsFcBAEBCAAQBQJctnS7CRA9TVsSAnZWagAAh9wP/1iZr4khBv3esoCSDCS0\nB8qtSBDr55EaKbm2Y9Ah6ElIWCJ+pYImOl7VozKDVJJysy7RfTBK0pL4yYYj\nofaNzh9Nw+PCaNBRzJGxtkB4GXuo6xOMozUbVmwO0sbz3eAuNiANbK+kBfUx\n65XYyVB0YuWc6XDh+7LBGuepklsKH433udj2+1hmVSDijEWC+uz+5Jci36Rz\n8410fhcC5T5LDnofzC/Elwo8blDoNgndiFY2rZSYqjEuqwfyekvdR7dU8KL6\n+xCUpkhhG92OnVbW5CiQtOU38szus8vsTQa45+9APIysgc2yEYNNK1ywOFpd\ny5mofgIsobBmslw1531NzWcgolZ6kUjgC4T5yslTCod75lGGmgqDfb2E4EvY\n87EN+1zYncnnr7P70CmtVWmqIXl5Ea+oWV4VIxxNUBxDSnB1bhLJH4fy3Z9A\n7Z84Bsnma9onH9bBkjzzrwsCRvn6Drl3IGeXsxBrv0UiG8h1NvW9RwejtH+Z\ne7EfowdWP/4iFJICexNra0KB+jYsBtA8h9I+iuO5IRWyASOggdZaw2/x6qyr\nxUhSmgXyykCf7cCTPvMliwARAfLYhpfP8wDtINQPc2MzMM2/TORZ97aKz1mZ\np9/vTMH9sYM5SkZA+KwOQ3E4ZzVWzbYnXtfLKRaPnyOByPxTtrAX8mkX1/p4\nwfgc\r\n=ykFj\r\n-----END PGP SIGNATURE-----\r\n","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEUCIGVBuAtBzT2HZxMizS5QQQwn9jCv7JtRSODKGb1GwZ4qAiEA6dKMdEt96psSqwjVzfBGvZHQmyttDoKxg83zAypfc6U="}]},"maintainers":[{"name":"jaredlunde","email":"jared@BeStellar.co"}],"_npmUser":{"name":"jaredlunde","email":"jared@BeStellar.co"},"directories":{},"_npmOperationalInternal":{"host":"s3://npm-registry-packages","tmp":"tmp/skip-list_1.0.1_1555461306761_0.05610178156641865"},"_hasShrinkwrap":false},"1.0.2":{"name":"@data-structs/skip-list","version":"1.0.2","main":"dist/cjs/index.js","author":{"name":"Jared Lunde","email":"jared@BeStellar.co","url":"https://BeStellar.co"},"license":"MIT","sideEffects":false,"module":"dist/es/index.js","repository":{"type":"git","url":"https://github.com/jaredLunde/data-structs/tree/master/packages/skip-list"},"scripts":{"build":"yarn run build:es && yarn run build:cjs","build:es":"rimraf dist/es && cross-env NODE_ENV=production BABEL_ENV=es babel src --out-dir dist/es --ignore **/*.test.js && npm run prettier:es","build:cjs":"rimraf dist/cjs && cross-env NODE_ENV=production BABEL_ENV=cjs babel src --out-dir dist/cjs --ignore **/*.test.js && npm run prettier:cjs","watch":"rimraf dist/es && cross-env NODE_ENV=production BABEL_ENV=es babel src -w --out-dir dist/es --ignore **/*.test.js","prettier":"prettier --single-quote --no-semi --no-bracket-spacing --trailing-comma es5 --write","prettier:es":"yarn prettier \"dist/es/**/*.js\"","prettier:cjs":"yarn prettier \"dist/cjs/**/*.js\"","prepublishOnly":"yarn test && yarn build","test":"BABEL_ENV=cjs ava -v"},"ava":{"files":["src/**/*.test.js"],"require":["@babel/register"]},"devDependencies":{"@babel/register":"^7.4.0","@essentials/benchmark":"^1.0.4","@stellar-apps/babel-preset-es":"^1.0.4","ava":"^1.4.1","chalk":"^2.4.2","performance-now":"^2.1.0","prettier":"^1.17.0","rimraf":"^2.6.3"},"dependencies":{"@data-structs/doubly-linked-list":"^1.0.6","@data-structs/linked-list":"^1.0.15"},"description":"A generalized self-balancing skip list implemented in Javascript. You can insert any value types you wish so long as you provide your own comparator function. The default comparator is `(a, b) => a - b` which only allows for numeric comparisons. As you mi","licenseText":"The MIT License (MIT)\n\nCopyright (c) 2019 Jared Lunde\n\nPermission is hereby granted, free of charge, to any person obtaining a copy\nof this software and associated documentation files (the \"Software\"), to deal\nin the Software without restriction, including without limitation the rights\nto use, copy, modify, merge, publish, distribute, sublicense, and/or sell\ncopies of the Software, and to permit persons to whom the Software is\nfurnished to do so, subject to the following conditions:\n\nThe above copyright notice and this permission notice shall be included in all\ncopies or substantial portions of the Software.\n\nTHE SOFTWARE IS PROVIDED \"AS IS\", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR\nIMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,\nFITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE\nAUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER\nLIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,\nOUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE\nSOFTWARE.","_id":"@data-structs/skip-list@1.0.2","dist":{"shasum":"3a21e50750d53c6b7331140ebe8b2bfc034f4f21","integrity":"sha512-42xV1rEM8u3uvjiAwTgeA0k99tMR+jXMclOLdEwYA8WW2HqGWhd/KA5iM+71MDdPLfb5v8BlPbFuCwUaQwCC3Q==","tarball":"https://registry.npmjs.org/@data-structs/skip-list/-/skip-list-1.0.2.tgz","fileCount":13,"unpackedSize":53309,"npm-signature":"-----BEGIN PGP SIGNATURE-----\r\nVersion: OpenPGP.js v3.0.4\r\nComment: https://openpgpjs.org\r\n\r\nwsFcBAEBCAAQBQJctot7CRA9TVsSAnZWagAAMhUP/RZVGe208URATJPp98Ci\n694fOoLn9IdKv6V6fG4kLa6aThkjGOn0zVlkF+JW8kyV2fYoenvGf3BvG2Dj\nvbJntfhJLHklACZlaWsCilq1UHo1Ah0Q8Abdv7UmB3yYxRK1rMkAjxSIryFm\njwCvy9hzy5Ic6qo6u0gicUOlHozHnHuUbPKoDGHlfZQyzdlg/pA32PhvzwGr\neS28mt7PBZTppJE5/4qs1MCn7YoOBv7fl7i4+k82JdBUCkbvqoRv/Io1hkcZ\nu6nk14VEZsBOL9U6E0Vi7jW6+dtvUUegSvF2lVP/nG5hLjl+M8VWE77ODtJu\n0UoqM5bwvq8wzGq1j7p3SSRkPP3/v1yQTfp+WlT1sG4SaFrpRfVFB6saWXxW\nnWPsLSHofmFp31q+1OBYk4FAhbEC6fN/7T6LgsAWFBAFH1pV3iNBC7Qj92tN\n9brNuFP+c2YmvYtvpl5TG8RTV0IYm1XibVqw9bqAdH6ShIguDfzP6UxVxHtr\n0DiWSH6nUtZn3suvKUyqgi57d8RGkVHPNOzscoXqkjYq329G8ZUkAeVonGXd\nsSJnSQf87Qqp23FWQWfo9o7k9wjCSOR61NkrjBRzBzqBgoNMQGCvVWKXKU+h\ne2hFl0n3AmAPv26kY2p4fiMcXBQCXpXstnlC+lopemWOJ7snkHXyVM+CBVAP\nqVLL\r\n=0cma\r\n-----END PGP SIGNATURE-----\r\n","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEYCIQCJi8BCk91TWrXS7AII3DWFy46PxyQFM+as4L6XXkkGSQIhAInuTAtzOPVSeAO3XfdqjPeeb8FWleBTPaPd5LSJaDaU"}]},"maintainers":[{"name":"jaredlunde","email":"jared@BeStellar.co"}],"_npmUser":{"name":"jaredlunde","email":"jared@BeStellar.co"},"directories":{},"_npmOperationalInternal":{"host":"s3://npm-registry-packages","tmp":"tmp/skip-list_1.0.2_1555467130599_0.36183462811220335"},"_hasShrinkwrap":false}},"time":{"created":"2019-04-16T20:12:16.881Z","1.0.0":"2019-04-16T20:12:17.192Z","modified":"2022-04-05T02:50:45.704Z","1.0.1":"2019-04-17T00:35:06.889Z","1.0.2":"2019-04-17T02:12:10.876Z"},"maintainers":[{"name":"jaredlunde","email":"jared@BeStellar.co"}],"description":"A generalized self-balancing skip list implemented in Javascript. You can insert any value types you wish so long as you provide your own comparator function. The default comparator is `(a, b) => a - b` which only allows for numeric comparisons. As you mi","repository":{"type":"git","url":"https://github.com/jaredLunde/data-structs/tree/master/packages/skip-list"},"author":{"name":"Jared Lunde","email":"jared@BeStellar.co","url":"https://BeStellar.co"},"license":"MIT","readme":"# @data-structs/skip-list\nA generalized self-balancing skip list implemented in Javascript. You\ncan insert any value types you wish so long as you provide your own\ncomparator function. The default comparator is `(a, b) => a - b` which\nonly allows for numeric comparisons. As you might guess, values are\nconsidered equal when the comparator function returns `0`.\n\nThe algorithm for height-selection is more predictably balanced than a\ntraditional coin-flip model while maintaining an element of randomness\nin selections. This is accomplished by randomly selecting levels where\nthe expected number of elements is fewer than the actual number of\nelements in that level. The expected number of elements for a level is\ncalculated using `Math.floor((2**(-1 * level)) * n)` which ensures each\nsubsequent level has half as many elements as its predecessor, providing\nO(log n) insertions and searches with high probability.\n\n## Installation\n`yarn add @data-structs/skip-list`\n\n## Usage\n```js\nimport skipList from '@data-structs/skip-list'\n\nconst mySkipList = skipList(\n  Array.from(Array(16), () => Math.floor(Math.random() * (16 * 2)))\n)\n\nskipList.size        // 16\nskipList.insert(196) // 17\nskipList.has(196)    // true\nskipList.remove(196) // 16\nskipList.forEach(console.log)\n```\n\n## Implementation details\n```\n[3] Sentinel ->                                                948\n[2] Sentinel ->                    545 <>                      948\n[1] Sentinel ->             302 <> 545 <>               926 <> 948 \n[0]            32 <> 218 <> 302 <> 545 <> 840 <> 855 <> 926 <> 948\n```\n-  All levels are implemented using doubly-linked lists\n- `O(1)` insert at head + tail\n  - Ultra-fast inserts when the inserted value is certainly less than or\n    equal to the head or certainly greater than or equal to the tail\n- `O(log(n))` insert at mid with high probability\n- `O(1)` remove at head + tail\n  - Ultra-fast inserts when the removed value is certainly the head\n    or certainly the tail\n- `O(log(n))` remove at mid with high probability\n- `O(log(n))` search with high probability\n- `O(1)` search bailout when value is certainly less than the head value\n  or certainly greater than the tail value\n- `O(n log(n))` space complexity ","readmeFilename":"README.md"}