{"_id":"interval-skip-list","_rev":"28-bc2aed7c538c134ee5f56eb35e3909e8","name":"interval-skip-list","description":"A data structure for finding all intervals that overlap a point in O(ln n)","dist-tags":{"latest":"2.0.1"},"versions":{"0.1.0":{"name":"interval-skip-list","version":"0.1.0","description":"A data structure for finding all intervals that overlap a point in O(ln n)","main":"lib/interval-skip-list.js","scripts":{"test":"grunt test"},"repository":{"type":"git","url":"http://github.com/atom/interval-skip-list.git"},"bugs":{"url":"https://github.com/atom/interval-skip-list/issues"},"homepage":"http://atom.github.io/interval-skip-list","keywords":["data-structures","collections","intervals"],"author":{"name":"Nathan Sobo"},"licenses":[{"type":"MIT","url":"http://github.com/atom/interval-skip-list/raw/master/LICENSE.md"}],"dependencies":{"underscore":"~1.5.1"},"devDependencies":{"coffee-script":"~1.6.3","jasmine-focused":"~0.12.0","grunt-contrib-coffee":"~0.7.0","grunt-cli":"~0.1.8","grunt":"~0.4.1","grunt-shell":"~0.2.2","grunt-coffeelint":"0.0.6","rimraf":"~2.2.2"},"_id":"interval-skip-list@0.1.0","dist":{"shasum":"3892e9da7ba38f65c8587549f6f8ca994b1b9e79","tarball":"https://registry.npmjs.org/interval-skip-list/-/interval-skip-list-0.1.0.tgz","integrity":"sha512-oWT3flrxi0gcmqxRspn1W7fBK/Ae3R5eojThdDPKhlRxM0FfYWzRxWpZNYKHWSdEuqWSaHmuGpfA1UTz/oYgxQ==","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEYCIQCivKesS0uX5Ft2ZC9IpAKDBBQUpNVwV7n/HBd8L7CKnQIhANiwAwEWtzDYUDypM+GmLkj+8jGMkXxZTA5WZ15j9+5e"}]},"_from":".","_npmVersion":"1.3.8","_npmUser":{"name":"nathansobo","email":"nathansobo@gmail.com"},"maintainers":[{"name":"nathansobo","email":"nathansobo@gmail.com"}],"directories":{}},"0.2.0":{"name":"interval-skip-list","version":"0.2.0","description":"A data structure for finding all intervals that overlap a point in O(ln n)","main":"lib/interval-skip-list.js","scripts":{"test":"grunt test"},"repository":{"type":"git","url":"http://github.com/atom/interval-skip-list.git"},"bugs":{"url":"https://github.com/atom/interval-skip-list/issues"},"homepage":"http://atom.github.io/interval-skip-list","keywords":["data-structures","collections","intervals"],"author":{"name":"Nathan Sobo"},"licenses":[{"type":"MIT","url":"http://github.com/atom/interval-skip-list/raw/master/LICENSE.md"}],"dependencies":{"underscore":"~1.5.1"},"devDependencies":{"coffee-script":"~1.6.3","jasmine-focused":"~0.12.0","grunt-contrib-coffee":"~0.7.0","grunt-cli":"~0.1.8","grunt":"~0.4.1","grunt-shell":"~0.2.2","grunt-coffeelint":"0.0.6","rimraf":"~2.2.2"},"_id":"interval-skip-list@0.2.0","dist":{"shasum":"e86f471bb2961ca25a7edb5e1f7b63003c53b138","tarball":"https://registry.npmjs.org/interval-skip-list/-/interval-skip-list-0.2.0.tgz","integrity":"sha512-qiToIpjZmraGiDnGNMyCWaw19Pf9k06+kpxDOEmBBczZMeyGSCcPBmWX7AE9Ch0Yd6o0gBmdo0jZfwBAcLGHWg==","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEQCIASsYjmtN3hy3FHF+gyfNURtn2ZajypGxDvR5m2qZJXWAiBR6gj0zxe96AVtuEPm0IRveNrCrsGwofA77ZX2pDqRxQ=="}]},"_from":".","_npmVersion":"1.3.8","_npmUser":{"name":"nathansobo","email":"nathansobo@gmail.com"},"maintainers":[{"name":"nathansobo","email":"nathansobo@gmail.com"}],"directories":{}},"0.3.0":{"name":"interval-skip-list","version":"0.3.0","description":"A data structure for finding all intervals that overlap a point in O(ln n)","main":"lib/interval-skip-list.js","scripts":{"prepublish":"grunt clean lint coffee","test":"grunt test"},"repository":{"type":"git","url":"http://github.com/atom/interval-skip-list.git"},"bugs":{"url":"https://github.com/atom/interval-skip-list/issues"},"homepage":"http://atom.github.io/interval-skip-list","keywords":["data-structures","collections","intervals"],"author":{"name":"Nathan Sobo"},"licenses":[{"type":"MIT","url":"http://github.com/atom/interval-skip-list/raw/master/LICENSE.md"}],"dependencies":{"underscore":"~1.5.1"},"devDependencies":{"coffee-script":"~1.6.3","jasmine-focused":"~0.12.0","grunt-contrib-coffee":"~0.7.0","grunt-cli":"~0.1.8","grunt":"~0.4.1","grunt-shell":"~0.2.2","grunt-coffeelint":"0.0.6","rimraf":"~2.2.2"},"_id":"interval-skip-list@0.3.0","dist":{"shasum":"669bb696a42d469127427760bb4811417e25db85","tarball":"https://registry.npmjs.org/interval-skip-list/-/interval-skip-list-0.3.0.tgz","integrity":"sha512-2Bt0C0no2HpIL0OMyXpo/S5H+f/2XYXbbTm5otx0Lgt308q08y5iP4ytbFNBhuq9nw/q8M3PiMSCYmeYwqH8Mg==","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEQCIA4+usLINmxJjwTnDV0vog+75pAOS+GHFbXZXtsUn3JlAiAww7L6YEYGi8vgPyqRYqRLeOwdHVjxxsCB5svh6VjfyA=="}]},"_from":".","_npmVersion":"1.3.14","_npmUser":{"name":"nathansobo","email":"nathansobo@gmail.com"},"maintainers":[{"name":"nathansobo","email":"nathansobo@gmail.com"}]},"0.4.0":{"name":"interval-skip-list","version":"0.4.0","description":"A data structure for finding all intervals that overlap a point in O(ln n)","main":"lib/interval-skip-list.js","scripts":{"prepublish":"grunt clean lint coffee","test":"grunt test"},"repository":{"type":"git","url":"http://github.com/atom/interval-skip-list.git"},"bugs":{"url":"https://github.com/atom/interval-skip-list/issues"},"homepage":"http://atom.github.io/interval-skip-list","keywords":["data-structures","collections","intervals"],"author":{"name":"Nathan Sobo"},"licenses":[{"type":"MIT","url":"http://github.com/atom/interval-skip-list/raw/master/LICENSE.md"}],"dependencies":{"underscore":"~1.5.1"},"devDependencies":{"coffee-script":"~1.6.3","jasmine-focused":"~0.12.0","grunt-contrib-coffee":"~0.7.0","grunt-cli":"~0.1.8","grunt":"~0.4.1","grunt-shell":"~0.2.2","grunt-coffeelint":"0.0.6","rimraf":"~2.2.2"},"_id":"interval-skip-list@0.4.0","dist":{"shasum":"39222d002b19af14885d7ecd53337a74c543d90a","tarball":"https://registry.npmjs.org/interval-skip-list/-/interval-skip-list-0.4.0.tgz","integrity":"sha512-JfGo+pZKgiQOWGzeNyIQi5Xm12fph+ikgUQ7ghmiX/LiOJsVFbJ9SyTtKNvqyMGLC9AEtA6drv+ZHKJlt8CA9A==","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEUCIACChzlHGxjrJvD5HoRoruwFlVMrPUQP86yGGc96RLN6AiEAzdLI5YhLYVSoM7jfgPXbUjA68z9o1mWatCVFkwqVAqU="}]},"_from":".","_npmVersion":"1.3.14","_npmUser":{"name":"nathansobo","email":"nathansobo@gmail.com"},"maintainers":[{"name":"nathansobo","email":"nathansobo@gmail.com"}]},"1.0.0":{"name":"interval-skip-list","version":"1.0.0","description":"A data structure for finding all intervals that overlap a point in O(ln n)","main":"lib/interval-skip-list.js","scripts":{"prepublish":"grunt clean lint coffee","test":"grunt test"},"repository":{"type":"git","url":"http://github.com/atom/interval-skip-list.git"},"bugs":{"url":"https://github.com/atom/interval-skip-list/issues"},"homepage":"http://atom.github.io/interval-skip-list","keywords":["data-structures","collections","intervals"],"author":{"name":"Nathan Sobo"},"licenses":[{"type":"MIT","url":"http://github.com/atom/interval-skip-list/raw/master/LICENSE.md"}],"dependencies":{"underscore":"~1.5.1"},"devDependencies":{"coffee-script":"~1.6.3","jasmine-focused":"~0.12.0","grunt-contrib-coffee":"~0.7.0","grunt-cli":"~0.1.8","grunt":"~0.4.1","grunt-shell":"~0.2.2","grunt-coffeelint":"0.0.6","rimraf":"~2.2.2"},"_id":"interval-skip-list@1.0.0","dist":{"shasum":"046f50dcdaa8f1052fb4cc8ab6190cd42c02b461","tarball":"https://registry.npmjs.org/interval-skip-list/-/interval-skip-list-1.0.0.tgz","integrity":"sha512-oFTk1lkaybhOntknGh0OEBlw7ES36KbKtttM+61L1G6DM9wwtho3c01MKyp/EB1ZbfD5VGs3kQyoVRBFF7PHsQ==","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEUCICCGW5aSkGD0wLSqpY+sgi5ohaC9sbX7aksdXgM7p01eAiEA1hY5x+Wp3h34wOM2AkM0Va41LZyCnNqhzgH/cTR9KKA="}]},"_from":".","_npmVersion":"1.4.4","_npmUser":{"name":"nathansobo","email":"nathansobo@gmail.com"},"maintainers":[{"name":"nathansobo","email":"nathansobo@gmail.com"}]},"2.0.0":{"name":"interval-skip-list","version":"2.0.0","description":"A data structure for finding all intervals that overlap a point in O(ln n)","main":"lib/interval-skip-list.js","scripts":{"prepublish":"grunt clean lint coffee","test":"grunt test"},"repository":{"type":"git","url":"http://github.com/atom/interval-skip-list.git"},"bugs":{"url":"https://github.com/atom/interval-skip-list/issues"},"homepage":"http://atom.github.io/interval-skip-list","keywords":["data-structures","collections","intervals"],"author":{"name":"Nathan Sobo"},"licenses":[{"type":"MIT","url":"http://github.com/atom/interval-skip-list/raw/master/LICENSE.md"}],"dependencies":{"underscore":"~1.5.1"},"devDependencies":{"coffee-script":"~1.6.3","jasmine-focused":"~0.12.0","grunt-contrib-coffee":"~0.7.0","grunt-cli":"~0.1.8","grunt":"~0.4.1","grunt-shell":"~0.2.2","grunt-coffeelint":"0.0.6","rimraf":"~2.2.2"},"_id":"interval-skip-list@2.0.0","dist":{"shasum":"694cdcb23608116e1dde2da10d319f5f165ae223","tarball":"https://registry.npmjs.org/interval-skip-list/-/interval-skip-list-2.0.0.tgz","integrity":"sha512-npRNmTsi1XNgrUKgihfgF7kXvvgl79g1xjGqT62HIniEs4Ce/vlQevwDcGV976NS38oLgp5qIDPC/c+enzGZhg==","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEUCIBIHzjB3PamEgIicHfwMfe19OIGVOwi19MOArIAxyYs6AiEAnYl7VJzLaXgNbB0TrFkJEjnnQCRTZ+8GLiNe3fDcjfc="}]},"_from":".","_npmVersion":"1.4.6","_npmUser":{"name":"nathansobo","email":"nathan@github.com"},"maintainers":[{"name":"nathansobo","email":"nathansobo@gmail.com"}]},"2.0.1":{"name":"interval-skip-list","version":"2.0.1","description":"A data structure for finding all intervals that overlap a point in O(ln n)","main":"lib/interval-skip-list.js","scripts":{"prepublish":"grunt clean lint coffee","test":"grunt test"},"repository":{"type":"git","url":"http://github.com/atom/interval-skip-list.git"},"bugs":{"url":"https://github.com/atom/interval-skip-list/issues"},"homepage":"http://atom.github.io/interval-skip-list","keywords":["data-structures","collections","intervals"],"author":{"name":"Nathan Sobo"},"licenses":[{"type":"MIT","url":"http://github.com/atom/interval-skip-list/raw/master/LICENSE.md"}],"dependencies":{"underscore-plus":"^1.6.6"},"devDependencies":{"coffee-script":"~1.6.3","jasmine-focused":"~0.12.0","grunt-contrib-coffee":"~0.7.0","grunt-cli":"~0.1.8","grunt":"~0.4.1","grunt-shell":"~0.2.2","grunt-coffeelint":"0.0.6","rimraf":"~2.2.2"},"gitHead":"1585a9a3be5230766e603d5ee99a68588ae92826","_id":"interval-skip-list@2.0.1","_shasum":"a8aab16b23f80f780640de15ba159cbbc2e38035","_from":".","_npmVersion":"1.4.28","_npmUser":{"name":"kevinsawicki","email":"kevinsawicki@gmail.com"},"maintainers":[{"name":"nathansobo","email":"nathansobo@gmail.com"},{"name":"kevinsawicki","email":"kevinsawicki@gmail.com"},{"name":"zcbenz","email":"zcbenz@gmail.com"},{"name":"benogle","email":"ogle.ben@gmail.com"},{"name":"maxbrunsfeld","email":"maxbrunsfeld@gmail.com"}],"dist":{"shasum":"a8aab16b23f80f780640de15ba159cbbc2e38035","tarball":"https://registry.npmjs.org/interval-skip-list/-/interval-skip-list-2.0.1.tgz","integrity":"sha512-+s671MsDhB/3isKoTLXt+xlRxMpD5Vpj6Ve6UsIH9M9hmXGi6PCAcZUIrRe/xEoiS1zF6/ysV5Uq1a8wXI6Xcg==","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEUCIQDlHEPtmLclaLcE1IyTBeRvXEA26RLwZvUpYh5HwRRyygIgUR8zXQNXH0QXQpnJUSEaYGYHYqKfVXb59+XbFh80KC0="}]}}},"readme":"# Interval Skip List [![Build Status](https://travis-ci.org/atom/interval-skip-list.png)](https://travis-ci.org/atom/interval-skip-list)\n\nThis data structure maps intervals to values and allows you to find all\nintervals that contain an index in `O(ln(n))`, where `n` is the number of\nintervals stored. This implementation is based on the paper\n[The Interval Skip List](https://www.cise.ufl.edu/tr/DOC/REP-1992-45.pdf) by\nEric N. Hanson.\n\n## Basic Usage Example\n\n```coffee\nIntervalSkipList = require 'interval-skip-list'\nlist = new IntervalSkipList\n\nlist.insert('a', 2, 7)\nlist.insert('b', 1, 5)\nlist.insert('c', 8, 8)\n\nlist.findContaining(1) # => ['b']\nlist.findContaining(2) # => ['b', 'a']\nlist.findContaining(8) # => ['c']\n\nlist.remove('b')\n\nlist.findContaining(2) # => ['a']\n```\n\n## API\n\n* `::insert(label, startIndex, endIndex)`\n  Adds an interval with the given unique label to the list.\n\n* `::remove(label)`\n  Removes the interval with the given unique label from the list.\n\n* `::update(label, startIndex, endIndex)`\n  Inserts or updates the interval corresponding to the given unique label.\n  Unlike `::insert`, this method allows you to specify a label that's already\n  been inserted in the list.\n\n* `::findContaining(indices...)`\n  Returns the labels of all intervals containing the given indices.\n\n* `::findIntersecting(indices...)`\n  Returns the labels of all intervals intersecting the given set of indices.\n  Unlike `::findContaining`, this method does not require that the intervals\n  contain *all* the given indices.\n\n* `::findStartingAt(index)`\n  Returns the labels of all intervals starting at the given index.\n\n* `::findEndingAt(index)`\n  Returns the labels of all intervals ending at the given index.\n\n* `::findStartingIn(startIndex, endIndex)`\n  Returns the labels of all intervals starting within the interval described by\n  the given start and end indices.\n\n* `::findEndingIn(startIndex, endIndex)`\n  Returns the labels of all intervals ending within the interval described by\n  the given start and end indices.\n\n## Using a Custom Comparator\n\nYou can also supply a custom comparator function with corresponding min and max\nindex values. The following example uses arrays expressing coordinate pairs\ninstead of the default numeric values:\n\n```coffee\nlist = new IntervalSkipList\n  minIndex: [-Infinity, -Infinity]\n  maxIndex: [Infinity, Infinity]\n  compare: (a, b) ->\n    if a[0] < b[0]\n      -1\n    else if a[0] > b[0]\n      1\n    else\n      if a[1] < b[1]\n        -1\n      else if a[1] > b[1]\n        1\n      else\n        0\n\n  list.insert(\"a\", [1, 2], [3, 4])\n  list.insert(\"b\", [2, 1], [3, 10])\n  list.findContaining([1, Infinity]) # => [\"a\"]\n  list.findContaining([2, 20]) # => [\"a\", \"b\"]\n```\n","maintainers":[{"email":"atom@github.com","name":"atom-team"},{"email":"nathan@github.com","name":"nathansobo"},{"email":"kevinsawicki@gmail.com","name":"kevinsawicki"},{"email":"zcbenz@gmail.com","name":"zcbenz"},{"email":"ogle.ben@gmail.com","name":"benogle"},{"email":"maxbrunsfeld@gmail.com","name":"maxbrunsfeld"}],"time":{"modified":"2022-06-19T01:49:35.252Z","created":"2013-08-27T22:52:10.510Z","0.1.0":"2013-08-27T22:52:11.163Z","0.2.0":"2013-08-28T18:42:11.179Z","0.3.0":"2013-12-29T17:04:30.773Z","0.4.0":"2013-12-31T01:27:11.020Z","1.0.0":"2014-03-06T18:30:53.739Z","2.0.0":"2014-06-13T01:13:24.612Z","2.0.1":"2015-02-13T01:39:58.359Z"},"author":{"name":"Nathan Sobo"},"repository":{"type":"git","url":"http://github.com/atom/interval-skip-list.git"},"homepage":"http://atom.github.io/interval-skip-list","keywords":["data-structures","collections","intervals"],"bugs":{"url":"https://github.com/atom/interval-skip-list/issues"},"readmeFilename":"README.md","users":{"heineiuo":true}}